--- /dev/null
+/* -*-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 -------------------------------------------------*/
+
+}
~mdw / tripe-android / blobdiff