X-Git-Url: https://git.distorted.org.uk/~mdw/tripe-android/blobdiff_plain/9190adc66f814b8b9add2d2df2ff65b43175104b..0157de026e802e94a2d0db0421b02ffca986c616:/dep.scala

diff --git a/dep.scala b/dep.scala
new file mode 100644
index 0000000..d94925d
--- /dev/null
+++ b/dep.scala
@@ -0,0 +1,428 @@
+/* -*-scala-*-
+ *
+ * Dependency-based computation
+ *
+ * (c) 2018 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of the Trivial IP Encryption (TrIPE) Android app.
+ *
+ * TrIPE 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 3 of the License, or (at your
+ * option) any later version.
+ *
+ * TrIPE 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 General Public License
+ * for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with TrIPE.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+package uk.org.distorted.tripe; package object dep {
+
+/*----- Imports -----------------------------------------------------------*/
+
+import scala.collection.mutable.{ArrayBuffer, Queue};
+
+import java.lang.ref.WeakReference;
+
+import Implicits.{truish, bitwiseImplicits};
+
+/*----- Main code ---------------------------------------------------------*/
+
+object Generation {
+  private var nextseq: Int = 0;
+}
+class Generation(what: String) extends Brand(what) {
+  /* Formally, a generation marker has no interesting properties except for
+   * its identity, so we could just as well use a plain `Brand'.  For
+   * diagnostic purposes though, we include a sequence number which we can
+   * include in the object printout.
+   */
+
+  import Generation._;
+  private val seq =
+    Generation synchronized { val v = nextseq; nextseq += 1; v };
+  override def toString(): String = s"${getClass.getName}($what, #$seq)";
+}
+
+class BadDep extends Throwable;
+  /* Thrown when you try to read a `bad' `Dep' object. */
+
+class CircularDependency extends Exception;
+  /* Thrown if a `Dep' depends on itself, possibly indirectly. */
+
+/* Some type aliases because otherwise we need to mess with existential
+ * types.
+ */
+type AbstractDep = Dep[_];
+type AbstractComputedDep = ComputedDep[_];
+
+object Dep {
+
+  /* Event types for hook clients. */
+  sealed abstract class Event;
+  case object Changed extends Event;
+
+  /* Flags for `Dep' objects. */
+  private[dep] final val F_VALUE = 1;	// has a value
+  private[dep] final val F_DEPS = 2;	// dependencies are know
+  private[dep] final val F_CHANGED = 4;	// changed in this update cycle
+  private[dep] final val F_RECOMPUTING = 8; // currently recomputing
+  private[dep] final val F_QUEUED = 16;	// queued for recomputation
+
+  /* Overall system state. */
+  object DepState extends Enumeration
+    { val READY, FROZEN, RECOMPUTING = Value; }
+  import DepState.{READY, FROZEN, RECOMPUTING, Value => State};
+
+  private[dep] var generation: Generation = new Generation("dep-generation");
+    /* The current generation.   Updated in `withDepsFrozen'. */
+
+  private[dep] val state = new SharedFluid(READY);
+    /* The current system state.  Must be `let'-bound. */
+
+  private[dep] val evaluating = new SharedFluid[AbstractComputedDep](null);
+    /* The `ComputedDep' object which is being evaluated, or null.  Must be
+     * `let'-bound.
+     */
+
+  private[dep] val delayed = new SharedFluid[Queue[() => Unit]](null);
+    /* Delayed thunks from `withDepsDelayed'.  Must be `let'-bound to a fresh
+     * `Queue', and then mutated in place.
+     */
+
+  private[dep] val pending =
+    new SharedFluid[Queue[AbstractComputedDep]](null);
+    /* `ComputedDep' objects awaiting recomputation.  Must be `let'-bound to
+     * a fresh `Queue', and then mutated in place.
+     */
+
+  private def recomputePending() {
+    /* Recalculate the deps on the `pending' queue.
+     *
+     * While this is running, we are in the `RECOMPUTING' state.
+     */
+
+    let(state -> RECOMPUTING) {
+      try {
+	while (pending.v) {
+	  val d = pending.v.dequeue();
+	  val f = d._flags;
+	  d._flags = f&~F_QUEUED;
+	  if (!(f&F_VALUE)) d.recompute();
+	  else if (!(f&F_DEPS)) { d.recompute(); d.flags = f | F_DEPS; }
+	}
+      } finally {
+	while (pending.v) pending.v.dequeue()._val = None;
+      }
+    }
+  }
+
+  def withDepsFrozen[T](body: => T): T = state.v match {
+    /* Evaluate the BODY, allowing it to modify `Dep' objects.  When the BODY
+     * completes, but not before, all dependent `Dep's are recalculated.
+     * This can be used to improve performance if a big batch of changes is
+     * planned.
+     *
+     * It's not permitted to modify a `Dep' while recomputation is in
+     * progress.  See `withDepsDelayed'.
+     */
+
+    case FROZEN => body
+    case RECOMPUTING =>
+      throw new IllegalStateException("currently recomputing");
+    case READY =>
+      let(state -> FROZEN,
+	  delayed -> new Queue[() => Unit],
+	  pending -> new Queue[AbstractComputedDep]) {
+	generation = new Generation("dep-generation");
+	val r = body;
+	while ({ recomputePending(); delayed.v }) delayed.v.dequeue()();
+	r
+      }
+    }
+
+  def withDepsDelayed(body: => Unit) { state.v match {
+    /* Evaluate the BODY, allowing it to modify `Dep' objects.  If
+     * recomputation is in progress, then save the BODY in a queue to be
+     * evaluated later.
+     */
+
+    case RECOMPUTING => delayed.v += { () => body };
+    case _ => withDepsFrozen { body };
+  } }
+
+  /* Various constructures for basic `Dep' objects. */
+  def apply[T: Equiv](name: String, init: T): Dep[T] =
+    new Dep(name, Some(init));
+  def apply[T: Equiv](name: String): Dep[T] = new Dep(name, None);
+  def apply[T: Equiv](init: T): Dep[T] = new Dep(null, Some(init));
+  def apply[T: Equiv](): Dep[T] = new Dep(null, None);
+}
+
+/* Import these things here so that they're included in the scope of `Dep''s
+ * additional constructor bodies.
+ */
+import Dep._;
+
+/* tryDep { BODY } ifBad { ALT }
+ *
+ * Evaluate BODY.  If it tries to read a bad `Dep', then evaluate ALT
+ * instead.
+ */
+class PendingAttempt[T] private[dep](body: => T)
+  { def ifBad(alt: => T): T = try { body } catch { case _: BadDep => alt } }
+def tryDep[T](body: => T): PendingAttempt[T] = new PendingAttempt(body);
+
+def bad: Nothing = throw new BadDep;
+  /* Call from a `Dep' expression to cause the `Dep' to be marked bad. */
+
+class Dep[T: Equiv] protected(val name: String,
+			      var _val: Option[T],
+			      var _flags: Int)
+	extends Hook[Dep.Event]
+{
+  /* A leaf `Dep'.
+   *
+   * A `Dep' has a value, of some type T, and maybe a name.  The value is
+   * available in the `v' property.  A `Dep' may be `bad', in which case an
+   * exception, `BadDep', is thrown when an attempt is made to read its
+   * value; this can be hedged against either by calling `goodp' in advance,
+   * or by using the `tryDep' function.
+   *
+   * The value of a leaf `Dep' changes only as a result of direct assignments
+   * to its `v' property.
+   */
+
+  /* Internal constructor, for the benefit of the companion module. */
+  private def this(name: String, init: Option[T])
+    { this(name, init, F_CHANGED | F_VALUE); }
+
+  /* Other useful definitions. */
+  import DepState.{READY, FROZEN, RECOMPUTING, Value => State};
+
+  protected var gen: Generation = generation;
+    /* The generation during which this `Dep' was most recently updated. */
+
+  protected val dependents =
+    new ArrayBuffer[WeakReference[AbstractComputedDep]];
+    /* A collection of other `Dep's which depend (directly) on this one. */
+
+  override def toString(): String = {
+    /* Convert this `Dep' to a string.  The contents are useful only for
+     * diagnostic purposes.
+     */
+
+    val b = new StringBuilder;
+    val f = flags;
+
+    b ++= f"${getClass.getName}%s@${hashCode}%x(";
+
+    b ++= (_val match {
+      case _ if !(f&F_VALUE) => "<out-of-date>"
+      case None => "<bad>"
+      case Some(x) => x.toString
+    })
+
+    if (name != null) b ++= s" $name";
+
+    if (f&F_DEPS) b ++= " :recompute-deps";
+    if (f&F_QUEUED) b ++= " :queued";
+    if (f&F_CHANGED) b ++= " :changed";
+
+    b += ')'; b.result
+  }
+
+  /* A property for accessing the `Dep' flags.
+   *
+   * The flags stored are only relevant during recomputation and if they're
+   * fresh.  Otherwise we must synthesize appropriate flags.
+   */
+  protected[dep] def flags: Int =
+    if (state.v == READY || gen != generation) F_VALUE | F_DEPS
+    else _flags;
+  protected[dep] def flags_=(f: Int) { _flags = f; }
+
+  def update(v: Option[T]): Boolean = (v, _val) match {
+    /* Set this `Dep''s value to V; return true if this is a substantive
+     * change.
+     */
+    case (Some(x), Some(y)) if implicitly[Equiv[T]].equiv(x, y) => false
+    case _ => _val = v; true
+  }
+
+  protected def propagate() {
+    /* Notify all of our dependents that this `Dep' has changed its value. */
+    for {
+      dweak <- dependents;
+      d = dweak.get;
+      if d != null;
+      f = d.flags;
+      if !(f&(F_QUEUED | F_DEPS))
+    } {
+      pending.v += d;
+      d.flags = (f&F_VALUE) | F_QUEUED;
+    }
+    dependents.clear();
+    callHook(Changed);
+  }
+
+  private[dep] def force(): Boolean = flags&F_CHANGED;
+    /* Force this `Dep' to update its value if it hasn't done so already in
+     * the current recomputation cycle.  Return true if its value has changed
+     * in the current cycle.
+     *
+     * The implementation here is trivial, but subclasses will need to
+     * override it.
+     */
+
+  def v: T = {
+    /* Return the value of this `Dep', recalculating it if necessary.
+     *
+     * Throws `BadDep' if the `Dep is bad.
+     */
+
+    if (state.v == RECOMPUTING) {
+      if (evaluating.v != null) {
+	dependents += evaluating.v.weakref;
+	evaluating.v.dependencies += this;
+      }
+      force();
+    }
+    _val match {
+      case None => bad
+      case Some(v) => v
+    }
+  }
+
+  /* The obvious good/bad predicates. */
+  def goodp: Boolean = { if (state.v == RECOMPUTING) force(); _val != bad }
+  def badp: Boolean = { if (state.v == RECOMPUTING) force(); _val == bad }
+
+  private def set(v: Option[T]) {
+    /* Low-level operation to change the value of this `Dep', and trigger
+     * recomputation as necessary.
+     */
+
+    withDepsFrozen {
+      update(v);
+      gen = generation;
+      _flags = F_VALUE | F_CHANGED;
+      propagate();
+    }
+  }
+
+  /* Modify the `Dep' value. */
+  def v_=(x: T) { set(Some(x)); }
+  def makeBad() { set(None); }
+}
+
+object ComputedDep {
+
+  /* Cooked constructors. */
+  def apply[T: Equiv](expr: => T) = new ComputedDep(null, expr, None);
+  def apply[T: Equiv](name: String)(expr: => T) =
+    new ComputedDep(name, expr, None);
+  def apply[T: Equiv](init: T)(expr: => T) =
+    new ComputedDep(null, expr, Some(init));
+  def apply[T: Equiv](name: String, init: T)(expr: => T) =
+    new ComputedDep(name, expr, Some(init));
+}
+
+class ComputedDep[T: Equiv] protected(name: String,
+				      expr: => T,
+				      init: Option[T])
+	extends Dep[T](name, init,
+		       F_CHANGED | F_QUEUED | F_DEPS | (init match {
+			 case Some(_) => F_VALUE
+			 case None => 0
+		       }))
+{
+  /* A `Dep' which calculates its value based on other `Dep' objects.
+   *
+   * During this calculation, we keep track of the dependency structure so
+   * that, in the future, we can determine whether this `Dep' needs to be
+   * recalculated as a result of other changes.
+   */
+
+  private[dep] val dependencies = new ArrayBuffer[AbstractDep];
+    /* A collection of other `Dep' objects; if any of them change, we must
+     * recalculate.
+     */
+
+  private[dep] val weakref: WeakReference[AbstractComputedDep] =
+    new WeakReference(this);
+    /* A weak reference to this `Dep'.
+     *
+     * A `Dep' maintains only weak references to those other `Dep's which
+     * depend on it: just because X's value is determined (partially) by Y
+     * doesn't mean that we should keep X alive just because Y is alive.
+     *
+     * The weak reference is captured once to reduce consing.
+     */
+
+  /* Arrange recalculation at the earliest opportunity. */
+  withDepsFrozen { pending.v += this; }
+
+  /* Other useful definitions. */
+  import DepState.{READY, FROZEN, RECOMPUTING, Value => State};
+
+  /* Synthesize different flags when we aren't fresh. */
+  override protected[dep] def flags: Int =
+    if (state.v == READY) F_VALUE | F_DEPS
+    else if (gen == generation) _flags
+    else 0;
+
+  def newValue(): Option[T] = {
+    /* Determine the new value of this `Dep', keeping track of other `Dep'
+     * objects which we look at.
+     */
+
+    try { let(evaluating -> this) { dependencies.clear(); Some(expr)} }
+    catch { case _: BadDep => None }
+  }
+
+  private[this] def _recompute(v: Option[T], nf: Int): Boolean =
+    if (update(v)) { flags = nf | Dep.F_CHANGED; propagate(); true }
+    else { flags = nf; false }
+
+  private[dep] def recompute(): Boolean = {
+    /* Recalculate the value of this `Dep'.  Catch exceptions and mark the
+     * `Dep' as bad if it encounters any.
+     *
+     * Note that the special case of `BadDep' is trapped lower down in
+     * `newValue'.
+     */
+
+    val nf = (flags&F_QUEUED) | F_VALUE | F_DEPS;
+    try { _recompute(newValue(), nf) }
+    catch { case e: Exception => _recompute(None, nf); throw e; }
+  }
+
+  private[dep] override def force(): Boolean = {
+    /* Force this `Dep' to update its value if it hasn't done so already in
+     * the current recomputation cycle.  Return true if its value has changed
+     * in the current cycle.
+     */
+
+    val f = flags;
+    if (f&F_RECOMPUTING) throw new CircularDependency;
+    else if (f&F_VALUE) f&F_CHANGED
+    else {
+      gen = generation;
+      flags = (f&F_QUEUED) | F_RECOMPUTING;
+      if (dependencies.exists { _.force() }) recompute();
+      else { flags = f; false }
+    }
+  }
+}
+
+/*----- That's all, folks -------------------------------------------------*/
+
+}