/* * Copyright 2022 The Android Open Source Project * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ @file:OptIn(ExperimentalComposeUiApi::class) package androidx.compose.ui.node import androidx.compose.runtime.collection.MutableVector import androidx.compose.runtime.collection.mutableVectorOf import androidx.compose.ui.CombinedModifier import androidx.compose.ui.ExperimentalComposeUiApi import androidx.compose.ui.Modifier import androidx.compose.ui.areObjectsOfSameType import androidx.compose.ui.layout.ModifierInfo private val SentinelHead = object : Modifier.Node() { override fun toString() = "" } internal class NodeChain(val layoutNode: LayoutNode) { internal val innerCoordinator = InnerNodeCoordinator(layoutNode) internal var outerCoordinator: NodeCoordinator = innerCoordinator private set internal val tail: Modifier.Node = innerCoordinator.tail internal var head: Modifier.Node = tail private set private val isUpdating: Boolean get() = head === SentinelHead private val aggregateChildKindSet: Long get() = head.aggregateChildKindSet private var current: MutableVector? = null private var buffer: MutableVector? = null private var cachedDiffer: Differ? = null private var logger: Logger? = null internal fun useLogger(logger: Logger?) { this.logger = logger } private fun padChain() { check(head !== SentinelHead) val currentHead = head currentHead.parent = SentinelHead SentinelHead.child = currentHead head = SentinelHead } private fun trimChain() { check(head === SentinelHead) head = SentinelHead.child ?: tail head.parent = null SentinelHead.child = null check(head !== SentinelHead) } /** * This method will update the node chain based on the provided modifier chain. This method is * responsible for calling all appropriate lifecycles for nodes that are * created/disposed/updated during this call. * * This method will attempt to optimize for the common scenario of the modifier chain being of * equal size and each element being able to be reused from the prior one. In most cases this * is what recomposition will result in, provided modifiers weren't conditionally provided. In * the cases where the modifier is not of equal length to the prior value, or modifiers of * different reuse types ended up in the same position, this method will deopt into a slower * path which will perform a diff on the modifier chain and execute a minimal number of * insertions and deletions. */ internal fun updateFrom(m: Modifier) { // If we run the diff and there are no new nodes created, then we don't need to loop through // and run the attach cycle on them. We simply keep track of this during the diff to avoid // this overhead at the end if we can, since it should be fairly common. var attachNeeded = false // If we run the diff and there are no structural changes, we can avoid looping through the // list and updating the coordinators. We simply keep track of this during the diff to avoid // this overhead at the end if we can, since it should be fairly common. Note that this is // slightly different from [attachNeeded] since a node can be updated and return null or a // new instance which is perfectly valid and would require a new attach cycle, however the // coordinator would be identical and so [attachNeeded] would be true but this false var coordinatorSyncNeeded = false // Use the node chain itself as a head/tail temporarily to prevent pruning the linkedlist // to the point where we don't have reference to it. We need to undo this at the end of // this method. padChain() // to avoid allocating vectors every time modifier is set, we have two vectors that we // reuse over time. Since the common case is the modifier chains will be of equal length, // these vectors should be sized appropriately val before = current ?: mutableVectorOf() val after = m.fillVector(buffer ?: mutableVectorOf()) if (after.size == before.size) { // assume if the sizes are the same, that we are in a common case of no structural // changes we will attempt an O(n) fast-path diff and exit if a diff is detected, and // do the O(N^2) diff beyond that point val size = before.size // for the linear diff we want to start with the "unpadded" tail var node: Modifier.Node? = tail.parent var i = size - 1 var aggregateChildKindSet = 0L while (node != null && i >= 0) { val prev = before[i] val next = after[i] when (reuseActionForModifiers(prev, next)) { ActionReplace -> { // TODO(lmr): we could avoid running the diff if i = 0, since that would // always be simple remove + insert // structural change! // back up one for the structural diff algorithm. This should be safe since // our chain is padded with the EmptyHead/EmptyTail nodes logger?.linearDiffAborted(i, prev, next, node) i++ node = node.child break } ActionUpdate -> { // this is "the same" modifier, but some things have changed so we want to // reuse the node but also update it val beforeUpdate = node node = updateNodeAndReplaceIfNeeded(prev, next, beforeUpdate) // if the node is new, we need to run attach on it attachNeeded = attachNeeded || beforeUpdate !== node logger?.nodeUpdated(i, i, prev, next, beforeUpdate, node) } ActionReuse -> { logger?.nodeReused(i, i, prev, next, node) // no need to do anything, this is "the same" modifier } } i-- aggregateChildKindSet = aggregateChildKindSet or node.kindSet node.aggregateChildKindSet = aggregateChildKindSet node = node.parent } if (i > 0) { check(node != null) attachNeeded = true coordinatorSyncNeeded = true // there must have been a structural change // we only need to diff what is left of the list, so we use `i` as the "beforeSize" // and "afterSize" structuralUpdate( before, i, after, i, // its important that the node we pass in here has an accurate // "aggregateChildMask" node, ) } } else if (before.size == 0) { // common case where we are initializing the chain and the previous size is zero. In // this case we just do all inserts. Since this is so common, we add a fast path here // for this condition. attachNeeded = true coordinatorSyncNeeded = true var i = after.size - 1 var aggregateChildKindSet = 0L var node = tail while (i >= 0) { val next = after[i] val child = node node = createAndInsertNodeAsParent(next, child) logger?.nodeInserted(0, i, next, child, node) aggregateChildKindSet = aggregateChildKindSet or node.kindSet node.aggregateChildKindSet = aggregateChildKindSet i-- } } else { attachNeeded = true coordinatorSyncNeeded = true structuralUpdate( before, before.size, after, after.size, tail, ) } current = after // clear the before vector to allow old modifiers to be Garbage Collected buffer = before.also { it.clear() } trimChain() if (coordinatorSyncNeeded) { syncCoordinators() } if (attachNeeded && layoutNode.isAttached) { attach() } } private fun syncCoordinators() { var coordinator: NodeCoordinator = innerCoordinator var node: Modifier.Node? = tail.parent while (node != null) { if (node.isKind(Nodes.Layout) && node is LayoutModifierNode) { val next = if (node.isAttached) { val c = node.coordinator as LayoutModifierNodeCoordinator val prevNode = c.layoutModifierNode c.layoutModifierNode = node if (prevNode !== node) c.onLayoutModifierNodeChanged() c } else { val c = LayoutModifierNodeCoordinator(layoutNode, node) node.updateCoordinator(c) c } coordinator.wrappedBy = next next.wrapped = coordinator coordinator = next } else { node.updateCoordinator(coordinator) } node = node.parent } coordinator.wrappedBy = layoutNode.parent?.innerCoordinator outerCoordinator = coordinator } fun attach() { headToTail { if (!it.isAttached) it.attach() } } /** * This returns a new List of Modifiers and the coordinates and any extra information * that may be useful. This is used for tooling to retrieve layout modifier and layer * information. */ fun getModifierInfo(): List { val current = current ?: return listOf() val infoList = MutableVector(current.size) var i = 0 headToTailExclusive { node -> val coordinator = requireNotNull(node.coordinator) infoList += ModifierInfo(current[i++], coordinator, coordinator.layer) } return infoList.asMutableList() } internal fun detach() { // NOTE(lmr): Currently this implementation allows for nodes to be // attached/detached/attached. We need to decide if that's what we want. If we // don't, the commented out implementation below it might be better. tailToHead { if (it.isAttached) it.detach() } // tailToHead { // if (it.isAttached) it.detach() // it.child?.parent = null // it.child = null // } // current?.clear() } private fun getDiffer( tail: Modifier.Node, before: MutableVector, after: MutableVector, ): Differ { val current = cachedDiffer @Suppress("IfThenToElvis") return if (current == null) { Differ( tail, tail.aggregateChildKindSet, before, after, ).also { cachedDiffer = it } } else { current.also { it.node = tail it.aggregateChildKindSet = tail.aggregateChildKindSet it.before = before it.after = after } } } private inner class Differ( var node: Modifier.Node, var aggregateChildKindSet: Long, var before: MutableVector, var after: MutableVector, ) : DiffCallback { override fun areItemsTheSame(oldIndex: Int, newIndex: Int): Boolean { return reuseActionForModifiers(before[oldIndex], after[newIndex]) != ActionReplace } override fun insert(atIndex: Int, newIndex: Int) { val child = node node = createAndInsertNodeAsParent(after[newIndex], child) logger?.nodeInserted(atIndex, newIndex, after[newIndex], child, node) aggregateChildKindSet = aggregateChildKindSet or node.kindSet node.aggregateChildKindSet = aggregateChildKindSet } override fun remove(oldIndex: Int) { node = node.parent!! logger?.nodeRemoved(oldIndex, before[oldIndex], node) node = disposeAndRemoveNode(node) } override fun same(oldIndex: Int, newIndex: Int) { node = node.parent!! val prev = before[oldIndex] val next = after[newIndex] if (prev != next) { val beforeUpdate = node node = updateNodeAndReplaceIfNeeded(prev, next, beforeUpdate) logger?.nodeUpdated(oldIndex, newIndex, prev, next, beforeUpdate, node) } else { logger?.nodeReused(oldIndex, newIndex, prev, next, node) } aggregateChildKindSet = aggregateChildKindSet or node.kindSet node.aggregateChildKindSet = aggregateChildKindSet } } internal interface Logger { fun linearDiffAborted( index: Int, prev: Modifier.Element, next: Modifier.Element, node: Modifier.Node ) fun nodeUpdated( oldIndex: Int, newIndex: Int, prev: Modifier.Element, next: Modifier.Element, before: Modifier.Node, after: Modifier.Node ) fun nodeReused( oldIndex: Int, newIndex: Int, prev: Modifier.Element, next: Modifier.Element, node: Modifier.Node ) fun nodeInserted( atIndex: Int, newIndex: Int, element: Modifier.Element, child: Modifier.Node, inserted: Modifier.Node ) fun nodeRemoved( oldIndex: Int, element: Modifier.Element, node: Modifier.Node ) } /** * This method utilizes a modified Myers Diff Algorithm which will diff the two modifier chains * and execute a minimal number of insertions/deletions. We make no attempt to execute "moves" * as part of this diff. If a modifier moves that is no different than it being inserted in * the new location and removed in the old location. * * @param tail - The Node that corresponds to the _end_ of the [before] list. This Node is * expected to have an up to date [aggregateChildKindSet]. */ private fun structuralUpdate( before: MutableVector, beforeSize: Int, after: MutableVector, afterSize: Int, tail: Modifier.Node, ) { executeDiff(beforeSize, afterSize, getDiffer(tail, before, after)) } /** * This method takes [prev] in the current linked list, and swaps it with [next], ensuring that * all the parent/child relationships are maintained. * * For example: * * Head... -> parent -> prev -> child -> ...Tail * * gets transformed into a list of the following shape: * * Head... -> parent -> next -> child -> ...Tail * * @return This method returns the updated [next] node, for convenience */ private fun replaceNode(prev: Modifier.Node, next: Modifier.Node): Modifier.Node { val parent = prev.parent if (parent != null) { next.parent = parent parent.child = next prev.parent = null } val child = prev.child if (child != null) { next.child = child child.parent = next prev.child = null } // NOTE: it is important that during a "replace", we keep the same coordinator as before // as there is a chance that at the end of the diff we won't iterate through the chain and // update all of the coordinators assuming there were no structural changes detected next.updateCoordinator(prev.coordinator) return next } private fun disposeAndRemoveNode(node: Modifier.Node): Modifier.Node { if (node.isAttached) node.detach() return removeNode(node) } /** * This removes [node] from the current linked list. * For example: * * Head... -> parent -> node -> child -> ...Tail * * gets transformed into a list of the following shape: * * Head... -> parent -> child -> ...Tail * * @return The child of the removed [node] */ private fun removeNode(node: Modifier.Node): Modifier.Node { val child = node.child val parent = node.parent if (child != null) { child.parent = parent node.child = null } if (parent != null) { parent.child = child node.parent = null } return child!! } private fun createAndInsertNodeAsParent( element: Modifier.Element, child: Modifier.Node, ): Modifier.Node { val node = if (element is ModifierNodeElement<*>) { element.create().also { it.kindSet = calculateNodeKindSetFrom(it) } } else { BackwardsCompatNode(element) } return insertParent(node, child) } /** * This inserts [node] as the parent of [child] in the current linked list. * For example: * * Head... -> child -> ...Tail * * gets transformed into a list of the following shape: * * Head... -> node -> child -> ...Tail * * @return The inserted [node] */ private fun insertParent(node: Modifier.Node, child: Modifier.Node): Modifier.Node { val theParent = child.parent if (theParent != null) { theParent.child = node node.parent = theParent } child.parent = node node.child = child return node } private fun updateNodeAndReplaceIfNeeded( prev: Modifier.Element, next: Modifier.Element, node: Modifier.Node, ): Modifier.Node { if (prev !is ModifierNodeElement<*> || next !is ModifierNodeElement<*>) { check(node is BackwardsCompatNode) node.element = next return node } val updated = next.updateUnsafe(node) val result = if (updated !== node) { // if a new instance is returned, we want to detach the old one node.detach() replaceNode(node, updated) } else { // the node was updated. we are done. updated } return result } // TRAVERSAL internal inline fun firstFromHead( type: NodeKind, block: (T) -> Boolean ): T? { headToTail(type) { if (block(it)) return it } return null } internal inline fun headToTail(type: NodeKind, block: (T) -> Unit) { headToTail(type.mask) { if (it is T) block(it) } } internal inline fun headToTail(mask: Long, block: (Modifier.Node) -> Unit) { if (aggregateChildKindSet and mask == 0L) return headToTail { if (it.kindSet and mask != 0L) { block(it) } if (it.aggregateChildKindSet and mask == 0L) return } } /** * Traverses the linked list from head to tail, running [block] on each Node as it goes. If * [block] returns true, it will stop traversing and return true. If [block] returns false, * it will continue. * * @return Returns true if [block] ever returned true, false otherwise. */ internal inline fun headToTail(block: (Modifier.Node) -> Unit) { var node: Modifier.Node? = head while (node != null) { block(node) node = node.child } } internal inline fun headToTailExclusive(block: (Modifier.Node) -> Unit) { var node: Modifier.Node? = head while (node != null && node !== tail) { block(node) node = node.child } } internal inline fun tailToHead(type: NodeKind, block: (T) -> Unit) { tailToHead(type.mask) { if (it is T) block(it) } } internal inline fun tailToHead(mask: Long, block: (Modifier.Node) -> Unit) { if (aggregateChildKindSet and mask == 0L) return tailToHead { if (it.kindSet and mask != 0L) { block(it) } } } internal inline fun tailToHead(block: (Modifier.Node) -> Unit) { var node: Modifier.Node? = tail while (node != null) { block(node) node = node.parent } } internal inline fun tail(type: NodeKind): T? { tailToHead(type) { return it } return null } internal inline fun head(type: NodeKind): T? { headToTail(type) { return it } return null } internal fun has(type: NodeKind<*>): Boolean = aggregateChildKindSet and type.mask != 0L override fun toString(): String = buildString { append("[") if (head === tail) { append("]") return@buildString } headToTailExclusive { append("$it") if (it.child === tail) { append("]") return@buildString } append(",") } } } private const val ActionReplace = 0 private const val ActionUpdate = 1 private const val ActionReuse = 2 /** * Here's the rules for reusing nodes for different modifiers: * 1. if modifiers are equals, we REUSE but NOT UPDATE * 2. if modifiers are same class, we REUSE and UPDATE * 3. else REPLACE (NO REUSE, NO UPDATE) */ internal fun reuseActionForModifiers(prev: Modifier.Element, next: Modifier.Element): Int { return if (prev == next) ActionReuse else if (areObjectsOfSameType(prev, next)) ActionUpdate else ActionReplace } private fun ModifierNodeElement.updateUnsafe( node: Modifier.Node ): Modifier.Node { @Suppress("UNCHECKED_CAST") return update(node as T) } private fun Modifier.fillVector( result: MutableVector ): MutableVector { val stack = MutableVector(result.size).also { it.add(this) } while (stack.isNotEmpty()) { when (val next = stack.removeAt(stack.size - 1)) { is CombinedModifier -> { stack.add(next.inner) stack.add(next.outer) } is Modifier.Element -> result.add(next) // some other androidx.compose.ui.node.Modifier implementation that we don't know about... else -> next.all { result.add(it) true } } } return result }