hphp/hack/src/hcons/lib.rs

   1 // Copyright (c) Facebook, Inc. and its affiliates.
   2 //
   3 // This source code is licensed under the MIT license found in the
   4 // LICENSE file in the "hack" directory of this source tree.
   5
   6 use std::borrow::Borrow;
   7 use std::fmt;
   8 use std::hash::{Hash, Hasher};
   9 use std::ops::Deref;
  10 use std::sync::{Arc, Weak};
  11
  12 use dashmap::{mapref::entry::Entry, DashMap};
  13
  14 /// A hash-consed pointer.
  15 pub struct Hc<T: ?Sized>(Arc<T>);
  16
  17 impl<T: ?Sized> Clone for Hc<T> {
  18     #[inline]
  19     fn clone(&self) -> Self {
  20         Hc(Arc::clone(&self.0))
  21     }
  22 }
  23
  24 impl<T: fmt::Debug + ?Sized> fmt::Debug for Hc<T> {
  25     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
  26         self.0.fmt(f)
  27     }
  28 }
  29
  30 impl<T: fmt::Display + ?Sized> fmt::Display for Hc<T> {
  31     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  32         self.0.fmt(f)
  33     }
  34 }
  35
  36 impl<T: ?Sized> Deref for Hc<T> {
  37     type Target = T;
  38
  39     fn deref(&self) -> &T {
  40         &self.0
  41     }
  42 }
  43
  44 impl<T: ?Sized> Eq for Hc<T> {}
  45
  46 impl<T: ?Sized> Hash for Hc<T> {
  47     fn hash<H: Hasher>(&self, state: &mut H) {
  48         // hashbrown-based hash tables use the upper byte of the hash code as a
  49         // tag which drives SIMD parallelism. If `state` is a Hasher which
  50         // doesn't distribute pointer hashes well (e.g., nohash_hasher), then
  51         // all upper bytes of Hc hash codes will be the same, and perf of
  52         // hashbrown tables containing Hc keys will suffer. If we carefully
  53         // avoid such hashers, we could probably just hash the (fat) pointer
  54         // here. But as a precaution for now, run it through FNV first.
  55         state.write_u64(fnv_hash(&Arc::as_ptr(&self.0)));
  56     }
  57 }
  58
  59 impl<T: ?Sized> PartialEq for Hc<T> {
  60     fn eq(&self, other: &Self) -> bool {
  61         std::ptr::eq(self.0.as_ref(), other.0.as_ref())
  62     }
  63 }
  64
  65 impl<T: ?Sized> PartialEq<&Hc<T>> for Hc<T> {
  66     fn eq(&self, other: &&Hc<T>) -> bool {
  67         std::ptr::eq(self.0.as_ref(), other.0.as_ref())
  68     }
  69 }
  70
  71 impl<T: ?Sized> PartialEq<Hc<T>> for &Hc<T> {
  72     fn eq(&self, other: &Hc<T>) -> bool {
  73         std::ptr::eq(self.0.as_ref(), other.0.as_ref())
  74     }
  75 }
  76
  77 impl<T: ?Sized + PartialOrd> PartialOrd for Hc<T> {
  78     #[inline]
  79     fn partial_cmp(&self, other: &Hc<T>) -> Option<std::cmp::Ordering> {
  80         (**self).partial_cmp(&**other)
  81     }
  82 }
  83
  84 impl<T: ?Sized + Ord> Ord for Hc<T> {
  85     #[inline]
  86     fn cmp(&self, other: &Hc<T>) -> std::cmp::Ordering {
  87         (**self).cmp(&**other)
  88     }
  89 }
  90
  91 macro_rules! impl_str_eq {
  92     ($lhs:ty, $rhs:ty) => {
  93         #[allow(clippy::partialeq_ne_impl)]
  94         impl PartialEq<$rhs> for $lhs {
  95             #[inline]
  96             fn eq(&self, other: &$rhs) -> bool {
  97                 PartialEq::eq(&self[..], &other[..])
  98             }
  99             #[inline]
 100             fn ne(&self, other: &$rhs) -> bool {
 101                 PartialEq::ne(&self[..], &other[..])
 102             }
 103         }
 104
 105         #[allow(clippy::partialeq_ne_impl)]
 106         impl PartialEq<$lhs> for $rhs {
 107             #[inline]
 108             fn eq(&self, other: &$lhs) -> bool {
 109                 PartialEq::eq(&self[..], &other[..])
 110             }
 111             #[inline]
 112             fn ne(&self, other: &$lhs) -> bool {
 113                 PartialEq::ne(&self[..], &other[..])
 114             }
 115         }
 116     };
 117 }
 118
 119 impl_str_eq! { Hc<str>, str }
 120 impl_str_eq! { Hc<str>, &str }
 121 impl_str_eq! { Hc<str>, String }
 122 impl_str_eq! { Hc<str>, &String }
 123 impl_str_eq! { Hc<str>, Box<str> }
 124
 125 impl AsRef<str> for Hc<str> {
 126     #[inline]
 127     fn as_ref(&self) -> &str {
 128         &self[..]
 129     }
 130 }
 131
 132 impl AsRef<[u8]> for Hc<str> {
 133     #[inline]
 134     fn as_ref(&self) -> &[u8] {
 135         self.as_bytes()
 136     }
 137 }
 138
 139 impl AsRef<std::path::Path> for Hc<str> {
 140     #[inline]
 141     fn as_ref(&self) -> &std::path::Path {
 142         std::path::Path::new(&self[..])
 143     }
 144 }
 145
 146 impl AsRef<std::ffi::OsStr> for Hc<str> {
 147     #[inline]
 148     fn as_ref(&self) -> &std::ffi::OsStr {
 149         std::ffi::OsStr::new(&self[..])
 150     }
 151 }
 152
 153 fn fnv_hash<T: Hash + ?Sized>(value: &T) -> u64 {
 154     let mut hasher = fnv::FnvHasher::default();
 155     value.hash(&mut hasher);
 156     hasher.finish()
 157 }
 158
 159 #[derive(Debug)]
 160 pub struct Conser<T: ?Sized> {
 161     table: DashMap<u64, Weak<T>>,
 162 }
 163
 164 impl<T: Eq + Hash + ?Sized> Conser<T> {
 165     pub fn new() -> Self {
 166         Conser {
 167             table: DashMap::new(),
 168         }
 169     }
 170
 171     pub fn gc(&self) -> bool {
 172         let l = self.table.len();
 173         self.table.retain(|_, v| v.strong_count() != 0);
 174         l != self.table.len()
 175     }
 176
 177     fn mk_helper<U>(
 178         &self,
 179         hash: u64,
 180         x: U,
 181         make_rc: impl FnOnce(U) -> Arc<T>,
 182         eq: impl FnOnce(&U, &T) -> bool,
 183     ) -> Hc<T> {
 184         let rc = match self.table.entry(hash) {
 185             Entry::Occupied(mut o) => match o.get().upgrade() {
 186                 Some(rc) => {
 187                     // TODO: handle collisions
 188                     debug_assert!(eq(&x, &rc));
 189                     rc
 190                 }
 191                 None => {
 192                     let rc = make_rc(x);
 193                     o.insert(Arc::downgrade(&rc));
 194                     rc
 195                 }
 196             },
 197             Entry::Vacant(v) => {
 198                 let rc = make_rc(x);
 199                 v.insert(Arc::downgrade(&rc));
 200                 rc
 201             }
 202         };
 203         Hc(rc)
 204     }
 205
 206     pub fn mk_from_ref<'a, Q>(&self, x: &'a Q) -> Hc<T>
 207     where
 208         T: Borrow<Q>,
 209         Q: 'a + Eq + Hash + PartialEq<T> + ?Sized,
 210         Arc<T>: From<&'a Q>,
 211     {
 212         self.mk_helper(fnv_hash(x), x, Arc::from, |x: &&Q, rc: &T| {
 213             *x == rc.borrow()
 214         })
 215     }
 216 }
 217
 218 impl<T: Eq + Hash> Conser<T> {
 219     pub fn mk(&self, x: T) -> Hc<T> {
 220         self.mk_helper(fnv_hash(&x), x, Arc::new, |x: &T, rc: &T| x == rc)
 221     }
 222 }
 223
 224 impl Conser<[u8]> {
 225     pub fn mk_str(&self, x: &str) -> Hc<str> {
 226         let bytes = self.mk_from_ref(x.as_bytes());
 227         let ptr: *const [u8] = Arc::into_raw(bytes.0);
 228         // SAFETY: `x` is known to be a valid `&str`, and `bytes` is just a
 229         // ref-counted copy of it.
 230         unsafe { Hc(Arc::from_raw(ptr as *const str)) }
 231     }
 232
 233     pub fn mk_bstr<B: ?Sized + AsRef<[u8]>>(&self, x: &B) -> Hc<bstr::BStr> {
 234         let bytes = self.mk_from_ref(x.as_ref());
 235         let ptr: *const [u8] = Arc::into_raw(bytes.0);
 236         // SAFETY: `BStr` is a `repr(transparent)` wrapper for `[u8]`.
 237         unsafe { Hc(Arc::from_raw(ptr as *const bstr::BStr)) }
 238     }
 239 }