QP/C++  7.2.1
Real-Time Embedded Framework
No Matches
State Machines

Design (SDS)

The behavior of each active object in QP Framework is specified by means of a hierarchical state machine (UML statechart), which is the most effective and elegant technique of describing event-driven behavior. The most important innovation of UML state machines over classical finite state machines (FSMs) is the hierarchical state nesting. The value of state nesting lies in avoiding repetitions, which are inevitable in the traditional "flat" FSM formalism and are the main reason for the "state-transition explosion" in FSMs. The semantics of state nesting allow substates to define only the differences of behavior from the superstates, thus promoting sharing and reusing behavior.

The Quantum Leaps Application Note A Crash Course in UML State Machines introduces the main state machine concepts backed up by examples.

The hallmark of the QP Framework implementation of UML state machines is traceability, which is direct, precise, and unambiguous mapping of every state machine element to human-readable, portable code. Preserving the traceability from requirements through design to code is essential for mission-critical systems, such as medical devices or avionic systems.

This section describes how to implement hierarchical state machines with the QP™/C real-time embedded framework, which is quite a mechanical process consisting of just a few simple rules. (In fact, the process of coding state machines in QP™/C has been automated by the QM model-based design and code-generating tool.)

To focus this discussion, this section uses the Calculator example, located in the directory qpcpp/examples/workstation/calc. This example has been used in the PSiCC2 book (Section 4.6 "Summary of Steps for Implementing HSMs with QEP")

This section explains how to code the following (marked) elements of a hierarchical state machine:

Fragment of the Calculator hierarchical state machine

[1] The top-most initial pseudo-state

[2] A state (nested in the implicit top state)

[3] An entry action to a state

[4] An exit action from a state

[5] An initial transition nested in a state

[6] A regular state transition

[7] A state (substate) nested in another state (superstate)

[8] Even more deeply nested substate

[9] A choice point with a guard

This section describes the QHsm state machine implementation strategy, suitable for manual coding of hierarchical state machines in QP™/C++. The alternative QMsm state machine implementation strategy, which QP™/C++ also supports, is not covered in this section, as the code needs to be generated automatically by the QM modeling tool.
Historical Notes
The previous implementation (from QP™/C++ version 3.x through 6.4.x) used state-handlers that were static members of the state machine class, which don't have the this pointer and therefore needed to use the specially supplied "me-> pointer" to access the members of the state machine class. That previous "me-> pointer" state machine implementation style is still supported in QP™/C++ for backwards compatibility with the existing code, but it is not recommended for new designs.

An even earlier QP™/C++ state machine implementation strategy, used in QP™/C++ version 2.x and published in the first edition of the PSiCC book, also implemented state handlers as regular members of the state machine class. However, this earlier implementation relied internally on pointers to member functions, which turned out to be a problematic in practice, because some embedded C++ compilers at the time didn't implement pointers to member functions efficiently. Therefore, the implementation published in the second edition of the PSiCC2 book, switched to static state-handler functions (without the this pointer), which allowed it to use internally the simple pointers to functions that are very efficient.

This latest "no me-> pointer" state machine implementation style in QP™/C++ applies a hybrid approach. Internally, it represents states as simple and efficient pointers to "state-caller" functions. But these "state-caller" functions call "state-handlers" as regular members of the state machine class, which have the this pointer and therefore can access all members of the state machine class naturally (without the need for the "me-> pointer").

State Machine Declaration

Hierarchical state machines are represented in QP™/C++ as subclasses of the QHsm abstract base class, which is defined in the header file qpcpp\include\qep.hpp. Please note that abstract classes like QP::QMsm, QP::QActive and QP::QMActive are also subclasses of QP::QHsm, so their subclasses also can have state machines.

[1] class Calc : public QP::QHsm {
[2] double m_operand1;
uint8_t m_operator;
[3] Calc() // constructor
[4] : QHsm(&initial) // superclass' constructor
[5] Q_STATE_DECL(initial);
[6] Q_STATE_DECL(on);
. . .
Hierarchical State Machine abstract base class (ABC)
Definition: qep.hpp:293
#define Q_STATE_DECL(state_)
Macro to generate a declaration of a state-handler, state-caller and a state-object for a given state...
Definition: qep.hpp:839

[1] Class Calc (Calculator) derives from QP::QHsm, so it can have a state machine

[2] The class can have data members (typically private), which will be accessible inside the state machine as the "extended-state variables".

[3] The class needs to provide a constructor, typically without any parameters.

[4] The constructor must call the appropriate superclass' constructor. The superclass' constructor takes the top-most a pointer to the initial pseudo-state (see step [5]), which binds the state-machine to the class.

[5] Each state machine must have exactly one initial pseudo-state, which by convention should be always called initial. The initial pseudo-state is declared with the macro Q_STATE_DECL(initial).

[6] The same Q_STATE_DECL() macro is also used to declare all other states in the state machine.

The Q_STATE_DECL() Macro

The Q_STATE_DECL() macro declares two functions for every state: the "state-handler" regular member function and the "state-caller" static member function. So, for example, the declaration of the "on" state Q_STATE_DECL(on) expands to the following two declarations within the Calc class:

[1] QP::QState on_h(QP::QEvt const * const e); // "state-handler"
[2] static QP::QState on(void * const me, QP::QEvt const * const e); // "state-caller"
Event class.
Definition: qep.hpp:163
std::uint_fast8_t QState
Type returned from state-handler functions.
Definition: qep.hpp:209

The two functions have each a different purpose.

[1] The "state-handler" on_h() is a regular member function used to implement the state behavior. As a regular class member, it has convenient, direct access to the state machine class attributes. The "state-handler" is called by the "state-caller".

[2] The "state-caller" on() is a static member function that has a simple job to call the state-handler member function on the specified instance of the class. Internally, the QEP event processor uses "state-callers" as unique "handles" for the states. Specifically, the QEP event processor uses the simple function pointers to these state-callers, which are simple objects (e.g. 32-bit addresses in ARM Cortex-M CPUs), because they don't use the this calling convention. These simple function pointers can be stored very efficiently inside the state machine objects and can be compared quickly inside the QEP algorithm that implements the UML semantics of hierarchical state machines.

See also
State-Handler Call Overhead
Because the state-handler functions are regular members of the state machine class, they can be virtual, which allows them to be overridden in the subclasses of a given state machine class. Such inheritance of entire sate machines is an advanced concept, which should be used only in very special circumstances and with great caution. To declare a virtual state-handler, you simply prepend virtual in front of the Q_STATE_DECL() macro, as in the following examples:
virtual Q_STATE_DECL(on);
virtual Q_STATE_DECL(ready);
. . .

State Machine Definition

The definition of the state machine class is the actual code for your state machine. You need to define (i.e., write the code for) all "state-handler" member functions you declared in the state machine class declaration. You don't need to explicitly define the "state-caller" static functions, because they are synthesized implicitly in the macro Q_STATE_DEF()).

One important aspect to realize about coding "state-handler" functions is that they are always called from the QEP event processor. The purpose of the "state-handlers" is to perform your specific actions and then to tell the event processor what needs to be done with the state machine. For example, if your "state-handler" performs a state transition, it executes some actions and then it calls the special tran(<target>) function, where it specifies the <target> state of this state transition. The state-handler then returns the status from the tran() function, and through this return value it informs the QEP event processor what needs to be done with the state machine. Based on this information, the event-processor might decide to call this or other state-handler functions to process the same current event. The following code examples should make all this clearer.

The Q_STATE_DEF() Macro

Every state that has been declared with the Q_STATE_DECL() macro in the state machine class needs to be defined with the Q_STATE_DEF() macro. For example, the state "ready" in the Calculator state machines, the Q_STATE_DEF(Calc, ready) macro expands into the following code:

[1] QP::QState Calc::ready(void * const me, QP::QEvt const * const e) {
return static_cast<Calc *>(me)->ready_h(e);
[2] QP::QState Calc::ready_h(QP::QEvt const * const e)
The static Calc::ready() state-caller function is fully defined to call the "state-handler" function on the provided me pointer, which is explicitly cast to the class instance.
The signature of the Calc::ready_h() "state-handler" member function is provided, which needs to be followed by the body ({...}) of the "state-handler" member function.

Top-Most Initial Pseudostate

Every state machine must have exactly one top-most initial pseudo-state, which is assumed when the state machine is instantiated in the constructor of the state machine class. By convention, the initial pseudo-state should be always called initial.

This top-most initial pseudo-state has one transition, which points to the state that will become active after the state machine is initialized (through the QHsm::init() function). The following code the definition of the initial pseudo-state for the Calc class:

[1] Q_STATE_DEF(Calc, initial) {
[2] . . . // initialize the members of the state machine class
[3] (void)e; // unused parameter
[4] return tran(&on);
#define Q_STATE_DEF(subclass_, state_)
Macro to generate a declaration of a state-handler, state-caller and a state-object for a given state...
Definition: qep.hpp:846

[1] The initial pseudo-state is defined by means of the macro Q_STATE_DEF(), which takes two parameters: the class name and the state name (initial in this case).

[2] The function body following the macro Q_STATE_DEF() provides the definition of the "state-handler" member function, so it can access all class members via the implicit this pointer.

[3] The initial pseudo-state receives the "initialization event" e, which is often not used. If the event is not used, this line of code avoids the compiler warning about unused parameter.

[4] The top-most initial transition from the initial pseudo-state is coded with the function tran(). The single parameter to the tran() function is the pointer to the target state of the transition. The top-most initial pseudo-state must return the value from the tran() function.

State-Handler Member Functions

Every regular state (including states nested in other states) is also coded with the Q_STATE_DEF() macro. The function body, following the macro, consists of the switch statement that discriminates based on the event signal (e->sig). The following code shows the complete definition of the Calculator "on" state. The explanation section below the code clarifies the main points.

[1] Q_STATE_DEF(Calc, ready) {
[2] QP::QState status_;
[3] switch (e->sig) {
[4] case Q_ENTRY_SIG: {
[5] BSP_message("ready-ENTRY;");
[6] status_ = Q_RET_HANDLED;
[7] break;
[8] case Q_EXIT_SIG: {
[9] status_ = Q_RET_HANDLED;
[10] case Q_INIT_SIG: {
[11] status_ = tran(&begin);
case DIGIT_0_SIG: {
status_ = tran(&zero1);
[12] case DIGIT_1_9_SIG: {
[13] BSP_insert(Q_EVT_CAST(CalcEvt)->key_code);
[14] status_ = tran(&int1);
case POINT_SIG: {
status_ = tran(&frac1);
case OPER_SIG: {
[15] m_operand1 = BSP_get_value();
[16] m_operator = Q_EVT_CAST(CalcEvt)->key_code;
status_ = tran(&opEntered);
case CE_SIG: {
status_ = tran(&ready);
[17] default: {
[18] status_ = super(&on);
[19] return status_;
QSignal sig
signal of the event instance RQP002
Definition: qep.hpp:168
#define Q_EVT_CAST(subclass_)
Perform downcast of an event onto a subclass of QEvt class_
Definition: qep.hpp:867

[1] The state is defined by means of the macro Q_STATE_DEF(), which takes two parameters: the class name and the state name (on in this case).

[2] The automatic variable status_ will hold the status of what will happen in the state-handler. This status will be eventually returned from the state-handler to the QEP event processor.

[3] Generally, every state handler is structured as a single switch that discriminates based on the signal of the current event e->sig, which is passed to the state-handler as parameter.

[4] The special, reserved event signal Q_ENTRY_SIG is generated by the QEP event processor to let the state-handler process an entry action to the state.

 By convention, all event signals end with the _SIG suffix. The _SIG suffix is omitted in the QM state machine diagrams.

[5] You place your own code, which might contain references to the members of the state machine class (via the implicit this pointer)

[6] After your entry action code, you inform the QEP event processor that the state entry has been handled by setting status_ to Q_RET_HANDLED.

[7] Finally, you close each case with the break statement.

[8] The special, reserved event signal Q_EXIT_SIG is generated by the QEP event processor to let the state-handler process an exit action from the state.

[9] Again, after your exit action code, you inform the QEP event processor that the state exit has been handled by setting status_ to Q_RET_HANDLED.

[10] The special, reserved event signal Q_INIT_SIG is generated by the QEP event processor to let the state-handler process an initial transition nested in the state.

[11] After your initial action code, you inform the QEP event processor to complete the initial transition and to go to the specified target state indicated as the parameter of the tran() function. You set status_ to the value returned from tran().

[12] A user-defined event, like DIGIT_1_9_SIG is handled in its own case statement.

[13] The state-handler code has access to the current event e. The macro Q_EVT_CAST() encapsulates downcasting the event pointer e to the specific event type (CalcEvt in this case).

[14] The DIGIT_1_9_SIG event triggers a state transition to state "int1", which you code with the tran(&int1) function.

[15-16]  The state-handler function has direct access to the data members of the Calc class.

 The previous implementation would require the use of "me->" pointer to access the data members.

[17] The default case handles the situation when this state does not prescribe how to handle the given event. This is where you define the superstate of the given state.

[18] The superstate of the given state is specified by calling the super() function.

 A state that does not explicitly nest in any state, such as the "on" state in the Calculator, calls super(&top)

[19] The state-handler ends by returning the status to the QEP event processor.

The switch statement code and the single return from the state-handler function is compliant with the AUTOSAR-C++:2014 standard.

State-Handler Call Overhead

For embedded system applications, it is always interesting to know the overhead of the implementation used. It turns out that the chosen "state-caller"/"state-handler" implementation is very efficient. The following dis-assembly listing shows the code generated for invocation of a state-handler from the QEP code. The compiler used is IAR C/C++ EWARM 8.32 with Cortex-M target CPU and Medium level of optimization.

r = (*s)(this, e); // invoke state handler s
[1] MOV R1, R7 // place `e` pointer in R1
[2] MOV R0, R6 // place `this` pointer in R0
[3] BLX R4 // branch to the state-caller
[4] B.W MyHsm::state_h() ; branch to state-handler member

The machine code instructions [1-3] are the minimum code to call a function with two parameters via a function pointer (in R4). The single branch instruction [4] represents the only overhead of using the "state-caller" indirection layer. This instruction takes about 4 CPU clock cycles, which is minuscule and typically much better than using a pointer to a C++ member function.

Design (SDS)