Implementing undo/redo with the Command Pattern
This article is about implementing undo/redo functionality by utilizing the command pattern and assumes you know how the command pattern works (for a refresher on the command pattern you might take a look at this). To summarize, the command pattern is about representing and encapsulating all information that is needed to execute an action at a later time. Usually a command is an object that provides an interface execute(), which wraps the execution of the desired action.
At first I’ll describe the basic principle of how undo/redo functionality can be implemented based on a minimal code example. Afterwards i’ll tell you about some of the problems that can arise if this approach is used for complex applications.
We want to make commands undo-/redoable - the basic idea is the following:
- We add undo() and redo() to our command interface, so every command has to implement this methods.
- We maintain two stacks, one for for commands available for undo and one for commands available for redo.
- When a command is executed, we add the executed command to the undo stack and clear the redo stack. execute() stores the “original” state of the object that is changed inside the command object, before changing it.
- When doing an undo, we take the top command from the undo stack and execute its undo() what restores the “original” state. The undone command is pushed to the redoStack().
- When doing a redo, we take the top command from the redo stack and execute its redo() what restores the “new” state. The redone command is added to the undoStack().
A simple undo/redo demo
Let’s take a look at a demonstration program: We have a TV that can be turned on and off and switch channels. The corresponding commands are TvOnCommand, TvOffCommand and TvSwitchChannelCommand. The CommandManager handles the execution of the commands and manages the undo and redo stack:
#include <stack>
#include <iostream>
#include <memory>
// ----- the Command Interface -----
class ICommand {
public:
virtual void execute() = 0;
virtual void undo() = 0;
virtual void redo() = 0;
};
// ----- the MODEL -----
class Tv {
bool mOn;
int mChannel;
public:
Tv() {}
void switchOn() { mOn = true; }
void switchOff() { mOn = false; }
void switchChannel(int channel) {
mChannel = channel;
}
bool isOn() { return mOn; }
int getChannel() { return mChannel; }
};
// ----- concrete ICommand commands -----
class TvOnCommand : public ICommand {
Tv *mTv;
public:
TvOnCommand(Tv &tv):mTv(&tv) {}
void execute() { mTv->switchOn(); }
void undo() { mTv->switchOff();}
void redo() { mTv->switchOn(); }
};
class TvOffCommand : public ICommand {
TvOnCommand mTvOnCommand; // reuse complementary command
public:
TvOffCommand(Tv &tv):mTvOnCommand(tv) {}
void execute() { mTvOnCommand.undo(); }
void undo() { mTvOnCommand.execute(); }
void redo() { mTvOnCommand.undo(); }
};
class TvSwitchChannelCommand : public ICommand {
Tv *mTv;
int mOldChannel;
int mNewChannel;
public:
TvSwitchChannelCommand(Tv *tv, int channel) {
mTv = tv;
mNewChannel = channel;
}
void execute() {
mOldChannel = mTv->getChannel();
mTv->switchChannel(mNewChannel);
}
void undo() {
mTv->switchChannel(mOldChannel);
}
void redo() {
mTv->switchChannel(mNewChannel);
}
};
// ----- our CONTROLLER with undo/redo -----
typedef std::stack<std::shared_ptr<ICommand> > commandStack_t;
class CommandManager {
commandStack_t mUndoStack;
commandStack_t mRedoStack;
public:
CommandManager() {}
void executeCmd(std::shared_ptr<ICommand> command) {
mRedoStack = commandStack_t(); // clear the redo stack
command->execute();
mUndoStack.push(command);
}
void undo() {
if (mUndoStack.size() <= 0) {
return;
}
mUndoStack.top()->undo(); // undo most recently executed command
mRedoStack.push(mUndoStack.top()); // add undone command to undo stack
mUndoStack.pop(); // remove top entry from undo stack
}
void redo() {
if (mRedoStack.size() <= 0) {
return;
}
mRedoStack.top()->redo(); // redo most recently executed command
mUndoStack.push(mRedoStack.top()); // add undone command to redo stack
mRedoStack.pop(); // remove top entry from redo stack
}
};
int main() {
using namespace std;
Tv tv;
CommandManager commandManager;
std::shared_ptr<ICommand> c1(new TvSwitchChannelCommand(&tv, 1)); // create command for switching to channel 1
commandManager.executeCmd(c1);
std::cout << "switched to channel " << tv.getChannel() << std::endl;
std::shared_ptr<ICommand> c2(new TvSwitchChannelCommand(&tv, 2)); // create command for switching to channel 2
commandManager.executeCmd(c2);
std::cout << "switched to channel: " << tv.getChannel() << std::endl;
std::shared_ptr<ICommand> c3(new TvSwitchChannelCommand(&tv, 3)); // create command for switching to channel 3
commandManager.executeCmd(c3);
std::cout << "switched to channel: " << tv.getChannel() << std::endl;
std::cout << "undoing..." << std::endl;
commandManager.undo();
std::cout << "current channel: " << tv.getChannel() << std::endl;
std::cout << "undoing..." << std::endl;
commandManager.undo();
std::cout << "current channel: " << tv.getChannel() << std::endl;
std::cout << "redoing..." << std::endl;
commandManager.redo();
std::cout << "current channel: " << tv.getChannel() << std::endl;
std::cout << "redoing..." << std::endl;
commandManager.redo();
std::cout << "current channel: " << tv.getChannel() << std::endl;
return 0;
}
If you compile and run the code above, the out put is:
switched to channel 1
switched to channel: 2
switched to channel: 3
undoing...
current channel: 2
undoing...
current channel: 1
redoing...
current channel: 2
redoing...
current channel: 3
There are different methods for restoring the states in undo() and redo(). In this simple example above for switching TV channels, we really just restore the remembered states. Another solution would be to execute the “inverse” command (we don’t need to store the state), but an inverse command does not always exist - e.g. for switching TV channels there exists no “switch to previous channel” command. But for TvSwitchOn the inverse command is defined: TvSwitchOff. So wether you use inverse commands or remember and restore the object states depends on the situation: an inverse command can take too long (e.g. if complex calculations are involved), saving and restoring the state might be too memory consuming if the state is large.
The difficulties in real-world applications …
The presented example is (with good reason) very simple and undo/redo can be implemented straight forward. For real-world applications things might become more difficult. I recently implemented undo/redo functionality in a CAD based application where the object model that has to be manipulated is large and therefore too memory consuming to store the model as a whole for each undo/redo operation. Additionally the object model was complicated: objects hold pointers to other objects which again can hold pointers to other objects and so on. So, for the actions that manipulate this model (the actions that I had to “wrap” into commands), it had to be carefully determined what subsets of the model gets manipulated and needs to be stored for restoring the desired state state at undo/redo. Moreover, its hard to keep the object model consistent after undo/redo if you have to deal with a complicated object model that connects it’s objects via pointers.
Let me illustrate this with an example: An object has a command createChild() which creates and returns a new object and connects it to the current/parent object - this means the parent objects holds a pointer that points to the new child. The command delChild(childObj) deletes and disconnects the childObj from the parent. The undo of createChild() is naively implemented by utilizing delChild(). Now imagine the following scenario:
B = A.addChild(); // create a new child object and connect it to object A
B.addChild(C); // create a new child object and connect it to object B - the corresponding command object holds a pointer to B
undo();
undo();
redo(); // recreate a new child object and connect it to object A - the recreated object is not object B (has a different address) - we call it B'
redo(); // recreate a new child object and connect it to object B -> crash! object B does not exist anymore!
The application will segfault when trying to execute the second redo, because object B does not exist anymore because the first redo created a new object instead of exactly restoring the original one. The same kind of problem appears if you clone objects and restore them by utilizing the copyconstructor - it does not work because the restored object is not the same as before, it’s just a clone (a copy). Think about it, it can get messy and a lot of manual work to get it right. So i don’t really like the described approach if you have (and have to live with) a structure like described but i also don’t know any better way to implement undo/redo in this case. Just something to think about: if referencing to other objects in the object model would be done via Object-ID’s instead of pointers this kind of problems could be handled easily.