Hello and welcome to the Modern Embedded Systems Programming course. My name is Miro Samek and in this eighth lesson on state machines I would like to drill deeper into the semantics of hierarchical state machines. Specifically, in this lesson you will examine a hierarchical state machine with multiple levels of state nesting. You will then see how this more advanced state machine handles various transitions and exactly which actions are executed in which order.

To remind you quickly what happened so far, in lesson-40 you designed a relatively simple hierarchical state machine for your TimeBomb application, which you first coded manually and then, in the last lesson-41, you generated the code automatically.

However, that TimeBomb state machine had only one level of state nesting and didn't really demonstrate the richness of semantics enabled by state hierarchy and transitions between states nested at various levels.

So, today to explore what's possible and to learn how exactly a more-advanced hierarchical state machine can handle various transition types, I'd like you to run an example already provided in the QP/C framework.

Specifically, in the last lesson-41 you've seen how to download and install the QP-bundle software, which, among others contains the QM modeling tool, QP frameworks, as well as many other supporting tools, some of which you will have a chance to use today.

So, first I'd like you to go to the qpc/examples/workstation directory, because today you will see an example that runs on your workstation as opposed to an embedded target. I will show you how to adapt this example for your TivaC LaunchPad embedded board in one of the future lessons.

But for today, choose to the qhsmtst example and find the QM model file, which I'd like you to open in the QM modeling tool.

Once the model opens, expand the HSMs package and double-click on the QHsmTst class to show the associated state machine.

Before anything else, let's start with locking the model, which will protect it from any accidental edits.

So this hierarchical state machine is taken from Chapter 2 of my book "Practical UML Statecharts in C/C++, 2nd Edition", which is available in PDF from the state-machine.com website.

The example is obviously contrived in that it does not model any real system, but it has been carefully designed to contain all possible transition topologies up to four levels of state nesting. This includes regular transitions between various levels of state hierarchy as well as internal transitions.

The state machine contains six nested states: "s", "s1", and "s11" on the left and "s2", "s21" and "s211" on the right.

The various transitions are triggered by events named A, B, C, and so on through I. These events correspond to the ordering of transition types from the simplest to progressively more complex in the state machine algorithm used inside the QP framedwork.

Also, all transition as well as states have actions. These actions produce information as to what exactly happened. For instance, entry action to state "s2" produces output "s2-ENTRY", while the exit action produces output "s2-EXIT".

Similarly, the action on state transition A in state s1 produces the output "s1-A", while state transition A in s21 produces the output "s21-A".

By the way, this kind of output with the information about the code execution is more technically called "software tracing", because the output generated by the instrumentation added to the software allows you to trace the code execution. Such information can be very useful for debugging, testing and fine-tuning your code. Software tracing is a very important concept and I will talk about it in the future lessons of this video course.

But going back to your state machine, it also demonstrates guard conditions and for that, it has an attribute "foo", which is used inside the guards and also modified in some transitions.

So, now lets generate the code from this hierarchical state machine, exactly as you did in the last lesson-41.

By now, the generated C code should be familiar to you, because this is the same "optimal" state machine implementation that you've been using since lesson-39.

In principle, you could write such code manually, because in fact it was originally designed for manual coding.

But here I have a personal story, which convinced me to automatic code generation.

So, as I already mentioned, I designed the QHsmTst example for the "Practical UML Statecharts" book. At that time, the QM tool didn't yet exist, so of course I coded it manually and drew the diagram in Visio.

After QM was developed, I wanted to provide all examples from the book as QM models. Interestingly, the QM-generated code from the QHsmTst state diagram produced a *different* trace than my manually written code. My first suspicion was the QM code generator, because the tool was new back then. But to my surprise, the generated code turned out to be right, and the problem was with the diagram.

Specifically the transition G in state "s21" went all the way to state "s11", whereas it should go only to the "s1" superstate. This is indeed what the current QHsmTst model shows.

This was a big lesson for me, and I hope it will inspire you as well. Since then, I just don't leave things to chance anymore and always generate code automatically.

But I digress, because now you need to build the generated code.

For that, open a command-prompt and change the directory to your QHsmTst example.

This directory contains a Makefile, which should work on Windows as well as Linux and MacOS. This Makefile is designed to be easily customizable for your own applications, whereas you typically don't need to change anything beyond that line.

To execute the Makefile you need the make utility. But, if you've installed QP-bundle, as shown in the last lesson-41, make should be directly available in your path.

Also, the Makefile assumes that the GCC GNU C/C++ compiler is directly available on your path as well. Again, if you've installed QP-bundle, you should have the GCC compiler available.

So, now just type "make" to build the code.

This produces the executable in the build directory

To run this executable form your command-prompt, type build-backslash-qhsmtst

This produces some printouts from your software tracing instrumentation inside the state machine actions.

By correlating this tracing information to the state diagram, you will be able to see exactly what the state machine is doing and in which order.

Please try to pay attention to the details here, because they are important to learn and understand the semantics of hierarchical state machines.

So, starting with the top-most initial transition, the first action "top-INIT" is the one attached to the transition itself. Please note that besides producing the output, the action also initializes the member "foo" to zero. This will be important later for evaluation of guard conditions.

Please also note that an initial transition is allowed to cut through more than one level of state nesting, like here it cuts through state "s" and goes directly to state "s2".

However, every state crossed by a transition (initial or regular) must be still properly entered, and therefore the next action executed, is the entry action to state "s", followed by the entry action to state "s2".

Now, the top-most initial transition ends on state "s2", which is called "the explicit target of the transition", but the trace does not stop there.

This is because the semantics prescribes that any transition, including initial transition, needs to "drill" into the sub-states as long as there are initial transitions nested directly in the target state.

And indeed, there is an initial transition nested directly in "s2", so it is taken.

Next, "s21" is entered and "s211" is also entered. 

"s211" is called a "leaf" state, because it has no further substates or nested initial transitions. Therefore the run-to-completion step completes here and the hierarchical state machine said to have reached a "stable state configuration".

The last entered state becomes the current state.

At this point you can start dispatching events to your state machine. You do this by typing on your keyboard. For example, letter G dispatches the corresponding event G to the state machine.

Per the semantics of hierarchical sate machines, the event G is handled in the following way:

First, the current state ("s211") attempts to handle the event. However, state "s211" does not have any transition labeled with G, so the event is passed on to the next higher-level state in the hierarchy, which is state "s21". "s21" has a transition triggered by G, so it executes the action associated with the transition and produces the printout "s21-G;".

Next the state machine executes the transition chain that exits the source state configuration and enters the target state configuration. The transition chain starts with exit actions from all states up the state hierarchy to the so called Least Common Ancestor (LCA), but not exiting the LCA itself.

The LCA of "s21"-"s1" pair of states is their common superstate "s", so all states up to "s", but without "s" itself are exited.

Next the target state configuration is entered in the exact opposite order, that is, starting from highest levels of state hierarchy down to the lowest.

The transition G from state "s21" terminates at state "s1". However, "s1" has a nested initial transition, so it is executed and "s11" is entered. This is a leaf state, so the RTC step completes.

Next, let's dispatch event I. Again, the current state "s11" does not have any transitions labeled I, so the event is passed on to the next level of state hierarchy, that is, to state "s1". "s1" has an *internal* transition triggered by I, therefore "s1" handles the event and produces the printout "s1-I;".

And at this point the processing ends. No change of state ever occurs in the internal transition, even if such transition is inherited from higher levels of state hierarchy. The current state remains the state "s11".

Next, let's dispatch event A. As before, the current state "s11" does not prescribe how to handle A, so the event is passed on to the superstate "s1". "s1" has a *self* transition triggered by A and so it executes actions associated with that transition producing the printout "s1-A;". This time, however, A is a regular transition, which requires exiting the source state configuration and entering the target state configuration. 

The LCA of a state pair "s1" - "s1" is "s", so all states from the current state up to "s", but excluding "s" are exited.

Next, state "s1" is cleanly re-entered by executing the entry action to "s1", initial transition in "s1, and entering the "s11" leaf state.

At this point I'd like to make two observations: The first is that in hierarchical state machines self-transitions, like "s1-A" here, are different from internal transitions, like "s1-I" here.

This is not necessarily the case in the classical, non-hierarchical state machines without entry and exit actions to states, where self-transitions are used exactly to cause a reaction in a given state.

And the second observation is that in hierarchical state machines, a self-transition is an idiom to cleanly *reset* a given state context, by cleanly exiting and re-entering the state again. Such self-transitions can be useful for various "Cancel" operations, like the "Cancel" button in a calculator.

Now, let's show the current state, which is still "s11" and dispatch event D.

"s11" has a transition D, but this transition has a guard [me->foo]. "foo" is an attribute of the state machine, which was initialized to 0 in the top-most initial transition.

Therefore the guard condition [me->foo] evaluates to FALSE. According to the UML semantics, this is treated as though transition D  was absent in "s11" and therefore, the event D is passed on to the next higher level, that is, to state "s1".

State "s1" also has transition D, but with the complementary guard [NOT me->foo]. This time, the guard evaluates to TRUE and the transition is taken, producing the "s1-D" trace. Please note that the action on that transition also changes the value of the attribute foo to 1.

After this, all the appropriate exit actions up to the LCA, which is state "s" are taken, followed by entry actions back to "s11". The current state becomes again "s11". 

Now, when you dispatch another event D, the guard [me->foo] in transition s11-D evaluates to TRUE and so this transition is taken. This time the LCA is only "s1", so fewer exit and entry actions are executed.

Event C dispatched to the state machine demonstrates again that all exit and entry actions are always executed, regardless of which transitions are in between. For example, the nested initial transition in that explicit target state "s2" goes to substate "s211", cutting through the substate "s21". However, still the entry actions don't skip the entry to "s21".

Before entering the "s211" leaf state.

This example demonstrates once again the powerful concept of guaranteed cleanup of the source state configuration through the exit actions and guaranteed initialization of the target state configuration through the entry actions, regardless of the complexity of the exit or entry path.


Interestingly, in hierarchical state machines, the exact same transition can cause different sequences of exit actions, depending on which state inherits the transition.

For example, let's now dispatch event E twice in a row.

Each time, the event triggers the same transition "s-E", but the actions executed are different, because transition E fires from different state configurations: once when the current state is "s211", and next when the current state is "s11".


Finally, guard conditions can also be used on internal transitions.

For example, let's now dispatch event G to change the current state to "s211"

and after this, two events I in a row.

The first I triggers transition "s2-I", because the guard [NOT-me->foo] is TRUE. Please note that the action on this transition also sets foo to 1.

The next event I does not trigger "s2-I", because this time the guard [NOT-me->foo] evaluates to FALSE, and so the event is passed up to the superstate "s". 

The internal transition "s-I" has a complementary guard, which is TRUE, so the transtion "s-I" is taken.

Of course, in case of internal transitions there is no change of state, so no exit or entry actions are ever executed.

Now, let's terminate the QHsmTst executable by pressing the Escape key, but you can learn much more by running this example yourself, dispatching various events to it, and studying software trace it produces.

Now, if you wish to play with the example and modify it, you can certainly unlock the model and change things directly in the QPC folder.

But perhaps a better idea is to make a local copy of the example and make any changes there.

So, let's just do that as a coding exercise for today.

In the file explorer, copy the qhsmtst example directory and paste it into your projects for this video course. Next, rename the qhsmtst directory to lesson-42.

Get inside the lesson-42 directory and double-click on the model file to open it in QM.

Now, copy the full path to the new directory

and in your command-prompt change directory there.

The directory contains the copied Makefile that you already used at the original location, so let's try it again, by typing make.

The build fails, because the qpc-dot-h header file cannot be found.

When you open the Makefile, you can see that this is because the location of the QP/C framework has been defined as a relative path. This was appropriate for the original QP/C examples, because it allows you to install QP/C anywhere in your file system and still have all the Makefiles work.

But it doesn't work anymore in a folder that is outside the QP/C directory tree.

You have a few options to fix the issue.

First, you can define the QPC environment variable, which the Makefile will then take instead of using the relative path.

You can do it permanently, from Settings|System|About tab and "Advanced Systems Settings" link.

Here you click the Environment Variables button, where finally you can add your new QPC variable.

Alternatively, you can set the QPC variable locally at the command-prompt

For the sake of this exercise, let's do it locally.

Now, the build succeeds and you can run the build\qhsmtxt executable as before.

But let's unset the variable and try the other option, which is to change the QPC variable inside the Makefile. The Makefile will then work without you remembering to set QPC the next time.


Alright, so now let's get back to your local qhsmtst model and take a look at a few issues that came up during the explanation of the hierarchical state machine semantics.

First, I'd like to explore a little deeper guard conditions and specifically, the propagation of events to the higher-level states when a guard evaluates to FALSE.

For example, this happens when you get to state "s11" and dispatch event D. The guard condition on transition s11-D evaluates to FALSE and the event is propagated to the higher-level state "s1".

This might be what you want, but sometimes you might exactly NOT want to propagate the event, even when the guard evaluates to FALSE.

You can model this by attaching a special, explicit complementary guard [else], like this.

Now, you need to re-generate the code

and re-build the program.

When you run it again, get to state "s11" as before, and dispatch event D.

As you can see, this time D produces no output, because the event is ignored due to the guard, but the event is no longer propagated up to state "s1". 

By the way, the special [else] guard and more tips for working with Choice Segments are described in the QM online manual.

Another aspect of the QHsmTst state machine that you can change is how it exits. Specifically, as you can see in the software trace, the execution stops abruptly without any cleanup, that is, without executing the appropriate exit actions from states.

This happens, because the TERMINATE event dispatched when you press the Escape key, is an internal transition that, as you've learned today, never triggers exit or entry.

To execute the exit actions you need to turn TERMINATE into a regular transition, that is, it needs to go to a state, which you can call "final".

Now, you can move the BSP_exit() action from the TERMINATE transition to the entry action to "final". This will exit the application, but only after the whole chain of exit actions from the "s" superstate has been executed.

As usual, you need to re-generate the code and rebuild the executable.

When you run it and press Escape, you can see that now it performs cleanup.

Interestingly, when you run it again, but change state before pressing Escape, the cleanup is different, because it is specific to the current state when the application is terminated. 


This concludes this lesson about the semantics of hierarchical state machines. I hope you have now a better idea how HSMs work and you gained some appreciation for the richness of the semantics that state hierarchy offers.

Of course, you might still have questions as to how exactly certain transition types will be handled. But here, the QHsmTst example can help, because it has been specifically designed to contain all possible state transition configurations up to four levels of state nesting. This allows you to quote-unquote "answer" all your questions by running the example and dispatching the events to trigger the specific transitions.



If you like this channel, please give this video a like and subscribe to stay tuned. You can also visit state-machine.com/video-course for the class notes and project file downloads.

Finally, all the projects are also available on GitHub in the Quantum Leaps repository "modern embedded programming course". Tanks for watching!