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         (&self[..]).hash_stable(ctx, hasher);
 328     }
 329 }
 330
 331 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
 332     #[inline]
 333     fn hash_stable<W: StableHasherResult>(&self,
 334                                           ctx: &mut CTX,
 335                                           hasher: &mut StableHasher<W>) {
 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<W: StableHasherResult>(&self,
 343                                           ctx: &mut CTX,
 344                                           hasher: &mut StableHasher<W>) {
 345         (**self).hash_stable(ctx, hasher);
 346     }
 347 }
 348
 349 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
 350     #[inline]
 351     fn hash_stable<W: StableHasherResult>(&self,
 352                                           ctx: &mut CTX,
 353                                           hasher: &mut StableHasher<W>) {
 354         (**self).hash_stable(ctx, hasher);
 355     }
 356 }
 357
 358 impl<CTX> HashStable<CTX> for str {
 359     #[inline]
 360     fn hash_stable<W: StableHasherResult>(&self,
 361                                           _: &mut CTX,
 362                                           hasher: &mut StableHasher<W>) {
 363         self.len().hash(hasher);
 364         self.as_bytes().hash(hasher);
 365     }
 366 }
 367
 368
 369 impl<CTX> HashStable<CTX> for String {
 370     #[inline]
 371     fn hash_stable<W: StableHasherResult>(&self,
 372                                           hcx: &mut CTX,
 373                                           hasher: &mut StableHasher<W>) {
 374         (&self[..]).hash_stable(hcx, hasher);
 375     }
 376 }
 377
 378 impl<HCX> ToStableHashKey<HCX> for String {
 379     type KeyType = String;
 380     #[inline]
 381     fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
 382         self.clone()
 383     }
 384 }
 385
 386 impl<CTX> HashStable<CTX> for bool {
 387     #[inline]
 388     fn hash_stable<W: StableHasherResult>(&self,
 389                                           ctx: &mut CTX,
 390                                           hasher: &mut StableHasher<W>) {
 391         (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
 392     }
 393 }
 394
 395
 396 impl<T, CTX> HashStable<CTX> for Option<T>
 397     where T: HashStable<CTX>
 398 {
 399     #[inline]
 400     fn hash_stable<W: StableHasherResult>(&self,
 401                                           ctx: &mut CTX,
 402                                           hasher: &mut StableHasher<W>) {
 403         if let Some(ref value) = *self {
 404             1u8.hash_stable(ctx, hasher);
 405             value.hash_stable(ctx, hasher);
 406         } else {
 407             0u8.hash_stable(ctx, hasher);
 408         }
 409     }
 410 }
 411
 412 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
 413     where T1: HashStable<CTX>,
 414           T2: HashStable<CTX>,
 415 {
 416     #[inline]
 417     fn hash_stable<W: StableHasherResult>(&self,
 418                                           ctx: &mut CTX,
 419                                           hasher: &mut StableHasher<W>) {
 420         mem::discriminant(self).hash_stable(ctx, hasher);
 421         match *self {
 422             Ok(ref x) => x.hash_stable(ctx, hasher),
 423             Err(ref x) => x.hash_stable(ctx, hasher),
 424         }
 425     }
 426 }
 427
 428 impl<'a, T, CTX> HashStable<CTX> for &'a T
 429     where T: HashStable<CTX> + ?Sized
 430 {
 431     #[inline]
 432     fn hash_stable<W: StableHasherResult>(&self,
 433                                           ctx: &mut CTX,
 434                                           hasher: &mut StableHasher<W>) {
 435         (**self).hash_stable(ctx, hasher);
 436     }
 437 }
 438
 439 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
 440     #[inline]
 441     fn hash_stable<W: StableHasherResult>(&self,
 442                                           _: &mut CTX,
 443                                           hasher: &mut StableHasher<W>) {
 444         ::std::hash::Hash::hash(self, hasher);
 445     }
 446 }
 447
 448 impl<I: indexed_vec::Idx, T, CTX> HashStable<CTX> for indexed_vec::IndexVec<I, T>
 449     where T: HashStable<CTX>,
 450 {
 451     fn hash_stable<W: StableHasherResult>(&self,
 452                                           ctx: &mut CTX,
 453                                           hasher: &mut StableHasher<W>) {
 454         self.len().hash_stable(ctx, hasher);
 455         for v in &self.raw {
 456             v.hash_stable(ctx, hasher);
 457         }
 458     }
 459 }
 460
 461
 462 impl<I: indexed_vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I>
 463 {
 464     fn hash_stable<W: StableHasherResult>(&self,
 465                                           ctx: &mut CTX,
 466                                           hasher: &mut StableHasher<W>) {
 467         self.words().hash_stable(ctx, hasher);
 468     }
 469 }
 470
 471 impl_stable_hash_via_hash!(::std::path::Path);
 472 impl_stable_hash_via_hash!(::std::path::PathBuf);
 473
 474 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
 475     where K: ToStableHashKey<HCX> + Eq + Hash,
 476           V: HashStable<HCX>,
 477           R: BuildHasher,
 478 {
 479     #[inline]
 480     fn hash_stable<W: StableHasherResult>(&self,
 481                                           hcx: &mut HCX,
 482                                           hasher: &mut StableHasher<W>) {
 483         hash_stable_hashmap(hcx, hasher, self, ToStableHashKey::to_stable_hash_key);
 484     }
 485 }
 486
 487 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
 488     where K: ToStableHashKey<HCX> + Eq + Hash,
 489           R: BuildHasher,
 490 {
 491     fn hash_stable<W: StableHasherResult>(&self,
 492                                           hcx: &mut HCX,
 493                                           hasher: &mut StableHasher<W>) {
 494         let mut keys: Vec<_> = self.iter()
 495                                    .map(|k| k.to_stable_hash_key(hcx))
 496                                    .collect();
 497         keys.sort_unstable();
 498         keys.hash_stable(hcx, hasher);
 499     }
 500 }
 501
 502 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
 503     where K: ToStableHashKey<HCX>,
 504           V: HashStable<HCX>,
 505 {
 506     fn hash_stable<W: StableHasherResult>(&self,
 507                                           hcx: &mut HCX,
 508                                           hasher: &mut StableHasher<W>) {
 509         let mut entries: Vec<_> = self.iter()
 510                                       .map(|(k, v)| (k.to_stable_hash_key(hcx), v))
 511                                       .collect();
 512         entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 513         entries.hash_stable(hcx, hasher);
 514     }
 515 }
 516
 517 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
 518     where K: ToStableHashKey<HCX>,
 519 {
 520     fn hash_stable<W: StableHasherResult>(&self,
 521                                           hcx: &mut HCX,
 522                                           hasher: &mut StableHasher<W>) {
 523         let mut keys: Vec<_> = self.iter()
 524                                    .map(|k| k.to_stable_hash_key(hcx))
 525                                    .collect();
 526         keys.sort_unstable();
 527         keys.hash_stable(hcx, hasher);
 528     }
 529 }
 530
 531 pub fn hash_stable_hashmap<HCX, K, V, R, SK, F, W>(
 532     hcx: &mut HCX,
 533     hasher: &mut StableHasher<W>,
 534     map: &::std::collections::HashMap<K, V, R>,
 535     to_stable_hash_key: F)
 536     where K: Eq + Hash,
 537           V: HashStable<HCX>,
 538           R: BuildHasher,
 539           SK: HashStable<HCX> + Ord + Clone,
 540           F: Fn(&K, &HCX) -> SK,
 541           W: StableHasherResult,
 542 {
 543     let mut entries: Vec<_> = map.iter()
 544                                   .map(|(k, v)| (to_stable_hash_key(k, hcx), v))
 545                                   .collect();
 546     entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 547     entries.hash_stable(hcx, hasher);
 548 }
 549
 550
 551 /// A vector container that makes sure that its items are hashed in a stable
 552 /// order.
 553 pub struct StableVec<T>(Vec<T>);
 554
 555 impl<T> StableVec<T> {
 556     pub fn new(v: Vec<T>) -> Self {
 557         StableVec(v)
 558     }
 559 }
 560
 561 impl<T> ::std::ops::Deref for StableVec<T> {
 562     type Target = Vec<T>;
 563
 564     fn deref(&self) -> &Vec<T> {
 565         &self.0
 566     }
 567 }
 568
 569 impl<T, HCX> HashStable<HCX> for StableVec<T>
 570     where T: HashStable<HCX> + ToStableHashKey<HCX>
 571 {
 572     fn hash_stable<W: StableHasherResult>(&self,
 573                                           hcx: &mut HCX,
 574                                           hasher: &mut StableHasher<W>) {
 575         let StableVec(ref v) = *self;
 576
 577         let mut sorted: Vec<_> = v.iter()
 578                                   .map(|x| x.to_stable_hash_key(hcx))
 579                                   .collect();
 580         sorted.sort_unstable();
 581         sorted.hash_stable(hcx, hasher);
 582     }
 583 }