Move ast_map::map to LinearMap

25 files changed, 111 insertions, 113 deletions

diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index 675a7837173..490fa357bb5 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -1026,7 +1026,7 @@ fn encode_info_for_items(ecx: @EncodeContext, ebml_w: writer::Encoder,
             let ebml_w = copy ebml_w;
             |i, cx, v| {
                 visit::visit_item(i, cx, v);
-                match ecx.tcx.items.get(&i.id) {
+                match *ecx.tcx.items.get(&i.id) {
                     ast_map::node_item(_, pt) => {
                         encode_info_for_item(ecx, ebml_w, i,
                                              index, *pt);
@@ -1039,7 +1039,7 @@ fn encode_info_for_items(ecx: @EncodeContext, ebml_w: writer::Encoder,
             let ebml_w = copy ebml_w;
             |ni, cx, v| {
                 visit::visit_foreign_item(ni, cx, v);
-                match ecx.tcx.items.get(&ni.id) {
+                match *ecx.tcx.items.get(&ni.id) {
                     ast_map::node_foreign_item(_, abi, _, pt) => {
                         encode_info_for_foreign_item(ecx, ebml_w, ni,
                                                      index, /*bad*/copy *pt,
diff --git a/src/librustc/middle/check_const.rs b/src/librustc/middle/check_const.rs
index 5a5ba6918d7..f9212d1ff7b 100644
--- a/src/librustc/middle/check_const.rs
+++ b/src/librustc/middle/check_const.rs
@@ -240,7 +240,7 @@ pub fn check_item_recursion(sess: Session,
             match env.def_map.find(&e.id) {
               Some(&def_const(def_id)) => {
                 if ast_util::is_local(def_id) {
-                  match env.ast_map.get(&def_id.node) {
+                  match *env.ast_map.get(&def_id.node) {
                     ast_map::node_item(it, _) => {
                       (v.visit_item)(it, env, v);
                     }
diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs
index a6c954b3851..a25d873af41 100644
--- a/src/librustc/middle/const_eval.rs
+++ b/src/librustc/middle/const_eval.rs
@@ -182,7 +182,7 @@ pub fn lookup_const_by_id(tcx: ty::ctxt,
     if ast_util::is_local(def_id) {
         match tcx.items.find(&def_id.node) {
             None => None,
-            Some(ast_map::node_item(it, _)) => match it.node {
+            Some(&ast_map::node_item(it, _)) => match it.node {
                 item_const(_, const_expr) => Some(const_expr),
                 _ => None
             },
diff --git a/src/librustc/middle/privacy.rs b/src/librustc/middle/privacy.rs
index 4e349d1506d..50e8ed23446 100644
--- a/src/librustc/middle/privacy.rs
+++ b/src/librustc/middle/privacy.rs
@@ -113,8 +113,8 @@ pub fn check_crate(tcx: ty::ctxt,
             @fn(span: span, method_id: node_id) -> def_id =
             |span, method_id| {
         match tcx.items.find(&method_id) {
-            Some(node_method(_, impl_id, _)) => impl_id,
-            Some(node_trait_method(_, trait_id, _)) => trait_id,
+            Some(&node_method(_, impl_id, _)) => impl_id,
+            Some(&node_trait_method(_, trait_id, _)) => trait_id,
             Some(_) => {
                 tcx.sess.span_bug(span,
                                   fmt!("method was a %s?!",
@@ -148,7 +148,7 @@ pub fn check_crate(tcx: ty::ctxt,
                 }
 
                 match tcx.items.find(&container_id.node) {
-                    Some(node_item(item, _)) => {
+                    Some(&node_item(item, _)) => {
                         match item.node {
                             item_impl(_, None, _, _)
                                     if item.vis != public => {
@@ -170,10 +170,10 @@ pub fn check_crate(tcx: ty::ctxt,
         };
 
         match tcx.items.find(&method_id) {
-            Some(node_method(method, impl_id, _)) => {
+            Some(&node_method(method, impl_id, _)) => {
                 check(method.vis, impl_id)
             }
-            Some(node_trait_method(trait_method, trait_id, _)) => {
+            Some(&node_trait_method(trait_method, trait_id, _)) => {
                 match *trait_method {
                     required(_) => check(public, trait_id),
                     provided(method) => check(method.vis, trait_id),
@@ -200,16 +200,16 @@ pub fn check_crate(tcx: ty::ctxt,
         let mut f: &fn(node_id) -> bool = |_| false;
         f = |item_id| {
             match tcx.items.find(&item_id) {
-                Some(node_item(item, _)) => item.vis != public,
-                Some(node_foreign_item(_, _, vis, _)) => vis != public,
-                Some(node_method(method, impl_did, _)) => {
+                Some(&node_item(item, _)) => item.vis != public,
+                Some(&node_foreign_item(_, _, vis, _)) => vis != public,
+                Some(&node_method(method, impl_did, _)) => {
                     match method.vis {
                         private => true,
                         public => false,
                         inherited => f(impl_did.node)
                     }
                 }
-                Some(node_trait_method(_, trait_did, _)) => f(trait_did.node),
+                Some(&node_trait_method(_, trait_did, _)) => f(trait_did.node),
                 Some(_) => {
                     tcx.sess.span_bug(span,
                                       fmt!("local_item_is_private: item was \
@@ -332,7 +332,7 @@ pub fn check_crate(tcx: ty::ctxt,
             method_super(trait_id, method_num) => {
                 if trait_id.crate == local_crate {
                     match tcx.items.find(&trait_id.node) {
-                        Some(node_item(item, _)) => {
+                        Some(&node_item(item, _)) => {
                             match item.node {
                                 item_trait(_, _, ref methods) => {
                                     if method_num >= (*methods).len() {
diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs
index 680e9c7053d..fb05cf0b739 100644
--- a/src/librustc/middle/trans/base.rs
+++ b/src/librustc/middle/trans/base.rs
@@ -2065,7 +2065,7 @@ pub fn trans_enum_def(ccx: @CrateContext, enum_definition: ast::enum_def,
 
 pub fn trans_item(ccx: @CrateContext, item: ast::item) {
     let _icx = ccx.insn_ctxt("trans_item");
-    let path = match ccx.tcx.items.get(&item.id) {
+    let path = match *ccx.tcx.items.get(&item.id) {
         ast_map::node_item(_, p) => p,
         // tjc: ?
         _ => fail!(~"trans_item"),
@@ -2336,13 +2336,12 @@ pub fn fill_fn_pair(bcx: block, pair: ValueRef, llfn: ValueRef,
 }
 
 pub fn item_path(ccx: @CrateContext, i: @ast::item) -> path {
-    vec::append(
-        /*bad*/copy *match ccx.tcx.items.get(&i.id) {
-            ast_map::node_item(_, p) => p,
-                // separate map for paths?
-            _ => fail!(~"item_path")
-        },
-        ~[path_name(i.ident)])
+    let base = match *ccx.tcx.items.get(&i.id) {
+        ast_map::node_item(_, p) => p,
+            // separate map for paths?
+        _ => fail!(~"item_path")
+    };
+    vec::append(/*bad*/copy *base, ~[path_name(i.ident)])
 }
 
 /* If there's already a symbol for the dtor with <id> and substs <substs>,
@@ -2393,7 +2392,7 @@ pub fn get_item_val(ccx: @CrateContext, id: ast::node_id) -> ValueRef {
       None => {
 
         let mut exprt = false;
-        let val = match ccx.tcx.items.get(&id) {
+        let val = match *ccx.tcx.items.get(&id) {
           ast_map::node_item(i, pth) => {
             let my_path = vec::append(/*bad*/copy *pth,
                                       ~[path_name(i.ident)]);
diff --git a/src/librustc/middle/trans/callee.rs b/src/librustc/middle/trans/callee.rs
index dd882087d38..7ba0b706e43 100644
--- a/src/librustc/middle/trans/callee.rs
+++ b/src/librustc/middle/trans/callee.rs
@@ -268,7 +268,7 @@ pub fn trans_fn_ref_with_vtables(
             ccx.tcx.items.find(&def_id.node),
             || fmt!("local item should be in ast map"));
 
-        match map_node {
+        match *map_node {
             ast_map::node_foreign_item(_,
                                        ast::foreign_abi_rust_intrinsic,
                                        _,
diff --git a/src/librustc/middle/trans/consts.rs b/src/librustc/middle/trans/consts.rs
index a929a53a769..1362f97c08e 100644
--- a/src/librustc/middle/trans/consts.rs
+++ b/src/librustc/middle/trans/consts.rs
@@ -158,7 +158,7 @@ pub fn get_const_val(cx: @CrateContext, def_id: ast::def_id) -> ValueRef {
         if !ast_util::is_local(def_id) {
             def_id = inline::maybe_instantiate_inline(cx, def_id, true);
         }
-        match cx.tcx.items.get(&def_id.node) {
+        match *cx.tcx.items.get(&def_id.node) {
             ast_map::node_item(@ast::item {
                 node: ast::item_const(_, subexpr), _
             }, _) => {
diff --git a/src/librustc/middle/trans/debuginfo.rs b/src/librustc/middle/trans/debuginfo.rs
index 50c7017029b..45884c9c3b4 100644
--- a/src/librustc/middle/trans/debuginfo.rs
+++ b/src/librustc/middle/trans/debuginfo.rs
@@ -849,7 +849,7 @@ pub fn create_function(fcx: fn_ctxt) -> @Metadata<SubProgramMetadata> {
     let sp = fcx.span.get();
     debug!("%s", cx.sess.codemap.span_to_str(sp));
 
-    let (ident, ret_ty, id) = match cx.tcx.items.get(&fcx.id) {
+    let (ident, ret_ty, id) = match *cx.tcx.items.get(&fcx.id) {
       ast_map::node_item(item, _) => {
         match item.node {
           ast::item_fn(ref decl, _, _, _) => {
diff --git a/src/librustc/middle/trans/foreign.rs b/src/librustc/middle/trans/foreign.rs
index 05acdae1bb0..08f86bfb2df 100644
--- a/src/librustc/middle/trans/foreign.rs
+++ b/src/librustc/middle/trans/foreign.rs
@@ -567,7 +567,7 @@ pub fn trans_intrinsic(ccx: @CrateContext,
             let tp_sz = machine::llbitsize_of_real(ccx, lltp_ty),
             out_sz = machine::llbitsize_of_real(ccx, llout_ty);
           if tp_sz != out_sz {
-              let sp = match ccx.tcx.items.get(&ref_id.get()) {
+              let sp = match *ccx.tcx.items.get(&ref_id.get()) {
                   ast_map::node_expr(e) => e.span,
                   _ => fail!(~"reinterpret_cast or forget has non-expr arg")
               };
@@ -1082,7 +1082,7 @@ pub fn register_foreign_fn(ccx: @CrateContext,
 fn abi_of_foreign_fn(ccx: @CrateContext, i: @ast::foreign_item)
     -> ast::foreign_abi {
     match attr::first_attr_value_str_by_name(i.attrs, ~"abi") {
-      None => match ccx.tcx.items.get(&i.id) {
+      None => match *ccx.tcx.items.get(&i.id) {
         ast_map::node_foreign_item(_, abi, _, _) => abi,
         // ??
         _ => fail!(~"abi_of_foreign_fn: not foreign")
diff --git a/src/librustc/middle/trans/meth.rs b/src/librustc/middle/trans/meth.rs
index 66a28a03bd8..1f348bc3e24 100644
--- a/src/librustc/middle/trans/meth.rs
+++ b/src/librustc/middle/trans/meth.rs
@@ -306,7 +306,7 @@ pub fn trans_static_method_callee(bcx: block,
     };
 
     let mname = if method_id.crate == ast::local_crate {
-        match bcx.tcx().items.get(&method_id.node) {
+        match *bcx.tcx().items.get(&method_id.node) {
             ast_map::node_trait_method(trait_method, _, _) => {
                 ast_util::trait_method_to_ty_method(trait_method).ident
             }
@@ -361,7 +361,7 @@ pub fn method_from_methods(ms: &[@ast::method], name: ast::ident)
 pub fn method_with_name(ccx: @CrateContext, impl_id: ast::def_id,
                         name: ast::ident) -> ast::def_id {
     if impl_id.crate == ast::local_crate {
-        match ccx.tcx.items.get(&impl_id.node) {
+        match *ccx.tcx.items.get(&impl_id.node) {
           ast_map::node_item(@ast::item {
                 node: ast::item_impl(_, _, _, ref ms),
                 _
@@ -378,7 +378,7 @@ pub fn method_with_name(ccx: @CrateContext, impl_id: ast::def_id,
 pub fn method_with_name_or_default(ccx: @CrateContext, impl_id: ast::def_id,
                                    name: ast::ident) -> ast::def_id {
     if impl_id.crate == ast::local_crate {
-        match ccx.tcx.items.get(&impl_id.node) {
+        match *ccx.tcx.items.get(&impl_id.node) {
           ast_map::node_item(@ast::item {
                 node: ast::item_impl(_, _, _, ref ms), _
           }, _) => {
@@ -414,7 +414,7 @@ pub fn method_ty_param_count(ccx: @CrateContext, m_id: ast::def_id,
     debug!("method_ty_param_count: m_id: %?, i_id: %?", m_id, i_id);
     if m_id.crate == ast::local_crate {
         match ccx.tcx.items.find(&m_id.node) {
-            Some(ast_map::node_method(m, _, _)) => m.generics.ty_params.len(),
+            Some(&ast_map::node_method(m, _, _)) => m.generics.ty_params.len(),
             None => {
                 match ccx.tcx.provided_method_sources.find(&m_id) {
                     Some(source) => {
@@ -424,7 +424,7 @@ pub fn method_ty_param_count(ccx: @CrateContext, m_id: ast::def_id,
                     None => fail!()
                 }
             }
-            Some(ast_map::node_trait_method(@ast::provided(@ref m),
+            Some(&ast_map::node_trait_method(@ast::provided(@ref m),
                                             _, _)) => {
                 m.generics.ty_params.len()
             }
diff --git a/src/librustc/middle/trans/monomorphize.rs b/src/librustc/middle/trans/monomorphize.rs
index 77e521b4af0..659b3f6c7ac 100644
--- a/src/librustc/middle/trans/monomorphize.rs
+++ b/src/librustc/middle/trans/monomorphize.rs
@@ -93,7 +93,7 @@ pub fn monomorphic_fn(ccx: @CrateContext,
         (may have attempted to monomorphize an item defined in a different \
         crate?)", fn_id));
     // Get the path so that we can create a symbol
-    let (pt, name, span) = match map_node {
+    let (pt, name, span) = match *map_node {
       ast_map::node_item(i, pt) => (pt, i.ident, i.span),
       ast_map::node_variant(ref v, enm, pt) => (pt, (*v).node.name, enm.span),
       ast_map::node_method(m, _, pt) => (pt, m.ident, m.span),
@@ -172,7 +172,7 @@ pub fn monomorphic_fn(ccx: @CrateContext,
         self_ty: impl_ty_opt
     });
 
-    let lldecl = match map_node {
+    let lldecl = match *map_node {
       ast_map::node_item(i@@ast::item {
                 // XXX: Bad copy.
                 node: ast::item_fn(ref decl, _, _, ref body),
diff --git a/src/librustc/middle/trans/reachable.rs b/src/librustc/middle/trans/reachable.rs
index 026a27dce2c..4ac3ac0555f 100644
--- a/src/librustc/middle/trans/reachable.rs
+++ b/src/librustc/middle/trans/reachable.rs
@@ -71,20 +71,17 @@ fn traverse_exports(cx: ctx, mod_id: node_id) -> bool {
 
 fn traverse_def_id(cx: ctx, did: def_id) {
     if did.crate != local_crate { return; }
-    let n = match cx.tcx.items.find(&did.node) {
-        None => return, // This can happen for self, for example
-        Some(ref n) => (/*bad*/copy *n)
-    };
-    match n {
-      ast_map::node_item(item, _) => traverse_public_item(cx, item),
-      ast_map::node_method(_, impl_id, _) => traverse_def_id(cx, impl_id),
-      ast_map::node_foreign_item(item, _, _, _) => {
-        cx.rmap.insert(item.id);
-      }
-      ast_map::node_variant(ref v, _, _) => {
-        cx.rmap.insert(v.node.id);
-      }
-      _ => ()
+    match cx.tcx.items.find(&did.node) {
+        None => (), // This can happen for self, for example
+        Some(&ast_map::node_item(item, _)) => traverse_public_item(cx, item),
+        Some(&ast_map::node_method(_, impl_id, _)) => traverse_def_id(cx, impl_id),
+        Some(&ast_map::node_foreign_item(item, _, _, _)) => {
+            cx.rmap.insert(item.id);
+        }
+        Some(&ast_map::node_variant(ref v, _, _)) => {
+            cx.rmap.insert(v.node.id);
+        }
+        _ => ()
     }
 }
 
diff --git a/src/librustc/middle/trans/type_use.rs b/src/librustc/middle/trans/type_use.rs
index 62cde5999e8..e19afb0d507 100644
--- a/src/librustc/middle/trans/type_use.rs
+++ b/src/librustc/middle/trans/type_use.rs
@@ -98,7 +98,7 @@ pub fn type_uses_for(ccx: @CrateContext, fn_id: def_id, n_tps: uint)
         return uses;
     }
     let map_node = match ccx.tcx.items.find(&fn_id_loc.node) {
-        Some(ref x) => (/*bad*/copy *x),
+        Some(x) => (/*bad*/copy *x),
         None    => ccx.sess.bug(fmt!("type_uses_for: unbound item ID %?",
                                      fn_id_loc))
     };
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 74146e56da2..fcbf34dca90 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -3538,7 +3538,7 @@ pub fn store_trait_methods(cx: ctxt, id: ast::node_id, ms: @~[method]) {
 pub fn provided_trait_methods(cx: ctxt, id: ast::def_id) -> ~[ast::ident] {
     if is_local(id) {
         match cx.items.find(&id.node) {
-            Some(ast_map::node_item(@ast::item {
+            Some(&ast_map::node_item(@ast::item {
                         node: item_trait(_, _, ref ms),
                         _
                     }, _)) =>
@@ -3627,7 +3627,7 @@ pub fn impl_traits(cx: ctxt, id: ast::def_id, store: TraitStore) -> ~[t] {
     if id.crate == ast::local_crate {
         debug!("(impl_traits) searching for trait impl %?", id);
         match cx.items.find(&id.node) {
-           Some(ast_map::node_item(@ast::item {
+           Some(&ast_map::node_item(@ast::item {
                         node: ast::item_impl(_, opt_trait, _, _),
                         _},
                     _)) => {
@@ -3663,7 +3663,7 @@ fn struct_ctor_id(cx: ctxt, struct_did: ast::def_id) -> Option<ast::def_id> {
     }
 
     match cx.items.find(&struct_did.node) {
-        Some(ast_map::node_item(item, _)) => {
+        Some(&ast_map::node_item(item, _)) => {
             match item.node {
                 ast::item_struct(struct_def, _) => {
                     struct_def.ctor_id.map(|ctor_id|
@@ -3735,7 +3735,7 @@ pub fn ty_dtor(cx: ctxt, struct_id: def_id) -> DtorKind {
 
     if is_local(struct_id) {
        match cx.items.find(&struct_id.node) {
-           Some(ast_map::node_item(@ast::item {
+           Some(&ast_map::node_item(@ast::item {
                node: ast::item_struct(@ast::struct_def { dtor: Some(ref dtor),
                                                          _ },
                                       _),
@@ -3762,8 +3762,12 @@ pub fn item_path(cx: ctxt, id: ast::def_id) -> ast_map::path {
     if id.crate != ast::local_crate {
         csearch::get_item_path(cx, id)
     } else {
-        let node = cx.items.get(&id.node);
-        match node {
+        // FIXME (#5521): uncomment this code and don't have a catch-all at the
+        //                end of the match statement. Favor explicitly listing
+        //                each variant.
+        // let node = cx.items.get(&id.node);
+        // match *node {
+        match *cx.items.get(&id.node) {
           ast_map::node_item(item, path) => {
             let item_elt = match item.node {
               item_mod(_) | item_foreign_mod(_) => {
@@ -3805,9 +3809,7 @@ pub fn item_path(cx: ctxt, id: ast::def_id) -> ast_map::path {
             vec::append_one(/*bad*/copy *path, ast_map::path_name(item.ident))
           }
 
-          ast_map::node_stmt(*) | ast_map::node_expr(*) |
-          ast_map::node_arg(*) | ast_map::node_local(*) |
-          ast_map::node_block(*) => {
+          ref node => {
             cx.sess.bug(fmt!("cannot find item_path for node %?", node));
           }
         }
@@ -3839,7 +3841,7 @@ pub fn enum_variants(cx: ctxt, id: ast::def_id) -> @~[VariantInfo] {
           call eval_const_expr, it should never get called twice for the same
           expr, since check_enum_variants also updates the enum_var_cache
          */
-        match cx.items.get(&id.node) {
+        match *cx.items.get(&id.node) {
           ast_map::node_item(@ast::item {
                     node: ast::item_enum(ref enum_definition, _),
                     _
@@ -3955,7 +3957,7 @@ pub fn lookup_field_type(tcx: ctxt,
 pub fn lookup_struct_fields(cx: ctxt, did: ast::def_id) -> ~[field_ty] {
   if did.crate == ast::local_crate {
     match cx.items.find(&did.node) {
-       Some(ast_map::node_item(i,_)) => {
+       Some(&ast_map::node_item(i,_)) => {
          match i.node {
             ast::item_struct(struct_def, _) => {
                struct_field_tys(struct_def.fields)
@@ -3963,7 +3965,7 @@ pub fn lookup_struct_fields(cx: ctxt, did: ast::def_id) -> ~[field_ty] {
             _ => cx.sess.bug(~"struct ID bound to non-struct")
          }
        }
-       Some(ast_map::node_variant(ref variant, _, _)) => {
+       Some(&ast_map::node_variant(ref variant, _, _)) => {
           match (*variant).node.kind {
             ast::struct_variant_kind(struct_def) => {
               struct_field_tys(struct_def.fields)
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index 3c436ffdf87..fcaf1c08342 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -1257,7 +1257,7 @@ pub impl<'self> LookupContext<'self> {
     fn report_static_candidate(&self, idx: uint, did: def_id) {
         let span = if did.crate == ast::local_crate {
             match self.tcx().items.find(&did.node) {
-              Some(ast_map::node_method(m, _, _)) => m.span,
+              Some(&ast_map::node_method(m, _, _)) => m.span,
               _ => fail!(fmt!("report_static_candidate: bad item %?", did))
             }
         } else {
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 3af23bb20ac..005b5377b62 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -1066,7 +1066,7 @@ pub fn impl_self_ty(vcx: &VtableContext,
         let region_param = tcx.region_paramd_items.find(&did.node).
                                map_consume(|x| *x);
         match tcx.items.find(&did.node) {
-          Some(ast_map::node_item(@ast::item {
+          Some(&ast_map::node_item(@ast::item {
                   node: ast::item_impl(ref ts, _, st, _),
                   _
               }, _)) => {
@@ -1074,7 +1074,7 @@ pub fn impl_self_ty(vcx: &VtableContext,
              region_param,
              vcx.ccx.to_ty(&rscope::type_rscope(region_param), st))
           }
-          Some(ast_map::node_item(@ast::item {
+          Some(&ast_map::node_item(@ast::item {
                   node: ast::item_struct(_, ref ts),
                   id: class_id,
                   _
@@ -1872,7 +1872,7 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
                 tcx.region_paramd_items.find(&class_id.node).
                     map_consume(|x| *x);
             match tcx.items.find(&class_id.node) {
-                Some(ast_map::node_item(@ast::item {
+                Some(&ast_map::node_item(@ast::item {
                         node: ast::item_struct(_, ref generics),
                         _
                     }, _)) => {
@@ -1960,7 +1960,7 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
             region_parameterized =
                 tcx.region_paramd_items.find(&enum_id.node).map_consume(|x| *x);
             match tcx.items.find(&enum_id.node) {
-                Some(ast_map::node_item(@ast::item {
+                Some(&ast_map::node_item(@ast::item {
                         node: ast::item_enum(_, ref generics),
                         _
                     }, _)) => {
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index e1d22f4e13d..7e97edf8f8a 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -801,7 +801,7 @@ pub impl CoherenceChecker {
     fn span_of_impl(&self, implementation: @Impl) -> span {
         fail_unless!(implementation.did.crate == local_crate);
         match self.crate_context.tcx.items.find(&implementation.did.node) {
-            Some(node_item(item, _)) => {
+            Some(&node_item(item, _)) => {
                 return item.span;
             }
             _ => {
@@ -1003,7 +1003,7 @@ pub impl CoherenceChecker {
                     // Destructors only work on nominal types.
                     if impl_info.did.crate == ast::local_crate {
                         match tcx.items.find(&impl_info.did.node) {
-                            Some(ast_map::node_item(@ref item, _)) => {
+                            Some(&ast_map::node_item(@ref item, _)) => {
                                 tcx.sess.span_err((*item).span,
                                                   ~"the Drop trait may only \
                                                     be implemented on \
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index cc40a65ff2c..a1fcf102988 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -137,10 +137,10 @@ impl AstConv for CrateCtxt {
             csearch::get_type(self.tcx, id)
         } else {
             match self.tcx.items.find(&id.node) {
-              Some(ast_map::node_item(item, _)) => {
+              Some(&ast_map::node_item(item, _)) => {
                 ty_of_item(self, item)
               }
-              Some(ast_map::node_foreign_item(foreign_item, _, _, _)) => {
+              Some(&ast_map::node_foreign_item(foreign_item, _, _, _)) => {
                 ty_of_foreign_item(self, foreign_item)
               }
               ref x => {
@@ -281,7 +281,7 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt,
 
     let tcx = ccx.tcx;
     let region_paramd = tcx.region_paramd_items.find(&id).map_consume(|x| *x);
-    match tcx.items.get(&id) {
+    match *tcx.items.get(&id) {
       ast_map::node_item(@ast::item {
                 node: ast::item_trait(ref generics, _, ref ms),
                 _
@@ -516,7 +516,7 @@ pub fn check_methods_against_trait(ccx: &CrateCtxt,
         // the methods within the trait with bogus results. (See issue #3903.)
 
         match tcx.items.find(&did.node) {
-            Some(ast_map::node_item(item, _)) => {
+            Some(&ast_map::node_item(item, _)) => {
                 let tpt = ty_of_item(ccx, item);
                 ensure_trait_methods(ccx, did.node, tpt.ty);
             }
diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs
index b783a099e16..77022b80feb 100644
--- a/src/librustc/middle/typeck/mod.rs
+++ b/src/librustc/middle/typeck/mod.rs
@@ -291,7 +291,7 @@ fn check_main_fn_ty(ccx: @mut CrateCtxt,
     match ty::get(main_t).sty {
         ty::ty_bare_fn(ref fn_ty) => {
             match tcx.items.find(&main_id) {
-                Some(ast_map::node_item(it,_)) => {
+                Some(&ast_map::node_item(it,_)) => {
                     match it.node {
                         ast::item_fn(_, _, ref ps, _)
                         if ps.is_parameterized() => {
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index eb63d675d80..bf2a35dbf7c 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -64,10 +64,10 @@ pub fn explain_region_and_span(cx: ctxt, region: ty::Region)
     return match region {
       re_scope(node_id) => {
         match cx.items.find(&node_id) {
-          Some(ast_map::node_block(ref blk)) => {
+          Some(&ast_map::node_block(ref blk)) => {
             explain_span(cx, "block", blk.span)
           }
-          Some(ast_map::node_expr(expr)) => {
+          Some(&ast_map::node_expr(expr)) => {
             match expr.node {
               ast::expr_call(*) => explain_span(cx, "call", expr.span),
               ast::expr_method_call(*) => {
@@ -77,10 +77,10 @@ pub fn explain_region_and_span(cx: ctxt, region: ty::Region)
               _ => explain_span(cx, "expression", expr.span)
             }
           }
-          Some(ast_map::node_stmt(stmt)) => {
+          Some(&ast_map::node_stmt(stmt)) => {
               explain_span(cx, "statement", stmt.span)
           }
-          Some(ast_map::node_item(it, _)) if (match it.node {
+          Some(&ast_map::node_item(it, _)) if (match it.node {
                 ast::item_fn(*) => true, _ => false}) => {
               explain_span(cx, "function body", it.span)
           }
@@ -102,7 +102,7 @@ pub fn explain_region_and_span(cx: ctxt, region: ty::Region)
         };
 
         match cx.items.find(&id) {
-          Some(ast_map::node_block(ref blk)) => {
+          Some(&ast_map::node_block(ref blk)) => {
             let (msg, opt_span) = explain_span(cx, "block", blk.span);
             (fmt!("%s %s", prefix, msg), opt_span)
           }
@@ -152,11 +152,11 @@ pub fn bound_region_to_str_space(cx: ctxt,
 
 pub fn re_scope_id_to_str(cx: ctxt, node_id: ast::node_id) -> ~str {
     match cx.items.find(&node_id) {
-      Some(ast_map::node_block(ref blk)) => {
+      Some(&ast_map::node_block(ref blk)) => {
         fmt!("<block at %s>",
              cx.sess.codemap.span_to_str(blk.span))
       }
-      Some(ast_map::node_expr(expr)) => {
+      Some(&ast_map::node_expr(expr)) => {
         match expr.node {
           ast::expr_call(*) => {
             fmt!("<call at %s>",
diff --git a/src/librustdoc/attr_pass.rs b/src/librustdoc/attr_pass.rs
index 0bf2f50e63f..30c8ff6964e 100644
--- a/src/librustdoc/attr_pass.rs
+++ b/src/librustdoc/attr_pass.rs
@@ -114,7 +114,7 @@ fn parse_item_attrs<T:Owned>(
     id: doc::AstId,
     parse_attrs: ~fn(a: ~[ast::attribute]) -> T) -> T {
     do astsrv::exec(srv) |ctxt| {
-        let attrs = match ctxt.ast_map.get(&id) {
+        let attrs = match *ctxt.ast_map.get(&id) {
           ast_map::node_item(item, _) => copy item.attrs,
           ast_map::node_foreign_item(item, _, _, _) => copy item.attrs,
           _ => fail!(~"parse_item_attrs: not an item")
@@ -162,7 +162,7 @@ fn fold_enum(
             let desc = {
                 let variant = copy variant;
                 do astsrv::exec(srv.clone()) |ctxt| {
-                    match ctxt.ast_map.get(&doc_id) {
+                    match *ctxt.ast_map.get(&doc_id) {
                         ast_map::node_item(@ast::item {
                             node: ast::item_enum(ref enum_definition, _), _
                         }, _) => {
@@ -226,7 +226,7 @@ fn merge_method_attrs(
 
     // Create an assoc list from method name to attributes
     let attrs: ~[(~str, Option<~str>)] = do astsrv::exec(srv) |ctxt| {
-        match ctxt.ast_map.get(&item_id) {
+        match *ctxt.ast_map.get(&item_id) {
           ast_map::node_item(@ast::item {
             node: ast::item_trait(_, _, ref methods), _
           }, _) => {
diff --git a/src/librustdoc/prune_hidden_pass.rs b/src/librustdoc/prune_hidden_pass.rs
index bbd975dd55a..3c069e59e7a 100644
--- a/src/librustdoc/prune_hidden_pass.rs
+++ b/src/librustdoc/prune_hidden_pass.rs
@@ -53,7 +53,7 @@ fn is_hidden(srv: astsrv::Srv, doc: doc::ItemDoc) -> bool {
 
     let id = doc.id;
     do astsrv::exec(srv) |ctxt| {
-        let attrs = match ctxt.ast_map.get(&id) {
+        let attrs = match *ctxt.ast_map.get(&id) {
           ast_map::node_item(item, _) => copy item.attrs,
           _ => ~[]
         };
diff --git a/src/librustdoc/prune_private_pass.rs b/src/librustdoc/prune_private_pass.rs
index b6aebf8b14f..e6f21b5df54 100644
--- a/src/librustdoc/prune_private_pass.rs
+++ b/src/librustdoc/prune_private_pass.rs
@@ -57,7 +57,7 @@ fn fold_impl(
     let doc = fold::default_seq_fold_impl(fold, doc);
 
     do astsrv::exec(fold.ctxt.clone()) |ctxt| {
-        match ctxt.ast_map.get(&doc.item.id) {
+        match *ctxt.ast_map.get(&doc.item.id) {
             ast_map::node_item(item, _) => {
                 match item.node {
                     ast::item_impl(_, None, _, ref methods) => {
@@ -136,7 +136,7 @@ fn is_visible(srv: astsrv::Srv, doc: doc::ItemDoc) -> bool {
     let id = doc.id;
 
     do astsrv::exec(srv) |ctxt| {
-        match ctxt.ast_map.get(&id) {
+        match *ctxt.ast_map.get(&id) {
             ast_map::node_item(item, _) => {
                 match &item.node {
                     &ast::item_impl(*) => {
diff --git a/src/librustdoc/tystr_pass.rs b/src/librustdoc/tystr_pass.rs
index 50ec41e80bc..229a0a3ff0f 100644
--- a/src/librustdoc/tystr_pass.rs
+++ b/src/librustdoc/tystr_pass.rs
@@ -66,7 +66,7 @@ fn fold_fn(
 
 fn get_fn_sig(srv: astsrv::Srv, fn_id: doc::AstId) -> Option<~str> {
     do astsrv::exec(srv) |ctxt| {
-        match ctxt.ast_map.get(&fn_id) {
+        match *ctxt.ast_map.get(&fn_id) {
           ast_map::node_item(@ast::item {
             ident: ident,
             node: ast::item_fn(ref decl, purity, ref tys, _), _
@@ -106,7 +106,7 @@ fn fold_const(
         sig: Some({
             let doc = copy doc;
             do astsrv::exec(srv) |ctxt| {
-                match ctxt.ast_map.get(&doc.id()) {
+                match *ctxt.ast_map.get(&doc.id()) {
                     ast_map::node_item(@ast::item {
                         node: ast::item_const(ty, _), _
                     }, _) => {
@@ -137,7 +137,7 @@ fn fold_enum(
             let sig = {
                 let variant = copy *variant;
                 do astsrv::exec(srv.clone()) |ctxt| {
-                    match ctxt.ast_map.get(&doc_id) {
+                    match *ctxt.ast_map.get(&doc_id) {
                         ast_map::node_item(@ast::item {
                             node: ast::item_enum(ref enum_definition, _), _
                         }, _) => {
@@ -199,7 +199,7 @@ fn get_method_sig(
     method_name: ~str
 ) -> Option<~str> {
     do astsrv::exec(srv) |ctxt| {
-        match ctxt.ast_map.get(&item_id) {
+        match *ctxt.ast_map.get(&item_id) {
           ast_map::node_item(@ast::item {
             node: ast::item_trait(_, _, ref methods), _
           }, _) => {
@@ -277,7 +277,7 @@ fn fold_impl(
     let (bounds, trait_types, self_ty) = {
         let doc = copy doc;
         do astsrv::exec(srv) |ctxt| {
-            match ctxt.ast_map.get(&doc.id()) {
+            match *ctxt.ast_map.get(&doc.id()) {
                 ast_map::node_item(@ast::item {
                     node: ast::item_impl(ref generics, opt_trait_type, self_ty, _), _
                 }, _) => {
@@ -347,7 +347,7 @@ fn fold_type(
         sig: {
             let doc = copy doc;
             do astsrv::exec(srv) |ctxt| {
-                match ctxt.ast_map.get(&doc.id()) {
+                match *ctxt.ast_map.get(&doc.id()) {
                     ast_map::node_item(@ast::item {
                         ident: ident,
                         node: ast::item_ty(ty, ref params), _
@@ -385,7 +385,7 @@ fn fold_struct(
         sig: {
             let doc = copy doc;
             do astsrv::exec(srv) |ctxt| {
-                match ctxt.ast_map.get(&doc.id()) {
+                match *ctxt.ast_map.get(&doc.id()) {
                     ast_map::node_item(item, _) => {
                         let item = strip_struct_extra_stuff(item);
                         Some(pprust::item_to_str(item,
diff --git a/src/libsyntax/ast_map.rs b/src/libsyntax/ast_map.rs
index 8989bb88cd7..eef14ac8b7a 100644
--- a/src/libsyntax/ast_map.rs
+++ b/src/libsyntax/ast_map.rs
@@ -23,9 +23,9 @@ use print::pprust;
 use visit;
 
 use core::cmp;
+use core::hashmap::linear::LinearMap;
 use core::str;
 use core::vec;
-use std;
 
 pub enum path_elt {
     path_mod(ident),
@@ -104,10 +104,10 @@ pub enum ast_node {
     node_struct_ctor(@struct_def, @item, @path),
 }
 
-pub type map = std::oldmap::HashMap<node_id, ast_node>;
+pub type map = @mut LinearMap<node_id, ast_node>;
 
 pub struct Ctx {
-    map: @map,
+    map: map,
     path: path,
     local_id: uint,
     diag: @span_handler,
@@ -134,13 +134,13 @@ pub fn mk_ast_map_visitor() -> vt {
 
 pub fn map_crate(diag: @span_handler, c: crate) -> map {
     let cx = @mut Ctx {
-        map: @std::oldmap::HashMap(),
+        map: @mut LinearMap::new(),
         path: ~[],
         local_id: 0u,
         diag: diag,
     };
     visit::visit_crate(c, cx, mk_ast_map_visitor());
-    *cx.map
+    cx.map
 }
 
 // Used for items loaded from external crate that are being inlined into this
@@ -157,7 +157,7 @@ pub fn map_decoded_item(diag: @span_handler,
     // even if we did I think it only needs an ordering between local
     // variables that are simultaneously in scope).
     let cx = @mut Ctx {
-        map: @map,
+        map: map,
         path: copy path,
         local_id: 0,
         diag: diag,
@@ -374,7 +374,7 @@ pub fn node_id_to_str(map: map, id: node_id, itr: @ident_interner) -> ~str {
       None => {
         fmt!("unknown node (id=%d)", id)
       }
-      Some(node_item(item, path)) => {
+      Some(&node_item(item, path)) => {
         let path_str = path_ident_to_str(*path, item.ident, itr);
         let item_str = match item.node {
           item_const(*) => ~"const",
@@ -390,43 +390,43 @@ pub fn node_id_to_str(map: map, id: node_id, itr: @ident_interner) -> ~str {
         };
         fmt!("%s %s (id=%?)", item_str, path_str, id)
       }
-      Some(node_foreign_item(item, abi, _, path)) => {
+      Some(&node_foreign_item(item, abi, _, path)) => {
         fmt!("foreign item %s with abi %? (id=%?)",
              path_ident_to_str(*path, item.ident, itr), abi, id)
       }
-      Some(node_method(m, _, path)) => {
+      Some(&node_method(m, _, path)) => {
         fmt!("method %s in %s (id=%?)",
              *itr.get(m.ident), path_to_str(*path, itr), id)
       }
-      Some(node_trait_method(ref tm, _, path)) => {
+      Some(&node_trait_method(ref tm, _, path)) => {
         let m = ast_util::trait_method_to_ty_method(&**tm);
         fmt!("method %s in %s (id=%?)",
              *itr.get(m.ident), path_to_str(*path, itr), id)
       }
-      Some(node_variant(ref variant, _, path)) => {
+      Some(&node_variant(ref variant, _, path)) => {
         fmt!("variant %s in %s (id=%?)",
              *itr.get(variant.node.name), path_to_str(*path, itr), id)
       }
-      Some(node_expr(expr)) => {
+      Some(&node_expr(expr)) => {
         fmt!("expr %s (id=%?)", pprust::expr_to_str(expr, itr), id)
       }
-      Some(node_stmt(stmt)) => {
+      Some(&node_stmt(stmt)) => {
         fmt!("stmt %s (id=%?)",
              pprust::stmt_to_str(*stmt, itr), id)
       }
-      Some(node_arg(_, _)) => { // add more info here
+      Some(&node_arg(_, _)) => { // add more info here
         fmt!("arg (id=%?)", id)
       }
-      Some(node_local(_)) => { // add more info here
+      Some(&node_local(_)) => { // add more info here
         fmt!("local (id=%?)", id)
       }
-      Some(node_dtor(*)) => { // add more info here
+      Some(&node_dtor(*)) => { // add more info here
         fmt!("node_dtor (id=%?)", id)
       }
-      Some(node_block(_)) => {
+      Some(&node_block(_)) => {
         fmt!("block")
       }
-      Some(node_struct_ctor(*)) => {
+      Some(&node_struct_ctor(*)) => {
         fmt!("struct_ctor")
       }
     }
@@ -436,7 +436,7 @@ pub fn node_item_query<Result>(items: map, id: node_id,
                                query: &fn(@item) -> Result,
                                +error_msg: ~str) -> Result {
     match items.find(&id) {
-        Some(node_item(it, _)) => query(it),
+        Some(&node_item(it, _)) => query(it),
         _ => fail!(error_msg)
     }
 }