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