src/libworkcache/lib.rs

   1 // Copyright 2012-2013 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 #![crate_id = "workcache#0.10-pre"]
  12 #![crate_type = "rlib"]
  13 #![crate_type = "dylib"]
  14 #![license = "MIT/ASL2"]
  15 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  16        html_favicon_url = "http://www.rust-lang.org/favicon.ico",
  17        html_root_url = "http://static.rust-lang.org/doc/master")]
  18 #![feature(phase)]
  19 #![allow(visible_private_types)]
  20
  21 #[phase(syntax, link)] extern crate log;
  22 extern crate serialize;
  23 extern crate collections;
  24 extern crate sync;
  25
  26 use serialize::json;
  27 use serialize::json::ToJson;
  28 use serialize::{Encoder, Encodable, Decoder, Decodable};
  29 use sync::{Arc, RWLock};
  30 use collections::TreeMap;
  31 use std::str;
  32 use std::io;
  33 use std::io::{File, MemWriter};
  34
  35 /**
  36 *
  37 * This is a loose clone of the [fbuild build system](https://github.com/felix-lang/fbuild),
  38 * made a touch more generic (not wired to special cases on files) and much
  39 * less metaprogram-y due to rust's comparative weakness there, relative to
  40 * python.
  41 *
  42 * It's based around _imperative builds_ that happen to have some function
  43 * calls cached. That is, it's _just_ a mechanism for describing cached
  44 * functions. This makes it much simpler and smaller than a "build system"
  45 * that produces an IR and evaluates it. The evaluation order is normal
  46 * function calls. Some of them just return really quickly.
  47 *
  48 * A cached function consumes and produces a set of _works_. A work has a
  49 * name, a kind (that determines how the value is to be checked for
  50 * freshness) and a value. Works must also be (de)serializable. Some
  51 * examples of works:
  52 *
  53 *    kind   name    value
  54 *   ------------------------
  55 *    cfg    os      linux
  56 *    file   foo.c   <sha1>
  57 *    url    foo.com <etag>
  58 *
  59 * Works are conceptually single units, but we store them most of the time
  60 * in maps of the form (type,name) => value. These are WorkMaps.
  61 *
  62 * A cached function divides the works it's interested in into inputs and
  63 * outputs, and subdivides those into declared (input) works and
  64 * discovered (input and output) works.
  65 *
  66 * A _declared_ input or is one that is given to the workcache before
  67 * any work actually happens, in the "prep" phase. Even when a function's
  68 * work-doing part (the "exec" phase) never gets called, it has declared
  69 * inputs, which can be checked for freshness (and potentially
  70 * used to determine that the function can be skipped).
  71 *
  72 * The workcache checks _all_ works for freshness, but uses the set of
  73 * discovered outputs from the _previous_ exec (which it will re-discover
  74 * and re-record each time the exec phase runs).
  75 *
  76 * Therefore the discovered works cached in the db might be a
  77 * mis-approximation of the current discoverable works, but this is ok for
  78 * the following reason: we assume that if an artifact A changed from
  79 * depending on B,C,D to depending on B,C,D,E, then A itself changed (as
  80 * part of the change-in-dependencies), so we will be ok.
  81 *
  82 * Each function has a single discriminated output work called its _result_.
  83 * This is only different from other works in that it is returned, by value,
  84 * from a call to the cacheable function; the other output works are used in
  85 * passing to invalidate dependencies elsewhere in the cache, but do not
  86 * otherwise escape from a function invocation. Most functions only have one
  87 * output work anyways.
  88 *
  89 * A database (the central store of a workcache) stores a mappings:
  90 *
  91 * (fn_name,{declared_input}) => ({discovered_input},
  92 *                                {discovered_output},result)
  93 *
  94 * (Note: fbuild, which workcache is based on, has the concept of a declared
  95 * output as separate from a discovered output. This distinction exists only
  96 * as an artifact of how fbuild works: via annotations on function types
  97 * and metaprogramming, with explicit dependency declaration as a fallback.
  98 * Workcache is more explicit about dependencies, and as such treats all
  99 * outputs the same, as discovered-during-the-last-run.)
 100 *
 101 */
 102
 103 #[deriving(Clone, Eq, Encodable, Decodable, Ord, TotalOrd, TotalEq)]
 104 struct WorkKey {
 105     kind: ~str,
 106     name: ~str
 107 }
 108
 109 impl WorkKey {
 110     pub fn new(kind: &str, name: &str) -> WorkKey {
 111         WorkKey {
 112             kind: kind.to_owned(),
 113             name: name.to_owned(),
 114         }
 115     }
 116 }
 117
 118 // FIXME #8883: The key should be a WorkKey and not a ~str.
 119 // This is working around some JSON weirdness.
 120 #[deriving(Clone, Eq, Encodable, Decodable)]
 121 struct WorkMap(TreeMap<~str, KindMap>);
 122
 123 #[deriving(Clone, Eq, Encodable, Decodable)]
 124 struct KindMap(TreeMap<~str, ~str>);
 125
 126 impl WorkMap {
 127     fn new() -> WorkMap { WorkMap(TreeMap::new()) }
 128
 129     fn insert_work_key(&mut self, k: WorkKey, val: ~str) {
 130         let WorkKey { kind, name } = k;
 131         let WorkMap(ref mut map) = *self;
 132         match map.find_mut(&name) {
 133             Some(&KindMap(ref mut m)) => { m.insert(kind, val); return; }
 134             None => ()
 135         }
 136         let mut new_map = TreeMap::new();
 137         new_map.insert(kind, val);
 138         map.insert(name, KindMap(new_map));
 139     }
 140 }
 141
 142 pub struct Database {
 143     priv db_filename: Path,
 144     priv db_cache: TreeMap<~str, ~str>,
 145     db_dirty: bool
 146 }
 147
 148 impl Database {
 149
 150     pub fn new(p: Path) -> Database {
 151         let mut rslt = Database {
 152             db_filename: p,
 153             db_cache: TreeMap::new(),
 154             db_dirty: false
 155         };
 156         if rslt.db_filename.exists() {
 157             rslt.load();
 158         }
 159         rslt
 160     }
 161
 162     pub fn prepare(&self,
 163                    fn_name: &str,
 164                    declared_inputs: &WorkMap)
 165                    -> Option<(WorkMap, WorkMap, ~str)> {
 166         let k = json_encode(&(fn_name, declared_inputs));
 167         match self.db_cache.find(&k) {
 168             None => None,
 169             Some(v) => Some(json_decode(*v))
 170         }
 171     }
 172
 173     pub fn cache(&mut self,
 174                  fn_name: &str,
 175                  declared_inputs: &WorkMap,
 176                  discovered_inputs: &WorkMap,
 177                  discovered_outputs: &WorkMap,
 178                  result: &str) {
 179         let k = json_encode(&(fn_name, declared_inputs));
 180         let v = json_encode(&(discovered_inputs,
 181                               discovered_outputs,
 182                               result));
 183         self.db_cache.insert(k,v);
 184         self.db_dirty = true
 185     }
 186
 187     // FIXME #4330: This should have &mut self and should set self.db_dirty to false.
 188     fn save(&self) -> io::IoResult<()> {
 189         let mut f = File::create(&self.db_filename);
 190         self.db_cache.to_json().to_pretty_writer(&mut f)
 191     }
 192
 193     fn load(&mut self) {
 194         assert!(!self.db_dirty);
 195         assert!(self.db_filename.exists());
 196         match File::open(&self.db_filename) {
 197             Err(e) => fail!("Couldn't load workcache database {}: {}",
 198                             self.db_filename.display(),
 199                             e),
 200             Ok(mut stream) => {
 201                 match json::from_reader(&mut stream) {
 202                     Err(e) => fail!("Couldn't parse workcache database (from file {}): {}",
 203                                     self.db_filename.display(), e.to_str()),
 204                     Ok(r) => {
 205                         let mut decoder = json::Decoder::new(r);
 206                         self.db_cache = Decodable::decode(&mut decoder).unwrap();
 207                     }
 208                 }
 209             }
 210         }
 211     }
 212 }
 213
 214 #[unsafe_destructor]
 215 impl Drop for Database {
 216     fn drop(&mut self) {
 217         if self.db_dirty {
 218             // FIXME: is failing the right thing to do here
 219             self.save().unwrap();
 220         }
 221     }
 222 }
 223
 224 pub type FreshnessMap = TreeMap<~str,extern fn(&str,&str)->bool>;
 225
 226 #[deriving(Clone)]
 227 pub struct Context {
 228     db: Arc<RWLock<Database>>,
 229     priv cfg: Arc<json::Object>,
 230     /// Map from kinds (source, exe, url, etc.) to a freshness function.
 231     /// The freshness function takes a name (e.g. file path) and value
 232     /// (e.g. hash of file contents) and determines whether it's up-to-date.
 233     /// For example, in the file case, this would read the file off disk,
 234     /// hash it, and return the result of comparing the given hash and the
 235     /// read hash for equality.
 236     priv freshness: Arc<FreshnessMap>
 237 }
 238
 239 pub struct Prep<'a> {
 240     priv ctxt: &'a Context,
 241     priv fn_name: &'a str,
 242     priv declared_inputs: WorkMap,
 243 }
 244
 245 pub struct Exec {
 246     priv discovered_inputs: WorkMap,
 247     priv discovered_outputs: WorkMap
 248 }
 249
 250 enum Work<'a, T> {
 251     WorkValue(T),
 252     WorkFromTask(&'a Prep<'a>, Receiver<(Exec, T)>),
 253 }
 254
 255 fn json_encode<'a, T:Encodable<json::Encoder<'a>, io::IoError>>(t: &T) -> ~str {
 256     let mut writer = MemWriter::new();
 257     let mut encoder = json::Encoder::new(&mut writer as &mut io::Writer);
 258     let _ = t.encode(&mut encoder);
 259     str::from_utf8_owned(writer.unwrap()).unwrap()
 260 }
 261
 262 // FIXME(#5121)
 263 fn json_decode<T:Decodable<json::Decoder, json::Error>>(s: &str) -> T {
 264     debug!("json decoding: {}", s);
 265     let j = json::from_str(s).unwrap();
 266     let mut decoder = json::Decoder::new(j);
 267     Decodable::decode(&mut decoder).unwrap()
 268 }
 269
 270 impl Context {
 271
 272     pub fn new(db: Arc<RWLock<Database>>,
 273                cfg: Arc<json::Object>) -> Context {
 274         Context::new_with_freshness(db, cfg, Arc::new(TreeMap::new()))
 275     }
 276
 277     pub fn new_with_freshness(db: Arc<RWLock<Database>>,
 278                               cfg: Arc<json::Object>,
 279                               freshness: Arc<FreshnessMap>) -> Context {
 280         Context {
 281             db: db,
 282             cfg: cfg,
 283             freshness: freshness
 284         }
 285     }
 286
 287     pub fn prep<'a>(&'a self, fn_name: &'a str) -> Prep<'a> {
 288         Prep::new(self, fn_name)
 289     }
 290
 291     pub fn with_prep<'a,
 292                      T>(
 293                      &'a self,
 294                      fn_name: &'a str,
 295                      blk: |p: &mut Prep| -> T)
 296                      -> T {
 297         let mut p = self.prep(fn_name);
 298         blk(&mut p)
 299     }
 300
 301 }
 302
 303 impl Exec {
 304     pub fn discover_input(&mut self,
 305                           dependency_kind: &str,
 306                           dependency_name: &str,
 307                           dependency_val: &str) {
 308         debug!("Discovering input {} {} {}", dependency_kind, dependency_name, dependency_val);
 309         self.discovered_inputs.insert_work_key(WorkKey::new(dependency_kind, dependency_name),
 310                                  dependency_val.to_owned());
 311     }
 312     pub fn discover_output(&mut self,
 313                            dependency_kind: &str,
 314                            dependency_name: &str,
 315                            dependency_val: &str) {
 316         debug!("Discovering output {} {} {}", dependency_kind, dependency_name, dependency_val);
 317         self.discovered_outputs.insert_work_key(WorkKey::new(dependency_kind, dependency_name),
 318                                  dependency_val.to_owned());
 319     }
 320
 321     // returns pairs of (kind, name)
 322     pub fn lookup_discovered_inputs(&self) -> ~[(~str, ~str)] {
 323         let mut rs = ~[];
 324         let WorkMap(ref discovered_inputs) = self.discovered_inputs;
 325         for (k, v) in discovered_inputs.iter() {
 326             let KindMap(ref vmap) = *v;
 327             for (k1, _) in vmap.iter() {
 328                 rs.push((k1.clone(), k.clone()));
 329             }
 330         }
 331         rs
 332     }
 333 }
 334
 335 impl<'a> Prep<'a> {
 336     fn new(ctxt: &'a Context, fn_name: &'a str) -> Prep<'a> {
 337         Prep {
 338             ctxt: ctxt,
 339             fn_name: fn_name,
 340             declared_inputs: WorkMap::new()
 341         }
 342     }
 343
 344     pub fn lookup_declared_inputs(&self) -> ~[~str] {
 345         let mut rs = ~[];
 346         let WorkMap(ref declared_inputs) = self.declared_inputs;
 347         for (_, v) in declared_inputs.iter() {
 348             let KindMap(ref vmap) = *v;
 349             for (inp, _) in vmap.iter() {
 350                 rs.push(inp.clone());
 351             }
 352         }
 353         rs
 354     }
 355 }
 356
 357 impl<'a> Prep<'a> {
 358     pub fn declare_input(&mut self, kind: &str, name: &str, val: &str) {
 359         debug!("Declaring input {} {} {}", kind, name, val);
 360         self.declared_inputs.insert_work_key(WorkKey::new(kind, name),
 361                                  val.to_owned());
 362     }
 363
 364     fn is_fresh(&self, cat: &str, kind: &str,
 365                 name: &str, val: &str) -> bool {
 366         let k = kind.to_owned();
 367         let f = self.ctxt.freshness.deref().find(&k);
 368         debug!("freshness for: {}/{}/{}/{}", cat, kind, name, val)
 369         let fresh = match f {
 370             None => fail!("missing freshness-function for '{}'", kind),
 371             Some(f) => (*f)(name, val)
 372         };
 373         if fresh {
 374             info!("{} {}:{} is fresh", cat, kind, name);
 375         } else {
 376             info!("{} {}:{} is not fresh", cat, kind, name);
 377         }
 378         fresh
 379     }
 380
 381     fn all_fresh(&self, cat: &str, map: &WorkMap) -> bool {
 382         let WorkMap(ref map) = *map;
 383         for (k_name, kindmap) in map.iter() {
 384             let KindMap(ref kindmap_) = *kindmap;
 385             for (k_kind, v) in kindmap_.iter() {
 386                if ! self.is_fresh(cat, *k_kind, *k_name, *v) {
 387                   return false;
 388             }
 389           }
 390         }
 391         return true;
 392     }
 393
 394     pub fn exec<'a, T:Send +
 395         Encodable<json::Encoder<'a>, io::IoError> +
 396         Decodable<json::Decoder, json::Error>>(
 397             &'a self, blk: proc:Send(&mut Exec) -> T) -> T {
 398         self.exec_work(blk).unwrap()
 399     }
 400
 401     fn exec_work<'a, T:Send +
 402         Encodable<json::Encoder<'a>, io::IoError> +
 403         Decodable<json::Decoder, json::Error>>( // FIXME(#5121)
 404             &'a self, blk: proc:Send(&mut Exec) -> T) -> Work<'a, T> {
 405         let mut bo = Some(blk);
 406
 407         debug!("exec_work: looking up {} and {:?}", self.fn_name,
 408                self.declared_inputs);
 409         let cached = {
 410             let db = self.ctxt.db.deref().read();
 411             db.deref().prepare(self.fn_name, &self.declared_inputs)
 412         };
 413
 414         match cached {
 415             Some((ref disc_in, ref disc_out, ref res))
 416             if self.all_fresh("declared input",&self.declared_inputs) &&
 417                self.all_fresh("discovered input", disc_in) &&
 418                self.all_fresh("discovered output", disc_out) => {
 419                 debug!("Cache hit!");
 420                 debug!("Trying to decode: {:?} / {:?} / {}",
 421                        disc_in, disc_out, *res);
 422                 Work::from_value(json_decode(*res))
 423             }
 424
 425             _ => {
 426                 debug!("Cache miss!");
 427                 let (tx, rx) = channel();
 428                 let blk = bo.take_unwrap();
 429
 430                 // FIXME: What happens if the task fails?
 431                 spawn(proc() {
 432                     let mut exe = Exec {
 433                         discovered_inputs: WorkMap::new(),
 434                         discovered_outputs: WorkMap::new(),
 435                     };
 436                     let v = blk(&mut exe);
 437                     tx.send((exe, v));
 438                 });
 439                 Work::from_task(self, rx)
 440             }
 441         }
 442     }
 443 }
 444
 445 impl<'a, T:Send +
 446        Encodable<json::Encoder<'a>, io::IoError> +
 447        Decodable<json::Decoder, json::Error>>
 448     Work<'a, T> { // FIXME(#5121)
 449
 450     pub fn from_value(elt: T) -> Work<'a, T> {
 451         WorkValue(elt)
 452     }
 453     pub fn from_task(prep: &'a Prep<'a>, port: Receiver<(Exec, T)>)
 454         -> Work<'a, T> {
 455         WorkFromTask(prep, port)
 456     }
 457
 458     pub fn unwrap(self) -> T {
 459         match self {
 460             WorkValue(v) => v,
 461             WorkFromTask(prep, port) => {
 462                 let (exe, v) = port.recv();
 463                 let s = json_encode(&v);
 464                 let mut db = prep.ctxt.db.deref().write();
 465                 db.deref_mut().cache(prep.fn_name,
 466                                      &prep.declared_inputs,
 467                                      &exe.discovered_inputs,
 468                                      &exe.discovered_outputs,
 469                                      s);
 470                 v
 471             }
 472         }
 473     }
 474 }
 475
 476
 477 #[test]
 478 #[cfg(not(target_os="android"))] // FIXME(#10455)
 479 fn test() {
 480     use std::os;
 481     use std::io::{fs, Process};
 482     use std::str::from_utf8_owned;
 483
 484     // Create a path to a new file 'filename' in the directory in which
 485     // this test is running.
 486     fn make_path(filename: ~str) -> Path {
 487         let pth = os::self_exe_path().expect("workcache::test failed").with_filename(filename);
 488         if pth.exists() {
 489             fs::unlink(&pth).unwrap();
 490         }
 491         return pth;
 492     }
 493
 494     let pth = make_path(~"foo.c");
 495     File::create(&pth).write(bytes!("int main() { return 0; }")).unwrap();
 496
 497     let db_path = make_path(~"db.json");
 498
 499     let cx = Context::new(Arc::new(RWLock::new(Database::new(db_path))),
 500                           Arc::new(TreeMap::new()));
 501
 502     let s = cx.with_prep("test1", |prep| {
 503
 504         let subcx = cx.clone();
 505         let pth = pth.clone();
 506
 507         let contents = File::open(&pth).read_to_end().unwrap();
 508         let file_content = from_utf8_owned(contents).unwrap();
 509
 510         // FIXME (#9639): This needs to handle non-utf8 paths
 511         prep.declare_input("file", pth.as_str().unwrap(), file_content);
 512         prep.exec(proc(_exe) {
 513             let out = make_path(~"foo.o");
 514             // FIXME (#9639): This needs to handle non-utf8 paths
 515             Process::status("gcc", [pth.as_str().unwrap().to_owned(),
 516                                     ~"-o",
 517                                     out.as_str().unwrap().to_owned()]).unwrap();
 518
 519             let _proof_of_concept = subcx.prep("subfn");
 520             // Could run sub-rules inside here.
 521
 522             // FIXME (#9639): This needs to handle non-utf8 paths
 523             out.as_str().unwrap().to_owned()
 524         })
 525     });
 526
 527     println!("{}", s);
 528 }