1 use std::hash::{Hash, Hasher, BuildHasher};
2 use std::marker::PhantomData;
4 use crate::sip128::SipHasher128;
5 use crate::indexed_vec;
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<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),
40 pub fn finish(self) -> W {
45 impl StableHasherResult for u128 {
46 fn finish(hasher: StableHasher<Self>) -> Self {
47 let (_0, _1) = hasher.finalize();
48 (_0 as u128) | ((_1 as u128) << 64)
52 impl StableHasherResult for u64 {
53 fn finish(hasher: StableHasher<Self>) -> Self {
58 impl<W> StableHasher<W> {
60 pub fn finalize(self) -> (u64, u64) {
61 self.state.finish128()
65 pub fn bytes_hashed(&self) -> u64 {
70 impl<W> Hasher for StableHasher<W> {
71 fn finish(&self) -> u64 {
72 panic!("use StableHasher::finalize instead");
76 fn write(&mut self, bytes: &[u8]) {
77 self.state.write(bytes);
78 self.bytes_hashed += bytes.len() as u64;
82 fn write_u8(&mut self, i: u8) {
83 self.state.write_u8(i);
84 self.bytes_hashed += 1;
88 fn write_u16(&mut self, i: u16) {
89 self.state.write_u16(i.to_le());
90 self.bytes_hashed += 2;
94 fn write_u32(&mut self, i: u32) {
95 self.state.write_u32(i.to_le());
96 self.bytes_hashed += 4;
100 fn write_u64(&mut self, i: u64) {
101 self.state.write_u64(i.to_le());
102 self.bytes_hashed += 8;
106 fn write_u128(&mut self, i: u128) {
107 self.state.write_u128(i.to_le());
108 self.bytes_hashed += 16;
112 fn write_usize(&mut self, i: usize) {
113 // Always treat usize as u64 so we get the same results on 32 and 64 bit
114 // platforms. This is important for symbol hashes when cross compiling,
116 self.state.write_u64((i as u64).to_le());
117 self.bytes_hashed += 8;
121 fn write_i8(&mut self, i: i8) {
122 self.state.write_i8(i);
123 self.bytes_hashed += 1;
127 fn write_i16(&mut self, i: i16) {
128 self.state.write_i16(i.to_le());
129 self.bytes_hashed += 2;
133 fn write_i32(&mut self, i: i32) {
134 self.state.write_i32(i.to_le());
135 self.bytes_hashed += 4;
139 fn write_i64(&mut self, i: i64) {
140 self.state.write_i64(i.to_le());
141 self.bytes_hashed += 8;
145 fn write_i128(&mut self, i: i128) {
146 self.state.write_i128(i.to_le());
147 self.bytes_hashed += 16;
151 fn write_isize(&mut self, i: isize) {
152 // Always treat isize as i64 so we get the same results on 32 and 64 bit
153 // platforms. This is important for symbol hashes when cross compiling,
155 self.state.write_i64((i as i64).to_le());
156 self.bytes_hashed += 8;
160 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
161 /// stable across multiple compilation sessions.
162 pub trait HashStable<CTX> {
163 fn hash_stable<W: StableHasherResult>(&self,
165 hasher: &mut StableHasher<W>);
168 /// Implement this for types that can be turned into stable keys like, for
169 /// example, for DefId that can be converted to a DefPathHash. This is used for
170 /// bringing maps into a predictable order before hashing them.
171 pub trait ToStableHashKey<HCX> {
172 type KeyType: Ord + Clone + Sized + HashStable<HCX>;
173 fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
176 // Implement HashStable by just calling `Hash::hash()`. This works fine for
177 // self-contained values that don't depend on the hashing context `CTX`.
179 macro_rules! impl_stable_hash_via_hash {
181 impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
183 fn hash_stable<W: $crate::stable_hasher::StableHasherResult>(
186 hasher: &mut $crate::stable_hasher::StableHasher<W>
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 ::std::num::NonZeroU32 {
213 fn hash_stable<W: StableHasherResult>(&self,
215 hasher: &mut StableHasher<W>) {
216 self.get().hash_stable(ctx, hasher)
220 impl<CTX> HashStable<CTX> for f32 {
221 fn hash_stable<W: StableHasherResult>(&self,
223 hasher: &mut StableHasher<W>) {
224 let val: u32 = unsafe {
225 ::std::mem::transmute(*self)
227 val.hash_stable(ctx, hasher);
231 impl<CTX> HashStable<CTX> for f64 {
232 fn hash_stable<W: StableHasherResult>(&self,
234 hasher: &mut StableHasher<W>) {
235 let val: u64 = unsafe {
236 ::std::mem::transmute(*self)
238 val.hash_stable(ctx, hasher);
242 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
243 fn hash_stable<W: StableHasherResult>(&self,
245 hasher: &mut StableHasher<W>) {
246 (*self as i8).hash_stable(ctx, hasher);
250 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
251 fn hash_stable<W: StableHasherResult>(&self,
253 hasher: &mut StableHasher<W>) {
254 let (ref _0,) = *self;
255 _0.hash_stable(ctx, hasher);
259 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
260 fn hash_stable<W: StableHasherResult>(&self,
262 hasher: &mut StableHasher<W>) {
263 let (ref _0, ref _1) = *self;
264 _0.hash_stable(ctx, hasher);
265 _1.hash_stable(ctx, hasher);
269 impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
270 where T1: HashStable<CTX>,
274 fn hash_stable<W: StableHasherResult>(&self,
276 hasher: &mut StableHasher<W>) {
277 let (ref _0, ref _1, ref _2) = *self;
278 _0.hash_stable(ctx, hasher);
279 _1.hash_stable(ctx, hasher);
280 _2.hash_stable(ctx, hasher);
284 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
285 where T1: HashStable<CTX>,
290 fn hash_stable<W: StableHasherResult>(&self,
292 hasher: &mut StableHasher<W>) {
293 let (ref _0, ref _1, ref _2, ref _3) = *self;
294 _0.hash_stable(ctx, hasher);
295 _1.hash_stable(ctx, hasher);
296 _2.hash_stable(ctx, hasher);
297 _3.hash_stable(ctx, hasher);
301 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
302 default fn hash_stable<W: StableHasherResult>(&self,
304 hasher: &mut StableHasher<W>) {
305 self.len().hash_stable(ctx, hasher);
307 item.hash_stable(ctx, hasher);
312 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
314 fn hash_stable<W: StableHasherResult>(&self,
316 hasher: &mut StableHasher<W>) {
317 (&self[..]).hash_stable(ctx, hasher);
321 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
323 fn hash_stable<W: StableHasherResult>(&self,
325 hasher: &mut StableHasher<W>) {
326 (**self).hash_stable(ctx, hasher);
330 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
332 fn hash_stable<W: StableHasherResult>(&self,
334 hasher: &mut StableHasher<W>) {
335 (**self).hash_stable(ctx, hasher);
339 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
341 fn hash_stable<W: StableHasherResult>(&self,
343 hasher: &mut StableHasher<W>) {
344 (**self).hash_stable(ctx, hasher);
348 impl<CTX> HashStable<CTX> for str {
350 fn hash_stable<W: StableHasherResult>(&self,
352 hasher: &mut StableHasher<W>) {
353 self.len().hash(hasher);
354 self.as_bytes().hash(hasher);
359 impl<CTX> HashStable<CTX> for String {
361 fn hash_stable<W: StableHasherResult>(&self,
363 hasher: &mut StableHasher<W>) {
364 (&self[..]).hash_stable(hcx, hasher);
368 impl<HCX> ToStableHashKey<HCX> for String {
369 type KeyType = String;
371 fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
376 impl<CTX> HashStable<CTX> for bool {
378 fn hash_stable<W: StableHasherResult>(&self,
380 hasher: &mut StableHasher<W>) {
381 (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
386 impl<T, CTX> HashStable<CTX> for Option<T>
387 where T: HashStable<CTX>
390 fn hash_stable<W: StableHasherResult>(&self,
392 hasher: &mut StableHasher<W>) {
393 if let Some(ref value) = *self {
394 1u8.hash_stable(ctx, hasher);
395 value.hash_stable(ctx, hasher);
397 0u8.hash_stable(ctx, hasher);
402 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
403 where T1: HashStable<CTX>,
407 fn hash_stable<W: StableHasherResult>(&self,
409 hasher: &mut StableHasher<W>) {
410 mem::discriminant(self).hash_stable(ctx, hasher);
412 Ok(ref x) => x.hash_stable(ctx, hasher),
413 Err(ref x) => x.hash_stable(ctx, hasher),
418 impl<'a, T, CTX> HashStable<CTX> for &'a T
419 where T: HashStable<CTX> + ?Sized
422 fn hash_stable<W: StableHasherResult>(&self,
424 hasher: &mut StableHasher<W>) {
425 (**self).hash_stable(ctx, hasher);
429 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
431 fn hash_stable<W: StableHasherResult>(&self,
433 hasher: &mut StableHasher<W>) {
434 ::std::hash::Hash::hash(self, hasher);
438 impl<I: indexed_vec::Idx, T, CTX> HashStable<CTX> for indexed_vec::IndexVec<I, T>
439 where T: HashStable<CTX>,
441 fn hash_stable<W: StableHasherResult>(&self,
443 hasher: &mut StableHasher<W>) {
444 self.len().hash_stable(ctx, hasher);
446 v.hash_stable(ctx, hasher);
452 impl<I: indexed_vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I>
454 fn hash_stable<W: StableHasherResult>(&self,
456 hasher: &mut StableHasher<W>) {
457 self.words().hash_stable(ctx, hasher);
461 impl_stable_hash_via_hash!(::std::path::Path);
462 impl_stable_hash_via_hash!(::std::path::PathBuf);
464 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
465 where K: ToStableHashKey<HCX> + Eq + Hash,
470 fn hash_stable<W: StableHasherResult>(&self,
472 hasher: &mut StableHasher<W>) {
473 hash_stable_hashmap(hcx, hasher, self, ToStableHashKey::to_stable_hash_key);
477 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
478 where K: ToStableHashKey<HCX> + Eq + Hash,
481 fn hash_stable<W: StableHasherResult>(&self,
483 hasher: &mut StableHasher<W>) {
484 let mut keys: Vec<_> = self.iter()
485 .map(|k| k.to_stable_hash_key(hcx))
487 keys.sort_unstable();
488 keys.hash_stable(hcx, hasher);
492 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
493 where K: ToStableHashKey<HCX>,
496 fn hash_stable<W: StableHasherResult>(&self,
498 hasher: &mut StableHasher<W>) {
499 let mut entries: Vec<_> = self.iter()
500 .map(|(k, v)| (k.to_stable_hash_key(hcx), v))
502 entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
503 entries.hash_stable(hcx, hasher);
507 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
508 where K: ToStableHashKey<HCX>,
510 fn hash_stable<W: StableHasherResult>(&self,
512 hasher: &mut StableHasher<W>) {
513 let mut keys: Vec<_> = self.iter()
514 .map(|k| k.to_stable_hash_key(hcx))
516 keys.sort_unstable();
517 keys.hash_stable(hcx, hasher);
521 pub fn hash_stable_hashmap<HCX, K, V, R, SK, F, W>(
523 hasher: &mut StableHasher<W>,
524 map: &::std::collections::HashMap<K, V, R>,
525 to_stable_hash_key: F)
529 SK: HashStable<HCX> + Ord + Clone,
530 F: Fn(&K, &HCX) -> SK,
531 W: StableHasherResult,
533 let mut entries: Vec<_> = map.iter()
534 .map(|(k, v)| (to_stable_hash_key(k, hcx), v))
536 entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
537 entries.hash_stable(hcx, hasher);
541 /// A vector container that makes sure that its items are hashed in a stable
543 pub struct StableVec<T>(Vec<T>);
545 impl<T> StableVec<T> {
546 pub fn new(v: Vec<T>) -> Self {
551 impl<T> ::std::ops::Deref for StableVec<T> {
552 type Target = Vec<T>;
554 fn deref(&self) -> &Vec<T> {
559 impl<T, HCX> HashStable<HCX> for StableVec<T>
560 where T: HashStable<HCX> + ToStableHashKey<HCX>
562 fn hash_stable<W: StableHasherResult>(&self,
564 hasher: &mut StableHasher<W>) {
565 let StableVec(ref v) = *self;
567 let mut sorted: Vec<_> = v.iter()
568 .map(|x| x.to_stable_hash_key(hcx))
570 sorted.sort_unstable();
571 sorted.hash_stable(hcx, hasher);