src/librustc_typeck/check/method/probe.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use super::MethodError;
  12 use super::NoMatchData;
  13 use super::{CandidateSource, ImplSource, TraitSource};
  14 use super::suggest;
  15
  16 use check;
  17 use check::{FnCtxt, UnresolvedTypeAction};
  18 use middle::def_id::DefId;
  19 use middle::subst;
  20 use middle::subst::Subst;
  21 use middle::traits;
  22 use middle::ty::{self, NoPreference, RegionEscape, Ty, ToPolyTraitRef, TraitRef};
  23 use middle::ty::HasTypeFlags;
  24 use middle::ty::fold::TypeFoldable;
  25 use middle::infer;
  26 use middle::infer::InferCtxt;
  27 use syntax::ast;
  28 use syntax::codemap::{Span, DUMMY_SP};
  29 use rustc_front::hir;
  30 use std::collections::HashSet;
  31 use std::mem;
  32 use std::rc::Rc;
  33
  34 use self::CandidateKind::*;
  35 pub use self::PickKind::*;
  36
  37 struct ProbeContext<'a, 'tcx:'a> {
  38     fcx: &'a FnCtxt<'a, 'tcx>,
  39     span: Span,
  40     mode: Mode,
  41     item_name: ast::Name,
  42     steps: Rc<Vec<CandidateStep<'tcx>>>,
  43     opt_simplified_steps: Option<Vec<ty::fast_reject::SimplifiedType>>,
  44     inherent_candidates: Vec<Candidate<'tcx>>,
  45     extension_candidates: Vec<Candidate<'tcx>>,
  46     impl_dups: HashSet<DefId>,
  47
  48     /// Collects near misses when the candidate functions are missing a `self` keyword and is only
  49     /// used for error reporting
  50     static_candidates: Vec<CandidateSource>,
  51
  52     /// Collects near misses when trait bounds for type parameters are unsatisfied and is only used
  53     /// for error reporting
  54     unsatisfied_predicates: Vec<TraitRef<'tcx>>
  55 }
  56
  57 #[derive(Debug)]
  58 struct CandidateStep<'tcx> {
  59     self_ty: Ty<'tcx>,
  60     autoderefs: usize,
  61     unsize: bool
  62 }
  63
  64 #[derive(Debug)]
  65 struct Candidate<'tcx> {
  66     xform_self_ty: Ty<'tcx>,
  67     item: ty::ImplOrTraitItem<'tcx>,
  68     kind: CandidateKind<'tcx>,
  69 }
  70
  71 #[derive(Debug)]
  72 enum CandidateKind<'tcx> {
  73     InherentImplCandidate(subst::Substs<'tcx>,
  74                           /* Normalize obligations */ Vec<traits::PredicateObligation<'tcx>>),
  75     ExtensionImplCandidate(/* Impl */ DefId, subst::Substs<'tcx>,
  76                            /* Normalize obligations */ Vec<traits::PredicateObligation<'tcx>>),
  77     ObjectCandidate,
  78     TraitCandidate,
  79     WhereClauseCandidate(/* Trait */ ty::PolyTraitRef<'tcx>),
  80 }
  81
  82 #[derive(Debug)]
  83 pub struct Pick<'tcx> {
  84     pub item: ty::ImplOrTraitItem<'tcx>,
  85     pub kind: PickKind<'tcx>,
  86
  87     // Indicates that the source expression should be autoderef'd N times
  88     //
  89     // A = expr | *expr | **expr | ...
  90     pub autoderefs: usize,
  91
  92     // Indicates that an autoref is applied after the optional autoderefs
  93     //
  94     // B = A | &A | &mut A
  95     pub autoref: Option<hir::Mutability>,
  96
  97     // Indicates that the source expression should be "unsized" to a
  98     // target type. This should probably eventually go away in favor
  99     // of just coercing method receivers.
 100     //
 101     // C = B | unsize(B)
 102     pub unsize: Option<Ty<'tcx>>,
 103 }
 104
 105 #[derive(Clone,Debug)]
 106 pub enum PickKind<'tcx> {
 107     InherentImplPick,
 108     ExtensionImplPick(/* Impl */ DefId),
 109     ObjectPick,
 110     TraitPick,
 111     WhereClausePick(/* Trait */ ty::PolyTraitRef<'tcx>),
 112 }
 113
 114 pub type PickResult<'tcx> = Result<Pick<'tcx>, MethodError<'tcx>>;
 115
 116 #[derive(PartialEq, Eq, Copy, Clone, Debug)]
 117 pub enum Mode {
 118     // An expression of the form `receiver.method_name(...)`.
 119     // Autoderefs are performed on `receiver`, lookup is done based on the
 120     // `self` argument  of the method, and static methods aren't considered.
 121     MethodCall,
 122     // An expression of the form `Type::item` or `<T>::item`.
 123     // No autoderefs are performed, lookup is done based on the type each
 124     // implementation is for, and static methods are included.
 125     Path
 126 }
 127
 128 pub fn probe<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 129                        span: Span,
 130                        mode: Mode,
 131                        item_name: ast::Name,
 132                        self_ty: Ty<'tcx>,
 133                        scope_expr_id: ast::NodeId)
 134                        -> PickResult<'tcx>
 135 {
 136     debug!("probe(self_ty={:?}, item_name={}, scope_expr_id={})",
 137            self_ty,
 138            item_name,
 139            scope_expr_id);
 140
 141     // FIXME(#18741) -- right now, creating the steps involves evaluating the
 142     // `*` operator, which registers obligations that then escape into
 143     // the global fulfillment context and thus has global
 144     // side-effects. This is a bit of a pain to refactor. So just let
 145     // it ride, although it's really not great, and in fact could I
 146     // think cause spurious errors. Really though this part should
 147     // take place in the `fcx.infcx().probe` below.
 148     let steps = if mode == Mode::MethodCall {
 149         match create_steps(fcx, span, self_ty) {
 150             Some(steps) => steps,
 151             None =>return Err(MethodError::NoMatch(NoMatchData::new(Vec::new(), Vec::new(),
 152                                                                     Vec::new(), mode))),
 153         }
 154     } else {
 155         vec![CandidateStep {
 156             self_ty: self_ty,
 157             autoderefs: 0,
 158             unsize: false
 159         }]
 160     };
 161
 162     // Create a list of simplified self types, if we can.
 163     let mut simplified_steps = Vec::new();
 164     for step in &steps {
 165         match ty::fast_reject::simplify_type(fcx.tcx(), step.self_ty, true) {
 166             None => { break; }
 167             Some(simplified_type) => { simplified_steps.push(simplified_type); }
 168         }
 169     }
 170     let opt_simplified_steps =
 171         if simplified_steps.len() < steps.len() {
 172             None // failed to convert at least one of the steps
 173         } else {
 174             Some(simplified_steps)
 175         };
 176
 177     debug!("ProbeContext: steps for self_ty={:?} are {:?}",
 178            self_ty,
 179            steps);
 180
 181     // this creates one big transaction so that all type variables etc
 182     // that we create during the probe process are removed later
 183     fcx.infcx().probe(|_| {
 184         let mut probe_cx = ProbeContext::new(fcx,
 185                                              span,
 186                                              mode,
 187                                              item_name,
 188                                              steps,
 189                                              opt_simplified_steps);
 190         probe_cx.assemble_inherent_candidates();
 191         try!(probe_cx.assemble_extension_candidates_for_traits_in_scope(scope_expr_id));
 192         probe_cx.pick()
 193     })
 194 }
 195
 196 fn create_steps<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 197                           span: Span,
 198                           self_ty: Ty<'tcx>)
 199                           -> Option<Vec<CandidateStep<'tcx>>> {
 200     let mut steps = Vec::new();
 201
 202     let (final_ty, dereferences, _) = check::autoderef(fcx,
 203                                                        span,
 204                                                        self_ty,
 205                                                        None,
 206                                                        UnresolvedTypeAction::Error,
 207                                                        NoPreference,
 208                                                        |t, d| {
 209         steps.push(CandidateStep {
 210             self_ty: t,
 211             autoderefs: d,
 212             unsize: false
 213         });
 214         None::<()> // keep iterating until we can't anymore
 215     });
 216
 217     match final_ty.sty {
 218         ty::TyArray(elem_ty, _) => {
 219             steps.push(CandidateStep {
 220                 self_ty: fcx.tcx().mk_slice(elem_ty),
 221                 autoderefs: dereferences,
 222                 unsize: true
 223             });
 224         }
 225         ty::TyError => return None,
 226         _ => (),
 227     }
 228
 229     Some(steps)
 230 }
 231
 232 impl<'a,'tcx> ProbeContext<'a,'tcx> {
 233     fn new(fcx: &'a FnCtxt<'a,'tcx>,
 234            span: Span,
 235            mode: Mode,
 236            item_name: ast::Name,
 237            steps: Vec<CandidateStep<'tcx>>,
 238            opt_simplified_steps: Option<Vec<ty::fast_reject::SimplifiedType>>)
 239            -> ProbeContext<'a,'tcx>
 240     {
 241         ProbeContext {
 242             fcx: fcx,
 243             span: span,
 244             mode: mode,
 245             item_name: item_name,
 246             inherent_candidates: Vec::new(),
 247             extension_candidates: Vec::new(),
 248             impl_dups: HashSet::new(),
 249             steps: Rc::new(steps),
 250             opt_simplified_steps: opt_simplified_steps,
 251             static_candidates: Vec::new(),
 252             unsatisfied_predicates: Vec::new(),
 253         }
 254     }
 255
 256     fn reset(&mut self) {
 257         self.inherent_candidates.clear();
 258         self.extension_candidates.clear();
 259         self.impl_dups.clear();
 260         self.static_candidates.clear();
 261     }
 262
 263     fn tcx(&self) -> &'a ty::ctxt<'tcx> {
 264         self.fcx.tcx()
 265     }
 266
 267     fn infcx(&self) -> &'a InferCtxt<'a, 'tcx> {
 268         self.fcx.infcx()
 269     }
 270
 271     ///////////////////////////////////////////////////////////////////////////
 272     // CANDIDATE ASSEMBLY
 273
 274     fn assemble_inherent_candidates(&mut self) {
 275         let steps = self.steps.clone();
 276         for step in steps.iter() {
 277             self.assemble_probe(step.self_ty);
 278         }
 279     }
 280
 281     fn assemble_probe(&mut self, self_ty: Ty<'tcx>) {
 282         debug!("assemble_probe: self_ty={:?}",
 283                self_ty);
 284
 285         match self_ty.sty {
 286             ty::TyTrait(box ref data) => {
 287                 self.assemble_inherent_candidates_from_object(self_ty, data);
 288                 self.assemble_inherent_impl_candidates_for_type(data.principal_def_id());
 289             }
 290             ty::TyEnum(def, _) |
 291             ty::TyStruct(def, _) => {
 292                 self.assemble_inherent_impl_candidates_for_type(def.did);
 293             }
 294             ty::TyBox(_) => {
 295                 if let Some(box_did) = self.tcx().lang_items.owned_box() {
 296                     self.assemble_inherent_impl_candidates_for_type(box_did);
 297                 }
 298             }
 299             ty::TyParam(p) => {
 300                 self.assemble_inherent_candidates_from_param(self_ty, p);
 301             }
 302             ty::TyChar => {
 303                 let lang_def_id = self.tcx().lang_items.char_impl();
 304                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 305             }
 306             ty::TyStr => {
 307                 let lang_def_id = self.tcx().lang_items.str_impl();
 308                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 309             }
 310             ty::TySlice(_) => {
 311                 let lang_def_id = self.tcx().lang_items.slice_impl();
 312                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 313             }
 314             ty::TyRawPtr(ty::TypeAndMut { ty: _, mutbl: hir::MutImmutable }) => {
 315                 let lang_def_id = self.tcx().lang_items.const_ptr_impl();
 316                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 317             }
 318             ty::TyRawPtr(ty::TypeAndMut { ty: _, mutbl: hir::MutMutable }) => {
 319                 let lang_def_id = self.tcx().lang_items.mut_ptr_impl();
 320                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 321             }
 322             ty::TyInt(ast::TyI8) => {
 323                 let lang_def_id = self.tcx().lang_items.i8_impl();
 324                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 325             }
 326             ty::TyInt(ast::TyI16) => {
 327                 let lang_def_id = self.tcx().lang_items.i16_impl();
 328                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 329             }
 330             ty::TyInt(ast::TyI32) => {
 331                 let lang_def_id = self.tcx().lang_items.i32_impl();
 332                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 333             }
 334             ty::TyInt(ast::TyI64) => {
 335                 let lang_def_id = self.tcx().lang_items.i64_impl();
 336                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 337             }
 338             ty::TyInt(ast::TyIs) => {
 339                 let lang_def_id = self.tcx().lang_items.isize_impl();
 340                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 341             }
 342             ty::TyUint(ast::TyU8) => {
 343                 let lang_def_id = self.tcx().lang_items.u8_impl();
 344                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 345             }
 346             ty::TyUint(ast::TyU16) => {
 347                 let lang_def_id = self.tcx().lang_items.u16_impl();
 348                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 349             }
 350             ty::TyUint(ast::TyU32) => {
 351                 let lang_def_id = self.tcx().lang_items.u32_impl();
 352                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 353             }
 354             ty::TyUint(ast::TyU64) => {
 355                 let lang_def_id = self.tcx().lang_items.u64_impl();
 356                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 357             }
 358             ty::TyUint(ast::TyUs) => {
 359                 let lang_def_id = self.tcx().lang_items.usize_impl();
 360                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 361             }
 362             ty::TyFloat(ast::TyF32) => {
 363                 let lang_def_id = self.tcx().lang_items.f32_impl();
 364                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 365             }
 366             ty::TyFloat(ast::TyF64) => {
 367                 let lang_def_id = self.tcx().lang_items.f64_impl();
 368                 self.assemble_inherent_impl_for_primitive(lang_def_id);
 369             }
 370             _ => {
 371             }
 372         }
 373     }
 374
 375     fn assemble_inherent_impl_for_primitive(&mut self, lang_def_id: Option<DefId>) {
 376         if let Some(impl_def_id) = lang_def_id {
 377             self.tcx().populate_implementations_for_primitive_if_necessary(impl_def_id);
 378
 379             self.assemble_inherent_impl_probe(impl_def_id);
 380         }
 381     }
 382
 383     fn assemble_inherent_impl_candidates_for_type(&mut self, def_id: DefId) {
 384         // Read the inherent implementation candidates for this type from the
 385         // metadata if necessary.
 386         self.tcx().populate_inherent_implementations_for_type_if_necessary(def_id);
 387
 388         if let Some(impl_infos) = self.tcx().inherent_impls.borrow().get(&def_id) {
 389             for &impl_def_id in impl_infos.iter() {
 390                 self.assemble_inherent_impl_probe(impl_def_id);
 391             }
 392         }
 393     }
 394
 395     fn assemble_inherent_impl_probe(&mut self, impl_def_id: DefId) {
 396         if !self.impl_dups.insert(impl_def_id) {
 397             return; // already visited
 398         }
 399
 400         debug!("assemble_inherent_impl_probe {:?}", impl_def_id);
 401
 402         let item = match impl_item(self.tcx(), impl_def_id, self.item_name) {
 403             Some(m) => m,
 404             None => { return; } // No method with correct name on this impl
 405         };
 406
 407         if !self.has_applicable_self(&item) {
 408             // No receiver declared. Not a candidate.
 409             return self.record_static_candidate(ImplSource(impl_def_id));
 410         }
 411
 412         let (impl_ty, impl_substs) = self.impl_ty_and_substs(impl_def_id);
 413         let impl_ty = impl_ty.subst(self.tcx(), &impl_substs);
 414
 415         // Determine the receiver type that the method itself expects.
 416         let xform_self_ty = self.xform_self_ty(&item, impl_ty, &impl_substs);
 417
 418         // We can't use normalize_associated_types_in as it will pollute the
 419         // fcx's fulfillment context after this probe is over.
 420         let cause = traits::ObligationCause::misc(self.span, self.fcx.body_id);
 421         let mut selcx = &mut traits::SelectionContext::new(self.fcx.infcx());
 422         let traits::Normalized { value: xform_self_ty, obligations } =
 423             traits::normalize(selcx, cause, &xform_self_ty);
 424         debug!("assemble_inherent_impl_probe: xform_self_ty = {:?}",
 425                xform_self_ty);
 426
 427         self.inherent_candidates.push(Candidate {
 428             xform_self_ty: xform_self_ty,
 429             item: item,
 430             kind: InherentImplCandidate(impl_substs, obligations)
 431         });
 432     }
 433
 434     fn assemble_inherent_candidates_from_object(&mut self,
 435                                                 self_ty: Ty<'tcx>,
 436                                                 data: &ty::TraitTy<'tcx>) {
 437         debug!("assemble_inherent_candidates_from_object(self_ty={:?})",
 438                self_ty);
 439
 440         // It is illegal to invoke a method on a trait instance that
 441         // refers to the `Self` type. An error will be reported by
 442         // `enforce_object_limitations()` if the method refers to the
 443         // `Self` type anywhere other than the receiver. Here, we use
 444         // a substitution that replaces `Self` with the object type
 445         // itself. Hence, a `&self` method will wind up with an
 446         // argument type like `&Trait`.
 447         let trait_ref = data.principal_trait_ref_with_self_ty(self.tcx(), self_ty);
 448         self.elaborate_bounds(&[trait_ref], |this, new_trait_ref, item| {
 449             let new_trait_ref = this.erase_late_bound_regions(&new_trait_ref);
 450
 451             let xform_self_ty = this.xform_self_ty(&item,
 452                                                    new_trait_ref.self_ty(),
 453                                                    new_trait_ref.substs);
 454
 455             this.inherent_candidates.push(Candidate {
 456                 xform_self_ty: xform_self_ty,
 457                 item: item,
 458                 kind: ObjectCandidate
 459             });
 460         });
 461     }
 462
 463     fn assemble_inherent_candidates_from_param(&mut self,
 464                                                _rcvr_ty: Ty<'tcx>,
 465                                                param_ty: ty::ParamTy) {
 466         // FIXME -- Do we want to commit to this behavior for param bounds?
 467
 468         let bounds: Vec<_> =
 469             self.fcx.inh.infcx.parameter_environment.caller_bounds
 470             .iter()
 471             .filter_map(|predicate| {
 472                 match *predicate {
 473                     ty::Predicate::Trait(ref trait_predicate) => {
 474                         match trait_predicate.0.trait_ref.self_ty().sty {
 475                             ty::TyParam(ref p) if *p == param_ty => {
 476                                 Some(trait_predicate.to_poly_trait_ref())
 477                             }
 478                             _ => None
 479                         }
 480                     }
 481                     ty::Predicate::Equate(..) |
 482                     ty::Predicate::Projection(..) |
 483                     ty::Predicate::RegionOutlives(..) |
 484                     ty::Predicate::WellFormed(..) |
 485                     ty::Predicate::ObjectSafe(..) |
 486                     ty::Predicate::TypeOutlives(..) => {
 487                         None
 488                     }
 489                 }
 490             })
 491             .collect();
 492
 493         self.elaborate_bounds(&bounds, |this, poly_trait_ref, item| {
 494             let trait_ref =
 495                 this.erase_late_bound_regions(&poly_trait_ref);
 496
 497             let xform_self_ty =
 498                 this.xform_self_ty(&item,
 499                                    trait_ref.self_ty(),
 500                                    trait_ref.substs);
 501
 502             if let Some(ref m) = item.as_opt_method() {
 503                 debug!("found match: trait_ref={:?} substs={:?} m={:?}",
 504                        trait_ref,
 505                        trait_ref.substs,
 506                        m);
 507                 assert_eq!(m.generics.types.get_slice(subst::TypeSpace).len(),
 508                            trait_ref.substs.types.get_slice(subst::TypeSpace).len());
 509                 assert_eq!(m.generics.regions.get_slice(subst::TypeSpace).len(),
 510                            trait_ref.substs.regions().get_slice(subst::TypeSpace).len());
 511                 assert_eq!(m.generics.types.get_slice(subst::SelfSpace).len(),
 512                            trait_ref.substs.types.get_slice(subst::SelfSpace).len());
 513                 assert_eq!(m.generics.regions.get_slice(subst::SelfSpace).len(),
 514                            trait_ref.substs.regions().get_slice(subst::SelfSpace).len());
 515             }
 516
 517             // Because this trait derives from a where-clause, it
 518             // should not contain any inference variables or other
 519             // artifacts. This means it is safe to put into the
 520             // `WhereClauseCandidate` and (eventually) into the
 521             // `WhereClausePick`.
 522             assert!(!trait_ref.substs.types.needs_infer());
 523
 524             this.inherent_candidates.push(Candidate {
 525                 xform_self_ty: xform_self_ty,
 526                 item: item,
 527                 kind: WhereClauseCandidate(poly_trait_ref)
 528             });
 529         });
 530     }
 531
 532     // Do a search through a list of bounds, using a callback to actually
 533     // create the candidates.
 534     fn elaborate_bounds<F>(
 535         &mut self,
 536         bounds: &[ty::PolyTraitRef<'tcx>],
 537         mut mk_cand: F,
 538     ) where
 539         F: for<'b> FnMut(
 540             &mut ProbeContext<'b, 'tcx>,
 541             ty::PolyTraitRef<'tcx>,
 542             ty::ImplOrTraitItem<'tcx>,
 543         ),
 544     {
 545         debug!("elaborate_bounds(bounds={:?})", bounds);
 546
 547         let tcx = self.tcx();
 548         for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
 549             let item = match trait_item(tcx,
 550                                         bound_trait_ref.def_id(),
 551                                         self.item_name) {
 552                 Some(v) => v,
 553                 None => { continue; }
 554             };
 555
 556             if !self.has_applicable_self(&item) {
 557                 self.record_static_candidate(TraitSource(bound_trait_ref.def_id()));
 558             } else {
 559                 mk_cand(self, bound_trait_ref, item);
 560             }
 561         }
 562     }
 563
 564     fn assemble_extension_candidates_for_traits_in_scope(&mut self,
 565                                                          expr_id: ast::NodeId)
 566                                                          -> Result<(), MethodError<'tcx>>
 567     {
 568         let mut duplicates = HashSet::new();
 569         let opt_applicable_traits = self.fcx.ccx.trait_map.get(&expr_id);
 570         if let Some(applicable_traits) = opt_applicable_traits {
 571             for &trait_did in applicable_traits {
 572                 if duplicates.insert(trait_did) {
 573                     try!(self.assemble_extension_candidates_for_trait(trait_did));
 574                 }
 575             }
 576         }
 577         Ok(())
 578     }
 579
 580     fn assemble_extension_candidates_for_all_traits(&mut self) -> Result<(), MethodError<'tcx>> {
 581         let mut duplicates = HashSet::new();
 582         for trait_info in suggest::all_traits(self.fcx.ccx) {
 583             if duplicates.insert(trait_info.def_id) {
 584                 try!(self.assemble_extension_candidates_for_trait(trait_info.def_id));
 585             }
 586         }
 587         Ok(())
 588     }
 589
 590     fn assemble_extension_candidates_for_trait(&mut self,
 591                                                trait_def_id: DefId)
 592                                                -> Result<(), MethodError<'tcx>>
 593     {
 594         debug!("assemble_extension_candidates_for_trait(trait_def_id={:?})",
 595                trait_def_id);
 596
 597         // Check whether `trait_def_id` defines a method with suitable name:
 598         let trait_items =
 599             self.tcx().trait_items(trait_def_id);
 600         let maybe_item =
 601             trait_items.iter()
 602                        .find(|item| item.name() == self.item_name);
 603         let item = match maybe_item {
 604             Some(i) => i,
 605             None => { return Ok(()); }
 606         };
 607
 608         // Check whether `trait_def_id` defines a method with suitable name:
 609         if !self.has_applicable_self(item) {
 610             debug!("method has inapplicable self");
 611             self.record_static_candidate(TraitSource(trait_def_id));
 612             return Ok(());
 613         }
 614
 615         self.assemble_extension_candidates_for_trait_impls(trait_def_id, item.clone());
 616
 617         try!(self.assemble_closure_candidates(trait_def_id, item.clone()));
 618
 619         self.assemble_projection_candidates(trait_def_id, item.clone());
 620
 621         self.assemble_where_clause_candidates(trait_def_id, item.clone());
 622
 623         Ok(())
 624     }
 625
 626     fn assemble_extension_candidates_for_trait_impls(&mut self,
 627                                                      trait_def_id: DefId,
 628                                                      item: ty::ImplOrTraitItem<'tcx>)
 629     {
 630         let trait_def = self.tcx().lookup_trait_def(trait_def_id);
 631
 632         // FIXME(arielb1): can we use for_each_relevant_impl here?
 633         trait_def.for_each_impl(self.tcx(), |impl_def_id| {
 634             debug!("assemble_extension_candidates_for_trait_impl: trait_def_id={:?} \
 635                                                                   impl_def_id={:?}",
 636                    trait_def_id,
 637                    impl_def_id);
 638
 639             if !self.impl_can_possibly_match(impl_def_id) {
 640                 return;
 641             }
 642
 643             let (_, impl_substs) = self.impl_ty_and_substs(impl_def_id);
 644
 645             debug!("impl_substs={:?}", impl_substs);
 646
 647             let impl_trait_ref =
 648                 self.tcx().impl_trait_ref(impl_def_id)
 649                 .unwrap() // we know this is a trait impl
 650                 .subst(self.tcx(), &impl_substs);
 651
 652             debug!("impl_trait_ref={:?}", impl_trait_ref);
 653
 654             // Determine the receiver type that the method itself expects.
 655             let xform_self_ty =
 656                 self.xform_self_ty(&item,
 657                                    impl_trait_ref.self_ty(),
 658                                    impl_trait_ref.substs);
 659
 660             // Normalize the receiver. We can't use normalize_associated_types_in
 661             // as it will pollute the fcx's fulfillment context after this probe
 662             // is over.
 663             let cause = traits::ObligationCause::misc(self.span, self.fcx.body_id);
 664             let mut selcx = &mut traits::SelectionContext::new(self.fcx.infcx());
 665             let traits::Normalized { value: xform_self_ty, obligations } =
 666                 traits::normalize(selcx, cause, &xform_self_ty);
 667
 668             debug!("xform_self_ty={:?}", xform_self_ty);
 669
 670             self.extension_candidates.push(Candidate {
 671                 xform_self_ty: xform_self_ty,
 672                 item: item.clone(),
 673                 kind: ExtensionImplCandidate(impl_def_id, impl_substs, obligations)
 674             });
 675         });
 676     }
 677
 678     fn impl_can_possibly_match(&self, impl_def_id: DefId) -> bool {
 679         let simplified_steps = match self.opt_simplified_steps {
 680             Some(ref simplified_steps) => simplified_steps,
 681             None => { return true; }
 682         };
 683
 684         let impl_type = self.tcx().lookup_item_type(impl_def_id);
 685         let impl_simplified_type =
 686             match ty::fast_reject::simplify_type(self.tcx(), impl_type.ty, false) {
 687                 Some(simplified_type) => simplified_type,
 688                 None => { return true; }
 689             };
 690
 691         simplified_steps.contains(&impl_simplified_type)
 692     }
 693
 694     fn assemble_closure_candidates(&mut self,
 695                                    trait_def_id: DefId,
 696                                    item: ty::ImplOrTraitItem<'tcx>)
 697                                    -> Result<(), MethodError<'tcx>>
 698     {
 699         // Check if this is one of the Fn,FnMut,FnOnce traits.
 700         let tcx = self.tcx();
 701         let kind = if Some(trait_def_id) == tcx.lang_items.fn_trait() {
 702             ty::FnClosureKind
 703         } else if Some(trait_def_id) == tcx.lang_items.fn_mut_trait() {
 704             ty::FnMutClosureKind
 705         } else if Some(trait_def_id) == tcx.lang_items.fn_once_trait() {
 706             ty::FnOnceClosureKind
 707         } else {
 708             return Ok(());
 709         };
 710
 711         // Check if there is an unboxed-closure self-type in the list of receivers.
 712         // If so, add "synthetic impls".
 713         let steps = self.steps.clone();
 714         for step in steps.iter() {
 715             let closure_def_id = match step.self_ty.sty {
 716                 ty::TyClosure(a, _) => a,
 717                 _ => continue,
 718             };
 719
 720             let closure_kinds = &self.fcx.inh.tables.borrow().closure_kinds;
 721             let closure_kind = match closure_kinds.get(&closure_def_id) {
 722                 Some(&k) => k,
 723                 None => {
 724                     return Err(MethodError::ClosureAmbiguity(trait_def_id));
 725                 }
 726             };
 727
 728             // this closure doesn't implement the right kind of `Fn` trait
 729             if !closure_kind.extends(kind) {
 730                 continue;
 731             }
 732
 733             // create some substitutions for the argument/return type;
 734             // for the purposes of our method lookup, we only take
 735             // receiver type into account, so we can just substitute
 736             // fresh types here to use during substitution and subtyping.
 737             let trait_def = self.tcx().lookup_trait_def(trait_def_id);
 738             let substs = self.infcx().fresh_substs_for_trait(self.span,
 739                                                              &trait_def.generics,
 740                                                              step.self_ty);
 741
 742             let xform_self_ty = self.xform_self_ty(&item,
 743                                                    step.self_ty,
 744                                                    &substs);
 745             self.inherent_candidates.push(Candidate {
 746                 xform_self_ty: xform_self_ty,
 747                 item: item.clone(),
 748                 kind: TraitCandidate
 749             });
 750         }
 751
 752         Ok(())
 753     }
 754
 755     fn assemble_projection_candidates(&mut self,
 756                                       trait_def_id: DefId,
 757                                       item: ty::ImplOrTraitItem<'tcx>)
 758     {
 759         debug!("assemble_projection_candidates(\
 760                trait_def_id={:?}, \
 761                item={:?})",
 762                trait_def_id,
 763                item);
 764
 765         for step in self.steps.iter() {
 766             debug!("assemble_projection_candidates: step={:?}",
 767                    step);
 768
 769             let projection_trait_ref = match step.self_ty.sty {
 770                 ty::TyProjection(ref data) => &data.trait_ref,
 771                 _ => continue,
 772             };
 773
 774             debug!("assemble_projection_candidates: projection_trait_ref={:?}",
 775                    projection_trait_ref);
 776
 777             let trait_predicates = self.tcx().lookup_predicates(projection_trait_ref.def_id);
 778             let bounds = trait_predicates.instantiate(self.tcx(), projection_trait_ref.substs);
 779             let predicates = bounds.predicates.into_vec();
 780             debug!("assemble_projection_candidates: predicates={:?}",
 781                    predicates);
 782             for poly_bound in
 783                 traits::elaborate_predicates(self.tcx(), predicates)
 784                 .filter_map(|p| p.to_opt_poly_trait_ref())
 785                 .filter(|b| b.def_id() == trait_def_id)
 786             {
 787                 let bound = self.erase_late_bound_regions(&poly_bound);
 788
 789                 debug!("assemble_projection_candidates: projection_trait_ref={:?} bound={:?}",
 790                        projection_trait_ref,
 791                        bound);
 792
 793                 if self.infcx().can_equate(&step.self_ty, &bound.self_ty()).is_ok() {
 794                     let xform_self_ty = self.xform_self_ty(&item,
 795                                                            bound.self_ty(),
 796                                                            bound.substs);
 797
 798                     debug!("assemble_projection_candidates: bound={:?} xform_self_ty={:?}",
 799                            bound,
 800                            xform_self_ty);
 801
 802                     self.extension_candidates.push(Candidate {
 803                         xform_self_ty: xform_self_ty,
 804                         item: item.clone(),
 805                         kind: TraitCandidate
 806                     });
 807                 }
 808             }
 809         }
 810     }
 811
 812     fn assemble_where_clause_candidates(&mut self,
 813                                         trait_def_id: DefId,
 814                                         item: ty::ImplOrTraitItem<'tcx>)
 815     {
 816         debug!("assemble_where_clause_candidates(trait_def_id={:?})",
 817                trait_def_id);
 818
 819         let caller_predicates = self.fcx.inh.infcx.parameter_environment.caller_bounds.clone();
 820         for poly_bound in traits::elaborate_predicates(self.tcx(), caller_predicates)
 821                           .filter_map(|p| p.to_opt_poly_trait_ref())
 822                           .filter(|b| b.def_id() == trait_def_id)
 823         {
 824             let bound = self.erase_late_bound_regions(&poly_bound);
 825             let xform_self_ty = self.xform_self_ty(&item,
 826                                                    bound.self_ty(),
 827                                                    bound.substs);
 828
 829             debug!("assemble_where_clause_candidates: bound={:?} xform_self_ty={:?}",
 830                    bound,
 831                    xform_self_ty);
 832
 833             self.extension_candidates.push(Candidate {
 834                 xform_self_ty: xform_self_ty,
 835                 item: item.clone(),
 836                 kind: WhereClauseCandidate(poly_bound)
 837             });
 838         }
 839     }
 840
 841     ///////////////////////////////////////////////////////////////////////////
 842     // THE ACTUAL SEARCH
 843
 844     fn pick(mut self) -> PickResult<'tcx> {
 845         match self.pick_core() {
 846             Some(r) => return r,
 847             None => {}
 848         }
 849
 850         let static_candidates = mem::replace(&mut self.static_candidates, vec![]);
 851         let unsatisfied_predicates = mem::replace(&mut self.unsatisfied_predicates, vec![]);
 852
 853         // things failed, so lets look at all traits, for diagnostic purposes now:
 854         self.reset();
 855
 856         let span = self.span;
 857         let tcx = self.tcx();
 858
 859         try!(self.assemble_extension_candidates_for_all_traits());
 860
 861         let out_of_scope_traits = match self.pick_core() {
 862             Some(Ok(p)) => vec![p.item.container().id()],
 863             Some(Err(MethodError::Ambiguity(v))) => v.into_iter().map(|source| {
 864                 match source {
 865                     TraitSource(id) => id,
 866                     ImplSource(impl_id) => {
 867                         match tcx.trait_id_of_impl(impl_id) {
 868                             Some(id) => id,
 869                             None =>
 870                                 tcx.sess.span_bug(span,
 871                                                   "found inherent method when looking at traits")
 872                         }
 873                     }
 874                 }
 875             }).collect(),
 876             Some(Err(MethodError::NoMatch(NoMatchData { out_of_scope_traits: others, .. }))) => {
 877                 assert!(others.is_empty());
 878                 vec![]
 879             }
 880             Some(Err(MethodError::ClosureAmbiguity(..))) => {
 881                 // this error only occurs when assembling candidates
 882                 tcx.sess.span_bug(span, "encountered ClosureAmbiguity from pick_core");
 883             }
 884             None => vec![],
 885         };
 886
 887         Err(MethodError::NoMatch(NoMatchData::new(static_candidates, unsatisfied_predicates,
 888                                                   out_of_scope_traits, self.mode)))
 889     }
 890
 891     fn pick_core(&mut self) -> Option<PickResult<'tcx>> {
 892         let steps = self.steps.clone();
 893
 894         // find the first step that works
 895         steps.iter().filter_map(|step| self.pick_step(step)).next()
 896     }
 897
 898     fn pick_step(&mut self, step: &CandidateStep<'tcx>) -> Option<PickResult<'tcx>> {
 899         debug!("pick_step: step={:?}", step);
 900
 901         if step.self_ty.references_error() {
 902             return None;
 903         }
 904
 905         match self.pick_by_value_method(step) {
 906             Some(result) => return Some(result),
 907             None => {}
 908         }
 909
 910         self.pick_autorefd_method(step)
 911     }
 912
 913     fn pick_by_value_method(&mut self,
 914                             step: &CandidateStep<'tcx>)
 915                             -> Option<PickResult<'tcx>>
 916     {
 917         /*!
 918          * For each type `T` in the step list, this attempts to find a
 919          * method where the (transformed) self type is exactly `T`. We
 920          * do however do one transformation on the adjustment: if we
 921          * are passing a region pointer in, we will potentially
 922          * *reborrow* it to a shorter lifetime. This allows us to
 923          * transparently pass `&mut` pointers, in particular, without
 924          * consuming them for their entire lifetime.
 925          */
 926
 927         if step.unsize {
 928             return None;
 929         }
 930
 931         self.pick_method(step.self_ty).map(|r| r.map(|mut pick| {
 932             pick.autoderefs = step.autoderefs;
 933
 934             // Insert a `&*` or `&mut *` if this is a reference type:
 935             if let ty::TyRef(_, mt) = step.self_ty.sty {
 936                 pick.autoderefs += 1;
 937                 pick.autoref = Some(mt.mutbl);
 938             }
 939
 940             pick
 941         }))
 942     }
 943
 944     fn pick_autorefd_method(&mut self,
 945                             step: &CandidateStep<'tcx>)
 946                             -> Option<PickResult<'tcx>>
 947     {
 948         let tcx = self.tcx();
 949
 950         // In general, during probing we erase regions. See
 951         // `impl_self_ty()` for an explanation.
 952         let region = tcx.mk_region(ty::ReStatic);
 953
 954         // Search through mutabilities in order to find one where pick works:
 955         [hir::MutImmutable, hir::MutMutable].iter().filter_map(|&m| {
 956             let autoref_ty = tcx.mk_ref(region, ty::TypeAndMut {
 957                 ty: step.self_ty,
 958                 mutbl: m
 959             });
 960             self.pick_method(autoref_ty).map(|r| r.map(|mut pick| {
 961                 pick.autoderefs = step.autoderefs;
 962                 pick.autoref = Some(m);
 963                 pick.unsize = if step.unsize {
 964                     Some(step.self_ty)
 965                 } else {
 966                     None
 967                 };
 968                 pick
 969             }))
 970         }).nth(0)
 971     }
 972
 973     fn pick_method(&mut self, self_ty: Ty<'tcx>) -> Option<PickResult<'tcx>> {
 974         debug!("pick_method(self_ty={})", self.infcx().ty_to_string(self_ty));
 975
 976         let mut possibly_unsatisfied_predicates = Vec::new();
 977
 978         debug!("searching inherent candidates");
 979         match self.consider_candidates(self_ty, &self.inherent_candidates,
 980                                        &mut possibly_unsatisfied_predicates) {
 981             None => {}
 982             Some(pick) => {
 983                 return Some(pick);
 984             }
 985         }
 986
 987         debug!("searching extension candidates");
 988         let res = self.consider_candidates(self_ty, &self.extension_candidates,
 989                                            &mut possibly_unsatisfied_predicates);
 990         if let None = res {
 991             self.unsatisfied_predicates.extend(possibly_unsatisfied_predicates);
 992         }
 993         res
 994     }
 995
 996     fn consider_candidates(&self,
 997                            self_ty: Ty<'tcx>,
 998                            probes: &[Candidate<'tcx>],
 999                            possibly_unsatisfied_predicates: &mut Vec<TraitRef<'tcx>>)
1000                            -> Option<PickResult<'tcx>> {
1001         let mut applicable_candidates: Vec<_> =
1002             probes.iter()
1003                   .filter(|&probe| self.consider_probe(self_ty,
1004                                                        probe,possibly_unsatisfied_predicates))
1005                   .collect();
1006
1007         debug!("applicable_candidates: {:?}", applicable_candidates);
1008
1009         if applicable_candidates.len() > 1 {
1010             match self.collapse_candidates_to_trait_pick(&applicable_candidates[..]) {
1011                 Some(pick) => { return Some(Ok(pick)); }
1012                 None => { }
1013             }
1014         }
1015
1016         if applicable_candidates.len() > 1 {
1017             let sources = probes.iter().map(|p| p.to_source()).collect();
1018             return Some(Err(MethodError::Ambiguity(sources)));
1019         }
1020
1021         applicable_candidates.pop().map(|probe| {
1022             Ok(probe.to_unadjusted_pick())
1023         })
1024     }
1025
1026     fn consider_probe(&self, self_ty: Ty<'tcx>, probe: &Candidate<'tcx>,
1027                       possibly_unsatisfied_predicates: &mut Vec<TraitRef<'tcx>>) -> bool {
1028         debug!("consider_probe: self_ty={:?} probe={:?}",
1029                self_ty,
1030                probe);
1031
1032         self.infcx().probe(|_| {
1033             // First check that the self type can be related.
1034             match self.make_sub_ty(self_ty, probe.xform_self_ty) {
1035                 Ok(()) => { }
1036                 Err(_) => {
1037                     debug!("--> cannot relate self-types");
1038                     return false;
1039                 }
1040             }
1041
1042             // If so, impls may carry other conditions (e.g., where
1043             // clauses) that must be considered. Make sure that those
1044             // match as well (or at least may match, sometimes we
1045             // don't have enough information to fully evaluate).
1046             let (impl_def_id, substs, ref_obligations) = match probe.kind {
1047                 InherentImplCandidate(ref substs, ref ref_obligations) => {
1048                     (probe.item.container().id(), substs, ref_obligations)
1049                 }
1050
1051                 ExtensionImplCandidate(impl_def_id, ref substs, ref ref_obligations) => {
1052                     (impl_def_id, substs, ref_obligations)
1053                 }
1054
1055                 ObjectCandidate(..) |
1056                 TraitCandidate |
1057                 WhereClauseCandidate(..) => {
1058                     // These have no additional conditions to check.
1059                     return true;
1060                 }
1061             };
1062
1063             let selcx = &mut traits::SelectionContext::new(self.infcx());
1064             let cause = traits::ObligationCause::misc(self.span, self.fcx.body_id);
1065
1066             // Check whether the impl imposes obligations we have to worry about.
1067             let impl_bounds = self.tcx().lookup_predicates(impl_def_id);
1068             let impl_bounds = impl_bounds.instantiate(self.tcx(), substs);
1069             let traits::Normalized { value: impl_bounds,
1070                                         obligations: norm_obligations } =
1071                 traits::normalize(selcx, cause.clone(), &impl_bounds);
1072
1073             // Convert the bounds into obligations.
1074             let obligations =
1075                 traits::predicates_for_generics(cause.clone(),
1076                                                 &impl_bounds);
1077             debug!("impl_obligations={:?}", obligations);
1078
1079             // Evaluate those obligations to see if they might possibly hold.
1080             let mut all_true = true;
1081             for o in obligations.iter()
1082                 .chain(norm_obligations.iter())
1083                 .chain(ref_obligations.iter()) {
1084                 if !selcx.evaluate_obligation(o) {
1085                     all_true = false;
1086                     if let &ty::Predicate::Trait(ref pred) = &o.predicate {
1087                         possibly_unsatisfied_predicates.push(pred.0.trait_ref);
1088                     }
1089                 }
1090             }
1091             all_true
1092         })
1093     }
1094
1095     /// Sometimes we get in a situation where we have multiple probes that are all impls of the
1096     /// same trait, but we don't know which impl to use. In this case, since in all cases the
1097     /// external interface of the method can be determined from the trait, it's ok not to decide.
1098     /// We can basically just collapse all of the probes for various impls into one where-clause
1099     /// probe. This will result in a pending obligation so when more type-info is available we can
1100     /// make the final decision.
1101     ///
1102     /// Example (`src/test/run-pass/method-two-trait-defer-resolution-1.rs`):
1103     ///
1104     /// ```
1105     /// trait Foo { ... }
1106     /// impl Foo for Vec<int> { ... }
1107     /// impl Foo for Vec<usize> { ... }
1108     /// ```
1109     ///
1110     /// Now imagine the receiver is `Vec<_>`. It doesn't really matter at this time which impl we
1111     /// use, so it's ok to just commit to "using the method from the trait Foo".
1112     fn collapse_candidates_to_trait_pick(&self,
1113                                          probes: &[&Candidate<'tcx>])
1114                                          -> Option<Pick<'tcx>> {
1115         // Do all probes correspond to the same trait?
1116         let container = probes[0].item.container();
1117         match container {
1118             ty::TraitContainer(_) => {}
1119             ty::ImplContainer(_) => return None
1120         }
1121         if probes[1..].iter().any(|p| p.item.container() != container) {
1122             return None;
1123         }
1124
1125         // If so, just use this trait and call it a day.
1126         Some(Pick {
1127             item: probes[0].item.clone(),
1128             kind: TraitPick,
1129             autoderefs: 0,
1130             autoref: None,
1131             unsize: None
1132         })
1133     }
1134
1135     ///////////////////////////////////////////////////////////////////////////
1136     // MISCELLANY
1137
1138     fn make_sub_ty(&self, sub: Ty<'tcx>, sup: Ty<'tcx>) -> infer::UnitResult<'tcx> {
1139         self.infcx().sub_types(false, infer::Misc(DUMMY_SP), sub, sup)
1140     }
1141
1142     fn has_applicable_self(&self, item: &ty::ImplOrTraitItem) -> bool {
1143         // "fast track" -- check for usage of sugar
1144         match *item {
1145             ty::ImplOrTraitItem::MethodTraitItem(ref method) =>
1146                 match method.explicit_self {
1147                     ty::StaticExplicitSelfCategory => self.mode == Mode::Path,
1148                     ty::ByValueExplicitSelfCategory |
1149                     ty::ByReferenceExplicitSelfCategory(..) |
1150                     ty::ByBoxExplicitSelfCategory => true,
1151                 },
1152             ty::ImplOrTraitItem::ConstTraitItem(..) => self.mode == Mode::Path,
1153             _ => false,
1154         }
1155         // FIXME -- check for types that deref to `Self`,
1156         // like `Rc<Self>` and so on.
1157         //
1158         // Note also that the current code will break if this type
1159         // includes any of the type parameters defined on the method
1160         // -- but this could be overcome.
1161     }
1162
1163     fn record_static_candidate(&mut self, source: CandidateSource) {
1164         self.static_candidates.push(source);
1165     }
1166
1167     fn xform_self_ty(&self,
1168                      item: &ty::ImplOrTraitItem<'tcx>,
1169                      impl_ty: Ty<'tcx>,
1170                      substs: &subst::Substs<'tcx>)
1171                      -> Ty<'tcx>
1172     {
1173         match item.as_opt_method() {
1174             Some(ref method) => self.xform_method_self_ty(method, impl_ty,
1175                                                           substs),
1176             None => impl_ty,
1177         }
1178     }
1179
1180     fn xform_method_self_ty(&self,
1181                             method: &Rc<ty::Method<'tcx>>,
1182                             impl_ty: Ty<'tcx>,
1183                             substs: &subst::Substs<'tcx>)
1184                             -> Ty<'tcx>
1185     {
1186         debug!("xform_self_ty(impl_ty={:?}, self_ty={:?}, substs={:?})",
1187                impl_ty,
1188                method.fty.sig.0.inputs.get(0),
1189                substs);
1190
1191         assert!(!substs.has_escaping_regions());
1192
1193         // It is possible for type parameters or early-bound lifetimes
1194         // to appear in the signature of `self`. The substitutions we
1195         // are given do not include type/lifetime parameters for the
1196         // method yet. So create fresh variables here for those too,
1197         // if there are any.
1198         assert_eq!(substs.types.len(subst::FnSpace), 0);
1199         assert_eq!(substs.regions().len(subst::FnSpace), 0);
1200
1201         if self.mode == Mode::Path {
1202             return impl_ty;
1203         }
1204
1205         let mut placeholder;
1206         let mut substs = substs;
1207         if
1208             !method.generics.types.is_empty_in(subst::FnSpace) ||
1209             !method.generics.regions.is_empty_in(subst::FnSpace)
1210         {
1211             // In general, during probe we erase regions. See
1212             // `impl_self_ty()` for an explanation.
1213             let method_regions =
1214                 method.generics.regions.get_slice(subst::FnSpace)
1215                 .iter()
1216                 .map(|_| ty::ReStatic)
1217                 .collect();
1218
1219             placeholder = (*substs).clone().with_method(Vec::new(), method_regions);
1220
1221             self.infcx().type_vars_for_defs(
1222                 self.span,
1223                 subst::FnSpace,
1224                 &mut placeholder,
1225                 method.generics.types.get_slice(subst::FnSpace));
1226
1227             substs = &placeholder;
1228         }
1229
1230         // Erase any late-bound regions from the method and substitute
1231         // in the values from the substitution.
1232         let xform_self_ty = method.fty.sig.input(0);
1233         let xform_self_ty = self.erase_late_bound_regions(&xform_self_ty);
1234         let xform_self_ty = xform_self_ty.subst(self.tcx(), substs);
1235
1236         xform_self_ty
1237     }
1238
1239     /// Get the type of an impl and generate substitutions with placeholders.
1240     fn impl_ty_and_substs(&self,
1241                           impl_def_id: DefId)
1242                           -> (Ty<'tcx>, subst::Substs<'tcx>)
1243     {
1244         let impl_pty = self.tcx().lookup_item_type(impl_def_id);
1245
1246         let type_vars =
1247             impl_pty.generics.types.map(
1248                 |_| self.infcx().next_ty_var());
1249
1250         let region_placeholders =
1251             impl_pty.generics.regions.map(
1252                 |_| ty::ReStatic); // see erase_late_bound_regions() for an expl of why 'static
1253
1254         let substs = subst::Substs::new(type_vars, region_placeholders);
1255         (impl_pty.ty, substs)
1256     }
1257
1258     /// Replace late-bound-regions bound by `value` with `'static` using
1259     /// `ty::erase_late_bound_regions`.
1260     ///
1261     /// This is only a reasonable thing to do during the *probe* phase, not the *confirm* phase, of
1262     /// method matching. It is reasonable during the probe phase because we don't consider region
1263     /// relationships at all. Therefore, we can just replace all the region variables with 'static
1264     /// rather than creating fresh region variables. This is nice for two reasons:
1265     ///
1266     /// 1. Because the numbers of the region variables would otherwise be fairly unique to this
1267     ///    particular method call, it winds up creating fewer types overall, which helps for memory
1268     ///    usage. (Admittedly, this is a rather small effect, though measureable.)
1269     ///
1270     /// 2. It makes it easier to deal with higher-ranked trait bounds, because we can replace any
1271     ///    late-bound regions with 'static. Otherwise, if we were going to replace late-bound
1272     ///    regions with actual region variables as is proper, we'd have to ensure that the same
1273     ///    region got replaced with the same variable, which requires a bit more coordination
1274     ///    and/or tracking the substitution and
1275     ///    so forth.
1276     fn erase_late_bound_regions<T>(&self, value: &ty::Binder<T>) -> T
1277         where T : TypeFoldable<'tcx>
1278     {
1279         self.tcx().erase_late_bound_regions(value)
1280     }
1281 }
1282
1283 fn impl_item<'tcx>(tcx: &ty::ctxt<'tcx>,
1284                    impl_def_id: DefId,
1285                    item_name: ast::Name)
1286                    -> Option<ty::ImplOrTraitItem<'tcx>>
1287 {
1288     let impl_items = tcx.impl_items.borrow();
1289     let impl_items = impl_items.get(&impl_def_id).unwrap();
1290     impl_items
1291         .iter()
1292         .map(|&did| tcx.impl_or_trait_item(did.def_id()))
1293         .find(|item| item.name() == item_name)
1294 }
1295
1296 /// Find item with name `item_name` defined in `trait_def_id`
1297 /// and return it, or `None`, if no such item.
1298 fn trait_item<'tcx>(tcx: &ty::ctxt<'tcx>,
1299                     trait_def_id: DefId,
1300                     item_name: ast::Name)
1301                     -> Option<ty::ImplOrTraitItem<'tcx>>
1302 {
1303     let trait_items = tcx.trait_items(trait_def_id);
1304     debug!("trait_method; items: {:?}", trait_items);
1305     trait_items.iter()
1306                .find(|item| item.name() == item_name)
1307                .cloned()
1308 }
1309
1310 impl<'tcx> Candidate<'tcx> {
1311     fn to_unadjusted_pick(&self) -> Pick<'tcx> {
1312         Pick {
1313             item: self.item.clone(),
1314             kind: match self.kind {
1315                 InherentImplCandidate(_, _) => InherentImplPick,
1316                 ExtensionImplCandidate(def_id, _, _) => {
1317                     ExtensionImplPick(def_id)
1318                 }
1319                 ObjectCandidate => ObjectPick,
1320                 TraitCandidate => TraitPick,
1321                 WhereClauseCandidate(ref trait_ref) => {
1322                     // Only trait derived from where-clauses should
1323                     // appear here, so they should not contain any
1324                     // inference variables or other artifacts. This
1325                     // means they are safe to put into the
1326                     // `WhereClausePick`.
1327                     assert!(!trait_ref.substs().types.needs_infer());
1328
1329                     WhereClausePick(trait_ref.clone())
1330                 }
1331             },
1332             autoderefs: 0,
1333             autoref: None,
1334             unsize: None
1335         }
1336     }
1337
1338     fn to_source(&self) -> CandidateSource {
1339         match self.kind {
1340             InherentImplCandidate(_, _) => {
1341                 ImplSource(self.item.container().id())
1342             }
1343             ExtensionImplCandidate(def_id, _, _) => ImplSource(def_id),
1344             ObjectCandidate |
1345             TraitCandidate |
1346             WhereClauseCandidate(_) => TraitSource(self.item.container().id()),
1347         }
1348     }
1349 }