refactor rustc_metadata to use CamelCase names and IndexVec

9 files changed, 106 insertions, 97 deletions

diff --git a/src/librustc_data_structures/indexed_vec.rs b/src/librustc_data_structures/indexed_vec.rs
index b3918f1e4bc..91234631499 100644
--- a/src/librustc_data_structures/indexed_vec.rs
+++ b/src/librustc_data_structures/indexed_vec.rs
@@ -15,6 +15,7 @@ use std::marker::PhantomData;
 use std::ops::{Index, IndexMut, Range};
 use std::fmt;
 use std::vec;
+use std::u32;
 
 use rustc_serialize as serialize;
 
@@ -31,6 +32,11 @@ impl Idx for usize {
     fn index(self) -> usize { self }
 }
 
+impl Idx for u32 {
+    fn new(idx: usize) -> Self { assert!(idx <= u32::MAX as usize); idx as u32 }
+    fn index(self) -> usize { self as usize }
+}
+
 #[derive(Clone)]
 pub struct IndexVec<I: Idx, T> {
     pub raw: Vec<T>,
diff --git a/src/librustc_metadata/Cargo.toml b/src/librustc_metadata/Cargo.toml
index 11896e17630..2d3302c2eef 100644
--- a/src/librustc_metadata/Cargo.toml
+++ b/src/librustc_metadata/Cargo.toml
@@ -16,6 +16,7 @@ rustc = { path = "../librustc" }
 rustc_back = { path = "../librustc_back" }
 rustc_bitflags = { path = "../librustc_bitflags" }
 rustc_const_math = { path = "../librustc_const_math" }
+rustc_data_structures = { path = "../librustc_data_structures" }
 rustc_errors = { path = "../librustc_errors" }
 rustc_llvm = { path = "../librustc_llvm" }
 serialize = { path = "../libserialize" }
diff --git a/src/librustc_metadata/astencode.rs b/src/librustc_metadata/astencode.rs
index dc37bdf6322..532c263139b 100644
--- a/src/librustc_metadata/astencode.rs
+++ b/src/librustc_metadata/astencode.rs
@@ -62,7 +62,7 @@ use rustc_serialize::{Encodable, EncoderHelpers};
 
 struct DecodeContext<'a, 'b, 'tcx: 'a> {
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
-    cdata: &'b cstore::crate_metadata,
+    cdata: &'b cstore::CrateMetadata,
     from_id_range: IdRange,
     to_id_range: IdRange,
     // Cache the last used filemap for translating spans as an optimization.
@@ -123,7 +123,7 @@ impl<'a, 'b, 'c, 'tcx> ast_map::FoldOps for &'a DecodeContext<'b, 'c, 'tcx> {
 
 /// Decodes an item from its AST in the cdata's metadata and adds it to the
 /// ast-map.
-pub fn decode_inlined_item<'a, 'tcx>(cdata: &cstore::crate_metadata,
+pub fn decode_inlined_item<'a, 'tcx>(cdata: &cstore::CrateMetadata,
                                      tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                      parent_def_path: ast_map::DefPath,
                                      parent_did: DefId,
@@ -248,7 +248,7 @@ impl<S:serialize::Encoder> def_id_encoder_helpers for S
 trait def_id_decoder_helpers {
     fn read_def_id(&mut self, dcx: &DecodeContext) -> DefId;
     fn read_def_id_nodcx(&mut self,
-                         cdata: &cstore::crate_metadata) -> DefId;
+                         cdata: &cstore::CrateMetadata) -> DefId;
 }
 
 impl<D:serialize::Decoder> def_id_decoder_helpers for D
@@ -260,7 +260,7 @@ impl<D:serialize::Decoder> def_id_decoder_helpers for D
     }
 
     fn read_def_id_nodcx(&mut self,
-                         cdata: &cstore::crate_metadata)
+                         cdata: &cstore::CrateMetadata)
                          -> DefId {
         let did: DefId = Decodable::decode(self).unwrap();
         decoder::translate_def_id(cdata, did)
@@ -860,17 +860,17 @@ trait rbml_decoder_decoder_helpers<'tcx> {
     // Versions of the type reading functions that don't need the full
     // DecodeContext.
     fn read_ty_nodcx<'a>(&mut self, tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                         cdata: &cstore::crate_metadata) -> Ty<'tcx>;
+                         cdata: &cstore::CrateMetadata) -> Ty<'tcx>;
     fn read_tys_nodcx<'a>(&mut self, tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                          cdata: &cstore::crate_metadata) -> Vec<Ty<'tcx>>;
+                          cdata: &cstore::CrateMetadata) -> Vec<Ty<'tcx>>;
     fn read_substs_nodcx<'a>(&mut self, tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                             cdata: &cstore::crate_metadata)
+                             cdata: &cstore::CrateMetadata)
                              -> subst::Substs<'tcx>;
 }
 
 impl<'a, 'tcx> rbml_decoder_decoder_helpers<'tcx> for reader::Decoder<'a> {
     fn read_ty_nodcx<'b>(&mut self, tcx: TyCtxt<'b, 'tcx, 'tcx>,
-                         cdata: &cstore::crate_metadata)
+                         cdata: &cstore::CrateMetadata)
                          -> Ty<'tcx> {
         self.read_opaque(|_, doc| {
             Ok(
@@ -881,7 +881,7 @@ impl<'a, 'tcx> rbml_decoder_decoder_helpers<'tcx> for reader::Decoder<'a> {
     }
 
     fn read_tys_nodcx<'b>(&mut self, tcx: TyCtxt<'b, 'tcx, 'tcx>,
-                          cdata: &cstore::crate_metadata) -> Vec<Ty<'tcx>> {
+                          cdata: &cstore::CrateMetadata) -> Vec<Ty<'tcx>> {
         self.read_to_vec(|this| Ok(this.read_ty_nodcx(tcx, cdata)) )
             .unwrap()
             .into_iter()
@@ -889,7 +889,7 @@ impl<'a, 'tcx> rbml_decoder_decoder_helpers<'tcx> for reader::Decoder<'a> {
     }
 
     fn read_substs_nodcx<'b>(&mut self, tcx: TyCtxt<'b, 'tcx, 'tcx>,
-                             cdata: &cstore::crate_metadata)
+                             cdata: &cstore::CrateMetadata)
                              -> subst::Substs<'tcx>
     {
         self.read_opaque(|_, doc| {
diff --git a/src/librustc_metadata/creader.rs b/src/librustc_metadata/creader.rs
index 2ccac91ae91..f97030a30f8 100644
--- a/src/librustc_metadata/creader.rs
+++ b/src/librustc_metadata/creader.rs
@@ -24,7 +24,7 @@ use rustc::session::{config, Session};
 use rustc::session::config::PanicStrategy;
 use rustc::session::search_paths::PathKind;
 use rustc::middle::cstore::{CrateStore, validate_crate_name, ExternCrate};
-use rustc::util::nodemap::FnvHashMap;
+use rustc::util::nodemap::{FnvHashMap, FnvHashSet};
 use rustc::hir::map as hir_map;
 
 use std::cell::{RefCell, Cell};
@@ -132,7 +132,7 @@ struct ExtensionCrate {
 }
 
 enum PMDSource {
-    Registered(Rc<cstore::crate_metadata>),
+    Registered(Rc<cstore::CrateMetadata>),
     Owned(MetadataBlob),
 }
 
@@ -294,7 +294,7 @@ impl<'a> CrateReader<'a> {
                       span: Span,
                       lib: loader::Library,
                       explicitly_linked: bool)
-                      -> (ast::CrateNum, Rc<cstore::crate_metadata>,
+                      -> (ast::CrateNum, Rc<cstore::CrateMetadata>,
                           cstore::CrateSource) {
         self.verify_rustc_version(name, span, &lib.metadata);
         self.verify_no_symbol_conflicts(span, &lib.metadata);
@@ -318,10 +318,10 @@ impl<'a> CrateReader<'a> {
 
         let loader::Library { dylib, rlib, metadata } = lib;
 
-        let cnum_map = self.resolve_crate_deps(root, metadata.as_slice(), span);
+        let cnum_map = self.resolve_crate_deps(root, metadata.as_slice(), cnum, span);
         let staged_api = self.is_staged_api(metadata.as_slice());
 
-        let cmeta = Rc::new(cstore::crate_metadata {
+        let cmeta = Rc::new(cstore::CrateMetadata {
             name: name.to_string(),
             extern_crate: Cell::new(None),
             index: decoder::load_index(metadata.as_slice()),
@@ -364,7 +364,7 @@ impl<'a> CrateReader<'a> {
                      span: Span,
                      kind: PathKind,
                      explicitly_linked: bool)
-                     -> (ast::CrateNum, Rc<cstore::crate_metadata>, cstore::CrateSource) {
+                     -> (ast::CrateNum, Rc<cstore::CrateMetadata>, cstore::CrateSource) {
         let result = match self.existing_match(name, hash, kind) {
             Some(cnum) => LoadResult::Previous(cnum),
             None => {
@@ -438,8 +438,11 @@ impl<'a> CrateReader<'a> {
 
     fn update_extern_crate(&mut self,
                            cnum: ast::CrateNum,
-                           mut extern_crate: ExternCrate)
+                           mut extern_crate: ExternCrate,
+                           visited: &mut FnvHashSet<(ast::CrateNum, bool)>)
     {
+        if !visited.insert((cnum, extern_crate.direct)) { return }
+
         let cmeta = self.cstore.get_crate_data(cnum);
         let old_extern_crate = cmeta.extern_crate.get();
 
@@ -458,11 +461,10 @@ impl<'a> CrateReader<'a> {
         }
 
         cmeta.extern_crate.set(Some(extern_crate));
-
         // Propagate the extern crate info to dependencies.
         extern_crate.direct = false;
-        for &dep_cnum in cmeta.cnum_map.borrow().values() {
-            self.update_extern_crate(dep_cnum, extern_crate);
+        for &dep_cnum in cmeta.cnum_map.borrow().iter() {
+            self.update_extern_crate(dep_cnum, extern_crate, visited);
         }
     }
 
@@ -470,12 +472,13 @@ impl<'a> CrateReader<'a> {
     fn resolve_crate_deps(&mut self,
                           root: &Option<CratePaths>,
                           cdata: &[u8],
-                          span : Span)
-                          -> cstore::cnum_map {
+                          krate: ast::CrateNum,
+                          span: Span)
+                          -> cstore::CrateNumMap {
         debug!("resolving deps of external crate");
         // The map from crate numbers in the crate we're resolving to local crate
         // numbers
-        decoder::get_crate_deps(cdata).iter().map(|dep| {
+        let map: FnvHashMap<_, _> = decoder::get_crate_deps(cdata).iter().map(|dep| {
             debug!("resolving dep crate {} hash: `{}`", dep.name, dep.hash);
             let (local_cnum, _, _) = self.resolve_crate(root,
                                                         &dep.name,
@@ -485,7 +488,13 @@ impl<'a> CrateReader<'a> {
                                                         PathKind::Dependency,
                                                         dep.explicitly_linked);
             (dep.cnum, local_cnum)
-        }).collect()
+        }).collect();
+
+        let max_cnum = map.values().cloned().max().unwrap_or(0);
+
+        // we map 0 and all other holes in the map to our parent crate. The "additional"
+        // self-dependencies should be harmless.
+        (0..max_cnum+1).map(|cnum| map.get(&cnum).cloned().unwrap_or(krate)).collect()
     }
 
     fn read_extension_crate(&mut self, span: Span, info: &CrateInfo) -> ExtensionCrate {
@@ -826,7 +835,7 @@ impl<'a> CrateReader<'a> {
     fn inject_dependency_if(&self,
                             krate: ast::CrateNum,
                             what: &str,
-                            needs_dep: &Fn(&cstore::crate_metadata) -> bool) {
+                            needs_dep: &Fn(&cstore::CrateMetadata) -> bool) {
         // don't perform this validation if the session has errors, as one of
         // those errors may indicate a circular dependency which could cause
         // this to stack overflow.
@@ -837,7 +846,17 @@ impl<'a> CrateReader<'a> {
         // Before we inject any dependencies, make sure we don't inject a
         // circular dependency by validating that this crate doesn't
         // transitively depend on any crates satisfying `needs_dep`.
-        validate(self, krate, krate, what, needs_dep);
+        for dep in self.cstore.crate_dependencies_in_rpo(krate) {
+            let data = self.cstore.get_crate_data(dep);
+            if needs_dep(&data) {
+                self.sess.err(&format!("the crate `{}` cannot depend \
+                                        on a crate that needs {}, but \
+                                        it depends on `{}`",
+                                       self.cstore.get_crate_data(krate).name(),
+                                       what,
+                                       data.name()));
+            }
+        }
 
         // All crates satisfying `needs_dep` do not explicitly depend on the
         // crate provided for this compile, but in order for this compilation to
@@ -849,32 +868,8 @@ impl<'a> CrateReader<'a> {
             }
 
             info!("injecting a dep from {} to {}", cnum, krate);
-            let mut cnum_map = data.cnum_map.borrow_mut();
-            let remote_cnum = cnum_map.len() + 1;
-            let prev = cnum_map.insert(remote_cnum as ast::CrateNum, krate);
-            assert!(prev.is_none());
+            data.cnum_map.borrow_mut().push(krate);
         });
-
-        fn validate(me: &CrateReader,
-                    krate: ast::CrateNum,
-                    root: ast::CrateNum,
-                    what: &str,
-                    needs_dep: &Fn(&cstore::crate_metadata) -> bool) {
-            let data = me.cstore.get_crate_data(krate);
-            if needs_dep(&data) {
-                let krate_name = data.name();
-                let data = me.cstore.get_crate_data(root);
-                let root_name = data.name();
-                me.sess.err(&format!("the crate `{}` cannot depend \
-                                      on a crate that needs {}, but \
-                                      it depends on `{}`", root_name, what,
-                                      krate_name));
-            }
-
-            for (_, &dep) in data.cnum_map.borrow().iter() {
-                validate(me, dep, root, what, needs_dep);
-            }
-        }
     }
 }
 
@@ -948,7 +943,8 @@ impl<'a> LocalCrateReader<'a> {
                                                          span: i.span,
                                                          direct: true,
                                                          path_len: len,
-                                                     });
+                                                     },
+                                                     &mut FnvHashSet());
                     self.cstore.add_extern_mod_stmt_cnum(info.id, cnum);
                 }
             }
diff --git a/src/librustc_metadata/cstore.rs b/src/librustc_metadata/cstore.rs
index e89f428c96f..7573929ab2c 100644
--- a/src/librustc_metadata/cstore.rs
+++ b/src/librustc_metadata/cstore.rs
@@ -26,6 +26,7 @@ use rustc::hir::map::DefKey;
 use rustc::hir::svh::Svh;
 use rustc::middle::cstore::{ExternCrate};
 use rustc::session::config::PanicStrategy;
+use rustc_data_structures::indexed_vec::IndexVec;
 use rustc::util::nodemap::{FnvHashMap, NodeMap, NodeSet, DefIdMap};
 
 use std::cell::{RefCell, Ref, Cell};
@@ -46,7 +47,7 @@ pub use middle::cstore::{CrateSource, LinkMeta};
 // local crate numbers (as generated during this session). Each external
 // crate may refer to types in other external crates, and each has their
 // own crate numbers.
-pub type cnum_map = FnvHashMap<ast::CrateNum, ast::CrateNum>;
+pub type CrateNumMap = IndexVec<ast::CrateNum, ast::CrateNum>;
 
 pub enum MetadataBlob {
     MetadataVec(Bytes),
@@ -64,7 +65,7 @@ pub struct ImportedFileMap {
     pub translated_filemap: Rc<syntax_pos::FileMap>
 }
 
-pub struct crate_metadata {
+pub struct CrateMetadata {
     pub name: String,
 
     /// Information about the extern crate that caused this crate to
@@ -73,7 +74,7 @@ pub struct crate_metadata {
     pub extern_crate: Cell<Option<ExternCrate>>,
 
     pub data: MetadataBlob,
-    pub cnum_map: RefCell<cnum_map>,
+    pub cnum_map: RefCell<CrateNumMap>,
     pub cnum: ast::CrateNum,
     pub codemap_import_info: RefCell<Vec<ImportedFileMap>>,
     pub staged_api: bool,
@@ -97,7 +98,7 @@ pub struct crate_metadata {
 
 pub struct CStore {
     pub dep_graph: DepGraph,
-    metas: RefCell<FnvHashMap<ast::CrateNum, Rc<crate_metadata>>>,
+    metas: RefCell<FnvHashMap<ast::CrateNum, Rc<CrateMetadata>>>,
     /// Map from NodeId's of local extern crate statements to crate numbers
     extern_mod_crate_map: RefCell<NodeMap<ast::CrateNum>>,
     used_crate_sources: RefCell<Vec<CrateSource>>,
@@ -128,7 +129,7 @@ impl CStore {
         self.metas.borrow().len() as ast::CrateNum + 1
     }
 
-    pub fn get_crate_data(&self, cnum: ast::CrateNum) -> Rc<crate_metadata> {
+    pub fn get_crate_data(&self, cnum: ast::CrateNum) -> Rc<CrateMetadata> {
         self.metas.borrow().get(&cnum).unwrap().clone()
     }
 
@@ -137,12 +138,12 @@ impl CStore {
         decoder::get_crate_hash(cdata.data())
     }
 
-    pub fn set_crate_data(&self, cnum: ast::CrateNum, data: Rc<crate_metadata>) {
+    pub fn set_crate_data(&self, cnum: ast::CrateNum, data: Rc<CrateMetadata>) {
         self.metas.borrow_mut().insert(cnum, data);
     }
 
     pub fn iter_crate_data<I>(&self, mut i: I) where
-        I: FnMut(ast::CrateNum, &Rc<crate_metadata>),
+        I: FnMut(ast::CrateNum, &Rc<CrateMetadata>),
     {
         for (&k, v) in self.metas.borrow().iter() {
             i(k, v);
@@ -151,7 +152,7 @@ impl CStore {
 
     /// Like `iter_crate_data`, but passes source paths (if available) as well.
     pub fn iter_crate_data_origins<I>(&self, mut i: I) where
-        I: FnMut(ast::CrateNum, &crate_metadata, Option<CrateSource>),
+        I: FnMut(ast::CrateNum, &CrateMetadata, Option<CrateSource>),
     {
         for (&k, v) in self.metas.borrow().iter() {
             let origin = self.opt_used_crate_source(k);
@@ -182,6 +183,30 @@ impl CStore {
         self.statically_included_foreign_items.borrow_mut().clear();
     }
 
+    pub fn crate_dependencies_in_rpo(&self, krate: ast::CrateNum) -> Vec<ast::CrateNum>
+    {
+        let mut ordering = Vec::new();
+        self.push_dependencies_in_postorder(&mut ordering, krate);
+        ordering.reverse();
+        ordering
+    }
+
+    pub fn push_dependencies_in_postorder(&self,
+                                          ordering: &mut Vec<ast::CrateNum>,
+                                          krate: ast::CrateNum)
+    {
+        if ordering.contains(&krate) { return }
+
+        let data = self.get_crate_data(krate);
+        for &dep in data.cnum_map.borrow().iter() {
+            if dep != krate {
+                self.push_dependencies_in_postorder(ordering, dep);
+            }
+        }
+
+        ordering.push(krate);
+    }
+
     // This method is used when generating the command line to pass through to
     // system linker. The linker expects undefined symbols on the left of the
     // command line to be defined in libraries on the right, not the other way
@@ -194,17 +219,8 @@ impl CStore {
     pub fn do_get_used_crates(&self, prefer: LinkagePreference)
                               -> Vec<(ast::CrateNum, Option<PathBuf>)> {
         let mut ordering = Vec::new();
-        fn visit(cstore: &CStore, cnum: ast::CrateNum,
-                 ordering: &mut Vec<ast::CrateNum>) {
-            if ordering.contains(&cnum) { return }
-            let meta = cstore.get_crate_data(cnum);
-            for (_, &dep) in meta.cnum_map.borrow().iter() {
-                visit(cstore, dep, ordering);
-            }
-            ordering.push(cnum);
-        }
         for (&num, _) in self.metas.borrow().iter() {
-            visit(self, num, &mut ordering);
+            self.push_dependencies_in_postorder(&mut ordering, num);
         }
         info!("topological ordering: {:?}", ordering);
         ordering.reverse();
@@ -264,7 +280,7 @@ impl CStore {
     }
 }
 
-impl crate_metadata {
+impl CrateMetadata {
     pub fn data<'a>(&'a self) -> &'a [u8] { self.data.as_slice() }
     pub fn name(&self) -> &str { decoder::get_crate_name(self.data()) }
     pub fn hash(&self) -> Svh { decoder::get_crate_hash(self.data()) }
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index 3efdf36acd9..0a59c152ca3 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -15,7 +15,7 @@
 use self::Family::*;
 
 use astencode::decode_inlined_item;
-use cstore::{self, crate_metadata};
+use cstore::{self, CrateMetadata};
 use common::*;
 use def_key;
 use encoder::def_to_u64;
@@ -30,7 +30,7 @@ use rustc::util::nodemap::FnvHashMap;
 use rustc::hir;
 use rustc::session::config::PanicStrategy;
 
-use middle::cstore::{LOCAL_CRATE, FoundAst, InlinedItem, LinkagePreference};
+use middle::cstore::{FoundAst, InlinedItem, LinkagePreference};
 use middle::cstore::{DefLike, DlDef, DlField, DlImpl, tls};
 use rustc::hir::def::Def;
 use rustc::hir::def_id::{DefId, DefIndex};
@@ -61,9 +61,9 @@ use syntax::print::pprust;
 use syntax::ptr::P;
 use syntax_pos::{self, Span, BytePos, NO_EXPANSION};
 
-pub type Cmd<'a> = &'a crate_metadata;
+pub type Cmd<'a> = &'a CrateMetadata;
 
-impl crate_metadata {
+impl CrateMetadata {
     fn get_item(&self, item_id: DefIndex) -> Option<rbml::Doc> {
         self.index.lookup_item(self.data(), item_id).map(|pos| {
             reader::doc_at(self.data(), pos as usize).unwrap().doc
@@ -663,7 +663,7 @@ fn each_child_of_item_or_crate<F, G>(intr: Rc<IdentInterner>,
                                      mut get_crate_data: G,
                                      mut callback: F) where
     F: FnMut(DefLike, ast::Name, ty::Visibility),
-    G: FnMut(ast::CrateNum) -> Rc<crate_metadata>,
+    G: FnMut(ast::CrateNum) -> Rc<CrateMetadata>,
 {
     // Iterate over all children.
     for child_info_doc in reader::tagged_docs(item_doc, tag_mod_child) {
@@ -758,7 +758,7 @@ pub fn each_child_of_item<F, G>(intr: Rc<IdentInterner>,
                                get_crate_data: G,
                                callback: F) where
     F: FnMut(DefLike, ast::Name, ty::Visibility),
-    G: FnMut(ast::CrateNum) -> Rc<crate_metadata>,
+    G: FnMut(ast::CrateNum) -> Rc<CrateMetadata>,
 {
     // Find the item.
     let item_doc = match cdata.get_item(id) {
@@ -779,7 +779,7 @@ pub fn each_top_level_item_of_crate<F, G>(intr: Rc<IdentInterner>,
                                           get_crate_data: G,
                                           callback: F) where
     F: FnMut(DefLike, ast::Name, ty::Visibility),
-    G: FnMut(ast::CrateNum) -> Rc<crate_metadata>,
+    G: FnMut(ast::CrateNum) -> Rc<CrateMetadata>,
 {
     let root_doc = rbml::Doc::new(cdata.data());
     let misc_info_doc = reader::get_doc(root_doc, tag_misc_info);
@@ -1348,25 +1348,16 @@ pub fn translate_def_id(cdata: Cmd, did: DefId) -> DefId {
         return DefId { krate: cdata.cnum, index: did.index };
     }
 
-    match cdata.cnum_map.borrow().get(&did.krate) {
-        Some(&n) => {
-            DefId {
-                krate: n,
-                index: did.index,
-            }
-        }
-        None => bug!("didn't find a crate in the cnum_map")
+    DefId {
+        krate: cdata.cnum_map.borrow()[did.krate],
+        index: did.index
     }
 }
 
 // Translate a DefId from the current compilation environment to a DefId
 // for an external crate.
 fn reverse_translate_def_id(cdata: Cmd, did: DefId) -> Option<DefId> {
-    if did.krate == cdata.cnum {
-        return Some(DefId { krate: LOCAL_CRATE, index: did.index });
-    }
-
-    for (&local, &global) in cdata.cnum_map.borrow().iter() {
+    for (local, &global) in cdata.cnum_map.borrow().iter_enumerated() {
         if global == did.krate {
             return Some(DefId { krate: local, index: did.index });
         }
@@ -1545,10 +1536,7 @@ pub fn get_dylib_dependency_formats(cdata: Cmd)
         let cnum = spec.split(':').nth(0).unwrap();
         let link = spec.split(':').nth(1).unwrap();
         let cnum: ast::CrateNum = cnum.parse().unwrap();
-        let cnum = match cdata.cnum_map.borrow().get(&cnum) {
-            Some(&n) => n,
-            None => bug!("didn't find a crate in the cnum_map")
-        };
+        let cnum = cdata.cnum_map.borrow()[cnum];
         result.push((cnum, if link == "d" {
             LinkagePreference::RequireDynamic
         } else {
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index c23ad6d5f07..b2f52100da4 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -1505,7 +1505,7 @@ fn encode_polarity(rbml_w: &mut Encoder, polarity: hir::ImplPolarity) {
 
 fn encode_crate_deps(rbml_w: &mut Encoder, cstore: &cstore::CStore) {
     fn get_ordered_deps(cstore: &cstore::CStore)
-                        -> Vec<(CrateNum, Rc<cstore::crate_metadata>)> {
+                        -> Vec<(CrateNum, Rc<cstore::CrateMetadata>)> {
         // Pull the cnums and name,vers,hash out of cstore
         let mut deps = Vec::new();
         cstore.iter_crate_data(|cnum, val| {
@@ -1736,7 +1736,7 @@ fn encode_reachable(ecx: &EncodeContext, rbml_w: &mut Encoder) {
 }
 
 fn encode_crate_dep(rbml_w: &mut Encoder,
-                    dep: &cstore::crate_metadata) {
+                    dep: &cstore::CrateMetadata) {
     rbml_w.start_tag(tag_crate_dep);
     rbml_w.wr_tagged_str(tag_crate_dep_crate_name, &dep.name());
     let hash = decoder::get_crate_hash(dep.data());
diff --git a/src/librustc_metadata/lib.rs b/src/librustc_metadata/lib.rs
index 1cf7282e9e9..cd92493e3db 100644
--- a/src/librustc_metadata/lib.rs
+++ b/src/librustc_metadata/lib.rs
@@ -36,6 +36,7 @@ extern crate rustc_errors as errors;
 
 #[macro_use]
 extern crate rustc;
+extern crate rustc_data_structures;
 extern crate rustc_back;
 extern crate rustc_llvm;
 extern crate rustc_const_math;
diff --git a/src/rustc/Cargo.lock b/src/rustc/Cargo.lock
index 9c6ed991df8..c9d1eb39f0a 100644
--- a/src/rustc/Cargo.lock
+++ b/src/rustc/Cargo.lock
@@ -213,6 +213,7 @@ dependencies = [
  "rustc_back 0.0.0",
  "rustc_bitflags 0.0.0",
  "rustc_const_math 0.0.0",
+ "rustc_data_structures 0.0.0",
  "rustc_errors 0.0.0",
  "rustc_llvm 0.0.0",
  "serialize 0.0.0",