From cbf262a1bc72f10dc93a4993da0012d3b0abb56f Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sat, 2 Nov 2019 15:18:26 +0100 Subject: Change order of calls to get method candidate order correct --- crates/ra_hir_ty/src/method_resolution.rs | 152 ++++++++++++++++++++++-------- crates/ra_hir_ty/src/tests.rs | 2 - 2 files changed, 115 insertions(+), 39 deletions(-) (limited to 'crates/ra_hir_ty/src') diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index 2bded3dbd..fbb932a3e 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -176,7 +176,6 @@ pub fn iterate_method_candidates( mode: LookupMode, mut callback: impl FnMut(&Ty, AssocItemId) -> Option, ) -> Option { - let krate = resolver.krate()?; match mode { LookupMode::MethodCall => { // For method calls, rust first does any number of autoderef, and then one @@ -189,57 +188,125 @@ pub fn iterate_method_candidates( // rustc does an autoderef and then autoref again). let environment = TraitEnvironment::lower(db, resolver); let ty = InEnvironment { value: ty.clone(), environment }; - for derefed_ty in autoderef::autoderef(db, resolver.krate(), ty) { - if let Some(result) = - iterate_inherent_methods(&derefed_ty, db, name, mode, krate, &mut callback) - { - return Some(result); - } - if let Some(result) = iterate_trait_method_candidates( - &derefed_ty, + let krate = resolver.krate()?; + + // We have to be careful about the order of operations here. + // Consider the case where we're resolving `x.clone()` where `x: + // &Vec<_>`. This resolves to the clone method with self type + // `Vec<_>`, *not* `&_`. I.e. we need to consider methods where the + // receiver type exactly matches before cases where we have to do + // autoref. But in the autoderef steps, the `&_` self type comes up + // *before* the `Vec<_>` self type. + // + // On the other hand, we don't want to just pick any by-value method + // before any by-autoref method; it's just that we need to consider + // the methods by autoderef order of *receiver types*, not *self + // types*. + + let deref_chain: Vec<_> = autoderef::autoderef(db, Some(krate), ty.clone()).collect(); + for i in 0..deref_chain.len() { + if let Some(result) = iterate_method_candidates_autoref( + &deref_chain[i..], db, resolver, name, - mode, &mut callback, ) { return Some(result); } } + None } LookupMode::Path => { // No autoderef for path lookups - if let Some(result) = - iterate_inherent_methods(&ty, db, name, mode, krate.into(), &mut callback) - { - return Some(result); - } - if let Some(result) = - iterate_trait_method_candidates(&ty, db, resolver, name, mode, &mut callback) - { - return Some(result); - } + iterate_method_candidates_inner(&ty, db, resolver, name, None, &mut callback) + } + } +} + +fn iterate_method_candidates_autoref( + deref_chain: &[Canonical], + db: &impl HirDatabase, + resolver: &Resolver, + name: Option<&Name>, + mut callback: impl FnMut(&Ty, AssocItemId) -> Option, +) -> Option { + if let Some(result) = iterate_method_candidates_by_receiver(&deref_chain[0], &deref_chain[1..], db, resolver, name, &mut callback) { + return Some(result); + } + let refed = Canonical { + num_vars: deref_chain[0].num_vars, + value: Ty::apply_one(TypeCtor::Ref(Mutability::Shared), deref_chain[0].value.clone()), + }; + if let Some(result) = iterate_method_candidates_by_receiver(&refed, deref_chain, db, resolver, name, &mut callback) { + return Some(result); + } + let ref_muted = Canonical { + num_vars: deref_chain[0].num_vars, + value: Ty::apply_one(TypeCtor::Ref(Mutability::Mut), deref_chain[0].value.clone()), + }; + if let Some(result) = iterate_method_candidates_by_receiver(&ref_muted, deref_chain, db, resolver, name, &mut callback) { + return Some(result); + } + None +} + +fn iterate_method_candidates_by_receiver( + receiver_ty: &Canonical, + deref_chain: &[Canonical], + db: &impl HirDatabase, + resolver: &Resolver, + name: Option<&Name>, + mut callback: impl FnMut(&Ty, AssocItemId) -> Option, +) -> Option { + // TODO: do we need to do the whole loop for inherents before traits? + // We're looking for methods with *receiver* type receiver_ty. These could + // be found in any of the derefs of receiver_ty, so we have to go through + // that. + for self_ty in std::iter::once(receiver_ty).chain(deref_chain) { + if let Some(result) = iterate_method_candidates_inner(self_ty, db, resolver, name, Some(receiver_ty), &mut callback) { + return Some(result); } } None } +fn iterate_method_candidates_inner( + self_ty: &Canonical, + db: &impl HirDatabase, + resolver: &Resolver, + name: Option<&Name>, + receiver_ty: Option<&Canonical>, + mut callback: impl FnMut(&Ty, AssocItemId) -> Option, +) -> Option { + let krate = resolver.krate()?; + if let Some(result) = iterate_inherent_methods(self_ty, db, name, receiver_ty, krate, &mut callback) { + return Some(result); + } + if let Some(result) = + iterate_trait_method_candidates(self_ty, db, resolver, name, receiver_ty, &mut callback) + { + return Some(result); + } + None +} + fn iterate_trait_method_candidates( - ty: &Canonical, + self_ty: &Canonical, db: &impl HirDatabase, resolver: &Resolver, name: Option<&Name>, - mode: LookupMode, + receiver_ty: Option<&Canonical>, mut callback: impl FnMut(&Ty, AssocItemId) -> Option, ) -> Option { let krate = resolver.krate()?; // FIXME: maybe put the trait_env behind a query (need to figure out good input parameters for that) let env = TraitEnvironment::lower(db, resolver); // if ty is `impl Trait` or `dyn Trait`, the trait doesn't need to be in scope - let inherent_trait = ty.value.inherent_trait().into_iter(); + let inherent_trait = self_ty.value.inherent_trait().into_iter(); // if we have `T: Trait` in the param env, the trait doesn't need to be in scope let traits_from_env = env - .trait_predicates_for_self_ty(&ty.value) + .trait_predicates_for_self_ty(&self_ty.value) .map(|tr| tr.trait_) .flat_map(|t| all_super_traits(db, t)); let traits = @@ -252,17 +319,17 @@ fn iterate_trait_method_candidates( // iteration let mut known_implemented = false; for (_name, item) in data.items.iter() { - if !is_valid_candidate(db, name, mode, (*item).into()) { + if !is_valid_candidate(db, name, receiver_ty, (*item).into(), self_ty) { continue; } if !known_implemented { - let goal = generic_implements_goal(db, env.clone(), t, ty.clone()); + let goal = generic_implements_goal(db, env.clone(), t, self_ty.clone()); if db.trait_solve(krate.into(), goal).is_none() { continue 'traits; } } known_implemented = true; - if let Some(result) = callback(&ty.value, (*item).into()) { + if let Some(result) = callback(&self_ty.value, (*item).into()) { return Some(result); } } @@ -271,22 +338,22 @@ fn iterate_trait_method_candidates( } fn iterate_inherent_methods( - ty: &Canonical, + self_ty: &Canonical, db: &impl HirDatabase, name: Option<&Name>, - mode: LookupMode, + receiver_ty: Option<&Canonical>, krate: CrateId, mut callback: impl FnMut(&Ty, AssocItemId) -> Option, ) -> Option { - for krate in ty.value.def_crates(db, krate)? { + for krate in self_ty.value.def_crates(db, krate)? { let impls = db.impls_in_crate(krate); - for impl_block in impls.lookup_impl_blocks(&ty.value) { + for impl_block in impls.lookup_impl_blocks(&self_ty.value) { for &item in db.impl_data(impl_block).items.iter() { - if !is_valid_candidate(db, name, mode, item) { + if !is_valid_candidate(db, name, receiver_ty, item, self_ty) { continue; } - if let Some(result) = callback(&ty.value, item.into()) { + if let Some(result) = callback(&self_ty.value, item) { return Some(result); } } @@ -298,18 +365,29 @@ fn iterate_inherent_methods( fn is_valid_candidate( db: &impl HirDatabase, name: Option<&Name>, - mode: LookupMode, + receiver_ty: Option<&Canonical>, item: AssocItemId, + self_ty: &Canonical, ) -> bool { match item { AssocItemId::FunctionId(m) => { let data = db.function_data(m); - name.map_or(true, |name| &data.name == name) - && (data.has_self_param || mode == LookupMode::Path) + if let Some(name) = name { + if &data.name != name { + return false; + } + } + if let Some(receiver_ty) = receiver_ty { + if !data.has_self_param { + return false; + } + // TODO compare receiver ty + } + true } AssocItemId::ConstId(c) => { let data = db.const_data(c); - name.map_or(true, |name| data.name.as_ref() == Some(name)) && (mode == LookupMode::Path) + name.map_or(true, |name| data.name.as_ref() == Some(name)) && receiver_ty.is_none() } _ => false, } diff --git a/crates/ra_hir_ty/src/tests.rs b/crates/ra_hir_ty/src/tests.rs index a3cc5cf95..be8768c62 100644 --- a/crates/ra_hir_ty/src/tests.rs +++ b/crates/ra_hir_ty/src/tests.rs @@ -3433,7 +3433,6 @@ pub fn baz() -> usize { 31usize } assert_eq!("(i32, usize)", type_at_pos(&db, pos)); } -#[ignore] #[test] fn method_resolution_trait_before_autoref() { let t = type_at( @@ -3449,7 +3448,6 @@ fn test() { S.foo()<|>; } assert_eq!(t, "u128"); } -#[ignore] #[test] fn method_resolution_by_value_before_autoref() { let t = type_at( -- cgit v1.2.3 From 599dab59824b164b1c24e2e51adeae1ac1307964 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 1 Dec 2019 20:30:28 +0100 Subject: Extract unification code to unify module --- crates/ra_hir_ty/src/infer.rs | 255 +++----------------------------- crates/ra_hir_ty/src/infer/coerce.rs | 10 +- crates/ra_hir_ty/src/infer/expr.rs | 30 ++-- crates/ra_hir_ty/src/infer/pat.rs | 4 +- crates/ra_hir_ty/src/infer/path.rs | 4 +- crates/ra_hir_ty/src/infer/unify.rs | 272 ++++++++++++++++++++++++++++++++++- 6 files changed, 312 insertions(+), 263 deletions(-) (limited to 'crates/ra_hir_ty/src') diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs index fe259371f..81afbd2b4 100644 --- a/crates/ra_hir_ty/src/infer.rs +++ b/crates/ra_hir_ty/src/infer.rs @@ -18,7 +18,6 @@ use std::mem; use std::ops::Index; use std::sync::Arc; -use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; use rustc_hash::FxHashMap; use hir_def::{ @@ -33,12 +32,11 @@ use hir_def::{ use hir_expand::{diagnostics::DiagnosticSink, name}; use ra_arena::map::ArenaMap; use ra_prof::profile; -use test_utils::tested_by; use super::{ primitive::{FloatTy, IntTy}, traits::{Guidance, Obligation, ProjectionPredicate, Solution}, - ApplicationTy, InEnvironment, ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TypeCtor, + ApplicationTy, InEnvironment, ProjectionTy, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk, Uncertain, }; use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic}; @@ -191,7 +189,7 @@ struct InferenceContext<'a, D: HirDatabase> { owner: DefWithBodyId, body: Arc, resolver: Resolver, - var_unification_table: InPlaceUnificationTable, + table: unify::InferenceTable, trait_env: Arc, obligations: Vec, result: InferenceResult, @@ -209,7 +207,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { fn new(db: &'a D, owner: DefWithBodyId, resolver: Resolver) -> Self { InferenceContext { result: InferenceResult::default(), - var_unification_table: InPlaceUnificationTable::new(), + table: unify::InferenceTable::new(), obligations: Vec::default(), return_ty: Ty::Unknown, // set in collect_fn_signature trait_env: TraitEnvironment::lower(db, &resolver), @@ -224,13 +222,12 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { fn resolve_all(mut self) -> InferenceResult { // FIXME resolve obligations as well (use Guidance if necessary) let mut result = mem::replace(&mut self.result, InferenceResult::default()); - let mut tv_stack = Vec::new(); for ty in result.type_of_expr.values_mut() { - let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown)); + let resolved = self.table.resolve_ty_completely(mem::replace(ty, Ty::Unknown)); *ty = resolved; } for ty in result.type_of_pat.values_mut() { - let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown)); + let resolved = self.table.resolve_ty_completely(mem::replace(ty, Ty::Unknown)); *ty = resolved; } result @@ -275,96 +272,15 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { self.normalize_associated_types_in(ty) } - fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool { - substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth)) - } - - fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { - self.unify_inner(ty1, ty2, 0) - } - - fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { - if depth > 1000 { - // prevent stackoverflows - panic!("infinite recursion in unification"); - } - if ty1 == ty2 { - return true; - } - // try to resolve type vars first - let ty1 = self.resolve_ty_shallow(ty1); - let ty2 = self.resolve_ty_shallow(ty2); - match (&*ty1, &*ty2) { - (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), - } - } - - fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty) -> bool { - match (ty1, ty2) { - (Ty::Unknown, _) | (_, Ty::Unknown) => 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))) - | ( - Ty::Infer(InferTy::MaybeNeverTypeVar(tv1)), - Ty::Infer(InferTy::MaybeNeverTypeVar(tv2)), - ) => { - // both type vars are unknown since we tried to resolve them - self.var_unification_table.union(*tv1, *tv2); - true - } - - // The order of MaybeNeverTypeVar matters here. - // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar. - // Unifying MaybeNeverTypeVar and other concrete type will let the former become it. - (Ty::Infer(InferTy::TypeVar(tv)), other) - | (other, Ty::Infer(InferTy::TypeVar(tv))) - | (Ty::Infer(InferTy::MaybeNeverTypeVar(tv)), other) - | (other, Ty::Infer(InferTy::MaybeNeverTypeVar(tv))) - | (Ty::Infer(InferTy::IntVar(tv)), other @ ty_app!(TypeCtor::Int(_))) - | (other @ ty_app!(TypeCtor::Int(_)), Ty::Infer(InferTy::IntVar(tv))) - | (Ty::Infer(InferTy::FloatVar(tv)), other @ ty_app!(TypeCtor::Float(_))) - | (other @ ty_app!(TypeCtor::Float(_)), Ty::Infer(InferTy::FloatVar(tv))) => { - // the type var is unknown since we tried to resolve it - self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone())); - true - } - - _ => false, - } - } - - fn new_type_var(&mut self) -> Ty { - Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) - } - - fn new_integer_var(&mut self) -> Ty { - Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) - } - - fn new_float_var(&mut self) -> Ty { - Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) - } - - fn new_maybe_never_type_var(&mut self) -> Ty { - Ty::Infer(InferTy::MaybeNeverTypeVar( - self.var_unification_table.new_key(TypeVarValue::Unknown), - )) - } - /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it. fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty { match ty { - Ty::Unknown => self.new_type_var(), + Ty::Unknown => self.table.new_type_var(), Ty::Apply(ApplicationTy { ctor: TypeCtor::Int(Uncertain::Unknown), .. }) => { - self.new_integer_var() + self.table.new_integer_var() } Ty::Apply(ApplicationTy { ctor: TypeCtor::Float(Uncertain::Unknown), .. }) => { - self.new_float_var() + self.table.new_float_var() } _ => ty, } @@ -402,64 +318,22 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { } } + fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { + self.table.unify(ty1, ty2) + } + /// 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 { + fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty { self.resolve_obligations_as_possible(); - ty.fold(&mut |ty| match ty { - Ty::Infer(tv) => { - let inner = tv.to_inner(); - if tv_stack.contains(&inner) { - tested_by!(type_var_cycles_resolve_as_possible); - // recursive type - return tv.fallback_value(); - } - if let Some(known_ty) = - self.var_unification_table.inlined_probe_value(inner).known() - { - // known_ty may contain other variables that are known by now - tv_stack.push(inner); - let result = self.resolve_ty_as_possible(tv_stack, known_ty.clone()); - tv_stack.pop(); - result - } else { - ty - } - } - _ => ty, - }) + self.table.resolve_ty_as_possible(ty) } - /// If `ty` is a type variable with known type, returns that type; - /// otherwise, return ty. fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> { - let mut ty = Cow::Borrowed(ty); - // The type variable could resolve to a int/float variable. Hence try - // resolving up to three times; each type of variable shouldn't occur - // more than once - for i in 0..3 { - if i > 0 { - tested_by!(type_var_resolves_to_int_var); - } - match &*ty { - Ty::Infer(tv) => { - let inner = tv.to_inner(); - match self.var_unification_table.inlined_probe_value(inner).known() { - Some(known_ty) => { - // The known_ty can't be a type var itself - ty = Cow::Owned(known_ty.clone()); - } - _ => return ty, - } - } - _ => return ty, - } - } - log::error!("Inference variable still not resolved: {:?}", ty); - ty + self.table.resolve_ty_shallow(ty) } /// Recurses through the given type, normalizing associated types mentioned @@ -469,7 +343,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { /// call). `make_ty` handles this already, but e.g. for field types we need /// to do it as well. fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty { - let ty = self.resolve_ty_as_possible(&mut vec![], ty); + let ty = self.resolve_ty_as_possible(ty); ty.fold(&mut |ty| match ty { Ty::Projection(proj_ty) => self.normalize_projection_ty(proj_ty), _ => ty, @@ -477,40 +351,13 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { } fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty { - let var = self.new_type_var(); + let var = self.table.new_type_var(); let predicate = ProjectionPredicate { projection_ty: proj_ty, ty: var.clone() }; let obligation = Obligation::Projection(predicate); self.obligations.push(obligation); var } - /// Resolves the type completely; type variables without known type are - /// replaced by Ty::Unknown. - fn resolve_ty_completely(&mut self, tv_stack: &mut Vec, ty: Ty) -> Ty { - ty.fold(&mut |ty| match ty { - Ty::Infer(tv) => { - let inner = tv.to_inner(); - if tv_stack.contains(&inner) { - tested_by!(type_var_cycles_resolve_completely); - // recursive type - return tv.fallback_value(); - } - if let Some(known_ty) = - self.var_unification_table.inlined_probe_value(inner).known() - { - // known_ty may contain other variables that are known by now - tv_stack.push(inner); - let result = self.resolve_ty_completely(tv_stack, known_ty.clone()); - tv_stack.pop(); - result - } else { - tv.fallback_value() - } - } - _ => ty, - }) - } - fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option) { let path = match path { Some(path) => path, @@ -615,78 +462,20 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { } } -/// The ID of a type variable. -#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] -pub struct TypeVarId(pub(super) u32); - -impl UnifyKey for TypeVarId { - type Value = TypeVarValue; - - fn index(&self) -> u32 { - self.0 - } - - fn from_index(i: u32) -> Self { - TypeVarId(i) - } - - fn tag() -> &'static str { - "TypeVarId" - } -} - -/// The value of a type variable: either we already know the type, or we don't -/// know it yet. -#[derive(Clone, PartialEq, Eq, Debug)] -pub enum TypeVarValue { - Known(Ty), - Unknown, -} - -impl TypeVarValue { - fn known(&self) -> Option<&Ty> { - match self { - TypeVarValue::Known(ty) => Some(ty), - TypeVarValue::Unknown => None, - } - } -} - -impl UnifyValue for TypeVarValue { - type Error = NoError; - - fn unify_values(value1: &Self, value2: &Self) -> Result { - match (value1, value2) { - // We should never equate two type variables, both of which have - // known types. Instead, we recursively equate those types. - (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!( - "equating two type variables, both of which have known types: {:?} and {:?}", - t1, t2 - ), - - // If one side is known, prefer that one. - (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()), - (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()), - - (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown), - } - } -} - /// The kinds of placeholders we need during type inference. There's separate /// values for general types, and for integer and float variables. The latter /// two are used for inference of literal values (e.g. `100` could be one of /// several integer types). #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] pub enum InferTy { - TypeVar(TypeVarId), - IntVar(TypeVarId), - FloatVar(TypeVarId), - MaybeNeverTypeVar(TypeVarId), + TypeVar(unify::TypeVarId), + IntVar(unify::TypeVarId), + FloatVar(unify::TypeVarId), + MaybeNeverTypeVar(unify::TypeVarId), } impl InferTy { - fn to_inner(self) -> TypeVarId { + fn to_inner(self) -> unify::TypeVarId { match self { InferTy::TypeVar(ty) | InferTy::IntVar(ty) diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs index 064993d34..9bfc701cd 100644 --- a/crates/ra_hir_ty/src/infer/coerce.rs +++ b/crates/ra_hir_ty/src/infer/coerce.rs @@ -10,7 +10,7 @@ use test_utils::tested_by; use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk}; -use super::{InEnvironment, InferTy, InferenceContext, TypeVarValue}; +use super::{InEnvironment, InferTy, InferenceContext, unify::TypeVarValue}; impl<'a, D: HirDatabase> InferenceContext<'a, D> { /// Unify two types, but may coerce the first one to the second one @@ -85,8 +85,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { match (&from_ty, to_ty) { // Never type will make type variable to fallback to Never Type instead of Unknown. (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => { - let var = self.new_maybe_never_type_var(); - self.var_unification_table.union_value(*tv, TypeVarValue::Known(var)); + let var = self.table.new_maybe_never_type_var(); + self.table.var_unification_table.union_value(*tv, TypeVarValue::Known(var)); return true; } (ty_app!(TypeCtor::Never), _) => return true, @@ -94,7 +94,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { // Trivial cases, this should go after `never` check to // avoid infer result type to be never _ => { - if self.unify_inner_trivial(&from_ty, &to_ty) { + if self.table.unify_inner_trivial(&from_ty, &to_ty) { return true; } } @@ -330,7 +330,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { // Stop when constructor matches. (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => { // It will not recurse to `coerce`. - return self.unify_substs(st1, st2, 0); + return self.table.unify_substs(st1, st2, 0); } _ => {} } diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs index 4014f4732..1e78f6efd 100644 --- a/crates/ra_hir_ty/src/infer/expr.rs +++ b/crates/ra_hir_ty/src/infer/expr.rs @@ -32,7 +32,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() }, ); } - let ty = self.resolve_ty_as_possible(&mut vec![], ty); + let ty = self.resolve_ty_as_possible(ty); ty } @@ -53,7 +53,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { expected.ty.clone() }; - self.resolve_ty_as_possible(&mut vec![], ty) + self.resolve_ty_as_possible(ty) } fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty { @@ -94,7 +94,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { let pat_ty = match self.resolve_into_iter_item() { Some(into_iter_item_alias) => { - let pat_ty = self.new_type_var(); + let pat_ty = self.table.new_type_var(); let projection = ProjectionPredicate { ty: pat_ty.clone(), projection_ty: ProjectionTy { @@ -103,7 +103,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { }, }; self.obligations.push(Obligation::Projection(projection)); - self.resolve_ty_as_possible(&mut vec![], pat_ty) + self.resolve_ty_as_possible(pat_ty) } None => Ty::Unknown, }; @@ -128,7 +128,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { } // add return type - let ret_ty = self.new_type_var(); + let ret_ty = self.table.new_type_var(); sig_tys.push(ret_ty.clone()); let sig_ty = Ty::apply( TypeCtor::FnPtr { num_args: sig_tys.len() as u16 - 1 }, @@ -167,7 +167,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { Expr::Match { expr, arms } => { let input_ty = self.infer_expr(*expr, &Expectation::none()); - let mut result_ty = self.new_maybe_never_type_var(); + let mut result_ty = self.table.new_maybe_never_type_var(); for arm in arms { for &pat in &arm.pats { @@ -283,7 +283,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { let inner_ty = self.infer_expr(*expr, &Expectation::none()); let ty = match self.resolve_future_future_output() { Some(future_future_output_alias) => { - let ty = self.new_type_var(); + let ty = self.table.new_type_var(); let projection = ProjectionPredicate { ty: ty.clone(), projection_ty: ProjectionTy { @@ -292,7 +292,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { }, }; self.obligations.push(Obligation::Projection(projection)); - self.resolve_ty_as_possible(&mut vec![], ty) + self.resolve_ty_as_possible(ty) } None => Ty::Unknown, }; @@ -302,7 +302,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { let inner_ty = self.infer_expr(*expr, &Expectation::none()); let ty = match self.resolve_ops_try_ok() { Some(ops_try_ok_alias) => { - let ty = self.new_type_var(); + let ty = self.table.new_type_var(); let projection = ProjectionPredicate { ty: ty.clone(), projection_ty: ProjectionTy { @@ -311,7 +311,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { }, }; self.obligations.push(Obligation::Projection(projection)); - self.resolve_ty_as_possible(&mut vec![], ty) + self.resolve_ty_as_possible(ty) } None => Ty::Unknown, }; @@ -465,10 +465,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { ty_app!(TypeCtor::Tuple { .. }, st) => st .iter() .cloned() - .chain(repeat_with(|| self.new_type_var())) + .chain(repeat_with(|| self.table.new_type_var())) .take(exprs.len()) .collect::>(), - _ => (0..exprs.len()).map(|_| self.new_type_var()).collect(), + _ => (0..exprs.len()).map(|_| self.table.new_type_var()).collect(), }; for (expr, ty) in exprs.iter().zip(tys.iter_mut()) { @@ -482,7 +482,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { ty_app!(TypeCtor::Array, st) | ty_app!(TypeCtor::Slice, st) => { st.as_single().clone() } - _ => self.new_type_var(), + _ => self.table.new_type_var(), }; match array { @@ -524,7 +524,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { }; // use a new type variable if we got Ty::Unknown here let ty = self.insert_type_vars_shallow(ty); - let ty = self.resolve_ty_as_possible(&mut vec![], ty); + let ty = self.resolve_ty_as_possible(ty); self.write_expr_ty(tgt_expr, ty.clone()); ty } @@ -553,7 +553,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { } } - let ty = self.resolve_ty_as_possible(&mut vec![], ty); + let ty = self.resolve_ty_as_possible(ty); self.infer_pat(*pat, &ty, BindingMode::default()); } Statement::Expr(expr) => { diff --git a/crates/ra_hir_ty/src/infer/pat.rs b/crates/ra_hir_ty/src/infer/pat.rs index 1ebb36239..a14662884 100644 --- a/crates/ra_hir_ty/src/infer/pat.rs +++ b/crates/ra_hir_ty/src/infer/pat.rs @@ -170,7 +170,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { } BindingMode::Move => inner_ty.clone(), }; - let bound_ty = self.resolve_ty_as_possible(&mut vec![], bound_ty); + let bound_ty = self.resolve_ty_as_possible(bound_ty); self.write_pat_ty(pat, bound_ty); return inner_ty; } @@ -179,7 +179,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { // use a new type variable if we got Ty::Unknown here let ty = self.insert_type_vars_shallow(ty); self.unify(&ty, expected); - let ty = self.resolve_ty_as_possible(&mut vec![], ty); + let ty = self.resolve_ty_as_possible(ty); self.write_pat_ty(pat, ty.clone()); ty } diff --git a/crates/ra_hir_ty/src/infer/path.rs b/crates/ra_hir_ty/src/infer/path.rs index bbf146418..d0d7646a4 100644 --- a/crates/ra_hir_ty/src/infer/path.rs +++ b/crates/ra_hir_ty/src/infer/path.rs @@ -57,7 +57,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { let typable: ValueTyDefId = match value { ValueNs::LocalBinding(pat) => { let ty = self.result.type_of_pat.get(pat)?.clone(); - let ty = self.resolve_ty_as_possible(&mut vec![], ty); + let ty = self.resolve_ty_as_possible(ty); return Some(ty); } ValueNs::FunctionId(it) => it.into(), @@ -211,7 +211,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { // we're picking this method let trait_substs = Substs::build_for_def(self.db, trait_) .push(ty.clone()) - .fill(std::iter::repeat_with(|| self.new_type_var())) + .fill(std::iter::repeat_with(|| self.table.new_type_var())) .build(); let substs = Substs::build_for_def(self.db, item) .use_parent_substs(&trait_substs) diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs index f3a875678..ff50138f5 100644 --- a/crates/ra_hir_ty/src/infer/unify.rs +++ b/crates/ra_hir_ty/src/infer/unify.rs @@ -1,9 +1,15 @@ //! Unification and canonicalization logic. +use std::borrow::Cow; + +use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; + +use test_utils::tested_by; + use super::{InferenceContext, Obligation}; use crate::{ db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate, - ProjectionTy, Substs, TraitRef, Ty, TypeWalk, + ProjectionTy, Substs, TraitRef, Ty, TypeCtor, TypeWalk, }; impl<'a, D: HirDatabase> InferenceContext<'a, D> { @@ -24,7 +30,7 @@ where /// A stack of type variables that is used to detect recursive types (which /// are an error, but we need to protect against them to avoid stack /// overflows). - var_stack: Vec, + var_stack: Vec, } pub(super) struct Canonicalized { @@ -53,14 +59,14 @@ where return tv.fallback_value(); } if let Some(known_ty) = - self.ctx.var_unification_table.inlined_probe_value(inner).known() + self.ctx.table.var_unification_table.inlined_probe_value(inner).known() { self.var_stack.push(inner); let result = self.do_canonicalize_ty(known_ty.clone()); self.var_stack.pop(); result } else { - let root = self.ctx.var_unification_table.find(inner); + let root = self.ctx.table.var_unification_table.find(inner); let free_var = match tv { InferTy::TypeVar(_) => InferTy::TypeVar(root), InferTy::IntVar(_) => InferTy::IntVar(root), @@ -153,10 +159,264 @@ impl Canonicalized { solution: Canonical>, ) { // the solution may contain new variables, which we need to convert to new inference vars - let new_vars = Substs((0..solution.num_vars).map(|_| ctx.new_type_var()).collect()); + let new_vars = Substs((0..solution.num_vars).map(|_| ctx.table.new_type_var()).collect()); for (i, ty) in solution.value.into_iter().enumerate() { let var = self.free_vars[i]; - ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars)); + ctx.table.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars)); + } + } +} + +pub fn unify(ty1: Canonical<&Ty>, ty2: &Ty) -> Substs { + let mut table = InferenceTable::new(); + let vars = Substs::builder(ty1.num_vars) + .fill(std::iter::repeat_with(|| table.new_type_var())).build(); + let ty_with_vars = ty1.value.clone().subst_bound_vars(&vars); + table.unify(&ty_with_vars, ty2); + Substs::builder(ty1.num_vars).fill(vars.iter().map(|v| table.resolve_ty_completely(v.clone()))).build() +} + +#[derive(Clone, Debug)] +pub(crate) struct InferenceTable { + pub(super) var_unification_table: InPlaceUnificationTable, +} + +impl InferenceTable { + pub fn new() -> Self { + InferenceTable { + var_unification_table: InPlaceUnificationTable::new(), + } + } + + pub fn new_type_var(&mut self) -> Ty { + Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) + } + + pub fn new_integer_var(&mut self) -> Ty { + Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) + } + + pub fn new_float_var(&mut self) -> Ty { + Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) + } + + pub fn new_maybe_never_type_var(&mut self) -> Ty { + Ty::Infer(InferTy::MaybeNeverTypeVar( + self.var_unification_table.new_key(TypeVarValue::Unknown), + )) + } + + pub fn resolve_ty_completely(&mut self, ty: Ty) -> Ty { + self.resolve_ty_completely_inner(&mut Vec::new(), ty) + } + + pub fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty { + self.resolve_ty_as_possible_inner(&mut Vec::new(), ty) + } + + pub fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { + self.unify_inner(ty1, ty2, 0) + } + + pub fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool { + substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth)) + } + + fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { + if depth > 1000 { + // prevent stackoverflows + panic!("infinite recursion in unification"); + } + if ty1 == ty2 { + return true; + } + // try to resolve type vars first + let ty1 = self.resolve_ty_shallow(ty1); + let ty2 = self.resolve_ty_shallow(ty2); + match (&*ty1, &*ty2) { + (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), + } + } + + pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty) -> bool { + match (ty1, ty2) { + (Ty::Unknown, _) | (_, Ty::Unknown) => 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))) + | ( + Ty::Infer(InferTy::MaybeNeverTypeVar(tv1)), + Ty::Infer(InferTy::MaybeNeverTypeVar(tv2)), + ) => { + // both type vars are unknown since we tried to resolve them + self.var_unification_table.union(*tv1, *tv2); + true + } + + // The order of MaybeNeverTypeVar matters here. + // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar. + // Unifying MaybeNeverTypeVar and other concrete type will let the former become it. + (Ty::Infer(InferTy::TypeVar(tv)), other) + | (other, Ty::Infer(InferTy::TypeVar(tv))) + | (Ty::Infer(InferTy::MaybeNeverTypeVar(tv)), other) + | (other, Ty::Infer(InferTy::MaybeNeverTypeVar(tv))) + | (Ty::Infer(InferTy::IntVar(tv)), other @ ty_app!(TypeCtor::Int(_))) + | (other @ ty_app!(TypeCtor::Int(_)), Ty::Infer(InferTy::IntVar(tv))) + | (Ty::Infer(InferTy::FloatVar(tv)), other @ ty_app!(TypeCtor::Float(_))) + | (other @ ty_app!(TypeCtor::Float(_)), Ty::Infer(InferTy::FloatVar(tv))) => { + // the type var is unknown since we tried to resolve it + self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone())); + true + } + + _ => 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> { + let mut ty = Cow::Borrowed(ty); + // The type variable could resolve to a int/float variable. Hence try + // resolving up to three times; each type of variable shouldn't occur + // more than once + for i in 0..3 { + if i > 0 { + tested_by!(type_var_resolves_to_int_var); + } + match &*ty { + Ty::Infer(tv) => { + let inner = tv.to_inner(); + match self.var_unification_table.inlined_probe_value(inner).known() { + Some(known_ty) => { + // The known_ty can't be a type var itself + ty = Cow::Owned(known_ty.clone()); + } + _ => return ty, + } + } + _ => return ty, + } + } + log::error!("Inference variable still not resolved: {:?}", ty); + ty + } + + /// 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_inner(&mut self, tv_stack: &mut Vec, ty: Ty) -> Ty { + ty.fold(&mut |ty| match ty { + Ty::Infer(tv) => { + let inner = tv.to_inner(); + if tv_stack.contains(&inner) { + tested_by!(type_var_cycles_resolve_as_possible); + // recursive type + return tv.fallback_value(); + } + if let Some(known_ty) = + self.var_unification_table.inlined_probe_value(inner).known() + { + // known_ty may contain other variables that are known by now + tv_stack.push(inner); + let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone()); + tv_stack.pop(); + result + } else { + ty + } + } + _ => ty, + }) + } + + /// Resolves the type completely; type variables without known type are + /// replaced by Ty::Unknown. + fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec, ty: Ty) -> Ty { + ty.fold(&mut |ty| match ty { + Ty::Infer(tv) => { + let inner = tv.to_inner(); + if tv_stack.contains(&inner) { + tested_by!(type_var_cycles_resolve_completely); + // recursive type + return tv.fallback_value(); + } + if let Some(known_ty) = + self.var_unification_table.inlined_probe_value(inner).known() + { + // known_ty may contain other variables that are known by now + tv_stack.push(inner); + let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone()); + tv_stack.pop(); + result + } else { + tv.fallback_value() + } + } + _ => ty, + }) + } +} + +/// The ID of a type variable. +#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] +pub struct TypeVarId(pub(super) u32); + +impl UnifyKey for TypeVarId { + type Value = TypeVarValue; + + fn index(&self) -> u32 { + self.0 + } + + fn from_index(i: u32) -> Self { + TypeVarId(i) + } + + fn tag() -> &'static str { + "TypeVarId" + } +} + +/// The value of a type variable: either we already know the type, or we don't +/// know it yet. +#[derive(Clone, PartialEq, Eq, Debug)] +pub enum TypeVarValue { + Known(Ty), + Unknown, +} + +impl TypeVarValue { + fn known(&self) -> Option<&Ty> { + match self { + TypeVarValue::Known(ty) => Some(ty), + TypeVarValue::Unknown => None, + } + } +} + +impl UnifyValue for TypeVarValue { + type Error = NoError; + + fn unify_values(value1: &Self, value2: &Self) -> Result { + match (value1, value2) { + // We should never equate two type variables, both of which have + // known types. Instead, we recursively equate those types. + (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!( + "equating two type variables, both of which have known types: {:?} and {:?}", + t1, t2 + ), + + // If one side is known, prefer that one. + (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()), + (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()), + + (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown), } } } -- cgit v1.2.3 From 456d52fdfa8525af2a54e76ee5300f0a40ef582a Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 1 Dec 2019 22:14:28 +0100 Subject: Check receiver type properly --- crates/ra_hir_ty/src/infer.rs | 6 ++- crates/ra_hir_ty/src/infer/coerce.rs | 2 +- crates/ra_hir_ty/src/infer/unify.rs | 20 +++++---- crates/ra_hir_ty/src/method_resolution.rs | 71 +++++++++++++++++++++++++++---- 4 files changed, 80 insertions(+), 19 deletions(-) (limited to 'crates/ra_hir_ty/src') diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs index 81afbd2b4..0889a6bf9 100644 --- a/crates/ra_hir_ty/src/infer.rs +++ b/crates/ra_hir_ty/src/infer.rs @@ -36,11 +36,13 @@ use ra_prof::profile; use super::{ primitive::{FloatTy, IntTy}, traits::{Guidance, Obligation, ProjectionPredicate, Solution}, - ApplicationTy, InEnvironment, ProjectionTy, TraitEnvironment, TraitRef, Ty, TypeCtor, - TypeWalk, Uncertain, + ApplicationTy, InEnvironment, ProjectionTy, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk, + Uncertain, }; use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic}; +pub use unify::unify; + macro_rules! ty_app { ($ctor:pat, $param:pat) => { crate::Ty::Apply(crate::ApplicationTy { ctor: $ctor, parameters: $param }) diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs index 9bfc701cd..9daa77cfa 100644 --- a/crates/ra_hir_ty/src/infer/coerce.rs +++ b/crates/ra_hir_ty/src/infer/coerce.rs @@ -10,7 +10,7 @@ use test_utils::tested_by; use crate::{autoderef, db::HirDatabase, Substs, Ty, TypeCtor, TypeWalk}; -use super::{InEnvironment, InferTy, InferenceContext, unify::TypeVarValue}; +use super::{unify::TypeVarValue, InEnvironment, InferTy, InferenceContext}; impl<'a, D: HirDatabase> InferenceContext<'a, D> { /// Unify two types, but may coerce the first one to the second one diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs index ff50138f5..8ed2a6090 100644 --- a/crates/ra_hir_ty/src/infer/unify.rs +++ b/crates/ra_hir_ty/src/infer/unify.rs @@ -167,13 +167,19 @@ impl Canonicalized { } } -pub fn unify(ty1: Canonical<&Ty>, ty2: &Ty) -> Substs { +pub fn unify(ty1: Canonical<&Ty>, ty2: &Ty) -> Option { let mut table = InferenceTable::new(); - let vars = Substs::builder(ty1.num_vars) - .fill(std::iter::repeat_with(|| table.new_type_var())).build(); + let vars = + Substs::builder(ty1.num_vars).fill(std::iter::repeat_with(|| table.new_type_var())).build(); let ty_with_vars = ty1.value.clone().subst_bound_vars(&vars); - table.unify(&ty_with_vars, ty2); - Substs::builder(ty1.num_vars).fill(vars.iter().map(|v| table.resolve_ty_completely(v.clone()))).build() + if !table.unify(&ty_with_vars, ty2) { + return None; + } + Some( + Substs::builder(ty1.num_vars) + .fill(vars.iter().map(|v| table.resolve_ty_completely(v.clone()))) + .build(), + ) } #[derive(Clone, Debug)] @@ -183,9 +189,7 @@ pub(crate) struct InferenceTable { impl InferenceTable { pub fn new() -> Self { - InferenceTable { - var_unification_table: InPlaceUnificationTable::new(), - } + InferenceTable { var_unification_table: InPlaceUnificationTable::new() } } pub fn new_type_var(&mut self) -> Ty { diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index fbb932a3e..97281cf15 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -7,19 +7,20 @@ use std::sync::Arc; use arrayvec::ArrayVec; use hir_def::{ lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AssocItemId, AstItemDef, - FunctionId, HasModule, ImplId, TraitId, + FunctionId, HasModule, ImplId, Lookup, TraitId, }; use hir_expand::name::Name; use ra_db::CrateId; use ra_prof::profile; use rustc_hash::FxHashMap; +use super::Substs; use crate::{ autoderef, db::HirDatabase, primitive::{FloatBitness, Uncertain}, utils::all_super_traits, - Canonical, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor, + Canonical, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk, }; /// This is used as a key for indexing impls. @@ -231,21 +232,42 @@ fn iterate_method_candidates_autoref( name: Option<&Name>, mut callback: impl FnMut(&Ty, AssocItemId) -> Option, ) -> Option { - if let Some(result) = iterate_method_candidates_by_receiver(&deref_chain[0], &deref_chain[1..], db, resolver, name, &mut callback) { + if let Some(result) = iterate_method_candidates_by_receiver( + &deref_chain[0], + &deref_chain[1..], + db, + resolver, + name, + &mut callback, + ) { return Some(result); } let refed = Canonical { num_vars: deref_chain[0].num_vars, value: Ty::apply_one(TypeCtor::Ref(Mutability::Shared), deref_chain[0].value.clone()), }; - if let Some(result) = iterate_method_candidates_by_receiver(&refed, deref_chain, db, resolver, name, &mut callback) { + if let Some(result) = iterate_method_candidates_by_receiver( + &refed, + deref_chain, + db, + resolver, + name, + &mut callback, + ) { return Some(result); } let ref_muted = Canonical { num_vars: deref_chain[0].num_vars, value: Ty::apply_one(TypeCtor::Ref(Mutability::Mut), deref_chain[0].value.clone()), }; - if let Some(result) = iterate_method_candidates_by_receiver(&ref_muted, deref_chain, db, resolver, name, &mut callback) { + if let Some(result) = iterate_method_candidates_by_receiver( + &ref_muted, + deref_chain, + db, + resolver, + name, + &mut callback, + ) { return Some(result); } None @@ -264,7 +286,14 @@ fn iterate_method_candidates_by_receiver( // be found in any of the derefs of receiver_ty, so we have to go through // that. for self_ty in std::iter::once(receiver_ty).chain(deref_chain) { - if let Some(result) = iterate_method_candidates_inner(self_ty, db, resolver, name, Some(receiver_ty), &mut callback) { + if let Some(result) = iterate_method_candidates_inner( + self_ty, + db, + resolver, + name, + Some(receiver_ty), + &mut callback, + ) { return Some(result); } } @@ -280,7 +309,9 @@ fn iterate_method_candidates_inner( mut callback: impl FnMut(&Ty, AssocItemId) -> Option, ) -> Option { let krate = resolver.krate()?; - if let Some(result) = iterate_inherent_methods(self_ty, db, name, receiver_ty, krate, &mut callback) { + if let Some(result) = + iterate_inherent_methods(self_ty, db, name, receiver_ty, krate, &mut callback) + { return Some(result); } if let Some(result) = @@ -381,7 +412,31 @@ fn is_valid_candidate( if !data.has_self_param { return false; } - // TODO compare receiver ty + let substs = match m.lookup(db).container { + hir_def::ContainerId::TraitId(_) => Substs::build_for_def(db, item) + .push(self_ty.value.clone()) + .fill_with_unknown() + .build(), + hir_def::ContainerId::ImplId(impl_id) => { + let vars = + Substs::build_for_def(db, impl_id).fill_with_bound_vars(0).build(); + let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars); + let self_ty_with_vars = + Canonical { num_vars: vars.len(), value: &self_ty_with_vars }; + if let Some(substs) = super::infer::unify(self_ty_with_vars, &self_ty.value) + { + substs + } else { + return false; + } + } + hir_def::ContainerId::ModuleId(_) => unreachable!(), + }; + let sig = db.callable_item_signature(m.into()); + let receiver = sig.params()[0].clone().subst(&substs); + if receiver != receiver_ty.value { + return false; + } } true } -- cgit v1.2.3 From cfa50df33e1ebfa89f7fbdece7454699f858de92 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Mon, 2 Dec 2019 18:12:49 +0100 Subject: Refactor a bit --- crates/ra_hir_ty/src/infer/path.rs | 38 +----------- crates/ra_hir_ty/src/method_resolution.rs | 98 ++++++++++++++++++------------- crates/ra_hir_ty/src/tests.rs | 15 +++++ 3 files changed, 74 insertions(+), 77 deletions(-) (limited to 'crates/ra_hir_ty/src') diff --git a/crates/ra_hir_ty/src/infer/path.rs b/crates/ra_hir_ty/src/infer/path.rs index d0d7646a4..b0024c6e1 100644 --- a/crates/ra_hir_ty/src/infer/path.rs +++ b/crates/ra_hir_ty/src/infer/path.rs @@ -206,7 +206,9 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { AssocItemId::TypeAliasId(_) => unreachable!(), }; let substs = match container { - ContainerId::ImplId(_) => self.find_self_types(&def, ty.clone()), + ContainerId::ImplId(impl_id) => { + method_resolution::inherent_impl_substs(self.db, impl_id, &ty) + } ContainerId::TraitId(trait_) => { // we're picking this method let trait_substs = Substs::build_for_def(self.db, trait_) @@ -231,38 +233,4 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> { }, ) } - - fn find_self_types(&self, def: &ValueNs, actual_def_ty: Ty) -> Option { - if let ValueNs::FunctionId(func) = *def { - // We only do the infer if parent has generic params - let gen = self.db.generic_params(func.into()); - if gen.count_parent_params() == 0 { - return None; - } - - let impl_id = match func.lookup(self.db).container { - ContainerId::ImplId(it) => it, - _ => return None, - }; - let self_ty = self.db.impl_self_ty(impl_id).clone(); - let self_ty_substs = self_ty.substs()?; - let actual_substs = actual_def_ty.substs()?; - - let mut new_substs = vec![Ty::Unknown; gen.count_parent_params()]; - - // The following code *link up* the function actual parma type - // and impl_block type param index - self_ty_substs.iter().zip(actual_substs.iter()).for_each(|(param, pty)| { - if let Ty::Param { idx, .. } = param { - if let Some(s) = new_substs.get_mut(*idx as usize) { - *s = pty.clone(); - } - } - }); - - Some(Substs(new_substs.into())) - } else { - None - } - } } diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index 97281cf15..21efb196a 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -191,13 +191,13 @@ pub fn iterate_method_candidates( let ty = InEnvironment { value: ty.clone(), environment }; let krate = resolver.krate()?; - // We have to be careful about the order of operations here. - // Consider the case where we're resolving `x.clone()` where `x: - // &Vec<_>`. This resolves to the clone method with self type - // `Vec<_>`, *not* `&_`. I.e. we need to consider methods where the - // receiver type exactly matches before cases where we have to do - // autoref. But in the autoderef steps, the `&_` self type comes up - // *before* the `Vec<_>` self type. + // We have to be careful about the order we're looking at candidates + // in here. Consider the case where we're resolving `x.clone()` + // where `x: &Vec<_>`. This resolves to the clone method with self + // type `Vec<_>`, *not* `&_`. I.e. we need to consider methods where + // the receiver type exactly matches before cases where we have to + // do autoref. But in the autoderef steps, the `&_` self type comes + // up *before* the `Vec<_>` self type. // // On the other hand, we don't want to just pick any by-value method // before any by-autoref method; it's just that we need to consider @@ -206,7 +206,7 @@ pub fn iterate_method_candidates( let deref_chain: Vec<_> = autoderef::autoderef(db, Some(krate), ty.clone()).collect(); for i in 0..deref_chain.len() { - if let Some(result) = iterate_method_candidates_autoref( + if let Some(result) = iterate_method_candidates_with_autoref( &deref_chain[i..], db, resolver, @@ -220,12 +220,12 @@ pub fn iterate_method_candidates( } LookupMode::Path => { // No autoderef for path lookups - iterate_method_candidates_inner(&ty, db, resolver, name, None, &mut callback) + iterate_method_candidates_for_self_ty(&ty, db, resolver, name, &mut callback) } } } -fn iterate_method_candidates_autoref( +fn iterate_method_candidates_with_autoref( deref_chain: &[Canonical], db: &impl HirDatabase, resolver: &Resolver, @@ -275,18 +275,25 @@ fn iterate_method_candidates_autoref( fn iterate_method_candidates_by_receiver( receiver_ty: &Canonical, - deref_chain: &[Canonical], + rest_of_deref_chain: &[Canonical], db: &impl HirDatabase, resolver: &Resolver, name: Option<&Name>, mut callback: impl FnMut(&Ty, AssocItemId) -> Option, ) -> Option { - // TODO: do we need to do the whole loop for inherents before traits? // We're looking for methods with *receiver* type receiver_ty. These could // be found in any of the derefs of receiver_ty, so we have to go through // that. - for self_ty in std::iter::once(receiver_ty).chain(deref_chain) { - if let Some(result) = iterate_method_candidates_inner( + let krate = resolver.krate()?; + for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) { + if let Some(result) = + iterate_inherent_methods(self_ty, db, name, Some(receiver_ty), krate, &mut callback) + { + return Some(result); + } + } + for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) { + if let Some(result) = iterate_trait_method_candidates( self_ty, db, resolver, @@ -300,22 +307,19 @@ fn iterate_method_candidates_by_receiver( None } -fn iterate_method_candidates_inner( +fn iterate_method_candidates_for_self_ty( self_ty: &Canonical, db: &impl HirDatabase, resolver: &Resolver, name: Option<&Name>, - receiver_ty: Option<&Canonical>, mut callback: impl FnMut(&Ty, AssocItemId) -> Option, ) -> Option { let krate = resolver.krate()?; - if let Some(result) = - iterate_inherent_methods(self_ty, db, name, receiver_ty, krate, &mut callback) - { + if let Some(result) = iterate_inherent_methods(self_ty, db, name, None, krate, &mut callback) { return Some(result); } if let Some(result) = - iterate_trait_method_candidates(self_ty, db, resolver, name, receiver_ty, &mut callback) + iterate_trait_method_candidates(self_ty, db, resolver, name, None, &mut callback) { return Some(result); } @@ -412,29 +416,11 @@ fn is_valid_candidate( if !data.has_self_param { return false; } - let substs = match m.lookup(db).container { - hir_def::ContainerId::TraitId(_) => Substs::build_for_def(db, item) - .push(self_ty.value.clone()) - .fill_with_unknown() - .build(), - hir_def::ContainerId::ImplId(impl_id) => { - let vars = - Substs::build_for_def(db, impl_id).fill_with_bound_vars(0).build(); - let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars); - let self_ty_with_vars = - Canonical { num_vars: vars.len(), value: &self_ty_with_vars }; - if let Some(substs) = super::infer::unify(self_ty_with_vars, &self_ty.value) - { - substs - } else { - return false; - } - } - hir_def::ContainerId::ModuleId(_) => unreachable!(), + let transformed_receiver_ty = match transform_receiver_ty(db, m, self_ty) { + Some(ty) => ty, + None => return false, }; - let sig = db.callable_item_signature(m.into()); - let receiver = sig.params()[0].clone().subst(&substs); - if receiver != receiver_ty.value { + if transformed_receiver_ty != receiver_ty.value { return false; } } @@ -448,6 +434,34 @@ fn is_valid_candidate( } } +pub(crate) fn inherent_impl_substs( + db: &impl HirDatabase, + impl_id: ImplId, + self_ty: &Ty, +) -> Option { + let vars = Substs::build_for_def(db, impl_id).fill_with_bound_vars(0).build(); + let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars); + let self_ty_with_vars = Canonical { num_vars: vars.len(), value: &self_ty_with_vars }; + super::infer::unify(self_ty_with_vars, self_ty) +} + +fn transform_receiver_ty( + db: &impl HirDatabase, + function_id: FunctionId, + self_ty: &Canonical, +) -> Option { + let substs = match function_id.lookup(db).container { + hir_def::ContainerId::TraitId(_) => Substs::build_for_def(db, function_id) + .push(self_ty.value.clone()) + .fill_with_unknown() + .build(), + hir_def::ContainerId::ImplId(impl_id) => inherent_impl_substs(db, impl_id, &self_ty.value)?, + hir_def::ContainerId::ModuleId(_) => unreachable!(), + }; + let sig = db.callable_item_signature(function_id.into()); + Some(sig.params()[0].clone().subst(&substs)) +} + pub fn implements_trait( ty: &Canonical, db: &impl HirDatabase, diff --git a/crates/ra_hir_ty/src/tests.rs b/crates/ra_hir_ty/src/tests.rs index be8768c62..d28e835c7 100644 --- a/crates/ra_hir_ty/src/tests.rs +++ b/crates/ra_hir_ty/src/tests.rs @@ -3493,6 +3493,21 @@ fn test() { S.foo()<|>; } assert_eq!(t, "i8"); } +#[test] +fn method_resolution_impl_ref_before_trait() { + let t = type_at( + r#" +//- /main.rs +trait Trait { fn foo(self) -> u128; } +struct S; +impl S { fn foo(&self) -> i8 { 0 } } +impl Trait for &S { fn foo(self) -> u128 { 0 } } +fn test() { S.foo()<|>; } +"#, + ); + assert_eq!(t, "i8"); +} + #[test] fn method_resolution_trait_autoderef() { let t = type_at( -- cgit v1.2.3 From a5a07bde049c59059bc4a68b16a49a174d22cf65 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Mon, 2 Dec 2019 19:27:31 +0100 Subject: Add tests for checking the impl self type --- crates/ra_hir_ty/src/tests.rs | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'crates/ra_hir_ty/src') diff --git a/crates/ra_hir_ty/src/tests.rs b/crates/ra_hir_ty/src/tests.rs index d28e835c7..d5b8d10e2 100644 --- a/crates/ra_hir_ty/src/tests.rs +++ b/crates/ra_hir_ty/src/tests.rs @@ -3433,6 +3433,20 @@ pub fn baz() -> usize { 31usize } assert_eq!("(i32, usize)", type_at_pos(&db, pos)); } +#[test] +fn method_resolution_unify_impl_self_type() { + let t = type_at( + r#" +//- /main.rs +struct S; +impl S { fn foo(&self) -> u8 {} } +impl S { fn foo(&self) -> i8 {} } +fn test() { (S::.foo(), S::.foo())<|>; } +"#, + ); + assert_eq!(t, "(u8, i8)"); +} + #[test] fn method_resolution_trait_before_autoref() { let t = type_at( -- cgit v1.2.3 From 18f25acb89304b2eb0a822b7b49b5e66a439ada7 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Tue, 3 Dec 2019 13:58:02 +0100 Subject: Make unify pub(crate) --- crates/ra_hir_ty/src/infer.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'crates/ra_hir_ty/src') diff --git a/crates/ra_hir_ty/src/infer.rs b/crates/ra_hir_ty/src/infer.rs index 0889a6bf9..d16f1eb46 100644 --- a/crates/ra_hir_ty/src/infer.rs +++ b/crates/ra_hir_ty/src/infer.rs @@ -41,7 +41,7 @@ use super::{ }; use crate::{db::HirDatabase, infer::diagnostics::InferenceDiagnostic}; -pub use unify::unify; +pub(crate) use unify::unify; macro_rules! ty_app { ($ctor:pat, $param:pat) => { -- cgit v1.2.3