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.

3 files changed, 59 insertions, 13 deletions

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 };