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 blake2b::Blake2bHasher;
  15 use rustc_serialize::leb128;
  16
  17 fn write_unsigned_leb128_to_buf(buf: &mut [u8; 16], value: u64) -> usize {
  18     leb128::write_unsigned_leb128_to(value as u128, |i, v| buf[i] = v)
  19 }
  20
  21 fn write_signed_leb128_to_buf(buf: &mut [u8; 16], value: i64) -> usize {
  22     leb128::write_signed_leb128_to(value as i128, |i, v| buf[i] = v)
  23 }
  24
  25 /// When hashing something that ends up affecting properties like symbol names. We
  26 /// want these symbol names to be calculated independent of other factors like
  27 /// what architecture you're compiling *from*.
  28 ///
  29 /// The hashing just uses the standard `Hash` trait, but the implementations of
  30 /// `Hash` for the `usize` and `isize` types are *not* architecture independent
  31 /// (e.g. they has 4 or 8 bytes). As a result we want to avoid `usize` and
  32 /// `isize` completely when hashing.
  33 ///
  34 /// To do that, we encode all integers to be hashed with some
  35 /// arch-independent encoding.
  36 ///
  37 /// At the moment, we pass i8/u8 straight through and encode
  38 /// all other integers using leb128.
  39 ///
  40 /// This hasher currently always uses the stable Blake2b algorithm
  41 /// and allows for variable output lengths through its type
  42 /// parameter.
  43 pub struct StableHasher<W> {
  44     state: Blake2bHasher,
  45     bytes_hashed: u64,
  46     width: PhantomData<W>,
  47 }
  48
  49 impl<W: StableHasherResult> ::std::fmt::Debug for StableHasher<W> {
  50     fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
  51         write!(f, "{:?}", self.state)
  52     }
  53 }
  54
  55 pub trait StableHasherResult: Sized {
  56     fn finish(hasher: StableHasher<Self>) -> Self;
  57 }
  58
  59 impl<W: StableHasherResult> StableHasher<W> {
  60     pub fn new() -> Self {
  61         StableHasher {
  62             state: Blake2bHasher::new(mem::size_of::<W>(), &[]),
  63             bytes_hashed: 0,
  64             width: PhantomData,
  65         }
  66     }
  67
  68     pub fn finish(self) -> W {
  69         W::finish(self)
  70     }
  71 }
  72
  73 impl StableHasherResult for [u8; 20] {
  74     fn finish(mut hasher: StableHasher<Self>) -> Self {
  75         let mut result: [u8; 20] = [0; 20];
  76         result.copy_from_slice(hasher.state.finalize());
  77         result
  78     }
  79 }
  80
  81 impl StableHasherResult for u128 {
  82     fn finish(mut hasher: StableHasher<Self>) -> Self {
  83         let hash_bytes: &[u8] = hasher.finalize();
  84         assert!(hash_bytes.len() >= mem::size_of::<u128>());
  85
  86         unsafe {
  87             ::std::ptr::read_unaligned(hash_bytes.as_ptr() as *const u128)
  88         }
  89     }
  90 }
  91
  92 impl StableHasherResult for u64 {
  93     fn finish(mut hasher: StableHasher<Self>) -> Self {
  94         hasher.state.finalize();
  95         hasher.state.finish()
  96     }
  97 }
  98
  99 impl<W> StableHasher<W> {
 100     #[inline]
 101     pub fn finalize(&mut self) -> &[u8] {
 102         self.state.finalize()
 103     }
 104
 105     #[inline]
 106     pub fn bytes_hashed(&self) -> u64 {
 107         self.bytes_hashed
 108     }
 109
 110     #[inline]
 111     fn write_uleb128(&mut self, value: u64) {
 112         let mut buf = [0; 16];
 113         let len = write_unsigned_leb128_to_buf(&mut buf, value);
 114         self.state.write(&buf[..len]);
 115         self.bytes_hashed += len as u64;
 116     }
 117
 118     #[inline]
 119     fn write_ileb128(&mut self, value: i64) {
 120         let mut buf = [0; 16];
 121         let len = write_signed_leb128_to_buf(&mut buf, value);
 122         self.state.write(&buf[..len]);
 123         self.bytes_hashed += len as u64;
 124     }
 125 }
 126
 127 // For the non-u8 integer cases we leb128 encode them first. Because small
 128 // integers dominate, this significantly and cheaply reduces the number of
 129 // bytes hashed, which is good because blake2b is expensive.
 130 impl<W> Hasher for StableHasher<W> {
 131     fn finish(&self) -> u64 {
 132         panic!("use StableHasher::finish instead");
 133     }
 134
 135     #[inline]
 136     fn write(&mut self, bytes: &[u8]) {
 137         self.state.write(bytes);
 138         self.bytes_hashed += bytes.len() as u64;
 139     }
 140
 141     #[inline]
 142     fn write_u8(&mut self, i: u8) {
 143         self.state.write_u8(i);
 144         self.bytes_hashed += 1;
 145     }
 146
 147     #[inline]
 148     fn write_u16(&mut self, i: u16) {
 149         self.write_uleb128(i as u64);
 150     }
 151
 152     #[inline]
 153     fn write_u32(&mut self, i: u32) {
 154         self.write_uleb128(i as u64);
 155     }
 156
 157     #[inline]
 158     fn write_u64(&mut self, i: u64) {
 159         self.write_uleb128(i);
 160     }
 161
 162     #[inline]
 163     fn write_usize(&mut self, i: usize) {
 164         self.write_uleb128(i as u64);
 165     }
 166
 167     #[inline]
 168     fn write_i8(&mut self, i: i8) {
 169         self.state.write_i8(i);
 170         self.bytes_hashed += 1;
 171     }
 172
 173     #[inline]
 174     fn write_i16(&mut self, i: i16) {
 175         self.write_ileb128(i as i64);
 176     }
 177
 178     #[inline]
 179     fn write_i32(&mut self, i: i32) {
 180         self.write_ileb128(i as i64);
 181     }
 182
 183     #[inline]
 184     fn write_i64(&mut self, i: i64) {
 185         self.write_ileb128(i);
 186     }
 187
 188     #[inline]
 189     fn write_isize(&mut self, i: isize) {
 190         self.write_ileb128(i as i64);
 191     }
 192 }
 193
 194
 195 /// Something that can provide a stable hashing context.
 196 pub trait StableHashingContextProvider {
 197     type ContextType;
 198     fn create_stable_hashing_context(&self) -> Self::ContextType;
 199 }
 200
 201 impl<'a, T: StableHashingContextProvider> StableHashingContextProvider for &'a T {
 202     type ContextType = T::ContextType;
 203
 204     fn create_stable_hashing_context(&self) -> Self::ContextType {
 205         (**self).create_stable_hashing_context()
 206     }
 207 }
 208
 209 impl<'a, T: StableHashingContextProvider> StableHashingContextProvider for &'a mut T {
 210     type ContextType = T::ContextType;
 211
 212     fn create_stable_hashing_context(&self) -> Self::ContextType {
 213         (**self).create_stable_hashing_context()
 214     }
 215 }
 216
 217 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
 218 /// stable across multiple compilation sessions.
 219 pub trait HashStable<CTX> {
 220     fn hash_stable<W: StableHasherResult>(&self,
 221                                           hcx: &mut CTX,
 222                                           hasher: &mut StableHasher<W>);
 223 }
 224
 225 /// Implement this for types that can be turned into stable keys like, for
 226 /// example, for DefId that can be converted to a DefPathHash. This is used for
 227 /// bringing maps into a predictable order before hashing them.
 228 pub trait ToStableHashKey<HCX> {
 229     type KeyType: Ord + Clone + Sized + HashStable<HCX>;
 230     fn to_stable_hash_key(&self, hcx: &HCX) -> Self::KeyType;
 231 }
 232
 233 // Implement HashStable by just calling `Hash::hash()`. This works fine for
 234 // self-contained values that don't depend on the hashing context `CTX`.
 235 macro_rules! impl_stable_hash_via_hash {
 236     ($t:ty) => (
 237         impl<CTX> HashStable<CTX> for $t {
 238             #[inline]
 239             fn hash_stable<W: StableHasherResult>(&self,
 240                                                   _: &mut CTX,
 241                                                   hasher: &mut StableHasher<W>) {
 242                 ::std::hash::Hash::hash(self, hasher);
 243             }
 244         }
 245     );
 246 }
 247
 248 impl_stable_hash_via_hash!(i8);
 249 impl_stable_hash_via_hash!(i16);
 250 impl_stable_hash_via_hash!(i32);
 251 impl_stable_hash_via_hash!(i64);
 252 impl_stable_hash_via_hash!(isize);
 253
 254 impl_stable_hash_via_hash!(u8);
 255 impl_stable_hash_via_hash!(u16);
 256 impl_stable_hash_via_hash!(u32);
 257 impl_stable_hash_via_hash!(u64);
 258 impl_stable_hash_via_hash!(usize);
 259
 260 impl_stable_hash_via_hash!(u128);
 261 impl_stable_hash_via_hash!(i128);
 262
 263 impl_stable_hash_via_hash!(char);
 264 impl_stable_hash_via_hash!(());
 265
 266 impl<CTX> HashStable<CTX> for f32 {
 267     fn hash_stable<W: StableHasherResult>(&self,
 268                                           ctx: &mut CTX,
 269                                           hasher: &mut StableHasher<W>) {
 270         let val: u32 = unsafe {
 271             ::std::mem::transmute(*self)
 272         };
 273         val.hash_stable(ctx, hasher);
 274     }
 275 }
 276
 277 impl<CTX> HashStable<CTX> for f64 {
 278     fn hash_stable<W: StableHasherResult>(&self,
 279                                           ctx: &mut CTX,
 280                                           hasher: &mut StableHasher<W>) {
 281         let val: u64 = unsafe {
 282             ::std::mem::transmute(*self)
 283         };
 284         val.hash_stable(ctx, hasher);
 285     }
 286 }
 287
 288 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
 289     fn hash_stable<W: StableHasherResult>(&self,
 290                                           ctx: &mut CTX,
 291                                           hasher: &mut StableHasher<W>) {
 292         let (ref _0,) = *self;
 293         _0.hash_stable(ctx, hasher);
 294     }
 295 }
 296
 297 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
 298     fn hash_stable<W: StableHasherResult>(&self,
 299                                           ctx: &mut CTX,
 300                                           hasher: &mut StableHasher<W>) {
 301         let (ref _0, ref _1) = *self;
 302         _0.hash_stable(ctx, hasher);
 303         _1.hash_stable(ctx, hasher);
 304     }
 305 }
 306
 307 impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
 308      where T1: HashStable<CTX>,
 309            T2: HashStable<CTX>,
 310            T3: HashStable<CTX>,
 311 {
 312     fn hash_stable<W: StableHasherResult>(&self,
 313                                           ctx: &mut CTX,
 314                                           hasher: &mut StableHasher<W>) {
 315         let (ref _0, ref _1, ref _2) = *self;
 316         _0.hash_stable(ctx, hasher);
 317         _1.hash_stable(ctx, hasher);
 318         _2.hash_stable(ctx, hasher);
 319     }
 320 }
 321
 322 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
 323     default fn hash_stable<W: StableHasherResult>(&self,
 324                                                   ctx: &mut CTX,
 325                                                   hasher: &mut StableHasher<W>) {
 326         self.len().hash_stable(ctx, hasher);
 327         for item in self {
 328             item.hash_stable(ctx, hasher);
 329         }
 330     }
 331 }
 332
 333 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
 334     #[inline]
 335     fn hash_stable<W: StableHasherResult>(&self,
 336                                           ctx: &mut CTX,
 337                                           hasher: &mut StableHasher<W>) {
 338         (&self[..]).hash_stable(ctx, hasher);
 339     }
 340 }
 341
 342 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for Box<T> {
 343     #[inline]
 344     fn hash_stable<W: StableHasherResult>(&self,
 345                                           ctx: &mut CTX,
 346                                           hasher: &mut StableHasher<W>) {
 347         (**self).hash_stable(ctx, hasher);
 348     }
 349 }
 350
 351 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
 352     #[inline]
 353     fn hash_stable<W: StableHasherResult>(&self,
 354                                           ctx: &mut CTX,
 355                                           hasher: &mut StableHasher<W>) {
 356         (**self).hash_stable(ctx, hasher);
 357     }
 358 }
 359
 360 impl<T: ?Sized + HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
 361     #[inline]
 362     fn hash_stable<W: StableHasherResult>(&self,
 363                                           ctx: &mut CTX,
 364                                           hasher: &mut StableHasher<W>) {
 365         (**self).hash_stable(ctx, hasher);
 366     }
 367 }
 368
 369 impl<CTX> HashStable<CTX> for str {
 370     #[inline]
 371     fn hash_stable<W: StableHasherResult>(&self,
 372                                           _: &mut CTX,
 373                                           hasher: &mut StableHasher<W>) {
 374         self.len().hash(hasher);
 375         self.as_bytes().hash(hasher);
 376     }
 377 }
 378
 379
 380 impl<CTX> HashStable<CTX> for String {
 381     #[inline]
 382     fn hash_stable<W: StableHasherResult>(&self,
 383                                           hcx: &mut CTX,
 384                                           hasher: &mut StableHasher<W>) {
 385         (&self[..]).hash_stable(hcx, hasher);
 386     }
 387 }
 388
 389 impl<HCX> ToStableHashKey<HCX> for String {
 390     type KeyType = String;
 391     #[inline]
 392     fn to_stable_hash_key(&self, _: &HCX) -> Self::KeyType {
 393         self.clone()
 394     }
 395 }
 396
 397 impl<CTX> HashStable<CTX> for bool {
 398     #[inline]
 399     fn hash_stable<W: StableHasherResult>(&self,
 400                                           ctx: &mut CTX,
 401                                           hasher: &mut StableHasher<W>) {
 402         (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
 403     }
 404 }
 405
 406
 407 impl<T, CTX> HashStable<CTX> for Option<T>
 408     where T: HashStable<CTX>
 409 {
 410     #[inline]
 411     fn hash_stable<W: StableHasherResult>(&self,
 412                                           ctx: &mut CTX,
 413                                           hasher: &mut StableHasher<W>) {
 414         if let Some(ref value) = *self {
 415             1u8.hash_stable(ctx, hasher);
 416             value.hash_stable(ctx, hasher);
 417         } else {
 418             0u8.hash_stable(ctx, hasher);
 419         }
 420     }
 421 }
 422
 423 impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
 424     where T1: HashStable<CTX>,
 425           T2: HashStable<CTX>,
 426 {
 427     #[inline]
 428     fn hash_stable<W: StableHasherResult>(&self,
 429                                           ctx: &mut CTX,
 430                                           hasher: &mut StableHasher<W>) {
 431         mem::discriminant(self).hash_stable(ctx, hasher);
 432         match *self {
 433             Ok(ref x) => x.hash_stable(ctx, hasher),
 434             Err(ref x) => x.hash_stable(ctx, hasher),
 435         }
 436     }
 437 }
 438
 439 impl<'a, T, CTX> HashStable<CTX> for &'a T
 440     where T: HashStable<CTX> + ?Sized
 441 {
 442     #[inline]
 443     fn hash_stable<W: StableHasherResult>(&self,
 444                                           ctx: &mut CTX,
 445                                           hasher: &mut StableHasher<W>) {
 446         (**self).hash_stable(ctx, hasher);
 447     }
 448 }
 449
 450 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
 451     #[inline]
 452     fn hash_stable<W: StableHasherResult>(&self,
 453                                           _: &mut CTX,
 454                                           hasher: &mut StableHasher<W>) {
 455         ::std::hash::Hash::hash(self, hasher);
 456     }
 457 }
 458
 459 impl<I: ::indexed_vec::Idx, T, CTX> HashStable<CTX> for ::indexed_vec::IndexVec<I, T>
 460     where T: HashStable<CTX>,
 461 {
 462     fn hash_stable<W: StableHasherResult>(&self,
 463                                           ctx: &mut CTX,
 464                                           hasher: &mut StableHasher<W>) {
 465         self.len().hash_stable(ctx, hasher);
 466         for v in &self.raw {
 467             v.hash_stable(ctx, hasher);
 468         }
 469     }
 470 }
 471
 472
 473 impl<I: ::indexed_vec::Idx, CTX> HashStable<CTX> for ::indexed_set::IdxSetBuf<I>
 474 {
 475     fn hash_stable<W: StableHasherResult>(&self,
 476                                           ctx: &mut CTX,
 477                                           hasher: &mut StableHasher<W>) {
 478         self.words().hash_stable(ctx, hasher);
 479     }
 480 }
 481
 482 impl_stable_hash_via_hash!(::std::path::Path);
 483 impl_stable_hash_via_hash!(::std::path::PathBuf);
 484
 485 impl<K, V, R, HCX> HashStable<HCX> for ::std::collections::HashMap<K, V, R>
 486     where K: ToStableHashKey<HCX> + Eq + Hash,
 487           V: HashStable<HCX>,
 488           R: BuildHasher,
 489 {
 490     #[inline]
 491     fn hash_stable<W: StableHasherResult>(&self,
 492                                           hcx: &mut HCX,
 493                                           hasher: &mut StableHasher<W>) {
 494         hash_stable_hashmap(hcx, hasher, self, ToStableHashKey::to_stable_hash_key);
 495     }
 496 }
 497
 498 impl<K, R, HCX> HashStable<HCX> for ::std::collections::HashSet<K, R>
 499     where K: ToStableHashKey<HCX> + Eq + Hash,
 500           R: BuildHasher,
 501 {
 502     fn hash_stable<W: StableHasherResult>(&self,
 503                                           hcx: &mut HCX,
 504                                           hasher: &mut StableHasher<W>) {
 505         let mut keys: Vec<_> = self.iter()
 506                                    .map(|k| k.to_stable_hash_key(hcx))
 507                                    .collect();
 508         keys.sort_unstable();
 509         keys.hash_stable(hcx, hasher);
 510     }
 511 }
 512
 513 impl<K, V, HCX> HashStable<HCX> for ::std::collections::BTreeMap<K, V>
 514     where K: ToStableHashKey<HCX>,
 515           V: HashStable<HCX>,
 516 {
 517     fn hash_stable<W: StableHasherResult>(&self,
 518                                           hcx: &mut HCX,
 519                                           hasher: &mut StableHasher<W>) {
 520         let mut entries: Vec<_> = self.iter()
 521                                       .map(|(k, v)| (k.to_stable_hash_key(hcx), v))
 522                                       .collect();
 523         entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 524         entries.hash_stable(hcx, hasher);
 525     }
 526 }
 527
 528 impl<K, HCX> HashStable<HCX> for ::std::collections::BTreeSet<K>
 529     where K: ToStableHashKey<HCX>,
 530 {
 531     fn hash_stable<W: StableHasherResult>(&self,
 532                                           hcx: &mut HCX,
 533                                           hasher: &mut StableHasher<W>) {
 534         let mut keys: Vec<_> = self.iter()
 535                                    .map(|k| k.to_stable_hash_key(hcx))
 536                                    .collect();
 537         keys.sort_unstable();
 538         keys.hash_stable(hcx, hasher);
 539     }
 540 }
 541
 542 pub fn hash_stable_hashmap<HCX, K, V, R, SK, F, W>(
 543     hcx: &mut HCX,
 544     hasher: &mut StableHasher<W>,
 545     map: &::std::collections::HashMap<K, V, R>,
 546     to_stable_hash_key: F)
 547     where K: Eq + Hash,
 548           V: HashStable<HCX>,
 549           R: BuildHasher,
 550           SK: HashStable<HCX> + Ord + Clone,
 551           F: Fn(&K, &HCX) -> SK,
 552           W: StableHasherResult,
 553 {
 554     let mut entries: Vec<_> = map.iter()
 555                                   .map(|(k, v)| (to_stable_hash_key(k, hcx), v))
 556                                   .collect();
 557     entries.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
 558     entries.hash_stable(hcx, hasher);
 559 }
 560
 561
 562 /// A vector container that makes sure that its items are hashed in a stable
 563 /// order.
 564 pub struct StableVec<T>(Vec<T>);
 565
 566 impl<T> StableVec<T> {
 567     pub fn new(v: Vec<T>) -> Self {
 568         StableVec(v)
 569     }
 570 }
 571
 572 impl<T> ::std::ops::Deref for StableVec<T> {
 573     type Target = Vec<T>;
 574
 575     fn deref(&self) -> &Vec<T> {
 576         &self.0
 577     }
 578 }
 579
 580 impl<T, HCX> HashStable<HCX> for StableVec<T>
 581     where T: HashStable<HCX> + ToStableHashKey<HCX>
 582 {
 583     fn hash_stable<W: StableHasherResult>(&self,
 584                                           hcx: &mut HCX,
 585                                           hasher: &mut StableHasher<W>) {
 586         let StableVec(ref v) = *self;
 587
 588         let mut sorted: Vec<_> = v.iter()
 589                                   .map(|x| x.to_stable_hash_key(hcx))
 590                                   .collect();
 591         sorted.sort_unstable();
 592         sorted.hash_stable(hcx, hasher);
 593     }
 594 }