Re: more on preemption

I don't have time right now.  The error isn't in calculating the exit sets
but specifically in deciding how to preempt things.

The error is line:

if isDescendent(t1.source, t2.source):****

                    transitionsToRemove.add(t2)****

                else:****

                    t1Preempted = true****

                    break


Where it reads t1.source and t2.source is should be getArena(t1) and
getArena(t2).


Chris



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

>  Chris,****
>
> Are you saying that we are calculating exit sets incorrectly?  The
> algorithm detects a conflict between two transitions whenever their exit
> sets intersect.  There’s no mention of source states here (i.e., in the
> definition of conflict) except insofar as they help determine the exit set.
> ( Internal transitions are handled in getTransitionDomain(), so their
> influence on the exit set should also be reflected in the algorithm) Then
> once a conflict is detected, we look at the source state relationships to
> determine who preempts whom.   That’s our heuristic for resolving
> conflicts, inherited from UML, but I don’t think it effects correctness.
> But if we’re calculating exit sets incorrectly, that would cause us to be
> incorrect.  ****
>
> ** **
>
> Can you send around an example that shows the problem?****
>
> ** **
>
> Thanks,****
>
> Jim****
>
> ** **
>
> *From:* chris nuernberger [mailto:cnuernber@gmail.com]
> *Sent:* Friday, March 08, 2013 1:07 PM
>
> *To:* Jim Barnett
> *Cc:* VBWG Public (www-voice@w3.org)
> *Subject:* 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 ****
>



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