src/librustc_typeck/check/method/probe.rs

   1 use super::MethodError;
   2 use super::NoMatchData;
   3 use super::{CandidateSource, ImplSource, TraitSource};
   4 use super::suggest;
   5
   6 use check::autoderef::{self, Autoderef};
   7 use check::FnCtxt;
   8 use hir::def_id::DefId;
   9 use hir::def::Def;
  10 use namespace::Namespace;
  11
  12 use rustc_data_structures::sync::Lrc;
  13 use rustc::hir;
  14 use rustc::lint;
  15 use rustc::session::config::nightly_options;
  16 use rustc::ty::subst::{Subst, Substs};
  17 use rustc::traits::{self, ObligationCause};
  18 use rustc::traits::query::{CanonicalTyGoal};
  19 use rustc::traits::query::method_autoderef::{CandidateStep, MethodAutoderefStepsResult};
  20 use rustc::traits::query::method_autoderef::{MethodAutoderefBadTy};
  21 use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt, ToPolyTraitRef, ToPredicate, TraitRef, TypeFoldable};
  22 use rustc::ty::GenericParamDefKind;
  23 use rustc::infer::type_variable::TypeVariableOrigin;
  24 use rustc::util::nodemap::FxHashSet;
  25 use rustc::infer::{self, InferOk};
  26 use rustc::infer::canonical::{Canonical, QueryResponse};
  27 use rustc::infer::canonical::{OriginalQueryValues};
  28 use rustc::middle::stability;
  29 use syntax::ast;
  30 use syntax::util::lev_distance::{lev_distance, find_best_match_for_name};
  31 use syntax_pos::{DUMMY_SP, Span, symbol::Symbol};
  32 use std::iter;
  33 use std::mem;
  34 use std::ops::Deref;
  35 use std::cmp::max;
  36
  37 use self::CandidateKind::*;
  38 pub use self::PickKind::*;
  39
  40 /// Boolean flag used to indicate if this search is for a suggestion
  41 /// or not. If true, we can allow ambiguity and so forth.
  42 #[derive(Clone, Copy)]
  43 pub struct IsSuggestion(pub bool);
  44
  45 struct ProbeContext<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
  46     fcx: &'a FnCtxt<'a, 'gcx, 'tcx>,
  47     span: Span,
  48     mode: Mode,
  49     method_name: Option<ast::Ident>,
  50     return_type: Option<Ty<'tcx>>,
  51
  52     /// This is the OriginalQueryValues for the steps queries
  53     /// that are answered in steps.
  54     orig_steps_var_values: OriginalQueryValues<'tcx>,
  55     steps: Lrc<Vec<CandidateStep<'gcx>>>,
  56
  57     inherent_candidates: Vec<Candidate<'tcx>>,
  58     extension_candidates: Vec<Candidate<'tcx>>,
  59     impl_dups: FxHashSet<DefId>,
  60
  61     /// Collects near misses when the candidate functions are missing a `self` keyword and is only
  62     /// used for error reporting
  63     static_candidates: Vec<CandidateSource>,
  64
  65     /// When probing for names, include names that are close to the
  66     /// requested name (by Levensthein distance)
  67     allow_similar_names: bool,
  68
  69     /// Some(candidate) if there is a private candidate
  70     private_candidate: Option<Def>,
  71
  72     /// Collects near misses when trait bounds for type parameters are unsatisfied and is only used
  73     /// for error reporting
  74     unsatisfied_predicates: Vec<TraitRef<'tcx>>,
  75
  76     is_suggestion: IsSuggestion,
  77 }
  78
  79 impl<'a, 'gcx, 'tcx> Deref for ProbeContext<'a, 'gcx, 'tcx> {
  80     type Target = FnCtxt<'a, 'gcx, 'tcx>;
  81     fn deref(&self) -> &Self::Target {
  82         &self.fcx
  83     }
  84 }
  85
  86 #[derive(Debug)]
  87 struct Candidate<'tcx> {
  88     xform_self_ty: Ty<'tcx>,
  89     xform_ret_ty: Option<Ty<'tcx>>,
  90     item: ty::AssociatedItem,
  91     kind: CandidateKind<'tcx>,
  92     import_id: Option<ast::NodeId>,
  93 }
  94
  95 #[derive(Debug)]
  96 enum CandidateKind<'tcx> {
  97     InherentImplCandidate(&'tcx Substs<'tcx>,
  98                           // Normalize obligations
  99                           Vec<traits::PredicateObligation<'tcx>>),
 100     ObjectCandidate,
 101     TraitCandidate(ty::TraitRef<'tcx>),
 102     WhereClauseCandidate(// Trait
 103                          ty::PolyTraitRef<'tcx>),
 104 }
 105
 106 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
 107 enum ProbeResult {
 108     NoMatch,
 109     BadReturnType,
 110     Match,
 111 }
 112
 113 #[derive(Debug, PartialEq, Clone)]
 114 pub struct Pick<'tcx> {
 115     pub item: ty::AssociatedItem,
 116     pub kind: PickKind<'tcx>,
 117     pub import_id: Option<ast::NodeId>,
 118
 119     // Indicates that the source expression should be autoderef'd N times
 120     //
 121     // A = expr | *expr | **expr | ...
 122     pub autoderefs: usize,
 123
 124     // Indicates that an autoref is applied after the optional autoderefs
 125     //
 126     // B = A | &A | &mut A
 127     pub autoref: Option<hir::Mutability>,
 128
 129     // Indicates that the source expression should be "unsized" to a
 130     // target type. This should probably eventually go away in favor
 131     // of just coercing method receivers.
 132     //
 133     // C = B | unsize(B)
 134     pub unsize: Option<Ty<'tcx>>,
 135 }
 136
 137 #[derive(Clone, Debug, PartialEq, Eq)]
 138 pub enum PickKind<'tcx> {
 139     InherentImplPick,
 140     ObjectPick,
 141     TraitPick,
 142     WhereClausePick(// Trait
 143                     ty::PolyTraitRef<'tcx>),
 144 }
 145
 146 pub type PickResult<'tcx> = Result<Pick<'tcx>, MethodError<'tcx>>;
 147
 148 #[derive(PartialEq, Eq, Copy, Clone, Debug)]
 149 pub enum Mode {
 150     // An expression of the form `receiver.method_name(...)`.
 151     // Autoderefs are performed on `receiver`, lookup is done based on the
 152     // `self` argument  of the method, and static methods aren't considered.
 153     MethodCall,
 154     // An expression of the form `Type::item` or `<T>::item`.
 155     // No autoderefs are performed, lookup is done based on the type each
 156     // implementation is for, and static methods are included.
 157     Path,
 158 }
 159
 160 #[derive(PartialEq, Eq, Copy, Clone, Debug)]
 161 pub enum ProbeScope {
 162     // Assemble candidates coming only from traits in scope.
 163     TraitsInScope,
 164
 165     // Assemble candidates coming from all traits.
 166     AllTraits,
 167 }
 168
 169 impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 170     /// This is used to offer suggestions to users. It returns methods
 171     /// that could have been called which have the desired return
 172     /// type. Some effort is made to rule out methods that, if called,
 173     /// would result in an error (basically, the same criteria we
 174     /// would use to decide if a method is a plausible fit for
 175     /// ambiguity purposes).
 176     pub fn probe_for_return_type(&self,
 177                                  span: Span,
 178                                  mode: Mode,
 179                                  return_type: Ty<'tcx>,
 180                                  self_ty: Ty<'tcx>,
 181                                  scope_expr_id: ast::NodeId)
 182                                  -> Vec<ty::AssociatedItem> {
 183         debug!("probe(self_ty={:?}, return_type={}, scope_expr_id={})",
 184                self_ty,
 185                return_type,
 186                scope_expr_id);
 187         let method_names =
 188             self.probe_op(span, mode, None, Some(return_type), IsSuggestion(true),
 189                           self_ty, scope_expr_id, ProbeScope::AllTraits,
 190                           |probe_cx| Ok(probe_cx.candidate_method_names()))
 191                 .unwrap_or(vec![]);
 192          method_names
 193              .iter()
 194              .flat_map(|&method_name| {
 195                  self.probe_op(
 196                      span, mode, Some(method_name), Some(return_type),
 197                      IsSuggestion(true), self_ty, scope_expr_id,
 198                      ProbeScope::AllTraits, |probe_cx| probe_cx.pick()
 199                  ).ok().map(|pick| pick.item)
 200              })
 201             .collect()
 202     }
 203
 204     pub fn probe_for_name(&self,
 205                           span: Span,
 206                           mode: Mode,
 207                           item_name: ast::Ident,
 208                           is_suggestion: IsSuggestion,
 209                           self_ty: Ty<'tcx>,
 210                           scope_expr_id: ast::NodeId,
 211                           scope: ProbeScope)
 212                           -> PickResult<'tcx> {
 213         debug!("probe(self_ty={:?}, item_name={}, scope_expr_id={})",
 214                self_ty,
 215                item_name,
 216                scope_expr_id);
 217         self.probe_op(span,
 218                       mode,
 219                       Some(item_name),
 220                       None,
 221                       is_suggestion,
 222                       self_ty,
 223                       scope_expr_id,
 224                       scope,
 225                       |probe_cx| probe_cx.pick())
 226     }
 227
 228     fn probe_op<OP,R>(&'a self,
 229                       span: Span,
 230                       mode: Mode,
 231                       method_name: Option<ast::Ident>,
 232                       return_type: Option<Ty<'tcx>>,
 233                       is_suggestion: IsSuggestion,
 234                       self_ty: Ty<'tcx>,
 235                       scope_expr_id: ast::NodeId,
 236                       scope: ProbeScope,
 237                       op: OP)
 238                       -> Result<R, MethodError<'tcx>>
 239         where OP: FnOnce(ProbeContext<'a, 'gcx, 'tcx>) -> Result<R, MethodError<'tcx>>
 240     {
 241         let mut orig_values = OriginalQueryValues::default();
 242         let param_env_and_self_ty =
 243             self.infcx.canonicalize_query(
 244                 &ParamEnvAnd {
 245                     param_env: self.param_env,
 246                     value: self_ty
 247                 }, &mut orig_values);
 248
 249         let steps = if mode == Mode::MethodCall {
 250             self.tcx.method_autoderef_steps(param_env_and_self_ty)
 251         } else {
 252             self.infcx.probe(|_| {
 253                 // Mode::Path - the deref steps is "trivial". This turns
 254                 // our CanonicalQuery into a "trivial" QueryResponse. This
 255                 // is a bit inefficient, but I don't think that writing
 256                 // special handling for this "trivial case" is a good idea.
 257
 258                 let infcx = &self.infcx;
 259                 let (ParamEnvAnd {
 260                     param_env: _,
 261                     value: self_ty
 262                 }, canonical_inference_vars) =
 263                     infcx.instantiate_canonical_with_fresh_inference_vars(
 264                         span, &param_env_and_self_ty);
 265                 debug!("probe_op: Mode::Path, param_env_and_self_ty={:?} self_ty={:?}",
 266                        param_env_and_self_ty, self_ty);
 267                 MethodAutoderefStepsResult {
 268                     steps: Lrc::new(vec![CandidateStep {
 269                         self_ty: self.make_query_response_ignoring_pending_obligations(
 270                             canonical_inference_vars, self_ty),
 271                         autoderefs: 0,
 272                         from_unsafe_deref: false,
 273                         unsize: false,
 274                     }]),
 275                     opt_bad_ty: None,
 276                     reached_recursion_limit: false
 277                 }
 278             })
 279         };
 280
 281         // If our autoderef loop had reached the recursion limit,
 282         // report an overflow error, but continue going on with
 283         // the truncated autoderef list.
 284         if steps.reached_recursion_limit {
 285             self.probe(|_| {
 286                 let ty = &steps.steps.last().unwrap_or_else(|| {
 287                     span_bug!(span, "reached the recursion limit in 0 steps?")
 288                 }).self_ty;
 289                 let ty = self.probe_instantiate_query_response(span, &orig_values, ty)
 290                     .unwrap_or_else(|_| span_bug!(span, "instantiating {:?} failed?", ty));
 291                 autoderef::report_autoderef_recursion_limit_error(self.tcx, span,
 292                                                                   ty.value);
 293             });
 294         }
 295
 296
 297         // If we encountered an `_` type or an error type during autoderef, this is
 298         // ambiguous.
 299         if let Some(bad_ty) = &steps.opt_bad_ty {
 300             if is_suggestion.0 {
 301                 // Ambiguity was encountered during a suggestion. Just keep going.
 302                 debug!("ProbeContext: encountered ambiguity in suggestion");
 303             } else if bad_ty.reached_raw_pointer && !self.tcx.features().arbitrary_self_types {
 304                 // this case used to be allowed by the compiler,
 305                 // so we do a future-compat lint here for the 2015 edition
 306                 // (see https://github.com/rust-lang/rust/issues/46906)
 307                 if self.tcx.sess.rust_2018() {
 308                     span_err!(self.tcx.sess, span, E0699,
 309                               "the type of this value must be known \
 310                                to call a method on a raw pointer on it");
 311                 } else {
 312                    self.tcx.lint_node(
 313                         lint::builtin::TYVAR_BEHIND_RAW_POINTER,
 314                         scope_expr_id,
 315                         span,
 316                         "type annotations needed");
 317                 }
 318             } else {
 319                 // Encountered a real ambiguity, so abort the lookup. If `ty` is not
 320                 // an `Err`, report the right "type annotations needed" error pointing
 321                 // to it.
 322                 let ty = &bad_ty.ty;
 323                 let ty = self.probe_instantiate_query_response(span, &orig_values, ty)
 324                     .unwrap_or_else(|_| span_bug!(span, "instantiating {:?} failed?", ty));
 325                 let ty = self.structurally_resolved_type(span, ty.value);
 326                 assert_eq!(ty, self.tcx.types.err);
 327                 return Err(MethodError::NoMatch(NoMatchData::new(Vec::new(),
 328                                                                  Vec::new(),
 329                                                                  Vec::new(),
 330                                                                  None,
 331                                                                  mode)));
 332             }
 333         }
 334
 335         debug!("ProbeContext: steps for self_ty={:?} are {:?}",
 336                self_ty,
 337                steps);
 338
 339
 340         // this creates one big transaction so that all type variables etc
 341         // that we create during the probe process are removed later
 342         self.probe(|_| {
 343             let mut probe_cx = ProbeContext::new(
 344                 self, span, mode, method_name, return_type, orig_values,
 345                 steps.steps, is_suggestion,
 346             );
 347
 348             probe_cx.assemble_inherent_candidates();
 349             match scope {
 350                 ProbeScope::TraitsInScope =>
 351                     probe_cx.assemble_extension_candidates_for_traits_in_scope(scope_expr_id)?,
 352                 ProbeScope::AllTraits =>
 353                     probe_cx.assemble_extension_candidates_for_all_traits()?,
 354             };
 355             op(probe_cx)
 356         })
 357     }
 358 }
 359
 360 pub fn provide(providers: &mut ty::query::Providers) {
 361     providers.method_autoderef_steps = method_autoderef_steps;
 362 }
 363
 364 fn method_autoderef_steps<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'gcx>,
 365                                           goal: CanonicalTyGoal<'tcx>)
 366                                           -> MethodAutoderefStepsResult<'gcx>
 367 {
 368     debug!("method_autoderef_steps({:?})", goal);
 369
 370     tcx.infer_ctxt().enter_with_canonical(DUMMY_SP, &goal, |ref infcx, goal, inference_vars| {
 371         let ParamEnvAnd { param_env, value: self_ty } = goal;
 372
 373         let mut autoderef = Autoderef::new(infcx, param_env, ast::DUMMY_NODE_ID, DUMMY_SP, self_ty)
 374             .include_raw_pointers()
 375             .silence_errors();
 376         let mut reached_raw_pointer = false;
 377         let mut steps: Vec<_> = autoderef.by_ref()
 378             .map(|(ty, d)| {
 379                 let step = CandidateStep {
 380                     self_ty: infcx.make_query_response_ignoring_pending_obligations(
 381                         inference_vars.clone(), ty),
 382                     autoderefs: d,
 383                     from_unsafe_deref: reached_raw_pointer,
 384                     unsize: false,
 385                 };
 386                 if let ty::RawPtr(_) = ty.sty {
 387                     // all the subsequent steps will be from_unsafe_deref
 388                     reached_raw_pointer = true;
 389                 }
 390                 step
 391             })
 392             .collect();
 393
 394         let final_ty = autoderef.maybe_ambiguous_final_ty();
 395         let opt_bad_ty = match final_ty.sty {
 396             ty::Infer(ty::TyVar(_)) |
 397             ty::Error => {
 398                 Some(MethodAutoderefBadTy {
 399                     reached_raw_pointer,
 400                     ty: infcx.make_query_response_ignoring_pending_obligations(
 401                         inference_vars, final_ty)
 402                 })
 403             }
 404             ty::Array(elem_ty, _) => {
 405                 let dereferences = steps.len() - 1;
 406
 407                 steps.push(CandidateStep {
 408                     self_ty: infcx.make_query_response_ignoring_pending_obligations(
 409                         inference_vars, infcx.tcx.mk_slice(elem_ty)),
 410                     autoderefs: dereferences,
 411                     // this could be from an unsafe deref if we had
 412                     // a *mut/const [T; N]
 413                     from_unsafe_deref: reached_raw_pointer,
 414                     unsize: true,
 415                 });
 416
 417                 None
 418             }
 419             _ => None
 420         };
 421
 422         debug!("method_autoderef_steps: steps={:?} opt_bad_ty={:?}", steps, opt_bad_ty);
 423
 424         MethodAutoderefStepsResult {
 425             steps: Lrc::new(steps),
 426             opt_bad_ty: opt_bad_ty.map(Lrc::new),
 427             reached_recursion_limit: autoderef.reached_recursion_limit()
 428         }
 429     })
 430 }
 431
 432
 433 impl<'a, 'gcx, 'tcx> ProbeContext<'a, 'gcx, 'tcx> {
 434     fn new(fcx: &'a FnCtxt<'a, 'gcx, 'tcx>,
 435            span: Span,
 436            mode: Mode,
 437            method_name: Option<ast::Ident>,
 438            return_type: Option<Ty<'tcx>>,
 439            orig_steps_var_values: OriginalQueryValues<'tcx>,
 440            steps: Lrc<Vec<CandidateStep<'gcx>>>,
 441            is_suggestion: IsSuggestion)
 442            -> ProbeContext<'a, 'gcx, 'tcx> {
 443         ProbeContext {
 444             fcx,
 445             span,
 446             mode,
 447             method_name,
 448             return_type,
 449             inherent_candidates: Vec::new(),
 450             extension_candidates: Vec::new(),
 451             impl_dups: FxHashSet::default(),
 452             orig_steps_var_values,
 453             steps,
 454             static_candidates: Vec::new(),
 455             allow_similar_names: false,
 456             private_candidate: None,
 457             unsatisfied_predicates: Vec::new(),
 458             is_suggestion,
 459         }
 460     }
 461
 462     fn reset(&mut self) {
 463         self.inherent_candidates.clear();
 464         self.extension_candidates.clear();
 465         self.impl_dups.clear();
 466         self.static_candidates.clear();
 467         self.private_candidate = None;
 468     }
 469
 470     ///////////////////////////////////////////////////////////////////////////
 471     // CANDIDATE ASSEMBLY
 472
 473     fn push_candidate(&mut self,
 474                       candidate: Candidate<'tcx>,
 475                       is_inherent: bool)
 476     {
 477         let is_accessible = if let Some(name) = self.method_name {
 478             let item = candidate.item;
 479             let def_scope = self.tcx.adjust_ident(name, item.container.id(), self.body_id).1;
 480             item.vis.is_accessible_from(def_scope, self.tcx)
 481         } else {
 482             true
 483         };
 484         if is_accessible {
 485             if is_inherent {
 486                 self.inherent_candidates.push(candidate);
 487             } else {
 488                 self.extension_candidates.push(candidate);
 489             }
 490         } else if self.private_candidate.is_none() {
 491             self.private_candidate = Some(candidate.item.def());
 492         }
 493     }
 494
 495     fn assemble_inherent_candidates(&mut self) {
 496         let steps = self.steps.clone();
 497         for step in steps.iter() {
 498             self.assemble_probe(&step.self_ty);
 499         }
 500     }
 501
 502     fn assemble_probe(&mut self, self_ty: &Canonical<'gcx, QueryResponse<'gcx, Ty<'gcx>>>) {
 503         debug!("assemble_probe: self_ty={:?}", self_ty);
 504         let lang_items = self.tcx.lang_items();
 505
 506         match self_ty.value.value.sty {
 507             ty::Dynamic(ref data, ..) => {
 508                 if let Some(p) = data.principal() {
 509                     let InferOk { value: instantiated_self_ty, obligations: _ } =
 510                         self.fcx.probe_instantiate_query_response(
 511                             self.span, &self.orig_steps_var_values, self_ty)
 512                         .unwrap_or_else(|_| {
 513                             span_bug!(self.span, "{:?} was applicable but now isn't?", self_ty)
 514                         });
 515                     self.assemble_inherent_candidates_from_object(instantiated_self_ty);
 516                     self.assemble_inherent_impl_candidates_for_type(p.def_id());
 517                 }
 518             }
 519             ty::Adt(def, _) => {
 520                 self.assemble_inherent_impl_candidates_for_type(def.did);
 521             }
 522             ty::Foreign(did) => {
 523                 self.assemble_inherent_impl_candidates_for_type(did);
 524             }
 525             ty::Param(p) => {
 526                 self.assemble_inherent_candidates_from_param(p);
 527             }
 528             ty::Char => {
 529                 let lang_def_id = lang_items.char_impl();
 530                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 531             }
 532             ty::Str => {
 533                 let lang_def_id = lang_items.str_impl();
 534                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 535
 536                 let lang_def_id = lang_items.str_alloc_impl();
 537                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 538             }
 539             ty::Slice(_) => {
 540                 let lang_def_id = lang_items.slice_impl();
 541                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 542
 543                 let lang_def_id = lang_items.slice_u8_impl();
 544                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 545
 546                 let lang_def_id = lang_items.slice_alloc_impl();
 547                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 548
 549                 let lang_def_id = lang_items.slice_u8_alloc_impl();
 550                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 551             }
 552             ty::RawPtr(ty::TypeAndMut { ty: _, mutbl: hir::MutImmutable }) => {
 553                 let lang_def_id = lang_items.const_ptr_impl();
 554                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 555             }
 556             ty::RawPtr(ty::TypeAndMut { ty: _, mutbl: hir::MutMutable }) => {
 557                 let lang_def_id = lang_items.mut_ptr_impl();
 558                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 559             }
 560             ty::Int(ast::IntTy::I8) => {
 561                 let lang_def_id = lang_items.i8_impl();
 562                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 563             }
 564             ty::Int(ast::IntTy::I16) => {
 565                 let lang_def_id = lang_items.i16_impl();
 566                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 567             }
 568             ty::Int(ast::IntTy::I32) => {
 569                 let lang_def_id = lang_items.i32_impl();
 570                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 571             }
 572             ty::Int(ast::IntTy::I64) => {
 573                 let lang_def_id = lang_items.i64_impl();
 574                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 575             }
 576             ty::Int(ast::IntTy::I128) => {
 577                 let lang_def_id = lang_items.i128_impl();
 578                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 579             }
 580             ty::Int(ast::IntTy::Isize) => {
 581                 let lang_def_id = lang_items.isize_impl();
 582                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 583             }
 584             ty::Uint(ast::UintTy::U8) => {
 585                 let lang_def_id = lang_items.u8_impl();
 586                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 587             }
 588             ty::Uint(ast::UintTy::U16) => {
 589                 let lang_def_id = lang_items.u16_impl();
 590                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 591             }
 592             ty::Uint(ast::UintTy::U32) => {
 593                 let lang_def_id = lang_items.u32_impl();
 594                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 595             }
 596             ty::Uint(ast::UintTy::U64) => {
 597                 let lang_def_id = lang_items.u64_impl();
 598                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 599             }
 600             ty::Uint(ast::UintTy::U128) => {
 601                 let lang_def_id = lang_items.u128_impl();
 602                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 603             }
 604             ty::Uint(ast::UintTy::Usize) => {
 605                 let lang_def_id = lang_items.usize_impl();
 606                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 607             }
 608             ty::Float(ast::FloatTy::F32) => {
 609                 let lang_def_id = lang_items.f32_impl();
 610                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 611
 612                 let lang_def_id = lang_items.f32_runtime_impl();
 613                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 614             }
 615             ty::Float(ast::FloatTy::F64) => {
 616                 let lang_def_id = lang_items.f64_impl();
 617                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 618
 619                 let lang_def_id = lang_items.f64_runtime_impl();
 620                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 621             }
 622             _ => {}
 623         }
 624     }
 625
 626     fn assemble_inherent_impl_for_primitive(&mut self, lang_def_id: Option<DefId>) {
 627         if let Some(impl_def_id) = lang_def_id {
 628             self.assemble_inherent_impl_probe(impl_def_id);
 629         }
 630     }
 631
 632     fn assemble_inherent_impl_candidates_for_type(&mut self, def_id: DefId) {
 633         let impl_def_ids = self.tcx.at(self.span).inherent_impls(def_id);
 634         for &impl_def_id in impl_def_ids.iter() {
 635             self.assemble_inherent_impl_probe(impl_def_id);
 636         }
 637     }
 638
 639     fn assemble_inherent_impl_probe(&mut self, impl_def_id: DefId) {
 640         if !self.impl_dups.insert(impl_def_id) {
 641             return; // already visited
 642         }
 643
 644         debug!("assemble_inherent_impl_probe {:?}", impl_def_id);
 645
 646         for item in self.impl_or_trait_item(impl_def_id) {
 647             if !self.has_applicable_self(&item) {
 648                 // No receiver declared. Not a candidate.
 649                 self.record_static_candidate(ImplSource(impl_def_id));
 650                 continue
 651             }
 652
 653             let (impl_ty, impl_substs) = self.impl_ty_and_substs(impl_def_id);
 654             let impl_ty = impl_ty.subst(self.tcx, impl_substs);
 655
 656             // Determine the receiver type that the method itself expects.
 657             let xform_tys = self.xform_self_ty(&item, impl_ty, impl_substs);
 658
 659             // We can't use normalize_associated_types_in as it will pollute the
 660             // fcx's fulfillment context after this probe is over.
 661             let cause = traits::ObligationCause::misc(self.span, self.body_id);
 662             let selcx = &mut traits::SelectionContext::new(self.fcx);
 663             let traits::Normalized { value: (xform_self_ty, xform_ret_ty), obligations } =
 664                 traits::normalize(selcx, self.param_env, cause, &xform_tys);
 665             debug!("assemble_inherent_impl_probe: xform_self_ty = {:?}/{:?}",
 666                    xform_self_ty, xform_ret_ty);
 667
 668             self.push_candidate(Candidate {
 669                 xform_self_ty, xform_ret_ty, item,
 670                 kind: InherentImplCandidate(impl_substs, obligations),
 671                 import_id: None
 672             }, true);
 673         }
 674     }
 675
 676     fn assemble_inherent_candidates_from_object(&mut self,
 677                                                 self_ty: Ty<'tcx>) {
 678         debug!("assemble_inherent_candidates_from_object(self_ty={:?})",
 679                self_ty);
 680
 681         let principal = match self_ty.sty {
 682             ty::Dynamic(ref data, ..) => Some(data),
 683             _ => None
 684         }.and_then(|data| data.principal()).unwrap_or_else(|| {
 685             span_bug!(self.span, "non-object {:?} in assemble_inherent_candidates_from_object",
 686                       self_ty)
 687         });
 688
 689         // It is illegal to invoke a method on a trait instance that
 690         // refers to the `Self` type. An error will be reported by
 691         // `enforce_object_limitations()` if the method refers to the
 692         // `Self` type anywhere other than the receiver. Here, we use
 693         // a substitution that replaces `Self` with the object type
 694         // itself. Hence, a `&self` method will wind up with an
 695         // argument type like `&Trait`.
 696         let trait_ref = principal.with_self_ty(self.tcx, self_ty);
 697         self.elaborate_bounds(iter::once(trait_ref), |this, new_trait_ref, item| {
 698             let new_trait_ref = this.erase_late_bound_regions(&new_trait_ref);
 699
 700             let (xform_self_ty, xform_ret_ty) =
 701                 this.xform_self_ty(&item, new_trait_ref.self_ty(), new_trait_ref.substs);
 702             this.push_candidate(Candidate {
 703                 xform_self_ty, xform_ret_ty, item,
 704                 kind: ObjectCandidate,
 705                 import_id: None
 706             }, true);
 707         });
 708     }
 709
 710     fn assemble_inherent_candidates_from_param(&mut self,
 711                                                param_ty: ty::ParamTy) {
 712         // FIXME -- Do we want to commit to this behavior for param bounds?
 713
 714         let bounds = self.param_env
 715             .caller_bounds
 716             .iter()
 717             .filter_map(|predicate| {
 718                 match *predicate {
 719                     ty::Predicate::Trait(ref trait_predicate) => {
 720                         match trait_predicate.skip_binder().trait_ref.self_ty().sty {
 721                             ty::Param(ref p) if *p == param_ty => {
 722                                 Some(trait_predicate.to_poly_trait_ref())
 723                             }
 724                             _ => None,
 725                         }
 726                     }
 727                     ty::Predicate::Subtype(..) |
 728                     ty::Predicate::Projection(..) |
 729                     ty::Predicate::RegionOutlives(..) |
 730                     ty::Predicate::WellFormed(..) |
 731                     ty::Predicate::ObjectSafe(..) |
 732                     ty::Predicate::ClosureKind(..) |
 733                     ty::Predicate::TypeOutlives(..) |
 734                     ty::Predicate::ConstEvaluatable(..) => None,
 735                 }
 736             });
 737
 738         self.elaborate_bounds(bounds, |this, poly_trait_ref, item| {
 739             let trait_ref = this.erase_late_bound_regions(&poly_trait_ref);
 740
 741             let (xform_self_ty, xform_ret_ty) =
 742                 this.xform_self_ty(&item, trait_ref.self_ty(), trait_ref.substs);
 743
 744             // Because this trait derives from a where-clause, it
 745             // should not contain any inference variables or other
 746             // artifacts. This means it is safe to put into the
 747             // `WhereClauseCandidate` and (eventually) into the
 748             // `WhereClausePick`.
 749             assert!(!trait_ref.substs.needs_infer());
 750
 751             this.push_candidate(Candidate {
 752                 xform_self_ty, xform_ret_ty, item,
 753                 kind: WhereClauseCandidate(poly_trait_ref),
 754                 import_id: None
 755             }, true);
 756         });
 757     }
 758
 759     // Do a search through a list of bounds, using a callback to actually
 760     // create the candidates.
 761     fn elaborate_bounds<F>(&mut self,
 762                            bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>,
 763                            mut mk_cand: F)
 764         where F: for<'b> FnMut(&mut ProbeContext<'b, 'gcx, 'tcx>,
 765                                ty::PolyTraitRef<'tcx>,
 766                                ty::AssociatedItem)
 767     {
 768         let tcx = self.tcx;
 769         for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
 770             debug!("elaborate_bounds(bound_trait_ref={:?})", bound_trait_ref);
 771             for item in self.impl_or_trait_item(bound_trait_ref.def_id()) {
 772                 if !self.has_applicable_self(&item) {
 773                     self.record_static_candidate(TraitSource(bound_trait_ref.def_id()));
 774                 } else {
 775                     mk_cand(self, bound_trait_ref, item);
 776                 }
 777             }
 778         }
 779     }
 780
 781     fn assemble_extension_candidates_for_traits_in_scope(&mut self,
 782                                                          expr_id: ast::NodeId)
 783                                                          -> Result<(), MethodError<'tcx>> {
 784         if expr_id == ast::DUMMY_NODE_ID {
 785             return Ok(())
 786         }
 787         let mut duplicates = FxHashSet::default();
 788         let expr_hir_id = self.tcx.hir().node_to_hir_id(expr_id);
 789         let opt_applicable_traits = self.tcx.in_scope_traits(expr_hir_id);
 790         if let Some(applicable_traits) = opt_applicable_traits {
 791             for trait_candidate in applicable_traits.iter() {
 792                 let trait_did = trait_candidate.def_id;
 793                 if duplicates.insert(trait_did) {
 794                     let import_id = trait_candidate.import_id;
 795                     let result = self.assemble_extension_candidates_for_trait(import_id, trait_did);
 796                     result?;
 797                 }
 798             }
 799         }
 800         Ok(())
 801     }
 802
 803     fn assemble_extension_candidates_for_all_traits(&mut self) -> Result<(), MethodError<'tcx>> {
 804         let mut duplicates = FxHashSet::default();
 805         for trait_info in suggest::all_traits(self.tcx) {
 806             if duplicates.insert(trait_info.def_id) {
 807                 self.assemble_extension_candidates_for_trait(None, trait_info.def_id)?;
 808             }
 809         }
 810         Ok(())
 811     }
 812
 813     pub fn matches_return_type(&self,
 814                                method: &ty::AssociatedItem,
 815                                self_ty: Option<Ty<'tcx>>,
 816                                expected: Ty<'tcx>) -> bool {
 817         match method.def() {
 818             Def::Method(def_id) => {
 819                 let fty = self.tcx.fn_sig(def_id);
 820                 self.probe(|_| {
 821                     let substs = self.fresh_substs_for_item(self.span, method.def_id);
 822                     let fty = fty.subst(self.tcx, substs);
 823                     let (fty, _) = self.replace_bound_vars_with_fresh_vars(
 824                         self.span,
 825                         infer::FnCall,
 826                         &fty
 827                     );
 828
 829                     if let Some(self_ty) = self_ty {
 830                         if self.at(&ObligationCause::dummy(), self.param_env)
 831                                .sup(fty.inputs()[0], self_ty)
 832                                .is_err()
 833                         {
 834                             return false
 835                         }
 836                     }
 837                     self.can_sub(self.param_env, fty.output(), expected).is_ok()
 838                 })
 839             }
 840             _ => false,
 841         }
 842     }
 843
 844     fn assemble_extension_candidates_for_trait(&mut self,
 845                                                import_id: Option<ast::NodeId>,
 846                                                trait_def_id: DefId)
 847                                                -> Result<(), MethodError<'tcx>> {
 848         debug!("assemble_extension_candidates_for_trait(trait_def_id={:?})",
 849                trait_def_id);
 850         let trait_substs = self.fresh_item_substs(trait_def_id);
 851         let trait_ref = ty::TraitRef::new(trait_def_id, trait_substs);
 852
 853         for item in self.impl_or_trait_item(trait_def_id) {
 854             // Check whether `trait_def_id` defines a method with suitable name:
 855             if !self.has_applicable_self(&item) {
 856                 debug!("method has inapplicable self");
 857                 self.record_static_candidate(TraitSource(trait_def_id));
 858                 continue;
 859             }
 860
 861             let (xform_self_ty, xform_ret_ty) =
 862                 self.xform_self_ty(&item, trait_ref.self_ty(), trait_substs);
 863             self.push_candidate(Candidate {
 864                 xform_self_ty, xform_ret_ty, item, import_id,
 865                 kind: TraitCandidate(trait_ref),
 866             }, false);
 867         }
 868         Ok(())
 869     }
 870
 871     fn candidate_method_names(&self) -> Vec<ast::Ident> {
 872         let mut set = FxHashSet::default();
 873         let mut names: Vec<_> = self.inherent_candidates
 874             .iter()
 875             .chain(&self.extension_candidates)
 876             .filter(|candidate| {
 877                 if let Some(return_ty) = self.return_type {
 878                     self.matches_return_type(&candidate.item, None, return_ty)
 879                 } else {
 880                     true
 881                 }
 882             })
 883             .map(|candidate| candidate.item.ident)
 884             .filter(|&name| set.insert(name))
 885             .collect();
 886
 887         // sort them by the name so we have a stable result
 888         names.sort_by_cached_key(|n| n.as_str());
 889         names
 890     }
 891
 892     ///////////////////////////////////////////////////////////////////////////
 893     // THE ACTUAL SEARCH
 894
 895     fn pick(mut self) -> PickResult<'tcx> {
 896         assert!(self.method_name.is_some());
 897
 898         if let Some(r) = self.pick_core() {
 899             return r;
 900         }
 901
 902         let static_candidates = mem::replace(&mut self.static_candidates, vec![]);
 903         let private_candidate = self.private_candidate.take();
 904         let unsatisfied_predicates = mem::replace(&mut self.unsatisfied_predicates, vec![]);
 905
 906         // things failed, so lets look at all traits, for diagnostic purposes now:
 907         self.reset();
 908
 909         let span = self.span;
 910         let tcx = self.tcx;
 911
 912         self.assemble_extension_candidates_for_all_traits()?;
 913
 914         let out_of_scope_traits = match self.pick_core() {
 915             Some(Ok(p)) => vec![p.item.container.id()],
 916             //Some(Ok(p)) => p.iter().map(|p| p.item.container().id()).collect(),
 917             Some(Err(MethodError::Ambiguity(v))) => {
 918                 v.into_iter()
 919                     .map(|source| {
 920                         match source {
 921                             TraitSource(id) => id,
 922                             ImplSource(impl_id) => {
 923                                 match tcx.trait_id_of_impl(impl_id) {
 924                                     Some(id) => id,
 925                                     None => {
 926                                         span_bug!(span,
 927                                                   "found inherent method when looking at traits")
 928                                     }
 929                                 }
 930                             }
 931                         }
 932                     })
 933                     .collect()
 934             }
 935             Some(Err(MethodError::NoMatch(NoMatchData { out_of_scope_traits: others, .. }))) => {
 936                 assert!(others.is_empty());
 937                 vec![]
 938             }
 939             _ => vec![],
 940         };
 941
 942         if let Some(def) = private_candidate {
 943             return Err(MethodError::PrivateMatch(def, out_of_scope_traits));
 944         }
 945         let lev_candidate = self.probe_for_lev_candidate()?;
 946
 947         Err(MethodError::NoMatch(NoMatchData::new(static_candidates,
 948                                                   unsatisfied_predicates,
 949                                                   out_of_scope_traits,
 950                                                   lev_candidate,
 951                                                   self.mode)))
 952     }
 953
 954     fn pick_core(&mut self) -> Option<PickResult<'tcx>> {
 955         let steps = self.steps.clone();
 956
 957         // find the first step that works
 958         steps
 959             .iter()
 960             .filter(|step| {
 961                 debug!("pick_core: step={:?}", step);
 962                 // skip types that are from a type error or that would require dereferencing
 963                 // a raw pointer
 964                 !step.self_ty.references_error() && !step.from_unsafe_deref
 965             }).flat_map(|step| {
 966                 let InferOk { value: self_ty, obligations: _ } =
 967                     self.fcx.probe_instantiate_query_response(
 968                         self.span, &self.orig_steps_var_values, &step.self_ty
 969                     ).unwrap_or_else(|_| {
 970                         span_bug!(self.span, "{:?} was applicable but now isn't?", step.self_ty)
 971                     });
 972                 self.pick_by_value_method(step, self_ty).or_else(|| {
 973                 self.pick_autorefd_method(step, self_ty, hir::MutImmutable).or_else(|| {
 974                 self.pick_autorefd_method(step, self_ty, hir::MutMutable)
 975             })})})
 976             .next()
 977     }
 978
 979     fn pick_by_value_method(&mut self, step: &CandidateStep<'gcx>, self_ty: Ty<'tcx>)
 980                             -> Option<PickResult<'tcx>>
 981     {
 982         //! For each type `T` in the step list, this attempts to find a
 983         //! method where the (transformed) self type is exactly `T`. We
 984         //! do however do one transformation on the adjustment: if we
 985         //! are passing a region pointer in, we will potentially
 986         //! *reborrow* it to a shorter lifetime. This allows us to
 987         //! transparently pass `&mut` pointers, in particular, without
 988         //! consuming them for their entire lifetime.
 989
 990         if step.unsize {
 991             return None;
 992         }
 993
 994         self.pick_method(self_ty).map(|r| {
 995             r.map(|mut pick| {
 996                 pick.autoderefs = step.autoderefs;
 997
 998                 // Insert a `&*` or `&mut *` if this is a reference type:
 999                 if let ty::Ref(_, _, mutbl) = step.self_ty.value.value.sty {
1000                     pick.autoderefs += 1;
1001                     pick.autoref = Some(mutbl);
1002                 }
1003
1004                 pick
1005             })
1006         })
1007     }
1008
1009     fn pick_autorefd_method(&mut self,
1010                             step: &CandidateStep<'gcx>,
1011                             self_ty: Ty<'tcx>,
1012                             mutbl: hir::Mutability)
1013                             -> Option<PickResult<'tcx>> {
1014         let tcx = self.tcx;
1015
1016         // In general, during probing we erase regions. See
1017         // `impl_self_ty()` for an explanation.
1018         let region = tcx.types.re_erased;
1019
1020         let autoref_ty = tcx.mk_ref(region,
1021                                     ty::TypeAndMut {
1022                                         ty: self_ty, mutbl
1023                                     });
1024         self.pick_method(autoref_ty).map(|r| {
1025             r.map(|mut pick| {
1026                 pick.autoderefs = step.autoderefs;
1027                 pick.autoref = Some(mutbl);
1028                 pick.unsize = if step.unsize {
1029                     Some(self_ty)
1030                 } else {
1031                     None
1032                 };
1033                 pick
1034             })
1035         })
1036     }
1037
1038     fn pick_method(&mut self, self_ty: Ty<'tcx>) -> Option<PickResult<'tcx>> {
1039         debug!("pick_method(self_ty={})", self.ty_to_string(self_ty));
1040
1041         let mut possibly_unsatisfied_predicates = Vec::new();
1042         let mut unstable_candidates = Vec::new();
1043
1044         for (kind, candidates) in &[
1045             ("inherent", &self.inherent_candidates),
1046             ("extension", &self.extension_candidates),
1047         ] {
1048             debug!("searching {} candidates", kind);
1049             let res = self.consider_candidates(
1050                 self_ty,
1051                 candidates.iter(),
1052                 &mut possibly_unsatisfied_predicates,
1053                 Some(&mut unstable_candidates),
1054             );
1055             if let Some(pick) = res {
1056                 if !self.is_suggestion.0 && !unstable_candidates.is_empty() {
1057                     if let Ok(p) = &pick {
1058                         // Emit a lint if there are unstable candidates alongside the stable ones.
1059                         //
1060                         // We suppress warning if we're picking the method only because it is a
1061                         // suggestion.
1062                         self.emit_unstable_name_collision_hint(p, &unstable_candidates);
1063                     }
1064                 }
1065                 return Some(pick);
1066             }
1067         }
1068
1069         debug!("searching unstable candidates");
1070         let res = self.consider_candidates(
1071             self_ty,
1072             unstable_candidates.into_iter().map(|(c, _)| c),
1073             &mut possibly_unsatisfied_predicates,
1074             None,
1075         );
1076         if res.is_none() {
1077             self.unsatisfied_predicates.extend(possibly_unsatisfied_predicates);
1078         }
1079         res
1080     }
1081
1082     fn consider_candidates<'b, ProbesIter>(
1083         &self,
1084         self_ty: Ty<'tcx>,
1085         probes: ProbesIter,
1086         possibly_unsatisfied_predicates: &mut Vec<TraitRef<'tcx>>,
1087         unstable_candidates: Option<&mut Vec<(&'b Candidate<'tcx>, Symbol)>>,
1088     ) -> Option<PickResult<'tcx>>
1089     where
1090         ProbesIter: Iterator<Item = &'b Candidate<'tcx>> + Clone,
1091     {
1092         let mut applicable_candidates: Vec<_> = probes.clone()
1093             .map(|probe| {
1094                 (probe, self.consider_probe(self_ty, probe, possibly_unsatisfied_predicates))
1095             })
1096             .filter(|&(_, status)| status != ProbeResult::NoMatch)
1097             .collect();
1098
1099         debug!("applicable_candidates: {:?}", applicable_candidates);
1100
1101         if applicable_candidates.len() > 1 {
1102             if let Some(pick) = self.collapse_candidates_to_trait_pick(&applicable_candidates[..]) {
1103                 return Some(Ok(pick));
1104             }
1105         }
1106
1107         if let Some(uc) = unstable_candidates {
1108             applicable_candidates.retain(|&(p, _)| {
1109                 if let stability::EvalResult::Deny { feature, .. } =
1110                     self.tcx.eval_stability(p.item.def_id, None, self.span)
1111                 {
1112                     uc.push((p, feature));
1113                     return false;
1114                 }
1115                 true
1116             });
1117         }
1118
1119         if applicable_candidates.len() > 1 {
1120             let sources = probes
1121                 .map(|p| self.candidate_source(p, self_ty))
1122                 .collect();
1123             return Some(Err(MethodError::Ambiguity(sources)));
1124         }
1125
1126         applicable_candidates.pop().map(|(probe, status)| {
1127             if status == ProbeResult::Match {
1128                 Ok(probe.to_unadjusted_pick())
1129             } else {
1130                 Err(MethodError::BadReturnType)
1131             }
1132         })
1133     }
1134
1135     fn emit_unstable_name_collision_hint(
1136         &self,
1137         stable_pick: &Pick,
1138         unstable_candidates: &[(&Candidate<'tcx>, Symbol)],
1139     ) {
1140         let mut diag = self.tcx.struct_span_lint_node(
1141             lint::builtin::UNSTABLE_NAME_COLLISIONS,
1142             self.fcx.body_id,
1143             self.span,
1144             "a method with this name may be added to the standard library in the future",
1145         );
1146
1147         // FIXME: This should be a `span_suggestion` instead of `help`
1148         // However `self.span` only
1149         // highlights the method name, so we can't use it. Also consider reusing the code from
1150         // `report_method_error()`.
1151         diag.help(&format!(
1152             "call with fully qualified syntax `{}(...)` to keep using the current method",
1153             self.tcx.item_path_str(stable_pick.item.def_id),
1154         ));
1155
1156         if nightly_options::is_nightly_build() {
1157             for (candidate, feature) in unstable_candidates {
1158                 diag.help(&format!(
1159                     "add #![feature({})] to the crate attributes to enable `{}`",
1160                     feature,
1161                     self.tcx.item_path_str(candidate.item.def_id),
1162                 ));
1163             }
1164         }
1165
1166         diag.emit();
1167     }
1168
1169     fn select_trait_candidate(&self, trait_ref: ty::TraitRef<'tcx>)
1170                               -> traits::SelectionResult<'tcx, traits::Selection<'tcx>>
1171     {
1172         let cause = traits::ObligationCause::misc(self.span, self.body_id);
1173         let predicate =
1174             trait_ref.to_poly_trait_ref().to_poly_trait_predicate();
1175         let obligation = traits::Obligation::new(cause, self.param_env, predicate);
1176         traits::SelectionContext::new(self).select(&obligation)
1177     }
1178
1179     fn candidate_source(&self, candidate: &Candidate<'tcx>, self_ty: Ty<'tcx>)
1180                         -> CandidateSource
1181     {
1182         match candidate.kind {
1183             InherentImplCandidate(..) => ImplSource(candidate.item.container.id()),
1184             ObjectCandidate |
1185             WhereClauseCandidate(_) => TraitSource(candidate.item.container.id()),
1186             TraitCandidate(trait_ref) => self.probe(|_| {
1187                 let _ = self.at(&ObligationCause::dummy(), self.param_env)
1188                     .sup(candidate.xform_self_ty, self_ty);
1189                 match self.select_trait_candidate(trait_ref) {
1190                     Ok(Some(traits::Vtable::VtableImpl(ref impl_data))) => {
1191                         // If only a single impl matches, make the error message point
1192                         // to that impl.
1193                         ImplSource(impl_data.impl_def_id)
1194                     }
1195                     _ => {
1196                         TraitSource(candidate.item.container.id())
1197                     }
1198                 }
1199             })
1200         }
1201     }
1202
1203     fn consider_probe(&self,
1204                       self_ty: Ty<'tcx>,
1205                       probe: &Candidate<'tcx>,
1206                       possibly_unsatisfied_predicates: &mut Vec<TraitRef<'tcx>>)
1207                       -> ProbeResult {
1208         debug!("consider_probe: self_ty={:?} probe={:?}", self_ty, probe);
1209
1210         self.probe(|_| {
1211             // First check that the self type can be related.
1212             let sub_obligations = match self.at(&ObligationCause::dummy(), self.param_env)
1213                                             .sup(probe.xform_self_ty, self_ty) {
1214                 Ok(InferOk { obligations, value: () }) => obligations,
1215                 Err(_) => {
1216                     debug!("--> cannot relate self-types");
1217                     return ProbeResult::NoMatch;
1218                 }
1219             };
1220
1221             let mut result = ProbeResult::Match;
1222             let selcx = &mut traits::SelectionContext::new(self);
1223             let cause = traits::ObligationCause::misc(self.span, self.body_id);
1224
1225             // If so, impls may carry other conditions (e.g., where
1226             // clauses) that must be considered. Make sure that those
1227             // match as well (or at least may match, sometimes we
1228             // don't have enough information to fully evaluate).
1229             let candidate_obligations : Vec<_> = match probe.kind {
1230                 InherentImplCandidate(ref substs, ref ref_obligations) => {
1231                     // Check whether the impl imposes obligations we have to worry about.
1232                     let impl_def_id = probe.item.container.id();
1233                     let impl_bounds = self.tcx.predicates_of(impl_def_id);
1234                     let impl_bounds = impl_bounds.instantiate(self.tcx, substs);
1235                     let traits::Normalized { value: impl_bounds, obligations: norm_obligations } =
1236                         traits::normalize(selcx, self.param_env, cause.clone(), &impl_bounds);
1237
1238                     // Convert the bounds into obligations.
1239                     let impl_obligations = traits::predicates_for_generics(
1240                         cause, self.param_env, &impl_bounds);
1241
1242                     debug!("impl_obligations={:?}", impl_obligations);
1243                     impl_obligations.into_iter()
1244                         .chain(norm_obligations.into_iter())
1245                         .chain(ref_obligations.iter().cloned())
1246                         .collect()
1247                 }
1248
1249                 ObjectCandidate |
1250                 WhereClauseCandidate(..) => {
1251                     // These have no additional conditions to check.
1252                     vec![]
1253                 }
1254
1255                 TraitCandidate(trait_ref) => {
1256                     let predicate = trait_ref.to_predicate();
1257                     let obligation =
1258                         traits::Obligation::new(cause, self.param_env, predicate);
1259                     if !self.predicate_may_hold(&obligation) {
1260                         if self.probe(|_| self.select_trait_candidate(trait_ref).is_err()) {
1261                             // This candidate's primary obligation doesn't even
1262                             // select - don't bother registering anything in
1263                             // `potentially_unsatisfied_predicates`.
1264                             return ProbeResult::NoMatch;
1265                         } else {
1266                             // Some nested subobligation of this predicate
1267                             // failed.
1268                             //
1269                             // FIXME: try to find the exact nested subobligation
1270                             // and point at it rather than reporting the entire
1271                             // trait-ref?
1272                             result = ProbeResult::NoMatch;
1273                             let trait_ref = self.resolve_type_vars_if_possible(&trait_ref);
1274                             possibly_unsatisfied_predicates.push(trait_ref);
1275                         }
1276                     }
1277                     vec![]
1278                 }
1279             };
1280
1281             debug!("consider_probe - candidate_obligations={:?} sub_obligations={:?}",
1282                    candidate_obligations, sub_obligations);
1283
1284             // Evaluate those obligations to see if they might possibly hold.
1285             for o in candidate_obligations.into_iter().chain(sub_obligations) {
1286                 let o = self.resolve_type_vars_if_possible(&o);
1287                 if !self.predicate_may_hold(&o) {
1288                     result = ProbeResult::NoMatch;
1289                     if let &ty::Predicate::Trait(ref pred) = &o.predicate {
1290                         possibly_unsatisfied_predicates.push(pred.skip_binder().trait_ref);
1291                     }
1292                 }
1293             }
1294
1295             if let ProbeResult::Match = result {
1296                 if let (Some(return_ty), Some(xform_ret_ty)) =
1297                     (self.return_type, probe.xform_ret_ty)
1298                 {
1299                     let xform_ret_ty = self.resolve_type_vars_if_possible(&xform_ret_ty);
1300                     debug!("comparing return_ty {:?} with xform ret ty {:?}",
1301                            return_ty,
1302                            probe.xform_ret_ty);
1303                     if self.at(&ObligationCause::dummy(), self.param_env)
1304                         .sup(return_ty, xform_ret_ty)
1305                         .is_err()
1306                     {
1307                         return ProbeResult::BadReturnType;
1308                     }
1309                 }
1310             }
1311
1312             result
1313         })
1314     }
1315
1316     /// Sometimes we get in a situation where we have multiple probes that are all impls of the
1317     /// same trait, but we don't know which impl to use. In this case, since in all cases the
1318     /// external interface of the method can be determined from the trait, it's ok not to decide.
1319     /// We can basically just collapse all of the probes for various impls into one where-clause
1320     /// probe. This will result in a pending obligation so when more type-info is available we can
1321     /// make the final decision.
1322     ///
1323     /// Example (`src/test/run-pass/method-two-trait-defer-resolution-1.rs`):
1324     ///
1325     /// ```
1326     /// trait Foo { ... }
1327     /// impl Foo for Vec<int> { ... }
1328     /// impl Foo for Vec<usize> { ... }
1329     /// ```
1330     ///
1331     /// Now imagine the receiver is `Vec<_>`. It doesn't really matter at this time which impl we
1332     /// use, so it's ok to just commit to "using the method from the trait Foo".
1333     fn collapse_candidates_to_trait_pick(&self, probes: &[(&Candidate<'tcx>, ProbeResult)])
1334                                          -> Option<Pick<'tcx>>
1335     {
1336         // Do all probes correspond to the same trait?
1337         let container = probes[0].0.item.container;
1338         if let ty::ImplContainer(_) = container {
1339             return None
1340         }
1341         if probes[1..].iter().any(|&(p, _)| p.item.container != container) {
1342             return None;
1343         }
1344
1345         // FIXME: check the return type here somehow.
1346         // If so, just use this trait and call it a day.
1347         Some(Pick {
1348             item: probes[0].0.item.clone(),
1349             kind: TraitPick,
1350             import_id: probes[0].0.import_id,
1351             autoderefs: 0,
1352             autoref: None,
1353             unsize: None,
1354         })
1355     }
1356
1357     /// Similarly to `probe_for_return_type`, this method attempts to find the best matching
1358     /// candidate method where the method name may have been misspelt. Similarly to other
1359     /// Levenshtein based suggestions, we provide at most one such suggestion.
1360     fn probe_for_lev_candidate(&mut self) -> Result<Option<ty::AssociatedItem>, MethodError<'tcx>> {
1361         debug!("Probing for method names similar to {:?}",
1362                self.method_name);
1363
1364         let steps = self.steps.clone();
1365         self.probe(|_| {
1366             let mut pcx = ProbeContext::new(self.fcx, self.span, self.mode, self.method_name,
1367                                             self.return_type,
1368                                             self.orig_steps_var_values.clone(),
1369                                             steps, IsSuggestion(true));
1370             pcx.allow_similar_names = true;
1371             pcx.assemble_inherent_candidates();
1372             pcx.assemble_extension_candidates_for_traits_in_scope(ast::DUMMY_NODE_ID)?;
1373
1374             let method_names = pcx.candidate_method_names();
1375             pcx.allow_similar_names = false;
1376             let applicable_close_candidates: Vec<ty::AssociatedItem> = method_names
1377                 .iter()
1378                 .filter_map(|&method_name| {
1379                     pcx.reset();
1380                     pcx.method_name = Some(method_name);
1381                     pcx.assemble_inherent_candidates();
1382                     pcx.assemble_extension_candidates_for_traits_in_scope(ast::DUMMY_NODE_ID)
1383                         .ok().map_or(None, |_| {
1384                             pcx.pick_core()
1385                                 .and_then(|pick| pick.ok())
1386                                 .and_then(|pick| Some(pick.item))
1387                         })
1388                 })
1389                .collect();
1390
1391             if applicable_close_candidates.is_empty() {
1392                 Ok(None)
1393             } else {
1394                 let best_name = {
1395                     let names = applicable_close_candidates.iter().map(|cand| &cand.ident.name);
1396                     find_best_match_for_name(names,
1397                                              &self.method_name.unwrap().as_str(),
1398                                              None)
1399                 }.unwrap();
1400                 Ok(applicable_close_candidates
1401                    .into_iter()
1402                    .find(|method| method.ident.name == best_name))
1403             }
1404         })
1405     }
1406
1407     ///////////////////////////////////////////////////////////////////////////
1408     // MISCELLANY
1409     fn has_applicable_self(&self, item: &ty::AssociatedItem) -> bool {
1410         // "Fast track" -- check for usage of sugar when in method call
1411         // mode.
1412         //
1413         // In Path mode (i.e., resolving a value like `T::next`), consider any
1414         // associated value (i.e., methods, constants) but not types.
1415         match self.mode {
1416             Mode::MethodCall => item.method_has_self_argument,
1417             Mode::Path => match item.kind {
1418                 ty::AssociatedKind::Existential |
1419                 ty::AssociatedKind::Type => false,
1420                 ty::AssociatedKind::Method | ty::AssociatedKind::Const => true
1421             },
1422         }
1423         // FIXME -- check for types that deref to `Self`,
1424         // like `Rc<Self>` and so on.
1425         //
1426         // Note also that the current code will break if this type
1427         // includes any of the type parameters defined on the method
1428         // -- but this could be overcome.
1429     }
1430
1431     fn record_static_candidate(&mut self, source: CandidateSource) {
1432         self.static_candidates.push(source);
1433     }
1434
1435     fn xform_self_ty(&self,
1436                      item: &ty::AssociatedItem,
1437                      impl_ty: Ty<'tcx>,
1438                      substs: &Substs<'tcx>)
1439                      -> (Ty<'tcx>, Option<Ty<'tcx>>) {
1440         if item.kind == ty::AssociatedKind::Method && self.mode == Mode::MethodCall {
1441             let sig = self.xform_method_sig(item.def_id, substs);
1442             (sig.inputs()[0], Some(sig.output()))
1443         } else {
1444             (impl_ty, None)
1445         }
1446     }
1447
1448     fn xform_method_sig(&self,
1449                         method: DefId,
1450                         substs: &Substs<'tcx>)
1451                         -> ty::FnSig<'tcx>
1452     {
1453         let fn_sig = self.tcx.fn_sig(method);
1454         debug!("xform_self_ty(fn_sig={:?}, substs={:?})",
1455                fn_sig,
1456                substs);
1457
1458         assert!(!substs.has_escaping_bound_vars());
1459
1460         // It is possible for type parameters or early-bound lifetimes
1461         // to appear in the signature of `self`. The substitutions we
1462         // are given do not include type/lifetime parameters for the
1463         // method yet. So create fresh variables here for those too,
1464         // if there are any.
1465         let generics = self.tcx.generics_of(method);
1466         assert_eq!(substs.len(), generics.parent_count as usize);
1467
1468         // Erase any late-bound regions from the method and substitute
1469         // in the values from the substitution.
1470         let xform_fn_sig = self.erase_late_bound_regions(&fn_sig);
1471
1472         if generics.params.is_empty() {
1473             xform_fn_sig.subst(self.tcx, substs)
1474         } else {
1475             let substs = Substs::for_item(self.tcx, method, |param, _| {
1476                 let i = param.index as usize;
1477                 if i < substs.len() {
1478                     substs[i]
1479                 } else {
1480                     match param.kind {
1481                         GenericParamDefKind::Lifetime => {
1482                             // In general, during probe we erase regions. See
1483                             // `impl_self_ty()` for an explanation.
1484                             self.tcx.types.re_erased.into()
1485                         }
1486                         GenericParamDefKind::Type {..} => self.var_for_def(self.span, param),
1487                     }
1488                 }
1489             });
1490             xform_fn_sig.subst(self.tcx, substs)
1491         }
1492     }
1493
1494     /// Get the type of an impl and generate substitutions with placeholders.
1495     fn impl_ty_and_substs(&self, impl_def_id: DefId) -> (Ty<'tcx>, &'tcx Substs<'tcx>) {
1496         (self.tcx.type_of(impl_def_id), self.fresh_item_substs(impl_def_id))
1497     }
1498
1499     fn fresh_item_substs(&self, def_id: DefId) -> &'tcx Substs<'tcx> {
1500         Substs::for_item(self.tcx, def_id, |param, _| {
1501             match param.kind {
1502                 GenericParamDefKind::Lifetime => self.tcx.types.re_erased.into(),
1503                 GenericParamDefKind::Type {..} => {
1504                     self.next_ty_var(TypeVariableOrigin::SubstitutionPlaceholder(
1505                         self.tcx.def_span(def_id))).into()
1506                 }
1507             }
1508         })
1509     }
1510
1511     /// Replace late-bound-regions bound by `value` with `'static` using
1512     /// `ty::erase_late_bound_regions`.
1513     ///
1514     /// This is only a reasonable thing to do during the *probe* phase, not the *confirm* phase, of
1515     /// method matching. It is reasonable during the probe phase because we don't consider region
1516     /// relationships at all. Therefore, we can just replace all the region variables with 'static
1517     /// rather than creating fresh region variables. This is nice for two reasons:
1518     ///
1519     /// 1. Because the numbers of the region variables would otherwise be fairly unique to this
1520     ///    particular method call, it winds up creating fewer types overall, which helps for memory
1521     ///    usage. (Admittedly, this is a rather small effect, though measurable.)
1522     ///
1523     /// 2. It makes it easier to deal with higher-ranked trait bounds, because we can replace any
1524     ///    late-bound regions with 'static. Otherwise, if we were going to replace late-bound
1525     ///    regions with actual region variables as is proper, we'd have to ensure that the same
1526     ///    region got replaced with the same variable, which requires a bit more coordination
1527     ///    and/or tracking the substitution and
1528     ///    so forth.
1529     fn erase_late_bound_regions<T>(&self, value: &ty::Binder<T>) -> T
1530         where T: TypeFoldable<'tcx>
1531     {
1532         self.tcx.erase_late_bound_regions(value)
1533     }
1534
1535     /// Find the method with the appropriate name (or return type, as the case may be). If
1536     /// `allow_similar_names` is set, find methods with close-matching names.
1537     fn impl_or_trait_item(&self, def_id: DefId) -> Vec<ty::AssociatedItem> {
1538         if let Some(name) = self.method_name {
1539             if self.allow_similar_names {
1540                 let max_dist = max(name.as_str().len(), 3) / 3;
1541                 self.tcx.associated_items(def_id)
1542                     .filter(|x| {
1543                         let dist = lev_distance(&*name.as_str(), &x.ident.as_str());
1544                         Namespace::from(x.kind) == Namespace::Value && dist > 0
1545                             && dist <= max_dist
1546                     })
1547                     .collect()
1548             } else {
1549                 self.fcx
1550                     .associated_item(def_id, name, Namespace::Value)
1551                     .map_or(Vec::new(), |x| vec![x])
1552             }
1553         } else {
1554             self.tcx.associated_items(def_id).collect()
1555         }
1556     }
1557 }
1558
1559 impl<'tcx> Candidate<'tcx> {
1560     fn to_unadjusted_pick(&self) -> Pick<'tcx> {
1561         Pick {
1562             item: self.item.clone(),
1563             kind: match self.kind {
1564                 InherentImplCandidate(..) => InherentImplPick,
1565                 ObjectCandidate => ObjectPick,
1566                 TraitCandidate(_) => TraitPick,
1567                 WhereClauseCandidate(ref trait_ref) => {
1568                     // Only trait derived from where-clauses should
1569                     // appear here, so they should not contain any
1570                     // inference variables or other artifacts. This
1571                     // means they are safe to put into the
1572                     // `WhereClausePick`.
1573                     assert!(
1574                         !trait_ref.skip_binder().substs.needs_infer()
1575                             && !trait_ref.skip_binder().substs.has_placeholders()
1576                     );
1577
1578                     WhereClausePick(trait_ref.clone())
1579                 }
1580             },
1581             import_id: self.import_id,
1582             autoderefs: 0,
1583             autoref: None,
1584             unsize: None,
1585         }
1586     }
1587 }