4
\$\begingroup\$

This question is a follow-up from Object Oriented Finite State Machine. I vastly improved commenting and followed the suggestions from the answer. Additionally, I improved my tests and did some more refactoring.

At this point, I still want to know what I could be doing better in my code. How could I better follow C++ conventions? I purposely named my class in lowercase to mimic the standard library, but is that a bad idea? I also moved a lot of code from the cpp/impl file into the header file; did I go too far? Also, to use my function binding mechanism, it is often required to use a pointer (as can be seen in my test file). This feels ugly; is there a better way?

Additionally, what could make the code run faster?

fsm.hpp

#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.
    Defining mappings, outputs, and bindings must be done via fsm::builder.

    In addition to simply implementing a state machine, this class keeps track
    of the inputs you feed it in an accumulator.
    */
    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;

        /*
        Creates a blank fsm. This is not useful for actually doing anything, but
        default constructors are necessary for many use cases
        */
        fsm() {}
        /* Advance the fsm to the next state. */
        void advance(const Input&);
        /* Get the output of the fsm at the current state. */
        Output get_output() const { return details.output_map.at(cur_state); }
        /* Get whether the fsm can return an output */
        bool has_output() const { return details.output_map.count(cur_state) > 0; }
        /* Get the current state of the fsm */
        State get_current_state() const { return cur_state; }
        /*
        Get the current accumulator for the fsm. This contains all inputs from the
        last reset_accumulator() until now.
        */
        const std::vector<Input>& get_accumulator() const { return accumulator; }
        /* Resets (ie clears) the accumulator */
        void reset_accumulator() { accumulator.clear(); }
        /* Resets this finite state machine such that it's as if it was just created. */
        void reset()
        {
            cur_state = initial_state;
            reset_accumulator();
        }
    private:
        State initial_state;
        State cur_state;
        std::vector<Input> accumulator;
        builder details;

        fsm(builder builder)
            : initial_state{ builder.initial_state }
            , cur_state{ builder.initial_state }
            , details{ 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) : initial_state{ starting_state } {}

        /* defines the initial state of the fsm */
        builder & starting_state(State state) { initial_state = state; return *this; }
        /*
        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(Input)> callback)
        {
            state_bindings.emplace(toBindTo, callback);
            return *this;
        }
        /* Map from `from` to `to` when receiving the input `trigger` */
        builder & map(State from, Input trigger, State to)
        {
            map(from, [trigger](Input in) { return trigger == in; }, to);
            return *this;
        }
        /* Map from `from` to `to` when receiving any input whatsoever. Lowest priority. */
        builder & map(State from, State to)
        {
            map(from, [](Input) { return true; }, to);
            return *this;
        }
        /* Map from `from` to `to` when the given function returns true */
        builder & map(State from, std::function<bool(Input)> guard, State to)
        {
            auto & functionsForState = function_state_map[from];
            functionsForState.emplace_back(std::make_pair(guard, to));
            return *this;
        }
        /* Return `result` when the fsm is at the current output */
        builder & map_output(State from, Output output)
        {
            output_map.emplace(from, output);
            return *this;
        }
        /* Build the finite state machine */
        fsm<Input, Output, State> build() { return fsm{ *this }; }

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

fsm.impl

#pragma once // This file is included within "fsm.h", so we need to ensure we don't get circular inclusion

#include "fsm.hpp"

/* Advance the fsm to the next state. */
template<typename Input, typename Output, typename State>
void extra::fsm<Input, Output, State>::advance(const Input & input)
{
    accumulator.push_back(input);

    auto & allApplicableFunctions = details.function_state_map.find(cur_state); // Look at all mappings from this state

    if (allApplicableFunctions != details.function_state_map.end()) {
        for (auto & mapping : allApplicableFunctions->second) { // For every mapping from the current state,
            auto & acceptFunction = mapping.first;
            bool acceptState = (acceptFunction)(input);         // see if it takes this input.

            if (acceptState) {              // If the given mapping takes this input,
                cur_state = mapping.second; // go to the mapping's destination.

                auto binding = details.state_bindings.find(cur_state); // If the given state that we went to
                if (binding != details.state_bindings.end()) {         // has a binding,
                    binding->second(input);                 // call that binding.
                }
                return; // We already went to a state, so quit
            }
        }
    }
}

fsm_test.cpp (uses googletest)

#include <vector>

#include "fsm.hpp"

#include "gtest/gtest.h"

using namespace extra;

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

class fsm_test : public ::testing::Test
{
protected:
    virtual void SetUp()
    {
        auto * count = &s2_count;
        machine = fsm<int, int, State>::builder(State::INIT)
            .map(INIT, 1, S1)                                   // +--------+ <--0-- +------+
            .map(S1, 1, S2)                                     // | INIT:0 | --1--> | S1:1 |
            .map(S2, 1, S1)                                     // +--------+        +------+
            .map(S2, 2, S3)                                     //  ^ ^   +-1---------^ |
            .map(S3, 1, S4)                                     //  +-|-1-|----+        1
            .map(S4, 1, INIT)                                   //  | 0   1    |        |
            .map(S4, [](int input) { return input > 2; }, INIT) // ++ |   |    1        |
            .map(S1, 0, INIT)                                   // | +------+  |        |
            .map(S2, 0, INIT)                                   // | | S2:2*|<----------+
            .map(S3, 0, INIT)                                   // | +------+  |
            .map(S4, 0, INIT)                                   // |  |  ^     +--------+
            .map(S3, S2)                                        // |  2  |              |
            .map_output(INIT, 0)                                // |  | [*]        [0, 1, >2] 
            .map_output(S1, 1)                                  // 0  v  |              |
            .map_output(S2, 2)                                  // | +------+        +------+ 
            .map_output(S3, 3)                                  // +-| S3:3 | --1--> |  S4  | (no output on S4)
            .bind(S2, [count](int) { (*count)++; })             //   +------+        +------+
            .build();                                           // * Increment count on entrance to S2
    }

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

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

    machine.advance(1); // INIT -> S1
    EXPECT_EQ(S1, machine.get_current_state());

    machine.advance(1); // S1 -> S2 (count++)
    EXPECT_EQ(S2, machine.get_current_state());

    machine.advance(1); // S2 -> S1
    EXPECT_EQ(S1, machine.get_current_state());

    machine.advance(1); // S1 -> S2 (count++)
    machine.advance(2); // S2 -> S3
    EXPECT_EQ(S3, machine.get_current_state());

    machine.advance(14); // S3 -> S2 (count++)
    EXPECT_EQ(S2, machine.get_current_state());

    machine.advance(2); // S2 -> S3
    machine.advance(1); // S3 -> S4
    EXPECT_EQ(S4, machine.get_current_state());

    machine.advance(2); // S4 -> S4 (implicit)
    EXPECT_EQ(S4, machine.get_current_state());

    machine.advance(1); // S4 -> INIT
    EXPECT_EQ(INIT, machine.get_current_state());

    machine.advance(1); // INIT -> S1
    machine.advance(1); // S1 -> S2 (count++)
    machine.advance(0); // S2 -> INIT
    EXPECT_EQ(INIT, machine.get_current_state());

    machine.advance(1); // INIT -> S1
    machine.advance(1); // S1 -> S2 (count++)
    machine.advance(2); // S2 -> S3
    machine.advance(1); // S3 -> S4
    ASSERT_EQ(S4, machine.get_current_state()); // Just to be sure

    machine.advance(10); // S4 -> S1
    EXPECT_EQ(INIT, machine.get_current_state());

    EXPECT_EQ(5, s2_count);
}

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()); // S4 has no output; Throws.

    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";
}
\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.