1 use super::suggest;
2 use super::CandidateSource;
3 use super::MethodError;
4 use super::NoMatchData;
5
6 use crate::errors::MethodCallOnUnknownRawPointee;
7 use crate::FnCtxt;
8 use rustc_data_structures::fx::FxHashSet;
9 use rustc_errors::Applicability;
10 use rustc_hir as hir;
11 use rustc_hir::def::DefKind;
12 use rustc_hir_analysis::autoderef::{self, Autoderef};
13 use rustc_infer::infer::canonical::OriginalQueryValues;
14 use rustc_infer::infer::canonical::{Canonical, QueryResponse};
15 use rustc_infer::infer::error_reporting::TypeAnnotationNeeded::E0282;
16 use rustc_infer::infer::DefineOpaqueTypes;
17 use rustc_infer::infer::{self, InferOk, TyCtxtInferExt};
18 use rustc_middle::middle::stability;
19 use rustc_middle::query::Providers;
20 use rustc_middle::ty::fast_reject::{simplify_type, TreatParams};
21 use rustc_middle::ty::AssocItem;
22 use rustc_middle::ty::GenericParamDefKind;
23 use rustc_middle::ty::ToPredicate;
24 use rustc_middle::ty::{self, ParamEnvAnd, Ty, TyCtxt, TypeFoldable, TypeVisitableExt};
25 use rustc_middle::ty::{InternalSubsts, SubstsRef};
26 use rustc_session::lint;
27 use rustc_span::def_id::DefId;
28 use rustc_span::def_id::LocalDefId;
29 use rustc_span::edit_distance::{
30 edit_distance_with_substrings, find_best_match_for_name_with_substrings,
31 };
32 use rustc_span::symbol::sym;
33 use rustc_span::{symbol::Ident, Span, Symbol, DUMMY_SP};
34 use rustc_trait_selection::traits::query::evaluate_obligation::InferCtxtExt;
35 use rustc_trait_selection::traits::query::method_autoderef::MethodAutoderefBadTy;
36 use rustc_trait_selection::traits::query::method_autoderef::{
37 CandidateStep, MethodAutoderefStepsResult,
38 };
39 use rustc_trait_selection::traits::query::CanonicalTyGoal;
40 use rustc_trait_selection::traits::NormalizeExt;
41 use rustc_trait_selection::traits::{self, ObligationCause};
42 use std::cell::RefCell;
43 use std::cmp::max;
44 use std::iter;
45 use std::ops::Deref;
46
47 use smallvec::{smallvec, SmallVec};
48
49 use self::CandidateKind::*;
50 pub use self::PickKind::*;
51
52 /// Boolean flag used to indicate if this search is for a suggestion
53 /// or not. If true, we can allow ambiguity and so forth.
54 #[derive(Clone, Copy, Debug)]
55 pub struct IsSuggestion(pub bool);
56
57 struct ProbeContext<'a, 'tcx> {
58 fcx: &'a FnCtxt<'a, 'tcx>,
59 span: Span,
60 mode: Mode,
61 method_name: Option<Ident>,
62 return_type: Option<Ty<'tcx>>,
63
64 /// This is the OriginalQueryValues for the steps queries
65 /// that are answered in steps.
66 orig_steps_var_values: &'a OriginalQueryValues<'tcx>,
67 steps: &'tcx [CandidateStep<'tcx>],
68
69 inherent_candidates: Vec<Candidate<'tcx>>,
70 extension_candidates: Vec<Candidate<'tcx>>,
71 impl_dups: FxHashSet<DefId>,
72
73 /// When probing for names, include names that are close to the
74 /// requested name (by edit distance)
75 allow_similar_names: bool,
76
77 /// Some(candidate) if there is a private candidate
78 private_candidate: Option<(DefKind, DefId)>,
79
80 /// Collects near misses when the candidate functions are missing a `self` keyword and is only
81 /// used for error reporting
82 static_candidates: RefCell<Vec<CandidateSource>>,
83
84 /// Collects near misses when trait bounds for type parameters are unsatisfied and is only used
85 /// for error reporting
86 unsatisfied_predicates: RefCell<
87 Vec<(ty::Predicate<'tcx>, Option<ty::Predicate<'tcx>>, Option<ObligationCause<'tcx>>)>,
88 >,
89
90 scope_expr_id: hir::HirId,
91 }
92
93 impl<'a, 'tcx> Deref for ProbeContext<'a, 'tcx> {
94 type Target = FnCtxt<'a, 'tcx>;
deref(&self) -> &Self::Target95 fn deref(&self) -> &Self::Target {
96 self.fcx
97 }
98 }
99
100 #[derive(Debug, Clone)]
101 pub(crate) struct Candidate<'tcx> {
102 // Candidates are (I'm not quite sure, but they are mostly) basically
103 // some metadata on top of a `ty::AssocItem` (without substs).
104 //
105 // However, method probing wants to be able to evaluate the predicates
106 // for a function with the substs applied - for example, if a function
107 // has `where Self: Sized`, we don't want to consider it unless `Self`
108 // is actually `Sized`, and similarly, return-type suggestions want
109 // to consider the "actual" return type.
110 //
111 // The way this is handled is through `xform_self_ty`. It contains
112 // the receiver type of this candidate, but `xform_self_ty`,
113 // `xform_ret_ty` and `kind` (which contains the predicates) have the
114 // generic parameters of this candidate substituted with the *same set*
115 // of inference variables, which acts as some weird sort of "query".
116 //
117 // When we check out a candidate, we require `xform_self_ty` to be
118 // a subtype of the passed-in self-type, and this equates the type
119 // variables in the rest of the fields.
120 //
121 // For example, if we have this candidate:
122 // ```
123 // trait Foo {
124 // fn foo(&self) where Self: Sized;
125 // }
126 // ```
127 //
128 // Then `xform_self_ty` will be `&'erased ?X` and `kind` will contain
129 // the predicate `?X: Sized`, so if we are evaluating `Foo` for a
130 // the receiver `&T`, we'll do the subtyping which will make `?X`
131 // get the right value, then when we evaluate the predicate we'll check
132 // if `T: Sized`.
133 xform_self_ty: Ty<'tcx>,
134 xform_ret_ty: Option<Ty<'tcx>>,
135 pub(crate) item: ty::AssocItem,
136 pub(crate) kind: CandidateKind<'tcx>,
137 pub(crate) import_ids: SmallVec<[LocalDefId; 1]>,
138 }
139
140 #[derive(Debug, Clone)]
141 pub(crate) enum CandidateKind<'tcx> {
142 InherentImplCandidate(
143 SubstsRef<'tcx>,
144 // Normalize obligations
145 Vec<traits::PredicateObligation<'tcx>>,
146 ),
147 ObjectCandidate,
148 TraitCandidate(ty::TraitRef<'tcx>),
149 WhereClauseCandidate(
150 // Trait
151 ty::PolyTraitRef<'tcx>,
152 ),
153 }
154
155 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
156 enum ProbeResult {
157 NoMatch,
158 BadReturnType,
159 Match,
160 }
161
162 /// When adjusting a receiver we often want to do one of
163 ///
164 /// - Add a `&` (or `&mut`), converting the receiver from `T` to `&T` (or `&mut T`)
165 /// - If the receiver has type `*mut T`, convert it to `*const T`
166 ///
167 /// This type tells us which one to do.
168 ///
169 /// Note that in principle we could do both at the same time. For example, when the receiver has
170 /// type `T`, we could autoref it to `&T`, then convert to `*const T`. Or, when it has type `*mut
171 /// T`, we could convert it to `*const T`, then autoref to `&*const T`. However, currently we do
172 /// (at most) one of these. Either the receiver has type `T` and we convert it to `&T` (or with
173 /// `mut`), or it has type `*mut T` and we convert it to `*const T`.
174 #[derive(Debug, PartialEq, Copy, Clone)]
175 pub enum AutorefOrPtrAdjustment {
176 /// Receiver has type `T`, add `&` or `&mut` (it `T` is `mut`), and maybe also "unsize" it.
177 /// Unsizing is used to convert a `[T; N]` to `[T]`, which only makes sense when autorefing.
178 Autoref {
179 mutbl: hir::Mutability,
180
181 /// Indicates that the source expression should be "unsized" to a target type.
182 /// This is special-cased for just arrays unsizing to slices.
183 unsize: bool,
184 },
185 /// Receiver has type `*mut T`, convert to `*const T`
186 ToConstPtr,
187 }
188
189 impl AutorefOrPtrAdjustment {
get_unsize(&self) -> bool190 fn get_unsize(&self) -> bool {
191 match self {
192 AutorefOrPtrAdjustment::Autoref { mutbl: _, unsize } => *unsize,
193 AutorefOrPtrAdjustment::ToConstPtr => false,
194 }
195 }
196 }
197
198 #[derive(Debug, Clone)]
199 pub struct Pick<'tcx> {
200 pub item: ty::AssocItem,
201 pub kind: PickKind<'tcx>,
202 pub import_ids: SmallVec<[LocalDefId; 1]>,
203
204 /// Indicates that the source expression should be autoderef'd N times
205 /// ```ignore (not-rust)
206 /// A = expr | *expr | **expr | ...
207 /// ```
208 pub autoderefs: usize,
209
210 /// Indicates that we want to add an autoref (and maybe also unsize it), or if the receiver is
211 /// `*mut T`, convert it to `*const T`.
212 pub autoref_or_ptr_adjustment: Option<AutorefOrPtrAdjustment>,
213 pub self_ty: Ty<'tcx>,
214
215 /// Unstable candidates alongside the stable ones.
216 unstable_candidates: Vec<(Candidate<'tcx>, Symbol)>,
217 }
218
219 #[derive(Clone, Debug, PartialEq, Eq)]
220 pub enum PickKind<'tcx> {
221 InherentImplPick,
222 ObjectPick,
223 TraitPick,
224 WhereClausePick(
225 // Trait
226 ty::PolyTraitRef<'tcx>,
227 ),
228 }
229
230 pub type PickResult<'tcx> = Result<Pick<'tcx>, MethodError<'tcx>>;
231
232 #[derive(PartialEq, Eq, Copy, Clone, Debug)]
233 pub enum Mode {
234 // An expression of the form `receiver.method_name(...)`.
235 // Autoderefs are performed on `receiver`, lookup is done based on the
236 // `self` argument of the method, and static methods aren't considered.
237 MethodCall,
238 // An expression of the form `Type::item` or `<T>::item`.
239 // No autoderefs are performed, lookup is done based on the type each
240 // implementation is for, and static methods are included.
241 Path,
242 }
243
244 #[derive(PartialEq, Eq, Copy, Clone, Debug)]
245 pub enum ProbeScope {
246 // Assemble candidates coming only from traits in scope.
247 TraitsInScope,
248
249 // Assemble candidates coming from all traits.
250 AllTraits,
251 }
252
253 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
254 /// This is used to offer suggestions to users. It returns methods
255 /// that could have been called which have the desired return
256 /// type. Some effort is made to rule out methods that, if called,
257 /// would result in an error (basically, the same criteria we
258 /// would use to decide if a method is a plausible fit for
259 /// ambiguity purposes).
260 #[instrument(level = "debug", skip(self, candidate_filter))]
probe_for_return_type( &self, span: Span, mode: Mode, return_type: Ty<'tcx>, self_ty: Ty<'tcx>, scope_expr_id: hir::HirId, candidate_filter: impl Fn(&ty::AssocItem) -> bool, ) -> Vec<ty::AssocItem>261 pub fn probe_for_return_type(
262 &self,
263 span: Span,
264 mode: Mode,
265 return_type: Ty<'tcx>,
266 self_ty: Ty<'tcx>,
267 scope_expr_id: hir::HirId,
268 candidate_filter: impl Fn(&ty::AssocItem) -> bool,
269 ) -> Vec<ty::AssocItem> {
270 let method_names = self
271 .probe_op(
272 span,
273 mode,
274 None,
275 Some(return_type),
276 IsSuggestion(true),
277 self_ty,
278 scope_expr_id,
279 ProbeScope::AllTraits,
280 |probe_cx| Ok(probe_cx.candidate_method_names(candidate_filter)),
281 )
282 .unwrap_or_default();
283 method_names
284 .iter()
285 .flat_map(|&method_name| {
286 self.probe_op(
287 span,
288 mode,
289 Some(method_name),
290 Some(return_type),
291 IsSuggestion(true),
292 self_ty,
293 scope_expr_id,
294 ProbeScope::AllTraits,
295 |probe_cx| probe_cx.pick(),
296 )
297 .ok()
298 .map(|pick| pick.item)
299 })
300 .collect()
301 }
302
303 #[instrument(level = "debug", skip(self))]
probe_for_name( &self, mode: Mode, item_name: Ident, return_type: Option<Ty<'tcx>>, is_suggestion: IsSuggestion, self_ty: Ty<'tcx>, scope_expr_id: hir::HirId, scope: ProbeScope, ) -> PickResult<'tcx>304 pub fn probe_for_name(
305 &self,
306 mode: Mode,
307 item_name: Ident,
308 return_type: Option<Ty<'tcx>>,
309 is_suggestion: IsSuggestion,
310 self_ty: Ty<'tcx>,
311 scope_expr_id: hir::HirId,
312 scope: ProbeScope,
313 ) -> PickResult<'tcx> {
314 self.probe_op(
315 item_name.span,
316 mode,
317 Some(item_name),
318 return_type,
319 is_suggestion,
320 self_ty,
321 scope_expr_id,
322 scope,
323 |probe_cx| probe_cx.pick(),
324 )
325 }
326
327 #[instrument(level = "debug", skip(self))]
probe_for_name_many( &self, mode: Mode, item_name: Ident, return_type: Option<Ty<'tcx>>, is_suggestion: IsSuggestion, self_ty: Ty<'tcx>, scope_expr_id: hir::HirId, scope: ProbeScope, ) -> Vec<Candidate<'tcx>>328 pub(crate) fn probe_for_name_many(
329 &self,
330 mode: Mode,
331 item_name: Ident,
332 return_type: Option<Ty<'tcx>>,
333 is_suggestion: IsSuggestion,
334 self_ty: Ty<'tcx>,
335 scope_expr_id: hir::HirId,
336 scope: ProbeScope,
337 ) -> Vec<Candidate<'tcx>> {
338 self.probe_op(
339 item_name.span,
340 mode,
341 Some(item_name),
342 return_type,
343 is_suggestion,
344 self_ty,
345 scope_expr_id,
346 scope,
347 |probe_cx| {
348 Ok(probe_cx
349 .inherent_candidates
350 .into_iter()
351 .chain(probe_cx.extension_candidates)
352 .collect())
353 },
354 )
355 .unwrap()
356 }
357
probe_op<OP, R>( &'a self, span: Span, mode: Mode, method_name: Option<Ident>, return_type: Option<Ty<'tcx>>, is_suggestion: IsSuggestion, self_ty: Ty<'tcx>, scope_expr_id: hir::HirId, scope: ProbeScope, op: OP, ) -> Result<R, MethodError<'tcx>> where OP: FnOnce(ProbeContext<'_, 'tcx>) -> Result<R, MethodError<'tcx>>,358 fn probe_op<OP, R>(
359 &'a self,
360 span: Span,
361 mode: Mode,
362 method_name: Option<Ident>,
363 return_type: Option<Ty<'tcx>>,
364 is_suggestion: IsSuggestion,
365 self_ty: Ty<'tcx>,
366 scope_expr_id: hir::HirId,
367 scope: ProbeScope,
368 op: OP,
369 ) -> Result<R, MethodError<'tcx>>
370 where
371 OP: FnOnce(ProbeContext<'_, 'tcx>) -> Result<R, MethodError<'tcx>>,
372 {
373 let mut orig_values = OriginalQueryValues::default();
374 let param_env_and_self_ty = self.canonicalize_query(
375 ParamEnvAnd { param_env: self.param_env, value: self_ty },
376 &mut orig_values,
377 );
378
379 let steps = match mode {
380 Mode::MethodCall => self.tcx.method_autoderef_steps(param_env_and_self_ty),
381 Mode::Path => self.probe(|_| {
382 // Mode::Path - the deref steps is "trivial". This turns
383 // our CanonicalQuery into a "trivial" QueryResponse. This
384 // is a bit inefficient, but I don't think that writing
385 // special handling for this "trivial case" is a good idea.
386
387 let infcx = &self.infcx;
388 let (ParamEnvAnd { param_env: _, value: self_ty }, canonical_inference_vars) =
389 infcx.instantiate_canonical_with_fresh_inference_vars(
390 span,
391 ¶m_env_and_self_ty,
392 );
393 debug!(
394 "probe_op: Mode::Path, param_env_and_self_ty={:?} self_ty={:?}",
395 param_env_and_self_ty, self_ty
396 );
397 MethodAutoderefStepsResult {
398 steps: infcx.tcx.arena.alloc_from_iter([CandidateStep {
399 self_ty: self.make_query_response_ignoring_pending_obligations(
400 canonical_inference_vars,
401 self_ty,
402 ),
403 autoderefs: 0,
404 from_unsafe_deref: false,
405 unsize: false,
406 }]),
407 opt_bad_ty: None,
408 reached_recursion_limit: false,
409 }
410 }),
411 };
412
413 // If our autoderef loop had reached the recursion limit,
414 // report an overflow error, but continue going on with
415 // the truncated autoderef list.
416 if steps.reached_recursion_limit {
417 self.probe(|_| {
418 let ty = &steps
419 .steps
420 .last()
421 .unwrap_or_else(|| span_bug!(span, "reached the recursion limit in 0 steps?"))
422 .self_ty;
423 let ty = self
424 .probe_instantiate_query_response(span, &orig_values, ty)
425 .unwrap_or_else(|_| span_bug!(span, "instantiating {:?} failed?", ty));
426 autoderef::report_autoderef_recursion_limit_error(self.tcx, span, ty.value);
427 });
428 }
429
430 // If we encountered an `_` type or an error type during autoderef, this is
431 // ambiguous.
432 if let Some(bad_ty) = &steps.opt_bad_ty {
433 if is_suggestion.0 {
434 // Ambiguity was encountered during a suggestion. Just keep going.
435 debug!("ProbeContext: encountered ambiguity in suggestion");
436 } else if bad_ty.reached_raw_pointer && !self.tcx.features().arbitrary_self_types {
437 // this case used to be allowed by the compiler,
438 // so we do a future-compat lint here for the 2015 edition
439 // (see https://github.com/rust-lang/rust/issues/46906)
440 if self.tcx.sess.rust_2018() {
441 self.tcx.sess.emit_err(MethodCallOnUnknownRawPointee { span });
442 } else {
443 self.tcx.struct_span_lint_hir(
444 lint::builtin::TYVAR_BEHIND_RAW_POINTER,
445 scope_expr_id,
446 span,
447 "type annotations needed",
448 |lint| lint,
449 );
450 }
451 } else {
452 // Ended up encountering a type variable when doing autoderef,
453 // but it may not be a type variable after processing obligations
454 // in our local `FnCtxt`, so don't call `structurally_resolve_type`.
455 let ty = &bad_ty.ty;
456 let ty = self
457 .probe_instantiate_query_response(span, &orig_values, ty)
458 .unwrap_or_else(|_| span_bug!(span, "instantiating {:?} failed?", ty));
459 let ty = self.resolve_vars_if_possible(ty.value);
460 let guar = match *ty.kind() {
461 ty::Infer(ty::TyVar(_)) => self
462 .err_ctxt()
463 .emit_inference_failure_err(self.body_id, span, ty.into(), E0282, true)
464 .emit(),
465 ty::Error(guar) => guar,
466 _ => bug!("unexpected bad final type in method autoderef"),
467 };
468 self.demand_eqtype(span, ty, Ty::new_error(self.tcx, guar));
469 return Err(MethodError::NoMatch(NoMatchData {
470 static_candidates: Vec::new(),
471 unsatisfied_predicates: Vec::new(),
472 out_of_scope_traits: Vec::new(),
473 similar_candidate: None,
474 mode,
475 }));
476 }
477 }
478
479 debug!("ProbeContext: steps for self_ty={:?} are {:?}", self_ty, steps);
480
481 // this creates one big transaction so that all type variables etc
482 // that we create during the probe process are removed later
483 self.probe(|_| {
484 let mut probe_cx = ProbeContext::new(
485 self,
486 span,
487 mode,
488 method_name,
489 return_type,
490 &orig_values,
491 steps.steps,
492 scope_expr_id,
493 );
494
495 probe_cx.assemble_inherent_candidates();
496 match scope {
497 ProbeScope::TraitsInScope => {
498 probe_cx.assemble_extension_candidates_for_traits_in_scope()
499 }
500 ProbeScope::AllTraits => probe_cx.assemble_extension_candidates_for_all_traits(),
501 };
502 op(probe_cx)
503 })
504 }
505 }
506
provide(providers: &mut Providers)507 pub fn provide(providers: &mut Providers) {
508 providers.method_autoderef_steps = method_autoderef_steps;
509 }
510
method_autoderef_steps<'tcx>( tcx: TyCtxt<'tcx>, goal: CanonicalTyGoal<'tcx>, ) -> MethodAutoderefStepsResult<'tcx>511 fn method_autoderef_steps<'tcx>(
512 tcx: TyCtxt<'tcx>,
513 goal: CanonicalTyGoal<'tcx>,
514 ) -> MethodAutoderefStepsResult<'tcx> {
515 debug!("method_autoderef_steps({:?})", goal);
516
517 let (ref infcx, goal, inference_vars) = tcx.infer_ctxt().build_with_canonical(DUMMY_SP, &goal);
518 let ParamEnvAnd { param_env, value: self_ty } = goal;
519
520 let mut autoderef =
521 Autoderef::new(infcx, param_env, hir::def_id::CRATE_DEF_ID, DUMMY_SP, self_ty)
522 .include_raw_pointers()
523 .silence_errors();
524 let mut reached_raw_pointer = false;
525 let mut steps: Vec<_> = autoderef
526 .by_ref()
527 .map(|(ty, d)| {
528 let step = CandidateStep {
529 self_ty: infcx.make_query_response_ignoring_pending_obligations(inference_vars, ty),
530 autoderefs: d,
531 from_unsafe_deref: reached_raw_pointer,
532 unsize: false,
533 };
534 if let ty::RawPtr(_) = ty.kind() {
535 // all the subsequent steps will be from_unsafe_deref
536 reached_raw_pointer = true;
537 }
538 step
539 })
540 .collect();
541
542 let final_ty = autoderef.final_ty(true);
543 let opt_bad_ty = match final_ty.kind() {
544 ty::Infer(ty::TyVar(_)) | ty::Error(_) => Some(MethodAutoderefBadTy {
545 reached_raw_pointer,
546 ty: infcx.make_query_response_ignoring_pending_obligations(inference_vars, final_ty),
547 }),
548 ty::Array(elem_ty, _) => {
549 let dereferences = steps.len() - 1;
550
551 steps.push(CandidateStep {
552 self_ty: infcx.make_query_response_ignoring_pending_obligations(
553 inference_vars,
554 Ty::new_slice(infcx.tcx, *elem_ty),
555 ),
556 autoderefs: dereferences,
557 // this could be from an unsafe deref if we had
558 // a *mut/const [T; N]
559 from_unsafe_deref: reached_raw_pointer,
560 unsize: true,
561 });
562
563 None
564 }
565 _ => None,
566 };
567
568 debug!("method_autoderef_steps: steps={:?} opt_bad_ty={:?}", steps, opt_bad_ty);
569
570 MethodAutoderefStepsResult {
571 steps: tcx.arena.alloc_from_iter(steps),
572 opt_bad_ty: opt_bad_ty.map(|ty| &*tcx.arena.alloc(ty)),
573 reached_recursion_limit: autoderef.reached_recursion_limit(),
574 }
575 }
576
577 impl<'a, 'tcx> ProbeContext<'a, 'tcx> {
new( fcx: &'a FnCtxt<'a, 'tcx>, span: Span, mode: Mode, method_name: Option<Ident>, return_type: Option<Ty<'tcx>>, orig_steps_var_values: &'a OriginalQueryValues<'tcx>, steps: &'tcx [CandidateStep<'tcx>], scope_expr_id: hir::HirId, ) -> ProbeContext<'a, 'tcx>578 fn new(
579 fcx: &'a FnCtxt<'a, 'tcx>,
580 span: Span,
581 mode: Mode,
582 method_name: Option<Ident>,
583 return_type: Option<Ty<'tcx>>,
584 orig_steps_var_values: &'a OriginalQueryValues<'tcx>,
585 steps: &'tcx [CandidateStep<'tcx>],
586 scope_expr_id: hir::HirId,
587 ) -> ProbeContext<'a, 'tcx> {
588 ProbeContext {
589 fcx,
590 span,
591 mode,
592 method_name,
593 return_type,
594 inherent_candidates: Vec::new(),
595 extension_candidates: Vec::new(),
596 impl_dups: FxHashSet::default(),
597 orig_steps_var_values,
598 steps,
599 allow_similar_names: false,
600 private_candidate: None,
601 static_candidates: RefCell::new(Vec::new()),
602 unsatisfied_predicates: RefCell::new(Vec::new()),
603 scope_expr_id,
604 }
605 }
606
reset(&mut self)607 fn reset(&mut self) {
608 self.inherent_candidates.clear();
609 self.extension_candidates.clear();
610 self.impl_dups.clear();
611 self.private_candidate = None;
612 self.static_candidates.borrow_mut().clear();
613 self.unsatisfied_predicates.borrow_mut().clear();
614 }
615
616 ///////////////////////////////////////////////////////////////////////////
617 // CANDIDATE ASSEMBLY
618
push_candidate(&mut self, candidate: Candidate<'tcx>, is_inherent: bool)619 fn push_candidate(&mut self, candidate: Candidate<'tcx>, is_inherent: bool) {
620 let is_accessible = if let Some(name) = self.method_name {
621 let item = candidate.item;
622 let hir_id = self.tcx.hir().local_def_id_to_hir_id(self.body_id);
623 let def_scope =
624 self.tcx.adjust_ident_and_get_scope(name, item.container_id(self.tcx), hir_id).1;
625 item.visibility(self.tcx).is_accessible_from(def_scope, self.tcx)
626 } else {
627 true
628 };
629 if is_accessible {
630 if is_inherent {
631 self.inherent_candidates.push(candidate);
632 } else {
633 self.extension_candidates.push(candidate);
634 }
635 } else if self.private_candidate.is_none() {
636 self.private_candidate =
637 Some((candidate.item.kind.as_def_kind(), candidate.item.def_id));
638 }
639 }
640
assemble_inherent_candidates(&mut self)641 fn assemble_inherent_candidates(&mut self) {
642 for step in self.steps.iter() {
643 self.assemble_probe(&step.self_ty);
644 }
645 }
646
assemble_probe(&mut self, self_ty: &Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>)647 fn assemble_probe(&mut self, self_ty: &Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>) {
648 debug!("assemble_probe: self_ty={:?}", self_ty);
649 let raw_self_ty = self_ty.value.value;
650 match *raw_self_ty.kind() {
651 ty::Dynamic(data, ..) if let Some(p) = data.principal() => {
652 // Subtle: we can't use `instantiate_query_response` here: using it will
653 // commit to all of the type equalities assumed by inference going through
654 // autoderef (see the `method-probe-no-guessing` test).
655 //
656 // However, in this code, it is OK if we end up with an object type that is
657 // "more general" than the object type that we are evaluating. For *every*
658 // object type `MY_OBJECT`, a function call that goes through a trait-ref
659 // of the form `<MY_OBJECT as SuperTraitOf(MY_OBJECT)>::func` is a valid
660 // `ObjectCandidate`, and it should be discoverable "exactly" through one
661 // of the iterations in the autoderef loop, so there is no problem with it
662 // being discoverable in another one of these iterations.
663 //
664 // Using `instantiate_canonical_with_fresh_inference_vars` on our
665 // `Canonical<QueryResponse<Ty<'tcx>>>` and then *throwing away* the
666 // `CanonicalVarValues` will exactly give us such a generalization - it
667 // will still match the original object type, but it won't pollute our
668 // type variables in any form, so just do that!
669 let (QueryResponse { value: generalized_self_ty, .. }, _ignored_var_values) =
670 self.fcx
671 .instantiate_canonical_with_fresh_inference_vars(self.span, self_ty);
672
673 self.assemble_inherent_candidates_from_object(generalized_self_ty);
674 self.assemble_inherent_impl_candidates_for_type(p.def_id());
675 if self.tcx.has_attr(p.def_id(), sym::rustc_has_incoherent_inherent_impls) {
676 self.assemble_inherent_candidates_for_incoherent_ty(raw_self_ty);
677 }
678 }
679 ty::Adt(def, _) => {
680 let def_id = def.did();
681 self.assemble_inherent_impl_candidates_for_type(def_id);
682 if self.tcx.has_attr(def_id, sym::rustc_has_incoherent_inherent_impls) {
683 self.assemble_inherent_candidates_for_incoherent_ty(raw_self_ty);
684 }
685 }
686 ty::Foreign(did) => {
687 self.assemble_inherent_impl_candidates_for_type(did);
688 if self.tcx.has_attr(did, sym::rustc_has_incoherent_inherent_impls) {
689 self.assemble_inherent_candidates_for_incoherent_ty(raw_self_ty);
690 }
691 }
692 ty::Param(p) => {
693 self.assemble_inherent_candidates_from_param(p);
694 }
695 ty::Bool
696 | ty::Char
697 | ty::Int(_)
698 | ty::Uint(_)
699 | ty::Float(_)
700 | ty::Str
701 | ty::Array(..)
702 | ty::Slice(_)
703 | ty::RawPtr(_)
704 | ty::Ref(..)
705 | ty::Never
706 | ty::Tuple(..) => self.assemble_inherent_candidates_for_incoherent_ty(raw_self_ty),
707 _ => {}
708 }
709 }
710
assemble_inherent_candidates_for_incoherent_ty(&mut self, self_ty: Ty<'tcx>)711 fn assemble_inherent_candidates_for_incoherent_ty(&mut self, self_ty: Ty<'tcx>) {
712 let Some(simp) = simplify_type(self.tcx, self_ty, TreatParams::AsCandidateKey) else {
713 bug!("unexpected incoherent type: {:?}", self_ty)
714 };
715 for &impl_def_id in self.tcx.incoherent_impls(simp) {
716 self.assemble_inherent_impl_probe(impl_def_id);
717 }
718 }
719
assemble_inherent_impl_candidates_for_type(&mut self, def_id: DefId)720 fn assemble_inherent_impl_candidates_for_type(&mut self, def_id: DefId) {
721 let impl_def_ids = self.tcx.at(self.span).inherent_impls(def_id);
722 for &impl_def_id in impl_def_ids.iter() {
723 self.assemble_inherent_impl_probe(impl_def_id);
724 }
725 }
726
assemble_inherent_impl_probe(&mut self, impl_def_id: DefId)727 fn assemble_inherent_impl_probe(&mut self, impl_def_id: DefId) {
728 if !self.impl_dups.insert(impl_def_id) {
729 return; // already visited
730 }
731
732 debug!("assemble_inherent_impl_probe {:?}", impl_def_id);
733
734 for item in self.impl_or_trait_item(impl_def_id) {
735 if !self.has_applicable_self(&item) {
736 // No receiver declared. Not a candidate.
737 self.record_static_candidate(CandidateSource::Impl(impl_def_id));
738 continue;
739 }
740
741 let (impl_ty, impl_substs) = self.impl_ty_and_substs(impl_def_id);
742 let impl_ty = impl_ty.subst(self.tcx, impl_substs);
743
744 debug!("impl_ty: {:?}", impl_ty);
745
746 // Determine the receiver type that the method itself expects.
747 let (xform_self_ty, xform_ret_ty) = self.xform_self_ty(item, impl_ty, impl_substs);
748 debug!("xform_self_ty: {:?}, xform_ret_ty: {:?}", xform_self_ty, xform_ret_ty);
749
750 // We can't use normalize_associated_types_in as it will pollute the
751 // fcx's fulfillment context after this probe is over.
752 // Note: we only normalize `xform_self_ty` here since the normalization
753 // of the return type can lead to inference results that prohibit
754 // valid candidates from being found, see issue #85671
755 // FIXME Postponing the normalization of the return type likely only hides a deeper bug,
756 // which might be caused by the `param_env` itself. The clauses of the `param_env`
757 // maybe shouldn't include `Param`s, but rather fresh variables or be canonicalized,
758 // see issue #89650
759 let cause = traits::ObligationCause::misc(self.span, self.body_id);
760 let InferOk { value: xform_self_ty, obligations } =
761 self.fcx.at(&cause, self.param_env).normalize(xform_self_ty);
762
763 debug!(
764 "assemble_inherent_impl_probe after normalization: xform_self_ty = {:?}/{:?}",
765 xform_self_ty, xform_ret_ty
766 );
767
768 self.push_candidate(
769 Candidate {
770 xform_self_ty,
771 xform_ret_ty,
772 item,
773 kind: InherentImplCandidate(impl_substs, obligations),
774 import_ids: smallvec![],
775 },
776 true,
777 );
778 }
779 }
780
assemble_inherent_candidates_from_object(&mut self, self_ty: Ty<'tcx>)781 fn assemble_inherent_candidates_from_object(&mut self, self_ty: Ty<'tcx>) {
782 debug!("assemble_inherent_candidates_from_object(self_ty={:?})", self_ty);
783
784 let principal = match self_ty.kind() {
785 ty::Dynamic(ref data, ..) => Some(data),
786 _ => None,
787 }
788 .and_then(|data| data.principal())
789 .unwrap_or_else(|| {
790 span_bug!(
791 self.span,
792 "non-object {:?} in assemble_inherent_candidates_from_object",
793 self_ty
794 )
795 });
796
797 // It is illegal to invoke a method on a trait instance that refers to
798 // the `Self` type. An [`ObjectSafetyViolation::SupertraitSelf`] error
799 // will be reported by `object_safety.rs` if the method refers to the
800 // `Self` type anywhere other than the receiver. Here, we use a
801 // substitution that replaces `Self` with the object type itself. Hence,
802 // a `&self` method will wind up with an argument type like `&dyn Trait`.
803 let trait_ref = principal.with_self_ty(self.tcx, self_ty);
804 self.elaborate_bounds(iter::once(trait_ref), |this, new_trait_ref, item| {
805 if new_trait_ref.has_non_region_late_bound() {
806 this.tcx.sess.delay_span_bug(
807 this.span,
808 "tried to select method from HRTB with non-lifetime bound vars",
809 );
810 return;
811 }
812
813 let new_trait_ref = this.erase_late_bound_regions(new_trait_ref);
814
815 let (xform_self_ty, xform_ret_ty) =
816 this.xform_self_ty(item, new_trait_ref.self_ty(), new_trait_ref.substs);
817 this.push_candidate(
818 Candidate {
819 xform_self_ty,
820 xform_ret_ty,
821 item,
822 kind: ObjectCandidate,
823 import_ids: smallvec![],
824 },
825 true,
826 );
827 });
828 }
829
assemble_inherent_candidates_from_param(&mut self, param_ty: ty::ParamTy)830 fn assemble_inherent_candidates_from_param(&mut self, param_ty: ty::ParamTy) {
831 // FIXME: do we want to commit to this behavior for param bounds?
832 debug!("assemble_inherent_candidates_from_param(param_ty={:?})", param_ty);
833
834 let bounds = self.param_env.caller_bounds().iter().filter_map(|predicate| {
835 let bound_predicate = predicate.kind();
836 match bound_predicate.skip_binder() {
837 ty::ClauseKind::Trait(trait_predicate) => {
838 match *trait_predicate.trait_ref.self_ty().kind() {
839 ty::Param(p) if p == param_ty => {
840 Some(bound_predicate.rebind(trait_predicate.trait_ref))
841 }
842 _ => None,
843 }
844 }
845 ty::ClauseKind::RegionOutlives(_)
846 | ty::ClauseKind::TypeOutlives(_)
847 | ty::ClauseKind::Projection(_)
848 | ty::ClauseKind::ConstArgHasType(_, _)
849 | ty::ClauseKind::WellFormed(_)
850 | ty::ClauseKind::ConstEvaluatable(_) => None,
851 }
852 });
853
854 self.elaborate_bounds(bounds, |this, poly_trait_ref, item| {
855 let trait_ref = this.instantiate_binder_with_fresh_vars(
856 this.span,
857 infer::LateBoundRegionConversionTime::FnCall,
858 poly_trait_ref,
859 );
860
861 let (xform_self_ty, xform_ret_ty) =
862 this.xform_self_ty(item, trait_ref.self_ty(), trait_ref.substs);
863
864 this.push_candidate(
865 Candidate {
866 xform_self_ty,
867 xform_ret_ty,
868 item,
869 kind: WhereClauseCandidate(poly_trait_ref),
870 import_ids: smallvec![],
871 },
872 true,
873 );
874 });
875 }
876
877 // Do a search through a list of bounds, using a callback to actually
878 // create the candidates.
elaborate_bounds<F>( &mut self, bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>, mut mk_cand: F, ) where F: for<'b> FnMut(&mut ProbeContext<'b, 'tcx>, ty::PolyTraitRef<'tcx>, ty::AssocItem),879 fn elaborate_bounds<F>(
880 &mut self,
881 bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>,
882 mut mk_cand: F,
883 ) where
884 F: for<'b> FnMut(&mut ProbeContext<'b, 'tcx>, ty::PolyTraitRef<'tcx>, ty::AssocItem),
885 {
886 let tcx = self.tcx;
887 for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
888 debug!("elaborate_bounds(bound_trait_ref={:?})", bound_trait_ref);
889 for item in self.impl_or_trait_item(bound_trait_ref.def_id()) {
890 if !self.has_applicable_self(&item) {
891 self.record_static_candidate(CandidateSource::Trait(bound_trait_ref.def_id()));
892 } else {
893 mk_cand(self, bound_trait_ref, item);
894 }
895 }
896 }
897 }
898
assemble_extension_candidates_for_traits_in_scope(&mut self)899 fn assemble_extension_candidates_for_traits_in_scope(&mut self) {
900 let mut duplicates = FxHashSet::default();
901 let opt_applicable_traits = self.tcx.in_scope_traits(self.scope_expr_id);
902 if let Some(applicable_traits) = opt_applicable_traits {
903 for trait_candidate in applicable_traits.iter() {
904 let trait_did = trait_candidate.def_id;
905 if duplicates.insert(trait_did) {
906 self.assemble_extension_candidates_for_trait(
907 &trait_candidate.import_ids,
908 trait_did,
909 );
910 }
911 }
912 }
913 }
914
assemble_extension_candidates_for_all_traits(&mut self)915 fn assemble_extension_candidates_for_all_traits(&mut self) {
916 let mut duplicates = FxHashSet::default();
917 for trait_info in suggest::all_traits(self.tcx) {
918 if duplicates.insert(trait_info.def_id) {
919 self.assemble_extension_candidates_for_trait(&smallvec![], trait_info.def_id);
920 }
921 }
922 }
923
matches_return_type( &self, method: ty::AssocItem, self_ty: Option<Ty<'tcx>>, expected: Ty<'tcx>, ) -> bool924 fn matches_return_type(
925 &self,
926 method: ty::AssocItem,
927 self_ty: Option<Ty<'tcx>>,
928 expected: Ty<'tcx>,
929 ) -> bool {
930 match method.kind {
931 ty::AssocKind::Fn => self.probe(|_| {
932 let substs = self.fresh_substs_for_item(self.span, method.def_id);
933 let fty = self.tcx.fn_sig(method.def_id).subst(self.tcx, substs);
934 let fty = self.instantiate_binder_with_fresh_vars(self.span, infer::FnCall, fty);
935
936 if let Some(self_ty) = self_ty {
937 if self
938 .at(&ObligationCause::dummy(), self.param_env)
939 .sup(DefineOpaqueTypes::No, fty.inputs()[0], self_ty)
940 .is_err()
941 {
942 return false;
943 }
944 }
945 self.can_sub(self.param_env, fty.output(), expected)
946 }),
947 _ => false,
948 }
949 }
950
assemble_extension_candidates_for_trait( &mut self, import_ids: &SmallVec<[LocalDefId; 1]>, trait_def_id: DefId, )951 fn assemble_extension_candidates_for_trait(
952 &mut self,
953 import_ids: &SmallVec<[LocalDefId; 1]>,
954 trait_def_id: DefId,
955 ) {
956 debug!("assemble_extension_candidates_for_trait(trait_def_id={:?})", trait_def_id);
957 let trait_substs = self.fresh_substs_for_item(self.span, trait_def_id);
958 let trait_ref = ty::TraitRef::new(self.tcx, trait_def_id, trait_substs);
959
960 if self.tcx.is_trait_alias(trait_def_id) {
961 // For trait aliases, recursively assume all explicitly named traits are relevant
962 for expansion in traits::expand_trait_aliases(
963 self.tcx,
964 iter::once((ty::Binder::dummy(trait_ref), self.span)),
965 ) {
966 let bound_trait_ref = expansion.trait_ref();
967 for item in self.impl_or_trait_item(bound_trait_ref.def_id()) {
968 if !self.has_applicable_self(&item) {
969 self.record_static_candidate(CandidateSource::Trait(
970 bound_trait_ref.def_id(),
971 ));
972 } else {
973 let new_trait_ref = self.instantiate_binder_with_fresh_vars(
974 self.span,
975 infer::LateBoundRegionConversionTime::FnCall,
976 bound_trait_ref,
977 );
978
979 let (xform_self_ty, xform_ret_ty) =
980 self.xform_self_ty(item, new_trait_ref.self_ty(), new_trait_ref.substs);
981 self.push_candidate(
982 Candidate {
983 xform_self_ty,
984 xform_ret_ty,
985 item,
986 import_ids: import_ids.clone(),
987 kind: TraitCandidate(new_trait_ref),
988 },
989 false,
990 );
991 }
992 }
993 }
994 } else {
995 debug_assert!(self.tcx.is_trait(trait_def_id));
996 if self.tcx.trait_is_auto(trait_def_id) {
997 return;
998 }
999 for item in self.impl_or_trait_item(trait_def_id) {
1000 // Check whether `trait_def_id` defines a method with suitable name.
1001 if !self.has_applicable_self(&item) {
1002 debug!("method has inapplicable self");
1003 self.record_static_candidate(CandidateSource::Trait(trait_def_id));
1004 continue;
1005 }
1006
1007 let (xform_self_ty, xform_ret_ty) =
1008 self.xform_self_ty(item, trait_ref.self_ty(), trait_substs);
1009 self.push_candidate(
1010 Candidate {
1011 xform_self_ty,
1012 xform_ret_ty,
1013 item,
1014 import_ids: import_ids.clone(),
1015 kind: TraitCandidate(trait_ref),
1016 },
1017 false,
1018 );
1019 }
1020 }
1021 }
1022
candidate_method_names( &self, candidate_filter: impl Fn(&ty::AssocItem) -> bool, ) -> Vec<Ident>1023 fn candidate_method_names(
1024 &self,
1025 candidate_filter: impl Fn(&ty::AssocItem) -> bool,
1026 ) -> Vec<Ident> {
1027 let mut set = FxHashSet::default();
1028 let mut names: Vec<_> = self
1029 .inherent_candidates
1030 .iter()
1031 .chain(&self.extension_candidates)
1032 .filter(|candidate| candidate_filter(&candidate.item))
1033 .filter(|candidate| {
1034 if let Some(return_ty) = self.return_type {
1035 self.matches_return_type(candidate.item, None, return_ty)
1036 } else {
1037 true
1038 }
1039 })
1040 // ensure that we don't suggest unstable methods
1041 .filter(|candidate| {
1042 // note that `DUMMY_SP` is ok here because it is only used for
1043 // suggestions and macro stuff which isn't applicable here.
1044 !matches!(
1045 self.tcx.eval_stability(candidate.item.def_id, None, DUMMY_SP, None),
1046 stability::EvalResult::Deny { .. }
1047 )
1048 })
1049 .map(|candidate| candidate.item.ident(self.tcx))
1050 .filter(|&name| set.insert(name))
1051 .collect();
1052
1053 // Sort them by the name so we have a stable result.
1054 names.sort_by(|a, b| a.as_str().cmp(b.as_str()));
1055 names
1056 }
1057
1058 ///////////////////////////////////////////////////////////////////////////
1059 // THE ACTUAL SEARCH
1060
pick(mut self) -> PickResult<'tcx>1061 fn pick(mut self) -> PickResult<'tcx> {
1062 assert!(self.method_name.is_some());
1063
1064 if let Some(r) = self.pick_core() {
1065 return r;
1066 }
1067
1068 debug!("pick: actual search failed, assemble diagnostics");
1069
1070 let static_candidates = std::mem::take(self.static_candidates.get_mut());
1071 let private_candidate = self.private_candidate.take();
1072 let unsatisfied_predicates = std::mem::take(self.unsatisfied_predicates.get_mut());
1073
1074 // things failed, so lets look at all traits, for diagnostic purposes now:
1075 self.reset();
1076
1077 let span = self.span;
1078 let tcx = self.tcx;
1079
1080 self.assemble_extension_candidates_for_all_traits();
1081
1082 let out_of_scope_traits = match self.pick_core() {
1083 Some(Ok(p)) => vec![p.item.container_id(self.tcx)],
1084 Some(Err(MethodError::Ambiguity(v))) => v
1085 .into_iter()
1086 .map(|source| match source {
1087 CandidateSource::Trait(id) => id,
1088 CandidateSource::Impl(impl_id) => match tcx.trait_id_of_impl(impl_id) {
1089 Some(id) => id,
1090 None => span_bug!(span, "found inherent method when looking at traits"),
1091 },
1092 })
1093 .collect(),
1094 Some(Err(MethodError::NoMatch(NoMatchData {
1095 out_of_scope_traits: others, ..
1096 }))) => {
1097 assert!(others.is_empty());
1098 vec![]
1099 }
1100 _ => vec![],
1101 };
1102
1103 if let Some((kind, def_id)) = private_candidate {
1104 return Err(MethodError::PrivateMatch(kind, def_id, out_of_scope_traits));
1105 }
1106 let similar_candidate = self.probe_for_similar_candidate()?;
1107
1108 Err(MethodError::NoMatch(NoMatchData {
1109 static_candidates,
1110 unsatisfied_predicates,
1111 out_of_scope_traits,
1112 similar_candidate,
1113 mode: self.mode,
1114 }))
1115 }
1116
pick_core(&self) -> Option<PickResult<'tcx>>1117 fn pick_core(&self) -> Option<PickResult<'tcx>> {
1118 // Pick stable methods only first, and consider unstable candidates if not found.
1119 self.pick_all_method(Some(&mut vec![])).or_else(|| self.pick_all_method(None))
1120 }
1121
pick_all_method( &self, mut unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>, ) -> Option<PickResult<'tcx>>1122 fn pick_all_method(
1123 &self,
1124 mut unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>,
1125 ) -> Option<PickResult<'tcx>> {
1126 self.steps
1127 .iter()
1128 .filter(|step| {
1129 debug!("pick_all_method: step={:?}", step);
1130 // skip types that are from a type error or that would require dereferencing
1131 // a raw pointer
1132 !step.self_ty.references_error() && !step.from_unsafe_deref
1133 })
1134 .find_map(|step| {
1135 let InferOk { value: self_ty, obligations: _ } = self
1136 .fcx
1137 .probe_instantiate_query_response(
1138 self.span,
1139 &self.orig_steps_var_values,
1140 &step.self_ty,
1141 )
1142 .unwrap_or_else(|_| {
1143 span_bug!(self.span, "{:?} was applicable but now isn't?", step.self_ty)
1144 });
1145 self.pick_by_value_method(step, self_ty, unstable_candidates.as_deref_mut())
1146 .or_else(|| {
1147 self.pick_autorefd_method(
1148 step,
1149 self_ty,
1150 hir::Mutability::Not,
1151 unstable_candidates.as_deref_mut(),
1152 )
1153 .or_else(|| {
1154 self.pick_autorefd_method(
1155 step,
1156 self_ty,
1157 hir::Mutability::Mut,
1158 unstable_candidates.as_deref_mut(),
1159 )
1160 })
1161 .or_else(|| {
1162 self.pick_const_ptr_method(
1163 step,
1164 self_ty,
1165 unstable_candidates.as_deref_mut(),
1166 )
1167 })
1168 })
1169 })
1170 }
1171
1172 /// For each type `T` in the step list, this attempts to find a method where
1173 /// the (transformed) self type is exactly `T`. We do however do one
1174 /// transformation on the adjustment: if we are passing a region pointer in,
1175 /// we will potentially *reborrow* it to a shorter lifetime. This allows us
1176 /// to transparently pass `&mut` pointers, in particular, without consuming
1177 /// them for their entire lifetime.
pick_by_value_method( &self, step: &CandidateStep<'tcx>, self_ty: Ty<'tcx>, unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>, ) -> Option<PickResult<'tcx>>1178 fn pick_by_value_method(
1179 &self,
1180 step: &CandidateStep<'tcx>,
1181 self_ty: Ty<'tcx>,
1182 unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>,
1183 ) -> Option<PickResult<'tcx>> {
1184 if step.unsize {
1185 return None;
1186 }
1187
1188 self.pick_method(self_ty, unstable_candidates).map(|r| {
1189 r.map(|mut pick| {
1190 pick.autoderefs = step.autoderefs;
1191
1192 // Insert a `&*` or `&mut *` if this is a reference type:
1193 if let ty::Ref(_, _, mutbl) = *step.self_ty.value.value.kind() {
1194 pick.autoderefs += 1;
1195 pick.autoref_or_ptr_adjustment = Some(AutorefOrPtrAdjustment::Autoref {
1196 mutbl,
1197 unsize: pick.autoref_or_ptr_adjustment.is_some_and(|a| a.get_unsize()),
1198 })
1199 }
1200
1201 pick
1202 })
1203 })
1204 }
1205
pick_autorefd_method( &self, step: &CandidateStep<'tcx>, self_ty: Ty<'tcx>, mutbl: hir::Mutability, unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>, ) -> Option<PickResult<'tcx>>1206 fn pick_autorefd_method(
1207 &self,
1208 step: &CandidateStep<'tcx>,
1209 self_ty: Ty<'tcx>,
1210 mutbl: hir::Mutability,
1211 unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>,
1212 ) -> Option<PickResult<'tcx>> {
1213 let tcx = self.tcx;
1214
1215 // In general, during probing we erase regions.
1216 let region = tcx.lifetimes.re_erased;
1217
1218 let autoref_ty = Ty::new_ref(tcx, region, ty::TypeAndMut { ty: self_ty, mutbl });
1219 self.pick_method(autoref_ty, unstable_candidates).map(|r| {
1220 r.map(|mut pick| {
1221 pick.autoderefs = step.autoderefs;
1222 pick.autoref_or_ptr_adjustment =
1223 Some(AutorefOrPtrAdjustment::Autoref { mutbl, unsize: step.unsize });
1224 pick
1225 })
1226 })
1227 }
1228
1229 /// If `self_ty` is `*mut T` then this picks `*const T` methods. The reason why we have a
1230 /// special case for this is because going from `*mut T` to `*const T` with autoderefs and
1231 /// autorefs would require dereferencing the pointer, which is not safe.
pick_const_ptr_method( &self, step: &CandidateStep<'tcx>, self_ty: Ty<'tcx>, unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>, ) -> Option<PickResult<'tcx>>1232 fn pick_const_ptr_method(
1233 &self,
1234 step: &CandidateStep<'tcx>,
1235 self_ty: Ty<'tcx>,
1236 unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>,
1237 ) -> Option<PickResult<'tcx>> {
1238 // Don't convert an unsized reference to ptr
1239 if step.unsize {
1240 return None;
1241 }
1242
1243 let &ty::RawPtr(ty::TypeAndMut { ty, mutbl: hir::Mutability::Mut }) = self_ty.kind() else {
1244 return None;
1245 };
1246
1247 let const_self_ty = ty::TypeAndMut { ty, mutbl: hir::Mutability::Not };
1248 let const_ptr_ty = Ty::new_ptr(self.tcx, const_self_ty);
1249 self.pick_method(const_ptr_ty, unstable_candidates).map(|r| {
1250 r.map(|mut pick| {
1251 pick.autoderefs = step.autoderefs;
1252 pick.autoref_or_ptr_adjustment = Some(AutorefOrPtrAdjustment::ToConstPtr);
1253 pick
1254 })
1255 })
1256 }
1257
pick_method( &self, self_ty: Ty<'tcx>, mut unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>, ) -> Option<PickResult<'tcx>>1258 fn pick_method(
1259 &self,
1260 self_ty: Ty<'tcx>,
1261 mut unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>,
1262 ) -> Option<PickResult<'tcx>> {
1263 debug!("pick_method(self_ty={})", self.ty_to_string(self_ty));
1264
1265 let mut possibly_unsatisfied_predicates = Vec::new();
1266
1267 for (kind, candidates) in
1268 &[("inherent", &self.inherent_candidates), ("extension", &self.extension_candidates)]
1269 {
1270 debug!("searching {} candidates", kind);
1271 let res = self.consider_candidates(
1272 self_ty,
1273 candidates,
1274 &mut possibly_unsatisfied_predicates,
1275 unstable_candidates.as_deref_mut(),
1276 );
1277 if let Some(pick) = res {
1278 return Some(pick);
1279 }
1280 }
1281
1282 // `pick_method` may be called twice for the same self_ty if no stable methods
1283 // match. Only extend once.
1284 if unstable_candidates.is_some() {
1285 self.unsatisfied_predicates.borrow_mut().extend(possibly_unsatisfied_predicates);
1286 }
1287 None
1288 }
1289
consider_candidates( &self, self_ty: Ty<'tcx>, candidates: &[Candidate<'tcx>], possibly_unsatisfied_predicates: &mut Vec<( ty::Predicate<'tcx>, Option<ty::Predicate<'tcx>>, Option<ObligationCause<'tcx>>, )>, mut unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>, ) -> Option<PickResult<'tcx>>1290 fn consider_candidates(
1291 &self,
1292 self_ty: Ty<'tcx>,
1293 candidates: &[Candidate<'tcx>],
1294 possibly_unsatisfied_predicates: &mut Vec<(
1295 ty::Predicate<'tcx>,
1296 Option<ty::Predicate<'tcx>>,
1297 Option<ObligationCause<'tcx>>,
1298 )>,
1299 mut unstable_candidates: Option<&mut Vec<(Candidate<'tcx>, Symbol)>>,
1300 ) -> Option<PickResult<'tcx>> {
1301 let mut applicable_candidates: Vec<_> = candidates
1302 .iter()
1303 .map(|probe| {
1304 (probe, self.consider_probe(self_ty, probe, possibly_unsatisfied_predicates))
1305 })
1306 .filter(|&(_, status)| status != ProbeResult::NoMatch)
1307 .collect();
1308
1309 debug!("applicable_candidates: {:?}", applicable_candidates);
1310
1311 if applicable_candidates.len() > 1 {
1312 if let Some(pick) =
1313 self.collapse_candidates_to_trait_pick(self_ty, &applicable_candidates)
1314 {
1315 return Some(Ok(pick));
1316 }
1317 }
1318
1319 if let Some(uc) = &mut unstable_candidates {
1320 applicable_candidates.retain(|&(candidate, _)| {
1321 if let stability::EvalResult::Deny { feature, .. } =
1322 self.tcx.eval_stability(candidate.item.def_id, None, self.span, None)
1323 {
1324 uc.push((candidate.clone(), feature));
1325 return false;
1326 }
1327 true
1328 });
1329 }
1330
1331 if applicable_candidates.len() > 1 {
1332 let sources = candidates.iter().map(|p| self.candidate_source(p, self_ty)).collect();
1333 return Some(Err(MethodError::Ambiguity(sources)));
1334 }
1335
1336 applicable_candidates.pop().map(|(probe, status)| match status {
1337 ProbeResult::Match => {
1338 Ok(probe
1339 .to_unadjusted_pick(self_ty, unstable_candidates.cloned().unwrap_or_default()))
1340 }
1341 ProbeResult::NoMatch | ProbeResult::BadReturnType => Err(MethodError::BadReturnType),
1342 })
1343 }
1344 }
1345
1346 impl<'tcx> Pick<'tcx> {
1347 /// In case there were unstable name collisions, emit them as a lint.
1348 /// Checks whether two picks do not refer to the same trait item for the same `Self` type.
1349 /// Only useful for comparisons of picks in order to improve diagnostics.
1350 /// Do not use for type checking.
differs_from(&self, other: &Self) -> bool1351 pub fn differs_from(&self, other: &Self) -> bool {
1352 let Self {
1353 item:
1354 AssocItem {
1355 def_id,
1356 name: _,
1357 kind: _,
1358 container: _,
1359 trait_item_def_id: _,
1360 fn_has_self_parameter: _,
1361 opt_rpitit_info: _,
1362 },
1363 kind: _,
1364 import_ids: _,
1365 autoderefs: _,
1366 autoref_or_ptr_adjustment: _,
1367 self_ty,
1368 unstable_candidates: _,
1369 } = *self;
1370 self_ty != other.self_ty || def_id != other.item.def_id
1371 }
1372
1373 /// In case there were unstable name collisions, emit them as a lint.
maybe_emit_unstable_name_collision_hint( &self, tcx: TyCtxt<'tcx>, span: Span, scope_expr_id: hir::HirId, )1374 pub fn maybe_emit_unstable_name_collision_hint(
1375 &self,
1376 tcx: TyCtxt<'tcx>,
1377 span: Span,
1378 scope_expr_id: hir::HirId,
1379 ) {
1380 if self.unstable_candidates.is_empty() {
1381 return;
1382 }
1383 let def_kind = self.item.kind.as_def_kind();
1384 tcx.struct_span_lint_hir(
1385 lint::builtin::UNSTABLE_NAME_COLLISIONS,
1386 scope_expr_id,
1387 span,
1388 format!(
1389 "{} {} with this name may be added to the standard library in the future",
1390 tcx.def_kind_descr_article(def_kind, self.item.def_id),
1391 tcx.def_kind_descr(def_kind, self.item.def_id),
1392 ),
1393 |lint| {
1394 match (self.item.kind, self.item.container) {
1395 (ty::AssocKind::Fn, _) => {
1396 // FIXME: This should be a `span_suggestion` instead of `help`
1397 // However `self.span` only
1398 // highlights the method name, so we can't use it. Also consider reusing
1399 // the code from `report_method_error()`.
1400 lint.help(format!(
1401 "call with fully qualified syntax `{}(...)` to keep using the current \
1402 method",
1403 tcx.def_path_str(self.item.def_id),
1404 ));
1405 }
1406 (ty::AssocKind::Const, ty::AssocItemContainer::TraitContainer) => {
1407 let def_id = self.item.container_id(tcx);
1408 lint.span_suggestion(
1409 span,
1410 "use the fully qualified path to the associated const",
1411 format!(
1412 "<{} as {}>::{}",
1413 self.self_ty,
1414 tcx.def_path_str(def_id),
1415 self.item.name
1416 ),
1417 Applicability::MachineApplicable,
1418 );
1419 }
1420 _ => {}
1421 }
1422 if tcx.sess.is_nightly_build() {
1423 for (candidate, feature) in &self.unstable_candidates {
1424 lint.help(format!(
1425 "add `#![feature({})]` to the crate attributes to enable `{}`",
1426 feature,
1427 tcx.def_path_str(candidate.item.def_id),
1428 ));
1429 }
1430 }
1431
1432 lint
1433 },
1434 );
1435 }
1436 }
1437
1438 impl<'a, 'tcx> ProbeContext<'a, 'tcx> {
select_trait_candidate( &self, trait_ref: ty::TraitRef<'tcx>, ) -> traits::SelectionResult<'tcx, traits::Selection<'tcx>>1439 fn select_trait_candidate(
1440 &self,
1441 trait_ref: ty::TraitRef<'tcx>,
1442 ) -> traits::SelectionResult<'tcx, traits::Selection<'tcx>> {
1443 let cause = traits::ObligationCause::misc(self.span, self.body_id);
1444 let obligation = traits::Obligation::new(self.tcx, cause, self.param_env, trait_ref);
1445 traits::SelectionContext::new(self).select(&obligation)
1446 }
1447
candidate_source(&self, candidate: &Candidate<'tcx>, self_ty: Ty<'tcx>) -> CandidateSource1448 fn candidate_source(&self, candidate: &Candidate<'tcx>, self_ty: Ty<'tcx>) -> CandidateSource {
1449 match candidate.kind {
1450 InherentImplCandidate(..) => {
1451 CandidateSource::Impl(candidate.item.container_id(self.tcx))
1452 }
1453 ObjectCandidate | WhereClauseCandidate(_) => {
1454 CandidateSource::Trait(candidate.item.container_id(self.tcx))
1455 }
1456 TraitCandidate(trait_ref) => self.probe(|_| {
1457 let _ = self.at(&ObligationCause::dummy(), self.param_env).sup(
1458 DefineOpaqueTypes::No,
1459 candidate.xform_self_ty,
1460 self_ty,
1461 );
1462 match self.select_trait_candidate(trait_ref) {
1463 Ok(Some(traits::ImplSource::UserDefined(ref impl_data))) => {
1464 // If only a single impl matches, make the error message point
1465 // to that impl.
1466 CandidateSource::Impl(impl_data.impl_def_id)
1467 }
1468 _ => CandidateSource::Trait(candidate.item.container_id(self.tcx)),
1469 }
1470 }),
1471 }
1472 }
1473
consider_probe( &self, self_ty: Ty<'tcx>, probe: &Candidate<'tcx>, possibly_unsatisfied_predicates: &mut Vec<( ty::Predicate<'tcx>, Option<ty::Predicate<'tcx>>, Option<ObligationCause<'tcx>>, )>, ) -> ProbeResult1474 fn consider_probe(
1475 &self,
1476 self_ty: Ty<'tcx>,
1477 probe: &Candidate<'tcx>,
1478 possibly_unsatisfied_predicates: &mut Vec<(
1479 ty::Predicate<'tcx>,
1480 Option<ty::Predicate<'tcx>>,
1481 Option<ObligationCause<'tcx>>,
1482 )>,
1483 ) -> ProbeResult {
1484 debug!("consider_probe: self_ty={:?} probe={:?}", self_ty, probe);
1485
1486 self.probe(|_| {
1487 // First check that the self type can be related.
1488 let sub_obligations = match self.at(&ObligationCause::dummy(), self.param_env).sup(
1489 DefineOpaqueTypes::No,
1490 probe.xform_self_ty,
1491 self_ty,
1492 ) {
1493 Ok(InferOk { obligations, value: () }) => obligations,
1494 Err(err) => {
1495 debug!("--> cannot relate self-types {:?}", err);
1496 return ProbeResult::NoMatch;
1497 }
1498 };
1499
1500 let mut result = ProbeResult::Match;
1501 let mut xform_ret_ty = probe.xform_ret_ty;
1502 debug!(?xform_ret_ty);
1503
1504 let cause = traits::ObligationCause::misc(self.span, self.body_id);
1505
1506 let mut parent_pred = None;
1507
1508 // If so, impls may carry other conditions (e.g., where
1509 // clauses) that must be considered. Make sure that those
1510 // match as well (or at least may match, sometimes we
1511 // don't have enough information to fully evaluate).
1512 match probe.kind {
1513 InherentImplCandidate(ref substs, ref ref_obligations) => {
1514 // `xform_ret_ty` hasn't been normalized yet, only `xform_self_ty`,
1515 // see the reasons mentioned in the comments in `assemble_inherent_impl_probe`
1516 // for why this is necessary
1517 let InferOk {
1518 value: normalized_xform_ret_ty,
1519 obligations: normalization_obligations,
1520 } = self.fcx.at(&cause, self.param_env).normalize(xform_ret_ty);
1521 xform_ret_ty = normalized_xform_ret_ty;
1522 debug!("xform_ret_ty after normalization: {:?}", xform_ret_ty);
1523
1524 // Check whether the impl imposes obligations we have to worry about.
1525 let impl_def_id = probe.item.container_id(self.tcx);
1526 let impl_bounds = self.tcx.predicates_of(impl_def_id);
1527 let impl_bounds = impl_bounds.instantiate(self.tcx, substs);
1528
1529 let InferOk { value: impl_bounds, obligations: norm_obligations } =
1530 self.fcx.at(&cause, self.param_env).normalize(impl_bounds);
1531
1532 // Convert the bounds into obligations.
1533 let impl_obligations = traits::predicates_for_generics(
1534 |idx, span| {
1535 let code = if span.is_dummy() {
1536 traits::ExprItemObligation(impl_def_id, self.scope_expr_id, idx)
1537 } else {
1538 traits::ExprBindingObligation(
1539 impl_def_id,
1540 span,
1541 self.scope_expr_id,
1542 idx,
1543 )
1544 };
1545 ObligationCause::new(self.span, self.body_id, code)
1546 },
1547 self.param_env,
1548 impl_bounds,
1549 );
1550
1551 let candidate_obligations = impl_obligations
1552 .chain(norm_obligations.into_iter())
1553 .chain(ref_obligations.iter().cloned())
1554 .chain(normalization_obligations.into_iter());
1555
1556 // Evaluate those obligations to see if they might possibly hold.
1557 for o in candidate_obligations {
1558 let o = self.resolve_vars_if_possible(o);
1559 if !self.predicate_may_hold(&o) {
1560 result = ProbeResult::NoMatch;
1561 let parent_o = o.clone();
1562 let implied_obligations = traits::elaborate(self.tcx, vec![o]);
1563 for o in implied_obligations {
1564 let parent = if o == parent_o {
1565 None
1566 } else {
1567 if o.predicate.to_opt_poly_trait_pred().map(|p| p.def_id())
1568 == self.tcx.lang_items().sized_trait()
1569 {
1570 // We don't care to talk about implicit `Sized` bounds.
1571 continue;
1572 }
1573 Some(parent_o.predicate)
1574 };
1575 if !self.predicate_may_hold(&o) {
1576 possibly_unsatisfied_predicates.push((
1577 o.predicate,
1578 parent,
1579 Some(o.cause),
1580 ));
1581 }
1582 }
1583 }
1584 }
1585 }
1586
1587 ObjectCandidate | WhereClauseCandidate(..) => {
1588 // These have no additional conditions to check.
1589 }
1590
1591 TraitCandidate(trait_ref) => {
1592 if let Some(method_name) = self.method_name {
1593 // Some trait methods are excluded for arrays before 2021.
1594 // (`array.into_iter()` wants a slice iterator for compatibility.)
1595 if self_ty.is_array() && !method_name.span.rust_2021() {
1596 let trait_def = self.tcx.trait_def(trait_ref.def_id);
1597 if trait_def.skip_array_during_method_dispatch {
1598 return ProbeResult::NoMatch;
1599 }
1600 }
1601 }
1602 let predicate =
1603 ty::Binder::dummy(trait_ref).without_const().to_predicate(self.tcx);
1604 parent_pred = Some(predicate);
1605 let obligation =
1606 traits::Obligation::new(self.tcx, cause.clone(), self.param_env, predicate);
1607 if !self.predicate_may_hold(&obligation) {
1608 result = ProbeResult::NoMatch;
1609 if self.probe(|_| {
1610 match self.select_trait_candidate(trait_ref) {
1611 Err(_) => return true,
1612 Ok(Some(impl_source))
1613 if !impl_source.borrow_nested_obligations().is_empty() =>
1614 {
1615 for obligation in impl_source.borrow_nested_obligations() {
1616 // Determine exactly which obligation wasn't met, so
1617 // that we can give more context in the error.
1618 if !self.predicate_may_hold(obligation) {
1619 let nested_predicate =
1620 self.resolve_vars_if_possible(obligation.predicate);
1621 let predicate =
1622 self.resolve_vars_if_possible(predicate);
1623 let p = if predicate == nested_predicate {
1624 // Avoid "`MyStruct: Foo` which is required by
1625 // `MyStruct: Foo`" in E0599.
1626 None
1627 } else {
1628 Some(predicate)
1629 };
1630 possibly_unsatisfied_predicates.push((
1631 nested_predicate,
1632 p,
1633 Some(obligation.cause.clone()),
1634 ));
1635 }
1636 }
1637 }
1638 _ => {
1639 // Some nested subobligation of this predicate
1640 // failed.
1641 let predicate = self.resolve_vars_if_possible(predicate);
1642 possibly_unsatisfied_predicates.push((predicate, None, None));
1643 }
1644 }
1645 false
1646 }) {
1647 // This candidate's primary obligation doesn't even
1648 // select - don't bother registering anything in
1649 // `potentially_unsatisfied_predicates`.
1650 return ProbeResult::NoMatch;
1651 }
1652 }
1653 }
1654 }
1655
1656 // Evaluate those obligations to see if they might possibly hold.
1657 for o in sub_obligations {
1658 let o = self.resolve_vars_if_possible(o);
1659 if !self.predicate_may_hold(&o) {
1660 result = ProbeResult::NoMatch;
1661 possibly_unsatisfied_predicates.push((o.predicate, parent_pred, Some(o.cause)));
1662 }
1663 }
1664
1665 if let ProbeResult::Match = result
1666 && let Some(return_ty) = self.return_type
1667 && let Some(mut xform_ret_ty) = xform_ret_ty
1668 {
1669 // `xform_ret_ty` has only been normalized for `InherentImplCandidate`.
1670 // We don't normalize the other candidates for perf/backwards-compat reasons...
1671 // but `self.return_type` is only set on the diagnostic-path, so we
1672 // should be okay doing it here.
1673 if !matches!(probe.kind, InherentImplCandidate(..)) {
1674 let InferOk {
1675 value: normalized_xform_ret_ty,
1676 obligations: normalization_obligations,
1677 } = self.fcx.at(&cause, self.param_env).normalize(xform_ret_ty);
1678 xform_ret_ty = normalized_xform_ret_ty;
1679 debug!("xform_ret_ty after normalization: {:?}", xform_ret_ty);
1680 // Evaluate those obligations to see if they might possibly hold.
1681 for o in normalization_obligations {
1682 let o = self.resolve_vars_if_possible(o);
1683 if !self.predicate_may_hold(&o) {
1684 result = ProbeResult::NoMatch;
1685 possibly_unsatisfied_predicates.push((
1686 o.predicate,
1687 None,
1688 Some(o.cause),
1689 ));
1690 }
1691 }
1692 }
1693
1694 debug!(
1695 "comparing return_ty {:?} with xform ret ty {:?}",
1696 return_ty, xform_ret_ty
1697 );
1698 if let ProbeResult::Match = result
1699 && self
1700 .at(&ObligationCause::dummy(), self.param_env)
1701 .sup(DefineOpaqueTypes::No, return_ty, xform_ret_ty)
1702 .is_err()
1703 {
1704 result = ProbeResult::BadReturnType;
1705 }
1706 }
1707
1708 result
1709 })
1710 }
1711
1712 /// Sometimes we get in a situation where we have multiple probes that are all impls of the
1713 /// same trait, but we don't know which impl to use. In this case, since in all cases the
1714 /// external interface of the method can be determined from the trait, it's ok not to decide.
1715 /// We can basically just collapse all of the probes for various impls into one where-clause
1716 /// probe. This will result in a pending obligation so when more type-info is available we can
1717 /// make the final decision.
1718 ///
1719 /// Example (`tests/ui/method-two-trait-defer-resolution-1.rs`):
1720 ///
1721 /// ```ignore (illustrative)
1722 /// trait Foo { ... }
1723 /// impl Foo for Vec<i32> { ... }
1724 /// impl Foo for Vec<usize> { ... }
1725 /// ```
1726 ///
1727 /// Now imagine the receiver is `Vec<_>`. It doesn't really matter at this time which impl we
1728 /// use, so it's ok to just commit to "using the method from the trait Foo".
collapse_candidates_to_trait_pick( &self, self_ty: Ty<'tcx>, probes: &[(&Candidate<'tcx>, ProbeResult)], ) -> Option<Pick<'tcx>>1729 fn collapse_candidates_to_trait_pick(
1730 &self,
1731 self_ty: Ty<'tcx>,
1732 probes: &[(&Candidate<'tcx>, ProbeResult)],
1733 ) -> Option<Pick<'tcx>> {
1734 // Do all probes correspond to the same trait?
1735 let container = probes[0].0.item.trait_container(self.tcx)?;
1736 for (p, _) in &probes[1..] {
1737 let p_container = p.item.trait_container(self.tcx)?;
1738 if p_container != container {
1739 return None;
1740 }
1741 }
1742
1743 // FIXME: check the return type here somehow.
1744 // If so, just use this trait and call it a day.
1745 Some(Pick {
1746 item: probes[0].0.item,
1747 kind: TraitPick,
1748 import_ids: probes[0].0.import_ids.clone(),
1749 autoderefs: 0,
1750 autoref_or_ptr_adjustment: None,
1751 self_ty,
1752 unstable_candidates: vec![],
1753 })
1754 }
1755
1756 /// Similarly to `probe_for_return_type`, this method attempts to find the best matching
1757 /// candidate method where the method name may have been misspelled. Similarly to other
1758 /// edit distance based suggestions, we provide at most one such suggestion.
probe_for_similar_candidate(&mut self) -> Result<Option<ty::AssocItem>, MethodError<'tcx>>1759 fn probe_for_similar_candidate(&mut self) -> Result<Option<ty::AssocItem>, MethodError<'tcx>> {
1760 debug!("probing for method names similar to {:?}", self.method_name);
1761
1762 self.probe(|_| {
1763 let mut pcx = ProbeContext::new(
1764 self.fcx,
1765 self.span,
1766 self.mode,
1767 self.method_name,
1768 self.return_type,
1769 self.orig_steps_var_values,
1770 self.steps,
1771 self.scope_expr_id,
1772 );
1773 pcx.allow_similar_names = true;
1774 pcx.assemble_inherent_candidates();
1775
1776 let method_names = pcx.candidate_method_names(|_| true);
1777 pcx.allow_similar_names = false;
1778 let applicable_close_candidates: Vec<ty::AssocItem> = method_names
1779 .iter()
1780 .filter_map(|&method_name| {
1781 pcx.reset();
1782 pcx.method_name = Some(method_name);
1783 pcx.assemble_inherent_candidates();
1784 pcx.pick_core().and_then(|pick| pick.ok()).map(|pick| pick.item)
1785 })
1786 .collect();
1787
1788 if applicable_close_candidates.is_empty() {
1789 Ok(None)
1790 } else {
1791 let best_name = {
1792 let names = applicable_close_candidates
1793 .iter()
1794 .map(|cand| cand.name)
1795 .collect::<Vec<Symbol>>();
1796 find_best_match_for_name_with_substrings(
1797 &names,
1798 self.method_name.unwrap().name,
1799 None,
1800 )
1801 }
1802 .or_else(|| {
1803 applicable_close_candidates
1804 .iter()
1805 .find(|cand| self.matches_by_doc_alias(cand.def_id))
1806 .map(|cand| cand.name)
1807 })
1808 .unwrap();
1809 Ok(applicable_close_candidates.into_iter().find(|method| method.name == best_name))
1810 }
1811 })
1812 }
1813
1814 ///////////////////////////////////////////////////////////////////////////
1815 // MISCELLANY
has_applicable_self(&self, item: &ty::AssocItem) -> bool1816 fn has_applicable_self(&self, item: &ty::AssocItem) -> bool {
1817 // "Fast track" -- check for usage of sugar when in method call
1818 // mode.
1819 //
1820 // In Path mode (i.e., resolving a value like `T::next`), consider any
1821 // associated value (i.e., methods, constants) but not types.
1822 match self.mode {
1823 Mode::MethodCall => item.fn_has_self_parameter,
1824 Mode::Path => match item.kind {
1825 ty::AssocKind::Type => false,
1826 ty::AssocKind::Fn | ty::AssocKind::Const => true,
1827 },
1828 }
1829 // FIXME -- check for types that deref to `Self`,
1830 // like `Rc<Self>` and so on.
1831 //
1832 // Note also that the current code will break if this type
1833 // includes any of the type parameters defined on the method
1834 // -- but this could be overcome.
1835 }
1836
record_static_candidate(&self, source: CandidateSource)1837 fn record_static_candidate(&self, source: CandidateSource) {
1838 self.static_candidates.borrow_mut().push(source);
1839 }
1840
1841 #[instrument(level = "debug", skip(self))]
xform_self_ty( &self, item: ty::AssocItem, impl_ty: Ty<'tcx>, substs: SubstsRef<'tcx>, ) -> (Ty<'tcx>, Option<Ty<'tcx>>)1842 fn xform_self_ty(
1843 &self,
1844 item: ty::AssocItem,
1845 impl_ty: Ty<'tcx>,
1846 substs: SubstsRef<'tcx>,
1847 ) -> (Ty<'tcx>, Option<Ty<'tcx>>) {
1848 if item.kind == ty::AssocKind::Fn && self.mode == Mode::MethodCall {
1849 let sig = self.xform_method_sig(item.def_id, substs);
1850 (sig.inputs()[0], Some(sig.output()))
1851 } else {
1852 (impl_ty, None)
1853 }
1854 }
1855
1856 #[instrument(level = "debug", skip(self))]
xform_method_sig(&self, method: DefId, substs: SubstsRef<'tcx>) -> ty::FnSig<'tcx>1857 fn xform_method_sig(&self, method: DefId, substs: SubstsRef<'tcx>) -> ty::FnSig<'tcx> {
1858 let fn_sig = self.tcx.fn_sig(method);
1859 debug!(?fn_sig);
1860
1861 assert!(!substs.has_escaping_bound_vars());
1862
1863 // It is possible for type parameters or early-bound lifetimes
1864 // to appear in the signature of `self`. The substitutions we
1865 // are given do not include type/lifetime parameters for the
1866 // method yet. So create fresh variables here for those too,
1867 // if there are any.
1868 let generics = self.tcx.generics_of(method);
1869 assert_eq!(substs.len(), generics.parent_count as usize);
1870
1871 let xform_fn_sig = if generics.params.is_empty() {
1872 fn_sig.subst(self.tcx, substs)
1873 } else {
1874 let substs = InternalSubsts::for_item(self.tcx, method, |param, _| {
1875 let i = param.index as usize;
1876 if i < substs.len() {
1877 substs[i]
1878 } else {
1879 match param.kind {
1880 GenericParamDefKind::Lifetime => {
1881 // In general, during probe we erase regions.
1882 self.tcx.lifetimes.re_erased.into()
1883 }
1884 GenericParamDefKind::Type { .. } | GenericParamDefKind::Const { .. } => {
1885 self.var_for_def(self.span, param)
1886 }
1887 }
1888 }
1889 });
1890 fn_sig.subst(self.tcx, substs)
1891 };
1892
1893 self.erase_late_bound_regions(xform_fn_sig)
1894 }
1895
1896 /// Gets the type of an impl and generate substitutions with inference vars.
impl_ty_and_substs( &self, impl_def_id: DefId, ) -> (ty::EarlyBinder<Ty<'tcx>>, SubstsRef<'tcx>)1897 fn impl_ty_and_substs(
1898 &self,
1899 impl_def_id: DefId,
1900 ) -> (ty::EarlyBinder<Ty<'tcx>>, SubstsRef<'tcx>) {
1901 (self.tcx.type_of(impl_def_id), self.fresh_substs_for_item(self.span, impl_def_id))
1902 }
1903
1904 /// Replaces late-bound-regions bound by `value` with `'static` using
1905 /// `ty::erase_late_bound_regions`.
1906 ///
1907 /// This is only a reasonable thing to do during the *probe* phase, not the *confirm* phase, of
1908 /// method matching. It is reasonable during the probe phase because we don't consider region
1909 /// relationships at all. Therefore, we can just replace all the region variables with 'static
1910 /// rather than creating fresh region variables. This is nice for two reasons:
1911 ///
1912 /// 1. Because the numbers of the region variables would otherwise be fairly unique to this
1913 /// particular method call, it winds up creating fewer types overall, which helps for memory
1914 /// usage. (Admittedly, this is a rather small effect, though measurable.)
1915 ///
1916 /// 2. It makes it easier to deal with higher-ranked trait bounds, because we can replace any
1917 /// late-bound regions with 'static. Otherwise, if we were going to replace late-bound
1918 /// regions with actual region variables as is proper, we'd have to ensure that the same
1919 /// region got replaced with the same variable, which requires a bit more coordination
1920 /// and/or tracking the substitution and
1921 /// so forth.
erase_late_bound_regions<T>(&self, value: ty::Binder<'tcx, T>) -> T where T: TypeFoldable<TyCtxt<'tcx>>,1922 fn erase_late_bound_regions<T>(&self, value: ty::Binder<'tcx, T>) -> T
1923 where
1924 T: TypeFoldable<TyCtxt<'tcx>>,
1925 {
1926 self.tcx.erase_late_bound_regions(value)
1927 }
1928
1929 /// Determine if the given associated item type is relevant in the current context.
is_relevant_kind_for_mode(&self, kind: ty::AssocKind) -> bool1930 fn is_relevant_kind_for_mode(&self, kind: ty::AssocKind) -> bool {
1931 match (self.mode, kind) {
1932 (Mode::MethodCall, ty::AssocKind::Fn) => true,
1933 (Mode::Path, ty::AssocKind::Const | ty::AssocKind::Fn) => true,
1934 _ => false,
1935 }
1936 }
1937
1938 /// Determine if the associated item withe the given DefId matches
1939 /// the desired name via a doc alias.
matches_by_doc_alias(&self, def_id: DefId) -> bool1940 fn matches_by_doc_alias(&self, def_id: DefId) -> bool {
1941 let Some(name) = self.method_name else { return false; };
1942 let Some(local_def_id) = def_id.as_local() else { return false; };
1943 let hir_id = self.fcx.tcx.hir().local_def_id_to_hir_id(local_def_id);
1944 let attrs = self.fcx.tcx.hir().attrs(hir_id);
1945 for attr in attrs {
1946 let sym::doc = attr.name_or_empty() else { continue; };
1947 let Some(values) = attr.meta_item_list() else { continue; };
1948 for v in values {
1949 if v.name_or_empty() != sym::alias {
1950 continue;
1951 }
1952 if let Some(nested) = v.meta_item_list() {
1953 // #[doc(alias("foo", "bar"))]
1954 for n in nested {
1955 if let Some(lit) = n.lit() && name.as_str() == lit.symbol.as_str() {
1956 return true;
1957 }
1958 }
1959 } else if let Some(meta) = v.meta_item()
1960 && let Some(lit) = meta.name_value_literal()
1961 && name.as_str() == lit.symbol.as_str() {
1962 // #[doc(alias = "foo")]
1963 return true;
1964 }
1965 }
1966 }
1967 false
1968 }
1969
1970 /// Finds the method with the appropriate name (or return type, as the case may be). If
1971 /// `allow_similar_names` is set, find methods with close-matching names.
1972 // The length of the returned iterator is nearly always 0 or 1 and this
1973 // method is fairly hot.
impl_or_trait_item(&self, def_id: DefId) -> SmallVec<[ty::AssocItem; 1]>1974 fn impl_or_trait_item(&self, def_id: DefId) -> SmallVec<[ty::AssocItem; 1]> {
1975 if let Some(name) = self.method_name {
1976 if self.allow_similar_names {
1977 let max_dist = max(name.as_str().len(), 3) / 3;
1978 self.tcx
1979 .associated_items(def_id)
1980 .in_definition_order()
1981 .filter(|x| {
1982 if !self.is_relevant_kind_for_mode(x.kind) {
1983 return false;
1984 }
1985 if self.matches_by_doc_alias(x.def_id) {
1986 return true;
1987 }
1988 match edit_distance_with_substrings(
1989 name.as_str(),
1990 x.name.as_str(),
1991 max_dist,
1992 ) {
1993 Some(d) => d > 0,
1994 None => false,
1995 }
1996 })
1997 .copied()
1998 .collect()
1999 } else {
2000 self.fcx
2001 .associated_value(def_id, name)
2002 .filter(|x| self.is_relevant_kind_for_mode(x.kind))
2003 .map_or_else(SmallVec::new, |x| SmallVec::from_buf([x]))
2004 }
2005 } else {
2006 self.tcx
2007 .associated_items(def_id)
2008 .in_definition_order()
2009 .filter(|x| self.is_relevant_kind_for_mode(x.kind))
2010 .copied()
2011 .collect()
2012 }
2013 }
2014 }
2015
2016 impl<'tcx> Candidate<'tcx> {
to_unadjusted_pick( &self, self_ty: Ty<'tcx>, unstable_candidates: Vec<(Candidate<'tcx>, Symbol)>, ) -> Pick<'tcx>2017 fn to_unadjusted_pick(
2018 &self,
2019 self_ty: Ty<'tcx>,
2020 unstable_candidates: Vec<(Candidate<'tcx>, Symbol)>,
2021 ) -> Pick<'tcx> {
2022 Pick {
2023 item: self.item,
2024 kind: match self.kind {
2025 InherentImplCandidate(..) => InherentImplPick,
2026 ObjectCandidate => ObjectPick,
2027 TraitCandidate(_) => TraitPick,
2028 WhereClauseCandidate(ref trait_ref) => {
2029 // Only trait derived from where-clauses should
2030 // appear here, so they should not contain any
2031 // inference variables or other artifacts. This
2032 // means they are safe to put into the
2033 // `WhereClausePick`.
2034 assert!(
2035 !trait_ref.skip_binder().substs.has_infer()
2036 && !trait_ref.skip_binder().substs.has_placeholders()
2037 );
2038
2039 WhereClausePick(*trait_ref)
2040 }
2041 },
2042 import_ids: self.import_ids.clone(),
2043 autoderefs: 0,
2044 autoref_or_ptr_adjustment: None,
2045 self_ty,
2046 unstable_candidates,
2047 }
2048 }
2049 }
2050