src/bootstrap/cache.rs

   1 use std::any::{Any, TypeId};
   2 use std::borrow::Borrow;
   3 use std::cell::RefCell;
   4 use std::collections::HashMap;
   5 use std::convert::AsRef;
   6 use std::ffi::OsStr;
   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::{Path, PathBuf};
  13 use std::sync::Mutex;
  14 use std::cmp::{PartialOrd, Ord, Ordering};
  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 {
 172             items: Vec::new(),
 173             set: Default::default(),
 174         }
 175     }
 176 }
 177
 178 impl<T: Hash + Clone + Eq> TyIntern<T> {
 179     fn intern_borrow<B>(&mut self, item: &B) -> Interned<T>
 180     where
 181         B: Eq + Hash + ToOwned<Owned=T> + ?Sized,
 182         T: Borrow<B>,
 183     {
 184         if let Some(i) = self.set.get(&item) {
 185             return *i;
 186         }
 187         let item = item.to_owned();
 188         let interned =  Interned(self.items.len(), PhantomData::<*const T>);
 189         self.set.insert(item.clone(), interned);
 190         self.items.push(item);
 191         interned
 192     }
 193
 194     fn intern(&mut self, item: T) -> Interned<T> {
 195         if let Some(i) = self.set.get(&item) {
 196             return *i;
 197         }
 198         let interned =  Interned(self.items.len(), PhantomData::<*const T>);
 199         self.set.insert(item.clone(), interned);
 200         self.items.push(item);
 201         interned
 202     }
 203
 204     fn get(&self, i: Interned<T>) -> &T {
 205         &self.items[i.0]
 206     }
 207 }
 208
 209 #[derive(Default)]
 210 pub struct Interner {
 211     strs: Mutex<TyIntern<String>>,
 212     paths: Mutex<TyIntern<PathBuf>>,
 213 }
 214
 215 impl Interner {
 216     pub fn intern_str(&self, s: &str) -> Interned<String> {
 217         self.strs.lock().unwrap().intern_borrow(s)
 218     }
 219     pub fn intern_string(&self, s: String) -> Interned<String> {
 220         self.strs.lock().unwrap().intern(s)
 221     }
 222
 223     pub fn intern_path(&self, s: PathBuf) -> Interned<PathBuf> {
 224         self.paths.lock().unwrap().intern(s)
 225     }
 226 }
 227
 228 lazy_static! {
 229     pub static ref INTERNER: Interner = Interner::default();
 230 }
 231
 232 /// This is essentially a `HashMap` which allows storing any type in its input and
 233 /// any type in its output. It is a write-once cache; values are never evicted,
 234 /// which means that references to the value can safely be returned from the
 235 /// `get()` method.
 236 #[derive(Debug)]
 237 pub struct Cache(
 238     RefCell<HashMap<
 239         TypeId,
 240         Box<dyn Any>, // actually a HashMap<Step, Interned<Step::Output>>
 241     >>
 242 );
 243
 244 impl Cache {
 245     pub fn new() -> Cache {
 246         Cache(RefCell::new(HashMap::new()))
 247     }
 248
 249     pub fn put<S: Step>(&self, step: S, value: S::Output) {
 250         let mut cache = self.0.borrow_mut();
 251         let type_id = TypeId::of::<S>();
 252         let stepcache = cache.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.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.remove(&type_id)
 277             .map(|b| b.downcast::<HashMap<S, S::Output>>().expect("correct type"))
 278             .map(|m| m.into_iter().collect::<Vec<_>>())
 279             .unwrap_or_default();
 280         v.sort_by_key(|&(a, _)| a);
 281         v
 282     }
 283
 284     pub fn contains<S: Step>(&self) -> bool {
 285         self.0.borrow().contains_key(&TypeId::of::<S>())
 286     }
 287 }