rustc_hir_typeck/method/
probe.rs

1use std::assert_matches::debug_assert_matches;
2use std::cell::{Cell, RefCell};
3use std::cmp::max;
4use std::ops::Deref;
5
6use rustc_attr_parsing::is_doc_alias_attrs_contain_symbol;
7use rustc_data_structures::fx::FxHashSet;
8use rustc_data_structures::sso::SsoHashSet;
9use rustc_errors::Applicability;
10use rustc_hir as hir;
11use rustc_hir::HirId;
12use rustc_hir::def::DefKind;
13use rustc_hir_analysis::autoderef::{self, Autoderef};
14use rustc_infer::infer::canonical::{Canonical, OriginalQueryValues, QueryResponse};
15use rustc_infer::infer::{self, DefineOpaqueTypes, InferOk, TyCtxtInferExt};
16use rustc_infer::traits::ObligationCauseCode;
17use rustc_middle::middle::stability;
18use rustc_middle::query::Providers;
19use rustc_middle::ty::elaborate::supertrait_def_ids;
20use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams, simplify_type};
21use rustc_middle::ty::{
22    self, AssocItem, AssocItemContainer, GenericArgs, GenericArgsRef, GenericParamDefKind,
23    ParamEnvAnd, Ty, TyCtxt, TypeVisitableExt, Upcast,
24};
25use rustc_middle::{bug, span_bug};
26use rustc_session::lint;
27use rustc_span::def_id::{DefId, LocalDefId};
28use rustc_span::edit_distance::{
29    edit_distance_with_substrings, find_best_match_for_name_with_substrings,
30};
31use rustc_span::{DUMMY_SP, Ident, Span, Symbol, sym};
32use rustc_trait_selection::error_reporting::infer::need_type_info::TypeAnnotationNeeded;
33use rustc_trait_selection::infer::InferCtxtExt as _;
34use rustc_trait_selection::traits::query::CanonicalTyGoal;
35use rustc_trait_selection::traits::query::evaluate_obligation::InferCtxtExt;
36use rustc_trait_selection::traits::query::method_autoderef::{
37    CandidateStep, MethodAutoderefBadTy, MethodAutoderefStepsResult,
38};
39use rustc_trait_selection::traits::{self, ObligationCause, ObligationCtxt};
40use smallvec::{SmallVec, smallvec};
41use tracing::{debug, instrument};
42
43use self::CandidateKind::*;
44pub(crate) use self::PickKind::*;
45use super::{CandidateSource, MethodError, NoMatchData, suggest};
46use crate::FnCtxt;
47
48/// Boolean flag used to indicate if this search is for a suggestion
49/// or not. If true, we can allow ambiguity and so forth.
50#[derive(Clone, Copy, Debug)]
51pub(crate) struct IsSuggestion(pub bool);
52
53pub(crate) struct ProbeContext<'a, 'tcx> {
54    fcx: &'a FnCtxt<'a, 'tcx>,
55    span: Span,
56    mode: Mode,
57    method_name: Option<Ident>,
58    return_type: Option<Ty<'tcx>>,
59
60    /// This is the OriginalQueryValues for the steps queries
61    /// that are answered in steps.
62    orig_steps_var_values: &'a OriginalQueryValues<'tcx>,
63    steps: &'tcx [CandidateStep<'tcx>],
64
65    inherent_candidates: Vec<Candidate<'tcx>>,
66    extension_candidates: Vec<Candidate<'tcx>>,
67    impl_dups: FxHashSet<DefId>,
68
69    /// When probing for names, include names that are close to the
70    /// requested name (by edit distance)
71    allow_similar_names: bool,
72
73    /// List of potential private candidates. Will be trimmed to ones that
74    /// actually apply and then the result inserted into `private_candidate`
75    private_candidates: Vec<Candidate<'tcx>>,
76
77    /// Some(candidate) if there is a private candidate
78    private_candidate: Cell<Option<(DefKind, DefId)>>,
79
80    /// Collects near misses when the candidate functions are missing a `self` keyword and is only
81    /// used for error reporting
82    static_candidates: RefCell<Vec<CandidateSource>>,
83
84    scope_expr_id: HirId,
85
86    /// Is this probe being done for a diagnostic? This will skip some error reporting
87    /// machinery, since we don't particularly care about, for example, similarly named
88    /// candidates if we're *reporting* similarly named candidates.
89    is_suggestion: IsSuggestion,
90}
91
92impl<'a, 'tcx> Deref for ProbeContext<'a, 'tcx> {
93    type Target = FnCtxt<'a, 'tcx>;
94    fn deref(&self) -> &Self::Target {
95        self.fcx
96    }
97}
98
99#[derive(Debug, Clone)]
100pub(crate) struct Candidate<'tcx> {
101    pub(crate) item: ty::AssocItem,
102    pub(crate) kind: CandidateKind<'tcx>,
103    pub(crate) import_ids: SmallVec<[LocalDefId; 1]>,
104}
105
106#[derive(Debug, Clone)]
107pub(crate) enum CandidateKind<'tcx> {
108    InherentImplCandidate { impl_def_id: DefId, receiver_steps: usize },
109    ObjectCandidate(ty::PolyTraitRef<'tcx>),
110    TraitCandidate(ty::PolyTraitRef<'tcx>),
111    WhereClauseCandidate(ty::PolyTraitRef<'tcx>),
112}
113
114#[derive(Debug, PartialEq, Eq, Copy, Clone)]
115enum ProbeResult {
116    NoMatch,
117    BadReturnType,
118    Match,
119}
120
121/// When adjusting a receiver we often want to do one of
122///
123/// - Add a `&` (or `&mut`), converting the receiver from `T` to `&T` (or `&mut T`)
124/// - If the receiver has type `*mut T`, convert it to `*const T`
125///
126/// This type tells us which one to do.
127///
128/// Note that in principle we could do both at the same time. For example, when the receiver has
129/// type `T`, we could autoref it to `&T`, then convert to `*const T`. Or, when it has type `*mut
130/// T`, we could convert it to `*const T`, then autoref to `&*const T`. However, currently we do
131/// (at most) one of these. Either the receiver has type `T` and we convert it to `&T` (or with
132/// `mut`), or it has type `*mut T` and we convert it to `*const T`.
133#[derive(Debug, PartialEq, Copy, Clone)]
134pub(crate) enum AutorefOrPtrAdjustment {
135    /// Receiver has type `T`, add `&` or `&mut` (if `T` is `mut`), and maybe also "unsize" it.
136    /// Unsizing is used to convert a `[T; N]` to `[T]`, which only makes sense when autorefing.
137    Autoref {
138        mutbl: hir::Mutability,
139
140        /// Indicates that the source expression should be "unsized" to a target type.
141        /// This is special-cased for just arrays unsizing to slices.
142        unsize: bool,
143    },
144    /// Receiver has type `*mut T`, convert to `*const T`
145    ToConstPtr,
146
147    /// Reborrow a `Pin<&mut T>` or `Pin<&T>`.
148    ReborrowPin(hir::Mutability),
149}
150
151impl AutorefOrPtrAdjustment {
152    fn get_unsize(&self) -> bool {
153        match self {
154            AutorefOrPtrAdjustment::Autoref { mutbl: _, unsize } => *unsize,
155            AutorefOrPtrAdjustment::ToConstPtr => false,
156            AutorefOrPtrAdjustment::ReborrowPin(_) => false,
157        }
158    }
159}
160
161/// Extra information required only for error reporting.
162#[derive(Debug)]
163struct PickDiagHints<'a, 'tcx> {
164    /// Unstable candidates alongside the stable ones.
165    unstable_candidates: Option<Vec<(Candidate<'tcx>, Symbol)>>,
166
167    /// Collects near misses when trait bounds for type parameters are unsatisfied and is only used
168    /// for error reporting
169    unsatisfied_predicates: &'a mut Vec<(
170        ty::Predicate<'tcx>,
171        Option<ty::Predicate<'tcx>>,
172        Option<ObligationCause<'tcx>>,
173    )>,
174}
175
176/// Criteria to apply when searching for a given Pick. This is used during
177/// the search for potentially shadowed methods to ensure we don't search
178/// more candidates than strictly necessary.
179#[derive(Debug)]
180struct PickConstraintsForShadowed {
181    autoderefs: usize,
182    receiver_steps: Option<usize>,
183    def_id: DefId,
184}
185
186impl PickConstraintsForShadowed {
187    fn may_shadow_based_on_autoderefs(&self, autoderefs: usize) -> bool {
188        autoderefs == self.autoderefs
189    }
190
191    fn candidate_may_shadow(&self, candidate: &Candidate<'_>) -> bool {
192        // An item never shadows itself
193        candidate.item.def_id != self.def_id
194            // and we're only concerned about inherent impls doing the shadowing.
195            // Shadowing can only occur if the shadowed is further along
196            // the Receiver dereferencing chain than the shadowed.
197            && match candidate.kind {
198                CandidateKind::InherentImplCandidate { receiver_steps, .. } => match self.receiver_steps {
199                    Some(shadowed_receiver_steps) => receiver_steps > shadowed_receiver_steps,
200                    _ => false
201                },
202                _ => false
203            }
204    }
205}
206
207#[derive(Debug, Clone)]
208pub(crate) struct Pick<'tcx> {
209    pub item: ty::AssocItem,
210    pub kind: PickKind<'tcx>,
211    pub import_ids: SmallVec<[LocalDefId; 1]>,
212
213    /// Indicates that the source expression should be autoderef'd N times
214    /// ```ignore (not-rust)
215    /// A = expr | *expr | **expr | ...
216    /// ```
217    pub autoderefs: usize,
218
219    /// Indicates that we want to add an autoref (and maybe also unsize it), or if the receiver is
220    /// `*mut T`, convert it to `*const T`.
221    pub autoref_or_ptr_adjustment: Option<AutorefOrPtrAdjustment>,
222    pub self_ty: Ty<'tcx>,
223
224    /// Unstable candidates alongside the stable ones.
225    unstable_candidates: Vec<(Candidate<'tcx>, Symbol)>,
226
227    /// Number of jumps along the `Receiver::Target` chain we followed
228    /// to identify this method. Used only for deshadowing errors.
229    /// Only applies for inherent impls.
230    pub receiver_steps: Option<usize>,
231
232    /// Candidates that were shadowed by supertraits.
233    pub shadowed_candidates: Vec<ty::AssocItem>,
234}
235
236#[derive(Clone, Debug, PartialEq, Eq)]
237pub(crate) enum PickKind<'tcx> {
238    InherentImplPick,
239    ObjectPick,
240    TraitPick,
241    WhereClausePick(
242        // Trait
243        ty::PolyTraitRef<'tcx>,
244    ),
245}
246
247pub(crate) type PickResult<'tcx> = Result<Pick<'tcx>, MethodError<'tcx>>;
248
249#[derive(PartialEq, Eq, Copy, Clone, Debug)]
250pub(crate) enum Mode {
251    // An expression of the form `receiver.method_name(...)`.
252    // Autoderefs are performed on `receiver`, lookup is done based on the
253    // `self` argument of the method, and static methods aren't considered.
254    MethodCall,
255    // An expression of the form `Type::item` or `<T>::item`.
256    // No autoderefs are performed, lookup is done based on the type each
257    // implementation is for, and static methods are included.
258    Path,
259}
260
261#[derive(PartialEq, Eq, Copy, Clone, Debug)]
262pub(crate) enum ProbeScope {
263    // Single candidate coming from pre-resolved delegation method.
264    Single(DefId),
265
266    // Assemble candidates coming only from traits in scope.
267    TraitsInScope,
268
269    // Assemble candidates coming from all traits.
270    AllTraits,
271}
272
273impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
274    /// This is used to offer suggestions to users. It returns methods
275    /// that could have been called which have the desired return
276    /// type. Some effort is made to rule out methods that, if called,
277    /// would result in an error (basically, the same criteria we
278    /// would use to decide if a method is a plausible fit for
279    /// ambiguity purposes).
280    #[instrument(level = "debug", skip(self, candidate_filter))]
281    pub(crate) fn probe_for_return_type_for_diagnostic(
282        &self,
283        span: Span,
284        mode: Mode,
285        return_type: Ty<'tcx>,
286        self_ty: Ty<'tcx>,
287        scope_expr_id: HirId,
288        candidate_filter: impl Fn(&ty::AssocItem) -> bool,
289    ) -> Vec<ty::AssocItem> {
290        let method_names = self
291            .probe_op(
292                span,
293                mode,
294                None,
295                Some(return_type),
296                IsSuggestion(true),
297                self_ty,
298                scope_expr_id,
299                ProbeScope::AllTraits,
300                |probe_cx| Ok(probe_cx.candidate_method_names(candidate_filter)),
301            )
302            .unwrap_or_default();
303        method_names
304            .iter()
305            .flat_map(|&method_name| {
306                self.probe_op(
307                    span,
308                    mode,
309                    Some(method_name),
310                    Some(return_type),
311                    IsSuggestion(true),
312                    self_ty,
313                    scope_expr_id,
314                    ProbeScope::AllTraits,
315                    |probe_cx| probe_cx.pick(),
316                )
317                .ok()
318                .map(|pick| pick.item)
319            })
320            .collect()
321    }
322
323    #[instrument(level = "debug", skip(self))]
324    pub(crate) fn probe_for_name(
325        &self,
326        mode: Mode,
327        item_name: Ident,
328        return_type: Option<Ty<'tcx>>,
329        is_suggestion: IsSuggestion,
330        self_ty: Ty<'tcx>,
331        scope_expr_id: HirId,
332        scope: ProbeScope,
333    ) -> PickResult<'tcx> {
334        self.probe_op(
335            item_name.span,
336            mode,
337            Some(item_name),
338            return_type,
339            is_suggestion,
340            self_ty,
341            scope_expr_id,
342            scope,
343            |probe_cx| probe_cx.pick(),
344        )
345    }
346
347    #[instrument(level = "debug", skip(self))]
348    pub(crate) fn probe_for_name_many(
349        &self,
350        mode: Mode,
351        item_name: Ident,
352        return_type: Option<Ty<'tcx>>,
353        is_suggestion: IsSuggestion,
354        self_ty: Ty<'tcx>,
355        scope_expr_id: HirId,
356        scope: ProbeScope,
357    ) -> Result<Vec<Candidate<'tcx>>, MethodError<'tcx>> {
358        self.probe_op(
359            item_name.span,
360            mode,
361            Some(item_name),
362            return_type,
363            is_suggestion,
364            self_ty,
365            scope_expr_id,
366            scope,
367            |probe_cx| {
368                Ok(probe_cx
369                    .inherent_candidates
370                    .into_iter()
371                    .chain(probe_cx.extension_candidates)
372                    .collect())
373            },
374        )
375    }
376
377    pub(crate) fn probe_op<OP, R>(
378        &'a self,
379        span: Span,
380        mode: Mode,
381        method_name: Option<Ident>,
382        return_type: Option<Ty<'tcx>>,
383        is_suggestion: IsSuggestion,
384        self_ty: Ty<'tcx>,
385        scope_expr_id: HirId,
386        scope: ProbeScope,
387        op: OP,
388    ) -> Result<R, MethodError<'tcx>>
389    where
390        OP: FnOnce(ProbeContext<'_, 'tcx>) -> Result<R, MethodError<'tcx>>,
391    {
392        let mut orig_values = OriginalQueryValues::default();
393        let query_input = self.canonicalize_query(
394            ParamEnvAnd { param_env: self.param_env, value: self_ty },
395            &mut orig_values,
396        );
397
398        let steps = match mode {
399            Mode::MethodCall => self.tcx.method_autoderef_steps(query_input),
400            Mode::Path => self.probe(|_| {
401                // Mode::Path - the deref steps is "trivial". This turns
402                // our CanonicalQuery into a "trivial" QueryResponse. This
403                // is a bit inefficient, but I don't think that writing
404                // special handling for this "trivial case" is a good idea.
405
406                let infcx = &self.infcx;
407                let (ParamEnvAnd { param_env: _, value: self_ty }, canonical_inference_vars) =
408                    infcx.instantiate_canonical(span, &query_input.canonical);
409                debug!(?self_ty, ?query_input, "probe_op: Mode::Path");
410                MethodAutoderefStepsResult {
411                    steps: infcx.tcx.arena.alloc_from_iter([CandidateStep {
412                        self_ty: self.make_query_response_ignoring_pending_obligations(
413                            canonical_inference_vars,
414                            self_ty,
415                        ),
416                        autoderefs: 0,
417                        from_unsafe_deref: false,
418                        unsize: false,
419                        reachable_via_deref: true,
420                    }]),
421                    opt_bad_ty: None,
422                    reached_recursion_limit: false,
423                }
424            }),
425        };
426
427        // If our autoderef loop had reached the recursion limit,
428        // report an overflow error, but continue going on with
429        // the truncated autoderef list.
430        if steps.reached_recursion_limit && !is_suggestion.0 {
431            self.probe(|_| {
432                let ty = &steps
433                    .steps
434                    .last()
435                    .unwrap_or_else(|| span_bug!(span, "reached the recursion limit in 0 steps?"))
436                    .self_ty;
437                let ty = self
438                    .probe_instantiate_query_response(span, &orig_values, ty)
439                    .unwrap_or_else(|_| span_bug!(span, "instantiating {:?} failed?", ty));
440                autoderef::report_autoderef_recursion_limit_error(self.tcx, span, ty.value);
441            });
442        }
443
444        // If we encountered an `_` type or an error type during autoderef, this is
445        // ambiguous.
446        if let Some(bad_ty) = &steps.opt_bad_ty {
447            if is_suggestion.0 {
448                // Ambiguity was encountered during a suggestion. There's really
449                // not much use in suggesting methods in this case.
450                return Err(MethodError::NoMatch(NoMatchData {
451                    static_candidates: Vec::new(),
452                    unsatisfied_predicates: Vec::new(),
453                    out_of_scope_traits: Vec::new(),
454                    similar_candidate: None,
455                    mode,
456                }));
457            } else if bad_ty.reached_raw_pointer
458                && !self.tcx.features().arbitrary_self_types_pointers()
459                && !self.tcx.sess.at_least_rust_2018()
460            {
461                // this case used to be allowed by the compiler,
462                // so we do a future-compat lint here for the 2015 edition
463                // (see https://github.com/rust-lang/rust/issues/46906)
464                self.tcx.node_span_lint(
465                    lint::builtin::TYVAR_BEHIND_RAW_POINTER,
466                    scope_expr_id,
467                    span,
468                    |lint| {
469                        lint.primary_message("type annotations needed");
470                    },
471                );
472            } else {
473                // Ended up encountering a type variable when doing autoderef,
474                // but it may not be a type variable after processing obligations
475                // in our local `FnCtxt`, so don't call `structurally_resolve_type`.
476                let ty = &bad_ty.ty;
477                let ty = self
478                    .probe_instantiate_query_response(span, &orig_values, ty)
479                    .unwrap_or_else(|_| span_bug!(span, "instantiating {:?} failed?", ty));
480                let ty = self.resolve_vars_if_possible(ty.value);
481                let guar = match *ty.kind() {
482                    ty::Infer(ty::TyVar(_)) => {
483                        let raw_ptr_call = bad_ty.reached_raw_pointer
484                            && !self.tcx.features().arbitrary_self_types();
485                        let mut err = self.err_ctxt().emit_inference_failure_err(
486                            self.body_id,
487                            span,
488                            ty.into(),
489                            TypeAnnotationNeeded::E0282,
490                            !raw_ptr_call,
491                        );
492                        if raw_ptr_call {
493                            err.span_label(span, "cannot call a method on a raw pointer with an unknown pointee type");
494                        }
495                        err.emit()
496                    }
497                    ty::Error(guar) => guar,
498                    _ => bug!("unexpected bad final type in method autoderef"),
499                };
500                self.demand_eqtype(span, ty, Ty::new_error(self.tcx, guar));
501                return Err(MethodError::ErrorReported(guar));
502            }
503        }
504
505        debug!("ProbeContext: steps for self_ty={:?} are {:?}", self_ty, steps);
506
507        // this creates one big transaction so that all type variables etc
508        // that we create during the probe process are removed later
509        self.probe(|_| {
510            let mut probe_cx = ProbeContext::new(
511                self,
512                span,
513                mode,
514                method_name,
515                return_type,
516                &orig_values,
517                steps.steps,
518                scope_expr_id,
519                is_suggestion,
520            );
521
522            match scope {
523                ProbeScope::TraitsInScope => {
524                    probe_cx.assemble_inherent_candidates();
525                    probe_cx.assemble_extension_candidates_for_traits_in_scope();
526                }
527                ProbeScope::AllTraits => {
528                    probe_cx.assemble_inherent_candidates();
529                    probe_cx.assemble_extension_candidates_for_all_traits();
530                }
531                ProbeScope::Single(def_id) => {
532                    let item = self.tcx.associated_item(def_id);
533                    // FIXME(fn_delegation): Delegation to inherent methods is not yet supported.
534                    assert_eq!(item.container, AssocItemContainer::Trait);
535
536                    let trait_def_id = self.tcx.parent(def_id);
537                    let trait_span = self.tcx.def_span(trait_def_id);
538
539                    let trait_args = self.fresh_args_for_item(trait_span, trait_def_id);
540                    let trait_ref = ty::TraitRef::new_from_args(self.tcx, trait_def_id, trait_args);
541
542                    probe_cx.push_candidate(
543                        Candidate {
544                            item,
545                            kind: CandidateKind::TraitCandidate(ty::Binder::dummy(trait_ref)),
546                            import_ids: smallvec![],
547                        },
548                        false,
549                    );
550                }
551            };
552            op(probe_cx)
553        })
554    }
555}
556
557pub(crate) fn provide(providers: &mut Providers) {
558    providers.method_autoderef_steps = method_autoderef_steps;
559}
560
561fn method_autoderef_steps<'tcx>(
562    tcx: TyCtxt<'tcx>,
563    goal: CanonicalTyGoal<'tcx>,
564) -> MethodAutoderefStepsResult<'tcx> {
565    debug!("method_autoderef_steps({:?})", goal);
566
567    let (ref infcx, goal, inference_vars) = tcx.infer_ctxt().build_with_canonical(DUMMY_SP, &goal);
568    let ParamEnvAnd { param_env, value: self_ty } = goal;
569
570    // If arbitrary self types is not enabled, we follow the chain of
571    // `Deref<Target=T>`. If arbitrary self types is enabled, we instead
572    // follow the chain of `Receiver<Target=T>`, but we also record whether
573    // such types are reachable by following the (potentially shorter)
574    // chain of `Deref<Target=T>`. We will use the first list when finding
575    // potentially relevant function implementations (e.g. relevant impl blocks)
576    // but the second list when determining types that the receiver may be
577    // converted to, in order to find out which of those methods might actually
578    // be callable.
579    let mut autoderef_via_deref =
580        Autoderef::new(infcx, param_env, hir::def_id::CRATE_DEF_ID, DUMMY_SP, self_ty)
581            .include_raw_pointers()
582            .silence_errors();
583
584    let mut reached_raw_pointer = false;
585    let arbitrary_self_types_enabled =
586        tcx.features().arbitrary_self_types() || tcx.features().arbitrary_self_types_pointers();
587    let (mut steps, reached_recursion_limit): (Vec<_>, bool) = if arbitrary_self_types_enabled {
588        let reachable_via_deref =
589            autoderef_via_deref.by_ref().map(|_| true).chain(std::iter::repeat(false));
590
591        let mut autoderef_via_receiver =
592            Autoderef::new(infcx, param_env, hir::def_id::CRATE_DEF_ID, DUMMY_SP, self_ty)
593                .include_raw_pointers()
594                .use_receiver_trait()
595                .silence_errors();
596        let steps = autoderef_via_receiver
597            .by_ref()
598            .zip(reachable_via_deref)
599            .map(|((ty, d), reachable_via_deref)| {
600                let step = CandidateStep {
601                    self_ty: infcx
602                        .make_query_response_ignoring_pending_obligations(inference_vars, ty),
603                    autoderefs: d,
604                    from_unsafe_deref: reached_raw_pointer,
605                    unsize: false,
606                    reachable_via_deref,
607                };
608                if ty.is_raw_ptr() {
609                    // all the subsequent steps will be from_unsafe_deref
610                    reached_raw_pointer = true;
611                }
612                step
613            })
614            .collect();
615        (steps, autoderef_via_receiver.reached_recursion_limit())
616    } else {
617        let steps = autoderef_via_deref
618            .by_ref()
619            .map(|(ty, d)| {
620                let step = CandidateStep {
621                    self_ty: infcx
622                        .make_query_response_ignoring_pending_obligations(inference_vars, ty),
623                    autoderefs: d,
624                    from_unsafe_deref: reached_raw_pointer,
625                    unsize: false,
626                    reachable_via_deref: true,
627                };
628                if ty.is_raw_ptr() {
629                    // all the subsequent steps will be from_unsafe_deref
630                    reached_raw_pointer = true;
631                }
632                step
633            })
634            .collect();
635        (steps, autoderef_via_deref.reached_recursion_limit())
636    };
637    let final_ty = autoderef_via_deref.final_ty(true);
638    let opt_bad_ty = match final_ty.kind() {
639        ty::Infer(ty::TyVar(_)) | ty::Error(_) => Some(MethodAutoderefBadTy {
640            reached_raw_pointer,
641            ty: infcx.make_query_response_ignoring_pending_obligations(inference_vars, final_ty),
642        }),
643        ty::Array(elem_ty, _) => {
644            let autoderefs = steps.iter().filter(|s| s.reachable_via_deref).count() - 1;
645            steps.push(CandidateStep {
646                self_ty: infcx.make_query_response_ignoring_pending_obligations(
647                    inference_vars,
648                    Ty::new_slice(infcx.tcx, *elem_ty),
649                ),
650                autoderefs,
651                // this could be from an unsafe deref if we had
652                // a *mut/const [T; N]
653                from_unsafe_deref: reached_raw_pointer,
654                unsize: true,
655                reachable_via_deref: true, // this is always the final type from
656                                           // autoderef_via_deref
657            });
658
659            None
660        }
661        _ => None,
662    };
663
664    debug!("method_autoderef_steps: steps={:?} opt_bad_ty={:?}", steps, opt_bad_ty);
665
666    MethodAutoderefStepsResult {
667        steps: tcx.arena.alloc_from_iter(steps),
668        opt_bad_ty: opt_bad_ty.map(|ty| &*tcx.arena.alloc(ty)),
669        reached_recursion_limit,
670    }
671}
672
673impl<'a, 'tcx> ProbeContext<'a, 'tcx> {
674    fn new(
675        fcx: &'a FnCtxt<'a, 'tcx>,
676        span: Span,
677        mode: Mode,
678        method_name: Option<Ident>,
679        return_type: Option<Ty<'tcx>>,
680        orig_steps_var_values: &'a OriginalQueryValues<'tcx>,
681        steps: &'tcx [CandidateStep<'tcx>],
682        scope_expr_id: HirId,
683        is_suggestion: IsSuggestion,
684    ) -> ProbeContext<'a, 'tcx> {
685        ProbeContext {
686            fcx,
687            span,
688            mode,
689            method_name,
690            return_type,
691            inherent_candidates: Vec::new(),
692            extension_candidates: Vec::new(),
693            impl_dups: FxHashSet::default(),
694            orig_steps_var_values,
695            steps,
696            allow_similar_names: false,
697            private_candidates: Vec::new(),
698            private_candidate: Cell::new(None),
699            static_candidates: RefCell::new(Vec::new()),
700            scope_expr_id,
701            is_suggestion,
702        }
703    }
704
705    fn reset(&mut self) {
706        self.inherent_candidates.clear();
707        self.extension_candidates.clear();
708        self.impl_dups.clear();
709        self.private_candidates.clear();
710        self.private_candidate.set(None);
711        self.static_candidates.borrow_mut().clear();
712    }
713
714    /// When we're looking up a method by path (UFCS), we relate the receiver
715    /// types invariantly. When we are looking up a method by the `.` operator,
716    /// we relate them covariantly.
717    fn variance(&self) -> ty::Variance {
718        match self.mode {
719            Mode::MethodCall => ty::Covariant,
720            Mode::Path => ty::Invariant,
721        }
722    }
723
724    ///////////////////////////////////////////////////////////////////////////
725    // CANDIDATE ASSEMBLY
726
727    fn push_candidate(&mut self, candidate: Candidate<'tcx>, is_inherent: bool) {
728        let is_accessible = if let Some(name) = self.method_name {
729            let item = candidate.item;
730            let hir_id = self.tcx.local_def_id_to_hir_id(self.body_id);
731            let def_scope =
732                self.tcx.adjust_ident_and_get_scope(name, item.container_id(self.tcx), hir_id).1;
733            item.visibility(self.tcx).is_accessible_from(def_scope, self.tcx)
734        } else {
735            true
736        };
737        if is_accessible {
738            if is_inherent {
739                self.inherent_candidates.push(candidate);
740            } else {
741                self.extension_candidates.push(candidate);
742            }
743        } else {
744            self.private_candidates.push(candidate);
745        }
746    }
747
748    fn assemble_inherent_candidates(&mut self) {
749        for step in self.steps.iter() {
750            self.assemble_probe(&step.self_ty, step.autoderefs);
751        }
752    }
753
754    #[instrument(level = "debug", skip(self))]
755    fn assemble_probe(
756        &mut self,
757        self_ty: &Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>,
758        receiver_steps: usize,
759    ) {
760        let raw_self_ty = self_ty.value.value;
761        match *raw_self_ty.kind() {
762            ty::Dynamic(data, ..) if let Some(p) = data.principal() => {
763                // Subtle: we can't use `instantiate_query_response` here: using it will
764                // commit to all of the type equalities assumed by inference going through
765                // autoderef (see the `method-probe-no-guessing` test).
766                //
767                // However, in this code, it is OK if we end up with an object type that is
768                // "more general" than the object type that we are evaluating. For *every*
769                // object type `MY_OBJECT`, a function call that goes through a trait-ref
770                // of the form `<MY_OBJECT as SuperTraitOf(MY_OBJECT)>::func` is a valid
771                // `ObjectCandidate`, and it should be discoverable "exactly" through one
772                // of the iterations in the autoderef loop, so there is no problem with it
773                // being discoverable in another one of these iterations.
774                //
775                // Using `instantiate_canonical` on our
776                // `Canonical<QueryResponse<Ty<'tcx>>>` and then *throwing away* the
777                // `CanonicalVarValues` will exactly give us such a generalization - it
778                // will still match the original object type, but it won't pollute our
779                // type variables in any form, so just do that!
780                let (QueryResponse { value: generalized_self_ty, .. }, _ignored_var_values) =
781                    self.fcx.instantiate_canonical(self.span, self_ty);
782
783                self.assemble_inherent_candidates_from_object(generalized_self_ty);
784                self.assemble_inherent_impl_candidates_for_type(p.def_id(), receiver_steps);
785                if self.tcx.has_attr(p.def_id(), sym::rustc_has_incoherent_inherent_impls) {
786                    self.assemble_inherent_candidates_for_incoherent_ty(
787                        raw_self_ty,
788                        receiver_steps,
789                    );
790                }
791            }
792            ty::Adt(def, _) => {
793                let def_id = def.did();
794                self.assemble_inherent_impl_candidates_for_type(def_id, receiver_steps);
795                if self.tcx.has_attr(def_id, sym::rustc_has_incoherent_inherent_impls) {
796                    self.assemble_inherent_candidates_for_incoherent_ty(
797                        raw_self_ty,
798                        receiver_steps,
799                    );
800                }
801            }
802            ty::Foreign(did) => {
803                self.assemble_inherent_impl_candidates_for_type(did, receiver_steps);
804                if self.tcx.has_attr(did, sym::rustc_has_incoherent_inherent_impls) {
805                    self.assemble_inherent_candidates_for_incoherent_ty(
806                        raw_self_ty,
807                        receiver_steps,
808                    );
809                }
810            }
811            ty::Param(_) => {
812                self.assemble_inherent_candidates_from_param(raw_self_ty);
813            }
814            ty::Bool
815            | ty::Char
816            | ty::Int(_)
817            | ty::Uint(_)
818            | ty::Float(_)
819            | ty::Str
820            | ty::Array(..)
821            | ty::Slice(_)
822            | ty::RawPtr(_, _)
823            | ty::Ref(..)
824            | ty::Never
825            | ty::Tuple(..) => {
826                self.assemble_inherent_candidates_for_incoherent_ty(raw_self_ty, receiver_steps)
827            }
828            _ => {}
829        }
830    }
831
832    fn assemble_inherent_candidates_for_incoherent_ty(
833        &mut self,
834        self_ty: Ty<'tcx>,
835        receiver_steps: usize,
836    ) {
837        let Some(simp) = simplify_type(self.tcx, self_ty, TreatParams::InstantiateWithInfer) else {
838            bug!("unexpected incoherent type: {:?}", self_ty)
839        };
840        for &impl_def_id in self.tcx.incoherent_impls(simp).into_iter() {
841            self.assemble_inherent_impl_probe(impl_def_id, receiver_steps);
842        }
843    }
844
845    fn assemble_inherent_impl_candidates_for_type(&mut self, def_id: DefId, receiver_steps: usize) {
846        let impl_def_ids = self.tcx.at(self.span).inherent_impls(def_id).into_iter();
847        for &impl_def_id in impl_def_ids {
848            self.assemble_inherent_impl_probe(impl_def_id, receiver_steps);
849        }
850    }
851
852    #[instrument(level = "debug", skip(self))]
853    fn assemble_inherent_impl_probe(&mut self, impl_def_id: DefId, receiver_steps: usize) {
854        if !self.impl_dups.insert(impl_def_id) {
855            return; // already visited
856        }
857
858        for item in self.impl_or_trait_item(impl_def_id) {
859            if !self.has_applicable_self(&item) {
860                // No receiver declared. Not a candidate.
861                self.record_static_candidate(CandidateSource::Impl(impl_def_id));
862                continue;
863            }
864            self.push_candidate(
865                Candidate {
866                    item,
867                    kind: InherentImplCandidate { impl_def_id, receiver_steps },
868                    import_ids: smallvec![],
869                },
870                true,
871            );
872        }
873    }
874
875    #[instrument(level = "debug", skip(self))]
876    fn assemble_inherent_candidates_from_object(&mut self, self_ty: Ty<'tcx>) {
877        let principal = match self_ty.kind() {
878            ty::Dynamic(data, ..) => Some(data),
879            _ => None,
880        }
881        .and_then(|data| data.principal())
882        .unwrap_or_else(|| {
883            span_bug!(
884                self.span,
885                "non-object {:?} in assemble_inherent_candidates_from_object",
886                self_ty
887            )
888        });
889
890        // It is illegal to invoke a method on a trait instance that refers to
891        // the `Self` type. An [`DynCompatibilityViolation::SupertraitSelf`] error
892        // will be reported by `dyn_compatibility.rs` if the method refers to the
893        // `Self` type anywhere other than the receiver. Here, we use a
894        // instantiation that replaces `Self` with the object type itself. Hence,
895        // a `&self` method will wind up with an argument type like `&dyn Trait`.
896        let trait_ref = principal.with_self_ty(self.tcx, self_ty);
897        self.assemble_candidates_for_bounds(
898            traits::supertraits(self.tcx, trait_ref),
899            |this, new_trait_ref, item| {
900                this.push_candidate(
901                    Candidate {
902                        item,
903                        kind: ObjectCandidate(new_trait_ref),
904                        import_ids: smallvec![],
905                    },
906                    true,
907                );
908            },
909        );
910    }
911
912    #[instrument(level = "debug", skip(self))]
913    fn assemble_inherent_candidates_from_param(&mut self, param_ty: Ty<'tcx>) {
914        debug_assert_matches!(param_ty.kind(), ty::Param(_));
915
916        let tcx = self.tcx;
917        let bounds = self.param_env.caller_bounds().iter().filter_map(|predicate| {
918            let bound_predicate = predicate.kind();
919            match bound_predicate.skip_binder() {
920                ty::ClauseKind::Trait(trait_predicate) => DeepRejectCtxt::relate_rigid_rigid(tcx)
921                    .types_may_unify(param_ty, trait_predicate.trait_ref.self_ty())
922                    .then(|| bound_predicate.rebind(trait_predicate.trait_ref)),
923                ty::ClauseKind::RegionOutlives(_)
924                | ty::ClauseKind::TypeOutlives(_)
925                | ty::ClauseKind::Projection(_)
926                | ty::ClauseKind::ConstArgHasType(_, _)
927                | ty::ClauseKind::WellFormed(_)
928                | ty::ClauseKind::ConstEvaluatable(_)
929                | ty::ClauseKind::HostEffect(..) => None,
930            }
931        });
932
933        self.assemble_candidates_for_bounds(bounds, |this, poly_trait_ref, item| {
934            this.push_candidate(
935                Candidate {
936                    item,
937                    kind: WhereClauseCandidate(poly_trait_ref),
938                    import_ids: smallvec![],
939                },
940                true,
941            );
942        });
943    }
944
945    // Do a search through a list of bounds, using a callback to actually
946    // create the candidates.
947    fn assemble_candidates_for_bounds<F>(
948        &mut self,
949        bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>,
950        mut mk_cand: F,
951    ) where
952        F: for<'b> FnMut(&mut ProbeContext<'b, 'tcx>, ty::PolyTraitRef<'tcx>, ty::AssocItem),
953    {
954        for bound_trait_ref in bounds {
955            debug!("elaborate_bounds(bound_trait_ref={:?})", bound_trait_ref);
956            for item in self.impl_or_trait_item(bound_trait_ref.def_id()) {
957                if !self.has_applicable_self(&item) {
958                    self.record_static_candidate(CandidateSource::Trait(bound_trait_ref.def_id()));
959                } else {
960                    mk_cand(self, bound_trait_ref, item);
961                }
962            }
963        }
964    }
965
966    #[instrument(level = "debug", skip(self))]
967    fn assemble_extension_candidates_for_traits_in_scope(&mut self) {
968        let mut duplicates = FxHashSet::default();
969        let opt_applicable_traits = self.tcx.in_scope_traits(self.scope_expr_id);
970        if let Some(applicable_traits) = opt_applicable_traits {
971            for trait_candidate in applicable_traits.iter() {
972                let trait_did = trait_candidate.def_id;
973                if duplicates.insert(trait_did) {
974                    self.assemble_extension_candidates_for_trait(
975                        &trait_candidate.import_ids,
976                        trait_did,
977                    );
978                }
979            }
980        }
981    }
982
983    #[instrument(level = "debug", skip(self))]
984    fn assemble_extension_candidates_for_all_traits(&mut self) {
985        let mut duplicates = FxHashSet::default();
986        for trait_info in suggest::all_traits(self.tcx) {
987            if duplicates.insert(trait_info.def_id) {
988                self.assemble_extension_candidates_for_trait(&smallvec![], trait_info.def_id);
989            }
990        }
991    }
992
993    fn matches_return_type(&self, method: ty::AssocItem, expected: Ty<'tcx>) -> bool {
994        match method.kind {
995            ty::AssocKind::Fn { .. } => self.probe(|_| {
996                let args = self.fresh_args_for_item(self.span, method.def_id);
997                let fty = self.tcx.fn_sig(method.def_id).instantiate(self.tcx, args);
998                let fty = self.instantiate_binder_with_fresh_vars(self.span, infer::FnCall, fty);
999                self.can_eq(self.param_env, fty.output(), expected)
1000            }),
1001            _ => false,
1002        }
1003    }
1004
1005    #[instrument(level = "debug", skip(self))]
1006    fn assemble_extension_candidates_for_trait(
1007        &mut self,
1008        import_ids: &SmallVec<[LocalDefId; 1]>,
1009        trait_def_id: DefId,
1010    ) {
1011        let trait_args = self.fresh_args_for_item(self.span, trait_def_id);
1012        let trait_ref = ty::TraitRef::new_from_args(self.tcx, trait_def_id, trait_args);
1013
1014        if self.tcx.is_trait_alias(trait_def_id) {
1015            // For trait aliases, recursively assume all explicitly named traits are relevant
1016            for (bound_trait_pred, _) in
1017                traits::expand_trait_aliases(self.tcx, [(trait_ref.upcast(self.tcx), self.span)]).0
1018            {
1019                assert_eq!(bound_trait_pred.polarity(), ty::PredicatePolarity::Positive);
1020                let bound_trait_ref = bound_trait_pred.map_bound(|pred| pred.trait_ref);
1021                for item in self.impl_or_trait_item(bound_trait_ref.def_id()) {
1022                    if !self.has_applicable_self(&item) {
1023                        self.record_static_candidate(CandidateSource::Trait(
1024                            bound_trait_ref.def_id(),
1025                        ));
1026                    } else {
1027                        self.push_candidate(
1028                            Candidate {
1029                                item,
1030                                import_ids: import_ids.clone(),
1031                                kind: TraitCandidate(bound_trait_ref),
1032                            },
1033                            false,
1034                        );
1035                    }
1036                }
1037            }
1038        } else {
1039            debug_assert!(self.tcx.is_trait(trait_def_id));
1040            if self.tcx.trait_is_auto(trait_def_id) {
1041                return;
1042            }
1043            for item in self.impl_or_trait_item(trait_def_id) {
1044                // Check whether `trait_def_id` defines a method with suitable name.
1045                if !self.has_applicable_self(&item) {
1046                    debug!("method has inapplicable self");
1047                    self.record_static_candidate(CandidateSource::Trait(trait_def_id));
1048                    continue;
1049                }
1050                self.push_candidate(
1051                    Candidate {
1052                        item,
1053                        import_ids: import_ids.clone(),
1054                        kind: TraitCandidate(ty::Binder::dummy(trait_ref)),
1055                    },
1056                    false,
1057                );
1058            }
1059        }
1060    }
1061
1062    fn candidate_method_names(
1063        &self,
1064        candidate_filter: impl Fn(&ty::AssocItem) -> bool,
1065    ) -> Vec<Ident> {
1066        let mut set = FxHashSet::default();
1067        let mut names: Vec<_> = self
1068            .inherent_candidates
1069            .iter()
1070            .chain(&self.extension_candidates)
1071            .filter(|candidate| candidate_filter(&candidate.item))
1072            .filter(|candidate| {
1073                if let Some(return_ty) = self.return_type {
1074                    self.matches_return_type(candidate.item, return_ty)
1075                } else {
1076                    true
1077                }
1078            })
1079            // ensure that we don't suggest unstable methods
1080            .filter(|candidate| {
1081                // note that `DUMMY_SP` is ok here because it is only used for
1082                // suggestions and macro stuff which isn't applicable here.
1083                !matches!(
1084                    self.tcx.eval_stability(candidate.item.def_id, None, DUMMY_SP, None),
1085                    stability::EvalResult::Deny { .. }
1086                )
1087            })
1088            .map(|candidate| candidate.item.ident(self.tcx))
1089            .filter(|&name| set.insert(name))
1090            .collect();
1091
1092        // Sort them by the name so we have a stable result.
1093        names.sort_by(|a, b| a.as_str().cmp(b.as_str()));
1094        names
1095    }
1096
1097    ///////////////////////////////////////////////////////////////////////////
1098    // THE ACTUAL SEARCH
1099
1100    #[instrument(level = "debug", skip(self))]
1101    fn pick(mut self) -> PickResult<'tcx> {
1102        assert!(self.method_name.is_some());
1103
1104        let mut unsatisfied_predicates = Vec::new();
1105
1106        if let Some(r) = self.pick_core(&mut unsatisfied_predicates) {
1107            return r;
1108        }
1109
1110        // If it's a `lookup_probe_for_diagnostic`, then quit early. No need to
1111        // probe for other candidates.
1112        if self.is_suggestion.0 {
1113            return Err(MethodError::NoMatch(NoMatchData {
1114                static_candidates: vec![],
1115                unsatisfied_predicates: vec![],
1116                out_of_scope_traits: vec![],
1117                similar_candidate: None,
1118                mode: self.mode,
1119            }));
1120        }
1121
1122        debug!("pick: actual search failed, assemble diagnostics");
1123
1124        let static_candidates = std::mem::take(self.static_candidates.get_mut());
1125        let private_candidate = self.private_candidate.take();
1126
1127        // things failed, so lets look at all traits, for diagnostic purposes now:
1128        self.reset();
1129
1130        let span = self.span;
1131        let tcx = self.tcx;
1132
1133        self.assemble_extension_candidates_for_all_traits();
1134
1135        let out_of_scope_traits = match self.pick_core(&mut Vec::new()) {
1136            Some(Ok(p)) => vec![p.item.container_id(self.tcx)],
1137            Some(Err(MethodError::Ambiguity(v))) => v
1138                .into_iter()
1139                .map(|source| match source {
1140                    CandidateSource::Trait(id) => id,
1141                    CandidateSource::Impl(impl_id) => match tcx.trait_id_of_impl(impl_id) {
1142                        Some(id) => id,
1143                        None => span_bug!(span, "found inherent method when looking at traits"),
1144                    },
1145                })
1146                .collect(),
1147            Some(Err(MethodError::NoMatch(NoMatchData {
1148                out_of_scope_traits: others, ..
1149            }))) => {
1150                assert!(others.is_empty());
1151                vec![]
1152            }
1153            _ => vec![],
1154        };
1155
1156        if let Some((kind, def_id)) = private_candidate {
1157            return Err(MethodError::PrivateMatch(kind, def_id, out_of_scope_traits));
1158        }
1159        let similar_candidate = self.probe_for_similar_candidate()?;
1160
1161        Err(MethodError::NoMatch(NoMatchData {
1162            static_candidates,
1163            unsatisfied_predicates,
1164            out_of_scope_traits,
1165            similar_candidate,
1166            mode: self.mode,
1167        }))
1168    }
1169
1170    fn pick_core(
1171        &self,
1172        unsatisfied_predicates: &mut Vec<(
1173            ty::Predicate<'tcx>,
1174            Option<ty::Predicate<'tcx>>,
1175            Option<ObligationCause<'tcx>>,
1176        )>,
1177    ) -> Option<PickResult<'tcx>> {
1178        // Pick stable methods only first, and consider unstable candidates if not found.
1179        self.pick_all_method(&mut PickDiagHints {
1180            // This first cycle, maintain a list of unstable candidates which
1181            // we encounter. This will end up in the Pick for diagnostics.
1182            unstable_candidates: Some(Vec::new()),
1183            // Contribute to the list of unsatisfied predicates which may
1184            // also be used for diagnostics.
1185            unsatisfied_predicates,
1186        })
1187        .or_else(|| {
1188            self.pick_all_method(&mut PickDiagHints {
1189                // On the second search, don't provide a special list of unstable
1190                // candidates. This indicates to the picking code that it should
1191                // in fact include such unstable candidates in the actual
1192                // search.
1193                unstable_candidates: None,
1194                // And there's no need to duplicate ourselves in the
1195                // unsatisifed predicates list. Provide a throwaway list.
1196                unsatisfied_predicates: &mut Vec::new(),
1197            })
1198        })
1199    }
1200
1201    fn pick_all_method<'b>(
1202        &self,
1203        pick_diag_hints: &mut PickDiagHints<'b, 'tcx>,
1204    ) -> Option<PickResult<'tcx>> {
1205        let track_unstable_candidates = pick_diag_hints.unstable_candidates.is_some();
1206        self.steps
1207            .iter()
1208            // At this point we're considering the types to which the receiver can be converted,
1209            // so we want to follow the `Deref` chain not the `Receiver` chain. Filter out
1210            // steps which can only be reached by following the (longer) `Receiver` chain.
1211            .filter(|step| step.reachable_via_deref)
1212            .filter(|step| {
1213                debug!("pick_all_method: step={:?}", step);
1214                // skip types that are from a type error or that would require dereferencing
1215                // a raw pointer
1216                !step.self_ty.value.references_error() && !step.from_unsafe_deref
1217            })
1218            .find_map(|step| {
1219                let InferOk { value: self_ty, obligations: _ } = self
1220                    .fcx
1221                    .probe_instantiate_query_response(
1222                        self.span,
1223                        self.orig_steps_var_values,
1224                        &step.self_ty,
1225                    )
1226                    .unwrap_or_else(|_| {
1227                        span_bug!(self.span, "{:?} was applicable but now isn't?", step.self_ty)
1228                    });
1229
1230                let by_value_pick = self.pick_by_value_method(step, self_ty, pick_diag_hints);
1231
1232                // Check for shadowing of a by-reference method by a by-value method (see comments on check_for_shadowing)
1233                if let Some(by_value_pick) = by_value_pick {
1234                    if let Ok(by_value_pick) = by_value_pick.as_ref() {
1235                        if by_value_pick.kind == PickKind::InherentImplPick {
1236                            for mutbl in [hir::Mutability::Not, hir::Mutability::Mut] {
1237                                if let Err(e) = self.check_for_shadowed_autorefd_method(
1238                                    by_value_pick,
1239                                    step,
1240                                    self_ty,
1241                                    mutbl,
1242                                    track_unstable_candidates,
1243                                ) {
1244                                    return Some(Err(e));
1245                                }
1246                            }
1247                        }
1248                    }
1249                    return Some(by_value_pick);
1250                }
1251
1252                let autoref_pick = self.pick_autorefd_method(
1253                    step,
1254                    self_ty,
1255                    hir::Mutability::Not,
1256                    pick_diag_hints,
1257                    None,
1258                );
1259                // Check for shadowing of a by-mut-ref method by a by-reference method (see comments on check_for_shadowing)
1260                if let Some(autoref_pick) = autoref_pick {
1261                    if let Ok(autoref_pick) = autoref_pick.as_ref() {
1262                        // Check we're not shadowing others
1263                        if autoref_pick.kind == PickKind::InherentImplPick {
1264                            if let Err(e) = self.check_for_shadowed_autorefd_method(
1265                                autoref_pick,
1266                                step,
1267                                self_ty,
1268                                hir::Mutability::Mut,
1269                                track_unstable_candidates,
1270                            ) {
1271                                return Some(Err(e));
1272                            }
1273                        }
1274                    }
1275                    return Some(autoref_pick);
1276                }
1277
1278                // Note that no shadowing errors are produced from here on,
1279                // as we consider const ptr methods.
1280                // We allow new methods that take *mut T to shadow
1281                // methods which took *const T, so there is no entry in
1282                // this list for the results of `pick_const_ptr_method`.
1283                // The reason is that the standard pointer cast method
1284                // (on a mutable pointer) always already shadows the
1285                // cast method (on a const pointer). So, if we added
1286                // `pick_const_ptr_method` to this method, the anti-
1287                // shadowing algorithm would always complain about
1288                // the conflict between *const::cast and *mut::cast.
1289                // In practice therefore this does constrain us:
1290                // we cannot add new
1291                //   self: *mut Self
1292                // methods to types such as NonNull or anything else
1293                // which implements Receiver, because this might in future
1294                // shadow existing methods taking
1295                //   self: *const NonNull<Self>
1296                // in the pointee. In practice, methods taking raw pointers
1297                // are rare, and it seems that it should be easily possible
1298                // to avoid such compatibility breaks.
1299                // We also don't check for reborrowed pin methods which
1300                // may be shadowed; these also seem unlikely to occur.
1301                self.pick_autorefd_method(
1302                    step,
1303                    self_ty,
1304                    hir::Mutability::Mut,
1305                    pick_diag_hints,
1306                    None,
1307                )
1308                .or_else(|| self.pick_const_ptr_method(step, self_ty, pick_diag_hints))
1309                .or_else(|| self.pick_reborrow_pin_method(step, self_ty, pick_diag_hints))
1310            })
1311    }
1312
1313    /// Check for cases where arbitrary self types allows shadowing
1314    /// of methods that might be a compatibility break. Specifically,
1315    /// we have something like:
1316    /// ```ignore (illustrative)
1317    /// struct A;
1318    /// impl A {
1319    ///   fn foo(self: &NonNull<A>) {}
1320    ///      // note this is by reference
1321    /// }
1322    /// ```
1323    /// then we've come along and added this method to `NonNull`:
1324    /// ```ignore (illustrative)
1325    ///   fn foo(self)  // note this is by value
1326    /// ```
1327    /// Report an error in this case.
1328    fn check_for_shadowed_autorefd_method(
1329        &self,
1330        possible_shadower: &Pick<'tcx>,
1331        step: &CandidateStep<'tcx>,
1332        self_ty: Ty<'tcx>,
1333        mutbl: hir::Mutability,
1334        track_unstable_candidates: bool,
1335    ) -> Result<(), MethodError<'tcx>> {
1336        // The errors emitted by this function are part of
1337        // the arbitrary self types work, and should not impact
1338        // other users.
1339        if !self.tcx.features().arbitrary_self_types()
1340            && !self.tcx.features().arbitrary_self_types_pointers()
1341        {
1342            return Ok(());
1343        }
1344
1345        // We don't want to remember any of the diagnostic hints from this
1346        // shadow search, but we do need to provide Some/None for the
1347        // unstable_candidates in order to reflect the behavior of the
1348        // main search.
1349        let mut pick_diag_hints = PickDiagHints {
1350            unstable_candidates: if track_unstable_candidates { Some(Vec::new()) } else { None },
1351            unsatisfied_predicates: &mut Vec::new(),
1352        };
1353        // Set criteria for how we find methods possibly shadowed by 'possible_shadower'
1354        let pick_constraints = PickConstraintsForShadowed {
1355            // It's the same `self` type...
1356            autoderefs: possible_shadower.autoderefs,
1357            // ... but the method was found in an impl block determined
1358            // by searching further along the Receiver chain than the other,
1359            // showing that it's a smart pointer type causing the problem...
1360            receiver_steps: possible_shadower.receiver_steps,
1361            // ... and they don't end up pointing to the same item in the
1362            // first place (could happen with things like blanket impls for T)
1363            def_id: possible_shadower.item.def_id,
1364        };
1365        // A note on the autoderefs above. Within pick_by_value_method, an extra
1366        // autoderef may be applied in order to reborrow a reference with
1367        // a different lifetime. That seems as though it would break the
1368        // logic of these constraints, since the number of autoderefs could
1369        // no longer be used to identify the fundamental type of the receiver.
1370        // However, this extra autoderef is applied only to by-value calls
1371        // where the receiver is already a reference. So this situation would
1372        // only occur in cases where the shadowing looks like this:
1373        // ```
1374        // struct A;
1375        // impl A {
1376        //   fn foo(self: &&NonNull<A>) {}
1377        //      // note this is by DOUBLE reference
1378        // }
1379        // ```
1380        // then we've come along and added this method to `NonNull`:
1381        // ```
1382        //   fn foo(&self)  // note this is by single reference
1383        // ```
1384        // and the call is:
1385        // ```
1386        // let bar = NonNull<Foo>;
1387        // let bar = &foo;
1388        // bar.foo();
1389        // ```
1390        // In these circumstances, the logic is wrong, and we wouldn't spot
1391        // the shadowing, because the autoderef-based maths wouldn't line up.
1392        // This is a niche case and we can live without generating an error
1393        // in the case of such shadowing.
1394        let potentially_shadowed_pick = self.pick_autorefd_method(
1395            step,
1396            self_ty,
1397            mutbl,
1398            &mut pick_diag_hints,
1399            Some(&pick_constraints),
1400        );
1401        // Look for actual pairs of shadower/shadowed which are
1402        // the sort of shadowing case we want to avoid. Specifically...
1403        if let Some(Ok(possible_shadowed)) = potentially_shadowed_pick.as_ref() {
1404            let sources = [possible_shadower, possible_shadowed]
1405                .into_iter()
1406                .map(|p| self.candidate_source_from_pick(p))
1407                .collect();
1408            return Err(MethodError::Ambiguity(sources));
1409        }
1410        Ok(())
1411    }
1412
1413    /// For each type `T` in the step list, this attempts to find a method where
1414    /// the (transformed) self type is exactly `T`. We do however do one
1415    /// transformation on the adjustment: if we are passing a region pointer in,
1416    /// we will potentially *reborrow* it to a shorter lifetime. This allows us
1417    /// to transparently pass `&mut` pointers, in particular, without consuming
1418    /// them for their entire lifetime.
1419    fn pick_by_value_method(
1420        &self,
1421        step: &CandidateStep<'tcx>,
1422        self_ty: Ty<'tcx>,
1423        pick_diag_hints: &mut PickDiagHints<'_, 'tcx>,
1424    ) -> Option<PickResult<'tcx>> {
1425        if step.unsize {
1426            return None;
1427        }
1428
1429        self.pick_method(self_ty, pick_diag_hints, None).map(|r| {
1430            r.map(|mut pick| {
1431                pick.autoderefs = step.autoderefs;
1432
1433                match *step.self_ty.value.value.kind() {
1434                    // Insert a `&*` or `&mut *` if this is a reference type:
1435                    ty::Ref(_, _, mutbl) => {
1436                        pick.autoderefs += 1;
1437                        pick.autoref_or_ptr_adjustment = Some(AutorefOrPtrAdjustment::Autoref {
1438                            mutbl,
1439                            unsize: pick.autoref_or_ptr_adjustment.is_some_and(|a| a.get_unsize()),
1440                        })
1441                    }
1442
1443                    ty::Adt(def, args)
1444                        if self.tcx.features().pin_ergonomics()
1445                            && self.tcx.is_lang_item(def.did(), hir::LangItem::Pin) =>
1446                    {
1447                        // make sure this is a pinned reference (and not a `Pin<Box>` or something)
1448                        if let ty::Ref(_, _, mutbl) = args[0].expect_ty().kind() {
1449                            pick.autoref_or_ptr_adjustment =
1450                                Some(AutorefOrPtrAdjustment::ReborrowPin(*mutbl));
1451                        }
1452                    }
1453
1454                    _ => (),
1455                }
1456
1457                pick
1458            })
1459        })
1460    }
1461
1462    fn pick_autorefd_method(
1463        &self,
1464        step: &CandidateStep<'tcx>,
1465        self_ty: Ty<'tcx>,
1466        mutbl: hir::Mutability,
1467        pick_diag_hints: &mut PickDiagHints<'_, 'tcx>,
1468        pick_constraints: Option<&PickConstraintsForShadowed>,
1469    ) -> Option<PickResult<'tcx>> {
1470        let tcx = self.tcx;
1471
1472        if let Some(pick_constraints) = pick_constraints {
1473            if !pick_constraints.may_shadow_based_on_autoderefs(step.autoderefs) {
1474                return None;
1475            }
1476        }
1477
1478        // In general, during probing we erase regions.
1479        let region = tcx.lifetimes.re_erased;
1480
1481        let autoref_ty = Ty::new_ref(tcx, region, self_ty, mutbl);
1482        self.pick_method(autoref_ty, pick_diag_hints, pick_constraints).map(|r| {
1483            r.map(|mut pick| {
1484                pick.autoderefs = step.autoderefs;
1485                pick.autoref_or_ptr_adjustment =
1486                    Some(AutorefOrPtrAdjustment::Autoref { mutbl, unsize: step.unsize });
1487                pick
1488            })
1489        })
1490    }
1491
1492    /// Looks for applicable methods if we reborrow a `Pin<&mut T>` as a `Pin<&T>`.
1493    #[instrument(level = "debug", skip(self, step, pick_diag_hints))]
1494    fn pick_reborrow_pin_method(
1495        &self,
1496        step: &CandidateStep<'tcx>,
1497        self_ty: Ty<'tcx>,
1498        pick_diag_hints: &mut PickDiagHints<'_, 'tcx>,
1499    ) -> Option<PickResult<'tcx>> {
1500        if !self.tcx.features().pin_ergonomics() {
1501            return None;
1502        }
1503
1504        // make sure self is a Pin<&mut T>
1505        let inner_ty = match self_ty.kind() {
1506            ty::Adt(def, args) if self.tcx.is_lang_item(def.did(), hir::LangItem::Pin) => {
1507                match args[0].expect_ty().kind() {
1508                    ty::Ref(_, ty, hir::Mutability::Mut) => *ty,
1509                    _ => {
1510                        return None;
1511                    }
1512                }
1513            }
1514            _ => return None,
1515        };
1516
1517        let region = self.tcx.lifetimes.re_erased;
1518        let autopin_ty = Ty::new_pinned_ref(self.tcx, region, inner_ty, hir::Mutability::Not);
1519        self.pick_method(autopin_ty, pick_diag_hints, None).map(|r| {
1520            r.map(|mut pick| {
1521                pick.autoderefs = step.autoderefs;
1522                pick.autoref_or_ptr_adjustment =
1523                    Some(AutorefOrPtrAdjustment::ReborrowPin(hir::Mutability::Not));
1524                pick
1525            })
1526        })
1527    }
1528
1529    /// If `self_ty` is `*mut T` then this picks `*const T` methods. The reason why we have a
1530    /// special case for this is because going from `*mut T` to `*const T` with autoderefs and
1531    /// autorefs would require dereferencing the pointer, which is not safe.
1532    fn pick_const_ptr_method(
1533        &self,
1534        step: &CandidateStep<'tcx>,
1535        self_ty: Ty<'tcx>,
1536        pick_diag_hints: &mut PickDiagHints<'_, 'tcx>,
1537    ) -> Option<PickResult<'tcx>> {
1538        // Don't convert an unsized reference to ptr
1539        if step.unsize {
1540            return None;
1541        }
1542
1543        let &ty::RawPtr(ty, hir::Mutability::Mut) = self_ty.kind() else {
1544            return None;
1545        };
1546
1547        let const_ptr_ty = Ty::new_imm_ptr(self.tcx, ty);
1548        self.pick_method(const_ptr_ty, pick_diag_hints, None).map(|r| {
1549            r.map(|mut pick| {
1550                pick.autoderefs = step.autoderefs;
1551                pick.autoref_or_ptr_adjustment = Some(AutorefOrPtrAdjustment::ToConstPtr);
1552                pick
1553            })
1554        })
1555    }
1556
1557    fn pick_method(
1558        &self,
1559        self_ty: Ty<'tcx>,
1560        pick_diag_hints: &mut PickDiagHints<'_, 'tcx>,
1561        pick_constraints: Option<&PickConstraintsForShadowed>,
1562    ) -> Option<PickResult<'tcx>> {
1563        debug!("pick_method(self_ty={})", self.ty_to_string(self_ty));
1564
1565        for (kind, candidates) in
1566            [("inherent", &self.inherent_candidates), ("extension", &self.extension_candidates)]
1567        {
1568            debug!("searching {} candidates", kind);
1569            let res =
1570                self.consider_candidates(self_ty, candidates, pick_diag_hints, pick_constraints);
1571            if let Some(pick) = res {
1572                return Some(pick);
1573            }
1574        }
1575
1576        if self.private_candidate.get().is_none() {
1577            if let Some(Ok(pick)) = self.consider_candidates(
1578                self_ty,
1579                &self.private_candidates,
1580                &mut PickDiagHints {
1581                    unstable_candidates: None,
1582                    unsatisfied_predicates: &mut vec![],
1583                },
1584                None,
1585            ) {
1586                self.private_candidate.set(Some((pick.item.as_def_kind(), pick.item.def_id)));
1587            }
1588        }
1589        None
1590    }
1591
1592    fn consider_candidates(
1593        &self,
1594        self_ty: Ty<'tcx>,
1595        candidates: &[Candidate<'tcx>],
1596        pick_diag_hints: &mut PickDiagHints<'_, 'tcx>,
1597        pick_constraints: Option<&PickConstraintsForShadowed>,
1598    ) -> Option<PickResult<'tcx>> {
1599        let mut applicable_candidates: Vec<_> = candidates
1600            .iter()
1601            .filter(|candidate| {
1602                pick_constraints
1603                    .map(|pick_constraints| pick_constraints.candidate_may_shadow(&candidate))
1604                    .unwrap_or(true)
1605            })
1606            .map(|probe| {
1607                (
1608                    probe,
1609                    self.consider_probe(
1610                        self_ty,
1611                        probe,
1612                        &mut pick_diag_hints.unsatisfied_predicates,
1613                    ),
1614                )
1615            })
1616            .filter(|&(_, status)| status != ProbeResult::NoMatch)
1617            .collect();
1618
1619        debug!("applicable_candidates: {:?}", applicable_candidates);
1620
1621        if applicable_candidates.len() > 1 {
1622            if let Some(pick) =
1623                self.collapse_candidates_to_trait_pick(self_ty, &applicable_candidates)
1624            {
1625                return Some(Ok(pick));
1626            }
1627        }
1628
1629        if let Some(uc) = &mut pick_diag_hints.unstable_candidates {
1630            applicable_candidates.retain(|&(candidate, _)| {
1631                if let stability::EvalResult::Deny { feature, .. } =
1632                    self.tcx.eval_stability(candidate.item.def_id, None, self.span, None)
1633                {
1634                    uc.push((candidate.clone(), feature));
1635                    return false;
1636                }
1637                true
1638            });
1639        }
1640
1641        if applicable_candidates.len() > 1 {
1642            // We collapse to a subtrait pick *after* filtering unstable candidates
1643            // to make sure we don't prefer a unstable subtrait method over a stable
1644            // supertrait method.
1645            if self.tcx.features().supertrait_item_shadowing() {
1646                if let Some(pick) =
1647                    self.collapse_candidates_to_subtrait_pick(self_ty, &applicable_candidates)
1648                {
1649                    return Some(Ok(pick));
1650                }
1651            }
1652
1653            let sources = candidates.iter().map(|p| self.candidate_source(p, self_ty)).collect();
1654            return Some(Err(MethodError::Ambiguity(sources)));
1655        }
1656
1657        applicable_candidates.pop().map(|(probe, status)| match status {
1658            ProbeResult::Match => Ok(probe.to_unadjusted_pick(
1659                self_ty,
1660                pick_diag_hints.unstable_candidates.clone().unwrap_or_default(),
1661            )),
1662            ProbeResult::NoMatch | ProbeResult::BadReturnType => Err(MethodError::BadReturnType),
1663        })
1664    }
1665}
1666
1667impl<'tcx> Pick<'tcx> {
1668    /// In case there were unstable name collisions, emit them as a lint.
1669    /// Checks whether two picks do not refer to the same trait item for the same `Self` type.
1670    /// Only useful for comparisons of picks in order to improve diagnostics.
1671    /// Do not use for type checking.
1672    pub(crate) fn differs_from(&self, other: &Self) -> bool {
1673        let Self {
1674            item: AssocItem { def_id, kind: _, container: _, trait_item_def_id: _ },
1675            kind: _,
1676            import_ids: _,
1677            autoderefs: _,
1678            autoref_or_ptr_adjustment: _,
1679            self_ty,
1680            unstable_candidates: _,
1681            receiver_steps: _,
1682            shadowed_candidates: _,
1683        } = *self;
1684        self_ty != other.self_ty || def_id != other.item.def_id
1685    }
1686
1687    /// In case there were unstable name collisions, emit them as a lint.
1688    pub(crate) fn maybe_emit_unstable_name_collision_hint(
1689        &self,
1690        tcx: TyCtxt<'tcx>,
1691        span: Span,
1692        scope_expr_id: HirId,
1693    ) {
1694        if self.unstable_candidates.is_empty() {
1695            return;
1696        }
1697        let def_kind = self.item.as_def_kind();
1698        tcx.node_span_lint(lint::builtin::UNSTABLE_NAME_COLLISIONS, scope_expr_id, span, |lint| {
1699            lint.primary_message(format!(
1700                "{} {} with this name may be added to the standard library in the future",
1701                tcx.def_kind_descr_article(def_kind, self.item.def_id),
1702                tcx.def_kind_descr(def_kind, self.item.def_id),
1703            ));
1704
1705            match (self.item.kind, self.item.container) {
1706                (ty::AssocKind::Fn { .. }, _) => {
1707                    // FIXME: This should be a `span_suggestion` instead of `help`
1708                    // However `self.span` only
1709                    // highlights the method name, so we can't use it. Also consider reusing
1710                    // the code from `report_method_error()`.
1711                    lint.help(format!(
1712                        "call with fully qualified syntax `{}(...)` to keep using the current \
1713                             method",
1714                        tcx.def_path_str(self.item.def_id),
1715                    ));
1716                }
1717                (ty::AssocKind::Const { name }, ty::AssocItemContainer::Trait) => {
1718                    let def_id = self.item.container_id(tcx);
1719                    lint.span_suggestion(
1720                        span,
1721                        "use the fully qualified path to the associated const",
1722                        format!("<{} as {}>::{}", self.self_ty, tcx.def_path_str(def_id), name),
1723                        Applicability::MachineApplicable,
1724                    );
1725                }
1726                _ => {}
1727            }
1728            tcx.disabled_nightly_features(
1729                lint,
1730                Some(scope_expr_id),
1731                self.unstable_candidates.iter().map(|(candidate, feature)| {
1732                    (format!(" `{}`", tcx.def_path_str(candidate.item.def_id)), *feature)
1733                }),
1734            );
1735        });
1736    }
1737}
1738
1739impl<'a, 'tcx> ProbeContext<'a, 'tcx> {
1740    fn select_trait_candidate(
1741        &self,
1742        trait_ref: ty::TraitRef<'tcx>,
1743    ) -> traits::SelectionResult<'tcx, traits::Selection<'tcx>> {
1744        let obligation =
1745            traits::Obligation::new(self.tcx, self.misc(self.span), self.param_env, trait_ref);
1746        traits::SelectionContext::new(self).select(&obligation)
1747    }
1748
1749    /// Used for ambiguous method call error reporting. Uses probing that throws away the result internally,
1750    /// so do not use to make a decision that may lead to a successful compilation.
1751    fn candidate_source(&self, candidate: &Candidate<'tcx>, self_ty: Ty<'tcx>) -> CandidateSource {
1752        match candidate.kind {
1753            InherentImplCandidate { .. } => {
1754                CandidateSource::Impl(candidate.item.container_id(self.tcx))
1755            }
1756            ObjectCandidate(_) | WhereClauseCandidate(_) => {
1757                CandidateSource::Trait(candidate.item.container_id(self.tcx))
1758            }
1759            TraitCandidate(trait_ref) => self.probe(|_| {
1760                let trait_ref =
1761                    self.instantiate_binder_with_fresh_vars(self.span, infer::FnCall, trait_ref);
1762                let (xform_self_ty, _) =
1763                    self.xform_self_ty(candidate.item, trait_ref.self_ty(), trait_ref.args);
1764                // Guide the trait selection to show impls that have methods whose type matches
1765                // up with the `self` parameter of the method.
1766                let _ = self.at(&ObligationCause::dummy(), self.param_env).sup(
1767                    DefineOpaqueTypes::Yes,
1768                    xform_self_ty,
1769                    self_ty,
1770                );
1771                match self.select_trait_candidate(trait_ref) {
1772                    Ok(Some(traits::ImplSource::UserDefined(ref impl_data))) => {
1773                        // If only a single impl matches, make the error message point
1774                        // to that impl.
1775                        CandidateSource::Impl(impl_data.impl_def_id)
1776                    }
1777                    _ => CandidateSource::Trait(candidate.item.container_id(self.tcx)),
1778                }
1779            }),
1780        }
1781    }
1782
1783    fn candidate_source_from_pick(&self, pick: &Pick<'tcx>) -> CandidateSource {
1784        match pick.kind {
1785            InherentImplPick => CandidateSource::Impl(pick.item.container_id(self.tcx)),
1786            ObjectPick | WhereClausePick(_) | TraitPick => {
1787                CandidateSource::Trait(pick.item.container_id(self.tcx))
1788            }
1789        }
1790    }
1791
1792    #[instrument(level = "trace", skip(self, possibly_unsatisfied_predicates), ret)]
1793    fn consider_probe(
1794        &self,
1795        self_ty: Ty<'tcx>,
1796        probe: &Candidate<'tcx>,
1797        possibly_unsatisfied_predicates: &mut Vec<(
1798            ty::Predicate<'tcx>,
1799            Option<ty::Predicate<'tcx>>,
1800            Option<ObligationCause<'tcx>>,
1801        )>,
1802    ) -> ProbeResult {
1803        debug!("consider_probe: self_ty={:?} probe={:?}", self_ty, probe);
1804
1805        self.probe(|snapshot| {
1806            let outer_universe = self.universe();
1807
1808            let mut result = ProbeResult::Match;
1809            let cause = &self.misc(self.span);
1810            let ocx = ObligationCtxt::new_with_diagnostics(self);
1811
1812            let mut trait_predicate = None;
1813            let (mut xform_self_ty, mut xform_ret_ty);
1814
1815            match probe.kind {
1816                InherentImplCandidate { impl_def_id, .. } => {
1817                    let impl_args = self.fresh_args_for_item(self.span, impl_def_id);
1818                    let impl_ty = self.tcx.type_of(impl_def_id).instantiate(self.tcx, impl_args);
1819                    (xform_self_ty, xform_ret_ty) =
1820                        self.xform_self_ty(probe.item, impl_ty, impl_args);
1821                    xform_self_ty = ocx.normalize(cause, self.param_env, xform_self_ty);
1822                    match ocx.relate(cause, self.param_env, self.variance(), self_ty, xform_self_ty)
1823                    {
1824                        Ok(()) => {}
1825                        Err(err) => {
1826                            debug!("--> cannot relate self-types {:?}", err);
1827                            return ProbeResult::NoMatch;
1828                        }
1829                    }
1830                    // FIXME: Weirdly, we normalize the ret ty in this candidate, but no other candidates.
1831                    xform_ret_ty = ocx.normalize(cause, self.param_env, xform_ret_ty);
1832                    // Check whether the impl imposes obligations we have to worry about.
1833                    let impl_def_id = probe.item.container_id(self.tcx);
1834                    let impl_bounds =
1835                        self.tcx.predicates_of(impl_def_id).instantiate(self.tcx, impl_args);
1836                    let impl_bounds = ocx.normalize(cause, self.param_env, impl_bounds);
1837                    // Convert the bounds into obligations.
1838                    ocx.register_obligations(traits::predicates_for_generics(
1839                        |idx, span| {
1840                            let code = ObligationCauseCode::WhereClauseInExpr(
1841                                impl_def_id,
1842                                span,
1843                                self.scope_expr_id,
1844                                idx,
1845                            );
1846                            self.cause(self.span, code)
1847                        },
1848                        self.param_env,
1849                        impl_bounds,
1850                    ));
1851                }
1852                TraitCandidate(poly_trait_ref) => {
1853                    // Some trait methods are excluded for arrays before 2021.
1854                    // (`array.into_iter()` wants a slice iterator for compatibility.)
1855                    if let Some(method_name) = self.method_name {
1856                        if self_ty.is_array() && !method_name.span.at_least_rust_2021() {
1857                            let trait_def = self.tcx.trait_def(poly_trait_ref.def_id());
1858                            if trait_def.skip_array_during_method_dispatch {
1859                                return ProbeResult::NoMatch;
1860                            }
1861                        }
1862
1863                        // Some trait methods are excluded for boxed slices before 2024.
1864                        // (`boxed_slice.into_iter()` wants a slice iterator for compatibility.)
1865                        if self_ty.boxed_ty().is_some_and(Ty::is_slice)
1866                            && !method_name.span.at_least_rust_2024()
1867                        {
1868                            let trait_def = self.tcx.trait_def(poly_trait_ref.def_id());
1869                            if trait_def.skip_boxed_slice_during_method_dispatch {
1870                                return ProbeResult::NoMatch;
1871                            }
1872                        }
1873                    }
1874
1875                    let trait_ref = self.instantiate_binder_with_fresh_vars(
1876                        self.span,
1877                        infer::FnCall,
1878                        poly_trait_ref,
1879                    );
1880                    let trait_ref = ocx.normalize(cause, self.param_env, trait_ref);
1881                    (xform_self_ty, xform_ret_ty) =
1882                        self.xform_self_ty(probe.item, trait_ref.self_ty(), trait_ref.args);
1883                    xform_self_ty = ocx.normalize(cause, self.param_env, xform_self_ty);
1884                    match self_ty.kind() {
1885                        // HACK: opaque types will match anything for which their bounds hold.
1886                        // Thus we need to prevent them from trying to match the `&_` autoref
1887                        // candidates that get created for `&self` trait methods.
1888                        ty::Alias(ty::Opaque, alias_ty)
1889                            if !self.next_trait_solver()
1890                                && self.infcx.can_define_opaque_ty(alias_ty.def_id)
1891                                && !xform_self_ty.is_ty_var() =>
1892                        {
1893                            return ProbeResult::NoMatch;
1894                        }
1895                        _ => match ocx.relate(
1896                            cause,
1897                            self.param_env,
1898                            self.variance(),
1899                            self_ty,
1900                            xform_self_ty,
1901                        ) {
1902                            Ok(()) => {}
1903                            Err(err) => {
1904                                debug!("--> cannot relate self-types {:?}", err);
1905                                return ProbeResult::NoMatch;
1906                            }
1907                        },
1908                    }
1909                    let obligation = traits::Obligation::new(
1910                        self.tcx,
1911                        cause.clone(),
1912                        self.param_env,
1913                        ty::Binder::dummy(trait_ref),
1914                    );
1915
1916                    // We only need this hack to deal with fatal overflow in the old solver.
1917                    if self.infcx.next_trait_solver() || self.infcx.predicate_may_hold(&obligation)
1918                    {
1919                        ocx.register_obligation(obligation);
1920                    } else {
1921                        result = ProbeResult::NoMatch;
1922                        if let Ok(Some(candidate)) = self.select_trait_candidate(trait_ref) {
1923                            for nested_obligation in candidate.nested_obligations() {
1924                                if !self.infcx.predicate_may_hold(&nested_obligation) {
1925                                    possibly_unsatisfied_predicates.push((
1926                                        self.resolve_vars_if_possible(nested_obligation.predicate),
1927                                        Some(self.resolve_vars_if_possible(obligation.predicate)),
1928                                        Some(nested_obligation.cause),
1929                                    ));
1930                                }
1931                            }
1932                        }
1933                    }
1934
1935                    trait_predicate = Some(trait_ref.upcast(self.tcx));
1936                }
1937                ObjectCandidate(poly_trait_ref) | WhereClauseCandidate(poly_trait_ref) => {
1938                    let trait_ref = self.instantiate_binder_with_fresh_vars(
1939                        self.span,
1940                        infer::FnCall,
1941                        poly_trait_ref,
1942                    );
1943                    (xform_self_ty, xform_ret_ty) =
1944                        self.xform_self_ty(probe.item, trait_ref.self_ty(), trait_ref.args);
1945                    xform_self_ty = ocx.normalize(cause, self.param_env, xform_self_ty);
1946                    match ocx.relate(cause, self.param_env, self.variance(), self_ty, xform_self_ty)
1947                    {
1948                        Ok(()) => {}
1949                        Err(err) => {
1950                            debug!("--> cannot relate self-types {:?}", err);
1951                            return ProbeResult::NoMatch;
1952                        }
1953                    }
1954                }
1955            }
1956
1957            // See <https://github.com/rust-lang/trait-system-refactor-initiative/issues/134>.
1958            //
1959            // In the new solver, check the well-formedness of the return type.
1960            // This emulates, in a way, the predicates that fall out of
1961            // normalizing the return type in the old solver.
1962            //
1963            // FIXME(-Znext-solver): We alternatively could check the predicates of
1964            // the method itself hold, but we intentionally do not do this in the old
1965            // solver b/c of cycles, and doing it in the new solver would be stronger.
1966            // This should be fixed in the future, since it likely leads to much better
1967            // method winnowing.
1968            if let Some(xform_ret_ty) = xform_ret_ty
1969                && self.infcx.next_trait_solver()
1970            {
1971                ocx.register_obligation(traits::Obligation::new(
1972                    self.tcx,
1973                    cause.clone(),
1974                    self.param_env,
1975                    ty::ClauseKind::WellFormed(xform_ret_ty.into()),
1976                ));
1977            }
1978
1979            // Evaluate those obligations to see if they might possibly hold.
1980            for error in ocx.select_where_possible() {
1981                result = ProbeResult::NoMatch;
1982                let nested_predicate = self.resolve_vars_if_possible(error.obligation.predicate);
1983                if let Some(trait_predicate) = trait_predicate
1984                    && nested_predicate == self.resolve_vars_if_possible(trait_predicate)
1985                {
1986                    // Don't report possibly unsatisfied predicates if the root
1987                    // trait obligation from a `TraitCandidate` is unsatisfied.
1988                    // That just means the candidate doesn't hold.
1989                } else {
1990                    possibly_unsatisfied_predicates.push((
1991                        nested_predicate,
1992                        Some(self.resolve_vars_if_possible(error.root_obligation.predicate))
1993                            .filter(|root_predicate| *root_predicate != nested_predicate),
1994                        Some(error.obligation.cause),
1995                    ));
1996                }
1997            }
1998
1999            if let ProbeResult::Match = result
2000                && let Some(return_ty) = self.return_type
2001                && let Some(mut xform_ret_ty) = xform_ret_ty
2002            {
2003                // `xform_ret_ty` has only been normalized for `InherentImplCandidate`.
2004                // We don't normalize the other candidates for perf/backwards-compat reasons...
2005                // but `self.return_type` is only set on the diagnostic-path, so we
2006                // should be okay doing it here.
2007                if !matches!(probe.kind, InherentImplCandidate { .. }) {
2008                    xform_ret_ty = ocx.normalize(&cause, self.param_env, xform_ret_ty);
2009                }
2010
2011                debug!("comparing return_ty {:?} with xform ret ty {:?}", return_ty, xform_ret_ty);
2012                match ocx.relate(cause, self.param_env, self.variance(), xform_ret_ty, return_ty) {
2013                    Ok(()) => {}
2014                    Err(_) => {
2015                        result = ProbeResult::BadReturnType;
2016                    }
2017                }
2018
2019                // Evaluate those obligations to see if they might possibly hold.
2020                for error in ocx.select_where_possible() {
2021                    result = ProbeResult::NoMatch;
2022                    possibly_unsatisfied_predicates.push((
2023                        error.obligation.predicate,
2024                        Some(error.root_obligation.predicate)
2025                            .filter(|predicate| *predicate != error.obligation.predicate),
2026                        Some(error.root_obligation.cause),
2027                    ));
2028                }
2029            }
2030
2031            // Previously, method probe used `evaluate_predicate` to determine if a predicate
2032            // was impossible to satisfy. This did a leak check, so we must also do a leak
2033            // check here to prevent backwards-incompatible ambiguity being introduced. See
2034            // `tests/ui/methods/leak-check-disquality.rs` for a simple example of when this
2035            // may happen.
2036            if let Err(_) = self.leak_check(outer_universe, Some(snapshot)) {
2037                result = ProbeResult::NoMatch;
2038            }
2039
2040            result
2041        })
2042    }
2043
2044    /// Sometimes we get in a situation where we have multiple probes that are all impls of the
2045    /// same trait, but we don't know which impl to use. In this case, since in all cases the
2046    /// external interface of the method can be determined from the trait, it's ok not to decide.
2047    /// We can basically just collapse all of the probes for various impls into one where-clause
2048    /// probe. This will result in a pending obligation so when more type-info is available we can
2049    /// make the final decision.
2050    ///
2051    /// Example (`tests/ui/method-two-trait-defer-resolution-1.rs`):
2052    ///
2053    /// ```ignore (illustrative)
2054    /// trait Foo { ... }
2055    /// impl Foo for Vec<i32> { ... }
2056    /// impl Foo for Vec<usize> { ... }
2057    /// ```
2058    ///
2059    /// Now imagine the receiver is `Vec<_>`. It doesn't really matter at this time which impl we
2060    /// use, so it's ok to just commit to "using the method from the trait Foo".
2061    fn collapse_candidates_to_trait_pick(
2062        &self,
2063        self_ty: Ty<'tcx>,
2064        probes: &[(&Candidate<'tcx>, ProbeResult)],
2065    ) -> Option<Pick<'tcx>> {
2066        // Do all probes correspond to the same trait?
2067        let container = probes[0].0.item.trait_container(self.tcx)?;
2068        for (p, _) in &probes[1..] {
2069            let p_container = p.item.trait_container(self.tcx)?;
2070            if p_container != container {
2071                return None;
2072            }
2073        }
2074
2075        // FIXME: check the return type here somehow.
2076        // If so, just use this trait and call it a day.
2077        Some(Pick {
2078            item: probes[0].0.item,
2079            kind: TraitPick,
2080            import_ids: probes[0].0.import_ids.clone(),
2081            autoderefs: 0,
2082            autoref_or_ptr_adjustment: None,
2083            self_ty,
2084            unstable_candidates: vec![],
2085            receiver_steps: None,
2086            shadowed_candidates: vec![],
2087        })
2088    }
2089
2090    /// Much like `collapse_candidates_to_trait_pick`, this method allows us to collapse
2091    /// multiple conflicting picks if there is one pick whose trait container is a subtrait
2092    /// of the trait containers of all of the other picks.
2093    ///
2094    /// This implements RFC #3624.
2095    fn collapse_candidates_to_subtrait_pick(
2096        &self,
2097        self_ty: Ty<'tcx>,
2098        probes: &[(&Candidate<'tcx>, ProbeResult)],
2099    ) -> Option<Pick<'tcx>> {
2100        let mut child_candidate = probes[0].0;
2101        let mut child_trait = child_candidate.item.trait_container(self.tcx)?;
2102        let mut supertraits: SsoHashSet<_> = supertrait_def_ids(self.tcx, child_trait).collect();
2103
2104        let mut remaining_candidates: Vec<_> = probes[1..].iter().map(|&(p, _)| p).collect();
2105        while !remaining_candidates.is_empty() {
2106            let mut made_progress = false;
2107            let mut next_round = vec![];
2108
2109            for remaining_candidate in remaining_candidates {
2110                let remaining_trait = remaining_candidate.item.trait_container(self.tcx)?;
2111                if supertraits.contains(&remaining_trait) {
2112                    made_progress = true;
2113                    continue;
2114                }
2115
2116                // This pick is not a supertrait of the `child_pick`.
2117                // Check if it's a subtrait of the `child_pick`, instead.
2118                // If it is, then it must have been a subtrait of every
2119                // other pick we've eliminated at this point. It will
2120                // take over at this point.
2121                let remaining_trait_supertraits: SsoHashSet<_> =
2122                    supertrait_def_ids(self.tcx, remaining_trait).collect();
2123                if remaining_trait_supertraits.contains(&child_trait) {
2124                    child_candidate = remaining_candidate;
2125                    child_trait = remaining_trait;
2126                    supertraits = remaining_trait_supertraits;
2127                    made_progress = true;
2128                    continue;
2129                }
2130
2131                // `child_pick` is not a supertrait of this pick.
2132                // Don't bail here, since we may be comparing two supertraits
2133                // of a common subtrait. These two supertraits won't be related
2134                // at all, but we will pick them up next round when we find their
2135                // child as we continue iterating in this round.
2136                next_round.push(remaining_candidate);
2137            }
2138
2139            if made_progress {
2140                // If we've made progress, iterate again.
2141                remaining_candidates = next_round;
2142            } else {
2143                // Otherwise, we must have at least two candidates which
2144                // are not related to each other at all.
2145                return None;
2146            }
2147        }
2148
2149        Some(Pick {
2150            item: child_candidate.item,
2151            kind: TraitPick,
2152            import_ids: child_candidate.import_ids.clone(),
2153            autoderefs: 0,
2154            autoref_or_ptr_adjustment: None,
2155            self_ty,
2156            unstable_candidates: vec![],
2157            shadowed_candidates: probes
2158                .iter()
2159                .map(|(c, _)| c.item)
2160                .filter(|item| item.def_id != child_candidate.item.def_id)
2161                .collect(),
2162            receiver_steps: None,
2163        })
2164    }
2165
2166    /// Similarly to `probe_for_return_type`, this method attempts to find the best matching
2167    /// candidate method where the method name may have been misspelled. Similarly to other
2168    /// edit distance based suggestions, we provide at most one such suggestion.
2169    #[instrument(level = "debug", skip(self))]
2170    pub(crate) fn probe_for_similar_candidate(
2171        &mut self,
2172    ) -> Result<Option<ty::AssocItem>, MethodError<'tcx>> {
2173        debug!("probing for method names similar to {:?}", self.method_name);
2174
2175        self.probe(|_| {
2176            let mut pcx = ProbeContext::new(
2177                self.fcx,
2178                self.span,
2179                self.mode,
2180                self.method_name,
2181                self.return_type,
2182                self.orig_steps_var_values,
2183                self.steps,
2184                self.scope_expr_id,
2185                IsSuggestion(true),
2186            );
2187            pcx.allow_similar_names = true;
2188            pcx.assemble_inherent_candidates();
2189            pcx.assemble_extension_candidates_for_all_traits();
2190
2191            let method_names = pcx.candidate_method_names(|_| true);
2192            pcx.allow_similar_names = false;
2193            let applicable_close_candidates: Vec<ty::AssocItem> = method_names
2194                .iter()
2195                .filter_map(|&method_name| {
2196                    pcx.reset();
2197                    pcx.method_name = Some(method_name);
2198                    pcx.assemble_inherent_candidates();
2199                    pcx.assemble_extension_candidates_for_all_traits();
2200                    pcx.pick_core(&mut Vec::new()).and_then(|pick| pick.ok()).map(|pick| pick.item)
2201                })
2202                .collect();
2203
2204            if applicable_close_candidates.is_empty() {
2205                Ok(None)
2206            } else {
2207                let best_name = {
2208                    let names = applicable_close_candidates
2209                        .iter()
2210                        .map(|cand| cand.name())
2211                        .collect::<Vec<Symbol>>();
2212                    find_best_match_for_name_with_substrings(
2213                        &names,
2214                        self.method_name.unwrap().name,
2215                        None,
2216                    )
2217                }
2218                .or_else(|| {
2219                    applicable_close_candidates
2220                        .iter()
2221                        .find(|cand| self.matches_by_doc_alias(cand.def_id))
2222                        .map(|cand| cand.name())
2223                });
2224                Ok(best_name.and_then(|best_name| {
2225                    applicable_close_candidates
2226                        .into_iter()
2227                        .find(|method| method.name() == best_name)
2228                }))
2229            }
2230        })
2231    }
2232
2233    ///////////////////////////////////////////////////////////////////////////
2234    // MISCELLANY
2235    fn has_applicable_self(&self, item: &ty::AssocItem) -> bool {
2236        // "Fast track" -- check for usage of sugar when in method call
2237        // mode.
2238        //
2239        // In Path mode (i.e., resolving a value like `T::next`), consider any
2240        // associated value (i.e., methods, constants) but not types.
2241        match self.mode {
2242            Mode::MethodCall => item.is_method(),
2243            Mode::Path => match item.kind {
2244                ty::AssocKind::Type { .. } => false,
2245                ty::AssocKind::Fn { .. } | ty::AssocKind::Const { .. } => true,
2246            },
2247        }
2248        // FIXME -- check for types that deref to `Self`,
2249        // like `Rc<Self>` and so on.
2250        //
2251        // Note also that the current code will break if this type
2252        // includes any of the type parameters defined on the method
2253        // -- but this could be overcome.
2254    }
2255
2256    fn record_static_candidate(&self, source: CandidateSource) {
2257        self.static_candidates.borrow_mut().push(source);
2258    }
2259
2260    #[instrument(level = "debug", skip(self))]
2261    fn xform_self_ty(
2262        &self,
2263        item: ty::AssocItem,
2264        impl_ty: Ty<'tcx>,
2265        args: GenericArgsRef<'tcx>,
2266    ) -> (Ty<'tcx>, Option<Ty<'tcx>>) {
2267        if item.is_fn() && self.mode == Mode::MethodCall {
2268            let sig = self.xform_method_sig(item.def_id, args);
2269            (sig.inputs()[0], Some(sig.output()))
2270        } else {
2271            (impl_ty, None)
2272        }
2273    }
2274
2275    #[instrument(level = "debug", skip(self))]
2276    fn xform_method_sig(&self, method: DefId, args: GenericArgsRef<'tcx>) -> ty::FnSig<'tcx> {
2277        let fn_sig = self.tcx.fn_sig(method);
2278        debug!(?fn_sig);
2279
2280        assert!(!args.has_escaping_bound_vars());
2281
2282        // It is possible for type parameters or early-bound lifetimes
2283        // to appear in the signature of `self`. The generic parameters
2284        // we are given do not include type/lifetime parameters for the
2285        // method yet. So create fresh variables here for those too,
2286        // if there are any.
2287        let generics = self.tcx.generics_of(method);
2288        assert_eq!(args.len(), generics.parent_count);
2289
2290        let xform_fn_sig = if generics.is_own_empty() {
2291            fn_sig.instantiate(self.tcx, args)
2292        } else {
2293            let args = GenericArgs::for_item(self.tcx, method, |param, _| {
2294                let i = param.index as usize;
2295                if i < args.len() {
2296                    args[i]
2297                } else {
2298                    match param.kind {
2299                        GenericParamDefKind::Lifetime => {
2300                            // In general, during probe we erase regions.
2301                            self.tcx.lifetimes.re_erased.into()
2302                        }
2303                        GenericParamDefKind::Type { .. } | GenericParamDefKind::Const { .. } => {
2304                            self.var_for_def(self.span, param)
2305                        }
2306                    }
2307                }
2308            });
2309            fn_sig.instantiate(self.tcx, args)
2310        };
2311
2312        self.tcx.instantiate_bound_regions_with_erased(xform_fn_sig)
2313    }
2314
2315    /// Determine if the given associated item type is relevant in the current context.
2316    fn is_relevant_kind_for_mode(&self, kind: ty::AssocKind) -> bool {
2317        match (self.mode, kind) {
2318            (Mode::MethodCall, ty::AssocKind::Fn { .. }) => true,
2319            (Mode::Path, ty::AssocKind::Const { .. } | ty::AssocKind::Fn { .. }) => true,
2320            _ => false,
2321        }
2322    }
2323
2324    /// Determine if the associated item with the given DefId matches
2325    /// the desired name via a doc alias.
2326    fn matches_by_doc_alias(&self, def_id: DefId) -> bool {
2327        let Some(method) = self.method_name else {
2328            return false;
2329        };
2330        let Some(local_def_id) = def_id.as_local() else {
2331            return false;
2332        };
2333        let hir_id = self.fcx.tcx.local_def_id_to_hir_id(local_def_id);
2334        let attrs = self.fcx.tcx.hir_attrs(hir_id);
2335
2336        if is_doc_alias_attrs_contain_symbol(attrs.into_iter(), method.name) {
2337            return true;
2338        }
2339
2340        for attr in attrs {
2341            if attr.has_name(sym::rustc_confusables) {
2342                let Some(confusables) = attr.meta_item_list() else {
2343                    continue;
2344                };
2345                // #[rustc_confusables("foo", "bar"))]
2346                for n in confusables {
2347                    if let Some(lit) = n.lit()
2348                        && method.name == lit.symbol
2349                    {
2350                        return true;
2351                    }
2352                }
2353            }
2354        }
2355        false
2356    }
2357
2358    /// Finds the method with the appropriate name (or return type, as the case may be). If
2359    /// `allow_similar_names` is set, find methods with close-matching names.
2360    // The length of the returned iterator is nearly always 0 or 1 and this
2361    // method is fairly hot.
2362    fn impl_or_trait_item(&self, def_id: DefId) -> SmallVec<[ty::AssocItem; 1]> {
2363        if let Some(name) = self.method_name {
2364            if self.allow_similar_names {
2365                let max_dist = max(name.as_str().len(), 3) / 3;
2366                self.tcx
2367                    .associated_items(def_id)
2368                    .in_definition_order()
2369                    .filter(|x| {
2370                        if !self.is_relevant_kind_for_mode(x.kind) {
2371                            return false;
2372                        }
2373                        if self.matches_by_doc_alias(x.def_id) {
2374                            return true;
2375                        }
2376                        match edit_distance_with_substrings(
2377                            name.as_str(),
2378                            x.name().as_str(),
2379                            max_dist,
2380                        ) {
2381                            Some(d) => d > 0,
2382                            None => false,
2383                        }
2384                    })
2385                    .copied()
2386                    .collect()
2387            } else {
2388                self.fcx
2389                    .associated_value(def_id, name)
2390                    .filter(|x| self.is_relevant_kind_for_mode(x.kind))
2391                    .map_or_else(SmallVec::new, |x| SmallVec::from_buf([x]))
2392            }
2393        } else {
2394            self.tcx
2395                .associated_items(def_id)
2396                .in_definition_order()
2397                .filter(|x| self.is_relevant_kind_for_mode(x.kind))
2398                .copied()
2399                .collect()
2400        }
2401    }
2402}
2403
2404impl<'tcx> Candidate<'tcx> {
2405    fn to_unadjusted_pick(
2406        &self,
2407        self_ty: Ty<'tcx>,
2408        unstable_candidates: Vec<(Candidate<'tcx>, Symbol)>,
2409    ) -> Pick<'tcx> {
2410        Pick {
2411            item: self.item,
2412            kind: match self.kind {
2413                InherentImplCandidate { .. } => InherentImplPick,
2414                ObjectCandidate(_) => ObjectPick,
2415                TraitCandidate(_) => TraitPick,
2416                WhereClauseCandidate(trait_ref) => {
2417                    // Only trait derived from where-clauses should
2418                    // appear here, so they should not contain any
2419                    // inference variables or other artifacts. This
2420                    // means they are safe to put into the
2421                    // `WhereClausePick`.
2422                    assert!(
2423                        !trait_ref.skip_binder().args.has_infer()
2424                            && !trait_ref.skip_binder().args.has_placeholders()
2425                    );
2426
2427                    WhereClausePick(trait_ref)
2428                }
2429            },
2430            import_ids: self.import_ids.clone(),
2431            autoderefs: 0,
2432            autoref_or_ptr_adjustment: None,
2433            self_ty,
2434            unstable_candidates,
2435            receiver_steps: match self.kind {
2436                InherentImplCandidate { receiver_steps, .. } => Some(receiver_steps),
2437                _ => None,
2438            },
2439            shadowed_candidates: vec![],
2440        }
2441    }
2442}