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 use ich::Fingerprint;
  20 use rustc_data_structures::fx::FxHashMap;
  21 use rustc_data_structures::indexed_vec::IndexVec;
  22 use rustc_data_structures::stable_hasher::StableHasher;
  23 use serialize::{Encodable, Decodable, Encoder, Decoder};
  24 use std::fmt::Write;
  25 use std::hash::Hash;
  26 use syntax::ast::{self, Ident};
  27 use syntax::ext::hygiene::{Mark, SyntaxContext};
  28 use syntax::symbol::{Symbol, InternedString};
  29 use ty::TyCtxt;
  30 use util::nodemap::NodeMap;
  31
  32 /// The DefPathTable maps DefIndexes to DefKeys and vice versa.
  33 /// Internally the DefPathTable holds a tree of DefKeys, where each DefKey
  34 /// stores the DefIndex of its parent.
  35 /// There is one DefPathTable for each crate.
  36 pub struct DefPathTable {
  37     index_to_key: [Vec<DefKey>; 2],
  38     key_to_index: FxHashMap<DefKey, DefIndex>,
  39     def_path_hashes: [Vec<Fingerprint>; 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             key_to_index: self.key_to_index.clone(),
  50             def_path_hashes: [self.def_path_hashes[0].clone(),
  51                               self.def_path_hashes[1].clone()],
  52         }
  53     }
  54 }
  55
  56 impl DefPathTable {
  57
  58     fn allocate(&mut self,
  59                 key: DefKey,
  60                 def_path_hash: Fingerprint,
  61                 address_space: DefIndexAddressSpace)
  62                 -> DefIndex {
  63         let index = {
  64             let index_to_key = &mut self.index_to_key[address_space.index()];
  65             let index = DefIndex::new(index_to_key.len() + address_space.start());
  66             debug!("DefPathTable::insert() - {:?} <-> {:?}", key, index);
  67             index_to_key.push(key.clone());
  68             index
  69         };
  70         self.key_to_index.insert(key, index);
  71         self.def_path_hashes[address_space.index()].push(def_path_hash);
  72         debug_assert!(self.def_path_hashes[address_space.index()].len() ==
  73                       self.index_to_key[address_space.index()].len());
  74         index
  75     }
  76
  77     #[inline(always)]
  78     pub fn def_key(&self, index: DefIndex) -> DefKey {
  79         self.index_to_key[index.address_space().index()]
  80                          [index.as_array_index()].clone()
  81     }
  82
  83     #[inline(always)]
  84     pub fn def_path_hash(&self, index: DefIndex) -> Fingerprint {
  85         self.def_path_hashes[index.address_space().index()]
  86                             [index.as_array_index()]
  87     }
  88
  89     #[inline(always)]
  90     pub fn def_index_for_def_key(&self, key: &DefKey) -> Option<DefIndex> {
  91         self.key_to_index.get(key).cloned()
  92     }
  93
  94     #[inline(always)]
  95     pub fn contains_key(&self, key: &DefKey) -> bool {
  96         self.key_to_index.contains_key(key)
  97     }
  98
  99     pub fn retrace_path(&self,
 100                         path_data: &[DisambiguatedDefPathData])
 101                         -> Option<DefIndex> {
 102         let root_key = DefKey {
 103             parent: None,
 104             disambiguated_data: DisambiguatedDefPathData {
 105                 data: DefPathData::CrateRoot,
 106                 disambiguator: 0,
 107             },
 108         };
 109
 110         let root_index = self.key_to_index
 111                              .get(&root_key)
 112                              .expect("no root key?")
 113                              .clone();
 114
 115         debug!("retrace_path: root_index={:?}", root_index);
 116
 117         let mut index = root_index;
 118         for data in path_data {
 119             let key = DefKey { parent: Some(index), disambiguated_data: data.clone() };
 120             debug!("retrace_path: key={:?}", key);
 121             match self.key_to_index.get(&key) {
 122                 Some(&i) => index = i,
 123                 None => return None,
 124             }
 125         }
 126
 127         Some(index)
 128     }
 129 }
 130
 131
 132 impl Encodable for DefPathTable {
 133     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 134         // Index to key
 135         self.index_to_key[DefIndexAddressSpace::Low.index()].encode(s)?;
 136         self.index_to_key[DefIndexAddressSpace::High.index()].encode(s)?;
 137
 138         // DefPath hashes
 139         self.def_path_hashes[DefIndexAddressSpace::Low.index()].encode(s)?;
 140         self.def_path_hashes[DefIndexAddressSpace::High.index()].encode(s)?;
 141
 142         Ok(())
 143     }
 144 }
 145
 146 impl Decodable for DefPathTable {
 147     fn decode<D: Decoder>(d: &mut D) -> Result<DefPathTable, D::Error> {
 148         let index_to_key_lo: Vec<DefKey> = Decodable::decode(d)?;
 149         let index_to_key_hi: Vec<DefKey> = Decodable::decode(d)?;
 150
 151         let def_path_hashes_lo: Vec<Fingerprint> = Decodable::decode(d)?;
 152         let def_path_hashes_hi: Vec<Fingerprint> = Decodable::decode(d)?;
 153
 154         let index_to_key = [index_to_key_lo, index_to_key_hi];
 155         let def_path_hashes = [def_path_hashes_lo, def_path_hashes_hi];
 156
 157         let mut key_to_index = FxHashMap();
 158
 159         for space in &[DefIndexAddressSpace::Low, DefIndexAddressSpace::High] {
 160             key_to_index.extend(index_to_key[space.index()]
 161                 .iter()
 162                 .enumerate()
 163                 .map(|(index, key)| (key.clone(),
 164                                      DefIndex::new(index + space.start()))))
 165         }
 166
 167         Ok(DefPathTable {
 168             index_to_key: index_to_key,
 169             key_to_index: key_to_index,
 170             def_path_hashes: def_path_hashes,
 171         })
 172     }
 173 }
 174
 175
 176 /// The definition table containing node definitions.
 177 /// It holds the DefPathTable for local DefIds/DefPaths and it also stores a
 178 /// mapping from NodeIds to local DefIds.
 179 pub struct Definitions {
 180     table: DefPathTable,
 181     node_to_def_index: NodeMap<DefIndex>,
 182     def_index_to_node: [Vec<ast::NodeId>; 2],
 183     pub(super) node_to_hir_id: IndexVec<ast::NodeId, hir::HirId>,
 184     macro_def_scopes: FxHashMap<Mark, DefId>,
 185     expansions: FxHashMap<DefIndex, Mark>,
 186 }
 187
 188 // Unfortunately we have to provide a manual impl of Clone because of the
 189 // fixed-sized array field.
 190 impl Clone for Definitions {
 191     fn clone(&self) -> Self {
 192         Definitions {
 193             table: self.table.clone(),
 194             node_to_def_index: self.node_to_def_index.clone(),
 195             def_index_to_node: [
 196                 self.def_index_to_node[0].clone(),
 197                 self.def_index_to_node[1].clone(),
 198             ],
 199             node_to_hir_id: self.node_to_hir_id.clone(),
 200             macro_def_scopes: self.macro_def_scopes.clone(),
 201             expansions: self.expansions.clone(),
 202         }
 203     }
 204 }
 205
 206 /// A unique identifier that we can use to lookup a definition
 207 /// precisely. It combines the index of the definition's parent (if
 208 /// any) with a `DisambiguatedDefPathData`.
 209 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 210 pub struct DefKey {
 211     /// Parent path.
 212     pub parent: Option<DefIndex>,
 213
 214     /// Identifier of this node.
 215     pub disambiguated_data: DisambiguatedDefPathData,
 216 }
 217
 218 impl DefKey {
 219     fn compute_stable_hash(&self, parent_hash: Fingerprint) -> Fingerprint {
 220         let mut hasher = StableHasher::new();
 221
 222         // We hash a 0u8 here to disambiguate between regular DefPath hashes,
 223         // and the special "root_parent" below.
 224         0u8.hash(&mut hasher);
 225         parent_hash.hash(&mut hasher);
 226         self.disambiguated_data.hash(&mut hasher);
 227         hasher.finish()
 228     }
 229
 230     fn root_parent_stable_hash(crate_name: &str, crate_disambiguator: &str) -> Fingerprint {
 231         let mut hasher = StableHasher::new();
 232         // Disambiguate this from a regular DefPath hash,
 233         // see compute_stable_hash() above.
 234         1u8.hash(&mut hasher);
 235         crate_name.hash(&mut hasher);
 236         crate_disambiguator.hash(&mut hasher);
 237         hasher.finish()
 238     }
 239 }
 240
 241 /// Pair of `DefPathData` and an integer disambiguator. The integer is
 242 /// normally 0, but in the event that there are multiple defs with the
 243 /// same `parent` and `data`, we use this field to disambiguate
 244 /// between them. This introduces some artificial ordering dependency
 245 /// but means that if you have (e.g.) two impls for the same type in
 246 /// the same module, they do get distinct def-ids.
 247 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 248 pub struct DisambiguatedDefPathData {
 249     pub data: DefPathData,
 250     pub disambiguator: u32
 251 }
 252
 253 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 254 pub struct DefPath {
 255     /// the path leading from the crate root to the item
 256     pub data: Vec<DisambiguatedDefPathData>,
 257
 258     /// what krate root is this path relative to?
 259     pub krate: CrateNum,
 260 }
 261
 262 impl DefPath {
 263     pub fn is_local(&self) -> bool {
 264         self.krate == LOCAL_CRATE
 265     }
 266
 267     pub fn make<FN>(krate: CrateNum,
 268                     start_index: DefIndex,
 269                     mut get_key: FN) -> DefPath
 270         where FN: FnMut(DefIndex) -> DefKey
 271     {
 272         let mut data = vec![];
 273         let mut index = Some(start_index);
 274         loop {
 275             debug!("DefPath::make: krate={:?} index={:?}", krate, index);
 276             let p = index.unwrap();
 277             let key = get_key(p);
 278             debug!("DefPath::make: key={:?}", key);
 279             match key.disambiguated_data.data {
 280                 DefPathData::CrateRoot => {
 281                     assert!(key.parent.is_none());
 282                     break;
 283                 }
 284                 _ => {
 285                     data.push(key.disambiguated_data);
 286                     index = key.parent;
 287                 }
 288             }
 289         }
 290         data.reverse();
 291         DefPath { data: data, krate: krate }
 292     }
 293
 294     pub fn to_string(&self, tcx: TyCtxt) -> String {
 295         let mut s = String::with_capacity(self.data.len() * 16);
 296
 297         s.push_str(&tcx.original_crate_name(self.krate).as_str());
 298         s.push_str("/");
 299         s.push_str(&tcx.crate_disambiguator(self.krate).as_str());
 300
 301         for component in &self.data {
 302             write!(s,
 303                    "::{}[{}]",
 304                    component.data.as_interned_str(),
 305                    component.disambiguator)
 306                 .unwrap();
 307         }
 308
 309         s
 310     }
 311
 312     /// Returns a string representation of the DefPath without
 313     /// the crate-prefix. This method is useful if you don't have
 314     /// a TyCtxt available.
 315     pub fn to_string_no_crate(&self) -> String {
 316         let mut s = String::with_capacity(self.data.len() * 16);
 317
 318         for component in &self.data {
 319             write!(s,
 320                    "::{}[{}]",
 321                    component.data.as_interned_str(),
 322                    component.disambiguator)
 323                 .unwrap();
 324         }
 325
 326         s
 327     }
 328 }
 329
 330 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 331 pub enum DefPathData {
 332     // Root: these should only be used for the root nodes, because
 333     // they are treated specially by the `def_path` function.
 334     /// The crate root (marker)
 335     CrateRoot,
 336
 337     // Catch-all for random DefId things like DUMMY_NODE_ID
 338     Misc,
 339
 340     // Different kinds of items and item-like things:
 341     /// An impl
 342     Impl,
 343     /// Something in the type NS
 344     TypeNs(Ident),
 345     /// Something in the value NS
 346     ValueNs(Ident),
 347     /// A module declaration
 348     Module(Ident),
 349     /// A macro rule
 350     MacroDef(Ident),
 351     /// A closure expression
 352     ClosureExpr,
 353
 354     // Subportions of items
 355     /// A type parameter (generic parameter)
 356     TypeParam(Ident),
 357     /// A lifetime definition
 358     LifetimeDef(Ident),
 359     /// A variant of a enum
 360     EnumVariant(Ident),
 361     /// A struct field
 362     Field(Ident),
 363     /// Implicit ctor for a tuple-like struct
 364     StructCtor,
 365     /// Initializer for a const
 366     Initializer,
 367     /// Pattern binding
 368     Binding(Ident),
 369     /// An `impl Trait` type node.
 370     ImplTrait,
 371     /// A `typeof` type node.
 372     Typeof,
 373 }
 374
 375 impl Definitions {
 376     /// Create new empty definition map.
 377     pub fn new() -> Definitions {
 378         Definitions {
 379             table: DefPathTable {
 380                 index_to_key: [vec![], vec![]],
 381                 key_to_index: FxHashMap(),
 382                 def_path_hashes: [vec![], vec![]],
 383             },
 384             node_to_def_index: NodeMap(),
 385             def_index_to_node: [vec![], vec![]],
 386             node_to_hir_id: IndexVec::new(),
 387             macro_def_scopes: FxHashMap(),
 388             expansions: FxHashMap(),
 389         }
 390     }
 391
 392     pub fn def_path_table(&self) -> &DefPathTable {
 393         &self.table
 394     }
 395
 396     /// Get the number of definitions.
 397     pub fn def_index_counts_lo_hi(&self) -> (usize, usize) {
 398         (self.def_index_to_node[DefIndexAddressSpace::Low.index()].len(),
 399          self.def_index_to_node[DefIndexAddressSpace::High.index()].len())
 400     }
 401
 402     pub fn def_key(&self, index: DefIndex) -> DefKey {
 403         self.table.def_key(index)
 404     }
 405
 406     #[inline(always)]
 407     pub fn def_path_hash(&self, index: DefIndex) -> Fingerprint {
 408         self.table.def_path_hash(index)
 409     }
 410
 411     pub fn def_index_for_def_key(&self, key: DefKey) -> Option<DefIndex> {
 412         self.table.def_index_for_def_key(&key)
 413     }
 414
 415     /// Returns the path from the crate root to `index`. The root
 416     /// nodes are not included in the path (i.e., this will be an
 417     /// empty vector for the crate root). For an inlined item, this
 418     /// will be the path of the item in the external crate (but the
 419     /// path will begin with the path to the external crate).
 420     pub fn def_path(&self, index: DefIndex) -> DefPath {
 421         DefPath::make(LOCAL_CRATE, index, |p| self.def_key(p))
 422     }
 423
 424     pub fn opt_def_index(&self, node: ast::NodeId) -> Option<DefIndex> {
 425         self.node_to_def_index.get(&node).cloned()
 426     }
 427
 428     pub fn opt_local_def_id(&self, node: ast::NodeId) -> Option<DefId> {
 429         self.opt_def_index(node).map(DefId::local)
 430     }
 431
 432     pub fn local_def_id(&self, node: ast::NodeId) -> DefId {
 433         self.opt_local_def_id(node).unwrap()
 434     }
 435
 436     pub fn as_local_node_id(&self, def_id: DefId) -> Option<ast::NodeId> {
 437         if def_id.krate == LOCAL_CRATE {
 438             let space_index = def_id.index.address_space().index();
 439             let array_index = def_id.index.as_array_index();
 440             Some(self.def_index_to_node[space_index][array_index])
 441         } else {
 442             None
 443         }
 444     }
 445
 446     pub fn node_to_hir_id(&self, node_id: ast::NodeId) -> hir::HirId {
 447         self.node_to_hir_id[node_id]
 448     }
 449
 450     /// Add a definition with a parent definition.
 451     pub fn create_root_def(&mut self,
 452                            crate_name: &str,
 453                            crate_disambiguator: &str)
 454                            -> DefIndex {
 455         let key = DefKey {
 456             parent: None,
 457             disambiguated_data: DisambiguatedDefPathData {
 458                 data: DefPathData::CrateRoot,
 459                 disambiguator: 0
 460             }
 461         };
 462
 463         let parent_hash = DefKey::root_parent_stable_hash(crate_name,
 464                                                           crate_disambiguator);
 465         let def_path_hash = key.compute_stable_hash(parent_hash);
 466
 467         // Create the definition.
 468         let address_space = super::ITEM_LIKE_SPACE;
 469         let index = self.table.allocate(key, def_path_hash, address_space);
 470         assert!(self.def_index_to_node[address_space.index()].is_empty());
 471         self.def_index_to_node[address_space.index()].push(ast::CRATE_NODE_ID);
 472         self.node_to_def_index.insert(ast::CRATE_NODE_ID, index);
 473
 474         index
 475     }
 476
 477     /// Add a definition with a parent definition.
 478     pub fn create_def_with_parent(&mut self,
 479                                   parent: DefIndex,
 480                                   node_id: ast::NodeId,
 481                                   data: DefPathData,
 482                                   address_space: DefIndexAddressSpace,
 483                                   expansion: Mark)
 484                                   -> DefIndex {
 485         debug!("create_def_with_parent(parent={:?}, node_id={:?}, data={:?})",
 486                parent, node_id, data);
 487
 488         assert!(!self.node_to_def_index.contains_key(&node_id),
 489                 "adding a def'n for node-id {:?} and data {:?} but a previous def'n exists: {:?}",
 490                 node_id,
 491                 data,
 492                 self.table.def_key(self.node_to_def_index[&node_id]));
 493
 494         // The root node must be created with create_root_def()
 495         assert!(data != DefPathData::CrateRoot);
 496
 497         // Find a unique DefKey. This basically means incrementing the disambiguator
 498         // until we get no match.
 499         let mut key = DefKey {
 500             parent: Some(parent),
 501             disambiguated_data: DisambiguatedDefPathData {
 502                 data: data,
 503                 disambiguator: 0
 504             }
 505         };
 506
 507         while self.table.contains_key(&key) {
 508             key.disambiguated_data.disambiguator += 1;
 509         }
 510
 511         let parent_hash = self.table.def_path_hash(parent);
 512         let def_path_hash = key.compute_stable_hash(parent_hash);
 513
 514         debug!("create_def_with_parent: after disambiguation, key = {:?}", key);
 515
 516         // Create the definition.
 517         let index = self.table.allocate(key, def_path_hash, address_space);
 518         assert_eq!(index.as_array_index(),
 519                    self.def_index_to_node[address_space.index()].len());
 520         self.def_index_to_node[address_space.index()].push(node_id);
 521         if expansion.is_modern() {
 522             self.expansions.insert(index, expansion);
 523         }
 524
 525         debug!("create_def_with_parent: def_index_to_node[{:?} <-> {:?}", index, node_id);
 526         self.node_to_def_index.insert(node_id, index);
 527
 528         index
 529     }
 530
 531     /// Initialize the ast::NodeId to HirId mapping once it has been generated during
 532     /// AST to HIR lowering.
 533     pub fn init_node_id_to_hir_id_mapping(&mut self,
 534                                           mapping: IndexVec<ast::NodeId, hir::HirId>) {
 535         assert!(self.node_to_hir_id.is_empty(),
 536                 "Trying initialize NodeId -> HirId mapping twice");
 537         self.node_to_hir_id = mapping;
 538     }
 539
 540     pub fn expansion(&self, index: DefIndex) -> Mark {
 541         self.expansions.get(&index).cloned().unwrap_or(Mark::root())
 542     }
 543
 544     pub fn macro_def_scope(&self, mark: Mark) -> DefId {
 545         self.macro_def_scopes[&mark]
 546     }
 547
 548     pub fn add_macro_def_scope(&mut self, mark: Mark, scope: DefId) {
 549         self.macro_def_scopes.insert(mark, scope);
 550     }
 551 }
 552
 553 impl DefPathData {
 554     pub fn get_opt_ident(&self) -> Option<Ident> {
 555         use self::DefPathData::*;
 556         match *self {
 557             TypeNs(ident) |
 558             ValueNs(ident) |
 559             Module(ident) |
 560             MacroDef(ident) |
 561             TypeParam(ident) |
 562             LifetimeDef(ident) |
 563             EnumVariant(ident) |
 564             Binding(ident) |
 565             Field(ident) => Some(ident),
 566
 567             Impl |
 568             CrateRoot |
 569             Misc |
 570             ClosureExpr |
 571             StructCtor |
 572             Initializer |
 573             ImplTrait |
 574             Typeof => None
 575         }
 576     }
 577
 578     pub fn get_opt_name(&self) -> Option<ast::Name> {
 579         self.get_opt_ident().map(|ident| ident.name)
 580     }
 581
 582     pub fn as_interned_str(&self) -> InternedString {
 583         use self::DefPathData::*;
 584         let s = match *self {
 585             TypeNs(ident) |
 586             ValueNs(ident) |
 587             Module(ident) |
 588             MacroDef(ident) |
 589             TypeParam(ident) |
 590             LifetimeDef(ident) |
 591             EnumVariant(ident) |
 592             Binding(ident) |
 593             Field(ident) => {
 594                 return ident.name.as_str();
 595             }
 596
 597             // note that this does not show up in user printouts
 598             CrateRoot => "{{root}}",
 599
 600             Impl => "{{impl}}",
 601             Misc => "{{?}}",
 602             ClosureExpr => "{{closure}}",
 603             StructCtor => "{{constructor}}",
 604             Initializer => "{{initializer}}",
 605             ImplTrait => "{{impl-Trait}}",
 606             Typeof => "{{typeof}}",
 607         };
 608
 609         Symbol::intern(s).as_str()
 610     }
 611
 612     pub fn to_string(&self) -> String {
 613         self.as_interned_str().to_string()
 614     }
 615 }
 616
 617 impl Eq for DefPathData {}
 618 impl PartialEq for DefPathData {
 619     fn eq(&self, other: &DefPathData) -> bool {
 620         ::std::mem::discriminant(self) == ::std::mem::discriminant(other) &&
 621         self.get_opt_ident() == other.get_opt_ident()
 622     }
 623 }
 624
 625 impl ::std::hash::Hash for DefPathData {
 626     fn hash<H: ::std::hash::Hasher>(&self, hasher: &mut H) {
 627         ::std::mem::discriminant(self).hash(hasher);
 628         if let Some(ident) = self.get_opt_ident() {
 629             if ident.ctxt == SyntaxContext::empty() && ident.name == ident.name.interned() {
 630                 ident.name.as_str().hash(hasher)
 631             } else {
 632                 // FIXME(jseyfried) implement stable hashing for idents with macros 2.0 hygiene info
 633                 ident.hash(hasher)
 634             }
 635         }
 636     }
 637 }