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

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?

6 Answers

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

Answers 2

There are few projects that could help with some boilerplate code.
You already know, as you mention in your question, which software could help with the save/load part of the work, namely Google's Protocol Buffers, Apache Thrift and Boost Serialization.
It appears from a brief research, that there are some projects that could help with the undo/redo part of you work.
In this respect I would like to mention a few:

1. Flip
   https://isocpp.org/blog/2016/12/flip-a-new-data-model-cpp-framework-focused-on-real-time-collaboration
   https://irisate.com/flip-overview/
   http://ohmflip.sourceforge.net/index.html

2. http://doc.qt.io/qt-5/qundocommand.html: it appears that might help you. Please check also an extra example located in http://doc.qt.io/qt-5/qtwidgets-tools-undoframework-example.html which also makes use of those classes for undo/redo

3. Txnmgr
   http://www.findbestopensource.com/product/txnmgr
   https://code.google.com/archive/p/txnmgr/

4. NLHistory
   https://github.com/catnapgames/NLHistory

5. https://github.com/d-led/undoredo-cpp
6. https://github.com/aseprite/undo

It also seems that Qt 5 does provides some serialization functionalities:
http://doc.qt.io/qt-5/datastreamformat.html
which might turn out to be useful for you, in addition to the undo/redo mentioned in 1).
Flip seems really powerful software that is used in industry and provides undo/redo, though you should check whether it fits your needs.

Then there's ODB. Since you are mentioning sqlite in comments and minimizing handling details of saving the state, I thought might be useful for you:
http://www.codesynthesis.com/products/odb/

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

Answers 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

Answers 5

Assuming that you're calling save() on a temporary file for each edit of the diagram (even if user doesn't explicitly call the save action) and that you undo only the latest action, you can do as follows:

LastDiagram load(const std::string &path) {   /* Check for valid path (e.g. boost::filesystem here) */   if(!found)   {     throw std::runtime_exception{"No diagram found"};   }    //read LastDiagram   return LastDiagram; } LastDiagram undoLastAction() {     return loadLastDiagram("/tmp/tmp_diagram_file"); } 

and in your main app you handle the exception if thrown. In case you want to allow more undos, then you should think to a solution like sqlite or a tmp file with more entries.

If performance in time and space are issues due large diagrams, think to implement some strategy like keeping an incremental difference for each element of a diagram in a std::vector (limit it to 3/5 if objects are big) and call the renderer with the current statuses. I'm not an OpenGL expert, but I think it's the way it's done there. Actually you could 'steal' this strategy from game development best practices, or generally graphics related ones.

One of those strategies could be something like this:

A structure for efficient update, incremental redisplay and undo in graphical editors

Answers 6

The process you are after is called Serialization or Marshalling.

Boost has a very robust library called: Boost.Serialization

If You Enjoyed This, Take 5 Seconds To Share It

• Facebook
• Twitter
• Google+
• StumbleUpon
• Digg
• Delicious
• LinkedIn
• Reddit
• Technorati