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::mem;
   7
   8 #[cfg(test)]
   9 mod tests;
  10
  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*.
  14 ///
  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.
  18 pub struct StableHasher {
  19     state: SipHasher128,
  20 }
  21
  22 impl ::std::fmt::Debug for StableHasher {
  23     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
  24         write!(f, "{:?}", self.state)
  25     }
  26 }
  27
  28 pub trait StableHasherResult: Sized {
  29     fn finish(hasher: StableHasher) -> Self;
  30 }
  31
  32 impl StableHasher {
  33     #[inline]
  34     pub fn new() -> Self {
  35         StableHasher { state: SipHasher128::new_with_keys(0, 0) }
  36     }
  37
  38     #[inline]
  39     pub fn finish<W: StableHasherResult>(self) -> W {
  40         W::finish(self)
  41     }
  42 }
  43
  44 impl StableHasherResult for u128 {
  45     #[inline]
  46     fn finish(hasher: StableHasher) -> Self {
  47         let (_0, _1) = hasher.finalize();
  48         u128::from(_0) | (u128::from(_1) << 64)
  49     }
  50 }
  51
  52 impl StableHasherResult for u64 {
  53     #[inline]
  54     fn finish(hasher: StableHasher) -> Self {
  55         hasher.finalize().0
  56     }
  57 }
  58
  59 impl StableHasher {
  60     #[inline]
  61     pub fn finalize(self) -> (u64, u64) {
  62         self.state.finish128()
  63     }
  64 }
  65
  66 impl Hasher for StableHasher {
  67     fn finish(&self) -> u64 {
  68         panic!("use StableHasher::finalize instead");
  69     }
  70
  71     #[inline]
  72     fn write(&mut self, bytes: &[u8]) {
  73         self.state.write(bytes);
  74     }
  75
  76     #[inline]
  77     fn write_u8(&mut self, i: u8) {
  78         self.state.write_u8(i);
  79     }
  80
  81     #[inline]
  82     fn write_u16(&mut self, i: u16) {
  83         self.state.write_u16(i.to_le());
  84     }
  85
  86     #[inline]
  87     fn write_u32(&mut self, i: u32) {
  88         self.state.write_u32(i.to_le());
  89     }
  90
  91     #[inline]
  92     fn write_u64(&mut self, i: u64) {
  93         self.state.write_u64(i.to_le());
  94     }
  95
  96     #[inline]
  97     fn write_u128(&mut self, i: u128) {
  98         self.state.write_u128(i.to_le());
  99     }
 100
 101     #[inline]
 102     fn write_usize(&mut self, i: usize) {
 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());
 107     }
 108
 109     #[inline]
 110     fn write_i8(&mut self, i: i8) {
 111         self.state.write_i8(i);
 112     }
 113
 114     #[inline]
 115     fn write_i16(&mut self, i: i16) {
 116         self.state.write_i16(i.to_le());
 117     }
 118
 119     #[inline]
 120     fn write_i32(&mut self, i: i32) {
 121         self.state.write_i32(i.to_le());
 122     }
 123
 124     #[inline]
 125     fn write_i64(&mut self, i: i64) {
 126         self.state.write_i64(i.to_le());
 127     }
 128
 129     #[inline]
 130     fn write_i128(&mut self, i: i128) {
 131         self.state.write_i128(i.to_le());
 132     }
 133
 134     #[inline]
 135     fn write_isize(&mut self, i: isize) {
 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,
 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.
 140         self.state.write_i64((i as i64).to_le());
 141     }
 142 }
 143
 144 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
 145 /// stable across multiple compilation sessions.
 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
 158 ///   information into the hasher that a `PartialEq` comparison takes into
 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.
 170 pub trait HashStable<CTX> {
 171     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher);
 172 }
 173
 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> {
 178     type KeyType: Ord + Sized + HashStable<HCX>;
 179     fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
 180 }
 181
 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`.
 184 #[macro_export]
 185 macro_rules! impl_stable_hash_via_hash {
 186     ($t:ty) => {
 187         impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
 188             #[inline]
 189             fn hash_stable(&self, _: &mut CTX, hasher: &mut $crate::stable_hasher::StableHasher) {
 190                 ::std::hash::Hash::hash(self, hasher);
 191             }
 192         }
 193     };
 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
 214 impl<CTX> HashStable<CTX> for ! {
 215     fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) {
 216         unreachable!()
 217     }
 218 }
 219
 220 impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
 221     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 222         self.get().hash_stable(ctx, hasher)
 223     }
 224 }
 225
 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
 232 impl<CTX> HashStable<CTX> for f32 {
 233     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 234         let val: u32 = unsafe { ::std::mem::transmute(*self) };
 235         val.hash_stable(ctx, hasher);
 236     }
 237 }
 238
 239 impl<CTX> HashStable<CTX> for f64 {
 240     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 241         let val: u64 = unsafe { ::std::mem::transmute(*self) };
 242         val.hash_stable(ctx, hasher);
 243     }
 244 }
 245
 246 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
 247     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 248         (*self as i8).hash_stable(ctx, hasher);
 249     }
 250 }
 251
 252 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
 253     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 254         let (ref _0,) = *self;
 255         _0.hash_stable(ctx, hasher);
 256     }
 257 }
 258
 259 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
 260     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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)
 268 where
 269     T1: HashStable<CTX>,
 270     T2: HashStable<CTX>,
 271     T3: HashStable<CTX>,
 272 {
 273     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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);
 278     }
 279 }
 280
 281 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
 282 where
 283     T1: HashStable<CTX>,
 284     T2: HashStable<CTX>,
 285     T3: HashStable<CTX>,
 286     T4: HashStable<CTX>,
 287 {
 288     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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
 297 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
 298     default fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 299         self.len().hash_stable(ctx, hasher);
 300         for item in self {
 301             item.hash_stable(ctx, hasher);
 302         }
 303     }
 304 }
 305
 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
 313 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
 314     #[inline]
 315     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 316         (&self[..]).hash_stable(ctx, hasher);
 317     }
 318 }
 319
 320 impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
 321 where
 322     K: HashStable<CTX> + Eq + Hash,
 323     V: HashStable<CTX>,
 324     R: BuildHasher,
 325 {
 326     #[inline]
 327     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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>
 336 where
 337     K: HashStable<CTX> + Eq + Hash,
 338     R: BuildHasher,
 339 {
 340     #[inline]
 341     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 342         self.len().hash_stable(ctx, hasher);
 343         for key in self {
 344             key.hash_stable(ctx, hasher);
 345         }
 346     }
 347 }
 348
 349 impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]>
 350 where
 351     A: HashStable<CTX>,
 352 {
 353     #[inline]
 354     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 355         (&self[..]).hash_stable(ctx, hasher);
 356     }
 357 }
 358
 359 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
 360     #[inline]
 361     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 362         (**self).hash_stable(ctx, hasher);
 363     }
 364 }
 365
 366 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
 367     #[inline]
 368     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 369         (**self).hash_stable(ctx, hasher);
 370     }
 371 }
 372
 373 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
 374     #[inline]
 375     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 376         (**self).hash_stable(ctx, hasher);
 377     }
 378 }
 379
 380 impl<CTX> HashStable<CTX> for str {
 381     #[inline]
 382     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 383         self.as_bytes().hash_stable(ctx, hasher);
 384     }
 385 }
 386
 387 impl<CTX> HashStable<CTX> for String {
 388     #[inline]
 389     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 390         (&self[..]).hash_stable(hcx, hasher);
 391     }
 392 }
 393
 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
 402 impl<CTX> HashStable<CTX> for bool {
 403     #[inline]
 404     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 405         (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
 406     }
 407 }
 408
 409 impl<T, CTX> HashStable<CTX> for Option<T>
 410 where
 411     T: HashStable<CTX>,
 412 {
 413     #[inline]
 414     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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
 424 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
 425 where
 426     T1: HashStable<CTX>,
 427     T2: HashStable<CTX>,
 428 {
 429     #[inline]
 430     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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
 439 impl<'a, T, CTX> HashStable<CTX> for &'a T
 440 where
 441     T: HashStable<CTX> + ?Sized,
 442 {
 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, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
 450     #[inline]
 451     fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
 452         ::std::hash::Hash::hash(self, hasher);
 453     }
 454 }
 455
 456 impl<T, CTX> HashStable<CTX> for ::std::ops::RangeInclusive<T>
 457 where
 458     T: HashStable<CTX>,
 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
 467 impl<I: vec::Idx, T, CTX> HashStable<CTX> for vec::IndexVec<I, T>
 468 where
 469     T: HashStable<CTX>,
 470 {
 471     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 472         self.len().hash_stable(ctx, hasher);
 473         for v in &self.raw {
 474             v.hash_stable(ctx, hasher);
 475         }
 476     }
 477 }
 478
 479 impl<I: vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I> {
 480     fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) {
 481         ::std::hash::Hash::hash(self, hasher);
 482     }
 483 }
 484
 485 impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C> {
 486     fn hash_stable(&self, _ctx: &mut CTX, hasher: &mut StableHasher) {
 487         ::std::hash::Hash::hash(self, hasher);
 488     }
 489 }
 490
 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
 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>
 504 where
 505     K: ToStableHashKey<HCX> + Eq,
 506     V: HashStable<HCX>,
 507     R: BuildHasher,
 508 {
 509     #[inline]
 510     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 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         });
 516     }
 517 }
 518
 519 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
 520 where
 521     K: ToStableHashKey<HCX> + Eq,
 522     R: BuildHasher,
 523 {
 524     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 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         });
 529     }
 530 }
 531
 532 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
 533 where
 534     K: ToStableHashKey<HCX>,
 535     V: HashStable<HCX>,
 536 {
 537     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 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         });
 543     }
 544 }
 545
 546 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
 547 where
 548     K: ToStableHashKey<HCX>,
 549 {
 550     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 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         });
 555     }
 556 }
 557
 558 fn stable_hash_reduce<HCX, I, C, F>(
 559     hcx: &mut HCX,
 560     hasher: &mut StableHasher,
 561     mut collection: C,
 562     length: usize,
 563     hash_function: F,
 564 ) where
 565     C: Iterator<Item = I>,
 566     F: Fn(&mut StableHasher, &mut HCX, I),
 567 {
 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     }
 585 }