The undo protocol ================= General ------- Undo is organized into a separate module. This module conceptually maintains a tree where the nodes represent application states and the arcs represent transitions between these states. The root of the tree represents the initial state of the application. The undo module also maintains a current state. During normal application operation, the current state is a leaf of a fairly long branch of the tree. Normal application operations add new nodes to the end of this branch. Moving the current state up the tree corresponds to an undo operation and moving it down some branch corresponds to some redo operation. Arcs in the tree are ordered so that they always point FROM the current state. When the current state moves from one state to the other, the arc it traversed is reversed. The undo module does this by calling a generic function that client code must supply a method for. no-more-undo [error condition] A condition of this type is signaled whenever an attempt is made to call undo when the application is in its initial state. undo-tree [protocol class] The base class for all undo trees. undo-record [protocol class] The base class for all undo records. Client code typically derives subclasses of this class that are specific to the application. :tree [initarg] Supplies the undo tree to which the undo record belongs. add-undo undo-record undo-tree [generic function] Add an undo record to the undo tree below the current state, and set the current state to be below the transition represented by the undo record. flip-undo-record undo-record [generic function] This function is called by the undo module whenever the current state is changed from its current value to that of the parent state (presumably as a result of a call to undo) or to that of one of its child states. Client code is required to supply methods for this function on client-specific subclasses of undo-record. undo undo-tree &optional (n 1) [generic function] Move the current state n steps up the undo tree and call flip-undo-record on each step. If the current state is at a level less than n, a no-more-undo condition is signaled and the current state is not moved (and no calls to flip-undo-record are made). As long as no new record are added to the tree, the undo module remembers which branch it was in before a sequence of calls to undo. redo undo-tree &optional (n 1) [generic function] Move the current state n steps down the remembered branch of the undo tree and call flip-undo-record on each step. If the remembered branch is shorter than n, a no-more-undo condition is signaled and the current state is not moved (and no calls to flip-undo-record are made). Implementation -------------- Application states have no explicit representation, only undo records do. The current state is a pointer to an undo record (meaning, the current state is BELOW the transition represented by the record) or to the undo tree itself if the current state is the initial state of the application. Suggested CLIM gadget --------------------- Undo might be presented in a CLIM gadget in the form of a tree where branches are added to the right over time, like this : + | + | + |\ + + | | + + |\ + * where `*' indicates the current state. The tree will be fairly tall and skinny, so the gadget should probably be a tall, narrow window with scroll bars, and/or zoom. The transitions should be PRESENTed by client code so that a compact indication of the type of record is used. When the mouse is moved over a transition, a more elaborate description is visible. Clicking on any of the states generates calls to flip-undo-record for every step the current state has to move in order to eventually arrive at the state clicked on. How the buffer handles undo =========================== undoable-buffer [class] This is a subclass of standard-buffer. Instantiating this class creates an empy undo-tree for the buffer. undo-tree undoable-buffer [generic function] Return the undo-tree of the buffer. Undo is implemented as :after methods on, insert-buffer-object, insert-buffer-sequence and delete-buffer-range specialized on undoable-buffer. *undo-accumulate* [special variable] This variable is initially nil (the empty list). The :after methods on insert-buffer-object, insert-buffer-sequence, and delete-buffer-range push undo records on to this list. *performing-undo* [special variable] This variable is initially nil. The :after methods on insert-buffer-object, insert-buffer-sequence, and delete-buffer-range push undo records onto *undo-accumulate* only if *performing-undo* is nil so that no undo information is added as a result of an undo operation. Three subclasses `insert-record', `delete-record', and `compound-record' of undo-record are used. An insert record stores a position and some sequence of objects to be inserted, a delete record stores a position and the length of the sequence to be deleted, and a compound record stores a list of other undo records. The :after methods on insert-buffer-object and insert-buffer-sequence push a record of type delete-record onto *undo-accumulate*, and the :after method on delete-buffer-range pushes a record of type insert-record onto *undo-accumulate*. with-undo buffer &body body [macro] This macro first binds *undo-accumulate* to nil. Then it executes the forms of body. Finally, it calls add-undo with an undo record and the undo tree of the buffer. If *undo-accumulate* contains a single undo record, it is passed as is to add-undo. If it contains several undo records, a compound undo record is constructed out of the list and passed to add-undo. Finally, if *undo-accumulate* is nil, add-undo is not called at all. To avoid storing an undo record for each object that is inserted, the with-undo macro may in some cases just increment the length of the sequence in the last delete-record. The method on flip-undo-record specialized on insert-record binds *performing-undo* to t, inserts the sequence of objects in the buffer, and calls change-class to convert the insert-record to a delete-record, giving it a the length of the stored sequence. The method on flip-undo-record specialized on delete-record binds *performing-undo* to t, deletes the range from the buffer, and calls change-class to convert the delete-record to an insert-record, giving it the sequence at the stored offset in the buffer with the specified length. The method on flip-undo-record specialized on compound-record binds *performing-undo* to t, recursively calls flip-undo-record on each element of the list of undo records, and finally destructively reverses the list. buffer-undo-record [class] A subclass of undo-record. :buffer [initarg] The buffer to which the record belongs. :offset [initarg] This initarg is mandatory and supplies the offset that determines the position at which the undo operation is to be executed. undo-offset undo-record [generic function] Return the offset of the undo record. delete-record [class] A subclass of buffer-undo-record. Whenever objects are inserted, a delete-record containing a mark is created and added to the undo tree. :length [initarg] Supply the length of the sequence of objects to be deleted whenever flip-undo-record is called on an instance of delete-record. insert-record [class] A subclass of buffer-undo-record. Whenever objects are deleted, the sequence of objectgs is stored in an insert record containing a mark. :objects [initarg] Supply the sequence of objects that are to be inserted whenever flip-undo-record is called on an instance of insert-record. compound-record [class] A subclass of buffer-undo-record. This record simply contains a list of other records. :records [initarg]