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