Undo/Redo implementation

Give me some thoughts how to implement undo/redo functionality - like we have in text editors. What algorithms should I use and what I may read. thanks.

I know about two major divisions of the types of undo's

• SAVE STATE: One category of undo is where you actually save history states. In this case what happens is that at every point you keep on saving the state in some location of memory. When you want to do an undo, you just swap out the current state and swap in the state which was already there in the memory. This is how it is done with History in Adobe Photoshop or reopening closed tabs in Google Chrome, for example.

• GENERATE STATE: The other category is where instead of maintaining the states themselves, you just remember what the actions were. when you need to undo, you need to do a logical reverse of that particular action. For a simple example, when you do a Ctrl+B in some text editor that supports undo's, it is remembered as a Bold action. Now with each action is a mapping of its logical reverses. So, when you do a Ctrl+Z, it looks up from a inverse actions table and finds that the undo action is a Ctrl+B again. That is performed and you get your previous state. So, here your previous state was not stored in memory but generated when you needed it.

For text editors, generating the state this way is not too computation intensive but for programs like Adobe Photoshop, it might be too computationally intensive or just plain impossible. For example - for a Blur action, you will specify a de-Blur action, but that can never get you to the original state because the data is already lost. So, depending on the situation - possibility of a logical inverse action and the feasibility of it, you need to choose between these two broad categories, and then implement them the way you want. Ofcourse, it is possible to have a hybrid strategy that works for you.

Also, sometimes, like in Gmail, a time limited undo is possible because the action (sending the mail) is never done in the first place. So, you are not "undo"ing there, you are just "not doing" the action itself.

I have written two text editors from scratch, and they both employ a very primitive form of undo/redo functionality. By "primitive", I mean that the functionality was very easy to implement, but that it is uneconomical in very large files (say >> 10 MB). However, the system is very flexible; for instance, it supports unlimited levels of undo.

Basically, I define a structure like

type
  TUndoDataItem = record
    text: /array of/ string;
    selBegin: integer;
    selEnd: integer;
    scrollPos: TPoint;
  end;
  

and then define an array

var
  UndoData: array of TUndoDataItem;

Then each member of this array specifies a saved state of the text. Now, on each edit of the text (character key down, backspace down, delete key down, cut/paste, selection moved by mouse etc.), I (re)start a timer of (say) one second. When triggered, the timer saves the current state as a new member of the UndoData array.

On undo (Ctrl+Z), I restore the editor to the state UndoData[UndoLevel - 1] and decrease the UndoLevel by one. By default, UndoLevel is equal to the index of the last member of the UndoData array. On redo (Ctrl+Y or Shift+Ctrl+Z), I restore the editor to the state UndoData[UndoLevel + 1] and increase the UndoLevel by one. Of course, if the edit timer is triggered when UndoLevel is not equal to the length (minus one) of the UndoData array, I clear all items of this array after UndoLevel, as is common on the Microsoft Windows platform (but Emacs is better, if I recall correctly -- the disadvantage of the Microsoft Windows approach is that, if you undo a lot of changes and then accidentally edit the buffer, the previous content (that was undid) is permanently lost). You might want to skip this reduction of the array.

In a different type of program, for instance, an image editor, the same technique can be applied, but, of course, with a completely different UndoDataItem structure. A more advanced approach, which does not require as much memory, is to save only the changes between the undo levels (that is, instead of saving "alpha\nbeta\gamma" and "alpha\nbeta\ngamma\ndelta", you could save "alpha\nbeta\ngamma" and "ADD \ndelta", if you see what I mean). In very large files where each change is small compared to the file size, this will greatly decrease the memory usage of the undo data, but it is trickier to implement, and possibly more error-prone.

There are several ways to do this, but you could start looking at the Command pattern. Use a list of commands to move back (Undo) or forward (redo) through your actions. An example in C# can be found here.

A bit late, but here goes: You specifically refer to text editors, what follow explains an algorithm that can be adapted to whatever it is you are editing. The principle involved is to keep a list of actions/instructions that can be automated to recreate each change you made. Do not make changes to the original file (if not empty), keep it as a back-up.

Keep a forward-backward linked-list of changes you make to the original file. This list is saved intermittently to a temporary file, until the user actually Saves the changes: when this happens you apply the changes to a new file, copying the old one and simultaneously applying the changes; then rename the original file to a backup, and change the new file's name to the correct name. (You can either keep the saved change-list, or delete it and replace with a subsequent list of changes.)

Each node in the linked-list contain the following info:.

• type of change: you either insert data, or you delete data: to "change" data means a delete followed by an insert
• position in file: can be an offset or line/column-pair
• data buffer: this is the data involved with the action; if insert it is the data that was inserted; if delete, the data that was deleted.

To implement Undo, you work backward from the tail of the linked-list, using a 'current-node' pointer or index: where the change was insert, you do a delete but without updating the linked-list; and where it was a delete you insert the data from the data in the linked-list buffer. Do this for each 'Undo'-command from the user. Redo moves the 'current-node' pointer forward and executes the change as per the node. Should the user make a change to the code after undoing, delete all nodes after the'current-node' indicator to the tail, and set tail equal to the 'current-node' indicator. The user's new changes are then inserted after the tail. And that's about it.

My only two cents is that you would want to use two stacks to keep track of the operations. Every time the user performs some operations, your program should put those operations on a "performed" stack. When user want to undo those operations, simply pop operations from the "performed" stack to a "recall" stack. When user wants to redo those operations, pop items from "recall" stack and push them back to "performed" stack.

Hope it helps.

The Memento pattern was made for this.

Before implementing this yourself, note that this is quite common, and code already exist - For example, if you're coding in .Net, you can use IEditableObject, and in the javascript world, you can use immutable libraries like immer.js.

One way to implement a basic undo/redo feature is to use both the memento and command design patterns.

Memento aims at keeping the state of an object to be restored later for example. This memento should be as small as possible in an optimisation purpose.

The command pattern encapsulates in an object (a command) some instructions to execute when required.

Based on these two concepts you can write a basic undo/redo history, like the following one coded in TypeScript (extracted and adapted from the front-end library Interacto).

Such a history relies on two stacks:

• the stack for objects that can be undone
• the stack for objects that can be redone

Comments are provided within the algorithm. Just note that on an undo operation, the redo stack must be cleared! The reason is to let the application in a stable state: if you go back in past to redo some actions you made, your former actions will not exist any more as you change the future.

export class UndoHistory {
    /** The undoable objects. */
    private readonly undos: Array<Undoable>;

    /** The redoable objects. */
    private readonly redos: Array<Undoable>;

    /** The maximal number of undo. */
    private sizeMax: number;

    public constructor() {
        this.sizeMax = 0;
        this.undos = [];
        this.redos = [];
        this.sizeMax = 30;
    }

    /** Adds an undoable object to the collector. */
    public add(undoable: Undoable): void {
        if (this.sizeMax > 0) {
            // Cleaning the oldest undoable object
            if (this.undos.length === this.sizeMax) {
                this.undos.shift();
            }

            this.undos.push(undoable);
            // You must clear the redo stack!
            this.clearRedo();
        }
    }

    private clearRedo(): void {
        if (this.redos.length > 0) {
            this.redos.length = 0;
        }
    }

    /** Undoes the last undoable object. */
    public undo(): void {
        const undoable = this.undos.pop();
        if (undoable !== undefined) {
            undoable.undo();
            this.redos.push(undoable);
        }
    }

    /** Redoes the last undoable object. */
    public redo(): void {
        const undoable = this.redos.pop();
        if (undoable !== undefined) {
            undoable.redo();
            this.undos.push(undoable);
        }
    }
}

The Undoable interface is quite simple:

export interface Undoable {
    /** Undoes the command */
    undo(): void;
    /** Redoes the undone command */
    redo(): void;
}

You can now write undoable commands that operate on your application.

For example (still based on Interacto examples), you can write a command like this one:

export class ClearTextCmd implements Undoable {
   // The memento that saves the previous state of the text data
   private memento: string;

   public constructor(private text: TextData) {}
   
   // Executes the command
   public execute() void {
     // Creating the memento
     this.memento = this.text.text;
     // Applying the changes (in many 
     // cases do and redo are similar, but the memento creation)
     redo();
   }

   public undo(): void {
     this.text.text = this.memento;
   }

   public redo(): void {
     this.text.text = '';
   }
}

You can now execute and add the command to the UndoHistory instance:

const cmd = new ClearTextCmd(...);
//...
undoHistory.add(cmd);

Finally, you can bind an undo button (or a shortcut) to this history (same thing for redo).

Such examples are detailed on the Interacto documentation page.

Edit:

Note that there exists several undo/redo algorithms. I detailed the classic linear one. For code editors, researchers proposed the 'selective undo algorithm' (research article). Undo/redo algorithms for collaborative editing are also specific (research article).

If the actions are reversible. e.g Adding 1, make a player move etc see how to use the Command Pattern to implement undo/redo. Follow the link the you will find a detailed examples on how to do that.

If not, use Saved State as explained by @Lazer.

You may study an example of an existing undo/redo framework, the first Google hit is on codeplex (for .NET). I don't know if that is better or worse than any other framework, there are lots of them.

If your goal is to have undo/redo functionality in your application you might as well just pick an existing framework that looks suitable to your kind of application.
If you want to learn how to build your own undo/redo you can download the source code and have a look at both patterns and the details how to wire things up.