Rollup merge of #33852 - arielb1:autoderef-iterator, r=eddyb

refactor autoderef to avoid prematurely registering obligations

Refactor `FnCtxt::autoderef` to use an external iterator and to not
register any obligation from the main autoderef loop, but rather to
register them after (and if) the loop successfully completes.

Fixes #24819
Fixes #25801
Fixes #27631
Fixes #31258
Fixes #31964
Fixes #32320
Fixes #33515
Fixes #33755

r? @eddyb

18 files changed, 515 insertions, 472 deletions

diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index 41982ddc78b..7c9c52baa63 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -163,6 +163,11 @@ pub struct InferCtxt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     // If the number of errors increases, that's also a sign (line
     // `tained_by_errors`) to avoid reporting certain kinds of errors.
     err_count_on_creation: usize,
+
+    // This flag is used for debugging, and is set to true if there are
+    // any obligations set during the current snapshot. In that case, the
+    // snapshot can't be rolled back.
+    pub obligations_in_snapshot: Cell<bool>,
 }
 
 /// A map returned by `skolemize_late_bound_regions()` indicating the skolemized
@@ -476,7 +481,8 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'gcx> {
             normalize: false,
             projection_mode: ProjectionMode::AnyFinal,
             tainted_by_errors_flag: Cell::new(false),
-            err_count_on_creation: self.sess.err_count()
+            err_count_on_creation: self.sess.err_count(),
+            obligations_in_snapshot: Cell::new(false),
         }
     }
 }
@@ -515,7 +521,8 @@ impl<'a, 'gcx, 'tcx> InferCtxtBuilder<'a, 'gcx, 'tcx> {
             normalize: normalize,
             projection_mode: projection_mode,
             tainted_by_errors_flag: Cell::new(false),
-            err_count_on_creation: tcx.sess.err_count()
+            err_count_on_creation: tcx.sess.err_count(),
+            obligations_in_snapshot: Cell::new(false),
         }))
     }
 }
@@ -542,6 +549,7 @@ pub struct CombinedSnapshot {
     int_snapshot: unify::Snapshot<ty::IntVid>,
     float_snapshot: unify::Snapshot<ty::FloatVid>,
     region_vars_snapshot: RegionSnapshot,
+    obligations_in_snapshot: bool,
 }
 
 /// Helper trait for shortening the lifetimes inside a
@@ -809,11 +817,15 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     }
 
     fn start_snapshot(&self) -> CombinedSnapshot {
+        let obligations_in_snapshot = self.obligations_in_snapshot.get();
+        self.obligations_in_snapshot.set(false);
+
         CombinedSnapshot {
             type_snapshot: self.type_variables.borrow_mut().snapshot(),
             int_snapshot: self.int_unification_table.borrow_mut().snapshot(),
             float_snapshot: self.float_unification_table.borrow_mut().snapshot(),
             region_vars_snapshot: self.region_vars.start_snapshot(),
+            obligations_in_snapshot: obligations_in_snapshot,
         }
     }
 
@@ -822,7 +834,11 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         let CombinedSnapshot { type_snapshot,
                                int_snapshot,
                                float_snapshot,
-                               region_vars_snapshot } = snapshot;
+                               region_vars_snapshot,
+                               obligations_in_snapshot } = snapshot;
+
+        assert!(!self.obligations_in_snapshot.get());
+        self.obligations_in_snapshot.set(obligations_in_snapshot);
 
         self.type_variables
             .borrow_mut()
@@ -842,7 +858,10 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         let CombinedSnapshot { type_snapshot,
                                int_snapshot,
                                float_snapshot,
-                               region_vars_snapshot } = snapshot;
+                               region_vars_snapshot,
+                               obligations_in_snapshot } = snapshot;
+
+        self.obligations_in_snapshot.set(obligations_in_snapshot);
 
         self.type_variables
             .borrow_mut()
@@ -904,12 +923,16 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         let CombinedSnapshot { type_snapshot,
                                int_snapshot,
                                float_snapshot,
-                               region_vars_snapshot } = self.start_snapshot();
+                               region_vars_snapshot,
+                               obligations_in_snapshot } = self.start_snapshot();
 
         let r = self.commit_if_ok(|_| f());
 
         debug!("commit_regions_if_ok: rolling back everything but regions");
 
+        assert!(!self.obligations_in_snapshot.get());
+        self.obligations_in_snapshot.set(obligations_in_snapshot);
+
         // Roll back any non-region bindings - they should be resolved
         // inside `f`, with, e.g. `resolve_type_vars_if_possible`.
         self.type_variables
diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index d9d0367bdcb..0d7d7afd120 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -171,6 +171,8 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
         // debug output much nicer to read and so on.
         let obligation = infcx.resolve_type_vars_if_possible(&obligation);
 
+        infcx.obligations_in_snapshot.set(true);
+
         if infcx.tcx.fulfilled_predicates.borrow().check_duplicate(&obligation.predicate)
         {
             return
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index c5db2a8a780..c177ec4dbed 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -31,7 +31,7 @@ pub use self::coherence::overlapping_impls;
 pub use self::coherence::OrphanCheckErr;
 pub use self::fulfill::{FulfillmentContext, GlobalFulfilledPredicates, RegionObligation};
 pub use self::project::{MismatchedProjectionTypes, ProjectionMode};
-pub use self::project::{normalize, Normalized};
+pub use self::project::{normalize, normalize_projection_type, Normalized};
 pub use self::object_safety::ObjectSafetyViolation;
 pub use self::object_safety::MethodViolationCode;
 pub use self::select::{EvaluationCache, SelectionContext, SelectionCache};
diff --git a/src/librustc/traits/specialize/mod.rs b/src/librustc/traits/specialize/mod.rs
index b2d14dab9a0..c7a36375576 100644
--- a/src/librustc/traits/specialize/mod.rs
+++ b/src/librustc/traits/specialize/mod.rs
@@ -187,51 +187,49 @@ fn fulfill_implication<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
                                        source_trait_ref: ty::TraitRef<'tcx>,
                                        target_impl: DefId)
                                        -> Result<&'tcx Substs<'tcx>, ()> {
-    infcx.commit_if_ok(|_| {
-        let selcx = &mut SelectionContext::new(&infcx);
-        let target_substs = fresh_type_vars_for_impl(&infcx, DUMMY_SP, target_impl);
-        let (target_trait_ref, obligations) = impl_trait_ref_and_oblig(selcx,
-                                                                       target_impl,
-                                                                       &target_substs);
-
-        // do the impls unify? If not, no specialization.
-        if let Err(_) = infcx.eq_trait_refs(true,
-                                            TypeOrigin::Misc(DUMMY_SP),
-                                            source_trait_ref,
-                                            target_trait_ref) {
-            debug!("fulfill_implication: {:?} does not unify with {:?}",
-                   source_trait_ref,
-                   target_trait_ref);
-            return Err(());
-        }
+    let selcx = &mut SelectionContext::new(&infcx);
+    let target_substs = fresh_type_vars_for_impl(&infcx, DUMMY_SP, target_impl);
+    let (target_trait_ref, obligations) = impl_trait_ref_and_oblig(selcx,
+                                                                   target_impl,
+                                                                   &target_substs);
+
+    // do the impls unify? If not, no specialization.
+    if let Err(_) = infcx.eq_trait_refs(true,
+                                        TypeOrigin::Misc(DUMMY_SP),
+                                        source_trait_ref,
+                                        target_trait_ref) {
+        debug!("fulfill_implication: {:?} does not unify with {:?}",
+               source_trait_ref,
+               target_trait_ref);
+        return Err(());
+    }
 
-        // attempt to prove all of the predicates for impl2 given those for impl1
-        // (which are packed up in penv)
+    // attempt to prove all of the predicates for impl2 given those for impl1
+    // (which are packed up in penv)
 
-        let mut fulfill_cx = FulfillmentContext::new();
-        for oblig in obligations.into_iter() {
-            fulfill_cx.register_predicate_obligation(&infcx, oblig);
-        }
+    let mut fulfill_cx = FulfillmentContext::new();
+    for oblig in obligations.into_iter() {
+        fulfill_cx.register_predicate_obligation(&infcx, oblig);
+    }
 
-        if let Err(errors) = infcx.drain_fulfillment_cx(&mut fulfill_cx, &()) {
-            // no dice!
-            debug!("fulfill_implication: for impls on {:?} and {:?}, could not fulfill: {:?} given \
-                    {:?}",
-                   source_trait_ref,
-                   target_trait_ref,
-                   errors,
-                   infcx.parameter_environment.caller_bounds);
-            Err(())
-        } else {
-            debug!("fulfill_implication: an impl for {:?} specializes {:?}",
-                   source_trait_ref,
-                   target_trait_ref);
-
-            // Now resolve the *substitution* we built for the target earlier, replacing
-            // the inference variables inside with whatever we got from fulfillment.
-            Ok(infcx.resolve_type_vars_if_possible(&target_substs))
-        }
-    })
+    if let Err(errors) = infcx.drain_fulfillment_cx(&mut fulfill_cx, &()) {
+        // no dice!
+        debug!("fulfill_implication: for impls on {:?} and {:?}, could not fulfill: {:?} given \
+                {:?}",
+               source_trait_ref,
+               target_trait_ref,
+               errors,
+               infcx.parameter_environment.caller_bounds);
+        Err(())
+    } else {
+        debug!("fulfill_implication: an impl for {:?} specializes {:?}",
+               source_trait_ref,
+               target_trait_ref);
+
+        // Now resolve the *substitution* we built for the target earlier, replacing
+        // the inference variables inside with whatever we got from fulfillment.
+        Ok(infcx.resolve_type_vars_if_possible(&target_substs))
+    }
 }
 
 pub struct SpecializesCache {
diff --git a/src/librustc/ty/adjustment.rs b/src/librustc/ty/adjustment.rs
index 71e49031347..60f2ca6f4d9 100644
--- a/src/librustc/ty/adjustment.rs
+++ b/src/librustc/ty/adjustment.rs
@@ -235,8 +235,9 @@ impl<'a, 'gcx, 'tcx> ty::TyS<'tcx> {
             None => {
                 span_bug!(
                     expr_span,
-                    "the {}th autoderef failed: {}",
+                    "the {}th autoderef for {} failed: {}",
                     autoderef,
+                    expr_id,
                     adjusted_ty);
             }
         }
diff --git a/src/librustc_typeck/check/autoderef.rs b/src/librustc_typeck/check/autoderef.rs
new file mode 100644
index 00000000000..9e2b7cd0346
--- /dev/null
+++ b/src/librustc_typeck/check/autoderef.rs
@@ -0,0 +1,210 @@
+// Copyright 2016 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 astconv::AstConv;
+
+use super::FnCtxt;
+
+use rustc::traits;
+use rustc::ty::{self, Ty, TraitRef};
+use rustc::ty::{ToPredicate, TypeFoldable};
+use rustc::ty::{MethodCall, MethodCallee};
+use rustc::ty::subst::Substs;
+use rustc::ty::{LvaluePreference, NoPreference, PreferMutLvalue};
+use rustc::hir;
+
+use syntax::codemap::Span;
+use syntax::parse::token;
+
+#[derive(Copy, Clone, Debug)]
+enum AutoderefKind {
+    Builtin,
+    Overloaded
+}
+
+pub struct Autoderef<'a, 'gcx: 'tcx, 'tcx: 'a> {
+    fcx: &'a FnCtxt<'a, 'gcx, 'tcx>,
+    steps: Vec<(Ty<'tcx>, AutoderefKind)>,
+    cur_ty: Ty<'tcx>,
+    obligations: Vec<traits::PredicateObligation<'tcx>>,
+    at_start: bool,
+    span: Span
+}
+
+impl<'a, 'gcx, 'tcx> Iterator for Autoderef<'a, 'gcx, 'tcx> {
+    type Item = (Ty<'tcx>, usize);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let tcx = self.fcx.tcx;
+
+        debug!("autoderef: steps={:?}, cur_ty={:?}",
+               self.steps, self.cur_ty);
+        if self.at_start {
+            self.at_start = false;
+            debug!("autoderef stage #0 is {:?}", self.cur_ty);
+            return Some((self.cur_ty, 0));
+        }
+
+        if self.steps.len() == tcx.sess.recursion_limit.get() {
+            // We've reached the recursion limit, error gracefully.
+            span_err!(tcx.sess, self.span, E0055,
+                      "reached the recursion limit while auto-dereferencing {:?}",
+                      self.cur_ty);
+            return None;
+        }
+
+        if self.cur_ty.is_ty_var() {
+            return None;
+        }
+
+        // Otherwise, deref if type is derefable:
+        let (kind, new_ty) = if let Some(mt) = self.cur_ty.builtin_deref(false, NoPreference) {
+            (AutoderefKind::Builtin, mt.ty)
+        } else {
+            match self.overloaded_deref_ty(self.cur_ty) {
+                Some(ty) => (AutoderefKind::Overloaded, ty),
+                _ => return None
+            }
+        };
+
+        if new_ty.references_error() {
+            return None;
+        }
+
+        self.steps.push((self.cur_ty, kind));
+        debug!("autoderef stage #{:?} is {:?} from {:?}", self.steps.len(),
+               new_ty, (self.cur_ty, kind));
+        self.cur_ty = new_ty;
+
+        Some((self.cur_ty, self.steps.len()))
+    }
+}
+
+impl<'a, 'gcx, 'tcx> Autoderef<'a, 'gcx, 'tcx> {
+    fn overloaded_deref_ty(&mut self, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
+        debug!("overloaded_deref_ty({:?})", ty);
+
+        let tcx = self.fcx.tcx();
+
+        // <cur_ty as Deref>
+        let trait_ref = TraitRef {
+            def_id: match tcx.lang_items.deref_trait() {
+                Some(f) => f,
+                None => return None
+            },
+            substs: tcx.mk_substs(Substs::new_trait(vec![], vec![], self.cur_ty))
+        };
+
+        let cause = traits::ObligationCause::misc(self.span, self.fcx.body_id);
+
+        let mut selcx = traits::SelectionContext::new(self.fcx);
+        let obligation = traits::Obligation::new(cause.clone(), trait_ref.to_predicate());
+        if !selcx.evaluate_obligation(&obligation) {
+            debug!("overloaded_deref_ty: cannot match obligation");
+            return None;
+        }
+
+        let normalized = traits::normalize_projection_type(
+            &mut selcx,
+            ty::ProjectionTy {
+                trait_ref: trait_ref,
+                item_name: token::intern("Target")
+            },
+            cause,
+            0
+        );
+
+        debug!("overloaded_deref_ty({:?}) = {:?}", ty, normalized);
+        self.obligations.extend(normalized.obligations);
+
+        Some(self.fcx.resolve_type_vars_if_possible(&normalized.value))
+    }
+
+    pub fn unambiguous_final_ty(&self) -> Ty<'tcx> {
+        self.fcx.structurally_resolved_type(self.span, self.cur_ty)
+    }
+
+    pub fn finalize<'b, I>(self, pref: LvaluePreference, exprs: I)
+        where I: IntoIterator<Item=&'b hir::Expr>
+    {
+        let methods : Vec<_> = self.steps.iter().map(|&(ty, kind)| {
+            if let AutoderefKind::Overloaded = kind {
+                self.fcx.try_overloaded_deref(self.span, None, ty, pref)
+            } else {
+                None
+            }
+        }).collect();
+
+        debug!("finalize({:?}) - {:?},{:?}", pref, methods, self.obligations);
+
+        for expr in exprs {
+            debug!("finalize - finalizing #{} - {:?}", expr.id, expr);
+            for (n, method) in methods.iter().enumerate() {
+                if let &Some(method) = method {
+                    let method_call = MethodCall::autoderef(expr.id, n as u32);
+                    self.fcx.tables.borrow_mut().method_map.insert(method_call, method);
+                }
+            }
+        }
+
+        for obligation in self.obligations {
+            self.fcx.register_predicate(obligation);
+        }
+    }
+}
+
+impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
+    pub fn autoderef(&'a self,
+                     span: Span,
+                     base_ty: Ty<'tcx>)
+                     -> Autoderef<'a, 'gcx, 'tcx>
+    {
+        Autoderef {
+            fcx: self,
+            steps: vec![],
+            cur_ty: self.resolve_type_vars_if_possible(&base_ty),
+            obligations: vec![],
+            at_start: true,
+            span: span
+        }
+    }
+
+    pub fn try_overloaded_deref(&self,
+                                span: Span,
+                                base_expr: Option<&hir::Expr>,
+                                base_ty: Ty<'tcx>,
+                                lvalue_pref: LvaluePreference)
+                                -> Option<MethodCallee<'tcx>>
+    {
+        debug!("try_overloaded_deref({:?},{:?},{:?},{:?})",
+               span, base_expr, base_ty, lvalue_pref);
+        // Try DerefMut first, if preferred.
+        let method = match (lvalue_pref, self.tcx.lang_items.deref_mut_trait()) {
+            (PreferMutLvalue, Some(trait_did)) => {
+                self.lookup_method_in_trait(span, base_expr,
+                                            token::intern("deref_mut"), trait_did,
+                                            base_ty, None)
+            }
+            _ => None
+        };
+
+        // Otherwise, fall back to Deref.
+        let method = match (method, self.tcx.lang_items.deref_trait()) {
+            (None, Some(trait_did)) => {
+                self.lookup_method_in_trait(span, base_expr,
+                                            token::intern("deref"), trait_did,
+                                            base_ty, None)
+            }
+            (method, _) => method
+        };
+
+        method
+    }
+}
diff --git a/src/librustc_typeck/check/callee.rs b/src/librustc_typeck/check/callee.rs
index 7493ca70f55..417b2fafecf 100644
--- a/src/librustc_typeck/check/callee.rs
+++ b/src/librustc_typeck/check/callee.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use super::{DeferredCallResolution, Expectation, FnCtxt,
-            TupleArgumentsFlag, UnresolvedTypeAction};
+            TupleArgumentsFlag};
 
 use CrateCtxt;
 use middle::cstore::LOCAL_CRATE;
@@ -72,15 +72,13 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
     {
         self.check_expr(callee_expr);
         let original_callee_ty = self.expr_ty(callee_expr);
-        let (callee_ty, _, result) =
-            self.autoderef(callee_expr.span,
-                           original_callee_ty,
-                           || Some(callee_expr),
-                           UnresolvedTypeAction::Error,
-                           LvaluePreference::NoPreference,
-                           |adj_ty, idx| {
-                self.try_overloaded_call_step(call_expr, callee_expr, adj_ty, idx)
-        });
+
+        let mut autoderef = self.autoderef(callee_expr.span, original_callee_ty);
+        let result = autoderef.by_ref().flat_map(|(adj_ty, idx)| {
+            self.try_overloaded_call_step(call_expr, callee_expr, adj_ty, idx)
+        }).next();
+        let callee_ty = autoderef.unambiguous_final_ty();
+        autoderef.finalize(LvaluePreference::NoPreference, Some(callee_expr));
 
         match result {
             None => {
diff --git a/src/librustc_typeck/check/coercion.rs b/src/librustc_typeck/check/coercion.rs
index 4861ab15e2c..9dd737f3a61 100644
--- a/src/librustc_typeck/check/coercion.rs
+++ b/src/librustc_typeck/check/coercion.rs
@@ -60,7 +60,7 @@
 //! sort of a minor point so I've opted to leave it for later---after all
 //! we may want to adjust precisely when coercions occur.
 
-use check::{FnCtxt, UnresolvedTypeAction};
+use check::{FnCtxt};
 
 use rustc::hir;
 use rustc::infer::{Coercion, InferOk, TypeOrigin, TypeTrace};
@@ -220,7 +220,8 @@ impl<'f, 'gcx, 'tcx> Coerce<'f, 'gcx, 'tcx> {
                                          -> CoerceResult<'tcx>
         // FIXME(eddyb) use copyable iterators when that becomes ergonomic.
         where E: Fn() -> I,
-              I: IntoIterator<Item=&'a hir::Expr> {
+              I: IntoIterator<Item=&'a hir::Expr>
+    {
 
         debug!("coerce_borrowed_pointer(a={:?}, b={:?})", a, b);
 
@@ -240,18 +241,16 @@ impl<'f, 'gcx, 'tcx> Coerce<'f, 'gcx, 'tcx> {
 
         let span = self.origin.span();
 
-        let lvalue_pref = LvaluePreference::from_mutbl(mt_b.mutbl);
         let mut first_error = None;
         let mut r_borrow_var = None;
-        let (_, autoderefs, success) = self.autoderef(span, a, exprs,
-                                                      UnresolvedTypeAction::Ignore,
-                                                      lvalue_pref,
-                                                      |referent_ty, autoderef|
-        {
-            if autoderef == 0 {
+        let mut autoderef = self.autoderef(span, a);
+        let mut success = None;
+
+        for (referent_ty, autoderefs) in autoderef.by_ref() {
+            if autoderefs == 0 {
                 // Don't let this pass, otherwise it would cause
                 // &T to autoref to &&T.
-                return None;
+                continue
             }
 
             // At this point, we have deref'd `a` to `referent_ty`.  So
@@ -326,7 +325,7 @@ impl<'f, 'gcx, 'tcx> Coerce<'f, 'gcx, 'tcx> {
             //     and let regionck figure it out.
             let r = if !self.use_lub {
                 r_b // [2] above
-            } else if autoderef == 1 {
+            } else if autoderefs == 1 {
                 r_a // [3] above
             } else {
                 if r_borrow_var.is_none() { // create var lazilly, at most once
@@ -341,23 +340,22 @@ impl<'f, 'gcx, 'tcx> Coerce<'f, 'gcx, 'tcx> {
                 mutbl: mt_b.mutbl // [1] above
             });
             match self.unify(derefd_ty_a, b) {
-                Ok(ty) => Some(ty),
+                Ok(ty) => { success = Some((ty, autoderefs)); break },
                 Err(err) => {
                     if first_error.is_none() {
                         first_error = Some(err);
                     }
-                    None
                 }
             }
-        });
+        }
 
         // Extract type or return an error. We return the first error
         // we got, which should be from relating the "base" type
         // (e.g., in example above, the failure from relating `Vec<T>`
         // to the target type), since that should be the least
         // confusing.
-        let ty = match success {
-            Some(ty) => ty,
+        let (ty, autoderefs) = match success {
+            Some(d) => d,
             None => {
                 let err = first_error.expect("coerce_borrowed_pointer had no error");
                 debug!("coerce_borrowed_pointer: failed with err = {:?}", err);
@@ -365,6 +363,10 @@ impl<'f, 'gcx, 'tcx> Coerce<'f, 'gcx, 'tcx> {
             }
         };
 
+        // This commits the obligations to the fulfillcx. After this succeeds,
+        // this snapshot can't be rolled back.
+        autoderef.finalize(LvaluePreference::from_mutbl(mt_b.mutbl), exprs());
+
         // Now apply the autoref. We have to extract the region out of
         // the final ref type we got.
         if ty == a && mt_a.mutbl == hir::MutImmutable && autoderefs == 1 {
diff --git a/src/librustc_typeck/check/compare_method.rs b/src/librustc_typeck/check/compare_method.rs
index a1a6a83d34f..20f82271b9c 100644
--- a/src/librustc_typeck/check/compare_method.rs
+++ b/src/librustc_typeck/check/compare_method.rs
@@ -279,78 +279,63 @@ pub fn compare_impl_method<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
         // type.
 
         // Compute skolemized form of impl and trait method tys.
-        let impl_fty = tcx.mk_fn_ptr(impl_m.fty);
-        let impl_fty = impl_fty.subst(tcx, impl_to_skol_substs);
-        let trait_fty = tcx.mk_fn_ptr(trait_m.fty);
-        let trait_fty = trait_fty.subst(tcx, &trait_to_skol_substs);
-
-        let err = infcx.commit_if_ok(|snapshot| {
-            let tcx = infcx.tcx;
-            let origin = TypeOrigin::MethodCompatCheck(impl_m_span);
-
-            let (impl_sig, _) =
-                infcx.replace_late_bound_regions_with_fresh_var(impl_m_span,
-                                                                infer::HigherRankedType,
-                                                                &impl_m.fty.sig);
-            let impl_sig =
-                impl_sig.subst(tcx, impl_to_skol_substs);
-            let impl_sig =
-                assoc::normalize_associated_types_in(&infcx,
-                                                     &mut fulfillment_cx,
-                                                     impl_m_span,
-                                                     impl_m_body_id,
-                                                     &impl_sig);
-            let impl_fty = tcx.mk_fn_ptr(tcx.mk_bare_fn(ty::BareFnTy {
-                unsafety: impl_m.fty.unsafety,
-                abi: impl_m.fty.abi,
-                sig: ty::Binder(impl_sig)
-            }));
-            debug!("compare_impl_method: impl_fty={:?}",
-                   impl_fty);
-
-            let (trait_sig, skol_map) =
-                infcx.skolemize_late_bound_regions(&trait_m.fty.sig, snapshot);
-            let trait_sig =
-                trait_sig.subst(tcx, &trait_to_skol_substs);
-            let trait_sig =
-                assoc::normalize_associated_types_in(&infcx,
-                                                     &mut fulfillment_cx,
-                                                     impl_m_span,
-                                                     impl_m_body_id,
-                                                     &trait_sig);
-            let trait_fty = tcx.mk_fn_ptr(tcx.mk_bare_fn(ty::BareFnTy {
-                unsafety: trait_m.fty.unsafety,
-                abi: trait_m.fty.abi,
-                sig: ty::Binder(trait_sig)
-            }));
-
-            debug!("compare_impl_method: trait_fty={:?}",
+        let tcx = infcx.tcx;
+        let origin = TypeOrigin::MethodCompatCheck(impl_m_span);
+
+        let (impl_sig, _) =
+            infcx.replace_late_bound_regions_with_fresh_var(impl_m_span,
+                                                            infer::HigherRankedType,
+                                                            &impl_m.fty.sig);
+        let impl_sig =
+            impl_sig.subst(tcx, impl_to_skol_substs);
+        let impl_sig =
+            assoc::normalize_associated_types_in(&infcx,
+                                                 &mut fulfillment_cx,
+                                                 impl_m_span,
+                                                 impl_m_body_id,
+                                                 &impl_sig);
+        let impl_fty = tcx.mk_fn_ptr(tcx.mk_bare_fn(ty::BareFnTy {
+            unsafety: impl_m.fty.unsafety,
+            abi: impl_m.fty.abi,
+            sig: ty::Binder(impl_sig)
+        }));
+        debug!("compare_impl_method: impl_fty={:?}", impl_fty);
+
+        let trait_sig = tcx.liberate_late_bound_regions(
+            infcx.parameter_environment.free_id_outlive,
+            &trait_m.fty.sig);
+        let trait_sig =
+            trait_sig.subst(tcx, &trait_to_skol_substs);
+        let trait_sig =
+            assoc::normalize_associated_types_in(&infcx,
+                                                 &mut fulfillment_cx,
+                                                 impl_m_span,
+                                                 impl_m_body_id,
+                                                 &trait_sig);
+        let trait_fty = tcx.mk_fn_ptr(tcx.mk_bare_fn(ty::BareFnTy {
+            unsafety: trait_m.fty.unsafety,
+            abi: trait_m.fty.abi,
+            sig: ty::Binder(trait_sig)
+        }));
+
+        debug!("compare_impl_method: trait_fty={:?}", trait_fty);
+
+        if let Err(terr) = infcx.sub_types(false, origin, impl_fty, trait_fty) {
+            debug!("sub_types failed: impl ty {:?}, trait ty {:?}",
+                   impl_fty,
                    trait_fty);
-
-            infcx.sub_types(false, origin, impl_fty, trait_fty)?;
-
-            infcx.leak_check(false, &skol_map, snapshot)
-        });
-
-        match err {
-            Ok(()) => { }
-            Err(terr) => {
-                debug!("checking trait method for compatibility: impl ty {:?}, trait ty {:?}",
-                       impl_fty,
-                       trait_fty);
-                span_err!(tcx.sess, impl_m_span, E0053,
-                          "method `{}` has an incompatible type for trait: {}",
-                          trait_m.name,
-                          terr);
-                return;
-            }
+            span_err!(tcx.sess, impl_m_span, E0053,
+                      "method `{}` has an incompatible type for trait: {}",
+                      trait_m.name,
+                      terr);
+            return
         }
 
         // Check that all obligations are satisfied by the implementation's
         // version.
-        match fulfillment_cx.select_all_or_error(&infcx) {
-            Err(ref errors) => { infcx.report_fulfillment_errors(errors) }
-            Ok(_) => {}
+        if let Err(ref errors) = fulfillment_cx.select_all_or_error(&infcx) {
+            infcx.report_fulfillment_errors(errors);
+            return
         }
 
         // Finally, resolve all regions. This catches wily misuses of
diff --git a/src/librustc_typeck/check/method/confirm.rs b/src/librustc_typeck/check/method/confirm.rs
index 6faf6f415c2..683a67ff07c 100644
--- a/src/librustc_typeck/check/method/confirm.rs
+++ b/src/librustc_typeck/check/method/confirm.rs
@@ -11,11 +11,10 @@
 use super::probe;
 
 use check::{FnCtxt, callee};
-use check::UnresolvedTypeAction;
 use hir::def_id::DefId;
 use rustc::ty::subst::{self};
 use rustc::traits;
-use rustc::ty::{self, NoPreference, PreferMutLvalue, Ty};
+use rustc::ty::{self, LvaluePreference, NoPreference, PreferMutLvalue, Ty};
 use rustc::ty::adjustment::{AdjustDerefRef, AutoDerefRef, AutoPtr};
 use rustc::ty::fold::TypeFoldable;
 use rustc::infer::{self, InferOk, TypeOrigin};
@@ -133,10 +132,10 @@ impl<'a, 'gcx, 'tcx> ConfirmContext<'a, 'gcx, 'tcx> {
             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 overloaded derefs and so on).
-        self.fixup_derefs_on_method_receiver_if_necessary(&callee);
+
+        if let Some(hir::MutMutable) = pick.autoref {
+            self.convert_lvalue_derefs_to_mutable();
+        }
 
         callee
     }
@@ -164,22 +163,14 @@ impl<'a, 'gcx, 'tcx> ConfirmContext<'a, 'gcx, 'tcx> {
             (None, None)
         };
 
-        // Commit the autoderefs by calling `autoderef again, but this
+        // Commit the autoderefs by calling `autoderef` again, but this
         // time writing the results into the various tables.
-        let (autoderefd_ty, n, result) = self.autoderef(self.span,
-                                                        unadjusted_self_ty,
-                                                        || Some(self.self_expr),
-                                                        UnresolvedTypeAction::Error,
-                                                        NoPreference,
-                                                        |_, n| {
-            if n == pick.autoderefs {
-                Some(())
-            } else {
-                None
-            }
-        });
+        let mut autoderef = self.autoderef(self.span, unadjusted_self_ty);
+        let (autoderefd_ty, n) = autoderef.nth(pick.autoderefs).unwrap();
         assert_eq!(n, pick.autoderefs);
-        assert_eq!(result, Some(()));
+
+        autoderef.unambiguous_final_ty();
+        autoderef.finalize(LvaluePreference::NoPreference, Some(self.self_expr));
 
         // Write out the final adjustment.
         self.write_adjustment(self.self_expr.id, AdjustDerefRef(AutoDerefRef {
@@ -293,27 +284,21 @@ impl<'a, 'gcx, 'tcx> ConfirmContext<'a, 'gcx, 'tcx> {
         // yield an object-type (e.g., `&Object` or `Box<Object>`
         // etc).
 
-        let (_, _, result) = self.fcx.autoderef(self.span,
-                                                self_ty,
-                                                || None,
-                                                UnresolvedTypeAction::Error,
-                                                NoPreference,
-                                                |ty, _| {
-            match ty.sty {
-                ty::TyTrait(ref data) => Some(closure(self, ty, &data)),
-                _ => None,
-            }
-        });
-
-        match result {
-            Some(r) => r,
-            None => {
+        // FIXME: this feels, like, super dubious
+        self.fcx.autoderef(self.span, self_ty)
+            .filter_map(|(ty, _)| {
+                match ty.sty {
+                    ty::TyTrait(ref data) => Some(closure(self, ty, &data)),
+                    _ => None,
+                }
+            })
+            .next()
+            .unwrap_or_else(|| {
                 span_bug!(
                     self.span,
                     "self-type `{}` for ObjectPick never dereferenced to an object",
                     self_ty)
-            }
-        }
+            })
     }
 
     fn instantiate_method_substs(&mut self,
@@ -463,24 +448,10 @@ impl<'a, 'gcx, 'tcx> ConfirmContext<'a, 'gcx, 'tcx> {
     ///////////////////////////////////////////////////////////////////////////
     // RECONCILIATION
 
-    /// When we select a method with an `&mut self` receiver, we have to go convert any
+    /// When we select a method with a mutable autoref, we have to go convert any
     /// auto-derefs, indices, etc from `Deref` and `Index` into `DerefMut` and `IndexMut`
     /// respectively.
-    fn fixup_derefs_on_method_receiver_if_necessary(&self,
-                                                    method_callee: &ty::MethodCallee) {
-        let sig = match method_callee.ty.sty {
-            ty::TyFnDef(_, _, ref f) => f.sig.clone(),
-            _ => return,
-        };
-
-        match sig.0.inputs[0].sty {
-            ty::TyRef(_, ty::TypeAndMut {
-                ty: _,
-                mutbl: hir::MutMutable,
-            }) => {}
-            _ => return,
-        }
-
+    fn convert_lvalue_derefs_to_mutable(&self) {
         // Gather up expressions we want to munge.
         let mut exprs = Vec::new();
         exprs.push(self.self_expr);
@@ -495,8 +466,7 @@ impl<'a, 'gcx, 'tcx> ConfirmContext<'a, 'gcx, 'tcx> {
             }
         }
 
-        debug!("fixup_derefs_on_method_receiver_if_necessary: exprs={:?}",
-               exprs);
+        debug!("convert_lvalue_derefs_to_mutable: exprs={:?}", exprs);
 
         // Fix up autoderefs and derefs.
         for (i, &expr) in exprs.iter().rev().enumerate() {
@@ -509,23 +479,17 @@ impl<'a, 'gcx, 'tcx> ConfirmContext<'a, 'gcx, 'tcx> {
                 Some(_) | None => 0,
             };
 
-            debug!("fixup_derefs_on_method_receiver_if_necessary: i={} expr={:?} \
-                                                                  autoderef_count={}",
+            debug!("convert_lvalue_derefs_to_mutable: i={} expr={:?} \
+                                                      autoderef_count={}",
                    i, expr, autoderef_count);
 
             if autoderef_count > 0 {
-                self.autoderef(expr.span,
-                               self.expr_ty(expr),
-                               || Some(expr),
-                               UnresolvedTypeAction::Error,
-                               PreferMutLvalue,
-                               |_, autoderefs| {
-                    if autoderefs == autoderef_count + 1 {
-                        Some(())
-                    } else {
-                        None
-                    }
+                let mut autoderef = self.autoderef(expr.span, self.expr_ty(expr));
+                autoderef.nth(autoderef_count).unwrap_or_else(|| {
+                    span_bug!(expr.span, "expr was deref-able {} times but now isn't?",
+                              autoderef_count);
                 });
+                autoderef.finalize(PreferMutLvalue, Some(expr));
             }
 
             // Don't retry the first one or we might infinite loop!
diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs
index 08c04122517..0bb078dfbcb 100644
--- a/src/librustc_typeck/check/method/probe.rs
+++ b/src/librustc_typeck/check/method/probe.rs
@@ -13,13 +13,13 @@ use super::NoMatchData;
 use super::{CandidateSource, ImplSource, TraitSource};
 use super::suggest;
 
-use check::{FnCtxt, UnresolvedTypeAction};
+use check::{FnCtxt};
 use hir::def_id::DefId;
 use hir::def::Def;
 use rustc::ty::subst;
 use rustc::ty::subst::Subst;
 use rustc::traits;
-use rustc::ty::{self, NoPreference, Ty, ToPolyTraitRef, TraitRef, TypeFoldable};
+use rustc::ty::{self, Ty, ToPolyTraitRef, TraitRef, TypeFoldable};
 use rustc::infer::{InferOk, TypeOrigin};
 use syntax::ast;
 use syntax::codemap::{Span, DUMMY_SP};
@@ -208,25 +208,22 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
     fn create_steps(&self,
                     span: Span,
                     self_ty: Ty<'tcx>)
-                    -> Option<Vec<CandidateStep<'tcx>>> {
-        let mut steps = Vec::new();
-
-        let (final_ty, dereferences, _) = self.autoderef(span,
-                                                         self_ty,
-                                                         || None,
-                                                         UnresolvedTypeAction::Error,
-                                                         NoPreference,
-                                                         |t, d| {
-            steps.push(CandidateStep {
-                self_ty: t,
-                autoderefs: d,
-                unsize: false
-            });
-            None::<()> // keep iterating until we can't anymore
-        });
+                    -> Option<Vec<CandidateStep<'tcx>>>
+    {
+        // FIXME: we don't need to create the entire steps in one pass
 
+        let mut autoderef = self.autoderef(span, self_ty);
+        let mut steps: Vec<_> = autoderef.by_ref().map(|(ty, d)| CandidateStep {
+            self_ty: ty,
+            autoderefs: d,
+            unsize: false
+        }).collect();
+
+        let final_ty = autoderef.unambiguous_final_ty();
         match final_ty.sty {
             ty::TyArray(elem_ty, _) => {
+                let dereferences = steps.len() - 1;
+
                 steps.push(CandidateStep {
                     self_ty: self.tcx.mk_slice(elem_ty),
                     autoderefs: dereferences,
@@ -237,6 +234,8 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
             _ => (),
         }
 
+        debug!("create_steps: steps={:?}", steps);
+
         Some(steps)
     }
 }
diff --git a/src/librustc_typeck/check/method/suggest.rs b/src/librustc_typeck/check/method/suggest.rs
index 2cd60d20251..6f0d2bc0ca5 100644
--- a/src/librustc_typeck/check/method/suggest.rs
+++ b/src/librustc_typeck/check/method/suggest.rs
@@ -13,7 +13,7 @@
 
 use CrateCtxt;
 
-use check::{self, FnCtxt, UnresolvedTypeAction};
+use check::{FnCtxt};
 use rustc::hir::map as hir_map;
 use rustc::ty::{self, Ty, ToPolyTraitRef, ToPredicate, TypeFoldable};
 use middle::cstore;
@@ -21,7 +21,6 @@ use hir::def::Def;
 use hir::def_id::DefId;
 use middle::lang_items::FnOnceTraitLangItem;
 use rustc::ty::subst::Substs;
-use rustc::ty::LvaluePreference;
 use rustc::traits::{Obligation, SelectionContext};
 use util::nodemap::{FnvHashSet};
 
@@ -48,42 +47,28 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
             ty::TyClosure(..) | ty::TyFnDef(..) | ty::TyFnPtr(_) => true,
             // If it's not a simple function, look for things which implement FnOnce
             _ => {
-                if let Ok(fn_once_trait_did) =
-                        tcx.lang_items.require(FnOnceTraitLangItem) {
-                    let (_, _, opt_is_fn) = self.autoderef(span,
-                                                           ty,
-                                                           || None,
-                                                           UnresolvedTypeAction::Ignore,
-                                                           LvaluePreference::NoPreference,
-                                                           |ty, _| {
-                        self.probe(|_| {
-                            let fn_once_substs =
-                                Substs::new_trait(vec![self.next_ty_var()], vec![], ty);
-                            let trait_ref =
-                                ty::TraitRef::new(fn_once_trait_did,
-                                                  tcx.mk_substs(fn_once_substs));
-                            let poly_trait_ref = trait_ref.to_poly_trait_ref();
-                            let obligation = Obligation::misc(span,
-                                                              self.body_id,
-                                                              poly_trait_ref
-                                                                 .to_predicate());
-                            let mut selcx = SelectionContext::new(self);
-
-                            if selcx.evaluate_obligation(&obligation) {
-                                Some(())
-                            } else {
-                                None
-                            }
-                        })
-                    });
+                let fn_once = match tcx.lang_items.require(FnOnceTraitLangItem) {
+                    Ok(fn_once) => fn_once,
+                    Err(..) => return false
+                };
 
-                    opt_is_fn.is_some()
-                } else {
-                    false
-                }
+                self.autoderef(span, ty).any(|(ty, _)| self.probe(|_| {
+                    let fn_once_substs =
+                        Substs::new_trait(vec![self.next_ty_var()], vec![], ty);
+                    let trait_ref =
+                        ty::TraitRef::new(fn_once,
+                                          tcx.mk_substs(fn_once_substs));
+                    let poly_trait_ref = trait_ref.to_poly_trait_ref();
+                    let obligation = Obligation::misc(span,
+                                                      self.body_id,
+                                                      poly_trait_ref
+                                                      .to_predicate());
+                    SelectionContext::new(self).evaluate_obligation(&obligation)
+                }))
             }
         }
     }
+
     pub fn report_method_error(&self,
                                span: Span,
                                rcvr_ty: Ty<'tcx>,
@@ -384,15 +369,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
             return is_local(self.resolve_type_vars_with_obligations(rcvr_ty));
         }
 
-        self.autoderef(span, rcvr_ty, || None,
-                       check::UnresolvedTypeAction::Ignore, ty::NoPreference,
-                       |ty, _| {
-            if is_local(ty) {
-                Some(())
-            } else {
-                None
-            }
-        }).2.is_some()
+        self.autoderef(span, rcvr_ty).any(|(ty, _)| is_local(ty))
     }
 }
 
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 264003bb62b..5dd00cf3666 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -129,6 +129,7 @@ use rustc_back::slice;
 use rustc_const_eval::eval_repeat_count;
 
 mod assoc;
+mod autoderef;
 pub mod dropck;
 pub mod _match;
 pub mod writeback;
@@ -1412,17 +1413,6 @@ impl<'a, 'gcx, 'tcx> RegionScope for FnCtxt<'a, 'gcx, 'tcx> {
     }
 }
 
-/// Whether `autoderef` requires types to resolve.
-#[derive(Copy, Clone, Debug, PartialEq, Eq)]
-pub enum UnresolvedTypeAction {
-    /// Produce an error and return `TyError` whenever a type cannot
-    /// be resolved (i.e. it is `TyInfer`).
-    Error,
-    /// Go on without emitting any errors, and return the unresolved
-    /// type. Useful for probing, e.g. in coercions.
-    Ignore
-}
-
 /// Controls whether the arguments are tupled. This is used for the call
 /// operator.
 ///
@@ -2228,120 +2218,6 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         }
     }
 
-    /// Executes an autoderef loop for the type `t`. At each step, invokes `should_stop`
-    /// to decide whether to terminate the loop. Returns the final type and number of
-    /// derefs that it performed.
-    ///
-    /// Note: this method does not modify the adjustments table. The caller is responsible for
-    /// inserting an AutoAdjustment record into the `self` using one of the suitable methods.
-    pub fn autoderef<'b, E, I, T, F>(&self,
-                                     sp: Span,
-                                     base_ty: Ty<'tcx>,
-                                     maybe_exprs: E,
-                                     unresolved_type_action: UnresolvedTypeAction,
-                                     mut lvalue_pref: LvaluePreference,
-                                     mut should_stop: F)
-                                     -> (Ty<'tcx>, usize, Option<T>)
-        // FIXME(eddyb) use copyable iterators when that becomes ergonomic.
-        where E: Fn() -> I,
-              I: IntoIterator<Item=&'b hir::Expr>,
-              F: FnMut(Ty<'tcx>, usize) -> Option<T>,
-    {
-        debug!("autoderef(base_ty={:?}, lvalue_pref={:?})",
-               base_ty, lvalue_pref);
-
-        let mut t = base_ty;
-        for autoderefs in 0..self.tcx.sess.recursion_limit.get() {
-            let resolved_t = match unresolved_type_action {
-                UnresolvedTypeAction::Error => {
-                    self.structurally_resolved_type(sp, t)
-                }
-                UnresolvedTypeAction::Ignore => {
-                    // We can continue even when the type cannot be resolved
-                    // (i.e. it is an inference variable) because `Ty::builtin_deref`
-                    // and `try_overloaded_deref` both simply return `None`
-                    // in such a case without producing spurious errors.
-                    self.resolve_type_vars_if_possible(&t)
-                }
-            };
-            if resolved_t.references_error() {
-                return (resolved_t, autoderefs, None);
-            }
-
-            match should_stop(resolved_t, autoderefs) {
-                Some(x) => return (resolved_t, autoderefs, Some(x)),
-                None => {}
-            }
-
-            // Otherwise, deref if type is derefable:
-
-            // Super subtle: it might seem as though we should
-            // pass `opt_expr` to `try_overloaded_deref`, so that
-            // the (implicit) autoref of using an overloaded deref
-            // would get added to the adjustment table. However we
-            // do not do that, because it's kind of a
-            // "meta-adjustment" -- instead, we just leave it
-            // unrecorded and know that there "will be" an
-            // autoref. regionck and other bits of the code base,
-            // when they encounter an overloaded autoderef, have
-            // to do some reconstructive surgery. This is a pretty
-            // complex mess that is begging for a proper MIR.
-            let mt = if let Some(mt) = resolved_t.builtin_deref(false, lvalue_pref) {
-                mt
-            } else if let Some(method) = self.try_overloaded_deref(sp, None,
-                                                                   resolved_t, lvalue_pref) {
-                for expr in maybe_exprs() {
-                    let method_call = MethodCall::autoderef(expr.id, autoderefs as u32);
-                    self.tables.borrow_mut().method_map.insert(method_call, method);
-                }
-                self.make_overloaded_lvalue_return_type(method)
-            } else {
-                return (resolved_t, autoderefs, None);
-            };
-
-            t = mt.ty;
-            if mt.mutbl == hir::MutImmutable {
-                lvalue_pref = NoPreference;
-            }
-        }
-
-        // We've reached the recursion limit, error gracefully.
-        span_err!(self.tcx.sess, sp, E0055,
-            "reached the recursion limit while auto-dereferencing {:?}",
-            base_ty);
-        (self.tcx.types.err, 0, None)
-    }
-
-    fn try_overloaded_deref(&self,
-                            span: Span,
-                            base_expr: Option<&hir::Expr>,
-                            base_ty: Ty<'tcx>,
-                            lvalue_pref: LvaluePreference)
-                            -> Option<MethodCallee<'tcx>>
-    {
-        // Try DerefMut first, if preferred.
-        let method = match (lvalue_pref, self.tcx.lang_items.deref_mut_trait()) {
-            (PreferMutLvalue, Some(trait_did)) => {
-                self.lookup_method_in_trait(span, base_expr,
-                                            token::intern("deref_mut"), trait_did,
-                                            base_ty, None)
-            }
-            _ => None
-        };
-
-        // Otherwise, fall back to Deref.
-        let method = match (method, self.tcx.lang_items.deref_trait()) {
-            (None, Some(trait_did)) => {
-                self.lookup_method_in_trait(span, base_expr,
-                                            token::intern("deref"), trait_did,
-                                            base_ty, None)
-            }
-            (method, _) => method
-        };
-
-        method
-    }
-
     /// For the overloaded lvalue expressions (`*x`, `x[3]`), the trait
     /// returns a type of `&T`, but the actual type we assign to the
     /// *expression* is `T`. So this function just peels off the return
@@ -2371,29 +2247,28 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         // autoderef that normal method probing does. They could likely be
         // consolidated.
 
-        let (ty, autoderefs, final_mt) = self.autoderef(base_expr.span,
-                                                        base_ty,
-                                                        || Some(base_expr),
-                                                        UnresolvedTypeAction::Error,
-                                                        lvalue_pref,
-                                                        |adj_ty, idx| {
-            self.try_index_step(MethodCall::expr(expr.id), expr, base_expr,
-                                adj_ty, idx, false, lvalue_pref, idx_ty)
-        });
+        let mut autoderef = self.autoderef(base_expr.span, base_ty);
 
-        if final_mt.is_some() {
-            return final_mt;
-        }
+        while let Some((adj_ty, autoderefs)) = autoderef.next() {
+            if let Some(final_mt) = self.try_index_step(
+                MethodCall::expr(expr.id),
+                expr, base_expr, adj_ty, autoderefs,
+                false, lvalue_pref, idx_ty)
+            {
+                autoderef.finalize(lvalue_pref, Some(base_expr));
+                return Some(final_mt);
+            }
 
-        // After we have fully autoderef'd, if the resulting type is [T; n], then
-        // do a final unsized coercion to yield [T].
-        if let ty::TyArray(element_ty, _) = ty.sty {
-            let adjusted_ty = self.tcx.mk_slice(element_ty);
-            self.try_index_step(MethodCall::expr(expr.id), expr, base_expr,
-                                adjusted_ty, autoderefs, true, lvalue_pref, idx_ty)
-        } else {
-            None
+            if let ty::TyArray(element_ty, _) = adj_ty.sty {
+                autoderef.finalize(lvalue_pref, Some(base_expr));
+                let adjusted_ty = self.tcx.mk_slice(element_ty);
+                return self.try_index_step(
+                    MethodCall::expr(expr.id), expr, base_expr,
+                    adjusted_ty, autoderefs, true, lvalue_pref, idx_ty);
+            }
         }
+        autoderef.unambiguous_final_ty();
+        None
     }
 
     /// To type-check `base_expr[index_expr]`, we progressively autoderef
@@ -3034,32 +2909,23 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         let expr_t = self.structurally_resolved_type(expr.span,
                                                      self.expr_ty(base));
         let mut private_candidate = None;
-        let (_, autoderefs, field_ty) = self.autoderef(expr.span,
-                                                       expr_t,
-                                                       || Some(base),
-                                                       UnresolvedTypeAction::Error,
-                                                       lvalue_pref,
-                                                       |base_t, _| {
-                if let ty::TyStruct(base_def, substs) = base_t.sty {
-                    debug!("struct named {:?}",  base_t);
-                    if let Some(field) = base_def.struct_variant().find_field_named(field.node) {
-                        let field_ty = self.field_ty(expr.span, field, substs);
-                        if field.vis.is_accessible_from(self.body_id, &self.tcx().map) {
-                            return Some(field_ty);
-                        }
-                        private_candidate = Some((base_def.did, field_ty));
+        let mut autoderef = self.autoderef(expr.span, expr_t);
+        while let Some((base_t, autoderefs)) = autoderef.next() {
+            if let ty::TyStruct(base_def, substs) = base_t.sty {
+                debug!("struct named {:?}",  base_t);
+                if let Some(field) = base_def.struct_variant().find_field_named(field.node) {
+                    let field_ty = self.field_ty(expr.span, field, substs);
+                    if field.vis.is_accessible_from(self.body_id, &self.tcx().map) {
+                        autoderef.finalize(lvalue_pref, Some(base));
+                        self.write_ty(expr.id, field_ty);
+                        self.write_autoderef_adjustment(base.id, autoderefs);
+                        return;
                     }
+                    private_candidate = Some((base_def.did, field_ty));
                 }
-                None
-            });
-        match field_ty {
-            Some(field_ty) => {
-                self.write_ty(expr.id, field_ty);
-                self.write_autoderef_adjustment(base.id, autoderefs);
-                return;
             }
-            None => {}
         }
+        autoderef.unambiguous_final_ty();
 
         if let Some((did, field_ty)) = private_candidate {
             let struct_path = self.tcx().item_path_str(did);
@@ -3132,42 +2998,39 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                                                      self.expr_ty(base));
         let mut private_candidate = None;
         let mut tuple_like = false;
-        let (_, autoderefs, field_ty) = self.autoderef(expr.span,
-                                                       expr_t,
-                                                       || Some(base),
-                                                       UnresolvedTypeAction::Error,
-                                                       lvalue_pref,
-                                                       |base_t, _| {
-                let (base_def, substs) = match base_t.sty {
-                    ty::TyStruct(base_def, substs) => (base_def, substs),
-                    ty::TyTuple(ref v) => {
-                        tuple_like = true;
-                        return if idx.node < v.len() { Some(v[idx.node]) } else { None }
-                    }
-                    _ => return None,
-                };
-
-                tuple_like = base_def.struct_variant().is_tuple_struct();
-                if !tuple_like { return None }
-
-                debug!("tuple struct named {:?}",  base_t);
-                if let Some(field) = base_def.struct_variant().fields.get(idx.node) {
-                    let field_ty = self.field_ty(expr.span, field, substs);
-                    if field.vis.is_accessible_from(self.body_id, &self.tcx().map) {
-                        return Some(field_ty);
-                    }
-                    private_candidate = Some((base_def.did, field_ty));
+        let mut autoderef = self.autoderef(expr.span, expr_t);
+        while let Some((base_t, autoderefs)) = autoderef.next() {
+            let field = match base_t.sty {
+                ty::TyStruct(base_def, substs) => {
+                    tuple_like = base_def.struct_variant().is_tuple_struct();
+                    if !tuple_like { continue }
+
+                    debug!("tuple struct named {:?}",  base_t);
+                    base_def.struct_variant().fields.get(idx.node).and_then(|field| {
+                        let field_ty = self.field_ty(expr.span, field, substs);
+                        private_candidate = Some((base_def.did, field_ty));
+                        if field.vis.is_accessible_from(self.body_id, &self.tcx().map) {
+                            Some(field_ty)
+                        } else {
+                            None
+                        }
+                    })
                 }
-                None
-            });
-        match field_ty {
-            Some(field_ty) => {
+                ty::TyTuple(ref v) => {
+                    tuple_like = true;
+                    v.get(idx.node).cloned()
+                }
+                _ => continue
+            };
+
+            if let Some(field_ty) = field {
+                autoderef.finalize(lvalue_pref, Some(base));
                 self.write_ty(expr.id, field_ty);
                 self.write_autoderef_adjustment(base.id, autoderefs);
                 return;
             }
-            None => {}
         }
+        autoderef.unambiguous_final_ty();
 
         if let Some((did, field_ty)) = private_candidate {
             let struct_path = self.tcx().item_path_str(did);
diff --git a/src/test/compile-fail/E0055.rs b/src/test/compile-fail/E0055.rs
index cb78f4b3bb5..f86d7ec114b 100644
--- a/src/test/compile-fail/E0055.rs
+++ b/src/test/compile-fail/E0055.rs
@@ -19,5 +19,4 @@ fn main() {
     let foo = Foo;
     let ref_foo = &&Foo;
     ref_foo.foo(); //~ ERROR E0055
-                   //~^ ERROR E0275
 }
diff --git a/src/test/compile-fail/borrowck/borrowck-borrow-overloaded-auto-deref-mut.rs b/src/test/compile-fail/borrowck/borrowck-borrow-overloaded-auto-deref-mut.rs
index 497b0e63edf..764d05be879 100644
--- a/src/test/compile-fail/borrowck/borrowck-borrow-overloaded-auto-deref-mut.rs
+++ b/src/test/compile-fail/borrowck/borrowck-borrow-overloaded-auto-deref-mut.rs
@@ -99,7 +99,7 @@ fn assign_field1<'a>(x: Own<Point>) {
 }
 
 fn assign_field2<'a>(x: &'a Own<Point>) {
-    x.y = 3; //~ ERROR cannot assign
+    x.y = 3; //~ ERROR cannot borrow
 }
 
 fn assign_field3<'a>(x: &'a mut Own<Point>) {
diff --git a/src/test/compile-fail/issue-24819.rs b/src/test/compile-fail/issue-24819.rs
new file mode 100644
index 00000000000..52f5f1cd079
--- /dev/null
+++ b/src/test/compile-fail/issue-24819.rs
@@ -0,0 +1,21 @@
+// Copyright 2016 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 std::collections::HashSet;
+
+fn main() {
+    let mut v = Vec::new();
+    foo(&mut v);
+    //~^ ERROR mismatched types
+    //~| expected struct `std::collections::HashSet`, found struct `std::vec::Vec`
+}
+
+fn foo(h: &mut HashSet<u32>) {
+}
diff --git a/src/test/compile-fail/regions-bound-missing-bound-in-impl.rs b/src/test/compile-fail/regions-bound-missing-bound-in-impl.rs
index abffd33e3f8..6e60a373d9b 100644
--- a/src/test/compile-fail/regions-bound-missing-bound-in-impl.rs
+++ b/src/test/compile-fail/regions-bound-missing-bound-in-impl.rs
@@ -34,7 +34,8 @@ impl<'a, 't> Foo<'a, 't> for &'a isize {
     }
 
     fn wrong_bound1<'b,'c,'d:'a+'c>(self, b: Inv<'b>, c: Inv<'c>, d: Inv<'d>) {
-        //~^ ERROR method `wrong_bound1` has an incompatible type for trait
+        //~^ ERROR method not compatible with trait
+        //~^^ ERROR method not compatible with trait
         //
         // Note: This is a terrible error message. It is caused
         // because, in the trait, 'b is early bound, and in the impl,
diff --git a/src/test/compile-fail/regions-trait-1.rs b/src/test/compile-fail/regions-trait-1.rs
index 01439ce5e68..9cd08656b62 100644
--- a/src/test/compile-fail/regions-trait-1.rs
+++ b/src/test/compile-fail/regions-trait-1.rs
@@ -23,7 +23,7 @@ impl<'a> get_ctxt for has_ctxt<'a> {
 
     // Here an error occurs because we used `&self` but
     // the definition used `&`:
-    fn get_ctxt(&self) -> &'a ctxt { //~ ERROR method `get_ctxt` has an incompatible type
+    fn get_ctxt(&self) -> &'a ctxt { //~ ERROR method not compatible with trait
         self.c
     }