src/librustc/hir/map/definitions.rs

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