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