compose/runtime/design/how-compose-works.md

# How Composition Works

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.

## Purpose of the Composer

The composer has three jobs,
1. Record positional information for the composition (positional memoization)
    - It records the results of calling the lambda function passed to `remember`
    - It records the value of the parameters passed to skippable composable functions.
2. Detect changes to composition
3. Incrementally evaluate the composition as the data used to produce the composition changes

## Positional Memoization

Memoization 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,

##### Example: A and B with no parameters
```kt
@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.

## The Slot Table

*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 | <none> |   0   |   3   |   -1   |   0   |
| 4567 | <none> |   0   |   1   |    0   |   0   |
| 4567 | <none> |   0   |   1   |    0   |   1   |

| Slots             |
|-------------------|
| <Data instance 0> |
| <Data instance 1> |

- Even though the groups records have 6 fields they are stored in 5 integers by packing Flags and Nodes together into a single integer.
- The parent and size information are redundant. That is, parent can be calculated from size and size can be calculated from the parent but they are both stored to allow efficient traversal of the slot table from any node upwards and efficient pre-order enumeration of the tree.
- There are no child pointers. A group is a child of its parent implicitly by its location in the array. The 4567 entries are both children of 1234 because 1234 is size 3 which includes both of them.
- The number of slots assigned to a given group is the difference between its slot index and the next entry in the table. For the last group, the next index is assumed to be the size of the table. That is, `1234` has `0` slots because `0 - 0 ` is `0` both `4567` entries have one because `1 - 0 = 1` and `2 - 1 = 1`, respectively.
- The `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.
- When writing to the `SlotTable` the arrays of the slot table are a [gap buffer](https://en.wikipedia.org/wiki/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.
- The number of slots associated with a group, once created, can not change when updating the slot table. That is, slots cannot be inserted, deleted or moved, only groups can. The value in the slot can only be updated. If slots are conditional then they must be in a group that is conditional.
- When inserting a group, once a child group has been inserted, no further slots can be added to the parent group. If slots need to be added (because a call to `remember` after a call to a composable function, for example) then the slots require their own group.

## Compiler Plugin
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.

### Positional Memoization
The above code is rewritten by the plugin (ignoring skipping and restarting, for now) to look something like,

##### Example: Positional Memoization runtime calls
```kt
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

### Skipping
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.

##### Example: Position Memoization and Skipping of parameterless functions
```kt
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.

##### Example: A and B with parameters
```kt
@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,

##### Example: A and B with skipping code that checks the parameter values.
```kt
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.
- As the number slots cannot change for the group, the number of times `changed` is called cannot be conditional, therefore a non-short-circuiting `||` pattern needs to be used.

### Restarting
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,

##### Example: A and B with parameters, positional memoization, skipping and restarting calls.
```kt
@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.

### `$changed`
The 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.

## Detecting Structural Changes
A structural change is detected when the groups emitted by one or more composable functions change.

### Detecting Deletes
Consider the following function,

##### Example: ShowPerson
```kt
@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.

### Detecting Inserts
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.

### Detecting Moves
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.

### Content Identity
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,

##### Example: Counter
```kt
@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,

##### Example: Simple Counters
```kt
@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,

##### Example: Counters with parameter
```kt
@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.

### Duplicate keys
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,

##### Example: Repeated Counters
```kt
@Composable
fun Counters(count: Int) {
  Row {
    repeat(count) {
      if (displayLabelFor(count)) {
         Text("Counter #$count: ")
      }
      Counter()
    }
}
```

Assume this generates a sequence of the same key, <Counter> repeatedly, with <Text> 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.