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