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::{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 #[deriving(Clone)]
 178 struct Context {
 179     db: RWARC<Database>,
 180     logger: RWARC<Logger>,
 181     cfg: ARC<json::Object>,
 182     freshness: ARC<TreeMap<~str,extern fn(&str,&str)->bool>>
 183 }
 184
 185 struct Prep<'self> {
 186     ctxt: &'self Context,
 187     fn_name: &'self str,
 188     declared_inputs: WorkMap,
 189 }
 190
 191 struct Exec {
 192     discovered_inputs: WorkMap,
 193     discovered_outputs: WorkMap
 194 }
 195
 196 struct Work<'self, T> {
 197     prep: &'self Prep<'self>,
 198     res: Option<Either<T,PortOne<(Exec,T)>>>
 199 }
 200
 201 fn json_encode<T:Encodable<json::Encoder>>(t: &T) -> ~str {
 202     do io::with_str_writer |wr| {
 203         let mut encoder = json::Encoder(wr);
 204         t.encode(&mut encoder);
 205     }
 206 }
 207
 208 // FIXME(#5121)
 209 fn json_decode<T:Decodable<json::Decoder>>(s: &str) -> T {
 210     do io::with_str_reader(s) |rdr| {
 211         let j = result::unwrap(json::from_reader(rdr));
 212         let mut decoder = json::Decoder(j);
 213         Decodable::decode(&mut decoder)
 214     }
 215 }
 216
 217 fn digest<T:Encodable<json::Encoder>>(t: &T) -> ~str {
 218     let mut sha = ~Sha1::new();
 219     (*sha).input_str(json_encode(t));
 220     (*sha).result_str()
 221 }
 222
 223 fn digest_file(path: &Path) -> ~str {
 224     let mut sha = ~Sha1::new();
 225     let s = io::read_whole_file_str(path);
 226     (*sha).input_str(*s.get_ref());
 227     (*sha).result_str()
 228 }
 229
 230 impl Context {
 231
 232     pub fn new(db: RWARC<Database>,
 233                lg: RWARC<Logger>,
 234                cfg: ARC<json::Object>) -> Context {
 235         Context {
 236             db: db,
 237             logger: lg,
 238             cfg: cfg,
 239             freshness: ARC(TreeMap::new())
 240         }
 241     }
 242
 243     pub fn prep<'a>(&'a self, fn_name: &'a str) -> Prep<'a> {
 244         Prep::new(self, fn_name)
 245     }
 246
 247     pub fn with_prep<'a, T>(&'a self, fn_name: &'a str, blk: &fn(p: &mut Prep) -> T) -> T {
 248         let mut p = self.prep(fn_name);
 249         blk(&mut p)
 250     }
 251
 252 }
 253
 254 impl<'self> Prep<'self> {
 255     fn new(ctxt: &'self Context, fn_name: &'self str) -> Prep<'self> {
 256         Prep {
 257             ctxt: ctxt,
 258             fn_name: fn_name,
 259             declared_inputs: WorkMap::new()
 260         }
 261     }
 262 }
 263
 264 impl<'self> Prep<'self> {
 265     fn declare_input(&mut self, kind:&str, name:&str, val:&str) {
 266         self.declared_inputs.insert(WorkKey::new(kind, name),
 267                                  val.to_owned());
 268     }
 269
 270     fn is_fresh(&self, cat: &str, kind: &str,
 271                 name: &str, val: &str) -> bool {
 272         let k = kind.to_owned();
 273         let f = self.ctxt.freshness.get().find(&k);
 274         let fresh = match f {
 275             None => fail!("missing freshness-function for '%s'", kind),
 276             Some(f) => (*f)(name, val)
 277         };
 278         do self.ctxt.logger.write |lg| {
 279             if fresh {
 280                 lg.info(fmt!("%s %s:%s is fresh",
 281                              cat, kind, name));
 282             } else {
 283                 lg.info(fmt!("%s %s:%s is not fresh",
 284                              cat, kind, name))
 285             }
 286         };
 287         fresh
 288     }
 289
 290     fn all_fresh(&self, cat: &str, map: &WorkMap) -> bool {
 291         for map.iter().advance |(k, v)| {
 292             if ! self.is_fresh(cat, k.kind, k.name, *v) {
 293                 return false;
 294             }
 295         }
 296         return true;
 297     }
 298
 299     fn exec<T:Send +
 300         Encodable<json::Encoder> +
 301         Decodable<json::Decoder>>(
 302             &'self self, blk: ~fn(&Exec) -> T) -> T {
 303         self.exec_work(blk).unwrap()
 304     }
 305
 306     fn exec_work<T:Send +
 307         Encodable<json::Encoder> +
 308         Decodable<json::Decoder>>( // FIXME(#5121)
 309             &'self self, blk: ~fn(&Exec) -> T) -> Work<'self, T> {
 310         let mut bo = Some(blk);
 311
 312         let cached = do self.ctxt.db.read |db| {
 313             db.prepare(self.fn_name, &self.declared_inputs)
 314         };
 315
 316         let res = match cached {
 317             Some((ref disc_in, ref disc_out, ref res))
 318             if self.all_fresh("declared input",&self.declared_inputs) &&
 319                self.all_fresh("discovered input", disc_in) &&
 320                self.all_fresh("discovered output", disc_out) => {
 321                 Left(json_decode(*res))
 322             }
 323
 324             _ => {
 325                 let (port, chan) = oneshot();
 326                 let blk = bo.take_unwrap();
 327                 let chan = Cell::new(chan);
 328
 329                 do task::spawn {
 330                     let exe = Exec {
 331                         discovered_inputs: WorkMap::new(),
 332                         discovered_outputs: WorkMap::new(),
 333                     };
 334                     let chan = chan.take();
 335                     let v = blk(&exe);
 336                     send_one(chan, (exe, v));
 337                 }
 338                 Right(port)
 339             }
 340         };
 341         Work::new(self, res)
 342     }
 343 }
 344
 345 impl<'self, T:Send +
 346        Encodable<json::Encoder> +
 347        Decodable<json::Decoder>>
 348     Work<'self, T> { // FIXME(#5121)
 349
 350     pub fn new(p: &'self Prep<'self>, e: Either<T,PortOne<(Exec,T)>>) -> Work<'self, T> {
 351         Work { prep: p, res: Some(e) }
 352     }
 353
 354     pub fn unwrap(self) -> T {
 355         let Work { prep, res } = self;
 356         match res {
 357             None => fail!(),
 358             Some(Left(v)) => v,
 359             Some(Right(port)) => {
 360                 let (exe, v) = recv_one(port);
 361                 let s = json_encode(&v);
 362                 do prep.ctxt.db.write |db| {
 363                     db.cache(prep.fn_name,
 364                              &prep.declared_inputs,
 365                              &exe.discovered_inputs,
 366                              &exe.discovered_outputs,
 367                              s);
 368                 }
 369                 v
 370             }
 371         }
 372     }
 373 }
 374
 375
 376 //#[test]
 377 fn test() {
 378     use std::io::WriterUtil;
 379
 380     let pth = Path("foo.c");
 381     {
 382         let r = io::file_writer(&pth, [io::Create]);
 383         r.get_ref().write_str("int main() { return 0; }");
 384     }
 385
 386     let cx = Context::new(RWARC(Database::new(Path("db.json"))),
 387                           RWARC(Logger::new()),
 388                           ARC(TreeMap::new()));
 389
 390     let s = do cx.with_prep("test1") |prep| {
 391
 392         let subcx = cx.clone();
 393
 394         prep.declare_input("file", pth.to_str(), digest_file(&pth));
 395         do prep.exec |_exe| {
 396             let out = Path("foo.o");
 397             run::process_status("gcc", [~"foo.c", ~"-o", out.to_str()]);
 398
 399             let _proof_of_concept = subcx.prep("subfn");
 400             // Could run sub-rules inside here.
 401
 402             out.to_str()
 403         }
 404     };
 405     io::println(s);
 406 }