compose/compose-runtime/src/commonMain/kotlin/androidx/compose/Composer.kt - platform/frameworks/support - Git at Google

 /*
  * Copyright 2019 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package androidx.compose

 import androidx.compose.SlotTable.Companion.EMPTY
 import kotlin.collections.isNotEmpty

 /**
  * This is here because outdated versions of the compose IDE plugin expect to find it.
  * Without it, calls to [remember] are seen as errors, which breaks inference of [state] and more.
  *
  * This API is no longer needed in any way by the compiler, but we still need this API
  * to be here to support versions of Android Studio that are still looking for it. Without it,
  * valid composable code will look broken in the IDE. Remove this after we have left some time to
  * get all versions of Studio upgraded.
  * TODO b/152059242
  */
 @Deprecated(
     "This property should not be called directly. It is only used by the compiler.",
     replaceWith = ReplaceWith("currentComposer")
 )
 internal val composer: Composer<*> get() = error(
     "This property should not be called directly. It is only used by the compiler."
 )

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

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

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

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

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

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

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

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

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

     /**
      * Get the next key information for the given key.
      */
     fun getNext(key: Any): KeyInfo? = keyMap.pop(key)

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

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

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

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

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

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

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

 private val RootKey = OpaqueKey("root")

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

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

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

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

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

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

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

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

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

     /**
      * True when the recompose scope is in an slot in the slot table
      */
     var inTable = true

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

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

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

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

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

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

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

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

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

 interface ComposerValidator {
     fun changed(value: Int): Boolean
     fun <T> changed(value: T): Boolean
 }

 // TODO(lmr): this could be named MutableTreeComposer
 /**
  * Implementation of a composer for mutable tree.
  */
 open class Composer<N>(
     /**
      * Backing storage for the composition
      */
     val slotTable: SlotTable,

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

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

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

     private val invalidateStack = Stack<RecomposeScope>()

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

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

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

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

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

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

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

     protected fun composeRoot(block: () -> Unit) {
         startRoot()
         startGroup(invocation)
         block()
         endGroup()
         endRoot()
     }

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

     /**
      * 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 key for the group. This is expected to be the result of [joinKey] which
      * will create a compound key of a source-location-based key and an arbitrary externally
      * provided piece of data. Whatever object is passed in here is expected to have a meaningful
      * [equals] and [hashCode] implementation.
      *
      * @see [endMovableGroup]
      * @see [key]
      * @see [joinKey]
      * @see [startReplaceableGroup]
      * @see [startRestartGroup]
      */
     fun startMovableGroup(key: Any) = start(key, 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]
      */
     fun endMovableGroup() = endGroup()

     inline fun call(
         key: Any,
         invalid: ComposerValidator.() -> Boolean,
         block: () -> Unit
     ) {
         startGroup(key)
         if (this.invalid() || !skipping) {
             block()
         } else {
             skipToGroupEnd()
         }
         endGroup()
     }

     /**
      * Start the composition. This should be called, and only be called, as the first group in
      * the composition.
      */
     fun startRoot() {
         reader = slotTable.openReader()
         startGroup(RootKey)
         parentReference?.let { parentRef ->
             parentProvider = parentRef.getAmbientScope()
             providersInvalidStack.push(providersInvalid.asInt())
             providersInvalid = changed(parentProvider)
         }
     }

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

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

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

     /**
      * True if the composition should be checking if the composable functions can be skipped.
      */
     val skipping: Boolean get() = !inserting && !providersInvalid

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

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

     /**
      * Apply the changes to the tree that were collected during the last composition.
      */
     fun applyChanges() {
         trace("Compose:applyChanges") {
             invalidateStack.clear()
             val enters = mutableSetOf<CompositionLifecycleObserverHolder>()
             val leaves = mutableSetOf<CompositionLifecycleObserverHolder>()
             val manager = object : LifeCycleManager {
                 override fun entering(instance: CompositionLifecycleObserver) {
                     val holder = CompositionLifecycleObserverHolder(instance)
                     lifecycleObservers.getOrPut(holder) {
                         enters.add(holder)
                         holder
                     }.apply { count++ }
                 }

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

             val invalidationAnchors = invalidations.map { slotTable.anchor(it.location) to it }

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

             providerUpdates.clear()

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

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

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

             dispatchChangesAppliedObservers()
         }
     }

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

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

     fun startExpr(key: Any) = startGroup(key)

     fun endExpr() = endGroup()

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

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

     // Deprecated
     fun <T : N> emitNode(factory: () -> T) {
         validateNodeExpected()
         if (inserting) {
             val insertIndex = nodeIndexStack.peek()
             // The pending is the pending information for where the node is being inserted.
             // pending will be null here when the parent was inserted too.
             groupNodeCount++
             recordFixup { applier, slots, _ ->
                 val node = factory()
                 slots.node = node
                 applier.insert(insertIndex, node)
                 applier.down(node)
             }
         } else {
             recordDown(reader.node)
         }
     }

     /**
      * 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")
     fun <T : N> createNode(factory: () -> T) {
         validateNodeExpected()
         require(inserting) { "createNode() can only be called when inserting" }
         val insertIndex = nodeIndexStack.peek()
         // see emitNode
         groupNodeCount++
         recordFixup { applier, slots, _ ->
             val node = factory()
             slots.node = node
             applier.insert(insertIndex, node)
             applier.down(node)
         }
         // Allocate a slot that will be fixed-up by the above operation.
         writer.skip()
     }

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

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

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

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

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

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

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

     // TODO: Add more overloads for common primitive types like String and Float etc to avoid boxing
     override fun changed(value: Int): Boolean {
         return if (nextSlot() != value || inserting) {
             updateValue(value)
             true
         } else {
             false
         }
     }

     /**
      * 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.
      */
     fun updateValue(value: Any?) {
         if (inserting) {
             writer.update(value)
             if (value is CompositionLifecycleObserver) {
                 record { _, _, lifecycleManager -> lifecycleManager.entering(value) }
             }
         } else {
             recordSlotTableOperation(-1) { _, slots, lifecycleManager ->
                 if (value is CompositionLifecycleObserver)
                     lifecycleManager.entering(value)
                 when (val previous = slots.update(value)) {
                     is CompositionLifecycleObserver ->
                         lifecycleManager.leaving(previous)
                     is RecomposeScope ->
                         previous.inTable = false
                 }
             }
             // Advance the writers reader location to account for the update above.
             writersReaderDelta++
         }
     }

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

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

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

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

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

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

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

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

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

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

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

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

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

         var ref = nextSlot() as? CompositionReference
         if (ref == null || !inserting) {
             val scope = invalidateStack.peek()
             scope.used = true
             ref = CompositionReferenceImpl(scope)
             updateValue(ref)
         }
         endGroup()

         return ref
     }

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

         val ref = parentReference

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

         return key.defaultValueHolder.value
     }

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

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

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

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

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

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

     /**
      * Important: This is a short-cut for the full version of [start] and should be kept in sync
      * with its implementation. This version avoids boxing for [Int] keys.
      */
     private fun start(key: Int, isNode: Boolean, data: Any?) {
         if (!inserting && pending == null && run {
                 val slot = reader.groupKey
                 if (slot is Int) {
                     val slotInt: Int = slot
                     key == slotInt
                 } else false
             }) {
             validateNodeNotExpected()

             updateCompoundKeyWhenWeEnterGroupKeyHash(key)
             startReaderGroup(isNode, data)
             enterGroup(isNode, null)
         } else {
             start(key as Any, isNode, data)
         }
     }

     private fun start(key: Any, isNode: Boolean, data: Any?) {
         // !! IMPORTANT !! If there are changes to this method there might need to be
         // corresponding changes to the Int short cut method above.

         validateNodeNotExpected()

         updateCompoundKeyWhenWeEnterGroup(key)

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

         if (pending == null) {
             val slotKey = reader.groupKey
             if (slotKey == key) {
                 // 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)
             if (keyInfo != null) {
                 // This group was generated last time, use it.
                 pending.recordUsed(keyInfo)

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

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

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

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

         enterGroup(isNode, newPending)
     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

             realizeMovement()
         }

         exitGroup(expectedNodeCount, inserting)
     }

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

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

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

             invalidations.removeLocation(location)

             recomposed = true

             reader.reposition(location)
             val newGroup = reader.group

             // Record the changes to the applier location
             recordUpsAndDowns(oldGroup, newGroup, recomposeGroup)
             oldGroup = newGroup

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

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

             firstInRange.scope.compose(this)

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

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

         isComposing = wasComposing
     }

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

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

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

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

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

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

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

                 current = end
             }
             break
         }
         return index
     }

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

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

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

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

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

     internal fun invalidate(scope: RecomposeScope): InvalidationResult {
         val location = scope.anchor?.location(slotTable)
             ?: return InvalidationResult.IGNORED // The scope never entered the composition
         if (location < 0)
             return InvalidationResult.IGNORED // The scope was removed from the composition

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

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

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

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

     /**
      * Start a restart group. A restart group creates a recompose scope and sets it as the current
      * recompose scope of the composition. If the recompose scope is invalidated then this group
      * will be recomposed. A recompose scope can be invalidated by calling the lambda returned by
      * [androidx.compose.invalidate].
      */
     fun startRestartGroup(key: Int) {
         val location = reader.current
         start(key, false, null)
         if (inserting) {
             val scope = RecomposeScope(this)
             invalidateStack.push(scope)
             updateValue(scope)
         } else {
             invalidations.removeLocation(location)
             val scope = reader.next() as RecomposeScope
             invalidateStack.push(scope)
         }
     }

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

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

     internal fun hasInvalidations() = invalidations.isNotEmpty()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     private var pendingInsertUps = 0

     private fun recordInsertUp() {
         pendingInsertUps++
     }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     private fun recordRemoveNode(nodeIndex: Int, count: Int) {
         if (count > 0) {
             require(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) }
             }
         }
     }

     private inner class CompositionReferenceImpl(val scope: RecomposeScope) : CompositionReference,
         CompositionLifecycleObserver {

         val composers = mutableSetOf<Composer<*>>()

         override fun onEnter() {
             // do nothing
         }

         override fun onLeave() {
             composers.clear()
         }

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

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

             invalidate(scope)
         }

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

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

     private fun updateCompoundKeyWhenWeEnterGroup(groupKey: Any) {
         updateCompoundKeyWhenWeEnterGroupKeyHash(groupKey.hashCode())
     }

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

     private fun updateCompoundKeyWhenWeExitGroup(groupKey: Any) {
         currentCompoundKeyHash = (currentCompoundKeyHash xor groupKey.hashCode()) ror 3
     }
 }

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

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

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

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

 /**
  * 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 [valid] is true the
  * value is obtained from the slot table and [block] is not invoked. If [valid] is false a new
  * value is produced by calling [block] and the slot table is updated to contain the new value.
  */
 inline fun <N, T> Composer<N>.cache(valid: Boolean = true, block: () -> T): T {
     var result = nextSlot()
     if (result === EMPTY || !valid) {
         val value = block()
         updateValue(value)
         result = value
     }

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

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

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

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

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

         index++

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 object NullCompilationScope {
     val composer = Unit
 }

 inline fun <T> escapeCompose(block: NullCompilationScope.() -> T) = NullCompilationScope.block()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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