From a1ed53a4f183b5826162eb9e998207b92be9c57f Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 31 Mar 2019 20:02:16 +0200 Subject: 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) --- crates/ra_hir/src/ty/infer.rs | 84 ++++++++++++++++++++-- crates/ra_hir/src/ty/lower.rs | 9 ++- crates/ra_hir/src/ty/method_resolution.rs | 47 +++++-------- crates/ra_hir/src/ty/tests.rs | 51 +++++++++++--- crates/ra_hir/src/ty/traits.rs | 112 ++++++++++++++++++++++++++++++ 5 files changed, 260 insertions(+), 43 deletions(-) create mode 100644 crates/ra_hir/src/ty/traits.rs (limited to 'crates/ra_hir/src/ty') 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 { @@ -153,6 +153,7 @@ struct InferenceContext<'a, D: HirDatabase> { body: Arc, resolver: Resolver, var_unification_table: InPlaceUnificationTable, + obligations: Vec, method_resolutions: FxHashMap, field_resolutions: FxHashMap, assoc_resolutions: FxHashMap, @@ -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, 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>, generic_args: &Option, + 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 { - substs.push(Ty::Unknown); + if let Some(parent_generics) = def_generics.and_then(|p| p.parent_params.clone()) { + 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, ) -> Option { 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 { 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 - // - check in rustc whether it does anything smarter than putting variables for everything - let trait_ref = TraitRef { trait_: *t, substs: Substs::single(self.clone()) }; - db.implements(trait_ref) + let trait_ref = + TraitRef { trait_: *t, substs: fresh_substs_for_trait(db, *t, self.clone()) }; + let (trait_ref, _) = super::traits::canonicalize(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} -[110; 114) 'self': &{unknown} +[31; 35) 'self': &Self +[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} -[169; 173) 'self': &{unknown} +[63; 67) 'self': &Self +[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 { + fn method1(&self) -> (T1, T2, T3); + fn method2(&self) -> (T3, T2, T1); +} +struct S1; +impl Trait for S1 {} +struct S2; +impl Trait 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(T) -> S [108; 115) 'S(1u32)': S @@ -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 { + // 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) { + 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 { + 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())) +} -- cgit v1.2.3