Étude de cas : dp state en c++

r0d

Le pattern state, ou patron état, est l'un des patterns les plus utilisés. Dans sa définition initiale, il est très simple, mais comme beaucoup de design pattern, son implémentation concrète peut varier beaucoup selon le contexte. Je vous propose ici d'analyser plusieurs implémentations possibles. ♪

- Titre : Étude de cas : dp state en c++

- Auteur : r0d

- Parution : 24 septembre 2009

- Licence : Copyright ® 2010 r0d. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

- I-A. Généralités

- I-B. Définition du pattern state

- I-C. Le diagramme d'état

- II. Modèle initial

- III. Implémentations en c++

- III-A. Implémentation « YaTuS »

- III-B. FSM State

- III-C. Laisser le contrôle aux états concrets

- III-D. Les états sous forme de singleton

- III-E. La machine à états selon Qt

- IV. Annexes

- IV-A. Liens

- IV-B. Notes

- IV-C. Remerciements

- IV-D. Commentaires

I - Introduction

I-A - Généralités

retour à la page d'accueil

Le pattern State (patron Etat) est un behavioural design pattern (patron de conception de type comportemental).

Les design patterns fournissent des modèles théoriques qui permettent de résoudre des problèmes récurrents. Ils ont été pensés de façon à répondre à un maximum de problèmes, de façon à ce qu'ils puissent être appliqués avec succès dans les contextes les plus différents possible. De fait, ils sont utilisés régulièrement par les développeurs qui font de l'objet, et on les retrouve donc dans de nombreux logiciels.

Concernant les design pattern, je pense qu'il est inutile de les apprendre par cœur. D'autant plus qu'à force de les utiliser on finit par les connaître sans avoir à faire l'effort de les apprendre. En revanche je crois qu'il est important de les connaître, juste pour savoir qu'ils existent et savoir où trouver des informations lorsque nous voulons les appliquer. La compréhension de ces design pattern est également un excellent exercice qui permet de comprendre un certain nombre de problématiques relatives au paradigme objet et d'en appréhender des solutions efficaces, générales et élégantes.

L'UML propose tout un tas de diagrammes, qui permettent de représenter différentes étapes de la réalisation d'un logiciel, et de différentes façons. Pour comprendre cet article, vous aurez juste besoin de savoir lire un diagramme de classe et savoir ce qu'est un diagramme d'état.
Ici je n'utiliserai que des diagrammes très simplifiés, nettoyés de tout ce qui n'a pas de rapport direct avec le sujet dont traite le diagramme.

I-B - Définition du pattern state

L'idée de ce pattern est d'obtenir une classe, que j'appellerai contexte (context), qui aura un comportement circonstancié à un état courant, c'est-à-dire un comportement différent selon son état.
. Nous allons donc créer une classe abstraite qui définit l'interface publique des états. En gros, nous allons y mettre les fonctions du contexte dont le comportement peut varier. C'est l'état abstrait (abstract state).
. Ensuite il faut implémenter les états concrets, qui hériteront de l'état abstrait. Après on crée un pointeur état courant, en variable membre du contexte.
. Lorsqu'on souhaite que le contexte change d'état, il suffit de modifier l'état courant.

Une implémentation d'un pattern state est considérée comme meilleure si elle respecte les critères suivants :

. le LSP est respecté (entre l'état abstrait et les états concrets). Cela facilite la manipulation des états et peut éviter des situations complexes et/ou ambiguës ;
. les états concrets ne possèdent pas de données. Les données doivent se trouver dans le contexte ou dans l'état abstrait.

I-C - Le diagramme d'état

Le diagramme d'état est généralement moins connu que le diagramme de classes, je vais donc en dire un mot. Il sert à représenter un automate d'état fini (ou graphe). C'est extrêmement simple en fait : il y a des états – les nœuds du graphe – et des évènements (ou transitions) – les arcs du graphe – qui permettent de passer d'un état à l'autre.

diagramme d'état

Prenons un exemple didactique simplissime et sans rapport avec le développement logiciel (l'UML est conçu pour représenter tous types de problèmes, pas uniquement de programmation). Prenons donc l'exemple d'un graveur de CD. Il pourra se trouver dans trois états différents : stand-by (il ne fait rien), lecture, et enregistrement. Pour passer de l'un à l'autre de ces états, on a trois événements : play, stop, et record, qui correspondent par exemple à l'activation par l'utilisateur de la touche de la télécommande correspondante.

diagramme d'état

II - Modèle initial

Le pattern state le plus simple est celui de la page Wikipédia sur le pattern State[en].

patron Etat le plus simple

Diagramme qui peut donner le code suivant par exemple :

#include <iostream>
#include <boost/shared_ptr.hpp> // pour boost::shared_ptr
using namespace std;

class State
{
public:
virtual ~State() {}
void Action() { DoSomething(); }
private:
virtual void DoSomething() = 0;
};

class ConcreteStateA : public State
{
private:
void DoSomething() { cout << "ConcreteStateA: DoSomething" << endl; }
};

class ConcreteStateB : public State
{
private:
void DoSomething() { cout << "ConcreteStateB: DoSomething" << endl; }
};

class Context
{
public:
Context():currentState( new ConcreteStateA ) {}

void SetState( State * newState )
{
currentState.reset( newState );
}

void DoSomething() { currentState->Action(); }

private:
boost::shared_ptr<State> currentState;
};

int main()
{
Context context;
contexte.SetState( new ConcreteStateA );
context.DoSomething();
contexte.SetState( new ConcreteStateB );
context.DoSomething();
// ...

cin.get();
}

À noter l'utilisation d'un pointeur intelligent (boost::shared_ptr) dans le code ci-dessus. Pour plus d'informations sur les pointeurs intelligents, je vous renvoie à la F.A.Q de developpez.com sur les pointeurs intelligents[fr] ou cet excellent tuto de JolyLoic[fr].

Celui du GoF[en] n'est pas fondamentalement différent, il ajoute juste le passage du contexte lors de l'action effectuée par l'état.

patron Etat du GoF

Le code sera quasiment identique au premier, puisque seules les fonctions d'action() des états vont changer :

class State
{
public:
void Action( Context context) { DoSomething( context ); }
private:
virtual void DoSomething( Context ) = 0;
};

Cette implémentation permet souvent d'éviter d'avoir à stocker des données dans les états, en stockant toutes ces données dans le contexte. En revanche, il rajoute une dépendance des états vers le contexte qui ne me plait pas tant que ça. Une autre raison pour laquelle je n'aime pas trop cette implémentation c'est qu'elle pose un problème (un cas de conscience au moins) si l'on souhaite que les états puissent accéder à des données/fonctions non publiques du contexte.

III - Implémentations en c++

III-A - Implémentation « YaTuS »

J'ai appelé cette implémentation ainsi, car c'est celle que j'utilise à plusieurs reprises dans YaTuS[fr]. Cette implémentation me semble bonne lorsqu'on a peu d'états et que les états concrets sont gros.

Prenons par exemple celui de la classe Game. Cette classe représente la partie en cours, d'un point de vue comportemental. Elle possède deux états, qui représentent respectivement la phase de déplacement (MovementState) et la phase de combats (FightState).

Son diagramme de classe est le suivant :

patron 'Etat YaTuS'

Ce qui change par rapport au pattern classique (voir chap. II), c'est qu'ici mon contexte (Game), possède une instance de chaque état. Dans cette implémentation, le contexte (Game) possède également un pointeur qui va pointer successivement sur chacune de ces instances.
Cette implémentation laisse la responsabilité des transitions à la classe qui va manipuler le contexte.

#include <iostream>
#include <string>
using namespace std;

class GameState
{
public:
void Action() { DoSomething(); }
private:
virtual void DoSomething() = 0 ;
};

class MovementState : public GameState
{
private:
void DoSomething() { cout << "MovementState::DoSomething" << endl; }
};

class FightState : public GameState
{
private:
void DoSomething() { cout << "FightState::DoSomething" << endl; }
};

class Game
{
public:
Game() : m_currentState( &m_mvtState ) {}

void DoSomething()
{
m_currentState->Action();
}

void UpdateCurPhase( const std::string & stateName )
{
if ( stateName == "movement" )
m_currentState = &m_mvtState;
else
m_currentState = &m_fightState;
}

private:
MovementState    m_mvtState;
FightState    m_fightState;
GameState *    m_currentState;
};

int main()
{
Game game;
game.DoSomething();
game.UpdateCurPhase( "fight" );
game.DoSomething();
game.UpdateCurPhase( "movement" );
game.DoSomething();

cin.get();
return 0;
}

Avantages
- Les états ne sont créés qu'une seule fois, et l'état courant n'est qu'un pointeur qui va pointer sur un de ces états déjà instanciés. Il n’y a donc pas de manipulation de mémoire (new), ce qui est souvent une bonne chose lorsque les classes états concrètes sont un peu grosses.
- Cette méthode n'impose pas de contraintes concernant la responsabilité des transitions. En effet, elle peut être implémentée dans le contexte (ce qui est le cas dans le code ci-dessus), ou laissée aux états concrets.

Inconvénients
- Cette implémentation n'est pas souhaitable lorsqu'il y a beaucoup d'états de type différent.
- Cette implémentation implique une gestion assez spécialisée des états (le contexte doit connaître les différents types d'états). Cela peut rendre plus difficile la modification du diagramme d'état.

III-B - FSM State

La définition initiale du patron état ne spécifie pas qui est en charge des transitions (le contexte, les états, autres…).

L'implémentation FSM[en] nous est proposée par Vince Huston comme exemple d'implémentation du pattern state. Elle est conçue de façon à ce que les transitions soient définies dans le contexte, et pas dans les états.
Le principal avantage de cette implémentation est que toutes les transitions sont centralisées (dans le contexte), facilitant ainsi la compréhension et la maintenance.

class FSMstate { public:
virtual void on()  { cout << "undefined combo" << endl; }
virtual void off() { cout << "undefined combo" << endl; }
virtual void ack() { cout << "undefined combo" << endl; } };

class FSM {
public:
FSM();
void on()   { states[current]->on();  current = next[current][0]; }
void off()  { states[current]->off(); current = next[current][1]; }
void ack()  { states[current]->ack(); current = next[current][2]; }
private:
FSMstate*  states[3];
int        current;
int        next[3][3];
};

class A : public FSMstate { public:
void on()  { cout << "A, on ==> A" << endl; }
void off() { cout << "A, off ==> B" << endl; }
void ack() { cout << "A, ack ==> C" << endl; }
};
class B : public FSMstate { public:
void off() { cout << "B, off ==> A" << endl; }
void ack() { cout << "B, ack ==> C" << endl; }
};
class C : public FSMstate { public:
void ack() { cout << "C, ack ==> B" << endl; }
};

FSM::FSM() {
states[0] = new A; states[1] = new B; states[2] = new C;
current = 1;
next[0][0] = 0; next[0][1] = 1; next[0][2] = 2;
next[1][0] = 1; next[1][1] = 0; next[1][2] = 2;
next[2][0] = 2; next[2][1] = 2; next[2][2] = 1; }

enum     Message { On, Off, Ack };
Message  messageArray[10] = { On,Off,Off,Ack,Ack,Ack,Ack,On,Off,Off };

int main() {
FSM  fsm;
for (int i = 0; i < 10; i++) {
if (messageArray[i] == On)        fsm.on();
else if (messageArray[i] == Off)  fsm.off();
else if (messageArray[i] == Ack)  fsm.ack(); }
}

Cette implémentation est très orientée « graphe ». FSM est le contexte. Le tableau next, variable membre de FSM, n'est rien de plus que le graphe de transitions, ou STT (state transition table).
Une bonne étude sur cette façon de procéder est proposée par Robert C. Martin ici[en].

III-C - Laisser le contrôle aux états concrets

Dans la plupart des patterns state que avons vu précédemment, c'est le contexte, voire le propriétaire du contexte qui va gérer le changement d'état du contexte. Mais il arrive souvent, selon le design du programme, qu'il soit préférable de laisser aux états concrets eux-mêmes la responsabilité de l'état du contexte. Dans ce cas il faudra opter pour un mécanisme qui ne fait pas de delete/new sur l'état courant pendant la transition. Souvent on sera obligé de passer le contexte en paramètre des fonctions des états, afin que ces derniers gèrent l'état courant du contexte.

Il y a une implémentation, qui laisse aux états concrets le soin de gérer les transitions, que j'apprécie beaucoup. Elle est très générale et modulaire. Voici à quoi elle ressemble :

#include <iostream>
#include <map>
#include <string>

using namespace std;

class State
{
public:
const string Action( int i ) { return DoSomething(i); }
private:
virtual const string DoSomething( int i ) = 0;
};

class StateA: public State
{
private:
const string DoSomething( int i ) {
cout << "A -> ";
return (i%2==0) ? "B" : "C";
}
};

class StateB: public State
{
private:
const string DoSomething( int i ) {
cout << "B -> ";
return (i%3==0) ? "C" : "A";
}
};

class StateC: public State
{
private:
const string DoSomething( int i ) {
cout << "C -> ";
return (i%4==0) ? "B" : "A";
}
};

class Graph
{
public:
Graph() {
states_["A"] = new StateA;
states_["B"] = new StateB;
states_["C"] = new StateC;
currentState_ = states_["A"];
}

void DoSomething( int i ){
string nextState = currentState_->Action(i);
currentState_ = states_[nextState];
}

private:
map<string, State*> states_;
State * currentState_;
};

int main()
{
Graph graph;
for (int i=0; i<20 ; i++)
graph.DoSomething(i);

cout << "end" << endl;
cin.get();
return 0;
}

Sortie du programme ci-dessus :

À -> B -> A -> B -> C -> B -> A -> B -> A -> B -> C -> A -> C -> B -> A -> B ->
C -> B -> A -> B -> end

Le principe de cette implémentation est qu'il n'y a pas de fonction changeState(), la gestion des états se fait automatiquement : les appels aux fonctions implémentées par les états concrets doivent retourner le nouvel état, et le contexte se met à jour directement.

Le principal avantage de cette implémentation est qu'elle permet la construction d'un graphe, aussi complexe soit-il, de façon assez intuitive.
Un autre avantage est qu'elle permet l'ajout de nouveaux états à peu de frais. En effet, pour ajouter un nouvel état, il suffit de créer la classe de cet état, et le déclarer dans le constructeur du contexte (states_[« identificateur de l'état »] = new StateX;) et c'est tout.

Nous voyons dans cette implémentation que, même si ce sont les états concrets qui décident de l'état suivant, le code qui effectue la transition est quand même dans le contexte (c'est la ligne : currentState_ = states_[nextState];).
Il est possible d'aller plus loin et de laisser cette responsabilité aux états concrets. Pour ce faire, il suffit de passer le contexte en paramètre aux fonctions qui vont modifier cet état.

III-D - Les états sous forme de singleton

Une implémentation fréquente du design pattern State est d'implémenter les états sous forme de singletons. On la trouve par exemple sur cet article de Stephen B. Morris[en].
Il y a plusieurs avantages à procéder ainsi. Tout d'abord, puisque chaque état est unique, c'est assez logique d'en faire des singletons. Ensuite, ça évite de faire des new et des delete pendant l'exécution.

En appliquant cette technique à l'exemple du paragraphe III-a, cela donnerait quelque chose comme ceci :

#include <iostream>
#include <string>
using namespace std;

class GameState
{
public:
void Action() { DoSomething(); }
private:
virtual void DoSomething() = 0 ;
};

class MovementState : public GameState
{
public:
static MovementState& GetInstance() { return instance_; }
private:
void DoSomething() { cout << "MovementState::DoSomething" << endl; }
private:
static MovementState instance_;
MovementState(){}
~MovementState(){}
};

class FightState : public GameState
{
public:
static FightState& GetInstance() { return instance_; }
private:
void DoSomething() { cout << "FightState::DoSomething" << endl; }
private:
static FightState instance_;
FightState(){}
~FightState(){}
};

MovementState    MovementState::instance_;
FightState        FightState::instance_;

class Game
{
public:
Game()
: m_mvtState( MovementState::GetInstance() )
, m_fightState( FightState::GetInstance() )
, m_currentState( &m_mvtState )
{}

void DoSomething()
{
m_currentState->Action();
}

void UpdateCurPhase( const std::string & stateName )
{
if ( stateName == "movement" )
m_currentState = &m_mvtState;
else
m_currentState = &m_fightState;
}

private:
MovementState&    m_mvtState;
FightState&    m_fightState;
GameState *    m_currentState;
};

int main()
{
Game game;
game.DoSomething();
game.UpdateCurPhase( "fight" );
game.DoSomething();
game.UpdateCurPhase( "movement" );
game.DoSomething();

cin.get();
return 0;
}

III-E - La machine à états selon Qt

Qt propose une interface très élaborée pour la création de notre propre machine à états : le framework « machine à états » de Qt.
Je vous propose ci-dessous un diagramme de classe très simplifié du patron état de Qt :

Qt state

Je n'en ai pas trop parlé jusqu'ici, mais la notion de transition est primordiale dans un automate à états. Il parait donc légitime de consacrer une (ou des) classe(s) à cette notion de transition. C'est (entre autres) ce que fait Qt : nous voyons clairement sur le diagramme ci-dessus que la machine à états comporte deux sortes d'objets : les états et les transitions.

IV - Annexes

IV-A - Liens

. Les diagrammes UML que j'ai dessinés pour cette page ont été faits avec UML Pad (qui ne fonctionne malheureusement que sous Windows pour l'instant).
. Les patterns du GoF appliqués à java sur developpez.net.
. Améliorez vos logiciels avec le pattern Etat, par Pierre Caboche
. La page Wikipédia sur le pattern State.
. Le pattern State du GoF.
. Un article de Stephen B. Morris sur le pattern State.

IV-B - Notes

À noter également que boost a implémenté une machine à états : The Boost Statechart Library (aussi connue sous le nom de boost fsm).

Si vous avez fait attention aux morceaux de code présents dans ce papier, vous vous aurez peut-être noté quelque chose de pas très habituel dans l'implémentation des états.

class State
{
public:
void Action() { return DoSomething(i); }
private:
virtual void DoSomething() = 0;
};

class StateA: public State
{
private:
void DoSomething();
};

class StateB: public State
{
private:
void DoSomething();
};

En effet, nous aurions pu faire plus simple en mettant directement DoSomething en public :

class State
{
public:
virtual void DoSomething() = 0;
};

class StateA: public State
{
public:
void DoSomething();
};

class StateB: public State
{
public:
void DoSomething();
};

Seulement cette dernière façon de faire n'est pas recommandée. Pour en savoir plus, je vous invite à regarder la FAQ sur le pattern NVI.

IV-C - Remerciements

- Un gros merci à 3DArchi qui m'a conseillé, corrigé, et beaucoup aidé.

- Merci à yan, koala, Alp, qui m'ont bien conseillé, et toute l'équipe de dvp.

IV-D - Commentaires

Tout commentaire est le bienvenu. Pour ce faire, vous pouvez m'envoyer un mp ou intervenir directement sur la discussion consacrée à cet article .