mr-edd.co.uk :: horsing around with the C++ programming language

Undo/redo part 1: the easy bits

[16th January 2011]

First of all: happy new year! Better late than never, I suppose :)

In my current project at work, we've been looking in to and exploring various implementations of undo/redo.

A web-search yields plenty of results, each eagerly telling you how to use the command pattern to create undo-able tasks and put them in to some kind of undo stack container. This is all well and good, but from where I'm standing, implementing the command pattern for undo/redo and rustling up an undo_stack class is the easy bit.

What I struggled to find were any notes on the implications for an application's data model, given that most or all mutations have to be undo-able. This is the hard bit of implementing undo/redo, I think. It's what our team has been discussing recently and it is these implications that I want to get around to discussing in subsequent posts.

We might even end up with a little library by the end of this series. We'll see…

Unfortunately, this will be another one of those articles that runs through the implementation of an undo stack, but I just want to get this down quickly so that we can refer back to it in follow-up posts of the series.

So let's crack on. We'll assume that we're creating an application that has two menu items, Edit > Undo and Edit > Redo:

undo/redo in edit menu

We won't worry about being able to repeat the last action performed, or having to provide a description of each action (both these things often appear nearby in the Edit menu), or anything else too fancy.

The action interface

class action
{
    public:
        virtual ~action() { }

        virtual void exec() { redo(); }
        virtual void undo() = 0;
        virtual void redo() = 0;

        // perhaps add stuff for action description, memory usage, whether
        // or not the action is repeatable, etc

    protected:
        action() { }

    private:
        // prohibit copying to prevent accidental slicing and other nasties
        action(const action &);
        action &operator= (const action &);
};

typedef boost::shared_ptr<action> action_ptr; // we'll use this later

So here we have an interface that must be implemented for each undo-able action. At a minimum, the undo() and redo() methods must be overridden in order to do the right thing for the particular data-model-mutation in question. For many derived action implementations, executing the action in the first place — that is, calling exec() — will be equivalent to redo(). This is encoded in the way that the method definition of exec() defers to redo() by default[1].

There are a bunch of other ways of writing the action class, but they all essentially boil down to the same thing. So I won't bother to enumerate the alternatives.

As a quick example, consider the simplest possible todo-list application. We might have an add_todo action that looks something like this:

struct add_todo : action
{
    std::string item;
    todo_list &todos;

    add_todo(const std::string &item, todo_list &todos) : 
        item(item),
        todos(todos)
    {
    }

    void undo() { todos.remove_last(); }
    void redo() { todos.append(item); }
    // exec() does the right thing already
};

Before you fall asleep, let's now get the undo_stack class out the way.

The undo_stack class

Nothing too fancy is going on here. The basic idea is to maintain an array of actions and keep an index in to that array that refers to the last action that has been performed. When the user clicks Edit > Undo, the action at this index has its undo() method called and the index is decremented. The reverse happens for Edit > Redo.

class undo_stack
{
    public:
        undo_stack() : just_done(-1) { }

        bool can_undo() const 
        { 
            return just_done != -1; 
        }
        
        bool can_redo() const 
        {
            return static_cast<std::size_t>(just_done + 1) < actions.size(); 
        }

        // assumes the action has already been executed
        void push(const action_ptr &a)
        {
            // N.B. erase() doesn't change capacity(), so push_back() won't throw
            // if there are elements to erase i.e. we're strongly exception-safe.
            actions.erase(actions.begin() + (just_done + 1), actions.end());
            actions.push_back(a);
            ++just_done;

            assert(can_undo());
            assert(!can_redo());
        }

        const action &top() const
        {
            assert(can_undo()); // or an exception if you'd prefer
            return *actions[just_done];
        }

        void undo()
        {
            assert(can_undo()); // or an exception if you'd prefer
            actions[just_done]->undo();
            --just_done; // only decrement if undo() doesn't throw
        }

        void redo()
        {
            assert(can_redo()); // or an exception if you'd prefer
            actions[just_done + 1]->redo();
            ++just_done; // only advance if redo() doesn't throw
        }

    private:
        undo_stack(const undo_stack &);
        undo_stack &operator=(const undo_stack &);

    private:
        long just_done; // index of last action performed
        std::vector<action_ptr> actions;
};

Other implementations might maintain two separate arrays/stacks internally, but I think having an index (just_done) in to a single array is simpler. This implementation also assumes that it's not possible to undo arbitrary actions in the stack without having undone all those that came after it, first. Again, most variations are actually quite boring. Add pepper to taste.

Coming soon

So that concludes the easy bits. I'll be referring to these basic elements in subsequent installments in this series, which I hope will explore the following topics:

Throughout the series, I'd be very interested to hear about other undo/redo implementations, particularly the deeper stuff I'll be wading in to next. So please leave suggestions, alternatives, tips and tricks in the comments!

Footnotes
  1. I would have liked to have called the exec() method do() instead, but of course do is a C++ keyword. If you use a title-case naming convention, you're in luck here []

Comments

ManicQin

[11/02/2011 at 01:31:52]

About the function exec.
The way I see it, exec() could easily be a heavy function (e.g. search and replace).

Shouldn't exec() process the operation, store as much information (or even the result) aside and then redo() would just use that pre-calculated information? (memorization)

If you hardwire exec() to call redo() at the base you leave "lazy" derivers to only implement the redo() and recalculate the heavy process.

Edd

[11/02/2011 at 19:11:15]

exec() isn't hard-wired. It's a virtual function. In those cases where exec()'s behaviour needs to differ from that of redo()'s, it can.

(optional)
(optional)
(required, hint)

Links can be added like [this one -> http://www.mr-edd.co.uk], to my homepage.
Phrases and blocks of code can be enclosed in {{{triple braces}}}.
Any HTML markup will be escaped.