src/librustc_data_structures/stable_hasher.rs

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