Implementing the undo / redo model for a complex document

Hi Habr! In this article I want to show how you can organize a model for editing a document with a complex structure with the possibility of undo / redo actions.

Background and Issues

It all started with the fact that I wrote a highly specialized outline-software, where the main idea is to operate a bunch of virtual paper cards on different scenes in different editors.

It turned out similar to MS Visio with a certain degree of customization and plaginization. There are no technical difficulties here, but there are a number of features.

First, there are several scenes. This means that window editors need several, each of which works by its own rules.

Secondly, because a set of cards is one, and the same card can be used in different places, this creates certain dependencies between different parts of the document. And, if the card is removed, then it entails the elimination of this card from all the places where it is involved.

Thirdly, when I did everything I wanted and showed the results to a friend (who is not even a programmer), he poked and said that it would be nice to do Ctrl + Z. I got an idea, but it turned out to be not such a trivial task. In this article I will describe what I came to in the end.

Existing solutions

Of course, before I did something of my own, I was hoping to find something ready. A sufficiently detailed analysis of the problems is given in Undo and Redo - analysis and implementation . However, as it turned out, in addition to general principles and words, it is difficult to find something like a library.

The first and most obvious solution is to make a version of the document for each change. Of course, it is reliable, but takes a lot of space and unnecessary operations. Therefore, this option was dropped immediately.

More interesting is the memento pattern . Here you can already save some resources by using the state of the document, and not the document itself. But this again, depends on the specific situation. And since I wrote everything in C ++, here I would not get any win. At the same time, there is even a C ++ template project undoredo-cpp that implements this pattern.

Command patter is basically what you need, but unfortunately, you can find only principles, but not universal implementations. Therefore, he was taken as a basis. And, of course, I wanted to achieve maximum performance, which resulted in minimizing data storage.

Thus, it became clear how and what I want to get at the implementation level. And it turned out to highlight specific goals:

1. The system contains a set of editors, each of which can edit its scene.
2. Any change to the document that will affect the open editor should be communicated to it, and the editor himself should respond to it as efficiently as possible (excluding the complete rebuilding of the document's scene).
3. All changes are global, i.e. Regardless which editor we are in now, the total change stack.
4. It must be possible to both undo the last action, and return (Undo / Redo).
5. The size of the change buffer should not be limited by anything except settings and hardware resources.

It should also be noted that everything was written in QT5 / C ++ 11.

Document model

The main essence on which actions are performed is a document . Various atomic actions can be applied to the document, let's call them primitives . Atomicity assumes that before and after the primitive application the document is in a consistent state.

In my document, I highlighted the following entities (it should be noted that my software was intended to outline the outline of the script, hence the specificity): card, character, story card (refers to the card), character card (refers to the card), point of the storyline (referenced to the card), storyline (contains a chain of story cards), etc. Thus, entities can refer to each other, and this can be a source of problems in the future if we want to return the action to create a story card that refers to y, the creation of which we have already rolled back. Those. It begs some mechanism for managing links, but about it later.

When allocating primitives, the following set is obtained: create a card, change the text of the card, delete the card, create a story card, create a storyline, change the text of the storyline, add a card to the storyline, etc. Conceptually, any primitive clearly refers to some to an entity, it means it makes sense to introduce a typification of primitives according to the addressed entity (card, storyline, character, etc.).

class outline_primitive { public: enum class entity_t { card, plot, act_break, outline_card, ...}; ... entity_t entity; document_t * pDoc; using ref_t = referenced_entity<outline_primitive>; std::vector<ref_t*> dependencies; }; 

Attention should be paid to the dependencies attribute - these are just the dependencies to which the primitive refers, but its purpose will be considered a little later. Also, primitives can be classified by type: creation; modification; deletion.

 enum class operation_t { create, modify, remove }; operation_t operation; 

At the same time, modifying primitives can generate a whole tree, depending on the permissible modifications - for example, move the card, add a card to the storyline, etc.

The primitive can be applied either in the forward direction or in the opposite direction. Moreover, for removing primitives and for assertions, it is useful to store in what state the primitive is applied or rolled back.

 virtual void outline_primitive::apply() { perform_check(!applied); applied = true; pDoc->unsavedChanges = true; } virtual void outline_primitive::revert() { perform_check(applied); applied = false; pDoc->unsavedChanges = true; } bool applied; 

Next, consider the implementation of the simplest primitive - adding a card.

Implementation of the simplest primitive

Something like this is the implementation of the card creation primitive. I will not give obvious routine operations, such as pDoc initialization, etc.

 class OUTLINE_DOC_API card_create_primitive : public outline_primitive { index_card * pCard; index_card::data_t cardData; //    card_create_primitive::card_create_primitive(const index_card::data_t & _data); void apply() { _Base::apply(); auto p_card = new index_card; //   p_card->data = cardData; pDoc->cards.push_back(p_card); //   pCard = p_card; //   } void revert() { _Base::revert(); auto it = std::find(pdoc->cards.begin(), pdoc->cards.end(), pCard); perform_check(it != pdoc->cards.end()); //assert pDoc->cards.erase(it); //    delete pCard; //    pCard = nullptr; //       } } 

Several assertions are specially added to the code, which confirm the consistent state of the document before and after the primitive has been applied.

Referential integrity

Now consider the primitive creation of a story card. In fact, this is the same card, but located on the plot sheet and having a coordinate. Those. it refers to the story card and contains additional attributes (coordinates).

Thus, suppose we have a sequence of primitives — create a card, create a story card based on it. Then the 2nd primitive must be referenced to the first one, while providing the possibility of updating the link if it is canceled and restored (with the associated deletion / re-creation of the card itself).

For this purpose, the special entity referenced_entity is introduced, which you have already met before in the list of dependencies.

 template<typename T> struct referenced_entity { using primitive_t = T; using entity_ptr = void; referenced_entity(primitive_t * prim, entity_ptr * p_ent) { ... prim->dependencies.push_back(this); //      } entity_ptr * get() const { if (!parent) return entity; else { auto cur_ref = this; while (cur_ref->parent) cur_ref = &(cur_ref->parent->baseEntity); return cur_ref->entity; } } primitive_t * parent; entity_ptr * entity; }; 

Here the important point is to place yourself in the list of dependencies of the primitive. Thus, if someone already refers to the contents of the referenced_entity, you can reconnect when the primitive is placed in the buffer, and then, based on this connection, get a pointer to the current address of the object using the get () method.

Primitive processing

To process the primitive, a special entity is introduced - command_buffer. Her tasks include:

• storing a sequence of primitives;
• providing reference links;
• direct and reverse application of primitives;
• tail garbage when exceeding the length;
• event generation

 class command_buffer { using primitive_id_sequence_t = std::vector<unsigned>; std::vector<primitive_t*> data; std::map<void*, primitive_id_sequence_t> front; }; 

Data stores primitives in the order in which they are created by the user. And in front - the so-called front reference objects. When a new primitive enters the buffer, it enters the last element of the object chain, which is stored in baseEntity. And then linking occurs.

 void command_buffer::submit(primitive_t * new_prim) { discard_horizon(); //      // ,   for (auto & dep : new_prim->dependencies) { auto front_it = front.find(dep->entity); if (front_it != front.end()) dep->reset_parent(data[*front_it->second.rbegin()]); } unsigned new_id = add_action(new_prim); //  data   //       if (new_prim->operation == primitive_t::operation_t::create) { new_prim->apply(pDoc); primitive_id_sequence_t new_seq; new_seq.push_back(new_id); front.insert(make_pair(new_prim->baseEntity.get(), new_seq)); } else //     - ,      { auto front_it = front.find(new_prim->baseEntity.get()); if (front_it == front.end()) { primitive_id_sequence_t new_seq; new_seq.push_back(new_id); front.insert(make_pair(new_prim->baseEntity.get(), new_seq)); new_prim->apply(pDoc); } else { auto & seq = front_it->second; perform_check(!seq.empty()); seq.push_back(new_id); new_prim->apply(pDoc); } } } 

All other buffer methods are fairly trivial, and they also contain undo () and redo (). Thus, command_buffer provides a consistent state of the document, and the question remains how to maintain the correct state of presentation, formed by the relevant editors.

Interaction model

To do this, you must enter a new entity - the event, and each open editor must correctly respond to the appropriate type of event. The event is associated with the use of a primitive - before application, after application, before rollback, after rollback. For example, after applying, you can make a reaction to the creation primitives (since there is still no object before using the object), before rolling back - to the same creation primitives, since after the rollback, the link will be lost.

 template<typename T> struct primitive_event { using primitive_t = T; enum class kind_t {pre_applied, post_applied, pre_reverted, post_reverted}; kind_t kind; primitive_t * primitive; }; 

These are the events that will be sent after each of the 4x operations on the primitive. Accordingly, in each editor, you need to make a handler that will react to these events, and, accordingly, miniaturely rebuild the scene.

 void my_editor::event_occured(event_t * event) { switch..case } 

Here you need to make a three-story switch..case in essence, operation and event, and it looks awful. To do this, use the trick, based on the fact that each of the elements can be converted to an integer, and we introduce such a macro.

 #define PRIMITIVE_EVENT_ID(entity, operation, event) ((unsigned char)entity << 16) | ((unsigned char)operation << 8) | (unsigned char)event 

Then the body of this method will take this form, and it will be possible to add it as new primitives appear, without detriment to the convenience of perception.

 switch (PRIMITIVE_EVENT_ID(event->primitive->entity, event->primitive->operation, event->kind)) { case PRIMITIVE_EVENT_ID(outline_primitive::entity_t::collision, outline_primitive::operation_t::create, event_t::kind_t::post_applied): case PRIMITIVE_EVENT_ID(outline_primitive::entity_t::collision, outline_primitive::operation_t::remove, event_t::kind_t::post_reverted): { auto p_collision = static_cast<collision_t*>(event->primitive->baseEntity.get()); pScene->create_image(p_collision); break; } ... } 

True, it should be noted that if the hierarchy of types of the modifying primitive grows for some entity, then inside it is necessary to make new branches.

And it really works.

The described method is not limited to my document model, and can be used in various document models. If someone is interested to see this in action, then the compiled application itself can be downloaded on the ultra_outliner page.

Conclusion

In the framework of the proposed method, one important issue remained unexplored. Most user actions on documents are indeed atomic, but some of them produce several primitives at once. For example, if a user moves a card, this is one primitive. And if he removes a card that is in 3 ways - then these are 3 primitives for excluding the card from the circuit, removing the card from the field, and then removing the card itself. If such a chain is rolled back, then only one primitive will be rolled out in one rollback operation, while it would be logical to roll back everything at once. This requires some refinement of the method, but we will consider this problem in the next article.