Commit | Line | Data |
---|---|---|
0157de02 MW |
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 | } |