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 crate::hir
::def_id
::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX, LOCAL_CRATE}
;
9 use crate::ich
::Fingerprint
;
10 use crate::session
::CrateDisambiguator
;
11 use crate::util
::nodemap
::NodeMap
;
13 use rustc_data_structures
::fx
::FxHashMap
;
14 use rustc_data_structures
::stable_hasher
::StableHasher
;
15 use rustc_index
::vec
::IndexVec
;
16 use std
::borrow
::Borrow
;
20 use syntax_pos
::hygiene
::ExpnId
;
21 use syntax_pos
::symbol
::{sym, Symbol}
;
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: data, krate: 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()