Merge #3744

3744: Upgrade Chalk r=matklad a=flodiebold



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

10 files changed, 291 insertions, 133 deletions

diff --git a/crates/ra_hir_ty/src/autoderef.rs b/crates/ra_hir_ty/src/autoderef.rs
index 53e81e85d..d91c21e24 100644
--- a/crates/ra_hir_ty/src/autoderef.rs
+++ b/crates/ra_hir_ty/src/autoderef.rs
@@ -14,7 +14,7 @@ use crate::{
     db::HirDatabase,
     traits::{InEnvironment, Solution},
     utils::generics,
-    Canonical, Substs, Ty, TypeWalk,
+    BoundVar, Canonical, DebruijnIndex, Substs, Ty,
 };
 
 const AUTODEREF_RECURSION_LIMIT: usize = 10;
@@ -61,14 +61,13 @@ fn deref_by_trait(
         return None;
     }
 
-    // FIXME make the Canonical handling nicer
+    // FIXME make the Canonical / bound var handling nicer
 
-    let parameters = Substs::build_for_generics(&generic_params)
-        .push(ty.value.value.clone().shift_bound_vars(1))
-        .build();
+    let parameters =
+        Substs::build_for_generics(&generic_params).push(ty.value.value.clone()).build();
 
     let projection = super::traits::ProjectionPredicate {
-        ty: Ty::Bound(0),
+        ty: Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, ty.value.num_vars)),
         projection_ty: super::ProjectionTy { associated_ty: target, parameters },
     };
 
@@ -93,12 +92,16 @@ fn deref_by_trait(
             // we have `impl<T> Deref for Foo<T> { Target = T }`, that should be
             // the case.
             for i in 1..vars.0.num_vars {
-                if vars.0.value[i] != Ty::Bound((i - 1) as u32) {
+                if vars.0.value[i - 1] != Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, i - 1))
+                {
                     warn!("complex solution for derefing {:?}: {:?}, ignoring", ty.value, solution);
                     return None;
                 }
             }
-            Some(Canonical { value: vars.0.value[0].clone(), num_vars: vars.0.num_vars })
+            Some(Canonical {
+                value: vars.0.value[vars.0.value.len() - 1].clone(),
+                num_vars: vars.0.num_vars,
+            })
         }
         Solution::Ambig(_) => {
             info!("Ambiguous solution for derefing {:?}: {:?}", ty.value, solution);
diff --git a/crates/ra_hir_ty/src/display.rs b/crates/ra_hir_ty/src/display.rs
index 1665e25e4..0e9313aa1 100644
--- a/crates/ra_hir_ty/src/display.rs
+++ b/crates/ra_hir_ty/src/display.rs
@@ -311,7 +311,7 @@ impl HirDisplay for Ty {
                     }
                 }
             }
-            Ty::Bound(idx) => write!(f, "?{}", idx)?,
+            Ty::Bound(idx) => write!(f, "?{}.{}", idx.debruijn.depth(), idx.index)?,
             Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
                 match self {
                     Ty::Dyn(_) => write!(f, "dyn ")?,
diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs
index 0bf8fbd63..ac25f8a80 100644
--- a/crates/ra_hir_ty/src/infer/unify.rs
+++ b/crates/ra_hir_ty/src/infer/unify.rs
@@ -7,7 +7,9 @@ use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
 use test_utils::tested_by;
 
 use super::{InferenceContext, Obligation};
-use crate::{Canonical, InEnvironment, InferTy, Substs, Ty, TypeCtor, TypeWalk};
+use crate::{
+    BoundVar, Canonical, DebruijnIndex, InEnvironment, InferTy, Substs, Ty, TypeCtor, TypeWalk,
+};
 
 impl<'a> InferenceContext<'a> {
     pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b>
@@ -47,7 +49,7 @@ where
         })
     }
 
-    fn do_canonicalize<T: TypeWalk>(&mut self, t: T, binders: usize) -> T {
+    fn do_canonicalize<T: TypeWalk>(&mut self, t: T, binders: DebruijnIndex) -> T {
         t.fold_binders(
             &mut |ty, binders| match ty {
                 Ty::Infer(tv) => {
@@ -72,7 +74,7 @@ where
                             InferTy::MaybeNeverTypeVar(_) => InferTy::MaybeNeverTypeVar(root),
                         };
                         let position = self.add(free_var);
-                        Ty::Bound((position + binders) as u32)
+                        Ty::Bound(BoundVar::new(binders, position))
                     }
                 }
                 _ => ty,
@@ -89,7 +91,7 @@ where
     }
 
     pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> {
-        let result = self.do_canonicalize(ty, 0);
+        let result = self.do_canonicalize(ty, DebruijnIndex::INNERMOST);
         self.into_canonicalized(result)
     }
 
@@ -98,8 +100,12 @@ where
         obligation: InEnvironment<Obligation>,
     ) -> Canonicalized<InEnvironment<Obligation>> {
         let result = match obligation.value {
-            Obligation::Trait(tr) => Obligation::Trait(self.do_canonicalize(tr, 0)),
-            Obligation::Projection(pr) => Obligation::Projection(self.do_canonicalize(pr, 0)),
+            Obligation::Trait(tr) => {
+                Obligation::Trait(self.do_canonicalize(tr, DebruijnIndex::INNERMOST))
+            }
+            Obligation::Projection(pr) => {
+                Obligation::Projection(self.do_canonicalize(pr, DebruijnIndex::INNERMOST))
+            }
         };
         self.into_canonicalized(InEnvironment {
             value: result,
@@ -112,13 +118,13 @@ impl<T> Canonicalized<T> {
     pub fn decanonicalize_ty(&self, mut ty: Ty) -> Ty {
         ty.walk_mut_binders(
             &mut |ty, binders| {
-                if let &mut Ty::Bound(idx) = ty {
-                    if idx as usize >= binders && (idx as usize - binders) < self.free_vars.len() {
-                        *ty = Ty::Infer(self.free_vars[idx as usize - binders]);
+                if let &mut Ty::Bound(bound) = ty {
+                    if bound.debruijn >= binders {
+                        *ty = Ty::Infer(self.free_vars[bound.index]);
                     }
                 }
             },
-            0,
+            DebruijnIndex::INNERMOST,
         );
         ty
     }
@@ -150,7 +156,7 @@ pub fn unify(ty1: &Canonical<Ty>, ty2: &Canonical<Ty>) -> Option<Substs> {
     // (kind of hacky)
     for (i, var) in vars.iter().enumerate() {
         if &*table.resolve_ty_shallow(var) == var {
-            table.unify(var, &Ty::Bound(i as u32));
+            table.unify(var, &Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, i)));
         }
     }
     Some(
diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs
index 6c5469ecd..a9022dee7 100644
--- a/crates/ra_hir_ty/src/lib.rs
+++ b/crates/ra_hir_ty/src/lib.rs
@@ -64,6 +64,8 @@ pub use lower::{
 };
 pub use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment};
 
+pub use chalk_ir::{BoundVar, DebruijnIndex};
+
 /// A type constructor or type name: this might be something like the primitive
 /// type `bool`, a struct like `Vec`, or things like function pointers or
 /// tuples.
@@ -265,7 +267,11 @@ impl TypeWalk for ProjectionTy {
         self.parameters.walk(f);
     }
 
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
         self.parameters.walk_mut_binders(f, binders);
     }
 }
@@ -299,7 +305,7 @@ pub enum Ty {
     /// parameters get turned into variables; during trait resolution, inference
     /// variables get turned into bound variables and back; and in `Dyn` the
     /// `Self` type is represented with a bound variable as well.
-    Bound(u32),
+    Bound(BoundVar),
 
     /// A type variable used during type checking.
     Infer(InferTy),
@@ -337,7 +343,11 @@ impl TypeWalk for Substs {
         }
     }
 
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
         for t in make_mut_slice(&mut self.0) {
             t.walk_mut_binders(f, binders);
         }
@@ -381,7 +391,13 @@ impl Substs {
 
     /// Return Substs that replace each parameter by a bound variable.
     pub(crate) fn bound_vars(generic_params: &Generics) -> Substs {
-        Substs(generic_params.iter().enumerate().map(|(idx, _)| Ty::Bound(idx as u32)).collect())
+        Substs(
+            generic_params
+                .iter()
+                .enumerate()
+                .map(|(idx, _)| Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, idx)))
+                .collect(),
+        )
     }
 
     pub fn build_for_def(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> SubstsBuilder {
@@ -425,8 +441,8 @@ impl SubstsBuilder {
         self.param_count - self.vec.len()
     }
 
-    pub fn fill_with_bound_vars(self, starting_from: u32) -> Self {
-        self.fill((starting_from..).map(Ty::Bound))
+    pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self {
+        self.fill((starting_from..).map(|idx| Ty::Bound(BoundVar::new(debruijn, idx))))
     }
 
     pub fn fill_with_unknown(self) -> Self {
@@ -507,7 +523,11 @@ impl TypeWalk for TraitRef {
         self.substs.walk(f);
     }
 
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
         self.substs.walk_mut_binders(f, binders);
     }
 }
@@ -558,7 +578,11 @@ impl TypeWalk for GenericPredicate {
         }
     }
 
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
         match self {
             GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
             GenericPredicate::Projection(projection_pred) => {
@@ -616,7 +640,11 @@ impl TypeWalk for FnSig {
         }
     }
 
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
         for t in make_mut_slice(&mut self.params_and_return) {
             t.walk_mut_binders(f, binders);
         }
@@ -755,7 +783,7 @@ impl Ty {
 pub trait TypeWalk {
     fn walk(&self, f: &mut impl FnMut(&Ty));
     fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
-        self.walk_mut_binders(&mut |ty, _binders| f(ty), 0);
+        self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST);
     }
     /// Walk the type, counting entered binders.
     ///
@@ -767,9 +795,17 @@ pub trait TypeWalk {
     /// that. Currently, the only thing that introduces bound variables on our
     /// side are `Ty::Dyn` and `Ty::Opaque`, which each introduce a bound
     /// variable for the self type.
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize);
-
-    fn fold_binders(mut self, f: &mut impl FnMut(Ty, usize) -> Ty, binders: usize) -> Self
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    );
+
+    fn fold_binders(
+        mut self,
+        f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty,
+        binders: DebruijnIndex,
+    ) -> Self
     where
         Self: Sized,
     {
@@ -795,40 +831,43 @@ pub trait TypeWalk {
     }
 
     /// Substitutes `Ty::Bound` vars with the given substitution.
-    fn subst_bound_vars(mut self, substs: &Substs) -> Self
+    fn subst_bound_vars(self, substs: &Substs) -> Self
+    where
+        Self: Sized,
+    {
+        self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST)
+    }
+
+    /// Substitutes `Ty::Bound` vars with the given substitution.
+    fn subst_bound_vars_at_depth(mut self, substs: &Substs, depth: DebruijnIndex) -> Self
     where
         Self: Sized,
     {
         self.walk_mut_binders(
             &mut |ty, binders| {
-                if let &mut Ty::Bound(idx) = ty {
-                    if idx as usize >= binders && (idx as usize - binders) < substs.len() {
-                        *ty = substs.0[idx as usize - binders].clone();
-                    } else if idx as usize >= binders + substs.len() {
-                        // shift free binders
-                        *ty = Ty::Bound(idx - substs.len() as u32);
+                if let &mut Ty::Bound(bound) = ty {
+                    if bound.debruijn >= binders {
+                        *ty = substs.0[bound.index].clone();
                     }
                 }
             },
-            0,
+            depth,
         );
         self
     }
-
-    /// Shifts up `Ty::Bound` vars by `n`.
-    fn shift_bound_vars(self, n: i32) -> Self
+    // /// Shifts up debruijn indices of `Ty::Bound` vars by `n`.
+    fn shift_bound_vars(self, n: DebruijnIndex) -> Self
     where
         Self: Sized,
     {
         self.fold_binders(
             &mut |ty, binders| match ty {
-                Ty::Bound(idx) if idx as usize >= binders => {
-                    assert!(idx as i32 >= -n);
-                    Ty::Bound((idx as i32 + n) as u32)
+                Ty::Bound(bound) if bound.debruijn >= binders => {
+                    Ty::Bound(bound.shifted_in_from(n))
                 }
                 ty => ty,
             },
-            0,
+            DebruijnIndex::INNERMOST,
         )
     }
 }
@@ -856,7 +895,11 @@ impl TypeWalk for Ty {
         f(self);
     }
 
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
         match self {
             Ty::Apply(a_ty) => {
                 a_ty.parameters.walk_mut_binders(f, binders);
@@ -866,7 +909,7 @@ impl TypeWalk for Ty {
             }
             Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
                 for p in make_mut_slice(predicates) {
-                    p.walk_mut_binders(f, binders + 1);
+                    p.walk_mut_binders(f, binders.shifted_in());
                 }
             }
             Ty::Placeholder { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
diff --git a/crates/ra_hir_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs
index d7f250783..6c7bbc448 100644
--- a/crates/ra_hir_ty/src/lower.rs
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -29,8 +29,8 @@ use crate::{
         all_super_traits, associated_type_by_name_including_super_traits, generics, make_mut_slice,
         variant_data,
     },
-    Binders, FnSig, GenericPredicate, PolyFnSig, ProjectionPredicate, ProjectionTy, Substs,
-    TraitEnvironment, TraitRef, Ty, TypeCtor,
+    Binders, BoundVar, DebruijnIndex, FnSig, GenericPredicate, PolyFnSig, ProjectionPredicate,
+    ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TypeCtor,
 };
 
 #[derive(Debug)]
@@ -131,7 +131,7 @@ impl Ty {
                 Ty::apply(TypeCtor::FnPtr { num_args: sig.len() as u16 - 1 }, sig)
             }
             TypeRef::DynTrait(bounds) => {
-                let self_ty = Ty::Bound(0);
+                let self_ty = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0));
                 let predicates = bounds
                     .iter()
                     .flat_map(|b| GenericPredicate::from_type_bound(ctx, b, self_ty.clone()))
@@ -141,7 +141,7 @@ impl Ty {
             TypeRef::ImplTrait(bounds) => {
                 match ctx.impl_trait_mode {
                     ImplTraitLoweringMode::Opaque => {
-                        let self_ty = Ty::Bound(0);
+                        let self_ty = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0));
                         let predicates = bounds
                             .iter()
                             .flat_map(|b| {
@@ -177,12 +177,10 @@ impl Ty {
                             } else {
                                 (0, 0, 0, 0)
                             };
-                        Ty::Bound(
-                            idx as u32
-                                + parent_params as u32
-                                + self_params as u32
-                                + list_params as u32,
-                        )
+                        Ty::Bound(BoundVar::new(
+                            DebruijnIndex::INNERMOST,
+                            idx as usize + parent_params + self_params + list_params,
+                        ))
                     }
                     ImplTraitLoweringMode::Disallowed => {
                         // FIXME: report error
@@ -249,7 +247,11 @@ impl Ty {
         let ty = match resolution {
             TypeNs::TraitId(trait_) => {
                 // if this is a bare dyn Trait, we'll directly put the required ^0 for the self type in there
-                let self_ty = if remaining_segments.len() == 0 { Some(Ty::Bound(0)) } else { None };
+                let self_ty = if remaining_segments.len() == 0 {
+                    Some(Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)))
+                } else {
+                    None
+                };
                 let trait_ref =
                     TraitRef::from_resolved_path(ctx, trait_, resolved_segment, self_ty);
                 let ty = if remaining_segments.len() == 1 {
@@ -289,7 +291,7 @@ impl Ty {
                     TypeParamLoweringMode::Placeholder => Ty::Placeholder(param_id),
                     TypeParamLoweringMode::Variable => {
                         let idx = generics.param_idx(param_id).expect("matching generics");
-                        Ty::Bound(idx)
+                        Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, idx))
                     }
                 }
             }
@@ -558,7 +560,7 @@ impl GenericPredicate {
                     TypeParamLoweringMode::Placeholder => Ty::Placeholder(param_id),
                     TypeParamLoweringMode::Variable => {
                         let idx = generics.param_idx(param_id).expect("matching generics");
-                        Ty::Bound(idx)
+                        Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, idx))
                     }
                 }
             }
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index 533c6ccfb..74a0bc7db 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -20,7 +20,8 @@ use crate::{
     db::HirDatabase,
     primitive::{FloatBitness, Uncertain},
     utils::all_super_traits,
-    ApplicationTy, Canonical, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk,
+    ApplicationTy, Canonical, DebruijnIndex, InEnvironment, TraitEnvironment, TraitRef, Ty,
+    TypeCtor, TypeWalk,
 };
 
 /// This is used as a key for indexing impls.
@@ -507,8 +508,9 @@ pub(crate) fn inherent_impl_substs(
 ) -> Option<Substs> {
     // we create a var for each type parameter of the impl; we need to keep in
     // mind here that `self_ty` might have vars of its own
-    let vars =
-        Substs::build_for_def(db, impl_id).fill_with_bound_vars(self_ty.num_vars as u32).build();
+    let vars = Substs::build_for_def(db, impl_id)
+        .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.num_vars)
+        .build();
     let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars);
     let self_ty_with_vars =
         Canonical { num_vars: vars.len() + self_ty.num_vars, value: self_ty_with_vars };
@@ -526,8 +528,8 @@ pub(crate) fn inherent_impl_substs(
 fn fallback_bound_vars(s: Substs, num_vars_to_keep: usize) -> Substs {
     s.fold_binders(
         &mut |ty, binders| {
-            if let Ty::Bound(idx) = &ty {
-                if *idx >= binders as u32 {
+            if let Ty::Bound(bound) = &ty {
+                if bound.index >= num_vars_to_keep && bound.debruijn >= binders {
                     Ty::Unknown
                 } else {
                     ty
@@ -536,7 +538,7 @@ fn fallback_bound_vars(s: Substs, num_vars_to_keep: usize) -> Substs {
                 ty
             }
         },
-        num_vars_to_keep,
+        DebruijnIndex::INNERMOST,
     )
 }
 
@@ -586,7 +588,7 @@ fn generic_implements_goal(
     let num_vars = self_ty.num_vars;
     let substs = super::Substs::build_for_def(db, trait_)
         .push(self_ty.value)
-        .fill_with_bound_vars(num_vars as u32)
+        .fill_with_bound_vars(DebruijnIndex::INNERMOST, num_vars)
         .build();
     let num_vars = substs.len() - 1 + self_ty.num_vars;
     let trait_ref = TraitRef { trait_, substs };
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs
index a1ca33c98..07854a062 100644
--- a/crates/ra_hir_ty/src/traits.rs
+++ b/crates/ra_hir_ty/src/traits.rs
@@ -7,7 +7,7 @@ use ra_db::{impl_intern_key, salsa, CrateId};
 use ra_prof::profile;
 use rustc_hash::FxHashSet;
 
-use crate::db::HirDatabase;
+use crate::{db::HirDatabase, DebruijnIndex};
 
 use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk};
 
@@ -128,7 +128,11 @@ impl TypeWalk for ProjectionPredicate {
         self.ty.walk(f);
     }
 
-    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+    fn walk_mut_binders(
+        &mut self,
+        f: &mut impl FnMut(&mut Ty, DebruijnIndex),
+        binders: DebruijnIndex,
+    ) {
         self.projection_ty.walk_mut_binders(f, binders);
         self.ty.walk_mut_binders(f, binders);
     }
@@ -144,7 +148,7 @@ pub(crate) fn trait_solve_query(
         Obligation::Trait(it) => db.trait_data(it.trait_).name.to_string(),
         Obligation::Projection(_) => "projection".to_string(),
     });
-    log::debug!("trait_solve_query({})", goal.value.value.display(db));
+    eprintln!("trait_solve_query({})", goal.value.value.display(db));
 
     if let Obligation::Projection(pred) = &goal.value.value {
         if let Ty::Bound(_) = &pred.projection_ty.parameters[0] {
@@ -153,7 +157,7 @@ pub(crate) fn trait_solve_query(
         }
     }
 
-    let canonical = goal.to_chalk(db).cast();
+    let canonical = goal.to_chalk(db).cast(&Interner);
 
     // We currently don't deal with universes (I think / hope they're not yet
     // relevant for our use cases?)
@@ -194,8 +198,8 @@ fn solution_from_chalk(
     let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution<Interner>>| {
         let value = subst
             .value
-            .into_iter()
-            .map(|p| match p.ty() {
+            .iter(&Interner)
+            .map(|p| match p.ty(&Interner) {
                 Some(ty) => from_chalk(db, ty.clone()),
                 None => unimplemented!(),
             })
diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs
index 73e3c5c78..ccab246bf 100644
--- a/crates/ra_hir_ty/src/traits/builtin.rs
+++ b/crates/ra_hir_ty/src/traits/builtin.rs
@@ -8,7 +8,8 @@ use super::{AssocTyValue, Impl, UnsizeToSuperTraitObjectData};
 use crate::{
     db::HirDatabase,
     utils::{all_super_traits, generics},
-    ApplicationTy, Binders, GenericPredicate, Substs, TraitRef, Ty, TypeCtor,
+    ApplicationTy, Binders, BoundVar, DebruijnIndex, GenericPredicate, Substs, TraitRef, Ty,
+    TypeCtor, TypeWalk,
 };
 
 pub(super) struct BuiltinImplData {
@@ -164,11 +165,15 @@ fn closure_fn_trait_impl_datum(
 
     let arg_ty = Ty::apply(
         TypeCtor::Tuple { cardinality: num_args },
-        Substs::builder(num_args as usize).fill_with_bound_vars(0).build(),
+        Substs::builder(num_args as usize)
+            .fill_with_bound_vars(DebruijnIndex::INNERMOST, 0)
+            .build(),
     );
     let sig_ty = Ty::apply(
         TypeCtor::FnPtr { num_args },
-        Substs::builder(num_args as usize + 1).fill_with_bound_vars(0).build(),
+        Substs::builder(num_args as usize + 1)
+            .fill_with_bound_vars(DebruijnIndex::INNERMOST, 0)
+            .build(),
     );
 
     let self_ty = Ty::apply_one(TypeCtor::Closure { def: data.def, expr: data.expr }, sig_ty);
@@ -203,7 +208,7 @@ fn closure_fn_trait_output_assoc_ty_value(
         }
     };
 
-    let output_ty = Ty::Bound(num_args.into());
+    let output_ty = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, num_args.into()));
 
     let fn_once_trait =
         get_fn_trait(db, krate, super::FnTrait::FnOnce).expect("assoc ty value should not exist");
@@ -241,7 +246,7 @@ fn array_unsize_impl_datum(db: &dyn HirDatabase, krate: CrateId) -> BuiltinImplD
         // the existence of the Unsize trait has been checked before
         .expect("Unsize trait missing");
 
-    let var = Ty::Bound(0);
+    let var = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0));
     let substs = Substs::builder(2)
         .push(Ty::apply_one(TypeCtor::Array, var.clone()))
         .push(Ty::apply_one(TypeCtor::Slice, var))
@@ -270,19 +275,18 @@ fn trait_object_unsize_impl_datum(
         // the existence of the Unsize trait has been checked before
         .expect("Unsize trait missing");
 
-    let self_ty = Ty::Bound(0);
+    let self_ty = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0));
 
     let target_substs = Substs::build_for_def(db, trait_)
-        .push(Ty::Bound(0))
-        // starting from ^2 because we want to start with ^1 outside of the
-        // `dyn`, which is ^2 inside
-        .fill_with_bound_vars(2)
+        .push(Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)))
+        .fill_with_bound_vars(DebruijnIndex::ONE, 1)
         .build();
     let num_vars = target_substs.len();
     let target_trait_ref = TraitRef { trait_, substs: target_substs };
     let target_bounds = vec![GenericPredicate::Implemented(target_trait_ref)];
 
-    let self_substs = Substs::build_for_def(db, trait_).fill_with_bound_vars(0).build();
+    let self_substs =
+        Substs::build_for_def(db, trait_).fill_with_bound_vars(DebruijnIndex::INNERMOST, 0).build();
     let self_trait_ref = TraitRef { trait_, substs: self_substs };
     let where_clauses = vec![GenericPredicate::Implemented(self_trait_ref)];
 
@@ -305,24 +309,26 @@ fn super_trait_object_unsize_impl_datum(
         // the existence of the Unsize trait has been checked before
         .expect("Unsize trait missing");
 
-    let self_substs = Substs::build_for_def(db, data.trait_).fill_with_bound_vars(0).build();
+    let self_substs = Substs::build_for_def(db, data.trait_)
+        .fill_with_bound_vars(DebruijnIndex::INNERMOST, 0)
+        .build();
+    let self_trait_ref = TraitRef { trait_: data.trait_, substs: self_substs.clone() };
 
     let num_vars = self_substs.len() - 1;
 
-    let self_trait_ref = TraitRef { trait_: data.trait_, substs: self_substs.clone() };
-    let self_bounds = vec![GenericPredicate::Implemented(self_trait_ref.clone())];
-
     // we need to go from our trait to the super trait, substituting type parameters
     let path = crate::utils::find_super_trait_path(db.upcast(), data.trait_, data.super_trait);
 
-    let mut current_trait_ref = self_trait_ref;
+    let mut current_trait_ref = self_trait_ref.clone();
     for t in path.into_iter().skip(1) {
         let bounds = db.generic_predicates(current_trait_ref.trait_.into());
         let super_trait_ref = bounds
             .iter()
             .find_map(|b| match &b.value {
                 GenericPredicate::Implemented(tr)
-                    if tr.trait_ == t && tr.substs[0] == Ty::Bound(0) =>
+                    if tr.trait_ == t
+                        && tr.substs[0]
+                            == Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)) =>
                 {
                     Some(Binders { value: tr, num_binders: b.num_binders })
                 }
@@ -332,7 +338,18 @@ fn super_trait_object_unsize_impl_datum(
         current_trait_ref = super_trait_ref.cloned().subst(&current_trait_ref.substs);
     }
 
-    let super_bounds = vec![GenericPredicate::Implemented(current_trait_ref)];
+    // We need to renumber the variables a bit now: from ^0.0, ^0.1, ^0.2, ...
+    // to ^0.0, ^1.0, ^1.1. The reason for this is that the first variable comes
+    // from the dyn Trait binder, while the other variables come from the impl.
+    let new_substs = Substs::builder(num_vars + 1)
+        .push(Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)))
+        .fill_with_bound_vars(DebruijnIndex::ONE, 0)
+        .build();
+
+    let self_bounds =
+        vec![GenericPredicate::Implemented(self_trait_ref.subst_bound_vars(&new_substs))];
+    let super_bounds =
+        vec![GenericPredicate::Implemented(current_trait_ref.subst_bound_vars(&new_substs))];
 
     let substs = Substs::builder(2)
         .push(Ty::Dyn(self_bounds.into()))
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index 943d5f125..53ce362ea 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -3,7 +3,10 @@ use std::{fmt, sync::Arc};
 
 use log::debug;
 
-use chalk_ir::{cast::Cast, Goal, GoalData, Parameter, PlaceholderIndex, TypeName, UniverseIndex};
+use chalk_ir::{
+    cast::Cast, fold::shift::Shift, Goal, GoalData, Parameter, PlaceholderIndex, TypeName,
+    UniverseIndex,
+};
 
 use hir_def::{AssocContainerId, AssocItemId, GenericDefId, HasModule, Lookup, TypeAliasId};
 use ra_db::{
@@ -59,53 +62,126 @@ impl chalk_ir::interner::Interner for Interner {
         None
     }
 
+    fn debug_ty(_ty: &chalk_ir::Ty<Self>, _fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
+        None
+    }
+
+    fn debug_lifetime(
+        _lifetime: &chalk_ir::Lifetime<Self>,
+        _fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        None
+    }
+
+    fn debug_parameter(
+        _parameter: &Parameter<Self>,
+        _fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        None
+    }
+
+    fn debug_goal(_goal: &Goal<Self>, _fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
+        None
+    }
+
+    fn debug_goals(
+        _goals: &chalk_ir::Goals<Self>,
+        _fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        None
+    }
+
+    fn debug_program_clause_implication(
+        _pci: &chalk_ir::ProgramClauseImplication<Self>,
+        _fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        None
+    }
+
+    fn debug_application_ty(
+        _application_ty: &chalk_ir::ApplicationTy<Self>,
+        _fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        None
+    }
+
+    fn debug_substitution(
+        _substitution: &chalk_ir::Substitution<Self>,
+        _fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        None
+    }
+
+    fn debug_separator_trait_ref(
+        _separator_trait_ref: &chalk_ir::SeparatorTraitRef<Self>,
+        _fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        None
+    }
+
     fn intern_ty(&self, ty: chalk_ir::TyData<Self>) -> Box<chalk_ir::TyData<Self>> {
         Box::new(ty)
     }
 
-    fn ty_data(ty: &Box<chalk_ir::TyData<Self>>) -> &chalk_ir::TyData<Self> {
+    fn ty_data<'a>(&self, ty: &'a Box<chalk_ir::TyData<Self>>) -> &'a chalk_ir::TyData<Self> {
         ty
     }
 
-    fn intern_lifetime(lifetime: chalk_ir::LifetimeData<Self>) -> chalk_ir::LifetimeData<Self> {
+    fn intern_lifetime(
+        &self,
+        lifetime: chalk_ir::LifetimeData<Self>,
+    ) -> chalk_ir::LifetimeData<Self> {
         lifetime
     }
 
-    fn lifetime_data(lifetime: &chalk_ir::LifetimeData<Self>) -> &chalk_ir::LifetimeData<Self> {
+    fn lifetime_data<'a>(
+        &self,
+        lifetime: &'a chalk_ir::LifetimeData<Self>,
+    ) -> &'a chalk_ir::LifetimeData<Self> {
         lifetime
     }
 
-    fn intern_parameter(parameter: chalk_ir::ParameterData<Self>) -> chalk_ir::ParameterData<Self> {
+    fn intern_parameter(
+        &self,
+        parameter: chalk_ir::ParameterData<Self>,
+    ) -> chalk_ir::ParameterData<Self> {
         parameter
     }
 
-    fn parameter_data(parameter: &chalk_ir::ParameterData<Self>) -> &chalk_ir::ParameterData<Self> {
+    fn parameter_data<'a>(
+        &self,
+        parameter: &'a chalk_ir::ParameterData<Self>,
+    ) -> &'a chalk_ir::ParameterData<Self> {
         parameter
     }
 
-    fn intern_goal(goal: GoalData<Self>) -> Arc<GoalData<Self>> {
+    fn intern_goal(&self, goal: GoalData<Self>) -> Arc<GoalData<Self>> {
         Arc::new(goal)
     }
 
-    fn intern_goals(data: impl IntoIterator<Item = Goal<Self>>) -> Self::InternedGoals {
+    fn intern_goals(&self, data: impl IntoIterator<Item = Goal<Self>>) -> Self::InternedGoals {
         data.into_iter().collect()
     }
 
-    fn goal_data(goal: &Arc<GoalData<Self>>) -> &GoalData<Self> {
+    fn goal_data<'a>(&self, goal: &'a Arc<GoalData<Self>>) -> &'a GoalData<Self> {
         goal
     }
 
-    fn goals_data(goals: &Vec<Goal<Interner>>) -> &[Goal<Interner>] {
+    fn goals_data<'a>(&self, goals: &'a Vec<Goal<Interner>>) -> &'a [Goal<Interner>] {
         goals
     }
 
     fn intern_substitution<E>(
+        &self,
         data: impl IntoIterator<Item = Result<Parameter<Self>, E>>,
     ) -> Result<Vec<Parameter<Self>>, E> {
         data.into_iter().collect()
     }
 
-    fn substitution_data(substitution: &Vec<Parameter<Self>>) -> &[Parameter<Self>] {
+    fn substitution_data<'a>(
+        &self,
+        substitution: &'a Vec<Parameter<Self>>,
+    ) -> &'a [Parameter<Self>] {
         substitution
     }
 }
@@ -145,12 +221,14 @@ impl ToChalk for Ty {
             Ty::Apply(apply_ty) => {
                 let name = apply_ty.ctor.to_chalk(db);
                 let substitution = apply_ty.parameters.to_chalk(db);
-                chalk_ir::ApplicationTy { name, substitution }.cast().intern(&Interner)
+                chalk_ir::ApplicationTy { name, substitution }.cast(&Interner).intern(&Interner)
             }
             Ty::Projection(proj_ty) => {
                 let associated_ty_id = proj_ty.associated_ty.to_chalk(db);
                 let substitution = proj_ty.parameters.to_chalk(db);
-                chalk_ir::AliasTy { associated_ty_id, substitution }.cast().intern(&Interner)
+                chalk_ir::AliasTy { associated_ty_id, substitution }
+                    .cast(&Interner)
+                    .intern(&Interner)
             }
             Ty::Placeholder(id) => {
                 let interned_id = db.intern_type_param_id(id);
@@ -160,7 +238,7 @@ impl ToChalk for Ty {
                 }
                 .to_ty::<Interner>(&Interner)
             }
-            Ty::Bound(idx) => chalk_ir::TyData::BoundVar(idx as usize).intern(&Interner),
+            Ty::Bound(idx) => chalk_ir::TyData::BoundVar(idx).intern(&Interner),
             Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
             Ty::Dyn(predicates) => {
                 let where_clauses = predicates
@@ -173,14 +251,14 @@ impl ToChalk for Ty {
                 chalk_ir::TyData::Dyn(bounded_ty).intern(&Interner)
             }
             Ty::Opaque(_) | Ty::Unknown => {
-                let substitution = chalk_ir::Substitution::empty();
+                let substitution = chalk_ir::Substitution::empty(&Interner);
                 let name = TypeName::Error;
-                chalk_ir::ApplicationTy { name, substitution }.cast().intern(&Interner)
+                chalk_ir::ApplicationTy { name, substitution }.cast(&Interner).intern(&Interner)
             }
         }
     }
     fn from_chalk(db: &dyn HirDatabase, chalk: chalk_ir::Ty<Interner>) -> Self {
-        match chalk.data().clone() {
+        match chalk.data(&Interner).clone() {
             chalk_ir::TyData::Apply(apply_ty) => match apply_ty.name {
                 TypeName::Error => Ty::Unknown,
                 _ => {
@@ -202,7 +280,7 @@ impl ToChalk for Ty {
                 Ty::Projection(ProjectionTy { associated_ty, parameters })
             }
             chalk_ir::TyData::Function(_) => unimplemented!(),
-            chalk_ir::TyData::BoundVar(idx) => Ty::Bound(idx as u32),
+            chalk_ir::TyData::BoundVar(idx) => Ty::Bound(idx),
             chalk_ir::TyData::InferenceVar(_iv) => Ty::Unknown,
             chalk_ir::TyData::Dyn(where_clauses) => {
                 assert_eq!(where_clauses.bounds.binders.len(), 1);
@@ -218,13 +296,13 @@ impl ToChalk for Substs {
     type Chalk = chalk_ir::Substitution<Interner>;
 
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Substitution<Interner> {
-        chalk_ir::Substitution::from(self.iter().map(|ty| ty.clone().to_chalk(db)))
+        chalk_ir::Substitution::from(&Interner, self.iter().map(|ty| ty.clone().to_chalk(db)))
     }
 
     fn from_chalk(db: &dyn HirDatabase, parameters: chalk_ir::Substitution<Interner>) -> Substs {
         let tys = parameters
-            .into_iter()
-            .map(|p| match p.ty() {
+            .iter(&Interner)
+            .map(|p| match p.ty(&Interner) {
                 Some(ty) => from_chalk(db, ty.clone()),
                 None => unimplemented!(),
             })
@@ -332,15 +410,15 @@ impl ToChalk for GenericPredicate {
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::QuantifiedWhereClause<Interner> {
         match self {
             GenericPredicate::Implemented(trait_ref) => {
-                make_binders(chalk_ir::WhereClause::Implemented(trait_ref.to_chalk(db)), 0)
+                let chalk_trait_ref = trait_ref.to_chalk(db);
+                let chalk_trait_ref = chalk_trait_ref.shifted_in(&Interner);
+                make_binders(chalk_ir::WhereClause::Implemented(chalk_trait_ref), 0)
+            }
+            GenericPredicate::Projection(projection_pred) => {
+                let ty = projection_pred.ty.to_chalk(db).shifted_in(&Interner);
+                let alias = projection_pred.projection_ty.to_chalk(db).shifted_in(&Interner);
+                make_binders(chalk_ir::WhereClause::AliasEq(chalk_ir::AliasEq { alias, ty }), 0)
             }
-            GenericPredicate::Projection(projection_pred) => make_binders(
-                chalk_ir::WhereClause::AliasEq(chalk_ir::AliasEq {
-                    alias: projection_pred.projection_ty.to_chalk(db),
-                    ty: projection_pred.ty.to_chalk(db),
-                }),
-                0,
-            ),
             GenericPredicate::Error => panic!("tried passing GenericPredicate::Error to Chalk"),
         }
     }
@@ -400,8 +478,8 @@ impl ToChalk for Obligation {
 
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::DomainGoal<Interner> {
         match self {
-            Obligation::Trait(tr) => tr.to_chalk(db).cast(),
-            Obligation::Projection(pr) => pr.to_chalk(db).cast(),
+            Obligation::Trait(tr) => tr.to_chalk(db).cast(&Interner),
+            Obligation::Projection(pr) => pr.to_chalk(db).cast(&Interner),
         }
     }
 
@@ -438,8 +516,8 @@ impl ToChalk for Arc<super::TraitEnvironment> {
                 continue;
             }
             let program_clause: chalk_ir::ProgramClause<Interner> =
-                pred.clone().to_chalk(db).cast();
-            clauses.push(program_clause.into_from_env_clause());
+                pred.clone().to_chalk(db).cast(&Interner);
+            clauses.push(program_clause.into_from_env_clause(&Interner));
         }
         chalk_ir::Environment::new().add_clauses(clauses)
     }
@@ -504,7 +582,8 @@ impl ToChalk for builtin::BuiltinImplAssocTyValueData {
     type Chalk = AssociatedTyValue;
 
     fn to_chalk(self, db: &dyn HirDatabase) -> AssociatedTyValue {
-        let value_bound = chalk_rust_ir::AssociatedTyValueBound { ty: self.value.to_chalk(db) };
+        let ty = self.value.to_chalk(db);
+        let value_bound = chalk_rust_ir::AssociatedTyValueBound { ty };
 
         chalk_rust_ir::AssociatedTyValue {
             associated_ty_id: self.assoc_ty_id.to_chalk(db),
@@ -578,9 +657,9 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
             .map(|impl_| impl_.to_chalk(self.db))
             .collect();
 
-        let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref().clone());
+        let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref(&Interner).clone());
         let arg: Option<Ty> =
-            parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref().clone()));
+            parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref(&Interner).clone()));
 
         builtin::get_builtin_impls(self.db, self.krate, &ty, &arg, trait_, |i| {
             result.push(i.to_chalk(self.db))
@@ -663,11 +742,13 @@ pub(crate) fn trait_datum_query(
     let associated_ty_ids =
         trait_data.associated_types().map(|type_alias| type_alias.to_chalk(db)).collect();
     let trait_datum_bound = chalk_rust_ir::TraitDatumBound { where_clauses };
+    let well_known = None; // FIXME set this (depending on lang items)
     let trait_datum = TraitDatum {
         id: trait_id,
         binders: make_binders(trait_datum_bound, bound_vars.len()),
         flags,
         associated_ty_ids,
+        well_known,
     };
     Arc::new(trait_datum)
 }
diff --git a/crates/ra_hir_ty/src/utils.rs b/crates/ra_hir_ty/src/utils.rs
index b40d4eb73..1e5022fa4 100644
--- a/crates/ra_hir_ty/src/utils.rs
+++ b/crates/ra_hir_ty/src/utils.rs
@@ -201,11 +201,11 @@ impl Generics {
         (parent, self_params, list_params, impl_trait_params)
     }
 
-    pub(crate) fn param_idx(&self, param: TypeParamId) -> Option<u32> {
+    pub(crate) fn param_idx(&self, param: TypeParamId) -> Option<usize> {
         Some(self.find_param(param)?.0)
     }
 
-    fn find_param(&self, param: TypeParamId) -> Option<(u32, &TypeParamData)> {
+    fn find_param(&self, param: TypeParamId) -> Option<(usize, &TypeParamData)> {
         if param.parent == self.def {
             let (idx, (_local_id, data)) = self
                 .params
@@ -215,7 +215,7 @@ impl Generics {
                 .find(|(_, (idx, _))| *idx == param.local_id)
                 .unwrap();
             let (_total, parent_len, _child) = self.len_split();
-            Some(((parent_len + idx) as u32, data))
+            Some((parent_len + idx, data))
         } else {
             self.parent_generics.as_ref().and_then(|g| g.find_param(param))
         }