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 | 2084 |
1 files changed, 553 insertions, 1531 deletions
diff --git a/crates/hir-ty/src/method_resolution.rs b/crates/hir-ty/src/method_resolution.rs index 1e30897362..59299f2c35 100644 --- a/crates/hir-ty/src/method_resolution.rs +++ b/crates/hir-ty/src/method_resolution.rs @@ -2,683 +2,349 @@ //! 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 rustc_hir_analysis/check/method/probe.rs. -use std::ops::ControlFlow; + +mod confirm; +mod probe; + +use either::Either; +use hir_expand::name::Name; +use span::Edition; +use tracing::{debug, instrument}; use base_db::Crate; use hir_def::{ - AdtId, AssocItemId, BlockId, ConstId, FunctionId, HasModule, ImplId, ItemContainerId, Lookup, - ModuleId, TraitId, TypeAliasId, + AssocItemId, BlockId, ConstId, FunctionId, GenericParamId, HasModule, ImplId, ItemContainerId, + ModuleId, TraitId, + expr_store::path::GenericArgs as HirGenericArgs, + hir::ExprId, nameres::{DefMap, block_def_map, crate_def_map}, - signatures::{ConstFlags, EnumFlags, FnFlags, StructFlags, TraitFlags, TypeAliasFlags}, + resolver::Resolver, }; -use hir_expand::name::Name; -use intern::sym; -use rustc_ast_ir::Mutability; +use intern::{Symbol, sym}; use rustc_hash::{FxHashMap, FxHashSet}; use rustc_type_ir::{ - FloatTy, IntTy, TypeVisitableExt, UintTy, - inherent::{ - AdtDef, BoundExistentialPredicates, GenericArgs as _, IntoKind, SliceLike, Ty as _, - }, + TypeVisitableExt, + fast_reject::{TreatParams, simplify_type}, + inherent::{BoundExistentialPredicates, IntoKind, SliceLike}, }; -use smallvec::{SmallVec, smallvec}; -use stdx::never; +use stdx::impl_from; use triomphe::Arc; use crate::{ - TraitEnvironment, - autoderef::{self, AutoderefKind}, + TraitEnvironment, all_super_traits, db::HirDatabase, - infer::{Adjust, Adjustment, OverloadedDeref, PointerCast, unify::InferenceTable}, - lang_items::is_box, + infer::{InferenceContext, unify::InferenceTable}, + lower::GenericPredicates, next_solver::{ - Canonical, DbInterner, ErrorGuaranteed, GenericArgs, Goal, Predicate, Region, SolverDefId, - TraitRef, Ty, TyKind, TypingMode, + Binder, ClauseKind, DbInterner, FnSig, GenericArgs, PredicateKind, SimplifiedType, + SolverDefId, TraitRef, Ty, TyKind, TypingMode, infer::{ - DbInternerInferExt, InferCtxt, + BoundRegionConversionTime, DbInternerInferExt, InferCtxt, InferOk, select::ImplSource, - traits::{Obligation, ObligationCause, PredicateObligation}, + traits::{Obligation, ObligationCause, PredicateObligations}, }, obligation_ctxt::ObligationCtxt, + util::clauses_as_obligations, }, - traits::next_trait_solve_canonical_in_ctxt, - utils::all_super_traits, }; -/// This is used as a key for indexing impls. -#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)] -pub enum TyFingerprint { - // These are lang item impls: - Str, - Slice, - Array, - Never, - Ref(Mutability), - RawPtr(Mutability), - Bool, - Char, - Int(IntTy), - Uint(UintTy), - Float(FloatTy), - // These can have user-defined impls: - Adt(hir_def::AdtId), - Dyn(TraitId), - ForeignType(TypeAliasId), - // These only exist for trait impls - Unit, - Unnameable, - Function(u32), -} - -impl TyFingerprint { - /// Creates a TyFingerprint for looking up an inherent impl. Only certain - /// types can have inherent impls: if we have some `struct S`, we can have - /// an `impl S`, but not `impl &S`. Hence, this will return `None` for - /// reference types and such. - pub fn for_inherent_impl<'db>(ty: Ty<'db>) -> Option<TyFingerprint> { - let fp = match ty.kind() { - TyKind::Str => TyFingerprint::Str, - TyKind::Never => TyFingerprint::Never, - TyKind::Slice(..) => TyFingerprint::Slice, - TyKind::Array(..) => TyFingerprint::Array, - TyKind::Bool => TyFingerprint::Bool, - TyKind::Char => TyFingerprint::Char, - TyKind::Int(int) => TyFingerprint::Int(int), - TyKind::Uint(int) => TyFingerprint::Uint(int), - TyKind::Float(float) => TyFingerprint::Float(float), - TyKind::Adt(adt_def, _) => TyFingerprint::Adt(adt_def.def_id().0), - TyKind::RawPtr(_, mutability) => TyFingerprint::RawPtr(mutability), - TyKind::Foreign(alias_id, ..) => TyFingerprint::ForeignType(alias_id.0), - TyKind::Dynamic(bounds, _) => { - bounds.principal_def_id().map(|trait_| TyFingerprint::Dyn(trait_.0))? - } - _ => return None, - }; - Some(fp) - } - - /// Creates a TyFingerprint for looking up a trait impl. - pub fn for_trait_impl<'db>(ty: Ty<'db>) -> Option<TyFingerprint> { - let fp = match ty.kind() { - TyKind::Str => TyFingerprint::Str, - TyKind::Never => TyFingerprint::Never, - TyKind::Slice(..) => TyFingerprint::Slice, - TyKind::Array(..) => TyFingerprint::Array, - TyKind::Bool => TyFingerprint::Bool, - TyKind::Char => TyFingerprint::Char, - TyKind::Int(int) => TyFingerprint::Int(int), - TyKind::Uint(int) => TyFingerprint::Uint(int), - TyKind::Float(float) => TyFingerprint::Float(float), - TyKind::Adt(adt_def, _) => TyFingerprint::Adt(adt_def.def_id().0), - TyKind::RawPtr(_, mutability) => TyFingerprint::RawPtr(mutability), - TyKind::Foreign(alias_id, ..) => TyFingerprint::ForeignType(alias_id.0), - TyKind::Dynamic(bounds, _) => { - bounds.principal_def_id().map(|trait_| TyFingerprint::Dyn(trait_.0))? - } - TyKind::Ref(_, _, mutability) => TyFingerprint::Ref(mutability), - TyKind::Tuple(subst) => { - let first_ty = subst.as_slice().first(); - match first_ty { - Some(ty) => return TyFingerprint::for_trait_impl(*ty), - None => TyFingerprint::Unit, - } - } - // FIXME(next-solver): Putting `Alias` here is *probably* incorrect, AFAIK it should return `None`. But this breaks - // flyimport, which uses an incorrect but fast method resolution algorithm. Therefore we put it here, - // because this function is only called by flyimport, and anyway we should get rid of `TyFingerprint` - // and switch to `rustc_type_ir`'s `SimplifiedType`. - TyKind::Alias(..) - | TyKind::FnDef(_, _) - | TyKind::Closure(_, _) - | TyKind::Coroutine(..) - | TyKind::CoroutineClosure(..) - | TyKind::CoroutineWitness(..) => TyFingerprint::Unnameable, - TyKind::FnPtr(sig, _) => { - TyFingerprint::Function(sig.skip_binder().inputs_and_output.inner().len() as u32) - } - TyKind::Param(_) - | TyKind::Bound(..) - | TyKind::Placeholder(..) - | TyKind::Infer(_) - | TyKind::Error(_) - | TyKind::Pat(..) - | TyKind::UnsafeBinder(..) => return None, - }; - Some(fp) - } -} +pub use self::probe::{ + Candidate, CandidateKind, CandidateStep, CandidateWithPrivate, Mode, Pick, PickKind, +}; -pub(crate) const ALL_INT_FPS: [TyFingerprint; 12] = [ - TyFingerprint::Int(IntTy::I8), - TyFingerprint::Int(IntTy::I16), - TyFingerprint::Int(IntTy::I32), - TyFingerprint::Int(IntTy::I64), - TyFingerprint::Int(IntTy::I128), - TyFingerprint::Int(IntTy::Isize), - TyFingerprint::Uint(UintTy::U8), - TyFingerprint::Uint(UintTy::U16), - TyFingerprint::Uint(UintTy::U32), - TyFingerprint::Uint(UintTy::U64), - TyFingerprint::Uint(UintTy::U128), - TyFingerprint::Uint(UintTy::Usize), -]; - -pub(crate) const ALL_FLOAT_FPS: [TyFingerprint; 4] = [ - TyFingerprint::Float(FloatTy::F16), - TyFingerprint::Float(FloatTy::F32), - TyFingerprint::Float(FloatTy::F64), - TyFingerprint::Float(FloatTy::F128), -]; - -type TraitFpMap = FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Box<[ImplId]>>>; -type TraitFpMapCollector = FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>; - -/// Trait impls defined or available in some crate. -#[derive(Debug, Eq, PartialEq)] -pub struct TraitImpls { - // If the `Option<TyFingerprint>` is `None`, the impl may apply to any self type. - map: TraitFpMap, +#[derive(Debug, Clone)] +pub struct MethodResolutionUnstableFeatures { + arbitrary_self_types: bool, + arbitrary_self_types_pointers: bool, + supertrait_item_shadowing: bool, } -impl TraitImpls { - pub(crate) fn trait_impls_in_crate_query(db: &dyn HirDatabase, krate: Crate) -> Arc<Self> { - let _p = tracing::info_span!("trait_impls_in_crate_query", ?krate).entered(); - let mut impls = FxHashMap::default(); - - Self::collect_def_map(db, &mut impls, crate_def_map(db, krate)); - - Arc::new(Self::finish(impls)) - } - - pub(crate) fn trait_impls_in_block_query( - db: &dyn HirDatabase, - block: BlockId, - ) -> Option<Arc<Self>> { - let _p = tracing::info_span!("trait_impls_in_block_query").entered(); - let mut impls = FxHashMap::default(); - - Self::collect_def_map(db, &mut impls, block_def_map(db, block)); - - if impls.is_empty() { None } else { Some(Arc::new(Self::finish(impls))) } - } - - pub(crate) fn trait_impls_in_deps_query( - db: &dyn HirDatabase, - krate: Crate, - ) -> Arc<[Arc<Self>]> { - let _p = tracing::info_span!("trait_impls_in_deps_query", ?krate).entered(); - Arc::from_iter( - db.transitive_deps(krate).into_iter().map(|krate| db.trait_impls_in_crate(krate)), - ) - } - - fn finish(map: TraitFpMapCollector) -> TraitImpls { - TraitImpls { - map: map - .into_iter() - .map(|(k, v)| (k, v.into_iter().map(|(k, v)| (k, v.into_boxed_slice())).collect())) - .collect(), - } - } - - fn collect_def_map(db: &dyn HirDatabase, map: &mut TraitFpMapCollector, def_map: &DefMap) { - for (_module_id, module_data) in def_map.modules() { - for impl_id in module_data.scope.impls() { - // Reservation impls should be ignored during trait resolution, so we never need - // them during type analysis. See rust-lang/rust#64631 for details. - // - // FIXME: Reservation impls should be considered during coherence checks. If we are - // (ever) to implement coherence checks, this filtering should be done by the trait - // solver. - if db.attrs(impl_id.into()).by_key(sym::rustc_reservation_impl).exists() { - continue; - } - let target_trait = match db.impl_trait(impl_id) { - Some(tr) => tr.skip_binder().def_id.0, - None => continue, - }; - let self_ty = db.impl_self_ty(impl_id); - let self_ty_fp = TyFingerprint::for_trait_impl(self_ty.instantiate_identity()); - map.entry(target_trait).or_default().entry(self_ty_fp).or_default().push(impl_id); - } - - // 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) { - Self::collect_def_map(db, map, block_def_map); - } - } +impl MethodResolutionUnstableFeatures { + pub fn from_def_map(def_map: &DefMap) -> Self { + Self { + arbitrary_self_types: def_map.is_unstable_feature_enabled(&sym::arbitrary_self_types), + arbitrary_self_types_pointers: def_map + .is_unstable_feature_enabled(&sym::arbitrary_self_types_pointers), + supertrait_item_shadowing: def_map + .is_unstable_feature_enabled(&sym::supertrait_item_shadowing), } } - - /// Queries all trait impls for the given type. - pub fn for_self_ty_without_blanket_impls( - &self, - fp: TyFingerprint, - ) -> impl Iterator<Item = ImplId> + '_ { - self.map - .values() - .flat_map(move |impls| impls.get(&Some(fp)).into_iter()) - .flat_map(|it| it.iter().copied()) - } - - /// Queries all impls of the given trait. - pub fn for_trait(&self, trait_: TraitId) -> impl Iterator<Item = ImplId> + '_ { - self.map - .get(&trait_) - .into_iter() - .flat_map(|map| map.values().flat_map(|v| v.iter().copied())) - } - - /// Queries all impls of `trait_` that may apply to `self_ty`. - pub fn for_trait_and_self_ty( - &self, - trait_: TraitId, - self_ty: TyFingerprint, - ) -> impl Iterator<Item = ImplId> + '_ { - self.map - .get(&trait_) - .into_iter() - .flat_map(move |map| map.get(&Some(self_ty)).into_iter().chain(map.get(&None))) - .flat_map(|v| v.iter().copied()) - } - - /// Queries whether `self_ty` has potentially applicable implementations of `trait_`. - pub fn has_impls_for_trait_and_self_ty(&self, trait_: TraitId, self_ty: TyFingerprint) -> bool { - self.for_trait_and_self_ty(trait_, self_ty).next().is_some() - } - - pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ { - self.map.values().flat_map(|map| map.values().flat_map(|v| v.iter().copied())) - } } -/// Inherent impls defined in some crate. -/// -/// Inherent impls can only be defined in the crate that also defines the self type of the impl -/// (note that some primitives are considered to be defined by both libcore and liballoc). -/// -/// This makes inherent impl lookup easier than trait impl lookup since we only have to consider a -/// single crate. -#[derive(Debug, Eq, PartialEq)] -pub struct InherentImpls { - map: FxHashMap<TyFingerprint, Vec<ImplId>>, - invalid_impls: Vec<ImplId>, +pub struct MethodResolutionContext<'a, 'db> { + pub infcx: &'a InferCtxt<'db>, + pub resolver: &'a Resolver<'db>, + pub env: &'a TraitEnvironment<'db>, + pub traits_in_scope: &'a FxHashSet<TraitId>, + pub edition: Edition, + pub unstable_features: &'a MethodResolutionUnstableFeatures, } -impl InherentImpls { - pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: Crate) -> Arc<Self> { - let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered(); - let mut impls = Self { map: FxHashMap::default(), invalid_impls: Vec::default() }; - - let crate_def_map = crate_def_map(db, krate); - 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<Arc<Self>> { - let _p = tracing::info_span!("inherent_impls_in_block_query").entered(); - let mut impls = Self { map: FxHashMap::default(), invalid_impls: Vec::default() }; - - let block_def_map = block_def_map(db, block); - impls.collect_def_map(db, block_def_map); - impls.shrink_to_fit(); +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub enum CandidateId { + FunctionId(FunctionId), + ConstId(ConstId), +} +impl_from!(FunctionId, ConstId for CandidateId); - if impls.map.is_empty() && impls.invalid_impls.is_empty() { - None - } else { - Some(Arc::new(impls)) +impl CandidateId { + fn container(self, db: &dyn HirDatabase) -> ItemContainerId { + match self { + CandidateId::FunctionId(id) => id.loc(db).container, + CandidateId::ConstId(id) => id.loc(db).container, } } +} - fn shrink_to_fit(&mut self) { - self.map.values_mut().for_each(Vec::shrink_to_fit); - self.map.shrink_to_fit(); - } +#[derive(Clone, Copy, Debug)] +pub(crate) struct MethodCallee<'db> { + /// Impl method ID, for inherent methods, or trait method ID, otherwise. + pub def_id: FunctionId, + pub args: GenericArgs<'db>, - 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_signature(impl_id); - if data.target_trait.is_some() { - continue; - } + /// Instantiated method signature, i.e., it has been + /// instantiated, normalized, and has had late-bound + /// lifetimes replaced with inference variables. + pub sig: FnSig<'db>, +} - let self_ty = db.impl_self_ty(impl_id); - let self_ty = self_ty.instantiate_identity(); +#[derive(Debug)] +pub enum MethodError<'db> { + /// Did not find an applicable method. + NoMatch, - match is_inherent_impl_coherent(db, def_map, impl_id, self_ty) { - true => { - // `fp` should only be `None` in error cases (either erroneous code or incomplete name resolution) - if let Some(fp) = TyFingerprint::for_inherent_impl(self_ty) { - self.map.entry(fp).or_default().push(impl_id); - } - } - false => self.invalid_impls.push(impl_id), - } - } + /// Multiple methods might apply. + Ambiguity(Vec<CandidateSource>), - // 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) { - self.collect_def_map(db, block_def_map); - } - } - } - } + /// Found an applicable method, but it is not visible. + PrivateMatch(Pick<'db>), - pub fn for_self_ty<'db>(&self, self_ty: Ty<'db>) -> &[ImplId] { - match TyFingerprint::for_inherent_impl(self_ty) { - Some(fp) => self.map.get(&fp).map(|vec| vec.as_ref()).unwrap_or(&[]), - None => &[], - } - } + /// Found a `Self: Sized` bound where `Self` is a trait object. + IllegalSizedBound { candidates: Vec<FunctionId>, needs_mut: bool }, - pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ { - self.map.values().flat_map(|v| v.iter().copied()) - } + /// Error has already been emitted, no need to emit another one. + ErrorReported, +} - pub fn invalid_impls(&self) -> &[ImplId] { - &self.invalid_impls - } +// A pared down enum describing just the places from which a method +// candidate can arise. Used for error reporting only. +#[derive(Copy, Clone, Debug, Eq, PartialEq)] +pub enum CandidateSource { + Impl(ImplId), + Trait(TraitId), } -pub(crate) fn incoherent_inherent_impl_crates( - db: &dyn HirDatabase, - krate: Crate, - fp: TyFingerprint, -) -> SmallVec<[Crate; 2]> { - let _p = tracing::info_span!("incoherent_inherent_impl_crates").entered(); - let mut res = SmallVec::new(); +impl<'a, 'db> InferenceContext<'a, 'db> { + /// Performs method lookup. If lookup is successful, it will return the callee + /// and store an appropriate adjustment for the self-expr. In some cases it may + /// report an error (e.g., invoking the `drop` method). + #[instrument(level = "debug", skip(self))] + pub(crate) fn lookup_method_including_private( + &mut self, + self_ty: Ty<'db>, + name: Name, + generic_args: Option<&HirGenericArgs>, + receiver: ExprId, + call_expr: ExprId, + ) -> Result<(MethodCallee<'db>, bool), MethodError<'db>> { + let (pick, is_visible) = match self.lookup_probe(name, self_ty) { + Ok(it) => (it, true), + Err(MethodError::PrivateMatch(it)) => { + // FIXME: Report error. + (it, false) + } + Err(err) => return Err(err), + }; - // should pass crate for finger print and do reverse deps + let result = self.confirm_method(&pick, self_ty, call_expr, generic_args); + debug!("result = {:?}", result); - for krate in db.transitive_deps(krate) { - let impls = db.inherent_impls_in_crate(krate); - if impls.map.get(&fp).is_some_and(|v| !v.is_empty()) { - res.push(krate); + if result.illegal_sized_bound { + // FIXME: Report an error. } - } - res -} + self.write_expr_adj(receiver, result.adjustments); + self.write_method_resolution(call_expr, result.callee.def_id, result.callee.args); -pub fn def_crates<'db>( - db: &'db dyn HirDatabase, - ty: Ty<'db>, - cur_crate: Crate, -) -> Option<SmallVec<[Crate; 2]>> { - match ty.kind() { - TyKind::Adt(adt_def, _) => { - let def_id = adt_def.def_id().0; - let rustc_has_incoherent_inherent_impls = match def_id { - hir_def::AdtId::StructId(id) => db - .struct_signature(id) - .flags - .contains(StructFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS), - hir_def::AdtId::UnionId(id) => db - .union_signature(id) - .flags - .contains(StructFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS), - hir_def::AdtId::EnumId(id) => db - .enum_signature(id) - .flags - .contains(EnumFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS), - }; - Some(if rustc_has_incoherent_inherent_impls { - db.incoherent_inherent_impl_crates(cur_crate, TyFingerprint::Adt(def_id)) - } else { - smallvec![def_id.module(db).krate()] - }) - } - TyKind::Foreign(alias) => { - let alias = alias.0; - Some( - if db - .type_alias_signature(alias) - .flags - .contains(TypeAliasFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPL) - { - db.incoherent_inherent_impl_crates(cur_crate, TyFingerprint::ForeignType(alias)) - } else { - smallvec![alias.module(db).krate()] - }, - ) - } - TyKind::Dynamic(bounds, _) => { - let trait_id = bounds.principal_def_id()?.0; - Some( - if db - .trait_signature(trait_id) - .flags - .contains(TraitFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS) - { - db.incoherent_inherent_impl_crates(cur_crate, TyFingerprint::Dyn(trait_id)) - } else { - smallvec![trait_id.module(db).krate()] - }, - ) - } - // for primitives, there may be impls in various places (core and alloc - // mostly). We just check the whole crate graph for crates with impls - // (cached behind a query). - TyKind::Bool - | TyKind::Char - | TyKind::Int(_) - | TyKind::Uint(_) - | TyKind::Float(_) - | TyKind::Str - | TyKind::Slice(_) - | TyKind::Array(..) - | TyKind::RawPtr(..) => Some(db.incoherent_inherent_impl_crates( - cur_crate, - TyFingerprint::for_inherent_impl(ty).expect("fingerprint for primitive"), - )), - _ => None, + Ok((result.callee, is_visible)) } -} -/// Look up the method with the given name. -pub(crate) fn lookup_method<'db>( - ty: &Canonical<'db, Ty<'db>>, - table: &mut InferenceTable<'db>, - traits_in_scope: &FxHashSet<TraitId>, - visible_from_module: VisibleFromModule, - name: &Name, -) -> Option<(ReceiverAdjustments, FunctionId, bool)> { - let mut not_visible = None; - let res = iterate_method_candidates( - ty, - table, - traits_in_scope, - visible_from_module, - Some(name), - LookupMode::MethodCall, - |adjustments, f, visible| match f { - AssocItemId::FunctionId(f) if visible => Some((adjustments, f, true)), - AssocItemId::FunctionId(f) if not_visible.is_none() => { - not_visible = Some((adjustments, f, false)); - None - } - _ => None, - }, - ); - res.or(not_visible) -} - -/// Whether we're looking up a dotted method call (like `v.len()`) or a path -/// (like `Vec::new`). -#[derive(Copy, Clone, Debug, PartialEq, Eq)] -pub enum LookupMode { - /// Looking up a method call like `v.len()`: We only consider candidates - /// that have a `self` parameter, and do autoderef. - MethodCall, - /// Looking up a path like `Vec::new` or `Vec::default`: We consider all - /// candidates including associated constants, but don't do autoderef. - 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<Option<ModuleId>> for VisibleFromModule { - fn from(module: Option<ModuleId>) -> Self { - match module { - Some(module) => Self::Filter(module), - None => Self::None, - } + #[instrument(level = "debug", skip(self))] + pub(crate) fn lookup_probe( + &self, + method_name: Name, + self_ty: Ty<'db>, + ) -> probe::PickResult<'db> { + self.with_method_resolution(|ctx| { + let pick = ctx.probe_for_name(probe::Mode::MethodCall, method_name, self_ty)?; + Ok(pick) + }) } -} -impl From<Option<BlockId>> for VisibleFromModule { - fn from(block: Option<BlockId>) -> Self { - match block { - Some(block) => Self::IncludeBlock(block), - None => Self::None, - } + pub(crate) fn with_method_resolution<R>( + &self, + f: impl FnOnce(&MethodResolutionContext<'_, 'db>) -> R, + ) -> R { + let traits_in_scope = self.get_traits_in_scope(); + let traits_in_scope = match &traits_in_scope { + Either::Left(it) => it, + Either::Right(it) => *it, + }; + let ctx = MethodResolutionContext { + infcx: &self.table.infer_ctxt, + resolver: &self.resolver, + env: &self.table.trait_env, + traits_in_scope, + edition: self.edition, + unstable_features: &self.unstable_features, + }; + f(&ctx) } } -#[derive(Debug, Clone)] -pub enum AutorefOrPtrAdjustment { - Autoref(Mutability), - ToConstPtr, -} - -#[derive(Debug, Clone, Default)] -pub struct ReceiverAdjustments { - autoref: Option<AutorefOrPtrAdjustment>, - autoderefs: usize, - unsize_array: bool, -} - -impl ReceiverAdjustments { - pub(crate) fn apply<'db>( +/// Used by [FnCtxt::lookup_method_for_operator] with `-Znext-solver`. +/// +/// With `AsRigid` we error on `impl Opaque: NotInItemBounds` while +/// `AsInfer` just treats it as ambiguous and succeeds. This is necessary +/// as we want [FnCtxt::check_expr_call] to treat not-yet-defined opaque +/// types as rigid to support `impl Deref<Target = impl FnOnce()>` and +/// `Box<impl FnOnce()>`. +/// +/// We only want to treat opaque types as rigid if we need to eagerly choose +/// between multiple candidates. We otherwise treat them as ordinary inference +/// variable to avoid rejecting otherwise correct code. +#[derive(Debug)] +#[expect(dead_code)] +pub(super) enum TreatNotYetDefinedOpaques { + AsInfer, + AsRigid, +} + +impl<'db> InferenceTable<'db> { + /// `lookup_method_in_trait` is used for overloaded operators. + /// It does a very narrow slice of what the normal probe/confirm path does. + /// In particular, it doesn't really do any probing: it simply constructs + /// an obligation for a particular trait with the given self type and checks + /// whether that trait is implemented. + #[instrument(level = "debug", skip(self))] + pub(super) fn lookup_method_for_operator( &self, - table: &mut InferenceTable<'db>, - mut ty: Ty<'db>, - ) -> (Ty<'db>, Vec<Adjustment<'db>>) { - let mut adjust = Vec::new(); - let mut autoderef = table.autoderef(ty); - autoderef.next(); - for _ in 0..self.autoderefs { - match autoderef.next() { - None => { - never!("autoderef not possible for {:?}", ty); - ty = Ty::new_error(table.interner(), ErrorGuaranteed); - break; - } - Some((new_ty, _)) => { - ty = new_ty; - let mutbl = match self.autoref { - Some(AutorefOrPtrAdjustment::Autoref(m)) => Some(m), - Some(AutorefOrPtrAdjustment::ToConstPtr) => Some(Mutability::Not), - // FIXME should we know the mutability here, when autoref is `None`? - None => None, - }; - adjust.push(Adjustment { - kind: Adjust::Deref(match autoderef.steps().last().unwrap().1 { - AutoderefKind::Overloaded => Some(OverloadedDeref(mutbl)), - AutoderefKind::Builtin => None, - }), - target: ty, - }); - } - } - } - if let Some(autoref) = &self.autoref { - let lt = table.next_region_var(); - match autoref { - AutorefOrPtrAdjustment::Autoref(m) => { - let a = Adjustment::borrow(table.interner(), *m, ty, lt); - ty = a.target; - adjust.push(a); + cause: ObligationCause, + method_name: Symbol, + trait_def_id: TraitId, + self_ty: Ty<'db>, + opt_rhs_ty: Option<Ty<'db>>, + treat_opaques: TreatNotYetDefinedOpaques, + ) -> Option<InferOk<'db, MethodCallee<'db>>> { + // Construct a trait-reference `self_ty : Trait<input_tys>` + let args = GenericArgs::for_item( + self.interner(), + trait_def_id.into(), + |param_idx, param_id, _| match param_id { + GenericParamId::LifetimeParamId(_) | GenericParamId::ConstParamId(_) => { + unreachable!("did not expect operator trait to have lifetime/const") } - AutorefOrPtrAdjustment::ToConstPtr => { - if let TyKind::RawPtr(pointee, Mutability::Mut) = ty.kind() { - let a = Adjustment { - kind: Adjust::Pointer(PointerCast::MutToConstPointer), - target: Ty::new_ptr(table.interner(), pointee, Mutability::Not), - }; - ty = a.target; - adjust.push(a); + GenericParamId::TypeParamId(_) => { + if param_idx == 0 { + self_ty.into() + } else if let Some(rhs_ty) = opt_rhs_ty { + assert_eq!(param_idx, 1, "did not expect >1 param on operator trait"); + rhs_ty.into() } else { - never!("`ToConstPtr` target is not a raw mutable pointer"); + // FIXME: We should stop passing `None` for the failure case + // when probing for call exprs. I.e. `opt_rhs_ty` should always + // be set when it needs to be. + self.next_var_for_param(param_id) } } - }; - } - if self.unsize_array { - ty = 'it: { - if let TyKind::Ref(l, inner, m) = ty.kind() - && let TyKind::Array(inner, _) = inner.kind() - { - break 'it Ty::new_ref( - table.interner(), - l, - Ty::new_slice(table.interner(), inner), - m, - ); - } - // FIXME: report diagnostic if array unsizing happens without indirection. - ty - }; - adjust.push(Adjustment { kind: Adjust::Pointer(PointerCast::Unsize), target: ty }); - } - (ty, adjust) - } + }, + ); + + let obligation = Obligation::new( + self.interner(), + cause, + self.trait_env.env, + TraitRef::new_from_args(self.interner(), trait_def_id.into(), args), + ); + + // Now we want to know if this can be matched + let matches_trait = match treat_opaques { + TreatNotYetDefinedOpaques::AsInfer => self.infer_ctxt.predicate_may_hold(&obligation), + TreatNotYetDefinedOpaques::AsRigid => { + self.infer_ctxt.predicate_may_hold_opaque_types_jank(&obligation) + } + }; - fn with_autoref(&self, a: AutorefOrPtrAdjustment) -> ReceiverAdjustments { - Self { autoref: Some(a), ..*self } - } -} + if !matches_trait { + debug!("--> Cannot match obligation"); + // Cannot be matched, no such method resolution is possible. + return None; + } + + // Trait must have a method named `m_name` and it should not have + // type parameters or early-bound regions. + let interner = self.interner(); + // We use `Ident::with_dummy_span` since no built-in operator methods have + // any macro-specific hygiene, so the span's context doesn't really matter. + let Some(method_item) = + trait_def_id.trait_items(self.db).method_by_name(&Name::new_symbol_root(method_name)) + else { + panic!("expected associated item for operator trait") + }; -// 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(crate) fn iterate_method_candidates<'db, T>( - ty: &Canonical<'db, Ty<'db>>, - table: &mut InferenceTable<'db>, - traits_in_scope: &FxHashSet<TraitId>, - visible_from_module: VisibleFromModule, - name: Option<&Name>, - mode: LookupMode, - mut callback: impl FnMut(ReceiverAdjustments, AssocItemId, bool) -> Option<T>, -) -> Option<T> { - let mut slot = None; - _ = iterate_method_candidates_dyn_impl( - ty, - table, - traits_in_scope, - visible_from_module, - name, - mode, - &mut |adj, item, visible| { - assert!(slot.is_none()); - if let Some(it) = callback(adj, item, visible) { - slot = Some(it); - return ControlFlow::Break(()); - } - ControlFlow::Continue(()) - }, - ); - slot + let def_id = method_item; + + debug!("lookup_in_trait_adjusted: method_item={:?}", method_item); + let mut obligations = PredicateObligations::new(); + + // Instantiate late-bound regions and instantiate the trait + // parameters into the method type to get the actual method type. + // + // N.B., instantiate late-bound regions before normalizing the + // function signature so that normalization does not need to deal + // with bound regions. + let fn_sig = + self.db.callable_item_signature(method_item.into()).instantiate(interner, args); + let fn_sig = self + .infer_ctxt + .instantiate_binder_with_fresh_vars(BoundRegionConversionTime::FnCall, fn_sig); + + // Register obligations for the parameters. This will include the + // `Self` parameter, which in turn has a bound of the main trait, + // so this also effectively registers `obligation` as well. (We + // used to register `obligation` explicitly, but that resulted in + // double error messages being reported.) + // + // Note that as the method comes from a trait, it should not have + // any late-bound regions appearing in its bounds. + let bounds = GenericPredicates::query_all(self.db, method_item.into()); + let bounds = clauses_as_obligations( + bounds.iter_instantiated_copied(interner, args.as_slice()), + ObligationCause::new(), + self.trait_env.env, + ); + + obligations.extend(bounds); + + // Also add an obligation for the method type being well-formed. + debug!( + "lookup_method_in_trait: matched method fn_sig={:?} obligation={:?}", + fn_sig, obligation + ); + for ty in fn_sig.inputs_and_output { + obligations.push(Obligation::new( + interner, + obligation.cause.clone(), + self.trait_env.env, + Binder::dummy(PredicateKind::Clause(ClauseKind::WellFormed(ty.into()))), + )); + } + + let callee = MethodCallee { def_id, args, sig: fn_sig }; + debug!("callee = {:?}", callee); + + Some(InferOk { obligations, value: callee }) + } } pub fn lookup_impl_const<'db>( @@ -690,7 +356,7 @@ pub fn lookup_impl_const<'db>( let interner = infcx.interner; let db = interner.db; - let trait_id = match const_id.lookup(db).container { + let trait_id = match const_id.loc(db).container { ItemContainerId::TraitId(id) => id, _ => return (const_id, subs), }; @@ -719,7 +385,7 @@ pub fn is_dyn_method<'db>( ) -> Option<usize> { let db = interner.db; - let ItemContainerId::TraitId(trait_id) = func.lookup(db).container else { + let ItemContainerId::TraitId(trait_id) = func.loc(db).container else { return None; }; let trait_params = db.generic_params(trait_id.into()).len(); @@ -755,7 +421,7 @@ pub(crate) fn lookup_impl_method_query<'db>( let interner = DbInterner::new_with(db, Some(env.krate), env.block); let infcx = interner.infer_ctxt().build(TypingMode::PostAnalysis); - let ItemContainerId::TraitId(trait_id) = func.lookup(db).container else { + let ItemContainerId::TraitId(trait_id) = func.loc(db).container else { return (func, fn_subst); }; let trait_params = db.generic_params(trait_id.into()).len(); @@ -833,981 +499,337 @@ pub(crate) fn find_matching_impl<'db>( } } -fn is_inherent_impl_coherent<'db>( - db: &'db dyn HirDatabase, - def_map: &DefMap, - impl_id: ImplId, - self_ty: Ty<'db>, -) -> bool { - let self_ty = self_ty.kind(); - let impl_allowed = match self_ty { - TyKind::Tuple(_) - | TyKind::FnDef(_, _) - | TyKind::Array(_, _) - | TyKind::Never - | TyKind::RawPtr(_, _) - | TyKind::Ref(_, _, _) - | TyKind::Slice(_) - | TyKind::Str - | TyKind::Bool - | TyKind::Char - | TyKind::Int(_) - | TyKind::Uint(_) - | TyKind::Float(_) => def_map.is_rustc_coherence_is_core(), - - TyKind::Adt(adt_def, _) => adt_def.def_id().0.module(db).krate() == def_map.krate(), - TyKind::Dynamic(it, _) => it - .principal_def_id() - .is_some_and(|trait_id| trait_id.0.module(db).krate() == def_map.krate()), +#[salsa::tracked(returns(ref))] +fn crates_containing_incoherent_inherent_impls(db: &dyn HirDatabase) -> Box<[Crate]> { + // We assume that only sysroot crates contain `#[rustc_has_incoherent_inherent_impls]` + // impls, since this is an internal feature and only std uses it. + db.all_crates().iter().copied().filter(|krate| krate.data(db).origin.is_lang()).collect() +} +pub fn incoherent_inherent_impls(db: &dyn HirDatabase, self_ty: SimplifiedType) -> &[ImplId] { + let has_incoherent_impls = match self_ty.def() { + Some(def_id) => match def_id.try_into() { + Ok(def_id) => { + db.attrs(def_id).by_key(sym::rustc_has_incoherent_inherent_impls).exists() + } + Err(()) => true, + }, _ => true, }; - impl_allowed || { - let rustc_has_incoherent_inherent_impls = match self_ty { - TyKind::Tuple(_) - | TyKind::FnDef(_, _) - | TyKind::Array(_, _) - | TyKind::Never - | TyKind::RawPtr(_, _) - | TyKind::Ref(_, _, _) - | TyKind::Slice(_) - | TyKind::Str - | TyKind::Bool - | TyKind::Char - | TyKind::Int(_) - | TyKind::Uint(_) - | TyKind::Float(_) => true, - - TyKind::Adt(adt_def, _) => match adt_def.def_id().0 { - hir_def::AdtId::StructId(id) => db - .struct_signature(id) - .flags - .contains(StructFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS), - hir_def::AdtId::UnionId(id) => db - .union_signature(id) - .flags - .contains(StructFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS), - hir_def::AdtId::EnumId(it) => db - .enum_signature(it) - .flags - .contains(EnumFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS), - }, - TyKind::Dynamic(it, _) => it.principal_def_id().is_some_and(|trait_id| { - db.trait_signature(trait_id.0) - .flags - .contains(TraitFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS) - }), - - _ => false, - }; - let items = impl_id.impl_items(db); - rustc_has_incoherent_inherent_impls - && !items.items.is_empty() - && items.items.iter().all(|&(_, assoc)| match assoc { - AssocItemId::FunctionId(it) => { - db.function_signature(it).flags.contains(FnFlags::RUSTC_ALLOW_INCOHERENT_IMPL) - } - AssocItemId::ConstId(it) => { - db.const_signature(it).flags.contains(ConstFlags::RUSTC_ALLOW_INCOHERENT_IMPL) - } - AssocItemId::TypeAliasId(it) => db - .type_alias_signature(it) - .flags - .contains(TypeAliasFlags::RUSTC_ALLOW_INCOHERENT_IMPL), - }) - } -} - -/// Checks whether the impl satisfies the orphan rules. -/// -/// Given `impl<P1..=Pn> Trait<T1..=Tn> for T0`, an `impl`` is valid only if at least one of the following is true: -/// - Trait is a local trait -/// - All of -/// - At least one of the types `T0..=Tn`` must be a local type. Let `Ti`` be the first such type. -/// - No uncovered type parameters `P1..=Pn` may appear in `T0..Ti`` (excluding `Ti`) -pub fn check_orphan_rules<'db>(db: &'db dyn HirDatabase, impl_: ImplId) -> bool { - let Some(impl_trait) = db.impl_trait(impl_) else { - // not a trait impl - return true; + return if !has_incoherent_impls { + &[] + } else { + incoherent_inherent_impls_query(db, (), self_ty) }; - let local_crate = impl_.lookup(db).container.krate(); - let is_local = |tgt_crate| tgt_crate == local_crate; - - let trait_ref = impl_trait.instantiate_identity(); - let trait_id = trait_ref.def_id.0; - if is_local(trait_id.module(db).krate()) { - // trait to be implemented is local - return true; - } + #[salsa::tracked(returns(ref))] + fn incoherent_inherent_impls_query( + db: &dyn HirDatabase, + _force_query_input_to_be_interned: (), + self_ty: SimplifiedType, + ) -> Box<[ImplId]> { + let _p = tracing::info_span!("incoherent_inherent_impl_crates").entered(); - let unwrap_fundamental = |mut ty: Ty<'db>| { - // Unwrap all layers of fundamental types with a loop. - loop { - match ty.kind() { - TyKind::Ref(_, referenced, _) => ty = referenced, - TyKind::Adt(adt_def, subs) => { - let AdtId::StructId(s) = adt_def.def_id().0 else { - break ty; - }; - let struct_signature = db.struct_signature(s); - if struct_signature.flags.contains(StructFlags::FUNDAMENTAL) { - let next = subs.types().next(); - match next { - Some(it) => ty = it, - None => break ty, - } - } else { - break ty; - } - } - _ => break ty, - } - } - }; - // - At least one of the types `T0..=Tn`` must be a local type. Let `Ti`` be the first such type. - - // FIXME: param coverage - // - No uncovered type parameters `P1..=Pn` may appear in `T0..Ti`` (excluding `Ti`) - let is_not_orphan = trait_ref.args.types().any(|ty| match unwrap_fundamental(ty).kind() { - TyKind::Adt(adt_def, _) => is_local(adt_def.def_id().0.module(db).krate()), - TyKind::Error(_) => true, - TyKind::Dynamic(it, _) => { - it.principal_def_id().is_some_and(|trait_id| is_local(trait_id.0.module(db).krate())) + let mut result = Vec::new(); + for &krate in crates_containing_incoherent_inherent_impls(db) { + let impls = InherentImpls::for_crate(db, krate); + result.extend_from_slice(impls.for_self_ty(&self_ty)); } - _ => false, - }); - #[allow(clippy::let_and_return)] - is_not_orphan + result.into_boxed_slice() + } } -/// To be used from `hir` only. -pub fn iterate_path_candidates<'db>( - ty: &Canonical<'db, Ty<'db>>, - db: &'db dyn HirDatabase, - env: Arc<TraitEnvironment<'db>>, - traits_in_scope: &FxHashSet<TraitId>, - visible_from_module: VisibleFromModule, - name: Option<&Name>, - callback: &mut dyn MethodCandidateCallback, -) -> 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 - callback, - ) +pub fn simplified_type_module(db: &dyn HirDatabase, ty: &SimplifiedType) -> Option<ModuleId> { + match ty.def()? { + SolverDefId::AdtId(id) => Some(id.module(db)), + SolverDefId::TypeAliasId(id) => Some(id.module(db)), + SolverDefId::TraitId(id) => Some(id.module(db)), + _ => None, + } } -/// To be used from `hir` only. -pub fn iterate_method_candidates_dyn<'db>( - ty: &Canonical<'db, Ty<'db>>, - db: &'db dyn HirDatabase, - env: Arc<TraitEnvironment<'db>>, - traits_in_scope: &FxHashSet<TraitId>, - visible_from_module: VisibleFromModule, - name: Option<&Name>, - mode: LookupMode, - callback: &mut dyn MethodCandidateCallback, -) -> ControlFlow<()> { - iterate_method_candidates_dyn_impl( - ty, - &mut InferenceTable::new(db, env, None), - traits_in_scope, - visible_from_module, - name, - mode, - callback, - ) +#[derive(Debug, PartialEq, Eq)] +pub struct InherentImpls { + map: FxHashMap<SimplifiedType, Box<[ImplId]>>, } -fn iterate_method_candidates_dyn_impl<'db>( - ty: &Canonical<'db, Ty<'db>>, - table: &mut InferenceTable<'db>, - traits_in_scope: &FxHashSet<TraitId>, - visible_from_module: VisibleFromModule, - name: Option<&Name>, - mode: LookupMode, - callback: &mut dyn MethodCandidateCallback, -) -> ControlFlow<()> { - let _p = tracing::info_span!( - "iterate_method_candidates_dyn", - ?mode, - ?name, - traits_in_scope_len = traits_in_scope.len() - ) - .entered(); - - 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). - // 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 `it.clone()` - // where `it: &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*. - - table.run_in_snapshot(|table| { - let ty = table.instantiate_canonical(*ty); - let deref_chain = autoderef_method_receiver(table, ty); - - deref_chain.into_iter().try_for_each(|(receiver_ty, adj)| { - iterate_method_candidates_with_autoref( - table, - receiver_ty, - adj, - traits_in_scope, - visible_from_module, - name, - callback, - ) - }) - }) - } - LookupMode::Path => { - // No autoderef for path lookups - iterate_method_candidates_for_self_ty( - ty, - table, - traits_in_scope, - visible_from_module, - name, - callback, - ) - } - } -} +#[salsa::tracked] +impl InherentImpls { + #[salsa::tracked(returns(ref))] + pub fn for_crate(db: &dyn HirDatabase, krate: Crate) -> Self { + let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered(); -#[tracing::instrument(skip_all, fields(name = ?name))] -fn iterate_method_candidates_with_autoref<'db>( - table: &mut InferenceTable<'db>, - receiver_ty: Canonical<'db, Ty<'db>>, - first_adjustment: ReceiverAdjustments, - traits_in_scope: &FxHashSet<TraitId>, - visible_from_module: VisibleFromModule, - name: Option<&Name>, - callback: &mut dyn MethodCandidateCallback, -) -> ControlFlow<()> { - let interner = table.interner(); - - let mut iterate_method_candidates_by_receiver = move |receiver_ty, first_adjustment| { - iterate_method_candidates_by_receiver( - table, - receiver_ty, - first_adjustment, - traits_in_scope, - visible_from_module, - name, - callback, - ) - }; + let crate_def_map = crate_def_map(db, krate); - let mut maybe_reborrowed = first_adjustment.clone(); - if let TyKind::Ref(_, _, m) = receiver_ty.value.kind() { - // Prefer reborrow of references to move - maybe_reborrowed.autoref = Some(AutorefOrPtrAdjustment::Autoref(m)); - maybe_reborrowed.autoderefs += 1; + Self::collect_def_map(db, crate_def_map) } - iterate_method_candidates_by_receiver(receiver_ty, maybe_reborrowed)?; - - let refed = Canonical { - max_universe: receiver_ty.max_universe, - variables: receiver_ty.variables, - value: Ty::new_ref(interner, Region::error(interner), receiver_ty.value, Mutability::Not), - }; - - iterate_method_candidates_by_receiver( - refed, - first_adjustment.with_autoref(AutorefOrPtrAdjustment::Autoref(Mutability::Not)), - )?; - - let ref_muted = Canonical { - max_universe: receiver_ty.max_universe, - variables: receiver_ty.variables, - value: Ty::new_ref(interner, Region::error(interner), receiver_ty.value, Mutability::Mut), - }; - - iterate_method_candidates_by_receiver( - ref_muted, - first_adjustment.with_autoref(AutorefOrPtrAdjustment::Autoref(Mutability::Mut)), - )?; + #[salsa::tracked(returns(ref))] + pub fn for_block(db: &dyn HirDatabase, block: BlockId) -> Option<Box<Self>> { + let _p = tracing::info_span!("inherent_impls_in_block_query").entered(); - if let TyKind::RawPtr(ty, Mutability::Mut) = receiver_ty.value.kind() { - let const_ptr_ty = rustc_type_ir::Canonical { - max_universe: rustc_type_ir::UniverseIndex::ZERO, - value: Ty::new_ptr(interner, ty, Mutability::Not), - variables: receiver_ty.variables, - }; - iterate_method_candidates_by_receiver( - const_ptr_ty, - first_adjustment.with_autoref(AutorefOrPtrAdjustment::ToConstPtr), - )?; + let block_def_map = block_def_map(db, block); + let result = Self::collect_def_map(db, block_def_map); + if result.map.is_empty() { None } else { Some(Box::new(result)) } } - - ControlFlow::Continue(()) } -pub trait MethodCandidateCallback { - fn on_inherent_method( - &mut self, - adjustments: ReceiverAdjustments, - item: AssocItemId, - is_visible: bool, - ) -> ControlFlow<()>; +impl InherentImpls { + fn collect_def_map(db: &dyn HirDatabase, def_map: &DefMap) -> Self { + let mut map = FxHashMap::default(); + collect(db, def_map, &mut map); + let mut map = map + .into_iter() + .map(|(self_ty, impls)| (self_ty, impls.into_boxed_slice())) + .collect::<FxHashMap<_, _>>(); + map.shrink_to_fit(); + return Self { map }; + + fn collect( + db: &dyn HirDatabase, + def_map: &DefMap, + map: &mut FxHashMap<SimplifiedType, Vec<ImplId>>, + ) { + for (_module_id, module_data) in def_map.modules() { + for impl_id in module_data.scope.impls() { + let data = db.impl_signature(impl_id); + if data.target_trait.is_some() { + continue; + } - fn on_trait_method( - &mut self, - adjustments: ReceiverAdjustments, - item: AssocItemId, - is_visible: bool, - ) -> ControlFlow<()>; -} + let interner = DbInterner::new_with(db, None, None); + let self_ty = db.impl_self_ty(impl_id); + let self_ty = self_ty.instantiate_identity(); + if let Some(self_ty) = + simplify_type(interner, self_ty, TreatParams::InstantiateWithInfer) + { + map.entry(self_ty).or_default().push(impl_id); + } + } -impl<F> MethodCandidateCallback for F -where - F: FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>, -{ - fn on_inherent_method( - &mut self, - adjustments: ReceiverAdjustments, - item: AssocItemId, - is_visible: bool, - ) -> ControlFlow<()> { - self(adjustments, item, is_visible) + // 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) { + collect(db, block_def_map, map); + } + } + } + } } - fn on_trait_method( - &mut self, - adjustments: ReceiverAdjustments, - item: AssocItemId, - is_visible: bool, - ) -> ControlFlow<()> { - self(adjustments, item, is_visible) + pub fn for_self_ty(&self, self_ty: &SimplifiedType) -> &[ImplId] { + self.map.get(self_ty).map(|it| &**it).unwrap_or_default() } -} - -#[tracing::instrument(skip_all, fields(name = ?name))] -fn iterate_method_candidates_by_receiver<'db>( - table: &mut InferenceTable<'db>, - receiver_ty: Canonical<'db, Ty<'db>>, - receiver_adjustments: ReceiverAdjustments, - traits_in_scope: &FxHashSet<TraitId>, - visible_from_module: VisibleFromModule, - name: Option<&Name>, - callback: &mut dyn MethodCandidateCallback, -) -> ControlFlow<()> { - let receiver_ty = table.instantiate_canonical(receiver_ty); - // 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, including raw derefs. - table.run_in_snapshot(|table| { - let mut autoderef = autoderef::Autoderef::new_no_tracking(table, receiver_ty) - .include_raw_pointers() - .use_receiver_trait(); - while let Some((self_ty, _)) = autoderef.next() { - iterate_inherent_methods( - self_ty, - autoderef.table, - name, - Some(receiver_ty), - Some(receiver_adjustments.clone()), - visible_from_module, - LookupMode::MethodCall, - &mut |adjustments, item, is_visible| { - callback.on_inherent_method(adjustments, item, is_visible) - }, - )? - } - ControlFlow::Continue(()) - })?; - table.run_in_snapshot(|table| { - let mut autoderef = autoderef::Autoderef::new_no_tracking(table, receiver_ty) - .include_raw_pointers() - .use_receiver_trait(); - while let Some((self_ty, _)) = autoderef.next() { - if matches!(self_ty.kind(), TyKind::Infer(rustc_type_ir::TyVar(_))) { - // don't try to resolve methods on unknown types - return ControlFlow::Continue(()); - } - iterate_trait_method_candidates( - self_ty, - autoderef.table, - traits_in_scope, - name, - Some(receiver_ty), - Some(receiver_adjustments.clone()), - LookupMode::MethodCall, - &mut |adjustments, item, is_visible| { - callback.on_trait_method(adjustments, item, is_visible) - }, - )? - } - ControlFlow::Continue(()) - }) + pub fn for_each_crate_and_block( + db: &dyn HirDatabase, + krate: Crate, + block: Option<BlockId>, + for_each: &mut dyn FnMut(&InherentImpls), + ) { + let blocks = std::iter::successors(block, |block| block.loc(db).module.containing_block()); + blocks.filter_map(|block| Self::for_block(db, block).as_deref()).for_each(&mut *for_each); + for_each(Self::for_crate(db, krate)); + } } -#[tracing::instrument(skip_all, fields(name = ?name))] -fn iterate_method_candidates_for_self_ty<'db>( - self_ty: &Canonical<'db, Ty<'db>>, - table: &mut InferenceTable<'db>, - traits_in_scope: &FxHashSet<TraitId>, - visible_from_module: VisibleFromModule, - name: Option<&Name>, - callback: &mut dyn MethodCandidateCallback, -) -> ControlFlow<()> { - table.run_in_snapshot(|table| { - let self_ty = table.instantiate_canonical(*self_ty); - iterate_inherent_methods( - self_ty, - table, - name, - None, - None, - visible_from_module, - LookupMode::Path, - &mut |adjustments, item, is_visible| { - callback.on_inherent_method(adjustments, item, is_visible) - }, - )?; - iterate_trait_method_candidates( - self_ty, - table, - traits_in_scope, - name, - None, - None, - LookupMode::Path, - &mut |adjustments, item, is_visible| { - callback.on_trait_method(adjustments, item, is_visible) - }, - ) - }) +#[derive(Debug, PartialEq)] +struct OneTraitImpls { + non_blanket_impls: FxHashMap<SimplifiedType, Box<[ImplId]>>, + blanket_impls: Box<[ImplId]>, } -#[tracing::instrument(skip_all, fields(name = ?name, visible_from_module, receiver_ty))] -fn iterate_trait_method_candidates<'db>( - self_ty: Ty<'db>, - table: &mut InferenceTable<'db>, - traits_in_scope: &FxHashSet<TraitId>, - name: Option<&Name>, - receiver_ty: Option<Ty<'db>>, - receiver_adjustments: Option<ReceiverAdjustments>, - mode: LookupMode, - callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>, -) -> ControlFlow<()> { - let db = table.db; - - let canonical_self_ty = table.canonicalize(self_ty); - let krate = table.trait_env.krate; - - 'traits: for &t in traits_in_scope { - let data = db.trait_signature(t); - - // Traits annotated with `#[rustc_skip_during_method_dispatch]` are skipped during - // method resolution, if the receiver is an array, and we're compiling for editions before - // 2021. - // This is to make `[a].into_iter()` not break code with the new `IntoIterator` impl for - // arrays. - if data.flags.contains(TraitFlags::SKIP_ARRAY_DURING_METHOD_DISPATCH) - && matches!(self_ty.kind(), TyKind::Array(..)) - { - // FIXME: this should really be using the edition of the method name's span, in case it - // comes from a macro - if !krate.data(db).edition.at_least_2021() { - continue; - } - } - if data.flags.contains(TraitFlags::SKIP_BOXED_SLICE_DURING_METHOD_DISPATCH) - && matches!( - self_ty.kind(), TyKind::Adt(adt_def, subst) - if is_box(table.db, adt_def.def_id().0) - && matches!(subst.type_at(0).kind(), TyKind::Slice(..)) - ) - { - // FIXME: this should really be using the edition of the method name's span, in case it - // comes from a macro - if !krate.data(db).edition.at_least_2024() { - continue; - } - } +#[derive(Default)] +struct OneTraitImplsBuilder { + non_blanket_impls: FxHashMap<SimplifiedType, Vec<ImplId>>, + blanket_impls: Vec<ImplId>, +} - // we'll be lazy about checking whether the type implements the - // trait, but if we find out it doesn't, we'll skip the rest of the - // iteration - let mut known_implemented = false; - for &(_, item) in t.trait_items(db).items.iter() { - // Don't pass a `visible_from_module` down to `is_valid_candidate`, - // since only inherent methods should be included into visibility checking. - let visible = match is_valid_trait_method_candidate( - table, - t, - name, - receiver_ty, - item, - self_ty, - mode, - ) { - IsValidCandidate::Yes => true, - IsValidCandidate::NotVisible => false, - IsValidCandidate::No => continue, - }; - if !known_implemented { - let goal = generic_implements_goal_ns(table, t, canonical_self_ty); - if next_trait_solve_canonical_in_ctxt(&table.infer_ctxt, goal).no_solution() { - continue 'traits; - } - } - known_implemented = true; - callback(receiver_adjustments.clone().unwrap_or_default(), item, visible)?; - } +impl OneTraitImplsBuilder { + fn finish(self) -> OneTraitImpls { + let mut non_blanket_impls = self + .non_blanket_impls + .into_iter() + .map(|(self_ty, impls)| (self_ty, impls.into_boxed_slice())) + .collect::<FxHashMap<_, _>>(); + non_blanket_impls.shrink_to_fit(); + let blanket_impls = self.blanket_impls.into_boxed_slice(); + OneTraitImpls { non_blanket_impls, blanket_impls } } - ControlFlow::Continue(()) } -#[tracing::instrument(skip_all, fields(name = ?name, visible_from_module, receiver_ty))] -fn iterate_inherent_methods<'db>( - self_ty: Ty<'db>, - table: &mut InferenceTable<'db>, - name: Option<&Name>, - receiver_ty: Option<Ty<'db>>, - receiver_adjustments: Option<ReceiverAdjustments>, - visible_from_module: VisibleFromModule, - mode: LookupMode, - callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>, -) -> ControlFlow<()> { - let db = table.db; - let env = table.trait_env.clone(); - - // For trait object types and placeholder types with trait bounds, the methods of the trait and - // its super traits are considered inherent methods. This matters because these methods have - // higher priority than the other traits' methods, which would be considered in - // `iterate_trait_method_candidates()` only after this function. - match self_ty.kind() { - TyKind::Param(_) => { - let env = table.trait_env.clone(); - let traits = - env.traits_in_scope_from_clauses(self_ty).flat_map(|t| all_super_traits(db, t)); - iterate_inherent_trait_methods( - self_ty, - table, - name, - receiver_ty, - receiver_adjustments.clone(), - callback, - traits, - mode, - )?; - } - TyKind::Dynamic(bounds, _) => { - if let Some(principal_trait) = bounds.principal_def_id() { - let traits = all_super_traits(db, principal_trait.0); - iterate_inherent_trait_methods( - self_ty, - table, - name, - receiver_ty, - receiver_adjustments.clone(), - callback, - traits.into_iter(), - mode, - )?; - } - } - _ => {} - } +#[derive(Debug, PartialEq)] +pub struct TraitImpls { + map: FxHashMap<TraitId, OneTraitImpls>, +} - let def_crates = match def_crates(db, self_ty, env.krate) { - Some(k) => k, - None => return ControlFlow::Continue(()), - }; +#[salsa::tracked] +impl TraitImpls { + #[salsa::tracked(returns(ref))] + pub fn for_crate(db: &dyn HirDatabase, krate: Crate) -> Arc<Self> { + let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered(); - let (module, mut block) = match visible_from_module { - VisibleFromModule::Filter(module) => (Some(module), module.containing_block()), - VisibleFromModule::IncludeBlock(block) => (None, Some(block)), - VisibleFromModule::None => (None, None), - }; + let crate_def_map = crate_def_map(db, krate); + let result = Self::collect_def_map(db, crate_def_map); + Arc::new(result) + } - while let Some(block_id) = block { - if let Some(impls) = db.inherent_impls_in_block(block_id) { - impls_for_self_ty( - &impls, - self_ty, - table, - name, - receiver_ty, - receiver_adjustments.clone(), - module, - callback, - )?; - } + #[salsa::tracked(returns(ref))] + pub fn for_block(db: &dyn HirDatabase, block: BlockId) -> Option<Box<Self>> { + let _p = tracing::info_span!("inherent_impls_in_block_query").entered(); - block = block_def_map(db, block_id).parent().and_then(|module| module.containing_block()); + let block_def_map = block_def_map(db, block); + let result = Self::collect_def_map(db, block_def_map); + if result.map.is_empty() { None } else { Some(Box::new(result)) } } - for krate in def_crates { - let impls = db.inherent_impls_in_crate(krate); - impls_for_self_ty( - &impls, - self_ty, - table, - name, - receiver_ty, - receiver_adjustments.clone(), - module, - callback, - )?; + #[salsa::tracked(returns(ref))] + pub fn for_crate_and_deps(db: &dyn HirDatabase, krate: Crate) -> Box<[Arc<Self>]> { + krate.transitive_deps(db).iter().map(|&dep| Self::for_crate(db, dep).clone()).collect() } - return ControlFlow::Continue(()); +} - #[tracing::instrument(skip_all, fields(name = ?name, visible_from_module, receiver_ty))] - fn iterate_inherent_trait_methods<'db>( - self_ty: Ty<'db>, - table: &mut InferenceTable<'db>, - name: Option<&Name>, - receiver_ty: Option<Ty<'db>>, - receiver_adjustments: Option<ReceiverAdjustments>, - callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>, - traits: impl Iterator<Item = TraitId>, - mode: LookupMode, - ) -> ControlFlow<()> { - let db = table.db; - for t in traits { - let data = t.trait_items(db); - for &(_, item) in data.items.iter() { - // We don't pass `visible_from_module` as all trait items should be visible. - let visible = match is_valid_trait_method_candidate( - table, - t, - name, - receiver_ty, - item, - self_ty, - mode, - ) { - IsValidCandidate::Yes => true, - IsValidCandidate::NotVisible => false, - IsValidCandidate::No => continue, - }; - callback(receiver_adjustments.clone().unwrap_or_default(), item, visible)?; - } - } - ControlFlow::Continue(()) - } +impl TraitImpls { + fn collect_def_map(db: &dyn HirDatabase, def_map: &DefMap) -> Self { + let mut map = FxHashMap::default(); + collect(db, def_map, &mut map); + let mut map = map + .into_iter() + .map(|(trait_id, trait_map)| (trait_id, trait_map.finish())) + .collect::<FxHashMap<_, _>>(); + map.shrink_to_fit(); + return Self { map }; + + fn collect( + db: &dyn HirDatabase, + def_map: &DefMap, + map: &mut FxHashMap<TraitId, OneTraitImplsBuilder>, + ) { + for (_module_id, module_data) in def_map.modules() { + for impl_id in module_data.scope.impls() { + // Reservation impls should be ignored during trait resolution, so we never need + // them during type analysis. See rust-lang/rust#64631 for details. + // + // FIXME: Reservation impls should be considered during coherence checks. If we are + // (ever) to implement coherence checks, this filtering should be done by the trait + // solver. + if db.attrs(impl_id.into()).by_key(sym::rustc_reservation_impl).exists() { + continue; + } + let trait_ref = match db.impl_trait(impl_id) { + Some(tr) => tr.instantiate_identity(), + None => continue, + }; + let self_ty = trait_ref.self_ty(); + let interner = DbInterner::new_with(db, None, None); + let entry = map.entry(trait_ref.def_id.0).or_default(); + match simplify_type(interner, self_ty, TreatParams::InstantiateWithInfer) { + Some(self_ty) => { + entry.non_blanket_impls.entry(self_ty).or_default().push(impl_id) + } + None => entry.blanket_impls.push(impl_id), + } + } - #[tracing::instrument(skip_all, fields(name = ?name, visible_from_module, receiver_ty))] - fn impls_for_self_ty<'db>( - impls: &InherentImpls, - self_ty: Ty<'db>, - table: &mut InferenceTable<'db>, - name: Option<&Name>, - receiver_ty: Option<Ty<'db>>, - receiver_adjustments: Option<ReceiverAdjustments>, - visible_from_module: Option<ModuleId>, - callback: &mut dyn FnMut(ReceiverAdjustments, AssocItemId, bool) -> ControlFlow<()>, - ) -> ControlFlow<()> { - for &impl_id in impls.for_self_ty(self_ty) { - for &(ref item_name, item) in impl_id.impl_items(table.db).items.iter() { - let visible = match is_valid_impl_method_candidate( - table, - self_ty, - receiver_ty, - visible_from_module, - name, - impl_id, - item, - item_name, - ) { - IsValidCandidate::Yes => true, - IsValidCandidate::NotVisible => false, - IsValidCandidate::No => continue, - }; - callback(receiver_adjustments.clone().unwrap_or_default(), item, visible)?; + // 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) { + collect(db, block_def_map, map); + } + } } } - ControlFlow::Continue(()) } -} -/// Returns the receiver type for the index trait call. -pub(crate) fn resolve_indexing_op<'db>( - table: &mut InferenceTable<'db>, - ty: Canonical<'db, Ty<'db>>, - index_trait: TraitId, -) -> Option<ReceiverAdjustments> { - let ty = table.instantiate_canonical(ty); - let deref_chain = autoderef_method_receiver(table, ty); - for (ty, adj) in deref_chain { - let goal = generic_implements_goal_ns(table, index_trait, ty); - if !next_trait_solve_canonical_in_ctxt(&table.infer_ctxt, goal).no_solution() { - return Some(adj); - } + pub fn blanket_impls(&self, for_trait: TraitId) -> &[ImplId] { + self.map.get(&for_trait).map(|it| &*it.blanket_impls).unwrap_or_default() } - None -} -// FIXME: Replace this with a `Try` impl once stable -macro_rules! check_that { - ($cond:expr) => { - if !$cond { - return IsValidCandidate::No; - } - }; -} + /// Queries whether `self_ty` has potentially applicable implementations of `trait_`. + pub fn has_impls_for_trait_and_self_ty( + &self, + trait_: TraitId, + self_ty: &SimplifiedType, + ) -> bool { + self.map.get(&trait_).is_some_and(|trait_impls| { + trait_impls.non_blanket_impls.contains_key(self_ty) + || !trait_impls.blanket_impls.is_empty() + }) + } -#[derive(Debug)] -enum IsValidCandidate { - Yes, - No, - NotVisible, -} + pub fn for_trait_and_self_ty(&self, trait_: TraitId, self_ty: &SimplifiedType) -> &[ImplId] { + self.map + .get(&trait_) + .and_then(|map| map.non_blanket_impls.get(self_ty)) + .map(|it| &**it) + .unwrap_or_default() + } -#[tracing::instrument(skip_all, fields(name))] -fn is_valid_impl_method_candidate<'db>( - table: &mut InferenceTable<'db>, - self_ty: Ty<'db>, - receiver_ty: Option<Ty<'db>>, - visible_from_module: Option<ModuleId>, - name: Option<&Name>, - impl_id: ImplId, - item: AssocItemId, - item_name: &Name, -) -> IsValidCandidate { - match item { - AssocItemId::FunctionId(f) => is_valid_impl_fn_candidate( - table, - impl_id, - f, - name, - receiver_ty, - self_ty, - visible_from_module, - item_name, - ), - AssocItemId::ConstId(c) => { - let db = table.db; - check_that!(receiver_ty.is_none()); - check_that!(name.is_none_or(|n| n == item_name)); - - if let Some(from_module) = visible_from_module - && !db.assoc_visibility(c.into()).is_visible_from(db, from_module) - { - cov_mark::hit!(const_candidate_not_visible); - return IsValidCandidate::NotVisible; + pub fn for_trait(&self, trait_: TraitId, mut callback: impl FnMut(&[ImplId])) { + if let Some(impls) = self.map.get(&trait_) { + callback(&impls.blanket_impls); + for impls in impls.non_blanket_impls.values() { + callback(impls); } - let self_ty_matches = table.run_in_snapshot(|table| { - let impl_args = table.fresh_args_for_item(impl_id.into()); - let expected_self_ty = - db.impl_self_ty(impl_id).instantiate(table.interner(), impl_args); - table.unify(expected_self_ty, self_ty) - }); - if !self_ty_matches { - cov_mark::hit!(const_candidate_self_type_mismatch); - return IsValidCandidate::No; - } - IsValidCandidate::Yes } - _ => IsValidCandidate::No, } -} - -/// Checks whether a given `AssocItemId` is applicable for `receiver_ty`. -#[tracing::instrument(skip_all, fields(name))] -fn is_valid_trait_method_candidate<'db>( - table: &mut InferenceTable<'db>, - trait_id: TraitId, - name: Option<&Name>, - receiver_ty: Option<Ty<'db>>, - item: AssocItemId, - self_ty: Ty<'db>, - mode: LookupMode, -) -> IsValidCandidate { - let db = table.db; - match item { - AssocItemId::FunctionId(fn_id) => { - let data = db.function_signature(fn_id); - - check_that!(name.is_none_or(|n| n == &data.name)); - - table.run_in_snapshot(|table| { - let impl_subst = table.fresh_args_for_item(trait_id.into()); - let expect_self_ty = impl_subst.type_at(0); - - check_that!(table.unify(expect_self_ty, self_ty)); - - if let Some(receiver_ty) = receiver_ty { - check_that!(data.has_self_param()); - - let args = table.fill_rest_fresh_args(fn_id.into(), impl_subst); - - let sig = db.callable_item_signature(fn_id.into()); - let expected_receiver = sig - .map_bound(|s| s.skip_binder().inputs_and_output.as_slice()[0]) - .instantiate(table.interner(), args); - - // FIXME: Clean up this mess with some context struct like rustc's `ProbeContext` - let variance = match mode { - LookupMode::MethodCall => rustc_type_ir::Variance::Covariant, - LookupMode::Path => rustc_type_ir::Variance::Invariant, - }; - let res = table - .infer_ctxt - .at(&ObligationCause::dummy(), table.trait_env.env) - .relate(expected_receiver, variance, receiver_ty); - let Ok(infer_ok) = res else { - return IsValidCandidate::No; - }; - if !infer_ok.obligations.is_empty() { - let mut ctxt = ObligationCtxt::new(&table.infer_ctxt); - ctxt.register_obligations(infer_ok.into_obligations()); - // FIXME: Are we doing this correctly? Probably better to follow rustc more closely. - check_that!(ctxt.try_evaluate_obligations().is_empty()); - } - - check_that!(table.unify(receiver_ty, expected_receiver)); - } - - IsValidCandidate::Yes - }) - } - AssocItemId::ConstId(c) => { - check_that!(receiver_ty.is_none()); - check_that!(name.is_none_or(|n| db.const_signature(c).name.as_ref() == Some(n))); - - IsValidCandidate::Yes + pub fn for_self_ty(&self, self_ty: &SimplifiedType, mut callback: impl FnMut(&[ImplId])) { + for for_trait in self.map.values() { + if let Some(for_ty) = for_trait.non_blanket_impls.get(self_ty) { + callback(for_ty); + } } - _ => IsValidCandidate::No, } -} -#[tracing::instrument(skip_all, fields(name))] -fn is_valid_impl_fn_candidate<'db>( - table: &mut InferenceTable<'db>, - impl_id: ImplId, - fn_id: FunctionId, - name: Option<&Name>, - receiver_ty: Option<Ty<'db>>, - self_ty: Ty<'db>, - visible_from_module: Option<ModuleId>, - item_name: &Name, -) -> IsValidCandidate { - check_that!(name.is_none_or(|n| n == item_name)); - - let db = table.db; - let data = db.function_signature(fn_id); - - if let Some(from_module) = visible_from_module - && !db.assoc_visibility(fn_id.into()).is_visible_from(db, from_module) - { - cov_mark::hit!(autoderef_candidate_not_visible); - return IsValidCandidate::NotVisible; + pub fn for_each_crate_and_block( + db: &dyn HirDatabase, + krate: Crate, + block: Option<BlockId>, + for_each: &mut dyn FnMut(&TraitImpls), + ) { + let blocks = std::iter::successors(block, |block| block.loc(db).module.containing_block()); + blocks.filter_map(|block| Self::for_block(db, block).as_deref()).for_each(&mut *for_each); + Self::for_crate_and_deps(db, krate).iter().map(|it| &**it).for_each(for_each); } - table.run_in_snapshot(|table| { - let _p = tracing::info_span!("subst_for_def").entered(); - let impl_subst = table.infer_ctxt.fresh_args_for_item(impl_id.into()); - let expect_self_ty = db.impl_self_ty(impl_id).instantiate(table.interner(), &impl_subst); - check_that!(table.unify(expect_self_ty, self_ty)); - - if let Some(receiver_ty) = receiver_ty { - let _p = tracing::info_span!("check_receiver_ty").entered(); - check_that!(data.has_self_param()); - - let args = table.infer_ctxt.fresh_args_for_item(fn_id.into()); - - let sig = db.callable_item_signature(fn_id.into()); - let expected_receiver = sig - .map_bound(|s| s.skip_binder().inputs_and_output.as_slice()[0]) - .instantiate(table.interner(), args); - - check_that!(table.unify(receiver_ty, expected_receiver)); - } - - // We need to consider the bounds on the impl to distinguish functions of the same name - // for a type. - let predicates = db.generic_predicates(impl_id.into()); - let Some(predicates) = predicates.instantiate(table.interner(), impl_subst) else { - return IsValidCandidate::Yes; + /// Like [`Self::for_each_crate_and_block()`], but takes in account two blocks, one for a trait and one for a self type. + pub fn for_each_crate_and_block_trait_and_type( + db: &dyn HirDatabase, + krate: Crate, + type_block: Option<BlockId>, + trait_block: Option<BlockId>, + for_each: &mut dyn FnMut(&TraitImpls), + ) { + let in_self_and_deps = TraitImpls::for_crate_and_deps(db, krate); + in_self_and_deps.iter().for_each(|impls| for_each(impls)); + + // We must not provide duplicate impls to the solver. Therefore we work with the following strategy: + // start from each block, and walk ancestors until you meet the other block. If they never meet, + // that means there can't be duplicate impls; if they meet, we stop the search of the deeper block. + // This breaks when they are equal (both will stop immediately), therefore we handle this case + // specifically. + let blocks_iter = |block: Option<BlockId>| { + std::iter::successors(block, |block| block.loc(db).module.containing_block()) }; - - let mut ctxt = ObligationCtxt::new(&table.infer_ctxt); - - ctxt.register_obligations(predicates.into_iter().map(|p| { - PredicateObligation::new( - table.interner(), - ObligationCause::new(), - table.trait_env.env, - p.0, - ) - })); - - if ctxt.try_evaluate_obligations().is_empty() { - IsValidCandidate::Yes + let for_each_block = |current_block: Option<BlockId>, other_block: Option<BlockId>| { + blocks_iter(current_block) + .take_while(move |&block| { + other_block.is_none_or(|other_block| other_block != block) + }) + .filter_map(move |block| TraitImpls::for_block(db, block).as_deref()) + }; + if trait_block == type_block { + blocks_iter(trait_block) + .filter_map(|block| TraitImpls::for_block(db, block).as_deref()) + .for_each(for_each); } else { - IsValidCandidate::No + for_each_block(trait_block, type_block).for_each(&mut *for_each); + for_each_block(type_block, trait_block).for_each(for_each); } - }) -} - -/// This creates Substs for a trait with the given Self type and type variables -/// for all other parameters, to query the trait solver with it. -#[tracing::instrument(skip_all)] -fn generic_implements_goal_ns<'db>( - table: &mut InferenceTable<'db>, - trait_: TraitId, - self_ty: Canonical<'db, Ty<'db>>, -) -> Canonical<'db, Goal<'db, Predicate<'db>>> { - let args = table.infer_ctxt.fresh_args_for_item(SolverDefId::TraitId(trait_)); - let self_ty = table.instantiate_canonical(self_ty); - let trait_ref = - rustc_type_ir::TraitRef::new_from_args(table.infer_ctxt.interner, trait_.into(), args) - .with_replaced_self_ty(table.infer_ctxt.interner, self_ty); - let goal = Goal::new(table.infer_ctxt.interner, table.trait_env.env, trait_ref); - - table.canonicalize(goal) -} - -fn autoderef_method_receiver<'db>( - table: &mut InferenceTable<'db>, - ty: Ty<'db>, -) -> Vec<(Canonical<'db, Ty<'db>>, ReceiverAdjustments)> { - let interner = table.interner(); - let mut deref_chain = Vec::new(); - let mut autoderef = autoderef::Autoderef::new_no_tracking(table, ty).use_receiver_trait(); - while let Some((ty, derefs)) = autoderef.next() { - deref_chain.push(( - autoderef.table.canonicalize(ty), - 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((rustc_type_ir::Array(parameters, _), variables, max_universe, adj)) = - deref_chain.last().map(|d| (d.0.value.kind(), d.0.variables, d.0.max_universe, d.1.clone())) - { - let unsized_ty = Ty::new_slice(interner, parameters); - deref_chain.push(( - Canonical { max_universe, value: unsized_ty, variables }, - ReceiverAdjustments { unsize_array: true, ..adj.clone() }, - )); } - deref_chain } |