auto merge of #11616 : huonw/rust/ast_map, r=pnkfelix

NodeIds are sequential integers starting at zero, so we can achieve some
memory savings by just storing the items all in a line in a vector.

The occupancy for typical crates seems to be 75-80%, so we're already
more efficient than a HashMap (maximum occupancy 75%), not even counting
the extra book-keeping that HashMap does.

25 files changed, 195 insertions, 217 deletions

diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs
index b015638435b..5271d6ceba6 100644
--- a/src/librustc/metadata/encoder.rs
+++ b/src/librustc/metadata/encoder.rs
@@ -496,9 +496,8 @@ fn encode_reexported_static_methods(ecx: &EncodeContext,
                                     ebml_w: &mut writer::Encoder,
                                     mod_path: &[ast_map::PathElem],
                                     exp: &middle::resolve::Export2) {
-    let items = ecx.tcx.items.borrow();
-    match items.get().find(&exp.def_id.node) {
-        Some(&ast_map::NodeItem(item, path)) => {
+    match ecx.tcx.items.find(exp.def_id.node) {
+        Some(ast_map::NodeItem(item, path)) => {
             let original_name = ecx.tcx.sess.str_of(item.ident);
 
             //
@@ -1347,8 +1346,7 @@ fn my_visit_item(i: &Item,
                  ebml_w: &mut writer::Encoder,
                  ecx_ptr: *int,
                  index: @RefCell<~[entry<i64>]>) {
-    let items = items.borrow();
-    match items.get().get_copy(&i.id) {
+    match items.get(i.id) {
         ast_map::NodeItem(_, pt) => {
             let mut ebml_w = unsafe {
                 ebml_w.unsafe_clone()
@@ -1366,8 +1364,7 @@ fn my_visit_foreign_item(ni: &ForeignItem,
                          ebml_w: &mut writer::Encoder,
                          ecx_ptr:*int,
                          index: @RefCell<~[entry<i64>]>) {
-    let items = items.borrow();
-    match items.get().get_copy(&ni.id) {
+    match items.get(ni.id) {
         ast_map::NodeForeignItem(_, abi, _, pt) => {
             debug!("writing foreign item {}::{}",
                    ast_map::path_to_str(
diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs
index a252a590141..74845878907 100644
--- a/src/librustc/middle/borrowck/mod.rs
+++ b/src/librustc/middle/borrowck/mod.rs
@@ -550,9 +550,8 @@ impl BorrowckCtxt {
             move_data::Declared => {}
 
             move_data::MoveExpr => {
-                let items = self.tcx.items.borrow();
-                let (expr_ty, expr_span) = match items.get().find(&move.id) {
-                    Some(&ast_map::NodeExpr(expr)) => {
+                let (expr_ty, expr_span) = match self.tcx.items.find(move.id) {
+                    Some(ast_map::NodeExpr(expr)) => {
                         (ty::expr_ty_adjusted(self.tcx, expr), expr.span)
                     }
                     r => self.tcx.sess.bug(format!("MoveExpr({:?}) maps to {:?}, not Expr",
@@ -578,9 +577,8 @@ impl BorrowckCtxt {
             }
 
             move_data::Captured => {
-                let items = self.tcx.items.borrow();
-                let (expr_ty, expr_span) = match items.get().find(&move.id) {
-                    Some(&ast_map::NodeExpr(expr)) => {
+                let (expr_ty, expr_span) = match self.tcx.items.find(move.id) {
+                    Some(ast_map::NodeExpr(expr)) => {
                         (ty::expr_ty_adjusted(self.tcx, expr), expr.span)
                     }
                     r => self.tcx.sess.bug(format!("Captured({:?}) maps to {:?}, not Expr",
@@ -768,9 +766,8 @@ impl BorrowckCtxt {
                                    out: &mut ~str) {
         match *loan_path {
             LpVar(id) => {
-                let items = self.tcx.items.borrow();
-                match items.get().find(&id) {
-                    Some(&ast_map::NodeLocal(ref ident, _)) => {
+                match self.tcx.items.find(id) {
+                    Some(ast_map::NodeLocal(ref ident, _)) => {
                         out.push_str(token::ident_to_str(ident));
                     }
                     r => {
diff --git a/src/librustc/middle/check_const.rs b/src/librustc/middle/check_const.rs
index e13f6f8c537..efa1bd5fd51 100644
--- a/src/librustc/middle/check_const.rs
+++ b/src/librustc/middle/check_const.rs
@@ -250,8 +250,7 @@ impl<'a> Visitor<()> for CheckItemRecursionVisitor<'a> {
                 match def_map.get().find(&e.id) {
                     Some(&DefStatic(def_id, _)) if
                             ast_util::is_local(def_id) => {
-                        let ast_map = self.ast_map.borrow();
-                        match ast_map.get().get_copy(&def_id.node) {
+                        match self.ast_map.get(def_id.node) {
                             ast_map::NodeItem(it, _) => {
                                 self.visit_item(it, ());
                             }
diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs
index 340c8d67ce3..770275f3f6a 100644
--- a/src/librustc/middle/const_eval.rs
+++ b/src/librustc/middle/const_eval.rs
@@ -108,10 +108,9 @@ pub fn lookup_variant_by_id(tcx: ty::ctxt,
 
     if ast_util::is_local(enum_def) {
         {
-            let items = tcx.items.borrow();
-            match items.get().find(&enum_def.node) {
+            match tcx.items.find(enum_def.node) {
                 None => None,
-                Some(&ast_map::NodeItem(it, _)) => match it.node {
+                Some(ast_map::NodeItem(it, _)) => match it.node {
                     ItemEnum(ast::EnumDef { variants: ref variants }, _) => {
                         variant_expr(*variants, variant_def.node)
                     }
@@ -161,10 +160,9 @@ pub fn lookup_const_by_id(tcx: ty::ctxt, def_id: ast::DefId)
                           -> Option<@Expr> {
     if ast_util::is_local(def_id) {
         {
-            let items = tcx.items.borrow();
-            match items.get().find(&def_id.node) {
+            match tcx.items.find(def_id.node) {
                 None => None,
-                Some(&ast_map::NodeItem(it, _)) => match it.node {
+                Some(ast_map::NodeItem(it, _)) => match it.node {
                     ItemStatic(_, ast::MutImmutable, const_expr) => {
                         Some(const_expr)
                     }
diff --git a/src/librustc/middle/dead.rs b/src/librustc/middle/dead.rs
index f6cb635d01e..746cc74d7f6 100644
--- a/src/librustc/middle/dead.rs
+++ b/src/librustc/middle/dead.rs
@@ -38,12 +38,11 @@ fn should_explore(tcx: ty::ctxt, def_id: ast::DefId) -> bool {
         return false;
     }
 
-    let items = tcx.items.borrow();
-    match items.get().find(&def_id.node) {
-        Some(&ast_map::NodeItem(..))
-        | Some(&ast_map::NodeMethod(..))
-        | Some(&ast_map::NodeForeignItem(..))
-        | Some(&ast_map::NodeTraitMethod(..)) => true,
+    match tcx.items.find(def_id.node) {
+        Some(ast_map::NodeItem(..))
+        | Some(ast_map::NodeMethod(..))
+        | Some(ast_map::NodeForeignItem(..))
+        | Some(ast_map::NodeTraitMethod(..)) => true,
         _ => false
     }
 }
@@ -136,9 +135,8 @@ impl MarkSymbolVisitor {
             }
             scanned.insert(id);
 
-            let items = self.tcx.items.borrow();
-            match items.get().find(&id) {
-                Some(node) => {
+            match self.tcx.items.find(id) {
+                Some(ref node) => {
                     self.live_symbols.insert(id);
                     self.visit_node(node);
                 }
diff --git a/src/librustc/middle/entry.rs b/src/librustc/middle/entry.rs
index d6e4ad64182..3938a786a39 100644
--- a/src/librustc/middle/entry.rs
+++ b/src/librustc/middle/entry.rs
@@ -75,9 +75,8 @@ fn find_item(item: &Item, ctxt: &mut EntryContext) {
         ItemFn(..) => {
             if item.ident.name == special_idents::main.name {
                 {
-                    let ast_map = ctxt.ast_map.borrow();
-                    match ast_map.get().find(&item.id) {
-                        Some(&ast_map::NodeItem(_, path)) => {
+                    match ctxt.ast_map.find(item.id) {
+                        Some(ast_map::NodeItem(_, path)) => {
                             if path.len() == 0 {
                                 // This is a top-level function so can be 'main'
                                 if ctxt.main_fn.is_none() {
diff --git a/src/librustc/middle/lint.rs b/src/librustc/middle/lint.rs
index 098e4154e17..07caf28b801 100644
--- a/src/librustc/middle/lint.rs
+++ b/src/librustc/middle/lint.rs
@@ -1330,8 +1330,7 @@ fn check_stability(cx: &Context, e: &ast::Expr) {
 
     let stability = if ast_util::is_local(id) {
         // this crate
-        let items = cx.tcx.items.borrow();
-        match items.get().find(&id.node) {
+        match cx.tcx.items.find(id.node) {
             Some(ast_node) => {
                 let s = ast_node.with_attrs(|attrs| {
                     attrs.map(|a| {
diff --git a/src/librustc/middle/privacy.rs b/src/librustc/middle/privacy.rs
index 4318fde9b3a..a430790a2af 100644
--- a/src/librustc/middle/privacy.rs
+++ b/src/librustc/middle/privacy.rs
@@ -431,8 +431,7 @@ impl<'a> PrivacyVisitor<'a> {
         let mut closest_private_id = did.node;
         loop {
             debug!("privacy - examining {}", self.nodestr(closest_private_id));
-            let items = self.tcx.items.borrow();
-            let vis = match items.get().find(&closest_private_id) {
+            let vis = match self.tcx.items.find(closest_private_id) {
                 // If this item is a method, then we know for sure that it's an
                 // actual method and not a static method. The reason for this is
                 // that these cases are only hit in the ExprMethodCall
@@ -449,22 +448,22 @@ impl<'a> PrivacyVisitor<'a> {
                 // invocation.
                 // FIXME(#10573) is this the right behavior? Why not consider
                 //               where the method was defined?
-                Some(&ast_map::NodeMethod(ref m, imp, _)) => {
+                Some(ast_map::NodeMethod(ref m, imp, _)) => {
                     match ty::impl_trait_ref(self.tcx, imp) {
                         Some(..) => return Allowable,
                         _ if m.vis == ast::Public => return Allowable,
                         _ => m.vis
                     }
                 }
-                Some(&ast_map::NodeTraitMethod(..)) => {
+                Some(ast_map::NodeTraitMethod(..)) => {
                     return Allowable;
                 }
 
                 // This is not a method call, extract the visibility as one
                 // would normally look at it
-                Some(&ast_map::NodeItem(it, _)) => it.vis,
-                Some(&ast_map::NodeForeignItem(_, _, v, _)) => v,
-                Some(&ast_map::NodeVariant(ref v, _, _)) => {
+                Some(ast_map::NodeItem(it, _)) => it.vis,
+                Some(ast_map::NodeForeignItem(_, _, v, _)) => v,
+                Some(ast_map::NodeVariant(ref v, _, _)) => {
                     // sadly enum variants still inherit visibility, so only
                     // break out of this is explicitly private
                     if v.node.vis == ast::Private { break }
@@ -538,9 +537,8 @@ impl<'a> PrivacyVisitor<'a> {
                     self.tcx.sess.span_err(span, format!("{} is inaccessible",
                                                          msg));
                 }
-                let items = self.tcx.items.borrow();
-                match items.get().find(&id) {
-                    Some(&ast_map::NodeItem(item, _)) => {
+                match self.tcx.items.find(id) {
+                    Some(ast_map::NodeItem(item, _)) => {
                         let desc = match item.node {
                             ast::ItemMod(..) => "module",
                             ast::ItemTrait(..) => "trait",
diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs
index b95901b8d78..6f8ad77e90b 100644
--- a/src/librustc/middle/reachable.rs
+++ b/src/librustc/middle/reachable.rs
@@ -66,9 +66,8 @@ fn method_might_be_inlined(tcx: ty::ctxt, method: &ast::Method,
     }
     if is_local(impl_src) {
         {
-            let items = tcx.items.borrow();
-            match items.get().find(&impl_src.node) {
-                Some(&ast_map::NodeItem(item, _)) => {
+            match tcx.items.find(impl_src.node) {
+                Some(ast_map::NodeItem(item, _)) => {
                     item_might_be_inlined(item)
                 }
                 Some(..) | None => {
@@ -213,21 +212,20 @@ impl ReachableContext {
         }
 
         let node_id = def_id.node;
-        let items = tcx.items.borrow();
-        match items.get().find(&node_id) {
-            Some(&ast_map::NodeItem(item, _)) => {
+        match tcx.items.find(node_id) {
+            Some(ast_map::NodeItem(item, _)) => {
                 match item.node {
                     ast::ItemFn(..) => item_might_be_inlined(item),
                     _ => false,
                 }
             }
-            Some(&ast_map::NodeTraitMethod(trait_method, _, _)) => {
+            Some(ast_map::NodeTraitMethod(trait_method, _, _)) => {
                 match *trait_method {
                     ast::Required(_) => false,
                     ast::Provided(_) => true,
                 }
             }
-            Some(&ast_map::NodeMethod(method, impl_did, _)) => {
+            Some(ast_map::NodeMethod(method, impl_did, _)) => {
                 if generics_require_inlining(&method.generics) ||
                         attributes_specify_inlining(method.attrs) {
                     true
@@ -235,8 +233,8 @@ impl ReachableContext {
                     // Check the impl. If the generics on the self type of the
                     // impl require inlining, this method does too.
                     assert!(impl_did.crate == ast::LOCAL_CRATE);
-                    match items.get().find(&impl_did.node) {
-                        Some(&ast_map::NodeItem(item, _)) => {
+                    match tcx.items.find(impl_did.node) {
+                        Some(ast_map::NodeItem(item, _)) => {
                             match item.node {
                                 ast::ItemImpl(ref generics, _, _, _) => {
                                     generics_require_inlining(generics)
@@ -294,9 +292,8 @@ impl ReachableContext {
             };
 
             scanned.insert(search_item);
-            let items = self.tcx.items.borrow();
-            match items.get().find(&search_item) {
-                Some(item) => self.propagate_node(item, search_item,
+            match self.tcx.items.find(search_item) {
+                Some(ref item) => self.propagate_node(item, search_item,
                                                   &mut visitor),
                 None if search_item == ast::CRATE_NODE_ID => {}
                 None => {
diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs
index ef40629946d..583a15b85c9 100644
--- a/src/librustc/middle/trans/base.rs
+++ b/src/librustc/middle/trans/base.rs
@@ -1731,8 +1731,7 @@ impl Visitor<()> for TransItemVisitor {
 pub fn trans_item(ccx: @CrateContext, item: &ast::Item) {
     let _icx = push_ctxt("trans_item");
     let path = {
-        let items = ccx.tcx.items.borrow();
-        match items.get().get_copy(&item.id) {
+        match ccx.tcx.items.get(item.id) {
             ast_map::NodeItem(_, p) => p,
             // tjc: ?
             _ => fail!("trans_item"),
@@ -2034,10 +2033,7 @@ pub fn get_item_val(ccx: @CrateContext, id: ast::NodeId) -> ValueRef {
         Some(v) => v,
         None => {
             let mut foreign = false;
-            let item = {
-                let items = ccx.tcx.items.borrow();
-                items.get().get_copy(&id)
-            };
+            let item = ccx.tcx.items.get(id);
             let val = match item {
                 ast_map::NodeItem(i, pth) => {
 
diff --git a/src/librustc/middle/trans/callee.rs b/src/librustc/middle/trans/callee.rs
index 27903e74e07..229a1b3662d 100644
--- a/src/librustc/middle/trans/callee.rs
+++ b/src/librustc/middle/trans/callee.rs
@@ -365,13 +365,12 @@ pub fn trans_fn_ref_with_vtables(
         must_monomorphise = true;
     } else if def_id.crate == ast::LOCAL_CRATE {
         {
-            let items = ccx.tcx.items.borrow();
             let map_node = session::expect(
                 ccx.sess,
-                items.get().find(&def_id.node),
+                ccx.tcx.items.find(def_id.node),
                 || format!("local item should be in ast map"));
 
-            match *map_node {
+            match map_node {
                 ast_map::NodeForeignItem(_, abis, _, _) => {
                     must_monomorphise = abis.is_intrinsic()
                 }
diff --git a/src/librustc/middle/trans/consts.rs b/src/librustc/middle/trans/consts.rs
index ce251a9ec06..d70f2ab7d99 100644
--- a/src/librustc/middle/trans/consts.rs
+++ b/src/librustc/middle/trans/consts.rs
@@ -166,10 +166,7 @@ pub fn get_const_val(cx: @CrateContext,
             def_id = inline::maybe_instantiate_inline(cx, def_id);
         }
 
-        let opt_item = {
-            let items = cx.tcx.items.borrow();
-            items.get().get_copy(&def_id.node)
-        };
+        let opt_item = cx.tcx.items.get(def_id.node);
 
         match opt_item {
             ast_map::NodeItem(item, _) => {
diff --git a/src/librustc/middle/trans/debuginfo.rs b/src/librustc/middle/trans/debuginfo.rs
index 88f38d9f4fd..d256dd7e9a3 100644
--- a/src/librustc/middle/trans/debuginfo.rs
+++ b/src/librustc/middle/trans/debuginfo.rs
@@ -322,10 +322,8 @@ pub fn create_captured_var_metadata(bcx: &Block,
 
     let cx = bcx.ccx();
 
-    let ast_item = {
-        let items = cx.tcx.items.borrow();
-        items.get().find_copy(&node_id)
-    };
+    let ast_item = cx.tcx.items.find(node_id);
+
     let variable_ident = match ast_item {
         None => {
             cx.sess.span_bug(span, "debuginfo::create_captured_var_metadata() - NodeId not found");
@@ -423,10 +421,7 @@ pub fn create_self_argument_metadata(bcx: &Block,
     }
 
     // Extract the span of the self argument from the method's AST
-    let fnitem = {
-        let items = bcx.ccx().tcx.items.borrow();
-        items.get().get_copy(&bcx.fcx.id)
-    };
+    let fnitem = bcx.ccx().tcx.items.get(bcx.fcx.id);
     let span = match fnitem {
         ast_map::NodeMethod(method, _, _) => {
             method.explicit_self.span
@@ -613,10 +608,8 @@ pub fn create_function_debug_context(cx: &CrateContext,
 
     let empty_generics = ast::Generics { lifetimes: opt_vec::Empty, ty_params: opt_vec::Empty };
 
-    let fnitem = {
-        let items = cx.tcx.items.borrow();
-        items.get().get_copy(&fn_ast_id)
-    };
+    let fnitem = cx.tcx.items.get(fn_ast_id);
+
     let (ident, fn_decl, generics, top_level_block, span, has_path) = match fnitem {
         ast_map::NodeItem(ref item, _) => {
             match item.node {
@@ -1098,8 +1091,7 @@ fn scope_metadata(fcx: &FunctionContext,
     match scope_map.get().find_copy(&node_id) {
         Some(scope_metadata) => scope_metadata,
         None => {
-            let items = fcx.ccx.tcx.items.borrow();
-            let node = items.get().get_copy(&node_id);
+            let node = fcx.ccx.tcx.items.get(node_id);
 
             fcx.ccx.sess.span_bug(span,
                 format!("debuginfo: Could not find scope info for node {:?}", node));
@@ -1419,9 +1411,8 @@ fn describe_enum_variant(cx: &CrateContext,
     // Find the source code location of the variant's definition
     let variant_definition_span = if variant_info.id.crate == ast::LOCAL_CRATE {
         {
-            let items = cx.tcx.items.borrow();
-            match items.get().find(&variant_info.id.node) {
-                Some(&ast_map::NodeVariant(ref variant, _, _)) => variant.span,
+            match cx.tcx.items.find(variant_info.id.node) {
+                Some(ast_map::NodeVariant(ref variant, _, _)) => variant.span,
                 ref node => {
                     cx.sess.span_warn(span,
                         format!("debuginfo::enum_metadata()::\
@@ -2300,9 +2291,8 @@ fn get_namespace_and_span_for_item(cx: &CrateContext,
     let containing_scope = namespace_for_item(cx, def_id, warning_span).scope;
     let definition_span = if def_id.crate == ast::LOCAL_CRATE {
         {
-            let items = cx.tcx.items.borrow();
-            let definition_span = match items.get().find(&def_id.node) {
-                Some(&ast_map::NodeItem(item, _)) => item.span,
+            let definition_span = match cx.tcx.items.find(def_id.node) {
+                Some(ast_map::NodeItem(item, _)) => item.span,
                 ref node => {
                     cx.sess.span_warn(warning_span,
                         format!("debuginfo::\
diff --git a/src/librustc/middle/trans/foreign.rs b/src/librustc/middle/trans/foreign.rs
index 083a1c6988d..2526d8e3fea 100644
--- a/src/librustc/middle/trans/foreign.rs
+++ b/src/librustc/middle/trans/foreign.rs
@@ -354,9 +354,8 @@ pub fn trans_foreign_mod(ccx: @CrateContext,
     for &foreign_item in foreign_mod.items.iter() {
         match foreign_item.node {
             ast::ForeignItemFn(..) => {
-                let items = ccx.tcx.items.borrow();
                 let (abis, mut path) =
-                    match items.get().get_copy(&foreign_item.id) {
+                    match ccx.tcx.items.get(foreign_item.id) {
                         ast_map::NodeForeignItem(_, abis, _, path) => {
                             (abis, (*path).clone())
                         }
diff --git a/src/librustc/middle/trans/intrinsic.rs b/src/librustc/middle/trans/intrinsic.rs
index 1fc749bb687..67505285630 100644
--- a/src/librustc/middle/trans/intrinsic.rs
+++ b/src/librustc/middle/trans/intrinsic.rs
@@ -337,8 +337,7 @@ pub fn trans_intrinsic(ccx: @CrateContext,
             let out_type_size = machine::llbitsize_of_real(ccx, llouttype);
             if in_type_size != out_type_size {
                 let sp = {
-                    let items = ccx.tcx.items.borrow();
-                    match items.get().get_copy(&ref_id.unwrap()) {
+                    match ccx.tcx.items.get(ref_id.unwrap()) {
                         ast_map::NodeExpr(e) => e.span,
                         _ => fail!("transmute has non-expr arg"),
                     }
diff --git a/src/librustc/middle/trans/meth.rs b/src/librustc/middle/trans/meth.rs
index 85b9e16e5cc..3badfc38df6 100644
--- a/src/librustc/middle/trans/meth.rs
+++ b/src/librustc/middle/trans/meth.rs
@@ -238,8 +238,7 @@ pub fn trans_static_method_callee(bcx: &Block,
 
     let mname = if method_id.crate == ast::LOCAL_CRATE {
         {
-            let items = bcx.tcx().items.borrow();
-            match items.get().get_copy(&method_id.node) {
+            match bcx.tcx().items.get(method_id.node) {
                 ast_map::NodeTraitMethod(trait_method, _, _) => {
                     ast_util::trait_method_to_ty_method(trait_method).ident
                 }
diff --git a/src/librustc/middle/trans/monomorphize.rs b/src/librustc/middle/trans/monomorphize.rs
index a128a953eac..5e3e3236394 100644
--- a/src/librustc/middle/trans/monomorphize.rs
+++ b/src/librustc/middle/trans/monomorphize.rs
@@ -95,10 +95,9 @@ pub fn monomorphic_fn(ccx: @CrateContext,
     let mut is_static_provided = None;
 
     let map_node = {
-        let items = ccx.tcx.items.borrow();
         session::expect(
             ccx.sess,
-            items.get().find_copy(&fn_id.node),
+            ccx.tcx.items.find(fn_id.node),
             || format!("While monomorphizing {:?}, couldn't find it in the \
                         item map (may have attempted to monomorphize an item \
                         defined in a different crate?)", fn_id))
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 538a3c89bef..815aa4ba38e 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -3557,9 +3557,8 @@ pub fn provided_source(cx: ctxt, id: ast::DefId) -> Option<ast::DefId> {
 pub fn provided_trait_methods(cx: ctxt, id: ast::DefId) -> ~[@Method] {
     if is_local(id) {
         {
-            let items = cx.items.borrow();
-            match items.get().find(&id.node) {
-                Some(&ast_map::NodeItem(item, _)) => {
+            match cx.items.find(id.node) {
+                Some(ast_map::NodeItem(item, _)) => {
                     match item.node {
                         ItemTrait(_, _, ref ms) => {
                             let (_, p) = ast_util::split_trait_methods(*ms);
@@ -3688,9 +3687,8 @@ pub fn impl_trait_ref(cx: ctxt, id: ast::DefId) -> Option<@TraitRef> {
     let ret = if id.crate == ast::LOCAL_CRATE {
         debug!("(impl_trait_ref) searching for trait impl {:?}", id);
         {
-            let items = cx.items.borrow();
-            match items.get().find(&id.node) {
-                Some(&ast_map::NodeItem(item, _)) => {
+            match cx.items.find(id.node) {
+                Some(ast_map::NodeItem(item, _)) => {
                     match item.node {
                         ast::ItemImpl(_, ref opt_trait, _, _) => {
                             match opt_trait {
@@ -3885,8 +3883,7 @@ pub fn item_path(cx: ctxt, id: ast::DefId) -> ast_map::Path {
     //                each variant.
     // let node = cx.items.get(&id.node);
     // match *node {
-    let items = cx.items.borrow();
-    match *items.get().get(&id.node) {
+    match cx.items.get(id.node) {
         ast_map::NodeItem(item, path) => {
             let item_elt = match item.node {
                 ItemMod(_) | ItemForeignMod(_) => {
@@ -3956,8 +3953,7 @@ pub fn enum_variants(cx: ctxt, id: ast::DefId) -> @~[@VariantInfo] {
           expr, since check_enum_variants also updates the enum_var_cache
          */
         {
-            let items = cx.items.borrow();
-            match items.get().get_copy(&id.node) {
+            match cx.items.get(id.node) {
               ast_map::NodeItem(item, _) => {
                   match item.node {
                     ast::ItemEnum(ref enum_definition, _) => {
@@ -4081,9 +4077,8 @@ pub fn lookup_trait_def(cx: ctxt, did: ast::DefId) -> @ty::TraitDef {
 pub fn each_attr(tcx: ctxt, did: DefId, f: |@MetaItem| -> bool) -> bool {
     if is_local(did) {
         {
-            let items = tcx.items.borrow();
-            match items.get().find(&did.node) {
-                Some(&ast_map::NodeItem(item, _)) => {
+            match tcx.items.find(did.node) {
+                Some(ast_map::NodeItem(item, _)) => {
                     item.attrs.iter().advance(|attr| f(attr.node.value))
                 }
                 _ => tcx.sess.bug(format!("has_attr: {:?} is not an item",
@@ -4165,9 +4160,8 @@ pub fn lookup_field_type(tcx: ctxt,
 pub fn lookup_struct_fields(cx: ctxt, did: ast::DefId) -> ~[field_ty] {
   if did.crate == ast::LOCAL_CRATE {
       {
-          let items = cx.items.borrow();
-          match items.get().find(&did.node) {
-           Some(&ast_map::NodeItem(i,_)) => {
+          match cx.items.find(did.node) {
+           Some(ast_map::NodeItem(i,_)) => {
              match i.node {
                 ast::ItemStruct(struct_def, _) => {
                    struct_field_tys(struct_def.fields)
@@ -4175,7 +4169,7 @@ pub fn lookup_struct_fields(cx: ctxt, did: ast::DefId) -> ~[field_ty] {
                 _ => cx.sess.bug("struct ID bound to non-struct")
              }
            }
-           Some(&ast_map::NodeVariant(ref variant, _, _)) => {
+           Some(ast_map::NodeVariant(ref variant, _, _)) => {
               match (*variant).node.kind {
                 ast::StructVariantKind(struct_def) => {
                   struct_field_tys(struct_def.fields)
@@ -4704,13 +4698,12 @@ pub fn populate_implementations_for_trait_if_necessary(
 /// If it implements no trait, return `None`.
 pub fn trait_id_of_impl(tcx: ctxt,
                         def_id: ast::DefId) -> Option<ast::DefId> {
-    let items = tcx.items.borrow();
-    let node = match items.get().find(&def_id.node) {
+    let node = match tcx.items.find(def_id.node) {
         Some(node) => node,
         None => return None
     };
     match node {
-        &ast_map::NodeItem(item, _) => {
+        ast_map::NodeItem(item, _) => {
             match item.node {
                 ast::ItemImpl(_, Some(ref trait_ref), _, _) => {
                     Some(node_id_to_trait_ref(tcx, trait_ref.ref_id).def_id)
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index 3c0849f04b8..293442417d2 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -1306,10 +1306,9 @@ impl<'a> LookupContext<'a> {
     fn report_static_candidate(&self, idx: uint, did: DefId) {
         let span = if did.crate == ast::LOCAL_CRATE {
             {
-                let items = self.tcx().items.borrow();
-                match items.get().find(&did.node) {
-                  Some(&ast_map::NodeMethod(m, _, _)) => m.span,
-                  Some(&ast_map::NodeTraitMethod(trait_method, _, _)) => {
+                match self.tcx().items.find(did.node) {
+                  Some(ast_map::NodeMethod(m, _, _)) => m.span,
+                  Some(ast_map::NodeTraitMethod(trait_method, _, _)) => {
                       match *trait_method {
                           ast::Provided(m) => m.span,
                           _ => {
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index c58b9fb83bb..89c24cf4116 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -570,14 +570,13 @@ impl CoherenceChecker {
 
                         // Make sure that this type precisely names a nominal
                         // type.
-                        let items = self.crate_context.tcx.items.borrow();
-                        match items.get().find(&def_id.node) {
+                        match self.crate_context.tcx.items.find(def_id.node) {
                             None => {
                                 self.crate_context.tcx.sess.span_bug(
                                     original_type.span,
                                     "resolve didn't resolve this type?!");
                             }
-                            Some(&NodeItem(item, _)) => {
+                            Some(NodeItem(item, _)) => {
                                 match item.node {
                                     ItemStruct(..) | ItemEnum(..) => true,
                                     _ => false,
@@ -628,9 +627,8 @@ impl CoherenceChecker {
 
     pub fn span_of_impl(&self, implementation: @Impl) -> Span {
         assert_eq!(implementation.did.crate, LOCAL_CRATE);
-        let items = self.crate_context.tcx.items.borrow();
-        match items.get().find(&implementation.did.node) {
-            Some(&NodeItem(item, _)) => {
+        match self.crate_context.tcx.items.find(implementation.did.node) {
+            Some(NodeItem(item, _)) => {
                 return item.span;
             }
             _ => {
@@ -734,9 +732,8 @@ impl CoherenceChecker {
                     // Destructors only work on nominal types.
                     if impl_info.did.crate == ast::LOCAL_CRATE {
                         {
-                            let items = tcx.items.borrow();
-                            match items.get().find(&impl_info.did.node) {
-                                Some(&ast_map::NodeItem(item, _)) => {
+                            match tcx.items.find(impl_info.did.node) {
+                                Some(ast_map::NodeItem(item, _)) => {
                                     tcx.sess.span_err((*item).span,
                                                       "the Drop trait may \
                                                        only be implemented \
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index f9193c4f73c..474335caa7b 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -110,10 +110,9 @@ impl AstConv for CrateCtxt {
             return csearch::get_type(self.tcx, id)
         }
 
-        let items = self.tcx.items.borrow();
-        match items.get().find(&id.node) {
-            Some(&ast_map::NodeItem(item, _)) => ty_of_item(self, item),
-            Some(&ast_map::NodeForeignItem(foreign_item, abis, _, _)) => {
+        match self.tcx.items.find(id.node) {
+            Some(ast_map::NodeItem(item, _)) => ty_of_item(self, item),
+            Some(ast_map::NodeForeignItem(foreign_item, abis, _, _)) => {
                 ty_of_foreign_item(self, foreign_item, abis)
             }
             ref x => {
@@ -185,8 +184,7 @@ pub fn get_enum_variant_types(ccx: &CrateCtxt,
 
 pub fn ensure_trait_methods(ccx: &CrateCtxt, trait_id: ast::NodeId) {
     let tcx = ccx.tcx;
-    let items = tcx.items.borrow();
-    match items.get().get_copy(&trait_id) {
+    match tcx.items.get(trait_id) {
         ast_map::NodeItem(item, _) => {
             match item.node {
                 ast::ItemTrait(ref generics, _, ref ms) => {
@@ -720,9 +718,8 @@ pub fn convert_foreign(ccx: &CrateCtxt, i: &ast::ForeignItem) {
     // map, and I regard each time that I use it as a personal and
     // moral failing, but at the moment it seems like the only
     // convenient way to extract the ABI. - ndm
-    let items = ccx.tcx.items.borrow();
-    let abis = match items.get().find(&i.id) {
-        Some(&ast_map::NodeForeignItem(_, abis, _, _)) => abis,
+    let abis = match ccx.tcx.items.find(i.id) {
+        Some(ast_map::NodeForeignItem(_, abis, _, _)) => abis,
         ref x => {
             ccx.tcx.sess.bug(format!("unexpected sort of item \
                                    in get_item_ty(): {:?}", (*x)));
@@ -774,9 +771,8 @@ fn get_trait_def(ccx: &CrateCtxt, trait_id: ast::DefId) -> @ty::TraitDef {
         return ty::lookup_trait_def(ccx.tcx, trait_id)
     }
 
-    let items = ccx.tcx.items.borrow();
-    match items.get().get(&trait_id.node) {
-        &ast_map::NodeItem(item, _) => trait_def_of_item(ccx, item),
+    match ccx.tcx.items.get(trait_id.node) {
+        ast_map::NodeItem(item, _) => trait_def_of_item(ccx, item),
         _ => ccx.tcx.sess.bug(format!("get_trait_def({}): not an item",
                                    trait_id.node))
     }
diff --git a/src/librustc/middle/typeck/mod.rs b/src/librustc/middle/typeck/mod.rs
index 0a7f7303a37..da3a2eebfeb 100644
--- a/src/librustc/middle/typeck/mod.rs
+++ b/src/librustc/middle/typeck/mod.rs
@@ -347,9 +347,8 @@ fn check_main_fn_ty(ccx: &CrateCtxt,
     let main_t = ty::node_id_to_type(tcx, main_id);
     match ty::get(main_t).sty {
         ty::ty_bare_fn(..) => {
-            let items = tcx.items.borrow();
-            match items.get().find(&main_id) {
-                Some(&ast_map::NodeItem(it,_)) => {
+            match tcx.items.find(main_id) {
+                Some(ast_map::NodeItem(it,_)) => {
                     match it.node {
                         ast::ItemFn(_, _, _, ref ps, _)
                         if ps.is_parameterized() => {
@@ -393,9 +392,8 @@ fn check_start_fn_ty(ccx: &CrateCtxt,
     let start_t = ty::node_id_to_type(tcx, start_id);
     match ty::get(start_t).sty {
         ty::ty_bare_fn(_) => {
-            let items = tcx.items.borrow();
-            match items.get().find(&start_id) {
-                Some(&ast_map::NodeItem(it,_)) => {
+            match tcx.items.find(start_id) {
+                Some(ast_map::NodeItem(it,_)) => {
                     match it.node {
                         ast::ItemFn(_,_,_,ref ps,_)
                         if ps.is_parameterized() => {
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index b9916749fe9..dc35ab7e885 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -72,15 +72,14 @@ pub fn explain_region_and_span(cx: ctxt, region: ty::Region)
                             -> (~str, Option<Span>) {
     return match region {
       ReScope(node_id) => {
-        let items = cx.items.borrow();
-        match items.get().find(&node_id) {
-          Some(&ast_map::NodeBlock(ref blk)) => {
+        match cx.items.find(node_id) {
+          Some(ast_map::NodeBlock(ref blk)) => {
             explain_span(cx, "block", blk.span)
           }
-          Some(&ast_map::NodeCalleeScope(expr)) => {
+          Some(ast_map::NodeCalleeScope(expr)) => {
               explain_span(cx, "callee", expr.span)
           }
-          Some(&ast_map::NodeExpr(expr)) => {
+          Some(ast_map::NodeExpr(expr)) => {
             match expr.node {
               ast::ExprCall(..) => explain_span(cx, "call", expr.span),
               ast::ExprMethodCall(..) => {
@@ -90,10 +89,10 @@ pub fn explain_region_and_span(cx: ctxt, region: ty::Region)
               _ => explain_span(cx, "expression", expr.span)
             }
           }
-          Some(&ast_map::NodeStmt(stmt)) => {
+          Some(ast_map::NodeStmt(stmt)) => {
               explain_span(cx, "statement", stmt.span)
           }
-          Some(&ast_map::NodeItem(it, _)) if (match it.node {
+          Some(ast_map::NodeItem(it, _)) if (match it.node {
                 ast::ItemFn(..) => true, _ => false}) => {
               explain_span(cx, "function body", it.span)
           }
@@ -114,13 +113,12 @@ pub fn explain_region_and_span(cx: ctxt, region: ty::Region)
                     bound_region_ptr_to_str(cx, fr.bound_region))
         };
 
-        let items = cx.items.borrow();
-        match items.get().find(&fr.scope_id) {
-          Some(&ast_map::NodeBlock(ref blk)) => {
+        match cx.items.find(fr.scope_id) {
+          Some(ast_map::NodeBlock(ref blk)) => {
             let (msg, opt_span) = explain_span(cx, "block", blk.span);
             (format!("{} {}", prefix, msg), opt_span)
           }
-          Some(&ast_map::NodeItem(it, _)) if match it.node {
+          Some(ast_map::NodeItem(it, _)) if match it.node {
                 ast::ItemImpl(..) => true, _ => false} => {
             let (msg, opt_span) = explain_span(cx, "impl", it.span);
             (format!("{} {}", prefix, msg), opt_span)
@@ -174,13 +172,12 @@ pub fn bound_region_to_str(cx: ctxt,
 }
 
 pub fn ReScope_id_to_str(cx: ctxt, node_id: ast::NodeId) -> ~str {
-    let items = cx.items.borrow();
-    match items.get().find(&node_id) {
-      Some(&ast_map::NodeBlock(ref blk)) => {
+    match cx.items.find(node_id) {
+      Some(ast_map::NodeBlock(ref blk)) => {
         format!("<block at {}>",
              cx.sess.codemap.span_to_str(blk.span))
       }
-      Some(&ast_map::NodeExpr(expr)) => {
+      Some(ast_map::NodeExpr(expr)) => {
         match expr.node {
           ast::ExprCall(..) => {
             format!("<call at {}>",
@@ -751,14 +748,13 @@ impl Repr for ast::DefId {
         // and otherwise fallback to just printing the crate/node pair
         if self.crate == ast::LOCAL_CRATE {
             {
-                let items = tcx.items.borrow();
-                match items.get().find(&self.node) {
-                    Some(&ast_map::NodeItem(..)) |
-                    Some(&ast_map::NodeForeignItem(..)) |
-                    Some(&ast_map::NodeMethod(..)) |
-                    Some(&ast_map::NodeTraitMethod(..)) |
-                    Some(&ast_map::NodeVariant(..)) |
-                    Some(&ast_map::NodeStructCtor(..)) => {
+                match tcx.items.find(self.node) {
+                    Some(ast_map::NodeItem(..)) |
+                    Some(ast_map::NodeForeignItem(..)) |
+                    Some(ast_map::NodeMethod(..)) |
+                    Some(ast_map::NodeTraitMethod(..)) |
+                    Some(ast_map::NodeVariant(..)) |
+                    Some(ast_map::NodeStructCtor(..)) => {
                         return format!("{:?}:{}",
                                        *self,
                                        ty::item_path_str(tcx, *self));
diff --git a/src/librustdoc/visit_ast.rs b/src/librustdoc/visit_ast.rs
index ce29584f5b9..171ec13a6e6 100644
--- a/src/librustdoc/visit_ast.rs
+++ b/src/librustdoc/visit_ast.rs
@@ -188,10 +188,7 @@ impl<'a> RustdocVisitor<'a> {
         };
         if analysis.public_items.contains(&def.node) { return false }
 
-        let item = {
-            let items = self.cx.tycx.unwrap().items.borrow();
-            *items.get().get(&def.node)
-        };
+        let item = self.cx.tycx.unwrap().items.get(def.node);
         match item {
             ast_map::NodeItem(it, _) => {
                 if glob {
diff --git a/src/libsyntax/ast_map.rs b/src/libsyntax/ast_map.rs
index 9cb4f14caf0..27f4c34d3cd 100644
--- a/src/libsyntax/ast_map.rs
+++ b/src/libsyntax/ast_map.rs
@@ -21,8 +21,9 @@ use parse::token::special_idents;
 use print::pprust;
 use util::small_vector::SmallVector;
 
+use std::logging;
 use std::cell::RefCell;
-use std::hashmap::HashMap;
+use extra::smallintmap::SmallIntMap;
 
 #[deriving(Clone, Eq)]
 pub enum PathElem {
@@ -193,7 +194,36 @@ impl Node {
     }
 }
 
-pub type Map = @RefCell<HashMap<NodeId, Node>>;
+pub struct Map {
+    /// NodeIds are sequential integers from 0, so we can be
+    /// super-compact by storing them in a vector. Not everything with
+    /// a NodeId is in the map, but empirically the occupancy is about
+    /// 75-80%, so there's not too much overhead (certainly less than
+    /// a hashmap, since they (at the time of writing) have a maximum
+    /// of 75% occupancy). (The additional overhead of the Option<>
+    /// inside the SmallIntMap could be removed by adding an extra
+    /// empty variant to Node and storing a vector here, but that was
+    /// found to not make much difference.)
+    ///
+    /// Also, indexing is pretty quick when you've got a vector and
+    /// plain old integers.
+    priv map: @RefCell<SmallIntMap<Node>>
+}
+
+impl Map {
+    /// Retrieve the Node corresponding to `id`, failing if it cannot
+    /// be found.
+    pub fn get(&self, id: ast::NodeId) -> Node {
+        let map = self.map.borrow();
+        *map.get().get(&(id as uint))
+    }
+    /// Retrieve the Node corresponding to `id`, returning None if
+    /// cannot be found.
+    pub fn find(&self, id: ast::NodeId) -> Option<Node> {
+        let map = self.map.borrow();
+        map.get().find(&(id as uint)).map(|&n| n)
+    }
+}
 
 pub trait FoldOps {
     fn new_id(&self, id: ast::NodeId) -> ast::NodeId {
@@ -213,8 +243,8 @@ pub struct Ctx<F> {
 
 impl<F> Ctx<F> {
     fn insert(&self, id: ast::NodeId, node: Node) {
-        let mut map = self.map.borrow_mut();
-        map.get().insert(id, node);
+        let mut map = self.map.map.borrow_mut();
+        map.get().insert(id as uint, node);
     }
 
     fn map_self(&self, m: @Method) {
@@ -375,12 +405,27 @@ impl<F: FoldOps> Folder for Ctx<F> {
 pub fn map_crate<F: 'static + FoldOps>(diag: @SpanHandler, c: Crate,
                                        fold_ops: F) -> (Crate, Map) {
     let mut cx = Ctx {
-        map: @RefCell::new(HashMap::new()),
+        map: Map { map: @RefCell::new(SmallIntMap::new()) },
         path: ~[],
         diag: diag,
         fold_ops: fold_ops
     };
-    (cx.fold_crate(c), cx.map)
+    let crate = cx.fold_crate(c);
+
+    if log_enabled!(logging::DEBUG) {
+        let map = cx.map.map.borrow();
+        // this only makes sense for ordered stores; note the
+        // enumerate to count the number of entries.
+        let (entries_less_1, (largest_id, _)) =
+            map.get().iter().enumerate().last().expect("AST map was empty after folding?");
+
+        let entries = entries_less_1 + 1;
+        let vector_length = largest_id + 1;
+        debug!("The AST map has {} entries with a maximum of {}: occupancy {:.1}%",
+              entries, vector_length, (entries as f64 / vector_length as f64) * 100.);
+    }
+
+    (crate, cx.map)
 }
 
 // Used for items loaded from external crate that are being inlined into this
@@ -430,12 +475,11 @@ pub fn map_decoded_item<F: 'static + FoldOps>(diag: @SpanHandler,
 }
 
 pub fn node_id_to_str(map: Map, id: NodeId, itr: @IdentInterner) -> ~str {
-    let map = map.borrow();
-    match map.get().find(&id) {
+    match map.find(id) {
       None => {
         format!("unknown node (id={})", id)
       }
-      Some(&NodeItem(item, path)) => {
+      Some(NodeItem(item, path)) => {
         let path_str = path_ident_to_str(path, item.ident, itr);
         let item_str = match item.node {
             ItemStatic(..) => ~"static",
@@ -451,43 +495,43 @@ pub fn node_id_to_str(map: Map, id: NodeId, itr: @IdentInterner) -> ~str {
         };
         format!("{} {} (id={})", item_str, path_str, id)
       }
-      Some(&NodeForeignItem(item, abi, _, path)) => {
+      Some(NodeForeignItem(item, abi, _, path)) => {
         format!("foreign item {} with abi {:?} (id={})",
              path_ident_to_str(path, item.ident, itr), abi, id)
       }
-      Some(&NodeMethod(m, _, path)) => {
+      Some(NodeMethod(m, _, path)) => {
         format!("method {} in {} (id={})",
              itr.get(m.ident.name), path_to_str(*path, itr), id)
       }
-      Some(&NodeTraitMethod(ref tm, _, path)) => {
+      Some(NodeTraitMethod(ref tm, _, path)) => {
         let m = ast_util::trait_method_to_ty_method(&**tm);
         format!("method {} in {} (id={})",
              itr.get(m.ident.name), path_to_str(*path, itr), id)
       }
-      Some(&NodeVariant(ref variant, _, path)) => {
+      Some(NodeVariant(ref variant, _, path)) => {
         format!("variant {} in {} (id={})",
              itr.get(variant.node.name.name), path_to_str(*path, itr), id)
       }
-      Some(&NodeExpr(expr)) => {
+      Some(NodeExpr(expr)) => {
         format!("expr {} (id={})", pprust::expr_to_str(expr, itr), id)
       }
-      Some(&NodeCalleeScope(expr)) => {
+      Some(NodeCalleeScope(expr)) => {
         format!("callee_scope {} (id={})", pprust::expr_to_str(expr, itr), id)
       }
-      Some(&NodeStmt(stmt)) => {
+      Some(NodeStmt(stmt)) => {
         format!("stmt {} (id={})",
              pprust::stmt_to_str(stmt, itr), id)
       }
-      Some(&NodeArg(pat)) => {
+      Some(NodeArg(pat)) => {
         format!("arg {} (id={})", pprust::pat_to_str(pat, itr), id)
       }
-      Some(&NodeLocal(ident, _)) => {
+      Some(NodeLocal(ident, _)) => {
         format!("local (id={}, name={})", id, itr.get(ident.name))
       }
-      Some(&NodeBlock(block)) => {
+      Some(NodeBlock(block)) => {
         format!("block {} (id={})", pprust::block_to_str(block, itr), id)
       }
-      Some(&NodeStructCtor(_, _, path)) => {
+      Some(NodeStructCtor(_, _, path)) => {
         format!("struct_ctor {} (id={})", path_to_str(*path, itr), id)
       }
     }
@@ -495,36 +539,34 @@ pub fn node_id_to_str(map: Map, id: NodeId, itr: @IdentInterner) -> ~str {
 
 pub fn node_item_query<Result>(items: Map, id: NodeId, query: |@Item| -> Result, error_msg: ~str)
                        -> Result {
-    let items = items.borrow();
-    match items.get().find(&id) {
-        Some(&NodeItem(it, _)) => query(it),
+    match items.find(id) {
+        Some(NodeItem(it, _)) => query(it),
         _ => fail!("{}", error_msg)
     }
 }
 
 pub fn node_span(items: Map, id: ast::NodeId) -> Span {
-    let items = items.borrow();
-    match items.get().find(&id) {
-        Some(&NodeItem(item, _)) => item.span,
-        Some(&NodeForeignItem(foreign_item, _, _, _)) => foreign_item.span,
-        Some(&NodeTraitMethod(trait_method, _, _)) => {
+    match items.find(id) {
+        Some(NodeItem(item, _)) => item.span,
+        Some(NodeForeignItem(foreign_item, _, _, _)) => foreign_item.span,
+        Some(NodeTraitMethod(trait_method, _, _)) => {
             match *trait_method {
                 Required(ref type_method) => type_method.span,
                 Provided(ref method) => method.span,
             }
         }
-        Some(&NodeMethod(method, _, _)) => method.span,
-        Some(&NodeVariant(variant, _, _)) => variant.span,
-        Some(&NodeExpr(expr)) => expr.span,
-        Some(&NodeStmt(stmt)) => stmt.span,
-        Some(&NodeArg(pat)) => pat.span,
-        Some(&NodeLocal(_, pat)) => match pat {
+        Some(NodeMethod(method, _, _)) => method.span,
+        Some(NodeVariant(variant, _, _)) => variant.span,
+        Some(NodeExpr(expr)) => expr.span,
+        Some(NodeStmt(stmt)) => stmt.span,
+        Some(NodeArg(pat)) => pat.span,
+        Some(NodeLocal(_, pat)) => match pat {
             Some(pat) => pat.span,
             None => fail!("node_span: cannot get span from NodeLocal (likely `self`)")
         },
-        Some(&NodeBlock(block)) => block.span,
-        Some(&NodeStructCtor(_, item, _)) => item.span,
-        Some(&NodeCalleeScope(expr)) => expr.span,
+        Some(NodeBlock(block)) => block.span,
+        Some(NodeStructCtor(_, item, _)) => item.span,
+        Some(NodeCalleeScope(expr)) => expr.span,
         None => fail!("node_span: could not find id {}", id),
     }
 }