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