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