Re: [boost] [msm]exit pseudo state and event

Subject: Re: [boost] [msm]exit pseudo state and event
From: Takatoshi Kondo (redboltz_at_[hidden])
Date: 2011-07-18 04:02:00

On Thu, Jul 14, 2011 at 4:48 AM, Christophe Henry
<christophe.j.henry_at_[hidden]> wrote:
>>> > Off the top of my head, how about the functor Else_ below?
>>> > Else_ <Guard1, Guard2, Guard3, ... >
>>>
>>> For else, we can use the fact that msm tries guards from the bottom of
>>> the
>>> table to the top:
>>>
>>> // else clause
>>> Row< state1, ev, state2, none, none>,
>>> // if clause
>>> Row< state1, ev, state2, none, Or_<...> >
>>> // more if clauses
>>> ...
>>
>> Fantastic!
>> This has 2 advantages and 1 disadvantage.
>>
>> Advantages:
>> One is simple enough. The other is good performance.
>> It doesn't need evaluating the guard functor twice.
>> I was about to consider how to cache the functor's result.
>>
>> Disadvantage:
>> As you might expect, the evaluating direction is opposite of my intuition.
>>
>> Are there any reasons of this implementation?
>
> There are.
> It's an implementation detail which dates back to the early phases of the
> library (start + 3 months).
> The reason is that msm adds, for performance, rows for submachines at the
> end of the table (one for every event found in the submachine), then starts
> processing from the bottom to give these rows a higher priority (UML rule).

I agree.
But this UML rule should only apply the submachine structure.
I describe more details below.

> At the same time, the library also uses the table to generate state ids
> (http://svn.boost.org/svn/boost/trunk/libs/msm/doc/HTML/ch06s03.html).
> I could do the opposite (extra rows at the beginning) but it'd be pretty
> hard to guess after this what the state id you get in no_transition means
> (it's already hard enough to explain the current order, imagine if I had to
> explain you have to count in reverse order...).

I agree.
State id ordering shouldn't be changed.

> And as the else feature is not in the Standard, it seemed ok.
> In these early phases I didn't have, like now, different steps of transition
> table processing.
> This old decision could deserve some revisiting, but:
> - there are a few corner cases which could make a change pretty tricky
> (pseudo entry/exit states)

I think it isn't corner case.
Consider else_usecase.png.(attached file)
When we implement choice pseudo state, we often use the else guard.
And when we implement this statemachine using msm, we use extra event like the
substatemachine case.
See else_usecase_converted.png.

IMHO, we often meet with this case.

> - some people already use the current implementation state, so it'd break
> their code, I'd need some compile-time configuration, which would get hidden
> deep in the already big doc. The default would still be the current order.

Current documents refer to only state id order.
http://www.boost.org/doc/libs/1_47_0/libs/msm/doc/HTML/ch06s03.html

They don't refer to reverse transition evaluation. I believe it's
still implement detail.
This meas we have a chance to change the evaluation order.
Here is my solution.

See forward_eval.patch.

In dispatch_table.hpp,
If the state is submachine state then front_row and Fsm::frow<State,
Event> are same.
And it appears only front element.
The evaluating direction changes by this information.
After applying this patch, 14_GuardEvalOrder.cpp(attached file)
outputs the result below.

Guard1_1
Guard1_2
Guard1_3
Guard1_4
Guard1
Guard2
Guard3
Guard4

Both evaluation priority and order are OK :)

But there is another problem that relate to internal transitions.
http://www.boost.org/doc/libs/1_47_0/libs/msm/doc/HTML/ch03s02.html#d0e807

The document said internal transitions have the highest priority(as
mandated by the UML standard).
I checked UML standard. But I couldn't find this rule.
(OMG Unified Modeling LanguageTM (OMG UML) Superstructure Version 2.3)

I'm guessing you mean below.

15.3.12 StateMachine (from BehaviorStateMachines)

=== begin quotation ===
Conflicting transitions
It was already noted that it is possible for more than one transition
to be enabled within a state machine. If that happens,
then such transitions may be in conflict with each other. For example,
consider the case of two transitions originating
from the same state, triggered by the same event, but with different
guards. If that event occurs and both guard conditions
are true, then only one transition will fire. In other words, in case
of conflicting transitions, only one of them will fire in
a single run-to-completion step.
Two transitions are said to conflict if they both exit the same state,
or, more precisely, that the intersection of the set of
states they exit is non-empty. Only transitions that occur in mutually
orthogonal regions may be fired simultaneously. This
constraint guarantees that the new active state configuration
resulting from executing the set of transitions is well-formed.
An internal transition in a state conflicts only with transitions that
cause an exit from that state.

Firing priorities
In situations where there are conflicting transitions, the selection
of which transitions will fire is based in part on an
implicit priority. These priorities resolve some transition conflicts,
but not all of them. The priorities of conflicting
transitions are based on their relative position in the state
hierarchy. By definition, a transition originating from a substate
has higher priority than a conflicting transition originating from any
of its containing states.
The priority of a transition is defined based on its source state. The
priority of joined transitions is based on the priority
of the transition with the most transitively nested source state.
In general, if t1 is a transition whose source state is s1, and t2 has
source s2, then:
 * If s1 is a direct or transitively nested substate of s2, then t1
has higher priority than t2.
 * If s1 and s2 are not in the same state configuration, then there is
no priority difference between t1 and t2.
Transition selection algorithm
The set of transitions that will fire is a maximal set of transitions
that satisfies the following conditions:
 * All transitions in the set are enabled.
 * There are no conflicting transitions within the set.
 * There is no transition outside the set that has higher priority
than a transition in the set (that is, enabled transitions
with highest priorities are in the set while conflicting transitions
with lower priorities are left out).
This can be easily implemented by a greedy selection algorithm, with a
straightforward traversal of the active state
configuration. States in the active state configuration are traversed
starting with the innermost nested simple states and
working outwards. For each state at a given level, all originating
transitions are evaluated to determine if they are
enabled. This traversal guarantees that the priority principle is not
violated. The only non-trivial issue is resolving
transition conflicts across orthogonal states on all levels. This is
resolved by terminating the search in each orthogonal
state once a transition inside any one of its components is fired.
=== end quotation ===

See smd1.png , smd2.png and smd3.png. These are my understanding.
And I wrote internal_continue.patch.
This modification is to continue evaluating process if evaluated row
is internal transition.

If my understanding is right, we don't need the following expression.

struct Empty : public msm::front::state<>
{
    struct internal_transition_table : mpl::vector<
           a_internal < cd_detected , Empty, &Empty::internal_action >
    > {};
};

You can check this behavior using 15_MultiInternalTransition.cpp.

>> Modifying to the opposite direction is easy?
>
> Unfortunately not, so considering the gain and the time it'd cost, it's
> unlikely to change until I have nothing else to implement in the library,
> which could take some time ;-)

I also did the tests.
To pass the all tests, it requires some changes. See msm_test.patch.
The changes are only ordering of rows.
Internal transitions move up in the same start state group.
These changes doesn't effect the state ids.

After 3 patches are applied, all tests passed.
I tested on the following environments.
g++ (Ubuntu 4.4.3-4ubuntu5) 4.4.3
Microsoft Visual C++ 2008 Express Edition SP1

Could you check my patches?

> Regards,
> Christophe

Thanks,
Takatoshi