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 pub trait HashStable<CTX> {
 144     fn hash_stable<W: StableHasherResult>(&self,
 145                                           hcx: &mut CTX,
 146                                           hasher: &mut StableHasher<W>);
 147 }
 148
 149 /// Implement this for types that can be turned into stable keys like, for
 150 /// example, for DefId that can be converted to a DefPathHash. This is used for
 151 /// bringing maps into a predictable order before hashing them.
 152 pub trait ToStableHashKey<HCX> {
 153     type KeyType: Ord + Clone + Sized + HashStable<HCX>;
 154     fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
 155 }
 156
 157 // Implement HashStable by just calling `Hash::hash()`. This works fine for
 158 // self-contained values that don't depend on the hashing context `CTX`.
 159 #[macro_export]
 160 macro_rules! impl_stable_hash_via_hash {
 161     ($t:ty) => (
 162         impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
 163             #[inline]
 164             fn hash_stable<W: $crate::stable_hasher::StableHasherResult>(
 165                 &self,
 166                 _: &mut CTX,
 167                 hasher: &mut $crate::stable_hasher::StableHasher<W>
 168             ) {
 169                 ::std::hash::Hash::hash(self, hasher);
 170             }
 171         }
 172     );
 173 }
 174
 175 impl_stable_hash_via_hash!(i8);
 176 impl_stable_hash_via_hash!(i16);
 177 impl_stable_hash_via_hash!(i32);
 178 impl_stable_hash_via_hash!(i64);
 179 impl_stable_hash_via_hash!(isize);
 180
 181 impl_stable_hash_via_hash!(u8);
 182 impl_stable_hash_via_hash!(u16);
 183 impl_stable_hash_via_hash!(u32);
 184 impl_stable_hash_via_hash!(u64);
 185 impl_stable_hash_via_hash!(usize);
 186
 187 impl_stable_hash_via_hash!(u128);
 188 impl_stable_hash_via_hash!(i128);
 189
 190 impl_stable_hash_via_hash!(char);
 191 impl_stable_hash_via_hash!(());
 192
 193 impl<CTX> HashStable<CTX> for ::std::num::NonZeroU32 {
 194     fn hash_stable<W: StableHasherResult>(&self,
 195                                           ctx: &mut CTX,
 196                                           hasher: &mut StableHasher<W>) {
 197         self.get().hash_stable(ctx, hasher)
 198     }
 199 }
 200
 201 impl<CTX> HashStable<CTX> for f32 {
 202     fn hash_stable<W: StableHasherResult>(&self,
 203                                           ctx: &mut CTX,
 204                                           hasher: &mut StableHasher<W>) {
 205         let val: u32 = unsafe {
 206             ::std::mem::transmute(*self)
 207         };
 208         val.hash_stable(ctx, hasher);
 209     }
 210 }
 211
 212 impl<CTX> HashStable<CTX> for f64 {
 213     fn hash_stable<W: StableHasherResult>(&self,
 214                                           ctx: &mut CTX,
 215                                           hasher: &mut StableHasher<W>) {
 216         let val: u64 = unsafe {
 217             ::std::mem::transmute(*self)
 218         };
 219         val.hash_stable(ctx, hasher);
 220     }
 221 }
 222
 223 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
 224     fn hash_stable<W: StableHasherResult>(&self,
 225                                           ctx: &mut CTX,
 226                                           hasher: &mut StableHasher<W>) {
 227         (*self as i8).hash_stable(ctx, hasher);
 228     }
 229 }
 230
 231 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
 232     fn hash_stable<W: StableHasherResult>(&self,
 233                                           ctx: &mut CTX,
 234                                           hasher: &mut StableHasher<W>) {
 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<W: StableHasherResult>(&self,
 242                                           ctx: &mut CTX,
 243                                           hasher: &mut StableHasher<W>) {
 244         let (ref _0, ref _1) = *self;
 245         _0.hash_stable(ctx, hasher);
 246         _1.hash_stable(ctx, hasher);
 247     }
 248 }
 249
 250 impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
 251      where T1: HashStable<CTX>,
 252            T2: HashStable<CTX>,
 253            T3: HashStable<CTX>,
 254 {
 255     fn hash_stable<W: StableHasherResult>(&self,
 256                                           ctx: &mut CTX,
 257                                           hasher: &mut StableHasher<W>) {
 258         let (ref _0, ref _1, ref _2) = *self;
 259         _0.hash_stable(ctx, hasher);
 260         _1.hash_stable(ctx, hasher);
 261         _2.hash_stable(ctx, hasher);
 262     }
 263 }
 264
 265 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
 266      where T1: HashStable<CTX>,
 267            T2: HashStable<CTX>,
 268            T3: HashStable<CTX>,
 269            T4: HashStable<CTX>,
 270 {
 271     fn hash_stable<W: StableHasherResult>(&self,
 272                                           ctx: &mut CTX,
 273                                           hasher: &mut StableHasher<W>) {
 274         let (ref _0, ref _1, ref _2, ref _3) = *self;
 275         _0.hash_stable(ctx, hasher);
 276         _1.hash_stable(ctx, hasher);
 277         _2.hash_stable(ctx, hasher);
 278         _3.hash_stable(ctx, hasher);
 279     }
 280 }
 281
 282 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
 283     default fn hash_stable<W: StableHasherResult>(&self,
 284                                                   ctx: &mut CTX,
 285                                                   hasher: &mut StableHasher<W>) {
 286         self.len().hash_stable(ctx, hasher);
 287         for item in self {
 288             item.hash_stable(ctx, hasher);
 289         }
 290     }
 291 }
 292
 293 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
 294     #[inline]
 295     fn hash_stable<W: StableHasherResult>(&self,
 296                                           ctx: &mut CTX,
 297                                           hasher: &mut StableHasher<W>) {
 298         (&self[..]).hash_stable(ctx, hasher);
 299     }
 300 }
 301
 302 impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]> where A: HashStable<CTX> {
 303     #[inline]
 304     fn hash_stable<W: StableHasherResult>(&self,
 305                                           ctx: &mut CTX,
 306                                           hasher: &mut StableHasher<W>) {
 307         (&self[..]).hash_stable(ctx, hasher);
 308     }
 309 }
 310
 311 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
 312     #[inline]
 313     fn hash_stable<W: StableHasherResult>(&self,
 314                                           ctx: &mut CTX,
 315                                           hasher: &mut StableHasher<W>) {
 316         (**self).hash_stable(ctx, hasher);
 317     }
 318 }
 319
 320 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
 321     #[inline]
 322     fn hash_stable<W: StableHasherResult>(&self,
 323                                           ctx: &mut CTX,
 324                                           hasher: &mut StableHasher<W>) {
 325         (**self).hash_stable(ctx, hasher);
 326     }
 327 }
 328
 329 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
 330     #[inline]
 331     fn hash_stable<W: StableHasherResult>(&self,
 332                                           ctx: &mut CTX,
 333                                           hasher: &mut StableHasher<W>) {
 334         (**self).hash_stable(ctx, hasher);
 335     }
 336 }
 337
 338 impl<CTX> HashStable<CTX> for str {
 339     #[inline]
 340     fn hash_stable<W: StableHasherResult>(&self,
 341                                           _: &mut CTX,
 342                                           hasher: &mut StableHasher<W>) {
 343         self.len().hash(hasher);
 344         self.as_bytes().hash(hasher);
 345     }
 346 }
 347
 348
 349 impl<CTX> HashStable<CTX> for String {
 350     #[inline]
 351     fn hash_stable<W: StableHasherResult>(&self,
 352                                           hcx: &mut CTX,
 353                                           hasher: &mut StableHasher<W>) {
 354         (&self[..]).hash_stable(hcx, hasher);
 355     }
 356 }
 357
 358 impl<HCX> ToStableHashKey<HCX> for String {
 359     type KeyType = String;
 360     #[inline]
 361     fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
 362         self.clone()
 363     }
 364 }
 365
 366 impl<CTX> HashStable<CTX> for bool {
 367     #[inline]
 368     fn hash_stable<W: StableHasherResult>(&self,
 369                                           ctx: &mut CTX,
 370                                           hasher: &mut StableHasher<W>) {
 371         (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
 372     }
 373 }
 374
 375
 376 impl<T, CTX> HashStable<CTX> for Option<T>
 377     where T: HashStable<CTX>
 378 {
 379     #[inline]
 380     fn hash_stable<W: StableHasherResult>(&self,
 381                                           ctx: &mut CTX,
 382                                           hasher: &mut StableHasher<W>) {
 383         if let Some(ref value) = *self {
 384             1u8.hash_stable(ctx, hasher);
 385             value.hash_stable(ctx, hasher);
 386         } else {
 387             0u8.hash_stable(ctx, hasher);
 388         }
 389     }
 390 }
 391
 392 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
 393     where T1: HashStable<CTX>,
 394           T2: HashStable<CTX>,
 395 {
 396     #[inline]
 397     fn hash_stable<W: StableHasherResult>(&self,
 398                                           ctx: &mut CTX,
 399                                           hasher: &mut StableHasher<W>) {
 400         mem::discriminant(self).hash_stable(ctx, hasher);
 401         match *self {
 402             Ok(ref x) => x.hash_stable(ctx, hasher),
 403             Err(ref x) => x.hash_stable(ctx, hasher),
 404         }
 405     }
 406 }
 407
 408 impl<'a, T, CTX> HashStable<CTX> for &'a T
 409     where T: HashStable<CTX> + ?Sized
 410 {
 411     #[inline]
 412     fn hash_stable<W: StableHasherResult>(&self,
 413                                           ctx: &mut CTX,
 414                                           hasher: &mut StableHasher<W>) {
 415         (**self).hash_stable(ctx, hasher);
 416     }
 417 }
 418
 419 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
 420     #[inline]
 421     fn hash_stable<W: StableHasherResult>(&self,
 422                                           _: &mut CTX,
 423                                           hasher: &mut StableHasher<W>) {
 424         ::std::hash::Hash::hash(self, hasher);
 425     }
 426 }
 427
 428 impl<I: indexed_vec::Idx, T, CTX> HashStable<CTX> for indexed_vec::IndexVec<I, T>
 429     where T: HashStable<CTX>,
 430 {
 431     fn hash_stable<W: StableHasherResult>(&self,
 432                                           ctx: &mut CTX,
 433                                           hasher: &mut StableHasher<W>) {
 434         self.len().hash_stable(ctx, hasher);
 435         for v in &self.raw {
 436             v.hash_stable(ctx, hasher);
 437         }
 438     }
 439 }
 440
 441
 442 impl<I: indexed_vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I>
 443 {
 444     fn hash_stable<W: StableHasherResult>(&self,
 445                                           ctx: &mut CTX,
 446                                           hasher: &mut StableHasher<W>) {
 447         self.words().hash_stable(ctx, hasher);
 448     }
 449 }
 450
 451 impl_stable_hash_via_hash!(::std::path::Path);
 452 impl_stable_hash_via_hash!(::std::path::PathBuf);
 453
 454 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
 455     where K: ToStableHashKey<HCX> + Eq + Hash,
 456           V: HashStable<HCX>,
 457           R: BuildHasher,
 458 {
 459     #[inline]
 460     fn hash_stable<W: StableHasherResult>(&self,
 461                                           hcx: &mut HCX,
 462                                           hasher: &mut StableHasher<W>) {
 463         hash_stable_hashmap(hcx, hasher, self, ToStableHashKey::to_stable_hash_key);
 464     }
 465 }
 466
 467 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
 468     where K: ToStableHashKey<HCX> + Eq + Hash,
 469           R: BuildHasher,
 470 {
 471     fn hash_stable<W: StableHasherResult>(&self,
 472                                           hcx: &mut HCX,
 473                                           hasher: &mut StableHasher<W>) {
 474         let mut keys: Vec<_> = self.iter()
 475                                    .map(|k| k.to_stable_hash_key(hcx))
 476                                    .collect();
 477         keys.sort_unstable();
 478         keys.hash_stable(hcx, hasher);
 479     }
 480 }
 481
 482 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
 483     where K: ToStableHashKey<HCX>,
 484           V: HashStable<HCX>,
 485 {
 486     fn hash_stable<W: StableHasherResult>(&self,
 487                                           hcx: &mut HCX,
 488                                           hasher: &mut StableHasher<W>) {
 489         let mut entries: Vec<_> = self.iter()
 490                                       .map(|(k, v)| (k.to_stable_hash_key(hcx), v))
 491                                       .collect();
 492         entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 493         entries.hash_stable(hcx, hasher);
 494     }
 495 }
 496
 497 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
 498     where K: ToStableHashKey<HCX>,
 499 {
 500     fn hash_stable<W: StableHasherResult>(&self,
 501                                           hcx: &mut HCX,
 502                                           hasher: &mut StableHasher<W>) {
 503         let mut keys: Vec<_> = self.iter()
 504                                    .map(|k| k.to_stable_hash_key(hcx))
 505                                    .collect();
 506         keys.sort_unstable();
 507         keys.hash_stable(hcx, hasher);
 508     }
 509 }
 510
 511 pub fn hash_stable_hashmap<HCX, K, V, R, SK, F, W>(
 512     hcx: &mut HCX,
 513     hasher: &mut StableHasher<W>,
 514     map: &::std::collections::HashMap<K, V, R>,
 515     to_stable_hash_key: F)
 516     where K: Eq + Hash,
 517           V: HashStable<HCX>,
 518           R: BuildHasher,
 519           SK: HashStable<HCX> + Ord + Clone,
 520           F: Fn(&K, &HCX) -> SK,
 521           W: StableHasherResult,
 522 {
 523     let mut entries: Vec<_> = map.iter()
 524                                   .map(|(k, v)| (to_stable_hash_key(k, hcx), v))
 525                                   .collect();
 526     entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 527     entries.hash_stable(hcx, hasher);
 528 }
 529
 530
 531 /// A vector container that makes sure that its items are hashed in a stable
 532 /// order.
 533 pub struct StableVec<T>(Vec<T>);
 534
 535 impl<T> StableVec<T> {
 536     pub fn new(v: Vec<T>) -> Self {
 537         StableVec(v)
 538     }
 539 }
 540
 541 impl<T> ::std::ops::Deref for StableVec<T> {
 542     type Target = Vec<T>;
 543
 544     fn deref(&self) -> &Vec<T> {
 545         &self.0
 546     }
 547 }
 548
 549 impl<T, HCX> HashStable<HCX> for StableVec<T>
 550     where T: HashStable<HCX> + ToStableHashKey<HCX>
 551 {
 552     fn hash_stable<W: StableHasherResult>(&self,
 553                                           hcx: &mut HCX,
 554                                           hasher: &mut StableHasher<W>) {
 555         let StableVec(ref v) = *self;
 556
 557         let mut sorted: Vec<_> = v.iter()
 558                                   .map(|x| x.to_stable_hash_key(hcx))
 559                                   .collect();
 560         sorted.sort_unstable();
 561         sorted.hash_stable(hcx, hasher);
 562     }
 563 }