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

Subject: Re: [boost] [msm]exit pseudo state and event
From: Takatoshi Kondo (kondo_at_[hidden])
Date: 2011-07-20 10:16:29

On Wed, 20 Jul 2011 00:30:03 +0200
"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.
> 
> Sure but msm implements all those cases.

Yes.

> >> 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.
> 
> I'm afraid you misunderstood me. I didn't write that a choice pseudo-state 
> is a corner case but that the change you request has a few corner cases to 
> consider if the implementation is to work.

I'm sorry. I omitted too much information.
Please let me explain step by step.

1.When the transition process exiting the substatemachine, 
  We sometimes need if/else transition outside of substatemachine.
2.In the case above, we can use the anonymous transitions for else 
  transitions.
  But we have to write it the top of same start state group in 
  transition table.
  I think it isn't natural description.
  And I asked you to change the evaluation order reverse.

And then, you said it's difficult. And you showed me some reasons.
At that time I didn't know the evaluation order was already documented.
Hence, I thought changing the order was not big problem, 
I thought it's only implementation problem.

3.I consider that anonymous transitions for else transition have wider usage.
  e.g. For implement choice pseudo states using msm.

This is why I said it's not corner case. Sorry for less description.

> >> - 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.
> 
> No, this is documented 
> (http://www.boost.org/doc/libs/1_47_0/libs/msm/doc/HTML/ch06.html): "the 
> guard conditions are tried in reverse order of their transition definition 
> in the transition table" and I know of a few people using this.

Oh.. I missed it.

> > 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 ===
> 
> Yes, it is probably this.
> 
> > 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 >
> >    > {};
> > };
> 
> Are you saying we don't need internal transitions? I'd disagree then. 
> They're the best way to implement taking action without changing state.

No. UML's internal transitions are important.
Msm provides some options to implement it.

Without eUML, functor front-end is preferred.
http://www.boost.org/doc/libs/1_47_0/libs/msm/doc/HTML/ch03s03.html#d0e1396
//    Start     Event         Next      Action     Guard
Row < Empty   , cd_detected , none    , none     , internal_guard       >,

We can describe internal transitions to set Next to none.
Is it right?

g_irow is almost same.
//       Start   Event        Guard
g_irow < Empty , cd_detected ,&p::internal_guard>

I think they are needed.

I only mean internal_transition_table is not mandatory.
http://www.boost.org/doc/libs/1_47_0/libs/msm/doc/HTML/ch03s02.html#internal-transitions

Because we already have the machanism that controls the evaluation order 
from inside substatemachine to outside.
And UML standard said that internal transitions are not relate to priority.
There are no guaranty that internal transitions are evaluated faster than 
another (non internal) transitions if they have same start state.

Consider fig1.png.
Thease two transitions have same priority.
At least in UML specification, we don't have a guaranty that 
which transition would be handled.
But one of them would be handled.

If we want to give the internal transition higher priority,
we should write the statemachine like fig2.png.
In the case of fig2, only the internal transition would be handled.

Do you agree?

But we can control the evaluating order using the Row's sequence.
(I think it is out of UML standard.)

e.g. 

//    Start     Event         Next      Action     Guard
Row < Empty   , cd_detected , none    , none     , internal_guard       >,
Row < Empty   , cd_detected , State1  , none     , another_guard        >,
or
//    Start     Event         Next      Action     Guard
Row < Empty   , cd_detected , State1  , none     , another_guard        >,
Row < Empty   , cd_detected , none    , none     , internal_guard       >,

I'd like to know why internal_transition_table is needed.
I think transition_table is enough.

> > 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.
> 
> Well, yes, if you change the test, of course it will work ;-)

Sorry, I was misunderstanding UML specification.
My internal_continue.patch is wrong.

I misunderstood the sentence that "An internal transition in a 
state conflicts only with transitions that cause an exit from that state."

I thought we could execute multiple internal transitions on one event.
But it's not true.

I found the sentence below.
"In the presence of orthogonal regions it is possible to fire multiple transi
tions as a result of the same event occurrence --
as many as one transition in each region in the current state configuration."

I pull back internal_continue.patch.

> > I tested on the following environments.
> > g++ (Ubuntu 4.4.3-4ubuntu5) 4.4.3
> > Microsoft Visual C++ 2008 Express Edition SP1
> 
> Unfortunately my tests are not sufficient, it's something I want to take 
> care of soon.

OK.

> > Could you check my patches?
> 
> I did. I'm not sure I fully get what you're trying but I don't think it will 
> work.
> Again, there are quite some cases to think about.
> Let's take one, to show why the priority given to inner is important. See 
> conflict_and_exit.
> If I believe your example in smd1, there is no priority. Then, the exit 
> points cannot work any more (yes, transitions leading to exit points are 
> inner transitions).

Sorry smd1 is based on my misunderstanding of UML specification.

> Frankly, I don't see the point in doing such change:
> - it will break people's code
> - it will break a documented implementation

I agree.

> - I doubt it will work in all cases
> - it is likely to be slower (more if statements)
> - it will not be Standard-conform. To do this, I need a really good reason
> 
> And this for no bugfix and no added feature, simply to be able to write:
> 
> // else clause
> Row< state1, ev, state2, none, none>
> // if clause
> Row< state1, ev, state2, none, Or_<...> >
> 
> instead of:
> 
> // if clause
> Row< state1, ev, state2, none, Or_<...> >
> // else clause
> Row< state1, ev, state2, none, none>
> 
> No, this does not look appealing to me.
> If you're at implementing stuff for msm, I might consider another solution:
> - a typedef in the front-end, which will change the reading order of the 
> table, no to break other's code

Thanks for good suggestion.
I'd like to consider a little more:)

> - replacing in dispatch_table reverse_fold by fold to change the reading 
> order if typedef is requesting it.
> - adding rows (frows) at the top instead of bottom.
> 
> This leaves us with the hard part, reading the ids in the correct order. For 
> this, we need to find out which one of the transition table transformations 
> is the correct one. I didn't look at it yet, but I imagine it could be 
> tricky. Then use it to read the id from up to down.
> 
> I understand you like this feature, but I need to also consider the wishes 
> of those who requested me very useful features some time ago and are waiting 
> for them.
> So it's also my job to allocate my scarce development time (my evenings) 
> where I think it will be the most useful.
> For example, the junction pseudo-state you requested seems to me to have a 
> much higher gain for all of us.

Yes. I understand your situation.
I agree this request is not high priority.
And the request is not reasonable enough at this time.

Also I'd like to know your design philosophy of msm.
I would ask you some questions.

> Regards,
> Christophe

Thanks,
Takatoshi