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