The undo list ~~~~~~~~~~~~~ Each undo item contains an integer serial number and const pointer to the operator that can handle the item. Items are stored in order on a doubly linked list, as shown in the following table: serial | (1) (1) (2) (3) (3) (4) (4) item | item0 <-> item1 <-> item2 <-> item3 <-> item4 <-> item5 <-> item6 | ^ ^ marker | head tail | section| <---------undo----------|----redo----> Items are appended to the list as operations are performed by the user. The head pointer points to the first (oldest) item, new items are appended at the tail. Undo and redo ~~~~~~~~~~~~~ Normally, before the first undo is performed, the list ends at tail. If the user performs an undo, the tail pointer is moved backward, splitting the list into two sections: an undo and a redo section. Further undo operations will move the tail backward, to the left; redo operations will move the tail to the right. If the user performs a new action when the redo section is non-empty, and a new item has to be added, the redo buffer is reset. In the above table, this means if a new item is to be added at the current situation: - first item 5 and 6 are removed - a new item5 is appended after item4 - the tail pointer is set to point to item5 - the undo section contains 5 items, the redo section contains 0 items Sequence numbers ~~~~~~~~~~~~~~~~ Each atomically undoable/redoable operation is a separate item on the undo list. However the user very often will perform a complex operation by a single user input, which means multiple atomic items are appended to the list upon a single action. The user typically wants to undo a single action with a single undo, which means multiple atomic operations need to be grouped for a single undo. This can be implemented using serial numbers. Each new user action should increment the serial number using uundo_inc_serial(). Each new item inherits the current serial from the uundo_list_t. This way items triggered by the same user action will have the same serial. When an undo or redo operation is performed, it will execute all items with the same serial. Considering the above example, an undo would undo item4 and item3, a redo would redo both item5 and item6. It is the responsible of the caller to increase the serial after each new user action. Multiple increases doesn't matter, as the requiremet is only that the serial number of an item must be greater than or equal to the previous item. Sequence numbers: user action in user action (hack #1) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ In some cases multiple user action need to have the same serial. For example assume the code has a function for user action A and B, each implementations adding multiple items then ending in an uundo_inc_serial(). The code also has an user action C that needs to call function A and B. When C is called, it needs to block A and B from using a different serial number or changing the serial number. A technique for this is save & restore: 1. C starts 2. uundo_save_serial() 3. C adds items 4. C calls A; A adds items and increases the serial _once_ 5. uundo_restore_serial() 6. C adds items 7. C calls B; B adds items and increases the serial _once_ 8. uundo_restore_serial() 9. C adds items 10. uundo_inc_serial() 11. C ends This technique works only if: - A and B increase the serial only once - the increase happens at the end, after adding the items (so no item is added with the increased serial before C can restore it) - which includes: every user action function is aware of this and wraps subsequent user action calls in the same save+restore, so that: C and other composite actions increase the serial only once, at the end Sequence numbers: user action in user action (hack #2) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ If the above can not be guaranteed, the alternative method to solve the same problem is freeze. While freeze is activated, uundo_inc_serial() will not touch the serial number. Freeze is really a counter: uundo_freeze_serial() and uundo_unfreeze_serial() need to be in pairs. The easiest way to use this mechanism is to always freeze and unfreez+inc from user actions: 1. action function starts 2. uundo_freeze_serial() 3. add items 4. call other action functions 5. uundo_unfreeze_serial() 6. uundo_inc_serial() This guarantees that only the outmost user action increases the serial only by one. Group operations: freeze adds ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ If there is an operation carried out on a group object (or recursive objects in general), special care needs to be taken to avoid duplicate operations. A (re)do is: - do the operation on the group object - then recurse and do the operation on all children An undo is: - undo each children from the list - undo the group object from the list If the undo/redo for the group object is symmetric (e.g. swap), it will recurse on undo, which means the operation on children are executed twice. Even worse, a redo operation would generate new undo entries from children recursion. There are three ways to manage redo/undo: A. Children should never touch the undo list and should depend on the group object to be done/undone; this is easy to implement if the layout of the tree of object is special, e.g. there is a top level of group objects and then a single level of leaf objects that differ from group objects. B. Make the redo and undo asymmetric in group objects: recurse only on undo, never on redo; do not add new undo entries if entries are already present. This can get real complicated in caller code, it is not recommended to implement this method. C. Same as A, but children objects can be on top level in the tree where they do need to undo/redo using the undo list and groups may have groups as children. In this case the 'freeze adds' mechanism shall be used. The 'freeze adds' is a recursive lock tha tells libuundo that subsequent operations will allocate undo slots, but these slots should not be appended to the undo list. Libuundo still creates the slots because caller's redo/udno code does require the memory to work on, but these slots are saved in a temporary buffer that is discarded when the freeze is over. In other words: - the [top level] group object does its own operation (allocating an undo slot normally, on the undo list) - then it freezes adds - then it recurses to children objects to do the operation - children objects do the operation normally, not knowing their undo slot will not be saved in the list - at the end of the recursion the group object releases the freeze - if this was the last freeze, libuundo discards the temporary slots used in recursion The same is done on undo and redo, which means only the group object will end up having an undo slot on the undo list. Still children objects don't need to be implemented specially: when they are not within a group they will create undo slots on the undo list; when they are under a group, without children objects having to know, they are creating only throw-away undo slots that are not saved.