Undo / Redo - The Illusion of Simplicity

Such a simple and familiar function in any text and graphic editor. It would seem that what could be the difficulty with its implementation? When we first faced with the development of Undo / Redo for the text editor XtraRichEdit , we thought about it, and what approach should we take?



It was obvious that there must be some kind of object responsible for the change history. This object should contain a list of items representing individual actions. Each such element must store enough information to undo the action (Undo), as well as repeat it (Redo).

Since actions can be very different (inserting text, changing the font, adding a red line to a paragraph), we immediately decided that the elements of the Undo buffer would not only store all the necessary data for undo / redo operations, but would also be responsible for performing undo repeat:
')

public abstract class HistoryItem { public abstract void Undo(Document document); public abstract void Redo(Document document); } 

The first class prototype for the Undo buffer was as follows:

 public class History { readonly List<HistoryItem> items = new List<HistoryItem>(); public History(Document document) { this.document = document; } public void Undo() { } public void Redo() { } public void Add(HistoryItem item) { items.Add(item); } } 

Hands and stretch to write the Undo method:

 public void Undo() { items[items.Count - 1].Undo(document); } 

Laconic, elegant ... but completely wrong.

To begin with, when you try to call the Undo method when the list is empty, an exception will be thrown. We fix:

 public bool CanUndo { get { return items.Count > 0; } } public void Undo() { if (!CanUndo) return; items[items.Count - 1].Undo(document); } 

And again we get the wrong code. After all, if you call the Undo method several times in a row, then it will be called Undo time after time for the last item in the list, which is wrong. Make changes:

 public void Undo() { if (!CanUndo) return; items[items.Count - 1].Undo(document); items.RemoveAt(items.Count - 1); } 

Now everything is fine. Well, it's time to get redo. Nothing complicated ...

 public void Redo() { if (!CanRedo) return; // ??? } 

Oops! We arrived.
In our implementation of Undo, we are irretrievably losing rolled elements in the rollback process, so there is no one to do Redo. We'll have to start an index pointing to the current item in the clipboard. So:

 int currentIndex = -1; public bool CanUndo { get { return currentIndex >= 0; } } public bool CanRedo { get { return items.Count > 0 && currentIndex < items.Count - 1; } } public void Undo() { if (!CanUndo) return; items[currentIndex].Undo(document); this.currentIndex--; } public void Redo() { if (!CanRedo) return; this.currentIndex++; items[currentIndex].Redo(document); } public void Add(HistoryItem item) { items.Add(item); this.currentIndex++; } 

Already better, at least it looks like something workable. Note that in the case of Undo, the index changes after a rollback, and in the case of Redo, it changes before rolling. We also remember to increment the index when adding an item to the history.

And now let's look carefully at the Add method and ask ourselves how it will behave if we have completed and recorded 5 actions in history, then rolled back 3 of them and are going to perform a new action? After thinking and seeing how it was done from others (everything is already stolen before us), we conclude that in this case, that part of the action history that is after the current index should be lost, and instead of it new actions will start to be recorded:

 public void Add(HistoryItem item) { CutOffHistory(); items.Add(item); this.currentIndex++; } void CutOffHistory() { int index = currentIndex + 1; if (index < Count) items.RemoveRange(index, Count - index); } 

Now, finally, the simplest implementation of Undo / Redo has become operational.

Let's think about how we will use it. First of all, such a sequence of actions climbs into the head:

1. Perform the action;
2. Bring information about this action into the undo buffer for further rollback / retry.

But at the very beginning, we decided that the undo-buffer elements are capable of not only storing the necessary data, but also independently perform the necessary rollback / repeat operations. And what is the replay operation? This is its direct execution from the current state. Those. to perform any operation, you can do so:

1. Create an undo buffer element, and put it in the undo buffer for further rollback / repeat;
2. Perform Redo for this item:

 void DoAction() { HistoryItem item = CreateActionHistoryItem(); document.History.Add(item); item.Redo(document); } 

It turned out elegant and beautiful. The first execution of an action is Redo of this action from the current state. Rollback - undo from the current state. Repeat - rerun the operation from its current state.

In the last sentences we have used the word state several times. The fact is that the information that is stored in the undo buffer is quite correct at the moment of saving. However, at the next moment it may become incorrect. The simplest example. We have the text “Hello World!”.



We perform the insert operation of the “DevExpress” text before the word “World”. At the same time, we will place the information in the undo buffer that the text “DevExpress” was inserted into the position with index 6 (starting with 0).



Perform the following action: insert the line “We say:” at the beginning of the text. Of course, after this action, information about the position where you need to insert the string “DevExpress” will become incorrect.



If at this moment call Undo for the first operation, then the contents of the document will be corrupted. For the information to be correct, it is necessary to recalculate.

Is it possible in some case to do without recalculation? Of course, it is possible, if we assume that the rollback of each operation leads the document to exactly the state it had at the time of the operation. A similar requirement should be imposed on the repetition of the operation.

In this, it turns out that the information in the undo buffer automatically "becomes" correct as soon as the document arrives in the original state in which this information was stored. If the state is different from the original, then this information is generally incorrect and cannot be used. And since operations are rolled back in the reverse order of their execution, we will never be able to use the information until the document is reset.

These are some of the considerations you can use when implementing a simple Undo / Redo manager for your own text or graphic editor. However, in life everything happens a little differently, as we will tell you in the next article .

But the link to the extreme article on the same topic.

PS:
In the process of writing this article, we became interested, and when did such a useful thing appear as Undo?

Carefully googling, came to the conclusion that it happened somewhere in the period from 1971 to 1976. So, modern ed ed manuals claim that it supports undo. However, in the manual from the first Unix for 1971 there is no mention of Undo yet. But in the vi editor, the first version of which was released in 1976, Undo seemed to be originally.

The term undo itself was mentioned, possibly for the first time, also in 1976: “It wasn’t been very much the case” (by issuing some special und undo command command). ”(Lance A Miller and John C. Thomas of IBM, “Behavioral Issues in the Use of Interactive Systems.”) (See NY Times Magazine, 5th paragraph).