State machines refinement - final
Last updated on Thursday, 16 March 2023
In the previous post we improved the maintainability of state machines with some pre-processor tricks. In this post we will add some functionality to the state machine implementation. These additions allow for more freedom in designing your state machines, decrease maintenance effort and help reducing code size even further. The updated state machine implementation will add support for triggers that should be handled regardless of state. We will allow for multiple guards and effects per trigger. We will add choice pseudostates. We will finished by adding support for state entry- and exit functions.
To illustrate the new functionality we will start with a new example application; a super secret server. The server will have two registered users; Alice and Bob. A user can login with a correct user name and corresponding password. All failed logins are logged. A failed login with a registered user name is also reported to that user. To protect our super secret server in case of a calamity there is a kill switch that disables all functionality.
Trigger regardless of state
Sometimes a trigger has the same effect regardless of the state. In these cases you may not want to repeat that trigger for all states. We define a special ANY state in our state machine. When evaluating rules defined in this ANY state, the current state is ignored. All rules are matched in order, so if you always define the rules with ANY last, these rules will only be evaluated if no other rules match.
A common situation is when the trigger has an effect for all states, but does not cause a state change. We can accomodate with a special SAME state. We only need to use this in rules for ANY, but it is best to apply it in other rules as well. This will allow us to quickly see which rules cause a state change and which rules do not.
1static bool evaluateState(statemachine_t *pStatemachine, uint8_t state) {
2 return (state == pStatemachine->currentState)
3 || (state == ANY);
4}
5
6static void updateState(statemachine_t *pStatemachine, uint8_t state) {
7 if (state != SAME) {
8 pStatemachine->currentState = state;
9 }
10}
11
12void statemachine_ApplyTrigger(
13 statemachine_t *pStatemachine,
14 uint8_t trigger ) {
15
16 uint8_t internalState = INVALID;
17
18 for ( size_t i = 0u; i < pStatemachine->nrOfRules; ++i ) {
19 statemachineRule_t rule = pStatemachine->pRules[i];
20 if ( rule.trigger == INVALID ) {
21 internalState = rule.state;
22 continue;
23 }
24
25 if ( evaluateState(pStateMachine, internalState)
26 && (trigger == rule.trigger)
27 && ( (pStatemachine->guardHandler == NULL)
28 || pStatemachine->guardHandler(rule.guard)) ) {
29
30 if ( pStatemachine->effectHandler ) {
31 pStatemachine->effectHandler(rule.effect);
32 }
33 updateState(pStatemachine, rule.state);
34 break;
35 }
36 }
37}
Multiple guards and effects
Sometimes a trigger causes to multiple effects. When we want to login on our super secret server, the server may present us with a prompt to enter a username and a prompt to enter a password. In our current implementation we would have to combine these effects. This has a number of disadvantages. It could lead to inconvenient long names, such as ePromptUserAndPassword. But suppose we also need a ePromptUser effect when the user wants to change its name. Or if a logged-in user wants to perform a highly dangerous function we may need to ask for its password (we already know the user name). We would end up with three separate effects; ePromptUser, ePromptPassword and ePromptUserAndPassword! This is harder to maintain and possibly more wasteful of code size w.r.t. the situation in which we only need two effect; ePromptUser and ePromptPassword.
To keep our statemachine readable, we would like the restrict the line widths. If a trigger needs multiple effects or guards, it makes sense to put these on a new line. With EXTRA we indicate that the line does not define a new trigger or state, but rather adds extra information to the trigger. To implement this we only need a few simple modifications to the implementation of our state machine handler.
The rationale and implementation for extra guards is similar to that of extra effects. We will immediately use it in our case for introducing choice pseudostates.
1static bool evaluateGuards(statemachine_t *pStatemachine, size_t ruleIndex) {
2
3 guardHandler_t guardHandler = pStatemachine->guardHandler;
4 if (guardHandler == NULL) return true;
5
6 size_t i = ruleIndex;
7 do {
8 statemachineRule_t rule = pStatemachine->pRules[i];
9
10 if ( !guardHandler( rule.guard ) )
11 return false;
12
13 ++i;
14
15 } while ( (i < pStatemachine->nrOfRules)
16 && (pStatemachine->pRules[i].trigger == EXTRA));
17
18 return true;
19}
20
21static void executeEffects(statemachine_t *pStatemachine, size_t ruleIndex) {
22
23 effectHandler_t effectHandler = pStatemachine->effectHandler;
24 if (effectHandler == NULL) return;
25
26 size_t i = ruleIndex;
27 do {
28 statemachineRule_t rule = pStatemachine->pRules[i];
29 effectHandler( guardAsEffect ? rule.guard : rule.effect );
30 ++i;
31
32 } while ( (i < pStatemachine->nrOfRules)
33 && (pStatemachine->pRules[i].trigger == EXTRA));
34
35}
36
37void statemachine_ApplyTrigger(
38 statemachine_t *pStatemachine,
39 uint8_t trigger ) {
40
41 size_t internalState = INVALID;
42
43 for ( size_t i = 0u; i < pStatemachine->nrOfRules; ++i ) {
44 statemachineRule_t rule = pStatemachine->pRules[i];
45
46 if ( isStateRule(rule) ) {
47 internalState = rule.state;
48 continue;
49 }
50
51 if ( rule.trigger == EXTRA )
52 continue;
53
54 if ( evaluateState(pStatemachine, internalState)
55 && (trigger == rule.trigger)
56 && (evaluateGuards(pStatemachine, i))) {
57
58 executeEffects(pStatemachine, i);
59
60 updateState(pStatemachine, rule.state);
61
62 break;
63 }
64 }
65}
Choice pseudostate
Sometimes we need to check the result of an effect to decide to which state we should transition. In our super secret server we need to evaluate both the user name and password to decide whether we can log in our user. We can do so with a choice pseudostate. In this intermediate state without an external trigger we have three possible transitions. In case both user name and password are correct, we transition to the sAuthorised state and welcome our user. In case the name exists, but the password is incorrect, we stay in the sUnauthorised state, log the incorrect login attempt and notify the existing user. If the user name does not exist we also stay in the sUnauthorised state, but only log the attempt. Note that choice pseudostates can also have multiple guards and effects! Since pseudochoice states do not have an external trigger, we can again use the trigger field to indicate them. This time with the CHOICE macro.
1static void evaluateChoices(statemachine_t *pStatemachine, size_t ruleIndex) {
2
3 for ( size_t i = ruleIndex + 1; i < pStatemachine->nrOfRules; ++i ) {
4 statemachineRule_t rule = pStatemachine->pRules[i];
5 if (rule.trigger == EXTRA)
6 continue;
7
8 if (rule.trigger == CHOICE) {
9 if ( evaluateGuards(pStatemachine, i) ) {
10 executeEffects(pStatemachine, i);
11
12 updateState(pStatemachine, rule.state);
13 return;
14 }
15 }
16 }
17
18 assert( false );
19}
20
21void statemachine_ApplyTrigger(
22 statemachine_t *pStatemachine,
23 uint8_t trigger ) {
24
25 size_t internalState = INVALID;
26
27 for ( size_t i = 0u; i < pStatemachine->nrOfRules; ++i ) {
28 statemachineRule_t rule = pStatemachine->pRules[i];
29
30 if ( isStateRule(rule) ) {
31 internalState = rule.state;
32 continue;
33 }
34
35 if ( rule.trigger == EXTRA || rule.trigger == CHOICE )
36 continue;
37
38 if ( evaluateState(pStatemachine, internalState)
39 && (trigger == rule.trigger)
40 && (evaluateGuards(pStatemachine, i))) {
41
42 executeEffects(pStatemachine, i);
43
44 if (rule.state == CHOICE) {
45 evaluateChoices(pStatemachine, i);
46 } else {
47 updateState(pStatemachine, rule.state);
48 }
49
50 break;
51 }
52 }
53}
State entry- and exit functions
It sometimes makes more sense to model an effect to occur upon the entry of a state, rather than upon the trigger that caused the state transition. The same holds for the exit of a state. In our super secret server we only have a single transition to the sLocked state. We could easily add an effect to this transition for displaying a message. But the state machine may change over time. The logic for entering the sLocked state may change. Even if there is only one trigger now, it is more robust to display a warning message upon entering the sLocked state. There are two triggers for leaving the sAuthorised state. A user can logout or can hit the kill switch. In both cases we would like to show a brief goodbye message, so it makes sense to implement this as an exit function.
We identify a state entry in our statemachine definition by a trigger property that is set to INVALID. This means we can use the guard and effect properties for specifying a entry and exit effect. We can also use EXTRA rules after the STATE definition to add additional entry and exit functions. Again the guard and effect properties are interpreted as entry and exit functions/effects.
We introduce an extra macro STATE_EX to add a state definition with entry- and exit functions. Instead of the current state, we will store the index of the current state. This makes it more efficient to loop over the optional exit functions. We still have to find the index for the new state in case of a state transition. This comes at a performance cost. But since we now store the index for the current state we can make our ApplyTrigger function more efficient by starting at that index.
updated statemachine:
1#define STATES( FUN ) \
FUN( Unauthenticated ) \
FUN( Authenticated ) \
FUN( Locked )
2
3#define EFFECTS( FUN ) \
FUN( PromptUsername ) \
FUN( PromptPassword ) \
FUN( DisplayWelcome ) \
FUN( DisplayBye ) \
FUN( DisplayWarning ) \
FUN( LogAttempt ) \
FUN( NotifyUser )
4
5#define GUARDS( FUN ) \
FUN( NameExists ) \
FUN( PassCorrect )
6
7#define TRIGGERS( FUN ) \
FUN( Login ) \
FUN( Logout ) \
FUN( Lockdown )
8
9#define STATEMACHINE \
STATE( sUnauthenticated ), \
{ tLogin , NONE , ePromptUsername , CHOICE }, \
{ EXTRA , NONE , ePromptPassword , NONE }, \
\
{ CHOICE , gNameExists , eDisplayWelcome , sAuthenticated }, \
{ EXTRA , gPassCorrect, NONE , NONE }, \
\
{ CHOICE , gNameExists , eNotifyUser , SAME }, \
{ EXTRA , NONE , eLogAttempt , NONE }, \
\
{ CHOICE , ELSE , eLogAttempt , SAME }, \
\
STATE_EX( sAuthenticated, NONE, eDisplayBye ), \
{ tLogout , NONE , NONE , sUnauthenticated }, \
\
STATE_EX( sLocked, eDisplayWarning, NONE ), \
\
STATE( ANY ), \
{ tLockdown , NONE , NONE , sLocked }
10
11#define INITIAL_STATE sUnauthenticated
updated statemachine handler:
1static void updateState(statemachine_t *pStatemachine, size_t ruleIndex) {
2 statemachineRule_t rule = pStatemachine->pRules[ruleIndex];
3 uint8_t currentState = pStatemachine->pRules[pStatemachine->currentStateIndex].state;
4
5 if ( (rule.state == SAME) || (rule.state == currentState) )
6 return;
7
8 // execute exit functions
9 executeEffects(pStatemachine, pStatemachine->currentStateIndex);
10
11 // execute entry functions and update index
12 size_t newIndex = findStateIndex(pStatemachine, rule.state);
13 executeEntryEffects(pStatemachine, newIndex);
14 pStatemachine->currentStateIndex = newIndex;
15}
16
17void statemachine_ApplyTrigger(
18 statemachine_t *pStatemachine,
19 uint8_t trigger ) {
20
21 size_t internalStateIndex = INVALID;
22
23 for ( size_t i = pStatemachine->currentStateIndex; i < pStatemachine->nrOfRules; ++i ) {
24 statemachineRule_t rule = pStatemachine->pRules[i];
25
26 if ( isStateRule(rule) ) {
27 internalStateIndex = i;
28 continue;
29 }
30
31 if ( rule.trigger == EXTRA || rule.trigger == CHOICE )
32 continue;
33
34 if ( evaluateState(pStatemachine, internalStateIndex)
35 && (trigger == rule.trigger)
36 && (evaluateGuards(pStatemachine, i))) {
37
38 executeEffects(pStatemachine, i);
39
40 if (rule.state == CHOICE) {
41 evaluateChoices(pStatemachine, i);
42 } else {
43 updateState(pStatemachine, i);
44 }
45
46 break;
47 }
48 }
49}
The complete sources can be downloaded from statemachine_final.zip