compiler/rustc_typeck/src/check/method/probe.rs

   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::{
  25     self, ParamEnvAnd, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, TypeFoldable, WithConstness,
  26 };
  27 use rustc_session::lint;
  28 use rustc_span::def_id::LocalDefId;
  29 use rustc_span::lev_distance::{find_best_match_for_name, lev_distance};
  30 use rustc_span::{symbol::Ident, Span, Symbol, DUMMY_SP};
  31 use rustc_trait_selection::autoderef::{self, Autoderef};
  32 use rustc_trait_selection::traits::query::evaluate_obligation::InferCtxtExt;
  33 use rustc_trait_selection::traits::query::method_autoderef::MethodAutoderefBadTy;
  34 use rustc_trait_selection::traits::query::method_autoderef::{
  35     CandidateStep, MethodAutoderefStepsResult,
  36 };
  37 use rustc_trait_selection::traits::query::CanonicalTyGoal;
  38 use rustc_trait_selection::traits::{self, ObligationCause};
  39 use std::cmp::max;
  40 use std::iter;
  41 use std::mem;
  42 use std::ops::Deref;
  43
  44 use smallvec::{smallvec, SmallVec};
  45
  46 use self::CandidateKind::*;
  47 pub use self::PickKind::*;
  48
  49 /// Boolean flag used to indicate if this search is for a suggestion
  50 /// or not. If true, we can allow ambiguity and so forth.
  51 #[derive(Clone, Copy, Debug)]
  52 pub struct IsSuggestion(pub bool);
  53
  54 struct ProbeContext<'a, 'tcx> {
  55     fcx: &'a FnCtxt<'a, 'tcx>,
  56     span: Span,
  57     mode: Mode,
  58     method_name: Option<Ident>,
  59     return_type: Option<Ty<'tcx>>,
  60
  61     /// This is the OriginalQueryValues for the steps queries
  62     /// that are answered in steps.
  63     orig_steps_var_values: OriginalQueryValues<'tcx>,
  64     steps: Lrc<Vec<CandidateStep<'tcx>>>,
  65
  66     inherent_candidates: Vec<Candidate<'tcx>>,
  67     extension_candidates: Vec<Candidate<'tcx>>,
  68     impl_dups: FxHashSet<DefId>,
  69
  70     /// Collects near misses when the candidate functions are missing a `self` keyword and is only
  71     /// used for error reporting
  72     static_candidates: Vec<CandidateSource>,
  73
  74     /// When probing for names, include names that are close to the
  75     /// requested name (by Levensthein distance)
  76     allow_similar_names: bool,
  77
  78     /// Some(candidate) if there is a private candidate
  79     private_candidate: Option<(DefKind, DefId)>,
  80
  81     /// Collects near misses when trait bounds for type parameters are unsatisfied and is only used
  82     /// for error reporting
  83     unsatisfied_predicates: Vec<(ty::Predicate<'tcx>, Option<ty::Predicate<'tcx>>)>,
  84
  85     is_suggestion: IsSuggestion,
  86
  87     scope_expr_id: hir::HirId,
  88 }
  89
  90 impl<'a, 'tcx> Deref for ProbeContext<'a, 'tcx> {
  91     type Target = FnCtxt<'a, 'tcx>;
  92     fn deref(&self) -> &Self::Target {
  93         &self.fcx
  94     }
  95 }
  96
  97 #[derive(Debug)]
  98 struct Candidate<'tcx> {
  99     // Candidates are (I'm not quite sure, but they are mostly) basically
 100     // some metadata on top of a `ty::AssocItem` (without substs).
 101     //
 102     // However, method probing wants to be able to evaluate the predicates
 103     // for a function with the substs applied - for example, if a function
 104     // has `where Self: Sized`, we don't want to consider it unless `Self`
 105     // is actually `Sized`, and similarly, return-type suggestions want
 106     // to consider the "actual" return type.
 107     //
 108     // The way this is handled is through `xform_self_ty`. It contains
 109     // the receiver type of this candidate, but `xform_self_ty`,
 110     // `xform_ret_ty` and `kind` (which contains the predicates) have the
 111     // generic parameters of this candidate substituted with the *same set*
 112     // of inference variables, which acts as some weird sort of "query".
 113     //
 114     // When we check out a candidate, we require `xform_self_ty` to be
 115     // a subtype of the passed-in self-type, and this equates the type
 116     // variables in the rest of the fields.
 117     //
 118     // For example, if we have this candidate:
 119     // ```
 120     //    trait Foo {
 121     //        fn foo(&self) where Self: Sized;
 122     //    }
 123     // ```
 124     //
 125     // Then `xform_self_ty` will be `&'erased ?X` and `kind` will contain
 126     // the predicate `?X: Sized`, so if we are evaluating `Foo` for a
 127     // the receiver `&T`, we'll do the subtyping which will make `?X`
 128     // get the right value, then when we evaluate the predicate we'll check
 129     // if `T: Sized`.
 130     xform_self_ty: Ty<'tcx>,
 131     xform_ret_ty: Option<Ty<'tcx>>,
 132     item: ty::AssocItem,
 133     kind: CandidateKind<'tcx>,
 134     import_ids: SmallVec<[LocalDefId; 1]>,
 135 }
 136
 137 #[derive(Debug)]
 138 enum CandidateKind<'tcx> {
 139     InherentImplCandidate(
 140         SubstsRef<'tcx>,
 141         // Normalize obligations
 142         Vec<traits::PredicateObligation<'tcx>>,
 143     ),
 144     ObjectCandidate,
 145     TraitCandidate(ty::TraitRef<'tcx>),
 146     WhereClauseCandidate(
 147         // Trait
 148         ty::PolyTraitRef<'tcx>,
 149     ),
 150 }
 151
 152 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
 153 enum ProbeResult {
 154     NoMatch,
 155     BadReturnType,
 156     Match,
 157 }
 158
 159 /// When adjusting a receiver we often want to do one of
 160 ///
 161 /// - Add a `&` (or `&mut`), converting the receiver from `T` to `&T` (or `&mut T`)
 162 /// - If the receiver has type `*mut T`, convert it to `*const T`
 163 ///
 164 /// This type tells us which one to do.
 165 ///
 166 /// Note that in principle we could do both at the same time. For example, when the receiver has
 167 /// type `T`, we could autoref it to `&T`, then convert to `*const T`. Or, when it has type `*mut
 168 /// T`, we could convert it to `*const T`, then autoref to `&*const T`. However, currently we do
 169 /// (at most) one of these. Either the receiver has type `T` and we convert it to `&T` (or with
 170 /// `mut`), or it has type `*mut T` and we convert it to `*const T`.
 171 #[derive(Debug, PartialEq, Clone)]
 172 pub enum AutorefOrPtrAdjustment<'tcx> {
 173     /// Receiver has type `T`, add `&` or `&mut` (it `T` is `mut`), and maybe also "unsize" it.
 174     /// Unsizing is used to convert a `[T; N]` to `[T]`, which only makes sense when autorefing.
 175     Autoref {
 176         mutbl: hir::Mutability,
 177
 178         /// Indicates that the source expression should be "unsized" to a target type. This should
 179         /// probably eventually go away in favor of just coercing method receivers.
 180         unsize: Option<Ty<'tcx>>,
 181     },
 182     /// Receiver has type `*mut T`, convert to `*const T`
 183     ToConstPtr,
 184 }
 185
 186 impl<'tcx> AutorefOrPtrAdjustment<'tcx> {
 187     fn get_unsize(&self) -> Option<Ty<'tcx>> {
 188         match self {
 189             AutorefOrPtrAdjustment::Autoref { mutbl: _, unsize } => unsize.clone(),
 190             AutorefOrPtrAdjustment::ToConstPtr => None,
 191         }
 192     }
 193 }
 194
 195 #[derive(Debug, PartialEq, Clone)]
 196 pub struct Pick<'tcx> {
 197     pub item: ty::AssocItem,
 198     pub kind: PickKind<'tcx>,
 199     pub import_ids: SmallVec<[LocalDefId; 1]>,
 200
 201     /// Indicates that the source expression should be autoderef'd N times
 202     ///
 203     ///     A = expr | *expr | **expr | ...
 204     pub autoderefs: usize,
 205
 206     /// Indicates that we want to add an autoref (and maybe also unsize it), or if the receiver is
 207     /// `*mut T`, convert it to `*const T`.
 208     pub autoref_or_ptr_adjustment: Option<AutorefOrPtrAdjustment<'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))]
 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))]
 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
 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                         &param_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
 468 pub fn provide(providers: &mut ty::query::Providers) {
 469     providers.method_autoderef_steps = method_autoderef_steps;
 470 }
 471
 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> {
 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
 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
 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
 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
 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(ref data, ..) => {
 620                 if let Some(p) = data.principal() {
 621                     // Subtle: we can't use `instantiate_query_response` here: using it will
 622                     // commit to all of the type equalities assumed by inference going through
 623                     // autoderef (see the `method-probe-no-guessing` test).
 624                     //
 625                     // However, in this code, it is OK if we end up with an object type that is
 626                     // "more general" than the object type that we are evaluating. For *every*
 627                     // object type `MY_OBJECT`, a function call that goes through a trait-ref
 628                     // of the form `<MY_OBJECT as SuperTraitOf(MY_OBJECT)>::func` is a valid
 629                     // `ObjectCandidate`, and it should be discoverable "exactly" through one
 630                     // of the iterations in the autoderef loop, so there is no problem with it
 631                     // being discoverable in another one of these iterations.
 632                     //
 633                     // Using `instantiate_canonical_with_fresh_inference_vars` on our
 634                     // `Canonical<QueryResponse<Ty<'tcx>>>` and then *throwing away* the
 635                     // `CanonicalVarValues` will exactly give us such a generalization - it
 636                     // will still match the original object type, but it won't pollute our
 637                     // type variables in any form, so just do that!
 638                     let (QueryResponse { value: generalized_self_ty, .. }, _ignored_var_values) =
 639                         self.fcx
 640                             .instantiate_canonical_with_fresh_inference_vars(self.span, &self_ty);
 641
 642                     self.assemble_inherent_candidates_from_object(generalized_self_ty);
 643                     self.assemble_inherent_impl_candidates_for_type(p.def_id());
 644                 }
 645             }
 646             ty::Adt(def, _) => {
 647                 self.assemble_inherent_impl_candidates_for_type(def.did);
 648             }
 649             ty::Foreign(did) => {
 650                 self.assemble_inherent_impl_candidates_for_type(did);
 651             }
 652             ty::Param(p) => {
 653                 self.assemble_inherent_candidates_from_param(p);
 654             }
 655             ty::Bool => {
 656                 let lang_def_id = lang_items.bool_impl();
 657                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 658             }
 659             ty::Char => {
 660                 let lang_def_id = lang_items.char_impl();
 661                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 662             }
 663             ty::Str => {
 664                 let lang_def_id = lang_items.str_impl();
 665                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 666
 667                 let lang_def_id = lang_items.str_alloc_impl();
 668                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 669             }
 670             ty::Slice(_) => {
 671                 for &lang_def_id in &[
 672                     lang_items.slice_impl(),
 673                     lang_items.slice_u8_impl(),
 674                     lang_items.slice_alloc_impl(),
 675                     lang_items.slice_u8_alloc_impl(),
 676                 ] {
 677                     self.assemble_inherent_impl_for_primitive(lang_def_id);
 678                 }
 679             }
 680             ty::Array(_, _) => {
 681                 let lang_def_id = lang_items.array_impl();
 682                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 683             }
 684             ty::RawPtr(ty::TypeAndMut { ty: _, mutbl }) => {
 685                 let (lang_def_id1, lang_def_id2) = match mutbl {
 686                     hir::Mutability::Not => {
 687                         (lang_items.const_ptr_impl(), lang_items.const_slice_ptr_impl())
 688                     }
 689                     hir::Mutability::Mut => {
 690                         (lang_items.mut_ptr_impl(), lang_items.mut_slice_ptr_impl())
 691                     }
 692                 };
 693                 self.assemble_inherent_impl_for_primitive(lang_def_id1);
 694                 self.assemble_inherent_impl_for_primitive(lang_def_id2);
 695             }
 696             ty::Int(i) => {
 697                 let lang_def_id = match i {
 698                     ty::IntTy::I8 => lang_items.i8_impl(),
 699                     ty::IntTy::I16 => lang_items.i16_impl(),
 700                     ty::IntTy::I32 => lang_items.i32_impl(),
 701                     ty::IntTy::I64 => lang_items.i64_impl(),
 702                     ty::IntTy::I128 => lang_items.i128_impl(),
 703                     ty::IntTy::Isize => lang_items.isize_impl(),
 704                 };
 705                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 706             }
 707             ty::Uint(i) => {
 708                 let lang_def_id = match i {
 709                     ty::UintTy::U8 => lang_items.u8_impl(),
 710                     ty::UintTy::U16 => lang_items.u16_impl(),
 711                     ty::UintTy::U32 => lang_items.u32_impl(),
 712                     ty::UintTy::U64 => lang_items.u64_impl(),
 713                     ty::UintTy::U128 => lang_items.u128_impl(),
 714                     ty::UintTy::Usize => lang_items.usize_impl(),
 715                 };
 716                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 717             }
 718             ty::Float(f) => {
 719                 let (lang_def_id1, lang_def_id2) = match f {
 720                     ty::FloatTy::F32 => (lang_items.f32_impl(), lang_items.f32_runtime_impl()),
 721                     ty::FloatTy::F64 => (lang_items.f64_impl(), lang_items.f64_runtime_impl()),
 722                 };
 723                 self.assemble_inherent_impl_for_primitive(lang_def_id1);
 724                 self.assemble_inherent_impl_for_primitive(lang_def_id2);
 725             }
 726             _ => {}
 727         }
 728     }
 729
 730     fn assemble_inherent_impl_for_primitive(&mut self, lang_def_id: Option<DefId>) {
 731         if let Some(impl_def_id) = lang_def_id {
 732             self.assemble_inherent_impl_probe(impl_def_id);
 733         }
 734     }
 735
 736     fn assemble_inherent_impl_candidates_for_type(&mut self, def_id: DefId) {
 737         let impl_def_ids = self.tcx.at(self.span).inherent_impls(def_id);
 738         for &impl_def_id in impl_def_ids.iter() {
 739             self.assemble_inherent_impl_probe(impl_def_id);
 740         }
 741     }
 742
 743     fn assemble_inherent_impl_probe(&mut self, impl_def_id: DefId) {
 744         if !self.impl_dups.insert(impl_def_id) {
 745             return; // already visited
 746         }
 747
 748         debug!("assemble_inherent_impl_probe {:?}", impl_def_id);
 749
 750         for item in self.impl_or_trait_item(impl_def_id) {
 751             if !self.has_applicable_self(&item) {
 752                 // No receiver declared. Not a candidate.
 753                 self.record_static_candidate(ImplSource(impl_def_id));
 754                 continue;
 755             }
 756
 757             let (impl_ty, impl_substs) = self.impl_ty_and_substs(impl_def_id);
 758             let impl_ty = impl_ty.subst(self.tcx, impl_substs);
 759
 760             // Determine the receiver type that the method itself expects.
 761             let xform_tys = self.xform_self_ty(&item, impl_ty, impl_substs);
 762
 763             // We can't use normalize_associated_types_in as it will pollute the
 764             // fcx's fulfillment context after this probe is over.
 765             let cause = traits::ObligationCause::misc(self.span, self.body_id);
 766             let selcx = &mut traits::SelectionContext::new(self.fcx);
 767             let traits::Normalized { value: (xform_self_ty, xform_ret_ty), obligations } =
 768                 traits::normalize(selcx, self.param_env, cause, xform_tys);
 769             debug!(
 770                 "assemble_inherent_impl_probe: xform_self_ty = {:?}/{:?}",
 771                 xform_self_ty, xform_ret_ty
 772             );
 773
 774             self.push_candidate(
 775                 Candidate {
 776                     xform_self_ty,
 777                     xform_ret_ty,
 778                     item,
 779                     kind: InherentImplCandidate(impl_substs, obligations),
 780                     import_ids: smallvec![],
 781                 },
 782                 true,
 783             );
 784         }
 785     }
 786
 787     fn assemble_inherent_candidates_from_object(&mut self, self_ty: Ty<'tcx>) {
 788         debug!("assemble_inherent_candidates_from_object(self_ty={:?})", self_ty);
 789
 790         let principal = match self_ty.kind() {
 791             ty::Dynamic(ref data, ..) => Some(data),
 792             _ => None,
 793         }
 794         .and_then(|data| data.principal())
 795         .unwrap_or_else(|| {
 796             span_bug!(
 797                 self.span,
 798                 "non-object {:?} in assemble_inherent_candidates_from_object",
 799                 self_ty
 800             )
 801         });
 802
 803         // It is illegal to invoke a method on a trait instance that refers to
 804         // the `Self` type. An [`ObjectSafetyViolation::SupertraitSelf`] error
 805         // will be reported by `object_safety.rs` if the method refers to the
 806         // `Self` type anywhere other than the receiver. Here, we use a
 807         // substitution that replaces `Self` with the object type itself. Hence,
 808         // a `&self` method will wind up with an argument type like `&dyn Trait`.
 809         let trait_ref = principal.with_self_ty(self.tcx, self_ty);
 810         self.elaborate_bounds(iter::once(trait_ref), |this, new_trait_ref, item| {
 811             let new_trait_ref = this.erase_late_bound_regions(new_trait_ref);
 812
 813             let (xform_self_ty, xform_ret_ty) =
 814                 this.xform_self_ty(&item, new_trait_ref.self_ty(), new_trait_ref.substs);
 815             this.push_candidate(
 816                 Candidate {
 817                     xform_self_ty,
 818                     xform_ret_ty,
 819                     item,
 820                     kind: ObjectCandidate,
 821                     import_ids: smallvec![],
 822                 },
 823                 true,
 824             );
 825         });
 826     }
 827
 828     fn assemble_inherent_candidates_from_param(&mut self, param_ty: ty::ParamTy) {
 829         // FIXME: do we want to commit to this behavior for param bounds?
 830         debug!("assemble_inherent_candidates_from_param(param_ty={:?})", param_ty);
 831
 832         let bounds = self.param_env.caller_bounds().iter().filter_map(|predicate| {
 833             let bound_predicate = predicate.kind();
 834             match bound_predicate.skip_binder() {
 835                 ty::PredicateKind::Trait(trait_predicate, _) => {
 836                     match *trait_predicate.trait_ref.self_ty().kind() {
 837                         ty::Param(p) if p == param_ty => {
 838                             Some(bound_predicate.rebind(trait_predicate.trait_ref))
 839                         }
 840                         _ => None,
 841                     }
 842                 }
 843                 ty::PredicateKind::Subtype(..)
 844                 | ty::PredicateKind::Projection(..)
 845                 | ty::PredicateKind::RegionOutlives(..)
 846                 | ty::PredicateKind::WellFormed(..)
 847                 | ty::PredicateKind::ObjectSafe(..)
 848                 | ty::PredicateKind::ClosureKind(..)
 849                 | ty::PredicateKind::TypeOutlives(..)
 850                 | ty::PredicateKind::ConstEvaluatable(..)
 851                 | ty::PredicateKind::ConstEquate(..)
 852                 | ty::PredicateKind::TypeWellFormedFromEnv(..) => None,
 853             }
 854         });
 855
 856         self.elaborate_bounds(bounds, |this, poly_trait_ref, item| {
 857             let trait_ref = this.erase_late_bound_regions(poly_trait_ref);
 858
 859             let (xform_self_ty, xform_ret_ty) =
 860                 this.xform_self_ty(&item, trait_ref.self_ty(), trait_ref.substs);
 861
 862             // Because this trait derives from a where-clause, it
 863             // should not contain any inference variables or other
 864             // artifacts. This means it is safe to put into the
 865             // `WhereClauseCandidate` and (eventually) into the
 866             // `WhereClausePick`.
 867             assert!(!trait_ref.substs.needs_infer());
 868
 869             this.push_candidate(
 870                 Candidate {
 871                     xform_self_ty,
 872                     xform_ret_ty,
 873                     item,
 874                     kind: WhereClauseCandidate(poly_trait_ref),
 875                     import_ids: smallvec![],
 876                 },
 877                 true,
 878             );
 879         });
 880     }
 881
 882     // Do a search through a list of bounds, using a callback to actually
 883     // create the candidates.
 884     fn elaborate_bounds<F>(
 885         &mut self,
 886         bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>,
 887         mut mk_cand: F,
 888     ) where
 889         F: for<'b> FnMut(&mut ProbeContext<'b, 'tcx>, ty::PolyTraitRef<'tcx>, ty::AssocItem),
 890     {
 891         let tcx = self.tcx;
 892         for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
 893             debug!("elaborate_bounds(bound_trait_ref={:?})", bound_trait_ref);
 894             for item in self.impl_or_trait_item(bound_trait_ref.def_id()) {
 895                 if !self.has_applicable_self(&item) {
 896                     self.record_static_candidate(TraitSource(bound_trait_ref.def_id()));
 897                 } else {
 898                     mk_cand(self, bound_trait_ref, item);
 899                 }
 900             }
 901         }
 902     }
 903
 904     fn assemble_extension_candidates_for_traits_in_scope(&mut self, expr_hir_id: hir::HirId) {
 905         let mut duplicates = FxHashSet::default();
 906         let opt_applicable_traits = self.tcx.in_scope_traits(expr_hir_id);
 907         if let Some(applicable_traits) = opt_applicable_traits {
 908             for trait_candidate in applicable_traits.iter() {
 909                 let trait_did = trait_candidate.def_id;
 910                 if duplicates.insert(trait_did) {
 911                     self.assemble_extension_candidates_for_trait(
 912                         &trait_candidate.import_ids,
 913                         trait_did,
 914                     );
 915                 }
 916             }
 917         }
 918     }
 919
 920     fn assemble_extension_candidates_for_all_traits(&mut self) {
 921         let mut duplicates = FxHashSet::default();
 922         for trait_info in suggest::all_traits(self.tcx) {
 923             if duplicates.insert(trait_info.def_id) {
 924                 self.assemble_extension_candidates_for_trait(&smallvec![], trait_info.def_id);
 925             }
 926         }
 927     }
 928
 929     pub fn matches_return_type(
 930         &self,
 931         method: &ty::AssocItem,
 932         self_ty: Option<Ty<'tcx>>,
 933         expected: Ty<'tcx>,
 934     ) -> bool {
 935         match method.kind {
 936             ty::AssocKind::Fn => {
 937                 let fty = self.tcx.fn_sig(method.def_id);
 938                 self.probe(|_| {
 939                     let substs = self.fresh_substs_for_item(self.span, method.def_id);
 940                     let fty = fty.subst(self.tcx, substs);
 941                     let (fty, _) =
 942                         self.replace_bound_vars_with_fresh_vars(self.span, infer::FnCall, fty);
 943
 944                     if let Some(self_ty) = self_ty {
 945                         if self
 946                             .at(&ObligationCause::dummy(), self.param_env)
 947                             .sup(fty.inputs()[0], self_ty)
 948                             .is_err()
 949                         {
 950                             return false;
 951                         }
 952                     }
 953                     self.can_sub(self.param_env, fty.output(), expected).is_ok()
 954                 })
 955             }
 956             _ => false,
 957         }
 958     }
 959
 960     fn assemble_extension_candidates_for_trait(
 961         &mut self,
 962         import_ids: &SmallVec<[LocalDefId; 1]>,
 963         trait_def_id: DefId,
 964     ) {
 965         debug!("assemble_extension_candidates_for_trait(trait_def_id={:?})", trait_def_id);
 966         let trait_substs = self.fresh_item_substs(trait_def_id);
 967         let trait_ref = ty::TraitRef::new(trait_def_id, trait_substs);
 968
 969         if self.tcx.is_trait_alias(trait_def_id) {
 970             // For trait aliases, assume all super-traits are relevant.
 971             let bounds = iter::once(trait_ref.to_poly_trait_ref());
 972             self.elaborate_bounds(bounds, |this, new_trait_ref, item| {
 973                 let new_trait_ref = this.erase_late_bound_regions(new_trait_ref);
 974
 975                 let (xform_self_ty, xform_ret_ty) =
 976                     this.xform_self_ty(&item, new_trait_ref.self_ty(), new_trait_ref.substs);
 977                 this.push_candidate(
 978                     Candidate {
 979                         xform_self_ty,
 980                         xform_ret_ty,
 981                         item,
 982                         import_ids: import_ids.clone(),
 983                         kind: TraitCandidate(new_trait_ref),
 984                     },
 985                     false,
 986                 );
 987             });
 988         } else {
 989             debug_assert!(self.tcx.is_trait(trait_def_id));
 990             for item in self.impl_or_trait_item(trait_def_id) {
 991                 // Check whether `trait_def_id` defines a method with suitable name.
 992                 if !self.has_applicable_self(&item) {
 993                     debug!("method has inapplicable self");
 994                     self.record_static_candidate(TraitSource(trait_def_id));
 995                     continue;
 996                 }
 997
 998                 let (xform_self_ty, xform_ret_ty) =
 999                     self.xform_self_ty(&item, trait_ref.self_ty(), trait_substs);
1000                 self.push_candidate(
1001                     Candidate {
1002                         xform_self_ty,
1003                         xform_ret_ty,
1004                         item,
1005                         import_ids: import_ids.clone(),
1006                         kind: TraitCandidate(trait_ref),
1007                     },
1008                     false,
1009                 );
1010             }
1011         }
1012     }
1013
1014     fn candidate_method_names(&self) -> Vec<Ident> {
1015         let mut set = FxHashSet::default();
1016         let mut names: Vec<_> = self
1017             .inherent_candidates
1018             .iter()
1019             .chain(&self.extension_candidates)
1020             .filter(|candidate| {
1021                 if let Some(return_ty) = self.return_type {
1022                     self.matches_return_type(&candidate.item, None, return_ty)
1023                 } else {
1024                     true
1025                 }
1026             })
1027             .map(|candidate| candidate.item.ident)
1028             .filter(|&name| set.insert(name))
1029             .collect();
1030
1031         // Sort them by the name so we have a stable result.
1032         names.sort_by_cached_key(|n| n.as_str());
1033         names
1034     }
1035
1036     ///////////////////////////////////////////////////////////////////////////
1037     // THE ACTUAL SEARCH
1038
1039     fn pick(mut self) -> PickResult<'tcx> {
1040         assert!(self.method_name.is_some());
1041
1042         if let Some(r) = self.pick_core() {
1043             return r;
1044         }
1045
1046         debug!("pick: actual search failed, assemble diagnostics");
1047
1048         let static_candidates = mem::take(&mut self.static_candidates);
1049         let private_candidate = self.private_candidate.take();
1050         let unsatisfied_predicates = mem::take(&mut self.unsatisfied_predicates);
1051
1052         // things failed, so lets look at all traits, for diagnostic purposes now:
1053         self.reset();
1054
1055         let span = self.span;
1056         let tcx = self.tcx;
1057
1058         self.assemble_extension_candidates_for_all_traits();
1059
1060         let out_of_scope_traits = match self.pick_core() {
1061             Some(Ok(p)) => vec![p.item.container.id()],
1062             //Some(Ok(p)) => p.iter().map(|p| p.item.container().id()).collect(),
1063             Some(Err(MethodError::Ambiguity(v))) => v
1064                 .into_iter()
1065                 .map(|source| match source {
1066                     TraitSource(id) => id,
1067                     ImplSource(impl_id) => match tcx.trait_id_of_impl(impl_id) {
1068                         Some(id) => id,
1069                         None => span_bug!(span, "found inherent method when looking at traits"),
1070                     },
1071                 })
1072                 .collect(),
1073             Some(Err(MethodError::NoMatch(NoMatchData {
1074                 out_of_scope_traits: others, ..
1075             }))) => {
1076                 assert!(others.is_empty());
1077                 vec![]
1078             }
1079             _ => vec![],
1080         };
1081
1082         if let Some((kind, def_id)) = private_candidate {
1083             return Err(MethodError::PrivateMatch(kind, def_id, out_of_scope_traits));
1084         }
1085         let lev_candidate = self.probe_for_lev_candidate()?;
1086
1087         Err(MethodError::NoMatch(NoMatchData::new(
1088             static_candidates,
1089             unsatisfied_predicates,
1090             out_of_scope_traits,
1091             lev_candidate,
1092             self.mode,
1093         )))
1094     }
1095
1096     fn pick_core(&mut self) -> Option<PickResult<'tcx>> {
1097         let steps = self.steps.clone();
1098
1099         // find the first step that works
1100         steps
1101             .iter()
1102             .filter(|step| {
1103                 debug!("pick_core: step={:?}", step);
1104                 // skip types that are from a type error or that would require dereferencing
1105                 // a raw pointer
1106                 !step.self_ty.references_error() && !step.from_unsafe_deref
1107             })
1108             .flat_map(|step| {
1109                 let InferOk { value: self_ty, obligations: _ } = self
1110                     .fcx
1111                     .probe_instantiate_query_response(
1112                         self.span,
1113                         &self.orig_steps_var_values,
1114                         &step.self_ty,
1115                     )
1116                     .unwrap_or_else(|_| {
1117                         span_bug!(self.span, "{:?} was applicable but now isn't?", step.self_ty)
1118                     });
1119                 self.pick_by_value_method(step, self_ty).or_else(|| {
1120                     self.pick_autorefd_method(step, self_ty, hir::Mutability::Not)
1121                         .or_else(|| self.pick_autorefd_method(step, self_ty, hir::Mutability::Mut))
1122                         .or_else(|| self.pick_const_ptr_method(step, self_ty))
1123                 })
1124             })
1125             .next()
1126     }
1127
1128     /// For each type `T` in the step list, this attempts to find a method where
1129     /// the (transformed) self type is exactly `T`. We do however do one
1130     /// transformation on the adjustment: if we are passing a region pointer in,
1131     /// we will potentially *reborrow* it to a shorter lifetime. This allows us
1132     /// to transparently pass `&mut` pointers, in particular, without consuming
1133     /// them for their entire lifetime.
1134     fn pick_by_value_method(
1135         &mut self,
1136         step: &CandidateStep<'tcx>,
1137         self_ty: Ty<'tcx>,
1138     ) -> Option<PickResult<'tcx>> {
1139         if step.unsize {
1140             return None;
1141         }
1142
1143         self.pick_method(self_ty).map(|r| {
1144             r.map(|mut pick| {
1145                 pick.autoderefs = step.autoderefs;
1146
1147                 // Insert a `&*` or `&mut *` if this is a reference type:
1148                 if let ty::Ref(_, _, mutbl) = *step.self_ty.value.value.kind() {
1149                     pick.autoderefs += 1;
1150                     pick.autoref_or_ptr_adjustment = Some(AutorefOrPtrAdjustment::Autoref {
1151                         mutbl,
1152                         unsize: pick.autoref_or_ptr_adjustment.and_then(|a| a.get_unsize()),
1153                     })
1154                 }
1155
1156                 pick
1157             })
1158         })
1159     }
1160
1161     fn pick_autorefd_method(
1162         &mut self,
1163         step: &CandidateStep<'tcx>,
1164         self_ty: Ty<'tcx>,
1165         mutbl: hir::Mutability,
1166     ) -> Option<PickResult<'tcx>> {
1167         let tcx = self.tcx;
1168
1169         // In general, during probing we erase regions.
1170         let region = tcx.lifetimes.re_erased;
1171
1172         let autoref_ty = tcx.mk_ref(region, ty::TypeAndMut { ty: self_ty, mutbl });
1173         self.pick_method(autoref_ty).map(|r| {
1174             r.map(|mut pick| {
1175                 pick.autoderefs = step.autoderefs;
1176                 pick.autoref_or_ptr_adjustment = Some(AutorefOrPtrAdjustment::Autoref {
1177                     mutbl,
1178                     unsize: step.unsize.then_some(self_ty),
1179                 });
1180                 pick
1181             })
1182         })
1183     }
1184
1185     /// If `self_ty` is `*mut T` then this picks `*const T` methods. The reason why we have a
1186     /// special case for this is because going from `*mut T` to `*const T` with autoderefs and
1187     /// autorefs would require dereferencing the pointer, which is not safe.
1188     fn pick_const_ptr_method(
1189         &mut self,
1190         step: &CandidateStep<'tcx>,
1191         self_ty: Ty<'tcx>,
1192     ) -> Option<PickResult<'tcx>> {
1193         // Don't convert an unsized reference to ptr
1194         if step.unsize {
1195             return None;
1196         }
1197
1198         let ty = match self_ty.kind() {
1199             ty::RawPtr(ty::TypeAndMut { ty, mutbl: hir::Mutability::Mut }) => ty,
1200             _ => return None,
1201         };
1202
1203         let const_self_ty = ty::TypeAndMut { ty, mutbl: hir::Mutability::Not };
1204         let const_ptr_ty = self.tcx.mk_ptr(const_self_ty);
1205         self.pick_method(const_ptr_ty).map(|r| {
1206             r.map(|mut pick| {
1207                 pick.autoderefs = step.autoderefs;
1208                 pick.autoref_or_ptr_adjustment = Some(AutorefOrPtrAdjustment::ToConstPtr);
1209                 pick
1210             })
1211         })
1212     }
1213
1214     fn pick_method(&mut self, self_ty: Ty<'tcx>) -> Option<PickResult<'tcx>> {
1215         debug!("pick_method(self_ty={})", self.ty_to_string(self_ty));
1216
1217         let mut possibly_unsatisfied_predicates = Vec::new();
1218         let mut unstable_candidates = Vec::new();
1219
1220         for (kind, candidates) in
1221             &[("inherent", &self.inherent_candidates), ("extension", &self.extension_candidates)]
1222         {
1223             debug!("searching {} candidates", kind);
1224             let res = self.consider_candidates(
1225                 self_ty,
1226                 candidates.iter(),
1227                 &mut possibly_unsatisfied_predicates,
1228                 Some(&mut unstable_candidates),
1229             );
1230             if let Some(pick) = res {
1231                 if !self.is_suggestion.0 && !unstable_candidates.is_empty() {
1232                     if let Ok(p) = &pick {
1233                         // Emit a lint if there are unstable candidates alongside the stable ones.
1234                         //
1235                         // We suppress warning if we're picking the method only because it is a
1236                         // suggestion.
1237                         self.emit_unstable_name_collision_hint(p, &unstable_candidates, self_ty);
1238                     }
1239                 }
1240                 return Some(pick);
1241             }
1242         }
1243
1244         debug!("searching unstable candidates");
1245         let res = self.consider_candidates(
1246             self_ty,
1247             unstable_candidates.into_iter().map(|(c, _)| c),
1248             &mut possibly_unsatisfied_predicates,
1249             None,
1250         );
1251         if res.is_none() {
1252             self.unsatisfied_predicates.extend(possibly_unsatisfied_predicates);
1253         }
1254         res
1255     }
1256
1257     fn consider_candidates<'b, ProbesIter>(
1258         &self,
1259         self_ty: Ty<'tcx>,
1260         probes: ProbesIter,
1261         possibly_unsatisfied_predicates: &mut Vec<(
1262             ty::Predicate<'tcx>,
1263             Option<ty::Predicate<'tcx>>,
1264         )>,
1265         unstable_candidates: Option<&mut Vec<(&'b Candidate<'tcx>, Symbol)>>,
1266     ) -> Option<PickResult<'tcx>>
1267     where
1268         ProbesIter: Iterator<Item = &'b Candidate<'tcx>> + Clone,
1269     {
1270         let mut applicable_candidates: Vec<_> = probes
1271             .clone()
1272             .map(|probe| {
1273                 (probe, self.consider_probe(self_ty, probe, possibly_unsatisfied_predicates))
1274             })
1275             .filter(|&(_, status)| status != ProbeResult::NoMatch)
1276             .collect();
1277
1278         debug!("applicable_candidates: {:?}", applicable_candidates);
1279
1280         if applicable_candidates.len() > 1 {
1281             if let Some(pick) = self.collapse_candidates_to_trait_pick(&applicable_candidates[..]) {
1282                 return Some(Ok(pick));
1283             }
1284         }
1285
1286         if let Some(uc) = unstable_candidates {
1287             applicable_candidates.retain(|&(p, _)| {
1288                 if let stability::EvalResult::Deny { feature, .. } =
1289                     self.tcx.eval_stability(p.item.def_id, None, self.span)
1290                 {
1291                     uc.push((p, feature));
1292                     return false;
1293                 }
1294                 true
1295             });
1296         }
1297
1298         if applicable_candidates.len() > 1 {
1299             let sources = probes.map(|p| self.candidate_source(p, self_ty)).collect();
1300             return Some(Err(MethodError::Ambiguity(sources)));
1301         }
1302
1303         applicable_candidates.pop().map(|(probe, status)| {
1304             if status == ProbeResult::Match {
1305                 Ok(probe.to_unadjusted_pick())
1306             } else {
1307                 Err(MethodError::BadReturnType)
1308             }
1309         })
1310     }
1311
1312     fn emit_unstable_name_collision_hint(
1313         &self,
1314         stable_pick: &Pick<'_>,
1315         unstable_candidates: &[(&Candidate<'tcx>, Symbol)],
1316         self_ty: Ty<'tcx>,
1317     ) {
1318         self.tcx.struct_span_lint_hir(
1319             lint::builtin::UNSTABLE_NAME_COLLISIONS,
1320             self.scope_expr_id,
1321             self.span,
1322             |lint| {
1323                 let def_kind = stable_pick.item.kind.as_def_kind();
1324                 let mut diag = lint.build(&format!(
1325                     "{} {} with this name may be added to the standard library in the future",
1326                     def_kind.article(),
1327                     def_kind.descr(stable_pick.item.def_id),
1328                 ));
1329                 match (stable_pick.item.kind, stable_pick.item.container) {
1330                     (ty::AssocKind::Fn, _) => {
1331                         // FIXME: This should be a `span_suggestion` instead of `help`
1332                         // However `self.span` only
1333                         // highlights the method name, so we can't use it. Also consider reusing
1334                         // the code from `report_method_error()`.
1335                         diag.help(&format!(
1336                             "call with fully qualified syntax `{}(...)` to keep using the current \
1337                              method",
1338                             self.tcx.def_path_str(stable_pick.item.def_id),
1339                         ));
1340                     }
1341                     (ty::AssocKind::Const, ty::AssocItemContainer::TraitContainer(def_id)) => {
1342                         diag.span_suggestion(
1343                             self.span,
1344                             "use the fully qualified path to the associated const",
1345                             format!(
1346                                 "<{} as {}>::{}",
1347                                 self_ty,
1348                                 self.tcx.def_path_str(def_id),
1349                                 stable_pick.item.ident
1350                             ),
1351                             Applicability::MachineApplicable,
1352                         );
1353                     }
1354                     _ => {}
1355                 }
1356                 if self.tcx.sess.is_nightly_build() {
1357                     for (candidate, feature) in unstable_candidates {
1358                         diag.help(&format!(
1359                             "add `#![feature({})]` to the crate attributes to enable `{}`",
1360                             feature,
1361                             self.tcx.def_path_str(candidate.item.def_id),
1362                         ));
1363                     }
1364                 }
1365
1366                 diag.emit();
1367             },
1368         );
1369     }
1370
1371     fn select_trait_candidate(
1372         &self,
1373         trait_ref: ty::TraitRef<'tcx>,
1374     ) -> traits::SelectionResult<'tcx, traits::Selection<'tcx>> {
1375         let cause = traits::ObligationCause::misc(self.span, self.body_id);
1376         let predicate = trait_ref.to_poly_trait_ref().to_poly_trait_predicate();
1377         let obligation = traits::Obligation::new(cause, self.param_env, predicate);
1378         traits::SelectionContext::new(self).select(&obligation)
1379     }
1380
1381     fn candidate_source(&self, candidate: &Candidate<'tcx>, self_ty: Ty<'tcx>) -> CandidateSource {
1382         match candidate.kind {
1383             InherentImplCandidate(..) => ImplSource(candidate.item.container.id()),
1384             ObjectCandidate | WhereClauseCandidate(_) => TraitSource(candidate.item.container.id()),
1385             TraitCandidate(trait_ref) => self.probe(|_| {
1386                 let _ = self
1387                     .at(&ObligationCause::dummy(), self.param_env)
1388                     .sup(candidate.xform_self_ty, self_ty);
1389                 match self.select_trait_candidate(trait_ref) {
1390                     Ok(Some(traits::ImplSource::UserDefined(ref impl_data))) => {
1391                         // If only a single impl matches, make the error message point
1392                         // to that impl.
1393                         ImplSource(impl_data.impl_def_id)
1394                     }
1395                     _ => TraitSource(candidate.item.container.id()),
1396                 }
1397             }),
1398         }
1399     }
1400
1401     fn consider_probe(
1402         &self,
1403         self_ty: Ty<'tcx>,
1404         probe: &Candidate<'tcx>,
1405         possibly_unsatisfied_predicates: &mut Vec<(
1406             ty::Predicate<'tcx>,
1407             Option<ty::Predicate<'tcx>>,
1408         )>,
1409     ) -> ProbeResult {
1410         debug!("consider_probe: self_ty={:?} probe={:?}", self_ty, probe);
1411
1412         self.probe(|_| {
1413             // First check that the self type can be related.
1414             let sub_obligations = match self
1415                 .at(&ObligationCause::dummy(), self.param_env)
1416                 .sup(probe.xform_self_ty, self_ty)
1417             {
1418                 Ok(InferOk { obligations, value: () }) => obligations,
1419                 Err(_) => {
1420                     debug!("--> cannot relate self-types");
1421                     return ProbeResult::NoMatch;
1422                 }
1423             };
1424
1425             let mut result = ProbeResult::Match;
1426             let selcx = &mut traits::SelectionContext::new(self);
1427             let cause = traits::ObligationCause::misc(self.span, self.body_id);
1428
1429             // If so, impls may carry other conditions (e.g., where
1430             // clauses) that must be considered. Make sure that those
1431             // match as well (or at least may match, sometimes we
1432             // don't have enough information to fully evaluate).
1433             match probe.kind {
1434                 InherentImplCandidate(ref substs, ref ref_obligations) => {
1435                     // Check whether the impl imposes obligations we have to worry about.
1436                     let impl_def_id = probe.item.container.id();
1437                     let impl_bounds = self.tcx.predicates_of(impl_def_id);
1438                     let impl_bounds = impl_bounds.instantiate(self.tcx, substs);
1439                     let traits::Normalized { value: impl_bounds, obligations: norm_obligations } =
1440                         traits::normalize(selcx, self.param_env, cause.clone(), impl_bounds);
1441
1442                     // Convert the bounds into obligations.
1443                     let impl_obligations =
1444                         traits::predicates_for_generics(cause, self.param_env, impl_bounds);
1445
1446                     let candidate_obligations = impl_obligations
1447                         .chain(norm_obligations.into_iter())
1448                         .chain(ref_obligations.iter().cloned());
1449                     // Evaluate those obligations to see if they might possibly hold.
1450                     for o in candidate_obligations {
1451                         let o = self.resolve_vars_if_possible(o);
1452                         if !self.predicate_may_hold(&o) {
1453                             result = ProbeResult::NoMatch;
1454                             possibly_unsatisfied_predicates.push((o.predicate, None));
1455                         }
1456                     }
1457                 }
1458
1459                 ObjectCandidate | WhereClauseCandidate(..) => {
1460                     // These have no additional conditions to check.
1461                 }
1462
1463                 TraitCandidate(trait_ref) => {
1464                     if let Some(method_name) = self.method_name {
1465                         // Some trait methods are excluded for arrays before 2021.
1466                         // (`array.into_iter()` wants a slice iterator for compatibility.)
1467                         if self_ty.is_array() && !method_name.span.rust_2021() {
1468                             let trait_def = self.tcx.trait_def(trait_ref.def_id);
1469                             if trait_def.skip_array_during_method_dispatch {
1470                                 return ProbeResult::NoMatch;
1471                             }
1472                         }
1473                     }
1474                     let predicate = trait_ref.without_const().to_predicate(self.tcx);
1475                     let obligation = traits::Obligation::new(cause, self.param_env, predicate);
1476                     if !self.predicate_may_hold(&obligation) {
1477                         result = ProbeResult::NoMatch;
1478                         if self.probe(|_| {
1479                             match self.select_trait_candidate(trait_ref) {
1480                                 Err(_) => return true,
1481                                 Ok(Some(impl_source))
1482                                     if !impl_source.borrow_nested_obligations().is_empty() =>
1483                                 {
1484                                     for obligation in impl_source.borrow_nested_obligations() {
1485                                         // Determine exactly which obligation wasn't met, so
1486                                         // that we can give more context in the error.
1487                                         if !self.predicate_may_hold(obligation) {
1488                                             let nested_predicate =
1489                                                 self.resolve_vars_if_possible(obligation.predicate);
1490                                             let predicate =
1491                                                 self.resolve_vars_if_possible(predicate);
1492                                             let p = if predicate == nested_predicate {
1493                                                 // Avoid "`MyStruct: Foo` which is required by
1494                                                 // `MyStruct: Foo`" in E0599.
1495                                                 None
1496                                             } else {
1497                                                 Some(predicate)
1498                                             };
1499                                             possibly_unsatisfied_predicates
1500                                                 .push((nested_predicate, p));
1501                                         }
1502                                     }
1503                                 }
1504                                 _ => {
1505                                     // Some nested subobligation of this predicate
1506                                     // failed.
1507                                     let predicate = self.resolve_vars_if_possible(predicate);
1508                                     possibly_unsatisfied_predicates.push((predicate, None));
1509                                 }
1510                             }
1511                             false
1512                         }) {
1513                             // This candidate's primary obligation doesn't even
1514                             // select - don't bother registering anything in
1515                             // `potentially_unsatisfied_predicates`.
1516                             return ProbeResult::NoMatch;
1517                         }
1518                     }
1519                 }
1520             }
1521
1522             // Evaluate those obligations to see if they might possibly hold.
1523             for o in sub_obligations {
1524                 let o = self.resolve_vars_if_possible(o);
1525                 if !self.predicate_may_hold(&o) {
1526                     result = ProbeResult::NoMatch;
1527                     possibly_unsatisfied_predicates.push((o.predicate, None));
1528                 }
1529             }
1530
1531             if let ProbeResult::Match = result {
1532                 if let (Some(return_ty), Some(xform_ret_ty)) =
1533                     (self.return_type, probe.xform_ret_ty)
1534                 {
1535                     let xform_ret_ty = self.resolve_vars_if_possible(xform_ret_ty);
1536                     debug!(
1537                         "comparing return_ty {:?} with xform ret ty {:?}",
1538                         return_ty, probe.xform_ret_ty
1539                     );
1540                     if self
1541                         .at(&ObligationCause::dummy(), self.param_env)
1542                         .sup(return_ty, xform_ret_ty)
1543                         .is_err()
1544                     {
1545                         return ProbeResult::BadReturnType;
1546                     }
1547                 }
1548             }
1549
1550             result
1551         })
1552     }
1553
1554     /// Sometimes we get in a situation where we have multiple probes that are all impls of the
1555     /// same trait, but we don't know which impl to use. In this case, since in all cases the
1556     /// external interface of the method can be determined from the trait, it's ok not to decide.
1557     /// We can basically just collapse all of the probes for various impls into one where-clause
1558     /// probe. This will result in a pending obligation so when more type-info is available we can
1559     /// make the final decision.
1560     ///
1561     /// Example (`src/test/ui/method-two-trait-defer-resolution-1.rs`):
1562     ///
1563     /// ```
1564     /// trait Foo { ... }
1565     /// impl Foo for Vec<i32> { ... }
1566     /// impl Foo for Vec<usize> { ... }
1567     /// ```
1568     ///
1569     /// Now imagine the receiver is `Vec<_>`. It doesn't really matter at this time which impl we
1570     /// use, so it's ok to just commit to "using the method from the trait Foo".
1571     fn collapse_candidates_to_trait_pick(
1572         &self,
1573         probes: &[(&Candidate<'tcx>, ProbeResult)],
1574     ) -> Option<Pick<'tcx>> {
1575         // Do all probes correspond to the same trait?
1576         let container = probes[0].0.item.container;
1577         if let ty::ImplContainer(_) = container {
1578             return None;
1579         }
1580         if probes[1..].iter().any(|&(p, _)| p.item.container != container) {
1581             return None;
1582         }
1583
1584         // FIXME: check the return type here somehow.
1585         // If so, just use this trait and call it a day.
1586         Some(Pick {
1587             item: probes[0].0.item,
1588             kind: TraitPick,
1589             import_ids: probes[0].0.import_ids.clone(),
1590             autoderefs: 0,
1591             autoref_or_ptr_adjustment: None,
1592         })
1593     }
1594
1595     /// Similarly to `probe_for_return_type`, this method attempts to find the best matching
1596     /// candidate method where the method name may have been misspelt. Similarly to other
1597     /// Levenshtein based suggestions, we provide at most one such suggestion.
1598     fn probe_for_lev_candidate(&mut self) -> Result<Option<ty::AssocItem>, MethodError<'tcx>> {
1599         debug!("probing for method names similar to {:?}", self.method_name);
1600
1601         let steps = self.steps.clone();
1602         self.probe(|_| {
1603             let mut pcx = ProbeContext::new(
1604                 self.fcx,
1605                 self.span,
1606                 self.mode,
1607                 self.method_name,
1608                 self.return_type,
1609                 self.orig_steps_var_values.clone(),
1610                 steps,
1611                 IsSuggestion(true),
1612                 self.scope_expr_id,
1613             );
1614             pcx.allow_similar_names = true;
1615             pcx.assemble_inherent_candidates();
1616
1617             let method_names = pcx.candidate_method_names();
1618             pcx.allow_similar_names = false;
1619             let applicable_close_candidates: Vec<ty::AssocItem> = method_names
1620                 .iter()
1621                 .filter_map(|&method_name| {
1622                     pcx.reset();
1623                     pcx.method_name = Some(method_name);
1624                     pcx.assemble_inherent_candidates();
1625                     pcx.pick_core().and_then(|pick| pick.ok()).map(|pick| pick.item)
1626                 })
1627                 .collect();
1628
1629             if applicable_close_candidates.is_empty() {
1630                 Ok(None)
1631             } else {
1632                 let best_name = {
1633                     let names = applicable_close_candidates
1634                         .iter()
1635                         .map(|cand| cand.ident.name)
1636                         .collect::<Vec<Symbol>>();
1637                     find_best_match_for_name(&names, self.method_name.unwrap().name, None)
1638                 }
1639                 .unwrap();
1640                 Ok(applicable_close_candidates
1641                     .into_iter()
1642                     .find(|method| method.ident.name == best_name))
1643             }
1644         })
1645     }
1646
1647     ///////////////////////////////////////////////////////////////////////////
1648     // MISCELLANY
1649     fn has_applicable_self(&self, item: &ty::AssocItem) -> bool {
1650         // "Fast track" -- check for usage of sugar when in method call
1651         // mode.
1652         //
1653         // In Path mode (i.e., resolving a value like `T::next`), consider any
1654         // associated value (i.e., methods, constants) but not types.
1655         match self.mode {
1656             Mode::MethodCall => item.fn_has_self_parameter,
1657             Mode::Path => match item.kind {
1658                 ty::AssocKind::Type => false,
1659                 ty::AssocKind::Fn | ty::AssocKind::Const => true,
1660             },
1661         }
1662         // FIXME -- check for types that deref to `Self`,
1663         // like `Rc<Self>` and so on.
1664         //
1665         // Note also that the current code will break if this type
1666         // includes any of the type parameters defined on the method
1667         // -- but this could be overcome.
1668     }
1669
1670     fn record_static_candidate(&mut self, source: CandidateSource) {
1671         self.static_candidates.push(source);
1672     }
1673
1674     fn xform_self_ty(
1675         &self,
1676         item: &ty::AssocItem,
1677         impl_ty: Ty<'tcx>,
1678         substs: SubstsRef<'tcx>,
1679     ) -> (Ty<'tcx>, Option<Ty<'tcx>>) {
1680         if item.kind == ty::AssocKind::Fn && self.mode == Mode::MethodCall {
1681             let sig = self.xform_method_sig(item.def_id, substs);
1682             (sig.inputs()[0], Some(sig.output()))
1683         } else {
1684             (impl_ty, None)
1685         }
1686     }
1687
1688     fn xform_method_sig(&self, method: DefId, substs: SubstsRef<'tcx>) -> ty::FnSig<'tcx> {
1689         let fn_sig = self.tcx.fn_sig(method);
1690         debug!("xform_self_ty(fn_sig={:?}, substs={:?})", fn_sig, substs);
1691
1692         assert!(!substs.has_escaping_bound_vars());
1693
1694         // It is possible for type parameters or early-bound lifetimes
1695         // to appear in the signature of `self`. The substitutions we
1696         // are given do not include type/lifetime parameters for the
1697         // method yet. So create fresh variables here for those too,
1698         // if there are any.
1699         let generics = self.tcx.generics_of(method);
1700         assert_eq!(substs.len(), generics.parent_count as usize);
1701
1702         // Erase any late-bound regions from the method and substitute
1703         // in the values from the substitution.
1704         let xform_fn_sig = self.erase_late_bound_regions(fn_sig);
1705
1706         if generics.params.is_empty() {
1707             xform_fn_sig.subst(self.tcx, substs)
1708         } else {
1709             let substs = InternalSubsts::for_item(self.tcx, method, |param, _| {
1710                 let i = param.index as usize;
1711                 if i < substs.len() {
1712                     substs[i]
1713                 } else {
1714                     match param.kind {
1715                         GenericParamDefKind::Lifetime => {
1716                             // In general, during probe we erase regions.
1717                             self.tcx.lifetimes.re_erased.into()
1718                         }
1719                         GenericParamDefKind::Type { .. } | GenericParamDefKind::Const { .. } => {
1720                             self.var_for_def(self.span, param)
1721                         }
1722                     }
1723                 }
1724             });
1725             xform_fn_sig.subst(self.tcx, substs)
1726         }
1727     }
1728
1729     /// Gets the type of an impl and generate substitutions with placeholders.
1730     fn impl_ty_and_substs(&self, impl_def_id: DefId) -> (Ty<'tcx>, SubstsRef<'tcx>) {
1731         (self.tcx.type_of(impl_def_id), self.fresh_item_substs(impl_def_id))
1732     }
1733
1734     fn fresh_item_substs(&self, def_id: DefId) -> SubstsRef<'tcx> {
1735         InternalSubsts::for_item(self.tcx, def_id, |param, _| match param.kind {
1736             GenericParamDefKind::Lifetime => self.tcx.lifetimes.re_erased.into(),
1737             GenericParamDefKind::Type { .. } => self
1738                 .next_ty_var(TypeVariableOrigin {
1739                     kind: TypeVariableOriginKind::SubstitutionPlaceholder,
1740                     span: self.tcx.def_span(def_id),
1741                 })
1742                 .into(),
1743             GenericParamDefKind::Const { .. } => {
1744                 let span = self.tcx.def_span(def_id);
1745                 let origin = ConstVariableOrigin {
1746                     kind: ConstVariableOriginKind::SubstitutionPlaceholder,
1747                     span,
1748                 };
1749                 self.next_const_var(self.tcx.type_of(param.def_id), origin).into()
1750             }
1751         })
1752     }
1753
1754     /// Replaces late-bound-regions bound by `value` with `'static` using
1755     /// `ty::erase_late_bound_regions`.
1756     ///
1757     /// This is only a reasonable thing to do during the *probe* phase, not the *confirm* phase, of
1758     /// method matching. It is reasonable during the probe phase because we don't consider region
1759     /// relationships at all. Therefore, we can just replace all the region variables with 'static
1760     /// rather than creating fresh region variables. This is nice for two reasons:
1761     ///
1762     /// 1. Because the numbers of the region variables would otherwise be fairly unique to this
1763     ///    particular method call, it winds up creating fewer types overall, which helps for memory
1764     ///    usage. (Admittedly, this is a rather small effect, though measurable.)
1765     ///
1766     /// 2. It makes it easier to deal with higher-ranked trait bounds, because we can replace any
1767     ///    late-bound regions with 'static. Otherwise, if we were going to replace late-bound
1768     ///    regions with actual region variables as is proper, we'd have to ensure that the same
1769     ///    region got replaced with the same variable, which requires a bit more coordination
1770     ///    and/or tracking the substitution and
1771     ///    so forth.
1772     fn erase_late_bound_regions<T>(&self, value: ty::Binder<'tcx, T>) -> T
1773     where
1774         T: TypeFoldable<'tcx>,
1775     {
1776         self.tcx.erase_late_bound_regions(value)
1777     }
1778
1779     /// Finds the method with the appropriate name (or return type, as the case may be). If
1780     /// `allow_similar_names` is set, find methods with close-matching names.
1781     // The length of the returned iterator is nearly always 0 or 1 and this
1782     // method is fairly hot.
1783     fn impl_or_trait_item(&self, def_id: DefId) -> SmallVec<[ty::AssocItem; 1]> {
1784         if let Some(name) = self.method_name {
1785             if self.allow_similar_names {
1786                 let max_dist = max(name.as_str().len(), 3) / 3;
1787                 self.tcx
1788                     .associated_items(def_id)
1789                     .in_definition_order()
1790                     .filter(|x| {
1791                         let dist = lev_distance(&*name.as_str(), &x.ident.as_str());
1792                         x.kind.namespace() == Namespace::ValueNS && dist > 0 && dist <= max_dist
1793                     })
1794                     .copied()
1795                     .collect()
1796             } else {
1797                 self.fcx
1798                     .associated_item(def_id, name, Namespace::ValueNS)
1799                     .map_or_else(SmallVec::new, |x| SmallVec::from_buf([x]))
1800             }
1801         } else {
1802             self.tcx.associated_items(def_id).in_definition_order().copied().collect()
1803         }
1804     }
1805 }
1806
1807 impl<'tcx> Candidate<'tcx> {
1808     fn to_unadjusted_pick(&self) -> Pick<'tcx> {
1809         Pick {
1810             item: self.item,
1811             kind: match self.kind {
1812                 InherentImplCandidate(..) => InherentImplPick,
1813                 ObjectCandidate => ObjectPick,
1814                 TraitCandidate(_) => TraitPick,
1815                 WhereClauseCandidate(ref trait_ref) => {
1816                     // Only trait derived from where-clauses should
1817                     // appear here, so they should not contain any
1818                     // inference variables or other artifacts. This
1819                     // means they are safe to put into the
1820                     // `WhereClausePick`.
1821                     assert!(
1822                         !trait_ref.skip_binder().substs.needs_infer()
1823                             && !trait_ref.skip_binder().substs.has_placeholders()
1824                     );
1825
1826                     WhereClausePick(*trait_ref)
1827                 }
1828             },
1829             import_ids: self.import_ids.clone(),
1830             autoderefs: 0,
1831             autoref_or_ptr_adjustment: None,
1832         }
1833     }
1834 }