Auto merge of #47181 - michaelwoerister:var-len-def-index, r=eddyb

Use DefIndex encoding that works better with on-disk variable length integer representations.

Use the least instead of the most significant bit for representing the address space.

r? @eddyb

10 files changed, 64 insertions, 65 deletions

diff --git a/src/librustc/hir/def_id.rs b/src/librustc/hir/def_id.rs
index 8858023ec1d..637b156ceef 100644
--- a/src/librustc/hir/def_id.rs
+++ b/src/librustc/hir/def_id.rs
@@ -71,27 +71,23 @@ impl serialize::UseSpecializedDecodable for CrateNum {}
 /// 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
+/// At the moment we are allocating the numerical values of DefIndexes from two
+/// address spaces: DefIndexAddressSpace::Low and DefIndexAddressSpace::High.
+/// This allows us to allocate the DefIndexes of all item-likes
+/// (Items, TraitItems, and ImplItems) into one of these spaces 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.
-newtype_index!(DefIndex
-    {
-        ENCODABLE = custom
-        DEBUG_FORMAT = custom,
+/// don't have to care about these address spaces.
 
-        /// The start of the "high" range of DefIndexes.
-        const DEF_INDEX_HI_START = 1 << 31,
+#[derive(Clone, Eq, Ord, PartialOrd, PartialEq, Hash, Copy)]
+pub struct DefIndex(u32);
+
+/// 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);
 
-        /// The crate root is always assigned index 0 by the AST Map code,
-        /// thanks to `NodeCollector::new`.
-        const CRATE_DEF_INDEX = 0,
-    });
 
 impl fmt::Debug for DefIndex {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
@@ -104,40 +100,50 @@ impl fmt::Debug for DefIndex {
 
 impl DefIndex {
     #[inline]
-    pub fn from_u32(x: u32) -> DefIndex {
-        DefIndex(x)
+    pub fn address_space(&self) -> DefIndexAddressSpace {
+        match self.0 & 1 {
+            0 => DefIndexAddressSpace::Low,
+            1 => DefIndexAddressSpace::High,
+            _ => unreachable!()
+        }
     }
 
+    /// Converts this DefIndex into a zero-based array index.
+    /// This index is the offset within the given DefIndexAddressSpace.
     #[inline]
-    pub fn as_usize(&self) -> usize {
-        self.0 as usize
+    pub fn as_array_index(&self) -> usize {
+        (self.0 >> 1) as usize
     }
 
     #[inline]
-    pub fn as_u32(&self) -> u32 {
-        self.0
+    pub fn from_array_index(i: usize, address_space: DefIndexAddressSpace) -> DefIndex {
+        DefIndex::from_raw_u32(((i << 1) | (address_space as usize)) as u32)
     }
 
-    #[inline]
-    pub fn address_space(&self) -> DefIndexAddressSpace {
-        if self.0 < DEF_INDEX_HI_START.0 {
-            DefIndexAddressSpace::Low
-        } else {
-            DefIndexAddressSpace::High
-        }
+    // Proc macros from a proc-macro crate have a kind of virtual DefIndex. This
+    // function maps the index of the macro within the crate (which is also the
+    // index of the macro in the CrateMetadata::proc_macros array) to the
+    // corresponding DefIndex.
+    pub fn from_proc_macro_index(proc_macro_index: usize) -> DefIndex {
+        let def_index = DefIndex::from_array_index(proc_macro_index,
+                                                   DefIndexAddressSpace::High);
+        assert!(def_index != CRATE_DEF_INDEX);
+        def_index
     }
 
-    /// 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
+    // This function is the reverse of from_proc_macro_index() above.
+    pub fn to_proc_macro_index(self: DefIndex) -> usize {
+        self.as_array_index()
     }
 
-    pub fn from_array_index(i: usize, address_space: DefIndexAddressSpace) -> DefIndex {
-        DefIndex::new(address_space.start() + i)
+    // Don't use this if you don't know about the DefIndex encoding.
+    pub fn from_raw_u32(x: u32) -> DefIndex {
+        DefIndex(x)
+    }
+
+    // Don't use this if you don't know about the DefIndex encoding.
+    pub fn as_raw_u32(&self) -> u32 {
+        self.0
     }
 }
 
@@ -155,11 +161,6 @@ impl DefIndexAddressSpace {
     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
diff --git a/src/librustc/hir/map/definitions.rs b/src/librustc/hir/map/definitions.rs
index 7c2f0bc3cef..43cc437e1e7 100644
--- a/src/librustc/hir/map/definitions.rs
+++ b/src/librustc/hir/map/definitions.rs
@@ -19,7 +19,7 @@ use hir::def_id::{CrateNum, DefId, DefIndex, LOCAL_CRATE, DefIndexAddressSpace,
                   CRATE_DEF_INDEX};
 use ich::Fingerprint;
 use rustc_data_structures::fx::FxHashMap;
-use rustc_data_structures::indexed_vec::{IndexVec, Idx};
+use rustc_data_structures::indexed_vec::{IndexVec};
 use rustc_data_structures::stable_hasher::StableHasher;
 use serialize::{Encodable, Decodable, Encoder, Decoder};
 use session::CrateDisambiguator;
@@ -61,7 +61,7 @@ impl DefPathTable {
                 -> 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());
+            let index = DefIndex::from_array_index(index_to_key.len(), address_space);
             debug!("DefPathTable::insert() - {:?} <-> {:?}", key, index);
             index_to_key.push(key);
             index
@@ -89,8 +89,7 @@ impl DefPathTable {
     pub fn add_def_path_hashes_to(&self,
                                   cnum: CrateNum,
                                   out: &mut FxHashMap<DefPathHash, DefId>) {
-        for address_space in &[DefIndexAddressSpace::Low, DefIndexAddressSpace::High] {
-            let start_index = address_space.start();
+        for &address_space in &[DefIndexAddressSpace::Low, DefIndexAddressSpace::High] {
             out.extend(
                 (&self.def_path_hashes[address_space.index()])
                     .iter()
@@ -98,7 +97,7 @@ impl DefPathTable {
                     .map(|(index, &hash)| {
                         let def_id = DefId {
                             krate: cnum,
-                            index: DefIndex::new(index + start_index),
+                            index: DefIndex::from_array_index(index, address_space),
                         };
                         (hash, def_id)
                     })
diff --git a/src/librustc/infer/lexical_region_resolve/graphviz.rs b/src/librustc/infer/lexical_region_resolve/graphviz.rs
index 41209487395..d9d08294334 100644
--- a/src/librustc/infer/lexical_region_resolve/graphviz.rs
+++ b/src/librustc/infer/lexical_region_resolve/graphviz.rs
@@ -19,7 +19,6 @@
 use graphviz as dot;
 
 use hir::def_id::DefIndex;
-use rustc_data_structures::indexed_vec::Idx;
 use ty;
 use middle::free_region::RegionRelations;
 use middle::region;
@@ -68,7 +67,7 @@ pub fn maybe_print_constraints_for<'a, 'gcx, 'tcx>(
     }
 
     let requested_node = env::var("RUST_REGION_GRAPH_NODE")
-        .ok().and_then(|s| s.parse().map(DefIndex::new).ok());
+        .ok().and_then(|s| s.parse().map(DefIndex::from_raw_u32).ok());
 
     if requested_node.is_some() && requested_node != Some(context.index) {
         return;
@@ -102,7 +101,7 @@ pub fn maybe_print_constraints_for<'a, 'gcx, 'tcx>(
             let mut new_str = String::new();
             for c in output_template.chars() {
                 if c == '%' {
-                    new_str.push_str(&context.index.as_usize().to_string());
+                    new_str.push_str(&context.index.as_raw_u32().to_string());
                 } else {
                     new_str.push(c);
                 }
diff --git a/src/librustc/session/mod.rs b/src/librustc/session/mod.rs
index 43dbb8d7e13..3ae7d01823c 100644
--- a/src/librustc/session/mod.rs
+++ b/src/librustc/session/mod.rs
@@ -562,14 +562,14 @@ impl Session {
                                             index: DefIndex)
                                             -> String {
         format!("__rustc_plugin_registrar__{}_{}", disambiguator.to_fingerprint().to_hex(),
-                                                   index.as_usize())
+                                                   index.to_proc_macro_index())
     }
 
     pub fn generate_derive_registrar_symbol(&self, disambiguator: CrateDisambiguator,
                                             index: DefIndex)
                                             -> String {
         format!("__rustc_derive_registrar__{}_{}", disambiguator.to_fingerprint().to_hex(),
-                                                   index.as_usize())
+                                                   index.to_proc_macro_index())
     }
 
     pub fn sysroot<'a>(&'a self) -> &'a Path {
diff --git a/src/librustc_metadata/cstore_impl.rs b/src/librustc_metadata/cstore_impl.rs
index 955648208cd..436ddc32a74 100644
--- a/src/librustc_metadata/cstore_impl.rs
+++ b/src/librustc_metadata/cstore_impl.rs
@@ -463,7 +463,7 @@ impl CrateStore for cstore::CStore {
     fn load_macro_untracked(&self, id: DefId, sess: &Session) -> LoadedMacro {
         let data = self.get_crate_data(id.krate);
         if let Some(ref proc_macros) = data.proc_macros {
-            return LoadedMacro::ProcMacro(proc_macros[id.index.as_usize() - 1].1.clone());
+            return LoadedMacro::ProcMacro(proc_macros[id.index.to_proc_macro_index()].1.clone());
         } else if data.name == "proc_macro" &&
                   self.get_crate_data(id.krate).item_name(id.index) == "quote" {
             let ext = SyntaxExtension::ProcMacro(Box::new(::proc_macro::__internal::Quoter));
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index 7023bd1e6a9..c62b8a692d7 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -18,7 +18,8 @@ use rustc::hir;
 use rustc::middle::cstore::{LinkagePreference, ExternConstBody,
                             ExternBodyNestedBodies};
 use rustc::hir::def::{self, Def, CtorKind};
-use rustc::hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX, LOCAL_CRATE};
+use rustc::hir::def_id::{CrateNum, DefId, DefIndex,
+                         CRATE_DEF_INDEX, LOCAL_CRATE};
 use rustc::ich::Fingerprint;
 use rustc::middle::lang_items;
 use rustc::mir;
@@ -36,7 +37,6 @@ use std::rc::Rc;
 use std::u32;
 
 use rustc_serialize::{Decodable, Decoder, SpecializedDecoder, opaque};
-use rustc_data_structures::indexed_vec::Idx;
 use syntax::attr;
 use syntax::ast::{self, Ident};
 use syntax::codemap;
@@ -264,7 +264,7 @@ impl<'a, 'tcx> SpecializedDecoder<DefId> for DecodeContext<'a, 'tcx> {
 impl<'a, 'tcx> SpecializedDecoder<DefIndex> for DecodeContext<'a, 'tcx> {
     #[inline]
     fn specialized_decode(&mut self) -> Result<DefIndex, Self::Error> {
-        Ok(DefIndex::from_u32(self.read_u32()?))
+        Ok(DefIndex::from_raw_u32(self.read_u32()?))
     }
 }
 
@@ -453,7 +453,7 @@ impl<'a, 'tcx> CrateMetadata {
         if !self.is_proc_macro(index) {
             self.entry(index).kind.to_def(self.local_def_id(index))
         } else {
-            let kind = self.proc_macros.as_ref().unwrap()[index.as_usize() - 1].1.kind();
+            let kind = self.proc_macros.as_ref().unwrap()[index.to_proc_macro_index()].1.kind();
             Some(Def::Macro(self.local_def_id(index), kind))
         }
     }
@@ -634,7 +634,7 @@ impl<'a, 'tcx> CrateMetadata {
                     let def = Def::Macro(
                         DefId {
                             krate: self.cnum,
-                            index: DefIndex::new(id + 1)
+                            index: DefIndex::from_proc_macro_index(id),
                         },
                         ext.kind()
                     );
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index aead706823e..d52a31d50cd 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -140,7 +140,7 @@ impl<'a, 'tcx> SpecializedEncoder<DefId> for EncodeContext<'a, 'tcx> {
 impl<'a, 'tcx> SpecializedEncoder<DefIndex> for EncodeContext<'a, 'tcx> {
     #[inline]
     fn specialized_encode(&mut self, def_index: &DefIndex) -> Result<(), Self::Error> {
-        self.emit_u32(def_index.as_u32())
+        self.emit_u32(def_index.as_raw_u32())
     }
 }
 
diff --git a/src/librustc_metadata/index.rs b/src/librustc_metadata/index.rs
index 69fbc935461..157b8385a69 100644
--- a/src/librustc_metadata/index.rs
+++ b/src/librustc_metadata/index.rs
@@ -74,10 +74,9 @@ impl<'tcx> LazySeq<Index> {
     #[inline(never)]
     pub fn lookup(&self, bytes: &[u8], def_index: DefIndex) -> Option<Lazy<Entry<'tcx>>> {
         let words = &bytes_to_words(&bytes[self.position..])[..self.len];
-        let index = def_index.as_usize();
 
         debug!("Index::lookup: index={:?} words.len={:?}",
-               index,
+               def_index,
                words.len());
 
         let positions = match def_index.address_space() {
diff --git a/src/librustc_resolve/macros.rs b/src/librustc_resolve/macros.rs
index 7c2ea4a68b0..2b0c839152c 100644
--- a/src/librustc_resolve/macros.rs
+++ b/src/librustc_resolve/macros.rs
@@ -13,8 +13,8 @@ use {Module, ModuleKind, NameBinding, NameBindingKind, PathResult};
 use Namespace::{self, MacroNS};
 use build_reduced_graph::BuildReducedGraphVisitor;
 use resolve_imports::ImportResolver;
-use rustc_data_structures::indexed_vec::Idx;
-use rustc::hir::def_id::{DefId, BUILTIN_MACROS_CRATE, CRATE_DEF_INDEX, DefIndex};
+use rustc::hir::def_id::{DefId, BUILTIN_MACROS_CRATE, CRATE_DEF_INDEX, DefIndex,
+                         DefIndexAddressSpace};
 use rustc::hir::def::{Def, Export};
 use rustc::hir::map::{self, DefCollector};
 use rustc::{ty, lint};
@@ -188,7 +188,8 @@ impl<'a> base::Resolver for Resolver<'a> {
     fn add_builtin(&mut self, ident: ast::Ident, ext: Rc<SyntaxExtension>) {
         let def_id = DefId {
             krate: BUILTIN_MACROS_CRATE,
-            index: DefIndex::new(self.macro_map.len()),
+            index: DefIndex::from_array_index(self.macro_map.len(),
+                                              DefIndexAddressSpace::Low),
         };
         let kind = ext.kind();
         self.macro_map.insert(def_id, ext);
diff --git a/src/librustc_save_analysis/lib.rs b/src/librustc_save_analysis/lib.rs
index b282837750e..2e494fdfad8 100644
--- a/src/librustc_save_analysis/lib.rs
+++ b/src/librustc_save_analysis/lib.rs
@@ -1123,7 +1123,7 @@ fn generated_code(span: Span) -> bool {
 fn id_from_def_id(id: DefId) -> rls_data::Id {
     rls_data::Id {
         krate: id.krate.as_u32(),
-        index: id.index.as_u32(),
+        index: id.index.as_raw_u32(),
     }
 }