Listing 4.1 shows the directories and files comprising the QEP event processor in C. The structure of the C++ version is identical, except that the implementation files have the .cpp extension.

The QEP source files contain typically just one function or a data structure definition per file. This design aims at deploying QEP as a fine-granularity library that you statically link with your applications. Fine granularity means that the QEP library consists of several small, loosely coupled modules (object files) rather than a single module that contains all functionality. For example, a separate module qhsm_in.c implements the QHsm_isIn() function; therefore, if your application never calls this function, the linker will not pull in the qhsm_in module. This strategy puts the burden on the linker to do the heavy lifting of eliminating any unused code automatically at link time, rather than on the application programmer to configure the QEP code for each application at compile time.

A signal in UML is the specification of an asynchronous stimulus that triggers reactions [OMG 07] and as such is an essential part of an event. The signal conveys the type of the occurrence—what happened. Signals are typically enumerated constants. The following fragment of QEvent.h header file defines the type of the signal QSignal to be either 8 bits (uint8_t), 16 bits (uint16_t), or 32 bits wide (uint32_t), depending on the configuration macro Q_SIGNAL_SIZE. If you don't define this macro, a default of 8 bits is assumed.

Listing 4.2 shows the definition of the QEvent structure in C. The member sig of type QSignal represents the signal. The byte-wide member dynamic_ is used by the QP framework to manage dynamically allocated events. You should never need to access this member from the application-level code. (I'll explain dynamic event allocation in Chapter 7.)

The QEvent structure can be used as is for events without parameters or can serve as the base structure for derivation of events with arbitrary parameters. The following C code snippet shows how to derive the calculator event CalcEvt that contains the key-code parameter (also see the sidebar “Single Inheritance in C” in Chapter 1):

Having the common base structure QEvent for all events ensures that every event object contains the signal at the same offset within the event. This allows using a pointer to a derived event as a parameter to any function that expects a generic QEvent *e pointer to the base structure. Any such function can always access the sig data member (as e->sig) to determine what kind of derived event structure is used. The function can then perform an explicit downcast⁴ Casting from the subclass to the superclass is called in OOP downcasting because the cast goes down a traditionally drawn inheritance relationship in a class diagram, such as Figure 4.1. to the derived event structure to get the event parameters. For example, to get the key_code parameter, a generic QEvent *e pointer needs to be cast to CalcEvt as follows: ((CalcEvt *)e)->key_code.

The point here is that the sig data member has double responsibility. It obviously must convey the occurrence (what happened?). But in addition, the signal must also uniquely identify the derived event structure so that state-handler functions can explicitly downcast to this derived structure based only on the sig value. This second responsibility will became clearer in the upcoming Section 4.4.2, where I provide examples of state handler functions.

In C++, the QEvent structure can be defined without the ugly typedef, as shown in Listing 4.3. Please note that in C++ struct is exactly equivalent to class, except in struct the default protection level is public and in class it is private.

Event instances are used primarily as “bags” for passing around signals and event parameters. To generate events efficiently, it's often convenient to use statically preallocated, constant event objects initialized with an initializer list. To allow such initialization in C++, a class must be an aggregate; that is, it must not have private or protected members, constructors, base classes, and virtual functions [Stroustrup 00]. For that reason, QEvent is declared as struct in Listing 4.3, without any private members or constructors. (An obvious constructor would take one argument to initialize the sig attribute.)

The following C++ code snippet shows how to derive the calculator event CalcEvt class that contains the key-code parameter:

When you derive from QEvent, the subclass is obviously no longer an aggregate. However, I recommend that you still keep your event classes simple and lightweight. I like to define the QEvent subclasses using the struct keyword as a reminder that they are lightweight. In particular, I avoid private members, constructors, or virtual functions in the derived event classes. As you will see in Chapter 7, events generally do not go through conventional instantiation (the standard operator new isn't used to create dynamic events), so the constructors aren't invoked and the virtual pointers aren't set up.

When a hierarchical state handler function does not handle the current event, it returns the macro Q_SUPER() to the event processor, which is defined as follows:

The Q_SUPER() macro is defined using the comma expression. A comma expression is evaluated from left to right, whereas the type and value of the whole expression is the rightmost operand. The rightmost operand is in this case the status of the operation (superstate), which is returned from the state-handler function. The pivotal aspect of this design is that the Q_SUPER() macro can be used with respect to structures derived (inheriting) from QHsm, which in C requires explicit casting (upcasting) to the QHsm base structure (see the sidebar “Single Inheritance in C” in Chapter 1).

Listing 4.4 shows an example of a hierarchical state-handler function that corresponds to the state “int1” in the calculator statechart in Figure 2.18State “int1” controls entering the integer part of the first operand.

In C, HSMs are derived from the QHsm base structure, shown in Listing 4.6.

In C++, HSMs are derived from the QHsm abstract base class, shown in Listing 4.7.

Every HSM has the (typically implicit) top state, which surrounds all the other elements of the entire state machine, as depicted in Figure 4.2.

Figure 4.2. The top state and the initial pseudostate.

The QHsm class guarantees that the top state is available to every derived state machine by providing the QHsm_top() hierarchical state handler subsequently inherited by the subclasses. The QHsm_top() hierarchical state-handler function is defined as follows:

By the UML semantics, the top state has no superstates and silently ignores all events, so it always returns Q_IGNORED() to the event processor (see Listing 3.6(15) in Chapter 3). The only purpose, and legitimate use, of the top state is to provide the ultimate root of a state hierarchy so that the highest-level state handlers can return &QHsm_top as their superstate. In particular, you should never target the top state in a state transition.

The state machine initialization is intentionally divided into two steps. The QHsm constructor merely initializes the state variable to the initial pseudostate. Later, the application code must trigger the initial transition explicitly by invoking QHsm_init() (described in the upcoming Section 4.5.6). This design separates instantiation of the state machine from initialization, giving the applications full control over the sequence of initializations in the system. The following code shows an example of an initial pseudostate handler for the calculator state machine:

Note that the topmost initial transition can fire only once (actually, exactly once), because after you leave the top state, you cannot transition back. In other words, your state machine cannot reuse the initial pseudostate in its life cycle.

In Chapter 2, you saw that UML state machines support elements of Moore automata such as entry and exit actions as well as nested initial transitions. These elements are sole characteristics of the state in which they are defined and do not depend, in particular, on the transition path through which the state has been reached. As described in Chapter 3, state-handler functions in QEP can (optionally) define state-specific behavior by responding to the following reserved signals defined in the qep.h header file:

A state handler can handle these signals by using them as case labels in the usual switch statement. A state handler is free to execute any actions in response to those signals, but it should not take any state transitions in entry/exit actions. Conversely, the response to the Q_INIT_SIG signal must always include the Q_TRAN() macro to designate the default substate of the current state.

Listing 4.8 provides an example of using an entry action, an exit action, and a nested initial transition.

The reserved signals take up the lowest signal values (0..3), which are thus not available for the applications. For convenience, the public HSM interface contains the signal Q_USER_SIG, which indicates the first signal free for the users. A typical way of defining application-level signals is to use an enumeration. In this case, Q_USER_SIG can be used to offset the values of the entire enumeration, as shown in Listing 4.9.

To execute entry/exit actions and initial transitions, the QEP event processor needs to invoke the various state-handler functions and pass to them pointers to event objects containing the reserved signals. For example, to trigger an entry action in the Calc_on() state handler, the event processor calls the Calc_on() function with a pointer to an event that has the signal equal to Q_ENTRY_SIG. To do this efficiently, QEP uses the QEP_reservedEvt_[] constant array of reserved events, defined as follows:

The array QEP_reservedEvt_[] is designed to be indexed by the reserved signals. For example, &QEP_reservedEvt_[Q_ENTRY_SIG] represents a pointer to an event with the reserved signal Q_ENTRY_SIG.

The following three helper macros are then used extensively inside the QEP implementation (file <qp>qpcqepsourceqep_pkg.h):

For example, the macro QEP_TRIG_() calls a given state-handler function state_ with the reserved event pointer argument &QEP_reservedEvt_[sig_], where sig_ is one of these: QEP_EMPTY_SIG_, Q_ENTRY_SIG, Q_EXIT_SIG, or Q_INIT_SIG. Note the characteristic syntax of the function call based on a pointer to function (*(state_))(…).

State nesting adds a lot of complexity to the topmost initial transition in an HSM compared to a nonhierarchical FSM. The initial transition in an HSM might be complex because UML semantics require “drilling” into the state hierarchy with the nested initial transitions until the leaf state is reached. For example, the topmost initial transition in the calculator example (Figure 2.18 in Chapter 2) involves the following six steps:

Figure 4.3 shows the inheritance tree of the states comprising the calculator statechart. The UML specification requires that higher-level states must be entered before entering lower-level states. Unfortunately, this is exactly the opposite order to the natural direction of navigation through the state handlers denoted by the behavioral inheritance arrow in Figure 4.3. As you recall from Section 4.4, a hierarchical state-handler function provides the superstate, so it's easy to traverse the state hierarchy from lower- to higher-level states. Although this order is very convenient for the efficient implementation of the most frequently used QHsm_dispatch() function, entering states is harder.

Figure 4.3. The inheritance tree of the calculator HSM with the nested initial transitions.

The solution implemented in QEP is to use a temporary array path[] to record the exit path from the target state of the initial transition without executing any actions (see Figure 4.4). This is achieved by calling the state handlers with the reserved QEP_EMPTY_SIG_ signal, which causes every state handler to immediately return the superstate without executing any actions. The returned superstates are saved in the path[] array. After reaching the current state, the path[] array is played backward to enter the target state in the exact reversed order in which it was exited.

Figure 4.4. The use of the path[] array to enter the target state configuration in the correct order.

Listing 4.10 shows the definition of the QHsm_init() function that executes a generic topmost initial transition according to the UML semantics. The equivalent C++ implementation of the QHsm::init() member function is identical, except for trivial syntactic differences between C and C++.

Dispatching an event to an HSM requires implementing the UML state nesting semantics, that is, propagating the event through all the levels of nesting until it is handled or reaches the top state. This functionality as well as executing of transitions is implemented in the QHsm_dispatch() function.

The QHsm_dispatch() function is the most complicated in the QEP event processor.⁶ QHsm_dispatch() is not broken up in to smaller functions to conserve the stack space. I will break up the discussion of the implementation into two steps. First, in this section I explain how the function handles hierarchical event processing. In the next section, I take a closer look at the transition execution algorithm.

Listing 4.11 shows the general structure of the QHsm_dispatch() function. The implementation uses many elements already described for QHsm_init(). The code carefully optimizes the number and size of temporary stack variables to minimize the stack use. The equivalent C++ implementation of the QHsm::dispatch() member function is identical, except for trivial syntactic differences between C and C++.

For example, assume that the state “result” is the current active state of the calculator state machine in Figure 4.5 while the user presses one of the operator keys (+, –, *, or /). When the function QHsm_dispatch() receives the OPER event, it calls the currently active state handler first, which is the Calc_result() state handler. This state handler doesn't handle the OPER event, so it returns the superstate Calc_ready(). The QHsm_dispatch() function then calls the Calc_ready() state handler, which handles the OPER event by taking a state transition Q_TRAN(&Calc_opEntered). However, the correct exit of the current state configuration must include exiting “result” before exiting “ready.” This transition segment is shown in grey in Figure 4.5.

Figure 4.5. Two segments of an inherited state transition.

Executing a generic state transition in a HSM is by far the most complex part of the QEP implementation. The challenge is to quickly find the least common ancestor (LCA) state of the source and target states. (The LCA is the lowest-hierarchy state that is simultaneously the superstate of the source and the target states.) The transition sequence involves the exit of all states up to the LCA (but without exiting the LCA itself), followed by the recursive entry into the target state, followed by “drilling” into the target state configuration with the initial transitions until a leaf state is reached.

Listing 4.12 shows the omitted part of the QHsm_dispatch() function that implements the general case of a state transition. A large part of the complexity of this part of the code results from the optimization of the workload required to efficiently execute the most frequently used types of state transitions. The optimization criterion used in the transition algorithm is to minimize the number of invocations of state-handler functions, in particular the “empty” invocations (with the reserved QEP_EMPTY_SIG_), which serve only for eliciting the superstate of a given state handler. The strategy is to order the possible source-target state combinations in such a way that the information about the state hierarchy gained from earlier steps can be used in later states. Figure 4.6 shows such ordering of state transition topologies. This ordering is the basis for the transition algorithm in Listing 4.12.

Figure 4.6. Ordering of transition types from simplest to progressively more complex in the transition algorithm (Listing 4.12).

The transition types shown in Figure 4.6(A) through Figure 4.6(H) represent all valid transition topologies, and every well-formed transition should be recognized as one of the cases (A) through (H). Once QHsm_dispatch() detects the type of the transition and executes all necessary exit actions up to the LCA, it must enter the target state configuration.

The first step of the implementation consists of enumerating all signals recognized by the state machine shown in the state diagram (Figure 2.18 in Chapter 2), such as C, CE, DIGIT_0, DIGIT_1_9, and so on.

Listing 4.9 shows the enumeration of all signals recognized by the calculator state machine. Note that the user-level signals do not start from zero but rather are offset by the constant Q_USER_SIG. Also note that by QEP convention, all signals have the suffix_SIG to easily distinguish signals from other constants. The suffix _SIG is omitted in the state diagram to reduce the clutter.

Many events consist only of the signal and don't need any additional parameters. You can represent such events directly as instances of the QEvent structure provided in the header file <qp>qpcincludeqevent.h.

However, some events require parameters. For example, the calculator signal DIGIT_1_9_SIG communicates only that one of the digit keys 1..9 has been depressed, but the signal alone does not inform us as to which digit key this was. The missing information is added to the event in the form of the key_code parameter that represents the code of the depressed key.

The following fragment of the calc.h header file demonstrates how you add event parameters. You define a class (CalcEvt) that inherits from the QEvent class. You then add arbitrary parameters as data members:

Hierarchical state machines are represented in QEP as subclasses of the QHsm abstract base class, which is defined in the header file <qp>qpcppincludeqep.h. Listing 4.13 demonstrates how you derive the Calc (calculator) class from QHsm.

The initial pseudostate Calc::initial() shown here takes the “me” pointer to its own class (Calc *) as the first argument and an event pointer as the second parameter. This particular initial pseudostate ignores the event, but sometimes such an initialization event can be helpful to provide additional information required to initialize extended-state variables of the state machine.

The initial pseudostate can initialize the extended state variables and perform any other actions, but its most important job is to set the default state of the state machine with the Q_TRAN() macro, as shown.

Earlier in this chapter, in Listing 4.5 you saw an example of the Calc::int1() state handler function. Typically, every state handler function consists of a switch statement that discriminates based on the event signal e->sig. Each case is labeled by a signal and terminates either with “return Q_HANDLED()” or “return Q_TRAN(…).” Either one of these return statements informs the QEP event processor that the particular event has been handled. On the other hand, if no case executes, the state handler exits through the final “return Q_SUPER(…)” statement, which informs the QEP event processor that the event needs to be handled by the designated superstate.

Highest-level states without explicit superstate (e.g., the “on” state in the calculator example) nest implicitly in the top state. Such states disignate &QHsm::top as the argument to the Q_SUPER() macro.

While coding state-handler functions, you need to keep in mind that QEP will invoke them 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 events enlisted in the case statements. You should also avoid any code outside the switch statement, especially code that would have side effects.

The qep.h header file provides two reserved signals Q_ENTRY_SIG and Q_EXIT_SIG that the QEP event processor passes to the appropriate state-handler function to execute the state entry actions or exit actions, respectively.

Therefore, as shown in Listing 4.8 earlier in this chapter, to code an entry action, you provide a case statement labeled with signal Q_ENTRY_SIG, enlist all the actions you want to execute upon the entry to the state, and terminate the lists with “return Q_HANDLED(),” which informs the QEP that the entry actions have been handled.

Coding the exit actions is identical, except that you provide a case statement labeled with the signal Q_EXIT_SIG, call the actions you want to execute upon the exit from the state, and terminate the lists with “return Q_HANDLED(),” which informs the QEP that the exit action has been handled.

Every composite state (a state with substates) can have its own initial transition, which in the diagram is represented as an arrow originating from a black ball. For example, the calculator state “on” in Figure 2.18 has such a transition to substate “ready.”

The QEP provides a reserved signal Q_INIT_SIG that the event processor passes to the appropriate state-handler function to execute the initial transition.

Therefore, as shown Listing 4.8 earlier in this chapter, to code an initial transition, you provide a case statement labeled with signal Q_INIT_SIG, enlist all the actions you want to execute upon the initial transition, and then designate the target substate with the Q_TRAN() macro. The status returned from the Q_TRAN() macro informs QEP that the initial transition has been handled.

The UML specification requires that the target of the initial transition is a direct or indirect substate of the source state. An initial transition to a nonsubstate (e.g., a peer state, or a superstate) corresponds to a malformed state machine and may even crash the event processor. Note that initial transitions cannot have guard conditions.

Internal transitions are simple reactions to events that never lead to change of state and consequently never cause execution of exit actions, entry actions, or initial transitions.

To code an internal transition, you provide a case statement labeled with the triggering signal, enlist the actions, and terminate the list with “return Q_HANDLED()” to inform QEP that the event has been handled.

State-handler Calc::int1() from Listing 4.5 provides two examples of regular state transitions. To code a regular transition, you provide a case statement labeled with the triggering signal (e.g., POINT_SIG), enlist the actions, and then designate the target state with the Q_TRAN() macro. The status returned from the Q_TRAN() macro informs QEP that a transition has been taken.

The Q_TRAN() macro can accept any target state at any level of nesting, such as a peer state, a substate, a superstate, or even the same state as the source of the transition (transition to self).

Guard conditions (or simply guards) are Boolean expressions evaluated dynamically based on the value of event parameters and/or the variables associated with the state machine (extended-state variables). The following definition of the Cacl::begin() state-handler function shows an example of a state transition with a guard.

The guard condition maps simply to an if-statement that conditionally executes actions. Note that only the TRUE branch of the if contains the “return Q_TRAN()” statement, meaning that only the TRUE branch reports that the event has been handled. If the TRUE branch is not taken, the break statement causes a jump to the final return that informs the QEP that the event has not been handled. This is in compliance with the UML semantics, which require treating an event as unhandled in case the guard evaluates to FALSE. In that case, the event should be propagated up to the higher levels of hierarchy (to the superstate).

Guard conditions are allowed not just for regular state transitions but for the internal transitions as well. In this case a guard maps to the if statement that contains “return Q_HANDLED()” only in the TRUE branch. The only difference for the internal transition is that you return the Q_HANDLED() macro instead of Q_TRAN().

You should construct only complete state handlers, that is, state-handler functions that directly include all state machine elements pertaining to a given state (such as all actions, all transitions, and all guards), so that you or anyone else could at any time unambiguously draw the state in a diagram using only the state-handler function.

The key is the way you break up the code. Instead of thinking in terms of individual C statements, you should think at a higher level of abstraction, in terms of the idioms defined in Sections 4.6.5-4.6.10 for coding states, transitions, entry/exit actions, initial transitions, and guards.

Consider the following problematic implementation of the “on” state handler of the calculator state machine shown before, in Section 4.5.4:

This Calc_on() state-handler function differs from the original implementation discussed in Section 4.5.4 only in the way it handles the C_SIG signal. Though the problematic implementation is in principle equivalent to the original and would perform exactly the same way, the problematic state handler is incomplete because it does not follow the idiom for coding state transition from Section 4.6.9. In particular, the state handler hides the state transition to self triggered by C_SIG and from such an incomplete state handler alone you would not be able to correctly draw the state in the diagram.

In summary, perhaps the most important principle to keep in mind while coding state machines with QEP is that the code is as much an implementation as it is a specification of a state machine. This perspective on coding state machines with QEP will help you (and others) readily see the state machine structure right from the code and easily and unambiguously map the code back to state diagrams. Conversely, state machine code structured arbitrarily, even if working correctly, might be misleading and therefore difficult to maintain (see also [Samek 03f]).

All nontrivial, semantically rich formalisms, including UML state machines, allow building ill-formed constructs. An ill-formed state machine is inherently wrong, not one that just happens to incorrectly represent behavior. For example, you could draw a UML state diagram with initial transitions targeting peer states rather than substates or conflicting transitions with overlapping guards. The specific state machine implementation technique, such as QEP, introduces additional opportunities of “shooting yourself in the foot.” It is possible, for example, to code a state handler that would nest inside itself (the state-handler function would return a pointer to self). Such a state machine cannot be even drawn in a state diagram but is quite easy to code with QEP.

This section examines more of such situations that result with ill-formed state machines. Often, ill-formed state machines cause an assertion violation within the QEP code (see the sidebar “Design by Contract in C and C++”). However, some pathological cases, such as circular state nesting, could crash the QEP event processor.

Novice QEP users sometimes try to code a transition inside the entry action to a state by using the Q_TRAN() macro. This happens typically when a developer confuses a statechart with a flowchart (see Section 2.2.3) and thinks of the entered state as just a stage of processing that automatically progresses to the next stage upon completion of the entry actions.

The UML does not allow transitions in entry or exit actions. The typical intention in coding a state transition in an entry action is to enter a given state only under some condition and transition to a different state under some other condition. The correct way of handling this situation is to explicitly code two transitions with complementary guards and with different target states.

As described in Section 4.3, event parameters are added to the QEvent structure in the process of class inheritance. However, events are uniformly passed to state-handler functions as the generic QEvent* pointer, even though they point to various derived event classes. That's why you need to downcast the generic QEvent* pointer onto the pointer to the specific event subclass as shown, for instance, in Listing 4.4(5).

However, to perform the downcast correctly, you need to know what derived event to cast to. The only information you have at this point is the signal of the event (e->sig), and therefore the signal alone must unambiguously identify the derived event structure. The problem arises if you use one signal with multiple event classes, because then you could cast incorrectly on the wrong event class.

A specific case of incorrect event casting is an attempt to access event parameters when handling entry/exit actions or initial transitions. For example, if a state has only one incoming transition that is triggered with an event with parameters, novice QEP users sometimes try to access these parameters in the entry action to this state. Consider the following hypothetical code example:

The transition in “stateA” triggered by EVTB_SIG is the only way to get to “stateB.” In the entry action to “stateB” the programmer realizes that some parameter foo in the EvtB structure, associated with signal EVTB_SIG, is needed and casts the generic event on (EvtB const *). This is an incorrect cast, however, because by the time “stateB” is entered the original triggering event EvtB is no longer accessible. Instead, the entry action is triggered by a reserved signal Q_ENTRY_SIG, which is not associated with the EvtB event structure. This is actually logical because a state can be entered in many different transitions, each one triggered by a different event, and none of them are accessible by the time entry action is processed.

The correct way of handling this situation is to perform actions dependent on the event parameters directly on the transition triggered by this event rather than in the entry action. Alternatively, the event parameters can be stored in the extended-state variables (members of the state machine structure that you access through the “me” pointer). The extended-state variables are accessible all the time, so they can be used also in the entry/exit actions or initial transitions.

All initial transitions must target direct or indirect substates of the state in which the initial transition is defined. Figure 4.8(A) shows several examples of correct initial transitions. Note that an initial transition can span more than one level of state hierarchy, but it must always target a direct or indirect substate of a given state. Figure 4.8(B) shows one example of the highlighted initial transition in “stateA1” that targets “stateA21.” The problem is that “stateA21” is not a substate of “stateA1” and therefore the state machine in Figure 4.8(B) is ill-formed according to the UML semantics. Coding such an initial transition in QEP will crash the event processor.

Figure 4.8. Correct (A) and incorrect (B) initial transitions.

As the QEP user, you need to understand that each event that dispatched the state machine through the function QHsm_dispatch() might potentially cause invocation of many state-handler functions and some of them might be called more than once. This is because the event processor needs to call state-handler functions to perform hierarchical event processing, to handle entry/exit actions and initial transitions, or simply to discover the nesting level of a given state. Therefore, you should not assume that a state-handler function would be called exactly once for a given event, so you should avoid any code outside the main switch statement dedicated to events, especially if the code has side effects.

For example, the following state-handler function is certainly inefficient, and probably incorrect, because the for loop executes every time the state handler is invoked, which is not just for the events enlisted as cases in the switch statement.

You should even avoid allocating and initializing any automatic variables outside the main switch statement. I specifically recommend using braces after each case statement so that you can allocate and initialize automatic variables locally in each individual case statement. The following code snippet illustrates the situation:

Nothing affects state machine complexity and efficiency as much as the right granularity and semantics of events. The optimal granularity of signals falls somewhere between the two extremes of too fine and too coarse.

The granularity of signals is too fine if you repeatedly find the same groups of signals handled in the same way. For example, recall the calculator example (Section 2.4 in Chapter 2). The calculator HSM handles all numerals 1 through 9 in the same way. Therefore, introducing a separate signal for each numeral would lead to a signal granularity that is too fine, which would unnecessarily bloat the state-handler functions (you would see long lists of cases handled identically). Instead, the calculator statechart represents the whole group of numerals 1 through 9 as just one signal, IDC_1_9_SIG (see Figure 2.18).

The granularity of signals is too coarse if you find yourself frequently using guard conditions that test event parameters. In this case, event parameters are the de facto signals. Consider the Windows message WM_COMMAND, frequently used in Windows GUI applications for all buttons and menus of the application. This signal is too coarse because Windows applications typically must test the wParam parameter associated with the WM_COMMAND to determine what actually happened. In other words, values of wParam are the de facto signals. In this case, the too coarse signal granularity results in a suboptimal (and not very elegant) additional switch statement based on wParam nested within the WM_COMMAND case. When you encounter signals that are too coarse, the first thing you should try is to redefine or remap signals to the right level of granularity before dispatching them to the state machine. However, if you cannot do this, you should include all the de facto signals directly in your state handlers. All too often, the additional layer of signal dispatching (such as the switch based on wParam) end up in a separate function, which makes state handlers incomplete in the sense discussed in Section 4.7.1.

All state machine formalisms, including UML statecharts, universally assume run-to-completion (RTC) semantics of processing events. RTC means that a state machine must always complete processing of the previous event before it can start processing the next. The RTC restriction comes from the fact that a state machine must always go from one stable state configuration all the way to another stable state configuration in one indivisible step (RTC step). A state machine cannot accept events before reaching a stable state configuration.

The RTC semantics is implicit in the QEP implementation because each invocation of the function QHsm_dispatch() represents one RTC step. In single-threaded systems, such as all the examples discussed in this chapter, the RTC semantics cannot be violated because each function must return before it can be called again. However, in multitasking environments, even as simple as the superloop (main+ISRs), the RTC semantics can be easily violated by attempts to dispatch an event to a state machine from an ISR while the same state machine in the background loop is still busy processing the previous event.

A very nasty and difficult-to-debug violation of the RTC semantics is an inadvertent corruption of the current event before the RTC step completes. Recall that the state-handler functions in QEP take just pointers to events, not the copies of the entire event objects. It is therefore possible that the memory pointed to by the event pointer will get corrupted before the current RTC step completes.

For example, consider once more the superloop (main+ISRs) architecture. An ISR produces an event and sets a global flag to trigger a state machine running in the background. The background loop starts processing the event, but before it completes, another interrupt preempts it. The ISR produces another event by overwriting the memory used previously for the first event. The RTC semantics are violated even though the ISR merely sets a flag instead of calling the state machine directly.

The general solution to guarantee RTC semantics in multitasking systems is to use event queues to store events while a state machine is busy. The mechanisms for a thread-safe event queuing and dispatching to multiple concurrently executing state machines can be generalized and reused rather than being reinvented from scratch for each application. Virtually all GUI systems (such as Microsoft Windows, X Windows, and others) are examples of such reusable architectures. QEP can be used with virtually any such event-driven infrastructure. In particular, QEP can be combined with the QF event-driven framework design specifically for the domain of real-time embedded systems. I introduce the QF component in Chapter 6.