]>
Commit | Line | Data |
---|---|---|
9fa01778 | 1 | use crate::sip128::SipHasher128; |
e74abb32 | 2 | use rustc_index::bit_set; |
dfeec247 XL |
3 | use rustc_index::vec; |
4 | use smallvec::SmallVec; | |
5 | use std::hash::{BuildHasher, Hash, Hasher}; | |
064997fb | 6 | use std::marker::PhantomData; |
dfeec247 | 7 | use std::mem; |
476ff2be | 8 | |
1b1a35ee XL |
9 | #[cfg(test)] |
10 | mod tests; | |
11 | ||
abe05a73 XL |
12 | /// When hashing something that ends up affecting properties like symbol names, |
13 | /// we want these symbol names to be calculated independently of other factors | |
14 | /// like what architecture you're compiling *from*. | |
476ff2be | 15 | /// |
abe05a73 XL |
16 | /// To that end we always convert integers to little-endian format before |
17 | /// hashing and the architecture dependent `isize` and `usize` types are | |
18 | /// extended to 64 bits if needed. | |
e74abb32 | 19 | pub struct StableHasher { |
abe05a73 | 20 | state: SipHasher128, |
476ff2be SL |
21 | } |
22 | ||
e74abb32 | 23 | impl ::std::fmt::Debug for StableHasher { |
29967ef6 | 24 | fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { |
cc61c64b XL |
25 | write!(f, "{:?}", self.state) |
26 | } | |
27 | } | |
28 | ||
476ff2be | 29 | pub trait StableHasherResult: Sized { |
e74abb32 | 30 | fn finish(hasher: StableHasher) -> Self; |
476ff2be SL |
31 | } |
32 | ||
e74abb32 | 33 | impl StableHasher { |
74b04a01 | 34 | #[inline] |
476ff2be | 35 | pub fn new() -> Self { |
dfeec247 | 36 | StableHasher { state: SipHasher128::new_with_keys(0, 0) } |
476ff2be SL |
37 | } |
38 | ||
6a06907d | 39 | #[inline] |
e74abb32 | 40 | pub fn finish<W: StableHasherResult>(self) -> W { |
476ff2be SL |
41 | W::finish(self) |
42 | } | |
43 | } | |
44 | ||
041b39d2 | 45 | impl StableHasherResult for u128 { |
a2a8927a | 46 | #[inline] |
e74abb32 | 47 | fn finish(hasher: StableHasher) -> Self { |
abe05a73 | 48 | let (_0, _1) = hasher.finalize(); |
dc9dc135 | 49 | u128::from(_0) | (u128::from(_1) << 64) |
041b39d2 XL |
50 | } |
51 | } | |
52 | ||
476ff2be | 53 | impl StableHasherResult for u64 { |
a2a8927a | 54 | #[inline] |
e74abb32 | 55 | fn finish(hasher: StableHasher) -> Self { |
abe05a73 | 56 | hasher.finalize().0 |
476ff2be SL |
57 | } |
58 | } | |
59 | ||
e74abb32 | 60 | impl StableHasher { |
476ff2be | 61 | #[inline] |
abe05a73 XL |
62 | pub fn finalize(self) -> (u64, u64) { |
63 | self.state.finish128() | |
476ff2be | 64 | } |
476ff2be SL |
65 | } |
66 | ||
e74abb32 | 67 | impl Hasher for StableHasher { |
476ff2be | 68 | fn finish(&self) -> u64 { |
abe05a73 | 69 | panic!("use StableHasher::finalize instead"); |
476ff2be SL |
70 | } |
71 | ||
72 | #[inline] | |
73 | fn write(&mut self, bytes: &[u8]) { | |
74 | self.state.write(bytes); | |
476ff2be SL |
75 | } |
76 | ||
04454e1e FG |
77 | #[inline] |
78 | fn write_str(&mut self, s: &str) { | |
79 | self.state.write_str(s); | |
80 | } | |
81 | ||
82 | #[inline] | |
83 | fn write_length_prefix(&mut self, len: usize) { | |
84 | // Our impl for `usize` will extend it if needed. | |
85 | self.write_usize(len); | |
86 | } | |
87 | ||
476ff2be SL |
88 | #[inline] |
89 | fn write_u8(&mut self, i: u8) { | |
90 | self.state.write_u8(i); | |
476ff2be SL |
91 | } |
92 | ||
93 | #[inline] | |
94 | fn write_u16(&mut self, i: u16) { | |
5099ac24 | 95 | self.state.short_write(i.to_le_bytes()); |
476ff2be SL |
96 | } |
97 | ||
98 | #[inline] | |
99 | fn write_u32(&mut self, i: u32) { | |
5099ac24 | 100 | self.state.short_write(i.to_le_bytes()); |
476ff2be SL |
101 | } |
102 | ||
103 | #[inline] | |
104 | fn write_u64(&mut self, i: u64) { | |
5099ac24 | 105 | self.state.short_write(i.to_le_bytes()); |
abe05a73 XL |
106 | } |
107 | ||
108 | #[inline] | |
109 | fn write_u128(&mut self, i: u128) { | |
5099ac24 | 110 | self.state.write(&i.to_le_bytes()); |
476ff2be SL |
111 | } |
112 | ||
113 | #[inline] | |
114 | fn write_usize(&mut self, i: usize) { | |
abe05a73 XL |
115 | // Always treat usize as u64 so we get the same results on 32 and 64 bit |
116 | // platforms. This is important for symbol hashes when cross compiling, | |
117 | // for example. | |
5099ac24 | 118 | self.state.short_write((i as u64).to_le_bytes()); |
476ff2be SL |
119 | } |
120 | ||
121 | #[inline] | |
122 | fn write_i8(&mut self, i: i8) { | |
123 | self.state.write_i8(i); | |
476ff2be SL |
124 | } |
125 | ||
126 | #[inline] | |
127 | fn write_i16(&mut self, i: i16) { | |
5099ac24 | 128 | self.state.short_write((i as u16).to_le_bytes()); |
476ff2be SL |
129 | } |
130 | ||
131 | #[inline] | |
132 | fn write_i32(&mut self, i: i32) { | |
5099ac24 | 133 | self.state.short_write((i as u32).to_le_bytes()); |
476ff2be SL |
134 | } |
135 | ||
136 | #[inline] | |
137 | fn write_i64(&mut self, i: i64) { | |
5099ac24 | 138 | self.state.short_write((i as u64).to_le_bytes()); |
abe05a73 XL |
139 | } |
140 | ||
141 | #[inline] | |
142 | fn write_i128(&mut self, i: i128) { | |
5099ac24 | 143 | self.state.write(&(i as u128).to_le_bytes()); |
476ff2be SL |
144 | } |
145 | ||
146 | #[inline] | |
147 | fn write_isize(&mut self, i: isize) { | |
5099ac24 | 148 | // Always treat isize as a 64-bit number so we get the same results on 32 and 64 bit |
abe05a73 | 149 | // platforms. This is important for symbol hashes when cross compiling, |
1b1a35ee XL |
150 | // for example. Sign extending here is preferable as it means that the |
151 | // same negative number hashes the same on both 32 and 64 bit platforms. | |
5099ac24 FG |
152 | let value = i as u64; |
153 | ||
154 | // Cold path | |
155 | #[cold] | |
156 | #[inline(never)] | |
157 | fn hash_value(state: &mut SipHasher128, value: u64) { | |
158 | state.write_u8(0xFF); | |
159 | state.short_write(value.to_le_bytes()); | |
160 | } | |
161 | ||
162 | // `isize` values often seem to have a small (positive) numeric value in practice. | |
163 | // To exploit this, if the value is small, we will hash a smaller amount of bytes. | |
164 | // However, we cannot just skip the leading zero bytes, as that would produce the same hash | |
165 | // e.g. if you hash two values that have the same bit pattern when they are swapped. | |
166 | // See https://github.com/rust-lang/rust/pull/93014 for context. | |
167 | // | |
168 | // Therefore, we employ the following strategy: | |
169 | // 1) When we encounter a value that fits within a single byte (the most common case), we | |
170 | // hash just that byte. This is the most common case that is being optimized. However, we do | |
171 | // not do this for the value 0xFF, as that is a reserved prefix (a bit like in UTF-8). | |
172 | // 2) When we encounter a larger value, we hash a "marker" 0xFF and then the corresponding | |
173 | // 8 bytes. Since this prefix cannot occur when we hash a single byte, when we hash two | |
174 | // `isize`s that fit within a different amount of bytes, they should always produce a different | |
175 | // byte stream for the hasher. | |
176 | if value < 0xFF { | |
177 | self.state.write_u8(value as u8); | |
178 | } else { | |
179 | hash_value(&mut self.state, value); | |
180 | } | |
476ff2be SL |
181 | } |
182 | } | |
cc61c64b | 183 | |
cc61c64b | 184 | /// Something that implements `HashStable<CTX>` can be hashed in a way that is |
3b2f2976 | 185 | /// stable across multiple compilation sessions. |
48663c56 XL |
186 | /// |
187 | /// Note that `HashStable` imposes rather more strict requirements than usual | |
188 | /// hash functions: | |
189 | /// | |
190 | /// - Stable hashes are sometimes used as identifiers. Therefore they must | |
191 | /// conform to the corresponding `PartialEq` implementations: | |
192 | /// | |
193 | /// - `x == y` implies `hash_stable(x) == hash_stable(y)`, and | |
194 | /// - `x != y` implies `hash_stable(x) != hash_stable(y)`. | |
195 | /// | |
196 | /// That second condition is usually not required for hash functions | |
197 | /// (e.g. `Hash`). In practice this means that `hash_stable` must feed any | |
60c5eb7d | 198 | /// information into the hasher that a `PartialEq` comparison takes into |
48663c56 XL |
199 | /// account. See [#49300](https://github.com/rust-lang/rust/issues/49300) |
200 | /// for an example where violating this invariant has caused trouble in the | |
201 | /// past. | |
202 | /// | |
203 | /// - `hash_stable()` must be independent of the current | |
204 | /// compilation session. E.g. they must not hash memory addresses or other | |
205 | /// things that are "randomly" assigned per compilation session. | |
206 | /// | |
207 | /// - `hash_stable()` must be independent of the host architecture. The | |
208 | /// `StableHasher` takes care of endianness and `isize`/`usize` platform | |
209 | /// differences. | |
cc61c64b | 210 | pub trait HashStable<CTX> { |
e74abb32 | 211 | fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher); |
cc61c64b XL |
212 | } |
213 | ||
ea8adc8c XL |
214 | /// Implement this for types that can be turned into stable keys like, for |
215 | /// example, for DefId that can be converted to a DefPathHash. This is used for | |
216 | /// bringing maps into a predictable order before hashing them. | |
217 | pub trait ToStableHashKey<HCX> { | |
e74abb32 | 218 | type KeyType: Ord + Sized + HashStable<HCX>; |
ea8adc8c XL |
219 | fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType; |
220 | } | |
221 | ||
487cf647 FG |
222 | /// Trait for marking a type as having a sort order that is |
223 | /// stable across compilation session boundaries. More formally: | |
224 | /// | |
225 | /// ```txt | |
226 | /// Ord::cmp(a1, b1) == Ord:cmp(a2, b2) | |
227 | /// where a2 = decode(encode(a1, context1), context2) | |
228 | /// b2 = decode(encode(b1, context1), context2) | |
229 | /// ``` | |
230 | /// | |
231 | /// i.e. the result of `Ord::cmp` is not influenced by encoding | |
232 | /// the values in one session and then decoding them in another | |
233 | /// session. | |
234 | /// | |
235 | /// This is trivially true for types where encoding and decoding | |
236 | /// don't change the bytes of the values that are used during | |
237 | /// comparison and comparison only depends on these bytes (as | |
238 | /// opposed to some non-local state). Examples are u32, String, | |
239 | /// Path, etc. | |
240 | /// | |
241 | /// But it is not true for: | |
242 | /// - `*const T` and `*mut T` because the values of these pointers | |
243 | /// will change between sessions. | |
244 | /// - `DefIndex`, `CrateNum`, `LocalDefId`, because their concrete | |
245 | /// values depend on state that might be different between | |
246 | /// compilation sessions. | |
247 | pub unsafe trait StableOrd: Ord {} | |
248 | ||
249 | /// Implement HashStable by just calling `Hash::hash()`. Also implement `StableOrd` for the type since | |
250 | /// that has the same requirements. | |
04454e1e FG |
251 | /// |
252 | /// **WARNING** This is only valid for types that *really* don't need any context for fingerprinting. | |
253 | /// But it is easy to misuse this macro (see [#96013](https://github.com/rust-lang/rust/issues/96013) | |
254 | /// for examples). Therefore this macro is not exported and should only be used in the limited cases | |
255 | /// here in this module. | |
256 | /// | |
257 | /// Use `#[derive(HashStable_Generic)]` instead. | |
487cf647 | 258 | macro_rules! impl_stable_traits_for_trivial_type { |
dfeec247 | 259 | ($t:ty) => { |
b7449926 | 260 | impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t { |
cc61c64b | 261 | #[inline] |
dfeec247 | 262 | fn hash_stable(&self, _: &mut CTX, hasher: &mut $crate::stable_hasher::StableHasher) { |
cc61c64b XL |
263 | ::std::hash::Hash::hash(self, hasher); |
264 | } | |
265 | } | |
487cf647 FG |
266 | |
267 | unsafe impl $crate::stable_hasher::StableOrd for $t {} | |
dfeec247 | 268 | }; |
cc61c64b XL |
269 | } |
270 | ||
487cf647 FG |
271 | impl_stable_traits_for_trivial_type!(i8); |
272 | impl_stable_traits_for_trivial_type!(i16); | |
273 | impl_stable_traits_for_trivial_type!(i32); | |
274 | impl_stable_traits_for_trivial_type!(i64); | |
275 | impl_stable_traits_for_trivial_type!(isize); | |
cc61c64b | 276 | |
487cf647 FG |
277 | impl_stable_traits_for_trivial_type!(u8); |
278 | impl_stable_traits_for_trivial_type!(u16); | |
279 | impl_stable_traits_for_trivial_type!(u32); | |
280 | impl_stable_traits_for_trivial_type!(u64); | |
281 | impl_stable_traits_for_trivial_type!(usize); | |
cc61c64b | 282 | |
487cf647 FG |
283 | impl_stable_traits_for_trivial_type!(u128); |
284 | impl_stable_traits_for_trivial_type!(i128); | |
cc61c64b | 285 | |
487cf647 FG |
286 | impl_stable_traits_for_trivial_type!(char); |
287 | impl_stable_traits_for_trivial_type!(()); | |
cc61c64b | 288 | |
c295e0f8 XL |
289 | impl<CTX> HashStable<CTX> for ! { |
290 | fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) { | |
291 | unreachable!() | |
292 | } | |
293 | } | |
294 | ||
064997fb FG |
295 | impl<CTX, T> HashStable<CTX> for PhantomData<T> { |
296 | fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) {} | |
297 | } | |
298 | ||
b7449926 | 299 | impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 { |
04454e1e | 300 | #[inline] |
e74abb32 | 301 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
b7449926 XL |
302 | self.get().hash_stable(ctx, hasher) |
303 | } | |
304 | } | |
305 | ||
ba9703b0 | 306 | impl<CTX> HashStable<CTX> for ::std::num::NonZeroUsize { |
04454e1e | 307 | #[inline] |
ba9703b0 XL |
308 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
309 | self.get().hash_stable(ctx, hasher) | |
310 | } | |
311 | } | |
312 | ||
cc61c64b | 313 | impl<CTX> HashStable<CTX> for f32 { |
e74abb32 | 314 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
3c0e092e | 315 | let val: u32 = unsafe { ::std::mem::transmute(*self) }; |
cc61c64b XL |
316 | val.hash_stable(ctx, hasher); |
317 | } | |
318 | } | |
319 | ||
320 | impl<CTX> HashStable<CTX> for f64 { | |
e74abb32 | 321 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
3c0e092e | 322 | let val: u64 = unsafe { ::std::mem::transmute(*self) }; |
cc61c64b XL |
323 | val.hash_stable(ctx, hasher); |
324 | } | |
325 | } | |
326 | ||
0531ce1d | 327 | impl<CTX> HashStable<CTX> for ::std::cmp::Ordering { |
04454e1e | 328 | #[inline] |
e74abb32 | 329 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
0531ce1d XL |
330 | (*self as i8).hash_stable(ctx, hasher); |
331 | } | |
332 | } | |
333 | ||
041b39d2 | 334 | impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) { |
04454e1e | 335 | #[inline] |
e74abb32 | 336 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
ea8adc8c XL |
337 | let (ref _0,) = *self; |
338 | _0.hash_stable(ctx, hasher); | |
041b39d2 XL |
339 | } |
340 | } | |
341 | ||
cc61c64b | 342 | impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) { |
e74abb32 | 343 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
ea8adc8c XL |
344 | let (ref _0, ref _1) = *self; |
345 | _0.hash_stable(ctx, hasher); | |
346 | _1.hash_stable(ctx, hasher); | |
347 | } | |
348 | } | |
349 | ||
350 | impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3) | |
dfeec247 XL |
351 | where |
352 | T1: HashStable<CTX>, | |
353 | T2: HashStable<CTX>, | |
354 | T3: HashStable<CTX>, | |
ea8adc8c | 355 | { |
e74abb32 | 356 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
ea8adc8c XL |
357 | let (ref _0, ref _1, ref _2) = *self; |
358 | _0.hash_stable(ctx, hasher); | |
359 | _1.hash_stable(ctx, hasher); | |
360 | _2.hash_stable(ctx, hasher); | |
cc61c64b XL |
361 | } |
362 | } | |
363 | ||
b7449926 | 364 | impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4) |
dfeec247 XL |
365 | where |
366 | T1: HashStable<CTX>, | |
367 | T2: HashStable<CTX>, | |
368 | T3: HashStable<CTX>, | |
369 | T4: HashStable<CTX>, | |
b7449926 | 370 | { |
e74abb32 | 371 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
b7449926 XL |
372 | let (ref _0, ref _1, ref _2, ref _3) = *self; |
373 | _0.hash_stable(ctx, hasher); | |
374 | _1.hash_stable(ctx, hasher); | |
375 | _2.hash_stable(ctx, hasher); | |
376 | _3.hash_stable(ctx, hasher); | |
377 | } | |
378 | } | |
379 | ||
cc61c64b | 380 | impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] { |
e74abb32 | 381 | default fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b XL |
382 | self.len().hash_stable(ctx, hasher); |
383 | for item in self { | |
384 | item.hash_stable(ctx, hasher); | |
385 | } | |
386 | } | |
387 | } | |
388 | ||
3c0e092e XL |
389 | impl<CTX> HashStable<CTX> for [u8] { |
390 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
391 | self.len().hash_stable(ctx, hasher); | |
392 | hasher.write(self); | |
393 | } | |
394 | } | |
395 | ||
cc61c64b XL |
396 | impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> { |
397 | #[inline] | |
e74abb32 | 398 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
487cf647 | 399 | self[..].hash_stable(ctx, hasher); |
cc61c64b XL |
400 | } |
401 | } | |
402 | ||
dc9dc135 | 403 | impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R> |
dfeec247 XL |
404 | where |
405 | K: HashStable<CTX> + Eq + Hash, | |
406 | V: HashStable<CTX>, | |
407 | R: BuildHasher, | |
dc9dc135 XL |
408 | { |
409 | #[inline] | |
e74abb32 | 410 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
dc9dc135 XL |
411 | self.len().hash_stable(ctx, hasher); |
412 | for kv in self { | |
413 | kv.hash_stable(ctx, hasher); | |
414 | } | |
415 | } | |
416 | } | |
417 | ||
418 | impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R> | |
dfeec247 XL |
419 | where |
420 | K: HashStable<CTX> + Eq + Hash, | |
421 | R: BuildHasher, | |
dc9dc135 XL |
422 | { |
423 | #[inline] | |
e74abb32 | 424 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
dc9dc135 XL |
425 | self.len().hash_stable(ctx, hasher); |
426 | for key in self { | |
427 | key.hash_stable(ctx, hasher); | |
428 | } | |
429 | } | |
430 | } | |
431 | ||
487cf647 | 432 | impl<A, const N: usize, CTX> HashStable<CTX> for SmallVec<[A; N]> |
dfeec247 XL |
433 | where |
434 | A: HashStable<CTX>, | |
435 | { | |
48663c56 | 436 | #[inline] |
e74abb32 | 437 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
487cf647 | 438 | self[..].hash_stable(ctx, hasher); |
48663c56 XL |
439 | } |
440 | } | |
441 | ||
ea8adc8c | 442 | impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> { |
041b39d2 | 443 | #[inline] |
e74abb32 | 444 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
041b39d2 XL |
445 | (**self).hash_stable(ctx, hasher); |
446 | } | |
447 | } | |
448 | ||
ea8adc8c XL |
449 | impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> { |
450 | #[inline] | |
e74abb32 | 451 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
ea8adc8c XL |
452 | (**self).hash_stable(ctx, hasher); |
453 | } | |
454 | } | |
455 | ||
456 | impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> { | |
041b39d2 | 457 | #[inline] |
e74abb32 | 458 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
041b39d2 XL |
459 | (**self).hash_stable(ctx, hasher); |
460 | } | |
461 | } | |
462 | ||
cc61c64b XL |
463 | impl<CTX> HashStable<CTX> for str { |
464 | #[inline] | |
a2a8927a XL |
465 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
466 | self.as_bytes().hash_stable(ctx, hasher); | |
cc61c64b XL |
467 | } |
468 | } | |
469 | ||
7cac9316 XL |
470 | impl<CTX> HashStable<CTX> for String { |
471 | #[inline] | |
e74abb32 | 472 | fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { |
487cf647 | 473 | self[..].hash_stable(hcx, hasher); |
7cac9316 XL |
474 | } |
475 | } | |
476 | ||
487cf647 FG |
477 | // Safety: String comparison only depends on their contents and the |
478 | // contents are not changed by (de-)serialization. | |
479 | unsafe impl StableOrd for String {} | |
480 | ||
ea8adc8c XL |
481 | impl<HCX> ToStableHashKey<HCX> for String { |
482 | type KeyType = String; | |
483 | #[inline] | |
484 | fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType { | |
485 | self.clone() | |
486 | } | |
487 | } | |
488 | ||
cc61c64b XL |
489 | impl<CTX> HashStable<CTX> for bool { |
490 | #[inline] | |
e74abb32 | 491 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b XL |
492 | (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher); |
493 | } | |
494 | } | |
495 | ||
487cf647 FG |
496 | // Safety: sort order of bools is not changed by (de-)serialization. |
497 | unsafe impl StableOrd for bool {} | |
498 | ||
cc61c64b | 499 | impl<T, CTX> HashStable<CTX> for Option<T> |
dfeec247 XL |
500 | where |
501 | T: HashStable<CTX>, | |
cc61c64b XL |
502 | { |
503 | #[inline] | |
e74abb32 | 504 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b XL |
505 | if let Some(ref value) = *self { |
506 | 1u8.hash_stable(ctx, hasher); | |
507 | value.hash_stable(ctx, hasher); | |
508 | } else { | |
509 | 0u8.hash_stable(ctx, hasher); | |
510 | } | |
511 | } | |
512 | } | |
513 | ||
487cf647 FG |
514 | // Safety: the Option wrapper does not add instability to comparison. |
515 | unsafe impl<T: StableOrd> StableOrd for Option<T> {} | |
516 | ||
ea8adc8c | 517 | impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2> |
dfeec247 XL |
518 | where |
519 | T1: HashStable<CTX>, | |
520 | T2: HashStable<CTX>, | |
ea8adc8c XL |
521 | { |
522 | #[inline] | |
e74abb32 | 523 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
ea8adc8c XL |
524 | mem::discriminant(self).hash_stable(ctx, hasher); |
525 | match *self { | |
526 | Ok(ref x) => x.hash_stable(ctx, hasher), | |
527 | Err(ref x) => x.hash_stable(ctx, hasher), | |
528 | } | |
529 | } | |
530 | } | |
531 | ||
cc61c64b | 532 | impl<'a, T, CTX> HashStable<CTX> for &'a T |
dfeec247 XL |
533 | where |
534 | T: HashStable<CTX> + ?Sized, | |
cc61c64b XL |
535 | { |
536 | #[inline] | |
e74abb32 | 537 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b XL |
538 | (**self).hash_stable(ctx, hasher); |
539 | } | |
540 | } | |
541 | ||
542 | impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> { | |
543 | #[inline] | |
e74abb32 | 544 | fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b XL |
545 | ::std::hash::Hash::hash(self, hasher); |
546 | } | |
547 | } | |
548 | ||
60c5eb7d | 549 | impl<T, CTX> HashStable<CTX> for ::std::ops::RangeInclusive<T> |
dfeec247 XL |
550 | where |
551 | T: HashStable<CTX>, | |
60c5eb7d XL |
552 | { |
553 | #[inline] | |
554 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
555 | self.start().hash_stable(ctx, hasher); | |
556 | self.end().hash_stable(ctx, hasher); | |
557 | } | |
558 | } | |
559 | ||
e74abb32 | 560 | impl<I: vec::Idx, T, CTX> HashStable<CTX> for vec::IndexVec<I, T> |
dfeec247 XL |
561 | where |
562 | T: HashStable<CTX>, | |
cc61c64b | 563 | { |
e74abb32 | 564 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b | 565 | self.len().hash_stable(ctx, hasher); |
ea8adc8c | 566 | for v in &self.raw { |
cc61c64b XL |
567 | v.hash_stable(ctx, hasher); |
568 | } | |
569 | } | |
570 | } | |
571 | ||
dfeec247 | 572 | impl<I: vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I> { |
a2a8927a XL |
573 | fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) { |
574 | ::std::hash::Hash::hash(self, hasher); | |
cc61c64b XL |
575 | } |
576 | } | |
577 | ||
dfeec247 | 578 | impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C> { |
a2a8927a XL |
579 | fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) { |
580 | ::std::hash::Hash::hash(self, hasher); | |
dc9dc135 XL |
581 | } |
582 | } | |
583 | ||
3dfed10e XL |
584 | impl<T, CTX> HashStable<CTX> for bit_set::FiniteBitSet<T> |
585 | where | |
586 | T: HashStable<CTX> + bit_set::FiniteBitSetTy, | |
587 | { | |
588 | fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { | |
589 | self.0.hash_stable(hcx, hasher); | |
590 | } | |
591 | } | |
592 | ||
487cf647 FG |
593 | impl_stable_traits_for_trivial_type!(::std::path::Path); |
594 | impl_stable_traits_for_trivial_type!(::std::path::PathBuf); | |
ea8adc8c XL |
595 | |
596 | impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R> | |
dfeec247 XL |
597 | where |
598 | K: ToStableHashKey<HCX> + Eq, | |
599 | V: HashStable<HCX>, | |
600 | R: BuildHasher, | |
cc61c64b | 601 | { |
ea8adc8c | 602 | #[inline] |
e74abb32 | 603 | fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { |
a2a8927a XL |
604 | stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, (key, value)| { |
605 | let key = key.to_stable_hash_key(hcx); | |
606 | key.hash_stable(hcx, hasher); | |
607 | value.hash_stable(hcx, hasher); | |
608 | }); | |
ea8adc8c XL |
609 | } |
610 | } | |
611 | ||
612 | impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R> | |
dfeec247 XL |
613 | where |
614 | K: ToStableHashKey<HCX> + Eq, | |
615 | R: BuildHasher, | |
ea8adc8c | 616 | { |
e74abb32 | 617 | fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { |
a2a8927a XL |
618 | stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| { |
619 | let key = key.to_stable_hash_key(hcx); | |
620 | key.hash_stable(hcx, hasher); | |
621 | }); | |
ea8adc8c XL |
622 | } |
623 | } | |
624 | ||
625 | impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V> | |
dfeec247 | 626 | where |
487cf647 | 627 | K: HashStable<HCX> + StableOrd, |
dfeec247 | 628 | V: HashStable<HCX>, |
ea8adc8c | 629 | { |
e74abb32 | 630 | fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { |
487cf647 FG |
631 | self.len().hash_stable(hcx, hasher); |
632 | for entry in self.iter() { | |
633 | entry.hash_stable(hcx, hasher); | |
634 | } | |
ea8adc8c XL |
635 | } |
636 | } | |
637 | ||
638 | impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K> | |
dfeec247 | 639 | where |
487cf647 | 640 | K: HashStable<HCX> + StableOrd, |
ea8adc8c | 641 | { |
e74abb32 | 642 | fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { |
487cf647 FG |
643 | self.len().hash_stable(hcx, hasher); |
644 | for entry in self.iter() { | |
645 | entry.hash_stable(hcx, hasher); | |
646 | } | |
ea8adc8c XL |
647 | } |
648 | } | |
649 | ||
a2a8927a | 650 | fn stable_hash_reduce<HCX, I, C, F>( |
ea8adc8c | 651 | hcx: &mut HCX, |
e74abb32 | 652 | hasher: &mut StableHasher, |
a2a8927a XL |
653 | mut collection: C, |
654 | length: usize, | |
655 | hash_function: F, | |
dfeec247 | 656 | ) where |
a2a8927a XL |
657 | C: Iterator<Item = I>, |
658 | F: Fn(&mut StableHasher, &mut HCX, I), | |
ea8adc8c | 659 | { |
a2a8927a XL |
660 | length.hash_stable(hcx, hasher); |
661 | ||
662 | match length { | |
663 | 1 => { | |
664 | hash_function(hasher, hcx, collection.next().unwrap()); | |
665 | } | |
666 | _ => { | |
667 | let hash = collection | |
668 | .map(|value| { | |
669 | let mut hasher = StableHasher::new(); | |
670 | hash_function(&mut hasher, hcx, value); | |
671 | hasher.finish::<u128>() | |
672 | }) | |
673 | .reduce(|accum, value| accum.wrapping_add(value)); | |
674 | hash.hash_stable(hcx, hasher); | |
675 | } | |
676 | } | |
ea8adc8c | 677 | } |
5099ac24 | 678 | |
923072b8 | 679 | /// Controls what data we do or do not hash. |
5099ac24 FG |
680 | /// Whenever a `HashStable` implementation caches its |
681 | /// result, it needs to include `HashingControls` as part | |
923072b8 | 682 | /// of the key, to ensure that it does not produce an incorrect |
5099ac24 | 683 | /// result (for example, using a `Fingerprint` produced while |
5e7ed085 | 684 | /// hashing `Span`s when a `Fingerprint` without `Span`s is |
5099ac24 FG |
685 | /// being requested) |
686 | #[derive(Clone, Hash, Eq, PartialEq, Debug)] | |
687 | pub struct HashingControls { | |
688 | pub hash_spans: bool, | |
5099ac24 | 689 | } |