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