rustc_span/
def_id.rs

Help
1use std::fmt;
2use std::hash::{BuildHasherDefault, Hash, Hasher};
3
4use rustc_data_structures::AtomicRef;
5use rustc_data_structures::fingerprint::Fingerprint;
6use rustc_data_structures::stable_hasher::{HashStable, StableHasher, StableOrd, ToStableHashKey};
7use rustc_data_structures::unhash::Unhasher;
8use rustc_hashes::Hash64;
9use rustc_index::Idx;
10use rustc_macros::{Decodable, Encodable, HashStable_Generic};
11use rustc_serialize::{Decodable, Encodable};
12
13use crate::{HashStableContext, SpanDecoder, SpanEncoder, Symbol};
14
15pub type StableCrateIdMap =
16    indexmap::IndexMap<StableCrateId, CrateNum, BuildHasherDefault<Unhasher>>;
17
18rustc_index::newtype_index! {
19    #[orderable]
20    #[debug_format = "crate{}"]
21    pub struct CrateNum {}
22}
23
24/// Item definitions in the currently-compiled crate would have the `CrateNum`
25/// `LOCAL_CRATE` in their `DefId`.
26pub const LOCAL_CRATE: CrateNum = CrateNum::ZERO;
27
28impl CrateNum {
29    #[inline]
30    pub fn new(x: usize) -> CrateNum {
31        CrateNum::from_usize(x)
32    }
33
34    // FIXME(typed_def_id): Replace this with `as_mod_def_id`.
35    #[inline]
36    pub fn as_def_id(self) -> DefId {
37        DefId { krate: self, index: CRATE_DEF_INDEX }
38    }
39
40    #[inline]
41    pub fn as_mod_def_id(self) -> ModDefId {
42        ModDefId::new_unchecked(DefId { krate: self, index: CRATE_DEF_INDEX })
43    }
44}
45
46impl fmt::Display for CrateNum {
47    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
48        fmt::Display::fmt(&self.as_u32(), f)
49    }
50}
51
52/// A `DefPathHash` is a fixed-size representation of a `DefPath` that is
53/// stable across crate and compilation session boundaries. It consists of two
54/// separate 64-bit hashes. The first uniquely identifies the crate this
55/// `DefPathHash` originates from (see [StableCrateId]), and the second
56/// uniquely identifies the corresponding `DefPath` within that crate. Together
57/// they form a unique identifier within an entire crate graph.
58///
59/// There is a very small chance of hash collisions, which would mean that two
60/// different `DefPath`s map to the same `DefPathHash`. Proceeding compilation
61/// with such a hash collision would very probably lead to an ICE, and in the
62/// worst case lead to a silent mis-compilation. The compiler therefore actively
63/// and exhaustively checks for such hash collisions and aborts compilation if
64/// it finds one.
65///
66/// `DefPathHash` uses 64-bit hashes for both the crate-id part and the
67/// crate-internal part, even though it is likely that there are many more
68/// `LocalDefId`s in a single crate than there are individual crates in a crate
69/// graph. Since we use the same number of bits in both cases, the collision
70/// probability for the crate-local part will be quite a bit higher (though
71/// still very small).
72///
73/// This imbalance is not by accident: A hash collision in the
74/// crate-local part of a `DefPathHash` will be detected and reported while
75/// compiling the crate in question. Such a collision does not depend on
76/// outside factors and can be easily fixed by the crate maintainer (e.g. by
77/// renaming the item in question or by bumping the crate version in a harmless
78/// way).
79///
80/// A collision between crate-id hashes on the other hand is harder to fix
81/// because it depends on the set of crates in the entire crate graph of a
82/// compilation session. Again, using the same crate with a different version
83/// number would fix the issue with a high probability -- but that might be
84/// easier said then done if the crates in questions are dependencies of
85/// third-party crates.
86///
87/// That being said, given a high quality hash function, the collision
88/// probabilities in question are very small. For example, for a big crate like
89/// `rustc_middle` (with ~50000 `LocalDefId`s as of the time of writing) there
90/// is a probability of roughly 1 in 14,750,000,000 of a crate-internal
91/// collision occurring. For a big crate graph with 1000 crates in it, there is
92/// a probability of 1 in 36,890,000,000,000 of a `StableCrateId` collision.
93#[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)]
94#[derive(HashStable_Generic, Encodable, Decodable)]
95pub struct DefPathHash(pub Fingerprint);
96
97impl DefPathHash {
98    /// Returns the [StableCrateId] identifying the crate this [DefPathHash]
99    /// originates from.
100    #[inline]
101    pub fn stable_crate_id(&self) -> StableCrateId {
102        StableCrateId(self.0.split().0)
103    }
104
105    /// Returns the crate-local part of the [DefPathHash].
106    #[inline]
107    pub fn local_hash(&self) -> Hash64 {
108        self.0.split().1
109    }
110
111    /// Builds a new [DefPathHash] with the given [StableCrateId] and
112    /// `local_hash`, where `local_hash` must be unique within its crate.
113    pub fn new(stable_crate_id: StableCrateId, local_hash: Hash64) -> DefPathHash {
114        DefPathHash(Fingerprint::new(stable_crate_id.0, local_hash))
115    }
116}
117
118impl Default for DefPathHash {
119    fn default() -> Self {
120        DefPathHash(Fingerprint::ZERO)
121    }
122}
123
124impl StableOrd for DefPathHash {
125    const CAN_USE_UNSTABLE_SORT: bool = true;
126
127    // `DefPathHash` sort order is not affected by (de)serialization.
128    const THIS_IMPLEMENTATION_HAS_BEEN_TRIPLE_CHECKED: () = ();
129}
130
131/// A [`StableCrateId`] is a 64-bit hash of a crate name, together with all
132/// `-Cmetadata` arguments, and some other data. It is to [`CrateNum`] what [`DefPathHash`] is to
133/// [`DefId`]. It is stable across compilation sessions.
134///
135/// Since the ID is a hash value, there is a small chance that two crates
136/// end up with the same [`StableCrateId`]. The compiler will check for such
137/// collisions when loading crates and abort compilation in order to avoid
138/// further trouble.
139///
140/// For more information on the possibility of hash collisions in rustc,
141/// see the discussion in [`DefId`].
142#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]
143#[derive(Hash, HashStable_Generic, Encodable, Decodable)]
144pub struct StableCrateId(pub(crate) Hash64);
145
146impl StableCrateId {
147    /// Computes the stable ID for a crate with the given name and
148    /// `-Cmetadata` arguments.
149    pub fn new(
150        crate_name: Symbol,
151        is_exe: bool,
152        mut metadata: Vec<String>,
153        cfg_version: &'static str,
154    ) -> StableCrateId {
155        let mut hasher = StableHasher::new();
156        // We must hash the string text of the crate name, not the id, as the id is not stable
157        // across builds.
158        crate_name.as_str().hash(&mut hasher);
159
160        // We don't want the stable crate ID to depend on the order of
161        // -C metadata arguments, so sort them:
162        metadata.sort();
163        // Every distinct -C metadata value is only incorporated once:
164        metadata.dedup();
165
166        hasher.write(b"metadata");
167        for s in &metadata {
168            // Also incorporate the length of a metadata string, so that we generate
169            // different values for `-Cmetadata=ab -Cmetadata=c` and
170            // `-Cmetadata=a -Cmetadata=bc`
171            hasher.write_usize(s.len());
172            hasher.write(s.as_bytes());
173        }
174
175        // Also incorporate crate type, so that we don't get symbol conflicts when
176        // linking against a library of the same name, if this is an executable.
177        hasher.write(if is_exe { b"exe" } else { b"lib" });
178
179        // Also incorporate the rustc version. Otherwise, with -Zsymbol-mangling-version=v0
180        // and no -Cmetadata, symbols from the same crate compiled with different versions of
181        // rustc are named the same.
182        //
183        // RUSTC_FORCE_RUSTC_VERSION is used to inject rustc version information
184        // during testing.
185        if let Some(val) = std::env::var_os("RUSTC_FORCE_RUSTC_VERSION") {
186            hasher.write(val.to_string_lossy().into_owned().as_bytes())
187        } else {
188            hasher.write(cfg_version.as_bytes())
189        }
190
191        StableCrateId(hasher.finish())
192    }
193
194    #[inline]
195    pub fn as_u64(self) -> u64 {
196        self.0.as_u64()
197    }
198}
199
200impl fmt::LowerHex for StableCrateId {
201    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
202        fmt::LowerHex::fmt(&self.0, f)
203    }
204}
205
206rustc_index::newtype_index! {
207    /// A DefIndex is an index into the hir-map for a crate, identifying a
208    /// particular definition. It should really be considered an interned
209    /// shorthand for a particular DefPath.
210    #[orderable]
211    #[debug_format = "DefIndex({})"]
212    pub struct DefIndex {
213        /// The crate root is always assigned index 0 by the AST Map code,
214        /// thanks to `NodeCollector::new`.
215        const CRATE_DEF_INDEX = 0;
216    }
217}
218
219/// A `DefId` identifies a particular *definition*, by combining a crate
220/// index and a def index.
221///
222/// You can create a `DefId` from a `LocalDefId` using `local_def_id.to_def_id()`.
223#[derive(Clone, PartialEq, Eq, Copy)]
224// On below-64 bit systems we can simply use the derived `Hash` impl
225#[cfg_attr(not(target_pointer_width = "64"), derive(Hash))]
226#[repr(C)]
227#[rustc_pass_by_value]
228// We guarantee field order. Note that the order is essential here, see below why.
229pub struct DefId {
230    // cfg-ing the order of fields so that the `DefIndex` which is high entropy always ends up in
231    // the lower bits no matter the endianness. This allows the compiler to turn that `Hash` impl
232    // into a direct call to `u64::hash(_)`.
233    #[cfg(not(all(target_pointer_width = "64", target_endian = "big")))]
234    pub index: DefIndex,
235    pub krate: CrateNum,
236    #[cfg(all(target_pointer_width = "64", target_endian = "big"))]
237    pub index: DefIndex,
238}
239
240// To ensure correctness of incremental compilation,
241// `DefId` must not implement `Ord` or `PartialOrd`.
242// See https://github.com/rust-lang/rust/issues/90317.
243impl !Ord for DefId {}
244impl !PartialOrd for DefId {}
245
246// On 64-bit systems, we can hash the whole `DefId` as one `u64` instead of two `u32`s. This
247// improves performance without impairing `FxHash` quality. So the below code gets compiled to a
248// noop on little endian systems because the memory layout of `DefId` is as follows:
249//
250// ```
251//     +-1--------------31-+-32-------------63-+
252//     ! index             ! krate             !
253//     +-------------------+-------------------+
254// ```
255//
256// The order here has direct impact on `FxHash` quality because we have far more `DefIndex` per
257// crate than we have `Crate`s within one compilation. Or in other words, this arrangement puts
258// more entropy in the low bits than the high bits. The reason this matters is that `FxHash`, which
259// is used throughout rustc, has problems distributing the entropy from the high bits, so reversing
260// the order would lead to a large number of collisions and thus far worse performance.
261//
262// On 64-bit big-endian systems, this compiles to a 64-bit rotation by 32 bits, which is still
263// faster than another `FxHash` round.
264#[cfg(target_pointer_width = "64")]
265impl Hash for DefId {
266    fn hash<H: Hasher>(&self, h: &mut H) {
267        (((self.krate.as_u32() as u64) << 32) | (self.index.as_u32() as u64)).hash(h)
268    }
269}
270
271impl DefId {
272    /// Makes a local `DefId` from the given `DefIndex`.
273    #[inline]
274    pub fn local(index: DefIndex) -> DefId {
275        DefId { krate: LOCAL_CRATE, index }
276    }
277
278    /// Returns whether the item is defined in the crate currently being compiled.
279    #[inline]
280    pub fn is_local(self) -> bool {
281        self.krate == LOCAL_CRATE
282    }
283
284    #[inline]
285    pub fn as_local(self) -> Option<LocalDefId> {
286        self.is_local().then(|| LocalDefId { local_def_index: self.index })
287    }
288
289    #[inline]
290    #[track_caller]
291    pub fn expect_local(self) -> LocalDefId {
292        // NOTE: `match` below is required to apply `#[track_caller]`,
293        // i.e. don't use closures.
294        match self.as_local() {
295            Some(local_def_id) => local_def_id,
296            None => panic!("DefId::expect_local: `{self:?}` isn't local"),
297        }
298    }
299
300    #[inline]
301    pub fn is_crate_root(self) -> bool {
302        self.index == CRATE_DEF_INDEX
303    }
304
305    #[inline]
306    pub fn as_crate_root(self) -> Option<CrateNum> {
307        self.is_crate_root().then_some(self.krate)
308    }
309
310    #[inline]
311    pub fn is_top_level_module(self) -> bool {
312        self.is_local() && self.is_crate_root()
313    }
314}
315
316impl From<LocalDefId> for DefId {
317    fn from(local: LocalDefId) -> DefId {
318        local.to_def_id()
319    }
320}
321
322pub fn default_def_id_debug(def_id: DefId, f: &mut fmt::Formatter<'_>) -> fmt::Result {
323    f.debug_struct("DefId").field("krate", &def_id.krate).field("index", &def_id.index).finish()
324}
325
326pub static DEF_ID_DEBUG: AtomicRef<fn(DefId, &mut fmt::Formatter<'_>) -> fmt::Result> =
327    AtomicRef::new(&(default_def_id_debug as fn(_, &mut fmt::Formatter<'_>) -> _));
328
329impl fmt::Debug for DefId {
330    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
331        (*DEF_ID_DEBUG)(*self, f)
332    }
333}
334
335rustc_data_structures::define_id_collections!(DefIdMap, DefIdSet, DefIdMapEntry, DefId);
336
337/// A `LocalDefId` is equivalent to a `DefId` with `krate == LOCAL_CRATE`. Since
338/// we encode this information in the type, we can ensure at compile time that
339/// no `DefId`s from upstream crates get thrown into the mix. There are quite a
340/// few cases where we know that only `DefId`s from the local crate are expected;
341/// a `DefId` from a different crate would signify a bug somewhere. This
342/// is when `LocalDefId` comes in handy.
343#[derive(Clone, Copy, PartialEq, Eq, Hash)]
344pub struct LocalDefId {
345    pub local_def_index: DefIndex,
346}
347
348// To ensure correctness of incremental compilation,
349// `LocalDefId` must not implement `Ord` or `PartialOrd`.
350// See https://github.com/rust-lang/rust/issues/90317.
351impl !Ord for LocalDefId {}
352impl !PartialOrd for LocalDefId {}
353
354pub const CRATE_DEF_ID: LocalDefId = LocalDefId { local_def_index: CRATE_DEF_INDEX };
355
356impl Idx for LocalDefId {
357    #[inline]
358    fn new(idx: usize) -> Self {
359        LocalDefId { local_def_index: Idx::new(idx) }
360    }
361    #[inline]
362    fn index(self) -> usize {
363        self.local_def_index.index()
364    }
365}
366
367impl LocalDefId {
368    #[inline]
369    pub fn to_def_id(self) -> DefId {
370        DefId { krate: LOCAL_CRATE, index: self.local_def_index }
371    }
372
373    #[inline]
374    pub fn is_top_level_module(self) -> bool {
375        self == CRATE_DEF_ID
376    }
377}
378
379impl fmt::Debug for LocalDefId {
380    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
381        self.to_def_id().fmt(f)
382    }
383}
384
385impl<E: SpanEncoder> Encodable<E> for LocalDefId {
386    fn encode(&self, s: &mut E) {
387        self.to_def_id().encode(s);
388    }
389}
390
391impl<D: SpanDecoder> Decodable<D> for LocalDefId {
392    fn decode(d: &mut D) -> LocalDefId {
393        DefId::decode(d).expect_local()
394    }
395}
396
397rustc_data_structures::define_id_collections!(
398    LocalDefIdMap,
399    LocalDefIdSet,
400    LocalDefIdMapEntry,
401    LocalDefId
402);
403
404impl<CTX: HashStableContext> HashStable<CTX> for DefId {
405    #[inline]
406    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
407        self.to_stable_hash_key(hcx).hash_stable(hcx, hasher);
408    }
409}
410
411impl<CTX: HashStableContext> HashStable<CTX> for LocalDefId {
412    #[inline]
413    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
414        self.to_stable_hash_key(hcx).hash_stable(hcx, hasher);
415    }
416}
417
418impl<CTX: HashStableContext> HashStable<CTX> for CrateNum {
419    #[inline]
420    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
421        self.to_stable_hash_key(hcx).hash_stable(hcx, hasher);
422    }
423}
424
425impl<CTX: HashStableContext> ToStableHashKey<CTX> for DefId {
426    type KeyType = DefPathHash;
427
428    #[inline]
429    fn to_stable_hash_key(&self, hcx: &CTX) -> DefPathHash {
430        hcx.def_path_hash(*self)
431    }
432}
433
434impl<CTX: HashStableContext> ToStableHashKey<CTX> for LocalDefId {
435    type KeyType = DefPathHash;
436
437    #[inline]
438    fn to_stable_hash_key(&self, hcx: &CTX) -> DefPathHash {
439        hcx.def_path_hash(self.to_def_id())
440    }
441}
442
443impl<CTX: HashStableContext> ToStableHashKey<CTX> for CrateNum {
444    type KeyType = DefPathHash;
445
446    #[inline]
447    fn to_stable_hash_key(&self, hcx: &CTX) -> DefPathHash {
448        self.as_def_id().to_stable_hash_key(hcx)
449    }
450}
451
452impl<CTX: HashStableContext> ToStableHashKey<CTX> for DefPathHash {
453    type KeyType = DefPathHash;
454
455    #[inline]
456    fn to_stable_hash_key(&self, _: &CTX) -> DefPathHash {
457        *self
458    }
459}
460
461macro_rules! typed_def_id {
462    ($Name:ident, $LocalName:ident) => {
463        #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Encodable, Decodable, HashStable_Generic)]
464        pub struct $Name(DefId);
465
466        impl $Name {
467            pub const fn new_unchecked(def_id: DefId) -> Self {
468                Self(def_id)
469            }
470
471            pub fn to_def_id(self) -> DefId {
472                self.into()
473            }
474
475            pub fn is_local(self) -> bool {
476                self.0.is_local()
477            }
478
479            pub fn as_local(self) -> Option<$LocalName> {
480                self.0.as_local().map($LocalName::new_unchecked)
481            }
482        }
483
484        impl From<$LocalName> for $Name {
485            fn from(local: $LocalName) -> Self {
486                Self(local.0.to_def_id())
487            }
488        }
489
490        impl From<$Name> for DefId {
491            fn from(typed: $Name) -> Self {
492                typed.0
493            }
494        }
495
496        #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Encodable, Decodable, HashStable_Generic)]
497        pub struct $LocalName(LocalDefId);
498
499        impl !Ord for $LocalName {}
500        impl !PartialOrd for $LocalName {}
501
502        impl $LocalName {
503            pub const fn new_unchecked(def_id: LocalDefId) -> Self {
504                Self(def_id)
505            }
506
507            pub fn to_def_id(self) -> DefId {
508                self.0.into()
509            }
510
511            pub fn to_local_def_id(self) -> LocalDefId {
512                self.0
513            }
514        }
515
516        impl From<$LocalName> for LocalDefId {
517            fn from(typed: $LocalName) -> Self {
518                typed.0
519            }
520        }
521
522        impl From<$LocalName> for DefId {
523            fn from(typed: $LocalName) -> Self {
524                typed.0.into()
525            }
526        }
527    };
528}
529
530// N.B.: when adding new typed `DefId`s update the corresponding trait impls in
531// `rustc_middle::dep_graph::def_node` for `DepNodeParams`.
532typed_def_id! { ModDefId, LocalModDefId }
533
534impl LocalModDefId {
535    pub const CRATE_DEF_ID: Self = Self::new_unchecked(CRATE_DEF_ID);
536}
537
538impl ModDefId {
539    pub fn is_top_level_module(self) -> bool {
540        self.0.is_top_level_module()
541    }
542}
543
544impl LocalModDefId {
545    pub fn is_top_level_module(self) -> bool {
546        self.0.is_top_level_module()
547    }
548}
rustc_span/def_id.rs

rustc_span/
def_id.rs
