src/bootstrap/cache.rs

   1 use std::any::{Any, TypeId};
   2 use std::borrow::Borrow;
   3 use std::cell::RefCell;
   4 use std::cmp::{Ord, Ordering, PartialOrd};
   5 use std::collections::HashMap;
   6 use std::convert::AsRef;
   7 use std::fmt;
   8 use std::hash::{Hash, Hasher};
   9 use std::marker::PhantomData;
  10 use std::mem;
  11 use std::ops::Deref;
  12 use std::path::PathBuf;
  13 use std::sync::Mutex;
  14
  15 // FIXME: replace with std::lazy after it gets stabilized and reaches beta
  16 use once_cell::sync::Lazy;
  17
  18 use crate::builder::Step;
  19
  20 pub struct Interned<T>(usize, PhantomData<*const T>);
  21
  22 impl<T: Internable + Default> Default for Interned<T> {
  23     fn default() -> Self {
  24         T::default().intern()
  25     }
  26 }
  27
  28 impl<T> Copy for Interned<T> {}
  29 impl<T> Clone for Interned<T> {
  30     fn clone(&self) -> Interned<T> {
  31         *self
  32     }
  33 }
  34
  35 impl<T> PartialEq for Interned<T> {
  36     fn eq(&self, other: &Self) -> bool {
  37         self.0 == other.0
  38     }
  39 }
  40 impl<T> Eq for Interned<T> {}
  41
  42 impl PartialEq<str> for Interned<String> {
  43     fn eq(&self, other: &str) -> bool {
  44         *self == other
  45     }
  46 }
  47 impl<'a> PartialEq<&'a str> for Interned<String> {
  48     fn eq(&self, other: &&str) -> bool {
  49         **self == **other
  50     }
  51 }
  52 impl<'a, T> PartialEq<&'a Interned<T>> for Interned<T> {
  53     fn eq(&self, other: &&Self) -> bool {
  54         self.0 == other.0
  55     }
  56 }
  57 impl<'a, T> PartialEq<Interned<T>> for &'a Interned<T> {
  58     fn eq(&self, other: &Interned<T>) -> bool {
  59         self.0 == other.0
  60     }
  61 }
  62
  63 unsafe impl<T> Send for Interned<T> {}
  64 unsafe impl<T> Sync for Interned<T> {}
  65
  66 impl fmt::Display for Interned<String> {
  67     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  68         let s: &str = &*self;
  69         f.write_str(s)
  70     }
  71 }
  72
  73 impl<T, U: ?Sized + fmt::Debug> fmt::Debug for Interned<T>
  74 where
  75     Self: Deref<Target = U>,
  76 {
  77     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  78         let s: &U = &*self;
  79         f.write_fmt(format_args!("{:?}", s))
  80     }
  81 }
  82
  83 impl<T: Internable + Hash> Hash for Interned<T> {
  84     fn hash<H: Hasher>(&self, state: &mut H) {
  85         let l = T::intern_cache().lock().unwrap();
  86         l.get(*self).hash(state)
  87     }
  88 }
  89
  90 impl<T: Internable + Deref> Deref for Interned<T> {
  91     type Target = T::Target;
  92     fn deref(&self) -> &Self::Target {
  93         let l = T::intern_cache().lock().unwrap();
  94         unsafe { mem::transmute::<&Self::Target, &Self::Target>(l.get(*self)) }
  95     }
  96 }
  97
  98 impl<T: Internable + AsRef<U>, U: ?Sized> AsRef<U> for Interned<T> {
  99     fn as_ref(&self) -> &U {
 100         let l = T::intern_cache().lock().unwrap();
 101         unsafe { mem::transmute::<&U, &U>(l.get(*self).as_ref()) }
 102     }
 103 }
 104
 105 impl<T: Internable + PartialOrd> PartialOrd for Interned<T> {
 106     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 107         let l = T::intern_cache().lock().unwrap();
 108         l.get(*self).partial_cmp(l.get(*other))
 109     }
 110 }
 111
 112 impl<T: Internable + Ord> Ord for Interned<T> {
 113     fn cmp(&self, other: &Self) -> Ordering {
 114         let l = T::intern_cache().lock().unwrap();
 115         l.get(*self).cmp(l.get(*other))
 116     }
 117 }
 118
 119 struct TyIntern<T: Clone + Eq> {
 120     items: Vec<T>,
 121     set: HashMap<T, Interned<T>>,
 122 }
 123
 124 impl<T: Hash + Clone + Eq> Default for TyIntern<T> {
 125     fn default() -> Self {
 126         TyIntern { items: Vec::new(), set: Default::default() }
 127     }
 128 }
 129
 130 impl<T: Hash + Clone + Eq> TyIntern<T> {
 131     fn intern_borrow<B>(&mut self, item: &B) -> Interned<T>
 132     where
 133         B: Eq + Hash + ToOwned<Owned = T> + ?Sized,
 134         T: Borrow<B>,
 135     {
 136         if let Some(i) = self.set.get(&item) {
 137             return *i;
 138         }
 139         let item = item.to_owned();
 140         let interned = Interned(self.items.len(), PhantomData::<*const T>);
 141         self.set.insert(item.clone(), interned);
 142         self.items.push(item);
 143         interned
 144     }
 145
 146     fn intern(&mut self, item: T) -> Interned<T> {
 147         if let Some(i) = self.set.get(&item) {
 148             return *i;
 149         }
 150         let interned = Interned(self.items.len(), PhantomData::<*const T>);
 151         self.set.insert(item.clone(), interned);
 152         self.items.push(item);
 153         interned
 154     }
 155
 156     fn get(&self, i: Interned<T>) -> &T {
 157         &self.items[i.0]
 158     }
 159 }
 160
 161 #[derive(Default)]
 162 pub struct Interner {
 163     strs: Mutex<TyIntern<String>>,
 164     paths: Mutex<TyIntern<PathBuf>>,
 165     lists: Mutex<TyIntern<Vec<String>>>,
 166 }
 167
 168 trait Internable: Clone + Eq + Hash + 'static {
 169     fn intern_cache() -> &'static Mutex<TyIntern<Self>>;
 170
 171     fn intern(self) -> Interned<Self> {
 172         Self::intern_cache().lock().unwrap().intern(self)
 173     }
 174 }
 175
 176 impl Internable for String {
 177     fn intern_cache() -> &'static Mutex<TyIntern<Self>> {
 178         &INTERNER.strs
 179     }
 180 }
 181
 182 impl Internable for PathBuf {
 183     fn intern_cache() -> &'static Mutex<TyIntern<Self>> {
 184         &INTERNER.paths
 185     }
 186 }
 187
 188 impl Internable for Vec<String> {
 189     fn intern_cache() -> &'static Mutex<TyIntern<Self>> {
 190         &INTERNER.lists
 191     }
 192 }
 193
 194 impl Interner {
 195     pub fn intern_str(&self, s: &str) -> Interned<String> {
 196         self.strs.lock().unwrap().intern_borrow(s)
 197     }
 198     pub fn intern_string(&self, s: String) -> Interned<String> {
 199         self.strs.lock().unwrap().intern(s)
 200     }
 201
 202     pub fn intern_path(&self, s: PathBuf) -> Interned<PathBuf> {
 203         self.paths.lock().unwrap().intern(s)
 204     }
 205
 206     pub fn intern_list(&self, v: Vec<String>) -> Interned<Vec<String>> {
 207         self.lists.lock().unwrap().intern(v)
 208     }
 209 }
 210
 211 pub static INTERNER: Lazy<Interner> = Lazy::new(Interner::default);
 212
 213 /// This is essentially a `HashMap` which allows storing any type in its input and
 214 /// any type in its output. It is a write-once cache; values are never evicted,
 215 /// which means that references to the value can safely be returned from the
 216 /// `get()` method.
 217 #[derive(Debug)]
 218 pub struct Cache(
 219     RefCell<
 220         HashMap<
 221             TypeId,
 222             Box<dyn Any>, // actually a HashMap<Step, Interned<Step::Output>>
 223         >,
 224     >,
 225 );
 226
 227 impl Cache {
 228     pub fn new() -> Cache {
 229         Cache(RefCell::new(HashMap::new()))
 230     }
 231
 232     pub fn put<S: Step>(&self, step: S, value: S::Output) {
 233         let mut cache = self.0.borrow_mut();
 234         let type_id = TypeId::of::<S>();
 235         let stepcache = cache
 236             .entry(type_id)
 237             .or_insert_with(|| Box::new(HashMap::<S, S::Output>::new()))
 238             .downcast_mut::<HashMap<S, S::Output>>()
 239             .expect("invalid type mapped");
 240         assert!(!stepcache.contains_key(&step), "processing {:?} a second time", step);
 241         stepcache.insert(step, value);
 242     }
 243
 244     pub fn get<S: Step>(&self, step: &S) -> Option<S::Output> {
 245         let mut cache = self.0.borrow_mut();
 246         let type_id = TypeId::of::<S>();
 247         let stepcache = cache
 248             .entry(type_id)
 249             .or_insert_with(|| Box::new(HashMap::<S, S::Output>::new()))
 250             .downcast_mut::<HashMap<S, S::Output>>()
 251             .expect("invalid type mapped");
 252         stepcache.get(step).cloned()
 253     }
 254 }
 255
 256 #[cfg(test)]
 257 impl Cache {
 258     pub fn all<S: Ord + Clone + Step>(&mut self) -> Vec<(S, S::Output)> {
 259         let cache = self.0.get_mut();
 260         let type_id = TypeId::of::<S>();
 261         let mut v = cache
 262             .remove(&type_id)
 263             .map(|b| b.downcast::<HashMap<S, S::Output>>().expect("correct type"))
 264             .map(|m| m.into_iter().collect::<Vec<_>>())
 265             .unwrap_or_default();
 266         v.sort_by_key(|(s, _)| s.clone());
 267         v
 268     }
 269
 270     pub fn contains<S: Step>(&self) -> bool {
 271         self.0.borrow().contains_key(&TypeId::of::<S>())
 272     }
 273 }