Mechanism for Save/Load+Undo/Redo with minimum boilerplate

Question

I want to make an app where a user can edit a diagram (for example), which would provide the standard mechanisms of: Save, Load, Undo, and Redo.

A simple way to do it is to have classes for the diagram and for the various shapes in it, which implement serialization via save and load methods, and where all methods to edit them return UndoableActions that can be added to an UndoManager which calls their perform method and adds them to an undo stack.

The problem with the simple way described above is that it requires a lot of error-prone boilerplate work.

I know that the serialization (save/load) part of the work can be solved by using something like Google's Protocol Buffers or Apache Thrift, which generates the boiler-plate serialization code for you, but it doesn't solve the undo+redo problem. I know that for Objective C and Swift, Apple provides Core Data which does solve serialization + undo, but I'm not familiar with anything similar for C++.

Is there a good way non-error-prone to solve save+load+undo+redo with little boilerplate?

Answer 1

The problem with the simple way described above is that it requires a lot of error-prone boilerplate work.

I am not convinced that this is the case. Your approach sounds reasonable and using Modern C++ features and abstractions you can implement a safe and elegant interface for it.

For starters, you could use std::variant as a sum type for "undoable actions" - this will give you a type-safe tagged union for every action. (Consider using boost::variant or other implementations that can be easily found on Google if you do not have access to C++17). Example:

namespace action
{
    // User dragged the shape to a separate position.
    struct move_shape
    {
        shape_id _id;
        offset _offset;
    };

    // User changed the color of a shape.
    struct change_shape_color
    {
        shape_id _id;
        color _previous;
        color _new;
    };

    // ...more actions...
}

using undoable_action = std::variant<
    action::move_shape,
    action::change_shape_color,
    // ...
>;

Now that you have a sum type for all your possible "undoable actions", you can define undo behavior by using pattern matching. I wrote two articles on variant "pattern matching" by overloading lambdas that you could find interesting:

• "visiting variants using lambdas - part 1"

• "visiting variants using lambdas - part 2"

Here's an example of how your undo function could look like:

void undo()
{
    auto action = undo_stack.pop_and_get();
    match(action, [&shapes](const move_shape& y)
                  {
                      // Revert shape movement.
                      shapes[y._id].move(-y._offset);
                  },
                  [&shapes](const change_shape_color& y)
                  {
                      // Revert shape color change.
                      shapes[y._id].set_color(y._previous);
                  },
                  [](auto)
                  {
                      // Produce a compile-time error.
                      struct undo_not_implemented;
                      undo_not_implemented{};
                  });
}

If every branch of match gets large, it could be moved to its own function for readability. Trying to instantiate undo_not_implemented or using a dependent static_assert is also a good idea: a compile-time error will be produced if you forget to implement behavior for a specific "undoable action".

That's pretty much it! If you want to save the undo_stack so that the history of actions is preserved in saved documents, you can implement a auto serialize(const undoable_action&) that, again, uses pattern matching to serialize the various actions. You could then implement a deserialize function that repopulates the undo_stack on file load.

If you find implementing serialization/deserialization for every action too tedious, consider using BOOST_HANA_DEFINE_STRUCT or similar solutions to automatically generate serialization/deserialization code.

Since you're concerned about battery and performance, I would also like to mention that using std::variant or similar tagged union constructs is on average faster and more lightweight compared to polymorphic hierarchies, as heap allocation is not required and as there is no run-time virtual dispatch.

---

About redo functionality: you could have a redo_stack and implement an auto invert(const undoable_action&) function that inverts the behavior of an action. Example:

void undo()
{
    auto action = undo_stack.pop_and_get();
    match(action, [&](const move_shape& y)
                  {
                      // Revert shape movement.
                      shapes[y._id].move(-y._offset);
                      redo_stack.push(invert(y));  
                  },
                  // ...

auto invert(const undoable_action& x)
{
    return match(x, [&](move_shape y)
                {
                    y._offset *= -1;
                    return y;
                },
                // ...

If you follow this pattern, you can implement redo in terms of undo! Simply call undo by popping from the redo_stack instead of the undo_stack: since you "inverted" the actions it will perform the desired operation.

---

EDIT: here's a minimal wandbox example that implements a match function that takes in a variant and returns a variant.

• The example uses boost::hana::overload to generate the visitor.

• The visitor is wrapped in a lambda f that unifies the return type to the type of the variant: this is necessary as std::visit requires that the visitor always returns the same type.

  • If returning a type which is different from the variant is desirable, std::common_type_t could be used, otherwise the user could explicitly specify it as the first template parameter of match.

Answer 2

Two reasonable approaches to this problem are implemented in the frameworks Flip and ODB.

Code-generation / ODB

With ODB you need to add #pragma declarations to your code, and have it's tool generate methods that you use for save/load and for editing the model, like so:

#pragma db object
class person
{
public:
    void setName (string);
    string getName();
    ...
private:
    friend class odb::access;
    person () {}

    #pragma db id
    string email_;

    string name_;
 };

Where the accessors declared in the class are auto-generated by ODB so that all changes to the model can get captured and undo-transactions may be made for them.

Reflection with minimal boilerplate / Flip

Unlike ODB, Flip doesn't generate C++ code for you, but rather it requires your program to call Model::declare to re-declare your structures like so:

class Song : public flip::Object
{
public:
    static void declare ();
    flip::Float tempo;
    flip::Array <Track> tracks;
};

void Song::declare ()
{
    Model::declare <Song> ()
    .name ("acme.product.Song")
    .member <flip::Float, &Song::tempo> ("tempo");
    .member <flip::Array <Track>, &Song::tracks> ("tracks");
}

int main()
{
    Song::declare();
    ...
}

With the structured declared like so, flip::Object's constructor can initialize all the fields so that they can point to the undo stack, and all the edits on them are recorded. It also has a list of all the members so that flip::Object can implement the serialization for you.

Answer 3

The problem with the simple way described above is that it requires a lot of error-prone boilerplate work.

I would say that the actual problem is that your undo/redo logic is part of a component, that should ship only a bunch of data as a position, a content and so on.

A common OOP way to decouple the undo/redo logic from the data is the command design pattern.
The basic idea is that all the user interactions are converted to commands and those commands are executed on the diagram itself. They contain all the information required to perform an operation and to rollback it, as long as you maintain a sorted list of commands and undo/redo them in order (that is usually the user expectation).

Another common OOP pattern that can help you either to design a custom serialization utility or to use the most common ones is the visitor design pattern.
Here the basic idea is that your diagram should not care about the kind of components it contains. Whenever you want to serialize it, you provide a serializer and the components promote themselves to the right type when queried (see double dispatching for further details on this technique).

That being said, a minimal example is worth more than a thousand words:

#include <memory>
#include <stack>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
#include <string>

struct Serializer;

struct Part {
    virtual void accept(Serializer &) = 0;
    virtual void draw() = 0;
};

struct Node: Part {
    void accept(Serializer &serializer) override;
    void draw() override;
    std::string label;
    unsigned int x;
    unsigned int y;
};

struct Link: Part {
    void accept(Serializer &serializer) override;
    void draw() override;
    std::weak_ptr<Node> from;
    std::weak_ptr<Node> to;
};

struct Serializer {
    void visit(Node &node) {
        std::cout << "serializing node " << node.label << " - x: " << node.x << ", y: " << node.y << std::endl;
    }

    void visit(Link &link) {
        auto pfrom = link.from.lock();
        auto pto = link.to.lock();
       std::cout << "serializing link between " << (pfrom ? pfrom->label : "-none-") << " and " << (pto ? pto->label : "-none-") << std::endl;
    }
};

void Node::accept(Serializer &serializer) {
    serializer.visit(*this);
}

void Node::draw() {
    std::cout << "drawing node " << label << " - x: " << x << ", y: " << y << std::endl;
}

void Link::accept(Serializer &serializer) {
    serializer.visit(*this);
}

void Link::draw() {
    auto pfrom = from.lock();
    auto pto = to.lock();

    std::cout << "drawing link between " << (pfrom ? pfrom->label : "-none-") << " and " << (pto ? pto->label : "-none-") << std::endl;
}

struct TreeDiagram;

struct Command {
    virtual void execute(TreeDiagram &) = 0;
    virtual void undo(TreeDiagram &) = 0;
};

struct TreeDiagram {
    std::vector<std::shared_ptr<Part>> parts;
    std::stack<std::unique_ptr<Command>> commands;

    void execute(std::unique_ptr<Command> command) {
        command->execute(*this);
        commands.push(std::move(command));
    }

    void undo() {
        if(!commands.empty()) {
            commands.top()->undo(*this);
            commands.pop();
        }
    }

    void draw() {
        std::cout << "draw..." << std::endl;
        for(auto &part: parts) {
            part->draw();
        }
    }

    void serialize(Serializer &serializer) {
        std::cout << "serialize..." << std::endl;
        for(auto &part: parts) {
            part->accept(serializer);
        }
    }
};

struct AddNode: Command {
    AddNode(std::string label, unsigned int x, unsigned int y):
        label{label}, x{x}, y{y}, node{std::make_shared<Node>()}
    {
        node->label = label;
        node->x = x;
        node->y = y;
    }

    void execute(TreeDiagram &diagram) override {
        diagram.parts.push_back(node);
    }

    void undo(TreeDiagram &diagram) override {
        auto &parts = diagram.parts;
        parts.erase(std::remove(parts.begin(), parts.end(), node), parts.end());
    }

    std::string label;
    unsigned int x;
    unsigned int y;
    std::shared_ptr<Node> node;
};

struct AddLink: Command {
    AddLink(std::shared_ptr<Node> from, std::shared_ptr<Node> to):
        link{std::make_shared<Link>()}
    {
        link->from = from;
        link->to = to;
    }

    void execute(TreeDiagram &diagram) override {
        diagram.parts.push_back(link);
    }

    void undo(TreeDiagram &diagram) override {
        auto &parts = diagram.parts;
        parts.erase(std::remove(parts.begin(), parts.end(), link), parts.end());
    }

    std::shared_ptr<Link> link;
};

struct MoveNode: Command {
    MoveNode(unsigned int x, unsigned int y, std::shared_ptr<Node> node):
        px{node->x}, py{node->y}, x{x}, y{y}, node{node}
    {}

    void execute(TreeDiagram &) override {
        node->x = x;
        node->y = y;
    }

    void undo(TreeDiagram &) override {
        node->x = px;
        node->y = py;
    }

    unsigned int px;
    unsigned int py;
    unsigned int x;
    unsigned int y;
    std::shared_ptr<Node> node;
};

int main() {
    TreeDiagram diagram;
    Serializer serializer;

    auto addNode1 = std::make_unique<AddNode>("foo", 0, 0);
    auto addNode2 = std::make_unique<AddNode>("bar", 100, 50);
    auto moveNode2 = std::make_unique<MoveNode>(10, 10, addNode2->node);
    auto addLink = std::make_unique<AddLink>(addNode1->node, addNode2->node);

    diagram.serialize(serializer);    
    diagram.execute(std::move(addNode1));
    diagram.execute(std::move(addNode2));
    diagram.execute(std::move(addLink));
    diagram.serialize(serializer);
    diagram.execute(std::move(moveNode2));
    diagram.draw();
    diagram.undo();
    diagram.undo();
    diagram.serialize(serializer);
}

I've not implemented the redo action and the code is far from being a production-ready piece of software, but it acts quite well as a starting point from which to create something more complex.

As you can see, the goal is to create a tree diagram that contains both nodes an links. A component contains a bunch of data and knows how to draw itself. Moreover, as anticipated, a component accepts a serializer in case you want to write it down on a file or whatever.
All the logic is contained in the so called commands. In the example there are three commands: add node, add link and move node. Neither the diagram nor the components know anything about what's going on under the hood. All what the diagram knows is that it's executing a set of commands and those commands can be executed back a step at the time.

A more complex undo/redo system can contain a circular buffer of commands and a few indexes that indicate the one to substitute with the next one, the one valid when going forth and the one valid when going back.
It's quite easy to implement indeed.

This approach will help you decoupling the logic from the data and it's quite common when dealing with user interfaces.
To be honest, it's not something that came up suddenly to my mind. I found something similar while looking at how open-source software solved the issue and I've used it a few years ago in a software of mine. The resulting code is really easy to maintain.

Answer 4

Another approach you might want to consider is working with inmutable data structures and objects. Then, the undo/redo stack can be implemented as a stack of versions of the scene/diagram/document. Undo() replaces the current version with an older version from the stack, and so on. Because all data is inmutable, you can keep references instead of copies, so it is fast and (relatively) cheap.

Pros:

• simple undo/redo
• multithread-friendly
• clean separation of "structure" and transient state (e.g. current selection)
• may simplify serialization
• caching/memoization/precomputation-friendly (e.g. bounding-box, gpu buffers)

Cons:

• consumes a bit more memory
• forces separation of "structure" and transient state
• probably more difficult: for example, for a typical tree-like scenegraph, to change a node you would also need to change all the nodes along the path to the root; the old and new versions can share the rest of the nodes