Merge #8348

8348: Make `Binders` more like Chalk r=flodiebold a=flodiebold

Working towards #8313.
 - hide `value`
 - use `VariableKinds`
 - adjust `subst` to be like Chalk's `substitute`
 - also clean up some other `TypeWalk` stuff to prepare for it being replaced by Chalk's `Fold`

Co-authored-by: Florian Diebold <[email protected]>

20 files changed, 296 insertions, 228 deletions

diff --git a/crates/hir/src/display.rs b/crates/hir/src/display.rs
index 993772aac..01a4d205f 100644
--- a/crates/hir/src/display.rs
+++ b/crates/hir/src/display.rs
@@ -9,6 +9,7 @@ use hir_ty::display::{
     write_bounds_like_dyn_trait_with_prefix, write_visibility, HirDisplay, HirDisplayError,
     HirFormatter,
 };
+use hir_ty::Interner;
 use syntax::ast::{self, NameOwner};
 
 use crate::{
@@ -235,7 +236,8 @@ impl HirDisplay for TypeParam {
         write!(f, "{}", self.name(f.db))?;
         let bounds = f.db.generic_predicates_for_param(self.id);
         let substs = TyBuilder::type_params_subst(f.db, self.id.parent);
-        let predicates = bounds.iter().cloned().map(|b| b.subst(&substs)).collect::<Vec<_>>();
+        let predicates =
+            bounds.iter().cloned().map(|b| b.substitute(&Interner, &substs)).collect::<Vec<_>>();
         if !(predicates.is_empty() || f.omit_verbose_types()) {
             write_bounds_like_dyn_trait_with_prefix(":", &predicates, f)?;
         }
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index b14c9a675..003821981 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -516,7 +516,7 @@ impl Field {
             VariantDef::Variant(it) => it.parent.id.into(),
         };
         let substs = TyBuilder::type_params_subst(db, generic_def_id);
-        let ty = db.field_types(var_id)[self.id].clone().subst(&substs);
+        let ty = db.field_types(var_id)[self.id].clone().substitute(&Interner, &substs);
         Type::new(db, self.parent.module(db).id.krate(), var_id, ty)
     }
 
@@ -702,7 +702,7 @@ impl_from!(Struct, Union, Enum for Adt);
 impl Adt {
     pub fn has_non_default_type_params(self, db: &dyn HirDatabase) -> bool {
         let subst = db.generic_defaults(self.into());
-        subst.iter().any(|ty| ty.value.is_unknown())
+        subst.iter().any(|ty| ty.skip_binders().is_unknown())
     }
 
     /// Turns this ADT into a type. Any type parameters of the ADT will be
@@ -1089,7 +1089,7 @@ pub struct TypeAlias {
 impl TypeAlias {
     pub fn has_non_default_type_params(self, db: &dyn HirDatabase) -> bool {
         let subst = db.generic_defaults(self.id.into());
-        subst.iter().any(|ty| ty.value.is_unknown())
+        subst.iter().any(|ty| ty.skip_binders().is_unknown())
     }
 
     pub fn module(self, db: &dyn HirDatabase) -> Module {
@@ -1503,7 +1503,7 @@ impl TypeParam {
         let krate = self.id.parent.module(db.upcast()).krate();
         let ty = params.get(local_idx)?.clone();
         let subst = TyBuilder::type_params_subst(db, self.id.parent);
-        let ty = ty.subst(&subst.prefix(local_idx));
+        let ty = ty.substitute(&Interner, &subst.prefix(local_idx));
         Some(Type::new_with_resolver_inner(db, krate, &resolver, ty))
     }
 }
@@ -1916,7 +1916,7 @@ impl Type {
             .iter()
             .map(|(local_id, ty)| {
                 let def = Field { parent: variant_id.into(), id: local_id };
-                let ty = ty.clone().subst(substs);
+                let ty = ty.clone().substitute(&Interner, substs);
                 (def, self.derived(ty))
             })
             .collect()
diff --git a/crates/hir/src/semantics.rs b/crates/hir/src/semantics.rs
index 3bf722d2a..7955bf0b5 100644
--- a/crates/hir/src/semantics.rs
+++ b/crates/hir/src/semantics.rs
@@ -494,9 +494,9 @@ impl<'db> SemanticsImpl<'db> {
     fn resolve_method_call_as_callable(&self, call: &ast::MethodCallExpr) -> Option<Callable> {
         // FIXME: this erases Substs
         let func = self.resolve_method_call(call)?;
-        let ty = self.db.value_ty(func.into());
+        let (ty, _) = self.db.value_ty(func.into()).into_value_and_skipped_binders();
         let resolver = self.analyze(call.syntax()).resolver;
-        let ty = Type::new_with_resolver(self.db, &resolver, ty.value)?;
+        let ty = Type::new_with_resolver(self.db, &resolver, ty)?;
         let mut res = ty.as_callable(self.db)?;
         res.is_bound_method = true;
         Some(res)
diff --git a/crates/hir/src/source_analyzer.rs b/crates/hir/src/source_analyzer.rs
index 8e9ea0a03..4ce1c2080 100644
--- a/crates/hir/src/source_analyzer.rs
+++ b/crates/hir/src/source_analyzer.rs
@@ -20,7 +20,7 @@ use hir_def::{
 use hir_expand::{hygiene::Hygiene, name::AsName, HirFileId, InFile};
 use hir_ty::{
     diagnostics::{record_literal_missing_fields, record_pattern_missing_fields},
-    InferenceResult, Substitution, TyLoweringContext,
+    InferenceResult, Interner, Substitution, TyLoweringContext,
 };
 use syntax::{
     ast::{self, AstNode},
@@ -339,7 +339,7 @@ impl SourceAnalyzer {
             .into_iter()
             .map(|local_id| {
                 let field = FieldId { parent: variant, local_id };
-                let ty = field_types[local_id].clone().subst(substs);
+                let ty = field_types[local_id].clone().substitute(&Interner, substs);
                 (field.into(), Type::new_with_resolver_inner(db, krate, &self.resolver, ty))
             })
             .collect()
diff --git a/crates/hir_ty/src/builder.rs b/crates/hir_ty/src/builder.rs
index 372621f73..9b2c6975a 100644
--- a/crates/hir_ty/src/builder.rs
+++ b/crates/hir_ty/src/builder.rs
@@ -139,7 +139,8 @@ impl TyBuilder<hir_def::AdtId> {
             } else {
                 // each default can depend on the previous parameters
                 let subst_so_far = Substitution::intern(self.vec.clone());
-                self.vec.push(default_ty.clone().subst(&subst_so_far).cast(&Interner));
+                self.vec
+                    .push(default_ty.clone().substitute(&Interner, &subst_so_far).cast(&Interner));
             }
         }
         self
@@ -194,13 +195,13 @@ impl TyBuilder<TypeAliasId> {
 
 impl<T: TypeWalk + HasInterner<Interner = Interner>> TyBuilder<Binders<T>> {
     fn subst_binders(b: Binders<T>) -> Self {
-        let param_count = b.num_binders;
+        let param_count = b.binders.len(&Interner);
         TyBuilder::new(b, param_count)
     }
 
     pub fn build(self) -> T {
         let (b, subst) = self.build_internal();
-        b.subst(&subst)
+        b.substitute(&Interner, &subst)
     }
 }
 
diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs
index 8169b759f..db278d0db 100644
--- a/crates/hir_ty/src/diagnostics/expr.rs
+++ b/crates/hir_ty/src/diagnostics/expr.rs
@@ -245,7 +245,8 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
                     Some(callee) => callee,
                     None => return,
                 };
-                let sig = db.callable_item_signature(callee.into()).value;
+                let sig =
+                    db.callable_item_signature(callee.into()).into_value_and_skipped_binders().0;
 
                 (sig, args)
             }
diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs
index 1108e5a10..f31e6b108 100644
--- a/crates/hir_ty/src/display.rs
+++ b/crates/hir_ty/src/display.rs
@@ -352,8 +352,8 @@ impl HirDisplay for Ty {
                             let data = (*datas)
                                 .as_ref()
                                 .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
-                            let bounds = data.subst(parameters);
-                            bounds.value
+                            let bounds = data.substitute(&Interner, parameters);
+                            bounds.into_value_and_skipped_binders().0
                         } else {
                             Vec::new()
                         }
@@ -397,7 +397,7 @@ impl HirDisplay for Ty {
             }
             TyKind::FnDef(def, parameters) => {
                 let def = from_chalk(f.db, *def);
-                let sig = f.db.callable_item_signature(def).subst(parameters);
+                let sig = f.db.callable_item_signature(def).substitute(&Interner, parameters);
                 match def {
                     CallableDefId::FunctionId(ff) => {
                         write!(f, "fn {}", f.db.function_data(ff).name)?
@@ -482,7 +482,7 @@ impl HirDisplay for Ty {
                                         (_, Some(default_parameter)) => {
                                             let actual_default = default_parameter
                                                 .clone()
-                                                .subst(&parameters.prefix(i));
+                                                .substitute(&Interner, &parameters.prefix(i));
                                             if parameter.assert_ty_ref(&Interner) != &actual_default
                                             {
                                                 default_from = i + 1;
@@ -542,8 +542,8 @@ impl HirDisplay for Ty {
                         let data = (*datas)
                             .as_ref()
                             .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
-                        let bounds = data.subst(&parameters);
-                        write_bounds_like_dyn_trait_with_prefix("impl", &bounds.value, f)?;
+                        let bounds = data.substitute(&Interner, &parameters);
+                        write_bounds_like_dyn_trait_with_prefix("impl", bounds.skip_binders(), f)?;
                         // FIXME: it would maybe be good to distinguish this from the alias type (when debug printing), and to show the substitution
                     }
                     ImplTraitId::AsyncBlockTypeImplTrait(..) => {
@@ -595,7 +595,7 @@ impl HirDisplay for Ty {
                         let bounds =
                             f.db.generic_predicates(id.parent)
                                 .into_iter()
-                                .map(|pred| pred.clone().subst(&substs))
+                                .map(|pred| pred.clone().substitute(&Interner, &substs))
                                 .filter(|wc| match &wc.skip_binders() {
                                     WhereClause::Implemented(tr) => {
                                         tr.self_type_parameter(&Interner) == self
@@ -629,8 +629,8 @@ impl HirDisplay for Ty {
                         let data = (*datas)
                             .as_ref()
                             .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
-                        let bounds = data.subst(&opaque_ty.substitution);
-                        write_bounds_like_dyn_trait_with_prefix("impl", &bounds.value, f)?;
+                        let bounds = data.substitute(&Interner, &opaque_ty.substitution);
+                        write_bounds_like_dyn_trait_with_prefix("impl", bounds.skip_binders(), f)?;
                     }
                     ImplTraitId::AsyncBlockTypeImplTrait(..) => {
                         write!(f, "{{async block}}")?;
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index 6151e48cd..1c3faf5cb 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -470,25 +470,25 @@ impl<'a> InferenceContext<'a> {
             TypeNs::AdtId(AdtId::StructId(strukt)) => {
                 let substs = ctx.substs_from_path(path, strukt.into(), true);
                 let ty = self.db.ty(strukt.into());
-                let ty = self.insert_type_vars(ty.subst(&substs));
+                let ty = self.insert_type_vars(ty.substitute(&Interner, &substs));
                 forbid_unresolved_segments((ty, Some(strukt.into())), unresolved)
             }
             TypeNs::AdtId(AdtId::UnionId(u)) => {
                 let substs = ctx.substs_from_path(path, u.into(), true);
                 let ty = self.db.ty(u.into());
-                let ty = self.insert_type_vars(ty.subst(&substs));
+                let ty = self.insert_type_vars(ty.substitute(&Interner, &substs));
                 forbid_unresolved_segments((ty, Some(u.into())), unresolved)
             }
             TypeNs::EnumVariantId(var) => {
                 let substs = ctx.substs_from_path(path, var.into(), true);
                 let ty = self.db.ty(var.parent.into());
-                let ty = self.insert_type_vars(ty.subst(&substs));
+                let ty = self.insert_type_vars(ty.substitute(&Interner, &substs));
                 forbid_unresolved_segments((ty, Some(var.into())), unresolved)
             }
             TypeNs::SelfType(impl_id) => {
                 let generics = crate::utils::generics(self.db.upcast(), impl_id.into());
                 let substs = generics.type_params_subst(self.db);
-                let ty = self.db.impl_self_ty(impl_id).subst(&substs);
+                let ty = self.db.impl_self_ty(impl_id).substitute(&Interner, &substs);
                 match unresolved {
                     None => {
                         let variant = ty_variant(&ty);
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index ccaae53e9..6966d26e7 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -419,7 +419,7 @@ impl<'a> InferenceContext<'a> {
                         self.result.record_field_resolutions.insert(field.expr, field_def);
                     }
                     let field_ty = field_def.map_or(self.err_ty(), |it| {
-                        field_types[it.local_id].clone().subst(&substs)
+                        field_types[it.local_id].clone().substitute(&Interner, &substs)
                     });
                     self.infer_expr_coerce(field.expr, &Expectation::has_type(field_ty));
                 }
@@ -462,7 +462,7 @@ impl<'a> InferenceContext<'a> {
                                 Some(
                                     self.db.field_types((*s).into())[field.local_id]
                                         .clone()
-                                        .subst(&parameters),
+                                        .substitute(&Interner, &parameters),
                                 )
                             } else {
                                 None
@@ -476,7 +476,7 @@ impl<'a> InferenceContext<'a> {
                                 Some(
                                     self.db.field_types((*u).into())[field.local_id]
                                         .clone()
-                                        .subst(&parameters),
+                                        .substitute(&Interner, &parameters),
                                 )
                             } else {
                                 None
@@ -849,10 +849,10 @@ impl<'a> InferenceContext<'a> {
                 self.write_method_resolution(tgt_expr, func);
                 (ty, self.db.value_ty(func.into()), Some(generics(self.db.upcast(), func.into())))
             }
-            None => (receiver_ty, Binders::new(0, self.err_ty()), None),
+            None => (receiver_ty, Binders::empty(&Interner, self.err_ty()), None),
         };
         let substs = self.substs_for_method_call(def_generics, generic_args, &derefed_receiver_ty);
-        let method_ty = method_ty.subst(&substs);
+        let method_ty = method_ty.substitute(&Interner, &substs);
         let method_ty = self.insert_type_vars(method_ty);
         self.register_obligations_for_call(&method_ty);
         let (expected_receiver_ty, param_tys, ret_ty) = match method_ty.callable_sig(self.db) {
@@ -949,9 +949,11 @@ impl<'a> InferenceContext<'a> {
             let def: CallableDefId = from_chalk(self.db, *fn_def);
             let generic_predicates = self.db.generic_predicates(def.into());
             for predicate in generic_predicates.iter() {
-                let (predicate, binders) =
-                    predicate.clone().subst(parameters).into_value_and_skipped_binders();
-                always!(binders == 0); // quantified where clauses not yet handled
+                let (predicate, binders) = predicate
+                    .clone()
+                    .substitute(&Interner, parameters)
+                    .into_value_and_skipped_binders();
+                always!(binders.len(&Interner) == 0); // quantified where clauses not yet handled
                 self.push_obligation(predicate.cast(&Interner));
             }
             // add obligation for trait implementation, if this is a trait method
diff --git a/crates/hir_ty/src/infer/pat.rs b/crates/hir_ty/src/infer/pat.rs
index 469f37dd9..252ae914a 100644
--- a/crates/hir_ty/src/infer/pat.rs
+++ b/crates/hir_ty/src/infer/pat.rs
@@ -49,7 +49,9 @@ impl<'a> InferenceContext<'a> {
             let expected_ty = var_data
                 .as_ref()
                 .and_then(|d| d.field(&Name::new_tuple_field(i)))
-                .map_or(self.err_ty(), |field| field_tys[field].clone().subst(&substs));
+                .map_or(self.err_ty(), |field| {
+                    field_tys[field].clone().substitute(&Interner, &substs)
+                });
             let expected_ty = self.normalize_associated_types_in(expected_ty);
             self.infer_pat(subpat, &expected_ty, default_bm);
         }
@@ -83,8 +85,9 @@ impl<'a> InferenceContext<'a> {
                 self.result.record_pat_field_resolutions.insert(subpat.pat, field_def);
             }
 
-            let expected_ty = matching_field
-                .map_or(self.err_ty(), |field| field_tys[field].clone().subst(&substs));
+            let expected_ty = matching_field.map_or(self.err_ty(), |field| {
+                field_tys[field].clone().substitute(&Interner, &substs)
+            });
             let expected_ty = self.normalize_associated_types_in(expected_ty);
             self.infer_pat(subpat.pat, &expected_ty, default_bm);
         }
diff --git a/crates/hir_ty/src/infer/path.rs b/crates/hir_ty/src/infer/path.rs
index 89d78e781..14f705173 100644
--- a/crates/hir_ty/src/infer/path.rs
+++ b/crates/hir_ty/src/infer/path.rs
@@ -81,9 +81,9 @@ impl<'a> InferenceContext<'a> {
             ValueNs::ImplSelf(impl_id) => {
                 let generics = crate::utils::generics(self.db.upcast(), impl_id.into());
                 let substs = generics.type_params_subst(self.db);
-                let ty = self.db.impl_self_ty(impl_id).subst(&substs);
+                let ty = self.db.impl_self_ty(impl_id).substitute(&Interner, &substs);
                 if let Some((AdtId::StructId(struct_id), substs)) = ty.as_adt() {
-                    let ty = self.db.value_ty(struct_id.into()).subst(&substs);
+                    let ty = self.db.value_ty(struct_id.into()).substitute(&Interner, &substs);
                     return Some(ty);
                 } else {
                     // FIXME: diagnostic, invalid Self reference
@@ -243,7 +243,8 @@ impl<'a> InferenceContext<'a> {
                         let impl_substs = TyBuilder::subst_for_def(self.db, impl_id)
                             .fill(iter::repeat_with(|| self.table.new_type_var()))
                             .build();
-                        let impl_self_ty = self.db.impl_self_ty(impl_id).subst(&impl_substs);
+                        let impl_self_ty =
+                            self.db.impl_self_ty(impl_id).substitute(&Interner, &impl_substs);
                         self.unify(&impl_self_ty, &ty);
                         Some(impl_substs)
                     }
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index 8370f2e1c..c90a16720 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -108,19 +108,22 @@ impl<'a, 'b> Canonicalizer<'a, 'b> {
 }
 
 impl<T> Canonicalized<T> {
-    pub(super) fn decanonicalize_ty(&self, mut ty: Ty) -> Ty {
-        ty.walk_mut_binders(
+    pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty {
+        ty.fold_binders(
             &mut |ty, binders| {
-                if let &mut TyKind::BoundVar(bound) = ty.interned_mut() {
+                if let TyKind::BoundVar(bound) = ty.kind(&Interner) {
                     if bound.debruijn >= binders {
                         let (v, k) = self.free_vars[bound.index];
-                        *ty = TyKind::InferenceVar(v, k).intern(&Interner);
+                        TyKind::InferenceVar(v, k).intern(&Interner)
+                    } else {
+                        ty
                     }
+                } else {
+                    ty
                 }
             },
             DebruijnIndex::INNERMOST,
-        );
-        ty
+        )
     }
 
     pub(super) fn apply_solution(
@@ -149,7 +152,7 @@ impl<T> Canonicalized<T> {
             // eagerly replace projections in the type; we may be getting types
             // e.g. from where clauses where this hasn't happened yet
             let ty = ctx.normalize_associated_types_in(
-                ty.assert_ty_ref(&Interner).clone().subst_bound_vars(&new_vars),
+                new_vars.apply(ty.assert_ty_ref(&Interner).clone(), &Interner),
             );
             ctx.table.unify(&TyKind::InferenceVar(v, k).intern(&Interner), &ty);
         }
@@ -170,8 +173,8 @@ pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> {
             // fallback to Unknown in the end (kind of hacky, as below)
             .map(|_| table.new_type_var()),
     );
-    let ty1_with_vars = tys.value.0.clone().subst_bound_vars(&vars);
-    let ty2_with_vars = tys.value.1.clone().subst_bound_vars(&vars);
+    let ty1_with_vars = vars.apply(tys.value.0.clone(), &Interner);
+    let ty2_with_vars = vars.apply(tys.value.1.clone(), &Interner);
     if !table.unify(&ty1_with_vars, &ty2_with_vars) {
         return None;
     }
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index adfdcaa37..daf379ef8 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -66,6 +66,8 @@ pub type ClosureId = chalk_ir::ClosureId<Interner>;
 pub type OpaqueTyId = chalk_ir::OpaqueTyId<Interner>;
 pub type PlaceholderIndex = chalk_ir::PlaceholderIndex;
 
+pub type VariableKind = chalk_ir::VariableKind<Interner>;
+pub type VariableKinds = chalk_ir::VariableKinds<Interner>;
 pub type CanonicalVarKinds = chalk_ir::CanonicalVarKinds<Interner>;
 
 pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
@@ -118,52 +120,34 @@ pub fn param_idx(db: &dyn HirDatabase, id: TypeParamId) -> Option<usize> {
 }
 
 impl<T> Binders<T> {
-    pub fn new(num_binders: usize, value: T) -> Self {
-        Self { num_binders, value }
-    }
-
     pub fn wrap_empty(value: T) -> Self
     where
         T: TypeWalk,
     {
-        Self { num_binders: 0, value: value.shift_bound_vars(DebruijnIndex::ONE) }
-    }
-
-    pub fn as_ref(&self) -> Binders<&T> {
-        Binders { num_binders: self.num_binders, value: &self.value }
-    }
-
-    pub fn map<U>(self, f: impl FnOnce(T) -> U) -> Binders<U> {
-        Binders { num_binders: self.num_binders, value: f(self.value) }
-    }
-
-    pub fn filter_map<U>(self, f: impl FnOnce(T) -> Option<U>) -> Option<Binders<U>> {
-        Some(Binders { num_binders: self.num_binders, value: f(self.value)? })
-    }
-
-    pub fn skip_binders(&self) -> &T {
-        &self.value
-    }
-
-    pub fn into_value_and_skipped_binders(self) -> (T, usize) {
-        (self.value, self.num_binders)
-    }
-}
-
-impl<T: Clone> Binders<&T> {
-    pub fn cloned(&self) -> Binders<T> {
-        Binders { num_binders: self.num_binders, value: self.value.clone() }
+        Binders::empty(&Interner, value.shifted_in_from(DebruijnIndex::ONE))
     }
 }
 
 impl<T: TypeWalk> Binders<T> {
     /// Substitutes all variables.
-    pub fn subst(self, subst: &Substitution) -> T {
-        assert_eq!(subst.len(&Interner), self.num_binders);
-        self.value.subst_bound_vars(subst)
+    pub fn substitute(self, interner: &Interner, subst: &Substitution) -> T {
+        let (value, binders) = self.into_value_and_skipped_binders();
+        assert_eq!(subst.len(interner), binders.len(interner));
+        value.subst_bound_vars(subst)
     }
 }
 
+pub fn make_only_type_binders<T>(num_vars: usize, value: T) -> Binders<T> {
+    Binders::new(
+        VariableKinds::from_iter(
+            &Interner,
+            std::iter::repeat(chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General))
+                .take(num_vars),
+        ),
+        value,
+    )
+}
+
 impl TraitRef {
     pub fn self_type_parameter(&self, interner: &Interner) -> &Ty {
         &self.substitution.at(interner, 0).assert_ty_ref(interner)
@@ -225,7 +209,8 @@ impl CallableSig {
             params_and_return: fn_ptr
                 .substs
                 .clone()
-                .shift_bound_vars_out(DebruijnIndex::ONE)
+                .shifted_out_to(DebruijnIndex::ONE)
+                .expect("unexpected lifetime vars in fn ptr")
                 .interned()
                 .iter()
                 .map(|arg| arg.assert_ty_ref(&Interner).clone())
@@ -334,12 +319,12 @@ impl Ty {
     /// If this is a `dyn Trait` type, this returns the `Trait` part.
     fn dyn_trait_ref(&self) -> Option<&TraitRef> {
         match self.kind(&Interner) {
-            TyKind::Dyn(dyn_ty) => {
-                dyn_ty.bounds.value.interned().get(0).and_then(|b| match b.skip_binders() {
+            TyKind::Dyn(dyn_ty) => dyn_ty.bounds.skip_binders().interned().get(0).and_then(|b| {
+                match b.skip_binders() {
                     WhereClause::Implemented(trait_ref) => Some(trait_ref),
                     _ => None,
-                })
-            }
+                }
+            }),
             _ => None,
         }
     }
@@ -378,7 +363,7 @@ impl Ty {
             TyKind::FnDef(def, parameters) => {
                 let callable_def = db.lookup_intern_callable_def((*def).into());
                 let sig = db.callable_item_signature(callable_def);
-                Some(sig.subst(&parameters))
+                Some(sig.substitute(&Interner, &parameters))
             }
             TyKind::Closure(.., substs) => {
                 let sig_param = substs.at(&Interner, 0).assert_ty_ref(&Interner);
@@ -429,8 +414,8 @@ impl Ty {
                             // This is only used by type walking.
                             // Parameters will be walked outside, and projection predicate is not used.
                             // So just provide the Future trait.
-                            let impl_bound = Binders::new(
-                                0,
+                            let impl_bound = Binders::empty(
+                                &Interner,
                                 WhereClause::Implemented(TraitRef {
                                     trait_id: to_chalk_trait_id(future_trait),
                                     substitution: Substitution::empty(&Interner),
@@ -452,14 +437,14 @@ impl Ty {
                             let data = (*it)
                                 .as_ref()
                                 .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
-                            data.subst(&opaque_ty.substitution)
+                            data.substitute(&Interner, &opaque_ty.substitution)
                         })
                     }
                     // It always has an parameter for Future::Output type.
                     ImplTraitId::AsyncBlockTypeImplTrait(..) => unreachable!(),
                 };
 
-                predicates.map(|it| it.value)
+                predicates.map(|it| it.into_value_and_skipped_binders().0)
             }
             TyKind::Placeholder(idx) => {
                 let id = from_placeholder_idx(db, *idx);
@@ -471,7 +456,7 @@ impl Ty {
                         let predicates = db
                             .generic_predicates(id.parent)
                             .into_iter()
-                            .map(|pred| pred.clone().subst(&substs))
+                            .map(|pred| pred.clone().substitute(&Interner, &substs))
                             .filter(|wc| match &wc.skip_binders() {
                                 WhereClause::Implemented(tr) => {
                                     tr.self_type_parameter(&Interner) == self
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index e9e4e69ad..48c26f471 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -31,7 +31,7 @@ use crate::{
     traits::chalk::{Interner, ToChalk},
     utils::{
         all_super_trait_refs, associated_type_by_name_including_super_traits, generics,
-        variant_data,
+        variant_data, Generics,
     },
     AliasEq, AliasTy, Binders, BoundVar, CallableSig, DebruijnIndex, DynTy, FnPointer, FnSig,
     ImplTraitId, OpaqueTy, PolyFnSig, ProjectionTy, QuantifiedWhereClause, QuantifiedWhereClauses,
@@ -196,7 +196,7 @@ impl<'a> TyLoweringContext<'a> {
                         bounds.iter().flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false)),
                     )
                 });
-                let bounds = Binders::new(1, bounds);
+                let bounds = crate::make_only_type_binders(1, bounds);
                 TyKind::Dyn(DynTy { bounds }).intern(&Interner)
             }
             TypeRef::ImplTrait(bounds) => {
@@ -209,9 +209,9 @@ impl<'a> TyLoweringContext<'a> {
                         // this dance is to make sure the data is in the right
                         // place even if we encounter more opaque types while
                         // lowering the bounds
-                        self.opaque_type_data
-                            .borrow_mut()
-                            .push(ReturnTypeImplTrait { bounds: Binders::new(1, Vec::new()) });
+                        self.opaque_type_data.borrow_mut().push(ReturnTypeImplTrait {
+                            bounds: crate::make_only_type_binders(1, Vec::new()),
+                        });
                         // We don't want to lower the bounds inside the binders
                         // we're currently in, because they don't end up inside
                         // those binders. E.g. when we have `impl Trait<impl
@@ -380,7 +380,7 @@ impl<'a> TyLoweringContext<'a> {
                     TyKind::Error.intern(&Interner)
                 } else {
                     let dyn_ty = DynTy {
-                        bounds: Binders::new(
+                        bounds: crate::make_only_type_binders(
                             1,
                             QuantifiedWhereClauses::from_iter(
                                 &Interner,
@@ -414,7 +414,7 @@ impl<'a> TyLoweringContext<'a> {
                     TypeParamLoweringMode::Placeholder => generics.type_params_subst(self.db),
                     TypeParamLoweringMode::Variable => generics.bound_vars_subst(self.in_binders),
                 };
-                self.db.impl_self_ty(impl_id).subst(&substs)
+                self.db.impl_self_ty(impl_id).substitute(&Interner, &substs)
             }
             TypeNs::AdtSelfType(adt) => {
                 let generics = generics(self.db.upcast(), adt.into());
@@ -422,7 +422,7 @@ impl<'a> TyLoweringContext<'a> {
                     TypeParamLoweringMode::Placeholder => generics.type_params_subst(self.db),
                     TypeParamLoweringMode::Variable => generics.bound_vars_subst(self.in_binders),
                 };
-                self.db.ty(adt.into()).subst(&substs)
+                self.db.ty(adt.into()).substitute(&Interner, &substs)
             }
 
             TypeNs::AdtId(it) => self.lower_path_inner(resolved_segment, it.into(), infer_args),
@@ -477,13 +477,13 @@ impl<'a> TyLoweringContext<'a> {
                                     ),
                                 );
                                 let s = generics.type_params_subst(self.db);
-                                t.substitution.clone().subst_bound_vars(&s)
+                                s.apply(t.substitution.clone(), &Interner)
                             }
                             TypeParamLoweringMode::Variable => t.substitution.clone(),
                         };
                         // We need to shift in the bound vars, since
                         // associated_type_shorthand_candidates does not do that
-                        let substs = substs.shift_bound_vars(self.in_binders);
+                        let substs = substs.shifted_in_from(self.in_binders);
                         // FIXME handle type parameters on the segment
                         return Some(
                             TyKind::Alias(AliasTy::Projection(ProjectionTy {
@@ -516,7 +516,7 @@ impl<'a> TyLoweringContext<'a> {
             TyDefId::TypeAliasId(it) => Some(it.into()),
         };
         let substs = self.substs_from_path_segment(segment, generic_def, infer_args, None);
-        self.db.ty(typeable).subst(&substs)
+        self.db.ty(typeable).substitute(&Interner, &substs)
     }
 
     /// Collect generic arguments from a path into a `Substs`. See also
@@ -620,7 +620,7 @@ impl<'a> TyLoweringContext<'a> {
                 for default_ty in defaults.iter().skip(substs.len()) {
                     // each default can depend on the previous parameters
                     let substs_so_far = Substitution::from_iter(&Interner, substs.clone());
-                    substs.push(default_ty.clone().subst(&substs_so_far));
+                    substs.push(default_ty.clone().substitute(&Interner, &substs_so_far));
                 }
             }
         }
@@ -787,7 +787,7 @@ impl<'a> TyLoweringContext<'a> {
         let predicates = self.with_shifted_in(DebruijnIndex::ONE, |ctx| {
             bounds.iter().flat_map(|b| ctx.lower_type_bound(b, self_ty.clone(), false)).collect()
         });
-        ReturnTypeImplTrait { bounds: Binders::new(1, predicates) }
+        ReturnTypeImplTrait { bounds: crate::make_only_type_binders(1, predicates) }
     }
 }
 
@@ -831,17 +831,20 @@ pub fn associated_type_shorthand_candidates<R>(
     };
 
     match res {
-        // FIXME: how to correctly handle higher-ranked bounds here?
-        TypeNs::SelfType(impl_id) => {
-            search(db.impl_trait(impl_id)?.value.shift_bound_vars_out(DebruijnIndex::ONE))
-        }
+        TypeNs::SelfType(impl_id) => search(
+            // we're _in_ the impl -- the binders get added back later. Correct,
+            // but it would be nice to make this more explicit
+            db.impl_trait(impl_id)?.into_value_and_skipped_binders().0,
+        ),
         TypeNs::GenericParam(param_id) => {
             let predicates = db.generic_predicates_for_param(param_id);
-            let res = predicates.iter().find_map(|pred| match &pred.value.value {
+            let res = predicates.iter().find_map(|pred| match pred.skip_binders().skip_binders() {
                 // FIXME: how to correctly handle higher-ranked bounds here?
-                WhereClause::Implemented(tr) => {
-                    search(tr.clone().shift_bound_vars_out(DebruijnIndex::ONE))
-                }
+                WhereClause::Implemented(tr) => search(
+                    tr.clone()
+                        .shifted_out_to(DebruijnIndex::ONE)
+                        .expect("FIXME unexpected higher-ranked trait bound"),
+                ),
                 _ => None,
             });
             if let res @ Some(_) = res {
@@ -881,7 +884,7 @@ pub(crate) fn field_types_query(
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
     for (field_id, field_data) in var_data.fields().iter() {
-        res.insert(field_id, Binders::new(generics.len(), ctx.lower_ty(&field_data.type_ref)))
+        res.insert(field_id, make_binders(&generics, ctx.lower_ty(&field_data.type_ref)))
     }
     Arc::new(res)
 }
@@ -915,9 +918,7 @@ pub(crate) fn generic_predicates_for_param_query(
             },
             WherePredicate::Lifetime { .. } => false,
         })
-        .flat_map(|pred| {
-            ctx.lower_where_predicate(pred, true).map(|p| Binders::new(generics.len(), p))
-        })
+        .flat_map(|pred| ctx.lower_where_predicate(pred, true).map(|p| make_binders(&generics, p)))
         .collect()
 }
 
@@ -988,9 +989,7 @@ pub(crate) fn generic_predicates_query(
     let generics = generics(db.upcast(), def);
     resolver
         .where_predicates_in_scope()
-        .flat_map(|pred| {
-            ctx.lower_where_predicate(pred, false).map(|p| Binders::new(generics.len(), p))
-        })
+        .flat_map(|pred| ctx.lower_where_predicate(pred, false).map(|p| make_binders(&generics, p)))
         .collect()
 }
 
@@ -1012,22 +1011,24 @@ pub(crate) fn generic_defaults_query(
                 p.default.as_ref().map_or(TyKind::Error.intern(&Interner), |t| ctx.lower_ty(t));
 
             // Each default can only refer to previous parameters.
-            ty.walk_mut_binders(
-                &mut |ty, binders| match ty.interned_mut() {
+            ty = ty.fold_binders(
+                &mut |ty, binders| match ty.kind(&Interner) {
                     TyKind::BoundVar(BoundVar { debruijn, index }) if *debruijn == binders => {
                         if *index >= idx {
                             // type variable default referring to parameter coming
                             // after it. This is forbidden (FIXME: report
                             // diagnostic)
-                            *ty = TyKind::Error.intern(&Interner);
+                            TyKind::Error.intern(&Interner)
+                        } else {
+                            ty
                         }
                     }
-                    _ => {}
+                    _ => ty,
                 },
                 DebruijnIndex::INNERMOST,
             );
 
-            Binders::new(idx, ty)
+            crate::make_only_type_binders(idx, ty)
         })
         .collect();
 
@@ -1040,14 +1041,13 @@ fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
     let ctx_params = TyLoweringContext::new(db, &resolver)
         .with_impl_trait_mode(ImplTraitLoweringMode::Variable)
         .with_type_param_mode(TypeParamLoweringMode::Variable);
-    let params = data.params.iter().map(|tr| (&ctx_params).lower_ty(tr)).collect::<Vec<_>>();
+    let params = data.params.iter().map(|tr| ctx_params.lower_ty(tr)).collect::<Vec<_>>();
     let ctx_ret = TyLoweringContext::new(db, &resolver)
         .with_impl_trait_mode(ImplTraitLoweringMode::Opaque)
         .with_type_param_mode(TypeParamLoweringMode::Variable);
-    let ret = (&ctx_ret).lower_ty(&data.ret_type);
+    let ret = ctx_ret.lower_ty(&data.ret_type);
     let generics = generics(db.upcast(), def.into());
-    let num_binders = generics.len();
-    Binders::new(num_binders, CallableSig::from_params_and_return(params, ret, data.is_varargs()))
+    make_binders(&generics, CallableSig::from_params_and_return(params, ret, data.is_varargs()))
 }
 
 /// Build the declared type of a function. This should not need to look at the
@@ -1055,8 +1055,8 @@ fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
 fn type_for_fn(db: &dyn HirDatabase, def: FunctionId) -> Binders<Ty> {
     let generics = generics(db.upcast(), def.into());
     let substs = generics.bound_vars_subst(DebruijnIndex::INNERMOST);
-    Binders::new(
-        substs.len(&Interner),
+    make_binders(
+        &generics,
         TyKind::FnDef(CallableDefId::FunctionId(def).to_chalk(db), substs).intern(&Interner),
     )
 }
@@ -1069,7 +1069,7 @@ fn type_for_const(db: &dyn HirDatabase, def: ConstId) -> Binders<Ty> {
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
 
-    Binders::new(generics.len(), ctx.lower_ty(&data.type_ref))
+    make_binders(&generics, ctx.lower_ty(&data.type_ref))
 }
 
 /// Build the declared type of a static.
@@ -1078,7 +1078,7 @@ fn type_for_static(db: &dyn HirDatabase, def: StaticId) -> Binders<Ty> {
     let resolver = def.resolver(db.upcast());
     let ctx = TyLoweringContext::new(db, &resolver);
 
-    Binders::new(0, ctx.lower_ty(&data.type_ref))
+    Binders::empty(&Interner, ctx.lower_ty(&data.type_ref))
 }
 
 fn fn_sig_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> PolyFnSig {
@@ -1088,8 +1088,8 @@ fn fn_sig_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> PolyFnS
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
     let params = fields.iter().map(|(_, field)| ctx.lower_ty(&field.type_ref)).collect::<Vec<_>>();
-    let ret = type_for_adt(db, def.into());
-    Binders::new(ret.num_binders, CallableSig::from_params_and_return(params, ret.value, false))
+    let (ret, binders) = type_for_adt(db, def.into()).into_value_and_skipped_binders();
+    Binders::new(binders, CallableSig::from_params_and_return(params, ret, false))
 }
 
 /// Build the type of a tuple struct constructor.
@@ -1100,8 +1100,8 @@ fn type_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> Binders<T
     }
     let generics = generics(db.upcast(), def.into());
     let substs = generics.bound_vars_subst(DebruijnIndex::INNERMOST);
-    Binders::new(
-        substs.len(&Interner),
+    make_binders(
+        &generics,
         TyKind::FnDef(CallableDefId::StructId(def).to_chalk(db), substs).intern(&Interner),
     )
 }
@@ -1114,8 +1114,8 @@ fn fn_sig_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId)
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
     let params = fields.iter().map(|(_, field)| ctx.lower_ty(&field.type_ref)).collect::<Vec<_>>();
-    let ret = type_for_adt(db, def.parent.into());
-    Binders::new(ret.num_binders, CallableSig::from_params_and_return(params, ret.value, false))
+    let (ret, binders) = type_for_adt(db, def.parent.into()).into_value_and_skipped_binders();
+    Binders::new(binders, CallableSig::from_params_and_return(params, ret, false))
 }
 
 /// Build the type of a tuple enum variant constructor.
@@ -1127,17 +1127,17 @@ fn type_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -
     }
     let generics = generics(db.upcast(), def.parent.into());
     let substs = generics.bound_vars_subst(DebruijnIndex::INNERMOST);
-    Binders::new(
-        substs.len(&Interner),
+    make_binders(
+        &generics,
         TyKind::FnDef(CallableDefId::EnumVariantId(def).to_chalk(db), substs).intern(&Interner),
     )
 }
 
 fn type_for_adt(db: &dyn HirDatabase, adt: AdtId) -> Binders<Ty> {
+    let generics = generics(db.upcast(), adt.into());
     let b = TyBuilder::adt(db, adt);
-    let num_binders = b.remaining();
     let ty = b.fill_with_bound_vars(DebruijnIndex::INNERMOST, 0).build();
-    Binders::new(num_binders, ty)
+    make_binders(&generics, ty)
 }
 
 fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders<Ty> {
@@ -1146,11 +1146,11 @@ fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders<Ty> {
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
     if db.type_alias_data(t).is_extern {
-        Binders::new(0, TyKind::Foreign(crate::to_foreign_def_id(t)).intern(&Interner))
+        Binders::empty(&Interner, TyKind::Foreign(crate::to_foreign_def_id(t)).intern(&Interner))
     } else {
         let type_ref = &db.type_alias_data(t).type_ref;
         let inner = ctx.lower_ty(type_ref.as_deref().unwrap_or(&TypeRef::Error));
-        Binders::new(generics.len(), inner)
+        make_binders(&generics, inner)
     }
 }
 
@@ -1209,19 +1209,21 @@ impl_from!(FunctionId, StructId, UnionId, EnumVariantId, ConstId, StaticId for V
 /// namespace.
 pub(crate) fn ty_query(db: &dyn HirDatabase, def: TyDefId) -> Binders<Ty> {
     match def {
-        TyDefId::BuiltinType(it) => Binders::new(0, TyBuilder::builtin(it)),
+        TyDefId::BuiltinType(it) => Binders::empty(&Interner, TyBuilder::builtin(it)),
         TyDefId::AdtId(it) => type_for_adt(db, it),
         TyDefId::TypeAliasId(it) => type_for_type_alias(db, it),
     }
 }
 
 pub(crate) fn ty_recover(db: &dyn HirDatabase, _cycle: &[String], def: &TyDefId) -> Binders<Ty> {
-    let num_binders = match *def {
-        TyDefId::BuiltinType(_) => 0,
-        TyDefId::AdtId(it) => generics(db.upcast(), it.into()).len(),
-        TyDefId::TypeAliasId(it) => generics(db.upcast(), it.into()).len(),
+    let generics = match *def {
+        TyDefId::BuiltinType(_) => {
+            return Binders::empty(&Interner, TyKind::Error.intern(&Interner))
+        }
+        TyDefId::AdtId(it) => generics(db.upcast(), it.into()),
+        TyDefId::TypeAliasId(it) => generics(db.upcast(), it.into()),
     };
-    Binders::new(num_binders, TyKind::Error.intern(&Interner))
+    make_binders(&generics, TyKind::Error.intern(&Interner))
 }
 
 pub(crate) fn value_ty_query(db: &dyn HirDatabase, def: ValueTyDefId) -> Binders<Ty> {
@@ -1241,7 +1243,7 @@ pub(crate) fn impl_self_ty_query(db: &dyn HirDatabase, impl_id: ImplId) -> Binde
     let generics = generics(db.upcast(), impl_id.into());
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
-    Binders::new(generics.len(), ctx.lower_ty(&impl_data.self_ty))
+    make_binders(&generics, ctx.lower_ty(&impl_data.self_ty))
 }
 
 pub(crate) fn const_param_ty_query(db: &dyn HirDatabase, def: ConstParamId) -> Ty {
@@ -1259,7 +1261,7 @@ pub(crate) fn impl_self_ty_recover(
     impl_id: &ImplId,
 ) -> Binders<Ty> {
     let generics = generics(db.upcast(), (*impl_id).into());
-    Binders::new(generics.len(), TyKind::Error.intern(&Interner))
+    make_binders(&generics, TyKind::Error.intern(&Interner))
 }
 
 pub(crate) fn impl_trait_query(db: &dyn HirDatabase, impl_id: ImplId) -> Option<Binders<TraitRef>> {
@@ -1267,9 +1269,9 @@ pub(crate) fn impl_trait_query(db: &dyn HirDatabase, impl_id: ImplId) -> Option<
     let resolver = impl_id.resolver(db.upcast());
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
-    let self_ty = db.impl_self_ty(impl_id);
+    let (self_ty, binders) = db.impl_self_ty(impl_id).into_value_and_skipped_binders();
     let target_trait = impl_data.target_trait.as_ref()?;
-    Some(Binders::new(self_ty.num_binders, ctx.lower_trait_ref(target_trait, Some(self_ty.value))?))
+    Some(Binders::new(binders, ctx.lower_trait_ref(target_trait, Some(self_ty))?))
 }
 
 pub(crate) fn return_type_impl_traits(
@@ -1284,13 +1286,12 @@ pub(crate) fn return_type_impl_traits(
         .with_type_param_mode(TypeParamLoweringMode::Variable);
     let _ret = (&ctx_ret).lower_ty(&data.ret_type);
     let generics = generics(db.upcast(), def.into());
-    let num_binders = generics.len();
     let return_type_impl_traits =
         ReturnTypeImplTraits { impl_traits: ctx_ret.opaque_type_data.into_inner() };
     if return_type_impl_traits.impl_traits.is_empty() {
         None
     } else {
-        Some(Arc::new(Binders::new(num_binders, return_type_impl_traits)))
+        Some(Arc::new(make_binders(&generics, return_type_impl_traits)))
     }
 }
 
@@ -1300,3 +1301,7 @@ pub(crate) fn lower_to_chalk_mutability(m: hir_def::type_ref::Mutability) -> Mut
         hir_def::type_ref::Mutability::Mut => Mutability::Mut,
     }
 }
+
+fn make_binders<T>(generics: &Generics, value: T) -> Binders<T> {
+    crate::make_only_type_binders(generics.len(), value)
+}
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index 6ace970d1..19a1fa793 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -102,11 +102,11 @@ impl TraitImpls {
         for (_module_id, module_data) in crate_def_map.modules() {
             for impl_id in module_data.scope.impls() {
                 let target_trait = match db.impl_trait(impl_id) {
-                    Some(tr) => tr.value.hir_trait_id(),
+                    Some(tr) => tr.skip_binders().hir_trait_id(),
                     None => continue,
                 };
                 let self_ty = db.impl_self_ty(impl_id);
-                let self_ty_fp = TyFingerprint::for_impl(&self_ty.value);
+                let self_ty_fp = TyFingerprint::for_impl(self_ty.skip_binders());
                 impls
                     .map
                     .entry(target_trait)
@@ -201,7 +201,7 @@ impl InherentImpls {
                 }
 
                 let self_ty = db.impl_self_ty(impl_id);
-                if let Some(fp) = TyFingerprint::for_impl(&self_ty.value) {
+                if let Some(fp) = TyFingerprint::for_impl(self_ty.skip_binders()) {
                     map.entry(fp).or_default().push(impl_id);
                 }
             }
@@ -712,7 +712,7 @@ pub(crate) fn inherent_impl_substs(
     let vars = TyBuilder::subst_for_def(db, impl_id)
         .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.binders.len(&Interner))
         .build();
-    let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars);
+    let self_ty_with_vars = db.impl_self_ty(impl_id).substitute(&Interner, &vars);
     let mut kinds = self_ty.binders.interned().to_vec();
     kinds.extend(
         iter::repeat(chalk_ir::WithKind::new(
@@ -774,7 +774,7 @@ fn transform_receiver_ty(
         AssocContainerId::ModuleId(_) => unreachable!(),
     };
     let sig = db.callable_item_signature(function_id.into());
-    Some(sig.value.params()[0].clone().subst_bound_vars(&substs))
+    Some(sig.map(|s| s.params()[0].clone()).substitute(&Interner, &substs))
 }
 
 pub fn implements_trait(
diff --git a/crates/hir_ty/src/traits/chalk.rs b/crates/hir_ty/src/traits/chalk.rs
index b7388b98c..dff87ef70 100644
--- a/crates/hir_ty/src/traits/chalk.rs
+++ b/crates/hir_ty/src/traits/chalk.rs
@@ -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
@@ -535,7 +540,8 @@ 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());
@@ -605,18 +611,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 +638,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 (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 +655,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)
 }
diff --git a/crates/hir_ty/src/traits/chalk/mapping.rs b/crates/hir_ty/src/traits/chalk/mapping.rs
index 67e88ebf4..c3b148cab 100644
--- a/crates/hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/hir_ty/src/traits/chalk/mapping.rs
@@ -93,12 +93,13 @@ impl ToChalk for Ty {
             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),
+                    bounds: chalk_ir::Binders::new(binders, where_clauses),
                     lifetime: LifetimeData::Static.intern(&Interner),
                 };
                 chalk_ir::TyKind::Dyn(bounded_ty).intern(&Interner)
@@ -148,7 +149,7 @@ impl ToChalk for Ty {
                     .map(|c| from_chalk(db, c.clone()));
                 TyKind::Dyn(crate::DynTy {
                     bounds: crate::Binders::new(
-                        1,
+                        where_clauses.bounds.binders.clone(),
                         crate::QuantifiedWhereClauses::from_iter(&Interner, bounds),
                     ),
                 })
@@ -486,19 +487,13 @@ 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))
     }
 }
 
@@ -524,7 +519,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
 }
@@ -536,8 +531,9 @@ 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(&Interner) != &self_ty_shifted_in {
                 // we can only convert predicates back to type bounds if they
@@ -549,7 +545,7 @@ pub(super) fn generic_predicate_to_inline_bound(
                 .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(&Interner) != &self_ty_shifted_in {
@@ -566,7 +562,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,
     }
diff --git a/crates/hir_ty/src/types.rs b/crates/hir_ty/src/types.rs
index bac086318..46c705a76 100644
--- a/crates/hir_ty/src/types.rs
+++ b/crates/hir_ty/src/types.rs
@@ -12,7 +12,7 @@ use smallvec::SmallVec;
 
 use crate::{
     AssocTypeId, CanonicalVarKinds, ChalkTraitId, ClosureId, FnDefId, FnSig, ForeignDefId,
-    InferenceVar, Interner, OpaqueTyId, PlaceholderIndex,
+    InferenceVar, Interner, OpaqueTyId, PlaceholderIndex, TypeWalk, VariableKinds,
 };
 
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
@@ -286,7 +286,11 @@ impl Substitution {
         Substitution(elements.into_iter().casted(interner).collect())
     }
 
-    // We can hopefully add this to Chalk
+    pub fn apply<T: TypeWalk>(&self, value: T, _interner: &Interner) -> T {
+        value.subst_bound_vars(self)
+    }
+
+    // Temporary helper functions, to be removed
     pub fn intern(interned: SmallVec<[GenericArg; 2]>) -> Substitution {
         Substitution(interned)
     }
@@ -296,10 +300,65 @@ impl Substitution {
     }
 }
 
-#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
+#[derive(Clone, PartialEq, Eq, Hash)]
 pub struct Binders<T> {
-    pub num_binders: usize,
-    pub value: T,
+    /// The binders that quantify over the value.
+    pub binders: VariableKinds,
+    value: T,
+}
+
+impl<T> Binders<T> {
+    pub fn new(binders: VariableKinds, value: T) -> Self {
+        Self { binders, value }
+    }
+
+    pub fn empty(_interner: &Interner, value: T) -> Self {
+        crate::make_only_type_binders(0, value)
+    }
+
+    pub fn as_ref(&self) -> Binders<&T> {
+        Binders { binders: self.binders.clone(), value: &self.value }
+    }
+
+    pub fn map<U>(self, f: impl FnOnce(T) -> U) -> Binders<U> {
+        Binders { binders: self.binders, value: f(self.value) }
+    }
+
+    pub fn filter_map<U>(self, f: impl FnOnce(T) -> Option<U>) -> Option<Binders<U>> {
+        Some(Binders { binders: self.binders, value: f(self.value)? })
+    }
+
+    pub fn skip_binders(&self) -> &T {
+        &self.value
+    }
+
+    pub fn into_value_and_skipped_binders(self) -> (T, VariableKinds) {
+        (self.value, self.binders)
+    }
+
+    /// Returns the number of binders.
+    pub fn len(&self, interner: &Interner) -> usize {
+        self.binders.len(interner)
+    }
+
+    // Temporary helper function, to be removed
+    pub fn skip_binders_mut(&mut self) -> &mut T {
+        &mut self.value
+    }
+}
+
+impl<T: Clone> Binders<&T> {
+    pub fn cloned(&self) -> Binders<T> {
+        Binders::new(self.binders.clone(), self.value.clone())
+    }
+}
+
+impl<T: std::fmt::Debug> std::fmt::Debug for Binders<T> {
+    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
+        let Binders { ref binders, ref value } = *self;
+        write!(fmt, "for{:?} ", binders.inner_debug(&Interner))?;
+        std::fmt::Debug::fmt(value, fmt)
+    }
 }
 
 /// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
diff --git a/crates/hir_ty/src/utils.rs b/crates/hir_ty/src/utils.rs
index df0ea4368..d11708299 100644
--- a/crates/hir_ty/src/utils.rs
+++ b/crates/hir_ty/src/utils.rs
@@ -66,13 +66,15 @@ fn direct_super_trait_refs(db: &dyn HirDatabase, trait_ref: &TraitRef) -> Vec<Tr
         .filter_map(|pred| {
             pred.as_ref().filter_map(|pred| match pred.skip_binders() {
                 // FIXME: how to correctly handle higher-ranked bounds here?
-                WhereClause::Implemented(tr) => {
-                    Some(tr.clone().shift_bound_vars_out(DebruijnIndex::ONE))
-                }
+                WhereClause::Implemented(tr) => Some(
+                    tr.clone()
+                        .shifted_out_to(DebruijnIndex::ONE)
+                        .expect("FIXME unexpected higher-ranked trait bound"),
+                ),
                 _ => None,
             })
         })
-        .map(|pred| pred.subst(&trait_ref.substitution))
+        .map(|pred| pred.substitute(&Interner, &trait_ref.substitution))
         .collect()
 }
 
@@ -103,6 +105,8 @@ pub(super) fn all_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<Tra
 /// we have `Self: Trait<u32, i32>` and `Trait<T, U>: OtherTrait<U>` we'll get
 /// `Self: OtherTrait<i32>`.
 pub(super) fn all_super_trait_refs(db: &dyn HirDatabase, trait_ref: TraitRef) -> Vec<TraitRef> {
+    // FIXME: replace by Chalk's `super_traits`, maybe make this a query
+
     // we need to take care a bit here to avoid infinite loops in case of cycles
     // (i.e. if we have `trait A: B; trait B: A;`)
     let mut result = vec![trait_ref];
diff --git a/crates/hir_ty/src/walk.rs b/crates/hir_ty/src/walk.rs
index 5dfd59746..b85e6ab4d 100644
--- a/crates/hir_ty/src/walk.rs
+++ b/crates/hir_ty/src/walk.rs
@@ -82,7 +82,7 @@ pub trait TypeWalk {
                         *ty = substs.interned()[bound.index]
                             .assert_ty_ref(&Interner)
                             .clone()
-                            .shift_bound_vars(binders);
+                            .shifted_in_from(binders);
                     }
                 }
             },
@@ -92,7 +92,7 @@ pub trait TypeWalk {
     }
 
     /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`.
-    fn shift_bound_vars(self, n: DebruijnIndex) -> Self
+    fn shifted_in_from(self, n: DebruijnIndex) -> Self
     where
         Self: Sized,
     {
@@ -108,20 +108,22 @@ pub trait TypeWalk {
     }
 
     /// Shifts debruijn indices of `TyKind::Bound` vars out (down) by `n`.
-    fn shift_bound_vars_out(self, n: DebruijnIndex) -> Self
+    fn shifted_out_to(self, n: DebruijnIndex) -> Option<Self>
     where
         Self: Sized + std::fmt::Debug,
     {
-        self.fold_binders(
-            &mut |ty, binders| match ty.kind(&Interner) {
-                TyKind::BoundVar(bound) if bound.debruijn >= binders => {
-                    TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone()))
-                        .intern(&Interner)
+        Some(self.fold_binders(
+            &mut |ty, binders| {
+                match ty.kind(&Interner) {
+                    TyKind::BoundVar(bound) if bound.debruijn >= binders => {
+                        TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone()))
+                            .intern(&Interner)
+                    }
+                    _ => ty,
                 }
-                _ => ty,
             },
             DebruijnIndex::INNERMOST,
-        )
+        ))
     }
 }
 
@@ -139,7 +141,7 @@ impl TypeWalk for Ty {
                 }
             }
             TyKind::Dyn(dyn_ty) => {
-                for p in dyn_ty.bounds.value.interned().iter() {
+                for p in dyn_ty.bounds.skip_binders().interned().iter() {
                     p.walk(f);
                 }
             }
@@ -167,7 +169,7 @@ impl TypeWalk for Ty {
                 p_ty.substitution.walk_mut_binders(f, binders);
             }
             TyKind::Dyn(dyn_ty) => {
-                for p in make_mut_slice(dyn_ty.bounds.value.interned_mut()) {
+                for p in make_mut_slice(dyn_ty.bounds.skip_binders_mut().interned_mut()) {
                     p.walk_mut_binders(f, binders.shifted_in());
                 }
             }
@@ -294,7 +296,7 @@ impl TypeWalk for Substitution {
 
 impl<T: TypeWalk> TypeWalk for Binders<T> {
     fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        self.value.walk(f);
+        self.skip_binders().walk(f);
     }
 
     fn walk_mut_binders(
@@ -302,7 +304,7 @@ impl<T: TypeWalk> TypeWalk for Binders<T> {
         f: &mut impl FnMut(&mut Ty, DebruijnIndex),
         binders: DebruijnIndex,
     ) {
-        self.value.walk_mut_binders(f, binders.shifted_in())
+        self.skip_binders_mut().walk_mut_binders(f, binders.shifted_in())
     }
 }