Embedded

Implementing a State Machine in C++17 – part 2

Wrzesień 23, 2019 0
Podziel się:

In my previous article we’ve talked about implementing a simple state machine based on a std::variant and other newer additions to the C++ standard. Even though the implementation had its merits it was far from being complete. In this article, we improve upon that design to make it more useful and easy to use. If you haven’t read the first part, I highly recommend that you do before diving into this article, as it heavily relies on code examples presented there.

A problem to solve

Let’s start with defining a problem that’ll serve as a testbed for new ideas. Previously a state machine representing basic door was used as an example. Sadly, a door that anyone can open is not very useful, so let’s change that. Let’s introduce a new state locked, so that only someone who knows the key could open the door. A sequence diagram for such state machine could look like this:

fsm 265x300 - Implementing a State Machine in C++17 - part 2

Besides an additional state, we’ve introduced two new events lock and unlock. Now, once the door is locked, the only way to open it, is to unlock it first. With all that in mind, we can try to implement such a state.

struct LockedState
{
    Nothing      handle(const OpenEvent&)   const { return {}; }
    Nothing      handle(const CloseEvent&)  const { return {}; }
    Nothing      handle(const LockEvent&)   const { return {}; }
    TransitionTo handle(const UnlockEvent&) const { return {}; }
};

Now, that’s a lot of boilerplate code! The state reacts only on unlock event but we had to provide actions for all 4 events. To make it even worse, we need to implement handlers for those two newly added events in closed and open states. To fix this, let’s provide a mechanism to collapse all similar event handlers.

template <typename Action>
struct ByDefault
{
    template <typename Event>
    Action handle(const Event&) const
    {
        return Action{};
    }
};

We can use this struct as a base for some of our states introducing some common behavior. Why is the action type parametrized you might ask? That’s because sometimes there’s a better action to invoke other than Nothing, like for example TransitionTo. Let’s see how this improves things when applied to closed state.

struct ClosedState : ByDefault<Nothing>
{
    using ByDefault::handle;

    TransitionTo<LockedState> handle(const LockEvent&) const { return {}; }
    TransitionTo<OpenState>   handle(const OpenEvent&) const { return {}; }
};

Better! But still not perfect 🙂 First of all, as we have handle method overloaded in ClosedState, we need to pull handle from ByDefault base class with a using declaration. Additionally, handlers for LockEvent and OpenEvent don’t do anything except returning a default constructed action object. This behavior could be shared in a helper base structure.

template <typename Event, typename Action>
struct On
{
    Action handle(const Event&) const
    {
        return {};
    }
};
struct ClosedState : ByDefault<Nothing>,
                     On<LockEvent, TransitionTo<LockedState>>,
                     On<OpenEvent, TransitionTo<OpenState>>
{
    using ByDefault::handle;
    using On<LockEvent, TransitionTo<LockedState>>::handle;
    using On<OpenEvent, TransitionTo<OpenState>>::handle;
};

Not much of an improvement since we still need to pull in handlers from all base classes. Fortunately, there’s a way to circumvent it. C++17 allows expanding parameter packs inside using declarations. We can use it to pull all overloads into a single base class.

template <typename... Handlers>
struct Will : Handlers...
{
    using Handlers::handle...;
};

Now we can get rid of all those using declarations.

struct ClosedState : public Will<ByDefault<Nothing>,
                                 On<LockEvent, TransitionTo<LockedState>>,
                                 On<OpenEvent, TransitionTo<OpenState>>>
{
};

Now, that’s much better 🙂 But our work is still far from complete. Even though we introduced a new locked state, we still don’t do any kind of verification. First of all, we need to store some value, let’s call it ‘key’, inside the state, which will be later used for access control. The issue here is that the states are currently default initialized by the state machine. We need to add a way to construct the states outside the state machine and pass them to the state machine constructor.

StateMachine(States... states) : states(std::move(states)...) { }

StateMachine() = default;

StateMachine(States... states)
    : states(std::move(states)...)
{
}

In essence, when we’re in a locked state we should only accept unlock events that have a matching ‘key’. This poses a problem since actions are returned from state handle methods and can have only one return type. We need to model somehow a situation where the result of an event can be an alternative to many possibilities. We can utilize std::variant for this task.

template <typename... Actions>
class OneOf
{
public:
    template <typename T>
    OneOf(T&& arg)
        : options(std::forward<T>(arg))
    {
    }

    template <typename Machine>
    void execute(Machine& machine)
    {
        std::visit([&machine](auto& action){ action.execute(machine); }, options);
    }

private:
    std::variant<Actions...> options;
};

And since, most of the time, we want to either do one thing or do nothing at all, as a convenience, another helper type can be introduced.

template <typename Action>
struct Maybe : public OneOf<Action, Nothing>
{
    using OneOf<Action, Nothing>::OneOf;
};

Now, with that in place, we can update both the unlock event and locked state

struct UnlockEvent
{
    uint32_t key;
};

class LockedState : public ByDefault<Nothing>
{
public:
    using ByDefault::handle;

    LockedState(uint32_t key)
        : key(key)
    {
    }

    Maybe<TransitionTo<ClosedState>> handle(const UnlockEvent& e) const
    {
        if (e.key == key) {
            return TransitionTo<ClosedState>{};
        }
        return Nothing{};
    }

private:
    uint32_t key;
};

Great! That’s exactly what we wanted! We’ve defined a state machine that resembles a door that can be unlocked only when the passed key matches the one stored in the state.

Taking things further

What if we wanted to model some kind of programmable door. Like a safe in some hotels, where you can define your own pin code, but you can do that only when the safe is unlocked. A sequence diagram for such door could look like this:

sequence 1 - Implementing a State Machine in C++17 - part 2

Locking and unlocking

Let’s start by adding a ‘newKey’ field to lock event. That’s not a big problem. The biggest hurdle is how to inform locked state about that new value? We could, for example, define a new action type that would update a given state. Even though that would solve our problem, it’s not the best solution, since it requires closed state to know the internals of a completely different state – locked.

The true problem that we need to solve lies even deeper. Instead of trying to pass this information from one state to another, we should focus on giving the state information when it was entered and under what circumstances. For example, we could use this information to open a socket or maintain a database connection for as long as we’re in that state and tear down everything once we leave.

Necessary changes

To start, we need to provide a bit more information to the actions. To call appropriate methods, TransitionTo action would need to know what’s the current state and what event triggered the action. Apart from that, we want to grab a reference to the newly selected state when we make a transition. Let’s update our state machine’s implementation to provide that extra information.

template <typename Event>
void handle(const Event& event)
{
    auto passEventToState = [this, &event] (auto statePtr) {
        auto action = statePtr->handle(event);
        action.execute(*this, *statePtr, event);
    };
    std::visit(passEventToState, currentState);
}

template <typename State>
State& transitionTo()
{
    auto& state = std::get<State>(states);
    currentState = &state;
    return state;
}

Now let’s update the TransitionTo action. We want to call onLeave method the on previous state and onEnter on the destination state, but how do we know that these methods are present? We could enforce it, just like it’s done with handle methods, but that would lead to a lot of unnecessary code. We can use SFINAE (link) to detect if such a method exists. If it does, we’ll call it, if not, we’ll simply ignore it.

You may ask why we didn’t use that trick with handle methods and implemented a bunch of helpers just to provide some default behavior? That’s because the situation is a little bit different. Formally speaking, a transition function should be defined for each state and each event. Furthermore, there are situations when we want to trigger a compilation error when we add a new event and one of the existing states doesn’t know how to handle it, instead of blindly ignoring it. With that in mind, let’s update the TransitionTo action.

template <typename TargetState>
class TransitionTo
{
public:
    template <typename Machine, typename State, typename Event>
    void execute(Machine& machine, State& prevState, const Event& event)
    {
        leave(prevState, event);
        TargetState& newState = machine.template transitionTo<TargetState>();
        enter(newState, event);
    }

private:
    void leave(...)
    {
    }

    template <typename State, typename Event>
    auto leave(State& state, const Event& event) -> decltype(state.onLeave(event))
    {
        return state.onLeave(event);
    }

    void enter(...)
    {
    }

    template <typename State, typename Event>
    auto enter(State& state, const Event& event) -> decltype(state.onEnter(event))
    {
        return state.onEnter(event);
    }
};

Thanks to SFINAE, we can detect if a onEnter or onLeave method was defined and act accordingly. The last thing to do is to implement an onEnter method for locked state

void onEnter(const LockEvent& e)
{
    key = e.newKey;
}

Wrapping things up

In this article, we explored how previous state machine implementation could be enhanced in order to support optional transitions and how to make it easier to use. States can now define custom onEnter and onLeave methods that will be called when the state is entered or left. If you want to play with that code, you can grab it here.

In the next part of the article, we’ll play with adding support for tracing and debugging information and we’ll try to infer a nice transition table solely based on the StateMachine’s type, so stay tuned! 🙂

Oceń ten post
Kategorie: Embedded
Michał Adamczyk
Autor: Michał Adamczyk
C++ programmer with 8 years of commercial experience interested in Clean Code and Software Craftsmanship in general. In his spare time plays video games, learns Haskell (over and over again), reads about AI and bakes bread.

Imię i nazwisko (wymagane)

Adres email (wymagane)

Temat

Treść wiadomości

Zostaw komentarz