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, DefIndex, LocalDefId, StableCrateId, CRATE_DEF_INDEX, LOCAL_CRATE}
;
11 use rustc_data_structures
::fx
::FxHashMap
;
12 use rustc_data_structures
::stable_hasher
::StableHasher
;
13 use rustc_data_structures
::unhash
::UnhashMap
;
14 use rustc_index
::vec
::IndexVec
;
15 use rustc_span
::hygiene
::ExpnId
;
16 use rustc_span
::symbol
::{kw, sym, Symbol}
;
18 use std
::fmt
::{self, Write}
;
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, Debug)]
27 pub struct DefPathTable
{
28 index_to_key
: IndexVec
<DefIndex
, DefKey
>,
29 def_path_hashes
: IndexVec
<DefIndex
, DefPathHash
>,
30 def_path_hash_to_index
: UnhashMap
<DefPathHash
, DefIndex
>,
34 fn allocate(&mut self, key
: DefKey
, def_path_hash
: DefPathHash
) -> DefIndex
{
36 let index
= DefIndex
::from(self.index_to_key
.len());
37 debug
!("DefPathTable::insert() - {:?} <-> {:?}", key
, index
);
38 self.index_to_key
.push(key
);
41 self.def_path_hashes
.push(def_path_hash
);
42 debug_assert
!(self.def_path_hashes
.len() == self.index_to_key
.len());
44 // Check for hash collisions of DefPathHashes. These should be
46 if let Some(existing
) = self.def_path_hash_to_index
.insert(def_path_hash
, index
) {
47 let def_path1
= DefPath
::make(LOCAL_CRATE
, existing
, |idx
| self.def_key(idx
));
48 let def_path2
= DefPath
::make(LOCAL_CRATE
, index
, |idx
| self.def_key(idx
));
50 // Continuing with colliding DefPathHashes can lead to correctness
51 // issues. We must abort compilation.
53 // The likelyhood of such a collision is very small, so actually
54 // running into one could be indicative of a poor hash function
57 // See the documentation for DefPathHash for more information.
59 "found DefPathHash collsion between {:?} and {:?}. \
60 Compilation cannot continue.",
65 // Assert that all DefPathHashes correctly contain the local crate's
67 #[cfg(debug_assertions)]
68 if let Some(root
) = self.def_path_hashes
.get(CRATE_DEF_INDEX
) {
69 assert
!(def_path_hash
.stable_crate_id() == root
.stable_crate_id());
76 pub fn def_key(&self, index
: DefIndex
) -> DefKey
{
77 self.index_to_key
[index
]
81 pub fn def_path_hash(&self, index
: DefIndex
) -> DefPathHash
{
82 let hash
= self.def_path_hashes
[index
];
83 debug
!("def_path_hash({:?}) = {:?}", index
, hash
);
87 pub fn enumerated_keys_and_path_hashes(
89 ) -> impl Iterator
<Item
= (DefIndex
, &DefKey
, &DefPathHash
)> + '_
{
92 .map(move |(index
, key
)| (index
, key
, &self.def_path_hashes
[index
]))
96 /// The definition table containing node definitions.
97 /// It holds the `DefPathTable` for `LocalDefId`s/`DefPath`s.
98 /// It also stores mappings to convert `LocalDefId`s to/from `HirId`s.
99 #[derive(Clone, Debug)]
100 pub struct Definitions
{
103 // FIXME(eddyb) ideally all `LocalDefId`s would be HIR owners.
104 pub(super) def_id_to_hir_id
: IndexVec
<LocalDefId
, Option
<hir
::HirId
>>,
105 /// The reverse mapping of `def_id_to_hir_id`.
106 pub(super) hir_id_to_def_id
: FxHashMap
<hir
::HirId
, LocalDefId
>,
108 /// Item with a given `LocalDefId` was defined during macro expansion with ID `ExpnId`.
109 expansions_that_defined
: FxHashMap
<LocalDefId
, ExpnId
>,
112 /// A unique identifier that we can use to lookup a definition
113 /// precisely. It combines the index of the definition's parent (if
114 /// any) with a `DisambiguatedDefPathData`.
115 #[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)]
118 pub parent
: Option
<DefIndex
>,
120 /// The identifier of this node.
121 pub disambiguated_data
: DisambiguatedDefPathData
,
125 pub(crate) fn compute_stable_hash(&self, parent
: DefPathHash
) -> DefPathHash
{
126 let mut hasher
= StableHasher
::new();
128 parent
.hash(&mut hasher
);
130 let DisambiguatedDefPathData { ref data, disambiguator }
= self.disambiguated_data
;
132 std
::mem
::discriminant(data
).hash(&mut hasher
);
133 if let Some(name
) = data
.get_opt_name() {
134 // Get a stable hash by considering the symbol chars rather than
136 name
.as_str().hash(&mut hasher
);
139 disambiguator
.hash(&mut hasher
);
141 let local_hash
: u64 = hasher
.finish();
143 // Construct the new DefPathHash, making sure that the `crate_id`
144 // portion of the hash is properly copied from the parent. This way the
145 // `crate_id` part will be recursively propagated from the root to all
146 // DefPathHashes in this DefPathTable.
147 DefPathHash
::new(parent
.stable_crate_id(), local_hash
)
151 /// A pair of `DefPathData` and an integer disambiguator. The integer is
152 /// normally `0`, but in the event that there are multiple defs with the
153 /// same `parent` and `data`, we use this field to disambiguate
154 /// between them. This introduces some artificial ordering dependency
155 /// but means that if you have, e.g., two impls for the same type in
156 /// the same module, they do get distinct `DefId`s.
157 #[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)]
158 pub struct DisambiguatedDefPathData
{
159 pub data
: DefPathData
,
160 pub disambiguator
: u32,
163 impl DisambiguatedDefPathData
{
164 pub fn fmt_maybe_verbose(&self, writer
: &mut impl Write
, verbose
: bool
) -> fmt
::Result
{
165 match self.data
.name() {
166 DefPathDataName
::Named(name
) => {
167 if verbose
&& self.disambiguator
!= 0 {
168 write
!(writer
, "{}#{}", name
, self.disambiguator
)
170 writer
.write_str(&name
.as_str())
173 DefPathDataName
::Anon { namespace }
=> {
174 write
!(writer
, "{{{}#{}}}", namespace
, self.disambiguator
)
180 impl fmt
::Display
for DisambiguatedDefPathData
{
181 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
182 self.fmt_maybe_verbose(f
, true)
186 #[derive(Clone, Debug, Encodable, Decodable)]
188 /// The path leading from the crate root to the item.
189 pub data
: Vec
<DisambiguatedDefPathData
>,
191 /// The crate root this path is relative to.
196 pub fn make
<FN
>(krate
: CrateNum
, start_index
: DefIndex
, mut get_key
: FN
) -> DefPath
198 FN
: FnMut(DefIndex
) -> DefKey
,
200 let mut data
= vec
![];
201 let mut index
= Some(start_index
);
203 debug
!("DefPath::make: krate={:?} index={:?}", krate
, index
);
204 let p
= index
.unwrap();
205 let key
= get_key(p
);
206 debug
!("DefPath::make: key={:?}", key
);
207 match key
.disambiguated_data
.data
{
208 DefPathData
::CrateRoot
=> {
209 assert
!(key
.parent
.is_none());
213 data
.push(key
.disambiguated_data
);
219 DefPath { data, krate }
222 /// Returns a string representation of the `DefPath` without
223 /// the crate-prefix. This method is useful if you don't have
224 /// a `TyCtxt` available.
225 pub fn to_string_no_crate_verbose(&self) -> String
{
226 let mut s
= String
::with_capacity(self.data
.len() * 16);
228 for component
in &self.data
{
229 write
!(s
, "::{}", component
).unwrap();
235 /// Returns a filename-friendly string of the `DefPath`, without
236 /// the crate-prefix. This method is useful if you don't have
237 /// a `TyCtxt` available.
238 pub fn to_filename_friendly_no_crate(&self) -> String
{
239 let mut s
= String
::with_capacity(self.data
.len() * 16);
241 let mut opt_delimiter
= None
;
242 for component
in &self.data
{
243 s
.extend(opt_delimiter
);
244 opt_delimiter
= Some('
-'
);
245 write
!(s
, "{}", component
).unwrap();
252 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Encodable, Decodable)]
253 pub enum DefPathData
{
254 // Root: these should only be used for the root nodes, because
255 // they are treated specially by the `def_path` function.
256 /// The crate root (marker).
258 // Catch-all for random `DefId` things like `DUMMY_NODE_ID`.
261 // Different kinds of items and item-like things:
264 /// Something in the type namespace.
266 /// Something in the value namespace.
268 /// Something in the macro namespace.
270 /// Something in the lifetime namespace.
272 /// A closure expression.
275 // Subportions of items:
276 /// Implicit constructor for a unit or tuple-like struct or enum variant.
278 /// A constant expression (see `{ast,hir}::AnonConst`).
280 /// An `impl Trait` type node.
285 pub fn def_path_table(&self) -> &DefPathTable
{
289 /// Gets the number of definitions.
290 pub fn def_index_count(&self) -> usize {
291 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 }
)
317 pub fn local_def_id_to_hir_id(&self, id
: LocalDefId
) -> hir
::HirId
{
318 self.def_id_to_hir_id
[id
].unwrap()
322 pub fn opt_hir_id_to_local_def_id(&self, hir_id
: hir
::HirId
) -> Option
<LocalDefId
> {
323 self.hir_id_to_def_id
.get(&hir_id
).copied()
326 /// Adds a root definition (no parent) and a few other reserved definitions.
327 pub fn new(stable_crate_id
: StableCrateId
) -> Definitions
{
330 disambiguated_data
: DisambiguatedDefPathData
{
331 data
: DefPathData
::CrateRoot
,
336 let parent_hash
= DefPathHash
::new(stable_crate_id
, 0);
337 let def_path_hash
= key
.compute_stable_hash(parent_hash
);
339 // Create the root definition.
340 let mut table
= DefPathTable
::default();
341 let root
= LocalDefId { local_def_index: table.allocate(key, def_path_hash) }
;
342 assert_eq
!(root
.local_def_index
, CRATE_DEF_INDEX
);
346 def_id_to_hir_id
: Default
::default(),
347 hir_id_to_def_id
: Default
::default(),
348 expansions_that_defined
: Default
::default(),
352 /// Retrieves the root definition.
353 pub fn get_root_def(&self) -> LocalDefId
{
354 LocalDefId { local_def_index: CRATE_DEF_INDEX }
357 /// Adds a definition with a parent definition.
363 mut next_disambiguator
: impl FnMut(LocalDefId
, DefPathData
) -> u32,
365 debug
!("create_def(parent={:?}, data={:?}, expn_id={:?})", parent
, data
, expn_id
);
367 // The root node must be created with `create_root_def()`.
368 assert
!(data
!= DefPathData
::CrateRoot
);
370 let disambiguator
= next_disambiguator(parent
, data
);
372 parent
: Some(parent
.local_def_index
),
373 disambiguated_data
: DisambiguatedDefPathData { data, disambiguator }
,
376 let parent_hash
= self.table
.def_path_hash(parent
.local_def_index
);
377 let def_path_hash
= key
.compute_stable_hash(parent_hash
);
379 debug
!("create_def: after disambiguation, key = {:?}", key
);
381 // Create the definition.
382 let def_id
= LocalDefId { local_def_index: self.table.allocate(key, def_path_hash) }
;
384 if expn_id
!= ExpnId
::root() {
385 self.expansions_that_defined
.insert(def_id
, expn_id
);
391 /// Initializes the `LocalDefId` to `HirId` mapping once it has been generated during
392 /// AST to HIR lowering.
393 pub fn init_def_id_to_hir_id_mapping(
395 mapping
: IndexVec
<LocalDefId
, Option
<hir
::HirId
>>,
398 self.def_id_to_hir_id
.is_empty(),
399 "trying to initialize `LocalDefId` <-> `HirId` mappings twice"
402 // Build the reverse mapping of `def_id_to_hir_id`.
403 self.hir_id_to_def_id
= mapping
405 .filter_map(|(def_id
, hir_id
)| hir_id
.map(|hir_id
| (hir_id
, def_id
)))
408 self.def_id_to_hir_id
= mapping
;
411 pub fn expansion_that_defined(&self, id
: LocalDefId
) -> ExpnId
{
412 self.expansions_that_defined
.get(&id
).copied().unwrap_or_else(ExpnId
::root
)
415 pub fn iter_local_def_id(&self) -> impl Iterator
<Item
= LocalDefId
> + '_
{
416 self.def_id_to_hir_id
.iter_enumerated().map(|(k
, _
)| k
)
420 pub fn local_def_path_hash_to_def_id(&self, hash
: DefPathHash
) -> Option
<LocalDefId
> {
422 .def_path_hash_to_index
424 .map(|&local_def_index
| LocalDefId { local_def_index }
)
428 #[derive(Copy, Clone, PartialEq, Debug)]
429 pub enum DefPathDataName
{
431 Anon { namespace: Symbol }
,
435 pub fn get_opt_name(&self) -> Option
<Symbol
> {
436 use self::DefPathData
::*;
438 TypeNs(name
) | ValueNs(name
) | MacroNs(name
) | LifetimeNs(name
) => Some(name
),
440 Impl
| CrateRoot
| Misc
| ClosureExpr
| Ctor
| AnonConst
| ImplTrait
=> None
,
444 pub fn name(&self) -> DefPathDataName
{
445 use self::DefPathData
::*;
447 TypeNs(name
) | ValueNs(name
) | MacroNs(name
) | LifetimeNs(name
) => {
448 DefPathDataName
::Named(name
)
450 // Note that this does not show up in user print-outs.
451 CrateRoot
=> DefPathDataName
::Anon { namespace: kw::Crate }
,
452 Impl
=> DefPathDataName
::Anon { namespace: kw::Impl }
,
453 Misc
=> DefPathDataName
::Anon { namespace: sym::misc }
,
454 ClosureExpr
=> DefPathDataName
::Anon { namespace: sym::closure }
,
455 Ctor
=> DefPathDataName
::Anon { namespace: sym::constructor }
,
456 AnonConst
=> DefPathDataName
::Anon { namespace: sym::constant }
,
457 ImplTrait
=> DefPathDataName
::Anon { namespace: sym::opaque }
,
462 impl fmt
::Display
for DefPathData
{
463 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
465 DefPathDataName
::Named(name
) => f
.write_str(&name
.as_str()),
466 // FIXME(#70334): this will generate legacy {{closure}}, {{impl}}, etc
467 DefPathDataName
::Anon { namespace }
=> write
!(f
, "{{{{{}}}}}", namespace
),