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

Undo/redo part 2: exception safety

[19th January 2011]

Ok, so on with the second installment of the N-part series on undo/redo mechanisms. Last time we introduced the action base class and an elementary undo_stack.

I claimed that those were the easy bits, or at the very least, the only parts of an undo-supporting-application that anyone has cared to talk about on the web so far. So we'd better start looking at some of the harder parts now. In this episode: exception safety.

A quick refresher on exception safety

If you don't know what exception safety is, now's a good time to brush up. I'll quickly provide some terminology for those not in the know but for more information, I recommend this overview.

If there's no chance what-so-ever of a function throwing any kind of exception, it is said to provide the no-throw guarantee, which is the strongest of all the guarantees.

If there's a possibility that a function may throw an exception, ideally it will provide commit-or-rollback semantics in order to unwind any of the work it has done up to the point that the exception is thrown. In other words, if the function throws then there will be no externally-visible side-effects to the call. In this case, we say the function provides the strong guarantee.

The strong guarantee is often hard to achieve and even when it is attainable, providing it might incur a prohibitive cost to efficiency. In this case, providing the basic guarantee is the best we can hope for, which is to say that any objects involved are left with their invariants intact, even though they may not be in the same state as they were before the function was called.

If a function does not provide any of the above guarantees, then it is broken. That's not a special exception-safety-related definition, just a statement of fact that often comes as quite a worrying surprise to those that haven't thought about it before. If your application considers all exceptions to be fatal, then this strategy is possibly ok, but tread very carefully (especially when such functions are in libraries that may be deployed across multiple applications).

I get the impression that the C++ community as a whole is more switched on to exception safety than many others, but that's not to say that exception safety is specific to C++ by any means. The definitions above and the majority of the following discussion applies equally well to say, Java or Python. In fact, since exceptions are just one means of transporting error notifications, the ideas central to exception safety can be translated in to languages that can only return errors rather than throwing them, such as C[1].

Exception safety of action's methods

For reference, here's the action interface that was introduced in the previous installment:

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 &);
};

It now goes without saying, that it's rather important that the implementations of actions provide exception-safe overrides of the virtual functions, especially if exceptions aren't considered to be notifications of some internal fatality.

As I mentioned earlier, it's often the case that providing the strong guarantee can be rather difficult to achieve. And even if it is strictly speaking possible for the implementation to provide the strong guarantee, it is sometimes prohibitively inefficient compared to providing only the basic guarantee.

The fact that it's only reasonable to expect the basic guarantee of our actions actually has implications for the implementation of the undo_stack. To see why, let's recall the definition of undo_stack::undo():

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

It simply calls undo() on the action that was most recently executed, as identified by the just_done index, and then decrements that index. Unfortunately, for actions with undo() methods that don't provide the strong guarantee, this implementation of undo_stack::undo() is no good.

If an action's undo() method were to throw an exception, in the general case it means that the call only did a portion of what it wanted to do (as we only have the basic guarantee). This implies that subsequent calls to undo() or redo() might do too much, too little or simply break something in the data model.

To put it another way, we can think of the actions in an undo stack as a facility to transition between a number of discrete states of the data model: S[0], S[1], S[2], …, S[N], with S[0] being the default state. The kth action in the undo_stack has an undo() method that takes us from S[k+1] back to S[k] under non-exceptional circumstances. But if for example, actions[1]->undo() were to throw an exception, we can't simply forget about that action and decrement just_done regardless, because actions[0]'s undo() expects the data model to be in state S[1], when in fact it's now somewhere between S[1] and S[2].

So in the general case, if an action's undo() or redo() throws an exception, that action is pretty much useless thereafter. In fact, all actions in the undo stack are pretty much useless thereafter.

Horrifying conclusion

When an action's undo() or redo() throws, we must clear the undo stack(!) before propagating the exception. This conclusion applies irrespective of the particular undo_stack implementation, as half-undone/half-redone actions are always going to be a problem, however or wherever they're stored.

This turn of events was somewhat unexpected to me, but on the whole I don't think it's too bad, given that exceptions should be rare.

So, the revised implementation of undo_stack::undo():

// new utility method
void undo_stack::clear()
{
    // return to default state
    actions.clear();
    just_done = -1;
}

void undo_stack::undo()
{
    assert(can_undo()); // or an exception if you'd prefer
    try 
    { 
        actions[just_done]->undo();
        --just_done;
    }
    catch (...)
    {
        clear();
        throw;
    }
}

// undo_stack::redo() requires similar changes

Still, somehow, clearing the undo stack when an exception occurs still seems a little drastic. Perhaps we might consider adding a few bool-returning virtual functions to our action base class:

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

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

        // NEW: do undo()/redo() provide the strong exception safety guarantee?
        virtual bool undo_provides_sg() const { return false; }
        virtual bool redo_provides_sg() const { return false; }

        // 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 &);
};

Derived implementations could use these to indicate to the wider undo/redo system whether or not each of their methods provide the strong guarantee. If the strong guarantee is provided, then no stack-clearing needs to be done under exceptional circumstances:

void undo_stack::undo()
{
    assert(can_undo()); // or an exception if you'd prefer
    try 
    { 
        actions[just_done]->undo();
        --just_done;
    }
    catch (...)
    {
        if (!actions[just_done]->undo_provides_sg())
        {
            // We only need to clear the stack if the failed action::undo()
            // left the data model in some intermediate state.
            clear();
        }
        throw;
    }
}

// undo_stack::redo() requires similar changes

The default implementations of action::undo_provides_sg() and action::redo_provides_sg() means you can ignore these features completely if you simply want to assume nothing more than the basic guarantee for all actions.

Some cases where the strong guarantee is easy to provide

SQL-driven relational data bases provide transactional semantics, which can be easily translated in to strongly exception-safe functions. So if your entire data-model is nothing more than a database, you can happily forget this discussion and use the original undo_stack! And of course, because of projects such as SQLite, databases don't have to be heavyweight.

I also have a feeling that Apple's Core Data APIs provide a transactional framework for data model manipulations, but I couldn't confirm this by a 2 minute skim of the documentation. There's certainly something for undo support in there, but is it transactional? If you know more, please let me know in the comments!

Lastly, though I haven't yet found a spare weekend to give Clojure a whirl, I think its persistent data structures might provide a natural means to efficiently represent discrete states in the data model, because of the sharing properties of those data structures. So if you can compose your data model entirely of persistent structures, you're laughing. Again, confirmation in the comments would be appreciated if you're in the know!

But for better or worse, this a C++ blog and so I'll be continuing to battle through the ins and outs of undo/redo from the C++ perspective and will have to leave SQL, Cocoa and Clojure behind for the most part.

Next up: combining actions efficiently

That's all until the next installment, where I'll be looking out how we can combine multiple actions in to a single action as best as possible, and why we might want to do so.

But I have sneaking suspicion that we'll bump in to exception safety again, further down the road…

Footnotes
  1. though arguably setjmp/longjmp provide a raw exception handling baseline []

Comments

(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.