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 <http://www.gnu.org/licenses/>.
24 var DEP
= { }; (function () {
26 /*----- Utility functions and classes -------------------------------------*/
28 function dolist(list
, func
) {
29 /* Apply FUNC to each element of LIST, discarding the results.
31 * JavaScript's looping iterates over indices rather than values, which is
32 * consistent with what you want from a mapping, but inconvenient for
37 for (i
in list
) func(list
[i
]);
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.
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.
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
60 try { return trythunk(); }
61 finally { finalthunk(); }
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.
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
74 try { return trythunk(); }
75 catch (e
) { cleanthunk(); throw e
; }
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
86 toString
: function () { return '#{Tag ' + this.what
+ '}'; }
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.
94 function Generation(what
) {
96 this.seq
= Generation
._next
++;
98 Generation
.prototype = {
99 toString
: function () {
100 return '#{Generation ' + this.what
+ ' #' + this.seq
.toString() + '}';
103 Generation
._next
= 0;
104 DEP
.Generation
= Generation
;
106 /*----- The system state --------------------------------------------------*/
108 var GENERATION
= new Generation('dep-generation');
109 // Current recomputation generation.
111 var EVALUATING
= null; // The dep being re-evaluated.
112 var STATE
= 'ready'; // The current state.
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.
121 var BAD
= Tag('BAD') // Used for the value of `bad' deps.
123 var DELAYED
= []; // Actions delayed by `with_frozen'.
124 var PENDING
= []; // Deps awaiting recomputation.
126 /*----- Exceptions --------------------------------------------------------*/
128 CircularDependency
= new Tag('CircularDependency');
129 DEP
.CircularDependency
= CircularDependency
;
131 BusyRecomputing
= new Tag('BusyRecomputing');
132 DEP
.BusyRecomputing
= BusyRecomputing
;
134 /*----- Main code ---------------------------------------------------------*/
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.
141 * A `Dep' object may have listener functions attached to it. These
142 * functions will bw called when its value changes.
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.
148 function Dep(value
, maybefunc
) {
149 /* Initialize a new `Dep' object.
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'.
158 * Some properties can be fiddled with by client programs (rather than
159 * trying to invent some crazy option-parsing protocol in the constructor).
161 * `name' A string name for this `Dep', used when printing.
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.
168 var val
, func
, f
= F_CHANGED
;
171 // Work out what's going on with our crazy argument convention.
172 if (maybefunc
!== undefined
) {
175 f
|= F_VALUE
| F_QUEUED
;
176 } else if (typeof value
=== 'function') {
183 f
|= F_VALUE
| F_DEPS
;
186 // Initialize the various slots.
187 this._value_function
= func
; // Recomputation function.
188 this._value
= val
; // Current value.
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.
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.
205 // If we have a recomputation function then exercise it.
207 with_frozen(function () {
214 Dep
._seq
= 0; // Next sequence number to allocate.
218 toString
: function () {
219 /* Convert the receiver to a string.
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.
228 var f
= this._flags();
232 if (this.name
!== null) s
+= ' "' + this.name
+ '"';
234 // Sequence number -- distinguishes the dep if nothing else will.
235 s
+= ' #' + this._seq
;
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();
243 if (!(f
& F_DEPS
)) s
+= ' :recompute-deps';
244 if (f
& F_QUEUED
) s
+= ' :queued';
245 if (f
& F_CHANGED
) s
+= ' :changed';
252 _flags
: function () {
253 /* Return the receiver's flags.
255 * If the receiver isn't up-to-date then we synthesize the flags.
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
;
264 _update
: function (value
) {
265 /* Store VALUE as the receiver's value.
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.
272 this._value
=== BAD
:
273 (this._value
!== BAD
&&
274 this.equivp(value
, this._value
)))
282 _new_value
: function () {
283 /* Run the `_value_function' of the receiver, returning the result.
285 * If a bad dep is read during this then return `BAD'. Other exceptions
286 * are propagated in the usual way.
289 var old
= EVALUATING
;
293 this._dependencies
= { };
294 return try_finally(function () {
296 return orelse(function () { return me
._value_function(); },
297 function () { return BAD
; });
303 _propagate
: function () {
304 /* Propagate a change in the receiver to dependents and listeners. */
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
];
314 if (!(f
& (F_QUEUED
| F_DEPS
))) {
316 d
._generation
= GENERATION
;
317 d
.__flags
= (f
& ~F_VALUE
) | F_QUEUED
;
321 // We no longer have any dependents. Maybe we'll acquire more when the
322 // old dependents recompute themselves.
323 this._dependents
= { };
325 // Tell the listeners that something interesting happened.
326 dolist(this._listeners
, function (l
) { l(); });
329 _recompute
: function () {
330 /* Recompute the receiver, propagating changes and so on.
332 * Return whether we actually needed to change anything.
335 var queued
= this.__flags
& F_QUEUED
;
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
;
345 me
.__flags
= queued
| F_VALUE
| F_DEPS
;
350 // Try to recompute our value. If that doesn't work then mark us as bad
351 // and propagate that.
352 return try_cleanup(function () { return update(me
._new_value()); },
353 function () { update(BAD
); });
356 _force
: function () {
357 /* Make sure the receiver has a current value.
359 * Return true if the receiver's value has changed in this recomputation
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.
368 var f
= this._flags();
371 if (f
& F_RECOMPUTING
) throw CircularDependency
;
372 else if (f
& F_VALUE
) return f
& F_CHANGED
;
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;
379 return this._recompute();
388 /* Fetch and return the receiver's current value.
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.
397 if (state
=== 'recomputing') {
399 this._dependents
[EVALUATING
._seq
] = EVALUATING
;
400 EVALUATING
._dependencies
[this._seq
] = this;
405 if (val
=== BAD
) throw BAD
;
409 set_value
: function (value
) {
410 /* Set the receiver's value to VALUE, and propagate. */
414 with_frozen(function () {
415 if (me
._update(value
)) {
416 me
._generation
= GENERATION
;
417 me
.__flags
= F_VALUE
| F_CHANGED
;
423 make_bad
: function () {
424 /* Mark the receiver as being bad, and propagate. */
428 add_listener
: function (func
) {
429 /* Add FUNC to the receiver's list of listeners.
431 * Listener functions are called without arguments, and any values
432 * returned are ignored.
435 this._listeners
.push(func
);
439 /* Return whether the receiver is good (i.e., not marked as bad). */
441 return this._value
!== BAD
;
445 function orelse(thunk
, errthunk
) {
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.
451 try { return thunk(); }
453 if (e
=== BAD
) { return errthunk(); }
460 /* For use in a value-function: make the dep be bad. */
465 function recompute_pending() {
466 /* Recompute any pending dependencies.
468 * The state is `recomputing' during this.
473 state
= 'recomputing';
474 try_finally(function () {
475 while (PENDING
.length
) {
478 d
.__flags
= f
& ~F_QUEUED
;
481 else if (!(f
& F_DEPS
)) {
483 d
.__flags
= f
| F_DEPS
;
487 while (PENDING
.length
) {
494 function with_frozen(body
, delay
) {
495 /* Call BODY with dependencies frozen.
497 * If the BODY function changes any dep values (using D.set_value(...))
498 * then dependents won't be updated until the BODY completes.
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
507 var old_delayed
, old_pending
;
514 if (!delay
) throw BusyRecomputing
;
518 old_delayed
= DELAYED
;
519 old_pending
= PENDING
;
520 try_finally(function () {
523 GENERATION
= new Generation('dep-generation');
527 if (!DELAYED
.length
) break;
528 op
= DELAYED
.shift();
532 DELAYED
= old_delayed
;
533 PENDING
= old_pending
;
538 DEP
.with_frozen
= with_frozen
;
540 /*----- That's all, folks -------------------------------------------------*/