Design of a Finite State Machine C++ Template. Part Two.

Author / Автор: Sergey Satskiy

Publication date / Опубликовано: 06.08.2004
Version / Версия текста: 1.0

A Year Later

A year has passed since the time of publishing the first part of the article. During that period the template has been slightly modified and new features were introduced. The second part of the article describes new ideas and shows the most non-trivial code fragments.

Improvements

At the end of the first part of the article some specific manipulators were mentioned. Those manipulators supposed to mark state machine transitions that should be ignored or an exception should be generated instead of a transition. The updated template has those manipulators implemented. The following example illustrates the manipulators usage using a state machine description in the example from the first part of the article.

	...
    #define FSMStateType   string
    #define FSMEventType   Events

    SStateMachine< StateType,
                   EventType,
                   SEmptyFunctor<StateType,EventType>,
                   SThrowStrategy<EventType>
                 >
    MyMachine(

        FSM_BEGIN( "empty" )

        FSM_STATES           "empty"      << "number"  << "identifier" << "unknown"

        FSM_EVENT(letter)    "identifier" << "unknown" << "identifier" << "unknown"
        FSM_EVENT(digit)     "number"     << "number"  << "identifier" << "unknown"

        FSM_END
             );

    #undef FSMStateType
    #undef FSMEventType
	...

It is possible to note that as soon as the machine comes to the state "unknown" any event will be ignored. Here the same state "unknown" is used. The code can be rewritten using a manipulator as follows.

    MyMachine(

        FSM_BEGIN( "empty" )

        FSM_STATES           "empty"      << "number"  << "identifier" << "unknown"

        FSM_EVENT(letter)    "identifier" << "unknown" << "identifier" << NONE
        FSM_EVENT(digit)     "number"     << "number"  << "identifier" << NONE

        FSM_END
             );

The NONE manipulator indicates that nothing should be done.

It is necessary to note that there is still a tiny difference between usage of the same state in the transition table and NONE manipulator. In case of manipulator there will be no actions at all - an event is ignored. In case of specifying the same state the functions OnEnter(. . .) and OnExit(. . .) will be called if they are specified. The manipulator usage is better in my opinion. It makes the code author intention clearer.

In addition to NONE manipulator the template supports one more: EXCEPTION. The EXCEPTION manipulator will lead to an exception generation instead of a transition and resetting a machine to the start state.

Some Theoretical Thoughts and the Second Template Version

Let us come back to function calls in the template described in the first part of the article. Functions are linked to states and it was required that a state type had OnEnter(. . .) and OnExit(. . .) member functions defined with the proper prototypes. It could be depicted as follows.

Figure 1. Finite state machine model with functions bound to states

Sometimes it is convenient to bind function calls to states but not to transitions though. That could be depicted as follows.

Figure 2. Finite state machine model with functions bound to transitions

Bearing in mind that the variable length list processing problem has already been solved there is only a question of a good notation for binding function calls to transitions. The operator [ ] could be used in C++. The figure 2 depicted state machine could be written as follows using the [ ] notation.

	...
    MyMachine(
        FUNCFSM_BEGIN( Start )

        FUNCFSM_STATES           Start  <<  S1      <<  S2      <<  S3

        FUNCFSM_EVENT(E1)        S1[f1] <<  NONE    <<  S2[f3]  <<  NONE
        FUNCFSM_EVENT(E2)        S2[f2] <<  NONE    <<  NONE    <<  NONE
        FUNCFSM_EVENT(E3)        NONE   <<  S3[f4]  <<  S3[f4]  <<  NONE

        FUNCFSM_END
             );
	...

A function, which should be called for a particular transition, is given in square brackets together with a new state. Surely a question appears what kind of functions could be specified here. There is a variety of options: free function, class member function, virtual class member function etc. A good solution to store a function object is proposed by one of the boost libraries (http://www.boost.org). The boost::function object is a template which allows to store and then to call anything which uses () notation. The following definition is suitable for the template.

typedef boost::function< void ( StateType &  From, 
                                EventType &, 
                                StateType &  To ) >   CallbackType;

Now we need to store a new state, callback function and a manipulator for each of the transitions. Two last elements are optional. A structure is suitable to store the mentioned elements.

        // A bundle of the state related information
    template < typename SState, typename SEvent >
    struct SFuncBundle
    {
        SState                                  NewState;
        int                                     Manipulator;
        boost::function< void ( SState &,
                                SEvent &,
                                SState & ) >    Callback;

        SFuncBundle() {}
    };

The operator [ ] implementation is not complicated. The only important detail that should be kept in mind is that there are two options: a new state with or without a callback function. In both cases the overloaded for transitions operator << expects a reference to a state. In order to simplify developers' life a template could be introduced.

template < typename  Child,
           typename  Event >
    class StateBase
    {
            // Should all of them be const? - No. It is easy to imagine that
            // some fields in the states and events should be changed
        typedef boost::function< void ( Child &,
                                        Event &,
                                        Child & ) >   CallbackType;

        private:
            CallbackType    Callback;

        protected:
            StateBase() : Callback( 0 ) {}

        public:
            inline Child & operator [] ( const CallbackType &  NewCallback )
            {
                Callback = NewCallback;
                return static_cast< Child & >( *this );
            }
            
            inline CallbackType  GetCallback( void )
            {
                CallbackType        Temporary( Callback );

                Callback = 0;
                return Temporary;
            }
    };

There are some interesting details here. The GetCallback(. . .) function cannot be const. A Proxy: class, which collects information about transitions, may have many transitions into the same state with different callback functions. So as soon as information about a necessary callback is collected a function object should be cleaned. Moreover the operator [ ] cannot be const either because it memorizes a callback function and therefore cannot be applied to a const reference to a state. That circumstatnces dictate to create instances of states before its usage in a template constructor. In other words a real code will be similar to the following.

. . .
class MyEvent { . . . };

class MyState : public StateBase< MyState, MyEvent >
{
. . .
};

MyEvent    E1(. . .), E2(. . .);    // Could be also instaniated 
                                    // in the MyMachine constructor
MyState    Start(. . .), S1(. . .), S2(. . .), S3(. . .);

    MyMachine(
        FUNCFSM_BEGIN( Start )

        FUNCFSM_STATES           Start  <<  S1      <<  S2      <<  S3

        FUNCFSM_EVENT(E1)        S1[f1] <<  NONE    <<  S2[f3]  <<  NONE
        FUNCFSM_EVENT(E2)        S2[f2] <<  NONE    <<  NONE    <<  NONE
        FUNCFSM_EVENT(E3)        NONE   <<  S3[f4]  <<  S3[f4]  <<  NONE

        FUNCFSM_END
             );
    . . .

Summary

Implementation of all the rest is similar to what is done for the first version of the template. The final prototype of the second template version is as follows.

    template < typename SState, 
               typename SEvent, 
               typename SUnknownEventStrategy = SThrowStrategy<SEvent> > 

Here there are no strategies of calling functions, which are bound to states.

New macroses are introduced to simplify a finite state machine description in a constructor. The macroses purpose and names are the same as for the first version except the added prefix FUNC.

Getting of the finite state machine as well as passing an event to a state machine is done in the same manner as for the first version of a template.

Advantages and Drawbacks

The drawbacks list of the first template version can be extended with the following:

• It is required to have state instances created first and only after that use them in a machine description.
• A state type must implement the operator [ ]. That leads to impossibility to use standard types directly. It is required to write a wrapper around them first. It is also required to remember how to implement operator [ ] properly or to derive from a ready template class.
• The cast operator is used in a state template base class. It is unavoidable unfortunately.

Advantagies are the same as for the first template version.

The given drawbacks list does not lead to large overheads for the "decorative" part of code while in some cases the model of bounding callbacks to transitions seems much better.

It is possible to implement a template, which allows both models (callbacks are linked to states and to transitions) at the same time. There is a chance that it is implemented one day.

Example

Examples source code could be found on the author's web site: (http://satsky.spb.ru).

References

1. David Vandevoorde, Nicolai M. Josuttis. C++ Templates. The Complete Guide. Addison-Wesley, 2003.
2. The boost library documentation (http://www.boost.org).