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, BuildHasher}
;
12 use std
::marker
::PhantomData
;
14 use sip128
::SipHasher128
;
16 /// When hashing something that ends up affecting properties like symbol names,
17 /// we want these symbol names to be calculated independently of other factors
18 /// like what architecture you're compiling *from*.
20 /// To that end we always convert integers to little-endian format before
21 /// hashing and the architecture dependent `isize` and `usize` types are
22 /// extended to 64 bits if needed.
23 pub struct StableHasher
<W
> {
26 width
: PhantomData
<W
>,
29 impl<W
: StableHasherResult
> ::std
::fmt
::Debug
for StableHasher
<W
> {
30 fn fmt(&self, f
: &mut ::std
::fmt
::Formatter
) -> ::std
::fmt
::Result
{
31 write
!(f
, "{:?}", self.state
)
35 pub trait StableHasherResult
: Sized
{
36 fn finish(hasher
: StableHasher
<Self>) -> Self;
39 impl<W
: StableHasherResult
> StableHasher
<W
> {
40 pub fn new() -> Self {
42 state
: SipHasher128
::new_with_keys(0, 0),
48 pub fn finish(self) -> W
{
53 impl StableHasherResult
for u128
{
54 fn finish(hasher
: StableHasher
<Self>) -> Self {
55 let (_0
, _1
) = hasher
.finalize();
56 (_0
as u128
) | ((_1
as u128
) << 64)
60 impl StableHasherResult
for u64 {
61 fn finish(hasher
: StableHasher
<Self>) -> Self {
66 impl<W
> StableHasher
<W
> {
68 pub fn finalize(self) -> (u64, u64) {
69 self.state
.finish128()
73 pub fn bytes_hashed(&self) -> u64 {
78 impl<W
> Hasher
for StableHasher
<W
> {
79 fn finish(&self) -> u64 {
80 panic
!("use StableHasher::finalize instead");
84 fn write(&mut self, bytes
: &[u8]) {
85 self.state
.write(bytes
);
86 self.bytes_hashed
+= bytes
.len() as u64;
90 fn write_u8(&mut self, i
: u8) {
91 self.state
.write_u8(i
);
92 self.bytes_hashed
+= 1;
96 fn write_u16(&mut self, i
: u16) {
97 self.state
.write_u16(i
.to_le());
98 self.bytes_hashed
+= 2;
102 fn write_u32(&mut self, i
: u32) {
103 self.state
.write_u32(i
.to_le());
104 self.bytes_hashed
+= 4;
108 fn write_u64(&mut self, i
: u64) {
109 self.state
.write_u64(i
.to_le());
110 self.bytes_hashed
+= 8;
114 fn write_u128(&mut self, i
: u128
) {
115 self.state
.write_u128(i
.to_le());
116 self.bytes_hashed
+= 16;
120 fn write_usize(&mut self, i
: usize) {
121 // Always treat usize as u64 so we get the same results on 32 and 64 bit
122 // platforms. This is important for symbol hashes when cross compiling,
124 self.state
.write_u64((i
as u64).to_le());
125 self.bytes_hashed
+= 8;
129 fn write_i8(&mut self, i
: i8) {
130 self.state
.write_i8(i
);
131 self.bytes_hashed
+= 1;
135 fn write_i16(&mut self, i
: i16) {
136 self.state
.write_i16(i
.to_le());
137 self.bytes_hashed
+= 2;
141 fn write_i32(&mut self, i
: i32) {
142 self.state
.write_i32(i
.to_le());
143 self.bytes_hashed
+= 4;
147 fn write_i64(&mut self, i
: i64) {
148 self.state
.write_i64(i
.to_le());
149 self.bytes_hashed
+= 8;
153 fn write_i128(&mut self, i
: i128
) {
154 self.state
.write_i128(i
.to_le());
155 self.bytes_hashed
+= 16;
159 fn write_isize(&mut self, i
: isize) {
160 // Always treat isize as i64 so we get the same results on 32 and 64 bit
161 // platforms. This is important for symbol hashes when cross compiling,
163 self.state
.write_i64((i
as i64).to_le());
164 self.bytes_hashed
+= 8;
168 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
169 /// stable across multiple compilation sessions.
170 pub trait HashStable
<CTX
> {
171 fn hash_stable
<W
: StableHasherResult
>(&self,
173 hasher
: &mut StableHasher
<W
>);
176 /// Implement this for types that can be turned into stable keys like, for
177 /// example, for DefId that can be converted to a DefPathHash. This is used for
178 /// bringing maps into a predictable order before hashing them.
179 pub trait ToStableHashKey
<HCX
> {
180 type KeyType
: Ord
+ Clone
+ Sized
+ HashStable
<HCX
>;
181 fn to_stable_hash_key(&self, hcx
: &HCX
) -> Self::KeyType
;
184 // Implement HashStable by just calling `Hash::hash()`. This works fine for
185 // self-contained values that don't depend on the hashing context `CTX`.
186 macro_rules
! impl_stable_hash_via_hash
{
188 impl<CTX
> HashStable
<CTX
> for $t
{
190 fn hash_stable
<W
: StableHasherResult
>(&self,
192 hasher
: &mut StableHasher
<W
>) {
193 ::std
::hash
::Hash
::hash(self, hasher
);
199 impl_stable_hash_via_hash
!(i8);
200 impl_stable_hash_via_hash
!(i16);
201 impl_stable_hash_via_hash
!(i32);
202 impl_stable_hash_via_hash
!(i64);
203 impl_stable_hash_via_hash
!(isize);
205 impl_stable_hash_via_hash
!(u8);
206 impl_stable_hash_via_hash
!(u16);
207 impl_stable_hash_via_hash
!(u32);
208 impl_stable_hash_via_hash
!(u64);
209 impl_stable_hash_via_hash
!(usize);
211 impl_stable_hash_via_hash
!(u128
);
212 impl_stable_hash_via_hash
!(i128
);
214 impl_stable_hash_via_hash
!(char);
215 impl_stable_hash_via_hash
!(());
217 impl<CTX
> HashStable
<CTX
> for f32 {
218 fn hash_stable
<W
: StableHasherResult
>(&self,
220 hasher
: &mut StableHasher
<W
>) {
221 let val
: u32 = unsafe {
222 ::std
::mem
::transmute(*self)
224 val
.hash_stable(ctx
, hasher
);
228 impl<CTX
> HashStable
<CTX
> for f64 {
229 fn hash_stable
<W
: StableHasherResult
>(&self,
231 hasher
: &mut StableHasher
<W
>) {
232 let val
: u64 = unsafe {
233 ::std
::mem
::transmute(*self)
235 val
.hash_stable(ctx
, hasher
);
239 impl<CTX
> HashStable
<CTX
> for ::std
::cmp
::Ordering
{
240 fn hash_stable
<W
: StableHasherResult
>(&self,
242 hasher
: &mut StableHasher
<W
>) {
243 (*self as i8).hash_stable(ctx
, hasher
);
247 impl<T1
: HashStable
<CTX
>, CTX
> HashStable
<CTX
> for (T1
,) {
248 fn hash_stable
<W
: StableHasherResult
>(&self,
250 hasher
: &mut StableHasher
<W
>) {
251 let (ref _0
,) = *self;
252 _0
.hash_stable(ctx
, hasher
);
256 impl<T1
: HashStable
<CTX
>, T2
: HashStable
<CTX
>, CTX
> HashStable
<CTX
> for (T1
, T2
) {
257 fn hash_stable
<W
: StableHasherResult
>(&self,
259 hasher
: &mut StableHasher
<W
>) {
260 let (ref _0
, ref _1
) = *self;
261 _0
.hash_stable(ctx
, hasher
);
262 _1
.hash_stable(ctx
, hasher
);
266 impl<T1
, T2
, T3
, CTX
> HashStable
<CTX
> for (T1
, T2
, T3
)
267 where T1
: HashStable
<CTX
>,
271 fn hash_stable
<W
: StableHasherResult
>(&self,
273 hasher
: &mut StableHasher
<W
>) {
274 let (ref _0
, ref _1
, ref _2
) = *self;
275 _0
.hash_stable(ctx
, hasher
);
276 _1
.hash_stable(ctx
, hasher
);
277 _2
.hash_stable(ctx
, hasher
);
281 impl<T
: HashStable
<CTX
>, CTX
> HashStable
<CTX
> for [T
] {
282 default fn hash_stable
<W
: StableHasherResult
>(&self,
284 hasher
: &mut StableHasher
<W
>) {
285 self.len().hash_stable(ctx
, hasher
);
287 item
.hash_stable(ctx
, hasher
);
292 impl<T
: HashStable
<CTX
>, CTX
> HashStable
<CTX
> for Vec
<T
> {
294 fn hash_stable
<W
: StableHasherResult
>(&self,
296 hasher
: &mut StableHasher
<W
>) {
297 (&self[..]).hash_stable(ctx
, hasher
);
301 impl<T
: ?Sized
+ HashStable
<CTX
>, CTX
> HashStable
<CTX
> for Box
<T
> {
303 fn hash_stable
<W
: StableHasherResult
>(&self,
305 hasher
: &mut StableHasher
<W
>) {
306 (**self).hash_stable(ctx
, hasher
);
310 impl<T
: ?Sized
+ HashStable
<CTX
>, CTX
> HashStable
<CTX
> for ::std
::rc
::Rc
<T
> {
312 fn hash_stable
<W
: StableHasherResult
>(&self,
314 hasher
: &mut StableHasher
<W
>) {
315 (**self).hash_stable(ctx
, hasher
);
319 impl<T
: ?Sized
+ HashStable
<CTX
>, CTX
> HashStable
<CTX
> for ::std
::sync
::Arc
<T
> {
321 fn hash_stable
<W
: StableHasherResult
>(&self,
323 hasher
: &mut StableHasher
<W
>) {
324 (**self).hash_stable(ctx
, hasher
);
328 impl<CTX
> HashStable
<CTX
> for str {
330 fn hash_stable
<W
: StableHasherResult
>(&self,
332 hasher
: &mut StableHasher
<W
>) {
333 self.len().hash(hasher
);
334 self.as_bytes().hash(hasher
);
339 impl<CTX
> HashStable
<CTX
> for String
{
341 fn hash_stable
<W
: StableHasherResult
>(&self,
343 hasher
: &mut StableHasher
<W
>) {
344 (&self[..]).hash_stable(hcx
, hasher
);
348 impl<HCX
> ToStableHashKey
<HCX
> for String
{
349 type KeyType
= String
;
351 fn to_stable_hash_key(&self, _
: &HCX
) -> Self::KeyType
{
356 impl<CTX
> HashStable
<CTX
> for bool
{
358 fn hash_stable
<W
: StableHasherResult
>(&self,
360 hasher
: &mut StableHasher
<W
>) {
361 (if *self { 1u8 }
else { 0u8 }
).hash_stable(ctx
, hasher
);
366 impl<T
, CTX
> HashStable
<CTX
> for Option
<T
>
367 where T
: HashStable
<CTX
>
370 fn hash_stable
<W
: StableHasherResult
>(&self,
372 hasher
: &mut StableHasher
<W
>) {
373 if let Some(ref value
) = *self {
374 1u8.hash_stable(ctx
, hasher
);
375 value
.hash_stable(ctx
, hasher
);
377 0u8.hash_stable(ctx
, hasher
);
382 impl<T1
, T2
, CTX
> HashStable
<CTX
> for Result
<T1
, T2
>
383 where T1
: HashStable
<CTX
>,
387 fn hash_stable
<W
: StableHasherResult
>(&self,
389 hasher
: &mut StableHasher
<W
>) {
390 mem
::discriminant(self).hash_stable(ctx
, hasher
);
392 Ok(ref x
) => x
.hash_stable(ctx
, hasher
),
393 Err(ref x
) => x
.hash_stable(ctx
, hasher
),
398 impl<'a
, T
, CTX
> HashStable
<CTX
> for &'a T
399 where T
: HashStable
<CTX
> + ?Sized
402 fn hash_stable
<W
: StableHasherResult
>(&self,
404 hasher
: &mut StableHasher
<W
>) {
405 (**self).hash_stable(ctx
, hasher
);
409 impl<T
, CTX
> HashStable
<CTX
> for ::std
::mem
::Discriminant
<T
> {
411 fn hash_stable
<W
: StableHasherResult
>(&self,
413 hasher
: &mut StableHasher
<W
>) {
414 ::std
::hash
::Hash
::hash(self, hasher
);
418 impl<I
: ::indexed_vec
::Idx
, T
, CTX
> HashStable
<CTX
> for ::indexed_vec
::IndexVec
<I
, T
>
419 where T
: HashStable
<CTX
>,
421 fn hash_stable
<W
: StableHasherResult
>(&self,
423 hasher
: &mut StableHasher
<W
>) {
424 self.len().hash_stable(ctx
, hasher
);
426 v
.hash_stable(ctx
, hasher
);
432 impl<I
: ::indexed_vec
::Idx
, CTX
> HashStable
<CTX
> for ::indexed_set
::IdxSetBuf
<I
>
434 fn hash_stable
<W
: StableHasherResult
>(&self,
436 hasher
: &mut StableHasher
<W
>) {
437 self.words().hash_stable(ctx
, hasher
);
441 impl_stable_hash_via_hash
!(::std
::path
::Path
);
442 impl_stable_hash_via_hash
!(::std
::path
::PathBuf
);
444 impl<K
, V
, R
, HCX
> HashStable
<HCX
> for ::std
::collections
::HashMap
<K
, V
, R
>
445 where K
: ToStableHashKey
<HCX
> + Eq
+ Hash
,
450 fn hash_stable
<W
: StableHasherResult
>(&self,
452 hasher
: &mut StableHasher
<W
>) {
453 hash_stable_hashmap(hcx
, hasher
, self, ToStableHashKey
::to_stable_hash_key
);
457 impl<K
, R
, HCX
> HashStable
<HCX
> for ::std
::collections
::HashSet
<K
, R
>
458 where K
: ToStableHashKey
<HCX
> + Eq
+ Hash
,
461 fn hash_stable
<W
: StableHasherResult
>(&self,
463 hasher
: &mut StableHasher
<W
>) {
464 let mut keys
: Vec
<_
> = self.iter()
465 .map(|k
| k
.to_stable_hash_key(hcx
))
467 keys
.sort_unstable();
468 keys
.hash_stable(hcx
, hasher
);
472 impl<K
, V
, HCX
> HashStable
<HCX
> for ::std
::collections
::BTreeMap
<K
, V
>
473 where K
: ToStableHashKey
<HCX
>,
476 fn hash_stable
<W
: StableHasherResult
>(&self,
478 hasher
: &mut StableHasher
<W
>) {
479 let mut entries
: Vec
<_
> = self.iter()
480 .map(|(k
, v
)| (k
.to_stable_hash_key(hcx
), v
))
482 entries
.sort_unstable_by(|&(ref sk1
, _
), &(ref sk2
, _
)| sk1
.cmp(sk2
));
483 entries
.hash_stable(hcx
, hasher
);
487 impl<K
, HCX
> HashStable
<HCX
> for ::std
::collections
::BTreeSet
<K
>
488 where K
: ToStableHashKey
<HCX
>,
490 fn hash_stable
<W
: StableHasherResult
>(&self,
492 hasher
: &mut StableHasher
<W
>) {
493 let mut keys
: Vec
<_
> = self.iter()
494 .map(|k
| k
.to_stable_hash_key(hcx
))
496 keys
.sort_unstable();
497 keys
.hash_stable(hcx
, hasher
);
501 pub fn hash_stable_hashmap
<HCX
, K
, V
, R
, SK
, F
, W
>(
503 hasher
: &mut StableHasher
<W
>,
504 map
: &::std
::collections
::HashMap
<K
, V
, R
>,
505 to_stable_hash_key
: F
)
509 SK
: HashStable
<HCX
> + Ord
+ Clone
,
510 F
: Fn(&K
, &HCX
) -> SK
,
511 W
: StableHasherResult
,
513 let mut entries
: Vec
<_
> = map
.iter()
514 .map(|(k
, v
)| (to_stable_hash_key(k
, hcx
), v
))
516 entries
.sort_unstable_by(|&(ref sk1
, _
), &(ref sk2
, _
)| sk1
.cmp(sk2
));
517 entries
.hash_stable(hcx
, hasher
);
521 /// A vector container that makes sure that its items are hashed in a stable
523 pub struct StableVec
<T
>(Vec
<T
>);
525 impl<T
> StableVec
<T
> {
526 pub fn new(v
: Vec
<T
>) -> Self {
531 impl<T
> ::std
::ops
::Deref
for StableVec
<T
> {
532 type Target
= Vec
<T
>;
534 fn deref(&self) -> &Vec
<T
> {
539 impl<T
, HCX
> HashStable
<HCX
> for StableVec
<T
>
540 where T
: HashStable
<HCX
> + ToStableHashKey
<HCX
>
542 fn hash_stable
<W
: StableHasherResult
>(&self,
544 hasher
: &mut StableHasher
<W
>) {
545 let StableVec(ref v
) = *self;
547 let mut sorted
: Vec
<_
> = v
.iter()
548 .map(|x
| x
.to_stable_hash_key(hcx
))
550 sorted
.sort_unstable();
551 sorted
.hash_stable(hcx
, hasher
);