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

rustc_span/
def_id.rs
