Introduction

The code below finds its origin in the following reflexion.

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 so 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).

silly state machine

It is silly, but it contains a few of the features that, in my experience, are necessary in a state machine implementation:

1. Entry, exit and transition actions.
2. Guards (conditional transitions).
3. Event parameters (a free event signature would be nice).
4. Composite states (states that contain sub-states).
5. 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.
6. 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):

1. 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.
2. Guards are regular "if" or "switch" statements in event handlers.
3. Event parameters are regular event handler parameters. The event handler signature is free (and clutter-free).
4. Composite states are implemented by applying the same model recursively. In the sate machine above, the state "Left" contains a "ColorState" virtual 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).
5. Orthogonal states are managed by letting the FSM have several virtual state members instead of just one ("LevelState" and "DirectionState" in "Machine" in the example).
6. Access to the FSM members is given to all states through the FSM reference "m" (e.g. m.changedColor()).

Please comment

• 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 without planning for it 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?

Thanks in advance.

Talk is cheap, here comes the code

genericstate.h

#ifndef GENERICSTATE_H
#define GENERICSTATE_H

#include <memory>

#define StateRef std::unique_ptr // ugly but compatible with g++ 4.6

template <typename StateMachine, class State>
class GenericState
{
public:
    template <class ConcreteState>
    static void init(StateMachine &m, StateRef<State> &state) {
        state = StateRef<State>(new ConcreteState(m, state));
        state->entry();
    }

protected:
    explicit GenericState(StateMachine &m, StateRef<State> &state) :
        m(m), state(state) {}

    template <class ConcreteState>
    void change() {
        exit();
        init<ConcreteState>(m, state);
    }

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:
    class LevelState : public GenericState<Machine, LevelState> {
    protected:
        explicit LevelState(Machine &m, StateRef<LevelState> &state) :
            GenericState<Machine, LevelState>(m, state) {}
    public:
        virtual void liftUp() { unhandledEvent(); }
        virtual void bringDown() { unhandledEvent(); }
    };
    StateRef<LevelState> levelState;

    struct High : public LevelState {
        explicit High(Machine &m, StateRef<LevelState> &state) :
            LevelState(m, state) {}
        void entry() { print("entering High"); }
        void liftUp() { print("already High"); }
        void bringDown() { change<Low>(); }
        void exit() { print("leaving High"); }
    };

    struct Low : public LevelState {
        explicit Low(Machine &m, StateRef<LevelState> &state) :
            LevelState(m, state) {}
        void entry() { print("entering Low"); }
        void liftUp() { change<High>(); }
        void bringDown() { print("already Low"); }
        void exit() { print("leaving Low"); }
    };

private:
    class ColorState : public GenericState<Machine, ColorState> {
    protected:
        explicit ColorState(Machine &m, StateRef<ColorState> &state) :
            GenericState<Machine, ColorState>(m, state) {}
    public:
        virtual void paint(Color color) { (void)color; unhandledEvent(); }
    };

    struct Red : public ColorState {
        explicit Red(Machine &m, StateRef<ColorState> &state) :
            ColorState(m, state) {}
        void entry() { m.changedColor(); }
        void paint(Color color);
    };

    struct Blue : public ColorState {
        explicit Blue(Machine &m, StateRef<ColorState> &state) :
            ColorState(m, state) {}
        void entry() { m.changedColor(); }
        void paint(Color color);
    };

private:
    class DirectionState : public GenericState<Machine, DirectionState> {
    protected:
        explicit DirectionState(Machine &m, StateRef<DirectionState> &state) :
            GenericState<Machine, DirectionState>(m, state) {}
    public:
        virtual void paint(Color color) { (void)color; unhandledEvent(); }
        virtual void turnRight() { unhandledEvent(); }
        virtual void turnLeft() { unhandledEvent(); }
    };
    StateRef<DirectionState> directionState;

    struct Left : public DirectionState {
        explicit Left(Machine &m, StateRef<DirectionState> &state) :
            DirectionState(m, state) {}
        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 {
        explicit Right(Machine &m, StateRef<DirectionState> &state) :
            DirectionState(m, state) {}
        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 from the program

entering High
changed color
leaving High
entering Low
already Low
leaving Low
entering High
already High
unhandled event
changed color
unhandled event
changed color