Finite State Machines are a very useful concept that allows modeling complex behavior. The basic idea is quite simple. We have a set of possible states and we define rules that govern transitions between the current state and some other state upon receiving an event. So how to implement one in C++17? Of course, there is a multitude of ways to do it. In this article, we try to explore another possibility based on several newer additions to the C++ standard.
Let’s build a State Machine
So what’s a state anyway? In reality, it can be anything. For the sake of this article let’s just assume that’s an arbitrary object. That object’s type can be used to distinguish it from other states. This way we don’t have to maintain a separate list of all possible states (like an enumeration for example). Furthermore, we don’t want to enforce any form of relationship between those types to keep them as separate as possible. So how to pass and store those completely independent types? A variadic template containing a std::tuple (both introduced in C++11) can help us with that.
template <typename... States>
class StateMachine
{
private:
std::tuple<States...> states;
};
There are a few noteworthy things about this class. First of all, StateMachine has no prior information about the states it contains. Additionally, we don’t have to worry about their lifetime as it’s tied to the lifetime of the machine itself.
Next on our todo list is to keep track which state is currently selected. Normally a plain pointer or a reference would suffice, but that’s not going to work in this case, because it’s impossible to select a single type that would accept all possible state types (besides void*, but that would be useless for us). As we’re trying to store heterogeneous data types we can use the std::variant (C++17) for that task. Since std::variant disallows using it with references, we have to use plain pointers. Additionally, we assume that the first state type provided to the state machine is the initial state.
std::variant<States*...> currentState { &std::get<0>(states) };
Now is time to add a method to change the current state of the machine. Once again, since we distinguish states by their type, it has to be a template method.
template <typename State>
void transitionTo()
{
currentState = &std::get<State>(states);
}
So far so good. Now we need to pass event information to the machine. That raises a fundamental question – what kind of events do we want to handle? As the states are doing the actual work let’s simply pass the event to the current state and let it handle it. In other words, the machine is able to accept all events that its states are capable of handling.
template <typename Event>
void handle(const Event& event)
{
auto passEventToState = [&event] (auto statePtr) {
statePtr->handle(event);
};
std::visit(passEventToState, currentState);
}
This change introduced a dependency on the type of state. Each time an event of type T is handled by the machine, the compiler ensures that all the state types have a ‘handle’ method that accepts an event of type T.
The last thing that’s missing is the ability to transition to another state based on the passed event. We need to figure out how to instruct the machine to perform a transition while being inside an event handler in a given state. There are some obstacles though. We don’t want to pass the machine type to the states, because we don’t want to tie them together. To fix this issue let’s return an intermediate object from the state’s ‘handle’ method that will describe what action should the machine take.
template <typename State>
struct TransitionTo
{
template <typename Machine>
void execute(Machine& machine)
{
machine.template transitionTo<State>();
}
};
Formally speaking, after receiving an event a machine should always transition to some state, even if it’s the same state as current. On the other hand, there are situations when we want to ignore an event and skip performing any action on the machine. To model this kind of behaviour we introduce a new action type.
struct Nothing
{
template <typename Machine>
void execute(Machine&)
{
}
};
Now we just need to plug it into our current StateMachine implementation.
template <typename Event>
void handle(const Event& event)
{
auto passEventToState = [this, &event] (auto statePtr) {
statePtr->handle(event).execute(*this);
};
std::visit(passEventToState, currentState);
}
Assuming we have some state Foo and we want to switch to state Bar on Trigger event and do nothing on Ignored event, the state’s implementation could look like this:
struct Foo
{
TransitionTo<Bar> handle(const Trigger& event)
{
/* some important calculations etc. */
return {};
}
Nothing handle(const Ignored&)
{
return {};
}
};
Example
Let’s see how it all works together by implementing a simple state machine representing a door. There are two states (Closed and Open) and two events (Open, Close). This is how the transition diagram looks like:
#include <iostream>
#include <tuple>
#include <variant>
#include <functional>
template <typename... States>
class StateMachine
{
public:
template <typename State>
void transitionTo()
{
currentState = &std::get<State>(states);
}
template <typename Event>
void handle(const Event& event)
{
auto passEventToState = [this, &event] (auto statePtr) {
statePtr->handle(event).execute(*this);
};
std::visit(passEventToState, currentState);
}
private:
std::tuple<States...> states;
std::variant<States*...> currentState{ &std::get<0>(states) };
};
template <typename State>
struct TransitionTo
{
template <typename Machine>
void execute(Machine& machine)
{
machine.template transitionTo<State>();
}
};
struct Nothing
{
template <typename Machine>
void execute(Machine&)
{
}
};
struct OpenEvent
{
};
struct CloseEvent
{
};
struct ClosedState;
struct OpenState;
struct ClosedState
{
TransitionTo<OpenState> handle(const OpenEvent&) const
{
std::cout << "Opening the door..." << std::endl;
return {};
}
Nothing handle(const CloseEvent&) const
{
std::cout << "Cannot close. The door is already closed!" << std::endl;
return {};
}
};
struct OpenState
{
Nothing handle(const OpenEvent&) const
{
std::cout << "Cannot open. The door is already open!" << std::endl;
return {};
}
TransitionTo<ClosedState> handle(const CloseEvent&) const
{
std::cout << "Closing the door..." << std::endl;
return {};
}
};
using Door = StateMachine<ClosedState, OpenState>;
int main()
{
Door door;
door.handle(OpenEvent{});
door.handle(CloseEvent{});
door.handle(CloseEvent{});
door.handle(OpenEvent{});
return 0;
}
Above code gives us the following output:
Opening the door...
Closing the door...
Cannot close. The door is already closed!
Opening the door...
Wrapping it all up
Of course, the above implementation is far from being complete. There are several questions that need to be answered:
- What if the states are not trivially constructible and would require passing some arguments during initialization?
- What if we want to decide in runtime to which state we want to transition to based on the information present in the event?
- Is there a way to generate a visual description of the state machine from the code itself?
We’ll try to tackle these questions in the next part of this article.
Leave a comment