src/librustc/hir/map/definitions.rs

   1 //! For each definition, we track the following data. A definition
   2 //! here is defined somewhat circularly as "something with a `DefId`",
   3 //! but it generally corresponds to things like structs, enums, etc.
   4 //! There are also some rather random cases (like const initializer
   5 //! expressions) that are mostly just leftovers.
   6
   7 use crate::hir;
   8 use crate::hir::def_id::{CrateNum, DefId, DefIndex, LOCAL_CRATE, CRATE_DEF_INDEX};
   9 use crate::ich::Fingerprint;
  10 use rustc_data_structures::fx::FxHashMap;
  11 use rustc_data_structures::indexed_vec::{IndexVec};
  12 use rustc_data_structures::stable_hasher::StableHasher;
  13 use serialize::{Encodable, Decodable, Encoder, Decoder};
  14 use crate::session::CrateDisambiguator;
  15 use std::borrow::Borrow;
  16 use std::fmt::Write;
  17 use std::hash::Hash;
  18 use syntax::ast;
  19 use syntax::ext::hygiene::Mark;
  20 use syntax::symbol::{Symbol, sym, InternedString};
  21 use syntax_pos::{Span, DUMMY_SP};
  22 use crate::util::nodemap::NodeMap;
  23
  24 /// The DefPathTable maps DefIndexes to DefKeys and vice versa.
  25 /// Internally the DefPathTable holds a tree of DefKeys, where each DefKey
  26 /// stores the DefIndex of its parent.
  27 /// There is one DefPathTable for each crate.
  28 #[derive(Clone, Default)]
  29 pub struct DefPathTable {
  30     index_to_key: Vec<DefKey>,
  31     def_path_hashes: Vec<DefPathHash>,
  32 }
  33
  34 impl DefPathTable {
  35
  36     fn allocate(&mut self,
  37                 key: DefKey,
  38                 def_path_hash: DefPathHash)
  39                 -> DefIndex {
  40         let index = {
  41             let index = DefIndex::from(self.index_to_key.len());
  42             debug!("DefPathTable::insert() - {:?} <-> {:?}", key, index);
  43             self.index_to_key.push(key);
  44             index
  45         };
  46         self.def_path_hashes.push(def_path_hash);
  47         debug_assert!(self.def_path_hashes.len() == self.index_to_key.len());
  48         index
  49     }
  50
  51     pub fn next_id(&self) -> DefIndex {
  52         DefIndex::from(self.index_to_key.len())
  53     }
  54
  55     #[inline(always)]
  56     pub fn def_key(&self, index: DefIndex) -> DefKey {
  57         self.index_to_key[index.index()].clone()
  58     }
  59
  60     #[inline(always)]
  61     pub fn def_path_hash(&self, index: DefIndex) -> DefPathHash {
  62         let ret = self.def_path_hashes[index.index()];
  63         debug!("def_path_hash({:?}) = {:?}", index, ret);
  64         return ret
  65     }
  66
  67     pub fn add_def_path_hashes_to(&self,
  68                                   cnum: CrateNum,
  69                                   out: &mut FxHashMap<DefPathHash, DefId>) {
  70         out.extend(
  71             self.def_path_hashes
  72                 .iter()
  73                 .enumerate()
  74                 .map(|(index, &hash)| {
  75                     let def_id = DefId {
  76                         krate: cnum,
  77                         index: DefIndex::from(index),
  78                     };
  79                     (hash, def_id)
  80                 })
  81         );
  82     }
  83
  84     pub fn size(&self) -> usize {
  85         self.index_to_key.len()
  86     }
  87 }
  88
  89
  90 impl Encodable for DefPathTable {
  91     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
  92         // Index to key
  93         self.index_to_key.encode(s)?;
  94
  95         // DefPath hashes
  96         self.def_path_hashes.encode(s)?;
  97
  98         Ok(())
  99     }
 100 }
 101
 102 impl Decodable for DefPathTable {
 103     fn decode<D: Decoder>(d: &mut D) -> Result<DefPathTable, D::Error> {
 104         Ok(DefPathTable {
 105             index_to_key: Decodable::decode(d)?,
 106             def_path_hashes : Decodable::decode(d)?,
 107         })
 108     }
 109 }
 110
 111 /// The definition table containing node definitions.
 112 /// It holds the `DefPathTable` for local `DefId`s/`DefPath`s and it also stores a
 113 /// mapping from `NodeId`s to local `DefId`s.
 114 #[derive(Clone, Default)]
 115 pub struct Definitions {
 116     table: DefPathTable,
 117     node_to_def_index: NodeMap<DefIndex>,
 118     def_index_to_node: Vec<ast::NodeId>,
 119     pub(super) node_to_hir_id: IndexVec<ast::NodeId, hir::HirId>,
 120     /// If `Mark` is an ID of some macro expansion,
 121     /// then `DefId` is the normal module (`mod`) in which the expanded macro was defined.
 122     parent_modules_of_macro_defs: FxHashMap<Mark, DefId>,
 123     /// Item with a given `DefIndex` was defined during macro expansion with ID `Mark`.
 124     expansions_that_defined: FxHashMap<DefIndex, Mark>,
 125     next_disambiguator: FxHashMap<(DefIndex, DefPathData), u32>,
 126     def_index_to_span: FxHashMap<DefIndex, Span>,
 127 }
 128
 129 /// A unique identifier that we can use to lookup a definition
 130 /// precisely. It combines the index of the definition's parent (if
 131 /// any) with a `DisambiguatedDefPathData`.
 132 #[derive(Clone, PartialEq, Debug, Hash, RustcEncodable, RustcDecodable)]
 133 pub struct DefKey {
 134     /// The parent path.
 135     pub parent: Option<DefIndex>,
 136
 137     /// The identifier of this node.
 138     pub disambiguated_data: DisambiguatedDefPathData,
 139 }
 140
 141 impl DefKey {
 142     fn compute_stable_hash(&self, parent_hash: DefPathHash) -> DefPathHash {
 143         let mut hasher = StableHasher::new();
 144
 145         // We hash a 0u8 here to disambiguate between regular DefPath hashes,
 146         // and the special "root_parent" below.
 147         0u8.hash(&mut hasher);
 148         parent_hash.hash(&mut hasher);
 149
 150         let DisambiguatedDefPathData {
 151             ref data,
 152             disambiguator,
 153         } = self.disambiguated_data;
 154
 155         ::std::mem::discriminant(data).hash(&mut hasher);
 156         if let Some(name) = data.get_opt_name() {
 157             name.hash(&mut hasher);
 158         }
 159
 160         disambiguator.hash(&mut hasher);
 161
 162         DefPathHash(hasher.finish())
 163     }
 164
 165     fn root_parent_stable_hash(crate_name: &str,
 166                                crate_disambiguator: CrateDisambiguator)
 167                                -> DefPathHash {
 168         let mut hasher = StableHasher::new();
 169         // Disambiguate this from a regular DefPath hash,
 170         // see compute_stable_hash() above.
 171         1u8.hash(&mut hasher);
 172         crate_name.hash(&mut hasher);
 173         crate_disambiguator.hash(&mut hasher);
 174         DefPathHash(hasher.finish())
 175     }
 176 }
 177
 178 /// A pair of `DefPathData` and an integer disambiguator. The integer is
 179 /// normally 0, but in the event that there are multiple defs with the
 180 /// same `parent` and `data`, we use this field to disambiguate
 181 /// between them. This introduces some artificial ordering dependency
 182 /// but means that if you have (e.g.) two impls for the same type in
 183 /// the same module, they do get distinct `DefId`s.
 184 #[derive(Clone, PartialEq, Debug, Hash, RustcEncodable, RustcDecodable)]
 185 pub struct DisambiguatedDefPathData {
 186     pub data: DefPathData,
 187     pub disambiguator: u32
 188 }
 189
 190 #[derive(Clone, Debug, Hash, RustcEncodable, RustcDecodable)]
 191 pub struct DefPath {
 192     /// The path leading from the crate root to the item.
 193     pub data: Vec<DisambiguatedDefPathData>,
 194
 195     /// The crate root this path is relative to.
 196     pub krate: CrateNum,
 197 }
 198
 199 impl DefPath {
 200     pub fn is_local(&self) -> bool {
 201         self.krate == LOCAL_CRATE
 202     }
 203
 204     pub fn make<FN>(krate: CrateNum,
 205                     start_index: DefIndex,
 206                     mut get_key: FN) -> DefPath
 207         where FN: FnMut(DefIndex) -> DefKey
 208     {
 209         let mut data = vec![];
 210         let mut index = Some(start_index);
 211         loop {
 212             debug!("DefPath::make: krate={:?} index={:?}", krate, index);
 213             let p = index.unwrap();
 214             let key = get_key(p);
 215             debug!("DefPath::make: key={:?}", key);
 216             match key.disambiguated_data.data {
 217                 DefPathData::CrateRoot => {
 218                     assert!(key.parent.is_none());
 219                     break;
 220                 }
 221                 _ => {
 222                     data.push(key.disambiguated_data);
 223                     index = key.parent;
 224                 }
 225             }
 226         }
 227         data.reverse();
 228         DefPath { data: data, krate: krate }
 229     }
 230
 231     /// Returns a string representation of the `DefPath` without
 232     /// the crate-prefix. This method is useful if you don't have
 233     /// a `TyCtxt` available.
 234     pub fn to_string_no_crate(&self) -> String {
 235         let mut s = String::with_capacity(self.data.len() * 16);
 236
 237         for component in &self.data {
 238             write!(s,
 239                    "::{}[{}]",
 240                    component.data.as_interned_str(),
 241                    component.disambiguator)
 242                 .unwrap();
 243         }
 244
 245         s
 246     }
 247
 248     /// Returns a filename-friendly string for the `DefPath`, with the
 249     /// crate-prefix.
 250     pub fn to_string_friendly<F>(&self, crate_imported_name: F) -> String
 251         where F: FnOnce(CrateNum) -> Symbol
 252     {
 253         let crate_name_str = crate_imported_name(self.krate).as_str();
 254         let mut s = String::with_capacity(crate_name_str.len() + self.data.len() * 16);
 255
 256         write!(s, "::{}", crate_name_str).unwrap();
 257
 258         for component in &self.data {
 259             if component.disambiguator == 0 {
 260                 write!(s, "::{}", component.data.as_interned_str()).unwrap();
 261             } else {
 262                 write!(s,
 263                        "{}[{}]",
 264                        component.data.as_interned_str(),
 265                        component.disambiguator)
 266                     .unwrap();
 267             }
 268         }
 269
 270         s
 271     }
 272
 273     /// Returns a filename-friendly string of the `DefPath`, without
 274     /// the crate-prefix. This method is useful if you don't have
 275     /// a `TyCtxt` available.
 276     pub fn to_filename_friendly_no_crate(&self) -> String {
 277         let mut s = String::with_capacity(self.data.len() * 16);
 278
 279         let mut opt_delimiter = None;
 280         for component in &self.data {
 281             opt_delimiter.map(|d| s.push(d));
 282             opt_delimiter = Some('-');
 283             if component.disambiguator == 0 {
 284                 write!(s, "{}", component.data.as_interned_str()).unwrap();
 285             } else {
 286                 write!(s,
 287                        "{}[{}]",
 288                        component.data.as_interned_str(),
 289                        component.disambiguator)
 290                     .unwrap();
 291             }
 292         }
 293         s
 294     }
 295 }
 296
 297 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 298 pub enum DefPathData {
 299     // Root: these should only be used for the root nodes, because
 300     // they are treated specially by the `def_path` function.
 301     /// The crate root (marker)
 302     CrateRoot,
 303     // Catch-all for random DefId things like DUMMY_NODE_ID
 304     Misc,
 305     // Different kinds of items and item-like things:
 306     /// An impl
 307     Impl,
 308     /// Something in the type NS
 309     TypeNs(InternedString),
 310     /// Something in the value NS
 311     ValueNs(InternedString),
 312     /// Something in the macro NS
 313     MacroNs(InternedString),
 314     /// Something in the lifetime NS
 315     LifetimeNs(InternedString),
 316     /// A closure expression
 317     ClosureExpr,
 318     // Subportions of items
 319     /// Implicit ctor for a unit or tuple-like struct or enum variant.
 320     Ctor,
 321     /// A constant expression (see {ast,hir}::AnonConst).
 322     AnonConst,
 323     /// An `impl Trait` type node
 324     ImplTrait,
 325     /// GlobalMetaData identifies a piece of crate metadata that is global to
 326     /// a whole crate (as opposed to just one item). GlobalMetaData components
 327     /// are only supposed to show up right below the crate root.
 328     GlobalMetaData(InternedString),
 329 }
 330
 331 #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug,
 332          RustcEncodable, RustcDecodable)]
 333 pub struct DefPathHash(pub Fingerprint);
 334
 335 impl_stable_hash_for!(tuple_struct DefPathHash { fingerprint });
 336
 337 impl Borrow<Fingerprint> for DefPathHash {
 338     #[inline]
 339     fn borrow(&self) -> &Fingerprint {
 340         &self.0
 341     }
 342 }
 343
 344 impl Definitions {
 345     pub fn def_path_table(&self) -> &DefPathTable {
 346         &self.table
 347     }
 348
 349     /// Gets the number of definitions.
 350     pub fn def_index_count(&self) -> usize {
 351         self.table.index_to_key.len()
 352     }
 353
 354     pub fn def_key(&self, index: DefIndex) -> DefKey {
 355         self.table.def_key(index)
 356     }
 357
 358     #[inline(always)]
 359     pub fn def_path_hash(&self, index: DefIndex) -> DefPathHash {
 360         self.table.def_path_hash(index)
 361     }
 362
 363     /// Returns the path from the crate root to `index`. The root
 364     /// nodes are not included in the path (i.e., this will be an
 365     /// empty vector for the crate root). For an inlined item, this
 366     /// will be the path of the item in the external crate (but the
 367     /// path will begin with the path to the external crate).
 368     pub fn def_path(&self, index: DefIndex) -> DefPath {
 369         DefPath::make(LOCAL_CRATE, index, |p| self.def_key(p))
 370     }
 371
 372     #[inline]
 373     pub fn opt_def_index(&self, node: ast::NodeId) -> Option<DefIndex> {
 374         self.node_to_def_index.get(&node).cloned()
 375     }
 376
 377     #[inline]
 378     pub fn opt_local_def_id(&self, node: ast::NodeId) -> Option<DefId> {
 379         self.opt_def_index(node).map(DefId::local)
 380     }
 381
 382     #[inline]
 383     pub fn local_def_id(&self, node: ast::NodeId) -> DefId {
 384         self.opt_local_def_id(node).unwrap()
 385     }
 386
 387     #[inline]
 388     pub fn as_local_node_id(&self, def_id: DefId) -> Option<ast::NodeId> {
 389         if def_id.krate == LOCAL_CRATE {
 390             let node_id = self.def_index_to_node[def_id.index.index()];
 391             if node_id != ast::DUMMY_NODE_ID {
 392                 return Some(node_id);
 393             }
 394         }
 395         None
 396     }
 397
 398     // FIXME(@ljedrz): replace the NodeId variant
 399     #[inline]
 400     pub fn as_local_hir_id(&self, def_id: DefId) -> Option<hir::HirId> {
 401         if def_id.krate == LOCAL_CRATE {
 402             let hir_id = self.def_index_to_hir_id(def_id.index);
 403             if hir_id != hir::DUMMY_HIR_ID {
 404                 Some(hir_id)
 405             } else {
 406                 None
 407             }
 408         } else {
 409             None
 410         }
 411     }
 412
 413     #[inline]
 414     pub fn node_to_hir_id(&self, node_id: ast::NodeId) -> hir::HirId {
 415         self.node_to_hir_id[node_id]
 416     }
 417
 418     #[inline]
 419     pub fn def_index_to_hir_id(&self, def_index: DefIndex) -> hir::HirId {
 420         let node_id = self.def_index_to_node[def_index.index()];
 421         self.node_to_hir_id[node_id]
 422     }
 423
 424     /// Retrieves the span of the given `DefId` if `DefId` is in the local crate, the span exists
 425     /// and it's not `DUMMY_SP`.
 426     #[inline]
 427     pub fn opt_span(&self, def_id: DefId) -> Option<Span> {
 428         if def_id.krate == LOCAL_CRATE {
 429             self.def_index_to_span.get(&def_id.index).cloned()
 430         } else {
 431             None
 432         }
 433     }
 434
 435     /// Adds a root definition (no parent) and a few other reserved definitions.
 436     ///
 437     /// After the initial definitions are created the first `FIRST_FREE_DEF_INDEX` indexes
 438     /// are taken, so the "user" indexes will be allocated starting with `FIRST_FREE_DEF_INDEX`
 439     /// in ascending order.
 440     pub fn create_root_def(&mut self,
 441                            crate_name: &str,
 442                            crate_disambiguator: CrateDisambiguator)
 443                            -> DefIndex {
 444         let key = DefKey {
 445             parent: None,
 446             disambiguated_data: DisambiguatedDefPathData {
 447                 data: DefPathData::CrateRoot,
 448                 disambiguator: 0
 449             }
 450         };
 451
 452         let parent_hash = DefKey::root_parent_stable_hash(crate_name,
 453                                                           crate_disambiguator);
 454         let def_path_hash = key.compute_stable_hash(parent_hash);
 455
 456         // Create the definition.
 457         let root_index = self.table.allocate(key, def_path_hash);
 458         assert_eq!(root_index, CRATE_DEF_INDEX);
 459         assert!(self.def_index_to_node.is_empty());
 460         self.def_index_to_node.push(ast::CRATE_NODE_ID);
 461         self.node_to_def_index.insert(ast::CRATE_NODE_ID, root_index);
 462
 463         // Allocate some other DefIndices that always must exist.
 464         GlobalMetaDataKind::allocate_def_indices(self);
 465
 466         root_index
 467     }
 468
 469     /// Add a definition with a parent definition.
 470     pub fn create_def_with_parent(&mut self,
 471                                   parent: DefIndex,
 472                                   node_id: ast::NodeId,
 473                                   data: DefPathData,
 474                                   expansion: Mark,
 475                                   span: Span)
 476                                   -> DefIndex {
 477         debug!("create_def_with_parent(parent={:?}, node_id={:?}, data={:?})",
 478                parent, node_id, data);
 479
 480         assert!(!self.node_to_def_index.contains_key(&node_id),
 481                 "adding a def'n for node-id {:?} and data {:?} but a previous def'n exists: {:?}",
 482                 node_id,
 483                 data,
 484                 self.table.def_key(self.node_to_def_index[&node_id]));
 485
 486         // The root node must be created with create_root_def()
 487         assert!(data != DefPathData::CrateRoot);
 488
 489         // Find the next free disambiguator for this key.
 490         let disambiguator = {
 491             let next_disamb = self.next_disambiguator.entry((parent, data.clone())).or_insert(0);
 492             let disambiguator = *next_disamb;
 493             *next_disamb = next_disamb.checked_add(1).expect("disambiguator overflow");
 494             disambiguator
 495         };
 496
 497         let key = DefKey {
 498             parent: Some(parent),
 499             disambiguated_data: DisambiguatedDefPathData {
 500                 data, disambiguator
 501             }
 502         };
 503
 504         let parent_hash = self.table.def_path_hash(parent);
 505         let def_path_hash = key.compute_stable_hash(parent_hash);
 506
 507         debug!("create_def_with_parent: after disambiguation, key = {:?}", key);
 508
 509         // Create the definition.
 510         let index = self.table.allocate(key, def_path_hash);
 511         assert_eq!(index.index(), self.def_index_to_node.len());
 512         self.def_index_to_node.push(node_id);
 513
 514         // Some things for which we allocate DefIndices don't correspond to
 515         // anything in the AST, so they don't have a NodeId. For these cases
 516         // we don't need a mapping from NodeId to DefIndex.
 517         if node_id != ast::DUMMY_NODE_ID {
 518             debug!("create_def_with_parent: def_index_to_node[{:?} <-> {:?}", index, node_id);
 519             self.node_to_def_index.insert(node_id, index);
 520         }
 521
 522         if expansion != Mark::root() {
 523             self.expansions_that_defined.insert(index, expansion);
 524         }
 525
 526         // The span is added if it isn't dummy
 527         if !span.is_dummy() {
 528             self.def_index_to_span.insert(index, span);
 529         }
 530
 531         index
 532     }
 533
 534     /// Initialize the `ast::NodeId` to `HirId` mapping once it has been generated during
 535     /// AST to HIR lowering.
 536     pub fn init_node_id_to_hir_id_mapping(&mut self,
 537                                           mapping: IndexVec<ast::NodeId, hir::HirId>) {
 538         assert!(self.node_to_hir_id.is_empty(),
 539                 "Trying initialize NodeId -> HirId mapping twice");
 540         self.node_to_hir_id = mapping;
 541     }
 542
 543     pub fn expansion_that_defined(&self, index: DefIndex) -> Mark {
 544         self.expansions_that_defined.get(&index).cloned().unwrap_or(Mark::root())
 545     }
 546
 547     pub fn parent_module_of_macro_def(&self, mark: Mark) -> DefId {
 548         self.parent_modules_of_macro_defs[&mark]
 549     }
 550
 551     pub fn add_parent_module_of_macro_def(&mut self, mark: Mark, module: DefId) {
 552         self.parent_modules_of_macro_defs.insert(mark, module);
 553     }
 554 }
 555
 556 impl DefPathData {
 557     pub fn get_opt_name(&self) -> Option<InternedString> {
 558         use self::DefPathData::*;
 559         match *self {
 560             TypeNs(name) |
 561             ValueNs(name) |
 562             MacroNs(name) |
 563             LifetimeNs(name) |
 564             GlobalMetaData(name) => Some(name),
 565
 566             Impl |
 567             CrateRoot |
 568             Misc |
 569             ClosureExpr |
 570             Ctor |
 571             AnonConst |
 572             ImplTrait => None
 573         }
 574     }
 575
 576     pub fn as_interned_str(&self) -> InternedString {
 577         use self::DefPathData::*;
 578         let s = match *self {
 579             TypeNs(name) |
 580             ValueNs(name) |
 581             MacroNs(name) |
 582             LifetimeNs(name) |
 583             GlobalMetaData(name) => {
 584                 return name
 585             }
 586             // note that this does not show up in user printouts
 587             CrateRoot => sym::double_braced_crate,
 588             Impl => sym::double_braced_impl,
 589             Misc => sym::double_braced_misc,
 590             ClosureExpr => sym::double_braced_closure,
 591             Ctor => sym::double_braced_constructor,
 592             AnonConst => sym::double_braced_constant,
 593             ImplTrait => sym::double_braced_opaque,
 594         };
 595
 596         s.as_interned_str()
 597     }
 598
 599     pub fn to_string(&self) -> String {
 600         self.as_interned_str().to_string()
 601     }
 602 }
 603
 604 macro_rules! count {
 605     () => (0usize);
 606     ( $x:tt $($xs:tt)* ) => (1usize + count!($($xs)*));
 607 }
 608
 609 // We define the GlobalMetaDataKind enum with this macro because we want to
 610 // make sure that we exhaustively iterate over all variants when registering
 611 // the corresponding DefIndices in the DefTable.
 612 macro_rules! define_global_metadata_kind {
 613     (pub enum GlobalMetaDataKind {
 614         $($variant:ident),*
 615     }) => (
 616         #[derive(Clone, Copy, Debug, Hash, RustcEncodable, RustcDecodable)]
 617         pub enum GlobalMetaDataKind {
 618             $($variant),*
 619         }
 620
 621         pub const FIRST_FREE_DEF_INDEX: usize = 1 + count!($($variant)*);
 622
 623         impl GlobalMetaDataKind {
 624             fn allocate_def_indices(definitions: &mut Definitions) {
 625                 $({
 626                     let instance = GlobalMetaDataKind::$variant;
 627                     definitions.create_def_with_parent(
 628                         CRATE_DEF_INDEX,
 629                         ast::DUMMY_NODE_ID,
 630                         DefPathData::GlobalMetaData(instance.name().as_interned_str()),
 631                         Mark::root(),
 632                         DUMMY_SP
 633                     );
 634
 635                     // Make sure calling def_index does not crash.
 636                     instance.def_index(&definitions.table);
 637                 })*
 638             }
 639
 640             pub fn def_index(&self, def_path_table: &DefPathTable) -> DefIndex {
 641                 let def_key = DefKey {
 642                     parent: Some(CRATE_DEF_INDEX),
 643                     disambiguated_data: DisambiguatedDefPathData {
 644                         data: DefPathData::GlobalMetaData(self.name().as_interned_str()),
 645                         disambiguator: 0,
 646                     }
 647                 };
 648
 649                 // These DefKeys are all right after the root,
 650                 // so a linear search is fine.
 651                 let index = def_path_table.index_to_key
 652                                           .iter()
 653                                           .position(|k| *k == def_key)
 654                                           .unwrap();
 655
 656                 DefIndex::from(index)
 657             }
 658
 659             fn name(&self) -> Symbol {
 660
 661                 let string = match *self {
 662                     $(
 663                         GlobalMetaDataKind::$variant => {
 664                             concat!("{{GlobalMetaData::", stringify!($variant), "}}")
 665                         }
 666                     )*
 667                 };
 668
 669                 Symbol::intern(string)
 670             }
 671         }
 672     )
 673 }
 674
 675 define_global_metadata_kind!(pub enum GlobalMetaDataKind {
 676     Krate,
 677     CrateDeps,
 678     DylibDependencyFormats,
 679     LangItems,
 680     LangItemsMissing,
 681     NativeLibraries,
 682     SourceMap,
 683     Impls,
 684     ExportedSymbols
 685 });