Implement unsize coercion using proper trait solving

5 files changed, 170 insertions, 187 deletions

diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs
index 76069eb9c..6e1d268de 100644
--- a/crates/ra_hir_ty/src/infer.rs
+++ b/crates/ra_hir_ty/src/infer.rs
@@ -206,12 +206,6 @@ struct InferenceContext<'a, D: HirDatabase> {
     /// closures, but currently this is the only field that will change there,
     /// so it doesn't make sense.
     return_ty: Ty,
-
-    /// Impls of `CoerceUnsized` used in coercion.
-    /// (from_ty_ctor, to_ty_ctor) => coerce_generic_index
-    // FIXME: Use trait solver for this.
-    // Chalk seems unable to work well with builtin impl of `Unsize` now.
-    coerce_unsized_map: FxHashMap<(TypeCtor, TypeCtor), usize>,
 }
 
 impl<'a, D: HirDatabase> InferenceContext<'a, D> {
@@ -222,7 +216,6 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             obligations: Vec::default(),
             return_ty: Ty::Unknown, // set in collect_fn_signature
             trait_env: TraitEnvironment::lower(db, &resolver),
-            coerce_unsized_map: Self::init_coerce_unsized_map(db, &resolver),
             db,
             owner,
             body: db.body(owner),
diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs
index fb6a51b12..95ac3c713 100644
--- a/crates/ra_hir_ty/src/infer/coerce.rs
+++ b/crates/ra_hir_ty/src/infer/coerce.rs
@@ -4,11 +4,12 @@
 //!
 //! See: https://doc.rust-lang.org/nomicon/coercions.html
 
-use hir_def::{lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AdtId};
-use rustc_hash::FxHashMap;
+use hir_def::{lang_item::LangItemTarget, type_ref::Mutability};
 use test_utils::tested_by;
 
-use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk};
+use crate::{
+    autoderef, db::HirDatabase, traits::Solution, Obligation, Substs, TraitRef, Ty, TypeCtor,
+};
 
 use super::{unify::TypeVarValue, InEnvironment, InferTy, InferenceContext};
 
@@ -39,44 +40,6 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         }
     }
 
-    pub(super) fn init_coerce_unsized_map(
-        db: &'a D,
-        resolver: &Resolver,
-    ) -> FxHashMap<(TypeCtor, TypeCtor), usize> {
-        let krate = resolver.krate().unwrap();
-        let impls = match db.lang_item(krate, "coerce_unsized".into()) {
-            Some(LangItemTarget::TraitId(trait_)) => db.impls_for_trait(krate, trait_),
-            _ => return FxHashMap::default(),
-        };
-
-        impls
-            .iter()
-            .filter_map(|&impl_id| {
-                let trait_ref = db.impl_trait(impl_id)?;
-
-                // `CoerseUnsized` has one generic parameter for the target type.
-                let cur_from_ty = trait_ref.value.substs.0.get(0)?;
-                let cur_to_ty = trait_ref.value.substs.0.get(1)?;
-
-                match (&cur_from_ty, cur_to_ty) {
-                    (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => {
-                        // FIXME: We return the first non-equal bound as the type parameter to coerce to unsized type.
-                        // This works for smart-pointer-like coercion, which covers all impls from std.
-                        st1.iter().zip(st2.iter()).enumerate().find_map(|(i, (ty1, ty2))| {
-                            match (ty1, ty2) {
-                                (Ty::Bound(idx1), Ty::Bound(idx2)) if idx1 != idx2 => {
-                                    Some(((*ctor1, *ctor2), i))
-                                }
-                                _ => None,
-                            }
-                        })
-                    }
-                    _ => None,
-                }
-            })
-            .collect()
-    }
-
     fn coerce_inner(&mut self, mut from_ty: Ty, to_ty: &Ty) -> bool {
         match (&from_ty, to_ty) {
             // Never type will make type variable to fallback to Never Type instead of Unknown.
@@ -157,154 +120,38 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
     ///
     /// See: https://doc.rust-lang.org/nightly/std/marker/trait.CoerceUnsized.html
     fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty) -> Option<bool> {
-        let (ctor1, st1, ctor2, st2) = match (from_ty, to_ty) {
-            (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => (ctor1, st1, ctor2, st2),
+        let krate = self.resolver.krate().unwrap();
+        let coerce_unsized_trait = match self.db.lang_item(krate, "coerce_unsized".into()) {
+            Some(LangItemTarget::TraitId(trait_)) => trait_,
             _ => return None,
         };
 
-        let coerce_generic_index = *self.coerce_unsized_map.get(&(*ctor1, *ctor2))?;
-
-        // Check `Unsize` first
-        match self.check_unsize_and_coerce(
-            st1.0.get(coerce_generic_index)?,
-            st2.0.get(coerce_generic_index)?,
-            0,
-        ) {
-            Some(true) => {}
-            ret => return ret,
+        let generic_params = crate::utils::generics(self.db, coerce_unsized_trait.into());
+        if generic_params.len() != 2 {
+            // The CoerceUnsized trait should have two generic params: Self and T.
+            return None;
         }
 
-        let ret = st1
-            .iter()
-            .zip(st2.iter())
-            .enumerate()
-            .filter(|&(idx, _)| idx != coerce_generic_index)
-            .all(|(_, (ty1, ty2))| self.unify(ty1, ty2));
+        let substs = Substs::build_for_generics(&generic_params)
+            .push(from_ty.clone())
+            .push(to_ty.clone())
+            .build();
+        let trait_ref = TraitRef { trait_: coerce_unsized_trait, substs };
+        let goal = InEnvironment::new(self.trait_env.clone(), Obligation::Trait(trait_ref));
 
-        Some(ret)
-    }
+        let canonicalizer = self.canonicalizer();
+        let canonicalized = canonicalizer.canonicalize_obligation(goal);
 
-    /// Check if `from_ty: Unsize<to_ty>`, and coerce to `to_ty` if it holds.
-    ///
-    /// It should not be directly called. It is only used by `try_coerce_unsized`.
-    ///
-    /// See: https://doc.rust-lang.org/nightly/std/marker/trait.Unsize.html
-    fn check_unsize_and_coerce(&mut self, from_ty: &Ty, to_ty: &Ty, depth: usize) -> Option<bool> {
-        if depth > 1000 {
-            panic!("Infinite recursion in coercion");
-        }
-
-        match (&from_ty, &to_ty) {
-            // `[T; N]` -> `[T]`
-            (ty_app!(TypeCtor::Array, st1), ty_app!(TypeCtor::Slice, st2)) => {
-                Some(self.unify(&st1[0], &st2[0]))
-            }
+        let solution = self.db.trait_solve(krate, canonicalized.value.clone())?;
 
-            // `T` -> `dyn Trait` when `T: Trait`
-            (_, Ty::Dyn(_)) => {
-                // FIXME: Check predicates
-                Some(true)
-            }
-
-            // `(..., T)` -> `(..., U)` when `T: Unsize<U>`
-            (
-                ty_app!(TypeCtor::Tuple { cardinality: len1 }, st1),
-                ty_app!(TypeCtor::Tuple { cardinality: len2 }, st2),
-            ) => {
-                if len1 != len2 || *len1 == 0 {
-                    return None;
-                }
-
-                match self.check_unsize_and_coerce(
-                    st1.last().unwrap(),
-                    st2.last().unwrap(),
-                    depth + 1,
-                ) {
-                    Some(true) => {}
-                    ret => return ret,
-                }
-
-                let ret = st1[..st1.len() - 1]
-                    .iter()
-                    .zip(&st2[..st2.len() - 1])
-                    .all(|(ty1, ty2)| self.unify(ty1, ty2));
-
-                Some(ret)
-            }
-
-            // Foo<..., T, ...> is Unsize<Foo<..., U, ...>> if:
-            // - T: Unsize<U>
-            // - Foo is a struct
-            // - Only the last field of Foo has a type involving T
-            // - T is not part of the type of any other fields
-            // - Bar<T>: Unsize<Bar<U>>, if the last field of Foo has type Bar<T>
-            (
-                ty_app!(TypeCtor::Adt(AdtId::StructId(struct1)), st1),
-                ty_app!(TypeCtor::Adt(AdtId::StructId(struct2)), st2),
-            ) if struct1 == struct2 => {
-                let field_tys = self.db.field_types((*struct1).into());
-                let struct_data = self.db.struct_data(*struct1);
-
-                let mut fields = struct_data.variant_data.fields().iter();
-                let (last_field_id, _data) = fields.next_back()?;
-
-                // Get the generic parameter involved in the last field.
-                let unsize_generic_index = {
-                    let mut index = None;
-                    let mut multiple_param = false;
-                    field_tys[last_field_id].value.walk(&mut |ty| {
-                        if let &Ty::Bound(idx) = ty {
-                            if index.is_none() {
-                                index = Some(idx);
-                            } else if Some(idx) != index {
-                                multiple_param = true;
-                            }
-                        }
-                    });
-
-                    if multiple_param {
-                        return None;
-                    }
-                    index?
-                };
-
-                // Check other fields do not involve it.
-                let mut multiple_used = false;
-                fields.for_each(|(field_id, _data)| {
-                    field_tys[field_id].value.walk(&mut |ty| match ty {
-                        &Ty::Bound(idx) if idx == unsize_generic_index => multiple_used = true,
-                        _ => {}
-                    })
-                });
-                if multiple_used {
-                    return None;
-                }
-
-                let unsize_generic_index = unsize_generic_index as usize;
-
-                // Check `Unsize` first
-                match self.check_unsize_and_coerce(
-                    st1.get(unsize_generic_index)?,
-                    st2.get(unsize_generic_index)?,
-                    depth + 1,
-                ) {
-                    Some(true) => {}
-                    ret => return ret,
-                }
-
-                // Then unify other parameters
-                let ret = st1
-                    .iter()
-                    .zip(st2.iter())
-                    .enumerate()
-                    .filter(|&(idx, _)| idx != unsize_generic_index)
-                    .all(|(_, (ty1, ty2))| self.unify(ty1, ty2));
-
-                Some(ret)
+        match solution {
+            Solution::Unique(v) => {
+                canonicalized.apply_solution(self, v.0);
             }
+            _ => return None,
+        };
 
-            _ => None,
-        }
+        Some(true)
     }
 
     /// Unify `from_ty` to `to_ty` with optional auto Deref
diff --git a/crates/ra_hir_ty/src/tests/coercion.rs b/crates/ra_hir_ty/src/tests/coercion.rs
index 42330b269..aa2dfb5f0 100644
--- a/crates/ra_hir_ty/src/tests/coercion.rs
+++ b/crates/ra_hir_ty/src/tests/coercion.rs
@@ -548,3 +548,85 @@ impl<TT> S<TT> {
     "###
     );
 }
+
+#[test]
+fn coerce_unsize_array() {
+    assert_snapshot!(
+        infer_with_mismatches(r#"
+#[lang = "unsize"]
+pub trait Unsize<T> {}
+#[lang = "coerce_unsized"]
+pub trait CoerceUnsized<T> {}
+
+impl<T: Unsize<U>, U> CoerceUnsized<&U> for &T {}
+
+fn test() {
+    let f: &[usize] = &[1, 2, 3];
+}
+"#, true),
+        @r###"
+    [162; 199) '{     ... 3]; }': ()
+    [172; 173) 'f': &[usize]
+    [186; 196) '&[1, 2, 3]': &[usize; _]
+    [187; 196) '[1, 2, 3]': [usize; _]
+    [188; 189) '1': usize
+    [191; 192) '2': usize
+    [194; 195) '3': usize
+    "###
+    );
+}
+
+#[ignore]
+#[test]
+fn coerce_unsize_trait_object() {
+    assert_snapshot!(
+        infer_with_mismatches(r#"
+#[lang = "unsize"]
+pub trait Unsize<T> {}
+#[lang = "coerce_unsized"]
+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 {}
+
+fn test() {
+    let obj: &dyn Bar = &S;
+    let obj: &dyn Foo = obj;
+}
+"#, true),
+        @r###"
+    "###
+    );
+}
+
+#[ignore]
+#[test]
+fn coerce_unsize_generic() {
+    // FIXME: Implement this
+    // https://doc.rust-lang.org/reference/type-coercions.html#unsized-coercions
+    assert_snapshot!(
+        infer_with_mismatches(r#"
+#[lang = "unsize"]
+pub trait Unsize<T> {}
+#[lang = "coerce_unsized"]
+pub trait CoerceUnsized<T> {}
+
+impl<T: Unsize<U>, U> CoerceUnsized<&U> for &T {}
+
+struct Foo<T> { t: T };
+struct Bar<T>(Foo<T>);
+
+fn test() {
+    let _: &Foo<[usize]> = &Foo { t: [1, 2, 3] };
+    let _: &Bar<[usize]> = &Bar(Foo { t: [1, 2, 3] });
+}
+"#, true),
+        @r###"
+    "###
+    );
+}
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs
index e83449957..c385f0098 100644
--- a/crates/ra_hir_ty/src/traits.rs
+++ b/crates/ra_hir_ty/src/traits.rs
@@ -343,6 +343,8 @@ pub enum Impl {
     ImplBlock(ImplId),
     /// Closure types implement the Fn traits synthetically.
     ClosureFnTraitImpl(ClosureFnTraitImplData),
+    /// [T; n]: Unsize<[T]>
+    UnsizeArray,
 }
 /// This exists just for Chalk, because our ImplIds are only unique per module.
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs
index a537420a5..394232fd9 100644
--- a/crates/ra_hir_ty/src/traits/builtin.rs
+++ b/crates/ra_hir_ty/src/traits/builtin.rs
@@ -5,7 +5,7 @@ use hir_expand::name::name;
 use ra_db::CrateId;
 
 use super::{AssocTyValue, Impl};
-use crate::{db::HirDatabase, ApplicationTy, Substs, TraitRef, Ty, TypeCtor};
+use crate::{db::HirDatabase, utils::generics, ApplicationTy, Substs, TraitRef, Ty, TypeCtor};
 
 pub(super) struct BuiltinImplData {
     pub num_vars: usize,
@@ -43,12 +43,22 @@ pub(super) fn get_builtin_impls(
             }
         }
     }
+    if let Ty::Apply(ApplicationTy { ctor: TypeCtor::Array, .. }) = ty {
+        if let Some(actual_trait) = get_unsize_trait(db, krate) {
+            if trait_ == actual_trait {
+                if check_unsize_impl_prerequisites(db, krate) {
+                    callback(Impl::UnsizeArray);
+                }
+            }
+        }
+    }
 }
 
 pub(super) fn impl_datum(db: &impl HirDatabase, krate: CrateId, impl_: Impl) -> BuiltinImplData {
     match impl_ {
         Impl::ImplBlock(_) => unreachable!(),
         Impl::ClosureFnTraitImpl(data) => closure_fn_trait_impl_datum(db, krate, data),
+        Impl::UnsizeArray => array_unsize_impl_datum(db, krate),
     }
 }
 
@@ -65,6 +75,8 @@ pub(super) fn associated_ty_value(
     }
 }
 
+// Closure Fn trait impls
+
 fn check_closure_fn_trait_impl_prerequisites(
     db: &impl HirDatabase,
     krate: CrateId,
@@ -165,6 +177,45 @@ fn closure_fn_trait_output_assoc_ty_value(
     }
 }
 
+// Array unsizing
+
+fn check_unsize_impl_prerequisites(db: &impl HirDatabase, krate: CrateId) -> bool {
+    // the Unsize trait needs to exist and have two type parameters (Self and T)
+    let unsize_trait = match get_unsize_trait(db, krate) {
+        Some(t) => t,
+        None => return false,
+    };
+    let generic_params = generics(db, unsize_trait.into());
+    if generic_params.len() != 2 {
+        return false;
+    }
+    true
+}
+
+fn array_unsize_impl_datum(db: &impl HirDatabase, krate: CrateId) -> BuiltinImplData {
+    // impl<T> Unsize<[T]> for [T; _]
+    // (this can be a single impl because we don't distinguish array sizes currently)
+
+    let trait_ = get_unsize_trait(db, krate) // get unsize trait
+        // the existence of the Unsize trait has been checked before
+        .expect("Unsize trait missing");
+
+    let var = Ty::Bound(0);
+    let substs = Substs::builder(2)
+        .push(Ty::apply_one(TypeCtor::Array, var.clone()))
+        .push(Ty::apply_one(TypeCtor::Slice, var))
+        .build();
+
+    let trait_ref = TraitRef { trait_, substs };
+
+    BuiltinImplData {
+        num_vars: 1,
+        trait_ref,
+        where_clauses: Vec::new(),
+        assoc_ty_values: Vec::new(),
+    }
+}
+
 fn get_fn_trait(
     db: &impl HirDatabase,
     krate: CrateId,
@@ -176,3 +227,11 @@ fn get_fn_trait(
         _ => None,
     }
 }
+
+fn get_unsize_trait(db: &impl HirDatabase, krate: CrateId) -> Option<TraitId> {
+    let target = db.lang_item(krate, "unsize".into())?;
+    match target {
+        LangItemTarget::TraitId(t) => Some(t),
+        _ => None,
+    }
+}