6 files changed, 331 insertions, 32 deletions

diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs
index 959b1e212..89200255a 100644
--- a/crates/ra_hir_ty/src/infer/coerce.rs
+++ b/crates/ra_hir_ty/src/infer/coerce.rs
@@ -51,7 +51,7 @@ impl<'a> InferenceContext<'a> {
             // Trivial cases, this should go after `never` check to
             // avoid infer result type to be never
             _ => {
-                if self.table.unify_inner_trivial(&from_ty, &to_ty) {
+                if self.table.unify_inner_trivial(&from_ty, &to_ty, 0) {
                     return true;
                 }
             }
@@ -175,7 +175,7 @@ impl<'a> InferenceContext<'a> {
                     return self.table.unify_substs(st1, st2, 0);
                 }
                 _ => {
-                    if self.table.unify_inner_trivial(&derefed_ty, &to_ty) {
+                    if self.table.unify_inner_trivial(&derefed_ty, &to_ty, 0) {
                         return true;
                     }
                 }
diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs
index 5f6cea8d3..ab0bc8b70 100644
--- a/crates/ra_hir_ty/src/infer/unify.rs
+++ b/crates/ra_hir_ty/src/infer/unify.rs
@@ -8,7 +8,8 @@ use test_utils::tested_by;
 
 use super::{InferenceContext, Obligation};
 use crate::{
-    BoundVar, Canonical, DebruijnIndex, InEnvironment, InferTy, Substs, Ty, TypeCtor, TypeWalk,
+    BoundVar, Canonical, DebruijnIndex, GenericPredicate, InEnvironment, InferTy, Substs, Ty,
+    TypeCtor, TypeWalk,
 };
 
 impl<'a> InferenceContext<'a> {
@@ -226,16 +227,26 @@ impl InferenceTable {
             (Ty::Apply(a_ty1), Ty::Apply(a_ty2)) if a_ty1.ctor == a_ty2.ctor => {
                 self.unify_substs(&a_ty1.parameters, &a_ty2.parameters, depth + 1)
             }
-            _ => self.unify_inner_trivial(&ty1, &ty2),
+
+            _ => self.unify_inner_trivial(&ty1, &ty2, depth),
         }
     }
 
-    pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
+    pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
         match (ty1, ty2) {
             (Ty::Unknown, _) | (_, Ty::Unknown) => true,
 
             (Ty::Placeholder(p1), Ty::Placeholder(p2)) if *p1 == *p2 => true,
 
+            (Ty::Dyn(dyn1), Ty::Dyn(dyn2)) if dyn1.len() == dyn2.len() => {
+                for (pred1, pred2) in dyn1.iter().zip(dyn2.iter()) {
+                    if !self.unify_preds(pred1, pred2, depth + 1) {
+                        return false;
+                    }
+                }
+                true
+            }
+
             (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2)))
             | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2)))
             | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2)))
@@ -268,6 +279,31 @@ impl InferenceTable {
         }
     }
 
+    fn unify_preds(
+        &mut self,
+        pred1: &GenericPredicate,
+        pred2: &GenericPredicate,
+        depth: usize,
+    ) -> bool {
+        match (pred1, pred2) {
+            (GenericPredicate::Implemented(tr1), GenericPredicate::Implemented(tr2))
+                if tr1.trait_ == tr2.trait_ =>
+            {
+                self.unify_substs(&tr1.substs, &tr2.substs, depth + 1)
+            }
+            (GenericPredicate::Projection(proj1), GenericPredicate::Projection(proj2))
+                if proj1.projection_ty.associated_ty == proj2.projection_ty.associated_ty =>
+            {
+                self.unify_substs(
+                    &proj1.projection_ty.parameters,
+                    &proj2.projection_ty.parameters,
+                    depth + 1,
+                ) && self.unify_inner(&proj1.ty, &proj2.ty, depth + 1)
+            }
+            _ => false,
+        }
+    }
+
     /// If `ty` is a type variable with known type, returns that type;
     /// otherwise, return ty.
     pub fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs
index 2677f3af2..a4b8d6683 100644
--- a/crates/ra_hir_ty/src/lib.rs
+++ b/crates/ra_hir_ty/src/lib.rs
@@ -396,12 +396,12 @@ impl Substs {
     }
 
     /// Return Substs that replace each parameter by a bound variable.
-    pub(crate) fn bound_vars(generic_params: &Generics) -> Substs {
+    pub(crate) fn bound_vars(generic_params: &Generics, debruijn: DebruijnIndex) -> Substs {
         Substs(
             generic_params
                 .iter()
                 .enumerate()
-                .map(|(idx, _)| Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, idx)))
+                .map(|(idx, _)| Ty::Bound(BoundVar::new(debruijn, idx)))
                 .collect(),
         )
     }
diff --git a/crates/ra_hir_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs
index cc1ac8e3e..c2812e178 100644
--- a/crates/ra_hir_ty/src/lower.rs
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -39,6 +39,7 @@ use crate::{
 pub struct TyLoweringContext<'a> {
     pub db: &'a dyn HirDatabase,
     pub resolver: &'a Resolver,
+    in_binders: DebruijnIndex,
     /// Note: Conceptually, it's thinkable that we could be in a location where
     /// some type params should be represented as placeholders, and others
     /// should be converted to variables. I think in practice, this isn't
@@ -53,7 +54,27 @@ impl<'a> TyLoweringContext<'a> {
         let impl_trait_counter = std::cell::Cell::new(0);
         let impl_trait_mode = ImplTraitLoweringMode::Disallowed;
         let type_param_mode = TypeParamLoweringMode::Placeholder;
-        Self { db, resolver, impl_trait_mode, impl_trait_counter, type_param_mode }
+        let in_binders = DebruijnIndex::INNERMOST;
+        Self { db, resolver, in_binders, impl_trait_mode, impl_trait_counter, type_param_mode }
+    }
+
+    pub fn with_shifted_in<T>(
+        &self,
+        debruijn: DebruijnIndex,
+        f: impl FnOnce(&TyLoweringContext) -> T,
+    ) -> T {
+        let new_ctx = Self {
+            in_binders: self.in_binders.shifted_in_from(debruijn),
+            impl_trait_counter: std::cell::Cell::new(self.impl_trait_counter.get()),
+            ..*self
+        };
+        let result = f(&new_ctx);
+        self.impl_trait_counter.set(new_ctx.impl_trait_counter.get());
+        result
+    }
+
+    pub fn shifted_in(self, debruijn: DebruijnIndex) -> Self {
+        Self { in_binders: self.in_binders.shifted_in_from(debruijn), ..self }
     }
 
     pub fn with_impl_trait_mode(self, impl_trait_mode: ImplTraitLoweringMode) -> Self {
@@ -134,22 +155,26 @@ impl Ty {
             }
             TypeRef::DynTrait(bounds) => {
                 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()))
-                    .collect();
+                let predicates = ctx.with_shifted_in(DebruijnIndex::ONE, |ctx| {
+                    bounds
+                        .iter()
+                        .flat_map(|b| GenericPredicate::from_type_bound(ctx, b, self_ty.clone()))
+                        .collect()
+                });
                 Ty::Dyn(predicates)
             }
             TypeRef::ImplTrait(bounds) => {
                 match ctx.impl_trait_mode {
                     ImplTraitLoweringMode::Opaque => {
                         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())
-                            })
-                            .collect();
+                        let predicates = ctx.with_shifted_in(DebruijnIndex::ONE, |ctx| {
+                            bounds
+                                .iter()
+                                .flat_map(|b| {
+                                    GenericPredicate::from_type_bound(ctx, b, self_ty.clone())
+                                })
+                                .collect()
+                        });
                         Ty::Opaque(predicates)
                     }
                     ImplTraitLoweringMode::Param => {
@@ -180,7 +205,7 @@ impl Ty {
                                 (0, 0, 0, 0)
                             };
                         Ty::Bound(BoundVar::new(
-                            DebruijnIndex::INNERMOST,
+                            ctx.in_binders,
                             idx as usize + parent_params + self_params + list_params,
                         ))
                     }
@@ -293,7 +318,7 @@ impl Ty {
                     TypeParamLoweringMode::Placeholder => Ty::Placeholder(param_id),
                     TypeParamLoweringMode::Variable => {
                         let idx = generics.param_idx(param_id).expect("matching generics");
-                        Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, idx))
+                        Ty::Bound(BoundVar::new(ctx.in_binders, idx))
                     }
                 }
             }
@@ -303,7 +328,9 @@ impl Ty {
                     TypeParamLoweringMode::Placeholder => {
                         Substs::type_params_for_generics(&generics)
                     }
-                    TypeParamLoweringMode::Variable => Substs::bound_vars(&generics),
+                    TypeParamLoweringMode::Variable => {
+                        Substs::bound_vars(&generics, ctx.in_binders)
+                    }
                 };
                 ctx.db.impl_self_ty(impl_id).subst(&substs)
             }
@@ -313,7 +340,9 @@ impl Ty {
                     TypeParamLoweringMode::Placeholder => {
                         Substs::type_params_for_generics(&generics)
                     }
-                    TypeParamLoweringMode::Variable => Substs::bound_vars(&generics),
+                    TypeParamLoweringMode::Variable => {
+                        Substs::bound_vars(&generics, ctx.in_binders)
+                    }
                 };
                 ctx.db.ty(adt.into()).subst(&substs)
             }
@@ -797,7 +826,7 @@ fn fn_sig_for_fn(db: &dyn HirDatabase, def: FunctionId) -> PolyFnSig {
 /// function body.
 fn type_for_fn(db: &dyn HirDatabase, def: FunctionId) -> Binders<Ty> {
     let generics = generics(db.upcast(), def.into());
-    let substs = Substs::bound_vars(&generics);
+    let substs = Substs::bound_vars(&generics, DebruijnIndex::INNERMOST);
     Binders::new(substs.len(), Ty::apply(TypeCtor::FnDef(def.into()), substs))
 }
 
@@ -851,7 +880,7 @@ fn type_for_struct_constructor(db: &dyn HirDatabase, def: StructId) -> Binders<T
         return type_for_adt(db, def.into());
     }
     let generics = generics(db.upcast(), def.into());
-    let substs = Substs::bound_vars(&generics);
+    let substs = Substs::bound_vars(&generics, DebruijnIndex::INNERMOST);
     Binders::new(substs.len(), Ty::apply(TypeCtor::FnDef(def.into()), substs))
 }
 
@@ -876,13 +905,13 @@ fn type_for_enum_variant_constructor(db: &dyn HirDatabase, def: EnumVariantId) -
         return type_for_adt(db, def.parent.into());
     }
     let generics = generics(db.upcast(), def.parent.into());
-    let substs = Substs::bound_vars(&generics);
+    let substs = Substs::bound_vars(&generics, DebruijnIndex::INNERMOST);
     Binders::new(substs.len(), Ty::apply(TypeCtor::FnDef(def.into()), substs))
 }
 
 fn type_for_adt(db: &dyn HirDatabase, adt: AdtId) -> Binders<Ty> {
     let generics = generics(db.upcast(), adt.into());
-    let substs = Substs::bound_vars(&generics);
+    let substs = Substs::bound_vars(&generics, DebruijnIndex::INNERMOST);
     Binders::new(substs.len(), Ty::apply(TypeCtor::Adt(adt), substs))
 }
 
@@ -892,7 +921,7 @@ fn type_for_type_alias(db: &dyn HirDatabase, t: TypeAliasId) -> Binders<Ty> {
     let ctx =
         TyLoweringContext::new(db, &resolver).with_type_param_mode(TypeParamLoweringMode::Variable);
     let type_ref = &db.type_alias_data(t).type_ref;
-    let substs = Substs::bound_vars(&generics);
+    let substs = Substs::bound_vars(&generics, DebruijnIndex::INNERMOST);
     let inner = Ty::from_hir(&ctx, type_ref.as_ref().unwrap_or(&TypeRef::Error));
     Binders::new(substs.len(), inner)
 }
diff --git a/crates/ra_hir_ty/src/tests/traits.rs b/crates/ra_hir_ty/src/tests/traits.rs
index 0a889f805..a46f03b7f 100644
--- a/crates/ra_hir_ty/src/tests/traits.rs
+++ b/crates/ra_hir_ty/src/tests/traits.rs
@@ -1211,6 +1211,42 @@ fn test(x: dyn Trait<u64>, y: &dyn Trait<u64>) {
 }
 
 #[test]
+fn dyn_trait_in_impl() {
+    assert_snapshot!(
+        infer(r#"
+trait Trait<T, U> {
+    fn foo(&self) -> (T, U);
+}
+struct S<T, U> {}
+impl<T, U> S<T, U> {
+    fn bar(&self) -> &dyn Trait<T, U> { loop {} }
+}
+trait Trait2<T, U> {
+    fn baz(&self) -> (T, U);
+}
+impl<T, U> Trait2<T, U> for dyn Trait<T, U> { }
+
+fn test(s: S<u32, i32>) {
+    s.bar().baz();
+}
+"#),
+        @r###"
+    [33; 37) 'self': &Self
+    [103; 107) 'self': &S<T, U>
+    [129; 140) '{ loop {} }': &dyn Trait<T, U>
+    [131; 138) 'loop {}': !
+    [136; 138) '{}': ()
+    [176; 180) 'self': &Self
+    [252; 253) 's': S<u32, i32>
+    [268; 290) '{     ...z(); }': ()
+    [274; 275) 's': S<u32, i32>
+    [274; 281) 's.bar()': &dyn Trait<u32, i32>
+    [274; 287) 's.bar().baz()': (u32, i32)
+    "###
+    );
+}
+
+#[test]
 fn dyn_trait_bare() {
     assert_snapshot!(
         infer(r#"
@@ -2204,3 +2240,201 @@ fn test(x: Box<dyn Trait>) {
     );
     assert_eq!(t, "()");
 }
+
+#[test]
+fn string_to_owned() {
+    let t = type_at(
+        r#"
+//- /main.rs
+struct String {}
+pub trait ToOwned {
+    type Owned;
+    fn to_owned(&self) -> Self::Owned;
+}
+impl ToOwned for str {
+    type Owned = String;
+}
+fn test() {
+    "foo".to_owned()<|>;
+}
+"#,
+    );
+    assert_eq!(t, "String");
+}
+
+#[test]
+fn iterator_chain() {
+    assert_snapshot!(
+        infer(r#"
+//- /main.rs
+#[lang = "fn_once"]
+trait FnOnce<Args> {
+    type Output;
+}
+#[lang = "fn_mut"]
+trait FnMut<Args>: FnOnce<Args> { }
+
+enum Option<T> { Some(T), None }
+use Option::*;
+
+pub trait Iterator {
+    type Item;
+
+    fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F>
+    where
+        F: FnMut(Self::Item) -> Option<B>,
+    { loop {} }
+
+    fn for_each<F>(self, f: F)
+    where
+        F: FnMut(Self::Item),
+    { loop {} }
+}
+
+pub trait IntoIterator {
+    type Item;
+    type IntoIter: Iterator<Item = Self::Item>;
+    fn into_iter(self) -> Self::IntoIter;
+}
+
+pub struct FilterMap<I, F> { }
+impl<B, I: Iterator, F> Iterator for FilterMap<I, F>
+where
+    F: FnMut(I::Item) -> Option<B>,
+{
+    type Item = B;
+}
+
+#[stable(feature = "rust1", since = "1.0.0")]
+impl<I: Iterator> IntoIterator for I {
+    type Item = I::Item;
+    type IntoIter = I;
+
+    fn into_iter(self) -> I {
+        self
+    }
+}
+
+struct Vec<T> {}
+impl<T> Vec<T> {
+    fn new() -> Self { loop {} }
+}
+
+impl<T> IntoIterator for Vec<T> {
+    type Item = T;
+    type IntoIter = IntoIter<T>;
+}
+
+pub struct IntoIter<T> { }
+impl<T> Iterator for IntoIter<T> {
+    type Item = T;
+}
+
+fn main() {
+    Vec::<i32>::new().into_iter()
+      .filter_map(|x| if x > 0 { Some(x as u32) } else { None })
+      .for_each(|y| { y; });
+}
+"#),
+        @r###"
+    [240; 244) 'self': Self
+    [246; 247) 'f': F
+    [331; 342) '{ loop {} }': FilterMap<Self, F>
+    [333; 340) 'loop {}': !
+    [338; 340) '{}': ()
+    [363; 367) 'self': Self
+    [369; 370) 'f': F
+    [419; 430) '{ loop {} }': ()
+    [421; 428) 'loop {}': !
+    [426; 428) '{}': ()
+    [539; 543) 'self': Self
+    [868; 872) 'self': I
+    [879; 899) '{     ...     }': I
+    [889; 893) 'self': I
+    [958; 969) '{ loop {} }': Vec<T>
+    [960; 967) 'loop {}': !
+    [965; 967) '{}': ()
+    [1156; 1287) '{     ... }); }': ()
+    [1162; 1177) 'Vec::<i32>::new': fn new<i32>() -> Vec<i32>
+    [1162; 1179) 'Vec::<...:new()': Vec<i32>
+    [1162; 1191) 'Vec::<...iter()': IntoIter<i32>
+    [1162; 1256) 'Vec::<...one })': FilterMap<IntoIter<i32>, |i32| -> Option<u32>>
+    [1162; 1284) 'Vec::<... y; })': ()
+    [1210; 1255) '|x| if...None }': |i32| -> Option<u32>
+    [1211; 1212) 'x': i32
+    [1214; 1255) 'if x >...None }': Option<u32>
+    [1217; 1218) 'x': i32
+    [1217; 1222) 'x > 0': bool
+    [1221; 1222) '0': i32
+    [1223; 1241) '{ Some...u32) }': Option<u32>
+    [1225; 1229) 'Some': Some<u32>(u32) -> Option<u32>
+    [1225; 1239) 'Some(x as u32)': Option<u32>
+    [1230; 1231) 'x': i32
+    [1230; 1238) 'x as u32': u32
+    [1247; 1255) '{ None }': Option<u32>
+    [1249; 1253) 'None': Option<u32>
+    [1273; 1283) '|y| { y; }': |u32| -> ()
+    [1274; 1275) 'y': u32
+    [1277; 1283) '{ y; }': ()
+    [1279; 1280) 'y': u32
+    "###
+    );
+}
+
+#[test]
+fn nested_assoc() {
+    let t = type_at(
+        r#"
+//- /main.rs
+struct Bar;
+struct Foo;
+
+trait A {
+    type OutputA;
+}
+
+impl A for Bar {
+    type OutputA = Foo;
+}
+
+trait B {
+    type Output;
+    fn foo() -> Self::Output;
+}
+
+impl<T:A> B for T {
+    type Output = T::OutputA;
+    fn foo() -> Self::Output { loop {} }
+}
+
+fn main() {
+    Bar::foo()<|>;
+}
+"#,
+    );
+    assert_eq!(t, "Foo");
+}
+
+#[test]
+fn trait_object_no_coercion() {
+    assert_snapshot!(
+        infer_with_mismatches(r#"
+trait Foo {}
+
+fn foo(x: &dyn Foo) {}
+
+fn test(x: &dyn Foo) {
+    foo(x);
+}
+"#, true),
+        @r###"
+    [22; 23) 'x': &dyn Foo
+    [35; 37) '{}': ()
+    [47; 48) 'x': &dyn Foo
+    [60; 75) '{     foo(x); }': ()
+    [66; 69) 'foo': fn foo(&dyn Foo)
+    [66; 72) 'foo(x)': ()
+    [70; 71) 'x': &dyn Foo
+    "###
+    );
+}
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index 60d70d18e..e00a82db2 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -17,7 +17,7 @@ use ra_db::{
 use super::{builtin, AssocTyValue, Canonical, ChalkContext, Impl, Obligation};
 use crate::{
     db::HirDatabase, display::HirDisplay, method_resolution::TyFingerprint, utils::generics,
-    ApplicationTy, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor,
+    ApplicationTy, DebruijnIndex, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor,
 };
 
 pub(super) mod tls;
@@ -815,7 +815,7 @@ pub(crate) fn associated_ty_data_query(
     // Lower bounds -- we could/should maybe move this to a separate query in `lower`
     let type_alias_data = db.type_alias_data(type_alias);
     let generic_params = generics(db.upcast(), type_alias.into());
-    let bound_vars = Substs::bound_vars(&generic_params);
+    let bound_vars = Substs::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
     let resolver = hir_def::resolver::HasResolver::resolver(type_alias, db.upcast());
     let ctx = crate::TyLoweringContext::new(db, &resolver)
         .with_type_param_mode(crate::lower::TypeParamLoweringMode::Variable);
@@ -849,7 +849,7 @@ pub(crate) fn trait_datum_query(
     let trait_data = db.trait_data(trait_);
     debug!("trait {:?} = {:?}", trait_id, trait_data.name);
     let generic_params = generics(db.upcast(), trait_.into());
-    let bound_vars = Substs::bound_vars(&generic_params);
+    let bound_vars = Substs::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
     let flags = chalk_rust_ir::TraitFlags {
         auto: trait_data.auto,
         upstream: trait_.lookup(db.upcast()).container.module(db.upcast()).krate != krate,
@@ -888,7 +888,7 @@ pub(crate) fn struct_datum_query(
         .as_generic_def()
         .map(|generic_def| {
             let generic_params = generics(db.upcast(), generic_def);
-            let bound_vars = Substs::bound_vars(&generic_params);
+            let bound_vars = Substs::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
             convert_where_clauses(db, generic_def, &bound_vars)
         })
         .unwrap_or_else(Vec::new);
@@ -934,7 +934,7 @@ fn impl_def_datum(
     let impl_data = db.impl_data(impl_id);
 
     let generic_params = generics(db.upcast(), impl_id.into());
-    let bound_vars = Substs::bound_vars(&generic_params);
+    let bound_vars = Substs::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
     let trait_ = trait_ref.trait_;
     let impl_type = if impl_id.lookup(db.upcast()).container.module(db.upcast()).krate == krate {
         chalk_rust_ir::ImplType::Local