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

@file:OptIn(
    InternalComposeApi::class,
    ExperimentalComposeApi::class,
    ComposeCompilerApi::class
)
package androidx.compose

import androidx.compose.SlotTable.Companion.EMPTY
import androidx.compose.tooling.InspectionTables

internal typealias Change<N> = (
    applier: Applier<N>,
    slots: SlotWriter,
    lifecycleManager: LifecycleManager
) -> Unit

private class GroupInfo(
    /**
     * The current location of the slot relative to the start location of the pending slot changes
     */
    var slotIndex: Int,

    /**
     * The current location of the first node relative the start location of the pending node
     * changes
     */
    var nodeIndex: Int,

    /**
     * The current number of nodes the group contains after changes have been applied
     */
    var nodeCount: Int
)

internal interface LifecycleManager {
    fun entering(instance: CompositionLifecycleObserver)
    fun leaving(instance: CompositionLifecycleObserver)
}

/**
 * Pending starts when the key is different than expected indicating that the structure of the tree
 * changed. It is used to determine how to update the nodes and the slot table when changes to the
 * structure of the tree is detected.
 */
private class Pending(
    val keyInfos: MutableList<KeyInfo>,
    val startIndex: Int
) {
    var groupIndex: Int = 0

    init {
        require(startIndex >= 0) { "Invalid start index" }
    }

    private val usedKeys = mutableListOf<KeyInfo>()
    private val groupInfos = run {
        var runningNodeIndex = 0
        val result = hashMapOf<Group, GroupInfo>()
        for (index in 0 until keyInfos.size) {
            val keyInfo = keyInfos[index]
            result[keyInfo.group] = GroupInfo(index, runningNodeIndex, keyInfo.nodes)
            runningNodeIndex += keyInfo.nodes
        }
        result
    }

    /**
     * A multi-map of keys from the previous composition. The keys can be retrieved in the order
     * they were generated by the previous composition.
     */
    val keyMap by lazy {
        multiMap<Any, KeyInfo>().also {
            for (index in 0 until keyInfos.size) {
                val keyInfo = keyInfos[index]
                @Suppress("ReplacePutWithAssignment")
                it.put(keyInfo.joinedKey, keyInfo)
            }
        }
    }

    /**
     * Get the next key information for the given key.
     */
    fun getNext(key: Int, dataKey: Any?): KeyInfo? {
        val joinedKey: Any = if (dataKey != null) JoinedKey(key, dataKey) else key
        return keyMap.pop(joinedKey)
    }

    /**
     * Record that this key info was generated.
     */
    fun recordUsed(keyInfo: KeyInfo) = usedKeys.add(keyInfo)

    val used: List<KeyInfo> get() = usedKeys

    // TODO(chuckj): This is a correct but expensive implementation (worst cases of O(N^2)). Rework
    // to O(N)
    fun registerMoveSlot(from: Int, to: Int) {
        if (from > to) {
            groupInfos.values.forEach { group ->
                val position = group.slotIndex
                if (position == from) group.slotIndex = to
                else if (position in to until from) group.slotIndex = position + 1
            }
        } else if (to > from) {
            groupInfos.values.forEach { group ->
                val position = group.slotIndex
                if (position == from) group.slotIndex = to
                else if (position in (from + 1) until to) group.slotIndex = position - 1
            }
        }
    }

    fun registerMoveNode(from: Int, to: Int, count: Int) {
        if (from > to) {
            groupInfos.values.forEach { group ->
                val position = group.nodeIndex
                if (position in from until from + count) group.nodeIndex = to + (position - from)
                else if (position in to until from) group.nodeIndex = position + count
            }
        } else if (to > from) {
            groupInfos.values.forEach { group ->
                val position = group.nodeIndex
                if (position in from until from + count) group.nodeIndex = to + (position - from)
                else if (position in (from + 1) until to) group.nodeIndex = position - count
            }
        }
    }

    fun registerInsert(keyInfo: KeyInfo, insertIndex: Int) {
        groupInfos[keyInfo.group] = GroupInfo(-1, insertIndex, 0)
    }

    fun updateNodeCount(group: Group, newCount: Int): Boolean {
        val groupInfo = groupInfos[group]
        if (groupInfo != null) {
            val index = groupInfo.nodeIndex
            val difference = newCount - groupInfo.nodeCount
            groupInfo.nodeCount = newCount
            if (difference != 0) {
                groupInfos.values.forEach { childGroupInfo ->
                    if (childGroupInfo.nodeIndex >= index && childGroupInfo != groupInfo)
                        childGroupInfo.nodeIndex += difference
                }
            }
            return true
        }
        return false
    }

    fun slotPositionOf(keyInfo: KeyInfo) = groupInfos[keyInfo.group]?.slotIndex ?: -1
    fun nodePositionOf(keyInfo: KeyInfo) = groupInfos[keyInfo.group]?.nodeIndex ?: -1
    fun updatedNodeCountOf(keyInfo: KeyInfo) = groupInfos[keyInfo.group]?.nodeCount ?: keyInfo.nodes
}

private class Invalidation(
    val scope: RecomposeScope,
    var location: Int
)

@ComposeCompilerApi
interface ScopeUpdateScope {
    fun updateScope(block: (Composer<*>, Int, Int) -> Unit)
}

internal enum class InvalidationResult {
    /**
     * The invalidation was ignored because the associated recompose scope is no longer part of the
     * composition or has yet to be entered in the composition. This could occur for invalidations
     * called on scopes that are no longer part of composition or if the scope was invalidated
     * before the applyChanges() was called that will enter the scope into the composition.
     */
    IGNORED,

    /**
     * The composition is not currently composing and the invalidation was recorded for a future
     * composition. A recomposition requested to be scheduled.
     */
    SCHEDULED,

    /**
     * The composition that owns the recompose scope is actively composing but the scope has
     * already been composed or is in the process of composing. The invalidation is treated as
     * SCHEDULED above.
     */
    DEFERRED,

    /**
     * The composition that owns the recompose scope is actively composing and the invalidated
     * scope has not been composed yet but will be recomposed before the composition completes. A
     * new recomposition was not scheduled for this invalidation.
     */
    IMMINENT
}

/**
 * A RecomposeScope is created for a region of the composition that can be recomposed independently
 * of the rest of the composition. The composer will position the slot table to the location
 * stored in [anchor] and call [block] when recomposition is requested. It is created by
 * [Composer.startRestartGroup] and is used to track how to restart the group.
 */
internal class RecomposeScope(var composer: Composer<*>?, val key: Int) : ScopeUpdateScope {
    /**
     * An anchor to the location in the slot table that start the group associated with this
     * recompose scope. This value is set by [composer] when the scope is committed to the slot
     * table by [Composer.applyChanges].
     */
    var anchor: Anchor? = null

    /**
     * Return whether the scope is valid. A scope becomes invalid when the slots it updates are
     * removed from the slot table. For example, if the scope is in the then clause of an if
     * statement that later becomes false.
     */
    val valid: Boolean get() = composer != null && anchor?.valid ?: false

    /**
     * Used is set when the [RecomposeScope] is used by, for example, [invalidate]. This is used
     * as the result of [Composer.endRestartGroup] and indicates whether the lambda that is stored
     * in [block] will be used.
     */
    var used = false

    var defaultsInScope = false
    var defaultsInvalid = false

    var requiresRecompose = false

    /**
     * The lambda to call to restart the scopes composition.
     */
    private var block: ((Composer<*>, Int, Int) -> Unit)? = null

    /**
     * Restart the scope's composition. It is an error if [block] was not updated. The code
     * generated by the compiler ensures that when the recompose scope is used then [block] will
     * be set but if might occur if the compiler is out-of-date (or ahead of the runtime) or
     * incorrect direct calls to [Composer.startRestartGroup] and [Composer.endRestartGroup].
     */
    fun <N> compose(composer: Composer<N>) {
        block?.invoke(composer, key, 1) ?: error("Invalid restart scope")
    }

    /**
     * Invalidate the group which will cause [composer] to request this scope be recomposed.
     */
    fun invalidate(): InvalidationResult = composer?.invalidate(this) ?: InvalidationResult.IGNORED

    /**
     * Update [block]. The scope is returned by [Composer.endRestartGroup] when [used] is true
     * and implements [ScopeUpdateScope].
     */
    override fun updateScope(block: (Composer<*>, Int, Int) -> Unit) { this.block = block }
}

/**
 * An instance to hold a value provided by [Providers] and is created by the
 * [ProvidableAmbient.provides] infixed operator.
 */
class ProvidedValue<T> internal constructor(val ambient: Ambient<T>, val value: T)

/**
 * An ambient map is is an immutable map that maps ambient keys to a provider of their current
 * value. It is used both to represent the values provided by a [Providers] call and the combined
 * scope of all provided ambients.
 */
internal typealias AmbientMap = BuildableMap<Ambient<Any?>, State<Any?>>

@Suppress("UNCHECKED_CAST")
internal fun <T> AmbientMap.contains(key: Ambient<T>) = this.containsKey(key as Ambient<Any?>)

@Suppress("UNCHECKED_CAST")
internal fun <T> AmbientMap.getValueOf(key: Ambient<T>) = this[key as Ambient<Any?>]?.value as T

@Composable
private fun ambientMapOf(values: Array<out ProvidedValue<*>>): AmbientMap {
    val result: AmbientMap = buildableMapOf()
    return result.mutate {
        for (provided in values) {
            @Suppress("UNCHECKED_CAST")
            it[provided.ambient as Ambient<Any?>] = provided.ambient.provided(provided.value)
        }
    }
}

/**
 * Implementation of a composer for mutable tree.
 */
class Composer<N>(
    /**
     * Backing storage for the composition
     */
    val slotTable: SlotTable,

    /**
     * An adapter that applies changes to the tree using the Applier abstraction.
     */
    @ComposeCompilerApi
    val applier: Applier<N>,

    /**
     * Manager for scheduling recompositions.
     */
    @ExperimentalComposeApi
    val recomposer: Recomposer
) {
    init {
        FrameManager.ensureStarted()
    }
    private val changes = mutableListOf<Change<N>>()
    private val lifecycleObservers = HashMap<
        CompositionLifecycleObserverHolder,
        CompositionLifecycleObserverHolder
    >()
    private val pendingStack = Stack<Pending?>()
    private var pending: Pending? = null
    private var nodeIndex: Int = 0
    private var nodeIndexStack = IntStack()
    private var groupNodeCount: Int = 0
    private var groupNodeCountStack = IntStack()
    private val nodeCountOverrides = HashMap<Group, Int>()
    private var collectKeySources = false

    private var nodeExpected = false
    private val invalidations: MutableList<Invalidation> = mutableListOf()
    private val entersStack = IntStack()
    private var parentProvider: AmbientMap = buildableMapOf()
    private val providerUpdates = HashMap<Group, AmbientMap>()
    private var providersInvalid = false
    private val providersInvalidStack = IntStack()

    private val invalidateStack = Stack<RecomposeScope>()

    internal var parentReference: CompositionReference? = null
    internal var isComposing = false

    private val changesAppliedObservers = mutableListOf<() -> Unit>()

    private fun dispatchChangesAppliedObservers() {
        trace("Compose:dispatchChangesAppliedObservers") {
            val listeners = changesAppliedObservers.toTypedArray()
            changesAppliedObservers.clear()
            listeners.forEach { it() }
        }
    }

    internal fun addChangesAppliedObserver(l: () -> Unit) {
        changesAppliedObservers.add(l)
    }

    internal fun removeChangesAppliedObserver(l: () -> Unit) {
        changesAppliedObservers.remove(l)
    }

    private var reader: SlotReader = slotTable.openReader().also { it.close() }

    private val insertTable = SlotTable()
    private var writer: SlotWriter = insertTable.openWriter().also { it.close() }
    private var hasProvider = false
    private var insertAnchor: Anchor = insertTable.anchor(0)
    private val insertFixups = mutableListOf<Change<N>>()

    @InternalComposeApi
    fun composeRoot(block: () -> Unit) {
        startRoot()
        startGroup(invocationKey, invocation)
        block()
        endGroup()
        endRoot()
    }

    /**
     * Inserts a "Replaceable Group" starting marker in the slot table at the current execution
     * position. A Replaceable Group is a group which cannot be moved between its siblings, but
     * can be removed or inserted. These groups are inserted by the compiler around branches of
     * conditional logic in Composable functions such as if expressions, when expressions, early
     * returns, and null-coalescing operators.
     *
     * A call to [startReplaceableGroup] must be matched with a corresponding call to
     * [endReplaceableGroup].
     *
     * Warning: This is expected to be executed by the compiler only and should not be called
     * directly from source code. Call this API at your own risk.
     *
     * @param key The source-location-based key for the group. Expected to be unique among its
     * siblings.
     *
     * @see [endReplaceableGroup]
     * @see [startMovableGroup]
     * @see [startRestartGroup]
     */
    @ComposeCompilerApi
    fun startReplaceableGroup(key: Int) = start(key, null, false, null)

    @ComposeCompilerApi
    fun startReplaceableGroup(key: Int, sourceInformation: String?) =
        start(key, null, false, sourceInformation)

    /**
     * Indicates the end of a "Replaceable Group" at the current execution position. A
     * Replaceable Group is a group which cannot be moved between its siblings, but
     * can be removed or inserted. These groups are inserted by the compiler around branches of
     * conditional logic in Composable functions such as if expressions, when expressions, early
     * returns, and null-coalescing operators.
     *
     * Warning: This is expected to be executed by the compiler only and should not be called
     * directly from source code. Call this API at your own risk.
     *
     * @see [startReplaceableGroup]
     */
    @ComposeCompilerApi
    fun endReplaceableGroup() = endGroup()

    /**
     *
     * Warning: This is expected to be executed by the compiler only and should not be called
     * directly from source code. Call this API at your own risk.
     *
     */
    @ComposeCompilerApi
    fun startDefaults() = start(0, null, false, null)

    /**
     *
     * Warning: This is expected to be executed by the compiler only and should not be called
     * directly from source code. Call this API at your own risk.
     *
     * @see [startReplaceableGroup]
     */
    @ComposeCompilerApi
    fun endDefaults() {
        endGroup()
        val scope = currentRecomposeScope
        if (scope != null && scope.used) {
            scope.defaultsInScope = true
        }
    }

    @ComposeCompilerApi
    val defaultsInvalid: Boolean
        get() {
            return providersInvalid || currentRecomposeScope?.defaultsInvalid == true
        }

    /**
     * Inserts a "Movable Group" starting marker in the slot table at the current execution
     * position. A Movable Group is a group which can be moved or reordered between its siblings
     * and retain slot table state, in addition to being removed or inserted. Movable Groups
     * are more expensive than other groups because when they are encountered with a mismatched
     * key in the slot table, they must be held on to temporarily until the entire parent group
     * finishes execution in case it moved to a later position in the group. Movable groups are
     * only inserted by the compiler as a result of calls to [key].
     *
     * A call to [startMovableGroup] must be matched with a corresponding call to [endMovableGroup].
     *
     * Warning: This is expected to be executed by the compiler only and should not be called
     * directly from source code. Call this API at your own risk.
     *
     * @param key The source-location-based key for the group. Expected to be unique among its
     * siblings.
     *
     * @param dataKey Additional identifying information to compound with [key]. If there are
     * multiple values, this is expected to be compounded together with [joinKey]. Whatever value
     * is passed in here is expected to have a meaningful [equals] and [hashCode] implementation.
     *
     * @see [endMovableGroup]
     * @see [key]
     * @see [joinKey]
     * @see [startReplaceableGroup]
     * @see [startRestartGroup]
     */
    @ComposeCompilerApi
    fun startMovableGroup(key: Int, dataKey: Any?) = start(key, dataKey, false, null)

    @ComposeCompilerApi
    fun startMovableGroup(key: Int, dataKey: Any?, sourceInformation: String?) =
        start(key, dataKey, false, sourceInformation)

    /**
     * Indicates the end of a "Movable Group" at the current execution position. A Movable Group is
     * a group which can be moved or reordered between its siblings and retain slot table state,
     * in addition to being removed or inserted. These groups are only valid when they are
     * inserted as direct children of Container Groups. Movable Groups are more expensive than
     * other groups because when they are encountered with a mismatched key in the slot table,
     * they must be held on to temporarily until the entire parent group finishes execution in
     * case it moved to a later position in the group. Movable groups are only inserted by the
     * compiler as a result of calls to [key].
     *
     * Warning: This is expected to be executed by the compiler only and should not be called
     * directly from source code. Call this API at your own risk.
     *
     * @see [startMovableGroup]
     */
    @ComposeCompilerApi
    fun endMovableGroup() = endGroup()

    /**
     * Start the composition. This should be called, and only be called, as the first group in
     * the composition.
     */
    internal fun startRoot() {
        reader = slotTable.openReader()
        startGroup(rootKey)
        parentReference?.let { parentRef ->
            parentProvider = parentRef.getAmbientScope()
            providersInvalidStack.push(providersInvalid.asInt())
            providersInvalid = changed(parentProvider)
            collectKeySources = parentRef.collectingKeySources
            resolveAmbient(InspectionTables, parentProvider)?.let {
                it.add(slotTable)
                parentRef.recordInspectionTable(it)
            }
            startGroup(parentRef.compoundHashKey)
        }
    }

    /**
     * End the composition. This should be called, and only be called, to end the first group in
     * the composition.
     */
    internal fun endRoot() {
        if (parentReference != null) {
            endGroup()
        }
        endGroup()
        recordEndRoot()
        finalizeCompose()
        reader.close()
    }

    /**
     * Discard a pending composition because an error was encountered during composition
     */
    internal fun abortRoot() {
        cleanUpCompose()
        pendingStack.clear()
        nodeIndexStack.clear()
        groupNodeCountStack.clear()
        entersStack.clear()
        providersInvalidStack.clear()
        invalidateStack.clear()
        reader.close()
        currentCompoundKeyHash = 0
        nodeExpected = false
    }

    /**
     * True if the composition is currently scheduling nodes to be inserted into the tree. During
     * first composition this is always true. During recomposition this is true when new nodes
     * are being scheduled to be added to the tree.
     */
    @ComposeCompilerApi
    var inserting: Boolean = false
        private set

    /**
     * True if the composition should be checking if the composable functions can be skipped.
     */
    @ComposeCompilerApi
    val skipping: Boolean get() {
        return !inserting &&
                !providersInvalid &&
                currentRecomposeScope?.requiresRecompose == false
    }

    /**
     * Returns the hash of the compound key calculated as a combination of the keys of all the
     * currently started groups via [startGroup].
     */
    @ExperimentalComposeApi
    var currentCompoundKeyHash: Int = 0
        private set

    /**
     * Start collecting key source information. This enables enables the tool API to be able to
     * determine the source location of where groups and nodes are created.
     */
    @InternalComposeApi
    fun collectKeySourceInformation() {
        collectKeySources = true
    }

    /**
     * Helper for collecting lifecycle enter and leave events for later strictly ordered dispatch.
     * [lifecycleObservers] should be the long-lived set of observers tracked over time; brand new
     * additions or leaves from this set will be tracked by the [LifecycleManager] callback methods.
     * Call [dispatchLifecycleObservers] to invoke the observers in LIFO order - last in,
     * first out.
     */
    private class LifecycleEventDispatcher(
        private val lifecycleObservers: MutableMap<CompositionLifecycleObserverHolder,
                CompositionLifecycleObserverHolder>
    ) : LifecycleManager {
        private val enters = mutableSetOf<CompositionLifecycleObserverHolder>()
        private val leaves = mutableSetOf<CompositionLifecycleObserverHolder>()

        override fun entering(instance: CompositionLifecycleObserver) {
            val holder = CompositionLifecycleObserverHolder(instance)
            lifecycleObservers.getOrPut(holder) {
                enters.add(holder)
                holder
            }.apply { count++ }
        }

        override fun leaving(instance: CompositionLifecycleObserver) {
            val holder = CompositionLifecycleObserverHolder(instance)
            val left = lifecycleObservers[holder]?.let {
                if (--it.count == 0) {
                    leaves.add(it)
                    it
                } else null
            }
            if (left != null) lifecycleObservers.remove(left)
        }

        fun dispatchLifecycleObservers() {
            trace("Compose:lifecycles") {
                // Send lifecycle leaves
                if (leaves.isNotEmpty()) {
                    for (holder in leaves.reversed()) {
                        // The count of the holder might be greater than 0 here as it might leave one
                        // part of the composition and reappear in another. Only send a leave if the
                        // count is still 0 after all changes have been applied.
                        if (holder.count == 0) {
                            holder.instance.onLeave()
                            lifecycleObservers.remove(holder)
                        }
                    }
                }

                // Send lifecycle enters
                if (enters.isNotEmpty()) {
                    for (holder in enters) {
                        holder.instance.onEnter()
                    }
                }
            }
        }
    }

    /**
     * Apply the changes to the tree that were collected during the last composition.
     */
    @InternalComposeApi
    fun applyChanges() {
        trace("Compose:applyChanges") {
            invalidateStack.clear()
            val invalidationAnchors = invalidations.map { slotTable.anchor(it.location) to it }
            val manager = LifecycleEventDispatcher(lifecycleObservers)

            // Apply all changes
            slotTable.write { slots ->
                changes.forEach { change -> change(applier, slots, manager) }
                changes.clear()
            }

            providerUpdates.clear()

            @Suppress("ReplaceManualRangeWithIndicesCalls") // Avoids allocation of an iterator
            for (index in 0 until invalidationAnchors.size) {
                val (anchor, invalidation) = invalidationAnchors[index]
                invalidation.location = slotTable.anchorLocation(anchor)
            }

            manager.dispatchLifecycleObservers()
            dispatchChangesAppliedObservers()
        }
    }

    internal fun dispose() {
        trace("Compose:Composer.dispose") {
            parentReference?.unregisterComposer(this)
            invalidateStack.clear()
            invalidations.clear()
            changes.clear()
            applier.clear()
            if (slotTable.size > 0) {
                val manager = LifecycleEventDispatcher(lifecycleObservers)
                slotTable.write { writer ->
                    writer.removeCurrentGroup(manager)
                }
                providerUpdates.clear()
                manager.dispatchLifecycleObservers()
            }
            dispatchChangesAppliedObservers()
        }
    }

    /**
     * Start a group with the given key. During recomposition if the currently expected group does
     * not match the given key a group the groups emitted in the same parent group are inspected
     * to determine if one of them has this key and that group the first such group is moved
     * (along with any nodes emitted by the group) to the current position and composition
     * continues. If no group with this key is found, then the composition shifts into insert
     * mode and new nodes are added at the current position.
     *
     *  @param key The key for the group
     */
    internal fun startGroup(key: Int) = start(key, null, false, null)

    internal fun startGroup(key: Int, dataKey: Any?) = start(key, dataKey, false, null)

    /**
     * End the current group.
     */
    internal fun endGroup() = end(false)

    private fun skipGroup() {
        groupNodeCount += reader.skipGroup()
    }

    /**
     * Start emitting a node. It is required that one of [emitNode] or [createNode] is called
     * after [startNode]. Similar to [startGroup], if, during recomposition, the current node
     * does not have the provided key a node with that key is scanned for and moved into the
     * current position if found, if no such node is found the composition switches into insert
     * mode and a the node is scheduled to be inserted at the current location.
     */
    @ComposeCompilerApi
    fun startNode() {
        start(nodeKey, null, true, null)
        nodeExpected = true
    }

    /**
     * Schedule a node to be created and inserted at the current location. This is only valid to
     * call when the composer is inserting.
     */
    @Suppress("UNUSED")
    @ComposeCompilerApi
    fun <T : N> createNode(factory: () -> T) {
        validateNodeExpected()
        check(inserting) { "createNode() can only be called when inserting" }
        val insertIndex = nodeIndexStack.peek()
        // see emitNode
        groupNodeCount++
        recordFixup { applier, slots, _ ->
            val node = factory()
            slots.node = node
            applier.insert(insertIndex, node)
            applier.down(node)
        }
        // Allocate a slot that will be fixed-up by the above operation.
        writer.skip()
    }

    /**
     * Schedule the given node to be inserted. This is only valid to call when the composer is
     * inserting.
     */
    @ComposeCompilerApi
    fun emitNode(node: Any?) {
        validateNodeExpected()
        check(inserting) { "emitNode() called when not inserting" }
        val insertIndex = nodeIndexStack.peek()
        // see emitNode
        groupNodeCount++
        @Suppress("UNCHECKED_CAST")
        writer.node = node as N
        recordApplierOperation { applier, _, _ ->
            applier.insert(insertIndex, node)
            applier.down(node)
        }
    }

    /**
     * Return the instance of the node that was inserted at the given location. This is only
     * valid to call when the composition is not inserting. This must be called at the same
     * location as [emitNode] or [createNode] as called even if the value is unused.
     */
    @ComposeCompilerApi
    fun useNode(): N {
        validateNodeExpected()
        check(!inserting) { "useNode() called while inserting" }
        val result = reader.node
        recordDown(result)
        return result
    }

    /**
     * Called to end the node group.
     */
    @ComposeCompilerApi
    fun endNode() = end(true)

    /**
     * Schedule a change to be applied to a node's property. This change will be applied to the
     * node that is the current node in the tree which was either created by [createNode],
     * emitted by [emitNode] or returned by [useNode].
     */
    internal fun <V, T> apply(value: V, block: T.(V) -> Unit) {
        recordApplierOperation { applier, _, _ ->
            @Suppress("UNCHECKED_CAST")
            (applier.current as T).block(value)
        }
    }

    /**
     * Create a composed key that can be used in calls to [startGroup] or [startNode]. This will
     * use the key stored at the current location in the slot table to avoid allocating a new key.
     */
    @ComposeCompilerApi
    fun joinKey(left: Any?, right: Any?): Any =
        getKey(reader.groupDataKey, left, right) ?: JoinedKey(left, right)

    /**
     * Return the next value in the slot table and advance the current location.
     */
    @ComposeCompilerApi
    fun nextSlot(): Any? = if (inserting) {
        validateNodeNotExpected()
        EMPTY
    } else reader.next()

    /**
     * Determine if the current slot table value is equal to the given value, if true, the value
     * is scheduled to be skipped during [applyChanges] and [changes] return false; otherwise
     * [applyChanges] will update the slot table to [value]. In either case the composer's slot
     * table is advanced.
     *
     * @param value the value to be compared.
     */
    @ComposeCompilerApi
    fun changed(value: Any?): Boolean {
        return if (nextSlot() != value) {
            updateValue(value)
            true
        } else {
            false
        }
    }

    @ComposeCompilerApi
    fun changed(value: Char): Boolean {
        val next = nextSlot()
        if (next is Char) {
            val nextPrimitive: Char = next
            if (value == nextPrimitive) return false
        }
        updateValue(value)
        return true
    }

    @ComposeCompilerApi
    fun changed(value: Byte): Boolean {
        val next = nextSlot()
        if (next is Byte) {
            val nextPrimitive: Byte = next
            if (value == nextPrimitive) return false
        }
        updateValue(value)
        return true
    }

    @ComposeCompilerApi
    fun changed(value: Short): Boolean {
        val next = nextSlot()
        if (next is Short) {
            val nextPrimitive: Short = next
            if (value == nextPrimitive) return false
        }
        updateValue(value)
        return true
    }

    @ComposeCompilerApi
    fun changed(value: Boolean): Boolean {
        val next = nextSlot()
        if (next is Boolean) {
            val nextPrimitive: Boolean = next
            if (value == nextPrimitive) return false
        }
        updateValue(value)
        return true
    }

    @ComposeCompilerApi
    fun changed(value: Float): Boolean {
        val next = nextSlot()
        if (next is Float) {
            val nextPrimitive: Float = next
            if (value == nextPrimitive) return false
        }
        updateValue(value)
        return true
    }

    @ComposeCompilerApi
    fun changed(value: Long): Boolean {
        val next = nextSlot()
        if (next is Long) {
            val nextPrimitive: Long = next
            if (value == nextPrimitive) return false
        }
        updateValue(value)
        return true
    }

    @ComposeCompilerApi
    fun changed(value: Double): Boolean {
        val next = nextSlot()
        if (next is Double) {
            val nextPrimitive: Double = next
            if (value == nextPrimitive) return false
        }
        updateValue(value)
        return true
    }

    @ComposeCompilerApi
    fun changed(value: Int): Boolean {
        val next = nextSlot()
        if (next is Int) {
            val nextPrimitive: Int = next
            if (value == nextPrimitive) return false
        }
        updateValue(value)
        return true
    }

    /**
     * Cache a value in the composition. During initial composition [block] is called to produce the
     * value that is then stored in the slot table. During recomposition, if [invalid] is false
     * the value is obtained from the slot table and [block] is not invoked. If [invalid] is
     * false a new value is produced by calling [block] and the slot table is updated to contain
     * the new value.
     */
    @ComposeCompilerApi
    inline fun <T> cache(invalid: Boolean, block: () -> T): T {
        var result = nextSlot()
        if (result === EMPTY || invalid) {
            val value = block()
            updateValue(value)
            result = value
        }

        @Suppress("UNCHECKED_CAST")
        return result as T
    }

    /**
     * Schedule the current value in the slot table to be updated to [value].
     *
     * @param value the value to schedule to be written to the slot table.
     */
    @PublishedApi
    internal fun updateValue(value: Any?) {
        if (inserting) {
            writer.update(value)
            if (value is CompositionLifecycleObserver) {
                record { _, _, lifecycleManager -> lifecycleManager.entering(value) }
            }
        } else {
            recordSlotTableOperation(-1) { _, slots, lifecycleManager ->
                if (value is CompositionLifecycleObserver)
                    lifecycleManager.entering(value)
                when (val previous = slots.update(value)) {
                    is CompositionLifecycleObserver ->
                        lifecycleManager.leaving(previous)
                    is RecomposeScope ->
                        previous.composer = null
                }
            }
            // Advance the writers reader location to account for the update above.
            writersReaderDelta++
        }
    }

    /**
     * Return the current ambient scope which was provided by a parent group.
     */
    private fun currentAmbientScope(): AmbientMap {
        if (inserting && hasProvider) {
            var group: Group? = writer.group(writer.parentLocation)
            while (group != null) {
                if (group.key == ambientMapKey && group.dataKey === ambientMap) {
                    @Suppress("UNCHECKED_CAST")
                    return group.data as AmbientMap
                }
                group = group.parent
            }
        }
        if (slotTable.size > 0) {
            var group: Group? = reader.group(reader.parentLocation)
            while (group != null) {
                if (group.key == ambientMapKey && group.dataKey === ambientMap) {
                    @Suppress("UNCHECKED_CAST")
                    return providerUpdates[group] ?: group.data as AmbientMap
                }
                group = group.parent
            }
        }
        return parentProvider
    }

    /**
     * Return the ambient scope for the location provided. If this is while the composer is
     * composing then this is a query from a sub-composition that is being recomposed by this
     * compose which might be inserting the sub-composition. In that case the current scope
     * is the correct scope.
     */
    private fun ambientScopeAt(location: Int): AmbientMap {
        if (isComposing) {
            // The sub-composer is being composed as part of a nested composition then use the
            // current ambient scope as the one in the slot table might be out of date.
            return currentAmbientScope()
        }

        if (location >= 0) {
            var group: Group? = slotTable.read { it.group(location) }
            while (group != null) {
                if (group.key == ambientMapKey && group.dataKey === ambientMap) {
                    @Suppress("UNCHECKED_CAST")
                    return providerUpdates[group] ?: group.data as AmbientMap
                }
                group = group.parent
            }
        }
        return parentProvider
    }

    /**
     * Update (or create) the slots to record the providers. The providers maps are first the
     * scope followed by the map used to augment the parent scope. Both are needed to detect
     * inserts, updates and deletes to the providers.
     */
    private fun updateProviderMapGroup(
        parentScope: AmbientMap,
        currentProviders: AmbientMap
    ): AmbientMap {
        val providerScope = parentScope.mutate { it.putAll(currentProviders) }
        startGroup(providerMapsKey, providerMaps)
        changed(providerScope)
        changed(currentProviders)
        endGroup()
        return providerScope
    }

    internal fun startProviders(values: Array<out ProvidedValue<*>>) {
        val parentScope = currentAmbientScope()
        startGroup(providerKey, provider)
        // The group is needed here because ambientMapOf() might change the number or kind of
        // slots consumed depending on the content of values to remember, for example, the value
        // holders used last time.
        startGroup(providerValuesKey, providerValues)
        val currentProviders = invokeComposableForResult(this) { ambientMapOf(values) }
        endGroup()
        val providers: AmbientMap
        val invalid: Boolean
        if (inserting) {
            providers = updateProviderMapGroup(parentScope, currentProviders)
            invalid = false
            hasProvider = true
        } else {
            val current = reader.current

            @Suppress("UNCHECKED_CAST")
            val oldScope = reader.get(current + 1) as AmbientMap

            @Suppress("UNCHECKED_CAST")
            val oldValues = reader.get(current + 2) as AmbientMap

            // skipping is true iff parentScope has not changed.
            if (!skipping || oldValues != currentProviders) {
                providers = updateProviderMapGroup(parentScope, currentProviders)

                // Compare against the old scope as currentProviders might have modified the scope
                // back to the previous value. This could happen, for example, if currentProviders
                // and parentScope have a key in common and the oldScope had the same value as
                // currentProviders for that key. If the scope has not changed, because these
                // providers obscure a change in the parent as described above, re-enable skipping
                // for the child region.
                invalid = providers != oldScope
            } else {
                // Nothing has changed
                skipGroup()
                providers = oldScope
                invalid = false
            }
        }

        if (invalid && !inserting) {
            providerUpdates[reader.group] = providers
        }
        providersInvalidStack.push(providersInvalid.asInt())
        providersInvalid = invalid
        start(ambientMapKey, ambientMap, false, providers)
    }

    internal fun endProviders() {
        endGroup()
        endGroup()
        providersInvalid = providersInvalidStack.pop().asBool()
    }

    @PublishedApi
    internal fun <T> consume(key: Ambient<T>): T = resolveAmbient(key, currentAmbientScope())

    /**
     * Create or use a memoized `CompositionReference` instance at this position in the slot table.
     */
    internal fun buildReference(): CompositionReference {
        startGroup(referenceKey, reference)

        var ref = nextSlot() as? CompositionReferenceHolder<*>
        if (ref == null || !inserting) {
            val scope = invalidateStack.peek()
            scope.used = true
            ref = CompositionReferenceHolder(
                CompositionReferenceImpl(scope, currentCompoundKeyHash, collectKeySources)
            )
            updateValue(ref)
        }
        endGroup()

        return ref.ref
    }

    private fun <T> resolveAmbient(key: Ambient<T>, scope: AmbientMap): T {
        if (scope.contains(key)) return scope.getValueOf(key)

        val ref = parentReference

        if (ref != null) {
            return ref.getAmbient(key)
        }

        return key.defaultValueHolder.value
    }

    internal fun <T> parentAmbient(key: Ambient<T>): T = resolveAmbient(key, currentAmbientScope())

    private fun <T> parentAmbient(key: Ambient<T>, location: Int): T =
        resolveAmbient(key, ambientScopeAt(location))

    /**
     * The number of changes that have been scheduled to be applied during [applyChanges].
     *
     * Slot table movement (skipping groups and nodes) will be coalesced so this number is
     * possibly less than the total changes detected.
     */
    internal val changeCount get() = changes.size

    internal val currentRecomposeScope: RecomposeScope?
        get() =
            invalidateStack.let { if (it.isNotEmpty()) it.peek() else null }

    private fun ensureWriter() {
        if (writer.closed) {
            writer = insertTable.openWriter()
            hasProvider = false
        }
    }

    /**
     * Start the reader group updating the data of the group if necessary
     */
    private fun startReaderGroup(isNode: Boolean, data: Any?) {
        if (isNode) {
            reader.startNode()
        } else {
            if (data != null && reader.groupData !== data) {
                recordSlotEditingOperation { _, slots, _ ->
                    slots.updateData(data)
                }
            }
            if (data != null)
                reader.startDataGroup()
            else
                reader.startGroup()
        }
    }

    private fun start(key: Int, dataKey: Any?, isNode: Boolean, data: Any?) {
        validateNodeNotExpected()

        updateCompoundKeyWhenWeEnterGroup(key, dataKey)

        // Check for the insert fast path. If we are already inserting (creating nodes) then
        // there is no need to track insert, deletes and moves with a pending changes object.
        if (inserting) {
            reader.beginEmpty()
            if (collectKeySources)
                recordSourceKeyInfo(key)
            when {
                isNode -> writer.startNode(null)
                data != null -> writer.startData(key, dataKey, data)
                else -> writer.startGroup(key, dataKey)
            }
            pending?.let { pending ->
                val insertKeyInfo = KeyInfo(key, -1, 0, -1, 0, writer.parentGroup)
                pending.registerInsert(insertKeyInfo, nodeIndex - pending.startIndex)
                pending.recordUsed(insertKeyInfo)
            }
            enterGroup(isNode, null)
            return
        }

        if (pending == null) {
            val slotKey = reader.groupKey
            if (slotKey == key && dataKey == reader.groupDataKey) {
                // The group is the same as what was generated last time.
                startReaderGroup(isNode, data)
            } else {
                pending = Pending(
                    reader.extractKeys(),
                    nodeIndex
                )
            }
        }

        val pending = pending
        var newPending: Pending? = null
        if (pending != null) {
            // Check to see if the key was generated last time from the keys collected above.
            val keyInfo = pending.getNext(key, dataKey)
            if (keyInfo != null) {
                // This group was generated last time, use it.
                pending.recordUsed(keyInfo)

                // Move the slot table to the location where the information about this group is
                // stored. The slot information will move once the changes are applied so moving the
                // current of the slot table is sufficient.
                val location = keyInfo.location

                // Determine what index this group is in. This is used for inserting nodes into the
                // group.
                nodeIndex = pending.nodePositionOf(keyInfo) + pending.startIndex

                // Determine how to move the slot group to the correct position.
                val relativePosition = pending.slotPositionOf(keyInfo)
                val currentRelativePosition = relativePosition - pending.groupIndex
                pending.registerMoveSlot(relativePosition, pending.groupIndex)
                recordReaderMoving(location)
                reader.reposition(location)
                if (currentRelativePosition > 0) {
                    // The slot group must be moved, record the move to be performed during apply.
                    recordSlotEditingOperation { _, slots, _ ->
                        slots.moveGroup(currentRelativePosition)
                    }
                }
                startReaderGroup(isNode, data)
            } else {
                // The group is new, go into insert mode. All child groups will written to the
                // insertTable until the group is complete which will schedule the groups to be
                // inserted into in the table.
                reader.beginEmpty()
                inserting = true
                if (collectKeySources)
                    recordSourceKeyInfo(key)

                ensureWriter()
                writer.beginInsert()
                val insertLocation = writer.current
                if (isNode) writer.startNode(null) else writer.startGroup(key, dataKey, data)
                insertAnchor = writer.anchor(insertLocation)
                val insertKeyInfo = KeyInfo(key, -1, 0, -1, 0, writer.parentGroup)
                pending.registerInsert(insertKeyInfo, nodeIndex - pending.startIndex)
                pending.recordUsed(insertKeyInfo)
                newPending = Pending(
                    mutableListOf(),
                    if (isNode) 0 else nodeIndex
                )
            }
        }

        enterGroup(isNode, newPending)
    }

    private fun enterGroup(isNode: Boolean, newPending: Pending?) {
        // When entering a group all the information about the parent should be saved, to be
        // restored when end() is called, and all the tracking counters set to initial state for the
        // group.
        pendingStack.push(pending)
        this.pending = newPending
        this.nodeIndexStack.push(nodeIndex)
        if (isNode) nodeIndex = 0
        this.groupNodeCountStack.push(groupNodeCount)
        groupNodeCount = 0
    }

    private fun exitGroup(expectedNodeCount: Int, inserting: Boolean) {
        // Restore the parent's state updating them if they have changed based on changes in the
        // children. For example, if a group generates nodes then the number of generated nodes will
        // increment the node index and the group's node count. If the parent is tracking structural
        // changes in pending then restore that too.
        val previousPending = pendingStack.pop()
        if (previousPending != null && !inserting) {
            previousPending.groupIndex++
        }
        this.pending = previousPending
        this.nodeIndex = nodeIndexStack.pop() + expectedNodeCount
        this.groupNodeCount = this.groupNodeCountStack.pop() + expectedNodeCount
    }

    private fun end(isNode: Boolean) {
        // All the changes to the group (or node) have been recorded. All new nodes have been
        // inserted but it has yet to determine which need to be removed or moved. Note that the
        // changes are relative to the first change in the list of nodes that are changing.

        val group = if (inserting)
            writer.group(writer.parentLocation)
        else
            reader.group(reader.parentLocation)
        updateCompoundKeyWhenWeExitGroup(group.key, group.dataKey)
        var expectedNodeCount = groupNodeCount
        val pending = pending
        if (pending != null && pending.keyInfos.size > 0) {
            // previous contains the list of keys as they were generated in the previous composition
            val previous = pending.keyInfos

            // current contains the list of keys in the order they need to be in the new composition
            val current = pending.used

            // usedKeys contains the keys that were used in the new composition, therefore if a key
            // doesn't exist in this set, it needs to be removed.
            val usedKeys = current.toSet()

            val placedKeys = mutableSetOf<KeyInfo>()
            var currentIndex = 0
            val currentEnd = current.size
            var previousIndex = 0
            val previousEnd = previous.size

            // Traverse the list of changes to determine startNode movement
            var nodeOffset = 0
            while (previousIndex < previousEnd) {
                val previousInfo = previous[previousIndex]
                if (!usedKeys.contains(previousInfo)) {
                    // If the key info was not used the group was deleted, remove the nodes in the
                    // group
                    val deleteOffset = pending.nodePositionOf(previousInfo)
                    recordRemoveNode(deleteOffset + pending.startIndex, previousInfo.nodes)
                    pending.updateNodeCount(previousInfo.group, 0)
                    recordReaderMoving(previousInfo.location)
                    reader.reposition(previousInfo.location)
                    recordDelete()
                    reader.skipGroup()

                    // Remove any invalidations pending for the group being removed. These are no
                    // longer part of the composition. The group being composed is one after the
                    // start of the group.
                    invalidations.removeRange(
                        previousInfo.location,
                        previousInfo.location + reader.groupSize(previousInfo.location)
                    )
                    previousIndex++
                    continue
                }

                if (previousInfo in placedKeys) {
                    // If the group was already placed in the correct location, skip it.
                    previousIndex++
                    continue
                }

                if (currentIndex < currentEnd) {
                    // At this point current should match previous unless the group is new or was
                    // moved.
                    val currentInfo = current[currentIndex]
                    if (currentInfo !== previousInfo) {
                        val nodePosition = pending.nodePositionOf(currentInfo)
                        placedKeys.add(currentInfo)
                        if (nodePosition != nodeOffset) {
                            val updatedCount = pending.updatedNodeCountOf(currentInfo)
                            recordMoveNode(
                                nodePosition + pending.startIndex,
                                nodeOffset + pending.startIndex, updatedCount
                            )
                            pending.registerMoveNode(nodePosition, nodeOffset, updatedCount)
                        } // else the nodes are already in the correct position
                    } else {
                        // The correct nodes are in the right location
                        previousIndex++
                    }
                    currentIndex++
                    nodeOffset += pending.updatedNodeCountOf(currentInfo)
                }
            }

            // If there are any current nodes left they where inserted into the right location
            // when the group began so the rest are ignored.
            realizeMovement()

            // We have now processed the entire list so move the slot table to the end of the list
            // by moving to the last key and skipping it.
            if (previous.size > 0) {
                recordReaderMoving(reader.groupEnd)
                reader.skipToGroupEnd()
            }
        }

        // Detect removing nodes at the end. No pending is created in this case we just have more
        // nodes in the previous composition than we expect (i.e. we are not yet at an end)
        val removeIndex = nodeIndex
        while (!reader.isGroupEnd) {
            val startSlot = reader.current
            recordDelete()
            val nodesToRemove = reader.skipGroup()
            recordRemoveNode(removeIndex, nodesToRemove)
            invalidations.removeRange(startSlot, reader.current)
        }

        val inserting = inserting
        if (inserting) {
            if (isNode) {
                recordInsertUp()
                expectedNodeCount = 1
            }
            reader.endEmpty()
            val parentGroup = writer.parentGroup
            writer.endGroup()
            if (!reader.inEmpty) {
                writer.endInsert()
                writer.close()
                recordInsert(insertAnchor)
                this.inserting = false
                nodeCountOverrides[parentGroup] = 0
                updateNodeCountOverrides(parentGroup, expectedNodeCount)
            }
        } else {
            if (isNode) recordUp()
            recordEndGroup()
            val parentGroup = reader.parentGroup
            if (expectedNodeCount != parentGroup.nodes) {
                updateNodeCountOverrides(parentGroup, expectedNodeCount)
            }
            if (isNode) {
                expectedNodeCount = 1
                reader.endNode()
            } else reader.endGroup()

            realizeMovement()
        }

        exitGroup(expectedNodeCount, inserting)
    }

    /**
     * Recompose any invalidate child groups of the current parent group. This should be called
     * after the group is started but on or before the first child group. It is intended to be
     * called instead of [skipReaderToGroupEnd] if any child groups are invalid. If no children
     * are invalid it will call [skipReaderToGroupEnd].
     */
    private fun recomposeToGroupEnd() {
        val wasComposing = isComposing
        isComposing = true
        var recomposed = false

        val parent = reader.parentLocation
        val end = parent + reader.groupSize(parent)
        val recomposeGroup = reader.group(parent)
        val recomposeIndex = nodeIndex
        val recomposeCompoundKey = currentCompoundKeyHash
        val oldGroupNodeCount = groupNodeCount
        var oldGroup = recomposeGroup

        var firstInRange = invalidations.firstInRange(reader.current, end)
        while (firstInRange != null) {
            val location = firstInRange.location

            invalidations.removeLocation(location)

            recomposed = true

            reader.reposition(location)
            val newGroup = reader.group
            // Record the changes to the applier location
            recordUpsAndDowns(oldGroup, newGroup, recomposeGroup)
            oldGroup = newGroup

            // Calculate the node index (the distance index in the node this groups nodes are
            // located in the parent node).
            nodeIndex = nodeIndexOf(
                location,
                newGroup,
                parent,
                recomposeGroup,
                recomposeIndex
            )

            // Calculate the compound hash code (a semi-unique code for every group in the
            // composition used to restore saved state).
            currentCompoundKeyHash = compoundKeyOf(
                newGroup.parent,
                recomposeGroup,
                recomposeCompoundKey
            )

            firstInRange.scope.compose(this)

            // Using slots.current here ensures composition always walks forward even if a component
            // before the current composition is invalidated when performing this composition. Any
            // such components will be considered invalid for the next composition. Skipping them
            // prevents potential infinite recomposes at the cost of potentially missing a compose
            // as well as simplifies the apply as it always modifies the slot table in a forward
            // direction.
            firstInRange = invalidations.firstInRange(reader.current, end)
        }

        if (recomposed) {
            recordUpsAndDowns(oldGroup, recomposeGroup, recomposeGroup)
            val parentGroup = reader.parentGroup
            reader.skipToGroupEnd()
            val parentGroupNodes = (nodeCountOverrides[parentGroup] ?: parentGroup.nodes)
            nodeIndex = recomposeIndex + parentGroupNodes
            groupNodeCount = oldGroupNodeCount + parentGroupNodes
        } else {
            // No recompositions were requested in the range, skip it.
            skipReaderToGroupEnd()
        }
        currentCompoundKeyHash = recomposeCompoundKey

        isComposing = wasComposing
    }

    /**
     * As operations to insert and remove nodes are recorded, the number of nodes that will be in
     * the group after changes are applied is maintained in a side overrides table. This method
     * updates that count and then updates any parent groups that include the nodes this group
     * emits.
     */
    private fun updateNodeCountOverrides(group: Group, newCount: Int) {
        val currentCount = nodeCountOverrides[group] ?: group.nodes
        if (currentCount != newCount) {
            // Update the overrides
            val delta = newCount - currentCount
            var current: Group? = group

            var minPending = pendingStack.size - 1
            while (current != null) {
                val newCurrentNodes = (nodeCountOverrides[current] ?: current.nodes) + delta
                nodeCountOverrides[current] = newCurrentNodes
                for (pendingIndex in minPending downTo 0) {
                    val pending = pendingStack.peek(pendingIndex)
                    if (pending != null && pending.updateNodeCount(current, newCurrentNodes)) {
                        minPending = pendingIndex - 1
                        break
                    }
                }
                if (current.isNode) break
                current = current.parent
            }
        }
    }

    /**
     * Calculates the node index (the index in the child list of a node will appear in the
     * resulting tree) for [group]. Passing in [recomposeGroup] and its node index in
     * [recomposeIndex] allows the calculation to exit early if there is no node group between
     * [group] and [recomposeGroup].
     */
    private fun nodeIndexOf(
        groupLocation: Int,
        group: Group,
        recomposeLocation: Int,
        recomposeGroup: Group,
        recomposeIndex: Int
    ): Int {
        // Find the anchor group which is either the recomposeGroup or the first parent node
        var anchorGroup = group.parent ?: error("Invalid group")
        while (anchorGroup != recomposeGroup) {
            if (anchorGroup.isNode) break
            anchorGroup = anchorGroup.parent ?: error("group not contained in recompose group")
        }

        var index = if (anchorGroup.isNode) 0 else recomposeIndex

        // An early out if the group and anchor sizes are the same as the index must then be index
        if (anchorGroup.slots == group.slots) return index

        // Find the location of the anchor group
        val anchorLocation =
            if (anchorGroup == recomposeGroup) {
                recomposeLocation
            } else {
                // anchor node must be between recomposeLocation and groupLocation but no farther
                // back than anchorGroup.size - group.size + 1 because anchorGroup contains group
                var location = recomposeLocation
                val anchorLimit = groupLocation - (anchorGroup.slots - group.slots + 1)
                if (location < anchorLimit) location = anchorLimit
                while (reader.get(location) !== anchorGroup)
                    location++
                location
            }

        // Walk down from the anchor group counting nodes of siblings in front of this group
        var current = anchorLocation
        val nodeIndexLimit = index + ((nodeCountOverrides[anchorGroup] ?: anchorGroup.nodes) -
                group.nodes)
        loop@ while (index < nodeIndexLimit) {
            if (current == groupLocation) break
            current++
            while (!reader.isGroup(current)) current++
            while (current < groupLocation) {
                val currentGroup = reader.group(current)
                val end = currentGroup.slots + current + 1
                if (groupLocation < end) continue@loop
                index += nodeCountOverrides[currentGroup] ?: currentGroup.nodes

                current = end
            }
            break
        }
        return index
    }

    /**
     * Records the operations necessary to move the applier the node affected by the previous
     * group to the new group.
     */
    private fun recordUpsAndDowns(oldGroup: Group, newGroup: Group, commonRoot: Group) {
        val nearestCommonRoot = nearestCommonRootOf(
            oldGroup,
            newGroup,
            commonRoot
        ) ?: commonRoot

        // Record ups for the nodes between oldGroup and nearestCommonRoot
        var current: Group? = oldGroup
        while (current != null && current != nearestCommonRoot) {
            if (current.isNode) recordUp()
            current = current.parent
        }

        // Record downs from nearestCommonRoot to newGroup
        doRecordDownsFor(newGroup, nearestCommonRoot)
    }

    private fun doRecordDownsFor(group: Group?, nearestCommonRoot: Group?) {
        if (group != null && group != nearestCommonRoot) {
            doRecordDownsFor(group.parent, nearestCommonRoot)
            @Suppress("UNCHECKED_CAST")
            if (group.isNode) recordDown(group.node as N)
        }
    }

    /**
     * Calculate the compound key (a semi-unique key produced for every group in the composition)
     * for [group]. Passing in the [recomposeGroup] and [recomposeKey] allows this method to exit
     * early.
     */
    private fun compoundKeyOf(group: Group?, recomposeGroup: Group, recomposeKey: Int): Int {
        return if (group == recomposeGroup) recomposeKey else (compoundKeyOf(
            (group ?: error("Detached group")).parent,
            recomposeGroup,
            recomposeKey
        ) rol 3) xor (if (group.dataKey != null) group.dataKey.hashCode() else group.key)
    }

    internal fun invalidate(scope: RecomposeScope): InvalidationResult {
        if (scope.defaultsInScope) {
            scope.defaultsInvalid = true
        }
        val anchor = scope.anchor
        if (anchor == null || insertTable.ownsAnchor(anchor))
            return InvalidationResult.IGNORED // The scope has not yet entered the composition
        val location = anchor.location(slotTable)
        if (location < 0)
            return InvalidationResult.IGNORED // The scope was removed from the composition

        invalidations.insertIfMissing(location, scope)
        if (isComposing && location >= reader.current) {
            // if we are invalidating a scope that is going to be traversed during this
            // composition.
            return InvalidationResult.IMMINENT
        }
        if (parentReference != null) {
            parentReference?.invalidate()
        } else {
            recomposer.scheduleRecompose(this)
        }
        return if (isComposing) InvalidationResult.DEFERRED else InvalidationResult.SCHEDULED
    }

    /**
     * Skip a group. Skips the group at the current location. This is only valid to call if the
     * composition is not inserting.
     */
    @ComposeCompilerApi
    fun skipCurrentGroup() {
        if (invalidations.isEmpty()) {
            skipGroup()
        } else {
            val reader = reader
            val key = reader.groupKey
            val dataKey = reader.groupDataKey
            updateCompoundKeyWhenWeEnterGroup(key, dataKey)
            startReaderGroup(reader.isNode, reader.groupData)
            recomposeToGroupEnd()
            reader.endGroup()
            updateCompoundKeyWhenWeExitGroup(key, dataKey)
        }
    }

    private fun skipReaderToGroupEnd() {
        groupNodeCount = reader.parentNodes
        reader.skipToGroupEnd()
    }

    /**
     * Skip to the end of the group opened by [startGroup].
     */
    @ComposeCompilerApi
    fun skipToGroupEnd() {
        check(groupNodeCount == 0) { "No nodes can be emitted before calling skipAndEndGroup" }
        if (invalidations.isEmpty()) {
            skipReaderToGroupEnd()
        } else {
            recomposeToGroupEnd()
        }
    }

    /**
     * Start a restart group. A restart group creates a recompose scope and sets it as the current
     * recompose scope of the composition. If the recompose scope is invalidated then this group
     * will be recomposed. A recompose scope can be invalidated by calling the lambda returned by
     * [androidx.compose.invalidate].
     */
    @ComposeCompilerApi
    fun startRestartGroup(key: Int) {
        start(key, null, false, null)
        addRecomposeScope(key)
    }

    @ComposeCompilerApi
    fun startRestartGroup(key: Int, sourceInformation: String?) {
        start(key, null, false, sourceInformation)
        addRecomposeScope(key)
    }

    private fun addRecomposeScope(key: Int) {
        if (inserting) {
            val scope = RecomposeScope(this, key)
            invalidateStack.push(scope)
            updateValue(scope)
        } else {
            val invalidation = invalidations.removeLocation(reader.parentLocation)
            val scope = reader.next() as RecomposeScope
            scope.requiresRecompose = invalidation != null
            invalidateStack.push(scope)
        }
    }

    /**
     * End a restart group. If the recompose scope was marked used during composition then a
     * [ScopeUpdateScope] is returned that allows attaching a lambda that will produce the same
     * composition as was produced by this group (including calling [startRestartGroup] and
     * [endRestartGroup]).
     */
    @ComposeCompilerApi
    fun endRestartGroup(): ScopeUpdateScope? {
        // This allows for the invalidate stack to be out of sync since this might be called during exception stack
        // unwinding that might have not called the doneJoin/endRestartGroup in the wrong order.
        val scope = if (invalidateStack.isNotEmpty()) invalidateStack.pop()
            else null
        scope?.requiresRecompose = false
        val result = if (scope != null && (scope.used || collectKeySources)) {
            if (scope.anchor == null) {
                scope.anchor = if (inserting)
                    insertTable.anchor(writer.parentLocation)
                else
                    slotTable.anchor(reader.parentLocation)
            }
            scope.defaultsInvalid = false
            scope
        } else {
            null
        }
        end(false)
        return result
    }

    /**
     * Synchronously recompose all invalidated groups. This collects the changes which must be
     * applied by [applyChanges] to have an effect.
     */
    @InternalComposeApi
    fun recompose(): Boolean {
        if (invalidations.isNotEmpty()) {
            trace("Compose:recompose") {
                nodeIndex = 0
                var complete = false
                try {
                    startRoot()
                    skipCurrentGroup()
                    endRoot()
                    complete = true
                } finally {
                    if (!complete) abortRoot()
                }
                finalizeCompose()
            }
            return true
        }
        return false
    }

    internal fun hasInvalidations() = invalidations.isNotEmpty()

    @Suppress("UNCHECKED_CAST")
    private var SlotWriter.node
        get() = nodeGroup.node as N
        set(value) { nodeGroup.node = value }
    private val SlotWriter.nodeGroup get() = get(current - 1) as NodeGroup
    private fun SlotWriter.nodeGroupAt(location: Int) = get(location) as NodeGroup
    private fun SlotWriter.nodeAt(location: Int) = nodeGroupAt(location).node
    @Suppress("UNCHECKED_CAST")
    private val SlotReader.node get() = nodeGroupAt(current - 1).node as N
    private fun SlotReader.nodeGroupAt(location: Int) = get(location) as NodeGroup
    @Suppress("UNCHECKED_CAST")
    private fun SlotReader.nodeAt(location: Int) = nodeGroupAt(location).node as N

    private fun validateNodeExpected() {
        check(nodeExpected) {
            "A call to createNode(), emitNode() or useNode() expected was not expected"
        }
        nodeExpected = false
    }

    private fun validateNodeNotExpected() {
        check(!nodeExpected) { "A call to createNode(), emitNode() or useNode() expected" }
    }

    /**
     * Add a raw change to the change list. Once [record] is called, the operation is realized
     * into the change list. The helper routines below reduce the number of operations that must
     * be realized to change the previous tree to the new tree as well as update the slot table
     * to prepare for the next composition.
     */
    private fun record(change: Change<N>) {
        changes.add(change)
    }

    /**
     * Record a change ensuring that, when it is applied, the state of the writer reflects the
     * current expected state. This will ensure that the applier is focused on the correct node
     * and the slot table writer slot is the same as the current reader's slot.
     */
    private fun recordOperation(change: Change<N>) {
        realizeInsertUps()
        realizeUps()
        realizeDowns()
        realizeOperationLocation(0)
        record(change)
    }

    /**
     * Record a change ensuring, when it is applied, that the applier is focused on the current
     * node.
     */
    private fun recordApplierOperation(change: Change<N>) {
        realizeInsertUps()
        realizeUps()
        realizeDowns()
        record(change)
    }

    /**
     * Record a change that will insert, remove or move a slot table group. This ensures the slot
     * table is prepared for the change be ensuring the parent group is started and then ended
     * as the group is left.
     */
    private fun recordSlotEditingOperation(offset: Int = 0, change: Change<N>) {
        realizeOperationLocation(offset)
        recordSlotEditing()
        record(change)
    }

    /**
     * Record a change ensuring, when it is applied, the write matches the current slot in the
     * reader.
     */
    private fun recordSlotTableOperation(offset: Int = 0, change: Change<N>) {
        realizeOperationLocation(offset)
        record(change)
    }

    // Navigation of the node tree is performed by recording all the locations of the nodes as
    // they are traversed by the reader and recording them in the downNodes array. When the node
    // navigation is realized all the downs in the down nodes is played to the applier.
    //
    // If an up is recorded before the corresponding down is realized then it is simply removed
    // from the downNodes stack.

    private var pendingUps = 0
    private var downNodes = Stack<N>()

    private fun realizeUps() {
        val count = pendingUps
        if (count > 0) {
            pendingUps = 0
            record { applier, _, _ -> repeat(count) { applier.up() } }
        }
    }

    private fun realizeDowns(nodes: Array<N>) {
        record { applier, _, _ ->
            for (index in nodes.indices) {
                applier.down(nodes[index])
            }
        }
    }

    private fun realizeDowns() {
        if (downNodes.isNotEmpty()) {
            @Suppress("UNCHECKED_CAST")
            realizeDowns(downNodes.toArray())
            downNodes.clear()
        }
    }

    private fun recordDown(node: N) {
        @Suppress("UNCHECKED_CAST")
        downNodes.push(node)
    }

    private fun recordUp() {
        if (downNodes.isNotEmpty()) {
            downNodes.pop()
        } else {
            pendingUps++
        }
    }

    private var pendingInsertUps = 0

    private fun recordInsertUp() {
        pendingInsertUps++
    }

    private fun realizeInsertUps() {
        if (pendingInsertUps > 0) {
            val count = pendingInsertUps
            record { applier, _, _ -> repeat(count) { applier.up() } }
            pendingInsertUps = 0
        }
    }

    // Navigating the writer slot is performed relatively as the location of a group in the writer
    // might be different than it is in the reader as groups can be inserted, deleted, or moved.
    //
    // writersReaderDelta tracks the difference between reader's current slot the current of
    // the writer must be before the recorded change is applied. Moving the writer to a location
    // is performed by advancing the writer the same the number of slots traversed by the reader
    // since the last write change. This works transparently for inserts. For deletes the number
    // of nodes deleted needs to be added to writersReaderDelta. When slots move the delta is
    // updated as if the move has already taken place. The delta is updated again once the group
    // begin edited is complete.
    //
    // The SlotTable requires that the group that contains any moves, inserts or removes must have
    // the group that contains the moved, inserted or removed groups be started with a startGroup
    // and terminated with a endGroup so the effects of the inserts, deletes, and moves can be
    // recorded correctly in its internal data structures. The startedGroups stack maintains the
    // groups that must be closed before we can move past the started group.

    /**
     * The skew or delta between where the writer will be and where the reader is now. This can
     * be thought of as the unrealized distance the writer must move to match the current slot in
     * the reader. When an operation affects the slot table the writer location must be realized
     * by moving the writer slot table the unrealized distance.
     */
    private var writersReaderDelta = 0

    /**
     * Record whether any groups were stared. If no groups were started then the root group
     * doesn't need to be started or ended either.
     */
    private var startedGroup = false

    /**
     * A stack of the location of the groups that were started.
     */
    private val startedGroups = IntStack()

    private fun realizeOperationLocation(offset: Int) {
        val location = reader.current + offset
        val distance = location - writersReaderDelta
        require(distance >= 0) { "Tried to seek backward" }
        if (distance > 0) {
            record { _, slots, _ -> slots.skip(distance) }
            writersReaderDelta = location
        }
    }

    private fun recordInsert(anchor: Anchor) {
        if (insertFixups.isEmpty()) {
            recordSlotEditingOperation { _, slots, _ ->
                slots.beginInsert()
                slots.moveFrom(insertTable, anchor.location(insertTable))
                slots.endInsert()
            }
        } else {
            val fixups = insertFixups.toMutableList()
            insertFixups.clear()
            recordSlotEditing()
            recordOperation { applier, slots, lifecycleManager ->
                insertTable.write { writer ->
                    for (fixup in fixups) {
                        fixup(applier, writer, lifecycleManager)
                    }
                }
                slots.beginInsert()
                slots.moveFrom(insertTable, anchor.location(insertTable))
                slots.endInsert()
            }
        }
    }

    private fun recordFixup(change: Change<N>) {
        realizeInsertUps()
        val anchor = insertAnchor
        val start = insertTable.anchorLocation(anchor)
        val location = writer.current - start
        insertFixups.add { _, slots, _ ->
            slots.current = location + insertTable.anchorLocation(anchor)
        }
        insertFixups.add(change)
    }

    /**
     * When a group is removed the reader will move but the writer will not so to ensure both the
     * writer and reader are tracking the same slot we advance the [writersReaderDelta] to
     * account for the removal.
     */
    private fun recordDelete() {
        recordSlotEditingOperation(change = removeCurrentGroupInstance)
        writersReaderDelta += reader.groupSize + 1
    }

    /**
     * Called when reader current is moved directly, such as when a group moves, to [location].
     */
    private fun recordReaderMoving(location: Int) {
        val distance = reader.current - writersReaderDelta

        // Ensure the next skip will account for the distance we have already travelled.
        writersReaderDelta = location - distance
    }

    private fun recordSlotEditing() {
        val location = reader.parentLocation

        if (startedGroups.peekOr(-1) != location) {
            // During initial composition (when the parent and current are both 0), no group needs
            // to be started.
            if (reader.current != 0) {
                val anchor = slotTable.anchor(location)
                startedGroups.push(location)
                startedGroup = true
                recordSlotTableOperation { _, slots, _ -> slots.ensureStarted(anchor) }
            }
        }
    }

    private fun recordSkipToGroupEnd() {
        recordSlotTableOperation(change = skipToEndGroupInstance)
        writersReaderDelta = reader.current
    }

    private fun recordEndGroup() {
        val location = reader.parentLocation
        val currentStartedGroup = startedGroups.peekOr(-1)
        check(currentStartedGroup <= location) { "Missed recording an endGroup" }
        if (startedGroups.peekOr(-1) == location) {
            startedGroups.pop()
            recordSlotTableOperation(change = endGroupInstance)
        }
    }

    private fun recordEndRoot() {
        if (startedGroup) {
            recordSlotTableOperation(change = endGroupInstance)
            startedGroup = false
        }
    }

    private fun finalizeCompose() {
        realizeInsertUps()
        realizeUps()
        check(pendingStack.isEmpty()) { "Start/end imbalance" }
        check(startedGroups.isEmpty()) { "Missed recording an endGroup()" }
        cleanUpCompose()
    }

    private fun cleanUpCompose() {
        pending = null
        nodeIndex = 0
        groupNodeCount = 0
        writersReaderDelta = 0
        currentCompoundKeyHash = 0
        nodeExpected = false
        startedGroup = false
        startedGroups.clear()
        nodeCountOverrides.clear()
    }

    private var previousRemove = -1
    private var previousMoveFrom = -1
    private var previousMoveTo = -1
    private var previousCount = 0

    private fun recordRemoveNode(nodeIndex: Int, count: Int) {
        if (count > 0) {
            check(nodeIndex >= 0) { "Invalid remove index $nodeIndex" }
            if (previousRemove == nodeIndex) previousCount += count
            else {
                realizeMovement()
                previousRemove = nodeIndex
                previousCount = count
            }
        }
    }

    private fun recordMoveNode(from: Int, to: Int, count: Int) {
        if (count > 0) {
            if (previousCount > 0 && previousMoveFrom == from - previousCount &&
                previousMoveTo == to - previousCount
            ) {
                previousCount += count
            } else {
                realizeMovement()
                previousMoveFrom = from
                previousMoveTo = to
                previousCount = count
            }
        }
    }

    private fun realizeMovement() {
        val count = previousCount
        previousCount = 0
        if (count > 0) {
            if (previousRemove >= 0) {
                val removeIndex = previousRemove
                previousRemove = -1
                recordApplierOperation { applier, _, _ -> applier.remove(removeIndex, count) }
            } else {
                val from = previousMoveFrom
                previousMoveFrom = -1
                val to = previousMoveTo
                previousMoveTo = -1
                recordApplierOperation { applier, _, _ -> applier.move(from, to, count) }
            }
        }
    }

    /**
     * A holder that will dispose of its [CompositionReference] when it leaves the composition
     * that will not have its reference made visible to user code.
     */
    // This warning becomes an error if its advice is followed since Composer needs its type param
    @Suppress("RemoveRedundantQualifierName")
    private class CompositionReferenceHolder<T>(
        val ref: Composer<T>.CompositionReferenceImpl
    ) : CompositionLifecycleObserver {
        override fun onLeave() {
            ref.dispose()
        }
    }

    private inner class CompositionReferenceImpl(
        val scope: RecomposeScope,
        override val compoundHashKey: Int,
        override val collectingKeySources: Boolean
    ) : CompositionReference() {
        var inspectionTables: MutableSet<MutableSet<SlotTable>>? = null
        val composers = mutableSetOf<Composer<*>>()

        fun dispose() {
            if (composers.isNotEmpty()) {
                inspectionTables?.let {
                    for (composer in composers) {
                        for (table in it)
                            table.remove(composer.slotTable)
                    }
                }
                composers.clear()
            }
        }

        override fun <N> registerComposer(composer: Composer<N>) {
            composers.add(composer)
        }

        override fun unregisterComposer(composer: Composer<*>) {
            inspectionTables?.forEach { it.remove(composer.slotTable) }
            composers.remove(composer)
        }

        override fun invalidate() {
            // continue invalidating up the spine of AmbientReferences
            parentReference?.invalidate()

            invalidate(scope)
        }

        override fun <T> getAmbient(key: Ambient<T>): T {
            val anchor = scope.anchor
            return if (anchor != null && anchor.valid) {
                parentAmbient(key, anchor.location(slotTable))
            } else {
                // The composition is composing and the ambient has not landed in the slot table
                // yet. This is a synchronous read from a sub-composition so the current ambient
                parentAmbient(key)
            }
        }

        override fun getAmbientScope(): AmbientMap {
            return ambientScopeAt(scope.anchor?.location(slotTable) ?: 0)
        }

        override fun recordInspectionTable(table: MutableSet<SlotTable>) {
            (inspectionTables ?: HashSet<MutableSet<SlotTable>>().also {
                inspectionTables = it
            }).add(table)
        }
    }

    private fun updateCompoundKeyWhenWeEnterGroup(groupKey: Int, dataKey: Any?) {
        if (dataKey == null)
            updateCompoundKeyWhenWeEnterGroupKeyHash(groupKey)
        else
            updateCompoundKeyWhenWeEnterGroupKeyHash(dataKey.hashCode())
    }

    private fun updateCompoundKeyWhenWeEnterGroupKeyHash(keyHash: Int) {
        currentCompoundKeyHash = (currentCompoundKeyHash rol 3) xor keyHash
    }

    private fun updateCompoundKeyWhenWeExitGroup(groupKey: Int, dataKey: Any?) {
        if (dataKey == null)
            updateCompoundKeyWhenWeExitGroupKeyHash(groupKey)
        else
            updateCompoundKeyWhenWeExitGroupKeyHash(dataKey.hashCode())
    }

    private fun updateCompoundKeyWhenWeExitGroupKeyHash(groupKey: Int) {
        currentCompoundKeyHash = (currentCompoundKeyHash xor groupKey.hashCode()) ror 3
    }
}

@Suppress("UNCHECKED_CAST")
/*inline */ class Updater<T>(val composer: Composer<*>, val node: T) {
    inline fun set(
        value: Int,
        /*crossinline*/
        block: T.(value: Int) -> Unit
    ) = with(composer) {
        if (inserting || nextSlot() != value) {
            updateValue(value)
            node.block(value)
//            val appliedBlock: T.(value: Int) -> Unit = { block(it) }
//            composer.apply(value, appliedBlock)
        }
    }

    inline fun <reified V> set(
        value: V,
        /*crossinline*/
        block: T.(value: V) -> Unit
    ) = with(composer) {
        if (inserting || nextSlot() != value) {
            updateValue(value)
            node.block(value)
//            val appliedBlock: T.(value: V) -> Unit = { block(it) }
//            composer.apply(value, appliedBlock)
        }
    }

    inline fun update(
        value: Int,
        /*crossinline*/
        block: T.(value: Int) -> Unit
    ) = with(composer) {
        if (inserting || nextSlot() != value) {
            updateValue(value)
            node.block(value)
//            val appliedBlock: T.(value: Int) -> Unit = { block(it) }
//            if (!inserting) composer.apply(value, appliedBlock)
        }
    }

    inline fun <reified V> update(
        value: V,
        /*crossinline*/
        block: T.(value: V) -> Unit
    ) = with(composer) {
        if (inserting || nextSlot() != value) {
            updateValue(value)
            node.block(value)
//            val appliedBlock: T.(value: V) -> Unit = { block(it) }
//            if (!inserting) composer.apply(value, appliedBlock)
        }
    }

    inline fun reconcile(
        block: T.() -> Unit
    ) {
        node.block()
    }
}

private fun SlotWriter.removeCurrentGroup(lifecycleManager: LifecycleManager) {
    // Notify the lifecycle manager of any observers leaving the slot table
    // The notification order should ensure that listeners are notified of leaving
    // in opposite order that they are notified of entering.

    // To ensure this order, we call `enters` as a pre-order traversal
    // of the group tree, and then call `leaves` in the inverse order.

    var groupEnd = Int.MAX_VALUE
    var index = 0
    val groupEndStack = IntStack()

    for (slot in groupSlots()) {
        when (slot) {
            is CompositionLifecycleObserver -> {
                lifecycleManager.leaving(slot)
            }
            is Group -> {
                groupEndStack.push(groupEnd)
                groupEnd = index + slot.slots
            }
            is RecomposeScope -> {
                slot.composer = null
            }
        }

        index++

        while (index >= groupEnd) {
            groupEnd = groupEndStack.pop()
        }
    }

    if (groupEndStack.isNotEmpty()) error("Invalid slot structure")

    // Remove the item from the slot table and notify the FrameManager if any
    // anchors are orphaned by removing the slots.
    if (removeGroup()) {
        FrameManager.scheduleCleanup()
    }
}

// Mutable list
private fun <K, V> multiMap() = HashMap<K, LinkedHashSet<V>>()

private fun <K, V> HashMap<K, LinkedHashSet<V>>.put(key: K, value: V) = getOrPut(key) {
    LinkedHashSet()
}.add(value)

private fun <K, V> HashMap<K, LinkedHashSet<V>>.remove(key: K, value: V) =
    get(key)?.let {
        it.remove(value)
        if (it.isEmpty()) remove(key)
    }

private fun <K, V> HashMap<K, LinkedHashSet<V>>.pop(key: K) = get(key)?.firstOrNull()?.also {
    remove(key, it)
}

private fun getKey(value: Any?, left: Any?, right: Any?): Any? = (value as? JoinedKey)?.let {
    if (it.left == left && it.right == right) value
    else getKey(it.left, left, right) ?: getKey(
        it.right,
        left,
        right
    )
}

// Invalidation helpers
private fun MutableList<Invalidation>.findLocation(location: Int): Int {
    var low = 0
    var high = size - 1

    while (low <= high) {
        val mid = (low + high).ushr(1) // safe from overflows
        val midVal = get(mid)
        val cmp = midVal.location.compareTo(location)

        if (cmp < 0)
            low = mid + 1
        else if (cmp > 0)
            high = mid - 1
        else
            return mid // key found
    }
    return -(low + 1) // key not found
}

private fun MutableList<Invalidation>.insertIfMissing(location: Int, scope: RecomposeScope) {
    val index = findLocation(location)
    if (index < 0) {
        add(-(index + 1), Invalidation(scope, location))
    }
}

private fun MutableList<Invalidation>.firstInRange(start: Int, end: Int): Invalidation? {
    val index = findLocation(start).let { if (it < 0) -(it + 1) else it }
    if (index < size) {
        val firstInvalidation = get(index)
        if (firstInvalidation.location <= end) return firstInvalidation
    }
    return null
}

private fun MutableList<Invalidation>.removeLocation(location: Int): Invalidation? {
    val index = findLocation(location)
    return if (index >= 0) removeAt(index) else null
}

private fun MutableList<Invalidation>.removeRange(start: Int, end: Int) {
    val index = findLocation(start).let { if (it < 0) -(it + 1) else it }
    while (index < size) {
        val validation = get(index)
        if (validation.location <= end) removeAt(index)
        else break
    }
}

private fun Boolean.asInt() = if (this) 1 else 0
private fun Int.asBool() = this != 0

@Composable
val currentComposer: Composer<*> get() {
    throw NotImplementedError("Implemented as an intrinsic")
}

// TODO: get rid of the need for this when we merge FrameManager and Recomposer together!
internal var currentComposerInternal: Composer<*>? = null

internal fun invokeComposable(composer: Composer<*>, composable: @Composable () -> Unit) {
    @Suppress("UNCHECKED_CAST")
    val realFn = composable as Function3<Composer<*>, Int, Int, Unit>
    realFn(composer, 0, 1)
}

internal fun <T> invokeComposableForResult(
    composer: Composer<*>,
    composable: @Composable () -> T
): T {
    @Suppress("UNCHECKED_CAST")
    val realFn = composable as Function3<Composer<*>, Int, Int, T>
    return realFn(composer, 0, 1)
}

private fun Group.distanceFrom(root: Group): Int {
    var count = 0
    var current: Group? = this
    while (current != null && current != root) {
        current = current.parent
        count++
    }
    return count
}

// find the nearest common root
private fun nearestCommonRootOf(a: Group, b: Group, common: Group): Group? {
    // Early outs, to avoid calling distanceFrom in trivial cases
    if (a == b) return a // A group is the nearest common root of itself
    if (a == common || b == common) return common // If either is common then common is nearest
    if (a.parent == b) return b // if b is a's parent b is the nearest common root
    if (b.parent == a) return a // if a is b's parent a is the nearest common root
    if (a.parent == b.parent) return a.parent // if a an b share a parent it is the nearest common

    // Find the nearest using distance from common
    var currentA: Group? = a
    var currentB: Group? = b
    val aDistance = a.distanceFrom(common)
    val bDistance = b.distanceFrom(common)
    repeat(aDistance - bDistance) { currentA = currentA?.parent }
    repeat(bDistance - aDistance) { currentB = currentB?.parent }

    // Both ca and cb are now the same distance from a known common root,
    // therefore, the first parent that is the same is the lowest common root.
    while (currentA != currentB) {
        currentA = currentA?.parent
        currentB = currentB?.parent
    }

    // ca == cb so it doesn't matter which is returned
    return currentA
}

private val removeCurrentGroupInstance: Change<*> = { _, slots, lifecycleManager ->
    slots.removeCurrentGroup(lifecycleManager)
}
private val skipToEndGroupInstance: Change<*> = { _, slots, _ -> slots.skipToGroupEnd() }
private val endGroupInstance: Change<*> = { _, slots, _ -> slots.endGroup() }

private val KeyInfo.joinedKey: Any get() = if (dataKey != null) JoinedKey(key, dataKey) else key

/*
 * Integer keys are arbitrary values in the biload range. The do not need to be unique as if
 * there is a chance they will collide with a compiler generated key they are paired with a
 * OpaqueKey to ensure they are unique.
 */

// rootKey doesn't need a corresponding OpaqueKey as it never has sibling nodes and will always
// a unique key.
private const val rootKey = 100

// An arbitrary value paired with a boxed Int or a JoinKey data key.
private const val nodeKey = 125

@PublishedApi
internal const val invocationKey = 200

@PublishedApi
internal val invocation = OpaqueKey("provider")

@PublishedApi
internal const val providerKey = 201

@PublishedApi
internal val provider = OpaqueKey("provider")

@PublishedApi
internal const val ambientMapKey = 202

@PublishedApi
internal val ambientMap = OpaqueKey("ambientMap")

@PublishedApi
internal const val providerValuesKey = 203

@PublishedApi
internal val providerValues = OpaqueKey("providerValues")

@PublishedApi
internal const val providerMapsKey = 204

@PublishedApi
internal val providerMaps = OpaqueKey("providers")

@PublishedApi
internal const val referenceKey = 206

@PublishedApi
internal val reference = OpaqueKey("reference")