[C++] A C++17 Statemachine using std::tuple and std::variant

May 8

Written By Thomas

Find this example herer on compiler explorer.

One of my favorite design patterns is the state machine pattern. You can trigger certain function when you enter or leave a state and can run different update methods depending on its state, just like illustrated bellow:

A simple statemachine with two states, where each states runs it’s own update method and transitions.

And then I used to write a statemachine like this:

#include <iostream>
#include <memory>

// an abstract state which holds on_update which we want to call
struct state 
{
    virtual ~state() = default;
    virtual void on_update() = 0;
};

// two specific states where we implement our functions which 
// we want to when we enter, leave and update the state
struct idle : public state 
{
    idle(){
        std::cout << "entering idle \n";
    }
    ~idle(){
        std::cout << "leaving idle \n";
    }
    void on_update() override {    
        std::cout << "still waiting \n";
    }
};
struct run : public state 
{
    run(){
        std::cout << "entering run \n";
    }
    ~run(){
        std::cout << "leaving run \n";
    }
    void on_update() override {
        std::cout << "we are running! \n";
    }
};

// a statemachine which holds the states and whenever certain conditions
// are fullfilled we can set a new state here with set_state 
class state_machine 
{
private:
    // set the initial state to idle
    std::unique_ptr<state> m_state = std::make_unique<idle>();

public:
    void set_state(std::unique_ptr<state> next) {
        m_state = std::move(next);
    }
    void on_update(){
        m_state->on_update();
    }
};



int main()
{
    state_machine machine;

    // update a couple of times 
    machine.on_update();
    machine.on_update();
    machine.on_update();
    // something happened, we want to change the state to run
    machine.set_state(std::make_unique<run>());
    // update a couple of times 
    machine.on_update();
    machine.on_update();
    machine.on_update();

    return 0;
}

What I don't like here and what we can do better

Basically this isn't too bad and if you're looking at other languages, like Java, I think this is the way the pattern suggests (maybe there are modern, different approaches in Java, I don't know and I'm not a Java developer).

But:

Things can go out of hand here when you have plenty of states
Maybe, depending where you create the states we'd need to seperate headers and bodies
Dynamic state allocation with std::unique_ptr<state>, we know all states at compile time

Let's create a new statemachine

When I started thinking about a new approach, it was something with templates, because we actually know all states at compile time. I had some ideas and found this article online. Ultimately I modified this statemachine a bit, where I'm happy now with.

Let's introduce std::tuple and std::variant and create a state machine. If you're not familiar with tuples, you can check out my article: Tuples From Scratch. In short:

std::tuple is like a list which holds all given types
std::variant is like a union where we can assign one value to it, which can be of different types

template <typename... States>
class state_machine
{
private:
    // the tuple m_states holds all states we'll define
    std::tuple<States...> m_states;
    // in this variant we hold a reference to the current state, it's initialized by the state at index 0
    std::variant<States*...> m_current_state{ &std::get<0>(m_states) };

public:
    // we can change a state by calling set state with a state type
    template <typename State>
    void set_state() {
        m_current_state = &std::get<State>(m_states);
    }

    // we can define certain events which call a dedicated state transition
    template <typename Event>
    void on_state_transition(const Event& event)
    {
        auto execute_on_call = [this, &event] (auto current_state) {
            current_state->on_state_transition(event).execute(*this);
        };
        // std::visit "visits" the current_state and calls the lambda with the current state
        // this means every possible state needs to implement the execute function inside the lambda
        std::visit(execute_on_call, m_current_state);
    }
    
    // we call on_update of each state also with std::visit like above
    void on_update()
    {
        auto execute_on_call = [this] (auto current_state) {
            current_state->on_update();
        };
        std::visit(execute_on_call, m_current_state);
    }
};

The state transitions

Since we introduced on_state_transition() as template in our state machine, we need to define state transitions types:

// the state transition type, where the template represents the target state
template <typename State>
struct state_transition_to
{
    // on execute we're setting the target state in our statemachine by calling execute()
    template <typename Statemachine>
    void execute(Statemachine& statemachine) {
        statemachine.template set_state<State>();
    }
};

// an invalid state transition which has an emptye execute() function
// we need this (guess what) for all transitions we wont support
struct invalid_state_transition 
{
    template <typename Machine>
    void execute(Machine&) { }
};

// specific state transition types we support
struct transition_to_run{};
struct transition_to_idle{};

The states

And also we need to define the state types in which our state machine can be:

// state definitions
struct idle;
struct run;
struct any_other_state;


// idle state which implements the methods to call by the statemachine
struct idle
{

    // regular on update call 
    void on_update() const {
        std::cout << "still waiting \n";
    }

    // specific transition to run, where we return the concrete state transition to run
    // to distinguish different state transitions, we use an empty function argument here
    state_transition_to<run> on_state_transition(const transition_to_run&) const{
        std::cout << "leaving idle with transition to run \n";
        return {};
    }

    // a template function to indicate all non supported state transitions.
    template<typename Transition>
    invalid_state_transition on_state_transition(const Transition&) const {
        std::cout << "state transition: " <<  typeid(Transition).name() << " is not supported in idle! \n";
        return {};
    }
};


// the same for our run state
struct run
{
    void on_update() const {
        std::cout << "we are running! \n";
    }

    state_transition_to<idle> on_state_transition(const transition_to_idle&) const {
        std::cout << "leaving run with transition to idle \n";
        return {};
    }

    template<typename Transition>
    invalid_state_transition on_state_transition(const Transition&) const {
        std::cout << "state transition: " <<  typeid(Transition).name() << " is not supported in run! \n";
        return {};
    }
};

Let's use this statemachine

Now we're done and can use this state machine. This is almost the same behaviour as with the previous one we had. There is a bit of a difference with entering and leaving the states, but on the contrary we have certain state transitions where we can implement some functionality. And:

There's no dynamic allocation and runtime polymorphism and we got rid of std::unique_ptr<states> here
The states are types and were all stored initially in the tuple
Switching states just changes the referens in the variant and doesn't create a new state on every change
All state transitions are empty types this doesn't cost much at runtime

// the alias for our state machine with state idle and run
// the statemachin is initialized with idle
using example_state_machine = state_machine<idle, run>;

int main()
{
    example_state_machine machine;

    // update a couple of times in idle
    machine.on_update();
    machine.on_update();
    machine.on_update();

    
    // something happende, we change state to run
    machine.on_state_transition(transition_to_run{});

    // update a couple of times in run 
    machine.on_update();
    machine.on_update();
    machine.on_update();

    // just for demonstration here
    // call a invalid state transition
    machine.on_state_transition(transition_to_run{});
    machine.on_state_transition(transition_to_run{});

    return 0;
}

If we wouldn't use a templated invalid state transition function...

... then we have to implement all possible state transitions. This is from my point of view a bit overwhelming and a lot of overhead. The number of statetransition is then ⁿ with n=states.

Inside the invalid state transition, you could throw a compiletime error or maybe SFINAE it out. But this is not in the scope of this article and I just illustrate the invalid state with a print to the terminal.

To illustrate the overhead just take a look at this arbitrary state and then imagine you'd have many more ...

// a defined state transition to any state
struct any_other_transition{};
// ... 
// any defined state
struct any_state;
// ... 
// the implementation of any state

struct any_state
{
    // updating any state here 
    void on_update() const {
    }

    // transition to idle
    state_transition_to<idle> on_state_transition(const transition_to_idle&) const {
        return {};
    }

    // invalid transition to run (just as an example, this would be invalid)
    invalid_state_transition on_state_transition(const transition_to_run&) const{
        return {};
    }

    // invalid transition to itself
    invalid_state_transition on_state_transition(const any_other_transition&) const{
        return {};
    }
    
    // and a lot of other states would follow....
};

Conclusion

Find this example herer on compiler explorer.

I really like this approach of a state machine, like i pointed out the advantages of it in this article. Feel free and play around with.

That's it for now.

Best Thomas

cppbest-practicesdeisgn-pattern

Thomas