Core to the runtime of Compose is the Composer. It is passed as an implicit parameter to every @Composable function and calls are inserted to Composer by the Compose Compiler Plugin.
This document goes into more detail about how the Composer detects changes and what must be true about the code generated by the Compose Compiler Plugin for the algorithm it uses to work.
The composer has three jobs,
rememberMemoization is a technique which remembers, based on the actual parameters of the call, the previous result of a function call instead of recalculating it every time. Positional Memoization is memoization but also considers where in the call graph the function is executed as implicitly one of the actual parameters.
Composition is the result of calling composable functions from some root composable function. The function calls, at runtime, form a tree. The location in this tree where the call to remember happens is considered an implicit parameter to remember. When the position is the same, the previous result of the lambda is used instead of calling it again. Consider the following example,
@Composable fun A() { val data = remember { Data() } … } @Composable fun B() { A() A() }
When B is called the first time, there are two copies of Data created, one for each invocation of A. However, when B is called again, during recomposition, the lambdas are not invoked again, the previous values are returned instead.
Note: the SlotTable is under active development and some of the following implementation details might be describe an older implementation
The Composer uses a side table to store information about the composable functions as they are executed that includes the results of the previous calls to remember, for example. This side table is often referred to as the Slot Table after the data structure used to hold it. The Slot Table records this information in a tree of groups flattened into two arrays, one storing information about the group and a second array storing the slot values (such as the result of calling remember). This is split into two arrays to avoid boxing overhead to store the 5 integer fields that make up the information stored about the group. Each group consists of a integer key, called Key, some Flags indicating what kind group it represents (is it a node group, for example); Nodes, the number of nodes generated in the group; Size, the size of the group (the total number of transitive children and itself); Slots, a reference to the location of the slots of the group in the slot array; and finally, Parent, an index of the parent group (to efficiently traverse the tree upward). These groups correspond to the call tree mentioned above in Positional Memoization where the position of positional memoization refers to the location of the group in the slot table generated by the call.
The Slot Table of calling B above might look something like this,
| Key | Flags | Nodes | Size | Parent | Slots |
|---|---|---|---|---|---|
| 1234 | 0 | 3 | -1 | 0 | |
| 4567 | 0 | 1 | 0 | 0 | |
| 4567 | 0 | 1 | 0 | 1 |
| Slots |
|---|
| <Data instance 0> |
| <Data instance 1> |
1234 has 0 slots because 0 - 0 is 0 both 4567 entries have one because 1 - 0 = 1 and 2 - 1 = 1, respectively.SlotTable is read by a SlotReader instance and can be updated by a SlotWriter instance. Only one SlotWriter can be open at any time for a SlotTable but only when no SlotReader is open. Any number of SlotReader instances can be open at the same time and can only be opened if there is no open SlotWriter instance open.SlotTable the arrays of the slot table are a gap buffer. The index of a group is the location ignoring the gap. The address of a group is its absolute location. To calculate the address of a group given an index, the address is index if the group is before the gap and index + gap_size if it is after the gap. The meaning of the Slot field changes if the slot is referencing the slots after the gap in the slot array, its value is the distance to the end of the array. That is the slot address is slot_array_size - slot. Slot is updated as the slot array gap is moved. When an index value is used the way it is called values is called an anchor.remember after a call to a composable function, for example) then the slots require their own group.The job of the compiler plugin is to transform @Composable calls and inject the calls into the runtime to allow it to generate the slot table.
The above code is rewritten by the plugin (ignoring skipping and restarting, for now) to look something like,
fun A($composer: Composer) { $composer.startGroup(1234) val data = remember($composer) { Data() } … $composer.endGroup() } @Composable fun B($composer: Composer) { $composer.startGroup(4567) A($composer) A($composer) $composer.endGroup() }
This code is sufficient to enable positional composition, but not skipping or restarting described
If the actual arguments of a function are the same as the last time it was called in the same position then it is assumed it will produce the same result and can be skipped. To determine if a function can be skipped, the previous values are remembered in the slot table and compared with the current values. If they are the same values, the function can be skipped.
Since A and B don't take parameters they can be skipped unconditionally as they are assumed to always produce the same result.
fun A($composer: Composer) { $composer.startGroup(1234) val data = remember($composer) { Data() } if (!$composer.skipping) { … } else { $composer.skipToEndGroup() } $composer.endGroup() } @Composable fun B($composer: Composer) { $composer.startGroup(4567) if (!$composer.skipping) { A($composer) A($composer) } else { $composer.skipToEndGroup() } $composer.endGroup() }
In this example $composer.skipping is false the first time B is invoked and true every subsequent call of B at the same position. The call to $composer.skipToEndGroup() requests the composer to skip the group end of B's group which includes both calls to A.
If the code was modified to have parameters then the parameters need to be checked.
@Composable fun A(text: String) { val data = remember { Data() } … } @Composable fun B(person: Person) { A(person.givenName) A(person.familyName) }
The resulting code might look something like,
fun A(text: String, $composer: Composer) { $composer.startGroup(1234) val data = remember($composer) { Data() } val changed = $composer.changed(text) if (changed || !$composer.skipping) { … } else { $composer.skipToEndGroup() } $composer.endGroup() } @Composable fun B(person: Person, $composer: Composer) { $composer.startGroup(4567) val changed = $composer.changed(person) if (changed || !$composer.skipping) { A(person.givenName, $composer) A(person.familyName, $composer) } else { $composer.skipToEndGroup() } $composer.endGroup() }
changed uses a slot in the slot table to store values from the previous composition so that they may be compared.changed is called cannot be conditional, therefore a non-short-circuiting || pattern needs to be used.The above code would be correct if Person was immutable. What if Person can change? If the value of givenName and familyName backed by mutableStateOf, then B must be called again, or restarted, whenever either givenName or familyName is modified. A restartable composable function is reported to the runtime using a startRestartGroup instead of just a startGroup call. For the above B this looks like,
@Composable fun B(person: Person, $composer: Composer) { $composer.startRestartGroup(4567) val changed = $composer.changed(person) if (changed || !$composer.skipping) { A(person.givenName, $composer) A(person.familyName, $composer) } else { $composer.skipToEndGroup() } $composer.endRestartGroup()?.updateScope { $composer: Composer -> B(person, $composer) } }
If the call to B needs to be restarted then the lambda passed to updateScope is invoked. endRestartGroup() will return null when no observable reads occurred in B. This means that the code above works correctly when Person is observable or immutable. If it is immutable then endRestartGroup() will return null, avoiding the creation of the lambda instance.
It is important that the code work correctly if Person is immutable or mutable as the implementation of Person might be in a different module and might change its implementation after the module containing B has beend compiled. This means that the code generated for B cannot assume anything about the implementation of Person that is not in its type declaration.
In the call $composer.skipToEndGroup(), if there are any functions that need to be restarted in the groups being skipped, the functions are restarted, by calling their restart lambdas, prior to skipToEndGroup() returning.
$changedThe compiler plugin also adds an additional parameter $changed that is used to avoid calling $composer.changed() in cases where either the value will never change or was already compared by the caller and there is no need to do it again. How this works is beyond the scope of this document as it doesn't affect how the Composer works, only what code the plugin generates.
A structural change is detected when the groups emitted by one or more composable functions change.
Consider the following function,
@Composable fun ShowPerson(person: Person) { Column { ShowName(person.name) if (person.employed) { ShowCompany(person.employer) } ShowEmail(person.email) } }
If person.employed becomes true the ShowCompany content should be inserted just after ShowName but before ShowEmail. If it becomes false, ShowCompany should be deleted.
A simplified slot table for a true version might look,
| # | Key | Size | Nodes |
|---|---|---|---|
| 0 | <ShowPerson> | 9 | 1 |
| 1 | <Column> | 8 | 1 |
| 2 | Node | 7 | 3 |
| 3 | <ShowName> | 2 | 1 |
| 4 | Node | 1 | 0 |
| 5 | <ShowCompany> | 2 | 1 |
| 6 | Node | 1 | 0 |
| 7 | <ShowEmail> | 2 | 1 |
| 8 | Node | 1 | 0 |
Where keys like <ShowPerson> is an arbitrary key generated by the compiler plugin for the ShowPerson function.
The sequence of calls used to produce this table are,
startRestartGroup(<ShowPerson>) startGroup(<Column>) startNode() startRestartGroup(<ShowName>) startNode() endNode() endRestartGroup() startRestartGroup(<ShowCompany>) startNode() endNode() endRestartGroup() startRestartGroup(<ShowEmail>) startNode() endNode() endRestartGroup() endNode() endGroup() endRestartGroup()
From now on, this kind of sequence will be represented as follows,
<ShowPerson> <Column> N <ShowName> N/ /G <ShowCompany> N/ /G <ShowEmail> N/ /G /N /G /G
Where <ShowPerson> is a startGroup(<ShowPerson>), N is a startNode(), N/ is a startNode() followed immediately by an endNode(), /G is an the appropriate end group call, /N is an endNode().
The sequence when employed is false is:
<ShowPerson> <Column> N <ShowName> N/ /G <ShowEmail> N/ /G /N /G /G
During recomposition, the slot table from the previous composition is consulted as each group is generated and if the new table would match what is in the old table then nothing has changed. In this case, it isn‘t until group #5, the <ShowCompany> group, it detects a difference. At this point it is not clear whether this is an insert, delete or move, so the groups remaining in the current group of the old slot table (the <Column>‘s Node group) are put into a hash table with the Key as the hash table key. <ShowEmail> is in the hash table so it’s group is scheduled to move to position #5, then the <ShowEmail> group is set as the current group and ShowEmail() is called. No changes are detected for ShowEmail(). Next is \G. This means no further groups are coming for <Column> so any groups left in the hash table should be removed which schedules <ShowCompany> to be deleted. Since the group contains 1 node, 1 node is removed from index 1 of the node produced for <Column>. We know it is at index 1 because the previous group’s node counts sum to 1.
The hash table is stored in a Pending object created by the Composer. Pending also tracks where the pending group's nodes are relative to other changes that have already been made. For example, Pending is updated to record that <ShowEmail>'s node will be at index 1 after the <ShowCompany> node is removed so that, if it needs to be removed as well, the Composer removes the node at index 1 again. These adjacent removes are coalesced into a single call to the Applier that would remove two nodes at index 1.
After the slot table is updated to reflect the false state above, it would look something like this,
| # | Key | Size | Nodes |
|---|---|---|---|
| 0 | <ShowPerson> | 7 | 1 |
| 1 | <Column> | 6 | 1 |
| 2 | Node | 5 | 3 |
| 3 | <ShowName> | 2 | 1 |
| 4 | Node | 1 | 0 |
| 5 | <ShowEmail> | 2 | 1 |
| 6 | Node | 1 | 0 |
If the value of person.employed becomes true again the original sequence is played to the composer,
<ShowPerson> <Column> N <ShowName> N/ /G <ShowCompany> N/ /G <ShowEmail> N/ /G /N /G /G
Just as in detecting deletes, the sequence is the same up to group #5. Here we encounter <ShowCompany> when we expect <ShowEmail>. As before we create a Pending object that contains the remaining groups which, in this case, is just <ShowEmail>. We consult Pending to see if <ShowCompany> is in this hash table. It isn't so this is an insert of new content. The composer switches to using a side table, an insert table which is a separate slot table, to hold the new content and ShowCompany proceeds to execute adding groups to the insert table. The main slot table is not used to store the new groups because the slot table is read-only during composition. After ShowCompany executes, the insert table table might look something like,
| # | Key | Size | Nodes |
|---|---|---|---|
| 0 | <ShowCompany> | 2 | 1 |
| 1 | Node | 1 | 0 |
And it would be scheduled to be inserted at group #5. It contains a node so this node is scheduled to be inserted at index 1 of the Column node.
Currently moves can only be generated by using a key composable. This adds an additional key object to the group generated for key. However, the runtime is more general and can handle non-key groups moving. As this is the case, to demonstrate how movement is detected we will simply use a different sequence for the order of the groups. Given the true slot table above, consider the runtime encountering following sequence,
<ShowPerson> <Column> N <ShowEmail> N/ /G <ShowCompany> N/ /G <ShowName> N/ /G /N /G /G
where order of the groups of the column are reversed. The sequence is the same until group #3. Just as before, a Pending object is created and the remaining groups are added. In this case <ShowName>, <ShowCompany> and <ShowEmail> are added. The pending object is consulted and <ShowEmail> is found and scheduled to be moved to group #3 (sliding the others down) and its node is scheduled to be moved to index 0 (moving ShowName to 1 and ShowCompany to 2). Next <ShowCompany> is in Pending so it is scheduled to be moved to group #5 (it is now would be at group #7 as it slid down) and its node is moved to index 1 from 2. Next <ShowName> is encountered. It has already slid down to index #7 and its nodes also have slid down to index 2 so nothing needs to be moved and no changes are scheduled. Just like deletes, adjacent moves are also coalesced so that nodes that move together result in a single call to the Applier to move the nodes.
Call location is the identity of composable content. This principle follows from positional memoization. The state generated by a call site is assumed to update the state that was generated at the same call-site in the same position.
Consider the following,
@Composable fun Counter() { var count by mutableStateOf(0) Row { Text("Count: $count") Button("+", onClick = { count++ }) Button("-", onClick = { count-- }) } }
This example uses count as an example state that is private and local to the composable function. This state might be animation state, focus, text selection, scroll position, etc. For all of these, the state is perceived as logically part of the content generated by the function, just as count is above.
Counter can might be used like,
@Composable fun Counters() { Counter() Counter() Counter() }
The code implies there are three independent counter states created, one for each Counter call in Counters. They each get their own instance of the count object; their own private state.
If the code was changed to,
@Composable fun Counters(showMiddle: Boolean) { Counter() if (showMiddle) { Counter() } Counter() }
toggling showMiddle from true to false must preserve the state of the last counter and remove only the middle counter. Toggling from false to true must insert a new counter in between the first and last counters. In other words, the identity of the counters is inferred from the call-site that created it. This implies, at minimum, the key for the group that contains the second counter must be different from the group that contains the third counter. If we were to rely entirely on the the group key generated for the by the startRestartGroup() call at the beginning Counter then the sequence the runtime would see for Counter with true would be,
<Counter> … /G <Counter> … /G <Counter> … /G
And if it was false,
<Counter> … /G <Counter> … /G
Following the algorithm above this would delete the last counter not the middle counter. If, on the other hand, a group was inserted around the if statement, the sequences would look like,
<Counter> … /G <if> <Counter> … /G /G <Counter> … /G <Counter> … /G <if> /G <Counter> … /G
which will correctly delete the state of the middle counter. It is the responsibility of the compiler plugin to generate the runtime calls necessary to ensure that groups generated by a call will be interpreted correctly, such as wrapping if statements in a group if necessary. Groups to resolve this ambiguity are called flow-control groups as they are inserted around language constructs that can change the flow of what code gets executed.
When a Pending object is created, the Pending object will return the groups with the same key in the same order that the group was generated in the old slot table. Consider the following code that uses Counter from before,
@Composable fun Counters(count: Int) { Row { repeat(count) { if (displayLabelFor(count)) { Text("Counter #$count: ") } Counter() } }
Assume this generates a sequence of the same key, repeatedly, with periodically inserted whenever displayLabelFor() returns true.
<Counter> … /G <Counter> … /G … <Text> … /G … /G … <Counter> … /G
If displayLabelFor changes from returning true for count % 5 == 0 to count % 3 == 0, a change will be encountered when the first <Text> group is emitted. It, and all subsequent groups, are added to the Pending object which will contain only two hash table entries, one for all the <Text> groups and one for all the <Counter> groups. As each <Counter> is encountered it will select the same <Counter> as was previously generated because they are selected in the same order as they appear in the old slot table. This preserves the identity of the content generated by all calls to Counter(). Using duplicate keys in order preserves the identity of all calls to Counter() regardless of what displayLabelFor() returns without requiring an explicit key for each loop iteration.