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