src/bootstrap/cache.rs

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