1 use crate::sip128::SipHasher128;
2 use rustc_index::bit_set;
4 use smallvec::SmallVec;
5 use std::hash::{BuildHasher, Hash, Hasher};
11 /// When hashing something that ends up affecting properties like symbol names,
12 /// we want these symbol names to be calculated independently of other factors
13 /// like what architecture you're compiling *from*.
15 /// To that end we always convert integers to little-endian format before
16 /// hashing and the architecture dependent `isize` and `usize` types are
17 /// extended to 64 bits if needed.
18 pub struct StableHasher {
22 impl ::std::fmt::Debug for StableHasher {
23 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
24 write!(f, "{:?}", self.state)
28 pub trait StableHasherResult: Sized {
29 fn finish(hasher: StableHasher) -> Self;
34 pub fn new() -> Self {
35 StableHasher { state: SipHasher128::new_with_keys(0, 0) }
39 pub fn finish<W: StableHasherResult>(self) -> W {
44 impl StableHasherResult for u128 {
46 fn finish(hasher: StableHasher) -> Self {
47 let (_0, _1) = hasher.finalize();
48 u128::from(_0) | (u128::from(_1) << 64)
52 impl StableHasherResult for u64 {
54 fn finish(hasher: StableHasher) -> Self {
61 pub fn finalize(self) -> (u64, u64) {
62 self.state.finish128()
66 impl Hasher for StableHasher {
67 fn finish(&self) -> u64 {
68 panic!("use StableHasher::finalize instead");
72 fn write(&mut self, bytes: &[u8]) {
73 self.state.write(bytes);
77 fn write_str(&mut self, s: &str) {
78 self.state.write_str(s);
82 fn write_length_prefix(&mut self, len: usize) {
83 // Our impl for `usize` will extend it if needed.
84 self.write_usize(len);
88 fn write_u8(&mut self, i: u8) {
89 self.state.write_u8(i);
93 fn write_u16(&mut self, i: u16) {
94 self.state.short_write(i.to_le_bytes());
98 fn write_u32(&mut self, i: u32) {
99 self.state.short_write(i.to_le_bytes());
103 fn write_u64(&mut self, i: u64) {
104 self.state.short_write(i.to_le_bytes());
108 fn write_u128(&mut self, i: u128) {
109 self.state.write(&i.to_le_bytes());
113 fn write_usize(&mut self, i: usize) {
114 // Always treat usize as u64 so we get the same results on 32 and 64 bit
115 // platforms. This is important for symbol hashes when cross compiling,
117 self.state.short_write((i as u64).to_le_bytes());
121 fn write_i8(&mut self, i: i8) {
122 self.state.write_i8(i);
126 fn write_i16(&mut self, i: i16) {
127 self.state.short_write((i as u16).to_le_bytes());
131 fn write_i32(&mut self, i: i32) {
132 self.state.short_write((i as u32).to_le_bytes());
136 fn write_i64(&mut self, i: i64) {
137 self.state.short_write((i as u64).to_le_bytes());
141 fn write_i128(&mut self, i: i128) {
142 self.state.write(&(i as u128).to_le_bytes());
146 fn write_isize(&mut self, i: isize) {
147 // Always treat isize as a 64-bit number so we get the same results on 32 and 64 bit
148 // platforms. This is important for symbol hashes when cross compiling,
149 // for example. Sign extending here is preferable as it means that the
150 // same negative number hashes the same on both 32 and 64 bit platforms.
151 let value = i as u64;
156 fn hash_value(state: &mut SipHasher128, value: u64) {
157 state.write_u8(0xFF);
158 state.short_write(value.to_le_bytes());
161 // `isize` values often seem to have a small (positive) numeric value in practice.
162 // To exploit this, if the value is small, we will hash a smaller amount of bytes.
163 // However, we cannot just skip the leading zero bytes, as that would produce the same hash
164 // e.g. if you hash two values that have the same bit pattern when they are swapped.
165 // See https://github.com/rust-lang/rust/pull/93014 for context.
167 // Therefore, we employ the following strategy:
168 // 1) When we encounter a value that fits within a single byte (the most common case), we
169 // hash just that byte. This is the most common case that is being optimized. However, we do
170 // not do this for the value 0xFF, as that is a reserved prefix (a bit like in UTF-8).
171 // 2) When we encounter a larger value, we hash a "marker" 0xFF and then the corresponding
172 // 8 bytes. Since this prefix cannot occur when we hash a single byte, when we hash two
173 // `isize`s that fit within a different amount of bytes, they should always produce a different
174 // byte stream for the hasher.
176 self.state.write_u8(value as u8);
178 hash_value(&mut self.state, value);
183 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
184 /// stable across multiple compilation sessions.
186 /// Note that `HashStable` imposes rather more strict requirements than usual
189 /// - Stable hashes are sometimes used as identifiers. Therefore they must
190 /// conform to the corresponding `PartialEq` implementations:
192 /// - `x == y` implies `hash_stable(x) == hash_stable(y)`, and
193 /// - `x != y` implies `hash_stable(x) != hash_stable(y)`.
195 /// That second condition is usually not required for hash functions
196 /// (e.g. `Hash`). In practice this means that `hash_stable` must feed any
197 /// information into the hasher that a `PartialEq` comparison takes into
198 /// account. See [#49300](https://github.com/rust-lang/rust/issues/49300)
199 /// for an example where violating this invariant has caused trouble in the
202 /// - `hash_stable()` must be independent of the current
203 /// compilation session. E.g. they must not hash memory addresses or other
204 /// things that are "randomly" assigned per compilation session.
206 /// - `hash_stable()` must be independent of the host architecture. The
207 /// `StableHasher` takes care of endianness and `isize`/`usize` platform
209 pub trait HashStable<CTX> {
210 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher);
213 /// Implement this for types that can be turned into stable keys like, for
214 /// example, for DefId that can be converted to a DefPathHash. This is used for
215 /// bringing maps into a predictable order before hashing them.
216 pub trait ToStableHashKey<HCX> {
217 type KeyType: Ord + Sized + HashStable<HCX>;
218 fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
221 /// Implement HashStable by just calling `Hash::hash()`.
223 /// **WARNING** This is only valid for types that *really* don't need any context for fingerprinting.
224 /// But it is easy to misuse this macro (see [#96013](https://github.com/rust-lang/rust/issues/96013)
225 /// for examples). Therefore this macro is not exported and should only be used in the limited cases
226 /// here in this module.
228 /// Use `#[derive(HashStable_Generic)]` instead.
229 macro_rules! impl_stable_hash_via_hash {
231 impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
233 fn hash_stable(&self, _: &mut CTX, hasher: &mut $crate::stable_hasher::StableHasher) {
234 ::std::hash::Hash::hash(self, hasher);
240 impl_stable_hash_via_hash!(i8);
241 impl_stable_hash_via_hash!(i16);
242 impl_stable_hash_via_hash!(i32);
243 impl_stable_hash_via_hash!(i64);
244 impl_stable_hash_via_hash!(isize);
246 impl_stable_hash_via_hash!(u8);
247 impl_stable_hash_via_hash!(u16);
248 impl_stable_hash_via_hash!(u32);
249 impl_stable_hash_via_hash!(u64);
250 impl_stable_hash_via_hash!(usize);
252 impl_stable_hash_via_hash!(u128);
253 impl_stable_hash_via_hash!(i128);
255 impl_stable_hash_via_hash!(char);
256 impl_stable_hash_via_hash!(());
258 impl<CTX> HashStable<CTX> for ! {
259 fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) {
264 impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
266 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
267 self.get().hash_stable(ctx, hasher)
271 impl<CTX> HashStable<CTX> for ::std::num::NonZeroUsize {
273 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
274 self.get().hash_stable(ctx, hasher)
278 impl<CTX> HashStable<CTX> for f32 {
279 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
280 let val: u32 = unsafe { ::std::mem::transmute(*self) };
281 val.hash_stable(ctx, hasher);
285 impl<CTX> HashStable<CTX> for f64 {
286 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
287 let val: u64 = unsafe { ::std::mem::transmute(*self) };
288 val.hash_stable(ctx, hasher);
292 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
294 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
295 (*self as i8).hash_stable(ctx, hasher);
299 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
301 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
302 let (ref _0,) = *self;
303 _0.hash_stable(ctx, hasher);
307 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
308 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
309 let (ref _0, ref _1) = *self;
310 _0.hash_stable(ctx, hasher);
311 _1.hash_stable(ctx, hasher);
315 impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
321 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
322 let (ref _0, ref _1, ref _2) = *self;
323 _0.hash_stable(ctx, hasher);
324 _1.hash_stable(ctx, hasher);
325 _2.hash_stable(ctx, hasher);
329 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
336 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
337 let (ref _0, ref _1, ref _2, ref _3) = *self;
338 _0.hash_stable(ctx, hasher);
339 _1.hash_stable(ctx, hasher);
340 _2.hash_stable(ctx, hasher);
341 _3.hash_stable(ctx, hasher);
345 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
346 default fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
347 self.len().hash_stable(ctx, hasher);
349 item.hash_stable(ctx, hasher);
354 impl<CTX> HashStable<CTX> for [u8] {
355 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
356 self.len().hash_stable(ctx, hasher);
361 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
363 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
364 (&self[..]).hash_stable(ctx, hasher);
368 impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
370 K: HashStable<CTX> + Eq + Hash,
375 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
376 self.len().hash_stable(ctx, hasher);
378 kv.hash_stable(ctx, hasher);
383 impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R>
385 K: HashStable<CTX> + Eq + Hash,
389 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
390 self.len().hash_stable(ctx, hasher);
392 key.hash_stable(ctx, hasher);
397 impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]>
402 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
403 (&self[..]).hash_stable(ctx, hasher);
407 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
409 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
410 (**self).hash_stable(ctx, hasher);
414 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
416 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
417 (**self).hash_stable(ctx, hasher);
421 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
423 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
424 (**self).hash_stable(ctx, hasher);
428 impl<CTX> HashStable<CTX> for str {
430 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
431 self.as_bytes().hash_stable(ctx, hasher);
435 impl<CTX> HashStable<CTX> for String {
437 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
438 (&self[..]).hash_stable(hcx, hasher);
442 impl<HCX> ToStableHashKey<HCX> for String {
443 type KeyType = String;
445 fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
450 impl<CTX> HashStable<CTX> for bool {
452 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
453 (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
457 impl<T, CTX> HashStable<CTX> for Option<T>
462 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
463 if let Some(ref value) = *self {
464 1u8.hash_stable(ctx, hasher);
465 value.hash_stable(ctx, hasher);
467 0u8.hash_stable(ctx, hasher);
472 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
478 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
479 mem::discriminant(self).hash_stable(ctx, hasher);
481 Ok(ref x) => x.hash_stable(ctx, hasher),
482 Err(ref x) => x.hash_stable(ctx, hasher),
487 impl<'a, T, CTX> HashStable<CTX> for &'a T
489 T: HashStable<CTX> + ?Sized,
492 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
493 (**self).hash_stable(ctx, hasher);
497 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
499 fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
500 ::std::hash::Hash::hash(self, hasher);
504 impl<T, CTX> HashStable<CTX> for ::std::ops::RangeInclusive<T>
509 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
510 self.start().hash_stable(ctx, hasher);
511 self.end().hash_stable(ctx, hasher);
515 impl<I: vec::Idx, T, CTX> HashStable<CTX> for vec::IndexVec<I, T>
519 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
520 self.len().hash_stable(ctx, hasher);
522 v.hash_stable(ctx, hasher);
527 impl<I: vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I> {
528 fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) {
529 ::std::hash::Hash::hash(self, hasher);
533 impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C> {
534 fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) {
535 ::std::hash::Hash::hash(self, hasher);
539 impl<T, CTX> HashStable<CTX> for bit_set::FiniteBitSet<T>
541 T: HashStable<CTX> + bit_set::FiniteBitSetTy,
543 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
544 self.0.hash_stable(hcx, hasher);
548 impl_stable_hash_via_hash!(::std::path::Path);
549 impl_stable_hash_via_hash!(::std::path::PathBuf);
551 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
553 K: ToStableHashKey<HCX> + Eq,
558 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
559 stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, (key, value)| {
560 let key = key.to_stable_hash_key(hcx);
561 key.hash_stable(hcx, hasher);
562 value.hash_stable(hcx, hasher);
567 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
569 K: ToStableHashKey<HCX> + Eq,
572 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
573 stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| {
574 let key = key.to_stable_hash_key(hcx);
575 key.hash_stable(hcx, hasher);
580 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
582 K: ToStableHashKey<HCX>,
585 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
586 stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, (key, value)| {
587 let key = key.to_stable_hash_key(hcx);
588 key.hash_stable(hcx, hasher);
589 value.hash_stable(hcx, hasher);
594 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
596 K: ToStableHashKey<HCX>,
598 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
599 stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| {
600 let key = key.to_stable_hash_key(hcx);
601 key.hash_stable(hcx, hasher);
606 fn stable_hash_reduce<HCX, I, C, F>(
608 hasher: &mut StableHasher,
613 C: Iterator<Item = I>,
614 F: Fn(&mut StableHasher, &mut HCX, I),
616 length.hash_stable(hcx, hasher);
620 hash_function(hasher, hcx, collection.next().unwrap());
623 let hash = collection
625 let mut hasher = StableHasher::new();
626 hash_function(&mut hasher, hcx, value);
627 hasher.finish::<u128>()
629 .reduce(|accum, value| accum.wrapping_add(value));
630 hash.hash_stable(hcx, hasher);
635 /// Controls what data we do or do not hash.
636 /// Whenever a `HashStable` implementation caches its
637 /// result, it needs to include `HashingControls` as part
638 /// of the key, to ensure that it does not produce an incorrect
639 /// result (for example, using a `Fingerprint` produced while
640 /// hashing `Span`s when a `Fingerprint` without `Span`s is
642 #[derive(Clone, Hash, Eq, PartialEq, Debug)]
643 pub struct HashingControls {
644 pub hash_spans: bool,