xref: /compose/runtime/runtime/src/commonMain/kotlin/androidx/compose/runtime/Applier.kt

/*
 * Copyright 2019 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.
 */

package androidx.compose.runtime

import androidx.compose.runtime.internal.JvmDefaultWithCompatibility

/**
 * An Applier is responsible for applying the tree-based operations that get emitted during a
 * composition. Every [Composer] has an [Applier] which it uses to emit a [ComposeNode].
 *
 * A custom [Applier] implementation will be needed in order to utilize Compose to build and
 * maintain a tree of a novel type.
 *
 * @sample androidx.compose.runtime.samples.CustomTreeComposition
 * @see AbstractApplier
 * @see Composition
 * @see Composer
 * @see ComposeNode
 */
@JvmDefaultWithCompatibility
interface Applier<N> {
    /**
     * The node that operations will be applied on at any given time. It is expected that the value
     * of this property will change as [down] and [up] are called.
     */
    val current: N

    /**
     * Called when the [Composer] is about to begin applying changes using this applier.
     * [onEndChanges] will be called when changes are complete.
     */
    fun onBeginChanges() {}

    /**
     * Called when the [Composer] is finished applying changes using this applier. A call to
     * [onBeginChanges] will always precede a call to [onEndChanges].
     */
    fun onEndChanges() {}

    /**
     * Indicates that the applier is getting traversed "down" the tree. When this gets called,
     * [node] is expected to be a child of [current], and after this operation, [node] is expected
     * to be the new [current].
     */
    fun down(node: N)

    /**
     * Indicates that the applier is getting traversed "up" the tree. After this operation
     * completes, the [current] should return the "parent" of the [current] node at the beginning of
     * this operation.
     */
    fun up()

    /**
     * Indicates that [instance] should be inserted as a child to [current] at [index]. An applier
     * should insert the node into the tree either in [insertTopDown] or [insertBottomUp], not both.
     *
     * The [insertTopDown] method is called before the children of [instance] have been created and
     * inserted into it. [insertBottomUp] is called after all children have been created and
     * inserted.
     *
     * Some trees are faster to build top-down, in which case the [insertTopDown] method should be
     * used to insert the [instance]. Other trees are faster to build bottom-up in which case
     * [insertBottomUp] should be used.
     *
     * To give example of building a tree top-down vs. bottom-up consider the following tree,
     * ```
     *      R
     *      |
     *      B
     *     / \
     *    A   C
     *  ```
     *
     * where the node `B` is being inserted into the tree at `R`. Top-down building of the tree
     * first inserts `B` into `R`, then inserts `A` into `B` followed by inserting `C` into B`. For
     * example,
     *
     *  ```
     *      1           2           3
     *      R           R           R
     *      |           |           |
     *      B           B           B
     *                 /           / \
     *                A           A   C
     * ```
     *
     * A bottom-up building of the tree starts with inserting `A` and `C` into `B` then inserts `B`
     * tree into `R`.
     *
     * ```
     *    1           2           3
     *    B           B           R
     *    |          / \          |
     *    A         A   C         B
     *                           / \
     *                          A   C
     * ```
     *
     * To see how building top-down vs. bottom-up can differ significantly in performance consider a
     * tree where whenever a child is added to the tree all parent nodes, up to the root, are
     * notified of the new child entering the tree. If the tree is built top-down,
     * 1. `R` is notified of `B` entering.
     * 2. `B` is notified of `A` entering, `R` is notified of `A` entering.
     * 3. `B` is notified of `C` entering, `R` is notified of `C` entering.
     *
     * for a total of 5 notifications. The number of notifications grows exponentially with the
     * number of inserts.
     *
     * For bottom-up, the notifications are,
     * 1. `B` is notified `A` entering.
     * 2. `B` is notified `C` entering.
     * 3. `R` is notified `B` entering.
     *
     * The notifications are linear to the number of nodes inserted.
     *
     * If, on the other hand, all children are notified when the parent enters a tree, then the
     * notifications are, for top-down,
     * 1. `B` is notified it is entering `R`.
     * 2. `A` is notified it is entering `B`.
     * 3. `C` is notified it is entering `B`.
     *
     * which is linear to the number of nodes inserted.
     *
     * For bottom-up, the notifications look like,
     * 1. `A` is notified it is entering `B`.
     * 2. `C` is notified it is entering `B`.
     * 3. `B` is notified it is entering `R`, `A` is notified it is entering `R`, `C` is notified it
     *    is entering `R`.
     *
     *    which exponential to the number of nodes inserted.
     */
    fun insertTopDown(index: Int, instance: N)

    /**
     * Indicates that [instance] should be inserted as a child of [current] at [index]. An applier
     * should insert the node into the tree either in [insertTopDown] or [insertBottomUp], not both.
     * See the description of [insertTopDown] to which describes when to implement [insertTopDown]
     * and when to use [insertBottomUp].
     */
    fun insertBottomUp(index: Int, instance: N)

    /**
     * Indicates that the children of [current] from [index] to [index] + [count] should be removed.
     */
    fun remove(index: Int, count: Int)

    /**
     * Indicates that [count] children of [current] should be moved from index [from] to index [to].
     *
     * The [to] index is relative to the position before the change, so, for example, to move an
     * element at position 1 to after the element at position 2, [from] should be `1` and [to]
     * should be `3`. If the elements were A B C D E, calling `move(1, 3, 1)` would result in the
     * elements being reordered to A C B D E.
     */
    fun move(from: Int, to: Int, count: Int)

    /**
     * Move to the root and remove all nodes from the root, preparing both this [Applier] and its
     * root to be used as the target of a new composition in the future.
     */
    fun clear()

    /** Apply a change to the current node. */
    fun apply(block: N.(Any?) -> Unit, value: Any?) {
        current.block(value)
    }

    /** Notify [current] is is being reused in reusable content. */
    fun reuse() {
        (current as? ComposeNodeLifecycleCallback)?.onReuse()
    }
}

/**
 * An abstract [Applier] implementation.
 *
 * @sample androidx.compose.runtime.samples.CustomTreeComposition
 * @see Applier
 * @see Composition
 * @see Composer
 * @see ComposeNode
 */
abstract class AbstractApplier<T>(val root: T) : Applier<T> {
    private val stack = Stack<T>()

    override var current: T = root
        protected set

    override fun down(node: T) {
        stack.push(current)
        current = node
    }

    override fun up() {
        current = stack.pop()
    }

    final override fun clear() {
        stack.clear()
        current = root
        onClear()
    }

    /** Called to perform clearing of the [root] when [clear] is called. */
    protected abstract fun onClear()

    protected fun MutableList<T>.remove(index: Int, count: Int) {
        if (count == 1) {
            removeAt(index)
        } else {
            subList(index, index + count).clear()
        }
    }

    protected fun MutableList<T>.move(from: Int, to: Int, count: Int) {
        val dest = if (from > to) to else to - count
        if (count == 1) {
            if (from == to + 1 || from == to - 1) {
                // Adjacent elements, perform swap to avoid backing array manipulations.
                val fromEl = get(from)
                val toEl = set(to, fromEl)
                set(from, toEl)
            } else {
                val fromEl = removeAt(from)
                add(dest, fromEl)
            }
        } else {
            val subView = subList(from, from + count)
            val subCopy = subView.toMutableList()
            subView.clear()
            addAll(dest, subCopy)
        }
    }
}

internal class OffsetApplier<N>(private val applier: Applier<N>, private val offset: Int) :
    Applier<N> {
    private var nesting = 0
    override val current: N
        get() = applier.current

    override fun down(node: N) {
        nesting++
        applier.down(node)
    }

    override fun up() {
        runtimeCheck(nesting > 0) { "OffsetApplier up called with no corresponding down" }
        nesting--
        applier.up()
    }

    override fun insertTopDown(index: Int, instance: N) {
        applier.insertTopDown(index + if (nesting == 0) offset else 0, instance)
    }

    override fun insertBottomUp(index: Int, instance: N) {
        applier.insertBottomUp(index + if (nesting == 0) offset else 0, instance)
    }

    override fun remove(index: Int, count: Int) {
        applier.remove(index + if (nesting == 0) offset else 0, count)
    }

    override fun move(from: Int, to: Int, count: Int) {
        val effectiveOffset = if (nesting == 0) offset else 0
        applier.move(from + effectiveOffset, to + effectiveOffset, count)
    }

    override fun clear() {
        composeImmediateRuntimeError("Clear is not valid on OffsetApplier")
    }
}