rustc_hir/
definitions.rs

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.
6
7use std::fmt::{self, Write};
8use std::hash::Hash;
9
10use rustc_data_structures::stable_hasher::StableHasher;
11use rustc_data_structures::unord::UnordMap;
12use rustc_hashes::Hash64;
13use rustc_index::IndexVec;
14use rustc_macros::{Decodable, Encodable};
15use rustc_span::{Symbol, kw, sym};
16use tracing::{debug, instrument};
17
18pub use crate::def_id::DefPathHash;
19use crate::def_id::{CRATE_DEF_INDEX, CrateNum, DefIndex, LOCAL_CRATE, LocalDefId, StableCrateId};
20use crate::def_path_hash_map::DefPathHashMap;
21
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(Debug)]
27pub struct DefPathTable {
28    stable_crate_id: StableCrateId,
29    index_to_key: IndexVec<DefIndex, DefKey>,
30    // We do only store the local hash, as all the definitions are from the current crate.
31    def_path_hashes: IndexVec<DefIndex, Hash64>,
32    def_path_hash_to_index: DefPathHashMap,
33}
34
35impl DefPathTable {
36    fn new(stable_crate_id: StableCrateId) -> DefPathTable {
37        DefPathTable {
38            stable_crate_id,
39            index_to_key: Default::default(),
40            def_path_hashes: Default::default(),
41            def_path_hash_to_index: Default::default(),
42        }
43    }
44
45    fn allocate(&mut self, key: DefKey, def_path_hash: DefPathHash) -> DefIndex {
46        // Assert that all DefPathHashes correctly contain the local crate's StableCrateId.
47        debug_assert_eq!(self.stable_crate_id, def_path_hash.stable_crate_id());
48        let local_hash = def_path_hash.local_hash();
49
50        let index = {
51            let index = DefIndex::from(self.index_to_key.len());
52            debug!("DefPathTable::insert() - {:?} <-> {:?}", key, index);
53            self.index_to_key.push(key);
54            index
55        };
56        self.def_path_hashes.push(local_hash);
57        debug_assert!(self.def_path_hashes.len() == self.index_to_key.len());
58
59        // Check for hash collisions of DefPathHashes. These should be
60        // exceedingly rare.
61        if let Some(existing) = self.def_path_hash_to_index.insert(&local_hash, &index) {
62            let def_path1 = DefPath::make(LOCAL_CRATE, existing, |idx| self.def_key(idx));
63            let def_path2 = DefPath::make(LOCAL_CRATE, index, |idx| self.def_key(idx));
64
65            // Continuing with colliding DefPathHashes can lead to correctness
66            // issues. We must abort compilation.
67            //
68            // The likelihood of such a collision is very small, so actually
69            // running into one could be indicative of a poor hash function
70            // being used.
71            //
72            // See the documentation for DefPathHash for more information.
73            panic!(
74                "found DefPathHash collision between {def_path1:?} and {def_path2:?}. \
75                    Compilation cannot continue."
76            );
77        }
78
79        index
80    }
81
82    #[inline(always)]
83    pub fn def_key(&self, index: DefIndex) -> DefKey {
84        self.index_to_key[index]
85    }
86
87    #[instrument(level = "trace", skip(self), ret)]
88    #[inline(always)]
89    pub fn def_path_hash(&self, index: DefIndex) -> DefPathHash {
90        let hash = self.def_path_hashes[index];
91        DefPathHash::new(self.stable_crate_id, hash)
92    }
93
94    pub fn enumerated_keys_and_path_hashes(
95        &self,
96    ) -> impl Iterator<Item = (DefIndex, &DefKey, DefPathHash)> + ExactSizeIterator {
97        self.index_to_key
98            .iter_enumerated()
99            .map(move |(index, key)| (index, key, self.def_path_hash(index)))
100    }
101}
102
103/// The definition table containing node definitions.
104/// It holds the `DefPathTable` for `LocalDefId`s/`DefPath`s.
105/// It also stores mappings to convert `LocalDefId`s to/from `HirId`s.
106#[derive(Debug)]
107pub struct Definitions {
108    table: DefPathTable,
109    next_disambiguator: UnordMap<(LocalDefId, DefPathData), u32>,
110}
111
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)]
116pub struct DefKey {
117    /// The parent path.
118    pub parent: Option<DefIndex>,
119
120    /// The identifier of this node.
121    pub disambiguated_data: DisambiguatedDefPathData,
122}
123
124impl DefKey {
125    pub(crate) fn compute_stable_hash(&self, parent: DefPathHash) -> DefPathHash {
126        let mut hasher = StableHasher::new();
127
128        parent.hash(&mut hasher);
129
130        let DisambiguatedDefPathData { ref data, disambiguator } = self.disambiguated_data;
131
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
135            // the symbol index.
136            name.as_str().hash(&mut hasher);
137        }
138
139        disambiguator.hash(&mut hasher);
140
141        let local_hash = hasher.finish();
142
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)
148    }
149
150    #[inline]
151    pub fn get_opt_name(&self) -> Option<Symbol> {
152        self.disambiguated_data.data.get_opt_name()
153    }
154}
155
156/// A pair of `DefPathData` and an integer disambiguator. The integer is
157/// normally `0`, but in the event that there are multiple defs with the
158/// same `parent` and `data`, we use this field to disambiguate
159/// between them. This introduces some artificial ordering dependency
160/// but means that if you have, e.g., two impls for the same type in
161/// the same module, they do get distinct `DefId`s.
162#[derive(Copy, Clone, PartialEq, Debug, Encodable, Decodable)]
163pub struct DisambiguatedDefPathData {
164    pub data: DefPathData,
165    pub disambiguator: u32,
166}
167
168impl DisambiguatedDefPathData {
169    pub fn fmt_maybe_verbose(&self, writer: &mut impl Write, verbose: bool) -> fmt::Result {
170        match self.data.name() {
171            DefPathDataName::Named(name) => {
172                if verbose && self.disambiguator != 0 {
173                    write!(writer, "{}#{}", name, self.disambiguator)
174                } else {
175                    writer.write_str(name.as_str())
176                }
177            }
178            DefPathDataName::Anon { namespace } => {
179                write!(writer, "{{{}#{}}}", namespace, self.disambiguator)
180            }
181        }
182    }
183}
184
185impl fmt::Display for DisambiguatedDefPathData {
186    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
187        self.fmt_maybe_verbose(f, true)
188    }
189}
190
191#[derive(Clone, Debug, Encodable, Decodable)]
192pub struct DefPath {
193    /// The path leading from the crate root to the item.
194    pub data: Vec<DisambiguatedDefPathData>,
195
196    /// The crate root this path is relative to.
197    pub krate: CrateNum,
198}
199
200impl DefPath {
201    pub fn make<FN>(krate: CrateNum, start_index: DefIndex, mut get_key: FN) -> DefPath
202    where
203        FN: FnMut(DefIndex) -> DefKey,
204    {
205        let mut data = vec![];
206        let mut index = Some(start_index);
207        loop {
208            debug!("DefPath::make: krate={:?} index={:?}", krate, index);
209            let p = index.unwrap();
210            let key = get_key(p);
211            debug!("DefPath::make: key={:?}", key);
212            match key.disambiguated_data.data {
213                DefPathData::CrateRoot => {
214                    assert!(key.parent.is_none());
215                    break;
216                }
217                _ => {
218                    data.push(key.disambiguated_data);
219                    index = key.parent;
220                }
221            }
222        }
223        data.reverse();
224        DefPath { data, krate }
225    }
226
227    /// Returns a string representation of the `DefPath` without
228    /// the crate-prefix. This method is useful if you don't have
229    /// a `TyCtxt` available.
230    pub fn to_string_no_crate_verbose(&self) -> String {
231        let mut s = String::with_capacity(self.data.len() * 16);
232
233        for component in &self.data {
234            write!(s, "::{component}").unwrap();
235        }
236
237        s
238    }
239
240    /// Returns a filename-friendly string of the `DefPath`, without
241    /// the crate-prefix. This method is useful if you don't have
242    /// a `TyCtxt` available.
243    pub fn to_filename_friendly_no_crate(&self) -> String {
244        let mut s = String::with_capacity(self.data.len() * 16);
245
246        let mut opt_delimiter = None;
247        for component in &self.data {
248            s.extend(opt_delimiter);
249            opt_delimiter = Some('-');
250            write!(s, "{component}").unwrap();
251        }
252
253        s
254    }
255}
256
257/// New variants should only be added in synchronization with `enum DefKind`.
258#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Encodable, Decodable)]
259pub enum DefPathData {
260    // Root: these should only be used for the root nodes, because
261    // they are treated specially by the `def_path` function.
262    /// The crate root (marker).
263    CrateRoot,
264
265    // Different kinds of items and item-like things:
266    /// An impl.
267    Impl,
268    /// An `extern` block.
269    ForeignMod,
270    /// A `use` item.
271    Use,
272    /// A global asm item.
273    GlobalAsm,
274    /// Something in the type namespace. Will be empty for RPITIT associated
275    /// types, which are given a synthetic name later, if necessary.
276    TypeNs(Option<Symbol>),
277    /// Something in the value namespace.
278    ValueNs(Symbol),
279    /// Something in the macro namespace.
280    MacroNs(Symbol),
281    /// Something in the lifetime namespace.
282    LifetimeNs(Symbol),
283    /// A closure expression.
284    Closure,
285
286    // Subportions of items:
287    /// Implicit constructor for a unit or tuple-like struct or enum variant.
288    Ctor,
289    /// A constant expression (see `{ast,hir}::AnonConst`).
290    AnonConst,
291    /// An existential `impl Trait` type node.
292    /// Argument position `impl Trait` have a `TypeNs` with their pretty-printed name.
293    OpaqueTy,
294}
295
296impl Definitions {
297    pub fn def_path_table(&self) -> &DefPathTable {
298        &self.table
299    }
300
301    /// Gets the number of definitions.
302    pub fn def_index_count(&self) -> usize {
303        self.table.index_to_key.len()
304    }
305
306    #[inline]
307    pub fn def_key(&self, id: LocalDefId) -> DefKey {
308        self.table.def_key(id.local_def_index)
309    }
310
311    #[inline(always)]
312    pub fn def_path_hash(&self, id: LocalDefId) -> DefPathHash {
313        self.table.def_path_hash(id.local_def_index)
314    }
315
316    /// Returns the path from the crate root to `index`. The root
317    /// nodes are not included in the path (i.e., this will be an
318    /// empty vector for the crate root). For an inlined item, this
319    /// will be the path of the item in the external crate (but the
320    /// path will begin with the path to the external crate).
321    pub fn def_path(&self, id: LocalDefId) -> DefPath {
322        DefPath::make(LOCAL_CRATE, id.local_def_index, |index| {
323            self.def_key(LocalDefId { local_def_index: index })
324        })
325    }
326
327    /// Adds a root definition (no parent) and a few other reserved definitions.
328    pub fn new(stable_crate_id: StableCrateId) -> Definitions {
329        let key = DefKey {
330            parent: None,
331            disambiguated_data: DisambiguatedDefPathData {
332                data: DefPathData::CrateRoot,
333                disambiguator: 0,
334            },
335        };
336
337        let parent_hash = DefPathHash::new(stable_crate_id, Hash64::ZERO);
338        let def_path_hash = key.compute_stable_hash(parent_hash);
339
340        // Create the root definition.
341        let mut table = DefPathTable::new(stable_crate_id);
342        let root = LocalDefId { local_def_index: table.allocate(key, def_path_hash) };
343        assert_eq!(root.local_def_index, CRATE_DEF_INDEX);
344
345        Definitions { table, next_disambiguator: Default::default() }
346    }
347
348    /// Adds a definition with a parent definition.
349    pub fn create_def(&mut self, parent: LocalDefId, data: DefPathData) -> LocalDefId {
350        // We can't use `Debug` implementation for `LocalDefId` here, since it tries to acquire a
351        // reference to `Definitions` and we're already holding a mutable reference.
352        debug!(
353            "create_def(parent={}, data={data:?})",
354            self.def_path(parent).to_string_no_crate_verbose(),
355        );
356
357        // The root node must be created with `create_root_def()`.
358        assert!(data != DefPathData::CrateRoot);
359
360        // Find the next free disambiguator for this key.
361        let disambiguator = {
362            let next_disamb = self.next_disambiguator.entry((parent, data)).or_insert(0);
363            let disambiguator = *next_disamb;
364            *next_disamb = next_disamb.checked_add(1).expect("disambiguator overflow");
365            disambiguator
366        };
367        let key = DefKey {
368            parent: Some(parent.local_def_index),
369            disambiguated_data: DisambiguatedDefPathData { data, disambiguator },
370        };
371
372        let parent_hash = self.table.def_path_hash(parent.local_def_index);
373        let def_path_hash = key.compute_stable_hash(parent_hash);
374
375        debug!("create_def: after disambiguation, key = {:?}", key);
376
377        // Create the definition.
378        LocalDefId { local_def_index: self.table.allocate(key, def_path_hash) }
379    }
380
381    #[inline(always)]
382    /// Returns `None` if the `DefPathHash` does not correspond to a `LocalDefId`
383    /// in the current compilation session. This can legitimately happen if the
384    /// `DefPathHash` is from a `DefId` in an upstream crate or, during incr. comp.,
385    /// if the `DefPathHash` is from a previous compilation session and
386    /// the def-path does not exist anymore.
387    pub fn local_def_path_hash_to_def_id(&self, hash: DefPathHash) -> Option<LocalDefId> {
388        debug_assert!(hash.stable_crate_id() == self.table.stable_crate_id);
389        self.table
390            .def_path_hash_to_index
391            .get(&hash.local_hash())
392            .map(|local_def_index| LocalDefId { local_def_index })
393    }
394
395    pub fn def_path_hash_to_def_index_map(&self) -> &DefPathHashMap {
396        &self.table.def_path_hash_to_index
397    }
398
399    pub fn num_definitions(&self) -> usize {
400        self.table.def_path_hashes.len()
401    }
402}
403
404#[derive(Copy, Clone, PartialEq, Debug)]
405pub enum DefPathDataName {
406    Named(Symbol),
407    Anon { namespace: Symbol },
408}
409
410impl DefPathData {
411    pub fn get_opt_name(&self) -> Option<Symbol> {
412        use self::DefPathData::*;
413        match *self {
414            TypeNs(name) => name,
415
416            ValueNs(name) | MacroNs(name) | LifetimeNs(name) => Some(name),
417
418            Impl | ForeignMod | CrateRoot | Use | GlobalAsm | Closure | Ctor | AnonConst
419            | OpaqueTy => None,
420        }
421    }
422
423    pub fn name(&self) -> DefPathDataName {
424        use self::DefPathData::*;
425        match *self {
426            TypeNs(name) => {
427                if let Some(name) = name {
428                    DefPathDataName::Named(name)
429                } else {
430                    DefPathDataName::Anon { namespace: sym::synthetic }
431                }
432            }
433            ValueNs(name) | MacroNs(name) | LifetimeNs(name) => DefPathDataName::Named(name),
434            // Note that this does not show up in user print-outs.
435            CrateRoot => DefPathDataName::Anon { namespace: kw::Crate },
436            Impl => DefPathDataName::Anon { namespace: kw::Impl },
437            ForeignMod => DefPathDataName::Anon { namespace: kw::Extern },
438            Use => DefPathDataName::Anon { namespace: kw::Use },
439            GlobalAsm => DefPathDataName::Anon { namespace: sym::global_asm },
440            Closure => DefPathDataName::Anon { namespace: sym::closure },
441            Ctor => DefPathDataName::Anon { namespace: sym::constructor },
442            AnonConst => DefPathDataName::Anon { namespace: sym::constant },
443            OpaqueTy => DefPathDataName::Anon { namespace: sym::opaque },
444        }
445    }
446}
447
448impl fmt::Display for DefPathData {
449    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
450        match self.name() {
451            DefPathDataName::Named(name) => f.write_str(name.as_str()),
452            // FIXME(#70334): this will generate legacy {{closure}}, {{impl}}, etc
453            DefPathDataName::Anon { namespace } => write!(f, "{{{{{namespace}}}}}"),
454        }
455    }
456}
rustc_hir/definitions.rs

rustc_hir/
definitions.rs
