RE: more on preemption

Gavin,
   Here’s my current version of the whole algorithm.  It may be impossible to read via email, but it’s a start (Let me know if you have problems – I can try resending things piecemeal).   Separately I do plan to post my “editor’s draft”,  along with a diff-specd version, sometime in the next couple of weeks.  It will include the changes to the spec language as well as the algorithm.   I’d like for everyone who had commented on the current draft to get a look at the proposed changes before we publish another official draft.


-          Jim

Procedures and Functions

This section defines the procedures and functions that make up the core of the SCXML interpreter. N.B. in the code below, the keyword 'continue' has its traditional meaning in languages like C: break off the current iteration of the loop and procede to the next iteration.

procedure interpret(scxml,id)

The purpose of this procedure is to initialize the interpreter and to start processing.

In order to interpret an SCXML document, first (optionally) perform [XInclude]<file:///D:\W3C\WWW\Voice\Group\2005\HST\SCXMLNotation.html#xinclude> processing and (optionally) validate the document, throwing an exception if validation fails. Then convert initial attributes to <initial> container children with transitions to the state specified by the attribute. (This step is done purely to simplify the statement of the algorithm and has no effect on the system's behavior. Such transitions will not contain any executable content). Initialize the global data structures, including the datamodel. If binding is set to 'early', initialize the datamodel. Then execute the global <script> element, if any. Finally call enterStates on the initial configuration, set the global running variable to true and start the interpreter's event loop.

procedure interpret(doc):

    if not valid(doc): failWithError()

    expandScxmlSource(doc)

    configuration = new OrderedSet()

    statesToInvoke = new OrderedSet()

    internalQueue = new Queue()

    externalQueue = new BlockingQueue()

    historyValue = new HashTable()

    datamodel = new Datamodel(doc)

    if doc.binding == "early":

        initializeDatamodel(datamodel, doc)

    running = true

    executeGlobalScriptElement(doc)

    enterStates([doc.initial.transition])

    mainEventLoop()

procedure mainEventLoop()

This loop runs until we enter a top-level final state or an external entity cancels processing. In either case 'running' will be set to false (see EnterStates, below, for termination by entering a top-level final state.)

At the top of the loop, we have either just entered the state machine, or we have just processed an external event. Each iteration through the loop consists of four main steps: 1)Complete the macrostep by repeatedly taking any internally enabled transitions, namely those that don't require an event or that are triggered by an internal event. After each such transition/microstep, check to see if we have reached a final state. 2) When there are no more internally enabled transitions available, the macrostep is done. Execute any <invoke> tags for states that we entered on the last iteration through the loop 3) If any internal events have been generated by the invokes, repeat step 1 to handle any errors raised by the <invoke> elements. 4) When the internal event queue is empty, wait for an external event and then execute any transitions that it triggers. However special preliminary processing is applied to the event if the state has executed any <invoke> elements. First, if this event was generated by an invoked process, apply <finalize> processing to it. Secondly, if any <invoke> elements have autoforwarding set, forward the event to them. These steps apply before the transitions are taken.

This event loop thus enforces run-to-completion semantics, in which the system process an external event and then takes all the 'follow-up' transitions that the processing has enabled before looking for another external event. For example, suppose that the external event queue contains events ext1 and ext2 and the machine is in state s1. If processing ext1 takes the machine to s2 and generates internal event int1, and s2 contains a transition t triggered by int1, the system is guaranteed to take t, no matter what transitions s2 or other states have that would be triggered by ext2. Note that this is true even though ext2 was already in the external event queue when int1 was generated. In effect, the algorithm treats the processing of int1 as finishing up the processing of ext1.

procedure mainEventLoop():

    while running:

        enabledTransitions = null

        macrostepDone = false

        # Here we handle eventless transitions and transitions

        # triggered by internal events until macrostep is complete

        while running and not macrostepDone:

            enabledTransitions = selectEventlessTransitions()

            if enabledTransitions.isEmpty():

                if internalQueue.isEmpty():

                    macrostepDone = true

                else:

                    internalEvent = internalQueue.dequeue()

                    datamodel["_event"] = internalEvent

                    enabledTransitions = selectTransitions(internalEvent)

            if not enabledTransitions.isEmpty():

                microstep(enabledTransitions.toList())

        # either we're in a final state, and we break out of the loop

        if not running:

            break;

        # or we've completed a macrostep, so we start a new macrostep by waiting for an external event

        # Here we invoke whatever needs to be invoked. The implementation of 'invoke' is platform-specific

        for state in statesToInvoke:

            for inv in state.invoke:

                invoke(inv)

        statesToInvoke.clear()

        # Invoking may have raised internal error events and we iterate to handle them

        if not internalQueue.isEmpty():

            continue

       # A blocking wait for an external event.  Alternatively, if we have been invoked

       # our parent session also might cancel us.  The mechanism for this is platform specific,

       # but here we assume it’s a special event we receive

       externalEvent = externalQueue.dequeue()

       if isCancelEvent(externalEvent):

           running = false

           continue

       datamodel["_event"] = externalEvent

       for state in configuration:

           for inv in state.invoke:

              if inv.invokeid == externalEvent.invokeid:

                  applyFinalize(inv, externalEvent)

              if inv.autoforward:

                  send(inv.id, externalEvent)

       enabledTransitions = selectTransitions(externalEvent)

       if not enabledTransitions.isEmpty():

           microstep(enabledTransitions.toList())

    # End of outer while running loop.  If we get here, we have reached a top-level final state or have been cancelled

    exitInterpreter()

procedure exitInterpreter()

The purpose of this procedure is to exit the current SCXML process by exiting all active states. If the machine is in a top-level final state, a Done event is generated. (Note that in this case, the final state will be the only active state.) The implementation of returnDoneEvent is platform-dependent, but if this session is the result of an <invoke> in another SCXML session, returnDoneEvent will cause the event done.invoke.<id> to be placed in the external event queue of that session, where <id> is the id generated in that session when the <invoke> was executed.

procedure exitInterpreter():

    statesToExit = configuration.toList().sort(exitOrder)

    for s in statesToExit:

        for content in s.onexit:

            executeContent(content)

        for inv in s.invoke:

            cancelInvoke(inv)

        configuration.delete(s)

        if isFinalState(s) and isScxmlState(s.parent):

            returnDoneEvent(s.donedata)

function selectEventlessTransitions()

This function selects all transitions that are enabled in the current configuration that do not require an event trigger. First find a transition with no 'event' attribute whose condition evaluates to true. If multiple matching transitions are present, take the first in document order. If none are present, search in the state's ancestors in ancestry order until one is found. As soon as such a transition is found, add it to enabledTransitions, and proceed to the next atomic state in the configuration. If no such transition is found in the state or its ancestors, proceed to the next state in the configuration. When all atomic states have been visited and transitions selected, filter the set of enabled transitions, removing any that are preempted by other transitions, then return the resulting set.

function selectEventlessTransitions():

    enabledTransitions = new OrderedSet()

    atomicStates = configuration.toList().filter(isAtomicState).sort(documentOrder)

    for state in atomicStates:

        loop: for s in [state].append(getProperAncestors(state, null)):

            for t in s.transition:

                if not t.event and conditionMatch(t):

                    enabledTransitions.add(t)

                    break loop

    enabledTransitions = filterPreempted(enabledTransitions)

    return enabledTransitions

function selectTransitions(event)

The purpose of the selectTransitions()procedure is to collect the transitions that are enabled by this event in the current configuration.

Create an empty set of enabledTransitions. For each atomic state , find a transition whose 'event' attribute matches event and whose condition evaluates to true. If multiple matching transitions are present, take the first in document order. If none are present, search in the state's ancestors in ancestry order until one is found. As soon as such a transition is found, add it to enabledTransitions, and proceed to the next atomic state in the configuration. If no such transition is found in the state or its ancestors, proceed to the next state in the configuration. When all atomic states have been visited and transitions selected, filter out any preempted transitions and return the resulting set.

function selectTransitions(event):

    enabledTransitions = new OrderedSet()

    atomicStates = configuration.toList().filter(isAtomicState).sort(documentOrder)

    for state in atomicStates:

        loop: for s in [state].append(getProperAncestors(state, null)):

            for t in s.transition:

                if t.event and nameMatch(t.event, event.name) and conditionMatch(t):

                    enabledTransitions.add(t)

                    break loop

    enabledTransitions = removeConflictingTransitions(enabledTransitions)

    return enabledTransitions

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

procedure microstep(enabledTransitions)

The purpose of the microstep procedure is to process a single set of transitions. These may have been enabled by an external event, an internal event, or by the presence or absence of certain values in the datamodel at the current point in time. The processing of the enabled transitions must be done in parallel ('lock step') in the sense that their source states must first be exited, then their actions must be executed, and finally their target states entered.

If a single atomic state is active, then enabledTransitions will contain only a single transition. If multiple states are active (i.e., we are in a parallel region), then there may be multiple transitions, one per active atomic state (though some states may not select a transition.) In this case, the transitions are taken in the document order of the atomic states that selected them.

procedure microstep(enabledTransitions):

    exitStates(enabledTransitions)

    executeTransitionContent(enabledTransitions)

    enterStates(enabledTransitions)

procedure exitStates(enabledTransitions)

Compute the set of states to exit. Then remove all the states on statesToExit from the set of states that will have invoke processing done at the start of the next macrostep. (Suppose macrostep M1 consists of microsteps m11 and m12. We may enter state s in m11 and exit it in m12. We will add s to statesToInvoke in m11, and must remove it in m12. In the subsequent macrostep M2, we will apply invoke processing to all states that were entered, and not exited, in M1.) Then convert statesToExit to a list and sort it in exitOrder.

For each state s in the list, if s has a deep history state h, set the history value of h to be the list of all atomic descendants of s that are members in the current configuration, else set its value to be the list of all immediate children of s that are members of the current configuration. Again for each state s in the list, first execute any onexit handlers, then cancel any ongoing invocations, and finally remove s from the current configuration.

procedure exitStates(enabledTransitions):

   statesToExit = computeExitSet(enabledTransitions)

   for s in statesToExit:

       statesToInvoke.delete(s)

   statesToExit = statesToExit.toList().sort(exitOrder)

   for s in statesToExit:

       for h in s.history:

           if h.type == "deep":

               f = lambda s0: isAtomicState(s0) and isDescendant(s0,s)

           else:

               f = lambda s0: s0.parent == s

            historyValue[h.id] = configuration.toList().filter(f)

   for s in statesToExit:

       for content in s.onexit:

           executeContent(content)

       for inv in s.invoke:

           cancelInvoke(inv)

       configuration.delete(s)

procedure computeExitSet(enabledTransitions, statesToExit)

For each transition t in enabledTransitions, if t is targetless then do nothing, else compute the transition's domain. (This will be the source state in the case of internal transitions) or the least common compound ancestor state of the source state and target states of t (in the case of external transitions. Add to the statesToExit set all states in the configuration that are descendants of the domain.

function computeExitSet(transitions)

   statesToExit = new OrderedSet

         for t in transitions:

             domain = getTransitionDomain(t)

       for s in configuration:

           if isDescendant(s,domain):

               statesToExit.add(s)

   return statesToExit



procedure executeTransitionContent(enabledTransitions)

For each transition in the list of enabledTransitions, execute its executable content.

procedure executeTransitionContent(enabledTransitions):

    for t in enabledTransitions:

        executeContent(t)

procedure enterStates(enabledTransitions)

First, compute the list of all the states that will be entered as a result of taking the transitions in enabledTransitions. Add them to statesToInvoke so that invoke processing can be done at the start of the next macrostep. Convert statesToEnter to a list and sort it in entryOrder. For each state s in the list, first add s to the current configuration. Then if we are using late binding, and this is the first time we have entered s, initialize its data model. Then execute any onentry handlers. If s's initial state is being entered by default, execute any executable content in the initial transition. Finally, if s is a final state, generate relevant Done events. If we have reached a top-level final state, set running to false as a signal to stop processing.

procedure enterStates(enabledTransitions):

    statesToEnter = new OrderedSet()

    statesForDefaultEntry = new OrderedSet()

    computeEntrySet(enabledTransitions, statesToEnter, statesForDefaultEntry)

    for s in statesToEnter.toList().sort(entryOrder):

        configuration.add(s)

        statesToInvoke.add(s)

        if binding == "late" and s.isFirstEntry:

            initializeDataModel(datamodel.s,doc.s)

            s.isFirstEntry = false

        for content in s.onentry:

            executeContent(content)

        if statesForDefaultEntry.isMember(s):

            executeContent(s.initial.transition)

        if isFinalState(s):

            if isSCXMLElement(s.parent):

                running = false

            else:

                parent = s.parent

                grandparent = parent.parent

                internalQueue.enqueue(new Event("done.state." + parent.id, s.donedata))

                if isParallelState(grandparent):

                    if getChildStates(grandparent).every(isInFinalState):

                        internalQueue.enqueue(new Event("done.state." + grandparent.id))



procedurecomputeEntrySet(transitions, statesToEnter, statesForDefaultEntry)

Compute the complete set of states that will be entered as a result of taking 'transitions'. This value will be returned in 'statesToEnter' (which is modified by this procedure). Also place in 'statesForDefaultEntry' the set of all states whose default initial states were entered. First gather up all the target states in 'transitions'. Then add them and, for all that are not atomic states, add all of their (default) descendents until we reach one or more atomic states. Then add any ancestors that will be entered within the domain of the transition. (Ancestors outside of the domain of the transition will not have been exited.)

procedure computeEntrySet(transitions, statesToEnter, statesForDefaultEntry)

   for t in transitions:

        statesToEnter.union(getTargetStates(t.target))

    for s in statesToEnter:

        addDescendentStatesToEnter(s,statesToEnter,statesForDefaultEntry)

    for t in transitions:

        ancestor = getTransitionDomain(t)

        for s in getTargetStates(t.target)):

            addAncestorStatesToEnter(s, ancestor, statesToEnter, statesForDefaultEntry)

procedure addDescendentStatesToEnter(state,statesToEnter,statesForDefaultEntry)

The purpose of this procedure is to add to statesToEnter 'state' and any of its descendents that the state machine will end up entering when it enters 'state'. (N.B. If 'state' is a history pseudo-state, we dereference it and add the history value instead.) Note that this procedure permanently modifies both statesToEnter and statesForDefaultEntry.

First, If state is a history state then add either the history values associated with state or state's default target to statesToEnter. Then (since the history value may not be an immediate descendent of 'state's parent) add any ancestors between the history value and state's parent. Else (if state is not a history state), add state to statesToEnter. Then, if state is a compound state, add state to statesForDefaultEntry and recursively call addStatesToEnter on its default initial state(s). Then, since the default initial states may not be children of 'state', add any ancestors between the default initial states and 'state'. Otherwise, if state is a parallel state, recursively call addStatesToEnter on any of its child states that don't already have a descendent on statesToEnter.

procedure addDescendentStatesToEnter(state,statesToEnter,statesForDefaultEntry):

    if isHistoryState(state):

        if historyValue[state.id]:

            for s in historyValue[state.id]:

                addDescendentStatesToEnter(s,statesToEnter,statesForDefaultEntry)

                addAncestorStatesToEnter(s, state.parent, statesToEnter, statesForDefaultEntry)

        else:

            for t in state.transition:

                for s in getTargetStates(t.target):

                    addDescendentStatesToEnter(s,statesToEnter,statesForDefaultEntry)

                    addAncestorStatesToEnter(s, state.parent, statesToEnter, statesForDefaultEntry)

    else:

        statesToEnter.add(state)

        if isCompoundState(state):

            statesForDefaultEntry.add(state)

            for s in getTargetStates(state.initial):

                addDescendentStatesToEnter(s,statesToEnter,statesForDefaultEntry)

                addAncestorStatesToEnter(s, state, statesToEnter, statesForDefaultEntry)

        else:

            if isParallelState(state):

                for child in getChildStates(state):

                    if not statesToEnter.some(lambda s: isDescendant(s,child)):

                        addDescendentStatesToEnter(child,statesToEnter,statesForDefaultEntry)



procedureaddAncestorsStatesToEnter(state, ancestor, statesToEnter, statesForDefaultEntry)

Add to statesToEnter any ancestors of 'state' up to, but not including, 'ancestor' that must be entered in order to enter 'state'. If any of these ancestor states is a parallel state, we must fill in its descendents as well.

procedure addAncestorsToEnter(state, ancestor, statesToEnter, statesForDefaultEntry)

   for anc in getProperAncestors(state,ancestor):

       statesToEnter.add(anc)

       if isParallelState(anc):

           for child in getChildStates(anc):

               if not statesToEnter.some(lambda s: isDescendant(s,child)):

                   addStatesToEnter(child,statesToEnter,statesForDefaultEntry)

procedure isInFinalState(s)

Return true if s is a compound <state> and one of its children is an active <final> state (i.e. is a member of the current configuration), or if s is a <parallel> state and isInFinalState is true of all its children.

function isInFinalState(s):

    if isCompoundState(s):

        return getChildStates(s).some(lambda s: isFinalState(s) and configuration.isMember(s))

    elif isParallelState(s):

        return getChildStates(s).every(isInFinalState)

    else:

        return false

function getTransitionDomain(transition)

Return the compound state such that 1) all states that are exited or entered as a result of taking 'transition' are descendents of it 2) no descendent of it has this property.

function getTransitionDomain(t)

  tstates = getTargetStates(t.target)

  if not tstates

      return t.source

        elif t.type == "internal" and isCompoundState(t.source) and tstates.every(lambda s: isDescendant(s,t.source)):

      return t.source

  else:

      return findLCCA([t.source].append(tstates))

function findLCCA(stateList)

The Least Common Compound Ancestor is the <state> or <scxml> element s such that s is a proper ancestor of all states on stateList and no descendant of s has this property. Note that there is guaranteed to be such an element since the <scxml> wrapper element is a common ancestor of all states. Note also that since we are speaking of proper ancestor (parent or parent of a parent, etc.) the LCCA is never a member of stateList.

function findLCCA(stateList):

    for anc in getProperAncestors(stateList.head(),null).filter(isCompoundState):

        if stateList.tail().every(lambda s: isDescendant(s,anc)):

            return anc



function getProperAncestors(state1, state2)

If state2 is null, returns the set of all ancestors of state1 in ancestry order (state1's parent followed by the parent's parent, etc.). If state2 is non-null, returns in ancestry order the set of all ancestors of state1, up to but not including state2. (A "proper ancestor" of a state is its parent, or the parent's parent, or the parent's parent's parent, etc. If state2 is state1's parent, or equal to state1, or a descendent of state1, this returns the empty set.

function isDescendant(state1, state2)

Returns 'true' if state1 is a descendant of state2 (a child, or a child of a child, or a child of a child of a child, etc.) Otherwise returns 'false'.

function getChildStates(state1)

Returns a list containing all <state>, <final>, and <parallel> children of state1.


From: Gavin Kistner [mailto:phrogz@me.com]
Sent: Friday, March 08, 2013 10:57 AM
To: Jim Barnett
Cc: VBWG Public (www-voice@w3.org)
Subject: Re: more on preemption

I'd love to try implementing this (and other proposed changes to the algorithm) in a branch of my runtime and see how it fares in both my real application and test suite. However, with just a function definition and not the proposed call path(s) to the function I'm hesitant to implement what may not match what you are imagining.

Do you have a unified modified proposed algorithm that includes all proposed changes available somewhere?

--
(-, /\ \/ / /\/ (via phone)

On Mar 8, 2013, at 8:12 AM, Jim Barnett <Jim.Barnett@genesyslab.com<mailto: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