| /* |
| * 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 |
| |
| @InternalComposeApi |
| class SlotReader(val table: SlotTable) { |
| var current = 0 |
| private set |
| var currentEnd = table.size |
| private set |
| var nodeIndex: Int = 0 |
| private set |
| |
| internal val startStack = IntStack() |
| private val slots = table.slots |
| private var currentGroup: Group? = null |
| private var emptyCount = 0 |
| private val nodeIndexStack = IntStack() |
| |
| init { |
| require(table.gapStart == currentEnd) { "Gap is not at the end of the slot table" } |
| } |
| |
| /** |
| * Determine the slot at [current] is the start of a group and not at the end of the current |
| * group. |
| */ |
| val isGroup get() = current < currentEnd && calculateCurrentGroup() != null |
| |
| internal val group get() = assumeGroup() |
| internal fun group(location: Int) = slots[location].asGroup |
| internal val parentGroup get() = slots[parentLocation].asGroup |
| |
| /** |
| * Determine if the slot at [index] is the start of a group |
| */ |
| fun isGroup(index: Int) = slots[index] is Group |
| |
| /** |
| * Determine if the slot is start of a node. |
| */ |
| val isNode get() = calculateCurrentGroup()?.isNode ?: false |
| |
| /** |
| * Determine if the slot at [location] is a node group. This will throw if the slot at |
| * [location] is not a node. |
| */ |
| fun isNode(location: Int) = slots[location].asGroup.isNode |
| |
| /** |
| * Determine if the reader is at the end of a group and an [endGroup] or [endNode] is expected. |
| */ |
| val isGroupEnd get() = inEmpty || current == currentEnd |
| |
| /** |
| * Determine if a [beginEmpty] has been called. |
| */ |
| val inEmpty get() = emptyCount > 0 |
| |
| /** |
| * Get the size of the group at [current]. Will throw an exception if the [isGroup] is `false`. |
| */ |
| val groupSize get() = assumeGroup().slots |
| |
| /** |
| * Get the size of the group at [index]. Will throw an exception if [index] is not a group |
| * start. |
| */ |
| fun groupSize(index: Int) = slots[index].asGroup.slots |
| |
| /** |
| * Get location the end of the currently started group. |
| */ |
| val groupEnd get() = currentEnd |
| |
| /** |
| * Get location of the end of the group at [index]. |
| */ |
| fun groupEnd(index: Int) = index + slots[index].asGroup.slots + 1 |
| |
| /** |
| * Get the data for the current group. Returns null if [current] is not a group |
| */ |
| val groupData get() = if (current < currentEnd) calculateCurrentGroup()?.data else null |
| |
| /** |
| * Get the key of the current group. Returns 0 if the [current] is not a group. |
| */ |
| val groupKey get() = if (current < currentEnd) { |
| val group = calculateCurrentGroup() |
| if (group != null) group.key else 0 |
| } else 0 |
| |
| /** |
| * Get the data key for the current group. Returns null if the [current] is not a group. |
| */ |
| val groupDataKey get() = |
| if (current < currentEnd) calculateCurrentGroup()?.dataKey else null |
| |
| /** |
| * Get the node associated with the group if there is one. |
| */ |
| val groupNode get() = (assumeGroup() as? NodeGroup)?.node |
| |
| /** |
| * Get the key of the group at [index]. Will throw an exception if [index] is not a group |
| * start. |
| */ |
| fun groupKey(index: Int) = slots[index].asGroup.key |
| |
| /** |
| * Return the location of the parent group of the [current] |
| */ |
| val parentLocation: Int get() = startStack.peekOr(0) |
| |
| /** |
| * Return the number of nodes where emitted into the current group. |
| */ |
| val parentNodes: Int get() = |
| if (startStack.isEmpty()) 0 else slots[startStack.peek()].asGroup.nodes |
| |
| /** |
| * Return the number of slots are in the current group. |
| */ |
| val parentSlots: Int get() = |
| if (startStack.isEmpty()) 0 else slots[startStack.peek()].asGroup.slots |
| |
| /** |
| * Get the value stored at [anchor]. |
| */ |
| @Suppress("KotlinOperator") |
| fun get(anchor: Anchor) = if (anchor.loc >= 0) slots[anchor.loc] else EMPTY |
| |
| /** |
| * Get the value stored at [index]. |
| */ |
| @Suppress("KotlinOperator") |
| fun get(index: Int) = if (emptyCount > 0) EMPTY else slots[index] |
| |
| /** |
| * Get the value of the slot at [current] or [EMPTY] if at then end of a group. During empty |
| * mode this value is always [EMPTY] which is the value a newly inserted slot. |
| */ |
| fun next(): Any? { |
| if (emptyCount > 0) return EMPTY |
| currentGroup = null |
| return if (current < currentEnd) slots[current++] else EMPTY |
| } |
| |
| /** |
| * Begin reporting empty for all calls to next() or get(). beginEmpty() can be nested and must |
| * be called with a balanced number of endEmpty() |
| */ |
| fun beginEmpty() { emptyCount++ } |
| |
| /** |
| * End reporting [EMPTY] for calls to [next] and [get], |
| */ |
| fun endEmpty() { |
| require(emptyCount > 0) { "Unbalanced begin/end empty" } |
| emptyCount-- |
| } |
| |
| /** |
| * Close the slot reader. After all [SlotReader]s have been closed the [SlotTable] a |
| * [SlotWriter] can be created. |
| */ |
| fun close() = table.close(this) |
| |
| /** |
| * Start a group. Passing an EMPTY as the key will enter the group without validating the key. |
| */ |
| fun startGroup() = startGroup(GROUP) |
| |
| /** |
| * Start a node. |
| */ |
| fun startNode() = startGroup(NODE) |
| |
| /** |
| * Start a data group. |
| */ |
| fun startDataGroup() = startGroup(DATA) |
| |
| /** |
| * Skip a group. Must be called at the start of a group. |
| */ |
| fun skipGroup(): Int { |
| require(emptyCount == 0) { "Cannot skip while in an empty region" } |
| val group = assumeGroup() |
| current += group.slots + 1 |
| currentGroup = null |
| val count = if (group.isNode) 1 else group.nodes |
| nodeIndex += count |
| return count |
| } |
| |
| /** |
| * Start a node. |
| */ |
| fun skipNode() = skipGroup() |
| |
| /** |
| * Skip to the end of the current group. |
| */ |
| fun skipToGroupEnd() { |
| require(emptyCount == 0) { "Cannot skip the enclosing group while in an empty region" } |
| require(startStack.isNotEmpty()) { "No enclosing group to skip" } |
| nodeIndex = slots[startStack.peek()].asGroup.nodes + nodeIndexStack.peek() |
| currentGroup = null |
| current = currentEnd |
| } |
| |
| fun reposition(value: Int) { |
| current = value |
| currentGroup = null |
| } |
| /** |
| * End the current group. Must be called after the corresponding [startGroup]. |
| */ |
| fun endGroup() { |
| if (emptyCount == 0) { |
| require(current == currentEnd) |
| val startLocation = startStack.pop() |
| if (startStack.isEmpty()) return |
| val parentLocation = startStack.peekOr(0) |
| val group = slots[startLocation].asGroup |
| val parentGroup = slots[parentLocation].asGroup |
| nodeIndex = nodeIndexStack.pop() + if (group.isNode) 1 else nodeIndex |
| currentEnd = parentGroup.slots + parentLocation + 1 |
| currentGroup = null |
| } |
| } |
| |
| /** |
| * End a node |
| */ |
| fun endNode() = endGroup() |
| |
| /** |
| * Extract the keys from this point to the end of the group. The current is left unaffected. |
| * Must be called inside a group. |
| */ |
| fun extractKeys(): MutableList<KeyInfo> { |
| val result = mutableListOf<KeyInfo>() |
| if (emptyCount > 0) return result |
| val oldCurrent = current |
| val oldNodeIndex = nodeIndex |
| var index = 0 |
| while (current < currentEnd) { |
| val location = current |
| val group = slots[location].asGroup |
| result.add(KeyInfo( |
| group.key, |
| group.dataKey, |
| location, |
| skipGroup(), |
| index++, |
| group |
| )) |
| } |
| current = oldCurrent |
| this.nodeIndex = oldNodeIndex |
| return result |
| } |
| |
| override fun toString(): String = "SlotReader(current=$current, emptyCount=$emptyCount)" |
| |
| private fun startGroup(kind: GroupKind) { |
| if (emptyCount <= 0) { |
| startStack.push(current) |
| nodeIndexStack.push(nodeIndex) |
| nodeIndex = 0 |
| val group = assumeGroup() |
| currentEnd = current + group.slots + 1 |
| require(group.kind == kind) { "Group kind changed" } |
| current++ |
| currentGroup = null |
| } |
| } |
| |
| private fun calculateCurrentGroup(): Group? = |
| (currentGroup ?: slots[current] as? Group)?.also { currentGroup = it } |
| private fun assumeGroup(): Group = calculateCurrentGroup() |
| ?: error("Expected a group start") |
| } |
| |
| @PublishedApi |
| internal val EMPTY = SlotTable.EMPTY |
| |
| @InternalComposeApi |
| class SlotWriter internal constructor(val table: SlotTable) { |
| var current = 0 |
| |
| internal val slots get() = table.slots |
| internal fun effectiveIndex(index: Int) = table.effectiveIndex(index) |
| internal var currentEnd = table.slots.size |
| |
| private var startStack = IntStack() |
| private val nodeCountStack = IntStack() |
| private val endStack = IntStack() |
| private var nodeCount = 0 |
| private var insertCount = 0 |
| private var pendingClear = false |
| |
| /** |
| * Return true if the current slot starts a group |
| */ |
| val isGroup get() = current < currentEnd && get(current) is Group |
| |
| /** |
| * Return true if the slot at index starts a gorup |
| */ |
| fun isGroup(index: Int) = get(index) is Group |
| |
| internal fun group(location: Int) = slots[effectiveIndex(location)].asGroup |
| |
| internal val parentGroup: Group get() = group(parentLocation) |
| |
| /** |
| * Return true if the current slot starts a node. A node is a kind of group so this will |
| * return true for isGroup as well. |
| */ |
| val isNode get() = current < currentEnd && (get(current) as? Group)?.isNode ?: false |
| |
| /** |
| * Return the number of nodes in the group. isGroup must be true or this will throw. |
| */ |
| val groupSize get() = get(current).asGroup.slots |
| |
| /** |
| * Return the size of the group at index. isGroup(index) must be true of this will throw. |
| */ |
| fun groupSize(index: Int): Int = get(index).asGroup.slots |
| |
| /** |
| * Get the number of nodes emitted to the group prior to the current slot. |
| */ |
| val nodeIndex get() = nodeCount |
| |
| /** |
| * Get the total number of nodes emitted in the group containing the current. |
| */ |
| val parentNodes: Int |
| get() { |
| return if (startStack.isEmpty()) 0 |
| else slots[effectiveIndex(startStack.peek())].asGroup.nodes |
| } |
| |
| /** |
| * Return the start location of the nearest group that contains [current]. |
| */ |
| val parentLocation: Int get() = startStack.peekOr(-1) |
| |
| /** |
| * True if the writer has been closed |
| */ |
| var closed = false |
| private set |
| |
| /** |
| * Return the start location of the nearest group that contains the slot at [anchor]. |
| */ |
| fun parentIndex(anchor: Anchor): Int { |
| val group = get(anchor).asGroup |
| val location = table.anchorLocation(anchor) |
| val parent = group.parent |
| if (parent != null) { |
| // Scan the slot table for the parent slot. |
| // The parent is, at most parent.slots - group.slots - 1 before location. |
| val start = (location - (parent.slots - group.slots) - 1).let { if (it < 0) 0 else it } |
| for (probe in start until location) { |
| if (get(probe) === parent) return probe |
| } |
| } |
| error("Could not find parent of group at $location") |
| } |
| |
| /** |
| * Get the value at an Anchor |
| */ |
| @Suppress("KotlinOperator") |
| fun get(anchor: Anchor) = if (anchor.loc >= 0) slots[anchor.loc] else SlotTable.EMPTY |
| |
| /** |
| * Get the value at the index'th slot. |
| */ |
| @Suppress("KotlinOperator") |
| fun get(index: Int) = effectiveIndex(index).let { |
| if (it < slots.size) slots[it] else SlotTable.EMPTY |
| } |
| |
| fun close() { |
| closed = true |
| table.close(this) |
| // Ensure, for readers, there is no gap |
| moveGapTo(table.size) |
| } |
| |
| /** |
| * Set the value of the next slot. |
| */ |
| fun update(value: Any?): Any? { |
| val result = skip() |
| set(value) |
| return result |
| } |
| |
| /** |
| * Updates the data for a data group |
| */ |
| fun updateData(value: Any?) { |
| (get(current) as? DataGroup ?: error("Expected a data group")).data = value |
| } |
| |
| /** |
| * Set the value at the slot previous to current. |
| */ |
| fun set(value: Any?) { |
| slots[effectiveIndex(current - 1)] = value |
| } |
| |
| /** |
| * Skip the current slot without updating. If the slot table is inserting then and [EMPTY] slot |
| * is added and [skip] return [EMPTY]. |
| */ |
| fun skip(): Any? { |
| if (insertCount > 0) { |
| insert(1) |
| } |
| val index = current++ |
| return slots[table.effectiveIndex(index)] |
| } |
| |
| /** |
| * Skip [amount] slots in the slot table. If the slot table is inserting then this |
| * adds [amount] [EMPTY] slots. |
| * |
| * Skip cannot skip outside the current group. |
| */ |
| fun skip(amount: Int) { |
| if (insertCount > 0) { |
| insert(amount) |
| } else { |
| val location = current + amount |
| require(location <= currentEnd) { |
| "Cannot skip outside the current group ($currentEnd)" |
| } |
| current = location |
| } |
| } |
| |
| /** |
| * Skip to the end of the current group. |
| */ |
| fun skipToGroupEnd() { current = currentEnd } |
| |
| /** |
| * If the start of a group was skipped using [skip], calling [ensureStarted] puts the writer |
| * into the same state as if [startGroup] or [startNode] was called on the group starting at |
| * [location]. If, after starting, the group, [current] is not a the end of the group or |
| * [current] is not at the start of a group for which [location] is not location the parent |
| * group, an exception is thrown. |
| * |
| * Calling [ensureStarted] implies that an [endGroup] should be called once the end of the |
| * group is reached. |
| */ |
| fun ensureStarted(location: Int) { |
| require(insertCount <= 0) { "Cannot call ensureStarted() while inserting" } |
| require(location in 0 until current) { "$location is out of range 0..${current - 1}" } |
| val parentLoc = parentLocation |
| if (parentLoc != location) { |
| if (startStack.isEmpty() && location > 0) ensureStarted(0) |
| val currentParent = if (parentLoc >= 0) get(parentLocation).asGroup else null |
| val newParent = get(location).asGroup |
| |
| // The new parent must be a (possibly indirect) child of the current parent |
| require(newParent.isDecendentOf(currentParent)) { |
| "Started group must be a subgroup of the group at $parentLocation" |
| } |
| |
| val oldCurrent = current |
| current = location |
| startGroup(newParent.key, newParent.dataKey, newParent.kind, newParent.data) |
| current = oldCurrent |
| } |
| } |
| |
| fun ensureStarted(anchor: Anchor) = ensureStarted(anchor.location(table)) |
| |
| /** |
| * Begin inserting at the current location. beginInsert() can be nested and must be called with |
| * a balanced number of endInsert() |
| */ |
| fun beginInsert() { |
| insertCount++ |
| } |
| |
| /** |
| * Ends inserting. |
| */ |
| fun endInsert() { |
| require(insertCount > 0) { "Unbalenced begin/end insert" } |
| insertCount-- |
| } |
| |
| /** |
| * Enter the group at current without changing it. Requires not currently inserting. |
| */ |
| fun startGroup() { |
| require(insertCount == 0) { "Key must be supplied when inserting" } |
| startGroup(0, null, GROUP, null) |
| } |
| |
| /** |
| * Start a group with a integer key |
| */ |
| fun startGroup(key: Int) = startGroup(key, null, GROUP, null) |
| |
| /** |
| * Start a group with a data key |
| */ |
| fun startGroup(key: Int, dataKey: Any?) = startGroup(key, dataKey, GROUP, null) |
| |
| /** |
| * Start a group with a data key and auxiliary data. |
| */ |
| fun startGroup(key: Int, dataKey: Any?, data: Any?) = |
| startGroup(key, dataKey, if (data != null) DATA else GROUP, data) |
| |
| private fun startGroup(key: Int, dataKey: Any?, kind: GroupKind, data: Any?) { |
| val inserting = insertCount > 0 |
| val parent = if (startStack.isEmpty()) null else get(startStack.peek()).asGroup |
| startStack.push(current) |
| nodeCountStack.push(nodeCount) |
| |
| // Record the end location as relative to the end of the slot table so when we pop it back |
| // off again all inserts and removes that happened while a child group was open are already |
| // reflected into its value. |
| endStack.push(slots.size - table.gapLen - currentEnd) |
| currentEnd = if (inserting) { |
| update(Group(kind, key, dataKey, parent, data)) |
| nodeCount = 0 |
| current |
| } else { |
| val group = advance().asGroup |
| require(group.kind == kind) { "Group kind changed" } |
| require(key == 0 || group.key == key) { "Group key changed" } |
| require(key == 0 || group.dataKey == dataKey) { "Group dataKey changed" } |
| if (kind == DATA) { |
| (group as? DataGroup ?: error("Expected a data group")).data = data |
| } else if (kind == NODE && data != null) { |
| (group as? NodeGroup ?: error("Expected a node group")).node = data |
| } |
| nodeCount = group.nodes |
| current + group.slots |
| } |
| } |
| |
| /** |
| * Skip a group. Must be called at the start of a group. |
| */ |
| fun skipGroup(): Int { |
| require(insertCount == 0) { "Cannot skip while inserting" } |
| return advanceToNextGroup() |
| } |
| |
| /** |
| * End the current group. Must be called after the corresponding startGroup(). |
| */ |
| fun endGroup(): Int { |
| require(startStack.isNotEmpty()) { |
| "Invalid state. Unbalanced calls to startGroup() and endGroup()" |
| } |
| val inserting = insertCount > 0 |
| require(inserting || current == currentEnd) { "Expected to be at the end of a group" } |
| |
| // Update group length |
| val startLocation = startStack.pop() |
| val group = get(startLocation).asGroup |
| val cur = current |
| val oldSlots = group.slots |
| val oldNodes = group.nodes |
| val newSlots = cur - startLocation - 1 |
| val newNodes = nodeCount |
| group.slots = newSlots |
| group.nodes = newNodes |
| currentEnd = (slots.size - table.gapLen) - endStack.pop() |
| if (nodeCountStack.isEmpty()) { |
| table.clearGap() |
| } else if (startStack.isNotEmpty()) { |
| nodeCount = nodeCountStack.pop() |
| val parent = get(startStack.peek()).asGroup |
| if (group.parent == parent) { |
| nodeCount += if (inserting) { |
| if (group.isNode) 1 else newNodes |
| } else { |
| if (group.isNode) 0 else newNodes - oldNodes |
| } |
| } else { |
| // If we are closing a group whose parent is not the now current group then the |
| // slot writer was seek'ed to the group and the parents of this group need to be |
| // updated to reflect any changes to the groups nodes or slots. |
| val slotsDelta = newSlots - oldSlots |
| var nodesDelta = if (group.isNode) 0 else newNodes - oldNodes |
| if (slotsDelta != 0 || nodesDelta != 0) { |
| var currentGroup = group.parent |
| while ( |
| currentGroup != null && |
| currentGroup != parent && |
| (nodesDelta != 0 || slotsDelta != 0) |
| ) { |
| currentGroup.slots += slotsDelta |
| currentGroup.nodes += nodesDelta |
| if (currentGroup.isNode) nodesDelta = 0 |
| currentGroup = currentGroup.parent |
| } |
| } |
| nodeCount += nodesDelta |
| } |
| } |
| return newNodes |
| } |
| |
| /** |
| * Move the offset'th group after the current group to the current location. |
| */ |
| fun moveGroup(offset: Int) { |
| require(insertCount == 0) { "Cannot move a group while inserting" } |
| val oldCurrent = current |
| val oldNodeCount = nodeCount |
| |
| // Find the group to move |
| var count = offset |
| while (count > 0) { |
| advanceToNextGroup() |
| count-- |
| } |
| |
| // Move the current one here by first inserting room for it then copying it over the spot |
| // then removing the old slot. |
| val moveLocation = current |
| advanceToNextGroup() |
| val moveLen = current - moveLocation |
| current = oldCurrent |
| insert(moveLen) |
| // insert inserted moveLen slots which moved moveLocation |
| val newMoveLocation = moveLocation + moveLen |
| current = oldCurrent |
| nodeCount = oldNodeCount |
| |
| slots.copyInto(slots, effectiveIndex(current), |
| effectiveIndex(newMoveLocation), effectiveIndex(newMoveLocation) + moveLen) |
| |
| // Before we remove the old location, move any anchors |
| table.moveAnchors(newMoveLocation, current, moveLen) |
| |
| // Remove the now duplicate entries |
| val anchorsRemoved = remove(moveLocation + moveLen, moveLen) |
| require(!anchorsRemoved) { "Unexpectedly removed anchors" } |
| } |
| |
| /** |
| * Remove a group. Must be called at group. |
| */ |
| fun removeGroup(): Boolean { |
| require(insertCount == 0) { "Cannot remove group while inserting" } |
| val oldCurrent = current |
| val count = advanceToNextGroup() |
| val anchorsRemoved = remove(oldCurrent, current - oldCurrent) |
| current = oldCurrent |
| nodeCount -= count |
| return anchorsRemoved |
| } |
| |
| /** |
| * Returns an iterator for the slots of group. |
| */ |
| fun groupSlots(): Iterator<Any?> { |
| val start = current |
| val oldCount = nodeCount |
| advanceToNextGroup() |
| val end = current |
| current = start |
| nodeCount = oldCount |
| return object : Iterator<Any?> { |
| var current = start + 1 |
| override fun hasNext(): Boolean = current < end |
| override fun next(): Any? = slots[effectiveIndex(current++)] |
| } |
| } |
| |
| /** |
| * Enter an existing node |
| */ |
| fun startNode() { |
| require(insertCount == 0) { "Key must be supplied when inserting" } |
| startGroup(0, null, NODE, null) |
| } |
| |
| /** |
| * Start a node. |
| */ |
| fun startNode(key: Any?) = startGroup(125, key, NODE, null) |
| |
| /** |
| * Start a node |
| */ |
| fun startNode(key: Any?, node: Any?) = startGroup(125, key, NODE, node) |
| |
| /** |
| * End a node |
| */ |
| fun endNode() = endGroup() |
| |
| /** |
| * Start a data node. |
| */ |
| fun startData(key: Int, dataKey: Any?, data: Any?) = startGroup(key, dataKey, DATA, data) |
| |
| /** |
| * End a data node |
| */ |
| fun endData() = endGroup() |
| |
| /** |
| * Skip a node |
| */ |
| fun skipNode() = skipGroup() |
| |
| /** |
| * Move (insert and then delete) the group at [location] from [slots]. All anchors in the range |
| * (including [location]) are moved to the slot table for which this is a reader. |
| * |
| * It is required that the writer be inserting. |
| * |
| * @return a list of the anchors that were moved |
| */ |
| fun moveFrom(table: SlotTable, location: Int): List<Anchor> { |
| require(insertCount > 0) |
| |
| if (location == 0 && current == 0 && this.table.size == 0) { |
| // Special moving the entire slot table into an empty table, just swap the slots |
| // and the anchors. |
| table.write { |
| val sourceSlots = table.slots |
| val sourceAnchors = table.anchors |
| val sourceGapStart = table.gapStart |
| val sourceGapLen = table.gapLen |
| val destTable = this.table |
| val destSlots = destTable.slots |
| val destAnchors = destTable.anchors |
| destTable.slots = sourceSlots |
| destTable.anchors = sourceAnchors |
| destTable.gapStart = sourceGapStart |
| destTable.gapLen = sourceGapLen |
| table.slots = destSlots |
| table.anchors = destAnchors |
| table.gapStart = 0 |
| table.gapLen = 0 |
| } |
| return this.table.anchors |
| } |
| |
| return table.write { tableWriter -> |
| val sourceStart = location |
| val slotsToMove = tableWriter.groupSize(sourceStart) + 1 |
| |
| // Make room in the table |
| insert(slotsToMove) |
| |
| // Copy the slots to the |
| val sourceSlots = table.slots |
| val destSlots = slots |
| val destStart = current |
| val sourceEnd = sourceStart + slotsToMove |
| // Move the gap to make the location contiguous. The remove at the end will do this |
| // as well so doing this early makes this code easier as the gap can be ignored. |
| tableWriter.moveGapTo(sourceEnd) |
| sourceSlots.copyInto(destSlots, current, sourceStart, sourceEnd) |
| |
| val group = get(destStart).asGroup |
| |
| // Update the sizes of the parents of the group that was moved. |
| var currentGroup = group.parent |
| val slotsDelta = group.slots + 1 |
| var nodesDelta = if (group.isNode) 1 else group.nodes |
| while (currentGroup != null) { |
| currentGroup.slots -= slotsDelta |
| currentGroup.nodes -= nodesDelta |
| if (currentGroup.isNode) nodesDelta = 0 |
| currentGroup = currentGroup.parent |
| } |
| |
| // Update the parent of the group moved. |
| group.parent = get(startStack.peek()).asGroup |
| |
| // Extract the anchors in range |
| val startAnchors = table.anchors.locationOf(sourceStart) |
| val endAnchors = table.anchors.locationOf(sourceEnd) |
| val anchors = if (startAnchors < endAnchors) { |
| val sourceAnchors = table.anchors |
| val anchors = ArrayList<Anchor>(endAnchors - startAnchors) |
| |
| // update the anchor locations to their new location |
| for (index in startAnchors until endAnchors) { |
| val sourceAnchor = sourceAnchors[index] |
| sourceAnchor.loc = sourceAnchor.loc - sourceStart + destStart |
| anchors.add(sourceAnchor) |
| } |
| |
| // Insert them into the new table |
| val insertLocation = this.table.anchors.locationOf(current) |
| this.table.anchors.addAll(insertLocation, anchors) |
| |
| // Remove them from the old table |
| sourceAnchors.subList(startAnchors, endAnchors).clear() |
| |
| anchors |
| } else emptyList<Anchor>() |
| |
| // Now remove the range from the table. |
| val anchorsRemoved = tableWriter.remove(sourceStart, slotsToMove) |
| require(!anchorsRemoved) { "Removing anchors that should have been moved" } |
| |
| // Update the node count. |
| nodeCount += group.nodes |
| |
| // Move current passed the insert |
| current += slotsToMove |
| |
| anchors |
| } |
| } |
| |
| /** |
| * Allocate an anchor for a location. As content is inserted and removed from the slot table the |
| * anchor is updated to reflect those changes. For example, if an anchor is requested for an |
| * group, the anchor will report the location of that group even if the group is moved in the slot |
| * table. If the position referenced by the anchor is removed, the anchor location is set to -1. |
| */ |
| fun anchor(index: Int = current): Anchor = table.anchor(index) |
| |
| private fun advance(): Any? { |
| if (current >= currentEnd) { |
| return SlotTable.EMPTY |
| } |
| val index = current++ |
| return slots[effectiveIndex(index)] |
| } |
| |
| private fun advanceToNextGroup(): Int { |
| val groupStart = advance().asGroup |
| current += groupStart.slots |
| |
| return if (groupStart.isNode) 1 else groupStart.nodes |
| } |
| |
| private fun moveGapTo(index: Int) { |
| if (table.gapLen > 0 && table.gapStart != index) { |
| trace("SlotTable:moveGap") { |
| pendingClear = false |
| if (table.anchors.isNotEmpty()) table.updateAnchors(index) |
| if (index < table.gapStart) { |
| slots.copyInto(slots, index + table.gapLen, |
| index, table.gapStart) |
| } else { |
| slots.copyInto(slots, table.gapStart, |
| table.gapStart + table.gapLen, |
| index + table.gapLen) |
| } |
| table.gapStart = index |
| pendingClear = true |
| } |
| } else { |
| table.gapStart = index |
| } |
| } |
| |
| private fun insert(size: Int) { |
| if (size > 0) { |
| moveGapTo(current) |
| if (table.gapLen < size) { |
| trace("SlotTable:grow") { |
| // Create a bigger gap |
| val oldCapacity = slots.size |
| val oldSize = slots.size - table.gapLen |
| // Double the size of the array, but at least MIN_GROWTH_SIZE and >= size |
| val newCapacity = kotlin.math.max( |
| kotlin.math.max(oldCapacity * 2, oldSize + size), |
| MIN_GROWTH_SIZE |
| ) |
| val newSlots = arrayOfNulls<Any?>(newCapacity) |
| val newGapLen = newCapacity - oldSize |
| val oldGapEnd = table.gapStart + table.gapLen |
| val newGapEnd = table.gapStart + newGapLen |
| // Copy the old array into the new array |
| slots.copyInto(newSlots, 0, 0, table.gapStart) |
| slots.copyInto(newSlots, newGapEnd, oldGapEnd, oldCapacity) |
| |
| // Update the anchors |
| if (table.anchors.isNotEmpty()) table.anchorGapResize(newGapLen - table.gapLen) |
| |
| // Update the gap and slots |
| table.slots = newSlots |
| table.gapLen = newGapLen |
| } |
| } |
| if (currentEnd >= table.gapStart) currentEnd += size |
| table.gapStart += size |
| table.gapLen -= size |
| |
| repeat(size) { |
| slots[current + it] = SlotTable.EMPTY |
| } |
| pendingClear = true |
| } |
| } |
| |
| internal fun remove(start: Int, len: Int): Boolean { |
| return if (len > 0) { |
| pendingClear = false |
| var anchorsRemoved = false |
| if (table.gapLen == 0) { |
| // If there is no current gap, just make the removed slots the gap |
| table.gapStart = start |
| if (table.anchors.isNotEmpty()) anchorsRemoved = table.removeAnchors(start, len) |
| table.gapLen = len |
| } else { |
| // Move the gap to the startGroup + len location and set the gap startGroup to |
| // startGroup and gap len to len + gapLen |
| val removeEnd = start + len |
| moveGapTo(removeEnd) |
| if (table.anchors.isNotEmpty()) anchorsRemoved = table.removeAnchors(start, len) |
| table.gapStart = start |
| table.gapLen += len |
| } |
| if (currentEnd >= table.gapStart) currentEnd -= len |
| pendingClear = true |
| anchorsRemoved |
| } else false |
| } |
| |
| override fun toString(): String { |
| if (pendingClear) { |
| pendingClear = false |
| table.clearGap() |
| } |
| val gap = if (table.gapLen > 0) |
| "${table.gapStart}-${table.gapStart + table.gapLen - 1}" |
| else |
| "none" |
| return "SlotWriter" + |
| "(current=$current, " + |
| "size=${slots.size - table.gapLen}, " + |
| "gap=${gap}${if (insertCount > 0) ", inserting" else ""})" |
| } |
| } |
| |
| private fun Group.isDecendentOf(parent: Group?): Boolean { |
| if (parent == null) return true |
| var current = this.parent |
| while (current != null) { |
| if (current == parent) return true |
| current = current.parent |
| } |
| return false |
| } |
| |
| private val Any?.asGroup: Group |
| get() = this as? Group ?: error("Expected a group") |
| |
| internal fun Group(kind: GroupKind, key: Int, dataKey: Any?, parent: Group?, data: Any?) = |
| when (kind) { |
| NODE -> { |
| NodeGroup(key, dataKey, parent).also { it.node = data } |
| } |
| DATA -> { |
| DataGroup(key, dataKey, parent, data) |
| } |
| else -> |
| if (dataKey != null) |
| DataKeyGroup(key, dataKey, parent) |
| else |
| Group(key, parent) |
| } |
| |
| internal open class Group( |
| val key: Int, |
| var parent: Group? |
| ) { |
| var slots: Int = 0 |
| var nodes: Int = 0 |
| open val kind: GroupKind get() = GROUP |
| open val dataKey: Any? get() = null |
| open val isNode get() = false |
| open val node: Any? get() = null |
| open val data: Any? get() = null |
| } |
| |
| internal class DataKeyGroup( |
| key: Int, |
| override val dataKey: Any?, |
| parent: Group? |
| ) : Group(key, parent) |
| |
| internal class NodeGroup( |
| key: Int, |
| override val dataKey: Any?, |
| parent: Group? |
| ) : Group(key, parent) { |
| override val kind: GroupKind get() = NODE |
| override val isNode get() = true |
| override var node: Any? = null |
| } |
| |
| internal class DataGroup( |
| key: Int, |
| override val dataKey: Any?, |
| parent: Group?, |
| override var data: Any? |
| ) : Group(key, parent) { |
| override val kind: GroupKind get() = DATA |
| } |
| |
| /** |
| * A gap buffer implementation of the composition slot space. A slot space can be thought of as |
| * a custom List<Any?> that optimizes around inserts and removes. |
| * |
| * Slots stores slots, groups, and nodes. |
| * |
| * Slot - A slot is the primitive base type of the slot space. It is of type Any? and can hold |
| * any value. |
| * Group - A group is a keyed group of slots. The group counts the number of slots and nodes it |
| * contains. |
| * Node - A node is a special group that is counted by the containing groups. |
| * |
| * All groups and nodes are just grouping of slots and use slots to describe the groups. At |
| * the root of a slot space is a group. Groups count the number nodes that are in the group. A node |
| * only counts as one node in its group regardless of the number of nodes it contains. |
| * |
| * ASIDE: |
| * The intent is that groups represent memoized function calls and nodes represent views. For |
| * example: |
| * |
| * @sample androidx.compose.runtime.samples.initialGroup |
| * |
| * the `LinearLayout` here would be a node (the linear layout view). The node contains the |
| * groups for the child views of the linear layout. |
| * |
| * If contact's composition looks like: |
| * |
| * @sample androidx.compose.runtime.samples.contactSample |
| * |
| * then composing contact into the linear layout would add two views to the linear layout's |
| * children. The composition of contact creates groups, one for each text view. The groups for each |
| * contact would be able to report that it produces two views (that is the group created for |
| * Contact has two nodes). Summing the nodes in the group produces the number of views (as |
| * each node corresponds to a view). |
| * |
| * If the order of jim and bob change: |
| * |
| * @sample androidx.compose.runtime.samples.reorderedGroup |
| * |
| * the previous result can be reused by moving the views generated bob's group before jim's (or vis |
| * versa). A composition algorithm could use the key information for each group to determine if they |
| * can be switched. For example, since the first contact's group has two nodes the composition |
| * algorithm can infer that the beginning of jim's views starts at 2 and contains 2 view. To move |
| * jim in front of bob, move the 2 views from offset 2 to offset 0. If contact is immutable, for |
| * example, Contact would only need to be recomposed if the value of jim or bob change. |
| */ |
| class SlotTable(internal var slots: Array<Any?> = arrayOf()) { |
| private var readers = 0 |
| private var writer = false |
| internal var gapStart: Int = 0 |
| internal var gapLen: Int = 0 |
| internal var anchors: ArrayList<Anchor> = arrayListOf() |
| |
| /** |
| * Read the slot table in [block]. Any number of readers can be created but a slot table cannot |
| * be read while it is being written to. |
| * |
| * @see SlotReader |
| */ |
| @InternalComposeApi |
| inline fun <T> read(block: (reader: SlotReader) -> T): T = openReader().let { reader -> |
| try { |
| block(reader) |
| } finally { |
| reader.close() |
| } |
| } |
| |
| /** |
| * Write to the slot table in [block]. Only one writer can be created for a slot table at a |
| * time and all readers must be closed an do readers can be created while the slot table is |
| * being written to. |
| * |
| * @see SlotWriter |
| */ |
| @InternalComposeApi |
| inline fun <T> write(block: (writer: SlotWriter) -> T): T = openWriter().let { writer -> |
| try { |
| block(writer) |
| } finally { |
| writer.close() |
| } |
| } |
| |
| /** |
| * Return a list of locations of slot table that contain the groups that contain [location]. |
| * |
| * [groupPathTo] creates a reader so it cannot be called when the slot table is being written |
| * to. |
| */ |
| @InternalComposeApi |
| fun groupPathTo(location: Int): List<Int> { |
| require(location < size) |
| val path = mutableListOf<Int>() |
| read { reader -> |
| var current = 0 |
| loop@ while (true) { |
| path.add(current) |
| if (current == location) break |
| current++ |
| while (current < location && !reader.isGroup(current)) current++ |
| if (current == location && !reader.isGroup(current)) break |
| while (current <= location) { |
| val end = reader.groupSize(current) + current + 1 |
| if (location < end) continue@loop |
| current = end |
| } |
| break |
| } |
| } |
| return path |
| } |
| |
| /** |
| * Open a reader. Any number of readers can be created but a slot table cannot be read while |
| * it is being written to. |
| * |
| * @see SlotReader |
| */ |
| @InternalComposeApi |
| fun openReader(): SlotReader { |
| if (writer) error("Cannot read while a writer is pending") |
| readers++ |
| return SlotReader(this) |
| } |
| |
| /** |
| * Open a writer. Only one writer can be created for a slot table at a time and all readers |
| * must be closed an do readers can be created while the slot table is being written to. |
| * |
| * @see SlotWriter |
| */ |
| @InternalComposeApi |
| fun openWriter(): SlotWriter { |
| if (writer) error("Cannot start a writer when another writer is pending") |
| if (readers > 0) error("Cannot start a writer when a reader is pending") |
| writer = true |
| return SlotWriter(this) |
| } |
| |
| /** |
| * Ensure a slot table is well-formed by verifying the internal structure of the slot table |
| * is consistent. This method will throw an exception when it detects inconsistency in the |
| * internal structure of the slot table. A slot table can be invalid (contain incorrect |
| * information about a composition) but still be well-formed but all valid slot tables are |
| * well-formed. |
| */ |
| @TestOnly |
| @InternalComposeApi |
| fun verifyWellFormed() { |
| var current = 0 |
| |
| fun validateGroup(parentLocation: Int, parent: Group?): Int { |
| val location = current++ |
| val group = slots[location].asGroup |
| require(group.parent == parent) { "Incorrect parent for group at $location" } |
| val end = location + group.slots + 1 |
| val parentEnd = parentLocation + (parent?.slots?.let { it + 1 } ?: size) |
| require(end <= size) { "Group extends past then end of its table at $location" } |
| require(end <= parentEnd) { "Group extends past its parent at $location" } |
| require(!group.isNode || group.node != null) { |
| "Node groups must have a node at $location" |
| } |
| |
| // Find the first child |
| while (current < end && slots[current] !is Group) current++ |
| |
| // Validate the child groups |
| var nodeCount = 0 |
| while (current < end) { |
| nodeCount += validateGroup(location, group) |
| } |
| require(group.nodes == nodeCount) { |
| "Incorrect node count for group at $location, expected ${ |
| group.nodes |
| }, received $nodeCount" |
| } |
| return if (group.isNode) 1 else nodeCount |
| } |
| |
| // Verify the groups are well-formed |
| require(gapStart == size) { "Gap is not at the end of the table" } |
| if (size > 0) |
| validateGroup(0, null) |
| |
| // Verify the anchors are well-formed |
| var lastLocation = -1 |
| for (anchor in anchors) { |
| val location = anchor.location(this) |
| require(location in 0..size) { "Location out of bound" } |
| require(lastLocation < location) { "Anchor is out of order" } |
| lastLocation = location |
| } |
| } |
| |
| /** |
| * The number of active slots in the slot table. The current capacity of the slot table is at |
| * lease [size]. |
| */ |
| @InternalComposeApi |
| val size: Int get() = slots.size - gapLen |
| |
| internal fun close(reader: SlotReader) { |
| require(reader.table === this && readers > 0) { "Unexpected reader close()" } |
| readers-- |
| } |
| |
| internal fun close(writer: SlotWriter) { |
| require(writer.table === this && this.writer) { "Unexpected writer close()" } |
| this.writer = false |
| clearGap() |
| } |
| |
| internal fun effectiveIndex(index: Int) = if (index < gapStart) index else gapLen + index |
| |
| internal fun clearGap() = repeat(gapLen) { i -> slots[gapStart + i] = null } |
| |
| internal fun anchor(index: Int): Anchor { |
| // TODO: Consider a buffer gap list of anchors if middle inserts and deletes are common |
| val anchorIndex = effectiveIndex(index) |
| val location = anchors.search(anchorIndex) |
| return if (location < 0) { |
| val anchor = Anchor(anchorIndex) |
| anchors.add(-(location + 1), anchor) |
| anchor |
| } else anchors[location] |
| } |
| |
| internal fun updateAnchors(gapMovedTo: Int) { |
| if (gapStart < gapMovedTo) { |
| // Gap is moving up |
| // All anchors between the new gap and the old gap switch to be anchored to the |
| // front of the table instead of the end. |
| val rangeStart = gapStart + gapLen |
| val rangeEnd = gapMovedTo + gapLen |
| var index = anchors.locationOf(rangeStart) |
| while (index < anchors.size) { |
| val anchor = anchors[index] |
| if (anchor.loc < rangeEnd) { |
| anchor.loc -= gapLen |
| index++ |
| } else break |
| } |
| } else { |
| // Gap is moving down. All anchors between gapMoveTo and gapStart need now to be |
| // anchored to the end of the table instead of the front of the table. |
| val rangeStart = gapMovedTo |
| val rangeEnd = gapStart |
| var index = anchors.locationOf(rangeStart) |
| while (index < anchors.size) { |
| val anchor = anchors[index] |
| if (anchor.loc < rangeEnd) { |
| anchor.loc += gapLen |
| index++ |
| } else break |
| } |
| } |
| } |
| |
| internal fun anchorGapResize(delta: Int) { |
| val start = anchors.locationOf(gapStart + gapLen) |
| for (index in start until anchors.size) |
| anchors[index].loc += delta |
| } |
| |
| internal fun removeAnchors(gapStart: Int, size: Int): Boolean { |
| val removeStart = gapStart |
| val removeEnd = gapStart + size |
| var index = anchors.locationOf(gapStart + size).let { |
| if (it >= anchors.size) it - 1 else it |
| } |
| var anchorsRemoved = false |
| while (index >= 0) { |
| val anchor = anchors[index] |
| if (anchor.loc >= removeStart) { |
| if (anchor.loc < removeEnd) { |
| anchor.loc = -1 |
| anchors.removeAt(index) |
| anchorsRemoved = true |
| } |
| index-- |
| } else break |
| } |
| return anchorsRemoved |
| } |
| |
| internal fun moveAnchors(originalLocation: Int, newLocation: Int, size: Int) { |
| val effectiveStart = effectiveIndex(originalLocation) |
| val effectiveEnd = effectiveIndex(originalLocation + size) |
| |
| // Remove all the anchors in range from the original location |
| val index = anchors.locationOf(effectiveStart) |
| val removedAnchors = mutableListOf<Anchor>() |
| if (index >= 0) { |
| while (index < anchors.size) { |
| val anchor = anchors[index] |
| if (anchor.loc >= effectiveStart && anchor.loc < effectiveEnd) { |
| removedAnchors.add(anchor) |
| anchors.removeAt(index) |
| } else break |
| } |
| } |
| |
| // Insert the anchors into there new location |
| for (anchor in removedAnchors) { |
| val location = anchorLocation(anchor) |
| val newAnchorLocation = location - originalLocation + newLocation |
| val effectiveLocation = effectiveIndex(newAnchorLocation) |
| anchor.loc = effectiveLocation |
| val insertIndex = anchors.locationOf(effectiveLocation) |
| anchors.add(insertIndex, anchor) |
| } |
| } |
| |
| internal fun anchorLocation(anchor: Anchor) = anchor.loc.let { |
| if (it > gapStart) it - gapLen else it |
| } |
| |
| internal fun ownsAnchor(anchor: Anchor?): Boolean { |
| if (anchor == null) return false |
| val loc = anchor.loc |
| if (loc < 0) return false |
| val location = anchors.search(loc) |
| if (location < 0) return false |
| return anchors[location] === anchor |
| } |
| |
| @InternalComposeApi |
| companion object { |
| @InternalComposeApi |
| val EMPTY = object : Any() { |
| override fun toString(): String { |
| return "EMPTY" |
| } |
| } |
| } |
| } |
| |
| private fun ArrayList<Anchor>.locationOf(index: Int) = |
| search(index).let { if (it >= 0) it else -(it + 1) } |
| private fun ArrayList<Anchor>.search(index: Int) = binarySearch { it.loc.compareTo(index) } |
| |
| /** |
| * Information about groups and their keys. |
| */ |
| @InternalComposeApi |
| class KeyInfo internal constructor( |
| /** |
| * The group key. |
| */ |
| val key: Int, |
| |
| /** |
| * The data key for the group |
| */ |
| val dataKey: Any?, |
| |
| /** |
| * The location of the group. |
| */ |
| val location: Int, |
| |
| /** |
| * The number of nodes in the group. If the group is a node this is always 1. |
| */ |
| val nodes: Int, |
| |
| /** |
| * The index of the key info in the list returned by extractKeys |
| */ |
| val index: Int, |
| |
| /** |
| * The group |
| */ |
| internal val group: Group |
| ) |
| |
| @InternalComposeApi |
| class Anchor(internal var loc: Int) { |
| val valid get() = loc >= 0 |
| fun location(slots: SlotTable) = slots.anchorLocation(this) |
| } |
| |
| private typealias GroupKind = Int |
| |
| private const val GROUP: GroupKind = 0 |
| private const val NODE: GroupKind = 1 |
| private const val DATA: GroupKind = 2 |
| |
| private const val MIN_GROWTH_SIZE = 128 |