I've been learning a little about the history of the XtraRichEdit control this week, and I wanted to share a development story with you all. :-)
Undo and redo are such simple and familiar features in any text and graphics editor that you'd think they'd be easy to implement. We thought so, too, when we first set out to develop the feature for our XtraRichEdit control. So, what's the approach we took?
Well, first, it's obvious that there needs to be an object that holds a history of the changes. It should contain a list of the actions, with enough information to undo or redo each action. Since actions can be very different (inserting text, changing fonts) we decided right away that our object should not only hold all the data necessary to undo and redo, but actually be responsible for implementing them:
public abstract class HistoryItem {
public abstract void Undo (Document document);
public abstract void Redo (Document document);
}
Our first basic prototype of the code looked like this:
public class History {
ReadOnly <HistoryItem> List 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);}
}
Diving in first to the Undo method:
public void Undo () {
items[items.Count - 1 ].Undo(document);
}
Looks good, right? Succinct and elegant… and wrong. For starters, when you call the Undo method for an empty list, we get an exception. So we fix that:
public bool CanUndo { get { return items.Count > 0 ;}}
public void Undo() {
if (!CanUndo) return ;
items[items.Count - 1 ].Undo(document);
}
Now, the issue is that if we call the Undo method several times in a row, it'll repeatedly try to Undo the last item in the list. So we remove the most recent item, and we're good to go:
public void Undo () {
if (!CanUndo) return ;
items[items.Count - 1 ].Undo(document);
items.RemoveAt(items.Count - 1 );
}
So, let's consider Redo:
public void Redo () {
if (!CanRedo) return ;
// ???
}
Oops! Our implementation of Undo means that we've lost the change we now need to redo. Instead, we need an index indicating the current item in the clipboard. So, we rewrite again:
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++;}
That's much better. Note that now, for an Undo, the index changes *after* the rollback; and for a Redo, it changes *before* the roll forward. We also correctly increment the index when we add an item in the history.
Now, let's take a closer look at the Add method. What if we perform 5 actions, roll back 3 of them, and then perform a new action? Looking around, we determine that the Undo/Redo standard here is to drop everything that has happened after the current index, and to instead begin a new history.
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, we have our Undo/Redo implementation. The original intention was:
- Perform an action;
- Record said action into the history, so that we're able to undo/redo later;
However, we decided we wanted our undo history not only to store what was undone, but actually to be able to redo the operation independently. In other words:
- Create an undo element, and add it to the history for potential undoing and redoing later;
- Perform redo for the history item, like so:
void DoAction() {
HistoryItem item = CreateActionHistoryItem();
document.History.Add(item);
item.Redo(document);
}
This works fabulously. We can redo an action from the current state, or undo an action from the current state, and it is possible to step through the history in either direction to affect the current state. By "state". I mean that the information recorded in the history is correct when it's saved, but it may change a moment later. For example, if we have "Hello World!":
Now, let's insert DevExpress in the middle; which means we record "insert DevExpress at position 6" into the history:
Next, we'll insert "We say:" at the beginning:
But, now our previous information about inserting DevExpress is incorrect. If we call undo at this point in the history, we'd invalidate the document. We have to recalculate the index to get the correct undo information. However, it's not necessary to recalculate. We can avoid it, by assuming that cancelling every operation before the relevant one leads the document to the state that it had at the beginning of the operation. We'd make the same assumption for redo, also. The information in the undo history will automatically become correct when the document arrives at the initial state (where the information was saved). As the redo operation occurs in the reverse order, we cannot use the information before the document is presented in the necessary state. Thus, we automatically handle the undo and redo correctly.
These were just our initial observations here at DevExpress. In the real world, things might be a little different. ;)
As a side note: While writing this, I wondered who first implemented undo and redo (and when). Apparently, it was between 1971 and 1976. Modern manuals of ed argue that it supports undo; the first manuals for UNIX (1971) do not include undo; but vi (first published 1976) contains it from the start. The term itself was first mentioned in 1976: "It would be quite useful, to permit users to ‘take back’ at least the immediately preceding command (by issuing some special ‘undo’ command).” (Lance A. Miller and John C. Thomas of I.B.M., “Behavioral Issues in the Use of Interactive Systems.”) See related article in the NY Times.