1 use crate::sip128::SipHasher128;
2 use rustc_index::bit_set;
4 use smallvec::SmallVec;
5 use std::hash::{BuildHasher, Hash, Hasher};
6 use std::marker::PhantomData;
12 /// When hashing something that ends up affecting properties like symbol names,
13 /// we want these symbol names to be calculated independently of other factors
14 /// like what architecture you're compiling *from*.
16 /// To that end we always convert integers to little-endian format before
17 /// hashing and the architecture dependent `isize` and `usize` types are
18 /// extended to 64 bits if needed.
19 pub struct StableHasher {
23 impl ::std::fmt::Debug for StableHasher {
24 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
25 write!(f, "{:?}", self.state)
29 pub trait StableHasherResult: Sized {
30 fn finish(hasher: StableHasher) -> Self;
35 pub fn new() -> Self {
36 StableHasher { state: SipHasher128::new_with_keys(0, 0) }
40 pub fn finish<W: StableHasherResult>(self) -> W {
45 impl StableHasherResult for u128 {
47 fn finish(hasher: StableHasher) -> Self {
48 let (_0, _1) = hasher.finalize();
49 u128::from(_0) | (u128::from(_1) << 64)
53 impl StableHasherResult for u64 {
55 fn finish(hasher: StableHasher) -> Self {
62 pub fn finalize(self) -> (u64, u64) {
63 self.state.finish128()
67 impl Hasher for StableHasher {
68 fn finish(&self) -> u64 {
69 panic!("use StableHasher::finalize instead");
73 fn write(&mut self, bytes: &[u8]) {
74 self.state.write(bytes);
78 fn write_str(&mut self, s: &str) {
79 self.state.write_str(s);
83 fn write_length_prefix(&mut self, len: usize) {
84 // Our impl for `usize` will extend it if needed.
85 self.write_usize(len);
89 fn write_u8(&mut self, i: u8) {
90 self.state.write_u8(i);
94 fn write_u16(&mut self, i: u16) {
95 self.state.short_write(i.to_le_bytes());
99 fn write_u32(&mut self, i: u32) {
100 self.state.short_write(i.to_le_bytes());
104 fn write_u64(&mut self, i: u64) {
105 self.state.short_write(i.to_le_bytes());
109 fn write_u128(&mut self, i: u128) {
110 self.state.write(&i.to_le_bytes());
114 fn write_usize(&mut self, i: usize) {
115 // Always treat usize as u64 so we get the same results on 32 and 64 bit
116 // platforms. This is important for symbol hashes when cross compiling,
118 self.state.short_write((i as u64).to_le_bytes());
122 fn write_i8(&mut self, i: i8) {
123 self.state.write_i8(i);
127 fn write_i16(&mut self, i: i16) {
128 self.state.short_write((i as u16).to_le_bytes());
132 fn write_i32(&mut self, i: i32) {
133 self.state.short_write((i as u32).to_le_bytes());
137 fn write_i64(&mut self, i: i64) {
138 self.state.short_write((i as u64).to_le_bytes());
142 fn write_i128(&mut self, i: i128) {
143 self.state.write(&(i as u128).to_le_bytes());
147 fn write_isize(&mut self, i: isize) {
148 // Always treat isize as a 64-bit number so we get the same results on 32 and 64 bit
149 // platforms. This is important for symbol hashes when cross compiling,
150 // for example. Sign extending here is preferable as it means that the
151 // same negative number hashes the same on both 32 and 64 bit platforms.
152 let value = i as u64;
157 fn hash_value(state: &mut SipHasher128, value: u64) {
158 state.write_u8(0xFF);
159 state.short_write(value.to_le_bytes());
162 // `isize` values often seem to have a small (positive) numeric value in practice.
163 // To exploit this, if the value is small, we will hash a smaller amount of bytes.
164 // However, we cannot just skip the leading zero bytes, as that would produce the same hash
165 // e.g. if you hash two values that have the same bit pattern when they are swapped.
166 // See https://github.com/rust-lang/rust/pull/93014 for context.
168 // Therefore, we employ the following strategy:
169 // 1) When we encounter a value that fits within a single byte (the most common case), we
170 // hash just that byte. This is the most common case that is being optimized. However, we do
171 // not do this for the value 0xFF, as that is a reserved prefix (a bit like in UTF-8).
172 // 2) When we encounter a larger value, we hash a "marker" 0xFF and then the corresponding
173 // 8 bytes. Since this prefix cannot occur when we hash a single byte, when we hash two
174 // `isize`s that fit within a different amount of bytes, they should always produce a different
175 // byte stream for the hasher.
177 self.state.write_u8(value as u8);
179 hash_value(&mut self.state, value);
184 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
185 /// stable across multiple compilation sessions.
187 /// Note that `HashStable` imposes rather more strict requirements than usual
190 /// - Stable hashes are sometimes used as identifiers. Therefore they must
191 /// conform to the corresponding `PartialEq` implementations:
193 /// - `x == y` implies `hash_stable(x) == hash_stable(y)`, and
194 /// - `x != y` implies `hash_stable(x) != hash_stable(y)`.
196 /// That second condition is usually not required for hash functions
197 /// (e.g. `Hash`). In practice this means that `hash_stable` must feed any
198 /// information into the hasher that a `PartialEq` comparison takes into
199 /// account. See [#49300](https://github.com/rust-lang/rust/issues/49300)
200 /// for an example where violating this invariant has caused trouble in the
203 /// - `hash_stable()` must be independent of the current
204 /// compilation session. E.g. they must not hash memory addresses or other
205 /// things that are "randomly" assigned per compilation session.
207 /// - `hash_stable()` must be independent of the host architecture. The
208 /// `StableHasher` takes care of endianness and `isize`/`usize` platform
210 pub trait HashStable<CTX> {
211 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher);
214 /// Implement this for types that can be turned into stable keys like, for
215 /// example, for DefId that can be converted to a DefPathHash. This is used for
216 /// bringing maps into a predictable order before hashing them.
217 pub trait ToStableHashKey<HCX> {
218 type KeyType: Ord + Sized + HashStable<HCX>;
219 fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
222 /// Trait for marking a type as having a sort order that is
223 /// stable across compilation session boundaries. More formally:
226 /// Ord::cmp(a1, b1) == Ord::cmp(a2, b2)
227 /// where a2 = decode(encode(a1, context1), context2)
228 /// b2 = decode(encode(b1, context1), context2)
231 /// i.e. the result of `Ord::cmp` is not influenced by encoding
232 /// the values in one session and then decoding them in another
235 /// This is trivially true for types where encoding and decoding
236 /// don't change the bytes of the values that are used during
237 /// comparison and comparison only depends on these bytes (as
238 /// opposed to some non-local state). Examples are u32, String,
241 /// But it is not true for:
242 /// - `*const T` and `*mut T` because the values of these pointers
243 /// will change between sessions.
244 /// - `DefIndex`, `CrateNum`, `LocalDefId`, because their concrete
245 /// values depend on state that might be different between
246 /// compilation sessions.
247 pub unsafe trait StableOrd: Ord {}
249 /// Implement HashStable by just calling `Hash::hash()`. Also implement `StableOrd` for the type since
250 /// that has the same requirements.
252 /// **WARNING** This is only valid for types that *really* don't need any context for fingerprinting.
253 /// But it is easy to misuse this macro (see [#96013](https://github.com/rust-lang/rust/issues/96013)
254 /// for examples). Therefore this macro is not exported and should only be used in the limited cases
255 /// here in this module.
257 /// Use `#[derive(HashStable_Generic)]` instead.
258 macro_rules! impl_stable_traits_for_trivial_type {
260 impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
262 fn hash_stable(&self, _: &mut CTX, hasher: &mut $crate::stable_hasher::StableHasher) {
263 ::std::hash::Hash::hash(self, hasher);
267 unsafe impl $crate::stable_hasher::StableOrd for $t {}
271 impl_stable_traits_for_trivial_type!(i8);
272 impl_stable_traits_for_trivial_type!(i16);
273 impl_stable_traits_for_trivial_type!(i32);
274 impl_stable_traits_for_trivial_type!(i64);
275 impl_stable_traits_for_trivial_type!(isize);
277 impl_stable_traits_for_trivial_type!(u8);
278 impl_stable_traits_for_trivial_type!(u16);
279 impl_stable_traits_for_trivial_type!(u32);
280 impl_stable_traits_for_trivial_type!(u64);
281 impl_stable_traits_for_trivial_type!(usize);
283 impl_stable_traits_for_trivial_type!(u128);
284 impl_stable_traits_for_trivial_type!(i128);
286 impl_stable_traits_for_trivial_type!(char);
287 impl_stable_traits_for_trivial_type!(());
289 impl<CTX> HashStable<CTX> for ! {
290 fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) {
295 impl<CTX, T> HashStable<CTX> for PhantomData<T> {
296 fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) {}
299 impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
301 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
302 self.get().hash_stable(ctx, hasher)
306 impl<CTX> HashStable<CTX> for ::std::num::NonZeroUsize {
308 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
309 self.get().hash_stable(ctx, hasher)
313 impl<CTX> HashStable<CTX> for f32 {
314 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
315 let val: u32 = unsafe { ::std::mem::transmute(*self) };
316 val.hash_stable(ctx, hasher);
320 impl<CTX> HashStable<CTX> for f64 {
321 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
322 let val: u64 = unsafe { ::std::mem::transmute(*self) };
323 val.hash_stable(ctx, hasher);
327 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
329 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
330 (*self as i8).hash_stable(ctx, hasher);
334 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
336 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
337 let (ref _0,) = *self;
338 _0.hash_stable(ctx, hasher);
342 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
343 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
344 let (ref _0, ref _1) = *self;
345 _0.hash_stable(ctx, hasher);
346 _1.hash_stable(ctx, hasher);
350 impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
356 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
357 let (ref _0, ref _1, ref _2) = *self;
358 _0.hash_stable(ctx, hasher);
359 _1.hash_stable(ctx, hasher);
360 _2.hash_stable(ctx, hasher);
364 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
371 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
372 let (ref _0, ref _1, ref _2, ref _3) = *self;
373 _0.hash_stable(ctx, hasher);
374 _1.hash_stable(ctx, hasher);
375 _2.hash_stable(ctx, hasher);
376 _3.hash_stable(ctx, hasher);
380 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
381 default fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
382 self.len().hash_stable(ctx, hasher);
384 item.hash_stable(ctx, hasher);
389 impl<CTX> HashStable<CTX> for [u8] {
390 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
391 self.len().hash_stable(ctx, hasher);
396 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
398 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
399 self[..].hash_stable(ctx, hasher);
403 impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
405 K: HashStable<CTX> + Eq + Hash,
410 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
411 self.len().hash_stable(ctx, hasher);
413 kv.hash_stable(ctx, hasher);
418 impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R>
420 K: HashStable<CTX> + Eq + Hash,
424 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
425 self.len().hash_stable(ctx, hasher);
427 key.hash_stable(ctx, hasher);
432 impl<A, const N: usize, CTX> HashStable<CTX> for SmallVec<[A; N]>
437 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
438 self[..].hash_stable(ctx, hasher);
442 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
444 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
445 (**self).hash_stable(ctx, hasher);
449 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
451 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
452 (**self).hash_stable(ctx, hasher);
456 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
458 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
459 (**self).hash_stable(ctx, hasher);
463 impl<CTX> HashStable<CTX> for str {
465 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
466 self.as_bytes().hash_stable(ctx, hasher);
470 impl<CTX> HashStable<CTX> for String {
472 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
473 self[..].hash_stable(hcx, hasher);
477 // Safety: String comparison only depends on their contents and the
478 // contents are not changed by (de-)serialization.
479 unsafe impl StableOrd for String {}
481 impl<HCX> ToStableHashKey<HCX> for String {
482 type KeyType = String;
484 fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
489 impl<CTX> HashStable<CTX> for bool {
491 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
492 (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
496 // Safety: sort order of bools is not changed by (de-)serialization.
497 unsafe impl StableOrd for bool {}
499 impl<T, CTX> HashStable<CTX> for Option<T>
504 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
505 if let Some(ref value) = *self {
506 1u8.hash_stable(ctx, hasher);
507 value.hash_stable(ctx, hasher);
509 0u8.hash_stable(ctx, hasher);
514 // Safety: the Option wrapper does not add instability to comparison.
515 unsafe impl<T: StableOrd> StableOrd for Option<T> {}
517 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
523 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
524 mem::discriminant(self).hash_stable(ctx, hasher);
526 Ok(ref x) => x.hash_stable(ctx, hasher),
527 Err(ref x) => x.hash_stable(ctx, hasher),
532 impl<'a, T, CTX> HashStable<CTX> for &'a T
534 T: HashStable<CTX> + ?Sized,
537 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
538 (**self).hash_stable(ctx, hasher);
542 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
544 fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
545 ::std::hash::Hash::hash(self, hasher);
549 impl<T, CTX> HashStable<CTX> for ::std::ops::RangeInclusive<T>
554 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
555 self.start().hash_stable(ctx, hasher);
556 self.end().hash_stable(ctx, hasher);
560 impl<I: vec::Idx, T, CTX> HashStable<CTX> for vec::IndexVec<I, T>
564 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
565 self.len().hash_stable(ctx, hasher);
567 v.hash_stable(ctx, hasher);
572 impl<I: vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I> {
573 fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) {
574 ::std::hash::Hash::hash(self, hasher);
578 impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C> {
579 fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) {
580 ::std::hash::Hash::hash(self, hasher);
584 impl<T, CTX> HashStable<CTX> for bit_set::FiniteBitSet<T>
586 T: HashStable<CTX> + bit_set::FiniteBitSetTy,
588 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
589 self.0.hash_stable(hcx, hasher);
593 impl_stable_traits_for_trivial_type!(::std::path::Path);
594 impl_stable_traits_for_trivial_type!(::std::path::PathBuf);
596 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
598 K: ToStableHashKey<HCX> + Eq,
603 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
604 stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, (key, value)| {
605 let key = key.to_stable_hash_key(hcx);
606 key.hash_stable(hcx, hasher);
607 value.hash_stable(hcx, hasher);
612 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
614 K: ToStableHashKey<HCX> + Eq,
617 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
618 stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| {
619 let key = key.to_stable_hash_key(hcx);
620 key.hash_stable(hcx, hasher);
625 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
627 K: HashStable<HCX> + StableOrd,
630 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
631 self.len().hash_stable(hcx, hasher);
632 for entry in self.iter() {
633 entry.hash_stable(hcx, hasher);
638 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
640 K: HashStable<HCX> + StableOrd,
642 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
643 self.len().hash_stable(hcx, hasher);
644 for entry in self.iter() {
645 entry.hash_stable(hcx, hasher);
650 fn stable_hash_reduce<HCX, I, C, F>(
652 hasher: &mut StableHasher,
657 C: Iterator<Item = I>,
658 F: Fn(&mut StableHasher, &mut HCX, I),
660 length.hash_stable(hcx, hasher);
664 hash_function(hasher, hcx, collection.next().unwrap());
667 let hash = collection
669 let mut hasher = StableHasher::new();
670 hash_function(&mut hasher, hcx, value);
671 hasher.finish::<u128>()
673 .reduce(|accum, value| accum.wrapping_add(value));
674 hash.hash_stable(hcx, hasher);
679 /// Controls what data we do or do not hash.
680 /// Whenever a `HashStable` implementation caches its
681 /// result, it needs to include `HashingControls` as part
682 /// of the key, to ensure that it does not produce an incorrect
683 /// result (for example, using a `Fingerprint` produced while
684 /// hashing `Span`s when a `Fingerprint` without `Span`s is
686 #[derive(Clone, Hash, Eq, PartialEq, Debug)]
687 pub struct HashingControls {
688 pub hash_spans: bool,