auto merge of #12491 : eddyb/rust/deref, r=nikomatsakis

Add the `Deref` and `DerefMut` traits and implement overloading explicit dereferences.

19 files changed, 520 insertions, 138 deletions

diff --git a/src/doc/rust.md b/src/doc/rust.md
index bb299b107c7..4e30b5537c6 100644
--- a/src/doc/rust.md
+++ b/src/doc/rust.md
@@ -2485,8 +2485,11 @@ before the expression they apply to.
 `*`
   : Dereference. When applied to a [pointer](#pointer-types) it denotes the pointed-to location.
     For pointers to mutable locations, the resulting [lvalue](#lvalues-rvalues-and-temporaries) can be assigned to.
-    For [enums](#enumerated-types) that have only a single variant, containing a single parameter,
-    the dereference operator accesses this parameter.
+    On non-pointer types, it calls calls the `deref` method of the `std::ops::Deref` trait, or the
+    `deref_mut` method of the `std::ops::DerefMut` trait (if implemented by the type and required
+    for an outer expression that will or could mutate the dereference), and produces the
+    result of dereferencing the `&` or `&mut` borrowed pointer returned from the overload method.
+
 `!`
   : Logical negation. On the boolean type, this flips between `true` and
     `false`. On integer types, this inverts the individual bits in the
diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs
index e9a96b0c47e..9e70b89d548 100644
--- a/src/librustc/middle/borrowck/mod.rs
+++ b/src/librustc/middle/borrowck/mod.rs
@@ -921,14 +921,17 @@ impl mc::Typer for TcxTyper {
         Ok(ty::node_id_to_type(self.tcx, id))
     }
 
+    fn node_method_ty(&mut self, id: ast::NodeId) -> Option<ty::t> {
+        self.method_map.borrow().get().find(&id).map(|method| method.ty)
+    }
+
     fn adjustment(&mut self, id: ast::NodeId) -> Option<@ty::AutoAdjustment> {
         let adjustments = self.tcx.adjustments.borrow();
         adjustments.get().find_copy(&id)
     }
 
     fn is_method_call(&mut self, id: ast::NodeId) -> bool {
-        let method_map = self.method_map.borrow();
-        method_map.get().contains_key(&id)
+        self.method_map.borrow().get().contains_key(&id)
     }
 
     fn temporary_scope(&mut self, id: ast::NodeId) -> Option<ast::NodeId> {
diff --git a/src/librustc/middle/lang_items.rs b/src/librustc/middle/lang_items.rs
index bedf8ed0529..ba5d9663c3b 100644
--- a/src/librustc/middle/lang_items.rs
+++ b/src/librustc/middle/lang_items.rs
@@ -232,6 +232,9 @@ lets_do_this! {
     ShrTraitLangItem,                "shr",                     shr_trait;
     IndexTraitLangItem,              "index",                   index_trait;
 
+    DerefTraitLangItem,              "deref",                   deref_trait;
+    DerefMutTraitLangItem,           "deref_mut",               deref_mut_trait;
+
     EqTraitLangItem,                 "eq",                      eq_trait;
     OrdTraitLangItem,                "ord",                     ord_trait;
 
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index fe66ec88f8f..45d1f112e95 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -267,6 +267,7 @@ pub type McResult<T> = Result<T, ()>;
 pub trait Typer {
     fn tcx(&self) -> ty::ctxt;
     fn node_ty(&mut self, id: ast::NodeId) -> McResult<ty::t>;
+    fn node_method_ty(&mut self, id: ast::NodeId) -> Option<ty::t>;
     fn adjustment(&mut self, node_id: ast::NodeId) -> Option<@ty::AutoAdjustment>;
     fn is_method_call(&mut self, id: ast::NodeId) -> bool;
     fn temporary_scope(&mut self, rvalue_id: ast::NodeId) -> Option<ast::NodeId>;
@@ -433,11 +434,13 @@ impl<TYPER:Typer> MemCategorizationContext<TYPER> {
         let expr_ty = if_ok!(self.expr_ty(expr));
         match expr.node {
           ast::ExprUnary(ast::UnDeref, e_base) => {
-            if self.typer.is_method_call(expr.id) {
-                return Ok(self.cat_rvalue_node(expr.id(), expr.span(), expr_ty));
-            }
-
-            let base_cmt = if_ok!(self.cat_expr(e_base));
+            let base_cmt = match self.typer.node_method_ty(expr.id) {
+                Some(method_ty) => {
+                    let ref_ty = ty::ty_fn_ret(method_ty);
+                    self.cat_rvalue_node(expr.id(), expr.span(), ref_ty)
+                }
+                None => if_ok!(self.cat_expr(e_base))
+            };
             Ok(self.cat_deref(expr, base_cmt, 0))
           }
 
diff --git a/src/librustc/middle/trans/callee.rs b/src/librustc/middle/trans/callee.rs
index 3c44c607e7f..9a780678e4f 100644
--- a/src/librustc/middle/trans/callee.rs
+++ b/src/librustc/middle/trans/callee.rs
@@ -444,14 +444,12 @@ pub fn trans_call<'a>(
                   call_ex: &ast::Expr,
                   f: &ast::Expr,
                   args: CallArgs,
-                  id: ast::NodeId,
                   dest: expr::Dest)
                   -> &'a Block<'a> {
     let _icx = push_ctxt("trans_call");
     trans_call_inner(in_cx,
                      Some(common::expr_info(call_ex)),
                      expr_ty(in_cx, f),
-                     node_id_type(in_cx, id),
                      |cx, _| trans(cx, f),
                      args,
                      Some(dest)).bcx
@@ -471,7 +469,6 @@ pub fn trans_method_call<'a>(
         bcx,
         Some(common::expr_info(call_ex)),
         monomorphize_type(bcx, method_ty),
-        expr_ty(bcx, call_ex),
         |cx, arg_cleanup_scope| {
             meth::trans_method_callee(cx, call_ex.id, rcvr, arg_cleanup_scope)
         },
@@ -490,11 +487,9 @@ pub fn trans_lang_call<'a>(
     } else {
         csearch::get_type(bcx.ccx().tcx, did).ty
     };
-    let rty = ty::ty_fn_ret(fty);
     callee::trans_call_inner(bcx,
                              None,
                              fty,
-                             rty,
                              |bcx, _| {
                                 trans_fn_ref_with_vtables_to_callee(bcx,
                                                                     did,
@@ -520,12 +515,10 @@ pub fn trans_lang_call_with_type_params<'a>(
         fty = csearch::get_type(bcx.tcx(), did).ty;
     }
 
-    let rty = ty::ty_fn_ret(fty);
     return callee::trans_call_inner(
         bcx,
         None,
         fty,
-        rty,
         |bcx, _| {
             let callee =
                 trans_fn_ref_with_vtables_to_callee(bcx, did, 0,
@@ -554,7 +547,6 @@ pub fn trans_call_inner<'a>(
                         bcx: &'a Block<'a>,
                         call_info: Option<NodeInfo>,
                         callee_ty: ty::t,
-                        ret_ty: ty::t,
                         get_callee: |bcx: &'a Block<'a>,
                                      arg_cleanup_scope: cleanup::ScopeId|
                                      -> Callee<'a>,
@@ -610,9 +602,10 @@ pub fn trans_call_inner<'a>(
         }
     };
 
-    let abi = match ty::get(callee_ty).sty {
-        ty::ty_bare_fn(ref f) => f.abis,
-        _ => AbiSet::Rust()
+    let (abi, ret_ty) = match ty::get(callee_ty).sty {
+        ty::ty_bare_fn(ref f) => (f.abis, f.sig.output),
+        ty::ty_closure(ref f) => (AbiSet::Rust(), f.sig.output),
+        _ => fail!("expected bare rust fn or closure in trans_call_inner")
     };
     let is_rust_fn =
         abi.is_rust() ||
diff --git a/src/librustc/middle/trans/expr.rs b/src/librustc/middle/trans/expr.rs
index b033086125d..fbb7decb302 100644
--- a/src/librustc/middle/trans/expr.rs
+++ b/src/librustc/middle/trans/expr.rs
@@ -467,10 +467,6 @@ fn trans_datum_unadjusted<'a>(bcx: &'a Block<'a>,
 
             trans_binary(bcx, expr, op, lhs, rhs)
         }
-        ast::ExprUnary(ast::UnDeref, base) => {
-            let basedatum = unpack_datum!(bcx, trans(bcx, base));
-            deref_once(bcx, expr, basedatum, 0)
-        }
         ast::ExprUnary(op, x) => {
             trans_unary_datum(bcx, expr, op, x)
         }
@@ -782,12 +778,7 @@ fn trans_rvalue_dps_unadjusted<'a>(bcx: &'a Block<'a>,
             closure::trans_expr_fn(bcx, sigil, decl, body, expr.id, dest)
         }
         ast::ExprCall(f, ref args) => {
-            callee::trans_call(bcx,
-                               expr,
-                               f,
-                               callee::ArgExprs(args.as_slice()),
-                               expr.id,
-                               dest)
+            callee::trans_call(bcx, expr, f, callee::ArgExprs(args.as_slice()), dest)
         }
         ast::ExprMethodCall(_, _, ref args) => {
             callee::trans_method_call(bcx,
@@ -798,18 +789,15 @@ fn trans_rvalue_dps_unadjusted<'a>(bcx: &'a Block<'a>,
         }
         ast::ExprBinary(_, lhs, rhs) => {
             // if not overloaded, would be RvalueDatumExpr
-            trans_overloaded_op(bcx, expr, lhs,
-                                Some(&*rhs), expr_ty(bcx, expr), dest)
+            trans_overloaded_op(bcx, expr, lhs, Some(&*rhs), Some(dest)).bcx
         }
         ast::ExprUnary(_, subexpr) => {
             // if not overloaded, would be RvalueDatumExpr
-            trans_overloaded_op(bcx, expr, subexpr,
-                                None, expr_ty(bcx, expr), dest)
+            trans_overloaded_op(bcx, expr, subexpr, None, Some(dest)).bcx
         }
         ast::ExprIndex(base, idx) => {
             // if not overloaded, would be RvalueDatumExpr
-            trans_overloaded_op(bcx, expr, base,
-                                Some(&*idx), expr_ty(bcx, expr), dest)
+            trans_overloaded_op(bcx, expr, base, Some(&*idx), Some(dest)).bcx
         }
         ast::ExprCast(val, _) => {
             // DPS output mode means this is a trait cast:
@@ -1185,17 +1173,14 @@ fn trans_unary_datum<'a>(
     let mut bcx = bcx;
     let _icx = push_ctxt("trans_unary_datum");
 
-    // if deref, would be LvalueExpr
-    assert!(op != ast::UnDeref);
-
-    // if overloaded, would be RvalueDpsExpr
-    {
+    let overloaded = {
         let method_map = bcx.ccx().maps.method_map.borrow();
-        assert!(!method_map.get().contains_key(&un_expr.id));
-    }
+        method_map.get().contains_key(&un_expr.id)
+    };
+    // if overloaded, would be RvalueDpsExpr
+    assert!(!overloaded || op == ast::UnDeref);
 
     let un_ty = expr_ty(bcx, un_expr);
-    let sub_ty = expr_ty(bcx, sub_expr);
 
     return match op {
         ast::UnNot => {
@@ -1226,15 +1211,19 @@ fn trans_unary_datum<'a>(
             immediate_rvalue_bcx(bcx, llneg, un_ty).to_expr_datumblock()
         }
         ast::UnBox => {
-            trans_boxed_expr(bcx, un_ty, sub_expr, sub_ty, heap_managed)
+            trans_boxed_expr(bcx, un_ty, sub_expr, expr_ty(bcx, sub_expr), heap_managed)
         }
         ast::UnUniq => {
-            trans_boxed_expr(bcx, un_ty, sub_expr, sub_ty, heap_exchange)
+            trans_boxed_expr(bcx, un_ty, sub_expr, expr_ty(bcx, sub_expr), heap_exchange)
         }
         ast::UnDeref => {
-            bcx.sess().bug("deref expressions should have been \
-                            translated using trans_lvalue(), not \
-                            trans_unary_datum()")
+            if overloaded {
+                let r = trans_overloaded_op(bcx, un_expr, sub_expr, None, None);
+                DatumBlock(r.bcx, Datum(r.val, un_ty, LvalueExpr))
+            } else {
+                let datum = unpack_datum!(bcx, trans(bcx, sub_expr));
+                deref_once(bcx, un_expr, datum, 0)
+            }
         }
     };
 }
@@ -1506,14 +1495,12 @@ fn trans_overloaded_op<'a, 'b>(
                        expr: &ast::Expr,
                        rcvr: &'b ast::Expr,
                        arg: Option<&'b ast::Expr>,
-                       ret_ty: ty::t,
-                       dest: Dest)
-                       -> &'a Block<'a> {
+                       dest: Option<Dest>)
+                       -> Result<'a> {
     let method_ty = bcx.ccx().maps.method_map.borrow().get().get(&expr.id).ty;
     callee::trans_call_inner(bcx,
                              Some(expr_info(expr)),
                              monomorphize_type(bcx, method_ty),
-                             ret_ty,
                              |bcx, arg_cleanup_scope| {
                                 meth::trans_method_callee(bcx,
                                                           expr.id,
@@ -1521,7 +1508,7 @@ fn trans_overloaded_op<'a, 'b>(
                                                           arg_cleanup_scope)
                              },
                              callee::ArgAutorefSecond(rcvr, arg),
-                             Some(dest)).bcx
+                             dest)
 }
 
 fn int_cast(bcx: &Block,
diff --git a/src/librustc/middle/trans/reflect.rs b/src/librustc/middle/trans/reflect.rs
index 196c69fd59e..bb31ed0aef8 100644
--- a/src/librustc/middle/trans/reflect.rs
+++ b/src/librustc/middle/trans/reflect.rs
@@ -105,9 +105,8 @@ impl<'a> Reflector<'a> {
         for (i, a) in args.iter().enumerate() {
             debug!("arg {}: {}", i, bcx.val_to_str(*a));
         }
-        let bool_ty = ty::mk_bool();
         let result = unpack_result!(bcx, callee::trans_call_inner(
-            self.bcx, None, mth_ty, bool_ty,
+            self.bcx, None, mth_ty,
             |bcx, _| meth::trans_trait_callee_from_llval(bcx,
                                                          mth_ty,
                                                          mth_idx,
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index e043bc8683f..34442c565ad 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -3284,6 +3284,7 @@ pub fn expr_kind(tcx: ctxt,
             // exception, as its result is always unit.
             return match expr.node {
                 ast::ExprAssignOp(..) => RvalueStmtExpr,
+                ast::ExprUnary(ast::UnDeref, _) => LvalueExpr,
                 _ => RvalueDpsExpr
             };
         }
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index f68bdcf3131..fe8d4caf905 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -1243,6 +1243,11 @@ impl FnCtxt {
     }
 }
 
+pub enum LvaluePreference {
+    PreferMutLvalue,
+    NoPreference
+}
+
 pub fn do_autoderef(fcx: @FnCtxt, sp: Span, t: ty::t) -> (ty::t, uint) {
     /*!
      *
@@ -1307,6 +1312,40 @@ pub fn do_autoderef(fcx: @FnCtxt, sp: Span, t: ty::t) -> (ty::t, uint) {
     };
 }
 
+fn try_overloaded_deref(fcx: @FnCtxt,
+                        expr: &ast::Expr,
+                        base_expr: &ast::Expr,
+                        base_ty: ty::t,
+                        lvalue_pref: LvaluePreference)
+                        -> Option<ty::mt> {
+    // Try DerefMut first, if preferred.
+    let method = match (lvalue_pref, fcx.tcx().lang_items.deref_mut_trait()) {
+        (PreferMutLvalue, Some(trait_did)) => {
+            method::lookup_in_trait(fcx, expr, base_expr, token::intern("deref_mut"),
+                                    trait_did, base_ty, [], DontAutoderefReceiver)
+        }
+        _ => None
+    };
+
+    // Otherwise, fall back to Deref.
+    let method = match (method, fcx.tcx().lang_items.deref_trait()) {
+        (None, Some(trait_did)) => {
+            method::lookup_in_trait(fcx, expr, base_expr, token::intern("deref"),
+                                    trait_did, base_ty, [], DontAutoderefReceiver)
+        }
+        (method, _) => method
+    };
+
+    match method {
+        Some(method) => {
+            let ref_ty = ty::ty_fn_ret(method.ty);
+            fcx.inh.method_map.borrow_mut().get().insert(expr.id, method);
+            ty::deref(ref_ty, true)
+        }
+        None => None
+    }
+}
+
 // AST fragment checking
 pub fn check_lit(fcx: @FnCtxt, lit: &ast::Lit) -> ty::t {
     let tcx = fcx.ccx.tcx;
@@ -1349,35 +1388,43 @@ pub fn valid_range_bounds(ccx: @CrateCtxt,
 pub fn check_expr_has_type(
     fcx: @FnCtxt, expr: &ast::Expr,
     expected: ty::t) {
-    check_expr_with_unifier(fcx, expr, Some(expected), || {
+    check_expr_with_unifier(fcx, expr, Some(expected), NoPreference, || {
         demand::suptype(fcx, expr.span, expected, fcx.expr_ty(expr));
     });
 }
 
-pub fn check_expr_coercable_to_type(
-    fcx: @FnCtxt, expr: &ast::Expr,
-    expected: ty::t) {
-    check_expr_with_unifier(fcx, expr, Some(expected), || {
+fn check_expr_coercable_to_type(fcx: @FnCtxt, expr: &ast::Expr, expected: ty::t) {
+    check_expr_with_unifier(fcx, expr, Some(expected), NoPreference, || {
         demand::coerce(fcx, expr.span, expected, expr)
     });
 }
 
-pub fn check_expr_with_hint(
-    fcx: @FnCtxt, expr: &ast::Expr,
-    expected: ty::t) {
-    check_expr_with_unifier(fcx, expr, Some(expected), || ())
+fn check_expr_with_hint(fcx: @FnCtxt, expr: &ast::Expr, expected: ty::t) {
+    check_expr_with_unifier(fcx, expr, Some(expected), NoPreference, || ())
 }
 
-pub fn check_expr_with_opt_hint(
-    fcx: @FnCtxt, expr: &ast::Expr,
-    expected: Option<ty::t>)  {
-    check_expr_with_unifier(fcx, expr, expected, || ())
+fn check_expr_with_opt_hint(fcx: @FnCtxt, expr: &ast::Expr,
+                            expected: Option<ty::t>)  {
+    check_expr_with_unifier(fcx, expr, expected, NoPreference, || ())
+}
+
+fn check_expr_with_opt_hint_and_lvalue_pref(fcx: @FnCtxt,
+                                            expr: &ast::Expr,
+                                            expected: Option<ty::t>,
+                                            lvalue_pref: LvaluePreference) {
+    check_expr_with_unifier(fcx, expr, expected, lvalue_pref, || ())
 }
 
-pub fn check_expr(fcx: @FnCtxt, expr: &ast::Expr)  {
-    check_expr_with_unifier(fcx, expr, None, || ())
+fn check_expr(fcx: @FnCtxt, expr: &ast::Expr)  {
+    check_expr_with_unifier(fcx, expr, None, NoPreference, || ())
 }
 
+fn check_expr_with_lvalue_pref(fcx: @FnCtxt, expr: &ast::Expr,
+                               lvalue_pref: LvaluePreference)  {
+    check_expr_with_unifier(fcx, expr, None, lvalue_pref, || ())
+}
+
+
 // determine the `self` type, using fresh variables for all variables
 // declared on the impl declaration e.g., `impl<A,B> for ~[(A,B)]`
 // would return ($0, $1) where $0 and $1 are freshly instantiated type
@@ -1606,10 +1653,11 @@ fn check_type_parameter_positions_in_path(function_context: @FnCtxt,
 /// Note that inspecting a type's structure *directly* may expose the fact
 /// that there are actually multiple representations for both `ty_err` and
 /// `ty_bot`, so avoid that when err and bot need to be handled differently.
-pub fn check_expr_with_unifier(fcx: @FnCtxt,
-                               expr: &ast::Expr,
-                               expected: Option<ty::t>,
-                               unifier: ||) {
+fn check_expr_with_unifier(fcx: @FnCtxt,
+                           expr: &ast::Expr,
+                           expected: Option<ty::t>,
+                           lvalue_pref: LvaluePreference,
+                           unifier: ||) {
     debug!(">> typechecking");
 
     fn check_method_argument_types(
@@ -1795,18 +1843,6 @@ pub fn check_expr_with_unifier(fcx: @FnCtxt,
         vec::from_fn(len, |_| ty::mk_err())
     }
 
-    // A generic function for checking assignment expressions
-    fn check_assignment(fcx: @FnCtxt,
-                        lhs: &ast::Expr,
-                        rhs: &ast::Expr,
-                        id: ast::NodeId) {
-        check_expr(fcx, lhs);
-        let lhs_type = fcx.expr_ty(lhs);
-        check_expr_has_type(fcx, rhs, lhs_type);
-        fcx.write_ty(id, ty::mk_nil());
-        // The callee checks for bot / err, we don't need to
-    }
-
     fn write_call(fcx: @FnCtxt, call_expr: &ast::Expr, output: ty::t) {
         fcx.write_ty(call_expr.id, output);
     }
@@ -1868,7 +1904,10 @@ pub fn check_expr_with_unifier(fcx: @FnCtxt,
                          args: &[@ast::Expr],
                          tps: &[ast::P<ast::Ty>]) {
         let rcvr = args[0];
-        check_expr(fcx, rcvr);
+        // We can't know if we need &mut self before we look up the method,
+        // so treat the receiver as mutable just in case - only explicit
+        // overloaded dereferences care about the distinction.
+        check_expr_with_lvalue_pref(fcx, rcvr, PreferMutLvalue);
 
         // no need to check for bot/err -- callee does that
         let expr_t = structurally_resolved_type(fcx,
@@ -1999,7 +2038,12 @@ pub fn check_expr_with_unifier(fcx: @FnCtxt,
                    is_binop_assignment: IsBinopAssignment) {
         let tcx = fcx.ccx.tcx;
 
-        check_expr(fcx, lhs);
+        let lvalue_pref = match is_binop_assignment {
+            BinopAssignment => PreferMutLvalue,
+            SimpleBinop => NoPreference
+        };
+        check_expr_with_lvalue_pref(fcx, lhs, lvalue_pref);
+
         // Callee does bot / err checking
         let lhs_t = structurally_resolved_type(fcx, lhs.span,
                                                fcx.expr_ty(lhs));
@@ -2246,11 +2290,12 @@ pub fn check_expr_with_unifier(fcx: @FnCtxt,
     // Check field access expressions
     fn check_field(fcx: @FnCtxt,
                    expr: &ast::Expr,
+                   lvalue_pref: LvaluePreference,
                    base: &ast::Expr,
                    field: ast::Name,
                    tys: &[ast::P<ast::Ty>]) {
         let tcx = fcx.ccx.tcx;
-        let bot = check_expr(fcx, base);
+        let bot = check_expr_with_lvalue_pref(fcx, base, lvalue_pref);
         let expr_t = structurally_resolved_type(fcx, expr.span,
                                                 fcx.expr_ty(base));
         let (base_t, derefs) = do_autoderef(fcx, expr.span, expr_t);
@@ -2278,7 +2323,7 @@ pub fn check_expr_with_unifier(fcx: @FnCtxt,
             _ => ()
         }
 
-        let tps : ~[ty::t] = tys.iter().map(|&ty| fcx.to_ty(ty)).collect();
+        let tps: ~[ty::t] = tys.iter().map(|&ty| fcx.to_ty(ty)).collect();
         match method::lookup(fcx,
                              expr,
                              base,
@@ -2678,10 +2723,13 @@ pub fn check_expr_with_unifier(fcx: @FnCtxt,
                 ast::UnDeref => None
             }
         });
-        check_expr_with_opt_hint(fcx, oprnd, exp_inner);
+        let lvalue_pref = match unop {
+            ast::UnDeref => lvalue_pref,
+            _ => NoPreference
+        };
+        check_expr_with_opt_hint_and_lvalue_pref(fcx, oprnd, exp_inner, lvalue_pref);
         let mut oprnd_t = fcx.expr_ty(oprnd);
-        if !ty::type_is_error(oprnd_t) &&
-              !ty::type_is_bot(oprnd_t) {
+        if !ty::type_is_error(oprnd_t) && !ty::type_is_bot(oprnd_t) {
             match unop {
                 ast::UnBox => {
                     oprnd_t = ty::mk_box(tcx, oprnd_t)
@@ -2690,33 +2738,35 @@ pub fn check_expr_with_unifier(fcx: @FnCtxt,
                     oprnd_t = ty::mk_uniq(tcx, oprnd_t);
                 }
                 ast::UnDeref => {
-                    let sty = structure_of(fcx, expr.span, oprnd_t);
-                    let operand_ty = ty::deref_sty(sty, true);
-                    match operand_ty {
-                        Some(mt) => {
-                            oprnd_t = mt.ty
-                        }
-                        None => {
-                            match *sty {
-                                ty::ty_struct(did, ref substs) if {
-                                    let fields = ty::struct_fields(fcx.tcx(), did, substs);
-                                    fields.len() == 1
-                                      && fields[0].ident == token::special_idents::unnamed_field
-                                } => {
+                    oprnd_t = structurally_resolved_type(fcx, expr.span, oprnd_t);
+                    oprnd_t = match ty::deref(oprnd_t, true) {
+                        Some(mt) => mt.ty,
+                        None => match try_overloaded_deref(fcx, expr, oprnd,
+                                                           oprnd_t, lvalue_pref) {
+                            Some(mt) => mt.ty,
+                            None => {
+                                let is_newtype = match ty::get(oprnd_t).sty {
+                                    ty::ty_struct(did, ref substs) => {
+                                        let fields = ty::struct_fields(fcx.tcx(), did, substs);
+                                        fields.len() == 1
+                                        && fields[0].ident == token::special_idents::unnamed_field
+                                    }
+                                    _ => false
+                                };
+                                if is_newtype {
                                     // This is an obsolete struct deref
-                                    tcx.sess.span_err(
-                                        expr.span,
-                                        "single-field tuple-structs can no longer be dereferenced");
-                                }
-                                _ => {
-                                    fcx.type_error_message(expr.span,
-                                        |actual| {
-                                            format!("type `{}` cannot be dereferenced", actual)
+                                    tcx.sess.span_err(expr.span,
+                                        "single-field tuple-structs can \
+                                         no longer be dereferenced");
+                                } else {
+                                    fcx.type_error_message(expr.span, |actual| {
+                                        format!("type `{}` cannot be dereferenced", actual)
                                     }, oprnd_t, None);
                                 }
+                                ty::mk_err()
                             }
                         }
-                    }
+                    };
                 }
                 ast::UnNot => {
                     oprnd_t = structurally_resolved_type(fcx, oprnd.span,
@@ -2747,7 +2797,11 @@ pub fn check_expr_with_unifier(fcx: @FnCtxt,
               fcx, expected,
               |sty| match *sty { ty::ty_rptr(_, ref mt) => Some(mt.ty),
                                  _ => None });
-        check_expr_with_opt_hint(fcx, oprnd, hint);
+        let lvalue_pref = match mutbl {
+            ast::MutMutable => PreferMutLvalue,
+            ast::MutImmutable => NoPreference
+        };
+        check_expr_with_opt_hint_and_lvalue_pref(fcx, oprnd, hint, lvalue_pref);
 
         // Note: at this point, we cannot say what the best lifetime
         // is to use for resulting pointer.  We want to use the
@@ -2817,11 +2871,11 @@ pub fn check_expr_with_unifier(fcx: @FnCtxt,
         fcx.write_ty(id, ty::mk_u32())
       }
       ast::ExprParen(a) => {
-        check_expr_with_opt_hint(fcx, a, expected);
+        check_expr_with_opt_hint_and_lvalue_pref(fcx, a, expected, lvalue_pref);
         fcx.write_ty(id, fcx.expr_ty(a));
       }
       ast::ExprAssign(lhs, rhs) => {
-        check_assignment(fcx, lhs, rhs, id);
+        check_expr_with_lvalue_pref(fcx, lhs, PreferMutLvalue);
 
         let tcx = fcx.tcx();
         if !ty::expr_is_lval(tcx, fcx.ccx.method_map, lhs) {
@@ -2829,14 +2883,14 @@ pub fn check_expr_with_unifier(fcx: @FnCtxt,
         }
 
         let lhs_ty = fcx.expr_ty(lhs);
+        check_expr_has_type(fcx, rhs, lhs_ty);
         let rhs_ty = fcx.expr_ty(rhs);
+
         if ty::type_is_error(lhs_ty) || ty::type_is_error(rhs_ty) {
             fcx.write_error(id);
-        }
-        else if ty::type_is_bot(lhs_ty) || ty::type_is_bot(rhs_ty) {
+        } else if ty::type_is_bot(lhs_ty) || ty::type_is_bot(rhs_ty) {
             fcx.write_bot(id);
-        }
-        else {
+        } else {
             fcx.write_nil(id);
         }
       }
@@ -3111,10 +3165,10 @@ pub fn check_expr_with_unifier(fcx: @FnCtxt,
         }
       }
       ast::ExprField(base, field, ref tys) => {
-        check_field(fcx, expr, base, field.name, tys.as_slice());
+        check_field(fcx, expr, lvalue_pref, base, field.name, tys.as_slice());
       }
       ast::ExprIndex(base, idx) => {
-          check_expr(fcx, base);
+          check_expr_with_lvalue_pref(fcx, base, lvalue_pref);
           check_expr(fcx, idx);
           let raw_base_t = fcx.expr_ty(base);
           let idx_t = fcx.expr_ty(idx);
diff --git a/src/librustc/middle/typeck/check/regionck.rs b/src/librustc/middle/typeck/check/regionck.rs
index ed03ced5ca0..381ff141bfb 100644
--- a/src/librustc/middle/typeck/check/regionck.rs
+++ b/src/librustc/middle/typeck/check/regionck.rs
@@ -226,12 +226,6 @@ impl Rcx {
         self.resolve_type(t)
     }
 
-    /// Try to resolve the callee type for the given method call.
-    pub fn resolve_method_type(&mut self, id: ast::NodeId) -> ty::t {
-        let t = self.fcx.method_ty(id);
-        self.resolve_type(t)
-    }
-
     /// Try to resolve the type for the given node.
     pub fn resolve_expr_type_adjusted(&mut self, expr: &ast::Expr) -> ty::t {
         let ty_unadjusted = self.resolve_node_type(expr.id);
@@ -258,14 +252,19 @@ impl<'a> mc::Typer for &'a mut Rcx {
         if ty::type_is_error(t) {Err(())} else {Ok(t)}
     }
 
+    fn node_method_ty(&mut self, id: ast::NodeId) -> Option<ty::t> {
+        self.fcx.inh.method_map.borrow().get().find(&id).map(|method| {
+            self.resolve_type(method.ty)
+        })
+    }
+
     fn adjustment(&mut self, id: ast::NodeId) -> Option<@ty::AutoAdjustment> {
         let adjustments = self.fcx.inh.adjustments.borrow();
         adjustments.get().find_copy(&id)
     }
 
     fn is_method_call(&mut self, id: ast::NodeId) -> bool {
-        let method_map = self.fcx.inh.method_map.borrow();
-        method_map.get().contains_key(&id)
+        self.fcx.inh.method_map.borrow().get().contains_key(&id)
     }
 
     fn temporary_scope(&mut self, id: ast::NodeId) -> Option<ast::NodeId> {
@@ -489,7 +488,13 @@ fn visit_expr(rcx: &mut Rcx, expr: &ast::Expr) {
 
         ast::ExprUnary(ast::UnDeref, base) => {
             // For *a, the lifetime of a must enclose the deref
-            let base_ty = rcx.resolve_node_type(base.id);
+            let base_ty = match rcx.fcx.inh.method_map.get().find(&expr.id) {
+                Some(method) => {
+                    constrain_call(rcx, None, expr, Some(base), [], true);
+                    ty::ty_fn_ret(method.ty)
+                }
+                None => rcx.resolve_node_type(base.id)
+            };
             constrain_derefs(rcx, expr, 1, base_ty);
 
             visit::walk_expr(rcx, expr, ());
@@ -764,7 +769,7 @@ fn constrain_call(rcx: &mut Rcx,
             implicitly_ref_args);
     let callee_ty = match fn_expr_id {
         Some(id) => rcx.resolve_node_type(id),
-        None => rcx.resolve_method_type(call_expr.id)
+        None => rcx.resolve_type(rcx.fcx.method_ty(call_expr.id))
     };
     if ty::type_is_error(callee_ty) {
         // Bail, as function type is unknown
diff --git a/src/libstd/cell.rs b/src/libstd/cell.rs
index 12524499a32..f4b530644a7 100644
--- a/src/libstd/cell.rs
+++ b/src/libstd/cell.rs
@@ -15,7 +15,7 @@ use clone::{Clone, DeepClone};
 use cmp::Eq;
 use fmt;
 use kinds::{marker, Pod};
-use ops::Drop;
+use ops::{Deref, DerefMut, Drop};
 use option::{None, Option, Some};
 
 /// A mutable memory location that admits only `Pod` data.
@@ -258,6 +258,13 @@ impl<'b, T> Ref<'b, T> {
     }
 }
 
+impl<'b, T> Deref<T> for Ref<'b, T> {
+    #[inline]
+    fn deref<'a>(&'a self) -> &'a T {
+        &self.parent.value
+    }
+}
+
 /// Wraps a mutable borrowed reference to a value in a `RefCell` box.
 pub struct RefMut<'b, T> {
     priv parent: &'b mut RefCell<T>
@@ -279,6 +286,20 @@ impl<'b, T> RefMut<'b, T> {
     }
 }
 
+impl<'b, T> Deref<T> for RefMut<'b, T> {
+    #[inline]
+    fn deref<'a>(&'a self) -> &'a T {
+        &self.parent.value
+    }
+}
+
+impl<'b, T> DerefMut<T> for RefMut<'b, T> {
+    #[inline]
+    fn deref_mut<'a>(&'a mut self) -> &'a mut T {
+        &mut self.parent.value
+    }
+}
+
 #[cfg(test)]
 mod test {
     use super::*;
diff --git a/src/libstd/ops.rs b/src/libstd/ops.rs
index ac329e6fe83..2d5d37e1abc 100644
--- a/src/libstd/ops.rs
+++ b/src/libstd/ops.rs
@@ -464,6 +464,28 @@ pub trait Index<Index,Result> {
     fn index(&self, index: &Index) -> Result;
 }
 
+#[cfg(stage0)]
+pub trait Deref<Result> {
+    fn deref<'a>(&'a self) -> &'a Result;
+}
+
+#[cfg(not(stage0))]
+#[lang="deref"]
+pub trait Deref<Result> {
+    fn deref<'a>(&'a self) -> &'a Result;
+}
+
+#[cfg(stage0)]
+pub trait DerefMut<Result>: Deref<Result> {
+    fn deref_mut<'a>(&'a mut self) -> &'a mut Result;
+}
+
+#[cfg(not(stage0))]
+#[lang="deref_mut"]
+pub trait DerefMut<Result>: Deref<Result> {
+    fn deref_mut<'a>(&'a mut self) -> &'a mut Result;
+}
+
 #[cfg(test)]
 mod bench {
     extern crate test;
diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs
index 19848f65097..c1cd3a6d79f 100644
--- a/src/libstd/prelude.rs
+++ b/src/libstd/prelude.rs
@@ -23,7 +23,7 @@ generally useful to many Rust programs.
 pub use kinds::{Freeze, Pod, Send, Sized};
 pub use ops::{Add, Sub, Mul, Div, Rem, Neg, Not};
 pub use ops::{BitAnd, BitOr, BitXor};
-pub use ops::{Drop};
+pub use ops::{Drop, Deref, DerefMut};
 pub use ops::{Shl, Shr, Index};
 pub use option::{Option, Some, None};
 pub use result::{Result, Ok, Err};
diff --git a/src/libstd/rc.rs b/src/libstd/rc.rs
index ea3d5e0edac..5daf6e797be 100644
--- a/src/libstd/rc.rs
+++ b/src/libstd/rc.rs
@@ -27,7 +27,7 @@ use cast::transmute;
 use clone::{Clone, DeepClone};
 use cmp::{Eq, Ord};
 use kinds::marker;
-use ops::Drop;
+use ops::{Deref, Drop};
 use option::{Option, Some, None};
 use ptr;
 use rt::global_heap::exchange_free;
@@ -78,6 +78,14 @@ impl<T> Rc<T> {
     }
 }
 
+impl<T> Deref<T> for Rc<T> {
+    /// Borrow the value contained in the reference-counted box
+    #[inline(always)]
+    fn deref<'a>(&'a self) -> &'a T {
+        unsafe { &(*self.ptr).value }
+    }
+}
+
 #[unsafe_destructor]
 impl<T> Drop for Rc<T> {
     fn drop(&mut self) {
diff --git a/src/test/compile-fail/borrowck-borrow-overloaded-deref-mut.rs b/src/test/compile-fail/borrowck-borrow-overloaded-deref-mut.rs
new file mode 100644
index 00000000000..4d220b3cc09
--- /dev/null
+++ b/src/test/compile-fail/borrowck-borrow-overloaded-deref-mut.rs
@@ -0,0 +1,68 @@
+// 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 how overloaded deref interacts with borrows when DerefMut
+// is implemented.
+
+use std::ops::{Deref, DerefMut};
+
+struct Own<T> {
+    value: *mut T
+}
+
+impl<T> Deref<T> for Own<T> {
+    fn deref<'a>(&'a self) -> &'a T {
+        unsafe { &*self.value }
+    }
+}
+
+impl<T> DerefMut<T> for Own<T> {
+    fn deref_mut<'a>(&'a mut self) -> &'a mut T {
+        unsafe { &mut *self.value }
+    }
+}
+
+fn deref_imm(x: Own<int>) {
+    let _i = &*x;
+}
+
+fn deref_mut1(x: Own<int>) {
+    let _i = &mut *x; //~ ERROR cannot borrow
+}
+
+fn deref_mut2(mut x: Own<int>) {
+    let _i = &mut *x;
+}
+
+fn deref_extend<'a>(x: &'a Own<int>) -> &'a int {
+    &**x
+}
+
+fn deref_extend_mut1<'a>(x: &'a Own<int>) -> &'a mut int {
+    &mut **x //~ ERROR cannot borrow
+}
+
+fn deref_extend_mut2<'a>(x: &'a mut Own<int>) -> &'a mut int {
+    &mut **x
+}
+
+fn assign1<'a>(x: Own<int>) {
+    *x = 3; //~ ERROR cannot borrow
+}
+
+fn assign2<'a>(x: &'a Own<int>) {
+    **x = 3; //~ ERROR cannot borrow
+}
+
+fn assign3<'a>(x: &'a mut Own<int>) {
+    **x = 3;
+}
+
+pub fn main() {}
\ No newline at end of file
diff --git a/src/test/compile-fail/borrowck-borrow-overloaded-deref.rs b/src/test/compile-fail/borrowck-borrow-overloaded-deref.rs
new file mode 100644
index 00000000000..7aac9458e3c
--- /dev/null
+++ b/src/test/compile-fail/borrowck-borrow-overloaded-deref.rs
@@ -0,0 +1,62 @@
+// 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 how overloaded deref interacts with borrows when only
+// Deref and not DerefMut is implemented.
+
+use std::ops::Deref;
+
+struct Rc<T> {
+    value: *T
+}
+
+impl<T> Deref<T> for Rc<T> {
+    fn deref<'a>(&'a self) -> &'a T {
+        unsafe { &*self.value }
+    }
+}
+
+fn deref_imm(x: Rc<int>) {
+    let _i = &*x;
+}
+
+fn deref_mut1(x: Rc<int>) {
+    let _i = &mut *x; //~ ERROR cannot borrow
+}
+
+fn deref_mut2(mut x: Rc<int>) {
+    let _i = &mut *x; //~ ERROR cannot borrow
+}
+
+fn deref_extend<'a>(x: &'a Rc<int>) -> &'a int {
+    &**x
+}
+
+fn deref_extend_mut1<'a>(x: &'a Rc<int>) -> &'a mut int {
+    &mut **x //~ ERROR cannot borrow
+}
+
+fn deref_extend_mut2<'a>(x: &'a mut Rc<int>) -> &'a mut int {
+    &mut **x //~ ERROR cannot borrow
+}
+
+fn assign1<'a>(x: Rc<int>) {
+    *x = 3; //~ ERROR cannot assign
+}
+
+fn assign2<'a>(x: &'a Rc<int>) {
+    **x = 3; //~ ERROR cannot assign
+}
+
+fn assign3<'a>(x: &'a mut Rc<int>) {
+    **x = 3; //~ ERROR cannot assign
+}
+
+pub fn main() {}
diff --git a/src/test/compile-fail/borrowck-move-out-of-overloaded-deref.rs b/src/test/compile-fail/borrowck-move-out-of-overloaded-deref.rs
new file mode 100644
index 00000000000..fc9210f54a0
--- /dev/null
+++ b/src/test/compile-fail/borrowck-move-out-of-overloaded-deref.rs
@@ -0,0 +1,16 @@
+// 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 std::rc::Rc;
+
+pub fn main() {
+    let _x = *Rc::new(~"hi");
+    //~^ ERROR cannot move out of dereference of `&`-pointer
+}
diff --git a/src/test/run-pass/overloaded-deref-count.rs b/src/test/run-pass/overloaded-deref-count.rs
new file mode 100644
index 00000000000..28ac70c47c5
--- /dev/null
+++ b/src/test/run-pass/overloaded-deref-count.rs
@@ -0,0 +1,85 @@
+// 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 std::cell::Cell;
+use std::ops::{Deref, DerefMut};
+use std::vec_ng::Vec;
+
+struct DerefCounter<T> {
+    count_imm: Cell<uint>,
+    count_mut: uint,
+    value: T
+}
+
+impl<T> DerefCounter<T> {
+    fn new(value: T) -> DerefCounter<T> {
+        DerefCounter {
+            count_imm: Cell::new(0),
+            count_mut: 0,
+            value: value
+        }
+    }
+
+    fn counts(&self) -> (uint, uint) {
+        (self.count_imm.get(), self.count_mut)
+    }
+}
+
+impl<T> Deref<T> for DerefCounter<T> {
+    fn deref<'a>(&'a self) -> &'a T {
+        self.count_imm.set(self.count_imm.get() + 1);
+        &self.value
+    }
+}
+
+impl<T> DerefMut<T> for DerefCounter<T> {
+    fn deref_mut<'a>(&'a mut self) -> &'a mut T {
+        self.count_mut += 1;
+        &mut self.value
+    }
+}
+
+pub fn main() {
+    let mut n = DerefCounter::new(0);
+    let mut v = DerefCounter::new(Vec::new());
+
+    let _ = *n; // Immutable deref + copy a POD.
+    assert_eq!(n.counts(), (1, 0));
+
+    let _ = (&*n, &*v); // Immutable deref + borrow.
+    assert_eq!(n.counts(), (2, 0)); assert_eq!(v.counts(), (1, 0));
+
+    let _ = (&mut *n, &mut *v); // Mutable deref + mutable borrow.
+    assert_eq!(n.counts(), (2, 1)); assert_eq!(v.counts(), (1, 1));
+
+    let mut v2 = Vec::new();
+    v2.push(1);
+
+    *n = 5; *v = v2; // Mutable deref + assignment.
+    assert_eq!(n.counts(), (2, 2)); assert_eq!(v.counts(), (1, 2));
+
+    *n -= 3; // Mutable deref + assignment with binary operation.
+    assert_eq!(n.counts(), (2, 3));
+
+    // Mutable deref used for calling a method taking &self.
+    // N.B. This is required because method lookup hasn't been performed so
+    // we don't know whether the called method takes mutable self, before
+    // the dereference itself is type-checked (a chicken-and-egg problem).
+    (*n).to_str();
+    assert_eq!(n.counts(), (2, 4));
+
+    // Mutable deref used for calling a method taking &mut self.
+    (*v).push(2);
+    assert_eq!(v.counts(), (1, 3));
+
+    // Check the final states.
+    assert_eq!(*n, 2);
+    assert_eq!((*v).as_slice(), &[1, 2]);
+}
diff --git a/src/test/run-pass/overloaded-deref.rs b/src/test/run-pass/overloaded-deref.rs
new file mode 100644
index 00000000000..86046e8e05d
--- /dev/null
+++ b/src/test/run-pass/overloaded-deref.rs
@@ -0,0 +1,49 @@
+// 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 std::cell::RefCell;
+use std::rc::Rc;
+
+#[deriving(Eq, Show)]
+struct Point {
+    x: int,
+    y: int
+}
+
+pub fn main() {
+    assert_eq!(*Rc::new(5), 5);
+    assert_eq!(***Rc::new(~~5), 5);
+    assert_eq!(*Rc::new(Point {x: 2, y: 4}), Point {x: 2, y: 4});
+
+    let i = Rc::new(RefCell::new(2));
+    let i_value = *(*i).borrow();
+    *(*i).borrow_mut() = 5;
+    assert_eq!((i_value, *(*i).borrow()), (2, 5));
+
+    let s = Rc::new(~"foo");
+    assert_eq!(*s, ~"foo");
+    assert_eq!((*s).as_slice(), "foo");
+
+    let mut_s = Rc::new(RefCell::new(~"foo"));
+    (*(*mut_s).borrow_mut()).push_str("bar");
+    // assert_eq! would fail here because it stores the LHS and RHS in two locals.
+    assert!((*(*mut_s).borrow()).as_slice() == "foobar");
+    assert!((*(*mut_s).borrow_mut()).as_slice() == "foobar");
+
+    let p = Rc::new(RefCell::new(Point {x: 1, y: 2}));
+    (*(*p).borrow_mut()).x = 3;
+    (*(*p).borrow_mut()).y += 3;
+    assert_eq!(*(*p).borrow(), Point {x: 3, y: 5});
+
+    let v = Rc::new(RefCell::new(~[1, 2, 3]));
+    (*(*v).borrow_mut())[0] = 3;
+    (*(*v).borrow_mut())[1] += 3;
+    assert_eq!(((*(*v).borrow())[0], (*(*v).borrow())[1], (*(*v).borrow())[2]), (3, 5, 3));
+}