9dd42b48455fc6647deb894eeaeaa425a3d1c072
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 /* A Tag is an object which is interesting only because of its identity, and
51 * that the set of Tags is basically determined by the static structure of
58 toString
: function () { return '#{Tag ' + this.what
+ '}'; }
62 /* A Generation is like a Tag, except that it's expected that a program will
63 * manufacture Generations repeatedly, and perhaps use them to determine
64 * whether an object is `up-to-date' in some sense.
66 function Generation(what
) {
68 this.seq
= Generation
._next
++;
70 Generation
.prototype = {
71 toString
: function () {
72 return '#{Generation ' + this.what
+ ' #' + this.seq
.toString() + '}';
76 DEP
.Generation
= Generation
;
78 /*----- The system state --------------------------------------------------*/
80 var GENERATION
= new Generation('dep-generation');
81 // Current recomputation generation.
83 var EVALUATING
= null; // The dep being re-evaluated.
84 var STATE
= 'ready'; // The current state.
86 /* Flags for Dep objects. */
87 var F_VALUE
= 1; // Value is up-to-date.
88 var F_DEPS
= 2; // Known as a dependent.
89 var F_CHANGED
= 4; // Changed in current phase.
90 var F_RECOMPUTING
= 8; // Currently being recomputed.
91 var F_QUEUED
= 16; // Queued for recomputation.
93 var BAD
= Tag('BAD') // Used for the value of `bad' deps.
95 var DELAYED
= []; // Actions delayed by `with_frozen'.
96 var PENDING
= []; // Deps awaiting recomputation.
98 /*----- Exceptions --------------------------------------------------------*/
100 CircularDependency
= new Tag('CircularDependency');
101 DEP
.CircularDependency
= CircularDependency
;
103 BusyRecomputing
= new Tag('BusyRecomputing');
104 DEP
.BusyRecomputing
= BusyRecomputing
;
106 /*----- Main code ---------------------------------------------------------*/
108 /* A `Dep' object maintains a value, either because it was provided
109 * explicitly by the programmer, or computed in terms of other `Dep' objects.
110 * In the latter case, its value will be recomputed if any of its
111 * dependencies change value.
113 * A `Dep' object may have listener functions attached to it. These
114 * functions will bw called when its value changes.
116 * A `Dep' may be `bad'. In this case, use of its value by a dependent
117 * causes that `Dep' to become bad in turn.
120 function Dep(value
, maybefunc
) {
121 /* Initialize a new `Dep' object.
123 * Handling of the arguments is a little fiddly. If two arguments are
124 * provided then the first is set as the value and the second as the
125 * recomputation function. Otherwise, the first argument is interpreted as
126 * the recomputation function if it has `function' type, or as an initial
127 * explicit value otherwise. To force a function to be interpreted as an
128 * initial value, pass a second argument of `null'.
130 * Some properties can be fiddled with by client programs (rather than
131 * trying to invent some crazy option-parsing protocol in the constructor).
133 * `name' A string name for this `Dep', used when printing.
135 * `equivp' A predicate for deciding whether two value assigned
136 * to this `Dep' are equivalent. Used to decide whether
137 * a change should be propagated.
140 var val
, func
, f
= F_CHANGED
;
143 // Work out what's going on with our crazy argument convention.
144 if (maybefunc
!== undefined
) {
147 f
|= F_VALUE
| F_QUEUED
;
148 } else if (typeof value
=== 'function') {
155 f
|= F_VALUE
| F_DEPS
;
158 // Initialize the various slots.
159 this._value_function
= func
; // Recomputation function.
160 this._value
= val
; // Current value.
162 this.name
= undefined
; // Name, for printing.
163 this.equivp
= eql
; // Equivalent-value predicate.
164 this.__flags
= f
; // Current flags.
165 this._generation
= GENERATION
; // Have we done this one already?.
166 this._listeners
= []; // List of listener functions.
168 // We need to maintain the dependency graph. In order to prevent duplicate
169 // entries in the various sets, we use maps rather than lists, but this
170 // presents a problem with coming up with keys: JavaScript stringifies
171 // objects rather than using them as-is, which is obviously hopeless. So
172 // assign each `Dep' a unique sequence number and use that as the key.
173 this._seq
= Dep
._seq
++; // For identifying this object.
174 this._dependents
= { }; // Set of dependent objects.
175 this._dependencies
= { }; // Set of objects we depend on.
177 // If we have a recomputation function then exercise it.
179 with_frozen(function () {
186 Dep
._seq
= 0; // Next sequence number to allocate.
190 toString
: function () {
191 /* Convert the receiver to a string.
193 * The printed representation includes a number of bits of information
194 * which are probably meaningless to most readers but are handy for
195 * debugging this library if it's misbehaving.
200 var f
= this._flags();
204 if (this.name
!== null) s
+= ' "' + this.name
+ '"';
206 // Sequence number -- distinguishes the dep if nothing else will.
207 s
+= ' #' + this._seq
;
209 // The value, or some kind of marker that it doesn't have one.
210 if (!(f
& F_VALUE
)) s
+= ' #{out-of-date}';
211 else if (v
=== BAD
) s
+= ' #{bad}';
212 else s
+= ' ' + v
.toString();
215 if (!(f
& F_DEPS
)) s
+= ' :recompute-deps';
216 if (f
& F_QUEUED
) s
+= ' :queued';
217 if (f
& F_CHANGED
) s
+= ' :changed';
224 _flags
: function () {
225 /* Return the receiver's flags.
227 * If the receiver isn't up-to-date then we synthesize the flags.
230 if (this.state
=== 'ready') return F_VALUE
| F_DEPS
;
231 else if (this._generation
=== GENERATION
) return this.__flags
;
232 else if (this._value_function
=== null) return F_VALUE
| F_DEPS
;
236 _update
: function (value
) {
237 /* Store VALUE as the receiver's value.
239 * Return whether the value has changed as a result. This is a low-level
240 * function which doesn't handle propagation or anything like that.
244 this._value
=== BAD
:
245 (this._value
!== BAD
&&
246 this.equivp(value
, this._value
)))
254 _new_value
: function () {
255 /* Run the `_value_function' of the receiver, returning the result.
257 * If a bad dep is read during this then return `BAD'. Other exceptions
258 * are propagated in the usual way.
261 var old
= EVALUATING
;
264 this._dependencies
= { };
268 return this._value_function();
270 if (e
=== BAD
) return BAD
;
278 _propagate
: function () {
279 /* Propagate a change in the receiver to dependents and listeners. */
283 // Iterate over each dependent, pushing each one onto the `PENDING'
284 // queue, bringing it into the current generation, and marking it as
285 // having no current value.
286 for (di
in this._dependents
) {
287 d
= this._dependents
[di
];
289 if (!(f
& (F_QUEUED
| F_DEPS
))) {
291 d
._generation
= GENERATION
;
292 d
.__flags
= (f
& ~F_VALUE
) | F_QUEUED
;
296 // We no longer have any dependents. Maybe we'll acquire more when the
297 // old dependents recompute themselves.
298 this._dependents
= { };
300 // Tell the listeners that something interesting happened.
301 dolist(this._listeners
, function (l
) { l(); });
304 _recompute
: function () {
305 /* Recompute the receiver, propagating changes and so on.
307 * Return whether we actually needed to change anything.
310 var queued
= this.__flags
& F_QUEUED
;
314 // Update us with the given VALUE.
315 function update(value
) {
316 if (me
._update(value
)) {
317 me
.__flags
= queued
| F_VALUE
| F_DEPS
| F_CHANGED
;
321 me
.__flags
= queued
| F_VALUE
| F_DEPS
;
326 // Try to recompute our value. If that doesn't work then mark us as bad
327 // and propagate that.
329 return update(this._new_value());
336 _force
: function () {
337 /* Make sure the receiver has a current value.
339 * Return true if the receiver's value has changed in this recomputation
342 * If it already has a good value then just return. Otherwise mark it
343 * as recomputing (to trap circularities) and poke our dependencies to
344 * ensure that they're up-to-date. If they weren't, then we recompute
345 * our own value before returning.
348 var f
= this._flags();
351 if (f
& F_RECOMPUTING
) throw CircularDependency
;
352 else if (f
& F_VALUE
) return f
& F_CHANGED
;
354 this._generation
= GENERATION
;
355 this.__flags
= (f
& ~F_QUEUED
) | F_RECOMPUTING
;
356 for (d
in this._dependencies
)
357 if (this._dependencies
[d
]._force()) any
= true;
359 return this._recompute();
368 /* Fetch and return the receiver's current value.
370 * If the receiver is bad then an exception is thrown. This exception
371 * can be caught using `orelse'; a dep recomputation function can let the
372 * exception propagate, and be marked as bad in turn.
377 if (state
=== 'recomputing') {
379 this._dependents
[EVALUATING
._seq
] = EVALUATING
;
380 EVALUATING
._dependencies
[this._seq
] = this;
385 if (val
=== BAD
) throw BAD
;
389 set_value
: function (value
) {
390 /* Set the receiver's value to VALUE, and propagate. */
394 with_frozen(function () {
395 if (me
._update(value
)) {
396 me
._generation
= GENERATION
;
397 me
.__flags
= F_VALUE
| F_CHANGED
;
403 make_bad
: function () {
404 /* Mark the receiver as being bad, and propagate. */
408 add_listener
: function (func
) {
409 /* Add FUNC to the receiver's list of listeners.
411 * Listener functions are called without arguments, and any values
412 * returned are ignored.
415 this._listeners
.push(func
);
419 /* Return whether the receiver is good (i.e., not marked as bad). */
421 return this._value
!== BAD
;
425 function orelse(thunk
, errthunk
) {
426 /* Call THUNK. If it succeeds, then return its result. If THUNK
427 * reads a bad dep then call ERRTHINK and return its result instead.
431 try { return thunk(); }
433 if (e
=== BAD
) { return errthunk(); }
440 /* For use in a value-function: make the dep be bad. */
445 function recompute_pending() {
446 /* Recompute any pending dependencies.
448 * The state is `recomputing' during this.
453 state
= 'recomputing';
455 while (PENDING
.length
) {
458 d
.__flags
= f
& ~F_QUEUED
;
461 else if (!(f
& F_DEPS
)) {
463 d
.__flags
= f
| F_DEPS
;
467 while (PENDING
.length
) {
474 function with_frozen(body
, delay
) {
475 /* Call BODY with dependencies frozen.
477 * If the BODY function changes any dep values (using D.set_value(...))
478 * then dependents won't be updated until the BODY completes.
481 * bad to do this during a recomputation phase. If DELAY is true, then the
482 * BODY is delayed until the recomputation completes; otherwise you get an
487 var old_delayed
, old_pending
;
494 if (!delay
) throw BusyRecomputing
;
498 old_delayed
= DELAYED
;
499 old_pending
= PENDING
;
503 GENERATION
= new Generation('dep-generation');
507 if (!DELAYED
.length
) break;
508 op
= DELAYED
.shift();
512 DELAYED
= old_delayed
;
513 PENDING
= old_pending
;
518 DEP
.with_frozen
= with_frozen
;
520 /*----- That's all, folks -------------------------------------------------*/