Add &dyn Trait -> &dyn SuperTrait coercion, and fix &T -> &dyn Trait

4 files changed, 132 insertions, 44 deletions

diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs
index 15356ab37..2f2d3080e 100644
--- a/crates/ra_hir_ty/src/lib.rs
+++ b/crates/ra_hir_ty/src/lib.rs
@@ -461,6 +461,12 @@ impl<T> Binders<T> {
     }
 }
 
+impl<T: Clone> Binders<&T> {
+    pub fn cloned(&self) -> Binders<T> {
+        Binders { num_binders: self.num_binders, value: self.value.clone() }
+    }
+}
+
 impl<T: TypeWalk> Binders<T> {
     /// Substitutes all variables.
     pub fn subst(self, subst: &Substs) -> T {
@@ -757,6 +763,20 @@ pub trait TypeWalk {
     /// 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
+    where
+        Self: Sized,
+    {
+        self.walk_mut_binders(
+            &mut |ty_mut, binders| {
+                let ty = mem::replace(ty_mut, Ty::Unknown);
+                *ty_mut = f(ty, binders);
+            },
+            binders,
+        );
+        self
+    }
+
     fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
     where
         Self: Sized,
diff --git a/crates/ra_hir_ty/src/tests/coercion.rs b/crates/ra_hir_ty/src/tests/coercion.rs
index b6fce9377..5594ed394 100644
--- a/crates/ra_hir_ty/src/tests/coercion.rs
+++ b/crates/ra_hir_ty/src/tests/coercion.rs
@@ -587,25 +587,37 @@ pub trait CoerceUnsized<T> {}
 
 impl<T: Unsize<U>, U> CoerceUnsized<&U> for &T {}
 
-trait Foo {}
-trait Bar: Foo {}
-struct S;
-impl Foo for S {}
-impl Bar for S {}
+trait Foo<T, U> {}
+trait Bar<U, T, X>: Foo<T, U> {}
+trait Baz<T, X>: Bar<usize, T, X> {}
+
+struct S<T, X>;
+impl<T, X> Foo<T, usize> for S<T, X> {}
+impl<T, X> Bar<usize, T, X> for S<T, X> {}
+impl<T, X> Baz<T, X> for S<T, X> {}
 
 fn test() {
-    let obj: &dyn Bar = &S;
-    let obj: &dyn Foo = obj;
+    let obj: &dyn Baz<i8, i16> = &S;
+    let obj: &dyn Bar<_, _, _> = obj;
+    let obj: &dyn Foo<_, _> = obj;
+    let obj2: &dyn Baz<i8, i16> = &S;
+    let _: &dyn Foo<_, _> = obj2;
 }
 "#, true),
         @r###"
-    [240; 300) '{     ...obj; }': ()
-    [250; 253) 'obj': &dyn Bar
-    [266; 268) '&S': &S
-    [267; 268) 'S': S
-    [278; 281) 'obj': &dyn Foo
-    [294; 297) 'obj': &dyn Bar
-    [294; 297): expected &dyn Foo, got &dyn Bar
+    [388; 573) '{     ...bj2; }': ()
+    [398; 401) 'obj': &dyn Baz<i8, i16>
+    [423; 425) '&S': &S<i8, i16>
+    [424; 425) 'S': S<i8, i16>
+    [435; 438) 'obj': &dyn Bar<usize, i8, i16>
+    [460; 463) 'obj': &dyn Baz<i8, i16>
+    [473; 476) 'obj': &dyn Foo<i8, usize>
+    [495; 498) 'obj': &dyn Bar<usize, i8, i16>
+    [508; 512) 'obj2': &dyn Baz<i8, i16>
+    [534; 536) '&S': &S<i8, i16>
+    [535; 536) 'S': S<i8, i16>
+    [546; 547) '_': &dyn Foo<i8, usize>
+    [566; 570) 'obj2': &dyn Baz<i8, i16>
     "###
     );
 }
diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs
index 3c8dd4af8..19e533cee 100644
--- a/crates/ra_hir_ty/src/traits/builtin.rs
+++ b/crates/ra_hir_ty/src/traits/builtin.rs
@@ -8,7 +8,7 @@ use super::{AssocTyValue, Impl, UnsizeToSuperTraitObjectData};
 use crate::{
     db::HirDatabase,
     utils::{all_super_traits, generics},
-    ApplicationTy, GenericPredicate, Substs, TraitRef, Ty, TypeCtor,
+    ApplicationTy, Binders, GenericPredicate, Substs, TraitRef, Ty, TypeCtor,
 };
 
 pub(super) struct BuiltinImplData {
@@ -72,20 +72,25 @@ fn get_builtin_unsize_impls(
 
     if let Ty::Apply(ApplicationTy { ctor: TypeCtor::Array, .. }) = ty {
         callback(Impl::UnsizeArray);
+        return; // array is unsized, the rest of the impls shouldn't apply
     }
 
     if let Some(target_trait) = arg.as_ref().and_then(|t| t.dyn_trait_ref()) {
+        // FIXME what about more complicated dyn tys with marker traits?
         if let Some(trait_ref) = ty.dyn_trait_ref() {
-            let super_traits = all_super_traits(db, trait_ref.trait_);
-            if super_traits.contains(&target_trait.trait_) {
-                // callback(Impl::UnsizeToSuperTraitObject(UnsizeToSuperTraitObjectData {
-                //     trait_: trait_ref.trait_,
-                //     super_trait: target_trait.trait_,
-                // }));
+            if trait_ref.trait_ != target_trait.trait_ {
+                let super_traits = all_super_traits(db, trait_ref.trait_);
+                if super_traits.contains(&target_trait.trait_) {
+                    callback(Impl::UnsizeToSuperTraitObject(UnsizeToSuperTraitObjectData {
+                        trait_: trait_ref.trait_,
+                        super_trait: target_trait.trait_,
+                    }));
+                }
             }
+        } else {
+            // FIXME only for sized types
+            callback(Impl::UnsizeToTraitObject(target_trait.trait_));
         }
-
-        callback(Impl::UnsizeToTraitObject(target_trait.trait_));
     }
 }
 
@@ -270,48 +275,78 @@ fn trait_object_unsize_impl_datum(
 
     let self_ty = Ty::Bound(0);
 
-    let substs = Substs::build_for_def(db, trait_)
-        // this fits together nicely: $0 is our self type, and the rest are the type
-        // args for the trait
-        .fill_with_bound_vars(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)
         .build();
-    let trait_ref = TraitRef { trait_, substs };
-    // This is both the bound for the `dyn` type, *and* the bound for the impl!
-    // This works because the self type for `dyn` is always Ty::Bound(0), which
-    // we've also made the parameter for our impl self type.
-    let bounds = vec![GenericPredicate::Implemented(trait_ref)];
+    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 impl_substs = Substs::builder(2).push(self_ty).push(Ty::Dyn(bounds.clone().into())).build();
+    let self_substs = Substs::build_for_def(db, trait_).fill_with_bound_vars(0).build();
+    let self_trait_ref = TraitRef { trait_, substs: self_substs };
+    let where_clauses = vec![GenericPredicate::Implemented(self_trait_ref)];
+
+    let impl_substs =
+        Substs::builder(2).push(self_ty).push(Ty::Dyn(target_bounds.clone().into())).build();
 
     let trait_ref = TraitRef { trait_: unsize_trait, substs: impl_substs };
 
-    BuiltinImplData { num_vars: 1, trait_ref, where_clauses: bounds, assoc_ty_values: Vec::new() }
+    BuiltinImplData { num_vars, trait_ref, where_clauses, assoc_ty_values: Vec::new() }
 }
 
 fn super_trait_object_unsize_impl_datum(
     db: &impl HirDatabase,
     krate: CrateId,
-    _data: UnsizeToSuperTraitObjectData,
+    data: UnsizeToSuperTraitObjectData,
 ) -> BuiltinImplData {
-    // impl Unsize<dyn SuperTrait> for dyn Trait
+    // impl<T1, ...> Unsize<dyn SuperTrait> for dyn Trait<T1, ...>
 
     let unsize_trait = get_unsize_trait(db, krate) // get unsize trait
         // 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 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 mut path = crate::utils::find_super_trait_path(db, data.super_trait, data.trait_);
+    path.pop(); // the last one is our current trait, we don't need that
+    path.reverse(); // we want to go from trait to super trait
+
+    let mut current_trait_ref = self_trait_ref;
+    for t in path {
+        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) =>
+                {
+                    Some(Binders { value: tr, num_binders: b.num_binders })
+                }
+                _ => None,
+            })
+            .expect("trait bound for known super trait not found");
+        current_trait_ref = super_trait_ref.cloned().subst(&current_trait_ref.substs);
+    }
+
+    let super_bounds = vec![GenericPredicate::Implemented(current_trait_ref)];
+
     let substs = Substs::builder(2)
-        // .push(Ty::Dyn(todo!()))
-        // .push(Ty::Dyn(todo!()))
+        .push(Ty::Dyn(self_bounds.into()))
+        .push(Ty::Dyn(super_bounds.into()))
         .build();
 
     let trait_ref = TraitRef { trait_: unsize_trait, substs };
 
-    BuiltinImplData {
-        num_vars: 1,
-        trait_ref,
-        where_clauses: Vec::new(),
-        assoc_ty_values: Vec::new(),
-    }
+    BuiltinImplData { num_vars, trait_ref, where_clauses: Vec::new(), assoc_ty_values: Vec::new() }
 }
 
 fn get_fn_trait(
diff --git a/crates/ra_hir_ty/src/utils.rs b/crates/ra_hir_ty/src/utils.rs
index 508ae9046..0d1583c39 100644
--- a/crates/ra_hir_ty/src/utils.rs
+++ b/crates/ra_hir_ty/src/utils.rs
@@ -62,6 +62,27 @@ pub(super) fn all_super_traits(db: &impl DefDatabase, trait_: TraitId) -> Vec<Tr
     result
 }
 
+/// Finds a path from a trait to one of its descendant traits. Returns an empty
+/// vector if there is no path.
+pub(super) fn find_super_trait_path(
+    db: &impl DefDatabase,
+    super_trait: TraitId,
+    trait_: TraitId,
+) -> Vec<TraitId> {
+    if trait_ == super_trait {
+        return vec![trait_];
+    }
+
+    for tt in direct_super_traits(db, trait_) {
+        let mut path = find_super_trait_path(db, super_trait, tt);
+        if !path.is_empty() {
+            path.push(trait_);
+            return path;
+        }
+    }
+    Vec::new()
+}
+
 pub(super) fn associated_type_by_name_including_super_traits(
     db: &impl DefDatabase,
     trait_: TraitId,