[dep-ui] / dep.js

/* -*-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 () {

/*----- Utility functions and classes -------------------------------------*/

function dolist(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]);
}
DEP.dolist = dolist;

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.
 */
function Tag(what) {
  this.what = what;
}
Tag.prototype = {
  toString: function () { return '#{Tag ' + this.what + '}'; }
}
DEP.Tag = Tag;

/* 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.
 */
function Generation(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 --------------------------------------------------------*/

CircularDependency = new Tag('CircularDependency');
DEP.CircularDependency = CircularDependency;

BusyRecomputing = new Tag('BusyRecomputing');
DEP.BusyRecomputing = 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.
 */

function Dep(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.Dep = Dep;
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;
  }
};

function orelse(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.orelse = orelse;

function bad() {
  /* For use in a value-function: make the dep be bad. */
  throw BAD;
}
DEP.bad = 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;
    }
  }
}

function with_frozen(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;
  }
}
DEP.with_frozen = with_frozen;

/*----- That's all, folks -------------------------------------------------*/
})();