librustc (RFC #34): Implement the new `Index` and `IndexMut` traits.

This will break code that used the old `Index` trait. Change this code
to use the new `Index` traits. For reference, here are their signatures:

    pub trait Index<Index,Result> {
        fn index<'a>(&'a self, index: &Index) -> &'a Result;
    }
    pub trait IndexMut<Index,Result> {
        fn index_mut<'a>(&'a mut self, index: &Index) -> &'a mut Result;
    }

Closes #6515.

[breaking-change]

5 files changed, 214 insertions, 71 deletions

diff --git a/src/librustc/middle/lang_items.rs b/src/librustc/middle/lang_items.rs
index 186a737a56b..1a1d47b2547 100644
--- a/src/librustc/middle/lang_items.rs
+++ b/src/librustc/middle/lang_items.rs
@@ -234,6 +234,7 @@ lets_do_this! {
     ShlTraitLangItem,                "shl",                     shl_trait;
     ShrTraitLangItem,                "shr",                     shr_trait;
     IndexTraitLangItem,              "index",                   index_trait;
+    IndexMutTraitLangItem,           "index_mut",               index_mut_trait;
 
     UnsafeTypeLangItem,              "unsafe",                  unsafe_type;
 
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index 54cca082e0d..96716ce09e0 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -443,10 +443,6 @@ impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
           }
 
           ast::ExprIndex(ref 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(&**base));
             Ok(self.cat_index(expr, base_cmt, 0))
           }
@@ -759,7 +755,7 @@ impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
 
     pub fn cat_index<N:ast_node>(&self,
                                  elt: &N,
-                                 base_cmt: cmt,
+                                 mut base_cmt: cmt,
                                  derefs: uint)
                                  -> cmt {
         //! Creates a cmt for an indexing operation (`[]`); this
@@ -793,14 +789,26 @@ impl<'t,TYPER:Typer> MemCategorizationContext<'t,TYPER> {
         //! - `derefs`: the deref number to be used for
         //!   the implicit index deref, if any (see above)
 
-        let element_ty = match ty::array_element_ty(base_cmt.ty) {
-          Some(ref mt) => mt.ty,
-          None => {
-            self.tcx().sess.span_bug(
-                elt.span(),
-                format!("Explicit index of non-index type `{}`",
-                        base_cmt.ty.repr(self.tcx())).as_slice());
-          }
+        let method_call = typeck::MethodCall::expr(elt.id());
+        let method_ty = self.typer.node_method_ty(method_call);
+
+        let element_ty = match method_ty {
+            Some(method_ty) => {
+                let ref_ty = ty::ty_fn_ret(method_ty);
+                base_cmt = self.cat_rvalue_node(elt.id(), elt.span(), ref_ty);
+                *ty::ty_fn_args(method_ty).get(0)
+            }
+            None => {
+                match ty::array_element_ty(base_cmt.ty) {
+                    Some(ref mt) => mt.ty,
+                    None => {
+                        self.tcx().sess.span_bug(
+                            elt.span(),
+                            format!("Explicit index of non-index type `{}`",
+                                    base_cmt.ty.repr(self.tcx())).as_slice());
+                    }
+                }
+            }
         };
 
         return match deref_kind(self.tcx(), base_cmt.ty) {
diff --git a/src/librustc/middle/trans/expr.rs b/src/librustc/middle/trans/expr.rs
index ac33f9bd1a8..85e85f8ab55 100644
--- a/src/librustc/middle/trans/expr.rs
+++ b/src/librustc/middle/trans/expr.rs
@@ -396,7 +396,7 @@ fn trans_datum_unadjusted<'a>(bcx: &'a Block<'a>,
             trans_rec_field(bcx, &**base, ident.node)
         }
         ast::ExprIndex(ref base, ref idx) => {
-            trans_index(bcx, expr, &**base, &**idx)
+            trans_index(bcx, expr, &**base, &**idx, MethodCall::expr(expr.id))
         }
         ast::ExprVstore(ref contents, ast::ExprVstoreUniq) => {
             fcx.push_ast_cleanup_scope(contents.id);
@@ -467,7 +467,8 @@ fn trans_rec_field<'a>(bcx: &'a Block<'a>,
 fn trans_index<'a>(bcx: &'a Block<'a>,
                    index_expr: &ast::Expr,
                    base: &ast::Expr,
-                   idx: &ast::Expr)
+                   idx: &ast::Expr,
+                   method_call: MethodCall)
                    -> DatumBlock<'a, Expr> {
     //! Translates `base[idx]`.
 
@@ -475,43 +476,97 @@ fn trans_index<'a>(bcx: &'a Block<'a>,
     let ccx = bcx.ccx();
     let mut bcx = bcx;
 
-    let base_datum = unpack_datum!(bcx, trans_to_lvalue(bcx, base, "index"));
-
-    // Translate index expression and cast to a suitable LLVM integer.
-    // Rust is less strict than LLVM in this regard.
-    let ix_datum = unpack_datum!(bcx, trans(bcx, idx));
-    let ix_val = ix_datum.to_llscalarish(bcx);
-    let ix_size = machine::llbitsize_of_real(bcx.ccx(), val_ty(ix_val));
-    let int_size = machine::llbitsize_of_real(bcx.ccx(), ccx.int_type);
-    let ix_val = {
-        if ix_size < int_size {
-            if ty::type_is_signed(expr_ty(bcx, idx)) {
-                SExt(bcx, ix_val, ccx.int_type)
-            } else { ZExt(bcx, ix_val, ccx.int_type) }
-        } else if ix_size > int_size {
-            Trunc(bcx, ix_val, ccx.int_type)
-        } else {
-            ix_val
-        }
-    };
+    // Check for overloaded index.
+    let method_ty = ccx.tcx
+                       .method_map
+                       .borrow()
+                       .find(&method_call)
+                       .map(|method| method.ty);
+    let elt_datum = match method_ty {
+        Some(method_ty) => {
+            let base_datum = unpack_datum!(bcx, trans(bcx, base));
 
-    let vt = tvec::vec_types(bcx, ty::sequence_element_type(bcx.tcx(), base_datum.ty));
-    base::maybe_name_value(bcx.ccx(), vt.llunit_size, "unit_sz");
+            // Translate index expression.
+            let ix_datum = unpack_datum!(bcx, trans(bcx, idx));
 
-    let (base, len) = base_datum.get_vec_base_and_len(bcx);
+            // Overloaded. Evaluate `trans_overloaded_op`, which will
+            // invoke the user's index() method, which basically yields
+            // a `&T` pointer.  We can then proceed down the normal
+            // path (below) to dereference that `&T`.
+            let val =
+                unpack_result!(bcx,
+                               trans_overloaded_op(bcx,
+                                                   index_expr,
+                                                   method_call,
+                                                   base_datum,
+                                                   Some((ix_datum, idx.id)),
+                                                   None));
+            let ref_ty = ty::ty_fn_ret(monomorphize_type(bcx, method_ty));
+            let elt_ty = match ty::deref(ref_ty, true) {
+                None => {
+                    bcx.tcx().sess.span_bug(index_expr.span,
+                                            "index method didn't return a \
+                                             dereferenceable type?!")
+                }
+                Some(elt_tm) => elt_tm.ty,
+            };
+            Datum::new(val, elt_ty, LvalueExpr)
+        }
+        None => {
+            let base_datum = unpack_datum!(bcx, trans_to_lvalue(bcx,
+                                                                base,
+                                                                "index"));
+
+            // Translate index expression and cast to a suitable LLVM integer.
+            // Rust is less strict than LLVM in this regard.
+            let ix_datum = unpack_datum!(bcx, trans(bcx, idx));
+            let ix_val = ix_datum.to_llscalarish(bcx);
+            let ix_size = machine::llbitsize_of_real(bcx.ccx(),
+                                                     val_ty(ix_val));
+            let int_size = machine::llbitsize_of_real(bcx.ccx(),
+                                                      ccx.int_type);
+            let ix_val = {
+                if ix_size < int_size {
+                    if ty::type_is_signed(expr_ty(bcx, idx)) {
+                        SExt(bcx, ix_val, ccx.int_type)
+                    } else { ZExt(bcx, ix_val, ccx.int_type) }
+                } else if ix_size > int_size {
+                    Trunc(bcx, ix_val, ccx.int_type)
+                } else {
+                    ix_val
+                }
+            };
 
-    debug!("trans_index: base {}", bcx.val_to_str(base));
-    debug!("trans_index: len {}", bcx.val_to_str(len));
+            let vt =
+                tvec::vec_types(bcx,
+                                ty::sequence_element_type(bcx.tcx(),
+                                                          base_datum.ty));
+            base::maybe_name_value(bcx.ccx(), vt.llunit_size, "unit_sz");
+
+            let (base, len) = base_datum.get_vec_base_and_len(bcx);
+
+            debug!("trans_index: base {}", bcx.val_to_str(base));
+            debug!("trans_index: len {}", bcx.val_to_str(len));
+
+            let bounds_check = ICmp(bcx, lib::llvm::IntUGE, ix_val, len);
+            let expect = ccx.get_intrinsic(&("llvm.expect.i1"));
+            let expected = Call(bcx,
+                                expect,
+                                [bounds_check, C_bool(ccx, false)],
+                                []);
+            bcx = with_cond(bcx, expected, |bcx| {
+                controlflow::trans_fail_bounds_check(bcx,
+                                                     index_expr.span,
+                                                     ix_val,
+                                                     len)
+            });
+            let elt = InBoundsGEP(bcx, base, [ix_val]);
+            let elt = PointerCast(bcx, elt, vt.llunit_ty.ptr_to());
+            Datum::new(elt, vt.unit_ty, LvalueExpr)
+        }
+    };
 
-    let bounds_check = ICmp(bcx, lib::llvm::IntUGE, ix_val, len);
-    let expect = ccx.get_intrinsic(&("llvm.expect.i1"));
-    let expected = Call(bcx, expect, [bounds_check, C_bool(ccx, false)], []);
-    let bcx = with_cond(bcx, expected, |bcx| {
-            controlflow::trans_fail_bounds_check(bcx, index_expr.span, ix_val, len)
-        });
-    let elt = InBoundsGEP(bcx, base, [ix_val]);
-    let elt = PointerCast(bcx, elt, vt.llunit_ty.ptr_to());
-    DatumBlock::new(bcx, Datum::new(elt, vt.unit_ty, LvalueExpr))
+    DatumBlock::new(bcx, elt_datum)
 }
 
 fn trans_def<'a>(bcx: &'a Block<'a>,
@@ -1756,7 +1811,7 @@ fn deref_once<'a>(bcx: &'a Block<'a>,
         Some(method_ty) => {
             // Overloaded. Evaluate `trans_overloaded_op`, which will
             // invoke the user's deref() method, which basically
-            // converts from the `Shaht<T>` pointer that we have into
+            // converts from the `Smaht<T>` pointer that we have into
             // a `&T` pointer.  We can then proceed down the normal
             // path (below) to dereference that `&T`.
             let datum = match method_call.adjustment {
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 141731ded95..282ccf1155d 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -3030,6 +3030,9 @@ pub fn expr_kind(tcx: &ctxt, expr: &ast::Expr) -> ExprKind {
             // the deref method invoked for `*a` always yields an `&T`
             ast::ExprUnary(ast::UnDeref, _) => LvalueExpr,
 
+            // the index method invoked for `a[i]` always yields an `&T`
+            ast::ExprIndex(..) => LvalueExpr,
+
             // in the general case, result could be any type, use DPS
             _ => RvalueDpsExpr
         };
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index e4d9bcfad61..a5817832212 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -1629,6 +1629,76 @@ fn try_overloaded_deref(fcx: &FnCtxt,
     }
 }
 
+fn try_overloaded_index(fcx: &FnCtxt,
+                        method_call: Option<MethodCall>,
+                        expr: &ast::Expr,
+                        base_expr: Gc<ast::Expr>,
+                        base_ty: ty::t,
+                        index_expr: Gc<ast::Expr>,
+                        lvalue_pref: LvaluePreference)
+                        -> Option<ty::mt> {
+    // Try `IndexMut` first, if preferred.
+    let method = match (lvalue_pref, fcx.tcx().lang_items.index_mut_trait()) {
+        (PreferMutLvalue, Some(trait_did)) => {
+            method::lookup_in_trait(fcx,
+                                    expr.span,
+                                    Some(&*base_expr),
+                                    token::intern("index_mut"),
+                                    trait_did,
+                                    base_ty,
+                                    [],
+                                    DontAutoderefReceiver,
+                                    IgnoreStaticMethods)
+        }
+        _ => None,
+    };
+
+    // Otherwise, fall back to `Index`.
+    let method = match (method, fcx.tcx().lang_items.index_trait()) {
+        (None, Some(trait_did)) => {
+            method::lookup_in_trait(fcx,
+                                    expr.span,
+                                    Some(&*base_expr),
+                                    token::intern("index"),
+                                    trait_did,
+                                    base_ty,
+                                    [],
+                                    DontAutoderefReceiver,
+                                    IgnoreStaticMethods)
+        }
+        (method, _) => method,
+    };
+
+    // Regardless of whether the lookup succeeds, check the method arguments
+    // so that we have *some* type for each argument.
+    let method_type = match method {
+        Some(ref method) => method.ty,
+        None => ty::mk_err()
+    };
+    check_method_argument_types(fcx,
+                                expr.span,
+                                method_type,
+                                expr,
+                                [base_expr, index_expr],
+                                DoDerefArgs,
+                                DontTupleArguments);
+
+    match method {
+        Some(method) => {
+            let ref_ty = ty::ty_fn_ret(method.ty);
+            match method_call {
+                Some(method_call) => {
+                    fcx.inh.method_map.borrow_mut().insert(method_call,
+                                                           method);
+                }
+                None => {}
+            }
+            ty::deref(ref_ty, true)
+        }
+        None => None,
+    }
+}
+
 fn check_method_argument_types(fcx: &FnCtxt,
                                sp: Span,
                                method_fn_ty: ty::t,
@@ -3323,7 +3393,7 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
           } else if ty::type_is_error(idx_t) || ty::type_is_bot(idx_t) {
               fcx.write_ty(id, idx_t);
           } else {
-              let (base_t, autoderefs, field_ty) =
+              let (_, autoderefs, field_ty) =
                 autoderef(fcx, expr.span, raw_base_t, Some(base.id),
                           lvalue_pref, |base_t, _| ty::index(base_t));
               match field_ty {
@@ -3333,27 +3403,33 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
                       fcx.write_autoderef_adjustment(base.id, autoderefs);
                   }
                   None => {
-                      let resolved = structurally_resolved_type(fcx,
-                                                                expr.span,
-                                                                raw_base_t);
-                      let ret_ty = lookup_op_method(fcx,
-                                                    expr,
-                                                    resolved,
-                                                    token::intern("index"),
-                                                    tcx.lang_items.index_trait(),
-                                                    [base.clone(), idx.clone()],
-                                                    AutoderefReceiver,
-                                                    || {
-                        fcx.type_error_message(expr.span,
-                                               |actual| {
-                                                    format!("cannot index a \
-                                                             value of type \
-                                                             `{}`", actual)
-                                               },
-                                               base_t,
-                                               None);
-                      });
-                      fcx.write_ty(id, ret_ty);
+                      // This is an overloaded method.
+                      let base_t = structurally_resolved_type(fcx,
+                                                              expr.span,
+                                                              raw_base_t);
+                      let method_call = MethodCall::expr(expr.id);
+                      match try_overloaded_index(fcx,
+                                                 Some(method_call),
+                                                 expr,
+                                                 *base,
+                                                 base_t,
+                                                 *idx,
+                                                 lvalue_pref) {
+                          Some(mt) => fcx.write_ty(id, mt.ty),
+                          None => {
+                                fcx.type_error_message(expr.span,
+                                                       |actual| {
+                                                        format!("cannot \
+                                                                 index a \
+                                                                 value of \
+                                                                 type `{}`",
+                                                                actual)
+                                                       },
+                                                       base_t,
+                                                       None);
+                                fcx.write_ty(id, ty::mk_err())
+                          }
+                      }
                   }
               }
           }