]>
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}; | |
6 | use std::mem; | |
476ff2be | 7 | |
1b1a35ee XL |
8 | #[cfg(test)] |
9 | mod tests; | |
10 | ||
abe05a73 XL |
11 | /// When hashing something that ends up affecting properties like symbol names, |
12 | /// we want these symbol names to be calculated independently of other factors | |
13 | /// like what architecture you're compiling *from*. | |
476ff2be | 14 | /// |
abe05a73 XL |
15 | /// To that end we always convert integers to little-endian format before |
16 | /// hashing and the architecture dependent `isize` and `usize` types are | |
17 | /// extended to 64 bits if needed. | |
e74abb32 | 18 | pub struct StableHasher { |
abe05a73 | 19 | state: SipHasher128, |
476ff2be SL |
20 | } |
21 | ||
e74abb32 | 22 | impl ::std::fmt::Debug for StableHasher { |
29967ef6 | 23 | fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { |
cc61c64b XL |
24 | write!(f, "{:?}", self.state) |
25 | } | |
26 | } | |
27 | ||
476ff2be | 28 | pub trait StableHasherResult: Sized { |
e74abb32 | 29 | fn finish(hasher: StableHasher) -> Self; |
476ff2be SL |
30 | } |
31 | ||
e74abb32 | 32 | impl StableHasher { |
74b04a01 | 33 | #[inline] |
476ff2be | 34 | pub fn new() -> Self { |
dfeec247 | 35 | StableHasher { state: SipHasher128::new_with_keys(0, 0) } |
476ff2be SL |
36 | } |
37 | ||
6a06907d | 38 | #[inline] |
e74abb32 | 39 | pub fn finish<W: StableHasherResult>(self) -> W { |
476ff2be SL |
40 | W::finish(self) |
41 | } | |
42 | } | |
43 | ||
041b39d2 | 44 | impl StableHasherResult for u128 { |
a2a8927a | 45 | #[inline] |
e74abb32 | 46 | fn finish(hasher: StableHasher) -> Self { |
abe05a73 | 47 | let (_0, _1) = hasher.finalize(); |
dc9dc135 | 48 | u128::from(_0) | (u128::from(_1) << 64) |
041b39d2 XL |
49 | } |
50 | } | |
51 | ||
476ff2be | 52 | impl StableHasherResult for u64 { |
a2a8927a | 53 | #[inline] |
e74abb32 | 54 | fn finish(hasher: StableHasher) -> Self { |
abe05a73 | 55 | hasher.finalize().0 |
476ff2be SL |
56 | } |
57 | } | |
58 | ||
e74abb32 | 59 | impl StableHasher { |
476ff2be | 60 | #[inline] |
abe05a73 XL |
61 | pub fn finalize(self) -> (u64, u64) { |
62 | self.state.finish128() | |
476ff2be | 63 | } |
476ff2be SL |
64 | } |
65 | ||
e74abb32 | 66 | impl Hasher for StableHasher { |
476ff2be | 67 | fn finish(&self) -> u64 { |
abe05a73 | 68 | panic!("use StableHasher::finalize instead"); |
476ff2be SL |
69 | } |
70 | ||
71 | #[inline] | |
72 | fn write(&mut self, bytes: &[u8]) { | |
73 | self.state.write(bytes); | |
476ff2be SL |
74 | } |
75 | ||
76 | #[inline] | |
77 | fn write_u8(&mut self, i: u8) { | |
78 | self.state.write_u8(i); | |
476ff2be SL |
79 | } |
80 | ||
81 | #[inline] | |
82 | fn write_u16(&mut self, i: u16) { | |
abe05a73 | 83 | self.state.write_u16(i.to_le()); |
476ff2be SL |
84 | } |
85 | ||
86 | #[inline] | |
87 | fn write_u32(&mut self, i: u32) { | |
abe05a73 | 88 | self.state.write_u32(i.to_le()); |
476ff2be SL |
89 | } |
90 | ||
91 | #[inline] | |
92 | fn write_u64(&mut self, i: u64) { | |
abe05a73 | 93 | self.state.write_u64(i.to_le()); |
abe05a73 XL |
94 | } |
95 | ||
96 | #[inline] | |
97 | fn write_u128(&mut self, i: u128) { | |
98 | self.state.write_u128(i.to_le()); | |
476ff2be SL |
99 | } |
100 | ||
101 | #[inline] | |
102 | fn write_usize(&mut self, i: usize) { | |
abe05a73 XL |
103 | // Always treat usize as u64 so we get the same results on 32 and 64 bit |
104 | // platforms. This is important for symbol hashes when cross compiling, | |
105 | // for example. | |
106 | self.state.write_u64((i as u64).to_le()); | |
476ff2be SL |
107 | } |
108 | ||
109 | #[inline] | |
110 | fn write_i8(&mut self, i: i8) { | |
111 | self.state.write_i8(i); | |
476ff2be SL |
112 | } |
113 | ||
114 | #[inline] | |
115 | fn write_i16(&mut self, i: i16) { | |
abe05a73 | 116 | self.state.write_i16(i.to_le()); |
476ff2be SL |
117 | } |
118 | ||
119 | #[inline] | |
120 | fn write_i32(&mut self, i: i32) { | |
abe05a73 | 121 | self.state.write_i32(i.to_le()); |
476ff2be SL |
122 | } |
123 | ||
124 | #[inline] | |
125 | fn write_i64(&mut self, i: i64) { | |
abe05a73 | 126 | self.state.write_i64(i.to_le()); |
abe05a73 XL |
127 | } |
128 | ||
129 | #[inline] | |
130 | fn write_i128(&mut self, i: i128) { | |
131 | self.state.write_i128(i.to_le()); | |
476ff2be SL |
132 | } |
133 | ||
134 | #[inline] | |
135 | fn write_isize(&mut self, i: isize) { | |
abe05a73 XL |
136 | // Always treat isize as i64 so we get the same results on 32 and 64 bit |
137 | // platforms. This is important for symbol hashes when cross compiling, | |
1b1a35ee XL |
138 | // for example. Sign extending here is preferable as it means that the |
139 | // same negative number hashes the same on both 32 and 64 bit platforms. | |
abe05a73 | 140 | self.state.write_i64((i as i64).to_le()); |
476ff2be SL |
141 | } |
142 | } | |
cc61c64b | 143 | |
cc61c64b | 144 | /// Something that implements `HashStable<CTX>` can be hashed in a way that is |
3b2f2976 | 145 | /// stable across multiple compilation sessions. |
48663c56 XL |
146 | /// |
147 | /// Note that `HashStable` imposes rather more strict requirements than usual | |
148 | /// hash functions: | |
149 | /// | |
150 | /// - Stable hashes are sometimes used as identifiers. Therefore they must | |
151 | /// conform to the corresponding `PartialEq` implementations: | |
152 | /// | |
153 | /// - `x == y` implies `hash_stable(x) == hash_stable(y)`, and | |
154 | /// - `x != y` implies `hash_stable(x) != hash_stable(y)`. | |
155 | /// | |
156 | /// That second condition is usually not required for hash functions | |
157 | /// (e.g. `Hash`). In practice this means that `hash_stable` must feed any | |
60c5eb7d | 158 | /// information into the hasher that a `PartialEq` comparison takes into |
48663c56 XL |
159 | /// account. See [#49300](https://github.com/rust-lang/rust/issues/49300) |
160 | /// for an example where violating this invariant has caused trouble in the | |
161 | /// past. | |
162 | /// | |
163 | /// - `hash_stable()` must be independent of the current | |
164 | /// compilation session. E.g. they must not hash memory addresses or other | |
165 | /// things that are "randomly" assigned per compilation session. | |
166 | /// | |
167 | /// - `hash_stable()` must be independent of the host architecture. The | |
168 | /// `StableHasher` takes care of endianness and `isize`/`usize` platform | |
169 | /// differences. | |
cc61c64b | 170 | pub trait HashStable<CTX> { |
e74abb32 | 171 | fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher); |
cc61c64b XL |
172 | } |
173 | ||
ea8adc8c XL |
174 | /// Implement this for types that can be turned into stable keys like, for |
175 | /// example, for DefId that can be converted to a DefPathHash. This is used for | |
176 | /// bringing maps into a predictable order before hashing them. | |
177 | pub trait ToStableHashKey<HCX> { | |
e74abb32 | 178 | type KeyType: Ord + Sized + HashStable<HCX>; |
ea8adc8c XL |
179 | fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType; |
180 | } | |
181 | ||
cc61c64b XL |
182 | // Implement HashStable by just calling `Hash::hash()`. This works fine for |
183 | // self-contained values that don't depend on the hashing context `CTX`. | |
b7449926 | 184 | #[macro_export] |
cc61c64b | 185 | macro_rules! impl_stable_hash_via_hash { |
dfeec247 | 186 | ($t:ty) => { |
b7449926 | 187 | impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t { |
cc61c64b | 188 | #[inline] |
dfeec247 | 189 | fn hash_stable(&self, _: &mut CTX, hasher: &mut $crate::stable_hasher::StableHasher) { |
cc61c64b XL |
190 | ::std::hash::Hash::hash(self, hasher); |
191 | } | |
192 | } | |
dfeec247 | 193 | }; |
cc61c64b XL |
194 | } |
195 | ||
196 | impl_stable_hash_via_hash!(i8); | |
197 | impl_stable_hash_via_hash!(i16); | |
198 | impl_stable_hash_via_hash!(i32); | |
199 | impl_stable_hash_via_hash!(i64); | |
200 | impl_stable_hash_via_hash!(isize); | |
201 | ||
202 | impl_stable_hash_via_hash!(u8); | |
203 | impl_stable_hash_via_hash!(u16); | |
204 | impl_stable_hash_via_hash!(u32); | |
205 | impl_stable_hash_via_hash!(u64); | |
206 | impl_stable_hash_via_hash!(usize); | |
207 | ||
208 | impl_stable_hash_via_hash!(u128); | |
209 | impl_stable_hash_via_hash!(i128); | |
210 | ||
211 | impl_stable_hash_via_hash!(char); | |
212 | impl_stable_hash_via_hash!(()); | |
213 | ||
c295e0f8 XL |
214 | impl<CTX> HashStable<CTX> for ! { |
215 | fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) { | |
216 | unreachable!() | |
217 | } | |
218 | } | |
219 | ||
b7449926 | 220 | impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 { |
e74abb32 | 221 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
b7449926 XL |
222 | self.get().hash_stable(ctx, hasher) |
223 | } | |
224 | } | |
225 | ||
ba9703b0 XL |
226 | impl<CTX> HashStable<CTX> for ::std::num::NonZeroUsize { |
227 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
228 | self.get().hash_stable(ctx, hasher) | |
229 | } | |
230 | } | |
231 | ||
cc61c64b | 232 | impl<CTX> HashStable<CTX> for f32 { |
e74abb32 | 233 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
3c0e092e | 234 | let val: u32 = unsafe { ::std::mem::transmute(*self) }; |
cc61c64b XL |
235 | val.hash_stable(ctx, hasher); |
236 | } | |
237 | } | |
238 | ||
239 | impl<CTX> HashStable<CTX> for f64 { | |
e74abb32 | 240 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
3c0e092e | 241 | let val: u64 = unsafe { ::std::mem::transmute(*self) }; |
cc61c64b XL |
242 | val.hash_stable(ctx, hasher); |
243 | } | |
244 | } | |
245 | ||
0531ce1d | 246 | impl<CTX> HashStable<CTX> for ::std::cmp::Ordering { |
e74abb32 | 247 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
0531ce1d XL |
248 | (*self as i8).hash_stable(ctx, hasher); |
249 | } | |
250 | } | |
251 | ||
041b39d2 | 252 | impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) { |
e74abb32 | 253 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
ea8adc8c XL |
254 | let (ref _0,) = *self; |
255 | _0.hash_stable(ctx, hasher); | |
041b39d2 XL |
256 | } |
257 | } | |
258 | ||
cc61c64b | 259 | impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) { |
e74abb32 | 260 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
ea8adc8c XL |
261 | let (ref _0, ref _1) = *self; |
262 | _0.hash_stable(ctx, hasher); | |
263 | _1.hash_stable(ctx, hasher); | |
264 | } | |
265 | } | |
266 | ||
267 | impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3) | |
dfeec247 XL |
268 | where |
269 | T1: HashStable<CTX>, | |
270 | T2: HashStable<CTX>, | |
271 | T3: HashStable<CTX>, | |
ea8adc8c | 272 | { |
e74abb32 | 273 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
ea8adc8c XL |
274 | let (ref _0, ref _1, ref _2) = *self; |
275 | _0.hash_stable(ctx, hasher); | |
276 | _1.hash_stable(ctx, hasher); | |
277 | _2.hash_stable(ctx, hasher); | |
cc61c64b XL |
278 | } |
279 | } | |
280 | ||
b7449926 | 281 | impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4) |
dfeec247 XL |
282 | where |
283 | T1: HashStable<CTX>, | |
284 | T2: HashStable<CTX>, | |
285 | T3: HashStable<CTX>, | |
286 | T4: HashStable<CTX>, | |
b7449926 | 287 | { |
e74abb32 | 288 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
b7449926 XL |
289 | let (ref _0, ref _1, ref _2, ref _3) = *self; |
290 | _0.hash_stable(ctx, hasher); | |
291 | _1.hash_stable(ctx, hasher); | |
292 | _2.hash_stable(ctx, hasher); | |
293 | _3.hash_stable(ctx, hasher); | |
294 | } | |
295 | } | |
296 | ||
cc61c64b | 297 | impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] { |
e74abb32 | 298 | default fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b XL |
299 | self.len().hash_stable(ctx, hasher); |
300 | for item in self { | |
301 | item.hash_stable(ctx, hasher); | |
302 | } | |
303 | } | |
304 | } | |
305 | ||
3c0e092e XL |
306 | impl<CTX> HashStable<CTX> for [u8] { |
307 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
308 | self.len().hash_stable(ctx, hasher); | |
309 | hasher.write(self); | |
310 | } | |
311 | } | |
312 | ||
cc61c64b XL |
313 | impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> { |
314 | #[inline] | |
e74abb32 | 315 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b XL |
316 | (&self[..]).hash_stable(ctx, hasher); |
317 | } | |
318 | } | |
319 | ||
dc9dc135 | 320 | impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R> |
dfeec247 XL |
321 | where |
322 | K: HashStable<CTX> + Eq + Hash, | |
323 | V: HashStable<CTX>, | |
324 | R: BuildHasher, | |
dc9dc135 XL |
325 | { |
326 | #[inline] | |
e74abb32 | 327 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
dc9dc135 XL |
328 | self.len().hash_stable(ctx, hasher); |
329 | for kv in self { | |
330 | kv.hash_stable(ctx, hasher); | |
331 | } | |
332 | } | |
333 | } | |
334 | ||
335 | impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R> | |
dfeec247 XL |
336 | where |
337 | K: HashStable<CTX> + Eq + Hash, | |
338 | R: BuildHasher, | |
dc9dc135 XL |
339 | { |
340 | #[inline] | |
e74abb32 | 341 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
dc9dc135 XL |
342 | self.len().hash_stable(ctx, hasher); |
343 | for key in self { | |
344 | key.hash_stable(ctx, hasher); | |
345 | } | |
346 | } | |
347 | } | |
348 | ||
dfeec247 XL |
349 | impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]> |
350 | where | |
351 | A: HashStable<CTX>, | |
352 | { | |
48663c56 | 353 | #[inline] |
e74abb32 | 354 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
48663c56 XL |
355 | (&self[..]).hash_stable(ctx, hasher); |
356 | } | |
357 | } | |
358 | ||
ea8adc8c | 359 | impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> { |
041b39d2 | 360 | #[inline] |
e74abb32 | 361 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
041b39d2 XL |
362 | (**self).hash_stable(ctx, hasher); |
363 | } | |
364 | } | |
365 | ||
ea8adc8c XL |
366 | impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> { |
367 | #[inline] | |
e74abb32 | 368 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
ea8adc8c XL |
369 | (**self).hash_stable(ctx, hasher); |
370 | } | |
371 | } | |
372 | ||
373 | impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> { | |
041b39d2 | 374 | #[inline] |
e74abb32 | 375 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
041b39d2 XL |
376 | (**self).hash_stable(ctx, hasher); |
377 | } | |
378 | } | |
379 | ||
cc61c64b XL |
380 | impl<CTX> HashStable<CTX> for str { |
381 | #[inline] | |
a2a8927a XL |
382 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
383 | self.as_bytes().hash_stable(ctx, hasher); | |
cc61c64b XL |
384 | } |
385 | } | |
386 | ||
7cac9316 XL |
387 | impl<CTX> HashStable<CTX> for String { |
388 | #[inline] | |
e74abb32 | 389 | fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { |
7cac9316 XL |
390 | (&self[..]).hash_stable(hcx, hasher); |
391 | } | |
392 | } | |
393 | ||
ea8adc8c XL |
394 | impl<HCX> ToStableHashKey<HCX> for String { |
395 | type KeyType = String; | |
396 | #[inline] | |
397 | fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType { | |
398 | self.clone() | |
399 | } | |
400 | } | |
401 | ||
cc61c64b XL |
402 | impl<CTX> HashStable<CTX> for bool { |
403 | #[inline] | |
e74abb32 | 404 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b XL |
405 | (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher); |
406 | } | |
407 | } | |
408 | ||
cc61c64b | 409 | impl<T, CTX> HashStable<CTX> for Option<T> |
dfeec247 XL |
410 | where |
411 | T: HashStable<CTX>, | |
cc61c64b XL |
412 | { |
413 | #[inline] | |
e74abb32 | 414 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b XL |
415 | if let Some(ref value) = *self { |
416 | 1u8.hash_stable(ctx, hasher); | |
417 | value.hash_stable(ctx, hasher); | |
418 | } else { | |
419 | 0u8.hash_stable(ctx, hasher); | |
420 | } | |
421 | } | |
422 | } | |
423 | ||
ea8adc8c | 424 | impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2> |
dfeec247 XL |
425 | where |
426 | T1: HashStable<CTX>, | |
427 | T2: HashStable<CTX>, | |
ea8adc8c XL |
428 | { |
429 | #[inline] | |
e74abb32 | 430 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
ea8adc8c XL |
431 | mem::discriminant(self).hash_stable(ctx, hasher); |
432 | match *self { | |
433 | Ok(ref x) => x.hash_stable(ctx, hasher), | |
434 | Err(ref x) => x.hash_stable(ctx, hasher), | |
435 | } | |
436 | } | |
437 | } | |
438 | ||
cc61c64b | 439 | impl<'a, T, CTX> HashStable<CTX> for &'a T |
dfeec247 XL |
440 | where |
441 | T: HashStable<CTX> + ?Sized, | |
cc61c64b XL |
442 | { |
443 | #[inline] | |
e74abb32 | 444 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b XL |
445 | (**self).hash_stable(ctx, hasher); |
446 | } | |
447 | } | |
448 | ||
449 | impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> { | |
450 | #[inline] | |
e74abb32 | 451 | fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b XL |
452 | ::std::hash::Hash::hash(self, hasher); |
453 | } | |
454 | } | |
455 | ||
60c5eb7d | 456 | impl<T, CTX> HashStable<CTX> for ::std::ops::RangeInclusive<T> |
dfeec247 XL |
457 | where |
458 | T: HashStable<CTX>, | |
60c5eb7d XL |
459 | { |
460 | #[inline] | |
461 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { | |
462 | self.start().hash_stable(ctx, hasher); | |
463 | self.end().hash_stable(ctx, hasher); | |
464 | } | |
465 | } | |
466 | ||
e74abb32 | 467 | impl<I: vec::Idx, T, CTX> HashStable<CTX> for vec::IndexVec<I, T> |
dfeec247 XL |
468 | where |
469 | T: HashStable<CTX>, | |
cc61c64b | 470 | { |
e74abb32 | 471 | fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) { |
cc61c64b | 472 | self.len().hash_stable(ctx, hasher); |
ea8adc8c | 473 | for v in &self.raw { |
cc61c64b XL |
474 | v.hash_stable(ctx, hasher); |
475 | } | |
476 | } | |
477 | } | |
478 | ||
dfeec247 | 479 | impl<I: vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I> { |
a2a8927a XL |
480 | fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) { |
481 | ::std::hash::Hash::hash(self, hasher); | |
cc61c64b XL |
482 | } |
483 | } | |
484 | ||
dfeec247 | 485 | impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C> { |
a2a8927a XL |
486 | fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) { |
487 | ::std::hash::Hash::hash(self, hasher); | |
dc9dc135 XL |
488 | } |
489 | } | |
490 | ||
3dfed10e XL |
491 | impl<T, CTX> HashStable<CTX> for bit_set::FiniteBitSet<T> |
492 | where | |
493 | T: HashStable<CTX> + bit_set::FiniteBitSetTy, | |
494 | { | |
495 | fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { | |
496 | self.0.hash_stable(hcx, hasher); | |
497 | } | |
498 | } | |
499 | ||
ea8adc8c XL |
500 | impl_stable_hash_via_hash!(::std::path::Path); |
501 | impl_stable_hash_via_hash!(::std::path::PathBuf); | |
502 | ||
503 | impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R> | |
dfeec247 XL |
504 | where |
505 | K: ToStableHashKey<HCX> + Eq, | |
506 | V: HashStable<HCX>, | |
507 | R: BuildHasher, | |
cc61c64b | 508 | { |
ea8adc8c | 509 | #[inline] |
e74abb32 | 510 | fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { |
a2a8927a XL |
511 | stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, (key, value)| { |
512 | let key = key.to_stable_hash_key(hcx); | |
513 | key.hash_stable(hcx, hasher); | |
514 | value.hash_stable(hcx, hasher); | |
515 | }); | |
ea8adc8c XL |
516 | } |
517 | } | |
518 | ||
519 | impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R> | |
dfeec247 XL |
520 | where |
521 | K: ToStableHashKey<HCX> + Eq, | |
522 | R: BuildHasher, | |
ea8adc8c | 523 | { |
e74abb32 | 524 | fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { |
a2a8927a XL |
525 | stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| { |
526 | let key = key.to_stable_hash_key(hcx); | |
527 | key.hash_stable(hcx, hasher); | |
528 | }); | |
ea8adc8c XL |
529 | } |
530 | } | |
531 | ||
532 | impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V> | |
dfeec247 XL |
533 | where |
534 | K: ToStableHashKey<HCX>, | |
535 | V: HashStable<HCX>, | |
ea8adc8c | 536 | { |
e74abb32 | 537 | fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { |
a2a8927a XL |
538 | stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, (key, value)| { |
539 | let key = key.to_stable_hash_key(hcx); | |
540 | key.hash_stable(hcx, hasher); | |
541 | value.hash_stable(hcx, hasher); | |
542 | }); | |
ea8adc8c XL |
543 | } |
544 | } | |
545 | ||
546 | impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K> | |
dfeec247 XL |
547 | where |
548 | K: ToStableHashKey<HCX>, | |
ea8adc8c | 549 | { |
e74abb32 | 550 | fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) { |
a2a8927a XL |
551 | stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| { |
552 | let key = key.to_stable_hash_key(hcx); | |
553 | key.hash_stable(hcx, hasher); | |
554 | }); | |
ea8adc8c XL |
555 | } |
556 | } | |
557 | ||
a2a8927a | 558 | fn stable_hash_reduce<HCX, I, C, F>( |
ea8adc8c | 559 | hcx: &mut HCX, |
e74abb32 | 560 | hasher: &mut StableHasher, |
a2a8927a XL |
561 | mut collection: C, |
562 | length: usize, | |
563 | hash_function: F, | |
dfeec247 | 564 | ) where |
a2a8927a XL |
565 | C: Iterator<Item = I>, |
566 | F: Fn(&mut StableHasher, &mut HCX, I), | |
ea8adc8c | 567 | { |
a2a8927a XL |
568 | length.hash_stable(hcx, hasher); |
569 | ||
570 | match length { | |
571 | 1 => { | |
572 | hash_function(hasher, hcx, collection.next().unwrap()); | |
573 | } | |
574 | _ => { | |
575 | let hash = collection | |
576 | .map(|value| { | |
577 | let mut hasher = StableHasher::new(); | |
578 | hash_function(&mut hasher, hcx, value); | |
579 | hasher.finish::<u128>() | |
580 | }) | |
581 | .reduce(|accum, value| accum.wrapping_add(value)); | |
582 | hash.hash_stable(hcx, hasher); | |
583 | } | |
584 | } | |
ea8adc8c | 585 | } |