1 use crate::HashStableContext
;
2 use rustc_data_structures
::fingerprint
::Fingerprint
;
3 use rustc_data_structures
::stable_hasher
::{HashStable, StableHasher, ToStableHashKey}
;
4 use rustc_data_structures
::AtomicRef
;
5 use rustc_index
::vec
::Idx
;
6 use rustc_macros
::HashStable_Generic
;
7 use rustc_serialize
::{Decodable, Decoder, Encodable, Encoder}
;
8 use std
::borrow
::Borrow
;
10 use std
::hash
::{Hash, Hasher}
;
12 rustc_index
::newtype_index
! {
15 DEBUG_FORMAT
= "crate{}"
19 /// Item definitions in the currently-compiled crate would have the `CrateNum`
20 /// `LOCAL_CRATE` in their `DefId`.
21 pub const LOCAL_CRATE
: CrateNum
= CrateNum
::from_u32(0);
25 pub fn new(x
: usize) -> CrateNum
{
26 CrateNum
::from_usize(x
)
30 pub fn as_def_id(self) -> DefId
{
31 DefId { krate: self, index: CRATE_DEF_INDEX }
35 impl fmt
::Display
for CrateNum
{
36 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
37 fmt
::Display
::fmt(&self.private
, f
)
41 /// As a local identifier, a `CrateNum` is only meaningful within its context, e.g. within a tcx.
42 /// Therefore, make sure to include the context when encode a `CrateNum`.
43 impl<E
: Encoder
> Encodable
<E
> for CrateNum
{
44 default fn encode(&self, s
: &mut E
) {
45 s
.emit_u32(self.as_u32());
49 impl<D
: Decoder
> Decodable
<D
> for CrateNum
{
50 default fn decode(d
: &mut D
) -> CrateNum
{
51 CrateNum
::from_u32(d
.read_u32())
55 /// A `DefPathHash` is a fixed-size representation of a `DefPath` that is
56 /// stable across crate and compilation session boundaries. It consists of two
57 /// separate 64-bit hashes. The first uniquely identifies the crate this
58 /// `DefPathHash` originates from (see [StableCrateId]), and the second
59 /// uniquely identifies the corresponding `DefPath` within that crate. Together
60 /// they form a unique identifier within an entire crate graph.
62 /// There is a very small chance of hash collisions, which would mean that two
63 /// different `DefPath`s map to the same `DefPathHash`. Proceeding compilation
64 /// with such a hash collision would very probably lead to an ICE, and in the
65 /// worst case lead to a silent mis-compilation. The compiler therefore actively
66 /// and exhaustively checks for such hash collisions and aborts compilation if
69 /// `DefPathHash` uses 64-bit hashes for both the crate-id part and the
70 /// crate-internal part, even though it is likely that there are many more
71 /// `LocalDefId`s in a single crate than there are individual crates in a crate
72 /// graph. Since we use the same number of bits in both cases, the collision
73 /// probability for the crate-local part will be quite a bit higher (though
74 /// still very small).
76 /// This imbalance is not by accident: A hash collision in the
77 /// crate-local part of a `DefPathHash` will be detected and reported while
78 /// compiling the crate in question. Such a collision does not depend on
79 /// outside factors and can be easily fixed by the crate maintainer (e.g. by
80 /// renaming the item in question or by bumping the crate version in a harmless
83 /// A collision between crate-id hashes on the other hand is harder to fix
84 /// because it depends on the set of crates in the entire crate graph of a
85 /// compilation session. Again, using the same crate with a different version
86 /// number would fix the issue with a high probability -- but that might be
87 /// easier said then done if the crates in questions are dependencies of
88 /// third-party crates.
90 /// That being said, given a high quality hash function, the collision
91 /// probabilities in question are very small. For example, for a big crate like
92 /// `rustc_middle` (with ~50000 `LocalDefId`s as of the time of writing) there
93 /// is a probability of roughly 1 in 14,750,000,000 of a crate-internal
94 /// collision occurring. For a big crate graph with 1000 crates in it, there is
95 /// a probability of 1 in 36,890,000,000,000 of a `StableCrateId` collision.
96 #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)]
97 #[derive(HashStable_Generic, Encodable, Decodable)]
98 pub struct DefPathHash(pub Fingerprint
);
101 /// Returns the [StableCrateId] identifying the crate this [DefPathHash]
104 pub fn stable_crate_id(&self) -> StableCrateId
{
105 StableCrateId(self.0.as_value().0)
108 /// Returns the crate-local part of the [DefPathHash].
112 pub fn local_hash(&self) -> u64 {
116 /// Builds a new [DefPathHash] with the given [StableCrateId] and
117 /// `local_hash`, where `local_hash` must be unique within its crate.
118 pub fn new(stable_crate_id
: StableCrateId
, local_hash
: u64) -> DefPathHash
{
119 DefPathHash(Fingerprint
::new(stable_crate_id
.0, local_hash
))
123 impl Borrow
<Fingerprint
> for DefPathHash
{
125 fn borrow(&self) -> &Fingerprint
{
130 /// A [`StableCrateId`] is a 64-bit hash of a crate name, together with all
131 /// `-Cmetadata` arguments, and some other data. It is to [`CrateNum`] what [`DefPathHash`] is to
132 /// [`DefId`]. It is stable across compilation sessions.
134 /// Since the ID is a hash value, there is a small chance that two crates
135 /// end up with the same [`StableCrateId`]. The compiler will check for such
136 /// collisions when loading crates and abort compilation in order to avoid
139 /// For more information on the possibility of hash collisions in rustc,
140 /// see the discussion in [`DefId`].
141 #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)]
142 #[derive(HashStable_Generic, Encodable, Decodable)]
143 pub struct StableCrateId(pub(crate) u64);
146 pub fn to_u64(self) -> u64 {
150 /// Computes the stable ID for a crate with the given name and
151 /// `-Cmetadata` arguments.
152 pub fn new(crate_name
: &str, is_exe
: bool
, mut metadata
: Vec
<String
>) -> StableCrateId
{
153 let mut hasher
= StableHasher
::new();
154 crate_name
.hash(&mut hasher
);
156 // We don't want the stable crate ID to depend on the order of
157 // -C metadata arguments, so sort them:
159 // Every distinct -C metadata value is only incorporated once:
162 hasher
.write(b
"metadata");
164 // Also incorporate the length of a metadata string, so that we generate
165 // different values for `-Cmetadata=ab -Cmetadata=c` and
166 // `-Cmetadata=a -Cmetadata=bc`
167 hasher
.write_usize(s
.len());
168 hasher
.write(s
.as_bytes());
171 // Also incorporate crate type, so that we don't get symbol conflicts when
172 // linking against a library of the same name, if this is an executable.
173 hasher
.write(if is_exe { b"exe" }
else { b"lib" }
);
175 // Also incorporate the rustc version. Otherwise, with -Zsymbol-mangling-version=v0
176 // and no -Cmetadata, symbols from the same crate compiled with different versions of
177 // rustc are named the same.
179 // RUSTC_FORCE_RUSTC_VERSION is used to inject rustc version information
181 if let Some(val
) = std
::env
::var_os("RUSTC_FORCE_RUSTC_VERSION") {
182 hasher
.write(val
.to_string_lossy().into_owned().as_bytes())
184 hasher
.write(option_env
!("CFG_VERSION").unwrap_or("unknown version").as_bytes());
187 StableCrateId(hasher
.finish())
191 rustc_index
::newtype_index
! {
192 /// A DefIndex is an index into the hir-map for a crate, identifying a
193 /// particular definition. It should really be considered an interned
194 /// shorthand for a particular DefPath.
195 pub struct DefIndex
{
196 ENCODABLE
= custom
// (only encodable in metadata)
198 DEBUG_FORMAT
= "DefIndex({})",
199 /// The crate root is always assigned index 0 by the AST Map code,
200 /// thanks to `NodeCollector::new`.
201 const CRATE_DEF_INDEX
= 0,
205 impl<E
: Encoder
> Encodable
<E
> for DefIndex
{
206 default fn encode(&self, _
: &mut E
) {
207 panic
!("cannot encode `DefIndex` with `{}`", std
::any
::type_name
::<E
>());
211 impl<D
: Decoder
> Decodable
<D
> for DefIndex
{
212 default fn decode(_
: &mut D
) -> DefIndex
{
213 panic
!("cannot decode `DefIndex` with `{}`", std
::any
::type_name
::<D
>());
217 /// A `DefId` identifies a particular *definition*, by combining a crate
218 /// index and a def index.
220 /// You can create a `DefId` from a `LocalDefId` using `local_def_id.to_def_id()`.
221 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Copy)]
222 // On below-64 bit systems we can simply use the derived `Hash` impl
223 #[cfg_attr(not(target_pointer_width = "64"), derive(Hash))]
225 #[rustc_pass_by_value]
226 // We guarantee field order. Note that the order is essential here, see below why.
228 // cfg-ing the order of fields so that the `DefIndex` which is high entropy always ends up in
229 // the lower bits no matter the endianness. This allows the compiler to turn that `Hash` impl
230 // into a direct call to 'u64::hash(_)`.
231 #[cfg(not(all(target_pointer_width = "64", target_endian = "big")))]
234 #[cfg(all(target_pointer_width = "64", target_endian = "big"))]
238 // On 64-bit systems, we can hash the whole `DefId` as one `u64` instead of two `u32`s. This
239 // improves performance without impairing `FxHash` quality. So the below code gets compiled to a
240 // noop on little endian systems because the memory layout of `DefId` is as follows:
243 // +-1--------------31-+-32-------------63-+
245 // +-------------------+-------------------+
248 // The order here has direct impact on `FxHash` quality because we have far more `DefIndex` per
249 // crate than we have `Crate`s within one compilation. Or in other words, this arrangement puts
250 // more entropy in the low bits than the high bits. The reason this matters is that `FxHash`, which
251 // is used throughout rustc, has problems distributing the entropy from the high bits, so reversing
252 // the order would lead to a large number of collisions and thus far worse performance.
254 // On 64-bit big-endian systems, this compiles to a 64-bit rotation by 32 bits, which is still
255 // faster than another `FxHash` round.
256 #[cfg(target_pointer_width = "64")]
257 impl Hash
for DefId
{
258 fn hash
<H
: Hasher
>(&self, h
: &mut H
) {
259 (((self.krate
.as_u32() as u64) << 32) | (self.index
.as_u32() as u64)).hash(h
)
264 /// Makes a local `DefId` from the given `DefIndex`.
266 pub fn local(index
: DefIndex
) -> DefId
{
267 DefId { krate: LOCAL_CRATE, index }
270 /// Returns whether the item is defined in the crate currently being compiled.
272 pub fn is_local(self) -> bool
{
273 self.krate
== LOCAL_CRATE
277 pub fn as_local(self) -> Option
<LocalDefId
> {
278 if self.is_local() { Some(LocalDefId { local_def_index: self.index }
) } else { None }
283 pub fn expect_local(self) -> LocalDefId
{
284 // NOTE: `match` below is required to apply `#[track_caller]`,
285 // i.e. don't use closures.
286 match self.as_local() {
287 Some(local_def_id
) => local_def_id
,
288 None
=> panic
!("DefId::expect_local: `{:?}` isn't local", self),
293 pub fn is_crate_root(self) -> bool
{
294 self.index
== CRATE_DEF_INDEX
298 pub fn as_crate_root(self) -> Option
<CrateNum
> {
299 if self.is_crate_root() { Some(self.krate) }
else { None }
303 pub fn is_top_level_module(self) -> bool
{
304 self.is_local() && self.is_crate_root()
308 impl<E
: Encoder
> Encodable
<E
> for DefId
{
309 default fn encode(&self, s
: &mut E
) {
310 self.krate
.encode(s
);
311 self.index
.encode(s
);
315 impl<D
: Decoder
> Decodable
<D
> for DefId
{
316 default fn decode(d
: &mut D
) -> DefId
{
317 DefId { krate: Decodable::decode(d), index: Decodable::decode(d) }
321 pub fn default_def_id_debug(def_id
: DefId
, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
322 f
.debug_struct("DefId").field("krate", &def_id
.krate
).field("index", &def_id
.index
).finish()
325 pub static DEF_ID_DEBUG
: AtomicRef
<fn(DefId
, &mut fmt
::Formatter
<'_
>) -> fmt
::Result
> =
326 AtomicRef
::new(&(default_def_id_debug
as fn(_
, &mut fmt
::Formatter
<'_
>) -> _
));
328 impl fmt
::Debug
for DefId
{
329 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
330 (*DEF_ID_DEBUG
)(*self, f
)
334 rustc_data_structures
::define_id_collections
!(DefIdMap
, DefIdSet
, DefId
);
336 /// A `LocalDefId` is equivalent to a `DefId` with `krate == LOCAL_CRATE`. Since
337 /// we encode this information in the type, we can ensure at compile time that
338 /// no `DefId`s from upstream crates get thrown into the mix. There are quite a
339 /// few cases where we know that only `DefId`s from the local crate are expected;
340 /// a `DefId` from a different crate would signify a bug somewhere. This
341 /// is when `LocalDefId` comes in handy.
342 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
343 pub struct LocalDefId
{
344 pub local_def_index
: DefIndex
,
347 // To ensure correctness of incremental compilation,
348 // `LocalDefId` must not implement `Ord` or `PartialOrd`.
349 // See https://github.com/rust-lang/rust/issues/90317.
350 impl !Ord
for LocalDefId {}
351 impl !PartialOrd
for LocalDefId {}
353 pub const CRATE_DEF_ID
: LocalDefId
= LocalDefId { local_def_index: CRATE_DEF_INDEX }
;
355 impl Idx
for LocalDefId
{
357 fn new(idx
: usize) -> Self {
358 LocalDefId { local_def_index: Idx::new(idx) }
361 fn index(self) -> usize {
362 self.local_def_index
.index()
368 pub fn to_def_id(self) -> DefId
{
369 DefId { krate: LOCAL_CRATE, index: self.local_def_index }
373 pub fn is_top_level_module(self) -> bool
{
378 impl fmt
::Debug
for LocalDefId
{
379 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
380 self.to_def_id().fmt(f
)
384 impl<E
: Encoder
> Encodable
<E
> for LocalDefId
{
385 fn encode(&self, s
: &mut E
) {
386 self.to_def_id().encode(s
);
390 impl<D
: Decoder
> Decodable
<D
> for LocalDefId
{
391 fn decode(d
: &mut D
) -> LocalDefId
{
392 DefId
::decode(d
).expect_local()
396 rustc_data_structures
::define_id_collections
!(LocalDefIdMap
, LocalDefIdSet
, LocalDefId
);
398 impl<CTX
: HashStableContext
> HashStable
<CTX
> for DefId
{
400 fn hash_stable(&self, hcx
: &mut CTX
, hasher
: &mut StableHasher
) {
401 self.to_stable_hash_key(hcx
).hash_stable(hcx
, hasher
);
405 impl<CTX
: HashStableContext
> HashStable
<CTX
> for LocalDefId
{
407 fn hash_stable(&self, hcx
: &mut CTX
, hasher
: &mut StableHasher
) {
408 self.to_stable_hash_key(hcx
).hash_stable(hcx
, hasher
);
412 impl<CTX
: HashStableContext
> HashStable
<CTX
> for CrateNum
{
414 fn hash_stable(&self, hcx
: &mut CTX
, hasher
: &mut StableHasher
) {
415 self.to_stable_hash_key(hcx
).hash_stable(hcx
, hasher
);
419 impl<CTX
: HashStableContext
> ToStableHashKey
<CTX
> for DefId
{
420 type KeyType
= DefPathHash
;
423 fn to_stable_hash_key(&self, hcx
: &CTX
) -> DefPathHash
{
424 hcx
.def_path_hash(*self)
428 impl<CTX
: HashStableContext
> ToStableHashKey
<CTX
> for LocalDefId
{
429 type KeyType
= DefPathHash
;
432 fn to_stable_hash_key(&self, hcx
: &CTX
) -> DefPathHash
{
433 hcx
.def_path_hash(self.to_def_id())
437 impl<CTX
: HashStableContext
> ToStableHashKey
<CTX
> for CrateNum
{
438 type KeyType
= DefPathHash
;
441 fn to_stable_hash_key(&self, hcx
: &CTX
) -> DefPathHash
{
442 self.as_def_id().to_stable_hash_key(hcx
)