rustc: Switch mutability from being a type constructor to a field annotation

7 files changed, 327 insertions, 280 deletions

diff --git a/src/comp/front/ast.rs b/src/comp/front/ast.rs
index 1970f788..e519d03b 100644
--- a/src/comp/front/ast.rs
+++ b/src/comp/front/ast.rs
@@ -168,7 +168,6 @@ tag unop {
     bitnot;
     not;
     neg;
-    _mutable;
 }
 
 fn unop_to_str(unop op) -> str {
@@ -178,7 +177,6 @@ fn unop_to_str(unop op) -> str {
         case (bitnot) {ret "~";}
         case (not) {ret "!";}
         case (neg) {ret "-";}
-        case (_mutable) {ret "mutable";}
     }
 }
 
@@ -215,7 +213,7 @@ type field = rec(mutability mut, ident ident, @expr expr);
 
 type expr = spanned[expr_];
 tag expr_ {
-    expr_vec(vec[@expr], ann);
+    expr_vec(vec[@expr], mutability, ann);
     expr_tup(vec[elt], ann);
     expr_rec(vec[field], option.t[@expr], ann);
     expr_call(@expr, vec[@expr], ann);
@@ -263,7 +261,8 @@ tag lit_ {
 // NB: If you change this, you'll probably want to change the corresponding
 // type structure in middle/ty.rs as well.
 
-type ty_field = rec(ident ident, @ty ty);
+type mt = rec(@ty ty, mutability mut);
+type ty_field = rec(ident ident, mt mt);
 type ty_arg = rec(mode mode, @ty ty);
 // TODO: effect
 type ty_method = rec(proto proto, ident ident,
@@ -277,16 +276,15 @@ tag ty_ {
     ty_machine(util.common.ty_mach);
     ty_char;
     ty_str;
-    ty_box(@ty);
-    ty_vec(@ty);
+    ty_box(mt);
+    ty_vec(mt);
     ty_port(@ty);
     ty_chan(@ty);
-    ty_tup(vec[@ty]);
+    ty_tup(vec[mt]);
     ty_rec(vec[ty_field]);
     ty_fn(proto, vec[ty_arg], @ty);        // TODO: effect
     ty_obj(vec[ty_method]);
     ty_path(path, option.t[def]);
-    ty_mutable(@ty);
     ty_type;
     ty_constr(@ty, vec[@constr]);
 }
diff --git a/src/comp/front/parser.rs b/src/comp/front/parser.rs
index db09301c..71f0f2d8 100644
--- a/src/comp/front/parser.rs
+++ b/src/comp/front/parser.rs
@@ -189,6 +189,11 @@ impure fn parse_ty_fn(ast.proto proto, parser p,
         if (p.peek() == token.BINOP(token.AND)) {
             p.bump();
             mode = ast.alias;
+
+            if (p.peek() == token.MUTABLE) {
+                p.bump();
+                // TODO: handle mutable alias args
+            }
         } else {
             mode = ast.val;
         }
@@ -262,10 +267,16 @@ impure fn parse_ty_obj(parser p, &mutable ast.span hi) -> ast.ty_ {
     ret ast.ty_obj(meths.node);
 }
 
+impure fn parse_mt(parser p) -> ast.mt {
+    auto mut = parse_mutability(p);
+    auto t = parse_ty(p);
+    ret rec(ty=t, mut=mut);
+}
+
 impure fn parse_ty_field(parser p) -> ast.ty_field {
-    auto ty = parse_ty(p);
+    auto mt = parse_mt(p);
     auto id = parse_ident(p);
-    ret rec(ident=id, ty=ty);
+    ret rec(ident=id, mt=mt);
 }
 
 impure fn parse_constr_arg(parser p) -> @ast.constr_arg {
@@ -360,25 +371,25 @@ impure fn parse_ty(parser p) -> @ast.ty {
 
         case (token.AT) {
             p.bump();
-            auto t0 = parse_ty(p);
-            hi = t0.span;
-            t = ast.ty_box(t0);
+            auto mt = parse_mt(p);
+            hi = mt.ty.span;
+            t = ast.ty_box(mt);
         }
 
         case (token.VEC) {
             p.bump();
             expect(p, token.LBRACKET);
-            t = ast.ty_vec(parse_ty(p));
+            t = ast.ty_vec(parse_mt(p));
             hi = p.get_span();
             expect(p, token.RBRACKET);
         }
 
         case (token.TUP) {
             p.bump();
-            auto f = parse_ty; // FIXME: trans_const_lval bug
-            auto elems = parse_seq[@ast.ty] (token.LPAREN,
-                                             token.RPAREN,
-                                             some(token.COMMA), f, p);
+            auto f = parse_mt; // FIXME: trans_const_lval bug
+            auto elems = parse_seq[ast.mt] (token.LPAREN,
+                                            token.RPAREN,
+                                            some(token.COMMA), f, p);
             hi = elems.span;
             t = ast.ty_tup(elems.node);
         }
@@ -395,13 +406,6 @@ impure fn parse_ty(parser p) -> @ast.ty {
             t = ast.ty_rec(elems.node);
         }
 
-        case (token.MUTABLE) {
-            p.bump();
-            auto t0 = parse_ty(p);
-            hi = t0.span;
-            t = ast.ty_mutable(t0);
-        }
-
         case (token.FN) {
             auto flo = p.get_span();
             p.bump();
@@ -463,20 +467,22 @@ impure fn parse_arg(parser p) -> ast.arg {
     if (p.peek() == token.BINOP(token.AND)) {
         m = ast.alias;
         p.bump();
+
+        if (p.peek() == token.MUTABLE) {
+            // TODO: handle mutable alias args
+            p.bump();
+        }
     }
     let @ast.ty t = parse_ty(p);
     let ast.ident i = parse_ident(p);
     ret rec(mode=m, ty=t, ident=i, id=p.next_def_id());
 }
 
-impure fn parse_seq[T](token.token bra,
-                      token.token ket,
-                      option.t[token.token] sep,
-                      (impure fn(parser) -> T) f,
-                      parser p) -> util.common.spanned[vec[T]] {
+impure fn parse_seq_to_end[T](token.token ket,
+                              option.t[token.token] sep,
+                              (impure fn(parser) -> T) f,
+                              parser p) -> vec[T] {
     let bool first = true;
-    auto lo = p.get_span();
-    expect(p, bra);
     let vec[T] v = vec();
     while (p.peek() != ket) {
         alt(sep) {
@@ -494,9 +500,20 @@ impure fn parse_seq[T](token.token bra,
         let T t = f(p);
         v += vec(t);
     }
-    auto hi = p.get_span();
     expect(p, ket);
-    ret spanned(lo, hi, v);
+    ret v;
+}
+
+impure fn parse_seq[T](token.token bra,
+                      token.token ket,
+                      option.t[token.token] sep,
+                      (impure fn(parser) -> T) f,
+                      parser p) -> util.common.spanned[vec[T]] {
+    auto lo = p.get_span();
+    expect(p, bra);
+    auto result = parse_seq_to_end[T](ket, sep, f, p);
+    auto hi = p.get_span();
+    ret spanned(lo, hi, result);
 }
 
 impure fn parse_lit(parser p) -> ast.lit {
@@ -667,12 +684,15 @@ impure fn parse_bottom_expr(parser p) -> @ast.expr {
         case (token.VEC) {
             p.bump();
             auto pf = parse_expr;
-            auto es = parse_seq[@ast.expr](token.LPAREN,
-                                           token.RPAREN,
-                                           some(token.COMMA),
-                                           pf, p);
-            hi = es.span;
-            ex = ast.expr_vec(es.node, ast.ann_none);
+
+            expect(p, token.LPAREN);
+            auto mut = parse_mutability(p);
+
+            auto es = parse_seq_to_end[@ast.expr](token.RPAREN,
+                                                  some(token.COMMA),
+                                                  pf, p);
+            hi = p.get_span();
+            ex = ast.expr_vec(es, mut, ast.ann_none);
         }
 
         case (token.REC) {
@@ -1004,13 +1024,6 @@ impure fn parse_prefix_expr(parser p) -> @ast.expr {
             ex = ast.expr_unary(ast.box, e, ast.ann_none);
         }
 
-        case (token.MUTABLE) {
-            p.bump();
-            auto e = parse_prefix_expr(p);
-            hi = e.span;
-            ex = ast.expr_unary(ast._mutable, e, ast.ann_none);
-        }
-
         case (_) {
             ret parse_dot_or_call_expr(p);
         }
@@ -1558,7 +1571,7 @@ fn stmt_ends_with_semi(@ast.stmt stmt) -> bool {
         }
         case (ast.stmt_expr(?e)) {
             alt (e.node) {
-                case (ast.expr_vec(_,_))        { ret true; }
+                case (ast.expr_vec(_,_,_))      { ret true; }
                 case (ast.expr_tup(_,_))        { ret true; }
                 case (ast.expr_rec(_,_,_))      { ret true; }
                 case (ast.expr_call(_,_,_))     { ret true; }
@@ -1722,6 +1735,7 @@ impure fn parse_item_fn_or_iter(parser p, ast.effect eff) -> @ast.item {
 
 
 impure fn parse_obj_field(parser p) -> ast.obj_field {
+    auto mut = parse_mutability(p); // TODO: store this, use it in typeck
     auto ty = parse_ty(p);
     auto ident = parse_ident(p);
     ret rec(ty=ty, ident=ident, id=p.next_def_id(), ann=ast.ann_none);
diff --git a/src/comp/middle/fold.rs b/src/comp/middle/fold.rs
index e2f2e192..703c7ea4 100644
--- a/src/comp/middle/fold.rs
+++ b/src/comp/middle/fold.rs
@@ -28,6 +28,7 @@ import front.ast.arm;
 import front.ast.def;
 import front.ast.def_id;
 import front.ast.ann;
+import front.ast.mt;
 
 import std._uint;
 import std._vec;
@@ -46,10 +47,10 @@ type ast_fold[ENV] =
      (fn(&ENV e, &span sp, ty_mach tm) -> @ty)    fold_ty_machine,
      (fn(&ENV e, &span sp) -> @ty)                fold_ty_char,
      (fn(&ENV e, &span sp) -> @ty)                fold_ty_str,
-     (fn(&ENV e, &span sp, @ty t) -> @ty)         fold_ty_box,
-     (fn(&ENV e, &span sp, @ty t) -> @ty)         fold_ty_vec,
+     (fn(&ENV e, &span sp, &mt tm) -> @ty)        fold_ty_box,
+     (fn(&ENV e, &span sp, &mt tm) -> @ty)        fold_ty_vec,
 
-     (fn(&ENV e, &span sp, vec[@ty] elts) -> @ty) fold_ty_tup,
+     (fn(&ENV e, &span sp, vec[mt] elts) -> @ty)  fold_ty_tup,
 
      (fn(&ENV e, &span sp,
          vec[ast.ty_field] elts) -> @ty)          fold_ty_rec,
@@ -65,13 +66,13 @@ type ast_fold[ENV] =
      (fn(&ENV e, &span sp, ast.path p,
          &option.t[def] d) -> @ty)                fold_ty_path,
 
-     (fn(&ENV e, &span sp, @ty t) -> @ty)         fold_ty_mutable,
      (fn(&ENV e, &span sp, @ty t) -> @ty)         fold_ty_chan,
      (fn(&ENV e, &span sp, @ty t) -> @ty)         fold_ty_port,
 
      // Expr folds.
      (fn(&ENV e, &span sp,
-         vec[@expr] es, ann a) -> @expr)          fold_expr_vec,
+         vec[@expr] es, ast.mutability mut,
+         ann a) -> @expr)                         fold_expr_vec,
 
      (fn(&ENV e, &span sp,
          vec[ast.elt] es, ann a) -> @expr)        fold_expr_tup,
@@ -343,20 +344,21 @@ fn fold_ty[ENV](&ENV env, ast_fold[ENV] fld, @ty t) -> @ty {
         case (ast.ty_char) { ret fld.fold_ty_char(env_, t.span); }
         case (ast.ty_str) { ret fld.fold_ty_str(env_, t.span); }
 
-        case (ast.ty_box(?ty)) {
-            auto ty_ = fold_ty(env, fld, ty);
-            ret fld.fold_ty_box(env_, t.span, ty_);
+        case (ast.ty_box(?tm)) {
+            auto ty_ = fold_ty(env, fld, tm.ty);
+            ret fld.fold_ty_box(env_, t.span, rec(ty=ty_, mut=tm.mut));
         }
 
-        case (ast.ty_vec(?ty)) {
-            auto ty_ = fold_ty(env, fld, ty);
-            ret fld.fold_ty_vec(env_, t.span, ty_);
+        case (ast.ty_vec(?tm)) {
+            auto ty_ = fold_ty(env, fld, tm.ty);
+            ret fld.fold_ty_vec(env_, t.span, rec(ty=ty_, mut=tm.mut));
         }
 
         case (ast.ty_tup(?elts)) {
-            let vec[@ty] elts_ = vec();
-            for (@ty elt in elts) {
-                _vec.push[@ty](elts_,fold_ty(env, fld, elt));
+            let vec[mt] elts_ = vec();
+            for (mt elt in elts) {
+                auto ty_ = fold_ty(env, fld, elt.ty);
+                _vec.push[mt](elts_, rec(ty=ty_, mut=elt.mut));
             }
             ret fld.fold_ty_tup(env_, t.span, elts_);
         }
@@ -364,8 +366,9 @@ fn fold_ty[ENV](&ENV env, ast_fold[ENV] fld, @ty t) -> @ty {
         case (ast.ty_rec(?flds)) {
             let vec[ast.ty_field] flds_ = vec();
             for (ast.ty_field f in flds) {
+                auto ty_ = fold_ty(env, fld, f.mt.ty);
                 _vec.push[ast.ty_field]
-                    (flds_, rec(ty=fold_ty(env, fld, f.ty) with f));
+                    (flds_, rec(mt=rec(ty=ty_, mut=f.mt.mut) with f));
             }
             ret fld.fold_ty_rec(env_, t.span, flds_);
         }
@@ -391,11 +394,6 @@ fn fold_ty[ENV](&ENV env, ast_fold[ENV] fld, @ty t) -> @ty {
             ret fld.fold_ty_path(env_, t.span, pth_, ref_opt);
         }
 
-        case (ast.ty_mutable(?ty)) {
-            auto ty_ = fold_ty(env, fld, ty);
-            ret fld.fold_ty_mutable(env_, t.span, ty_);
-        }
-
         case (ast.ty_fn(?proto, ?inputs, ?output)) {
             ret fold_ty_fn(env_, fld, t.span, proto, inputs, output);
         }
@@ -516,9 +514,9 @@ fn fold_expr[ENV](&ENV env, ast_fold[ENV] fld, &@expr e) -> @expr {
     }
 
     alt (e.node) {
-        case (ast.expr_vec(?es, ?t)) {
+        case (ast.expr_vec(?es, ?mut, ?t)) {
             auto ees = fold_exprs(env_, fld, es);
-            ret fld.fold_expr_vec(env_, e.span, ees, t);
+            ret fld.fold_expr_vec(env_, e.span, ees, mut, t);
         }
 
         case (ast.expr_tup(?es, ?t)) {
@@ -1077,16 +1075,16 @@ fn identity_fold_ty_str[ENV](&ENV env, &span sp) -> @ty {
     ret @respan(sp, ast.ty_str);
 }
 
-fn identity_fold_ty_box[ENV](&ENV env, &span sp, @ty t) -> @ty {
-    ret @respan(sp, ast.ty_box(t));
+fn identity_fold_ty_box[ENV](&ENV env, &span sp, &mt tm) -> @ty {
+    ret @respan(sp, ast.ty_box(tm));
 }
 
-fn identity_fold_ty_vec[ENV](&ENV env, &span sp, @ty t) -> @ty {
-    ret @respan(sp, ast.ty_vec(t));
+fn identity_fold_ty_vec[ENV](&ENV env, &span sp, &mt tm) -> @ty {
+    ret @respan(sp, ast.ty_vec(tm));
 }
 
 fn identity_fold_ty_tup[ENV](&ENV env, &span sp,
-                             vec[@ty] elts) -> @ty {
+                             vec[mt] elts) -> @ty {
     ret @respan(sp, ast.ty_tup(elts));
 }
 
@@ -1112,10 +1110,6 @@ fn identity_fold_ty_path[ENV](&ENV env, &span sp, ast.path p,
     ret @respan(sp, ast.ty_path(p, d));
 }
 
-fn identity_fold_ty_mutable[ENV](&ENV env, &span sp, @ty t) -> @ty {
-    ret @respan(sp, ast.ty_mutable(t));
-}
-
 fn identity_fold_ty_chan[ENV](&ENV env, &span sp, @ty t) -> @ty {
     ret @respan(sp, ast.ty_chan(t));
 }
@@ -1127,8 +1121,8 @@ fn identity_fold_ty_port[ENV](&ENV env, &span sp, @ty t) -> @ty {
 // Expr identities.
 
 fn identity_fold_expr_vec[ENV](&ENV env, &span sp, vec[@expr] es,
-                               ann a) -> @expr {
-    ret @respan(sp, ast.expr_vec(es, a));
+                               ast.mutability mut, ann a) -> @expr {
+    ret @respan(sp, ast.expr_vec(es, mut, a));
 }
 
 fn identity_fold_expr_tup[ENV](&ENV env, &span sp,
@@ -1528,11 +1522,10 @@ fn new_identity_fold[ENV]() -> ast_fold[ENV] {
          fold_ty_obj     = bind identity_fold_ty_obj[ENV](_,_,_),
          fold_ty_fn      = bind identity_fold_ty_fn[ENV](_,_,_,_,_),
          fold_ty_path    = bind identity_fold_ty_path[ENV](_,_,_,_),
-         fold_ty_mutable = bind identity_fold_ty_mutable[ENV](_,_,_),
          fold_ty_chan    = bind identity_fold_ty_chan[ENV](_,_,_),
          fold_ty_port    = bind identity_fold_ty_port[ENV](_,_,_),
 
-         fold_expr_vec    = bind identity_fold_expr_vec[ENV](_,_,_,_),
+         fold_expr_vec    = bind identity_fold_expr_vec[ENV](_,_,_,_,_),
          fold_expr_tup    = bind identity_fold_expr_tup[ENV](_,_,_,_),
          fold_expr_rec    = bind identity_fold_expr_rec[ENV](_,_,_,_,_),
          fold_expr_call   = bind identity_fold_expr_call[ENV](_,_,_,_,_),
diff --git a/src/comp/middle/trans.rs b/src/comp/middle/trans.rs
index f119681b..2ef619cb 100644
--- a/src/comp/middle/trans.rs
+++ b/src/comp/middle/trans.rs
@@ -614,23 +614,23 @@ fn type_of_inner(@crate_ctxt cx, @ty.t t, bool boxed) -> TypeRef {
                 llty = T_tag(cx.tn, size);
             }
         }
-        case (ty.ty_box(?t)) {
-            llty = T_ptr(T_box(type_of_inner(cx, t, true)));
+        case (ty.ty_box(?mt)) {
+            llty = T_ptr(T_box(type_of_inner(cx, mt.ty, true)));
         }
-        case (ty.ty_vec(?t)) {
-            llty = T_ptr(T_vec(type_of_inner(cx, t, true)));
+        case (ty.ty_vec(?mt)) {
+            llty = T_ptr(T_vec(type_of_inner(cx, mt.ty, true)));
         }
         case (ty.ty_tup(?elts)) {
             let vec[TypeRef] tys = vec();
-            for (@ty.t elt in elts) {
-                tys += vec(type_of_inner(cx, elt, boxed));
+            for (ty.mt elt in elts) {
+                tys += vec(type_of_inner(cx, elt.ty, boxed));
             }
             llty = T_struct(tys);
         }
         case (ty.ty_rec(?fields)) {
             let vec[TypeRef] tys = vec();
             for (ty.field f in fields) {
-                tys += vec(type_of_inner(cx, f.ty, boxed));
+                tys += vec(type_of_inner(cx, f.mt.ty, boxed));
             }
             llty = T_struct(tys);
         }
@@ -971,8 +971,7 @@ fn static_size_of_tag(@crate_ctxt cx, @ty.t t) -> uint {
     auto max_size = 0u;
     auto variants = tag_variants(cx, tid);
     for (ast.variant variant in variants) {
-        let vec[@ty.t] tys = variant_types(cx, variant);
-        auto tup_ty = ty.plain_ty(ty.ty_tup(tys));
+        auto tup_ty = ty.plain_tup_ty(variant_types(cx, variant));
 
         // Perform any type parameter substitutions.
         tup_ty = ty.substitute_ty_params(ty_params, subtys, tup_ty);
@@ -1021,12 +1020,16 @@ fn dynamic_size_of(@block_ctxt cx, @ty.t t) -> result {
             ret res(szptr.bcx, szptr.bcx.build.Load(szptr.val));
         }
         case (ty.ty_tup(?elts)) {
-            ret align_elements(cx, elts);
+            let vec[@ty.t] tys = vec();
+            for (ty.mt mt in elts) {
+                tys += vec(mt.ty);
+            }
+            ret align_elements(cx, tys);
         }
         case (ty.ty_rec(?flds)) {
             let vec[@ty.t] tys = vec();
             for (ty.field f in flds) {
-                tys += vec(f.ty);
+                tys += vec(f.mt.ty);
             }
             ret align_elements(cx, tys);
         }
@@ -1072,8 +1075,8 @@ fn dynamic_align_of(@block_ctxt cx, @ty.t t) -> result {
         case (ty.ty_tup(?elts)) {
             auto a = C_int(1);
             auto bcx = cx;
-            for (@ty.t e in elts) {
-                auto align = align_of(bcx, e);
+            for (ty.mt e in elts) {
+                auto align = align_of(bcx, e.ty);
                 bcx = align.bcx;
                 a = umax(bcx, a, align.val);
             }
@@ -1083,7 +1086,7 @@ fn dynamic_align_of(@block_ctxt cx, @ty.t t) -> result {
             auto a = C_int(1);
             auto bcx = cx;
             for (ty.field f in flds) {
-                auto align = align_of(bcx, f.ty);
+                auto align = align_of(bcx, f.mt.ty);
                 bcx = align.bcx;
                 a = umax(bcx, a, align.val);
             }
@@ -1183,7 +1186,7 @@ fn GEP_tup_like(@block_ctxt cx, @ty.t t,
     // flattened the incoming structure.
 
     auto s = split_type(t, ixs, 0u);
-    auto prefix_ty = plain_ty(ty.ty_tup(s.prefix));
+    auto prefix_ty = ty.plain_tup_ty(s.prefix);
     auto bcx = cx;
     auto sz = size_of(bcx, prefix_ty);
     bcx = sz.bcx;
@@ -1227,7 +1230,8 @@ fn GEP_tag(@block_ctxt cx,
 
         i += 1;
     }
-    auto tup_ty = ty.plain_ty(ty.ty_tup(true_arg_tys));
+
+    auto tup_ty = ty.plain_tup_ty(true_arg_tys);
 
     // Cast the blob pointer to the appropriate type, if we need to (i.e. if
     // the blob pointer isn't dynamically sized).
@@ -1267,8 +1271,8 @@ fn trans_raw_malloc(@block_ctxt cx, TypeRef llptr_ty, ValueRef llsize)
 fn trans_malloc_boxed(@block_ctxt cx, @ty.t t) -> result {
     // Synthesize a fake box type structurally so we have something
     // to measure the size of.
-    auto boxed_body = plain_ty(ty.ty_tup(vec(plain_ty(ty.ty_int), t)));
-    auto box_ptr = plain_ty(ty.ty_box(t));
+    auto boxed_body = ty.plain_tup_ty(vec(plain_ty(ty.ty_int), t));
+    auto box_ptr = ty.plain_box_ty(t);
     auto sz = size_of(cx, boxed_body);
     auto llty = type_of(cx.fcx.ccx, box_ptr);
     ret trans_raw_malloc(sz.bcx, llty, sz.val);
@@ -1566,7 +1570,7 @@ fn make_drop_glue(@block_ctxt cx, ValueRef v, @ty.t t) -> result {
                                         T_int(), C_int(0));
         }
 
-        case (ty.ty_box(?body_ty)) {
+        case (ty.ty_box(?body_mt)) {
             fn hit_zero(@block_ctxt cx, ValueRef v,
                         @ty.t body_ty) -> result {
                 auto body = cx.build.GEP(v,
@@ -1579,7 +1583,7 @@ fn make_drop_glue(@block_ctxt cx, ValueRef v, @ty.t t) -> result {
                 ret trans_non_gc_free(res.bcx, v);
             }
             ret decr_refcnt_and_if_zero(cx, v,
-                                        bind hit_zero(_, v, body_ty),
+                                        bind hit_zero(_, v, body_mt.ty),
                                         "free box",
                                         T_int(), C_int(0));
         }
@@ -1831,7 +1835,7 @@ fn iter_structural_ty_full(@block_ctxt cx,
         auto box_a_ptr = cx.build.Load(box_a_cell);
         auto box_b_ptr = cx.build.Load(box_b_cell);
         auto tnil = plain_ty(ty.ty_nil);
-        auto tbox = plain_ty(ty.ty_box(tnil));
+        auto tbox = ty.plain_box_ty(tnil);
 
         auto inner_cx = new_sub_block_ctxt(cx, "iter box");
         auto next_cx = new_sub_block_ctxt(cx, "next");
@@ -1846,15 +1850,15 @@ fn iter_structural_ty_full(@block_ctxt cx,
     alt (t.struct) {
         case (ty.ty_tup(?args)) {
             let int i = 0;
-            for (@ty.t arg in args) {
+            for (ty.mt arg in args) {
                 r = GEP_tup_like(r.bcx, t, av, vec(0, i));
                 auto elt_a = r.val;
                 r = GEP_tup_like(r.bcx, t, bv, vec(0, i));
                 auto elt_b = r.val;
                 r = f(r.bcx,
-                      load_scalar_or_boxed(r.bcx, elt_a, arg),
-                      load_scalar_or_boxed(r.bcx, elt_b, arg),
-                      arg);
+                      load_scalar_or_boxed(r.bcx, elt_a, arg.ty),
+                      load_scalar_or_boxed(r.bcx, elt_b, arg.ty),
+                      arg.ty);
                 i += 1;
             }
         }
@@ -1866,9 +1870,9 @@ fn iter_structural_ty_full(@block_ctxt cx,
                 r = GEP_tup_like(r.bcx, t, bv, vec(0, i));
                 auto llfld_b = r.val;
                 r = f(r.bcx,
-                      load_scalar_or_boxed(r.bcx, llfld_a, fld.ty),
-                      load_scalar_or_boxed(r.bcx, llfld_b, fld.ty),
-                      fld.ty);
+                      load_scalar_or_boxed(r.bcx, llfld_a, fld.mt.ty),
+                      load_scalar_or_boxed(r.bcx, llfld_b, fld.mt.ty),
+                      fld.mt.ty);
                 i += 1;
             }
         }
@@ -2106,8 +2110,8 @@ fn iter_sequence(@block_ctxt cx,
     }
 
     alt (t.struct) {
-        case (ty.ty_vec(?et)) {
-            ret iter_sequence_body(cx, v, et, f, false);
+        case (ty.ty_vec(?elt)) {
+            ret iter_sequence_body(cx, v, elt.ty, f, false);
         }
         case (ty.ty_str) {
             auto et = plain_ty(ty.ty_machine(common.ty_u8));
@@ -2397,9 +2401,6 @@ fn trans_unary(@block_ctxt cx, ast.unop op,
             }
             ret res(sub.bcx, val);
         }
-        case (ast._mutable) {
-            ret trans_expr(cx, e);
-        }
     }
     fail;
 }
@@ -2698,12 +2699,12 @@ fn autoderef(@block_ctxt cx, ValueRef v, @ty.t t) -> result {
 
     while (true) {
         alt (t1.struct) {
-            case (ty.ty_box(?inner)) {
+            case (ty.ty_box(?mt)) {
                 auto body = cx.build.GEP(v1,
                                          vec(C_int(0),
                                              C_int(abi.box_rc_field_body)));
-                t1 = inner;
-                v1 = load_scalar_or_boxed(cx, body, inner);
+                t1 = mt.ty;
+                v1 = load_scalar_or_boxed(cx, body, t1);
             }
             case (_) {
                 ret res(cx, v1);
@@ -2717,8 +2718,8 @@ fn autoderefed_ty(@ty.t t) -> @ty.t {
 
     while (true) {
         alt (t1.struct) {
-            case (ty.ty_box(?inner)) {
-                t1 = inner;
+            case (ty.ty_box(?mt)) {
+                t1 = mt.ty;
             }
             case (_) {
                 ret t1;
@@ -3483,7 +3484,7 @@ fn trans_field(@block_ctxt cx, &ast.span sp, @ast.expr base,
     r = autoderef(r.bcx, r.val, t);
     t = autoderefed_ty(t);
     alt (t.struct) {
-        case (ty.ty_tup(?fields)) {
+        case (ty.ty_tup(_)) {
             let uint ix = ty.field_num(cx.fcx.ccx.sess, sp, field);
             auto v = GEP_tup_like(r.bcx, t, r.val, vec(0, ix as int));
             ret lval_mem(v.bcx, v.val);
@@ -3623,7 +3624,7 @@ fn trans_bind_thunk(@crate_ctxt cx,
     auto fcx = new_fn_ctxt(cx, llthunk);
     auto bcx = new_top_block_ctxt(fcx);
 
-    auto llclosure_ptr_ty = type_of(cx, plain_ty(ty.ty_box(closure_ty)));
+    auto llclosure_ptr_ty = type_of(cx, ty.plain_box_ty(closure_ty));
     auto llclosure = bcx.build.PointerCast(fcx.llenv, llclosure_ptr_ty);
 
     auto lltarget = GEP_tup_like(bcx, closure_ty, llclosure,
@@ -3795,7 +3796,7 @@ fn trans_bind(@block_ctxt cx, @ast.expr f,
             }
 
             // Synthesize a closure type.
-            let @ty.t bindings_ty = plain_ty(ty.ty_tup(bound_tys));
+            let @ty.t bindings_ty = ty.plain_tup_ty(bound_tys);
 
             // NB: keep this in sync with T_closure_ptr; we're making
             // a ty.t structure that has the same "shape" as the LLVM type
@@ -3809,9 +3810,9 @@ fn trans_bind(@block_ctxt cx, @ast.expr f,
                 vec(tydesc_ty,
                     outgoing_fty,
                     bindings_ty,
-                    plain_ty(ty.ty_tup(captured_tys)));
+                    ty.plain_tup_ty(captured_tys));
 
-            let @ty.t closure_ty = plain_ty(ty.ty_tup(closure_tys));
+            let @ty.t closure_ty = ty.plain_tup_ty(closure_tys);
 
             auto r = trans_malloc_boxed(bcx, closure_ty);
             auto box = r.val;
@@ -4155,8 +4156,8 @@ fn trans_vec(@block_ctxt cx, vec[@ast.expr] args,
     auto t = node_ann_type(cx.fcx.ccx, ann);
     auto unit_ty = t;
     alt (t.struct) {
-        case (ty.ty_vec(?t)) {
-            unit_ty = t;
+        case (ty.ty_vec(?mt)) {
+            unit_ty = mt.ty;
         }
         case (_) {
             cx.fcx.ccx.sess.bug("non-vec type in trans_vec");
@@ -4183,8 +4184,8 @@ fn trans_vec(@block_ctxt cx, vec[@ast.expr] args,
                                            C_int(abi.vec_elt_data)));
 
     auto pseudo_tup_ty =
-        plain_ty(ty.ty_tup(_vec.init_elt[@ty.t](unit_ty,
-                                                _vec.len[@ast.expr](args))));
+        ty.plain_tup_ty(_vec.init_elt[@ty.t](unit_ty,
+                                             _vec.len[@ast.expr](args)));
     let int i = 0;
 
     for (@ast.expr e in args) {
@@ -4253,7 +4254,7 @@ fn trans_rec(@block_ctxt cx, vec[ast.field] fields,
     }
 
     for (ty.field tf in ty_fields) {
-        auto e_ty = tf.ty;
+        auto e_ty = tf.mt.ty;
         auto dst_res = GEP_tup_like(bcx, t, rec_val, vec(0, i));
         bcx = dst_res.bcx;
 
@@ -4359,7 +4360,7 @@ fn trans_expr(@block_ctxt cx, @ast.expr e) -> result {
             ret trans_cast(cx, e, ann);
         }
 
-        case (ast.expr_vec(?args, ?ann)) {
+        case (ast.expr_vec(?args, _, ?ann)) {
             ret trans_vec(cx, args, ann);
         }
 
@@ -4910,7 +4911,7 @@ fn populate_fn_ctxt_from_llself(@block_ctxt cx, ValueRef llself) -> result {
 
     // Synthesize a tuple type for the fields so that GEP_tup_like() can work
     // its magic.
-    auto fields_tup_ty = ty.plain_ty(ty.ty_tup(field_tys));
+    auto fields_tup_ty = ty.plain_tup_ty(field_tys);
 
     auto n_typarams = _vec.len[ast.ty_param](bcx.fcx.ccx.obj_typarams);
     let TypeRef llobj_box_ty = T_obj_ptr(bcx.fcx.ccx.tn, n_typarams);
@@ -5102,12 +5103,12 @@ fn trans_obj(@crate_ctxt cx, &ast._obj ob, ast.def_id oid,
             _vec.push[@ty.t](tps, tydesc_ty);
         }
 
-        let @ty.t typarams_ty = plain_ty(ty.ty_tup(tps));
-        let @ty.t fields_ty = plain_ty(ty.ty_tup(obj_fields));
-        let @ty.t body_ty = plain_ty(ty.ty_tup(vec(tydesc_ty,
-                                                   typarams_ty,
-                                                   fields_ty)));
-        let @ty.t boxed_body_ty = plain_ty(ty.ty_box(body_ty));
+        let @ty.t typarams_ty = ty.plain_tup_ty(tps);
+        let @ty.t fields_ty = ty.plain_tup_ty(obj_fields);
+        let @ty.t body_ty = ty.plain_tup_ty(vec(tydesc_ty,
+                                                typarams_ty,
+                                                fields_ty));
+        let @ty.t boxed_body_ty = ty.plain_box_ty(body_ty);
 
         // Malloc a box for the body.
         auto box = trans_malloc_boxed(bcx, body_ty);
diff --git a/src/comp/middle/ty.rs b/src/comp/middle/ty.rs
index 56a9c226..3d10462a 100644
--- a/src/comp/middle/ty.rs
+++ b/src/comp/middle/ty.rs
@@ -17,15 +17,17 @@ import util.common.span;
 // Data types
 
 type arg = rec(ast.mode mode, @t ty);
-type field = rec(ast.ident ident, @t ty);
+type field = rec(ast.ident ident, mt mt);
 type method = rec(ast.proto proto,
                   ast.ident ident,
                   vec[arg] inputs,
                   @t output);
 
+type mt = rec(@t ty, ast.mutability mut);
+
 // NB: If you change this, you'll probably want to change the corresponding
 // AST structure in front/ast.rs as well.
-type t = rec(sty struct, mutability mut, option.t[str] cname);
+type t = rec(sty struct, option.t[str] cname);
 tag sty {
     ty_nil;
     ty_bool;
@@ -35,11 +37,11 @@ tag sty {
     ty_char;
     ty_str;
     ty_tag(ast.def_id, vec[@t]);
-    ty_box(@t);
-    ty_vec(@t);
+    ty_box(mt);
+    ty_vec(mt);
     ty_port(@t);
     ty_chan(@t);
-    ty_tup(vec[@t]);
+    ty_tup(vec[mt]);
     ty_rec(vec[field]);
     ty_fn(ast.proto, vec[arg], @t);                 // TODO: effect
     ty_native_fn(ast.native_abi, vec[arg], @t);     // TODO: effect
@@ -65,6 +67,8 @@ type unify_handler = obj {
 
 tag type_err {
     terr_mismatch;
+    terr_box_mutability;
+    terr_vec_mutability;
     terr_tuple_size(uint, uint);
     terr_tuple_mutability;
     terr_record_size(uint, uint);
@@ -138,14 +142,20 @@ fn ty_to_str(&@t typ) -> str {
     }
 
     fn field_to_str(&field f) -> str {
-        ret ty_to_str(f.ty) + " " + f.ident;
+        ret mt_to_str(f.mt) + " " + f.ident;
     }
 
-    auto s = "";
-    if (typ.mut == ast.mut) {
-        s += "mutable ";
+    fn mt_to_str(&mt m) -> str {
+        auto mstr;
+        alt (m.mut) {
+            case (ast.mut) { mstr = "mutable "; }
+            case (ast.imm) { mstr = "";         }
+        }
+
+        ret mstr + ty_to_str(m.ty);
     }
 
+    auto s = "";
     alt (typ.struct) {
         case (ty_native)       { s += "native";                     }
         case (ty_nil)          { s += "()";                         }
@@ -155,15 +165,15 @@ fn ty_to_str(&@t typ) -> str {
         case (ty_machine(?tm)) { s += common.ty_mach_to_str(tm);    }
         case (ty_char)         { s += "char";                       }
         case (ty_str)          { s += "str";                        }
-        case (ty_box(?t))      { s += "@" + ty_to_str(t);           }
-        case (ty_vec(?t))      { s += "vec[" + ty_to_str(t) + "]";  }
+        case (ty_box(?tm))     { s += "@" + mt_to_str(tm);          }
+        case (ty_vec(?tm))     { s += "vec[" + mt_to_str(tm) + "]"; }
         case (ty_port(?t))     { s += "port[" + ty_to_str(t) + "]"; }
         case (ty_chan(?t))     { s += "chan[" + ty_to_str(t) + "]"; }
         case (ty_type)         { s += "type";                       }
 
         case (ty_tup(?elems)) {
-            auto f = ty_to_str;
-            auto strs = _vec.map[@t,str](f, elems);
+            auto f = mt_to_str;
+            auto strs = _vec.map[mt,str](f, elems);
             s += "tup(" + _str.connect(strs, ",") + ")";
         }
 
@@ -224,7 +234,7 @@ type ty_fold = state obj {
 
 fn fold_ty(ty_fold fld, @t ty) -> @t {
     fn rewrap(@t orig, &sty new) -> @t {
-        ret @rec(struct=new, mut=orig.mut, cname=orig.cname);
+        ret @rec(struct=new, cname=orig.cname);
     }
 
     alt (ty.struct) {
@@ -237,11 +247,11 @@ fn fold_ty(ty_fold fld, @t ty) -> @t {
         case (ty_str)           { ret fld.fold_simple_ty(ty); }
         case (ty_type)          { ret fld.fold_simple_ty(ty); }
         case (ty_native)        { ret fld.fold_simple_ty(ty); }
-        case (ty_box(?subty)) {
-            ret rewrap(ty, ty_box(fold_ty(fld, subty)));
+        case (ty_box(?tm)) {
+            ret rewrap(ty, ty_box(rec(ty=fold_ty(fld, tm.ty), mut=tm.mut)));
         }
-        case (ty_vec(?subty)) {
-            ret rewrap(ty, ty_vec(fold_ty(fld, subty)));
+        case (ty_vec(?tm)) {
+            ret rewrap(ty, ty_vec(rec(ty=fold_ty(fld, tm.ty), mut=tm.mut)));
         }
         case (ty_port(?subty)) {
             ret rewrap(ty, ty_port(fold_ty(fld, subty)));
@@ -256,18 +266,20 @@ fn fold_ty(ty_fold fld, @t ty) -> @t {
             }
             ret rewrap(ty, ty_tag(tid, new_subtys));
         }
-        case (ty_tup(?subtys)) {
-            let vec[@t] new_subtys = vec();
-            for (@t subty in subtys) {
-                new_subtys += vec(fold_ty(fld, subty));
+        case (ty_tup(?mts)) {
+            let vec[mt] new_mts = vec();
+            for (mt tm in mts) {
+                auto new_subty = fold_ty(fld, tm.ty);
+                new_mts += vec(rec(ty=new_subty, mut=tm.mut));
             }
-            ret rewrap(ty, ty_tup(new_subtys));
+            ret rewrap(ty, ty_tup(new_mts));
         }
         case (ty_rec(?fields)) {
             let vec[field] new_fields = vec();
             for (field fl in fields) {
-                auto new_ty = fold_ty(fld, fl.ty);
-                new_fields += vec(rec(ident=fl.ident, ty=new_ty));
+                auto new_ty = fold_ty(fld, fl.mt.ty);
+                auto new_mt = rec(ty=new_ty, mut=fl.mt.mut);
+                new_fields += vec(rec(ident=fl.ident, mt=new_mt));
             }
             ret rewrap(ty, ty_rec(new_fields));
         }
@@ -351,8 +363,8 @@ fn type_is_sequence(@t ty) -> bool {
 
 fn sequence_element_type(@t ty) -> @t {
     alt (ty.struct) {
-        case (ty_str)     { ret plain_ty(ty_machine(common.ty_u8)); }
-        case (ty_vec(?e)) { ret e; }
+        case (ty_str)      { ret plain_ty(ty_machine(common.ty_u8)); }
+        case (ty_vec(?mt)) { ret mt.ty; }
     }
     fail;
 }
@@ -372,11 +384,11 @@ fn type_is_tup_like(@t ty) -> bool {
 fn get_element_type(@t ty, uint i) -> @t {
     check (type_is_tup_like(ty));
     alt (ty.struct) {
-        case (ty_tup(?tys)) {
-            ret tys.(i);
+        case (ty_tup(?mts)) {
+            ret mts.(i).ty;
         }
         case (ty_rec(?flds)) {
-            ret flds.(i).ty;
+            ret flds.(i).mt.ty;
         }
     }
     fail;
@@ -427,17 +439,17 @@ fn type_is_native(@t ty) -> bool {
 
 fn type_has_dynamic_size(@t ty) -> bool {
     alt (ty.struct) {
-        case (ty_tup(?ts)) {
+        case (ty_tup(?mts)) {
             auto i = 0u;
-            while (i < _vec.len[@t](ts)) {
-                if (type_has_dynamic_size(ts.(i))) { ret true; }
+            while (i < _vec.len[mt](mts)) {
+                if (type_has_dynamic_size(mts.(i).ty)) { ret true; }
                 i += 1u;
             }
         }
         case (ty_rec(?fields)) {
             auto i = 0u;
             while (i < _vec.len[field](fields)) {
-                if (type_has_dynamic_size(fields.(i).ty)) { ret true; }
+                if (type_has_dynamic_size(fields.(i).mt.ty)) { ret true; }
                 i += 1u;
             }
         }
@@ -518,7 +530,19 @@ fn type_param(@t ty) -> option.t[ast.def_id] {
 }
 
 fn plain_ty(&sty st) -> @t {
-    ret @rec(struct=st, mut=ast.imm, cname=none[str]);
+    ret @rec(struct=st, cname=none[str]);
+}
+
+fn plain_box_ty(@t subty) -> @t {
+    ret plain_ty(ty_box(rec(ty=subty, mut=ast.imm)));
+}
+
+fn plain_tup_ty(vec[@t] elem_tys) -> @t {
+    let vec[ty.mt] mts = vec();
+    for (@ty.t typ in elem_tys) {
+        mts += vec(rec(ty=typ, mut=ast.imm));
+    }
+    ret plain_ty(ty_tup(mts));
 }
 
 fn hash_ty(&@t ty) -> uint {
@@ -703,7 +727,7 @@ fn pat_ty(@ast.pat pat) -> @t {
 
 fn expr_ty(@ast.expr expr) -> @t {
     alt (expr.node) {
-        case (ast.expr_vec(_, ?ann))          { ret ann_to_type(ann); }
+        case (ast.expr_vec(_, _, ?ann))       { ret ann_to_type(ann); }
         case (ast.expr_tup(_, ?ann))          { ret ann_to_type(ann); }
         case (ast.expr_rec(_, _, ?ann))       { ret ann_to_type(ann); }
         case (ast.expr_bind(_, _, ?ann))      { ret ann_to_type(ann); }
@@ -1131,16 +1155,23 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
                 ret ures_err(terr_mismatch, expected, actual);
             }
 
-            case (ty.ty_box(?expected_sub)) {
+            case (ty.ty_box(?expected_mt)) {
                 alt (actual.struct) {
-                    case (ty.ty_box(?actual_sub)) {
+                    case (ty.ty_box(?actual_mt)) {
+                        if (expected_mt.mut != actual_mt.mut) {
+                            ret ures_err(terr_box_mutability, expected,
+                                         actual);
+                        }
+
                         auto result = unify_step(bindings,
-                                                 expected_sub,
-                                                 actual_sub,
+                                                 expected_mt.ty,
+                                                 actual_mt.ty,
                                                  handler);
                         alt (result) {
                             case (ures_ok(?result_sub)) {
-                                ret ures_ok(plain_ty(ty.ty_box(result_sub)));
+                                auto mt = rec(ty=result_sub,
+                                              mut=expected_mt.mut);
+                                ret ures_ok(plain_ty(ty.ty_box(mt)));
                             }
                             case (_) {
                                 ret result;
@@ -1154,16 +1185,23 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
                 }
             }
 
-            case (ty.ty_vec(?expected_sub)) {
+            case (ty.ty_vec(?expected_mt)) {
                 alt (actual.struct) {
-                    case (ty.ty_vec(?actual_sub)) {
+                    case (ty.ty_vec(?actual_mt)) {
+                        if (expected_mt.mut != actual_mt.mut) {
+                            ret ures_err(terr_vec_mutability, expected,
+                                         actual);
+                        }
+
                         auto result = unify_step(bindings,
-                                                 expected_sub,
-                                                 actual_sub,
+                                                 expected_mt.ty,
+                                                 actual_mt.ty,
                                                  handler);
                         alt (result) {
                             case (ures_ok(?result_sub)) {
-                                ret ures_ok(plain_ty(ty.ty_vec(result_sub)));
+                                auto mt = rec(ty=result_sub,
+                                              mut=expected_mt.mut);
+                                ret ures_ok(plain_ty(ty.ty_vec(mt)));
                             }
                             case (_) {
                                 ret result;
@@ -1226,8 +1264,8 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
             case (ty.ty_tup(?expected_elems)) {
                 alt (actual.struct) {
                     case (ty.ty_tup(?actual_elems)) {
-                        auto expected_len = _vec.len[@ty.t](expected_elems);
-                        auto actual_len = _vec.len[@ty.t](actual_elems);
+                        auto expected_len = _vec.len[ty.mt](expected_elems);
+                        auto actual_len = _vec.len[ty.mt](actual_elems);
                         if (expected_len != actual_len) {
                             auto err = terr_tuple_size(expected_len,
                                                        actual_len);
@@ -1236,7 +1274,7 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
 
                         // TODO: implement an iterator that can iterate over
                         // two arrays simultaneously.
-                        let vec[@ty.t] result_elems = vec();
+                        let vec[ty.mt] result_elems = vec();
                         auto i = 0u;
                         while (i < expected_len) {
                             auto expected_elem = expected_elems.(i);
@@ -1247,12 +1285,14 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
                             }
 
                             auto result = unify_step(bindings,
-                                                     expected_elem,
-                                                     actual_elem,
+                                                     expected_elem.ty,
+                                                     actual_elem.ty,
                                                      handler);
                             alt (result) {
                                 case (ures_ok(?rty)) {
-                                    _vec.push[@ty.t](result_elems,rty);
+                                    auto mt = rec(ty=rty,
+                                                  mut=expected_elem.mut);
+                                    result_elems += vec(mt);
                                 }
                                 case (_) {
                                     ret result;
@@ -1289,14 +1329,14 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
                         while (i < expected_len) {
                             auto expected_field = expected_fields.(i);
                             auto actual_field = actual_fields.(i);
-                            if (expected_field.ty.mut
-                                != actual_field.ty.mut) {
+                            if (expected_field.mt.mut
+                                    != actual_field.mt.mut) {
                                 auto err = terr_record_mutability;
                                 ret ures_err(err, expected, actual);
                             }
 
                             if (!_str.eq(expected_field.ident,
-                                        actual_field.ident)) {
+                                         actual_field.ident)) {
                                 auto err =
                                     terr_record_fields(expected_field.ident,
                                                        actual_field.ident);
@@ -1304,14 +1344,16 @@ fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
                             }
 
                             auto result = unify_step(bindings,
-                                                     expected_field.ty,
-                                                     actual_field.ty,
+                                                     expected_field.mt.ty,
+                                                     actual_field.mt.ty,
                                                      handler);
                             alt (result) {
                                 case (ures_ok(?rty)) {
+                                    auto mt = rec(ty=rty,
+                                                  mut=expected_field.mt.mut);
                                     _vec.push[field]
                                         (result_fields,
-                                         rec(ty=rty with expected_field));
+                                         rec(mt=mt with expected_field));
                                 }
                                 case (_) {
                                     ret result;
diff --git a/src/comp/middle/typeck.rs b/src/comp/middle/typeck.rs
index b689c502..5279b713 100644
--- a/src/comp/middle/typeck.rs
+++ b/src/comp/middle/typeck.rs
@@ -276,6 +276,10 @@ fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty.t {
         ret rec(mode=arg.mode, ty=ast_ty_to_ty(getter, arg.ty));
     }
 
+    fn ast_mt_to_mt(ty_getter getter, &ast.mt mt) -> ty.mt {
+        ret rec(ty=ast_ty_to_ty(getter, mt.ty), mut=mt.mut);
+    }
+
     fn instantiate(ty_getter getter, ast.def_id id,
                    vec[@ast.ty] args) -> @ty.t {
         // TODO: maybe record cname chains so we can do
@@ -305,8 +309,8 @@ fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty.t {
         case (ast.ty_machine(?tm)) { sty = ty.ty_machine(tm); }
         case (ast.ty_char)         { sty = ty.ty_char; }
         case (ast.ty_str)          { sty = ty.ty_str; }
-        case (ast.ty_box(?t)) { sty = ty.ty_box(ast_ty_to_ty(getter, t)); }
-        case (ast.ty_vec(?t)) { sty = ty.ty_vec(ast_ty_to_ty(getter, t)); }
+        case (ast.ty_box(?mt)) { sty = ty.ty_box(ast_mt_to_mt(getter, mt)); }
+        case (ast.ty_vec(?mt)) { sty = ty.ty_vec(ast_mt_to_mt(getter, mt)); }
 
         case (ast.ty_port(?t)) {
             sty = ty.ty_port(ast_ty_to_ty(getter, t));
@@ -317,9 +321,9 @@ fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty.t {
         }
 
         case (ast.ty_tup(?fields)) {
-            let vec[@ty.t] flds = vec();
-            for (@ast.ty field in fields) {
-                _vec.push[@ty.t](flds, ast_ty_to_ty(getter, field));
+            let vec[ty.mt] flds = vec();
+            for (ast.mt field in fields) {
+                _vec.push[ty.mt](flds, ast_mt_to_mt(getter, field));
             }
             sty = ty.ty_tup(flds);
         }
@@ -327,7 +331,7 @@ fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty.t {
             let vec[field] flds = vec();
             for (ast.ty_field f in fields) {
                 _vec.push[field](flds, rec(ident=f.ident,
-                                        ty=ast_ty_to_ty(getter, f.ty)));
+                                        mt=ast_mt_to_mt(getter, f.mt)));
             }
             sty = ty.ty_rec(flds);
         }
@@ -357,13 +361,6 @@ fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty.t {
             cname = some(path_to_str(path));
         }
 
-        case (ast.ty_mutable(?t)) {
-            mut = ast.mut;
-            auto t0 = ast_ty_to_ty(getter, t);
-            sty = t0.struct;
-            cname = t0.cname;
-        }
-
         case (ast.ty_obj(?meths)) {
             let vec[ty.method] tmeths = vec();
             auto f = bind ast_arg_to_arg(getter, _);
@@ -381,7 +378,7 @@ fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty.t {
         }
     }
 
-    ret @rec(struct=sty, mut=mut, cname=cname);
+    ret @rec(struct=sty, cname=cname);
 }
 
 fn actual_type(@ty.t t, @ast.item item) -> @ty.t {
@@ -638,8 +635,7 @@ fn collect_item_types(session.session sess, @ast.crate crate)
                     // Avoid repeating work.
                     ret item_to_ty.get(def_id);
                 }
-                auto x =
-                    @rec(struct=ty.ty_native, mut=ast.imm, cname=none[str]);
+                auto x = @rec(struct=ty.ty_native, cname=none[str]);
                 item_to_ty.insert(def_id, x);
                 ret x;
             }
@@ -973,7 +969,7 @@ fn strip_boxes(@ty.t t) -> @ty.t {
     auto t1 = t;
     while (true) {
         alt (t1.struct) {
-            case (ty.ty_box(?inner)) { t1 = inner; }
+            case (ty.ty_box(?inner)) { t1 = inner.ty; }
             case (_) { ret t1; }
         }
     }
@@ -983,7 +979,7 @@ fn strip_boxes(@ty.t t) -> @ty.t {
 fn add_boxes(uint n, @ty.t t) -> @ty.t {
     auto t1 = t;
     while (n != 0u) {
-        t1 = plain_ty(ty.ty_box(t1));
+        t1 = ty.plain_box_ty(t1);
         n -= 1u;
     }
     ret t1;
@@ -995,7 +991,7 @@ fn count_boxes(@ty.t t) -> uint {
     auto t1 = t;
     while (true) {
         alt (t1.struct) {
-            case (ty.ty_box(?inner)) { n += 1u; t1 = inner; }
+            case (ty.ty_box(?inner)) { n += 1u; t1 = inner.ty; }
             case (_) { ret n; }
         }
     }
@@ -1143,13 +1139,15 @@ fn demand_expr_full(&@fn_ctxt fcx, @ty.t expected, @ast.expr e,
     auto e_1;
 
     alt (e.node) {
-        case (ast.expr_vec(?es_0, ?ann)) {
+        case (ast.expr_vec(?es_0, ?mut, ?ann)) {
+            // TODO: enforce mutability
+
             auto t = demand(fcx, e.span, expected, ann_to_type(ann));
             let vec[@ast.expr] es_1 = vec();
             alt (t.struct) {
-                case (ty.ty_vec(?subty)) {
+                case (ty.ty_vec(?mt)) {
                     for (@ast.expr e_0 in es_0) {
-                        es_1 += vec(demand_expr(fcx, subty, e_0));
+                        es_1 += vec(demand_expr(fcx, mt.ty, e_0));
                     }
                 }
                 case (_) {
@@ -1157,16 +1155,16 @@ fn demand_expr_full(&@fn_ctxt fcx, @ty.t expected, @ast.expr e,
                     fail;
                 }
             }
-            e_1 = ast.expr_vec(es_1, ast.ann_type(t, none[vec[@ty.t]]));
+            e_1 = ast.expr_vec(es_1, mut, ast.ann_type(t, none[vec[@ty.t]]));
         }
         case (ast.expr_tup(?es_0, ?ann)) {
             auto t = demand(fcx, e.span, expected, ann_to_type(ann));
             let vec[ast.elt] elts_1 = vec();
             alt (t.struct) {
-                case (ty.ty_tup(?subtys)) {
+                case (ty.ty_tup(?mts)) {
                     auto i = 0u;
                     for (ast.elt elt_0 in es_0) {
-                        auto e_1 = demand_expr(fcx, subtys.(i), elt_0.expr);
+                        auto e_1 = demand_expr(fcx, mts.(i).ty, elt_0.expr);
                         elts_1 += vec(rec(mut=elt_0.mut, expr=e_1));
                         i += 1u;
                     }
@@ -1185,15 +1183,15 @@ fn demand_expr_full(&@fn_ctxt fcx, @ty.t expected, @ast.expr e,
             auto t = demand(fcx, e.span, expected, ann_to_type(ann));
             let vec[ast.field] fields_1 = vec();
             alt (t.struct) {
-                case (ty.ty_rec(?field_tys)) {
+                case (ty.ty_rec(?field_mts)) {
                     alt (base_0) {
                         case (none[@ast.expr]) {
                             auto i = 0u;
                             for (ast.field field_0 in fields_0) {
                                 check (_str.eq(field_0.ident,
-                                               field_tys.(i).ident));
+                                               field_mts.(i).ident));
                                 auto e_1 = demand_expr(fcx,
-                                                       field_tys.(i).ty,
+                                                       field_mts.(i).mt.ty,
                                                        field_0.expr);
                                 fields_1 += vec(rec(mut=field_0.mut,
                                                     ident=field_0.ident,
@@ -1210,9 +1208,9 @@ fn demand_expr_full(&@fn_ctxt fcx, @ty.t expected, @ast.expr e,
 
                             for (ast.field field_0 in fields_0) {
 
-                                for (ty.field ft in field_tys) {
+                                for (ty.field ft in field_mts) {
                                     if (_str.eq(field_0.ident, ft.ident)) {
-                                        auto e_1 = demand_expr(fcx, ft.ty,
+                                        auto e_1 = demand_expr(fcx, ft.mt.ty,
                                                                field_0.expr);
                                         fields_1 +=
                                             vec(rec(mut=field_0.mut,
@@ -1704,11 +1702,14 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             auto oper_1 = check_expr(fcx, oper);
             auto oper_t = expr_ty(oper_1);
             alt (unop) {
-                case (ast.box) { oper_t = plain_ty(ty.ty_box(oper_t)); }
+                case (ast.box) {
+                    // TODO: mutable
+                    oper_t = ty.plain_box_ty(oper_t);
+                }
                 case (ast.deref) {
                     alt (oper_t.struct) {
-                        case (ty.ty_box(?inner_t)) {
-                            oper_t = inner_t;
+                        case (ty.ty_box(?inner)) {
+                            oper_t = inner.ty;
                         }
                         case (_) {
                             fcx.ccx.sess.span_err
@@ -1718,9 +1719,6 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                         }
                     }
                 }
-                case (ast._mutable) {
-                    oper_t = @rec(mut=ast.mut with *oper_t);
-                }
                 case (_) { oper_t = strip_boxes(oper_t); }
             }
 
@@ -2107,12 +2105,9 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                                         ast.expr_cast(e_1, t, ann));
         }
 
-        case (ast.expr_vec(?args, _)) {
+        case (ast.expr_vec(?args, ?mut, _)) {
             let vec[@ast.expr] args_1 = vec();
 
-            // FIXME: implement mutable vectors with leading 'mutable' flag
-            // marking the elements as mutable.
-
             let @ty.t t;
             if (_vec.len[@ast.expr](args) == 0u) {
                 t = next_ty_var(fcx.ccx);
@@ -2127,26 +2122,25 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                 demand(fcx, expr.span, t, expr_t);
                 _vec.push[@ast.expr](args_1,expr_1);
             }
-            auto ann = ast.ann_type(plain_ty(ty.ty_vec(t)), none[vec[@ty.t]]);
+
+            auto vec_sty = ty.ty_vec(rec(ty=t, mut=mut));
+            auto ann = ast.ann_type(plain_ty(vec_sty), none[vec[@ty.t]]);
             ret @fold.respan[ast.expr_](expr.span,
-                                        ast.expr_vec(args_1, ann));
+                                        ast.expr_vec(args_1, mut, ann));
         }
 
         case (ast.expr_tup(?elts, _)) {
             let vec[ast.elt] elts_1 = vec();
-            let vec[@ty.t] elts_t = vec();
+            let vec[ty.mt] elts_mt = vec();
 
             for (ast.elt e in elts) {
                 auto expr_1 = check_expr(fcx, e.expr);
                 auto expr_t = expr_ty(expr_1);
-                if (e.mut == ast.mut) {
-                    expr_t = @rec(mut=ast.mut with *expr_t);
-                }
                 _vec.push[ast.elt](elts_1, rec(expr=expr_1 with e));
-                _vec.push[@ty.t](elts_t, expr_t);
+                elts_mt += vec(rec(ty=expr_t, mut=e.mut));
             }
 
-            auto ann = ast.ann_type(plain_ty(ty.ty_tup(elts_t)),
+            auto ann = ast.ann_type(plain_ty(ty.ty_tup(elts_mt)),
                                     none[vec[@ty.t]]);
             ret @fold.respan[ast.expr_](expr.span,
                                         ast.expr_tup(elts_1, ann));
@@ -2168,11 +2162,10 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             for (ast.field f in fields) {
                 auto expr_1 = check_expr(fcx, f.expr);
                 auto expr_t = expr_ty(expr_1);
-                if (f.mut == ast.mut) {
-                    expr_t = @rec(mut=ast.mut with *expr_t);
-                }
                 _vec.push[ast.field](fields_1, rec(expr=expr_1 with f));
-                _vec.push[field](fields_t, rec(ident=f.ident, ty=expr_t));
+
+                auto expr_mt = rec(ty=expr_t, mut=f.mut);
+                _vec.push[field](fields_t, rec(ident=f.ident, mt=expr_mt));
             }
 
             auto ann = ast.ann_none;
@@ -2206,7 +2199,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                         auto found = false;
                         for (ty.field bf in base_fields) {
                             if (_str.eq(f.ident, bf.ident)) {
-                                demand(fcx, expr.span, f.ty, bf.ty);
+                                demand(fcx, expr.span, f.mt.ty, bf.mt.ty);
                                 found = true;
                             }
                         }
@@ -2231,11 +2224,11 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                 case (ty.ty_tup(?args)) {
                     let uint ix = ty.field_num(fcx.ccx.sess,
                                                expr.span, field);
-                    if (ix >= _vec.len[@ty.t](args)) {
+                    if (ix >= _vec.len[ty.mt](args)) {
                         fcx.ccx.sess.span_err(expr.span,
                                               "bad index on tuple");
                     }
-                    auto ann = ast.ann_type(args.(ix), none[vec[@ty.t]]);
+                    auto ann = ast.ann_type(args.(ix).ty, none[vec[@ty.t]]);
                     ret @fold.respan[ast.expr_](expr.span,
                                                 ast.expr_field(base_1,
                                                                field,
@@ -2249,7 +2242,8 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                         fcx.ccx.sess.span_err(expr.span,
                                               "bad index on record");
                     }
-                    auto ann = ast.ann_type(fields.(ix).ty, none[vec[@ty.t]]);
+                    auto ann = ast.ann_type(fields.(ix).mt.ty,
+                                            none[vec[@ty.t]]);
                     ret @fold.respan[ast.expr_](expr.span,
                                                 ast.expr_field(base_1,
                                                                field,
@@ -2289,14 +2283,14 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             auto idx_t = expr_ty(idx_1);
 
             alt (base_t.struct) {
-                case (ty.ty_vec(?t)) {
+                case (ty.ty_vec(?mt)) {
                     if (! type_is_integral(idx_t)) {
                         fcx.ccx.sess.span_err
                             (idx.span,
                              "non-integral type of vec index: "
                              + ty_to_str(idx_t));
                     }
-                    auto ann = ast.ann_type(t, none[vec[@ty.t]]);
+                    auto ann = ast.ann_type(mt.ty, none[vec[@ty.t]]);
                     ret @fold.respan[ast.expr_](expr.span,
                                                 ast.expr_index(base_1,
                                                                idx_1,
diff --git a/src/comp/pretty/pprust.rs b/src/comp/pretty/pprust.rs
index 1f9b455b..f2e52d72 100644
--- a/src/comp/pretty/pprust.rs
+++ b/src/comp/pretty/pprust.rs
@@ -48,7 +48,7 @@ impure fn bclose(ps s) {
   end(s);
   pp.cwrd(s, "}");
 }
-impure fn commasep[IN](ps s, vec[IN] elts, impure fn (ps, IN) op) {
+impure fn commasep[IN](ps s, vec[IN] elts, impure fn (ps, &IN) op) {
   auto first = true;
   for (IN elt in elts) {
     if (first) {first = false;}
@@ -57,7 +57,14 @@ impure fn commasep[IN](ps s, vec[IN] elts, impure fn (ps, IN) op) {
   }
 }
 
-impure fn print_type(ps s, @ast.ty ty) {
+impure fn print_mt(ps s, &ast.mt mt) {
+    if (mt.mut == ast.mut) {
+        wrd1(s, "mutable");
+    }
+    print_type(s, mt.ty);
+}
+
+impure fn print_type(ps s, &@ast.ty ty) {
   hbox(s);
   alt (ty.node) {
     case (ast.ty_nil) {wrd(s, "()");}
@@ -67,22 +74,22 @@ impure fn print_type(ps s, @ast.ty ty) {
     case (ast.ty_machine(?tm)) {wrd(s, util.common.ty_mach_to_str(tm));}
     case (ast.ty_char) {wrd(s, "char");}
     case (ast.ty_str) {wrd(s, "str");}
-    case (ast.ty_box(?t)) {wrd(s, "@"); print_type(s, t);}
-    case (ast.ty_vec(?t)) {wrd(s, "vec["); print_type(s, t); wrd(s, "]");}
+    case (ast.ty_box(?mt)) {wrd(s, "@"); print_mt(s, mt);}
+    case (ast.ty_vec(?mt)) {wrd(s, "vec["); print_mt(s, mt); wrd(s, "]");}
     case (ast.ty_type) {wrd(s, "type");}
     case (ast.ty_tup(?elts)) {
       wrd(s, "tup");
       popen(s);
-      auto f = print_type;
-      commasep[@ast.ty](s, elts, f);
+      auto f = print_mt;
+      commasep[ast.mt](s, elts, f);
       pclose(s);
     }
     case (ast.ty_rec(?fields)) {
       wrd(s, "rec");
       popen(s);
-      impure fn print_field(ps s, ast.ty_field f) {
+      impure fn print_field(ps s, &ast.ty_field f) {
         hbox(s);
-        print_type(s, f.ty);
+        print_mt(s, f.mt);
         space(s);
         wrd(s, f.ident);
         end(s);
@@ -110,10 +117,6 @@ impure fn print_type(ps s, @ast.ty ty) {
     case (ast.ty_path(?path,_)) {
       print_path(s, path);
     }
-    case (ast.ty_mutable(?t)) {
-      wrd1(s, "mutable");
-      print_type(s, t);
-    }
   }
   end(s);
 }
@@ -186,7 +189,7 @@ impure fn print_item(ps s, @ast.item item) {
         wrd(s, v.name);
         if (_vec.len[ast.variant_arg](v.args) > 0u) {
           popen(s);
-          impure fn print_variant_arg(ps s, ast.variant_arg arg) {
+          impure fn print_variant_arg(ps s, &ast.variant_arg arg) {
             print_type(s, arg.ty);
           }
           auto f = print_variant_arg;
@@ -203,7 +206,7 @@ impure fn print_item(ps s, @ast.item item) {
       wrd(s, id);
       print_type_params(s, params);
       popen(s);
-      impure fn print_field(ps s, ast.obj_field field) {
+      impure fn print_field(ps s, &ast.obj_field field) {
         hbox(s);
         print_type(s, field.ty);
         space(s);
@@ -285,18 +288,21 @@ impure fn print_literal(ps s, @ast.lit lit) {
   }
 }
 
-impure fn print_expr(ps s, @ast.expr expr) {
+impure fn print_expr(ps s, &@ast.expr expr) {
   auto pe = print_expr;
   hbox(s);
   alt (expr.node) {
-    case (ast.expr_vec(?exprs,_)) {
+    case (ast.expr_vec(?exprs,?mut,_)) {
+      if (mut == ast.mut) {
+        wrd1(s, "mutable");
+      }
       wrd(s, "vec");
       popen(s);
       commasep[@ast.expr](s, exprs, pe);
       pclose(s);
     }
     case (ast.expr_tup(?exprs,_)) {
-      impure fn printElt(ps s, ast.elt elt) {
+      impure fn printElt(ps s, &ast.elt elt) {
         hbox(s);
         if (elt.mut == ast.mut) {wrd1(s, "mutable");}
         print_expr(s, elt.expr);
@@ -309,7 +315,7 @@ impure fn print_expr(ps s, @ast.expr expr) {
       pclose(s);
     }
     case (ast.expr_rec(?fields,?wth,_)) {
-      impure fn print_field(ps s, ast.field field) {
+      impure fn print_field(ps s, &ast.field field) {
         hbox(s);
         if (field.mut == ast.mut) {wrd1(s, "mutable");}
         wrd(s, field.ident);
@@ -340,7 +346,7 @@ impure fn print_expr(ps s, @ast.expr expr) {
       pclose(s);
     }
     case (ast.expr_bind(?func,?args,_)) {
-      impure fn print_opt(ps s, option.t[@ast.expr] expr) {
+      impure fn print_opt(ps s, &option.t[@ast.expr] expr) {
         alt (expr) {
           case (option.some[@ast.expr](?expr)) {
             print_expr(s, expr);
@@ -364,7 +370,6 @@ impure fn print_expr(ps s, @ast.expr expr) {
     }
     case (ast.expr_unary(?op,?expr,_)) {
       wrd(s, ast.unop_to_str(op));
-      if (op == ast._mutable) {space(s);}
       print_expr(s, expr);
     }
     case (ast.expr_lit(?lit,_)) {
@@ -577,7 +582,7 @@ impure fn print_path(ps s, ast.path path) {
   }
 }
 
-impure fn print_pat(ps s, @ast.pat pat) {
+impure fn print_pat(ps s, &@ast.pat pat) {
   alt (pat.node) {
     case (ast.pat_wild(_)) {wrd(s, "_");}
     case (ast.pat_bind(?id,_,_)) {wrd(s, "?" + id);}
@@ -605,7 +610,7 @@ impure fn print_fn(ps s, ast.fn_decl decl, str name,
   wrd(s, name);
   print_type_params(s, typarams);
   popen(s);
-  impure fn print_arg(ps s, ast.arg x) {
+  impure fn print_arg(ps s, &ast.arg x) {
     hbox(s);
     print_type(s, x.ty);
     space(s);
@@ -627,7 +632,7 @@ impure fn print_fn(ps s, ast.fn_decl decl, str name,
 impure fn print_type_params(ps s, vec[ast.ty_param] params) {
   if (_vec.len[ast.ty_param](params) > 0u) {
     wrd(s, "[");
-    impure fn printParam(ps s, ast.ty_param param) {wrd(s, param.ident);}
+    impure fn printParam(ps s, &ast.ty_param param) {wrd(s, param.ident);}
     auto f = printParam;
     commasep[ast.ty_param](s, params, f);
     wrd(s, "]");
@@ -642,7 +647,7 @@ impure fn print_view_item(ps s, @ast.view_item item) {
       wrd(s, id);
       if (_vec.len[@ast.meta_item](mta) > 0u) {
         popen(s);
-        impure fn print_meta(ps s, @ast.meta_item item) {
+        impure fn print_meta(ps s, &@ast.meta_item item) {
           hbox(s);
           wrd1(s, item.node.name);
           wrd1(s, "=");
@@ -738,7 +743,7 @@ impure fn print_ty_fn(ps s, ast.proto proto, option.t[str] id,
     case (_) {}
   }
   popen(s);
-  impure fn print_arg(ps s, ast.ty_arg input) {
+  impure fn print_arg(ps s, &ast.ty_arg input) {
     if (middle.ty.mode_is_alias(input.mode)) {wrd(s, "&");}
     print_type(s, input.ty);
   }