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