src/libextra/workcache.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 #[allow(missing_doc)];
  12
  13 use digest::Digest;
  14 use json;
  15 use sha1::Sha1;
  16 use serialize::{Encoder, Encodable, Decoder, Decodable};
  17 use arc::{Arc,RWArc};
  18 use treemap::TreeMap;
  19
  20 use std::cell::Cell;
  21 use std::comm::{PortOne, oneshot, send_one, recv_one};
  22 use std::either::{Either, Left, Right};
  23 use std::io;
  24 use std::run;
  25 use std::task;
  26
  27 /**
  28 *
  29 * This is a loose clone of the [fbuild build system](https://github.com/felix-lang/fbuild),
  30 * made a touch more generic (not wired to special cases on files) and much
  31 * less metaprogram-y due to rust's comparative weakness there, relative to
  32 * python.
  33 *
  34 * It's based around _imperative builds_ that happen to have some function
  35 * calls cached. That is, it's _just_ a mechanism for describing cached
  36 * functions. This makes it much simpler and smaller than a "build system"
  37 * that produces an IR and evaluates it. The evaluation order is normal
  38 * function calls. Some of them just return really quickly.
  39 *
  40 * A cached function consumes and produces a set of _works_. A work has a
  41 * name, a kind (that determines how the value is to be checked for
  42 * freshness) and a value. Works must also be (de)serializable. Some
  43 * examples of works:
  44 *
  45 *    kind   name    value
  46 *   ------------------------
  47 *    cfg    os      linux
  48 *    file   foo.c   <sha1>
  49 *    url    foo.com <etag>
  50 *
  51 * Works are conceptually single units, but we store them most of the time
  52 * in maps of the form (type,name) => value. These are WorkMaps.
  53 *
  54 * A cached function divides the works it's interested in into inputs and
  55 * outputs, and subdivides those into declared (input) works and
  56 * discovered (input and output) works.
  57 *
  58 * A _declared_ input or is one that is given to the workcache before
  59 * any work actually happens, in the "prep" phase. Even when a function's
  60 * work-doing part (the "exec" phase) never gets called, it has declared
  61 * inputs, which can be checked for freshness (and potentially
  62 * used to determine that the function can be skipped).
  63 *
  64 * The workcache checks _all_ works for freshness, but uses the set of
  65 * discovered outputs from the _previous_ exec (which it will re-discover
  66 * and re-record each time the exec phase runs).
  67 *
  68 * Therefore the discovered works cached in the db might be a
  69 * mis-approximation of the current discoverable works, but this is ok for
  70 * the following reason: we assume that if an artifact A changed from
  71 * depending on B,C,D to depending on B,C,D,E, then A itself changed (as
  72 * part of the change-in-dependencies), so we will be ok.
  73 *
  74 * Each function has a single discriminated output work called its _result_.
  75 * This is only different from other works in that it is returned, by value,
  76 * from a call to the cacheable function; the other output works are used in
  77 * passing to invalidate dependencies elsewhere in the cache, but do not
  78 * otherwise escape from a function invocation. Most functions only have one
  79 * output work anyways.
  80 *
  81 * A database (the central store of a workcache) stores a mappings:
  82 *
  83 * (fn_name,{declared_input}) => ({discovered_input},
  84 *                                {discovered_output},result)
  85 *
  86 * (Note: fbuild, which workcache is based on, has the concept of a declared
  87 * output as separate from a discovered output. This distinction exists only
  88 * as an artifact of how fbuild works: via annotations on function types
  89 * and metaprogramming, with explicit dependency declaration as a fallback.
  90 * Workcache is more explicit about dependencies, and as such treats all
  91 * outputs the same, as discovered-during-the-last-run.)
  92 *
  93 */
  94
  95 #[deriving(Clone, Eq, Encodable, Decodable, TotalOrd, TotalEq)]
  96 struct WorkKey {
  97     kind: ~str,
  98     name: ~str
  99 }
 100
 101 impl WorkKey {
 102     pub fn new(kind: &str, name: &str) -> WorkKey {
 103         WorkKey {
 104             kind: kind.to_owned(),
 105             name: name.to_owned(),
 106         }
 107     }
 108 }
 109
 110 #[deriving(Clone, Eq, Encodable, Decodable)]
 111 struct WorkMap(TreeMap<WorkKey, ~str>);
 112
 113 impl WorkMap {
 114     fn new() -> WorkMap { WorkMap(TreeMap::new()) }
 115 }
 116
 117 struct Database {
 118     db_filename: Path,
 119     db_cache: TreeMap<~str, ~str>,
 120     db_dirty: bool
 121 }
 122
 123 impl Database {
 124
 125     pub fn new(p: Path) -> Database {
 126         Database {
 127             db_filename: p,
 128             db_cache: TreeMap::new(),
 129             db_dirty: false
 130         }
 131     }
 132
 133     pub fn prepare(&self,
 134                    fn_name: &str,
 135                    declared_inputs: &WorkMap)
 136                    -> Option<(WorkMap, WorkMap, ~str)> {
 137         let k = json_encode(&(fn_name, declared_inputs));
 138         match self.db_cache.find(&k) {
 139             None => None,
 140             Some(v) => Some(json_decode(*v))
 141         }
 142     }
 143
 144     pub fn cache(&mut self,
 145                  fn_name: &str,
 146                  declared_inputs: &WorkMap,
 147                  discovered_inputs: &WorkMap,
 148                  discovered_outputs: &WorkMap,
 149                  result: &str) {
 150         let k = json_encode(&(fn_name, declared_inputs));
 151         let v = json_encode(&(discovered_inputs,
 152                               discovered_outputs,
 153                               result));
 154         self.db_cache.insert(k,v);
 155         self.db_dirty = true
 156     }
 157 }
 158
 159 struct Logger {
 160     // FIXME #4432: Fill in
 161     a: ()
 162 }
 163
 164 impl Logger {
 165
 166     pub fn new() -> Logger {
 167         Logger { a: () }
 168     }
 169
 170     pub fn info(&self, i: &str) {
 171         io::println(~"workcache: " + i);
 172     }
 173 }
 174
 175 #[deriving(Clone)]
 176 struct Context {
 177     db: RWArc<Database>,
 178     logger: RWArc<Logger>,
 179     cfg: Arc<json::Object>,
 180     freshness: Arc<TreeMap<~str,extern fn(&str,&str)->bool>>
 181 }
 182
 183 struct Prep<'self> {
 184     ctxt: &'self Context,
 185     fn_name: &'self str,
 186     declared_inputs: WorkMap,
 187 }
 188
 189 struct Exec {
 190     discovered_inputs: WorkMap,
 191     discovered_outputs: WorkMap
 192 }
 193
 194 struct Work<'self, T> {
 195     prep: &'self Prep<'self>,
 196     res: Option<Either<T,PortOne<(Exec,T)>>>
 197 }
 198
 199 fn json_encode<T:Encodable<json::Encoder>>(t: &T) -> ~str {
 200     do io::with_str_writer |wr| {
 201         let mut encoder = json::Encoder(wr);
 202         t.encode(&mut encoder);
 203     }
 204 }
 205
 206 // FIXME(#5121)
 207 fn json_decode<T:Decodable<json::Decoder>>(s: &str) -> T {
 208     do io::with_str_reader(s) |rdr| {
 209         let j = json::from_reader(rdr).unwrap();
 210         let mut decoder = json::Decoder(j);
 211         Decodable::decode(&mut decoder)
 212     }
 213 }
 214
 215 fn digest<T:Encodable<json::Encoder>>(t: &T) -> ~str {
 216     let mut sha = ~Sha1::new();
 217     (*sha).input_str(json_encode(t));
 218     (*sha).result_str()
 219 }
 220
 221 fn digest_file(path: &Path) -> ~str {
 222     let mut sha = ~Sha1::new();
 223     let s = io::read_whole_file_str(path);
 224     (*sha).input_str(*s.get_ref());
 225     (*sha).result_str()
 226 }
 227
 228 impl Context {
 229
 230     pub fn new(db: RWArc<Database>,
 231                lg: RWArc<Logger>,
 232                cfg: Arc<json::Object>) -> Context {
 233         Context {
 234             db: db,
 235             logger: lg,
 236             cfg: cfg,
 237             freshness: Arc::new(TreeMap::new())
 238         }
 239     }
 240
 241     pub fn prep<'a>(&'a self, fn_name: &'a str) -> Prep<'a> {
 242         Prep::new(self, fn_name)
 243     }
 244
 245     pub fn with_prep<'a, T>(&'a self, fn_name: &'a str, blk: &fn(p: &mut Prep) -> T) -> T {
 246         let mut p = self.prep(fn_name);
 247         blk(&mut p)
 248     }
 249
 250 }
 251
 252 impl<'self> Prep<'self> {
 253     fn new(ctxt: &'self Context, fn_name: &'self str) -> Prep<'self> {
 254         Prep {
 255             ctxt: ctxt,
 256             fn_name: fn_name,
 257             declared_inputs: WorkMap::new()
 258         }
 259     }
 260 }
 261
 262 impl<'self> Prep<'self> {
 263     fn declare_input(&mut self, kind:&str, name:&str, val:&str) {
 264         self.declared_inputs.insert(WorkKey::new(kind, name),
 265                                  val.to_owned());
 266     }
 267
 268     fn is_fresh(&self, cat: &str, kind: &str,
 269                 name: &str, val: &str) -> bool {
 270         let k = kind.to_owned();
 271         let f = self.ctxt.freshness.get().find(&k);
 272         let fresh = match f {
 273             None => fail!("missing freshness-function for '%s'", kind),
 274             Some(f) => (*f)(name, val)
 275         };
 276         do self.ctxt.logger.write |lg| {
 277             if fresh {
 278                 lg.info(fmt!("%s %s:%s is fresh",
 279                              cat, kind, name));
 280             } else {
 281                 lg.info(fmt!("%s %s:%s is not fresh",
 282                              cat, kind, name))
 283             }
 284         };
 285         fresh
 286     }
 287
 288     fn all_fresh(&self, cat: &str, map: &WorkMap) -> bool {
 289         for (k, v) in map.iter() {
 290             if ! self.is_fresh(cat, k.kind, k.name, *v) {
 291                 return false;
 292             }
 293         }
 294         return true;
 295     }
 296
 297     fn exec<T:Send +
 298         Encodable<json::Encoder> +
 299         Decodable<json::Decoder>>(
 300             &'self self, blk: ~fn(&Exec) -> T) -> T {
 301         self.exec_work(blk).unwrap()
 302     }
 303
 304     fn exec_work<T:Send +
 305         Encodable<json::Encoder> +
 306         Decodable<json::Decoder>>( // FIXME(#5121)
 307             &'self self, blk: ~fn(&Exec) -> T) -> Work<'self, T> {
 308         let mut bo = Some(blk);
 309
 310         let cached = do self.ctxt.db.read |db| {
 311             db.prepare(self.fn_name, &self.declared_inputs)
 312         };
 313
 314         let res = match cached {
 315             Some((ref disc_in, ref disc_out, ref res))
 316             if self.all_fresh("declared input",&self.declared_inputs) &&
 317                self.all_fresh("discovered input", disc_in) &&
 318                self.all_fresh("discovered output", disc_out) => {
 319                 Left(json_decode(*res))
 320             }
 321
 322             _ => {
 323                 let (port, chan) = oneshot();
 324                 let blk = bo.take_unwrap();
 325                 let chan = Cell::new(chan);
 326
 327                 do task::spawn {
 328                     let exe = Exec {
 329                         discovered_inputs: WorkMap::new(),
 330                         discovered_outputs: WorkMap::new(),
 331                     };
 332                     let chan = chan.take();
 333                     let v = blk(&exe);
 334                     send_one(chan, (exe, v));
 335                 }
 336                 Right(port)
 337             }
 338         };
 339         Work::new(self, res)
 340     }
 341 }
 342
 343 impl<'self, T:Send +
 344        Encodable<json::Encoder> +
 345        Decodable<json::Decoder>>
 346     Work<'self, T> { // FIXME(#5121)
 347
 348     pub fn new(p: &'self Prep<'self>, e: Either<T,PortOne<(Exec,T)>>) -> Work<'self, T> {
 349         Work { prep: p, res: Some(e) }
 350     }
 351
 352     pub fn unwrap(self) -> T {
 353         let Work { prep, res } = self;
 354         match res {
 355             None => fail!(),
 356             Some(Left(v)) => v,
 357             Some(Right(port)) => {
 358                 let (exe, v) = recv_one(port);
 359                 let s = json_encode(&v);
 360                 do prep.ctxt.db.write |db| {
 361                     db.cache(prep.fn_name,
 362                              &prep.declared_inputs,
 363                              &exe.discovered_inputs,
 364                              &exe.discovered_outputs,
 365                              s);
 366                 }
 367                 v
 368             }
 369         }
 370     }
 371 }
 372
 373
 374 //#[test]
 375 fn test() {
 376     use std::io::WriterUtil;
 377
 378     let pth = Path("foo.c");
 379     {
 380         let r = io::file_writer(&pth, [io::Create]);
 381         r.get_ref().write_str("int main() { return 0; }");
 382     }
 383
 384     let cx = Context::new(RWArc::new(Database::new(Path("db.json"))),
 385                           RWArc::new(Logger::new()),
 386                           Arc::new(TreeMap::new()));
 387
 388     let s = do cx.with_prep("test1") |prep| {
 389
 390         let subcx = cx.clone();
 391
 392         prep.declare_input("file", pth.to_str(), digest_file(&pth));
 393         do prep.exec |_exe| {
 394             let out = Path("foo.o");
 395             run::process_status("gcc", [~"foo.c", ~"-o", out.to_str()]);
 396
 397             let _proof_of_concept = subcx.prep("subfn");
 398             // Could run sub-rules inside here.
 399
 400             out.to_str()
 401         }
 402     };
 403     io::println(s);
 404 }