| 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 | } |