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.
7 pub use crate::def_id
::DefPathHash
;
8 use crate::def_id
::{CrateNum, DefId, DefIndex, LocalDefId, CRATE_DEF_INDEX, LOCAL_CRATE}
;
12 use rustc_ast
::crate_disambiguator
::CrateDisambiguator
;
13 use rustc_data_structures
::fx
::FxHashMap
;
14 use rustc_data_structures
::stable_hasher
::StableHasher
;
15 use rustc_index
::vec
::IndexVec
;
16 use rustc_span
::hygiene
::ExpnId
;
17 use rustc_span
::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
{
82 def_id_to_span
: IndexVec
<LocalDefId
, Span
>,
84 // FIXME(eddyb) don't go through `ast::NodeId` to convert between `HirId`
85 // and `LocalDefId` - ideally all `LocalDefId`s would be HIR owners.
86 node_id_to_def_id
: FxHashMap
<ast
::NodeId
, LocalDefId
>,
87 def_id_to_node_id
: IndexVec
<LocalDefId
, ast
::NodeId
>,
89 pub(super) node_id_to_hir_id
: IndexVec
<ast
::NodeId
, Option
<hir
::HirId
>>,
90 /// The reverse mapping of `node_id_to_hir_id`.
91 pub(super) hir_id_to_node_id
: FxHashMap
<hir
::HirId
, ast
::NodeId
>,
93 /// If `ExpnId` is an ID of some macro expansion,
94 /// then `DefId` is the normal module (`mod`) in which the expanded macro was defined.
95 parent_modules_of_macro_defs
: FxHashMap
<ExpnId
, DefId
>,
96 /// Item with a given `LocalDefId` was defined during macro expansion with ID `ExpnId`.
97 expansions_that_defined
: FxHashMap
<LocalDefId
, ExpnId
>,
98 next_disambiguator
: FxHashMap
<(LocalDefId
, DefPathData
), u32>,
99 /// When collecting definitions from an AST fragment produced by a macro invocation `ExpnId`
100 /// we know what parent node that fragment should be attached to thanks to this table.
101 invocation_parents
: FxHashMap
<ExpnId
, LocalDefId
>,
102 /// Indices of unnamed struct or variant fields with unresolved attributes.
103 placeholder_field_indices
: FxHashMap
<ast
::NodeId
, usize>,
106 /// A unique identifier that we can use to lookup a definition
107 /// precisely. It combines the index of the definition's parent (if
108 /// any) with a `DisambiguatedDefPathData`.
109 #[derive(Copy, Clone, PartialEq, Debug, RustcEncodable, RustcDecodable)]
112 pub parent
: Option
<DefIndex
>,
114 /// The identifier of this node.
115 pub disambiguated_data
: DisambiguatedDefPathData
,
119 fn compute_stable_hash(&self, parent_hash
: DefPathHash
) -> DefPathHash
{
120 let mut hasher
= StableHasher
::new();
122 // We hash a `0u8` here to disambiguate between regular `DefPath` hashes,
123 // and the special "root_parent" below.
124 0u8.hash(&mut hasher
);
125 parent_hash
.hash(&mut hasher
);
127 let DisambiguatedDefPathData { ref data, disambiguator }
= self.disambiguated_data
;
129 ::std
::mem
::discriminant(data
).hash(&mut hasher
);
130 if let Some(name
) = data
.get_opt_name() {
131 // Get a stable hash by considering the symbol chars rather than
133 name
.as_str().hash(&mut hasher
);
136 disambiguator
.hash(&mut hasher
);
138 DefPathHash(hasher
.finish())
141 fn root_parent_stable_hash(
143 crate_disambiguator
: CrateDisambiguator
,
145 let mut hasher
= StableHasher
::new();
146 // Disambiguate this from a regular `DefPath` hash; see `compute_stable_hash()` above.
147 1u8.hash(&mut hasher
);
148 crate_name
.hash(&mut hasher
);
149 crate_disambiguator
.hash(&mut hasher
);
150 DefPathHash(hasher
.finish())
154 /// A pair of `DefPathData` and an integer disambiguator. The integer is
155 /// normally `0`, but in the event that there are multiple defs with the
156 /// same `parent` and `data`, we use this field to disambiguate
157 /// between them. This introduces some artificial ordering dependency
158 /// but means that if you have, e.g., two impls for the same type in
159 /// the same module, they do get distinct `DefId`s.
160 #[derive(Copy, Clone, PartialEq, Debug, RustcEncodable, RustcDecodable)]
161 pub struct DisambiguatedDefPathData
{
162 pub data
: DefPathData
,
163 pub disambiguator
: u32,
166 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
168 /// The path leading from the crate root to the item.
169 pub data
: Vec
<DisambiguatedDefPathData
>,
171 /// The crate root this path is relative to.
176 pub fn is_local(&self) -> bool
{
177 self.krate
== LOCAL_CRATE
180 pub fn make
<FN
>(krate
: CrateNum
, start_index
: DefIndex
, mut get_key
: FN
) -> DefPath
182 FN
: FnMut(DefIndex
) -> DefKey
,
184 let mut data
= vec
![];
185 let mut index
= Some(start_index
);
187 debug
!("DefPath::make: krate={:?} index={:?}", krate
, index
);
188 let p
= index
.unwrap();
189 let key
= get_key(p
);
190 debug
!("DefPath::make: key={:?}", key
);
191 match key
.disambiguated_data
.data
{
192 DefPathData
::CrateRoot
=> {
193 assert
!(key
.parent
.is_none());
197 data
.push(key
.disambiguated_data
);
203 DefPath { data, krate }
206 /// Returns a string representation of the `DefPath` without
207 /// the crate-prefix. This method is useful if you don't have
208 /// a `TyCtxt` available.
209 pub fn to_string_no_crate(&self) -> String
{
210 let mut s
= String
::with_capacity(self.data
.len() * 16);
212 for component
in &self.data
{
213 write
!(s
, "::{}[{}]", component
.data
.as_symbol(), component
.disambiguator
).unwrap();
219 /// Returns a filename-friendly string for the `DefPath`, with the
221 pub fn to_string_friendly
<F
>(&self, crate_imported_name
: F
) -> String
223 F
: FnOnce(CrateNum
) -> Symbol
,
225 let crate_name_str
= crate_imported_name(self.krate
).as_str();
226 let mut s
= String
::with_capacity(crate_name_str
.len() + self.data
.len() * 16);
228 write
!(s
, "::{}", crate_name_str
).unwrap();
230 for component
in &self.data
{
231 if component
.disambiguator
== 0 {
232 write
!(s
, "::{}", component
.data
.as_symbol()).unwrap();
234 write
!(s
, "{}[{}]", component
.data
.as_symbol(), component
.disambiguator
).unwrap();
241 /// Returns a filename-friendly string of the `DefPath`, without
242 /// the crate-prefix. This method is useful if you don't have
243 /// a `TyCtxt` available.
244 pub fn to_filename_friendly_no_crate(&self) -> String
{
245 let mut s
= String
::with_capacity(self.data
.len() * 16);
247 let mut opt_delimiter
= None
;
248 for component
in &self.data
{
249 opt_delimiter
.map(|d
| s
.push(d
));
250 opt_delimiter
= Some('
-'
);
251 if component
.disambiguator
== 0 {
252 write
!(s
, "{}", component
.data
.as_symbol()).unwrap();
254 write
!(s
, "{}[{}]", component
.data
.as_symbol(), component
.disambiguator
).unwrap();
261 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
262 pub enum DefPathData
{
263 // Root: these should only be used for the root nodes, because
264 // they are treated specially by the `def_path` function.
265 /// The crate root (marker).
267 // Catch-all for random `DefId` things like `DUMMY_NODE_ID`.
270 // Different kinds of items and item-like things:
273 /// Something in the type namespace.
275 /// Something in the value namespace.
277 /// Something in the macro namespace.
279 /// Something in the lifetime namespace.
281 /// A closure expression.
284 // Subportions of items:
285 /// Implicit constructor for a unit or tuple-like struct or enum variant.
287 /// A constant expression (see `{ast,hir}::AnonConst`).
289 /// An `impl Trait` type node.
294 pub fn def_path_table(&self) -> &DefPathTable
{
298 /// Gets the number of definitions.
299 pub fn def_index_count(&self) -> usize {
300 self.table
.index_to_key
.len()
303 pub fn def_key(&self, id
: LocalDefId
) -> DefKey
{
304 self.table
.def_key(id
.local_def_index
)
308 pub fn def_path_hash(&self, id
: LocalDefId
) -> DefPathHash
{
309 self.table
.def_path_hash(id
.local_def_index
)
312 /// Returns the path from the crate root to `index`. The root
313 /// nodes are not included in the path (i.e., this will be an
314 /// empty vector for the crate root). For an inlined item, this
315 /// will be the path of the item in the external crate (but the
316 /// path will begin with the path to the external crate).
317 pub fn def_path(&self, id
: LocalDefId
) -> DefPath
{
318 DefPath
::make(LOCAL_CRATE
, id
.local_def_index
, |index
| {
319 self.def_key(LocalDefId { local_def_index: index }
)
324 pub fn opt_local_def_id(&self, node
: ast
::NodeId
) -> Option
<LocalDefId
> {
325 self.node_id_to_def_id
.get(&node
).copied()
329 pub fn local_def_id(&self, node
: ast
::NodeId
) -> LocalDefId
{
330 self.opt_local_def_id(node
).unwrap()
334 pub fn as_local_node_id(&self, def_id
: DefId
) -> Option
<ast
::NodeId
> {
335 if let Some(def_id
) = def_id
.as_local() {
336 let node_id
= self.def_id_to_node_id
[def_id
];
337 if node_id
!= ast
::DUMMY_NODE_ID
{
338 return Some(node_id
);
345 pub fn as_local_hir_id(&self, def_id
: DefId
) -> Option
<hir
::HirId
> {
346 if let Some(def_id
) = def_id
.as_local() {
347 Some(self.local_def_id_to_hir_id(def_id
))
354 pub fn hir_id_to_node_id(&self, hir_id
: hir
::HirId
) -> ast
::NodeId
{
355 self.hir_id_to_node_id
[&hir_id
]
359 pub fn node_id_to_hir_id(&self, node_id
: ast
::NodeId
) -> hir
::HirId
{
360 self.node_id_to_hir_id
[node_id
].unwrap()
364 pub fn opt_node_id_to_hir_id(&self, node_id
: ast
::NodeId
) -> Option
<hir
::HirId
> {
365 self.node_id_to_hir_id
[node_id
]
369 pub fn local_def_id_to_hir_id(&self, id
: LocalDefId
) -> hir
::HirId
{
370 let node_id
= self.def_id_to_node_id
[id
];
371 self.node_id_to_hir_id
[node_id
].unwrap()
375 pub fn opt_local_def_id_to_hir_id(&self, id
: LocalDefId
) -> Option
<hir
::HirId
> {
376 let node_id
= self.def_id_to_node_id
[id
];
377 self.node_id_to_hir_id
[node_id
]
380 /// Retrieves the span of the given `DefId` if `DefId` is in the local crate.
382 pub fn opt_span(&self, def_id
: DefId
) -> Option
<Span
> {
383 if let Some(def_id
) = def_id
.as_local() { Some(self.def_id_to_span[def_id]) }
else { None }
386 /// Adds a root definition (no parent) and a few other reserved definitions.
387 pub fn create_root_def(
390 crate_disambiguator
: CrateDisambiguator
,
394 disambiguated_data
: DisambiguatedDefPathData
{
395 data
: DefPathData
::CrateRoot
,
400 let parent_hash
= DefKey
::root_parent_stable_hash(crate_name
, crate_disambiguator
);
401 let def_path_hash
= key
.compute_stable_hash(parent_hash
);
403 // Create the definition.
404 let root
= LocalDefId { local_def_index: self.table.allocate(key, def_path_hash) }
;
405 assert_eq
!(root
.local_def_index
, CRATE_DEF_INDEX
);
407 assert_eq
!(self.def_id_to_node_id
.push(ast
::CRATE_NODE_ID
), root
);
408 assert_eq
!(self.def_id_to_span
.push(rustc_span
::DUMMY_SP
), root
);
410 self.node_id_to_def_id
.insert(ast
::CRATE_NODE_ID
, root
);
411 self.set_invocation_parent(ExpnId
::root(), root
);
416 /// Adds a definition with a parent definition.
417 pub fn create_def_with_parent(
420 node_id
: ast
::NodeId
,
426 "create_def_with_parent(parent={:?}, node_id={:?}, data={:?})",
427 parent
, node_id
, data
431 !self.node_id_to_def_id
.contains_key(&node_id
),
432 "adding a def'n for node-id {:?} and data {:?} but a previous def'n exists: {:?}",
435 self.table
.def_key(self.node_id_to_def_id
[&node_id
].local_def_index
),
438 // The root node must be created with `create_root_def()`.
439 assert
!(data
!= DefPathData
::CrateRoot
);
441 // Find the next free disambiguator for this key.
442 let disambiguator
= {
443 let next_disamb
= self.next_disambiguator
.entry((parent
, data
)).or_insert(0);
444 let disambiguator
= *next_disamb
;
445 *next_disamb
= next_disamb
.checked_add(1).expect("disambiguator overflow");
450 parent
: Some(parent
.local_def_index
),
451 disambiguated_data
: DisambiguatedDefPathData { data, disambiguator }
,
454 let parent_hash
= self.table
.def_path_hash(parent
.local_def_index
);
455 let def_path_hash
= key
.compute_stable_hash(parent_hash
);
457 debug
!("create_def_with_parent: after disambiguation, key = {:?}", key
);
459 // Create the definition.
460 let def_id
= LocalDefId { local_def_index: self.table.allocate(key, def_path_hash) }
;
462 assert_eq
!(self.def_id_to_node_id
.push(node_id
), def_id
);
463 assert_eq
!(self.def_id_to_span
.push(span
), def_id
);
465 // Some things for which we allocate `LocalDefId`s don't correspond to
466 // anything in the AST, so they don't have a `NodeId`. For these cases
467 // we don't need a mapping from `NodeId` to `LocalDefId`.
468 if node_id
!= ast
::DUMMY_NODE_ID
{
469 debug
!("create_def_with_parent: def_id_to_node_id[{:?}] <-> {:?}", def_id
, node_id
);
470 self.node_id_to_def_id
.insert(node_id
, def_id
);
473 if expn_id
!= ExpnId
::root() {
474 self.expansions_that_defined
.insert(def_id
, expn_id
);
480 /// Initializes the `ast::NodeId` to `HirId` mapping once it has been generated during
481 /// AST to HIR lowering.
482 pub fn init_node_id_to_hir_id_mapping(
484 mapping
: IndexVec
<ast
::NodeId
, Option
<hir
::HirId
>>,
487 self.node_id_to_hir_id
.is_empty(),
488 "trying to initialize `NodeId` -> `HirId` mapping twice"
490 self.node_id_to_hir_id
= mapping
;
492 // Build the reverse mapping of `node_id_to_hir_id`.
493 self.hir_id_to_node_id
= self
496 .filter_map(|(node_id
, &hir_id
)| hir_id
.map(|hir_id
| (hir_id
, node_id
)))
500 pub fn expansion_that_defined(&self, id
: LocalDefId
) -> ExpnId
{
501 self.expansions_that_defined
.get(&id
).copied().unwrap_or(ExpnId
::root())
504 pub fn parent_module_of_macro_def(&self, expn_id
: ExpnId
) -> DefId
{
505 self.parent_modules_of_macro_defs
[&expn_id
]
508 pub fn add_parent_module_of_macro_def(&mut self, expn_id
: ExpnId
, module
: DefId
) {
509 self.parent_modules_of_macro_defs
.insert(expn_id
, module
);
512 pub fn invocation_parent(&self, invoc_id
: ExpnId
) -> LocalDefId
{
513 self.invocation_parents
[&invoc_id
]
516 pub fn set_invocation_parent(&mut self, invoc_id
: ExpnId
, parent
: LocalDefId
) {
517 let old_parent
= self.invocation_parents
.insert(invoc_id
, parent
);
518 assert
!(old_parent
.is_none(), "parent `LocalDefId` is reset for an invocation");
521 pub fn placeholder_field_index(&self, node_id
: ast
::NodeId
) -> usize {
522 self.placeholder_field_indices
[&node_id
]
525 pub fn set_placeholder_field_index(&mut self, node_id
: ast
::NodeId
, index
: usize) {
526 let old_index
= self.placeholder_field_indices
.insert(node_id
, index
);
527 assert
!(old_index
.is_none(), "placeholder field index is reset for a node ID");
532 pub fn get_opt_name(&self) -> Option
<Symbol
> {
533 use self::DefPathData
::*;
535 TypeNs(name
) | ValueNs(name
) | MacroNs(name
) | LifetimeNs(name
) => Some(name
),
537 Impl
| CrateRoot
| Misc
| ClosureExpr
| Ctor
| AnonConst
| ImplTrait
=> None
,
541 pub fn as_symbol(&self) -> Symbol
{
542 use self::DefPathData
::*;
544 TypeNs(name
) | ValueNs(name
) | MacroNs(name
) | LifetimeNs(name
) => name
,
545 // Note that this does not show up in user print-outs.
546 CrateRoot
=> sym
::double_braced_crate
,
547 Impl
=> sym
::double_braced_impl
,
548 Misc
=> sym
::double_braced_misc
,
549 ClosureExpr
=> sym
::double_braced_closure
,
550 Ctor
=> sym
::double_braced_constructor
,
551 AnonConst
=> sym
::double_braced_constant
,
552 ImplTrait
=> sym
::double_braced_opaque
,
556 pub fn to_string(&self) -> String
{
557 self.as_symbol().to_string()