Object Oriented Finite State Machine

Question

I wrote a little library for myself: implementing a generic finite state machine. I will be using this library in class assignments.

I clearly have little understanding of C++ templates because most changes I make break it and take around 30 minutes to debug each. So I would like some review especially regarding my use of templates: are there better ways, can I make it more readable, etc. I feel like my source files are unnecessarily bloated due to templates.

I also want to know how well I followed C++ conventions.

Additionally, I am concerned that my fsm is strange in implementation. I have 4 different ways to map states in the finite state machine, all of which are stored in different data-structures. This might make it hard to use, but I couldn't think of a better way that wasn't too difficult to use (I want convenience when defining a state machine). Furthermore, I believe that it would be best if my fsm class inherited from some base_fsm or something of the like, but I have no idea how to get that to work in a reasonable manner.

fsm.h

#pragma once

/*
A library to define a Finite State Machine (fsm).
*/

#include <map> // std::map
#include <tuple> // std::pair
#include <vector> // std::vector
#include <functional> // std::function

/*
A namespace for extra library classes / functions.
*/
namespace extra
{
    /*
    An implementation of an fsm.
    This class implements a Moore state machine.
    */
    template<
        typename Input, // The input that the fsm expects to receive
        typename Output, // The output that the fsm will output
        typename State // The type of state that the fsm will walk through. Recommended to be an enum
    >
    class fsm
    {
        friend class builder;
    public:
        class builder;

        fsm();
        fsm(const fsm & other);
        fsm(fsm && other);
        fsm & operator=(const fsm & other);
        fsm & operator=(fsm && other);

        void advance(const Input&); // Advance the fsm to the new state
        Output get_output() const; // Get the output of the fsm at the state.
        bool has_output() const; // Get whether the fsm can return an output
        State get_current_state() const; // Get the current state of the fsm
        const std::vector<Input>& get_accumulator() const; // Get the current accumulator for the fsm. This contains all inputs from the last reset_accumulator() until now.
        void reset_accumulator(); // Resets (ie clears) the accumulator
        void reset(); // Reset to initial state and call reset_accumulator()
    private:
        State initial_state;
        State cur_state;
        std::vector<Input> accumulator;
        builder details;

        fsm(builder);
    };

    /*
    A class for building an fsm.
    */
    template<typename Input, typename Output, typename State>
    class fsm<Input, Output, State>::builder
    {
        friend class fsm<Input, Output, State>;
    public:
        builder();
        builder(State starting_state);
        builder(const builder & other);
        builder(builder && other);
        builder & operator=(const builder & other);
        builder & operator=(builder && other);

        /* defines the initial state of the fsm */
        builder & starting_state(State state);
        /*
        Binds an entrance into the given state to the given callback. The Input argument to the
        callback is the input that made the machine go into the given state
        */
        builder & bind(State toBindTo, std::function<void(State, Input)> callback);
        /* Map from `from` to `to` when receiving the input `trigger` */
        builder & map(State from, Input trigger, State to);
        /* Map from `from` to `to` when the given function returns true */
        builder & map(State from, std::function<bool(Input)>, State to);
        /* Map from any state to `to` when receiving the input `trigger`. Low priority */
        builder & map(Input trigger, State to);
        /* Map from `from` to `to` when receiving any input whatsoever. Lowest priority. */
        builder & map(State from, State to);
        /* Return `result` when the fsm is at the current output */
        builder & map_output(State, Output result);
        /* Build the finite state machine */
        fsm<Input, Output, State> build();

    private:
        State initial_state;
        std::map<State, std::function<void(State, Input)> > state_bindings;
        std::map<State, State> default_state_map;
        std::map<State, std::pair<std::function<bool(Input)>, State> > function_state_map;
        std::map<Input, State> default_char_map;
        std::map<std::pair<State, Input>, State> state_map;
        std::map<State, Output> output_map;
    };
}
#include "fsm.cpp"

fsm.cpp

#include "fsm.h"

namespace extra
{
    template<typename Input, typename Output, typename State>
    fsm<Input, Output, State>::fsm() {}

    template<typename Input, typename Output, typename State>
    fsm<Input, Output, State>::fsm(builder builder)
        : initial_state{ builder.initial_state }
        , cur_state{ builder.initial_state }
        , details{ builder }
    {}

    template<typename Input, typename Output, typename State>
    fsm<Input, Output, State>::fsm(const fsm<Input, Output, State> & other)
        : initial_state{ other.details.initial_state }
        , cur_state{ other.details.initial_state }
        , details{ other.details }
    {}

    template<typename Input, typename Output, typename State>
    fsm<Input, Output, State>::fsm(fsm<Input, Output, State> && other)
        : initial_state{ other.details.initial_state }
        , cur_state{ other.details.initial_state }
        , details{ other.details }
    {}

    template<typename Input, typename Output, typename State>
    fsm<Input, Output, State> & fsm<Input, Output, State>::operator=(const fsm<Input, Output, State> & other)
    {
        initial_state = other.initial_state;
        cur_state = other.cur_state;
        details = other.details;
        accumulator = other.accumulator;
    }

    template<typename Input, typename Output, typename State>
    fsm<Input, Output, State> & fsm<Input, Output, State>::operator=(fsm<Input, Output, State> && other)
    {
        initial_state = other.initial_state;
        cur_state = other.cur_state;
        details = other.details;
        accumulator = other.accumulator;
        return *this;
    }

    template<typename Input, typename Output, typename State>
    void fsm<Input, Output, State>::advance(const Input & input)
    {
        accumulator.push_back(input);
        auto find = details.state_map.find(std::make_pair(cur_state, input));
        if (find != details.state_map.end()) {
            cur_state = find->second;
            auto binding = details.state_bindings.find(cur_state);
            if (binding != details.state_bindings.end()) {
                binding->second(cur_state, input);
            }
            return;
        }
        auto findFunction = details.function_state_map.find(cur_state);
        if (findFunction != details.function_state_map.end()) {
            auto functionPair = findFunction->second;
            bool acceptState = (functionPair.first)(input);
            if (acceptState) {
                cur_state = functionPair.second;
                auto binding = details.state_bindings.find(cur_state);
                if (binding != details.state_bindings.end()) {
                    binding->second(cur_state, input);
                }
                return;
            }
        }
        auto findDefaultChar = details.default_char_map.find(input);
        if (findDefaultChar != details.default_char_map.end()) {
            cur_state = findDefaultChar->second;
            auto binding = details.state_bindings.find(cur_state);
            if (binding != details.state_bindings.end()) {
                binding->second(cur_state, input);
            }
            return;
        }
        auto findDefaultState = details.default_state_map.find(cur_state);
        if (findDefaultState != details.default_state_map.end()) {
            cur_state = findDefaultState->second;
            auto binding = details.state_bindings.find(cur_state);
            if (binding != details.state_bindings.end()) {
                binding->second(cur_state, input);
            }
            return;
        }
    }

    template<typename Input, typename Output, typename State>
    bool fsm<Input, Output, State>::has_output() const
    {
        return details.output_map.count(cur_state) > 0;
    }

    template<typename Input, typename Output, typename State>
    Output fsm<Input, Output, State>::get_output() const
    {
        return details.output_map.at(cur_state);
    }

    template<typename Input, typename Output, typename State>
    State fsm<Input, Output, State>::get_current_state() const
    {
        return cur_state;
    }

    template<typename Input, typename Output, typename State>
    const std::vector<Input>& fsm<Input, Output, State>::get_accumulator() const
    {
        return accumulator;
    }

    template<typename Input, typename Output, typename State>
    void fsm<Input, Output, State>::reset_accumulator()
    {
        accumulator.clear();
    }

    template<typename Input, typename Output, typename State>
    void fsm<Input, Output, State>::reset()
    {
        cur_state = initial_state;
        reset_accumulator();
    }



    template<typename Input, typename Output, typename State>
    fsm<Input, Output, State>::builder::builder()
    {}

    template<typename Input, typename Output, typename State>
    fsm<Input, Output, State>::builder::builder(State starting_state)
        : initial_state{ starting_state }
    {}

    template<typename Input, typename Output, typename State>
    fsm<Input, Output, State>::builder::builder(const builder & builder)
        : initial_state{ builder.initial_state }
        , state_bindings{ builder.state_bindings }
        , default_state_map{ builder.default_state_map }
        , function_state_map{ builder.function_state_map }
        , default_char_map{ builder.default_char_map }
        , state_map{ builder.state_map }
        , output_map{ builder.output_map }
    {}

    template<typename Input, typename Output, typename State>
    fsm<Input, Output, State>::builder::builder(builder && builder)
        : initial_state{ builder.initial_state }
        , state_bindings{ builder.state_bindings }
        , default_state_map{ builder.default_state_map }
        , function_state_map{ builder.function_state_map }
        , default_char_map{ builder.default_char_map }
        , state_map{ builder.state_map }
        , output_map{ builder.output_map }
    {}

    template<typename Input, typename Output, typename State>
    typename fsm<Input, Output, State>::builder & fsm<Input, Output, State>::builder::operator=(const builder & other)
    {
        initial_state = other.initial_state;
        state_bindings = other.state_bindings;
        default_state_map = other.default_state_map;
        function_state_map = other.function_state_map;
        default_char_map = other.default_char_map;
        state_map = other.state_map;
        output_map = other.output_map;
        return *this;
    }

    template<typename Input, typename Output, typename State>
    typename fsm<Input, Output, State>::builder & fsm<Input, Output, State>::builder::operator=(builder && other)
    {
        initial_state = other.initial_state;
        state_bindings = other.state_bindings;
        default_state_map = other.default_state_map;
        function_state_map = other.function_state_map;
        default_char_map = other.default_char_map;
        state_map = other.state_map;
        output_map = other.output_map;
        return *this;
    }

    template<typename Input, typename Output, typename State>
    typename fsm<Input, Output, State>::builder & fsm<Input, Output, State>::builder::starting_state(State state)
    {
        initial_state = state;
        return *this;
    }

    template<typename Input, typename Output, typename State>
    typename fsm<Input, Output, State>::builder & fsm<Input, Output, State>::builder::bind(
        State toBindTo, std::function<void(State, Input)> callback)
    {
        state_bindings.emplace(toBindTo, callback);
        return *this;
    }

    template<typename Input, typename Output, typename State>
    typename fsm<Input, Output, State>::builder & fsm<Input, Output, State>::builder::map(
        State from, Input input, State to)
    {
        state_map.emplace(std::make_pair(from, input), to);
        return *this;
    }

    template<typename Input, typename Output, typename State>
    typename fsm<Input, Output, State>::builder & fsm<Input, Output, State>::builder::map(
        State from, std::function<bool(Input)> advanceTo, State to)
    {
        function_state_map.emplace(from, std::make_pair(advanceTo, to));
        return *this;
    }

    template<typename Input, typename Output, typename State>
    typename fsm<Input, Output, State>::builder & fsm<Input, Output, State>::builder::map(Input from, State to)
    {
        default_char_map.emplace(from, to);
        return *this;
    }

    template<typename Input, typename Output, typename State>
    typename fsm<Input, Output, State>::builder &  fsm<Input, Output, State>::builder::map(State from, State to)
    {
        default_state_map.emplace(from, to);
        return *this;
    }

    template<typename Input, typename Output, typename State>
    typename fsm<Input, Output, State>::builder & fsm<Input, Output, State>::builder::map_output(State from, Output output)
    {
        output_map.emplace(from, output);
        return *this;
    }

    template<typename Input, typename Output, typename State>
    typename fsm<Input, Output, State> fsm<Input, Output, State>::builder::build()
    {
        return fsm{ *this };
    }
}

fsm_test.cpp (uses Google Test)

#include <iostream>
#include <vector>

#include "fsm.h"

#include "gtest/gtest.h"

using namespace extra;

enum State
{
    INIT, S1, S2, S3, S4
};

class fsm_test : public ::testing::Test
{
protected:
    virtual void SetUp()
    {
        machine = fsm<int, int, State>::builder(State::INIT)
            .map(INIT, 1, S1)
            .map(S1, 1, S2)
            .map(S2, 1, S1)
            .map(S2, 2, S3)
            .map(S3, 1, S4)
            .map(S4, 1, INIT)
            .map(S4, [](int input) { return input > 2; }, INIT)
            .map(0, INIT)
            .map(S3, S2)
            .map_output(INIT, 0)
            .map_output(S1, 1)
            .map_output(S2, 2)
            .map_output(S3, 3)
            .build();
    }

    fsm<int, int, State> machine;
};

TEST_F(fsm_test, canAdvanceStates)
{
    machine.advance(10);
    EXPECT_EQ(INIT, machine.get_current_state());

    machine.advance(1);
    EXPECT_EQ(S1, machine.get_current_state());

    machine.advance(1);
    EXPECT_EQ(S2, machine.get_current_state());

    machine.advance(1);
    EXPECT_EQ(S1, machine.get_current_state());

    machine.advance(1);
    machine.advance(2);
    EXPECT_EQ(S3, machine.get_current_state());

    machine.advance(14);
    EXPECT_EQ(S2, machine.get_current_state());

    machine.advance(2);
    machine.advance(1);
    EXPECT_EQ(S4, machine.get_current_state());

    machine.advance(2);
    EXPECT_EQ(S4, machine.get_current_state());

    machine.advance(1);
    EXPECT_EQ(INIT, machine.get_current_state());

    machine.advance(1);
    machine.advance(1);
    machine.advance(0);
    EXPECT_EQ(INIT, machine.get_current_state());

    machine.advance(1);
    machine.advance(1);
    machine.advance(2);
    machine.advance(1);
    EXPECT_EQ(S4, machine.get_current_state());

    machine.advance(10);
    EXPECT_EQ(INIT, machine.get_current_state());
}

TEST_F(fsm_test, canReturnCorrectOutput)
{
    EXPECT_TRUE(machine.has_output());
    EXPECT_EQ(0, machine.get_output());

    machine.advance(1);
    EXPECT_TRUE(machine.has_output());
    EXPECT_EQ(1, machine.get_output());

    machine.advance(1);
    EXPECT_TRUE(machine.has_output());
    EXPECT_EQ(2, machine.get_output());

    machine.advance(2);
    EXPECT_TRUE(machine.has_output());
    EXPECT_EQ(3, machine.get_output());

    machine.advance(1);
    EXPECT_FALSE(machine.has_output());
    EXPECT_ANY_THROW(machine.get_output());

    machine.advance(1);
    EXPECT_TRUE(machine.has_output());
    EXPECT_EQ(0, machine.get_output());
}

TEST_F(fsm_test, canReturnAccumulators)
{
    std::vector<int> accumulator;
    ASSERT_EQ(accumulator, machine.get_accumulator());
    accumulator.push_back(1);
    machine.advance(1);

    ASSERT_EQ(accumulator, machine.get_accumulator());
    accumulator.push_back(2);
    machine.advance(2);

    ASSERT_EQ(accumulator, machine.get_accumulator());
    accumulator.push_back(-1);
    machine.advance(-1);

    ASSERT_EQ(accumulator, machine.get_accumulator());
    accumulator.clear();
    machine.reset_accumulator();

    ASSERT_EQ(accumulator, machine.get_accumulator());
    accumulator.push_back(1);
    machine.advance(1);

    ASSERT_EQ(accumulator, machine.get_accumulator());
    accumulator.push_back(2);
    machine.advance(2);

    ASSERT_EQ(accumulator, machine.get_accumulator());
    accumulator.push_back(-1);
    machine.advance(-1);

    ASSERT_EQ(accumulator, machine.get_accumulator());
}

TEST_F(fsm_test, canReset)
{
    machine.advance(1);
    ASSERT_NE(INIT, machine.get_current_state()) << "State machine didn't advance states";

    machine.reset();
    EXPECT_EQ(INIT, machine.get_current_state()) << "Didn't reset to initial_state";
    EXPECT_TRUE(machine.get_accumulator().empty()) << "Didn't clear accumulator";
}

Answer 1

template <typename Input, typename Output, typename State>
typename fsm<Input, Output, State> fsm<Input, Output, State>::builder::build()
{
  return fsm{*this};
}

Two things with this:

• There's a bug, the typename in the second line shouldn't be there
• The signal to noise ratio is, as you've noticed, terrible.

Simple solution: move it inline in the class definition. Then it will look like:

/* Build the finite state machine */
fsm<Input, Output, State> build() { return fsm{*this}; }

Do that for all your one- and two-liners, and your code will be much shorter and more readable. And easier to maintain: less "noise" is good.

---

Look at all your default and copy constructors and copy/move-assignment operators. They're not consistent (the state of accumulator after copy-construction and assignment isn't the same), and some even have bugs (missing return statement). But they also essentially don't do anything that the compiler wouldn't do for you anyway. Especially, your move constructors/assignment operators are identical to the copy ones.

Just remove all of them, and default the default constructor, and your code will still work (pass tests), will have less bugs, and much less noise. Only keep the constructors that take State or builder that the compiler can't generate for you.

---

You can actually use the same functionality for the following three functions, the latter two being special cases of the first, if you can allow a small semantic change: drop this "priority" notion you have in comments and replace it with "first map declared tried first".

builder & map(State from, std::function<bool(Input)>, State to);
builder & map(State from, Input trigger, State to);
builder & map(State from, State to);

e.g.:

builder &map(State from, Input trigger, State to)
{
  map(from, [trigger](Input got) { return got == trigger; }, to);
  return *this;
}
builder &map(State from, State to)
{
  map(from, [](Input) { return true; }, to);
  return *this;
}

If you change that particular map to (typedefs or usings could help make that palatable):

std::map<State, std::vector<std::pair<std::function<bool(Input)>, State>>>
  function_state_map;

Then you can implement the "base case" like this:

builder &map(State from, std::function<bool(Input)> selector, State to)
{ 
  auto& funcs = function_state_map[from];
  funcs.emplace_back(std::make_pair(selector, to));
  return *this;
}

And your advance function boils down to this, after having factored out the common part of each loop:

template <typename Input, typename Output, typename State>
void fsm<Input, Output, State>::advance(const Input &input)
{
  accumulator.push_back(input);
  auto all_funcs = details.function_state_map.find(cur_state);
  if (all_funcs != details.function_state_map.end()) {
    for (auto &selector : all_funcs->second) {
      auto &sel_func = selector.first;
      bool acceptState = sel_func(input);
      if (acceptState) {
        enter(selector.second, input);
        return;
      }
    }
  }
  auto findDefaultChar = details.default_char_map.find(input);
  if (findDefaultChar != details.default_char_map.end()) {
    enter(findDefaultChar->second, input);
    return;
  }
}

Tests pass without change of the test code with this modification.

---

With all that, your code will be down to a bit less than half its original size, and have much, much less repetition of template and typename gook. And still pass your tests.