X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=crates%2Fhir_ty%2Fsrc%2Fmethod_resolution.rs;h=06c834fbc89e1702cea99de5b229a2f0bbe8932c;hb=b301b040f5781a9083348936369a01c37138756f;hp=507742c22a9fc1ca9b044386368cb9f748d9ffa4;hpb=aa1cdc0cce39949389347b5e0a50d80f8f4ade66;p=rust.git diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs index 507742c22a9..06c834fbc89 100644 --- a/crates/hir_ty/src/method_resolution.rs +++ b/crates/hir_ty/src/method_resolution.rs @@ -2,27 +2,32 @@ //! For details about how this works in rustc, see the method lookup page in the //! [rustc guide](https://rust-lang.github.io/rustc-guide/method-lookup.html) //! and the corresponding code mostly in librustc_typeck/check/method/probe.rs. -use std::{iter, sync::Arc}; +use std::{iter, ops::ControlFlow, sync::Arc}; use arrayvec::ArrayVec; use base_db::{CrateId, Edition}; -use chalk_ir::{cast::Cast, Mutability, UniverseIndex}; +use chalk_ir::{cast::Cast, fold::Fold, interner::HasInterner, Mutability, UniverseIndex}; use hir_def::{ - lang_item::LangItemTarget, nameres::DefMap, AssocContainerId, AssocItemId, BlockId, FunctionId, - GenericDefId, HasModule, ImplId, Lookup, ModuleId, TraitId, + item_scope::ItemScope, lang_item::LangItemTarget, nameres::DefMap, AssocItemId, BlockId, + ConstId, FunctionId, GenericDefId, HasModule, ImplId, ItemContainerId, Lookup, ModuleDefId, + ModuleId, TraitId, }; use hir_expand::name::Name; use rustc_hash::{FxHashMap, FxHashSet}; +use stdx::never; use crate::{ - autoderef, + 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, InEnvironment, Interner, - Scalar, Substitution, TraitEnvironment, TraitRefExt, Ty, TyBuilder, TyExt, TyKind, + AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, ForeignDefId, GenericArgData, + InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, TraitRefExt, Ty, TyBuilder, + TyExt, TyKind, }; /// This is used as a key for indexing impls. @@ -51,7 +56,7 @@ impl TyFingerprint { /// an `impl S`, but not `impl &S`. Hence, this will return `None` for /// reference types and such. pub fn for_inherent_impl(ty: &Ty) -> Option { - let fp = match ty.kind(&Interner) { + let fp = match ty.kind(Interner) { TyKind::Str => TyFingerprint::Str, TyKind::Never => TyFingerprint::Never, TyKind::Slice(..) => TyFingerprint::Slice, @@ -68,7 +73,7 @@ pub fn for_inherent_impl(ty: &Ty) -> Option { /// Creates a TyFingerprint for looking up a trait impl. pub fn for_trait_impl(ty: &Ty) -> Option { - let fp = match ty.kind(&Interner) { + let fp = match ty.kind(Interner) { TyKind::Str => TyFingerprint::Str, TyKind::Never => TyFingerprint::Never, TyKind::Slice(..) => TyFingerprint::Slice, @@ -80,11 +85,10 @@ pub fn for_trait_impl(ty: &Ty) -> Option { TyKind::Dyn(_) => ty.dyn_trait().map(TyFingerprint::Dyn)?, TyKind::Ref(_, _, ty) => return TyFingerprint::for_trait_impl(ty), TyKind::Tuple(_, subst) => { - let first_ty = subst.interned().get(0).map(|arg| arg.assert_ty_ref(&Interner)); - if let Some(ty) = first_ty { - return TyFingerprint::for_trait_impl(ty); - } else { - TyFingerprint::Unit + let first_ty = subst.interned().get(0).map(|arg| arg.assert_ty_ref(Interner)); + match first_ty { + Some(ty) => return TyFingerprint::for_trait_impl(ty), + None => TyFingerprint::Unit, } } TyKind::AssociatedType(_, _) @@ -94,7 +98,7 @@ pub fn for_trait_impl(ty: &Ty) -> Option { | TyKind::Generator(..) | TyKind::GeneratorWitness(..) => TyFingerprint::Unnameable, TyKind::Function(fn_ptr) => { - TyFingerprint::Function(fn_ptr.substitution.0.len(&Interner) as u32) + TyFingerprint::Function(fn_ptr.substitution.0.len(Interner) as u32) } TyKind::Alias(_) | TyKind::Placeholder(_) @@ -140,8 +144,9 @@ pub(crate) fn trait_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) - let crate_def_map = db.crate_def_map(krate); impls.collect_def_map(db, &crate_def_map); + impls.shrink_to_fit(); - return Arc::new(impls); + Arc::new(impls) } pub(crate) fn trait_impls_in_block_query( @@ -153,8 +158,30 @@ pub(crate) fn trait_impls_in_block_query( let block_def_map = db.block_def_map(block)?; impls.collect_def_map(db, &block_def_map); + impls.shrink_to_fit(); - return Some(Arc::new(impls)); + Some(Arc::new(impls)) + } + + pub(crate) fn trait_impls_in_deps_query(db: &dyn HirDatabase, krate: CrateId) -> Arc { + let _p = profile::span("trait_impls_in_deps_query"); + let crate_graph = db.crate_graph(); + let mut res = Self { map: FxHashMap::default() }; + + for krate in crate_graph.transitive_deps(krate) { + res.merge(&db.trait_impls_in_crate(krate)); + } + res.shrink_to_fit(); + + Arc::new(res) + } + + fn shrink_to_fit(&mut self) { + self.map.shrink_to_fit(); + self.map.values_mut().for_each(|map| { + map.shrink_to_fit(); + map.values_mut().for_each(Vec::shrink_to_fit); + }); } fn collect_def_map(&mut self, db: &dyn HirDatabase, def_map: &DefMap) { @@ -176,7 +203,7 @@ fn collect_def_map(&mut self, db: &dyn HirDatabase, def_map: &DefMap) { // To better support custom derives, collect impls in all unnamed const items. // const _: () = { ... }; - for konst in module_data.scope.unnamed_consts() { + for konst in collect_unnamed_consts(db, &module_data.scope) { let body = db.body(konst.into()); for (_, block_def_map) in body.blocks(db.upcast()) { self.collect_def_map(db, &block_def_map); @@ -185,18 +212,6 @@ fn collect_def_map(&mut self, db: &dyn HirDatabase, def_map: &DefMap) { } } - pub(crate) fn trait_impls_in_deps_query(db: &dyn HirDatabase, krate: CrateId) -> Arc { - let _p = profile::span("trait_impls_in_deps_query"); - let crate_graph = db.crate_graph(); - let mut res = Self { map: FxHashMap::default() }; - - for krate in crate_graph.transitive_deps(krate) { - res.merge(&db.trait_impls_in_crate(krate)); - } - - Arc::new(res) - } - fn merge(&mut self, other: &Self) { for (trait_, other_map) in &other.map { let map = self.map.entry(*trait_).or_default(); @@ -261,33 +276,52 @@ pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId let mut impls = Self { map: FxHashMap::default() }; let crate_def_map = db.crate_def_map(krate); - collect_def_map(db, &crate_def_map, &mut impls); - - return Arc::new(impls); - - fn collect_def_map(db: &dyn HirDatabase, def_map: &DefMap, impls: &mut InherentImpls) { - for (_module_id, module_data) in def_map.modules() { - for impl_id in module_data.scope.impls() { - let data = db.impl_data(impl_id); - if data.target_trait.is_some() { - continue; - } - - let self_ty = db.impl_self_ty(impl_id); - let fp = TyFingerprint::for_inherent_impl(self_ty.skip_binders()); - if let Some(fp) = fp { - impls.map.entry(fp).or_default().push(impl_id); - } - // `fp` should only be `None` in error cases (either erroneous code or incomplete name resolution) + impls.collect_def_map(db, &crate_def_map); + impls.shrink_to_fit(); + + Arc::new(impls) + } + + pub(crate) fn inherent_impls_in_block_query( + db: &dyn HirDatabase, + block: BlockId, + ) -> Option> { + let mut impls = Self { map: FxHashMap::default() }; + if let Some(block_def_map) = db.block_def_map(block) { + impls.collect_def_map(db, &block_def_map); + impls.shrink_to_fit(); + return Some(Arc::new(impls)); + } + None + } + + fn shrink_to_fit(&mut self) { + self.map.values_mut().for_each(Vec::shrink_to_fit); + self.map.shrink_to_fit(); + } + + fn collect_def_map(&mut self, db: &dyn HirDatabase, def_map: &DefMap) { + for (_module_id, module_data) in def_map.modules() { + for impl_id in module_data.scope.impls() { + let data = db.impl_data(impl_id); + if data.target_trait.is_some() { + continue; } - // To better support custom derives, collect impls in all unnamed const items. - // const _: () = { ... }; - for konst in module_data.scope.unnamed_consts() { - let body = db.body(konst.into()); - for (_, block_def_map) in body.blocks(db.upcast()) { - collect_def_map(db, &block_def_map, impls); - } + let self_ty = db.impl_self_ty(impl_id); + let fp = TyFingerprint::for_inherent_impl(self_ty.skip_binders()); + if let Some(fp) = fp { + self.map.entry(fp).or_default().push(impl_id); + } + // `fp` should only be `None` in error cases (either erroneous code or incomplete name resolution) + } + + // To better support custom derives, collect impls in all unnamed const items. + // const _: () = { ... }; + for konst in collect_unnamed_consts(db, &module_data.scope) { + let body = db.body(konst.into()); + for (_, block_def_map) in body.blocks(db.upcast()) { + self.collect_def_map(db, &block_def_map); } } } @@ -305,6 +339,34 @@ pub fn all_impls(&self) -> impl Iterator + '_ { } } +fn collect_unnamed_consts<'a>( + db: &'a dyn HirDatabase, + scope: &'a ItemScope, +) -> impl Iterator + 'a { + let unnamed_consts = scope.unnamed_consts(); + + // FIXME: Also treat consts named `_DERIVE_*` as unnamed, since synstructure generates those. + // Should be removed once synstructure stops doing that. + let synstructure_hack_consts = scope.values().filter_map(|(item, _)| match item { + ModuleDefId::ConstId(id) => { + let loc = id.lookup(db.upcast()); + let item_tree = loc.id.item_tree(db.upcast()); + if item_tree[loc.id.value] + .name + .as_ref() + .map_or(false, |n| n.to_smol_str().starts_with("_DERIVE_")) + { + Some(id) + } else { + None + } + } + _ => None, + }); + + unnamed_consts.chain(synstructure_hack_consts) +} + pub fn def_crates( db: &dyn HirDatabase, ty: &Ty, @@ -322,9 +384,9 @@ macro_rules! lang_item_crate { }}; } - let mod_to_crate_ids = |module: ModuleId| Some(std::iter::once(module.krate()).collect()); + let mod_to_crate_ids = |module: ModuleId| Some(iter::once(module.krate()).collect()); - let lang_item_targets = match ty.kind(&Interner) { + let lang_item_targets = match ty.kind(Interner) { TyKind::Adt(AdtId(def_id), _) => { return mod_to_crate_ids(def_id.module(db.upcast())); } @@ -369,28 +431,25 @@ macro_rules! lang_item_crate { Some(res) } -/// Look up the method with the given name, returning the actual autoderefed -/// receiver type (but without autoref applied yet). +/// Look up the method with the given name. pub(crate) fn lookup_method( ty: &Canonical, db: &dyn HirDatabase, env: Arc, - krate: CrateId, traits_in_scope: &FxHashSet, - visible_from_module: Option, + visible_from_module: VisibleFromModule, name: &Name, -) -> Option<(Ty, FunctionId)> { +) -> Option<(ReceiverAdjustments, FunctionId)> { iterate_method_candidates( ty, db, env, - krate, traits_in_scope, visible_from_module, Some(name), LookupMode::MethodCall, - |ty, f| match f { - AssocItemId::FunctionId(f) => Some((ty.clone(), f)), + |adjustments, f| match f { + AssocItemId::FunctionId(f) => Some((adjustments, f)), _ => None, }, ) @@ -408,61 +467,165 @@ pub enum LookupMode { Path, } +#[derive(Clone, Copy)] +pub enum VisibleFromModule { + /// Filter for results that are visible from the given module + Filter(ModuleId), + /// Include impls from the given block. + IncludeBlock(BlockId), + /// Do nothing special in regards visibility + None, +} + +impl From> for VisibleFromModule { + fn from(module: Option) -> Self { + match module { + Some(module) => Self::Filter(module), + None => Self::None, + } + } +} + +impl From> for VisibleFromModule { + fn from(block: Option) -> Self { + match block { + Some(block) => Self::IncludeBlock(block), + None => Self::None, + } + } +} + +#[derive(Debug, Clone, Default)] +pub struct ReceiverAdjustments { + autoref: Option, + autoderefs: usize, + unsize_array: bool, +} + +impl ReceiverAdjustments { + pub(crate) fn apply(&self, table: &mut InferenceTable, ty: Ty) -> (Ty, Vec) { + let mut ty = ty; + let mut adjust = Vec::new(); + for _ in 0..self.autoderefs { + match autoderef::autoderef_step(table, ty.clone()) { + None => { + never!("autoderef not possible for {:?}", ty); + ty = TyKind::Error.intern(Interner); + break; + } + Some((kind, new_ty)) => { + ty = new_ty.clone(); + adjust.push(Adjustment { + kind: Adjust::Deref(match kind { + // FIXME should we know the mutability here? + AutoderefKind::Overloaded => Some(OverloadedDeref(Mutability::Not)), + AutoderefKind::Builtin => None, + }), + target: new_ty, + }); + } + } + } + if self.unsize_array { + ty = match ty.kind(Interner) { + TyKind::Array(inner, _) => TyKind::Slice(inner.clone()).intern(Interner), + _ => { + never!("unsize_array with non-array {:?}", ty); + ty + } + }; + // FIXME this is kind of wrong since the unsize needs to happen to a pointer/reference + adjust.push(Adjustment { + kind: Adjust::Pointer(PointerCast::Unsize), + target: ty.clone(), + }); + } + if let Some(m) = self.autoref { + ty = TyKind::Ref(m, static_lifetime(), ty).intern(Interner); + adjust + .push(Adjustment { kind: Adjust::Borrow(AutoBorrow::Ref(m)), target: ty.clone() }); + } + (ty, adjust) + } + + fn with_autoref(&self, m: Mutability) -> ReceiverAdjustments { + Self { autoref: Some(m), ..*self } + } +} + // This would be nicer if it just returned an iterator, but that runs into // lifetime problems, because we need to borrow temp `CrateImplDefs`. // FIXME add a context type here? -pub fn iterate_method_candidates( +pub(crate) fn iterate_method_candidates( ty: &Canonical, db: &dyn HirDatabase, env: Arc, - krate: CrateId, traits_in_scope: &FxHashSet, - visible_from_module: Option, + visible_from_module: VisibleFromModule, name: Option<&Name>, mode: LookupMode, - mut callback: impl FnMut(&Ty, AssocItemId) -> Option, + mut callback: impl FnMut(ReceiverAdjustments, AssocItemId) -> Option, ) -> Option { let mut slot = None; iterate_method_candidates_dyn( ty, db, env, - krate, traits_in_scope, visible_from_module, name, mode, - &mut |ty, item| { + &mut |adj, item| { assert!(slot.is_none()); - slot = callback(ty, item); - slot.is_some() + if let Some(it) = callback(adj, item) { + slot = Some(it); + return ControlFlow::Break(()); + } + ControlFlow::Continue(()) }, ); slot } +pub fn iterate_path_candidates( + ty: &Canonical, + db: &dyn HirDatabase, + env: Arc, + traits_in_scope: &FxHashSet, + visible_from_module: VisibleFromModule, + name: Option<&Name>, + callback: &mut dyn FnMut(AssocItemId) -> ControlFlow<()>, +) -> ControlFlow<()> { + iterate_method_candidates_dyn( + ty, + db, + env, + traits_in_scope, + visible_from_module, + name, + LookupMode::Path, + // the adjustments are not relevant for path lookup + &mut |_, id| callback(id), + ) +} + pub fn iterate_method_candidates_dyn( ty: &Canonical, db: &dyn HirDatabase, env: Arc, - krate: CrateId, traits_in_scope: &FxHashSet, - visible_from_module: Option, + visible_from_module: VisibleFromModule, name: Option<&Name>, mode: LookupMode, - callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool, -) -> bool { + callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, +) -> ControlFlow<()> { match mode { LookupMode::MethodCall => { - // For method calls, rust first does any number of autoderef, and then one - // autoref (i.e. when the method takes &self or &mut self). We just ignore - // the autoref currently -- when we find a method matching the given name, - // we assume it fits. - - // Also note that when we've got a receiver like &S, even if the method we - // find in the end takes &self, we still do the autoderef step (just as - // rustc does an autoderef and then autoref again). - let ty = InEnvironment { goal: ty.clone(), environment: env.env.clone() }; + // For method calls, rust first does any number of autoderef, and + // then one autoref (i.e. when the method takes &self or &mut self). + // Note that when we've got a receiver like &S, even if the method + // we find in the end takes &self, we still do the autoderef step + // (just as rustc does an autoderef and then autoref again). // We have to be careful about the order we're looking at candidates // in here. Consider the case where we're resolving `x.clone()` @@ -477,22 +640,24 @@ pub fn iterate_method_candidates_dyn( // the methods by autoderef order of *receiver types*, not *self // types*. - let deref_chain = autoderef_method_receiver(db, krate, ty); - for i in 0..deref_chain.len() { - if iterate_method_candidates_with_autoref( - &deref_chain[i..], + 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)| { + iterate_method_candidates_with_autoref( + deref_chain, + adj, db, env.clone(), - krate, traits_in_scope, visible_from_module, name, callback, - ) { - return true; - } - } - false + ) + }); + result } LookupMode::Path => { // No autoderef for path lookups @@ -500,7 +665,6 @@ pub fn iterate_method_candidates_dyn( ty, db, env, - krate, traits_in_scope, visible_from_module, name, @@ -512,160 +676,159 @@ pub fn iterate_method_candidates_dyn( fn iterate_method_candidates_with_autoref( deref_chain: &[Canonical], + first_adjustment: ReceiverAdjustments, db: &dyn HirDatabase, env: Arc, - krate: CrateId, traits_in_scope: &FxHashSet, - visible_from_module: Option, + visible_from_module: VisibleFromModule, name: Option<&Name>, - mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool, -) -> bool { - if iterate_method_candidates_by_receiver( - &deref_chain[0], - &deref_chain[1..], + 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(), - krate, traits_in_scope, visible_from_module, name, &mut callback, - ) { - return true; - } + )?; + let refed = Canonical { - binders: deref_chain[0].binders.clone(), - value: TyKind::Ref(Mutability::Not, static_lifetime(), deref_chain[0].value.clone()) - .intern(&Interner), + value: TyKind::Ref(Mutability::Not, static_lifetime(), receiver_ty.value.clone()) + .intern(Interner), + binders: receiver_ty.binders.clone(), }; - if iterate_method_candidates_by_receiver( + + iterate_method_candidates_by_receiver( &refed, + first_adjustment.with_autoref(Mutability::Not), deref_chain, db, env.clone(), - krate, traits_in_scope, visible_from_module, name, &mut callback, - ) { - return true; - } + )?; + let ref_muted = Canonical { - binders: deref_chain[0].binders.clone(), - value: TyKind::Ref(Mutability::Mut, static_lifetime(), deref_chain[0].value.clone()) - .intern(&Interner), + value: TyKind::Ref(Mutability::Mut, static_lifetime(), receiver_ty.value.clone()) + .intern(Interner), + binders: receiver_ty.binders.clone(), }; - if iterate_method_candidates_by_receiver( + + iterate_method_candidates_by_receiver( &ref_muted, + first_adjustment.with_autoref(Mutability::Mut), deref_chain, db, env, - krate, traits_in_scope, visible_from_module, name, &mut callback, - ) { - return true; - } - false + ) } fn iterate_method_candidates_by_receiver( receiver_ty: &Canonical, + receiver_adjustments: ReceiverAdjustments, rest_of_deref_chain: &[Canonical], db: &dyn HirDatabase, env: Arc, - krate: CrateId, traits_in_scope: &FxHashSet, - visible_from_module: Option, + visible_from_module: VisibleFromModule, name: Option<&Name>, - mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool, -) -> bool { + mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, +) -> ControlFlow<()> { // 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(rest_of_deref_chain) { - if iterate_inherent_methods( + for self_ty in iter::once(receiver_ty).chain(rest_of_deref_chain) { + iterate_inherent_methods( self_ty, db, env.clone(), name, Some(receiver_ty), - krate, + Some(receiver_adjustments.clone()), visible_from_module, &mut callback, - ) { - return true; - } + )? } - for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) { - if iterate_trait_method_candidates( + + for self_ty in iter::once(receiver_ty).chain(rest_of_deref_chain) { + iterate_trait_method_candidates( self_ty, db, env.clone(), - krate, traits_in_scope, name, Some(receiver_ty), + Some(receiver_adjustments.clone()), &mut callback, - ) { - return true; - } + )? } - false + + ControlFlow::Continue(()) } fn iterate_method_candidates_for_self_ty( self_ty: &Canonical, db: &dyn HirDatabase, env: Arc, - krate: CrateId, traits_in_scope: &FxHashSet, - visible_from_module: Option, + visible_from_module: VisibleFromModule, name: Option<&Name>, - mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool, -) -> bool { - if iterate_inherent_methods( + mut callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, +) -> ControlFlow<()> { + iterate_inherent_methods( self_ty, db, env.clone(), name, None, - krate, + None, visible_from_module, &mut callback, - ) { - return true; - } - iterate_trait_method_candidates(self_ty, db, env, krate, traits_in_scope, name, None, callback) + )?; + iterate_trait_method_candidates(self_ty, db, env, traits_in_scope, name, None, None, callback) } fn iterate_trait_method_candidates( self_ty: &Canonical, db: &dyn HirDatabase, env: Arc, - krate: CrateId, traits_in_scope: &FxHashSet, name: Option<&Name>, receiver_ty: Option<&Canonical>, - callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool, -) -> bool { - let receiver_is_array = matches!(self_ty.value.kind(&Interner), chalk_ir::TyKind::Array(..)); + receiver_adjustments: Option, + callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, +) -> ControlFlow<()> { + let self_is_array = matches!(self_ty.value.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 = if let TyKind::Placeholder(_) = self_ty.value.kind(&Interner) { + let env_traits = matches!(self_ty.value.kind(Interner), TyKind::Placeholder(_)) // if we have `T: Trait` in the param env, the trait doesn't need to be in scope - env.traits_in_scope_from_clauses(&self_ty.value) - .flat_map(|t| all_super_traits(db.upcast(), t)) - .collect() - } else { - Vec::new() - }; - let traits = - inherent_trait.chain(env_traits.into_iter()).chain(traits_in_scope.iter().copied()); + .then(|| { + env.traits_in_scope_from_clauses(self_ty.value.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()); + 'traits: for t in traits { let data = db.trait_data(t); @@ -674,10 +837,10 @@ fn iterate_trait_method_candidates( // 2021. // This is to make `[a].into_iter()` not break code with the new `IntoIterator` impl for // arrays. - if data.skip_array_during_method_dispatch && receiver_is_array { + if data.skip_array_during_method_dispatch && self_is_array { // FIXME: this should really be using the edition of the method name's span, in case it // comes from a macro - if db.crate_graph()[krate].edition < Edition::Edition2021 { + if db.crate_graph()[env.krate].edition < Edition::Edition2021 { continue; } } @@ -686,26 +849,46 @@ fn iterate_trait_method_candidates( // trait, but if we find out it doesn't, we'll skip the rest of the // iteration let mut known_implemented = false; - for (_name, item) in data.items.iter() { + 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(db, env.clone(), name, receiver_ty, item, self_ty, None) { continue; } if !known_implemented { - let goal = generic_implements_goal(db, env.clone(), t, self_ty.clone()); - if db.trait_solve(krate, goal.cast(&Interner)).is_none() { + let goal = generic_implements_goal(db, env.clone(), t, self_ty); + if db.trait_solve(env.krate, goal.cast(Interner)).is_none() { continue 'traits; } } known_implemented = true; - // FIXME: we shouldn't be ignoring the binders here - if callback(&self_ty.value, *item) { - return true; + callback(receiver_adjustments.clone().unwrap_or_default(), item)?; + } + } + ControlFlow::Continue(()) +} + +fn filter_inherent_impls_for_self_ty<'i>( + impls: &'i InherentImpls, + self_ty: &Ty, +) -> impl Iterator { + // 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, } } - false + .into_iter() + .flatten(); + + impls.for_self_ty(self_ty).iter().chain(array_impls) } fn iterate_inherent_methods( @@ -714,19 +897,67 @@ fn iterate_inherent_methods( env: Arc, name: Option<&Name>, receiver_ty: Option<&Canonical>, - krate: CrateId, - visible_from_module: Option, - callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool, -) -> bool { - let def_crates = match def_crates(db, &self_ty.value, krate) { + receiver_adjustments: Option, + visible_from_module: VisibleFromModule, + callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, +) -> ControlFlow<()> { + let def_crates = match def_crates(db, &self_ty.value, env.krate) { Some(k) => k, - None => return false, + None => return ControlFlow::Continue(()), + }; + + let (module, block) = match visible_from_module { + VisibleFromModule::Filter(module) => (Some(module), module.containing_block()), + VisibleFromModule::IncludeBlock(block) => (None, Some(block)), + VisibleFromModule::None => (None, None), }; + + if let Some(block_id) = block { + if let Some(impls) = db.inherent_impls_in_block(block_id) { + impls_for_self_ty( + &impls, + self_ty, + db, + env.clone(), + name, + receiver_ty, + receiver_adjustments.clone(), + module, + callback, + )?; + } + } + for krate in def_crates { let impls = db.inherent_impls_in_crate(krate); + impls_for_self_ty( + &impls, + self_ty, + db, + env.clone(), + name, + receiver_ty, + receiver_adjustments.clone(), + module, + callback, + )?; + } + return ControlFlow::Continue(()); - for &impl_def in impls.for_self_ty(&self_ty.value) { - for &item in db.impl_data(impl_def).items.iter() { + fn impls_for_self_ty( + impls: &InherentImpls, + self_ty: &Canonical, + db: &dyn HirDatabase, + env: Arc, + name: Option<&Name>, + receiver_ty: Option<&Canonical>, + receiver_adjustments: Option, + visible_from_module: Option, + callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId) -> ControlFlow<()>, + ) -> ControlFlow<()> { + let impls_for_self_ty = filter_inherent_impls_for_self_ty(impls, &self_ty.value); + for &impl_def in impls_for_self_ty { + for &item in &db.impl_data(impl_def).items { if !is_valid_candidate( db, env.clone(), @@ -748,35 +979,54 @@ fn iterate_inherent_methods( cov_mark::hit!(impl_self_type_match_without_receiver); continue; } - let receiver_ty = receiver_ty.map(|x| &x.value).unwrap_or(&self_ty.value); - if callback(receiver_ty, item) { - return true; - } + callback(receiver_adjustments.clone().unwrap_or_default(), item)?; } } + ControlFlow::Continue(()) } - false } -/// Returns the self type for the index trait call. +/// Returns the receiver type for the index trait call. pub fn resolve_indexing_op( db: &dyn HirDatabase, - ty: &Canonical, env: Arc, - krate: CrateId, + ty: Canonical, index_trait: TraitId, -) -> Option> { - let ty = InEnvironment { goal: ty.clone(), environment: env.env.clone() }; - let deref_chain = autoderef_method_receiver(db, krate, ty); - for ty in deref_chain { - let goal = generic_implements_goal(db, env.clone(), index_trait, ty.clone()); - if db.trait_solve(krate, goal.cast(&Interner)).is_some() { - return Some(ty); +) -> Option { + let mut table = InferenceTable::new(db, env.clone()); + let ty = table.instantiate_canonical(ty); + let (deref_chain, adj) = autoderef_method_receiver(&mut table, ty); + for (ty, adj) in deref_chain.into_iter().zip(adj) { + let goal = generic_implements_goal(db, env.clone(), index_trait, &ty); + if db.trait_solve(env.krate, goal.cast(Interner)).is_some() { + return Some(adj); } } 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, @@ -802,7 +1052,8 @@ fn is_valid_candidate( Some(ty) => ty, None => return false, }; - if transformed_receiver_ty != receiver_ty.value { + + if !is_transformed_receiver_ty_equal(&transformed_receiver_ty, &receiver_ty.value) { return false; } } @@ -831,21 +1082,22 @@ pub(crate) fn inherent_impl_substs( ) -> Option { // 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 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 self_ty_with_vars = db.impl_self_ty(impl_id).substitute(Interner, &vars); let mut kinds = self_ty.binders.interned().to_vec(); - kinds.extend( - iter::repeat(chalk_ir::WithKind::new( - chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General), - UniverseIndex::ROOT, - )) - .take(vars.len(&Interner)), - ); + 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), + binders: CanonicalVarKinds::from_iter(Interner, kinds), value: (self_ty_with_vars, self_ty.value.clone()), }; let substs = super::infer::unify(db, env, &tys)?; @@ -855,20 +1107,33 @@ pub(crate) fn inherent_impl_substs( // 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).cloned().skip(self_ty_vars)); + 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`. -fn fallback_bound_vars(s: Substitution, num_vars_to_keep: usize) -> Substitution { - 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) - } - }) +pub(crate) fn fallback_bound_vars + HasInterner>( + 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( @@ -878,32 +1143,32 @@ fn transform_receiver_ty( self_ty: &Canonical, ) -> Option { let substs = match function_id.lookup(db.upcast()).container { - AssocContainerId::TraitId(_) => TyBuilder::subst_for_def(db, function_id) + ItemContainerId::TraitId(_) => TyBuilder::subst_for_def(db, function_id) .push(self_ty.value.clone()) .fill_with_unknown() .build(), - AssocContainerId::ImplId(impl_id) => { + 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() } - AssocContainerId::ModuleId(_) => unreachable!(), + // 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)) + Some(sig.map(|s| s.params()[0].clone()).substitute(Interner, &substs)) } pub fn implements_trait( ty: &Canonical, db: &dyn HirDatabase, env: Arc, - krate: CrateId, trait_: TraitId, ) -> bool { - let goal = generic_implements_goal(db, env, trait_, ty.clone()); - let solution = db.trait_solve(krate, goal.cast(&Interner)); + let goal = generic_implements_goal(db, env.clone(), trait_, ty); + let solution = db.trait_solve(env.krate, goal.cast(Interner)); solution.is_some() } @@ -912,11 +1177,10 @@ pub fn implements_trait_unique( ty: &Canonical, db: &dyn HirDatabase, env: Arc, - krate: CrateId, trait_: TraitId, ) -> bool { - let goal = generic_implements_goal(db, env, trait_, ty.clone()); - let solution = db.trait_solve(krate, goal.cast(&Interner)); + let goal = generic_implements_goal(db, env.clone(), trait_, ty); + let solution = db.trait_solve(env.krate, goal.cast(Interner)); matches!(solution, Some(crate::Solution::Unique(_))) } @@ -927,40 +1191,54 @@ fn generic_implements_goal( db: &dyn HirDatabase, env: Arc, trait_: TraitId, - self_ty: Canonical, + self_ty: &Canonical, ) -> Canonical> { let mut kinds = self_ty.binders.interned().to_vec(); let trait_ref = TyBuilder::trait_ref(db, trait_) - .push(self_ty.value) + .push(self_ty.value.clone()) .fill_with_bound_vars(DebruijnIndex::INNERMOST, kinds.len()) .build(); - kinds.extend( - iter::repeat(chalk_ir::WithKind::new( - chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General), - UniverseIndex::ROOT, - )) - .take(trait_ref.substitution.len(&Interner) - 1), - ); - let obligation = trait_ref.cast(&Interner); + kinds.extend(trait_ref.substitution.iter(Interner).skip(1).map(|x| { + let vk = match x.data(Interner) { + chalk_ir::GenericArgData::Ty(_) => { + chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General) + } + chalk_ir::GenericArgData::Lifetime(_) => chalk_ir::VariableKind::Lifetime, + chalk_ir::GenericArgData::Const(c) => { + chalk_ir::VariableKind::Const(c.data(Interner).ty.clone()) + } + }; + chalk_ir::WithKind::new(vk, UniverseIndex::ROOT) + })); + let obligation = trait_ref.cast(Interner); Canonical { - binders: CanonicalVarKinds::from_iter(&Interner, kinds), + binders: CanonicalVarKinds::from_iter(Interner, kinds), value: InEnvironment::new(&env.env, obligation), } } fn autoderef_method_receiver( - db: &dyn HirDatabase, - krate: CrateId, - ty: InEnvironment>, -) -> Vec> { - let mut deref_chain: Vec<_> = autoderef::autoderef(db, Some(krate), ty).collect(); + table: &mut InferenceTable, + ty: Ty, +) -> (Vec>, Vec) { + let (mut deref_chain, mut adjustments): (Vec<_>, Vec<_>) = (Vec::new(), Vec::new()); + let mut autoderef = autoderef::Autoderef::new(table, ty); + while let Some((ty, derefs)) = autoderef.next() { + deref_chain.push(autoderef.table.canonicalize(ty).value); + adjustments.push(ReceiverAdjustments { + autoref: None, + autoderefs: derefs, + unsize_array: false, + }); + } // As a last step, we can do array unsizing (that's the only unsizing that rustc does for method receivers!) - if let Some(TyKind::Array(parameters, _)) = - deref_chain.last().map(|ty| ty.value.kind(&Interner)) - { - let kinds = deref_chain.last().unwrap().binders.clone(); - let unsized_ty = TyKind::Slice(parameters.clone()).intern(&Interner); - deref_chain.push(Canonical { value: unsized_ty, binders: kinds }) - } - deref_chain + if let (Some((TyKind::Array(parameters, _), binders)), Some(adj)) = ( + deref_chain.last().map(|ty| (ty.value.kind(Interner), ty.binders.clone())), + adjustments.last().cloned(), + ) { + let unsized_ty = TyKind::Slice(parameters.clone()).intern(Interner); + deref_chain.push(Canonical { value: unsized_ty, binders }); + adjustments.push(ReceiverAdjustments { unsize_array: true, ..adj }); + } + (deref_chain, adjustments) }