Click here to Skip to main content
Click here to Skip to main content

Generic Finite State Machine (FSM)

By , 2 Jul 2012
Rate this:
Please Sign up or sign in to vote.
  • The RandomNumbersFsm.zip file is a project made for Visual Studio 2010. However, you should be able to use it's files in other environments with some minor changes.
  • If you happen to download and use this library, please comment about it. Feedbacks would be great for me in order to improve it.
  • If you've created a useful state machine with this framework please share it with us.

Introduction   

A simple way to use, create and design type safe state machines. A template structure that makes the process of mapping state machines to C++ more straight forward. 

Background  

I assume you have background in state machines diagrams, as well as knowledge with templates. There is no need to know more than how to use std::vector<> in order to use it (understanding is totally different story). I suppose that some of you already tried to create your own design pattern of FSM at some time or you might have used an already made for the task. My experience was not that good with design patterns that enforced me to move some of the logic to the run-time just because there was no straight logic in C++ that could deal with state machines during compile time coding. That way some bugs could only be eliminated and found when I run the program and not before that. I've tried also some compile time solutions in the past but they were either too verbose or used some cryptic macros that made the state machine object unmaintainable.

Using the library  

Using the state machine  

I'll start with an example of diagram and then I'll go straight to show how to use the a state machine object before I even 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 there are:

  1. 2 states: On and Off. Initial state is Off 
  2. 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, many other designers tend to ignore such kind of transition. can you find another transition that is obvious to be ignored? 
  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 repository inside the state machine. this data is also accessible to anyone who may observe the state machine.  

So now that we all know how the state machine looks like, we know what are the three keys that define a state machine, let us use it! Please consider that someone already created for us the state machine by using the design pattern I contributed in this article (please open the demo RandomNumbersFsm.zip file in Visual Studio 2010 or above). When the programmer use the state machine, his code should look like this: 

NumberGenFsm NumbersGeneratorFsm;
NumbersGeneratorFsm->Start();
NumbersGeneratorFsm->Generate();
NumbersGeneratorFsm->Generate();
NumbersGeneratorFsm->Stop();
int test1 = NumbersGeneratorFsm.data.number;
States test2 = NumbersGeneratorFsm.GetState();
  • I guess you realized something weird, the operator-> is used even though the object is not representing a pointer nor an iterator. It is however representing some kind of indirection that is well represented with the -> operator. The other thing that you may already understood is that every function that is invoked through that operator is actually a transition, while the function GetState() has nothing to do with transitions.  
  • I guess you already observed that there is a data member to that state machine that is (always) called data. and that data has a member called number. and you might already guessed that this number is the one generated in the transition "generate"... 
  • You have seen that GetState() returns a value of type States and you might guessed that it is some kind of enumerator that holds two values, like "On" and "Off".  
  • You haven't seen it here, but the state machine here is initialized to the "Off" state even though it's not written anywhere in the example.
That is it! You know how to use the state machine. No big deal!  

Creating the state machine  

The state machine is created the same way a class is defined, but with some extra details. As with all header files you may need to #include something so let #include the fsm.h library for example:

#include "fsm.h"

Then you should define the state, use simple enum for that, but remember these things:

  1. States enum should start with a value that is equal to 0, not more not less!
  2. The first value of the enum also represent the initial state. (at least in this version of the article) 
  3. The last value in the enum should be the "terminate" state (not obligatory, but recommended).
  4. values should be sequential from initial state to terminate state.
// Declare states 
enum States 
{ 
    Off, 
    On 
};

Now define the transitions. Please look again at the diagram and try to guess (again?) what are the names of the transitions. the transitions should be defined as methods. I, myself prefer the non pure virtual "interface" like this:

// Declare Events (Transitions)
// Non-pure virtual  - means: do nothing if nothing is implemented
struct IEvents 
{
    virtual void Start()	{}
    virtual void Stop()		{}
    virtual void Generate()	{}
};

Why I like it non pure virtual? Because I want to deal only with transitions that I should implement in the future for each state. Some states ignore some transitions (events) so I want to keep them empty by default.

And there is the data structure I mentioned before. This is the data structure that will be aggregated inside the FSM later on. In that data structure the generated number will be saved each time it is generated.

struct Data
{
	int number;
	Data() : number(0) {}
};

The next thing is to collect all the keys for an FSM definition and should look like this:

// Define the state machine
typedef StateMachineComponents<States, IEvents, Off, On, Data> NumbersGeneratorFsmDef; 
Then some cryptic thing pops out! Don't worry I'll explain this thing very fast and into details, just look at it first:
// Define transition implementation
// Declarre Transitions:
DECLARE_TRANSITION_IMPL_CLASS(NumbersGeneratorFsmDef,Off)
BEGIN_TRANSITION_IMPL_CLASS
    virtual void Start();
END_TRANSITION_IMPL_CLASS
 
DECLARE_TRANSITION_IMPL_CLASS(NumbersGeneratorFsmDef,On)
BEGIN_TRANSITION_IMPL_CLASS
    virtual void Stop();
    virtual void Generate();
END_TRANSITION_IMPL_CLASS

Those macros are expanded to something that will be explained immediately:

template<>
struct TransitionImplement<NumbersGeneratorFsmDef, Off> : TransitionsInterface<NumbersGeneratorFsmDef> 
{
    TransitionImplement (States &state, SharedData &data) : TransitionsInterface<NumbersGeneratorFsmDef>(state, data) {}
    virtual void Start(); 
};
 
template<> 
struct TransitionImplement<NumbersGeneratorFsmDef, On> : TransitionsInterface<NumbersGeneratorFsmDef> 
{
    TransitionImplement (States &state, SharedData &data) : TransitionsInterface<NumbersGeneratorFsmDef>(state, data) {} 
    virtual void Stop(); 
    virtual void Generate();
}

the expanded macros expand to templates that remind more or less the macros above with one exception, everyone can see that there is one line that repeats itself, it is the constructor! It is written in a special way that I wanted to conceal from you. I also wanted to save you from writing code that you don't really need to take care of. That code is repeating the same way for each class (struct in this case) definition. I prefer always to save time and coding errors from the user especially when it comes to code that the user shouldn't really care about.

It's up to you to decide whether to use the macros (and spare yourself some extra coding) or just write the spartan template with all the extras... I prefer the macros.

Last, but very important, the FSM itself. Lets create it: 

typedef Fsm<NumbersGeneratorFsmDef> NumberGenFsm;

For some of you it looks so unimportant to typedef the state machine giving it another name like NumberGenFsm. If you like your object to be declared like this:

Fsm<NumbersGeneratorFsmDef> fsmObject;

It's fine by me. However, I prefer it typedefed. It is much nicer to use later on like that. 

Now we can move on to the implementation of the NumbersGenerator State Machine. create the source file now, and according to my definition, that only transitions that do something are implemented. The rest of the code should look like this:

#include "NumbersGenerator.h"

#include <cstdlib>
#include <ctime>

void TransitionImplement<NumbersGeneratorFsmDef,Off>::Start()
{
	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:
	state = On;
}

void TransitionImplement<NumbersGeneratorFsmDef,On>::Stop()
{
	state = Off;
}

void TransitionImplement<NumbersGeneratorFsmDef,On>::Generate()
{
	//just generate random number and put it in data
	data.number = std::rand() % 100; //Pick a number between 0-100
	//state is not changed
}

Let explain the first transition implementation, it says:

void TransitionImplement<NumbersGeneratorFsmDef,Off>::Start()

which means: implement transition according to the definition of state machine NumbersGeneratorFsmDef that we defined earlier (Remember? A struct that collected everything that is needed to define an FSM: States enumeration, transition interface and the data definition). For that specific state machine, implement the transition Start() for the state Off.

In the implementation code you can see there is a data member that popped up out of nowhere, also a state member is used. Those two are defined in the Fsm<> template for you to use. What you see as the next state in the diagram (where the arrow point to the next state) is done by setting the state member into the next state. That's it! As for the generated number now you know where it is saved.

You may want to see what is the state of the machine, for that there is the GetState() method. You may want to access the data member of the state machine. you can access it directly from the state machine object. I showed how to use the state machine in the early stage of this article. now it's time to go back and look again. 

How the magic works

There is no black magic behind the code in fsm.h and it going to be explained here. The basic idea is to create a state machine that does nothing as default for each transition on each state and then let the programmer specialize the specific transitions for specific states. That is done with the cryptic DECLARE_TRANSITION_IMPL_CLASS. But then you ask how come the FSM object knows how to create all these classes? we'll deal with that later on.

Basically there are 2 classes: 1) the state machine class and 2) the transition interface class. They know partial information about each other and yet the state machine can handle transition classes quite nicely. Interesting!

Another thing we know is that both classes, transitions classes and the FSM class are dependent upon the definition of the state machine (states, transitions and data). So, it only make sense to create a mutual agreement between the two by creating a special "contract" class:

template <typename StatesType, typename TransitionsType, StatesType initStateParam, StatesType terminateStateParam, typename SharedDataType>
struct StateMachineComponents<StatesType,TransitionsType,initStateParam,terminateStateParam,SharedDataType,true>
{
    typedef StatesType States;
    typedef TransitionsType Transitions;
    enum {InitState = initStateParam};
    enum {TerminateState = terminateStateParam};
    typedef SharedDataType SharedData;
};
  

This class define the common minimum information needed to define a state machine. The last parameter of the templete here is there to denote that this class is defined only when the trait in the default value for this parameter is true. If you don't understand what written you should learen these topics: 1) template specialization, 2) type traits. The the trait is always true if you don't have C++11 compiler.

If you have C++11 or C++0x compiler support, you'll enjoy some extra typesafty. In that case the "contract" class itself is guarded with trait that makes sure that the States type is enum, the "init' state is 0 and that the "terminate" state is greater or equal to "init" state. if the contract doesn't follow this specific trait rule, the type State won't be defined and therefore the classes that rely on it won't compile! If any of you have the time to add support for other pre-C++11 compiler by using boost library or other means I'll be glad the see here your contribution.

Then on, a generic template of transition class is defined to be used as the base class for all the possible transition interfaces implementations. You can see that this "base" class is actually a middle class between the transitions interface you declared before and the transitions implementation in the inheritance tree.

template <typename StateMachineComponents>
struct TransitionsInterface : StateMachineComponents::Transitions
{
    //typedef for later use
    typedef typename StateMachineComponents::States States;
    typedef typename StateMachineComponents::SharedData SharedData;

    States &state;
    SharedData &data;
    TransitionsInterface (States &state, SharedData &data) : state(state), data(data) {}
};

Each transition interface has two important fields: state and data. The types of both of them are defined as part of the "contract" in StateMachineComponents.

A generic transition interface implementation is defined before the definition of Fsm<>:

template<typename StateMachineComponents, typename StateMachineComponents::States stateParam>
struct TransitionImplement : TransitionsInterface<StateMachineComponents>
{
    TransitionImplement (typename StateMachineComponents::States &state, typename StateMachineComponents::SharedData &data) : TransitionsInterface<StateMachineComponents>(state, data) {}
};

Later on, specialization of specific transitions will be implemented by you after the definition of Fsm<>. Fsm<> will take any specialization that is defined in the same translation unit. if there is no specialization the default generic one that is defined before Fsm<> will be used. and That is the first part of the magic! Of course there is another little magic to be shown later on. 

Take a look at the Fsm<> class:

template<typename StateMachineComponents>
class Fsm
{

	// types that must exist in StateMachineComponents
	typedef typename StateMachineComponents::States States;
	typedef typename StateMachineComponents::SharedData SharedData;
	typedef typename StateMachineComponents::Transitions Transitions;
	
	// important constant
	enum {InitState = StateMachineComponents::InitState};
	enum {TerminateState = StateMachineComponents::TerminateState};
.
.
.
}

Again, you can see that Fsm<StateMachineComponents> imply that it respects the "contract" by repeating the types it thinks should be in the FSM definition. If one of those doesn't exist then the class won't compile.

Inside the class there are few members that are going to be explained in more details:

The state member

The state member holds the current state of the state machine. It is important to explain now that there is intrinsic reason for using enumeration as a way to represent the states. The reason is that enumerations are convertible to numbers on one hand, while on the other hand they are type safe, i.e. two distinct/different template types can be made out of two distinct enumeration with the same numeric value! the transformation between the numeric value and the type of the value is very important for the design of the state machine.

The state is accessible through an inline function GetState() only. I guess you understand that only the state machine can change it's own state by using transitions only! Trying to override the state from the outside is violating the idea of state machine!

the data member

The data member holds the data of the state machine. the data is publicly accessible. 

The operator->() method

The operator->() method is one of many constructs inside the Fsm<> that makes use of the dual meaning of enumeration value both as a number and a type.

Transitions *operator->()
{
    return StateHanlderInstance.m_interfaces[static_cast<size_t>(StateHanlderInstance.state)];
}

If you look closely you can see that there is some "transitions" vector (m_interfaces) that holds all possible transitions interfaces for each state (will be explained in details later on how). By invoking transition using this operator like that: 

NumbersGeneratorFsm->Generate(); 

you actually invoke the right transition implementation for the current state. So for the state On the Generate() transition that will be invoked is: 

void TransitionImplement<NumbersGeneratorFsmDef,On>::Generate()
{
	//just generate random number and put it in data
	data.number = std::rand() % 100; //Pick a number between 0-100
	//state is not changed
} 

- that is defined in the demo (RandomNumbersFsm.zip) in the file NumbersGenerator.cpp.

StateHanlderInstance and the magic behind

This structure that looks like a member field but actually act as initializer of other fields is doing the magic behind everything. This structure answers two questions you may asked yourself already in the past: 

  1. How each interface implementation knows what is the current state and data of the machine?
  2. How the Fsm<> knows how many states (and therefore transition interfaces) exists, and how does it know to collect them all into one vector (see operator->)?

The answers are not that obvious:  

  1. The class StateHanlderType initialize each interface implementation to have a reference to the state and data members (see StateHandlerBase). StateHanlderType doesn't know that it is contained inside Fsm<>. Fsm<> is responsible to run the constructor of StateHanlderType and get the references to data and state fields. The real state and data fields resides inside some base class making them accessible to all StateHandler classes that inherit from it.  

  2. StateHanlderType in it's turn initialize by recursively inheriting itself (with class StateHandler), each time with different state value (till value is equal to 0 that is specialized) and at the same time the m_interfaces vector is initialized with right transition interface implementation object the current version of StateHandler<States>.

Fsm<> in its turn, after the construction of StateHandlerTypeInstance takes the instance's 3 members and expose data, state and interfaces!

The inheritance tree is explained below:

struct StateHandlerBase
{
    SharedData data;
    States state;
    Transitions *m_interfaces[static_cast<size_t>(Size)];
    StateHandlerBase() 
		: data(SharedData()), 
		state(static_cast<States>(InitState))/*, m_interfaces({0})*/ 
	{
	}
};

This class is responsible to hold the current state, data and m_interfaces of the containing state machine. I explained in a remark inside the code, the recursive inheritance. I think it is quiet good explanation. I can't find nice diagram to express this better. The base class is written on the bottom and the most inherited classes on top of it.

// StateHanlderType inheritance explanation:
// legend: -> means inherit from
// StateHandler<static_cast<States>(TerminateState), DummyExplicitSpecialization> -> 
// StateHandler<static_cast<States>(TerminateState-1), DummyExplicitSpecialization> ->...-> 
// StateHandler<static_cast<States>(0), DummyExplicitSpecialization> -> 
// StateHandlerBase

The rest of the code is self explanatory for intermediate C++ programmer. You can understand that the class is copyable and assignable. One important remark is that the field StateHandlerTypeInstance is not copyable, due to the fact that it creates references on construction time. Those references have absolute address inside the object. Therefore, it is uncopy-able and I consider this field more like a constructor field that do something at some point (construction) than a real field that is something. this field whole existence is to harness the support of the language to express at compile time all the transitions. 

The guardian traits 

I'll put here a brief explanation regarding the newly added traits guardians. I assume you've some knowledge with template meta-programming and that the term trait is not new for you. Here is a code excerpt:

 //C++11 specific support
#if defined(__cplusplus) && __cplusplus >= 199711L
#include <type_traits>
#endif
	
// A type-safe static machine

template <typename StatesType, StatesType InitStateParam, StatesType TerminateStateParam>
struct CorrectStates
{
#if defined(__cplusplus) && __cplusplus >= 199711L
	enum {value = (std::is_enum<StatesType>::value && InitStateParam == 0 && TerminateStateParam >= InitStateParam) };
#else
	enum {value = 1};
#endif
};
.
.
.
template <..., bool GuardianTrait=static_cast<bool>(CorrectStates<StatesType, initStateParam, terminateStateParam>::value)>
struct StateMachineComponents
{
};

template <..., typename SharedDataType>
struct StateMachineComponents<StatesType,TransitionsType,initStateParam,terminateStateParam,SharedDataType,true>
{
    typedef StatesType States;
    typedef TransitionsType Transitions;
    enum {InitState = initStateParam};
    enum {TerminateState = terminateStateParam};
    typedef SharedDataType SharedData;
};

I stripped out all the irrelevant code and left the most important one. Here you can see that:

  1. CorrectStates is the trait that works only when the version of the C++ is __cplusplus >= 199711L, meaning that it not less than C++11
  2. You can see that the first version of StateMachineComponents is empty. That means that if the trait GuardianTrate fails, the "contract" is broken and therefore your code will become broken (won't compile).
    1. The first version applies only when the trait value is false, otherwise it should work.
    2. The second version applies when the trait is true, then you get full version of the StateMachineComponents with the type States defined, which makes the code workable!

List of issues to consider

  1. The Fsm<> has guarding traits only for C++0x or C++11. If you have other compiler that doesn't support current standard, I trust you to avoid the following situations:
    1. init state with other value than 0.
    2. terminate state that it's numeric value is less than init state.
  2. You can't define the Fsm<> in one namespace and the transition implementation in different namespace. Actually, I tested fsm<> only on global namespace.  

History 

Revisions: 

  1. First publish.
  2. Final with source
  3. Revision in source
  4. Second review for typos  
  5. Adding guarding traits for the Fsm<>
  6. 1) Addressing random engine seeding issue, 2) fixing the type of trait.  
  7. 1) sync source with article 2) random generation seed now depend on static 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Cpp For All

United States United States
No Biography provided

Comments and Discussions

 
QuestionMultiple state machines of different type [modified] PinmemberMember 102258235-Feb-14 4:33 
QuestionThread safety PinmemberMember 102258235-Feb-14 4:22 
Bug[Clang5] Partial Specialization Pinmemberarthurdp96@hotmail.fr14-Jan-14 9:32 
GeneralMy vote of 5 Pingrouplyricc30-Jul-13 15:37 
Bug"This declaration has no storage class or type specifier" PinmemberGiGi916-Aug-12 16:28 
GeneralRe: "This declaration has no storage class or type specifier" PinmemberCpp For All16-Aug-12 21:35 
GeneralMy vote of 5 PinmemberMihai MOGA14-Jul-12 20:10 
GeneralRe: My vote of 5 PinmemberCpp For All15-Jul-12 0:59 
Generaldownload to learn Pinmemberhylong10-Jul-12 0:17 
GeneralRe: download to learn PinmemberCpp For All15-Jul-12 5:28 
QuestionMacho PinmemberPatrice STOESSEL2-Jul-12 12:01 
GeneralRe: Macho [modified] PinmemberCpp For All3-Jul-12 11:16 
GeneralRe: Macho PinmemberPatrice STOESSEL6-Jul-12 6:03 
AnswerRe: Macho PinmemberMicroImaging5-Jul-12 13:56 
GeneralMy vote of 5 PinmemberVitaly Tomilov30-Jun-12 12:50 
GeneralRe: My vote of 5 PinmemberCpp For All2-Jul-12 4:05 
Thank you. You're welcome!
QuestionI still can not download the file. Pinmemberleegen25-Jun-12 23:26 
AnswerRe: I still can not download the file. PinmemberCpp For All26-Jun-12 3:50 
QuestionI can't download sourcecode. Pinmemberleegen25-Jun-12 2:50 
AnswerRe: I can't download sourcecode. PinmemberCpp For All25-Jun-12 3:31 
GeneralRe: I can't download sourcecode. Pinmemberleegen25-Jun-12 23:21 
AnswerRe: I can't download sourcecode. PinmemberCpp For All25-Jun-12 8:22 
GeneralMy vote of 5 Pinmembermhsien_tsai24-Jun-12 17:11 
GeneralRe: My vote of 5 PinmemberCpp For All25-Jun-12 1:43 
GeneralRe: My vote of 5 Pinmembermhsien_tsai25-Jun-12 4:57 
GeneralRe: My vote of 5 PinmemberKochise25-Jun-12 23:43 
GeneralRe: My vote of 5 PinmemberCpp For All26-Jun-12 1:27 
GeneralMy vote of 5 PinmemberThatsAlok21-Jun-12 19:49 
GeneralRe: My vote of 5 PinmemberCpp For All22-Jun-12 2:59 
Questionlook good! PinmemberThatsAlok21-Jun-12 19:49 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140421.2 | Last Updated 2 Jul 2012
Article Copyright 2012 by Cpp For All
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid