Implementing a robust persistent undo/redo feature

Question

I'm writing a bitmap editor where I use the Command Pattern to represent actions that will transform the document. I keep all the commands executed so far in a list and, to implement undo, I restore the document to its initial state and then replay all but the last command.

I would like my undo/redo system to have the following feature: When the user closes the editor and returns, the document, including the available undo and redo commands, should be restored to the state it was in when the user left.

I'm implementing this for Android where your application can be given very little notice before it will be cleared from memory if e.g. the user gets a phone call. Also, some of my commands are e.g. a list of all the x,y co-ord the user painted on so these might take a few moments to save to disk.

My current idea is as follows:

1. When a new action is performed, the command object is added to a list S for commands that need to be saved to disk.
2. A background thread is used that will continually take commands from list S and save them to disk. The postfix of the filenames used will be numbered in sequence. For example, if the user filled the screen then drew 2 circles, the command files might be called FillCommand1.cmd, DrawCircleCommand2.cmd, DrawCircleCommand3.cmd.
3. Periodically, we save a "checkpoint" command whose purpose is to store the full document state so that, even if one of the .cmd files is corrupted, we can restore a recent version of the document.
4. When the user exits the app, the background thread attempts to finish up saving all the commands it can (but it might get killed).
5. On startup, we look for the most recent .cmd file that represents a checkpoint that we can load successfully. All the .cmd files we can load after this (i.e. some files might be corrupt) go in the redo command list, all the .cmd files we can load between the first checkpoint loaded and the oldest checkpoint we can load go in the undo list.

I want the undo limit to be about 20 or 30 commands back so I need extra logic for discarding commands, deleting .cmd files and I've got to worry about multi-threading behaviour. This system seems pretty complex and will need a lot of testing to make sure it doesn't go wrong.

Is there anything in Java or Android than can help make this easier? Am I reinventing the wheel anywhere? Maybe a database would be better?

Answer 1

Well, your code is probably imperative in nature, where the state of the application is modified in place by the user's actions. This is probably fast and straightforward. Undo is basically time-travel and if you clobber old states by modifying state in place you will have to store either recipes to recompute it in reverse, or a history that can recompute it forwards.

Like you said, you can store the actions and the initial state and play them forward (stopping at the new point in history the user selects) but that means undoing one action can cause n actions to replay. One approach is to store saved state copies in the history list so you can immediately jump to a given state. To avoid using too much RAM/storage you if your system is clever it can detect the nearest (non-null) saved state in the history and recompute those few stpes forward (assuming you have all the actions you need -- this assumes actions are small and state is large(r)) until the correct state is reached. In this manner you can start eliminating old saved states (delete or set to null) (drop the state based on a cost function inversely linear to how far back in time the state is), making undo fast for the recent past, and memory/storage efficient for ancient history. I've had success with this method.

Answer 2

Rather than reverting to the original then performing all actions, consider making Commands reversible. That way, if you ever decide to increase the size of your undo history, you won't be introducing the potential for lag while undoing. Alternatively, as Jared Updike notes, your application may benefit from caching render results in the near past and future.

I think you're overcomplicating things with your filesystem-based solution. If you want to maintain a backup of the entire history of current working document, you should just keep an unbuffered log open in append mode, and log actions to it. The log should be associated with the particular instance of the application and file being edited, so you don't have to worry about another thread stepping on your toes. Loading from that log should be very similar to loading from an ordinary save file. Just discarding the last-read action whenever you encounter an undo action.