Is there anything sadder than the Command pattern? The exemplar of the once-proud Patterns movement, the one that everyone understands and can see the power of, the one that has an instant applicability to many applications: the undo system. I remember a time when undo seemed a luxury to be implemented only by the most hardened of programmers; then the command pattern made it achievable by any decent coder. Now, the Command pattern is just that extra cruft you have to write when your language doesn’t have good support for closures.
But what of undo? Doesn’t Command still encapsulate something worth having in this situation, beyond what a closure gives you for free? Especially when, for whatever reason, you are using a language without decent support for closures.
I found myself in this situation recently when re-writing the undo system for the Linux Stopmotion application. This application is written in C++, and there are many bugs in it. Fixing the undo system seemed necessary for sorting the worst of them out.
If you search the internet for “undo.cpp”, you can find three different undo system implementations that people have used in C++. One is the classic described in Gamma et al’s Design Patterns, where Command objects have an
undo() and a
redo() method. This was the original Stopmotion implementation, and I also found this in Inkscape, a Battle for Wesnoth tool, Torque3D and example code from the blogs of RandomMonekyWorks and Yingle Jia. It is unfortunate that this version is so popular because, unless you do some cleverness I have yet to see attempted, you need to implement each operation twice; once as the Undo of Delete (say), again as the Redo of Insert. You also need (again, barring as-yet-unseen cleverness) to copy any data that will be added or removed into your command object.
A better approach (the one I took with my re-write) can be seen in Yzis, KAlarm and Doom 3′s Radiant tool (although the code in these three is not for the faint-hearted and doesn’t quite conform to the platonic ideal I’m about to express). Here your Command object has just an
undo() and an
invert() method – indeed these can (and should) be combined –
undo() should perform the operation, delete itself and return an inverse of itself – to ensure that a command, once undone, cannot be undone again without being redone first. This also means that a Command object does not need to copy any data; a Delete object removes the thing deleted from the model, attaches it to the inverse Insert object, deletes itself and returns the Insert object. The Insert object, if executed, returns the same object back to the model, creates the delete object, deletes itself (now that it is in an empty state) and everything is fine.
A third approach I saw just once in my quick search; an application called Satan Paint, which stores the entire model state as the undo element, not using the Command pattern at all. However, storing the entire state is madness, right? All that memory storing all that data you’ll probably never use…
But now that I’ve done my re-write and it seems to be working well, there’s a nagging thought. Can and should we retire the Command pattern, even in C++, even for undo? My motto in these cases is always “think how you’d do it in Haskell, then see if it’s applicable in the other language”. So how would one apprach undo in Haskell?
Well Haskell, having no mutable state, would require the use of a purely-functional data structure. This is a data structure that has operations that return mutated versions of the operated-on structure, but the original is still present. To avoid creating a whole new copy, parts of the old structure are re-used in the new wherever possible. And the art in designing purely-functional data structures is enabling as much re-use as possible. Once you have a purely-functional data structure, a Command object is redundant; you simply remember previous states. So, kudos to Satan Paint!
Now all we need is a decent library of purely-functional data structures in C++, together with a decent garbage collector to stop no-longer-used sub-parts leaking…