Designing Undo for large-scale projects. Going deep.

That is huge architect-level article about designing undo in large-scale project, welcome under more label…

Pre-requirements

First it makes sense to talk about some pre requirements. It worths that application classes and relations between them can be really split into two parts – one is business logic and second is user interface. As example you can consider project where you can exclude all gui codes from compilation just by removing such files and it still compiles fine and as result you get a command-line tool which has same functionality as gui application but managed through command-line options for example.

That’s probably an ideal example, but often it is enough to have an architecture of project which is close to described idea, and I suggest as you took large-scale project in your account and responsibility you probably already moved into the direction to have the user interface codes separated from real logic of application which does what user requires.

Also I would suggest that you have combined several modules which provides some functionality, or they may be kind of “cores” for some logics. Then they may have or may not have own user interfaces. Those modules can be developed by different people in different times.

So your task is some kind of an architecturing all these modules, objects, codes to work really well together and the application should provide an easy way for user to just undo any change that he applied to the data without any harm to the state of user data. Surely if you would like users to love your application which can do really complicated things then users should not afraid of pressing undo/redo.

I sure you may state examples of such applications where the idea of undo is discredited at all. Such application declares undo functionality but it works so unstable and just leads users to save datas every time when they do something that they may feel will harm datas if they try undo/redo, and as it is not stable they have to do it very often.

By separation of logic and gui the project may look like this:

It looks as composed as two parts where “logic” part is not dependent on gui. Gui still may add some “logic” which is more related to operating all gui states etc.

Where to apply

Then for analyzing the project you should decide where are points of applying your efforts. Let’s consider some examples:

1. One – it is an application of hundred different actions that user can apply by using menu items, keyboard shortcuts, complex iterations with data structures etc, but same time on the “data model” level it can have very few actions to operate with data – like: the core of project are just few data models.

2. Second – it is an application of very few but advanced methods available for user iterations but on “core” level you have hundred of data structures, they relations and more.

3. Third example may be a large-scale project have hundred of user interactions and tons of tangled internals.

In first example it is clear enough that you may reimplement few virtual methods of “core” logic to have them transparently cover by undo. That’s something that I described in Undo in complex Qt projects but maybe not deep enough.

For second example you can probably easily implement undo coverage in points where user applys his actions – in GUI level just as reaction to user interactions. But again because logic of “core” level expected to be very tricky (we do large-scale app isn’t?) you may face with problem that there is no direct “reverse” operation even implemented, and you have to do it in right way and then also keep it maintained and in sync with direct operation. Situation may went bad if the “core” have progressing changes which you then always have to reflect to undo. Also though now application have very few user interactions, still you plan to add new functionalities in new version, isn’t? So you may encounter huge number of changes that you have to apply to code. Almost same in third example where you have combination of both.

So I hope you see my point why undo should not be implemented in a way to just to cover user interaction where they are invoked.

Again from considerations above you may see a lot of problematic point that hard to resolve at first sight.

Storing changes

First consider way of “storaging” undo data/commands in stack. There are three ways:

1. Whole document is serialized on every user interaction and restored to state on undo – may work for something small, but totally unproductive for us.

2. Every object can be serialized separately in own small piece of data and restore. Here you should be very very careful to avoid having ANY pointer in undo commands. Because, as something is serialized in undo, then removed, later by undo restored into a new object (deserialized) and we have an another pointer!!! for new object which comes from undo stack – so all other undo commands now have wrong pointer.

3. Keep objects and they properties in undo commands – this one may be most productive as you need to have change existing code not much. So you operate with smart pointers only (boost/std::shared_ptr, QSharedPointer etc) Easy to explain why – as some object is removed from your document at all, there is only one reference left to keep your object alive – reference from undo stack. As you clear undo stack or by interactions go by other branch, then all collected information is free to be released and then your objects are deleted – exactly precise moment of time.

Again be very careful not to mix means 2 and 3, sometime it may work, but it is very easy to break when you are changing your code. So better to chose just one of these methods.

Too many calls to cover

Second, if you have hundred of methods which change something in your objects, like: Obj1::setSomething1(Arg1 arg), Obj1::setSomething2(Arg2 arg) … and more and more. Not a good idea to write separate undo command for each, isn’t?

Let’s use all power of C++ templates. You know that it is very easy to write generic code which can be applied to generic objects which have same api, but we need to make an generic algorithm to apply to “any” method which requires undo. Let’s write it like this:

template<class Item, class Value, typename Set>
void Undo(Item * i, Value to, Value from, Set set) {
    if (from == to) return;
    // get shared pointer as shared_from_this or your other way
    shared_ptr<Item> ip = i->shared_from_this<Item>();
    if (!ip) { set(i,to); return; }
    // way to access current undo stack
    QUndoStack * st = ...
    if (!st) { set(i,to); return; }
    st->push(new UndoValueCmd<Item,Value,Set>(ip,to,from,set));
}

Unclear? I guess it is, let’s show how UndoValueCmd looks like:

template <class Item, class Value, typename Set>
class UndoValueCmd : public QUndoCommand {
    shared_ptr<Item> i; Value to,from; Set set;
public:
    UndoValueCmd(shared_ptr<Item> ip, Value t, Value f, Set s)
        :i(ip), to(t),from(f),set(s) {}
    void redo() override { set(i.get(), to); }
    void undo() override { set(i.get(), from); }
};

I guess still not clear enough, so let’s show how to cover some method:

class ModelUndo : public Model {
    typedef Model Base;
    typedef ModelUndo This;
public:
    ...
    void setRect(QRectF r) override
        { Undo(this,r,rect(), std::mem_fun(&This::b_setRect)); }
    void setComments(QString v) override
        { Undo(this,v,comments(), std::mem_fun(&This::b_setComments)); }
private:
    ...
    void b_setRect(QRectF r) { Base::setRect(r); }
    void b_setComments(QString v) { Base::setComments(v); }

We inherited class Model and covered virtual methods of super class: setRect() and setComments() by undo – all changes to rect and comments are stored to undo stack. And because methods are virtual, it tracks changes even in “logic” module when it makes calls: model->setComments(“”).

Why it works? and why do we need these “b_” methods? Answer is simple enough: we use std::mem_fun to make a wrapping object for specific method – create a functor – because we need to use the method later – when apply for undo or redo. This functor is stored in undo command as reference which method of object we need to call (see calls like this: set(i.get(), from);), But in C++ when we call member function in this way we can not bypass table of virtual functions. So no matter which functor we will make – std::mem_fun(&This::setComments) or std::mem_fun(&Base::setComments) – you can not bypass virtualization, and as result we get a recursion :(. But we can pass a private method This::b_setComments which by calling Base::setComments will bypass the virtualization!

Note from 2016: Surely the b_ methods should be replaced with lambdas as we have modern compilers.

Summarize: every time when we need to cover some setSomething() method then instead of writing new undo command class we need to call just Undo() call and write simple b_setSomething() which is more like just “definition” of what we would like to undo. So, simple to maintain, simple to expand.

Non-linear behavior

This is most valuable point of the whole article, so sure it is at the very end of text

Let’s explain what I mean by non-linear behavior. If we have more closer look at example above you may see that application of that is very limited and it is applicable only if there are no cross-calss, cross-usages of methods of each other. Very simple example: imagine that “logic” implementation of Model::setRect() also changes comments:

void Model::setRect(QRectF r) {
    m_rect = r;
    setComments(tr("Hey!, rect width is now %1").arg(r.width()));
    update();
}

On first sight, if we consider just very first redo it looks okay, by calling ModelUndo::setRect() we have pushed undo command to record changes of rect and same time because it will cast for setComments(), the reimplemented ModelUndo::setComments() also push undo command to record changes about comments.

But if we follow how it works when user pressed “undo” we will see real disaster!. The implementation of undo() for rect changes will cast Model::setRect() to restore previous rect that was before, but due to implementation of Model::setRect() it will push new undo command into the stack!

User will see that when he presses undo(Ctrl+Z) previous “redo” part of undo stack is dropped away and new unexpected undo actions appears in stack!

Such behavior (non-linear) is actually happens much much often in applications and actually it cause all complications in implementing undo in large-scale applications. That’s why developers see that they can not implement “coverage” of logic level and instead they go to the level “above” gui and try to implement coverage there, but as result they are duplicating a lot of code from logic level and even do it multiple times as logic code is interlinked and later they fail in the maintenance of application and make it almost impossible to grow it and expand with new functionalities as complexity of undo code is just growing exponentially. Often even the adding more people to devteam makes the situation worse.

How we can solve this? You may notice that existing undo frameworks can not offer a generic solutions for such cases. But solution is simple enough but it requires you to implement “nested undo“. Let’s show a code of undo command for setRect() which resolves the problem:

class SetRectUndo : public QUndoCommand {
    QUndoStack stRedo, stUndo; 
    Model * m; QRectF rNew, rOld;
public:
    SetRectUndo(Model * _m, QRectF r_new, QRectF r_old): 
        m(_m), rNew(r_new), rOld(r_old) {}
    void redo() {
        QUndoStack * cur = currentUndoStack();
        setCurrentUndoStack(&stRedo);
        stRedo.beginMacro("nested");
        m->Model::setRect(rNew);
        stRedo.endMacro();
        setCurrentUndoStack(cur);
    }
    void undo() {
        QUndoStack * cur = currentUndoStack();
        setCurrentUndoStack(&stUndo);
        stUndo.beginMacro("nested");
        m->Model::setRect(rOld);
        stUndo.endMacro();
        setCurrentUndoStack(cur);
        stUndo.clear();
        while(stRedo.canUndo()) stRedo.undo();
        stRedo.clear();
    }
};

Let’s follow setRect() initiated by user actions: first it makes current undo stack stRedo, start macro and then cast Model::setRect(). In implementation of Model::setRect() it cast setComments() which leads to reimplemented ModelUndo::setComments() which pushes new undo command, but into stRedo.

Let’s follow pressing Ctrl+Z by user. We go into SetRectUndo::undo(), where it changes current undo stack into stUndo, then it cast for Model::setRect() to restore old rect, but same times it cast setComments(), which by reimplementation pushes new undo command but into stUndo, – stack of application(or document) is not spoiled by new undo command. Then it clears stUndo, as we are not interested in it. Finally, at the end we undo everything what is located in stRedo – you may remember that it has an undo command to change comments which were before setRect() initiated by user actions.

It reverts to exactly same state of datas existing before user action even with non-linear behavior. Good.

Please note that depending on the way of interlinking of calls you may need to do some adjustments to code above to fix the order of calls and restoring nested stacks, but still that can be usually resolved simple enough appropriate to your codes.

Summary

We researched above such problems as ways of tracking undo, places of applying efforts to implement it in effective way, covering of numerous methods by using templating approaches and finally covering of non-linear behaviors.

As result you may choose such architecture of your application:

Then you have undo layer between logic and gui, covering all changes in user datas with respect to non-linear behavior.

Also you can notice that by just few defines in code you can switch off the whole undo layer, because this is really just layer created by inheritance, and then test behavior of your application without undo involved. For testing purposes it makes sense as you can easily allocate places where your bugs comes from and if they are related to undo effects at all.

How would you use undo now as top-level/integration gui developer? That is the place where your dream comes true! All what you need to do is just marking beginMacro() and endMacro() for places that should be covered by undo:

void DocumentWindow::onActionSomethingComplicated() 
{
    currentUndoStack()->beginMacro(tr("Do something complicated here"));
    Obj1 * obj1 = document()->createXxxObject("yyy");
    obj1->addSubObject(document()->newLevel(1));
    ....
    ....
    // whatever you can do with user datas
    ....
    currentUndoStack()->endMacro();
}

Then user presses Ctrl+Z and magic works…