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 | |
21 | * along with this program; if not, see <http://www.gnu.org/licenses/>. | |
22 | */ | |
23 | ||
6cfd4191 | 24 | var DEP = { }; (function () { |
ac26861c MW |
25 | |
26 | /*----- Utility functions and classes -------------------------------------*/ | |
27 | ||
6cfd4191 | 28 | function dolist(list, func) { |
ac26861c MW |
29 | /* Apply FUNC to each element of LIST, discarding the results. |
30 | * | |
31 | * JavaScript's looping iterates over indices rather than values, which is | |
32 | * consistent with what you want from a mapping, but inconvenient for | |
33 | * sequences. | |
34 | */ | |
35 | ||
36 | var i; | |
37 | for (i in list) func(list[i]); | |
38 | } | |
6cfd4191 | 39 | DEP.dolist = dolist; |
ac26861c MW |
40 | |
41 | function eql(x, y) { | |
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. | |
45 | */ | |
46 | ||
47 | return x === y; | |
48 | } | |
49 | ||
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 | |
52 | * the program. | |
53 | */ | |
6cfd4191 | 54 | function Tag(what) { |
ac26861c MW |
55 | this.what = what; |
56 | } | |
57 | Tag.prototype = { | |
58 | toString: function () { return '#{Tag ' + this.what + '}'; } | |
59 | } | |
6cfd4191 | 60 | DEP.Tag = Tag; |
ac26861c MW |
61 | |
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. | |
65 | */ | |
6cfd4191 | 66 | function Generation(what) { |
ac26861c MW |
67 | this.what = what; |
68 | this.seq = Generation._next++; | |
69 | } | |
70 | Generation.prototype = { | |
71 | toString: function () { | |
72 | return '#{Generation ' + this.what + ' #' + this.seq.toString() + '}'; | |
73 | } | |
74 | }; | |
75 | Generation._next = 0; | |
76 | DEP.Generation = Generation; | |
77 | ||
78 | /*----- The system state --------------------------------------------------*/ | |
79 | ||
80 | var GENERATION = new Generation('dep-generation'); | |
81 | // Current recomputation generation. | |
82 | ||
83 | var EVALUATING = null; // The dep being re-evaluated. | |
84 | var STATE = 'ready'; // The current state. | |
85 | ||
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. | |
92 | ||
93 | var BAD = Tag('BAD') // Used for the value of `bad' deps. | |
94 | ||
95 | var DELAYED = []; // Actions delayed by `with_frozen'. | |
96 | var PENDING = []; // Deps awaiting recomputation. | |
97 | ||
98 | /*----- Exceptions --------------------------------------------------------*/ | |
99 | ||
6cfd4191 MW |
100 | CircularDependency = new Tag('CircularDependency'); |
101 | DEP.CircularDependency = CircularDependency; | |
102 | ||
103 | BusyRecomputing = new Tag('BusyRecomputing'); | |
104 | DEP.BusyRecomputing = BusyRecomputing; | |
ac26861c MW |
105 | |
106 | /*----- Main code ---------------------------------------------------------*/ | |
107 | ||
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. | |
112 | * | |
113 | * A `Dep' object may have listener functions attached to it. These | |
114 | * functions will bw called when its value changes. | |
115 | * | |
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. | |
118 | */ | |
119 | ||
6cfd4191 | 120 | function Dep(value, maybefunc) { |
ac26861c MW |
121 | /* Initialize a new `Dep' object. |
122 | * | |
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'. | |
129 | * | |
130 | * Some properties can be fiddled with by client programs (rather than | |
131 | * trying to invent some crazy option-parsing protocol in the constructor). | |
132 | * | |
133 | * `name' A string name for this `Dep', used when printing. | |
134 | * | |
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. | |
138 | */ | |
139 | ||
140 | var val, func, f = F_CHANGED; | |
141 | var me = this; | |
142 | ||
143 | // Work out what's going on with our crazy argument convention. | |
144 | if (maybefunc !== undefined) { | |
145 | val = value; | |
146 | func = maybefunc; | |
147 | f |= F_VALUE | F_QUEUED; | |
148 | } else if (typeof value === 'function') { | |
149 | val = BAD; | |
150 | func = value; | |
151 | f |= F_QUEUED; | |
152 | } else { | |
153 | val = value; | |
154 | func = null; | |
155 | f |= F_VALUE | F_DEPS; | |
156 | } | |
157 | ||
158 | // Initialize the various slots. | |
159 | this._value_function = func; // Recomputation function. | |
160 | this._value = val; // Current value. | |
161 | ||
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. | |
167 | ||
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. | |
176 | ||
177 | // If we have a recomputation function then exercise it. | |
178 | if (func !== null) { | |
179 | with_frozen(function () { | |
180 | PENDING.push(me); | |
181 | }); | |
182 | } | |
183 | } | |
184 | ||
6cfd4191 | 185 | DEP.Dep = Dep; |
ac26861c MW |
186 | Dep._seq = 0; // Next sequence number to allocate. |
187 | ||
188 | Dep.prototype = { | |
189 | ||
190 | toString: function () { | |
191 | /* Convert the receiver to a string. | |
192 | * | |
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. | |
196 | */ | |
197 | ||
198 | // Basic stuff. | |
199 | var s = '#{Dep'; | |
200 | var f = this._flags(); | |
201 | var v = this._value; | |
202 | ||
203 | // The dep's name. | |
204 | if (this.name !== null) s += ' "' + this.name + '"'; | |
205 | ||
206 | // Sequence number -- distinguishes the dep if nothing else will. | |
207 | s += ' #' + this._seq; | |
208 | ||
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(); | |
213 | ||
214 | // Various flags. | |
215 | if (!(f & F_DEPS)) s += ' :recompute-deps'; | |
216 | if (f & F_QUEUED) s += ' :queued'; | |
217 | if (f & F_CHANGED) s += ' :changed'; | |
218 | ||
219 | // Done. | |
220 | s += '}'; | |
221 | return s; | |
222 | }, | |
223 | ||
224 | _flags: function () { | |
225 | /* Return the receiver's flags. | |
226 | * | |
227 | * If the receiver isn't up-to-date then we synthesize the flags. | |
228 | */ | |
229 | ||
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; | |
233 | else return 0; | |
234 | }, | |
235 | ||
236 | _update: function (value) { | |
237 | /* Store VALUE as the receiver's value. | |
238 | * | |
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. | |
241 | */ | |
242 | ||
243 | if (value === BAD ? | |
244 | this._value === BAD : | |
245 | (this._value !== BAD && | |
246 | this.equivp(value, this._value))) | |
247 | return false; | |
248 | else { | |
249 | this._value = value; | |
250 | return true; | |
251 | } | |
252 | }, | |
253 | ||
254 | _new_value: function () { | |
255 | /* Run the `_value_function' of the receiver, returning the result. | |
256 | * | |
257 | * If a bad dep is read during this then return `BAD'. Other exceptions | |
258 | * are propagated in the usual way. | |
259 | */ | |
260 | ||
261 | var old = EVALUATING; | |
262 | var val, e; | |
263 | ||
264 | this._dependencies = { }; | |
265 | try { | |
266 | EVALUATING = this; | |
267 | try { | |
268 | return this._value_function(); | |
269 | } catch (e) { | |
270 | if (e === BAD) return BAD; | |
271 | else throw e; | |
272 | } | |
273 | } finally { | |
274 | EVALUATING = old; | |
275 | } | |
276 | }, | |
277 | ||
278 | _propagate: function () { | |
279 | /* Propagate a change in the receiver to dependents and listeners. */ | |
280 | ||
281 | var d, di, f; | |
282 | ||
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]; | |
288 | f = d._flags(); | |
289 | if (!(f & (F_QUEUED | F_DEPS))) { | |
290 | PENDING.push(d); | |
291 | d._generation = GENERATION; | |
292 | d.__flags = (f & ~F_VALUE) | F_QUEUED; | |
293 | } | |
294 | } | |
295 | ||
296 | // We no longer have any dependents. Maybe we'll acquire more when the | |
297 | // old dependents recompute themselves. | |
298 | this._dependents = { }; | |
299 | ||
300 | // Tell the listeners that something interesting happened. | |
301 | dolist(this._listeners, function (l) { l(); }); | |
302 | }, | |
303 | ||
304 | _recompute: function () { | |
305 | /* Recompute the receiver, propagating changes and so on. | |
306 | * | |
307 | * Return whether we actually needed to change anything. | |
308 | */ | |
309 | ||
310 | var queued = this.__flags & F_QUEUED; | |
311 | var e; | |
312 | var me = this; | |
313 | ||
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; | |
318 | me._propagate(); | |
319 | return true; | |
320 | } else { | |
321 | me.__flags = queued | F_VALUE | F_DEPS; | |
322 | return false; | |
323 | } | |
324 | }; | |
325 | ||
326 | // Try to recompute our value. If that doesn't work then mark us as bad | |
327 | // and propagate that. | |
328 | try { | |
329 | return update(this._new_value()); | |
330 | } catch (e) { | |
331 | update(BAD); | |
332 | throw e; | |
333 | } | |
334 | }, | |
335 | ||
336 | _force: function () { | |
337 | /* Make sure the receiver has a current value. | |
338 | * | |
339 | * Return true if the receiver's value has changed in this recomputation | |
340 | * phase. | |
341 | * | |
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. | |
346 | */ | |
347 | ||
348 | var f = this._flags(); | |
349 | var d, any = false; | |
350 | ||
351 | if (f & F_RECOMPUTING) throw CircularDependency; | |
352 | else if (f & F_VALUE) return f & F_CHANGED; | |
353 | else { | |
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; | |
358 | if (any) | |
359 | return this._recompute(); | |
360 | else { | |
361 | this.__flags = f; | |
362 | return false; | |
363 | } | |
364 | } | |
365 | }, | |
366 | ||
367 | value: function () { | |
368 | /* Fetch and return the receiver's current value. | |
369 | * | |
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. | |
373 | */ | |
374 | ||
375 | var val; | |
376 | ||
377 | if (state === 'recomputing') { | |
378 | if (EVALUATING) { | |
379 | this._dependents[EVALUATING._seq] = EVALUATING; | |
380 | EVALUATING._dependencies[this._seq] = this; | |
381 | } | |
382 | this._force(); | |
383 | } | |
384 | val = this._value; | |
385 | if (val === BAD) throw BAD; | |
386 | return val; | |
387 | }, | |
388 | ||
389 | set_value: function (value) { | |
390 | /* Set the receiver's value to VALUE, and propagate. */ | |
391 | ||
392 | var me = this; | |
393 | ||
394 | with_frozen(function () { | |
395 | if (me._update(value)) { | |
396 | me._generation = GENERATION; | |
397 | me.__flags = F_VALUE | F_CHANGED; | |
398 | me._propagate(); | |
399 | } | |
400 | }); | |
401 | }, | |
402 | ||
403 | make_bad: function () { | |
404 | /* Mark the receiver as being bad, and propagate. */ | |
405 | this.set_value(BAD); | |
406 | }, | |
407 | ||
408 | add_listener: function (func) { | |
409 | /* Add FUNC to the receiver's list of listeners. | |
410 | * | |
411 | * Listener functions are called without arguments, and any values | |
412 | * returned are ignored. | |
413 | */ | |
414 | ||
415 | this._listeners.push(func); | |
416 | }, | |
417 | ||
418 | goodp: function () { | |
419 | /* Return whether the receiver is good (i.e., not marked as bad). */ | |
420 | ||
421 | return this._value !== BAD; | |
422 | } | |
423 | }; | |
424 | ||
6cfd4191 | 425 | function orelse(thunk, errthunk) { |
ac26861c MW |
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. | |
428 | */ | |
429 | ||
430 | var e; | |
431 | try { return thunk(); } | |
432 | catch (e) { | |
433 | if (e === BAD) { return errthunk(); } | |
434 | else throw e; | |
435 | } | |
436 | } | |
6cfd4191 | 437 | DEP.orelse = orelse; |
ac26861c | 438 | |
6cfd4191 | 439 | function bad() { |
ac26861c MW |
440 | /* For use in a value-function: make the dep be bad. */ |
441 | throw BAD; | |
442 | } | |
6cfd4191 | 443 | DEP.bad = bad; |
ac26861c MW |
444 | |
445 | function recompute_pending() { | |
446 | /* Recompute any pending dependencies. | |
447 | * | |
448 | * The state is `recomputing' during this. | |
449 | */ | |
450 | ||
451 | var d, f; | |
452 | ||
453 | state = 'recomputing'; | |
454 | try { | |
455 | while (PENDING.length) { | |
456 | d = PENDING.shift(); | |
457 | f = d.__flags; | |
458 | d.__flags = f & ~F_QUEUED; | |
459 | if (!(f & F_VALUE)) | |
460 | d._recompute(); | |
461 | else if (!(f & F_DEPS)) { | |
462 | d.new_value(); | |
463 | d.__flags = f | F_DEPS; | |
464 | } | |
465 | } | |
466 | } finally { | |
467 | while (PENDING.length) { | |
468 | d = PENDING.shift(); | |
469 | d._value = BAD; | |
470 | } | |
471 | } | |
472 | } | |
473 | ||
6cfd4191 | 474 | function with_frozen(body, delay) { |
ac26861c MW |
475 | /* Call BODY with dependencies frozen. |
476 | * | |
477 | * If the BODY function changes any dep values (using D.set_value(...)) | |
478 | * then dependents won't be updated until the BODY completes. | |
479 | * | |
480 | * It's very | |
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 | |
483 | * exception. | |
484 | */ | |
485 | ||
486 | var op, val; | |
487 | var old_delayed, old_pending; | |
488 | ||
489 | switch (STATE) { | |
490 | case 'frozen': | |
491 | body(); | |
492 | break; | |
493 | case 'recomputing': | |
494 | if (!delay) throw BusyRecomputing; | |
495 | DELAYED.push(body); | |
496 | break; | |
497 | case 'ready': | |
498 | old_delayed = DELAYED; | |
499 | old_pending = PENDING; | |
500 | try { | |
501 | DELAYED = []; | |
502 | PENDING = []; | |
503 | GENERATION = new Generation('dep-generation'); | |
504 | val = body(); | |
505 | for (;;) { | |
506 | recompute_pending(); | |
507 | if (!DELAYED.length) break; | |
508 | op = DELAYED.shift(); | |
509 | op(); | |
510 | } | |
511 | } finally { | |
512 | DELAYED = old_delayed; | |
513 | PENDING = old_pending; | |
514 | } | |
515 | break; | |
516 | } | |
517 | } | |
6cfd4191 | 518 | DEP.with_frozen = with_frozen; |
ac26861c MW |
519 | |
520 | /*----- That's all, folks -------------------------------------------------*/ | |
6cfd4191 | 521 | })(); |