1 //! For each definition, we track the following data. A definition
2 //! here is defined somewhat circularly as "something with a `DefId`",
3 //! but it generally corresponds to things like structs, enums, etc.
4 //! There are also some rather random cases (like const initializer
5 //! expressions) that are mostly just leftovers.
8 use rustc_ast::node_id::NodeMap;
9 use rustc_data_structures::fingerprint::Fingerprint;
10 use rustc_data_structures::fx::FxHashMap;
11 use rustc_data_structures::stable_hasher::StableHasher;
13 use rustc_hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX, LOCAL_CRATE};
14 use rustc_index::vec::IndexVec;
15 use rustc_session::CrateDisambiguator;
16 use rustc_span::hygiene::ExpnId;
17 use rustc_span::symbol::{sym, Symbol};
20 use std::borrow::Borrow;
24 /// The `DefPathTable` maps `DefIndex`es to `DefKey`s and vice versa.
25 /// Internally the `DefPathTable` holds a tree of `DefKey`s, where each `DefKey`
26 /// stores the `DefIndex` of its parent.
27 /// There is one `DefPathTable` for each crate.
28 #[derive(Clone, Default, RustcDecodable, RustcEncodable)]
29 pub struct DefPathTable {
30 index_to_key: IndexVec<DefIndex, DefKey>,
31 def_path_hashes: IndexVec<DefIndex, DefPathHash>,
35 fn allocate(&mut self, key: DefKey, def_path_hash: DefPathHash) -> DefIndex {
37 let index = DefIndex::from(self.index_to_key.len());
38 debug!("DefPathTable::insert() - {:?} <-> {:?}", key, index);
39 self.index_to_key.push(key);
42 self.def_path_hashes.push(def_path_hash);
43 debug_assert!(self.def_path_hashes.len() == self.index_to_key.len());
47 pub fn next_id(&self) -> DefIndex {
48 DefIndex::from(self.index_to_key.len())
52 pub fn def_key(&self, index: DefIndex) -> DefKey {
53 self.index_to_key[index]
57 pub fn def_path_hash(&self, index: DefIndex) -> DefPathHash {
58 let hash = self.def_path_hashes[index];
59 debug!("def_path_hash({:?}) = {:?}", index, hash);
63 pub fn add_def_path_hashes_to(&self, cnum: CrateNum, out: &mut FxHashMap<DefPathHash, DefId>) {
64 out.extend(self.def_path_hashes.iter().enumerate().map(|(index, &hash)| {
65 let def_id = DefId { krate: cnum, index: DefIndex::from(index) };
70 pub fn size(&self) -> usize {
71 self.index_to_key.len()
75 /// The definition table containing node definitions.
76 /// It holds the `DefPathTable` for local `DefId`s/`DefPath`s and it also stores a
77 /// mapping from `NodeId`s to local `DefId`s.
78 #[derive(Clone, Default)]
79 pub struct Definitions {
81 node_to_def_index: NodeMap<DefIndex>,
82 def_index_to_node: IndexVec<DefIndex, ast::NodeId>,
83 pub(super) node_to_hir_id: IndexVec<ast::NodeId, hir::HirId>,
84 /// If `ExpnId` is an ID of some macro expansion,
85 /// then `DefId` is the normal module (`mod`) in which the expanded macro was defined.
86 parent_modules_of_macro_defs: FxHashMap<ExpnId, DefId>,
87 /// Item with a given `DefIndex` was defined during macro expansion with ID `ExpnId`.
88 expansions_that_defined: FxHashMap<DefIndex, ExpnId>,
89 next_disambiguator: FxHashMap<(DefIndex, DefPathData), u32>,
90 def_index_to_span: FxHashMap<DefIndex, Span>,
91 /// When collecting definitions from an AST fragment produced by a macro invocation `ExpnId`
92 /// we know what parent node that fragment should be attached to thanks to this table.
93 invocation_parents: FxHashMap<ExpnId, DefIndex>,
94 /// Indices of unnamed struct or variant fields with unresolved attributes.
95 placeholder_field_indices: NodeMap<usize>,
98 /// A unique identifier that we can use to lookup a definition
99 /// precisely. It combines the index of the definition's parent (if
100 /// any) with a `DisambiguatedDefPathData`.
101 #[derive(Copy, Clone, PartialEq, Debug, RustcEncodable, RustcDecodable)]
104 pub parent: Option<DefIndex>,
106 /// The identifier of this node.
107 pub disambiguated_data: DisambiguatedDefPathData,
111 fn compute_stable_hash(&self, parent_hash: DefPathHash) -> DefPathHash {
112 let mut hasher = StableHasher::new();
114 // We hash a `0u8` here to disambiguate between regular `DefPath` hashes,
115 // and the special "root_parent" below.
116 0u8.hash(&mut hasher);
117 parent_hash.hash(&mut hasher);
119 let DisambiguatedDefPathData { ref data, disambiguator } = self.disambiguated_data;
121 ::std::mem::discriminant(data).hash(&mut hasher);
122 if let Some(name) = data.get_opt_name() {
123 // Get a stable hash by considering the symbol chars rather than
125 name.as_str().hash(&mut hasher);
128 disambiguator.hash(&mut hasher);
130 DefPathHash(hasher.finish())
133 fn root_parent_stable_hash(
135 crate_disambiguator: CrateDisambiguator,
137 let mut hasher = StableHasher::new();
138 // Disambiguate this from a regular `DefPath` hash; see `compute_stable_hash()` above.
139 1u8.hash(&mut hasher);
140 crate_name.hash(&mut hasher);
141 crate_disambiguator.hash(&mut hasher);
142 DefPathHash(hasher.finish())
146 /// A pair of `DefPathData` and an integer disambiguator. The integer is
147 /// normally `0`, but in the event that there are multiple defs with the
148 /// same `parent` and `data`, we use this field to disambiguate
149 /// between them. This introduces some artificial ordering dependency
150 /// but means that if you have, e.g., two impls for the same type in
151 /// the same module, they do get distinct `DefId`s.
152 #[derive(Copy, Clone, PartialEq, Debug, RustcEncodable, RustcDecodable)]
153 pub struct DisambiguatedDefPathData {
154 pub data: DefPathData,
155 pub disambiguator: u32,
158 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
160 /// The path leading from the crate root to the item.
161 pub data: Vec<DisambiguatedDefPathData>,
163 /// The crate root this path is relative to.
168 pub fn is_local(&self) -> bool {
169 self.krate == LOCAL_CRATE
172 pub fn make<FN>(krate: CrateNum, start_index: DefIndex, mut get_key: FN) -> DefPath
174 FN: FnMut(DefIndex) -> DefKey,
176 let mut data = vec![];
177 let mut index = Some(start_index);
179 debug!("DefPath::make: krate={:?} index={:?}", krate, index);
180 let p = index.unwrap();
181 let key = get_key(p);
182 debug!("DefPath::make: key={:?}", key);
183 match key.disambiguated_data.data {
184 DefPathData::CrateRoot => {
185 assert!(key.parent.is_none());
189 data.push(key.disambiguated_data);
195 DefPath { data, krate }
198 /// Returns a string representation of the `DefPath` without
199 /// the crate-prefix. This method is useful if you don't have
200 /// a `TyCtxt` available.
201 pub fn to_string_no_crate(&self) -> String {
202 let mut s = String::with_capacity(self.data.len() * 16);
204 for component in &self.data {
205 write!(s, "::{}[{}]", component.data.as_symbol(), component.disambiguator).unwrap();
211 /// Returns a filename-friendly string for the `DefPath`, with the
213 pub fn to_string_friendly<F>(&self, crate_imported_name: F) -> String
215 F: FnOnce(CrateNum) -> Symbol,
217 let crate_name_str = crate_imported_name(self.krate).as_str();
218 let mut s = String::with_capacity(crate_name_str.len() + self.data.len() * 16);
220 write!(s, "::{}", crate_name_str).unwrap();
222 for component in &self.data {
223 if component.disambiguator == 0 {
224 write!(s, "::{}", component.data.as_symbol()).unwrap();
226 write!(s, "{}[{}]", component.data.as_symbol(), component.disambiguator).unwrap();
233 /// Returns a filename-friendly string of the `DefPath`, without
234 /// the crate-prefix. This method is useful if you don't have
235 /// a `TyCtxt` available.
236 pub fn to_filename_friendly_no_crate(&self) -> String {
237 let mut s = String::with_capacity(self.data.len() * 16);
239 let mut opt_delimiter = None;
240 for component in &self.data {
241 opt_delimiter.map(|d| s.push(d));
242 opt_delimiter = Some('-');
243 if component.disambiguator == 0 {
244 write!(s, "{}", component.data.as_symbol()).unwrap();
246 write!(s, "{}[{}]", component.data.as_symbol(), component.disambiguator).unwrap();
253 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
254 pub enum DefPathData {
255 // Root: these should only be used for the root nodes, because
256 // they are treated specially by the `def_path` function.
257 /// The crate root (marker).
259 // Catch-all for random `DefId` things like `DUMMY_NODE_ID`.
262 // Different kinds of items and item-like things:
265 /// Something in the type namespace.
267 /// Something in the value namespace.
269 /// Something in the macro namespace.
271 /// Something in the lifetime namespace.
273 /// A closure expression.
276 // Subportions of items:
277 /// Implicit constructor for a unit or tuple-like struct or enum variant.
279 /// A constant expression (see `{ast,hir}::AnonConst`).
281 /// An `impl Trait` type node.
298 pub struct DefPathHash(pub Fingerprint);
300 impl Borrow<Fingerprint> for DefPathHash {
302 fn borrow(&self) -> &Fingerprint {
308 pub fn def_path_table(&self) -> &DefPathTable {
312 /// Gets the number of definitions.
313 pub fn def_index_count(&self) -> usize {
314 self.table.index_to_key.len()
317 pub fn def_key(&self, index: DefIndex) -> DefKey {
318 self.table.def_key(index)
322 pub fn def_path_hash(&self, index: DefIndex) -> DefPathHash {
323 self.table.def_path_hash(index)
326 /// Returns the path from the crate root to `index`. The root
327 /// nodes are not included in the path (i.e., this will be an
328 /// empty vector for the crate root). For an inlined item, this
329 /// will be the path of the item in the external crate (but the
330 /// path will begin with the path to the external crate).
331 pub fn def_path(&self, index: DefIndex) -> DefPath {
332 DefPath::make(LOCAL_CRATE, index, |p| self.def_key(p))
336 pub fn opt_def_index(&self, node: ast::NodeId) -> Option<DefIndex> {
337 self.node_to_def_index.get(&node).copied()
341 pub fn opt_local_def_id(&self, node: ast::NodeId) -> Option<DefId> {
342 self.opt_def_index(node).map(DefId::local)
346 pub fn local_def_id(&self, node: ast::NodeId) -> DefId {
347 self.opt_local_def_id(node).unwrap()
351 pub fn as_local_node_id(&self, def_id: DefId) -> Option<ast::NodeId> {
352 if def_id.krate == LOCAL_CRATE {
353 let node_id = self.def_index_to_node[def_id.index];
354 if node_id != ast::DUMMY_NODE_ID {
355 return Some(node_id);
362 pub fn as_local_hir_id(&self, def_id: DefId) -> Option<hir::HirId> {
363 if def_id.krate == LOCAL_CRATE {
364 let hir_id = self.def_index_to_hir_id(def_id.index);
365 if hir_id != hir::DUMMY_HIR_ID { Some(hir_id) } else { None }
372 pub fn node_to_hir_id(&self, node_id: ast::NodeId) -> hir::HirId {
373 self.node_to_hir_id[node_id]
377 pub fn def_index_to_hir_id(&self, def_index: DefIndex) -> hir::HirId {
378 let node_id = self.def_index_to_node[def_index];
379 self.node_to_hir_id[node_id]
382 /// Retrieves the span of the given `DefId` if `DefId` is in the local crate, the span exists
383 /// and it's not `DUMMY_SP`.
385 pub fn opt_span(&self, def_id: DefId) -> Option<Span> {
386 if def_id.krate == LOCAL_CRATE {
387 self.def_index_to_span.get(&def_id.index).copied()
393 /// Adds a root definition (no parent) and a few other reserved definitions.
394 pub fn create_root_def(
397 crate_disambiguator: CrateDisambiguator,
401 disambiguated_data: DisambiguatedDefPathData {
402 data: DefPathData::CrateRoot,
407 let parent_hash = DefKey::root_parent_stable_hash(crate_name, crate_disambiguator);
408 let def_path_hash = key.compute_stable_hash(parent_hash);
410 // Create the definition.
411 let root_index = self.table.allocate(key, def_path_hash);
412 assert_eq!(root_index, CRATE_DEF_INDEX);
413 assert!(self.def_index_to_node.is_empty());
414 self.def_index_to_node.push(ast::CRATE_NODE_ID);
415 self.node_to_def_index.insert(ast::CRATE_NODE_ID, root_index);
416 self.set_invocation_parent(ExpnId::root(), root_index);
421 /// Adds a definition with a parent definition.
422 pub fn create_def_with_parent(
425 node_id: ast::NodeId,
431 "create_def_with_parent(parent={:?}, node_id={:?}, data={:?})",
432 parent, node_id, data
436 !self.node_to_def_index.contains_key(&node_id),
437 "adding a def'n for node-id {:?} and data {:?} but a previous def'n exists: {:?}",
440 self.table.def_key(self.node_to_def_index[&node_id])
443 // The root node must be created with `create_root_def()`.
444 assert!(data != DefPathData::CrateRoot);
446 // Find the next free disambiguator for this key.
447 let disambiguator = {
448 let next_disamb = self.next_disambiguator.entry((parent, data)).or_insert(0);
449 let disambiguator = *next_disamb;
450 *next_disamb = next_disamb.checked_add(1).expect("disambiguator overflow");
455 parent: Some(parent),
456 disambiguated_data: DisambiguatedDefPathData { data, disambiguator },
459 let parent_hash = self.table.def_path_hash(parent);
460 let def_path_hash = key.compute_stable_hash(parent_hash);
462 debug!("create_def_with_parent: after disambiguation, key = {:?}", key);
464 // Create the definition.
465 let index = self.table.allocate(key, def_path_hash);
466 assert_eq!(index.index(), self.def_index_to_node.len());
467 self.def_index_to_node.push(node_id);
469 // Some things for which we allocate `DefIndex`es don't correspond to
470 // anything in the AST, so they don't have a `NodeId`. For these cases
471 // we don't need a mapping from `NodeId` to `DefIndex`.
472 if node_id != ast::DUMMY_NODE_ID {
473 debug!("create_def_with_parent: def_index_to_node[{:?} <-> {:?}", index, node_id);
474 self.node_to_def_index.insert(node_id, index);
477 if expn_id != ExpnId::root() {
478 self.expansions_that_defined.insert(index, expn_id);
481 // The span is added if it isn't dummy.
482 if !span.is_dummy() {
483 self.def_index_to_span.insert(index, span);
489 /// Initializes the `ast::NodeId` to `HirId` mapping once it has been generated during
490 /// AST to HIR lowering.
491 pub fn init_node_id_to_hir_id_mapping(&mut self, mapping: IndexVec<ast::NodeId, hir::HirId>) {
493 self.node_to_hir_id.is_empty(),
494 "trying to initialize `NodeId` -> `HirId` mapping twice"
496 self.node_to_hir_id = mapping;
499 pub fn expansion_that_defined(&self, index: DefIndex) -> ExpnId {
500 self.expansions_that_defined.get(&index).copied().unwrap_or(ExpnId::root())
503 pub fn parent_module_of_macro_def(&self, expn_id: ExpnId) -> DefId {
504 self.parent_modules_of_macro_defs[&expn_id]
507 pub fn add_parent_module_of_macro_def(&mut self, expn_id: ExpnId, module: DefId) {
508 self.parent_modules_of_macro_defs.insert(expn_id, module);
511 pub fn invocation_parent(&self, invoc_id: ExpnId) -> DefIndex {
512 self.invocation_parents[&invoc_id]
515 pub fn set_invocation_parent(&mut self, invoc_id: ExpnId, parent: DefIndex) {
516 let old_parent = self.invocation_parents.insert(invoc_id, parent);
517 assert!(old_parent.is_none(), "parent `DefIndex` is reset for an invocation");
520 pub fn placeholder_field_index(&self, node_id: ast::NodeId) -> usize {
521 self.placeholder_field_indices[&node_id]
524 pub fn set_placeholder_field_index(&mut self, node_id: ast::NodeId, index: usize) {
525 let old_index = self.placeholder_field_indices.insert(node_id, index);
526 assert!(old_index.is_none(), "placeholder field index is reset for a node ID");
531 pub fn get_opt_name(&self) -> Option<Symbol> {
532 use self::DefPathData::*;
534 TypeNs(name) | ValueNs(name) | MacroNs(name) | LifetimeNs(name) => Some(name),
536 Impl | CrateRoot | Misc | ClosureExpr | Ctor | AnonConst | ImplTrait => None,
540 pub fn as_symbol(&self) -> Symbol {
541 use self::DefPathData::*;
543 TypeNs(name) | ValueNs(name) | MacroNs(name) | LifetimeNs(name) => name,
544 // Note that this does not show up in user print-outs.
545 CrateRoot => sym::double_braced_crate,
546 Impl => sym::double_braced_impl,
547 Misc => sym::double_braced_misc,
548 ClosureExpr => sym::double_braced_closure,
549 Ctor => sym::double_braced_constructor,
550 AnonConst => sym::double_braced_constant,
551 ImplTrait => sym::double_braced_opaque,
555 pub fn to_string(&self) -> String {
556 self.as_symbol().to_string()