Compose defined, as part of the call ABI, that calls must generate a group to ensure the correctness of the application. These groups were informally called call groups. Initially (in early pre-alpha) all calls generated a group. Later this was changed to generate a group in the function itself instead of at the call site. To ensure correctness, control-flow groups were introduced to remove the need for the call site groups.
This document describes a semantics of Compose that preserves correctness without relying on call groups. This was enabled by control-flow groups but the implication of how this affects the need for all calls to have groups was not explored. This document proposes that Compose only keep function groups that are required for restarting.
This document was motivated by Leland Richardson's observation that, although most composable functions are restartable, the majority of groups added to the slot table are for composable functions that are not (e.g. remember, rememberSaveable and all the effects). This is because most composables use these primitives to create higher level concepts and the slot table is dominated by the groups for these primitives.
In How Compose Works composition is described in terms of a call tree. A call tree, in this context, is the fully expanded graph of the invocation of where each call has its own node in the tree. Consider, for example, the functions,
fun Root() { A(true) A(false) } fun A(value: Boolean) { remember { … } B() B() if (value) C() else D() } fun B() { … remember { … } … } fun C() { … remember { … } … } fun D() { … remember { … } … }
Calling Root will produce a call tree that looks something like,
where B is repeated because it is called twice and calling A twice creates two independent trees. The dotted lines and boxes represent the calls to remember made by each function and represent the slots tracked by the group.
If each function is assigned a unique value to use as a key (Compose uses a compiler generated integer), then the location in the tree can be uniquely identified by the concatenation of these keys if 1) a function is not called twice in the same function and 2) the function is not called in the same relative location conditionally. These two conditions were violated even by the simple code above as we call A twice in a row and call B twice in a row.
To allow for adjacent calls, originally (in pre-alpha) Compose added another key, the call site key, to disambiguate calls like this. Each call site was given another location that, taken together with the function key, disambiguated each group. The combined key of B, for example, would distinguish the first call from the second. This requires two keys per call instead of just one.
As described in How Compose Works, the call-site key was removed by adding control-flow groups. A control flow group introduces a group around code that contains a branch. That is, it marks when the flow of control might change. This results in the above tree changing to,
At first sight this doesn't appear to disambiguate calls to A and B. It is ensured, however, by the compiler ensuring that, absent a control flow group, the call will occur unconditionally. That is A will always be called twice in the order given and B will always, unconditionally, be called twice. If it could be called conditionally then it would have a control flow group. This means that the call is disambiguated by considering the order they are called. If the keys are combined with the index in which they are called in the parent group, the concatenated key is guaranteed to be unique for the location in the tree.
If A and B are always unconditionally executed, are the groups needed at all?
A group is needed, as described in How Compose Works, to ensure that positional memoization has the expected semantics. If A calls remember then each A in the graph above must return a unique value when it is recomposed but the same value for the same location in the graph for the lifetime of the composition. This is done by associating the slots needed by calls to remember to uniquely identifiable groups in the tree as described above. For each invocation of a function, the composer can find the previous state keys generated by the compiler to find the corresponding slots in the slot table.
However, the function groups are not needed for this, just unique addressing in the tree.
To see this, let's reorganize the tree along the lines of flow of control, instead of calls.
If the state of the above tree is laid out linearly it would look like,
As the calls to A and B are unconditional (otherwise they would have a flow-control group around them), the slots for A and B will always be adjacent to each other in a fixed order.
The only variation is the state for the If blocks that contain C and D. If the tree was re-organized to be,
which reorganizes the tree by when the slots will always be in the same order and only creates a separate node for when the order or number of slots can change (assuming, for example, that C and D could have a different number of slots) the nodes of this tree are equally uniquely addressable given the key+order assumptions introduced above.
Since the order of the calls is fixed, the call groups are no longer necessary to address the tree, only the control flow groups are necessary so the tree can be written as,
This tree requires the same number of slots, but has significantly fewer groups.
Composable functions do not need function groups to uniquely identify their state. However, they do need a group to be skipped and restarted. A group is used to mark the region of the slot table that contains the state of a restartable function and the region of the slot table that can be skipped if the function is skipped. This means that not all function groups can be removed, only groups for non-restartable functions. As noted above, however, even though this is a minority of the total of composable functions written, the number of non-restartable functions called is quite high as functions like remember are called by nearly every restartable function.
The current slot table implementation requires that once a child group is created, no more slots can be added to the group. This means that any function that adds slots to the slot table requires a group around it as it can be called after a group has already been added by another function called before it.
If we lift the restriction that would allow slots to be added after child groups then remember would not need its own group as remember it could just add slots to the caller's group.
To allow removing groups around non-skipable functions, the slot table needs to be changed to allow adding slots to a group that already has child groups.
Adding this to the existing slot table impacts both the SlotReader and SlotWriter. The SlotReader will now need to track where the parent left off reading the slots when a child group is entered and restore that when the child group is closed. This is not necessary today as the slots are never read after a child is entered. The SlotWriter would need to handle the case where slots are added after a child group is entered which it currently ignores. Both of these changes are relatively simple but the SlotReader might slow down recomposition as it must now do more work.
Marking a composable as read-only allowed the compiler to remove the group as the composable was guaranteed to not add a group. With this change if the function is not restartable and doesn't call remember it will generate the same code as read only composable meaning that read-only composable is effectively an alias for non-restartable.
Source information used by the inspector is stored in the group for the function. This took advantage of the fact that all functions introduced groups. To support read-only functions, a start/end source marker was added that would conditionally add a group if source information is collected. This can be reused for non-restartable functions.
The source information is currently needed to find the call that generated a layout node. As Box, Column, and Row are such calls as they are non-restarable (as they are inline functions) source information is required for these functions. This implies that it is inferred when a function generates a layout node, which is hard, or mark such functions with an annotation or always generates source markers for non-restartable functions, which are both simple.
The layout inspector and animation inspector both rely on the slot tree which, by naming convention, exposes the call tree based model of navigation. The naming convention might need to change here to reflect that a group doesn't necessarily map to a call which was true already as we already had control flow groups that are not call groups.
Tracing is independent of the start and end groups and are unaffected by this proposal.
Composite keys are used to uniquely identify state information that is preserved across restarting the activity or process. As these keys are a proxy for concatenating the keys as described above (they are hashed together instead of concatenated) they will still be as unique as they were previously.