More trait infrastructure

- make it possible to get parent trait from method - add 'obligation' machinery for checking that a type implements a trait (and inferring facts about type variables from that) - handle type parameters of traits (to a certain degree) - improve the hacky implements check to cover enough cases to exercise the handling of traits with type parameters - basic canonicalization (will probably also be done by Chalk)
author: Florian Diebold <[email protected]> 2019-03-31 19:02:16 +0100
committer: Florian Diebold <[email protected]> 2019-04-14 10:28:53 +0100
commit: a1ed53a4f183b5826162eb9e998207b92be9c57f (patch)
tree: 7c139a7dc38483188653c6d40583cddac9d23192 /crates/ra_hir/src/ty
parent: 413c87f155ab6b389b1cc122b5739716acccb476 (diff)
5 files changed, 260 insertions, 43 deletions
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index 28947be51..3dec5936a 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -41,7 +41,7 @@ use crate::{
    ty::infer::diagnostics::InferenceDiagnostic,
    diagnostics::DiagnosticSink,
 };
-use super::{Ty, TypableDef, Substs, primitive, op, FnSig, ApplicationTy, TypeCtor};
+use super::{Ty, TypableDef, Substs, primitive, op, FnSig, ApplicationTy, TypeCtor, traits::{ Solution, Obligation, Guidance}, CallableDef, TraitRef};
 /// The entry point of type inference.
 pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
@@ -153,6 +153,7 @@ struct InferenceContext<'a, D: HirDatabase> {
    body: Arc<Body>,
    resolver: Resolver,
    var_unification_table: InPlaceUnificationTable<TypeVarId>,
+    obligations: Vec<Obligation>,
    method_resolutions: FxHashMap<ExprId, Function>,
    field_resolutions: FxHashMap<ExprId, StructField>,
    assoc_resolutions: FxHashMap<ExprOrPatId, ImplItem>,
@@ -173,6 +174,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
            type_of_pat: ArenaMap::default(),
            diagnostics: Vec::default(),
            var_unification_table: InPlaceUnificationTable::new(),
+            obligations: Vec::default(),
            return_ty: Ty::Unknown, // set in collect_fn_signature
            db,
            body,
@@ -181,6 +183,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
    }
    fn resolve_all(mut self) -> InferenceResult {
+        // FIXME resolve obligations as well (use Guidance if necessary)
        let mut tv_stack = Vec::new();
        let mut expr_types = mem::replace(&mut self.type_of_expr, ArenaMap::default());
        for ty in expr_types.values_mut() {
@@ -311,11 +314,49 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
        ty.fold(&mut |ty| self.insert_type_vars_shallow(ty))
    }
+    fn resolve_obligations_as_possible(&mut self) {
+        let obligations = mem::replace(&mut self.obligations, Vec::new());
+        for obligation in obligations {
+            // FIXME resolve types in the obligation first
+            let (solution, var_mapping) = match &obligation {
+                Obligation::Trait(tr) => {
+                    let (tr, var_mapping) = super::traits::canonicalize(tr.clone());
+                    (self.db.implements(tr), var_mapping)
+                }
+            };
+            match solution {
+                Some(Solution::Unique(substs)) => {
+                    for (i, subst) in substs.0.iter().enumerate() {
+                        let uncanonical = var_mapping[i];
+                        // FIXME the subst may contain type variables, which would need to be mapped back as well
+                        self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
+                    }
+                }
+                Some(Solution::Ambig(Guidance::Definite(substs))) => {
+                    for (i, subst) in substs.0.iter().enumerate() {
+                        let uncanonical = var_mapping[i];
+                        // FIXME the subst may contain type variables, which would need to be mapped back as well
+                        self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
+                    }
+                    self.obligations.push(obligation);
+                }
+                Some(_) => {
+                    self.obligations.push(obligation);
+                }
+                None => {
+                    // FIXME obligation cannot be fulfilled => diagnostic
+                }
+            }
+        }
+    }
    /// Resolves the type as far as currently possible, replacing type variables
    /// by their known types. All types returned by the infer_* functions should
    /// be resolved as far as possible, i.e. contain no type variables with
    /// known type.
    fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
+        self.resolve_obligations_as_possible();
        ty.fold(&mut |ty| match ty {
            Ty::Infer(tv) => {
                let inner = tv.to_inner();
@@ -710,12 +751,19 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
        &mut self,
        def_generics: Option<Arc<GenericParams>>,
        generic_args: &Option<GenericArgs>,
+        receiver_ty: &Ty,
    ) -> Substs {
        let (parent_param_count, param_count) =
-            def_generics.map_or((0, 0), |g| (g.count_parent_params(), g.params.len()));
+            def_generics.as_ref().map_or((0, 0), |g| (g.count_parent_params(), g.params.len()));
        let mut substs = Vec::with_capacity(parent_param_count + param_count);
-        for _ in 0..parent_param_count {
+        if let Some(parent_generics) = def_generics.and_then(|p| p.parent_params.clone()) {
-            substs.push(Ty::Unknown);
+            for param in &parent_generics.params {
+                if param.name.as_known_name() == Some(crate::KnownName::SelfType) {
+                    substs.push(receiver_ty.clone());
+                } else {
+                    substs.push(Ty::Unknown);
+                }
+            }
        }
        // handle provided type arguments
        if let Some(generic_args) = generic_args {
@@ -817,6 +865,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                        (Vec::new(), Ty::Unknown)
                    }
                };
+                // FIXME register obligations from where clauses from the function
                let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
                for (arg, param) in args.iter().zip(param_iter) {
                    self.infer_expr(*arg, &Expectation::has_type(param));
@@ -838,7 +887,11 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                    }
                    None => (receiver_ty, Ty::Unknown, None),
                };
-                let substs = self.substs_for_method_call(def_generics, generic_args);
+                let substs = self.substs_for_method_call(
+                    def_generics.clone(),
+                    generic_args,
+                    &derefed_receiver_ty,
+                );
                let method_ty = method_ty.apply_substs(substs);
                let method_ty = self.insert_type_vars(method_ty);
                let (expected_receiver_ty, param_tys, ret_ty) = match &method_ty {
@@ -859,6 +912,24 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                            let sig = self.db.callable_item_signature(def);
                            let ret_ty = sig.ret().clone().subst(&a_ty.parameters);
+                            // add obligation for trait implementation, if this is a trait method
+                            // FIXME also register obligations from where clauses from the trait or impl and method
+                            match def {
+                                CallableDef::Function(f) => {
+                                    if let Some(trait_) = f.parent_trait(self.db) {
+                                        // construct a TraitDef
+                                        let substs = a_ty.parameters.prefix(
+                                            def_generics
+                                                .expect("trait parent should always have generics")
+                                                .count_parent_params(),
+                                        );
+                                        self.obligations
+                                            .push(Obligation::Trait(TraitRef { trait_, substs }));
+                                    }
+                                }
+                                CallableDef::Struct(_) | CallableDef::EnumVariant(_) => {}
+                            }
                            if !sig.params().is_empty() {
                                let mut params_iter = sig
                                    .params()
@@ -875,6 +946,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                    _ => (Ty::Unknown, Vec::new(), Ty::Unknown),
                };
                // Apply autoref so the below unification works correctly
+                // FIXME: return correct autorefs/derefs from lookup_method
                let actual_receiver_ty = match expected_receiver_ty.as_reference() {
                    Some((_, mutability)) => {
                        Ty::apply_one(TypeCtor::Ref(mutability), derefed_receiver_ty)
@@ -1180,7 +1252,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
 /// The ID of a type variable.
 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
-pub struct TypeVarId(u32);
+pub struct TypeVarId(pub(super) u32);
 impl UnifyKey for TypeVarId {
    type Value = TypeVarValue;
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 4523b3954..ccacb5e73 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -206,6 +206,7 @@ impl TraitRef {
        db: &impl HirDatabase,
        resolver: &Resolver,
        type_ref: &TypeRef,
+        explicit_self_ty: Option<Ty>,
    ) -> Option<Self> {
        let path = match type_ref {
            TypeRef::Path(path) => path,
@@ -215,7 +216,13 @@ impl TraitRef {
            Resolution::Def(ModuleDef::Trait(tr)) => tr,
            _ => return None,
        };
-        let substs = Self::substs_from_path(db, resolver, path, resolved);
+        let mut substs = Self::substs_from_path(db, resolver, path, resolved);
+        if let Some(self_ty) = explicit_self_ty {
+            // FIXME this could be nicer
+            let mut substs_vec = substs.0.to_vec();
+            substs_vec[0] = self_ty;
+            substs.0 = substs_vec.into();
+        }
        Some(TraitRef { trait_: resolved, substs })
    }
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index aac7d6384..f69b8304b 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -108,20 +108,6 @@ impl CrateImplBlocks {
    }
 }
-/// Rudimentary check whether an impl exists for a given type and trait; this
-/// will actually be done by chalk.
-pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> bool {
-    // FIXME use all trait impls in the whole crate graph
-    let krate = trait_ref.trait_.module(db).krate(db);
-    let krate = match krate {
-        Some(krate) => krate,
-        None => return false,
-    };
-    let crate_impl_blocks = db.impls_in_crate(krate);
-    let mut impl_blocks = crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_ref.trait_);
-    impl_blocks.any(|impl_block| &impl_block.target_ty(db) == trait_ref.self_ty())
-}
 fn def_crate(db: &impl HirDatabase, ty: &Ty) -> Option<Crate> {
    match ty {
        Ty::Apply(a_ty) => match a_ty.ctor {
@@ -142,6 +128,7 @@ impl Ty {
        resolver: &Resolver,
    ) -> Option<(Ty, Function)> {
        // FIXME: trait methods should be used before autoderefs
+        // (and we need to do autoderefs for trait method calls as well)
        let inherent_method = self.clone().iterate_methods(db, |ty, f| {
            let sig = f.signature(db);
            if sig.name() == name && sig.has_self_param() {
@@ -174,24 +161,15 @@ impl Ty {
                }
            }
        }
-        // FIXME:
-        //  - we might not actually be able to determine fully that the type
-        //    implements the trait here; it's enough if we (well, Chalk) determine
-        //    that it's possible.
-        //  - when the trait method is picked, we need to register an
-        //    'obligation' somewhere so that we later check that it's really
-        //    implemented
-        //  - both points go for additional requirements from where clauses as
-        //    well (in fact, the 'implements' condition could just be considered a
-        //    'where Self: Trait' clause)
        candidates.retain(|(t, _m)| {
-            // FIXME construct substs of the correct length for the trait
+            let trait_ref =
-            //  - check in rustc whether it does anything smarter than putting variables for everything
+                TraitRef { trait_: *t, substs: fresh_substs_for_trait(db, *t, self.clone()) };
-            let trait_ref = TraitRef { trait_: *t, substs: Substs::single(self.clone()) };
+            let (trait_ref, _) = super::traits::canonicalize(trait_ref);
-            db.implements(trait_ref)
+            db.implements(trait_ref).is_some()
        });
        // FIXME if there's multiple candidates here, that's an ambiguity error
        let (_chosen_trait, chosen_method) = candidates.first()?;
+        // FIXME return correct receiver type
        Some((self.clone(), *chosen_method))
    }
@@ -254,3 +232,16 @@ impl Ty {
        None
    }
 }
+fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs {
+    let mut substs = Vec::new();
+    let mut counter = 0;
+    let generics = tr.generic_params(db);
+    substs.push(self_ty);
+    substs.extend(generics.params_including_parent().into_iter().skip(1).map(|_p| {
+        let fresh_var = Ty::Infer(super::infer::InferTy::TypeVar(super::infer::TypeVarId(counter)));
+        counter += 1;
+        fresh_var
+    }));
+    substs.into()
+}
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index d7c2ca132..291bc9ae5 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -1926,8 +1926,8 @@ fn test() {
 }
 "#),
        @r###"
-[31; 35) 'self': &{unknown}
+[31; 35) 'self': &Self
-[110; 114) 'self': &{unknown}
+[110; 114) 'self': &Self
 [170; 228) '{     ...i128 }': ()
 [176; 178) 'S1': S1
 [176; 187) 'S1.method()': u32
@@ -1972,8 +1972,8 @@ mod bar_test {
 }
 "#),
        @r###"
-[63; 67) 'self': &{unknown}
+[63; 67) 'self': &Self
-[169; 173) 'self': &{unknown}
+[169; 173) 'self': &Self
 [300; 337) '{     ...     }': ()
 [310; 311) 'S': S
 [310; 320) 'S.method()': u32
@@ -1998,10 +1998,45 @@ fn test() {
 }
 "#),
        @r###"
-[33; 37) 'self': &{unknown}
+[33; 37) 'self': &Self
 [92; 111) '{     ...d(); }': ()
 [98; 99) 'S': S
-[98; 108) 'S.method()': {unknown}"###
+[98; 108) 'S.method()': u32"###
+    );
+}
+#[test]
+fn infer_trait_method_generic_more_params() {
+    // the trait implementation is intentionally incomplete -- it shouldn't matter
+    assert_snapshot_matches!(
+        infer(r#"
+trait Trait<T1, T2, T3> {
+    fn method1(&self) -> (T1, T2, T3);
+    fn method2(&self) -> (T3, T2, T1);
+}
+struct S1;
+impl Trait<u8, u16, u32> for S1 {}
+struct S2;
+impl<T> Trait<i8, i16, T> for S2 {}
+fn test() {
+    S1.method1(); // u8, u16, u32
+    S1.method2(); // u32, u16, u8
+    S2.method1(); // i8, i16, {unknown}
+    S2.method2(); // {unknown}, i16, i8
+}
+"#),
+        @r###"
+[43; 47) 'self': &Self
+[82; 86) 'self': &Self
+[210; 361) '{     ..., i8 }': ()
+[216; 218) 'S1': S1
+[216; 228) 'S1.method1()': (u8, u16, u32)
+[250; 252) 'S1': S1
+[250; 262) 'S1.method2()': (u32, u16, u8)
+[284; 286) 'S2': S2
+[284; 296) 'S2.method1()': (i8, i16, {unknown})
+[324; 326) 'S2': S2
+[324; 336) 'S2.method2()': ({unknown}, i16, i8)"###
    );
 }
@@ -2020,7 +2055,7 @@ fn test() {
 }
 "#),
        @r###"
-[33; 37) 'self': &{unknown}
+[33; 37) 'self': &Self
 [102; 127) '{     ...d(); }': ()
 [108; 109) 'S': S<u32>(T) -> S<T>
 [108; 115) 'S(1u32)': S<u32>
@@ -2168,7 +2203,7 @@ fn test() {
 }
 "#),
        @r###"
-[29; 33) 'self': {unknown}
+[29; 33) 'self': Self
 [107; 198) '{     ...(S); }': ()
 [117; 118) 'x': u32
 [126; 127) 'S': S
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
new file mode 100644
index 000000000..f8c3958bd
--- /dev/null
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -0,0 +1,112 @@
+//! Stuff that will probably mostly replaced by Chalk.
+use std::collections::HashMap;
+use crate::db::HirDatabase;
+use super::{ TraitRef, Substs, infer::{ TypeVarId, InferTy}, Ty};
+// Copied (and simplified) from Chalk
+#[derive(Clone, Debug, PartialEq, Eq)]
+/// A (possible) solution for a proposed goal. Usually packaged in a `Result`,
+/// where `Err` represents definite *failure* to prove a goal.
+pub enum Solution {
+    /// The goal indeed holds, and there is a unique value for all existential
+    /// variables.
+    Unique(Substs),
+    /// The goal may be provable in multiple ways, but regardless we may have some guidance
+    /// for type inference.
+    Ambig(Guidance),
+}
+#[derive(Clone, Debug, PartialEq, Eq)]
+/// When a goal holds ambiguously (e.g., because there are multiple possible
+/// solutions), we issue a set of *guidance* back to type inference.
+pub enum Guidance {
+    /// The existential variables *must* have the given values if the goal is
+    /// ever to hold, but that alone isn't enough to guarantee the goal will
+    /// actually hold.
+    Definite(Substs),
+    /// There are multiple plausible values for the existentials, but the ones
+    /// here are suggested as the preferred choice heuristically. These should
+    /// be used for inference fallback only.
+    Suggested(Substs),
+    /// There's no useful information to feed back to type inference
+    Unknown,
+}
+/// Something that needs to be proven (by Chalk) during type checking, e.g. that
+/// a certain type implements a certain trait. Proving the Obligation might
+/// result in additional information about inference variables.
+///
+/// This might be handled by Chalk when we integrate it?
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub enum Obligation {
+    /// Prove that a certain type implements a trait (the type is the `Self` type
+    /// parameter to the `TraitRef`).
+    Trait(TraitRef),
+}
+/// Rudimentary check whether an impl exists for a given type and trait; this
+/// will actually be done by chalk.
+pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> Option<Solution> {
+    // FIXME use all trait impls in the whole crate graph
+    let krate = trait_ref.trait_.module(db).krate(db);
+    let krate = match krate {
+        Some(krate) => krate,
+        None => return None,
+    };
+    let crate_impl_blocks = db.impls_in_crate(krate);
+    let mut impl_blocks = crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_ref.trait_);
+    impl_blocks
+        .find_map(|impl_block| unify_trait_refs(&trait_ref, &impl_block.target_trait_ref(db)?))
+}
+pub(super) fn canonicalize(trait_ref: TraitRef) -> (TraitRef, Vec<TypeVarId>) {
+    let mut canonical = HashMap::new(); // mapping uncanonical -> canonical
+    let mut uncanonical = Vec::new(); // mapping canonical -> uncanonical (which is dense)
+    let mut substs = trait_ref.substs.0.to_vec();
+    for ty in &mut substs {
+        ty.walk_mut(&mut |ty| match ty {
+            Ty::Infer(InferTy::TypeVar(tv)) => {
+                let tv: &mut TypeVarId = tv;
+                *tv = *canonical.entry(*tv).or_insert_with(|| {
+                    let i = uncanonical.len();
+                    uncanonical.push(*tv);
+                    TypeVarId(i as u32)
+                });
+            }
+            _ => {}
+        });
+    }
+    (TraitRef { substs: substs.into(), ..trait_ref }, uncanonical)
+}
+fn unify_trait_refs(tr1: &TraitRef, tr2: &TraitRef) -> Option<Solution> {
+    if tr1.trait_ != tr2.trait_ {
+        return None;
+    }
+    let mut solution_substs = Vec::new();
+    for (t1, t2) in tr1.substs.0.iter().zip(tr2.substs.0.iter()) {
+        // this is very bad / hacky 'unification' logic, just enough to make the simple tests pass
+        match (t1, t2) {
+            (_, Ty::Infer(InferTy::TypeVar(_))) | (_, Ty::Unknown) | (_, Ty::Param { .. }) => {
+                // type variable (or similar) in the impl, we just assume it works
+            }
+            (Ty::Infer(InferTy::TypeVar(v1)), _) => {
+                // type variable in the query and fixed type in the impl, record its value
+                solution_substs.resize_with(v1.0 as usize + 1, || Ty::Unknown);
+                solution_substs[v1.0 as usize] = t2.clone();
+            }
+            _ => {
+                // check that they're equal (actually we'd have to recurse etc.)
+                if t1 != t2 {
+                    return None;
+                }
+            }
+        }
+    }
+    Some(Solution::Unique(solution_substs.into()))
+}
author	Florian Diebold <[email protected]>	2019-03-31 19:02:16 +0100
committer	Florian Diebold <[email protected]>	2019-04-14 10:28:53 +0100
commit	a1ed53a4f183b5826162eb9e998207b92be9c57f (patch)
tree	7c139a7dc38483188653c6d40583cddac9d23192 /crates/ra_hir/src/ty
parent	413c87f155ab6b389b1cc122b5739716acccb476 (diff)