Commit | Line | Data |
---|---|---|
ac26861c MW |
1 | /* -*-javascript-*- |
2 | * | |
3 | * Dependency-based computation. | |
4 | * | |
5 | * (c) 2013 Mark Wooding | |
6 | */ | |
7 | ||
8 | /*----- Licensing notice --------------------------------------------------* | |
9 | * | |
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. | |
14 | * | |
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. | |
19 | * | |
20 | * You should have received a copy of the GNU General Public License | |
8a0fc4a2 | 21 | * along with this program; if not, see <https://www.gnu.org/licenses/>. |
ac26861c MW |
22 | */ |
23 | ||
6cfd4191 | 24 | var DEP = { }; (function () { |
ac26861c MW |
25 | |
26 | /*----- Utility functions and classes -------------------------------------*/ | |
27 | ||
26176703 MW |
28 | DEP.DEBUG = false; |
29 | function blather(msg) { | |
30 | /* Report MSG to the log if we're debugging. */ | |
31 | if (DEP.DEBUG) console.log(";; " + msg); | |
32 | } | |
33 | function show(what, value) { | |
34 | /* Report that WHAT has the value VALUE, if we're debugging; and, | |
35 | * regardless, return VALUE. | |
36 | */ | |
37 | blather(what + " = " + value); | |
38 | return value; | |
39 | } | |
40 | ||
6cfd4191 | 41 | function dolist(list, func) { |
ac26861c MW |
42 | /* Apply FUNC to each element of LIST, discarding the results. |
43 | * | |
44 | * JavaScript's looping iterates over indices rather than values, which is | |
45 | * consistent with what you want from a mapping, but inconvenient for | |
46 | * sequences. | |
47 | */ | |
48 | ||
49 | var i; | |
50 | for (i in list) func(list[i]); | |
51 | } | |
6cfd4191 | 52 | DEP.dolist = dolist; |
ac26861c MW |
53 | |
54 | function eql(x, y) { | |
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. | |
58 | */ | |
59 | ||
60 | return x === y; | |
61 | } | |
62 | ||
5a0d36b9 MW |
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. | |
67 | * | |
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 | |
70 | * for the compiler). | |
71 | */ | |
72 | ||
73 | try { return trythunk(); } | |
74 | finally { finalthunk(); } | |
75 | } | |
76 | ||
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. | |
80 | * | |
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 | |
83 | * for the compiler). | |
84 | */ | |
85 | ||
86 | var e; | |
87 | try { return trythunk(); } | |
88 | catch (e) { cleanthunk(); throw e; } | |
89 | } | |
90 | ||
ac26861c MW |
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 | |
93 | * the program. | |
94 | */ | |
6cfd4191 | 95 | function Tag(what) { |
ac26861c MW |
96 | this.what = what; |
97 | } | |
98 | Tag.prototype = { | |
99 | toString: function () { return '#{Tag ' + this.what + '}'; } | |
100 | } | |
6cfd4191 | 101 | DEP.Tag = Tag; |
ac26861c MW |
102 | |
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. | |
106 | */ | |
6cfd4191 | 107 | function Generation(what) { |
ac26861c MW |
108 | this.what = what; |
109 | this.seq = Generation._next++; | |
110 | } | |
111 | Generation.prototype = { | |
112 | toString: function () { | |
113 | return '#{Generation ' + this.what + ' #' + this.seq.toString() + '}'; | |
114 | } | |
115 | }; | |
116 | Generation._next = 0; | |
117 | DEP.Generation = Generation; | |
118 | ||
119 | /*----- The system state --------------------------------------------------*/ | |
120 | ||
121 | var GENERATION = new Generation('dep-generation'); | |
122 | // Current recomputation generation. | |
123 | ||
124 | var EVALUATING = null; // The dep being re-evaluated. | |
125 | var STATE = 'ready'; // The current state. | |
126 | ||
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. | |
133 | ||
c0644ca0 | 134 | var BAD = new Tag('BAD'); // Used for the value of `bad' deps. |
ac26861c MW |
135 | |
136 | var DELAYED = []; // Actions delayed by `with_frozen'. | |
137 | var PENDING = []; // Deps awaiting recomputation. | |
138 | ||
139 | /*----- Exceptions --------------------------------------------------------*/ | |
140 | ||
6cfd4191 MW |
141 | CircularDependency = new Tag('CircularDependency'); |
142 | DEP.CircularDependency = CircularDependency; | |
143 | ||
144 | BusyRecomputing = new Tag('BusyRecomputing'); | |
145 | DEP.BusyRecomputing = BusyRecomputing; | |
ac26861c MW |
146 | |
147 | /*----- Main code ---------------------------------------------------------*/ | |
148 | ||
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. | |
153 | * | |
154 | * A `Dep' object may have listener functions attached to it. These | |
155 | * functions will bw called when its value changes. | |
156 | * | |
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. | |
159 | */ | |
160 | ||
6cfd4191 | 161 | function Dep(value, maybefunc) { |
ac26861c MW |
162 | /* Initialize a new `Dep' object. |
163 | * | |
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'. | |
170 | * | |
171 | * Some properties can be fiddled with by client programs (rather than | |
172 | * trying to invent some crazy option-parsing protocol in the constructor). | |
173 | * | |
174 | * `name' A string name for this `Dep', used when printing. | |
175 | * | |
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. | |
179 | */ | |
180 | ||
181 | var val, func, f = F_CHANGED; | |
182 | var me = this; | |
183 | ||
184 | // Work out what's going on with our crazy argument convention. | |
185 | if (maybefunc !== undefined) { | |
186 | val = value; | |
187 | func = maybefunc; | |
188 | f |= F_VALUE | F_QUEUED; | |
189 | } else if (typeof value === 'function') { | |
190 | val = BAD; | |
191 | func = value; | |
192 | f |= F_QUEUED; | |
193 | } else { | |
c0644ca0 | 194 | val = value === undefined ? BAD : value; |
ac26861c MW |
195 | func = null; |
196 | f |= F_VALUE | F_DEPS; | |
197 | } | |
198 | ||
199 | // Initialize the various slots. | |
200 | this._value_function = func; // Recomputation function. | |
201 | this._value = val; // Current value. | |
202 | ||
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. | |
208 | ||
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. | |
217 | ||
218 | // If we have a recomputation function then exercise it. | |
26176703 | 219 | blather("new dep " + me); |
ac26861c MW |
220 | if (func !== null) { |
221 | with_frozen(function () { | |
222 | PENDING.push(me); | |
26176703 | 223 | blather("push new dep " + me); |
ac26861c MW |
224 | }); |
225 | } | |
226 | } | |
227 | ||
6cfd4191 | 228 | DEP.Dep = Dep; |
ac26861c MW |
229 | Dep._seq = 0; // Next sequence number to allocate. |
230 | ||
231 | Dep.prototype = { | |
232 | ||
233 | toString: function () { | |
234 | /* Convert the receiver to a string. | |
235 | * | |
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. | |
239 | */ | |
240 | ||
241 | // Basic stuff. | |
242 | var s = '#{Dep'; | |
243 | var f = this._flags(); | |
244 | var v = this._value; | |
245 | ||
246 | // The dep's name. | |
247 | if (this.name !== null) s += ' "' + this.name + '"'; | |
248 | ||
249 | // Sequence number -- distinguishes the dep if nothing else will. | |
250 | s += ' #' + this._seq; | |
251 | ||
252 | // The value, or some kind of marker that it doesn't have one. | |
b51588fd | 253 | if (!(f & F_VALUE)) s += ' #{stale}'; |
ac26861c MW |
254 | else if (v === BAD) s += ' #{bad}'; |
255 | else s += ' ' + v.toString(); | |
256 | ||
257 | // Various flags. | |
258 | if (!(f & F_DEPS)) s += ' :recompute-deps'; | |
259 | if (f & F_QUEUED) s += ' :queued'; | |
260 | if (f & F_CHANGED) s += ' :changed'; | |
261 | ||
262 | // Done. | |
263 | s += '}'; | |
264 | return s; | |
265 | }, | |
266 | ||
267 | _flags: function () { | |
268 | /* Return the receiver's flags. | |
269 | * | |
270 | * If the receiver isn't up-to-date then we synthesize the flags. | |
271 | */ | |
272 | ||
d8722374 | 273 | if (STATE === 'ready') return F_VALUE | F_DEPS; |
ac26861c MW |
274 | else if (this._generation === GENERATION) return this.__flags; |
275 | else if (this._value_function === null) return F_VALUE | F_DEPS; | |
276 | else return 0; | |
277 | }, | |
278 | ||
279 | _update: function (value) { | |
280 | /* Store VALUE as the receiver's value. | |
281 | * | |
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. | |
284 | */ | |
285 | ||
26176703 | 286 | blather("_update " + this + ": " + value); |
ac26861c MW |
287 | if (value === BAD ? |
288 | this._value === BAD : | |
289 | (this._value !== BAD && | |
290 | this.equivp(value, this._value))) | |
291 | return false; | |
292 | else { | |
293 | this._value = value; | |
294 | return true; | |
295 | } | |
296 | }, | |
297 | ||
298 | _new_value: function () { | |
299 | /* Run the `_value_function' of the receiver, returning the result. | |
300 | * | |
301 | * If a bad dep is read during this then return `BAD'. Other exceptions | |
302 | * are propagated in the usual way. | |
303 | */ | |
304 | ||
305 | var old = EVALUATING; | |
5a0d36b9 MW |
306 | var me = this; |
307 | var val; | |
ac26861c MW |
308 | |
309 | this._dependencies = { }; | |
5a0d36b9 MW |
310 | return try_finally(function () { |
311 | EVALUATING = me; | |
26176703 MW |
312 | return show("_new_value for " + me, |
313 | orelse(function () { return me._value_function(); }, | |
314 | function () { return show("ret", BAD); })); | |
5a0d36b9 | 315 | }, function() { |
ac26861c | 316 | EVALUATING = old; |
5a0d36b9 | 317 | }); |
ac26861c MW |
318 | }, |
319 | ||
320 | _propagate: function () { | |
321 | /* Propagate a change in the receiver to dependents and listeners. */ | |
322 | ||
323 | var d, di, f; | |
324 | ||
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]; | |
330 | f = d._flags(); | |
331 | if (!(f & (F_QUEUED | F_DEPS))) { | |
332 | PENDING.push(d); | |
333 | d._generation = GENERATION; | |
334 | d.__flags = (f & ~F_VALUE) | F_QUEUED; | |
335 | } | |
336 | } | |
337 | ||
338 | // We no longer have any dependents. Maybe we'll acquire more when the | |
339 | // old dependents recompute themselves. | |
340 | this._dependents = { }; | |
341 | ||
342 | // Tell the listeners that something interesting happened. | |
343 | dolist(this._listeners, function (l) { l(); }); | |
344 | }, | |
345 | ||
346 | _recompute: function () { | |
347 | /* Recompute the receiver, propagating changes and so on. | |
348 | * | |
349 | * Return whether we actually needed to change anything. | |
350 | */ | |
351 | ||
352 | var queued = this.__flags & F_QUEUED; | |
ac26861c MW |
353 | var me = this; |
354 | ||
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; | |
359 | me._propagate(); | |
360 | return true; | |
361 | } else { | |
362 | me.__flags = queued | F_VALUE | F_DEPS; | |
363 | return false; | |
364 | } | |
365 | }; | |
366 | ||
367 | // Try to recompute our value. If that doesn't work then mark us as bad | |
368 | // and propagate that. | |
5a0d36b9 MW |
369 | return try_cleanup(function () { return update(me._new_value()); }, |
370 | function () { update(BAD); }); | |
ac26861c MW |
371 | }, |
372 | ||
373 | _force: function () { | |
374 | /* Make sure the receiver has a current value. | |
375 | * | |
376 | * Return true if the receiver's value has changed in this recomputation | |
377 | * phase. | |
378 | * | |
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. | |
383 | */ | |
384 | ||
385 | var f = this._flags(); | |
386 | var d, any = false; | |
387 | ||
388 | if (f & F_RECOMPUTING) throw CircularDependency; | |
389 | else if (f & F_VALUE) return f & F_CHANGED; | |
390 | else { | |
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; | |
395 | if (any) | |
396 | return this._recompute(); | |
397 | else { | |
398 | this.__flags = f; | |
399 | return false; | |
400 | } | |
401 | } | |
402 | }, | |
403 | ||
404 | value: function () { | |
405 | /* Fetch and return the receiver's current value. | |
406 | * | |
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. | |
410 | */ | |
411 | ||
412 | var val; | |
413 | ||
d8722374 | 414 | if (STATE === 'recomputing') { |
f2059c0f | 415 | this._force(); |
ac26861c MW |
416 | if (EVALUATING) { |
417 | this._dependents[EVALUATING._seq] = EVALUATING; | |
418 | EVALUATING._dependencies[this._seq] = this; | |
419 | } | |
ac26861c MW |
420 | } |
421 | val = this._value; | |
26176703 | 422 | blather("value " + this + ": " + val); |
ac26861c MW |
423 | if (val === BAD) throw BAD; |
424 | return val; | |
425 | }, | |
426 | ||
427 | set_value: function (value) { | |
428 | /* Set the receiver's value to VALUE, and propagate. */ | |
429 | ||
430 | var me = this; | |
431 | ||
432 | with_frozen(function () { | |
433 | if (me._update(value)) { | |
434 | me._generation = GENERATION; | |
435 | me.__flags = F_VALUE | F_CHANGED; | |
436 | me._propagate(); | |
437 | } | |
438 | }); | |
439 | }, | |
440 | ||
441 | make_bad: function () { | |
442 | /* Mark the receiver as being bad, and propagate. */ | |
443 | this.set_value(BAD); | |
444 | }, | |
445 | ||
446 | add_listener: function (func) { | |
447 | /* Add FUNC to the receiver's list of listeners. | |
448 | * | |
449 | * Listener functions are called without arguments, and any values | |
450 | * returned are ignored. | |
451 | */ | |
452 | ||
453 | this._listeners.push(func); | |
454 | }, | |
455 | ||
456 | goodp: function () { | |
457 | /* Return whether the receiver is good (i.e., not marked as bad). */ | |
458 | ||
459 | return this._value !== BAD; | |
460 | } | |
461 | }; | |
462 | ||
6cfd4191 | 463 | function orelse(thunk, errthunk) { |
ac26861c | 464 | /* Call THUNK. If it succeeds, then return its result. If THUNK |
55be9d83 | 465 | * reads a bad dep then call ERRTHUNK and return its result instead. |
ac26861c MW |
466 | */ |
467 | ||
468 | var e; | |
469 | try { return thunk(); } | |
470 | catch (e) { | |
471 | if (e === BAD) { return errthunk(); } | |
472 | else throw e; | |
473 | } | |
474 | } | |
6cfd4191 | 475 | DEP.orelse = orelse; |
ac26861c | 476 | |
6cfd4191 | 477 | function bad() { |
ac26861c MW |
478 | /* For use in a value-function: make the dep be bad. */ |
479 | throw BAD; | |
480 | } | |
6cfd4191 | 481 | DEP.bad = bad; |
ac26861c MW |
482 | |
483 | function recompute_pending() { | |
484 | /* Recompute any pending dependencies. | |
485 | * | |
486 | * The state is `recomputing' during this. | |
487 | */ | |
488 | ||
489 | var d, f; | |
d8722374 MW |
490 | var old_state = STATE; |
491 | STATE = 'recomputing'; | |
26176703 | 492 | blather("STATE <- :recomputing"); |
5a0d36b9 | 493 | try_finally(function () { |
ac26861c MW |
494 | while (PENDING.length) { |
495 | d = PENDING.shift(); | |
496 | f = d.__flags; | |
497 | d.__flags = f & ~F_QUEUED; | |
498 | if (!(f & F_VALUE)) | |
499 | d._recompute(); | |
500 | else if (!(f & F_DEPS)) { | |
501 | d.new_value(); | |
502 | d.__flags = f | F_DEPS; | |
503 | } | |
504 | } | |
5a0d36b9 | 505 | }, function () { |
ac26861c MW |
506 | while (PENDING.length) { |
507 | d = PENDING.shift(); | |
508 | d._value = BAD; | |
26176703 | 509 | blather("recompute_pending mark " + d); |
ac26861c | 510 | } |
d8722374 | 511 | STATE = old_state; |
26176703 | 512 | blather("STATE <- :" + old_state); |
5a0d36b9 | 513 | }); |
ac26861c MW |
514 | } |
515 | ||
6cfd4191 | 516 | function with_frozen(body, delay) { |
ac26861c MW |
517 | /* Call BODY with dependencies frozen. |
518 | * | |
519 | * If the BODY function changes any dep values (using D.set_value(...)) | |
520 | * then dependents won't be updated until the BODY completes. | |
521 | * | |
1eef3da3 MW |
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. | |
ac26861c MW |
525 | */ |
526 | ||
527 | var op, val; | |
d8722374 | 528 | var old_delayed, old_pending, old_state; |
ac26861c MW |
529 | |
530 | switch (STATE) { | |
531 | case 'frozen': | |
532 | body(); | |
533 | break; | |
534 | case 'recomputing': | |
535 | if (!delay) throw BusyRecomputing; | |
536 | DELAYED.push(body); | |
537 | break; | |
538 | case 'ready': | |
539 | old_delayed = DELAYED; | |
540 | old_pending = PENDING; | |
d8722374 MW |
541 | old_state = STATE; |
542 | STATE = "frozen"; | |
26176703 | 543 | blather("STATE <- :frozen"); |
5a0d36b9 | 544 | try_finally(function () { |
ac26861c MW |
545 | DELAYED = []; |
546 | PENDING = []; | |
547 | GENERATION = new Generation('dep-generation'); | |
548 | val = body(); | |
549 | for (;;) { | |
550 | recompute_pending(); | |
551 | if (!DELAYED.length) break; | |
552 | op = DELAYED.shift(); | |
553 | op(); | |
554 | } | |
5a0d36b9 | 555 | }, function () { |
ac26861c MW |
556 | DELAYED = old_delayed; |
557 | PENDING = old_pending; | |
d8722374 | 558 | STATE = old_state; |
26176703 | 559 | blather("STATE <- :" + old_state); |
5a0d36b9 | 560 | }); |
ac26861c MW |
561 | break; |
562 | } | |
563 | } | |
6cfd4191 | 564 | DEP.with_frozen = with_frozen; |
ac26861c MW |
565 | |
566 | /*----- That's all, folks -------------------------------------------------*/ | |
6cfd4191 | 567 | })(); |