This finds its origin in the following reflection. In their book from 1995, the so-called gang of four (GoF) described the state pattern. What they were actually telling us in their description, is that any object oriented language that implements dynamic polymorphism has an embedded finite state machine (FSM) engine. C++ is such a language, and the example code in the book is written in that language. Why then, do we have to use large frameworks, libraries and tools in order to implement state machines in C++?
I asked myself that question recently for a C++ project where I have the freedom to choose my tools. Since I have long been a supporter of the KISS-principle (keep it simple stupid), my first intention was to just apply the pattern as described in the book.
Basically, the state pattern tells us that the FSM should have a pointer member to a virtual state class, always pointing to a specialization of that class, that represents the current concrete state. It then delegates the events it receives to the state pointer, like this (quoting the book):
TCPConnection::ActiveOpen () {
_state->ActiveOpen(this);
}
where TCPConnection is the FSM and ActiveOpen() is an event.
However, the event handlers look like this:
void TCPClosed::ActiveOpen (TCPConnection* t) {
// send SYN, receive SYN, ACK, etc.
ChangeState(t, TCPEstablished::Instance());
}
where TCPClosed and TCPEstablished are concrete states.
Not so neat. I started to wonder if templates couldn't help me to parametrize the target state in ChangeState(). If the state had both a reference to the FSM and the ability to transform itself as a result of a transition, surely I would get a much simpler and cleaner syntax.
Example FSM
Let's assume that I have the following silly state machine to implement (made with ArgoUML, if anybody is curious).
It is silly, but it contains the features that, in my experience, are necessary in a state machine implementation:
- Entry, exit and transition actions.
- Guards (conditional transitions).
- Event parameters (a free event signature would be nice).
- Composite states (states that contain sub-states).
- Orthogonal states (also called and-states, which are semantically equivalent to separate simultaneous FSMs, but it is sometimes necessary to run them in the same class). E.g. LevelState and DirectionState are orthogonal states in the example.
- Access to FSM members (variables or functions).
The UML has a lot more than that, but I am not convinced that the rest is strictly necessary in the FSM implementation. After all, we have the rest of the programming language for that...
What I want is all you get
The kind of event handler I want is this:
void Machine::Red::paint(Machine::Color color)
{
if (color == BLUE)
change<Blue>();
}
where Machine is my FSM, Red the state, paint() the event, color an event parameter and Blue the target state for the transition. But you knew all that, it's in the diagram.
As the code below testifies (public domain, use it as you wish, but don't blame me - compiles with g++ 4.6, C++11 switched on), I have managed to implement the state machine depicted above, in such a simple syntax, with the help of a 40-line state template that I have called GenericState (genericstate.h, the rest is the state machine code):
- Entry and exit actions can be defined at any state level. Transition actions are programmed as regular instructions in the event handlers before the actual state transitions. There is, however, a difference with the UML in the order of execution: transition actions, exit actions (old state), entry actions (new state). The UML has exit, transition actions, entry. But mine is the same order as Miro Samek's model (http://www.state-machine.com/) - i.e. it is not uncommon and there is nothing wrong with it as long as it is consistent.
- Guards are regular "if" or "switch" statements in event handlers.
- Event parameters are regular event handler arguments. The event handler signature is free (and clutter-free).
- Composite states are implemented by applying the same model recursively. In the sate machine above, the state "Left" contains a
ColorStatevirtual state that can be "Red" or "Blue". However, when going from "Left" to "Right", the exit action from the current color will not be executed (contrary to the UML semantics, but not a practical problem I believe). - Orthogonal states are managed by letting the FSM have several virtual state members instead of just one (
LevelStateandDirectionStateinMachinein the example). - Access to the FSM members is given to all states through the FSM reference "m" (e.g.
m.changedColor()).
Questions:
- Any known similar implementation?
- Any obvious bug or hazard?
- Any obvious potential for improvement (performance, type safety in template use, etc.)?
- It looks like I have unintentionally applied the so-called "curiously recurring template pattern". Do you recognize any other pattern in my implementation? Any other pattern related comment?
- My implementation has a low RAM footprint (only one state instantiated at a time per FSM instance and orthogonal region) but a certain runtime cost: every state transition will incur the creation of a state instance and the destruction of another one on the heap. Comments about that?
- A reader of an earlier version commented off-line that my states were not flyweight as described by GoF. This basically means that my state instances cannot be shared between several state machine instances. I agree. I would not get such a simple syntax otherwise. I think the trade off was worth it. Comments?
genericstate.h
#ifndef GENERICSTATE_H
#define GENERICSTATE_H
#include <memory>
template <class State>
using StateRef = std::unique_ptr<State>;
template <typename StateMachine, class State>
class GenericState
{
public:
explicit GenericState(StateMachine &m, StateRef<State> &state) :
m(m), state(state) {}
template <class ConcreteState>
static void init(StateMachine &m, StateRef<State> &state) {
state = StateRef<State>(new ConcreteState(m, state));
state->entry();
}
protected:
template <class ConcreteState>
void change() {
exit();
init<ConcreteState>(m, state);
}
void reenter() {
exit();
entry();
}
private:
virtual void entry() {}
virtual void exit() {}
protected:
StateMachine &m;
private:
StateRef<State> &state;
};
#endif // GENERICSTATE_H
machine.h
#ifndef MACHINE_H
#define MACHINE_H
#include <string>
#include <iostream>
#include "genericstate.h"
class Machine
{
public:
Machine() {}
~Machine() {}
void start();
public:
enum Color {
BLUE,
RED
};
public:
void liftUp() { levelState->liftUp(); }
void bringDown() { levelState->bringDown(); }
void paint(Color color) { directionState->paint(color); }
void turnRight() { directionState->turnRight(); }
void turnLeft() { directionState->turnLeft(); }
private:
static void print(const std::string &str) { std::cout << str << std::endl; }
static void unhandledEvent() { print("unhandled event"); }
void changedColor() { print("changed color"); }
private:
struct LevelState : public GenericState<Machine, LevelState> {
using GenericState::GenericState;
virtual void liftUp() { unhandledEvent(); }
virtual void bringDown() { unhandledEvent(); }
};
StateRef<LevelState> levelState;
struct High : public LevelState {
using LevelState::LevelState;
void entry() { print("entering High"); }
void liftUp() { print("already High"); }
void bringDown() { change<Low>(); }
void exit() { print("leaving High"); }
};
struct Low : public LevelState {
using LevelState::LevelState;
void entry() { print("entering Low"); }
void liftUp() { change<High>(); }
void bringDown() { print("already Low"); }
void exit() { print("leaving Low"); }
};
private:
struct ColorState : public GenericState<Machine, ColorState> {
using GenericState::GenericState;
virtual void paint(Color color) { (void)color; unhandledEvent(); }
};
struct Red : public ColorState {
using ColorState::ColorState;
void entry() { m.changedColor(); }
void paint(Color color);
};
struct Blue : public ColorState {
using ColorState::ColorState;
void entry() { m.changedColor(); }
void paint(Color color);
};
private:
struct DirectionState : public GenericState<Machine, DirectionState> {
using GenericState::GenericState;
virtual void paint(Color color) { (void)color; unhandledEvent(); }
virtual void turnRight() { unhandledEvent(); }
virtual void turnLeft() { unhandledEvent(); }
};
StateRef<DirectionState> directionState;
struct Left : public DirectionState {
using DirectionState::DirectionState;
void entry() { ColorState::init<Red>(m, colorState); }
void paint(Color color) { colorState->paint(color); }
void turnRight() { change<Right>(); }
private:
StateRef<ColorState> colorState;
};
struct Right : public DirectionState {
using DirectionState::DirectionState;
void turnLeft() { change<Left>(); }
};
};
#endif // MACHINE_H
machine.cpp
#include "machine.h"
void Machine::start()
{
LevelState::init<High>(*this, levelState);
DirectionState::init<Left>(*this, directionState);
}
void Machine::Red::paint(Machine::Color color)
{
if (color == BLUE) change<Blue>();
else ColorState::paint(color);
}
void Machine::Blue::paint(Machine::Color color)
{
if (color == RED) change<Red>();
else ColorState::paint(color);
}
main.cpp
#include "machine.h"
int main()
{
Machine m;
m.start();
m.bringDown();
m.bringDown();
m.liftUp();
m.liftUp();
m.turnRight();
m.paint(Machine::BLUE);
m.turnLeft();
m.paint(Machine::RED);
m.paint(Machine::BLUE);
return 0;
}
Output
entering High changed color leaving High entering Low already Low leaving Low entering High already High unhandled event changed color unhandled event changed color
