]>
Commit | Line | Data |
---|---|---|
9fa01778 | 1 | use crate::stable_hasher; |
3dfed10e | 2 | use rustc_serialize::{ |
5869c6ff | 3 | opaque::{self, EncodeResult, FileEncodeResult}, |
3dfed10e XL |
4 | Decodable, Encodable, |
5 | }; | |
1b1a35ee | 6 | use std::hash::{Hash, Hasher}; |
5869c6ff | 7 | use std::mem::{self, MaybeUninit}; |
c30ab7b3 | 8 | |
1b1a35ee | 9 | #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy)] |
6a06907d | 10 | #[repr(C)] |
7cac9316 | 11 | pub struct Fingerprint(u64, u64); |
c30ab7b3 SL |
12 | |
13 | impl Fingerprint { | |
ff7c6d11 | 14 | pub const ZERO: Fingerprint = Fingerprint(0, 0); |
c30ab7b3 | 15 | |
6a06907d XL |
16 | #[inline] |
17 | pub fn new(_0: u64, _1: u64) -> Fingerprint { | |
18 | Fingerprint(_0, _1) | |
19 | } | |
20 | ||
7cac9316 | 21 | #[inline] |
c30ab7b3 | 22 | pub fn from_smaller_hash(hash: u64) -> Fingerprint { |
7cac9316 | 23 | Fingerprint(hash, hash) |
c30ab7b3 SL |
24 | } |
25 | ||
7cac9316 | 26 | #[inline] |
c30ab7b3 | 27 | pub fn to_smaller_hash(&self) -> u64 { |
6a06907d XL |
28 | // Even though both halves of the fingerprint are expected to be good |
29 | // quality hash values, let's still combine the two values because the | |
30 | // Fingerprints in DefPathHash have the StableCrateId portion which is | |
31 | // the same for all DefPathHashes from the same crate. Combining the | |
32 | // two halfs makes sure we get a good quality hash in such cases too. | |
33 | self.0.wrapping_mul(3).wrapping_add(self.1) | |
c30ab7b3 | 34 | } |
476ff2be | 35 | |
abe05a73 XL |
36 | #[inline] |
37 | pub fn as_value(&self) -> (u64, u64) { | |
38 | (self.0, self.1) | |
39 | } | |
40 | ||
041b39d2 XL |
41 | #[inline] |
42 | pub fn combine(self, other: Fingerprint) -> Fingerprint { | |
43 | // See https://stackoverflow.com/a/27952689 on why this function is | |
44 | // implemented this way. | |
45 | Fingerprint( | |
46 | self.0.wrapping_mul(3).wrapping_add(other.0), | |
dfeec247 | 47 | self.1.wrapping_mul(3).wrapping_add(other.1), |
041b39d2 XL |
48 | ) |
49 | } | |
50 | ||
8faf50e0 XL |
51 | // Combines two hashes in an order independent way. Make sure this is what |
52 | // you want. | |
53 | #[inline] | |
54 | pub fn combine_commutative(self, other: Fingerprint) -> Fingerprint { | |
dc9dc135 XL |
55 | let a = u128::from(self.1) << 64 | u128::from(self.0); |
56 | let b = u128::from(other.1) << 64 | u128::from(other.0); | |
8faf50e0 XL |
57 | |
58 | let c = a.wrapping_add(b); | |
59 | ||
60 | Fingerprint((c >> 64) as u64, c as u64) | |
61 | } | |
62 | ||
476ff2be | 63 | pub fn to_hex(&self) -> String { |
7cac9316 | 64 | format!("{:x}{:x}", self.0, self.1) |
476ff2be | 65 | } |
041b39d2 | 66 | |
3dfed10e | 67 | pub fn decode_opaque(decoder: &mut opaque::Decoder<'_>) -> Result<Fingerprint, String> { |
5869c6ff | 68 | let mut bytes: [MaybeUninit<u8>; 16] = MaybeUninit::uninit_array(); |
2c00a5a8 XL |
69 | |
70 | decoder.read_raw_bytes(&mut bytes)?; | |
71 | ||
72 | let [l, r]: [u64; 2] = unsafe { mem::transmute(bytes) }; | |
73 | ||
74 | Ok(Fingerprint(u64::from_le(l), u64::from_le(r))) | |
75 | } | |
c30ab7b3 SL |
76 | } |
77 | ||
29967ef6 XL |
78 | impl std::fmt::Display for Fingerprint { |
79 | fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { | |
7cac9316 | 80 | write!(formatter, "{:x}-{:x}", self.0, self.1) |
c30ab7b3 SL |
81 | } |
82 | } | |
83 | ||
1b1a35ee XL |
84 | impl Hash for Fingerprint { |
85 | #[inline] | |
86 | fn hash<H: Hasher>(&self, state: &mut H) { | |
87 | state.write_fingerprint(self); | |
88 | } | |
89 | } | |
90 | ||
91 | trait FingerprintHasher { | |
92 | fn write_fingerprint(&mut self, fingerprint: &Fingerprint); | |
93 | } | |
94 | ||
95 | impl<H: Hasher> FingerprintHasher for H { | |
96 | #[inline] | |
97 | default fn write_fingerprint(&mut self, fingerprint: &Fingerprint) { | |
98 | self.write_u64(fingerprint.0); | |
99 | self.write_u64(fingerprint.1); | |
100 | } | |
101 | } | |
102 | ||
103 | impl FingerprintHasher for crate::unhash::Unhasher { | |
104 | #[inline] | |
105 | fn write_fingerprint(&mut self, fingerprint: &Fingerprint) { | |
6a06907d XL |
106 | // Even though both halves of the fingerprint are expected to be good |
107 | // quality hash values, let's still combine the two values because the | |
108 | // Fingerprints in DefPathHash have the StableCrateId portion which is | |
109 | // the same for all DefPathHashes from the same crate. Combining the | |
110 | // two halfs makes sure we get a good quality hash in such cases too. | |
111 | // | |
112 | // Since `Unhasher` is used only in the context of HashMaps, it is OK | |
113 | // to combine the two components in an order-independent way (which is | |
114 | // cheaper than the more robust Fingerprint::to_smaller_hash()). For | |
115 | // HashMaps we don't really care if Fingerprint(x,y) and | |
116 | // Fingerprint(y, x) result in the same hash value. Collision | |
117 | // probability will still be much better than with FxHash. | |
118 | self.write_u64(fingerprint.0.wrapping_add(fingerprint.1)); | |
1b1a35ee XL |
119 | } |
120 | } | |
121 | ||
7cac9316 | 122 | impl stable_hasher::StableHasherResult for Fingerprint { |
0731742a | 123 | #[inline] |
e74abb32 | 124 | fn finish(hasher: stable_hasher::StableHasher) -> Self { |
abe05a73 XL |
125 | let (_0, _1) = hasher.finalize(); |
126 | Fingerprint(_0, _1) | |
c30ab7b3 SL |
127 | } |
128 | } | |
476ff2be | 129 | |
b7449926 | 130 | impl_stable_hash_via_hash!(Fingerprint); |
2c00a5a8 | 131 | |
3dfed10e XL |
132 | impl<E: rustc_serialize::Encoder> Encodable<E> for Fingerprint { |
133 | fn encode(&self, s: &mut E) -> Result<(), E::Error> { | |
134 | s.encode_fingerprint(self) | |
135 | } | |
136 | } | |
2c00a5a8 | 137 | |
3dfed10e XL |
138 | impl<D: rustc_serialize::Decoder> Decodable<D> for Fingerprint { |
139 | fn decode(d: &mut D) -> Result<Self, D::Error> { | |
140 | d.decode_fingerprint() | |
141 | } | |
142 | } | |
2c00a5a8 | 143 | |
3dfed10e XL |
144 | pub trait FingerprintEncoder: rustc_serialize::Encoder { |
145 | fn encode_fingerprint(&mut self, f: &Fingerprint) -> Result<(), Self::Error>; | |
146 | } | |
147 | ||
148 | pub trait FingerprintDecoder: rustc_serialize::Decoder { | |
149 | fn decode_fingerprint(&mut self) -> Result<Fingerprint, Self::Error>; | |
150 | } | |
151 | ||
152 | impl<E: rustc_serialize::Encoder> FingerprintEncoder for E { | |
153 | default fn encode_fingerprint(&mut self, _: &Fingerprint) -> Result<(), E::Error> { | |
154 | panic!("Cannot encode `Fingerprint` with `{}`", std::any::type_name::<E>()); | |
155 | } | |
156 | } | |
157 | ||
158 | impl FingerprintEncoder for opaque::Encoder { | |
159 | fn encode_fingerprint(&mut self, f: &Fingerprint) -> EncodeResult { | |
5869c6ff XL |
160 | let bytes: [u8; 16] = unsafe { mem::transmute([f.0.to_le(), f.1.to_le()]) }; |
161 | self.emit_raw_bytes(&bytes); | |
162 | Ok(()) | |
163 | } | |
164 | } | |
165 | ||
166 | impl FingerprintEncoder for opaque::FileEncoder { | |
167 | fn encode_fingerprint(&mut self, f: &Fingerprint) -> FileEncodeResult { | |
168 | let bytes: [u8; 16] = unsafe { mem::transmute([f.0.to_le(), f.1.to_le()]) }; | |
169 | self.emit_raw_bytes(&bytes) | |
2c00a5a8 XL |
170 | } |
171 | } | |
172 | ||
3dfed10e XL |
173 | impl<D: rustc_serialize::Decoder> FingerprintDecoder for D { |
174 | default fn decode_fingerprint(&mut self) -> Result<Fingerprint, D::Error> { | |
175 | panic!("Cannot decode `Fingerprint` with `{}`", std::any::type_name::<D>()); | |
176 | } | |
177 | } | |
fc512014 | 178 | |
3dfed10e XL |
179 | impl FingerprintDecoder for opaque::Decoder<'_> { |
180 | fn decode_fingerprint(&mut self) -> Result<Fingerprint, String> { | |
2c00a5a8 XL |
181 | Fingerprint::decode_opaque(self) |
182 | } | |
183 | } | |
fc512014 XL |
184 | |
185 | // `PackedFingerprint` wraps a `Fingerprint`. Its purpose is to, on certain | |
186 | // architectures, behave like a `Fingerprint` without alignment requirements. | |
187 | // This behavior is only enabled on x86 and x86_64, where the impact of | |
188 | // unaligned accesses is tolerable in small doses. | |
189 | // | |
190 | // This may be preferable to use in large collections of structs containing | |
191 | // fingerprints, as it can reduce memory consumption by preventing the padding | |
192 | // that the more strictly-aligned `Fingerprint` can introduce. An application of | |
193 | // this is in the query dependency graph, which contains a large collection of | |
194 | // `DepNode`s. As of this writing, the size of a `DepNode` decreases by ~30% | |
195 | // (from 24 bytes to 17) by using the packed representation here, which | |
196 | // noticeably decreases total memory usage when compiling large crates. | |
197 | // | |
198 | // The wrapped `Fingerprint` is private to reduce the chance of a client | |
199 | // invoking undefined behavior by taking a reference to the packed field. | |
200 | #[cfg_attr(any(target_arch = "x86", target_arch = "x86_64"), repr(packed))] | |
201 | #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy, Hash)] | |
202 | pub struct PackedFingerprint(Fingerprint); | |
203 | ||
204 | impl std::fmt::Display for PackedFingerprint { | |
205 | #[inline] | |
206 | fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { | |
207 | // Copy to avoid taking reference to packed field. | |
208 | let copy = self.0; | |
209 | copy.fmt(formatter) | |
210 | } | |
211 | } | |
212 | ||
213 | impl<E: rustc_serialize::Encoder> Encodable<E> for PackedFingerprint { | |
214 | #[inline] | |
215 | fn encode(&self, s: &mut E) -> Result<(), E::Error> { | |
216 | // Copy to avoid taking reference to packed field. | |
217 | let copy = self.0; | |
218 | copy.encode(s) | |
219 | } | |
220 | } | |
221 | ||
222 | impl<D: rustc_serialize::Decoder> Decodable<D> for PackedFingerprint { | |
223 | #[inline] | |
224 | fn decode(d: &mut D) -> Result<Self, D::Error> { | |
5869c6ff | 225 | Fingerprint::decode(d).map(PackedFingerprint) |
fc512014 XL |
226 | } |
227 | } | |
228 | ||
229 | impl From<Fingerprint> for PackedFingerprint { | |
230 | #[inline] | |
231 | fn from(f: Fingerprint) -> PackedFingerprint { | |
232 | PackedFingerprint(f) | |
233 | } | |
234 | } | |
235 | ||
236 | impl From<PackedFingerprint> for Fingerprint { | |
237 | #[inline] | |
238 | fn from(f: PackedFingerprint) -> Fingerprint { | |
239 | f.0 | |
240 | } | |
241 | } |