hir_ty/
method_resolution.rs

1//! This module is concerned with finding methods that a given type provides.
2//! For details about how this works in rustc, see the method lookup page in the
3//! [rustc guide] and the corresponding code mostly in
4//! [`rustc_hir_typeck/method/probe.rs`].
5//!
6//! [rustc guide]: https://rust-lang.github.io/rustc-guide/method-lookup.html
7//! [`rustc_hir_typeck/method/probe.rs`]: https://github.com/rust-lang/rust/blob/5503df87342a73d0c29126a7e08dc9c1255c46ad/compiler/rustc_hir_typeck/src/method/probe.rs
8
9mod confirm;
10mod probe;
11
12use either::Either;
13use hir_expand::name::Name;
14use salsa::Update;
15use span::Edition;
16use tracing::{debug, instrument};
17
18use base_db::{Crate, salsa::update_fallback_db};
19use hir_def::{
20    AssocItemId, BlockIdLt, BuiltinDeriveImplId, ConstId, FunctionId, GenericParamId, HasModule,
21    ImplId, ItemContainerId, ModuleId, TraitId,
22    attrs::AttrFlags,
23    builtin_derive::BuiltinDeriveImplMethod,
24    expr_store::{Body, path::GenericArgs as HirGenericArgs},
25    hir::{ExprId, generics::GenericParams},
26    lang_item::LangItems,
27    nameres::{DefMap, block_def_map, crate_def_map},
28    resolver::Resolver,
29    signatures::{ConstSignature, FunctionSignature},
30    unstable_features::UnstableFeatures,
31};
32use rustc_hash::{FxHashMap, FxHashSet};
33use rustc_type_ir::{
34    TypeVisitableExt,
35    fast_reject::{TreatParams, simplify_type},
36    inherent::{BoundExistentialPredicates, IntoKind},
37};
38use stdx::impl_from;
39use triomphe::Arc;
40
41use crate::{
42    InferenceDiagnostic, Span, all_super_traits,
43    db::HirDatabase,
44    infer::{InferenceContext, unify::InferenceTable},
45    lower::GenericPredicates,
46    next_solver::{
47        AnyImplId, Binder, ClauseKind, DbInterner, FnSig, GenericArgs, ParamEnv, PredicateKind,
48        SimplifiedType, SolverDefId, TraitRef, Ty, TyKind, TypingMode, Unnormalized,
49        infer::{
50            BoundRegionConversionTime, DbInternerInferExt, InferCtxt, InferOk,
51            select::ImplSource,
52            traits::{Obligation, ObligationCause, PredicateObligations},
53        },
54        obligation_ctxt::ObligationCtxt,
55        util::clauses_as_obligations,
56    },
57    traits::ParamEnvAndCrate,
58};
59
60pub use self::probe::{
61    Candidate, CandidateKind, CandidateStep, CandidateWithPrivate, Mode, Pick, PickKind,
62};
63
64pub struct MethodResolutionContext<'a, 'db> {
65    pub infcx: &'a InferCtxt<'db>,
66    pub resolver: &'a Resolver<'db>,
67    pub param_env: ParamEnv<'db>,
68    pub traits_in_scope: &'a FxHashSet<TraitId>,
69    pub edition: Edition,
70    pub features: &'a UnstableFeatures,
71    pub call_span: Span,
72    pub receiver_span: Span,
73}
74
75#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, salsa::Update)]
76pub enum CandidateId {
77    FunctionId(FunctionId),
78    ConstId(ConstId),
79}
80impl_from!(FunctionId, ConstId for CandidateId);
81
82impl CandidateId {
83    fn container(self, db: &dyn HirDatabase) -> ItemContainerId {
84        match self {
85            CandidateId::FunctionId(id) => id.loc(db).container,
86            CandidateId::ConstId(id) => id.loc(db).container,
87        }
88    }
89}
90
91#[derive(Clone, Copy, Debug)]
92pub(crate) struct MethodCallee<'db> {
93    /// Impl method ID, for inherent methods, or trait method ID, otherwise.
94    pub def_id: FunctionId,
95    pub args: GenericArgs<'db>,
96
97    /// Instantiated method signature, i.e., it has been
98    /// instantiated, normalized, and has had late-bound
99    /// lifetimes replaced with inference variables.
100    pub sig: FnSig<'db>,
101}
102
103#[derive(Debug)]
104pub enum MethodError<'db> {
105    /// Did not find an applicable method.
106    NoMatch,
107
108    /// Multiple methods might apply.
109    Ambiguity(Vec<CandidateSource>),
110
111    /// Found an applicable method, but it is not visible.
112    PrivateMatch(Pick<'db>),
113
114    /// Found a `Self: Sized` bound where `Self` is a trait object.
115    IllegalSizedBound { candidates: Vec<FunctionId>, needs_mut: bool },
116
117    /// Error has already been emitted, no need to emit another one.
118    ErrorReported,
119}
120
121// A pared down enum describing just the places from which a method
122// candidate can arise. Used for error reporting only.
123#[derive(Copy, Clone, Debug, Eq, PartialEq)]
124pub enum CandidateSource {
125    Impl(AnyImplId),
126    Trait(TraitId),
127}
128
129impl<'db> InferenceContext<'db> {
130    /// Performs method lookup. If lookup is successful, it will return the callee
131    /// and store an appropriate adjustment for the self-expr. In some cases it may
132    /// report an error (e.g., invoking the `drop` method).
133    #[instrument(level = "debug", skip(self))]
134    pub(crate) fn lookup_method_including_private(
135        &mut self,
136        self_ty: Ty<'db>,
137        name: Name,
138        generic_args: Option<&HirGenericArgs>,
139        receiver: ExprId,
140        call_expr: ExprId,
141    ) -> Result<(MethodCallee<'db>, bool), MethodError<'db>> {
142        let (pick, is_visible) = match self.lookup_probe(call_expr, receiver, name, self_ty) {
143            Ok(it) => (it, true),
144            Err(MethodError::PrivateMatch(it)) => {
145                // FIXME: Report error.
146                (it, false)
147            }
148            Err(err) => return Err(err),
149        };
150
151        let result = self.confirm_method(&pick, self_ty, call_expr, generic_args);
152        debug!("result = {:?}", result);
153
154        if result.illegal_sized_bound {
155            self.push_diagnostic(InferenceDiagnostic::MethodCallIllegalSizedBound { call_expr });
156        }
157
158        self.write_expr_adj(receiver, result.adjustments);
159        self.write_method_resolution(call_expr, result.callee.def_id, result.callee.args);
160
161        Ok((result.callee, is_visible))
162    }
163
164    #[instrument(level = "debug", skip(self))]
165    pub(crate) fn lookup_probe(
166        &self,
167        call_expr: ExprId,
168        receiver: ExprId,
169        method_name: Name,
170        self_ty: Ty<'db>,
171    ) -> probe::PickResult<'db> {
172        self.with_method_resolution(call_expr.into(), receiver.into(), |ctx| {
173            let pick = ctx.probe_for_name(probe::Mode::MethodCall, method_name, self_ty)?;
174            Ok(pick)
175        })
176    }
177
178    pub(crate) fn with_method_resolution<R>(
179        &self,
180        call_span: Span,
181        receiver_span: Span,
182        f: impl FnOnce(&MethodResolutionContext<'_, 'db>) -> R,
183    ) -> R {
184        let traits_in_scope = self.get_traits_in_scope();
185        let traits_in_scope = match &traits_in_scope {
186            Either::Left(it) => it,
187            Either::Right(it) => *it,
188        };
189        let ctx = MethodResolutionContext {
190            infcx: &self.table.infer_ctxt,
191            resolver: &self.resolver,
192            param_env: self.table.param_env,
193            traits_in_scope,
194            edition: self.edition,
195            features: self.features,
196            call_span,
197            receiver_span,
198        };
199        f(&ctx)
200    }
201}
202
203/// Used by `FnCtxt::lookup_method_for_operator` with `-Znext-solver`.
204///
205/// With `AsRigid` we error on `impl Opaque: NotInItemBounds` while
206/// `AsInfer` just treats it as ambiguous and succeeds. This is necessary
207/// as we want `FnCtxt::check_expr_call` to treat not-yet-defined opaque
208/// types as rigid to support `impl Deref<Target = impl FnOnce()>` and
209/// `Box<impl FnOnce()>`.
210///
211/// We only want to treat opaque types as rigid if we need to eagerly choose
212/// between multiple candidates. We otherwise treat them as ordinary inference
213/// variable to avoid rejecting otherwise correct code.
214#[derive(Debug)]
215pub(super) enum TreatNotYetDefinedOpaques {
216    AsInfer,
217    AsRigid,
218}
219
220impl<'db> InferenceTable<'db> {
221    /// `lookup_method_in_trait` is used for overloaded operators.
222    /// It does a very narrow slice of what the normal probe/confirm path does.
223    /// In particular, it doesn't really do any probing: it simply constructs
224    /// an obligation for a particular trait with the given self type and checks
225    /// whether that trait is implemented.
226    #[instrument(level = "debug", skip(self))]
227    pub(super) fn lookup_method_for_operator(
228        &self,
229        cause: ObligationCause,
230        trait_def_id: TraitId,
231        method_item: FunctionId,
232        self_ty: Ty<'db>,
233        opt_rhs_ty: Option<Ty<'db>>,
234        treat_opaques: TreatNotYetDefinedOpaques,
235    ) -> Option<InferOk<'db, MethodCallee<'db>>> {
236        // Construct a trait-reference `self_ty : Trait<input_tys>`
237        let args = GenericArgs::for_item(
238            self.interner(),
239            trait_def_id.into(),
240            |param_idx, param_id, _, _| match param_id {
241                GenericParamId::LifetimeParamId(_) | GenericParamId::ConstParamId(_) => {
242                    unreachable!("did not expect operator trait to have lifetime/const")
243                }
244                GenericParamId::TypeParamId(_) => {
245                    if param_idx == 0 {
246                        self_ty.into()
247                    } else if let Some(rhs_ty) = opt_rhs_ty {
248                        assert_eq!(param_idx, 1, "did not expect >1 param on operator trait");
249                        rhs_ty.into()
250                    } else {
251                        // FIXME: We should stop passing `None` for the failure case
252                        // when probing for call exprs. I.e. `opt_rhs_ty` should always
253                        // be set when it needs to be.
254                        self.var_for_def(param_id, cause.span())
255                    }
256                }
257            },
258        );
259
260        let obligation = Obligation::new(
261            self.interner(),
262            cause,
263            self.param_env,
264            TraitRef::new_from_args(self.interner(), trait_def_id.into(), args),
265        );
266
267        // Now we want to know if this can be matched
268        let matches_trait = match treat_opaques {
269            TreatNotYetDefinedOpaques::AsInfer => self.infer_ctxt.predicate_may_hold(&obligation),
270            TreatNotYetDefinedOpaques::AsRigid => {
271                self.infer_ctxt.predicate_may_hold_opaque_types_jank(&obligation)
272            }
273        };
274
275        if !matches_trait {
276            debug!("--> Cannot match obligation");
277            // Cannot be matched, no such method resolution is possible.
278            return None;
279        }
280
281        // Trait must have a method named `m_name` and it should not have
282        // type parameters or early-bound regions.
283        let interner = self.interner();
284
285        let def_id = method_item;
286
287        debug!("lookup_in_trait_adjusted: method_item={:?}", method_item);
288        let mut obligations = PredicateObligations::new();
289
290        // Instantiate late-bound regions and instantiate the trait
291        // parameters into the method type to get the actual method type.
292        //
293        // N.B., instantiate late-bound regions before normalizing the
294        // function signature so that normalization does not need to deal
295        // with bound regions.
296        let fn_sig = self
297            .db
298            .callable_item_signature(method_item.into())
299            .instantiate(interner, args)
300            .skip_norm_wip();
301        let fn_sig = self.infer_ctxt.instantiate_binder_with_fresh_vars(
302            cause.span(),
303            BoundRegionConversionTime::FnCall,
304            fn_sig,
305        );
306
307        // Register obligations for the parameters. This will include the
308        // `Self` parameter, which in turn has a bound of the main trait,
309        // so this also effectively registers `obligation` as well. (We
310        // used to register `obligation` explicitly, but that resulted in
311        // double error messages being reported.)
312        //
313        // Note that as the method comes from a trait, it should not have
314        // any late-bound regions appearing in its bounds.
315        let bounds = GenericPredicates::query_all(self.db, method_item.into());
316        let bounds = clauses_as_obligations(
317            bounds.iter_instantiated(interner, args.as_slice()).map(Unnormalized::skip_norm_wip),
318            cause,
319            self.param_env,
320        );
321
322        obligations.extend(bounds);
323
324        // Also add an obligation for the method type being well-formed.
325        debug!(
326            "lookup_method_in_trait: matched method fn_sig={:?} obligation={:?}",
327            fn_sig, obligation
328        );
329        for ty in fn_sig.inputs_and_output {
330            obligations.push(Obligation::new(
331                interner,
332                obligation.cause,
333                self.param_env,
334                Binder::dummy(PredicateKind::Clause(ClauseKind::WellFormed(ty.into()))),
335            ));
336        }
337
338        let callee = MethodCallee { def_id, args, sig: fn_sig };
339        debug!("callee = {:?}", callee);
340
341        Some(InferOk { obligations, value: callee })
342    }
343}
344
345pub fn lookup_impl_const<'db>(
346    infcx: &InferCtxt<'db>,
347    env: ParamEnv<'db>,
348    const_id: ConstId,
349    subs: GenericArgs<'db>,
350) -> (ConstId, GenericArgs<'db>) {
351    let interner = infcx.interner;
352    let db = interner.db;
353
354    let trait_id = match const_id.loc(db).container {
355        ItemContainerId::TraitId(id) => id,
356        _ => return (const_id, subs),
357    };
358    let trait_ref = TraitRef::new_from_args(interner, trait_id.into(), subs);
359
360    let const_signature = ConstSignature::of(db, const_id);
361    let name = match const_signature.name.as_ref() {
362        Some(name) => name,
363        None => return (const_id, subs),
364    };
365
366    lookup_impl_assoc_item_for_trait_ref(infcx, trait_ref, env, name)
367        .and_then(|assoc| {
368            if let (Either::Left(AssocItemId::ConstId(id)), s) = assoc {
369                Some((id, s))
370            } else {
371                None
372            }
373        })
374        .unwrap_or((const_id, subs))
375}
376
377/// Checks if the self parameter of `Trait` method is the `dyn Trait` and we should
378/// call the method using the vtable.
379pub fn is_dyn_method<'db>(
380    interner: DbInterner<'db>,
381    _env: ParamEnv<'db>,
382    func: FunctionId,
383    fn_subst: GenericArgs<'db>,
384) -> Option<usize> {
385    let db = interner.db;
386
387    let ItemContainerId::TraitId(trait_id) = func.loc(db).container else {
388        return None;
389    };
390    let trait_params = GenericParams::of(db, trait_id.into()).len();
391    let fn_params = fn_subst.len() - trait_params;
392    let trait_ref = TraitRef::new_from_args(
393        interner,
394        trait_id.into(),
395        GenericArgs::new_from_slice(&fn_subst[..trait_params]),
396    );
397    let self_ty = trait_ref.self_ty();
398    if let TyKind::Dynamic(d, _) = self_ty.kind() {
399        // rustc doesn't accept `impl Foo<2> for dyn Foo<5>`, so if the trait id is equal, no matter
400        // what the generics are, we are sure that the method is come from the vtable.
401        let is_my_trait_in_bounds = d
402            .principal_def_id()
403            .is_some_and(|trait_| all_super_traits(db, trait_.0).contains(&trait_id));
404        if is_my_trait_in_bounds {
405            return Some(fn_params);
406        }
407    }
408    None
409}
410
411/// Looks up the impl method that actually runs for the trait method `func`.
412///
413/// Returns `func` if it's not a method defined in a trait or the lookup failed.
414pub(crate) fn lookup_impl_method_query<'db>(
415    db: &'db dyn HirDatabase,
416    env: ParamEnvAndCrate<'db>,
417    func: FunctionId,
418    fn_subst: GenericArgs<'db>,
419) -> (Either<FunctionId, (BuiltinDeriveImplId, BuiltinDeriveImplMethod)>, GenericArgs<'db>) {
420    let interner = DbInterner::new_with(db, env.krate);
421    let infcx = interner.infer_ctxt().build(TypingMode::PostAnalysis);
422
423    let ItemContainerId::TraitId(trait_id) = func.loc(db).container else {
424        return (Either::Left(func), fn_subst);
425    };
426    let trait_params = GenericParams::of(db, trait_id.into()).len();
427    let trait_ref = TraitRef::new_from_args(
428        interner,
429        trait_id.into(),
430        GenericArgs::new_from_slice(&fn_subst[..trait_params]),
431    );
432
433    let name = &FunctionSignature::of(db, func).name;
434    let Some((impl_fn, impl_subst)) =
435        lookup_impl_assoc_item_for_trait_ref(&infcx, trait_ref, env.param_env, name).and_then(
436            |(assoc, impl_args)| {
437                let assoc = match assoc {
438                    Either::Left(AssocItemId::FunctionId(id)) => Either::Left(id),
439                    Either::Right(it) => Either::Right(it),
440                    _ => return None,
441                };
442                Some((assoc, impl_args))
443            },
444        )
445    else {
446        return (Either::Left(func), fn_subst);
447    };
448
449    (
450        impl_fn,
451        GenericArgs::new_from_iter(
452            interner,
453            impl_subst.iter().chain(fn_subst.iter().skip(trait_params)),
454        ),
455    )
456}
457
458fn lookup_impl_assoc_item_for_trait_ref<'db>(
459    infcx: &InferCtxt<'db>,
460    trait_ref: TraitRef<'db>,
461    env: ParamEnv<'db>,
462    name: &Name,
463) -> Option<(Either<AssocItemId, (BuiltinDeriveImplId, BuiltinDeriveImplMethod)>, GenericArgs<'db>)>
464{
465    let (impl_id, impl_subst) = find_matching_impl(infcx, env, trait_ref)?;
466    let impl_id = match impl_id {
467        AnyImplId::ImplId(it) => it,
468        AnyImplId::BuiltinDeriveImplId(impl_) => {
469            return impl_
470                .loc(infcx.interner.db)
471                .trait_
472                .get_method(name.symbol())
473                .map(|method| (Either::Right((impl_, method)), impl_subst));
474        }
475    };
476    let item =
477        impl_id.impl_items(infcx.interner.db).items.iter().find_map(|(n, it)| match *it {
478            AssocItemId::FunctionId(f) => (n == name).then_some(AssocItemId::FunctionId(f)),
479            AssocItemId::ConstId(c) => (n == name).then_some(AssocItemId::ConstId(c)),
480            AssocItemId::TypeAliasId(_) => None,
481        })?;
482    Some((Either::Left(item), impl_subst))
483}
484
485pub(crate) fn find_matching_impl<'db>(
486    infcx: &InferCtxt<'db>,
487    env: ParamEnv<'db>,
488    trait_ref: TraitRef<'db>,
489) -> Option<(AnyImplId, GenericArgs<'db>)> {
490    let trait_ref = infcx.at(&ObligationCause::dummy(), env).deeply_normalize(trait_ref).ok()?;
491
492    let obligation = Obligation::new(infcx.interner, ObligationCause::dummy(), env, trait_ref);
493
494    let selection = infcx.select(&obligation).ok()??;
495
496    // Currently, we use a fulfillment context to completely resolve
497    // all nested obligations. This is because they can inform the
498    // inference of the impl's type parameters.
499    let mut ocx = ObligationCtxt::new(infcx);
500    let impl_source = selection.map(|obligation| ocx.register_obligation(obligation));
501
502    let errors = ocx.evaluate_obligations_error_on_ambiguity();
503    if !errors.is_empty() {
504        return None;
505    }
506
507    let impl_source = infcx.resolve_vars_if_possible(impl_source);
508    if impl_source.has_non_region_infer() {
509        return None;
510    }
511
512    match impl_source {
513        ImplSource::UserDefined(impl_source) => Some((impl_source.impl_def_id, impl_source.args)),
514        ImplSource::Param(_) | ImplSource::Builtin(..) => None,
515    }
516}
517
518#[salsa::tracked(returns(ref))]
519fn crates_containing_incoherent_inherent_impls(db: &dyn HirDatabase, krate: Crate) -> Box<[Crate]> {
520    let _p = tracing::info_span!("crates_containing_incoherent_inherent_impls").entered();
521    // We assume that only sysroot crates contain `#[rustc_has_incoherent_inherent_impls]`
522    // impls, since this is an internal feature and only std uses it.
523    krate.transitive_deps(db).into_iter().filter(|krate| krate.data(db).origin.is_lang()).collect()
524}
525
526pub fn with_incoherent_inherent_impls<'db>(
527    db: &'db dyn HirDatabase,
528    krate: Crate,
529    self_ty: &SimplifiedType<'db>,
530    mut callback: impl FnMut(&[ImplId]),
531) {
532    let has_incoherent_impls = match self_ty.def() {
533        Some(def_id) => match def_id.try_into() {
534            Ok(def_id) => AttrFlags::query(db, def_id)
535                .contains(AttrFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS),
536            Err(()) => true,
537        },
538        _ => true,
539    };
540    if !has_incoherent_impls {
541        return;
542    }
543    let _p = tracing::info_span!("incoherent_inherent_impls").entered();
544    let crates = crates_containing_incoherent_inherent_impls(db, krate);
545    for &krate in crates {
546        let impls = InherentImpls::for_crate(db, krate);
547        callback(impls.for_self_ty(self_ty));
548    }
549}
550
551pub fn simplified_type_module(db: &dyn HirDatabase, ty: &SimplifiedType<'_>) -> Option<ModuleId> {
552    match ty.def()? {
553        SolverDefId::AdtId(id) => Some(id.module(db)),
554        SolverDefId::TypeAliasId(id) => Some(id.module(db)),
555        SolverDefId::TraitId(id) => Some(id.module(db)),
556        _ => None,
557    }
558}
559
560#[derive(Debug, PartialEq, Eq, Update)]
561pub struct InherentImpls<'db> {
562    #[update(bounds(SolverDefId<'db>: Update), unsafe(with(update_fallback_db::<'db, _>)))]
563    map: FxHashMap<SimplifiedType<'db>, Box<[ImplId]>>,
564}
565
566#[salsa::tracked]
567impl<'db> InherentImpls<'db> {
568    #[salsa::tracked(returns(ref))]
569    pub fn for_crate(db: &'db dyn HirDatabase, krate: Crate) -> InherentImpls<'db> {
570        let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered();
571
572        let crate_def_map = crate_def_map(db, krate);
573
574        Self::collect_def_map(db, crate_def_map)
575    }
576
577    #[salsa::tracked(returns(ref))]
578    pub fn for_block(
579        db: &'db dyn HirDatabase,
580        block: BlockIdLt<'db>,
581    ) -> Option<Box<InherentImpls<'db>>> {
582        let _p = tracing::info_span!("inherent_impls_in_block_query").entered();
583
584        let block_def_map = block_def_map(db, block);
585        let result = Self::collect_def_map(db, block_def_map);
586        if result.map.is_empty() { None } else { Some(Box::new(result)) }
587    }
588}
589
590impl<'db> InherentImpls<'db> {
591    fn collect_def_map(db: &'db dyn HirDatabase, def_map: &'db DefMap) -> Self {
592        let mut map = FxHashMap::default();
593        collect(db, def_map, &mut map);
594        let mut map = map
595            .into_iter()
596            .map(|(self_ty, impls)| (self_ty, impls.into_boxed_slice()))
597            .collect::<FxHashMap<_, _>>();
598        map.shrink_to_fit();
599        return Self { map };
600
601        fn collect<'db>(
602            db: &'db dyn HirDatabase,
603            def_map: &DefMap,
604            map: &mut FxHashMap<SimplifiedType<'db>, Vec<ImplId>>,
605        ) {
606            for (_module_id, module_data) in def_map.modules() {
607                for impl_id in module_data.scope.inherent_impls() {
608                    let interner = DbInterner::new_no_crate(db);
609                    let self_ty = db.impl_self_ty(impl_id);
610                    let self_ty = self_ty.instantiate_identity().skip_norm_wip();
611                    if let Some(self_ty) =
612                        simplify_type(interner, self_ty, TreatParams::InstantiateWithInfer)
613                    {
614                        map.entry(self_ty).or_default().push(impl_id);
615                    }
616                }
617
618                // To better support custom derives, collect impls in all unnamed const items.
619                // const _: () = { ... };
620                for konst in module_data.scope.unnamed_consts() {
621                    let body = Body::of(db, konst.into());
622                    for (_, block_def_map) in body.blocks(db) {
623                        collect(db, block_def_map, map);
624                    }
625                }
626            }
627        }
628    }
629
630    pub fn for_self_ty(&self, self_ty: &SimplifiedType<'db>) -> &[ImplId] {
631        self.map.get(self_ty).map(|it| &**it).unwrap_or_default()
632    }
633
634    pub fn for_each_crate_and_block(
635        db: &'db dyn HirDatabase,
636        krate: Crate,
637        block: Option<BlockIdLt<'db>>,
638        for_each: &mut dyn FnMut(&InherentImpls<'db>),
639    ) {
640        let blocks = std::iter::successors(block, |block| block.module(db).block(db));
641        blocks.filter_map(|block| Self::for_block(db, block).as_deref()).for_each(&mut *for_each);
642        for_each(Self::for_crate(db, krate));
643    }
644}
645
646#[derive(Debug, PartialEq, Update)]
647struct OneTraitImpls<'db> {
648    #[update(bounds(SolverDefId<'db>: Update), unsafe(with(update_fallback_db::<'db, _>)))]
649    non_blanket_impls: FxHashMap<SimplifiedType<'db>, (Box<[ImplId]>, Box<[BuiltinDeriveImplId]>)>,
650    blanket_impls: Box<[ImplId]>,
651}
652
653#[derive(Default)]
654struct OneTraitImplsBuilder<'db> {
655    non_blanket_impls: FxHashMap<SimplifiedType<'db>, (Vec<ImplId>, Vec<BuiltinDeriveImplId>)>,
656    blanket_impls: Vec<ImplId>,
657}
658
659impl<'db> OneTraitImplsBuilder<'db> {
660    fn finish(self) -> OneTraitImpls<'db> {
661        let mut non_blanket_impls = self
662            .non_blanket_impls
663            .into_iter()
664            .map(|(self_ty, (impls, builtin_derive_impls))| {
665                (self_ty, (impls.into_boxed_slice(), builtin_derive_impls.into_boxed_slice()))
666            })
667            .collect::<FxHashMap<_, _>>();
668        non_blanket_impls.shrink_to_fit();
669        let blanket_impls = self.blanket_impls.into_boxed_slice();
670        OneTraitImpls { non_blanket_impls, blanket_impls }
671    }
672}
673
674#[derive(Debug, PartialEq, Update)]
675pub struct TraitImpls<'db> {
676    map: FxHashMap<TraitId, OneTraitImpls<'db>>,
677}
678
679#[salsa::tracked]
680impl<'db> TraitImpls<'db> {
681    #[salsa::tracked(returns(ref))]
682    pub fn for_crate(db: &'db dyn HirDatabase, krate: Crate) -> Arc<TraitImpls<'db>> {
683        let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered();
684
685        let crate_def_map = crate_def_map(db, krate);
686        let result = Self::collect_def_map(db, crate_def_map);
687        Arc::new(result)
688    }
689
690    #[salsa::tracked(returns(as_deref))]
691    pub fn for_block(
692        db: &'db dyn HirDatabase,
693        block: BlockIdLt<'db>,
694    ) -> Option<Box<TraitImpls<'db>>> {
695        let _p = tracing::info_span!("inherent_impls_in_block_query").entered();
696
697        let block_def_map = block_def_map(db, block);
698        let result = Self::collect_def_map(db, block_def_map);
699        if result.map.is_empty() { None } else { Some(Box::new(result)) }
700    }
701
702    #[salsa::tracked(returns(deref))]
703    pub fn for_crate_and_deps(db: &'db dyn HirDatabase, krate: Crate) -> Box<[Arc<Self>]> {
704        krate.transitive_deps(db).iter().map(|&dep| Self::for_crate(db, dep).clone()).collect()
705    }
706}
707
708impl<'db> TraitImpls<'db> {
709    fn collect_def_map(db: &'db dyn HirDatabase, def_map: &DefMap) -> Self {
710        let lang_items = hir_def::lang_item::lang_items(db, def_map.krate());
711        let mut map = FxHashMap::default();
712        collect(db, def_map, lang_items, &mut map);
713        let mut map = map
714            .into_iter()
715            .map(|(trait_id, trait_map)| (trait_id, trait_map.finish()))
716            .collect::<FxHashMap<_, _>>();
717        map.shrink_to_fit();
718        return Self { map };
719
720        fn collect<'db>(
721            db: &'db dyn HirDatabase,
722            def_map: &DefMap,
723            lang_items: &LangItems,
724            map: &mut FxHashMap<TraitId, OneTraitImplsBuilder<'db>>,
725        ) {
726            for (_module_id, module_data) in def_map.modules() {
727                for impl_id in module_data.scope.trait_impls() {
728                    let trait_ref = match db.impl_trait(impl_id) {
729                        Some(tr) => tr.instantiate_identity().skip_norm_wip(),
730                        None => continue,
731                    };
732                    // Reservation impls should be ignored during trait resolution, so we never need
733                    // them during type analysis. See rust-lang/rust#64631 for details.
734                    //
735                    // FIXME: Reservation impls should be considered during coherence checks. If we are
736                    // (ever) to implement coherence checks, this filtering should be done by the trait
737                    // solver.
738                    if AttrFlags::query(db, impl_id.into())
739                        .contains(AttrFlags::RUSTC_RESERVATION_IMPL)
740                    {
741                        continue;
742                    }
743
744                    let self_ty = trait_ref.self_ty();
745                    if self_ty_has_error_constructor(self_ty) {
746                        // If we see `impl Foo for NoSuchType`, just ignore it.
747                        continue;
748                    }
749
750                    let interner = DbInterner::new_no_crate(db);
751                    let entry = map.entry(trait_ref.def_id.0).or_default();
752                    match simplify_type(interner, self_ty, TreatParams::InstantiateWithInfer) {
753                        Some(self_ty) => {
754                            entry.non_blanket_impls.entry(self_ty).or_default().0.push(impl_id)
755                        }
756                        None => entry.blanket_impls.push(impl_id),
757                    }
758                }
759
760                for impl_id in module_data.scope.builtin_derive_impls() {
761                    let loc = impl_id.loc(db);
762                    let Some(trait_id) = loc.trait_.get_id(lang_items) else { continue };
763                    let entry = map.entry(trait_id).or_default();
764                    let entry = entry
765                        .non_blanket_impls
766                        .entry(SimplifiedType::Adt(loc.adt.into()))
767                        .or_default();
768                    entry.1.push(impl_id);
769                }
770
771                // To better support custom derives, collect impls in all unnamed const items.
772                // const _: () = { ... };
773                for konst in module_data.scope.unnamed_consts() {
774                    let body = Body::of(db, konst.into());
775                    for (_, block_def_map) in body.blocks(db) {
776                        collect(db, block_def_map, lang_items, map);
777                    }
778                }
779            }
780        }
781    }
782
783    pub fn blanket_impls(&self, for_trait: TraitId) -> &[ImplId] {
784        self.map.get(&for_trait).map(|it| &*it.blanket_impls).unwrap_or_default()
785    }
786
787    /// Queries whether `self_ty` has potentially applicable implementations of `trait_`.
788    pub fn has_impls_for_trait_and_self_ty(
789        &self,
790        trait_: TraitId,
791        self_ty: &SimplifiedType<'db>,
792    ) -> bool {
793        self.map.get(&trait_).is_some_and(|trait_impls| {
794            trait_impls.non_blanket_impls.contains_key(self_ty)
795                || !trait_impls.blanket_impls.is_empty()
796        })
797    }
798
799    pub fn for_trait_and_self_ty(
800        &'db self,
801        trait_: TraitId,
802        self_ty: &SimplifiedType<'db>,
803    ) -> (&'db [ImplId], &'db [BuiltinDeriveImplId]) {
804        self.map
805            .get(&trait_)
806            .and_then(|map| map.non_blanket_impls.get(self_ty))
807            .map(|it| (&*it.0, &*it.1))
808            .unwrap_or_default()
809    }
810
811    pub fn for_trait(
812        &self,
813        trait_: TraitId,
814        mut callback: impl FnMut(Either<&[ImplId], &[BuiltinDeriveImplId]>),
815    ) {
816        if let Some(impls) = self.map.get(&trait_) {
817            callback(Either::Left(&impls.blanket_impls));
818            for impls in impls.non_blanket_impls.values() {
819                callback(Either::Left(&impls.0));
820                callback(Either::Right(&impls.1));
821            }
822        }
823    }
824
825    pub fn for_self_ty(
826        &self,
827        self_ty: &SimplifiedType<'db>,
828        mut callback: impl FnMut(Either<&[ImplId], &[BuiltinDeriveImplId]>),
829    ) {
830        for for_trait in self.map.values() {
831            if let Some(for_ty) = for_trait.non_blanket_impls.get(self_ty) {
832                callback(Either::Left(&for_ty.0));
833                callback(Either::Right(&for_ty.1));
834            }
835        }
836    }
837
838    pub fn for_each_crate_and_block(
839        db: &'db dyn HirDatabase,
840        krate: Crate,
841        block: Option<BlockIdLt<'db>>,
842        for_each: &mut dyn FnMut(&TraitImpls<'db>),
843    ) {
844        let blocks = std::iter::successors(block, |block| block.module(db).block(db));
845        blocks.filter_map(|block| Self::for_block(db, block)).for_each(&mut *for_each);
846        Self::for_crate_and_deps(db, krate).iter().map(|it| &**it).for_each(for_each);
847    }
848
849    /// Like [`Self::for_each_crate_and_block()`], but takes in account two blocks, one for a trait and one for a self type.
850    pub fn for_each_crate_and_block_trait_and_type(
851        db: &'db dyn HirDatabase,
852        krate: Crate,
853        type_block: Option<BlockIdLt<'db>>,
854        trait_block: Option<BlockIdLt<'db>>,
855        for_each: &mut dyn FnMut(&TraitImpls<'db>),
856    ) {
857        let in_self_and_deps = TraitImpls::for_crate_and_deps(db, krate);
858        in_self_and_deps.iter().for_each(|impls| for_each(impls));
859
860        // We must not provide duplicate impls to the solver. Therefore we work with the following strategy:
861        // start from each block, and walk ancestors until you meet the other block. If they never meet,
862        // that means there can't be duplicate impls; if they meet, we stop the search of the deeper block.
863        // This breaks when they are equal (both will stop immediately), therefore we handle this case
864        // specifically.
865        let blocks_iter = |block: Option<BlockIdLt<'db>>| {
866            std::iter::successors(block, |block| block.module(db).block(db))
867        };
868        let for_each_block = |current_block: Option<BlockIdLt<'db>>,
869                              other_block: Option<BlockIdLt<'db>>| {
870            blocks_iter(current_block)
871                .take_while(move |&block| {
872                    other_block.is_none_or(|other_block| other_block != block)
873                })
874                .filter_map(move |block| TraitImpls::for_block(db, block))
875        };
876        if trait_block == type_block {
877            blocks_iter(trait_block)
878                .filter_map(|block| TraitImpls::for_block(db, block))
879                .for_each(for_each);
880        } else {
881            for_each_block(trait_block, type_block).for_each(&mut *for_each);
882            for_each_block(type_block, trait_block).for_each(for_each);
883        }
884    }
885}
886
887fn self_ty_has_error_constructor<'db>(mut self_ty: Ty<'db>) -> bool {
888    if !self_ty.references_non_lt_error() {
889        return false;
890    }
891
892    loop {
893        self_ty = match self_ty.kind() {
894            TyKind::Error(_) => return true,
895            TyKind::Ref(_, inner, _)
896            | TyKind::RawPtr(inner, _)
897            | TyKind::Array(inner, _)
898            | TyKind::Slice(inner)
899            | TyKind::Pat(inner, _) => inner,
900            TyKind::UnsafeBinder(inner) => inner.skip_binder(),
901            _ => return false,
902        };
903    }
904}
hir_ty/method_resolution.rs

hir_ty/
method_resolution.rs
