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