rustc: Pass a type store around, which does nothing yet

7 files changed, 600 insertions, 440 deletions

diff --git a/src/comp/driver/rustc.rs b/src/comp/driver/rustc.rs
index f2ace0f7f80..afef226e27f 100644
--- a/src/comp/driver/rustc.rs
+++ b/src/comp/driver/rustc.rs
@@ -68,16 +68,19 @@ fn compile_input(session.session sess,
     auto p = parser.new_parser(sess, env, def, input, 0u);
     auto crate = parse_input(sess, p, input);
     if (ot == trans.output_type_none) {ret;}
+
     crate = creader.read_crates(sess, crate, library_search_paths);
     crate = resolve.resolve_crate(sess, crate);
     capture.check_for_captures(sess, crate);
-    auto typeck_result = typeck.check_crate(sess, crate);
+
+    auto tystore = ty.mk_type_store();
+    auto typeck_result = typeck.check_crate(sess, tystore, crate);
     crate = typeck_result._0;
     auto type_cache = typeck_result._1;
     // FIXME: uncomment once typestate_check works
     // crate = typestate_check.check_crate(crate);
-    trans.trans_crate(sess, crate, type_cache, output, shared, optimize,
-                      verify, ot);
+    trans.trans_crate(sess, crate, tystore, type_cache, output, shared,
+                      optimize, verify, ot);
 }
 
 fn pretty_print_input(session.session sess,
diff --git a/src/comp/front/creader.rs b/src/comp/front/creader.rs
index 2490613ae9c..febde3fd477 100644
--- a/src/comp/front/creader.rs
+++ b/src/comp/front/creader.rs
@@ -49,22 +49,23 @@ tag resolve_result {
 // Callback to translate defs to strs or back.
 type str_def = fn(str) -> ast.def_id;
 
-type pstate = rec(str rep, mutable uint pos, uint len);
+type pstate = rec(str rep, mutable uint pos, uint len,
+                  @ty.type_store tystore);
 
 fn peek(@pstate st) -> u8 {
     if (st.pos < st.len) {ret st.rep.(st.pos) as u8;}
     else {ret ' ' as u8;}
 }
-fn next(@pstate st) -> u8 { // ?? somehow not recognized as impure
+fn next(@pstate st) -> u8 {
     if (st.pos >= st.len) {fail;}
     auto ch = st.rep.(st.pos);
     st.pos = st.pos + 1u;
     ret ch as u8;
 }
 
-fn parse_ty_str(str rep, str_def sd) -> @ty.t {
+fn parse_ty_str(str rep, str_def sd, @ty.type_store tystore) -> @ty.t {
     auto len = _str.byte_len(rep);
-    auto st = @rec(rep=rep, mutable pos=0u, len=len);
+    auto st = @rec(rep=rep, mutable pos=0u, len=len, tystore=tystore);
     auto result = parse_ty(st, sd);
     if (st.pos != len) {
         log_err "parse_ty_str: incomplete parse, stopped at byte "
@@ -76,27 +77,27 @@ fn parse_ty_str(str rep, str_def sd) -> @ty.t {
 
 fn parse_ty(@pstate st, str_def sd) -> @ty.t {
     alt (next(st) as char) {
-        case ('n') { ret ty.mk_nil(); }
-        case ('b') { ret ty.mk_bool(); }
-        case ('i') { ret ty.mk_int(); }
-        case ('u') { ret ty.mk_uint(); }
-        case ('l') { ret ty.mk_float(); }
+        case ('n') { ret ty.mk_nil(st.tystore); }
+        case ('b') { ret ty.mk_bool(st.tystore); }
+        case ('i') { ret ty.mk_int(st.tystore); }
+        case ('u') { ret ty.mk_uint(st.tystore); }
+        case ('l') { ret ty.mk_float(st.tystore); }
         case ('M') {
             alt (next(st) as char) {
-                case ('b') { ret ty.mk_mach(common.ty_u8); }
-                case ('w') { ret ty.mk_mach(common.ty_u16); }
-                case ('l') { ret ty.mk_mach(common.ty_u32); }
-                case ('d') { ret ty.mk_mach(common.ty_u64); }
-                case ('B') { ret ty.mk_mach(common.ty_i8); }
-                case ('W') { ret ty.mk_mach(common.ty_i16); }
-                case ('L') { ret ty.mk_mach(common.ty_i32); }
-                case ('D') { ret ty.mk_mach(common.ty_i64); }
-                case ('f') { ret ty.mk_mach(common.ty_f32); }
-                case ('F') { ret ty.mk_mach(common.ty_f64); }
+                case ('b') { ret ty.mk_mach(st.tystore, common.ty_u8); }
+                case ('w') { ret ty.mk_mach(st.tystore, common.ty_u16); }
+                case ('l') { ret ty.mk_mach(st.tystore, common.ty_u32); }
+                case ('d') { ret ty.mk_mach(st.tystore, common.ty_u64); }
+                case ('B') { ret ty.mk_mach(st.tystore, common.ty_i8); }
+                case ('W') { ret ty.mk_mach(st.tystore, common.ty_i16); }
+                case ('L') { ret ty.mk_mach(st.tystore, common.ty_i32); }
+                case ('D') { ret ty.mk_mach(st.tystore, common.ty_i64); }
+                case ('f') { ret ty.mk_mach(st.tystore, common.ty_f32); }
+                case ('F') { ret ty.mk_mach(st.tystore, common.ty_f64); }
             }
         }
-        case ('c') { ret ty.mk_char(); }
-        case ('s') { ret ty.mk_str(); }
+        case ('c') { ret ty.mk_char(st.tystore); }
+        case ('s') { ret ty.mk_str(st.tystore); }
         case ('t') {
             check(next(st) as char == '[');
             auto def = parse_def(st, sd);
@@ -105,13 +106,13 @@ fn parse_ty(@pstate st, str_def sd) -> @ty.t {
                 params += vec(parse_ty(st, sd));
             }
             st.pos = st.pos + 1u;
-            ret ty.mk_tag(def, params);
+            ret ty.mk_tag(st.tystore, def, params);
         }
-        case ('p') { ret ty.mk_param(parse_int(st) as uint); }
-        case ('@') { ret ty.mk_box(parse_mt(st, sd)); }
-        case ('V') { ret ty.mk_vec(parse_mt(st, sd)); }
-        case ('P') { ret ty.mk_port(parse_ty(st, sd)); }
-        case ('C') { ret ty.mk_chan(parse_ty(st, sd)); }
+        case ('p') { ret ty.mk_param(st.tystore, parse_int(st) as uint); }
+        case ('@') { ret ty.mk_box(st.tystore, parse_mt(st, sd)); }
+        case ('V') { ret ty.mk_vec(st.tystore, parse_mt(st, sd)); }
+        case ('P') { ret ty.mk_port(st.tystore, parse_ty(st, sd)); }
+        case ('C') { ret ty.mk_chan(st.tystore, parse_ty(st, sd)); }
         case ('T') {
             check(next(st) as char == '[');
             let vec[ty.mt] params = vec();
@@ -119,7 +120,7 @@ fn parse_ty(@pstate st, str_def sd) -> @ty.t {
                 params += vec(parse_mt(st, sd));
             }
             st.pos = st.pos + 1u;
-            ret ty.mk_tup(params);
+            ret ty.mk_tup(st.tystore, params);
         }
         case ('R') {
             check(next(st) as char == '[');
@@ -133,15 +134,15 @@ fn parse_ty(@pstate st, str_def sd) -> @ty.t {
                 fields += vec(rec(ident=name, mt=parse_mt(st, sd)));
             }
             st.pos = st.pos + 1u;
-            ret ty.mk_rec(fields);
+            ret ty.mk_rec(st.tystore, fields);
         }
         case ('F') {
             auto func = parse_ty_fn(st, sd);
-            ret ty.mk_fn(ast.proto_fn, func._0, func._1);
+            ret ty.mk_fn(st.tystore, ast.proto_fn, func._0, func._1);
         }
         case ('W') {
             auto func = parse_ty_fn(st, sd);
-            ret ty.mk_fn(ast.proto_iter, func._0, func._1);
+            ret ty.mk_fn(st.tystore, ast.proto_iter, func._0, func._1);
         }
         case ('N') {
             auto abi;
@@ -151,7 +152,7 @@ fn parse_ty(@pstate st, str_def sd) -> @ty.t {
                 case ('l') {abi = ast.native_abi_llvm;}
             }
             auto func = parse_ty_fn(st, sd);
-            ret ty.mk_native_fn(abi,func._0,func._1);
+            ret ty.mk_native_fn(st.tystore,abi,func._0,func._1);
         }
         case ('O') {
             check(next(st) as char == '[');
@@ -173,11 +174,11 @@ fn parse_ty(@pstate st, str_def sd) -> @ty.t {
                                    output=func._1));
             }
             st.pos += 1u;
-            ret ty.mk_obj(methods);
+            ret ty.mk_obj(st.tystore, methods);
         }
-        case ('X') { ret ty.mk_var(parse_int(st)); }
-        case ('E') { ret ty.mk_native(); }
-        case ('Y') { ret ty.mk_type(); }
+        case ('X') { ret ty.mk_var(st.tystore, parse_int(st)); }
+        case ('E') { ret ty.mk_native(st.tystore); }
+        case ('Y') { ret ty.mk_type(st.tystore); }
     }
 }
 
@@ -330,7 +331,7 @@ fn variant_tag_id(&ebml.doc d) -> ast.def_id {
     ret parse_def_id(ebml.doc_data(tagdoc));
 }
 
-fn item_type(&ebml.doc item, int this_cnum) -> @ty.t {
+fn item_type(&ebml.doc item, int this_cnum, @ty.type_store tystore) -> @ty.t {
     fn parse_external_def_id(int this_cnum, str s) -> ast.def_id {
         // FIXME: This is completely wrong when linking against a crate
         // that, in turn, links against another crate. We need a mapping
@@ -343,7 +344,7 @@ fn item_type(&ebml.doc item, int this_cnum) -> @ty.t {
 
     auto tp = ebml.get_doc(item, metadata.tag_items_data_item_type);
     auto s = _str.unsafe_from_bytes(ebml.doc_data(tp));
-    ret parse_ty_str(s, bind parse_external_def_id(this_cnum, _));
+    ret parse_ty_str(s, bind parse_external_def_id(this_cnum, _), tystore);
 }
 
 fn item_ty_param_count(&ebml.doc item, int this_cnum) -> uint {
@@ -505,12 +506,12 @@ fn lookup_def(session.session sess, int cnum, vec[ast.ident] path)
     ret some[ast.def](def);
 }
 
-fn get_type(session.session sess, ast.def_id def)
+fn get_type(session.session sess, @ty.type_store tystore, ast.def_id def)
         -> ty.ty_param_count_and_ty {
     auto external_crate_id = def._0;
     auto data = sess.get_external_crate(external_crate_id).data;
     auto item = lookup_item(def._1, data);
-    auto t = item_type(item, external_crate_id);
+    auto t = item_type(item, external_crate_id, tystore);
 
     auto tp_count;
     auto kind_ch = item_kind(item);
@@ -531,8 +532,9 @@ fn get_symbol(session.session sess, ast.def_id def) -> str {
     ret item_symbol(item);
 }
 
-fn get_tag_variants(session.session sess, ast.def_id def)
-        -> vec[trans.variant_info] {
+fn get_tag_variants(session.session sess,
+                    @ty.type_store tystore,
+                    ast.def_id def) -> vec[trans.variant_info] {
     auto external_crate_id = def._0;
     auto data = sess.get_external_crate(external_crate_id).data;
     auto items = ebml.get_doc(ebml.new_doc(data), metadata.tag_items);
@@ -542,7 +544,7 @@ fn get_tag_variants(session.session sess, ast.def_id def)
     auto variant_ids = tag_variant_ids(item, external_crate_id);
     for (ast.def_id did in variant_ids) {
         auto item = find_item(did._1, items);
-        auto ctor_ty = item_type(item, external_crate_id);
+        auto ctor_ty = item_type(item, external_crate_id, tystore);
         let vec[@ty.t] arg_tys = vec();
         alt (ctor_ty.struct) {
             case (ty.ty_fn(_, ?args, _)) {
diff --git a/src/comp/middle/metadata.rs b/src/comp/middle/metadata.rs
index 3a3d3105c68..4ea6b3e86ca 100644
--- a/src/comp/middle/metadata.rs
+++ b/src/comp/middle/metadata.rs
@@ -461,7 +461,7 @@ fn encode_info_for_native_item(@trans.crate_ctxt cx, &ebml.writer ebml_w,
         case (ast.native_item_ty(_, ?did)) {
             encode_def_id(ebml_w, did);
             encode_kind(ebml_w, 'T' as u8);
-            encode_type(ebml_w, ty.mk_native());
+            encode_type(ebml_w, ty.mk_native(cx.tystore));
         }
         case (ast.native_item_fn(_, _, _, ?tps, ?did, ?ann)) {
             encode_def_id(ebml_w, did);
diff --git a/src/comp/middle/trans.rs b/src/comp/middle/trans.rs
index 439e563ebac..1153047d60e 100644
--- a/src/comp/middle/trans.rs
+++ b/src/comp/middle/trans.rs
@@ -112,7 +112,8 @@ state type crate_ctxt = rec(session.session sess,
                             hashmap[@ty.t, TypeRef] lltypes,
                             @glue_fns glues,
                             namegen names,
-                            std.sha1.sha1 sha);
+                            std.sha1.sha1 sha,
+                            @ty.type_store tystore);
 
 type local_ctxt = rec(vec[str] path,
                       vec[str] module_path,
@@ -638,7 +639,7 @@ fn type_of_fn_full(@crate_ctxt cx,
             vec(T_fn_pair(cx.tn,
                           type_of_fn_full(cx, ast.proto_fn, none[TypeRef],
                                           vec(rec(mode=ast.val, ty=output)),
-                                          ty.mk_nil(), 0u)));
+                                          ty.mk_nil(cx.tystore), 0u)));
     }
 
     // ... then explicit args.
@@ -1145,17 +1146,17 @@ fn array_alloca(@block_ctxt cx, TypeRef t, ValueRef n) -> ValueRef {
 // to have (a) the same size as the type that was passed in; (b) to be non-
 // recursive. This is done by replacing all boxes in a type with boxed unit
 // types.
-fn simplify_type(@ty.t typ) -> @ty.t {
-    fn simplifier(@ty.t typ) -> @ty.t {
+fn simplify_type(@crate_ctxt ccx, @ty.t typ) -> @ty.t {
+    fn simplifier(@crate_ctxt ccx, @ty.t typ) -> @ty.t {
         alt (typ.struct) {
             case (ty.ty_box(_)) {
-                ret ty.mk_imm_box(ty.mk_nil());
+                ret ty.mk_imm_box(ccx.tystore, ty.mk_nil(ccx.tystore));
             }
             case (_) { ret typ; }
         }
     }
-    auto f = simplifier;
-    ret ty.fold_ty(f, typ);
+    auto f = bind simplifier(ccx, _);
+    ret ty.fold_ty(ccx.tystore, f, typ);
 }
 
 // Computes the size of the data part of a non-dynamically-sized tag.
@@ -1186,11 +1187,12 @@ fn static_size_of_tag(@crate_ctxt cx, @ty.t t) -> uint {
     auto max_size = 0u;
     auto variants = tag_variants(cx, tid);
     for (variant_info variant in variants) {
-        auto tup_ty = simplify_type(ty.mk_imm_tup(variant.args));
+        auto tup_ty = simplify_type(cx,
+                                    ty.mk_imm_tup(cx.tystore, variant.args));
 
         // Perform any type parameter substitutions.
-        tup_ty = ty.bind_params_in_type(tup_ty);
-        tup_ty = ty.substitute_type_params(subtys, tup_ty);
+        tup_ty = ty.bind_params_in_type(cx.tystore, tup_ty);
+        tup_ty = ty.substitute_type_params(cx.tystore, subtys, tup_ty);
 
         // Here we possibly do a recursive call.
         auto this_size = llsize_of_real(cx, type_of(cx, tup_ty));
@@ -1262,8 +1264,10 @@ fn dynamic_size_of(@block_ctxt cx, @ty.t t) -> result {
                 let vec[@ty.t] raw_tys = variant.args;
                 let vec[@ty.t] tys = vec();
                 for (@ty.t raw_ty in raw_tys) {
-                    auto t = ty.bind_params_in_type(raw_ty);
-                    t = ty.substitute_type_params(tps, t);
+                    auto t = ty.bind_params_in_type(cx.fcx.lcx.ccx.tystore,
+                                                    raw_ty);
+                    t = ty.substitute_type_params(cx.fcx.lcx.ccx.tystore, tps,
+                                                  t);
                     tys += vec(t);
                 }
 
@@ -1402,7 +1406,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 = ty.mk_imm_tup(s.prefix);
+    auto prefix_ty = ty.mk_imm_tup(cx.fcx.lcx.ccx.tystore, s.prefix);
     auto bcx = cx;
     auto sz = size_of(bcx, prefix_ty);
     bcx = sz.bcx;
@@ -1433,12 +1437,13 @@ fn GEP_tag(@block_ctxt cx,
     // Synthesize a tuple type so that GEP_tup_like() can work its magic.
     // Separately, store the type of the element we're interested in.
     auto arg_tys = variant.args;
-    auto elem_ty = ty.mk_nil(); // typestate infelicity
+    auto elem_ty = ty.mk_nil(cx.fcx.lcx.ccx.tystore); // typestate infelicity
     auto i = 0;
     let vec[@ty.t] true_arg_tys = vec();
     for (@ty.t aty in arg_tys) {
-        auto arg_ty = ty.bind_params_in_type(aty);
-        arg_ty = ty.substitute_type_params(ty_substs, arg_ty);
+        auto arg_ty = ty.bind_params_in_type(cx.fcx.lcx.ccx.tystore, aty);
+        arg_ty = ty.substitute_type_params(cx.fcx.lcx.ccx.tystore, ty_substs,
+                                           arg_ty);
         true_arg_tys += vec(arg_ty);
         if (i == ix) {
             elem_ty = arg_ty;
@@ -1447,7 +1452,7 @@ fn GEP_tag(@block_ctxt cx,
         i += 1;
     }
 
-    auto tup_ty = ty.mk_imm_tup(true_arg_tys);
+    auto tup_ty = ty.mk_imm_tup(cx.fcx.lcx.ccx.tystore, 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).
@@ -1487,8 +1492,10 @@ 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 = ty.mk_imm_tup(vec(ty.mk_int(), t));
-    auto box_ptr = ty.mk_imm_box(t);
+    auto boxed_body = ty.mk_imm_tup(cx.fcx.lcx.ccx.tystore,
+                                    vec(ty.mk_int(cx.fcx.lcx.ccx.tystore),
+                                        t));
+    auto box_ptr = ty.mk_imm_box(cx.fcx.lcx.ccx.tystore, t);
     auto sz = size_of(cx, boxed_body);
     auto llty = type_of(cx.fcx.lcx.ccx, box_ptr);
     ret trans_raw_malloc(sz.bcx, llty, sz.val);
@@ -2116,7 +2123,7 @@ fn make_cmp_glue(@block_ctxt cx,
             auto min_len = umin(r.bcx, vec_fill(r.bcx, lhs),
                                 vec_fill(r.bcx, rhs));
             auto rhs_lim = r.bcx.build.GEP(rhs_p0, vec(min_len));
-            auto elt_ty = ty.sequence_element_type(t);
+            auto elt_ty = ty.sequence_element_type(cx.fcx.lcx.ccx.tystore, t);
             r = size_of(r.bcx, elt_ty);
             r = iter_sequence_raw(r.bcx, lhs_p0, rhs_p0, rhs_lim, r.val,
                                   bind inner(next, true, flag, llop,
@@ -2250,7 +2257,7 @@ type variant_info = rec(vec[@ty.t] args, @ty.t ctor_ty, ast.def_id id);
 // Returns information about the variants in a tag.
 fn tag_variants(@crate_ctxt cx, ast.def_id id) -> vec[variant_info] {
     if (cx.sess.get_targ_crate_num() != id._0) {
-        ret creader.get_tag_variants(cx.sess, id);
+        ret creader.get_tag_variants(cx.sess, cx.tystore, id);
     }
 
     check (cx.items.contains_key(id));
@@ -2333,8 +2340,8 @@ fn iter_structural_ty_full(@block_ctxt cx,
                   val_pair_and_ty_fn f) -> result {
         auto box_a_ptr = cx.build.Load(box_a_cell);
         auto box_b_ptr = cx.build.Load(box_b_cell);
-        auto tnil = ty.mk_nil();
-        auto tbox = ty.mk_imm_box(tnil);
+        auto tnil = ty.mk_nil(cx.fcx.lcx.ccx.tystore);
+        auto tbox = ty.mk_imm_box(cx.fcx.lcx.ccx.tystore, tnil);
 
         auto inner_cx = new_sub_block_ctxt(cx, "iter box");
         auto next_cx = new_sub_block_ctxt(cx, "next");
@@ -2399,7 +2406,8 @@ fn iter_structural_ty_full(@block_ctxt cx,
             // NB: we must hit the discriminant first so that structural
             // comparison know not to proceed when the discriminants differ.
             auto bcx = cx;
-            bcx = f(bcx, lldiscrim_a, lldiscrim_b, ty.mk_int()).bcx;
+            bcx = f(bcx, lldiscrim_a, lldiscrim_b,
+                    ty.mk_int(cx.fcx.lcx.ccx.tystore)).bcx;
 
             auto unr_cx = new_sub_block_ctxt(bcx, "tag-iter-unr");
             unr_cx.build.Unreachable();
@@ -2435,9 +2443,10 @@ fn iter_structural_ty_full(@block_ctxt cx,
                                 auto llfldp_b = rslt.val;
                                 variant_cx = rslt.bcx;
 
-                                auto ty_subst = ty.bind_params_in_type(a.ty);
-                                ty_subst =
-                                    ty.substitute_type_params(tps, ty_subst);
+                                auto ty_subst = ty.bind_params_in_type(
+                                    cx.fcx.lcx.ccx.tystore, a.ty);
+                                ty_subst = ty.substitute_type_params(
+                                    cx.fcx.lcx.ccx.tystore, tps, ty_subst);
 
                                 auto llfld_a =
                                     load_if_immediate(variant_cx,
@@ -2619,7 +2628,7 @@ fn iter_sequence(@block_ctxt cx,
             ret iter_sequence_body(cx, v, elt.ty, f, false);
         }
         case (ty.ty_str) {
-            auto et = ty.mk_mach(common.ty_u8);
+            auto et = ty.mk_mach(cx.fcx.lcx.ccx.tystore, common.ty_u8);
             ret iter_sequence_body(cx, v, et, f, true);
         }
         case (_) { fail; }
@@ -2843,11 +2852,13 @@ fn trans_lit(@crate_ctxt cx, &ast.lit lit, &ast.ann ann) -> ValueRef {
 fn target_type(@crate_ctxt cx, @ty.t t) -> @ty.t {
     alt (t.struct) {
         case (ty.ty_int) {
-            auto struct_ty = ty.mk_mach(cx.sess.get_targ_cfg().int_type);
+            auto struct_ty = ty.mk_mach(cx.tystore,
+                                        cx.sess.get_targ_cfg().int_type);
             ret ty.copy_cname(struct_ty, t);
         }
         case (ty.ty_uint) {
-            auto struct_ty = ty.mk_mach(cx.sess.get_targ_cfg().uint_type);
+            auto struct_ty = ty.mk_mach(cx.tystore,
+                                        cx.sess.get_targ_cfg().uint_type);
             ret ty.copy_cname(struct_ty, t);
         }
         case (_) { /* fall through */ }
@@ -2858,7 +2869,7 @@ fn target_type(@crate_ctxt cx, @ty.t t) -> @ty.t {
 
 // Converts an annotation to a type
 fn node_ann_type(@crate_ctxt cx, &ast.ann a) -> @ty.t {
-    ret target_type(cx, ty.ann_to_monotype(a));
+    ret target_type(cx, ty.ann_to_monotype(cx.tystore, a));
 }
 
 fn node_ann_ty_params(&ast.ann a) -> vec[@ty.t] {
@@ -2887,19 +2898,22 @@ fn trans_unary(@block_ctxt cx, ast.unop op,
                @ast.expr e, &ast.ann a) -> result {
 
     auto sub = trans_expr(cx, e);
-    auto e_ty = ty.expr_ty(e);
+    auto e_ty = ty.expr_ty(cx.fcx.lcx.ccx.tystore, e);
 
     alt (op) {
         case (ast.bitnot) {
-            sub = autoderef(sub.bcx, sub.val, ty.expr_ty(e));
+            sub = autoderef(sub.bcx, sub.val,
+                            ty.expr_ty(cx.fcx.lcx.ccx.tystore, e));
             ret res(sub.bcx, sub.bcx.build.Not(sub.val));
         }
         case (ast.not) {
-            sub = autoderef(sub.bcx, sub.val, ty.expr_ty(e));
+            sub = autoderef(sub.bcx, sub.val,
+                            ty.expr_ty(cx.fcx.lcx.ccx.tystore, e));
             ret res(sub.bcx, sub.bcx.build.Not(sub.val));
         }
         case (ast.neg) {
-            sub = autoderef(sub.bcx, sub.val, ty.expr_ty(e));
+            sub = autoderef(sub.bcx, sub.val,
+                            ty.expr_ty(cx.fcx.lcx.ccx.tystore, e));
             if(e_ty.struct == ty.ty_float) {
                 ret res(sub.bcx, sub.bcx.build.FNeg(sub.val));
             }
@@ -2908,7 +2922,7 @@ fn trans_unary(@block_ctxt cx, ast.unop op,
             }
         }
         case (ast.box(_)) {
-            auto e_ty = ty.expr_ty(e);
+            auto e_ty = ty.expr_ty(cx.fcx.lcx.ccx.tystore, e);
             auto e_val = sub.val;
             auto box_ty = node_ann_type(sub.bcx.fcx.lcx.ccx, a);
             sub = trans_malloc_boxed(sub.bcx, e_ty);
@@ -2988,7 +3002,7 @@ fn trans_compare(@block_ctxt cx0, ast.binop op, @ty.t t0,
 fn trans_vec_append(@block_ctxt cx, @ty.t t,
                     ValueRef lhs, ValueRef rhs) -> result {
 
-    auto elt_ty = ty.sequence_element_type(t);
+    auto elt_ty = ty.sequence_element_type(cx.fcx.lcx.ccx.tystore, t);
 
     auto skip_null = C_bool(false);
     alt (t.struct) {
@@ -3160,11 +3174,13 @@ fn trans_binary(@block_ctxt cx, ast.binop op,
         case (ast.and) {
             // Lazy-eval and
             auto lhs_res = trans_expr(cx, a);
-            lhs_res = autoderef(lhs_res.bcx, lhs_res.val, ty.expr_ty(a));
+            lhs_res = autoderef(lhs_res.bcx, lhs_res.val,
+                                ty.expr_ty(cx.fcx.lcx.ccx.tystore, a));
 
             auto rhs_cx = new_scope_block_ctxt(cx, "rhs");
             auto rhs_res = trans_expr(rhs_cx, b);
-            rhs_res = autoderef(rhs_res.bcx, rhs_res.val, ty.expr_ty(b));
+            rhs_res = autoderef(rhs_res.bcx, rhs_res.val,
+                                ty.expr_ty(cx.fcx.lcx.ccx.tystore, b));
 
             auto lhs_false_cx = new_scope_block_ctxt(cx, "lhs false");
             auto lhs_false_res = res(lhs_false_cx, C_bool(false));
@@ -3180,11 +3196,13 @@ fn trans_binary(@block_ctxt cx, ast.binop op,
         case (ast.or) {
             // Lazy-eval or
             auto lhs_res = trans_expr(cx, a);
-            lhs_res = autoderef(lhs_res.bcx, lhs_res.val, ty.expr_ty(a));
+            lhs_res = autoderef(lhs_res.bcx, lhs_res.val,
+                                ty.expr_ty(cx.fcx.lcx.ccx.tystore, a));
 
             auto rhs_cx = new_scope_block_ctxt(cx, "rhs");
             auto rhs_res = trans_expr(rhs_cx, b);
-            rhs_res = autoderef(rhs_res.bcx, rhs_res.val, ty.expr_ty(b));
+            rhs_res = autoderef(rhs_res.bcx, rhs_res.val,
+                                ty.expr_ty(cx.fcx.lcx.ccx.tystore, b));
 
             auto lhs_true_cx = new_scope_block_ctxt(cx, "lhs true");
             auto lhs_true_res = res(lhs_true_cx, C_bool(true));
@@ -3200,10 +3218,10 @@ fn trans_binary(@block_ctxt cx, ast.binop op,
         case (_) {
             // Remaining cases are eager:
             auto lhs = trans_expr(cx, a);
-            auto lhty = ty.expr_ty(a);
+            auto lhty = ty.expr_ty(cx.fcx.lcx.ccx.tystore, a);
             lhs = autoderef(lhs.bcx, lhs.val, lhty);
             auto rhs = trans_expr(lhs.bcx, b);
-            auto rhty = ty.expr_ty(b);
+            auto rhty = ty.expr_ty(cx.fcx.lcx.ccx.tystore, b);
             rhs = autoderef(rhs.bcx, rhs.val, rhty);
             ret trans_eager_binop(rhs.bcx, op,
                                   autoderefed_ty(lhty),
@@ -3281,7 +3299,7 @@ fn trans_if(@block_ctxt cx, @ast.expr cond,
             // If we have an else expression, then the entire
             // if expression can have a non-nil type.
             // FIXME: This isn't quite right, particularly re: dynamic types
-            auto expr_ty = ty.expr_ty(elexpr);
+            auto expr_ty = ty.expr_ty(cx.fcx.lcx.ccx.tystore, elexpr);
             if (ty.type_has_dynamic_size(expr_ty)) {
                 expr_llty = T_typaram_ptr(cx.fcx.lcx.ccx.tn);
             } else {
@@ -3338,7 +3356,7 @@ fn trans_for(@block_ctxt cx,
     }
 
     auto next_cx = new_sub_block_ctxt(cx, "next");
-    auto seq_ty = ty.expr_ty(seq);
+    auto seq_ty = ty.expr_ty(cx.fcx.lcx.ccx.tystore, seq);
     auto seq_res = trans_expr(cx, seq);
     auto it = iter_sequence(seq_res.bcx, seq_res.val, seq_ty,
                             bind inner(_, local, _, _, body, next_cx));
@@ -3440,7 +3458,7 @@ fn trans_for_each(@block_ctxt cx,
 
     auto lcx = cx.fcx.lcx;
     // FIXME: possibly support alias-mode here?
-    auto decl_ty = ty.mk_nil();
+    auto decl_ty = ty.mk_nil(lcx.ccx.tystore);
     auto decl_id;
     alt (decl.node) {
         case (ast.decl_local(?local)) {
@@ -3527,7 +3545,7 @@ fn trans_for_each(@block_ctxt cx,
     auto iter_body_llty = type_of_fn_full(lcx.ccx, ast.proto_fn,
                                           none[TypeRef],
                                           vec(rec(mode=ast.val, ty=decl_ty)),
-                                          ty.mk_nil(), 0u);
+                                          ty.mk_nil(lcx.ccx.tystore), 0u);
 
     let ValueRef lliterbody = decl_internal_fastcall_fn(lcx.ccx.llmod,
                                                        s, iter_body_llty);
@@ -3715,8 +3733,7 @@ fn trans_pat_match(@block_ctxt cx, @ast.pat pat, ValueRef llval,
                     matched_cx = rslt.bcx;
 
                     auto llsubval = load_if_immediate(matched_cx,
-                                                         llsubvalptr,
-                                                         pat_ty(subpat));
+                        llsubvalptr, pat_ty(cx.fcx.lcx.ccx.tystore, subpat));
                     auto subpat_res = trans_pat_match(matched_cx, subpat,
                                                       llsubval, next_cx);
                     matched_cx = subpat_res.bcx;
@@ -3770,7 +3787,7 @@ fn trans_pat_binding(@block_ctxt cx, @ast.pat pat, ValueRef llval)
                 auto llsubvalptr = rslt.val;
 
                 auto llsubval = load_if_immediate(this_cx, llsubvalptr,
-                                                     pat_ty(subpat));
+                    pat_ty(cx.fcx.lcx.ccx.tystore, subpat));
                 auto subpat_res = trans_pat_binding(this_cx, subpat,
                                                     llsubval);
                 this_cx = subpat_res.bcx;
@@ -3959,16 +3976,19 @@ fn trans_path(@block_ctxt cx, &ast.path p, &option.t[ast.def] dopt,
                 }
                 case (ast.def_fn(?did)) {
                     auto tyt = ty.lookup_item_type(cx.fcx.lcx.ccx.sess,
+                        cx.fcx.lcx.ccx.tystore,
                         cx.fcx.lcx.ccx.type_cache, did);
                     ret lval_generic_fn(cx, tyt, did, ann);
                 }
                 case (ast.def_obj(?did)) {
                     auto tyt = ty.lookup_item_type(cx.fcx.lcx.ccx.sess,
+                        cx.fcx.lcx.ccx.tystore,
                         cx.fcx.lcx.ccx.type_cache, did);
                     ret lval_generic_fn(cx, tyt, did, ann);
                 }
                 case (ast.def_variant(?tid, ?vid)) {
                     auto v_tyt = ty.lookup_item_type(cx.fcx.lcx.ccx.sess,
+                        cx.fcx.lcx.ccx.tystore,
                         cx.fcx.lcx.ccx.type_cache, vid);
                     alt (v_tyt._1.struct) {
                         case (ty.ty_fn(_, _, _)) {
@@ -4010,6 +4030,7 @@ fn trans_path(@block_ctxt cx, &ast.path p, &option.t[ast.def] dopt,
                 }
                 case (ast.def_native_fn(?did)) {
                     auto tyt = ty.lookup_item_type(cx.fcx.lcx.ccx.sess,
+                        cx.fcx.lcx.ccx.tystore,
                         cx.fcx.lcx.ccx.type_cache, did);
                     ret lval_generic_fn(cx, tyt, did, ann);
                 }
@@ -4054,7 +4075,8 @@ fn trans_field(@block_ctxt cx, &ast.span sp, ValueRef v, @ty.t t0,
                                                 C_int(ix as int)));
 
             auto lvo = lval_mem(r.bcx, v);
-            let @ty.t fn_ty = ty.method_ty_to_fn_ty(methods.(ix));
+            let @ty.t fn_ty = ty.method_ty_to_fn_ty(cx.fcx.lcx.ccx.tystore,
+                                                    methods.(ix));
             ret rec(llobj = some[ValueRef](r.val),
                     method_ty = some[@ty.t](fn_ty)
                     with lvo);
@@ -4068,7 +4090,7 @@ fn trans_index(@block_ctxt cx, &ast.span sp, @ast.expr base,
                @ast.expr idx, &ast.ann ann) -> lval_result {
 
     auto lv = trans_expr(cx, base);
-    lv = autoderef(lv.bcx, lv.val, ty.expr_ty(base));
+    lv = autoderef(lv.bcx, lv.val, ty.expr_ty(cx.fcx.lcx.ccx.tystore, base));
     auto ix = trans_expr(lv.bcx, idx);
     auto v = lv.val;
     auto bcx = ix.bcx;
@@ -4134,7 +4156,7 @@ fn trans_lval(@block_ctxt cx, @ast.expr e) -> lval_result {
         }
         case (ast.expr_field(?base, ?ident, ?ann)) {
             auto r = trans_expr(cx, base);
-            auto t = ty.expr_ty(base);
+            auto t = ty.expr_ty(cx.fcx.lcx.ccx.tystore, base);
             ret trans_field(r.bcx, e.span, r.val, t, ident, ann);
         }
         case (ast.expr_index(?base, ?idx, ?ann)) {
@@ -4178,7 +4200,7 @@ fn trans_cast(@block_ctxt cx, @ast.expr e, &ast.ann ann) -> result {
     auto lldsttype = type_of(cx.fcx.lcx.ccx, t);
     if (!ty.type_is_fp(t)) {
         // TODO: native-to-native casts
-        if (ty.type_is_native(ty.expr_ty(e))) {
+        if (ty.type_is_native(ty.expr_ty(cx.fcx.lcx.ccx.tystore, e))) {
             e_res.val = e_res.bcx.build.PtrToInt(e_res.val, lldsttype);
         } else if (ty.type_is_native(t)) {
             e_res.val = e_res.bcx.build.IntToPtr(e_res.val, lldsttype);
@@ -4226,7 +4248,8 @@ fn trans_bind_thunk(@local_ctxt cx,
     auto bcx = new_top_block_ctxt(fcx);
     auto lltop = bcx.llbb;
 
-    auto llclosure_ptr_ty = type_of(cx.ccx, ty.mk_imm_box(closure_ty));
+    auto llclosure_ptr_ty =
+        type_of(cx.ccx, ty.mk_imm_box(cx.ccx.tystore, closure_ty));
     auto llclosure = bcx.build.PointerCast(fcx.llenv, llclosure_ptr_ty);
 
     auto lltarget = GEP_tup_like(bcx, closure_ty, llclosure,
@@ -4368,7 +4391,7 @@ fn trans_bind(@block_ctxt cx, @ast.expr f,
         let vec[ValueRef] lltydescs;
         alt (f_res.generic) {
             case (none[generic_info]) {
-                outgoing_fty = ty.expr_ty(f);
+                outgoing_fty = ty.expr_ty(cx.fcx.lcx.ccx.tystore, f);
                 lltydescs = vec();
             }
             case (some[generic_info](?ginfo)) {
@@ -4395,18 +4418,20 @@ fn trans_bind(@block_ctxt cx, @ast.expr f,
                 bcx = arg.bcx;
 
                 _vec.push[ValueRef](bound_vals, arg.val);
-                _vec.push[@ty.t](bound_tys, ty.expr_ty(e));
+                _vec.push[@ty.t](bound_tys,
+                                 ty.expr_ty(cx.fcx.lcx.ccx.tystore, e));
 
                 i += 1u;
             }
 
             // Synthesize a closure type.
-            let @ty.t bindings_ty = ty.mk_imm_tup(bound_tys);
+            let @ty.t bindings_ty = ty.mk_imm_tup(cx.fcx.lcx.ccx.tystore,
+                                                  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
             // it constructs.
-            let @ty.t tydesc_ty = ty.mk_type();
+            let @ty.t tydesc_ty = ty.mk_type(cx.fcx.lcx.ccx.tystore);
 
             let vec[@ty.t] captured_tys =
                 _vec.init_elt[@ty.t](tydesc_ty, ty_param_count);
@@ -4415,9 +4440,10 @@ fn trans_bind(@block_ctxt cx, @ast.expr f,
                 vec(tydesc_ty,
                     outgoing_fty,
                     bindings_ty,
-                    ty.mk_imm_tup(captured_tys));
+                    ty.mk_imm_tup(cx.fcx.lcx.ccx.tystore, captured_tys));
 
-            let @ty.t closure_ty = ty.mk_imm_tup(closure_tys);
+            let @ty.t closure_ty = ty.mk_imm_tup(cx.fcx.lcx.ccx.tystore,
+                                                 closure_tys);
 
             auto r = trans_malloc_boxed(bcx, closure_ty);
             auto box = r.val;
@@ -4622,7 +4648,7 @@ fn trans_args(@block_ctxt cx,
         auto mode = args.(i).mode;
 
         auto val;
-        if (ty.type_is_structural(ty.expr_ty(e))) {
+        if (ty.type_is_structural(ty.expr_ty(cx.fcx.lcx.ccx.tystore, e))) {
             auto re = trans_expr(bcx, e);
             val = re.val;
             bcx = re.bcx;
@@ -4632,7 +4658,8 @@ fn trans_args(@block_ctxt cx,
                 lv = trans_lval(bcx, e);
             } else {
                 auto r = trans_expr(bcx, e);
-                if (type_is_immediate(ty.expr_ty(e))) {
+                if (type_is_immediate(ty.expr_ty(cx.fcx.lcx.ccx.tystore,
+                                                 e))) {
                     lv = lval_val(r.bcx, r.val);
                 } else {
                     lv = lval_mem(r.bcx, r.val);
@@ -4658,7 +4685,8 @@ fn trans_args(@block_ctxt cx,
             auto lldestty = arg_tys.(i);
             if (mode == ast.val) {
                 // FIXME: we'd prefer to use &&, but rustboot doesn't like it
-                if (ty.type_is_structural(ty.expr_ty(e))) {
+                if (ty.type_is_structural(ty.expr_ty(cx.fcx.lcx.ccx.tystore,
+                                                     e))) {
                     lldestty = T_ptr(lldestty);
                 }
             }
@@ -4668,7 +4696,8 @@ fn trans_args(@block_ctxt cx,
 
         if (mode == ast.val) {
             // FIXME: we'd prefer to use &&, but rustboot doesn't like it
-            if (ty.type_is_structural(ty.expr_ty(e))) {
+            if (ty.type_is_structural(ty.expr_ty(cx.fcx.lcx.ccx.tystore,
+                                                 e))) {
                 // Until here we've been treating structures by pointer;
                 // we are now passing it as an arg, so need to load it.
                 val = bcx.build.Load(val);
@@ -4723,7 +4752,7 @@ fn trans_call(@block_ctxt cx, @ast.expr f,
         }
 
         case (_) {
-            fn_ty = ty.expr_ty(f);
+            fn_ty = ty.expr_ty(cx.fcx.lcx.ccx.tystore, f);
 
         }
 
@@ -4776,7 +4805,7 @@ fn trans_tup(@block_ctxt cx, vec[ast.elt] elts,
     let int i = 0;
 
     for (ast.elt e in elts) {
-        auto e_ty = ty.expr_ty(e.expr);
+        auto e_ty = ty.expr_ty(cx.fcx.lcx.ccx.tystore, e.expr);
         auto src_res = trans_expr(bcx, e.expr);
         bcx = src_res.bcx;
         auto dst_res = GEP_tup_like(bcx, t, tup_val, vec(0, i));
@@ -4819,7 +4848,8 @@ fn trans_vec(@block_ctxt cx, vec[@ast.expr] args,
                                            C_int(abi.vec_elt_data)));
 
     auto pseudo_tup_ty =
-        ty.mk_imm_tup(_vec.init_elt[@ty.t](unit_ty,
+        ty.mk_imm_tup(cx.fcx.lcx.ccx.tystore,
+                      _vec.init_elt[@ty.t](unit_ty,
                                            _vec.len[@ast.expr](args)));
     let int i = 0;
 
@@ -5076,7 +5106,7 @@ fn trans_expr(@block_ctxt cx, @ast.expr e) -> result {
     // lval cases fall through to trans_lval and then
     // possibly load the result (if it's non-structural).
 
-    auto t = ty.expr_ty(e);
+    auto t = ty.expr_ty(cx.fcx.lcx.ccx.tystore, e);
     auto sub = trans_lval(cx, e);
     ret res(sub.res.bcx, load_if_immediate(sub.res.bcx, sub.res.val, t));
 }
@@ -5135,7 +5165,7 @@ fn trans_log(int lvl, @block_ctxt cx, @ast.expr e) -> result {
     cx.build.CondBr(test, log_cx.llbb, after_cx.llbb);
 
     auto sub = trans_expr(log_cx, e);
-    auto e_ty = ty.expr_ty(e);
+    auto e_ty = ty.expr_ty(cx.fcx.lcx.ccx.tystore, e);
 
     if (ty.type_is_fp(e_ty)) {
         let TypeRef tr;
@@ -5251,7 +5281,8 @@ fn trans_put(@block_ctxt cx, &option.t[@ast.expr] e) -> result {
 
             auto llarg = r.val;
             bcx = r.bcx;
-            if (ty.type_is_structural(ty.expr_ty(x))) {
+            if (ty.type_is_structural(ty.expr_ty(cx.fcx.lcx.ccx.tystore,
+                                                 x))) {
                 // Until here we've been treating structures by pointer; we
                 // are now passing it as an arg, so need to load it.
                 llarg = bcx.build.Load(llarg);
@@ -5311,7 +5342,7 @@ fn trans_ret(@block_ctxt cx, &option.t[@ast.expr] e) -> result {
 
     alt (e) {
         case (some[@ast.expr](?x)) {
-            auto t = ty.expr_ty(x);
+            auto t = ty.expr_ty(cx.fcx.lcx.ccx.tystore, x);
             auto r = trans_expr(cx, x);
             bcx = r.bcx;
             val = r.val;
@@ -5686,7 +5717,7 @@ fn trans_block(@block_ctxt cx, &ast.block b) -> result {
             if (is_terminated(bcx)) {
                 ret r;
             } else {
-                auto r_ty = ty.expr_ty(e);
+                auto r_ty = ty.expr_ty(cx.fcx.lcx.ccx.tystore, e);
                 if (!ty.type_is_nil(r_ty)) {
                     // The value resulting from the block gets copied into an
                     // alloca created in an outer scope and its refcount
@@ -5917,7 +5948,7 @@ fn populate_fn_ctxt_from_llself(@fn_ctxt fcx, self_vt llself) {
 
     // Synthesize a tuple type for the fields so that GEP_tup_like() can work
     // its magic.
-    auto fields_tup_ty = ty.mk_imm_tup(field_tys);
+    auto fields_tup_ty = ty.mk_imm_tup(fcx.lcx.ccx.tystore, field_tys);
 
     auto n_typarams = _vec.len[ast.ty_param](bcx.fcx.lcx.obj_typarams);
     let TypeRef llobj_box_ty = T_obj_ptr(bcx.fcx.lcx.ccx.tn, n_typarams);
@@ -6142,18 +6173,19 @@ fn trans_obj(@local_ctxt cx, &ast._obj ob, ast.def_id oid,
         }
 
         // Synthesize an obj body type.
-        auto tydesc_ty = ty.mk_type();
+        auto tydesc_ty = ty.mk_type(cx.ccx.tystore);
         let vec[@ty.t] tps = vec();
         for (ast.ty_param tp in ty_params) {
             _vec.push[@ty.t](tps, tydesc_ty);
         }
 
-        let @ty.t typarams_ty = ty.mk_imm_tup(tps);
-        let @ty.t fields_ty = ty.mk_imm_tup(obj_fields);
-        let @ty.t body_ty = ty.mk_imm_tup(vec(tydesc_ty,
+        let @ty.t typarams_ty = ty.mk_imm_tup(cx.ccx.tystore, tps);
+        let @ty.t fields_ty = ty.mk_imm_tup(cx.ccx.tystore, obj_fields);
+        let @ty.t body_ty = ty.mk_imm_tup(cx.ccx.tystore,
+                                          vec(tydesc_ty,
                                               typarams_ty,
                                               fields_ty));
-        let @ty.t boxed_body_ty = ty.mk_imm_box(body_ty);
+        let @ty.t boxed_body_ty = ty.mk_imm_box(cx.ccx.tystore, body_ty);
 
         // Malloc a box for the body.
         auto box = trans_malloc_boxed(bcx, body_ty);
@@ -6255,7 +6287,7 @@ fn trans_tag_variant(@local_ctxt cx, ast.def_id tag_id,
     let vec[@ty.t] ty_param_substs = vec();
     i = 0u;
     for (ast.ty_param tp in ty_params) {
-        ty_param_substs += vec(ty.mk_param(i));
+        ty_param_substs += vec(ty.mk_param(cx.ccx.tystore, i));
         i += 1u;
     }
 
@@ -7450,7 +7482,7 @@ fn create_crate_map(@crate_ctxt ccx) -> ValueRef {
     ret map;
 }
 
-fn trans_crate(session.session sess, @ast.crate crate,
+fn trans_crate(session.session sess, @ast.crate crate, @ty.type_store tystore,
                &ty.type_cache type_cache, str output, bool shared,
                bool optimize, bool verify, output_type ot) {
     auto llmod =
@@ -7496,7 +7528,8 @@ fn trans_crate(session.session sess, @ast.crate crate,
                     lltypes = lltypes,
                     glues = glues,
                     names = namegen(0),
-                    sha = std.sha1.mk_sha1());
+                    sha = std.sha1.mk_sha1(),
+                    tystore = tystore);
     auto cx = new_local_ctxt(ccx);
 
     create_typedefs(ccx);
diff --git a/src/comp/middle/ty.rs b/src/comp/middle/ty.rs
index 0140e5e8d5a..4d94535f53b 100644
--- a/src/comp/middle/ty.rs
+++ b/src/comp/middle/ty.rs
@@ -31,8 +31,8 @@ type mt = rec(@t ty, ast.mutability mut);
 
 // Convert from method type to function type.  Pretty easy; we just drop
 // 'ident'.
-fn method_ty_to_fn_ty(method m) -> @ty.t {
-    ret mk_fn(m.proto, m.inputs, m.output);
+fn method_ty_to_fn_ty(@type_store tystore, method m) -> @ty.t {
+    ret mk_fn(tystore, m.proto, m.inputs, m.output);
 }
 
 // Do not construct these manually. Soon we want to intern these, at which
@@ -100,62 +100,99 @@ type ty_param_count_and_ty = tup(uint, @t);
 type type_cache = hashmap[ast.def_id,ty_param_count_and_ty];
 
 
+type type_store = hashmap[@t,()];
+
+fn mk_type_store() -> @hashmap[@t,()] {
+    auto hasher = hash_ty;
+    auto eqer = eq_ty;
+    ret @map.mk_hashmap[@t,()](hasher, eqer);
+}
+
 // Type constructors
 
 // This is a private constructor to this module. External users should always
 // use the mk_foo() functions below.
-fn gen_ty(&sty st) -> @t {
+fn gen_ty(@type_store tystore, &sty st) -> @t {
+    // TODO: Intern the type.
     ret @rec(struct=st, cname=none[str], hash=hash_type_structure(st));
 }
 
-fn mk_nil() -> @t                        { ret gen_ty(ty_nil); }
-fn mk_bool() -> @t                       { ret gen_ty(ty_bool); }
-fn mk_int() -> @t                        { ret gen_ty(ty_int); }
-fn mk_float() -> @t                      { ret gen_ty(ty_float); }
-fn mk_uint() -> @t                       { ret gen_ty(ty_uint); }
-fn mk_mach(util.common.ty_mach tm) -> @t { ret gen_ty(ty_machine(tm)); }
-fn mk_char() -> @t                       { ret gen_ty(ty_char); }
-fn mk_str() -> @t                        { ret gen_ty(ty_str); }
+fn mk_nil(@type_store ts) -> @t          { ret gen_ty(ts, ty_nil); }
+fn mk_bool(@type_store ts) -> @t         { ret gen_ty(ts, ty_bool); }
+fn mk_int(@type_store ts) -> @t          { ret gen_ty(ts, ty_int); }
+fn mk_float(@type_store ts) -> @t        { ret gen_ty(ts, ty_float); }
+fn mk_uint(@type_store ts) -> @t         { ret gen_ty(ts, ty_uint); }
 
-fn mk_tag(ast.def_id did, vec[@t] tys) -> @t {
-    ret gen_ty(ty_tag(did, tys));
+fn mk_mach(@type_store ts, util.common.ty_mach tm) -> @t {
+    ret gen_ty(ts, ty_machine(tm));
 }
 
-fn mk_box(mt tm) -> @t     { ret gen_ty(ty_box(tm)); }
-fn mk_imm_box(@t ty) -> @t { ret mk_box(rec(ty=ty, mut=ast.imm)); }
+fn mk_char(@type_store ts) -> @t         { ret gen_ty(ts, ty_char); }
+fn mk_str(@type_store ts) -> @t          { ret gen_ty(ts, ty_str); }
 
-fn mk_vec(mt tm) -> @t                   { ret gen_ty(ty_vec(tm)); }
-fn mk_port(@t ty) -> @t                  { ret gen_ty(ty_port(ty)); }
-fn mk_chan(@t ty) -> @t                  { ret gen_ty(ty_chan(ty)); }
-fn mk_task() -> @t                       { ret gen_ty(ty_task); }
+fn mk_tag(@type_store ts, ast.def_id did, vec[@t] tys) -> @t {
+    ret gen_ty(ts, ty_tag(did, tys));
+}
 
-fn mk_tup(vec[mt] tms) -> @t             { ret gen_ty(ty_tup(tms)); }
-fn mk_imm_tup(vec[@t] tys) -> @t {
+fn mk_box(@type_store ts, mt tm) -> @t {
+    ret gen_ty(ts, ty_box(tm));
+}
+
+fn mk_imm_box(@type_store ts, @t ty) -> @t {
+    ret mk_box(ts, rec(ty=ty, mut=ast.imm));
+}
+
+fn mk_vec(@type_store ts, mt tm) -> @t   { ret gen_ty(ts, ty_vec(tm)); }
+fn mk_port(@type_store ts, @t ty) -> @t  { ret gen_ty(ts, ty_port(ty)); }
+fn mk_chan(@type_store ts, @t ty) -> @t  { ret gen_ty(ts, ty_chan(ty)); }
+fn mk_task(@type_store ts) -> @t         { ret gen_ty(ts, ty_task); }
+
+fn mk_tup(@type_store ts, vec[mt] tms) -> @t {
+    ret gen_ty(ts, ty_tup(tms));
+}
+
+fn mk_imm_tup(@type_store ts, vec[@t] tys) -> @t {
     // TODO: map
     let vec[ty.mt] mts = vec();
     for (@ty.t typ in tys) {
         mts += vec(rec(ty=typ, mut=ast.imm));
     }
-    ret mk_tup(mts);
+    ret mk_tup(ts, mts);
+}
+
+fn mk_rec(@type_store ts, vec[field] fs) -> @t {
+    ret gen_ty(ts, ty_rec(fs));
 }
 
-fn mk_rec(vec[field] fs) -> @t           { ret gen_ty(ty_rec(fs)); }
+fn mk_fn(@type_store ts, ast.proto proto, vec[arg] args, @t ty) -> @t {
+    ret gen_ty(ts, ty_fn(proto, args, ty));
+}
+
+fn mk_native_fn(@type_store ts, ast.native_abi abi, vec[arg] args, @t ty)
+        -> @t {
+    ret gen_ty(ts, ty_native_fn(abi, args, ty));
+}
 
-fn mk_fn(ast.proto proto, vec[arg] args, @t ty) -> @t {
-    ret gen_ty(ty_fn(proto, args, ty));
+fn mk_obj(@type_store ts, vec[method] meths) -> @t {
+    ret gen_ty(ts, ty_obj(meths));
 }
 
-fn mk_native_fn(ast.native_abi abi, vec[arg] args, @t ty) -> @t {
-    ret gen_ty(ty_native_fn(abi, args, ty));
+fn mk_var(@type_store ts, int v) -> @t   { ret gen_ty(ts, ty_var(v)); }
+
+fn mk_local(@type_store ts, ast.def_id did) -> @t {
+    ret gen_ty(ts, ty_local(did));
 }
 
-fn mk_obj(vec[method] meths) -> @t       { ret gen_ty(ty_obj(meths)); }
-fn mk_var(int v) -> @t                   { ret gen_ty(ty_var(v)); }
-fn mk_local(ast.def_id did) -> @t        { ret gen_ty(ty_local(did)); }
-fn mk_param(uint n) -> @t                { ret gen_ty(ty_param(n)); }
-fn mk_bound_param(uint n) -> @t          { ret gen_ty(ty_bound_param(n)); }
-fn mk_type() -> @t                       { ret gen_ty(ty_type); }
-fn mk_native() -> @t                     { ret gen_ty(ty_native); }
+fn mk_param(@type_store ts, uint n) -> @t {
+    ret gen_ty(ts, ty_param(n));
+}
+
+fn mk_bound_param(@type_store ts, uint n) -> @t {
+    ret gen_ty(ts, ty_bound_param(n));
+}
+
+fn mk_type(@type_store ts) -> @t         { ret gen_ty(ts, ty_type); }
+fn mk_native(@type_store ts) -> @t       { ret gen_ty(ts, ty_native); }
 
 
 // Stringification
@@ -386,7 +423,7 @@ fn walk_ty(ty_walk walker, @t ty) {
 
 type ty_fold = fn(@t) -> @t;
 
-fn fold_ty(ty_fold fld, @t ty_0) -> @t {
+fn fold_ty(@type_store tystore, ty_fold fld, @t ty_0) -> @t {
     auto ty = ty_0;
     alt (ty.struct) {
         case (ty_nil)           { /* no-op */ }
@@ -400,58 +437,65 @@ fn fold_ty(ty_fold fld, @t ty_0) -> @t {
         case (ty_type)          { /* no-op */ }
         case (ty_native)        { /* no-op */ }
         case (ty_box(?tm)) {
-            ty = copy_cname(mk_box(rec(ty=fold_ty(fld, tm.ty), mut=tm.mut)),
-                            ty);
+            ty = copy_cname(mk_box(tystore,
+                                   rec(ty=fold_ty(tystore, fld, tm.ty),
+                                       mut=tm.mut)), ty);
         }
         case (ty_vec(?tm)) {
-            ty = copy_cname(mk_vec(rec(ty=fold_ty(fld, tm.ty), mut=tm.mut)),
-                            ty);
+            ty = copy_cname(mk_vec(tystore,
+                                   rec(ty=fold_ty(tystore, fld, tm.ty),
+                                       mut=tm.mut)), ty);
         }
         case (ty_port(?subty)) {
-            ty = copy_cname(mk_port(fold_ty(fld, subty)), ty);
+            ty = copy_cname(mk_port(tystore, fold_ty(tystore, fld, subty)),
+                            ty);
         }
         case (ty_chan(?subty)) {
-            ty = copy_cname(mk_chan(fold_ty(fld, subty)), ty);
+            ty = copy_cname(mk_chan(tystore, fold_ty(tystore, fld, subty)),
+                            ty);
         }
         case (ty_tag(?tid, ?subtys)) {
             let vec[@t] new_subtys = vec();
             for (@t subty in subtys) {
-                new_subtys += vec(fold_ty(fld, subty));
+                new_subtys += vec(fold_ty(tystore, fld, subty));
             }
-            ty = copy_cname(mk_tag(tid, new_subtys), ty);
+            ty = copy_cname(mk_tag(tystore, tid, new_subtys), ty);
         }
         case (ty_tup(?mts)) {
             let vec[mt] new_mts = vec();
             for (mt tm in mts) {
-                auto new_subty = fold_ty(fld, tm.ty);
+                auto new_subty = fold_ty(tystore, fld, tm.ty);
                 new_mts += vec(rec(ty=new_subty, mut=tm.mut));
             }
-            ty = copy_cname(mk_tup(new_mts), ty);
+            ty = copy_cname(mk_tup(tystore, new_mts), ty);
         }
         case (ty_rec(?fields)) {
             let vec[field] new_fields = vec();
             for (field fl in fields) {
-                auto new_ty = fold_ty(fld, fl.mt.ty);
+                auto new_ty = fold_ty(tystore, 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));
             }
-            ty = copy_cname(mk_rec(new_fields), ty);
+            ty = copy_cname(mk_rec(tystore, new_fields), ty);
         }
         case (ty_fn(?proto, ?args, ?ret_ty)) {
             let vec[arg] new_args = vec();
             for (arg a in args) {
-                auto new_ty = fold_ty(fld, a.ty);
+                auto new_ty = fold_ty(tystore, fld, a.ty);
                 new_args += vec(rec(mode=a.mode, ty=new_ty));
             }
-            ty = copy_cname(mk_fn(proto, new_args, fold_ty(fld, ret_ty)), ty);
+            ty = copy_cname(mk_fn(tystore, proto, new_args,
+                                  fold_ty(tystore, fld, ret_ty)),
+                            ty);
         }
         case (ty_native_fn(?abi, ?args, ?ret_ty)) {
             let vec[arg] new_args = vec();
             for (arg a in args) {
-                auto new_ty = fold_ty(fld, a.ty);
+                auto new_ty = fold_ty(tystore, fld, a.ty);
                 new_args += vec(rec(mode=a.mode, ty=new_ty));
             }
-            ty = copy_cname(mk_native_fn(abi, new_args, fold_ty(fld, ret_ty)),
+            ty = copy_cname(mk_native_fn(tystore, abi, new_args,
+                                         fold_ty(tystore, fld, ret_ty)),
                             ty);
         }
         case (ty_obj(?methods)) {
@@ -459,13 +503,15 @@ fn fold_ty(ty_fold fld, @t ty_0) -> @t {
             for (method m in methods) {
                 let vec[arg] new_args = vec();
                 for (arg a in m.inputs) {
-                    new_args += vec(rec(mode=a.mode, ty=fold_ty(fld, a.ty)));
+                    new_args += vec(rec(mode=a.mode,
+                                        ty=fold_ty(tystore, fld, a.ty)));
                 }
                 new_methods += vec(rec(proto=m.proto, ident=m.ident,
                                        inputs=new_args,
-                                       output=fold_ty(fld, m.output)));
+                                       output=fold_ty(tystore, fld,
+                                                      m.output)));
             }
-            ty = copy_cname(mk_obj(new_methods), ty);
+            ty = copy_cname(mk_obj(tystore, new_methods), ty);
         }
         case (ty_var(_))         { /* no-op */ }
         case (ty_local(_))       { /* no-op */ }
@@ -536,9 +582,9 @@ fn type_is_sequence(@t ty) -> bool {
     fail;
 }
 
-fn sequence_element_type(@t ty) -> @t {
+fn sequence_element_type(@type_store tystore, @t ty) -> @t {
     alt (ty.struct) {
-        case (ty_str)      { ret mk_mach(common.ty_u8); }
+        case (ty_str)      { ret mk_mach(tystore, common.ty_u8); }
         case (ty_vec(?mt)) { ret mt.ty; }
     }
     fail;
@@ -1158,7 +1204,7 @@ fn ann_to_type_params(&ast.ann ann) -> vec[@t] {
 
 // Returns the type of an annotation, with type parameter substitutions
 // performed if applicable.
-fn ann_to_monotype(ast.ann a) -> @ty.t {
+fn ann_to_monotype(@type_store tystore, ast.ann a) -> @ty.t {
     // TODO: Refactor to use recursive pattern matching when we're more
     // confident that it works.
     alt (a) {
@@ -1170,7 +1216,7 @@ fn ann_to_monotype(ast.ann a) -> @ty.t {
             alt (tps_opt) {
                 case (none[vec[@ty.t]]) { ret typ; }
                 case (some[vec[@ty.t]](?tps)) {
-                    ret substitute_type_params(tps, typ);
+                    ret substitute_type_params(tystore, tps, typ);
                 }
             }
         }
@@ -1312,32 +1358,32 @@ fn item_ty(@ast.item it) -> ty_param_count_and_ty {
     ret tup(ty_param_count, result_ty);
 }
 
-fn stmt_ty(@ast.stmt s) -> @t {
+fn stmt_ty(@type_store tystore, @ast.stmt s) -> @t {
     alt (s.node) {
         case (ast.stmt_expr(?e,_)) {
-            ret expr_ty(e);
+            ret expr_ty(tystore, e);
         }
         case (_) {
-            ret mk_nil();
+            ret mk_nil(tystore);
         }
     }
 }
 
-fn block_ty(&ast.block b) -> @t {
+fn block_ty(@type_store tystore, &ast.block b) -> @t {
     alt (b.node.expr) {
-        case (some[@ast.expr](?e)) { ret expr_ty(e); }
-        case (none[@ast.expr])     { ret mk_nil(); }
+        case (some[@ast.expr](?e)) { ret expr_ty(tystore, e); }
+        case (none[@ast.expr])     { ret mk_nil(tystore); }
     }
 }
 
 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
 // doesn't provide type parameter substitutions.
-fn pat_ty(@ast.pat pat) -> @t {
+fn pat_ty(@type_store ts, @ast.pat pat) -> @t {
     alt (pat.node) {
-        case (ast.pat_wild(?ann))           { ret ann_to_monotype(ann); }
-        case (ast.pat_lit(_, ?ann))         { ret ann_to_monotype(ann); }
-        case (ast.pat_bind(_, _, ?ann))     { ret ann_to_monotype(ann); }
-        case (ast.pat_tag(_, _, _, ?ann))   { ret ann_to_monotype(ann); }
+        case (ast.pat_wild(?ann))           { ret ann_to_monotype(ts, ann); }
+        case (ast.pat_lit(_, ?ann))         { ret ann_to_monotype(ts, ann); }
+        case (ast.pat_bind(_, _, ?ann))     { ret ann_to_monotype(ts, ann); }
+        case (ast.pat_tag(_, _, _, ?ann))   { ret ann_to_monotype(ts, ann); }
     }
     fail;   // not reached
 }
@@ -1394,18 +1440,19 @@ fn expr_ann(@ast.expr expr) -> option.t[ast.ann] {
 // ask for the type of "id" in "id(3)", it will return "fn(&int) -> int"
 // instead of "fn(&T) -> T with T = int". If this isn't what you want, see
 // expr_ty_params_and_ty() below.
-fn expr_ty(@ast.expr expr) -> @t {
+fn expr_ty(@type_store tystore, @ast.expr expr) -> @t {
     alt (expr_ann(expr)) {
-        case (none[ast.ann])     { ret mk_nil(); }
-        case (some[ast.ann](?a)) { ret ann_to_monotype(a); }
+        case (none[ast.ann])     { ret mk_nil(tystore); }
+        case (some[ast.ann](?a)) { ret ann_to_monotype(tystore, a); }
     }
 }
 
-fn expr_ty_params_and_ty(@ast.expr expr) -> tup(vec[@t], @t) {
+fn expr_ty_params_and_ty(@type_store tystore, @ast.expr expr)
+        -> tup(vec[@t], @t) {
     alt (expr_ann(expr)) {
         case (none[ast.ann]) {
             let vec[@t] tps = vec();
-            ret tup(tps, mk_nil());
+            ret tup(tps, mk_nil(tystore));
         }
         case (some[ast.ann](?a)) {
             ret tup(ann_to_type_params(a), ann_to_type(a));
@@ -1555,7 +1602,8 @@ mod Unify {
     type ctxt = rec(UFind.ufind sets,
                     hashmap[int,uint] var_ids,
                     mutable vec[mutable vec[@t]] types,
-                    unify_handler handler);
+                    unify_handler handler,
+                    @type_store tystore);
 
     // Wraps the given type in an appropriate cname.
     //
@@ -1670,7 +1718,7 @@ mod Unify {
                 ret r;
             }
             case (fn_common_res_ok(?result_ins, ?result_out)) {
-                auto t2 = mk_fn(e_proto, result_ins, result_out);
+                auto t2 = mk_fn(cx.tystore, e_proto, result_ins, result_out);
                 ret ures_ok(t2);
             }
         }
@@ -1696,7 +1744,8 @@ mod Unify {
                 ret r;
             }
             case (fn_common_res_ok(?result_ins, ?result_out)) {
-                auto t2 = mk_native_fn(e_abi, result_ins, result_out);
+                auto t2 = mk_native_fn(cx.tystore, e_abi, result_ins,
+                                       result_out);
                 ret ures_ok(t2);
             }
         }
@@ -1744,7 +1793,7 @@ mod Unify {
         }
         i += 1u;
       }
-      auto t = mk_obj(result_meths);
+      auto t = mk_obj(cx.tystore, result_meths);
       ret ures_ok(t);
     }
 
@@ -1868,7 +1917,8 @@ mod Unify {
                             i += 1u;
                         }
 
-                        ret ures_ok(mk_tag(expected_id, result_tps));
+                        ret ures_ok(mk_tag(cx.tystore, expected_id,
+                                           result_tps));
                     }
                     case (_) { /* fall through */ }
                 }
@@ -1894,7 +1944,7 @@ mod Unify {
                         alt (result) {
                             case (ures_ok(?result_sub)) {
                                 auto mt = rec(ty=result_sub, mut=mut);
-                                ret ures_ok(mk_box(mt));
+                                ret ures_ok(mk_box(cx.tystore, mt));
                             }
                             case (_) {
                                 ret result;
@@ -1926,7 +1976,7 @@ mod Unify {
                         alt (result) {
                             case (ures_ok(?result_sub)) {
                                 auto mt = rec(ty=result_sub, mut=mut);
-                                ret ures_ok(mk_vec(mt));
+                                ret ures_ok(mk_vec(cx.tystore, mt));
                             }
                             case (_) {
                                 ret result;
@@ -1948,7 +1998,7 @@ mod Unify {
                                                  actual_sub);
                         alt (result) {
                             case (ures_ok(?result_sub)) {
-                                ret ures_ok(mk_port(result_sub));
+                                ret ures_ok(mk_port(cx.tystore, result_sub));
                             }
                             case (_) {
                                 ret result;
@@ -1970,7 +2020,7 @@ mod Unify {
                                                  actual_sub);
                         alt (result) {
                             case (ures_ok(?result_sub)) {
-                                ret ures_ok(mk_chan(result_sub));
+                                ret ures_ok(mk_chan(cx.tystore, result_sub));
                             }
                             case (_) {
                                 ret result;
@@ -2029,7 +2079,7 @@ mod Unify {
                             i += 1u;
                         }
 
-                        ret ures_ok(mk_tup(result_elems));
+                        ret ures_ok(mk_tup(cx.tystore, result_elems));
                     }
 
                     case (_) {
@@ -2093,7 +2143,7 @@ mod Unify {
                             i += 1u;
                         }
 
-                        ret ures_ok(mk_rec(result_fields));
+                        ret ures_ok(mk_rec(cx.tystore, result_fields));
                     }
 
                     case (_) {
@@ -2202,7 +2252,7 @@ mod Unify {
         }
 
         auto f = bind substituter(cx, set_types, _);
-        ret fold_ty(f, typ);
+        ret fold_ty(cx.tystore, f, typ);
     }
 
     fn unify_sets(@ctxt cx) -> vec[@t] {
@@ -2235,8 +2285,10 @@ mod Unify {
         ret result;
     }
 
-    fn unify(@ty.t expected, @ty.t actual, &unify_handler handler)
-            -> result {
+    fn unify(@ty.t expected,
+             @ty.t actual,
+             &unify_handler handler,
+             @type_store tystore) -> result {
         let vec[@t] throwaway = vec();
         let vec[mutable vec[@t]] types = vec(mutable throwaway);
         _vec.pop[mutable vec[@t]](types);   // FIXME: botch
@@ -2244,7 +2296,8 @@ mod Unify {
         auto cx = @rec(sets=UFind.make(),
                        var_ids=common.new_int_hash[uint](),
                        mutable types=types,
-                       handler=handler);
+                       handler=handler,
+                       tystore=tystore);
 
         auto ures = unify_step(cx, expected, actual);
         alt (ures) {
@@ -2307,7 +2360,9 @@ fn type_err_to_str(&ty.type_err err) -> str {
 
 // Performs bound type parameter replacement using the supplied mapping from
 // parameter IDs to types.
-fn substitute_type_params(vec[@t] bindings, @t typ) -> @t {
+fn substitute_type_params(@type_store tystore,
+                          vec[@t] bindings,
+                          @t typ) -> @t {
     fn replacer(vec[@t] bindings, @t typ) -> @t {
         alt (typ.struct) {
             case (ty_bound_param(?param_index)) {
@@ -2318,25 +2373,25 @@ fn substitute_type_params(vec[@t] bindings, @t typ) -> @t {
     }
 
     auto f = bind replacer(bindings, _);
-    ret fold_ty(f, typ);
+    ret fold_ty(tystore, f, typ);
 }
 
 // Converts type parameters in a type to bound type parameters.
-fn bind_params_in_type(@t typ) -> @t {
-    fn binder(@t typ) -> @t {
+fn bind_params_in_type(@type_store tystore, @t typ) -> @t {
+    fn binder(@type_store tystore, @t typ) -> @t {
         alt (typ.struct) {
             case (ty_bound_param(?index)) {
                 log_err "bind_params_in_type() called on type that already " +
                     "has bound params in it";
                 fail;
             }
-            case (ty_param(?index)) { ret mk_bound_param(index); }
+            case (ty_param(?index)) { ret mk_bound_param(tystore, index); }
             case (_) { ret typ; }
         }
     }
 
-    auto f = binder;
-    ret fold_ty(f, typ);
+    auto f = bind binder(tystore, _);
+    ret fold_ty(tystore, f, typ);
 }
 
 
@@ -2361,7 +2416,9 @@ fn def_has_ty_params(&ast.def def) -> bool {
 
 // If the given item is in an external crate, looks up its type and adds it to
 // the type cache. Returns the type parameters and type.
-fn lookup_item_type(session.session sess, &type_cache cache,
+fn lookup_item_type(session.session sess,
+                    @type_store tystore,
+                    &type_cache cache,
                     ast.def_id did) -> ty_param_count_and_ty {
     if (did._0 == sess.get_targ_crate_num()) {
         // The item is in this crate. The caller should have added it to the
@@ -2374,7 +2431,7 @@ fn lookup_item_type(session.session sess, &type_cache cache,
         ret cache.get(did);
     }
 
-    auto tyt = creader.get_type(sess, did);
+    auto tyt = creader.get_type(sess, tystore, did);
     cache.insert(did, tyt);
     ret tyt;
 }
diff --git a/src/comp/middle/typeck.rs b/src/comp/middle/typeck.rs
index 8baab19e960..cf60cb04183 100644
--- a/src/comp/middle/typeck.rs
+++ b/src/comp/middle/typeck.rs
@@ -62,7 +62,8 @@ type crate_ctxt = rec(session.session sess,
                       mutable int next_var_id,
                       unify_cache unify_cache,
                       mutable uint cache_hits,
-                      mutable uint cache_misses);
+                      mutable uint cache_misses,
+                      @ty.type_store tystore);
 
 type fn_ctxt = rec(@ty.t ret_ty,
                    @ty_table locals,
@@ -95,7 +96,7 @@ fn substitute_ty_params(&@crate_ctxt ccx,
     }
 
     auto f = bind substituter(ccx, supplied, _);
-    ret ty.fold_ty(f, typ);
+    ret ty.fold_ty(ccx.tystore, f, typ);
 }
 
 
@@ -111,7 +112,7 @@ fn ty_param_count_and_ty_for_def(@fn_ctxt fcx, &ast.def defn)
             auto t;
             alt (fcx.locals.find(id)) {
                 case (some[@ty.t](?t1)) { t = t1; }
-                case (none[@ty.t]) { t = ty.mk_local(id); }
+                case (none[@ty.t]) { t = ty.mk_local(fcx.ccx.tystore, id); }
             }
             ret tup(0u, t);
         }
@@ -120,29 +121,34 @@ fn ty_param_count_and_ty_for_def(@fn_ctxt fcx, &ast.def defn)
             ret tup(0u, fcx.locals.get(id));
         }
         case (ast.def_fn(?id)) {
-            ret ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.type_cache, id);
+            ret ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.tystore,
+                                    fcx.ccx.type_cache, id);
         }
         case (ast.def_native_fn(?id)) {
-            ret ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.type_cache, id);
+            ret ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.tystore,
+                                    fcx.ccx.type_cache, id);
         }
         case (ast.def_const(?id)) {
-            ret ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.type_cache, id);
+            ret ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.tystore,
+                                    fcx.ccx.type_cache, id);
         }
         case (ast.def_variant(_, ?vid)) {
-            ret ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.type_cache, vid);
+            ret ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.tystore,
+                                    fcx.ccx.type_cache, vid);
         }
         case (ast.def_binding(?id)) {
             check (fcx.locals.contains_key(id));
             ret tup(0u, fcx.locals.get(id));
         }
         case (ast.def_obj(?id)) {
-            ret ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.type_cache, id);
+            ret ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.tystore,
+                                    fcx.ccx.type_cache, id);
         }
 
         case (ast.def_mod(_)) {
             // Hopefully part of a path.
             // TODO: return a type that's more poisonous, perhaps?
-            ret tup(0u, ty.mk_nil());
+            ret tup(0u, ty.mk_nil(fcx.ccx.tystore));
         }
 
         case (ast.def_ty(_)) {
@@ -163,7 +169,7 @@ fn ty_param_count_and_ty_for_def(@fn_ctxt fcx, &ast.def defn)
 fn instantiate_path(@fn_ctxt fcx, &ast.path pth, &ty_param_count_and_ty tpt,
         &span sp) -> ast.ann {
     auto ty_param_count = tpt._0;
-    auto t = bind_params_in_type(tpt._1);
+    auto t = bind_params_in_type(fcx.ccx.tystore, tpt._1);
 
     auto ty_substs_opt;
     auto ty_substs_len = _vec.len[@ast.ty](pth.node.types);
@@ -198,17 +204,25 @@ fn instantiate_path(@fn_ctxt fcx, &ast.path pth, &ty_param_count_and_ty tpt,
 // Parses the programmer's textual representation of a type into our internal
 // notion of a type. `getter` is a function that returns the type
 // corresponding to a definition ID.
-fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty.t {
-    fn ast_arg_to_arg(ty_getter getter, &rec(ast.mode mode, @ast.ty ty) arg)
+fn ast_ty_to_ty(@ty.type_store tystore,
+                ty_getter getter,
+                &@ast.ty ast_ty) -> @ty.t {
+    fn ast_arg_to_arg(@ty.type_store tystore,
+                      ty_getter getter,
+                      &rec(ast.mode mode, @ast.ty ty) arg)
             -> rec(ast.mode mode, @ty.t ty) {
-        ret rec(mode=arg.mode, ty=ast_ty_to_ty(getter, arg.ty));
+        ret rec(mode=arg.mode, ty=ast_ty_to_ty(tystore, 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 ast_mt_to_mt(@ty.type_store tystore,
+                    ty_getter getter,
+                    &ast.mt mt) -> ty.mt {
+        ret rec(ty=ast_ty_to_ty(tystore, getter, mt.ty), mut=mt.mut);
     }
 
-    fn instantiate(ty_getter getter, ast.def_id id,
+    fn instantiate(@ty.type_store tystore,
+                   ty_getter getter,
+                   ast.def_id id,
                    vec[@ast.ty] args) -> @ty.t {
         // TODO: maybe record cname chains so we can do
         // "foo = int" like OCaml?
@@ -222,73 +236,76 @@ fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty.t {
         //
         // TODO: Make sure the number of supplied bindings matches the number
         // of type parameters in the typedef. Emit a friendly error otherwise.
-        auto bound_ty = bind_params_in_type(params_opt_and_ty._1);
+        auto bound_ty = bind_params_in_type(tystore, params_opt_and_ty._1);
         let vec[@ty.t] param_bindings = vec();
         for (@ast.ty ast_ty in args) {
-            param_bindings += vec(ast_ty_to_ty(getter, ast_ty));
+            param_bindings += vec(ast_ty_to_ty(tystore, getter, ast_ty));
         }
-        ret ty.substitute_type_params(param_bindings, bound_ty);
+        ret ty.substitute_type_params(tystore, param_bindings, bound_ty);
     }
 
     auto mut = ast.imm;
     auto typ;
     auto cname = none[str];
     alt (ast_ty.node) {
-        case (ast.ty_nil)          { typ = ty.mk_nil(); }
-        case (ast.ty_bool)         { typ = ty.mk_bool(); }
-        case (ast.ty_int)          { typ = ty.mk_int(); }
-        case (ast.ty_uint)         { typ = ty.mk_uint(); }
-        case (ast.ty_float)        { typ = ty.mk_float(); }
-        case (ast.ty_machine(?tm)) { typ = ty.mk_mach(tm); }
-        case (ast.ty_char)         { typ = ty.mk_char(); }
-        case (ast.ty_str)          { typ = ty.mk_str(); }
-        case (ast.ty_box(?mt)) { typ = ty.mk_box(ast_mt_to_mt(getter, mt)); }
-        case (ast.ty_vec(?mt)) { typ = ty.mk_vec(ast_mt_to_mt(getter, mt)); }
+        case (ast.ty_nil)          { typ = ty.mk_nil(tystore); }
+        case (ast.ty_bool)         { typ = ty.mk_bool(tystore); }
+        case (ast.ty_int)          { typ = ty.mk_int(tystore); }
+        case (ast.ty_uint)         { typ = ty.mk_uint(tystore); }
+        case (ast.ty_float)        { typ = ty.mk_float(tystore); }
+        case (ast.ty_machine(?tm)) { typ = ty.mk_mach(tystore, tm); }
+        case (ast.ty_char)         { typ = ty.mk_char(tystore); }
+        case (ast.ty_str)          { typ = ty.mk_str(tystore); }
+        case (ast.ty_box(?mt)) {
+            typ = ty.mk_box(tystore, ast_mt_to_mt(tystore, getter, mt));
+        }
+        case (ast.ty_vec(?mt)) {
+            typ = ty.mk_vec(tystore, ast_mt_to_mt(tystore, getter, mt));
+        }
 
         case (ast.ty_port(?t)) {
-            typ = ty.mk_port(ast_ty_to_ty(getter, t));
+            typ = ty.mk_port(tystore, ast_ty_to_ty(tystore, getter, t));
         }
 
         case (ast.ty_chan(?t)) {
-            typ = ty.mk_chan(ast_ty_to_ty(getter, t));
+            typ = ty.mk_chan(tystore, ast_ty_to_ty(tystore, getter, t));
         }
 
         case (ast.ty_tup(?fields)) {
             let vec[ty.mt] flds = vec();
             for (ast.mt field in fields) {
-                _vec.push[ty.mt](flds, ast_mt_to_mt(getter, field));
+                _vec.push[ty.mt](flds, ast_mt_to_mt(tystore, getter, field));
             }
-            typ = ty.mk_tup(flds);
+            typ = ty.mk_tup(tystore, flds);
         }
         case (ast.ty_rec(?fields)) {
             let vec[field] flds = vec();
             for (ast.ty_field f in fields) {
-                _vec.push[field](flds, rec(ident=f.ident,
-                                        mt=ast_mt_to_mt(getter, f.mt)));
+                auto tm = ast_mt_to_mt(tystore, getter, f.mt);
+                _vec.push[field](flds, rec(ident=f.ident, mt=tm));
             }
-            typ = ty.mk_rec(flds);
+            typ = ty.mk_rec(tystore, flds);
         }
 
         case (ast.ty_fn(?proto, ?inputs, ?output)) {
-            auto f = bind ast_arg_to_arg(getter, _);
+            auto f = bind ast_arg_to_arg(tystore, getter, _);
             auto i = _vec.map[ast.ty_arg, arg](f, inputs);
-            typ = ty.mk_fn(proto, i, ast_ty_to_ty(getter, output));
+            auto out_ty = ast_ty_to_ty(tystore, getter, output);
+            typ = ty.mk_fn(tystore, proto, i, out_ty);
         }
 
         case (ast.ty_path(?path, ?def)) {
             check (def != none[ast.def]);
             alt (option.get[ast.def](def)) {
                 case (ast.def_ty(?id)) {
-                    typ = instantiate(getter, id, path.node.types);
-                }
-                case (ast.def_native_ty(?id)) {
-                    typ = getter(id)._1;
+                    typ = instantiate(tystore, getter, id, path.node.types);
                 }
-                case (ast.def_obj(?id))     {
-                    typ = instantiate(getter, id, path.node.types);
+                case (ast.def_native_ty(?id)) { typ = getter(id)._1; }
+                case (ast.def_obj(?id)) {
+                    typ = instantiate(tystore, getter, id, path.node.types);
                 }
-                case (ast.def_ty_arg(?id))  { typ = ty.mk_param(id); }
-                case (_)                    { fail; }
+                case (ast.def_ty_arg(?id)) { typ = ty.mk_param(tystore, id); }
+                case (_)                   { fail; }
             }
 
             cname = some(path_to_str(path));
@@ -296,10 +313,10 @@ fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty.t {
 
         case (ast.ty_obj(?meths)) {
             let vec[ty.method] tmeths = vec();
-            auto f = bind ast_arg_to_arg(getter, _);
+            auto f = bind ast_arg_to_arg(tystore, getter, _);
             for (ast.ty_method m in meths) {
                 auto ins = _vec.map[ast.ty_arg, arg](f, m.inputs);
-                auto out = ast_ty_to_ty(getter, m.output);
+                auto out = ast_ty_to_ty(tystore, getter, m.output);
                 _vec.push[ty.method](tmeths,
                                   rec(proto=m.proto,
                                       ident=m.ident,
@@ -307,7 +324,7 @@ fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty.t {
                                       output=out));
             }
 
-            typ = ty.mk_obj(ty.sort_methods(tmeths));
+            typ = ty.mk_obj(tystore, ty.sort_methods(tmeths));
         }
     }
 
@@ -322,10 +339,10 @@ fn ast_ty_to_ty(ty_getter getter, &@ast.ty ast_ty) -> @ty.t {
 // ast_ty_to_ty.
 fn ast_ty_to_ty_crate(@crate_ctxt ccx, &@ast.ty ast_ty) -> @ty.t {
     fn getter(@crate_ctxt ccx, ast.def_id id) -> ty.ty_param_count_and_ty {
-        ret ty.lookup_item_type(ccx.sess, ccx.type_cache, id);
+        ret ty.lookup_item_type(ccx.sess, ccx.tystore, ccx.type_cache, id);
     }
     auto f = bind getter(ccx, _);
-    ret ast_ty_to_ty(f, ast_ty);
+    ret ast_ty_to_ty(ccx.tystore, f, ast_ty);
 }
 
 
@@ -343,7 +360,8 @@ fn ast_ty_to_ty_crate(@crate_ctxt ccx, &@ast.ty ast_ty) -> @ty.t {
 mod Collect {
     type ctxt = rec(session.session sess,
                     @ty_item_table id_to_ty_item,
-                    ty.type_cache type_cache);
+                    ty.type_cache type_cache,
+                    @ty.type_store tystore);
     type env = rec(@ctxt cx, ast.native_abi abi);
 
     fn ty_of_fn_decl(@ctxt cx,
@@ -355,7 +373,7 @@ mod Collect {
                      ast.def_id def_id) -> ty.ty_param_count_and_ty {
         auto input_tys = _vec.map[ast.arg,arg](ty_of_arg, decl.inputs);
         auto output_ty = convert(decl.output);
-        auto t_fn = ty.mk_fn(proto, input_tys, output_ty);
+        auto t_fn = ty.mk_fn(cx.tystore, proto, input_tys, output_ty);
         auto ty_param_count = _vec.len[ast.ty_param](ty_params);
         auto tpt = tup(ty_param_count, t_fn);
         cx.type_cache.insert(def_id, tpt);
@@ -371,7 +389,7 @@ mod Collect {
                             ast.def_id def_id) -> ty.ty_param_count_and_ty {
         auto input_tys = _vec.map[ast.arg,arg](ty_of_arg, decl.inputs);
         auto output_ty = convert(decl.output);
-        auto t_fn = ty.mk_native_fn(abi, input_tys, output_ty);
+        auto t_fn = ty.mk_native_fn(cx.tystore, abi, input_tys, output_ty);
         auto ty_param_count = _vec.len[ast.ty_param](ty_params);
         auto tpt = tup(ty_param_count, t_fn);
         cx.type_cache.insert(def_id, tpt);
@@ -382,7 +400,7 @@ mod Collect {
 
         if (id._0 != cx.sess.get_targ_crate_num()) {
             // This is a type we need to load in from the crate reader.
-            ret creader.get_type(cx.sess, id);
+            ret creader.get_type(cx.sess, cx.tystore, id);
         }
 
         check (cx.id_to_ty_item.contains_key(id));
@@ -401,12 +419,12 @@ mod Collect {
 
     fn ty_of_arg(@ctxt cx, &ast.arg a) -> arg {
         auto f = bind getter(cx, _);
-        ret rec(mode=a.mode, ty=ast_ty_to_ty(f, a.ty));
+        ret rec(mode=a.mode, ty=ast_ty_to_ty(cx.tystore, f, a.ty));
     }
 
     fn ty_of_method(@ctxt cx, &@ast.method m) -> method {
         auto get = bind getter(cx, _);
-        auto convert = bind ast_ty_to_ty(get, _);
+        auto convert = bind ast_ty_to_ty(cx.tystore, get, _);
         auto f = bind ty_of_arg(cx, _);
         auto inputs = _vec.map[ast.arg,arg](f, m.node.meth.decl.inputs);
         auto output = convert(m.node.meth.decl.output);
@@ -421,7 +439,7 @@ mod Collect {
         auto f = bind ty_of_method(cx, _);
         auto methods = _vec.map[@ast.method,method](f, obj_info.methods);
 
-        auto t_obj = ty.mk_obj(ty.sort_methods(methods));
+        auto t_obj = ty.mk_obj(cx.tystore, ty.sort_methods(methods));
         t_obj = ty.rename(t_obj, id);
         auto ty_param_count = _vec.len[ast.ty_param](ty_params);
         ret tup(ty_param_count, t_obj);
@@ -437,20 +455,20 @@ mod Collect {
         let vec[arg] t_inputs = vec();
         for (ast.obj_field f in obj_info.fields) {
             auto g = bind getter(cx, _);
-            auto t_field = ast_ty_to_ty(g, f.ty);
+            auto t_field = ast_ty_to_ty(cx.tystore, g, f.ty);
             _vec.push[arg](t_inputs, rec(mode=ast.alias, ty=t_field));
         }
 
         cx.type_cache.insert(obj_ty_id, t_obj);
 
-        auto t_fn = ty.mk_fn(ast.proto_fn, t_inputs, t_obj._1);
+        auto t_fn = ty.mk_fn(cx.tystore, ast.proto_fn, t_inputs, t_obj._1);
         ret tup(t_obj._0, t_fn);
     }
 
     fn ty_of_item(@ctxt cx, @ast.item it) -> ty.ty_param_count_and_ty {
 
         auto get = bind getter(cx, _);
-        auto convert = bind ast_ty_to_ty(get, _);
+        auto convert = bind ast_ty_to_ty(cx.tystore, get, _);
 
         alt (it.node) {
 
@@ -493,11 +511,11 @@ mod Collect {
 
                 auto i = 0u;
                 for (ast.ty_param tp in tps) {
-                    subtys += vec(ty.mk_param(i));
+                    subtys += vec(ty.mk_param(cx.tystore, i));
                     i += 1u;
                 }
 
-                auto t = ty.mk_tag(def_id, subtys);
+                auto t = ty.mk_tag(cx.tystore, def_id, subtys);
 
                 auto ty_param_count = _vec.len[ast.ty_param](tps);
                 auto tpt = tup(ty_param_count, t);
@@ -516,7 +534,7 @@ mod Collect {
             case (ast.native_item_fn(?ident, ?lname, ?fn_decl,
                                      ?params, ?def_id, _)) {
                 auto get = bind getter(cx, _);
-                auto convert = bind ast_ty_to_ty(get, _);
+                auto convert = bind ast_ty_to_ty(cx.tystore, get, _);
                 auto f = bind ty_of_arg(cx, _);
                 ret ty_of_native_fn_decl(cx, convert, f, fn_decl, abi, params,
                                          def_id);
@@ -527,7 +545,7 @@ mod Collect {
                     ret cx.type_cache.get(def_id);
                 }
 
-                auto t = ty.mk_native();
+                auto t = ty.mk_native(cx.tystore);
                 auto tpt = tup(0u, t);
                 cx.type_cache.insert(def_id, tpt);
                 ret tpt;
@@ -545,7 +563,7 @@ mod Collect {
         let vec[@ty.t] ty_param_tys = vec();
         auto i = 0u;
         for (ast.ty_param tp in ty_params) {
-            ty_param_tys += vec(ty.mk_param(i));
+            ty_param_tys += vec(ty.mk_param(cx.tystore, i));
             i += 1u;
         }
 
@@ -556,7 +574,7 @@ mod Collect {
             // constructors get turned into functions.
             auto result_ty;
             if (_vec.len[ast.variant_arg](variant.node.args) == 0u) {
-                result_ty = ty.mk_tag(tag_id, ty_param_tys);
+                result_ty = ty.mk_tag(cx.tystore, tag_id, ty_param_tys);
             } else {
                 // As above, tell ast_ty_to_ty() that trans_ty_item_to_ty()
                 // should be called to resolve named types.
@@ -564,11 +582,11 @@ mod Collect {
 
                 let vec[arg] args = vec();
                 for (ast.variant_arg va in variant.node.args) {
-                    auto arg_ty = ast_ty_to_ty(f, va.ty);
+                    auto arg_ty = ast_ty_to_ty(cx.tystore, f, va.ty);
                     args += vec(rec(mode=ast.alias, ty=arg_ty));
                 }
-                auto tag_t = ty.mk_tag(tag_id, ty_param_tys);
-                result_ty = ty.mk_fn(ast.proto_fn, args, tag_t);
+                auto tag_t = ty.mk_tag(cx.tystore, tag_id, ty_param_tys);
+                result_ty = ty.mk_fn(cx.tystore, ast.proto_fn, args, tag_t);
             }
 
             auto tpt = tup(ty_param_count, result_ty);
@@ -702,7 +720,8 @@ mod Collect {
             let method meth_ty = meth_tys.(ix);
             let ast.method_ m_;
             let @ast.method m;
-            auto meth_tfn = ty.mk_fn(meth_ty.proto,
+            auto meth_tfn = ty.mk_fn(e.cx.tystore,
+                                     meth_ty.proto,
                                      meth_ty.inputs,
                                      meth_ty.output);
             m_ = rec(ann=triv_ann(meth_tfn)
@@ -713,7 +732,7 @@ mod Collect {
         }
         auto g = bind getter(e.cx, _);
         for (ast.obj_field fld in ob.fields) {
-            let @ty.t fty = ast_ty_to_ty(g, fld.ty);
+            let @ty.t fty = ast_ty_to_ty(e.cx.tystore, g, fld.ty);
             let ast.obj_field f = rec(ann=triv_ann(fty)
                 with fld
             );
@@ -724,8 +743,9 @@ mod Collect {
         alt (ob.dtor) {
             case (some[@ast.method](?d)) {
                 let vec[arg] inputs = vec();
-                let @ty.t output = ty.mk_nil();
-                auto dtor_tfn = ty.mk_fn(ast.proto_fn, inputs, output);
+                let @ty.t output = ty.mk_nil(e.cx.tystore);
+                auto dtor_tfn = ty.mk_fn(e.cx.tystore, ast.proto_fn, inputs,
+                                         output);
                 auto d_ = rec(ann=triv_ann(dtor_tfn) with d.node);
                 dtor = some[@ast.method](@rec(node=d_ with *d));
             }
@@ -762,7 +782,9 @@ mod Collect {
         ret @fold.respan[ast.item_](sp, item);
     }
 
-    fn collect_item_types(session.session sess, @ast.crate crate)
+    fn collect_item_types(session.session sess,
+                          @ty.type_store tystore,
+                          @ast.crate crate)
             -> tup(@ast.crate, ty.type_cache, @ty_item_table) {
         // First pass: collect all type item IDs.
         auto module = crate.node.module;
@@ -779,7 +801,8 @@ mod Collect {
 
         auto cx = @rec(sess=sess,
                        id_to_ty_item=id_to_ty_item,
-                       type_cache=type_cache);
+                       type_cache=type_cache,
+                       tystore=tystore);
 
         let @env e = @rec(cx=cx, abi=ast.native_abi_cdecl);
 
@@ -806,7 +829,8 @@ mod Collect {
 mod Unify {
     fn simple(@fn_ctxt fcx, @ty.t expected, @ty.t actual) -> ty.Unify.result {
         // FIXME: horrid botch
-        let vec[mutable @ty.t] param_substs = vec(mutable ty.mk_nil());
+        let vec[mutable @ty.t] param_substs =
+            vec(mutable ty.mk_nil(fcx.ccx.tystore));
         _vec.pop[mutable @ty.t](param_substs);
         ret with_params(fcx, expected, actual, param_substs);
     }
@@ -855,7 +879,8 @@ mod Unify {
                 }
 
                 unified_type =
-                    ty.substitute_type_params(param_substs_1, unified_type);
+                    ty.substitute_type_params(fcx.ccx.tystore, param_substs_1,
+                                              unified_type);
                 fcx.locals.insert(id, unified_type);
             }
             fn record_param(uint index, @ty.t binding) -> ty.Unify.result {
@@ -868,7 +893,8 @@ mod Unify {
                 alt (result) {
                     case (ures_ok(?new_subst)) {
                         param_substs.(index) = new_subst;
-                        ret ures_ok(ty.mk_bound_param(index));
+                        ret ures_ok(ty.mk_bound_param(fcx.ccx.tystore,
+                                                      index));
                     }
                     case (_) { ret result; }
                 }
@@ -877,7 +903,10 @@ mod Unify {
 
 
         auto handler = unify_handler(fcx, param_substs);
-        auto result = ty.Unify.unify(expected, actual, handler);
+        auto result = ty.Unify.unify(expected,
+                                     actual,
+                                     handler,
+                                     fcx.ccx.tystore);
         fcx.ccx.unify_cache.insert(cache_key, result);
         ret result;
     }
@@ -900,10 +929,10 @@ fn strip_boxes(@ty.t t) -> @ty.t {
     fail;
 }
 
-fn add_boxes(uint n, @ty.t t) -> @ty.t {
+fn add_boxes(@crate_ctxt ccx, uint n, @ty.t t) -> @ty.t {
     auto t1 = t;
     while (n != 0u) {
-        t1 = ty.mk_imm_box(t1);
+        t1 = ty.mk_imm_box(ccx.tystore, t1);
         n -= 1u;
     }
     ret t1;
@@ -957,7 +986,8 @@ mod Demand {
             implicit_boxes = count_boxes(actual);
         }
 
-        let vec[mutable @ty.t] ty_param_substs = vec(mutable ty.mk_nil());
+        let vec[mutable @ty.t] ty_param_substs =
+            vec(mutable ty.mk_nil(fcx.ccx.tystore));
         _vec.pop[mutable @ty.t](ty_param_substs);   // FIXME: horrid botch
         for (@ty.t ty_param_subst in ty_param_substs_0) {
             ty_param_substs += vec(mutable ty_param_subst);
@@ -971,7 +1001,8 @@ mod Demand {
                     result_ty_param_substs += vec(ty_param_subst);
                 }
 
-                ret tup(result_ty_param_substs, add_boxes(implicit_boxes, t));
+                ret tup(result_ty_param_substs,
+                        add_boxes(fcx.ccx, implicit_boxes, t));
             }
 
             case (ures_err(?err, ?expected, ?actual)) {
@@ -1004,12 +1035,13 @@ fn variant_arg_types(@crate_ctxt ccx, &span sp, ast.def_id vid,
 
     let vec[@ty.t] result = vec();
 
-    auto tpt = ty.lookup_item_type(ccx.sess, ccx.type_cache, vid);
+    auto tpt = ty.lookup_item_type(ccx.sess, ccx.tystore, ccx.type_cache,
+                                   vid);
     alt (tpt._1.struct) {
         case (ty.ty_fn(_, ?ins, _)) {
             // N-ary variant.
             for (ty.arg arg in ins) {
-                auto arg_ty = bind_params_in_type(arg.ty);
+                auto arg_ty = bind_params_in_type(ccx.tystore, arg.ty);
                 arg_ty = substitute_ty_params(ccx, arg_ty, ty_param_count,
                                               tag_ty_params, sp);
                 result += vec(arg_ty);
@@ -1380,7 +1412,7 @@ mod Pushdown {
                 let @ast.expr es_1;
                 alt (t.struct) {
                     case (ty.ty_chan(?subty)) {
-                        auto pt = ty.mk_port(subty);
+                        auto pt = ty.mk_port(fcx.ccx.tystore, subty);
                         es_1 = pushdown_expr(fcx, pt, es);
                     }
                     case (_) {
@@ -1396,7 +1428,8 @@ mod Pushdown {
                 let vec[ast.arm] arms_1 = vec();
                 for (ast.arm arm_0 in arms_0) {
                     auto block_1 = pushdown_block(fcx, expected, arm_0.block);
-                    t = Demand.simple(fcx, e.span, t, block_ty(block_1));
+                    t = Demand.simple(fcx, e.span, t,
+                                      block_ty(fcx.ccx.tystore, block_1));
                     auto arm_1 = rec(pat=arm_0.pat, block=block_1,
                                      index=arm_0.index);
                     arms_1 += vec(arm_1);
@@ -1407,16 +1440,20 @@ mod Pushdown {
             case (ast.expr_recv(?lval_0, ?expr_0, ?ann)) {
                 auto lval_1 = pushdown_expr(fcx, next_ty_var(fcx.ccx),
                                             lval_0);
-                auto t = expr_ty(lval_1);
-                auto expr_1 = pushdown_expr(fcx, ty.mk_port(t), expr_0);
+                auto t = expr_ty(fcx.ccx.tystore, lval_1);
+                auto expr_1 = pushdown_expr(fcx,
+                                            ty.mk_port(fcx.ccx.tystore, t),
+                                            expr_0);
                 e_1 = ast.expr_recv(lval_1, expr_1, ann);
             }
 
             case (ast.expr_send(?lval_0, ?expr_0, ?ann)) {
                 auto expr_1 = pushdown_expr(fcx, next_ty_var(fcx.ccx),
                                             expr_0);
-                auto t = expr_ty(expr_1);
-                auto lval_1 = pushdown_expr(fcx, ty.mk_chan(t), lval_0);
+                auto t = expr_ty(fcx.ccx.tystore, expr_1);
+                auto lval_1 = pushdown_expr(fcx,
+                                            ty.mk_chan(fcx.ccx.tystore, t),
+                                            lval_0);
                 e_1 = ast.expr_send(lval_1, expr_1, ann);
             }
 
@@ -1440,13 +1477,14 @@ mod Pushdown {
                 auto block_ = rec(stmts=bloc.node.stmts,
                                   expr=some[@ast.expr](e_1),
                                   index=bloc.node.index,
-                                  a=plain_ann());
+                                  a=plain_ann(fcx.ccx.tystore));
                 ret fold.respan[ast.block_](bloc.span, block_);
             }
             case (none[@ast.expr]) {
-                Demand.simple(fcx, bloc.span, expected, ty.mk_nil());
+                Demand.simple(fcx, bloc.span, expected,
+                              ty.mk_nil(fcx.ccx.tystore));
                 ret fold.respan[ast.block_](bloc.span,
-                      rec(a = plain_ann() with bloc.node));
+                      rec(a = plain_ann(fcx.ccx.tystore) with bloc.node));
             }
         }
     }
@@ -1488,7 +1526,7 @@ fn resolve_local_types_in_annotation(&option.t[@fn_ctxt] env, ast.ann ann)
         }
         case (ast.ann_type(?typ, ?tps, ?ts_info)) {
             auto f = bind resolver(fcx, _);
-            auto new_type = ty.fold_ty(f, ann_to_type(ann));
+            auto new_type = ty.fold_ty(fcx.ccx.tystore, f, ann_to_type(ann));
             ret ast.ann_type(new_type, tps, ts_info);
         }
     }
@@ -1522,18 +1560,18 @@ fn resolve_local_types_in_block(&@fn_ctxt fcx, &ast.block block)
 
 // AST fragment checking
 
-fn check_lit(@ast.lit lit) -> @ty.t {
+fn check_lit(@crate_ctxt ccx, @ast.lit lit) -> @ty.t {
     alt (lit.node) {
-        case (ast.lit_str(_))           { ret ty.mk_str(); }
-        case (ast.lit_char(_))          { ret ty.mk_char(); }
-        case (ast.lit_int(_))           { ret ty.mk_int();  }
-        case (ast.lit_float(_))         { ret ty.mk_float();  }
+        case (ast.lit_str(_))           { ret ty.mk_str(ccx.tystore); }
+        case (ast.lit_char(_))          { ret ty.mk_char(ccx.tystore); }
+        case (ast.lit_int(_))           { ret ty.mk_int(ccx.tystore);  }
+        case (ast.lit_float(_))         { ret ty.mk_float(ccx.tystore);  }
         case (ast.lit_mach_float(?tm, _))
-                                        { ret ty.mk_mach(tm); }
-        case (ast.lit_uint(_))          { ret ty.mk_uint(); }
-        case (ast.lit_mach_int(?tm, _)) { ret ty.mk_mach(tm); }
-        case (ast.lit_nil)              { ret ty.mk_nil();  }
-        case (ast.lit_bool(_))          { ret ty.mk_bool(); }
+                                        { ret ty.mk_mach(ccx.tystore, tm); }
+        case (ast.lit_uint(_))          { ret ty.mk_uint(ccx.tystore); }
+        case (ast.lit_mach_int(?tm, _)) { ret ty.mk_mach(ccx.tystore, tm); }
+        case (ast.lit_nil)              { ret ty.mk_nil(ccx.tystore);  }
+        case (ast.lit_bool(_))          { ret ty.mk_bool(ccx.tystore); }
     }
 
     fail; // not reached
@@ -1546,7 +1584,7 @@ fn check_pat(&@fn_ctxt fcx, @ast.pat pat) -> @ast.pat {
             new_pat = ast.pat_wild(triv_ann(next_ty_var(fcx.ccx)));
         }
         case (ast.pat_lit(?lt, _)) {
-            new_pat = ast.pat_lit(lt, triv_ann(check_lit(lt)));
+            new_pat = ast.pat_lit(lt, triv_ann(check_lit(fcx.ccx, lt)));
         }
         case (ast.pat_bind(?id, ?def_id, _)) {
             auto ann = triv_ann(next_ty_var(fcx.ccx));
@@ -1554,13 +1592,13 @@ fn check_pat(&@fn_ctxt fcx, @ast.pat pat) -> @ast.pat {
         }
         case (ast.pat_tag(?p, ?subpats, ?vdef_opt, _)) {
             auto vdef = option.get[ast.variant_def](vdef_opt);
-            auto t = ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.type_cache,
-                                         vdef._1)._1;
+            auto t = ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.tystore,
+                                         fcx.ccx.type_cache, vdef._1)._1;
             auto len = _vec.len[ast.ident](p.node.idents);
             auto last_id = p.node.idents.(len - 1u);
 
-            auto tpt = ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.type_cache,
-                                           vdef._0);
+            auto tpt = ty.lookup_item_type(fcx.ccx.sess, fcx.ccx.tystore,
+                                           fcx.ccx.type_cache, vdef._0);
             auto ann = instantiate_path(fcx, p, tpt, pat.span);
 
             alt (t.struct) {
@@ -1635,7 +1673,8 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                     args_0 += vec(some[@ast.expr](a_0));
 
                     // FIXME: this breaks aliases. We need a ty_fn_arg.
-                    auto arg_ty = rec(mode=ast.val, ty=expr_ty(a_0));
+                    auto arg_ty = rec(mode=ast.val,
+                                      ty=expr_ty(fcx.ccx.tystore, a_0));
                     _vec.push[arg](arg_tys_0, arg_ty);
                 }
                 case (none[@ast.expr]) {
@@ -1650,12 +1689,12 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
         auto rt_0 = next_ty_var(fcx.ccx);
         auto t_0;
-        alt (expr_ty(f_0).struct) {
+        alt (expr_ty(fcx.ccx.tystore, f_0).struct) {
             case (ty.ty_fn(?proto, _, _))   {
-                t_0 = ty.mk_fn(proto, arg_tys_0, rt_0);
+                t_0 = ty.mk_fn(fcx.ccx.tystore, proto, arg_tys_0, rt_0);
             }
             case (ty.ty_native_fn(?abi, _, _))   {
-                t_0 = ty.mk_native_fn(abi, arg_tys_0, rt_0);
+                t_0 = ty.mk_native_fn(fcx.ccx.tystore, abi, arg_tys_0, rt_0);
             }
             case (_) {
                 log_err "check_call_or_bind(): fn expr doesn't have fn type";
@@ -1664,7 +1703,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
         }
 
         // Unify the callee and arguments.
-        auto tpt_0 = ty.expr_ty_params_and_ty(f_0);
+        auto tpt_0 = ty.expr_ty_params_and_ty(fcx.ccx.tystore, f_0);
         auto tpt_1 = Demand.full(fcx, f.span, tpt_0._1, t_0, tpt_0._0,
                                  NO_AUTODEREF);
         auto f_1 = ty.replace_expr_type(f_0, tpt_1);
@@ -1677,13 +1716,15 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
         -> tup(@ast.expr, @ast.expr, ast.ann) {
         auto lhs_0 = check_expr(fcx, lhs);
         auto rhs_0 = check_expr(fcx, rhs);
-        auto lhs_t0 = expr_ty(lhs_0);
-        auto rhs_t0 = expr_ty(rhs_0);
+        auto lhs_t0 = expr_ty(fcx.ccx.tystore, lhs_0);
+        auto rhs_t0 = expr_ty(fcx.ccx.tystore, rhs_0);
 
         auto lhs_1 = Pushdown.pushdown_expr(fcx, rhs_t0, lhs_0);
-        auto rhs_1 = Pushdown.pushdown_expr(fcx, expr_ty(lhs_1), rhs_0);
+        auto rhs_1 = Pushdown.pushdown_expr(fcx,
+                                            expr_ty(fcx.ccx.tystore, lhs_1),
+                                            rhs_0);
 
-        auto ann = triv_ann(expr_ty(rhs_1));
+        auto ann = triv_ann(expr_ty(fcx.ccx.tystore, rhs_1));
         ret tup(lhs_1, rhs_1, ann);
     }
 
@@ -1710,7 +1751,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
     alt (expr.node) {
         case (ast.expr_lit(?lit, _)) {
-            auto typ = check_lit(lit);
+            auto typ = check_lit(fcx.ccx, lit);
             auto ann = triv_ann(typ);
             ret @fold.respan[ast.expr_](expr.span, ast.expr_lit(lit, ann));
         }
@@ -1719,23 +1760,25 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
         case (ast.expr_binary(?binop, ?lhs, ?rhs, _)) {
             auto lhs_0 = check_expr(fcx, lhs);
             auto rhs_0 = check_expr(fcx, rhs);
-            auto lhs_t0 = expr_ty(lhs_0);
-            auto rhs_t0 = expr_ty(rhs_0);
+            auto lhs_t0 = expr_ty(fcx.ccx.tystore, lhs_0);
+            auto rhs_t0 = expr_ty(fcx.ccx.tystore, rhs_0);
 
             // FIXME: Binops have a bit more subtlety than this.
             auto lhs_1 = Pushdown.pushdown_expr_full(fcx, rhs_t0, lhs_0,
                                                      AUTODEREF_OK);
-            auto rhs_1 = Pushdown.pushdown_expr_full(fcx, expr_ty(lhs_1),
-                                                     rhs_0, AUTODEREF_OK);
+            auto rhs_1 =
+                Pushdown.pushdown_expr_full(fcx,
+                                            expr_ty(fcx.ccx.tystore, lhs_1),
+                                            rhs_0, AUTODEREF_OK);
 
             auto t = strip_boxes(lhs_t0);
             alt (binop) {
-                case (ast.eq) { t = ty.mk_bool(); }
-                case (ast.lt) { t = ty.mk_bool(); }
-                case (ast.le) { t = ty.mk_bool(); }
-                case (ast.ne) { t = ty.mk_bool(); }
-                case (ast.ge) { t = ty.mk_bool(); }
-                case (ast.gt) { t = ty.mk_bool(); }
+                case (ast.eq) { t = ty.mk_bool(fcx.ccx.tystore); }
+                case (ast.lt) { t = ty.mk_bool(fcx.ccx.tystore); }
+                case (ast.le) { t = ty.mk_bool(fcx.ccx.tystore); }
+                case (ast.ne) { t = ty.mk_bool(fcx.ccx.tystore); }
+                case (ast.ge) { t = ty.mk_bool(fcx.ccx.tystore); }
+                case (ast.gt) { t = ty.mk_bool(fcx.ccx.tystore); }
                 case (_) { /* fall through */ }
             }
 
@@ -1748,10 +1791,11 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
         case (ast.expr_unary(?unop, ?oper, _)) {
             auto oper_1 = check_expr(fcx, oper);
-            auto oper_t = expr_ty(oper_1);
+            auto oper_t = expr_ty(fcx.ccx.tystore, oper_1);
             alt (unop) {
                 case (ast.box(?mut)) {
-                    oper_t = ty.mk_box(rec(ty=oper_t, mut=mut));
+                    oper_t = ty.mk_box(fcx.ccx.tystore,
+                                       rec(ty=oper_t, mut=mut));
                 }
                 case (ast.deref) {
                     alt (oper_t.struct) {
@@ -1775,7 +1819,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
         }
 
         case (ast.expr_path(?pth, ?defopt, _)) {
-            auto t = ty.mk_nil();
+            auto t = ty.mk_nil(fcx.ccx.tystore);
             check (defopt != none[ast.def]);
             auto defn = option.get[ast.def](defopt);
 
@@ -1801,7 +1845,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
         case (ast.expr_ext(?p, ?args, ?body, ?expanded, _)) {
             auto exp_ = check_expr(fcx, expanded);
-            auto t = expr_ty(exp_);
+            auto t = expr_ty(fcx.ccx.tystore, exp_);
             auto ann = triv_ann(t);
             ret @fold.respan[ast.expr_](expr.span,
                                         ast.expr_ext(p, args, body, exp_,
@@ -1810,23 +1854,23 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
         case (ast.expr_fail(_)) {
             ret @fold.respan[ast.expr_](expr.span,
-                                        ast.expr_fail(plain_ann()));
+                ast.expr_fail(plain_ann(fcx.ccx.tystore)));
         }
 
         case (ast.expr_break(_)) {
             ret @fold.respan[ast.expr_](expr.span,
-                                        ast.expr_break(plain_ann()));
+                ast.expr_break(plain_ann(fcx.ccx.tystore)));
         }
 
         case (ast.expr_cont(_)) {
             ret @fold.respan[ast.expr_](expr.span,
-                                        ast.expr_cont(plain_ann()));
+                ast.expr_cont(plain_ann(fcx.ccx.tystore)));
         }
 
         case (ast.expr_ret(?expr_opt, _)) {
             alt (expr_opt) {
                 case (none[@ast.expr]) {
-                    auto nil = ty.mk_nil();
+                    auto nil = ty.mk_nil(fcx.ccx.tystore);
                     if (!are_compatible(fcx, fcx.ret_ty, nil)) {
                         fcx.ccx.sess.err("ret; in function "
                                          + "returning non-nil");
@@ -1834,7 +1878,8 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
                     ret @fold.respan[ast.expr_]
                         (expr.span,
-                         ast.expr_ret(none[@ast.expr], plain_ann()));
+                         ast.expr_ret(none[@ast.expr],
+                                      plain_ann(fcx.ccx.tystore)));
                 }
 
                 case (some[@ast.expr](?e)) {
@@ -1842,7 +1887,8 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                     auto expr_1 = Pushdown.pushdown_expr(fcx, fcx.ret_ty,
                                                          expr_0);
                     ret @fold.respan[ast.expr_]
-                        (expr.span, ast.expr_ret(some(expr_1), plain_ann()));
+                        (expr.span, ast.expr_ret(some(expr_1),
+                                                 plain_ann(fcx.ccx.tystore)));
                 }
             }
         }
@@ -1850,7 +1896,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
         case (ast.expr_put(?expr_opt, _)) {
             alt (expr_opt) {
                 case (none[@ast.expr]) {
-                    auto nil = ty.mk_nil();
+                    auto nil = ty.mk_nil(fcx.ccx.tystore);
                     if (!are_compatible(fcx, fcx.ret_ty, nil)) {
                         fcx.ccx.sess.err("put; in function "
                                          + "putting non-nil");
@@ -1858,7 +1904,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
                     ret @fold.respan[ast.expr_]
                         (expr.span, ast.expr_put(none[@ast.expr],
-                                                 plain_ann()));
+                         plain_ann(fcx.ccx.tystore)));
                 }
 
                 case (some[@ast.expr](?e)) {
@@ -1866,7 +1912,8 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                     auto expr_1 = Pushdown.pushdown_expr(fcx, fcx.ret_ty,
                                                          expr_0);
                     ret @fold.respan[ast.expr_]
-                        (expr.span, ast.expr_put(some(expr_1), plain_ann()));
+                        (expr.span, ast.expr_put(some(expr_1),
+                                                 plain_ann(fcx.ccx.tystore)));
                 }
             }
         }
@@ -1877,21 +1924,23 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             auto expr_0 = check_expr(fcx, e);
             auto expr_1 = Pushdown.pushdown_expr(fcx, fcx.ret_ty, expr_0);
             ret @fold.respan[ast.expr_](expr.span,
-                                        ast.expr_be(expr_1,
-                                                    plain_ann()));
+                ast.expr_be(expr_1, plain_ann(fcx.ccx.tystore)));
         }
 
         case (ast.expr_log(?l,?e,_)) {
             auto expr_t = check_expr(fcx, e);
             ret @fold.respan[ast.expr_]
-                (expr.span, ast.expr_log(l, expr_t, plain_ann()));
+                (expr.span, ast.expr_log(l, expr_t,
+                                         plain_ann(fcx.ccx.tystore)));
         }
 
         case (ast.expr_check_expr(?e, _)) {
             auto expr_t = check_expr(fcx, e);
-            Demand.simple(fcx, expr.span, ty.mk_bool(), expr_ty(expr_t));
+            Demand.simple(fcx, expr.span, ty.mk_bool(fcx.ccx.tystore),
+                          expr_ty(fcx.ccx.tystore, expr_t));
             ret @fold.respan[ast.expr_]
-                (expr.span, ast.expr_check_expr(expr_t, plain_ann()));
+                (expr.span, ast.expr_check_expr(expr_t,
+                                                plain_ann(fcx.ccx.tystore)));
         }
 
         case (ast.expr_assign(?lhs, ?rhs, _)) {
@@ -1914,12 +1963,12 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
         case (ast.expr_send(?lhs, ?rhs, _)) {
             auto lhs_0 = check_expr(fcx, lhs);
             auto rhs_0 = check_expr(fcx, rhs);
-            auto rhs_t = expr_ty(rhs_0);
+            auto rhs_t = expr_ty(fcx.ccx.tystore, rhs_0);
 
-            auto chan_t = ty.mk_chan(rhs_t);
+            auto chan_t = ty.mk_chan(fcx.ccx.tystore, rhs_t);
             auto lhs_1 = Pushdown.pushdown_expr(fcx, chan_t, lhs_0);
             auto item_t;
-            alt (expr_ty(lhs_1).struct) {
+            alt (expr_ty(fcx.ccx.tystore, lhs_1).struct) {
                 case (ty.ty_chan(?it)) {
                     item_t = it;
                 }
@@ -1937,12 +1986,12 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
         case (ast.expr_recv(?lhs, ?rhs, _)) {
             auto lhs_0 = check_expr(fcx, lhs);
             auto rhs_0 = check_expr(fcx, rhs);
-            auto lhs_t1 = expr_ty(lhs_0);
+            auto lhs_t1 = expr_ty(fcx.ccx.tystore, lhs_0);
 
-            auto port_t = ty.mk_port(lhs_t1);
+            auto port_t = ty.mk_port(fcx.ccx.tystore, lhs_t1);
             auto rhs_1 = Pushdown.pushdown_expr(fcx, port_t, rhs_0);
             auto item_t;
-            alt (expr_ty(rhs_0).struct) {
+            alt (expr_ty(fcx.ccx.tystore, rhs_0).struct) {
                 case (ty.ty_port(?it)) {
                     item_t = it;
                 }
@@ -1959,10 +2008,12 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
         case (ast.expr_if(?cond, ?thn, ?elsopt, _)) {
             auto cond_0 = check_expr(fcx, cond);
-            auto cond_1 = Pushdown.pushdown_expr(fcx, ty.mk_bool(), cond_0);
+            auto cond_1 = Pushdown.pushdown_expr(fcx,
+                                                 ty.mk_bool(fcx.ccx.tystore),
+                                                 cond_0);
 
             auto thn_0 = check_block(fcx, thn);
-            auto thn_t = block_ty(thn_0);
+            auto thn_t = block_ty(fcx.ccx.tystore, thn_0);
 
             auto elsopt_1;
             auto elsopt_t;
@@ -1971,11 +2022,11 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                     auto els_0 = check_expr(fcx, els);
                     auto els_1 = Pushdown.pushdown_expr(fcx, thn_t, els_0);
                     elsopt_1 = some[@ast.expr](els_1);
-                    elsopt_t = expr_ty(els_1);
+                    elsopt_t = expr_ty(fcx.ccx.tystore, els_1);
                 }
                 case (none[@ast.expr]) {
                     elsopt_1 = none[@ast.expr];
-                    elsopt_t = ty.mk_nil();
+                    elsopt_t = ty.mk_nil(fcx.ccx.tystore);
                 }
             }
 
@@ -1995,7 +2046,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             // FIXME: enforce that the type of the decl is the element type
             // of the seq.
 
-            auto ann = triv_ann(ty.mk_nil());
+            auto ann = triv_ann(ty.mk_nil(fcx.ccx.tystore));
             ret @fold.respan[ast.expr_](expr.span,
                                         ast.expr_for(decl_1, seq_1,
                                                      body_1, ann));
@@ -2006,7 +2057,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             auto seq_1 = check_expr(fcx, seq);
             auto body_1 = check_block(fcx, body);
 
-            auto ann = triv_ann(ty.mk_nil());
+            auto ann = triv_ann(ty.mk_nil(fcx.ccx.tystore));
             ret @fold.respan[ast.expr_](expr.span,
                                         ast.expr_for_each(decl_1, seq_1,
                                                           body_1, ann));
@@ -2014,20 +2065,24 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
         case (ast.expr_while(?cond, ?body, _)) {
             auto cond_0 = check_expr(fcx, cond);
-            auto cond_1 = Pushdown.pushdown_expr(fcx, ty.mk_bool(), cond_0);
+            auto cond_1 = Pushdown.pushdown_expr(fcx,
+                                                 ty.mk_bool(fcx.ccx.tystore),
+                                                 cond_0);
             auto body_1 = check_block(fcx, body);
 
-            auto ann = triv_ann(ty.mk_nil());
+            auto ann = triv_ann(ty.mk_nil(fcx.ccx.tystore));
             ret @fold.respan[ast.expr_](expr.span,
                                         ast.expr_while(cond_1, body_1, ann));
         }
 
         case (ast.expr_do_while(?body, ?cond, _)) {
             auto cond_0 = check_expr(fcx, cond);
-            auto cond_1 = Pushdown.pushdown_expr(fcx, ty.mk_bool(), cond_0);
+            auto cond_1 = Pushdown.pushdown_expr(fcx,
+                                                 ty.mk_bool(fcx.ccx.tystore),
+                                                 cond_0);
             auto body_1 = check_block(fcx, body);
 
-            auto ann = triv_ann(block_ty(body_1));
+            auto ann = triv_ann(block_ty(fcx.ccx.tystore, body_1));
             ret @fold.respan[ast.expr_](expr.span,
                                         ast.expr_do_while(body_1, cond_1,
                                                           ann));
@@ -2038,13 +2093,13 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
             // Typecheck the patterns first, so that we get types for all the
             // bindings.
-            auto pattern_ty = expr_ty(expr_0);
+            auto pattern_ty = expr_ty(fcx.ccx.tystore, expr_0);
 
             let vec[@ast.pat] pats_0 = vec();
             for (ast.arm arm in arms) {
                 auto pat_0 = check_pat(fcx, arm.pat);
                 pattern_ty = Demand.simple(fcx, pat_0.span, pattern_ty,
-                                           pat_ty(pat_0));
+                                           pat_ty(fcx.ccx.tystore, pat_0));
                 pats_0 += vec(pat_0);
             }
 
@@ -2060,7 +2115,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             for (ast.arm arm in arms) {
                 auto block_0 = check_block(fcx, arm.block);
                 result_ty = Demand.simple(fcx, block_0.span, result_ty,
-                                          block_ty(block_0));
+                                          block_ty(fcx.ccx.tystore, block_0));
                 blocks_0 += vec(block_0);
             }
 
@@ -2088,10 +2143,10 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             auto ann;
             alt (b_0.node.expr) {
                 case (some[@ast.expr](?expr)) {
-                    ann = triv_ann(expr_ty(expr));
+                    ann = triv_ann(expr_ty(fcx.ccx.tystore, expr));
                 }
                 case (none[@ast.expr]) {
-                    ann = triv_ann(ty.mk_nil());
+                    ann = triv_ann(ty.mk_nil(fcx.ccx.tystore));
                 }
             }
             ret @fold.respan[ast.expr_](expr.span,
@@ -2106,7 +2161,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             auto proto_1;
             let vec[ty.arg] arg_tys_1 = vec();
             auto rt_1;
-            alt (expr_ty(result._0).struct) {
+            alt (expr_ty(fcx.ccx.tystore, result._0).struct) {
                 case (ty.ty_fn(?proto, ?arg_tys, ?rt)) {
                     proto_1 = proto;
                     rt_1 = rt;
@@ -2130,7 +2185,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                 }
             }
 
-            auto t_1 = ty.mk_fn(proto_1, arg_tys_1, rt_1);
+            auto t_1 = ty.mk_fn(fcx.ccx.tystore, proto_1, arg_tys_1, rt_1);
             auto ann = triv_ann(t_1);
             ret @fold.respan[ast.expr_](expr.span,
                                         ast.expr_bind(result._0, result._1,
@@ -2143,8 +2198,8 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             auto args_1 = result._1;
 
             // Pull the return type out of the type of the function.
-            auto rt_1 = ty.mk_nil();    // FIXME: typestate botch
-            alt (expr_ty(f_1).struct) {
+            auto rt_1 = ty.mk_nil(fcx.ccx.tystore);  // FIXME: typestate botch
+            alt (expr_ty(fcx.ccx.tystore, f_1).struct) {
                 case (ty.ty_fn(_,_,?rt))    { rt_1 = rt; }
                 case (ty.ty_native_fn(_, _, ?rt))    { rt_1 = rt; }
                 case (_) {
@@ -2159,7 +2214,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
         }
 
         case (ast.expr_self_method(?id, _)) {
-            auto t = ty.mk_nil();
+            auto t = ty.mk_nil(fcx.ccx.tystore);
             let @ty.t this_obj_ty;
 
             // Grab the type of the current object
@@ -2167,7 +2222,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             alt (this_obj_id) {
                 case (some[ast.def_id](?def_id)) {
                     this_obj_ty = ty.lookup_item_type(fcx.ccx.sess,
-                        fcx.ccx.type_cache, def_id)._1;
+                        fcx.ccx.tystore, fcx.ccx.type_cache, def_id)._1;
                 }
                 case (_) { fail; }
             }
@@ -2180,7 +2235,8 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                 case (ty.ty_obj(?methods)) {
                     for (ty.method method in methods) {
                         if (method.ident == id) {
-                            t = ty.method_ty_to_fn_ty(method);
+                            t = ty.method_ty_to_fn_ty(fcx.ccx.tystore,
+                                                      method);
                         }
                     }
                 }
@@ -2199,7 +2255,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             auto args_1 = result._1;
 
             // Check the return type
-            alt (expr_ty(f_1).struct) {
+            alt (expr_ty(fcx.ccx.tystore, f_1).struct) {
                 case (ty.ty_fn(_,_,?rt)) {
                     alt (rt.struct) {
                         case (ty.ty_nil) {
@@ -2217,7 +2273,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
             // FIXME: Other typechecks needed
 
-            auto ann = triv_ann(ty.mk_task());
+            auto ann = triv_ann(ty.mk_task(fcx.ccx.tystore));
             ret @fold.respan[ast.expr_](expr.span,
                                         ast.expr_spawn(dom, name,
                                                        f_1, args_1, ann));
@@ -2227,13 +2283,12 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
             auto e_1 = check_expr(fcx, e);
             auto t_1 = ast_ty_to_ty_crate(fcx.ccx, t);
             // FIXME: there are more forms of cast to support, eventually.
-            if (! (type_is_scalar(expr_ty(e_1)) &&
+            if (! (type_is_scalar(expr_ty(fcx.ccx.tystore, e_1)) &&
                    type_is_scalar(t_1))) {
                 fcx.ccx.sess.span_err(expr.span,
-                                      "non-scalar cast: "
-                                      + ty_to_str(expr_ty(e_1))
-                                      + " as "
-                                      +  ty_to_str(t_1));
+                    "non-scalar cast: " +
+                    ty_to_str(expr_ty(fcx.ccx.tystore, e_1)) + " as " +
+                    ty_to_str(t_1));
             }
 
             auto ann = triv_ann(t_1);
@@ -2249,17 +2304,18 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                 t = next_ty_var(fcx.ccx);
             } else {
                 auto expr_1 = check_expr(fcx, args.(0));
-                t = expr_ty(expr_1);
+                t = expr_ty(fcx.ccx.tystore, expr_1);
             }
 
             for (@ast.expr e in args) {
                 auto expr_1 = check_expr(fcx, e);
-                auto expr_t = expr_ty(expr_1);
+                auto expr_t = expr_ty(fcx.ccx.tystore, expr_1);
                 Demand.simple(fcx, expr.span, t, expr_t);
                 _vec.push[@ast.expr](args_1,expr_1);
             }
 
-            auto ann = triv_ann(ty.mk_vec(rec(ty=t, mut=mut)));
+            auto ann = triv_ann(ty.mk_vec(fcx.ccx.tystore,
+                                          rec(ty=t, mut=mut)));
             ret @fold.respan[ast.expr_](expr.span,
                                         ast.expr_vec(args_1, mut, ann));
         }
@@ -2270,12 +2326,12 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
             for (ast.elt e in elts) {
                 auto expr_1 = check_expr(fcx, e.expr);
-                auto expr_t = expr_ty(expr_1);
+                auto expr_t = expr_ty(fcx.ccx.tystore, expr_1);
                 _vec.push[ast.elt](elts_1, rec(expr=expr_1 with e));
                 elts_mt += vec(rec(ty=expr_t, mut=e.mut));
             }
 
-            auto ann = triv_ann(ty.mk_tup(elts_mt));
+            auto ann = triv_ann(ty.mk_tup(fcx.ccx.tystore, elts_mt));
             ret @fold.respan[ast.expr_](expr.span,
                                         ast.expr_tup(elts_1, ann));
         }
@@ -2295,7 +2351,7 @@ 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);
+                auto expr_t = expr_ty(fcx.ccx.tystore, expr_1);
                 _vec.push[ast.field](fields_1, rec(expr=expr_1 with f));
 
                 auto expr_mt = rec(ty=expr_t, mut=f.mut);
@@ -2306,12 +2362,12 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
             alt (base) {
                 case (none[@ast.expr]) {
-                    ann = triv_ann(ty.mk_rec(fields_t));
+                    ann = triv_ann(ty.mk_rec(fcx.ccx.tystore, fields_t));
                 }
 
                 case (some[@ast.expr](?bexpr)) {
                     auto bexpr_1 = check_expr(fcx, bexpr);
-                    auto bexpr_t = expr_ty(bexpr_1);
+                    auto bexpr_t = expr_ty(fcx.ccx.tystore, bexpr_1);
 
                     let vec[field] base_fields = vec();
 
@@ -2353,7 +2409,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
         case (ast.expr_field(?base, ?field, _)) {
             auto base_1 = check_expr(fcx, base);
-            auto base_t = strip_boxes(expr_ty(base_1));
+            auto base_t = strip_boxes(expr_ty(fcx.ccx.tystore, base_1));
             alt (base_t.struct) {
                 case (ty.ty_tup(?args)) {
                     let uint ix = ty.field_num(fcx.ccx.sess,
@@ -2391,7 +2447,8 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                                               "bad index on obj");
                     }
                     auto meth = methods.(ix);
-                    auto t = ty.mk_fn(meth.proto, meth.inputs, meth.output);
+                    auto t = ty.mk_fn(fcx.ccx.tystore, meth.proto,
+                                      meth.inputs, meth.output);
                     auto ann = triv_ann(t);
                     ret @fold.respan[ast.expr_](expr.span,
                                                 ast.expr_field(base_1,
@@ -2409,10 +2466,10 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
         case (ast.expr_index(?base, ?idx, _)) {
             auto base_1 = check_expr(fcx, base);
-            auto base_t = strip_boxes(expr_ty(base_1));
+            auto base_t = strip_boxes(expr_ty(fcx.ccx.tystore, base_1));
 
             auto idx_1 = check_expr(fcx, idx);
-            auto idx_t = expr_ty(idx_1);
+            auto idx_t = expr_ty(fcx.ccx.tystore, idx_1);
 
             alt (base_t.struct) {
                 case (ty.ty_vec(?mt)) {
@@ -2435,7 +2492,8 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
                              "non-integral type of str index: "
                              + ty_to_str(idx_t));
                     }
-                    auto ann = triv_ann(ty.mk_mach(common.ty_u8));
+                    auto ann = triv_ann(ty.mk_mach(fcx.ccx.tystore,
+                                                   common.ty_u8));
                     ret @fold.respan[ast.expr_](expr.span,
                                                 ast.expr_index(base_1,
                                                                idx_1,
@@ -2452,17 +2510,17 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 
         case (ast.expr_port(_)) {
             auto t = next_ty_var(fcx.ccx);
-            auto pt = ty.mk_port(t);
+            auto pt = ty.mk_port(fcx.ccx.tystore, t);
             auto ann = triv_ann(pt);
             ret @fold.respan[ast.expr_](expr.span, ast.expr_port(ann));
         }
 
         case (ast.expr_chan(?x, _)) {
             auto expr_1 = check_expr(fcx, x);
-            auto port_t = expr_ty(expr_1);
+            auto port_t = expr_ty(fcx.ccx.tystore, expr_1);
             alt (port_t.struct) {
                 case (ty.ty_port(?subtype)) {
-                    auto ct = ty.mk_chan(subtype);
+                    auto ct = ty.mk_chan(fcx.ccx.tystore, subtype);
                     auto ann = triv_ann(ct);
                     ret @fold.respan[ast.expr_](expr.span,
                                                 ast.expr_chan(expr_1, ann));
@@ -2484,7 +2542,7 @@ fn check_expr(&@fn_ctxt fcx, @ast.expr expr) -> @ast.expr {
 }
 
 fn next_ty_var(@crate_ctxt ccx) -> @ty.t {
-    auto t = ty.mk_var(ccx.next_var_id);
+    auto t = ty.mk_var(ccx.tystore, ccx.next_var_id);
     ccx.next_var_id += 1;
     ret t;
 }
@@ -2495,7 +2553,7 @@ fn check_decl_local(&@fn_ctxt fcx, &@ast.decl decl) -> @ast.decl {
 
             auto t;
 
-            t = middle.ty.mk_nil();
+            t = ty.mk_nil(fcx.ccx.tystore);
             
             alt (local.ty) {
                 case (none[@ast.ty]) {
@@ -2521,14 +2579,14 @@ fn check_decl_local(&@fn_ctxt fcx, &@ast.decl decl) -> @ast.decl {
             alt (local.init) {
                 case (some[ast.initializer](?init)) {
                     auto expr_0 = check_expr(fcx, init.expr);
-                    auto lty = ty.mk_local(local.id);
+                    auto lty = ty.mk_local(fcx.ccx.tystore, local.id);
                     auto expr_1;
                     alt (init.op) {
                         case (ast.init_assign) {
                             expr_1 = Pushdown.pushdown_expr(fcx, lty, expr_0);
                         }
                         case (ast.init_recv) {
-                            auto port_ty = ty.mk_port(lty);
+                            auto port_ty = ty.mk_port(fcx.ccx.tystore, lty);
                             expr_1 = Pushdown.pushdown_expr(fcx, port_ty,
                                                             expr_0);
                         }
@@ -2566,7 +2624,9 @@ fn check_stmt(&@fn_ctxt fcx, &@ast.stmt stmt) -> @ast.stmt {
 
         case (ast.stmt_expr(?expr,?a)) {
             auto expr_t = check_expr(fcx, expr);
-            expr_t = Pushdown.pushdown_expr(fcx, expr_ty(expr_t), expr_t);
+            expr_t = Pushdown.pushdown_expr(fcx,
+                                            expr_ty(fcx.ccx.tystore, expr_t),
+                                            expr_t);
             ret @fold.respan[ast.stmt_](stmt.span, ast.stmt_expr(expr_t, a));
         }
     }
@@ -2585,7 +2645,9 @@ fn check_block(&@fn_ctxt fcx, &ast.block block) -> ast.block {
         case (none[@ast.expr]) { /* empty */ }
         case (some[@ast.expr](?e)) {
             auto expr_t = check_expr(fcx, e);
-            expr_t = Pushdown.pushdown_expr(fcx, expr_ty(expr_t), expr_t);
+            expr_t = Pushdown.pushdown_expr(fcx,
+                                            expr_ty(fcx.ccx.tystore, expr_t),
+                                            expr_t);
             expr = some[@ast.expr](expr_t);
         }
     }
@@ -2593,7 +2655,7 @@ fn check_block(&@fn_ctxt fcx, &ast.block block) -> ast.block {
     ret fold.respan[ast.block_](block.span,
                                 rec(stmts=stmts, expr=expr,
                                     index=block.node.index,
-                                    a=plain_ann()));
+                                    a=plain_ann(fcx.ccx.tystore)));
 }
 
 fn check_const(&@crate_ctxt ccx, &span sp, ast.ident ident, @ast.ty t,
@@ -2660,7 +2722,7 @@ fn check_item_fn(&@crate_ctxt ccx, &span sp, ast.ident ident, &ast._fn f,
     }
 
     auto output_ty = ast_ty_to_ty_crate(ccx, f.decl.output);
-    auto fn_ann = triv_ann(ty.mk_fn(f.proto, inputs, output_ty));
+    auto fn_ann = triv_ann(ty.mk_fn(ccx.tystore, f.proto, inputs, output_ty));
 
     auto item = ast.item_fn(ident, f, ty_params, id, fn_ann);
     ret @fold.respan[ast.item_](sp, item);
@@ -2714,8 +2776,10 @@ fn eq_unify_cache_entry(&unify_cache_entry a, &unify_cache_entry b) -> bool {
 
 type typecheck_result = tup(@ast.crate, ty.type_cache);
 
-fn check_crate(session.session sess, @ast.crate crate) -> typecheck_result {
-    auto result = Collect.collect_item_types(sess, crate);
+fn check_crate(session.session sess,
+               @ty.type_store tystore,
+               @ast.crate crate) -> typecheck_result {
+    auto result = Collect.collect_item_types(sess, tystore, crate);
 
     let vec[ast.obj_field] fields = vec();
 
@@ -2732,7 +2796,8 @@ fn check_crate(session.session sess, @ast.crate crate) -> typecheck_result {
                     mutable next_var_id=0,
                     unify_cache=unify_cache,
                     mutable cache_hits=0u,
-                    mutable cache_misses=0u);
+                    mutable cache_misses=0u,
+                    tystore=tystore);
 
     auto fld = fold.new_identity_fold[@crate_ctxt]();
 
diff --git a/src/comp/util/common.rs b/src/comp/util/common.rs
index ef99a226e77..afec418c4e5 100644
--- a/src/comp/util/common.rs
+++ b/src/comp/util/common.rs
@@ -110,8 +110,8 @@ fn field_exprs(vec[ast.field] fields) -> vec [@ast.expr] {
     ret _vec.map[ast.field, @ast.expr](f, fields);
 }
 
-fn plain_ann() -> ast.ann {
-  ret ast.ann_type(middle.ty.mk_nil(),
+fn plain_ann(@middle.ty.type_store tystore) -> ast.ann {
+  ret ast.ann_type(middle.ty.mk_nil(tystore),
                    none[vec[@middle.ty.t]], none[@ts_ann]);
 }