Features

Contents

• Overview
• Events
• States
• Transitions
  • Usage
  • Transitions priority
  • Synchronous transitions
• Parallel
• Substates
  • Usage
  • Multiple entry points
  • Conditional entry points
• History
  • Shallow history
  • Deep history

Overview

hsmcpp allows to use hierarchical state machine (HSM) in your project without worrying about the mechanism itself and instead focus on the structure and logic. I will not cover basics of HSM and instead will focus on how to use the library. You can familiarize yourself with HSM concept and terminology here:

• Introduction to Hierarchical State Machines
• Wikipedia: UML state machine
• Hierarchical Finite State Machine for AI Acting Engine

Since Finite State Machines (FSM) are just a simple case of HSM, those could be defined too using hsmcpp.

Here is an example of a simple HSM which only contains states and transitions:

Events

Events are defined as an enum:

enum class MyEvents
{
    EVENT_1,
    EVENT_2,
    EVENT_3,
    EVENT_4
};

They could be later used when registering transitions.

States

States are defined as an enum:

enum class MyStates
{
    StateA,
    StateB,
    StateC
};

State callbacks are optional and include:

• entering
  • called right before changing a state
  • transition is canceled if callback returns FALSE
• state changed
  • called when HSM already changed its current state
• exiting
  • called for previous state before starting to transition to a new state
  • transition is canceled if callback returns FALSE

Assuming we create HSM as a separate object, here are possible ways to register a state:

HierarchicalStateMachine<MyStates, MyEvents> hsm;
HandlerClass hsmHandler;

hsm.registerState(MyStates::StateA);
hsm.registerState(MyStates::StateA, &hsmHandler, &HandlerClass::on_state_changed_a);
hsm.registerState(MyStates::StateA,
                  &hsmHandler,
                  &HandlerClass::on_state_changed_a,
                  &HandlerClass::on_entering_a);
hsm.registerState(MyStates::StateA,
                  &hsmHandler,
                  &HandlerClass::on_state_changed_a,
                  &HandlerClass::on_entering_a,
                  &HandlerClass::on_exiting_a);
hsm.registerState<HandlerClass>(MyStates::StateA,
                                &hsmHandler,
                                &HandlerClass::on_state_changed_a,
                                nullptr,
                                &HandlerClass::on_exiting_a);

Note that if you explicitly need to pass nullptr (as in the last example) you will need to provide class name as a template parameter.

Transitions

Transition is an entity that allows changing current HSM state to a different one. Its definition includes:

• starting state: state from which transition is possible
• target state: new state which HSM which have if transition is successful
• triggering event: even which triggers transition
• condition (optional): additional logic to restrict transition
• callback (optional): will be called during transition

HSM applies following logic when trying to execute a transition:

It is possible to define multiple transitions between two states. As a general rule, these transitions should be exclusive, but HSM doesn't enforce this. If multiple valid transitions are found for the same event then the first applicable one will be used (based on registration order). But this situation should be treated by developers as a bug in their code since it most probably will result in unpredictable behavior.

Usage

To register transition use registerTransition() API:

hsm.registerTransition(MyStates::StateA,
                       MyStates::StateB,
                       MyEvents::EVENT_1,
                       &hsmHandler,
                       &HandlerClass::on_event_1_transition,
                       &HandlerClass::event_1_condition);
hsm.registerTransition(MyStates::StateA,
                       MyStates::StateB,
                       MyEvents::EVENT_1,
                       [](const VariantList_t& args){ ... },
                       [](const VariantList_t& args){ ... return true; });

Call transition() API to trigger a transition.

hsm.transition(MyEvents::EVENT_1);

By default, transitions are executed asynchronously and it's a recommended way to use them. When multiple events are sent at the same time they will be internally queued and executed sequentially. Potentially it's possible to have multiple events queued when you need to send a new event which will make previous events obsolete (for example user want to cancel operation). In this case you can use transitionWithQueueClear() or transitionEx() to clear pending events:

hsm.transitionWithQueueClear(MyEvents::EVENT_1);
hsm.transitionEx(MyEvents::EVENT_1, true, false);

Keep in mind that current ongoing transition can't be canceled.

Normally if you try to send event which is not handled in current state it will be just ignored by HSM without any notification. But sometimes you might want to know in advance if transition would be possible or not. You can use isTransitionPossible() API for that. It will check if provided event will be accepted by HSM considering:

• current state
• pending events
• conditions assigned to transitions

Note: it is still possible for HSM to reject your event if after isTransitionPossible() some other thread will manage to trigger another transition be careful when using it in multi-threaded environment.

Transitions priority

Ideally, when designing state machine, you should avoid having multiple transitions which could be valid at the same time. This will make understanding the logic and debugging easier. But if for some reason your state machine will contain such transition, hsmcpp library will still handle them in a deterministic and predictable manner:

• all valid transitions will be executed is they are defined on the same level;
• self transitions are always executed before any outgoing transitions;
• if transitions are defined on multiple levels (for example between substates and on the same level as a parent):
  • internal transitions between substates always have the highest priority. Outer transitions will be ignored;

Let's check the following example:

• If StateA is active and EVENT_1 is triggered:
  • first self transition for StateA will be executed;
  • both states B and C will be activated (see Parallel section for details).
• If StateD is active and EVENT_3 is triggered:
  • only StateD->StateE transition will be executed since internal transitions have higher priority.
• If StateE is active and EVENT_3 is triggered:
  • first self transition for ParentState will be executed;
  • then ParentState->StateF transition will be executed.

Synchronous transitions

Transitions can be executed synchronously using transitionEx() API. It was added mostly for testing purposes (since async unit tests are a headache) and is strongly discouraged from usage in production code. But if you really have to then keep these things in mind:

• All callbacks will still be executed on dispatcher's thread. So will have a deadlock if you trigger a synchronous transition from HSM callback.
• when using Glib-based dispatcher you can't call sync transitions from Glib thread assigned to dispatcher (usually main thread). This will also result in deadlock.

Parallel

Up until now our state machines were handling a single state at a time and no more than one state could have been active at any given moment. That's easy to define and handle, but imagine that we are using HSM to define behavior of a system UI and have the following requirements:

• embedded system with two displays;
• each display can display any of the available UI applications (Media, Weather, Navigation);

Since any two of the 3 defined UI applications could be active at any given time we would need to create 3 separate HSMs to handle their logic separately. Sounds a bit inconvenient, but still ok at this point.

But what if eventually our requirements get extended and now we also need to add interaction between these apps? For example, ability to open weather forecast from Navigation. At this point, things will start getting messy since we will have to manually synchronize 2 separate HSM in code.

All of this could be avoided by using the parallel states feature. Essentially it allows HSM to have multiple active states and process their transitions in parallel.

This structure can be achieved by simply defining multiple transitions which will be valid at the same time:

• non-conditional transitions with the same event;
• conditional transitions with the same event (condition must be TRUE for both transitions)

hsm.registerTransition(MyStates::StateA, MyStates::StateB, MyEvents::EVENT_1);
hsm.registerTransition(MyStates::StateA, MyStates::StateC, MyEvents::EVENT_1);

// or

hsm.registerTransition(MyStates::StateA,
                       MyStates::StateB,
                       MyEvents::EVENT_1,
                       &hsmHandler,
                       nullptr,
                       &HandlerClass::event_1_condition);
hsm.registerTransition(MyStates::StateA,
                       MyStates::StateC,
                       MyEvents::EVENT_1,
                       &hsmHandler,
                       nullptr,
                       &HandlerClass::event_1_condition);

When defining HSM in SCXML format you can also use tag. This approach is a bit more restrictive and was added mostly for compatibility with SCXML format specification. Here is an example from Qt Creator:

Note: it's important to understand that all transitions and callbacks are executed on a single thread. If you need actual parallel execution of multiple state machines then you would need to create multiple event dispatchers and handle such machines separately.

Substates

Imagine we have the following state machine:

In this example EVENT_CANCEL must be added for any state except StateA. With increasing complexity of your state machine, this can become a significant issue for maintenance. So such logic could be simplified using substates:

Substates allow grouping of states to create a hierarchy inside your state machine. Any state could have substates added to it on the following conditions:

• any state can have only one parent;
• there is no depth limitations when creating substates, but circle inclusion is not allowed (A->B->C->A);
• parent/composite states can't have callbacks (it's possible to register them, but they will be ignored);
• when state has substates an entry point must be specified;
• multiple entry points can be specified for each composite state.

Entering a substate is considered an atomic operation that can't be interrupted.

Usage

Adding a new substate is done using registerSubstate() API:

hsm.registerSubstate(MyStates::ParentState, MyStates::StateB, true));
hsm.registerSubstate(MyStates::ParentState, MyStates::StateC));

Note that ParentState must be a part of MyStates enum as any other state.

Multiple entry points

If you define multiple entry points without any additional conditions they will automatically become parallel states and will get activated as soon as HSM transitions to their parent state.

Conditional entry points

It's quite common to have multiple ways to enter a parent state. But sometimes you might have a situation when you would want to have a different entry state depending on the triggering transition.

This could be done by specifying multiple entry points with conditions.

When determining which entry point to activate hsmcpp follows these rules:

• if there are no conditional entry points -> activate all entry points;
• if there is one or more conditional entry point -> check if outer transition event matches with entry point transition event;
  • in case of multiple conditional entry points they will be checked in the same order as they were registered;
• if there are multiple conditional entry points with the same matching event all of them will be activated;
• non-conditional entry points will be ignored if there is at least one matching conditional entry point;
• if none of the conditional entry points match outer transition -> non-conditional entry points will be activated.

Here is how above example will treated by HSM:

• when entering Playback state from Idle it will activate only Paused substate;
  • we have conditional transition, but LOAD != RESTART_DONE;
• when entering Playback state from Restart it will activate only Playing substate;
  • since there is a matching conditional entry point transition to Paused will be ignored.

History

A history state is used to remember the previous state of a state machine when it was interrupted. The following diagram illustrates the use of history states. The example is a state machine belonging to a washing machine.

In this state machine, when a washing machine is running, it will progress from "Washing" through "Rinsing" to "Spinning". If there is a power cut, the washing machine will stop running and will go to the "Power Off" state. Then when the power is restored, the Running state is entered at the "History State" symbol meaning that it should resume where it last left-off.

Each history state can have default transitions defined. This transition is used when a composite state had never been active before (therefore it's history being empty).

Two types of history are supported:

• shallow
• deep

Note: it's important to keep in mind, that when restoring history all corresponding callbacks will be called (on enter, on state, on exit).

Shallow history

Shallow history pseudostate represents the most recent active substate of its parent state (but not the substates of that substate). A composite state can have at most one shallow history vertex. A transition coming into the shallow history state is equivalent to a transition coming into the most recent active substate of a state. The entry action of the state represented by the shallow history is performed.

A shallow history is indicated by a small circle containing an "H". It applies to the state that contains it.

Let's look at the example. Let's say we have this state machine with StateE being currently active:

After E1 transition active state will become StateD:

Since we are using shallow history type, HSM will remember Parent2 as a history target for Parent1:

Since Parent2 has substates entry transition will be automatically executed and StateC will become active:

Deep history

Deep history pseudostate represents the most recent active configuration of the composite state that directly contains this pseudostate (e.g., the state configuration that was active when the composite state was last exited). A composite state can have at most one deep history element.

Deep history is indicated by a small circle containing an "H*". It applies to the state that contains it.

Let's look at the example. We have exactly same state machine, but now history type is set to "deep":

While moving to StateD, HSM will save StateE as a history target for Parent1:

So after E2 transition to history state, our HSM will look exactly same as it's initial version: