/*
 * 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,
)
package androidx.compose.runtime

import androidx.compose.runtime.collection.IdentityArrayMap
import androidx.compose.runtime.collection.IdentityArraySet
import androidx.compose.runtime.external.kotlinx.collections.immutable.PersistentMap
import androidx.compose.runtime.external.kotlinx.collections.immutable.persistentHashMapOf
import androidx.compose.runtime.snapshots.currentSnapshot
import androidx.compose.runtime.snapshots.fastForEach
import androidx.compose.runtime.snapshots.fastForEachIndexed
import androidx.compose.runtime.snapshots.fastMap
import androidx.compose.runtime.snapshots.fastToSet
import androidx.compose.runtime.tooling.CompositionData
import androidx.compose.runtime.tooling.LocalInspectionTables
import kotlin.coroutines.CoroutineContext

internal typealias Change = (
    applier: Applier<*>,
    slots: SlotWriter,
    rememberManager: RememberManager
) -> 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
)

/**
 * An interface used during [ControlledComposition.applyChanges] and [Composition.dispose] to
 * track when [RememberObserver] instances and leave the composition an also allows recording
 * [SideEffect] calls.
 */
internal interface RememberManager {
    /**
     * The [RememberObserver] is being remembered by a slot in the slot table.
     */
    fun remembering(instance: RememberObserver)

    /**
     * The [RememberObserver] is being forgotten by a slot in the slot table.
     */
    fun forgetting(instance: RememberObserver)

    /**
     * The [effect] should be called when changes are being applied but after the remember/forget
     * notifications are sent.
     */
    fun sideEffect(effect: () -> Unit)
}

/**
 * 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<Int, GroupInfo>()
        for (index in 0 until keyInfos.size) {
            val keyInfo = keyInfos[index]
            @OptIn(InternalComposeApi::class)
            result[keyInfo.location] = GroupInfo(index, runningNodeIndex, keyInfo.nodes)
            @OptIn(InternalComposeApi::class)
            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
            }
        }
    }

    @OptIn(InternalComposeApi::class)
    fun registerInsert(keyInfo: KeyInfo, insertIndex: Int) {
        groupInfos[keyInfo.location] = GroupInfo(-1, insertIndex, 0)
    }

    fun updateNodeCount(group: Int, 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) {
                        val newIndex = childGroupInfo.nodeIndex + difference
                        if (newIndex >= 0)
                            childGroupInfo.nodeIndex = newIndex
                    }
                }
            }
            return true
        }
        return false
    }

    @OptIn(InternalComposeApi::class)
    fun slotPositionOf(keyInfo: KeyInfo) = groupInfos[keyInfo.location]?.slotIndex ?: -1

    @OptIn(InternalComposeApi::class)
    fun nodePositionOf(keyInfo: KeyInfo) = groupInfos[keyInfo.location]?.nodeIndex ?: -1

    @OptIn(InternalComposeApi::class)
    fun updatedNodeCountOf(keyInfo: KeyInfo) =
        groupInfos[keyInfo.location]?.nodeCount ?: keyInfo.nodes
}

private class Invalidation(
    /**
     * The recompose scope being invalidate
     */
    val scope: RecomposeScopeImpl,

    /**
     * The index of the group in the slot table being invalidated.
     */
    val location: Int,

    /**
     * The instances invalidating the scope. If this is `null` or empty then the scope is
     * unconditionally invalid. If it contains instances it is only invalid if at least on of the
     * instances is changed. This is used to track `DerivedState<*>` changes and only treat the
     * scope as invalid if the instance has changed.
     */
    var instances: IdentityArraySet<Any>?
) {
    fun isInvalid(): Boolean = scope.isInvalidFor(instances)
}

/**
 * Internal compose compiler plugin API that is used to update the function the composer will
 * call to recompose a recomposition scope. This should not be used or called directly.
 */
@ComposeCompilerApi
interface ScopeUpdateScope {
    /**
     * Called by generated code to update the recomposition scope with the function to call
     * recompose the scope. This is called by code generated by the compose compiler plugin and
     * should not be called directly.
     */
    fun updateScope(block: (Composer, 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 [ControlledComposition.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
}

/**
 * An instance to hold a value provided by [CompositionLocalProvider] and is created by the
 * [ProvidableCompositionLocal.provides] infixed operator. If [canOverride] is `false`, the
 * provided value will not overwrite a potentially already existing value in the scope.
 */
class ProvidedValue<T> internal constructor(
    val compositionLocal: CompositionLocal<T>,
    val value: T,
    val canOverride: Boolean
)

/**
 * A [CompositionLocal] map is is an immutable map that maps [CompositionLocal] keys to a provider
 * of their current value. It is used to represent the combined scope of all provided
 * [CompositionLocal]s.
 */
internal typealias CompositionLocalMap = PersistentMap<CompositionLocal<Any?>, State<Any?>>

internal inline fun CompositionLocalMap.mutate(
    mutator: (MutableMap<CompositionLocal<Any?>, State<Any?>>) -> Unit
): CompositionLocalMap = builder().apply(mutator).build()

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

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

@Composable
private fun compositionLocalMapOf(
    values: Array<out ProvidedValue<*>>,
    parentScope: CompositionLocalMap
): CompositionLocalMap {
    val result: CompositionLocalMap = persistentHashMapOf()
    return result.mutate {
        for (provided in values) {
            if (provided.canOverride || !parentScope.contains(provided.compositionLocal)) {
                @Suppress("UNCHECKED_CAST")
                it[provided.compositionLocal as CompositionLocal<Any?>] =
                    provided.compositionLocal.provided(provided.value)
            }
        }
    }
}

/**
 * A Compose compiler plugin API. DO NOT call directly.
 *
 * An instance used to track the identity of the movable content. Using a holder object allows
 * creating unique movable content instances from the same instance of a lambda. This avoids
 * using the identity of a lambda instance as it can be merged into a singleton or merged by later
 * rewritings and using its identity might lead to unpredictable results that might change from the
 * debug and release builds.
 */
@InternalComposeApi
class MovableContent<P>(val content: @Composable (parameter: P) -> Unit)

/**
 * A Compose compiler plugin API. DO NOT call directly.
 *
 * A reference to the movable content state prior to changes being applied.
 */
@InternalComposeApi
class MovableContentStateReference internal constructor(
    internal val content: MovableContent<Any?>,
    internal val parameter: Any?,
    internal val composition: ControlledComposition,
    internal val slotTable: SlotTable,
    internal val anchor: Anchor,
    internal val invalidations: List<Pair<RecomposeScopeImpl, IdentityArraySet<Any>?>>,
    internal val locals: CompositionLocalMap
)

/**
 * A Compose compiler plugin API. DO NOT call directly.
 *
 * A reference to the state of a [MovableContent] after changes have being applied. This is the
 * state that was removed from the `from` composition during [ControlledComposition.applyChanges]
 * and before it is inserted during [ControlledComposition.insertMovableContent].
 */
@InternalComposeApi
class MovableContentState internal constructor(
    internal val slotTable: SlotTable
)

/**
 * Composer is the interface that is targeted by the Compose Kotlin compiler plugin and used by
 * code generation helpers. It is highly recommended that direct calls these be avoided as the
 * runtime assumes that the calls are generated by the compiler and contain only a minimum amount
 * of state validation.
 */
sealed interface Composer {
    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Changes calculated and recorded during composition and are sent to [applier] which makes
     * the physical changes to the node tree implied by a composition.
     *
     * Composition has two discrete phases, 1) calculate and record changes and 2) making the
     * changes via the [applier]. While a [Composable] functions is executing, none of the
     * [applier] methods are called. The recorded changes are sent to the [applier] all at once
     * after all [Composable] functions have completed.
     */
    @ComposeCompilerApi
    val applier: Applier<*>

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Reflects that a new part of the composition is being created, that is, the composition
     * will insert new nodes into the resulting tree.
     */
    @ComposeCompilerApi
    val inserting: Boolean

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Reflects whether the [Composable] function can skip. Even if a [Composable] function is
     * called with the same parameters it might still need to run because, for example, a new
     * value was provided for a [CompositionLocal] created by [staticCompositionLocalOf].
     */
    @ComposeCompilerApi
    val skipping: Boolean

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Reflects whether the default parameter block of a [Composable] function is valid. This is
     * `false` if a [State] object read in the [startDefaults] group was modified since the last
     * time the [Composable] function was run.
     */
    @ComposeCompilerApi
    val defaultsInvalid: Boolean

    /**
     * A Compose internal property. DO NOT call directly. Use [currentRecomposeScope] instead.
     *
     * The invalidation current invalidation scope. An new invalidation scope is created whenever
     * [startRestartGroup] is called. when this scope's [RecomposeScope.invalidate] is called
     * then lambda supplied to [endRestartGroup]'s [ScopeUpdateScope] will be scheduled to be
     * run.
     */
    @InternalComposeApi
    val recomposeScope: RecomposeScope?

    /**
     * A Compose internal property. DO NOT call directly. Use [currentCompositeKeyHash] instead.
     *
     * This a hash value used to coordinate map externally stored state to the composition. For
     * example, this is used by saved instance state to preserve state across activity lifetime
     * boundaries.
     *
     * This value is not likely to be unique but is not guaranteed unique. There are known cases,
     * such as for loops without a [key], where the runtime does not have enough information to
     * make the compound key hash unique.
     */
    @InternalComposeApi
    val compoundKeyHash: Int

    // Groups

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Start a replacable group. A replacable group is a group that cannot be moved during
     * execution and can only either inserted, removed, or replaced. For example, the group
     * created by most control flow constructs such as an `if` statement are replacable groups.
     *
     * @param key A compiler generated key based on the source location of the call.
     */
    @ComposeCompilerApi
    fun startReplaceableGroup(key: Int)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Called at the end of a replacable group.
     *
     * @see startRestartGroup
     */
    @ComposeCompilerApi
    fun endReplaceableGroup()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Start a movable group. A movable group is one that can be moved based on the value of
     * [dataKey] which is typically supplied by the [key][androidx.compose.runtime.key] pseudo
     * compiler function.
     *
     * A movable group implements the semantics of [key][androidx.compose.runtime.key] which allows
     * the state and nodes generated by a loop to move with the composition implied by the key
     * passed to [key][androidx.compose.runtime.key].

     * @param key A compiler generated key based on the source location of the call.
     */
    @ComposeCompilerApi
    fun startMovableGroup(key: Int, dataKey: Any?)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Called at the end of a movable group.
     *
     * @see startMovableGroup
     */
    @ComposeCompilerApi
    fun endMovableGroup()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Called to start the group that calculates the default parameters of a [Composable] function.
     *
     * This method is called near the beginning of a [Composable] function with default
     * parameters and surrounds the remembered values or [Composable] calls necessary to produce
     * the default parameters. For example, for `model: Model = remember { DefaultModel() }` the
     * call to [remember] is called inside a [startDefaults] group.
     */
    @ComposeCompilerApi
    fun startDefaults()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Called at the end of defaults group.
     *
     * @see startDefaults
     */
    @ComposeCompilerApi
    fun endDefaults()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Called to record a group for a [Composable] function and starts a group that can be
     * recomposed on demand based on the lambda passed to
     * [updateScope][ScopeUpdateScope.updateScope] when [endRestartGroup] is called
     *
     * @param key A compiler generated key based on the source location of the call.
     * @return the instance of the composer to use for the rest of the function.
     */
    @ComposeCompilerApi
    fun startRestartGroup(key: Int): Composer

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Called to end a restart group.
     */
    @ComposeCompilerApi
    fun endRestartGroup(): ScopeUpdateScope?

    /**
     * A Compose internal API. DO NOT call directly.
     *
     * Request movable content be inserted at the current location. This will schedule with the
     * root composition parent a call to [insertMovableContent] with the correct
     * [MovableContentState] if one was released in another part of composition.
     */
    @InternalComposeApi
    fun insertMovableContent(value: MovableContent<*>, parameter: Any?)

    /**
     * A Compose internal API. DO NOT call directly.
     *
     * Perform a late composition that adds to the current late apply that will insert the given
     * references to [MovableContent] into the composition. If a [MovableContent] is paired
     * then this is a request to move a released [MovableContent] from a different location or
     * from a different composition. If it is not paired (i.e. the `second`
     * [MovableContentStateReference] is `null`) then new state for the [MovableContent] is
     * inserted into the composition.
     */
    @InternalComposeApi
    fun insertMovableContentReferences(
        references: List<Pair<MovableContentStateReference, MovableContentStateReference?>>
    )

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Record the source information string for a group. This must be immediately called after the
     * start of a group.
     *
     * @param sourceInformation An string value to that provides the compose tools enough
     * information to calculate the source location of calls to composable functions.
     */
    fun sourceInformation(sourceInformation: String)

    /**
     * A compose compiler plugin API. DO NOT call directly.
     *
     * Record a source information marker. This marker can be used in place of a group that would
     * have contained the information but was elided as the compiler plugin determined the group
     * was not necessary such as when a function is marked with [ReadOnlyComposable].
     *
     * @param key A compiler generated key based on the source location of the call.
     * @param sourceInformation An string value to that provides the compose tools enough
     * information to calculate the source location of calls to composable functions.
     *
     */
    fun sourceInformationMarkerStart(key: Int, sourceInformation: String)

    /**
     * A compose compiler plugin API. DO NOT call directly.
     *
     * Record the end of the marked source information range.
     */
    fun sourceInformationMarkerEnd()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Skips the composer to the end of the current group. This generated by the compiler to when
     * the body of a [Composable] function can be skipped typically because the parameters to the
     * function are equal to the values passed to it in the previous composition.
     */
    @ComposeCompilerApi
    fun skipToGroupEnd()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Skips the current group. This called by the compiler to indicate that the current group
     * can be skipped, for example, this is generated to skip the [startDefaults] group the
     * default group is was not invalidated.
     */
    @ComposeCompilerApi
    fun skipCurrentGroup()

    // Nodes

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Start a group that tracks a the code that will create or update a node that is generated
     * as part of the tree implied by the composition.
     */
    @ComposeCompilerApi
    fun startNode()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Start a group that tracks a the code that will create or update a node that is generated
     * as part of the tree implied by the composition. A reusable node can be reused in a
     * reusable group even if the group key is changed.
     */
    @ComposeCompilerApi
    fun startReusableNode()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Report the [factory] that will be used to create the node that will be generated into the
     * tree implied by the composition. This will only be called if [inserting] is is `true`.
     *
     * @param factory a factory function that will generate a node that will eventually be
     * supplied to [applier] though [Applier.insertBottomUp] and [Applier.insertTopDown].
     */
    @ComposeCompilerApi
    fun <T> createNode(factory: () -> T)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Report that the node is still being used. This will be called in the same location as the
     * corresponding [createNode] when [inserting] is `false`.
     */
    @ComposeCompilerApi
    fun useNode()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Called at the end of a node group.
     */
    @ComposeCompilerApi
    fun endNode()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Start a reuse group. Unlike a movable group, in a reuse group if the [dataKey] changes
     * the composition shifts into a reusing state cause the composer to act like it is
     * inserting (e.g. [cache] acts as if all values are invalid, [changed] always returns
     * true, etc.) even though it is recomposing until it encounters a reusable node. If the
     * node is reusable it temporarily shifts into recomposition for the node and then shifts
     * back to reusing for the children.  If a non-reusable node is generated the composer
     * shifts to inserting for the node and all of its children.
     *
     * @param key An compiler generated key based on the source location of the call.
     * @param dataKey A key provided by the [ReusableContent] composable function that is used to
     * determine if the composition shifts into a reusing state for this group.
     */
    @ComposeCompilerApi
    fun startReusableGroup(key: Int, dataKey: Any?)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Called at the end of a reusable group.
     */
    @ComposeCompilerApi
    fun endReusableGroup()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Temporarily disable reusing if it is enabled.
     */
    @ComposeCompilerApi
    fun disableReusing()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Reenable reusing if it was previously enabled before the last call to [disableReusing].
     */
    @ComposeCompilerApi
    fun enableReusing()

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Schedule [block] to called with [value]. This is intended to update the node generated by
     * [createNode] to changes discovered by composition.
     *
     * @param value the new value to be set into some property of the node.
     * @param block the block that sets the some property of the node to [value].
     */
    @ComposeCompilerApi
    fun <V, T> apply(value: V, block: T.(V) -> Unit)

    // State

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Produce an object that will compare equal an iff [left] and [right] compare equal to
     * some [left] and [right] of a previous call to [joinKey]. This is used by [key] to handle
     * multiple parameters. Since the previous composition stored [left] and [right] in a "join
     * key" object this call is used to return the previous value without an allocation instead
     * of blindly creating a new value that will be immediately discarded.
     *
     * @param left the first part of a a joined key.
     * @param right the second part of a joined key.
     * @return an object that will compare equal to a value previously returned by [joinKey] iff
     * [left] and [right] compare equal to the [left] and [right] passed to the previous call.
     */
    @ComposeCompilerApi
    fun joinKey(left: Any?, right: Any?): Any

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Remember a value into the composition state. This is a primitive method used to implement
     * [remember].
     *
     * @return [Composer.Empty] when [inserting] is `true` or the value passed to
     * [updateRememberedValue]
     * from the previous composition.
     *
     * @see cache
     */
    @ComposeCompilerApi
    fun rememberedValue(): Any?

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Update the remembered value correspond to the previous call to [rememberedValue]. The
     * [value] will be returned by [rememberedValue] for the next composition.
     */
    @ComposeCompilerApi
    fun updateRememberedValue(value: Any?)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Check [value] is different than the value used in the previous composition. This is used,
     * for example, to check parameter values to determine if they have changed.
     *
     * @param value the value to check
     * @return `true` if the value if [equals] of the previous value returns `false` when passed
     * [value].
     */
    @ComposeCompilerApi
    fun changed(value: Any?): Boolean

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Check [value] is different than the value used in the previous composition. This is used,
     * for example, to check parameter values to determine if they have changed.
     *
     * This overload is provided to avoid boxing [value] to compare with a potentially boxed
     * version of [value] in the composition state.
     *
     * @param value the value to check
     * @return `true` if the value if [equals] of the previous value returns `false` when passed
     * [value].
     */
    @ComposeCompilerApi
    fun changed(value: Boolean): Boolean = changed(value)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Check [value] is different than the value used in the previous composition. This is used,
     * for example, to check parameter values to determine if they have changed.
     *
     * This overload is provided to avoid boxing [value] to compare with a potentially boxed
     * version of [value] in the composition state.
     *
     * @param value the value to check
     * @return `true` if the value if [equals] of the previous value returns `false` when passed
     * [value].
     */
    @ComposeCompilerApi
    fun changed(value: Char): Boolean = changed(value)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Check [value] is different than the value used in the previous composition. This is used,
     * for example, to check parameter values to determine if they have changed.
     *
     * This overload is provided to avoid boxing [value] to compare with a potentially boxed
     * version of [value] in the composition state.
     *
     * @param value the value to check
     * @return `true` if the value if [equals] of the previous value returns `false` when passed
     * [value].
     */
    @ComposeCompilerApi
    fun changed(value: Byte): Boolean = changed(value)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Check [value] is different than the value used in the previous composition. This is used,
     * for example, to check parameter values to determine if they have changed.
     *
     * This overload is provided to avoid boxing [value] to compare with a potentially boxed
     * version of [value] in the composition state.
     *
     * @param value the value to check
     * @return `true` if the value if [equals] of the previous value returns `false` when passed
     * [value].
     */
    @ComposeCompilerApi
    fun changed(value: Short): Boolean = changed(value)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Check [value] is different than the value used in the previous composition. This is used,
     * for example, to check parameter values to determine if they have changed.
     *
     * This overload is provided to avoid boxing [value] to compare with a potentially boxed
     * version of [value] in the composition state.
     *
     * @param value the value to check
     * @return `true` if the value if [equals] of the previous value returns `false` when passed
     * [value].
     */
    @ComposeCompilerApi
    fun changed(value: Int): Boolean = changed(value)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Check [value] is different than the value used in the previous composition. This is used,
     * for example, to check parameter values to determine if they have changed.
     *
     * This overload is provided to avoid boxing [value] to compare with a potentially boxed
     * version of [value] in the composition state.
     *
     * @param value the value to check
     * @return `true` if the value if [equals] of the previous value returns `false` when passed
     * [value].
     */
    @ComposeCompilerApi
    fun changed(value: Float): Boolean = changed(value)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Check [value] is different than the value used in the previous composition. This is used,
     * for example, to check parameter values to determine if they have changed.
     *
     * This overload is provided to avoid boxing [value] to compare with a potentially boxed
     * version of [value] in the composition state.
     *
     * @param value the value to check
     * @return `true` if the value if [equals] of the previous value returns `false` when passed
     * [value].
     */
    @ComposeCompilerApi
    fun changed(value: Long): Boolean = changed(value)

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Check [value] is different than the value used in the previous composition. This is used,
     * for example, to check parameter values to determine if they have changed.
     *
     * This overload is provided to avoid boxing [value] to compare with a potentially boxed
     * version of [value] in the composition state.
     *
     * @param value the value to check
     * @return `true` if the value if [equals] of the previous value returns `false` when passed
     * [value].
     */
    @ComposeCompilerApi
    fun changed(value: Double): Boolean = changed(value)

    // Scopes

    /**
     * A Compose compiler plugin API. DO NOT call directly.
     *
     * Mark [scope] as used. [endReplaceableGroup] will return `null` unless [recordUsed] is
     * called on the corresponding [scope]. This is called implicitly when [State] objects are
     * read during composition is called when [currentRecomposeScope] is called in the
     * [Composable] function.
     */
    @InternalComposeApi
    fun recordUsed(scope: RecomposeScope)

    // Internal API

    /**
     * A Compose internal function. DO NOT call directly.
     *
     * Record a function to call when changes to the corresponding tree are applied to the
     * [applier]. This is used to implement [SideEffect].
     *
     * @param effect a lambda to invoke after the changes calculated up to this point have been
     * applied.
     */
    @InternalComposeApi
    fun recordSideEffect(effect: () -> Unit)

    /**
     * A Compose internal function. DO NOT call directly.
     *
     * Return the [CompositionLocal] value associated with [key]. This is the primitive function
     * used to implement [CompositionLocal.current].
     *
     * @param key the [CompositionLocal] value to be retrieved.
     */
    @InternalComposeApi
    fun <T> consume(key: CompositionLocal<T>): T

    /**
     * A Compose internal function. DO NOT call directly.
     *
     * Provide the given values for the associated [CompositionLocal] keys. This is the primitive
     * function used to implement [CompositionLocalProvider].
     *
     * @param values an array of value to provider key pairs.
     */
    @InternalComposeApi
    fun startProviders(values: Array<out ProvidedValue<*>>)

    /**
     * A Compose internal function. DO NOT call directly.
     *
     * End the provider group.
     *
     * @see startProviders
     */
    @InternalComposeApi
    fun endProviders()

    /**
     * A tooling API function. DO NOT call directly.
     *
     * The data stored for the composition. This is used by Compose tools, such as the preview and
     * the inspector, to display or interpret the result of composition.
     */
    val compositionData: CompositionData

    /**
     * A tooling API function. DO NOT call directly.
     *
     * Called by the inspector to inform the composer that it should collect additional
     * information about call parameters. By default, only collect parameter information for
     * scopes that are [recordUsed] has been called on. If [collectParameterInformation] is called
     * it will attempt to collect all calls even if the runtime doesn't need them.
     *
     * WARNING: calling this will result in a significant number of additional allocations that are
     * typically avoided.
     */
    fun collectParameterInformation()

    /**
     * A Compose internal function. DO NOT call directly.
     *
     * Build a composition context that can be used to created a subcomposition. A composition
     * reference is used to communicate information from this composition to the subcompositions
     * such as the all the [CompositionLocal]s provided at the point the reference is created.
     */
    @InternalComposeApi
    fun buildContext(): CompositionContext

    /**
     * A Compose internal function. DO NOT call directly.
     *
     * The coroutine context for the composition. This is used, for example, to implement
     * [LaunchedEffect]. This context is managed by the [Recomposer].
     */
    @InternalComposeApi
    val applyCoroutineContext: CoroutineContext
        @TestOnly
        get

    /**
     * The composition that is used to control this composer.
     */
    val composition: ControlledComposition
        @TestOnly get

    companion object {
        /**
         * A special value used to represent no value was stored (e.g. an empty slot). This is
         * returned, for example by [Composer.rememberedValue] while it is [Composer.inserting]
         * is `true`.
         */
        val Empty = object {
            override fun toString() = "Empty"
        }

        /**
         * Experimental API for specifying a tracer used for instrumenting frequent
         * operations, e.g. recompositions.
         */
        @ExperimentalComposeApi
        fun setTracer(tracer: CompositionTracer) {
            compositionTracer = tracer
        }
    }
}

/**
 * A Compose compiler plugin API. DO NOT call directly.
 *
 * Cache, that is remember, a value in the composition data of a composition. This is used to
 * implement [remember] and used by the compiler plugin to generate more efficient calls to
 * [remember] when it determines these optimizations are safe.
 */
@ComposeCompilerApi
inline fun <T> Composer.cache(invalid: Boolean, block: () -> T): T {
    @Suppress("UNCHECKED_CAST")
    return rememberedValue().let {
        if (invalid || it === Composer.Empty) {
            val value = block()
            updateRememberedValue(value)
            value
        } else it
    } as T
}

/**
 * A Compose internal function. DO NOT call directly.
 *
 * Records source information that can be used for tooling to determine the source location of
 * the corresponding composable function. By default, this function is declared as having no
 * side-effects. It is safe for code shrinking tools (such as R8 or ProGuard) to remove it.
 */
@ComposeCompilerApi
fun sourceInformation(composer: Composer, sourceInformation: String) {
    composer.sourceInformation(sourceInformation)
}

/**
 * A Compose internal function. DO NOT call directly.
 *
 * Records the start of a source information marker that can be used for tooling to determine the
 * source location of the corresponding composable function that otherwise don't require tracking
 * information such as [ReadOnlyComposable] functions. By default, this function is declared as
 * having no side-effects. It is safe for code shrinking tools (such as R8 or ProGuard) to remove
 * it.
 *
 * Important that both [sourceInformationMarkerStart] and [sourceInformationMarkerEnd] are removed
 * together or both kept. Removing only one will cause incorrect runtime behavior.
 */
@ComposeCompilerApi
fun sourceInformationMarkerStart(composer: Composer, key: Int, sourceInformation: String) {
    composer.sourceInformationMarkerStart(key, sourceInformation)
}

@ExperimentalComposeApi
interface CompositionTracer {
    fun traceEventStart(key: Int, info: String): Unit
    fun traceEventEnd(): Unit
}

@OptIn(ExperimentalComposeApi::class)
private var compositionTracer: CompositionTracer? = null

@OptIn(ExperimentalComposeApi::class)
@ComposeCompilerApi
fun isTraceInProgress(): Boolean = compositionTracer != null

@OptIn(ExperimentalComposeApi::class)
@ComposeCompilerApi
fun traceEventStart(key: Int, info: String): Unit =
    compositionTracer?.traceEventStart(key, info) ?: Unit

@OptIn(ExperimentalComposeApi::class)
@ComposeCompilerApi
fun traceEventEnd(): Unit = compositionTracer?.traceEventEnd() ?: Unit

/**
 * A Compose internal function. DO NOT call directly.
 *
 * Records the end of a source information marker that can be used for tooling to determine the
 * source location of the corresponding composable function that otherwise don't require tracking
 * information such as [ReadOnlyComposable] functions. By default, this function is declared as
 * having no side-effects. It is safe for code shrinking tools (such as R8 or ProGuard) to remove
 * it.
 *
 * Important that both [sourceInformationMarkerStart] and [sourceInformationMarkerEnd] are removed
 * together or both kept. Removing only one will cause incorrect runtime behavior.
 */
@ComposeCompilerApi
fun sourceInformationMarkerEnd(composer: Composer) {
    composer.sourceInformationMarkerEnd()
}

/**
 * Implementation of a composer for a mutable tree.
 */
internal class ComposerImpl(
    /**
     * An adapter that applies changes to the tree using the Applier abstraction.
     */
    override val applier: Applier<*>,

    /**
     * Parent of this composition; a [Recomposer] for root-level compositions.
     */
    private val parentContext: CompositionContext,

    /**
     * The slot table to use to store composition data
     */
    private val slotTable: SlotTable,

    private val abandonSet: MutableSet<RememberObserver>,

    private var changes: MutableList<Change>,

    private var lateChanges: MutableList<Change>,

    /**
     * The composition that owns this composer
     */
    override val composition: ControlledComposition
) : Composer {
    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 var nodeCountOverrides: IntArray? = null
    private var nodeCountVirtualOverrides: HashMap<Int, Int>? = null
    private var forceRecomposeScopes = false
    private var forciblyRecompose = false
    private var nodeExpected = false
    private val invalidations: MutableList<Invalidation> = mutableListOf()
    private val entersStack = IntStack()
    private var parentProvider: CompositionLocalMap = persistentHashMapOf()
    private val providerUpdates = HashMap<Int, CompositionLocalMap>()
    private var providersInvalid = false
    private val providersInvalidStack = IntStack()
    private var reusing = false
    private var reusingGroup = -1
    private var childrenComposing: Int = 0
    private var snapshot = currentSnapshot()

    private val invalidateStack = Stack<RecomposeScopeImpl>()

    internal var isComposing = false
        private set
    internal var isDisposed = false
        private set
    internal val areChildrenComposing get() = childrenComposing > 0

    internal val hasPendingChanges: Boolean get() = changes.isNotEmpty()

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

    internal var insertTable = SlotTable()

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

    override val applyCoroutineContext: CoroutineContext
        @TestOnly get() = parentContext.effectCoroutineContext

    /**
     * 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
    override fun startReplaceableGroup(key: Int) = start(key, null, false, null)

    /**
     * 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
    override 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
    @Suppress("unused")
    override fun startDefaults() = start(defaultsKey, 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
    @Suppress("unused")
    override fun endDefaults() {
        endGroup()
        val scope = currentRecomposeScope
        if (scope != null && scope.used) {
            scope.defaultsInScope = true
        }
    }

    @ComposeCompilerApi
    @Suppress("unused")
    override 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
    override fun startMovableGroup(key: Int, dataKey: Any?) = start(key, dataKey, false, null)

    /**
     * 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
    override fun endMovableGroup() = endGroup()

    /**
     * Start the composition. This should be called, and only be called, as the first group in
     * the composition.
     */
    @OptIn(InternalComposeApi::class)
    private fun startRoot() {
        reader = slotTable.openReader()
        startGroup(rootKey)

        // parent reference management
        parentContext.startComposing()
        parentProvider = parentContext.getCompositionLocalScope()
        providersInvalidStack.push(providersInvalid.asInt())
        providersInvalid = changed(parentProvider)
        if (!forceRecomposeScopes) {
            forceRecomposeScopes = parentContext.collectingParameterInformation
        }
        resolveCompositionLocal(LocalInspectionTables, parentProvider)?.let {
            it.add(slotTable)
            parentContext.recordInspectionTable(it)
        }
        startGroup(parentContext.compoundHashKey)
    }

    /**
     * End the composition. This should be called, and only be called, to end the first group in
     * the composition.
     */
    @OptIn(InternalComposeApi::class)
    private fun endRoot() {
        endGroup()
        parentContext.doneComposing()
        endGroup()
        recordEndRoot()
        finalizeCompose()
        reader.close()
        forciblyRecompose = false
    }

    /**
     * Discard a pending composition because an error was encountered during composition
     */
    @OptIn(InternalComposeApi::class)
    private fun abortRoot() {
        cleanUpCompose()
        pendingStack.clear()
        nodeIndexStack.clear()
        groupNodeCountStack.clear()
        entersStack.clear()
        providersInvalidStack.clear()
        providerUpdates.clear()
        reader.close()
        compoundKeyHash = 0
        childrenComposing = 0
        nodeExpected = false
        isComposing = false
        forciblyRecompose = false
    }

    internal fun changesApplied() {
        providerUpdates.clear()
    }

    /**
     * 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
    override var inserting: Boolean = false
        private set

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

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

    /**
     * Start collecting parameter information. This enables the tools API to always be able to
     * determine the parameter values of composable calls.
     */
    override fun collectParameterInformation() {
        forceRecomposeScopes = true
    }

    @OptIn(InternalComposeApi::class)
    internal fun dispose() {
        trace("Compose:Composer.dispose") {
            parentContext.unregisterComposer(this)
            invalidateStack.clear()
            invalidations.clear()
            changes.clear()
            providerUpdates.clear()
            applier.clear()
            isDisposed = true
        }
    }

    internal fun forceRecomposeScopes(): Boolean {
        return if (!forceRecomposeScopes) {
            forceRecomposeScopes = true
            forciblyRecompose = true
             true
        } else {
            false
        }
    }

    /**
     * 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
     */
    private fun startGroup(key: Int) = start(key, null, false, null)

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

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

    @OptIn(InternalComposeApi::class)
    private fun skipGroup() {
        groupNodeCount += reader.skipGroup()
    }

    /**
     * Start emitting a node. It is required that [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.
     */
    override fun startNode() {
        val key = if (inserting) nodeKey
        else if (reusing)
            if (reader.groupKey == nodeKey) nodeKeyReplace else nodeKey
        else if (reader.groupKey == nodeKeyReplace) nodeKeyReplace
        else nodeKey
        start(key, null, true, null)
        nodeExpected = true
    }

    override fun startReusableNode() {
        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")
    override fun <T> createNode(factory: () -> T) {
        validateNodeExpected()
        runtimeCheck(inserting) { "createNode() can only be called when inserting" }
        val insertIndex = nodeIndexStack.peek()
        val groupAnchor = writer.anchor(writer.parent)
        groupNodeCount++
        recordFixup { applier, slots, _ ->
            @Suppress("UNCHECKED_CAST")
            val node = factory()
            slots.updateNode(groupAnchor, node)
            @Suppress("UNCHECKED_CAST") val nodeApplier = applier as Applier<T>
            nodeApplier.insertTopDown(insertIndex, node)
            applier.down(node)
        }
        recordInsertUpFixup { applier, slots, _ ->
            @Suppress("UNCHECKED_CAST")
            val nodeToInsert = slots.node(groupAnchor)
            applier.up()
            @Suppress("UNCHECKED_CAST") val nodeApplier = applier as Applier<Any?>
            nodeApplier.insertBottomUp(insertIndex, nodeToInsert)
        }
    }

    /**
     * Mark the node that was created by [createNode] as used by composition.
     */
    @OptIn(InternalComposeApi::class)
    override fun useNode() {
        validateNodeExpected()
        runtimeCheck(!inserting) { "useNode() called while inserting" }
        recordDown(reader.node)
    }

    /**
     * Called to end the node group.
     */
    override fun endNode() = end(isNode = true)

    override fun startReusableGroup(key: Int, dataKey: Any?) {
        if (reader.groupKey == key && reader.groupAux != dataKey && reusingGroup < 0) {
            // Starting to reuse nodes
            reusingGroup = reader.currentGroup
            reusing = true
        }
        start(key, null, false, dataKey)
    }

    override fun endReusableGroup() {
        if (reusing && reader.parent == reusingGroup) {
            reusingGroup = -1
            reusing = false
        }
        end(isNode = false)
    }

    override fun disableReusing() {
        reusing = false
    }

    override fun enableReusing() {
        reusing = reusingGroup >= 0
    }

    /**
     * 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].
     */
    override fun <V, T> apply(value: V, block: T.(V) -> Unit) {
        val operation: Change = { applier, _, _ ->
            @Suppress("UNCHECKED_CAST")
            (applier.current as T).block(value)
        }
        if (inserting) recordFixup(operation)
        else recordApplierOperation(operation)
    }

    /**
     * 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
    @OptIn(InternalComposeApi::class)
    override fun joinKey(left: Any?, right: Any?): Any =
        getKey(reader.groupObjectKey, left, right) ?: JoinedKey(left, right)

    /**
     * Return the next value in the slot table and advance the current location.
     */
    @PublishedApi
    @OptIn(InternalComposeApi::class)
    internal fun nextSlot(): Any? = if (inserting) {
        validateNodeNotExpected()
        Composer.Empty
    } else reader.next().let { if (reusing) Composer.Empty else it }

    /**
     * Determine if the current slot table value is equal to the given value, if true, the value
     * is scheduled to be skipped during [ControlledComposition.applyChanges] and [changes] return
     * false; otherwise [ControlledComposition.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
    override fun changed(value: Any?): Boolean {
        return if (nextSlot() != value) {
            updateValue(value)
            true
        } else {
            false
        }
    }

    @ComposeCompilerApi
    override 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
    override 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
    override 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
    override 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
    override 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
    override 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
    override 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
    override 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 === Composer.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
    @OptIn(InternalComposeApi::class)
    internal fun updateValue(value: Any?) {
        if (inserting) {
            writer.update(value)
            if (value is RememberObserver) {
                record { _, _, rememberManager -> rememberManager.remembering(value) }
                abandonSet.add(value)
            }
        } else {
            val groupSlotIndex = reader.groupSlotIndex - 1
            if (value is RememberObserver) {
                abandonSet.add(value)
            }
            recordSlotTableOperation(forParent = true) { _, slots, rememberManager ->
                if (value is RememberObserver) {
                    rememberManager.remembering(value)
                }
                when (val previous = slots.set(groupSlotIndex, value)) {
                    is RememberObserver ->
                        rememberManager.forgetting(previous)
                    is RecomposeScopeImpl -> {
                        val composition = previous.composition
                        if (composition != null) {
                            previous.composition = null
                            composition.pendingInvalidScopes = true
                        }
                    }
                }
            }
        }
    }

    /**
     * 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
    @OptIn(InternalComposeApi::class)
    internal fun updateCachedValue(value: Any?) {
        updateValue(value)
    }

    override val compositionData: CompositionData get() = slotTable

    /**
     * Schedule a side effect to run when we apply composition changes.
     */
    override fun recordSideEffect(effect: () -> Unit) {
        record { _, _, rememberManager -> rememberManager.sideEffect(effect) }
    }

    /**
     * Return the current [CompositionLocal] scope which was provided by a parent group.
     */
    private fun currentCompositionLocalScope(group: Int? = null): CompositionLocalMap {
        if (inserting && writerHasAProvider) {
            var current = writer.parent
            while (current > 0) {
                if (writer.groupKey(current) == compositionLocalMapKey &&
                    writer.groupObjectKey(current) == compositionLocalMap
                ) {
                    @Suppress("UNCHECKED_CAST")
                    return writer.groupAux(current) as CompositionLocalMap
                }
                current = writer.parent(current)
            }
        }
        if (reader.size > 0) {
            var current = group ?: reader.parent
            while (current > 0) {
                if (reader.groupKey(current) == compositionLocalMapKey &&
                    reader.groupObjectKey(current) == compositionLocalMap
                ) {
                    @Suppress("UNCHECKED_CAST")
                    return providerUpdates[current]
                        ?: reader.groupAux(current) as CompositionLocalMap
                }
                current = reader.parent(current)
            }
        }
        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: CompositionLocalMap,
        currentProviders: CompositionLocalMap
    ): CompositionLocalMap {
        val providerScope = parentScope.mutate { it.putAll(currentProviders) }
        startGroup(providerMapsKey, providerMaps)
        changed(providerScope)
        changed(currentProviders)
        endGroup()
        return providerScope
    }

    @InternalComposeApi
    override fun startProviders(values: Array<out ProvidedValue<*>>) {
        val parentScope = currentCompositionLocalScope()
        startGroup(providerKey, provider)
        // The group is needed here because compositionLocalMapOf() 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) {
            compositionLocalMapOf(values, parentScope)
        }
        endGroup()
        val providers: CompositionLocalMap
        val invalid: Boolean
        if (inserting) {
            providers = updateProviderMapGroup(parentScope, currentProviders)
            invalid = false
            writerHasAProvider = true
        } else {
            @Suppress("UNCHECKED_CAST")
            val oldScope = reader.groupGet(0) as CompositionLocalMap

            @Suppress("UNCHECKED_CAST")
            val oldValues = reader.groupGet(1) as CompositionLocalMap

            // 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.currentGroup] = providers
        }
        providersInvalidStack.push(providersInvalid.asInt())
        providersInvalid = invalid
        start(compositionLocalMapKey, compositionLocalMap, false, providers)
    }

    @InternalComposeApi
    override fun endProviders() {
        endGroup()
        endGroup()
        providersInvalid = providersInvalidStack.pop().asBool()
    }

    @InternalComposeApi
    override fun <T> consume(key: CompositionLocal<T>): T =
        resolveCompositionLocal(key, currentCompositionLocalScope())

    /**
     * Create or use a memoized [CompositionContext] instance at this position in the slot table.
     */
    override fun buildContext(): CompositionContext {
        startGroup(referenceKey, reference)

        var ref = nextSlot() as? CompositionContextHolder
        if (ref == null) {
            ref = CompositionContextHolder(
                CompositionContextImpl(
                    compoundKeyHash,
                    forceRecomposeScopes
                )
            )
            updateValue(ref)
        }
        ref.ref.updateCompositionLocalScope(currentCompositionLocalScope())
        endGroup()

        return ref.ref
    }

    private fun <T> resolveCompositionLocal(
        key: CompositionLocal<T>,
        scope: CompositionLocalMap
    ): T = if (scope.contains(key)) {
        scope.getValueOf(key)
    } else {
        key.defaultValueHolder.value
    }

    /**
     * The number of changes that have been scheduled to be applied during
     * [ControlledComposition.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: RecomposeScopeImpl?
        get() = invalidateStack.let {
            if (childrenComposing == 0 && it.isNotEmpty()) it.peek() else null
        }

    private fun ensureWriter() {
        if (writer.closed) {
            writer = insertTable.openWriter()
            // Append to the end of the table
            writer.skipToGroupEnd()
            writerHasAProvider = false
        }
    }

    private fun createFreshInsertTable() {
        runtimeCheck(writer.closed)
        insertTable = SlotTable()
        writer = insertTable.openWriter().also { it.close() }
    }

    /**
     * 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.groupAux !== data) {
                recordSlotTableOperation { _, slots, _ ->
                    slots.updateAux(data)
                }
            }
            reader.startGroup()
        }
    }

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

        updateCompoundKeyWhenWeEnterGroup(key, objectKey, data)

        // 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()
            val startIndex = writer.currentGroup
            when {
                isNode -> writer.startNode(Composer.Empty)
                data != null -> writer.startData(key, objectKey ?: Composer.Empty, data)
                else -> writer.startGroup(key, objectKey ?: Composer.Empty)
            }
            pending?.let { pending ->
                val insertKeyInfo = KeyInfo(
                    key = key,
                    objectKey = -1,
                    location = insertedGroupVirtualIndex(startIndex),
                    nodes = -1,
                    index = 0
                )
                pending.registerInsert(insertKeyInfo, nodeIndex - pending.startIndex)
                pending.recordUsed(insertKeyInfo)
            }
            enterGroup(isNode, null)
            return
        }

        if (pending == null) {
            val slotKey = reader.groupKey
            if (slotKey == key && objectKey == reader.groupObjectKey) {
                // 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, objectKey)
            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
                ensureWriter()
                writer.beginInsert()
                val startIndex = writer.currentGroup
                when {
                    isNode -> writer.startNode(Composer.Empty)
                    data != null -> writer.startData(key, objectKey ?: Composer.Empty, data)
                    else -> writer.startGroup(key, objectKey ?: Composer.Empty)
                }
                insertAnchor = writer.anchor(startIndex)
                val insertKeyInfo = KeyInfo(
                    key = key,
                    objectKey = -1,
                    location = insertedGroupVirtualIndex(startIndex),
                    nodes = -1,
                    index = 0
                )
                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.

        if (inserting) {
            val parent = writer.parent
            updateCompoundKeyWhenWeExitGroup(
                writer.groupKey(parent),
                writer.groupObjectKey(parent),
                writer.groupAux(parent)
            )
        } else {
            val parent = reader.parent
            updateCompoundKeyWhenWeExitGroup(
                reader.groupKey(parent),
                reader.groupObjectKey(parent),
                reader.groupAux(parent)
            )
        }
        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.fastToSet()

            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.location, 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.currentGroup
            recordDelete()
            val nodesToRemove = reader.skipGroup()
            recordRemoveNode(removeIndex, nodesToRemove)
            invalidations.removeRange(startSlot, reader.currentGroup)
        }

        val inserting = inserting
        if (inserting) {
            if (isNode) {
                registerInsertUpFixup()
                expectedNodeCount = 1
            }
            reader.endEmpty()
            val parentGroup = writer.parent
            writer.endGroup()
            if (!reader.inEmpty) {
                val virtualIndex = insertedGroupVirtualIndex(parentGroup)
                writer.endInsert()
                writer.close()
                recordInsert(insertAnchor)
                this.inserting = false
                if (!slotTable.isEmpty) {
                    updateNodeCount(virtualIndex, 0)
                    updateNodeCountOverrides(virtualIndex, expectedNodeCount)
                }
            }
        } else {
            if (isNode) recordUp()
            recordEndGroup()
            val parentGroup = reader.parent
            val parentNodeCount = updatedNodeCount(parentGroup)
            if (expectedNodeCount != parentNodeCount) {
                updateNodeCountOverrides(parentGroup, expectedNodeCount)
            }
            if (isNode) {
                expectedNodeCount = 1
            }
            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.parent
        val end = parent + reader.groupSize(parent)
        val recomposeIndex = nodeIndex
        val recomposeCompoundKey = compoundKeyHash
        val oldGroupNodeCount = groupNodeCount
        var oldGroup = parent

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

            invalidations.removeLocation(location)

            if (firstInRange.isInvalid()) {
                recomposed = true

                reader.reposition(location)
                val newGroup = reader.currentGroup
                // Record the changes to the applier location
                recordUpsAndDowns(oldGroup, newGroup, parent)
                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,
                    recomposeIndex
                )

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

                firstInRange.scope.compose(this)

                // Restore the parent of the reader to the previous parent
                reader.restoreParent(parent)
            } else {
                // If the invalidation is not used restore the reads that were removed when the
                // the invalidation was recorded. This happens, for example, when on of a derived
                // state's dependencies changed but the derived state itself was not changed.
                invalidateStack.push(firstInRange.scope)
                firstInRange.scope.rereadTrackedInstances()
                invalidateStack.pop()
            }

            // 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.currentGroup, end)
        }

        if (recomposed) {
            recordUpsAndDowns(oldGroup, parent, parent)
            reader.skipToGroupEnd()
            val parentGroupNodes = updatedNodeCount(parent)
            nodeIndex = recomposeIndex + parentGroupNodes
            groupNodeCount = oldGroupNodeCount + parentGroupNodes
        } else {
            // No recompositions were requested in the range, skip it.
            skipReaderToGroupEnd()
        }
        compoundKeyHash = recomposeCompoundKey

        isComposing = wasComposing
    }

    /**
     * The index in the insertTable overlap with indexes the slotTable so the group index used to
     * track newly inserted groups is set to be negative offset from -2. This reserves -1 as the
     * root index which is the parent value returned by the root groups of the slot table.
     *
     * This function will also restore a virtual index to its index in the insertTable which is
     * not needed here but could be useful for debugging.
     */
    private fun insertedGroupVirtualIndex(index: Int) = -2 - index

    /**
     * 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: Int, newCount: Int) {
        // The value of group can be negative which indicates it is tracking an inserted group
        // instead of an existing group. The index is a virtual index calculated by
        // insertedGroupVirtualIndex which corresponds to the location of the groups to insert in
        // the insertTable.
        val currentCount = updatedNodeCount(group)
        if (currentCount != newCount) {
            // Update the overrides
            val delta = newCount - currentCount
            var current = group

            var minPending = pendingStack.size - 1
            while (current != -1) {
                val newCurrentNodes = updatedNodeCount(current) + delta
                updateNodeCount(current, newCurrentNodes)
                for (pendingIndex in minPending downTo 0) {
                    val pending = pendingStack.peek(pendingIndex)
                    if (pending != null && pending.updateNodeCount(current, newCurrentNodes)) {
                        minPending = pendingIndex - 1
                        break
                    }
                }
                @Suppress("LiftReturnOrAssignment")
                if (current < 0) {
                    current = reader.parent
                } else {
                    if (reader.isNode(current)) break
                    current = reader.parent(current)
                }
            }
        }
    }

    /**
     * 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: Int,
        recomposeGroup: Int,
        recomposeIndex: Int
    ): Int {
        // Find the anchor group which is either the recomposeGroup or the first parent node
        var anchorGroup = reader.parent(group)
        while (anchorGroup != recomposeGroup) {
            if (reader.isNode(anchorGroup)) break
            anchorGroup = reader.parent(anchorGroup)
        }

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

        // An early out if the group and anchor are the same
        if (anchorGroup == group) return index

        // Walk down from the anchor group counting nodes of siblings in front of this group
        var current = anchorGroup
        val nodeIndexLimit = index + (updatedNodeCount(anchorGroup) - reader.nodeCount(group))
        loop@ while (index < nodeIndexLimit) {
            if (current == groupLocation) break
            current++
            while (current < groupLocation) {
                val end = current + reader.groupSize(current)
                if (groupLocation < end) continue@loop
                index += updatedNodeCount(current)
                current = end
            }
            break
        }
        return index
    }

    private fun updatedNodeCount(group: Int): Int {
        if (group < 0) return nodeCountVirtualOverrides?.let { it[group] } ?: 0
        val nodeCounts = nodeCountOverrides
        if (nodeCounts != null) {
            val override = nodeCounts[group]
            if (override >= 0) return override
        }
        return reader.nodeCount(group)
    }

    private fun updateNodeCount(group: Int, count: Int) {
        if (updatedNodeCount(group) != count) {
            if (group < 0) {
                val virtualCounts = nodeCountVirtualOverrides ?: run {
                    val newCounts = HashMap<Int, Int>()
                    nodeCountVirtualOverrides = newCounts
                    newCounts
                }
                virtualCounts[group] = count
            } else {
                val nodeCounts = nodeCountOverrides ?: run {
                    val newCounts = IntArray(reader.size)
                    newCounts.fill(-1)
                    nodeCountOverrides = newCounts
                    newCounts
                }
                nodeCounts[group] = count
            }
        }
    }

    private fun clearUpdatedNodeCounts() {
        nodeCountOverrides = null
        nodeCountVirtualOverrides = null
    }

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

        // Record ups for the nodes between oldGroup and nearestCommonRoot
        var current = oldGroup
        while (current > 0 && current != nearestCommonRoot) {
            if (reader.isNode(current)) recordUp()
            current = reader.parent(current)
        }

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

    private fun doRecordDownsFor(group: Int, nearestCommonRoot: Int) {
        if (group > 0 && group != nearestCommonRoot) {
            doRecordDownsFor(reader.parent(group), nearestCommonRoot)
            if (reader.isNode(group)) recordDown(reader.nodeAt(group))
        }
    }

    /**
     * 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: Int, recomposeGroup: Int, recomposeKey: Int): Int {
        return if (group == recomposeGroup) recomposeKey else run {
            val groupKey = reader.groupCompoundKeyPart(group)
            if (groupKey == movableContentKey)
                groupKey
            else
                (
                    compoundKeyOf(
                        reader.parent(group),
                        recomposeGroup,
                        recomposeKey) rol 3
                ) xor groupKey
        }
    }

    private fun SlotReader.groupCompoundKeyPart(group: Int) =
        if (hasObjectKey(group)) {
            groupObjectKey(group)?.let {
                if (it is Enum<*>) it.ordinal else it.hashCode()
            } ?: 0
        } else groupKey(group).let {
            if (it == reuseKey) groupAux(group)?.let { aux ->
                if (aux == Composer.Empty) it else aux.hashCode()
            } ?: it else it
        }

    internal fun tryImminentInvalidation(scope: RecomposeScopeImpl, instance: Any?): Boolean {
        val anchor = scope.anchor ?: return false
        val location = anchor.toIndexFor(slotTable)
        if (isComposing && location >= reader.currentGroup) {
            // if we are invalidating a scope that is going to be traversed during this
            // composition.
            invalidations.insertIfMissing(location, scope, instance)
            return true
        }
        return false
    }

    @TestOnly
    internal fun parentKey(): Int {
        return if (inserting) {
            writer.groupKey(writer.parent)
        } else {
            reader.groupKey(reader.parent)
        }
    }

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

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

    /**
     * Skip to the end of the group opened by [startGroup].
     */
    @ComposeCompilerApi
    override fun skipToGroupEnd() {
        runtimeCheck(groupNodeCount == 0) {
            "No nodes can be emitted before calling skipAndEndGroup"
        }
        currentRecomposeScope?.scopeSkipped()
        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 invalidate on the object
     * returned by [androidx.compose.runtime.currentRecomposeScope].
     */
    @ComposeCompilerApi
    override fun startRestartGroup(key: Int): Composer {
        start(key, null, false, null)
        addRecomposeScope()
        return this
    }

    private fun addRecomposeScope() {
        if (inserting) {
            val scope = RecomposeScopeImpl(composition as CompositionImpl)
            invalidateStack.push(scope)
            updateValue(scope)
            scope.start(snapshot.id)
        } else {
            val invalidation = invalidations.removeLocation(reader.parent)
            val scope = reader.next() as RecomposeScopeImpl
            scope.requiresRecompose = invalidation != null
            invalidateStack.push(scope)
            scope.start(snapshot.id)
        }
    }

    /**
     * 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
    override 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
        // the correct order.
        val scope = if (invalidateStack.isNotEmpty()) invalidateStack.pop()
        else null
        scope?.requiresRecompose = false
        scope?.end(snapshot.id)?.let {
            record { _, _, _ -> it(composition) }
        }
        val result = if (scope != null &&
            !scope.skipped &&
            (scope.used || forceRecomposeScopes)
        ) {
            if (scope.anchor == null) {
                scope.anchor = if (inserting) {
                    writer.anchor(writer.parent)
                } else {
                    reader.anchor(reader.parent)
                }
            }
            scope.defaultsInvalid = false
            scope
        } else {
            null
        }
        end(isNode = false)
        return result
    }

    @InternalComposeApi
    override fun insertMovableContent(value: MovableContent<*>, parameter: Any?) {
        @Suppress("UNCHECKED_CAST")
        invokeMovableContentLambda(
            value as MovableContent<Any?>,
            currentCompositionLocalScope(),
            parameter,
            force = false
        )
    }

    private fun invokeMovableContentLambda(
        content: MovableContent<Any?>,
        locals: CompositionLocalMap,
        parameter: Any?,
        force: Boolean
    ) {
        // Start the movable content group
        startMovableGroup(movableContentKey, content)
        changed(parameter)

        if (inserting) writer.markGroup()

        // Capture the local providers at the point of the invocation. This allows detecting
        // changes to the locals as the value moves well as enables finding the correct providers
        // when applying late changes which might be very complicated otherwise.
        val providersChanged = if (inserting) false else reader.groupAux != locals
        if (providersChanged) providerUpdates[reader.currentGroup] = locals
        start(compositionLocalMapKey, compositionLocalMap, false, locals)

        // All movable content has a compound hash value rooted at the content itself so the hash
        // value doesn't change as the content moves in the tree.
        val savedCompoundKeyHash = compoundKeyHash
        compoundKeyHash = movableContentKey xor content.hashCode()

        // Either insert a place-holder to be inserted later (either created new or moved from
        // another location) or (re)compose the movable content. This is forced if a new value
        // needs to be created as a late change.
        if (inserting && !force) {
            writerHasAProvider = true
            // Create an anchor to the movable group
            val anchor = writer.anchor(writer.parent(writer.parent))
            val reference = MovableContentStateReference(
                content,
                parameter,
                composition,
                insertTable,
                anchor,
                emptyList(),
                currentCompositionLocalScope()
            )
            parentContext.insertMovableContent(reference)
        } else {
            val savedProvidersInvalid = providersInvalid
            providersInvalid = providersChanged
            invokeComposable(this, { content.content(parameter) })
            providersInvalid = savedProvidersInvalid
        }

        // Restore the state back to what is expected by the caller.
        compoundKeyHash = savedCompoundKeyHash
        endGroup()
        endMovableGroup()
    }

    @InternalComposeApi
    override fun insertMovableContentReferences(
        references: List<Pair<MovableContentStateReference, MovableContentStateReference?>>
    ) {
        fun positionToParentOf(slots: SlotWriter, applier: Applier<Any?>, index: Int) {
            while (!slots.indexInParent(index)) {
                slots.skipToGroupEnd()
                if (slots.isNode(slots.parent)) applier.up()
                slots.endGroup()
            }
        }

        fun currentNodeIndex(slots: SlotWriter): Int {
            val original = slots.currentGroup

            // Find parent node
            var current = slots.parent
            while (current >= 0 && !slots.isNode(current)) {
                current = slots.parent(current)
            }

            var index = 0
            current++
            while (current < original) {
                if (slots.indexInGroup(original, current)) {
                    if (slots.isNode(current)) index = 0
                    current++
                } else {
                    index += if (slots.isNode(current)) 1 else slots.nodeCount(current)
                    current += slots.groupSize(current)
                }
            }
            return index
        }

        fun positionToInsert(slots: SlotWriter, anchor: Anchor, applier: Applier<Any?>): Int {
            val destination = slots.anchorIndex(anchor)
            runtimeCheck(slots.currentGroup < destination)
            positionToParentOf(slots, applier, destination)
            var nodeIndex = currentNodeIndex(slots)
            while (slots.currentGroup < destination) {
                when {
                    slots.indexInCurrentGroup(destination) -> {
                        if (slots.isNode) {
                            applier.down(slots.node(slots.currentGroup))
                            nodeIndex = 0
                        }
                        slots.startGroup()
                    }
                    else -> nodeIndex += slots.skipGroup()
                }
            }

            runtimeCheck(slots.currentGroup == destination)
            return nodeIndex
        }

        withChanges(lateChanges) {
            record(resetSlotsInstance)
            references.fastForEach { (to, from) ->
                val anchor = to.anchor
                val location = to.slotTable.anchorIndex(anchor)
                var effectiveNodeIndex = 0
                realizeUps()
                // Insert content at the anchor point
                record { applier, slots, _ ->
                    @Suppress("UNCHECKED_CAST")
                    applier as Applier<Any?>
                    effectiveNodeIndex = positionToInsert(slots, anchor, applier)
                }
                if (from == null) {
                    val toSlotTable = to.slotTable
                    if (toSlotTable == insertTable) {
                        // We are going to compose reading the insert table which will also
                        // perform an insert. This would then cause both a reader and a writer to
                        // be created simultaneously which will throw an exception. To prevent
                        // that we release the old insert table and replace it with a fresh one.
                        // This allows us to read from the old table and write to the new table.

                        // This occurs when the placeholder version of movable content was inserted
                        // but no content was available to move so we now need to create the
                        // content.

                        createFreshInsertTable()
                    }
                    to.slotTable.read { reader ->
                        reader.reposition(location)
                        writersReaderDelta = location
                        val offsetChanges = mutableListOf<Change>()
                        recomposeMovableContent {
                            withChanges(offsetChanges) {
                                withReader(reader) {
                                    invokeMovableContentLambda(
                                        to.content,
                                        to.locals,
                                        to.parameter,
                                        force = true
                                    )
                                }
                            }
                        }
                        if (offsetChanges.isNotEmpty()) {
                            record { applier, slots, rememberManager ->
                                val offsetApplier = if (effectiveNodeIndex > 0)
                                    OffsetApplier(applier, effectiveNodeIndex) else applier
                                offsetChanges.fastForEach { change ->
                                    change(offsetApplier, slots, rememberManager)
                                }
                            }
                        }
                    }
                } else {
                    val nodesToInsert = from.slotTable.collectNodesFrom(from.anchor)
                    // Insert nodes if necessary
                    if (nodesToInsert.isNotEmpty()) {
                        record { applier, _, _ ->
                            val base = effectiveNodeIndex
                            @Suppress("UNCHECKED_CAST")
                            nodesToInsert.fastForEachIndexed { i, node ->
                                applier as Applier<Any?>
                                applier.insertBottomUp(base + i, node)
                                applier.insertTopDown(base + i, node)
                            }
                        }
                        val group = slotTable.anchorIndex(anchor)
                        updateNodeCount(
                            group,
                            updatedNodeCount(group) + nodesToInsert.size
                        )
                    }

                    // Copy the slot table into the anchor location
                    record { _, slots, _ ->
                        val state = parentContext.movableContentStateResolve(from)
                            ?: composeRuntimeError("Could not resolve state for movable content")

                        // The slot table contains the movable content group plus the group
                        // containing the movable content's table which then contains the actual
                        // state to be inserted. The state is at index 2 in the table (for the
                        // to groups) and is inserted into the provider group at offset 1 from the
                        // current location.
                        val anchors = slots.moveIntoGroupFrom(1, state.slotTable, 1)

                        // For all the anchors that moved, if the anchor is tracking a recompose
                        // scope, update it to reference its new composer.
                        if (anchors.isNotEmpty()) {
                            val toComposition = to.composition as CompositionImpl
                            anchors.fastForEach { anchor ->
                                // The recompose scope is always at slot 0 of a restart group.
                                val recomposeScope = slots.slot(anchor, 0) as? RecomposeScopeImpl
                                // Check for null as the anchor might not be for a recompose scope
                                recomposeScope?.let { it.composition = toComposition }
                            }
                        }
                    }

                    // Recompose over the moved content.
                    val fromTable = from.slotTable

                    fromTable.read { reader ->
                        withReader(reader) {
                            val newLocation = fromTable.anchorIndex(from.anchor)
                            reader.reposition(newLocation)
                            writersReaderDelta = newLocation
                            val offsetChanges = mutableListOf<Change>()

                            withChanges(offsetChanges) {
                                recomposeMovableContent(
                                    from = from.composition,
                                    to = to.composition,
                                    reader.currentGroup,
                                    invalidations = from.invalidations
                                ) {
                                    invokeMovableContentLambda(
                                            to.content,
                                            to.locals,
                                            to.parameter,
                                            force = true
                                    )
                                }
                            }
                            if (offsetChanges.isNotEmpty()) {
                                record { applier, slots, rememberManager ->
                                    val offsetApplier = if (effectiveNodeIndex > 0)
                                        OffsetApplier(applier, effectiveNodeIndex) else applier
                                    offsetChanges.fastForEach { change ->
                                        change(offsetApplier, slots, rememberManager)
                                    }
                                }
                            }
                        }
                    }
                }
                record(skipToGroupEndInstance)
            }
            record { applier, slots, _ ->
                @Suppress("UNCHECKED_CAST")
                applier as Applier<Any?>
                positionToParentOf(slots, applier, 0)
                slots.endGroup()
            }
            writersReaderDelta = 0
        }
        cleanUpCompose()
    }

    private inline fun <R> withChanges(newChanges: MutableList<Change>, block: () -> R): R {
        val savedChanges = changes
        try {
            changes = newChanges
            return block()
        } finally {
            changes = savedChanges
        }
    }

    private inline fun <R> withReader(reader: SlotReader, block: () -> R): R {
        val savedReader = this.reader
        val savedCountOverrides = nodeCountOverrides
        nodeCountOverrides = null
        try {
            this.reader = reader
            return block()
        } finally {
            this.reader = savedReader
            nodeCountOverrides = savedCountOverrides
        }
    }

    private fun <R> recomposeMovableContent(
        from: ControlledComposition? = null,
        to: ControlledComposition? = null,
        index: Int? = null,
        invalidations: List<Pair<RecomposeScopeImpl, IdentityArraySet<Any>?>> = emptyList(),
        block: () -> R
    ): R {
        val savedImplicitRootStart = this.implicitRootStart
        val savedIsComposing = isComposing
        val savedNodeIndex = nodeIndex
        try {
            implicitRootStart = false
            isComposing = true
            nodeIndex = 0
            invalidations.fastForEach { (scope, instances) ->
                if (instances != null) {
                    instances.forEach { instance ->
                        tryImminentInvalidation(scope, instance)
                    }
                } else {
                    tryImminentInvalidation(scope, null)
                }
            }
            return from?.delegateInvalidations(to, index ?: -1, block) ?: block()
        } finally {
            implicitRootStart = savedImplicitRootStart
            isComposing = savedIsComposing
            nodeIndex = savedNodeIndex
        }
    }

    @ComposeCompilerApi
    override fun sourceInformation(sourceInformation: String) {
        if (inserting) {
            writer.insertAux(sourceInformation)
        }
    }

    @ComposeCompilerApi
    override fun sourceInformationMarkerStart(key: Int, sourceInformation: String) {
        start(key, objectKey = null, isNode = false, data = sourceInformation)
    }

    @ComposeCompilerApi
    override fun sourceInformationMarkerEnd() {
        end(isNode = false)
    }

    /**
     * Synchronously compose the initial composition of [content]. This collects all the changes
     * which must be applied by [ControlledComposition.applyChanges] to build the tree implied by
     * [content].
     */
    internal fun composeContent(
        invalidationsRequested: IdentityArrayMap<RecomposeScopeImpl, IdentityArraySet<Any>?>,
        content: @Composable () -> Unit
    ) {
        runtimeCheck(changes.isEmpty()) { "Expected applyChanges() to have been called" }
        doCompose(invalidationsRequested, content)
    }

    internal fun prepareCompose(block: () -> Unit) {
        runtimeCheck(!isComposing) { "Preparing a composition while composing is not supported" }
        isComposing = true
        try {
            block()
        } finally {
            isComposing = false
        }
    }
    /**
     * Synchronously recompose all invalidated groups. This collects the changes which must be
     * applied by [ControlledComposition.applyChanges] to have an effect.
     */
    internal fun recompose(
        invalidationsRequested: IdentityArrayMap<RecomposeScopeImpl, IdentityArraySet<Any>?>
    ): Boolean {
        runtimeCheck(changes.isEmpty()) { "Expected applyChanges() to have been called" }
        // even if invalidationsRequested is empty we still need to recompose if the Composer has
        // some invalidations scheduled already. it can happen when during some parent composition
        // there were a change for a state which was used by the child composition. such changes
        // will be tracked and added into `invalidations` list.
        if (
            invalidationsRequested.isNotEmpty() ||
            invalidations.isNotEmpty() ||
            forciblyRecompose
        ) {
            doCompose(invalidationsRequested, null)
            return changes.isNotEmpty()
        }
        return false
    }

    private fun doCompose(
        invalidationsRequested: IdentityArrayMap<RecomposeScopeImpl, IdentityArraySet<Any>?>,
        content: (@Composable () -> Unit)?
    ) {
        runtimeCheck(!isComposing) { "Reentrant composition is not supported" }
        trace("Compose:recompose") {
            snapshot = currentSnapshot()
            providerUpdates.clear()
            invalidationsRequested.forEach { scope, set ->
                val location = scope.anchor?.location ?: return
                invalidations.add(Invalidation(scope, location, set))
            }
            invalidations.sortBy { it.location }
            nodeIndex = 0
            var complete = false
            isComposing = true
            try {
                startRoot()

                // vv Experimental for forced
                @Suppress("UNCHECKED_CAST")
                val savedContent = nextSlot()
                if (savedContent !== content && content != null) {
                    updateValue(content as Any?)
                }
                // ^^ Experimental for forced

                // Ignore reads of derivedStateOf recalculations
                observeDerivedStateRecalculations(
                    start = {
                        childrenComposing++
                    },
                    done = {
                        childrenComposing--
                    },
                ) {
                    if (content != null) {
                        startGroup(invocationKey, invocation)
                        invokeComposable(this, content)
                        endGroup()
                    } else if (
                        forciblyRecompose &&
                        savedContent != null &&
                        savedContent != Composer.Empty
                    ) {
                        startGroup(invocationKey, invocation)
                        @Suppress("UNCHECKED_CAST")
                        invokeComposable(this, savedContent as @Composable () -> Unit)
                        endGroup()
                    } else {
                        skipCurrentGroup()
                    }
                }
                endRoot()
                complete = true
            } finally {
                isComposing = false
                invalidations.clear()
                if (!complete) abortRoot()
            }
        }
    }

    val hasInvalidations get() = invalidations.isNotEmpty()

    private val SlotReader.node get() = node(parent)

    private fun SlotReader.nodeAt(index: Int) = node(index)

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

    private fun validateNodeNotExpected() {
        runtimeCheck(!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) {
        changes.add(change)
    }

    /**
     * Record a change ensuring, when it is applied, that the applier is focused on the current
     * node.
     */
    private fun recordApplierOperation(change: Change) {
        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 by ensuring the parent group is started and then ended
     * as the group is left.
     */
    private fun recordSlotEditingOperation(change: Change) {
        realizeOperationLocation()
        recordSlotEditing()
        record(change)
    }

    /**
     * Record a change ensuring, when it is applied, the write matches the current slot in the
     * reader.
     */
    private fun recordSlotTableOperation(forParent: Boolean = false, change: Change) {
        realizeOperationLocation(forParent)
        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<Any?>()

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

    private fun realizeDowns(nodes: Array<Any?>) {
        record { applier, _, _ ->
            for (index in nodes.indices) {
                @Suppress("UNCHECKED_CAST")
                val nodeApplier = applier as Applier<Any?>
                nodeApplier.down(nodes[index])
            }
        }
    }

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

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

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

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

    /**
     * During late change calculation the group start/end is handled by [insertMovableContentReferences]
     * directly instead of requiring implicit starts/end groups to be inserted.
     */
    private var implicitRootStart = true

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

    private fun realizeOperationLocation(forParent: Boolean = false) {
        val location = if (forParent) reader.parent else reader.currentGroup
        val distance = location - writersReaderDelta
        runtimeCheck(distance >= 0) {
            "Tried to seek backward"
        }
        if (distance > 0) {
            record { _, slots, _ -> slots.advanceBy(distance) }
            writersReaderDelta = location
        }
    }

    private fun recordInsert(anchor: Anchor) {
        if (insertFixups.isEmpty()) {
            val insertTable = insertTable
            recordSlotEditingOperation { _, slots, _ ->
                slots.beginInsert()
                slots.moveFrom(insertTable, anchor.toIndexFor(insertTable))
                slots.endInsert()
            }
        } else {
            val fixups = insertFixups.toMutableList()
            insertFixups.clear()
            realizeUps()
            realizeDowns()
            val insertTable = insertTable
            recordSlotEditingOperation { applier, slots, rememberManager ->
                insertTable.write { writer ->
                    fixups.fastForEach { fixup ->
                        fixup(applier, writer, rememberManager)
                    }
                }
                slots.beginInsert()
                slots.moveFrom(insertTable, anchor.toIndexFor(insertTable))
                slots.endInsert()
            }
        }
    }

    private fun recordFixup(change: Change) {
        insertFixups.add(change)
    }

    private val insertUpFixups = Stack<Change>()

    private fun recordInsertUpFixup(change: Change) {
        insertUpFixups.push(change)
    }

    private fun registerInsertUpFixup() {
        insertFixups.add(insertUpFixups.pop())
    }

    /**
     * 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() {
        // It is import that the movable content is reported first so it can be removed before the
        // group itself is removed.
        reportFreeMovableContent(reader.currentGroup)
        recordSlotEditingOperation(change = removeCurrentGroupInstance)
        writersReaderDelta += reader.groupSize
    }

    /**
     * Report any movable content that the group contains as being removed and ready to be moved.
     * Returns true if the group itself was removed.
     *
     * Returns the number of nodes left in place which is used to calculate the node index of
     * any nested calls.
     */
    private fun reportFreeMovableContent(groupBeingRemoved: Int) {

        fun reportGroup(group: Int, needsNodeDelete: Boolean, nodeIndex: Int): Int {
            // If the group has a mark (e.g. it is a movable content group), schedule it to be
            // removed and report that it is free to be moved to the parentContext. Nested
            // movable content is recomposed if necessary once the group has been claimed by
            // another insert. If the nested movable content ends up being removed this is reported
            // during that recomposition so there is no need to look at child movable content here.
            return if (reader.hasMark(group)) {
                @Suppress("UNCHECKED_CAST")
                val value = reader.groupObjectKey(group) as MovableContent<Any?>
                val parameter = reader.groupGet(group, 0)
                val anchor = reader.anchor(group)
                val end = group + reader.groupSize(group)
                val invalidations = this.invalidations.filterToRange(group, end).fastMap {
                    it.scope to it.instances
                }
                val reference = MovableContentStateReference(
                    value,
                    parameter,
                    composition,
                    slotTable,
                    anchor,
                    invalidations,
                    currentCompositionLocalScope(group)
                )
                parentContext.deletedMovableContent(reference)
                recordSlotEditing()
                record { _, slots, _ ->
                    val slotTable = SlotTable()

                    slotTable.write { writer ->
                        writer.beginInsert()
                        slots.moveTo(anchor, 1, writer)
                        writer.endInsert()
                    }
                    val state = MovableContentState(slotTable)
                    parentContext.movableContentStateReleased(reference, state)
                }
                if (needsNodeDelete) {
                    realizeMovement()
                    realizeUps()
                    realizeDowns()
                    val nodeCount = if (reader.isNode(group)) 1 else reader.nodeCount(group)
                    if (nodeCount > 0) {
                        recordRemoveNode(nodeIndex, nodeCount)
                    }
                    0 // These nodes were deleted
                } else reader.nodeCount(group)
            } else if (reader.containsMark(group)) {
                // Traverse the group freeing the child movable content. This group is known to
                // have at least one child that contains movable content because the group is
                // marked as containing a mark.
                val size = reader.groupSize(group)
                val end = group + size
                var current = group + 1
                var runningNodeCount = 0
                while (current < end) {
                    // A tree is not disassembled when it is removed, the root nodes of the
                    // sub-trees are removed, therefore, if we enter a node that contains movable
                    // content, the nodes should be removed so some future composition can
                    // re-insert them at a new location. Otherwise the applier will attempt to
                    // insert a node that already has a parent. If there is no node between the
                    // group removed and this group then the nodes will be removed by normal
                    // recomposition.
                    val isNode = reader.isNode(current)
                    if (isNode) {
                        realizeMovement()
                        recordDown(reader.node(current))
                    }
                    runningNodeCount += reportGroup(
                        group = current,
                        needsNodeDelete = isNode || needsNodeDelete,
                        nodeIndex = if (isNode) 0 else nodeIndex + runningNodeCount
                    )
                    if (isNode) {
                        realizeMovement()
                        recordUp()
                    }
                    current += reader.groupSize(current)
                }
                runningNodeCount
            } else reader.nodeCount(group)
        }
        reportGroup(groupBeingRemoved, needsNodeDelete = false, nodeIndex = 0)
        realizeMovement()
    }

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

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

    private fun recordSlotEditing() {
        // During initial composition (when the slot table is empty), no group needs
        // to be started.
        if (reader.size > 0) {
            val reader = reader
            val location = reader.parent

            if (startedGroups.peekOr(-1) != location) {
                if (!startedGroup && implicitRootStart) {
                    // We need to ensure the root group is started.
                    recordSlotTableOperation(change = startRootGroup)
                    startedGroup = true
                }
                val anchor = reader.anchor(location)
                startedGroups.push(location)
                recordSlotTableOperation { _, slots, _ -> slots.ensureStarted(anchor) }
            }
        }
    }

    private fun recordEndGroup() {
        val location = reader.parent
        val currentStartedGroup = startedGroups.peekOr(-1)
        runtimeCheck(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() {
        realizeUps()
        runtimeCheck(pendingStack.isEmpty()) { "Start/end imbalance" }
        runtimeCheck(startedGroups.isEmpty()) { "Missed recording an endGroup()" }
        cleanUpCompose()
    }

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

    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) {
            runtimeCheck(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 [CompositionContext] 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 CompositionContextHolder(
        val ref: ComposerImpl.CompositionContextImpl
    ) : RememberObserver {
        override fun onRemembered() { }
        override fun onAbandoned() {
            ref.dispose()
        }
        override fun onForgotten() {
            ref.dispose()
        }
    }

    private inner class CompositionContextImpl(
        override val compoundHashKey: Int,
        override val collectingParameterInformation: Boolean
    ) : CompositionContext() {
        var inspectionTables: MutableSet<MutableSet<CompositionData>>? = null
        val composers = mutableSetOf<ComposerImpl>()

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

        override fun registerComposer(composer: Composer) {
            super.registerComposer(composer as ComposerImpl)
            composers.add(composer)
        }

        override fun unregisterComposer(composer: Composer) {
            inspectionTables?.forEach { it.remove((composer as ComposerImpl).slotTable) }
            composers.remove(composer)
        }

        override fun registerComposition(composition: ControlledComposition) {
            parentContext.registerComposition(composition)
        }

        override fun unregisterComposition(composition: ControlledComposition) {
            parentContext.unregisterComposition(composition)
        }

        override val effectCoroutineContext: CoroutineContext
            get() = parentContext.effectCoroutineContext

        @Suppress("EXPERIMENTAL_ANNOTATION_ON_WRONG_TARGET")
        @OptIn(ExperimentalComposeApi::class)
        @get:OptIn(ExperimentalComposeApi::class)
        override val recomposeCoroutineContext: CoroutineContext
            get() = composition.recomposeCoroutineContext

        override fun composeInitial(
            composition: ControlledComposition,
            content: @Composable () -> Unit
        ) {
            parentContext.composeInitial(composition, content)
        }

        override fun invalidate(composition: ControlledComposition) {
            // Invalidate ourselves with our parent before we invalidate a child composer.
            // This ensures that when we are scheduling recompositions, parents always
            // recompose before their children just in case a recomposition in the parent
            // would also cause other recomposition in the child.
            // If the parent ends up having no real invalidations to process we will skip work
            // for that composer along a fast path later.
            // This invalidation process could be made more efficient as it's currently N^2 with
            // subcomposition meta-tree depth thanks to the double recursive parent walk
            // performed here, but we currently assume a low N.
            parentContext.invalidate(this@ComposerImpl.composition)
            parentContext.invalidate(composition)
        }

        override fun invalidateScope(scope: RecomposeScopeImpl) {
            parentContext.invalidateScope(scope)
        }

        // This is snapshot state not because we need it to be observable, but because
        // we need changes made to it in composition to be visible for the rest of the current
        // composition and not become visible outside of the composition process until composition
        // succeeds.
        private var compositionLocalScope by mutableStateOf<CompositionLocalMap>(
            persistentHashMapOf()
        )

        override fun getCompositionLocalScope(): CompositionLocalMap = compositionLocalScope

        fun updateCompositionLocalScope(scope: CompositionLocalMap) {
            compositionLocalScope = scope
        }

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

        override fun startComposing() {
            childrenComposing++
        }

        override fun doneComposing() {
            childrenComposing--
        }

        override fun insertMovableContent(reference: MovableContentStateReference) {
            parentContext.insertMovableContent(reference)
        }

        override fun deletedMovableContent(reference: MovableContentStateReference) {
            parentContext.deletedMovableContent(reference)
        }

        override fun movableContentStateResolve(
            reference: MovableContentStateReference
        ): MovableContentState? = parentContext.movableContentStateResolve(reference)

        override fun movableContentStateReleased(
            reference: MovableContentStateReference,
            data: MovableContentState
        ) {
            parentContext.movableContentStateReleased(reference, data)
        }
    }

    private fun updateCompoundKeyWhenWeEnterGroup(groupKey: Int, dataKey: Any?, data: Any?) {
        if (dataKey == null)
            if (data != null && groupKey == reuseKey && data != Composer.Empty)
                updateCompoundKeyWhenWeEnterGroupKeyHash(data.hashCode())
            else
                updateCompoundKeyWhenWeEnterGroupKeyHash(groupKey)
        else if (dataKey is Enum<*>)
            updateCompoundKeyWhenWeEnterGroupKeyHash(dataKey.ordinal)
        else
            updateCompoundKeyWhenWeEnterGroupKeyHash(dataKey.hashCode())
    }

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

    private fun updateCompoundKeyWhenWeExitGroup(groupKey: Int, dataKey: Any?, data: Any?) {
        if (dataKey == null)
            if (data != null && groupKey == reuseKey && data != Composer.Empty)
                updateCompoundKeyWhenWeExitGroupKeyHash(data.hashCode())
            else
                updateCompoundKeyWhenWeExitGroupKeyHash(groupKey)
        else if (dataKey is Enum<*>)
            updateCompoundKeyWhenWeExitGroupKeyHash(dataKey.ordinal)
        else
            updateCompoundKeyWhenWeExitGroupKeyHash(dataKey.hashCode())
    }

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

    override val recomposeScope: RecomposeScope? get() = currentRecomposeScope
    override fun rememberedValue(): Any? = nextSlot()
    override fun updateRememberedValue(value: Any?) = updateValue(value)
    override fun recordUsed(scope: RecomposeScope) { (scope as? RecomposeScopeImpl)?.used = true }
}

/**
 * A helper receiver scope class used by [ComposeNode] to help write code to initialized and update a
 * node.
 *
 * @see ComposeNode
 */
@Suppress("INLINE_CLASS_DEPRECATED", "EXPERIMENTAL_FEATURE_WARNING")
inline class Updater<T> constructor(
    @PublishedApi internal val composer: Composer
) {
    /**
     * Set the value property of the emitted node.
     *
     * Schedules [block] to be run when the node is first created or when [value] is different
     * than the previous composition.
     *
     * @see update
     */
    @Suppress("NOTHING_TO_INLINE") // Inlining the compare has noticeable impact
    inline fun set(
        value: Int,
        noinline block: T.(value: Int) -> Unit
    ) = with(composer) {
        if (inserting || rememberedValue() != value) {
            updateRememberedValue(value)
            composer.apply(value, block)
        }
    }

    /**
     * Set the value property of the emitted node.
     *
     * Schedules [block] to be run when the node is first created or when [value] is different
     * than the previous composition.
     *
     * @see update
     */
    fun <V> set(
        value: V,
        block: T.(value: V) -> Unit
    ) = with(composer) {
        if (inserting || rememberedValue() != value) {
            updateRememberedValue(value)
            composer.apply(value, block)
        }
    }

    /**
     * Update the value of a property of the emitted node.
     *
     * Schedules [block] to be run when [value] is different than the previous composition. It is
     * different than [set] in that it does not run when the node is created. This is used when
     * initial value set by the [ComposeNode] in the constructor callback already has the correct value.
     * For example, use [update} when [value] is passed into of the classes constructor
     * parameters.
     *
     * @see set
     */
    @Suppress("NOTHING_TO_INLINE") // Inlining the compare has noticeable impact
    inline fun update(
        value: Int,
        noinline block: T.(value: Int) -> Unit
    ) = with(composer) {
        val inserting = inserting
        if (inserting || rememberedValue() != value) {
            updateRememberedValue(value)
            if (!inserting) apply(value, block)
        }
    }

    /**
     * Update the value of a property of the emitted node.
     *
     * Schedules [block] to be run when [value] is different than the previous composition. It is
     * different than [set] in that it does not run when the node is created. This is used when
     * initial value set by the [ComposeNode] in the constructor callback already has the correct value.
     * For example, use [update} when [value] is passed into of the classes constructor
     * parameters.
     *
     * @see set
     */
    fun <V> update(
        value: V,
        block: T.(value: V) -> Unit
    ) = with(composer) {
        val inserting = inserting
        if (inserting || rememberedValue() != value) {
            updateRememberedValue(value)
            if (!inserting) apply(value, block)
        }
    }

    /**
     * Initialize emitted node.
     *
     * Schedule [block] to be executed after the node is created.
     *
     * This is only executed once. The can be used to call a method or set a value on a node
     * instance that is required to be set after one or more other properties have been set.
     *
     * @see reconcile
     */
    fun init(block: T.() -> Unit) {
        if (composer.inserting) composer.apply<Unit, T>(Unit) {
            block()
        }
    }

    /**
     * Reconcile the node to the current state.
     *
     * This is used when [set] and [update] are insufficient to update the state of the node
     * based on changes passed to the function calling [ComposeNode].
     *
     * Schedules [block] to execute. As this unconditionally schedules [block] to executed it
     * might be executed unnecessarily as no effort is taken to ensure it only executes when the
     * values [block] captures have changed. It is highly recommended that [set] and [update] be
     * used instead as they will only schedule their blocks to executed when the value passed to
     * them has changed.
     */
    @Suppress("MemberVisibilityCanBePrivate")
    fun reconcile(block: T.() -> Unit) {
        composer.apply<Unit, T>(Unit) {
            this.block()
        }
    }
}
@Suppress("INLINE_CLASS_DEPRECATED", "EXPERIMENTAL_FEATURE_WARNING")
inline class SkippableUpdater<T> constructor(
    @PublishedApi internal val composer: Composer
) {
    inline fun update(block: Updater<T>.() -> Unit) {
        composer.startReplaceableGroup(0x1e65194f)
        Updater<T>(composer).block()
        composer.endReplaceableGroup()
    }
}

internal fun SlotWriter.removeCurrentGroup(rememberManager: RememberManager) {
    // 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.

    for (slot in groupSlots()) {
        when (slot) {
            is RememberObserver -> {
                rememberManager.forgetting(slot)
            }
            is RecomposeScopeImpl -> {
                val composition = slot.composition
                if (composition != null) {
                    composition.pendingInvalidScopes = true
                    slot.composition = null
                }
            }
        }
    }

    removeGroup()
}

// 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)

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

private fun MutableList<Invalidation>.findInsertLocation(location: Int): Int =
    findLocation(location).let { if (it < 0) -(it + 1) else it }

private fun MutableList<Invalidation>.insertIfMissing(
    location: Int,
    scope: RecomposeScopeImpl,
    instance: Any?
) {
    val index = findLocation(location)
    if (index < 0) {
        add(
            -(index + 1),
            Invalidation(
                scope,
                location,
                instance?.let { i ->
                    IdentityArraySet<Any>().also { it.add(i) }
                }
            )
        )
    } else {
        if (instance == null) {
            get(index).instances = null
        } else {
            get(index).instances?.add(instance)
        }
    }
}

private fun MutableList<Invalidation>.firstInRange(start: Int, end: Int): Invalidation? {
    val index = findInsertLocation(start)
    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 = findInsertLocation(start)
    while (index < size) {
        val validation = get(index)
        if (validation.location < end) removeAt(index)
        else break
    }
}

private fun MutableList<Invalidation>.filterToRange(
    start: Int,
    end: Int
): MutableList<Invalidation> {
    val result = mutableListOf<Invalidation>()
    var index = findInsertLocation(start)
    while (index < size) {
        val invalidation = get(index)
        if (invalidation.location < end) result.add(invalidation)
        else break
        index++
    }
    return result
}

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

private fun SlotTable.collectNodesFrom(anchor: Anchor): List<Any?> {
    val result = mutableListOf<Any?>()
    read { reader ->
        val index = anchorIndex(anchor)
        fun collectFromGroup(group: Int) {
            if (reader.isNode(group)) {
                result.add(reader.node(group))
            } else {
                var current = group + 1
                val end = group + reader.groupSize(group)
                while (current < end) {
                    collectFromGroup(current)
                    current += reader.groupSize(current)
                }
            }
        }
        collectFromGroup(index)
    }
    return result
}

private fun SlotReader.distanceFrom(index: Int, root: Int): Int {
    var count = 0
    var current = index
    while (current > 0 && current != root) {
        current = parent(current)
        count++
    }
    return count
}

// find the nearest common root
private fun SlotReader.nearestCommonRootOf(a: Int, b: Int, common: Int): Int {
    // 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 (parent(a) == b) return b // if b is a's parent b is the nearest common root
    if (parent(b) == a) return a // if a is b's parent a is the nearest common root
    if (parent(a) == parent(b)) return parent(a) // if a an b share a parent it is common

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

    // 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 = parent(currentA)
        currentB = parent(currentB)
    }

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

private val removeCurrentGroupInstance: Change = { _, slots, rememberManager ->
    slots.removeCurrentGroup(rememberManager)
}

private val skipToGroupEndInstance: Change = { _, slots, _ -> slots.skipToGroupEnd() }

private val endGroupInstance: Change = { _, slots, _ -> slots.endGroup() }

private val startRootGroup: Change = { _, slots, _ -> slots.ensureStarted(0) }

private val resetSlotsInstance: Change = { _, slots, _ -> slots.reset() }

private val KeyInfo.joinedKey: Any get() = if (objectKey != null) JoinedKey(key, objectKey) 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 key value for a node.
private const val nodeKey = 125

// An arbitrary key value for a node used to force the node to be replaced.
private const val nodeKeyReplace = 126

// An arbitrary key value for a node used to force the node to be replaced.
private const val defaultsKey = -127

@PublishedApi
internal const val invocationKey = 200

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

@PublishedApi
internal const val providerKey = 201

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

@PublishedApi
internal const val compositionLocalMapKey = 202

@PublishedApi
internal val compositionLocalMap: Any = OpaqueKey("compositionLocalMap")

@PublishedApi
internal const val providerValuesKey = 203

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

@PublishedApi
internal const val providerMapsKey = 204

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

@PublishedApi
internal const val referenceKey = 206

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

@PublishedApi
internal const val reuseKey = 207

internal inline fun runtimeCheck(value: Boolean, lazyMessage: () -> Any) {
    if (!value) {
        val message = lazyMessage()
        composeRuntimeError(message.toString())
    }
}

internal fun runtimeCheck(value: Boolean) = runtimeCheck(value) { "Check failed" }

internal fun composeRuntimeError(message: String): Nothing {
    error(
        "Compose Runtime internal error. Unexpected or incorrect use of the Compose " +
            "internal runtime API ($message). Please report to Google or use " +
            "https://goo.gle/compose-feedback"
    )
}