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 pub struct Fingerprint(u64, u64);
  11
  12 impl Fingerprint {
  13     pub const ZERO: Fingerprint = Fingerprint(0, 0);
  14
  15     #[inline]
  16     pub fn from_smaller_hash(hash: u64) -> Fingerprint {
  17         Fingerprint(hash, hash)
  18     }
  19
  20     #[inline]
  21     pub fn to_smaller_hash(&self) -> u64 {
  22         self.0
  23     }
  24
  25     #[inline]
  26     pub fn as_value(&self) -> (u64, u64) {
  27         (self.0, self.1)
  28     }
  29
  30     #[inline]
  31     pub fn combine(self, other: Fingerprint) -> Fingerprint {
  32         // See https://stackoverflow.com/a/27952689 on why this function is
  33         // implemented this way.
  34         Fingerprint(
  35             self.0.wrapping_mul(3).wrapping_add(other.0),
  36             self.1.wrapping_mul(3).wrapping_add(other.1),
  37         )
  38     }
  39
  40     // Combines two hashes in an order independent way. Make sure this is what
  41     // you want.
  42     #[inline]
  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);
  46
  47         let c = a.wrapping_add(b);
  48
  49         Fingerprint((c >> 64) as u64, c as u64)
  50     }
  51
  52     pub fn to_hex(&self) -> String {
  53         format!("{:x}{:x}", self.0, self.1)
  54     }
  55
  56     pub fn decode_opaque(decoder: &mut opaque::Decoder<'_>) -> Result<Fingerprint, String> {
  57         let mut bytes: [MaybeUninit<u8>; 16] = MaybeUninit::uninit_array();
  58
  59         decoder.read_raw_bytes(&mut bytes)?;
  60
  61         let [l, r]: [u64; 2] = unsafe { mem::transmute(bytes) };
  62
  63         Ok(Fingerprint(u64::from_le(l), u64::from_le(r)))
  64     }
  65 }
  66
  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)
  70     }
  71 }
  72
  73 impl Hash for Fingerprint {
  74     #[inline]
  75     fn hash<H: Hasher>(&self, state: &mut H) {
  76         state.write_fingerprint(self);
  77     }
  78 }
  79
  80 trait FingerprintHasher {
  81     fn write_fingerprint(&mut self, fingerprint: &Fingerprint);
  82 }
  83
  84 impl<H: Hasher> FingerprintHasher for H {
  85     #[inline]
  86     default fn write_fingerprint(&mut self, fingerprint: &Fingerprint) {
  87         self.write_u64(fingerprint.0);
  88         self.write_u64(fingerprint.1);
  89     }
  90 }
  91
  92 impl FingerprintHasher for crate::unhash::Unhasher {
  93     #[inline]
  94     fn write_fingerprint(&mut self, fingerprint: &Fingerprint) {
  95         // `Unhasher` only wants a single `u64`
  96         self.write_u64(fingerprint.0);
  97     }
  98 }
  99
 100 impl stable_hasher::StableHasherResult for Fingerprint {
 101     #[inline]
 102     fn finish(hasher: stable_hasher::StableHasher) -> Self {
 103         let (_0, _1) = hasher.finalize();
 104         Fingerprint(_0, _1)
 105     }
 106 }
 107
 108 impl_stable_hash_via_hash!(Fingerprint);
 109
 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)
 113     }
 114 }
 115
 116 impl<D: rustc_serialize::Decoder> Decodable<D> for Fingerprint {
 117     fn decode(d: &mut D) -> Result<Self, D::Error> {
 118         d.decode_fingerprint()
 119     }
 120 }
 121
 122 pub trait FingerprintEncoder: rustc_serialize::Encoder {
 123     fn encode_fingerprint(&mut self, f: &Fingerprint) -> Result<(), Self::Error>;
 124 }
 125
 126 pub trait FingerprintDecoder: rustc_serialize::Decoder {
 127     fn decode_fingerprint(&mut self) -> Result<Fingerprint, Self::Error>;
 128 }
 129
 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>());
 133     }
 134 }
 135
 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);
 140         Ok(())
 141     }
 142 }
 143
 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)
 148     }
 149 }
 150
 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>());
 154     }
 155 }
 156
 157 impl FingerprintDecoder for opaque::Decoder<'_> {
 158     fn decode_fingerprint(&mut self) -> Result<Fingerprint, String> {
 159         Fingerprint::decode_opaque(self)
 160     }
 161 }
 162
 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.
 167 //
 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.
 175 //
 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);
 181
 182 impl std::fmt::Display for PackedFingerprint {
 183     #[inline]
 184     fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 185         // Copy to avoid taking reference to packed field.
 186         let copy = self.0;
 187         copy.fmt(formatter)
 188     }
 189 }
 190
 191 impl<E: rustc_serialize::Encoder> Encodable<E> for PackedFingerprint {
 192     #[inline]
 193     fn encode(&self, s: &mut E) -> Result<(), E::Error> {
 194         // Copy to avoid taking reference to packed field.
 195         let copy = self.0;
 196         copy.encode(s)
 197     }
 198 }
 199
 200 impl<D: rustc_serialize::Decoder> Decodable<D> for PackedFingerprint {
 201     #[inline]
 202     fn decode(d: &mut D) -> Result<Self, D::Error> {
 203         Fingerprint::decode(d).map(PackedFingerprint)
 204     }
 205 }
 206
 207 impl From<Fingerprint> for PackedFingerprint {
 208     #[inline]
 209     fn from(f: Fingerprint) -> PackedFingerprint {
 210         PackedFingerprint(f)
 211     }
 212 }
 213
 214 impl From<PackedFingerprint> for Fingerprint {
 215     #[inline]
 216     fn from(f: PackedFingerprint) -> Fingerprint {
 217         f.0
 218     }
 219 }