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 {
45 fn finish(hasher: StableHasher) -> Self {
46 let (_0, _1) = hasher.finalize();
47 u128::from(_0) | (u128::from(_1) << 64)
51 impl StableHasherResult for u64 {
52 fn finish(hasher: StableHasher) -> Self {
59 pub fn finalize(self) -> (u64, u64) {
60 self.state.finish128()
64 impl Hasher for StableHasher {
65 fn finish(&self) -> u64 {
66 panic!("use StableHasher::finalize instead");
70 fn write(&mut self, bytes: &[u8]) {
71 self.state.write(bytes);
75 fn write_u8(&mut self, i: u8) {
76 self.state.write_u8(i);
80 fn write_u16(&mut self, i: u16) {
81 self.state.write_u16(i.to_le());
85 fn write_u32(&mut self, i: u32) {
86 self.state.write_u32(i.to_le());
90 fn write_u64(&mut self, i: u64) {
91 self.state.write_u64(i.to_le());
95 fn write_u128(&mut self, i: u128) {
96 self.state.write_u128(i.to_le());
100 fn write_usize(&mut self, i: usize) {
101 // Always treat usize as u64 so we get the same results on 32 and 64 bit
102 // platforms. This is important for symbol hashes when cross compiling,
104 self.state.write_u64((i as u64).to_le());
108 fn write_i8(&mut self, i: i8) {
109 self.state.write_i8(i);
113 fn write_i16(&mut self, i: i16) {
114 self.state.write_i16(i.to_le());
118 fn write_i32(&mut self, i: i32) {
119 self.state.write_i32(i.to_le());
123 fn write_i64(&mut self, i: i64) {
124 self.state.write_i64(i.to_le());
128 fn write_i128(&mut self, i: i128) {
129 self.state.write_i128(i.to_le());
133 fn write_isize(&mut self, i: isize) {
134 // Always treat isize as i64 so we get the same results on 32 and 64 bit
135 // platforms. This is important for symbol hashes when cross compiling,
136 // for example. Sign extending here is preferable as it means that the
137 // same negative number hashes the same on both 32 and 64 bit platforms.
138 self.state.write_i64((i as i64).to_le());
142 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
143 /// stable across multiple compilation sessions.
145 /// Note that `HashStable` imposes rather more strict requirements than usual
148 /// - Stable hashes are sometimes used as identifiers. Therefore they must
149 /// conform to the corresponding `PartialEq` implementations:
151 /// - `x == y` implies `hash_stable(x) == hash_stable(y)`, and
152 /// - `x != y` implies `hash_stable(x) != hash_stable(y)`.
154 /// That second condition is usually not required for hash functions
155 /// (e.g. `Hash`). In practice this means that `hash_stable` must feed any
156 /// information into the hasher that a `PartialEq` comparison takes into
157 /// account. See [#49300](https://github.com/rust-lang/rust/issues/49300)
158 /// for an example where violating this invariant has caused trouble in the
161 /// - `hash_stable()` must be independent of the current
162 /// compilation session. E.g. they must not hash memory addresses or other
163 /// things that are "randomly" assigned per compilation session.
165 /// - `hash_stable()` must be independent of the host architecture. The
166 /// `StableHasher` takes care of endianness and `isize`/`usize` platform
168 pub trait HashStable<CTX> {
169 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher);
172 /// Implement this for types that can be turned into stable keys like, for
173 /// example, for DefId that can be converted to a DefPathHash. This is used for
174 /// bringing maps into a predictable order before hashing them.
175 pub trait ToStableHashKey<HCX> {
176 type KeyType: Ord + Sized + HashStable<HCX>;
177 fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
180 // Implement HashStable by just calling `Hash::hash()`. This works fine for
181 // self-contained values that don't depend on the hashing context `CTX`.
183 macro_rules! impl_stable_hash_via_hash {
185 impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
187 fn hash_stable(&self, _: &mut CTX, hasher: &mut $crate::stable_hasher::StableHasher) {
188 ::std::hash::Hash::hash(self, hasher);
194 impl_stable_hash_via_hash!(i8);
195 impl_stable_hash_via_hash!(i16);
196 impl_stable_hash_via_hash!(i32);
197 impl_stable_hash_via_hash!(i64);
198 impl_stable_hash_via_hash!(isize);
200 impl_stable_hash_via_hash!(u8);
201 impl_stable_hash_via_hash!(u16);
202 impl_stable_hash_via_hash!(u32);
203 impl_stable_hash_via_hash!(u64);
204 impl_stable_hash_via_hash!(usize);
206 impl_stable_hash_via_hash!(u128);
207 impl_stable_hash_via_hash!(i128);
209 impl_stable_hash_via_hash!(char);
210 impl_stable_hash_via_hash!(());
212 impl<CTX> HashStable<CTX> for ! {
213 fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) {
218 impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
219 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
220 self.get().hash_stable(ctx, hasher)
224 impl<CTX> HashStable<CTX> for ::std::num::NonZeroUsize {
225 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
226 self.get().hash_stable(ctx, hasher)
230 impl<CTX> HashStable<CTX> for f32 {
231 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
232 let val: u32 = unsafe { ::std::mem::transmute(*self) };
233 val.hash_stable(ctx, hasher);
237 impl<CTX> HashStable<CTX> for f64 {
238 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
239 let val: u64 = unsafe { ::std::mem::transmute(*self) };
240 val.hash_stable(ctx, hasher);
244 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
245 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
246 (*self as i8).hash_stable(ctx, hasher);
250 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
251 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
252 let (ref _0,) = *self;
253 _0.hash_stable(ctx, hasher);
257 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
258 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
259 let (ref _0, ref _1) = *self;
260 _0.hash_stable(ctx, hasher);
261 _1.hash_stable(ctx, hasher);
265 impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
271 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
272 let (ref _0, ref _1, ref _2) = *self;
273 _0.hash_stable(ctx, hasher);
274 _1.hash_stable(ctx, hasher);
275 _2.hash_stable(ctx, hasher);
279 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
286 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
287 let (ref _0, ref _1, ref _2, ref _3) = *self;
288 _0.hash_stable(ctx, hasher);
289 _1.hash_stable(ctx, hasher);
290 _2.hash_stable(ctx, hasher);
291 _3.hash_stable(ctx, hasher);
295 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
296 default fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
297 self.len().hash_stable(ctx, hasher);
299 item.hash_stable(ctx, hasher);
304 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
306 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
307 (&self[..]).hash_stable(ctx, hasher);
311 impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
313 K: HashStable<CTX> + Eq + Hash,
318 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
319 self.len().hash_stable(ctx, hasher);
321 kv.hash_stable(ctx, hasher);
326 impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R>
328 K: HashStable<CTX> + Eq + Hash,
332 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
333 self.len().hash_stable(ctx, hasher);
335 key.hash_stable(ctx, hasher);
340 impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]>
345 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
346 (&self[..]).hash_stable(ctx, hasher);
350 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
352 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
353 (**self).hash_stable(ctx, hasher);
357 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
359 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
360 (**self).hash_stable(ctx, hasher);
364 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
366 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
367 (**self).hash_stable(ctx, hasher);
371 impl<CTX> HashStable<CTX> for str {
373 fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
374 self.len().hash(hasher);
375 self.as_bytes().hash(hasher);
379 impl<CTX> HashStable<CTX> for String {
381 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
382 (&self[..]).hash_stable(hcx, hasher);
386 impl<HCX> ToStableHashKey<HCX> for String {
387 type KeyType = String;
389 fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
394 impl<CTX> HashStable<CTX> for bool {
396 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
397 (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
401 impl<T, CTX> HashStable<CTX> for Option<T>
406 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
407 if let Some(ref value) = *self {
408 1u8.hash_stable(ctx, hasher);
409 value.hash_stable(ctx, hasher);
411 0u8.hash_stable(ctx, hasher);
416 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
422 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
423 mem::discriminant(self).hash_stable(ctx, hasher);
425 Ok(ref x) => x.hash_stable(ctx, hasher),
426 Err(ref x) => x.hash_stable(ctx, hasher),
431 impl<'a, T, CTX> HashStable<CTX> for &'a T
433 T: HashStable<CTX> + ?Sized,
436 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
437 (**self).hash_stable(ctx, hasher);
441 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
443 fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
444 ::std::hash::Hash::hash(self, hasher);
448 impl<T, CTX> HashStable<CTX> for ::std::ops::RangeInclusive<T>
453 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
454 self.start().hash_stable(ctx, hasher);
455 self.end().hash_stable(ctx, hasher);
459 impl<I: vec::Idx, T, CTX> HashStable<CTX> for vec::IndexVec<I, T>
463 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
464 self.len().hash_stable(ctx, hasher);
466 v.hash_stable(ctx, hasher);
471 impl<I: vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I> {
472 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
473 self.words().hash_stable(ctx, hasher);
477 impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C> {
478 fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
479 self.words().hash_stable(ctx, hasher);
483 impl<T, CTX> HashStable<CTX> for bit_set::FiniteBitSet<T>
485 T: HashStable<CTX> + bit_set::FiniteBitSetTy,
487 fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
488 self.0.hash_stable(hcx, hasher);
492 impl_stable_hash_via_hash!(::std::path::Path);
493 impl_stable_hash_via_hash!(::std::path::PathBuf);
495 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
497 K: ToStableHashKey<HCX> + Eq,
502 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
503 hash_stable_hashmap(hcx, hasher, self, ToStableHashKey::to_stable_hash_key);
507 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
509 K: ToStableHashKey<HCX> + Eq,
512 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
513 let mut keys: Vec<_> = self.iter().map(|k| k.to_stable_hash_key(hcx)).collect();
514 keys.sort_unstable();
515 keys.hash_stable(hcx, hasher);
519 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
521 K: ToStableHashKey<HCX>,
524 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
525 let mut entries: Vec<_> =
526 self.iter().map(|(k, v)| (k.to_stable_hash_key(hcx), v)).collect();
527 entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
528 entries.hash_stable(hcx, hasher);
532 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
534 K: ToStableHashKey<HCX>,
536 fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
537 let mut keys: Vec<_> = self.iter().map(|k| k.to_stable_hash_key(hcx)).collect();
538 keys.sort_unstable();
539 keys.hash_stable(hcx, hasher);
543 pub fn hash_stable_hashmap<HCX, K, V, R, SK, F>(
545 hasher: &mut StableHasher,
546 map: &::std::collections::HashMap<K, V, R>,
547 to_stable_hash_key: F,
552 SK: HashStable<HCX> + Ord,
553 F: Fn(&K, &HCX) -> SK,
555 let mut entries: Vec<_> = map.iter().map(|(k, v)| (to_stable_hash_key(k, hcx), v)).collect();
556 entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
557 entries.hash_stable(hcx, hasher);