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}
;
11 use rustc_ast
::crate_disambiguator
::CrateDisambiguator
;
12 use rustc_data_structures
::fx
::FxHashMap
;
13 use rustc_data_structures
::stable_hasher
::StableHasher
;
14 use rustc_index
::vec
::IndexVec
;
15 use rustc_span
::hygiene
::ExpnId
;
16 use rustc_span
::symbol
::{sym, Symbol}
;
22 /// The `DefPathTable` maps `DefIndex`es to `DefKey`s and vice versa.
23 /// Internally the `DefPathTable` holds a tree of `DefKey`s, where each `DefKey`
24 /// stores the `DefIndex` of its parent.
25 /// There is one `DefPathTable` for each crate.
26 #[derive(Clone, Default)]
27 pub struct DefPathTable
{
28 index_to_key
: IndexVec
<DefIndex
, DefKey
>,
29 def_path_hashes
: IndexVec
<DefIndex
, DefPathHash
>,
33 fn allocate(&mut self, key
: DefKey
, def_path_hash
: DefPathHash
) -> DefIndex
{
35 let index
= DefIndex
::from(self.index_to_key
.len());
36 debug
!("DefPathTable::insert() - {:?} <-> {:?}", key
, index
);
37 self.index_to_key
.push(key
);
40 self.def_path_hashes
.push(def_path_hash
);
41 debug_assert
!(self.def_path_hashes
.len() == self.index_to_key
.len());
46 pub fn def_key(&self, index
: DefIndex
) -> DefKey
{
47 self.index_to_key
[index
]
51 pub fn def_path_hash(&self, index
: DefIndex
) -> DefPathHash
{
52 let hash
= self.def_path_hashes
[index
];
53 debug
!("def_path_hash({:?}) = {:?}", index
, hash
);
57 pub fn num_def_ids(&self) -> usize {
58 self.index_to_key
.len()
61 pub fn enumerated_keys_and_path_hashes(
63 ) -> impl Iterator
<Item
= (DefIndex
, &DefKey
, &DefPathHash
)> + '_
{
66 .map(move |(index
, key
)| (index
, key
, &self.def_path_hashes
[index
]))
69 pub fn all_def_path_hashes_and_def_ids(
72 ) -> impl Iterator
<Item
= (DefPathHash
, DefId
)> + '_
{
75 .map(move |(index
, hash
)| (*hash
, DefId { krate, index }
))
79 /// The definition table containing node definitions.
80 /// It holds the `DefPathTable` for `LocalDefId`s/`DefPath`s.
81 /// It also stores mappings to convert `LocalDefId`s to/from `HirId`s.
83 pub struct Definitions
{
86 // FIXME(eddyb) ideally all `LocalDefId`s would be HIR owners.
87 pub(super) def_id_to_hir_id
: IndexVec
<LocalDefId
, Option
<hir
::HirId
>>,
88 /// The reverse mapping of `def_id_to_hir_id`.
89 pub(super) hir_id_to_def_id
: FxHashMap
<hir
::HirId
, LocalDefId
>,
91 /// If `ExpnId` is an ID of some macro expansion,
92 /// then `DefId` is the normal module (`mod`) in which the expanded macro was defined.
93 parent_modules_of_macro_defs
: FxHashMap
<ExpnId
, DefId
>,
94 /// Item with a given `LocalDefId` was defined during macro expansion with ID `ExpnId`.
95 expansions_that_defined
: FxHashMap
<LocalDefId
, ExpnId
>,
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, Encodable, Decodable)]
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, Encodable, Decodable)]
153 pub struct DisambiguatedDefPathData
{
154 pub data
: DefPathData
,
155 pub disambiguator
: u32,
158 #[derive(Clone, Debug, Encodable, Decodable)]
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 s
.extend(opt_delimiter
);
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, Encodable, Decodable)]
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.
286 pub fn def_path_table(&self) -> &DefPathTable
{
290 /// Gets the number of definitions.
291 pub fn def_index_count(&self) -> usize {
292 self.table
.index_to_key
.len()
295 pub fn def_key(&self, id
: LocalDefId
) -> DefKey
{
296 self.table
.def_key(id
.local_def_index
)
300 pub fn def_path_hash(&self, id
: LocalDefId
) -> DefPathHash
{
301 self.table
.def_path_hash(id
.local_def_index
)
304 /// Returns the path from the crate root to `index`. The root
305 /// nodes are not included in the path (i.e., this will be an
306 /// empty vector for the crate root). For an inlined item, this
307 /// will be the path of the item in the external crate (but the
308 /// path will begin with the path to the external crate).
309 pub fn def_path(&self, id
: LocalDefId
) -> DefPath
{
310 DefPath
::make(LOCAL_CRATE
, id
.local_def_index
, |index
| {
311 self.def_key(LocalDefId { local_def_index: index }
)
316 pub fn local_def_id_to_hir_id(&self, id
: LocalDefId
) -> hir
::HirId
{
317 self.def_id_to_hir_id
[id
].unwrap()
321 pub fn opt_local_def_id_to_hir_id(&self, id
: LocalDefId
) -> Option
<hir
::HirId
> {
322 self.def_id_to_hir_id
[id
]
326 pub fn opt_hir_id_to_local_def_id(&self, hir_id
: hir
::HirId
) -> Option
<LocalDefId
> {
327 self.hir_id_to_def_id
.get(&hir_id
).copied()
330 /// Adds a root definition (no parent) and a few other reserved definitions.
331 pub fn new(crate_name
: &str, crate_disambiguator
: CrateDisambiguator
) -> Definitions
{
334 disambiguated_data
: DisambiguatedDefPathData
{
335 data
: DefPathData
::CrateRoot
,
340 let parent_hash
= DefKey
::root_parent_stable_hash(crate_name
, crate_disambiguator
);
341 let def_path_hash
= key
.compute_stable_hash(parent_hash
);
343 // Create the root definition.
344 let mut table
= DefPathTable
::default();
345 let root
= LocalDefId { local_def_index: table.allocate(key, def_path_hash) }
;
346 assert_eq
!(root
.local_def_index
, CRATE_DEF_INDEX
);
350 def_id_to_hir_id
: Default
::default(),
351 hir_id_to_def_id
: Default
::default(),
352 expansions_that_defined
: Default
::default(),
353 parent_modules_of_macro_defs
: Default
::default(),
357 /// Retrieves the root definition.
358 pub fn get_root_def(&self) -> LocalDefId
{
359 LocalDefId { local_def_index: CRATE_DEF_INDEX }
362 /// Adds a definition with a parent definition.
368 mut next_disambiguator
: impl FnMut(LocalDefId
, DefPathData
) -> u32,
370 debug
!("create_def(parent={:?}, data={:?}, expn_id={:?})", parent
, data
, expn_id
);
372 // The root node must be created with `create_root_def()`.
373 assert
!(data
!= DefPathData
::CrateRoot
);
375 let disambiguator
= next_disambiguator(parent
, data
);
377 parent
: Some(parent
.local_def_index
),
378 disambiguated_data
: DisambiguatedDefPathData { data, disambiguator }
,
381 let parent_hash
= self.table
.def_path_hash(parent
.local_def_index
);
382 let def_path_hash
= key
.compute_stable_hash(parent_hash
);
384 debug
!("create_def: after disambiguation, key = {:?}", key
);
386 // Create the definition.
387 let def_id
= LocalDefId { local_def_index: self.table.allocate(key, def_path_hash) }
;
389 if expn_id
!= ExpnId
::root() {
390 self.expansions_that_defined
.insert(def_id
, expn_id
);
396 /// Initializes the `LocalDefId` to `HirId` mapping once it has been generated during
397 /// AST to HIR lowering.
398 pub fn init_def_id_to_hir_id_mapping(
400 mapping
: IndexVec
<LocalDefId
, Option
<hir
::HirId
>>,
403 self.def_id_to_hir_id
.is_empty(),
404 "trying to initialize `LocalDefId` <-> `HirId` mappings twice"
407 // Build the reverse mapping of `def_id_to_hir_id`.
408 self.hir_id_to_def_id
= mapping
410 .filter_map(|(def_id
, hir_id
)| hir_id
.map(|hir_id
| (hir_id
, def_id
)))
413 self.def_id_to_hir_id
= mapping
;
416 pub fn expansion_that_defined(&self, id
: LocalDefId
) -> ExpnId
{
417 self.expansions_that_defined
.get(&id
).copied().unwrap_or(ExpnId
::root())
420 pub fn parent_module_of_macro_def(&self, expn_id
: ExpnId
) -> DefId
{
421 self.parent_modules_of_macro_defs
[&expn_id
]
424 pub fn add_parent_module_of_macro_def(&mut self, expn_id
: ExpnId
, module
: DefId
) {
425 self.parent_modules_of_macro_defs
.insert(expn_id
, module
);
430 pub fn get_opt_name(&self) -> Option
<Symbol
> {
431 use self::DefPathData
::*;
433 TypeNs(name
) | ValueNs(name
) | MacroNs(name
) | LifetimeNs(name
) => Some(name
),
435 Impl
| CrateRoot
| Misc
| ClosureExpr
| Ctor
| AnonConst
| ImplTrait
=> None
,
439 pub fn as_symbol(&self) -> Symbol
{
440 use self::DefPathData
::*;
442 TypeNs(name
) | ValueNs(name
) | MacroNs(name
) | LifetimeNs(name
) => name
,
443 // Note that this does not show up in user print-outs.
444 CrateRoot
=> sym
::double_braced_crate
,
445 Impl
=> sym
::double_braced_impl
,
446 Misc
=> sym
::double_braced_misc
,
447 ClosureExpr
=> sym
::double_braced_closure
,
448 Ctor
=> sym
::double_braced_constructor
,
449 AnonConst
=> sym
::double_braced_constant
,
450 ImplTrait
=> sym
::double_braced_opaque
,
454 pub fn to_string(&self) -> String
{
455 self.as_symbol().to_string()