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::def_id::{CrateNum, DefId, DefIndex, LOCAL_CRATE};
  18 use rustc_data_structures::fx::FxHashMap;
  19 use rustc_data_structures::stable_hasher::StableHasher;
  20 use serialize::{Encodable, Decodable, Encoder, Decoder};
  21 use std::fmt::Write;
  22 use std::hash::{Hash, Hasher};
  23 use syntax::ast;
  24 use syntax::symbol::{Symbol, InternedString};
  25 use ty::TyCtxt;
  26 use util::nodemap::NodeMap;
  27
  28 /// The DefPathTable maps DefIndexes to DefKeys and vice versa.
  29 /// Internally the DefPathTable holds a tree of DefKeys, where each DefKey
  30 /// stores the DefIndex of its parent.
  31 /// There is one DefPathTable for each crate.
  32 #[derive(Clone)]
  33 pub struct DefPathTable {
  34     index_to_key: Vec<DefKey>,
  35     key_to_index: FxHashMap<DefKey, DefIndex>,
  36 }
  37
  38 impl DefPathTable {
  39     fn insert(&mut self, key: DefKey) -> DefIndex {
  40         let index = DefIndex::new(self.index_to_key.len());
  41         debug!("DefPathTable::insert() - {:?} <-> {:?}", key, index);
  42         self.index_to_key.push(key.clone());
  43         self.key_to_index.insert(key, index);
  44         index
  45     }
  46
  47     #[inline(always)]
  48     pub fn def_key(&self, index: DefIndex) -> DefKey {
  49         self.index_to_key[index.as_usize()].clone()
  50     }
  51
  52     #[inline(always)]
  53     pub fn def_index_for_def_key(&self, key: &DefKey) -> Option<DefIndex> {
  54         self.key_to_index.get(key).cloned()
  55     }
  56
  57     #[inline(always)]
  58     pub fn contains_key(&self, key: &DefKey) -> bool {
  59         self.key_to_index.contains_key(key)
  60     }
  61
  62     pub fn retrace_path(&self,
  63                         path_data: &[DisambiguatedDefPathData])
  64                         -> Option<DefIndex> {
  65         let root_key = DefKey {
  66             parent: None,
  67             disambiguated_data: DisambiguatedDefPathData {
  68                 data: DefPathData::CrateRoot,
  69                 disambiguator: 0,
  70             },
  71         };
  72
  73         let root_index = self.key_to_index
  74                              .get(&root_key)
  75                              .expect("no root key?")
  76                              .clone();
  77
  78         debug!("retrace_path: root_index={:?}", root_index);
  79
  80         let mut index = root_index;
  81         for data in path_data {
  82             let key = DefKey { parent: Some(index), disambiguated_data: data.clone() };
  83             debug!("retrace_path: key={:?}", key);
  84             match self.key_to_index.get(&key) {
  85                 Some(&i) => index = i,
  86                 None => return None,
  87             }
  88         }
  89
  90         Some(index)
  91     }
  92 }
  93
  94
  95 impl Encodable for DefPathTable {
  96     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
  97         self.index_to_key.encode(s)
  98     }
  99 }
 100
 101 impl Decodable for DefPathTable {
 102     fn decode<D: Decoder>(d: &mut D) -> Result<DefPathTable, D::Error> {
 103         let index_to_key: Vec<DefKey> = Decodable::decode(d)?;
 104         let key_to_index = index_to_key.iter()
 105                                        .enumerate()
 106                                        .map(|(index, key)| (key.clone(), DefIndex::new(index)))
 107                                        .collect();
 108         Ok(DefPathTable {
 109             index_to_key: index_to_key,
 110             key_to_index: key_to_index,
 111         })
 112     }
 113 }
 114
 115
 116 /// The definition table containing node definitions.
 117 /// It holds the DefPathTable for local DefIds/DefPaths and it also stores a
 118 /// mapping from NodeIds to local DefIds.
 119 #[derive(Clone)]
 120 pub struct Definitions {
 121     table: DefPathTable,
 122     node_to_def_index: NodeMap<DefIndex>,
 123     def_index_to_node: Vec<ast::NodeId>,
 124 }
 125
 126 /// A unique identifier that we can use to lookup a definition
 127 /// precisely. It combines the index of the definition's parent (if
 128 /// any) with a `DisambiguatedDefPathData`.
 129 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 130 pub struct DefKey {
 131     /// Parent path.
 132     pub parent: Option<DefIndex>,
 133
 134     /// Identifier of this node.
 135     pub disambiguated_data: DisambiguatedDefPathData,
 136 }
 137
 138 /// Pair of `DefPathData` and an integer disambiguator. The integer is
 139 /// normally 0, but in the event that there are multiple defs with the
 140 /// same `parent` and `data`, we use this field to disambiguate
 141 /// between them. This introduces some artificial ordering dependency
 142 /// but means that if you have (e.g.) two impls for the same type in
 143 /// the same module, they do get distinct def-ids.
 144 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 145 pub struct DisambiguatedDefPathData {
 146     pub data: DefPathData,
 147     pub disambiguator: u32
 148 }
 149
 150 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 151 pub struct DefPath {
 152     /// the path leading from the crate root to the item
 153     pub data: Vec<DisambiguatedDefPathData>,
 154
 155     /// what krate root is this path relative to?
 156     pub krate: CrateNum,
 157 }
 158
 159 impl DefPath {
 160     pub fn is_local(&self) -> bool {
 161         self.krate == LOCAL_CRATE
 162     }
 163
 164     pub fn make<FN>(krate: CrateNum,
 165                     start_index: DefIndex,
 166                     mut get_key: FN) -> DefPath
 167         where FN: FnMut(DefIndex) -> DefKey
 168     {
 169         let mut data = vec![];
 170         let mut index = Some(start_index);
 171         loop {
 172             debug!("DefPath::make: krate={:?} index={:?}", krate, index);
 173             let p = index.unwrap();
 174             let key = get_key(p);
 175             debug!("DefPath::make: key={:?}", key);
 176             match key.disambiguated_data.data {
 177                 DefPathData::CrateRoot => {
 178                     assert!(key.parent.is_none());
 179                     break;
 180                 }
 181                 _ => {
 182                     data.push(key.disambiguated_data);
 183                     index = key.parent;
 184                 }
 185             }
 186         }
 187         data.reverse();
 188         DefPath { data: data, krate: krate }
 189     }
 190
 191     pub fn to_string(&self, tcx: TyCtxt) -> String {
 192         let mut s = String::with_capacity(self.data.len() * 16);
 193
 194         s.push_str(&tcx.original_crate_name(self.krate).as_str());
 195         s.push_str("/");
 196         s.push_str(&tcx.crate_disambiguator(self.krate).as_str());
 197
 198         for component in &self.data {
 199             write!(s,
 200                    "::{}[{}]",
 201                    component.data.as_interned_str(),
 202                    component.disambiguator)
 203                 .unwrap();
 204         }
 205
 206         s
 207     }
 208
 209     pub fn deterministic_hash(&self, tcx: TyCtxt) -> u64 {
 210         debug!("deterministic_hash({:?})", self);
 211         let mut state = StableHasher::new();
 212         self.deterministic_hash_to(tcx, &mut state);
 213         state.finish()
 214     }
 215
 216     pub fn deterministic_hash_to<H: Hasher>(&self, tcx: TyCtxt, state: &mut H) {
 217         tcx.original_crate_name(self.krate).as_str().hash(state);
 218         tcx.crate_disambiguator(self.krate).as_str().hash(state);
 219         self.data.hash(state);
 220     }
 221 }
 222
 223 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 224 pub enum DefPathData {
 225     // Root: these should only be used for the root nodes, because
 226     // they are treated specially by the `def_path` function.
 227     /// The crate root (marker)
 228     CrateRoot,
 229
 230     // Catch-all for random DefId things like DUMMY_NODE_ID
 231     Misc,
 232
 233     // Different kinds of items and item-like things:
 234     /// An impl
 235     Impl,
 236     /// Something in the type NS
 237     TypeNs(InternedString),
 238     /// Something in the value NS
 239     ValueNs(InternedString),
 240     /// A module declaration
 241     Module(InternedString),
 242     /// A macro rule
 243     MacroDef(InternedString),
 244     /// A closure expression
 245     ClosureExpr,
 246
 247     // Subportions of items
 248     /// A type parameter (generic parameter)
 249     TypeParam(InternedString),
 250     /// A lifetime definition
 251     LifetimeDef(InternedString),
 252     /// A variant of a enum
 253     EnumVariant(InternedString),
 254     /// A struct field
 255     Field(InternedString),
 256     /// Implicit ctor for a tuple-like struct
 257     StructCtor,
 258     /// Initializer for a const
 259     Initializer,
 260     /// Pattern binding
 261     Binding(InternedString),
 262     /// An `impl Trait` type node.
 263     ImplTrait
 264 }
 265
 266 impl Definitions {
 267     /// Create new empty definition map.
 268     pub fn new() -> Definitions {
 269         Definitions {
 270             table: DefPathTable {
 271                 index_to_key: vec![],
 272                 key_to_index: FxHashMap(),
 273             },
 274             node_to_def_index: NodeMap(),
 275             def_index_to_node: vec![],
 276         }
 277     }
 278
 279     pub fn def_path_table(&self) -> &DefPathTable {
 280         &self.table
 281     }
 282
 283     /// Get the number of definitions.
 284     pub fn len(&self) -> usize {
 285         self.def_index_to_node.len()
 286     }
 287
 288     pub fn def_key(&self, index: DefIndex) -> DefKey {
 289         self.table.def_key(index)
 290     }
 291
 292     pub fn def_index_for_def_key(&self, key: DefKey) -> Option<DefIndex> {
 293         self.table.def_index_for_def_key(&key)
 294     }
 295
 296     /// Returns the path from the crate root to `index`. The root
 297     /// nodes are not included in the path (i.e., this will be an
 298     /// empty vector for the crate root). For an inlined item, this
 299     /// will be the path of the item in the external crate (but the
 300     /// path will begin with the path to the external crate).
 301     pub fn def_path(&self, index: DefIndex) -> DefPath {
 302         DefPath::make(LOCAL_CRATE, index, |p| self.def_key(p))
 303     }
 304
 305     pub fn opt_def_index(&self, node: ast::NodeId) -> Option<DefIndex> {
 306         self.node_to_def_index.get(&node).cloned()
 307     }
 308
 309     pub fn opt_local_def_id(&self, node: ast::NodeId) -> Option<DefId> {
 310         self.opt_def_index(node).map(DefId::local)
 311     }
 312
 313     pub fn local_def_id(&self, node: ast::NodeId) -> DefId {
 314         self.opt_local_def_id(node).unwrap()
 315     }
 316
 317     pub fn as_local_node_id(&self, def_id: DefId) -> Option<ast::NodeId> {
 318         if def_id.krate == LOCAL_CRATE {
 319             assert!(def_id.index.as_usize() < self.def_index_to_node.len());
 320             Some(self.def_index_to_node[def_id.index.as_usize()])
 321         } else {
 322             None
 323         }
 324     }
 325
 326     /// Add a definition with a parent definition.
 327     pub fn create_def_with_parent(&mut self,
 328                                   parent: Option<DefIndex>,
 329                                   node_id: ast::NodeId,
 330                                   data: DefPathData)
 331                                   -> DefIndex {
 332         debug!("create_def_with_parent(parent={:?}, node_id={:?}, data={:?})",
 333                parent, node_id, data);
 334
 335         assert!(!self.node_to_def_index.contains_key(&node_id),
 336                 "adding a def'n for node-id {:?} and data {:?} but a previous def'n exists: {:?}",
 337                 node_id,
 338                 data,
 339                 self.table.def_key(self.node_to_def_index[&node_id]));
 340
 341         assert_eq!(parent.is_some(), data != DefPathData::CrateRoot);
 342
 343         // Find a unique DefKey. This basically means incrementing the disambiguator
 344         // until we get no match.
 345         let mut key = DefKey {
 346             parent: parent,
 347             disambiguated_data: DisambiguatedDefPathData {
 348                 data: data,
 349                 disambiguator: 0
 350             }
 351         };
 352
 353         while self.table.contains_key(&key) {
 354             key.disambiguated_data.disambiguator += 1;
 355         }
 356
 357         debug!("create_def_with_parent: after disambiguation, key = {:?}", key);
 358
 359         // Create the definition.
 360         let index = self.table.insert(key);
 361         debug!("create_def_with_parent: def_index_to_node[{:?} <-> {:?}", index, node_id);
 362         self.node_to_def_index.insert(node_id, index);
 363         assert_eq!(index.as_usize(), self.def_index_to_node.len());
 364         self.def_index_to_node.push(node_id);
 365
 366         index
 367     }
 368 }
 369
 370 impl DefPathData {
 371     pub fn get_opt_name(&self) -> Option<ast::Name> {
 372         use self::DefPathData::*;
 373         match *self {
 374             TypeNs(ref name) |
 375             ValueNs(ref name) |
 376             Module(ref name) |
 377             MacroDef(ref name) |
 378             TypeParam(ref name) |
 379             LifetimeDef(ref name) |
 380             EnumVariant(ref name) |
 381             Binding(ref name) |
 382             Field(ref name) => Some(Symbol::intern(name)),
 383
 384             Impl |
 385             CrateRoot |
 386             Misc |
 387             ClosureExpr |
 388             StructCtor |
 389             Initializer |
 390             ImplTrait => None
 391         }
 392     }
 393
 394     pub fn as_interned_str(&self) -> InternedString {
 395         use self::DefPathData::*;
 396         let s = match *self {
 397             TypeNs(ref name) |
 398             ValueNs(ref name) |
 399             Module(ref name) |
 400             MacroDef(ref name) |
 401             TypeParam(ref name) |
 402             LifetimeDef(ref name) |
 403             EnumVariant(ref name) |
 404             Binding(ref name) |
 405             Field(ref name) => {
 406                 return name.clone();
 407             }
 408
 409             // note that this does not show up in user printouts
 410             CrateRoot => "{{root}}",
 411
 412             Impl => "{{impl}}",
 413             Misc => "{{?}}",
 414             ClosureExpr => "{{closure}}",
 415             StructCtor => "{{constructor}}",
 416             Initializer => "{{initializer}}",
 417             ImplTrait => "{{impl-Trait}}",
 418         };
 419
 420         Symbol::intern(s).as_str()
 421     }
 422
 423     pub fn to_string(&self) -> String {
 424         self.as_interned_str().to_string()
 425     }
 426 }