Fix handling of the binders in dyn/impl Trait

We need to be more careful now when substituting bound variables (previously, we
didn't have anything that used bound variables except Chalk, so it was not a
problem).

This is obviously quite ad-hoc; Chalk has more infrastructure for handling this
in a principled way, which we maybe should adopt.

4 files changed, 116 insertions, 45 deletions

diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index ff6030ac4..a54135188 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -224,8 +224,8 @@ impl TypeWalk for ProjectionTy {
         self.parameters.walk(f);
     }
 
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
-        self.parameters.walk_mut(f);
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        self.parameters.walk_mut_binders(f, binders);
     }
 }
 
@@ -291,6 +291,20 @@ pub enum Ty {
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct Substs(Arc<[Ty]>);
 
+impl TypeWalk for Substs {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        for t in self.0.iter() {
+            t.walk(f);
+        }
+    }
+
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        for t in make_mut_slice(&mut self.0) {
+            t.walk_mut_binders(f, binders);
+        }
+    }
+}
+
 impl Substs {
     pub fn empty() -> Substs {
         Substs(Arc::new([]))
@@ -304,18 +318,6 @@ impl Substs {
         Substs(self.0[..std::cmp::min(self.0.len(), n)].into())
     }
 
-    pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        for t in self.0.iter() {
-            t.walk(f);
-        }
-    }
-
-    pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
-        for t in make_mut_slice(&mut self.0) {
-            t.walk_mut(f);
-        }
-    }
-
     pub fn as_single(&self) -> &Ty {
         if self.0.len() != 1 {
             panic!("expected substs of len 1, got {:?}", self);
@@ -440,8 +442,8 @@ impl TypeWalk for TraitRef {
         self.substs.walk(f);
     }
 
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
-        self.substs.walk_mut(f);
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        self.substs.walk_mut_binders(f, binders);
     }
 }
 
@@ -491,10 +493,12 @@ impl TypeWalk for GenericPredicate {
         }
     }
 
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
         match self {
-            GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut(f),
-            GenericPredicate::Projection(projection_pred) => projection_pred.walk_mut(f),
+            GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
+            GenericPredicate::Projection(projection_pred) => {
+                projection_pred.walk_mut_binders(f, binders)
+            }
             GenericPredicate::Error => {}
         }
     }
@@ -544,9 +548,9 @@ impl TypeWalk for FnSig {
         }
     }
 
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
         for t in make_mut_slice(&mut self.params_and_return) {
-            t.walk_mut(f);
+            t.walk_mut_binders(f, binders);
         }
     }
 }
@@ -671,7 +675,20 @@ impl Ty {
 /// types, similar to Chalk's `Fold` trait.
 pub trait TypeWalk {
     fn walk(&self, f: &mut impl FnMut(&Ty));
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty));
+    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+        self.walk_mut_binders(&mut |ty, _binders| f(ty), 0);
+    }
+    /// Walk the type, counting entered binders.
+    ///
+    /// `Ty::Bound` variables use DeBruijn indexing, which means that 0 refers
+    /// to the innermost binder, 1 to the next, etc.. So when we want to
+    /// substitute a certain bound variable, we can't just walk the whole type
+    /// and blindly replace each instance of a certain index; when we 'enter'
+    /// things that introduce new bound variables, we have to keep track of
+    /// 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(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
     where
@@ -700,14 +717,22 @@ pub trait TypeWalk {
     }
 
     /// Substitutes `Ty::Bound` vars (as opposed to type parameters).
-    fn subst_bound_vars(self, substs: &Substs) -> Self
+    fn subst_bound_vars(mut self, substs: &Substs) -> Self
     where
         Self: Sized,
     {
-        self.fold(&mut |ty| match ty {
-            Ty::Bound(idx) => substs.get(idx as usize).cloned().unwrap_or_else(|| Ty::Bound(idx)),
-            ty => ty,
-        })
+        self.walk_mut_binders(
+            &mut |ty, binders| match ty {
+                &mut Ty::Bound(idx) => {
+                    if idx as usize >= binders && (idx as usize - binders) < substs.len() {
+                        *ty = substs.0[idx as usize - binders].clone();
+                    }
+                }
+                _ => {}
+            },
+            0,
+        );
+        self
     }
 
     /// Shifts up `Ty::Bound` vars by `n`.
@@ -748,22 +773,22 @@ impl TypeWalk for Ty {
         f(self);
     }
 
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
         match self {
             Ty::Apply(a_ty) => {
-                a_ty.parameters.walk_mut(f);
+                a_ty.parameters.walk_mut_binders(f, binders);
             }
             Ty::Projection(p_ty) => {
-                p_ty.parameters.walk_mut(f);
+                p_ty.parameters.walk_mut_binders(f, binders);
             }
             Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
                 for p in make_mut_slice(predicates) {
-                    p.walk_mut(f);
+                    p.walk_mut_binders(f, binders + 1);
                 }
             }
             Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
         }
-        f(self);
+        f(self, binders);
     }
 }
 
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs
index ca33cc7f8..64d9394cf 100644
--- a/crates/ra_hir/src/ty/infer/unify.rs
+++ b/crates/ra_hir/src/ty/infer/unify.rs
@@ -134,17 +134,19 @@ where
 }
 
 impl<T> Canonicalized<T> {
-    pub fn decanonicalize_ty(&self, ty: Ty) -> Ty {
-        ty.fold(&mut |ty| match ty {
-            Ty::Bound(idx) => {
-                if (idx as usize) < self.free_vars.len() {
-                    Ty::Infer(self.free_vars[idx as usize])
-                } else {
-                    Ty::Bound(idx)
+    pub fn decanonicalize_ty(&self, mut ty: Ty) -> Ty {
+        ty.walk_mut_binders(
+            &mut |ty, binders| match ty {
+                &mut Ty::Bound(idx) => {
+                    if idx as usize >= binders && (idx as usize - binders) < self.free_vars.len() {
+                        *ty = Ty::Infer(self.free_vars[idx as usize - binders]);
+                    }
                 }
-            }
-            ty => ty,
-        })
+                _ => {}
+            },
+            0,
+        );
+        ty
     }
 
     pub fn apply_solution(
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 838cb4d23..ca1693679 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -4185,6 +4185,49 @@ fn test<T: Trait<Type = u32>>(x: T, y: impl Trait<Type = i64>) {
 }
 
 #[test]
+fn impl_trait_assoc_binding_projection_bug() {
+    let (db, pos) = TestDB::with_position(
+        r#"
+//- /main.rs crate:main deps:std
+pub trait Language {
+    type Kind;
+}
+pub enum RustLanguage {}
+impl Language for RustLanguage {
+    type Kind = SyntaxKind;
+}
+struct SyntaxNode<L> {}
+fn foo() -> impl Iterator<Item = SyntaxNode<RustLanguage>> {}
+
+trait Clone {
+    fn clone(&self) -> Self;
+}
+
+fn api_walkthrough() {
+    for node in foo() {
+        node.clone()<|>;
+    }
+}
+
+//- /std.rs crate:std
+#[prelude_import] use iter::*;
+mod iter {
+    trait IntoIterator {
+        type Item;
+    }
+    trait Iterator {
+        type Item;
+    }
+    impl<T: Iterator> IntoIterator for T {
+        type Item = <T as Iterator>::Item;
+    }
+}
+"#,
+    );
+    assert_eq!("{unknown}", type_at_pos(&db, pos));
+}
+
+#[test]
 fn projection_eq_within_chalk() {
     // std::env::set_var("CHALK_DEBUG", "1");
     assert_snapshot!(
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index 771525deb..99dbab99e 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -165,9 +165,9 @@ impl TypeWalk for ProjectionPredicate {
         self.ty.walk(f);
     }
 
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
-        self.projection_ty.walk_mut(f);
-        self.ty.walk_mut(f);
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        self.projection_ty.walk_mut_binders(f, binders);
+        self.ty.walk_mut_binders(f, binders);
     }
 }
 
@@ -188,6 +188,7 @@ pub(crate) fn trait_solve_query(
     }
 
     let canonical = goal.to_chalk(db).cast();
+
     // We currently don't deal with universes (I think / hope they're not yet
     // relevant for our use cases?)
     let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 };