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