Wednesday, February 2, 2011

Implementing Undo the Simple Way

Over the years I have implemented all kinds of undos for the editors and tools I have made. I have tried all kinds of ways, ranging from storing delta information to abstract command class that can undo redo itself. There is one kind, though, that is by far my favorite:

class Document ()
{
static int MAX_UNDO = 10;
struct UndoState
{
String cmd;
String path;
};
UndoState m_undoStack[MAX_UNDO];

int m_undoHead = 0; // Current state.
int m_undoTip = 0; // The highest state that is set.
}

// Adds undo state to the undo stack.
Document:: addUndoState(String cmd, String path)
{
// This kills all the states after the current one
m_undoTip = m_undoHead+1;
// Buffer getting full, shift down.
if (m_undoTip >= MAX_UNDO) {
for (int i = 0; i < MAX_UNDO-1; ++i)
m_undoStack[i] = m_undoStack[i+1];
m_undoTip--;
}
// Store state
m_undoHead = m_undoTip;
m_undoStack[m_undoTip].cmd = cmd;
m_undoStack[m_undoTip].path = path;
}

// Takes snapshot of the document.
Document::snapshot(String cmd)
{
String path = getTempFileName();
ZipWriter zip;
saveState(&zip);
zip.save(path);
addUndoState(cmd, path);
}

// Returns true if can undo.
Document::canUndo()
{
return m_undoHead > 0;
}

// Returns true if can redo.
Document::canRedo()
{
return m_undoHead < m_undoTip;
}

// Reverts to previous state of the document.
Document::undo()
{
if (!canUndo()) return;
m_undoHead--;

ZipReader zip;
zip.load(m_undoStack[m_undoHead].path);
loadState(&zip);
}

// Advances to next state of the document.
Document::redo()
{
if (!canRedo()) return;
m_undoHead++;

ZipReader zip;
zip.load(m_undoStack[m_undoHead].path);
loadState(&zip);
}

// Saves document state.
Document::saveState(Writer* out)
{
// Save document state
...
}

// Loads document state.
Document::loadState(Reader* in)
{
// Load document state
...
}

13 comments:

  1. Note that you may wish to save Editor state as well (current selection, current window, current copy/cut, etc).
    Best do that in a second file and separate state unless document state is willing to be polluted by eidtor state info.

    Did you ever tried "Diff" incremental save states, if yes, why didn't it made it to the top ?

    ReplyDelete
  2. Document above means all the state you would like to save, that could be selection too, basically anything that you may wish to revert when you press that undo button. I think cut/copy and window settings should not be undone and should be save to a settings file instead.

    Storing the undo as a binary diff is good idea to save space. Otherwise doing diffs manually get super complicated and error prone really quickly. That is usually because of dependencies.

    For example removing a waypoint from waypoint graph requires me to store not just the waypoint which was removed, but also all the other waypoints which were affected by the remove (links removed).

    For the sake of simplicity these waypoints may have been stored into an array. Removing a waypoint might change the index order, which is simple to patch by looping through all the links, but it is really nasty to build undo data for that. So a slightly sloppy implementation removing a waypoint makes the whole undo process super complicated to track and very error prone.

    Unless you are dealing with huge amounts of data, the above method allows a super simple way to implement undo, you can often retro fit it too to existing systems.

    If the undo is too cumbersome to implement, it will be the last thing to add (if at all!). I'd rather have slightly slow undo from day one than no undo at all.

    If your data has clear separations, say a waypoint graph and a light rig, it is of course possible to store revisions of each sub-system, and just store and restore the one that was changed.

    ReplyDelete
  3. I successfully used a command pattern (I think it's named that way) a couple years ago to implement undo/redo it works pretty good.

    The idea is to represent each action you can perform on a document as an object that can be applied to the document or unapplied. In some cases the action can be simply unapplied (removing a node from a graph is fairly simple), in other cases you save the state of the document the way you're doing it here.

    Youre way works fine but saves unecessary states of the document i think.

    ReplyDelete
  4. @Cloderic, that would be the "abstract command class that can undo redo itself".

    ReplyDelete
  5. I have used command classes in the past too. For example Maya uses them.

    My example of node removing required to potentially touch the whole graph, in which case it would have been just easier to store the whole graph rather than one node and complicated undo data.

    This method definitely saves unnecessary state. This is a case where I'm willing to sacrifice (on disk) memory and some processing power to get simpler and easier to maintain implementation.

    It is the bubble-sort of undos :)

    ReplyDelete
  6. Won't this system get awfully slow when everytime you undo you basically reload your entire application state?

    (The speed issue which, incidentally, matches your "the bubble-sort of undos" description :))

    ReplyDelete
  7. It totally depends what you edit. For example if you edit a game level, you might not get any problem at all. Most of the memory consuming data like sounds, textures and meshes are usually just referred. So you are practically just saving and loading "handles" to that data.

    Further as I explained earlier, you can split saving into chunks (i.e. each game system, streaming sections) and just save the chunk that changed. If you want to be really smart, there is a lot to learn from functional programming, where "all data is read only".

    If disk writes becomes bottleneck, just keep as many compressed undos as you can in memory.

    It is very rude way of doing undo.

    ReplyDelete
  8. Good point!

    It may be rude, but an interesting benefit is that it also allows more or less uninterrupted work after a crash, since you can just load the last state and continue working.

    ReplyDelete
  9. There is a lot to be said for storing revisions in general, of which undo is a very common subset, as snapshots instead of streams of commands. As Mikko points out the most common problem isn't usually size taken by the snapshots but the engineering time it takes to create a working command based design.

    If you are really concerned about storage there are plenty of research into binary diff algorithms, many that will probably be very close in compression ratio to a hand rolled solution. An interesting one is a paper by Bentley and McIlroy titled "Data Compression Using Long Common Strings". This is algorithm is extremely efficient at compression large datasets with only minor variations between them, exactly what you would see with a stream of editor states. One implementation called BMDiff is used by Bigtable to compress data between cells that only change slightly.

    ReplyDelete
  10. boost::function0 is key for success for me for all undo/redo operations

    m_manager_undo.exec("Rotation",
    boost::bind(CCore::cmd_set_selection_state, m_selected_entities),
    boost::bind(CCore::cmd_set_selection_state, old_state));

    ReplyDelete
  11. Yakov has a point there. If your code is already sub-routinized enough, and organized in a way there is a reverse way for each call, then storing two functions for each user action should do the trick. Keeping in mind that only direct user actions are concerned here, so it involve only a small subset of your functions.

    ReplyDelete
  12. As I mentioned earlier, I have used that model many many times in the past.

    I have noticed that at some point things break apart. Sometimes it is because you need to do things in a rush, or sometimes it is because the undo operation becomes really complicated (because the change has a lot of dependencies).

    My point was to explain the simplest possible undo which works, is super simple to implement and can tolerate quickly hacked together edit operations.

    ReplyDelete
  13. Love it. Simple solutions!

    Abstract commands are just an architecture, though, they don't have fixed semantics. You could, for example, implement a command to do its undo by saving the document to a temp file, exactly as you have above. So you can have some commands that can do local surgery, but at the inevitable point where something is too complex to be worth implementing as surgical changes, you can dump the document. The point about abstract commands is that they are general, and not tied to implementation.

    ReplyDelete