Designing a state machine in C++ using the STL

Question

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 AddState(string state);
    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 
int BasicFsm::AddState(string state)
{
    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_REMOTE_ANSWER = "E_RemoteAnswer";
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()
{
    AddStateEventMethod(TelephoneEnumsT::S_Idle, 
                        TelephoneEnumsT::E_OFFOOK, 
                        &(OffHookAtIdle));

    AddStateEventMethod(TelephoneEnumsT::S_DIGIT_COLLECTION, 
                        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  //////////////////////////////////////////

Answer 1

Two beginners mistakes:

Leading underscore in identifers

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

See: What are the rules about using an underscore in a C++ identifier?

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: https://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:

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 
int BasicFsm::AddState(string state)
{

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

Answer 2

Adding to the previous post.

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.