Rewrite method resolution to be cleaner, more correct, and to lay

groundwork for better performance.

Key points:

- Separate out determining which method to use from actually selecting
  a method (this should enable caching, as well as the pcwalton fast-reject strategy).
- Merge the impl selection back into method resolution and don't rely on
  trait matching (this should perform better but also is needed to resolve some
  kind of conflicts, see e.g. `method-two-traits-distinguished-via-where-clause.rs`)
- Purge a lot of out-of-date junk and coercions from method lookups.

23 files changed, 2396 insertions, 2070 deletions

diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 7a34c5977d6..ce736a344d5 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -29,7 +29,7 @@ This API is completely unstable and subject to change.
       html_root_url = "http://doc.rust-lang.org/nightly/")]
 
 #![feature(default_type_params, globs, if_let, import_shadowing, macro_rules, phase, quote)]
-#![feature(slicing_syntax, struct_variant, unsafe_destructor)]
+#![feature(slicing_syntax, struct_variant, tuple_indexing, unsafe_destructor)]
 #![feature(rustc_diagnostic_macros)]
 
 extern crate arena;
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index 1db8cf6baf3..9e0abb897f7 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -281,6 +281,16 @@ pub fn overlapping_impls(infcx: &InferCtxt,
     coherence::impl_can_satisfy(infcx, impl2_def_id, impl1_def_id)
 }
 
+pub fn impl_obligations(tcx: &ty::ctxt,
+                        cause: ObligationCause,
+                        impl_def_id: ast::DefId,
+                        impl_substs: &subst::Substs)
+                        -> subst::VecPerParamSpace<Obligation>
+{
+    let impl_generics = ty::lookup_item_type(tcx, impl_def_id).generics;
+    obligations_for_generics(tcx, cause, &impl_generics, impl_substs)
+}
+
 pub fn obligations_for_generics(tcx: &ty::ctxt,
                                 cause: ObligationCause,
                                 generics: &ty::Generics,
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 9ab2f948f9d..7ea58be3480 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -1714,7 +1714,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 closure_type.sig.binder_id,
                 &closure_type.sig,
                 |br| self.infcx.next_region_var(
-                         infer::LateBoundRegion(obligation.cause.span, br)));
+                         infer::LateBoundRegion(obligation.cause.span, br,
+                                                infer::FnCall)));
 
         let arguments_tuple = new_signature.inputs[0];
         let trait_ref = Rc::new(ty::TraitRef {
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 134dac9d3a7..52b29ff8b2e 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -3491,43 +3491,45 @@ pub fn adjust_ty(cx: &ctxt,
                         }
                     }
 
-                    match adj.autoref {
-                        None => adjusted_ty,
-                        Some(ref autoref) => adjust_for_autoref(cx, span, adjusted_ty, autoref)
-                    }
+                    adjust_ty_for_autoref(cx, span, adjusted_ty, adj.autoref.as_ref())
                 }
             }
         }
         None => unadjusted_ty
     };
+}
 
-    fn adjust_for_autoref(cx: &ctxt,
-                          span: Span,
-                          ty: ty::t,
-                          autoref: &AutoRef) -> ty::t{
-        match *autoref {
-            AutoPtr(r, m, ref a) => {
-                let adjusted_ty = match a {
-                    &Some(box ref a) => adjust_for_autoref(cx, span, ty, a),
-                    &None => ty
-                };
-                mk_rptr(cx, r, mt {
-                    ty: adjusted_ty,
-                    mutbl: m
-                })
-            }
+pub fn adjust_ty_for_autoref(cx: &ctxt,
+                             span: Span,
+                             ty: ty::t,
+                             autoref: Option<&AutoRef>)
+                             -> ty::t
+{
+    match autoref {
+        None => ty,
 
-            AutoUnsafe(m, ref a) => {
-                let adjusted_ty = match a {
-                    &Some(box ref a) => adjust_for_autoref(cx, span, ty, a),
-                    &None => ty
-                };
-                mk_ptr(cx, mt {ty: adjusted_ty, mutbl: m})
-            }
+        Some(&AutoPtr(r, m, ref a)) => {
+            let adjusted_ty = match a {
+                &Some(box ref a) => adjust_ty_for_autoref(cx, span, ty, Some(a)),
+                &None => ty
+            };
+            mk_rptr(cx, r, mt {
+                ty: adjusted_ty,
+                mutbl: m
+            })
+        }
 
-            AutoUnsize(ref k) => unsize_ty(cx, ty, k, span),
-            AutoUnsizeUniq(ref k) => ty::mk_uniq(cx, unsize_ty(cx, ty, k, span)),
+        Some(&AutoUnsafe(m, ref a)) => {
+            let adjusted_ty = match a {
+                &Some(box ref a) => adjust_ty_for_autoref(cx, span, ty, Some(a)),
+                &None => ty
+            };
+            mk_ptr(cx, mt {ty: adjusted_ty, mutbl: m})
         }
+
+        Some(&AutoUnsize(ref k)) => unsize_ty(cx, ty, k, span),
+
+        Some(&AutoUnsizeUniq(ref k)) => ty::mk_uniq(cx, unsize_ty(cx, ty, k, span)),
     }
 }
 
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
deleted file mode 100644
index 59b8309383c..00000000000
--- a/src/librustc/middle/typeck/check/method.rs
+++ /dev/null
@@ -1,1903 +0,0 @@
-// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-/*!
-
-# Method lookup
-
-Method lookup can be rather complex due to the interaction of a number
-of factors, such as self types, autoderef, trait lookup, etc.  The
-algorithm is divided into two parts: candidate collection and
-candidate selection.
-
-## Candidate collection
-
-A `Candidate` is a method item that might plausibly be the method
-being invoked.  Candidates are grouped into two kinds, inherent and
-extension.  Inherent candidates are those that are derived from the
-type of the receiver itself.  So, if you have a receiver of some
-nominal type `Foo` (e.g., a struct), any methods defined within an
-impl like `impl Foo` are inherent methods.  Nothing needs to be
-imported to use an inherent method, they are associated with the type
-itself (note that inherent impls can only be defined in the same
-module as the type itself).
-
-Inherent candidates are not always derived from impls.  If you have a
-trait instance, such as a value of type `Box<ToString>`, then the trait
-methods (`to_string()`, in this case) are inherently associated with it.
-Another case is type parameters, in which case the methods of their
-bounds are inherent.
-
-Extension candidates are derived from imported traits.  If I have the
-trait `ToString` imported, and I call `to_string()` on a value of type `T`,
-then we will go off to find out whether there is an impl of `ToString`
-for `T`.  These kinds of method calls are called "extension methods".
-They can be defined in any module, not only the one that defined `T`.
-Furthermore, you must import the trait to call such a method.
-
-For better or worse, we currently give weight to inherent methods over
-extension methods during candidate selection (below).
-
-## Candidate selection
-
-Once we know the set of candidates, we can go off and try to select
-which one is actually being called.  We do this by taking the type of
-the receiver, let's call it R, and checking whether it matches against
-the expected receiver type for each of the collected candidates.  We
-first check for inherent candidates and see whether we get exactly one
-match (zero means keep searching, more than one is an error).  If so,
-we return that as the candidate.  Otherwise we search the extension
-candidates in the same way.
-
-If find no matching candidate at all, we proceed to auto-deref the
-receiver type and search again.  We keep doing that until we cannot
-auto-deref any longer.  At each step, we also check for candidates
-based on "autoptr", which if the current type is `T`, checks for `&mut
-T`, `&const T`, and `&T` receivers.  Finally, at the very end, we will
-also try autoslice, which converts `~[]` to `&[]` (there is no point
-at trying autoslice earlier, because no autoderefable type is also
-sliceable).
-
-## Why two phases?
-
-You might wonder why we first collect the candidates and then select.
-Both the inherent candidate collection and the candidate selection
-proceed by progressively deref'ing the receiver type, after all.  The
-answer is that two phases are needed to elegantly deal with explicit
-self.  After all, if there is an impl for the type `Foo`, it can
-define a method with the type `Box<self>`, which means that it expects a
-receiver of type `Box<Foo>`.  If we have a receiver of type `Box<Foo>`, but we
-waited to search for that impl until we have deref'd the `Box` away and
-obtained the type `Foo`, we would never match this method.
-
-*/
-
-pub use self::CheckTraitsFlag::*;
-pub use self::AutoderefReceiverFlag::*;
-pub use self::MethodError::*;
-pub use self::CandidateSource::*;
-
-use middle::subst;
-use middle::subst::{Subst, SelfSpace};
-use middle::traits;
-use middle::ty::*;
-use middle::ty;
-use middle::typeck::astconv::AstConv;
-use middle::typeck::check::{FnCtxt, NoPreference, PreferMutLvalue};
-use middle::typeck::check::{impl_self_ty};
-use middle::typeck::check::vtable::select_new_fcx_obligations;
-use middle::typeck::check;
-use middle::typeck::infer;
-use middle::typeck::{MethodCall, MethodCallee};
-use middle::typeck::{MethodOrigin, MethodParam, MethodTypeParam};
-use middle::typeck::{MethodStatic, MethodStaticUnboxedClosure, MethodObject, MethodTraitObject};
-use middle::typeck::check::regionmanip::replace_late_bound_regions;
-use middle::typeck::TypeAndSubsts;
-use middle::typeck::check::vtable;
-use middle::ty_fold::TypeFoldable;
-use util::common::indenter;
-use util::ppaux;
-use util::ppaux::{Repr, UserString};
-
-use std::collections::HashSet;
-use std::rc::Rc;
-use syntax::ast::{DefId, MutImmutable, MutMutable};
-use syntax::ast;
-use syntax::codemap::Span;
-
-#[deriving(PartialEq)]
-pub enum CheckTraitsFlag {
-    CheckTraitsOnly,
-    CheckTraitsAndInherentMethods,
-}
-
-#[deriving(PartialEq)]
-pub enum AutoderefReceiverFlag {
-    AutoderefReceiver,
-    DontAutoderefReceiver,
-}
-
-pub enum MethodError {
-    // Did not find an applicable method, but we did find various
-    // static methods that may apply.
-    NoMatch(Vec<CandidateSource>),
-
-    // Multiple methods might apply.
-    Ambiguity(Vec<CandidateSource>),
-}
-
-pub type MethodResult = Result<MethodCallee, MethodError>;
-
-pub fn lookup<'a, 'tcx>(
-    fcx: &'a FnCtxt<'a, 'tcx>,
-
-    // In a call `a.b::<X, Y, ...>(...)`:
-    expr: &ast::Expr,                   // The expression `a.b(...)`.
-    self_expr: &'a ast::Expr,           // The expression `a`.
-    m_name: ast::Name,                  // The name `b`.
-    self_ty: ty::t,                     // The type of `a`.
-    supplied_tps: &'a [ty::t],          // The list of types X, Y, ... .
-    deref_args: check::DerefArgs,       // Whether we autopointer first.
-    check_traits: CheckTraitsFlag,      // Whether we check traits only.
-    autoderef_receiver: AutoderefReceiverFlag)
-    -> MethodResult
-{
-    let mut lcx = LookupContext {
-        fcx: fcx,
-        span: expr.span,
-        self_expr: Some(self_expr),
-        m_name: m_name,
-        supplied_tps: supplied_tps,
-        impl_dups: HashSet::new(),
-        inherent_candidates: Vec::new(),
-        extension_candidates: Vec::new(),
-        static_candidates: Vec::new(),
-        deref_args: deref_args,
-        check_traits: check_traits,
-        autoderef_receiver: autoderef_receiver,
-    };
-
-    debug!("method lookup(self_ty={}, expr={}, self_expr={})",
-           self_ty.repr(fcx.tcx()), expr.repr(fcx.tcx()),
-           self_expr.repr(fcx.tcx()));
-
-    debug!("searching inherent candidates");
-    lcx.push_inherent_candidates(self_ty);
-    debug!("searching extension candidates");
-    lcx.push_bound_candidates(self_ty, None);
-    lcx.push_extension_candidates(expr.id);
-    lcx.search(self_ty)
-}
-
-pub fn lookup_in_trait<'a, 'tcx>(
-    fcx: &'a FnCtxt<'a, 'tcx>,
-    span: Span,
-    self_expr: Option<&'a ast::Expr>,
-    m_name: ast::Name,
-    trait_def_id: DefId,
-    self_ty: ty::t,
-    opt_input_types: Option<Vec<ty::t>>)
-    -> Option<MethodCallee>
-{
-    lookup_in_trait_adjusted(fcx, span, self_expr, m_name, trait_def_id,
-                             ty::AutoDerefRef { autoderefs: 0, autoref: None },
-                             self_ty, opt_input_types)
-}
-
-pub fn lookup_in_trait_adjusted<'a, 'tcx>(
-    fcx: &'a FnCtxt<'a, 'tcx>,
-    span: Span,
-    self_expr: Option<&'a ast::Expr>,
-    m_name: ast::Name,
-    trait_def_id: DefId,
-    autoderefref: ty::AutoDerefRef,
-    self_ty: ty::t,
-    opt_input_types: Option<Vec<ty::t>>)
-    -> Option<MethodCallee>
-{
-    debug!("method lookup_in_trait(self_ty={}, self_expr={}, m_name={}, trait_def_id={})",
-           self_ty.repr(fcx.tcx()),
-           self_expr.repr(fcx.tcx()),
-           m_name.repr(fcx.tcx()),
-           trait_def_id.repr(fcx.tcx()));
-
-    let trait_def = ty::lookup_trait_def(fcx.tcx(), trait_def_id);
-
-    let expected_number_of_input_types = trait_def.generics.types.len(subst::TypeSpace);
-    let input_types = match opt_input_types {
-        Some(input_types) => {
-            assert_eq!(expected_number_of_input_types, input_types.len());
-            input_types
-        }
-
-        None => {
-            fcx.inh.infcx.next_ty_vars(expected_number_of_input_types)
-        }
-    };
-
-    let number_assoc_types = trait_def.generics.types.len(subst::AssocSpace);
-    let assoc_types = fcx.inh.infcx.next_ty_vars(number_assoc_types);
-
-    assert_eq!(trait_def.generics.types.len(subst::FnSpace), 0);
-    assert!(trait_def.generics.regions.is_empty());
-
-    // Construct a trait-reference `self_ty : Trait<input_tys>`
-    let substs = subst::Substs::new_trait(input_types, Vec::new(), assoc_types, self_ty);
-    let trait_ref = Rc::new(ty::TraitRef::new(trait_def_id, substs));
-
-    // Construct an obligation
-    let obligation = traits::Obligation::misc(span, trait_ref.clone());
-
-    // Now we want to know if this can be matched
-    let mut selcx = traits::SelectionContext::new(fcx.infcx(),
-                                                  &fcx.inh.param_env,
-                                                  fcx);
-    if !selcx.evaluate_obligation(&obligation) {
-        debug!("--> Cannot match obligation");
-        return None; // Cannot be matched, no such method resolution is possible.
-    }
-
-    // Trait must have a method named `m_name` and it should not have
-    // type parameters or early-bound regions.
-    let tcx = fcx.tcx();
-    let (method_num, method_ty) = trait_method(tcx, trait_def_id, m_name).unwrap();
-    assert_eq!(method_ty.generics.types.len(subst::FnSpace), 0);
-    assert_eq!(method_ty.generics.regions.len(subst::FnSpace), 0);
-
-    // Substitute the trait parameters into the method type and
-    // instantiate late-bound regions to get the actual method type.
-    let ref bare_fn_ty = method_ty.fty;
-    let fn_sig = bare_fn_ty.sig.subst(tcx, &trait_ref.substs);
-    let fn_sig = replace_late_bound_regions_with_fresh_var(fcx.infcx(), span,
-                                                           fn_sig.binder_id, &fn_sig);
-    let transformed_self_ty = fn_sig.inputs[0];
-    let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
-        sig: fn_sig,
-        fn_style: bare_fn_ty.fn_style,
-        abi: bare_fn_ty.abi.clone(),
-    });
-
-    debug!("matched method fty={} obligation={}",
-           fty.repr(fcx.tcx()),
-           obligation.repr(fcx.tcx()));
-
-    // Register obligations for the parameters.  This will include the
-    // `Self` parameter, which in turn has a bound of the main trait,
-    // so this also effectively registers `obligation` as well.  (We
-    // used to register `obligation` explicitly, but that resulted in
-    // double error messages being reported.)
-    fcx.add_obligations_for_parameters(
-        traits::ObligationCause::misc(span),
-        &trait_ref.substs,
-        &method_ty.generics);
-
-    // FIXME(#18653) -- Try to resolve obligations, giving us more
-    // typing information, which can sometimes be needed to avoid
-    // pathological region inference failures.
-    vtable::select_new_fcx_obligations(fcx);
-
-    // Insert any adjustments needed (always an autoref of some mutability).
-    match self_expr {
-        None => { }
-
-        Some(self_expr) => {
-            debug!("inserting adjustment if needed (self-id = {}, \
-                   base adjustment = {}, explicit self = {})",
-                   self_expr.id, autoderefref, method_ty.explicit_self);
-
-            match method_ty.explicit_self {
-                ty::ByValueExplicitSelfCategory => {
-                    // Trait method is fn(self), no transformation needed.
-                    if !autoderefref.is_identity() {
-                        fcx.write_adjustment(
-                            self_expr.id,
-                            span,
-                            ty::AdjustDerefRef(autoderefref));
-                    }
-                }
-
-                ty::ByReferenceExplicitSelfCategory(..) => {
-                    // Trait method is fn(&self) or fn(&mut self), need an
-                    // autoref. Pull the region etc out of the type of first argument.
-                    match ty::get(transformed_self_ty).sty {
-                        ty::ty_rptr(region, ty::mt { mutbl, ty: _ }) => {
-                            let ty::AutoDerefRef { autoderefs, autoref } = autoderefref;
-                            let autoref = autoref.map(|r| box r);
-                            fcx.write_adjustment(
-                                self_expr.id,
-                                span,
-                                ty::AdjustDerefRef(ty::AutoDerefRef {
-                                    autoderefs: autoderefs,
-                                    autoref: Some(ty::AutoPtr(region, mutbl, autoref))
-                                }));
-                        }
-
-                        _ => {
-                            fcx.tcx().sess.span_bug(
-                                span,
-                                format!(
-                                    "trait method is &self but first arg is: {}",
-                                    transformed_self_ty.repr(fcx.tcx())).as_slice());
-                        }
-                    }
-                }
-
-                _ => {
-                    fcx.tcx().sess.span_bug(
-                        span,
-                        format!(
-                            "unexpected explicit self type in operator method: {}",
-                            method_ty.explicit_self).as_slice());
-                }
-            }
-        }
-    }
-
-    let callee = MethodCallee {
-        origin: MethodTypeParam(MethodParam{trait_ref: trait_ref.clone(),
-                                            method_num: method_num}),
-        ty: fty,
-        substs: trait_ref.substs.clone()
-    };
-
-    debug!("callee = {}", callee.repr(fcx.tcx()));
-
-    Some(callee)
-}
-
-pub fn report_error(fcx: &FnCtxt,
-                    span: Span,
-                    rcvr_ty: ty::t,
-                    method_name: ast::Name,
-                    error: MethodError)
-{
-    match error {
-        NoMatch(static_sources) => {
-            let cx = fcx.tcx();
-            let method_ustring = method_name.user_string(cx);
-
-            // True if the type is a struct and contains a field with
-            // the same name as the not-found method
-            let is_field = match ty::get(rcvr_ty).sty {
-                ty_struct(did, _) =>
-                    ty::lookup_struct_fields(cx, did)
-                        .iter()
-                        .any(|f| f.name.user_string(cx) == method_ustring),
-                _ => false
-            };
-
-            fcx.type_error_message(
-                span,
-                |actual| {
-                    format!("type `{}` does not implement any \
-                             method in scope named `{}`",
-                            actual,
-                            method_ustring)
-                },
-                rcvr_ty,
-                None);
-
-            // If the method has the name of a field, give a help note
-            if is_field {
-                cx.sess.span_note(span,
-                    format!("use `(s.{0})(...)` if you meant to call the \
-                            function stored in the `{0}` field", method_ustring).as_slice());
-            }
-
-            if static_sources.len() > 0 {
-                fcx.tcx().sess.fileline_note(
-                    span,
-                    "found defined static methods, maybe a `self` is missing?");
-
-                report_candidates(fcx, span, method_name, static_sources);
-            }
-        }
-
-        Ambiguity(sources) => {
-            span_err!(fcx.sess(), span, E0034,
-                      "multiple applicable methods in scope");
-
-            report_candidates(fcx, span, method_name, sources);
-        }
-    }
-
-    fn report_candidates(fcx: &FnCtxt,
-                         span: Span,
-                         method_name: ast::Name,
-                         mut sources: Vec<CandidateSource>) {
-        sources.sort();
-        sources.dedup();
-
-        for (idx, source) in sources.iter().enumerate() {
-            match *source {
-                ImplSource(impl_did) => {
-                    // Provide the best span we can. Use the method, if local to crate, else
-                    // the impl, if local to crate (method may be defaulted), else the call site.
-                    let method = impl_method(fcx.tcx(), impl_did, method_name).unwrap();
-                    let impl_span = fcx.tcx().map.def_id_span(impl_did, span);
-                    let method_span = fcx.tcx().map.def_id_span(method.def_id, impl_span);
-
-                    let impl_ty = impl_self_ty(fcx, span, impl_did).ty;
-
-                    let insertion = match impl_trait_ref(fcx.tcx(), impl_did) {
-                        None => format!(""),
-                        Some(trait_ref) => format!(" of the trait `{}`",
-                                                   ty::item_path_str(fcx.tcx(),
-                                                                     trait_ref.def_id)),
-                    };
-
-                    span_note!(fcx.sess(), method_span,
-                               "candidate #{} is defined in an impl{} for the type `{}`",
-                               idx + 1u,
-                               insertion,
-                               impl_ty.user_string(fcx.tcx()));
-                }
-                TraitSource(trait_did) => {
-                    let (_, method) = trait_method(fcx.tcx(), trait_did, method_name).unwrap();
-                    let method_span = fcx.tcx().map.def_id_span(method.def_id, span);
-                    span_note!(fcx.sess(), method_span,
-                               "candidate #{} is defined in the trait `{}`",
-                               idx + 1u,
-                               ty::item_path_str(fcx.tcx(), trait_did));
-                }
-            }
-        }
-    }
-}
-
-// Determine the index of a method in the list of all methods belonging
-// to a trait and its supertraits.
-fn get_method_index(tcx: &ty::ctxt,
-                    trait_ref: &TraitRef,
-                    subtrait: Rc<TraitRef>,
-                    n_method: uint) -> uint {
-    // We need to figure the "real index" of the method in a
-    // listing of all the methods of an object. We do this by
-    // iterating down the supertraits of the object's trait until
-    // we find the trait the method came from, counting up the
-    // methods from them.
-    let mut method_count = 0;
-    ty::each_bound_trait_and_supertraits(tcx, &[subtrait], |bound_ref| {
-        if bound_ref.def_id == trait_ref.def_id {
-            false
-        } else {
-            let trait_items = ty::trait_items(tcx, bound_ref.def_id);
-            for trait_item in trait_items.iter() {
-                match *trait_item {
-                    ty::MethodTraitItem(_) => method_count += 1,
-                    ty::TypeTraitItem(_) => {}
-                }
-            }
-            true
-        }
-    });
-    method_count + n_method
-}
-
-struct LookupContext<'a, 'tcx: 'a> {
-    fcx: &'a FnCtxt<'a, 'tcx>,
-    span: Span,
-
-    // The receiver to the method call. Only `None` in the case of
-    // an overloaded autoderef, where the receiver may be an intermediate
-    // state like "the expression `x` when it has been autoderef'd
-    // twice already".
-    self_expr: Option<&'a ast::Expr>,
-
-    m_name: ast::Name,
-    supplied_tps: &'a [ty::t],
-    impl_dups: HashSet<DefId>,
-    inherent_candidates: Vec<Candidate>,
-    extension_candidates: Vec<ExtensionCandidate>,
-    static_candidates: Vec<CandidateSource>,
-    deref_args: check::DerefArgs,
-    check_traits: CheckTraitsFlag,
-    autoderef_receiver: AutoderefReceiverFlag,
-}
-
-// A method that the user may be trying to invoke. Initially, we
-// construct candidates only for inherent methods; for extension
-// traits, we use an ExtensionCandidate.
-#[deriving(Clone)]
-struct Candidate {
-    xform_self_ty: ty::t,
-    rcvr_substs: subst::Substs,
-    method_ty: Rc<ty::Method>,
-    origin: MethodOrigin,
-}
-
-// A variation on a candidate that just stores the data needed
-// extension trait matching.  Once we pick the trait that matches,
-// we'll construct a normal candidate from that. There is no deep
-// reason for this, the code just worked out a bit cleaner.
-struct ExtensionCandidate {
-    obligation: traits::Obligation,
-    xform_self_ty: ty::t,
-    method_ty: Rc<ty::Method>,
-    method_num: uint,
-}
-
-// A pared down enum describing just the places from which a method
-// candidate can arise. Used for error reporting only.
-#[deriving(PartialOrd, Ord, PartialEq, Eq)]
-pub enum CandidateSource {
-    ImplSource(ast::DefId),
-    TraitSource(/* trait id */ ast::DefId),
-}
-
-impl<'a, 'tcx> LookupContext<'a, 'tcx> {
-    fn search(self, self_ty: ty::t) -> MethodResult {
-        let span = self.self_expr.map_or(self.span, |e| e.span);
-        let self_expr_id = self.self_expr.map(|e| e.id);
-
-        let (_, _, result) =
-            check::autoderef(
-                self.fcx, span, self_ty, self_expr_id, NoPreference,
-                |self_ty, autoderefs| self.search_step(self_ty, autoderefs));
-
-        match result {
-            Some(Some(Ok(result))) => {
-                self.fixup_derefs_on_method_receiver_if_necessary(&result);
-                Ok(result)
-            }
-            Some(Some(Err(err))) => {
-                Err(err)
-            }
-            None | Some(None) => {
-                Err(NoMatch(self.static_candidates))
-            }
-        }
-    }
-
-    fn search_step(&self,
-                   self_ty: ty::t,
-                   autoderefs: uint)
-                   -> Option<Option<MethodResult>>
-    {
-        // Oh my, what a return type!
-        //
-        // Returning:
-        // - `None` => autoderef more, keep searching
-        // - `Some(None)` => stop searching, found nothing
-        // - `Some(Some(_))` => stop searching, found either callee/error
-        //   - `Some(Some(Ok(_)))` => found a callee
-        //   - `Some(Some(Err(_)))` => found an error (ambiguity, etc)
-
-        debug!("search_step: self_ty={} autoderefs={}",
-               self.ty_to_string(self_ty), autoderefs);
-
-        match self.deref_args {
-            check::DontDerefArgs => {
-                match self.search_for_autoderefd_method(self_ty, autoderefs) {
-                    Some(result) => return Some(Some(result)),
-                    None => {}
-                }
-
-                match self.search_for_autoptrd_method(self_ty, autoderefs) {
-                    Some(result) => return Some(Some(result)),
-                    None => {}
-                }
-            }
-            check::DoDerefArgs => {
-                match self.search_for_autoptrd_method(self_ty, autoderefs) {
-                    Some(result) => return Some(Some(result)),
-                    None => {}
-                }
-
-                match self.search_for_autoderefd_method(self_ty, autoderefs) {
-                    Some(result) => return Some(Some(result)),
-                    None => {}
-                }
-            }
-        }
-
-        // If we are searching for an overloaded deref, no
-        // need to try coercing a `~[T]` to an `&[T]` and
-        // searching for an overloaded deref on *that*.
-        if !self.is_overloaded_deref() {
-            match self.search_for_autofatptrd_method(self_ty, autoderefs) {
-                Some(result) => return Some(Some(result)),
-                None => {}
-            }
-        }
-
-        // Don't autoderef if we aren't supposed to.
-        if self.autoderef_receiver == DontAutoderefReceiver {
-            Some(None)
-        } else {
-            None
-        }
-    }
-
-    fn is_overloaded_deref(&self) -> bool {
-        self.self_expr.is_none()
-    }
-
-    ///////////////////////////////////////////////////////////////////////////
-    // Candidate collection (see comment at start of file)
-
-    fn push_inherent_candidates(&mut self, self_ty: ty::t) {
-        /*!
-         * Collect all inherent candidates into
-         * `self.inherent_candidates`.  See comment at the start of
-         * the file.  To find the inherent candidates, we repeatedly
-         * deref the self-ty to find the "base-type".  So, for
-         * example, if the receiver is Box<Box<C>> where `C` is a struct type,
-         * we'll want to find the inherent impls for `C`.
-         */
-
-        let span = self.self_expr.map_or(self.span, |e| e.span);
-        check::autoderef(self.fcx, span, self_ty, None, NoPreference, |self_ty, _| {
-            match get(self_ty).sty {
-                ty_trait(box TyTrait { ref principal, bounds, .. }) => {
-                    self.push_inherent_candidates_from_object(self_ty, &*principal, bounds);
-                    self.push_inherent_impl_candidates_for_type(principal.def_id);
-                }
-                ty_enum(did, _) |
-                ty_struct(did, _) |
-                ty_unboxed_closure(did, _, _) => {
-                    if self.check_traits == CheckTraitsAndInherentMethods {
-                        self.push_inherent_impl_candidates_for_type(did);
-                    }
-                }
-                _ => { /* No inherent methods in these types */ }
-            }
-
-            // Don't autoderef if we aren't supposed to.
-            if self.autoderef_receiver == DontAutoderefReceiver {
-                Some(())
-            } else {
-                None
-            }
-        });
-    }
-
-    fn push_bound_candidates(&mut self, self_ty: ty::t, restrict_to: Option<DefId>) {
-        let span = self.self_expr.map_or(self.span, |e| e.span);
-        check::autoderef(self.fcx, span, self_ty, None, NoPreference, |self_ty, _| {
-            match get(self_ty).sty {
-                ty_param(p) => {
-                    self.push_inherent_candidates_from_param(self_ty, restrict_to, p);
-                }
-                _ => { /* No bound methods in these types */ }
-            }
-
-            // Don't autoderef if we aren't supposed to.
-            if self.autoderef_receiver == DontAutoderefReceiver {
-                Some(())
-            } else {
-                None
-            }
-        });
-    }
-
-    fn push_extension_candidates(&mut self, expr_id: ast::NodeId) {
-        debug!("push_extension_candidates(expr_id={})", expr_id);
-
-        let mut duplicates = HashSet::new();
-        let opt_applicable_traits = self.fcx.ccx.trait_map.get(&expr_id);
-        for applicable_traits in opt_applicable_traits.into_iter() {
-            for &trait_did in applicable_traits.iter() {
-                if duplicates.insert(trait_did) {
-                    self.push_extension_candidate(trait_did);
-                }
-            }
-        }
-    }
-
-    fn push_extension_candidate(&mut self, trait_def_id: DefId) {
-        debug!("push_extension_candidates: trait_def_id={}", trait_def_id);
-
-        // Check whether `trait_def_id` defines a method with suitable name:
-        let trait_items =
-            ty::trait_items(self.tcx(), trait_def_id);
-        let matching_index =
-            trait_items.iter()
-                       .position(|item| item.name() == self.m_name);
-        let matching_index = match matching_index {
-            Some(i) => i,
-            None => { return; }
-        };
-        let method = match (&*trait_items)[matching_index].as_opt_method() {
-            Some(m) => m,
-            None => { return; }
-        };
-
-        // Check whether `trait_def_id` defines a method with suitable name:
-        if !self.has_applicable_self(&*method) {
-            debug!("method has inapplicable self");
-            return self.record_static_candidate(TraitSource(trait_def_id));
-        }
-
-        // Otherwise, construct the receiver type.
-        let self_ty =
-            self.fcx.infcx().next_ty_var();
-        let trait_def =
-            ty::lookup_trait_def(self.tcx(), trait_def_id);
-        let substs =
-            self.fcx.infcx().fresh_substs_for_trait(self.span,
-                                                    &trait_def.generics,
-                                                    self_ty);
-        let xform_self_ty =
-            self.xform_self_ty(&method, &substs);
-
-        // Construct the obligation which must match.
-        let trait_ref =
-            Rc::new(ty::TraitRef::new(trait_def_id, substs));
-        let obligation =
-            traits::Obligation::misc(self.span, trait_ref);
-
-        debug!("extension-candidate(xform_self_ty={} obligation={})",
-               self.infcx().ty_to_string(xform_self_ty),
-               obligation.repr(self.tcx()));
-
-        self.extension_candidates.push(ExtensionCandidate {
-            obligation: obligation,
-            xform_self_ty: xform_self_ty,
-            method_ty: method,
-            method_num: matching_index,
-        });
-    }
-
-    fn push_inherent_candidates_from_object(&mut self,
-                                            self_ty: ty::t,
-                                            principal: &ty::TraitRef,
-                                            _bounds: ty::ExistentialBounds) {
-        debug!("push_inherent_candidates_from_object(self_ty={})",
-               self_ty.repr(self.tcx()));
-
-        let tcx = self.tcx();
-
-        // It is illegal to invoke a method on a trait instance that
-        // refers to the `Self` type. An error will be reported by
-        // `enforce_object_limitations()` if the method refers to the
-        // `Self` type anywhere other than the receiver. Here, we use
-        // a substitution that replaces `Self` with the object type
-        // itself. Hence, a `&self` method will wind up with an
-        // argument type like `&Trait`.
-        let rcvr_substs = principal.substs.with_self_ty(self_ty);
-        let trait_ref = Rc::new(TraitRef { def_id: principal.def_id,
-                                           substs: rcvr_substs.clone() });
-
-        self.push_inherent_candidates_from_bounds_inner(
-            &[trait_ref.clone()],
-            |this, new_trait_ref, m, method_num| {
-                let vtable_index =
-                    get_method_index(tcx, &*new_trait_ref,
-                                     trait_ref.clone(), method_num);
-
-                // FIXME Hacky. By-value `self` methods in objects ought to be
-                // just a special case of passing ownership of a DST value
-                // as a parameter. *But* we currently hack them in and tie them to
-                // the particulars of the `Box` type. So basically for a `fn foo(self,...)`
-                // method invoked on an object, we don't want the receiver type to be
-                // `TheTrait`, but rather `Box<TheTrait>`. Yuck.
-                let mut m = m;
-                match m.explicit_self {
-                    ByValueExplicitSelfCategory => {
-                        let mut n = (*m).clone();
-                        let self_ty = n.fty.sig.inputs[0];
-                        n.fty.sig.inputs[0] = ty::mk_uniq(tcx, self_ty);
-                        m = Rc::new(n);
-                    }
-                    _ => { }
-                }
-
-                let xform_self_ty =
-                    this.xform_self_ty(&m, &new_trait_ref.substs);
-
-                Some(Candidate {
-                    xform_self_ty: xform_self_ty,
-                    rcvr_substs: new_trait_ref.substs.clone(),
-                    method_ty: m,
-                    origin: MethodTraitObject(MethodObject {
-                        trait_ref: new_trait_ref,
-                        object_trait_id: principal.def_id,
-                        method_num: method_num,
-                        real_index: vtable_index
-                    })
-                })
-            });
-    }
-
-    fn push_inherent_candidates_from_param(&mut self,
-                                           rcvr_ty: ty::t,
-                                           restrict_to: Option<DefId>,
-                                           param_ty: ParamTy) {
-        debug!("push_inherent_candidates_from_param(param_ty={})",
-               param_ty);
-        self.push_inherent_candidates_from_bounds(
-            rcvr_ty,
-            param_ty.space,
-            param_ty.idx,
-            restrict_to);
-    }
-
-    fn push_inherent_candidates_from_bounds(&mut self,
-                                            _self_ty: ty::t,
-                                            space: subst::ParamSpace,
-                                            index: uint,
-                                            restrict_to: Option<DefId>) {
-        let bounds =
-            self.fcx.inh.param_env.bounds.get(space, index).trait_bounds
-            .as_slice();
-        self.push_inherent_candidates_from_bounds_inner(bounds,
-            |this, trait_ref, m, method_num| {
-                match restrict_to {
-                    Some(trait_did) => {
-                        if trait_did != trait_ref.def_id {
-                            return None;
-                        }
-                    }
-                    _ => {}
-                }
-
-                let xform_self_ty =
-                    this.xform_self_ty(&m, &trait_ref.substs);
-
-                debug!("found match: trait_ref={} substs={} m={}",
-                       trait_ref.repr(this.tcx()),
-                       trait_ref.substs.repr(this.tcx()),
-                       m.repr(this.tcx()));
-                assert_eq!(m.generics.types.get_slice(subst::TypeSpace).len(),
-                           trait_ref.substs.types.get_slice(subst::TypeSpace).len());
-                assert_eq!(m.generics.regions.get_slice(subst::TypeSpace).len(),
-                           trait_ref.substs.regions().get_slice(subst::TypeSpace).len());
-                assert_eq!(m.generics.types.get_slice(subst::SelfSpace).len(),
-                           trait_ref.substs.types.get_slice(subst::SelfSpace).len());
-                assert_eq!(m.generics.regions.get_slice(subst::SelfSpace).len(),
-                           trait_ref.substs.regions().get_slice(subst::SelfSpace).len());
-
-                Some(Candidate {
-                    xform_self_ty: xform_self_ty,
-                    rcvr_substs: trait_ref.substs.clone(),
-                    method_ty: m,
-                    origin: MethodTypeParam(MethodParam {
-                        trait_ref: trait_ref,
-                        method_num: method_num,
-                    })
-                })
-            })
-    }
-
-    // Do a search through a list of bounds, using a callback to actually
-    // create the candidates.
-    fn push_inherent_candidates_from_bounds_inner(
-        &mut self,
-        bounds: &[Rc<TraitRef>],
-        mk_cand: |this: &mut LookupContext,
-                  tr: Rc<TraitRef>,
-                  m: Rc<ty::Method>,
-                  method_num: uint|
-                  -> Option<Candidate>)
-    {
-        let tcx = self.tcx();
-        let mut cache = HashSet::new();
-        for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
-            // Already visited this trait, skip it.
-            if !cache.insert(bound_trait_ref.def_id) {
-                continue;
-            }
-
-            let (pos, method) = match trait_method(tcx, bound_trait_ref.def_id, self.m_name) {
-                Some(v) => v,
-                None => { continue; }
-            };
-
-            if !self.has_applicable_self(&*method) {
-                self.record_static_candidate(TraitSource(bound_trait_ref.def_id));
-            } else {
-                match mk_cand(self,
-                              bound_trait_ref,
-                              method,
-                              pos) {
-                    Some(cand) => {
-                        debug!("pushing inherent candidate for param: {}",
-                               cand.repr(self.tcx()));
-                        self.inherent_candidates.push(cand);
-                    }
-                    None => {}
-                }
-            }
-        }
-    }
-
-
-    fn push_inherent_impl_candidates_for_type(&mut self, did: DefId) {
-        // Read the inherent implementation candidates for this type from the
-        // metadata if necessary.
-        ty::populate_implementations_for_type_if_necessary(self.tcx(), did);
-
-        for impl_infos in self.tcx().inherent_impls.borrow().get(&did).iter() {
-            for impl_did in impl_infos.iter() {
-                self.push_candidates_from_inherent_impl(*impl_did);
-            }
-        }
-    }
-
-    fn push_candidates_from_inherent_impl(&mut self,
-                                          impl_did: DefId) {
-        if !self.impl_dups.insert(impl_did) {
-            return; // already visited
-        }
-
-        let method = match impl_method(self.tcx(), impl_did, self.m_name) {
-            Some(m) => m,
-            None => { return; } // No method with correct name on this impl
-        };
-
-        debug!("push_candidates_from_inherent_impl: impl_did={} method={}",
-               impl_did.repr(self.tcx()),
-               method.repr(self.tcx()));
-
-        if !self.has_applicable_self(&*method) {
-            // No receiver declared. Not a candidate.
-            return self.record_static_candidate(ImplSource(impl_did));
-        }
-
-        // Determine the `self` of the impl with fresh
-        // variables for each parameter.
-        let span = self.self_expr.map_or(self.span, |e| e.span);
-        let TypeAndSubsts {
-            substs: impl_substs,
-            ty: _impl_ty
-        } = impl_self_ty(self.fcx, span, impl_did);
-
-        // Determine the receiver type that the method itself expects.
-        let xform_self_ty =
-            self.xform_self_ty(&method, &impl_substs);
-
-        self.inherent_candidates.push(Candidate {
-            xform_self_ty: xform_self_ty,
-            rcvr_substs: impl_substs,
-            origin: MethodStatic(method.def_id),
-            method_ty: method,
-        });
-    }
-
-    // ______________________________________________________________________
-    // Candidate selection (see comment at start of file)
-
-    fn search_for_autoderefd_method(&self,
-                                    self_ty: ty::t,
-                                    autoderefs: uint)
-                                    -> Option<MethodResult> {
-        // Hacky. For overloaded derefs, there may be an adjustment
-        // added to the expression from the outside context, so we do not store
-        // an explicit adjustment, but rather we hardwire the single deref
-        // that occurs in trans and mem_categorization.
-        if self.self_expr.is_none() {
-            return None;
-        }
-
-        let (self_ty, auto_deref_ref) = self.consider_reborrow(self_ty, autoderefs);
-        let adjustment = Some((self.self_expr.unwrap().id, ty::AdjustDerefRef(auto_deref_ref)));
-
-        match self.search_for_method(self_ty) {
-            None => {
-                None
-            }
-            Some(Ok(method)) => {
-                debug!("(searching for autoderef'd method) writing \
-                       adjustment {} for {}", adjustment, self.ty_to_string(self_ty));
-                match adjustment {
-                    Some((self_expr_id, adj)) => {
-                        self.fcx.write_adjustment(self_expr_id, self.span, adj);
-                    }
-                    None => {}
-                }
-                Some(Ok(method))
-            }
-            Some(Err(error)) => {
-                Some(Err(error))
-            }
-        }
-    }
-
-    fn consider_reborrow(&self,
-                         self_ty: ty::t,
-                         autoderefs: uint)
-                         -> (ty::t, ty::AutoDerefRef) {
-        /*!
-         * In the event that we are invoking a method with a receiver
-         * of a borrowed type like `&T`, `&mut T`, or `&mut [T]`,
-         * we will "reborrow" the receiver implicitly.  For example, if
-         * you have a call `r.inc()` and where `r` has type `&mut T`,
-         * then we treat that like `(&mut *r).inc()`.  This avoids
-         * consuming the original pointer.
-         *
-         * You might think that this would be a natural byproduct of
-         * the auto-deref/auto-ref process.  This is true for `Box<T>`
-         * but not for an `&mut T` receiver.  With `Box<T>`, we would
-         * begin by testing for methods with a self type `Box<T>`,
-         * then autoderef to `T`, then autoref to `&mut T`.  But with
-         * an `&mut T` receiver the process begins with `&mut T`, only
-         * without any autoadjustments.
-         */
-
-        let tcx = self.tcx();
-        return match ty::get(self_ty).sty {
-            ty::ty_rptr(_, self_mt) if default_method_hack(self_mt) => {
-                (self_ty,
-                 ty::AutoDerefRef {
-                     autoderefs: autoderefs,
-                     autoref: None})
-            }
-            ty::ty_rptr(_, self_mt) => {
-                let region =
-                    self.infcx().next_region_var(infer::Autoref(self.span));
-                (ty::mk_rptr(tcx, region, self_mt),
-                 ty::AutoDerefRef {
-                     autoderefs: autoderefs + 1,
-                     autoref: Some(ty::AutoPtr(region, self_mt.mutbl, None))})
-            }
-            _ => {
-                (self_ty,
-                 ty::AutoDerefRef {
-                     autoderefs: autoderefs,
-                     autoref: None})
-            }
-        };
-
-        fn default_method_hack(self_mt: ty::mt) -> bool {
-            // FIXME(#6129). Default methods can't deal with autoref.
-            //
-            // I am a horrible monster and I pray for death. Currently
-            // the default method code panics when you try to reborrow
-            // because it is not handling types correctly. In lieu of
-            // fixing that, I am introducing this horrible hack. - ndm
-            self_mt.mutbl == MutImmutable && ty::type_is_self(self_mt.ty)
-        }
-    }
-
-    // Takes an [T] - an unwrapped DST pointer (either ~ or &)
-    // [T] to &[T] or &&[T] (note that we started with a &[T] or ~[T] which has
-    // been implicitly derefed).
-    fn auto_slice_vec(&self, ty: ty::t, autoderefs: uint)
-                      -> Option<MethodResult>
-    {
-        let tcx = self.tcx();
-        debug!("auto_slice_vec {}", ppaux::ty_to_string(tcx, ty));
-
-        // First try to borrow to a slice
-        let entry = self.search_for_some_kind_of_autorefd_method(
-            |r, m| AutoPtr(r, m, None), autoderefs, &[MutImmutable, MutMutable],
-            |m,r| ty::mk_slice(tcx, r,
-                               ty::mt {ty:ty, mutbl:m}));
-
-        if entry.is_some() {
-            return entry;
-        }
-
-        // Then try to borrow to a slice *and* borrow a pointer.
-        self.search_for_some_kind_of_autorefd_method(
-            |r, m| AutoPtr(r, ast::MutImmutable, Some( box AutoPtr(r, m, None))),
-            autoderefs, &[MutImmutable, MutMutable],
-            |m, r| {
-                let slice_ty = ty::mk_slice(tcx, r,
-                                            ty::mt {ty:ty, mutbl:m});
-                // NB: we do not try to autoref to a mutable
-                // pointer. That would be creating a pointer
-                // to a temporary pointer (the borrowed
-                // slice), so any update the callee makes to
-                // it can't be observed.
-                ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:MutImmutable})
-            })
-    }
-
-    // [T, ..len] -> [T] or &[T] or &&[T]
-    fn auto_unsize_vec(&self, ty: ty::t, autoderefs: uint, len: uint) -> Option<MethodResult> {
-        let tcx = self.tcx();
-        debug!("auto_unsize_vec {}", ppaux::ty_to_string(tcx, ty));
-
-        // First try to borrow to an unsized vec.
-        let entry = self.search_for_some_kind_of_autorefd_method(
-            |_r, _m| AutoUnsize(ty::UnsizeLength(len)),
-            autoderefs, &[MutImmutable, MutMutable],
-            |_m, _r| ty::mk_vec(tcx, ty, None));
-
-        if entry.is_some() {
-            return entry;
-        }
-
-        // Then try to borrow to a slice.
-        let entry = self.search_for_some_kind_of_autorefd_method(
-            |r, m| AutoPtr(r, m, Some(box AutoUnsize(ty::UnsizeLength(len)))),
-            autoderefs, &[MutImmutable, MutMutable],
-            |m, r|  ty::mk_slice(tcx, r, ty::mt {ty:ty, mutbl:m}));
-
-        if entry.is_some() {
-            return entry;
-        }
-
-        // Then try to borrow to a slice *and* borrow a pointer.
-        self.search_for_some_kind_of_autorefd_method(
-            |r, m| AutoPtr(r, m,
-                           Some(box AutoPtr(r, m,
-                                            Some(box AutoUnsize(ty::UnsizeLength(len)))))),
-            autoderefs, &[MutImmutable, MutMutable],
-            |m, r| {
-                let slice_ty = ty::mk_slice(tcx, r, ty::mt {ty:ty, mutbl:m});
-                ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:MutImmutable})
-            })
-    }
-
-    fn auto_slice_str(&self, autoderefs: uint) -> Option<MethodResult> {
-        let tcx = self.tcx();
-        debug!("auto_slice_str");
-
-        let entry = self.search_for_some_kind_of_autorefd_method(
-            |r, m| AutoPtr(r, m, None), autoderefs, &[MutImmutable],
-            |_m, r| ty::mk_str_slice(tcx, r, MutImmutable));
-
-        if entry.is_some() {
-            return entry;
-        }
-
-        self.search_for_some_kind_of_autorefd_method(
-            |r, m| AutoPtr(r, ast::MutImmutable, Some( box AutoPtr(r, m, None))),
-            autoderefs, &[MutImmutable],
-            |m, r| {
-                let slice_ty = ty::mk_str_slice(tcx, r, m);
-                ty::mk_rptr(tcx, r, ty::mt {ty:slice_ty, mutbl:m})
-            })
-    }
-
-    // Coerce Box/&Trait instances to &Trait.
-    fn auto_slice_trait(&self, ty: ty::t, autoderefs: uint) -> Option<MethodResult> {
-        debug!("auto_slice_trait");
-        match ty::get(ty).sty {
-            ty_trait(box ty::TyTrait { ref principal,
-                                       bounds: b,
-                                       .. }) => {
-                let trt_did = principal.def_id;
-                let trt_substs = &principal.substs;
-                let tcx = self.tcx();
-                self.search_for_some_kind_of_autorefd_method(
-                    |r, m| AutoPtr(r, m, None),
-                    autoderefs, &[MutImmutable, MutMutable],
-                    |m, r| {
-                        let principal = ty::TraitRef::new(trt_did,
-                                                          trt_substs.clone());
-                        let tr = ty::mk_trait(tcx, principal, b);
-                        ty::mk_rptr(tcx, r, ty::mt{ ty: tr, mutbl: m })
-                    })
-            }
-            _ => panic!("Expected ty_trait in auto_slice_trait")
-        }
-    }
-
-    fn search_for_autofatptrd_method(&self,
-                                     self_ty: ty::t,
-                                     autoderefs: uint)
-                                     -> Option<MethodResult>
-    {
-        /*!
-         * Searches for a candidate by converting things like
-         * `~[]` to `&[]`.
-         */
-
-        let tcx = self.tcx();
-        debug!("search_for_autofatptrd_method {}", ppaux::ty_to_string(tcx, self_ty));
-
-        let sty = ty::get(self_ty).sty.clone();
-        match sty {
-            ty_vec(ty, Some(len)) => self.auto_unsize_vec(ty, autoderefs, len),
-            ty_vec(ty, None) => self.auto_slice_vec(ty, autoderefs),
-            ty_str => self.auto_slice_str(autoderefs),
-            ty_trait(..) => self.auto_slice_trait(self_ty, autoderefs),
-
-            ty_closure(..) => {
-                // This case should probably be handled similarly to
-                // Trait instances.
-                None
-            }
-
-            _ => None
-        }
-    }
-
-    fn search_for_autoptrd_method(&self, self_ty: ty::t, autoderefs: uint)
-                                  -> Option<MethodResult>
-    {
-        /*!
-         *
-         * Converts any type `T` to `&M T` where `M` is an
-         * appropriate mutability.
-         */
-
-        let tcx = self.tcx();
-        match ty::get(self_ty).sty {
-            ty_bare_fn(..) | ty_uniq(..) | ty_rptr(..) |
-            ty_infer(IntVar(_)) |
-            ty_infer(FloatVar(_)) |
-            ty_param(..) | ty_bool |
-            ty_char | ty_int(..) | ty_uint(..) |
-            ty_float(..) | ty_enum(..) | ty_ptr(..) | ty_struct(..) |
-            ty_unboxed_closure(..) | ty_tup(..) | ty_open(..) |
-            ty_str | ty_vec(..) | ty_trait(..) | ty_closure(..) => {
-                self.search_for_some_kind_of_autorefd_method(
-                    |r, m| AutoPtr(r, m, None), autoderefs, &[MutImmutable, MutMutable],
-                    |m,r| ty::mk_rptr(tcx, r, ty::mt {ty:self_ty, mutbl:m}))
-            }
-
-            ty_err => None,
-
-            ty_infer(TyVar(_)) |
-            ty_infer(SkolemizedTy(_)) |
-            ty_infer(SkolemizedIntTy(_)) => {
-                self.bug(format!("unexpected type: {}",
-                                 self.ty_to_string(self_ty)).as_slice());
-            }
-        }
-    }
-
-    fn search_for_some_kind_of_autorefd_method(
-        &self,
-        kind: |Region, ast::Mutability| -> ty::AutoRef,
-        autoderefs: uint,
-        mutbls: &[ast::Mutability],
-        mk_autoref_ty: |ast::Mutability, ty::Region| -> ty::t)
-        -> Option<MethodResult>
-    {
-        // Hacky. For overloaded derefs, there may be an adjustment
-        // added to the expression from the outside context, so we do not store
-        // an explicit adjustment, but rather we hardwire the single deref
-        // that occurs in trans and mem_categorization.
-        let self_expr_id = match self.self_expr {
-            Some(expr) => Some(expr.id),
-            None => {
-                assert_eq!(autoderefs, 0);
-                assert!(kind(ty::ReEmpty, ast::MutImmutable) ==
-                        ty::AutoPtr(ty::ReEmpty, ast::MutImmutable, None));
-                None
-            }
-        };
-
-        // This is hokey. We should have mutability inference as a
-        // variable.  But for now, try &, then &mut:
-        let region =
-            self.infcx().next_region_var(infer::Autoref(self.span));
-        for mutbl in mutbls.iter() {
-            let autoref_ty = mk_autoref_ty(*mutbl, region);
-            match self.search_for_method(autoref_ty) {
-                None => {}
-                Some(method) => {
-                    match self_expr_id {
-                        Some(self_expr_id) => {
-                            self.fcx.write_adjustment(
-                                self_expr_id,
-                                self.span,
-                                ty::AdjustDerefRef(ty::AutoDerefRef {
-                                    autoderefs: autoderefs,
-                                    autoref: Some(kind(region, *mutbl))
-                                }));
-                        }
-                        None => {}
-                    }
-                    return Some(method);
-                }
-            }
-        }
-        None
-    }
-
-    fn search_for_method(&self, rcvr_ty: ty::t) -> Option<MethodResult> {
-        debug!("search_for_method(rcvr_ty={})", self.ty_to_string(rcvr_ty));
-        let _indenter = indenter();
-
-        // I am not sure that inherent methods should have higher
-        // priority, but it is necessary ATM to handle some of the
-        // existing code.
-
-        debug!("searching inherent candidates");
-        match self.consider_candidates(rcvr_ty, self.inherent_candidates.as_slice()) {
-            None => {}
-            Some(mme) => {
-                return Some(mme);
-            }
-        }
-
-        debug!("searching extension candidates");
-        self.consider_extension_candidates(rcvr_ty)
-    }
-
-    fn consider_candidates(&self, rcvr_ty: ty::t,
-                           candidates: &[Candidate])
-                           -> Option<MethodResult> {
-        let relevant_candidates = self.filter_candidates(rcvr_ty, candidates);
-
-        if relevant_candidates.len() == 0 {
-            return None;
-        }
-
-        if relevant_candidates.len() > 1 {
-            let sources = relevant_candidates.iter()
-                                             .map(|candidate| candidate.to_source())
-                                             .collect();
-            return Some(Err(Ambiguity(sources)));
-        }
-
-        Some(Ok(self.confirm_candidate(rcvr_ty, &relevant_candidates[0])))
-    }
-
-    fn filter_candidates(&self, rcvr_ty: ty::t, candidates: &[Candidate]) -> Vec<Candidate> {
-        let mut relevant_candidates: Vec<Candidate> = Vec::new();
-
-        for candidate_a in candidates.iter().filter(|&c| self.is_relevant(rcvr_ty, c)) {
-            // Skip this one if we already have one like it
-            if !relevant_candidates.iter().any(|candidate_b| {
-                debug!("attempting to merge {} and {}",
-                       candidate_a.repr(self.tcx()),
-                       candidate_b.repr(self.tcx()));
-                match (&candidate_a.origin, &candidate_b.origin) {
-                    (&MethodTypeParam(ref p1), &MethodTypeParam(ref p2)) => {
-                        let same_trait =
-                            p1.trait_ref.def_id == p2.trait_ref.def_id;
-                        let same_method =
-                            p1.method_num == p2.method_num;
-                        // it's ok to compare self-ty with `==` here because
-                        // they are always a TyParam
-                        let same_param =
-                            p1.trait_ref.self_ty() == p2.trait_ref.self_ty();
-                        same_trait && same_method && same_param
-                    }
-                    _ => false
-                }
-            }) {
-                relevant_candidates.push((*candidate_a).clone());
-            }
-        }
-
-        relevant_candidates
-    }
-
-    fn consider_extension_candidates(&self, rcvr_ty: ty::t)
-                                     -> Option<MethodResult>
-    {
-        let mut selcx = traits::SelectionContext::new(self.infcx(),
-                                                      &self.fcx.inh.param_env,
-                                                      self.fcx);
-
-        let extension_evaluations: Vec<_> =
-            self.extension_candidates.iter()
-            .map(|ext| self.probe_extension_candidate(&mut selcx, rcvr_ty, ext))
-            .collect();
-
-        // How many traits can apply?
-        let applicable_evaluations_count =
-            extension_evaluations.iter()
-                                 .filter(|eval| eval.may_apply())
-                                 .count();
-
-        // Determine whether there are multiple traits that could apply.
-        if applicable_evaluations_count > 1 {
-            let sources =
-                self.extension_candidates.iter()
-                    .zip(extension_evaluations.iter())
-                    .filter(|&(_, eval)| eval.may_apply())
-                    .map(|(ext, _)| ext.to_source())
-                    .collect();
-            return Some(Err(Ambiguity(sources)));
-        }
-
-        // Determine whether there are no traits that could apply.
-        if applicable_evaluations_count == 0 {
-            return None;
-        }
-
-        // Exactly one trait applies. It itself could *still* be ambiguous thanks
-        // to coercions.
-        let applicable_evaluation = extension_evaluations.iter()
-                                                         .position(|eval| eval.may_apply())
-                                                         .unwrap();
-        let match_data = match extension_evaluations[applicable_evaluation] {
-            traits::MethodMatched(data) => data,
-            traits::MethodAmbiguous(ref impl_def_ids) => {
-                let sources = impl_def_ids.iter().map(|&d| ImplSource(d)).collect();
-                return Some(Err(Ambiguity(sources)));
-            }
-            traits::MethodDidNotMatch => {
-                self.bug("Method did not match and yet may_apply() is true")
-            }
-        };
-
-        let extension = &self.extension_candidates[applicable_evaluation];
-
-        debug!("picked extension={}", extension.repr(self.tcx()));
-
-        // We have to confirm the method match. This will cause the type variables
-        // in the obligation to be appropriately unified based on the subtyping/coercion
-        // between `rcvr_ty` and `extension.xform_self_ty`.
-        selcx.confirm_method_match(rcvr_ty, extension.xform_self_ty,
-                                   &extension.obligation, match_data);
-
-        // Finally, construct the candidate, now that everything is
-        // known, and confirm *that*. Note that whatever we pick
-        // (impl, whatever) we can always use the same kind of origin
-        // (trait-based method dispatch).
-        let candidate = Candidate {
-            xform_self_ty: extension.xform_self_ty,
-            rcvr_substs: extension.obligation.trait_ref.substs.clone(),
-            method_ty: extension.method_ty.clone(),
-            origin: MethodTypeParam(MethodParam{trait_ref: extension.obligation.trait_ref.clone(),
-                                                method_num: extension.method_num})
-        };
-
-        // Confirming the candidate will do the final work of
-        // instantiating late-bound variables, unifying things, and
-        // registering trait obligations (including
-        // `extension.obligation`, which should be a requirement of
-        // the `Self` trait).
-        let callee = self.confirm_candidate(rcvr_ty, &candidate);
-
-        select_new_fcx_obligations(self.fcx);
-
-        Some(Ok(callee))
-    }
-
-    fn probe_extension_candidate(&self,
-                                 selcx: &mut traits::SelectionContext,
-                                 rcvr_ty: ty::t,
-                                 candidate: &ExtensionCandidate)
-                                 -> traits::MethodMatchResult
-    {
-        debug!("probe_extension_candidate(rcvr_ty={}, candidate.obligation={})",
-               rcvr_ty.repr(self.tcx()),
-               candidate.obligation.repr(self.tcx()));
-
-        selcx.evaluate_method_obligation(rcvr_ty, candidate.xform_self_ty, &candidate.obligation)
-    }
-
-    fn confirm_candidate(&self, rcvr_ty: ty::t, candidate: &Candidate)
-                         -> MethodCallee
-    {
-        // This method performs two sets of substitutions, one after the other:
-        // 1. Substitute values for any type/lifetime parameters from the impl and
-        //    method declaration into the method type. This is the function type
-        //    before it is called; it may still include late bound region variables.
-        // 2. Instantiate any late bound lifetime parameters in the method itself
-        //    with fresh region variables.
-
-        let tcx = self.tcx();
-
-        debug!("confirm_candidate(rcvr_ty={}, candidate={})",
-               self.ty_to_string(rcvr_ty),
-               candidate.repr(self.tcx()));
-
-        let rcvr_substs = candidate.rcvr_substs.clone();
-        self.enforce_drop_trait_limitations(candidate);
-
-        // Determine the values for the generic parameters of the method.
-        // If they were not explicitly supplied, just construct fresh
-        // variables.
-        let num_supplied_tps = self.supplied_tps.len();
-        let num_method_tps = candidate.method_ty.generics.types.len(subst::FnSpace);
-        let m_types = {
-            if num_supplied_tps == 0u {
-                self.fcx.infcx().next_ty_vars(num_method_tps)
-            } else if num_method_tps == 0u {
-                span_err!(tcx.sess, self.span, E0035,
-                    "does not take type parameters");
-                self.fcx.infcx().next_ty_vars(num_method_tps)
-            } else if num_supplied_tps != num_method_tps {
-                span_err!(tcx.sess, self.span, E0036,
-                    "incorrect number of type parameters given for this method");
-                self.fcx.infcx().next_ty_vars(num_method_tps)
-            } else {
-                self.supplied_tps.to_vec()
-            }
-        };
-
-        // Create subst for early-bound lifetime parameters, combining
-        // parameters from the type and those from the method.
-        //
-        // FIXME -- permit users to manually specify lifetimes
-        let m_regions =
-            self.fcx.infcx().region_vars_for_defs(
-                self.span,
-                candidate.method_ty.generics.regions.get_slice(subst::FnSpace));
-
-        let all_substs = rcvr_substs.with_method(m_types, m_regions);
-
-        let ref bare_fn_ty = candidate.method_ty.fty;
-
-        // Compute the method type with type parameters substituted
-        debug!("fty={} all_substs={}",
-               bare_fn_ty.repr(tcx),
-               all_substs.repr(tcx));
-
-        let fn_sig = bare_fn_ty.sig.subst(tcx, &all_substs);
-
-        debug!("after subst, fty={}", fn_sig.repr(tcx));
-
-        // Replace any bound regions that appear in the function
-        // signature with region variables
-        let fn_sig =
-            self.replace_late_bound_regions_with_fresh_var(fn_sig.binder_id, &fn_sig);
-        let transformed_self_ty = fn_sig.inputs[0];
-        let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
-            sig: fn_sig,
-            fn_style: bare_fn_ty.fn_style,
-            abi: bare_fn_ty.abi.clone(),
-        });
-        debug!("after replacing bound regions, fty={}", self.ty_to_string(fty));
-
-        // Before, we only checked whether self_ty could be a subtype
-        // of rcvr_ty; now we actually make it so (this may cause
-        // variables to unify etc).  Since we checked beforehand, and
-        // nothing has changed in the meantime, this unification
-        // should never fail.
-        let span = self.self_expr.map_or(self.span, |e| e.span);
-        match self.fcx.mk_subty(false, infer::Misc(span),
-                                rcvr_ty, transformed_self_ty) {
-            Ok(_) => {}
-            Err(_) => {
-                self.bug(format!(
-                        "{} was a subtype of {} but now is not?",
-                        self.ty_to_string(rcvr_ty),
-                        self.ty_to_string(transformed_self_ty)).as_slice());
-            }
-        }
-
-        // FIXME(DST). Super hack. For a method on a trait object
-        // `Trait`, the generic signature requires that
-        // `Self:Trait`. Since, for an object, we bind `Self` to the
-        // type `Trait`, this leads to an obligation
-        // `Trait:Trait`. Until such time we DST is fully implemented,
-        // that obligation is not necessarily satisfied. (In the
-        // future, it would be.)
-        //
-        // To sidestep this, we overwrite the binding for `Self` with
-        // `err` (just for trait objects) when we generate the
-        // obligations.  This causes us to generate the obligation
-        // `err:Trait`, and the error type is considered to implement
-        // all traits, so we're all good. Hack hack hack.
-        match candidate.origin {
-            MethodTraitObject(..) => {
-                let mut temp_substs = all_substs.clone();
-                temp_substs.types.get_mut_slice(SelfSpace)[0] = ty::mk_err();
-                self.fcx.add_obligations_for_parameters(
-                    traits::ObligationCause::misc(self.span),
-                    &temp_substs,
-                    &candidate.method_ty.generics);
-            }
-            _ => {
-                self.fcx.add_obligations_for_parameters(
-                    traits::ObligationCause::misc(self.span),
-                    &all_substs,
-                    &candidate.method_ty.generics);
-            }
-        }
-
-        MethodCallee {
-            origin: candidate.origin.clone(),
-            ty: fty,
-            substs: all_substs
-        }
-    }
-
-    fn fixup_derefs_on_method_receiver_if_necessary(&self,
-                                                    method_callee: &MethodCallee) {
-        let sig = match ty::get(method_callee.ty).sty {
-            ty::ty_bare_fn(ref f) => f.sig.clone(),
-            ty::ty_closure(ref f) => f.sig.clone(),
-            _ => return,
-        };
-
-        match ty::get(sig.inputs[0]).sty {
-            ty::ty_rptr(_, ty::mt {
-                ty: _,
-                mutbl: ast::MutMutable,
-            }) => {}
-            _ => return,
-        }
-
-        // Gather up expressions we want to munge.
-        let mut exprs = Vec::new();
-        match self.self_expr {
-            Some(expr) => exprs.push(expr),
-            None => {}
-        }
-        loop {
-            if exprs.len() == 0 {
-                break
-            }
-            let last = exprs[exprs.len() - 1];
-            match last.node {
-                ast::ExprParen(ref expr) |
-                ast::ExprField(ref expr, _, _) |
-                ast::ExprTupField(ref expr, _, _) |
-                ast::ExprSlice(ref expr, _, _, _) |
-                ast::ExprIndex(ref expr, _) |
-                ast::ExprUnary(ast::UnDeref, ref expr) => exprs.push(&**expr),
-                _ => break,
-            }
-        }
-
-        debug!("fixup_derefs_on_method_receiver_if_necessary: exprs={}",
-               exprs.repr(self.tcx()));
-
-        // Fix up autoderefs and derefs.
-        for (i, expr) in exprs.iter().rev().enumerate() {
-            // Count autoderefs.
-            let autoderef_count = match self.fcx
-                                            .inh
-                                            .adjustments
-                                            .borrow()
-                                            .get(&expr.id) {
-                Some(&ty::AdjustDerefRef(ty::AutoDerefRef {
-                    autoderefs: autoderef_count,
-                    autoref: _
-                })) => autoderef_count,
-                Some(_) | None => 0,
-            };
-
-            debug!("fixup_derefs_on_method_receiver_if_necessary: i={} expr={} autoderef_count={}",
-                   i, expr.repr(self.tcx()), autoderef_count);
-
-            if autoderef_count > 0 {
-                check::autoderef(self.fcx,
-                                 expr.span,
-                                 self.fcx.expr_ty(*expr),
-                                 Some(expr.id),
-                                 PreferMutLvalue,
-                                 |_, autoderefs| {
-                                     if autoderefs == autoderef_count + 1 {
-                                         Some(())
-                                     } else {
-                                         None
-                                     }
-                                 });
-            }
-
-            // Don't retry the first one or we might infinite loop!
-            if i != 0 {
-                match expr.node {
-                    ast::ExprIndex(ref base_expr, _) => {
-                        let mut base_adjustment =
-                            match self.fcx.inh.adjustments.borrow().get(&base_expr.id) {
-                                Some(&ty::AdjustDerefRef(ref adr)) => (*adr).clone(),
-                                None => ty::AutoDerefRef { autoderefs: 0, autoref: None },
-                                Some(_) => {
-                                    self.tcx().sess.span_bug(
-                                        base_expr.span,
-                                        "unexpected adjustment type");
-                                }
-                            };
-
-                        // If this is an overloaded index, the
-                        // adjustment will include an extra layer of
-                        // autoref because the method is an &self/&mut
-                        // self method. We have to peel it off to get
-                        // the raw adjustment that `try_index_step`
-                        // expects. This is annoying and horrible. We
-                        // ought to recode this routine so it doesn't
-                        // (ab)use the normal type checking paths.
-                        base_adjustment.autoref = match base_adjustment.autoref {
-                            None => { None }
-                            Some(AutoPtr(_, _, None)) => { None }
-                            Some(AutoPtr(_, _, Some(box r))) => { Some(r) }
-                            Some(_) => {
-                                self.tcx().sess.span_bug(
-                                    base_expr.span,
-                                    "unexpected adjustment autoref");
-                            }
-                        };
-
-                        let adjusted_base_ty =
-                            self.fcx.adjust_expr_ty(
-                                &**base_expr,
-                                Some(&ty::AdjustDerefRef(base_adjustment.clone())));
-
-                        check::try_index_step(
-                            self.fcx,
-                            MethodCall::expr(expr.id),
-                            *expr,
-                            &**base_expr,
-                            adjusted_base_ty,
-                            base_adjustment,
-                            PreferMutLvalue);
-                    }
-                    ast::ExprUnary(ast::UnDeref, ref base_expr) => {
-                        // if this is an overloaded deref, then re-evaluate with
-                        // a preference for mut
-                        let method_call = MethodCall::expr(expr.id);
-                        if self.fcx.inh.method_map.borrow().contains_key(&method_call) {
-                            check::try_overloaded_deref(
-                                self.fcx,
-                                expr.span,
-                                Some(method_call),
-                                Some(&**base_expr),
-                                self.fcx.expr_ty(&**base_expr),
-                                PreferMutLvalue);
-                        }
-                    }
-                    _ => {}
-                }
-            }
-        }
-    }
-
-    fn enforce_drop_trait_limitations(&self, candidate: &Candidate) {
-        // No code can call the finalize method explicitly.
-        let bad = match candidate.origin {
-            MethodStatic(method_id) => {
-                self.tcx().destructors.borrow().contains(&method_id)
-            }
-            MethodStaticUnboxedClosure(_) => {
-                false
-            }
-            MethodTypeParam(MethodParam { ref trait_ref, .. }) |
-            MethodTraitObject(MethodObject { ref trait_ref, .. }) => {
-                Some(trait_ref.def_id) == self.tcx().lang_items.drop_trait()
-            }
-        };
-
-        if bad {
-            span_err!(self.tcx().sess, self.span, E0040,
-                "explicit call to destructor");
-        }
-    }
-
-    // `rcvr_ty` is the type of the expression. It may be a subtype of a
-    // candidate method's `self_ty`.
-    fn is_relevant(&self, rcvr_ty: ty::t, candidate: &Candidate) -> bool {
-        debug!("is_relevant(rcvr_ty={}, candidate={})",
-               self.ty_to_string(rcvr_ty), candidate.repr(self.tcx()));
-
-        infer::can_mk_subty(self.infcx(), rcvr_ty, candidate.xform_self_ty).is_ok()
-    }
-
-    fn infcx(&'a self) -> &'a infer::InferCtxt<'a, 'tcx> {
-        &self.fcx.inh.infcx
-    }
-
-    fn tcx(&self) -> &'a ty::ctxt<'tcx> {
-        self.fcx.tcx()
-    }
-
-    fn ty_to_string(&self, t: ty::t) -> String {
-        self.fcx.infcx().ty_to_string(t)
-    }
-
-    fn bug(&self, s: &str) -> ! {
-        self.tcx().sess.span_bug(self.span, s)
-    }
-
-    fn has_applicable_self(&self, method: &ty::Method) -> bool {
-        // "fast track" -- check for usage of sugar
-        match method.explicit_self {
-            StaticExplicitSelfCategory => {
-                // fallthrough
-            }
-            ByValueExplicitSelfCategory |
-            ByReferenceExplicitSelfCategory(..) |
-            ByBoxExplicitSelfCategory => {
-                return true;
-            }
-        }
-
-        // FIXME -- check for types that deref to `Self`,
-        // like `Rc<Self>` and so on.
-        //
-        // Note also that the current code will break if this type
-        // includes any of the type parameters defined on the method
-        // -- but this could be overcome.
-        return false;
-    }
-
-    fn record_static_candidate(&mut self, source: CandidateSource) {
-        self.static_candidates.push(source);
-    }
-
-    fn xform_self_ty(&self, method: &Rc<ty::Method>, substs: &subst::Substs) -> ty::t {
-        let xform_self_ty = method.fty.sig.inputs[0].subst(self.tcx(), substs);
-        self.replace_late_bound_regions_with_fresh_var(method.fty.sig.binder_id, &xform_self_ty)
-    }
-
-    fn replace_late_bound_regions_with_fresh_var<T>(&self, binder_id: ast::NodeId, value: &T) -> T
-        where T : TypeFoldable + Repr
-    {
-        replace_late_bound_regions_with_fresh_var(self.fcx.infcx(), self.span, binder_id, value)
-    }
-}
-
-fn replace_late_bound_regions_with_fresh_var<T>(infcx: &infer::InferCtxt,
-                                                span: Span,
-                                                binder_id: ast::NodeId,
-                                                value: &T)
-                                                -> T
-    where T : TypeFoldable + Repr
-{
-    let (_, value) = replace_late_bound_regions(
-        infcx.tcx,
-        binder_id,
-        value,
-        |br| infcx.next_region_var(infer::LateBoundRegion(span, br)));
-    value
-}
-
-fn trait_method(tcx: &ty::ctxt,
-                trait_def_id: ast::DefId,
-                method_name: ast::Name)
-                -> Option<(uint, Rc<ty::Method>)>
-{
-    /*!
-     * Find method with name `method_name` defined in `trait_def_id` and return it,
-     * along with its index (or `None`, if no such method).
-     */
-
-    let trait_items = ty::trait_items(tcx, trait_def_id);
-    trait_items
-        .iter()
-        .enumerate()
-        .find(|&(_, ref item)| item.name() == method_name)
-        .and_then(|(idx, item)| item.as_opt_method().map(|m| (idx, m)))
-}
-
-fn impl_method(tcx: &ty::ctxt,
-               impl_def_id: ast::DefId,
-               method_name: ast::Name)
-               -> Option<Rc<ty::Method>>
-{
-    let impl_items = tcx.impl_items.borrow();
-    let impl_items = impl_items.get(&impl_def_id).unwrap();
-    impl_items
-        .iter()
-        .map(|&did| ty::impl_or_trait_item(tcx, did.def_id()))
-        .find(|m| m.name() == method_name)
-        .and_then(|item| item.as_opt_method())
-}
-
-impl Repr for Candidate {
-    fn repr(&self, tcx: &ty::ctxt) -> String {
-        format!("Candidate(rcvr_ty={}, rcvr_substs={}, method_ty={}, origin={})",
-                self.xform_self_ty.repr(tcx),
-                self.rcvr_substs.repr(tcx),
-                self.method_ty.repr(tcx),
-                self.origin)
-    }
-}
-
-impl Repr for ExtensionCandidate {
-    fn repr(&self, tcx: &ty::ctxt) -> String {
-        format!("ExtensionCandidate(obligation={}, xform_self_ty={}, method_ty={}, method_num={})",
-                self.obligation.repr(tcx),
-                self.xform_self_ty.repr(tcx),
-                self.method_ty.repr(tcx),
-                self.method_num)
-    }
-}
-
-impl Candidate {
-    fn to_source(&self) -> CandidateSource {
-        match self.origin {
-            MethodStatic(def_id) => {
-                ImplSource(def_id)
-            }
-            MethodStaticUnboxedClosure(..) => {
-                panic!("MethodStaticUnboxedClosure only used in trans")
-            }
-            MethodTypeParam(ref param) => {
-                TraitSource(param.trait_ref.def_id)
-            }
-            MethodTraitObject(ref obj) => {
-                TraitSource(obj.trait_ref.def_id)
-            }
-        }
-    }
-}
-
-impl ExtensionCandidate {
-    fn to_source(&self) -> CandidateSource {
-        TraitSource(self.obligation.trait_ref.def_id)
-    }
-}
diff --git a/src/librustc/middle/typeck/check/method/confirm.rs b/src/librustc/middle/typeck/check/method/confirm.rs
new file mode 100644
index 00000000000..ba64a1e23a7
--- /dev/null
+++ b/src/librustc/middle/typeck/check/method/confirm.rs
@@ -0,0 +1,603 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use super::probe;
+
+use middle::subst;
+use middle::subst::Subst;
+use middle::traits;
+use middle::ty;
+use middle::typeck::check;
+use middle::typeck::check::{FnCtxt, NoPreference, PreferMutLvalue};
+use middle::typeck::{MethodCall, MethodCallee, MethodObject, MethodOrigin,
+                     MethodParam, MethodStatic, MethodTraitObject, MethodTypeParam};
+use middle::typeck::infer;
+use middle::typeck::infer::InferCtxt;
+use syntax::ast;
+use syntax::codemap::Span;
+use std::rc::Rc;
+use std::mem;
+use util::ppaux::Repr;
+
+struct ConfirmContext<'a, 'tcx:'a> {
+    fcx: &'a FnCtxt<'a, 'tcx>,
+    span: Span,
+    self_expr: &'a ast::Expr,
+}
+
+pub fn confirm(fcx: &FnCtxt,
+               span: Span,
+               self_expr: &ast::Expr,
+               unadjusted_self_ty: ty::t,
+               pick: probe::Pick,
+               supplied_method_types: Vec<ty::t>)
+               -> MethodCallee
+{
+    debug!("confirm(unadjusted_self_ty={}, pick={}, supplied_method_types={})",
+           unadjusted_self_ty.repr(fcx.tcx()),
+           pick.repr(fcx.tcx()),
+           supplied_method_types.repr(fcx.tcx()));
+
+    let mut confirm_cx = ConfirmContext::new(fcx, span, self_expr);
+    confirm_cx.confirm(unadjusted_self_ty, pick, supplied_method_types)
+}
+
+impl<'a,'tcx> ConfirmContext<'a,'tcx> {
+    fn new(fcx: &'a FnCtxt<'a, 'tcx>,
+           span: Span,
+           self_expr: &'a ast::Expr)
+           -> ConfirmContext<'a, 'tcx>
+    {
+        ConfirmContext { fcx: fcx, span: span, self_expr: self_expr }
+    }
+
+    fn confirm(&mut self,
+               unadjusted_self_ty: ty::t,
+               pick: probe::Pick,
+               supplied_method_types: Vec<ty::t>)
+               -> MethodCallee
+    {
+        // Adjust the self expression the user provided and obtain the adjusted type.
+        let self_ty = self.adjust_self_ty(unadjusted_self_ty, &pick.adjustment);
+
+        // Make sure nobody calls `drop()` explicitly.
+        self.enforce_drop_trait_limitations(&pick);
+
+        // Create substitutions for the method's type parameters.
+        let (rcvr_substs, method_origin) =
+            self.fresh_receiver_substs(self_ty, &pick);
+        let (method_types, method_regions) =
+            self.instantiate_method_substs(&pick, supplied_method_types);
+        let all_substs = rcvr_substs.with_method(method_types, method_regions);
+        debug!("all_substs={}", all_substs.repr(self.tcx()));
+
+        // Create the final signature for the method, replacing late-bound regions.
+        let method_sig = self.instantiate_method_sig(&pick, &all_substs);
+        let method_self_ty = method_sig.inputs[0];
+
+        // Unify the (adjusted) self type with what the method expects.
+        self.unify_receivers(self_ty, method_self_ty);
+
+        // Add any trait/regions obligations specified on the method's type parameters.
+        self.add_obligations(&pick, &all_substs);
+
+        // Create the final `MethodCallee`.
+        let fty = ty::mk_bare_fn(self.tcx(), ty::BareFnTy {
+            sig: method_sig,
+            fn_style: pick.method_ty.fty.fn_style,
+            abi: pick.method_ty.fty.abi.clone(),
+        });
+        let callee = MethodCallee {
+            origin: method_origin,
+            ty: fty,
+            substs: all_substs
+        };
+
+        // If this is an `&mut self` method, bias the receiver
+        // expression towards mutability (this will switch
+        // e.g. `Deref` to `DerefMut` in oveloaded derefs and so on).
+        self.fixup_derefs_on_method_receiver_if_necessary(&callee);
+
+        callee
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // ADJUSTMENTS
+
+    fn adjust_self_ty(&mut self,
+                      unadjusted_self_ty: ty::t,
+                      adjustment: &probe::PickAdjustment)
+                      -> ty::t
+    {
+        // Construct the actual adjustment and write it into the table
+        let auto_deref_ref = self.create_ty_adjustment(adjustment);
+
+        // Commit the autoderefs by calling `autoderef again, but this
+        // time writing the results into the various tables.
+        let (autoderefd_ty, n, result) =
+            check::autoderef(
+                self.fcx, self.span, unadjusted_self_ty, Some(self.self_expr.id), NoPreference,
+                |_, n| if n == auto_deref_ref.autoderefs { Some(()) } else { None });
+        assert_eq!(n, auto_deref_ref.autoderefs);
+        assert_eq!(result, Some(()));
+
+        let final_ty =
+            ty::adjust_ty_for_autoref(self.tcx(), self.span, autoderefd_ty,
+                                      auto_deref_ref.autoref.as_ref());
+
+        // Write out the final adjustment.
+        self.fcx.write_adjustment(self.self_expr.id, self.span, ty::AdjustDerefRef(auto_deref_ref));
+
+        final_ty
+    }
+
+    fn create_ty_adjustment(&mut self,
+                            adjustment: &probe::PickAdjustment)
+                            -> ty::AutoDerefRef
+    {
+        match *adjustment {
+            probe::AutoDeref(num) => {
+                ty::AutoDerefRef {
+                    autoderefs: num,
+                    autoref: None
+                }
+            }
+            probe::AutoUnsizeLength(autoderefs, len) => {
+                ty::AutoDerefRef {
+                    autoderefs: autoderefs,
+                    autoref: Some(ty::AutoUnsize(ty::UnsizeLength(len)))
+                }
+            }
+            probe::AutoRef(mutability, ref sub_adjustment) => {
+                let deref = self.create_ty_adjustment(&**sub_adjustment);
+                let region = self.infcx().next_region_var(infer::Autoref(self.span));
+                wrap_autoref(deref, |base| ty::AutoPtr(region, mutability, base))
+            }
+        }
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    //
+
+    fn fresh_receiver_substs(&mut self,
+                             self_ty: ty::t,
+                             pick: &probe::Pick)
+                             -> (subst::Substs, MethodOrigin)
+    {
+        /*!
+         * Returns a set of substitutions for the method *receiver*
+         * where all type and region parameters are instantiated with
+         * fresh variables. This substitution does not include any
+         * parameters declared on the method itself.
+         */
+
+        match pick.kind {
+            probe::InherentImplPick(impl_def_id) => {
+                assert!(ty::impl_trait_ref(self.tcx(), impl_def_id).is_none(),
+                        "impl {} is not an inherent impl", impl_def_id);
+                let impl_polytype = check::impl_self_ty(self.fcx, self.span, impl_def_id);
+
+                (impl_polytype.substs, MethodStatic(pick.method_ty.def_id))
+            }
+
+            probe::ObjectPick(trait_def_id, method_num, real_index) => {
+                self.extract_trait_ref(self_ty, |this, object_ty, data| {
+                    // The object data has no entry for the Self
+                    // Type. For the purposes of this method call, we
+                    // substitute the object type itself. This
+                    // wouldn't be a sound substitution in all cases,
+                    // since each instance of the object type is a
+                    // different existential and hence could match
+                    // distinct types (e.g., if `Self` appeared as an
+                    // argument type), but those cases have already
+                    // been ruled out when we deemed the trait to be
+                    // "object safe".
+                    let substs = data.principal.substs.clone().with_self_ty(object_ty);
+                    let original_trait_ref =
+                        Rc::new(ty::TraitRef::new(data.principal.def_id, substs));
+                    let upcast_trait_ref = this.upcast(original_trait_ref.clone(), trait_def_id);
+                    debug!("original_trait_ref={} upcast_trait_ref={} target_trait={}",
+                           original_trait_ref.repr(this.tcx()),
+                           upcast_trait_ref.repr(this.tcx()),
+                           trait_def_id.repr(this.tcx()));
+                    let substs = upcast_trait_ref.substs.clone();
+                    let origin = MethodTraitObject(MethodObject {
+                        trait_ref: upcast_trait_ref,
+                        object_trait_id: trait_def_id,
+                        method_num: method_num,
+                        real_index: real_index,
+                    });
+                    (substs, origin)
+                })
+            }
+
+            probe::ExtensionImplPick(impl_def_id, method_num) => {
+                // The method being invoked is the method as defined on the trait,
+                // so return the substitutions from the trait. Consider:
+                //
+                //     impl<A,B,C> Trait<A,B> for Foo<C> { ... }
+                //
+                // If we instantiate A, B, and C with $A, $B, and $C
+                // respectively, then we want to return the type
+                // parameters from the trait ([$A,$B]), not those from
+                // the impl ([$A,$B,$C]) not the receiver type ([$C]).
+                let impl_polytype = check::impl_self_ty(self.fcx, self.span, impl_def_id);
+                let impl_trait_ref = ty::impl_trait_ref(self.tcx(), impl_def_id)
+                                     .unwrap()
+                                     .subst(self.tcx(), &impl_polytype.substs);
+                let origin = MethodTypeParam(MethodParam { trait_ref: impl_trait_ref.clone(),
+                                                           method_num: method_num });
+                (impl_trait_ref.substs.clone(), origin)
+            }
+
+            probe::TraitPick(trait_def_id, method_num) => {
+                let trait_def = ty::lookup_trait_def(self.tcx(), trait_def_id);
+
+                // Make a trait reference `$0 : Trait<$1...$n>`
+                // consisting entirely of type variables. Later on in
+                // the process we will unify the transformed-self-type
+                // of the method with the actual type in order to
+                // unify some of these variables.
+                let substs = self.infcx().fresh_substs_for_trait(self.span,
+                                                                 &trait_def.generics,
+                                                                 self.infcx().next_ty_var());
+
+                let trait_ref = Rc::new(ty::TraitRef::new(trait_def_id, substs.clone()));
+                let origin = MethodTypeParam(MethodParam { trait_ref: trait_ref,
+                                                           method_num: method_num });
+                (substs, origin)
+            }
+
+            probe::WhereClausePick(ref trait_ref, method_num) => {
+                let origin = MethodTypeParam(MethodParam { trait_ref: (*trait_ref).clone(),
+                                                           method_num: method_num });
+                (trait_ref.substs.clone(), origin)
+            }
+        }
+    }
+
+    fn extract_trait_ref<R>(&mut self,
+                            self_ty: ty::t,
+                            closure: |&mut ConfirmContext<'a,'tcx>, ty::t, &ty::TyTrait| -> R)
+                            -> R
+    {
+        // If we specified that this is an object method, then the
+        // self-type ought to be something that can be dereferenced to
+        // yield an object-type (e.g., `&Object` or `Box<Object>`
+        // etc).
+
+        let (_, _, result) =
+            check::autoderef(
+                self.fcx, self.span, self_ty, None, NoPreference,
+                |ty, _| {
+                    match ty::get(ty).sty {
+                        ty::ty_trait(ref data) => Some(closure(self, ty, &**data)),
+                        _ => None,
+                    }
+                });
+
+        match result {
+            Some(r) => r,
+            None => {
+                self.tcx().sess.span_bug(
+                    self.span,
+                    format!("self-type `{}` for ObjectPick never dereferenced to an object",
+                            self_ty.repr(self.tcx()))[])
+            }
+        }
+    }
+
+    fn instantiate_method_substs(&mut self,
+                                 pick: &probe::Pick,
+                                 supplied_method_types: Vec<ty::t>)
+                                 -> (Vec<ty::t>, Vec<ty::Region>)
+    {
+        // Determine the values for the generic parameters of the method.
+        // If they were not explicitly supplied, just construct fresh
+        // variables.
+        let num_supplied_types = supplied_method_types.len();
+        let num_method_types = pick.method_ty.generics.types.len(subst::FnSpace);
+        let method_types = {
+            if num_supplied_types == 0u {
+                self.fcx.infcx().next_ty_vars(num_method_types)
+            } else if num_method_types == 0u {
+                span_err!(self.tcx().sess, self.span, E0035,
+                    "does not take type parameters");
+                self.fcx.infcx().next_ty_vars(num_method_types)
+            } else if num_supplied_types != num_method_types {
+                span_err!(self.tcx().sess, self.span, E0036,
+                    "incorrect number of type parameters given for this method");
+                Vec::from_elem(num_method_types, ty::mk_err())
+            } else {
+                supplied_method_types
+            }
+        };
+
+        // Create subst for early-bound lifetime parameters, combining
+        // parameters from the type and those from the method.
+        //
+        // FIXME -- permit users to manually specify lifetimes
+        let method_regions =
+            self.fcx.infcx().region_vars_for_defs(
+                self.span,
+                pick.method_ty.generics.regions.get_slice(subst::FnSpace));
+
+        (method_types, method_regions)
+    }
+
+    fn unify_receivers(&mut self,
+                       self_ty: ty::t,
+                       method_self_ty: ty::t)
+    {
+        match self.fcx.mk_subty(false, infer::Misc(self.span), self_ty, method_self_ty) {
+            Ok(_) => {}
+            Err(_) => {
+                self.tcx().sess.span_bug(
+                    self.span,
+                    format!(
+                        "{} was a subtype of {} but now is not?",
+                        self_ty.repr(self.tcx()),
+                        method_self_ty.repr(self.tcx()))[]);
+            }
+        }
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    //
+
+    fn instantiate_method_sig(&mut self,
+                              pick: &probe::Pick,
+                              all_substs: &subst::Substs)
+                              -> ty::FnSig
+    {
+        let ref bare_fn_ty = pick.method_ty.fty;
+        let fn_sig = bare_fn_ty.sig.subst(self.tcx(), all_substs);
+        self.infcx().replace_late_bound_regions_with_fresh_var(fn_sig.binder_id,
+                                                               self.span,
+                                                               infer::FnCall,
+                                                               &fn_sig).0
+    }
+
+    fn add_obligations(&mut self,
+                       pick: &probe::Pick,
+                       all_substs: &subst::Substs) {
+        // FIXME(DST). Super hack. For a method on a trait object
+        // `Trait`, the generic signature requires that
+        // `Self:Trait`. Since, for an object, we bind `Self` to the
+        // type `Trait`, this leads to an obligation
+        // `Trait:Trait`. Until such time we DST is fully implemented,
+        // that obligation is not necessarily satisfied. (In the
+        // future, it would be.)
+        //
+        // To sidestep this, we overwrite the binding for `Self` with
+        // `err` (just for trait objects) when we generate the
+        // obligations.  This causes us to generate the obligation
+        // `err:Trait`, and the error type is considered to implement
+        // all traits, so we're all good. Hack hack hack.
+        match pick.kind {
+            probe::ObjectPick(..) => {
+                let mut temp_substs = all_substs.clone();
+                temp_substs.types.get_mut_slice(subst::SelfSpace)[0] = ty::mk_err();
+                self.fcx.add_obligations_for_parameters(
+                    traits::ObligationCause::misc(self.span),
+                    &temp_substs,
+                    &pick.method_ty.generics);
+            }
+            _ => {
+                self.fcx.add_obligations_for_parameters(
+                    traits::ObligationCause::misc(self.span),
+                    all_substs,
+                    &pick.method_ty.generics);
+            }
+        }
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // RECONCILIATION
+
+    fn fixup_derefs_on_method_receiver_if_necessary(&self,
+                                                    method_callee: &MethodCallee) {
+        /*!
+         * When we select a method with an `&mut self` receiver, we have to go
+         * convert any auto-derefs, indices, etc from `Deref` and `Index` into
+         * `DerefMut` and `IndexMut` respectively.
+         */
+
+        let sig = match ty::get(method_callee.ty).sty {
+            ty::ty_bare_fn(ref f) => f.sig.clone(),
+            ty::ty_closure(ref f) => f.sig.clone(),
+            _ => return,
+        };
+
+        match ty::get(sig.inputs[0]).sty {
+            ty::ty_rptr(_, ty::mt {
+                ty: _,
+                mutbl: ast::MutMutable,
+            }) => {}
+            _ => return,
+        }
+
+        // Gather up expressions we want to munge.
+        let mut exprs = Vec::new();
+        exprs.push(self.self_expr);
+        loop {
+            let last = exprs[exprs.len() - 1];
+            match last.node {
+                ast::ExprParen(ref expr) |
+                ast::ExprField(ref expr, _, _) |
+                ast::ExprTupField(ref expr, _, _) |
+                ast::ExprSlice(ref expr, _, _, _) |
+                ast::ExprIndex(ref expr, _) |
+                ast::ExprUnary(ast::UnDeref, ref expr) => exprs.push(&**expr),
+                _ => break,
+            }
+        }
+
+        debug!("fixup_derefs_on_method_receiver_if_necessary: exprs={}",
+               exprs.repr(self.tcx()));
+
+        // Fix up autoderefs and derefs.
+        for (i, expr) in exprs.iter().rev().enumerate() {
+            // Count autoderefs.
+            let autoderef_count = match self.fcx
+                                            .inh
+                                            .adjustments
+                                            .borrow()
+                                            .get(&expr.id) {
+                Some(&ty::AdjustDerefRef(ty::AutoDerefRef {
+                    autoderefs: autoderef_count,
+                    autoref: _
+                })) => autoderef_count,
+                Some(_) | None => 0,
+            };
+
+            debug!("fixup_derefs_on_method_receiver_if_necessary: i={} expr={} autoderef_count={}",
+                   i, expr.repr(self.tcx()), autoderef_count);
+
+            if autoderef_count > 0 {
+                check::autoderef(self.fcx,
+                                 expr.span,
+                                 self.fcx.expr_ty(*expr),
+                                 Some(expr.id),
+                                 PreferMutLvalue,
+                                 |_, autoderefs| {
+                                     if autoderefs == autoderef_count + 1 {
+                                         Some(())
+                                     } else {
+                                         None
+                                     }
+                                 });
+            }
+
+            // Don't retry the first one or we might infinite loop!
+            if i != 0 {
+                match expr.node {
+                    ast::ExprIndex(ref base_expr, _) => {
+                        let mut base_adjustment =
+                            match self.fcx.inh.adjustments.borrow().get(&base_expr.id) {
+                                Some(&ty::AdjustDerefRef(ref adr)) => (*adr).clone(),
+                                None => ty::AutoDerefRef { autoderefs: 0, autoref: None },
+                                Some(_) => {
+                                    self.tcx().sess.span_bug(
+                                        base_expr.span,
+                                        "unexpected adjustment type");
+                                }
+                            };
+
+                        // If this is an overloaded index, the
+                        // adjustment will include an extra layer of
+                        // autoref because the method is an &self/&mut
+                        // self method. We have to peel it off to get
+                        // the raw adjustment that `try_index_step`
+                        // expects. This is annoying and horrible. We
+                        // ought to recode this routine so it doesn't
+                        // (ab)use the normal type checking paths.
+                        base_adjustment.autoref = match base_adjustment.autoref {
+                            None => { None }
+                            Some(ty::AutoPtr(_, _, None)) => { None }
+                            Some(ty::AutoPtr(_, _, Some(box r))) => { Some(r) }
+                            Some(_) => {
+                                self.tcx().sess.span_bug(
+                                    base_expr.span,
+                                    "unexpected adjustment autoref");
+                            }
+                        };
+
+                        let adjusted_base_ty =
+                            self.fcx.adjust_expr_ty(
+                                &**base_expr,
+                                Some(&ty::AdjustDerefRef(base_adjustment.clone())));
+
+                        check::try_index_step(
+                            self.fcx,
+                            MethodCall::expr(expr.id),
+                            *expr,
+                            &**base_expr,
+                            adjusted_base_ty,
+                            base_adjustment,
+                            PreferMutLvalue);
+                    }
+                    ast::ExprUnary(ast::UnDeref, ref base_expr) => {
+                        // if this is an overloaded deref, then re-evaluate with
+                        // a preference for mut
+                        let method_call = MethodCall::expr(expr.id);
+                        if self.fcx.inh.method_map.borrow().contains_key(&method_call) {
+                            check::try_overloaded_deref(
+                                self.fcx,
+                                expr.span,
+                                Some(method_call),
+                                Some(&**base_expr),
+                                self.fcx.expr_ty(&**base_expr),
+                                PreferMutLvalue);
+                        }
+                    }
+                    _ => {}
+                }
+            }
+        }
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // MISCELLANY
+
+    fn tcx(&self) -> &'a ty::ctxt<'tcx> {
+        self.fcx.tcx()
+    }
+
+    fn infcx(&self) -> &'a InferCtxt<'a, 'tcx> {
+        self.fcx.infcx()
+    }
+
+    fn enforce_drop_trait_limitations(&self, pick: &probe::Pick) {
+        // Disallow calls to the method `drop` defined in the `Drop` trait.
+        match pick.method_ty.container {
+            ty::TraitContainer(trait_def_id) => {
+                if Some(trait_def_id) == self.tcx().lang_items.drop_trait() {
+                    span_err!(self.tcx().sess, self.span, E0040,
+                              "explicit call to destructor");
+                }
+            }
+            ty::ImplContainer(..) => {
+                // Since `drop` is a trait method, we expect that any
+                // potential calls to it will wind up in the other
+                // arm. But just to be sure, check that the method id
+                // does not appear in the list of destructors.
+                assert!(!self.tcx().destructors.borrow().contains(&pick.method_ty.def_id));
+            }
+        }
+    }
+
+    fn upcast(&mut self,
+              source_trait_ref: Rc<ty::TraitRef>,
+              target_trait_def_id: ast::DefId)
+              -> Rc<ty::TraitRef>
+    {
+        for super_trait_ref in traits::supertraits(self.tcx(), source_trait_ref.clone()) {
+            if super_trait_ref.def_id == target_trait_def_id {
+                return super_trait_ref;
+            }
+        }
+
+        self.tcx().sess.span_bug(
+            self.span,
+            format!("cannot upcast `{}` to `{}`",
+                    source_trait_ref.repr(self.tcx()),
+                    target_trait_def_id.repr(self.tcx()))[]);
+    }
+}
+
+fn wrap_autoref(mut deref: ty::AutoDerefRef,
+                base_fn: |Option<Box<ty::AutoRef>>| -> ty::AutoRef)
+                -> ty::AutoDerefRef {
+    let autoref = mem::replace(&mut deref.autoref, None);
+    let autoref = autoref.map(|r| box r);
+    deref.autoref = Some(base_fn(autoref));
+    deref
+}
diff --git a/src/librustc/middle/typeck/check/method/doc.rs b/src/librustc/middle/typeck/check/method/doc.rs
new file mode 100644
index 00000000000..8c691e02ca9
--- /dev/null
+++ b/src/librustc/middle/typeck/check/method/doc.rs
@@ -0,0 +1,126 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/*!
+
+# Method lookup
+
+Method lookup can be rather complex due to the interaction of a number
+of factors, such as self types, autoderef, trait lookup, etc. This
+file provides an overview of the process. More detailed notes are in
+the code itself, naturally.
+
+One way to think of method lookup is that we convert an expression of
+the form:
+
+    receiver.method(...)
+
+into a more explicit UFCS form:
+
+    Trait::method(ADJ(receiver), ...) // for a trait call
+    ReceiverType::method(ADJ(receiver), ...) // for an inherent method call
+
+Here `ADJ` is some kind of adjustment, which is typically a series of
+autoderefs and then possibly an autoref (e.g., `&**receiver`). However
+we sometimes do other adjustments and coercions along the way, in
+particular unsizing (e.g., converting from `[T, ..n]` to `[T]`).
+
+## The Two Phases
+
+Method lookup is divided into two major phases: probing (`probe.rs`)
+and confirmation (`confirm.rs`). The probe phase is when we decide
+what method to call and how to adjust the receiver. The confirmation
+phase "applies" this selection, updating the side-tables, unifying
+type variables, and otherwise doing side-effectful things.
+
+One reason for this division is to be more amenable to caching.  The
+probe phase produces a "pick" (`probe::Pick`), which is designed to be
+cacheable across method-call sites. Therefore, it does not include
+inference variables or other information.
+
+## Probe phase
+
+The probe phase (`probe.rs`) decides what method is being called and
+how to adjust the receiver.
+
+### Steps
+
+The first thing that the probe phase does is to create a series of
+*steps*. This is done by progressively dereferencing the receiver type
+until it cannot be deref'd anymore, as well as applying an optional
+"unsize" step. So if the receiver has type `Rc<Box<[T, ..3]>>`, this
+might yield:
+
+    Rc<Box<[T, ..3]>>
+    Box<[T, ..3]>
+    [T, ..3]
+    [T]
+
+### Candidate assembly
+
+We then search along those steps to create a list of *candidates*. A
+`Candidate` is a method item that might plausibly be the method being
+invoked. For each candidate, we'll derive a "transformed self type"
+that takes into account explicit self.
+
+Candidates are grouped into two kinds, inherent and extension.
+
+**Inherent candidates** are those that are derived from the
+type of the receiver itself.  So, if you have a receiver of some
+nominal type `Foo` (e.g., a struct), any methods defined within an
+impl like `impl Foo` are inherent methods.  Nothing needs to be
+imported to use an inherent method, they are associated with the type
+itself (note that inherent impls can only be defined in the same
+module as the type itself).
+
+FIXME: Inherent candidates are not always derived from impls.  If you
+have a trait object, such as a value of type `Box<ToString>`, then the
+trait methods (`to_string()`, in this case) are inherently associated
+with it. Another case is type parameters, in which case the methods of
+their bounds are inherent. However, this part of the rules is subject
+to change: when DST's "impl Trait for Trait" is complete, trait object
+dispatch could be subsumed into trait matching, and the type parameter
+behavior should be reconsidered in light of where clauses.
+
+**Extension candidates** are derived from imported traits.  If I have
+the trait `ToString` imported, and I call `to_string()` on a value of
+type `T`, then we will go off to find out whether there is an impl of
+`ToString` for `T`.  These kinds of method calls are called "extension
+methods".  They can be defined in any module, not only the one that
+defined `T`.  Furthermore, you must import the trait to call such a
+method.
+
+So, let's continue our example. Imagine that we were calling a method
+`foo` with the receiver `Rc<Box<[T, ..3]>>` and there is a trait `Foo`
+that defines it with `&self` for the type `Rc<U>` as well as a method
+on the type `Box` that defines `Foo` but with `&mut self`. Then we
+might have two candidates:
+
+    &Rc<Box<[T, ..3]>> from the impl of `Foo` for `Rc<U>` where `U=Box<T, ..3]>
+    &mut Box<[T, ..3]>> from the inherent impl on `Box<U>` where `U=[T, ..3]`
+
+### Candidate search
+
+Finally, to actually pick the method, we will search down the steps,
+trying to match the receiver type against the candidate types. At
+each step, we also consider an auto-ref and auto-mut-ref to see whether
+that makes any of the candidates match. We pick the first step where
+we find a match.
+
+In the case of our example, the first step is `Rc<Box<[T, ..3]>>`,
+which does not itself match any candidate. But when we autoref it, we
+get the type `&Rc<Box<[T, ..3]>>` which does match. We would then
+recursively consider all where-clauses that appear on the impl: if
+those match (or we cannot rule out that they do), then this is the
+method we would pick. Otherwise, we would continue down the series of
+steps.
+
+*/
+
diff --git a/src/librustc/middle/typeck/check/method/mod.rs b/src/librustc/middle/typeck/check/method/mod.rs
new file mode 100644
index 00000000000..2cd98137057
--- /dev/null
+++ b/src/librustc/middle/typeck/check/method/mod.rs
@@ -0,0 +1,432 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/*! Method lookup: the secret sauce of Rust. See `doc.rs`. */
+
+use middle::subst;
+use middle::subst::{Subst};
+use middle::traits;
+use middle::ty::*;
+use middle::ty;
+use middle::typeck::astconv::AstConv;
+use middle::typeck::check::{FnCtxt};
+use middle::typeck::check::{impl_self_ty};
+use middle::typeck::check::vtable;
+use middle::typeck::check::vtable::select_new_fcx_obligations;
+use middle::typeck::infer;
+use middle::typeck::{MethodCallee};
+use middle::typeck::{MethodParam, MethodTypeParam};
+use util::ppaux::{Repr, UserString};
+
+use std::rc::Rc;
+use syntax::ast::{DefId};
+use syntax::ast;
+use syntax::codemap::Span;
+
+mod confirm;
+mod doc;
+mod probe;
+
+pub enum MethodError {
+    // Did not find an applicable method, but we did find various
+    // static methods that may apply.
+    NoMatch(Vec<CandidateSource>),
+
+    // Multiple methods might apply.
+    Ambiguity(Vec<CandidateSource>),
+}
+
+// A pared down enum describing just the places from which a method
+// candidate can arise. Used for error reporting only.
+#[deriving(PartialOrd, Ord, PartialEq, Eq)]
+pub enum CandidateSource {
+    ImplSource(ast::DefId),
+    TraitSource(/* trait id */ ast::DefId),
+}
+
+type MethodIndex = uint; // just for doc purposes
+
+pub fn exists(fcx: &FnCtxt,
+              span: Span,
+              method_name: ast::Name,
+              self_ty: ty::t,
+              call_expr_id: ast::NodeId)
+              -> bool
+{
+    /*!
+     * Determines whether the type `self_ty` supports a method name `method_name` or not.
+     */
+
+    match probe::probe(fcx, span, method_name, self_ty, call_expr_id) {
+        Ok(_) => true,
+        Err(NoMatch(_)) => false,
+        Err(Ambiguity(_)) => true,
+    }
+}
+
+pub fn lookup(fcx: &FnCtxt,
+              span: Span,
+              method_name: ast::Name,
+              self_ty: ty::t,
+              supplied_method_types: Vec<ty::t>,
+              call_expr_id: ast::NodeId,
+              self_expr: &ast::Expr)
+              -> Result<MethodCallee, MethodError>
+{
+    /*!
+     * Performs method lookup. If lookup is successful, it will return the callee
+     * and store an appropriate adjustment for the self-expr. In some cases it may
+     * report an error (e.g., invoking the `drop` method).
+     *
+     * # Arguments
+     *
+     * Given a method call like `foo.bar::<T1,...Tn>(...)`:
+     *
+     * - `fcx`:                   the surrounding `FnCtxt` (!)
+     * - `span`:                  the span for the method call
+     * - `method_name`:           the name of the method being called (`bar`)
+     * - `self_ty`:               the (unadjusted) type of the self expression (`foo`)
+     * - `supplied_method_types`: the explicit method type parameters, if any (`T1..Tn`)
+     * - `self_expr`:             the self expression (`foo`)
+     */
+
+    debug!("lookup(method_name={}, self_ty={}, call_expr_id={}, self_expr={})",
+           method_name.repr(fcx.tcx()),
+           self_ty.repr(fcx.tcx()),
+           call_expr_id,
+           self_expr.repr(fcx.tcx()));
+
+    let pick = try!(probe::probe(fcx, span, method_name, self_ty, call_expr_id));
+    Ok(confirm::confirm(fcx, span, self_expr, self_ty, pick, supplied_method_types))
+}
+
+pub fn lookup_in_trait<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
+                                 span: Span,
+                                 self_expr: Option<&'a ast::Expr>,
+                                 m_name: ast::Name,
+                                 trait_def_id: DefId,
+                                 self_ty: ty::t,
+                                 opt_input_types: Option<Vec<ty::t>>)
+                                 -> Option<MethodCallee>
+{
+    lookup_in_trait_adjusted(fcx, span, self_expr, m_name, trait_def_id,
+                             ty::AutoDerefRef { autoderefs: 0, autoref: None },
+                             self_ty, opt_input_types)
+}
+
+pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
+                                          span: Span,
+                                          self_expr: Option<&'a ast::Expr>,
+                                          m_name: ast::Name,
+                                          trait_def_id: DefId,
+                                          autoderefref: ty::AutoDerefRef,
+                                          self_ty: ty::t,
+                                          opt_input_types: Option<Vec<ty::t>>)
+                                          -> Option<MethodCallee>
+{
+    /*!
+     * `lookup_in_trait_adjusted` is used for overloaded operators. It
+     * does a very narrow slice of what the normal probe/confirm path
+     * does. In particular, it doesn't really do any probing: it
+     * simply constructs an obligation for a particular trait with the
+     * given self-type and checks whether that trait is implemented.
+     *
+     * FIXME(#18741) -- It seems likely that we can consolidate some of this
+     * code with the other method-lookup code. In particular,
+     * autoderef on index is basically identical to autoderef with
+     * normal probes, except that the test also looks for built-in
+     * indexing. Also, the second half of this method is basically
+     * the same as confirmation.
+     */
+
+    debug!("lookup_in_trait_adjusted(self_ty={}, self_expr={}, m_name={}, trait_def_id={})",
+           self_ty.repr(fcx.tcx()),
+           self_expr.repr(fcx.tcx()),
+           m_name.repr(fcx.tcx()),
+           trait_def_id.repr(fcx.tcx()));
+
+    let trait_def = ty::lookup_trait_def(fcx.tcx(), trait_def_id);
+
+    let expected_number_of_input_types = trait_def.generics.types.len(subst::TypeSpace);
+    let input_types = match opt_input_types {
+        Some(input_types) => {
+            assert_eq!(expected_number_of_input_types, input_types.len());
+            input_types
+        }
+
+        None => {
+            fcx.inh.infcx.next_ty_vars(expected_number_of_input_types)
+        }
+    };
+
+    let number_assoc_types = trait_def.generics.types.len(subst::AssocSpace);
+    let assoc_types = fcx.inh.infcx.next_ty_vars(number_assoc_types);
+
+    assert_eq!(trait_def.generics.types.len(subst::FnSpace), 0);
+    assert!(trait_def.generics.regions.is_empty());
+
+    // Construct a trait-reference `self_ty : Trait<input_tys>`
+    let substs = subst::Substs::new_trait(input_types, Vec::new(), assoc_types, self_ty);
+    let trait_ref = Rc::new(ty::TraitRef::new(trait_def_id, substs));
+
+    // Construct an obligation
+    let obligation = traits::Obligation::misc(span, trait_ref.clone());
+
+    // Now we want to know if this can be matched
+    let mut selcx = traits::SelectionContext::new(fcx.infcx(),
+                                                  &fcx.inh.param_env,
+                                                  fcx);
+    if !selcx.evaluate_obligation(&obligation) {
+        debug!("--> Cannot match obligation");
+        return None; // Cannot be matched, no such method resolution is possible.
+    }
+
+    // Trait must have a method named `m_name` and it should not have
+    // type parameters or early-bound regions.
+    let tcx = fcx.tcx();
+    let (method_num, method_ty) = trait_method(tcx, trait_def_id, m_name).unwrap();
+    assert_eq!(method_ty.generics.types.len(subst::FnSpace), 0);
+    assert_eq!(method_ty.generics.regions.len(subst::FnSpace), 0);
+
+    // Substitute the trait parameters into the method type and
+    // instantiate late-bound regions to get the actual method type.
+    let ref bare_fn_ty = method_ty.fty;
+    let fn_sig = bare_fn_ty.sig.subst(tcx, &trait_ref.substs);
+    let fn_sig = fcx.infcx().replace_late_bound_regions_with_fresh_var(fn_sig.binder_id,
+                                                                       span,
+                                                                       infer::FnCall,
+                                                                       &fn_sig).0;
+    let transformed_self_ty = fn_sig.inputs[0];
+    let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
+        sig: fn_sig,
+        fn_style: bare_fn_ty.fn_style,
+        abi: bare_fn_ty.abi.clone(),
+    });
+
+    debug!("matched method fty={} obligation={}",
+           fty.repr(fcx.tcx()),
+           obligation.repr(fcx.tcx()));
+
+    // Register obligations for the parameters.  This will include the
+    // `Self` parameter, which in turn has a bound of the main trait,
+    // so this also effectively registers `obligation` as well.  (We
+    // used to register `obligation` explicitly, but that resulted in
+    // double error messages being reported.)
+    fcx.add_obligations_for_parameters(
+        traits::ObligationCause::misc(span),
+        &trait_ref.substs,
+        &method_ty.generics);
+
+    // FIXME(#18653) -- Try to resolve obligations, giving us more
+    // typing information, which can sometimes be needed to avoid
+    // pathological region inference failures.
+    vtable::select_new_fcx_obligations(fcx);
+
+    // Insert any adjustments needed (always an autoref of some mutability).
+    match self_expr {
+        None => { }
+
+        Some(self_expr) => {
+            debug!("inserting adjustment if needed (self-id = {}, \
+                   base adjustment = {}, explicit self = {})",
+                   self_expr.id, autoderefref, method_ty.explicit_self);
+
+            match method_ty.explicit_self {
+                ty::ByValueExplicitSelfCategory => {
+                    // Trait method is fn(self), no transformation needed.
+                    if !autoderefref.is_identity() {
+                        fcx.write_adjustment(
+                            self_expr.id,
+                            span,
+                            ty::AdjustDerefRef(autoderefref));
+                    }
+                }
+
+                ty::ByReferenceExplicitSelfCategory(..) => {
+                    // Trait method is fn(&self) or fn(&mut self), need an
+                    // autoref. Pull the region etc out of the type of first argument.
+                    match ty::get(transformed_self_ty).sty {
+                        ty::ty_rptr(region, ty::mt { mutbl, ty: _ }) => {
+                            let ty::AutoDerefRef { autoderefs, autoref } = autoderefref;
+                            let autoref = autoref.map(|r| box r);
+                            fcx.write_adjustment(
+                                self_expr.id,
+                                span,
+                                ty::AdjustDerefRef(ty::AutoDerefRef {
+                                    autoderefs: autoderefs,
+                                    autoref: Some(ty::AutoPtr(region, mutbl, autoref))
+                                }));
+                        }
+
+                        _ => {
+                            fcx.tcx().sess.span_bug(
+                                span,
+                                format!(
+                                    "trait method is &self but first arg is: {}",
+                                    transformed_self_ty.repr(fcx.tcx())).as_slice());
+                        }
+                    }
+                }
+
+                _ => {
+                    fcx.tcx().sess.span_bug(
+                        span,
+                        format!(
+                            "unexpected explicit self type in operator method: {}",
+                            method_ty.explicit_self).as_slice());
+                }
+            }
+        }
+    }
+
+    let callee = MethodCallee {
+        origin: MethodTypeParam(MethodParam{trait_ref: trait_ref.clone(),
+                                            method_num: method_num}),
+        ty: fty,
+        substs: trait_ref.substs.clone()
+    };
+
+    debug!("callee = {}", callee.repr(fcx.tcx()));
+
+    Some(callee)
+}
+
+pub fn report_error(fcx: &FnCtxt,
+                    span: Span,
+                    rcvr_ty: ty::t,
+                    method_name: ast::Name,
+                    error: MethodError)
+{
+    match error {
+        NoMatch(static_sources) => {
+            let cx = fcx.tcx();
+            let method_ustring = method_name.user_string(cx);
+
+            // True if the type is a struct and contains a field with
+            // the same name as the not-found method
+            let is_field = match ty::get(rcvr_ty).sty {
+                ty_struct(did, _) =>
+                    ty::lookup_struct_fields(cx, did)
+                        .iter()
+                        .any(|f| f.name.user_string(cx) == method_ustring),
+                _ => false
+            };
+
+            fcx.type_error_message(
+                span,
+                |actual| {
+                    format!("type `{}` does not implement any \
+                             method in scope named `{}`",
+                            actual,
+                            method_ustring)
+                },
+                rcvr_ty,
+                None);
+
+            // If the method has the name of a field, give a help note
+            if is_field {
+                cx.sess.span_note(span,
+                    format!("use `(s.{0})(...)` if you meant to call the \
+                            function stored in the `{0}` field", method_ustring).as_slice());
+            }
+
+            if static_sources.len() > 0 {
+                fcx.tcx().sess.fileline_note(
+                    span,
+                    "found defined static methods, maybe a `self` is missing?");
+
+                report_candidates(fcx, span, method_name, static_sources);
+            }
+        }
+
+        Ambiguity(sources) => {
+            span_err!(fcx.sess(), span, E0034,
+                      "multiple applicable methods in scope");
+
+            report_candidates(fcx, span, method_name, sources);
+        }
+    }
+
+    fn report_candidates(fcx: &FnCtxt,
+                         span: Span,
+                         method_name: ast::Name,
+                         mut sources: Vec<CandidateSource>) {
+        sources.sort();
+        sources.dedup();
+
+        for (idx, source) in sources.iter().enumerate() {
+            match *source {
+                ImplSource(impl_did) => {
+                    // Provide the best span we can. Use the method, if local to crate, else
+                    // the impl, if local to crate (method may be defaulted), else the call site.
+                    let method = impl_method(fcx.tcx(), impl_did, method_name).unwrap();
+                    let impl_span = fcx.tcx().map.def_id_span(impl_did, span);
+                    let method_span = fcx.tcx().map.def_id_span(method.def_id, impl_span);
+
+                    let impl_ty = impl_self_ty(fcx, span, impl_did).ty;
+
+                    let insertion = match impl_trait_ref(fcx.tcx(), impl_did) {
+                        None => format!(""),
+                        Some(trait_ref) => format!(" of the trait `{}`",
+                                                   ty::item_path_str(fcx.tcx(),
+                                                                     trait_ref.def_id)),
+                    };
+
+                    span_note!(fcx.sess(), method_span,
+                               "candidate #{} is defined in an impl{} for the type `{}`",
+                               idx + 1u,
+                               insertion,
+                               impl_ty.user_string(fcx.tcx()));
+                }
+                TraitSource(trait_did) => {
+                    let (_, method) = trait_method(fcx.tcx(), trait_did, method_name).unwrap();
+                    let method_span = fcx.tcx().map.def_id_span(method.def_id, span);
+                    span_note!(fcx.sess(), method_span,
+                               "candidate #{} is defined in the trait `{}`",
+                               idx + 1u,
+                               ty::item_path_str(fcx.tcx(), trait_did));
+                }
+            }
+        }
+    }
+}
+
+fn trait_method(tcx: &ty::ctxt,
+                trait_def_id: ast::DefId,
+                method_name: ast::Name)
+                -> Option<(uint, Rc<ty::Method>)>
+{
+    /*!
+     * Find method with name `method_name` defined in `trait_def_id` and return it,
+     * along with its index (or `None`, if no such method).
+     */
+
+    let trait_items = ty::trait_items(tcx, trait_def_id);
+    trait_items
+        .iter()
+        .enumerate()
+        .find(|&(_, ref item)| item.name() == method_name)
+        .and_then(|(idx, item)| item.as_opt_method().map(|m| (idx, m)))
+}
+
+fn impl_method(tcx: &ty::ctxt,
+               impl_def_id: ast::DefId,
+               method_name: ast::Name)
+               -> Option<Rc<ty::Method>>
+{
+    let impl_items = tcx.impl_items.borrow();
+    let impl_items = impl_items.get(&impl_def_id).unwrap();
+    impl_items
+        .iter()
+        .map(|&did| ty::impl_or_trait_item(tcx, did.def_id()))
+        .find(|m| m.name() == method_name)
+        .and_then(|item| item.as_opt_method())
+}
+
diff --git a/src/librustc/middle/typeck/check/method/probe.rs b/src/librustc/middle/typeck/check/method/probe.rs
new file mode 100644
index 00000000000..63f017e8041
--- /dev/null
+++ b/src/librustc/middle/typeck/check/method/probe.rs
@@ -0,0 +1,1011 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use super::Ambiguity;
+use super::CandidateSource;
+use super::ImplSource;
+use super::MethodError;
+use super::MethodIndex;
+use super::NoMatch;
+use super::TraitSource;
+
+use middle::subst;
+use middle::subst::Subst;
+use middle::traits;
+use middle::ty;
+use middle::typeck::check;
+use middle::typeck::check::{FnCtxt, NoPreference};
+use middle::typeck::{MethodObject};
+use middle::typeck::infer;
+use middle::typeck::infer::InferCtxt;
+use syntax::ast;
+use syntax::codemap::{Span, DUMMY_SP};
+use std::collections::HashSet;
+use std::rc::Rc;
+use util::ppaux::Repr;
+
+struct ProbeContext<'a, 'tcx:'a> {
+    fcx: &'a FnCtxt<'a, 'tcx>,
+    span: Span,
+    method_name: ast::Name,
+    steps: Rc<Vec<CandidateStep>>,
+    inherent_candidates: Vec<Candidate>,
+    extension_candidates: Vec<Candidate>,
+    impl_dups: HashSet<ast::DefId>,
+    static_candidates: Vec<CandidateSource>,
+}
+
+struct CandidateStep {
+    self_ty: ty::t,
+    adjustment: PickAdjustment
+}
+
+struct Candidate {
+    xform_self_ty: ty::t,
+    method_ty: Rc<ty::Method>,
+    kind: CandidateKind,
+}
+
+enum CandidateKind {
+    InherentImplCandidate(/* Impl */ ast::DefId, subst::Substs),
+    ObjectCandidate(MethodObject),
+    ExtensionImplCandidate(/* Impl */ ast::DefId, Rc<ty::TraitRef>, subst::Substs, MethodIndex),
+    UnboxedClosureCandidate(/* Trait */ ast::DefId, MethodIndex),
+    WhereClauseCandidate(Rc<ty::TraitRef>, MethodIndex),
+}
+
+pub struct Pick {
+    pub method_ty: Rc<ty::Method>,
+    pub adjustment: PickAdjustment,
+    pub kind: PickKind,
+}
+
+#[deriving(Clone,Show)]
+pub enum PickKind {
+    InherentImplPick(/* Impl */ ast::DefId),
+    ObjectPick(/* Trait */ ast::DefId, /* method_num */ uint, /* real_index */ uint),
+    ExtensionImplPick(/* Impl */ ast::DefId, MethodIndex),
+    TraitPick(/* Trait */ ast::DefId, MethodIndex),
+    WhereClausePick(/* Trait */ Rc<ty::TraitRef>, MethodIndex),
+}
+
+pub type PickResult = Result<Pick, MethodError>;
+
+// This is a kind of "abstracted" version of ty::AutoAdjustment.  The
+// difference is that it doesn't embed any regions or other
+// specifics. The "confirmation" step recreates those details as
+// needed.
+#[deriving(Clone,Show)]
+pub enum PickAdjustment {
+    // Indicates that the source expression should be autoderef'd N times
+    //
+    // A = expr | *expr | **expr
+    AutoDeref(uint),
+
+    // Indicates that the source expression should be autoderef'd N
+    // times and then "unsized". This should probably eventually go
+    // away in favor of just coercing method receivers.
+    //
+    // A = unsize(expr | *expr | **expr)
+    AutoUnsizeLength(/* number of autoderefs */ uint, /* length*/ uint),
+
+    // Indicates that an autoref is applied after some number of other adjustments
+    //
+    // A = &A | &mut A
+    AutoRef(ast::Mutability, Box<PickAdjustment>),
+}
+
+pub fn probe(fcx: &FnCtxt,
+             span: Span,
+             method_name: ast::Name,
+             self_ty: ty::t,
+             call_expr_id: ast::NodeId)
+             -> PickResult
+{
+    debug!("probe(self_ty={}, method_name={}, call_expr_id={})",
+           self_ty.repr(fcx.tcx()),
+           method_name,
+           call_expr_id);
+
+    // FIXME(#18741) -- right now, creating the steps involves evaluating the
+    // `*` operator, which registers obligations that then escape into
+    // the global fulfillment context and thus has global
+    // side-effects. This is a bit of a pain to refactor. So just let
+    // it ride, although it's really not great, and in fact could I
+    // think cause spurious errors. Really though this part should
+    // take place in the `fcx.infcx().probe` below.
+    let steps = create_steps(fcx, span, self_ty);
+
+    debug!("ProbeContext: steps for self_ty={} are {}",
+           self_ty.repr(fcx.tcx()),
+           steps.repr(fcx.tcx()));
+
+    // this creates one big transaction so that all type variables etc
+    // that we create during the probe process are removed later
+    let mut steps = Some(steps); // FIXME(#18101) need once closures
+    fcx.infcx().probe(|| {
+        let steps = steps.take().unwrap();
+        let mut probe_cx = ProbeContext::new(fcx, span, method_name, steps);
+        probe_cx.assemble_inherent_candidates();
+        probe_cx.assemble_extension_candidates_for_traits_in_scope(call_expr_id);
+        probe_cx.pick()
+    })
+}
+
+fn create_steps(fcx: &FnCtxt, span: Span, self_ty: ty::t) -> Vec<CandidateStep> {
+    let mut steps = Vec::new();
+
+    let (fully_dereferenced_ty, dereferences, _) =
+        check::autoderef(
+            fcx, span, self_ty, None, NoPreference,
+            |t, d| {
+                let adjustment = consider_reborrow(t, d);
+                steps.push(CandidateStep { self_ty: t, adjustment: adjustment });
+                None::<()> // keep iterating until we can't anymore
+            });
+
+    match ty::get(fully_dereferenced_ty).sty {
+        ty::ty_vec(elem_ty, Some(len)) => {
+            steps.push(CandidateStep {
+                self_ty: ty::mk_vec(fcx.tcx(), elem_ty, None),
+                adjustment: AutoUnsizeLength(dereferences, len),
+            });
+        }
+        _ => {
+        }
+    }
+
+    return steps;
+
+    fn consider_reborrow(t: ty::t, d: uint) -> PickAdjustment {
+        // Insert a `&*` or `&mut *` if this is a reference type:
+        match ty::get(t).sty {
+            ty::ty_rptr(_, ref mt) => AutoRef(mt.mutbl, box AutoDeref(d+1)),
+            _ => AutoDeref(d),
+        }
+    }
+}
+
+impl<'a,'tcx> ProbeContext<'a,'tcx> {
+    fn new(fcx: &'a FnCtxt<'a,'tcx>,
+           span: Span,
+           method_name: ast::Name,
+           steps: Vec<CandidateStep>)
+           -> ProbeContext<'a,'tcx>
+    {
+        ProbeContext {
+            fcx: fcx,
+            span: span,
+            method_name: method_name,
+            inherent_candidates: Vec::new(),
+            extension_candidates: Vec::new(),
+            impl_dups: HashSet::new(),
+            steps: Rc::new(steps),
+            static_candidates: Vec::new(),
+        }
+    }
+
+    fn tcx(&self) -> &'a ty::ctxt<'tcx> {
+        self.fcx.tcx()
+    }
+
+    fn infcx(&self) -> &'a InferCtxt<'a, 'tcx> {
+        self.fcx.infcx()
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // CANDIDATE ASSEMBLY
+
+    fn assemble_inherent_candidates(&mut self) {
+        let steps = self.steps.clone();
+        for step in steps.iter() {
+            self.assemble_probe(step.self_ty);
+        }
+    }
+
+    fn assemble_probe(&mut self, self_ty: ty::t) {
+        debug!("assemble_probe: self_ty={}",
+               self_ty.repr(self.tcx()));
+
+        match ty::get(self_ty).sty {
+            ty::ty_trait(box ty::TyTrait { ref principal, bounds, .. }) => {
+                self.assemble_inherent_candidates_from_object(self_ty, &*principal, bounds);
+                self.assemble_inherent_impl_candidates_for_type(principal.def_id);
+            }
+            ty::ty_enum(did, _) |
+            ty::ty_struct(did, _) |
+            ty::ty_unboxed_closure(did, _, _) => {
+                self.assemble_inherent_impl_candidates_for_type(did);
+            }
+            ty::ty_param(p) => {
+                self.assemble_inherent_candidates_from_param(self_ty, p);
+            }
+            _ => {
+            }
+        }
+    }
+
+    fn assemble_inherent_impl_candidates_for_type(&mut self, def_id: ast::DefId) {
+        // Read the inherent implementation candidates for this type from the
+        // metadata if necessary.
+        ty::populate_implementations_for_type_if_necessary(self.tcx(), def_id);
+
+        for impl_infos in self.tcx().inherent_impls.borrow().get(&def_id).iter() {
+            for &impl_did in impl_infos.iter() {
+                self.assemble_inherent_impl_probe(impl_did);
+            }
+        }
+    }
+
+    fn assemble_inherent_impl_probe(&mut self, impl_did: ast::DefId) {
+        if !self.impl_dups.insert(impl_did) {
+            return; // already visited
+        }
+
+        let method = match impl_method(self.tcx(), impl_did, self.method_name) {
+            Some(m) => m,
+            None => { return; } // No method with correct name on this impl
+        };
+
+        if !self.has_applicable_self(&*method) {
+            // No receiver declared. Not a candidate.
+            return self.record_static_candidate(ImplSource(impl_did));
+        }
+
+        let impl_pty = check::impl_self_ty(self.fcx, self.span, impl_did);
+        let impl_substs = impl_pty.substs;
+
+        // Determine the receiver type that the method itself expects.
+        let xform_self_ty =
+            self.xform_self_ty(&method, &impl_substs);
+
+        self.inherent_candidates.push(Candidate {
+            xform_self_ty: xform_self_ty,
+            method_ty: method,
+            kind: InherentImplCandidate(impl_did, impl_substs)
+        });
+    }
+
+    fn assemble_inherent_candidates_from_object(&mut self,
+                                                self_ty: ty::t,
+                                                principal: &ty::TraitRef,
+                                                _bounds: ty::ExistentialBounds) {
+        debug!("assemble_inherent_candidates_from_object(self_ty={})",
+               self_ty.repr(self.tcx()));
+
+        let tcx = self.tcx();
+
+        // It is illegal to invoke a method on a trait instance that
+        // refers to the `Self` type. An error will be reported by
+        // `enforce_object_limitations()` if the method refers to the
+        // `Self` type anywhere other than the receiver. Here, we use
+        // a substitution that replaces `Self` with the object type
+        // itself. Hence, a `&self` method will wind up with an
+        // argument type like `&Trait`.
+        let rcvr_substs = principal.substs.clone().with_self_ty(self_ty);
+        let trait_ref = Rc::new(ty::TraitRef {
+            def_id: principal.def_id,
+            substs: rcvr_substs.clone()
+        });
+
+        self.elaborate_bounds(&[trait_ref.clone()], |this, new_trait_ref, m, method_num| {
+            let vtable_index =
+                get_method_index(tcx, &*new_trait_ref,
+                                 trait_ref.clone(), method_num);
+
+            // FIXME Hacky. By-value `self` methods in objects ought to be
+            // just a special case of passing ownership of a DST value
+            // as a parameter. *But* we currently hack them in and tie them to
+            // the particulars of the `Box` type. So basically for a `fn foo(self,...)`
+            // method invoked on an object, we don't want the receiver type to be
+            // `TheTrait`, but rather `Box<TheTrait>`. Yuck.
+            let mut m = m;
+            match m.explicit_self {
+                ty::ByValueExplicitSelfCategory => {
+                    let mut n = (*m).clone();
+                    let self_ty = n.fty.sig.inputs[0];
+                    n.fty.sig.inputs[0] = ty::mk_uniq(tcx, self_ty);
+                    m = Rc::new(n);
+                }
+                _ => { }
+            }
+
+            let xform_self_ty =
+                this.xform_self_ty(&m, &new_trait_ref.substs);
+
+            this.inherent_candidates.push(Candidate {
+                xform_self_ty: xform_self_ty,
+                method_ty: m,
+                kind: ObjectCandidate(MethodObject {
+                    trait_ref: new_trait_ref,
+                    object_trait_id: principal.def_id,
+                    method_num: method_num,
+                    real_index: vtable_index
+                })
+            });
+        });
+    }
+
+    fn assemble_inherent_candidates_from_param(&mut self,
+                                           _rcvr_ty: ty::t,
+                                           param_ty: ty::ParamTy) {
+        // FIXME -- Do we want to commit to this behavior for param bounds?
+
+        let ty::ParamTy { space, idx: index, .. } = param_ty;
+        let bounds =
+            self.fcx.inh.param_env.bounds.get(space, index).trait_bounds
+            .as_slice();
+        self.elaborate_bounds(bounds, |this, trait_ref, m, method_num| {
+            let xform_self_ty =
+                this.xform_self_ty(&m, &trait_ref.substs);
+
+            debug!("found match: trait_ref={} substs={} m={}",
+                   trait_ref.repr(this.tcx()),
+                   trait_ref.substs.repr(this.tcx()),
+                   m.repr(this.tcx()));
+            assert_eq!(m.generics.types.get_slice(subst::TypeSpace).len(),
+                       trait_ref.substs.types.get_slice(subst::TypeSpace).len());
+            assert_eq!(m.generics.regions.get_slice(subst::TypeSpace).len(),
+                       trait_ref.substs.regions().get_slice(subst::TypeSpace).len());
+            assert_eq!(m.generics.types.get_slice(subst::SelfSpace).len(),
+                       trait_ref.substs.types.get_slice(subst::SelfSpace).len());
+            assert_eq!(m.generics.regions.get_slice(subst::SelfSpace).len(),
+                       trait_ref.substs.regions().get_slice(subst::SelfSpace).len());
+
+            // Because this trait derives from a where-clause, it
+            // should not contain any inference variables or other
+            // artifacts. This means it is safe to put into the
+            // `WhereClauseCandidate` and (eventually) into the
+            // `WhereClausePick`.
+            assert!(trait_ref.substs.types.iter().all(|&t| !ty::type_needs_infer(t)));
+
+            this.inherent_candidates.push(Candidate {
+                xform_self_ty: xform_self_ty,
+                method_ty: m,
+                kind: WhereClauseCandidate(trait_ref, method_num)
+            });
+        });
+    }
+
+    // Do a search through a list of bounds, using a callback to actually
+    // create the candidates.
+    fn elaborate_bounds(
+        &mut self,
+        bounds: &[Rc<ty::TraitRef>],
+        mk_cand: |this: &mut ProbeContext,
+                  tr: Rc<ty::TraitRef>,
+                  m: Rc<ty::Method>,
+                  method_num: uint|)
+    {
+        let tcx = self.tcx();
+        let mut cache = HashSet::new();
+        for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
+            // Already visited this trait, skip it.
+            if !cache.insert(bound_trait_ref.def_id) {
+                continue;
+            }
+
+            let (pos, method) = match trait_method(tcx, bound_trait_ref.def_id, self.method_name) {
+                Some(v) => v,
+                None => { continue; }
+            };
+
+            if !self.has_applicable_self(&*method) {
+                self.record_static_candidate(TraitSource(bound_trait_ref.def_id));
+            } else {
+                mk_cand(self, bound_trait_ref, method, pos);
+            }
+        }
+    }
+
+    fn assemble_extension_candidates_for_traits_in_scope(&mut self,
+                                                         expr_id: ast::NodeId)
+    {
+        let mut duplicates = HashSet::new();
+        let opt_applicable_traits = self.fcx.ccx.trait_map.get(&expr_id);
+        for applicable_traits in opt_applicable_traits.into_iter() {
+            for &trait_did in applicable_traits.iter() {
+                if duplicates.insert(trait_did) {
+                    self.assemble_extension_candidates_for_trait(trait_did);
+                }
+            }
+        }
+    }
+
+    fn assemble_extension_candidates_for_trait(&mut self,
+                                           trait_def_id: ast::DefId) {
+        debug!("assemble_extension_candidates_for_trait: trait_def_id={}",
+               trait_def_id.repr(self.tcx()));
+
+        // Check whether `trait_def_id` defines a method with suitable name:
+        let trait_items =
+            ty::trait_items(self.tcx(), trait_def_id);
+        let matching_index =
+            trait_items.iter()
+                       .position(|item| item.name() == self.method_name);
+        let matching_index = match matching_index {
+            Some(i) => i,
+            None => { return; }
+        };
+        let method = match (&*trait_items)[matching_index].as_opt_method() {
+            Some(m) => m,
+            None => { return; }
+        };
+
+        // Check whether `trait_def_id` defines a method with suitable name:
+        if !self.has_applicable_self(&*method) {
+            debug!("method has inapplicable self");
+            return self.record_static_candidate(TraitSource(trait_def_id));
+        }
+
+        self.assemble_extension_candidates_for_trait_impls(trait_def_id,
+                                                       method.clone(),
+                                                       matching_index);
+
+        self.assemble_unboxed_closure_candidates(trait_def_id,
+                                                 method,
+                                                 matching_index);
+    }
+
+    fn assemble_extension_candidates_for_trait_impls(&mut self,
+                                                 trait_def_id: ast::DefId,
+                                                 method: Rc<ty::Method>,
+                                                 method_index: uint)
+    {
+        ty::populate_implementations_for_trait_if_necessary(self.tcx(),
+                                                            trait_def_id);
+
+        let trait_impls = self.tcx().trait_impls.borrow();
+        let impl_def_ids = match trait_impls.get(&trait_def_id) {
+            None => { return; }
+            Some(impls) => impls,
+        };
+
+        for &impl_def_id in impl_def_ids.borrow().iter() {
+            debug!("assemble_extension_candidates_for_trait_impl: trait_def_id={} impl_def_id={}",
+                   trait_def_id.repr(self.tcx()),
+                   impl_def_id.repr(self.tcx()));
+
+            let impl_pty = check::impl_self_ty(self.fcx, self.span, impl_def_id);
+            let impl_substs = impl_pty.substs;
+
+            debug!("impl_substs={}", impl_substs.repr(self.tcx()));
+
+            let impl_trait_ref =
+                ty::impl_trait_ref(self.tcx(), impl_def_id)
+                .unwrap() // we know this is a trait impl
+                .subst(self.tcx(), &impl_substs);
+
+            debug!("impl_trait_ref={}", impl_trait_ref.repr(self.tcx()));
+
+            // Determine the receiver type that the method itself expects.
+            let xform_self_ty =
+                self.xform_self_ty(&method, &impl_trait_ref.substs);
+
+            debug!("xform_self_ty={}", xform_self_ty.repr(self.tcx()));
+
+            self.extension_candidates.push(Candidate {
+                xform_self_ty: xform_self_ty,
+                method_ty: method.clone(),
+                kind: ExtensionImplCandidate(impl_def_id, impl_trait_ref, impl_substs, method_index)
+            });
+        }
+    }
+
+    fn assemble_unboxed_closure_candidates(&mut self,
+                                           trait_def_id: ast::DefId,
+                                           method_ty: Rc<ty::Method>,
+                                           method_index: uint)
+    {
+        // Check if this is one of the Fn,FnMut,FnOnce traits.
+        let tcx = self.tcx();
+        let kind = if Some(trait_def_id) == tcx.lang_items.fn_trait() {
+            ty::FnUnboxedClosureKind
+        } else if Some(trait_def_id) == tcx.lang_items.fn_mut_trait() {
+            ty::FnMutUnboxedClosureKind
+        } else if Some(trait_def_id) == tcx.lang_items.fn_once_trait() {
+            ty::FnOnceUnboxedClosureKind
+        } else {
+            return;
+        };
+
+        // Check if there is an unboxed-closure self-type in the list of receivers.
+        // If so, add "synthetic impls".
+        let steps = self.steps.clone();
+        for step in steps.iter() {
+            let (closure_def_id, _, _) = match ty::get(step.self_ty).sty {
+                ty::ty_unboxed_closure(a, b, ref c) => (a, b, c),
+                _ => continue,
+            };
+
+            let unboxed_closures = self.fcx.inh.unboxed_closures.borrow();
+            let closure_data = match unboxed_closures.get(&closure_def_id) {
+                Some(data) => data,
+                None => {
+                    self.tcx().sess.span_bug(
+                        self.span,
+                        format!("No entry for unboxed closure: {}",
+                                closure_def_id.repr(self.tcx())).as_slice());
+                }
+            };
+
+            // this closure doesn't implement the right kind of `Fn` trait
+            if closure_data.kind != kind {
+                continue;
+            }
+
+            // create some substitutions for the argument/return type;
+            // for the purposes of our method lookup, we only take
+            // receiver type into account, so we can just substitute
+            // fresh types here to use during substitution and subtyping.
+            let trait_def = ty::lookup_trait_def(self.tcx(), trait_def_id);
+            let substs = self.infcx().fresh_substs_for_trait(self.span,
+                                                             &trait_def.generics,
+                                                             step.self_ty);
+
+            let xform_self_ty = self.xform_self_ty(&method_ty, &substs);
+            self.inherent_candidates.push(Candidate {
+                xform_self_ty: xform_self_ty,
+                method_ty: method_ty.clone(),
+                kind: UnboxedClosureCandidate(trait_def_id, method_index)
+            });
+        }
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // THE ACTUAL SEARCH
+
+    fn pick(mut self) -> PickResult {
+        let steps = self.steps.clone();
+
+        for step in steps.iter() {
+            match self.pick_step(step) {
+                Some(r) => {
+                    return r;
+                }
+                None => { }
+            }
+        }
+
+        Err(NoMatch(self.static_candidates))
+    }
+
+    fn pick_step(&mut self, step: &CandidateStep) -> Option<PickResult> {
+        debug!("pick_step: step={}", step.repr(self.tcx()));
+
+        if ty::type_is_error(step.self_ty) {
+            return None;
+        }
+
+        match self.pick_adjusted_method(step) {
+            Some(result) => return Some(result),
+            None => {}
+        }
+
+        match self.pick_autorefd_method(step) {
+            Some(result) => return Some(result),
+            None => {}
+        }
+
+        // FIXME -- Super hack. For DST types, we will convert to
+        // &&[T] or &&str, as part of a kind of legacy lookup scheme.
+        match ty::get(step.self_ty).sty {
+            ty::ty_str | ty::ty_vec(_, None) => self.pick_autorefrefd_method(step),
+            _ => None
+        }
+    }
+
+    fn pick_adjusted_method(&mut self,
+                            step: &CandidateStep)
+                            -> Option<PickResult>
+    {
+        self.pick_method(step.self_ty).map(|r| self.adjust(r, step.adjustment.clone()))
+    }
+
+    fn pick_autorefd_method(&mut self,
+                            step: &CandidateStep)
+                            -> Option<PickResult>
+    {
+        let tcx = self.tcx();
+        self.search_mutabilities(
+            |m| AutoRef(m, box step.adjustment.clone()),
+            |m,r| ty::mk_rptr(tcx, r, ty::mt {ty:step.self_ty, mutbl:m}))
+    }
+
+    fn pick_autorefrefd_method(&mut self,
+                               step: &CandidateStep)
+                               -> Option<PickResult>
+    {
+        let tcx = self.tcx();
+        self.search_mutabilities(
+            |m| AutoRef(m, box AutoRef(m, box step.adjustment.clone())),
+            |m,r| ty::mk_rptr(tcx, r, ty::mt { ty: ty::mk_rptr(tcx, r, ty::mt { ty:step.self_ty,
+                                                                                mutbl:m}),
+                                               mutbl: m }))
+    }
+
+    fn search_mutabilities(&mut self,
+                           mk_adjustment: |ast::Mutability| -> PickAdjustment,
+                           mk_autoref_ty: |ast::Mutability, ty::Region| -> ty::t)
+                           -> Option<PickResult>
+    {
+        let region = self.infcx().next_region_var(infer::Autoref(self.span));
+
+        // Search through mutabilities in order to find one where pick works:
+        [ast::MutImmutable, ast::MutMutable]
+            .iter()
+            .flat_map(|&m| {
+                let autoref_ty = mk_autoref_ty(m, region);
+                self.pick_method(autoref_ty)
+                    .map(|r| self.adjust(r, mk_adjustment(m)))
+                    .into_iter()
+            })
+            .nth(0)
+    }
+
+    fn adjust(&mut self, result: PickResult, adjustment: PickAdjustment) -> PickResult {
+        match result {
+            Err(e) => Err(e),
+            Ok(mut pick) => {
+                pick.adjustment = adjustment;
+                Ok(pick)
+            }
+        }
+    }
+
+    fn pick_method(&mut self, self_ty: ty::t) -> Option<PickResult> {
+        debug!("pick_method(self_ty={})", self.infcx().ty_to_string(self_ty));
+
+        debug!("searching inherent candidates");
+        match self.consider_candidates(self_ty, self.inherent_candidates[]) {
+            None => {}
+            Some(pick) => {
+                return Some(pick);
+            }
+        }
+
+        debug!("searching extension candidates");
+        self.consider_candidates(self_ty, self.extension_candidates[])
+    }
+
+    fn consider_candidates(&self, self_ty: ty::t, probes: &[Candidate]) -> Option<PickResult> {
+        let mut applicable_candidates: Vec<_> =
+            probes.iter()
+                  .filter(|&probe| self.consider_probe(self_ty, probe))
+                  .collect();
+
+        debug!("applicable_candidates: {}", applicable_candidates.repr(self.tcx()));
+
+        if applicable_candidates.len() > 1 {
+            match self.collapse_candidates_to_trait_pick(applicable_candidates[]) {
+                Some(pick) => { return Some(Ok(pick)); }
+                None => { }
+            }
+        }
+
+        if applicable_candidates.len() > 1 {
+            let sources = probes.iter().map(|p| p.to_source()).collect();
+            return Some(Err(Ambiguity(sources)));
+        }
+
+        applicable_candidates.pop().map(|probe| {
+            let pick = probe.to_unadjusted_pick();
+            Ok(pick)
+        })
+    }
+
+    fn consider_probe(&self, self_ty: ty::t, probe: &Candidate) -> bool {
+        debug!("consider_probe: self_ty={} probe={}",
+               self_ty.repr(self.tcx()),
+               probe.repr(self.tcx()));
+
+        self.infcx().probe(|| {
+            match self.make_sub_ty(self_ty, probe.xform_self_ty) {
+                Ok(()) => { }
+                Err(_) => {
+                    debug!("--> cannot relate self-types");
+                    return false;
+                }
+            }
+
+            match probe.kind {
+                InherentImplCandidate(impl_def_id, ref substs) |
+                ExtensionImplCandidate(impl_def_id, _, ref substs, _) => {
+                    // Check whether the impl imposes obligations we have to worry about.
+                    let obligations =
+                        traits::impl_obligations(
+                            self.tcx(),
+                            traits::ObligationCause::misc(self.span),
+                            impl_def_id,
+                            substs);
+
+                    debug!("impl_obligations={}", obligations.repr(self.tcx()));
+
+                    let mut selcx = traits::SelectionContext::new(self.infcx(),
+                                                                  &self.fcx.inh.param_env,
+                                                                  self.fcx);
+
+                    obligations.all(|o| selcx.evaluate_obligation(o))
+                }
+
+                ObjectCandidate(..) |
+                UnboxedClosureCandidate(..) |
+                WhereClauseCandidate(..) => {
+                    // These have no additional conditions to check.
+                    true
+                }
+            }
+        })
+    }
+
+    fn collapse_candidates_to_trait_pick(&self, probes: &[&Candidate]) -> Option<Pick> {
+        /*!
+         * Sometimes we get in a situation where we have multiple
+         * probes that are all impls of the same trait, but we don't
+         * know which impl to use. In this case, since in all cases
+         * the external interface of the method can be determined from
+         * the trait, it's ok not to decide.  We can basically just
+         * collapse all of the probes for various impls into one
+         * where-clause probe. This will result in a pending
+         * obligation so when more type-info is available we can make
+         * the final decision.
+         *
+         * Example (`src/test/run-pass/method-two-trait-defer-resolution-1.rs`):
+         *
+         * ```
+         * trait Foo { ... }
+         * impl Foo for Vec<int> { ... }
+         * impl Foo for Vec<uint> { ... }
+         * ```
+         *
+         * Now imagine the receiver is `Vec<_>`. It doesn't really
+         * matter at this time which impl we use, so it's ok to just
+         * commit to "using the method from the trait Foo".
+         */
+
+        // Do all probes correspond to the same trait?
+        let trait_data = match probes[0].to_trait_data() {
+            Some(data) => data,
+            None => return None,
+        };
+        if probes[1..].iter().any(|p| p.to_trait_data() != Some(trait_data)) {
+            return None;
+        }
+
+        // If so, just use this trait and call it a day.
+        let (trait_def_id, method_num) = trait_data;
+        let method_ty = probes[0].method_ty.clone();
+        Some(Pick {
+            method_ty: method_ty,
+            adjustment: AutoDeref(0),
+            kind: TraitPick(trait_def_id, method_num)
+        })
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // MISCELLANY
+
+    fn make_sub_ty(&self, sub: ty::t, sup: ty::t) -> infer::ures {
+        self.infcx().sub_types(false, infer::Misc(DUMMY_SP), sub, sup)
+    }
+
+    fn has_applicable_self(&self, method: &ty::Method) -> bool {
+        // "fast track" -- check for usage of sugar
+        match method.explicit_self {
+            ty::StaticExplicitSelfCategory => {
+                // fallthrough
+            }
+            ty::ByValueExplicitSelfCategory |
+            ty::ByReferenceExplicitSelfCategory(..) |
+            ty::ByBoxExplicitSelfCategory => {
+                return true;
+            }
+        }
+
+        // FIXME -- check for types that deref to `Self`,
+        // like `Rc<Self>` and so on.
+        //
+        // Note also that the current code will break if this type
+        // includes any of the type parameters defined on the method
+        // -- but this could be overcome.
+        return false;
+    }
+
+    fn record_static_candidate(&mut self, source: CandidateSource) {
+        self.static_candidates.push(source);
+    }
+
+    fn xform_self_ty(&self, method: &Rc<ty::Method>, substs: &subst::Substs) -> ty::t {
+        debug!("xform_self_ty(self_ty={}, substs={})",
+               method.fty.sig.inputs[0].repr(self.tcx()),
+               substs.repr(self.tcx()));
+
+        let xform_self_ty = method.fty.sig.inputs[0].subst(self.tcx(), substs);
+        self.infcx().replace_late_bound_regions_with_fresh_var(method.fty.sig.binder_id,
+                                                               self.span,
+                                                               infer::FnCall,
+                                                               &xform_self_ty).0
+    }
+}
+
+fn impl_method(tcx: &ty::ctxt,
+               impl_def_id: ast::DefId,
+               method_name: ast::Name)
+               -> Option<Rc<ty::Method>>
+{
+    let impl_items = tcx.impl_items.borrow();
+    let impl_items = impl_items.get(&impl_def_id).unwrap();
+    impl_items
+        .iter()
+        .map(|&did| ty::impl_or_trait_item(tcx, did.def_id()))
+        .find(|m| m.name() == method_name)
+        .and_then(|item| item.as_opt_method())
+}
+
+fn trait_method(tcx: &ty::ctxt,
+                trait_def_id: ast::DefId,
+                method_name: ast::Name)
+                -> Option<(uint, Rc<ty::Method>)>
+{
+    /*!
+     * Find method with name `method_name` defined in `trait_def_id` and return it,
+     * along with its index (or `None`, if no such method).
+     */
+
+    let trait_items = ty::trait_items(tcx, trait_def_id);
+    trait_items
+        .iter()
+        .enumerate()
+        .find(|&(_, ref item)| item.name() == method_name)
+        .and_then(|(idx, item)| item.as_opt_method().map(|m| (idx, m)))
+}
+
+// Determine the index of a method in the list of all methods belonging
+// to a trait and its supertraits.
+fn get_method_index(tcx: &ty::ctxt,
+                    trait_ref: &ty::TraitRef,
+                    subtrait: Rc<ty::TraitRef>,
+                    n_method: uint) -> uint {
+    // We need to figure the "real index" of the method in a
+    // listing of all the methods of an object. We do this by
+    // iterating down the supertraits of the object's trait until
+    // we find the trait the method came from, counting up the
+    // methods from them.
+    let mut method_count = 0;
+    ty::each_bound_trait_and_supertraits(tcx, &[subtrait], |bound_ref| {
+        if bound_ref.def_id == trait_ref.def_id {
+            false
+        } else {
+            let trait_items = ty::trait_items(tcx, bound_ref.def_id);
+            for trait_item in trait_items.iter() {
+                match *trait_item {
+                    ty::MethodTraitItem(_) => method_count += 1,
+                    ty::TypeTraitItem(_) => {}
+                }
+            }
+            true
+        }
+    });
+    method_count + n_method
+}
+
+impl Candidate {
+    fn to_unadjusted_pick(&self) -> Pick {
+        Pick {
+            method_ty: self.method_ty.clone(),
+            adjustment: AutoDeref(0),
+            kind: match self.kind {
+                InherentImplCandidate(def_id, _) => {
+                    InherentImplPick(def_id)
+                }
+                ObjectCandidate(ref data) => {
+                    ObjectPick(data.trait_ref.def_id, data.method_num, data.real_index)
+                }
+                ExtensionImplCandidate(def_id, _, _, index) => {
+                    ExtensionImplPick(def_id, index)
+                }
+                UnboxedClosureCandidate(trait_def_id, index) => {
+                    TraitPick(trait_def_id, index)
+                }
+                WhereClauseCandidate(ref trait_ref, index) => {
+                    // Only trait derived from where-clauses should
+                    // appear here, so they should not contain any
+                    // inference variables or other artifacts. This
+                    // means they are safe to put into the
+                    // `WhereClausePick`.
+                    assert!(trait_ref.substs.types.iter().all(|&t| !ty::type_needs_infer(t)));
+
+                    WhereClausePick((*trait_ref).clone(), index)
+                }
+            }
+        }
+    }
+
+    fn to_source(&self) -> CandidateSource {
+        match self.kind {
+            InherentImplCandidate(def_id, _) => ImplSource(def_id),
+            ObjectCandidate(ref obj) => TraitSource(obj.trait_ref.def_id),
+            ExtensionImplCandidate(def_id, _, _, _) => ImplSource(def_id),
+            UnboxedClosureCandidate(trait_def_id, _) => TraitSource(trait_def_id),
+            WhereClauseCandidate(ref trait_ref, _) => TraitSource(trait_ref.def_id),
+        }
+    }
+
+    fn to_trait_data(&self) -> Option<(ast::DefId,MethodIndex)> {
+        match self.kind {
+            InherentImplCandidate(..) |
+            ObjectCandidate(..) => {
+                None
+            }
+            UnboxedClosureCandidate(trait_def_id, method_num) => {
+                Some((trait_def_id, method_num))
+            }
+            ExtensionImplCandidate(_, ref trait_ref, _, method_num) |
+            WhereClauseCandidate(ref trait_ref, method_num) => {
+                Some((trait_ref.def_id, method_num))
+            }
+        }
+    }
+}
+
+impl Repr for Candidate {
+    fn repr(&self, tcx: &ty::ctxt) -> String {
+        format!("Candidate(xform_self_ty={}, kind={})",
+                self.xform_self_ty.repr(tcx),
+                self.kind.repr(tcx))
+    }
+}
+
+impl Repr for CandidateKind {
+    fn repr(&self, tcx: &ty::ctxt) -> String {
+        match *self {
+            InherentImplCandidate(ref a, ref b) =>
+                format!("InherentImplCandidate({},{})", a.repr(tcx), b.repr(tcx)),
+            ObjectCandidate(ref a) =>
+                format!("ObjectCandidate({})", a.repr(tcx)),
+            ExtensionImplCandidate(ref a, ref b, ref c, ref d) =>
+                format!("ExtensionImplCandidate({},{},{},{})", a.repr(tcx), b.repr(tcx),
+                        c.repr(tcx), d),
+            UnboxedClosureCandidate(ref a, ref b) =>
+                format!("UnboxedClosureCandidate({},{})", a.repr(tcx), b),
+            WhereClauseCandidate(ref a, ref b) =>
+                format!("WhereClauseCandidate({},{})", a.repr(tcx), b),
+        }
+    }
+}
+
+impl Repr for CandidateStep {
+    fn repr(&self, tcx: &ty::ctxt) -> String {
+        format!("CandidateStep({},{})",
+                self.self_ty.repr(tcx),
+                self.adjustment)
+    }
+}
+
+impl Repr for PickAdjustment {
+    fn repr(&self, _tcx: &ty::ctxt) -> String {
+        format!("{}", self)
+    }
+}
+
+impl Repr for PickKind {
+    fn repr(&self, _tcx: &ty::ctxt) -> String {
+        format!("{}", self)
+    }
+}
+
+impl Repr for Pick {
+    fn repr(&self, tcx: &ty::ctxt) -> String {
+        format!("Pick(method_ty={}, adjustment={}, kind={})",
+                self.method_ty.repr(tcx),
+                self.adjustment,
+                self.kind)
+    }
+}
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 17c9676a98b..d58b0322433 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -102,8 +102,6 @@ use middle::typeck::astconv::AstConv;
 use middle::typeck::astconv::{ast_region_to_region, ast_ty_to_ty};
 use middle::typeck::astconv;
 use middle::typeck::check::_match::pat_ctxt;
-use middle::typeck::check::method::{AutoderefReceiver};
-use middle::typeck::check::method::{CheckTraitsAndInherentMethods};
 use middle::typeck::check::regionmanip::replace_late_bound_regions;
 use middle::typeck::CrateCtxt;
 use middle::typeck::infer;
@@ -2271,6 +2269,10 @@ fn autoderef_for_index<T>(fcx: &FnCtxt,
                           step: |ty::t, ty::AutoDerefRef| -> Option<T>)
                           -> Option<T>
 {
+    // FIXME(#18741) -- this is almost but not quite the same as the
+    // autoderef that normal method probing does. They could likely be
+    // consolidated.
+
     let (ty, autoderefs, final_mt) =
         autoderef(fcx, base_expr.span, base_ty, Some(base_expr.id), lvalue_pref, |adj_ty, idx| {
             let autoderefref = ty::AutoDerefRef { autoderefs: idx, autoref: None };
@@ -3048,9 +3050,12 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
 
         // Replace any bound regions that appear in the function
         // signature with region variables
-        let (_, fn_sig) = replace_late_bound_regions(fcx.tcx(), fn_sig.binder_id, fn_sig, |br| {
-            fcx.infcx().next_region_var(infer::LateBoundRegion(call_expr.span, br))
-        });
+        let fn_sig =
+            fcx.infcx().replace_late_bound_regions_with_fresh_var(
+                fn_sig.binder_id,
+                call_expr.span,
+                infer::FnCall,
+                fn_sig).0;
 
         // Call the generic checker.
         check_argument_types(fcx,
@@ -3082,14 +3087,12 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
 
         let tps = tps.iter().map(|ast_ty| fcx.to_ty(&**ast_ty)).collect::<Vec<_>>();
         let fn_ty = match method::lookup(fcx,
-                                         expr,
-                                         &*rcvr,
+                                         method_name.span,
                                          method_name.node.name,
                                          expr_t,
-                                         tps.as_slice(),
-                                         DontDerefArgs,
-                                         CheckTraitsAndInherentMethods,
-                                         AutoderefReceiver) {
+                                         tps,
+                                         expr.id,
+                                         rcvr) {
             Ok(method) => {
                 let method_ty = method.ty;
                 let method_call = MethodCall::expr(expr.id);
@@ -3597,8 +3600,7 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
                    expr: &ast::Expr,
                    lvalue_pref: LvaluePreference,
                    base: &ast::Expr,
-                   field: &ast::SpannedIdent,
-                   tys: &[P<ast::Ty>]) {
+                   field: &ast::SpannedIdent) {
         let tcx = fcx.ccx.tcx;
         check_expr_with_lvalue_pref(fcx, base, lvalue_pref);
         let expr_t = structurally_resolved_type(fcx, expr.span,
@@ -3625,42 +3627,29 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
             None => {}
         }
 
-        let tps: Vec<ty::t> = tys.iter().map(|ty| fcx.to_ty(&**ty)).collect();
-        match method::lookup(fcx,
-                             expr,
-                             base,
-                             field.node.name,
-                             expr_t,
-                             tps.as_slice(),
-                             DontDerefArgs,
-                             CheckTraitsAndInherentMethods,
-                             AutoderefReceiver) {
-            Ok(_) => {
-                fcx.type_error_message(
-                    field.span,
-                    |actual| {
-                        format!("attempted to take value of method `{}` on type \
-                                 `{}`", token::get_ident(field.node), actual)
-                    },
-                    expr_t, None);
-
-                tcx.sess.span_help(field.span,
-                    "maybe a `()` to call it is missing? \
-                     If not, try an anonymous function");
-            }
+        if method::exists(fcx, field.span, field.node.name, expr_t, expr.id) {
+            fcx.type_error_message(
+                field.span,
+                |actual| {
+                    format!("attempted to take value of method `{}` on type \
+                            `{}`", token::get_ident(field.node), actual)
+                },
+                expr_t, None);
 
-            Err(_) => {
-                fcx.type_error_message(
-                    expr.span,
-                    |actual| {
-                        format!("attempted access of field `{}` on \
-                                        type `{}`, but no field with that \
-                                        name was found",
-                                       token::get_ident(field.node),
-                                       actual)
-                    },
-                    expr_t, None);
-            }
+            tcx.sess.span_help(field.span,
+                               "maybe a `()` to call it is missing? \
+                               If not, try an anonymous function");
+        } else {
+            fcx.type_error_message(
+                expr.span,
+                |actual| {
+                    format!("attempted access of field `{}` on \
+                            type `{}`, but no field with that \
+                            name was found",
+                            token::get_ident(field.node),
+                            actual)
+                },
+                expr_t, None);
         }
 
         fcx.write_error(expr.id);
@@ -3671,8 +3660,7 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
                        expr: &ast::Expr,
                        lvalue_pref: LvaluePreference,
                        base: &ast::Expr,
-                       idx: codemap::Spanned<uint>,
-                       _tys: &[P<ast::Ty>]) {
+                       idx: codemap::Spanned<uint>) {
         let tcx = fcx.ccx.tcx;
         check_expr_with_lvalue_pref(fcx, base, lvalue_pref);
         let expr_t = structurally_resolved_type(fcx, expr.span,
@@ -4495,11 +4483,11 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
 
         fcx.require_expr_have_sized_type(expr, traits::StructInitializerSized);
       }
-      ast::ExprField(ref base, ref field, ref tys) => {
-        check_field(fcx, expr, lvalue_pref, &**base, field, tys.as_slice());
+      ast::ExprField(ref base, ref field, _) => {
+        check_field(fcx, expr, lvalue_pref, &**base, field);
       }
-      ast::ExprTupField(ref base, idx, ref tys) => {
-        check_tup_field(fcx, expr, lvalue_pref, &**base, idx, tys.as_slice());
+      ast::ExprTupField(ref base, idx, _) => {
+        check_tup_field(fcx, expr, lvalue_pref, &**base, idx);
       }
       ast::ExprIndex(ref base, ref idx) => {
           check_expr_with_lvalue_pref(fcx, &**base, lvalue_pref);
diff --git a/src/librustc/middle/typeck/infer/error_reporting.rs b/src/librustc/middle/typeck/infer/error_reporting.rs
index 77ee389c760..8c55872d962 100644
--- a/src/librustc/middle/typeck/infer/error_reporting.rs
+++ b/src/librustc/middle/typeck/infer/error_reporting.rs
@@ -1456,11 +1456,11 @@ impl<'a, 'tcx> ErrorReportingHelpers for InferCtxt<'a, 'tcx> {
             infer::AddrOfSlice(_) => " for slice expression".to_string(),
             infer::Autoref(_) => " for autoref".to_string(),
             infer::Coercion(_) => " for automatic coercion".to_string(),
-            infer::LateBoundRegion(_, br) => {
+            infer::LateBoundRegion(_, br, infer::FnCall) => {
                 format!(" for {}in function call",
                         bound_region_to_string(self.tcx, "lifetime parameter ", true, br))
             }
-            infer::BoundRegionInFnType(_, br) => {
+            infer::LateBoundRegion(_, br, infer::FnType) => {
                 format!(" for {}in function type",
                         bound_region_to_string(self.tcx, "lifetime parameter ", true, br))
             }
diff --git a/src/librustc/middle/typeck/infer/glb.rs b/src/librustc/middle/typeck/infer/glb.rs
index 7ed5a5db161..12b81010e98 100644
--- a/src/librustc/middle/typeck/infer/glb.rs
+++ b/src/librustc/middle/typeck/infer/glb.rs
@@ -15,12 +15,13 @@ use middle::ty;
 use middle::typeck::infer::combine::*;
 use middle::typeck::infer::lattice::*;
 use middle::typeck::infer::equate::Equate;
+use middle::typeck::infer::FnType;
+use middle::typeck::infer::fold_regions_in_sig;
 use middle::typeck::infer::lub::Lub;
+use middle::typeck::infer::region_inference::RegionMark;
 use middle::typeck::infer::sub::Sub;
 use middle::typeck::infer::{cres, InferCtxt};
 use middle::typeck::infer::{TypeTrace, Subtype};
-use middle::typeck::infer::fold_regions_in_sig;
-use middle::typeck::infer::region_inference::RegionMark;
 use syntax::ast::{Many, Once, MutImmutable, MutMutable};
 use syntax::ast::{NormalFn, UnsafeFn, NodeId};
 use syntax::ast::{Onceness, FnStyle};
@@ -140,12 +141,12 @@ impl<'f, 'tcx> Combine<'tcx> for Glb<'f, 'tcx> {
 
         // Instantiate each bound region with a fresh region variable.
         let (a_with_fresh, a_map) =
-            self.fields.infcx.replace_late_bound_regions_with_fresh_regions(
-                self.trace(), a);
+            self.fields.infcx.replace_late_bound_regions_with_fresh_var(
+                a.binder_id, self.trace().span(), FnType, a);
         let a_vars = var_ids(self, &a_map);
         let (b_with_fresh, b_map) =
-            self.fields.infcx.replace_late_bound_regions_with_fresh_regions(
-                self.trace(), b);
+            self.fields.infcx.replace_late_bound_regions_with_fresh_var(
+                b.binder_id, self.trace().span(), FnType, b);
         let b_vars = var_ids(self, &b_map);
 
         // Collect constraints.
diff --git a/src/librustc/middle/typeck/infer/lub.rs b/src/librustc/middle/typeck/infer/lub.rs
index 59778340564..bd0e88b5812 100644
--- a/src/librustc/middle/typeck/infer/lub.rs
+++ b/src/librustc/middle/typeck/infer/lub.rs
@@ -13,6 +13,7 @@ use middle::ty::RegionVid;
 use middle::ty;
 use middle::typeck::infer::combine::*;
 use middle::typeck::infer::equate::Equate;
+use middle::typeck::infer::FnType;
 use middle::typeck::infer::glb::Glb;
 use middle::typeck::infer::lattice::*;
 use middle::typeck::infer::sub::Sub;
@@ -126,11 +127,11 @@ impl<'f, 'tcx> Combine<'tcx> for Lub<'f, 'tcx> {
 
         // Instantiate each bound region with a fresh region variable.
         let (a_with_fresh, a_map) =
-            self.fields.infcx.replace_late_bound_regions_with_fresh_regions(
-                self.trace(), a);
+            self.fields.infcx.replace_late_bound_regions_with_fresh_var(
+                a.binder_id, self.trace().span(), FnType, a);
         let (b_with_fresh, _) =
-            self.fields.infcx.replace_late_bound_regions_with_fresh_regions(
-                self.trace(), b);
+            self.fields.infcx.replace_late_bound_regions_with_fresh_var(
+                b.binder_id, self.trace().span(), FnType, b);
 
         // Collect constraints.
         let sig0 = try!(super_fn_sigs(self, &a_with_fresh, &b_with_fresh));
diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs
index 1a64af1270f..ab7c8b7640e 100644
--- a/src/librustc/middle/typeck/infer/mod.rs
+++ b/src/librustc/middle/typeck/infer/mod.rs
@@ -41,7 +41,7 @@ use syntax::codemap;
 use syntax::codemap::Span;
 use util::common::indent;
 use util::nodemap::FnvHashMap;
-use util::ppaux::{bound_region_to_string, ty_to_string};
+use util::ppaux::{ty_to_string};
 use util::ppaux::{trait_ref_to_string, Repr};
 
 use self::coercion::Coerce;
@@ -227,6 +227,16 @@ pub enum SubregionOrigin {
     AutoBorrow(Span),
 }
 
+/// Times when we replace late-bound regions with variables:
+#[deriving(Clone, Show)]
+pub enum LateBoundRegionConversionTime {
+    /// when a fn is called
+    FnCall,
+
+    /// when two fn types are compared
+    FnType,
+}
+
 /// Reasons to create a region inference variable
 ///
 /// See `error_reporting.rs` for more details
@@ -256,11 +266,7 @@ pub enum RegionVariableOrigin {
 
     // Region variables created for bound regions
     // in a function or method that is called
-    LateBoundRegion(Span, ty::BoundRegion),
-
-    // Region variables created for bound regions
-    // when doing subtyping/lub/glb computations
-    BoundRegionInFnType(Span, ty::BoundRegion),
+    LateBoundRegion(Span, ty::BoundRegion, LateBoundRegionConversionTime),
 
     UpvarRegion(ty::UpvarId, Span),
 
@@ -959,22 +965,21 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         self.report_and_explain_type_error(trace, err);
     }
 
-    pub fn replace_late_bound_regions_with_fresh_regions(&self,
-                                                         trace: TypeTrace,
-                                                         fsig: &ty::FnSig)
-                                                    -> (ty::FnSig,
-                                                        FnvHashMap<ty::BoundRegion,
-                                                                ty::Region>) {
-        let (map, fn_sig) =
-            replace_late_bound_regions(self.tcx, fsig.binder_id, fsig, |br| {
-                let rvar = self.next_region_var(
-                    BoundRegionInFnType(trace.origin.span(), br));
-                debug!("Bound region {} maps to {}",
-                       bound_region_to_string(self.tcx, "", false, br),
-                       rvar);
-                rvar
-            });
-        (fn_sig, map)
+    pub fn replace_late_bound_regions_with_fresh_var<T>(&self,
+                                                        binder_id: ast::NodeId,
+                                                        span: Span,
+                                                        lbrct: LateBoundRegionConversionTime,
+                                                        value: &T)
+                                                        -> (T, FnvHashMap<ty::BoundRegion,ty::Region>)
+                                                        where T : TypeFoldable + Repr
+    {
+        let (map, value) =
+            replace_late_bound_regions(
+                self.tcx,
+                binder_id,
+                value,
+                |br| self.next_region_var(LateBoundRegion(span, br, lbrct)));
+        (value, map)
     }
 }
 
@@ -1156,8 +1161,7 @@ impl RegionVariableOrigin {
             Autoref(a) => a,
             Coercion(ref a) => a.span(),
             EarlyBoundRegion(a, _) => a,
-            LateBoundRegion(a, _) => a,
-            BoundRegionInFnType(a, _) => a,
+            LateBoundRegion(a, _, _) => a,
             BoundRegionInCoherence(_) => codemap::DUMMY_SP,
             UpvarRegion(_, a) => a
         }
@@ -1182,12 +1186,8 @@ impl Repr for RegionVariableOrigin {
             EarlyBoundRegion(a, b) => {
                 format!("EarlyBoundRegion({},{})", a.repr(tcx), b.repr(tcx))
             }
-            LateBoundRegion(a, b) => {
-                format!("LateBoundRegion({},{})", a.repr(tcx), b.repr(tcx))
-            }
-            BoundRegionInFnType(a, b) => {
-                format!("bound_regionInFnType({},{})", a.repr(tcx),
-                b.repr(tcx))
+            LateBoundRegion(a, b, c) => {
+                format!("LateBoundRegion({},{},{})", a.repr(tcx), b.repr(tcx), c)
             }
             BoundRegionInCoherence(a) => {
                 format!("bound_regionInCoherence({})", a.repr(tcx))
diff --git a/src/librustc/middle/typeck/infer/sub.rs b/src/librustc/middle/typeck/infer/sub.rs
index d2f315f2a4b..6f9000f5537 100644
--- a/src/librustc/middle/typeck/infer/sub.rs
+++ b/src/librustc/middle/typeck/infer/sub.rs
@@ -16,6 +16,7 @@ use middle::typeck::check::regionmanip::replace_late_bound_regions;
 use middle::typeck::infer::combine::*;
 use middle::typeck::infer::{cres, CresCompare};
 use middle::typeck::infer::equate::Equate;
+use middle::typeck::infer::FnType;
 use middle::typeck::infer::glb::Glb;
 use middle::typeck::infer::InferCtxt;
 use middle::typeck::infer::lub::Lub;
@@ -175,8 +176,8 @@ impl<'f, 'tcx> Combine<'tcx> for Sub<'f, 'tcx> {
         // First, we instantiate each bound region in the subtype with a fresh
         // region variable.
         let (a_sig, _) =
-            self.fields.infcx.replace_late_bound_regions_with_fresh_regions(
-                self.trace(), a);
+            self.fields.infcx.replace_late_bound_regions_with_fresh_var(
+                a.binder_id, self.trace().span(), FnType, a);
 
         // Second, we instantiate each bound region in the supertype with a
         // fresh concrete region.
diff --git a/src/libsyntax/ast_map/mod.rs b/src/libsyntax/ast_map/mod.rs
index 2a2ad9fd664..b116c84552e 100644
--- a/src/libsyntax/ast_map/mod.rs
+++ b/src/libsyntax/ast_map/mod.rs
@@ -544,7 +544,7 @@ impl<'ast> Map<'ast> {
 
     pub fn def_id_span(&self, def_id: DefId, fallback: Span) -> Span {
         if def_id.krate == LOCAL_CRATE {
-            self.span(def_id.node)
+            self.opt_span(def_id.node).unwrap_or(fallback)
         } else {
             fallback
         }
diff --git a/src/test/compile-fail/issue-16683.rs b/src/test/compile-fail/issue-16683.rs
index d9dfaac5720..fcbf8a3d351 100644
--- a/src/test/compile-fail/issue-16683.rs
+++ b/src/test/compile-fail/issue-16683.rs
@@ -11,7 +11,7 @@
 trait T<'a> {
     fn a(&'a self) -> &'a bool;
     fn b(&self) {
-        self.a(); //~ ERROR mismatched types: expected `&'a Self`, found `&Self` (lifetime mismatch)
+        self.a(); //~ ERROR cannot infer
     }
 }
 
diff --git a/src/test/compile-fail/issue-17758.rs b/src/test/compile-fail/issue-17758.rs
index bb480e5e4dd..a47f5c16a46 100644
--- a/src/test/compile-fail/issue-17758.rs
+++ b/src/test/compile-fail/issue-17758.rs
@@ -15,7 +15,7 @@ trait Foo<'a> {
     fn foo(&'a self);
     fn bar(&self) {
         self.foo();
-        //~^ ERROR mismatched types: expected `&'a Self`, found `&Self` (lifetime mismatch)
+        //~^ ERROR cannot infer
     }
 }
 
diff --git a/src/test/compile-fail/method-ambig-one-trait-coerce.rs b/src/test/compile-fail/method-ambig-one-trait-coerce.rs
index e5c3da10df8..5e3206ea516 100644
--- a/src/test/compile-fail/method-ambig-one-trait-coerce.rs
+++ b/src/test/compile-fail/method-ambig-one-trait-coerce.rs
@@ -27,8 +27,14 @@ impl foo for Box<Object+Send> {
 }
 
 fn test1(x: Box<Object+Send+Sync>) {
-    // Ambiguous because we could coerce to either impl:
-    x.foo(); //~ ERROR E0034
+    // FIXME(#18737) -- we ought to consider this to be ambiguous,
+    // since we could coerce to either impl. However, what actually
+    // happens is that we consider both impls applicable because of
+    // incorrect subtyping relation. We then decide to call this a
+    // call to the `foo` trait, leading to the following error
+    // message.
+
+    x.foo(); //~ ERROR `foo` is not implemented
 }
 
 fn test2(x: Box<Object+Send>) {
diff --git a/src/test/compile-fail/method-commit-to-trait.rs b/src/test/compile-fail/method-commit-to-trait.rs
deleted file mode 100644
index 6e4b5e088c9..00000000000
--- a/src/test/compile-fail/method-commit-to-trait.rs
+++ /dev/null
@@ -1,33 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-// Test that we pick `Foo`, and also pick the `impl`, even though in
-// this case the vector type `T` is not copyable. This is because
-// there is no other reasonable choice. The error you see is thus
-// about `T` being non-copyable, not about `Foo` being
-// unimplemented. This is better for user too, since it suggests minimal
-// diff requird to fix program.
-
-trait Object { }
-
-trait Foo {
-    fn foo(self) -> int;
-}
-
-impl<T:Copy> Foo for Vec<T> {
-    fn foo(self) -> int {1}
-}
-
-fn test1<T>(x: Vec<T>) {
-    x.foo();
-    //~^ ERROR `core::kinds::Copy` is not implemented for the type `T`
-}
-
-fn main() { }
diff --git a/src/test/compile-fail/unboxed-closures-type-mismatch.rs b/src/test/compile-fail/unboxed-closures-type-mismatch.rs
index 09f13b77386..c60a99ca0df 100644
--- a/src/test/compile-fail/unboxed-closures-type-mismatch.rs
+++ b/src/test/compile-fail/unboxed-closures-type-mismatch.rs
@@ -14,6 +14,6 @@ use std::ops::FnMut;
 
 pub fn main() {
     let mut f = |&mut: x: int, y: int| -> int { x + y };
-    let z = f.call_mut((1u, 2));    //~ ERROR mismatched types
+    let z = f.call_mut((1u, 2));    //~ ERROR not implemented
     println!("{}", z);
 }
diff --git a/src/test/run-pass/method-recursive-blanket-impl.rs b/src/test/run-pass/method-recursive-blanket-impl.rs
new file mode 100644
index 00000000000..b45faca2de6
--- /dev/null
+++ b/src/test/run-pass/method-recursive-blanket-impl.rs
@@ -0,0 +1,46 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that we don't trigger on the blanket impl for all `&'a T` but
+// rather keep autoderefing and trigger on the underlying impl.  To
+// know not to stop at the blanket, we have to recursively evaluate
+// the `T:Foo` bound.
+
+use std::kinds::Sized;
+
+// Note: this must be generic for the problem to show up
+trait Foo<A> for Sized? {
+    fn foo(&self);
+}
+
+impl Foo<u8> for [u8] {
+    fn foo(&self) {}
+}
+
+impl<'a, A, T> Foo<A> for &'a T where T: Foo<A> {
+    fn foo(&self) {
+        Foo::foo(*self)
+    }
+}
+
+trait Bar {
+    fn foo(&self);
+}
+
+struct MyType;
+
+impl Bar for MyType {
+    fn foo(&self) {}
+}
+
+fn main() {
+    let mut m = MyType;
+    (&mut m).foo()
+}
diff --git a/src/test/run-pass/method-two-traits-distinguished-via-where-clause.rs b/src/test/run-pass/method-two-traits-distinguished-via-where-clause.rs
new file mode 100644
index 00000000000..986236fb6f9
--- /dev/null
+++ b/src/test/run-pass/method-two-traits-distinguished-via-where-clause.rs
@@ -0,0 +1,34 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that we select between traits A and B. To do that, we must
+// consider the `Sized` bound.
+
+trait A {
+    fn foo(self);
+}
+
+trait B {
+    fn foo(self);
+}
+
+impl<T: Sized> A for *const T {
+    fn foo(self) {}
+}
+
+impl<T> B for *const [T] {
+    fn foo(self) {}
+}
+
+fn main() {
+    let x: [int, ..4] = [1,2,3,4];
+    let xptr = x.as_slice() as *const _;
+    xptr.foo();
+}