Adding undo/redo support for SuperEditor and SuperTextField

[matthew-carroll]

Users expect to be able to undo and redo document and text changes. Super Editor doesn't currently support undo/redo functionality. This document introduces concepts and ideas that are relevant for implementing these abilities.

Undo/redo requires a ledger

The ability to undo/redo changes requires some sort of ledger - a log of each change that was made.

The act of undoing a change means reconfiguring the state of the system to the previous location in the ledger. Redoing a change means reconfiguring the state of the system to the next location in the ledger.

A structural approach known as "event sourcing" is designed to provide a ledger such that the state of the system can move forward and backward across that ledger. The primary impetus for event sourcing is the ability to audit what has happened in a system, such as for financial compliance, but the same concepts should solve the undo/redo problem.

Redux is an example of an event sourcing implementation.

If we can implement an adequate ledger, ie, implement a working event sourced implementation, then undo/redo functionality will be achieved automatically.

Commands, Events, Snapshots, and Reversibility

Storing events is not enough to build a useful ledger. The hard part is deciding how to reconstruct system states at other points in the ledger.

State reconstruction has two major options: reconstruct state by replaying all events up to that point, or reconstruct state by reversing every event that appears after the desired point in time.

Replaying Events

Reconstructing state by starting from zero and replaying all events is the easiest option because it doesn't require additional behavior to figure out how to reverse an event. However, replaying all events requires a lot more processing power than reversing a small number of events. A mitigation strategy for the extra processing is available: take snapshots every so often so that you never have to return all the way to the beginning of the ledger. You can return to the nearest snapshot, like returning to your last checkpoint in a video game. Nonetheless, this approach involves replaying more events on average than would reversing events.

Reversing Events

For a text editor, reversing events is a much more natural behavior, and requires far less processing than the replay approach. However, reversing events requires twice as many event implementations. Every event needs to know how to apply itself forward and backwards. Sometimes going backwards is a lot more complicated than going forwards. Think about how you might implement the deletion of all document content and then reverse that.

Super Editor Approach

Despite the added complexity of reversible events, Super Editor will attempt that approach first, because event reversal is the literal action that the user is interested in taking. As a result, any future tradeoffs that this approach makes will likely be in-line with user expectations.

Commands vs Events

Commands and events are easily confused.

An event is something that has already happened. It's past tense.

A command is responsible for validating the current state of the system to ensure that the desired event is appropriate to apply. Consider the following events:

1. Created Paragraph1
2. Inserted "abcdefghi" into Paragraph1 at position zero
3. Deleted all characters in Paragraph1
4. Deleted character "a" at position zero in Paragraph1

The final event is inappropriate. Paragraph1 was empty after event 3, so event 4 could not possibly have deleted character "a" at position zero. In this particular example, if the code is smart enough, this event could be ignored without issue. However, event 4 is technically a corruption of the ledger. The event could not possibly have happened, and it's dangerous for the reconstruction system to assume that an event can be skipped without issue.

To avoid illegal events from appearing in the ledger, a command is responsible for validating the state of the system before adding the event to the ledger. That command should have recognized that Paragraph1 was empty and that there was no character "a" to remove at the given location. Then that command should have executed some kind of error behavior.

How do we playback events?

Storing events is simple. Creating commands that validate the system before savings events is simple. But how do we actually apply these events to accomplish the document editing that we're interested in?

Applying a single change

One option is to provide an object that knows how to apply every possible primitive change to the content in question. This approach might work for SuperTextField where the content is simple, e.g., attributed text + selection, and that content is unlikely to expand in the future. However, for SuperEditor, the concept of a document is already complicated, and package users are likely to extend the types of content within a document in an unbounded manner. Therefore, this option is unlikely to work well for super_editor.

Another option is to group functions with every event. Each event would know how to serialize itself, deserialize itself, apply changes to the content in question, and undo changes to the content in question. The limiting factor in this case is that all events would implement the same interface, requiring that the editable content be specified and restricted.

class Event {
  void apply(MutableDocument doc, DocumentSelection selection) {
    // TODO: change the document
  }

  void undo(MutableDocument doc, DocumentSelection selection) {
    // TODO: undo the change
  }
}

In the case of SuperTextField this is probably fine because it's unlikely that SuperTextField will need more than attributed text + selection. The restriction is less clear for SuperEditor. Presently, the content for SuperEditor is a document + document selection. This is sufficient for current requirements, but would it be too restrictive for future use-cases? A document with multiple selections could not be supported with this approach because that use-case would require multiple selections, or at least a different representation of document selection.

A mitigation for content constraints would be the introduction of generics as the content type. Each event would receive content based on a generic:

class Event<T> {
  void apply(T content) {/***/}
  void undo(T context) {/***/}
}

The object passed to apply() could be a data structure with various relevant artifacts:

class DocumentEditContext {
  final MutableDocument document;
  final DocumentSelection selection;
}

A concrete event would then define itself as follows:

class Event<DocumentEditContext> {
  void apply(DocumentEditContext editContext) {
    // TODO: alter the document
  }

  void undo(DocumentEditContext editContext) {
    // TODO: reverse the operation
  }
}

Accumulating changes

The DocumentEditor class can function as the entrypoint for the event-sourced editing of a document. Consider the following API:

abstract class DocumentEditor<T> {
  void apply(Event<T> event);

  bool get hasUndoableEvent;

  int get undoableCount;

  void undo();

  bool get hasRedoableEvent;

  int get redoableCount;

  void redo();

  List<dynamic> toJson();

  void clearAndLoadFromJson(List<dynamic> evensJson);
}

The DocumentEditor maintains a MutableDocument, which represents the current configuration of the document being edited. DocumentEditor also maintains the DocumentEditContext to pass to each Event, as well as the ledger of all Events that have been executed. This allows the DocumentEditor to perform "undo" and "redo" operations.

Merging related events

Each character that the user types in a document produces a corresponding edit event. Remembering every character entered could create a memory pressure issue. Moreover, the user probably doesn't want to undo changes one character at a time.

The addition of multiple characters should be combined into a single event, as should the deletion of multiple characters, but only if those changes occur in quick succession. If the user types some characters, then pauses for a while, and then types more characters, that user probably expects the undo operation to only revert the changes made after the pause.

While this particular time-based grouping of events is a good default, there could be any number of situations where package users want to add or alter the grouping rules. Therefore, the ability to alter the history of document edits must be exposed publicly, rather than hidden within DocumentEditor.

A possible approach is to introduce a Ledger, which is passed to every Event:

class Ledger<T> {
  Event<T> getEventAt(int indexFromPresent);

  void addEvent(Event<T> event);

  Event<T> get mostRecentEvent;

  void removeMostRecentEvent();

  void replaceEventAt(int indexFromPresent, Event<T> newEvent);

  void replaceEvents(int startIndexFromPresent, int endIndexFromPresent, List<Event<T>> newEvents);
}

class Event<T> {
  void apply(Ledger<T> ledger, T context);

  void undo(Ledger<T> ledger, T context);
}

However, this approach has a problem with determining the source of truth. If an Event is added to the ledger by a command, then an Event becomes responsible for removing itself from the ledger before rewriting any history. This creates an order-of-operations requirement that will be difficult to document and enforce. Instead, the responsibility of doing surgery on the event history can be left to the commands. A command can blindly add an Event, or it can rework the history of Events in the Ledger.

If commands are used to rework Event history then it may or may not be sufficient to expose the relevant methods from DocumentEditor, rather than create a Ledger API. This distinction depends upon what the natural axis of change appears to be.

Sanity check

Based on the aforementioned approach, what might a few fundamental commands and events look like?

First, let's consider the implementation of an event that inserts text within a TextNode:

/// Inserts the given [text] in the [DocumentNode] that corresponds to the given [nodeId], placing
/// the first character of [text] at the given [insertionOffset].
///
/// This event can be used to insert individual characters as well as longer `String`s.
class InsertTextEvent implements Event<DocumentEditContext> {
  final String nodeId;
  final int insertionOffset;
  final AttributedText text;

  void apply(DocumentEditContext context) {
    final doc = context.document;
    final node = doc.getNodeById(nodeId);
    if (node == null) {
      throw MissingNodeException('...');
    }
    if (node is! TextNode) {
      throw InvalidNodeException('...');
    }

    node.text = _insertTextAt(
      sourceText: node.text,
      insertionOffset: insertionOffset,
      textToInsert: text,
    );
  }

  void undo(DocumentEditContext context) {
    final doc = context.document;
    final node = doc.getNodeById(nodeId);
    if (node == null) {
      throw MissingNodeException('...');
    }
    if (node is! TextNode) {
      throw InvalidNodeException('...');
    }
    if (node.text.text.length < (insertionOffset + text.text.length)) {
      throw IllegalStateException('...');
    }

    node.text = _removeText(
       sourceText: node.text,
       removalStartIndex: insertionOffset,
       lengthToRemove: text.text.length,
    );
  }
}

InsertTextEvent handles the content changes for adding text to a TextNode, but it doesn't update the DocumentSelection. We need a new Event for that:

class ChangeDocumentSelectionEvent implements Event<DocumentEditContext> {
  final DocumentSelection newSelection;
  final DocumentSelection previousSelection;

  void apply(DocumentEditContext context) {
    context.composer.selection = newSelection;
  }

  void undo(DocumentEditContext context) {
    context.composer.selection = previousSelection;
  }
}

InsertTextEvent and ChangeDocumentSelectionEvent, when taken together, can implement a number of single-node text operations. However, they're not really independent. If we undo one event, we need to undo the other. This is a common issue that will repeat with many other scenarios. Therefore, we should introduce an Event specifically to batch other Events and apply() and undo() those events in one shot:

class Transaction<T> implements Event<T> {
  final List<Event<T>> batchEvents;

  void apply(T context) {
    for (final event in batchEvents) {
      event.apply(context);
    }
  }

  void undo(T context) {
    for (final event in batchEvents.reverse()) {
      event.undo(context);
    }
  }
}

Now we should be able to construct a command that orchestrates a real editor goal. Unlike Events, a command is just a concept, not a class. Therefore, the following code is what a command might execute, regardless of where it's implemented.

// assume we want to add a new character called newCharacter
// assume that the command has already ensured that the document selection is in a TextNode
// assume that the current document selection is available in docSelection
// assume that the current text position is available in textPosition

docEditor.apply(
  Transaction<DocumentEditContext>(events: [
    InsertTextEvent(
      nodeId: docSelection.extent.nodeId,
      insertionOffset: textPosition.offset,
      text: newCharacter,
    ),
    ChangeDocumentSelectionEvent(
      newSelection: DocumentSelection.collapsed(
        DocumentPosition(
          nodeId: docSelection.extent.nodeId,
          nodePosition: TextPosition(offset: textPosition.offset + 1),
        ),
      ),
      previousSelection: docSelection,
    ),
  ]),
);

This text insertion command is the simplest such command that could exist. It doesn't inspect a change in time, nor does it inspect the semantic meaning of the character added. Nonetheless, this command inserts the new character and moves the caret one character forward, all within a Transaction that can be undone.

TODO: write an example that reworks event history

WORK IN PROGRESS

[venkatd]

@matthew-carroll the implementation in our repo is very close to what you have described. (It has been running on our production app including undo/redo without any major issues so far.)

The flow happens in this order within controller.execute(command) (and is close to event sourcing best practices)

• A command handles validation and produces an event (it's not a void method, in our code it's named an Edit)
• This event gets inserted into a ledger that's managed by the controller (in our code, it's named a timeline)
• The current state gets advanced by calling event.apply (in backend systems, the state change is decoupled from the event, but I don't think decoupling this offers any advantage for our purposes)

Setting set selection and set text on controller are just shortcuts to calling controller.execute(...).

An few design decisions I think are worth highlighting

Commands and events don't mutate state directly

Commands return events. The events have apply and undo, pure functions, which take the previousValue and return nextValue. The don't modify anything in place. In the case of a SuperTextField, this value is an object that contains the AttributedText and TextSelection.

I would strongly recommend doing this rather than having void functions that mutate the state in place. It makes things easier to unit test, and easier to reason about because things are "frozen" until the very end at which the text+selection gets updated.

This would also open up possibilities such as:

• Time travel debugging with full traceability. We could visualize the state changes on the document, the events that triggered them, and the command that was executed
• Easier time to enforce invariants (for ex, can assert that event.undo(event.apply(document)) == document)

For SuperTextField, I think this would be trivial because AttributedText and TextSelection are pretty much immutable. For SuperEditor (as you've pointed out) that this could be more complex depending on the data structure. Is it possible to represent the document as an immutable value in the same way we can with SuperTextField? What are the trade-offs to doing so?

The ledger is mutated in a separate handler

I would recommend leaving ledger modification as a separate concern. The optimizations you describe such as taking snapshots, ignoring redundant events, pruning history, compacting multiple events, and so on, are application specific. One may want to modify how undo history is handled without having to rewrite the implementation of any commands or events.

In our implementation, we allow a custom handler for adding to the history:

typedef AddToHistoryHandler<T> = void Function(Queue<Event<T>> history, Event<T> event);

A handler like this allows a large diversity of implementations. For example:

• Ignore some events entirely (if move the cursor to the right, we don't want cmd+z to move the cursor back, meanwhile other implementations may want a full "replay" mode)
• Combine events into transactions (if you type "a", "b", then "c", we could pop these events off and re-insert those as a single event. Or if we add timestamps to each event, we could combine events that are within say 500ms of each other.
• Prune the history past more than 1000 edits