Generic Finite State Machine Revisited

• Download fsm.zip - 7.6 KB

Introduction

In this article I'll provide a library for implementing FSM in a way that is quick and similr to OOP, yet keeps you away from all the boilerplate code you find yourself writing when implementing FSM in C++. The interface is simple and easy to use . The libary was tested on Visual Studio 2017 Community Edition , GCC 5.4.0 and clang 3.8.0.

Background

FSM are not easily implemented in C and C++ even though they are fairly simple to understand. I always wanted to have a simple library to help me with writing FSM, yet keep me away from boilerplate and repeating code. Few years ago I provided similar library, but it was not following C++ standard, was compiler dependant and eventually I abandond the use of it. Having that said, I wanted to have in my toolbox a better implementation of that library. 

Using the code

Using the state machine  

I'll start with a diagram and then I'll move on to show how to use the a state machine object before I explain how to design the state machine class:  

It is a very simple diagram of random number generator and it is used for the purpose of this tutorial. In the diagram you can see:

1. We have 2 states: On and Off. Initial state is Off 
2. We have 3 transitions: start/stop/generate. It is quite obvious that I could avoid drawing the "start" transition in the "On" state, since the whole idea of "start" is to turn "On" the machine. However, I decided to draw it anyway.
3. Somewhere in the diagram a random number is generated but it's not clear where the number is saved, so I'll make it clear, it is saved in a data context (a structure the user provides) inside the state machine. this data is also accessible to anyone who wish to observe the state machine.  

So now that we all know how the state machine looks like, we know what are the three key features that define the state machine. Lets use it! The example above is already created for us by using the library I provided in this article. please open the demo fsm.zip file and generate the project for your favorite compiler or IDE using CMake. When the programmer use the state machine, his code should look like this: 

 fsm<NumbersGeneratorTransitions> numbersGenerator;
 numbersGenerator.move_to_state<StateOff>();
 printf("\nData %X\n", numbersGenerator.state().number);  //Will show the uninitialized number
 numbersGenerator->Start();
 numbersGenerator->Generate();
 numbersGenerator->Stop();
 numbersGenerator->Generate();
 printf("\nData %d\n", numbersGenerator.state().number); //Will show generated random number

*Remark: The demo in fsm.zip is similar to the above example, though a bit verbose and covers few other cases as well.
As one can see, the idea is to keep the interface exactly the same, while the implementation is differet for each state, where each state is represented by a class and the interface itself is represented, as expected, with an interface (sort of interface) class.

So, to start just include:

#include "fsm.h"

Then add a class to represent the state that is shared among all other state/transitions interfaces:

struct Data
{
    int number;
    Data() : number(0xdeadbeef) {} //that would be the value of uninitialized nubmer
};

Once finished with the data for the state machine (also refered as the context in the source) we should add the interface for the state machine:

struct NumbersGeneratorTransitions : public impl_ctx<NumbersGeneratorTransitions, Data>
{
    virtual void Start() {}
    virtual void Stop() {}
    virtual void Generate() {}
};

As one can see from the diagram, pure virtual methods should not be used as we want to ignore all transitions that do not change the state of the state machine.

The use of impl_ctx<NumbersGeneratorTransitions, Data> is to provide the boilerplate code (Curiously recurring template) to handle the state machine as well as introducing the Data structure to be part of the state machine (which later on is used and changed and shared among states handlers).

For each state we'll provide a set of interfaces. This is dead simple as writing the following declaration:

struct StateOff : public impl_state<StateOff, NumbersGeneratorTransitions>
{
    virtual void Start();
};

struct StateOn : public impl_state<StateOn, NumbersGeneratorTransitions>
{
    virtual void Stop();
    virtual void Generate();
};

As one can see, the implementation is one to one with the diagram. We haven't written to much boilerplate. There is not much of clutter and the code is easily debugable:

void StateOff::Start()
{
    printf("\nEndtered StateOff::Start()\n");
    static bool first_seed = true;
    // init random number (with simplified seed)

    if (first_seed)
    {
        first_seed = false;
        std::srand((unsigned int)time(0));
    }
    // the next state:

    change_state<StateOn>();
}

void StateOn::Stop()
{
    printf("\nEndtered StateOn::Stop()\n");
    change_state<StateOff>();
    /* DO NOT ACCESS this (pointer) OR state()  function after calling  change_state<...>()*/
}

void StateOn::Generate()
{    //just generate random number and put it in data

    printf("\nEndtered StateOn::Generate()\n");
    state().number = std::rand() % 100; //Pick a number between 0-100

    //state is not changed
}

One thing though, when using the change_state<...>() call, the interface/object will be erased (including all local data). In many ways one can think of it as the equivalent to delete this though there are many differences between the two. 

For the initialization make sure you call move_to_state<T>() otherwise the state machine is inaccesible.

This is it! There is nothing else add as the library can be used without any knowledge about the implementation. Please run the test and debug to see how the code is working. I'll only add remark that this state machine uses an optimized memory allocation where each state has allocated memory which is recycled for each state class size and use.

In order to run/build the code the user can use CMake to generate Visual Studio projects or make files for gcc or clang. 

In More Details

For the people who want more details about the implementation behind the scenes I dedicate this section:

1. template <typename InterfaceT> class fsm - The FSM template interface will ask you for the State's Transitions interface base class (the actual inteface). 
2. template<typename InterfaceT, typename StateT> class fsm_ctx - The FSM Context class will ask again for the interface and the state class, but you'll never access that class. it is merely serve as super-templated-class token for the FSM class. 
3. template <typename InterfaceT, typename StateT> class impl_ctx - provides a base class for the Transitions interface. It provides to the Transitions interface few services, including static constructor,  some sort of proxy class to handle the state and other boilerplate code. 

Memory management

With this library I was trying to avoid unnecessary memory allocations that in turn causes lots of memory fragments. Basically on each state change, the memory for the new state should be allocated. Unfortunatelly, if we use only regular new operator for the job, we'll end up with memory fragmantation. In order to avoid such situation, we alocate memory for the first State Transitions interface, once it's finished and we moved on to the next state, the same memory address is going to be reused for the next State Transition interface, unless the next State Transition interface class is bigger than the one already allocated in memory, in such case a new memroy space is allocated for it. This way the memory allocation remains static through the life time of the FSM as opposed to thousand or millions of memory allocations per each state change. In most cases (and compilers) the size of all interfaces is expected to be the same which leads to a very optimized memory usage (only one piace of memory is allocated in that case. Have a look at static U *create_new_interface(U u, fsm_ctx_t *afsm_ctx) to see how things are done.

Constuction and Destruction

Construction and Destruction of State's Transaition is automatically done on State change (for the user of course, for the library developer it is very much manual process). This means the user can use the constructor of each Transition Interface to do some stuf as well as using the Destructor to cleanup stuff. One can have a look at the call for the constractor on the placement new operator and the call to the virtual destructor, see this->~impl_ctx() for example in the function U *change_state(). 

Exceptions

In case the user is trying to use the FSM before initialization an exception will be thrown on such event. see throw uninitialized in the case where the user is trying to call State's interface methods through the operator -> or on the state() function which is not valid as well (though, I'm considering relaxing the last rule and avoid the exception). so use move_to_state() to initialize the state machine!

Remarks

When I think of it, I wouldn't consider that library as typical C++11, as beside auto, foreach and nullptr, it can all be done or converted to old versions of C++, though I haven't tested that. From my experience when working with template meta-programming one can meet corners and inconsistet behavior between compilers. So I was trying to be as close to common sense on implementing the library. Funny thing, it looks much easier to read and more linear than the template meta-programming I've done in the past to achive similar FSM behavior.

I hope this helps other developers.