Commit | Line | Data |
---|---|---|
ac26861c MW |
1 | /* -*-javascript-*- |
2 | * | |
3 | * Dependency-based computation. | |
4 | * | |
5 | * (c) 2013 Mark Wooding | |
6 | */ | |
7 | ||
8 | /*----- Licensing notice --------------------------------------------------* | |
9 | * | |
10 | * This program is free software; you can redistribute it and/or | |
11 | * modify it under the terms of the GNU General Public License as | |
12 | * published by the Free Software Foundation; either version 2 of the | |
13 | * License, or (at your option) any later version. | |
14 | * | |
15 | * This program is distributed in the hope that it will be useful, | |
16 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
17 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
18 | * GNU Library General Public License for more details. | |
19 | * | |
20 | * You should have received a copy of the GNU General Public License | |
21 | * along with this program; if not, see <http://www.gnu.org/licenses/>. | |
22 | */ | |
23 | ||
6cfd4191 | 24 | var DEP = { }; (function () { |
ac26861c MW |
25 | |
26 | /*----- Utility functions and classes -------------------------------------*/ | |
27 | ||
6cfd4191 | 28 | function dolist(list, func) { |
ac26861c MW |
29 | /* Apply FUNC to each element of LIST, discarding the results. |
30 | * | |
31 | * JavaScript's looping iterates over indices rather than values, which is | |
32 | * consistent with what you want from a mapping, but inconvenient for | |
33 | * sequences. | |
34 | */ | |
35 | ||
36 | var i; | |
37 | for (i in list) func(list[i]); | |
38 | } | |
6cfd4191 | 39 | DEP.dolist = dolist; |
ac26861c MW |
40 | |
41 | function eql(x, y) { | |
42 | /* A standard equality function, suitable for detecting changes to `Dep' | |
43 | * objects. This may be needlessly sensitive for some cases, but at least | |
44 | * that's slow rather than wrong. | |
45 | */ | |
46 | ||
47 | return x === y; | |
48 | } | |
49 | ||
5a0d36b9 MW |
50 | function try_finally(trythunk, finalthunk) { |
51 | /* Call the TRYTHUNK. When TRYTHUNK exits (even if it's with an exception) | |
52 | * then call FINALTHUNK. If TRYTHUNK returned normally then return its | |
53 | * value; otherwise continue with the non-local flow control. | |
54 | * | |
55 | * This is an unpleasant hack because V8 doesn't optimize functions which | |
56 | * contain try/finally very well (despite this being an easy transformation | |
57 | * for the compiler). | |
58 | */ | |
59 | ||
60 | try { return trythunk(); } | |
61 | finally { finalthunk(); } | |
62 | } | |
63 | ||
64 | function try_cleanup(trythunk, cleanthunk) { | |
65 | /* Call the TRYTHUNK. If TRYTHUNK returns normally, just return its value; | |
66 | * otherwise call CLEANTHUNK and re-throw the exception. | |
67 | * | |
68 | * This is an unpleasant hack because V8 doesn't optimize functions which | |
69 | * contain try/catch very well (despite this being an easy transformation | |
70 | * for the compiler). | |
71 | */ | |
72 | ||
73 | var e; | |
74 | try { return trythunk(); } | |
75 | catch (e) { cleanthunk(); throw e; } | |
76 | } | |
77 | ||
ac26861c MW |
78 | /* A Tag is an object which is interesting only because of its identity, and |
79 | * that the set of Tags is basically determined by the static structure of | |
80 | * the program. | |
81 | */ | |
6cfd4191 | 82 | function Tag(what) { |
ac26861c MW |
83 | this.what = what; |
84 | } | |
85 | Tag.prototype = { | |
86 | toString: function () { return '#{Tag ' + this.what + '}'; } | |
87 | } | |
6cfd4191 | 88 | DEP.Tag = Tag; |
ac26861c MW |
89 | |
90 | /* A Generation is like a Tag, except that it's expected that a program will | |
91 | * manufacture Generations repeatedly, and perhaps use them to determine | |
92 | * whether an object is `up-to-date' in some sense. | |
93 | */ | |
6cfd4191 | 94 | function Generation(what) { |
ac26861c MW |
95 | this.what = what; |
96 | this.seq = Generation._next++; | |
97 | } | |
98 | Generation.prototype = { | |
99 | toString: function () { | |
100 | return '#{Generation ' + this.what + ' #' + this.seq.toString() + '}'; | |
101 | } | |
102 | }; | |
103 | Generation._next = 0; | |
104 | DEP.Generation = Generation; | |
105 | ||
106 | /*----- The system state --------------------------------------------------*/ | |
107 | ||
108 | var GENERATION = new Generation('dep-generation'); | |
109 | // Current recomputation generation. | |
110 | ||
111 | var EVALUATING = null; // The dep being re-evaluated. | |
112 | var STATE = 'ready'; // The current state. | |
113 | ||
114 | /* Flags for Dep objects. */ | |
115 | var F_VALUE = 1; // Value is up-to-date. | |
116 | var F_DEPS = 2; // Known as a dependent. | |
117 | var F_CHANGED = 4; // Changed in current phase. | |
118 | var F_RECOMPUTING = 8; // Currently being recomputed. | |
119 | var F_QUEUED = 16; // Queued for recomputation. | |
120 | ||
121 | var BAD = Tag('BAD') // Used for the value of `bad' deps. | |
122 | ||
123 | var DELAYED = []; // Actions delayed by `with_frozen'. | |
124 | var PENDING = []; // Deps awaiting recomputation. | |
125 | ||
126 | /*----- Exceptions --------------------------------------------------------*/ | |
127 | ||
6cfd4191 MW |
128 | CircularDependency = new Tag('CircularDependency'); |
129 | DEP.CircularDependency = CircularDependency; | |
130 | ||
131 | BusyRecomputing = new Tag('BusyRecomputing'); | |
132 | DEP.BusyRecomputing = BusyRecomputing; | |
ac26861c MW |
133 | |
134 | /*----- Main code ---------------------------------------------------------*/ | |
135 | ||
136 | /* A `Dep' object maintains a value, either because it was provided | |
137 | * explicitly by the programmer, or computed in terms of other `Dep' objects. | |
138 | * In the latter case, its value will be recomputed if any of its | |
139 | * dependencies change value. | |
140 | * | |
141 | * A `Dep' object may have listener functions attached to it. These | |
142 | * functions will bw called when its value changes. | |
143 | * | |
144 | * A `Dep' may be `bad'. In this case, use of its value by a dependent | |
145 | * causes that `Dep' to become bad in turn. | |
146 | */ | |
147 | ||
6cfd4191 | 148 | function Dep(value, maybefunc) { |
ac26861c MW |
149 | /* Initialize a new `Dep' object. |
150 | * | |
151 | * Handling of the arguments is a little fiddly. If two arguments are | |
152 | * provided then the first is set as the value and the second as the | |
153 | * recomputation function. Otherwise, the first argument is interpreted as | |
154 | * the recomputation function if it has `function' type, or as an initial | |
155 | * explicit value otherwise. To force a function to be interpreted as an | |
156 | * initial value, pass a second argument of `null'. | |
157 | * | |
158 | * Some properties can be fiddled with by client programs (rather than | |
159 | * trying to invent some crazy option-parsing protocol in the constructor). | |
160 | * | |
161 | * `name' A string name for this `Dep', used when printing. | |
162 | * | |
163 | * `equivp' A predicate for deciding whether two value assigned | |
164 | * to this `Dep' are equivalent. Used to decide whether | |
165 | * a change should be propagated. | |
166 | */ | |
167 | ||
168 | var val, func, f = F_CHANGED; | |
169 | var me = this; | |
170 | ||
171 | // Work out what's going on with our crazy argument convention. | |
172 | if (maybefunc !== undefined) { | |
173 | val = value; | |
174 | func = maybefunc; | |
175 | f |= F_VALUE | F_QUEUED; | |
176 | } else if (typeof value === 'function') { | |
177 | val = BAD; | |
178 | func = value; | |
179 | f |= F_QUEUED; | |
180 | } else { | |
181 | val = value; | |
182 | func = null; | |
183 | f |= F_VALUE | F_DEPS; | |
184 | } | |
185 | ||
186 | // Initialize the various slots. | |
187 | this._value_function = func; // Recomputation function. | |
188 | this._value = val; // Current value. | |
189 | ||
190 | this.name = undefined; // Name, for printing. | |
191 | this.equivp = eql; // Equivalent-value predicate. | |
192 | this.__flags = f; // Current flags. | |
193 | this._generation = GENERATION; // Have we done this one already?. | |
194 | this._listeners = []; // List of listener functions. | |
195 | ||
196 | // We need to maintain the dependency graph. In order to prevent duplicate | |
197 | // entries in the various sets, we use maps rather than lists, but this | |
198 | // presents a problem with coming up with keys: JavaScript stringifies | |
199 | // objects rather than using them as-is, which is obviously hopeless. So | |
200 | // assign each `Dep' a unique sequence number and use that as the key. | |
201 | this._seq = Dep._seq++; // For identifying this object. | |
202 | this._dependents = { }; // Set of dependent objects. | |
203 | this._dependencies = { }; // Set of objects we depend on. | |
204 | ||
205 | // If we have a recomputation function then exercise it. | |
206 | if (func !== null) { | |
207 | with_frozen(function () { | |
208 | PENDING.push(me); | |
209 | }); | |
210 | } | |
211 | } | |
212 | ||
6cfd4191 | 213 | DEP.Dep = Dep; |
ac26861c MW |
214 | Dep._seq = 0; // Next sequence number to allocate. |
215 | ||
216 | Dep.prototype = { | |
217 | ||
218 | toString: function () { | |
219 | /* Convert the receiver to a string. | |
220 | * | |
221 | * The printed representation includes a number of bits of information | |
222 | * which are probably meaningless to most readers but are handy for | |
223 | * debugging this library if it's misbehaving. | |
224 | */ | |
225 | ||
226 | // Basic stuff. | |
227 | var s = '#{Dep'; | |
228 | var f = this._flags(); | |
229 | var v = this._value; | |
230 | ||
231 | // The dep's name. | |
232 | if (this.name !== null) s += ' "' + this.name + '"'; | |
233 | ||
234 | // Sequence number -- distinguishes the dep if nothing else will. | |
235 | s += ' #' + this._seq; | |
236 | ||
237 | // The value, or some kind of marker that it doesn't have one. | |
238 | if (!(f & F_VALUE)) s += ' #{out-of-date}'; | |
239 | else if (v === BAD) s += ' #{bad}'; | |
240 | else s += ' ' + v.toString(); | |
241 | ||
242 | // Various flags. | |
243 | if (!(f & F_DEPS)) s += ' :recompute-deps'; | |
244 | if (f & F_QUEUED) s += ' :queued'; | |
245 | if (f & F_CHANGED) s += ' :changed'; | |
246 | ||
247 | // Done. | |
248 | s += '}'; | |
249 | return s; | |
250 | }, | |
251 | ||
252 | _flags: function () { | |
253 | /* Return the receiver's flags. | |
254 | * | |
255 | * If the receiver isn't up-to-date then we synthesize the flags. | |
256 | */ | |
257 | ||
258 | if (this.state === 'ready') return F_VALUE | F_DEPS; | |
259 | else if (this._generation === GENERATION) return this.__flags; | |
260 | else if (this._value_function === null) return F_VALUE | F_DEPS; | |
261 | else return 0; | |
262 | }, | |
263 | ||
264 | _update: function (value) { | |
265 | /* Store VALUE as the receiver's value. | |
266 | * | |
267 | * Return whether the value has changed as a result. This is a low-level | |
268 | * function which doesn't handle propagation or anything like that. | |
269 | */ | |
270 | ||
271 | if (value === BAD ? | |
272 | this._value === BAD : | |
273 | (this._value !== BAD && | |
274 | this.equivp(value, this._value))) | |
275 | return false; | |
276 | else { | |
277 | this._value = value; | |
278 | return true; | |
279 | } | |
280 | }, | |
281 | ||
282 | _new_value: function () { | |
283 | /* Run the `_value_function' of the receiver, returning the result. | |
284 | * | |
285 | * If a bad dep is read during this then return `BAD'. Other exceptions | |
286 | * are propagated in the usual way. | |
287 | */ | |
288 | ||
289 | var old = EVALUATING; | |
5a0d36b9 MW |
290 | var me = this; |
291 | var val; | |
ac26861c MW |
292 | |
293 | this._dependencies = { }; | |
5a0d36b9 MW |
294 | return try_finally(function () { |
295 | EVALUATING = me; | |
296 | return orelse(function () { return me._value_function(); }, | |
297 | function () { return BAD; }); | |
298 | }, function() { | |
ac26861c | 299 | EVALUATING = old; |
5a0d36b9 | 300 | }); |
ac26861c MW |
301 | }, |
302 | ||
303 | _propagate: function () { | |
304 | /* Propagate a change in the receiver to dependents and listeners. */ | |
305 | ||
306 | var d, di, f; | |
307 | ||
308 | // Iterate over each dependent, pushing each one onto the `PENDING' | |
309 | // queue, bringing it into the current generation, and marking it as | |
310 | // having no current value. | |
311 | for (di in this._dependents) { | |
312 | d = this._dependents[di]; | |
313 | f = d._flags(); | |
314 | if (!(f & (F_QUEUED | F_DEPS))) { | |
315 | PENDING.push(d); | |
316 | d._generation = GENERATION; | |
317 | d.__flags = (f & ~F_VALUE) | F_QUEUED; | |
318 | } | |
319 | } | |
320 | ||
321 | // We no longer have any dependents. Maybe we'll acquire more when the | |
322 | // old dependents recompute themselves. | |
323 | this._dependents = { }; | |
324 | ||
325 | // Tell the listeners that something interesting happened. | |
326 | dolist(this._listeners, function (l) { l(); }); | |
327 | }, | |
328 | ||
329 | _recompute: function () { | |
330 | /* Recompute the receiver, propagating changes and so on. | |
331 | * | |
332 | * Return whether we actually needed to change anything. | |
333 | */ | |
334 | ||
335 | var queued = this.__flags & F_QUEUED; | |
ac26861c MW |
336 | var me = this; |
337 | ||
338 | // Update us with the given VALUE. | |
339 | function update(value) { | |
340 | if (me._update(value)) { | |
341 | me.__flags = queued | F_VALUE | F_DEPS | F_CHANGED; | |
342 | me._propagate(); | |
343 | return true; | |
344 | } else { | |
345 | me.__flags = queued | F_VALUE | F_DEPS; | |
346 | return false; | |
347 | } | |
348 | }; | |
349 | ||
350 | // Try to recompute our value. If that doesn't work then mark us as bad | |
351 | // and propagate that. | |
5a0d36b9 MW |
352 | return try_cleanup(function () { return update(me._new_value()); }, |
353 | function () { update(BAD); }); | |
ac26861c MW |
354 | }, |
355 | ||
356 | _force: function () { | |
357 | /* Make sure the receiver has a current value. | |
358 | * | |
359 | * Return true if the receiver's value has changed in this recomputation | |
360 | * phase. | |
361 | * | |
362 | * If it already has a good value then just return. Otherwise mark it | |
363 | * as recomputing (to trap circularities) and poke our dependencies to | |
364 | * ensure that they're up-to-date. If they weren't, then we recompute | |
365 | * our own value before returning. | |
366 | */ | |
367 | ||
368 | var f = this._flags(); | |
369 | var d, any = false; | |
370 | ||
371 | if (f & F_RECOMPUTING) throw CircularDependency; | |
372 | else if (f & F_VALUE) return f & F_CHANGED; | |
373 | else { | |
374 | this._generation = GENERATION; | |
375 | this.__flags = (f & ~F_QUEUED) | F_RECOMPUTING; | |
376 | for (d in this._dependencies) | |
377 | if (this._dependencies[d]._force()) any = true; | |
378 | if (any) | |
379 | return this._recompute(); | |
380 | else { | |
381 | this.__flags = f; | |
382 | return false; | |
383 | } | |
384 | } | |
385 | }, | |
386 | ||
387 | value: function () { | |
388 | /* Fetch and return the receiver's current value. | |
389 | * | |
390 | * If the receiver is bad then an exception is thrown. This exception | |
391 | * can be caught using `orelse'; a dep recomputation function can let the | |
392 | * exception propagate, and be marked as bad in turn. | |
393 | */ | |
394 | ||
395 | var val; | |
396 | ||
397 | if (state === 'recomputing') { | |
398 | if (EVALUATING) { | |
399 | this._dependents[EVALUATING._seq] = EVALUATING; | |
400 | EVALUATING._dependencies[this._seq] = this; | |
401 | } | |
402 | this._force(); | |
403 | } | |
404 | val = this._value; | |
405 | if (val === BAD) throw BAD; | |
406 | return val; | |
407 | }, | |
408 | ||
409 | set_value: function (value) { | |
410 | /* Set the receiver's value to VALUE, and propagate. */ | |
411 | ||
412 | var me = this; | |
413 | ||
414 | with_frozen(function () { | |
415 | if (me._update(value)) { | |
416 | me._generation = GENERATION; | |
417 | me.__flags = F_VALUE | F_CHANGED; | |
418 | me._propagate(); | |
419 | } | |
420 | }); | |
421 | }, | |
422 | ||
423 | make_bad: function () { | |
424 | /* Mark the receiver as being bad, and propagate. */ | |
425 | this.set_value(BAD); | |
426 | }, | |
427 | ||
428 | add_listener: function (func) { | |
429 | /* Add FUNC to the receiver's list of listeners. | |
430 | * | |
431 | * Listener functions are called without arguments, and any values | |
432 | * returned are ignored. | |
433 | */ | |
434 | ||
435 | this._listeners.push(func); | |
436 | }, | |
437 | ||
438 | goodp: function () { | |
439 | /* Return whether the receiver is good (i.e., not marked as bad). */ | |
440 | ||
441 | return this._value !== BAD; | |
442 | } | |
443 | }; | |
444 | ||
6cfd4191 | 445 | function orelse(thunk, errthunk) { |
ac26861c MW |
446 | /* Call THUNK. If it succeeds, then return its result. If THUNK |
447 | * reads a bad dep then call ERRTHINK and return its result instead. | |
448 | */ | |
449 | ||
450 | var e; | |
451 | try { return thunk(); } | |
452 | catch (e) { | |
453 | if (e === BAD) { return errthunk(); } | |
454 | else throw e; | |
455 | } | |
456 | } | |
6cfd4191 | 457 | DEP.orelse = orelse; |
ac26861c | 458 | |
6cfd4191 | 459 | function bad() { |
ac26861c MW |
460 | /* For use in a value-function: make the dep be bad. */ |
461 | throw BAD; | |
462 | } | |
6cfd4191 | 463 | DEP.bad = bad; |
ac26861c MW |
464 | |
465 | function recompute_pending() { | |
466 | /* Recompute any pending dependencies. | |
467 | * | |
468 | * The state is `recomputing' during this. | |
469 | */ | |
470 | ||
471 | var d, f; | |
472 | ||
473 | state = 'recomputing'; | |
5a0d36b9 | 474 | try_finally(function () { |
ac26861c MW |
475 | while (PENDING.length) { |
476 | d = PENDING.shift(); | |
477 | f = d.__flags; | |
478 | d.__flags = f & ~F_QUEUED; | |
479 | if (!(f & F_VALUE)) | |
480 | d._recompute(); | |
481 | else if (!(f & F_DEPS)) { | |
482 | d.new_value(); | |
483 | d.__flags = f | F_DEPS; | |
484 | } | |
485 | } | |
5a0d36b9 | 486 | }, function () { |
ac26861c MW |
487 | while (PENDING.length) { |
488 | d = PENDING.shift(); | |
489 | d._value = BAD; | |
490 | } | |
5a0d36b9 | 491 | }); |
ac26861c MW |
492 | } |
493 | ||
6cfd4191 | 494 | function with_frozen(body, delay) { |
ac26861c MW |
495 | /* Call BODY with dependencies frozen. |
496 | * | |
497 | * If the BODY function changes any dep values (using D.set_value(...)) | |
498 | * then dependents won't be updated until the BODY completes. | |
499 | * | |
500 | * It's very | |
501 | * bad to do this during a recomputation phase. If DELAY is true, then the | |
502 | * BODY is delayed until the recomputation completes; otherwise you get an | |
503 | * exception. | |
504 | */ | |
505 | ||
506 | var op, val; | |
507 | var old_delayed, old_pending; | |
508 | ||
509 | switch (STATE) { | |
510 | case 'frozen': | |
511 | body(); | |
512 | break; | |
513 | case 'recomputing': | |
514 | if (!delay) throw BusyRecomputing; | |
515 | DELAYED.push(body); | |
516 | break; | |
517 | case 'ready': | |
518 | old_delayed = DELAYED; | |
519 | old_pending = PENDING; | |
5a0d36b9 | 520 | try_finally(function () { |
ac26861c MW |
521 | DELAYED = []; |
522 | PENDING = []; | |
523 | GENERATION = new Generation('dep-generation'); | |
524 | val = body(); | |
525 | for (;;) { | |
526 | recompute_pending(); | |
527 | if (!DELAYED.length) break; | |
528 | op = DELAYED.shift(); | |
529 | op(); | |
530 | } | |
5a0d36b9 | 531 | }, function () { |
ac26861c MW |
532 | DELAYED = old_delayed; |
533 | PENDING = old_pending; | |
5a0d36b9 | 534 | }); |
ac26861c MW |
535 | break; |
536 | } | |
537 | } | |
6cfd4191 | 538 | DEP.with_frozen = with_frozen; |
ac26861c MW |
539 | |
540 | /*----- That's all, folks -------------------------------------------------*/ | |
6cfd4191 | 541 | })(); |