src/librustc/middle/typeck/check/method.rs

   1 // Copyright 2012 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 /*!
  12
  13 # Method lookup
  14
  15 Method lookup can be rather complex due to the interaction of a number
  16 of factors, such as self types, autoderef, trait lookup, etc.  The
  17 algorithm is divided into two parts: candidate collection and
  18 candidate selection.
  19
  20 ## Candidate collection
  21
  22 A `Candidate` is a method item that might plausibly be the method
  23 being invoked.  Candidates are grouped into two kinds, inherent and
  24 extension.  Inherent candidates are those that are derived from the
  25 type of the receiver itself.  So, if you have a receiver of some
  26 nominal type `Foo` (e.g., a struct), any methods defined within an
  27 impl like `impl Foo` are inherent methods.  Nothing needs to be
  28 imported to use an inherent method, they are associated with the type
  29 itself (note that inherent impls can only be defined in the same
  30 module as the type itself).
  31
  32 Inherent candidates are not always derived from impls.  If you have a
  33 trait instance, such as a value of type `@ToStr`, then the trait
  34 methods (`to_str()`, in this case) are inherently associated with it.
  35 Another case is type parameters, in which case the methods of their
  36 bounds are inherent.
  37
  38 Extension candidates are derived from imported traits.  If I have the
  39 trait `ToStr` imported, and I call `to_str()` on a value of type `T`,
  40 then we will go off to find out whether there is an impl of `ToStr`
  41 for `T`.  These kinds of method calls are called "extension methods".
  42 They can be defined in any module, not only the one that defined `T`.
  43 Furthermore, you must import the trait to call such a method.
  44
  45 For better or worse, we currently give weight to inherent methods over
  46 extension methods during candidate selection (below).
  47
  48 ## Candidate selection
  49
  50 Once we know the set of candidates, we can go off and try to select
  51 which one is actually being called.  We do this by taking the type of
  52 the receiver, let's call it R, and checking whether it matches against
  53 the expected receiver type for each of the collected candidates.  We
  54 first check for inherent candidates and see whether we get exactly one
  55 match (zero means keep searching, more than one is an error).  If so,
  56 we return that as the candidate.  Otherwise we search the extension
  57 candidates in the same way.
  58
  59 If find no matching candidate at all, we proceed to auto-deref the
  60 receiver type and search again.  We keep doing that until we cannot
  61 auto-deref any longer.  At each step, we also check for candidates
  62 based on "autoptr", which if the current type is `T`, checks for `&mut
  63 T`, `&const T`, and `&T` receivers.  Finally, at the very end, we will
  64 also try autoslice, which converts `~[]` to `&[]` (there is no point
  65 at trying autoslice earlier, because no autoderefable type is also
  66 sliceable).
  67
  68 ## Why two phases?
  69
  70 You might wonder why we first collect the candidates and then select.
  71 Both the inherent candidate collection and the candidate selection
  72 proceed by progressively deref'ing the receiver type, after all.  The
  73 answer is that two phases are needed to elegantly deal with explicit
  74 self.  After all, if there is an impl for the type `Foo`, it can
  75 define a method with the type `~self`, which means that it expects a
  76 receiver of type `~Foo`.  If we have a receiver of type `~Foo`, but we
  77 waited to search for that impl until we have deref'd the `~` away and
  78 obtained the type `Foo`, we would never match this method.
  79
  80 */
  81
  82
  83 use middle::subst::Subst;
  84 use middle::ty::*;
  85 use middle::ty;
  86 use middle::typeck::astconv::AstConv;
  87 use middle::typeck::check::{FnCtxt, impl_self_ty};
  88 use middle::typeck::check::{structurally_resolved_type};
  89 use middle::typeck::check::vtable;
  90 use middle::typeck::check;
  91 use middle::typeck::infer;
  92 use middle::typeck::MethodCallee;
  93 use middle::typeck::{MethodOrigin, MethodParam};
  94 use middle::typeck::{MethodStatic, MethodObject};
  95 use middle::typeck::{param_numbered, param_self, param_index};
  96 use middle::typeck::check::regionmanip::replace_bound_regions_in_fn_sig;
  97 use util::common::indenter;
  98 use util::ppaux::Repr;
  99
 100 use std::cell::RefCell;
 101 use collections::HashSet;
 102 use std::result;
 103 use std::vec;
 104 use syntax::ast::{DefId, SelfValue, SelfRegion};
 105 use syntax::ast::{SelfUniq, SelfStatic};
 106 use syntax::ast::{MutMutable, MutImmutable};
 107 use syntax::ast;
 108 use syntax::parse::token;
 109
 110 #[deriving(Eq)]
 111 pub enum CheckTraitsFlag {
 112     CheckTraitsOnly,
 113     CheckTraitsAndInherentMethods,
 114 }
 115
 116 #[deriving(Eq)]
 117 pub enum AutoderefReceiverFlag {
 118     AutoderefReceiver,
 119     DontAutoderefReceiver,
 120 }
 121
 122 pub fn lookup(
 123         fcx: @FnCtxt,
 124
 125         // In a call `a.b::<X, Y, ...>(...)`:
 126         expr: &ast::Expr,                   // The expression `a.b(...)`.
 127         self_expr: &ast::Expr,              // The expression `a`.
 128         m_name: ast::Name,                  // The name `b`.
 129         self_ty: ty::t,                     // The type of `a`.
 130         supplied_tps: &[ty::t],             // The list of types X, Y, ... .
 131         deref_args: check::DerefArgs,       // Whether we autopointer first.
 132         check_traits: CheckTraitsFlag,      // Whether we check traits only.
 133         autoderef_receiver: AutoderefReceiverFlag)
 134      -> Option<MethodCallee> {
 135     let lcx = LookupContext {
 136         fcx: fcx,
 137         expr: expr,
 138         self_expr: self_expr,
 139         m_name: m_name,
 140         supplied_tps: supplied_tps,
 141         impl_dups: @RefCell::new(HashSet::new()),
 142         inherent_candidates: @RefCell::new(~[]),
 143         extension_candidates: @RefCell::new(~[]),
 144         deref_args: deref_args,
 145         check_traits: check_traits,
 146         autoderef_receiver: autoderef_receiver,
 147     };
 148
 149     let self_ty = structurally_resolved_type(fcx, self_expr.span, self_ty);
 150     debug!("method lookup(self_ty={}, expr={}, self_expr={})",
 151            self_ty.repr(fcx.tcx()), expr.repr(fcx.tcx()),
 152            self_expr.repr(fcx.tcx()));
 153
 154     debug!("searching inherent candidates");
 155     lcx.push_inherent_candidates(self_ty);
 156     let mme = lcx.search(self_ty);
 157     if mme.is_some() {
 158         return mme;
 159     }
 160
 161     debug!("searching extension candidates");
 162     lcx.reset_candidates();
 163     lcx.push_bound_candidates(self_ty, None);
 164     lcx.push_extension_candidates();
 165     return lcx.search(self_ty);
 166 }
 167
 168 pub fn lookup_in_trait(
 169         fcx: @FnCtxt,
 170
 171         // In a call `a.b::<X, Y, ...>(...)`:
 172         expr: &ast::Expr,                   // The expression `a.b(...)`.
 173         self_expr: &ast::Expr,              // The expression `a`.
 174         m_name: ast::Name,                  // The name `b`.
 175         trait_did: DefId,                   // The trait to limit the lookup to.
 176         self_ty: ty::t,                     // The type of `a`.
 177         supplied_tps: &[ty::t],             // The list of types X, Y, ... .
 178         autoderef_receiver: AutoderefReceiverFlag)
 179      -> Option<MethodCallee> {
 180     let lcx = LookupContext {
 181         fcx: fcx,
 182         expr: expr,
 183         self_expr: self_expr,
 184         m_name: m_name,
 185         supplied_tps: supplied_tps,
 186         impl_dups: @RefCell::new(HashSet::new()),
 187         inherent_candidates: @RefCell::new(~[]),
 188         extension_candidates: @RefCell::new(~[]),
 189         deref_args: check::DoDerefArgs,
 190         check_traits: CheckTraitsOnly,
 191         autoderef_receiver: autoderef_receiver,
 192     };
 193
 194     let self_ty = structurally_resolved_type(fcx, self_expr.span, self_ty);
 195     debug!("method lookup_in_trait(self_ty={}, expr={}, self_expr={})",
 196            self_ty.repr(fcx.tcx()), expr.repr(fcx.tcx()),
 197            self_expr.repr(fcx.tcx()));
 198
 199     lcx.push_bound_candidates(self_ty, Some(trait_did));
 200     lcx.push_extension_candidate(trait_did);
 201     lcx.search(self_ty)
 202 }
 203
 204 pub struct LookupContext<'a> {
 205     fcx: @FnCtxt,
 206     expr: &'a ast::Expr,
 207     self_expr: &'a ast::Expr,
 208     m_name: ast::Name,
 209     supplied_tps: &'a [ty::t],
 210     impl_dups: @RefCell<HashSet<DefId>>,
 211     inherent_candidates: @RefCell<~[Candidate]>,
 212     extension_candidates: @RefCell<~[Candidate]>,
 213     deref_args: check::DerefArgs,
 214     check_traits: CheckTraitsFlag,
 215     autoderef_receiver: AutoderefReceiverFlag,
 216 }
 217
 218 /**
 219  * A potential method that might be called, assuming the receiver
 220  * is of a suitable type.
 221  */
 222 #[deriving(Clone)]
 223 pub struct Candidate {
 224     rcvr_match_condition: RcvrMatchCondition,
 225     rcvr_substs: ty::substs,
 226     method_ty: @ty::Method,
 227     origin: MethodOrigin,
 228 }
 229
 230 /// This type represents the conditions under which the receiver is
 231 /// considered to "match" a given method candidate. Typically the test
 232 /// is whether the receiver is of a particular type. However, this
 233 /// type is the type of the receiver *after accounting for the
 234 /// method's self type* (e.g., if the method is an `~self` method, we
 235 /// have *already verified* that the receiver is of some type `~T` and
 236 /// now we must check that the type `T` is correct).  Unfortunately,
 237 /// because traits are not types, this is a pain to do.
 238 #[deriving(Clone)]
 239 pub enum RcvrMatchCondition {
 240     RcvrMatchesIfObject(ast::DefId),
 241     RcvrMatchesIfSubtype(ty::t)
 242 }
 243
 244 impl<'a> LookupContext<'a> {
 245     fn search(&self, self_ty: ty::t) -> Option<MethodCallee> {
 246         let mut self_ty = self_ty;
 247         let mut autoderefs = 0;
 248         loop {
 249             debug!("loop: self_ty={} autoderefs={}",
 250                    self.ty_to_str(self_ty), autoderefs);
 251
 252             match self.deref_args {
 253                 check::DontDerefArgs => {
 254                     match self.search_for_autoderefd_method(self_ty,
 255                                                             autoderefs) {
 256                         Some(mme) => { return Some(mme); }
 257                         None => {}
 258                     }
 259
 260                     match self.search_for_autoptrd_method(self_ty,
 261                                                           autoderefs) {
 262                         Some(mme) => { return Some(mme); }
 263                         None => {}
 264                     }
 265                 }
 266                 check::DoDerefArgs => {
 267                     match self.search_for_autoptrd_method(self_ty,
 268                                                           autoderefs) {
 269                         Some(mme) => { return Some(mme); }
 270                         None => {}
 271                     }
 272
 273                     match self.search_for_autoderefd_method(self_ty,
 274                                                             autoderefs) {
 275                         Some(mme) => { return Some(mme); }
 276                         None => {}
 277                     }
 278                 }
 279             }
 280
 281             // Don't autoderef if we aren't supposed to.
 282             if self.autoderef_receiver == DontAutoderefReceiver {
 283                 break;
 284             }
 285
 286             // Otherwise, perform autoderef.
 287             match self.deref(self_ty) {
 288                 None => { break; }
 289                 Some(ty) => {
 290                     self_ty = ty;
 291                     autoderefs += 1;
 292                 }
 293             }
 294         }
 295
 296         self.search_for_autosliced_method(self_ty, autoderefs)
 297     }
 298
 299     fn deref(&self, ty: ty::t) -> Option<ty::t> {
 300         match ty::deref(ty, false) {
 301             None => None,
 302             Some(t) => {
 303                 Some(structurally_resolved_type(self.fcx,
 304                                                 self.self_expr.span,
 305                                                 t.ty))
 306             }
 307         }
 308     }
 309
 310     // ______________________________________________________________________
 311     // Candidate collection (see comment at start of file)
 312
 313     fn reset_candidates(&self) {
 314         self.inherent_candidates.set(~[]);
 315         self.extension_candidates.set(~[]);
 316     }
 317
 318     fn push_inherent_candidates(&self, self_ty: ty::t) {
 319         /*!
 320          * Collect all inherent candidates into
 321          * `self.inherent_candidates`.  See comment at the start of
 322          * the file.  To find the inherent candidates, we repeatedly
 323          * deref the self-ty to find the "base-type".  So, for
 324          * example, if the receiver is @@C where `C` is a struct type,
 325          * we'll want to find the inherent impls for `C`.
 326          */
 327
 328         let mut self_ty = self_ty;
 329         loop {
 330             match get(self_ty).sty {
 331                 ty_trait(did, ref substs, _, _, _) => {
 332                     self.push_inherent_candidates_from_object(did, substs);
 333                     self.push_inherent_impl_candidates_for_type(did);
 334                 }
 335                 ty_enum(did, _) | ty_struct(did, _) => {
 336                     if self.check_traits == CheckTraitsAndInherentMethods {
 337                         self.push_inherent_impl_candidates_for_type(did);
 338                     }
 339                 }
 340                 _ => { /* No inherent methods in these types */ }
 341             }
 342
 343             // n.b.: Generally speaking, we only loop if we hit the
 344             // fallthrough case in the match above.  The exception
 345             // would be newtype enums.
 346             self_ty = match self.deref(self_ty) {
 347                 None => { return; }
 348                 Some(ty) => { ty }
 349             }
 350         }
 351     }
 352
 353     fn push_bound_candidates(&self, self_ty: ty::t, restrict_to: Option<DefId>) {
 354         let mut self_ty = self_ty;
 355         loop {
 356             match get(self_ty).sty {
 357                 ty_param(p) => {
 358                     self.push_inherent_candidates_from_param(self_ty, restrict_to, p);
 359                 }
 360                 ty_self(..) => {
 361                     // Call is of the form "self.foo()" and appears in one
 362                     // of a trait's default method implementations.
 363                     self.push_inherent_candidates_from_self(self_ty, restrict_to);
 364                 }
 365                 _ => { /* No bound methods in these types */ }
 366             }
 367
 368             self_ty = match self.deref(self_ty) {
 369                 None => { return; }
 370                 Some(ty) => { ty }
 371             }
 372         }
 373     }
 374
 375     fn push_extension_candidate(&self, trait_did: DefId) {
 376         ty::populate_implementations_for_trait_if_necessary(self.tcx(), trait_did);
 377
 378         // Look for explicit implementations.
 379         let trait_impls = self.tcx().trait_impls.borrow();
 380         for impl_infos in trait_impls.get().find(&trait_did).iter() {
 381             for impl_info in impl_infos.borrow().get().iter() {
 382                 self.push_candidates_from_impl(
 383                     self.extension_candidates.borrow_mut().get(), *impl_info);
 384             }
 385         }
 386     }
 387
 388     fn push_extension_candidates(&self) {
 389         // If the method being called is associated with a trait, then
 390         // find all the impls of that trait.  Each of those are
 391         // candidates.
 392         let opt_applicable_traits = self.fcx.ccx.trait_map.find(&self.expr.id);
 393         for applicable_traits in opt_applicable_traits.move_iter() {
 394             for trait_did in applicable_traits.iter() {
 395                 self.push_extension_candidate(*trait_did);
 396             }
 397         }
 398     }
 399
 400     // Determine the index of a method in the list of all methods belonging
 401     // to a trait and its supertraits.
 402     fn get_method_index(&self,
 403                         trait_ref: @TraitRef,
 404                         subtrait: @TraitRef,
 405                         n_method: uint) -> uint {
 406         let tcx = self.tcx();
 407
 408         // We need to figure the "real index" of the method in a
 409         // listing of all the methods of an object. We do this by
 410         // iterating down the supertraits of the object's trait until
 411         // we find the trait the method came from, counting up the
 412         // methods from them.
 413         let mut method_count = 0;
 414         ty::each_bound_trait_and_supertraits(tcx, &[subtrait], |bound_ref| {
 415             if bound_ref.def_id == trait_ref.def_id { false }
 416                 else {
 417                 method_count += ty::trait_methods(tcx, bound_ref.def_id).len();
 418                 true
 419             }
 420         });
 421         return method_count + n_method;
 422     }
 423
 424
 425     fn push_inherent_candidates_from_object(&self,
 426                                             did: DefId,
 427                                             substs: &ty::substs) {
 428         debug!("push_inherent_candidates_from_object(did={}, substs={})",
 429                self.did_to_str(did),
 430                substs_to_str(self.tcx(), substs));
 431         let _indenter = indenter();
 432
 433         // It is illegal to invoke a method on a trait instance that
 434         // refers to the `self` type. An error will be reported by
 435         // `enforce_object_limitations()` if the method refers
 436         // to the `Self` type. Substituting ty_err here allows
 437         // compiler to soldier on.
 438         //
 439         // `confirm_candidate()` also relies upon this substitution
 440         // for Self. (fix)
 441         let rcvr_substs = substs {
 442             self_ty: Some(ty::mk_err()),
 443             ..(*substs).clone()
 444         };
 445         let trait_ref = @TraitRef { def_id: did, substs: rcvr_substs.clone() };
 446
 447         self.push_inherent_candidates_from_bounds_inner(&[trait_ref],
 448             |new_trait_ref, m, method_num, _bound_num| {
 449             let vtable_index =
 450                 self.get_method_index(new_trait_ref, trait_ref, method_num);
 451             let mut m = (*m).clone();
 452             // We need to fix up the transformed self type.
 453             m.fty.sig.inputs[0] =
 454                 self.construct_transformed_self_ty_for_object(
 455                     did, &rcvr_substs, &m);
 456
 457             Some(Candidate {
 458                 rcvr_match_condition: RcvrMatchesIfObject(did),
 459                 rcvr_substs: new_trait_ref.substs.clone(),
 460                 method_ty: @m,
 461                 origin: MethodObject(MethodObject {
 462                         trait_id: new_trait_ref.def_id,
 463                         object_trait_id: did,
 464                         method_num: method_num,
 465                         real_index: vtable_index
 466                     })
 467             })
 468         });
 469     }
 470
 471     fn push_inherent_candidates_from_param(&self,
 472                                            rcvr_ty: ty::t,
 473                                            restrict_to: Option<DefId>,
 474                                            param_ty: param_ty) {
 475         debug!("push_inherent_candidates_from_param(param_ty={:?})",
 476                param_ty);
 477         self.push_inherent_candidates_from_bounds(
 478             rcvr_ty,
 479             self.fcx.inh.param_env.type_param_bounds[param_ty.idx].trait_bounds,
 480             restrict_to,
 481             param_numbered(param_ty.idx));
 482     }
 483
 484
 485     fn push_inherent_candidates_from_self(&self,
 486                                           rcvr_ty: ty::t,
 487                                           restrict_to: Option<DefId>) {
 488         debug!("push_inherent_candidates_from_self()");
 489         self.push_inherent_candidates_from_bounds(
 490             rcvr_ty,
 491             [self.fcx.inh.param_env.self_param_bound.unwrap()],
 492             restrict_to,
 493             param_self)
 494     }
 495
 496     fn push_inherent_candidates_from_bounds(&self,
 497                                             self_ty: ty::t,
 498                                             bounds: &[@TraitRef],
 499                                             restrict_to: Option<DefId>,
 500                                             param: param_index) {
 501         self.push_inherent_candidates_from_bounds_inner(bounds,
 502             |trait_ref, m, method_num, bound_num| {
 503                 match restrict_to {
 504                     Some(trait_did) => {
 505                         if trait_did != trait_ref.def_id {
 506                             return None;
 507                         }
 508                     }
 509                     _ => {}
 510                 }
 511                 Some(Candidate {
 512                     rcvr_match_condition: RcvrMatchesIfSubtype(self_ty),
 513                     rcvr_substs: trait_ref.substs.clone(),
 514                     method_ty: m,
 515                     origin: MethodParam(MethodParam {
 516                         trait_id: trait_ref.def_id,
 517                         method_num: method_num,
 518                         param_num: param,
 519                         bound_num: bound_num,
 520                     })
 521                 })
 522         })
 523     }
 524
 525     // Do a search through a list of bounds, using a callback to actually
 526     // create the candidates.
 527     fn push_inherent_candidates_from_bounds_inner(&self,
 528                                                   bounds: &[@TraitRef],
 529                                                   mk_cand: |tr: @TraitRef,
 530                                                             m: @ty::Method,
 531                                                             method_num: uint,
 532                                                             bound_num: uint|
 533                                                             -> Option<Candidate>) {
 534         let tcx = self.tcx();
 535         let mut next_bound_idx = 0; // count only trait bounds
 536
 537         ty::each_bound_trait_and_supertraits(tcx, bounds, |bound_trait_ref| {
 538             let this_bound_idx = next_bound_idx;
 539             next_bound_idx += 1;
 540
 541             let trait_methods = ty::trait_methods(tcx, bound_trait_ref.def_id);
 542             match trait_methods.iter().position(|m| {
 543                 m.explicit_self != ast::SelfStatic &&
 544                 m.ident.name == self.m_name })
 545             {
 546                 Some(pos) => {
 547                     let method = trait_methods[pos];
 548
 549                     match mk_cand(bound_trait_ref, method, pos, this_bound_idx) {
 550                         Some(cand) => {
 551                             debug!("pushing inherent candidate for param: {:?}", cand);
 552                             self.inherent_candidates.borrow_mut().get().push(cand);
 553                         }
 554                         None => {}
 555                     }
 556                 }
 557                 None => {
 558                     debug!("trait doesn't contain method: {:?}",
 559                         bound_trait_ref.def_id);
 560                     // check next trait or bound
 561                 }
 562             }
 563             true
 564         });
 565     }
 566
 567
 568     fn push_inherent_impl_candidates_for_type(&self, did: DefId) {
 569         // Read the inherent implementation candidates for this type from the
 570         // metadata if necessary.
 571         ty::populate_implementations_for_type_if_necessary(self.tcx(), did);
 572
 573         let inherent_impls = self.tcx().inherent_impls.borrow();
 574         let opt_impl_infos = inherent_impls.get().find(&did);
 575         for impl_infos in opt_impl_infos.iter() {
 576             let impl_infos = impl_infos.borrow();
 577             for impl_info in impl_infos.get().iter() {
 578                 let mut inherent_candidates = self.inherent_candidates
 579                                                   .borrow_mut();
 580                 self.push_candidates_from_impl(inherent_candidates.get(),
 581                                                *impl_info);
 582             }
 583         }
 584     }
 585
 586     fn push_candidates_from_impl(&self,
 587                                      candidates: &mut ~[Candidate],
 588                                      impl_info: &ty::Impl) {
 589         {
 590             let mut impl_dups = self.impl_dups.borrow_mut();
 591             if !impl_dups.get().insert(impl_info.did) {
 592                 return; // already visited
 593             }
 594         }
 595
 596         debug!("push_candidates_from_impl: {} {} {}",
 597                token::get_name(self.m_name),
 598                impl_info.ident.repr(self.tcx()),
 599                impl_info.methods.map(|m| m.ident).repr(self.tcx()));
 600
 601         let idx = {
 602             match impl_info.methods.iter().position(|m| m.ident.name == self.m_name) {
 603                 Some(idx) => idx,
 604                 None => { return; } // No method with the right name.
 605             }
 606         };
 607
 608         let method = ty::method(self.tcx(), impl_info.methods[idx].def_id);
 609
 610         // determine the `self` of the impl with fresh
 611         // variables for each parameter:
 612         let location_info = &vtable::location_info_for_expr(self.self_expr);
 613         let vcx = self.fcx.vtable_context();
 614         let ty::ty_param_substs_and_ty {
 615             substs: impl_substs,
 616             ty: impl_ty
 617         } = impl_self_ty(&vcx, location_info, impl_info.did);
 618
 619         candidates.push(Candidate {
 620             rcvr_match_condition: RcvrMatchesIfSubtype(impl_ty),
 621             rcvr_substs: impl_substs,
 622             method_ty: method,
 623             origin: MethodStatic(method.def_id)
 624         });
 625     }
 626
 627     // ______________________________________________________________________
 628     // Candidate selection (see comment at start of file)
 629
 630     fn search_for_autoderefd_method(&self,
 631                                         self_ty: ty::t,
 632                                         autoderefs: uint)
 633                                         -> Option<MethodCallee> {
 634         let (self_ty, autoadjust) =
 635             self.consider_reborrow(self_ty, autoderefs);
 636         match self.search_for_method(self_ty) {
 637             None => None,
 638             Some(mme) => {
 639                 debug!("(searching for autoderef'd method) writing \
 640                        adjustment ({}) to {}",
 641                        autoderefs,
 642                        self.self_expr.id);
 643                 self.fcx.write_adjustment(self.self_expr.id, @autoadjust);
 644                 Some(mme)
 645             }
 646         }
 647     }
 648
 649     fn consider_reborrow(&self,
 650                              self_ty: ty::t,
 651                              autoderefs: uint)
 652                              -> (ty::t, ty::AutoAdjustment) {
 653         /*!
 654          * In the event that we are invoking a method with a receiver
 655          * of a borrowed type like `&T`, `&mut T`, or `&mut [T]`,
 656          * we will "reborrow" the receiver implicitly.  For example, if
 657          * you have a call `r.inc()` and where `r` has type `&mut T`,
 658          * then we treat that like `(&mut *r).inc()`.  This avoids
 659          * consuming the original pointer.
 660          *
 661          * You might think that this would be a natural byproduct of
 662          * the auto-deref/auto-ref process.  This is true for `~T`
 663          * but not for an `&mut T` receiver.  With `~T`, we would
 664          * begin by testing for methods with a self type `~T`,
 665          * then autoderef to `T`, then autoref to `&mut T`.  But with
 666          * an `&mut T` receiver the process begins with `&mut T`, only
 667          * without any autoadjustments.
 668          */
 669
 670         let tcx = self.tcx();
 671         return match ty::get(self_ty).sty {
 672             ty::ty_rptr(_, self_mt) if default_method_hack(self_mt) => {
 673                 (self_ty,
 674                  ty::AutoDerefRef(ty::AutoDerefRef {
 675                      autoderefs: autoderefs,
 676                      autoref: None}))
 677             }
 678             ty::ty_rptr(_, self_mt) => {
 679                 let region =
 680                     self.infcx().next_region_var(
 681                         infer::Autoref(self.expr.span));
 682                 (ty::mk_rptr(tcx, region, self_mt),
 683                  ty::AutoDerefRef(ty::AutoDerefRef {
 684                      autoderefs: autoderefs+1,
 685                      autoref: Some(ty::AutoPtr(region, self_mt.mutbl))}))
 686             }
 687             ty::ty_vec(self_mt, vstore_slice(_)) => {
 688                 let region =
 689                     self.infcx().next_region_var(
 690                         infer::Autoref(self.expr.span));
 691                 (ty::mk_vec(tcx, self_mt, vstore_slice(region)),
 692                  ty::AutoDerefRef(ty::AutoDerefRef {
 693                      autoderefs: autoderefs,
 694                      autoref: Some(ty::AutoBorrowVec(region, self_mt.mutbl))}))
 695             }
 696             ty_trait(did, ref substs, ty::RegionTraitStore(_), mutbl, bounds) => {
 697                 let region =
 698                     self.infcx().next_region_var(
 699                         infer::Autoref(self.expr.span));
 700                 (ty::mk_trait(tcx, did, substs.clone(),
 701                               ty::RegionTraitStore(region),
 702                               mutbl, bounds),
 703                  ty::AutoDerefRef(ty::AutoDerefRef {
 704                      autoderefs: autoderefs,
 705                      autoref: Some(ty::AutoBorrowObj(region, mutbl))}))
 706             }
 707             _ => {
 708                 (self_ty,
 709                  ty::AutoDerefRef(ty::AutoDerefRef {
 710                      autoderefs: autoderefs,
 711                      autoref: None}))
 712             }
 713         };
 714
 715         fn default_method_hack(self_mt: ty::mt) -> bool {
 716             // FIXME(#6129). Default methods can't deal with autoref.
 717             //
 718             // I am a horrible monster and I pray for death. Currently
 719             // the default method code fails when you try to reborrow
 720             // because it is not handling types correctly. In lieu of
 721             // fixing that, I am introducing this horrible hack. - ndm
 722             self_mt.mutbl == MutImmutable && ty::type_is_self(self_mt.ty)
 723         }
 724     }
 725
 726     fn search_for_autosliced_method(&self,
 727                                     self_ty: ty::t,
 728                                     autoderefs: uint)
 729                                     -> Option<MethodCallee> {
 730         /*!
 731          *
 732          * Searches for a candidate by converting things like
 733          * `~[]` to `&[]`. */
 734
 735         let tcx = self.tcx();
 736         let sty = ty::get(self_ty).sty.clone();
 737         match sty {
 738             ty_vec(mt, vstore_uniq) |
 739             ty_vec(mt, vstore_slice(_)) | // NDM(#3148)
 740             ty_vec(mt, vstore_fixed(_)) => {
 741                 // First try to borrow to a slice
 742                 let entry = self.search_for_some_kind_of_autorefd_method(
 743                     AutoBorrowVec, autoderefs, [MutImmutable, MutMutable],
 744                     |m,r| ty::mk_vec(tcx,
 745                                      ty::mt {ty:mt.ty, mutbl:m},
 746                                      vstore_slice(r)));
 747
 748                 if entry.is_some() { return entry; }
 749
 750                 // Then try to borrow to a slice *and* borrow a pointer.
 751                 self.search_for_some_kind_of_autorefd_method(
 752                     AutoBorrowVecRef, autoderefs, [MutImmutable, MutMutable],
 753                     |m,r| {
 754                         let slice_ty = ty::mk_vec(tcx,
 755                                                   ty::mt {ty:mt.ty, mutbl:m},
 756                                                   vstore_slice(r));
 757                         // NB: we do not try to autoref to a mutable
 758                         // pointer. That would be creating a pointer
 759                         // to a temporary pointer (the borrowed
 760                         // slice), so any update the callee makes to
 761                         // it can't be observed.
 762                         ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:MutImmutable})
 763                     })
 764             }
 765
 766             ty_str(vstore_uniq) |
 767             ty_str(vstore_fixed(_)) => {
 768                 let entry = self.search_for_some_kind_of_autorefd_method(
 769                     AutoBorrowVec, autoderefs, [MutImmutable],
 770                     |_m,r| ty::mk_str(tcx, vstore_slice(r)));
 771
 772                 if entry.is_some() { return entry; }
 773
 774                 self.search_for_some_kind_of_autorefd_method(
 775                     AutoBorrowVecRef, autoderefs, [MutImmutable],
 776                     |m,r| {
 777                         let slice_ty = ty::mk_str(tcx, vstore_slice(r));
 778                         ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:m})
 779                     })
 780             }
 781
 782             ty_trait(trt_did, trt_substs, _, _, b) => {
 783                 // Coerce ~/@/&Trait instances to &Trait.
 784
 785                 self.search_for_some_kind_of_autorefd_method(
 786                     AutoBorrowObj, autoderefs, [MutImmutable, MutMutable],
 787                     |trt_mut, reg| {
 788                         ty::mk_trait(tcx, trt_did, trt_substs.clone(),
 789                                      RegionTraitStore(reg), trt_mut, b)
 790                     })
 791             }
 792
 793             ty_closure(..) => {
 794                 // This case should probably be handled similarly to
 795                 // Trait instances.
 796                 None
 797             }
 798
 799             _ => None
 800         }
 801     }
 802
 803     fn search_for_autoptrd_method(&self, self_ty: ty::t, autoderefs: uint)
 804                                   -> Option<MethodCallee> {
 805         /*!
 806          *
 807          * Converts any type `T` to `&M T` where `M` is an
 808          * appropriate mutability.
 809          */
 810
 811         let tcx = self.tcx();
 812         match ty::get(self_ty).sty {
 813             ty_bare_fn(..) | ty_box(..) | ty_uniq(..) | ty_rptr(..) |
 814             ty_infer(IntVar(_)) |
 815             ty_infer(FloatVar(_)) |
 816             ty_self(_) | ty_param(..) | ty_nil | ty_bot | ty_bool |
 817             ty_char | ty_int(..) | ty_uint(..) |
 818             ty_float(..) | ty_enum(..) | ty_ptr(..) | ty_struct(..) | ty_tup(..) |
 819             ty_str(..) | ty_vec(..) | ty_trait(..) | ty_closure(..) => {
 820                 self.search_for_some_kind_of_autorefd_method(
 821                     AutoPtr, autoderefs, [MutImmutable, MutMutable],
 822                     |m,r| ty::mk_rptr(tcx, r, ty::mt {ty:self_ty, mutbl:m}))
 823             }
 824
 825             ty_err => None,
 826
 827             ty_unboxed_vec(_) | ty_infer(TyVar(_)) => {
 828                 self.bug(format!("unexpected type: {}",
 829                               self.ty_to_str(self_ty)));
 830             }
 831         }
 832     }
 833
 834     fn search_for_some_kind_of_autorefd_method(
 835             &self,
 836             kind: |Region, ast::Mutability| -> ty::AutoRef,
 837             autoderefs: uint,
 838             mutbls: &[ast::Mutability],
 839             mk_autoref_ty: |ast::Mutability, ty::Region| -> ty::t)
 840             -> Option<MethodCallee> {
 841         // This is hokey. We should have mutability inference as a
 842         // variable.  But for now, try &const, then &, then &mut:
 843         let region =
 844             self.infcx().next_region_var(
 845                 infer::Autoref(self.expr.span));
 846         for mutbl in mutbls.iter() {
 847             let autoref_ty = mk_autoref_ty(*mutbl, region);
 848             match self.search_for_method(autoref_ty) {
 849                 None => {}
 850                 Some(mme) => {
 851                     self.fcx.write_adjustment(
 852                         self.self_expr.id,
 853                         @ty::AutoDerefRef(ty::AutoDerefRef {
 854                             autoderefs: autoderefs,
 855                             autoref: Some(kind(region, *mutbl))}));
 856                     return Some(mme);
 857                 }
 858             }
 859         }
 860         return None;
 861     }
 862
 863     fn search_for_method(&self, rcvr_ty: ty::t)
 864                          -> Option<MethodCallee> {
 865         debug!("search_for_method(rcvr_ty={})", self.ty_to_str(rcvr_ty));
 866         let _indenter = indenter();
 867
 868         // I am not sure that inherent methods should have higher
 869         // priority, but it is necessary ATM to handle some of the
 870         // existing code.
 871
 872         debug!("searching inherent candidates");
 873         let mut inherent_candidates = self.inherent_candidates.borrow_mut();
 874         match self.consider_candidates(rcvr_ty, inherent_candidates.get()) {
 875             None => {}
 876             Some(mme) => {
 877                 return Some(mme);
 878             }
 879         }
 880
 881         debug!("searching extension candidates");
 882         let mut extension_candidates = self.extension_candidates.borrow_mut();
 883         match self.consider_candidates(rcvr_ty, extension_candidates.get()) {
 884             None => {
 885                 return None;
 886             }
 887             Some(mme) => {
 888                 return Some(mme);
 889             }
 890         }
 891     }
 892
 893     fn consider_candidates(&self,
 894                            rcvr_ty: ty::t,
 895                            candidates: &mut ~[Candidate])
 896                            -> Option<MethodCallee> {
 897         // FIXME(pcwalton): Do we need to clone here?
 898         let relevant_candidates: ~[Candidate] =
 899             candidates.iter().map(|c| (*c).clone()).
 900                 filter(|c| self.is_relevant(rcvr_ty, c)).collect();
 901
 902         let relevant_candidates = self.merge_candidates(relevant_candidates);
 903
 904         if relevant_candidates.len() == 0 {
 905             return None;
 906         }
 907
 908         if relevant_candidates.len() > 1 {
 909             self.tcx().sess.span_err(
 910                 self.expr.span,
 911                 "multiple applicable methods in scope");
 912             for (idx, candidate) in relevant_candidates.iter().enumerate() {
 913                 self.report_candidate(idx, &candidate.origin);
 914             }
 915         }
 916
 917         Some(self.confirm_candidate(rcvr_ty, &relevant_candidates[0]))
 918     }
 919
 920     fn merge_candidates(&self, candidates: &[Candidate]) -> ~[Candidate] {
 921         let mut merged = ~[];
 922         let mut i = 0;
 923         while i < candidates.len() {
 924             let candidate_a = &candidates[i];
 925
 926             let mut skip = false;
 927
 928             let mut j = i + 1;
 929             while j < candidates.len() {
 930                 let candidate_b = &candidates[j];
 931                 debug!("attempting to merge {:?} and {:?}",
 932                        candidate_a, candidate_b);
 933                 let candidates_same = match (&candidate_a.origin,
 934                                              &candidate_b.origin) {
 935                     (&MethodParam(ref p1), &MethodParam(ref p2)) => {
 936                         let same_trait = p1.trait_id == p2.trait_id;
 937                         let same_method = p1.method_num == p2.method_num;
 938                         let same_param = p1.param_num == p2.param_num;
 939                         // The bound number may be different because
 940                         // multiple bounds may lead to the same trait
 941                         // impl
 942                         same_trait && same_method && same_param
 943                     }
 944                     _ => false
 945                 };
 946                 if candidates_same {
 947                     skip = true;
 948                     break;
 949                 }
 950                 j += 1;
 951             }
 952
 953             i += 1;
 954
 955             if skip {
 956                 // There are more than one of these and we need only one
 957                 continue;
 958             } else {
 959                 merged.push(candidate_a.clone());
 960             }
 961         }
 962
 963         return merged;
 964     }
 965
 966     fn confirm_candidate(&self, rcvr_ty: ty::t, candidate: &Candidate)
 967                          -> MethodCallee {
 968         // This method performs two sets of substitutions, one after the other:
 969         // 1. Substitute values for any type/lifetime parameters from the impl and
 970         //    method declaration into the method type. This is the function type
 971         //    before it is called; it may still include late bound region variables.
 972         // 2. Instantiate any late bound lifetime parameters in the method itself
 973         //    with fresh region variables.
 974
 975         let tcx = self.tcx();
 976
 977         debug!("confirm_candidate(expr={}, candidate={})",
 978                self.expr.repr(tcx),
 979                self.cand_to_str(candidate));
 980
 981         self.enforce_object_limitations(candidate);
 982         self.enforce_drop_trait_limitations(candidate);
 983
 984         // static methods should never have gotten this far:
 985         assert!(candidate.method_ty.explicit_self != SelfStatic);
 986
 987         // Determine the values for the type parameters of the method.
 988         // If they were not explicitly supplied, just construct fresh
 989         // type variables.
 990         let num_supplied_tps = self.supplied_tps.len();
 991         let num_method_tps = candidate.method_ty.generics.type_param_defs().len();
 992         let m_substs = {
 993             if num_supplied_tps == 0u {
 994                 self.fcx.infcx().next_ty_vars(num_method_tps)
 995             } else if num_method_tps == 0u {
 996                 tcx.sess.span_err(
 997                     self.expr.span,
 998                     "this method does not take type parameters");
 999                 self.fcx.infcx().next_ty_vars(num_method_tps)
1000             } else if num_supplied_tps != num_method_tps {
1001                 tcx.sess.span_err(
1002                     self.expr.span,
1003                     "incorrect number of type \
1004                      parameters given for this method");
1005                 self.fcx.infcx().next_ty_vars(num_method_tps)
1006             } else {
1007                 self.supplied_tps.to_owned()
1008             }
1009         };
1010
1011         // Construct the full set of type parameters for the method,
1012         // which is equal to the class tps + the method tps.
1013         let all_substs = substs {
1014             tps: vec::append(candidate.rcvr_substs.tps.clone(), m_substs),
1015             regions: candidate.rcvr_substs.regions.clone(),
1016             self_ty: candidate.rcvr_substs.self_ty,
1017         };
1018
1019         let ref bare_fn_ty = candidate.method_ty.fty;
1020
1021         // Compute the method type with type parameters substituted
1022         debug!("fty={} all_substs={}",
1023                bare_fn_ty.repr(tcx),
1024                ty::substs_to_str(tcx, &all_substs));
1025
1026         let fn_sig = &bare_fn_ty.sig;
1027         let inputs = match candidate.origin {
1028             MethodObject(..) => {
1029                 // For annoying reasons, we've already handled the
1030                 // substitution of self for object calls.
1031                 let args = fn_sig.inputs.slice_from(1).iter().map(|t| {
1032                     t.subst(tcx, &all_substs)
1033                 });
1034                 Some(fn_sig.inputs[0]).move_iter().chain(args).collect()
1035             }
1036             _ => fn_sig.inputs.subst(tcx, &all_substs)
1037         };
1038         let fn_sig = ty::FnSig {
1039             binder_id: fn_sig.binder_id,
1040             inputs: inputs,
1041             output: fn_sig.output.subst(tcx, &all_substs),
1042             variadic: fn_sig.variadic
1043         };
1044
1045         debug!("after subst, fty={}", fn_sig.repr(tcx));
1046
1047         // Replace any bound regions that appear in the function
1048         // signature with region variables
1049         let (_, fn_sig) = replace_bound_regions_in_fn_sig( tcx, &fn_sig, |br| {
1050             self.fcx.infcx().next_region_var(
1051                 infer::BoundRegionInFnCall(self.expr.span, br))
1052         });
1053         let transformed_self_ty = fn_sig.inputs[0];
1054         let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
1055             sig: fn_sig,
1056             purity: bare_fn_ty.purity,
1057             abis: bare_fn_ty.abis.clone(),
1058         });
1059         debug!("after replacing bound regions, fty={}", self.ty_to_str(fty));
1060
1061         // before we only checked whether self_ty could be a subtype
1062         // of rcvr_ty; now we actually make it so (this may cause
1063         // variables to unify etc).  Since we checked beforehand, and
1064         // nothing has changed in the meantime, this unification
1065         // should never fail.
1066         match self.fcx.mk_subty(false, infer::Misc(self.self_expr.span),
1067                                 rcvr_ty, transformed_self_ty) {
1068             result::Ok(_) => {}
1069             result::Err(_) => {
1070                 self.bug(format!("{} was a subtype of {} but now is not?",
1071                               self.ty_to_str(rcvr_ty),
1072                               self.ty_to_str(transformed_self_ty)));
1073             }
1074         }
1075
1076         MethodCallee {
1077             origin: candidate.origin,
1078             ty: fty,
1079             substs: all_substs
1080         }
1081     }
1082
1083     fn construct_transformed_self_ty_for_object(
1084         &self,
1085         trait_def_id: ast::DefId,
1086         rcvr_substs: &ty::substs,
1087         method_ty: &ty::Method) -> ty::t
1088     {
1089         /*!
1090          * This is a bit tricky. We have a match against a trait method
1091          * being invoked on an object, and we want to generate the
1092          * self-type. As an example, consider a trait
1093          *
1094          *     trait Foo {
1095          *         fn r_method<'a>(&'a self);
1096          *         fn u_method(~self);
1097          *     }
1098          *
1099          * Now, assuming that `r_method` is being called, we want the
1100          * result to be `&'a Foo`. Assuming that `u_method` is being
1101          * called, we want the result to be `~Foo`. Of course,
1102          * this transformation has already been done as part of
1103          * `method_ty.fty.sig.inputs[0]`, but there the type
1104          * is expressed in terms of `Self` (i.e., `&'a Self`, `~Self`).
1105          * Because objects are not standalone types, we can't just substitute
1106          * `s/Self/Foo/`, so we must instead perform this kind of hokey
1107          * match below.
1108          */
1109
1110         let substs = ty::substs {regions: rcvr_substs.regions.clone(),
1111                                  self_ty: None,
1112                                  tps: rcvr_substs.tps.clone()};
1113         match method_ty.explicit_self {
1114             ast::SelfStatic => {
1115                 self.bug(~"static method for object type receiver");
1116             }
1117             ast::SelfValue => {
1118                 ty::mk_err() // error reported in `enforce_object_limitations()`
1119             }
1120             ast::SelfRegion(..) | ast::SelfUniq => {
1121                 let transformed_self_ty = method_ty.fty.sig.inputs[0];
1122                 match ty::get(transformed_self_ty).sty {
1123                     ty::ty_rptr(r, mt) => { // must be SelfRegion
1124                         ty::mk_trait(self.tcx(), trait_def_id,
1125                                      substs, RegionTraitStore(r), mt.mutbl,
1126                                      ty::EmptyBuiltinBounds())
1127                     }
1128                     ty::ty_uniq(_) => { // must be SelfUniq
1129                         ty::mk_trait(self.tcx(), trait_def_id,
1130                                      substs, UniqTraitStore, ast::MutImmutable,
1131                                      ty::EmptyBuiltinBounds())
1132                     }
1133                     _ => {
1134                         self.bug(
1135                             format!("'impossible' transformed_self_ty: {}",
1136                                  transformed_self_ty.repr(self.tcx())));
1137                     }
1138                 }
1139             }
1140         }
1141     }
1142
1143     fn enforce_object_limitations(&self, candidate: &Candidate) {
1144         /*!
1145          * There are some limitations to calling functions through an
1146          * object, because (a) the self type is not known
1147          * (that's the whole point of a trait instance, after all, to
1148          * obscure the self type) and (b) the call must go through a
1149          * vtable and hence cannot be monomorphized.
1150          */
1151
1152         match candidate.origin {
1153             MethodStatic(..) | MethodParam(..) => {
1154                 return; // not a call to a trait instance
1155             }
1156             MethodObject(..) => {}
1157         }
1158
1159         match candidate.method_ty.explicit_self {
1160             ast::SelfStatic => { // reason (a) above
1161                 self.tcx().sess.span_err(
1162                     self.expr.span,
1163                     "cannot call a method without a receiver \
1164                      through an object");
1165             }
1166
1167             ast::SelfValue => { // reason (a) above
1168                 self.tcx().sess.span_err(
1169                     self.expr.span,
1170                     "cannot call a method with a by-value receiver \
1171                      through an object");
1172             }
1173
1174             ast::SelfRegion(..) | ast::SelfUniq => {}
1175         }
1176
1177         // reason (a) above
1178         let check_for_self_ty = |ty| {
1179             if ty::type_has_self(ty) {
1180                 self.tcx().sess.span_err(
1181                     self.expr.span,
1182                     "cannot call a method whose type contains a \
1183                      self-type through an object");
1184                 true
1185             } else {
1186                 false
1187             }
1188         };
1189         let ref sig = candidate.method_ty.fty.sig;
1190         let mut found_self_ty = false;
1191         for &input_ty in sig.inputs.iter() {
1192             if check_for_self_ty(input_ty) {
1193                 found_self_ty = true;
1194                 break;
1195             }
1196         }
1197         if !found_self_ty {
1198             check_for_self_ty(sig.output);
1199         }
1200
1201         if candidate.method_ty.generics.has_type_params() { // reason (b) above
1202             self.tcx().sess.span_err(
1203                 self.expr.span,
1204                 "cannot call a generic method through an object");
1205         }
1206     }
1207
1208     fn enforce_drop_trait_limitations(&self, candidate: &Candidate) {
1209         // No code can call the finalize method explicitly.
1210         let bad;
1211         match candidate.origin {
1212             MethodStatic(method_id) => {
1213                 let destructors = self.tcx().destructors.borrow();
1214                 bad = destructors.get().contains(&method_id);
1215             }
1216             // FIXME: does this properly enforce this on everything now
1217             // that self has been merged in? -sully
1218             MethodParam(MethodParam { trait_id: trait_id, .. }) |
1219             MethodObject(MethodObject { trait_id: trait_id, .. }) => {
1220                 let destructor_for_type = self.tcx()
1221                                               .destructor_for_type
1222                                               .borrow();
1223                 bad = destructor_for_type.get().contains_key(&trait_id);
1224             }
1225         }
1226
1227         if bad {
1228             self.tcx().sess.span_err(self.expr.span,
1229                                      "explicit call to destructor");
1230         }
1231     }
1232
1233     // `rcvr_ty` is the type of the expression. It may be a subtype of a
1234     // candidate method's `self_ty`.
1235     fn is_relevant(&self, rcvr_ty: ty::t, candidate: &Candidate) -> bool {
1236         debug!("is_relevant(rcvr_ty={}, candidate={})",
1237                self.ty_to_str(rcvr_ty), self.cand_to_str(candidate));
1238
1239         return match candidate.method_ty.explicit_self {
1240             SelfStatic => {
1241                 debug!("(is relevant?) explicit self is static");
1242                 false
1243             }
1244
1245             SelfValue => {
1246                 rcvr_matches_ty(self.fcx, rcvr_ty, candidate)
1247             }
1248
1249             SelfRegion(_, m) => {
1250                 debug!("(is relevant?) explicit self is a region");
1251                 match ty::get(rcvr_ty).sty {
1252                     ty::ty_rptr(_, mt) => {
1253                         mutability_matches(mt.mutbl, m) &&
1254                         rcvr_matches_ty(self.fcx, mt.ty, candidate)
1255                     }
1256
1257                     ty::ty_trait(self_did, _, RegionTraitStore(_), self_m, _) => {
1258                         mutability_matches(self_m, m) &&
1259                         rcvr_matches_object(self_did, candidate)
1260                     }
1261
1262                     _ => false
1263                 }
1264             }
1265
1266             SelfUniq => {
1267                 debug!("(is relevant?) explicit self is a unique pointer");
1268                 match ty::get(rcvr_ty).sty {
1269                     ty::ty_uniq(typ) => {
1270                         rcvr_matches_ty(self.fcx, typ, candidate)
1271                     }
1272
1273                     ty::ty_trait(self_did, _, UniqTraitStore, _, _) => {
1274                         rcvr_matches_object(self_did, candidate)
1275                     }
1276
1277                     _ => false
1278                 }
1279             }
1280         };
1281
1282         fn rcvr_matches_object(self_did: ast::DefId,
1283                                candidate: &Candidate) -> bool {
1284             match candidate.rcvr_match_condition {
1285                 RcvrMatchesIfObject(desired_did) => {
1286                     self_did == desired_did
1287                 }
1288                 RcvrMatchesIfSubtype(_) => {
1289                     false
1290                 }
1291             }
1292         }
1293
1294         fn rcvr_matches_ty(fcx: @FnCtxt,
1295                            rcvr_ty: ty::t,
1296                            candidate: &Candidate) -> bool {
1297             match candidate.rcvr_match_condition {
1298                 RcvrMatchesIfObject(_) => {
1299                     false
1300                 }
1301                 RcvrMatchesIfSubtype(of_type) => {
1302                     fcx.can_mk_subty(rcvr_ty, of_type).is_ok()
1303                 }
1304             }
1305         }
1306
1307         fn mutability_matches(self_mutbl: ast::Mutability,
1308                               candidate_mutbl: ast::Mutability)
1309                               -> bool {
1310             //! True if `self_mutbl <: candidate_mutbl`
1311             self_mutbl == candidate_mutbl
1312         }
1313     }
1314
1315     fn report_candidate(&self, idx: uint, origin: &MethodOrigin) {
1316         match *origin {
1317             MethodStatic(impl_did) => {
1318                 // If it is an instantiated default method, use the original
1319                 // default method for error reporting.
1320                 let did = match provided_source(self.tcx(), impl_did) {
1321                     None => impl_did,
1322                     Some(did) => did
1323                 };
1324                 self.report_static_candidate(idx, did)
1325             }
1326             MethodParam(ref mp) => {
1327                 self.report_param_candidate(idx, (*mp).trait_id)
1328             }
1329             MethodObject(ref mo) => {
1330                 self.report_trait_candidate(idx, mo.trait_id)
1331             }
1332         }
1333     }
1334
1335     fn report_static_candidate(&self, idx: uint, did: DefId) {
1336         let span = if did.krate == ast::LOCAL_CRATE {
1337             self.tcx().map.span(did.node)
1338         } else {
1339             self.expr.span
1340         };
1341         self.tcx().sess.span_note(
1342             span,
1343             format!("candidate \\#{} is `{}`",
1344                  idx+1u,
1345                  ty::item_path_str(self.tcx(), did)));
1346     }
1347
1348     fn report_param_candidate(&self, idx: uint, did: DefId) {
1349         self.tcx().sess.span_note(
1350             self.expr.span,
1351             format!("candidate \\#{} derives from the bound `{}`",
1352                  idx+1u,
1353                  ty::item_path_str(self.tcx(), did)));
1354     }
1355
1356     fn report_trait_candidate(&self, idx: uint, did: DefId) {
1357         self.tcx().sess.span_note(
1358             self.expr.span,
1359             format!("candidate \\#{} derives from the type of the receiver, \
1360                   which is the trait `{}`",
1361                  idx+1u,
1362                  ty::item_path_str(self.tcx(), did)));
1363     }
1364
1365     fn infcx(&'a self) -> &'a infer::InferCtxt {
1366         &self.fcx.inh.infcx
1367     }
1368
1369     fn tcx(&self) -> ty::ctxt {
1370         self.fcx.tcx()
1371     }
1372
1373     fn ty_to_str(&self, t: ty::t) -> ~str {
1374         self.fcx.infcx().ty_to_str(t)
1375     }
1376
1377     fn cand_to_str(&self, cand: &Candidate) -> ~str {
1378         format!("Candidate(rcvr_ty={}, rcvr_substs={}, origin={:?})",
1379              cand.rcvr_match_condition.repr(self.tcx()),
1380              ty::substs_to_str(self.tcx(), &cand.rcvr_substs),
1381              cand.origin)
1382     }
1383
1384     fn did_to_str(&self, did: DefId) -> ~str {
1385         ty::item_path_str(self.tcx(), did)
1386     }
1387
1388     fn bug(&self, s: ~str) -> ! {
1389         self.tcx().sess.span_bug(self.self_expr.span, s)
1390     }
1391 }
1392
1393 impl Repr for RcvrMatchCondition {
1394     fn repr(&self, tcx: ty::ctxt) -> ~str {
1395         match *self {
1396             RcvrMatchesIfObject(d) => {
1397                 format!("RcvrMatchesIfObject({})", d.repr(tcx))
1398             }
1399             RcvrMatchesIfSubtype(t) => {
1400                 format!("RcvrMatchesIfSubtype({})", t.repr(tcx))
1401             }
1402         }
1403     }
1404 }