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 () { with (DEP
) {
26 /*----- Utility functions and classes -------------------------------------*/
28 DEP
.dolist
= function (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
]);
41 /* A standard equality function, suitable for detecting changes to `Dep'
42 * objects. This may be needlessly sensitive for some cases, but at least
43 * that's slow rather than wrong.
49 /* A Tag is an object which is interesting only because of its identity, and
50 * that the set of Tags is basically determined by the static structure of
53 DEP
.Tag
= function (what
) {
57 toString
: function () { return '#{Tag ' + this.what
+ '}'; }
60 /* A Generation is like a Tag, except that it's expected that a program will
61 * manufacture Generations repeatedly, and perhaps use them to determine
62 * whether an object is `up-to-date' in some sense.
64 DEP
.Generation
= function (what
) {
66 this.seq
= Generation
._next
++;
68 Generation
.prototype = {
69 toString
: function () {
70 return '#{Generation ' + this.what
+ ' #' + this.seq
.toString() + '}';
74 DEP
.Generation
= Generation
;
76 /*----- The system state --------------------------------------------------*/
78 var GENERATION
= new Generation('dep-generation');
79 // Current recomputation generation.
81 var EVALUATING
= null; // The dep being re-evaluated.
82 var STATE
= 'ready'; // The current state.
84 /* Flags for Dep objects. */
85 var F_VALUE
= 1; // Value is up-to-date.
86 var F_DEPS
= 2; // Known as a dependent.
87 var F_CHANGED
= 4; // Changed in current phase.
88 var F_RECOMPUTING
= 8; // Currently being recomputed.
89 var F_QUEUED
= 16; // Queued for recomputation.
91 var BAD
= Tag('BAD') // Used for the value of `bad' deps.
93 var DELAYED
= []; // Actions delayed by `with_frozen'.
94 var PENDING
= []; // Deps awaiting recomputation.
96 /*----- Exceptions --------------------------------------------------------*/
98 DEP
.CircularDependency
= new Tag('CircularDependency');
99 DEP
.BusyRecomputing
= new Tag('BusyRecomputing');
101 /*----- Main code ---------------------------------------------------------*/
103 /* A `Dep' object maintains a value, either because it was provided
104 * explicitly by the programmer, or computed in terms of other `Dep' objects.
105 * In the latter case, its value will be recomputed if any of its
106 * dependencies change value.
108 * A `Dep' object may have listener functions attached to it. These
109 * functions will bw called when its value changes.
111 * A `Dep' may be `bad'. In this case, use of its value by a dependent
112 * causes that `Dep' to become bad in turn.
115 DEP
.Dep
= function (value
, maybefunc
) {
116 /* Initialize a new `Dep' object.
118 * Handling of the arguments is a little fiddly. If two arguments are
119 * provided then the first is set as the value and the second as the
120 * recomputation function. Otherwise, the first argument is interpreted as
121 * the recomputation function if it has `function' type, or as an initial
122 * explicit value otherwise. To force a function to be interpreted as an
123 * initial value, pass a second argument of `null'.
125 * Some properties can be fiddled with by client programs (rather than
126 * trying to invent some crazy option-parsing protocol in the constructor).
128 * `name' A string name for this `Dep', used when printing.
130 * `equivp' A predicate for deciding whether two value assigned
131 * to this `Dep' are equivalent. Used to decide whether
132 * a change should be propagated.
135 var val
, func
, f
= F_CHANGED
;
138 // Work out what's going on with our crazy argument convention.
139 if (maybefunc
!== undefined
) {
142 f
|= F_VALUE
| F_QUEUED
;
143 } else if (typeof value
=== 'function') {
150 f
|= F_VALUE
| F_DEPS
;
153 // Initialize the various slots.
154 this._value_function
= func
; // Recomputation function.
155 this._value
= val
; // Current value.
157 this.name
= undefined
; // Name, for printing.
158 this.equivp
= eql
; // Equivalent-value predicate.
159 this.__flags
= f
; // Current flags.
160 this._generation
= GENERATION
; // Have we done this one already?.
161 this._listeners
= []; // List of listener functions.
163 // We need to maintain the dependency graph. In order to prevent duplicate
164 // entries in the various sets, we use maps rather than lists, but this
165 // presents a problem with coming up with keys: JavaScript stringifies
166 // objects rather than using them as-is, which is obviously hopeless. So
167 // assign each `Dep' a unique sequence number and use that as the key.
168 this._seq
= Dep
._seq
++; // For identifying this object.
169 this._dependents
= { }; // Set of dependent objects.
170 this._dependencies
= { }; // Set of objects we depend on.
172 // If we have a recomputation function then exercise it.
174 with_frozen(function () {
180 Dep
._seq
= 0; // Next sequence number to allocate.
184 toString
: function () {
185 /* Convert the receiver to a string.
187 * The printed representation includes a number of bits of information
188 * which are probably meaningless to most readers but are handy for
189 * debugging this library if it's misbehaving.
194 var f
= this._flags();
198 if (this.name
!== null) s
+= ' "' + this.name
+ '"';
200 // Sequence number -- distinguishes the dep if nothing else will.
201 s
+= ' #' + this._seq
;
203 // The value, or some kind of marker that it doesn't have one.
204 if (!(f
& F_VALUE
)) s
+= ' #{out-of-date}';
205 else if (v
=== BAD
) s
+= ' #{bad}';
206 else s
+= ' ' + v
.toString();
209 if (!(f
& F_DEPS
)) s
+= ' :recompute-deps';
210 if (f
& F_QUEUED
) s
+= ' :queued';
211 if (f
& F_CHANGED
) s
+= ' :changed';
218 _flags
: function () {
219 /* Return the receiver's flags.
221 * If the receiver isn't up-to-date then we synthesize the flags.
224 if (this.state
=== 'ready') return F_VALUE
| F_DEPS
;
225 else if (this._generation
=== GENERATION
) return this.__flags
;
226 else if (this._value_function
=== null) return F_VALUE
| F_DEPS
;
230 _update
: function (value
) {
231 /* Store VALUE as the receiver's value.
233 * Return whether the value has changed as a result. This is a low-level
234 * function which doesn't handle propagation or anything like that.
238 this._value
=== BAD
:
239 (this._value
!== BAD
&&
240 this.equivp(value
, this._value
)))
248 _new_value
: function () {
249 /* Run the `_value_function' of the receiver, returning the result.
251 * If a bad dep is read during this then return `BAD'. Other exceptions
252 * are propagated in the usual way.
255 var old
= EVALUATING
;
258 this._dependencies
= { };
262 return this._value_function();
264 if (e
=== BAD
) return BAD
;
272 _propagate
: function () {
273 /* Propagate a change in the receiver to dependents and listeners. */
277 // Iterate over each dependent, pushing each one onto the `PENDING'
278 // queue, bringing it into the current generation, and marking it as
279 // having no current value.
280 for (di
in this._dependents
) {
281 d
= this._dependents
[di
];
283 if (!(f
& (F_QUEUED
| F_DEPS
))) {
285 d
._generation
= GENERATION
;
286 d
.__flags
= (f
& ~F_VALUE
) | F_QUEUED
;
290 // We no longer have any dependents. Maybe we'll acquire more when the
291 // old dependents recompute themselves.
292 this._dependents
= { };
294 // Tell the listeners that something interesting happened.
295 dolist(this._listeners
, function (l
) { l(); });
298 _recompute
: function () {
299 /* Recompute the receiver, propagating changes and so on.
301 * Return whether we actually needed to change anything.
304 var queued
= this.__flags
& F_QUEUED
;
308 // Update us with the given VALUE.
309 function update(value
) {
310 if (me
._update(value
)) {
311 me
.__flags
= queued
| F_VALUE
| F_DEPS
| F_CHANGED
;
315 me
.__flags
= queued
| F_VALUE
| F_DEPS
;
320 // Try to recompute our value. If that doesn't work then mark us as bad
321 // and propagate that.
323 return update(this._new_value());
330 _force
: function () {
331 /* Make sure the receiver has a current value.
333 * Return true if the receiver's value has changed in this recomputation
336 * If it already has a good value then just return. Otherwise mark it
337 * as recomputing (to trap circularities) and poke our dependencies to
338 * ensure that they're up-to-date. If they weren't, then we recompute
339 * our own value before returning.
342 var f
= this._flags();
345 if (f
& F_RECOMPUTING
) throw CircularDependency
;
346 else if (f
& F_VALUE
) return f
& F_CHANGED
;
348 this._generation
= GENERATION
;
349 this.__flags
= (f
& ~F_QUEUED
) | F_RECOMPUTING
;
350 for (d
in this._dependencies
)
351 if (this._dependencies
[d
]._force()) any
= true;
353 return this._recompute();
362 /* Fetch and return the receiver's current value.
364 * If the receiver is bad then an exception is thrown. This exception
365 * can be caught using `orelse'; a dep recomputation function can let the
366 * exception propagate, and be marked as bad in turn.
371 if (state
=== 'recomputing') {
373 this._dependents
[EVALUATING
._seq
] = EVALUATING
;
374 EVALUATING
._dependencies
[this._seq
] = this;
379 if (val
=== BAD
) throw BAD
;
383 set_value
: function (value
) {
384 /* Set the receiver's value to VALUE, and propagate. */
388 with_frozen(function () {
389 if (me
._update(value
)) {
390 me
._generation
= GENERATION
;
391 me
.__flags
= F_VALUE
| F_CHANGED
;
397 make_bad
: function () {
398 /* Mark the receiver as being bad, and propagate. */
402 add_listener
: function (func
) {
403 /* Add FUNC to the receiver's list of listeners.
405 * Listener functions are called without arguments, and any values
406 * returned are ignored.
409 this._listeners
.push(func
);
413 /* Return whether the receiver is good (i.e., not marked as bad). */
415 return this._value
!== BAD
;
419 DEP
.orelse
= function (thunk
, errthunk
) {
420 /* Call THUNK. If it succeeds, then return its result. If THUNK
421 * reads a bad dep then call ERRTHINK and return its result instead.
425 try { return thunk(); }
427 if (e
=== BAD
) { return errthunk(); }
432 DEP
.bad
= function () {
433 /* For use in a value-function: make the dep be bad. */
437 function recompute_pending() {
438 /* Recompute any pending dependencies.
440 * The state is `recomputing' during this.
445 state
= 'recomputing';
447 while (PENDING
.length
) {
450 d
.__flags
= f
& ~F_QUEUED
;
453 else if (!(f
& F_DEPS
)) {
455 d
.__flags
= f
| F_DEPS
;
459 while (PENDING
.length
) {
466 DEP
.with_frozen
= function (body
, delay
) {
467 /* Call BODY with dependencies frozen.
469 * If the BODY function changes any dep values (using D.set_value(...))
470 * then dependents won't be updated until the BODY completes.
473 * bad to do this during a recomputation phase. If DELAY is true, then the
474 * BODY is delayed until the recomputation completes; otherwise you get an
479 var old_delayed
, old_pending
;
486 if (!delay
) throw BusyRecomputing
;
490 old_delayed
= DELAYED
;
491 old_pending
= PENDING
;
495 GENERATION
= new Generation('dep-generation');
499 if (!DELAYED
.length
) break;
500 op
= DELAYED
.shift();
504 DELAYED
= old_delayed
;
505 PENDING
= old_pending
;
511 /*----- That's all, folks -------------------------------------------------*/