Leveraging Immutability and Observability for Reliable Undo/Redo in Document-Based Applications

Document-based applications are software systems that are centred around creating and editing documents. What constitutes a “document” depends on the application. For a text editor, it may be as simple as a single text file. A CAD application most likely has its own file format to efficiently contain all the data associated with a given project in one place.

This post uses a simple 2D canvas application (like Miro or Freeform) from now on to make examples more concrete.

Everyone building document-based applications finds themselves thinking about the following things:

The Document Format

In some cases, like when building a text editor, the document format already exists. You can open a *.txt file with any text editor. They share the same document format.

If you're dealing with custom data, or just want to own the format, you need to define how a document is persisted. This can be as simple as serialising your data as JSON and persisting that in a file with a custom extension.

For the sake of simplicity, we'll assume the sample canvas application persists its data in a custom JSON structure.

This post focuses on the undo/redo part so we'll not cover this in detail here. Let us know if you are interested in a Post about document formats and file versioning.

In-App Document Representation

When a user opens a document, it needs to be transformed into something that's optimal for the editor to work with. On first glance you could assume that for a text editor all you need is the text as a string.

In reality there are a multitude of reasons, why this does not work (well). More practical approaches are gap buffers, piece tables and ropes.

Visual Studio Code switched to using a piece table as their main data structure in 2018. The lesson here is that we need to optimise our data structure for the editor.

For our example canvas application we'll begin with only two shapes that can be added to the canvas: Rectangles and Circles.

public abstract record Element
{
    public required Guid ElementId { get; init; }
    public required DocumentPoint Position { get; init; }
}

public abstract record ShapeElement : Element
{
    public DocumentColor Fill { get; init; }
}

public record CircleElement : ShapeElement
{
    public double Radius { get; init; }
}

public record RectElement : ShapeElement
{
    public double Width { get; init; }
    public double Height { get; init; }
}

All elements have an id and position. Shapes additionally have a fill color. Rectangles have a width and height, circles have a radius.

public record DocumentState
{
    public required ImmutableList<Element> Elements { get; init; }
    public required ImmutableSortedSet<Guid> SelectedElementIds { get; init; }
}

A document simply consists of a list of elements and which elements are currently selected.

Keeping State, Applying Modifications

The classes above allow us to represent the current state of a document we are editing, but it does not allow us to actually modify state or subscribe to state changes.

Because DocumentState is immutable we can think of it as an unmodifiable snapshot of a document. What we are missing is a place that keeps the current state and allows us to apply changes, producing a new document state.

public interface IEditorOperation
{
    public Task<DocumentState> Apply(DocumentState state);
}

public interface IEditorDocument
{
    public IObservable<DocumentState> Current { get; }
    public DocumentState GetSnapshot();

    public void EnqueueOperation(IEditorOperation operation);
    public Task<bool> EnqueueOperationAsync(IEditorOperation operation);
}

The Current property can be used to observe changes to the document. This is useful so we can bind UI elements directly to the current state of our document or observe it in other places of our app.

With GetSnapshot we get snapshot of the current document state.

Modifications are applied by passing an operation either to EnqueueOperation or EnqueueOperationAsync. The operation is then enqueued and eventually applied. The synchronous implementation immediately returns once the operation is enqueued, the async operation returns a Task that completes once the operation has been applied.

public class EditorDocument : IEditorDocument
{
    private record struct ChannelItem(IEditorOperation Operation, TaskCompletionSource<bool>? TaskCompletionSource);

    private readonly Channel<ChannelItem> _operationQueue;
    private readonly BehaviorSubject<DocumentState> _currentInternalState;
    private readonly Observable<DocumentState> _current;

    public IObservable<DocumentState> Current => _current.AsSystemObservable();

    public EditorDocument(DocumentState initialState)
    {
        _operationQueue = Channel.CreateUnbounded<ChannelItem>();
        _currentInternalState = new BehaviorSubject<DocumentState>(initialState);
        _current =
            _currentInternalState
                .ObserveOnThreadPool()
                .Replay(1)
                .RefCount()
                .AsObservable();

        Task.Run(StartOperationConsumer);
    }

    private async Task StartOperationConsumer()
    {
        await foreach (var editorOperation in _operationQueue.Reader.ReadAllAsync())
        {
            try
            {
                var result = await editorOperation.Operation.Apply(_currentInternalState.Value);

                _currentInternalState.OnNext(result);

                editorOperation.TaskCompletionSource?.SetResult(true);
            }
            catch (Exception e)
            {
                Console.WriteLine(e);
                editorOperation.TaskCompletionSource?.SetResult(false);
            }
        }
    }

    public DocumentState GetSnapshot() => _currentInternalState.Value;

    public void EnqueueOperation(IEditorOperation operation)
        => _operationQueue.Writer.TryWrite(new ChannelItem(operation, null));

    public Task<bool> EnqueueOperationAsync(IEditorOperation operation)
    {
        var taskCompletionSource = new TaskCompletionSource<bool>();

        _operationQueue.Writer.TryWrite(new ChannelItem(operation, taskCompletionSource));

        return taskCompletionSource.Task;
    }
}

If we now want to allow users to add a new circle to the document we'd create an operation for that.

public class CreateCircleOperation : IEditorOperation
{
    private readonly DocumentPoint _position;
    private readonly double _radius;
    private readonly DocumentColor _fill;

    public CreateCircleOperation(DocumentPoint position, double radius, DocumentColor fill)
    {
        _position = position;
        _radius = radius;
        _fill = fill;
    }

    public Task<DocumentState> Apply(DocumentState state)
    {
        var newElement = new CircleElement()
        {
            ElementId = Guid.NewGuid(),
            Position = _position,
            Radius = _radius,
            Fill = _fill
        };

        var newElements = state.Elements.Add(newElement);

        return Task.FromResult(state with { Elements = newElements });
    }
}

Using the operation is quite simple, we can just create a new instance and pass it to the IEditorDocument instance.

Change Tracking

There are different ways to implement undo and redo functionality.

The Memento Pattern and the Command Pattern are commonly used. Both have their issues and you'll best understand them once you have tried to implement them yourself. Both are not simple to implement correctly and reliably. And if undo is unreliable why have it in the first place?

Our strategy is quite different.

Because our DocumentState and all classes contained in it are immutable, they can't be modified after they were created. If we hold a reference to a DocumentState we can trust that it will never change. A reference to a DocumentState is an unmodifiable snapshot. This means we can implement undo and redo by keeping a stack of previous state snapshots we might want to revert back to.

This might seem memory inefficient at first sight, but because our classes are immutable and immutable collections are designed for efficient copying this usually is a non-issue. You can read more about .NET Immutable collections here and more about structural sharing here and here.

This is what this History class does, it keeps lists of snapshots.

public record History<T>
{
    public T Current { get; }
    
    // Not all applied operations create state that belongs on the undo     
    // stack. Moving elements for example produces intermediate states that
    // should not be revertable. Only the final update need to be kept in 
    // the undo stack. 
    // 
    // AppendToHistory basically specifies if the current state should be
    // pushed to the undo stack when new state is pushed.
    private bool AppendToHistory { get; }
    
    private ImmutableStack<T> UndoStack { get; }
    private ImmutableStack<T> RedoStack { get; }

    public bool CanUndo => !UndoStack.IsEmpty;
    public bool CanRedo => !RedoStack.IsEmpty;
}

Instead of working with `DocumentState` in our EditorDocument / IEditorDocument we now use EditorState instead.

public record EditorState
{
    public required History<DocumentState> History { get; init; }

    // In a real app we might want to keep track of other not undoable     
    // changes here, like canvas filepath, zoom, offset, ...
    // public required string? FilePath { get; init; } = null;
    // public required DocumentPoint Offset { get; init; } 
    // public required double Zoom { get; init; }
}

public interface IEditorOperation
{
    public Task<EditorState> Apply(EditorState state);
}

public interface IEditorDocument
{
    public IObservable<EditorState> Current { get; }
    public EditorState GetSnapshot();

    public void EnqueueOperation(IEditorOperation operation);
    public Task<bool> EnqueueOperationAsync(IEditorOperation operation);
}

IEditorOperations now need to return a new EditorState with a modified copy of the History that contains the new state in Current.

To make this simpler we can add a few methods to the History class.

public record History<T>
{
    public T Current { get; }
    private bool AppendToHistory { get; }
    private ImmutableStack<T> UndoStack { get; }
    private ImmutableStack<T> RedoStack { get; }

    public bool CanUndo => !UndoStack.IsEmpty;
    public bool CanRedo => !RedoStack.IsEmpty;

    private History(
        T current,
        bool appendToHistory,
        ImmutableStack<T> undoStack,
        ImmutableStack<T> redoStack
    )
    {
        Current = current;
        AppendToHistory = appendToHistory;
        UndoStack = undoStack;
        RedoStack = redoStack;
    }

    public History<T> Push(T state, bool appendToHistory)
    {
        var undoStack =
            AppendToHistory
                ? UndoStack.Push(Current)
                : UndoStack;

        return new History<T>(state, appendToHistory, undoStack, ImmutableStack<T>.Empty);
    }

    public History<T> TryUndo(out bool success)
    {
        if (UndoStack.IsEmpty)
        {
            success = false;
            return this;
        }
        else
        {
            success = true;
            var newHistory = UndoStack.Pop(out var newState);
            return new History<T>(newState, true, newHistory, RedoStack.Push(Current));
        }
    }

    public History<T> TryRedo(out bool success)
    {
        if (RedoStack.IsEmpty)
        {
            success = false;
            return this;
        }
        else
        {
            success = true;
            var newHistory = RedoStack.Pop(out var newState);
            return new History<T>(newState, true, UndoStack.Push(Current), newHistory);
        }
    }

    public static History<T> CreateInitial(T state) => new(state, true, ImmutableStack<T>.Empty, ImmutableStack<T>.Empty);
}

With this in place we have everything we need to write applications that properly support undo and redo.

public class UndoOperation : IEditorOperation
{
    public Task<EditorState> Apply(EditorState state)
    {
        return Task.FromResult(state with { History = state.History.TryUndo(out _) });
    }
}

public class RedoOperation : IEditorOperation
{
    public Task<EditorState> Apply(EditorState state)
    {
        return Task.FromResult(state with { History = state.History.TryRedo(out _) });
    }
}

public static class EditorDocumentExtensions
{
    public static void TryUndo(this IEditorDocument document)
    {
        document.EnqueueOperation(new UndoOperation());
    }
    
    public static Task TryUndoAsync(this IEditorDocument document)
    {
        return document.EnqueueOperationAsync(new UndoOperation());
    }
    
    public static void TryRedo(this IEditorDocument document)
    {
        document.EnqueueOperation(new RedoOperation());
    }
    
    public static Task TryRedoAsync(this IEditorDocument document)
    {
        return document.EnqueueOperationAsync(new RedoOperation());
    }
}

Example

Here is an example that adds multiple circles to a document and uses undo/redo to go back/forward in time.

[Fact]
public async Task Example()
{
    var initialEditorState = new EditorState()
    {
        History = History<DocumentState>.CreateInitial(new DocumentState()
        {
            Elements = [],
            SelectedElementIds = []
        })
    };
    
    var editorDocument = new EditorDocument(initialEditorState);
    
    await editorDocument.EnqueueOperationAsync(
        new CreateCircleOperation(
            position: new DocumentPoint(100, 100),
            radius: 50,
            fill: DocumentColor.Red
        )
    );
    
    Assert.Equal(1, editorDocument.GetSnapshot().History.Current.Elements.Count);
    
    await editorDocument.EnqueueOperationAsync(
        new CreateCircleOperation(
            position: new DocumentPoint(200, 200),
            radius: 70,
            fill: DocumentColor.Blue
        )
    );
    
    Assert.Equal(2, editorDocument.GetSnapshot().History.Current.Elements.Count);
    
    await editorDocument.TryUndoAsync();
    
    Assert.Equal(1, editorDocument.GetSnapshot().History.Current.Elements.Count);
    
    await editorDocument.TryRedoAsync();
    
    Assert.Equal(2, editorDocument.GetSnapshot().History.Current.Elements.Count);
    
    await editorDocument.TryUndoAsync();
    await editorDocument.TryUndoAsync();
    
    Assert.Equal(0, editorDocument.GetSnapshot().History.Current.Elements.Count);
}

Feel free to ask questions and suggest deep dives in the comments. We're always happy to help.