A Simple Undo System

Overview

This write-up describes a simple, practical implementation of an undo system for tools and applications. Although this technique is not applicable to all software, for cases where it is (such as small tools), it can be applied trivially with very little change to the existing code and overall project structure.

The undo system is based around calling a single function before potentially modifying any block of data. At the end of the user interaction a "commit" function is called which checks each block of data for differences with its pre-commit state and pushes the old data to the undo stack for any of these differences.

As the system works by marking data which may change before it has changed, the approach lends itself well to immediate mode UIs where there may be no indicator that a value will change before it does, nor a convenient way of retrieving its previous value after it has changed.

Usage

The main loop of a simple program which edits the content of a small bitmap may look as follows:

for (;;) {
  handle_events();

  if (mouse.is_pressed) {
    set_pixel(bitmap, mouse.x, mouse.y);
  }

  draw();
}

Undo/redo support could then be added with the simple addition of two lines of code:

for (;;) {
  handle_events();

  if (mouse.is_pressed) {
    undo_push(bitmap, sizeof(bitmap))
    set_pixel(bitmap, mouse.x, mouse.y);
  }

  if (!mouse.is_pressed) { undo_commit(); }

  draw();
}

Any change made to the bitmap would then be tracked by the undo system, calls to the undo system's undo_undo() and undo_redo() functions would undo and redo the user's actions as expected.

Several blocks of memory can be passed to the undo system by calling undo_push() on each block which may change. In a situation where our bitmap is large it may be more practical to call undo_push() on each region of potential-change as opposed to the entire bitmap. This reduces the amount of work the undo system has to do in detecting changes:

void set_pixel(unsigned *bitmap, int x, int y) {
  unsigned *p = &bitmap[x + y * WIDTH];
  undo_push(p, sizeof(*p));
  *p = 0xff00ff;
}

Alternatively the region could be an entire pixel-row instead of a single pixel, or several rows, depending on the operation being performed.

Note that in all cases only the changes are pushed to the resultant undo stack after undo_commit() is called. The block of data passed to undo_push() is kept only until undo_commit() is called.

The application of this approach to undo isn't limited to bitmaps. For example, if you have a fixed buffer of game-objects, commands or other items, the fixed buffers could be passed to undo_push(), or — if the buffers are large — individual items in the buffers could be passed before changes are made to those items:

undo_push(object, sizeof(*object));
object->x = 10;
object->y = 20;

Implementation

Internally the implementation stores 3 stacks:

• undo — Stores changes that can be undone
• redo — Stores undone changes which can be redone
• temp — Stores copies of all blocks of data passed to undo_push since the last commit

Each stack stores a series of items — a single item consists of the following parts which are pushed to the stack in order (and thus popped from the stack in the reverse order):

• data — Copy of the data before it was modified
• pointer — Pointer to the data's location in memory
• size — Size in bytes of the data

The undo_push() function takes a pointer and size value. When it is called the temp stack is first scanned to check if we already have an item for the given data block — if so the function already has the old-data for this commit and can return without doing anything. Otherwise — if the data is not on the temp stack — we push an item for the given pointer and size: pushing the data at the pointer, the pointer itself and finally the size of the data block.

When undo_commit() is called each item is popped from the temp stack and the stored data is compared to the current data at the item's pointer. Any differences are pushed as items to the undo stack. When the first change is encountered the redo stack is reset and a null item is pushed to the undo stack — this item is used to indicate the beginning of this commit.

When undo_undo() is called each item on the undo stack is popped until the null item is reached. The data stored for each item is pushed to the redo stack so that it can be redone and the item's data is copied to the location of the item's stored pointer such as to restore its old state.

The implementation of undo_redo() is identical to that of undo_undo() but with the roles of the undo and redo stacks swapped.

To deal with running out of memory on the undo stack the stack's push operation can be implemented such that the content at the beginning of the stack is discarded by shifting the entire stack's content if it does not have enough space for the pushed item. In undo_undo() a scan of the undo stack can be performed to check for the existence of a null item as to ensure a full commit exists before the undo operation is attempted.