3 * Dependency-based computation.
5 * (c) 2013 Mark Wooding
8 /*----- Licensing notice --------------------------------------------------*
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.
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.
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, see <https://www.gnu.org/licenses/>.
24 var DEP = { }; (function () {
26 /*----- Utility functions and classes -------------------------------------*/
29 function blather(msg) {
30 /* Report MSG to the log if we're debugging. */
31 if (DEP.DEBUG) console.log(";; " + msg);
33 function show(what, value) {
34 /* Report that WHAT has the value VALUE, if we're debugging; and,
35 * regardless, return VALUE.
37 blather(what + " = " + value);
41 function dolist(list, func) {
42 /* Apply FUNC to each element of LIST, discarding the results.
44 * JavaScript's looping iterates over indices rather than values, which is
45 * consistent with what you want from a mapping, but inconvenient for
50 for (i in list) func(list[i]);
55 /* A standard equality function, suitable for detecting changes to `Dep'
56 * objects. This may be needlessly sensitive for some cases, but at least
57 * that's slow rather than wrong.
63 function try_finally(trythunk, finalthunk) {
64 /* Call the TRYTHUNK. When TRYTHUNK exits (even if it's with an exception)
65 * then call FINALTHUNK. If TRYTHUNK returned normally then return its
66 * value; otherwise continue with the non-local flow control.
68 * This is an unpleasant hack because V8 doesn't optimize functions which
69 * contain try/finally very well (despite this being an easy transformation
73 try { return trythunk(); }
74 finally { finalthunk(); }
77 function try_cleanup(trythunk, cleanthunk) {
78 /* Call the TRYTHUNK. If TRYTHUNK returns normally, just return its value;
79 * otherwise call CLEANTHUNK and re-throw the exception.
81 * This is an unpleasant hack because V8 doesn't optimize functions which
82 * contain try/catch very well (despite this being an easy transformation
87 try { return trythunk(); }
88 catch (e) { cleanthunk(); throw e; }
91 /* A Tag is an object which is interesting only because of its identity, and
92 * that the set of Tags is basically determined by the static structure of
99 toString: function () { return '#{Tag ' + this.what + '}'; }
103 /* A Generation is like a Tag, except that it's expected that a program will
104 * manufacture Generations repeatedly, and perhaps use them to determine
105 * whether an object is `up-to-date' in some sense.
107 function Generation(what) {
109 this.seq = Generation._next++;
111 Generation.prototype = {
112 toString: function () {
113 return '#{Generation ' + this.what + ' #' + this.seq.toString() + '}';
116 Generation._next = 0;
117 DEP.Generation = Generation;
119 /*----- The system state --------------------------------------------------*/
121 var GENERATION = new Generation('dep-generation');
122 // Current recomputation generation.
124 var EVALUATING = null; // The dep being re-evaluated.
125 var STATE = 'ready'; // The current state.
127 /* Flags for Dep objects. */
128 var F_VALUE = 1; // Value is up-to-date.
129 var F_DEPS = 2; // Known as a dependent.
130 var F_CHANGED = 4; // Changed in current phase.
131 var F_RECOMPUTING = 8; // Currently being recomputed.
132 var F_QUEUED = 16; // Queued for recomputation.
134 var BAD = new Tag('BAD'); // Used for the value of `bad' deps.
136 var DELAYED = []; // Actions delayed by `with_frozen'.
137 var PENDING = []; // Deps awaiting recomputation.
139 /*----- Exceptions --------------------------------------------------------*/
141 CircularDependency = new Tag('CircularDependency');
142 DEP.CircularDependency = CircularDependency;
144 BusyRecomputing = new Tag('BusyRecomputing');
145 DEP.BusyRecomputing = BusyRecomputing;
147 /*----- Main code ---------------------------------------------------------*/
149 /* A `Dep' object maintains a value, either because it was provided
150 * explicitly by the programmer, or computed in terms of other `Dep' objects.
151 * In the latter case, its value will be recomputed if any of its
152 * dependencies change value.
154 * A `Dep' object may have listener functions attached to it. These
155 * functions will bw called when its value changes.
157 * A `Dep' may be `bad'. In this case, use of its value by a dependent
158 * causes that `Dep' to become bad in turn.
161 function Dep(value, maybefunc) {
162 /* Initialize a new `Dep' object.
164 * Handling of the arguments is a little fiddly. If two arguments are
165 * provided then the first is set as the value and the second as the
166 * recomputation function. Otherwise, the first argument is interpreted as
167 * the recomputation function if it has `function' type, or as an initial
168 * explicit value otherwise. To force a function to be interpreted as an
169 * initial value, pass a second argument of `null'.
171 * Some properties can be fiddled with by client programs (rather than
172 * trying to invent some crazy option-parsing protocol in the constructor).
174 * `name' A string name for this `Dep', used when printing.
176 * `equivp' A predicate for deciding whether two value assigned
177 * to this `Dep' are equivalent. Used to decide whether
178 * a change should be propagated.
181 var val, func, f = F_CHANGED;
184 // Work out what's going on with our crazy argument convention.
185 if (maybefunc !== undefined) {
188 f |= F_VALUE | F_QUEUED;
189 } else if (typeof value === 'function') {
194 val = value === undefined ? BAD : value;
196 f |= F_VALUE | F_DEPS;
199 // Initialize the various slots.
200 this._value_function = func; // Recomputation function.
201 this._value = val; // Current value.
203 this.name = undefined; // Name, for printing.
204 this.equivp = eql; // Equivalent-value predicate.
205 this.__flags = f; // Current flags.
206 this._generation = GENERATION; // Have we done this one already?.
207 this._listeners = []; // List of listener functions.
209 // We need to maintain the dependency graph. In order to prevent duplicate
210 // entries in the various sets, we use maps rather than lists, but this
211 // presents a problem with coming up with keys: JavaScript stringifies
212 // objects rather than using them as-is, which is obviously hopeless. So
213 // assign each `Dep' a unique sequence number and use that as the key.
214 this._seq = Dep._seq++; // For identifying this object.
215 this._dependents = { }; // Set of dependent objects.
216 this._dependencies = { }; // Set of objects we depend on.
218 // If we have a recomputation function then exercise it.
219 blather("new dep " + me);
221 with_frozen(function () {
223 blather("push new dep " + me);
229 Dep._seq = 0; // Next sequence number to allocate.
233 toString: function () {
234 /* Convert the receiver to a string.
236 * The printed representation includes a number of bits of information
237 * which are probably meaningless to most readers but are handy for
238 * debugging this library if it's misbehaving.
243 var f = this._flags();
247 if (this.name !== null) s += ' "' + this.name + '"';
249 // Sequence number -- distinguishes the dep if nothing else will.
250 s += ' #' + this._seq;
252 // The value, or some kind of marker that it doesn't have one.
253 if (!(f & F_VALUE)) s += ' #{stale}';
254 else if (v === BAD) s += ' #{bad}';
255 else s += ' ' + v.toString();
258 if (!(f & F_DEPS)) s += ' :recompute-deps';
259 if (f & F_QUEUED) s += ' :queued';
260 if (f & F_CHANGED) s += ' :changed';
267 _flags: function () {
268 /* Return the receiver's flags.
270 * If the receiver isn't up-to-date then we synthesize the flags.
273 if (STATE === 'ready') return F_VALUE | F_DEPS;
274 else if (this._generation === GENERATION) return this.__flags;
275 else if (this._value_function === null) return F_VALUE | F_DEPS;
279 _update: function (value) {
280 /* Store VALUE as the receiver's value.
282 * Return whether the value has changed as a result. This is a low-level
283 * function which doesn't handle propagation or anything like that.
286 blather("_update " + this + ": " + value);
288 this._value === BAD :
289 (this._value !== BAD &&
290 this.equivp(value, this._value)))
298 _new_value: function () {
299 /* Run the `_value_function' of the receiver, returning the result.
301 * If a bad dep is read during this then return `BAD'. Other exceptions
302 * are propagated in the usual way.
305 var old = EVALUATING;
309 this._dependencies = { };
310 return try_finally(function () {
312 return show("_new_value for " + me,
313 orelse(function () { return me._value_function(); },
314 function () { return show("ret", BAD); }));
320 _propagate: function () {
321 /* Propagate a change in the receiver to dependents and listeners. */
325 // Iterate over each dependent, pushing each one onto the `PENDING'
326 // queue, bringing it into the current generation, and marking it as
327 // having no current value.
328 for (di in this._dependents) {
329 d = this._dependents[di];
331 if (!(f & (F_QUEUED | F_DEPS))) {
333 d._generation = GENERATION;
334 d.__flags = (f & ~F_VALUE) | F_QUEUED;
338 // We no longer have any dependents. Maybe we'll acquire more when the
339 // old dependents recompute themselves.
340 this._dependents = { };
342 // Tell the listeners that something interesting happened.
343 dolist(this._listeners, function (l) { l(); });
346 _recompute: function () {
347 /* Recompute the receiver, propagating changes and so on.
349 * Return whether we actually needed to change anything.
352 var queued = this.__flags & F_QUEUED;
355 // Update us with the given VALUE.
356 function update(value) {
357 if (me._update(value)) {
358 me.__flags = queued | F_VALUE | F_DEPS | F_CHANGED;
362 me.__flags = queued | F_VALUE | F_DEPS;
367 // Try to recompute our value. If that doesn't work then mark us as bad
368 // and propagate that.
369 return try_cleanup(function () { return update(me._new_value()); },
370 function () { update(BAD); });
373 _force: function () {
374 /* Make sure the receiver has a current value.
376 * Return true if the receiver's value has changed in this recomputation
379 * If it already has a good value then just return. Otherwise mark it
380 * as recomputing (to trap circularities) and poke our dependencies to
381 * ensure that they're up-to-date. If they weren't, then we recompute
382 * our own value before returning.
385 var f = this._flags();
388 if (f & F_RECOMPUTING) throw CircularDependency;
389 else if (f & F_VALUE) return f & F_CHANGED;
391 this._generation = GENERATION;
392 this.__flags = (f & ~F_QUEUED) | F_RECOMPUTING;
393 for (d in this._dependencies)
394 if (this._dependencies[d]._force()) any = true;
396 return this._recompute();
405 /* Fetch and return the receiver's current value.
407 * If the receiver is bad then an exception is thrown. This exception
408 * can be caught using `orelse'; a dep recomputation function can let the
409 * exception propagate, and be marked as bad in turn.
414 if (STATE === 'recomputing') {
417 this._dependents[EVALUATING._seq] = EVALUATING;
418 EVALUATING._dependencies[this._seq] = this;
422 blather("value " + this + ": " + val);
423 if (val === BAD) throw BAD;
427 set_value: function (value) {
428 /* Set the receiver's value to VALUE, and propagate. */
432 with_frozen(function () {
433 if (me._update(value)) {
434 me._generation = GENERATION;
435 me.__flags = F_VALUE | F_CHANGED;
441 make_bad: function () {
442 /* Mark the receiver as being bad, and propagate. */
446 add_listener: function (func) {
447 /* Add FUNC to the receiver's list of listeners.
449 * Listener functions are called without arguments, and any values
450 * returned are ignored.
453 this._listeners.push(func);
457 /* Return whether the receiver is good (i.e., not marked as bad). */
459 return this._value !== BAD;
463 function orelse(thunk, errthunk) {
464 /* Call THUNK. If it succeeds, then return its result. If THUNK
465 * reads a bad dep then call ERRTHUNK and return its result instead.
469 try { return thunk(); }
471 if (e === BAD) { return errthunk(); }
478 /* For use in a value-function: make the dep be bad. */
483 function recompute_pending() {
484 /* Recompute any pending dependencies.
486 * The state is `recomputing' during this.
490 var old_state = STATE;
491 STATE = 'recomputing';
492 blather("STATE <- :recomputing");
493 try_finally(function () {
494 while (PENDING.length) {
497 d.__flags = f & ~F_QUEUED;
500 else if (!(f & F_DEPS)) {
502 d.__flags = f | F_DEPS;
506 while (PENDING.length) {
509 blather("recompute_pending mark " + d);
512 blather("STATE <- :" + old_state);
516 function with_frozen(body, delay) {
517 /* Call BODY with dependencies frozen.
519 * If the BODY function changes any dep values (using D.set_value(...))
520 * then dependents won't be updated until the BODY completes.
522 * It's very bad to do this during a recomputation phase. If DELAY is
523 * true, then the BODY is delayed until the recomputation completes;
524 * otherwise you get an exception.
528 var old_delayed, old_pending, old_state;
535 if (!delay) throw BusyRecomputing;
539 old_delayed = DELAYED;
540 old_pending = PENDING;
543 blather("STATE <- :frozen");
544 try_finally(function () {
547 GENERATION = new Generation('dep-generation');
551 if (!DELAYED.length) break;
552 op = DELAYED.shift();
556 DELAYED = old_delayed;
557 PENDING = old_pending;
559 blather("STATE <- :" + old_state);
564 DEP.with_frozen = with_frozen;
566 /*----- That's all, folks -------------------------------------------------*/