1 use crate::stable_hasher;
3 opaque::{self, EncodeResult, FileEncodeResult},
6 use std::hash::{Hash, Hasher};
7 use std::mem::{self, MaybeUninit};
9 #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy)]
10 pub struct Fingerprint(u64, u64);
13 pub const ZERO: Fingerprint = Fingerprint(0, 0);
16 pub fn from_smaller_hash(hash: u64) -> Fingerprint {
17 Fingerprint(hash, hash)
21 pub fn to_smaller_hash(&self) -> u64 {
26 pub fn as_value(&self) -> (u64, u64) {
31 pub fn combine(self, other: Fingerprint) -> Fingerprint {
32 // See https://stackoverflow.com/a/27952689 on why this function is
33 // implemented this way.
35 self.0.wrapping_mul(3).wrapping_add(other.0),
36 self.1.wrapping_mul(3).wrapping_add(other.1),
40 // Combines two hashes in an order independent way. Make sure this is what
43 pub fn combine_commutative(self, other: Fingerprint) -> Fingerprint {
44 let a = u128::from(self.1) << 64 | u128::from(self.0);
45 let b = u128::from(other.1) << 64 | u128::from(other.0);
47 let c = a.wrapping_add(b);
49 Fingerprint((c >> 64) as u64, c as u64)
52 pub fn to_hex(&self) -> String {
53 format!("{:x}{:x}", self.0, self.1)
56 pub fn decode_opaque(decoder: &mut opaque::Decoder<'_>) -> Result<Fingerprint, String> {
57 let mut bytes: [MaybeUninit<u8>; 16] = MaybeUninit::uninit_array();
59 decoder.read_raw_bytes(&mut bytes)?;
61 let [l, r]: [u64; 2] = unsafe { mem::transmute(bytes) };
63 Ok(Fingerprint(u64::from_le(l), u64::from_le(r)))
67 impl std::fmt::Display for Fingerprint {
68 fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
69 write!(formatter, "{:x}-{:x}", self.0, self.1)
73 impl Hash for Fingerprint {
75 fn hash<H: Hasher>(&self, state: &mut H) {
76 state.write_fingerprint(self);
80 trait FingerprintHasher {
81 fn write_fingerprint(&mut self, fingerprint: &Fingerprint);
84 impl<H: Hasher> FingerprintHasher for H {
86 default fn write_fingerprint(&mut self, fingerprint: &Fingerprint) {
87 self.write_u64(fingerprint.0);
88 self.write_u64(fingerprint.1);
92 impl FingerprintHasher for crate::unhash::Unhasher {
94 fn write_fingerprint(&mut self, fingerprint: &Fingerprint) {
95 // `Unhasher` only wants a single `u64`
96 self.write_u64(fingerprint.0);
100 impl stable_hasher::StableHasherResult for Fingerprint {
102 fn finish(hasher: stable_hasher::StableHasher) -> Self {
103 let (_0, _1) = hasher.finalize();
108 impl_stable_hash_via_hash!(Fingerprint);
110 impl<E: rustc_serialize::Encoder> Encodable<E> for Fingerprint {
111 fn encode(&self, s: &mut E) -> Result<(), E::Error> {
112 s.encode_fingerprint(self)
116 impl<D: rustc_serialize::Decoder> Decodable<D> for Fingerprint {
117 fn decode(d: &mut D) -> Result<Self, D::Error> {
118 d.decode_fingerprint()
122 pub trait FingerprintEncoder: rustc_serialize::Encoder {
123 fn encode_fingerprint(&mut self, f: &Fingerprint) -> Result<(), Self::Error>;
126 pub trait FingerprintDecoder: rustc_serialize::Decoder {
127 fn decode_fingerprint(&mut self) -> Result<Fingerprint, Self::Error>;
130 impl<E: rustc_serialize::Encoder> FingerprintEncoder for E {
131 default fn encode_fingerprint(&mut self, _: &Fingerprint) -> Result<(), E::Error> {
132 panic!("Cannot encode `Fingerprint` with `{}`", std::any::type_name::<E>());
136 impl FingerprintEncoder for opaque::Encoder {
137 fn encode_fingerprint(&mut self, f: &Fingerprint) -> EncodeResult {
138 let bytes: [u8; 16] = unsafe { mem::transmute([f.0.to_le(), f.1.to_le()]) };
139 self.emit_raw_bytes(&bytes);
144 impl FingerprintEncoder for opaque::FileEncoder {
145 fn encode_fingerprint(&mut self, f: &Fingerprint) -> FileEncodeResult {
146 let bytes: [u8; 16] = unsafe { mem::transmute([f.0.to_le(), f.1.to_le()]) };
147 self.emit_raw_bytes(&bytes)
151 impl<D: rustc_serialize::Decoder> FingerprintDecoder for D {
152 default fn decode_fingerprint(&mut self) -> Result<Fingerprint, D::Error> {
153 panic!("Cannot decode `Fingerprint` with `{}`", std::any::type_name::<D>());
157 impl FingerprintDecoder for opaque::Decoder<'_> {
158 fn decode_fingerprint(&mut self) -> Result<Fingerprint, String> {
159 Fingerprint::decode_opaque(self)
163 // `PackedFingerprint` wraps a `Fingerprint`. Its purpose is to, on certain
164 // architectures, behave like a `Fingerprint` without alignment requirements.
165 // This behavior is only enabled on x86 and x86_64, where the impact of
166 // unaligned accesses is tolerable in small doses.
168 // This may be preferable to use in large collections of structs containing
169 // fingerprints, as it can reduce memory consumption by preventing the padding
170 // that the more strictly-aligned `Fingerprint` can introduce. An application of
171 // this is in the query dependency graph, which contains a large collection of
172 // `DepNode`s. As of this writing, the size of a `DepNode` decreases by ~30%
173 // (from 24 bytes to 17) by using the packed representation here, which
174 // noticeably decreases total memory usage when compiling large crates.
176 // The wrapped `Fingerprint` is private to reduce the chance of a client
177 // invoking undefined behavior by taking a reference to the packed field.
178 #[cfg_attr(any(target_arch = "x86", target_arch = "x86_64"), repr(packed))]
179 #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy, Hash)]
180 pub struct PackedFingerprint(Fingerprint);
182 impl std::fmt::Display for PackedFingerprint {
184 fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
185 // Copy to avoid taking reference to packed field.
191 impl<E: rustc_serialize::Encoder> Encodable<E> for PackedFingerprint {
193 fn encode(&self, s: &mut E) -> Result<(), E::Error> {
194 // Copy to avoid taking reference to packed field.
200 impl<D: rustc_serialize::Decoder> Decodable<D> for PackedFingerprint {
202 fn decode(d: &mut D) -> Result<Self, D::Error> {
203 Fingerprint::decode(d).map(PackedFingerprint)
207 impl From<Fingerprint> for PackedFingerprint {
209 fn from(f: Fingerprint) -> PackedFingerprint {
214 impl From<PackedFingerprint> for Fingerprint {
216 fn from(f: PackedFingerprint) -> Fingerprint {