3 files changed, 164 insertions, 180 deletions

diff --git a/crates/hir_ty/src/traits/chalk.rs b/crates/hir_ty/src/traits/chalk.rs
index 011bef6f6..090f6492b 100644
--- a/crates/hir_ty/src/traits/chalk.rs
+++ b/crates/hir_ty/src/traits/chalk.rs
@@ -3,7 +3,7 @@ use std::sync::Arc;
 
 use log::debug;
 
-use chalk_ir::{fold::shift::Shift, CanonicalVarKinds, GenericArg};
+use chalk_ir::{fold::shift::Shift, CanonicalVarKinds};
 use chalk_solve::rust_ir::{self, OpaqueTyDatumBound, WellKnownTrait};
 
 use base_db::{salsa::InternKey, CrateId};
@@ -22,7 +22,7 @@ use crate::{
     to_assoc_type_id, to_chalk_trait_id,
     utils::generics,
     AliasEq, AliasTy, BoundVar, CallableDefId, DebruijnIndex, FnDefId, ProjectionTy, Substitution,
-    TraitRef, Ty, TyKind, WhereClause,
+    TraitRef, TraitRefExt, Ty, TyBuilder, TyExt, TyKind, WhereClause,
 };
 use mapping::{
     convert_where_clauses, generic_predicate_to_inline_bound, make_binders, TypeAliasAsValue,
@@ -80,7 +80,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
     fn impls_for_trait(
         &self,
         trait_id: TraitId,
-        parameters: &[GenericArg<Interner>],
+        parameters: &[chalk_ir::GenericArg<Interner>],
         binders: &CanonicalVarKinds<Interner>,
     ) -> Vec<ImplId> {
         debug!("impls_for_trait {:?}", trait_id);
@@ -92,7 +92,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
             ty: &Ty,
             binders: &CanonicalVarKinds<Interner>,
         ) -> Option<chalk_ir::TyVariableKind> {
-            if let TyKind::BoundVar(bv) = ty.interned(&Interner) {
+            if let TyKind::BoundVar(bv) = ty.kind(&Interner) {
                 let binders = binders.as_slice(&Interner);
                 if bv.debruijn == DebruijnIndex::INNERMOST {
                     if let chalk_ir::VariableKind::Ty(tk) = binders[bv.index].kind {
@@ -184,16 +184,21 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                     .db
                     .return_type_impl_traits(func)
                     .expect("impl trait id without impl traits");
-                let data = &datas.value.impl_traits[idx as usize];
+                let (datas, binders) = (*datas).as_ref().into_value_and_skipped_binders();
+                let data = &datas.impl_traits[idx as usize];
                 let bound = OpaqueTyDatumBound {
                     bounds: make_binders(
-                        data.bounds.value.iter().cloned().map(|b| b.to_chalk(self.db)).collect(),
+                        data.bounds
+                            .skip_binders()
+                            .iter()
+                            .cloned()
+                            .map(|b| b.to_chalk(self.db))
+                            .collect(),
                         1,
                     ),
                     where_clauses: make_binders(vec![], 0),
                 };
-                let num_vars = datas.num_binders;
-                make_binders(bound, num_vars)
+                chalk_ir::Binders::new(binders, bound)
             }
             crate::ImplTraitId::AsyncBlockTypeImplTrait(..) => {
                 if let Some((future_trait, future_output)) = self
@@ -215,7 +220,8 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                     let impl_bound = WhereClause::Implemented(TraitRef {
                         trait_id: to_chalk_trait_id(future_trait),
                         // Self type as the first parameter.
-                        substitution: Substitution::single(
+                        substitution: Substitution::from1(
+                            &Interner,
                             TyKind::BoundVar(BoundVar {
                                 debruijn: DebruijnIndex::INNERMOST,
                                 index: 0,
@@ -227,7 +233,8 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                         alias: AliasTy::Projection(ProjectionTy {
                             associated_ty_id: to_assoc_type_id(future_output),
                             // Self type as the first parameter.
-                            substitution: Substitution::single(
+                            substitution: Substitution::from1(
+                                &Interner,
                                 TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0))
                                     .intern(&Interner),
                             ),
@@ -239,8 +246,8 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
                     let bound = OpaqueTyDatumBound {
                         bounds: make_binders(
                             vec![
-                                wrap_in_empty_binders(impl_bound).to_chalk(self.db),
-                                wrap_in_empty_binders(proj_bound).to_chalk(self.db),
+                                crate::wrap_empty_binders(impl_bound).to_chalk(self.db),
+                                crate::wrap_empty_binders(proj_bound).to_chalk(self.db),
                             ],
                             1,
                         ),
@@ -265,7 +272,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
 
     fn hidden_opaque_type(&self, _id: chalk_ir::OpaqueTyId<Interner>) -> chalk_ir::Ty<Interner> {
         // FIXME: actually provide the hidden type; it is relevant for auto traits
-        TyKind::Unknown.intern(&Interner).to_chalk(self.db)
+        TyKind::Error.intern(&Interner).to_chalk(self.db)
     }
 
     fn is_object_safe(&self, _trait_id: chalk_ir::TraitId<Interner>) -> bool {
@@ -300,7 +307,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
         _closure_id: chalk_ir::ClosureId<Interner>,
         _substs: &chalk_ir::Substitution<Interner>,
     ) -> chalk_ir::Binders<chalk_ir::Ty<Interner>> {
-        let ty = Ty::unit().to_chalk(self.db);
+        let ty = TyBuilder::unit().to_chalk(self.db);
         make_binders(ty, 0)
     }
     fn closure_fn_substitution(
@@ -308,7 +315,7 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
         _closure_id: chalk_ir::ClosureId<Interner>,
         _substs: &chalk_ir::Substitution<Interner>,
     ) -> chalk_ir::Substitution<Interner> {
-        Substitution::empty().to_chalk(self.db)
+        Substitution::empty(&Interner).to_chalk(self.db)
     }
 
     fn trait_name(&self, trait_id: chalk_ir::TraitId<Interner>) -> String {
@@ -387,7 +394,7 @@ pub(crate) fn associated_ty_data_query(
     // Lower bounds -- we could/should maybe move this to a separate query in `lower`
     let type_alias_data = db.type_alias_data(type_alias);
     let generic_params = generics(db.upcast(), type_alias.into());
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
     let resolver = hir_def::resolver::HasResolver::resolver(type_alias, db.upcast());
     let ctx = crate::TyLoweringContext::new(db, &resolver)
         .with_type_param_mode(crate::lower::TypeParamLoweringMode::Variable);
@@ -421,7 +428,7 @@ pub(crate) fn trait_datum_query(
     let trait_data = db.trait_data(trait_);
     debug!("trait {:?} = {:?}", trait_id, trait_data.name);
     let generic_params = generics(db.upcast(), trait_.into());
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
     let flags = rust_ir::TraitFlags {
         auto: trait_data.is_auto,
         upstream: trait_.lookup(db.upcast()).container.krate() != krate,
@@ -439,7 +446,7 @@ pub(crate) fn trait_datum_query(
         lang_attr(db.upcast(), trait_).and_then(|name| well_known_trait_from_lang_attr(&name));
     let trait_datum = TraitDatum {
         id: trait_id,
-        binders: make_binders(trait_datum_bound, bound_vars.len()),
+        binders: make_binders(trait_datum_bound, bound_vars.len(&Interner)),
         flags,
         associated_ty_ids,
         well_known,
@@ -490,7 +497,7 @@ pub(crate) fn struct_datum_query(
     let upstream = adt_id.module(db.upcast()).krate() != krate;
     let where_clauses = {
         let generic_params = generics(db.upcast(), adt_id.into());
-        let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+        let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
         convert_where_clauses(db, adt_id.into(), &bound_vars)
     };
     let flags = rust_ir::AdtFlags {
@@ -535,11 +542,12 @@ fn impl_def_datum(
         .impl_trait(impl_id)
         // ImplIds for impls where the trait ref can't be resolved should never reach Chalk
         .expect("invalid impl passed to Chalk")
-        .value;
+        .into_value_and_skipped_binders()
+        .0;
     let impl_data = db.impl_data(impl_id);
 
     let generic_params = generics(db.upcast(), impl_id.into());
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
     let trait_ = trait_ref.hir_trait_id();
     let impl_type = if impl_id.lookup(db.upcast()).container.krate() == krate {
         rust_ir::ImplType::Local
@@ -577,7 +585,7 @@ fn impl_def_datum(
         .collect();
     debug!("impl_datum: {:?}", impl_datum_bound);
     let impl_datum = ImplDatum {
-        binders: make_binders(impl_datum_bound, bound_vars.len()),
+        binders: make_binders(impl_datum_bound, bound_vars.len(&Interner)),
         impl_type,
         polarity,
         associated_ty_value_ids,
@@ -605,18 +613,22 @@ fn type_alias_associated_ty_value(
         _ => panic!("assoc ty value should be in impl"),
     };
 
-    let trait_ref = db.impl_trait(impl_id).expect("assoc ty value should not exist").value; // we don't return any assoc ty values if the impl'd trait can't be resolved
+    let trait_ref = db
+        .impl_trait(impl_id)
+        .expect("assoc ty value should not exist")
+        .into_value_and_skipped_binders()
+        .0; // we don't return any assoc ty values if the impl'd trait can't be resolved
 
     let assoc_ty = db
         .trait_data(trait_ref.hir_trait_id())
         .associated_type_by_name(&type_alias_data.name)
         .expect("assoc ty value should not exist"); // validated when building the impl data as well
-    let ty = db.ty(type_alias.into());
-    let value_bound = rust_ir::AssociatedTyValueBound { ty: ty.value.to_chalk(db) };
+    let (ty, binders) = db.ty(type_alias.into()).into_value_and_skipped_binders();
+    let value_bound = rust_ir::AssociatedTyValueBound { ty: ty.to_chalk(db) };
     let value = rust_ir::AssociatedTyValue {
         impl_id: impl_id.to_chalk(db),
         associated_ty_id: to_assoc_type_id(assoc_ty),
-        value: make_binders(value_bound, ty.num_binders),
+        value: chalk_ir::Binders::new(binders, value_bound),
     };
     Arc::new(value)
 }
@@ -628,20 +640,15 @@ pub(crate) fn fn_def_datum_query(
 ) -> Arc<FnDefDatum> {
     let callable_def: CallableDefId = from_chalk(db, fn_def_id);
     let generic_params = generics(db.upcast(), callable_def.into());
-    let sig = db.callable_item_signature(callable_def);
-    let bound_vars = Substitution::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+    let (sig, binders) = db.callable_item_signature(callable_def).into_value_and_skipped_binders();
+    let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
     let where_clauses = convert_where_clauses(db, callable_def.into(), &bound_vars);
     let bound = rust_ir::FnDefDatumBound {
         // Note: Chalk doesn't actually use this information yet as far as I am aware, but we provide it anyway
         inputs_and_output: make_binders(
             rust_ir::FnDefInputsAndOutputDatum {
-                argument_types: sig
-                    .value
-                    .params()
-                    .iter()
-                    .map(|ty| ty.clone().to_chalk(db))
-                    .collect(),
-                return_type: sig.value.ret().clone().to_chalk(db),
+                argument_types: sig.params().iter().map(|ty| ty.clone().to_chalk(db)).collect(),
+                return_type: sig.ret().clone().to_chalk(db),
             }
             .shifted_in(&Interner),
             0,
@@ -650,12 +657,8 @@ pub(crate) fn fn_def_datum_query(
     };
     let datum = FnDefDatum {
         id: fn_def_id,
-        sig: chalk_ir::FnSig {
-            abi: (),
-            safety: chalk_ir::Safety::Safe,
-            variadic: sig.value.is_varargs,
-        },
-        binders: make_binders(bound, sig.num_binders),
+        sig: chalk_ir::FnSig { abi: (), safety: chalk_ir::Safety::Safe, variadic: sig.is_varargs },
+        binders: chalk_ir::Binders::new(binders, bound),
     };
     Arc::new(datum)
 }
@@ -720,7 +723,3 @@ impl From<crate::db::InternedClosureId> for chalk_ir::ClosureId<Interner> {
         chalk_ir::ClosureId(id.as_intern_id())
     }
 }
-
-fn wrap_in_empty_binders<T: crate::TypeWalk>(value: T) -> crate::Binders<T> {
-    crate::Binders::wrap_empty(value)
-}
diff --git a/crates/hir_ty/src/traits/chalk/interner.rs b/crates/hir_ty/src/traits/chalk/interner.rs
index 94e94a26d..bd9395b7e 100644
--- a/crates/hir_ty/src/traits/chalk/interner.rs
+++ b/crates/hir_ty/src/traits/chalk/interner.rs
@@ -192,59 +192,58 @@ impl chalk_ir::interner::Interner for Interner {
         tls::with_current_program(|prog| Some(prog?.debug_quantified_where_clauses(clauses, fmt)))
     }
 
-    fn intern_ty(&self, kind: chalk_ir::TyKind<Self>) -> Arc<chalk_ir::TyData<Self>> {
+    fn intern_ty(&self, kind: chalk_ir::TyKind<Self>) -> Self::InternedType {
         let flags = kind.compute_flags(self);
         Arc::new(chalk_ir::TyData { kind, flags })
     }
 
-    fn ty_data<'a>(&self, ty: &'a Arc<chalk_ir::TyData<Self>>) -> &'a chalk_ir::TyData<Self> {
+    fn ty_data<'a>(&self, ty: &'a Self::InternedType) -> &'a chalk_ir::TyData<Self> {
         ty
     }
 
-    fn intern_lifetime(
-        &self,
-        lifetime: chalk_ir::LifetimeData<Self>,
-    ) -> chalk_ir::LifetimeData<Self> {
+    fn intern_lifetime(&self, lifetime: chalk_ir::LifetimeData<Self>) -> Self::InternedLifetime {
         lifetime
     }
 
     fn lifetime_data<'a>(
         &self,
-        lifetime: &'a chalk_ir::LifetimeData<Self>,
+        lifetime: &'a Self::InternedLifetime,
     ) -> &'a chalk_ir::LifetimeData<Self> {
         lifetime
     }
 
-    fn intern_const(&self, constant: chalk_ir::ConstData<Self>) -> Arc<chalk_ir::ConstData<Self>> {
+    fn intern_const(&self, constant: chalk_ir::ConstData<Self>) -> Self::InternedConst {
         Arc::new(constant)
     }
 
-    fn const_data<'a>(
-        &self,
-        constant: &'a Arc<chalk_ir::ConstData<Self>>,
-    ) -> &'a chalk_ir::ConstData<Self> {
+    fn const_data<'a>(&self, constant: &'a Self::InternedConst) -> &'a chalk_ir::ConstData<Self> {
         constant
     }
 
-    fn const_eq(&self, _ty: &Arc<chalk_ir::TyData<Self>>, _c1: &(), _c2: &()) -> bool {
+    fn const_eq(
+        &self,
+        _ty: &Self::InternedType,
+        _c1: &Self::InternedConcreteConst,
+        _c2: &Self::InternedConcreteConst,
+    ) -> bool {
         true
     }
 
     fn intern_generic_arg(
         &self,
         parameter: chalk_ir::GenericArgData<Self>,
-    ) -> chalk_ir::GenericArgData<Self> {
+    ) -> Self::InternedGenericArg {
         parameter
     }
 
     fn generic_arg_data<'a>(
         &self,
-        parameter: &'a chalk_ir::GenericArgData<Self>,
+        parameter: &'a Self::InternedGenericArg,
     ) -> &'a chalk_ir::GenericArgData<Self> {
         parameter
     }
 
-    fn intern_goal(&self, goal: GoalData<Self>) -> Arc<GoalData<Self>> {
+    fn intern_goal(&self, goal: GoalData<Self>) -> Self::InternedGoal {
         Arc::new(goal)
     }
 
@@ -255,11 +254,11 @@ impl chalk_ir::interner::Interner for Interner {
         data.into_iter().collect()
     }
 
-    fn goal_data<'a>(&self, goal: &'a Arc<GoalData<Self>>) -> &'a GoalData<Self> {
+    fn goal_data<'a>(&self, goal: &'a Self::InternedGoal) -> &'a GoalData<Self> {
         goal
     }
 
-    fn goals_data<'a>(&self, goals: &'a Vec<Goal<Interner>>) -> &'a [Goal<Interner>] {
+    fn goals_data<'a>(&self, goals: &'a Self::InternedGoals) -> &'a [Goal<Interner>] {
         goals
     }
 
@@ -280,13 +279,13 @@ impl chalk_ir::interner::Interner for Interner {
     fn intern_program_clause(
         &self,
         data: chalk_ir::ProgramClauseData<Self>,
-    ) -> Arc<chalk_ir::ProgramClauseData<Self>> {
+    ) -> Self::InternedProgramClause {
         Arc::new(data)
     }
 
     fn program_clause_data<'a>(
         &self,
-        clause: &'a Arc<chalk_ir::ProgramClauseData<Self>>,
+        clause: &'a Self::InternedProgramClause,
     ) -> &'a chalk_ir::ProgramClauseData<Self> {
         clause
     }
@@ -294,13 +293,13 @@ impl chalk_ir::interner::Interner for Interner {
     fn intern_program_clauses<E>(
         &self,
         data: impl IntoIterator<Item = Result<chalk_ir::ProgramClause<Self>, E>>,
-    ) -> Result<Arc<[chalk_ir::ProgramClause<Self>]>, E> {
+    ) -> Result<Self::InternedProgramClauses, E> {
         data.into_iter().collect()
     }
 
     fn program_clauses_data<'a>(
         &self,
-        clauses: &'a Arc<[chalk_ir::ProgramClause<Self>]>,
+        clauses: &'a Self::InternedProgramClauses,
     ) -> &'a [chalk_ir::ProgramClause<Self>] {
         &clauses
     }
diff --git a/crates/hir_ty/src/traits/chalk/mapping.rs b/crates/hir_ty/src/traits/chalk/mapping.rs
index aef6b8a15..701359e6f 100644
--- a/crates/hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/hir_ty/src/traits/chalk/mapping.rs
@@ -3,18 +3,16 @@
 //! Chalk (in both directions); plus some helper functions for more specialized
 //! conversions.
 
-use chalk_ir::{cast::Cast, fold::shift::Shift, interner::HasInterner, LifetimeData};
+use chalk_ir::{cast::Cast, interner::HasInterner};
 use chalk_solve::rust_ir;
 
 use base_db::salsa::InternKey;
 use hir_def::{GenericDefId, TypeAliasId};
 
 use crate::{
-    db::HirDatabase,
-    primitive::UintTy,
-    traits::{Canonical, DomainGoal},
-    AliasTy, CallableDefId, FnPointer, InEnvironment, OpaqueTy, ProjectionTy,
-    QuantifiedWhereClause, Scalar, Substitution, TraitRef, Ty, TypeWalk, WhereClause,
+    db::HirDatabase, static_lifetime, AliasTy, CallableDefId, Canonical, ConstrainedSubst,
+    DomainGoal, FnPointer, GenericArg, InEnvironment, OpaqueTy, ProjectionTy, ProjectionTyExt,
+    QuantifiedWhereClause, Substitution, TraitRef, Ty, TypeWalk, WhereClause,
 };
 
 use super::interner::*;
@@ -24,16 +22,16 @@ impl ToChalk for Ty {
     type Chalk = chalk_ir::Ty<Interner>;
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Ty<Interner> {
         match self.into_inner() {
-            TyKind::Ref(m, ty) => ref_to_chalk(db, m, ty),
-            TyKind::Array(ty) => array_to_chalk(db, ty),
-            TyKind::Function(FnPointer { sig, substs, .. }) => {
-                let substitution = chalk_ir::FnSubst(substs.to_chalk(db).shifted_in(&Interner));
-                chalk_ir::TyKind::Function(chalk_ir::FnPointer {
-                    num_binders: 0,
-                    sig,
-                    substitution,
-                })
-                .intern(&Interner)
+            TyKind::Ref(m, lt, ty) => {
+                chalk_ir::TyKind::Ref(m, lt, ty.to_chalk(db)).intern(&Interner)
+            }
+            TyKind::Array(ty, size) => {
+                chalk_ir::TyKind::Array(ty.to_chalk(db), size).intern(&Interner)
+            }
+            TyKind::Function(FnPointer { sig, substitution: substs, num_binders }) => {
+                let substitution = chalk_ir::FnSubst(substs.0.to_chalk(db));
+                chalk_ir::TyKind::Function(chalk_ir::FnPointer { num_binders, sig, substitution })
+                    .intern(&Interner)
             }
             TyKind::AssociatedType(assoc_type_id, substs) => {
                 let substitution = substs.to_chalk(db);
@@ -45,7 +43,7 @@ impl ToChalk for Ty {
                 chalk_ir::TyKind::OpaqueType(id, substitution).intern(&Interner)
             }
 
-            TyKind::ForeignType(id) => chalk_ir::TyKind::Foreign(id).intern(&Interner),
+            TyKind::Foreign(id) => chalk_ir::TyKind::Foreign(id).intern(&Interner),
 
             TyKind::Scalar(scalar) => chalk_ir::TyKind::Scalar(scalar).intern(&Interner),
 
@@ -75,56 +73,41 @@ impl ToChalk for Ty {
                 chalk_ir::TyKind::Adt(adt_id, substitution).intern(&Interner)
             }
             TyKind::Alias(AliasTy::Projection(proj_ty)) => {
-                let associated_ty_id = proj_ty.associated_ty_id;
-                let substitution = proj_ty.substitution.to_chalk(db);
-                chalk_ir::AliasTy::Projection(chalk_ir::ProjectionTy {
-                    associated_ty_id,
-                    substitution,
-                })
-                .cast(&Interner)
-                .intern(&Interner)
-            }
-            TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
-                let opaque_ty_id = opaque_ty.opaque_ty_id;
-                let substitution = opaque_ty.substitution.to_chalk(db);
-                chalk_ir::AliasTy::Opaque(chalk_ir::OpaqueTy { opaque_ty_id, substitution })
+                chalk_ir::AliasTy::Projection(proj_ty.to_chalk(db))
                     .cast(&Interner)
                     .intern(&Interner)
             }
+            TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
+                chalk_ir::AliasTy::Opaque(opaque_ty.to_chalk(db)).cast(&Interner).intern(&Interner)
+            }
             TyKind::Placeholder(idx) => idx.to_ty::<Interner>(&Interner),
             TyKind::BoundVar(idx) => chalk_ir::TyKind::BoundVar(idx).intern(&Interner),
             TyKind::InferenceVar(..) => panic!("uncanonicalized infer ty"),
             TyKind::Dyn(dyn_ty) => {
+                let (bounds, binders) = dyn_ty.bounds.into_value_and_skipped_binders();
                 let where_clauses = chalk_ir::QuantifiedWhereClauses::from_iter(
                     &Interner,
-                    dyn_ty.bounds.value.interned().iter().cloned().map(|p| p.to_chalk(db)),
+                    bounds.interned().iter().cloned().map(|p| p.to_chalk(db)),
                 );
                 let bounded_ty = chalk_ir::DynTy {
-                    bounds: make_binders(where_clauses, 1),
-                    lifetime: LifetimeData::Static.intern(&Interner),
+                    bounds: chalk_ir::Binders::new(binders, where_clauses),
+                    lifetime: dyn_ty.lifetime,
                 };
                 chalk_ir::TyKind::Dyn(bounded_ty).intern(&Interner)
             }
-            TyKind::Unknown => chalk_ir::TyKind::Error.intern(&Interner),
+            TyKind::Error => chalk_ir::TyKind::Error.intern(&Interner),
         }
     }
     fn from_chalk(db: &dyn HirDatabase, chalk: chalk_ir::Ty<Interner>) -> Self {
         match chalk.data(&Interner).kind.clone() {
-            chalk_ir::TyKind::Error => TyKind::Unknown,
-            chalk_ir::TyKind::Array(ty, _size) => TyKind::Array(from_chalk(db, ty)),
+            chalk_ir::TyKind::Error => TyKind::Error,
+            chalk_ir::TyKind::Array(ty, size) => TyKind::Array(from_chalk(db, ty), size),
             chalk_ir::TyKind::Placeholder(idx) => TyKind::Placeholder(idx),
             chalk_ir::TyKind::Alias(chalk_ir::AliasTy::Projection(proj)) => {
-                let associated_ty = proj.associated_ty_id;
-                let parameters = from_chalk(db, proj.substitution);
-                TyKind::Alias(AliasTy::Projection(ProjectionTy {
-                    associated_ty_id: associated_ty,
-                    substitution: parameters,
-                }))
+                TyKind::Alias(AliasTy::Projection(from_chalk(db, proj)))
             }
             chalk_ir::TyKind::Alias(chalk_ir::AliasTy::Opaque(opaque_ty)) => {
-                let opaque_ty_id = opaque_ty.opaque_ty_id;
-                let parameters = from_chalk(db, opaque_ty.substitution);
-                TyKind::Alias(AliasTy::Opaque(OpaqueTy { opaque_ty_id, substitution: parameters }))
+                TyKind::Alias(AliasTy::Opaque(from_chalk(db, opaque_ty)))
             }
             chalk_ir::TyKind::Function(chalk_ir::FnPointer {
                 num_binders,
@@ -133,26 +116,25 @@ impl ToChalk for Ty {
                 ..
             }) => {
                 assert_eq!(num_binders, 0);
-                let substs: Substitution = from_chalk(
-                    db,
-                    substitution.0.shifted_out(&Interner).expect("fn ptr should have no binders"),
-                );
-                TyKind::Function(FnPointer { num_args: (substs.len() - 1), sig, substs })
+                let substs = crate::FnSubst(from_chalk(db, substitution.0));
+                TyKind::Function(FnPointer { num_binders, sig, substitution: substs })
             }
             chalk_ir::TyKind::BoundVar(idx) => TyKind::BoundVar(idx),
-            chalk_ir::TyKind::InferenceVar(_iv, _kind) => TyKind::Unknown,
-            chalk_ir::TyKind::Dyn(where_clauses) => {
-                assert_eq!(where_clauses.bounds.binders.len(&Interner), 1);
-                let bounds = where_clauses
-                    .bounds
-                    .skip_binders()
-                    .iter(&Interner)
-                    .map(|c| from_chalk(db, c.clone()));
+            chalk_ir::TyKind::InferenceVar(_iv, _kind) => TyKind::Error,
+            chalk_ir::TyKind::Dyn(dyn_ty) => {
+                assert_eq!(dyn_ty.bounds.binders.len(&Interner), 1);
+                let (bounds, binders) = dyn_ty.bounds.into_value_and_skipped_binders();
+                let where_clauses = crate::QuantifiedWhereClauses::from_iter(
+                    &Interner,
+                    bounds.interned().iter().cloned().map(|p| from_chalk(db, p)),
+                );
                 TyKind::Dyn(crate::DynTy {
-                    bounds: crate::Binders::new(
-                        1,
-                        crate::QuantifiedWhereClauses::from_iter(&Interner, bounds),
-                    ),
+                    bounds: crate::Binders::new(binders, where_clauses),
+                    // HACK: we sometimes get lifetime variables back in solutions
+                    // from Chalk, and don't have the infrastructure to substitute
+                    // them yet. So for now we just turn them into 'static right
+                    // when we get them
+                    lifetime: static_lifetime(),
                 })
             }
 
@@ -172,7 +154,11 @@ impl ToChalk for Ty {
             chalk_ir::TyKind::Raw(mutability, ty) => TyKind::Raw(mutability, from_chalk(db, ty)),
             chalk_ir::TyKind::Slice(ty) => TyKind::Slice(from_chalk(db, ty)),
             chalk_ir::TyKind::Ref(mutability, _lifetime, ty) => {
-                TyKind::Ref(mutability, from_chalk(db, ty))
+                // HACK: we sometimes get lifetime variables back in solutions
+                // from Chalk, and don't have the infrastructure to substitute
+                // them yet. So for now we just turn them into 'static right
+                // when we get them
+                TyKind::Ref(mutability, static_lifetime(), from_chalk(db, ty))
             }
             chalk_ir::TyKind::Str => TyKind::Str,
             chalk_ir::TyKind::Never => TyKind::Never,
@@ -183,7 +169,7 @@ impl ToChalk for Ty {
 
             chalk_ir::TyKind::Closure(id, subst) => TyKind::Closure(id, from_chalk(db, subst)),
 
-            chalk_ir::TyKind::Foreign(foreign_def_id) => TyKind::ForeignType(foreign_def_id),
+            chalk_ir::TyKind::Foreign(foreign_def_id) => TyKind::Foreign(foreign_def_id),
             chalk_ir::TyKind::Generator(_, _) => unimplemented!(), // FIXME
             chalk_ir::TyKind::GeneratorWitness(_, _) => unimplemented!(), // FIXME
         }
@@ -191,50 +177,40 @@ impl ToChalk for Ty {
     }
 }
 
-/// We currently don't model lifetimes, but Chalk does. So, we have to insert a
-/// fake lifetime here, because Chalks built-in logic may expect it to be there.
-fn ref_to_chalk(
-    db: &dyn HirDatabase,
-    mutability: chalk_ir::Mutability,
-    ty: Ty,
-) -> chalk_ir::Ty<Interner> {
-    let arg = ty.to_chalk(db);
-    let lifetime = LifetimeData::Static.intern(&Interner);
-    chalk_ir::TyKind::Ref(mutability, lifetime, arg).intern(&Interner)
-}
+impl ToChalk for GenericArg {
+    type Chalk = chalk_ir::GenericArg<Interner>;
+
+    fn to_chalk(self, db: &dyn HirDatabase) -> Self::Chalk {
+        match self.interned() {
+            crate::GenericArgData::Ty(ty) => ty.clone().to_chalk(db).cast(&Interner),
+        }
+    }
 
-/// We currently don't model constants, but Chalk does. So, we have to insert a
-/// fake constant here, because Chalks built-in logic may expect it to be there.
-fn array_to_chalk(db: &dyn HirDatabase, ty: Ty) -> chalk_ir::Ty<Interner> {
-    let arg = ty.to_chalk(db);
-    let usize_ty = chalk_ir::TyKind::Scalar(Scalar::Uint(UintTy::Usize)).intern(&Interner);
-    let const_ = chalk_ir::ConstData {
-        ty: usize_ty,
-        value: chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst { interned: () }),
-    }
-    .intern(&Interner);
-    chalk_ir::TyKind::Array(arg, const_).intern(&Interner)
+    fn from_chalk(db: &dyn HirDatabase, chalk: Self::Chalk) -> Self {
+        match chalk.interned() {
+            chalk_ir::GenericArgData::Ty(ty) => Ty::from_chalk(db, ty.clone()).cast(&Interner),
+            chalk_ir::GenericArgData::Lifetime(_) => unimplemented!(),
+            chalk_ir::GenericArgData::Const(_) => unimplemented!(),
+        }
+    }
 }
 
 impl ToChalk for Substitution {
     type Chalk = chalk_ir::Substitution<Interner>;
 
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Substitution<Interner> {
-        chalk_ir::Substitution::from_iter(&Interner, self.iter().map(|ty| ty.clone().to_chalk(db)))
+        chalk_ir::Substitution::from_iter(
+            &Interner,
+            self.iter(&Interner).map(|ty| ty.clone().to_chalk(db)),
+        )
     }
 
     fn from_chalk(
         db: &dyn HirDatabase,
         parameters: chalk_ir::Substitution<Interner>,
     ) -> Substitution {
-        let tys = parameters
-            .iter(&Interner)
-            .map(|p| match p.ty(&Interner) {
-                Some(ty) => from_chalk(db, ty.clone()),
-                None => unimplemented!(),
-            })
-            .collect();
-        Substitution(tys)
+        let tys = parameters.iter(&Interner).map(|p| from_chalk(db, p.clone())).collect();
+        Substitution::intern(tys)
     }
 }
 
@@ -473,19 +449,25 @@ where
     type Chalk = chalk_ir::Binders<T::Chalk>;
 
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Binders<T::Chalk> {
-        chalk_ir::Binders::new(
-            chalk_ir::VariableKinds::from_iter(
-                &Interner,
-                std::iter::repeat(chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General))
-                    .take(self.num_binders),
-            ),
-            self.value.to_chalk(db),
-        )
+        let (value, binders) = self.into_value_and_skipped_binders();
+        chalk_ir::Binders::new(binders, value.to_chalk(db))
     }
 
     fn from_chalk(db: &dyn HirDatabase, binders: chalk_ir::Binders<T::Chalk>) -> crate::Binders<T> {
         let (v, b) = binders.into_value_and_skipped_binders();
-        crate::Binders::new(b.len(&Interner), from_chalk(db, v))
+        crate::Binders::new(b, from_chalk(db, v))
+    }
+}
+
+impl ToChalk for crate::ConstrainedSubst {
+    type Chalk = chalk_ir::ConstrainedSubst<Interner>;
+
+    fn to_chalk(self, _db: &dyn HirDatabase) -> Self::Chalk {
+        unimplemented!()
+    }
+
+    fn from_chalk(db: &dyn HirDatabase, chalk: Self::Chalk) -> Self {
+        ConstrainedSubst { subst: from_chalk(db, chalk.subst) }
     }
 }
 
@@ -511,7 +493,7 @@ pub(super) fn convert_where_clauses(
     let generic_predicates = db.generic_predicates(def);
     let mut result = Vec::with_capacity(generic_predicates.len());
     for pred in generic_predicates.iter() {
-        result.push(pred.clone().subst(substs).to_chalk(db));
+        result.push(pred.clone().substitute(&Interner, substs).to_chalk(db));
     }
     result
 }
@@ -523,27 +505,28 @@ pub(super) fn generic_predicate_to_inline_bound(
 ) -> Option<chalk_ir::Binders<rust_ir::InlineBound<Interner>>> {
     // An InlineBound is like a GenericPredicate, except the self type is left out.
     // We don't have a special type for this, but Chalk does.
-    let self_ty_shifted_in = self_ty.clone().shift_bound_vars(DebruijnIndex::ONE);
-    match &pred.value {
+    let self_ty_shifted_in = self_ty.clone().shifted_in_from(DebruijnIndex::ONE);
+    let (pred, binders) = pred.as_ref().into_value_and_skipped_binders();
+    match pred {
         WhereClause::Implemented(trait_ref) => {
-            if trait_ref.self_type_parameter() != &self_ty_shifted_in {
+            if trait_ref.self_type_parameter(&Interner) != self_ty_shifted_in {
                 // we can only convert predicates back to type bounds if they
                 // have the expected self type
                 return None;
             }
-            let args_no_self = trait_ref.substitution[1..]
+            let args_no_self = trait_ref.substitution.interned()[1..]
                 .iter()
                 .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
                 .collect();
             let trait_bound = rust_ir::TraitBound { trait_id: trait_ref.trait_id, args_no_self };
-            Some(make_binders(rust_ir::InlineBound::TraitBound(trait_bound), pred.num_binders))
+            Some(chalk_ir::Binders::new(binders, rust_ir::InlineBound::TraitBound(trait_bound)))
         }
         WhereClause::AliasEq(AliasEq { alias: AliasTy::Projection(projection_ty), ty }) => {
-            if projection_ty.self_type_parameter() != &self_ty_shifted_in {
+            if projection_ty.self_type_parameter(&Interner) != self_ty_shifted_in {
                 return None;
             }
             let trait_ = projection_ty.trait_(db);
-            let args_no_self = projection_ty.substitution[1..]
+            let args_no_self = projection_ty.substitution.interned()[1..]
                 .iter()
                 .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
                 .collect();
@@ -553,7 +536,10 @@ pub(super) fn generic_predicate_to_inline_bound(
                 associated_ty_id: projection_ty.associated_ty_id,
                 parameters: Vec::new(), // FIXME we don't support generic associated types yet
             };
-            Some(make_binders(rust_ir::InlineBound::AliasEqBound(alias_eq_bound), pred.num_binders))
+            Some(chalk_ir::Binders::new(
+                binders,
+                rust_ir::InlineBound::AliasEqBound(alias_eq_bound),
+            ))
         }
         _ => None,
     }