1 use crate::sip128::SipHasher128;
2 use rustc_index::bit_set;
4 use smallvec::SmallVec;
5 use std::hash::{BuildHasher, Hash, Hasher};
8 /// When hashing something that ends up affecting properties like symbol names,
9 /// we want these symbol names to be calculated independently of other factors
10 /// like what architecture you're compiling *from*.
12 /// To that end we always convert integers to little-endian format before
13 /// hashing and the architecture dependent `isize` and `usize` types are
14 /// extended to 64 bits if needed.
15 pub struct StableHasher {
19 impl ::std::fmt::Debug for StableHasher {
20 fn fmt(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
21 write!(f, "{:?}", self.state)
25 pub trait StableHasherResult: Sized {
26 fn finish(hasher: StableHasher) -> Self;
31 pub fn new() -> Self {
32 StableHasher { state: SipHasher128::new_with_keys(0, 0) }
35 pub fn finish<W: StableHasherResult>(self) -> W {
40 impl StableHasherResult for u128 {
41 fn finish(hasher: StableHasher) -> Self {
42 let (_0, _1) = hasher.finalize();
43 u128::from(_0) | (u128::from(_1) << 64)
47 impl StableHasherResult for u64 {
48 fn finish(hasher: StableHasher) -> Self {
55 pub fn finalize(self) -> (u64, u64) {
56 self.state.finish128()
60 impl Hasher for StableHasher {
61 fn finish(&self) -> u64 {
62 panic!("use StableHasher::finalize instead");
66 fn write(&mut self, bytes: &[u8]) {
67 self.state.write(bytes);
71 fn write_u8(&mut self, i: u8) {
72 self.state.write_u8(i);
76 fn write_u16(&mut self, i: u16) {
77 self.state.write_u16(i.to_le());
81 fn write_u32(&mut self, i: u32) {
82 self.state.write_u32(i.to_le());
86 fn write_u64(&mut self, i: u64) {
87 self.state.write_u64(i.to_le());
91 fn write_u128(&mut self, i: u128) {
92 self.state.write_u128(i.to_le());
96 fn write_usize(&mut self, i: usize) {
97 // Always treat usize as u64 so we get the same results on 32 and 64 bit
98 // platforms. This is important for symbol hashes when cross compiling,
100 self.state.write_u64((i as u64).to_le());
104 fn write_i8(&mut self, i: i8) {
105 self.state.write_i8(i);
109 fn write_i16(&mut self, i: i16) {
110 self.state.write_i16(i.to_le());
114 fn write_i32(&mut self, i: i32) {
115 self.state.write_i32(i.to_le());
119 fn write_i64(&mut self, i: i64) {
120 self.state.write_i64(i.to_le());
124 fn write_i128(&mut self, i: i128) {
125 self.state.write_i128(i.to_le());
129 fn write_isize(&mut self, i: isize) {
130 // Always treat isize as i64 so we get the same results on 32 and 64 bit
131 // platforms. This is important for symbol hashes when cross compiling,
133 self.state.write_i64((i as i64).to_le());
137 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
138 /// stable across multiple compilation sessions.
140 /// Note that `HashStable` imposes rather more strict requirements than usual
143 /// - Stable hashes are sometimes used as identifiers. Therefore they must
144 /// conform to the corresponding `PartialEq` implementations:
146 /// - `x == y` implies `hash_stable(x) == hash_stable(y)`, and
147 /// - `x != y` implies `hash_stable(x) != hash_stable(y)`.
149 /// That second condition is usually not required for hash functions
150 /// (e.g. `Hash`). In practice this means that `hash_stable` must feed any
151 /// information into the hasher that a `PartialEq` comparison takes into
152 /// account. See [#49300](https://github.com/rust-lang/rust/issues/49300)
153 /// for an example where violating this invariant has caused trouble in the
156 /// - `hash_stable()` must be independent of the current
157 /// compilation session. E.g. they must not hash memory addresses or other
158 /// things that are "randomly" assigned per compilation session.
160 /// - `hash_stable()` must be independent of the host architecture. The
161 /// `StableHasher` takes care of endianness and `isize`/`usize` platform
163 pub trait HashStable<CTX> {
164 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher);
167 /// Implement this for types that can be turned into stable keys like, for
168 /// example, for DefId that can be converted to a DefPathHash. This is used for
169 /// bringing maps into a predictable order before hashing them.
170 pub trait ToStableHashKey<HCX> {
171 type KeyType: Ord + Sized + HashStable<HCX>;
172 fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
175 // Implement HashStable by just calling `Hash::hash()`. This works fine for
176 // self-contained values that don't depend on the hashing context `CTX`.
178 macro_rules! impl_stable_hash_via_hash {
180 impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
182 fn hash_stable(&self, _: &mut CTX, hasher: &mut $crate::stable_hasher::StableHasher) {
183 ::std::hash::Hash::hash(self, hasher);
189 impl_stable_hash_via_hash!(i8);
190 impl_stable_hash_via_hash!(i16);
191 impl_stable_hash_via_hash!(i32);
192 impl_stable_hash_via_hash!(i64);
193 impl_stable_hash_via_hash!(isize);
195 impl_stable_hash_via_hash!(u8);
196 impl_stable_hash_via_hash!(u16);
197 impl_stable_hash_via_hash!(u32);
198 impl_stable_hash_via_hash!(u64);
199 impl_stable_hash_via_hash!(usize);
201 impl_stable_hash_via_hash!(u128);
202 impl_stable_hash_via_hash!(i128);
204 impl_stable_hash_via_hash!(char);
205 impl_stable_hash_via_hash!(());
207 impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
208 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
209 self.get().hash_stable(ctx, hasher)
213 impl<CTX> HashStable<CTX> for f32 {
214 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
215 let val: u32 = unsafe { ::std::mem::transmute(*self) };
216 val.hash_stable(ctx, hasher);
220 impl<CTX> HashStable<CTX> for f64 {
221 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
222 let val: u64 = unsafe { ::std::mem::transmute(*self) };
223 val.hash_stable(ctx, hasher);
227 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
228 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
229 (*self as i8).hash_stable(ctx, hasher);
233 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
234 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
235 let (ref _0,) = *self;
236 _0.hash_stable(ctx, hasher);
240 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
241 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
242 let (ref _0, ref _1) = *self;
243 _0.hash_stable(ctx, hasher);
244 _1.hash_stable(ctx, hasher);
248 impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
254 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
255 let (ref _0, ref _1, ref _2) = *self;
256 _0.hash_stable(ctx, hasher);
257 _1.hash_stable(ctx, hasher);
258 _2.hash_stable(ctx, hasher);
262 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
269 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
270 let (ref _0, ref _1, ref _2, ref _3) = *self;
271 _0.hash_stable(ctx, hasher);
272 _1.hash_stable(ctx, hasher);
273 _2.hash_stable(ctx, hasher);
274 _3.hash_stable(ctx, hasher);
278 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
279 default fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
280 self.len().hash_stable(ctx, hasher);
282 item.hash_stable(ctx, hasher);
287 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
289 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
290 (&self[..]).hash_stable(ctx, hasher);
294 impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
296 K: HashStable<CTX> + Eq + Hash,
301 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
302 self.len().hash_stable(ctx, hasher);
304 kv.hash_stable(ctx, hasher);
309 impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R>
311 K: HashStable<CTX> + Eq + Hash,
315 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
316 self.len().hash_stable(ctx, hasher);
318 key.hash_stable(ctx, hasher);
323 impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]>
328 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
329 (&self[..]).hash_stable(ctx, hasher);
333 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
335 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
336 (**self).hash_stable(ctx, hasher);
340 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
342 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
343 (**self).hash_stable(ctx, hasher);
347 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
349 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
350 (**self).hash_stable(ctx, hasher);
354 impl<CTX> HashStable<CTX> for str {
356 fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
357 self.len().hash(hasher);
358 self.as_bytes().hash(hasher);
362 impl<CTX> HashStable<CTX> for String {
364 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
365 (&self[..]).hash_stable(hcx, hasher);
369 impl<HCX> ToStableHashKey<HCX> for String {
370 type KeyType = String;
372 fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
377 impl<CTX> HashStable<CTX> for bool {
379 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
380 (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
384 impl<T, CTX> HashStable<CTX> for Option<T>
389 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
390 if let Some(ref value) = *self {
391 1u8.hash_stable(ctx, hasher);
392 value.hash_stable(ctx, hasher);
394 0u8.hash_stable(ctx, hasher);
399 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
405 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
406 mem::discriminant(self).hash_stable(ctx, hasher);
408 Ok(ref x) => x.hash_stable(ctx, hasher),
409 Err(ref x) => x.hash_stable(ctx, hasher),
414 impl<'a, T, CTX> HashStable<CTX> for &'a T
416 T: HashStable<CTX> + ?Sized,
419 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
420 (**self).hash_stable(ctx, hasher);
424 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
426 fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
427 ::std::hash::Hash::hash(self, hasher);
431 impl<T, CTX> HashStable<CTX> for ::std::ops::RangeInclusive<T>
436 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
437 self.start().hash_stable(ctx, hasher);
438 self.end().hash_stable(ctx, hasher);
442 impl<I: vec::Idx, T, CTX> HashStable<CTX> for vec::IndexVec<I, T>
446 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
447 self.len().hash_stable(ctx, hasher);
449 v.hash_stable(ctx, hasher);
454 impl<I: vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I> {
455 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
456 self.words().hash_stable(ctx, hasher);
460 impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C> {
461 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
462 self.words().hash_stable(ctx, hasher);
466 impl_stable_hash_via_hash!(::std::path::Path);
467 impl_stable_hash_via_hash!(::std::path::PathBuf);
469 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
471 K: ToStableHashKey<HCX> + Eq,
476 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
477 hash_stable_hashmap(hcx, hasher, self, ToStableHashKey::to_stable_hash_key);
481 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
483 K: ToStableHashKey<HCX> + Eq,
486 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
487 let mut keys: Vec<_> = self.iter().map(|k| k.to_stable_hash_key(hcx)).collect();
488 keys.sort_unstable();
489 keys.hash_stable(hcx, hasher);
493 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
495 K: ToStableHashKey<HCX>,
498 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
499 let mut entries: Vec<_> =
500 self.iter().map(|(k, v)| (k.to_stable_hash_key(hcx), v)).collect();
501 entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
502 entries.hash_stable(hcx, hasher);
506 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
508 K: ToStableHashKey<HCX>,
510 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
511 let mut keys: Vec<_> = self.iter().map(|k| k.to_stable_hash_key(hcx)).collect();
512 keys.sort_unstable();
513 keys.hash_stable(hcx, hasher);
517 pub fn hash_stable_hashmap<HCX, K, V, R, SK, F>(
519 hasher: &mut StableHasher,
520 map: &::std::collections::HashMap<K, V, R>,
521 to_stable_hash_key: F,
526 SK: HashStable<HCX> + Ord,
527 F: Fn(&K, &HCX) -> SK,
529 let mut entries: Vec<_> = map.iter().map(|(k, v)| (to_stable_hash_key(k, hcx), v)).collect();
530 entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
531 entries.hash_stable(hcx, hasher);
534 /// A vector container that makes sure that its items are hashed in a stable
536 pub struct StableVec<T>(Vec<T>);
538 impl<T> StableVec<T> {
539 pub fn new(v: Vec<T>) -> Self {
544 impl<T> ::std::ops::Deref for StableVec<T> {
545 type Target = Vec<T>;
547 fn deref(&self) -> &Vec<T> {
552 impl<T, HCX> HashStable<HCX> for StableVec<T>
554 T: HashStable<HCX> + ToStableHashKey<HCX>,
556 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
557 let StableVec(ref v) = *self;
559 let mut sorted: Vec<_> = v.iter().map(|x| x.to_stable_hash_key(hcx)).collect();
560 sorted.sort_unstable();
561 sorted.hash_stable(hcx, hasher);