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}
;
9 use crate::def_path_hash_map
::DefPathHashMap
;
11 use rustc_data_structures
::fx
::FxHashMap
;
12 use rustc_data_structures
::stable_hasher
::StableHasher
;
13 use rustc_index
::vec
::IndexVec
;
14 use rustc_span
::symbol
::{kw, sym, Symbol}
;
16 use std
::fmt
::{self, Write}
;
19 /// The `DefPathTable` maps `DefIndex`es to `DefKey`s and vice versa.
20 /// Internally the `DefPathTable` holds a tree of `DefKey`s, where each `DefKey`
21 /// stores the `DefIndex` of its parent.
22 /// There is one `DefPathTable` for each crate.
23 #[derive(Clone, Default, Debug)]
24 pub struct DefPathTable
{
25 index_to_key
: IndexVec
<DefIndex
, DefKey
>,
26 def_path_hashes
: IndexVec
<DefIndex
, DefPathHash
>,
27 def_path_hash_to_index
: DefPathHashMap
,
31 fn allocate(&mut self, key
: DefKey
, def_path_hash
: DefPathHash
) -> DefIndex
{
33 let index
= DefIndex
::from(self.index_to_key
.len());
34 debug
!("DefPathTable::insert() - {:?} <-> {:?}", key
, index
);
35 self.index_to_key
.push(key
);
38 self.def_path_hashes
.push(def_path_hash
);
39 debug_assert
!(self.def_path_hashes
.len() == self.index_to_key
.len());
41 // Check for hash collisions of DefPathHashes. These should be
43 if let Some(existing
) = self.def_path_hash_to_index
.insert(&def_path_hash
, &index
) {
44 let def_path1
= DefPath
::make(LOCAL_CRATE
, existing
, |idx
| self.def_key(idx
));
45 let def_path2
= DefPath
::make(LOCAL_CRATE
, index
, |idx
| self.def_key(idx
));
47 // Continuing with colliding DefPathHashes can lead to correctness
48 // issues. We must abort compilation.
50 // The likelihood of such a collision is very small, so actually
51 // running into one could be indicative of a poor hash function
54 // See the documentation for DefPathHash for more information.
56 "found DefPathHash collision between {:?} and {:?}. \
57 Compilation cannot continue.",
62 // Assert that all DefPathHashes correctly contain the local crate's
64 #[cfg(debug_assertions)]
65 if let Some(root
) = self.def_path_hashes
.get(CRATE_DEF_INDEX
) {
66 assert
!(def_path_hash
.stable_crate_id() == root
.stable_crate_id());
73 pub fn def_key(&self, index
: DefIndex
) -> DefKey
{
74 self.index_to_key
[index
]
78 pub fn def_path_hash(&self, index
: DefIndex
) -> DefPathHash
{
79 let hash
= self.def_path_hashes
[index
];
80 debug
!("def_path_hash({:?}) = {:?}", index
, hash
);
84 pub fn enumerated_keys_and_path_hashes(
86 ) -> impl Iterator
<Item
= (DefIndex
, &DefKey
, &DefPathHash
)> + ExactSizeIterator
+ '_
{
89 .map(move |(index
, key
)| (index
, key
, &self.def_path_hashes
[index
]))
93 /// The definition table containing node definitions.
94 /// It holds the `DefPathTable` for `LocalDefId`s/`DefPath`s.
95 /// It also stores mappings to convert `LocalDefId`s to/from `HirId`s.
96 #[derive(Clone, Debug)]
97 pub struct Definitions
{
99 next_disambiguator
: FxHashMap
<(LocalDefId
, DefPathData
), u32>,
101 /// The [StableCrateId] of the local crate.
102 stable_crate_id
: StableCrateId
,
105 /// A unique identifier that we can use to lookup a definition
106 /// precisely. It combines the index of the definition's parent (if
107 /// any) with a `DisambiguatedDefPathData`.
108 #[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)]
111 pub parent
: Option
<DefIndex
>,
113 /// The identifier of this node.
114 pub disambiguated_data
: DisambiguatedDefPathData
,
118 pub(crate) fn compute_stable_hash(&self, parent
: DefPathHash
) -> DefPathHash
{
119 let mut hasher
= StableHasher
::new();
121 parent
.hash(&mut hasher
);
123 let DisambiguatedDefPathData { ref data, disambiguator }
= self.disambiguated_data
;
125 std
::mem
::discriminant(data
).hash(&mut hasher
);
126 if let Some(name
) = data
.get_opt_name() {
127 // Get a stable hash by considering the symbol chars rather than
129 name
.as_str().hash(&mut hasher
);
132 disambiguator
.hash(&mut hasher
);
134 let local_hash
: u64 = hasher
.finish();
136 // Construct the new DefPathHash, making sure that the `crate_id`
137 // portion of the hash is properly copied from the parent. This way the
138 // `crate_id` part will be recursively propagated from the root to all
139 // DefPathHashes in this DefPathTable.
140 DefPathHash
::new(parent
.stable_crate_id(), local_hash
)
144 pub fn get_opt_name(&self) -> Option
<Symbol
> {
145 self.disambiguated_data
.data
.get_opt_name()
149 /// A pair of `DefPathData` and an integer disambiguator. The integer is
150 /// normally `0`, but in the event that there are multiple defs with the
151 /// same `parent` and `data`, we use this field to disambiguate
152 /// between them. This introduces some artificial ordering dependency
153 /// but means that if you have, e.g., two impls for the same type in
154 /// the same module, they do get distinct `DefId`s.
155 #[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)]
156 pub struct DisambiguatedDefPathData
{
157 pub data
: DefPathData
,
158 pub disambiguator
: u32,
161 impl DisambiguatedDefPathData
{
162 pub fn fmt_maybe_verbose(&self, writer
: &mut impl Write
, verbose
: bool
) -> fmt
::Result
{
163 match self.data
.name() {
164 DefPathDataName
::Named(name
) => {
165 if verbose
&& self.disambiguator
!= 0 {
166 write
!(writer
, "{}#{}", name
, self.disambiguator
)
168 writer
.write_str(name
.as_str())
171 DefPathDataName
::Anon { namespace }
=> {
172 write
!(writer
, "{{{}#{}}}", namespace
, self.disambiguator
)
178 impl fmt
::Display
for DisambiguatedDefPathData
{
179 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
180 self.fmt_maybe_verbose(f
, true)
184 #[derive(Clone, Debug, Encodable, Decodable)]
186 /// The path leading from the crate root to the item.
187 pub data
: Vec
<DisambiguatedDefPathData
>,
189 /// The crate root this path is relative to.
194 pub fn make
<FN
>(krate
: CrateNum
, start_index
: DefIndex
, mut get_key
: FN
) -> DefPath
196 FN
: FnMut(DefIndex
) -> DefKey
,
198 let mut data
= vec
![];
199 let mut index
= Some(start_index
);
201 debug
!("DefPath::make: krate={:?} index={:?}", krate
, index
);
202 let p
= index
.unwrap();
203 let key
= get_key(p
);
204 debug
!("DefPath::make: key={:?}", key
);
205 match key
.disambiguated_data
.data
{
206 DefPathData
::CrateRoot
=> {
207 assert
!(key
.parent
.is_none());
211 data
.push(key
.disambiguated_data
);
217 DefPath { data, krate }
220 /// Returns a string representation of the `DefPath` without
221 /// the crate-prefix. This method is useful if you don't have
222 /// a `TyCtxt` available.
223 pub fn to_string_no_crate_verbose(&self) -> String
{
224 let mut s
= String
::with_capacity(self.data
.len() * 16);
226 for component
in &self.data
{
227 write
!(s
, "::{}", component
).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 write
!(s
, "{}", component
).unwrap();
250 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Encodable, Decodable)]
251 pub enum DefPathData
{
252 // Root: these should only be used for the root nodes, because
253 // they are treated specially by the `def_path` function.
254 /// The crate root (marker).
257 // Different kinds of items and item-like things:
260 /// An `extern` block.
264 /// A global asm item.
266 /// Something in the type namespace.
268 /// Something in the value namespace.
270 /// Something in the macro namespace.
272 /// Something in the lifetime namespace.
274 /// A closure expression.
277 // Subportions of items:
278 /// Implicit constructor for a unit or tuple-like struct or enum variant.
280 /// A constant expression (see `{ast,hir}::AnonConst`).
282 /// An `impl Trait` type node.
287 pub fn def_path_table(&self) -> &DefPathTable
{
291 /// Gets the number of definitions.
292 pub fn def_index_count(&self) -> usize {
293 self.table
.index_to_key
.len()
297 pub fn def_key(&self, id
: LocalDefId
) -> DefKey
{
298 self.table
.def_key(id
.local_def_index
)
302 pub fn def_path_hash(&self, id
: LocalDefId
) -> DefPathHash
{
303 self.table
.def_path_hash(id
.local_def_index
)
306 /// Returns the path from the crate root to `index`. The root
307 /// nodes are not included in the path (i.e., this will be an
308 /// empty vector for the crate root). For an inlined item, this
309 /// will be the path of the item in the external crate (but the
310 /// path will begin with the path to the external crate).
311 pub fn def_path(&self, id
: LocalDefId
) -> DefPath
{
312 DefPath
::make(LOCAL_CRATE
, id
.local_def_index
, |index
| {
313 self.def_key(LocalDefId { local_def_index: index }
)
317 /// Adds a root definition (no parent) and a few other reserved definitions.
318 pub fn new(stable_crate_id
: StableCrateId
) -> Definitions
{
321 disambiguated_data
: DisambiguatedDefPathData
{
322 data
: DefPathData
::CrateRoot
,
327 let parent_hash
= DefPathHash
::new(stable_crate_id
, 0);
328 let def_path_hash
= key
.compute_stable_hash(parent_hash
);
330 // Create the root definition.
331 let mut table
= DefPathTable
::default();
332 let root
= LocalDefId { local_def_index: table.allocate(key, def_path_hash) }
;
333 assert_eq
!(root
.local_def_index
, CRATE_DEF_INDEX
);
335 Definitions { table, next_disambiguator: Default::default(), stable_crate_id }
338 /// Adds a definition with a parent definition.
339 pub fn create_def(&mut self, parent
: LocalDefId
, data
: DefPathData
) -> LocalDefId
{
340 // We can't use `Debug` implementation for `LocalDefId` here, since it tries to acquire a
341 // reference to `Definitions` and we're already holding a mutable reference.
343 "create_def(parent={}, data={data:?})",
344 self.def_path(parent
).to_string_no_crate_verbose(),
347 // The root node must be created with `create_root_def()`.
348 assert
!(data
!= DefPathData
::CrateRoot
);
350 // Find the next free disambiguator for this key.
351 let disambiguator
= {
352 let next_disamb
= self.next_disambiguator
.entry((parent
, data
)).or_insert(0);
353 let disambiguator
= *next_disamb
;
354 *next_disamb
= next_disamb
.checked_add(1).expect("disambiguator overflow");
358 parent
: Some(parent
.local_def_index
),
359 disambiguated_data
: DisambiguatedDefPathData { data, disambiguator }
,
362 let parent_hash
= self.table
.def_path_hash(parent
.local_def_index
);
363 let def_path_hash
= key
.compute_stable_hash(parent_hash
);
365 debug
!("create_def: after disambiguation, key = {:?}", key
);
367 // Create the definition.
368 LocalDefId { local_def_index: self.table.allocate(key, def_path_hash) }
371 pub fn iter_local_def_id(&self) -> impl Iterator
<Item
= LocalDefId
> + '_
{
372 self.table
.def_path_hashes
.indices().map(|local_def_index
| LocalDefId { local_def_index }
)
376 pub fn local_def_path_hash_to_def_id(
379 err
: &mut dyn FnMut() -> !,
381 debug_assert
!(hash
.stable_crate_id() == self.stable_crate_id
);
383 .def_path_hash_to_index
385 .map(|local_def_index
| LocalDefId { local_def_index }
)
386 .unwrap_or_else(|| err())
389 pub fn def_path_hash_to_def_index_map(&self) -> &DefPathHashMap
{
390 &self.table
.def_path_hash_to_index
394 #[derive(Copy, Clone, PartialEq, Debug)]
395 pub enum DefPathDataName
{
397 Anon { namespace: Symbol }
,
401 pub fn get_opt_name(&self) -> Option
<Symbol
> {
402 use self::DefPathData
::*;
404 TypeNs(name
) | ValueNs(name
) | MacroNs(name
) | LifetimeNs(name
) => Some(name
),
406 Impl
| ForeignMod
| CrateRoot
| Use
| GlobalAsm
| ClosureExpr
| Ctor
| AnonConst
411 pub fn name(&self) -> DefPathDataName
{
412 use self::DefPathData
::*;
414 TypeNs(name
) | ValueNs(name
) | MacroNs(name
) | LifetimeNs(name
) => {
415 DefPathDataName
::Named(name
)
417 // Note that this does not show up in user print-outs.
418 CrateRoot
=> DefPathDataName
::Anon { namespace: kw::Crate }
,
419 Impl
=> DefPathDataName
::Anon { namespace: kw::Impl }
,
420 ForeignMod
=> DefPathDataName
::Anon { namespace: kw::Extern }
,
421 Use
=> DefPathDataName
::Anon { namespace: kw::Use }
,
422 GlobalAsm
=> DefPathDataName
::Anon { namespace: sym::global_asm }
,
423 ClosureExpr
=> DefPathDataName
::Anon { namespace: sym::closure }
,
424 Ctor
=> DefPathDataName
::Anon { namespace: sym::constructor }
,
425 AnonConst
=> DefPathDataName
::Anon { namespace: sym::constant }
,
426 ImplTrait
=> DefPathDataName
::Anon { namespace: sym::opaque }
,
431 impl fmt
::Display
for DefPathData
{
432 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
434 DefPathDataName
::Named(name
) => f
.write_str(name
.as_str()),
435 // FIXME(#70334): this will generate legacy {{closure}}, {{impl}}, etc
436 DefPathDataName
::Anon { namespace }
=> write
!(f
, "{{{{{}}}}}", namespace
),