compiler/rustc_data_structures/src/stable_hasher.rs

   1 use crate::sip128::SipHasher128;
   2 use rustc_index::bit_set;
   3 use rustc_index::vec;
   4 use smallvec::SmallVec;
   5 use std::hash::{BuildHasher, Hash, Hasher};
   6 use std::marker::PhantomData;
   7 use std::mem;
   8
   9 #[cfg(test)]
  10 mod tests;
  11
  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*.
  15 ///
  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.
  19 pub struct StableHasher {
  20     state: SipHasher128,
  21 }
  22
  23 impl ::std::fmt::Debug for StableHasher {
  24     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
  25         write!(f, "{:?}", self.state)
  26     }
  27 }
  28
  29 pub trait StableHasherResult: Sized {
  30     fn finish(hasher: StableHasher) -> Self;
  31 }
  32
  33 impl StableHasher {
  34     #[inline]
  35     pub fn new() -> Self {
  36         StableHasher { state: SipHasher128::new_with_keys(0, 0) }
  37     }
  38
  39     #[inline]
  40     pub fn finish<W: StableHasherResult>(self) -> W {
  41         W::finish(self)
  42     }
  43 }
  44
  45 impl StableHasherResult for u128 {
  46     #[inline]
  47     fn finish(hasher: StableHasher) -> Self {
  48         let (_0, _1) = hasher.finalize();
  49         u128::from(_0) | (u128::from(_1) << 64)
  50     }
  51 }
  52
  53 impl StableHasherResult for u64 {
  54     #[inline]
  55     fn finish(hasher: StableHasher) -> Self {
  56         hasher.finalize().0
  57     }
  58 }
  59
  60 impl StableHasher {
  61     #[inline]
  62     pub fn finalize(self) -> (u64, u64) {
  63         self.state.finish128()
  64     }
  65 }
  66
  67 impl Hasher for StableHasher {
  68     fn finish(&self) -> u64 {
  69         panic!("use StableHasher::finalize instead");
  70     }
  71
  72     #[inline]
  73     fn write(&mut self, bytes: &[u8]) {
  74         self.state.write(bytes);
  75     }
  76
  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
  88     #[inline]
  89     fn write_u8(&mut self, i: u8) {
  90         self.state.write_u8(i);
  91     }
  92
  93     #[inline]
  94     fn write_u16(&mut self, i: u16) {
  95         self.state.short_write(i.to_le_bytes());
  96     }
  97
  98     #[inline]
  99     fn write_u32(&mut self, i: u32) {
 100         self.state.short_write(i.to_le_bytes());
 101     }
 102
 103     #[inline]
 104     fn write_u64(&mut self, i: u64) {
 105         self.state.short_write(i.to_le_bytes());
 106     }
 107
 108     #[inline]
 109     fn write_u128(&mut self, i: u128) {
 110         self.state.write(&i.to_le_bytes());
 111     }
 112
 113     #[inline]
 114     fn write_usize(&mut self, i: usize) {
 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.
 118         self.state.short_write((i as u64).to_le_bytes());
 119     }
 120
 121     #[inline]
 122     fn write_i8(&mut self, i: i8) {
 123         self.state.write_i8(i);
 124     }
 125
 126     #[inline]
 127     fn write_i16(&mut self, i: i16) {
 128         self.state.short_write((i as u16).to_le_bytes());
 129     }
 130
 131     #[inline]
 132     fn write_i32(&mut self, i: i32) {
 133         self.state.short_write((i as u32).to_le_bytes());
 134     }
 135
 136     #[inline]
 137     fn write_i64(&mut self, i: i64) {
 138         self.state.short_write((i as u64).to_le_bytes());
 139     }
 140
 141     #[inline]
 142     fn write_i128(&mut self, i: i128) {
 143         self.state.write(&(i as u128).to_le_bytes());
 144     }
 145
 146     #[inline]
 147     fn write_isize(&mut self, i: isize) {
 148         // Always treat isize as a 64-bit number so we get the same results on 32 and 64 bit
 149         // platforms. This is important for symbol hashes when cross compiling,
 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.
 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         }
 181     }
 182 }
 183
 184 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
 185 /// stable across multiple compilation sessions.
 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
 198 ///   information into the hasher that a `PartialEq` comparison takes into
 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.
 210 pub trait HashStable<CTX> {
 211     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher);
 212 }
 213
 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> {
 218     type KeyType: Ord + Sized + HashStable<HCX>;
 219     fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
 220 }
 221
 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.
 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.
 258 macro_rules! impl_stable_traits_for_trivial_type {
 259     ($t:ty) => {
 260         impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
 261             #[inline]
 262             fn hash_stable(&self, _: &mut CTX, hasher: &mut $crate::stable_hasher::StableHasher) {
 263                 ::std::hash::Hash::hash(self, hasher);
 264             }
 265         }
 266
 267         unsafe impl $crate::stable_hasher::StableOrd for $t {}
 268     };
 269 }
 270
 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);
 276
 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);
 282
 283 impl_stable_traits_for_trivial_type!(u128);
 284 impl_stable_traits_for_trivial_type!(i128);
 285
 286 impl_stable_traits_for_trivial_type!(char);
 287 impl_stable_traits_for_trivial_type!(());
 288
 289 impl<CTX> HashStable<CTX> for ! {
 290     fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) {
 291         unreachable!()
 292     }
 293 }
 294
 295 impl<CTX, T> HashStable<CTX> for PhantomData<T> {
 296     fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) {}
 297 }
 298
 299 impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
 300     #[inline]
 301     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 302         self.get().hash_stable(ctx, hasher)
 303     }
 304 }
 305
 306 impl<CTX> HashStable<CTX> for ::std::num::NonZeroUsize {
 307     #[inline]
 308     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 309         self.get().hash_stable(ctx, hasher)
 310     }
 311 }
 312
 313 impl<CTX> HashStable<CTX> for f32 {
 314     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 315         let val: u32 = unsafe { ::std::mem::transmute(*self) };
 316         val.hash_stable(ctx, hasher);
 317     }
 318 }
 319
 320 impl<CTX> HashStable<CTX> for f64 {
 321     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 322         let val: u64 = unsafe { ::std::mem::transmute(*self) };
 323         val.hash_stable(ctx, hasher);
 324     }
 325 }
 326
 327 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
 328     #[inline]
 329     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 330         (*self as i8).hash_stable(ctx, hasher);
 331     }
 332 }
 333
 334 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
 335     #[inline]
 336     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 337         let (ref _0,) = *self;
 338         _0.hash_stable(ctx, hasher);
 339     }
 340 }
 341
 342 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
 343     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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)
 351 where
 352     T1: HashStable<CTX>,
 353     T2: HashStable<CTX>,
 354     T3: HashStable<CTX>,
 355 {
 356     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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);
 361     }
 362 }
 363
 364 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
 365 where
 366     T1: HashStable<CTX>,
 367     T2: HashStable<CTX>,
 368     T3: HashStable<CTX>,
 369     T4: HashStable<CTX>,
 370 {
 371     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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
 380 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
 381     default fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 382         self.len().hash_stable(ctx, hasher);
 383         for item in self {
 384             item.hash_stable(ctx, hasher);
 385         }
 386     }
 387 }
 388
 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
 396 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
 397     #[inline]
 398     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 399         self[..].hash_stable(ctx, hasher);
 400     }
 401 }
 402
 403 impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
 404 where
 405     K: HashStable<CTX> + Eq + Hash,
 406     V: HashStable<CTX>,
 407     R: BuildHasher,
 408 {
 409     #[inline]
 410     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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>
 419 where
 420     K: HashStable<CTX> + Eq + Hash,
 421     R: BuildHasher,
 422 {
 423     #[inline]
 424     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 425         self.len().hash_stable(ctx, hasher);
 426         for key in self {
 427             key.hash_stable(ctx, hasher);
 428         }
 429     }
 430 }
 431
 432 impl<A, const N: usize, CTX> HashStable<CTX> for SmallVec<[A; N]>
 433 where
 434     A: HashStable<CTX>,
 435 {
 436     #[inline]
 437     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 438         self[..].hash_stable(ctx, hasher);
 439     }
 440 }
 441
 442 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
 443     #[inline]
 444     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 445         (**self).hash_stable(ctx, hasher);
 446     }
 447 }
 448
 449 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
 450     #[inline]
 451     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 452         (**self).hash_stable(ctx, hasher);
 453     }
 454 }
 455
 456 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
 457     #[inline]
 458     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 459         (**self).hash_stable(ctx, hasher);
 460     }
 461 }
 462
 463 impl<CTX> HashStable<CTX> for str {
 464     #[inline]
 465     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 466         self.as_bytes().hash_stable(ctx, hasher);
 467     }
 468 }
 469
 470 impl<CTX> HashStable<CTX> for String {
 471     #[inline]
 472     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 473         self[..].hash_stable(hcx, hasher);
 474     }
 475 }
 476
 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
 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
 489 impl<HCX, T1: ToStableHashKey<HCX>, T2: ToStableHashKey<HCX>> ToStableHashKey<HCX> for (T1, T2) {
 490     type KeyType = (T1::KeyType, T2::KeyType);
 491     #[inline]
 492     fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType {
 493         (self.0.to_stable_hash_key(hcx), self.1.to_stable_hash_key(hcx))
 494     }
 495 }
 496
 497 impl<CTX> HashStable<CTX> for bool {
 498     #[inline]
 499     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 500         (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
 501     }
 502 }
 503
 504 // Safety: sort order of bools is not changed by (de-)serialization.
 505 unsafe impl StableOrd for bool {}
 506
 507 impl<T, CTX> HashStable<CTX> for Option<T>
 508 where
 509     T: HashStable<CTX>,
 510 {
 511     #[inline]
 512     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 513         if let Some(ref value) = *self {
 514             1u8.hash_stable(ctx, hasher);
 515             value.hash_stable(ctx, hasher);
 516         } else {
 517             0u8.hash_stable(ctx, hasher);
 518         }
 519     }
 520 }
 521
 522 // Safety: the Option wrapper does not add instability to comparison.
 523 unsafe impl<T: StableOrd> StableOrd for Option<T> {}
 524
 525 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
 526 where
 527     T1: HashStable<CTX>,
 528     T2: HashStable<CTX>,
 529 {
 530     #[inline]
 531     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 532         mem::discriminant(self).hash_stable(ctx, hasher);
 533         match *self {
 534             Ok(ref x) => x.hash_stable(ctx, hasher),
 535             Err(ref x) => x.hash_stable(ctx, hasher),
 536         }
 537     }
 538 }
 539
 540 impl<'a, T, CTX> HashStable<CTX> for &'a T
 541 where
 542     T: HashStable<CTX> + ?Sized,
 543 {
 544     #[inline]
 545     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 546         (**self).hash_stable(ctx, hasher);
 547     }
 548 }
 549
 550 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
 551     #[inline]
 552     fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
 553         ::std::hash::Hash::hash(self, hasher);
 554     }
 555 }
 556
 557 impl<T, CTX> HashStable<CTX> for ::std::ops::RangeInclusive<T>
 558 where
 559     T: HashStable<CTX>,
 560 {
 561     #[inline]
 562     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 563         self.start().hash_stable(ctx, hasher);
 564         self.end().hash_stable(ctx, hasher);
 565     }
 566 }
 567
 568 impl<I: vec::Idx, T, CTX> HashStable<CTX> for vec::IndexVec<I, T>
 569 where
 570     T: HashStable<CTX>,
 571 {
 572     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 573         self.len().hash_stable(ctx, hasher);
 574         for v in &self.raw {
 575             v.hash_stable(ctx, hasher);
 576         }
 577     }
 578 }
 579
 580 impl<I: vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I> {
 581     fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) {
 582         ::std::hash::Hash::hash(self, hasher);
 583     }
 584 }
 585
 586 impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C> {
 587     fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) {
 588         ::std::hash::Hash::hash(self, hasher);
 589     }
 590 }
 591
 592 impl<T, CTX> HashStable<CTX> for bit_set::FiniteBitSet<T>
 593 where
 594     T: HashStable<CTX> + bit_set::FiniteBitSetTy,
 595 {
 596     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 597         self.0.hash_stable(hcx, hasher);
 598     }
 599 }
 600
 601 impl_stable_traits_for_trivial_type!(::std::path::Path);
 602 impl_stable_traits_for_trivial_type!(::std::path::PathBuf);
 603
 604 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
 605 where
 606     K: ToStableHashKey<HCX> + Eq,
 607     V: HashStable<HCX>,
 608     R: BuildHasher,
 609 {
 610     #[inline]
 611     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 612         stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, (key, value)| {
 613             let key = key.to_stable_hash_key(hcx);
 614             key.hash_stable(hcx, hasher);
 615             value.hash_stable(hcx, hasher);
 616         });
 617     }
 618 }
 619
 620 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
 621 where
 622     K: ToStableHashKey<HCX> + Eq,
 623     R: BuildHasher,
 624 {
 625     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 626         stable_hash_reduce(hcx, hasher, self.iter(), self.len(), |hasher, hcx, key| {
 627             let key = key.to_stable_hash_key(hcx);
 628             key.hash_stable(hcx, hasher);
 629         });
 630     }
 631 }
 632
 633 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
 634 where
 635     K: HashStable<HCX> + StableOrd,
 636     V: HashStable<HCX>,
 637 {
 638     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 639         self.len().hash_stable(hcx, hasher);
 640         for entry in self.iter() {
 641             entry.hash_stable(hcx, hasher);
 642         }
 643     }
 644 }
 645
 646 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
 647 where
 648     K: HashStable<HCX> + StableOrd,
 649 {
 650     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 651         self.len().hash_stable(hcx, hasher);
 652         for entry in self.iter() {
 653             entry.hash_stable(hcx, hasher);
 654         }
 655     }
 656 }
 657
 658 fn stable_hash_reduce<HCX, I, C, F>(
 659     hcx: &mut HCX,
 660     hasher: &mut StableHasher,
 661     mut collection: C,
 662     length: usize,
 663     hash_function: F,
 664 ) where
 665     C: Iterator<Item = I>,
 666     F: Fn(&mut StableHasher, &mut HCX, I),
 667 {
 668     length.hash_stable(hcx, hasher);
 669
 670     match length {
 671         1 => {
 672             hash_function(hasher, hcx, collection.next().unwrap());
 673         }
 674         _ => {
 675             let hash = collection
 676                 .map(|value| {
 677                     let mut hasher = StableHasher::new();
 678                     hash_function(&mut hasher, hcx, value);
 679                     hasher.finish::<u128>()
 680                 })
 681                 .reduce(|accum, value| accum.wrapping_add(value));
 682             hash.hash_stable(hcx, hasher);
 683         }
 684     }
 685 }
 686
 687 /// Controls what data we do or do not hash.
 688 /// Whenever a `HashStable` implementation caches its
 689 /// result, it needs to include `HashingControls` as part
 690 /// of the key, to ensure that it does not produce an incorrect
 691 /// result (for example, using a `Fingerprint` produced while
 692 /// hashing `Span`s when a `Fingerprint` without `Span`s is
 693 /// being requested)
 694 #[derive(Clone, Hash, Eq, PartialEq, Debug)]
 695 pub struct HashingControls {
 696     pub hash_spans: bool,
 697 }