Posted by Mark Withall: 2014-06-20

Over the last week, I’ve developed an interest in Undo/Redo. This was partly inspired by reading an article by Aza Raskin (son of Jef) titled Never Use A Warning When You Mean Undo.

I looked at several articles on the subject of undo/redo and came to the conclusion that they were all far too complicated. I decided to see if there was a simpler way.

UndoableAction

In essence, to be able to have undo/redo functionality in an application one must have the ability to do and undo every action that modifies the state of the thing you are editing. [I realise that this is a rather loose definition and it should probably be pinned down for your specific application; in terms of what is, and isn’t, a state change that need to be undone.]

To achieve this, we can start by defining an interface to be implemented by all edit actions. This will look something like the following:

public interface UndoableAction
{
    void Do();
    void Undo();
}

UndoRedoStack

Undo and redo is essentially a stack operation. When an action is performed, it is put onto the undo stack. When undo is called, the top action on the stack is popped off; the undo method is run; and then the action is pushed onto the redo stack. When redo is called, the same sequence happens in reverse.

One special corner case, that caught me out at first, is the need to clear the redo stack when a new action is performed; as this invalidates the current redo stack because its expected initial state has now been changed. Undo is obviously unaffected by this.

A relatively simple implementation of the undo/redo stack might look something like the following:

public class UndoRedoStack
{
    private readonly Stack<UndoableAction> _undoStack = new Stack<UndoableAction>();
    private readonly Stack<UndoableAction> _redoStack = new Stack<UndoableAction>();

    public void Do(UndoableAction action)
    {
        action.Do();
        _undoStack.Push(action);
        _redoStack.Clear();
    }

    public void Undo()
    {
        RunAction(_undoStack, _redoStack, a => a.Undo());
    }

    public void Redo()
    {
        RunAction(_redoStack, _undoStack, a => a.Do());
    }

    private static void RunAction(
        Stack<UndoableAction> source,
        Stack<UndoableAction> target,
        Action<UndoableAction> undoRedo)
    {
        if (source.Count == 0)
            return;
        var action = source.Pop();
        undoRedo(action);
        target.Push(action);
    }
}

Each newly created action is passed to the Do method and Undo and Redo modify the state accordingly as they are called. This is almost certainly not thread safe but I’ll leave such additions as an exercise for the reader.

AddToListAction

All that remains is for us to create some undoable actions. These will, of course, be application specific and one must be very careful that undo and redo will perform correctly under all required circumstances. Here is a case that may commonly occur: adding an item to a list.

public class AddToListAction<T> : UndoableAction
{
    private readonly T _itemToAdd;
    private readonly IList<T> _list;

    public AddToListAction(T itemToAdd, IList<T> list)
    {
        _itemToAdd = itemToAdd;
        _list = list;
    }

    public void Do()
    {
        _list.Add(_itemToAdd);
    }

    public void Undo()
    {
        _list.RemoveAt(_list.Count - 1);
    }
}

In this case, Do appends an item to the end of the list and Undo removes the last item of the list. As long as the list is in the same state when Undo is called, as it was after Do had been called, everything should work out as planned. This is why it is important that every action that modifies the state is an UndoableAction.

ActionBlock

As a final bonus, here is another general purpose UndoableAction that is quite useful. Often we want to perform a group of actions in one compound action (e.g. adding a group of items to a list). In this case, we would want undo to remove all of the added items in one step rather than removing each item individually. Obviously, we could write an add multiple items action but that approach will get old fast as we add more and more actions. A better approach would be to have the ability to compose multiple simpler actions. This composition can also be done as an UndoableAction as follows:

public class ActionBlock : UndoableAction
{
    private readonly UndoableAction[] _actionSequence;

    public ActionBlock(params UndoableAction[] actionSequence)
    {
        _actionSequence = actionSequence;
    }

    public void Do()
    {
        foreach (var action in _actionSequence)
            action.Do();
    }

    public void Undo()
    {
        foreach (var action in _actionSequence.Reverse())
            action.Undo();
    }
}

This time, the action is a list of UndoableActions performed forwards for Do and in reverse for Undo. When Undo is called, all of the undo actions in the sequence will be called in one step.

So, there we have it. A simple implementation of undo/redo that uses an interface and a simple class that wraps two stacks. Now all that remains is the hard part: writing UndoableActions where Undo properly reverts the state.

A simple example implementation of the above can be found on github.