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 -------------------------------------------------*/