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.
174#[allow(dead_code)]
175pub trait HashStable<CTX> {
176    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher);
177}
178
179/// Implement this for types that can be turned into stable keys like, for
180/// example, for DefId that can be converted to a DefPathHash. This is used for
181/// bringing maps into a predictable order before hashing them.
182#[allow(dead_code)]
183pub trait ToStableHashKey<HCX> {
184    type KeyType: Ord + Clone + Sized + HashStable<HCX>;
185    fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
186}
187
188// Implement HashStable by just calling `Hash::hash()`. This works fine for
189// self-contained values that don't depend on the hashing context `CTX`.
190#[macro_export]
191macro_rules! impl_stable_hash_via_hash {
192    ($t:ty) => {
193        impl<CTX> $crate::rustc_data_structures::stable_hasher::HashStable<CTX> for $t {
194            #[inline]
195            fn hash_stable(
196                &self,
197                _: &mut CTX,
198                hasher: &mut $crate::rustc_data_structures::stable_hasher::StableHasher,
199            ) {
200                ::std::hash::Hash::hash(self, hasher);
201            }
202        }
203    };
204}
205
206impl_stable_hash_via_hash!(i8);
207impl_stable_hash_via_hash!(i16);
208impl_stable_hash_via_hash!(i32);
209impl_stable_hash_via_hash!(i64);
210impl_stable_hash_via_hash!(isize);
211
212impl_stable_hash_via_hash!(u8);
213impl_stable_hash_via_hash!(u16);
214impl_stable_hash_via_hash!(u32);
215impl_stable_hash_via_hash!(u64);
216impl_stable_hash_via_hash!(usize);
217
218impl_stable_hash_via_hash!(u128);
219impl_stable_hash_via_hash!(i128);
220
221impl_stable_hash_via_hash!(char);
222impl_stable_hash_via_hash!(());
223
224impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
225    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
226        self.get().hash_stable(ctx, hasher)
227    }
228}
229
230impl<CTX> HashStable<CTX> for f32 {
231    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
232        let val: u32 = f32::to_bits(*self);
233        val.hash_stable(ctx, hasher);
234    }
235}
236
237impl<CTX> HashStable<CTX> for f64 {
238    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
239        let val: u64 = f64::to_bits(*self);
240        val.hash_stable(ctx, hasher);
241    }
242}
243
244impl<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);
247    }
248}
249
250impl<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);
254    }
255}
256
257impl<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);
262    }
263}
264
265impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
266where
267    T1: HashStable<CTX>,
268    T2: HashStable<CTX>,
269    T3: HashStable<CTX>,
270{
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);
276    }
277}
278
279impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
280where
281    T1: HashStable<CTX>,
282    T2: HashStable<CTX>,
283    T3: HashStable<CTX>,
284    T4: HashStable<CTX>,
285{
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);
292    }
293}
294
295impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
296    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
297        self.len().hash_stable(ctx, hasher);
298        for item in self {
299            item.hash_stable(ctx, hasher);
300        }
301    }
302}
303
304impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
305    #[inline]
306    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
307        (&self[..]).hash_stable(ctx, hasher);
308    }
309}
310
311impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
312    #[inline]
313    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
314        (**self).hash_stable(ctx, hasher);
315    }
316}
317
318impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
319    #[inline]
320    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
321        (**self).hash_stable(ctx, hasher);
322    }
323}
324
325impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
326    #[inline]
327    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
328        (**self).hash_stable(ctx, hasher);
329    }
330}
331
332impl<CTX> HashStable<CTX> for str {
333    #[inline]
334    fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
335        self.len().hash(hasher);
336        self.as_bytes().hash(hasher);
337    }
338}
339
340impl<CTX> HashStable<CTX> for String {
341    #[inline]
342    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
343        (&self[..]).hash_stable(hcx, hasher);
344    }
345}
346
347impl<HCX> ToStableHashKey<HCX> for String {
348    type KeyType = String;
349
350    #[inline]
351    fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
352        self.clone()
353    }
354}
355
356impl<CTX> HashStable<CTX> for bool {
357    #[inline]
358    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
359        (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
360    }
361}
362
363impl<T, CTX> HashStable<CTX> for Option<T>
364where
365    T: HashStable<CTX>,
366{
367    #[inline]
368    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
369        if let Some(ref value) = *self {
370            1u8.hash_stable(ctx, hasher);
371            value.hash_stable(ctx, hasher);
372        } else {
373            0u8.hash_stable(ctx, hasher);
374        }
375    }
376}
377
378impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
379where
380    T1: HashStable<CTX>,
381    T2: HashStable<CTX>,
382{
383    #[inline]
384    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
385        mem::discriminant(self).hash_stable(ctx, hasher);
386        match *self {
387            Ok(ref x) => x.hash_stable(ctx, hasher),
388            Err(ref x) => x.hash_stable(ctx, hasher),
389        }
390    }
391}
392
393impl<'a, T, CTX> HashStable<CTX> for &'a T
394where
395    T: HashStable<CTX> + ?Sized,
396{
397    #[inline]
398    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
399        (**self).hash_stable(ctx, hasher);
400    }
401}
402
403impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
404    #[inline]
405    fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
406        ::std::hash::Hash::hash(self, hasher);
407    }
408}
409
410// impl<I: ::indexed_vec::Idx, T, CTX> HashStable<CTX> for
411// ::indexed_vec::IndexVec<I, T> where
412//     T: HashStable<CTX>,
413// {
414//     fn hash_stable<W: StableHasherResult>(&self, ctx: &mut CTX, hasher: &mut
415// StableHasher<W>) {         self.len().hash_stable(ctx, hasher);
416//         for v in &self.raw {
417//             v.hash_stable(ctx, hasher);
418//         }
419//     }
420// }
421
422// impl<I: ::indexed_vec::Idx, CTX> HashStable<CTX> for ::bit_set::BitSet<I> {
423//     fn hash_stable<W: StableHasherResult>(&self, ctx: &mut CTX, hasher: &mut
424// StableHasher<W>) {         self.words().hash_stable(ctx, hasher);
425//     }
426// }
427
428impl_stable_hash_via_hash!(::std::path::Path);
429impl_stable_hash_via_hash!(::std::path::PathBuf);
430
431impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
432where
433    K: ToStableHashKey<HCX> + Eq,
434    V: HashStable<HCX>,
435    R: BuildHasher,
436{
437    #[inline]
438    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
439        stable_hash_reduce(
440            hcx,
441            hasher,
442            self.iter(),
443            self.len(),
444            |hasher, hcx, (key, value)| {
445                let key = key.to_stable_hash_key(hcx);
446                key.hash_stable(hcx, hasher);
447                value.hash_stable(hcx, hasher);
448            },
449        );
450    }
451}
452
453impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
454where
455    K: ToStableHashKey<HCX> + Eq,
456    R: BuildHasher,
457{
458    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
459        stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| {
460            let key = key.to_stable_hash_key(hcx);
461            key.hash_stable(hcx, hasher);
462        });
463    }
464}
465
466impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
467where
468    K: ToStableHashKey<HCX>,
469    V: HashStable<HCX>,
470{
471    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
472        stable_hash_reduce(
473            hcx,
474            hasher,
475            self.iter(),
476            self.len(),
477            |hasher, hcx, (key, value)| {
478                let key = key.to_stable_hash_key(hcx);
479                key.hash_stable(hcx, hasher);
480                value.hash_stable(hcx, hasher);
481            },
482        );
483    }
484}
485
486impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
487where
488    K: ToStableHashKey<HCX>,
489{
490    fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
491        stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| {
492            let key = key.to_stable_hash_key(hcx);
493            key.hash_stable(hcx, hasher);
494        });
495    }
496}
497
498#[allow(dead_code)]
499fn stable_hash_reduce<HCX, I, C, F>(
500    hcx: &mut HCX,
501    hasher: &mut StableHasher,
502    mut collection: C,
503    length: usize,
504    hash_function: F,
505) where
506    C: Iterator<Item = I>,
507    F: Fn(&mut StableHasher, &mut HCX, I),
508{
509    length.hash_stable(hcx, hasher);
510
511    match length {
512        1 => {
513            hash_function(hasher, hcx, collection.next().unwrap());
514        }
515        _ => {
516            let hash = collection
517                .map(|value| {
518                    let mut hasher = StableHasher::new();
519                    hash_function(&mut hasher, hcx, value);
520                    hasher.finish::<u128>()
521                })
522                .reduce(|accum, value| accum.wrapping_add(value));
523            hash.hash_stable(hcx, hasher);
524        }
525    }
526}
swc_common/rustc_data_structures/stable_hasher.rs

swc_common/rustc_data_structures/
stable_hasher.rs
