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,Ambiguity,NoMatch};
  12 use super::MethodIndex;
  13 use super::{CandidateSource,ImplSource,TraitSource};
  14
  15 use check;
  16 use check::{FnCtxt, NoPreference};
  17 use middle::fast_reject;
  18 use middle::subst;
  19 use middle::subst::Subst;
  20 use middle::traits;
  21 use middle::ty::{mod, Ty, ToPolyTraitRef};
  22 use middle::ty_fold::TypeFoldable;
  23 use middle::infer;
  24 use middle::infer::InferCtxt;
  25 use syntax::ast;
  26 use syntax::codemap::{Span, DUMMY_SP};
  27 use std::collections::HashSet;
  28 use std::rc::Rc;
  29 use util::ppaux::Repr;
  30
  31 use self::CandidateKind::*;
  32 pub use self::PickAdjustment::*;
  33 pub use self::PickKind::*;
  34
  35 struct ProbeContext<'a, 'tcx:'a> {
  36     fcx: &'a FnCtxt<'a, 'tcx>,
  37     span: Span,
  38     method_name: ast::Name,
  39     steps: Rc<Vec<CandidateStep<'tcx>>>,
  40     opt_simplified_steps: Option<Vec<fast_reject::SimplifiedType>>,
  41     inherent_candidates: Vec<Candidate<'tcx>>,
  42     extension_candidates: Vec<Candidate<'tcx>>,
  43     impl_dups: HashSet<ast::DefId>,
  44     static_candidates: Vec<CandidateSource>,
  45 }
  46
  47 struct CandidateStep<'tcx> {
  48     self_ty: Ty<'tcx>,
  49     adjustment: PickAdjustment,
  50 }
  51
  52 struct Candidate<'tcx> {
  53     xform_self_ty: Ty<'tcx>,
  54     method_ty: Rc<ty::Method<'tcx>>,
  55     kind: CandidateKind<'tcx>,
  56 }
  57
  58 enum CandidateKind<'tcx> {
  59     InherentImplCandidate(/* Impl */ ast::DefId, subst::Substs<'tcx>),
  60     ObjectCandidate(/* Trait */ ast::DefId, /* method_num */ uint, /* real_index */ uint),
  61     ExtensionImplCandidate(/* Impl */ ast::DefId, Rc<ty::TraitRef<'tcx>>,
  62                            subst::Substs<'tcx>, MethodIndex),
  63     UnboxedClosureCandidate(/* Trait */ ast::DefId, MethodIndex),
  64     WhereClauseCandidate(ty::PolyTraitRef<'tcx>, MethodIndex),
  65 }
  66
  67 pub struct Pick<'tcx> {
  68     pub method_ty: Rc<ty::Method<'tcx>>,
  69     pub adjustment: PickAdjustment,
  70     pub kind: PickKind<'tcx>,
  71 }
  72
  73 #[deriving(Clone,Show)]
  74 pub enum PickKind<'tcx> {
  75     InherentImplPick(/* Impl */ ast::DefId),
  76     ObjectPick(/* Trait */ ast::DefId, /* method_num */ uint, /* real_index */ uint),
  77     ExtensionImplPick(/* Impl */ ast::DefId, MethodIndex),
  78     TraitPick(/* Trait */ ast::DefId, MethodIndex),
  79     WhereClausePick(/* Trait */ ty::PolyTraitRef<'tcx>, MethodIndex),
  80 }
  81
  82 pub type PickResult<'tcx> = Result<Pick<'tcx>, MethodError>;
  83
  84 // This is a kind of "abstracted" version of ty::AutoAdjustment.  The
  85 // difference is that it doesn't embed any regions or other
  86 // specifics. The "confirmation" step recreates those details as
  87 // needed.
  88 #[deriving(Clone,Show)]
  89 pub enum PickAdjustment {
  90     // Indicates that the source expression should be autoderef'd N times
  91     //
  92     // A = expr | *expr | **expr
  93     AutoDeref(uint),
  94
  95     // Indicates that the source expression should be autoderef'd N
  96     // times and then "unsized". This should probably eventually go
  97     // away in favor of just coercing method receivers.
  98     //
  99     // A = unsize(expr | *expr | **expr)
 100     AutoUnsizeLength(/* number of autoderefs */ uint, /* length*/ uint),
 101
 102     // Indicates that an autoref is applied after some number of other adjustments
 103     //
 104     // A = &A | &mut A
 105     AutoRef(ast::Mutability, Box<PickAdjustment>),
 106 }
 107
 108 pub fn probe<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 109                        span: Span,
 110                        method_name: ast::Name,
 111                        self_ty: Ty<'tcx>,
 112                        call_expr_id: ast::NodeId)
 113                        -> PickResult<'tcx>
 114 {
 115     debug!("probe(self_ty={}, method_name={}, call_expr_id={})",
 116            self_ty.repr(fcx.tcx()),
 117            method_name,
 118            call_expr_id);
 119
 120     // FIXME(#18741) -- right now, creating the steps involves evaluating the
 121     // `*` operator, which registers obligations that then escape into
 122     // the global fulfillment context and thus has global
 123     // side-effects. This is a bit of a pain to refactor. So just let
 124     // it ride, although it's really not great, and in fact could I
 125     // think cause spurious errors. Really though this part should
 126     // take place in the `fcx.infcx().probe` below.
 127     let steps = match create_steps(fcx, span, self_ty) {
 128         Some(steps) => steps,
 129         None => return Err(NoMatch(Vec::new())),
 130     };
 131
 132     // Create a list of simplified self types, if we can.
 133     let mut simplified_steps = Vec::new();
 134     for step in steps.iter() {
 135         match fast_reject::simplify_type(fcx.tcx(), step.self_ty, true) {
 136             None => { break; }
 137             Some(simplified_type) => { simplified_steps.push(simplified_type); }
 138         }
 139     }
 140     let opt_simplified_steps =
 141         if simplified_steps.len() < steps.len() {
 142             None // failed to convert at least one of the steps
 143         } else {
 144             Some(simplified_steps)
 145         };
 146
 147     debug!("ProbeContext: steps for self_ty={} are {}",
 148            self_ty.repr(fcx.tcx()),
 149            steps.repr(fcx.tcx()));
 150
 151     // this creates one big transaction so that all type variables etc
 152     // that we create during the probe process are removed later
 153     let mut dummy = Some((steps, opt_simplified_steps)); // FIXME(#18101) need once closures
 154     fcx.infcx().probe(|_| {
 155         let (steps, opt_simplified_steps) = dummy.take().unwrap();
 156         let mut probe_cx = ProbeContext::new(fcx, span, method_name, steps, opt_simplified_steps);
 157         probe_cx.assemble_inherent_candidates();
 158         probe_cx.assemble_extension_candidates_for_traits_in_scope(call_expr_id);
 159         probe_cx.pick()
 160     })
 161 }
 162
 163 fn create_steps<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 164                           span: Span,
 165                           self_ty: Ty<'tcx>)
 166                           -> Option<Vec<CandidateStep<'tcx>>> {
 167     let mut steps = Vec::new();
 168
 169     let (fully_dereferenced_ty, dereferences, _) =
 170         check::autoderef(
 171             fcx, span, self_ty, None, NoPreference,
 172             |t, d| {
 173                 let adjustment = AutoDeref(d);
 174                 steps.push(CandidateStep { self_ty: t, adjustment: adjustment });
 175                 None::<()> // keep iterating until we can't anymore
 176             });
 177
 178     match fully_dereferenced_ty.sty {
 179         ty::ty_vec(elem_ty, Some(len)) => {
 180             steps.push(CandidateStep {
 181                 self_ty: ty::mk_vec(fcx.tcx(), elem_ty, None),
 182                 adjustment: AutoUnsizeLength(dereferences, len),
 183             });
 184         }
 185         ty::ty_err => return None,
 186         _ => (),
 187     }
 188
 189     Some(steps)
 190 }
 191
 192 impl<'a,'tcx> ProbeContext<'a,'tcx> {
 193     fn new(fcx: &'a FnCtxt<'a,'tcx>,
 194            span: Span,
 195            method_name: ast::Name,
 196            steps: Vec<CandidateStep<'tcx>>,
 197            opt_simplified_steps: Option<Vec<fast_reject::SimplifiedType>>)
 198            -> ProbeContext<'a,'tcx>
 199     {
 200         ProbeContext {
 201             fcx: fcx,
 202             span: span,
 203             method_name: method_name,
 204             inherent_candidates: Vec::new(),
 205             extension_candidates: Vec::new(),
 206             impl_dups: HashSet::new(),
 207             steps: Rc::new(steps),
 208             opt_simplified_steps: opt_simplified_steps,
 209             static_candidates: Vec::new(),
 210         }
 211     }
 212
 213     fn tcx(&self) -> &'a ty::ctxt<'tcx> {
 214         self.fcx.tcx()
 215     }
 216
 217     fn infcx(&self) -> &'a InferCtxt<'a, 'tcx> {
 218         self.fcx.infcx()
 219     }
 220
 221     ///////////////////////////////////////////////////////////////////////////
 222     // CANDIDATE ASSEMBLY
 223
 224     fn assemble_inherent_candidates(&mut self) {
 225         let steps = self.steps.clone();
 226         for step in steps.iter() {
 227             self.assemble_probe(step.self_ty);
 228         }
 229     }
 230
 231     fn assemble_probe(&mut self, self_ty: Ty<'tcx>) {
 232         debug!("assemble_probe: self_ty={}",
 233                self_ty.repr(self.tcx()));
 234
 235         match self_ty.sty {
 236             ty::ty_trait(box ref data) => {
 237                 self.assemble_inherent_candidates_from_object(self_ty, data);
 238                 self.assemble_inherent_impl_candidates_for_type(data.principal_def_id());
 239             }
 240             ty::ty_enum(did, _) |
 241             ty::ty_struct(did, _) |
 242             ty::ty_unboxed_closure(did, _, _) => {
 243                 self.assemble_inherent_impl_candidates_for_type(did);
 244             }
 245             ty::ty_param(p) => {
 246                 self.assemble_inherent_candidates_from_param(self_ty, p);
 247             }
 248             _ => {
 249             }
 250         }
 251     }
 252
 253     fn assemble_inherent_impl_candidates_for_type(&mut self, def_id: ast::DefId) {
 254         // Read the inherent implementation candidates for this type from the
 255         // metadata if necessary.
 256         ty::populate_implementations_for_type_if_necessary(self.tcx(), def_id);
 257
 258         for impl_infos in self.tcx().inherent_impls.borrow().get(&def_id).iter() {
 259             for &impl_def_id in impl_infos.iter() {
 260                 self.assemble_inherent_impl_probe(impl_def_id);
 261             }
 262         }
 263     }
 264
 265     fn assemble_inherent_impl_probe(&mut self, impl_def_id: ast::DefId) {
 266         if !self.impl_dups.insert(impl_def_id) {
 267             return; // already visited
 268         }
 269
 270         debug!("assemble_inherent_impl_probe {}", impl_def_id);
 271
 272         let method = match impl_method(self.tcx(), impl_def_id, self.method_name) {
 273             Some(m) => m,
 274             None => { return; } // No method with correct name on this impl
 275         };
 276
 277         if !self.has_applicable_self(&*method) {
 278             // No receiver declared. Not a candidate.
 279             return self.record_static_candidate(ImplSource(impl_def_id));
 280         }
 281
 282         let impl_substs = self.impl_substs(impl_def_id);
 283
 284         // Determine the receiver type that the method itself expects.
 285         let xform_self_ty =
 286             self.xform_self_ty(&method, &impl_substs);
 287
 288         self.inherent_candidates.push(Candidate {
 289             xform_self_ty: xform_self_ty,
 290             method_ty: method,
 291             kind: InherentImplCandidate(impl_def_id, impl_substs)
 292         });
 293     }
 294
 295     fn assemble_inherent_candidates_from_object(&mut self,
 296                                                 self_ty: Ty<'tcx>,
 297                                                 data: &ty::TyTrait<'tcx>) {
 298         debug!("assemble_inherent_candidates_from_object(self_ty={})",
 299                self_ty.repr(self.tcx()));
 300
 301         let tcx = self.tcx();
 302
 303         // It is illegal to invoke a method on a trait instance that
 304         // refers to the `Self` type. An error will be reported by
 305         // `enforce_object_limitations()` if the method refers to the
 306         // `Self` type anywhere other than the receiver. Here, we use
 307         // a substitution that replaces `Self` with the object type
 308         // itself. Hence, a `&self` method will wind up with an
 309         // argument type like `&Trait`.
 310         let trait_ref = data.principal_trait_ref_with_self_ty(self.tcx(), self_ty);
 311         self.elaborate_bounds(&[trait_ref.clone()], false, |this, new_trait_ref, m, method_num| {
 312             let vtable_index =
 313                 traits::get_vtable_index_of_object_method(tcx,
 314                                                           trait_ref.clone(),
 315                                                           new_trait_ref.def_id(),
 316                                                           method_num);
 317
 318             let xform_self_ty = this.xform_self_ty(&m, new_trait_ref.substs());
 319
 320             this.inherent_candidates.push(Candidate {
 321                 xform_self_ty: xform_self_ty,
 322                 method_ty: m,
 323                 kind: ObjectCandidate(new_trait_ref.def_id(), method_num, vtable_index)
 324             });
 325         });
 326     }
 327
 328     fn assemble_inherent_candidates_from_param(&mut self,
 329                                                _rcvr_ty: Ty<'tcx>,
 330                                                param_ty: ty::ParamTy) {
 331         // FIXME -- Do we want to commit to this behavior for param bounds?
 332
 333         let bounds: Vec<_> =
 334             self.fcx.inh.param_env.caller_bounds.predicates
 335             .iter()
 336             .filter_map(|predicate| {
 337                 match *predicate {
 338                     ty::Predicate::Trait(ref trait_predicate) => {
 339                         match trait_predicate.0.trait_ref.self_ty().sty {
 340                             ty::ty_param(ref p) if *p == param_ty => {
 341                                 Some(trait_predicate.to_poly_trait_ref())
 342                             }
 343                             _ => None
 344                         }
 345                     }
 346                     ty::Predicate::Equate(..) |
 347                     ty::Predicate::Projection(..) |
 348                     ty::Predicate::RegionOutlives(..) |
 349                     ty::Predicate::TypeOutlives(..) => {
 350                         None
 351                     }
 352                 }
 353             })
 354             .collect();
 355
 356         self.elaborate_bounds(bounds.as_slice(), true, |this, trait_ref, m, method_num| {
 357             let xform_self_ty =
 358                 this.xform_self_ty(&m, trait_ref.substs());
 359
 360             debug!("found match: trait_ref={} substs={} m={}",
 361                    trait_ref.repr(this.tcx()),
 362                    trait_ref.substs().repr(this.tcx()),
 363                    m.repr(this.tcx()));
 364             assert_eq!(m.generics.types.get_slice(subst::TypeSpace).len(),
 365                        trait_ref.substs().types.get_slice(subst::TypeSpace).len());
 366             assert_eq!(m.generics.regions.get_slice(subst::TypeSpace).len(),
 367                        trait_ref.substs().regions().get_slice(subst::TypeSpace).len());
 368             assert_eq!(m.generics.types.get_slice(subst::SelfSpace).len(),
 369                        trait_ref.substs().types.get_slice(subst::SelfSpace).len());
 370             assert_eq!(m.generics.regions.get_slice(subst::SelfSpace).len(),
 371                        trait_ref.substs().regions().get_slice(subst::SelfSpace).len());
 372
 373             // Because this trait derives from a where-clause, it
 374             // should not contain any inference variables or other
 375             // artifacts. This means it is safe to put into the
 376             // `WhereClauseCandidate` and (eventually) into the
 377             // `WhereClausePick`.
 378             assert!(trait_ref.substs().types.iter().all(|&t| !ty::type_needs_infer(t)));
 379
 380             this.inherent_candidates.push(Candidate {
 381                 xform_self_ty: xform_self_ty,
 382                 method_ty: m,
 383                 kind: WhereClauseCandidate(trait_ref, method_num)
 384             });
 385         });
 386     }
 387
 388     // Do a search through a list of bounds, using a callback to actually
 389     // create the candidates.
 390     fn elaborate_bounds(
 391         &mut self,
 392         bounds: &[ty::PolyTraitRef<'tcx>],
 393         num_includes_types: bool,
 394         mk_cand: for<'b> |this: &mut ProbeContext<'b, 'tcx>,
 395                           tr: ty::PolyTraitRef<'tcx>,
 396                           m: Rc<ty::Method<'tcx>>,
 397                           method_num: uint|)
 398     {
 399         debug!("elaborate_bounds(bounds={})", bounds.repr(self.tcx()));
 400
 401         let tcx = self.tcx();
 402         let mut cache = HashSet::new();
 403         for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
 404             // Already visited this trait, skip it.
 405             if !cache.insert(bound_trait_ref.def_id()) {
 406                 continue;
 407             }
 408
 409             let (pos, method) = match trait_method(tcx,
 410                                                    bound_trait_ref.def_id(),
 411                                                    self.method_name,
 412                                                    num_includes_types) {
 413                 Some(v) => v,
 414                 None => { continue; }
 415             };
 416
 417             if !self.has_applicable_self(&*method) {
 418                 self.record_static_candidate(TraitSource(bound_trait_ref.def_id()));
 419             } else {
 420                 mk_cand(self, bound_trait_ref, method, pos);
 421             }
 422         }
 423     }
 424
 425     fn assemble_extension_candidates_for_traits_in_scope(&mut self,
 426                                                          expr_id: ast::NodeId)
 427     {
 428         let mut duplicates = HashSet::new();
 429         let opt_applicable_traits = self.fcx.ccx.trait_map.get(&expr_id);
 430         for applicable_traits in opt_applicable_traits.into_iter() {
 431             for &trait_did in applicable_traits.iter() {
 432                 if duplicates.insert(trait_did) {
 433                     self.assemble_extension_candidates_for_trait(trait_did);
 434                 }
 435             }
 436         }
 437     }
 438
 439     fn assemble_extension_candidates_for_trait(&mut self,
 440                                                trait_def_id: ast::DefId) {
 441         debug!("assemble_extension_candidates_for_trait: trait_def_id={}",
 442                trait_def_id.repr(self.tcx()));
 443
 444         // Check whether `trait_def_id` defines a method with suitable name:
 445         let trait_items =
 446             ty::trait_items(self.tcx(), trait_def_id);
 447         let matching_index =
 448             trait_items.iter()
 449                        .position(|item| item.name() == self.method_name);
 450         let matching_index = match matching_index {
 451             Some(i) => i,
 452             None => { return; }
 453         };
 454         let method = match (&*trait_items)[matching_index].as_opt_method() {
 455             Some(m) => m,
 456             None => { return; }
 457         };
 458
 459         // Check whether `trait_def_id` defines a method with suitable name:
 460         if !self.has_applicable_self(&*method) {
 461             debug!("method has inapplicable self");
 462             return self.record_static_candidate(TraitSource(trait_def_id));
 463         }
 464
 465         self.assemble_extension_candidates_for_trait_impls(trait_def_id,
 466                                                            method.clone(),
 467                                                            matching_index);
 468
 469         self.assemble_unboxed_closure_candidates(trait_def_id,
 470                                                  method,
 471                                                  matching_index);
 472     }
 473
 474     fn assemble_extension_candidates_for_trait_impls(&mut self,
 475                                                      trait_def_id: ast::DefId,
 476                                                      method: Rc<ty::Method<'tcx>>,
 477                                                      method_index: uint)
 478     {
 479         ty::populate_implementations_for_trait_if_necessary(self.tcx(),
 480                                                             trait_def_id);
 481
 482         let trait_impls = self.tcx().trait_impls.borrow();
 483         let impl_def_ids = match trait_impls.get(&trait_def_id) {
 484             None => { return; }
 485             Some(impls) => impls,
 486         };
 487
 488         for &impl_def_id in impl_def_ids.borrow().iter() {
 489             debug!("assemble_extension_candidates_for_trait_impl: trait_def_id={} impl_def_id={}",
 490                    trait_def_id.repr(self.tcx()),
 491                    impl_def_id.repr(self.tcx()));
 492
 493             if !self.impl_can_possibly_match(impl_def_id) {
 494                 continue;
 495             }
 496
 497             let impl_substs = self.impl_substs(impl_def_id);
 498
 499             debug!("impl_substs={}", impl_substs.repr(self.tcx()));
 500
 501             let impl_trait_ref =
 502                 ty::impl_trait_ref(self.tcx(), impl_def_id)
 503                 .unwrap() // we know this is a trait impl
 504                 .subst(self.tcx(), &impl_substs);
 505
 506             debug!("impl_trait_ref={}", impl_trait_ref.repr(self.tcx()));
 507
 508             // Determine the receiver type that the method itself expects.
 509             let xform_self_ty =
 510                 self.xform_self_ty(&method, impl_trait_ref.substs);
 511
 512             debug!("xform_self_ty={}", xform_self_ty.repr(self.tcx()));
 513
 514             self.extension_candidates.push(Candidate {
 515                 xform_self_ty: xform_self_ty,
 516                 method_ty: method.clone(),
 517                 kind: ExtensionImplCandidate(impl_def_id, impl_trait_ref, impl_substs, method_index)
 518             });
 519         }
 520     }
 521
 522     fn impl_can_possibly_match(&self, impl_def_id: ast::DefId) -> bool {
 523         let simplified_steps = match self.opt_simplified_steps {
 524             Some(ref simplified_steps) => simplified_steps,
 525             None => { return true; }
 526         };
 527
 528         let impl_type = ty::lookup_item_type(self.tcx(), impl_def_id);
 529         let impl_simplified_type =
 530             match fast_reject::simplify_type(self.tcx(), impl_type.ty, false) {
 531                 Some(simplified_type) => simplified_type,
 532                 None => { return true; }
 533             };
 534
 535         simplified_steps.contains(&impl_simplified_type)
 536     }
 537
 538     fn assemble_unboxed_closure_candidates(&mut self,
 539                                            trait_def_id: ast::DefId,
 540                                            method_ty: Rc<ty::Method<'tcx>>,
 541                                            method_index: uint)
 542     {
 543         // Check if this is one of the Fn,FnMut,FnOnce traits.
 544         let tcx = self.tcx();
 545         let kind = if Some(trait_def_id) == tcx.lang_items.fn_trait() {
 546             ty::FnUnboxedClosureKind
 547         } else if Some(trait_def_id) == tcx.lang_items.fn_mut_trait() {
 548             ty::FnMutUnboxedClosureKind
 549         } else if Some(trait_def_id) == tcx.lang_items.fn_once_trait() {
 550             ty::FnOnceUnboxedClosureKind
 551         } else {
 552             return;
 553         };
 554
 555         // Check if there is an unboxed-closure self-type in the list of receivers.
 556         // If so, add "synthetic impls".
 557         let steps = self.steps.clone();
 558         for step in steps.iter() {
 559             let (closure_def_id, _, _) = match step.self_ty.sty {
 560                 ty::ty_unboxed_closure(a, b, ref c) => (a, b, c),
 561                 _ => continue,
 562             };
 563
 564             let unboxed_closures = self.fcx.inh.unboxed_closures.borrow();
 565             let closure_data = match unboxed_closures.get(&closure_def_id) {
 566                 Some(data) => data,
 567                 None => {
 568                     self.tcx().sess.span_bug(
 569                         self.span,
 570                         format!("No entry for unboxed closure: {}",
 571                                 closure_def_id.repr(self.tcx()))[]);
 572                 }
 573             };
 574
 575             // this closure doesn't implement the right kind of `Fn` trait
 576             if closure_data.kind != kind {
 577                 continue;
 578             }
 579
 580             // create some substitutions for the argument/return type;
 581             // for the purposes of our method lookup, we only take
 582             // receiver type into account, so we can just substitute
 583             // fresh types here to use during substitution and subtyping.
 584             let trait_def = ty::lookup_trait_def(self.tcx(), trait_def_id);
 585             let substs = self.infcx().fresh_substs_for_trait(self.span,
 586                                                              &trait_def.generics,
 587                                                              step.self_ty);
 588
 589             let xform_self_ty = self.xform_self_ty(&method_ty, &substs);
 590             self.inherent_candidates.push(Candidate {
 591                 xform_self_ty: xform_self_ty,
 592                 method_ty: method_ty.clone(),
 593                 kind: UnboxedClosureCandidate(trait_def_id, method_index)
 594             });
 595         }
 596     }
 597
 598     ///////////////////////////////////////////////////////////////////////////
 599     // THE ACTUAL SEARCH
 600
 601     fn pick(mut self) -> PickResult<'tcx> {
 602         let steps = self.steps.clone();
 603
 604         for step in steps.iter() {
 605             match self.pick_step(step) {
 606                 Some(r) => {
 607                     return r;
 608                 }
 609                 None => { }
 610             }
 611         }
 612
 613         Err(NoMatch(self.static_candidates))
 614     }
 615
 616     fn pick_step(&mut self, step: &CandidateStep<'tcx>) -> Option<PickResult<'tcx>> {
 617         debug!("pick_step: step={}", step.repr(self.tcx()));
 618
 619         if ty::type_is_error(step.self_ty) {
 620             return None;
 621         }
 622
 623         match self.pick_by_value_method(step) {
 624             Some(result) => return Some(result),
 625             None => {}
 626         }
 627
 628         self.pick_autorefd_method(step)
 629     }
 630
 631     fn pick_by_value_method(&mut self,
 632                             step: &CandidateStep<'tcx>)
 633                             -> Option<PickResult<'tcx>>
 634     {
 635         /*!
 636          * For each type `T` in the step list, this attempts to find a
 637          * method where the (transformed) self type is exactly `T`. We
 638          * do however do one transformation on the adjustment: if we
 639          * are passing a region pointer in, we will potentially
 640          * *reborrow* it to a shorter lifetime. This allows us to
 641          * transparently pass `&mut` pointers, in particular, without
 642          * consuming them for their entire lifetime.
 643          */
 644
 645         let adjustment = match step.adjustment {
 646             AutoDeref(d) => consider_reborrow(step.self_ty, d),
 647             AutoUnsizeLength(..) | AutoRef(..) => step.adjustment.clone(),
 648         };
 649
 650         return self.pick_method(step.self_ty).map(|r| self.adjust(r, adjustment.clone()));
 651
 652         fn consider_reborrow(ty: Ty, d: uint) -> PickAdjustment {
 653             // Insert a `&*` or `&mut *` if this is a reference type:
 654             match ty.sty {
 655                 ty::ty_rptr(_, ref mt) => AutoRef(mt.mutbl, box AutoDeref(d+1)),
 656                 _ => AutoDeref(d),
 657             }
 658         }
 659     }
 660
 661     fn pick_autorefd_method(&mut self,
 662                             step: &CandidateStep<'tcx>)
 663                             -> Option<PickResult<'tcx>>
 664     {
 665         let tcx = self.tcx();
 666         self.search_mutabilities(
 667             |m| AutoRef(m, box step.adjustment.clone()),
 668             |m,r| ty::mk_rptr(tcx, tcx.mk_region(r), ty::mt {ty:step.self_ty, mutbl:m}))
 669     }
 670
 671     fn search_mutabilities<F, G>(&mut self,
 672                                  mut mk_adjustment: F,
 673                                  mut mk_autoref_ty: G)
 674                                  -> Option<PickResult<'tcx>> where
 675         F: FnMut(ast::Mutability) -> PickAdjustment,
 676         G: FnMut(ast::Mutability, ty::Region) -> Ty<'tcx>,
 677     {
 678         // In general, during probing we erase regions. See
 679         // `impl_self_ty()` for an explanation.
 680         let region = ty::ReStatic;
 681
 682         // Search through mutabilities in order to find one where pick works:
 683         [ast::MutImmutable, ast::MutMutable]
 684             .iter()
 685             .flat_map(|&m| {
 686                 let autoref_ty = mk_autoref_ty(m, region);
 687                 self.pick_method(autoref_ty)
 688                     .map(|r| self.adjust(r, mk_adjustment(m)))
 689                     .into_iter()
 690             })
 691             .nth(0)
 692     }
 693
 694     fn adjust(&mut self,
 695               result: PickResult<'tcx>,
 696               adjustment: PickAdjustment)
 697               -> PickResult<'tcx> {
 698         match result {
 699             Err(e) => Err(e),
 700             Ok(mut pick) => {
 701                 pick.adjustment = adjustment;
 702                 Ok(pick)
 703             }
 704         }
 705     }
 706
 707     fn pick_method(&mut self, self_ty: Ty<'tcx>) -> Option<PickResult<'tcx>> {
 708         debug!("pick_method(self_ty={})", self.infcx().ty_to_string(self_ty));
 709
 710         debug!("searching inherent candidates");
 711         match self.consider_candidates(self_ty, self.inherent_candidates[]) {
 712             None => {}
 713             Some(pick) => {
 714                 return Some(pick);
 715             }
 716         }
 717
 718         debug!("searching extension candidates");
 719         self.consider_candidates(self_ty, self.extension_candidates[])
 720     }
 721
 722     fn consider_candidates(&self,
 723                            self_ty: Ty<'tcx>,
 724                            probes: &[Candidate<'tcx>])
 725                            -> Option<PickResult<'tcx>> {
 726         let mut applicable_candidates: Vec<_> =
 727             probes.iter()
 728                   .filter(|&probe| self.consider_probe(self_ty, probe))
 729                   .collect();
 730
 731         debug!("applicable_candidates: {}", applicable_candidates.repr(self.tcx()));
 732
 733         if applicable_candidates.len() > 1 {
 734             match self.collapse_candidates_to_trait_pick(applicable_candidates[]) {
 735                 Some(pick) => { return Some(Ok(pick)); }
 736                 None => { }
 737             }
 738         }
 739
 740         if applicable_candidates.len() > 1 {
 741             let sources = probes.iter().map(|p| p.to_source()).collect();
 742             return Some(Err(Ambiguity(sources)));
 743         }
 744
 745         applicable_candidates.pop().map(|probe| {
 746             let pick = probe.to_unadjusted_pick();
 747             Ok(pick)
 748         })
 749     }
 750
 751     fn consider_probe(&self, self_ty: Ty<'tcx>, probe: &Candidate<'tcx>) -> bool {
 752         debug!("consider_probe: self_ty={} probe={}",
 753                self_ty.repr(self.tcx()),
 754                probe.repr(self.tcx()));
 755
 756         self.infcx().probe(|_| {
 757             // First check that the self type can be related.
 758             match self.make_sub_ty(self_ty, probe.xform_self_ty) {
 759                 Ok(()) => { }
 760                 Err(_) => {
 761                     debug!("--> cannot relate self-types");
 762                     return false;
 763                 }
 764             }
 765
 766             // If so, impls may carry other conditions (e.g., where
 767             // clauses) that must be considered. Make sure that those
 768             // match as well (or at least may match, sometimes we
 769             // don't have enough information to fully evaluate).
 770             match probe.kind {
 771                 InherentImplCandidate(impl_def_id, ref substs) |
 772                 ExtensionImplCandidate(impl_def_id, _, ref substs, _) => {
 773                     // Check whether the impl imposes obligations we have to worry about.
 774                     let impl_generics = ty::lookup_item_type(self.tcx(), impl_def_id).generics;
 775                     let impl_bounds = impl_generics.to_bounds(self.tcx(), substs);
 776                     // FIXME(#20378) assoc type normalization here?
 777
 778                     // Erase any late-bound regions bound in the impl
 779                     // which appear in the bounds.
 780                     let impl_bounds = self.erase_late_bound_regions(&ty::Binder(impl_bounds));
 781
 782                     // Convert the bounds into obligations.
 783                     let obligations =
 784                         traits::predicates_for_generics(
 785                             self.tcx(),
 786                             traits::ObligationCause::misc(self.span, self.fcx.body_id),
 787                             &impl_bounds);
 788                     debug!("impl_obligations={}", obligations.repr(self.tcx()));
 789
 790                     // Evaluate those obligations to see if they might possibly hold.
 791                     let mut selcx = traits::SelectionContext::new(self.infcx(), self.fcx);
 792                     obligations.all(|o| selcx.evaluate_obligation(o))
 793                 }
 794
 795                 ObjectCandidate(..) |
 796                 UnboxedClosureCandidate(..) |
 797                 WhereClauseCandidate(..) => {
 798                     // These have no additional conditions to check.
 799                     true
 800                 }
 801             }
 802         })
 803     }
 804
 805     /// Sometimes we get in a situation where we have multiple probes that are all impls of the
 806     /// same trait, but we don't know which impl to use. In this case, since in all cases the
 807     /// external interface of the method can be determined from the trait, it's ok not to decide.
 808     /// We can basically just collapse all of the probes for various impls into one where-clause
 809     /// probe. This will result in a pending obligation so when more type-info is available we can
 810     /// make the final decision.
 811     ///
 812     /// Example (`src/test/run-pass/method-two-trait-defer-resolution-1.rs`):
 813     ///
 814     /// ```
 815     /// trait Foo { ... }
 816     /// impl Foo for Vec<int> { ... }
 817     /// impl Foo for Vec<uint> { ... }
 818     /// ```
 819     ///
 820     /// Now imagine the receiver is `Vec<_>`. It doesn't really matter at this time which impl we
 821     /// use, so it's ok to just commit to "using the method from the trait Foo".
 822     fn collapse_candidates_to_trait_pick(&self,
 823                                          probes: &[&Candidate<'tcx>])
 824                                          -> Option<Pick<'tcx>> {
 825         // Do all probes correspond to the same trait?
 826         let trait_data = match probes[0].to_trait_data() {
 827             Some(data) => data,
 828             None => return None,
 829         };
 830         if probes[1..].iter().any(|p| p.to_trait_data() != Some(trait_data)) {
 831             return None;
 832         }
 833
 834         // If so, just use this trait and call it a day.
 835         let (trait_def_id, method_num) = trait_data;
 836         let method_ty = probes[0].method_ty.clone();
 837         Some(Pick {
 838             method_ty: method_ty,
 839             adjustment: AutoDeref(0),
 840             kind: TraitPick(trait_def_id, method_num)
 841         })
 842     }
 843
 844     ///////////////////////////////////////////////////////////////////////////
 845     // MISCELLANY
 846
 847     fn make_sub_ty(&self, sub: Ty<'tcx>, sup: Ty<'tcx>) -> infer::ures<'tcx> {
 848         self.infcx().sub_types(false, infer::Misc(DUMMY_SP), sub, sup)
 849     }
 850
 851     fn has_applicable_self(&self, method: &ty::Method) -> bool {
 852         // "fast track" -- check for usage of sugar
 853         match method.explicit_self {
 854             ty::StaticExplicitSelfCategory => {
 855                 // fallthrough
 856             }
 857             ty::ByValueExplicitSelfCategory |
 858             ty::ByReferenceExplicitSelfCategory(..) |
 859             ty::ByBoxExplicitSelfCategory => {
 860                 return true;
 861             }
 862         }
 863
 864         // FIXME -- check for types that deref to `Self`,
 865         // like `Rc<Self>` and so on.
 866         //
 867         // Note also that the current code will break if this type
 868         // includes any of the type parameters defined on the method
 869         // -- but this could be overcome.
 870         return false;
 871     }
 872
 873     fn record_static_candidate(&mut self, source: CandidateSource) {
 874         self.static_candidates.push(source);
 875     }
 876
 877     fn xform_self_ty(&self,
 878                      method: &Rc<ty::Method<'tcx>>,
 879                      substs: &subst::Substs<'tcx>)
 880                      -> Ty<'tcx>
 881     {
 882         debug!("xform_self_ty(self_ty={}, substs={})",
 883                method.fty.sig.0.inputs[0].repr(self.tcx()),
 884                substs.repr(self.tcx()));
 885
 886         // It is possible for type parameters or early-bound lifetimes
 887         // to appear in the signature of `self`. The substitutions we
 888         // are given do not include type/lifetime parameters for the
 889         // method yet. So create fresh variables here for those too,
 890         // if there are any.
 891         assert_eq!(substs.types.len(subst::FnSpace), 0);
 892         assert_eq!(substs.regions().len(subst::FnSpace), 0);
 893         let mut substs = substs;
 894         let placeholder;
 895         if
 896             !method.generics.types.is_empty_in(subst::FnSpace) ||
 897             !method.generics.regions.is_empty_in(subst::FnSpace)
 898         {
 899             let method_types =
 900                 self.infcx().next_ty_vars(
 901                     method.generics.types.len(subst::FnSpace));
 902
 903             // In general, during probe we erase regions. See
 904             // `impl_self_ty()` for an explanation.
 905             let method_regions =
 906                 method.generics.regions.get_slice(subst::FnSpace)
 907                 .iter()
 908                 .map(|_| ty::ReStatic)
 909                 .collect();
 910
 911             placeholder = (*substs).clone().with_method(method_types, method_regions);
 912             substs = &placeholder;
 913         }
 914
 915         // Replace early-bound regions and types.
 916         let xform_self_ty = method.fty.sig.0.inputs[0].subst(self.tcx(), substs);
 917
 918         // Replace late-bound regions bound in the impl or
 919         // where-clause (2 levels of binding) and method (1 level of binding).
 920         self.erase_late_bound_regions(
 921             &self.erase_late_bound_regions(
 922                 &ty::Binder(ty::Binder(xform_self_ty))))
 923     }
 924
 925     fn impl_substs(&self,
 926                    impl_def_id: ast::DefId)
 927                    -> subst::Substs<'tcx>
 928     {
 929         let impl_pty = ty::lookup_item_type(self.tcx(), impl_def_id);
 930
 931         let type_vars =
 932             impl_pty.generics.types.map(
 933                 |_| self.infcx().next_ty_var());
 934
 935         let region_placeholders =
 936             impl_pty.generics.regions.map(
 937                 |_| ty::ReStatic); // see erase_late_bound_regions() for an expl of why 'static
 938
 939         subst::Substs::new(type_vars, region_placeholders)
 940     }
 941
 942     /// Replace late-bound-regions bound by `value` with `'static` using
 943     /// `ty::erase_late_bound_regions`.
 944     ///
 945     /// This is only a reasonable thing to do during the *probe* phase, not the *confirm* phase, of
 946     /// method matching. It is reasonable during the probe phase because we don't consider region
 947     /// relationships at all. Therefore, we can just replace all the region variables with 'static
 948     /// rather than creating fresh region variables. This is nice for two reasons:
 949     ///
 950     /// 1. Because the numbers of the region variables would otherwise be fairly unique to this
 951     ///    particular method call, it winds up creating fewer types overall, which helps for memory
 952     ///    usage. (Admittedly, this is a rather small effect, though measureable.)
 953     ///
 954     /// 2. It makes it easier to deal with higher-ranked trait bounds, because we can replace any
 955     ///    late-bound regions with 'static. Otherwise, if we were going to replace late-bound
 956     ///    regions with actual region variables as is proper, we'd have to ensure that the same
 957     ///    region got replaced with the same variable, which requires a bit more coordination
 958     ///    and/or tracking the substitution and
 959     ///    so forth.
 960     fn erase_late_bound_regions<T>(&self, value: &ty::Binder<T>) -> T
 961         where T : TypeFoldable<'tcx> + Repr<'tcx>
 962     {
 963         ty::erase_late_bound_regions(self.tcx(), value)
 964     }
 965 }
 966
 967 fn impl_method<'tcx>(tcx: &ty::ctxt<'tcx>,
 968                      impl_def_id: ast::DefId,
 969                      method_name: ast::Name)
 970                      -> Option<Rc<ty::Method<'tcx>>>
 971 {
 972     let impl_items = tcx.impl_items.borrow();
 973     let impl_items = impl_items.get(&impl_def_id).unwrap();
 974     impl_items
 975         .iter()
 976         .map(|&did| ty::impl_or_trait_item(tcx, did.def_id()))
 977         .find(|m| m.name() == method_name)
 978         .and_then(|item| item.as_opt_method())
 979 }
 980
 981 /// Find method with name `method_name` defined in `trait_def_id` and return it, along with its
 982 /// index (or `None`, if no such method).
 983 fn trait_method<'tcx>(tcx: &ty::ctxt<'tcx>,
 984                       trait_def_id: ast::DefId,
 985                       method_name: ast::Name,
 986                       num_includes_types: bool)
 987                       -> Option<(uint, Rc<ty::Method<'tcx>>)>
 988 {
 989     let trait_items = ty::trait_items(tcx, trait_def_id);
 990     debug!("trait_method; items: {}", trait_items);
 991     trait_items
 992         .iter()
 993         .filter(|item|
 994             num_includes_types || match *item {
 995                 &ty::MethodTraitItem(_) => true,
 996                 &ty::TypeTraitItem(_) => false
 997             })
 998         .enumerate()
 999         .find(|&(_, ref item)| item.name() == method_name)
1000         .and_then(|(idx, item)| item.as_opt_method().map(|m| (idx, m)))
1001 }
1002
1003 impl<'tcx> Candidate<'tcx> {
1004     fn to_unadjusted_pick(&self) -> Pick<'tcx> {
1005         Pick {
1006             method_ty: self.method_ty.clone(),
1007             adjustment: AutoDeref(0),
1008             kind: match self.kind {
1009                 InherentImplCandidate(def_id, _) => {
1010                     InherentImplPick(def_id)
1011                 }
1012                 ObjectCandidate(def_id, method_num, real_index) => {
1013                     ObjectPick(def_id, method_num, real_index)
1014                 }
1015                 ExtensionImplCandidate(def_id, _, _, index) => {
1016                     ExtensionImplPick(def_id, index)
1017                 }
1018                 UnboxedClosureCandidate(trait_def_id, index) => {
1019                     TraitPick(trait_def_id, index)
1020                 }
1021                 WhereClauseCandidate(ref trait_ref, index) => {
1022                     // Only trait derived from where-clauses should
1023                     // appear here, so they should not contain any
1024                     // inference variables or other artifacts. This
1025                     // means they are safe to put into the
1026                     // `WhereClausePick`.
1027                     assert!(trait_ref.substs().types.iter().all(|&t| !ty::type_needs_infer(t)));
1028
1029                     WhereClausePick((*trait_ref).clone(), index)
1030                 }
1031             }
1032         }
1033     }
1034
1035     fn to_source(&self) -> CandidateSource {
1036         match self.kind {
1037             InherentImplCandidate(def_id, _) => ImplSource(def_id),
1038             ObjectCandidate(def_id, _, _) => TraitSource(def_id),
1039             ExtensionImplCandidate(def_id, _, _, _) => ImplSource(def_id),
1040             UnboxedClosureCandidate(trait_def_id, _) => TraitSource(trait_def_id),
1041             WhereClauseCandidate(ref trait_ref, _) => TraitSource(trait_ref.def_id()),
1042         }
1043     }
1044
1045     fn to_trait_data(&self) -> Option<(ast::DefId,MethodIndex)> {
1046         match self.kind {
1047             InherentImplCandidate(..) |
1048             ObjectCandidate(..) => {
1049                 None
1050             }
1051             UnboxedClosureCandidate(trait_def_id, method_num) => {
1052                 Some((trait_def_id, method_num))
1053             }
1054             ExtensionImplCandidate(_, ref trait_ref, _, method_num) => {
1055                 Some((trait_ref.def_id, method_num))
1056             }
1057             WhereClauseCandidate(ref trait_ref, method_num) => {
1058                 Some((trait_ref.def_id(), method_num))
1059             }
1060         }
1061     }
1062 }
1063
1064 impl<'tcx> Repr<'tcx> for Candidate<'tcx> {
1065     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1066         format!("Candidate(xform_self_ty={}, kind={})",
1067                 self.xform_self_ty.repr(tcx),
1068                 self.kind.repr(tcx))
1069     }
1070 }
1071
1072 impl<'tcx> Repr<'tcx> for CandidateKind<'tcx> {
1073     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1074         match *self {
1075             InherentImplCandidate(ref a, ref b) =>
1076                 format!("InherentImplCandidate({},{})", a.repr(tcx), b.repr(tcx)),
1077             ObjectCandidate(a, b, c) =>
1078                 format!("ObjectCandidate({},{},{})", a.repr(tcx), b, c),
1079             ExtensionImplCandidate(ref a, ref b, ref c, ref d) =>
1080                 format!("ExtensionImplCandidate({},{},{},{})", a.repr(tcx), b.repr(tcx),
1081                         c.repr(tcx), d),
1082             UnboxedClosureCandidate(ref a, ref b) =>
1083                 format!("UnboxedClosureCandidate({},{})", a.repr(tcx), b),
1084             WhereClauseCandidate(ref a, ref b) =>
1085                 format!("WhereClauseCandidate({},{})", a.repr(tcx), b),
1086         }
1087     }
1088 }
1089
1090 impl<'tcx> Repr<'tcx> for CandidateStep<'tcx> {
1091     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1092         format!("CandidateStep({},{})",
1093                 self.self_ty.repr(tcx),
1094                 self.adjustment)
1095     }
1096 }
1097
1098 impl<'tcx> Repr<'tcx> for PickAdjustment {
1099     fn repr(&self, _tcx: &ty::ctxt) -> String {
1100         format!("{}", self)
1101     }
1102 }
1103
1104 impl<'tcx> Repr<'tcx> for PickKind<'tcx> {
1105     fn repr(&self, _tcx: &ty::ctxt) -> String {
1106         format!("{}", self)
1107     }
1108 }
1109
1110 impl<'tcx> Repr<'tcx> for Pick<'tcx> {
1111     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1112         format!("Pick(method_ty={}, adjustment={}, kind={})",
1113                 self.method_ty.repr(tcx),
1114                 self.adjustment,
1115                 self.kind)
1116     }
1117 }