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> {
 173     items: Vec<T>,
 174     set: HashMap<T, Interned<T>>,
 175 }
 176
 177 impl<T: Hash + Clone + Eq> TyIntern<T> {
 178     fn new() -> TyIntern<T> {
 179         TyIntern {
 180             items: Vec::new(),
 181             set: HashMap::new(),
 182         }
 183     }
 184
 185     fn intern_borrow<B>(&mut self, item: &B) -> Interned<T>
 186     where
 187         B: Eq + Hash + ToOwned<Owned=T> + ?Sized,
 188         T: Borrow<B>,
 189     {
 190         if let Some(i) = self.set.get(&item) {
 191             return *i;
 192         }
 193         let item = item.to_owned();
 194         let interned =  Interned(self.items.len(), PhantomData::<*const T>);
 195         self.set.insert(item.clone(), interned);
 196         self.items.push(item);
 197         interned
 198     }
 199
 200     fn intern(&mut self, item: T) -> Interned<T> {
 201         if let Some(i) = self.set.get(&item) {
 202             return *i;
 203         }
 204         let interned =  Interned(self.items.len(), PhantomData::<*const T>);
 205         self.set.insert(item.clone(), interned);
 206         self.items.push(item);
 207         interned
 208     }
 209
 210     fn get(&self, i: Interned<T>) -> &T {
 211         &self.items[i.0]
 212     }
 213 }
 214
 215 pub struct Interner {
 216     strs: Mutex<TyIntern<String>>,
 217     paths: Mutex<TyIntern<PathBuf>>,
 218 }
 219
 220 impl Interner {
 221     fn new() -> Interner {
 222         Interner {
 223             strs: Mutex::new(TyIntern::new()),
 224             paths: Mutex::new(TyIntern::new()),
 225         }
 226     }
 227
 228     pub fn intern_str(&self, s: &str) -> Interned<String> {
 229         self.strs.lock().unwrap().intern_borrow(s)
 230     }
 231     pub fn intern_string(&self, s: String) -> Interned<String> {
 232         self.strs.lock().unwrap().intern(s)
 233     }
 234
 235     pub fn intern_path(&self, s: PathBuf) -> Interned<PathBuf> {
 236         self.paths.lock().unwrap().intern(s)
 237     }
 238 }
 239
 240 lazy_static! {
 241     pub static ref INTERNER: Interner = Interner::new();
 242 }
 243
 244 /// This is essentially a HashMap which allows storing any type in its input and
 245 /// any type in its output. It is a write-once cache; values are never evicted,
 246 /// which means that references to the value can safely be returned from the
 247 /// get() method.
 248 #[derive(Debug)]
 249 pub struct Cache(
 250     RefCell<HashMap<
 251         TypeId,
 252         Box<dyn Any>, // actually a HashMap<Step, Interned<Step::Output>>
 253     >>
 254 );
 255
 256 impl Cache {
 257     pub fn new() -> Cache {
 258         Cache(RefCell::new(HashMap::new()))
 259     }
 260
 261     pub fn put<S: Step>(&self, step: S, value: S::Output) {
 262         let mut cache = self.0.borrow_mut();
 263         let type_id = TypeId::of::<S>();
 264         let stepcache = cache.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         assert!(!stepcache.contains_key(&step), "processing {:?} a second time", step);
 269         stepcache.insert(step, value);
 270     }
 271
 272     pub fn get<S: Step>(&self, step: &S) -> Option<S::Output> {
 273         let mut cache = self.0.borrow_mut();
 274         let type_id = TypeId::of::<S>();
 275         let stepcache = cache.entry(type_id)
 276                         .or_insert_with(|| Box::new(HashMap::<S, S::Output>::new()))
 277                         .downcast_mut::<HashMap<S, S::Output>>()
 278                         .expect("invalid type mapped");
 279         stepcache.get(step).cloned()
 280     }
 281
 282     #[cfg(test)]
 283     pub fn all<S: Ord + Copy + Step>(&mut self) -> Vec<(S, S::Output)> {
 284         let cache = self.0.get_mut();
 285         let type_id = TypeId::of::<S>();
 286         let mut v = cache.remove(&type_id)
 287             .map(|b| b.downcast::<HashMap<S, S::Output>>().expect("correct type"))
 288             .map(|m| m.into_iter().collect::<Vec<_>>())
 289             .unwrap_or_default();
 290         v.sort_by_key(|&(a, _)| a);
 291         v
 292     }
 293 }