(index<- ) ./libworkcache/lib.rs
git branch: * master 5200215 auto merge of #14035 : alexcrichton/rust/experimental, r=huonw
modified: Fri May 9 13:02:28 2014
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::DecoderError>>(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::DecoderError>>(
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::DecoderError>>( // 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::DecoderError>>
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".to_owned());
496 File::create(&pth).write(bytes!("int main() { return 0; }")).unwrap();
497
498 let db_path = make_path("db.json".to_owned());
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".to_owned());
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".to_owned(),
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 }
libworkcache/lib.rs:104:69-104:69 -struct- definition:
struct WorkKey {
kind: ~str,
name: ~str
references:- 40libworkcache/lib.rs:263:16-263:16 -fn- definition:
// FIXME(#5121)
fn json_decode<T:Decodable<json::Decoder, json::DecoderError>>(s: &str) -> T {
debug!("json decoding: {}", s);
references:- 2422: disc_in, disc_out, *res);
423: Work::from_value(json_decode(*res))
424: }
libworkcache/lib.rs:124:45-124:45 -struct- definition:
struct KindMap(TreeMap<~str, ~str>);
impl WorkMap {
fn new() -> WorkMap { WorkMap(TreeMap::new()) }
references:- 9125: struct KindMap(TreeMap<~str, ~str>);
libworkcache/lib.rs:227:19-227:19 -struct- definition:
pub struct Context {
pub db: Arc<RWLock<Database>>,
cfg: Arc<json::Object>,
references:- 10280: freshness: Arc<FreshnessMap>) -> Context {
281: Context {
282: db: db,
--
336: impl<'a> Prep<'a> {
337: fn new(ctxt: &'a Context, fn_name: &'a str) -> Prep<'a> {
338: Prep {
libworkcache/lib.rs:250:1-250:1 -enum- definition:
enum Work<'a, T> {
WorkValue(T),
WorkFromTask(&'a Prep<'a>, Receiver<(Exec, T)>),
references:- 4404: Decodable<json::Decoder, json::DecoderError>>( // FIXME(#5121)
405: &'a self, blk: proc(&mut Exec):Send -> T) -> Work<'a, T> {
406: let mut bo = Some(blk);
--
448: Decodable<json::Decoder, json::DecoderError>>
449: Work<'a, T> { // FIXME(#5121)
451: pub fn from_value(elt: T) -> Work<'a, T> {
452: WorkValue(elt)
--
454: pub fn from_task(prep: &'a Prep<'a>, port: Receiver<(Exec, T)>)
455: -> Work<'a, T> {
456: WorkFromTask(prep, port)
libworkcache/lib.rs:224:1-224:1 -NK_AS_STR_TODO- definition:
pub type FreshnessMap = TreeMap<~str,extern fn(&str,&str)->bool>;
pub struct Context {
pub db: Arc<RWLock<Database>>,
references:- 2236: /// read hash for equality.
237: freshness: Arc<FreshnessMap>
238: }
--
279: cfg: Arc<json::Object>,
280: freshness: Arc<FreshnessMap>) -> Context {
281: Context {
libworkcache/lib.rs:121:45-121:45 -struct- definition:
struct WorkMap(TreeMap<~str, KindMap>);
struct KindMap(TreeMap<~str, ~str>);
impl WorkMap {
references:- 20247: discovered_inputs: WorkMap,
248: discovered_outputs: WorkMap
249: }
--
382: fn all_fresh(&self, cat: &str, map: &WorkMap) -> bool {
383: let WorkMap(ref map) = *map;
libworkcache/lib.rs:142:1-142:1 -struct- definition:
pub struct Database {
db_filename: Path,
db_cache: TreeMap<~str, ~str>,
references:- 7151: pub fn new(p: Path) -> Database {
152: let mut rslt = Database {
153: db_filename: p,
--
228: pub struct Context {
229: pub db: Arc<RWLock<Database>>,
230: cfg: Arc<json::Object>,
--
273: pub fn new(db: Arc<RWLock<Database>>,
274: cfg: Arc<json::Object>) -> Context {
--
278: pub fn new_with_freshness(db: Arc<RWLock<Database>>,
279: cfg: Arc<json::Object>,
libworkcache/lib.rs:245:1-245:1 -struct- definition:
pub struct Exec {
discovered_inputs: WorkMap,
discovered_outputs: WorkMap
references:- 6432: spawn(proc() {
433: let mut exe = Exec {
434: discovered_inputs: WorkMap::new(),
--
453: }
454: pub fn from_task(prep: &'a Prep<'a>, port: Receiver<(Exec, T)>)
455: -> Work<'a, T> {
libworkcache/lib.rs:255:1-255:1 -fn- definition:
fn json_encode<'a, T:Encodable<json::Encoder<'a>, io::IoError>>(t: &T) -> ~str {
let mut writer = MemWriter::new();
let mut encoder = json::Encoder::new(&mut writer as &mut io::Writer);
references:- 4180: let k = json_encode(&(fn_name, declared_inputs));
181: let v = json_encode(&(discovered_inputs,
182: discovered_outputs,
--
463: let (exe, v) = port.recv();
464: let s = json_encode(&v);
465: let mut db = prep.ctxt.db.deref().write();
libworkcache/lib.rs:239:1-239:1 -struct- definition:
pub struct Prep<'a> {
ctxt: &'a Context,
fn_name: &'a str,
references:- 8337: fn new(ctxt: &'a Context, fn_name: &'a str) -> Prep<'a> {
338: Prep {
339: ctxt: ctxt,
--
358: impl<'a> Prep<'a> {
359: pub fn declare_input(&mut self, kind: &str, name: &str, val: &str) {
--
453: }
454: pub fn from_task(prep: &'a Prep<'a>, port: Receiver<(Exec, T)>)
455: -> Work<'a, T> {