Design Thoughts: Undo Redo
Text editors require undo/redo support. The undo/redo behavior lets the user reverse one or more recent operations, and also lets the user redo one or more recent undo's. This behavior can be viewed as moving backward and forward through a ledger that holds the user's editing history.
It's worth noting the variety of information that might be captured in editing history. Obviously, changes to text are part of that history. Such changes include insertions, deletions, and style changes.
Related to text changes are selection changes. Users expect that when text changes are reversed, the caret is moved back to its previous position, too. Moreover, from a correctness standpoint, if the caret wasn't moved during undo operations, then the caret could end up in a non-existent location, which would be an error condition. Therefore, the caret/selection must also be tracked by the undo/redo system.
Super Editor isn't a plain-text editor, it's a rich text editor. Super Editor ships with support for images, videos, and horizontal rules. Super Editor can also be extended to support arbitrary content, such as tables and code editors. These media types might have any number of editable details. Images, videos, and horizontal rules probably only support insertion and deletion. But a table essentially includes a mini-document within every cell, and also includes the ability to add, remove, re-size, and re-arrange rows and columns. An embedded code editor includes its own entire editing system. There's an unbounded variety of both data models and data changes that are associated with possible Super Editor content.
Whatever approach Super Editor chooses for undo/redo, it needs to work equally well for content added by 3rd parties as it does for content changes that ship with Super Editor. The approach can't depend upon a bounded set of possible edit operations.
There seem to be two common approaches to implementing undo/redo. Both options are based on tracking a series of objects, but the thing that is tracked differs between the two. One option is to track the "commands" that alter the document state. The other option is to track the "state changes" that occur within the document state over time.
Commands are Dart objects that implement a change. For example, there might be an InsertTextCommand, which knows how to insert text into the document:
// Pseudo-code:
class InsertTextCommand implements Command {
InsertTextCommand(this.text, this.insertPosition);
final String text;
final DocumentPosition insertPosition;
void execute(...) {
document.getNodeAt(insertPosition).insertText(text);
}
}
Commands exist in the Super Editor implementation no matter which undo/redo approach is chosen. However, one of the approached to undo/redo would collect all executed commands in a stack.
class Editor {
final _history = <Command>[];
void execute(Command command) {
command.execute(...);
_history.add(command);
}
}
If we add an undo behavior to Command, we can use the stack of Commands to undo/redo changes.
class Editor {
final _history = <Command>[];
void undo() {
final lastCommand = _history.removeLast();
lastCommand.undo(...);
_future.add(lastCommand);
}
void redo() {
final futureCommand = _future.removeLast();
futureCommand.execute(...);
_history.add(futureCommand);
}
}
class InsertTextCommand implements Command {
InsertTextCommand(this.text, this.insertPosition);
final String text;
final DocumentPosition insertPosition;
void execute(...) {...}
void undo(...) {
document.getNodeAt(insertPosition).deleteTextAt(insertPosition, text.length);
}
}
A variation on tracking commands is tracking deltas. A delta is a data structure that captures exactly what changed. For example, the following is a delta that captures a text insertion:
{
"type": "text.insertion",
"nodeId": "12346",
"offset": 25,
"text": "insert me",
}
At first blush, storing deltas might seem more like "Tracking State Changes" than "Tracking Commands". However, some piece of code needs to be able to apply the delta. Applying the text insertion delta requires that a piece of code understand what a "text.insertion" is, where to find the associated TextNode, and how to insert the given text into that node. That piece of code is a Command, and so we're pretty much right back where we started when we tracked commands. Tracking deltas merely adds another data structure to the equation.
The alternative to tracking commands is to track the literal changes that are caused by a command. Some implementations choose to remember the entire application state after every change, while other implementations choose to only remember the specific properties that were changed by a given command.
The benefit of remembering the entire application state after every change is that it's trivial to move to an earlier state - the current state can be thrown away and replaced by an earlier state. However, this also means that an application retains significantly more state data than is truly needed to run the app.
The benefit of remembering only the properties that are changed by a command is that the application uses the minimum memory necessary to remember the change history. The downside is that the application needs a general means for storing and applying random combinations of properties.
Super Editor renders an editor by way of a Document and a DocumentComposer. The Document contains the information, such as ParagraphNodes, ImageNodes, etc. The DocumentComposer contains the user's selection, as well as the insertion mode (e.g., bold is currently activated). We call these objects, and any other object that might be altered during editing, an Editable. The Editor collects all the Editables and makes them available to the commands that execute the changes.
To remember all editor state, every Editable would need to be able to snapshot itself.
abstract interface class Editable {
EditableSnapshot createSnapshot();
}
abstract interface class EditableSnapshot {
// Marker interface.
}
The EditableSnapshot might be any kind of object. Every Editable would choose its own internal representation. Some might use a Map, others a List, others comma-separated values.
Of course, Editables would also need to be able to restore a given snapshot:
abstract interface class Editable {
EditableSnapshot createSnapshot();
void restoreSnapshot(EditableSnapshot snapshot);
}
When remembering every iteration of the global editor state, the Editor needs to create snapshots for every Editable after every change:
class Editor {
final Set<Editable> _editables;
final List<Map<String, EditableSnapshot> _history;
void execute(Command command) {
command.execute(...);
final snapshot = <String, EditableSnapshot>{};
for (final editable in _editables) {
snapshot[editable.id] = editable.createSnapshot();
}
_history.add(snapshot);
}
}
With a history of global snapshots, we can implement undo/redo:
class Editor {
final Set<Editable> _editables;
final List<Map<String, EditableSnapshot> _history;
final List<Map<String, EditableSnapshot> _future;
void undo() {
final mostRecentSnapshot = _history.removeLast();
for (final editable in _editables.values) {
editable.restoreSnapshot(mostRecentSnapshot);
// Note: During the executing of this loop, editables will be
// in inconsistent states until all restorations are complete.
// Make sure no integrity checks happen during this loop.
}
_future.add(mostRecentSnapshot);
}
void redo() {
final nextSnapshot = _future.removeLast();
for (final editable in _editables.values) {
editable.restoreSnapshot(nextSnapshot);
}
_history.add(nextSnapshot);
}
}
Remember individual property values is easier in some implementations than others. For example, an app that already utilizes a Redux store for global application state already has a mechanism for reading and writing individual global properties. In fact, an app that uses Redux already has access to 3rd party packages that add the ability to record groups of property values.
The downside of something like Redux is that it forces your entire application into a shared data model, which has any number of consequences over time. Everything is a tradeoff, and by simplifying all application state to a glorified global map, all the behavior around that global map becomes more complicated as it tries to co-exist around a shared resource.
Super Editor isn't an application - it's a toolkit to help developers build a specific piece of an application. Therefore, Super Editor can't depend upon any particular approach to overall application structure, i.e., Super Editor can't impose Redux on applications.
Super Editor could, theoretically, use something like a Redux store within itself, which would still allow the editor to use a Redux approach to remember individual saved properties. Again, a Redux store is a glorified map. When all state is held within a map, remembering individual property values is as easy as remembering a path and a value, e.g., "document.nodes['12345'].text" -> "Some text value". However, presently, Super Editor doesn't use a global data structure for all editor state. Instead, Super Editor groups together a set of Editables, which includes the Document and the DocumentComposer. This set of Editables can also be extended by 3rd parties to add other types of things that might be edited within the Editor. Given that there is no singular store for all Editor data, the Redux approach won't work.
To achieve a history of surgical state changes in Super Editor, the full snapshot approach can be adjusted from above, such that each snapshot includes a partial snapshot instead of a full snapshot. As a result, all snapshots need to be plaid back from the beginning on every undo.
class Editor {
final Set<Editable> _editables;
Map<String, EditableSnapshot> _initialSnapshot;
final List<Map<String, EditableSnapshot> _history;
final List<Map<String, EditableSnapshot> _future;
void undo() {
final mostRecentSnapshot = _history.removeLast();
_future.add(mostRecentSnapshot);
// Restore the initial editor state, which includes all data.
for (final editable in _editables.values) {
editable.restoreSnapshot(_initialSnapshot[editable.id]);
}
// Apply every snapshot as a partial change.
for (final snapshot in _history) {
for (final editable in _editables.values) {
editable.applyPartialSnapshot(snapshot[editable.id]);
}
}
}
void redo() {
final nextSnapshot = _future.removeLast();
_history.add(nextSnapshot);
// In the case of redo, we only need to apply the latest
// partial snapshot, because our app state is already up
// to date.
for (final editable in _editables.values) {
editable.applyPartialSnapshot(nextSnapshot);
}
}
}
The Editor code for surgical updates doesn't look a whole lot different from the pseudo code that stored the whole editor state on every change. You might wonder where the extra work is happening? Primarily, the difference is within each Editable. Each Editable, such as the Document, needs to know how to restore a full snapshot, and also how to restore a partial snapshot. Each Editable is responsible for structuring full and partial data in a way that's useful to it. A Document, for example, might serialize itself to JSON. That JSON could be used to represent the whole document, as well as a partial change to the document.
After some investigation into partial snapshots, they're trickier than they initially appeared. While the addition and modification of existing data is straight forward, the approach to handling data removal isn't clear.
Take the document as an example. How does a partial snapshot encode the deletion of a node, or a node moving from one position in the node list to another?
One approach to removal is to encode the act of removal. For example, a snapshot might explicitly declare "Node abc123 was deleted", or "Node abc123 was moved to index 5". But these aren't really snapshots, they're deltas. Code needs to know how to achieve those goals, rather than blindly applying new data over old data.
A possible way to handle non-additive changes in a document is to always encode the node order in every partial snapshot, and then explicitly pass null as the value for removed nodes:
{
"order": [
"c",
"a",
"d",
"b"
],
"nodes": {
"a": {
"id": "a",
"type": "text",
"data": {
"text": "Hello, world! I'm updated!",
"attributions": [
{
type: "link",
start: 7,
end: 11,
data: {
"url": "https://google.com"
}
}
]
}
},
"e": null,
"f": null
}
}
It's worth noting, to be able to restore an initial snapshot, or even apply a snapshot that includes the addition of a node, the MutableDocument needs to know about every possible node type that might exist in a document. At best, the MutableDocument needs to know which class is associated with the given node data:
Map<String, dynamic> nodeData;
if (nodeData["type"] == "image") {
return ImageNode.fromSnapshot(nodeData);
}
Creation of nodes could be generalized with a Chain of Responsibility:
Map<String, dynamic> nodeData;
for (final nodeFactory in nodeFactories) {
final node = nodeFactory(nodeData);
if (node != null) {
return null;
}
}
The above discussion shows how partial document updates might be accomplished. But that discussion assumes full replacement of document nodes. It's likely that we'd want partial node updates, too, because a single paragraph node can be quite large in some use-cases, so copying that whole paragraph after every change could result in significant memory usage over time.
Recording partial node updates essentially means encoding deltas:
{
id: "a",
type: "text",
data: {
type: "insert",
text: {
text: "Hello, world!",
attributions: []
}
}
}
At this point, we've arrived at a delta implementation, rather than a snapshot implementation. It's unclear if there's truly a partial snapshot approach that doesn't reduce to deltas. The tradeoff with deltas is that with deltas, every editable object essentially includes command behavior internally. If deltas are used, is there still a meaningful role for Commands?
The undo/redo system needs to work with transactions, batches, and reactions.
A transaction is a group of interdependent changes that must happen together. Either all of them happen, or none of them happen. For example, a text insertion needs to alter the document's text AND move the caret to a new position. If the text changes without moving the caret, it's a bug. If the caret moves without changing the text, it's a bug.
A batch is similar to a transaction, in that a group of changes are made together, but a batch is allowed to be broken apart, or re-grouped as desired. For example, imagine that the user types a bunch of words very quickly. The user expects to be able to undo the insertion of all of those words, rather than undo'ing every character. This is achieved by inspecting the change history, noticing a series of individual character insertions, and then grouping all those character insertions into a batch, which can then be undone.
A reaction is an arbitrary piece of code that runs in response to an editor change, which might then create another editor change. For example, a reaction might inspect the altered text, look for misspelled words, and then apply an underline style to the misspelled words.
Whatever the undo/redo implementation, it needs to ensure that each of the above behaviors work as expected.
There are two open questions around reactions:
- How should reactions be batched with regard to their originating change? Reactions should probably be batched separately, so that the user can always undo a reaction. Although that's not entirely clear, either, because a reaction that underlines a misspelled word shouldn't be undo-able. Perhaps it's a per-reaction choice.
- Should reactions be run after a redo, or only during new command executions, or does each reaction need to decide for itself?