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(
454            interner,
455            impl_subst.iter().chain(fn_subst.iter().skip(trait_params)),
456        ),
457    )
458}
459
460fn lookup_impl_assoc_item_for_trait_ref<'db>(
461    infcx: &InferCtxt<'db>,
462    trait_ref: TraitRef<'db>,
463    env: ParamEnv<'db>,
464    name: &Name,
465) -> Option<(Either<AssocItemId, (BuiltinDeriveImplId, BuiltinDeriveImplMethod)>, GenericArgs<'db>)>
466{
467    let (impl_id, impl_subst) = find_matching_impl(infcx, env, trait_ref)?;
468    let impl_id = match impl_id {
469        AnyImplId::ImplId(it) => it,
470        AnyImplId::BuiltinDeriveImplId(impl_) => {
471            return impl_
472                .loc(infcx.interner.db)
473                .trait_
474                .get_method(name.symbol())
475                .map(|method| (Either::Right((impl_, method)), impl_subst));
476        }
477    };
478    let item =
479        impl_id.impl_items(infcx.interner.db).items.iter().find_map(|(n, it)| match *it {
480            AssocItemId::FunctionId(f) => (n == name).then_some(AssocItemId::FunctionId(f)),
481            AssocItemId::ConstId(c) => (n == name).then_some(AssocItemId::ConstId(c)),
482            AssocItemId::TypeAliasId(_) => None,
483        })?;
484    Some((Either::Left(item), impl_subst))
485}
486
487pub(crate) fn find_matching_impl<'db>(
488    infcx: &InferCtxt<'db>,
489    env: ParamEnv<'db>,
490    trait_ref: TraitRef<'db>,
491) -> Option<(AnyImplId, GenericArgs<'db>)> {
492    let trait_ref = infcx.at(&ObligationCause::dummy(), env).deeply_normalize(trait_ref).ok()?;
493
494    let obligation = Obligation::new(infcx.interner, ObligationCause::dummy(), env, trait_ref);
495
496    let selection = infcx.select(&obligation).ok()??;
497
498    // Currently, we use a fulfillment context to completely resolve
499    // all nested obligations. This is because they can inform the
500    // inference of the impl's type parameters.
501    let mut ocx = ObligationCtxt::new(infcx);
502    let impl_source = selection.map(|obligation| ocx.register_obligation(obligation));
503
504    let errors = ocx.evaluate_obligations_error_on_ambiguity();
505    if !errors.is_empty() {
506        return None;
507    }
508
509    let impl_source = infcx.resolve_vars_if_possible(impl_source);
510    if impl_source.has_non_region_infer() {
511        return None;
512    }
513
514    // Selection may leave region inference variables unresolved; replace them before they escape
515    // this inference context.
516    //
517    // FIXME: decide whether inferred regions should be replaced with error or erased.
518    match impl_source {
519        ImplSource::UserDefined(impl_source) => Some((
520            impl_source.impl_def_id,
521            impl_source.args.fold_with(&mut ReplaceInferWithError::new(infcx.interner)),
522        )),
523        ImplSource::Param(_) | ImplSource::Builtin(..) => None,
524    }
525}
526
527#[salsa::tracked(returns(ref))]
528fn crates_containing_incoherent_inherent_impls(db: &dyn HirDatabase, krate: Crate) -> Box<[Crate]> {
529    let _p = tracing::info_span!("crates_containing_incoherent_inherent_impls").entered();
530    // We assume that only sysroot crates contain `#[rustc_has_incoherent_inherent_impls]`
531    // impls, since this is an internal feature and only std uses it.
532    krate.transitive_deps(db).into_iter().filter(|krate| krate.data(db).origin.is_lang()).collect()
533}
534
535pub fn with_incoherent_inherent_impls<'db>(
536    db: &'db dyn HirDatabase,
537    krate: Crate,
538    self_ty: &SimplifiedType<'db>,
539    mut callback: impl FnMut(&[ImplId]),
540) {
541    let has_incoherent_impls = match self_ty.def() {
542        Some(def_id) => match def_id.try_into() {
543            Ok(def_id) => AttrFlags::query(db, def_id)
544                .contains(AttrFlags::RUSTC_HAS_INCOHERENT_INHERENT_IMPLS),
545            Err(()) => true,
546        },
547        _ => true,
548    };
549    if !has_incoherent_impls {
550        return;
551    }
552    let _p = tracing::info_span!("incoherent_inherent_impls").entered();
553    let crates = crates_containing_incoherent_inherent_impls(db, krate);
554    for &krate in crates {
555        let impls = InherentImpls::for_crate(db, krate);
556        callback(impls.for_self_ty(self_ty));
557    }
558}
559
560pub fn simplified_type_module(db: &dyn HirDatabase, ty: &SimplifiedType<'_>) -> Option<ModuleId> {
561    match ty.def()? {
562        SolverDefId::AdtId(id) => Some(id.module(db)),
563        SolverDefId::TypeAliasId(id) => Some(id.module(db)),
564        SolverDefId::TraitId(id) => Some(id.module(db)),
565        _ => None,
566    }
567}
568
569#[derive(Debug, PartialEq, Eq, SalsaValue)]
570pub struct InherentImpls<'db> {
571    // SAFETY: necessary due to `SimplifiedType<'db>`.
572    // It's safe to retain, as it only contains `SolverDefId<'db>` (which is `SalsaValue`),
573    // and no `&'db` references.
574    #[salsa_value(unsafe(prove(SolverDefId<'db>: SalsaValue)))]
575    map: FxHashMap<SimplifiedType<'db>, Box<[ImplId]>>,
576}
577
578#[salsa::tracked]
579impl<'db> InherentImpls<'db> {
580    #[salsa::tracked(returns(ref))]
581    pub fn for_crate(db: &'db dyn HirDatabase, krate: Crate) -> InherentImpls<'db> {
582        let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered();
583
584        let crate_def_map = crate_def_map(db, krate);
585
586        Self::collect_def_map(db, crate_def_map)
587    }
588
589    #[salsa::tracked(returns(ref))]
590    pub fn for_block(
591        db: &'db dyn HirDatabase,
592        block: BlockIdLt<'db>,
593    ) -> Option<Box<InherentImpls<'db>>> {
594        let _p = tracing::info_span!("inherent_impls_in_block_query").entered();
595
596        let block_def_map = block_def_map(db, block);
597        let result = Self::collect_def_map(db, block_def_map);
598        if result.map.is_empty() { None } else { Some(Box::new(result)) }
599    }
600}
601
602impl<'db> InherentImpls<'db> {
603    fn collect_def_map(db: &'db dyn HirDatabase, def_map: &'db DefMap) -> Self {
604        let mut map = FxHashMap::default();
605        collect(db, def_map, &mut map);
606        let mut map = map
607            .into_iter()
608            .map(|(self_ty, impls)| (self_ty, impls.into_boxed_slice()))
609            .collect::<FxHashMap<_, _>>();
610        map.shrink_to_fit();
611        return Self { map };
612
613        fn collect<'db>(
614            db: &'db dyn HirDatabase,
615            def_map: &DefMap,
616            map: &mut FxHashMap<SimplifiedType<'db>, Vec<ImplId>>,
617        ) {
618            for (_module_id, module_data) in def_map.modules() {
619                for impl_id in module_data.scope.inherent_impls() {
620                    let interner = DbInterner::new_no_crate(db);
621                    let self_ty = db.impl_self_ty(impl_id);
622                    let self_ty = self_ty.instantiate_identity().skip_norm_wip();
623                    if let Some(self_ty) =
624                        simplify_type(interner, self_ty, TreatParams::InstantiateWithInfer)
625                    {
626                        map.entry(self_ty).or_default().push(impl_id);
627                    }
628                }
629
630                // To better support custom derives, collect impls in all unnamed const items.
631                // const _: () = { ... };
632                for konst in module_data.scope.unnamed_consts() {
633                    let body = Body::of(db, konst.into());
634                    for (_, block_def_map) in body.blocks(db) {
635                        collect(db, block_def_map, map);
636                    }
637                }
638            }
639        }
640    }
641
642    pub fn for_self_ty(&self, self_ty: &SimplifiedType<'db>) -> &[ImplId] {
643        self.map.get(self_ty).map(|it| &**it).unwrap_or_default()
644    }
645
646    pub fn for_each_crate_and_block(
647        db: &'db dyn HirDatabase,
648        krate: Crate,
649        block: Option<BlockIdLt<'db>>,
650        for_each: &mut dyn FnMut(&InherentImpls<'db>),
651    ) {
652        let blocks = std::iter::successors(block, |block| block.module(db).block(db));
653        blocks.filter_map(|block| Self::for_block(db, block).as_deref()).for_each(&mut *for_each);
654        for_each(Self::for_crate(db, krate));
655    }
656}
657
658#[derive(Debug, PartialEq, SalsaValue)]
659struct OneTraitImpls<'db> {
660    // SAFETY: necessary due to `SimplifiedType<'db>`.
661    // It's safe to retain, as it only contains `SolverDefId<'db>` (which is `SalsaValue`),
662    // and no `&'db` references.
663    #[salsa_value(unsafe(prove(SolverDefId<'db>: SalsaValue)))]
664    non_blanket_impls: FxHashMap<SimplifiedType<'db>, (Box<[ImplId]>, Box<[BuiltinDeriveImplId]>)>,
665    blanket_impls: Box<[ImplId]>,
666}
667
668#[derive(Default)]
669struct OneTraitImplsBuilder<'db> {
670    non_blanket_impls: FxHashMap<SimplifiedType<'db>, (Vec<ImplId>, Vec<BuiltinDeriveImplId>)>,
671    blanket_impls: Vec<ImplId>,
672}
673
674impl<'db> OneTraitImplsBuilder<'db> {
675    fn finish(self) -> OneTraitImpls<'db> {
676        let mut non_blanket_impls = self
677            .non_blanket_impls
678            .into_iter()
679            .map(|(self_ty, (impls, builtin_derive_impls))| {
680                (self_ty, (impls.into_boxed_slice(), builtin_derive_impls.into_boxed_slice()))
681            })
682            .collect::<FxHashMap<_, _>>();
683        non_blanket_impls.shrink_to_fit();
684        let blanket_impls = self.blanket_impls.into_boxed_slice();
685        OneTraitImpls { non_blanket_impls, blanket_impls }
686    }
687}
688
689#[derive(Debug, PartialEq, SalsaValue)]
690pub struct TraitImpls<'db> {
691    map: FxHashMap<TraitId, OneTraitImpls<'db>>,
692}
693
694#[salsa::tracked]
695impl<'db> TraitImpls<'db> {
696    #[salsa::tracked(returns(ref))]
697    pub fn for_crate(db: &'db dyn HirDatabase, krate: Crate) -> Arc<TraitImpls<'db>> {
698        let _p = tracing::info_span!("inherent_impls_in_crate_query", ?krate).entered();
699
700        let crate_def_map = crate_def_map(db, krate);
701        let result = Self::collect_def_map(db, crate_def_map);
702        Arc::new(result)
703    }
704
705    #[salsa::tracked(returns(as_deref))]
706    pub fn for_block(
707        db: &'db dyn HirDatabase,
708        block: BlockIdLt<'db>,
709    ) -> Option<Box<TraitImpls<'db>>> {
710        let _p = tracing::info_span!("inherent_impls_in_block_query").entered();
711
712        let block_def_map = block_def_map(db, block);
713        let result = Self::collect_def_map(db, block_def_map);
714        if result.map.is_empty() { None } else { Some(Box::new(result)) }
715    }
716
717    #[salsa::tracked(returns(deref))]
718    pub fn for_crate_and_deps(db: &'db dyn HirDatabase, krate: Crate) -> Box<[Arc<Self>]> {
719        krate.transitive_deps(db).iter().map(|&dep| Self::for_crate(db, dep).clone()).collect()
720    }
721}
722
723impl<'db> TraitImpls<'db> {
724    fn collect_def_map(db: &'db dyn HirDatabase, def_map: &DefMap) -> Self {
725        let lang_items = hir_def::lang_item::lang_items(db, def_map.krate());
726        let mut map = FxHashMap::default();
727        collect(db, def_map, lang_items, &mut map);
728        let mut map = map
729            .into_iter()
730            .map(|(trait_id, trait_map)| (trait_id, trait_map.finish()))
731            .collect::<FxHashMap<_, _>>();
732        map.shrink_to_fit();
733        return Self { map };
734
735        fn collect<'db>(
736            db: &'db dyn HirDatabase,
737            def_map: &DefMap,
738            lang_items: &LangItems,
739            map: &mut FxHashMap<TraitId, OneTraitImplsBuilder<'db>>,
740        ) {
741            for (_module_id, module_data) in def_map.modules() {
742                for impl_id in module_data.scope.trait_impls() {
743                    let trait_ref = match db.impl_trait(impl_id) {
744                        Some(tr) => tr.instantiate_identity().skip_norm_wip(),
745                        None => continue,
746                    };
747                    // Reservation impls should be ignored during trait resolution, so we never need
748                    // them during type analysis. See rust-lang/rust#64631 for details.
749                    //
750                    // FIXME: Reservation impls should be considered during coherence checks. If we are
751                    // (ever) to implement coherence checks, this filtering should be done by the trait
752                    // solver.
753                    if AttrFlags::query(db, impl_id.into())
754                        .contains(AttrFlags::RUSTC_RESERVATION_IMPL)
755                    {
756                        continue;
757                    }
758
759                    let self_ty = trait_ref.self_ty();
760                    if self_ty_has_error_constructor(self_ty) {
761                        // If we see `impl Foo for NoSuchType`, just ignore it.
762                        continue;
763                    }
764
765                    let interner = DbInterner::new_no_crate(db);
766                    let entry = map.entry(trait_ref.def_id.0).or_default();
767                    match simplify_type(interner, self_ty, TreatParams::InstantiateWithInfer) {
768                        Some(self_ty) => {
769                            entry.non_blanket_impls.entry(self_ty).or_default().0.push(impl_id)
770                        }
771                        None => entry.blanket_impls.push(impl_id),
772                    }
773                }
774
775                for impl_id in module_data.scope.builtin_derive_impls() {
776                    let loc = impl_id.loc(db);
777                    let Some(trait_id) = loc.trait_.get_id(lang_items) else { continue };
778                    let entry = map.entry(trait_id).or_default();
779                    let entry = entry
780                        .non_blanket_impls
781                        .entry(SimplifiedType::Adt(loc.adt.into()))
782                        .or_default();
783                    entry.1.push(impl_id);
784                }
785
786                // To better support custom derives, collect impls in all unnamed const items.
787                // const _: () = { ... };
788                for konst in module_data.scope.unnamed_consts() {
789                    let body = Body::of(db, konst.into());
790                    for (_, block_def_map) in body.blocks(db) {
791                        collect(db, block_def_map, lang_items, map);
792                    }
793                }
794            }
795        }
796    }
797
798    pub fn blanket_impls(&self, for_trait: TraitId) -> &[ImplId] {
799        self.map.get(&for_trait).map(|it| &*it.blanket_impls).unwrap_or_default()
800    }
801
802    /// Queries whether `self_ty` has potentially applicable implementations of `trait_`.
803    pub fn has_impls_for_trait_and_self_ty(
804        &self,
805        trait_: TraitId,
806        self_ty: &SimplifiedType<'db>,
807    ) -> bool {
808        self.map.get(&trait_).is_some_and(|trait_impls| {
809            trait_impls.non_blanket_impls.contains_key(self_ty)
810                || !trait_impls.blanket_impls.is_empty()
811        })
812    }
813
814    pub fn for_trait_and_self_ty(
815        &'db self,
816        trait_: TraitId,
817        self_ty: &SimplifiedType<'db>,
818    ) -> (&'db [ImplId], &'db [BuiltinDeriveImplId]) {
819        self.map
820            .get(&trait_)
821            .and_then(|map| map.non_blanket_impls.get(self_ty))
822            .map(|it| (&*it.0, &*it.1))
823            .unwrap_or_default()
824    }
825
826    pub fn for_trait(
827        &self,
828        trait_: TraitId,
829        mut callback: impl FnMut(Either<&[ImplId], &[BuiltinDeriveImplId]>),
830    ) {
831        if let Some(impls) = self.map.get(&trait_) {
832            callback(Either::Left(&impls.blanket_impls));
833            for impls in impls.non_blanket_impls.values() {
834                callback(Either::Left(&impls.0));
835                callback(Either::Right(&impls.1));
836            }
837        }
838    }
839
840    pub fn for_self_ty(
841        &self,
842        self_ty: &SimplifiedType<'db>,
843        mut callback: impl FnMut(Either<&[ImplId], &[BuiltinDeriveImplId]>),
844    ) {
845        for for_trait in self.map.values() {
846            if let Some(for_ty) = for_trait.non_blanket_impls.get(self_ty) {
847                callback(Either::Left(&for_ty.0));
848                callback(Either::Right(&for_ty.1));
849            }
850        }
851    }
852
853    pub fn for_each_crate_and_block<R: VisitorResult>(
854        db: &'db dyn HirDatabase,
855        krate: Crate,
856        block: Option<BlockIdLt<'db>>,
857        for_each: &mut dyn FnMut(&TraitImpls<'db>) -> R,
858    ) -> R {
859        let blocks = std::iter::successors(block, |block| block.module(db).block(db));
860        for impl_ in blocks.filter_map(|block| Self::for_block(db, block)) {
861            try_visit!(for_each(impl_));
862        }
863        for impl_ in Self::for_crate_and_deps(db, krate) {
864            try_visit!(for_each(impl_));
865        }
866        R::output()
867    }
868
869    /// Like [`Self::for_each_crate_and_block()`], but takes in account two blocks, one for a trait and one for a self type.
870    pub fn for_each_crate_and_block_trait_and_type<R: VisitorResult>(
871        db: &'db dyn HirDatabase,
872        krate: Crate,
873        type_block: Option<BlockIdLt<'db>>,
874        trait_block: Option<BlockIdLt<'db>>,
875        for_each: &mut dyn FnMut(&TraitImpls<'db>) -> R,
876    ) -> R {
877        let in_self_and_deps = TraitImpls::for_crate_and_deps(db, krate);
878        for impl_ in in_self_and_deps {
879            try_visit!(for_each(impl_));
880        }
881
882        // We must not provide duplicate impls to the solver. Therefore we work with the following strategy:
883        // start from each block, and walk ancestors until you meet the other block. If they never meet,
884        // that means there can't be duplicate impls; if they meet, we stop the search of the deeper block.
885        // This breaks when they are equal (both will stop immediately), therefore we handle this case
886        // specifically.
887        let blocks_iter = |block: Option<BlockIdLt<'db>>| {
888            std::iter::successors(block, |block| block.module(db).block(db))
889        };
890        let for_each_block = |current_block: Option<BlockIdLt<'db>>,
891                              other_block: Option<BlockIdLt<'db>>| {
892            blocks_iter(current_block)
893                .take_while(move |&block| {
894                    other_block.is_none_or(|other_block| other_block != block)
895                })
896                .filter_map(move |block| TraitImpls::for_block(db, block))
897        };
898        if trait_block == type_block {
899            for impl_ in
900                blocks_iter(trait_block).filter_map(|block| TraitImpls::for_block(db, block))
901            {
902                try_visit!(for_each(impl_));
903            }
904        } else {
905            for impl_ in for_each_block(trait_block, type_block) {
906                try_visit!(for_each(impl_));
907            }
908            for impl_ in for_each_block(type_block, trait_block) {
909                try_visit!(for_each(impl_));
910            }
911        }
912        R::output()
913    }
914}
915
916fn self_ty_has_error_constructor<'db>(mut self_ty: Ty<'db>) -> bool {
917    if !self_ty.references_non_lt_error() {
918        return false;
919    }
920
921    loop {
922        self_ty = match self_ty.kind() {
923            TyKind::Error(_) => return true,
924            TyKind::Ref(_, inner, _)
925            | TyKind::RawPtr(inner, _)
926            | TyKind::Array(inner, _)
927            | TyKind::Slice(inner)
928            | TyKind::Pat(inner, _) => inner,
929            TyKind::UnsafeBinder(inner) => inner.skip_binder(),
930            _ => return false,
931        };
932    }
933}
hir_ty/method_resolution.rs

hir_ty/
method_resolution.rs
