A "generalized" finite state machine implementation

Question

I often have the need to implement an object which is capable of switching its behaviour in response to a user command. For example, this could be the case of a class representig device connected to a PC and controlled by the user via a GUI. More generally, the device has to live on its own, with its own operation scheduling. Since I'd like to "extract" this behaviour from the specific device class in order to enhance code re-use, here I propose a templated finite state machine class using Qt. I also reported an example usage in class A. What do you ( more experienced programmers than me :) think about that? Is it the "correct" way to design such a class? Are there performance issues ?

template < class Base,
           typename T,
           class ThreadPolicy>
class FSM
{
public:
    typedef bool (Base::*my_func)();
    struct SState {
        SState(){}
        SState(const T& id_arg,
               const T& next_arg,
               const T& error_arg,
               const QList<T>& branches_arg,
               const my_func& op_arg) :
            id(id_arg),
            next(next_arg),
            error(error_arg),
            branches(branches_arg),
            op(op_arg)
        {}
        T id;       // state ID
        T next;    // next state
        T error;    // in case of error
        QList<T> branches; // allowed state switching from current
        my_func op; // operation associated with current state
    };
    typedef QMap<T ,SState> SMap;
    bool switchState(const T& ns){
        return _checkAllowed(ns);
    }
    bool addState(const T& id, const SState& s){
        return _register(id, s);
    }
protected:

    void _loop(Base* ptr){
        if ((ptr->*m_states[m_state].op)()) {
            ThreadPolicy::Lock();
            if(m_externalSwitch){
                m_externalSwitch = false;
                ThreadPolicy::Unlock();
                return;
            }
            m_state = m_states[m_state].next;
            ThreadPolicy::Unlock();
        } else {
            ThreadPolicy::Lock();
            if(m_externalSwitch){
                m_externalSwitch = false;
                ThreadPolicy::Unlock();
                return;
            }
            m_state = m_states[m_state].error;
            ThreadPolicy::Unlock();
        }
    }
    bool _checkAllowed(const T& cmd){
        if (!m_states[m_state].branches.contains(cmd)) { return false;}
        ThreadPolicy::Lock();
        m_state = cmd;
        m_externalSwitch = true;
        ThreadPolicy::Unlock();
        return true;
    }

    bool _register(const SState& s){
        if(m_states.find(s.id) != m_states.end()) { return false; } // state with same ID already exist
        m_states[s.id] = s; // add the new state to the map
        return true;
    }
    SMap m_states; // map states to Baseclass methods
    T m_state;  // holds my current state
    bool m_externalSwitch; // check if user request a state switch
};

class A :
        public QObject,
        public FSM< A, QString, MultiThreaded >
{
    Q_OBJECT
    A(){
//        SState startState; myState.branches << "start" << "stop";
        _register(SState("start",
                         "start",
                         "stop",QStringList(("start","stop")),
                         &A::_doStart));
        _register(SState("stop",
                         "stop",
                         "stop",QStringList(("stop","start")),
                         &A::_doStop));
    }

private slots:
    void run(){
        for(;;){
            _loop(this);
            QCoreApplication::processEvents();
        }
    }
private:
    bool _doStart(){ return true;}
    bool _doStop(){ return true;}

};

Answer 1

A. What do you ( more experienced programmers than me :) think about that? Is it the "correct" way to design such a class? Are there performance issues ?

OK! I had a rough look at your design, and it doesn't really feel good to me for a general purpose FSM framework. That's too narrow to be usable in a widened context. Some points of critique:

1. You're depending on Qt :( ; at least you should use C++ STL components for your implementation details.
2. Your states should be (specialized) classes on their own, that implement the behavior directly. The FSM class itself, should be independent (especially not implement) from their behavior.
3. You don't support more complex state diagrams, including sub-state (machines)/composite states, concurrent FSM pathes (fork, junctions), active states (repeated asynchronous do operations), ...

In general I'd recommend to follow the GoF State Pattern for FSM implementation. For very simple state diagrams a switch(event) case <event>: changeState(newState) might be enough. But to render events as method entries of the FSM, and delegate these to the current state class instance, makes the whole construct much more flexible. Think about optional parameters coming along with a particular event, and you'll need to extend your state machine design for these.

In general your approach to use a CRTP for your state machine is a good idea, but for what you demonstrated, simple dynamic polymorphism (using virtual member functions) would work well also.

About performance issues, don't think you will hit ones with your current environment, but that completely depends where and in which context you want to deploy.

I want to recommend you having a look at my State Machine Class Template framework STTCL, which provides various C++ template based aspects of UML 2.0 compliant state machines, following the already mentioned GoF State Pattern.

Answer 2

if it is still relevant, I have implemented a finite state machine in C++ which uses the Object OP, it is fairly simple to use and if you look at the main.cpp there is an example.

The code is here and it is compiled as a library now.

Finite State Machine

Let me know if it is what you want!

Cheers,

Andrea