RE: preemption again (sigh...)

I also find the existing behavior intuitive - once you realize how this edge case works.   And you can form a simple mental model of preemption (pick a transition in the first state, now go to the second, pick one and keep it if it doesn't conflict, etc.)

Here is the UML 2 discussion of the issue.  The second paragraph does say that transitions in descendents take precedence over those in ancestors, but I can't make much sense of the 'greedy selection algorithm' in the third paragraph.  In general, I think that we should be consistent with UML, but I don't like trying to maintain consistency with something I can't understand...


-          Jim

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.

582 UML Superstructure Specification, v2.3 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.
From: chris nuernberger [mailto:cnuernber@gmail.com]
Sent: Thursday, February 28, 2013 5:42 PM
To: Michael Bodell
Cc: Jim Barnett; VBWG Public (www-voice@w3.org)
Subject: Re: preemption again (sigh...)

I doubt there is a way you could come up with something where all of the examples have completely intuitive results.  I agree with the analysis.

IF you always wanted transitions in children to have descendants over transitions in ancestors then that is fine but it is somewhat (or perhaps) a lot harder to implement than the current algorithm.  It also precludes short circuiting the transition selection algorithm, something that I can in favor of.

Going back to the definition I gave a while time ago where you looked at preemption based on if a transition arena is the child of another arena you could have an efficient algorithm to allow exactly what UML suggests, allowing descendents to take precedence.  You would just always take the descendent of order of the transitions in the document.  The problem is that a later transition could preempt an earlier one and thus you would have to produce essentially a new transition list on every transition instead of just appending to the transition list.

In any case, this could be a potentially large discrepancy from the UML specification.  Which would only manifest itself in subtle edge cases.  Seems troubling.

Chris


On Thu, Feb 28, 2013 at 3:03 PM, Michael Bodell <bodell@247-inc.com<mailto:bodell@247-inc.com>> wrote:
I personally find the current behavior more intuitive, where the transition associated with deeplyNested1 that goes to somewhereFarAway "wins" over the transition as part of deeplyNested2.  I think the key thing for me is which atomic states you are in at the time, so thinking from that perspective makes the current behavior intuitive.

From: Jim Barnett [mailto:Jim.Barnett@genesyslab.com<mailto:Jim.Barnett@genesyslab.com>]
Sent: Thursday, February 28, 2013 1:57 PM
To: VBWG Public (www-voice@w3.org<mailto:www-voice@w3.org>)
Subject: preemption again (sigh...)

Johan points out that the currently proposed definition of preemption (and the one in the current spec) have a counter-intuitive result, which is that transitions placed very high in the state machine can preempt ones in atomic states.  Consider the following case:

<state id="s1">
<transition event="e" target="someWhereFarAway">
    ... imagine a bunch of nested states here with no transitions that handle e...
   <parallel>
      <state id="deeplyNested1"/>
      <state id="deeplyNested2">
           <transition event="e" target="someWhereElseFarAway"/>
  </state>
</parallel>
.......
</state>

If we are within the parallel region when e occurs, then state deeplyNested1 will select the transition that is a child of s1 while deeplyNested2 will select the transition that is contained inside it.   These two transitions will conflict.  In our current definition, the one chosen by deeplyNested1 will win, since that state comes first in document order.   Johan finds this counterintuitive since that transition is located much higher up in the state machine than the one in deeplyNested2.  (In fact, its source state is an ancestor of deeplyNested2).    Johan argues that this will make the behavior of complex state machines hard to understand.

So, my question is:  do other people find this behavior odd or confusing?  Do we want to try to tweak the definition so that the transition in deeplyNested2 would win?  (It may take a pretty big tweak...)


-          Jim


P.S.  I've looked at UML 2 and find its explanation extremely vague.  It does define clearly conflict in terms of intersecting exit sets.  It also says that transitions inside descendents take precedence over transitions in ancestors, but the rest of the discussion is so confusing that I'm not sure what algorithm they really suggest.



--
A foolish consistency is the hobgoblin of little minds - Emerson