Backmp11 back-end (C++17, experimental)

Backmp11 is a new back-end that is mostly backwards-compatible with back. It is currently in experimental stage, thus some details about the compatibility might change (feedback welcome!). It is named after the metaprogramming library Boost Mp11, the main contributor to the optimizations. Usages of MPL are replaced with Mp11 to get rid of the costly C++03 emulation of variadic templates.

It offers a significant improvement in runtime and memory usage, as can be seen in these benchmarks:

Large state machine

	Compile time / sec	Compile RAM / MB	Binary size / kB	Runtime / sec
back	10	844	73	0.7
back_favor_compile_time	12	821	241	1.0
back11	26	2675	92	0.7
backmp11	2	237	21	0.4
backmp11_favor_compile_time	2	225	45	2.2
sml	3	242	57	0.1

Large hierarchical state machine

	Compile time / sec	Compile RAM / MB	Binary size / kB	Runtime / sec
back	32	2160	252	3.7
back_favor_compile_time	37	1747	974	263
backmp11	5	362	52	1.8
backmp11_favor_compile_time	3	263	98	7.6
backmp11_favor_compile_time_multi_cu	3	~934	99	8.6
sml	12	567	436	2.5

The full code with the benchmarks and more information about them is available in this repository. The tables in the repository are frequently updated with results from the latest development branches of the benchmarked libraries.

Creation

The state_machine signature in backmp11 looks as follows (pseudo-code):

template <
    typename FrontEnd,
    typename Config = default_state_machine_config,
    typename Derived = state_machine
>
class state_machine;

Only the FrontEnd parameter is mandatory, using my_fsm = msm::backmp11::state_machine<my_front_end>; is the minimal declaration to create a state machine.

Configuration

A state machine’s configuration can be adjusted by passing a custom Config parameter. The default configuration is:

// Default config:
struct default_state_machine_config
{
    // A common context that is shared by all SMs
    // in hierarchical state machines.
    using context = no_context;
    // Tune characteristics related to compile time, runtime performance,
    // code size, and available features.
    using compile_policy = favor_runtime_speed;
    // Which container to use for the event pool.
    template <typename T>
    using event_pool_container = std::deque<T>;
    // Type of the Fsm parameter passed in actions and guards.
    using fsm_parameter = local_transition_owner;
    // Identifier for the upper-most SM
    // in hierarchical state machines.
    using root_sm = no_root_sm;
};

using state_machine_config = default_state_machine_config;

Inherit from state_machine_config and override the using directives to create a custom configuration.

// Custom config:
struct CustomStateMachineConfig : state_machine_config
{
    using context = Context;
    using root_sm = RootSm;
    using fsm_parameter = root_sm;
};

The state machine configuration is designed to be shared in hierarchical state machines.

Context

The setting context sets up a context member in the state machine for dependency injection.

If using context = CustomContext; is defined in the config, a reference to it has to be passed to the state machine constructor as first argument. The following API becomes available to access it in the state machine:

// Context access:
Context& state_machine::get_context();
const Context& state_machine::get_context() const;

Root state machine

The setting root_sm defines the type of the root state machine of hierarchical state machines. The root sm depicts the uppermost state machine.

If using root_sm = RootSm; is defined in the config, the following API becomes available to access it from any submachine:

// Root state machine access:
RootSm& state_machine::get_root_sm();
const RootSm& state_machine::get_root_sm() const;

It is highly recommended to always configure the root_sm in hierarchical state machines, even if access to it is not required. This reduces the compilation time, because it enables the back-end to instantiate the full set of construction-related methods only for the root and it can omit them for submachines.

`Fsm` parameter of actions und guards

The setting fsm_parameter defines the instance of the Fsm& fsm parameter that is passed to actions and guards in hierarchical state machines.

By default it is set to local_transition_owner, which behaves identically to back:

Actions and guards for transitions in the same transition table receive the SM instance that owns the transition (the one processing the event)
Entry and exit actions receive the "local" transition owner from the perspective of the state being entered/exited (the immediate parent SM)

You can alternatively set it to using fsm_parameter = root_sm, in which case the configured root_sm is passed as Fsm parameter.

In UML, the "transition owner" is the region or state machine that contains the transition. The term "local transition owner" extends this UML terminology, because the Fsm parameter in entry and exit actions is not necessarily the state machine containing the transition. It refers to the immediate parent state machine of the state being entered/exited, which is the transition owner from the local perspective of that state.

Example: Consider a hierarchical state machine with nested state machines:

SM1 (root)
  └─ SM2
      └─ SM3
          └─ State S0 (active)

When a transition defined in SM1 causes SM2 and SM3 to exit:

S0’s exit action receives SM3 as Fsm (S0’s immediate parent)
SM3’s exit action receives SM2 as Fsm (SM3’s immediate parent)
SM2’s exit action receives SM1 as Fsm (SM2’s immediate parent)

Event pool

The state machine utilizes an event pool for events that are not processed immediately. The default event pool container is a std::deque<T>. You can use a custom event pool container. It has to support push at both ends as well as removal at begin without iterator invalidation, in detail these API calls:

push_back(const T&)
push_front(const T&)
begin()
end()
erase(iterator)
clear()

You can deactivate the event pool with using event_pool_container = no_event_pool_container<T>;. A state machine requires the event pool to handle completion events, deferred events, and enqueued events.

Compile policy

`favor_runtime_speed`

The default compile policy prioritizes runtime speed, it evaluates all transitions and generates the dispatch table at compile time. The dispatch strategy can be tuned by inheriting from favor_runtime_speed and adapting the using dispatch_strategy directive:

struct favor_runtime_speed
{
    // Dispatch strategy for processing events.
    // Supported strategies:
    // - flat_fold (default)
    // - function_pointer_array
    using dispatch_strategy = dispatch_strategy::flat_fold;
};

It currently supports two dispatch strategies:

Strategy Description

Strategy	Description
`flat_fold` (default)	Generates a flat fold of inline comparison branches. All transition logic is visible to the optimizer. Usually results in optimal runtime performance and executable size.
`function_pointer_array`	Generates an array of function pointers. Guarantees O(1) dispatch, but the function pointers cannot be inlined. Usually results in worse runtime performance and larger executable size, but slightly better compile time.

flat_fold (default)

Generates a flat fold of inline comparison branches.
All transition logic is visible to the optimizer.
Usually results in optimal runtime performance and executable size.

function_pointer_array

Generates an array of function pointers.
Guarantees O(1) dispatch, but the function pointers cannot be inlined.
Usually results in worse runtime performance and larger executable size, but slightly better compile time.

`favor_compile_time`

This policy improves compile time at the cost of runtime speed. It evaluates transitions lazily and generates the dispatch table at runtime. Like its counterpart in back, it does not support Kleene events.

Events are wrapped into a std::any when they enter event processing to reduce the number of necessary template instances required to generate the state machine. A hash map contains the dispatch table, with the type index of each event as the key and an array of function pointers to the matching transitions as the value.

With this policy you can compile a state machine across multiple translation units (TUs) with the help of a preprocessor macro. Since the back-end should compile very fast for most state machines, this is an opt-in feature:

define BOOST_MSM_BACKMP11_MANUAL_GENERATION before including msm/backmp11/favor_compile_time.hpp
then generate your state machine back-end(s) with the macro BOOST_MSM_BACKMP11_GENERATE_STATE_MACHINE(<sm_type>)

You can find an example for this in the visitor test.

Extension

You can extend a state machine by inheriting from the state_machine template instead of a using directive. If the extended class is required to be available in Fsm parameter, pass it as third parameter to the state_machine template.

History

In backmp11 the history policy is defined in the front-end instead of the back-end. Defining it there ensures that one state machine config can be shared between multiple back-ends of hierarchical state machines.

// No history (default).
struct no_history {};

// Shallow history.
// For deep history use this policy for all the contained state machines.
template <typename... Events>
struct shallow_history {};

// Shallow history for all events (not UML conform).
// For deep history use this policy for all the contained state machines.
struct always_shallow_history {};

...

// User-defined state machine.
struct Playing_ : public msm::front::state_machine_def<Playing_>
{
    using history = msm::front::shallow_history<end_pause>;
    ...
};

Start and stop

A newly constructed state machine is inactive and does not process events as long as it is not yet started. The void start() method activates the state machine by first calling the state machine front-end’s entry action and then the initial state’s. By default the event passed to the entry actions is an empty struct backmp11::starting. You can pass a custom event with the overload void start(const auto& initial_event).

The void stop() method deactivates the state machine by first calling the active state’s exit action and then the state machine front-end’s. The default event is an empty struct backmp11::stopping, and a similar overload void stop(const auto& final_event) exists to customize it.

Calling start() on an active or stop() on an inactive state machine has no effect.

Handling events

Use process_result process_event(const Event&) to start processing an event while the state machine is idle.

You can enqueue an event for consecutive processing in an action with void enqueue_event(const Event&). The event will be processed immediately after the current event is done processing.

The back-end supports event deferral with the front-end’s deferred_events state property. Deferred events are evaluated in the same order they have been deferred, ensuring FIFO processing semantics. They are stored in the event pool of the state machine that was requested to process the event. In hierarchical state machines this is usually the root state machine, in which case all submachines are able to receive the event upon dispatch. Event deferral in orthogonal regions behaves as described in the UML standard: As long as one active region decides to defer an event, it remains deferred for all regions.

Conditional deferral is a backmp11-exclusive extension of the deferred_events property in states. Deferral can be made conditional by defining a bool is_event_deferred(…) method in the state:

struct MyState : boost::msm::front::state<>
{
    using deferred_events = mp11::mp_list<MyEvent>;

    template <typename Fsm>
    bool is_event_deferred(const MyEvent& event, Fsm& fsm) const
    {
        // Return true or false to decide
        // whether the event shall be deferred.
        ...
    }
};

You can also defer events in transitions by using the front::Defer action. While this mechanism offers additional flexibility for event deferral, it has a couple of limitations:

It uses the event pool of the state machine passed by the Fsm parameter - if this is not the root machine in hierarchical state machines, state machines further up the hierarchy cannot receive the event.
Action-deferred events get dispatched for evaluation and then put back into the event pool. This requires additional runtime and prevents deferred events from being processed in FIFO order.
In orthogonal regions each region evaluates the event independently, but the regions share the event pool of the containing state machine. This leads to the same event being dispatched multiple times.

Check for active states

Use the method bool is_state_active() to query for active states:

template <typename State>
bool state_machine::is_state_active() const;

If the type of the state appears multiple times in a hierarchical state machine, the method returns true if any of the states are active.

Visit states

You can visit all currently active states with a visitor API. In hierarchical state machines submachines are visited recursively.

template <typename Visitor>
void state_machine::visit(Visitor&& visitor);

The visitor functor must support to be called with all existing state types of the state machine.

template <typename State>
void operator()(State& state);

A state machine can be visited in multiple modes:

only the active states or all states
non-recursive or recursive

The visit function can be customized with a visit_mode template parameter.

// API:
enum class visit_mode
{
    // State selection (mutually exclusive).
    active_states = 0b001,
    all_states    = 0b010,

    // Traversal mode (not set = non-recursive).
    recursive     = 0b100,

    // All valid combinations.
    active_non_recursive = active_states,
    active_recursive     = active_states | recursive,
    all_non_recursive    = all_states,
    all_recursive        = all_states | recursive
};
template <visit_mode Mode, typename Visitor>
void state_machine::visit(Visitor&& visitor);

// Use the pre-defined constants...
state_machine.visit
    <visit_mode::all_recursive>
    ([](auto &state) {/*...*/});
// ... or assemble a mode
state_machine.visit
    <visit_mode::all_states | visit_mode::recursive>
    ([](auto &state) {/*...*/});

Reflection and serialization

The state_machine provides access to all its members recursively with a reflect free function and a visitor pattern:

// namespace boost::msm::backmp11

// Reflect on a state_machine's members with a visitor.
// The visitor has to implement the methods:
// - visit_front_end(auto&& front_end)
// - visit_front_end(auto&& front_end, auto&& reflect)
// - visit_member(const char* key, auto&& member)
// - visit_state(size_t state_id, auto&& state)
// - visit_state(size_t state_id, auto&& state, auto&& reflect)
template <typename FrontEnd, typename Config, typename Derived,
          typename Visitor>
void reflect(detail::state_machine_base<FrontEnd, Config, Derived>& sm,
             Visitor&& visitor);

Do not rely on assumptions about call orders and argument details of the visit methods. The reflection API exposes internal members of the state machine, which are subject to changes.

The visit methods of the front-end and states contain two overloads. The first one gets called in case the object to be visited does not have reflection, the second one provides a reflect functor argument that triggers the reflection deeper into the object. You can set up reflection for a front-end or state by implementing a reflect member function or alternatively a free function (with MSVC you have to use a member function due to ADL limitations).

struct MyState : boost::msm::front::state<>
{
    // Reflect with a member function.
    template <typename Visitor>
    void reflect(Visitor&& visitor)
    {
        visitor.visit_member("my_member", my_member);
    }
    template <typename Visitor>
    void reflect(Visitor&& visitor) const
    {
        visitor.visit_member("my_member", my_member);
    }

    uint32_t my_member{};
};

// Or reflect with a free function.
template <typename Visitor>
void reflect(MyState& my_state, Visitor&& visitor)
{
    visitor.visit_member("my_member", my_state.my_member);
}
template <typename Visitor>
void reflect(const MyState& my_state, Visitor&& visitor)
{
    visitor.visit_member("my_member", my_state.my_member);
}

You can use the reflection API for introspection use cases, the most prominent one being serialization of a state machine. backmp11 supports 3 serialization libraries out-of-the-box:

Boost.Serialization
Boost.JSON
nlohmann/json

For each serialization library you can find a corresponding header with serializer code under boost/msm/backmp11/serialization. The serializer expects all objects with non-static members to be serializable, which can be achieved by implementing either reflection or library-specific serialization methods. It is recommended to implement `backmp11’s reflection API, because this mechanism is generic and supports all serialization libraries.

For serialization with Boost.JSON and nlohmann/json you only need to include the corresponding header, for Boost.Serialization you additionally need to provide a serialize method for the (root) state machine. The backmp11 serialization test demonstrates how to use the serialization libraries.

Comparison to `back`

The backmp11 back-end should be mostly compatible with existing code utilizing the back back-end:

for the state machine use boost::msm::backmp11::state_machine in place of boost::msm::back::state_machine
for configuring the compile policy and more use a boost::msm::backmp11::state_machine_config struct
adapt public API calls that have been changed in backmp11 or write an adapter by extending the state_machine class

The next paragraphs offer further details about the differences between backmp11 and back.

Public API of `state_machine`

The following adapter pseudo-code showcases the differences to the state_machine API of back.

class state_machine_adapter
{
    using Flag_AND = backmp11::flag_and;

    template <typename Event>
    back::HandledEnum process_event(const Event& event)
    {
        if (this->get_machine_state() == detail::machine_state::processing)
        {
            this->enqueue_event(event);
            return back::HANDLED_DEFERRED;
        }
        else
        {
            return Base::process_event(event);
        }
    }

    // The new API returns a const std::array<...>&.
    const uint16_t* current_state() const
    {
        return &this->get_active_state_ids()[0];
    }

    auto& get_message_queue()
    {
        return this->get_event_pool().events;
    }

    size_t get_message_queue_size() const
    {
        return this->get_event_pool().events.size();
    }

    void execute_queued_events()
    {
        this->process_event_pool();
    }

    void execute_single_queued_event()
    {
        this->process_event_pool(1);
    }

    auto& get_deferred_queue()
    {
        return this->get_event_pool().events;
    }

    void clear_deferred_queue()
    {
        this->get_event_pool().events.clear();
    }

    template <class Archive>
    void serialize(Archive& ar,
                   const unsigned int /*version*/)
    {
        backmp11::reflect(*this, serializer<Archive>{ar});
    }

    // No adapter.
    // Superseded by the visitor API.
    // void visit_current_states(...) {...}

    // No adapter.
    // States can be set with `get_state<...>() = ...` or the visitor API.
    // void set_states(...) {...}

    // No adapter.
    // Could be implemented with the visitor API.
    // auto get_state_by_id(int id) {...}
};

A working code example of such an adapter is available in the tests. It can be copied and adapted if needed, though this class is internal to the tests and not planned to be supported officially.

Kleene events

To reduce the amount of necessary header inclusions, backmp11 uses std::any for defining Kleene events instead of boost::any. You can opt in to support boost::any by including boost/msm/event_traits.h.

Removed features

Initialization of states in the constructor and the `set_states(…)` method

There were some caveats with one constructor that was used for different use cases: On the one hand some arguments were immediately forwarded to the front-end’s constructor, on the other hand the stream operator was used to identify other arguments in the constructor as states, to copy them into the state machine. Besides the syntax of the later being rather unusual, when doing both at once the syntax becomes too difficult to understand; even more so if states within hierarchical submachines are initialized in this fashion.

In order to keep the API of the constructor simpler and less ambiguous, it only supports forwarding arguments to the front-end. Also the set_states(…) API is removed. If setting a state is required, this can still be done (in a more verbose, but also more direct & explicit way) by getting a reference to the desired state via get_state<State>() and then assigning a new state object to it.

The `get_state_by_id(…)` method

If you really need to get a state by id, you can use the visitor API to implement the function on your own. The state_machine has a method to support getting the id of a state in the visitor:

template <typename State>
static constexpr uint16_t state_machine::get_state_id(const State&);

The pointer overload of `get_state<…>()`

Similarly to the STL’s std::get<…>(…) method for a tuple, the only sensible template parameter for get_state<T>() is T returning a T&. The overload for a T* is removed and the T& is discouraged, although still supported. If you need to get a state by its address, use the address operator after you have received the state by reference.

The eUML front-end support

The support for EUML induces longer compilation times by the need to include the Boost proto headers and applying C++03 variadic template emulation. If you want to use a UML-like syntax, please try out the new PUML front-end.

The fsm check and find region support

The implementation of these two features depends on mpl_graph, which induces high compilation times.

`sm_ptr` support

Not needed with the functor front-end and was already deprecated, thus removed in backmp11.

Deprecation information

Deprecations of features, APIs, and other changes with additional context are listed in the table below.

Feature Deprecation / Removal Description

Feature	Deprecation / Removal	Description
Public access to the event container	1.90 / 1.91	The event container can be accessed and manipulated via public APIs. Manipulation of the container outside of the library code can lead to undefined behavior. Change: The public API to access the event container will be changed to `protected`. If needed, users can inherit from `state_machine` to access the event container, but without guarantees about correct functionality and API consistency.
Renaming of `transition_owner` to `local_transition_owner`	1.91 / 1.92	The default setting of the `Fsm` parameter was named `transition_owner`, which was intended to reflect the same behavior as in `back`. However, `transition_owner` does have a different behavior from `back`. Furthermore, it was not implemented correctly. Change: The behavior will be corrected to match `back` and the default setting will be renamed to `local_transition_owner` in 1.91. The previous setting name `transition_owner` will be deprecated in 1.91 and removed in 1.92.
Removal of APIs to process queued events	1.91 / 1.92	The event containers for queued events and deferred events have been merged into a single event pool. The APIs for processing queued events are obsolete. Change: The APIs `process_queued_events`, and `process_single_queued_event` will be removed. Occurrences of the old APIs can be replaced as follows: to process a single event in the event pool, use `process_event_pool(1)` to process all events in the event pool, use `process_event_pool()`
Removal of automatic enqueuing in the `process_event` API	1.91 / 1.92	The API `process_event` automatically enqueues events when the state machine is already processing. This requires instantiating `enqueue_event` for every event type, even though most instances are never called. They are only needed when `process_event` is called in actions. Change: The API `process_event` will reject an event and return `HANDLED_FALSE` when called during event processing instead of automatically enqueueing it. Calls to `process_event` in actions have to be replaced with `enqueue_event`.

Public access to the event container

1.90 / 1.91

The event container can be accessed and manipulated via public APIs. Manipulation of the container outside of the library code can lead to undefined behavior.

Change: The public API to access the event container will be changed to protected. If needed, users can inherit from state_machine to access the event container, but without guarantees about correct functionality and API consistency.

Renaming of transition_owner to local_transition_owner

1.91 / 1.92

The default setting of the Fsm parameter was named transition_owner, which was intended to reflect the same behavior as in back. However, transition_owner does have a different behavior from back. Furthermore, it was not implemented correctly.

Change: The behavior will be corrected to match back and the default setting will be renamed to local_transition_owner in 1.91. The previous setting name transition_owner will be deprecated in 1.91 and removed in 1.92.

Removal of APIs to process queued events

1.91 / 1.92

The event containers for queued events and deferred events have been merged into a single event pool. The APIs for processing queued events are obsolete.

Change: The APIs process_queued_events, and process_single_queued_event will be removed.

Occurrences of the old APIs can be replaced as follows:

to process a single event in the event pool, use process_event_pool(1)
to process all events in the event pool, use process_event_pool()

Removal of automatic enqueuing in the process_event API

1.91 / 1.92

The API process_event automatically enqueues events when the state machine is already processing. This requires instantiating enqueue_event for every event type, even though most instances are never called. They are only needed when process_event is called in actions.

Change: The API process_event will reject an event and return HANDLED_FALSE when called during event processing instead of automatically enqueueing it.

Calls to process_event in actions have to be replaced with enqueue_event.

Edit this Page

Backmp11 back-end (C++17, experimental)

Creation

Configuration

Context

Root state machine

Fsm parameter of actions und guards

Event pool

Compile policy

favor_runtime_speed

favor_compile_time

Extension

History

Start and stop

Handling events

Check for active states

Visit states

Reflection and serialization

Comparison to back

Public API of state_machine

Kleene events

Removed features

Initialization of states in the constructor and the set_states(…​) method

The get_state_by_id(…​) method

The pointer overload of get_state<…​>()

The eUML front-end support

The fsm check and find region support

sm_ptr support

Deprecation information

`Fsm` parameter of actions und guards

`favor_runtime_speed`

`favor_compile_time`

Comparison to `back`

Public API of `state_machine`

Initialization of states in the constructor and the `set_states(…)` method

The `get_state_by_id(…)` method

The pointer overload of `get_state<…>()`

`sm_ptr` support