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     fn finish(hasher: StableHasher) -> Self {
  46         let (_0, _1) = hasher.finalize();
  47         u128::from(_0) | (u128::from(_1) << 64)
  48     }
  49 }
  50
  51 impl StableHasherResult for u64 {
  52     fn finish(hasher: StableHasher) -> Self {
  53         hasher.finalize().0
  54     }
  55 }
  56
  57 impl StableHasher {
  58     #[inline]
  59     pub fn finalize(self) -> (u64, u64) {
  60         self.state.finish128()
  61     }
  62 }
  63
  64 impl Hasher for StableHasher {
  65     fn finish(&self) -> u64 {
  66         panic!("use StableHasher::finalize instead");
  67     }
  68
  69     #[inline]
  70     fn write(&mut self, bytes: &[u8]) {
  71         self.state.write(bytes);
  72     }
  73
  74     #[inline]
  75     fn write_u8(&mut self, i: u8) {
  76         self.state.write_u8(i);
  77     }
  78
  79     #[inline]
  80     fn write_u16(&mut self, i: u16) {
  81         self.state.write_u16(i.to_le());
  82     }
  83
  84     #[inline]
  85     fn write_u32(&mut self, i: u32) {
  86         self.state.write_u32(i.to_le());
  87     }
  88
  89     #[inline]
  90     fn write_u64(&mut self, i: u64) {
  91         self.state.write_u64(i.to_le());
  92     }
  93
  94     #[inline]
  95     fn write_u128(&mut self, i: u128) {
  96         self.state.write_u128(i.to_le());
  97     }
  98
  99     #[inline]
 100     fn write_usize(&mut self, i: usize) {
 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());
 105     }
 106
 107     #[inline]
 108     fn write_i8(&mut self, i: i8) {
 109         self.state.write_i8(i);
 110     }
 111
 112     #[inline]
 113     fn write_i16(&mut self, i: i16) {
 114         self.state.write_i16(i.to_le());
 115     }
 116
 117     #[inline]
 118     fn write_i32(&mut self, i: i32) {
 119         self.state.write_i32(i.to_le());
 120     }
 121
 122     #[inline]
 123     fn write_i64(&mut self, i: i64) {
 124         self.state.write_i64(i.to_le());
 125     }
 126
 127     #[inline]
 128     fn write_i128(&mut self, i: i128) {
 129         self.state.write_i128(i.to_le());
 130     }
 131
 132     #[inline]
 133     fn write_isize(&mut self, i: isize) {
 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,
 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.
 138         self.state.write_i64((i as i64).to_le());
 139     }
 140 }
 141
 142 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
 143 /// stable across multiple compilation sessions.
 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
 156 ///   information into the hasher that a `PartialEq` comparison takes into
 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.
 168 pub trait HashStable<CTX> {
 169     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher);
 170 }
 171
 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> {
 176     type KeyType: Ord + Sized + HashStable<HCX>;
 177     fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
 178 }
 179
 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`.
 182 #[macro_export]
 183 macro_rules! impl_stable_hash_via_hash {
 184     ($t:ty) => {
 185         impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
 186             #[inline]
 187             fn hash_stable(&self, _: &mut CTX, hasher: &mut $crate::stable_hasher::StableHasher) {
 188                 ::std::hash::Hash::hash(self, hasher);
 189             }
 190         }
 191     };
 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
 212 impl<CTX> HashStable<CTX> for ! {
 213     fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) {
 214         unreachable!()
 215     }
 216 }
 217
 218 impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
 219     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 220         self.get().hash_stable(ctx, hasher)
 221     }
 222 }
 223
 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
 230 impl<CTX> HashStable<CTX> for f32 {
 231     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 232         let val: u32 = unsafe { ::std::mem::transmute(*self) };
 233         val.hash_stable(ctx, hasher);
 234     }
 235 }
 236
 237 impl<CTX> HashStable<CTX> for f64 {
 238     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 239         let val: u64 = unsafe { ::std::mem::transmute(*self) };
 240         val.hash_stable(ctx, hasher);
 241     }
 242 }
 243
 244 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
 245     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 246         (*self as i8).hash_stable(ctx, hasher);
 247     }
 248 }
 249
 250 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
 251     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 252         let (ref _0,) = *self;
 253         _0.hash_stable(ctx, hasher);
 254     }
 255 }
 256
 257 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
 258     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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)
 266 where
 267     T1: HashStable<CTX>,
 268     T2: HashStable<CTX>,
 269     T3: HashStable<CTX>,
 270 {
 271     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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);
 276     }
 277 }
 278
 279 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
 280 where
 281     T1: HashStable<CTX>,
 282     T2: HashStable<CTX>,
 283     T3: HashStable<CTX>,
 284     T4: HashStable<CTX>,
 285 {
 286     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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
 295 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
 296     default fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 297         self.len().hash_stable(ctx, hasher);
 298         for item in self {
 299             item.hash_stable(ctx, hasher);
 300         }
 301     }
 302 }
 303
 304 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
 305     #[inline]
 306     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 307         (&self[..]).hash_stable(ctx, hasher);
 308     }
 309 }
 310
 311 impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
 312 where
 313     K: HashStable<CTX> + Eq + Hash,
 314     V: HashStable<CTX>,
 315     R: BuildHasher,
 316 {
 317     #[inline]
 318     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 319         self.len().hash_stable(ctx, hasher);
 320         for kv in self {
 321             kv.hash_stable(ctx, hasher);
 322         }
 323     }
 324 }
 325
 326 impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R>
 327 where
 328     K: HashStable<CTX> + Eq + Hash,
 329     R: BuildHasher,
 330 {
 331     #[inline]
 332     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 333         self.len().hash_stable(ctx, hasher);
 334         for key in self {
 335             key.hash_stable(ctx, hasher);
 336         }
 337     }
 338 }
 339
 340 impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]>
 341 where
 342     A: HashStable<CTX>,
 343 {
 344     #[inline]
 345     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 346         (&self[..]).hash_stable(ctx, hasher);
 347     }
 348 }
 349
 350 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
 351     #[inline]
 352     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 353         (**self).hash_stable(ctx, hasher);
 354     }
 355 }
 356
 357 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
 358     #[inline]
 359     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 360         (**self).hash_stable(ctx, hasher);
 361     }
 362 }
 363
 364 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
 365     #[inline]
 366     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 367         (**self).hash_stable(ctx, hasher);
 368     }
 369 }
 370
 371 impl<CTX> HashStable<CTX> for str {
 372     #[inline]
 373     fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
 374         self.len().hash(hasher);
 375         self.as_bytes().hash(hasher);
 376     }
 377 }
 378
 379 impl<CTX> HashStable<CTX> for String {
 380     #[inline]
 381     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 382         (&self[..]).hash_stable(hcx, hasher);
 383     }
 384 }
 385
 386 impl<HCX> ToStableHashKey<HCX> for String {
 387     type KeyType = String;
 388     #[inline]
 389     fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
 390         self.clone()
 391     }
 392 }
 393
 394 impl<CTX> HashStable<CTX> for bool {
 395     #[inline]
 396     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 397         (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
 398     }
 399 }
 400
 401 impl<T, CTX> HashStable<CTX> for Option<T>
 402 where
 403     T: HashStable<CTX>,
 404 {
 405     #[inline]
 406     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 407         if let Some(ref value) = *self {
 408             1u8.hash_stable(ctx, hasher);
 409             value.hash_stable(ctx, hasher);
 410         } else {
 411             0u8.hash_stable(ctx, hasher);
 412         }
 413     }
 414 }
 415
 416 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
 417 where
 418     T1: HashStable<CTX>,
 419     T2: HashStable<CTX>,
 420 {
 421     #[inline]
 422     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 423         mem::discriminant(self).hash_stable(ctx, hasher);
 424         match *self {
 425             Ok(ref x) => x.hash_stable(ctx, hasher),
 426             Err(ref x) => x.hash_stable(ctx, hasher),
 427         }
 428     }
 429 }
 430
 431 impl<'a, T, CTX> HashStable<CTX> for &'a T
 432 where
 433     T: HashStable<CTX> + ?Sized,
 434 {
 435     #[inline]
 436     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 437         (**self).hash_stable(ctx, hasher);
 438     }
 439 }
 440
 441 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
 442     #[inline]
 443     fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
 444         ::std::hash::Hash::hash(self, hasher);
 445     }
 446 }
 447
 448 impl<T, CTX> HashStable<CTX> for ::std::ops::RangeInclusive<T>
 449 where
 450     T: HashStable<CTX>,
 451 {
 452     #[inline]
 453     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 454         self.start().hash_stable(ctx, hasher);
 455         self.end().hash_stable(ctx, hasher);
 456     }
 457 }
 458
 459 impl<I: vec::Idx, T, CTX> HashStable<CTX> for vec::IndexVec<I, T>
 460 where
 461     T: HashStable<CTX>,
 462 {
 463     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 464         self.len().hash_stable(ctx, hasher);
 465         for v in &self.raw {
 466             v.hash_stable(ctx, hasher);
 467         }
 468     }
 469 }
 470
 471 impl<I: vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I> {
 472     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 473         self.words().hash_stable(ctx, hasher);
 474     }
 475 }
 476
 477 impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX> for bit_set::BitMatrix<R, C> {
 478     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 479         self.words().hash_stable(ctx, hasher);
 480     }
 481 }
 482
 483 impl<T, CTX> HashStable<CTX> for bit_set::FiniteBitSet<T>
 484 where
 485     T: HashStable<CTX> + bit_set::FiniteBitSetTy,
 486 {
 487     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 488         self.0.hash_stable(hcx, hasher);
 489     }
 490 }
 491
 492 impl_stable_hash_via_hash!(::std::path::Path);
 493 impl_stable_hash_via_hash!(::std::path::PathBuf);
 494
 495 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
 496 where
 497     K: ToStableHashKey<HCX> + Eq,
 498     V: HashStable<HCX>,
 499     R: BuildHasher,
 500 {
 501     #[inline]
 502     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 503         hash_stable_hashmap(hcx, hasher, self, ToStableHashKey::to_stable_hash_key);
 504     }
 505 }
 506
 507 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
 508 where
 509     K: ToStableHashKey<HCX> + Eq,
 510     R: BuildHasher,
 511 {
 512     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 513         let mut keys: Vec<_> = self.iter().map(|k| k.to_stable_hash_key(hcx)).collect();
 514         keys.sort_unstable();
 515         keys.hash_stable(hcx, hasher);
 516     }
 517 }
 518
 519 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
 520 where
 521     K: ToStableHashKey<HCX>,
 522     V: HashStable<HCX>,
 523 {
 524     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 525         let mut entries: Vec<_> =
 526             self.iter().map(|(k, v)| (k.to_stable_hash_key(hcx), v)).collect();
 527         entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 528         entries.hash_stable(hcx, hasher);
 529     }
 530 }
 531
 532 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
 533 where
 534     K: ToStableHashKey<HCX>,
 535 {
 536     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 537         let mut keys: Vec<_> = self.iter().map(|k| k.to_stable_hash_key(hcx)).collect();
 538         keys.sort_unstable();
 539         keys.hash_stable(hcx, hasher);
 540     }
 541 }
 542
 543 pub fn hash_stable_hashmap<HCX, K, V, R, SK, F>(
 544     hcx: &mut HCX,
 545     hasher: &mut StableHasher,
 546     map: &::std::collections::HashMap<K, V, R>,
 547     to_stable_hash_key: F,
 548 ) where
 549     K: Eq,
 550     V: HashStable<HCX>,
 551     R: BuildHasher,
 552     SK: HashStable<HCX> + Ord,
 553     F: Fn(&K, &HCX) -> SK,
 554 {
 555     let mut entries: Vec<_> = map.iter().map(|(k, v)| (to_stable_hash_key(k, hcx), v)).collect();
 556     entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 557     entries.hash_stable(hcx, hasher);
 558 }