Unnamed repository; edit this file 'description' to name the repository.
Diffstat (limited to 'crates/hir_ty/src/method_resolution.rs')
| -rw-r--r-- | crates/hir_ty/src/method_resolution.rs | 351 |
1 files changed, 125 insertions, 226 deletions
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs index 06c834fbc8..1c939f3d8a 100644 --- a/crates/hir_ty/src/method_resolution.rs +++ b/crates/hir_ty/src/method_resolution.rs @@ -6,7 +6,7 @@ use std::{iter, ops::ControlFlow, sync::Arc}; use arrayvec::ArrayVec; use base_db::{CrateId, Edition}; -use chalk_ir::{cast::Cast, fold::Fold, interner::HasInterner, Mutability, UniverseIndex}; +use chalk_ir::{cast::Cast, Mutability, UniverseIndex}; use hir_def::{ item_scope::ItemScope, lang_item::LangItemTarget, nameres::DefMap, AssocItemId, BlockId, ConstId, FunctionId, GenericDefId, HasModule, ImplId, ItemContainerId, Lookup, ModuleDefId, @@ -18,16 +18,14 @@ use stdx::never; use crate::{ autoderef::{self, AutoderefKind}, - consteval::{self, ConstExt}, db::HirDatabase, from_foreign_def_id, infer::{unify::InferenceTable, Adjust, Adjustment, AutoBorrow, OverloadedDeref, PointerCast}, primitive::{self, FloatTy, IntTy, UintTy}, static_lifetime, utils::all_super_traits, - AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, ForeignDefId, GenericArgData, - InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, TraitRefExt, Ty, TyBuilder, - TyExt, TyKind, + AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, ForeignDefId, InEnvironment, Interner, + Scalar, TraitEnvironment, TraitRefExt, Ty, TyBuilder, TyExt, TyKind, }; /// This is used as a key for indexing impls. @@ -643,11 +641,10 @@ pub fn iterate_method_candidates_dyn( let mut table = InferenceTable::new(db, env.clone()); let ty = table.instantiate_canonical(ty.clone()); let (deref_chain, adj) = autoderef_method_receiver(&mut table, ty); - let deref_chains = stdx::slice_tails(&deref_chain); - let result = deref_chains.zip(adj).try_for_each(|(deref_chain, adj)| { + let result = deref_chain.into_iter().zip(adj).try_for_each(|(receiver_ty, adj)| { iterate_method_candidates_with_autoref( - deref_chain, + &receiver_ty, adj, db, env.clone(), @@ -675,7 +672,7 @@ pub fn iterate_method_candidates_dyn( } fn iterate_method_candidates_with_autoref( - deref_chain: &[Canonical<Ty>], + receiver_ty: &Canonical<Ty>, first_adjustment: ReceiverAdjustments, db: &dyn HirDatabase, env: Arc<TraitEnvironment>, @@ -684,17 +681,9 @@ fn iterate_method_candidates_with_autoref( name: Option<&Name>, mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, ) -> ControlFlow<()> { - let (receiver_ty, rest) = match deref_chain.split_first() { - Some((rec, rest)) => (rec, rest), - None => { - never!("received empty deref-chain"); - return ControlFlow::Break(()); - } - }; iterate_method_candidates_by_receiver( receiver_ty, first_adjustment.clone(), - rest, db, env.clone(), traits_in_scope, @@ -712,7 +701,6 @@ fn iterate_method_candidates_with_autoref( iterate_method_candidates_by_receiver( &refed, first_adjustment.with_autoref(Mutability::Not), - deref_chain, db, env.clone(), traits_in_scope, @@ -730,7 +718,6 @@ fn iterate_method_candidates_with_autoref( iterate_method_candidates_by_receiver( &ref_muted, first_adjustment.with_autoref(Mutability::Mut), - deref_chain, db, env, traits_in_scope, @@ -743,7 +730,6 @@ fn iterate_method_candidates_with_autoref( fn iterate_method_candidates_by_receiver( receiver_ty: &Canonical<Ty>, receiver_adjustments: ReceiverAdjustments, - rest_of_deref_chain: &[Canonical<Ty>], db: &dyn HirDatabase, env: Arc<TraitEnvironment>, traits_in_scope: &FxHashSet<TraitId>, @@ -751,30 +737,35 @@ fn iterate_method_candidates_by_receiver( name: Option<&Name>, mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, ) -> ControlFlow<()> { + let mut table = InferenceTable::new(db, env); + let receiver_ty = table.instantiate_canonical(receiver_ty.clone()); + let snapshot = table.snapshot(); // 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 iter::once(receiver_ty).chain(rest_of_deref_chain) { + let mut autoderef = autoderef::Autoderef::new(&mut table, receiver_ty.clone()); + while let Some((self_ty, _)) = autoderef.next() { iterate_inherent_methods( - self_ty, - db, - env.clone(), + &self_ty, + &mut autoderef.table, name, - Some(receiver_ty), + Some(&receiver_ty), Some(receiver_adjustments.clone()), visible_from_module, &mut callback, )? } - for self_ty in iter::once(receiver_ty).chain(rest_of_deref_chain) { + table.rollback_to(snapshot); + + let mut autoderef = autoderef::Autoderef::new(&mut table, receiver_ty.clone()); + while let Some((self_ty, _)) = autoderef.next() { iterate_trait_method_candidates( - self_ty, - db, - env.clone(), + &self_ty, + &mut autoderef.table, traits_in_scope, name, - Some(receiver_ty), + Some(&receiver_ty), Some(receiver_adjustments.clone()), &mut callback, )? @@ -792,43 +783,55 @@ fn iterate_method_candidates_for_self_ty( name: Option<&Name>, mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, ) -> ControlFlow<()> { + let mut table = InferenceTable::new(db, env); + let self_ty = table.instantiate_canonical(self_ty.clone()); iterate_inherent_methods( - self_ty, - db, - env.clone(), + &self_ty, + &mut table, name, None, None, visible_from_module, &mut callback, )?; - iterate_trait_method_candidates(self_ty, db, env, traits_in_scope, name, None, None, callback) + iterate_trait_method_candidates( + &self_ty, + &mut table, + traits_in_scope, + name, + None, + None, + callback, + ) } fn iterate_trait_method_candidates( - self_ty: &Canonical<Ty>, - db: &dyn HirDatabase, - env: Arc<TraitEnvironment>, + self_ty: &Ty, + table: &mut InferenceTable, traits_in_scope: &FxHashSet<TraitId>, name: Option<&Name>, - receiver_ty: Option<&Canonical<Ty>>, + receiver_ty: Option<&Ty>, receiver_adjustments: Option<ReceiverAdjustments>, callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, ) -> ControlFlow<()> { - let self_is_array = matches!(self_ty.value.kind(Interner), chalk_ir::TyKind::Array(..)); + let db = table.db; + let env = table.trait_env.clone(); + let self_is_array = matches!(self_ty.kind(Interner), chalk_ir::TyKind::Array(..)); // if ty is `dyn Trait`, the trait doesn't need to be in scope let inherent_trait = - self_ty.value.dyn_trait().into_iter().flat_map(|t| all_super_traits(db.upcast(), t)); - let env_traits = matches!(self_ty.value.kind(Interner), TyKind::Placeholder(_)) + self_ty.dyn_trait().into_iter().flat_map(|t| all_super_traits(db.upcast(), t)); + let env_traits = matches!(self_ty.kind(Interner), TyKind::Placeholder(_)) // if we have `T: Trait` in the param env, the trait doesn't need to be in scope .then(|| { - env.traits_in_scope_from_clauses(self_ty.value.clone()) + env.traits_in_scope_from_clauses(self_ty.clone()) .flat_map(|t| all_super_traits(db.upcast(), t)) }) .into_iter() .flatten(); let traits = inherent_trait.chain(env_traits).chain(traits_in_scope.iter().copied()); + let canonical_self_ty = table.canonicalize(self_ty.clone()).value; + 'traits: for t in traits { let data = db.trait_data(t); @@ -852,11 +855,11 @@ fn iterate_trait_method_candidates( for &(_, item) in data.items.iter() { // Don't pass a `visible_from_module` down to `is_valid_candidate`, // since only inherent methods should be included into visibility checking. - if !is_valid_candidate(db, env.clone(), name, receiver_ty, item, self_ty, None) { + if !is_valid_candidate(table, name, receiver_ty, item, self_ty, None) { continue; } if !known_implemented { - let goal = generic_implements_goal(db, env.clone(), t, self_ty); + let goal = generic_implements_goal(db, env.clone(), t, &canonical_self_ty); if db.trait_solve(env.krate, goal.cast(Interner)).is_none() { continue 'traits; } @@ -868,40 +871,18 @@ fn iterate_trait_method_candidates( ControlFlow::Continue(()) } -fn filter_inherent_impls_for_self_ty<'i>( - impls: &'i InherentImpls, - self_ty: &Ty, -) -> impl Iterator<Item = &'i ImplId> { - // inherent methods on arrays are fingerprinted as [T; {unknown}], so we must also consider them when - // resolving a method call on an array with a known len - let array_impls = { - match self_ty.kind(Interner) { - TyKind::Array(parameters, array_len) if !array_len.is_unknown() => { - let unknown_array_len_ty = - TyKind::Array(parameters.clone(), consteval::usize_const(None)); - - Some(impls.for_self_ty(&unknown_array_len_ty.intern(Interner))) - } - _ => None, - } - } - .into_iter() - .flatten(); - - impls.for_self_ty(self_ty).iter().chain(array_impls) -} - fn iterate_inherent_methods( - self_ty: &Canonical<Ty>, - db: &dyn HirDatabase, - env: Arc<TraitEnvironment>, + self_ty: &Ty, + table: &mut InferenceTable, name: Option<&Name>, - receiver_ty: Option<&Canonical<Ty>>, + receiver_ty: Option<&Ty>, receiver_adjustments: Option<ReceiverAdjustments>, visible_from_module: VisibleFromModule, callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, ) -> ControlFlow<()> { - let def_crates = match def_crates(db, &self_ty.value, env.krate) { + let db = table.db; + let env = table.trait_env.clone(); + let def_crates = match def_crates(db, self_ty, env.krate) { Some(k) => k, None => return ControlFlow::Continue(()), }; @@ -917,8 +898,7 @@ fn iterate_inherent_methods( impls_for_self_ty( &impls, self_ty, - db, - env.clone(), + table, name, receiver_ty, receiver_adjustments.clone(), @@ -933,8 +913,7 @@ fn iterate_inherent_methods( impls_for_self_ty( &impls, self_ty, - db, - env.clone(), + table, name, receiver_ty, receiver_adjustments.clone(), @@ -946,37 +925,20 @@ fn iterate_inherent_methods( fn impls_for_self_ty( impls: &InherentImpls, - self_ty: &Canonical<Ty>, - db: &dyn HirDatabase, - env: Arc<TraitEnvironment>, + self_ty: &Ty, + table: &mut InferenceTable, name: Option<&Name>, - receiver_ty: Option<&Canonical<Ty>>, + receiver_ty: Option<&Ty>, receiver_adjustments: Option<ReceiverAdjustments>, visible_from_module: Option<ModuleId>, callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, ) -> ControlFlow<()> { - let impls_for_self_ty = filter_inherent_impls_for_self_ty(impls, &self_ty.value); + let db = table.db; + let impls_for_self_ty = impls.for_self_ty(self_ty); for &impl_def in impls_for_self_ty { for &item in &db.impl_data(impl_def).items { - if !is_valid_candidate( - db, - env.clone(), - name, - receiver_ty, - item, - self_ty, - visible_from_module, - ) { - continue; - } - // we have to check whether the self type unifies with the type - // that the impl is for. If we have a receiver type, this - // already happens in `is_valid_candidate` above; if not, we - // check it here - if receiver_ty.is_none() - && inherent_impl_substs(db, env.clone(), impl_def, self_ty).is_none() + if !is_valid_candidate(table, name, receiver_ty, item, self_ty, visible_from_module) { - cov_mark::hit!(impl_self_type_match_without_receiver); continue; } callback(receiver_adjustments.clone().unwrap_or_default(), item)?; @@ -1005,37 +967,15 @@ pub fn resolve_indexing_op( None } -fn is_transformed_receiver_ty_equal(transformed_receiver_ty: &Ty, receiver_ty: &Ty) -> bool { - if transformed_receiver_ty == receiver_ty { - return true; - } - - // a transformed receiver may be considered equal (and a valid method call candidate) if it is an array - // with an unknown (i.e. generic) length, and the receiver is an array with the same item type but a known len, - // this allows inherent methods on arrays to be considered valid resolution candidates - match (transformed_receiver_ty.kind(Interner), receiver_ty.kind(Interner)) { - ( - TyKind::Array(transformed_array_ty, transformed_array_len), - TyKind::Array(receiver_array_ty, receiver_array_len), - ) if transformed_array_ty == receiver_array_ty - && transformed_array_len.is_unknown() - && !receiver_array_len.is_unknown() => - { - true - } - _ => false, - } -} - fn is_valid_candidate( - db: &dyn HirDatabase, - env: Arc<TraitEnvironment>, + table: &mut InferenceTable, name: Option<&Name>, - receiver_ty: Option<&Canonical<Ty>>, + receiver_ty: Option<&Ty>, item: AssocItemId, - self_ty: &Canonical<Ty>, + self_ty: &Ty, visible_from_module: Option<ModuleId>, ) -> bool { + let db = table.db; match item { AssocItemId::FunctionId(m) => { let data = db.function_data(m); @@ -1044,123 +984,82 @@ fn is_valid_candidate( return false; } } - if let Some(receiver_ty) = receiver_ty { - if !data.has_self_param() { + table.run_in_snapshot(|table| { + let subst = TyBuilder::subst_for_def(db, m).fill_with_inference_vars(table).build(); + let expected_self_ty = match m.lookup(db.upcast()).container { + ItemContainerId::TraitId(_) => { + subst.at(Interner, 0).assert_ty_ref(Interner).clone() + } + ItemContainerId::ImplId(impl_id) => { + subst.apply(db.impl_self_ty(impl_id).skip_binders().clone(), Interner) + } + // We should only get called for associated items (impl/trait) + ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => { + unreachable!() + } + }; + if !table.unify(&expected_self_ty, &self_ty) { return false; } - let transformed_receiver_ty = match transform_receiver_ty(db, env, m, self_ty) { - Some(ty) => ty, - None => return false, - }; + if let Some(receiver_ty) = receiver_ty { + if !data.has_self_param() { + return false; + } + + let sig = db.callable_item_signature(m.into()); + let expected_receiver = + sig.map(|s| s.params()[0].clone()).substitute(Interner, &subst); + let receiver_matches = table.unify(&receiver_ty, &expected_receiver); + + if !receiver_matches { + return false; + } + } + if let Some(from_module) = visible_from_module { + if !db.function_visibility(m).is_visible_from(db.upcast(), from_module) { + cov_mark::hit!(autoderef_candidate_not_visible); + return false; + } + } - if !is_transformed_receiver_ty_equal(&transformed_receiver_ty, &receiver_ty.value) { + true + }) + } + AssocItemId::ConstId(c) => { + let data = db.const_data(c); + if receiver_ty.is_some() { + return false; + } + if let Some(name) = name { + if data.name.as_ref() != Some(name) { return false; } } if let Some(from_module) = visible_from_module { - if !db.function_visibility(m).is_visible_from(db.upcast(), from_module) { - cov_mark::hit!(autoderef_candidate_not_visible); + if !db.const_visibility(c).is_visible_from(db.upcast(), from_module) { + cov_mark::hit!(const_candidate_not_visible); + return false; + } + } + if let ItemContainerId::ImplId(impl_id) = c.lookup(db.upcast()).container { + let self_ty_matches = table.run_in_snapshot(|table| { + let subst = + TyBuilder::subst_for_def(db, c).fill_with_inference_vars(table).build(); + let expected_self_ty = + subst.apply(db.impl_self_ty(impl_id).skip_binders().clone(), Interner); + table.unify(&expected_self_ty, &self_ty) + }); + if !self_ty_matches { + cov_mark::hit!(const_candidate_self_type_mismatch); return false; } } - true } - AssocItemId::ConstId(c) => { - let data = db.const_data(c); - name.map_or(true, |name| data.name.as_ref() == Some(name)) && receiver_ty.is_none() - } _ => false, } } -pub(crate) fn inherent_impl_substs( - db: &dyn HirDatabase, - env: Arc<TraitEnvironment>, - impl_id: ImplId, - self_ty: &Canonical<Ty>, -) -> Option<Substitution> { - // we create a var for each type parameter of the impl; we need to keep in - // mind here that `self_ty` might have vars of its own - let self_ty_vars = self_ty.binders.len(Interner); - let vars = TyBuilder::subst_for_def(db, impl_id) - .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty_vars) - .build(); - let self_ty_with_vars = db.impl_self_ty(impl_id).substitute(Interner, &vars); - let mut kinds = self_ty.binders.interned().to_vec(); - kinds.extend(vars.iter(Interner).map(|x| { - let kind = match x.data(Interner) { - GenericArgData::Ty(_) => chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General), - GenericArgData::Const(c) => chalk_ir::VariableKind::Const(c.data(Interner).ty.clone()), - GenericArgData::Lifetime(_) => chalk_ir::VariableKind::Lifetime, - }; - chalk_ir::WithKind::new(kind, UniverseIndex::ROOT) - })); - let tys = Canonical { - binders: CanonicalVarKinds::from_iter(Interner, kinds), - value: (self_ty_with_vars, self_ty.value.clone()), - }; - let substs = super::infer::unify(db, env, &tys)?; - // We only want the substs for the vars we added, not the ones from self_ty. - // Also, if any of the vars we added are still in there, we replace them by - // Unknown. I think this can only really happen if self_ty contained - // Unknown, and in that case we want the result to contain Unknown in those - // places again. - let suffix = - Substitution::from_iter(Interner, substs.iter(Interner).skip(self_ty_vars).cloned()); - Some(fallback_bound_vars(suffix, self_ty_vars)) -} - -/// This replaces any 'free' Bound vars in `s` (i.e. those with indices past -/// num_vars_to_keep) by `TyKind::Unknown`. -pub(crate) fn fallback_bound_vars<T: Fold<Interner> + HasInterner<Interner = Interner>>( - s: T, - num_vars_to_keep: usize, -) -> T::Result { - crate::fold_free_vars( - s, - |bound, binders| { - if bound.index >= num_vars_to_keep && bound.debruijn == DebruijnIndex::INNERMOST { - TyKind::Error.intern(Interner) - } else { - bound.shifted_in_from(binders).to_ty(Interner) - } - }, - |ty, bound, binders| { - if bound.index >= num_vars_to_keep && bound.debruijn == DebruijnIndex::INNERMOST { - consteval::usize_const(None) - } else { - bound.shifted_in_from(binders).to_const(Interner, ty) - } - }, - ) -} - -fn transform_receiver_ty( - db: &dyn HirDatabase, - env: Arc<TraitEnvironment>, - function_id: FunctionId, - self_ty: &Canonical<Ty>, -) -> Option<Ty> { - let substs = match function_id.lookup(db.upcast()).container { - ItemContainerId::TraitId(_) => TyBuilder::subst_for_def(db, function_id) - .push(self_ty.value.clone()) - .fill_with_unknown() - .build(), - ItemContainerId::ImplId(impl_id) => { - let impl_substs = inherent_impl_substs(db, env, impl_id, self_ty)?; - TyBuilder::subst_for_def(db, function_id) - .use_parent_substs(&impl_substs) - .fill_with_unknown() - .build() - } - // No receiver - ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => unreachable!(), - }; - let sig = db.callable_item_signature(function_id.into()); - Some(sig.map(|s| s.params()[0].clone()).substitute(Interner, &substs)) -} - pub fn implements_trait( ty: &Canonical<Ty>, db: &dyn HirDatabase, |