src/librustc_data_structures/stable_hasher.rs

   1 use std::hash::{Hash, Hasher, BuildHasher};
   2 use std::mem;
   3 use smallvec::SmallVec;
   4 use crate::sip128::SipHasher128;
   5 use rustc_index::vec;
   6 use rustc_index::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 {
  16     state: SipHasher128,
  17 }
  18
  19 impl ::std::fmt::Debug for StableHasher {
  20     fn fmt(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
  21         write!(f, "{:?}", self.state)
  22     }
  23 }
  24
  25 pub trait StableHasherResult: Sized {
  26     fn finish(hasher: StableHasher) -> Self;
  27 }
  28
  29 impl StableHasher {
  30     pub fn new() -> Self {
  31         StableHasher {
  32             state: SipHasher128::new_with_keys(0, 0),
  33         }
  34     }
  35
  36     pub fn finish<W: StableHasherResult>(self) -> W {
  37         W::finish(self)
  38     }
  39 }
  40
  41 impl StableHasherResult for u128 {
  42     fn finish(hasher: StableHasher) -> Self {
  43         let (_0, _1) = hasher.finalize();
  44         u128::from(_0) | (u128::from(_1) << 64)
  45     }
  46 }
  47
  48 impl StableHasherResult for u64 {
  49     fn finish(hasher: StableHasher) -> Self {
  50         hasher.finalize().0
  51     }
  52 }
  53
  54 impl StableHasher {
  55     #[inline]
  56     pub fn finalize(self) -> (u64, u64) {
  57         self.state.finish128()
  58     }
  59 }
  60
  61 impl Hasher for StableHasher {
  62     fn finish(&self) -> u64 {
  63         panic!("use StableHasher::finalize instead");
  64     }
  65
  66     #[inline]
  67     fn write(&mut self, bytes: &[u8]) {
  68         self.state.write(bytes);
  69     }
  70
  71     #[inline]
  72     fn write_u8(&mut self, i: u8) {
  73         self.state.write_u8(i);
  74     }
  75
  76     #[inline]
  77     fn write_u16(&mut self, i: u16) {
  78         self.state.write_u16(i.to_le());
  79     }
  80
  81     #[inline]
  82     fn write_u32(&mut self, i: u32) {
  83         self.state.write_u32(i.to_le());
  84     }
  85
  86     #[inline]
  87     fn write_u64(&mut self, i: u64) {
  88         self.state.write_u64(i.to_le());
  89     }
  90
  91     #[inline]
  92     fn write_u128(&mut self, i: u128) {
  93         self.state.write_u128(i.to_le());
  94     }
  95
  96     #[inline]
  97     fn write_usize(&mut self, i: usize) {
  98         // Always treat usize as u64 so we get the same results on 32 and 64 bit
  99         // platforms. This is important for symbol hashes when cross compiling,
 100         // for example.
 101         self.state.write_u64((i as u64).to_le());
 102     }
 103
 104     #[inline]
 105     fn write_i8(&mut self, i: i8) {
 106         self.state.write_i8(i);
 107     }
 108
 109     #[inline]
 110     fn write_i16(&mut self, i: i16) {
 111         self.state.write_i16(i.to_le());
 112     }
 113
 114     #[inline]
 115     fn write_i32(&mut self, i: i32) {
 116         self.state.write_i32(i.to_le());
 117     }
 118
 119     #[inline]
 120     fn write_i64(&mut self, i: i64) {
 121         self.state.write_i64(i.to_le());
 122     }
 123
 124     #[inline]
 125     fn write_i128(&mut self, i: i128) {
 126         self.state.write_i128(i.to_le());
 127     }
 128
 129     #[inline]
 130     fn write_isize(&mut self, i: isize) {
 131         // Always treat isize as i64 so we get the same results on 32 and 64 bit
 132         // platforms. This is important for symbol hashes when cross compiling,
 133         // for example.
 134         self.state.write_i64((i as i64).to_le());
 135     }
 136 }
 137
 138 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
 139 /// stable across multiple compilation sessions.
 140 ///
 141 /// Note that `HashStable` imposes rather more strict requirements than usual
 142 /// hash functions:
 143 ///
 144 /// - Stable hashes are sometimes used as identifiers. Therefore they must
 145 ///   conform to the corresponding `PartialEq` implementations:
 146 ///
 147 ///     - `x == y` implies `hash_stable(x) == hash_stable(y)`, and
 148 ///     - `x != y` implies `hash_stable(x) != hash_stable(y)`.
 149 ///
 150 ///   That second condition is usually not required for hash functions
 151 ///   (e.g. `Hash`). In practice this means that `hash_stable` must feed any
 152 ///   information into the hasher that a `PartialEq` comparison takes into
 153 ///   account. See [#49300](https://github.com/rust-lang/rust/issues/49300)
 154 ///   for an example where violating this invariant has caused trouble in the
 155 ///   past.
 156 ///
 157 /// - `hash_stable()` must be independent of the current
 158 ///    compilation session. E.g. they must not hash memory addresses or other
 159 ///    things that are "randomly" assigned per compilation session.
 160 ///
 161 /// - `hash_stable()` must be independent of the host architecture. The
 162 ///   `StableHasher` takes care of endianness and `isize`/`usize` platform
 163 ///   differences.
 164 pub trait HashStable<CTX> {
 165     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher);
 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 + 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(
 184                 &self,
 185                 _: &mut CTX,
 186                 hasher: &mut $crate::stable_hasher::StableHasher
 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(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 214         self.get().hash_stable(ctx, hasher)
 215     }
 216 }
 217
 218 impl<CTX> HashStable<CTX> for f32 {
 219     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 220         let val: u32 = unsafe {
 221             ::std::mem::transmute(*self)
 222         };
 223         val.hash_stable(ctx, hasher);
 224     }
 225 }
 226
 227 impl<CTX> HashStable<CTX> for f64 {
 228     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 229         let val: u64 = unsafe {
 230             ::std::mem::transmute(*self)
 231         };
 232         val.hash_stable(ctx, hasher);
 233     }
 234 }
 235
 236 impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
 237     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 238         (*self as i8).hash_stable(ctx, hasher);
 239     }
 240 }
 241
 242 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
 243     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 244         let (ref _0,) = *self;
 245         _0.hash_stable(ctx, hasher);
 246     }
 247 }
 248
 249 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
 250     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 251         let (ref _0, ref _1) = *self;
 252         _0.hash_stable(ctx, hasher);
 253         _1.hash_stable(ctx, hasher);
 254     }
 255 }
 256
 257 impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
 258      where T1: HashStable<CTX>,
 259            T2: HashStable<CTX>,
 260            T3: HashStable<CTX>,
 261 {
 262     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 263         let (ref _0, ref _1, ref _2) = *self;
 264         _0.hash_stable(ctx, hasher);
 265         _1.hash_stable(ctx, hasher);
 266         _2.hash_stable(ctx, hasher);
 267     }
 268 }
 269
 270 impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
 271      where T1: HashStable<CTX>,
 272            T2: HashStable<CTX>,
 273            T3: HashStable<CTX>,
 274            T4: HashStable<CTX>,
 275 {
 276     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 277         let (ref _0, ref _1, ref _2, ref _3) = *self;
 278         _0.hash_stable(ctx, hasher);
 279         _1.hash_stable(ctx, hasher);
 280         _2.hash_stable(ctx, hasher);
 281         _3.hash_stable(ctx, hasher);
 282     }
 283 }
 284
 285 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
 286     default fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 287         self.len().hash_stable(ctx, hasher);
 288         for item in self {
 289             item.hash_stable(ctx, hasher);
 290         }
 291     }
 292 }
 293
 294 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
 295     #[inline]
 296     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 297         (&self[..]).hash_stable(ctx, hasher);
 298     }
 299 }
 300
 301 impl<K, V, R, CTX> HashStable<CTX> for indexmap::IndexMap<K, V, R>
 302     where K: HashStable<CTX> + Eq + Hash,
 303           V: HashStable<CTX>,
 304           R: BuildHasher,
 305 {
 306     #[inline]
 307     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 308         self.len().hash_stable(ctx, hasher);
 309         for kv in self {
 310             kv.hash_stable(ctx, hasher);
 311         }
 312     }
 313 }
 314
 315 impl<K, R, CTX> HashStable<CTX> for indexmap::IndexSet<K, R>
 316     where K: HashStable<CTX> + Eq + Hash,
 317           R: BuildHasher,
 318 {
 319     #[inline]
 320     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 321         self.len().hash_stable(ctx, hasher);
 322         for key in self {
 323             key.hash_stable(ctx, hasher);
 324         }
 325     }
 326 }
 327
 328 impl<A, CTX> HashStable<CTX> for SmallVec<[A; 1]> where A: HashStable<CTX> {
 329     #[inline]
 330     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 331         (&self[..]).hash_stable(ctx, hasher);
 332     }
 333 }
 334
 335 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
 336     #[inline]
 337     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 352         (**self).hash_stable(ctx, hasher);
 353     }
 354 }
 355
 356 impl<CTX> HashStable<CTX> for str {
 357     #[inline]
 358     fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
 359         self.len().hash(hasher);
 360         self.as_bytes().hash(hasher);
 361     }
 362 }
 363
 364
 365 impl<CTX> HashStable<CTX> for String {
 366     #[inline]
 367     fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
 368         (&self[..]).hash_stable(hcx, hasher);
 369     }
 370 }
 371
 372 impl<HCX> ToStableHashKey<HCX> for String {
 373     type KeyType = String;
 374     #[inline]
 375     fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
 376         self.clone()
 377     }
 378 }
 379
 380 impl<CTX> HashStable<CTX> for bool {
 381     #[inline]
 382     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 383         (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
 384     }
 385 }
 386
 387
 388 impl<T, CTX> HashStable<CTX> for Option<T>
 389     where T: HashStable<CTX>
 390 {
 391     #[inline]
 392     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 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(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 408         mem::discriminant(self).hash_stable(ctx, hasher);
 409         match *self {
 410             Ok(ref x) => x.hash_stable(ctx, hasher),
 411             Err(ref x) => x.hash_stable(ctx, hasher),
 412         }
 413     }
 414 }
 415
 416 impl<'a, T, CTX> HashStable<CTX> for &'a T
 417     where T: HashStable<CTX> + ?Sized
 418 {
 419     #[inline]
 420     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 421         (**self).hash_stable(ctx, hasher);
 422     }
 423 }
 424
 425 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
 426     #[inline]
 427     fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) {
 428         ::std::hash::Hash::hash(self, hasher);
 429     }
 430 }
 431
 432 impl<T, CTX> HashStable<CTX> for ::std::ops::RangeInclusive<T>
 433     where T: HashStable<CTX>
 434 {
 435     #[inline]
 436     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 437         self.start().hash_stable(ctx, hasher);
 438         self.end().hash_stable(ctx, hasher);
 439     }
 440 }
 441
 442 impl<I: vec::Idx, T, CTX> HashStable<CTX> for vec::IndexVec<I, T>
 443     where T: HashStable<CTX>,
 444 {
 445     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 446         self.len().hash_stable(ctx, hasher);
 447         for v in &self.raw {
 448             v.hash_stable(ctx, hasher);
 449         }
 450     }
 451 }
 452
 453
 454 impl<I: vec::Idx, CTX> HashStable<CTX> for bit_set::BitSet<I>
 455 {
 456     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 457         self.words().hash_stable(ctx, hasher);
 458     }
 459 }
 460
 461 impl<R: vec::Idx, C: vec::Idx, CTX> HashStable<CTX>
 462 for bit_set::BitMatrix<R, C>
 463 {
 464     fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
 465         self.words().hash_stable(ctx, hasher);
 466     }
 467 }
 468
 469 impl_stable_hash_via_hash!(::std::path::Path);
 470 impl_stable_hash_via_hash!(::std::path::PathBuf);
 471
 472 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
 473     where K: ToStableHashKey<HCX> + Eq,
 474           V: HashStable<HCX>,
 475           R: BuildHasher,
 476 {
 477     #[inline]
 478     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 479         hash_stable_hashmap(hcx, hasher, self, ToStableHashKey::to_stable_hash_key);
 480     }
 481 }
 482
 483 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
 484     where K: ToStableHashKey<HCX> + Eq,
 485           R: BuildHasher,
 486 {
 487     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 488         let mut keys: Vec<_> = self.iter()
 489                                    .map(|k| k.to_stable_hash_key(hcx))
 490                                    .collect();
 491         keys.sort_unstable();
 492         keys.hash_stable(hcx, hasher);
 493     }
 494 }
 495
 496 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
 497     where K: ToStableHashKey<HCX>,
 498           V: HashStable<HCX>,
 499 {
 500     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 501         let mut entries: Vec<_> = self.iter()
 502                                       .map(|(k, v)| (k.to_stable_hash_key(hcx), v))
 503                                       .collect();
 504         entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 505         entries.hash_stable(hcx, hasher);
 506     }
 507 }
 508
 509 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
 510     where K: ToStableHashKey<HCX>,
 511 {
 512     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 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>(
 522     hcx: &mut HCX,
 523     hasher: &mut StableHasher,
 524     map: &::std::collections::HashMap<K, V, R>,
 525     to_stable_hash_key: F)
 526     where K: Eq,
 527           V: HashStable<HCX>,
 528           R: BuildHasher,
 529           SK: HashStable<HCX> + Ord,
 530           F: Fn(&K, &HCX) -> SK,
 531 {
 532     let mut entries: Vec<_> = map.iter()
 533                                   .map(|(k, v)| (to_stable_hash_key(k, hcx), v))
 534                                   .collect();
 535     entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 536     entries.hash_stable(hcx, hasher);
 537 }
 538
 539
 540 /// A vector container that makes sure that its items are hashed in a stable
 541 /// order.
 542 pub struct StableVec<T>(Vec<T>);
 543
 544 impl<T> StableVec<T> {
 545     pub fn new(v: Vec<T>) -> Self {
 546         StableVec(v)
 547     }
 548 }
 549
 550 impl<T> ::std::ops::Deref for StableVec<T> {
 551     type Target = Vec<T>;
 552
 553     fn deref(&self) -> &Vec<T> {
 554         &self.0
 555     }
 556 }
 557
 558 impl<T, HCX> HashStable<HCX> for StableVec<T>
 559     where T: HashStable<HCX> + ToStableHashKey<HCX>
 560 {
 561     fn hash_stable(&self, hcx: &mut HCX, hasher: &mut StableHasher) {
 562         let StableVec(ref v) = *self;
 563
 564         let mut sorted: Vec<_> = v.iter()
 565                                   .map(|x| x.to_stable_hash_key(hcx))
 566                                   .collect();
 567         sorted.sort_unstable();
 568         sorted.hash_stable(hcx, hasher);
 569     }
 570 }