Yet another finite state machine in C++

Question

I know there are several implementation of FSM in C++ containing different set of features and written in different styles. Nevertheless, I've decided to write my own.

Here are some key points :

• c++17 (not later)
• no need for the state.entry / state.exit functionality
• number of states ≤ 10
• I find it quite convenient to represent FSM as a class when states and transitions have access to data members

fsm.hpp

#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
#include <type_traits>
template<class TMachine, typename TEvent, typename TState, TState initial>
struct FSM
{
 static_assert(std::is_enum<TEvent>::value);
 static_assert(std::is_enum<TState>::value);
 typedef bool (TMachine::*EventAction_t)();
 typedef void (TMachine::*TransitionAction_t)();
 struct Transition
 {
 TState from;
 TEvent event;
 TState to;
 TransitionAction_t action { &TMachine::noAction };
 };
 typedef std::map<TState, EventAction_t> StateMap;
 typedef std::vector<Transition> TransitionList;
 void process(const TEvent event)
 {
 auto it = std::find_if(transitions.begin(), transitions.end(),
 [event, this](const auto& tr)
 {
 return tr.event == event and tr.from == currentState;
 });
 if(it == transitions.end())
 return;
 (static_cast<TMachine*>(this)->*(it->action))();
 currentState = it->to;
 }
 bool step()
 {
 if(states.find(currentState) == states.end())
 return false;
 return (static_cast<TMachine*>(this)->*states[currentState])();
 }
 void noAction()
 {
 std::cout << "No action\n"; // debug
 }
 static TransitionList transitions;
 static StateMap states;
 TState currentState { initial };
};

Usage

Let's implement the coffee machine :

fsm of coffee machine

#include <iostream>
#include <cstdint>
#include "fsm.hpp"
enum class State_t : uint8_t
{
 eIdle,
 eWait4Money,
 eWait4Coffee,
 ePowerOff,
};
enum class Event_t : uint8_t
{
 eMoneyInserted,
 eCoffeeButtonPressed,
 eTimeoutElapsed,
 ePowerOff,
};
struct CoffeeMachine : public FSM<CoffeeMachine, Event_t, State_t, State_t::eIdle>
{
 bool onIdle()
 {
 std::cout << "FSM :: I'm waiting for a new customer ($ earned: " << moneyEarned << ")\n";
 return true;
 }
 bool onWait4Money()
 {
 std::cout << "FSM :: Insert money, please\n";
 return true;
 }
 bool onWait4Coffee()
 {
 std::cout << "FSM :: Choose a beverage, please\n";
 return true;
 }
 bool onPowerOff()
 {
 std::cout << "FSM :: I need some sleep, goodbye...\n";
 return false;
 }
 void onMoneyInserted()
 {
 moneyEarned++;
 }
 unsigned int moneyEarned = 0;
};
template<>
CoffeeMachine::StateMap FSM<CoffeeMachine, Event_t, State_t, State_t::eIdle>::states =
{
 { State_t::eIdle, &CoffeeMachine::onIdle },
 { State_t::eWait4Money, &CoffeeMachine::onWait4Money },
 { State_t::eWait4Coffee, &CoffeeMachine::onWait4Coffee },
 { State_t::ePowerOff, &CoffeeMachine::onPowerOff },
};
template<>
CoffeeMachine::TransitionList FSM<CoffeeMachine, Event_t, State_t, State_t::eIdle>::transitions = {
 // From // Event // To // Action
 { State_t::eIdle, Event_t::eCoffeeButtonPressed, State_t::eWait4Money },
 { State_t::eIdle, Event_t::ePowerOff, State_t::ePowerOff },
 { State_t::eWait4Money, Event_t::ePowerOff, State_t::ePowerOff },
 { State_t::eWait4Money, Event_t::eMoneyInserted, State_t::eWait4Coffee, &CoffeeMachine::onMoneyInserted },
 { State_t::eWait4Money, Event_t::eTimeoutElapsed, State_t::eIdle },
 { State_t::eWait4Coffee, Event_t::eCoffeeButtonPressed, State_t::eIdle },
 { State_t::eWait4Coffee, Event_t::eTimeoutElapsed, State_t::eIdle },
};
int main()
{
 CoffeeMachine fsm;
 while(fsm.step())
 {
 std::cout << "Choose your destiny [p - power, m - money, c - coffee] : ";
 char input = 't';
 std::cin >> input; 
 Event_t e = Event_t::eTimeoutElapsed;
 switch(input)
 {
 case 'p' :
 e = Event_t::ePowerOff;
 break;
 case 'm' :
 e = Event_t::eMoneyInserted;
 break;
 case 'c' :
 e = Event_t::eCoffeeButtonPressed;
 break;
 default :
 e = Event_t::eTimeoutElapsed;
 break;
 }
 fsm.process(e);
 }
 return 0;
}

I don't like the boilerplate of the specialization of the state and transition list, but I cannot see how I could do it less verbose. So what do you think?

• kebs: sorry, unrelated comment to your question, but in case you want to explore other stuff, you may have a look here: github.com/skramm/spaghetti (disclaimer: author here).

Answer 1

Don't use CRTP

I don't like the boilerplate of the specialization of the state and transition list, but I cannot see how I could do it less verbose.

The problem comes from the curiously recurring template pattern. It is limited in what it can do, since at the time the base class is instantiated, the derived class is not fully defined yet. So let this idea go. Instead, don't derive CoffeeMachine from anything, but instead write FSM such that you can write this in main(), without needing any other changes there:

FSM<CoffeeMachine> fsm;

To make this actually work, some things need to happen:

Move information about the state machine into CoffeeMachine

The state map and transition list now have to go into CoffeeMachine, as there is no FSM<CoffeeMachine>. But we don't want CoffeeMachine to know too much about how FSM actually wants to store its data. The only thing CoffeeMachine knows is the list of states and the list of transitions. We can encode that using constexpr arrays. First, we need to define some helper structs though:

template<typename T>
struct FSMState {
 typename T::State state;
 bool (T::*action)() = {};
};
template<typename T>
struct FSMTransition {
 typename T::State from;
 typename T::Event event;
 typename T::State to;
 void (T::*action)() = {};
};

Now we can move the enums and the state and transition lists into CoffeeMachine:

class CoffeeMachine {
 enum class State {
 Idle,
 ...
 };
 enum class Event {
 MoneyInserted,
 ...
 }
 ...
 static constexpr FSMState<CoffeeMachine> states[] = {
 {State::Idle, &CoffeeMachine::onIdle},
 ...
 };
 static constexpr FSMTransition<CoffeeMachine> transitions[] = {
 {State::Idle, Event::CoffeeButtonPressed, State::Wait4Money},
 };
 static constexpr State initialState = State::Idle;
};

So FSMState<CoffeeMachine> and FSMTransition<CoffeeMachine> look CRTP-ish, but here it's fine.

Make FSM build the maps

Now that the states and transitions are defined in the object we want to make a finite state machine for, FSM has to turn that into something it can efficiently query at runtime. You already used a std::map for the states, which is better than a std::vector, but even better is a std::unordered_map. Similarly, each state should have a map from events to the destination state and any action that needs to be performed. You can write it like so:

template<class T>
struct FSM
{
 using State = typename T::State;
 using Event = typename T::Event;
 using EventAction = bool (T::*)();
 using TransitionAction = void (T::*)();
 struct TransitionInfo {
 State to;
 TransitionAction action{};
 };
 struct StateInfo {
 EventAction action{};
 std::unordered_map<Event, TransitionInfo> transitions;
 };
 State currentState{T::initialState};
 std::unordered_map<State, StateInfo> states;

First some using declarations (which are a better form of typedef) to simplify writing types, then some helper structs, and finally there is just one map, states, which contains for each state both its action and the possible transitions. Now we just need to fill it in at construction time:

public:
 FSM() {
 for (auto& state: T::states) {
 states[state.state].action = state.action;
 }
 for (auto& transition: T::transitions) {
 states[transition.from].transitions[transition.event] = {
 transition.to,
 transition.action
 };
 }
 }

But that's not enough, because where is the CoffeeMachine object itself?

Make FSM own a CoffeeMachine object

As there is no longer a base class and derived class that combined the state of both FSM and CoffeeMachine, FSM should now explicitly instantiate a CoffeeMachine object. And since CoffeeMachine could have a constructor, you want to be able to pass any arguments to that constructor. You can do that like so:

template<typename T>
class FSM {
 ...
 T self;
public:
 template<typename... Args>
 FSM(Args&&... args): self{std::forward<Args>(args)...} {
 ...
 }

Now you have all the information to step() and process() events:

 void process(const Event event)
 {
 const auto& transitions = states[currentState].transitions;
 if (auto it = transitions.find(event); it != transitions.end()) {
 std::invoke(it->second.action, self);
 currentState = it->second.to;
 }
 }
 bool step()
 {
 if (states[currentState].action) {
 return std::invoke(states[currentState].action, self);
 }
 return false;
 }
};

I used std::invoke() here to avoid the horrible member pointer syntax. With this in place, your code should work, without needing overly verbose specialization. I might have overlooked some way to have things be automatically deduced.

Note that in main() you now have to write CoffeeMachine::Event instead of Event_t, but you can just write using Event_t = CoffeeMachine::Event. Alternatively, you can keep the enum definitions outside CoffeeMachine, and just declare using Event = ::Event_t inside CoffeeMachine, although I recommend avoiding polluting the global namespace with something as generically named as Event_t.

• LRDPRDX: Quite nice. I like it. Thank you. But there are several points: "you now have to write CoffeeMachine::Event instead of Event_t, but you can just write using Event_t = CoffeeMachine::Event" -- No, no, You are right. No need to make enums global. That just was for the demo of the general idea.| I would avoid duplication of the actions type by declaring type inside FSMState and then in using it inside StateInfo : FSMState<T>::Action action. I think in process we need a check for validity of the pointer to member function like you did in the step member function.
• LRDPRDX: And for the record. NIT. Returning false in case of the absence of a state action is different from my initial intention -- I would return true instead because returning false means FSM termination. Of course, it can be customizable -- just to be said.
• LRDPRDX: And I was trying to understand why did you replace one array of transitions with two maps. The only thing that comes to my mind is query performance. So inside process you quickly find if there is a transition from the current state and only then you are querying for the event. Is my reasoning correct ?
• LRDPRDX: And another thing :). You are assuming states[currentStates] is valid always but it should be checked also I believe.
• G. Sliepen: About the maps: yes. Searching through a std::vector scales as O(N), where N is the number of transitions. With std::unordered_map, it's O(1). For std::map and std::unordered_map, states[currentStates] is always valid. If the element with key currentState did not exist before, it will add it automatically. It uses the default constructor to initialize it.