Generic Finite State Machine Revisited

0
66

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++. I’ll describe how to use the new implementation similar to my old fsm library. This time with interface which is easy to use and is simplified as well. 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. You can still find the old article, though I can’t update it as I have to no login credentials anymore to that account. Therfore I’m writing a new article  based on the old one.

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<span> </span>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. 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); 
 numbersGenerator->Start();
 numbersGenerator->Generate();
 numbersGenerator->Stop();
 numbersGenerator->Generate();
 printf("\nData %d\n", numbersGenerator.state().number); 

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) {} 
};

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 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).

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;
 

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

 change_state<StateOn>();
}

void StateOn::Stop()
{
 printf("\nEndtered StateOn::Stop()\n");
 change_state<StateOff>();
 
}

void StateOn::Generate()
{ 

 printf("\nEndtered StateOn::Generate()\n");
 state().number = std::rand() % 100; 

 
}

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.

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 the code the user needs CMake to generate Visual Studio projects or make files for gcc or clang.

I hope this helps other developers.

LEAVE A REPLY