xref: /aosp_15_r20/frameworks/base/packages/SystemUI/utils/kairos/docs/semantics.md (revision d57664e9bc4670b3ecf6748a746a57c557b6bc9e) 
1# FRP Semantics
2
3`Kairos`'s pure API is based off of the following denotational semantics
4([wikipedia](https://en.wikipedia.org/wiki/Denotational_semantics)).
5
6The semantics model `Kairos` types as time-varying values; by making `Time` a
7first-class value, we can define a referentially-transparent API that allows us
8to reason about the behavior of the pure `Kairos` combinators. This is
9implementation-agnostic; we can compare the behavior of any implementation with
10expected behavior denoted by these semantics to identify bugs.
11
12The semantics are written in pseudo-Kotlin; places where we are deviating from
13real Kotlin are noted with comments.
14
15``` kotlin
16
17sealed class Time : Comparable<Time> {
18  object BigBang : Time()
19  data class At(time: BigDecimal) : Time()
20  object Infinity : Time()
21
22  override final fun compareTo(other: Time): Int =
23    when (this) {
24      BigBang -> if (other === BigBang) 0 else -1
25      is At -> when (other) {
26        BigBang -> 1
27        is At -> time.compareTo(other.time)
28        Infinity -> -1
29      }
30      Infinity -> if (other === Infinity) 0 else 1
31    }
32}
33
34typealias Transactional<T> = (Time) -> T
35
36typealias TFlow<T> = SortedMap<Time, T>
37
38private fun <T> SortedMap<Time, T>.pairwise(): List<Pair<Pair<Time, T>, Pair<Time<T>>>> =
39  // NOTE: pretend evaluation is lazy, so that error() doesn't immediately throw
40  (toList() + Pair(Time.Infinity, error("no value"))).zipWithNext()
41
42class TState<T> internal constructor(
43  internal val current: Transactional<T>,
44  val stateChanges: TFlow<T>,
45)
46
47val emptyTFlow: TFlow<Nothing> = emptyMap()
48
49fun <A, B> TFlow<A>.map(f: FrpTransactionScope.(A) -> B): TFlow<B> =
50  mapValues { (t, a) -> FrpTransactionScope(t).f(a) }
51
52fun <A> TFlow<A>.filter(f: FrpTransactionScope.(A) -> Boolean): TFlow<A> =
53  filter { (t, a) -> FrpTransactionScope(t).f(a) }
54
55fun <A> merge(
56  first: TFlow<A>,
57  second: TFlow<A>,
58  onCoincidence: Time.(A, A) -> A,
59): TFlow<A> =
60  first.toMutableMap().also { result ->
61    second.forEach { (t, a) ->
62      result.merge(t, a) { f, s ->
63        FrpTranscationScope(t).onCoincidence(f, a)
64      }
65    }
66  }.toSortedMap()
67
68fun <A> TState<TFlow<A>>.switch(): TFlow<A> {
69  val truncated = listOf(Pair(Time.BigBang, current.invoke(Time.BigBang))) +
70    stateChanges.dropWhile { (time, _) -> time < time0 }
71  val events =
72    truncated
73      .pairwise()
74      .flatMap { ((t0, sa), (t2, _)) ->
75        sa.filter { (t1, a) -> t0 < t1 && t1 <= t2 }
76      }
77  return events.toSortedMap()
78}
79
80fun <A> TState<TFlow<A>>.switchPromptly(): TFlow<A> {
81  val truncated = listOf(Pair(Time.BigBang, current.invoke(Time.BigBang))) +
82    stateChanges.dropWhile { (time, _) -> time < time0 }
83  val events =
84    truncated
85      .pairwise()
86      .flatMap { ((t0, sa), (t2, _)) ->
87        sa.filter { (t1, a) -> t0 <= t1 && t1 <= t2 }
88      }
89  return events.toSortedMap()
90}
91
92typealias GroupedTFlow<K, V> = TFlow<Map<K, V>>
93
94fun <K, V> TFlow<Map<K, V>>.groupByKey(): GroupedTFlow<K, V> = this
95
96fun <K, V> GroupedTFlow<K, V>.eventsForKey(key: K): TFlow<V> =
97  map { m -> m[k] }.filter { it != null }.map { it!! }
98
99fun <A, B> TState<A>.map(f: (A) -> B): TState<B> =
100  TState(
101    current = { t -> f(current.invoke(t)) },
102    stateChanges = stateChanges.map { f(it) },
103  )
104
105fun <A, B, C> TState<A>.combineWith(
106  other: TState<B>,
107  f: (A, B) -> C,
108): TState<C> =
109  TState(
110    current = { t -> f(current.invoke(t), other.current.invoke(t)) },
111    stateChanges = run {
112      val aChanges =
113        stateChanges
114          .map { a ->
115            val b = other.current.sample()
116            Triple(a, b, f(a, b))
117          }
118      val bChanges =
119        other
120          .stateChanges
121          .map { b ->
122            val a = current.sample()
123            Triple(a, b, f(a, b))
124          }
125      merge(aChanges, bChanges) { (a, _, _), (_, b, _) ->
126          Triple(a, b, f(a, b))
127        }
128        .map { (_, _, zipped) -> zipped }
129    },
130  )
131
132fun <A> TState<TState<A>>.flatten(): TState<A> {
133  val changes =
134    stateChanges
135      .pairwise()
136      .flatMap { ((t0, oldInner), (t2, _)) ->
137        val inWindow =
138          oldInner
139            .stateChanges
140            .filter { (t1, b) -> t0 <= t1 && t1 < t2 }
141        if (inWindow.firstOrNull()?.time != t0) {
142          listOf(Pair(t0, oldInner.current.invoke(t0))) + inWindow
143        } else {
144          inWindow
145        }
146      }
147  return TState(
148    current = { t -> current.invoke(t).current.invoke(t) },
149    stateChanges = changes.toSortedMap(),
150  )
151}
152
153open class FrpTranscationScope internal constructor(
154  internal val currentTime: Time,
155) {
156  val now: TFlow<Unit> =
157    sortedMapOf(currentTime to Unit)
158
159  fun <A> Transactional<A>.sample(): A =
160    invoke(currentTime)
161
162  fun <A> TState<A>.sample(): A =
163    current.sample()
164}
165
166class FrpStateScope internal constructor(
167  time: Time,
168  internal val stopTime: Time,
169): FrpTransactionScope(time) {
170
171  fun <A, B> TFlow<A>.fold(
172    initialValue: B,
173    f: FrpTransactionScope.(B, A) -> B,
174  ): TState<B> {
175    val truncated =
176      dropWhile { (t, _) -> t < currentTime }
177        .takeWhile { (t, _) -> t <= stopTime }
178    val folded =
179      truncated
180        .scan(Pair(currentTime, initialValue)) { (_, b) (t, a) ->
181          Pair(t, FrpTransactionScope(t).f(a, b))
182        }
183    val lookup = { t1 ->
184      folded.lastOrNull { (t0, _) -> t0 < t1 }?.value ?: initialValue
185    }
186    return TState(lookup, folded.toSortedMap())
187  }
188
189  fun <A> TFlow<A>.hold(initialValue: A): TState<A> =
190    fold(initialValue) { _, a -> a }
191
192  fun <K, V> TFlow<Map<K, Maybe<V>>>.foldMapIncrementally(
193    initialValues: Map<K, V>
194  ): TState<Map<K, V>> =
195    fold(initialValues) { patch, map ->
196      val eithers = patch.map { (k, v) ->
197        if (v is Just) Left(k to v.value) else Right(k)
198      }
199      val adds = eithers.filterIsInstance<Left>().map { it.left }
200      val removes = eithers.filterIsInstance<Right>().map { it.right }
201      val removed: Map<K, V> = map - removes.toSet()
202      val updated: Map<K, V> = removed + adds
203      updated
204    }
205
206  fun <K : Any, V> TFlow<Map<K, Maybe<TFlow<V>>>>.mergeIncrementally(
207    initialTFlows: Map<K, TFlow<V>>,
208  ): TFlow<Map<K, V>> =
209    foldMapIncrementally(initialTFlows).map { it.merge() }.switch()
210
211  fun <K, A, B> TFlow<Map<K, Maybe<A>>.mapLatestStatefulForKey(
212    transform: suspend FrpStateScope.(A) -> B,
213  ): TFlow<Map<K, Maybe<B>>> =
214    pairwise().map { ((t0, patch), (t1, _)) ->
215      patch.map { (k, ma) ->
216        ma.map { a ->
217          FrpStateScope(t0, t1).transform(a)
218        }
219      }
220    }
221  }
222
223}
224
225```
226