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