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};
  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 u64 {
  82     fn finish(mut hasher: StableHasher<Self>) -> Self {
  83         hasher.state.finalize();
  84         hasher.state.finish()
  85     }
  86 }
  87
  88 impl<W> StableHasher<W> {
  89     #[inline]
  90     pub fn finalize(&mut self) -> &[u8] {
  91         self.state.finalize()
  92     }
  93
  94     #[inline]
  95     pub fn bytes_hashed(&self) -> u64 {
  96         self.bytes_hashed
  97     }
  98
  99     #[inline]
 100     fn write_uleb128(&mut self, value: u64) {
 101         let mut buf = [0; 16];
 102         let len = write_unsigned_leb128_to_buf(&mut buf, value);
 103         self.state.write(&buf[..len]);
 104         self.bytes_hashed += len as u64;
 105     }
 106
 107     #[inline]
 108     fn write_ileb128(&mut self, value: i64) {
 109         let mut buf = [0; 16];
 110         let len = write_signed_leb128_to_buf(&mut buf, value);
 111         self.state.write(&buf[..len]);
 112         self.bytes_hashed += len as u64;
 113     }
 114 }
 115
 116 // For the non-u8 integer cases we leb128 encode them first. Because small
 117 // integers dominate, this significantly and cheaply reduces the number of
 118 // bytes hashed, which is good because blake2b is expensive.
 119 impl<W> Hasher for StableHasher<W> {
 120     fn finish(&self) -> u64 {
 121         panic!("use StableHasher::finish instead");
 122     }
 123
 124     #[inline]
 125     fn write(&mut self, bytes: &[u8]) {
 126         self.state.write(bytes);
 127         self.bytes_hashed += bytes.len() as u64;
 128     }
 129
 130     #[inline]
 131     fn write_u8(&mut self, i: u8) {
 132         self.state.write_u8(i);
 133         self.bytes_hashed += 1;
 134     }
 135
 136     #[inline]
 137     fn write_u16(&mut self, i: u16) {
 138         self.write_uleb128(i as u64);
 139     }
 140
 141     #[inline]
 142     fn write_u32(&mut self, i: u32) {
 143         self.write_uleb128(i as u64);
 144     }
 145
 146     #[inline]
 147     fn write_u64(&mut self, i: u64) {
 148         self.write_uleb128(i);
 149     }
 150
 151     #[inline]
 152     fn write_usize(&mut self, i: usize) {
 153         self.write_uleb128(i as u64);
 154     }
 155
 156     #[inline]
 157     fn write_i8(&mut self, i: i8) {
 158         self.state.write_i8(i);
 159         self.bytes_hashed += 1;
 160     }
 161
 162     #[inline]
 163     fn write_i16(&mut self, i: i16) {
 164         self.write_ileb128(i as i64);
 165     }
 166
 167     #[inline]
 168     fn write_i32(&mut self, i: i32) {
 169         self.write_ileb128(i as i64);
 170     }
 171
 172     #[inline]
 173     fn write_i64(&mut self, i: i64) {
 174         self.write_ileb128(i);
 175     }
 176
 177     #[inline]
 178     fn write_isize(&mut self, i: isize) {
 179         self.write_ileb128(i as i64);
 180     }
 181 }
 182
 183
 184 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
 185 /// stable across multiple compiliation sessions.
 186 pub trait HashStable<CTX> {
 187     fn hash_stable<W: StableHasherResult>(&self,
 188                                           hcx: &mut CTX,
 189                                           hasher: &mut StableHasher<W>);
 190 }
 191
 192 // Implement HashStable by just calling `Hash::hash()`. This works fine for
 193 // self-contained values that don't depend on the hashing context `CTX`.
 194 macro_rules! impl_stable_hash_via_hash {
 195     ($t:ty) => (
 196         impl<CTX> HashStable<CTX> for $t {
 197             #[inline]
 198             fn hash_stable<W: StableHasherResult>(&self,
 199                                                   _: &mut CTX,
 200                                                   hasher: &mut StableHasher<W>) {
 201                 ::std::hash::Hash::hash(self, hasher);
 202             }
 203         }
 204     );
 205 }
 206
 207 impl_stable_hash_via_hash!(i8);
 208 impl_stable_hash_via_hash!(i16);
 209 impl_stable_hash_via_hash!(i32);
 210 impl_stable_hash_via_hash!(i64);
 211 impl_stable_hash_via_hash!(isize);
 212
 213 impl_stable_hash_via_hash!(u8);
 214 impl_stable_hash_via_hash!(u16);
 215 impl_stable_hash_via_hash!(u32);
 216 impl_stable_hash_via_hash!(u64);
 217 impl_stable_hash_via_hash!(usize);
 218
 219 impl_stable_hash_via_hash!(u128);
 220 impl_stable_hash_via_hash!(i128);
 221
 222 impl_stable_hash_via_hash!(char);
 223 impl_stable_hash_via_hash!(());
 224
 225 impl<CTX> HashStable<CTX> for f32 {
 226     fn hash_stable<W: StableHasherResult>(&self,
 227                                           ctx: &mut CTX,
 228                                           hasher: &mut StableHasher<W>) {
 229         let val: u32 = unsafe {
 230             ::std::mem::transmute(*self)
 231         };
 232         val.hash_stable(ctx, hasher);
 233     }
 234 }
 235
 236 impl<CTX> HashStable<CTX> for f64 {
 237     fn hash_stable<W: StableHasherResult>(&self,
 238                                           ctx: &mut CTX,
 239                                           hasher: &mut StableHasher<W>) {
 240         let val: u64 = unsafe {
 241             ::std::mem::transmute(*self)
 242         };
 243         val.hash_stable(ctx, hasher);
 244     }
 245 }
 246
 247 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
 248     fn hash_stable<W: StableHasherResult>(&self,
 249                                           ctx: &mut CTX,
 250                                           hasher: &mut StableHasher<W>) {
 251         self.0.hash_stable(ctx, hasher);
 252         self.1.hash_stable(ctx, hasher);
 253     }
 254 }
 255
 256 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
 257     default fn hash_stable<W: StableHasherResult>(&self,
 258                                                   ctx: &mut CTX,
 259                                                   hasher: &mut StableHasher<W>) {
 260         self.len().hash_stable(ctx, hasher);
 261         for item in self {
 262             item.hash_stable(ctx, hasher);
 263         }
 264     }
 265 }
 266
 267 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
 268     #[inline]
 269     fn hash_stable<W: StableHasherResult>(&self,
 270                                           ctx: &mut CTX,
 271                                           hasher: &mut StableHasher<W>) {
 272         (&self[..]).hash_stable(ctx, hasher);
 273     }
 274 }
 275
 276 impl<CTX> HashStable<CTX> for str {
 277     #[inline]
 278     fn hash_stable<W: StableHasherResult>(&self,
 279                                           _: &mut CTX,
 280                                           hasher: &mut StableHasher<W>) {
 281         self.len().hash(hasher);
 282         self.as_bytes().hash(hasher);
 283     }
 284 }
 285
 286 impl<CTX> HashStable<CTX> for bool {
 287     #[inline]
 288     fn hash_stable<W: StableHasherResult>(&self,
 289                                           ctx: &mut CTX,
 290                                           hasher: &mut StableHasher<W>) {
 291         (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
 292     }
 293 }
 294
 295
 296 impl<T, CTX> HashStable<CTX> for Option<T>
 297     where T: HashStable<CTX>
 298 {
 299     #[inline]
 300     fn hash_stable<W: StableHasherResult>(&self,
 301                                           ctx: &mut CTX,
 302                                           hasher: &mut StableHasher<W>) {
 303         if let Some(ref value) = *self {
 304             1u8.hash_stable(ctx, hasher);
 305             value.hash_stable(ctx, hasher);
 306         } else {
 307             0u8.hash_stable(ctx, hasher);
 308         }
 309     }
 310 }
 311
 312 impl<'a, T, CTX> HashStable<CTX> for &'a T
 313     where T: HashStable<CTX>
 314 {
 315     #[inline]
 316     fn hash_stable<W: StableHasherResult>(&self,
 317                                           ctx: &mut CTX,
 318                                           hasher: &mut StableHasher<W>) {
 319         (**self).hash_stable(ctx, hasher);
 320     }
 321 }
 322
 323 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
 324     #[inline]
 325     fn hash_stable<W: StableHasherResult>(&self,
 326                                           _: &mut CTX,
 327                                           hasher: &mut StableHasher<W>) {
 328         ::std::hash::Hash::hash(self, hasher);
 329     }
 330 }
 331
 332 impl<K, V, CTX> HashStable<CTX> for ::std::collections::BTreeMap<K, V>
 333     where K: Ord + HashStable<CTX>,
 334           V: HashStable<CTX>,
 335 {
 336     fn hash_stable<W: StableHasherResult>(&self,
 337                                           ctx: &mut CTX,
 338                                           hasher: &mut StableHasher<W>) {
 339         self.len().hash_stable(ctx, hasher);
 340         for (k, v) in self {
 341             k.hash_stable(ctx, hasher);
 342             v.hash_stable(ctx, hasher);
 343         }
 344     }
 345 }
 346
 347 impl<T, CTX> HashStable<CTX> for ::std::collections::BTreeSet<T>
 348     where T: Ord + HashStable<CTX>,
 349 {
 350     fn hash_stable<W: StableHasherResult>(&self,
 351                                           ctx: &mut CTX,
 352                                           hasher: &mut StableHasher<W>) {
 353         self.len().hash_stable(ctx, hasher);
 354         for v in self {
 355             v.hash_stable(ctx, hasher);
 356         }
 357     }
 358 }
 359
 360 impl<I: ::indexed_vec::Idx, T, CTX> HashStable<CTX> for ::indexed_vec::IndexVec<I, T>
 361     where T: HashStable<CTX>,
 362 {
 363     fn hash_stable<W: StableHasherResult>(&self,
 364                                           ctx: &mut CTX,
 365                                           hasher: &mut StableHasher<W>) {
 366         self.len().hash_stable(ctx, hasher);
 367         for v in &self.raw {
 368             v.hash_stable(ctx, hasher);
 369         }
 370     }
 371 }