src/librustc_data_structures/stable_hasher.rs

   1 use std::hash::{Hash, Hasher, BuildHasher};
   2 use std::marker::PhantomData;
   3 use std::mem;
   4 use smallvec::SmallVec;
   5 use crate::sip128::SipHasher128;
   6 use crate::indexed_vec;
   7 use crate::bit_set;
   8
   9 /// When hashing something that ends up affecting properties like symbol names,
  10 /// we want these symbol names to be calculated independently of other factors
  11 /// like what architecture you're compiling *from*.
  12 ///
  13 /// To that end we always convert integers to little-endian format before
  14 /// hashing and the architecture dependent `isize` and `usize` types are
  15 /// extended to 64 bits if needed.
  16 pub struct StableHasher<W> {
  17     state: SipHasher128,
  18     width: PhantomData<W>,
  19 }
  20
  21 impl<W: StableHasherResult> ::std::fmt::Debug for StableHasher<W> {
  22     fn fmt(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
  23         write!(f, "{:?}", self.state)
  24     }
  25 }
  26
  27 pub trait StableHasherResult: Sized {
  28     fn finish(hasher: StableHasher<Self>) -> Self;
  29 }
  30
  31 impl<W: StableHasherResult> StableHasher<W> {
  32     pub fn new() -> Self {
  33         StableHasher {
  34             state: SipHasher128::new_with_keys(0, 0),
  35             width: PhantomData,
  36         }
  37     }
  38
  39     pub fn finish(self) -> W {
  40         W::finish(self)
  41     }
  42 }
  43
  44 impl StableHasherResult for u128 {
  45     fn finish(hasher: StableHasher<Self>) -> Self {
  46         let (_0, _1) = hasher.finalize();
  47         (_0 as u128) | ((_1 as u128) << 64)
  48     }
  49 }
  50
  51 impl StableHasherResult for u64 {
  52     fn finish(hasher: StableHasher<Self>) -> Self {
  53         hasher.finalize().0
  54     }
  55 }
  56
  57 impl<W> StableHasher<W> {
  58     #[inline]
  59     pub fn finalize(self) -> (u64, u64) {
  60         self.state.finish128()
  61     }
  62 }
  63
  64 impl<W> Hasher for StableHasher<W> {
  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.
 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` comparision 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<W: StableHasherResult>(&self,
 169                                           hcx: &mut CTX,
 170                                           hasher: &mut StableHasher<W>);
 171 }
 172
 173 /// Implement this for types that can be turned into stable keys like, for
 174 /// example, for DefId that can be converted to a DefPathHash. This is used for
 175 /// bringing maps into a predictable order before hashing them.
 176 pub trait ToStableHashKey<HCX> {
 177     type KeyType: Ord + Clone + Sized + HashStable<HCX>;
 178     fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
 179 }
 180
 181 // Implement HashStable by just calling `Hash::hash()`. This works fine for
 182 // self-contained values that don't depend on the hashing context `CTX`.
 183 #[macro_export]
 184 macro_rules! impl_stable_hash_via_hash {
 185     ($t:ty) => (
 186         impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
 187             #[inline]
 188             fn hash_stable<W: $crate::stable_hasher::StableHasherResult>(
 189                 &self,
 190                 _: &mut CTX,
 191                 hasher: &mut $crate::stable_hasher::StableHasher<W>
 192             ) {
 193                 ::std::hash::Hash::hash(self, hasher);
 194             }
 195         }
 196     );
 197 }
 198
 199 impl_stable_hash_via_hash!(i8);
 200 impl_stable_hash_via_hash!(i16);
 201 impl_stable_hash_via_hash!(i32);
 202 impl_stable_hash_via_hash!(i64);
 203 impl_stable_hash_via_hash!(isize);
 204
 205 impl_stable_hash_via_hash!(u8);
 206 impl_stable_hash_via_hash!(u16);
 207 impl_stable_hash_via_hash!(u32);
 208 impl_stable_hash_via_hash!(u64);
 209 impl_stable_hash_via_hash!(usize);
 210
 211 impl_stable_hash_via_hash!(u128);
 212 impl_stable_hash_via_hash!(i128);
 213
 214 impl_stable_hash_via_hash!(char);
 215 impl_stable_hash_via_hash!(());
 216
 217 impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
 218     fn hash_stable<W: StableHasherResult>(&self,
 219                                           ctx: &mut CTX,
 220                                           hasher: &mut StableHasher<W>) {
 221         self.get().hash_stable(ctx, hasher)
 222     }
 223 }
 224
 225 impl<CTX> HashStable<CTX> for f32 {
 226     fn hash_stable<W: StableHasherResult>(&self,
 227                                           ctx: &mut CTX,
 228                                           hasher: &mut StableHasher<W>) {
 229         let val: u32 = unsafe {
 230             ::std::mem::transmute(*self)
 231         };
 232         val.hash_stable(ctx, hasher);
 233     }
 234 }
 235
 236 impl<CTX> HashStable<CTX> for f64 {
 237     fn hash_stable<W: StableHasherResult>(&self,
 238                                           ctx: &mut CTX,
 239                                           hasher: &mut StableHasher<W>) {
 240         let val: u64 = unsafe {
 241             ::std::mem::transmute(*self)
 242         };
 243         val.hash_stable(ctx, hasher);
 244     }
 245 }
 246
 247 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
 248     fn hash_stable<W: StableHasherResult>(&self,
 249                                           ctx: &mut CTX,
 250                                           hasher: &mut StableHasher<W>) {
 251         (*self as i8).hash_stable(ctx, hasher);
 252     }
 253 }
 254
 255 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
 256     fn hash_stable<W: StableHasherResult>(&self,
 257                                           ctx: &mut CTX,
 258                                           hasher: &mut StableHasher<W>) {
 259         let (ref _0,) = *self;
 260         _0.hash_stable(ctx, hasher);
 261     }
 262 }
 263
 264 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
 265     fn hash_stable<W: StableHasherResult>(&self,
 266                                           ctx: &mut CTX,
 267                                           hasher: &mut StableHasher<W>) {
 268         let (ref _0, ref _1) = *self;
 269         _0.hash_stable(ctx, hasher);
 270         _1.hash_stable(ctx, hasher);
 271     }
 272 }
 273
 274 impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
 275      where T1: HashStable<CTX>,
 276            T2: HashStable<CTX>,
 277            T3: HashStable<CTX>,
 278 {
 279     fn hash_stable<W: StableHasherResult>(&self,
 280                                           ctx: &mut CTX,
 281                                           hasher: &mut StableHasher<W>) {
 282         let (ref _0, ref _1, ref _2) = *self;
 283         _0.hash_stable(ctx, hasher);
 284         _1.hash_stable(ctx, hasher);
 285         _2.hash_stable(ctx, hasher);
 286     }
 287 }
 288
 289 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
 290      where T1: HashStable<CTX>,
 291            T2: HashStable<CTX>,
 292            T3: HashStable<CTX>,
 293            T4: HashStable<CTX>,
 294 {
 295     fn hash_stable<W: StableHasherResult>(&self,
 296                                           ctx: &mut CTX,
 297                                           hasher: &mut StableHasher<W>) {
 298         let (ref _0, ref _1, ref _2, ref _3) = *self;
 299         _0.hash_stable(ctx, hasher);
 300         _1.hash_stable(ctx, hasher);
 301         _2.hash_stable(ctx, hasher);
 302         _3.hash_stable(ctx, hasher);
 303     }
 304 }
 305
 306 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
 307     default fn hash_stable<W: StableHasherResult>(&self,
 308                                                   ctx: &mut CTX,
 309                                                   hasher: &mut StableHasher<W>) {
 310         self.len().hash_stable(ctx, hasher);
 311         for item in self {
 312             item.hash_stable(ctx, hasher);
 313         }
 314     }
 315 }
 316
 317 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
 318     #[inline]
 319     fn hash_stable<W: StableHasherResult>(&self,
 320                                           ctx: &mut CTX,
 321                                           hasher: &mut StableHasher<W>) {
 322         (&self[..]).hash_stable(ctx, hasher);
 323     }
 324 }
 325
 326 impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
 327     where K: HashStable<CTX> + Eq + Hash,
 328           V: HashStable<CTX>,
 329           R: BuildHasher,
 330 {
 331     #[inline]
 332     fn hash_stable<W: StableHasherResult>(&self,
 333                                           ctx: &mut CTX,
 334                                           hasher: &mut StableHasher<W>) {
 335         self.len().hash_stable(ctx, hasher);
 336         for kv in self {
 337             kv.hash_stable(ctx, hasher);
 338         }
 339     }
 340 }
 341
 342 impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R>
 343     where K: HashStable<CTX> + Eq + Hash,
 344           R: BuildHasher,
 345 {
 346     #[inline]
 347     fn hash_stable<W: StableHasherResult>(&self,
 348                                           ctx: &mut CTX,
 349                                           hasher: &mut StableHasher<W>) {
 350         self.len().hash_stable(ctx, hasher);
 351         for key in self {
 352             key.hash_stable(ctx, hasher);
 353         }
 354     }
 355 }
 356
 357 impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]> where A: HashStable<CTX> {
 358     #[inline]
 359     fn hash_stable<W: StableHasherResult>(&self,
 360                                           ctx: &mut CTX,
 361                                           hasher: &mut StableHasher<W>) {
 362         (&self[..]).hash_stable(ctx, hasher);
 363     }
 364 }
 365
 366 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
 367     #[inline]
 368     fn hash_stable<W: StableHasherResult>(&self,
 369                                           ctx: &mut CTX,
 370                                           hasher: &mut StableHasher<W>) {
 371         (**self).hash_stable(ctx, hasher);
 372     }
 373 }
 374
 375 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
 376     #[inline]
 377     fn hash_stable<W: StableHasherResult>(&self,
 378                                           ctx: &mut CTX,
 379                                           hasher: &mut StableHasher<W>) {
 380         (**self).hash_stable(ctx, hasher);
 381     }
 382 }
 383
 384 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
 385     #[inline]
 386     fn hash_stable<W: StableHasherResult>(&self,
 387                                           ctx: &mut CTX,
 388                                           hasher: &mut StableHasher<W>) {
 389         (**self).hash_stable(ctx, hasher);
 390     }
 391 }
 392
 393 impl<CTX> HashStable<CTX> for str {
 394     #[inline]
 395     fn hash_stable<W: StableHasherResult>(&self,
 396                                           _: &mut CTX,
 397                                           hasher: &mut StableHasher<W>) {
 398         self.len().hash(hasher);
 399         self.as_bytes().hash(hasher);
 400     }
 401 }
 402
 403
 404 impl<CTX> HashStable<CTX> for String {
 405     #[inline]
 406     fn hash_stable<W: StableHasherResult>(&self,
 407                                           hcx: &mut CTX,
 408                                           hasher: &mut StableHasher<W>) {
 409         (&self[..]).hash_stable(hcx, hasher);
 410     }
 411 }
 412
 413 impl<HCX> ToStableHashKey<HCX> for String {
 414     type KeyType = String;
 415     #[inline]
 416     fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
 417         self.clone()
 418     }
 419 }
 420
 421 impl<CTX> HashStable<CTX> for bool {
 422     #[inline]
 423     fn hash_stable<W: StableHasherResult>(&self,
 424                                           ctx: &mut CTX,
 425                                           hasher: &mut StableHasher<W>) {
 426         (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
 427     }
 428 }
 429
 430
 431 impl<T, CTX> HashStable<CTX> for Option<T>
 432     where T: HashStable<CTX>
 433 {
 434     #[inline]
 435     fn hash_stable<W: StableHasherResult>(&self,
 436                                           ctx: &mut CTX,
 437                                           hasher: &mut StableHasher<W>) {
 438         if let Some(ref value) = *self {
 439             1u8.hash_stable(ctx, hasher);
 440             value.hash_stable(ctx, hasher);
 441         } else {
 442             0u8.hash_stable(ctx, hasher);
 443         }
 444     }
 445 }
 446
 447 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
 448     where T1: HashStable<CTX>,
 449           T2: HashStable<CTX>,
 450 {
 451     #[inline]
 452     fn hash_stable<W: StableHasherResult>(&self,
 453                                           ctx: &mut CTX,
 454                                           hasher: &mut StableHasher<W>) {
 455         mem::discriminant(self).hash_stable(ctx, hasher);
 456         match *self {
 457             Ok(ref x) => x.hash_stable(ctx, hasher),
 458             Err(ref x) => x.hash_stable(ctx, hasher),
 459         }
 460     }
 461 }
 462
 463 impl<'a, T, CTX> HashStable<CTX> for &'a T
 464     where T: HashStable<CTX> + ?Sized
 465 {
 466     #[inline]
 467     fn hash_stable<W: StableHasherResult>(&self,
 468                                           ctx: &mut CTX,
 469                                           hasher: &mut StableHasher<W>) {
 470         (**self).hash_stable(ctx, hasher);
 471     }
 472 }
 473
 474 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
 475     #[inline]
 476     fn hash_stable<W: StableHasherResult>(&self,
 477                                           _: &mut CTX,
 478                                           hasher: &mut StableHasher<W>) {
 479         ::std::hash::Hash::hash(self, hasher);
 480     }
 481 }
 482
 483 impl<I: indexed_vec::Idx, T, CTX> HashStable<CTX> for indexed_vec::IndexVec<I, T>
 484     where T: HashStable<CTX>,
 485 {
 486     fn hash_stable<W: StableHasherResult>(&self,
 487                                           ctx: &mut CTX,
 488                                           hasher: &mut StableHasher<W>) {
 489         self.len().hash_stable(ctx, hasher);
 490         for v in &self.raw {
 491             v.hash_stable(ctx, hasher);
 492         }
 493     }
 494 }
 495
 496
 497 impl<I: indexed_vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I>
 498 {
 499     fn hash_stable<W: StableHasherResult>(&self,
 500                                           ctx: &mut CTX,
 501                                           hasher: &mut StableHasher<W>) {
 502         self.words().hash_stable(ctx, hasher);
 503     }
 504 }
 505
 506 impl_stable_hash_via_hash!(::std::path::Path);
 507 impl_stable_hash_via_hash!(::std::path::PathBuf);
 508
 509 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
 510     where K: ToStableHashKey<HCX> + Eq + Hash,
 511           V: HashStable<HCX>,
 512           R: BuildHasher,
 513 {
 514     #[inline]
 515     fn hash_stable<W: StableHasherResult>(&self,
 516                                           hcx: &mut HCX,
 517                                           hasher: &mut StableHasher<W>) {
 518         hash_stable_hashmap(hcx, hasher, self, ToStableHashKey::to_stable_hash_key);
 519     }
 520 }
 521
 522 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
 523     where K: ToStableHashKey<HCX> + Eq + Hash,
 524           R: BuildHasher,
 525 {
 526     fn hash_stable<W: StableHasherResult>(&self,
 527                                           hcx: &mut HCX,
 528                                           hasher: &mut StableHasher<W>) {
 529         let mut keys: Vec<_> = self.iter()
 530                                    .map(|k| k.to_stable_hash_key(hcx))
 531                                    .collect();
 532         keys.sort_unstable();
 533         keys.hash_stable(hcx, hasher);
 534     }
 535 }
 536
 537 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
 538     where K: ToStableHashKey<HCX>,
 539           V: HashStable<HCX>,
 540 {
 541     fn hash_stable<W: StableHasherResult>(&self,
 542                                           hcx: &mut HCX,
 543                                           hasher: &mut StableHasher<W>) {
 544         let mut entries: Vec<_> = self.iter()
 545                                       .map(|(k, v)| (k.to_stable_hash_key(hcx), v))
 546                                       .collect();
 547         entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 548         entries.hash_stable(hcx, hasher);
 549     }
 550 }
 551
 552 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
 553     where K: ToStableHashKey<HCX>,
 554 {
 555     fn hash_stable<W: StableHasherResult>(&self,
 556                                           hcx: &mut HCX,
 557                                           hasher: &mut StableHasher<W>) {
 558         let mut keys: Vec<_> = self.iter()
 559                                    .map(|k| k.to_stable_hash_key(hcx))
 560                                    .collect();
 561         keys.sort_unstable();
 562         keys.hash_stable(hcx, hasher);
 563     }
 564 }
 565
 566 pub fn hash_stable_hashmap<HCX, K, V, R, SK, F, W>(
 567     hcx: &mut HCX,
 568     hasher: &mut StableHasher<W>,
 569     map: &::std::collections::HashMap<K, V, R>,
 570     to_stable_hash_key: F)
 571     where K: Eq + Hash,
 572           V: HashStable<HCX>,
 573           R: BuildHasher,
 574           SK: HashStable<HCX> + Ord + Clone,
 575           F: Fn(&K, &HCX) -> SK,
 576           W: StableHasherResult,
 577 {
 578     let mut entries: Vec<_> = map.iter()
 579                                   .map(|(k, v)| (to_stable_hash_key(k, hcx), v))
 580                                   .collect();
 581     entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 582     entries.hash_stable(hcx, hasher);
 583 }
 584
 585
 586 /// A vector container that makes sure that its items are hashed in a stable
 587 /// order.
 588 pub struct StableVec<T>(Vec<T>);
 589
 590 impl<T> StableVec<T> {
 591     pub fn new(v: Vec<T>) -> Self {
 592         StableVec(v)
 593     }
 594 }
 595
 596 impl<T> ::std::ops::Deref for StableVec<T> {
 597     type Target = Vec<T>;
 598
 599     fn deref(&self) -> &Vec<T> {
 600         &self.0
 601     }
 602 }
 603
 604 impl<T, HCX> HashStable<HCX> for StableVec<T>
 605     where T: HashStable<HCX> + ToStableHashKey<HCX>
 606 {
 607     fn hash_stable<W: StableHasherResult>(&self,
 608                                           hcx: &mut HCX,
 609                                           hasher: &mut StableHasher<W>) {
 610         let StableVec(ref v) = *self;
 611
 612         let mut sorted: Vec<_> = v.iter()
 613                                   .map(|x| x.to_stable_hash_key(hcx))
 614                                   .collect();
 615         sorted.sort_unstable();
 616         sorted.hash_stable(hcx, hasher);
 617     }
 618 }