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