compiler/rustc_data_structures/src/fingerprint.rs

   1 use crate::stable_hasher;
   2 use rustc_serialize::{
   3     opaque::{self, EncodeResult, FileEncodeResult},
   4     Decodable, Encodable,
   5 };
   6 use std::hash::{Hash, Hasher};
   7 use std::mem::{self, MaybeUninit};
   8
   9 #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy)]
  10 #[repr(C)]
  11 pub struct Fingerprint(u64, u64);
  12
  13 impl Fingerprint {
  14     pub const ZERO: Fingerprint = Fingerprint(0, 0);
  15
  16     #[inline]
  17     pub fn new(_0: u64, _1: u64) -> Fingerprint {
  18         Fingerprint(_0, _1)
  19     }
  20
  21     #[inline]
  22     pub fn from_smaller_hash(hash: u64) -> Fingerprint {
  23         Fingerprint(hash, hash)
  24     }
  25
  26     #[inline]
  27     pub fn to_smaller_hash(&self) -> u64 {
  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)
  34     }
  35
  36     #[inline]
  37     pub fn as_value(&self) -> (u64, u64) {
  38         (self.0, self.1)
  39     }
  40
  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),
  47             self.1.wrapping_mul(3).wrapping_add(other.1),
  48         )
  49     }
  50
  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 {
  55         let a = u128::from(self.1) << 64 | u128::from(self.0);
  56         let b = u128::from(other.1) << 64 | u128::from(other.0);
  57
  58         let c = a.wrapping_add(b);
  59
  60         Fingerprint((c >> 64) as u64, c as u64)
  61     }
  62
  63     pub fn to_hex(&self) -> String {
  64         format!("{:x}{:x}", self.0, self.1)
  65     }
  66
  67     pub fn decode_opaque(decoder: &mut opaque::Decoder<'_>) -> Result<Fingerprint, String> {
  68         let mut bytes: [MaybeUninit<u8>; 16] = MaybeUninit::uninit_array();
  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     }
  76 }
  77
  78 impl std::fmt::Display for Fingerprint {
  79     fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
  80         write!(formatter, "{:x}-{:x}", self.0, self.1)
  81     }
  82 }
  83
  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) {
 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));
 119     }
 120 }
 121
 122 impl stable_hasher::StableHasherResult for Fingerprint {
 123     #[inline]
 124     fn finish(hasher: stable_hasher::StableHasher) -> Self {
 125         let (_0, _1) = hasher.finalize();
 126         Fingerprint(_0, _1)
 127     }
 128 }
 129
 130 impl_stable_hash_via_hash!(Fingerprint);
 131
 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 }
 137
 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 }
 143
 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 {
 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)
 170     }
 171 }
 172
 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 }
 178
 179 impl FingerprintDecoder for opaque::Decoder<'_> {
 180     fn decode_fingerprint(&mut self) -> Result<Fingerprint, String> {
 181         Fingerprint::decode_opaque(self)
 182     }
 183 }
 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> {
 225         Fingerprint::decode(d).map(PackedFingerprint)
 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 }