# Designing a state machine in C++ using the STL

I have this working code for C++ state machine using STL (not using boost state chart).

The purpose of posting is two-fold:

1. To share a simple and working code C++ state machine using the STL for the sparse 'state' and 'event' function matrix.

2. To seek enhancements of implementation, since with this approach I have to init state machine for every new object created, which is not necessary since state-event function are same for all objects of a given class.

(Note: while compiling using g++, use the "-std=c++0x" option and link both .cpp files to get the executable)

File name: BasicFsmT.h

//////////////////////////////////////////////////////////////////////
// File name : BasicFsmT.h
// Purpose : To define simple FSM implementation base class.
//            This class to be inherited
//            by any class which would like to implement FSM
///////////////////////////////////////////////////////////////////////
#ifndef _BasicFsmT_h
#define _BasicFsmT_h

#include <string>
#include <map>
#include <iostream>
#include <vector>

using namespace std;

class BasicFsm
{
public :
BasicFsm(); // Default Constructor
BasicFsm(string initialState);
virtual ~BasicFsm();

// StateMachine Method prototype
typedef int (*pFsmMethodT) (BasicFsm* pFSM, string event, int info);

virtual int AddStateEventMethod(string state, string event, pFsmMethodT);
virtual string GetState();

virtual int Fsm(string event, int info);

virtual int TransitionToState(string state);
virtual int SetPreviousEvent(string event);

protected :

vector<string> m_statesVec; // all valid states list in the  fsm
vector<string> m_eventsVec; // all valid events list in the  fsm
string m_fsmStateStr;      // current state of the state fsm
string m_fsmPrevEventStr;  // the last event procesed by the fsm
string m_fsmPrevStateStr;  // the previous state of fsm

// the key is state and event strings concatanated together
map<string, pFsmMethodT> m_stateEventToMethodMap;

};

#endif // _BasicFsmT_h
////////////// End File  : BasicFsmT.h  ///////////////////////////////


File name: BasicFsmT.cpp

//////////////////////////////////////////////////////////////////////
// File name : BasicFsmT.cpp
// Purpose : To define BasicFsmT Class methods. This class to be inherited
//            by any class which would like to implement FSM
///////////////////////////////////////////////////////////////////////
#include <BasicFsmT.h>
#include <algorithm> // for std::find( ) etc.
#include <iostream>
#include <sstream>
#include <stdexcept>

#include <stdlib.h>

/// Description : Default Constructor, called by derrived classes object
/// @param[in]
/// @returns
BasicFsm::BasicFsm()
{
m_statesVec.clear();
m_eventsVec.clear();
m_fsmStateStr.clear();
m_fsmPrevEventStr.clear();
m_fsmPrevStateStr.clear();
m_stateEventToMethodMap.clear();
}

/// Description : Constructor, with initial state to setup.
///             Need expicit call by derrived classes constructor.
/// @param[in]
/// @returns
BasicFsm::BasicFsm(string initialState)
{
m_statesVec.clear();
m_eventsVec.clear();
m_fsmStateStr.clear();
m_fsmPrevEventStr.clear();
m_fsmPrevStateStr.clear();
m_stateEventToMethodMap.clear();

m_statesVec.push_back(initialState);
m_fsmStateStr = initialState;
}

/// Description : Destructor, this can be overrided by derrived class's destructor
///               No special cleanup is needed..
/// @param[in]
/// @returns
BasicFsm::~BasicFsm()
{

}

/// Description : Add a state to be handled by the fsm
///
/// @param[in] : state to be handled by the fsm
/// @returns
{
vector<string>::iterator itr;
itr = find(m_statesVec.begin(), m_statesVec.end(), state);
if (itr == m_statesVec.end())
{
m_statesVec.push_back(state);
}
// else state is already available
}

/// Description : Store the address of Method/function to be called
///    for the specified state and event
/// @param[in] : state - at which the specified Method is applicable.
/// @param[in] : event - for which the specified Method is applicable.
/// @param[in] : pFunc - Address of the Method to be called for the
///                      specified state and event.
/// @returns
int BasicFsm::AddStateEventMethod(string state, string event, pFsmMethodT pFunc)
{
string stateNEvent;

vector<string>::iterator itr;
itr = find(m_statesVec.begin(), m_statesVec.end(), state);
if (itr == m_statesVec.end())
{
m_statesVec.push_back(state);
}
// else state is already available

itr = find(m_eventsVec.begin(), m_eventsVec.end(), state);
if (itr == m_eventsVec.end())
{
m_eventsVec.push_back(event);
}
// else state is already available

// Add the function pointer to be called for the specified state-event pair
stateNEvent = state + event;
m_stateEventToMethodMap[stateNEvent] = pFunc;

}

/// Description : Get the current state of the fsm
/// @param[in] :
/// @returns
string BasicFsm::GetState()
{
return (m_fsmStateStr);
}

/// Description :  Change fsm state to the specified state.
/// @param[in]
/// @returns
int BasicFsm::TransitionToState(string state)
{
vector<string>::iterator itr;
itr = find(m_statesVec.begin(), m_statesVec.end(), state);
if (itr != m_statesVec.end())
{ // transition to state is a valid state
m_fsmPrevStateStr = m_fsmStateStr;
m_fsmStateStr = state;
}
// else transition to state is not valid

}

/// Description :  set fsm processed event to the specified event.
/// @param[in]
/// @returns
int BasicFsm::SetPreviousEvent(string event)
{
vector<string>::iterator itr;
itr = find(m_eventsVec.begin(), m_eventsVec.end(), event);
if (itr != m_eventsVec.end())
{ // transition to state is a valid state
m_fsmPrevEventStr = event;
}
// else event is not valid

}

/// Description :  Calls the Method specified for the specified state
///                event
/// @param[in] event - The event to be processed
/// @param[in] info  - Additional info needed for the method to process.
/// @returns   -1    - If specfied state or event is in valid, or
///                    no fsm function is defined for that state+event pair.
int  BasicFsm::Fsm(string event, int info)
{
pFsmMethodT pFunc;
int retStatus;
string state, stateNEvent;

try {
state = GetState();
stateNEvent = state + event;
map<string, pFsmMethodT>::iterator itr =
m_stateEventToMethodMap.find(stateNEvent);

// validate state, event and event handler
if (itr == m_stateEventToMethodMap.end())
{
return(-1);
}
pFunc = itr->second; // get pointer to the function to be executed.
// retStatus = (this->*(pFunc))(this, event, info);
retStatus = (*(pFunc))(this, event, info);

SetPreviousEvent(event);
return(retStatus);

} // end try
catch(exception& Error) {
stringstream logErr;
logErr << "Exception at BasicFsm::fsm, Error : " << Error.what();
}

}
/////////// End File : BasicFsmT.cpp ////////////////////////////////


File name: BasicFsmTest.cpp

//////////////////////////////////////////////////////////////////////
// File name : BasicFsmTest.cpp
// Purpose : To test implementation of FSM by BasicFsmT Class.
//          This includes BasicFsmT as public base class to implement a
//          sample Telephone state machine.
//
///////////////////////////////////////////////////////////////////////

#include <BasicFsmT.h>
#include <algorithm> // for std::find( ) etc.
#include <iostream>
#include <sstream>
#include <stdexcept>

///////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////
/////// Test Functions for BasicFsm Class ////////////////////

namespace TelephoneEnumsT
{

// List of Valid Sate in the Stmc
const string S_Idle = "S_Idle";
const string S_DIGIT_COLLECTION = "S_DigitCollection";
const string S_ESTABLISHING = "S_Establishing";
const string S_RINGING_OG = "S_RingingOG";
const string S_RINGING_IC = "S_RingingIC";
const string S_CALL_ESTABLISHED = "S_Established";
const string S_CALL_FE_TERMINATED  = "S_FETerminated";

// List of Valid Events in the Stmc
const string E_ONHOOK = "E_Onhook";
const string E_OFFOOK = "E_Offhook";
const string E_DIGIT_COLLECT = "E_DigitCollect";
const string E_DIGIT_COLLECT_COMPLETE = "E_DigitCollectComplete";
const string E_OG_RING = "E_OGRing";
const string E_IC_RING = "E_ICRing";
const string E_TIMEOUT = "E_Timeout";

}; // end namespace declaration

class Telephone : public BasicFsm
{
private :
string digitsCollected;
string myNumber;
time_t  call_st_time;
time_t  call_end_time;

public :
Telephone();
Telephone(string myNumber);
~Telephone();
void DispDigitsCollected()
{
cout << "Digits collected so far = " << digitsCollected << endl;
}

friend int OffHookAtIdle(BasicFsm* pFsm, string event, int info);
friend int DigitCollect(BasicFsm* pFsm, string event, int info);
friend int DigitCollectComplete(BasicFsm* pFsm, string event, int info);
friend int TimeoutAtDigitCollection(BasicFsm* pFsm, string event, int info);
friend int OffHookAtEstablished(BasicFsm* pFsm, string event, int info);
/// This state-event processing list of functions are not complete

void InitFsm(); // This will init the fsm functions
}; // end of Telephone class declaration

using namespace std;
using namespace TelephoneEnumsT;

Telephone::Telephone()
{
digitsCollected.clear();
myNumber.clear();
call_st_time = 0;
call_end_time = 0;
}

Telephone::Telephone(string myNumber)
{
digitsCollected.clear();
myNumber.assign(myNumber);
call_st_time = 0;
call_end_time = 0;
}

Telephone::~Telephone()
{

}

int OffHookAtIdle(BasicFsm* pFsm, string event, int info)
{
stringstream logMsg;

try {
Telephone* pPhone = static_cast <Telephone*> (pFsm);
logMsg << "In Function OffHookAtIdle() " << " At State "
<< pFsm->GetState() << " For Event " << event << endl;

cout << logMsg.str() << endl;
// Do the required Processing

pPhone->digitsCollected.clear();

// Do state transition and do some book keeping
pPhone->TransitionToState(TelephoneEnumsT::S_DIGIT_COLLECTION);
pPhone->SetPreviousEvent(event);
} // end try
catch (exception& Error) {
stringstream logErr;
logErr << "Exception at OffHookAtIdle(), Error : " << Error.what();

}
return(0);
}

int DigitCollect(BasicFsm* pFsm, string event, int info)
{
stringstream logMsg;

try {
Telephone* pPhone = static_cast <Telephone*> (pFsm);
logMsg << "In Function DigitCollect() " << " At State "
<< pFsm->GetState() << " For Event " << event
<< " adding digit to dialed number " << info << endl;

cout << logMsg.str() << endl;
// Do the required Processing

char cinfo[8];
sprintf(cinfo,"%d",info);
pPhone->digitsCollected.append((const char *) (&cinfo), (size_t)(1));

// Do state transition and do some book keeping
pPhone->SetPreviousEvent(event);
} // end try
catch (exception& Error) {
stringstream logErr;
logErr << "Exception at DigitCollect(), Error : " << Error.what();

}
return(0);
}

int DigitCollectComplete(BasicFsm* pFsm, string event, int info)
{
// Do the required Processing
return(0);
}

int TimeoutAtDigitCollection(BasicFsm* pFsm, string event, int info)
{
// Do the required Processing
return(0);
}

int OffHookAtEstablished(BasicFsm* pFsm, string event, int info)
{

// Do the required Processing
return(0);
}

void  Telephone::InitFsm()
{
TelephoneEnumsT::E_OFFOOK,
&(OffHookAtIdle));

TelephoneEnumsT::E_DIGIT_COLLECT,
&(DigitCollect));

// Add State - Event functions so forth...
}

int main()
{

int fsmStatus;
Telephone myPhone1("1112223333");
myPhone1.InitFsm();

// Test some event handlers
myPhone1.TransitionToState(S_Idle);
fsmStatus = myPhone1.Fsm(E_OFFOOK, 0);
fsmStatus = myPhone1.Fsm(E_DIGIT_COLLECT, 9);

Telephone myPhone2("2223331234");
myPhone2.InitFsm();

// Test some event handlers
myPhone2.TransitionToState(S_Idle);
fsmStatus = myPhone2.Fsm(E_OFFOOK, 1);
fsmStatus = myPhone2.Fsm(E_DIGIT_COLLECT, 2);

myPhone1.DispDigitsCollected();
myPhone2.DispDigitsCollected();

// Authors comment: try to modify the base class, which can still be
// inherited by any FSM implementing classes
// where you just need to do Telephone::InitFsm();
// instead of doing myPhone1.InitFsm(); and myPhone2.InitFsm(); ...

}
/////// End File : BasicFsmTest.cpp  //////////////////////////////////////////

-

## Two beginners mistakes:

#ifndef _BasicFsmT_h
#define _BasicFsmT_h


Using a leading underscore is a bad idea. The exact rules are complex and people usually get them wrong. So just don't use them and you will be safe.

### using directives.

using namespace std;


Never do this (at file scope) in a header file (any using directive). It means that if I include your code all the standard libraries have been imported into the global namespace for my code which may break it. This may potentially stop people from using your code.

Even in source files this is a bad idea. The whole reason the namespace is called std rather than standard is so prefixing items with std:: is not a major problem. Please start to use this.

If you really don't want to use std:: (you should) then you import specific things by doing

using std::cin;  // only imports std::cin into the current namespace.


This is also usable within a scope:

void foo()
{
using std::cin;
cin << "Hi there\n";
}
void bar()
{
cin << "This will fail to compile\n";
}


You shoudl read this: Why is 'using namespace std;' considered a bad practice in C++?

The most important answer for me is: http://stackoverflow.com/a/1453605/14065

## Interfaces:

Your BasicFsm uses function pointers. This is very C. An easy way is to define an interface that implements the method. This will make the code easier to read and write:

// StateMachine Method prototype
typedef int (*pFsmMethodT) (BasicFsm* pFSM, string event, int info);

// I would write:
struct  FsmMethodInterface
{
virtual ~FsmMethodInterface() {}
virtual int doWork(BasicFsm& pFSM, std::string event, int info) = 0;
};
// Note: unless pFSM can be NULL (I suspect it can't) then you should
//       pass it by reference (then you don't need to check for NULL).


This is also more useful as it allows you to maintain state in the callback if required.

### Constructor

/// Description : Default Constructor, called by derrived classes object
/// @param[in]
/// @returns
BasicFsm::BasicFsm()
{
m_statesVec.clear();
m_eventsVec.clear();
m_fsmStateStr.clear();
m_fsmPrevEventStr.clear();
m_fsmPrevStateStr.clear();
m_stateEventToMethodMap.clear();
}


This is doing no useful work. All those members are constructed empty. Just remove the constructor if it does nothing explicit.

Comments that do nothing but repeat what the code says are worse than useless. They can fall out of sync with the code and provide no meaningful information to the a maintainer (and thus waste space).

/// Description : Add a state to be handled by the fsm
///
/// @param[in] : state to be handled by the fsm
/// @returns
{


The code explains what it is doing (with menaingful method/variable names). The comments should explain WHY it is doing it. If the why is obvious that don't write anything.

Exceptions:

} // end try
catch(exception& Error) {
stringstream logErr;
logErr << "Exception at BasicFsm::fsm, Error : " << Error.what();
}


Best to catch exceptions by const reference. YOu probably don't want to alter the exception.

Also exceptions do not need to be derived from std::exception (they could be std::string or int or anything else. catch(...) catches anything. But if you use this the best you can usually do is log and re-throw the exception.

So you logged the exception (which is good). But is that enough (It may be I don;t the code well enough). If an exception was thrown can you continue? The fact that something failed would suggest that unless you explicitly fix it the state of the machine is not good. If you cant't fix it then after you log the exception you should probably re-throw it.

## Below is a discussion Seth and I are having.

It turns out Seths comments are more accurate then mine.
I am leaving the original comments for context.

In modern C++ functors and duck typing are more heavily used (then would be suggested by my answer above).

Seth thinks that they can be used in the current situation (I hope they can). But I can see how this will be done. We needed more space than the comments provided so we are working in the answer at the moment. This is an ongoing discussion which when resolved will be cleaned up.

### From @Seth

So the more modern way to add generic functions would be:

int AddStateEventMethod(string state, string event, std::function<int(BasicFsm*, string, int)> func)
{
/* CODE AS BEFORE */

// Add the function pointer to be called for the specified state-event pair

stateNEvent = state + event;
m_stateEventToMethodMap[stateNEvent] = func;
}

std::map<std::string, std::function<int(BasicFsm*, string, int)>> m_stateEventToMethodMap;


### Response from @Loki

Unfortunately this provides exactly zero benefit over the original and as such is not really modern C++. The whole point of modern C++ duck typing is that you could pass any object that behaves like a function. This actively prevents this and we have exactly the same code as above (just wrapped with std::function) so no real benefit.

To make this work in a modern C++ way you need to be able to templatize int AddStateEventMethod() but I can see how that would work.

template<typename T>
int BasicFsm::AddStateEventMethod<T>(string state, string event, T func)
{
/* CODE AS BEFORE */

// Add the function pointer to be called for the specified state-event pair

-- What goes here --
}

-
NOTE: The practice of adding the "_" or "__" at the beginning and end of the defines, is a technique long used in the layers of abstraction "hardware/middleware" to prevent that the end developer do make errors of inclusion. example in HAL: __UART_H__, in user code: UART_H. if in some cases the use of this "defines" is correct. +1 For the detailed answer. –  RTOSkit Jan 9 '13 at 0:31
While using function pointers is very C, making users of the class inherit from one of your classes is very "old C++". Isn't it better to write it as either a template if possible, else take an std::function? –  Seth Carnegie Jan 9 '13 at 2:29
@SethCarnegie: I would agree in most situations. But not in this specific case. Because the object is storing a container full of functors. You need to use a consistent interface to facilitate storage. –  Loki Astari Jan 9 '13 at 6:52
@RTOSkit: The implementation is allowed to use any identifers it likes (such as __UART_H__). Unfortunately using this pattern in user code is not legal. Thus adding " __ " (double underscore) is always illegal. And adding " _ " (single underscore) at the beginning of an identifier is also always wrong with macros (assuming you follow the rule of making macros all upper-case). So in user space code we should be very careful to use underscore. –  Loki Astari Jan 9 '13 at 7:05
Thanks for the correct justification and interpretation, in order to know that the "low level" we are always more illegal :) .You will know that when need optimizing code, we try using more the precompiler and these "illegal defines" are a strategy that not seem corect but are fluid and deterministic. ...¿What is upper-case? ? :) –  RTOSkit Jan 9 '13 at 7:29

Don't try to inhibit bugs, define pre conditions instead

Your AddState searches to see if there's already a state with the supplied identifier, and if that's the case it silently does nothing. If duplicates are not allowed you should either return an error / throw exception or simply assert. Robustness aside I'd rather have:

int BasicFsm::AddState(string state)
{
assert(find(m_statesVec.begin(), m_statesVec.end(), state) != m_statesVec.end());
m_statesVec.push_back(state);
}


Which to top it of is also faster. A good rule is to fail as fast as possible, this way you're more likely to spend your time debugging the actual bug instead of its consequences.

Learn when and where to use const, and const reference in particular

You have a couple of instances of this, but as a rule of thumb builtins are the only types which should be passed by value. There's very few instances where you need a copy of an argument. AddState(string state) should be AddState(const string& state). If you don't need to modify the argument add const, this way the caller knows what to expect.

Unless you're INCREDIBLY concerned about memory / performance don't use bare function pointers

They're just so incredibly inferior to std::function ( or boost::function for that matter ). Describing the power of std::bind & std::function would be quite lengthy, so unless you want to know anything in particular it's probably better to google.

Don't make things virtual just for the heck of it

I see no reason for why you want all the member functions of Fsm to be virtual, you're unnecessarily paying for virtual dispatch and by making member functions in your base virtual you're deceiving the user of it. Qualifiers describes intent, by making all functions virtual you're saying "All calls to me can do pretty much anything under the sun". If you later find that you need AddState to be virtual, make it virtual at that point instead. Good design is much more about restricting than enabling.

Don't use strings for static identifiers

This is a very common mistake made even by pretty experienced programmers, but strings makes for very poor static identifiers. They're expensive to compare for equality, requires unnecessary amounts of storage, introduces a whole slew of possibilities for user errors which are hard to impossible to check for at compile time, and inhibits the possibilities for generic programming. In this case there's nothing really stopping you from using static tags. IE:

    struct Event { virtual ~Event(){} }; // Needs at least 1 virtual function for vtable
struct OnHook : public Event {};
//...

struct State { virtual ~State(){} }; // Dtor for vtable
struct IdleState : public State {};
//...
map< std::pair< Loki::TypeInfo, Loki::TypeInfo >, pFsmMethodT > m_stateEventToMethodMap;
//...
void BasicFsm::AddStateEventMethod( const State& state, const Event& event, pFsmMethodT pFunc)
{
m_stateEventToMethodMap[ std::make_pair( Loki::TypeInfo( typeid( state ) ), Loki::TypeInfo( typeid( event ) ) ) ] = pFunc;
}


Loki::TypeInfo is a handy container for std::type_info which gives us the ability to use them as keys, if you opt to not use RTTI you need another way associate a type with unique ID, there's a ton of ways to do this ( the easiest probably being a virtual function ). This way is faster than using strings, and now we can't for example pass an event as a state by accident, or introduce user created strings which doesn't map to valid states or events.

-
Instead of Loki::TypeInfo you can use std::type_index in C++11. –  Seth Carnegie Jan 9 '13 at 20:27
Ah, cool, still stuck in the old times where I don't have C++11 :) –  Ylisar Jan 9 '13 at 20:29