1 use std::hash::{Hash, Hasher, BuildHasher};
2 use std::marker::PhantomData;
4 use smallvec::SmallVec;
5 use crate::sip128::SipHasher128;
6 use crate::indexed_vec;
9 /// When hashing something that ends up affecting properties like symbol names,
10 /// we want these symbol names to be calculated independently of other factors
11 /// like what architecture you're compiling *from*.
13 /// To that end we always convert integers to little-endian format before
14 /// hashing and the architecture dependent `isize` and `usize` types are
15 /// extended to 64 bits if needed.
16 pub struct StableHasher<W> {
18 width: PhantomData<W>,
21 impl<W: StableHasherResult> ::std::fmt::Debug for StableHasher<W> {
22 fn fmt(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
23 write!(f, "{:?}", self.state)
27 pub trait StableHasherResult: Sized {
28 fn finish(hasher: StableHasher<Self>) -> Self;
31 impl<W: StableHasherResult> StableHasher<W> {
32 pub fn new() -> Self {
34 state: SipHasher128::new_with_keys(0, 0),
39 pub fn finish(self) -> W {
44 impl StableHasherResult for u128 {
45 fn finish(hasher: StableHasher<Self>) -> 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>) -> Self {
57 impl<W> StableHasher<W> {
59 pub fn finalize(self) -> (u64, u64) {
60 self.state.finish128()
64 impl<W> Hasher for StableHasher<W> {
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,
137 self.state.write_i64((i as i64).to_le());
141 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
142 /// stable across multiple compilation sessions.
144 /// Note that `HashStable` imposes rather more strict requirements than usual
147 /// - Stable hashes are sometimes used as identifiers. Therefore they must
148 /// conform to the corresponding `PartialEq` implementations:
150 /// - `x == y` implies `hash_stable(x) == hash_stable(y)`, and
151 /// - `x != y` implies `hash_stable(x) != hash_stable(y)`.
153 /// That second condition is usually not required for hash functions
154 /// (e.g. `Hash`). In practice this means that `hash_stable` must feed any
155 /// information into the hasher that a `PartialEq` comparision takes into
156 /// account. See [#49300](https://github.com/rust-lang/rust/issues/49300)
157 /// for an example where violating this invariant has caused trouble in the
160 /// - `hash_stable()` must be independent of the current
161 /// compilation session. E.g. they must not hash memory addresses or other
162 /// things that are "randomly" assigned per compilation session.
164 /// - `hash_stable()` must be independent of the host architecture. The
165 /// `StableHasher` takes care of endianness and `isize`/`usize` platform
167 pub trait HashStable<CTX> {
168 fn hash_stable<W: StableHasherResult>(&self,
170 hasher: &mut StableHasher<W>);
173 /// Implement this for types that can be turned into stable keys like, for
174 /// example, for DefId that can be converted to a DefPathHash. This is used for
175 /// bringing maps into a predictable order before hashing them.
176 pub trait ToStableHashKey<HCX> {
177 type KeyType: Ord + Clone + Sized + HashStable<HCX>;
178 fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
181 // Implement HashStable by just calling `Hash::hash()`. This works fine for
182 // self-contained values that don't depend on the hashing context `CTX`.
184 macro_rules! impl_stable_hash_via_hash {
186 impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
188 fn hash_stable<W: $crate::stable_hasher::StableHasherResult>(
191 hasher: &mut $crate::stable_hasher::StableHasher<W>
193 ::std::hash::Hash::hash(self, hasher);
199 impl_stable_hash_via_hash!(i8);
200 impl_stable_hash_via_hash!(i16);
201 impl_stable_hash_via_hash!(i32);
202 impl_stable_hash_via_hash!(i64);
203 impl_stable_hash_via_hash!(isize);
205 impl_stable_hash_via_hash!(u8);
206 impl_stable_hash_via_hash!(u16);
207 impl_stable_hash_via_hash!(u32);
208 impl_stable_hash_via_hash!(u64);
209 impl_stable_hash_via_hash!(usize);
211 impl_stable_hash_via_hash!(u128);
212 impl_stable_hash_via_hash!(i128);
214 impl_stable_hash_via_hash!(char);
215 impl_stable_hash_via_hash!(());
217 impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
218 fn hash_stable<W: StableHasherResult>(&self,
220 hasher: &mut StableHasher<W>) {
221 self.get().hash_stable(ctx, hasher)
225 impl<CTX> HashStable<CTX> for f32 {
226 fn hash_stable<W: StableHasherResult>(&self,
228 hasher: &mut StableHasher<W>) {
229 let val: u32 = unsafe {
230 ::std::mem::transmute(*self)
232 val.hash_stable(ctx, hasher);
236 impl<CTX> HashStable<CTX> for f64 {
237 fn hash_stable<W: StableHasherResult>(&self,
239 hasher: &mut StableHasher<W>) {
240 let val: u64 = unsafe {
241 ::std::mem::transmute(*self)
243 val.hash_stable(ctx, hasher);
247 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
248 fn hash_stable<W: StableHasherResult>(&self,
250 hasher: &mut StableHasher<W>) {
251 (*self as i8).hash_stable(ctx, hasher);
255 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
256 fn hash_stable<W: StableHasherResult>(&self,
258 hasher: &mut StableHasher<W>) {
259 let (ref _0,) = *self;
260 _0.hash_stable(ctx, hasher);
264 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
265 fn hash_stable<W: StableHasherResult>(&self,
267 hasher: &mut StableHasher<W>) {
268 let (ref _0, ref _1) = *self;
269 _0.hash_stable(ctx, hasher);
270 _1.hash_stable(ctx, hasher);
274 impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
275 where T1: HashStable<CTX>,
279 fn hash_stable<W: StableHasherResult>(&self,
281 hasher: &mut StableHasher<W>) {
282 let (ref _0, ref _1, ref _2) = *self;
283 _0.hash_stable(ctx, hasher);
284 _1.hash_stable(ctx, hasher);
285 _2.hash_stable(ctx, hasher);
289 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
290 where T1: HashStable<CTX>,
295 fn hash_stable<W: StableHasherResult>(&self,
297 hasher: &mut StableHasher<W>) {
298 let (ref _0, ref _1, ref _2, ref _3) = *self;
299 _0.hash_stable(ctx, hasher);
300 _1.hash_stable(ctx, hasher);
301 _2.hash_stable(ctx, hasher);
302 _3.hash_stable(ctx, hasher);
306 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
307 default fn hash_stable<W: StableHasherResult>(&self,
309 hasher: &mut StableHasher<W>) {
310 self.len().hash_stable(ctx, hasher);
312 item.hash_stable(ctx, hasher);
317 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
319 fn hash_stable<W: StableHasherResult>(&self,
321 hasher: &mut StableHasher<W>) {
322 (&self[..]).hash_stable(ctx, hasher);
326 impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
327 where K: HashStable<CTX> + Eq + Hash,
332 fn hash_stable<W: StableHasherResult>(&self,
334 hasher: &mut StableHasher<W>) {
335 self.len().hash_stable(ctx, hasher);
337 kv.hash_stable(ctx, hasher);
342 impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R>
343 where K: HashStable<CTX> + Eq + Hash,
347 fn hash_stable<W: StableHasherResult>(&self,
349 hasher: &mut StableHasher<W>) {
350 self.len().hash_stable(ctx, hasher);
352 key.hash_stable(ctx, hasher);
357 impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]> where A: HashStable<CTX> {
359 fn hash_stable<W: StableHasherResult>(&self,
361 hasher: &mut StableHasher<W>) {
362 (&self[..]).hash_stable(ctx, hasher);
366 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
368 fn hash_stable<W: StableHasherResult>(&self,
370 hasher: &mut StableHasher<W>) {
371 (**self).hash_stable(ctx, hasher);
375 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
377 fn hash_stable<W: StableHasherResult>(&self,
379 hasher: &mut StableHasher<W>) {
380 (**self).hash_stable(ctx, hasher);
384 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
386 fn hash_stable<W: StableHasherResult>(&self,
388 hasher: &mut StableHasher<W>) {
389 (**self).hash_stable(ctx, hasher);
393 impl<CTX> HashStable<CTX> for str {
395 fn hash_stable<W: StableHasherResult>(&self,
397 hasher: &mut StableHasher<W>) {
398 self.len().hash(hasher);
399 self.as_bytes().hash(hasher);
404 impl<CTX> HashStable<CTX> for String {
406 fn hash_stable<W: StableHasherResult>(&self,
408 hasher: &mut StableHasher<W>) {
409 (&self[..]).hash_stable(hcx, hasher);
413 impl<HCX> ToStableHashKey<HCX> for String {
414 type KeyType = String;
416 fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
421 impl<CTX> HashStable<CTX> for bool {
423 fn hash_stable<W: StableHasherResult>(&self,
425 hasher: &mut StableHasher<W>) {
426 (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
431 impl<T, CTX> HashStable<CTX> for Option<T>
432 where T: HashStable<CTX>
435 fn hash_stable<W: StableHasherResult>(&self,
437 hasher: &mut StableHasher<W>) {
438 if let Some(ref value) = *self {
439 1u8.hash_stable(ctx, hasher);
440 value.hash_stable(ctx, hasher);
442 0u8.hash_stable(ctx, hasher);
447 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
448 where T1: HashStable<CTX>,
452 fn hash_stable<W: StableHasherResult>(&self,
454 hasher: &mut StableHasher<W>) {
455 mem::discriminant(self).hash_stable(ctx, hasher);
457 Ok(ref x) => x.hash_stable(ctx, hasher),
458 Err(ref x) => x.hash_stable(ctx, hasher),
463 impl<'a, T, CTX> HashStable<CTX> for &'a T
464 where T: HashStable<CTX> + ?Sized
467 fn hash_stable<W: StableHasherResult>(&self,
469 hasher: &mut StableHasher<W>) {
470 (**self).hash_stable(ctx, hasher);
474 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
476 fn hash_stable<W: StableHasherResult>(&self,
478 hasher: &mut StableHasher<W>) {
479 ::std::hash::Hash::hash(self, hasher);
483 impl<I: indexed_vec::Idx, T, CTX> HashStable<CTX> for indexed_vec::IndexVec<I, T>
484 where T: HashStable<CTX>,
486 fn hash_stable<W: StableHasherResult>(&self,
488 hasher: &mut StableHasher<W>) {
489 self.len().hash_stable(ctx, hasher);
491 v.hash_stable(ctx, hasher);
497 impl<I: indexed_vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I>
499 fn hash_stable<W: StableHasherResult>(&self,
501 hasher: &mut StableHasher<W>) {
502 self.words().hash_stable(ctx, hasher);
506 impl<R: indexed_vec::Idx, C: indexed_vec::Idx, CTX> HashStable<CTX>
507 for bit_set::BitMatrix<R, C>
509 fn hash_stable<W: StableHasherResult>(&self,
511 hasher: &mut StableHasher<W>) {
512 self.words().hash_stable(ctx, hasher);
516 impl_stable_hash_via_hash!(::std::path::Path);
517 impl_stable_hash_via_hash!(::std::path::PathBuf);
519 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
520 where K: ToStableHashKey<HCX> + Eq + Hash,
525 fn hash_stable<W: StableHasherResult>(&self,
527 hasher: &mut StableHasher<W>) {
528 hash_stable_hashmap(hcx, hasher, self, ToStableHashKey::to_stable_hash_key);
532 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
533 where K: ToStableHashKey<HCX> + Eq + Hash,
536 fn hash_stable<W: StableHasherResult>(&self,
538 hasher: &mut StableHasher<W>) {
539 let mut keys: Vec<_> = self.iter()
540 .map(|k| k.to_stable_hash_key(hcx))
542 keys.sort_unstable();
543 keys.hash_stable(hcx, hasher);
547 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
548 where K: ToStableHashKey<HCX>,
551 fn hash_stable<W: StableHasherResult>(&self,
553 hasher: &mut StableHasher<W>) {
554 let mut entries: Vec<_> = self.iter()
555 .map(|(k, v)| (k.to_stable_hash_key(hcx), v))
557 entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
558 entries.hash_stable(hcx, hasher);
562 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
563 where K: ToStableHashKey<HCX>,
565 fn hash_stable<W: StableHasherResult>(&self,
567 hasher: &mut StableHasher<W>) {
568 let mut keys: Vec<_> = self.iter()
569 .map(|k| k.to_stable_hash_key(hcx))
571 keys.sort_unstable();
572 keys.hash_stable(hcx, hasher);
576 pub fn hash_stable_hashmap<HCX, K, V, R, SK, F, W>(
578 hasher: &mut StableHasher<W>,
579 map: &::std::collections::HashMap<K, V, R>,
580 to_stable_hash_key: F)
584 SK: HashStable<HCX> + Ord + Clone,
585 F: Fn(&K, &HCX) -> SK,
586 W: StableHasherResult,
588 let mut entries: Vec<_> = map.iter()
589 .map(|(k, v)| (to_stable_hash_key(k, hcx), v))
591 entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
592 entries.hash_stable(hcx, hasher);
596 /// A vector container that makes sure that its items are hashed in a stable
598 pub struct StableVec<T>(Vec<T>);
600 impl<T> StableVec<T> {
601 pub fn new(v: Vec<T>) -> Self {
606 impl<T> ::std::ops::Deref for StableVec<T> {
607 type Target = Vec<T>;
609 fn deref(&self) -> &Vec<T> {
614 impl<T, HCX> HashStable<HCX> for StableVec<T>
615 where T: HashStable<HCX> + ToStableHashKey<HCX>
617 fn hash_stable<W: StableHasherResult>(&self,
619 hasher: &mut StableHasher<W>) {
620 let StableVec(ref v) = *self;
622 let mut sorted: Vec<_> = v.iter()
623 .map(|x| x.to_stable_hash_key(hcx))
625 sorted.sort_unstable();
626 sorted.hash_stable(hcx, hasher);