Undo / Redo - Tail wags the dog

In this article, we will continue to talk about how we did Undo / Redo in the XtraRichEdit text editor.

It all started with the fact that our team gave the source code of the text editor concept with the wish to bring this concept to mind. Despite the fact that only a month was spent on developing the concept, he knew a lot: you could enter and delete text, move the cursor horizontally and vertically.

It remained for us to add the possibility of formatting sections of text (font, its size, etc.) and all the other “trifles” such as paragraphs with all their properties, styles, etc. And the concept did not know how to do Undo / Redo.

During the two weeks that I had to delve into the sources of the concept, it finally became clear that the only way to tie Undo / Redo to it without rewriting it from scratch is to save the entire document state for every action:
')

public class DocumentHistoryItem : HistoryItem { readonly DocumentState previousState; readonly DocumentState nextState; public DocumentHistoryItem(DocumentState previousState, DocumentState nextState) { this.previousState = previousState; this.nextState = nextState; } public override void Undo(Document document) { document.ApplyState(previousState); } public override void Redo(Document document) { document.ApplyState(nextState); } } 

This, of course, was unacceptable, because this approach would use too much memory. Imagine a document of at least 1 megabyte. The task for the second-grader: how many keys must be pressed before the memory runs out, if each keystroke leads to a change in the document and entry in the undo buffer?

Why couldn’t it be possible to screw Undo / Redo in a more acceptable way? The fact is that when they developed the concept, they did not initially take into account the future implementation of Undo / Redo. All text operations were implemented in such a way that performing the reverse operation was rather problematic. Moreover, the very organization of storing text and the properties of its individual sections (font, text size, etc.) turned out to be extremely inconvenient for implementing Undo / Redo. For each operation, it was necessary to save a fairly large amount of data.

For example, it was not difficult to save data on changing the font name. For this, it was necessary to save the old and new font name in order to be able to both undo and redo actions. Similarly, for the font size - it was necessary to keep the old and new sizes. However, if the name of the font and its size were changed in one action (for example, in the Font dialog), then it was necessary to save 2 elements in the undo buffer. But apart from the actual name of the font and its size, it was necessary to store information to which part of the text these values ​​should be applied.

In the end, having made several unsuccessful attempts to integrate Undo / Redo into the existing code, we came to the conclusion: in order to avoid problems with Undo / Redo, it is necessary to redesign data structures and algorithms in a special way.

It was decided that every user action on the document should be transformed into a sequence of elementary operations on the document. Each such operation must be so elementary that it could be very easy for it to implement the inverse operation. Such an operation also stores the minimum necessary amount of data necessary for its direct and reverse execution. Elementary operations are packed into a single composite element and placed in an undo buffer:

 public class CompositeHistoryItem : HistoryItem { readonly List<HistoryItem> items = new List<HistoryItem>(); public void AddItem(HistoryItem item) { items.Add(item); } protected override void UndoCore() { for (int i = items.Count - 1; i >= 0; i--) items[i].Undo(); } protected override void RedoCore() { int count = items.Count; for (int i = 0; i < count; i++) items[i].Redo(); } } 

Note that the rollback of the elements of a composite operation is performed in the reverse order, and the roll forward is performed in the direct order.

In order to break down actions into elementary operations, we had to organize data structures in a special way. We divided the text inside paragraphs into intervals so that the formatting of the text inside each interval was the same.



When changing the formatting of an arbitrary selected text, the text was first divided into intervals according to the selection, and then the formatting of those intervals that were inside the selection was changed. Thus, 3 elementary operations “split interval”, “merge 2 neighboring intervals” and “change interval formatting” were selected.

The last elementary operation deserves separate consideration. To minimize the amount of data stored in the undo buffer, the object containing the text properties in the interval was divided into two sub-objects: variable (CharacterFormattingBase) and immutable (CharacterFormattingInfo). Immutable objects were stored in the cache-list (CharacterFormattingInfoCache), and the elements of the list were unique and were never removed from the list. Editable objects stored only an index of the immutable object in the list.



This allowed changing any property (or several properties at once, this is a matter of technology) of a variable object to be reduced to searching the index cache for a suitable immutable object and storing it in the variable object. If a suitable object could not be found, then it was created and added to the cache.

Using this approach, we achieved only 2 indices, old and new, in the undo buffer to change any number of interval properties (of course, within a single transaction).

At first glance, it seems that the ever-growing cache makes irrational use of memory. But in reality it is not. The fact is that there are not so many different combinations of text properties in real documents. Moreover, most of the text, as a rule, has the same formatting. And instead of duplicating all the values ​​of the properties responsible for formatting in each interval, we duplicate only the index of a single object in the cache.

And finally, consider an example of an action and its division into elementary operations.

Initially there is a solid and only part of the text:



Bold out some of the text "Wor".

This action can be divided into 3 elementary operations:

We divide the text section into 2 adjacent sections.



We divide the right part of the text into 2 more sections.



For the section with index 1, we use bold typeface.



Each of the operations is extremely simple, easily reversible and stores a minimum of data. So, for the operation of cutting a section of text, it is enough to keep the index of the section being cut and the index of the letter on the section before which the section will occur. The operation of applying the font style saves the number of a section of the text (run index), as well as the old and new indices of CharacterFormattingInfo objects in the cache.

It turns out that Undo / Redo dictates us how best to organize data. Namely: the text should be divided into sections so that the entire text of one section had strictly the same formatting. Parcels must be numbered. It is with this organization of the data that a natural and simple splitting of the action into elementary operations is achieved. And this, in turn, leads to a simplified implementation of Undo / Redo and minimizes the amount of data that needs to be stored.

When developing XtraRichEdit, we initially began to use the “from Undo / Redo” approach. When designing each action, we first of all thought through how to put this action into the Undo / Redo concept, what elementary operations to break it into, and how to get by with the minimum amount of data stored in the memory. This allowed us to create a simple document model in implementation that uses memory efficiently and does not require significant computational resources both when traversing the model during document formatting and when making a variety of changes to it.

Previous article on this topic | Next article on this topic