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