chiark - git - mdw - tripe-android/blob - dep.scala

   1 /* -*-scala-*-
   2  *
   3  * Dependency-based computation
   4  *
   5  * (c) 2018 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of the Trivial IP Encryption (TrIPE) Android app.
  11  *
  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.
  16  *
  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
  20  * for more details.
  21  *
  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/>.
  24  */
  25
  26 package uk.org.distorted.tripe; package object dep {
  27
  28 /*----- Imports -----------------------------------------------------------*/
  29
  30 import scala.collection.mutable.{ArrayBuffer, Queue};
  31
  32 import java.lang.ref.WeakReference;
  33
  34 import Implicits.{truish, bitwiseImplicits};
  35
  36 /*----- Main code ---------------------------------------------------------*/
  37
  38 object Generation {
  39   private var nextseq: Int = 0;
  40 }
  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.
  46    */
  47
  48   import Generation._;
  49   private val seq =
  50     Generation synchronized { val v = nextseq; nextseq += 1; v };
  51   override def toString(): String = s"${getClass.getName}($what, #$seq)";
  52 }
  53
  54 class BadDep extends Throwable;
  55   /* Thrown when you try to read a `bad' `Dep' object. */
  56
  57 class CircularDependency extends Exception;
  58   /* Thrown if a `Dep' depends on itself, possibly indirectly. */
  59
  60 /* Some type aliases because otherwise we need to mess with existential
  61  * types.
  62  */
  63 type AbstractDep = Dep[_];
  64 type AbstractComputedDep = ComputedDep[_];
  65
  66 object Dep {
  67
  68   /* Event types for hook clients. */
  69   sealed abstract class Event;
  70   case object Changed extends Event;
  71
  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
  78
  79   /* Overall system state. */
  80   object DepState extends Enumeration
  81     { val READY, FROZEN, RECOMPUTING = Value; }
  82   import DepState.{READY, FROZEN, RECOMPUTING, Value => State};
  83
  84   private[dep] var generation: Generation = new Generation("dep-generation");
  85     /* The current generation.   Updated in `withDepsFrozen'. */
  86
  87   private[dep] val state = new SharedFluid(READY);
  88     /* The current system state.  Must be `let'-bound. */
  89
  90   private[dep] val evaluating = new SharedFluid[AbstractComputedDep](null);
  91     /* The `ComputedDep' object which is being evaluated, or null.  Must be
  92      * `let'-bound.
  93      */
  94
  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.
  98      */
  99
 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.
 104      */
 105
 106   private def recomputePending() {
 107     /* Recalculate the deps on the `pending' queue.
 108      *
 109      * While this is running, we are in the `RECOMPUTING' state.
 110      */
 111
 112     let(state -> RECOMPUTING) {
 113       try {
 114         while (pending.v) {
 115           val d = pending.v.dequeue();
 116           val f = d._flags;
 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; }
 120         }
 121       } finally {
 122         while (pending.v) pending.v.dequeue()._val = None;
 123       }
 124     }
 125   }
 126
 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
 131      * planned.
 132      *
 133      * It's not permitted to modify a `Dep' while recomputation is in
 134      * progress.  See `withDepsDelayed'.
 135      */
 136
 137     case FROZEN => body
 138     case RECOMPUTING =>
 139       throw new IllegalStateException("currently recomputing");
 140     case READY =>
 141       let(state -> FROZEN,
 142           delayed -> new Queue[() => Unit],
 143           pending -> new Queue[AbstractComputedDep]) {
 144         generation = new Generation("dep-generation");
 145         val r = body;
 146         while ({ recomputePending(); delayed.v }) delayed.v.dequeue()();
 147         r
 148       }
 149     }
 150
 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
 154      * evaluated later.
 155      */
 156
 157     case RECOMPUTING => delayed.v += { () => body };
 158     case _ => withDepsFrozen { body };
 159   } }
 160
 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);
 167 }
 168
 169 /* Import these things here so that they're included in the scope of `Dep''s
 170  * additional constructor bodies.
 171  */
 172 import Dep._;
 173
 174 /* tryDep { BODY } ifBad { ALT }
 175  *
 176  * Evaluate BODY.  If it tries to read a bad `Dep', then evaluate ALT
 177  * instead.
 178  */
 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);
 182
 183 def bad: Nothing = throw new BadDep;
 184   /* Call from a `Dep' expression to cause the `Dep' to be marked bad. */
 185
 186 class Dep[T: Equiv] protected(val name: String,
 187                               var _val: Option[T],
 188                               var _flags: Int)
 189         extends Hook[Dep.Event]
 190 {
 191   /* A leaf `Dep'.
 192    *
 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.
 198    *
 199    * The value of a leaf `Dep' changes only as a result of direct assignments
 200    * to its `v' property.
 201    */
 202
 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); }
 206
 207   /* Other useful definitions. */
 208   import DepState.{READY, FROZEN, RECOMPUTING, Value => State};
 209
 210   protected var gen: Generation = generation;
 211     /* The generation during which this `Dep' was most recently updated. */
 212
 213   protected val dependents =
 214     new ArrayBuffer[WeakReference[AbstractComputedDep]];
 215     /* A collection of other `Dep's which depend (directly) on this one. */
 216
 217   override def toString(): String = {
 218     /* Convert this `Dep' to a string.  The contents are useful only for
 219      * diagnostic purposes.
 220      */
 221
 222     val b = new StringBuilder;
 223     val f = flags;
 224
 225     b ++= f"${getClass.getName}%s@${hashCode}%x(";
 226
 227     b ++= (_val match {
 228       case _ if !(f&F_VALUE) => "<out-of-date>"
 229       case None => "<bad>"
 230       case Some(x) => x.toString
 231     })
 232
 233     if (name != null) b ++= s" $name";
 234
 235     if (f&F_DEPS) b ++= " :recompute-deps";
 236     if (f&F_QUEUED) b ++= " :queued";
 237     if (f&F_CHANGED) b ++= " :changed";
 238
 239     b += ')'; b.result
 240   }
 241
 242   /* A property for accessing the `Dep' flags.
 243    *
 244    * The flags stored are only relevant during recomputation and if they're
 245    * fresh.  Otherwise we must synthesize appropriate flags.
 246    */
 247   protected[dep] def flags: Int =
 248     if (state.v == READY || gen != generation) F_VALUE | F_DEPS
 249     else _flags;
 250   protected[dep] def flags_=(f: Int) { _flags = f; }
 251
 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
 254      * change.
 255      */
 256     case (Some(x), Some(y)) if implicitly[Equiv[T]].equiv(x, y) => false
 257     case _ => _val = v; true
 258   }
 259
 260   protected def propagate() {
 261     /* Notify all of our dependents that this `Dep' has changed its value. */
 262     for {
 263       dweak <- dependents;
 264       d = dweak.get;
 265       if d != null;
 266       f = d.flags;
 267       if !(f&(F_QUEUED | F_DEPS))
 268     } {
 269       pending.v += d;
 270       d.flags = (f&F_VALUE) | F_QUEUED;
 271     }
 272     dependents.clear();
 273     callHook(Changed);
 274   }
 275
 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.
 280      *
 281      * The implementation here is trivial, but subclasses will need to
 282      * override it.
 283      */
 284
 285   def v: T = {
 286     /* Return the value of this `Dep', recalculating it if necessary.
 287      *
 288      * Throws `BadDep' if the `Dep is bad.
 289      */
 290
 291     if (state.v == RECOMPUTING) {
 292       if (evaluating.v != null) {
 293         dependents += evaluating.v.weakref;
 294         evaluating.v.dependencies += this;
 295       }
 296       force();
 297     }
 298     _val match {
 299       case None => bad
 300       case Some(v) => v
 301     }
 302   }
 303
 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 }
 307
 308   private def set(v: Option[T]) {
 309     /* Low-level operation to change the value of this `Dep', and trigger
 310      * recomputation as necessary.
 311      */
 312
 313     withDepsFrozen {
 314       update(v);
 315       gen = generation;
 316       _flags = F_VALUE | F_CHANGED;
 317       propagate();
 318     }
 319   }
 320
 321   /* Modify the `Dep' value. */
 322   def v_=(x: T) { set(Some(x)); }
 323   def makeBad() { set(None); }
 324 }
 325
 326 object ComputedDep {
 327
 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));
 336 }
 337
 338 class ComputedDep[T: Equiv] protected(name: String,
 339                                       expr: => T,
 340                                       init: Option[T])
 341         extends Dep[T](name, init,
 342                        F_CHANGED | F_QUEUED | F_DEPS | (init match {
 343                          case Some(_) => F_VALUE
 344                          case None => 0
 345                        }))
 346 {
 347   /* A `Dep' which calculates its value based on other `Dep' objects.
 348    *
 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.
 352    */
 353
 354   private[dep] val dependencies = new ArrayBuffer[AbstractDep];
 355     /* A collection of other `Dep' objects; if any of them change, we must
 356      * recalculate.
 357      */
 358
 359   private[dep] val weakref: WeakReference[AbstractComputedDep] =
 360     new WeakReference(this);
 361     /* A weak reference to this `Dep'.
 362      *
 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.
 366      *
 367      * The weak reference is captured once to reduce consing.
 368      */
 369
 370   /* Arrange recalculation at the earliest opportunity. */
 371   withDepsFrozen { pending.v += this; }
 372
 373   /* Other useful definitions. */
 374   import DepState.{READY, FROZEN, RECOMPUTING, Value => State};
 375
 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
 380     else 0;
 381
 382   def newValue(): Option[T] = {
 383     /* Determine the new value of this `Dep', keeping track of other `Dep'
 384      * objects which we look at.
 385      */
 386
 387     try { let(evaluating -> this) { dependencies.clear(); Some(expr)} }
 388     catch { case _: BadDep => None }
 389   }
 390
 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 }
 394
 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.
 398      *
 399      * Note that the special case of `BadDep' is trapped lower down in
 400      * `newValue'.
 401      */
 402
 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; }
 406   }
 407
 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.
 412      */
 413
 414     val f = flags;
 415     if (f&F_RECOMPUTING) throw new CircularDependency;
 416     else if (f&F_VALUE) f&F_CHANGED
 417     else {
 418       gen = generation;
 419       flags = (f&F_QUEUED) | F_RECOMPUTING;
 420       if (dependencies.exists { _.force() }) recompute();
 421       else { flags = f; false }
 422     }
 423   }
 424 }
 425
 426 /*----- That's all, folks -------------------------------------------------*/
 427
 428 }