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