+/* -*-javascript-*-
+ *
+ * Dependency-based computation.
+ *
+ * (c) 2013 Mark Wooding
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+var DEP = { }; (function () { with (DEP) {
+
+/*----- Utility functions and classes -------------------------------------*/
+
+DEP.dolist = function (list, func) {
+ /* Apply FUNC to each element of LIST, discarding the results.
+ *
+ * JavaScript's looping iterates over indices rather than values, which is
+ * consistent with what you want from a mapping, but inconvenient for
+ * sequences.
+ */
+
+ var i;
+ for (i in list) func(list[i]);
+}
+
+function eql(x, y) {
+ /* A standard equality function, suitable for detecting changes to `Dep'
+ * objects. This may be needlessly sensitive for some cases, but at least
+ * that's slow rather than wrong.
+ */
+
+ return x === y;
+}
+
+/* A Tag is an object which is interesting only because of its identity, and
+ * that the set of Tags is basically determined by the static structure of
+ * the program.
+ */
+DEP.Tag = function (what) {
+ this.what = what;
+}
+Tag.prototype = {
+ toString: function () { return '#{Tag ' + this.what + '}'; }
+}
+
+/* A Generation is like a Tag, except that it's expected that a program will
+ * manufacture Generations repeatedly, and perhaps use them to determine
+ * whether an object is `up-to-date' in some sense.
+ */
+DEP.Generation = function (what) {
+ this.what = what;
+ this.seq = Generation._next++;
+}
+Generation.prototype = {
+ toString: function () {
+ return '#{Generation ' + this.what + ' #' + this.seq.toString() + '}';
+ }
+};
+Generation._next = 0;
+DEP.Generation = Generation;
+
+/*----- The system state --------------------------------------------------*/
+
+var GENERATION = new Generation('dep-generation');
+ // Current recomputation generation.
+
+var EVALUATING = null; // The dep being re-evaluated.
+var STATE = 'ready'; // The current state.
+
+/* Flags for Dep objects. */
+var F_VALUE = 1; // Value is up-to-date.
+var F_DEPS = 2; // Known as a dependent.
+var F_CHANGED = 4; // Changed in current phase.
+var F_RECOMPUTING = 8; // Currently being recomputed.
+var F_QUEUED = 16; // Queued for recomputation.
+
+var BAD = Tag('BAD') // Used for the value of `bad' deps.
+
+var DELAYED = []; // Actions delayed by `with_frozen'.
+var PENDING = []; // Deps awaiting recomputation.
+
+/*----- Exceptions --------------------------------------------------------*/
+
+DEP.CircularDependency = new Tag('CircularDependency');
+DEP.BusyRecomputing = new Tag('BusyRecomputing');
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* A `Dep' object maintains a value, either because it was provided
+ * explicitly by the programmer, or computed in terms of other `Dep' objects.
+ * In the latter case, its value will be recomputed if any of its
+ * dependencies change value.
+ *
+ * A `Dep' object may have listener functions attached to it. These
+ * functions will bw called when its value changes.
+ *
+ * A `Dep' may be `bad'. In this case, use of its value by a dependent
+ * causes that `Dep' to become bad in turn.
+ */
+
+DEP.Dep = function (value, maybefunc) {
+ /* Initialize a new `Dep' object.
+ *
+ * Handling of the arguments is a little fiddly. If two arguments are
+ * provided then the first is set as the value and the second as the
+ * recomputation function. Otherwise, the first argument is interpreted as
+ * the recomputation function if it has `function' type, or as an initial
+ * explicit value otherwise. To force a function to be interpreted as an
+ * initial value, pass a second argument of `null'.
+ *
+ * Some properties can be fiddled with by client programs (rather than
+ * trying to invent some crazy option-parsing protocol in the constructor).
+ *
+ * `name' A string name for this `Dep', used when printing.
+ *
+ * `equivp' A predicate for deciding whether two value assigned
+ * to this `Dep' are equivalent. Used to decide whether
+ * a change should be propagated.
+ */
+
+ var val, func, f = F_CHANGED;
+ var me = this;
+
+ // Work out what's going on with our crazy argument convention.
+ if (maybefunc !== undefined) {
+ val = value;
+ func = maybefunc;
+ f |= F_VALUE | F_QUEUED;
+ } else if (typeof value === 'function') {
+ val = BAD;
+ func = value;
+ f |= F_QUEUED;
+ } else {
+ val = value;
+ func = null;
+ f |= F_VALUE | F_DEPS;
+ }
+
+ // Initialize the various slots.
+ this._value_function = func; // Recomputation function.
+ this._value = val; // Current value.
+
+ this.name = undefined; // Name, for printing.
+ this.equivp = eql; // Equivalent-value predicate.
+ this.__flags = f; // Current flags.
+ this._generation = GENERATION; // Have we done this one already?.
+ this._listeners = []; // List of listener functions.
+
+ // We need to maintain the dependency graph. In order to prevent duplicate
+ // entries in the various sets, we use maps rather than lists, but this
+ // presents a problem with coming up with keys: JavaScript stringifies
+ // objects rather than using them as-is, which is obviously hopeless. So
+ // assign each `Dep' a unique sequence number and use that as the key.
+ this._seq = Dep._seq++; // For identifying this object.
+ this._dependents = { }; // Set of dependent objects.
+ this._dependencies = { }; // Set of objects we depend on.
+
+ // If we have a recomputation function then exercise it.
+ if (func !== null) {
+ with_frozen(function () {
+ PENDING.push(me);
+ });
+ }
+}
+
+Dep._seq = 0; // Next sequence number to allocate.
+
+Dep.prototype = {
+
+ toString: function () {
+ /* Convert the receiver to a string.
+ *
+ * The printed representation includes a number of bits of information
+ * which are probably meaningless to most readers but are handy for
+ * debugging this library if it's misbehaving.
+ */
+
+ // Basic stuff.
+ var s = '#{Dep';
+ var f = this._flags();
+ var v = this._value;
+
+ // The dep's name.
+ if (this.name !== null) s += ' "' + this.name + '"';
+
+ // Sequence number -- distinguishes the dep if nothing else will.
+ s += ' #' + this._seq;
+
+ // The value, or some kind of marker that it doesn't have one.
+ if (!(f & F_VALUE)) s += ' #{out-of-date}';
+ else if (v === BAD) s += ' #{bad}';
+ else s += ' ' + v.toString();
+
+ // Various flags.
+ if (!(f & F_DEPS)) s += ' :recompute-deps';
+ if (f & F_QUEUED) s += ' :queued';
+ if (f & F_CHANGED) s += ' :changed';
+
+ // Done.
+ s += '}';
+ return s;
+ },
+
+ _flags: function () {
+ /* Return the receiver's flags.
+ *
+ * If the receiver isn't up-to-date then we synthesize the flags.
+ */
+
+ if (this.state === 'ready') return F_VALUE | F_DEPS;
+ else if (this._generation === GENERATION) return this.__flags;
+ else if (this._value_function === null) return F_VALUE | F_DEPS;
+ else return 0;
+ },
+
+ _update: function (value) {
+ /* Store VALUE as the receiver's value.
+ *
+ * Return whether the value has changed as a result. This is a low-level
+ * function which doesn't handle propagation or anything like that.
+ */
+
+ if (value === BAD ?
+ this._value === BAD :
+ (this._value !== BAD &&
+ this.equivp(value, this._value)))
+ return false;
+ else {
+ this._value = value;
+ return true;
+ }
+ },
+
+ _new_value: function () {
+ /* Run the `_value_function' of the receiver, returning the result.
+ *
+ * If a bad dep is read during this then return `BAD'. Other exceptions
+ * are propagated in the usual way.
+ */
+
+ var old = EVALUATING;
+ var val, e;
+
+ this._dependencies = { };
+ try {
+ EVALUATING = this;
+ try {
+ return this._value_function();
+ } catch (e) {
+ if (e === BAD) return BAD;
+ else throw e;
+ }
+ } finally {
+ EVALUATING = old;
+ }
+ },
+
+ _propagate: function () {
+ /* Propagate a change in the receiver to dependents and listeners. */
+
+ var d, di, f;
+
+ // Iterate over each dependent, pushing each one onto the `PENDING'
+ // queue, bringing it into the current generation, and marking it as
+ // having no current value.
+ for (di in this._dependents) {
+ d = this._dependents[di];
+ f = d._flags();
+ if (!(f & (F_QUEUED | F_DEPS))) {
+ PENDING.push(d);
+ d._generation = GENERATION;
+ d.__flags = (f & ~F_VALUE) | F_QUEUED;
+ }
+ }
+
+ // We no longer have any dependents. Maybe we'll acquire more when the
+ // old dependents recompute themselves.
+ this._dependents = { };
+
+ // Tell the listeners that something interesting happened.
+ dolist(this._listeners, function (l) { l(); });
+ },
+
+ _recompute: function () {
+ /* Recompute the receiver, propagating changes and so on.
+ *
+ * Return whether we actually needed to change anything.
+ */
+
+ var queued = this.__flags & F_QUEUED;
+ var e;
+ var me = this;
+
+ // Update us with the given VALUE.
+ function update(value) {
+ if (me._update(value)) {
+ me.__flags = queued | F_VALUE | F_DEPS | F_CHANGED;
+ me._propagate();
+ return true;
+ } else {
+ me.__flags = queued | F_VALUE | F_DEPS;
+ return false;
+ }
+ };
+
+ // Try to recompute our value. If that doesn't work then mark us as bad
+ // and propagate that.
+ try {
+ return update(this._new_value());
+ } catch (e) {
+ update(BAD);
+ throw e;
+ }
+ },
+
+ _force: function () {
+ /* Make sure the receiver has a current value.
+ *
+ * Return true if the receiver's value has changed in this recomputation
+ * phase.
+ *
+ * If it already has a good value then just return. Otherwise mark it
+ * as recomputing (to trap circularities) and poke our dependencies to
+ * ensure that they're up-to-date. If they weren't, then we recompute
+ * our own value before returning.
+ */
+
+ var f = this._flags();
+ var d, any = false;
+
+ if (f & F_RECOMPUTING) throw CircularDependency;
+ else if (f & F_VALUE) return f & F_CHANGED;
+ else {
+ this._generation = GENERATION;
+ this.__flags = (f & ~F_QUEUED) | F_RECOMPUTING;
+ for (d in this._dependencies)
+ if (this._dependencies[d]._force()) any = true;
+ if (any)
+ return this._recompute();
+ else {
+ this.__flags = f;
+ return false;
+ }
+ }
+ },
+
+ value: function () {
+ /* Fetch and return the receiver's current value.
+ *
+ * If the receiver is bad then an exception is thrown. This exception
+ * can be caught using `orelse'; a dep recomputation function can let the
+ * exception propagate, and be marked as bad in turn.
+ */
+
+ var val;
+
+ if (state === 'recomputing') {
+ if (EVALUATING) {
+ this._dependents[EVALUATING._seq] = EVALUATING;
+ EVALUATING._dependencies[this._seq] = this;
+ }
+ this._force();
+ }
+ val = this._value;
+ if (val === BAD) throw BAD;
+ return val;
+ },
+
+ set_value: function (value) {
+ /* Set the receiver's value to VALUE, and propagate. */
+
+ var me = this;
+
+ with_frozen(function () {
+ if (me._update(value)) {
+ me._generation = GENERATION;
+ me.__flags = F_VALUE | F_CHANGED;
+ me._propagate();
+ }
+ });
+ },
+
+ make_bad: function () {
+ /* Mark the receiver as being bad, and propagate. */
+ this.set_value(BAD);
+ },
+
+ add_listener: function (func) {
+ /* Add FUNC to the receiver's list of listeners.
+ *
+ * Listener functions are called without arguments, and any values
+ * returned are ignored.
+ */
+
+ this._listeners.push(func);
+ },
+
+ goodp: function () {
+ /* Return whether the receiver is good (i.e., not marked as bad). */
+
+ return this._value !== BAD;
+ }
+};
+
+DEP.orelse = function (thunk, errthunk) {
+ /* Call THUNK. If it succeeds, then return its result. If THUNK
+ * reads a bad dep then call ERRTHINK and return its result instead.
+ */
+
+ var e;
+ try { return thunk(); }
+ catch (e) {
+ if (e === BAD) { return errthunk(); }
+ else throw e;
+ }
+}
+
+DEP.bad = function () {
+ /* For use in a value-function: make the dep be bad. */
+ throw BAD;
+}
+
+function recompute_pending() {
+ /* Recompute any pending dependencies.
+ *
+ * The state is `recomputing' during this.
+ */
+
+ var d, f;
+
+ state = 'recomputing';
+ try {
+ while (PENDING.length) {
+ d = PENDING.shift();
+ f = d.__flags;
+ d.__flags = f & ~F_QUEUED;
+ if (!(f & F_VALUE))
+ d._recompute();
+ else if (!(f & F_DEPS)) {
+ d.new_value();
+ d.__flags = f | F_DEPS;
+ }
+ }
+ } finally {
+ while (PENDING.length) {
+ d = PENDING.shift();
+ d._value = BAD;
+ }
+ }
+}
+
+DEP.with_frozen = function (body, delay) {
+ /* Call BODY with dependencies frozen.
+ *
+ * If the BODY function changes any dep values (using D.set_value(...))
+ * then dependents won't be updated until the BODY completes.
+ *
+ * It's very
+ * bad to do this during a recomputation phase. If DELAY is true, then the
+ * BODY is delayed until the recomputation completes; otherwise you get an
+ * exception.
+ */
+
+ var op, val;
+ var old_delayed, old_pending;
+
+ switch (STATE) {
+ case 'frozen':
+ body();
+ break;
+ case 'recomputing':
+ if (!delay) throw BusyRecomputing;
+ DELAYED.push(body);
+ break;
+ case 'ready':
+ old_delayed = DELAYED;
+ old_pending = PENDING;
+ try {
+ DELAYED = [];
+ PENDING = [];
+ GENERATION = new Generation('dep-generation');
+ val = body();
+ for (;;) {
+ recompute_pending();
+ if (!DELAYED.length) break;
+ op = DELAYED.shift();
+ op();
+ }
+ } finally {
+ DELAYED = old_delayed;
+ PENDING = old_pending;
+ }
+ break;
+ }
+}
+
+/*----- That's all, folks -------------------------------------------------*/
+} })();