Allocate numerical values of DefIndexes from two seperate ranges.

This way we can have all item-likes occupy a dense range of
DefIndexes, which is good for making fast, array-based
dictionaries.

7 files changed, 237 insertions, 72 deletions

diff --git a/src/librustc/hir/def_id.rs b/src/librustc/hir/def_id.rs
index cbf162cc136..a6b18ac10a7 100644
--- a/src/librustc/hir/def_id.rs
+++ b/src/librustc/hir/def_id.rs
@@ -78,33 +78,86 @@ impl serialize::UseSpecializedDecodable for CrateNum {
 /// A DefIndex is an index into the hir-map for a crate, identifying a
 /// particular definition. It should really be considered an interned
 /// shorthand for a particular DefPath.
+///
+/// At the moment we are allocating the numerical values of DefIndexes into two
+/// ranges: the "low" range (starting at zero) and the "high" range (starting at
+/// DEF_INDEX_HI_START). This allows us to allocate the DefIndexes of all
+/// item-likes (Items, TraitItems, and ImplItems) into one of these ranges and
+/// consequently use a simple array for lookup tables keyed by DefIndex and
+/// known to be densely populated. This is especially important for the HIR map.
+///
+/// Since the DefIndex is mostly treated as an opaque ID, you probably
+/// don't have to care about these ranges.
 #[derive(Clone, Debug, Eq, Ord, PartialOrd, PartialEq, RustcEncodable,
            RustcDecodable, Hash, Copy)]
 pub struct DefIndex(u32);
 
 impl DefIndex {
+    #[inline]
     pub fn new(x: usize) -> DefIndex {
         assert!(x < (u32::MAX as usize));
         DefIndex(x as u32)
     }
 
+    #[inline]
     pub fn from_u32(x: u32) -> DefIndex {
         DefIndex(x)
     }
 
+    #[inline]
     pub fn as_usize(&self) -> usize {
         self.0 as usize
     }
 
+    #[inline]
     pub fn as_u32(&self) -> u32 {
         self.0
     }
+
+    #[inline]
+    pub fn address_space(&self) -> DefIndexAddressSpace {
+        if self.0 < DEF_INDEX_HI_START.0 {
+            DefIndexAddressSpace::Low
+        } else {
+            DefIndexAddressSpace::High
+        }
+    }
+
+    /// Converts this DefIndex into a zero-based array index.
+    /// This index is the offset within the given "range" of the DefIndex,
+    /// that is, if the DefIndex is part of the "high" range, the resulting
+    /// index will be (DefIndex - DEF_INDEX_HI_START).
+    #[inline]
+    pub fn as_array_index(&self) -> usize {
+        (self.0 & !DEF_INDEX_HI_START.0) as usize
+    }
 }
 
+/// The start of the "high" range of DefIndexes.
+const DEF_INDEX_HI_START: DefIndex = DefIndex(1 << 31);
+
 /// The crate root is always assigned index 0 by the AST Map code,
 /// thanks to `NodeCollector::new`.
 pub const CRATE_DEF_INDEX: DefIndex = DefIndex(0);
 
+#[derive(Copy, Clone, Eq, PartialEq, Hash)]
+pub enum DefIndexAddressSpace {
+    Low = 0,
+    High = 1,
+}
+
+impl DefIndexAddressSpace {
+    #[inline]
+    pub fn index(&self) -> usize {
+        *self as usize
+    }
+
+    #[inline]
+    pub fn start(&self) -> usize {
+        self.index() * DEF_INDEX_HI_START.as_usize()
+    }
+}
+
 /// A DefId identifies a particular *definition*, by combining a crate
 /// index and a def index.
 #[derive(Clone, Eq, Ord, PartialOrd, PartialEq, RustcEncodable, RustcDecodable, Hash, Copy)]
diff --git a/src/librustc/hir/lowering.rs b/src/librustc/hir/lowering.rs
index 22ca0e421be..2ac1a036f99 100644
--- a/src/librustc/hir/lowering.rs
+++ b/src/librustc/hir/lowering.rs
@@ -41,7 +41,7 @@
 // in the HIR, especially for multiple identifiers.
 
 use hir;
-use hir::map::{Definitions, DefKey};
+use hir::map::{Definitions, DefKey, REGULAR_SPACE};
 use hir::map::definitions::DefPathData;
 use hir::def_id::{DefIndex, DefId, CRATE_DEF_INDEX};
 use hir::def::{Def, PathResolution};
@@ -2711,7 +2711,10 @@ impl<'a> LoweringContext<'a> {
         let def_id = {
             let defs = self.resolver.definitions();
             let def_path_data = DefPathData::Binding(name.as_str());
-            let def_index = defs.create_def_with_parent(parent_def, id, def_path_data);
+            let def_index = defs.create_def_with_parent(parent_def,
+                                                        id,
+                                                        def_path_data,
+                                                        REGULAR_SPACE);
             DefId::local(def_index)
         };
 
diff --git a/src/librustc/hir/map/def_collector.rs b/src/librustc/hir/map/def_collector.rs
index f15e063e81e..cae358a303e 100644
--- a/src/librustc/hir/map/def_collector.rs
+++ b/src/librustc/hir/map/def_collector.rs
@@ -9,13 +9,15 @@
 // except according to those terms.
 
 use hir::map::definitions::*;
-use hir::def_id::{CRATE_DEF_INDEX, DefIndex};
+use hir::def_id::{CRATE_DEF_INDEX, DefIndex, DefIndexAddressSpace};
 
 use syntax::ast::*;
 use syntax::ext::hygiene::Mark;
 use syntax::visit;
 use syntax::symbol::{Symbol, keywords};
 
+use hir::map::{ITEM_LIKE_SPACE, REGULAR_SPACE};
+
 /// Creates def ids for nodes in the AST.
 pub struct DefCollector<'a> {
     definitions: &'a mut Definitions,
@@ -39,23 +41,31 @@ impl<'a> DefCollector<'a> {
     }
 
     pub fn collect_root(&mut self) {
-        let root = self.create_def_with_parent(None, CRATE_NODE_ID, DefPathData::CrateRoot);
+        let root = self.create_def_with_parent(None,
+                                               CRATE_NODE_ID,
+                                               DefPathData::CrateRoot,
+                                               ITEM_LIKE_SPACE);
         assert_eq!(root, CRATE_DEF_INDEX);
         self.parent_def = Some(root);
     }
 
-    fn create_def(&mut self, node_id: NodeId, data: DefPathData) -> DefIndex {
+    fn create_def(&mut self,
+                  node_id: NodeId,
+                  data: DefPathData,
+                  address_space: DefIndexAddressSpace)
+                  -> DefIndex {
         let parent_def = self.parent_def;
         debug!("create_def(node_id={:?}, data={:?}, parent_def={:?})", node_id, data, parent_def);
-        self.definitions.create_def_with_parent(parent_def, node_id, data)
+        self.definitions.create_def_with_parent(parent_def, node_id, data, address_space)
     }
 
     fn create_def_with_parent(&mut self,
                               parent: Option<DefIndex>,
                               node_id: NodeId,
-                              data: DefPathData)
+                              data: DefPathData,
+                              address_space: DefIndexAddressSpace)
                               -> DefIndex {
-        self.definitions.create_def_with_parent(parent, node_id, data)
+        self.definitions.create_def_with_parent(parent, node_id, data, address_space)
     }
 
     pub fn with_parent<F: FnOnce(&mut Self)>(&mut self, parent_def: DefIndex, f: F) {
@@ -76,7 +86,7 @@ impl<'a> DefCollector<'a> {
             _ => {}
         }
 
-        self.create_def(expr.id, DefPathData::Initializer);
+        self.create_def(expr.id, DefPathData::Initializer, REGULAR_SPACE);
     }
 
     fn visit_macro_invoc(&mut self, id: NodeId, const_expr: bool) {
@@ -118,14 +128,16 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
                     ViewPathSimple(..) => {}
                     ViewPathList(_, ref imports) => {
                         for import in imports {
-                            self.create_def(import.node.id, DefPathData::Misc);
+                            self.create_def(import.node.id,
+                                            DefPathData::Misc,
+                                            ITEM_LIKE_SPACE);
                         }
                     }
                 }
                 DefPathData::Misc
             }
         };
-        let def = self.create_def(i.id, def_data);
+        let def = self.create_def(i.id, def_data, ITEM_LIKE_SPACE);
 
         self.with_parent(def, |this| {
             match i.node {
@@ -133,12 +145,15 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
                     for v in &enum_definition.variants {
                         let variant_def_index =
                             this.create_def(v.node.data.id(),
-                                            DefPathData::EnumVariant(v.node.name.name.as_str()));
+                                            DefPathData::EnumVariant(v.node.name.name.as_str()),
+                                            REGULAR_SPACE);
                         this.with_parent(variant_def_index, |this| {
                             for (index, field) in v.node.data.fields().iter().enumerate() {
                                 let name = field.ident.map(|ident| ident.name)
                                     .unwrap_or_else(|| Symbol::intern(&index.to_string()));
-                                this.create_def(field.id, DefPathData::Field(name.as_str()));
+                                this.create_def(field.id,
+                                                DefPathData::Field(name.as_str()),
+                                                REGULAR_SPACE);
                             }
 
                             if let Some(ref expr) = v.node.disr_expr {
@@ -151,13 +166,14 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
                     // If this is a tuple-like struct, register the constructor.
                     if !struct_def.is_struct() {
                         this.create_def(struct_def.id(),
-                                        DefPathData::StructCtor);
+                                        DefPathData::StructCtor,
+                                        REGULAR_SPACE);
                     }
 
                     for (index, field) in struct_def.fields().iter().enumerate() {
                         let name = field.ident.map(|ident| ident.name.as_str())
                             .unwrap_or(Symbol::intern(&index.to_string()).as_str());
-                        this.create_def(field.id, DefPathData::Field(name));
+                        this.create_def(field.id, DefPathData::Field(name), REGULAR_SPACE);
                     }
                 }
                 _ => {}
@@ -168,7 +184,8 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
 
     fn visit_foreign_item(&mut self, foreign_item: &'a ForeignItem) {
         let def = self.create_def(foreign_item.id,
-                                  DefPathData::ValueNs(foreign_item.ident.name.as_str()));
+                                  DefPathData::ValueNs(foreign_item.ident.name.as_str()),
+                                  REGULAR_SPACE);
 
         self.with_parent(def, |this| {
             visit::walk_foreign_item(this, foreign_item);
@@ -177,7 +194,9 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
 
     fn visit_generics(&mut self, generics: &'a Generics) {
         for ty_param in generics.ty_params.iter() {
-            self.create_def(ty_param.id, DefPathData::TypeParam(ty_param.ident.name.as_str()));
+            self.create_def(ty_param.id,
+                            DefPathData::TypeParam(ty_param.ident.name.as_str()),
+                            REGULAR_SPACE);
         }
 
         visit::walk_generics(self, generics);
@@ -191,7 +210,7 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
             TraitItemKind::Macro(..) => return self.visit_macro_invoc(ti.id, false),
         };
 
-        let def = self.create_def(ti.id, def_data);
+        let def = self.create_def(ti.id, def_data, ITEM_LIKE_SPACE);
         self.with_parent(def, |this| {
             if let TraitItemKind::Const(_, Some(ref expr)) = ti.node {
                 this.visit_const_expr(expr);
@@ -209,7 +228,7 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
             ImplItemKind::Macro(..) => return self.visit_macro_invoc(ii.id, false),
         };
 
-        let def = self.create_def(ii.id, def_data);
+        let def = self.create_def(ii.id, def_data, ITEM_LIKE_SPACE);
         self.with_parent(def, |this| {
             if let ImplItemKind::Const(_, ref expr) = ii.node {
                 this.visit_const_expr(expr);
@@ -225,7 +244,9 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
         match pat.node {
             PatKind::Mac(..) => return self.visit_macro_invoc(pat.id, false),
             PatKind::Ident(_, id, _) => {
-                let def = self.create_def(pat.id, DefPathData::Binding(id.node.name.as_str()));
+                let def = self.create_def(pat.id,
+                                          DefPathData::Binding(id.node.name.as_str()),
+                                          REGULAR_SPACE);
                 self.parent_def = Some(def);
             }
             _ => {}
@@ -242,7 +263,9 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
             ExprKind::Mac(..) => return self.visit_macro_invoc(expr.id, false),
             ExprKind::Repeat(_, ref count) => self.visit_const_expr(count),
             ExprKind::Closure(..) => {
-                let def = self.create_def(expr.id, DefPathData::ClosureExpr);
+                let def = self.create_def(expr.id,
+                                          DefPathData::ClosureExpr,
+                                          REGULAR_SPACE);
                 self.parent_def = Some(def);
             }
             _ => {}
@@ -257,7 +280,7 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
             TyKind::Mac(..) => return self.visit_macro_invoc(ty.id, false),
             TyKind::Array(_, ref length) => self.visit_const_expr(length),
             TyKind::ImplTrait(..) => {
-                self.create_def(ty.id, DefPathData::ImplTrait);
+                self.create_def(ty.id, DefPathData::ImplTrait, REGULAR_SPACE);
             }
             TyKind::Typeof(ref expr) => self.visit_const_expr(expr),
             _ => {}
@@ -266,7 +289,9 @@ impl<'a> visit::Visitor<'a> for DefCollector<'a> {
     }
 
     fn visit_lifetime_def(&mut self, def: &'a LifetimeDef) {
-        self.create_def(def.lifetime.id, DefPathData::LifetimeDef(def.lifetime.name.as_str()));
+        self.create_def(def.lifetime.id,
+                        DefPathData::LifetimeDef(def.lifetime.name.as_str()),
+                        REGULAR_SPACE);
     }
 
     fn visit_stmt(&mut self, stmt: &'a Stmt) {
diff --git a/src/librustc/hir/map/definitions.rs b/src/librustc/hir/map/definitions.rs
index 0f7e54953b0..809d5db3071 100644
--- a/src/librustc/hir/map/definitions.rs
+++ b/src/librustc/hir/map/definitions.rs
@@ -15,7 +15,7 @@
 //! expressions) that are mostly just leftovers.
 
 use hir;
-use hir::def_id::{CrateNum, DefId, DefIndex, LOCAL_CRATE};
+use hir::def_id::{CrateNum, DefId, DefIndex, LOCAL_CRATE, DefIndexAddressSpace};
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::indexed_vec::IndexVec;
 use rustc_data_structures::stable_hasher::StableHasher;
@@ -31,24 +31,44 @@ use util::nodemap::NodeMap;
 /// Internally the DefPathTable holds a tree of DefKeys, where each DefKey
 /// stores the DefIndex of its parent.
 /// There is one DefPathTable for each crate.
-#[derive(Clone)]
 pub struct DefPathTable {
-    index_to_key: Vec<DefKey>,
+    index_to_key: [Vec<DefKey>; 2],
     key_to_index: FxHashMap<DefKey, DefIndex>,
 }
 
+// Unfortunately we have to provide a manual impl of Clone because of the
+// fixed-sized array field.
+impl Clone for DefPathTable {
+    fn clone(&self) -> Self {
+        DefPathTable {
+            index_to_key: [self.index_to_key[0].clone(),
+                           self.index_to_key[1].clone()],
+            key_to_index: self.key_to_index.clone(),
+        }
+    }
+}
+
 impl DefPathTable {
-    fn insert(&mut self, key: DefKey) -> DefIndex {
-        let index = DefIndex::new(self.index_to_key.len());
-        debug!("DefPathTable::insert() - {:?} <-> {:?}", key, index);
-        self.index_to_key.push(key.clone());
+
+    fn allocate(&mut self,
+                key: DefKey,
+                address_space: DefIndexAddressSpace)
+                -> DefIndex {
+        let index = {
+            let index_to_key = &mut self.index_to_key[address_space.index()];
+            let index = DefIndex::new(index_to_key.len() + address_space.start());
+            debug!("DefPathTable::insert() - {:?} <-> {:?}", key, index);
+            index_to_key.push(key.clone());
+            index
+        };
         self.key_to_index.insert(key, index);
         index
     }
 
     #[inline(always)]
     pub fn def_key(&self, index: DefIndex) -> DefKey {
-        self.index_to_key[index.as_usize()].clone()
+        self.index_to_key[index.address_space().index()]
+                         [index.as_array_index()].clone()
     }
 
     #[inline(always)]
@@ -96,17 +116,28 @@ impl DefPathTable {
 
 impl Encodable for DefPathTable {
     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
-        self.index_to_key.encode(s)
+        self.index_to_key[DefIndexAddressSpace::Low.index()].encode(s)?;
+        self.index_to_key[DefIndexAddressSpace::High.index()].encode(s)
     }
 }
 
 impl Decodable for DefPathTable {
     fn decode<D: Decoder>(d: &mut D) -> Result<DefPathTable, D::Error> {
-        let index_to_key: Vec<DefKey> = Decodable::decode(d)?;
-        let key_to_index = index_to_key.iter()
-                                       .enumerate()
-                                       .map(|(index, key)| (key.clone(), DefIndex::new(index)))
-                                       .collect();
+        let index_to_key_lo: Vec<DefKey> = Decodable::decode(d)?;
+        let index_to_key_high: Vec<DefKey> = Decodable::decode(d)?;
+
+        let index_to_key = [index_to_key_lo, index_to_key_high];
+
+        let mut key_to_index = FxHashMap();
+
+        for space in &[DefIndexAddressSpace::Low, DefIndexAddressSpace::High] {
+            key_to_index.extend(index_to_key[space.index()]
+                .iter()
+                .enumerate()
+                .map(|(index, key)| (key.clone(),
+                                     DefIndex::new(index + space.start()))))
+        }
+
         Ok(DefPathTable {
             index_to_key: index_to_key,
             key_to_index: key_to_index,
@@ -118,14 +149,29 @@ impl Decodable for DefPathTable {
 /// The definition table containing node definitions.
 /// It holds the DefPathTable for local DefIds/DefPaths and it also stores a
 /// mapping from NodeIds to local DefIds.
-#[derive(Clone)]
 pub struct Definitions {
     table: DefPathTable,
     node_to_def_index: NodeMap<DefIndex>,
-    def_index_to_node: Vec<ast::NodeId>,
+    def_index_to_node: [Vec<ast::NodeId>; 2],
     pub(super) node_to_hir_id: IndexVec<ast::NodeId, hir::HirId>,
 }
 
+// Unfortunately we have to provide a manual impl of Clone because of the
+// fixed-sized array field.
+impl Clone for Definitions {
+    fn clone(&self) -> Self {
+        Definitions {
+            table: self.table.clone(),
+            node_to_def_index: self.node_to_def_index.clone(),
+            def_index_to_node: [
+                self.def_index_to_node[0].clone(),
+                self.def_index_to_node[1].clone(),
+            ],
+            node_to_hir_id: self.node_to_hir_id.clone(),
+        }
+    }
+}
+
 /// A unique identifier that we can use to lookup a definition
 /// precisely. It combines the index of the definition's parent (if
 /// any) with a `DisambiguatedDefPathData`.
@@ -290,11 +336,11 @@ impl Definitions {
     pub fn new() -> Definitions {
         Definitions {
             table: DefPathTable {
-                index_to_key: vec![],
+                index_to_key: [vec![], vec![]],
                 key_to_index: FxHashMap(),
             },
             node_to_def_index: NodeMap(),
-            def_index_to_node: vec![],
+            def_index_to_node: [vec![], vec![]],
             node_to_hir_id: IndexVec::new(),
         }
     }
@@ -304,8 +350,9 @@ impl Definitions {
     }
 
     /// Get the number of definitions.
-    pub fn len(&self) -> usize {
-        self.def_index_to_node.len()
+    pub fn def_index_counts_lo_hi(&self) -> (usize, usize) {
+        (self.def_index_to_node[DefIndexAddressSpace::Low.index()].len(),
+         self.def_index_to_node[DefIndexAddressSpace::High.index()].len())
     }
 
     pub fn def_key(&self, index: DefIndex) -> DefKey {
@@ -339,8 +386,9 @@ impl Definitions {
 
     pub fn as_local_node_id(&self, def_id: DefId) -> Option<ast::NodeId> {
         if def_id.krate == LOCAL_CRATE {
-            assert!(def_id.index.as_usize() < self.def_index_to_node.len());
-            Some(self.def_index_to_node[def_id.index.as_usize()])
+            let space_index = def_id.index.address_space().index();
+            let array_index = def_id.index.as_array_index();
+            Some(self.def_index_to_node[space_index][array_index])
         } else {
             None
         }
@@ -350,7 +398,9 @@ impl Definitions {
     pub fn create_def_with_parent(&mut self,
                                   parent: Option<DefIndex>,
                                   node_id: ast::NodeId,
-                                  data: DefPathData)
+                                  data: DefPathData,
+                                  // is_owner: bool)
+                                  address_space: DefIndexAddressSpace)
                                   -> DefIndex {
         debug!("create_def_with_parent(parent={:?}, node_id={:?}, data={:?})",
                parent, node_id, data);
@@ -380,11 +430,13 @@ impl Definitions {
         debug!("create_def_with_parent: after disambiguation, key = {:?}", key);
 
         // Create the definition.
-        let index = self.table.insert(key);
+        let index = self.table.allocate(key, address_space);
+        assert_eq!(index.as_array_index(),
+                   self.def_index_to_node[address_space.index()].len());
+        self.def_index_to_node[address_space.index()].push(node_id);
+
         debug!("create_def_with_parent: def_index_to_node[{:?} <-> {:?}", index, node_id);
         self.node_to_def_index.insert(node_id, index);
-        assert_eq!(index.as_usize(), self.def_index_to_node.len());
-        self.def_index_to_node.push(node_id);
 
         index
     }
diff --git a/src/librustc/hir/map/mod.rs b/src/librustc/hir/map/mod.rs
index 3def41fd425..583b3b848f3 100644
--- a/src/librustc/hir/map/mod.rs
+++ b/src/librustc/hir/map/mod.rs
@@ -17,7 +17,7 @@ pub use self::definitions::{Definitions, DefKey, DefPath, DefPathData,
 
 use dep_graph::{DepGraph, DepNode};
 
-use hir::def_id::{CRATE_DEF_INDEX, DefId, DefIndex};
+use hir::def_id::{CRATE_DEF_INDEX, DefId, DefIndex, DefIndexAddressSpace};
 
 use syntax::abi::Abi;
 use syntax::ast::{self, Name, NodeId, CRATE_NODE_ID};
@@ -38,6 +38,9 @@ mod def_collector;
 pub mod definitions;
 mod hir_id_validator;
 
+pub const ITEM_LIKE_SPACE: DefIndexAddressSpace = DefIndexAddressSpace::Low;
+pub const REGULAR_SPACE: DefIndexAddressSpace = DefIndexAddressSpace::High;
+
 #[derive(Copy, Clone, Debug)]
 pub enum Node<'hir> {
     NodeItem(&'hir Item),
@@ -347,10 +350,6 @@ impl<'hir> Map<'hir> {
         }
     }
 
-    pub fn num_local_def_ids(&self) -> usize {
-        self.definitions.len()
-    }
-
     pub fn definitions(&self) -> &Definitions {
         &self.definitions
     }
diff --git a/src/librustc_metadata/index.rs b/src/librustc_metadata/index.rs
index db9fc870fa8..970a401177b 100644
--- a/src/librustc_metadata/index.rs
+++ b/src/librustc_metadata/index.rs
@@ -10,7 +10,7 @@
 
 use schema::*;
 
-use rustc::hir::def_id::{DefId, DefIndex};
+use rustc::hir::def_id::{DefId, DefIndex, DefIndexAddressSpace};
 use std::io::{Cursor, Write};
 use std::slice;
 use std::u32;
@@ -23,12 +23,15 @@ use std::u32;
 /// appropriate spot by calling `record_position`. We should never
 /// visit the same index twice.
 pub struct Index {
-    positions: Vec<u32>,
+    positions: [Vec<u32>; 2]
 }
 
 impl Index {
-    pub fn new(max_index: usize) -> Index {
-        Index { positions: vec![u32::MAX; max_index] }
+    pub fn new((max_index_lo, max_index_hi): (usize, usize)) -> Index {
+        Index {
+            positions: [vec![u32::MAX; max_index_lo],
+                        vec![u32::MAX; max_index_hi]],
+        }
     }
 
     pub fn record(&mut self, def_id: DefId, entry: Lazy<Entry>) {
@@ -37,24 +40,31 @@ impl Index {
     }
 
     pub fn record_index(&mut self, item: DefIndex, entry: Lazy<Entry>) {
-        let item = item.as_usize();
-
         assert!(entry.position < (u32::MAX as usize));
         let position = entry.position as u32;
+        let space_index = item.address_space().index();
+        let array_index = item.as_array_index();
 
-        assert!(self.positions[item] == u32::MAX,
+        assert!(self.positions[space_index][array_index] == u32::MAX,
                 "recorded position for item {:?} twice, first at {:?} and now at {:?}",
                 item,
-                self.positions[item],
+                self.positions[space_index][array_index],
                 position);
 
-        self.positions[item] = position.to_le();
+        self.positions[space_index][array_index] = position.to_le();
     }
 
     pub fn write_index(&self, buf: &mut Cursor<Vec<u8>>) -> LazySeq<Index> {
         let pos = buf.position();
-        buf.write_all(words_to_bytes(&self.positions)).unwrap();
-        LazySeq::with_position_and_length(pos as usize, self.positions.len())
+
+        // First we write the length of the lower range ...
+        buf.write_all(words_to_bytes(&[self.positions[0].len() as u32])).unwrap();
+        // ... then the values in the lower range ...
+        buf.write_all(words_to_bytes(&self.positions[0][..])).unwrap();
+        // ... then the values in the higher range.
+        buf.write_all(words_to_bytes(&self.positions[1][..])).unwrap();
+        LazySeq::with_position_and_length(pos as usize,
+            self.positions[0].len() + self.positions[1].len() + 1)
     }
 }
 
@@ -70,7 +80,18 @@ impl<'tcx> LazySeq<Index> {
                index,
                words.len());
 
-        let position = u32::from_le(words[index].get());
+        let positions = match def_index.address_space() {
+            DefIndexAddressSpace::Low => &words[1..],
+            DefIndexAddressSpace::High => {
+                // This is a DefIndex in the higher range, so find out where
+                // that starts:
+                let lo_count = u32::from_le(words[0].get()) as usize;
+                &words[lo_count + 1 .. ]
+            }
+        };
+
+        let array_index = def_index.as_array_index();
+        let position = u32::from_le(positions[array_index].get());
         if position == u32::MAX {
             debug!("Index::lookup: position=u32::MAX");
             None
@@ -84,14 +105,26 @@ impl<'tcx> LazySeq<Index> {
                                bytes: &'a [u8])
                                -> impl Iterator<Item = (DefIndex, Lazy<Entry<'tcx>>)> + 'a {
         let words = &bytes_to_words(&bytes[self.position..])[..self.len];
-        words.iter().map(|word| word.get()).enumerate().filter_map(|(index, position)| {
-            if position == u32::MAX {
+        let lo_count = u32::from_le(words[0].get()) as usize;
+        let lo = &words[1 .. lo_count + 1];
+        let hi = &words[1 + lo_count ..];
+
+        lo.iter().map(|word| word.get()).enumerate().filter_map(|(index, pos)| {
+            if pos == u32::MAX {
+                None
+            } else {
+                let pos = u32::from_le(pos) as usize;
+                Some((DefIndex::new(index), Lazy::with_position(pos)))
+            }
+        }).chain(hi.iter().map(|word| word.get()).enumerate().filter_map(|(index, pos)| {
+            if pos == u32::MAX {
                 None
             } else {
-                let position = u32::from_le(position) as usize;
-                Some((DefIndex::new(index), Lazy::with_position(position)))
+                let pos = u32::from_le(pos) as usize;
+                Some((DefIndex::new(index + DefIndexAddressSpace::High.start()),
+                                    Lazy::with_position(pos)))
             }
-        })
+        }))
     }
 }
 
diff --git a/src/librustc_metadata/index_builder.rs b/src/librustc_metadata/index_builder.rs
index 2359c747d88..a811f72bc95 100644
--- a/src/librustc_metadata/index_builder.rs
+++ b/src/librustc_metadata/index_builder.rs
@@ -90,7 +90,7 @@ impl<'a, 'b, 'tcx> DerefMut for IndexBuilder<'a, 'b, 'tcx> {
 impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
     pub fn new(ecx: &'a mut EncodeContext<'b, 'tcx>) -> Self {
         IndexBuilder {
-            items: Index::new(ecx.tcx.hir.num_local_def_ids()),
+            items: Index::new(ecx.tcx.hir.definitions().def_index_counts_lo_hi()),
             ecx: ecx,
         }
     }