more on preemption

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