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 tress 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()
}

/**
 * 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 = mutableListOf<T>()
    override var current: T = root
        protected set

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

    override fun up() {
        check(stack.isNotEmpty())
        current = stack.removeAt(stack.size - 1)
    }

    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() {
        runtimeCheck(false) { "Clear is not valid on OffsetApplier" }
    }
}