D Algorithm for SCXMLInterpretation
[This section is informative.]
This section contains an illustrative algorithm for theinterpretation of an SCXML document. It is intended as a guide forimplementers only. Implementations are free to implement SCXMLinterpreters in any way they choose.
Informal Semantics
The following definitions and highlevel principles andconstraint are intended to provide a background to the algorithm,and to serve as a guide for the proper understanding of it.
Preliminary definitions
- state
- An element of type <state>, <parallel>, or<final>.
- pseudo state
- An element of type <initial> or <history>.
- transition target
- A state, or an element of type <history>.
- atomic state
- A state of type <state> with no child states, or a stateof type <final>.
- compound state
- A state of type <state> with at least one childstate.
- configuration
- The maximal consistent set of states (including parallel andfinal states) that the machine is currently in. We note that if astate s is in the configuration c, it is always the case that theparent of s (if any) is also in c. Note, however, that<scxml> is not a(n explicit) member of theconfiguration.
- source state
- The source state of a transition is the state which containsthe transition.
- target state
- A target state of a transition is a state that the transitionis entering. Note that a transition can have zero or more targetstates.
- targetless transition
- A transition having zero target states.
- eventless transition
- A transition lacking the 'event' attribute.
- external event
- An SCXML event appearing in the external event queue. Suchevents are either sent by external sources or generated with the<send> element.
- internal event
- An event appearing in the internal event queue. Such events areeither raised automatically by the platform or generated with the<raise> or <send> elements.
- microstep
- A microstep involves the processing of a single transition (or,in the case of parallel states, a single set of transitions.) Amicrostep may change the current configuration, update the datamodel and/or generate new (internal and/or external) events. This,by causality, may in turn enable additional transitions which willbe handled in the next microstep in the sequence, and so on.
- macrostep
- A macrostep consists of a sequence (a chain) of microsteps, atthe end of which the state machine is in a stable state and readyto process an external event. Each external event causes an SCXMLstate machine to take exactly one macrostep. However, if theexternal event does not enable any transitions, no microstep willbe taken, and the corresponding macrostep will be empty.
Principles and Constraints
We state here some principles and constraints, on the level ofsemantics, that SCXML adheres to:
- Encapsulation
- An SCXML processor is apure event processor. The onlyway to get data into an SCXML state machine is to send externalevents to it. The only way to get data out is to receive eventsfrom it.
- Causality
- There shall be acausal justification of why eventsare (or are not) returned back to the environment, which can betraced back to the events provided by the system environment.
- Determinism
- An SCXML state machine which does not invoke any external eventprocessor must always react with the same behavior (i.e. the samesequence of output events) to a given sequence of input events(unless, of course, the state machine is explicitly programmed toexhibit an non-deterministic behavior). In particular, theavailability of the <parallel> element must not introduce anynon-determinism of the kind often associated with concurrency. Notethat observable determinism does not necessarily hold for statemachines that invoke other event processors.
- Completeness
- An SCXML interpreter must always treat an SCXML document ascompletely specifying the behavior of a state machine. Inparticular, SCXML is designed to use priorities (based on documentorder) to resolve situations which other state machine frameworkswould allow to remain under-specified (and thus non-deterministic,although in a different sense from the above).
- Run to completion
- SCXML adheres to a run to completion semantics in the sensethat an external event can only be processed when the processing ofthe previous external event has completed, i.e. when all microsteps(involving all triggered transitions) have been completelytaken.
- Termination
- A microstep always terminates. A macrostep may not. A macrostepthat does not terminate may be said to consist of an infinitelylong sequence of microsteps. This is currently allowed.
Algorithm
Note that the algorithm assumes a Lisp-like semantics in whichthe empty Set null is equivalent to boolean 'false' and all otherentities are equivalent to 'true'.
Datatypes
These are the abstract datatypes that are used in thealgorithm.
datatype Listfunction head() // Returns the head of the listfunction tail() // Returns the tail of the list (i.e., the rest of the list once the head is removed)function append(l) // Returns the list appended with lfunction filter(f) // Returns the list of elements that satisfy the predicate ffunction some(f) // Returns true if some element in the list satisfies the predicate f. Returns false for an empty list.function every(f) // Returns true if every element in the list satisfies the predicate f. Returns true for an empty list.The notation [...] is used as a list constructor, so that '[t]' denotes a list whose only member is the object t. datatype OrderedSetprocedure add(e) // Adds e to the set if it is not already a memberprocedure delete(e) // Deletes e from the setprocedure union(s) // Adds all members of s that are not already members of the set (s must also be an OrderedSet)function isMember(e) // Is e a member of set?function some(f) // Returns true if some element in the set satisfies the predicate f. Returns false for an empty set.function every(f) // Returns true if every element in the set satisfies the predicate f. Returns true for an empty set.function hasIntersection(s) // Returns true if this set and set s have at least one member in commonfunction isEmpty() // Is the set empty?procedure clear() // Remove all elements from the set (make it empty)function toList() // Converts the set to a list that reflects the order in which elements were originally added // In the case of sets created by intersection, the order of the first set (the one on which the method was called) is used // In the case of sets created by union, the members of the first set (the one on which union was called) retain their original ordering // while any members belonging to the second set only are placed after, retaining their ordering in their original set. datatype Queueprocedure enqueue(e) // Puts e last in the queuefunction dequeue() // Removes and returns first element in queuefunction isEmpty() // Is the queue empty?datatype BlockingQueueprocedure enqueue(e) // Puts e last in the queuefunction dequeue() // Removes and returns first element in queue, blocks if queue is emptydatatype HashTable // table[foo] returns the value associated with foo. table[foo] = bar sets the value associated with foo to be bar.
Global variables
The following variables are global from the point of view of thealgorithm. Their values will be set in the procedureinterpret().
global configurationglobal statesToInvokeglobal datamodelglobal internalQueueglobal externalQueueglobal historyValueglobal runningglobal binding
Predicates
The following binary predicates are used for determining theorder in which states are entered and exited.
entryOrder // Ancestors precede descendants, with document order being used to break ties (Note:since ancestors precede descendants, this is equivalent to document order.)exitOrder // Descendants precede ancestors, with reverse document order being used to break ties (Note: since descendants follow ancestors, this is equivalent to reverse document order.)
The following binary predicate is used to determine the order inwhich we examine transitions within a state.
documentOrder// The order in which the elements occurred in the original document.
Procedures and Functions
This section defines the procedures and functions that make upthe core of the SCXML interpreter. N.B. in the code below, thekeyword 'continue' has its traditional meaning in languages like C:break off the current iteration of the loop and proceed to the nextiteration.
procedure interpret(scxml,id)
The purpose of this procedure is to initialize the interpreterand to start processing.
In order to interpret an SCXML document, first (optionally)perform[xinclude] processing and(optionally) validate the document, throwing an exception ifvalidation fails. Then convert initial attributes to<initial> container children with transitions to the statespecified by the attribute. (This step is done purely to simplifythe statement of the algorithm and has no effect on the system'sbehavior. Such transitions will not contain any executablecontent). Initialize the global data structures, including the datamodel. If binding is set to 'early', initialize the data model.Then execute the global <script> element, if any. Finallycall enterStates on the initial configuration, set the globalrunning variable to true and start the interpreter's eventloop.
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 anexternal entity cancels processing. In either case 'running' willbe set to false (see EnterStates, below, for termination byentering a top-level final state.)
At the top of the loop, we have either just entered the statemachine, or we have just processed an external event. Eachiteration through the loop consists of four main steps: 1)Completethe macrostep by repeatedly taking any internally enabledtransitions, namely those that don't require an event or that aretriggered by an internal event. After each suchtransition/microstep, check to see if we have reached a finalstate. 2) When there are no more internally enabled transitionsavailable, the macrostep is done. Execute any <invoke> tagsfor states that we entered on the last iteration through the loop3) 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 anexternal event and then execute any transitions that it triggers.However special preliminary processing is applied to the event ifthe state has executed any <invoke> elements. First, if thisevent was generated by an invoked process, apply <finalize>processing to it. Secondly, if any <invoke> elements haveautoforwarding set, forward the event to them. These steps applybefore the transitions are taken.
This event loop thus enforces run-to-completion semantics, inwhich the system process an external event and then takes all the'follow-up' transitions that the processing has enabled beforelooking for another external event. For example, suppose that theexternal event queue contains events ext1 and ext2 and themachine is in state s1. If processing ext1 takes the machine to s2and generatesinternal event int1, and s2 contains atransition t triggered by int1, the system is guaranteed to take t,no matter what transitions s2 or other states have that would betriggered by ext2. Note that this is true even though ext2 wasalready in the external event queue when int1 was generated. Ineffect, the algorithm treats the processing of int1 as finishing upthe 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.sort(entryOrder): for inv in state.invoke.sort(documentOrder): 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()
procedureexitInterpreter()
The purpose of this procedure is to exit the current SCXMLprocess by exiting all active states. If the machine is in atop-level final state, a Done event is generated. (Note that inthis case, the final state will be the only active state.) Theimplementation of returnDoneEvent is platform-dependent, but ifthis session is the result of an <invoke> in another SCXMLsession, returnDoneEvent will cause the eventdone.invoke.<id> to be placed in the external event queue ofthat session, where <id> is the id generated in that sessionwhen the <invoke> was executed.
procedure exitInterpreter(): statesToExit = configuration.toList().sort(exitOrder) for s in statesToExit: for content in s.onexit.sort(documentOrder): executeContent(content) for inv in s.invoke: cancelInvoke(inv) configuration.delete(s) if isFinalState(s) and isScxmlElement(s.parent): returnDoneEvent(s.donedata)
functionselectEventlessTransitions()
This function selects all transitions that are enabled in thecurrent configuration that do not require an event trigger. Firstfind a transition with no 'event' attribute whose conditionevaluates totrue. If multiple matching transitionsare present, take the first in document order. If none are present,search in the state's ancestors in ancestry order until one isfound. As soon as such a transition is found, add it toenabledTransitions, and proceed to the next atomic state in theconfiguration. If no such transition is found in the state or itsancestors, proceed to the next state in the configuration. When allatomic states have been visited and transitions selected, filterthe set of enabled transitions, removing any that are preempted byother 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.sort(documentOrder): if not t.event and conditionMatch(t): enabledTransitions.add(t) break loop enabledTransitions = removeConflictingTransitions(enabledTransitions) return enabledTransitions
functionselectTransitions(event)
The purpose of the selectTransitions()procedure is to collectthe transitions that are enabled by this event in the currentconfiguration.
Create an empty set ofenabledTransitions. For eachatomic state , find a transition whose 'event' attribute matchesevent and whose condition evaluates totrue. If multiple matching transitions are present,take the first in document order. If none are present, search inthe state's ancestors in ancestry order until one is found. As soonas such a transition is found, add it to enabledTransitions, andproceed to the next atomic state in the configuration. If no suchtransition is found in the state or its ancestors, proceed to thenext state in the configuration. When all atomic states have beenvisited and transitions selected, filter out any preemptedtransitions 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.sort(documentOrder): if t.event and nameMatch(t.event, event.name) and conditionMatch(t): enabledTransitions.add(t) break loop enabledTransitions = removeConflictingTransitions(enabledTransitions) return enabledTransitions
functionremoveConflictingTransitions(enabledTransitions)
enabledTransitions will contain multiple transitions only if aparallel state is active. In that case, we may have one transitionselected for each of its children. These transitions may conflictwith each other in the sense that they have incompatible targetstates. Loosely speaking, transitions are compatible when each oneis contained within a single <state> child of the<parallel> element. Transitions that aren't contained withina single child force the state machine to leave the<parallel> ancestor (even if they reenter it later). Suchtransitions conflict with each other, and with transitions thatremain within a single <state> child, in that they may havetargets that cannot be simultaneously active. The test thattransitions have non-intersecting exit sets captures thisrequirement. (If the intersection is null, the source and targetsof the two transitions are contained in separate <state>descendants of <parallel>. If intersection is non-null, thenat least one of the transitions is exiting the <parallel>).When such a conflict occurs, then if the source state of one of thetransitions is a descendant of the source state of the other, weselect the transition in the descendant. Otherwise we prefer thetransition that was selected by the earlier state in document orderand discard the other transition. Note that targetless transitionshave empty exit sets and thus do not conflict with any othertransitions.
We start with a list of enabledTransitions and produce aconflict-free list of filteredTransitions. For each t1 inenabledTransitions, we test it against all t2 that are alreadyselected in filteredTransitions. If there is a conflict, then ift1's source state is a descendant of t2's source state, we prefert1 and say that it preempts t2 (so we we make a note to remove t2from filteredTransitions). Otherwise, we prefer t2 since it wasselected in an earlier state in document order, so we say that itpreempts t1. (There's no need to do anything in this case since t2is already in filteredTransitions. Furthermore, once one transitionpreempts t1, there is no need to test t1 against any othertransitions.) Finally, if t1 isn't preempted by any transition infilteredTransitions, remove any transitions that it preempts andadd 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 isDescendant(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
proceduremicrostep(enabledTransitions)
The purpose of the microstepprocedure is toprocess a single set of transitions. These may have been enabled byan external event, an internal event, or by the presence or absenceof certain values in the data model 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 beexited, then their actions must be executed, and finally theirtarget states entered.
If a single atomic state is active, then enabledTransitions willcontain only a single transition. If multiple states are active(i.e., we are in a parallel region), then there may be multipletransitions, one per active atomic state (though some states maynot select a transition.) In this case, the transitions are takenin the document order of the atomic states that selected them.
procedure microstep(enabledTransitions): exitStates(enabledTransitions) executeTransitionContent(enabledTransitions) enterStates(enabledTransitions)
procedureexitStates(enabledTransitions)
Compute the set of states to exit. Then remove all the states onstatesToExit from the set of states that will have invokeprocessing done at the start of the next macrostep. (Supposemacrostep M1 consists of microsteps m11 and m12. We may enter states in m11 and exit it in m12. We will add s to statesToInvoke inm11, and must remove it in m12. In the subsequent macrostep M2, wewill apply invoke processing to all states that were entered, andnot exited, in M1.) Then convert statesToExit to a list and sort itin 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 descendantsof s that are members in the current configuration, else set itsvalue to be the list of all immediate children of s that aremembers of the current configuration. Again for each state s in thelist, first execute any onexit handlers, then cancel any ongoinginvocations, and finally remove s from the currentconfiguration.
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.sort(documentOrder): executeContent(content) for inv in s.invoke: cancelInvoke(inv) configuration.delete(s)
procedurecomputeExitSet(enabledTransitions)
For each transition t in enabledTransitions, if t is targetlessthen do nothing, else compute the transition's domain. (This willbe the source state in the case of internal transitions) or theleast common compound ancestor state of the source state and targetstates of t (in the case of external transitions. Add to thestatesToExit set all states in the configuration that aredescendants of the domain.
function computeExitSet(transitions) statesToExit = new OrderedSet for t in transitions: if t.target: domain = getTransitionDomain(t) for s in configuration: if isDescendant(s,domain): statesToExit.add(s) return statesToExit
procedureexecuteTransitionContent(enabledTransitions)
For each transition in the list ofenabledTransitions, execute its executablecontent.
procedure executeTransitionContent(enabledTransitions): for t in enabledTransitions: executeContent(t)
procedureenterStates(enabledTransitions)
First, compute the list of all the states that will be enteredas a result of taking the transitions in enabledTransitions. Addthem to statesToInvoke so that invoke processing can be done at thestart of the next macrostep. Convert statesToEnter to a list andsort it in entryOrder. For each state s in the list, first add s tothe current configuration. Then if we are using late binding, andthis is the first time we have entered s, initialize its datamodel. Then execute any onentry handlers. If s's initial state isbeing entered by default, execute any executable content in theinitial transition. If a history state in s was the target of atransition, and s has not been entered before, execute the contentinside the history state's default transition. Finally, if s is afinal state, generate relevant Done events. If we have reached atop-level final state, set running to false as a signal to stopprocessing.
procedure enterStates(enabledTransitions): statesToEnter = new OrderedSet() statesForDefaultEntry = new OrderedSet() // initialize the temporary table for default content in history states defaultHistoryContent = new HashTable() computeEntrySet(enabledTransitions, statesToEnter, statesForDefaultEntry, defaultHistoryContent) 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.sort(documentOrder): executeContent(content) if statesForDefaultEntry.isMember(s): executeContent(s.initial.transition) if defaultHistoryContent[s.id]: executeContent(defaultHistoryContent[s.id]) 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,defaultHistoryContent)
Compute the complete set of states that will be entered as aresult of taking 'transitions'. This value will be returned in'statesToEnter' (which is modified by this procedure). Also placein 'statesForDefaultEntry' the set of all states whose defaultinitial states were entered. First gather up all the target statesin 'transitions'. Then add them and, for all that are not atomicstates, add all of their (default) descendants until we reach oneor more atomic states. Then add any ancestors that will be enteredwithin the domain of the transition. (Ancestors outside of thedomain of the transition will not have been exited.)
procedure computeEntrySet(transitions, statesToEnter, statesForDefaultEntry, defaultHistoryContent) for t in transitions: for s in t.target: addDescendantStatesToEnter(s,statesToEnter,statesForDefaultEntry, defaultHistoryContent) ancestor = getTransitionDomain(t) for s in getEffectiveTargetStates(t)): addAncestorStatesToEnter(s, ancestor, statesToEnter, statesForDefaultEntry, defaultHistoryContent)
procedureaddDescendantStatesToEnter(state,statesToEnter,statesForDefaultEntry,defaultHistoryContent)
The purpose of this procedure is to add to statesToEnter 'state'and any of its descendants that the state machine will end upentering when it enters 'state'. (N.B. If 'state' is a historypseudo-state, we dereference it and add the history value instead.)Note that this procedure permanently modifies both statesToEnterand statesForDefaultEntry.
First, If state is a history state then add either the historyvalues associated with state or state's default target tostatesToEnter. Then (since the history value may not be animmediate descendant of 'state's parent) add any ancestors betweenthe history value and state's parent. Else (if state is not ahistory state), add state to statesToEnter. Then if state is acompound state, add state to statesForDefaultEntry and recursivelycall addStatesToEnter on its default initial state(s). Then, sincethe default initial states may not be children of 'state', add anyancestors between the default initial states and 'state'.Otherwise, if state is a parallel state, recursively calladdStatesToEnter on any of its child states that don't already havea descendant on statesToEnter.
procedure addDescendantStatesToEnter(state,statesToEnter,statesForDefaultEntry, defaultHistoryContent): if isHistoryState(state): if historyValue[state.id]: for s in historyValue[state.id]: addDescendantStatesToEnter(s,statesToEnter,statesForDefaultEntry, defaultHistoryContent) for s in historyValue[state.id]: addAncestorStatesToEnter(s, state.parent, statesToEnter, statesForDefaultEntry, defaultHistoryContent) else: defaultHistoryContent[state.parent.id] = state.transition.content for s in state.transition.target: addDescendantStatesToEnter(s,statesToEnter,statesForDefaultEntry, defaultHistoryContent) for s in state.transition.target: addAncestorStatesToEnter(s, state.parent, statesToEnter, statesForDefaultEntry, defaultHistoryContent) else: statesToEnter.add(state) if isCompoundState(state): statesForDefaultEntry.add(state) for s in state.initial.transition.target: addDescendantStatesToEnter(s,statesToEnter,statesForDefaultEntry, defaultHistoryContent) for s in state.initial.transition.target: addAncestorStatesToEnter(s, state, statesToEnter, statesForDefaultEntry, defaultHistoryContent) else: if isParallelState(state): for child in getChildStates(state): if not statesToEnter.some(lambda s: isDescendant(s,child)): addDescendantStatesToEnter(child,statesToEnter,statesForDefaultEntry, defaultHistoryContent)
procedureaddAncestorStatesToEnter(state, ancestor, statesToEnter,statesForDefaultEntry, defaultHistoryContent)
Add to statesToEnter any ancestors of 'state' up to, but notincluding, 'ancestor' that must be entered in order to enter'state'. If any of these ancestor states is a parallel state, wemust fill in its descendants as well.
procedure addAncestorStatesToEnter(state, ancestor, statesToEnter, statesForDefaultEntry, defaultHistoryContent) 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)): addDescendantStatesToEnter(child,statesToEnter,statesForDefaultEntry, defaultHistoryContent)
procedureisInFinalState(s)
Return true if s is a compound <state> and one of itschildren is an active <final> state (i.e. is a member of thecurrent configuration), or if s is a <parallel> state andisInFinalState 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
functiongetTransitionDomain(transition)
Return the compound state such that 1) all states that areexited or entered as a result of taking 'transition' aredescendants of it 2) no descendant of it has this property.
function getTransitionDomain(t) tstates = getEffectiveTargetStates(t) if not tstates: return null 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)
TheLeast Common Compound Ancestoris the <state> or <scxml> element s such that s is aproper ancestor of all states on stateList and no descendant of shas this property. Note that there is guaranteed to be such anelement since the <scxml> wrapper element is a commonancestor of all states. Note also that since we are speaking ofproper ancestor (parent or parent of a parent, etc.) the LCCA isnever a member of stateList.
function findLCCA(stateList): for anc in getProperAncestors(stateList.head(),null).filter(isCompoundStateOrScxmlElement): if stateList.tail().every(lambda s: isDescendant(s,anc)): return anc
functiongetEffectiveTargetStates(transition)
Returns the states that will be the target when 'transition' istaken, dereferencing any history states.
function getEffectiveTargetStates(transition) targets = new OrderedSet() for s in transition.target if isHistoryState(s): if historyValue[s.id]: targets.union(historyValue[s.id]) else: targets.union(getEffectiveTargetStates(s.transition)) else: targets.add(s) return targets
functiongetProperAncestors(state1, state2)
If state2 is null, returns the set of all ancestors of state1 inancestry order (state1's parent followed by the parent's parent,etc. up to an including the <scxml> element). If state2 isnon-null, returns in ancestry order the set of all ancestors ofstate1, up to but not including state2. (A "proper ancestor" of astate is its parent, or the parent's parent, or the parent'sparent's parent, etc.))If state2 is state1's parent, or equal tostate1, or a descendant of state1, this returns the empty set.
function isDescendant(state1,state2)
Returns 'true' if state1 is a descendant of state2 (a child, ora child of a child, or a child of a child of a child, etc.)Otherwise returns 'false'.
functiongetChildStates(state1)
Returns a list containing all <state>, <final>, and<parallel> children of state1.