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]

18 files changed, 433 insertions, 167 deletions

diff --git a/src/etc/vim/syntax/rust.vim b/src/etc/vim/syntax/rust.vim
index a15bd3ca60f..6285eb6895d 100644
--- a/src/etc/vim/syntax/rust.vim
+++ b/src/etc/vim/syntax/rust.vim
@@ -65,7 +65,7 @@ syn keyword   rustTrait       Copy Send Sized Share
 syn keyword   rustTrait       Add Sub Mul Div Rem Neg Not
 syn keyword   rustTrait       BitAnd BitOr BitXor
 syn keyword   rustTrait       Drop Deref DerefMut
-syn keyword   rustTrait       Shl Shr Index
+syn keyword   rustTrait       Shl Shr Index IndexMut
 syn keyword   rustEnum        Option
 syn keyword   rustEnumVariant Some None
 syn keyword   rustEnum        Result
diff --git a/src/libcollections/bitv.rs b/src/libcollections/bitv.rs
index 6d7c91ccfee..f01b1cf9815 100644
--- a/src/libcollections/bitv.rs
+++ b/src/libcollections/bitv.rs
@@ -16,7 +16,6 @@ use core::cmp;
 use core::default::Default;
 use core::fmt;
 use core::iter::Take;
-use core::ops;
 use core::slice;
 use core::uint;
 use std::hash;
@@ -24,6 +23,29 @@ use std::hash;
 use {Collection, Mutable, Set, MutableSet};
 use vec::Vec;
 
+#[cfg(not(stage0))]
+use core::ops::Index;
+
+#[cfg(not(stage0))]
+static TRUE: bool = true;
+
+#[cfg(not(stage0))]
+static FALSE: bool = false;
+
+#[deriving(Clone)]
+struct SmallBitv {
+    /// only the lowest nbits of this value are used. the rest is undefined.
+    bits: uint
+}
+
+#[deriving(Clone)]
+struct BigBitv {
+    storage: Vec<uint>
+}
+
+#[deriving(Clone)]
+enum BitvVariant { Big(BigBitv), Small(SmallBitv) }
+
 /// The bitvector type
 ///
 /// # Example
@@ -58,6 +80,18 @@ pub struct Bitv {
     nbits: uint
 }
 
+#[cfg(not(stage0))]
+impl Index<uint,bool> for Bitv {
+    #[inline]
+    fn index<'a>(&'a self, i: &uint) -> &'a bool {
+        if self.get(*i) {
+            &TRUE
+        } else {
+            &FALSE
+        }
+    }
+}
+
 struct MaskWords<'a> {
     iter: slice::Items<'a, uint>,
     next_word: Option<&'a uint>,
@@ -268,7 +302,7 @@ impl Bitv {
             if offset >= bitv.nbits {
                 0
             } else {
-                bitv[offset] as u8 << (7 - bit)
+                bitv.get(offset) as u8 << (7 - bit)
             }
         }
 
@@ -287,6 +321,13 @@ impl Bitv {
     }
 
     /**
+     * Transform `self` into a `Vec<bool>` by turning each bit into a `bool`.
+     */
+    pub fn to_bools(&self) -> Vec<bool> {
+        Vec::from_fn(self.nbits, |i| self.get(i))
+    }
+
+    /**
      * Compare a bitvector to a vector of `bool`.
      *
      * Both the bitvector and vector must have the same length.
@@ -504,13 +545,6 @@ impl Clone for Bitv {
     }
 }
 
-impl ops::Index<uint,bool> for Bitv {
-    #[inline]
-    fn index(&self, i: &uint) -> bool {
-        self.get(*i)
-    }
-}
-
 impl fmt::Show for Bitv {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
         for bit in self.iter() {
@@ -1369,9 +1403,9 @@ mod tests {
         b2.set(1, true);
         b2.set(2, true);
         assert!(b1.difference(&b2));
-        assert!(b1[0]);
-        assert!(!b1[1]);
-        assert!(!b1[2]);
+        assert!(b1.get(0));
+        assert!(!b1.get(1));
+        assert!(!b1.get(2));
     }
 
     #[test]
@@ -1383,9 +1417,9 @@ mod tests {
         b2.set(40, true);
         b2.set(80, true);
         assert!(b1.difference(&b2));
-        assert!(b1[0]);
-        assert!(!b1[40]);
-        assert!(!b1[80]);
+        assert!(b1.get(0));
+        assert!(!b1.get(40));
+        assert!(!b1.get(80));
     }
 
     #[test]
diff --git a/src/libcore/ops.rs b/src/libcore/ops.rs
index d42c09b8163..fc37fdde8f5 100644
--- a/src/libcore/ops.rs
+++ b/src/libcore/ops.rs
@@ -613,7 +613,7 @@ shr_impl!(uint u8 u16 u32 u64 int i8 i16 i32 i64)
 /**
  *
  * The `Index` trait is used to specify the functionality of indexing operations
- * like `arr[idx]`.
+ * like `arr[idx]` when used in an immutable context.
  *
  * # Example
  *
@@ -624,9 +624,9 @@ shr_impl!(uint u8 u16 u32 u64 int i8 i16 i32 i64)
  * struct Foo;
  *
  * impl Index<Foo, Foo> for Foo {
- *     fn index(&self, _rhs: &Foo) -> Foo {
+ *     fn index<'a>(&'a self, _rhs: &Foo) -> &'a Foo {
  *         println!("Indexing!");
- *         *self
+ *         self
  *     }
  * }
  *
@@ -636,9 +636,42 @@ shr_impl!(uint u8 u16 u32 u64 int i8 i16 i32 i64)
  * ```
  */
 #[lang="index"]
+#[cfg(not(stage0))]
 pub trait Index<Index,Result> {
     /// The method for the indexing (`Foo[Bar]`) operation
-    fn index(&self, index: &Index) -> Result;
+    fn index<'a>(&'a self, index: &Index) -> &'a Result;
+}
+
+/**
+ *
+ * The `IndexMut` trait is used to specify the functionality of indexing
+ * operations like `arr[idx]`, when used in a mutable context.
+ *
+ * # Example
+ *
+ * A trivial implementation of `IndexMut`. When `Foo[Foo]` happens, it ends up
+ * calling `index`, and therefore, `main` prints `Indexing!`.
+ *
+ * ```
+ * struct Foo;
+ *
+ * impl IndexMut<Foo, Foo> for Foo {
+ *     fn index_mut<'a>(&'a mut self, _rhs: &Foo) -> &'a mut Foo {
+ *         println!("Indexing!");
+ *         self
+ *     }
+ * }
+ *
+ * fn main() {
+ *     &mut Foo[Foo];
+ * }
+ * ```
+ */
+#[lang="index_mut"]
+#[cfg(not(stage0))]
+pub trait IndexMut<Index,Result> {
+    /// The method for the indexing (`Foo[Bar]`) operation
+    fn index_mut<'a>(&'a mut self, index: &Index) -> &'a mut Result;
 }
 
 /**
diff --git a/src/libcore/prelude.rs b/src/libcore/prelude.rs
index df9c0e67b0d..f967a2a5fa5 100644
--- a/src/libcore/prelude.rs
+++ b/src/libcore/prelude.rs
@@ -33,7 +33,9 @@ pub use kinds::{Copy, Send, Sized, Share};
 pub use ops::{Add, Sub, Mul, Div, Rem, Neg, Not};
 pub use ops::{BitAnd, BitOr, BitXor};
 pub use ops::{Drop, Deref, DerefMut};
-pub use ops::{Shl, Shr, Index};
+pub use ops::{Shl, Shr};
+#[cfg(not(stage0))]
+pub use ops::{Index, IndexMut};
 pub use option::{Option, Some, None};
 pub use result::{Result, Ok, Err};
 
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())
+                          }
+                      }
                   }
               }
           }
diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs
index 61e8b63af35..28cd7223b0a 100644
--- a/src/libstd/prelude.rs
+++ b/src/libstd/prelude.rs
@@ -44,7 +44,8 @@
 #[doc(no_inline)] pub use ops::{Add, Sub, Mul, Div, Rem, Neg, Not};
 #[doc(no_inline)] pub use ops::{BitAnd, BitOr, BitXor};
 #[doc(no_inline)] pub use ops::{Drop, Deref, DerefMut};
-#[doc(no_inline)] pub use ops::{Shl, Shr, Index};
+#[doc(no_inline)] pub use ops::{Shl, Shr};
+#[doc(no_inline)] #[cfg(not(stage0))] pub use ops::{Index, IndexMut};
 #[doc(no_inline)] pub use option::{Option, Some, None};
 #[doc(no_inline)] pub use result::{Result, Ok, Err};
 
diff --git a/src/test/auxiliary/issue2378a.rs b/src/test/auxiliary/issue2378a.rs
deleted file mode 100644
index 934c4f52af0..00000000000
--- a/src/test/auxiliary/issue2378a.rs
+++ /dev/null
@@ -1,22 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-#![crate_type = "lib"]
-
-pub enum maybe<T> { just(T), nothing }
-
-impl <T:Clone> Index<uint,T> for maybe<T> {
-    fn index(&self, _idx: &uint) -> T {
-        match self {
-            &just(ref t) => (*t).clone(),
-            &nothing => { fail!(); }
-        }
-    }
-}
diff --git a/src/test/auxiliary/issue2378b.rs b/src/test/auxiliary/issue2378b.rs
deleted file mode 100644
index 03f685c949a..00000000000
--- a/src/test/auxiliary/issue2378b.rs
+++ /dev/null
@@ -1,23 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-#![crate_type = "lib"]
-
-extern crate issue2378a;
-
-use issue2378a::maybe;
-
-pub struct two_maybes<T> {pub a: maybe<T>, pub b: maybe<T>}
-
-impl<T:Clone> Index<uint,(T,T)> for two_maybes<T> {
-    fn index(&self, idx: &uint) -> (T, T) {
-        (self.a[*idx], self.b[*idx])
-    }
-}
diff --git a/src/test/compile-fail/borrowck-overloaded-index.rs b/src/test/compile-fail/borrowck-overloaded-index.rs
new file mode 100644
index 00000000000..d34aa1cd9cb
--- /dev/null
+++ b/src/test/compile-fail/borrowck-overloaded-index.rs
@@ -0,0 +1,64 @@
+// 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.
+
+struct Foo {
+    x: int,
+    y: int,
+}
+
+impl Index<String,int> for Foo {
+    fn index<'a>(&'a self, z: &String) -> &'a int {
+        if z.as_slice() == "x" {
+            &self.x
+        } else {
+            &self.y
+        }
+    }
+}
+
+impl IndexMut<String,int> for Foo {
+    fn index_mut<'a>(&'a mut self, z: &String) -> &'a mut int {
+        if z.as_slice() == "x" {
+            &mut self.x
+        } else {
+            &mut self.y
+        }
+    }
+}
+
+struct Bar {
+    x: int,
+}
+
+impl Index<int,int> for Bar {
+    fn index<'a>(&'a self, z: &int) -> &'a int {
+        &self.x
+    }
+}
+
+fn main() {
+    let mut f = Foo {
+        x: 1,
+        y: 2,
+    };
+    let mut s = "hello".to_string();
+    let rs = &mut s;
+    println!("{}", f[s]);
+    //~^ ERROR cannot borrow `s` as immutable because it is also borrowed as mutable
+    f[s] = 10;
+    //~^ ERROR cannot borrow `s` as immutable because it is also borrowed as mutable
+    let s = Bar {
+        x: 1,
+    };
+    s[2] = 20;
+    //~^ ERROR cannot assign to immutable indexed content
+}
+
+
diff --git a/src/test/run-pass/issue-11736.rs b/src/test/run-pass/issue-11736.rs
index 255807b4c0e..10d6e0158f6 100644
--- a/src/test/run-pass/issue-11736.rs
+++ b/src/test/run-pass/issue-11736.rs
@@ -16,13 +16,13 @@ use std::collections::Bitv;
 fn main() {
     // Generate sieve of Eratosthenes for n up to 1e6
     let n = 1000000u;
-    let sieve = Bitv::with_capacity(n+1, true);
+    let mut sieve = Bitv::with_capacity(n+1, true);
     let limit: uint = (n as f32).sqrt() as uint;
     for i in range(2, limit+1) {
         if sieve[i] {
             let mut j = 0;
             while i*i + j*i <= n {
-                sieve[i*i+j*i] = false;
+                sieve.set(i*i+j*i, false);
                 j += 1;
             }
         }
diff --git a/src/test/run-pass/issue2378c.rs b/src/test/run-pass/issue2378c.rs
deleted file mode 100644
index c453a538c7e..00000000000
--- a/src/test/run-pass/issue2378c.rs
+++ /dev/null
@@ -1,23 +0,0 @@
-// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-// aux-build:issue2378a.rs
-// aux-build:issue2378b.rs
-
-extern crate issue2378a;
-extern crate issue2378b;
-
-use issue2378a::{just};
-use issue2378b::{two_maybes};
-
-pub fn main() {
-    let x = two_maybes{a: just(3i), b: just(5i)};
-    assert_eq!(x[0u], (3, 5));
-}
diff --git a/src/test/run-pass/operator-overloading.rs b/src/test/run-pass/operator-overloading.rs
index 00e19b8481f..a36d8132b26 100644
--- a/src/test/run-pass/operator-overloading.rs
+++ b/src/test/run-pass/operator-overloading.rs
@@ -43,8 +43,12 @@ impl ops::Not<Point> for Point {
 }
 
 impl ops::Index<bool,int> for Point {
-    fn index(&self, x: &bool) -> int {
-        if *x { self.x } else { self.y }
+    fn index<'a>(&'a self, x: &bool) -> &'a int {
+        if *x {
+            &self.x
+        } else {
+            &self.y
+        }
     }
 }
 
diff --git a/src/test/run-pass/overload-index-operator.rs b/src/test/run-pass/overload-index-operator.rs
index de5456ef1c0..6b1ac0b821c 100644
--- a/src/test/run-pass/overload-index-operator.rs
+++ b/src/test/run-pass/overload-index-operator.rs
@@ -31,10 +31,10 @@ impl<K,V> AssociationList<K,V> {
 }
 
 impl<K:PartialEq,V:Clone> Index<K,V> for AssociationList<K,V> {
-    fn index(&self, index: &K) -> V {
+    fn index<'a>(&'a self, index: &K) -> &'a V {
         for pair in self.pairs.iter() {
             if pair.key == *index {
-                return pair.value.clone();
+                return &pair.value
             }
         }
         fail!("No value found for key: {:?}", index);
diff --git a/src/test/run-pass/overloaded-index.rs b/src/test/run-pass/overloaded-index.rs
new file mode 100644
index 00000000000..9d7c068cccd
--- /dev/null
+++ b/src/test/run-pass/overloaded-index.rs
@@ -0,0 +1,53 @@
+// 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.
+
+struct Foo {
+    x: int,
+    y: int,
+}
+
+impl Index<int,int> for Foo {
+    fn index<'a>(&'a self, z: &int) -> &'a int {
+        if *z == 0 {
+            &self.x
+        } else {
+            &self.y
+        }
+    }
+}
+
+impl IndexMut<int,int> for Foo {
+    fn index_mut<'a>(&'a mut self, z: &int) -> &'a mut int {
+        if *z == 0 {
+            &mut self.x
+        } else {
+            &mut self.y
+        }
+    }
+}
+
+fn main() {
+    let mut f = Foo {
+        x: 1,
+        y: 2,
+    };
+    assert_eq!(f[1], 2);
+    f[0] = 3;
+    assert_eq!(f[0], 3);
+    {
+        let p = &mut f[1];
+        *p = 4;
+    }
+    {
+        let p = &f[1];
+        assert_eq!(*p, 4);
+    }
+}
+