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