Site icon Blog Zenika

Pattern Command: Undo, variations Compensation/Replay/Memento

  • Laurent Claisse

    • La dernière fois je vous avez parlé de quelques patterns d’implémentation avec les enums java et en particulier de l’application des enums au Domain Driven Design grâce à l’inversion de dépendance. Aujourd’hui nous allons parler d’un design pattern classique, le pattern Command. Après un rappel de sa structure et de ses utilisations, nous irons un peu plus loin en analysant en particulier 3 variations permettant d’implémenter l’undo/redo.

    Rappels sur le pattern Command

    Dans le langage commun, un pattern désigne un motif répétitif, tel ceux qui décorent les tapis et le carrelage. En programmation, un pattern désigne une solution fréquente à un problème récurrent. Il existe plusieurs types de patterns:

    Ainsi le pattern Command est un design pattern, utilisable dans tout langage orienté objet.
    Le livre de loin le plus connu sur les design patterns est Design Patterns: Elements of Reusable Object-Oriented Software. On l’appelle souvent le GOF, abbréviation de Gang of Four qui désigne ses auteurs. Selon le GOF, l’intention du pattern Command, est d‘encapsuler une requête comme un objet, autorisant ainsi le paramétrage des clients par différentes requêtes, file d’attente et récapitulatifs de requêtes, et de plus permettant la révision des opérations. Le GOF fait ici allusion à deux utilisations des commandes: découpler la création d’une requête de son exécution, et implémenter l’undo. Ce dernier point est le sujet principal de ce post.
    La structure du pattern Commande telle qu’expliquée dans le GOF est la suivante:

    Expliquons les rôles intervenant dans ce pattern: -Command: l’abstraction d’une action, qui permet de découpler la création de l’action de son exécution -Invocator: celui qui déclenche l’exécution des commandes (ex: un item d’un menu d’IHM) -ConcreteCommand: un type de commande particulier -Client: l’instanciateur de ConcreteCommand. Il capture les paramètres passés au constructeur de ConcreteCommand. Attention, le terme Client n’est pas à prendre au sens remoting ni au sens IHM. -Receptor: la cible d’un type de commande particulier (ex: un graphique pour une commande « drawLine »). Attention, le terme Receptor n’est pas à prendre au sens remoting.
    Ils interagissent de la façon suivante:

    On voit que ce pattern permet bien de découpler l’instanciation d’un traitement de son exécution. C’est pour cela qu’on introduit souvent ce degré d’abstraction lorsque les lieux d’instanciation et d’exécution d’un traitement sont éloignés, dans l’espace ou dans le temps.

    Découplage modulaire

    Sans aller jusqu’à la séparation physique, la séparation entre modules (même co-localisés) est une motivation suffisante; le pattern Command permet :

    Découplage spatial ou temporel avec le pattern Command

    Le problème à résoudre est ici que le point de création de la commande, qui est le seul à connaître les données nécessaires à l’exécution d’un traitement, peut être différent du point d’exécution de la commande, qui est le seul à connaître le contexte (portée/scope d’une séquence de commandes, et/ou ressources techniques) nécessaires à son exécution.

    Découplage spatial: commande remote

    Dans le cas spatial, la commande est typiquement créée localement et exécutée sur un serveur distant/remote (les rôles du pattern Command sont indiqués sous forme de stéréotypes UML quand il diffèrent des types propres à la variation Remote Command):

    La cinématique de la création d’une commande côté local et de son exécution côté distant est la suivante:

    Découplage temporel: l’undo

    Dans le cas temporel, le problème est différent: la commande peut être exécutée tout de suite, mais elle doit pouvoir être annulée ou rejouée à un instant ultérieur et indéfini. Comme le dit le GOF, un objet Commande peut avoir une durée de vie indépendante de la requête originelle. Il est donc nécessaire qu’un contexte maintienne une référence vers la commande exécutée. Dans la suite on nomme ce contexte Conversation. Ce découplage temporel peut être utilisé de plusieurs façons:

    Dans le cas qui nous intéresse ici, la conversation mémorise les commandes exécutées et déclenche l’undo/redo. Chacune des commandes stockée par la conversation continue à contenir les paramètres spécifiques à une exécution particulière, qui avaient étés capturés lors de l’instanciation de la commande. Ce type de commande est typiquement exécutée dans le même environnement que celui où la commande a été instanciée, et la méthode execute n’a donc pas besoin d’un paramétre ExecutionEnvironnement (les ressources nécessaires à l’exécution peuvent être passées dès l’instanciation).
    L’undo par commande a la structure suivante (les rôles du pattern Command sont indiqués sous forme de stéréotypes UML quand il diffèrent des types propres à la variation Undo Command – en UML on devrait utiliser une « collaboration paramétrée » mais par simplicité on utilise ici de simples stéréotypes):

    Cas spatial et temporel

    Il est évidemment possible de cumuler les deux difficultés, auquel cas le serveur devra à la fois fournir un ExecutionEnvironment, et maintenir une pile des commandes déjà exécutées (un EJB Stateful permet par exemple de remplir ces deux fonctionnalités). Puisque ce post concerne l’undo, on simplifiera cependant en supposant que les commandes sont locales (intra-JVM, sans remoting)

    Implémentations de l’undo avec le pattern Command, tests et variations

    Venons-en au coeur du sujet: quelles sont les implémentation possibles? Laquelle choisir pour un type de commande particulier?
    La fonctionnalité d’undo/redo est fréquemment demandée pour une IHM car l’être humain se trompe. Elle est souvent lié à une action utilisateur Ctrl+Z/Ctrl+Y. Elle n’est cependant pas triviale à implémenter, car les implémentations possibles dépendent du type de commande (comme on le verra dans la partie Critères de choix d’une variation). On propose ici trois variations du pattern, plus ou moins adaptées selon le type de commande:

    Le code est disponible sur Github. Il nécessite java 8. Le projet contient un framework d’undo par commandes. Les tests junit implémentent la commande Typing de saisie d’un message sur un affichage (Display). Il comprend une même suite de tests appliquée aux 3 variations.

    Les interfaces principales: Command et Conversation

    Puisqu’on se place dans le cas simple sans ExecutionEnvironment, l’interface Command est la suivante:

    @FunctionalInterface
public interface Command {
void execute();
}

    L’annotation @FunctionalInterface n’est pas obligatoire, mais elle a les avantages suivants:

    Introduisons la conversation, qui est le scope dans lequel on execute, annule, et rejoue des commandes:

    public interface Conversation<C extends Command> {
void exec(C cmd);
void undo();
void redo();
}

    Le nom Conversation souligne le fait qu’il arrive souvent que le résultat d’une suite de commandes soit committé atomiquement, ce qui correspond à un scope conversation. La conversation est identifiée à l’Invocator (du pattern Command du GOF), qui a le double rôle de mémoriser et de déclencher les commandes. Ici, c’est le même Client qui instancie les commandes concrètes et qui demande à l’Invocator de les déclencher. Notons que l’interface Conversation est générique: elle porte un type parameter C extends Command. Le but est d’avoir une seule interface Conversation commune aux 3 variations d’undo, tout en permettant l’utilisation par ses implémentations des 3 déclinaisons de Command que nous allons présenter.

    Les tests exécutés pour toutes les variations

    On montre les tests (ce qu’on veut faire) avant de montrer l’implémentation (comment on le fait). Les tests utilisent une commande TypeString qui représente la saisie d’un String dans un Display (les interfaces CompensableCommand et MementoableCommand sont expliquées dans les parties sur les variations correspondantes)

    public class TypeString implements CompensableCommand, MementoableCommand {
private final Display display;
private final String stringToType;
public TypeString(Display display, String stringToType) {
this.display = display;
this.stringToType = stringToType;
}
@Override public void execute() {
display.append(stringToType);
}
[...]
}

    Le code passé sous silence pour l’instant est spécifique à une des 3 variations
    Le receptor (cf. partie Rappels sur le pattern Command) Display est la cible de la commande concrète Typing:

    public class Display {
private final LinkedList<String> displayElements = new LinkedList<>();
public void append(String stringToAppend) {
displayElements.addLast(stringToAppend);
}
public String displayed() {
//Collectors.joining est équivalent à un foreach+StringBuilder mais plus fonctionnel
//(évite l'itération externe/style impératif)
return displayElements.stream().collect(Collectors.joining());
}
[...]
}

    Le code passé sous silence est spécifique à une des 3 variations.
    Pour s’assurer que les 3 variations sont fonctionnellement équivalentes, on écrit les tests dans une classe abstraite CommandUndoTest_Typing. Les tests commencent par les cas triviaux et vont jusqu’à une conversation complexe:

    /**
* Undo is noop when there were no execs
* undo --> ""
*/
@Test public void basicNoopUndo() {
Conversation<C> commands = newConversation();
commands.undo();
assertEquals("", display.displayed());
}
/**
* Redo is noop when there were no undos
* redo --> ""
*/
@Test public void basicNoopRedo() {
Conversation<C> commands = newConversation();
commands.redo();
assertEquals("", display.displayed());
}
/**
* Basic undo
* a    --> "a"
* undo --> ""
*/
@Test public void basicUndo() {
Conversation<C> commands = newConversation();
commands.exec(typeString("a"));
assertEquals("a", display.displayed());
commands.undo();
assertEquals("", display.displayed());
}
/**
* Basic redo
* a    --> "a"
* undo --> ""
* redo --> "a"
*/
@Test public void basicRedo() {
Conversation<C> commands = newConversation();
commands.exec(typeString("a"));
assertEquals("a", display.displayed());
commands.undo();
assertEquals("", display.displayed());
commands.redo();
assertEquals("a", display.displayed());
}
/**
* a    --> "a"
* b    --> "ab"
* undo --> "a"
* undo --> ""
* redo --> "a"
* redo --> "ab"
*/
@Test public void exec_exec_undo_undo_redo_redo() {
Conversation<C> commands = newConversation();
commands.exec(typeString("a"));
assertEquals("a", display.displayed());
commands.exec(typeString("b"));
assertEquals("ab", display.displayed());
commands.undo();
assertEquals("a", display.displayed());
commands.undo();
assertEquals("", display.displayed());
commands.redo();
assertEquals("a", display.displayed());
commands.redo();
assertEquals("ab", display.displayed());
}

    Certains des tests peuvent être consultés dans le code sur Github mais ne sont pas mentionnés ici pour alléger l’article.
    Les classes concrètes spécifiques aux 3 variations ne font qu’instancier un type différent de Conversation (à un détail technique près, propre aux génériques java):

    public class CommandUndoTest_Compensation_Typing_Test extends CommandUndoTest_Typing<CompensableCommand> {
@Override protected Conversation<CompensableCommand> newConversation() {
return new CompensationConversation();
}
@Override protected CompensableCommand typeString(String stringToType) {
return new TypeString(display, stringToType);
}
}
public class CommandUndoTest_Replay_Typing_Test extends CommandUndoTest_Typing<Command> {
@Override protected Conversation<Command> newConversation() {
return new ReplayConversation(()->{
display.reset();
});
}
@Override protected Command typeString(String stringToType) {
return new TypeString(display, stringToType);
}
}
public class CommandUndoTest_Memento_Typing_Test extends CommandUndoTest_Typing<MementoableCommand> {
@Override protected Conversation<MementoableCommand> newConversation() {
return new MementoConversation();
}
@Override protected MementoableCommand typeString(String stringToType) {
return new TypeString(display, stringToType);
}
}
    Coeur de l’implémentation

    Le coeur de l’implémentation est l’utilisation de 2 stacks (FIFO), une pour l’undo et une pour le redo: intuitivement, on sent bien que:

    La classe AbstractConversation utilise 2 paramètres de type, C et S. En effet, chacune des 3 implémentations concrètes de Conversation a besoin de connaître:

    La classe AbstractConversation se présente ainsi:

    /**
*  @param <C> Type of executed commands
* @param <S> Type of stored state (commands or mementos)
*/
public abstract class AbstractConversation<C extends Command, S> implements Conversation<C> {
protected final Stack<S> undos, redos;
public AbstractConversation() {
this.undos= new Stack<S>();
this.redos= new Stack<S>();
}
}
AbstractConversation utilise la classe Stack (classe interne au framework):
public class Stack<T> {
//Delegate to avoid exposing too many Deque methods
private final Deque<T> stack = new LinkedList<>();
/**
* @return null if stack is empty
*/
public T pop() {
return stack.pollLast(); //Not using pop since it throws NoSuchElementException if the deque is empty
}
public void push(T cmd) {
stack.addLast(cmd);
}
public void clear() {
stack.clear();
}
public void forEachFifo(Consumer<? super T> action) {
stack.stream().forEachOrdered(action);
}
}

    Stack délègue à une Deque (double-ended queue) l’implémentation de la stack; en effet il existe une classe java.util.Stack mais elle est obsolète comme Vector. Déléguer à LinkedList plutôt que l’étendre présente 2 avantages:

    Enfin, précisons que forEachFifo() est utilisé par la variation Replay. FIFO signifie first-in first-out donc un parcours dans l’ordre d’insertion.

    Variation: Undo par Compensation

    L’infrastructure étant en place, regardons la première variation qui est la plus naturelle. Une action compensatoire d’une action A consiste à effectuer l’action inverse -A. Par exemple, l’action compensatoire d’un débit erronné de x EUR est un crédit de x EUR.
    Dans le pattern Command, ceci se traduit par une commande compensable:

    public interface CompensableCommand extends Command {
void compensate();
}

    On a vu dans le paragraphe Découplage temporel: l’undo que la conversation pouvait être identifiée à l’acteur Invocator du pattern Command du GOF. CompensationConversation est l’Invocator spécialisé pour les commandes compensables:

    public class CompensationConversation extends AbstractConversation<CompensableCommand, CompensableCommand> {
@Override public void exec(CompensableCommand todo) {
todo.execute();
undos.push(todo);
redos.clear();
}
@Override public void undo() {
CompensableCommand latestCmd = undos.pop();
if(latestCmd==null) return;
latestCmd.compensate();
redos.push(latestCmd);
}
@Override public void redo() {
CompensableCommand latestCmd = redos.pop();
if(latestCmd==null) return;
latestCmd.execute();
undos.push(latestCmd);
}
}

    Dans la variation Compensation, les deux type parameters sont identiques (S=C=CompensableCommand dans AbstractConversation<C,S>), puisque l’état mémorisé est constitué de commandes. En effet, la compensation utilise les commandes déjà exécutées pour les compenser (undo) ou les réexécuter (redo).
    A la fin d’exec(), on vide la stack de redo: les commandes undoées qui précèdent l’exécution d’une commande sont complètem
    ent effacées de la mémoire. La raison de ce choix est de se conformer aux conventions de toutes les IHM offrant un undo/redo (principe de moindre surprise).
    Il est évidemment nécessaire dans cette variation que les commandes utilisées soient compensable; pour la commande de test TypeString, cette fonctionnalité se traduit par le fait que TypeString implémente CompensableCommand et non pas simplement Command:

    public class TypeString implements CompensableCommand {
@Override public void compensate() {
display.unappend();
}
}
    Variation: Undo par Replay

    Il est parfois difficile de trouver une action compensatrice. Dans ce cas si on a invoqué N commandes, une implémentation alternative de l’undo est de réinitialiser l’état à zéro, puis de rejouer les N-1 premières commandes. Le redo consiste ensuite à rejouer la Nième commande.
    Contrairement à la variation Compensation, puisque la variation Replay se repose uniquement sur l’exécution des commandes dans leur sens normal, ReplayConversation n’a pas besoin d’un type de commande particulier de commandes: S=C=Command dans AbstractConversation<C,S>). Par contre elle a besoin d’une instance de commande capable de resetter l’état à zéro:

    public class ReplayConversation extends AbstractConversation<Command, Command> {
private final Command reset;
public ReplayConversation(Command reset) {
this.reset = reset;
}
@Override public void exec(Command todo) {
todo.execute();
undos.push(todo);
redos.clear();
}
@Override public void undo() {
Command latestCmd = undos.pop() ;
if(latestCmd==null) return;
redos.push(latestCmd);
reset.execute();
undos.forEachFifo(cmd->cmd.execute());
}
@Override public void redo() {
Command latestCmd = redos.pop() ;
if(latestCmd==null) return;
latestCmd.execute();
undos.push(latestCmd);
}
}

    Le reset de l’état utilise une commande spécifique au type d’état modifié par les commandes. Dans le cas de la commande Typing (saisie) qui modifie un Display (affichage), on peut simplement effacer complètement l’affichage:

    public class CommandUndoTest_Replay_Typing_Test extends CommandUndoTest_Typing<Command> {
@Override protected Conversation<Command> newConversation() {
return new ReplayConversation(()->{
display.clear();
});
}
}

    Le lambda qui est passé au constructeur de ReplayConversation correspond au champ ReplayConversation.reset. Il vide l’affichage.

    Variation: Undo par Memento

    Plutôt que de mémoriser les commandes, on peut aussi implémenter l’undo en mémorisant leur effet, plus précisément l’état du système avant et après chaque exécution.
    Ceci évoque un autre pattern du GOF, le Memento:

    L‘Originator instancie un Memento en passant à son constructeur un snapshot de l’état du système. Le CareTaker est chargé de connaître le Memento, afin de pouvoir demander, ultérieurement, la restauration de l’état capturé.
    Le Memento doit être capable de restaurer un état capturé antérieurement, d’où l’exigence d’immutabilité. On ne veut pas voir les changements de l’état du système postérieurs au snapshot, il faut donc utiliser des techniques comme la copie défensive. Comme Memento est une interface, on précise cette exigence dans le contrat sous forme de javadoc:

    /**
* Implementations must be immutable (the memento must capture a snapshot)
*/
@FunctionalInterface
public interface Memento {
void restore();
}

    Chaque type de commande peut modifier un type d’état différent, pour lequel la façon de capturer un Memento sera différente. Par exemple la capture d’un état persisté en BD sera très différente de la capture de l’état d’un logiciel de dessin. Le plus simple est donc de spécialiser Command en MementoableCommand, pour que les implémentations de MementoableCommand réalisent à la fois la modification et la capture de cet état, suivant les spécificités de ce dernier:

    public interface MementoableCommand extends Command {
Memento takeSnapshot();
}

    Dans la variation Memento, les deux type parameters ne sont pas identiques (C=MementoableCommand, S=BeforeAfter dans AbstractConversation<C,S>), puisque l’état mémorisé est constitué de captures successives de l’état et non de commandes. Petite subtilité: pour implémenter le redo, on a besoin de capturer l’état avant ET après exécution de la commande:

    public class MementoConversation extends AbstractConversation<MementoableCommand, BeforeAfter> {
@Override public void exec(MementoableCommand todo) {
Memento before = todo.takeSnapshot();
todo.execute();
Memento after = todo.takeSnapshot();
undos.push(new BeforeAfter(before, after));
redos.clear();
}
@Override public void undo() {
BeforeAfter latestMemento = undos.pop();
if(latestMemento==null) return;
Memento latestBefore = latestMemento.before;
latestBefore.restore();
redos.push(latestMemento);
}
@Override public void redo() {
BeforeAfter latestMemento = redos.pop();
if(latestMemento==null) return;
Memento latestAfter = latestMemento.after;
latestAfter.restore();
undos.push(latestMemento);
}
}
//@Immutable
class BeforeAfter {
final Memento before, after;
/**
* @param before must be immutable
* @param after  must be immutable
*/
public BeforeAfter(Memento before, Memento after) {
this.before = before;
this.after = after;
}
}

    Dans cette variation, la commande est donc l‘Originator du pattern Memento du GOF (l’acteur qui déclenche le snapshot), et la conversation en est le Caretaker (l’acteur qui mémorise les mementos). Les rôles du pattern Memento sont indiqués sous forme de stéréotypes UML quand il diffèrent des types propres à la variation Memento Undo Command)

    Critères de choix d’une variation

    Le critère éliminatoire est la possibilité d’implémenter une variation. Cette possibilité ou impossibilité dépend essentiellement de deux facteurs:

    Voyons pour chacune des trois variations quelques critères spécifiques.

    Compensation Undo

    Facteurs favorables:

    Facteurs défavorables:

    Remarques:

    Variation: Memento Undo

    Facteurs favorables:

    Facteurs défavorables:

    Variation: Replay Undo

    Facteurs favorables:

    Facteurs défavorables:

    Autres considérations

    Profondeur de l’undo-redo

    Dans notre exemple, les stacks d’undo/redo ont une profondeur illimitée. Ceci peut provoquer une OutOfMemoryError, et de toute façon l’utilisateur ne se rappelle plus des opérations trop anciennes. Le principe GRASP (attribution de responsabilités) expert en information nous suggère de placer la gestion de cette limitation dans le type qui a la connaissance de la profondeur actuelle de la stack, donc Stack.

    Commandes et macros

    A partir du pattern Command il est très simple de définir des macros: il suffit d’utiliser en plus le pattern Composite (les rôles du pattern Composite sont indiqués sous forme de stéréotypes UML quand il diffèrent des types propres à la variation Command Macro):

    Les macros sont simples à implémenter avec le pattern Command:

    public class Macro implements Command {
private final List<Command> parts;
public Macro(List<Command> parts) {
this.parts = parts;
}
@Override public void execute() {
this.parts.forEach(c -> c.execute());
}
}

    Conclusion

    Le pattern Command est la façon la plus répandue d’implémenter l’undo. Comme souvent en conception orientée objet, la solution est de remplacer l’invocation directe d’une méthode par la création d’un objet (ici, la commande). Cette technique est également très utile pour refactorer du code procédural (cf. Working effectively with legacy code).
    La fonction d’undo/redo peut être difficile à implémenter suivant le type d’état modifié. Cette fonctionnalité est structurante, et ne peut pas toujours être rajoutée a posteriori dans une conception existante sans un très gros refactor, alors incluez-la dès le début si c’est nécessaire. Attention aux bugs de type effet de bord, cette fonctionnalité doit absolument avoir une bonne couverture de tests.

    Auteur/Autrice

    Quitter la version mobile