]> git.lizzy.rs Git - rust.git/blob - src/librustc_data_structures/stable_hasher.rs
Rollup merge of #42496 - Razaekel:feature/integer_max-min, r=BurntSushi
[rust.git] / 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>, CTX> HashStable<CTX> for (T1,) {
248     fn hash_stable<W: StableHasherResult>(&self,
249                                           ctx: &mut CTX,
250                                           hasher: &mut StableHasher<W>) {
251         self.0.hash_stable(ctx, hasher);
252     }
253 }
254
255 impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
256     fn hash_stable<W: StableHasherResult>(&self,
257                                           ctx: &mut CTX,
258                                           hasher: &mut StableHasher<W>) {
259         self.0.hash_stable(ctx, hasher);
260         self.1.hash_stable(ctx, hasher);
261     }
262 }
263
264 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
265     default fn hash_stable<W: StableHasherResult>(&self,
266                                                   ctx: &mut CTX,
267                                                   hasher: &mut StableHasher<W>) {
268         self.len().hash_stable(ctx, hasher);
269         for item in self {
270             item.hash_stable(ctx, hasher);
271         }
272     }
273 }
274
275 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
276     #[inline]
277     fn hash_stable<W: StableHasherResult>(&self,
278                                           ctx: &mut CTX,
279                                           hasher: &mut StableHasher<W>) {
280         (&self[..]).hash_stable(ctx, hasher);
281     }
282 }
283
284 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for ::std::rc::Rc<T> {
285     #[inline]
286     fn hash_stable<W: StableHasherResult>(&self,
287                                           ctx: &mut CTX,
288                                           hasher: &mut StableHasher<W>) {
289         (**self).hash_stable(ctx, hasher);
290     }
291 }
292
293 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for ::std::sync::Arc<T> {
294     #[inline]
295     fn hash_stable<W: StableHasherResult>(&self,
296                                           ctx: &mut CTX,
297                                           hasher: &mut StableHasher<W>) {
298         (**self).hash_stable(ctx, hasher);
299     }
300 }
301
302 impl<CTX> HashStable<CTX> for str {
303     #[inline]
304     fn hash_stable<W: StableHasherResult>(&self,
305                                           _: &mut CTX,
306                                           hasher: &mut StableHasher<W>) {
307         self.len().hash(hasher);
308         self.as_bytes().hash(hasher);
309     }
310 }
311
312
313 impl<CTX> HashStable<CTX> for String {
314     #[inline]
315     fn hash_stable<W: StableHasherResult>(&self,
316                                           hcx: &mut CTX,
317                                           hasher: &mut StableHasher<W>) {
318         (&self[..]).hash_stable(hcx, hasher);
319     }
320 }
321
322 impl<CTX> HashStable<CTX> for bool {
323     #[inline]
324     fn hash_stable<W: StableHasherResult>(&self,
325                                           ctx: &mut CTX,
326                                           hasher: &mut StableHasher<W>) {
327         (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
328     }
329 }
330
331
332 impl<T, CTX> HashStable<CTX> for Option<T>
333     where T: HashStable<CTX>
334 {
335     #[inline]
336     fn hash_stable<W: StableHasherResult>(&self,
337                                           ctx: &mut CTX,
338                                           hasher: &mut StableHasher<W>) {
339         if let Some(ref value) = *self {
340             1u8.hash_stable(ctx, hasher);
341             value.hash_stable(ctx, hasher);
342         } else {
343             0u8.hash_stable(ctx, hasher);
344         }
345     }
346 }
347
348 impl<'a, T, CTX> HashStable<CTX> for &'a T
349     where T: HashStable<CTX>
350 {
351     #[inline]
352     fn hash_stable<W: StableHasherResult>(&self,
353                                           ctx: &mut CTX,
354                                           hasher: &mut StableHasher<W>) {
355         (**self).hash_stable(ctx, hasher);
356     }
357 }
358
359 impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
360     #[inline]
361     fn hash_stable<W: StableHasherResult>(&self,
362                                           _: &mut CTX,
363                                           hasher: &mut StableHasher<W>) {
364         ::std::hash::Hash::hash(self, hasher);
365     }
366 }
367
368 impl<K, V, CTX> HashStable<CTX> for ::std::collections::BTreeMap<K, V>
369     where K: Ord + HashStable<CTX>,
370           V: HashStable<CTX>,
371 {
372     fn hash_stable<W: StableHasherResult>(&self,
373                                           ctx: &mut CTX,
374                                           hasher: &mut StableHasher<W>) {
375         self.len().hash_stable(ctx, hasher);
376         for (k, v) in self {
377             k.hash_stable(ctx, hasher);
378             v.hash_stable(ctx, hasher);
379         }
380     }
381 }
382
383 impl<T, CTX> HashStable<CTX> for ::std::collections::BTreeSet<T>
384     where T: Ord + HashStable<CTX>,
385 {
386     fn hash_stable<W: StableHasherResult>(&self,
387                                           ctx: &mut CTX,
388                                           hasher: &mut StableHasher<W>) {
389         self.len().hash_stable(ctx, hasher);
390         for v in self {
391             v.hash_stable(ctx, hasher);
392         }
393     }
394 }
395
396 impl<I: ::indexed_vec::Idx, T, CTX> HashStable<CTX> for ::indexed_vec::IndexVec<I, T>
397     where T: HashStable<CTX>,
398 {
399     fn hash_stable<W: StableHasherResult>(&self,
400                                           ctx: &mut CTX,
401                                           hasher: &mut StableHasher<W>) {
402         self.len().hash_stable(ctx, hasher);
403         for v in &self.raw {
404             v.hash_stable(ctx, hasher);
405         }
406     }
407 }