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.
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.
11 use std::hash::{Hash, Hasher};
12 use std::marker::PhantomData;
14 use blake2b::Blake2bHasher;
15 use rustc_serialize::leb128;
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)
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)
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*.
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.
34 /// To do that, we encode all integers to be hashed with some
35 /// arch-independent encoding.
37 /// At the moment, we pass i8/u8 straight through and encode
38 /// all other integers using leb128.
40 /// This hasher currently always uses the stable Blake2b algorithm
41 /// and allows for variable output lengths through its type
43 pub struct StableHasher<W> {
46 width: PhantomData<W>,
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)
55 pub trait StableHasherResult: Sized {
56 fn finish(hasher: StableHasher<Self>) -> Self;
59 impl<W: StableHasherResult> StableHasher<W> {
60 pub fn new() -> Self {
62 state: Blake2bHasher::new(mem::size_of::<W>(), &[]),
68 pub fn finish(self) -> W {
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());
81 impl StableHasherResult for u64 {
82 fn finish(mut hasher: StableHasher<Self>) -> Self {
83 hasher.state.finalize();
88 impl<W> StableHasher<W> {
90 pub fn finalize(&mut self) -> &[u8] {
95 pub fn bytes_hashed(&self) -> u64 {
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;
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;
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");
125 fn write(&mut self, bytes: &[u8]) {
126 self.state.write(bytes);
127 self.bytes_hashed += bytes.len() as u64;
131 fn write_u8(&mut self, i: u8) {
132 self.state.write_u8(i);
133 self.bytes_hashed += 1;
137 fn write_u16(&mut self, i: u16) {
138 self.write_uleb128(i as u64);
142 fn write_u32(&mut self, i: u32) {
143 self.write_uleb128(i as u64);
147 fn write_u64(&mut self, i: u64) {
148 self.write_uleb128(i);
152 fn write_usize(&mut self, i: usize) {
153 self.write_uleb128(i as u64);
157 fn write_i8(&mut self, i: i8) {
158 self.state.write_i8(i);
159 self.bytes_hashed += 1;
163 fn write_i16(&mut self, i: i16) {
164 self.write_ileb128(i as i64);
168 fn write_i32(&mut self, i: i32) {
169 self.write_ileb128(i as i64);
173 fn write_i64(&mut self, i: i64) {
174 self.write_ileb128(i);
178 fn write_isize(&mut self, i: isize) {
179 self.write_ileb128(i as i64);
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,
189 hasher: &mut StableHasher<W>);
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 {
196 impl<CTX> HashStable<CTX> for $t {
198 fn hash_stable<W: StableHasherResult>(&self,
200 hasher: &mut StableHasher<W>) {
201 ::std::hash::Hash::hash(self, hasher);
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);
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);
219 impl_stable_hash_via_hash!(u128);
220 impl_stable_hash_via_hash!(i128);
222 impl_stable_hash_via_hash!(char);
223 impl_stable_hash_via_hash!(());
225 impl<CTX> HashStable<CTX> for f32 {
226 fn hash_stable<W: StableHasherResult>(&self,
228 hasher: &mut StableHasher<W>) {
229 let val: u32 = unsafe {
230 ::std::mem::transmute(*self)
232 val.hash_stable(ctx, hasher);
236 impl<CTX> HashStable<CTX> for f64 {
237 fn hash_stable<W: StableHasherResult>(&self,
239 hasher: &mut StableHasher<W>) {
240 let val: u64 = unsafe {
241 ::std::mem::transmute(*self)
243 val.hash_stable(ctx, hasher);
247 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
248 fn hash_stable<W: StableHasherResult>(&self,
250 hasher: &mut StableHasher<W>) {
251 self.0.hash_stable(ctx, hasher);
252 self.1.hash_stable(ctx, hasher);
256 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
257 default fn hash_stable<W: StableHasherResult>(&self,
259 hasher: &mut StableHasher<W>) {
260 self.len().hash_stable(ctx, hasher);
262 item.hash_stable(ctx, hasher);
267 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
269 fn hash_stable<W: StableHasherResult>(&self,
271 hasher: &mut StableHasher<W>) {
272 (&self[..]).hash_stable(ctx, hasher);
276 impl<CTX> HashStable<CTX> for str {
278 fn hash_stable<W: StableHasherResult>(&self,
280 hasher: &mut StableHasher<W>) {
281 self.len().hash(hasher);
282 self.as_bytes().hash(hasher);
286 impl<CTX> HashStable<CTX> for bool {
288 fn hash_stable<W: StableHasherResult>(&self,
290 hasher: &mut StableHasher<W>) {
291 (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
296 impl<T, CTX> HashStable<CTX> for Option<T>
297 where T: HashStable<CTX>
300 fn hash_stable<W: StableHasherResult>(&self,
302 hasher: &mut StableHasher<W>) {
303 if let Some(ref value) = *self {
304 1u8.hash_stable(ctx, hasher);
305 value.hash_stable(ctx, hasher);
307 0u8.hash_stable(ctx, hasher);
312 impl<'a, T, CTX> HashStable<CTX> for &'a T
313 where T: HashStable<CTX>
316 fn hash_stable<W: StableHasherResult>(&self,
318 hasher: &mut StableHasher<W>) {
319 (**self).hash_stable(ctx, hasher);
323 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
325 fn hash_stable<W: StableHasherResult>(&self,
327 hasher: &mut StableHasher<W>) {
328 ::std::hash::Hash::hash(self, hasher);
332 impl<K, V, CTX> HashStable<CTX> for ::std::collections::BTreeMap<K, V>
333 where K: Ord + HashStable<CTX>,
336 fn hash_stable<W: StableHasherResult>(&self,
338 hasher: &mut StableHasher<W>) {
339 self.len().hash_stable(ctx, hasher);
341 k.hash_stable(ctx, hasher);
342 v.hash_stable(ctx, hasher);
347 impl<T, CTX> HashStable<CTX> for ::std::collections::BTreeSet<T>
348 where T: Ord + HashStable<CTX>,
350 fn hash_stable<W: StableHasherResult>(&self,
352 hasher: &mut StableHasher<W>) {
353 self.len().hash_stable(ctx, hasher);
355 v.hash_stable(ctx, hasher);
360 impl<I: ::indexed_vec::Idx, T, CTX> HashStable<CTX> for ::indexed_vec::IndexVec<I, T>
361 where T: HashStable<CTX>,
363 fn hash_stable<W: StableHasherResult>(&self,
365 hasher: &mut StableHasher<W>) {
366 self.len().hash_stable(ctx, hasher);
368 v.hash_stable(ctx, hasher);