A Simplistic Finite State Machine Generator

Question

I have designed a compile time Finite State Machine generator. I have chosen to use some of the features of C++17 such as parameter pack expansion, fold expressions and lambdas to keep the complexity of this class structure and its hierarchy as simple and readable as possible.

It is currently in its infancy as I have only just created the basic shell, needed constructors and functionality to add transition states to previous existing states.

My design by intent is that the size of the FSM has to be known at compile time and the States have to be created before hand as the FSM class's constructor requires the appropriate amount of states to be constructed.

Once the FSM is constructed, its size can not be changed nor can any other states be added or removed from the fsm.

I chose to do it this way since a Finite State Machine has a "Finite" amount of states; otherwise it would just be an Arbitrary State Machine.

---

Here is my test application, source code and output:

main.cpp

#include <iostream>
#include <string>

#include "FSM.h"

int main() {
    const u16 size = 7;
    State<size> Idle("Idle", 0), Init("Init", 1), Fetch("Fetch", 2),
                Load("Load", 3), Read("Read", 4), Write("Write", 5), 
                Stop("Stop", 6);

    FiniteStateMachine<size> fsm( Idle, Init, Fetch, Load, Read, Write, Stop );

    fsm.addStateTransition(Idle, Init, Fetch, Load);
    fsm.addStateTransition(Init, Idle, Load, Read);
    fsm.addStateTransition(Fetch, Read, Load, Write, Idle);
    fsm.addStateTransition(Load, Read, Write, Fetch, Idle, Stop);
    fsm.addStateTransition(Read, Load, Fetch, Idle, Stop);
    fsm.addStateTransition(Write, Idle);
    fsm.addStateTransition(Stop, Idle);


    for (auto& state : fsm.states_) {
        std::cout << "State " << state.id_ << " (" << state.value_.to_string() << 
            ") has a transitions to: \n";

        for (auto& next : state.nextStates_) {
            std::cout << "\t" << next->id_ << " (" << next->value_.to_string() << ")\n";
        }
    }
    std::cout << '\n';

    return 0;
}

FSM.h

#pragma once

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <iostream>
#include <memory>
#include <string>
#include <utility>
#include <vector>

using u16 = std::uint16_t;

// Used to define the size of the bitset to represent
// all possible states with the fewest amount of binary digits.
constexpr unsigned numBits(unsigned n) {
    return n < 2 ? n : 1 + numBits(n >> 1);
}

template<u16 N>
class State {
public:
    const std::string id_;
    std::bitset<numBits(N)> value_;
    std::vector<std::shared_ptr<State<N>>> nextStates_;

    State(const std::string id, const u16 value) : id_{ id }, value_{ value } {}

    // Function to all of this state's next states it is public for now
    // but in a furture revision I plan on making this private and
    // a friend to the FSM class as it will only be callable from with
    // that class. The user would use the FSM's addStateTransition() function
    // for its public interface.
    template<typename... States>
    void addTransitions(const States& ... states) {
        // Use a Lambda to create a shared_ptr<State> and to add it
        // to the corresponding vector
        auto transition = [&](auto state) {
            auto ptr = std::make_shared<State>(state);
            nextStates_.emplace_back(std::forward<std::shared_ptr<State>>(ptr));
            return true;
        };

        const bool success = (transition( states ) && ...);
        if (!success)
            std::cout << "Failed to add transition states.\n";
    }

    // Operator== is needed for the FSM class, if both the
    // string id_ and the bitset value_ are equal then it is the same state.
    bool operator==(const State<N>& other) {
        return ((id_ == other.id_) && (value_ == other.value_));
    }
};

template<u16 N>
class FiniteStateMachine {
public:
    std::vector<State<N>> states_;  

    // There is no default constructor!
    FiniteStateMachine() = delete;

    // The parameter pack size must be equal to the number of States provided by N
    template<typename... States>    
    FiniteStateMachine(States&&... states) : states_{ std::move(states)... } {
        static_assert((sizeof...(states) == N), "The number of states passed in does not match this State Machines size.");
        // Let's keep the vector as small as possible!
        states_.shrink_to_fit();
    }

    // Public interface function to add transition states.
    // The first state passed is the current state and the parameter pack
    // is all of that state's next states
    template<typename Current, typename... NextStates>
    void addStateTransition(const Current& currentState, const NextStates& ... nextStates) {
        // First check if all of the states passed in exist within our container
        // if any one of them fails then it is an invalid State for this State machine
        // and return early. The use of a lambda here is quite practicle since I'm
        // using fold expressions and recursion to check and add all of the state transitions.

        auto current = std::find(states_.begin(), states_.end(), currentState);
        if (current == states_.end()) {
            std::cout << "Could not find the current state: " << current->id_ << " in this State Machine.";
            return;
        }

        auto lookup = [&](auto state) {
            // single find
            auto it = std::find(states_.begin(), states_.end(), state);
            if (it == states_.end()) {
                std::cout << "Could not find " << state.id_ << " in this State Machine.";
                return false;
            }
            return true;
        };
        bool const allFound = (lookup(nextStates) && ...);

        if (!allFound) {
            return;
        }

        current->addTransitions(nextStates...);
    }
};

Output

State Idle (000) has a transitions to:
        Init (001)
        Fetch (010)
        Load (011)
State Init (001) has a transitions to:
        Idle (000)
        Load (011)
        Read (100)
State Fetch (010) has a transitions to:
        Read (100)
        Load (011)
        Write (101)
        Idle (000)
State Load (011) has a transitions to:
        Read (100)
        Write (101)
        Fetch (010)
        Idle (000)
        Stop (110)
State Read (100) has a transitions to:
        Load (011)
        Fetch (010)
        Idle (000)
        Stop (110)
State Write (101) has a transitions to:
        Idle (000)
State Stop (110) has a transitions to:
        Idle (000)

---

I know I can wrap this in a namespace so I don't need that as a suggestion, but I would like to know the following about my code:

• I'd like to know your thoughts and concerns about this code.
• Do you think it is readable, manageable, explicit in its intent, etc.?
• Are there any code smells, gotchas, missed corner cases, etc.?
• Is there anything that can be done to improve this?

These are future plans that I have:

• -Note- *I do know that FSM's sometimes have conditions for a specific state to transition to another when their input relies on their current state such as the difference between a Moore and a Mealy machine.
• The ability for a state to add input values that may or may not change their state. For this the states would also have to have a condition variable added to their core component.
• The ability to return its data which may or may not effect any of the states it points to.
• I may add another vector that would represent previous states so that a current active state is aware of what state activated it. For example: Init goes to Idle, Load and Read by my example. If we are now in the Load state it could of been Idle, Fetch, or Read that triggered it. It might be useful to have this backtracking history available for future references.

To finish up; I would also be interested in your suggestions of what kind of features, functionality and support you would like to see in this kind of class structure, application.

---

Just a little bit on the side note:

Not included here but within the same project I have another small lightweight class template that takes 2 unsigned values for its template parameters one to represent the amount of inputs, and the other to represent the amount of binary logical functions to be performed on that set of inputs. The class will then generate a table with the corresponding inputs and outputs in binary and will display a canonical truth table. Each of my binary functions can take any number of inputs, they are independent functions that are separate from the Binary Truth Table Generator. I haven't posted it here on Code Review just yet as I'm still currently working on it. However, I may end up combining the two in order to try and generate transition tables, and K-Maps!

---

-Edit-

After looking at the code and considering the overall structure of what a finite state machine is I have determined that one could add two states with the same name as long as their values are different for example: A state machine may have an Idle state that is represented by say both 000 and 111, on the other hand what would be invalid would be having two states with the same value with different string names or ids! For example: having something like Go Right(010) and Go Left(010) would be invalid as two different states can not share the same value or bit representation since this would cause ambiguity! This will be considered under the list of future plans.

Answer 1

Avoid declaring u16.

You are defining u16 to be equal to std::uint16_t. Is this because you just want to save some keystrokes, or is it because the u16 represents something distinct in your class? If you want it to be a value representing the number of states or index of a state, then make this more explicit:

using state_size_t = std::uint16_t;

Now when you ever decide to change the amount of bits used for state sizes/indices, you only have to change one line.

Another issue with u16 is that it's a very generic name, and by just declaring it in the global namespace, you risk conflicting with other libraries that potentially make the same mistake.

Avoid exposing implementation details to the global namespace

numBits() is some function you just want to use in some of the member functions of class State. Similar to u16, you don't want this in the global namespace where it could cause conflicts. Just make it part of State:

template<u16 N>
class State {
    static constexpr unsigned numBits(u16 n) {...}

public:
    ...
};

Even better would be to declare a namespace for your library, and put everything in that namespace, including the using declaration.

There's no need to write State<N> inside State itself

Inside a templated class, you don't have to add the template parameters each time you use the type. So just write:

std::vector<std::shared_ptr<State>> nextStates_;

Note that you already use the type State without <N> in many places.

Don't use a std::bitset<> with only one bit set

When you create a State, you copy the u16 value to a std::bitset<> that might be very large (8 kilobytes if N equals 65535). But it's just a copy of the value, so store it as a u16.

Avoid pointer references for the list of transitions

With pointers, you always have to worry about ownership, and whether they are valid or not. They also restrict moving and copying of variables. And in this case, you don't need pointers to refer to states, since they already have unique identifiers in the form of a u16. So just write:

std::vector<u16> nextStates_;

Or, if you expect the transition table to be dense, it might make sense to make this a bitset:

std::bitset<numBits(N)> nextStates_;

And in addTransition(), write:

nextStates_.set(state.value_);

Use std::array<> instead of std::vector<> if you know the size up front

In class FiniteStateMachine, you already know the number of states you are going to support. So just write:

std::array<State, N> states_;

This has the advantage that it doesn't require heap allocations, and you don't have to shrink to fit in the constructor.

Can states be reused in different state machines?

One issue with your design is that you can declare a State, and it is not tied to a state machine. However, when creating a state machine and adding state transitions, those transitions are actually stored inside the State variable, not inside the FiniteStateMachine. So this effectively makes reusing states impossible.

You could make states reusable, by moving the list of possible transitions to FiniteStateMachine itself. There are various ways possible, for example you could do:

template<u16 N>
class FiniteStateMachine {
public:
    std::vector<std::pair<State, std::vector<State>>> states_;
    ...

So each element of states_ is a State plus a vector of other States it can transition to. Or if you have dense transition tables:

    std::vector<std::pair<State, std::bitset<numBits(N)>>> states_;