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.
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.
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.
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};
26 use syntax::symbol::{Symbol, InternedString};
28 use util::nodemap::NodeMap;
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],
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 {
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()],
56 fn allocate(&mut self,
59 address_space: DefIndexAddressSpace)
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());
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());
76 pub fn def_key(&self, index: DefIndex) -> DefKey {
77 self.index_to_key[index.address_space().index()]
78 [index.as_array_index()].clone()
82 pub fn def_path_hash(&self, index: DefIndex) -> u64 {
83 self.def_path_hashes[index.address_space().index()]
84 [index.as_array_index()]
88 pub fn def_index_for_def_key(&self, key: &DefKey) -> Option<DefIndex> {
89 self.key_to_index.get(key).cloned()
93 pub fn contains_key(&self, key: &DefKey) -> bool {
94 self.key_to_index.contains_key(key)
97 pub fn retrace_path(&self,
98 path_data: &[DisambiguatedDefPathData])
100 let root_key = DefKey {
102 disambiguated_data: DisambiguatedDefPathData {
103 data: DefPathData::CrateRoot,
108 let root_index = self.key_to_index
110 .expect("no root key?")
113 debug!("retrace_path: root_index={:?}", root_index);
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,
130 impl Encodable for DefPathTable {
131 fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
133 self.index_to_key[DefIndexAddressSpace::Low.index()].encode(s)?;
134 self.index_to_key[DefIndexAddressSpace::High.index()].encode(s)?;
137 self.def_path_hashes[DefIndexAddressSpace::Low.index()].encode(s)?;
138 self.def_path_hashes[DefIndexAddressSpace::High.index()].encode(s)?;
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)?;
149 let def_path_hashes_lo: Vec<u64> = Decodable::decode(d)?;
150 let def_path_hashes_hi: Vec<u64> = Decodable::decode(d)?;
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];
155 let mut key_to_index = FxHashMap();
157 for space in &[DefIndexAddressSpace::Low, DefIndexAddressSpace::High] {
158 key_to_index.extend(index_to_key[space.index()]
161 .map(|(index, key)| (key.clone(),
162 DefIndex::new(index + space.start()))))
166 index_to_key: index_to_key,
167 key_to_index: key_to_index,
168 def_path_hashes: def_path_hashes,
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 {
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>,
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 {
189 table: self.table.clone(),
190 node_to_def_index: self.node_to_def_index.clone(),
192 self.def_index_to_node[0].clone(),
193 self.def_index_to_node[1].clone(),
195 node_to_hir_id: self.node_to_hir_id.clone(),
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)]
206 pub parent: Option<DefIndex>,
208 /// Identifier of this node.
209 pub disambiguated_data: DisambiguatedDefPathData,
213 fn compute_stable_hash(&self, parent_hash: u64) -> u64 {
214 let mut hasher = StableHasher::new();
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);
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);
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
247 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
249 /// the path leading from the crate root to the item
250 pub data: Vec<DisambiguatedDefPathData>,
252 /// what krate root is this path relative to?
257 pub fn is_local(&self) -> bool {
258 self.krate == LOCAL_CRATE
261 pub fn make<FN>(krate: CrateNum,
262 start_index: DefIndex,
263 mut get_key: FN) -> DefPath
264 where FN: FnMut(DefIndex) -> DefKey
266 let mut data = vec![];
267 let mut index = Some(start_index);
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());
279 data.push(key.disambiguated_data);
285 DefPath { data: data, krate: krate }
288 pub fn to_string(&self, tcx: TyCtxt) -> String {
289 let mut s = String::with_capacity(self.data.len() * 16);
291 s.push_str(&tcx.original_crate_name(self.krate).as_str());
293 s.push_str(&tcx.crate_disambiguator(self.krate).as_str());
295 for component in &self.data {
298 component.data.as_interned_str(),
299 component.disambiguator)
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);
312 for component in &self.data {
315 component.data.as_interned_str(),
316 component.disambiguator)
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)
331 // Catch-all for random DefId things like DUMMY_NODE_ID
334 // Different kinds of items and item-like things:
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),
344 MacroDef(InternedString),
345 /// A closure expression
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),
356 Field(InternedString),
357 /// Implicit ctor for a tuple-like struct
359 /// Initializer for a const
362 Binding(InternedString),
363 /// An `impl Trait` type node.
365 /// A `typeof` type node.
370 /// Create new empty definition map.
371 pub fn new() -> Definitions {
373 table: DefPathTable {
374 index_to_key: [vec![], vec![]],
375 key_to_index: FxHashMap(),
376 def_path_hashes: [vec![], vec![]],
378 node_to_def_index: NodeMap(),
379 def_index_to_node: [vec![], vec![]],
380 node_to_hir_id: IndexVec::new(),
384 pub fn def_path_table(&self) -> &DefPathTable {
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())
394 pub fn def_key(&self, index: DefIndex) -> DefKey {
395 self.table.def_key(index)
399 pub fn def_path_hash(&self, index: DefIndex) -> u64 {
400 self.table.def_path_hash(index)
403 pub fn def_index_for_def_key(&self, key: DefKey) -> Option<DefIndex> {
404 self.table.def_index_for_def_key(&key)
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))
416 pub fn opt_def_index(&self, node: ast::NodeId) -> Option<DefIndex> {
417 self.node_to_def_index.get(&node).cloned()
420 pub fn opt_local_def_id(&self, node: ast::NodeId) -> Option<DefId> {
421 self.opt_def_index(node).map(DefId::local)
424 pub fn local_def_id(&self, node: ast::NodeId) -> DefId {
425 self.opt_local_def_id(node).unwrap()
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])
438 pub fn node_to_hir_id(&self, node_id: ast::NodeId) -> hir::HirId {
439 self.node_to_hir_id[node_id]
442 /// Add a definition with a parent definition.
443 pub fn create_root_def(&mut self,
445 crate_disambiguator: &str)
449 disambiguated_data: DisambiguatedDefPathData {
450 data: DefPathData::CrateRoot,
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);
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);
469 /// Add a definition with a parent definition.
470 pub fn create_def_with_parent(&mut self,
472 node_id: ast::NodeId,
474 address_space: DefIndexAddressSpace)
476 debug!("create_def_with_parent(parent={:?}, node_id={:?}, data={:?})",
477 parent, node_id, data);
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: {:?}",
483 self.table.def_key(self.node_to_def_index[&node_id]));
485 // The root node must be created with create_root_def()
486 assert!(data != DefPathData::CrateRoot);
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 {
498 while self.table.contains_key(&key) {
499 key.disambiguated_data.disambiguator += 1;
502 let parent_hash = self.table.def_path_hash(parent);
503 let def_path_hash = key.compute_stable_hash(parent_hash);
505 debug!("create_def_with_parent: after disambiguation, key = {:?}", key);
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);
513 debug!("create_def_with_parent: def_index_to_node[{:?} <-> {:?}", index, node_id);
514 self.node_to_def_index.insert(node_id, index);
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;
530 pub fn get_opt_name(&self) -> Option<ast::Name> {
531 use self::DefPathData::*;
537 TypeParam(ref name) |
538 LifetimeDef(ref name) |
539 EnumVariant(ref name) |
541 Field(ref name) => Some(Symbol::intern(name)),
554 pub fn as_interned_str(&self) -> InternedString {
555 use self::DefPathData::*;
556 let s = match *self {
561 TypeParam(ref name) |
562 LifetimeDef(ref name) |
563 EnumVariant(ref name) |
569 // note that this does not show up in user printouts
570 CrateRoot => "{{root}}",
574 ClosureExpr => "{{closure}}",
575 StructCtor => "{{constructor}}",
576 Initializer => "{{initializer}}",
577 ImplTrait => "{{impl-Trait}}",
578 Typeof => "{{typeof}}",
581 Symbol::intern(s).as_str()
584 pub fn to_string(&self) -> String {
585 self.as_interned_str().to_string()