auto merge of #6373 : nikomatsakis/rust/issue-6355-perf-regression, r=graydon

Fix #6355 and #6272---we were not giving the correct index to the derefs that occur as part of the rooting process, resulting in extra copies and generally bogus behavior. Haven't quite produced the right test for this, but I thought I'd push the fix in the meantime. Test will follow shortly.

r? @graydon

6 files changed, 76 insertions, 35 deletions

diff --git a/src/librustc/middle/borrowck/gather_loans/mod.rs b/src/librustc/middle/borrowck/gather_loans/mod.rs
index 5f3c5d977fe..94a029911a8 100644
--- a/src/librustc/middle/borrowck/gather_loans/mod.rs
+++ b/src/librustc/middle/borrowck/gather_loans/mod.rs
@@ -260,7 +260,7 @@ pub impl GatherLoanCtxt {
                                              r)
                     }
                     ty::AutoBorrowVec(r, m) | ty::AutoBorrowVecRef(r, m) => {
-                        let cmt_index = mcx.cat_index(expr, cmt);
+                        let cmt_index = mcx.cat_index(expr, cmt, autoderefs+1);
                         self.guarantee_valid(expr.id,
                                              expr.span,
                                              cmt_index,
@@ -574,7 +574,7 @@ pub impl GatherLoanCtxt {
                   let (slice_mutbl, slice_r) =
                       self.vec_slice_info(slice_pat, slice_ty);
                   let mcx = self.bccx.mc_ctxt();
-                  let cmt_index = mcx.cat_index(slice_pat, cmt);
+                  let cmt_index = mcx.cat_index(slice_pat, cmt, 0);
                   self.guarantee_valid(pat.id, pat.span,
                                        cmt_index, slice_mutbl, slice_r);
               }
diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs
index 68e70d245f7..75acc2d9511 100644
--- a/src/librustc/middle/borrowck/mod.rs
+++ b/src/librustc/middle/borrowck/mod.rs
@@ -184,6 +184,16 @@ pub type LoanMap = @mut HashMap<ast::node_id, @Loan>;
 //
 // Note that there is no entry with derefs:3---the type of that expression
 // is T, which is not a box.
+//
+// Note that implicit dereferences also occur with indexing of `@[]`,
+// `@str`, etc.  The same rules apply. So, for example, given a
+// variable `x` of type `@[@[...]]`, if I have an instance of the
+// expression `x[0]` which is then auto-slice'd, there would be two
+// potential entries in the root map, both with the id of the `x[0]`
+// expression. The entry with `derefs==0` refers to the deref of `x`
+// used as part of evaluating `x[0]`. The entry with `derefs==1`
+// refers to the deref of the `x[0]` that occurs as part of the
+// auto-slice.
 #[deriving(Eq, IterBytes)]
 pub struct root_map_key {
     id: ast::node_id,
@@ -605,7 +615,7 @@ pub impl BorrowckCtxt {
                 }
             }
 
-            LpExtend(lp_base, _, LpInterior(mc::interior_field(fld, _))) => {
+            LpExtend(lp_base, _, LpInterior(mc::interior_field(fld))) => {
                 self.append_loan_path_to_str_from_interior(lp_base, out);
                 str::push_char(out, '.');
                 str::push_str(out, *self.tcx.sess.intr().get(fld));
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index 26992388b29..0e819c66f09 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -66,7 +66,7 @@ pub enum categorization {
     cat_local(ast::node_id),           // local variable
     cat_arg(ast::node_id),             // formal argument
     cat_deref(cmt, uint, ptr_kind),    // deref of a ptr
-    cat_interior(cmt, interior_kind),          // something interior
+    cat_interior(cmt, interior_kind),  // something interior
     cat_discr(cmt, ast::node_id),      // match discriminant (see preserve())
     cat_self(ast::node_id),            // explicit `self`
 }
@@ -94,8 +94,7 @@ pub enum interior_kind {
     interior_anon_field,             // anonymous field (in e.g.
                                      // struct Foo(int, int);
     interior_variant(ast::def_id),   // internals to a variant of given enum
-    interior_field(ast::ident,       // name of field
-                   ast::mutability), // declared mutability of field
+    interior_field(ast::ident),      // name of field
     interior_index(ty::t,            // type of vec/str/etc being deref'd
                    ast::mutability)  // mutability of vec content
 }
@@ -395,8 +394,7 @@ pub impl mem_categorization_ctxt {
             assert!(!self.method_map.contains_key(&expr.id));
 
             let base_cmt = self.cat_expr(base);
-            self.cat_field(expr, base_cmt, f_name,
-                           self.expr_ty(expr), expr.id)
+            self.cat_field(expr, base_cmt, f_name, self.expr_ty(expr))
           }
 
           ast::expr_index(base, _) => {
@@ -405,7 +403,7 @@ pub impl mem_categorization_ctxt {
             }
 
             let base_cmt = self.cat_expr(base);
-            self.cat_index(expr, base_cmt)
+            self.cat_index(expr, base_cmt, 0)
           }
 
           ast::expr_path(_) => {
@@ -579,16 +577,12 @@ pub impl mem_categorization_ctxt {
                              node: N,
                              base_cmt: cmt,
                              f_name: ast::ident,
-                             f_ty: ty::t,
-                             field_id: ast::node_id) -> cmt {
-        let f_mutbl = m_imm;
-        let m = self.inherited_mutability(base_cmt.mutbl, f_mutbl);
-        let f_interior = interior_field(f_name, f_mutbl);
+                             f_ty: ty::t) -> cmt {
         @cmt_ {
             id: node.id(),
             span: node.span(),
-            cat: cat_interior(base_cmt, f_interior),
-            mutbl: m,
+            cat: cat_interior(base_cmt, interior_field(f_name)),
+            mutbl: base_cmt.mutbl.inherit(),
             ty: f_ty
         }
     }
@@ -670,7 +664,39 @@ pub impl mem_categorization_ctxt {
 
     fn cat_index<N:ast_node>(&self,
                              elt: N,
-                             base_cmt: cmt) -> cmt {
+                             base_cmt: cmt,
+                             derefs: uint) -> cmt {
+        //! Creates a cmt for an indexing operation (`[]`); this
+        //! indexing operation may occurs as part of an
+        //! AutoBorrowVec, which when converting a `~[]` to an `&[]`
+        //! effectively takes the address of the 0th element.
+        //!
+        //! One subtle aspect of indexing that may not be
+        //! immediately obvious: for anything other than a fixed-length
+        //! vector, an operation like `x[y]` actually consists of two
+        //! disjoint (from the point of view of borrowck) operations.
+        //! The first is a deref of `x` to create a pointer `p` that points
+        //! at the first element in the array. The second operation is
+        //! an index which adds `y*sizeof(T)` to `p` to obtain the
+        //! pointer to `x[y]`. `cat_index` will produce a resulting
+        //! cmt containing both this deref and the indexing,
+        //! presuming that `base_cmt` is not of fixed-length type.
+        //!
+        //! In the event that a deref is needed, the "deref count"
+        //! is taken from the parameter `derefs`. See the comment
+        //! on the def'n of `root_map_key` in borrowck/mod.rs
+        //! for more details about deref counts; the summary is
+        //! that `derefs` should be 0 for an explicit indexing
+        //! operation and N+1 for an indexing that is part of
+        //! an auto-adjustment, where N is the number of autoderefs
+        //! in that adjustment.
+        //!
+        //! # Parameters
+        //! - `elt`: the AST node being indexed
+        //! - `base_cmt`: the cmt of `elt`
+        //! - `derefs`: the deref number to be used for
+        //!   the implicit index deref, if any (see above)
+
         let mt = match ty::index(base_cmt.ty) {
           Some(mt) => mt,
           None => {
@@ -698,7 +724,7 @@ pub impl mem_categorization_ctxt {
             let deref_cmt = @cmt_ {
                 id:elt.id(),
                 span:elt.span(),
-                cat:cat_deref(base_cmt, 0u, ptr),
+                cat:cat_deref(base_cmt, derefs, ptr),
                 mutbl:m,
                 ty:mt.ty
             };
@@ -854,8 +880,7 @@ pub impl mem_categorization_ctxt {
             // {f1: p1, ..., fN: pN}
             for field_pats.each |fp| {
                 let field_ty = self.pat_ty(fp.pat); // see (*)
-                let cmt_field = self.cat_field(pat, cmt, fp.ident,
-                                               field_ty, pat.id);
+                let cmt_field = self.cat_field(pat, cmt, fp.ident, field_ty);
                 self.cat_pattern(cmt_field, fp.pat, op);
             }
           }
@@ -878,8 +903,8 @@ pub impl mem_categorization_ctxt {
           }
 
           ast::pat_vec(ref before, slice, ref after) => {
+              let elt_cmt = self.cat_index(pat, cmt, 0);
               for before.each |&before_pat| {
-                  let elt_cmt = self.cat_index(pat, cmt);
                   self.cat_pattern(elt_cmt, before_pat, op);
               }
               for slice.each |&slice_pat| {
@@ -888,7 +913,6 @@ pub impl mem_categorization_ctxt {
                   self.cat_pattern(slice_cmt, slice_pat, op);
               }
               for after.each |&after_pat| {
-                  let elt_cmt = self.cat_index(pat, cmt);
                   self.cat_pattern(elt_cmt, after_pat, op);
               }
           }
@@ -1110,7 +1134,7 @@ pub fn ptr_sigil(ptr: ptr_kind) -> ~str {
 impl Repr for interior_kind {
     fn repr(&self, tcx: ty::ctxt) -> ~str {
         match *self {
-            interior_field(fld, _) => copy *tcx.sess.str_of(fld),
+            interior_field(fld) => copy *tcx.sess.str_of(fld),
             interior_index(*) => ~"[]",
             interior_tuple => ~"()",
             interior_anon_field => ~"<anonymous field>",
diff --git a/src/librustc/middle/trans/_match.rs b/src/librustc/middle/trans/_match.rs
index 1443a7ef304..f94e646d3e2 100644
--- a/src/librustc/middle/trans/_match.rs
+++ b/src/librustc/middle/trans/_match.rs
@@ -885,7 +885,8 @@ pub fn extract_vec_elems(bcx: block,
                       -> ExtractedBlock {
     let _icx = bcx.insn_ctxt("match::extract_vec_elems");
     let vec_datum = match_datum(bcx, val, pat_id);
-    let (bcx, base, len) = vec_datum.get_vec_base_and_len(bcx, pat_span, pat_id);
+    let (bcx, base, len) = vec_datum.get_vec_base_and_len(bcx, pat_span,
+                                                          pat_id, 0);
     let vt = tvec::vec_types(bcx, node_id_type(bcx, pat_id));
 
     let mut elems = do vec::from_fn(elem_count) |i| {
diff --git a/src/librustc/middle/trans/datum.rs b/src/librustc/middle/trans/datum.rs
index 3b885ae9b94..64b29fd8573 100644
--- a/src/librustc/middle/trans/datum.rs
+++ b/src/librustc/middle/trans/datum.rs
@@ -735,13 +735,14 @@ pub impl Datum {
     fn get_vec_base_and_len(&self,
                             mut bcx: block,
                             span: span,
-                            expr_id: ast::node_id)
+                            expr_id: ast::node_id,
+                            derefs: uint)
                             -> (block, ValueRef, ValueRef) {
         //! Converts a vector into the slice pair. Performs rooting
         //! and write guards checks.
 
         // only imp't for @[] and @str, but harmless
-        bcx = write_guard::root_and_write_guard(self, bcx, span, expr_id, 0);
+        bcx = write_guard::root_and_write_guard(self, bcx, span, expr_id, derefs);
         let (base, len) = self.get_vec_base_and_len_no_root(bcx);
         (bcx, base, len)
     }
diff --git a/src/librustc/middle/trans/expr.rs b/src/librustc/middle/trans/expr.rs
index 29227b7c95a..698c30a6a42 100644
--- a/src/librustc/middle/trans/expr.rs
+++ b/src/librustc/middle/trans/expr.rs
@@ -144,10 +144,9 @@ use middle::trans::tvec;
 use middle::trans::type_of;
 use middle::ty::struct_fields;
 use middle::ty::{AutoDerefRef, AutoAddEnv};
-use middle::ty::{AutoPtr, AutoBorrowVec, AutoBorrowVecRef, AutoBorrowFn};
-use middle::ty;
 use middle::ty::{AutoPtr, AutoBorrowVec, AutoBorrowVecRef, AutoBorrowFn,
                  AutoDerefRef, AutoAddEnv, AutoUnsafe};
+use middle::ty;
 use util::common::indenter;
 use util::ppaux::Repr;
 
@@ -215,10 +214,12 @@ pub fn trans_to_datum(bcx: block, expr: @ast::expr) -> DatumBlock {
                     unpack_datum!(bcx, auto_ref(bcx, datum))
                 }
                 Some(AutoBorrowVec(*)) => {
-                    unpack_datum!(bcx, auto_slice(bcx, expr, datum))
+                    unpack_datum!(bcx, auto_slice(bcx, adj.autoderefs,
+                                                  expr, datum))
                 }
                 Some(AutoBorrowVecRef(*)) => {
-                    unpack_datum!(bcx, auto_slice_and_ref(bcx, expr, datum))
+                    unpack_datum!(bcx, auto_slice_and_ref(bcx, adj.autoderefs,
+                                                          expr, datum))
                 }
                 Some(AutoBorrowFn(*)) => {
                     let adjusted_ty = ty::adjust_ty(bcx.tcx(), expr.span,
@@ -246,7 +247,10 @@ pub fn trans_to_datum(bcx: block, expr: @ast::expr) -> DatumBlock {
                                   mode: datum.mode, source: datum.source}}
     }
 
-    fn auto_slice(bcx: block, expr: @ast::expr, datum: Datum) -> DatumBlock {
+    fn auto_slice(bcx: block,
+                  autoderefs: uint,
+                  expr: @ast::expr,
+                  datum: Datum) -> DatumBlock {
         // This is not the most efficient thing possible; since slices
         // are two words it'd be better if this were compiled in
         // 'dest' mode, but I can't find a nice way to structure the
@@ -256,9 +260,8 @@ pub fn trans_to_datum(bcx: block, expr: @ast::expr) -> DatumBlock {
         let tcx = bcx.tcx();
         let unit_ty = ty::sequence_element_type(tcx, datum.ty);
 
-        // FIXME(#6272) need to distinguish "auto-slice" from explicit index?
         let (bcx, base, len) =
-            datum.get_vec_base_and_len(bcx, expr.span, expr.id);
+            datum.get_vec_base_and_len(bcx, expr.span, expr.id, autoderefs+1);
 
         // this type may have a different region/mutability than the
         // real one, but it will have the same runtime representation
@@ -292,9 +295,10 @@ pub fn trans_to_datum(bcx: block, expr: @ast::expr) -> DatumBlock {
     }
 
     fn auto_slice_and_ref(bcx: block,
+                          autoderefs: uint,
                           expr: @ast::expr,
                           datum: Datum) -> DatumBlock {
-        let DatumBlock { bcx, datum } = auto_slice(bcx, expr, datum);
+        let DatumBlock { bcx, datum } = auto_slice(bcx, autoderefs, expr, datum);
         auto_ref(bcx, datum)
     }
 }
@@ -913,7 +917,8 @@ fn trans_lvalue_unadjusted(bcx: block, expr: @ast::expr) -> DatumBlock {
         base::maybe_name_value(bcx.ccx(), scaled_ix, ~"scaled_ix");
 
         let mut (bcx, base, len) =
-            base_datum.get_vec_base_and_len(bcx, index_expr.span, index_expr.id);
+            base_datum.get_vec_base_and_len(bcx, index_expr.span,
+                                            index_expr.id, 0);
 
         if ty::type_is_str(base_ty) {
             // acccount for null terminator in the case of string