Spring 2022 Compose Hackathon

Compose Hackathon: Day 1

Zach Klippenstein

May 2, 2022 — 7 min read

Introduction

This week the Jetpack Compose team is doing a hackweek. I am using it as an excuse to try building something I've been thinking about basically since I joined the team. I'm not sure if it will work, or if it will be fast enough to do what it needs to do, but I'm excited about the possibilities it opens up if it turns out. To document my plan and my findings, I'll use this blog series as a journal, hopefully posting once a day but we'll see how things go. Since I want to focus on the actual work, please excuse the lack of editing and polish.

Motivation

Compose’s text editing APIs currently have the following shape for communicating the text being edited and changes to that text:

TextField(text: String, onTextChanged: (String) -> Unit)

However, internally, there are many sophisticated operations that need to be performed on the current text to make changes. Unlike simple hardware keyboards, software keyboards like Android’s IME are aware of the contents of the text fields and can perform operations on more than one character at a time - eg when accepting an auto-correct suggestion. These commands can be delivered in batches, and so internally compose turns the text value into a mutable buffer that is more efficient to apply operations to. When a batch of IME commands comes in, it applies them all to the internal buffer at once, then converts that buffer to a string to pass back to the callback.

It keeps this buffer around between compositions to optimize for the case where the callback immediately accepts the text and provides the exact new text back in the next composition. Then, on every composition, it has to make sure the received text matches what it thinks it should be, otherwise it has to reset its internal state to match.

The reason this simple API was chosen is because:

it is simple to teach, understand, and work with,
while still allowing state hoisting and
immutable values,
it doesn’t introduce any new types, and
it matches many other APIs in compose.

However, if a developer wants to talk directly to the low-level IME API, they have to create their own buffer type. Kotlin doesn’t provide any efficient text editing buffers, which need to support efficient sequential inserts and deletes in the middle of the string. And even if a developer simply wants to observe text changes, or perform their own transformations, there’s no way, for example, to actually determine what text was inserted/deleted without comparing the before/after strings, which is ridiculous because the internal code already knows this so it shouldn’t be necessary to recompute it. It’s become apparent that this simple “value+change callback” pattern is almost too simple.

While there has been a big paradigm shift in the android world over the last ~5 years to preferring immutable data, for many good reasons, I think a solution to these problems might be to embrace mutability. Compose’s snapshot state system provides tools that address many of the reasons why we’ve all become afraid of mutability, and I think if we lean into that it might produce APIs that are still easy to use, provide decoupled API boundaries, and might even have better performance.

The project

What if, instead of passing a value+change callback around, we just passed a mutable text buffer? This buffer would be defined as an interface that supports a minimal set of mutation and read operations. We would provide a performant default implementation, similar to how Kotlin provides an ArrayList as the underlying data structure when you ask for a mutableListOf. But developers could create their own wrappers if they want to have more control.

This isn’t currently very practical because Compose uses a private gap buffer for its text editing. This is an efficient data structure for such a use case, but it requires careful handling because it doesn’t participate in Compose’s state snapshots. It’s basically an ArrayList for text editing: you wouldn’t use an ArrayList in regular Compose code, you’d use a snapshot-aware implementation like the one created by mutableStateListOf. So if we want to make a mutable text buffer part of our public API, we need to make a buffer that knows about snapshot state so it’s safe to use in regular compose code. See Goals below for an enumeration of the advantages of a snapshot-aware buffer.

As mentioned above, Compose currently uses a gap buffer. But there are two other well-known data structures that are used for this purpose: the rope and the piece table. When the Compose team was writing the first text field code, one of my team members wrote a nice brief introduction and evaluation of all three, which is unfortunately an internal document so I can't share it, but there is a lot of public literature about them (see the Related Reading section at the bottom of this post). But of all three, I think the piece table is the most well-suited to adapting to be aware of snapshots. And if we can do that, then we can start passing around mutable buffers in text editing and IME APIs, reusing the intuitions that Compose developers have built up around how state in Compose is managed and how changes are communicated.

Goals

Build a piece table that is unit tested and supports basic editing and read operations.
- We can probably make it implement standard, platform-agnostic interfaces like CharSequence for reads and Appendable/StringBuilder for writes.
Write or adapt benchmarks to compare this implementation to the current gap buffer, as well as to allow profiling and optimizing our implementation.
Adapt the piece table to have the following snapshot-related features (these should sound familiar as most of them are how other snapshot state classes work):
- Mutations to a buffer should not be visible outside the current snapshot until the snapshot is committed.
- Mutations to a buffer should be discarded if the snapshot is discarded before committing.
- Snapshot observers that read a buffer should be notified when the buffer is changed (that is, when the snapshot that changes it is committed).
- Multiple threads should be able to mutate the same buffer independently in their own snapshots without explicit synchronization other than snapshots.
- A sequence of mutations performed in the same snapshot should not have very much overhead.

Stretch Goals

If time permits:

Optimize the snapshot-aware piece table’s performance as much as possible using the benchmarks.
Explore how to use this data structure to build something like AnnotatedString.Builder for editing text that has spans associated with it.
Explore how to implement undo/redo operations using the piece table.

Non-goals

Since this hackathon is only a week long, I want to use it to prove that we can build such a data structure and keep the scope narrow. If it looks promising, future work can be prioritized and performed outside of the hackathon (we already have bugs filed for many of those tasks).

Change text field or IME APIs or implementation to use this data structure in production code.
Productionize the piece table itself in any way.

The data structure

Since this post is already getting a bit long I'm not going to explain piece tables in depth (see the Related Reading section at the bottom of this post for some excellent explainers), but just as a quick refresher, a piece table consists of:

Two text values:
an immutable one that holds the initial value of the text when the table was created, and
an append-only one that stores all new text inserted or added into the buffer.
A table of (source, index, length) tuples that describe which substrings to take from each of the two text values in (1) in order to construct the current buffer value.

To make this data structure snapshot aware, we need to make both parts of the data structure snapshot aware. One of the nice things about the snapshot state system is that any data structure composed of snapshot-safe parts is itself snapshot-safe. The second part should be relatively straightforward: we just need to store the table in a SnapshotStateList. The first part might be more challenging. How do we make an array snapshot-friendly? The entire array needs to be efficiently accessible by index, so we can’t just store a SnapshotStateList of each newly-appended string. We also want to make sure that a sequence of operations performed in the same snapshot can be performed without much overhead, neither computational nor space.

Here’s how I see this working. I don’t know if it will actually work, so the plan might change as I actually build it. We can break the single array into a list of fixed-length blocks, similar to Okio’s Segments. Every block except the last one will be full. Then we can use a SnapshotStateList to hold the blocks. This lets us copy the whole array efficiently because the underlying implementation of SnapshotStateList is a persistent data structure so most blocks can be shared between copies. To make a copy for mutation, we only need to copy the actual contents of the last block, which will only be partially filled, since that’s the only block that will actually be mutated (it’s append-only). We’ll also store some metadata that lets us determine if any snapshots other than the current one have access to the current list of blocks.

When performing a write operation, we’ll check if any other snapshots can see our last block:

If not, then the current snapshot has exclusive access to the block so we can just write directly into the block’s array. The size of the contents of the last block must also be stored in a snapshot state object so that if the snapshot is discarded after a mutation, the new size is also discarded (note that the discarded data will still exist in the block, but it will be overwritten on the next mutation).
However, if another snapshot can see the last block, we can't write to it because another snapshot may also write into it, so we need to copy the last block’s contents into a new array and replace the last element in the list of blocks. Since the block list is a SnapshotStateList, we can just use an indexed replace operation for the last block to do this efficiently. Then once we have our own dedicated block, subsequent mutations will hit the first case above and just write directly into the array. If the snapshot is discarded, the copy we just made of the block will be discarded and eventually garbage-collected.

The only part of this design that I’m not confident about is being able to determine if the current snapshot has exclusive access to the last block. I need to go refresh myself on the particulars of MVCC, but I think it might be possible by storing the ID of the snapshot that created the block and comparing it to the current snapshot ID. This might require dropping down into the low-level APIs for actually creating and managing snapshot state records, which both scares me and makes me excited for a new learning exercise.

Because the size of the last block is snapshot-aware, multiple reading snapshots can actually share access to it. We only need to ensure that a single snapshot has write access – the readers wouldn't see the size change until the mutating snapshot is committed. I'm not sure if it's possible to make that distinction.