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";
}