[[back-end]]

= Back-end

The back-end contains the library engine and defines the performance and functionality trade-offs. There are, at the moment, three back-ends:

- `msm::back` is using {cpp}03
- `msm::back11` is using {cpp}11 and should be used by default if possible as it removes some pre-{cpp}11 limitations (mpl::vector of limited size)
- `msm::backmp11` is using {cpp}17 (it is still experimental at the moment and further described in a xref:./backmp11-back-end.adoc[separate page])

The currently available back-ends implement most of the functionality
defined by the UML 2.0 standard at very high runtime speed, in exchange
for longer compile-time. The runtime speed is due to a constant-time
double-dispatch and self-adapting capabilities allowing the framework to
adapt itself to the features used by a given concrete state machine. All
unneeded features either disable themselves or can be manually disabled.
See section 5.1 for a complete description of the run-to-completion
algorithm.

[[creation]]

== Creation

MSM being divided between front and back-end, one needs to first define
a front-end. Then, to create a real state machine, the back-end must be
declared:

....
typedef msm::back11::state_machine<my_front_end> my_fsm;
....

We now have a fully functional state machine type. The next sections
will describe what can be done with it.

[[backend-start]]

== Starting and stopping a state machine

The `start()` method starts the state machine, meaning it will activate
the initial state, which means in turn that the initial state's entry
behavior will be called. We need the start method because you do not
always want the entry behavior of the initial state to be called
immediately but only when your state machine is ready to process events.
A good example of this is when you use a state machine to write an
algorithm and each loop back to the initial state is an algorithm call.
Each call to start will make the algorithm run once. The
xref:attachment$iPodSearch.cpp[iPodSearch] example uses this possibility.

The `stop()` method works the same way. It will cause the exit actions
of the currently active state(s) to be called.

Both methods are actually not an absolute need. Not calling them will
simply cause your first entry or your last exit action not to be called.

[[event-dispatching]]

== Event dispatching

The main reason to exist for a state machine is to dispatch events. For
MSM, events are objects of a given event type. The object itself can
contain data, but the event type is what decides of the transition to be
taken. For MSM, if some_event is a given type (a simple struct for
example) and e1 and e2 concrete instances of some_event, e1 and e2 are
equivalent, from a transition perspective. Of course, e1 and e2 can have
different values and you can use them inside actions. Events are
dispatched as const reference, so actions cannot modify events for
obvious side-effect reasons. To dispatch an event of type some_event,
you can simply create one on the fly or instantiate if before
processing:

....
my_fsm fsm; fsm.process_event(some_event());
some_event e1; fsm.process_event(e1)
....

Creating an event on the fly will be optimized by the compiler so the
performance will not degrade.

[[active-states]]

== Active state(s)

The backend also offers a way to know which state is active, though you
will normally only need this for debugging purposes. If what you need
simply is doing something with the active state, `internal transitions`
or `visitors` are a better alternative. If you need to know what state
is active, const int* current_state() will return an array of state ids.
Please refer to the `internals section` to know how state ids are
generated.

[[upper-state-machine]]

== Upper State Machine (`msm::back11` only)

The FSM template argument passed to functors or entry/exit actions is
the current state machine, which might not be what is wanted as the
upper state machine makes more sense. The back-end provides a
get_upper() function returning a pointer to the upper state machine,
which is usually what you want to call process_event on.

[[back-end-serialization]]

== Serialization

A common need is the ability to save a state machine and restore it at a
different time. MSM supports this feature for the basic and functor
front-ends, and in a more limited manner for eUML. MSM supports
boost::serialization out of the box (by offering a `serialize`
function). Actually, for basic serialization, you need not do much, a
MSM state machine is serializable almost like any other type. Without
any special work, you can make a state machine remember its state, for
example:

....
MyFsm fsm;
// write to archive
std::ofstream ofs("fsm.txt");
// save fsm to archive
{
    boost::archive::text_oarchive oa(ofs);
    // write class instance to archive
    oa << fsm;
}                                                  
....

Loading back is very similar:

....
MyFsm fsm;
{
    // create and open an archive for input
    std::ifstream ifs("fsm.txt");
    boost::archive::text_iarchive ia(ifs);
    // read class state from archive
    ia >> fsm;
}                                          
....

This will (de)serialize the state machine itself but not the concrete
states' data. This can be done on a per-state basis to reduce the amount
of typing necessary. To allow serialization of a concrete state, provide
a do_serialize typedef and implement the serialize function:

....
struct Empty : public msm::front::state<> 
{
    // we want Empty to be serialized. First provide the typedef
    typedef int do_serialize;
    // then implement serialize
    template<class Archive>
    void serialize(Archive & ar, const unsigned int /* version */)
    {
        ar & some_dummy_data;
    }
    Empty():some_dummy_data(0){}           
    int some_dummy_data;
};                        
....

You can also serialize data contained in the front-end class. Again, you
need to provide the typedef and implement serialize:

....
struct player_ : public msm::front::state_machine_def<player_>
{
    //we might want to serialize some data contained by the front-end
    int front_end_data;
    player_():front_end_data(0){}
    // to achieve this, provide the typedef
    typedef int do_serialize;
    // and implement serialize
    template<class Archive>
    void serialize(Archive & ar, const unsigned int )
    {
        ar & front_end_data;
    }  
...
};                                               
....

The saving of the back-end data (the current state(s)) is valid for all
front-ends, so a front-end written using eUML can be serialized.
However, to serialize a concrete state, the macros like
`BOOST_MSM_EUML_STATE` cannot be used, so the state will have to be
implemented by directly inheriting from `front::euml::euml_state`.

The only limitation is that the event queues cannot be serialized so
serializing must be done in a stable state, when no event is being
processed. You can serialize during event processing only if using no
queue (deferred or event queue).

This xref:attachment$Serialize.cpp[example] shows a state machine which we
serialize after processing an event. The `Empty` state also has some
data to serialize.

[[backend-base-state]]

== Base state type

Sometimes, one needs to customize states to avoid repetition and provide
a common functionality, for example in the form of a virtual method. You
might also want to make your states polymorphic so that you can call
typeid on them for logging or debugging. It is also useful if you need a
visitor, like the next section will show. You will notice that all
front-ends offer the possibility of adding a base type. Note that all
states and state machines must have the same base state, so this could
reduce reuse. For example, using the basic front end, you need to:

* Add the non-default base state in your msm::front::state<> definition,
as first template argument (except for interrupt_states for which it is
the second argument, the first one being the event ending the
interrupt), for example, my_base_state being your new base state for all
states in a given state machine:
+
....
struct Empty : public msm::front::state<my_base_state>
....
+
Now, my_base_state is your new base state. If it has a virtual function,
your states become polymorphic. MSM also provides a default polymorphic
base type, `msm::front::polymorphic_state`
* Add the user-defined base state in the state machine frontend
definition, as a second template argument, for example:
+
....
struct player_ : public msm::front::state_machine<player_,my_base_state>             
....

You can also ask for a state with a given id (which you might have
gotten from current_state()) using
`const base_state* get_state_by_id(int id) const` where base_state is
the one you just defined. You can now do something polymorphically.

[[backend-visitor]]

== Visitor

In some cases, having a pointer-to-base of the currently active states
is not enough. You might want to call non-virtually a method of the
currently active states. It will not be said that MSM forces the virtual
keyword down your throat!

To achieve this goal, MSM provides its own variation of a visitor
pattern using the previously described user-defined state technique. If
you add to your user-defined base state an `accept_sig` typedef giving
the return value (unused for the moment) and parameters and provide an
accept method with this signature, calling visit_current_states will
cause accept to be called on the currently active states. Typically, you
will also want to provide an empty default accept in your base state in
order not to force all your states to implement accept. For example your
base state could be:

....
struct my_visitable_state
{
   // signature of the accept function
   typedef args<void> accept_sig;
   // we also want polymorphic states
   virtual ~my_visitable_state() {}
   // default implementation for states who do not need to be visited
   void accept() const {}
};
....

This makes your states polymorphic and visitable. In this case, accept
is made const and takes no argument. It could also be:

....
struct SomeVisitor {…};
struct my_visitable_state
{
    // signature of the accept function
    typedef args<void,SomeVisitor&> accept_sig;
    // we also want polymorphic states
    virtual ~my_visitable_state() {}
    // default implementation for states who do not need to be visited
    void accept(SomeVisitor&) const {}
};
....

And now, `accept` will take one argument (it could also be non-const).
By default, `accept` takes up to 2 arguments. To get more, set #define
BOOST_MSM_VISITOR_ARG_SIZE to another value before including
state_machine.hpp. For example:

....
#define BOOST_MSM_VISITOR_ARG_SIZE 3
#include <boost/msm/back/state_machine.hpp>
....

Note that accept will be called on ALL active states _and also
automatically on sub-states of a submachine_.

_Important warning_: The method visit_current_states takes its parameter
by value, so if the signature of the accept function is to contain a
parameter passed by reference, pass this parameter with a boost:ref/cref
to avoid undesired copies or slicing. So, for example, in the above
case, call:

....
SomeVisitor vis; sm.visit_current_states(boost::ref(vis));
....

This xref:attachment$SM-2Arg.cpp[example] uses a visiting function with 2
arguments.

[[flags]]

== Flags

Flags is a MSM-only concept, supported by all front-ends, which base
themselves on the functions:

....
template <class Flag> bool is_flag_active()
template <class Flag,class BinaryOp> bool is_flag_active()
....

These functions return true if the currently active state(s) support the
Flag property. The first variant ORs the result if there are several
orthogonal regions, the second one expects OR or AND, for example:

....
my_fsm.is_flag_active<MyFlag>()
my_fsm.is_flag_active<MyFlag,my_fsm_type::Flag_OR>()
....

Please refer to the front-ends sections for usage examples.

[[getting-a-state]]

== Getting a state

It is sometimes necessary to have the client code get access to the
states' data. After all, the states are created once for good and hang
around as long as the state machine does, so why not use it? You simply
just need sometimes to get information about any state, even inactive
ones. An example is if you want to write a coverage tool and know how
many times a state was visited. To get a state, use the get_state method
giving the state name, for example:

....
player::Stopped* tempstate = p.get_state<player::Stopped*>();
....

or

....
player::Stopped& tempstate2 = p.get_state<player::Stopped&>();
....

depending on your personal taste.

[[backend-fsm-constructor-args]]

== State machine constructor with arguments

You might want to define a state machine with a non-default constructor.
For example, you might want to write:

....
struct player_ : public msm::front::state_machine_def<player_> 
{ 
    player_(int some_value){…} 
}; 
....

This is possible, using the back-end as forwarding object:

....
typedef msm::back11::state_machine<player_ > player; player p(3);
....

The back-end will call the corresponding front-end constructor upon
creation.

You can pass arguments up to the value of the
BOOST_MSM_CONSTRUCTOR_ARG_SIZE macro (currently 5) arguments. Change
this value before including any header if you need to overwrite the
default.

You can also pass arguments by reference (or const-reference) using
boost::ref (or boost::cref):

....
struct player_ : public msm::front::state_machine_def<player_>  
{
   player_(SomeType& t, int some_value){…}  
}; 

typedef msm::back11::state_machine<player_ > player; 
SomeType data;
player p(boost::ref(data),3);
                    
....

Normally, MSM default-constructs all its states or submachines. There
are however cases where you might not want this. An example is when you
use a state machine as submachine, and this submachine used the above
defined constructors. You can add as first argument of the state machine
constructor an expression where existing states are passed and copied:

....
player p( back::states_ << state_1 << ... << state_n , boost::ref(data),3);
....

Where state_1..n are instances of some or all of the states of the state
machine. Submachines being state machines, this can recurse, for
example, if Playing is a submachine containing a state Song1 having
itself a constructor where some data is passed:

....
player p( back::states_ << Playing(back::states_ << Song1(some_Song1_data)) , 
          boost::ref(data),3);
....

It is also possible to replace a given state by a new instance at any
time using `set_states()` and the same syntax, for example:

....
p.set_states( back::states_ << state_1 << ... << state_n );
....

An xref:attachment$Constructor.cpp[example] making intensive use of this
capability is provided.

[[backend-tradeof-rt-ct]]

== Trading run-time speed for better compile-time / multi-TU compilation (`msm::back` only)

MSM is optimized for run-time speed at the cost of longer compile-time.
This can become a problem with older compilers and big state machines,
especially if you don't really care about run-time speed that much and
would be satisfied by a performance roughly the same as most state
machine libraries. MSM offers a back-end policy to help there. But
before you try it, if you are using a VC compiler, deactivate the /Gm
compiler option (default for debug builds). This option can cause builds
to be 3 times longer... If the compile-time still is a problem, read
further. MSM offers a policy which will speed up compiling in two main
cases:

* many transition conflicts
* submachines

The back-end `msm::back11::state_machine` has a policy argument (first
is the front-end, then the history policy) defaulting to
`favor_runtime_speed`. To switch to `favor_compile_time`, which is
declared in `<msm/back/favor_compile_time.hpp>`, you need to:

* switch the policy to `favor_compile_time` for the main state machine
(and possibly submachines)
* move the submachine declarations into their own header which includes
`<msm/back/favor_compile_time.hpp>`
* add for each submachine a cpp file including your header and calling a
macro, which generates helper code, for example:
+
....
#include "mysubmachine.hpp"
BOOST_MSM_BACK_GENERATE_PROCESS_EVENT(mysubmachine)
....
* configure your compiler for multi-core compilation

You will now compile your state machine on as many cores as you have
submachines, which will greatly speed up the compilation if you factor
your state machine into smaller submachines.

Independently, transition conflicts resolution will also be much faster.

This policy uses boost.any behind the hood, which means that we will
lose a feature which MSM offers with the default policy,
link:#event-hierarchy[event hierarchy]. The following example takes our
iPod example and speeds up compile-time by using this technique. We
have:

* xref:attachment$iPod_distributed/iPod.cpp[our main state machine and
main function]
* xref:attachment$iPod_distributed/PlayingMode.hpp[PlayingMode moved to a
separate header]
* xref:attachment$iPod_distributed/PlayingMode.cpp[a cpp for PlayingMode]
* xref:attachment$iPod_distributed/MenuMode.hpp[MenuMode moved to a
separate header]
* xref:attachment$iPod_distributed/MenuMode.cpp[a cpp for MenuMode]
* xref:attachment$iPod_distributed/Events.hpp[events move to a separate
header as all machines use it]

[[backend-compile-time-analysis]]

== Compile-time state machine analysis

A MSM state machine being a metaprogram, it is only logical that
checking for the validity of a concrete state machine happens
compile-time. To this aim, using the compile-time graph library
http://www.dynagraph.org/mpl_graph/[mpl_graph] (delivered at the moment
with MSM) from Gordon Woodhull, MSM provides several compile-time
checks:

* Check that orthogonal regions are truly orthogonal.
* Check that all states are either reachable from the initial states or
are explicit entries / pseudo-entry states.

To make use of this feature, the back-end provides a policy (default is
no analysis), `msm::back::mpl_graph_fsm_check`. For example:

....
 typedef msm::back11::state_machine< player_,msm::back::mpl_graph_fsm_check> player;           
....

As MSM is now using Boost.Parameter to declare policies, the policy
choice can be made at any position after the front-end type (in this
case `player_`).

In case an error is detected, a compile-time assertion is provoked.

This feature is not enabled by default because it has a non-neglectable
compile-time cost. The algorithm is linear if no explicit or pseudo
entry states are found in the state machine, unfortunately still
O(number of states * number of entry states) otherwise. This will be
improved in future versions of MSM.

The same algorithm is also used in case you want to omit providing the
region index in the `explicit entry / pseudo entry state` declaration.

The author's advice is to enable the checks after any state machine
structure change and disable it again after sucessful analysis.

The xref:attachment$TestErrorOrthogonality.cpp[following example] provokes
an assertion if one of the first two lines of the transition table is
used.

[[backend-enqueueing]]

== Enqueueing events for later processing

Calling `process_event(Event const&)` will immediately process the event
with run-to-completion semantics. You can also enqueue the events and
delay their processing by calling `enqueue_event(Event const&)` instead.
Calling `execute_queued_events()` will then process all enqueued events
(in FIFO order). Calling `execute_single_queued_event()` will execute
the oldest enqueued event.

You can query the queue size by calling `get_message_queue_size()`.

[[backend-queues]]

== Customizing the message queues

MSM uses by default a std::deque for its queues (one message queue for
events generated during run-to-completion or with `enqueue_event`, one
for deferred events). Unfortunately, on some STL implementations, it is
a very expensive container in size and copying time. Should this be a
problem, MSM offers an alternative based on boost::circular_buffer. The
policy is msm::back::queue_container_circular. To use it, you need to
provide it to the back-end definition:

....
 typedef msm::back11::state_machine< player_,msm::back::queue_container_circular> player;           
....

You can access the queues with get_message_queue and get_deferred_queue,
both returning a reference or a const reference to the queues
themselves. Boost::circular_buffer is outside of the scope of this
documentation. What you will however need to define is the queue
capacity (initially is 0) to what you think your queue will at most
grow, for example (size 1 is common):

....
 fsm.get_message_queue().set_capacity(1);           
....

[[backend-boost-parameter]]

== Policy definition with Boost.Parameter

MSM uses Boost.Parameter to allow easier definition of
back11::state_machine<> policy arguments (all except the front-end).
This allows you to define policy arguments (history, compile-time /
run-time, state machine analysis, container for the queues) at any
position, in any number. For example:

....
 typedef msm::back11::state_machine< player_,msm::back::mpl_graph_fsm_check> player;  
 typedef msm::back11::state_machine< player_,msm::back::AlwaysHistory> player;  
 typedef msm::back11::state_machine< player_,msm::back::mpl_graph_fsm_check,msm::back::AlwaysHistory> player; 
 typedef msm::back11::state_machine< player_,msm::back::AlwaysHistory,msm::back::mpl_graph_fsm_check> player;      
....

[[backend-state-switch]]

== Choosing when to switch active states

The UML Standard is silent about a very important question: when a
transition fires, at which exact point is the target state the new
active state of a state machine? At the end of the transition? After the
source state has been left? What if an exception is thrown? The Standard
considers that run-to-completion means a transition completes in almost
no time. But even this can be in some conditions a very very long time.
Consider the following example. We have a state machine representing a
network connection. We can be `Connected` and `Disconnected`. When we
move from one state to another, we send a (Boost) Signal to another
entity. By default, MSM makes the target state as the new state after
the transition is completed. We want to send a signal based on a flag
is_connected which is true when in state Connected.

We are in state `Disconnected` and receive an event `connect`. The
transition action will ask the state machine
`is_flag_active<is_connected>` and will get... false because we are
still in `Disconnected`. Hmm, what to do? We could queue the action and
execute it later, but it means an extra queue, more work and higher
run-time.

MSM provides the possibility (in form of a policy) for a front-end to
decide when the target state becomes active. It can be:

* before the transition fires, if the guard will allow the transition to
fire: `active_state_switch_before_transition`
* after calling the exit action of the source state:
`active_state_switch_after_exit`
* after the transition action is executed:
`active_state_switch_after_transition_action`
* after the entry action of the target state is executed (default):
`active_state_switch_after_entry`

The problem and the solution is shown for the
xref:attachment$ActiveStateSetBeforeTransition.cpp[functor-front-end] and
xref:attachment$ActivateStateBeforeTransitionEuml.cpp[eUML]. Removing
`active_state_switch_before_transition` will show the default state.


== Known limitations

Any currently known issues and limitations with the `back` and `back11` back-ends are described below.


=== Deferring events in orthogonal regions

The event deferral logic requires deferred events to be dispatched for evaluation.
When a deferred event is dispatched to orthogonal regions, each region individually decides whether to consume or defer the event.
This can lead to scenarios where one region defers the event and the other one processes it,
causing infinite recursions because the event deferral logic needs to re-evaluate the deferred-and-processed event over and over.

According to the UML standard, in such a case the event should be deferred as long as one region decides to defer it.
This issue can be worked around by explicitly ensuring (for example with guards) that the event is exclusively _either_ deferred _or_ processed.
