| //! This module is concerned with finding methods that a given type provides. |
| //! For details about how this works in rustc, see the method lookup page in the |
| //! [rustc guide] and the corresponding code mostly in |
| //! [`rustc_hir_typeck/method/probe.rs`]. |
| //! |
| //! [rustc guide]: https://rust-lang.github.io/rustc-guide/method-lookup.html |
| //! [`rustc_hir_typeck/method/probe.rs`]: https://github.com/rust-lang/rust/blob/5503df87342a73d0c29126a7e08dc9c1255c46ad/compiler/rustc_hir_typeck/src/method/probe.rs |
| |
| mod confirm; |
| mod probe; |
| |
| use either::Either; |
| use hir_expand::name::Name; |
| use salsa::SalsaValue; |
| use span::Edition; |
| use tracing::{debug, instrument}; |
| |
| use base_db::Crate; |
| use hir_def::{ |
| AssocItemId, BlockIdLt, BuiltinDeriveImplId, ConstId, FunctionId, GenericParamId, HasModule, |
| ImplId, ItemContainerId, ModuleId, TraitId, |
| attrs::AttrFlags, |
| builtin_derive::BuiltinDeriveImplMethod, |
| expr_store::{Body, path::GenericArgs as HirGenericArgs}, |
| hir::{ExprId, generics::GenericParams}, |
| lang_item::LangItems, |
| nameres::{DefMap, block_def_map, crate_def_map}, |
| resolver::Resolver, |
| signatures::{ConstSignature, FunctionSignature}, |
| unstable_features::UnstableFeatures, |
| }; |
| use rustc_hash::{FxHashMap, FxHashSet}; |
| use rustc_type_ir::{ |
| TypeFoldable, TypeVisitableExt, VisitorResult, |
| fast_reject::{TreatParams, simplify_type}, |
| inherent::{BoundExistentialPredicates, IntoKind}, |
| try_visit, |
| }; |
| use stdx::impl_from; |
| use triomphe::Arc; |
| |
| use crate::{ |
| InferenceDiagnostic, Span, all_super_traits, |
| db::HirDatabase, |
| infer::{InferenceContext, unify::InferenceTable}, |
| lower::GenericPredicates, |
| next_solver::{ |
| AnyImplId, Binder, ClauseKind, DbInterner, FnSig, GenericArgs, ParamEnv, PredicateKind, |
| SimplifiedType, SolverDefId, TraitRef, Ty, TyKind, TypingMode, Unnormalized, |
| infer::{ |
| BoundRegionConversionTime, DbInternerInferExt, InferCtxt, InferOk, |
| resolve::ReplaceInferWithError, |
| select::ImplSource, |
| traits::{Obligation, ObligationCause, PredicateObligations}, |
| }, |
| obligation_ctxt::ObligationCtxt, |
| util::clauses_as_obligations, |
| }, |
| traits::ParamEnvAndCrate, |
| }; |
| |
| pub use self::probe::{ |
| Candidate, CandidateKind, CandidateStep, CandidateWithPrivate, Mode, Pick, PickKind, |
| }; |
| |
| pub struct MethodResolutionContext<'a, 'db> { |
| pub infcx: &'a InferCtxt<'db>, |
| pub resolver: &'a Resolver<'db>, |
| pub param_env: ParamEnv<'db>, |
| pub traits_in_scope: &'a FxHashSet<TraitId>, |
| pub edition: Edition, |
| pub features: &'a UnstableFeatures, |
| pub call_span: Span, |
| pub receiver_span: Span, |
| } |
| |
| #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, salsa::SalsaValue)] |
| pub enum CandidateId { |
| FunctionId(FunctionId), |
| ConstId(ConstId), |
| } |
| impl_from!(FunctionId, ConstId for CandidateId); |
| |
| 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, |
| } |
| } |
| } |
| |
| #[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>, |
| |
| /// Instantiated method signature, i.e., it has been |
| /// instantiated, normalized, and has had late-bound |
| /// lifetimes replaced with inference variables. |
| pub sig: FnSig<'db>, |
| } |
| |
| #[derive(Debug)] |
| pub enum MethodError<'db> { |
| /// Did not find an applicable method. |
| NoMatch, |
| |
| /// Multiple methods might apply. |
| Ambiguity(Vec<CandidateSource>), |
| |
| /// Found an applicable method, but it is not visible. |
| PrivateMatch(Pick<'db>), |
| |
| /// Found a `Self: Sized` bound where `Self` is a trait object. |
| IllegalSizedBound { candidates: Vec<FunctionId>, needs_mut: bool }, |
| |
| /// Error has already been emitted, no need to emit another one. |
| ErrorReported, |
| } |
| |
| // 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(AnyImplId), |
| Trait(TraitId), |
| } |
| |
| impl<'db> InferenceContext<'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(call_expr, receiver, name, self_ty) { |
| Ok(it) => (it, true), |
| Err(MethodError::PrivateMatch(it)) => { |
| // FIXME: Report error. |
| (it, false) |
| } |
| Err(err) => return Err(err), |
| }; |
| |
| let result = self.confirm_method(&pick, self_ty, call_expr, generic_args); |
| debug!("result = {:?}", result); |
| |
| if result.illegal_sized_bound { |
| self.push_diagnostic(InferenceDiagnostic::MethodCallIllegalSizedBound { call_expr }); |
| } |
| |
| self.write_expr_adj(receiver, result.adjustments); |
| self.write_method_resolution(call_expr, result.callee.def_id, result.callee.args); |
| |
| Ok((result.callee, is_visible)) |
| } |
| |
| #[instrument(level = "debug", skip(self))] |
| pub(crate) fn lookup_probe( |
| &self, |
| call_expr: ExprId, |
| receiver: ExprId, |
| method_name: Name, |
| self_ty: Ty<'db>, |
| ) -> probe::PickResult<'db> { |
| self.with_method_resolution(call_expr.into(), receiver.into(), |ctx| { |
| let pick = ctx.probe_for_name(probe::Mode::MethodCall, method_name, self_ty)?; |
| Ok(pick) |
| }) |
| } |
| |
| pub(crate) fn with_method_resolution<R>( |
| &self, |
| call_span: Span, |
| receiver_span: Span, |
| 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, |
| param_env: self.table.param_env, |
| traits_in_scope, |
| edition: self.edition, |
| features: self.features, |
| call_span, |
| receiver_span, |
| }; |
| f(&ctx) |
| } |
| } |
| |
| /// 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)] |
| 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, |
| cause: ObligationCause, |
| trait_def_id: TraitId, |
| method_item: FunctionId, |
| 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") |
| } |
| 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 { |
| // 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.var_for_def(param_id, cause.span()) |
| } |
| } |
| }, |
| ); |
| |
| let obligation = Obligation::new( |
| self.interner(), |
| cause, |
| self.param_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) |
| } |
| }; |
| |
| 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(); |
| |
| 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) |
| .skip_norm_wip(); |
| let fn_sig = self.infer_ctxt.instantiate_binder_with_fresh_vars( |
| cause.span(), |
| 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(interner, args.as_slice()).map(Unnormalized::skip_norm_wip), |
| cause, |
| self.param_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, |
| self.param_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>( |
| infcx: &InferCtxt<'db>, |
| env: ParamEnv<'db>, |
| const_id: ConstId, |
| subs: GenericArgs<'db>, |
| ) -> (ConstId, GenericArgs<'db>) { |
| let interner = infcx.interner; |
| let db = interner.db; |
| |
| let trait_id = match const_id.loc(db).container { |
| ItemContainerId::TraitId(id) => id, |
| _ => return (const_id, subs), |
| }; |
| let trait_ref = TraitRef::new_from_args(interner, trait_id.into(), subs); |
| |
| let const_signature = ConstSignature::of(db, const_id); |
| let name = match const_signature.name.as_ref() { |
| Some(name) => name, |
| None => return (const_id, subs), |
| }; |
| |
| lookup_impl_assoc_item_for_trait_ref(infcx, trait_ref, env, name) |
| .and_then(|assoc| { |
| if let (Either::Left(AssocItemId::ConstId(id)), s) = assoc { |
| Some((id, s)) |
| } else { |
| None |
| } |
| }) |
| .unwrap_or((const_id, subs)) |
| } |
| |
| /// Checks if the self parameter of `Trait` method is the `dyn Trait` and we should |
| /// call the method using the vtable. |
| pub fn is_dyn_method<'db>( |
| interner: DbInterner<'db>, |
| _env: ParamEnv<'db>, |
| func: FunctionId, |
| fn_subst: GenericArgs<'db>, |
| ) -> Option<usize> { |
| let db = interner.db; |
| |
| let ItemContainerId::TraitId(trait_id) = func.loc(db).container else { |
| return None; |
| }; |
| let trait_params = GenericParams::of(db, trait_id.into()).len(); |
| let fn_params = fn_subst.len() - trait_params; |
| let trait_ref = TraitRef::new_from_args( |
| interner, |
| trait_id.into(), |
| GenericArgs::new_from_slice(&fn_subst[..trait_params]), |
| ); |
| let self_ty = trait_ref.self_ty(); |
| if let TyKind::Dynamic(d, _) = self_ty.kind() { |
| // rustc doesn't accept `impl Foo<2> for dyn Foo<5>`, so if the trait id is equal, no matter |
| // what the generics are, we are sure that the method is come from the vtable. |
| let is_my_trait_in_bounds = d |
| .principal_def_id() |
| .is_some_and(|trait_| all_super_traits(db, trait_.0).contains(&trait_id)); |
| if is_my_trait_in_bounds { |
| return Some(fn_params); |
| } |
| } |
| None |
| } |
| |
| /// Looks up the impl method that actually runs for the trait method `func`. |
| /// |
| /// Returns `func` if it's not a method defined in a trait or the lookup failed. |
| pub(crate) fn lookup_impl_method_query<'db>( |
| db: &'db dyn HirDatabase, |
| env: ParamEnvAndCrate<'db>, |
| func: FunctionId, |
| fn_subst: GenericArgs<'db>, |
| ) -> (Either<FunctionId, (BuiltinDeriveImplId, BuiltinDeriveImplMethod)>, GenericArgs<'db>) { |
| let interner = DbInterner::new_with(db, env.krate); |
| let infcx = interner.infer_ctxt().build(TypingMode::PostAnalysis); |
| |
| let ItemContainerId::TraitId(trait_id) = func.loc(db).container else { |
| return (Either::Left(func), fn_subst); |
| }; |
| let trait_params = GenericParams::of(db, trait_id.into()).len(); |
| let trait_ref = TraitRef::new_from_args( |
| interner, |
| trait_id.into(), |
| GenericArgs::new_from_slice(&fn_subst[..trait_params]), |
| ); |
| |
| let name = &FunctionSignature::of(db, func).name; |
| let Some((impl_fn, impl_subst)) = |
| lookup_impl_assoc_item_for_trait_ref(&infcx, trait_ref, env.param_env, name).and_then( |
| |(assoc, impl_args)| { |
| let assoc = match assoc { |
| Either::Left(AssocItemId::FunctionId(id)) => Either::Left(id), |
| Either::Right(it) => Either::Right(it), |
| _ => return None, |
| }; |
| Some((assoc, impl_args)) |
| }, |
| ) |
| else { |
| return (Either::Left(func), fn_subst); |
| }; |
| |
| ( |
| impl_fn, |
| GenericArgs::new_from_iter( |
| interner, |
| impl_subst.iter().chain(fn_subst.iter().skip(trait_params)), |
| ), |
| ) |
| } |
| |
| fn lookup_impl_assoc_item_for_trait_ref<'db>( |
| infcx: &InferCtxt<'db>, |
| trait_ref: TraitRef<'db>, |
| env: ParamEnv<'db>, |
| name: &Name, |
| ) -> Option<(Either<AssocItemId, (BuiltinDeriveImplId, BuiltinDeriveImplMethod)>, GenericArgs<'db>)> |
| { |
| let (impl_id, impl_subst) = find_matching_impl(infcx, env, trait_ref)?; |
| let impl_id = match impl_id { |
| AnyImplId::ImplId(it) => it, |
| AnyImplId::BuiltinDeriveImplId(impl_) => { |
| return impl_ |
| .loc(infcx.interner.db) |
| .trait_ |
| .get_method(name.symbol()) |
| .map(|method| (Either::Right((impl_, method)), impl_subst)); |
| } |
| }; |
| let item = |
| impl_id.impl_items(infcx.interner.db).items.iter().find_map(|(n, it)| match *it { |
| AssocItemId::FunctionId(f) => (n == name).then_some(AssocItemId::FunctionId(f)), |
| AssocItemId::ConstId(c) => (n == name).then_some(AssocItemId::ConstId(c)), |
| AssocItemId::TypeAliasId(_) => None, |
| })?; |
| Some((Either::Left(item), impl_subst)) |
| } |
| |
| pub(crate) fn find_matching_impl<'db>( |
| infcx: &InferCtxt<'db>, |
| env: ParamEnv<'db>, |
| trait_ref: TraitRef<'db>, |
| ) -> Option<(AnyImplId, GenericArgs<'db>)> { |
| let trait_ref = infcx.at(&ObligationCause::dummy(), env).deeply_normalize(trait_ref).ok()?; |
| |
| let obligation = Obligation::new(infcx.interner, ObligationCause::dummy(), env, trait_ref); |
| |
| let selection = infcx.select(&obligation).ok()??; |
| |
| // Currently, we use a fulfillment context to completely resolve |
| // all nested obligations. This is because they can inform the |
| // inference of the impl's type parameters. |
| let mut ocx = ObligationCtxt::new(infcx); |
| let impl_source = selection.map(|obligation| ocx.register_obligation(obligation)); |
| |
| let errors = ocx.evaluate_obligations_error_on_ambiguity(); |
| if !errors.is_empty() { |
| return None; |
| } |
| |
| let impl_source = infcx.resolve_vars_if_possible(impl_source); |
| if impl_source.has_non_region_infer() { |
| return None; |
| } |
| |
| // Selection may leave region inference variables unresolved; replace them before they escape |
| // this inference context. |
| // |
| // FIXME: decide whether inferred regions should be replaced with error or erased. |
| match impl_source { |
| ImplSource::UserDefined(impl_source) => Some(( |
| impl_source.impl_def_id, |
| impl_source.args.fold_with(&mut ReplaceInferWithError::new(infcx.interner)), |
| )), |
| ImplSource::Param(_) | ImplSource::Builtin(..) => None, |
| } |
| } |
| |
| #[salsa::tracked(returns(ref))] |
| fn crates_containing_incoherent_inherent_impls(db: &dyn HirDatabase, krate: Crate) -> Box<[Crate]> { |
| let _p = tracing::info_span!("crates_containing_incoherent_inherent_impls").entered(); |
| // We assume that only sysroot crates contain `#[rustc_has_incoherent_inherent_impls]` |
| // impls, since this is an internal feature and only std uses it. |
| krate.transitive_deps(db).into_iter().filter(|krate| krate.data(db).origin.is_lang()).collect() |
| } |
| |
| pub fn with_incoherent_inherent_impls<'db>( |
| db: &'db dyn HirDatabase, |
| krate: Crate, |
| self_ty: &SimplifiedType<'db>, |
| mut callback: impl FnMut(&[ImplId]), |
| ) { |
| let has_incoherent_impls = match self_ty.def() { |
| Some(def_id) => match def_id.try_into() { |
| Ok(def_id) => AttrFlags::query(db, def_id) |
| .contains(AttrFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS), |
| Err(()) => true, |
| }, |
| _ => true, |
| }; |
| if !has_incoherent_impls { |
| return; |
| } |
| let _p = tracing::info_span!("incoherent_inherent_impls").entered(); |
| let crates = crates_containing_incoherent_inherent_impls(db, krate); |
| for &krate in crates { |
| let impls = InherentImpls::for_crate(db, krate); |
| callback(impls.for_self_ty(self_ty)); |
| } |
| } |
| |
| 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, |
| } |
| } |
| |
| #[derive(Debug, PartialEq, Eq, SalsaValue)] |
| pub struct InherentImpls<'db> { |
| // SAFETY: necessary due to `SimplifiedType<'db>`. |
| // It's safe to retain, as it only contains `SolverDefId<'db>` (which is `SalsaValue`), |
| // and no `&'db` references. |
| #[salsa_value(unsafe(prove(SolverDefId<'db>: SalsaValue)))] |
| map: FxHashMap<SimplifiedType<'db>, Box<[ImplId]>>, |
| } |
| |
| #[salsa::tracked] |
| impl<'db> InherentImpls<'db> { |
| #[salsa::tracked(returns(ref))] |
| pub fn for_crate(db: &'db dyn HirDatabase, krate: Crate) -> InherentImpls<'db> { |
| let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered(); |
| |
| let crate_def_map = crate_def_map(db, krate); |
| |
| Self::collect_def_map(db, crate_def_map) |
| } |
| |
| #[salsa::tracked(returns(ref))] |
| pub fn for_block( |
| db: &'db dyn HirDatabase, |
| block: BlockIdLt<'db>, |
| ) -> Option<Box<InherentImpls<'db>>> { |
| let _p = tracing::info_span!("inherent_impls_in_block_query").entered(); |
| |
| 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)) } |
| } |
| } |
| |
| impl<'db> InherentImpls<'db> { |
| fn collect_def_map(db: &'db dyn HirDatabase, def_map: &'db 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>( |
| db: &'db dyn HirDatabase, |
| def_map: &DefMap, |
| map: &mut FxHashMap<SimplifiedType<'db>, Vec<ImplId>>, |
| ) { |
| for (_module_id, module_data) in def_map.modules() { |
| for impl_id in module_data.scope.inherent_impls() { |
| let interner = DbInterner::new_no_crate(db); |
| let self_ty = db.impl_self_ty(impl_id); |
| let self_ty = self_ty.instantiate_identity().skip_norm_wip(); |
| if let Some(self_ty) = |
| simplify_type(interner, self_ty, TreatParams::InstantiateWithInfer) |
| { |
| map.entry(self_ty).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 = Body::of(db, konst.into()); |
| for (_, block_def_map) in body.blocks(db) { |
| collect(db, block_def_map, map); |
| } |
| } |
| } |
| } |
| } |
| |
| pub fn for_self_ty(&self, self_ty: &SimplifiedType<'db>) -> &[ImplId] { |
| self.map.get(self_ty).map(|it| &**it).unwrap_or_default() |
| } |
| |
| pub fn for_each_crate_and_block( |
| db: &'db dyn HirDatabase, |
| krate: Crate, |
| block: Option<BlockIdLt<'db>>, |
| for_each: &mut dyn FnMut(&InherentImpls<'db>), |
| ) { |
| let blocks = std::iter::successors(block, |block| block.module(db).block(db)); |
| blocks.filter_map(|block| Self::for_block(db, block).as_deref()).for_each(&mut *for_each); |
| for_each(Self::for_crate(db, krate)); |
| } |
| } |
| |
| #[derive(Debug, PartialEq, SalsaValue)] |
| struct OneTraitImpls<'db> { |
| // SAFETY: necessary due to `SimplifiedType<'db>`. |
| // It's safe to retain, as it only contains `SolverDefId<'db>` (which is `SalsaValue`), |
| // and no `&'db` references. |
| #[salsa_value(unsafe(prove(SolverDefId<'db>: SalsaValue)))] |
| non_blanket_impls: FxHashMap<SimplifiedType<'db>, (Box<[ImplId]>, Box<[BuiltinDeriveImplId]>)>, |
| blanket_impls: Box<[ImplId]>, |
| } |
| |
| #[derive(Default)] |
| struct OneTraitImplsBuilder<'db> { |
| non_blanket_impls: FxHashMap<SimplifiedType<'db>, (Vec<ImplId>, Vec<BuiltinDeriveImplId>)>, |
| blanket_impls: Vec<ImplId>, |
| } |
| |
| impl<'db> OneTraitImplsBuilder<'db> { |
| fn finish(self) -> OneTraitImpls<'db> { |
| let mut non_blanket_impls = self |
| .non_blanket_impls |
| .into_iter() |
| .map(|(self_ty, (impls, builtin_derive_impls))| { |
| (self_ty, (impls.into_boxed_slice(), builtin_derive_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 } |
| } |
| } |
| |
| #[derive(Debug, PartialEq, SalsaValue)] |
| pub struct TraitImpls<'db> { |
| map: FxHashMap<TraitId, OneTraitImpls<'db>>, |
| } |
| |
| #[salsa::tracked] |
| impl<'db> TraitImpls<'db> { |
| #[salsa::tracked(returns(ref))] |
| pub fn for_crate(db: &'db dyn HirDatabase, krate: Crate) -> Arc<TraitImpls<'db>> { |
| let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered(); |
| |
| let crate_def_map = crate_def_map(db, krate); |
| let result = Self::collect_def_map(db, crate_def_map); |
| Arc::new(result) |
| } |
| |
| #[salsa::tracked(returns(as_deref))] |
| pub fn for_block( |
| db: &'db dyn HirDatabase, |
| block: BlockIdLt<'db>, |
| ) -> Option<Box<TraitImpls<'db>>> { |
| let _p = tracing::info_span!("inherent_impls_in_block_query").entered(); |
| |
| 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)) } |
| } |
| |
| #[salsa::tracked(returns(deref))] |
| pub fn for_crate_and_deps(db: &'db dyn HirDatabase, krate: Crate) -> Box<[Arc<Self>]> { |
| krate.transitive_deps(db).iter().map(|&dep| Self::for_crate(db, dep).clone()).collect() |
| } |
| } |
| |
| impl<'db> TraitImpls<'db> { |
| fn collect_def_map(db: &'db dyn HirDatabase, def_map: &DefMap) -> Self { |
| let lang_items = hir_def::lang_item::lang_items(db, def_map.krate()); |
| let mut map = FxHashMap::default(); |
| collect(db, def_map, lang_items, &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>( |
| db: &'db dyn HirDatabase, |
| def_map: &DefMap, |
| lang_items: &LangItems, |
| map: &mut FxHashMap<TraitId, OneTraitImplsBuilder<'db>>, |
| ) { |
| for (_module_id, module_data) in def_map.modules() { |
| for impl_id in module_data.scope.trait_impls() { |
| let trait_ref = match db.impl_trait(impl_id) { |
| Some(tr) => tr.instantiate_identity().skip_norm_wip(), |
| None => continue, |
| }; |
| // 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 AttrFlags::query(db, impl_id.into()) |
| .contains(AttrFlags::RUSTC_RESERVATION_IMPL) |
| { |
| continue; |
| } |
| |
| let self_ty = trait_ref.self_ty(); |
| if self_ty_has_error_constructor(self_ty) { |
| // If we see `impl Foo for NoSuchType`, just ignore it. |
| continue; |
| } |
| |
| let interner = DbInterner::new_no_crate(db); |
| 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().0.push(impl_id) |
| } |
| None => entry.blanket_impls.push(impl_id), |
| } |
| } |
| |
| for impl_id in module_data.scope.builtin_derive_impls() { |
| let loc = impl_id.loc(db); |
| let Some(trait_id) = loc.trait_.get_id(lang_items) else { continue }; |
| let entry = map.entry(trait_id).or_default(); |
| let entry = entry |
| .non_blanket_impls |
| .entry(SimplifiedType::Adt(loc.adt.into())) |
| .or_default(); |
| entry.1.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 = Body::of(db, konst.into()); |
| for (_, block_def_map) in body.blocks(db) { |
| collect(db, block_def_map, lang_items, map); |
| } |
| } |
| } |
| } |
| } |
| |
| pub fn blanket_impls(&self, for_trait: TraitId) -> &[ImplId] { |
| self.map.get(&for_trait).map(|it| &*it.blanket_impls).unwrap_or_default() |
| } |
| |
| /// 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<'db>, |
| ) -> 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() |
| }) |
| } |
| |
| pub fn for_trait_and_self_ty( |
| &'db self, |
| trait_: TraitId, |
| self_ty: &SimplifiedType<'db>, |
| ) -> (&'db [ImplId], &'db [BuiltinDeriveImplId]) { |
| self.map |
| .get(&trait_) |
| .and_then(|map| map.non_blanket_impls.get(self_ty)) |
| .map(|it| (&*it.0, &*it.1)) |
| .unwrap_or_default() |
| } |
| |
| pub fn for_trait( |
| &self, |
| trait_: TraitId, |
| mut callback: impl FnMut(Either<&[ImplId], &[BuiltinDeriveImplId]>), |
| ) { |
| if let Some(impls) = self.map.get(&trait_) { |
| callback(Either::Left(&impls.blanket_impls)); |
| for impls in impls.non_blanket_impls.values() { |
| callback(Either::Left(&impls.0)); |
| callback(Either::Right(&impls.1)); |
| } |
| } |
| } |
| |
| pub fn for_self_ty( |
| &self, |
| self_ty: &SimplifiedType<'db>, |
| mut callback: impl FnMut(Either<&[ImplId], &[BuiltinDeriveImplId]>), |
| ) { |
| for for_trait in self.map.values() { |
| if let Some(for_ty) = for_trait.non_blanket_impls.get(self_ty) { |
| callback(Either::Left(&for_ty.0)); |
| callback(Either::Right(&for_ty.1)); |
| } |
| } |
| } |
| |
| pub fn for_each_crate_and_block<R: VisitorResult>( |
| db: &'db dyn HirDatabase, |
| krate: Crate, |
| block: Option<BlockIdLt<'db>>, |
| for_each: &mut dyn FnMut(&TraitImpls<'db>) -> R, |
| ) -> R { |
| let blocks = std::iter::successors(block, |block| block.module(db).block(db)); |
| for impl_ in blocks.filter_map(|block| Self::for_block(db, block)) { |
| try_visit!(for_each(impl_)); |
| } |
| for impl_ in Self::for_crate_and_deps(db, krate) { |
| try_visit!(for_each(impl_)); |
| } |
| R::output() |
| } |
| |
| /// 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<R: VisitorResult>( |
| db: &'db dyn HirDatabase, |
| krate: Crate, |
| type_block: Option<BlockIdLt<'db>>, |
| trait_block: Option<BlockIdLt<'db>>, |
| for_each: &mut dyn FnMut(&TraitImpls<'db>) -> R, |
| ) -> R { |
| let in_self_and_deps = TraitImpls::for_crate_and_deps(db, krate); |
| for impl_ in in_self_and_deps { |
| try_visit!(for_each(impl_)); |
| } |
| |
| // 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<BlockIdLt<'db>>| { |
| std::iter::successors(block, |block| block.module(db).block(db)) |
| }; |
| let for_each_block = |current_block: Option<BlockIdLt<'db>>, |
| other_block: Option<BlockIdLt<'db>>| { |
| 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)) |
| }; |
| if trait_block == type_block { |
| for impl_ in |
| blocks_iter(trait_block).filter_map(|block| TraitImpls::for_block(db, block)) |
| { |
| try_visit!(for_each(impl_)); |
| } |
| } else { |
| for impl_ in for_each_block(trait_block, type_block) { |
| try_visit!(for_each(impl_)); |
| } |
| for impl_ in for_each_block(type_block, trait_block) { |
| try_visit!(for_each(impl_)); |
| } |
| } |
| R::output() |
| } |
| } |
| |
| fn self_ty_has_error_constructor<'db>(mut self_ty: Ty<'db>) -> bool { |
| if !self_ty.references_non_lt_error() { |
| return false; |
| } |
| |
| loop { |
| self_ty = match self_ty.kind() { |
| TyKind::Error(_) => return true, |
| TyKind::Ref(_, inner, _) |
| | TyKind::RawPtr(inner, _) |
| | TyKind::Array(inner, _) |
| | TyKind::Slice(inner) |
| | TyKind::Pat(inner, _) => inner, |
| TyKind::UnsafeBinder(inner) => inner.skip_binder(), |
| _ => return false, |
| }; |
| } |
| } |
