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