<lambda>null1 package com.android.onboarding.nodes
2
3 import com.android.onboarding.nodes.OnboardingGraphNodeData.Component
4 import com.android.onboarding.nodes.OnboardingGraphNodeData.Type
5 import com.google.errorprone.annotations.CanIgnoreReturnValue
6 import java.time.Duration
7 import java.time.Instant
8 import kotlin.math.absoluteValue
9 import kotlin.properties.Delegates
10
11 internal object OnboardingGraphBuilder {
12
13 fun build(events: Iterable<OnboardingGraphLog.OnboardingEventDelegate>): OnboardingGraph {
14 val sortedEvents =
15 events
16 .distinctBy(OnboardingGraphLog.OnboardingEventDelegate::source)
17 .sortedBy(OnboardingGraphLog.OnboardingEventData::timestamp)
18
19 val nodes = buildNodes(sortedEvents)
20 return object : OnboardingGraph {
21 override val events: Iterable<OnboardingGraphLog.OnboardingEventDelegate> = sortedEvents
22 override val nodes: Map<Long, OnboardingGraphNode> = nodes
23 }
24 }
25
26 private fun buildNodes(
27 events: Iterable<OnboardingGraphLog.OnboardingEventDelegate>
28 ): Map<Long, NodeBuilder> = buildMap {
29 /**
30 * First pass:
31 * - Build nodes from the events they've spawned
32 * - Append spawned events
33 * - Append outgoing edges
34 * - Set obvious types
35 * - Prepare second pass
36 */
37 val secondPass = mutableListOf<OnboardingGraphLog.OnboardingEventDelegate>()
38 for (event in events) {
39 when (val source = event.source) {
40 is OnboardingEvent.ActivityNodeStartExecuteSynchronously -> {
41 secondPass += event
42 spawnNode(source.sourceNodeId, event) {
43 /*
44 * Don't create an outgoing edge since [OnboardingEvent.ActivityNodeExecutedForResult]
45 * is always spawned after [OnboardingEvent.ActivityNodeExecutedSynchronously]
46 */
47 }
48 }
49 is OnboardingEvent.ActivityNodeExecutedForResult -> {
50 secondPass += event
51 spawnNode(source.sourceNodeId, event) {
52 outgoingEdges(
53 InternalEdge.OutgoingEdge(
54 id = event.safeId(event.nodeId),
55 timestamp = event.timestamp,
56 )
57 )
58 }
59 }
60 is OnboardingEvent.ActivityNodeExecutedDirectly -> {
61 secondPass += event
62 spawnNode(source.sourceNodeId, event) {
63 outgoingEdges(
64 InternalEdge.OutgoingEdge(
65 id = event.safeId(event.nodeId),
66 timestamp = event.timestamp,
67 )
68 )
69 }
70 }
71 is OnboardingEvent.ActivityNodeExecutedSynchronously,
72 is OnboardingEvent.ActivityNodeResultReceived -> {
73 /* Spawned at source but does not contain source id */
74 secondPass += event
75 }
76 is OnboardingEvent.ActivityNodeResumedAfterLaunch -> {
77 secondPass += event
78 spawnNode(event.nodeId, event) {
79 name(event.nodeName)
80 component(event.nodeComponent)
81 type(Type.ACTIVITY)
82 }
83 }
84 is OnboardingEvent.ActivityNodeArgumentExtracted -> {
85 spawnNode(event.nodeId, event).update(event) {
86 name(event.nodeName)
87 component(event.nodeComponent)
88 type(Type.ACTIVITY)
89 argument(source.argument)
90 }
91 }
92 is OnboardingEvent.ActivityNodeSetResult -> {
93 spawnNode(event.nodeId, event) {
94 name(event.nodeName)
95 component(event.nodeComponent)
96 type(Type.ACTIVITY)
97 result(source.result)
98 }
99 }
100 is OnboardingEvent.ActivityNodeFail -> {
101 spawnNode(event.nodeId, event) {
102 name(event.nodeName)
103 component(event.nodeComponent)
104 type(Type.ACTIVITY)
105 failureReasons(IllegalStateException(source.reason))
106 }
107 }
108 is OnboardingEvent.ActivityNodeFailedValidation -> {
109 spawnNode(event.nodeId, event) {
110 name(event.nodeName)
111 component(event.nodeComponent)
112 type(Type.ACTIVITY)
113 failureReasons(source.exception)
114 }
115 }
116 is OnboardingEvent.ActivityNodeFinished -> {
117 spawnNode(event.nodeId, event) {
118 name(event.nodeName)
119 component(event.nodeComponent)
120 type(Type.ACTIVITY)
121 finish(source)
122 }
123 }
124 is OnboardingEvent.ActivityNodeResumed,
125 is OnboardingEvent.ActivityNodeValidating,
126 is OnboardingEvent.ActivityNodeExtractArgument -> {
127 spawnNode(event.nodeId, event) {
128 name(event.nodeName)
129 component(event.nodeComponent)
130 type(Type.ACTIVITY)
131 }
132 }
133 }
134 }
135
136 /**
137 * Second pass:
138 * - Stub nodes that did not spawn events
139 * - Append related events
140 * - Append incoming edges
141 * - Set remaining types
142 * - Prepare third pass
143 */
144 val thirdPass = mutableListOf<OnboardingGraphLog.OnboardingEventDelegate>()
145 for (event in secondPass) {
146 when (val source = event.source) {
147 is OnboardingEvent.ActivityNodeStartExecuteSynchronously -> {
148 node(
149 event.nodeId,
150 event,
151 onStub = { warn("Target node($it) not found in second pass for $event!") },
152 ) {
153 relatedEvents(event)
154 name(event.nodeName)
155 component(event.nodeComponent)
156 type(Type.SYNCHRONOUS)
157 argument(source.argument)
158 incomingEdge(
159 InternalEdge.OpenIncomingEdge(
160 id = event.safeId(source.sourceNodeId),
161 timestamp = event.timestamp,
162 )
163 )
164 }
165 }
166 is OnboardingEvent.ActivityNodeExecutedForResult -> {
167 node(
168 event.nodeId,
169 event,
170 onStub = { warn("Target node($it) not found in second pass for $event!") },
171 ) {
172 relatedEvents(event)
173 name(event.nodeName)
174 component(event.nodeComponent)
175 type(Type.ACTIVITY)
176 argument(source.argument)
177 incomingEdge(
178 InternalEdge.OpenIncomingEdge(
179 id = event.safeId(source.sourceNodeId),
180 timestamp = event.timestamp,
181 )
182 )
183 }
184 }
185 is OnboardingEvent.ActivityNodeExecutedDirectly -> {
186 node(
187 event.nodeId,
188 event,
189 onStub = { warn("Target node($it) not found in second pass for $event!") },
190 ) {
191 relatedEvents(event)
192 name(event.nodeName)
193 component(event.nodeComponent)
194 type(Type.ACTIVITY)
195 argument(source.argument)
196 incomingEdge(
197 InternalEdge.ClosedIncomingEdge(
198 id = event.safeId(source.sourceNodeId),
199 timestamp = event.timestamp,
200 )
201 )
202 }
203 }
204 is OnboardingEvent.ActivityNodeExecutedSynchronously,
205 is OnboardingEvent.ActivityNodeResultReceived -> {
206 thirdPass += event
207 node(
208 event.nodeId,
209 event,
210 onStub = { warn("Target node($it) not found in second pass for $event!") },
211 ) {
212 relatedEvents(event)
213 name(event.nodeName)
214 component(event.nodeComponent)
215 type(Type.ACTIVITY)
216 if (source is OnboardingEvent.WithResult) result(source.result)
217 }
218 }
219 is OnboardingEvent.ActivityNodeResumedAfterLaunch -> {
220 node(
221 source.sourceNodeId,
222 event,
223 onStub = { warn("Target node($it) not found in second pass for $event!") },
224 ) {
225 relatedEvents(event)
226 }
227 }
228 else -> {
229 /* ignored */
230 }
231 }
232 }
233 /**
234 * Third pass:
235 * - Join executions to source nodes via incomingEdges
236 */
237 for (event in thirdPass) {
238 when (event.source) {
239 is OnboardingEvent.ActivityNodeExecutedSynchronously -> {
240 node(
241 event.nodeId,
242 event,
243 onStub = { warn("Target node($it) not found in third pass for $event!") },
244 ) {
245 val incomingEdge = node.incomingEdge
246 if (incomingEdge == null) {
247 warn("Missing incoming edge for ${node.identity} $event")
248 } else {
249 incomingEdge.node.update(event) { spawnedEvents(event) }
250 }
251 }
252 }
253 is OnboardingEvent.ActivityNodeResultReceived -> {
254 node(
255 event.nodeId,
256 event,
257 onStub = { warn("Target node($it) not found in third pass for $event!") },
258 ) {
259 val incomingEdge = node.incomingEdge
260 if (incomingEdge == null) {
261 warn("Missing incoming edge for ${node.identity} $event")
262 } else {
263 incomingEdge.node.update(event) { spawnedEvents(event) }
264 }
265 }
266 }
267 else -> {
268 /* ignored */
269 }
270 }
271 }
272
273 /*
274 * Then we need to recursively expand the time of all callers which are waiting for a result -
275 * as they haven't finished executing.
276 */
277 val nodesToRemove = mutableSetOf<Long>()
278 for (node in values) {
279 var recursiveNode: NodeBuilder? = node
280 while (recursiveNode != null) {
281 recursiveNode =
282 recursiveNode.incomingEdge
283 ?.takeIf { it is InternalEdge.OpenIncomingEdge }
284 ?.let { incomingEdge ->
285 incomingEdge.node.also { incomingNode ->
286 /*
287 * If the edge is "Open" then it's waiting for a reply too so the incoming node must
288 * be at least as long as this node
289 */
290 incomingNode.update(null) {
291 if (node.start < incomingNode.start) timestamp(node.start)
292 if (node.end > incomingNode.end) timestamp(node.end)
293 }
294 }
295 }
296 }
297
298 if (node.isSynchronous && node.events.size == 1) {
299 // It only started and did nothing else
300 nodesToRemove += node.id
301 }
302 }
303 nodesToRemove.forEach(::remove)
304 }
305 }
306
307 /** Print a warning message to error stream. */
warnnull308 private fun warn(message: String) {
309 System.err.println("W: $message")
310 }
311
312 /** Represents raw graph edges used internally to build proper node edges. */
313 private sealed class InternalEdge {
314 /** Node ID this edge connects to. */
315 abstract val id: Long
316
317 /** The timestamp of the onboarding event that created this edge. */
318 abstract val timestamp: Instant
319 private var nodeProvider: (id: Long) -> NodeBuilder? by Delegates.notNull()
320 private var originId: Long by Delegates.notNull()
321 val node: NodeBuilder
322 get() =
<lambda>null323 checkNotNull(nodeProvider(id)) { "Node[$originId] relies on non-existing outgoing Node[$id]" }
324
325 /** Inject this edge with lazy metadata. */
injectnull326 fun inject(nodeProvider: (id: Long) -> NodeBuilder?, originId: Long) {
327 this.nodeProvider = nodeProvider
328 this.originId = originId
329 }
330
331 data class OutgoingEdge(override val id: Long, override var timestamp: Instant) :
332 InternalEdge(), OnboardingGraphEdge.Outgoing {
333 /**
334 * Open outgoing edge implies that the source is finishing and is not expected to resume later.
335 */
336 val isOpen: Boolean
337 get() = node.incomingEdge is OpenIncomingEdge
338 }
339
340 sealed class IncomingEdge : InternalEdge(), OnboardingGraphEdge.Incoming
341
342 /** The source node of this edge is waiting for result and is expecting to be resumed. */
343 data class OpenIncomingEdge(override val id: Long, override var timestamp: Instant) :
344 IncomingEdge()
345
346 /** The source node of this edge is finished and is not expecting to be resumed. */
347 data class ClosedIncomingEdge(override val id: Long, override var timestamp: Instant) :
348 IncomingEdge()
349 }
350
351 private class NodeBuilder(
352 private val nodeProvider: (id: Long) -> NodeBuilder?,
353 override val id: Long,
354 override val unknown: Boolean,
355 private val estimatedStart: Instant,
356 ) : OnboardingGraphNode {
toStringnull357 override fun toString(): String = identity
358
359 private val defaultName = IOnboardingGraphNode.unknown(id)
360 override var name: String = defaultName
361 private set
362
363 private val unknownComponent = Component(IOnboardingGraphNode.unknownComponent(id))
364 override var component: Component = unknownComponent
365 private set
366
367 override var argument: Any? = null
368 private set
369
370 override var result: Any? = null
371 private set
372
373 override var type = Type.UNKNOWN
374 private set
375
376 private var _start: Instant? = null
377 override val start: Instant
378 get() = _start ?: estimatedStart
379
380 private var tail: Instant? = null
381 private var finish: OnboardingEvent? = null
382
383 private var estimatedEnd: Instant? = null
384 override val end: Instant
385 get() = finish?.timestamp ?: tail ?: estimatedEnd ?: start
386
387 override var outgoingEdges: Set<InternalEdge.OutgoingEdge> = setOf()
388 private set
389
390 override val outgoingEdgesOfValidNodes: Collection<InternalEdge.OutgoingEdge>
391 get() = outgoingEdges.filter { nodeProvider(it.id) != null }
392
393 override var incomingEdge: InternalEdge.IncomingEdge? = null
394 private set
395
396 override var failureReasons: Set<Throwable> = setOf()
397 private set
398
399 override var spawnedEvents: Set<OnboardingGraphLog.OnboardingEventDelegate> = emptySet()
400 private set
401
402 override var relatedEvents: Set<OnboardingGraphLog.OnboardingEventDelegate> = emptySet()
403 private set
404
405 @CanIgnoreReturnValue
updatenull406 inline fun update(
407 event: OnboardingGraphLog.OnboardingEventDelegate?,
408 block: Updater.() -> Unit,
409 ): NodeBuilder {
410 Updater(this, event).apply(block)
411 return this
412 }
413
414 override var issues: Collection<String> = listOf()
415 private set
416
417 /** Print a warning message to error stream and add it to [issues]. */
warnnull418 private fun warn(message: String) {
419 System.err.println("W: $message")
420 issues += message
421 }
422 override val isComplete: Boolean
423 get() = events.size >= 2
424
425 override val pausedRuntime: Duration
426 get() {
427 var total = Duration.ZERO
428 var pause: OnboardingEvent? = null
429 val closures = mutableListOf<OnboardingEvent>()
430 for (event in spawnedEvents.sortedBy(OnboardingGraphLog.OnboardingEventData::timestamp)) {
431 when (val source = event.source) {
432 is OnboardingEvent.ActivityNodeExecutedDirectly -> {
433 if (pause != null) {
434 warn(
435 "Closure event without terminating previous suspend event for $identity: prev=$pause, next=$source"
436 )
437 } else {
438 pause = null
439 closures += source
440 }
441 }
442
443 /**
444 * We don't need to check for [OnboardingEvent.ActivityNodeStartExecuteSynchronously]
445 * since it is always spawned in tandem with
446 * [OnboardingEvent.ActivityNodeExecutedForResult].
447 */
448 is OnboardingEvent.ActivityNodeExecutedForResult -> {
449 if (closures.isNotEmpty()) {
450 warn("New suspend event after closure for $identity: $source")
451 } else if (pause != null) {
452 warn(
453 "New suspend event without terminating previous suspend event for $identity: prev=$pause, next=$source"
454 )
455 } else {
456 pause = source
457 }
458 }
459 is OnboardingEvent.ActivityNodeExecutedSynchronously,
460 is OnboardingEvent.ActivityNodeResultReceived -> {
461 if (closures.isNotEmpty()) {
462 warn("Resume event after closure for $identity: $source")
463 } else if (pause == null) {
464 warn("Resume event without previous suspend event for $identity: $source")
465 } else {
466 if (event.timestamp > end) {
467 warn("Resume event after end time for $identity: end=$end, event=$source")
468 } else {
469 total += Duration.between(pause.timestamp, event.timestamp)
470 }
471 pause = null
472 }
473 }
474 is OnboardingEvent.ActivityNodeStartExecuteSynchronously,
475 is OnboardingEvent.ActivityNodeFinished,
476 is OnboardingEvent.ActivityNodeResumedAfterLaunch,
477 is OnboardingEvent.ActivityNodeResumed,
478 is OnboardingEvent.ActivityNodeFailedValidation,
479 is OnboardingEvent.ActivityNodeFail,
480 is OnboardingEvent.ActivityNodeExtractArgument,
481 is OnboardingEvent.ActivityNodeSetResult,
482 is OnboardingEvent.ActivityNodeValidating,
483 is OnboardingEvent.ActivityNodeArgumentExtracted -> {
484 /* ignore */
485 }
486 }
487 }
488 if (closures.size > 1) {
489 warn("Multiple closure events for $identity: $closures")
490 }
491 return total
492 }
493
494 /**
495 * A helper class to update [NodeBuilder] properties.
496 *
497 * It validates that the properties are not set to different values and that the event is
498 * consistent with the node.
499 */
500 class Updater(val node: NodeBuilder, delegate: OnboardingGraphLog.OnboardingEventDelegate?) {
501 private val event = delegate?.source
502 private val eventRef = event?.toString() ?: ""
<lambda>null503 private val nodeProvider: (Long) -> NodeBuilder? = {
504 node.nodeProvider(event?.safeId(it) ?: it)
505 }
506
namenull507 fun name(value: String?) {
508 if (value != null && value != node.defaultName && value != node.name) {
509 validate(
510 condition = node.name == node.defaultName,
511 onFailure = { "Previously set name '${node.name}' cannot be overridden with '$value'" },
512 ) {
513 node.name = value
514 }
515 }
516 }
517
componentnull518 fun component(value: String?) {
519 if (value != null && value != node.unknownComponent.name && value != node.component.name) {
520 validate(
521 condition = node.component == node.unknownComponent,
522 onFailure = {
523 "Previously set component '${node.component}' cannot be overridden with '$value'"
524 },
525 ) {
526 node.component = Component(value)
527 }
528 }
529 }
530
argumentnull531 fun argument(value: Any?) {
532 validate(
533 condition = node.argument == null || value == node.argument,
534 onFailure = {
535 "Previously set argument '${node.argument}' cannot be overridden with '$value'"
536 },
537 ) {
538 node.argument = value
539 }
540 }
541
resultnull542 fun result(value: Any?) {
543 validate(
544 condition = node.result == null || value == node.result,
545 onFailure = { "Previously set result '${node.result}' cannot be overridden with '$value'" },
546 ) {
547 node.result = value
548 }
549 }
550
typenull551 fun type(value: Type?) {
552 if (value != null && (node.type == Type.UNKNOWN || value == Type.SYNCHRONOUS)) {
553 node.type = value
554 }
555 }
556
timestampnull557 fun timestamp(value: Instant) {
558 val s = node._start
559 if (s == null || value < s) node._start = value
560 val t = node.tail
561 if (t != null && value > t) node.tail = value
562 }
563
finishnull564 fun finish(value: OnboardingEvent.ActivityNodeFinished) {
565 validate(
566 condition = node.finish == null,
567 onFailure = {
568 "Duplicate finish events detected for ${node.identity}! prev=${node.finish}, next=$value"
569 },
570 ) {
571 node.finish =
572 maxOf(
573 a = value,
574 b = node.finish ?: value,
575 comparator = OnboardingGraphLog.OnboardingEventData::compareTo,
576 )
577 }
578 }
579
outgoingEdgesnull580 fun outgoingEdges(vararg values: InternalEdge.OutgoingEdge?) {
581 node.outgoingEdges +=
582 values.filterNotNull().onEach { it.inject(nodeProvider = nodeProvider, originId = node.id) }
583 }
584
incomingEdgenull585 fun incomingEdge(value: InternalEdge.IncomingEdge?) {
586 node.incomingEdge =
587 value?.also { it.inject(nodeProvider = nodeProvider, originId = node.id) }
588 ?: node.incomingEdge
589 }
590
failureReasonsnull591 fun failureReasons(vararg values: Throwable?) {
592 node.failureReasons += values.filterNotNull()
593 }
594
spawnedEventsnull595 fun spawnedEvents(vararg values: OnboardingGraphLog.OnboardingEventDelegate?) {
596 node.spawnedEvents +=
597 values.filterNotNull().onEach {
598 val s = node._start
599 if (s == null || it.timestamp < s) node._start = it.timestamp
600 val t = node.tail
601 if (t == null || it.timestamp > t) node.tail = it.timestamp
602 }
603 }
604
relatedEventsnull605 fun relatedEvents(vararg values: OnboardingGraphLog.OnboardingEventDelegate?) {
606 node.relatedEvents +=
607 values.filterNotNull().onEach {
608 val ee = node.estimatedEnd
609 if (ee == null || ee < it.timestamp) node.estimatedEnd = it.timestamp
610 }
611 }
612
validatenull613 private inline fun validate(
614 condition: Boolean,
615 onFailure: () -> String,
616 onSuccess: () -> Unit,
617 ) {
618 if (!condition) {
619 val failure = onFailure()
620 warn("$failure ${node.identity} $eventRef")
621 } else {
622 onSuccess()
623 }
624 }
625 }
626 }
627
628 private const val UNKNOWN_NODE_ID = -1L
629
630 /** Returns [original] or generated id from this event if [original] is [UNKNOWN_NODE_ID]. */
OnboardingGraphLognull631 private fun OnboardingGraphLog.OnboardingEventDelegate.safeId(original: Long = nodeId): Long =
632 if (original == UNKNOWN_NODE_ID) {
633 val id = "${source.nodeComponent}/${source.nodeName}".hashCode().toLong().absoluteValue
634 warn("Unknown node referenced, generating local id=$id $source")
635 id
636 } else {
637 original
638 }
639
640 /** Get an existing [NodeBuilder] or a new stub for [id] and [event]. */
nodenull641 private inline fun MutableMap<Long, NodeBuilder>.node(
642 id: Long,
643 event: OnboardingGraphLog.OnboardingEventDelegate,
644 onStub: (nodeId: Long) -> Unit = {},
645 update: NodeBuilder.Updater.() -> Unit,
646 ): NodeBuilder {
647 val newId = event.safeId(id)
<lambda>null648 return getOrPut(newId) {
649 onStub(newId)
650 NodeBuilder(
651 nodeProvider = { get(it) },
652 id = newId,
653 unknown = newId != id,
654 estimatedStart = event.timestamp,
655 )
656 }
657 .update(event, update)
658 }
659
660 /** Get a [NodeBuilder] for [id] and [event] spawned by this node. */
spawnNodenull661 private inline fun MutableMap<Long, NodeBuilder>.spawnNode(
662 id: Long,
663 event: OnboardingGraphLog.OnboardingEventDelegate,
664 update: NodeBuilder.Updater.() -> Unit = {},
665 ): NodeBuilder =
<lambda>null666 node(id, event) {
667 spawnedEvents(event)
668 update()
669 }
670