QP/C++
7. Coding Hierarchical State Machines

This QP/C++ Tutorial is adapted from Chapter 1 of Practical UML Statecharts in C/C++, Second Edition
by Miro Samek, the founder and president of Quantum Leaps, LLC.

qp_tutorial.jpg

Prev: 6. Defining Event Signals and Event Parameters
Next: 8. Using the Built-in Real-Time Kernels and Third-Party RTOSes

Contrary to widespread misconceptions, you don't need big design automation tools to translate hierarchical state machines (UML statecharts) into efficient and highly maintainable C or C++. This section explains how to hand-code the Ship state machine from Figure 5-2 with the help of the QF real-time framework and the QEP hierarchical processor, which is also part of the QP event-driven platform. Once you know how to code this state machine, you know how to code them all.

The source code for the Ship state machine is found in the file ship.cpp located either in the DOS version or the ARM-Cortex version of the "Fly 'n' Shoot" game. I break the explanation of this file into three steps.

7.1 Step 1: Defining the Ship Structure

In the first step you define the Ship data structure. Just like in case of events, you use inheritance to derive the Ship structure from the framework structure QActive (see the sidebar Encapsulation and Single Inheritance in C). Creating this inheritance relationship ties the Ship structure to the QF framework. The main responsibility of the QActive base structure is to store the information about the current active state of the state machine, as well as the event queue and priority level of the Ship active object. In fact, QActive itself derives from a simpler QEP structure QHsm that represents just the current active state of a hierarchical state machine. On top of that information, almost every state machine must also store other "extended-state" information. For example, the Ship object is responsible for maintaining the Ship position as well as the score accumulated in the game. You supply this additional information by means of data members enlisted after the base structure member super, as shown in Listing 7-1.

Listing 7-1 Deriving the Ship structure in file ship.cpp. 

 (1) #include "qp_port.h"
 (2) #include "bsp.h"
 (3) #include "game.h"

 (4) class Ship 
 (5)     : public QActive                               // extend the QActive class
     {                      
 (6)     uint8_t m_x;
 (7)     uint8_t m_y;
 (8)     uint8_t m_exp_ctr;
 (9)     uint16_t m_score;

     public:
(10)     Ship(void) : QActive((QState)&Ship::initial),
                      m_x(GAME_SHIP_X), m_y(GAME_SHIP_Y) {}
     private:
(11)     static QState active   (Ship *me, QEvent const *e);
(12)     static QState parked   (Ship *me, QEvent const *e);
(13)     static QState flying   (Ship *me, QEvent const *e);
(14)     static QState exploding(Ship *me, QEvent const *e);

(15)     static QState initial  (Ship *me, QEvent const *e);
     };

(16) static Ship l_ship;             // the sole instance of the Ship active object

     // global objects ------------------------------------------------------------
(17) QActive * const AO_Ship = &l_ship;                // opaque pointer to Ship AO
Note:
I like to keep active objects, and indeed all state machine objects (such as Mines), strictly encapsulated. Therefore, I don't put the state machine class definitions in header files but rather define them right in the implementation file, such as ship.cpp. That way, I can be sure that the internal data members of the Ship structure are not known to any other parts of the application.
Note:
The state-handler functions are necessarily static members of the class, so that they don't use the "this-calling convention". Please see the Sidebar: Pointers to Member Functions in C++.

Sidebar: Pointers to Member Functions in C++

The C++ state handler function takes the "me" pointer of its own class type, through which it accesses the state machine data members and member functions (e.g., me->operand1 = ...). This is because the state-handler functions are static members of the QHsm subclass, such as the Ship state machine class Calc (see Listing 7-1).

An obvious and more elegant alternative would be to make the state-handler functions regular, non-static class members, which would allow them to access the class members much more naturally through the implicit "this" pointer.

Indeed this much more elegant alternative has been used in the earlier QEP/C++ version published in the first edition of the "Practical Statecharts in C/C++" book. However, this alternative requires using pointers-to-member-functions instead of simple pointers-to-functions, which turned out to be a problem in practice.

Even though the earlier C++ version of QEP used pointers-to-member-functions in a rather standard way, the embedded developers have filed a number of alarming reports from the trenches where the elegant approach either had very lousy performance, or did not work at all. For example, some embedded C++ compilers used over 30 machine instructions to de-reference a pointer-to-member-function and only 3 to de-reference a regular pointer-to-function. Needless to say, 3 machine instructions should do the job.

As it turns out, too many C++ compilers simply don't support pointers-to-member-functions well due to interference of other language features such as multiple inheritance and virtual base classes. As eloquently explained in the online article "Member Function Pointers and the Fastest Possible C++ Delegates" (see "Member Function Pointers and the Fastest Possible C++ Delegates" at http://www.codeproject.com/cpp/FastDelegate.asp), even such widespread and important frameworks as the MFC actually use pointers-to-member-functions in a non-standard way by subverting the normal C++ type checking.

To avoid inefficiencies and portability issues, the current C++ version of QEP does not to use pointers-to-member-functions, but simply plain pointers-to-functions to static member functions that don't have the "this" pointer and therefore are not affected by polymorphism or multiple inheritance. Please note that the explicit "me" pointer required by static class members plays the same role as the "context" pointer required by the object-oriented State design pattern (see Chapter 3 in Practical UML Statecharts in C/C++, Second Edition).

7.2 Step 2: Initializing the State Machine

The state machine initialization is divided into the following two steps for increased flexibility and better control of the initialization timeline:

  1. The state machine constructor; and
  2. The top-most initial transition.

The state machine constructor, such as Ship::Ship() (see Listing 7-1(10)), intentionally does not execute the top-most initial transition defined in the initial pseudostate because at that time some vital objects can be missing and critical hardware might not be properly initialized yet. Instead, the state machine constructor merely puts the state machine in the initial pseudostate. Later, the user code must trigger the top-most initial transition explicitly, which happens actually inside the function QActive::start() (see Listing 3-11(15-17)). Listing 7-2 shows the initialization (the initial pseudostate) of the Ship active object.

Listing 7-2 Instantiation and Initialization of the Ship active object in ship.cpp. 

 (1) QState Ship::initial(Ship *me, QEvent const *) {
 (2)     me->subscribe(TIME_TICK_SIG);
 (3)     me->subscribe(PLAYER_TRIGGER_SIG);
 (4)     return Q_TRAN(&Ship::active);               // top-most initial transition
     }
Note:
The macro Q_TRAN() must always follow the return statement.

7.3 Step 3: Defining State Handler Functions

In the last step, you actually code the Ship state machine by implementing one state at a time as a state handler function. To determine what elements belong the any given state handler function, you follow around the state's boundary in the diagram (Figure 5-2). You need to implement all transitions originating at the boundary, any entry and exit actions defined in the state, as well as all internal transitions enlisted directly in the state. Additionally, if there is an initial transition embedded directly in the state, you need to implement it as well.

Take for example the state "flying" shown in Figure 5-2. This state has an entry action and two transitions originating at its boundary: HIT_WALL and HIT_MINE(type), as well as three internal transitions TIME_TICK, PLAYER_TRIGGER, and DESTROYED_MINE(score). The "flying" state nests inside the "active" superstate. Listing 7-3 shows two state handler functions of the Ship state machine from Figure 5-2. The state handler functions correspond to the states "active" and "flying", respectively. The explanation section immediately following the listing highlights the important implementation techniques.

Listing 7-3 State handler functions for states "active" and "flying" in ship.cpp. 

 (1) QState Ship::active(Ship *me, QEvent const *e) {
 (2)     switch (e->sig) {
 (3)         case Q_INIT_SIG: {                        // nested initial transition
 (4)             // any actions associated with the initial transition
 (5)             return Q_TRAN(&Ship::parked);
             }
 (6)         case PLAYER_SHIP_MOVE_SIG: {
 (7)             me->m_x = ((ObjectPosEvt const *)e)->x;
 (8)             me->m_y = ((ObjectPosEvt const *)e)->y;
 (9)             return Q_HANDLED();
             }
         }
(10)     return Q_SUPER(&QHsm::top);
     }
     //............................................................................
     QState Ship::flying(Ship *me, QEvent const *e) {
         switch (e->sig) {
(11)         case Q_ENTRY_SIG: {
(12)             ScoreEvt *sev;

                 me->m_score = 0;                                // reset the score
(13)             sev = Q_NEW(ScoreEvt, SCORE_SIG);
(14)             sev->score = me->m_score;
(15)             AO_Tunnel->postFIFO(sev);
(16)             return Q_HANDLED();
             }
             case TIME_TICK_SIG: {
                 // tell the Tunnel to draw the Ship and test for hits
                 ObjectImageEvt *oie = Q_NEW(ObjectImageEvt, SHIP_IMG_SIG);
                 oie->x   = me->m_x;
                 oie->y   = me->m_y;
                 oie->bmp = SHIP_BMP;
                 AO_Tunnel->postFIFO(oie);

                 ++me->m_score;   // increment the score for surviving another tick

                 if ((me->m_score % 10) == 0) {            // is the score "round"?
                     ScoreEvt *sev = Q_NEW(ScoreEvt, SCORE_SIG);
                     sev->score = me->m_score;
                     AO_Tunnel->postFIFO(sev);
                 }

                 return Q_HANDLED();
             }
             case PLAYER_TRIGGER_SIG: {                      // trigger the Missile
                 ObjectPosEvt *ope = Q_NEW(ObjectPosEvt, MISSILE_FIRE_SIG);
                 ope->x = me->m_x;
                 ope->y = me->m_y + SHIP_HEIGHT - 1;
                 AO_Missile->postFIFO(ope);
                 return Q_HANDLED();
             }
             case DESTROYED_MINE_SIG: {
                 me->m_score += ((ScoreEvt const *)e)->score;
                 // the score will be sent to the Tunnel by the next TIME_TICK
                 return Q_HANDLED();
             }
(17)         case HIT_WALL_SIG:
(18)         case HIT_MINE_SIG: {
(19)             // any actions associated with the transition
(20)             return Q_TRAN(&Ship::exploding);
             }
         }
(21)     return Q_SUPER(&Ship::active);
     }
Note:
The initial transition must necessarily target a direct or transitive substate of a given state. An initial transition cannot target a peer state or go up in state hierarchy to higher-level states, which in the UML would represent a "malformed" state machine.
Note:
The association between the event signal and event structure (event parameters) is established at the time the event is generated. All recipients of that event must know about this association to perform the cast to the correct event structure.
Note:
In C++, a pointer-to-function QHsm::top() can be written either as QHsm::top, or &QHsm::top. Even though the notation QHsm::top is more succinct, I prefer adding the ampersand explicitly, to leave absolutely no doubt that I mean a pointer-to-function &QHsm::top.

When implementing state handler functions you need to keep in mind that the QEP event processor is in charge here rather than your code. QEP will invoke a state handler function for various reasons: for hierarchical event processing, for execution of entry and exit actions, for triggering initial transitions, or even just to elicit the superstate of a given state handler. Therefore, you should not assume that a state handler would be invoked only for processing signals enlisted in the case statements. You should avoid any code outside the switch statement, especially code that would have side effects.

Prev: 6. Defining Event Signals and Event Parameters
Next: 8. Using the Built-in Real-Time Kernels and Third-Party RTOSes

logo_ql_TM.jpg

Copyright © 2002-2011 Quantum Leaps, LLC. All Rights Reserved.
http://www.state-machine.com

Generated on Sun Feb 10 2013 18:15:15 for QP/C++ by   doxygen 1.7.6.1