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