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

hir_ty/
method_resolution.rs
