In depth understanding of jetpack compose kernel: slottable system

introduction

Compose There are three stages in drawing , Combine > Layout > draw . The latter two passes are similar to the rendering process of traditional views , The only combination is Compose Unique .Compose Generate rendering trees by combining , This is a Compose The core competencies of the framework , And this process mainly depends on SlotTable Realized , This article will introduce SlotTable System .

1. from Compose The rendering process starts

be based on Android The development process of native views , Its essence is to build a tree based on View The rendering tree , When the frame signal arrives, the depth traversal starts from the root node , In turn, calls measure/layout/draw, Until the rendering of the whole tree is completed . about Compose There is also such a rendering tree , Let's call this Compositiion, The nodes on the tree are LayoutNode,Composition adopt LayoutNode complete measure/layout/draw The process will eventually UI Display on screen .Composition rely on Composable Function to create and update , The so-called combination and reorganization .

For example, above Composable Code , After execution, the... On the right will be generated Composition.

How a function is converted to after execution LayoutNode What about ？ thorough Text After the source code, I found that its internal call Layout, Layout Is a custom layout Composable, We use all kinds of directly Composable In the end, it's all by calling Layout To achieve different layout and display effects .

//Layout.kt
@Composable inline fun Layout(
    content: @Composable () -> Unit,
    modifier: Modifier = Modifier,
    measurePolicy: MeasurePolicy
) {
    
    val density = LocalDensity.current
    val layoutDirection = LocalLayoutDirection.current
    val viewConfiguration = LocalViewConfiguration.current
    ReusableComposeNode<ComposeUiNode, Applier<Any>>(
        factory = ComposeUiNode.Constructor, 
        update = {
    
            set(measurePolicy, ComposeUiNode.SetMeasurePolicy)
            set(density, ComposeUiNode.SetDensity)
            set(layoutDirection, ComposeUiNode.SetLayoutDirection)
            set(viewConfiguration, ComposeUiNode.SetViewConfiguration)
        },
        skippableUpdate = materializerOf(modifier),
        content = content
    )
}

Layout Through internal ReusableComposeNode establish LayoutNode.

• factory Is to create LayoutNode Our factory
• update The record will be updated Node The state of is used for subsequent rendering

Continue to enter ReusableComposeNode ：

//Composables.kt
inline fun <T, reified E : Applier<*>> ReusableComposeNode(
    noinline factory: () -> T,
    update: @DisallowComposableCalls Updater<T>.() -> Unit,
    noinline skippableUpdate: @Composable SkippableUpdater<T>.() -> Unit,
    content: @Composable () -> Unit
) {
    
    //... 
    $composer.startReusableNode()
    //...
    $composer.createNode(factory)
    //...
    Updater<T>(currentComposer).update()
    //...
    $composer.startReplaceableGroup(0x7ab4aae9)
    content()
    $composer.endReplaceableGroup()
    $composer.endNode()
}

We know Composable After the function is compiled, it will be passed into Composer, The code is based on the incoming Composer Completed a series of operations , The main logic is clear ：

• Composer#createNode Create nodes
• Updater#update to update Node state
• content() Continue with the internal Composable, Create child nodes .

Besides , The code is also interspersed with startXXX/endXXX , Such pairwise calls are like pressing the stack when traversing a tree in depth / Out of the stack

startReusableNode
    NodeData // Node data 
    startReplaceableGroup
        GroupData //Group data 
        ... //  Son Group
    endGroup
endNode

It's not just ReusableComposeNode This kind of built-in Composable, We wrote it ourselves Composable The compiled code of the function body will also insert a large number of startXXX/endXXX, These are all Composer Yes SlotTable The process of access ,Composer The function of is to SlotTable To create and update Composition.

The picture below is Composition,Composer And SlotTable Relational class diagram

2. First time to know SlotTable

We will Composable The rendering tree generated after execution is called Compositioin. In fact, to be more precise ,Composition There are two trees in the , One is LayoutNode Trees , This is the tree that actually performs rendering ,LayoutNode Can be like View Complete the same measure/layout/draw And so on ; And the other tree is SlotTable, It records Composition Various data states in . The state of the traditional view is recorded in View In the object , stay Compose Function oriented programming, not object-oriented , So these states need to depend on SlotTable Manage and maintain .

Composable All data generated during function execution will be stored in SlotTable, Include State、CompositionLocal,remember Of key And value wait , These data do not disappear with the function out of the stack , Can exist across reorganization .Composable If the function generates new data during reorganization, it will be updated SlotTable.

SlotTable Data stored in Slot in , One or more Slot It belongs to another Group. Can be Group It can be understood as nodes in the tree . say SlotTable It's a tree , In fact, it is not a real tree data structure , It uses linear arrays to express the semantics of a tree , from SlotT
able You can see this in the definition of ：

//SlotTable.kt
internal class SlotTable : CompositionData, Iterable<CompositionGroup> {
    

    /** * An array to store group information that is stored as groups of [Group_Fields_Size] * elements of the array. The [groups] array can be thought of as an array of an inline * struct. */
    var groups = IntArray(0)
        private set
 
    /** * An array that stores the slots for a group. The slot elements for a group start at the * offset returned by [dataAnchor] of [groups] and continue to the next group's slots or to * [slotsSize] for the last group. When in a writer the [dataAnchor] is an anchor instead of * an index as [slots] might contain a gap. */
    var slots = Array<Any?>(0) {
     null }
        private set

SlotTable There are two array members ,groups Array storage Group Information ,slots Storage Group Data under its jurisdiction . The advantage of using arrays instead of structured storage is that it can improve the accuracy of “ Trees ” Access speed of . Compose The frequency of recombination is very high , The reorganization process will continue to SlotTable To read and write , The time complexity of accessing the array is only O(1), Therefore, the use of linear array structure helps to improve the performance of reorganization .

groups It's a IntArray, Every time 5 individual Int Form a group Group Information about

• key : Group stay SlotTable Logo in , stay Parent Group It's the only one
• Group info: Int Of Bit Bits store some Group Information , For example, whether it is a Node, Does it include Data etc. , This information can be obtained by bit mask .
• Parent anchor: Parent stay groups Position in , That is, the offset from the array pointer
• Size: Group: Contains Slot The number of
• Data anchor： relation Slot stay slots The starting position in the array

slots It's where the data is really stored ,Composable Any type of data can be generated during execution , So the array type is Any?. Every Gorup The associated Slot Variable quantity ,Slot stay slots In accordance with the Group Store in order .

groups and slots It's not a linked list , So when the capacity is insufficient , They will be expanded .

3. In depth understanding of Group

Group The role of

SlotTable Data stored in Slot in , Why is the unit that acts as a node in the tree not Slot It is Group Well ？ because Group The following functions are provided ：

• Build a tree structure : Composable During the first execution , stay startXXXGroup China will create Group The node stores SlotTable, At the same time, by setting Parent anchor structure Group Father son relationship of ,Group The parent-child relationship is the basis for building the rendering tree .

• Identify structural changes : Compile time insert startXXXGroup Code generates recognizable based on the code location $key（parent It's the only one ）. In the first combination $key Will follow Group Deposit in SlotTable, In restructuring ,Composer be based on $key Can be identified by comparison Group The increased 、 Delete or move . In other words ,SlotTable Recorded in the Group Carrying location information , So this mechanism is also called Positional Memoization.Positional Memoization You can find SlotTable Structural changes , Eventually converted to LayoutNode Tree update .

• The smallest unit of reorganization : Compose The reorganization is “ intelligence ” Of ,Composable Function or Lambda Unnecessary execution can be skipped in reorganization . stay SlotTtable On , These functions or lambda Will be packaged one by one RestartGroup , therefore Group Is the smallest unit involved in the reorganization .

Group The type of

Composable Many different types of... Are generated at compile time startXXXGroup, They are SlotTable Insert Group At the same time , Auxiliary information will be stored to realize different functions ：

startXXXGroup	explain
startNode/startReusableNode	Insert a containing Node Of Group. For example, the beginning of the article ReusableComposeNode In the case of , The display calls startReusableNode , And then call createNode stay Slot Insert LayoutNode.
startRestartGroup	Insert a repeatable Group, It may be executed again with the reorganization , therefore RestartGroup Is the smallest unit of reorganization .
startReplaceableGroup	Insert a that can be replaced Group, For example, one if/else A code block is a ReplaceableGroup, It can be inserted in the reorganization of the latter from SlotTable Remove .
startMovableGroup	Insert a movable Group, In the reorganization, it may be in the brother Group Position shift occurs between .
startReusableGroup	Insert a reusable Group, Its internal data can be found in LayoutNode Reuse between , for example LazyList Of the same type in Item.

Of course startXXXGroup Not just for inserting new Group, It will also be used to track in reorganization SlotTable Existing Group, Compared with current execution
Compare the code in . Next, let's look at several different types of startXXXGroup In what kind of code .

4. Generated at compile time startXXXGroup

Previously, I introduced startXXXGroup Several types of , We usually write Compose Code , Have no sense of them , Then, under what conditions did they generate ？ Here are some common startXXXGroup Time to generate ：

startReplaceableGroup

As mentioned earlier Positional Memoization The concept of , namely Group Deposit in SlotTable when , Will carry location-based $key, This helps identify SlotTable The structural change of . The following code can explain this feature more clearly

@Composable
fun ReplaceableGroupTest(condition: Boolean) {
    
    if (condition) {
    
        Text("Hello") //Text Node 1
    } else {
    
        Text("World") //Text Node 2
    }
}

This code , When condition from true Turn into false, This means that the rendering tree should remove the old Text Node 1 , And add a new Text Node 2. In the source code, we do not Text Add recognizable key, If you only follow the source code , The program does not recognize counditioin Before and after the change Node Different , This may cause the old node state to remain ,UI Not as expected .

Compose How to solve this problem , Take a look at what the above code looks like after compilation （ Pseudo code ）：

@Composable
fun ReplaceableGroupTest(condition: Boolean, $composer: Composer?, $changed: Int) {
    
    if (condition) {
    
        $composer.startReplaceableGroup(1715939608)
        Text("Hello")
        $composer.endReplaceableGroup()
    } else {
    
        $composer.startReplaceableGroup(1715939657)
        Text("World")
        $composer.endReplaceableGroup()
    }
}

You can see , Compiler is if/else Each conditional branch is inserted RestaceableGroup , And added different $key. So when condition When something changes , We can identify Group There is a change , So as to change the structure SlotTable, Instead of just updating the original Node.

if/else Even if multiple... Are called internally Composable（ For example, there may be multiple Text) , They will only be packaged in one RestartGroup , Because they are always inserted together / Delete , There is no need to generate Group .

startMovableGroup

@Composable
fun MoveableGroupTest(list: List<Item>) {
    
    Column {
    
        list.forEach {
     
            Text("Item:$it")
        }
    }
}

The above code is an example of displaying a list . Because each row of the list is in for Generated in the loop , Cannot implement... Based on code location Positional Memoization, If parameters list There is a change , For example, a new one is inserted Item, here Composer Unrecognized Group The displacement of , It will be deleted and rebuilt , Affect reorganization performance .

For this class, you cannot rely on the compiler to generate $key The problem of ,Compose Gave the solution , Can pass key {...} Manually add a unique index key, Easy to identify Item New , Improve reorganization performance . The optimized code is as follows ：

//Before Compiler
@Composable
fun MoveableGroupTest(list: List<Item>) {
    
    Column {
    
        list.forEach {
     
            key(izt.id) {
     //Unique key
                Text("Item:$it")
            }
            
        }
    }
}

The above code will be inserted after compilation startMoveableGroup：

@Composable
fun MoveableGroupTest(list: List<Item>, $composer: Composer?, $changed: Int) {
    
    Column {
    
        list.forEach {
     
            key(it.id) {
    
                $composer.startMovableGroup(-846332013, Integer.valueOf(it));
                Text("Item:$it")
                $composer.endMovableGroup();
            }
        }
    }
}

startMoveableGroup Except for GroupKey An auxiliary DataKey. When you type list There is an increase in the data / When deleting or shifting ,MoveableGroup Can be based on DataKey Identify whether it is displacement rather than destruction reconstruction , Improve the performance of reorganization .

startRestartGroup

RestartGroup Is a reconfigurable unit , Every Composable Functions can participate in reorganization alone , So their function bodies will be inserted startRestartGroup/endRestartGroup, The code before and after compilation is as follows ：

// Before compiler (sources)
@Composable
fun RestartGroupTest(str: String) {
    
    Text(str)
}

// After compiler
@Composable
fun RestartGroupTest(str: String, $composer: Composer<*>, $changed: Int) {
    
    $composer.startRestartGroup(-846332013)
    // ...
    Text(str)
    $composer.endRestartGroup()?.updateScope {
     next ->
        RestartGroupTest(str, next, $changed or 0b1)
    }
}

to glance at startRestartGroup What did you do

//Composer.kt
fun startRestartGroup(key: Int): Composer {
    
    start(key, null, false, null)
    addRecomposeScope() 
    return this
}

private fun addRecomposeScope() {
    
    //...
    val scope = RecomposeScopeImpl(composition as CompositionImpl)
    invalidateStack.push(scope) 
    updateValue(scope)
    //...
}

Here is mainly to create RecomposeScopeImpl And deposit in SlotTable .

• RecomposeScopeImpl It is wrapped in a Composable function , When it needs to participate in restructuring ,Compose From SlotTable Find it in and call RecomposeScopeImpl#invalide() Mark failure , When restructuring comes Composable The function is re executed .
• RecomposeScopeImpl Cached to invalidateStack, And in Composer#endRestartGroup() Back in .
• updateScope Set up the... That need to participate in the reorganization Composable function , It is actually a recursive call to the current function . Be careful endRestartGroup The return value of is nullable , If RestartGroupTest If it does not depend on any state, it does not need to participate in the reorganization , You will return null.

so , No matter what Compsoable Whether it is necessary to participate in the reorganization , The generated code is the same . This reduces the complexity of the code generation logic , Leave the judgment to the runtime .

5. SlotTable Of Diff And traversal

SlotTable Of Diff

Declarative framework , The rendering tree is updated through Diff Realized , such as React adopt VirtualDom Of Diff Realization Dom Local update of tree , promote UI Refresh performance .

SlotTable Namely Compose Of “Virtual Dom”,Composable At the time of initial execution SlotTable Insert Group And corresponding Slot data . When Composable When participating in the reorganization , Based on the code status quo and SlotTable In the state of Diff, Find out Composition Status that needs to be updated in , And finally applied to LayoutNode Trees .

This Diff The process is also in startXXXGroup Completed in the process , The concrete implementation is focused on Composer#start() ：

//Composer.kt
private fun start(key: Int, objectKey: Any?, isNode: Boolean, data: Any?) {
    
    //...
    
    if (pending == null) {
    
        val slotKey = reader.groupKey
        if (slotKey == key && objectKey == reader.groupObjectKey) {
    
            //  adopt  key  Comparison , determine  group  The nodes have not changed , Compare the data 
            startReaderGroup(isNode, data)
        } else {
    
            // group  The node has changed , establish  pending  Follow up 
            pending = Pending(
                reader.extractKeys(),
                nodeIndex
            )
        }
    }
    //...
    if (pending != null) {
    
        //  seek  gorup  Whether in  Compositon  in 
        val keyInfo = pending.getNext(key, objectKey)
        if (keyInfo != null) {
    
            // group  There is , But the position has changed , Need help  GapBuffer  Carry out node displacement 
            val location = keyInfo.location
            reader.reposition(location)
            if (currentRelativePosition > 0) {
    
                //  Yes  Group  To displace 
                recordSlotEditingOperation {
     _, slots, _ ->
                    slots.moveGroup(currentRelativePosition)
                }
            }
            startReaderGroup(isNode, data)
        } else {
    
            //...
            val startIndex = writer.currentGroup
            when {
    
                isNode -> writer.startNode(Composer.Empty)
                data != null -> writer.startData(key, objectKey ?: Composer.Empty, data)
                else -> writer.startGroup(key, objectKey ?: Composer.Empty)
            }
        }
    }
    
    //...
}

start Method has four parameters ：

• key: Generated at compile time based on code location $key
• objectKey: Use key{} Added auxiliary key
• isNode： At present Group Is it a Node, stay startXXXNode in , Here... Will be passed in true
• data： At present Group Is there a data , stay startProviders Will be passed in providers

start There are many pairs of methods reader and writer Call to , They will be introduced later , All you need to know is that they can track SlotTable The current location that should be accessed in , And finish reading / Write operations . The above code has been refined , The logic is clear ：

• be based on key Compare Group Are they the same? （SlotTable Record and code status in ）, If Group There is no change , Call startReaderGroup Further judgment Group Whether the data in has changed
• If Group There is a change , Means that the start in Group Need to add or shift , adopt pending.getNext lookup key Whether in Composition in , If it exists, it means that Group Displacement required , adopt slot.moveGroup To displace
• If Group Need to add , According to Group type , Call different writer#startXXX take Group Insert SlotTable

Group The data comparison within is in startReaderGroup In the , The implementation is relatively simple

private fun startReaderGroup(isNode: Boolean, data: Any?) {
    
    //...
    if (data != null && reader.groupAux !== data) {
    
        recordSlotTableOperation {
     _, slots, _ ->
            slots.updateAux(data)
        }
    }
    //... 
}

• reader.groupAux Get current Slot Data in and data compare
• If different , Call recordSlotTableOperation Update the data .

Pay attention to that SlotTble The update of does not take effect immediately , This will be introduced later .

SlotReader & SlotWriter

See above ,start In the process of the SlotTable Both reading and writing depend on Composition Of reader and writer To complete .

writer and reader There are corresponding startGroup/endGroup Method . about writer Come on startGroup Represents right SlotTable Data change of , For example, insert or delete a Group ; about reader Come on startGroup It means moving currentGroup Pointer to the latest position .currentGroup and currentSlot Point to SlotTable Currently visiting Group and Slot The location of .

to glance at SlotWriter#startGroup Insert a Group The implementation of the ：

private fun startGroup(key: Int, objectKey: Any?, isNode: Boolean, aux: Any?) {
    

    //...
    insertGroups(1) // groups  Assign a new location in 
    val current = currentGroup 
    val currentAddress = groupIndexToAddress(current)
    val hasObjectKey = objectKey !== Composer.Empty
    val hasAux = !isNode && aux !== Composer.Empty
    groups.initGroup( // fill  Group  Information 
        address = currentAddress, //Group  Where to insert 
        key = key, //Group  Of  key
        isNode = isNode, // Is it a  Node 
        hasDataKey = hasObjectKey, // Is there a  DataKey
        hasData = hasAux, // Whether it contains data 
        parentAnchor = parent, // relation Parent
        dataAnchor = currentSlot // relation Slot Address 
    )
    //...
    val newCurrent = current + 1
    this.parent = current // to update parent
    this.currentGroup = newCurrent 
    //...
}

• insertGroups Used in groups Assign insert... In Group Space used , It will involve Gap Buffer Concept , We will describe in detail later .
• initGroup： be based on startGroup The parameters passed in are initialized Group Information . These parameters are changed with different types at compile time startXXXGroup Generated , Actually write here to SlotTable in
• The last update currentGroup The latest location of .

Look again. SlotReader#startGroup The implementation of the ：

fun startGroup() {
    
    //...
    parent = currentGroup
    currentEnd = currentGroup + groups.groupSize(currentGroup)
    val current = currentGroup++
    currentSlot = groups.slotAnchor(current)
    //...
}

The code is very simple , The main thing is to update currentGroup,currentSlot Etc .

SlotTable adopt openWriter/openReader establish writer/reader, The end of use needs to call respective close close .reader Sure open Multiple simultaneous use , and writer Only at the same time open One . To avoid concurrency problems , writer And reader You can't do it at the same time , So for SlotTable Of write The operation needs to be delayed until after the reorganization . So we see a lot in the source code recordXXX Method , They propose the write operation as a Change It was recorded that ChangeList, Wait for the combination to finish and apply again .

6. SlotTable The change is delayed

Composer Use in changes Record the change list

//Composer.kt
internal class ComposerImpl {
    
    //...
    private val changes: MutableList<Change>,
    //...
    
    private fun record(change: Change) {
    
        changes.add(change)
    }
}

Change It's a function , Execute specific change logic , The function signature, i.e. the parameters, are as follows ：

//Composer.kt
internal typealias Change = (
    applier: Applier<*>,
    slots: SlotWriter,
    rememberManager: RememberManager
) -> Unit

• applier： Pass in Applier Used to apply changes to LayoutNode Trees , In the following article, we will introduce in detail Applier
• slots： Pass in SlotWriter Used to update the SlotTable
• rememberManger： Pass in RememberManager Used to register Composition Lifecycle Callback , You can complete a specific business at a specific point in time , such as LaunchedEffect On the first entry into Composition Created on CoroutineScope, DisposableEffect In from Composition Call when leaving onDispose , This is achieved by registering callbacks here .

Record Change

We use remember{} Take... For example Change How to be recorded .
remember{} Of key and value Will do Composition The status in is recorded to SlotTable in . Restructuring , When remember Of key When something changes ,value Will recalculate value And update the SlotTable.

//Composables.kt
@Composable
inline fun <T> remember(
    key1: Any?,
    calculation: @DisallowComposableCalls () -> T
): T {
    
    return currentComposer.cache(currentComposer.changed(key1), calculation)
}

//Composer.kt
@ComposeCompilerApi
inline fun <T> Composer.cache(invalid: Boolean, block: () -> T): T {
    
    @Suppress("UNCHECKED_CAST")
    return rememberedValue().let {
    
        if (invalid || it === Composer.Empty) {
    
            val value = block()
            updateRememberedValue(value)
            value
        } else it
    } as T
}

Above is remember Source code

• Composer#changed Method SlotTable Stored in the key And key1 Compare
• Composer#cache in ,rememberedValue Will read SlotTable Current cached in value.
• If at this time key The difference is found in the comparison of , Call block Calculate and return the new value, At the same time call updateRememberedValue take value Update to SlotTable.

updateRememberedValue Will eventually call Composer#updateValue, Take a look at the implementation ：

//Composer.kt
internal fun updateValue(value: Any?) {
    
    //...
    val groupSlotIndex = reader.groupSlotIndex - 1 // Update location Index
    
    recordSlotTableOperation(forParent = true) {
     _, slots, rememberManager ->
        if (value is RememberObserver) {
    
            rememberManager.remembering(value) 
        }
        when (val previous = slots.set(groupSlotIndex, value)) {
    // to update 
            is RememberObserver ->
                rememberManager.forgetting(previous)
            is RecomposeScopeImpl -> {
    
                val composition = previous.composition
                if (composition != null) {
    
                    previous.composition = null
                    composition.pendingInvalidScopes = true
                }
            }
        }
    }
    //...
}

// Record updates  SlotTable  Of  Change

private fun recordSlotTableOperation(forParent: Boolean = false, change: Change) {
    
    realizeOperationLocation(forParent)
    record(change) // Record  Change
}

The key code here is right recordSlotTableOperation Call to ：

• take Change Add to changes list , here Change The content of is through SlotWriter#set take value Update to SlotTable The designated location of ,groupSlotIndex It's calculated value stay slots Offset in .
• previous return remember The old value , It can be used for some post-processing . It can also be seen from here , RememberObserver And RecomposeScopeImpl And so on Composition The state of .
  • RememberObserver Is a lifecycle callback ,RememberManager#forgetting Register it , When previous from Composition removed ,RememberObserver Will receive notice
  • RecomposeScopeImpl Is a reconfigurable unit ,pendingInvalidScopes = true This means that the recombination unit is from Composition Middle leave .

except remember, Others involve SlotTable Structural change , Delete... For example 、 Mobile nodes, etc. will also use changes Delay in taking effect （ Insert operation pair reader There is no impact, so it will be applied immediately ）. In the example remember Of the scene Change Don't involve LayoutNode Update , therefore recordSlotTableOperation Not used in Applier Parameters . But when race causes SlotTable When the structure changes , Changes need to be applied to LayoutNoel Trees , At this time, it is necessary to use Applier 了 .

application Change

Mentioned earlier , Recorded changes Wait for the combination to complete before executing .

When Composable On first execution , stay Recomposer#composeIntial Finish in Composable The combination of

//Composition.kt
override fun setContent(content: @Composable () -> Unit) {
    
    //...
    this.composable = content
    parent.composeInitial(this, composable)
}

//Recomposer.kt
internal override fun composeInitial(
    composition: ControlledComposition,
    content: @Composable () -> Unit
) {
    
    //...
    composing(composition, null) {
    
        composition.composeContent(content) // Executive combination 
    }
    //...

    composition.applyChanges() // application  Changes
    //...
}

You can see , Immediately after the combination , call Composition#applyChanges() application changes. Again , Also called after each reorganization applyChanges.

override fun applyChanges() {
    
      
      val manager = ...
      //...
      applier.onBeginChanges()
      // Apply all changes
      slotTable.write {
     slots ->
          val applier = applier
          changes.fastForEach {
     change ->
              change(applier, slots, manager)
          }
          hanges.clear()
       }
       applier.onEndChanges()
       //...
}

stay applyChanges See inside right changes Traversal and execution of . In addition, it will pass Applier Callback applyChanges The beginning and the end of .

7. UiApplier & LayoutNode

SlotTable How structural changes are reflected in LayoutNode On the tree ？

We are going to Composable The rendering tree generated after execution is called Composition. Actually Composition It is the macro cognition of this rendering tree , To be precise Composition Through internal Applier Maintain LayoutNode Tree and perform concrete rendering .SlotTable The structure changes with Change The application of the list is reflected in LayoutNode on the tree .

image View equally ,LayoutNode adopt measure/layout/draw Wait for a series of methods to complete the specific rendering . In addition, it provides insertAt/removeAt And other methods to realize the change of subtree structure . These methods will be UiApplier Call in ：

//UiApplier.kt
internal class UiApplier(
    root: LayoutNode
) : AbstractApplier<LayoutNode>(root) {
    

    override fun insertTopDown(index: Int, instance: LayoutNode) {
    
        // Ignored
    }

    override fun insertBottomUp(index: Int, instance: LayoutNode) {
    
        current.insertAt(index, instance)
    }

    override fun remove(index: Int, count: Int) {
    
        current.removeAt(index, count)
    }

    override fun move(from: Int, to: Int, count: Int) {
    
        current.move(from, to, count)
    }

    override fun onClear() {
    
        root.removeAll()
    }

}

UiApplier Used to update and modify LayoutNode Trees ：

• down()/up() Used for mobile current The location of , Complete the navigation on the tree .
• insertXXX/remove/move Used to modify the structure of the tree . among insertTopDown and insertBottomUp Are used to insert new nodes , It's just that the way you insert it is different , One is from bottom to top and the other is from top to bottom , Selecting different insertion sequences for different tree structures can help improve performance . for example Android Terminal UiApplier Mainly depends on insertBottomUp Insert new node , because Android Rendering logic , The change of child nodes will affect the re creation of parent nodes measure, Inserting downward from this point can avoid affecting too many parent nodes , Improve performance , because attach Last .

Composable The execution of depends only on Applier Abstract interface ,UiApplier And LayoutNode It's just Android Corresponding implementation of the platform , In theory, we can customize Applier And Node You can build your own rendering engine . for example Jake Wharton There is one named Mosaic Project , It's through customization Applier and Node The custom rendering logic is implemented .

Root Node The creation of

Android Under the platform , We are Activity#setContent Call in Composable：

//Wrapper.android.kt
internal fun AbstractComposeView.setContent(
    parent: CompositionContext,
    content: @Composable () -> Unit
): Composition {
    
    //...
    val composeView = ...
    return doSetContent(composeView, parent, content)
}

private fun doSetContent(
    owner: AndroidComposeView,
    parent: CompositionContext,
    content: @Composable () -> Unit
): Composition {
    
    //...
    val original = Composition(UiApplier(owner.root), parent)
    val wrapped = owner.view.getTag(R.id.wrapped_composition_tag)
        as? WrappedComposition
        ?: WrappedComposition(owner, original).also {
    
            owner.view.setTag(R.id.wrapped_composition_tag, it)
        }
    wrapped.setContent(content)
    return wrapped
}

• doSetContent Created in Composition example , At the same time, the binding Root Node Of Applier.Root Node By AndroidComposeView hold , come from View World dispatchDraw as well as KeyEvent,touchEvent Wait is from here Root Node Passed on to Compose The world .
• WrappedComposition It's a decorator , Also used for Composition And AndroidComposeView Establishing a connection , A lot of what we often use comes from Android Of CompositionLocal It is built here , such as LocalContext,LocalConfiguration wait .

8. SlotTable And Composable Life cycle

Composable The life cycle of can be summarized as the following three stages , Now I know SlotTable after , We can also from SlotTable Explain it from the angle of ：

• Enter：startRestartGroup Lieutenant general Composable Corresponding Group Deposit in SlotTable
• Recompose：SlotTable Search for Composable （by RecomposeScopeImpl） Re execution , And update the SlotTable
• Leave：Composable Corresponding Group from SlotTable Remove .

stay Composable Side effects of use in API Can act as Composable Lifecycle callbacks to use

DisposableEffect(Unit) {
    
    //callback when entered the Composition & recomposed
    onDispose {
     
        //callback for leaved the Composition
    }
}

We use DisposableEffect For example , Take a look at how lifecycle callbacks are based on SlotTable The system completes . to glance at DisposableEffect The implementation of the , The code is as follows ：

@Composable
@NonRestartableComposable
fun DisposableEffect(
    key1: Any?,
    effect: DisposableEffectScope.() -> DisposableEffectResult
) {
    
    remember(key1) {
     DisposableEffectImpl(effect) }
}


private class DisposableEffectImpl(
    private val effect: DisposableEffectScope.() -> DisposableEffectResult
) : RememberObserver {
    
    private var onDispose: DisposableEffectResult? = null

    override fun onRemembered() {
    
        onDispose = InternalDisposableEffectScope.effect()
    }

    override fun onForgotten() {
    
        onDispose?.dispose()
        onDispose = null
    }

    override fun onAbandoned() {
    
        // Nothing to do as [onRemembered] was not called.
    }
}

You can see ,DisposableEffect Its essence is to use remember towards SlotTable In an DisposableEffectImpl, This is a RememberObserver The implementation of the . DisposableEffectImpl With my father Group Entering and leaving SlotTable , Will receive onRemembered and onForgotten The callback .

Remember what I said before applyChanges Do you , It happens after the reorganization

override fun applyChanges() {
    
      
  val manager = ... //  establish  RememberManager
  //...
  // Apply all changes
  slotTable.write {
     slots ->
      //...
      changes.fastForEach {
     change ->
          // application  changes,  take  ManagerObserver  Sign up for  RememberMananger
          change(applier, slots, manager)
      }
      //...
  }
  //...
  manager.dispatchRememberObservers() // Distribution callback 
}

As mentioned earlier ,SlotTable Occurs during a write operation changes It will be applied uniformly here , Of course, it also includes DisposableEffectImpl Insert / deleted record Of changes, Specifically, yes ManagerObserver Registration of , It'll be in the back dispatchRememberObservers Callback in .

Restructuring is optimistic

There is a paragraph about reorganization in the official website document ： Reorganization is “ optimistic ” Of

When recomposition is canceled, Compose discards the UI tree from the recomposition. If you have any side-effects that depend on the UI being displayed, the side-effect will be applied even if composition is canceled. This can lead to inconsistent app state.

Ensure that all composable functions and lambdas are idempotent and side-effect free to handle optimistic recomposition.

https://developer.android.com/jetpack/compose/mental-model#optimistic

At first sight, many people will not understand this passage, so , But after reading the source code, I believe I can understand its meaning . Here we call “ optimistic ” Refer to Compose The reorganization of always assumes that it will not be interrupted , Once an interruption occurs ,Composable The actions performed in do not really reflect SlotTable, Because we know through the source code applyChanges It happened in composiiton After a successful ending .

If the combination is interrupted , you are here Composable The state read in the function is likely to be the same as the final SlotTable Inconsistency in . So if we need to be based on Composition To deal with some side effects , You have to use DisposableEffect Such side effects API The parcel , Because we also know through the source code DisposableEffect The callback is applyChanges Executive , At this point, you can ensure that the reorganization has been completed , Get the status of and SlotTable Consistent .

9. SlotTable And GapBuffer

As mentioned earlier ,startXXXGroup China Association and SlotTable Medium Group Conduct Diff, If the comparison is not equal , Means that the SlotTable The structure of has changed , Need to be right Group Insert / Delete / Move , This process is based on Gap Buffer Realized .

Gap Buffer The concept comes from the data structure in the text editor , It can be understood as sliding in a linear array 、 Scalable cache area , Specific to the SlotTable in , Namely groups Unused areas in , This area can be in groups Move , promote SlotTble Update efficiency when the structure changes , Here is an example of ：

@Composable
fun Test(condition: Boolean) {
     
    if (condition) {
    
        Node1()
        Node2()
    }
    Node3()
    Node4()
}

SlotTable In the beginning, only Node3,Node4, And then according to the state change , Need to insert Node1,Node2, If there is no Gap Buffer,SlotTable The changes are shown in the figure below ：

Every time you insert a new Node Will result in SlotTable There is already Node The movement of the , inefficiency . Let's take another look at the introduction Gap Buffer The behavior after that ：

When inserting new Node when , Will change the array of Gap Move to the position to be inserted , Then start inserting new Node. Insert again Node1,Node2 Even their sons Node, It's all filling Gap Free area of , Will not affect the cause of Node The movement of the .
Look at the movement Gap The concrete realization of , The relevant code is as follows ：

//SlotTable.kt
private fun moveGroupGapTo(index: Int) {
    

    //...
            val groupPhysicalAddress = index * Group_Fields_Size
            val groupPhysicalGapLen = gapLen * Group_Fields_Size
            val groupPhysicalGapStart = gapStart * Group_Fields_Size
            if (index < gapStart) {
    
                groups.copyInto(
                    destination = groups,
                    destinationOffset = groupPhysicalAddress + groupPhysicalGapLen,
                    startIndex = groupPhysicalAddress,
                    endIndex = groupPhysicalGapStart
                )
            } 
      //... 
}

• Index Is to insert Group The location of , That is to say, we need to put Gap Move here
• Group_Fields_Size yes groups Middle unit Group The length of , Now it is a constant 5.

The meaning of several temporary variables is also very clear ：

• groupPhysicalAddress: Currently, you need to insert group The address of
• groupPhysicalGapLen: At present Gap The length of
• groupPhysicalGapStart： At present Gap From

When index < gapState when , Need to put Gap Move forward to index Position to prepare for new insertion . From behind copyInto We can see that ,Gap Is actually moved forward by group Move back to achieve , the startIndex Situated Node Copied to the Gap After the new location of , Here's the picture ：

So we don't really have to move Gap, As long as Gap Of start The pointer of moves to groupPyhsicalAddress that will do , new Node1 Will insert... Here . Of course ,groups After moving ,anchor And other related information should also be updated accordingly .

Finally, let's take a look at deleting Node At the time of the Gap Movement , The principle is similar ：

take Gap Move to be deleted Group Before , Then start deleting Node, such , The deletion process is actually a move Gap Of end Just the position , It is very efficient and ensures Gap Continuity of .

10. summary

SlotTable System is Compose From composition to rendering to screen , The most important part of the whole process , Let's review the whole process with the following figure ：

1. Composable The source code is inserted at compile time startXXXGroup/endXXXGroup Template code , Used to deal with SlotTable Tree traversal of .
2. Composable In the first combination ,startXXXGroup stay SlotTable Insert Group And pass $key distinguish Group In the code
3. Restructuring ,startXXXGroup Would be right SlotTable Do traversal and Diff, And pass changes Delay update SlotTable, It also applies to LayoutNode Trees
4. When the rendered frame arrives ,LayoutNode For the changed part measure > layout > draw, complete UI Partial refresh of .