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 | ||
24 | var DEP = { }; (function () { with (DEP) { | |
25 | ||
26 | /*----- Utility functions and classes -------------------------------------*/ | |
27 | ||
28 | DEP.dolist = function (list, func) { | |
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 | } | |
39 | ||
40 | function eql(x, y) { | |
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. | |
44 | */ | |
45 | ||
46 | return x === y; | |
47 | } | |
48 | ||
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 | |
51 | * the program. | |
52 | */ | |
53 | DEP.Tag = function (what) { | |
54 | this.what = what; | |
55 | } | |
56 | Tag.prototype = { | |
57 | toString: function () { return '#{Tag ' + this.what + '}'; } | |
58 | } | |
59 | ||
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. | |
63 | */ | |
64 | DEP.Generation = function (what) { | |
65 | this.what = what; | |
66 | this.seq = Generation._next++; | |
67 | } | |
68 | Generation.prototype = { | |
69 | toString: function () { | |
70 | return '#{Generation ' + this.what + ' #' + this.seq.toString() + '}'; | |
71 | } | |
72 | }; | |
73 | Generation._next = 0; | |
74 | DEP.Generation = Generation; | |
75 | ||
76 | /*----- The system state --------------------------------------------------*/ | |
77 | ||
78 | var GENERATION = new Generation('dep-generation'); | |
79 | // Current recomputation generation. | |
80 | ||
81 | var EVALUATING = null; // The dep being re-evaluated. | |
82 | var STATE = 'ready'; // The current state. | |
83 | ||
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. | |
90 | ||
91 | var BAD = Tag('BAD') // Used for the value of `bad' deps. | |
92 | ||
93 | var DELAYED = []; // Actions delayed by `with_frozen'. | |
94 | var PENDING = []; // Deps awaiting recomputation. | |
95 | ||
96 | /*----- Exceptions --------------------------------------------------------*/ | |
97 | ||
98 | DEP.CircularDependency = new Tag('CircularDependency'); | |
99 | DEP.BusyRecomputing = new Tag('BusyRecomputing'); | |
100 | ||
101 | /*----- Main code ---------------------------------------------------------*/ | |
102 | ||
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. | |
107 | * | |
108 | * A `Dep' object may have listener functions attached to it. These | |
109 | * functions will bw called when its value changes. | |
110 | * | |
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. | |
113 | */ | |
114 | ||
115 | DEP.Dep = function (value, maybefunc) { | |
116 | /* Initialize a new `Dep' object. | |
117 | * | |
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'. | |
124 | * | |
125 | * Some properties can be fiddled with by client programs (rather than | |
126 | * trying to invent some crazy option-parsing protocol in the constructor). | |
127 | * | |
128 | * `name' A string name for this `Dep', used when printing. | |
129 | * | |
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. | |
133 | */ | |
134 | ||
135 | var val, func, f = F_CHANGED; | |
136 | var me = this; | |
137 | ||
138 | // Work out what's going on with our crazy argument convention. | |
139 | if (maybefunc !== undefined) { | |
140 | val = value; | |
141 | func = maybefunc; | |
142 | f |= F_VALUE | F_QUEUED; | |
143 | } else if (typeof value === 'function') { | |
144 | val = BAD; | |
145 | func = value; | |
146 | f |= F_QUEUED; | |
147 | } else { | |
148 | val = value; | |
149 | func = null; | |
150 | f |= F_VALUE | F_DEPS; | |
151 | } | |
152 | ||
153 | // Initialize the various slots. | |
154 | this._value_function = func; // Recomputation function. | |
155 | this._value = val; // Current value. | |
156 | ||
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. | |
162 | ||
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. | |
171 | ||
172 | // If we have a recomputation function then exercise it. | |
173 | if (func !== null) { | |
174 | with_frozen(function () { | |
175 | PENDING.push(me); | |
176 | }); | |
177 | } | |
178 | } | |
179 | ||
180 | Dep._seq = 0; // Next sequence number to allocate. | |
181 | ||
182 | Dep.prototype = { | |
183 | ||
184 | toString: function () { | |
185 | /* Convert the receiver to a string. | |
186 | * | |
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. | |
190 | */ | |
191 | ||
192 | // Basic stuff. | |
193 | var s = '#{Dep'; | |
194 | var f = this._flags(); | |
195 | var v = this._value; | |
196 | ||
197 | // The dep's name. | |
198 | if (this.name !== null) s += ' "' + this.name + '"'; | |
199 | ||
200 | // Sequence number -- distinguishes the dep if nothing else will. | |
201 | s += ' #' + this._seq; | |
202 | ||
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(); | |
207 | ||
208 | // Various flags. | |
209 | if (!(f & F_DEPS)) s += ' :recompute-deps'; | |
210 | if (f & F_QUEUED) s += ' :queued'; | |
211 | if (f & F_CHANGED) s += ' :changed'; | |
212 | ||
213 | // Done. | |
214 | s += '}'; | |
215 | return s; | |
216 | }, | |
217 | ||
218 | _flags: function () { | |
219 | /* Return the receiver's flags. | |
220 | * | |
221 | * If the receiver isn't up-to-date then we synthesize the flags. | |
222 | */ | |
223 | ||
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; | |
227 | else return 0; | |
228 | }, | |
229 | ||
230 | _update: function (value) { | |
231 | /* Store VALUE as the receiver's value. | |
232 | * | |
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. | |
235 | */ | |
236 | ||
237 | if (value === BAD ? | |
238 | this._value === BAD : | |
239 | (this._value !== BAD && | |
240 | this.equivp(value, this._value))) | |
241 | return false; | |
242 | else { | |
243 | this._value = value; | |
244 | return true; | |
245 | } | |
246 | }, | |
247 | ||
248 | _new_value: function () { | |
249 | /* Run the `_value_function' of the receiver, returning the result. | |
250 | * | |
251 | * If a bad dep is read during this then return `BAD'. Other exceptions | |
252 | * are propagated in the usual way. | |
253 | */ | |
254 | ||
255 | var old = EVALUATING; | |
256 | var val, e; | |
257 | ||
258 | this._dependencies = { }; | |
259 | try { | |
260 | EVALUATING = this; | |
261 | try { | |
262 | return this._value_function(); | |
263 | } catch (e) { | |
264 | if (e === BAD) return BAD; | |
265 | else throw e; | |
266 | } | |
267 | } finally { | |
268 | EVALUATING = old; | |
269 | } | |
270 | }, | |
271 | ||
272 | _propagate: function () { | |
273 | /* Propagate a change in the receiver to dependents and listeners. */ | |
274 | ||
275 | var d, di, f; | |
276 | ||
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]; | |
282 | f = d._flags(); | |
283 | if (!(f & (F_QUEUED | F_DEPS))) { | |
284 | PENDING.push(d); | |
285 | d._generation = GENERATION; | |
286 | d.__flags = (f & ~F_VALUE) | F_QUEUED; | |
287 | } | |
288 | } | |
289 | ||
290 | // We no longer have any dependents. Maybe we'll acquire more when the | |
291 | // old dependents recompute themselves. | |
292 | this._dependents = { }; | |
293 | ||
294 | // Tell the listeners that something interesting happened. | |
295 | dolist(this._listeners, function (l) { l(); }); | |
296 | }, | |
297 | ||
298 | _recompute: function () { | |
299 | /* Recompute the receiver, propagating changes and so on. | |
300 | * | |
301 | * Return whether we actually needed to change anything. | |
302 | */ | |
303 | ||
304 | var queued = this.__flags & F_QUEUED; | |
305 | var e; | |
306 | var me = this; | |
307 | ||
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; | |
312 | me._propagate(); | |
313 | return true; | |
314 | } else { | |
315 | me.__flags = queued | F_VALUE | F_DEPS; | |
316 | return false; | |
317 | } | |
318 | }; | |
319 | ||
320 | // Try to recompute our value. If that doesn't work then mark us as bad | |
321 | // and propagate that. | |
322 | try { | |
323 | return update(this._new_value()); | |
324 | } catch (e) { | |
325 | update(BAD); | |
326 | throw e; | |
327 | } | |
328 | }, | |
329 | ||
330 | _force: function () { | |
331 | /* Make sure the receiver has a current value. | |
332 | * | |
333 | * Return true if the receiver's value has changed in this recomputation | |
334 | * phase. | |
335 | * | |
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. | |
340 | */ | |
341 | ||
342 | var f = this._flags(); | |
343 | var d, any = false; | |
344 | ||
345 | if (f & F_RECOMPUTING) throw CircularDependency; | |
346 | else if (f & F_VALUE) return f & F_CHANGED; | |
347 | else { | |
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; | |
352 | if (any) | |
353 | return this._recompute(); | |
354 | else { | |
355 | this.__flags = f; | |
356 | return false; | |
357 | } | |
358 | } | |
359 | }, | |
360 | ||
361 | value: function () { | |
362 | /* Fetch and return the receiver's current value. | |
363 | * | |
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. | |
367 | */ | |
368 | ||
369 | var val; | |
370 | ||
371 | if (state === 'recomputing') { | |
372 | if (EVALUATING) { | |
373 | this._dependents[EVALUATING._seq] = EVALUATING; | |
374 | EVALUATING._dependencies[this._seq] = this; | |
375 | } | |
376 | this._force(); | |
377 | } | |
378 | val = this._value; | |
379 | if (val === BAD) throw BAD; | |
380 | return val; | |
381 | }, | |
382 | ||
383 | set_value: function (value) { | |
384 | /* Set the receiver's value to VALUE, and propagate. */ | |
385 | ||
386 | var me = this; | |
387 | ||
388 | with_frozen(function () { | |
389 | if (me._update(value)) { | |
390 | me._generation = GENERATION; | |
391 | me.__flags = F_VALUE | F_CHANGED; | |
392 | me._propagate(); | |
393 | } | |
394 | }); | |
395 | }, | |
396 | ||
397 | make_bad: function () { | |
398 | /* Mark the receiver as being bad, and propagate. */ | |
399 | this.set_value(BAD); | |
400 | }, | |
401 | ||
402 | add_listener: function (func) { | |
403 | /* Add FUNC to the receiver's list of listeners. | |
404 | * | |
405 | * Listener functions are called without arguments, and any values | |
406 | * returned are ignored. | |
407 | */ | |
408 | ||
409 | this._listeners.push(func); | |
410 | }, | |
411 | ||
412 | goodp: function () { | |
413 | /* Return whether the receiver is good (i.e., not marked as bad). */ | |
414 | ||
415 | return this._value !== BAD; | |
416 | } | |
417 | }; | |
418 | ||
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. | |
422 | */ | |
423 | ||
424 | var e; | |
425 | try { return thunk(); } | |
426 | catch (e) { | |
427 | if (e === BAD) { return errthunk(); } | |
428 | else throw e; | |
429 | } | |
430 | } | |
431 | ||
432 | DEP.bad = function () { | |
433 | /* For use in a value-function: make the dep be bad. */ | |
434 | throw BAD; | |
435 | } | |
436 | ||
437 | function recompute_pending() { | |
438 | /* Recompute any pending dependencies. | |
439 | * | |
440 | * The state is `recomputing' during this. | |
441 | */ | |
442 | ||
443 | var d, f; | |
444 | ||
445 | state = 'recomputing'; | |
446 | try { | |
447 | while (PENDING.length) { | |
448 | d = PENDING.shift(); | |
449 | f = d.__flags; | |
450 | d.__flags = f & ~F_QUEUED; | |
451 | if (!(f & F_VALUE)) | |
452 | d._recompute(); | |
453 | else if (!(f & F_DEPS)) { | |
454 | d.new_value(); | |
455 | d.__flags = f | F_DEPS; | |
456 | } | |
457 | } | |
458 | } finally { | |
459 | while (PENDING.length) { | |
460 | d = PENDING.shift(); | |
461 | d._value = BAD; | |
462 | } | |
463 | } | |
464 | } | |
465 | ||
466 | DEP.with_frozen = function (body, delay) { | |
467 | /* Call BODY with dependencies frozen. | |
468 | * | |
469 | * If the BODY function changes any dep values (using D.set_value(...)) | |
470 | * then dependents won't be updated until the BODY completes. | |
471 | * | |
472 | * It's very | |
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 | |
475 | * exception. | |
476 | */ | |
477 | ||
478 | var op, val; | |
479 | var old_delayed, old_pending; | |
480 | ||
481 | switch (STATE) { | |
482 | case 'frozen': | |
483 | body(); | |
484 | break; | |
485 | case 'recomputing': | |
486 | if (!delay) throw BusyRecomputing; | |
487 | DELAYED.push(body); | |
488 | break; | |
489 | case 'ready': | |
490 | old_delayed = DELAYED; | |
491 | old_pending = PENDING; | |
492 | try { | |
493 | DELAYED = []; | |
494 | PENDING = []; | |
495 | GENERATION = new Generation('dep-generation'); | |
496 | val = body(); | |
497 | for (;;) { | |
498 | recompute_pending(); | |
499 | if (!DELAYED.length) break; | |
500 | op = DELAYED.shift(); | |
501 | op(); | |
502 | } | |
503 | } finally { | |
504 | DELAYED = old_delayed; | |
505 | PENDING = old_pending; | |
506 | } | |
507 | break; | |
508 | } | |
509 | } | |
510 | ||
511 | /*----- That's all, folks -------------------------------------------------*/ | |
512 | } })(); |