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, _1: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(state: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(name:"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}
549