]>
Commit | Line | Data |
---|---|---|
74b04a01 | 1 | use crate::HashStableContext; |
ba9703b0 | 2 | use rustc_data_structures::fingerprint::Fingerprint; |
136023e0 | 3 | use rustc_data_structures::stable_hasher::{HashStable, StableHasher, ToStableHashKey}; |
dfeec247 | 4 | use rustc_data_structures::AtomicRef; |
e74abb32 | 5 | use rustc_index::vec::Idx; |
ba9703b0 | 6 | use rustc_macros::HashStable_Generic; |
3dfed10e | 7 | use rustc_serialize::{Decodable, Decoder, Encodable, Encoder}; |
ba9703b0 | 8 | use std::borrow::Borrow; |
e9174d1e | 9 | use std::fmt; |
a2a8927a | 10 | use std::hash::{Hash, Hasher}; |
e9174d1e | 11 | |
e74abb32 | 12 | rustc_index::newtype_index! { |
17df50a5 | 13 | pub struct CrateNum { |
abe05a73 | 14 | ENCODABLE = custom |
17df50a5 | 15 | DEBUG_FORMAT = "crate{}" |
b7449926 XL |
16 | } |
17 | } | |
9e0c209e | 18 | |
e1599b0c XL |
19 | /// Item definitions in the currently-compiled crate would have the `CrateNum` |
20 | /// `LOCAL_CRATE` in their `DefId`. | |
17df50a5 | 21 | pub const LOCAL_CRATE: CrateNum = CrateNum::from_u32(0); |
476ff2be | 22 | |
9e0c209e | 23 | impl CrateNum { |
17df50a5 | 24 | #[inline] |
9e0c209e | 25 | pub fn new(x: usize) -> CrateNum { |
b7449926 XL |
26 | CrateNum::from_usize(x) |
27 | } | |
28 | ||
17df50a5 | 29 | #[inline] |
dfeec247 XL |
30 | pub fn as_def_id(&self) -> DefId { |
31 | DefId { krate: *self, index: CRATE_DEF_INDEX } | |
32 | } | |
9e0c209e SL |
33 | } |
34 | ||
35 | impl fmt::Display for CrateNum { | |
0bf4aa26 | 36 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
17df50a5 | 37 | fmt::Display::fmt(&self.private, f) |
9e0c209e SL |
38 | } |
39 | } | |
40 | ||
dfeec247 XL |
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`. | |
3dfed10e XL |
43 | impl<E: Encoder> Encodable<E> for CrateNum { |
44 | default fn encode(&self, s: &mut E) -> Result<(), E::Error> { | |
45 | s.emit_u32(self.as_u32()) | |
dfeec247 XL |
46 | } |
47 | } | |
3dfed10e XL |
48 | |
49 | impl<D: Decoder> Decodable<D> for CrateNum { | |
5099ac24 FG |
50 | default fn decode(d: &mut D) -> CrateNum { |
51 | CrateNum::from_u32(d.read_u32()) | |
dfeec247 XL |
52 | } |
53 | } | |
9e0c209e | 54 | |
6a06907d XL |
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. | |
61 | /// | |
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 | |
67 | /// it finds one. | |
68 | /// | |
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). | |
75 | /// | |
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 | |
81 | /// way). | |
82 | /// | |
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. | |
89 | /// | |
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. | |
3dfed10e XL |
96 | #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)] |
97 | #[derive(HashStable_Generic, Encodable, Decodable)] | |
ba9703b0 XL |
98 | pub struct DefPathHash(pub Fingerprint); |
99 | ||
6a06907d XL |
100 | impl DefPathHash { |
101 | /// Returns the [StableCrateId] identifying the crate this [DefPathHash] | |
102 | /// originates from. | |
103 | #[inline] | |
104 | pub fn stable_crate_id(&self) -> StableCrateId { | |
105 | StableCrateId(self.0.as_value().0) | |
106 | } | |
107 | ||
108 | /// Returns the crate-local part of the [DefPathHash]. | |
cdc7bbd5 XL |
109 | /// |
110 | /// Used for tests. | |
6a06907d XL |
111 | #[inline] |
112 | pub fn local_hash(&self) -> u64 { | |
113 | self.0.as_value().1 | |
114 | } | |
115 | ||
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)) | |
120 | } | |
121 | } | |
122 | ||
ba9703b0 XL |
123 | impl Borrow<Fingerprint> for DefPathHash { |
124 | #[inline] | |
125 | fn borrow(&self) -> &Fingerprint { | |
126 | &self.0 | |
127 | } | |
128 | } | |
129 | ||
a2a8927a XL |
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. | |
6a06907d | 133 | /// |
a2a8927a XL |
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 | |
6a06907d XL |
136 | /// collisions when loading crates and abort compilation in order to avoid |
137 | /// further trouble. | |
a2a8927a XL |
138 | /// |
139 | /// For more information on the possibility of hash collisions in rustc, | |
140 | /// see the discussion in [`DefId`]. | |
136023e0 XL |
141 | #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)] |
142 | #[derive(HashStable_Generic, Encodable, Decodable)] | |
143 | pub struct StableCrateId(pub(crate) u64); | |
6a06907d XL |
144 | |
145 | impl StableCrateId { | |
136023e0 XL |
146 | pub fn to_u64(self) -> u64 { |
147 | self.0 | |
148 | } | |
149 | ||
6a06907d | 150 | /// Computes the stable ID for a crate with the given name and |
136023e0 XL |
151 | /// `-Cmetadata` arguments. |
152 | pub fn new(crate_name: &str, is_exe: bool, mut metadata: Vec<String>) -> StableCrateId { | |
6a06907d XL |
153 | let mut hasher = StableHasher::new(); |
154 | crate_name.hash(&mut hasher); | |
136023e0 | 155 | |
a2a8927a | 156 | // We don't want the stable crate ID to depend on the order of |
136023e0 XL |
157 | // -C metadata arguments, so sort them: |
158 | metadata.sort(); | |
159 | // Every distinct -C metadata value is only incorporated once: | |
160 | metadata.dedup(); | |
161 | ||
162 | hasher.write(b"metadata"); | |
163 | for s in &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()); | |
169 | } | |
170 | ||
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" }); | |
174 | ||
a2a8927a XL |
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. | |
178 | // | |
5099ac24 | 179 | // RUSTC_FORCE_RUSTC_VERSION is used to inject rustc version information |
a2a8927a | 180 | // during testing. |
5099ac24 | 181 | if let Some(val) = std::env::var_os("RUSTC_FORCE_RUSTC_VERSION") { |
a2a8927a XL |
182 | hasher.write(val.to_string_lossy().into_owned().as_bytes()) |
183 | } else { | |
184 | hasher.write(option_env!("CFG_VERSION").unwrap_or("unknown version").as_bytes()); | |
185 | } | |
186 | ||
6a06907d XL |
187 | StableCrateId(hasher.finish()) |
188 | } | |
189 | } | |
190 | ||
e74abb32 | 191 | rustc_index::newtype_index! { |
48663c56 XL |
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 { | |
3dfed10e | 196 | ENCODABLE = custom // (only encodable in metadata) |
ea8adc8c | 197 | |
3dfed10e | 198 | DEBUG_FORMAT = "DefIndex({})", |
48663c56 XL |
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, | |
ea8adc8c XL |
202 | } |
203 | } | |
204 | ||
3dfed10e XL |
205 | impl<E: Encoder> Encodable<E> for DefIndex { |
206 | default fn encode(&self, _: &mut E) -> Result<(), E::Error> { | |
207 | panic!("cannot encode `DefIndex` with `{}`", std::any::type_name::<E>()); | |
208 | } | |
209 | } | |
210 | ||
211 | impl<D: Decoder> Decodable<D> for DefIndex { | |
5099ac24 | 212 | default fn decode(_: &mut D) -> DefIndex { |
3dfed10e XL |
213 | panic!("cannot decode `DefIndex` with `{}`", std::any::type_name::<D>()); |
214 | } | |
215 | } | |
b039eaaf | 216 | |
0bf4aa26 | 217 | /// A `DefId` identifies a particular *definition*, by combining a crate |
b039eaaf | 218 | /// index and a def index. |
f035d41b XL |
219 | /// |
220 | /// You can create a `DefId` from a `LocalDefId` using `local_def_id.to_def_id()`. | |
a2a8927a XL |
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))] | |
5099ac24 FG |
224 | #[repr(C)] |
225 | // We guarantee field order. Note that the order is essential here, see below why. | |
e9174d1e | 226 | pub struct DefId { |
5099ac24 FG |
227 | // cfg-ing the order of fields so that the `DefIndex` which is high entropy always ends up in |
228 | // the lower bits no matter the endianness. This allows the compiler to turn that `Hash` impl | |
229 | // into a direct call to 'u64::hash(_)`. | |
230 | #[cfg(not(all(target_pointer_width = "64", target_endian = "big")))] | |
b039eaaf | 231 | pub index: DefIndex, |
a2a8927a | 232 | pub krate: CrateNum, |
5099ac24 FG |
233 | #[cfg(all(target_pointer_width = "64", target_endian = "big"))] |
234 | pub index: DefIndex, | |
a2a8927a XL |
235 | } |
236 | ||
237 | // On 64-bit systems, we can hash the whole `DefId` as one `u64` instead of two `u32`s. This | |
238 | // improves performance without impairing `FxHash` quality. So the below code gets compiled to a | |
239 | // noop on little endian systems because the memory layout of `DefId` is as follows: | |
240 | // | |
241 | // ``` | |
242 | // +-1--------------31-+-32-------------63-+ | |
243 | // ! index ! krate ! | |
244 | // +-------------------+-------------------+ | |
245 | // ``` | |
246 | // | |
247 | // The order here has direct impact on `FxHash` quality because we have far more `DefIndex` per | |
248 | // crate than we have `Crate`s within one compilation. Or in other words, this arrangement puts | |
249 | // more entropy in the low bits than the high bits. The reason this matters is that `FxHash`, which | |
250 | // is used throughout rustc, has problems distributing the entropy from the high bits, so reversing | |
251 | // the order would lead to a large number of collisions and thus far worse performance. | |
252 | // | |
253 | // On 64-bit big-endian systems, this compiles to a 64-bit rotation by 32 bits, which is still | |
254 | // faster than another `FxHash` round. | |
255 | #[cfg(target_pointer_width = "64")] | |
256 | impl Hash for DefId { | |
257 | fn hash<H: Hasher>(&self, h: &mut H) { | |
258 | (((self.krate.as_u32() as u64) << 32) | (self.index.as_u32() as u64)).hash(h) | |
259 | } | |
e9174d1e SL |
260 | } |
261 | ||
e9174d1e | 262 | impl DefId { |
9fa01778 | 263 | /// Makes a local `DefId` from the given `DefIndex`. |
abe05a73 | 264 | #[inline] |
b039eaaf | 265 | pub fn local(index: DefIndex) -> DefId { |
74b04a01 | 266 | DefId { krate: LOCAL_CRATE, index } |
e9174d1e SL |
267 | } |
268 | ||
29967ef6 | 269 | /// Returns whether the item is defined in the crate currently being compiled. |
abe05a73 XL |
270 | #[inline] |
271 | pub fn is_local(self) -> bool { | |
e9174d1e SL |
272 | self.krate == LOCAL_CRATE |
273 | } | |
abe05a73 XL |
274 | |
275 | #[inline] | |
ba9703b0 XL |
276 | pub fn as_local(self) -> Option<LocalDefId> { |
277 | if self.is_local() { Some(LocalDefId { local_def_index: self.index }) } else { None } | |
278 | } | |
279 | ||
280 | #[inline] | |
281 | pub fn expect_local(self) -> LocalDefId { | |
282 | self.as_local().unwrap_or_else(|| panic!("DefId::expect_local: `{:?}` isn't local", self)) | |
abe05a73 | 283 | } |
0731742a | 284 | |
dfeec247 XL |
285 | pub fn is_top_level_module(self) -> bool { |
286 | self.is_local() && self.index == CRATE_DEF_INDEX | |
0731742a | 287 | } |
e9174d1e | 288 | } |
abe05a73 | 289 | |
3dfed10e XL |
290 | impl<E: Encoder> Encodable<E> for DefId { |
291 | default fn encode(&self, s: &mut E) -> Result<(), E::Error> { | |
17df50a5 XL |
292 | s.emit_struct(false, |s| { |
293 | s.emit_struct_field("krate", true, |s| self.krate.encode(s))?; | |
3dfed10e | 294 | |
17df50a5 | 295 | s.emit_struct_field("index", false, |s| self.index.encode(s)) |
3dfed10e | 296 | }) |
dfeec247 XL |
297 | } |
298 | } | |
3dfed10e XL |
299 | |
300 | impl<D: Decoder> Decodable<D> for DefId { | |
5099ac24 FG |
301 | default fn decode(d: &mut D) -> DefId { |
302 | d.read_struct(|d| DefId { | |
303 | krate: d.read_struct_field("krate", Decodable::decode), | |
304 | index: d.read_struct_field("index", Decodable::decode), | |
3dfed10e | 305 | }) |
dfeec247 XL |
306 | } |
307 | } | |
308 | ||
309 | pub fn default_def_id_debug(def_id: DefId, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
310 | f.debug_struct("DefId").field("krate", &def_id.krate).field("index", &def_id.index).finish() | |
311 | } | |
312 | ||
313 | pub static DEF_ID_DEBUG: AtomicRef<fn(DefId, &mut fmt::Formatter<'_>) -> fmt::Result> = | |
314 | AtomicRef::new(&(default_def_id_debug as fn(_, &mut fmt::Formatter<'_>) -> _)); | |
315 | ||
316 | impl fmt::Debug for DefId { | |
317 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
318 | (*DEF_ID_DEBUG)(*self, f) | |
319 | } | |
320 | } | |
321 | ||
322 | rustc_data_structures::define_id_collections!(DefIdMap, DefIdSet, DefId); | |
abe05a73 | 323 | |
a2a8927a | 324 | /// A `LocalDefId` is equivalent to a `DefId` with `krate == LOCAL_CRATE`. Since |
abe05a73 | 325 | /// we encode this information in the type, we can ensure at compile time that |
a2a8927a XL |
326 | /// no `DefId`s from upstream crates get thrown into the mix. There are quite a |
327 | /// few cases where we know that only `DefId`s from the local crate are expected; | |
328 | /// a `DefId` from a different crate would signify a bug somewhere. This | |
329 | /// is when `LocalDefId` comes in handy. | |
330 | #[derive(Clone, Copy, PartialEq, Eq, Hash)] | |
ba9703b0 XL |
331 | pub struct LocalDefId { |
332 | pub local_def_index: DefIndex, | |
333 | } | |
abe05a73 | 334 | |
a2a8927a XL |
335 | // To ensure correctness of incremental compilation, |
336 | // `LocalDefId` must not implement `Ord` or `PartialOrd`. | |
337 | // See https://github.com/rust-lang/rust/issues/90317. | |
338 | impl !Ord for LocalDefId {} | |
339 | impl !PartialOrd for LocalDefId {} | |
340 | ||
6a06907d XL |
341 | pub const CRATE_DEF_ID: LocalDefId = LocalDefId { local_def_index: CRATE_DEF_INDEX }; |
342 | ||
ba9703b0 | 343 | impl Idx for LocalDefId { |
abe05a73 | 344 | #[inline] |
ba9703b0 XL |
345 | fn new(idx: usize) -> Self { |
346 | LocalDefId { local_def_index: Idx::new(idx) } | |
abe05a73 | 347 | } |
ba9703b0 XL |
348 | #[inline] |
349 | fn index(self) -> usize { | |
350 | self.local_def_index.index() | |
351 | } | |
352 | } | |
abe05a73 | 353 | |
ba9703b0 | 354 | impl LocalDefId { |
abe05a73 XL |
355 | #[inline] |
356 | pub fn to_def_id(self) -> DefId { | |
ba9703b0 XL |
357 | DefId { krate: LOCAL_CRATE, index: self.local_def_index } |
358 | } | |
359 | ||
360 | #[inline] | |
361 | pub fn is_top_level_module(self) -> bool { | |
362 | self.local_def_index == CRATE_DEF_INDEX | |
abe05a73 XL |
363 | } |
364 | } | |
365 | ||
366 | impl fmt::Debug for LocalDefId { | |
0bf4aa26 | 367 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
abe05a73 XL |
368 | self.to_def_id().fmt(f) |
369 | } | |
370 | } | |
371 | ||
3dfed10e XL |
372 | impl<E: Encoder> Encodable<E> for LocalDefId { |
373 | fn encode(&self, s: &mut E) -> Result<(), E::Error> { | |
374 | self.to_def_id().encode(s) | |
375 | } | |
376 | } | |
377 | ||
378 | impl<D: Decoder> Decodable<D> for LocalDefId { | |
5099ac24 FG |
379 | fn decode(d: &mut D) -> LocalDefId { |
380 | DefId::decode(d).expect_local() | |
3dfed10e XL |
381 | } |
382 | } | |
74b04a01 | 383 | |
6a06907d XL |
384 | rustc_data_structures::define_id_collections!(LocalDefIdMap, LocalDefIdSet, LocalDefId); |
385 | ||
74b04a01 | 386 | impl<CTX: HashStableContext> HashStable<CTX> for DefId { |
136023e0 | 387 | #[inline] |
74b04a01 | 388 | fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { |
136023e0 XL |
389 | self.to_stable_hash_key(hcx).hash_stable(hcx, hasher); |
390 | } | |
391 | } | |
392 | ||
393 | impl<CTX: HashStableContext> HashStable<CTX> for LocalDefId { | |
394 | #[inline] | |
395 | fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { | |
396 | self.to_stable_hash_key(hcx).hash_stable(hcx, hasher); | |
74b04a01 XL |
397 | } |
398 | } | |
3dfed10e XL |
399 | |
400 | impl<CTX: HashStableContext> HashStable<CTX> for CrateNum { | |
136023e0 | 401 | #[inline] |
3dfed10e | 402 | fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { |
136023e0 XL |
403 | self.to_stable_hash_key(hcx).hash_stable(hcx, hasher); |
404 | } | |
405 | } | |
406 | ||
407 | impl<CTX: HashStableContext> ToStableHashKey<CTX> for DefId { | |
408 | type KeyType = DefPathHash; | |
409 | ||
410 | #[inline] | |
411 | fn to_stable_hash_key(&self, hcx: &CTX) -> DefPathHash { | |
412 | hcx.def_path_hash(*self) | |
413 | } | |
414 | } | |
415 | ||
416 | impl<CTX: HashStableContext> ToStableHashKey<CTX> for LocalDefId { | |
417 | type KeyType = DefPathHash; | |
418 | ||
419 | #[inline] | |
420 | fn to_stable_hash_key(&self, hcx: &CTX) -> DefPathHash { | |
421 | hcx.def_path_hash(self.to_def_id()) | |
422 | } | |
423 | } | |
424 | ||
425 | impl<CTX: HashStableContext> ToStableHashKey<CTX> for CrateNum { | |
426 | type KeyType = DefPathHash; | |
427 | ||
428 | #[inline] | |
429 | fn to_stable_hash_key(&self, hcx: &CTX) -> DefPathHash { | |
430 | self.as_def_id().to_stable_hash_key(hcx) | |
3dfed10e XL |
431 | } |
432 | } |