Re: more on preemption

I don't think the algorithm is correct.  This goes back to the UML spec
which I *also* think is incorrect.

This argument ignores transitions of internal types which is a detail.

The exit set is calculated via the LCCA of the source and the target
states.  Let's call this item the transition arena as we have before.

It may be the source but it also may be considerable higher up the state
graph than the source.

Your given algorithm only compares the transition sources for descendant
qualities when it should compare the transition arenas *because* the
sources may be unrelated in the graph *but* the exit sets collide.  A
correct algorithm would look *just* like the one given except you would
compare the transition arena's for descendent instead of transition sources.

Chris




On Fri, Mar 8, 2013 at 8:12 AM, Jim Barnett <Jim.Barnett@genesyslab.com>wrote:

>  There hasn’t been any further discussion on this.  Based on the
> discussion so far, I think that we should say that transitions in
> descendents preempt transitions in ancestors.)  The UML spec requires this
> quite clearly (even if the rest of the discussion is confusing) and
> “descendents preempt ancestors” is one of the basic principles of the
> language.  Here’s a modified preemption algorithm that implements it.   **
> **
>
> ** **
>
> Implementations will be able to do something more efficient.  For example,
> this algorithm tries to handle the case where a transition t1 conflicts
> with multiple transitions, say t2 and t3, where t1’s source state is a
> descendent of t2’s, but not of t3’s.  in this case, t1 is preempted by t3
> (because t3 was chosen in a preceding state), so we _*keep*_ t2, even
> though it would be preempted by t1 if t1 weren’t blocked by t3.  I’m pretty
> sure that this case can’t arise in practice, but I haven’t been able to
> prove it, so I have tried to make the algorithm handle it.  ****
>
> ** **
>
> Let me know what you think about both the clarity and correctness of this
> version.  ****
>
> ** **
>
> **-          **Jim****
>
> ** **
>
> *function** removeConflictingTransitions(enabledTransitions)*
>
> enabledTransitions will contain multiple transitions only if a parallel
> state is active. In that case, we may have one transition selected for each
> of its children. These transitions may conflict with each other in the
> sense that they have incompatible target states. Loosely speaking,
> transitions are compatible when each one is contained within a single
> <state> child of the <parallel> element. Transitions that aren't contained
> within a single child force the state machine to leave the <parallel>
> ancestor (even if they reenter it later). Such transitions conflict with
> each other, and with transitions that remain within a single <state> child,
> in that they may have targets that cannot be simultaneously active. The
> test that transitions have non-intersecting exit sets captures this
> requirement. (If the intersection is null, the transitions are contained in
> separate <state> descendents of <parallel>. If intersection is non-null,
> then at least one of the transitions is exiting the <parallel>). When such
> a conflict occurs, then if the source state of one of the transitions is a
> descendent of the source state of the other, we select the transition in
> the descendent. Otherwise we prefer the transition that was selected by the
> earlier state in document order and discard the other transition. Note that
> targetless transitions have empty exit sets and thus do not conflict with
> any other transitions. ****
>
> We start with a list of enabledTransitions and produce a conflict-free
> list of filteredTransitions. For each t1 in enabledTransitions, we test it
> against all t2 that are already selected in filteredTransitions. If there
> is a conflict, then if t1's source state is a descendent of t2's source
> state, we prefer t1 and say that it preempts t2 (so we we make a note to
> remove t2 from filteredTransitions). Otherwise, we prefer t2 since it was
> selected in an earlier state in document order, so we say that it preempts
> t1. (There's no need to do anything in this case since t2 is already in
> filteredTransitions. Furthermore, once one transition preempts t1, there is
> no need to test t1 against any other transitions.) Finally, if t1 isn't
> preempted by any transition in filteredTransitions, remove any transitions
> that it preempts and add it to that list. ****
>
> function removeConflictingTransitions(enabledTransitions):****
>
>     filteredTransitions = new OrderedSet()****
>
> // toList sorts the transitions in the order of the states that selected
> them****
>
>     for t1 in enabledTransitions.toList():****
>
>         t1Preempted = false;****
>
>         transitionsToRemove = new OrderedSet()****
>
>         for t2 in filteredTransitions.toList():****
>
>             if computeExitSet(t1).hasIntersection(computeExitSet(t2)):****
>
>                 if isDescendent(t1.source, t2.source):****
>
>                     transitionsToRemove.add(t2)****
>
>                 else: ****
>
>                     t1Preempted = true****
>
>                     break****
>
>         if not t1Preempted:****
>
>             for t3 in transitionsToRemove.toList():****
>
>                 filteredTransitions.delete(t3)****
>
>             filteredTransitions.add(t1)****
>
>            ****
>
>     return filteredTransitions****
>
> ** **
>



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