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