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