swc_common/rustc_data_structures/
stable_hasher.rs

1use std::{
2    hash::{BuildHasher, Hash, Hasher},
3    mem,
4};
5
6use siphasher::sip128::{Hash128, Hasher128, SipHasher24};
7
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*.
11///
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.
15pub struct StableHasher {
16    state: SipHasher24,
17}
18
19impl ::std::fmt::Debug for StableHasher {
20    fn fmt(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
21        write!(f, "{:?}", self.state)
22    }
23}
24
25pub trait StableHasherResult: Sized {
26    fn finish(hasher: StableHasher) -> Self;
27}
28
29impl StableHasher {
30    #[inline]
31    pub fn new() -> Self {
32        StableHasher {
33            state: SipHasher24::new_with_keys(0, 0),
34        }
35    }
36
37    #[inline]
38    pub fn finish<W: StableHasherResult>(self) -> W {
39        W::finish(self)
40    }
41}
42
43impl StableHasherResult for u128 {
44    #[inline]
45    fn finish(hasher: StableHasher) -> Self {
46        hasher.finalize().as_u128()
47    }
48}
49
50impl StableHasherResult for u64 {
51    #[inline]
52    fn finish(hasher: StableHasher) -> Self {
53        hasher.finalize().h1
54    }
55}
56
57impl StableHasher {
58    #[inline]
59    pub fn finalize(self) -> Hash128 {
60        self.state.finish128()
61    }
62}
63
64impl Hasher for StableHasher {
65    fn finish(&self) -> u64 {
66        panic!("use StableHasher::finalize instead");
67    }
68
69    #[inline]
70    fn write(&mut self, bytes: &[u8]) {
71        self.state.write(bytes);
72    }
73
74    #[inline]
75    fn write_u8(&mut self, i: u8) {
76        self.state.write_u8(i);
77    }
78
79    #[inline]
80    fn write_u16(&mut self, i: u16) {
81        self.state.write_u16(i.to_le());
82    }
83
84    #[inline]
85    fn write_u32(&mut self, i: u32) {
86        self.state.write_u32(i.to_le());
87    }
88
89    #[inline]
90    fn write_u64(&mut self, i: u64) {
91        self.state.write_u64(i.to_le());
92    }
93
94    #[inline]
95    fn write_u128(&mut self, i: u128) {
96        self.state.write_u128(i.to_le());
97    }
98
99    #[inline]
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,
103        // for example.
104        self.state.write_u64((i as u64).to_le());
105    }
106
107    #[inline]
108    fn write_i8(&mut self, i: i8) {
109        self.state.write_i8(i);
110    }
111
112    #[inline]
113    fn write_i16(&mut self, i: i16) {
114        self.state.write_i16(i.to_le());
115    }
116
117    #[inline]
118    fn write_i32(&mut self, i: i32) {
119        self.state.write_i32(i.to_le());
120    }
121
122    #[inline]
123    fn write_i64(&mut self, i: i64) {
124        self.state.write_i64(i.to_le());
125    }
126
127    #[inline]
128    fn write_i128(&mut self, i: i128) {
129        self.state.write_i128(i.to_le());
130    }
131
132    #[inline]
133    fn write_isize(&mut self, i: isize) {
134        // Always treat isize as a 64-bit number so we get the same results on 32 and 64
135        // bit platforms. This is important for symbol hashes when cross
136        // compiling, for example. Sign extending here is preferable as it means
137        // that the same negative number hashes the same on both 32 and 64 bit
138        // platforms.
139        let value = i as u64;
140
141        // Cold path
142        #[cold]
143        #[inline(never)]
144        fn hash_value(state: &mut SipHasher24, value: u64) {
145            state.write_u8(0xff);
146            state.write_u64(value.to_le());
147        }
148
149        // `isize` values often seem to have a small (positive) numeric value in
150        // practice. To exploit this, if the value is small, we will hash a
151        // smaller amount of bytes. However, we cannot just skip the leading
152        // zero bytes, as that would produce the same hash e.g. if you hash two
153        // values that have the same bit pattern when they are swapped. See https://github.com/rust-lang/rust/pull/93014 for context.
154        //
155        // Therefore, we employ the following strategy:
156        // 1) When we encounter a value that fits within a single byte (the most common
157        // case), we hash just that byte. This is the most common case that is
158        // being optimized. However, we do not do this for the value 0xFF, as
159        // that is a reserved prefix (a bit like in UTF-8). 2) When we encounter
160        // a larger value, we hash a "marker" 0xFF and then the corresponding
161        // 8 bytes. Since this prefix cannot occur when we hash a single byte, when we
162        // hash two `isize`s that fit within a different amount of bytes, they
163        // should always produce a different byte stream for the hasher.
164        if value < 0xff {
165            self.state.write_u8(value as u8);
166        } else {
167            hash_value(&mut self.state, value);
168        }
169    }
170}
171
172/// Something that implements `HashStable<CTX>` can be hashed in a way that is
173/// stable across multiple compilation sessions.
174pub trait HashStable<CTX> {
175    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher);
176}
177
178/// Implement this for types that can be turned into stable keys like, for
179/// example, for DefId that can be converted to a DefPathHash. This is used for
180/// bringing maps into a predictable order before hashing them.
181pub trait ToStableHashKey<HCX> {
182    type KeyType: Ord + Clone + Sized + HashStable<HCX>;
183    fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
184}
185
186// Implement HashStable by just calling `Hash::hash()`. This works fine for
187// self-contained values that don't depend on the hashing context `CTX`.
188#[macro_export]
189macro_rules! impl_stable_hash_via_hash {
190    ($t:ty) => {
191        impl<CTX> $crate::rustc_data_structures::stable_hasher::HashStable<CTX> for $t {
192            #[inline]
193            fn hash_stable(
194                &self,
195                _: &mut CTX,
196                hasher: &mut $crate::rustc_data_structures::stable_hasher::StableHasher,
197            ) {
198                ::std::hash::Hash::hash(self, hasher);
199            }
200        }
201    };
202}
203
204impl_stable_hash_via_hash!(i8);
205impl_stable_hash_via_hash!(i16);
206impl_stable_hash_via_hash!(i32);
207impl_stable_hash_via_hash!(i64);
208impl_stable_hash_via_hash!(isize);
209
210impl_stable_hash_via_hash!(u8);
211impl_stable_hash_via_hash!(u16);
212impl_stable_hash_via_hash!(u32);
213impl_stable_hash_via_hash!(u64);
214impl_stable_hash_via_hash!(usize);
215
216impl_stable_hash_via_hash!(u128);
217impl_stable_hash_via_hash!(i128);
218
219impl_stable_hash_via_hash!(char);
220impl_stable_hash_via_hash!(());
221
222impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
223    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
224        self.get().hash_stable(ctx, hasher)
225    }
226}
227
228impl<CTX> HashStable<CTX> for f32 {
229    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
230        let val: u32 = unsafe { ::std::mem::transmute(*self) };
231        val.hash_stable(ctx, hasher);
232    }
233}
234
235impl<CTX> HashStable<CTX> for f64 {
236    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
237        let val: u64 = unsafe { ::std::mem::transmute(*self) };
238        val.hash_stable(ctx, hasher);
239    }
240}
241
242impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
243    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
244        (*self as i8).hash_stable(ctx, hasher);
245    }
246}
247
248impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
249    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
250        let (ref _0,) = *self;
251        _0.hash_stable(ctx, hasher);
252    }
253}
254
255impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
256    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
257        let (ref _0, ref _1) = *self;
258        _0.hash_stable(ctx, hasher);
259        _1.hash_stable(ctx, hasher);
260    }
261}
262
263impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
264where
265    T1: HashStable<CTX>,
266    T2: HashStable<CTX>,
267    T3: HashStable<CTX>,
268{
269    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
270        let (ref _0, ref _1, ref _2) = *self;
271        _0.hash_stable(ctx, hasher);
272        _1.hash_stable(ctx, hasher);
273        _2.hash_stable(ctx, hasher);
274    }
275}
276
277impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
278where
279    T1: HashStable<CTX>,
280    T2: HashStable<CTX>,
281    T3: HashStable<CTX>,
282    T4: HashStable<CTX>,
283{
284    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
285        let (ref _0, ref _1, ref _2, ref _3) = *self;
286        _0.hash_stable(ctx, hasher);
287        _1.hash_stable(ctx, hasher);
288        _2.hash_stable(ctx, hasher);
289        _3.hash_stable(ctx, hasher);
290    }
291}
292
293impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
294    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
295        self.len().hash_stable(ctx, hasher);
296        for item in self {
297            item.hash_stable(ctx, hasher);
298        }
299    }
300}
301
302impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
303    #[inline]
304    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
305        (&self[..]).hash_stable(ctx, hasher);
306    }
307}
308
309impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
310    #[inline]
311    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
312        (**self).hash_stable(ctx, hasher);
313    }
314}
315
316impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
317    #[inline]
318    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
319        (**self).hash_stable(ctx, hasher);
320    }
321}
322
323impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
324    #[inline]
325    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
326        (**self).hash_stable(ctx, hasher);
327    }
328}
329
330impl<CTX> HashStable<CTX> for str {
331    #[inline]
332    fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
333        self.len().hash(hasher);
334        self.as_bytes().hash(hasher);
335    }
336}
337
338impl<CTX> HashStable<CTX> for String {
339    #[inline]
340    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
341        (&self[..]).hash_stable(hcx, hasher);
342    }
343}
344
345impl<HCX> ToStableHashKey<HCX> for String {
346    type KeyType = String;
347
348    #[inline]
349    fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
350        self.clone()
351    }
352}
353
354impl<CTX> HashStable<CTX> for bool {
355    #[inline]
356    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
357        (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
358    }
359}
360
361impl<T, CTX> HashStable<CTX> for Option<T>
362where
363    T: HashStable<CTX>,
364{
365    #[inline]
366    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
367        if let Some(ref value) = *self {
368            1u8.hash_stable(ctx, hasher);
369            value.hash_stable(ctx, hasher);
370        } else {
371            0u8.hash_stable(ctx, hasher);
372        }
373    }
374}
375
376impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
377where
378    T1: HashStable<CTX>,
379    T2: HashStable<CTX>,
380{
381    #[inline]
382    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
383        mem::discriminant(self).hash_stable(ctx, hasher);
384        match *self {
385            Ok(ref x) => x.hash_stable(ctx, hasher),
386            Err(ref x) => x.hash_stable(ctx, hasher),
387        }
388    }
389}
390
391impl<'a, T, CTX> HashStable<CTX> for &'a T
392where
393    T: HashStable<CTX> + ?Sized,
394{
395    #[inline]
396    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
397        (**self).hash_stable(ctx, hasher);
398    }
399}
400
401impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
402    #[inline]
403    fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
404        ::std::hash::Hash::hash(self, hasher);
405    }
406}
407
408// impl<I: ::indexed_vec::Idx, T, CTX> HashStable<CTX> for
409// ::indexed_vec::IndexVec<I, T> where
410//     T: HashStable<CTX>,
411// {
412//     fn hash_stable<W: StableHasherResult>(&self, ctx: &mut CTX, hasher: &mut
413// StableHasher<W>) {         self.len().hash_stable(ctx, hasher);
414//         for v in &self.raw {
415//             v.hash_stable(ctx, hasher);
416//         }
417//     }
418// }
419
420// impl<I: ::indexed_vec::Idx, CTX> HashStable<CTX> for ::bit_set::BitSet<I> {
421//     fn hash_stable<W: StableHasherResult>(&self, ctx: &mut CTX, hasher: &mut
422// StableHasher<W>) {         self.words().hash_stable(ctx, hasher);
423//     }
424// }
425
426impl_stable_hash_via_hash!(::std::path::Path);
427impl_stable_hash_via_hash!(::std::path::PathBuf);
428
429impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
430where
431    K: ToStableHashKey<HCX> + Eq,
432    V: HashStable<HCX>,
433    R: BuildHasher,
434{
435    #[inline]
436    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
437        stable_hash_reduce(
438            hcx,
439            hasher,
440            self.iter(),
441            self.len(),
442            |hasher, hcx, (key, value)| {
443                let key = key.to_stable_hash_key(hcx);
444                key.hash_stable(hcx, hasher);
445                value.hash_stable(hcx, hasher);
446            },
447        );
448    }
449}
450
451impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
452where
453    K: ToStableHashKey<HCX> + Eq,
454    R: BuildHasher,
455{
456    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
457        stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| {
458            let key = key.to_stable_hash_key(hcx);
459            key.hash_stable(hcx, hasher);
460        });
461    }
462}
463
464impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
465where
466    K: ToStableHashKey<HCX>,
467    V: HashStable<HCX>,
468{
469    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
470        stable_hash_reduce(
471            hcx,
472            hasher,
473            self.iter(),
474            self.len(),
475            |hasher, hcx, (key, value)| {
476                let key = key.to_stable_hash_key(hcx);
477                key.hash_stable(hcx, hasher);
478                value.hash_stable(hcx, hasher);
479            },
480        );
481    }
482}
483
484impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
485where
486    K: ToStableHashKey<HCX>,
487{
488    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
489        stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| {
490            let key = key.to_stable_hash_key(hcx);
491            key.hash_stable(hcx, hasher);
492        });
493    }
494}
495
496fn stable_hash_reduce<HCX, I, C, F>(
497    hcx: &mut HCX,
498    hasher: &mut StableHasher,
499    mut collection: C,
500    length: usize,
501    hash_function: F,
502) where
503    C: Iterator<Item = I>,
504    F: Fn(&mut StableHasher, &mut HCX, I),
505{
506    length.hash_stable(hcx, hasher);
507
508    match length {
509        1 => {
510            hash_function(hasher, hcx, collection.next().unwrap());
511        }
512        _ => {
513            let hash = collection
514                .map(|value| {
515                    let mut hasher = StableHasher::new();
516                    hash_function(&mut hasher, hcx, value);
517                    hasher.finish::<u128>()
518                })
519                .reduce(|accum, value| accum.wrapping_add(value));
520            hash.hash_stable(hcx, hasher);
521        }
522    }
523}
swc_common/rustc_data_structures/stable_hasher.rs

swc_common/rustc_data_structures/
stable_hasher.rs
