3 * Dependency-based computation
5 * (c) 2018 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of the Trivial IP Encryption (TrIPE) Android app.
12 * TrIPE is free software: you can redistribute it and/or modify it under
13 * the terms of the GNU General Public License as published by the Free
14 * Software Foundation; either version 3 of the License, or (at your
15 * option) any later version.
17 * TrIPE is distributed in the hope that it will be useful, but WITHOUT
18 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
19 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
22 * You should have received a copy of the GNU General Public License
23 * along with TrIPE. If not, see <https://www.gnu.org/licenses/>.
26 package uk.org.distorted.tripe; package object dep {
28 /*----- Imports -----------------------------------------------------------*/
30 import scala.collection.mutable.{ArrayBuffer, Queue};
32 import java.lang.ref.WeakReference;
34 import Implicits.{truish, bitwiseImplicits};
36 /*----- Main code ---------------------------------------------------------*/
39 private var nextseq: Int = 0;
41 class Generation(what: String) extends Brand(what) {
42 /* Formally, a generation marker has no interesting properties except for
43 * its identity, so we could just as well use a plain `Brand'. For
44 * diagnostic purposes though, we include a sequence number which we can
45 * include in the object printout.
50 Generation synchronized { val v = nextseq; nextseq += 1; v };
51 override def toString(): String = s"${getClass.getName}($what, #$seq)";
54 class BadDep extends Throwable;
55 /* Thrown when you try to read a `bad' `Dep' object. */
57 class CircularDependency extends Exception;
58 /* Thrown if a `Dep' depends on itself, possibly indirectly. */
60 /* Some type aliases because otherwise we need to mess with existential
63 type AbstractDep = Dep[_];
64 type AbstractComputedDep = ComputedDep[_];
68 /* Event types for hook clients. */
69 sealed abstract class Event;
70 case object Changed extends Event;
72 /* Flags for `Dep' objects. */
73 private[dep] final val F_VALUE = 1; // has a value
74 private[dep] final val F_DEPS = 2; // dependencies are know
75 private[dep] final val F_CHANGED = 4; // changed in this update cycle
76 private[dep] final val F_RECOMPUTING = 8; // currently recomputing
77 private[dep] final val F_QUEUED = 16; // queued for recomputation
79 /* Overall system state. */
80 object DepState extends Enumeration
81 { val READY, FROZEN, RECOMPUTING = Value; }
82 import DepState.{READY, FROZEN, RECOMPUTING, Value => State};
84 private[dep] var generation: Generation = new Generation("dep-generation");
85 /* The current generation. Updated in `withDepsFrozen'. */
87 private[dep] val state = new SharedFluid(READY);
88 /* The current system state. Must be `let'-bound. */
90 private[dep] val evaluating = new SharedFluid[AbstractComputedDep](null);
91 /* The `ComputedDep' object which is being evaluated, or null. Must be
95 private[dep] val delayed = new SharedFluid[Queue[() => Unit]](null);
96 /* Delayed thunks from `withDepsDelayed'. Must be `let'-bound to a fresh
97 * `Queue', and then mutated in place.
100 private[dep] val pending =
101 new SharedFluid[Queue[AbstractComputedDep]](null);
102 /* `ComputedDep' objects awaiting recomputation. Must be `let'-bound to
103 * a fresh `Queue', and then mutated in place.
106 private def recomputePending() {
107 /* Recalculate the deps on the `pending' queue.
109 * While this is running, we are in the `RECOMPUTING' state.
112 let(state -> RECOMPUTING) {
115 val d = pending.v.dequeue();
117 d._flags = f&~F_QUEUED;
118 if (!(f&F_VALUE)) d.recompute();
119 else if (!(f&F_DEPS)) { d.recompute(); d.flags = f | F_DEPS; }
122 while (pending.v) pending.v.dequeue()._val = None;
127 def withDepsFrozen[T](body: => T): T = state.v match {
128 /* Evaluate the BODY, allowing it to modify `Dep' objects. When the BODY
129 * completes, but not before, all dependent `Dep's are recalculated.
130 * This can be used to improve performance if a big batch of changes is
133 * It's not permitted to modify a `Dep' while recomputation is in
134 * progress. See `withDepsDelayed'.
139 throw new IllegalStateException("currently recomputing");
142 delayed -> new Queue[() => Unit],
143 pending -> new Queue[AbstractComputedDep]) {
144 generation = new Generation("dep-generation");
146 while ({ recomputePending(); delayed.v }) delayed.v.dequeue()();
151 def withDepsDelayed(body: => Unit) { state.v match {
152 /* Evaluate the BODY, allowing it to modify `Dep' objects. If
153 * recomputation is in progress, then save the BODY in a queue to be
157 case RECOMPUTING => delayed.v += { () => body };
158 case _ => withDepsFrozen { body };
161 /* Various constructures for basic `Dep' objects. */
162 def apply[T: Equiv](name: String, init: T): Dep[T] =
163 new Dep(name, Some(init));
164 def apply[T: Equiv](name: String): Dep[T] = new Dep(name, None);
165 def apply[T: Equiv](init: T): Dep[T] = new Dep(null, Some(init));
166 def apply[T: Equiv](): Dep[T] = new Dep(null, None);
169 /* Import these things here so that they're included in the scope of `Dep''s
170 * additional constructor bodies.
174 /* tryDep { BODY } ifBad { ALT }
176 * Evaluate BODY. If it tries to read a bad `Dep', then evaluate ALT
179 class PendingAttempt[T] private[dep](body: => T)
180 { def ifBad(alt: => T): T = try { body } catch { case _: BadDep => alt } }
181 def tryDep[T](body: => T): PendingAttempt[T] = new PendingAttempt(body);
183 def bad: Nothing = throw new BadDep;
184 /* Call from a `Dep' expression to cause the `Dep' to be marked bad. */
186 class Dep[T: Equiv] protected(val name: String,
189 extends Hook[Dep.Event]
193 * A `Dep' has a value, of some type T, and maybe a name. The value is
194 * available in the `v' property. A `Dep' may be `bad', in which case an
195 * exception, `BadDep', is thrown when an attempt is made to read its
196 * value; this can be hedged against either by calling `goodp' in advance,
197 * or by using the `tryDep' function.
199 * The value of a leaf `Dep' changes only as a result of direct assignments
200 * to its `v' property.
203 /* Internal constructor, for the benefit of the companion module. */
204 private def this(name: String, init: Option[T])
205 { this(name, init, F_CHANGED | F_VALUE); }
207 /* Other useful definitions. */
208 import DepState.{READY, FROZEN, RECOMPUTING, Value => State};
210 protected var gen: Generation = generation;
211 /* The generation during which this `Dep' was most recently updated. */
213 protected val dependents =
214 new ArrayBuffer[WeakReference[AbstractComputedDep]];
215 /* A collection of other `Dep's which depend (directly) on this one. */
217 override def toString(): String = {
218 /* Convert this `Dep' to a string. The contents are useful only for
219 * diagnostic purposes.
222 val b = new StringBuilder;
225 b ++= f"${getClass.getName}%s@${hashCode}%x(";
228 case _ if !(f&F_VALUE) => "<out-of-date>"
230 case Some(x) => x.toString
233 if (name != null) b ++= s" $name";
235 if (f&F_DEPS) b ++= " :recompute-deps";
236 if (f&F_QUEUED) b ++= " :queued";
237 if (f&F_CHANGED) b ++= " :changed";
242 /* A property for accessing the `Dep' flags.
244 * The flags stored are only relevant during recomputation and if they're
245 * fresh. Otherwise we must synthesize appropriate flags.
247 protected[dep] def flags: Int =
248 if (state.v == READY || gen != generation) F_VALUE | F_DEPS
250 protected[dep] def flags_=(f: Int) { _flags = f; }
252 def update(v: Option[T]): Boolean = (v, _val) match {
253 /* Set this `Dep''s value to V; return true if this is a substantive
256 case (Some(x), Some(y)) if implicitly[Equiv[T]].equiv(x, y) => false
257 case _ => _val = v; true
260 protected def propagate() {
261 /* Notify all of our dependents that this `Dep' has changed its value. */
267 if !(f&(F_QUEUED | F_DEPS))
270 d.flags = (f&F_VALUE) | F_QUEUED;
276 private[dep] def force(): Boolean = flags&F_CHANGED;
277 /* Force this `Dep' to update its value if it hasn't done so already in
278 * the current recomputation cycle. Return true if its value has changed
279 * in the current cycle.
281 * The implementation here is trivial, but subclasses will need to
286 /* Return the value of this `Dep', recalculating it if necessary.
288 * Throws `BadDep' if the `Dep is bad.
291 if (state.v == RECOMPUTING) {
292 if (evaluating.v != null) {
293 dependents += evaluating.v.weakref;
294 evaluating.v.dependencies += this;
304 /* The obvious good/bad predicates. */
305 def goodp: Boolean = { if (state.v == RECOMPUTING) force(); _val != bad }
306 def badp: Boolean = { if (state.v == RECOMPUTING) force(); _val == bad }
308 private def set(v: Option[T]) {
309 /* Low-level operation to change the value of this `Dep', and trigger
310 * recomputation as necessary.
316 _flags = F_VALUE | F_CHANGED;
321 /* Modify the `Dep' value. */
322 def v_=(x: T) { set(Some(x)); }
323 def makeBad() { set(None); }
328 /* Cooked constructors. */
329 def apply[T: Equiv](expr: => T) = new ComputedDep(null, expr, None);
330 def apply[T: Equiv](name: String)(expr: => T) =
331 new ComputedDep(name, expr, None);
332 def apply[T: Equiv](init: T)(expr: => T) =
333 new ComputedDep(null, expr, Some(init));
334 def apply[T: Equiv](name: String, init: T)(expr: => T) =
335 new ComputedDep(name, expr, Some(init));
338 class ComputedDep[T: Equiv] protected(name: String,
341 extends Dep[T](name, init,
342 F_CHANGED | F_QUEUED | F_DEPS | (init match {
343 case Some(_) => F_VALUE
347 /* A `Dep' which calculates its value based on other `Dep' objects.
349 * During this calculation, we keep track of the dependency structure so
350 * that, in the future, we can determine whether this `Dep' needs to be
351 * recalculated as a result of other changes.
354 private[dep] val dependencies = new ArrayBuffer[AbstractDep];
355 /* A collection of other `Dep' objects; if any of them change, we must
359 private[dep] val weakref: WeakReference[AbstractComputedDep] =
360 new WeakReference(this);
361 /* A weak reference to this `Dep'.
363 * A `Dep' maintains only weak references to those other `Dep's which
364 * depend on it: just because X's value is determined (partially) by Y
365 * doesn't mean that we should keep X alive just because Y is alive.
367 * The weak reference is captured once to reduce consing.
370 /* Arrange recalculation at the earliest opportunity. */
371 withDepsFrozen { pending.v += this; }
373 /* Other useful definitions. */
374 import DepState.{READY, FROZEN, RECOMPUTING, Value => State};
376 /* Synthesize different flags when we aren't fresh. */
377 override protected[dep] def flags: Int =
378 if (state.v == READY) F_VALUE | F_DEPS
379 else if (gen == generation) _flags
382 def newValue(): Option[T] = {
383 /* Determine the new value of this `Dep', keeping track of other `Dep'
384 * objects which we look at.
387 try { let(evaluating -> this) { dependencies.clear(); Some(expr)} }
388 catch { case _: BadDep => None }
391 private[this] def _recompute(v: Option[T], nf: Int): Boolean =
392 if (update(v)) { flags = nf | Dep.F_CHANGED; propagate(); true }
393 else { flags = nf; false }
395 private[dep] def recompute(): Boolean = {
396 /* Recalculate the value of this `Dep'. Catch exceptions and mark the
397 * `Dep' as bad if it encounters any.
399 * Note that the special case of `BadDep' is trapped lower down in
403 val nf = (flags&F_QUEUED) | F_VALUE | F_DEPS;
404 try { _recompute(newValue(), nf) }
405 catch { case e: Exception => _recompute(None, nf); throw e; }
408 private[dep] override def force(): Boolean = {
409 /* Force this `Dep' to update its value if it hasn't done so already in
410 * the current recomputation cycle. Return true if its value has changed
411 * in the current cycle.
415 if (f&F_RECOMPUTING) throw new CircularDependency;
416 else if (f&F_VALUE) f&F_CHANGED
419 flags = (f&F_QUEUED) | F_RECOMPUTING;
420 if (dependencies.exists { _.force() }) recompute();
421 else { flags = f; false }
426 /*----- That's all, folks -------------------------------------------------*/