What is a command ?

State of the art in actions and command history handling and undo/redo mechanisms
Thomas Baudel written around 1999.

Introduction

This documents presents the current state of the art in actions and command history management. Its goal is to provide a pre-specification of features that may be wished in this domain for vaious toolkits. We start by some definitions and reflexions on the nature of commands. Then we list, by order of sophistication, the current features found in various applications dealing with command history management.

This list of features and overall structure is inspired from numerous toolkits, including Swing, Interviews/Idraw, Alias|Wavefront Maya and StudioPaint command histoies, Views command history, Garnet history handling mechanism, MacDraw and 4th dimension command histories...

I What is an action ? a command ?

One can describe user interaction at several levels: lexical (the base vocabulary of actions the user does, like keystrokes and move mouses), syntactic (like handling performing a selection, windows and views), and semantic, that is to say actual state changes of the objects dealing with the true purpose of the application.

An Event is the lexical atom of user interaction. The purpose of the user interface is to gather them in meaningful sequences (or sentences) that make what the user perceives as a single exchange between the user and the machine: an Action.

An Action is the syntactic atom of user-interaction. It is what the user perceives as a single chunk of exchange between the user : for instance, popping or closing a window, selecting a set of objects with a single drag, choosing a tool...

An action has the following basic structure: 

class Action {
    Action (Context=0);
    virtual void execute();
// for command logging, macro recording, one can had serialization routines:
    ostream& operator << (); // + meta-class info for rebuilding the object from a stream.
protected:
    Context context;
};
For macro recording, and many other purposes, the sequence of actions performed by the user can be logged, which requires an ActionHistory data structure that records the subsequent actions. From there, they can be recorded, edited and played back. Smart repeat features can also be implemented at the ActionHistory level.

A Command is an action that has a semantic, i.e. it changes the state of the application's data. It is the semantic atom of user-interaction. It implements the level at which the UI communicates with the functional core of the application. It is a sentence consisting of a verb, one or several objects and a list of complements (these complements can happen to be also objects).

In conventional GUIs, a command is triggered either by an atomic action (key press, pushbutton or menu trigger), or by a continuous action (the result of an interactor's handling of events). However, such a command may consist of several embedded state changes, thus a command can be made of several sub-commands. This means that commands have to be grouped in CommandChunks, that store what the user perceives as a single semantic action. Command chunks are opened at command entry points and closed by the same object opening the chunk, to ensure adequate balance of opening and closing. It is the caller's responsibility to ensure such bracketing balance, although some recovery mechanism can be built by the command history mechanism.

A command is an object that has the basic following structure: 

class Command : public Action {
    Command(Context);
  or  Command(Context, Object(s), Args);
    virtual void execute();
// to which one adds most of the time:
    String userName(); // for syntactic feedback of the command being built
    virtual undo();
    virtual redo(); // or copy + call execute()
    void commit();
};
The question of whether a Command inherits from an Action or not is left open. We can choose either. This class is derivable, and its instances are inserted in a CommandHistory structure whose primary goal is to maintain a queue to enable undo/redo features. We'll see that are are many more things that can be done with a command history, which is why the focus of this document is not on undo queues, but rather on command history handling.

A command history has the following basic structure: 

class CommandHistory {
    dequeueOf<Command*> commands;
    index lastDone;
    addCommand(Command*);
    purge();
// To which one adds the following functions most of the time:
    undo();
    redo();
    repeat();
};
Implementing a command history mecanism in a application is a very sane thing to do. Not only can the user benefit from all sorts of powerfull features that will be introduced, it also straighten the communication between UI and the functional core, enabling better modularization of the code. Yet it is costly to implement, which is why some of the wished feature of a good history handling mecanism include features to ease the implementation of command writing. Some of these facilities are: command decomposition, which allows to write a command as a composition of smaller-grained commands. Automatic undo generation, which allows one to revert the sate of the application by tracking the previous state before executing commands...

An Action/CommandHistory also serves as a context for the action to be executed. This means it should provided a way for an action to retrieve the context, such as the current selection, current clipboard and current application. Such contextual information may be accessed by properties set on the history and retrived by the actions upon execution.

In Views/Studio there are 2 objects named 'Command': the command which we discuss presently of, and the "ActionHandle" object. An ActionHandle object can be seen as a user handle to a command class. It enables the user to:

In other words, an ActionHandle object reifies the concept of actions to enable the user to handle actions like they would do of application objects: instantiate them, edit them, parametrize their defaults... This introduces the concept of ActionHandleFactory, the object that handles the repository of all available commands for the application.

An ActionHandle is not linked to a directly command, but to an ActionClass (or CommandClass) or ActionFactory. This seems to indicate that a command class should have some classInfo reference to be handled gracefully. Since one may want to have several ActionHandle point to the same action class, ActionHandle and ActionClass have to be different classes, the ActionHandle pointing to a given action class.

Actions & Commands taxonomy

Actions deal with objects of the user interface, not of the application's data-structure. To establish a taxonomy of those Actions, one could view the UI's data-structure as an application, and use the same taxonomy presented below. However, one can already show several classes of Actions: To understand the following Commands taxonomy, one should view the application has an object oriented data structure. A command has the effect on this structure. All commands can be expressed as a combination of those primitives. For instance, the group command is: 
groupCommand(objects[]):objs(objects) {}
groupCommand::execute () {
    group=Create(GroupClass);
    newOwner=objs[0].owner; // assuming all objects share the same owner
    for o in objs, i in [1..objs.cardinal]
        if (o.owner)
            Deconnect(o.owner, owner.getSlot(o), o, o.owner);
        Connect(group, groups.slot[i-1], o, o.owner);
    if (newOwner)
        Connect(newOwner, newOwner.slot[newOwner.newSlot()], group, group.owner);
}
One could want to view connect and deconnect as special cases of changeAttributes. Yet, a Change() command is always directly reversible, whereas a Connect() may not be: it could involve objects that don't exist anymore or that have changed state (slots have moved or disappeared).

Besides the semantic action, that can be decomposed in 5 primitives, the execution of a command can have several syntactic (read visible) side-effects. For example, in the above groupCommand, the command may additionally want to deselect the objects and select the created group. These syntactic side-effects have to be also handled, yet they may need to be tailored to the application. This indicates the need to implement CommandHooks, or CommandObservers that will be added by an application to a command class within a given context, so that the UI can be notified of the effects of a command.

Finally, as we mentionned about the CommandHandle objects, an application may want to handle its UI like a functional core: adding and removing menu items, toolbars and so forth. This means that one may wish to handle several 'CommandHistory' in an application.

II State ot the art in Command History handling

This is a simple feature list, where we detail the mechanism's purpose, implementation main lines and what sort of tradeoffs are to be considered when implementing the feature.
  1. Action/Command logging.

    2. The goal of action logging is simply to provide the user with a list of the commands done, possibily allowing some kind of rollback mechanism, or statistics on command usage. It is of limited use, but easy to implement with only the very basic command history class.  Command logging is usefull to indicate the user what action is about to be undone/can be redone, for instance by mentionning Undo <command name> in the edit menu.
    The simple way to implement it is to add a "userName()" pure virtual function on the Command class, that can be accessed by the UI that displays the undo/redo functions.
    Finally, since one should consider that the undo queue is finite, the destructor may have to perform additional actions (like notification and cleanup). One may want the user to be able to set the depth of the command history.
  2. Action/Command side-effects extensibility

    3. When one designs an application, one may wish to implement side effects of the action that don't deal with the objects but with the way they are displayed or presented to the use. For instance, a creation command may want to remove the current selection and replace it with the created object(s). Also when one extends an application with additional services, such as object inspectors, list editors (like Studio does)... one may want to notify these added functionality of the changes induced by the command. Since a command may be generated by a low level, embedded routine, this means that one has to allow for command's effects extensibility.
    The main mechanism to implement commands side effects extensibility is to add a notification mechanism at the command history level, preferably with a different hook for each action/command class. The execute() (and undo(), redo()) methods are responsible for notifying all observers that may have been put on the command class. Also note that raw observers have to be put on the command class to observe notify the state of CommandHandles.
    The application extending command's functionality is responsible for placing observers on the command classes/commandhistories that affect the added functionality. It will be notified whenever a command is executed or undone. This can be used to activate/disactivate menu items, switch toggles, refresh inspectors, or change the current selection (in the manager).
    Notification can be handled in several manners: Callbacks, as it is currently done in Views, or Observable/Observer objects, which are slightly more flexible and type safe. One could think of a more general mechanism: command derivability. The problem is that the manager may create its own commands, which won't be extensible from outside the manager class...
    Example of use: we want that typical manager commands only refresh the manager, but in Studio, they should also broadcast a message that tells if an object has changed.
    This extensibility may also be used so that CommandUI implement a state or display its availability. This would mean the CommandUI class would place an observer on the metaclass. Each time a command is done or undone, the CommandUI would be notified so that it could update its state.
  3. Pseudo-commands

    4. Navigation and Selection actions may or may not be considered as commands, as they do not modify objects. Therefore, one should provide a mechanism to distinguish them from real commands, even when they are undoable and used in the undo queue. This can be done by adding a boolean virtual flag that can be set by those command classes and queried by the command history whenever appropriate.
    -> add a 'virtual Boolean isModifying()' function. (or bringChanges()).
    Another way to look at this is to consider that selection actions may constitute commands if they are part of the Model (i.e. the application's functionality). Then, the Model/Document would have to keep track of the selection and treat its changes as changes of the data-structure. Since navigation operations are local to a view, one should also consider viewpoints as part of a document to make them undoable.
  4. Action Serialization, hardwired.

    5. This is usefull to
    - build reusable scripts or macros
    - as a first step to building PBE systems
    To be implemented, it requires a metaclass/action registry to allow reading back actions from a stream. Each action must build its own read/write routines, which can be asking to much to the developper. Also, if some classes do not implement the serialization, the outcoming command logs may be unusable for replay. Since this is an heavy requirement to the developper, we suggest not implementingcommand serialization. See generalized command serialization below for more insights on the implementation. Finally, objects need to be referenced by a unique identifer in Connect/Deconnect methods, which requires adding unique IDs to objects at the toolkit level.
    Since serialization is similar to writing language instructions, one can use a regular programming language as a file format: for instance one could consider that javascript would be a good command file format. Although one needs to consider if it's easy to parse.
  5. Monolevel Undo.

    6. In the good old days of the macintosh +, programs such as MacDraw did implement undo without a command history structure, only a command structure. The execute command would produce a shift between the application's data structure and the displayed structure: undo would simply consist of rereading the application's data, while a further command would propagate the changes to the data structure and shift again the display. This mechanism is fairly easy to implement, but allows only one level of undo, thus we won't consider it.
  6. Full undo/redo

    7. No application can be claimed to implement true direct manipulation interaction if it does not implement a full undo/redo mechanism. This means that all commands must implement both the 'execute' virtual function, and the undo() virtual function that reverts the effects of execute(). additionally, a redo() function defaults to calling back execute(), but it can be reimplemented to perform the execute in an optimized way.
    Besides requiring that each command implement a isUndoable() virtual function that defaults to false. WHen a command that is not undoable is added, it should purge the command history. A command may not be undoable for 3 reasons:
    - it commit changes (for instance save... or save as...)
    - it has to high memory requirements
    - its undo function is not implemented.
    One may whish to add a flag to mention this reason.
  7. Command chunking

    8. Because a user's action may be a composite of smaller grained commands, it is usefull to have command entry points create a 'Macro command' and place it on top of the command history. Any further command added by inner functions will be added to this macro command, instead of being placed on top of the stack. Hence, undo/redo will
    -> Create a CommandList :public Command class, and have the command history be ware of it so that it can accumulate the added commands in this class instead of stacking them.
  8. Command compression

    9. A mecanism should allow to compress several keystrokes into one
    insert text, or several moves of the same amplitude with a
    Move<List of Obj, Vector>, etc... Command compression requires extending the command metaclass to allow command argument's comparison. If the arguments are equal and the objects are the same, then the two commands are the same. This also requires the command class to allow manipulating its array to merge commands as they are pushed. Command compression is a first step toward creating a canonical form for commands (see below).
  9. Repeat

    10. Requires a virtual copy() function in the command class, as well as a repeat() function in the command history class.
  10. Smart repeat/hardwired

    11. In sequences of duplicate-move-duplicate, infer the position of the newly created object from the sequence of moves that have been performed. This works also for repeating move sequences alone, paste, resizing... need a general pattern.
    Implementation: Requires extending the command history mechanism with some predefined properties. When a command is 'done', it can adjust these properties. Commands aware of these properties can use query them to adjust their default parameters.
    For instance, adding a 'Translation' property to a CommandHistory. This 'translation' property (to be more general, it should be a full transformer is increment by each object move. It is reset to Identity by each selection changes. It is used by each object creation command to apply the relative transform to the newly created object.
  11. Generalized Command Serialization

    12. We've seen that all commands can be expressed as a combination of one of 5 primitives, plus some graphic side effect. We've also seen that a command has a base structure of:
    Verb, Object(s), Arg(s), the arguments being either objects or atoms. If all commands can declare their structure in those basic terms (IlvValue), serialization becomes way simpler to implement, the programmer only needs to write the commands in those terms. This can be implement by making the command class inherit from ValueInterface, and declaring as accessors its verb, objects and argument's values. Serialization can be implemented, but also way more powerfull functions such as PBE (see below)
  12. Generalized smart repeat

    13. When repeating, should be able to detect if several commands of the same type have been issued, and infer from their difference what is the increment to be given to the next repeat.
    This has the same requirements as GCS, but requires also the implementation of a comparison mechanism to infer the repeating patterns.
  13. Programming by example

    14. Programming by example is the next step after smart repeat: when the user issues a command, we look for a repetition pattern in the whole command structure. If so we propose the user to  repeat the sequence, filling the gaps that we haven't been  able to infer, and letting him entering is halting criteria if we can't infer it.
    The difference between generalized smart repeat and PBE is that PBE is active or semi active, whereas GSR is inkoked by the user. PBE requires continuous parsing of the command history to:
    - find repeating patterns
    - find invariants in the command's arguments and objects.
    - find variables, infer their rates of growth
    Propose the user to execute new commands with the variables incremented according to their estimated new values. Allow the user to adjust the variable parameters and change the constants to refine the inference as more and more repeated commands are issued.
  14. PBE with canonical forms

    15. To be truly efficient, PBE requires being able to reorder the command stack in a canonical order for comparison purposes. This means that commands should know if they are permutable with one another (commutativity). This also requires a good form of command compression.
  15. The halting problem and research frontiers in PBE

    16. So far, PBE only knows how to infer primitive recursive functions from the given examples. This is a huge shortcoming, as most user interaction appears to have various halting criteria that one can't always infer from the existing history. This is the current research frontier in PBE systems: infering possible halting conditions and proposing them to the user. This seems to require a finer grained typology of command args and their possible range. We won't say much more about it for now.
  16. Selective undo/redo: per object command history and reification of the command history mechanism. This requires building the application from the ground up arond a dependancy graph structure (like we did in Maya). Appears impractiable to implement at the toolkit level. The idea is that all objects have their own construction history, besides the global command history. One can select the top command instance from the object inspector and disactivate it or reactivate it at will. Very powerfull...
  17. automatic undo/redo handling: if all objects are accessible via the ValueInterface structure ans the 5 base types of commands are implemented, it may be possible to automatically revert states. Yet this states to heavy requirement for a library such as Views: the user would have to implement all his application classes based on the value interface structure to benefit from it...
About ActionHandles: command handles may not be seen as always linked to an ActionClass: they may not be semantically significant nor appear in the command history: consider the ShowPanel CommandHandles, the ToggleGrid command and so forth... This means this class should be defined in a different file, only the ActionClass should feature whatever is needed for command handles to be notified. 
class ActionHandle : public Observer {
// observes the menu items/buttons it is linked to
// may want to observe other objects such as buffers or other messages from the application to
// get its state info...
   state(); // enabled/disabled, on/off
     shortcut;    
   virtual void performAction(IlvAny context=0); // to use the Swing nomenclature
};
class UndoableCommandHandle : public CommandHandle {
// add the command class to the list of observers....
    CommandClass* _commandClass;
    execute (CommandContext* c) {
       c->history()->add(_commandClass->instantiate(c));
   }
};

Implementation considerations

.User defined semantics of do() and undo() need to be encapsulated to allow the command class to do some maintenance of the history when these functions are called: notification, flag changes. This means that the user will implement doIt() and undoIt() bodies, and call execute() and undo() to have the command do their effect.

Several flags are added to commands for convenience purposes: isModifying should be set for commands, to allow the maintenance of the _modified flag on documents. An observer can then observe the command history for a given document and maintain the flag properly. isPseudoCommand (a subset of isModifying): when this flag is set, it means these commands are not to be stored in the command history (thus they are treated as actions). This is usefull to have the command history distinguish itself the SelectionActions or NavigationActions and decide globally whether they should be considered as actions or commands. This does not prevent the user to use either SelectionActions or SelectionCommands depending on the context of use.

When adding and action to a command history, this action cannot be stored, because it is not undoable. Thus, the action is still executed (if it's not done), notification is done, and then the action is destroyed if it has not been adopted by one of its observers (adopting an action is done by using the setContext command).

The class ActionSelectionHandler is a helper meant to implement redrawing and graphics oriented notification, without having to specialize the CommandHistory class for a given type of document. This selection handler only assumes that a document is made of a graph of ValueInterfaces, and handles a current selection that can be modified or on which commands can operate if they have no arguments.

In a way very similar to the undo mechanism in swing, object changes are recorded by the model, not by the UI. This means that commands are recorded in the manager and the changeValues methods of the graphic objects instead of being explicitely done by the user interface.

IV Conclusion

 

 

V Annex: a comparison with Swing undo management

Swing's undo management relies on an application's structure representation that can accomodate command executions. It would be feasible in Views if we could afford to consider that all commands only act on ValueInterfaces and that those value interfaces be completely descriptive of the underlying object.
Modulo this constraint for application development, undo/redo becomes very easy to implement, almost automatic: all commands have only to implement state changes on the application's data structure. The command history (UndoManager) only has to gather successive state changes in the current chunk (CompoundEdit). Yet, this mecanism is more or less what happens de facto in the manager and for the object value changes with our mechanism.

Another view at it is that it is not the CommandObject that store the state change of the data structure, but the object itself, that in in charge of gathering its state changes and propagating them to one more command histories. To do that, we would have to augment ValueInterface changeValue methods, so that they keep track of state changes and propagate them to a current listenr that fills the undo queue.

Translation table between Swing classes and our proposed nomemclature:

UndoableEdit <~> Command
            undoableEdit.isSignificant() <-> command->isModifying()
     except that the undoable edit is created by an object, not by the action that instantiated the
     command.
StateEditable <~> ValueInterface if we implement generlized serialization/canonical command forms
UndoManager <~> CommandHistory, however, in swing, the UndoManager assumes the objects are responsible for adding commands to the history, not the application. This means that one must make the UndoManager observe all the objects it deals with to be able to handle undo... Impractical in the case of drawing editors, I think.
CompountEdit <-> MacroCommand
StateEdit <-> Any atomic command of type Change() yet there is no provision for connections, add and delete objects. These seem to be considered as state changes of the container instead of real creation/connection commands.
UndoableEditSupport <-> an Observer of  a CommandClass
Action <~> ActionHandle

Swing has a general introspection mechanism that seems to allow it to implement all the features enumerated above. Yet, it lacks explicit support of those features. Perhaps in future releases ? Perhaps these would be good extensions to jviews ? For instance, smart repeat might be a usefull feature. ?

Swing improves the notion of userName by differentiating undoUserName from redoUserName

Page created in 1999. Thomas Baudel