C B Algorithm for
SCXML Interpretation
This section presents a normative algorithm for the
interpretation of an SCXML docment.
document. Implementations are free to
implement SCXML intepreters interpreters in any way they choose, but they must
behave as if they were using the algorithm defined
here.
N.B.: in the following algorithm, we
define The fact that SCXML implements a
variant of the source state
Statechart formalism does not as such
determine a semantics for SCXML. Many different Statechart variants
have been proposed, each with its own semantics. This section
presents an informal semantics of SCXML
documents, as well as a transition to
be the state normative algorithm
for the transition is leaving
interpretation of SCXML documents.
Informal
Semantics
The following definitions and
the target state highlevel principles and constraint are intended to
provide a background to be the
one it is entering. Furthermore,
<state>, <parallel>, <history>
<final> normative
algorithm, and <scxml> are all
considered to be states. (Note that
they all can be targets serve as a
guide for the proper understanding of transitions.) it.
C.1
Initialization Phase Preliminary
definitions
Load and parse the SCXML
- state
machine and any
included
- An element of type <state>,
<parallel>, <final> or <scxml>.
- pseudo state
machine documents. Instantiate the data
model, loading any external data variables and then updating the
model
- 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
any data passed in no child states, or a state of type
<final>.
- compound state
- A state of type <state> with at
least one child state, or a state of type <scxml>.
- start state
- A dummy state equipped with a transition
which when triggered by the
invoking
context. Initiate 2 different currently empty FIFO
Run event queues:
one for internal events and one for external events. Throughout
processing, any events received from external sources are
added leads to the external event queue. Create initial state(s). Added by the interpreter with an
(initally empty) list id guaranteed to be unique within the statemachine.
The only role of ActiveStates. Create
an array associating invocations with the start state is to simplify the algorithm.
- configuration
- The maximal consistent set of
states (including parallel and final
states) that
invoked them. Create a two
dimensional array to hold DataModel snapshots for the
<anchor> element. Create an
activeTransitions list containing machine is currently in. We note that if a
single transition whose source
state s is in the <scxml>
element and whose target configuration
c, it is always the machines 'initialState'. Goto the Enter State Phase. //
Global Data Structures: environment env; // represents the data
passed in from the environment, the URL of the script, etc. state
SCXML; // structure representing the parsed state machine
list<state> ActiveStates; //list of currently active states
queue<event> InternalEvents; //FIFO event queue
queue<event> ExternalEvents; //FIFO event queue datamodel
DataModel; // the data model. Details will depend on the model
chosen stateID InvokeIDArray[]; //array associating ids of
invocations with the ids of states that executed the invocations.
invocationID InvokeStateArray[];//array associating state ids with
the ids of currently active invocations that // they have executed.
dataValues DataSnapshots[][];//array associating tuple of state ID
and anchor type with a subtree of the DataModel. //Data Passing
Structures - the following variables are used to pass //data
between phases and could be replaced by parameters
list<transition> activeTransitions;//list of transitions to
take list <state> newlyEnteredAtomicStates;// list of states
entered as a result of the most recent set of transitions event
currentEvent;// the event that triggered activeTransitions. SCXML =
loadAndParseStateMachine(env); // load the state machine DataModel
= buildDataModel(env, SCXML);//initialize data model
activeTransitions = new List(new Transition(source =
getAttribute(SCXML, 'id')), target = getAttribute(SCXML,
'initialState')); goto Enter_State_Phase; C.2 Immediately Enabled
Transitions Phase Call SelectTransitions with Null event. If any
transitions are found, set ActiveTransitions and goto
case that the Execute Transitions
Phase. Otherwise, see if there parent
of s (if any) is an event on the
internal or external event queues also in
c. Note, however, that triggers <scxml> is
not a(n explicit) member of the configuration.
- source state
- The source state of a
transition. If there is, set activeTransitions and
goto transition is the
Execute Transitions Phase. Otherwise there
are no immediately enabled transitions, so goto atomic state from which the Invoke Phase. label
Immediately_Enabled_Transitions_Phase; currentEvent = NULL;
selectedTransitions = SelectTransitions(NULL); if
(!empty(selectedTransitions)){ goto Execute_Transitions_Phase;}
while (!empty(InternalEvents) { currentEvent = pop(InternalEvents);
activeTransitions = SelectTransitions(currentEvent); if
(!empty(activeTransitions)) { goto Execute_Transitions_Phase;} } //
while (!empty(ExternalEvents)) { currentEvent =
pop(ExternalEvents); activeTransitions =
SelectTransitions(currentEvent); if (!empty(activeTransitions)) {
goto Execute_Transitions_Phase; } } // //if we get here, there are
no immediately enabled transitions goto Invoke_Phase; C.3 Invoke
Phase For transition is
leaving.
- target state
in newlyEnteredAtomicStates,
execute
- A target state of a transition is a state
that the
invoke element if any. When
all newlyEnteredAtomicStates transition
is entering. Note that a transition can have been visited, goto the Wait External Event Phase. label
Invoke_Phase for(state in newlyEnteredAtomicStates){ if
(getChild(state, 'invoke') != NULL) { invokeID =
executeInvoke(getChild(state, 'invoke')); // record that state
triggered this invocation. This will be used later for
<finalize> processing. InvokeIDArray[invokeId] =
getID(state); // record that this invocation is active in this
state; InvokeStateArray[getID(state)] = invokeID; } // } // goto
Wait_External_Event_Phase; C.4 Wait External Event Phase .
Clear zero or more target
states.
- targetless
transition
- A transition having zero target
states.
- eventless
transition
- A transition lacking the
newlyActiveAtomicStates list. Wait until
an 'event' attribute.
- external event
appears on
- An SCXML event appearing
in the external event
queue. When one appears, remove it from
See section ? for details.
- internal event
- An event appearing
in the internal event queue. If
it It's exact representation is
implementation dependent, but a
return simple
string would work.
- macrostep
- An external event
from causes an
<invoke>, pass it to the
<finalize> handler (if any) of the SCXML state that invoked it.
Then call SelectTransitions on it. If any transitions are found,
goto the Execute Transitions Phase. Otherwise return
machine to the
Wait External Event Phase. label Wait_External_Event_Phase; local
id invokeID; newlyActiveAtomicStates = NULL; wait
(!empty(ExternalEvents)) { // following code executes once
ExternalEvents is not empty currentEvent = pop(ExternalEvents); //
if this is an event generated by an <invoke>, execute the
<finalize> code invokeID = getAttribute(currentEvent,
'invokeID'); if (invokeID != NULL) { processFinalize(currentEvent,
InvokeArray[invokeID], DataModel); // if this is a Done event,
clean up the InvokeArrays; if(getAttribute(currentEvent, 'name'))
== "invokeID.done") { deleteArrayElement(InvokeStateArray,
InvokeIDArray[invokeID]); deleteArrayElement(InvokeIDArray,
invokeID); }// }// activeTransitions =
SelectTransitions(currentEvent); if (!empty(activeTransitions)) {
goto Execute_Transitions_Phase; } else { goto
Wait_External_Event_Phase; } } // C.5 Execute Transitions Phase
Note: in this phase we treat all transitions as take exactly one macrostep. A macrostep consists of a
sequence (a chain) of microsteps. However, if the external event does not enable any 'anchor' attributes have been used to set
transitions, no microstep will be taken,
and the corresponding 'target' in
macrostep will be empty.
- microstep
- If an external event enables one or
(in the
transition. See Section C.7
Semantics case of
<anchor> for parallel states) more transitions, a microstep is taken,
involving the explanation
processing of this interpretation. The Execute Transitions Phase
consists each of four sub-phases. First we resolve conflicts among
transitions. Then we exit all states that the transitions leave, executing their <onexit>
handlers. Then we execute enabled
transitions. This microstep may change the executable content included in the transitions. Then we enter all states that
current configuration, update the
datamodel and/or generate
new (internal and/or external) events. This, by causality,
may in turn enable additional transitions enter, executing their <onentry> handlers. Note
that there which will be
multiple transitions on activeTransitions
only if handled in the state machine
is next microstep in
a parallel region. In all other cases,
activeTransitions will contain only a single item and
the Remove Conflicting Transitions Phase may
be skipped. sequence, and so
on.
C.5.1
Remove Conflicting Transitions Phase Principles and Constraints
Two transitions conflict if
We state here some principles and
constraints, on the sets
level of states semantics, that
they exit have SCXML adheres to:
- Encapsulation
- An SCXML processor is a
non-null intersection. To resolve conflicts, we first
sort the transition list in document order. Then we pick the first
transition pure event
processor .The only way to get
data into an SCXML statemachine is to send external events to it.
The only way to get data out is to receive events from
it.
- Causality
- There shall be a causal justification of
why events are (or are not) returned back to the
ActiveTransitions list and form its conflict set by
finding all transitions that conflict with it (there may not
environment, which can be any). We then resolve traced
back to the (possible) conflict
events provided by selecting one member of the conflict set. We then remove all members of
system environment.
- Determinism
- An SCXML statemachine which does not
invoke any external event processor must always react with
the
conflict from consideration and iterate
on same behavior (i.e. the
rest same
sequence of the ActiveTransitions list
until all members have been tested for conflicts. The criterion for
selection within a conflict set is first scope and then document
order. That is, we chose transition T1 over T2 if a) T1's source
state is output events) to a
descendant given
sequence of T2's or b) if neither
transition's source state is a descendant input events (unless, of course, the other's and T1
precedes T2 in document order. label Execute_Transitions_Phase;
label Remove_Conflicting_Transitions_Phase; list<transition>
transitionsToTest = sort(activeTransitions, 'documentOrder'); //we
will rebuild the activeTransitions list as we examine
transitionsToTest activeTransitions = NULL;
while(transitionsToTest){ transition currentTr =
first(transitionsToTest); list<transition> conflictSet = new
list(currentTr); for restTrans in rest(transitionsToTest) { if
(intersection(getStatesToExit(restTrans),
getStatesToExit(currentTr) != NULL) { push(restTrans,
conflictSet);} }// //now choose one member from the conflict set.
Note that this is trivial for sets of size one. for trans in
sort(conflictSet, 'documentOrder') { boolean narrowScope = true;
for otherTrans in remove(trans, conflictSet) { if
(isDescendant(getSourceState(trans), getSourceState(otherTrans))) {
narrowScope = false; break; }// }// //this is the first transition
in document order such that there is no more narrowly scoped
transition // in this conflict set. if (narrowScope) { push(trans,
activeTransitions); break; // }// //now remove all transitions in
conflictSet from transitionsToTest. transitionsToTest gets smaller
// on each iteration so the while loop is guaranteed to terminate.
for trans in conflictSet { delete(trans, transitionsToTest); } }//
activeTransitions = sort(activeTransitions, 'documentOrder'); goto
Exit_State_Phase; C.5.2 Exit State Phase Create a statesToExit
List. For each transition T in activeTransitions, if T has no
target state, go on statemachine is
explicitly programmed to exhibit an
non-deterministic behavior). In particular, the next transition. Otherwise, let LCA be the least common
ancestor state of the target states availability of T and
the active descendents <parallel> element must not introduce any
non-determinism of the source
kind often associated with concurrency. Note
that observable determinism does not necessarily hold for
state of T. Add to the statesToExit list of
all active states machines that
are descendents of LCA. Now sort
invoke other event processors.
- Completeness
- An SCXML interpreter must always treat an
SCXML document as completely specifying the
list so that
state S1 proceeds S2 if 1) S1 is a descendant behavior of S2 or 2) S1
preceeds S2 in document order. Finally, for each state S
a statemachine. In particular, SCXML is
designed to use priorities (based on document order) to resolve situations which other
statemachine frameworks would allow to remain under-specified (and
thus non-deterministic, although in a different sense
from the list, 1) if S has
above).
- Run to
completion
- SCXML adheres to a
shallow history state, sets its value run to completion
semantics in
the sense that an external event can
only be processed when the
list processing of the previous
external event has completed, i.e. when all immediate children of S microsteps (involving all triggered transitions) have
been completely taken.
- Termination
- A microstep always terminates. A
macrostep may not. A macrostep that
are
active 2) if S has a deep history state, set its value to
does not terminate may be the list said to
consist of all atomic descendants
an infinitely long sequence of
S that microsteps. This is currently allowed.
Algorithm
This section presents a normative
algorithm for the interpretation of SCXML documents.
Implementations are active 3)if S has
an ongoing invocation,cancel it, 4) perform S's <onexit>
actions 4) remove S from free to
implement SCXML interpreters in any way they
choose, but they must behave as if they were
using the ActiveStates list.
algorithm defined here.
Datatypes
Goto Execute Content Phase.
These are the abstract datatypes that are
used in the algorithm.
label Exit_State_Phase;
list<state> statesToExit;
for trans in activeTransitions {
statesToExit = append(statesToExit, getStatesToExit(trans)); }
statesToExit = sort(statesToExit, 'exitOrder');
for state in statesToExit {
list<state> activeChildren;
list<state> activeAtomicDescendents;
// record currently active descendents for use as possible history values
for activeState in ActiveStates {
if(getParent(activeState) == state) {
push(activeState activeChildren);}
if(isAtomic(activeState) && isDescendent(activeState, state)) {
push(activeState activeAtomicDescendents); }
//
// update history states
for histState in getHistoryStates(state) {
if(getAttribute(histState, 'type') == 'deep') {
setHistoryValue(histState, activeChildren);
} else (setHistoryValue(histState, activeAtomicDescendents); }
}//
datatype List
function head() // Returns the head of the list function tail() // Returns the tail of the list function append(l) // Returns the list appended with l function filter(f) // Returns the list of elements that satisfy the predicate f function some(f) // Returns true if some element in the list satisfies the predicate f function every(f) // Returns true if every element in the list satisfies the predicate f
// now the executable content
if(getElement(state, 'onexit')) {
executeContent(getChildren(getElement(state, 'onexit')) currentEvent);}
// cancel any ongoing invocation
if(InvokeStateArray[getID(state)] != NULL; {
//cancel ongoing invocation and clean up Invoke Arrays;
cancelInvoke(InvokeStateArray[getID(state)];
deleteArrayElement(InvokeIDArray, InvokeStateArray[getID(state)]);
deleteArrayElement(InvokeStateArray, getID(state);
}//
// make state inactive
delete(state, ActiveStates);
}//
datatype Set
procedure add(e) // Adds e to the set procedure delete(e) // Deletes e from the set function member(e) // Is e a member of set? function isEmpty() // Is the set empty? function toList() // Converts the set to a list
goto Execute_Content_Phase;
datatype Queue
procedure enqueue(e) // Puts e last in the queue function dequeue() // Removes and returns first element in queue function isEmpty() // Is the queue empty?
datatype BlockingQueue
procedure enqueue(e) // Puts e last in the queue function dequeue() // Removes and returns first element in queue, blocks if queue is empty
C.5.3 Execute Content Phase Global variables
For each transition The following variables are global from the point of
view of the algorithm. Their values will be set in the
activeTransitions list, execute its
executable content. Then goto Enter State Phase.
procedure
interpret() .
label Execute_Content_Phase;
for transition in activeTransitions {
executeContent(getChildren(transition), currentEvent);}
global datamodel;
global configuration;
global internalQueue;
global externalQueue;
global historyValue;
global continue
Procedures
and Functions
This section defines the procedures and
functions that make up the core of the SCXML interpreter.
C.5.4
Enter State Phase procedure interpret(scxml,id)
Create a Target State list,
The purpose of this procedure is to
initialize the interpreter. It is called with a States parsed representation
of an SCXML document.
In order to Enter List, interpret an
SCXML document, first perform inplace expansions of states by
including SCXML source referenced by URIs (see 3.11 Referencing External
Files ) and a Default Entry List. Also create a Rollback array
associating stateIDs with anchors change initial attributes to be rolled back. For each transition T in
ActiveTransitions, if T has no target state, go on
initial container children with empty
transitions to the next transition. If
T was originally specified by an anchor element, add T's
target state from the attribute. Then
(optionally) validate the resulting SCXML, and throw an exception if validation fails. Create an empty
configuration complete with a new populated instance of the
anchor name data
model and a execute the global scripts. Create the two queues
to handle events and set the
Rollback array. Set Target State list
global continue variable to be true. Call
executeTransitionContent on the list of
T's target states. If any member of Target States initial transition that is a history state, replace it on Target States with its
history value. For each state in Target States, child of scxml. Then call addDefaultStatesToEnter enterState on state,
the least common ancestor initial transition. Finally, start the interpreter's
event loop.
procedure interpret(doc):
expandScxmlSource(doc)
if (!valid(doc)) {fail with error}
configuration = new Set()
datamodel = new Datamodel(doc)
executeGlobalScriptElements(doc)
internalQueue = new Queue()
externalQueue = new BlockingQueue()
continue = true
executeTransitionContent([doc.initial.transition])
enterState([doc.initial.transition])
startEventLoop()
procedure startEventLoop()
The interpreter's event loop has two main
parts. First it selects enabled transitions. Then it executes the
selected transitions. It stays in a continuous loop of
T's source selecting and target
states, executing transitions
until the States interpreter is finished. The details of how it selects
transitions are specified to Enter
List achieve the desired run to
completion semantics and final
processing.
The interpreter's event loop
enforces the Default Entry list. (Note
that run to completion semantics by
only breaking at the end of handling all of the microsteps
associated with any given event. It accomplishes this
modifies by each
and every time through the states
loop enforcing an ordering on which
transitions are selected. First the interpreter checks to
Enter see if
there are any eventless transitions that need to be taken. If there
are any then they are executed by the microstep being
performed and the Default Entry List.)
Sort next iteration of the
States loop
continues. If there were no eventless transitions to
Enter list so that S1 preceeds S2
execute then the internal event queue is
checked and if 1) S1 there is an ancestor of S2
or 2) S1 preceeds S2 in document order. Call EnterState
internal event then transitions are selected
based on each state S this event. If there were transitions selected
based on this event then these are
executed by the States to Enter List
along with the RollBack List microstep
being performed and the Default Entry
List. Finally next iteration of the
loop continues. If there were no transitions enabled then we
check if we have reached a top-level final state,
exit state by checking if continue is
true. If continue is false the interpreter. Otherwise goto statemachine is done and we break out of the
Immediately Enabled Transitions phase.
startEventLoop. If continue is true then we
grab an external event from the external event queue, blocking if
necessary. Once we have the external event we perform the
appropriate data model manipulation related to finalizing the event
and modifying the data model with the event information. Finally we
select transitions that were enabled by this event. If there were
transitions enabled by the event we execute them by the microstep
function and start the next iteration of the loop. If there were no
transitions selected by the external event we also start the next
iteration of the loop.
list <state> targetStates;
list <state> statesToEnter;
<state> statesToRollback[];
list <state> statesForDefaultEntry;
for trans in activeTransitions {
if (getTargetStates(trans) != NULL) {
if (getAttribute(trans, 'anchor')){
// transitions with anchors always have a single target
statesToRollback[first(getTargetStates(trans)] = getAttribute(trans, 'anchor');}
targetStates = getTargetStates(trans);
for state in targetStates {
if(isHistoryState(state)) {
delete(state, targetStates);
if(getHistoryValue(state) != NULL) {
targetStates = append(targetStates, getHistoryValue(state));
// if state has no history value, use default history value
} else {
targetStates = append(targetStates, getHistoryDefault(state));
}//
}//
}//
state LCA = findLeastCommonAncestor(add(getSourceState(trans), getTargetStates(trans));
for state in targetStates {
addDefaultStatesToEnter(state, LCA, statesToEnterList, statesForDefaultEntry);}
}//
statesToEnter = sort(statesToEnter, 'entryOrder');
procedure procedure startEventLoop():
while (true):
enabledTransitions = selectTransitions(null)
if (enabledTransitions.isEmpty() && !internalQueue.isEmpty()):
enabledTransitions = selectTransitions(internalQueue.dequeue())
if (enabledTransitions.isEmpty()enabledTransitions.isEmpty() && !internalQueue.isEmpty(): if (continue):
ee = externalQueue.dequeue()
datamodel.assignID("event",ee)
enabledTransitions = selectTransitions(ee)
else: break if (!enabledTransitions.isEmpty()):
microstep(enabledTransitions.toList())
for state in statesToEnter {
EnterState(state, statesToRollback, statesForDefaultEntry, currentEvent);}
for state in ActiveStates { if
(isFinal(state) && getParent(state>) == SCXML){
exitInterpreter();} }// goto
Immediately_Enabled_Transistions_Phase; procedure exitInterpreter()
The purpose of this
procedure is to exit the current SCXML process by halting the
interpreter's event loop. It does so by setting the global
variable continue
to false C.6 Utility
Functions
procedure exitInterpreter():
continue = false
C.6.1
SelectTransitions( event ) function selectTransitions(event)
The purpose of the selectTransitions() procedure is to
collect the transitions that are enabled in a given
configuration.
Create an empty set of
enabledTransitions . For
each atomic state in ActiveStates in
document order, the
configuration, first test if the state has been preempted by a
transition that has already been selected and that will cause the
state to be exited when the transition is taken. If the state has
not been preempted, find a transition whose "event" 'event'
attribute is either empty or matches event and whose
condition evaluates to true.
trueevent is nullin
document order. If none are present, search in the
state's ancestors in ancestory oder order until one
is found. As soon as such a transition is found, add it to
the back of the ActiveTransitions list,
enabledTransitions , and
proceed to the next atomic state
in ActiveStates.
the configuration. If no such
transition is found in the state or its ancestors,
proceed to the next state in ActiveStates. the
configuration. When all atomic states have been visited and
transitions selected, return the list set of
selected enabled transitions.
transition_list SelectTransitions(event) {
list <state> atomicStates = ();
list <transition> transitions = ();
for state in ActiveStates {
if (isAtomic(state)) {
push(state, atomicStates);
}
}//
atomicStates = sort(atomicStates, 'documentOrder');
for state in atomicStates {
transition tr = findTransitionMatchingEvent(event, state);
if (tr != NULL && !member(tr, transitions)) {
push(tr, transitions);
}//
}//
return transitions;
}
transition findTransitionMatchingEvent(event, state) {
transition matchingTransition = NULL;
for trans in getTransitions(state) {
if ((event == NULL || nameMatch(event, transition))
&&
conditionMatch(event, transition)) {
return trans; // return as soon as we find a transition that matches
}
}//
// if no transition found in this state, check parent recursively
if (getParent(state) !== NULL) {
return findTransitionMatchingEvent(event, getParent(state);
} else { return NULL; }
}
function selectTransitions(event):
enabledTransitions = new Set()
atomicStates = configuration.toList().filter(isAtomicState)
for state in atomicStates:
if !(isPreempted(s, enabledTransitions)):
loop: for s in [state].append(getProperAncestors(state,null)):
for t in s.transition: if ((event == null && t.attribute('event') == null && conditionMatch(t)) ||
(event != null && nameMatch(event,t) && conditionMatch(t))):
enabledTransitions.add(t)
break loop return enabledTransitions
C.6.2 findStatesToExit( trans ) procedure isPreempted?(s transitionList)
Return true if a list transition T in
transitionList exits an ancestor of all
states state s. In this case, taking T
will pull the state machine out of s and we say that
it preempts the selection of a transition
from s. Such preemption will be existed
when trans occur only if s is
taken. These are all a descendant of a parallel region and T exits that
region. If we did not do this preemption check, we could end up in
an illegal configuration, namely one in which there were
multiple active states that are
descendents were not all descendants of
a common parallel ancestor.
procedureisPreempted?(s transitionList):
boolean preempted = false
for t in transitionList:
if (t.attribute('target') != null):
LCA = findLCA([t.parent()].append(getTargetStates(t)))
if (isDescendant(s,LCA)):
preempted = true
break;
return preempted
procedure microstep(enabledTransitions)
The purpose of the microstep
procedure is to process the set of transitions 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.
procedure microstep(enabledTransitions):
exitStates(enabledTransitions)
executeTransitionContent(enabledTransitions)
enterStates(enabledTransitions)
procedure exitStates(enabledTransitions)
Create an empty statesToExit set. For
each transition t
in enabledTransitions ,if t
is targetless then do nothing, else let
LCA be the least common ancestor state of the source state and target states of trans. t
.Add to the statesToExit set all
states in
the configuration that are descendants
of LCA .Convert the statesToExit set 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.
list<state> getStatesToExit(transition trans) {
list<state> transitionStates = NULL;
list<state> statesToExit = NULL;
//if trans has no target state, no states will be exited
if (getTargetStates(trans) != NULL) {
push (getSourceState(trans), getTargetStates(trans));
state LCA = getLeastCommonAncestor(transitionStates);
for state in ActiveStates {
if(isDescendant(state, LCA)) {
push(state statesToExit); }
}//
}//
return statesToExit;
}
procedure exitStates(enabledTransitions):
statesToExit = new Set()
for t in enabledTransitions: if (t.attribute('target') != null):
LCA = findLCA([t.parent()].append(getTargetStates(t)))
for s in configuration.toList(): if (isDescendant(s,LCA)):
statesToExit.add(s)
statesToExit = statesToExit.toList().sort(exitOrder)
for s in statesToExit: for h in s.history:
f = (h.attribute('type') == "deep") ?
lambda(s0): isAtomicState(s0) && isDescendant(s0,s) :
lambda(s0): s0.parent() == s
historyValue[h.attribute('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)
C.6.3 findLeastCommonAncestor( state-list
) procedure
executeTransitionContent(enabledTransitions)
Return For
each transition in
the state S such that 1) S is
list of enabledTransitions ,execute its executable content.
procedure executeTransitions(enabledTransitions): for t in enabledTransitions:
executeContent(t)
procedure enterStates(enabledTransitions)
Create an empty statesToEnter set,
and an empty statesForDefaultEntry set. For each transition t in enabledTransitions ,if t
is targetless then do nothing, else let
LCA be the least common ancestor all states on state-list state of the source state and 2) no descendent target
states of S has this property. Note
that there t
.For each target state
s ,if s is
guaranteed to be such a history state since
then add either the <scxml> element (which we treat as
history values associated with
s or s
's default target to statesToEnter .Else
(if s is not a history state), add s to
statesToEnter .Convert statesToEnter to a list and sort it
in enterOrder .
For each state here) s
in the list, first add s to the current
configuration, then invoke any external processes specified
in <invoke> elements and assign their
sessionID s to the datamodel, keyed on the <invoke>
element's ID, then execute any onentry handlers, and finally,
if s is a
common ancestor of all states.
final state, generate relevant
Done events. If we have reached a top-level final state, exit
the interpreter.
state findLeastCommonAncestor(state-list) {
state LCA;
if (isNull(state-list)) {
LCA = SCXML;
} else {
LCA = first(state-list);
for state in rest(state-list) {
LCA = findLeastCommonAncestor(LCA, state);}
}//
return LCA;
}
state findLeastCommonAncestor(state1, state2) {
if (isDescendent(state2, state1)) {
return state1;
} elsif(isDescendent(state1, state2)) {
return state2;
} elsif (state1 == state2) {
return state1;
} else
for anc in listAncestors(state1, SCXML) {
if (isDescendant(state2, anc)){
return anc;}
}//
//
}
procedure enterStates(enabledTransitions):
statesToEnter = new Set()
statesForDefaultEntry = new Set()
for t in enabledTransitions: if (t.attribute('target') != null):
LCA = findLCA([t.parent()].append(getTargetStates(t)))
for s in getTargetStates(t): if (isHistoryState(s)): if (historyValue[s.attribute('id')] != null): for s0 in historyValue[s.attribute('id')]:
addStatesToEnter(s0,LCA,statesToEnter,statesForDefaultEntry)
else: for s0 in getTargetStates(s.transition):
addStatesToEnter(s0,LCA,statesToEnter,statesForDefaultEntry)
else:
addStatesToEnter(s,LCA,statesToEnter,statesForDefaultEntry)
statesToEnte for anc in getProperAncestors(stateList.head(),null):
r = statesToEnter.toList().sort(enterOrder)
for s in statesToEnter:
configuration.add(s)
for inv in s.invoke:
sessionID = executeInvoke(inv)
datamodel.assignValue(inv.attribute('ID'),sessionID)
for content in s.onentry:
executeContent(content)
if (statesForDefaultEntry.member(s)):
executeContent(s.initial.transition.children())
if (isFinalState(s)):
parent = s.parent()
grandparent = parent.parent()
internalQueue.enqueue(parent.attribute('id') + ".Done")
if (isParallelState(grandparent)): if (getChildStates(grandparent).every(isInFinalState)):
internalQueue.enqueue(grandparent.attribute('id') + ".Done")
for s in configuration.toList(): if (isFinalState(s) && isScxmlState(s.parent())):
exitInterpreter()
C.6.4 addDefaultStatesToEnter( state ,
rootState , [in/out]stateList , [in/out]defaultEntryList )
procedure addStatesToEnter(s,root,statesToEnter,statesForDefaultEntry)
The purpose of this routine
procedure is to add to
stateList statesToEnter all states that must be
entered as a result of entering state .
s . These include
ancestors of state , s , parallel siblings of state s
or its ancestors, and state
s 's default children, if
it s is a parallel or compound state. Note
that this procedure permanently modifies both
stateList statesToEnter and defaultEntryList . statesForDefaultEntry .
For all parallel states S between state
and rootState , for each parallel child that does not have a
descendant on stateList , call addDefaultStatesToEnter on the child
with S as the rootState . Now, First, add state ito
StateList s
to statesToEnter .Then, if it is not already
there. If state s is
a parallel state, call
addDefaultStatesToEnter on add
each of its s 's children
with state as the rootState. Otherwise
to statesToEnter .Else, if state
s is a compond compound
state, add it s to defaultEntryList
. Call addDefaultStatesToEnter on statesForDefaultEntry and add its default initial state with state as the rootState. Finally add all of state 's
ancestors up to but not including
rootState statesToEnter .Finally, for each ancestor anc of
s ,add anc
to stateList if they are not already there.
void addDefaultStatesToEnter(state, rootState, [in/out]stateList,
[in/out]defaultEntryList) { for ancestor in getAncestors(state,
rootState) { if(isParallel(ancestor)) { for pChild in
getChildStates(ancestor) { boolean descendentPresent = false; for
enterState in stateList { if (isDescendent(enterState, ancestor)) {
descendentPresent = true; } }// if(!descendentPresent) {
addDefaultStatesToEnter(pChild, ancestor, stateList,
defaultEntryList); } // // // if (!member(state, stateList)) {
push(state, stateList); } if (isParallel(state)) { for child in
getChildStates(state) { addDefaultStatesToEnter(child, state,
stateList, defaultEntryList); } } elsif (isCompound(state)) {
push(state, defaultEntryList);
addDefaultStatesToEnter(getDefaultInitialState(state), state,
stateList, defaultEntryList); }// for ancestor in
getAncestors(state, rootState) { if(!member(ancestor, stateList)) {
push(ancestor, stateList); } }// } C.6.5 EnterState( state ,
rollbackArray , defaultEntryList , currentEvent ) 1)
statesToEnter and if state contains one or
more anchors, take the corresponding snapshots. 2) If state has an
entry on the rollbackArray , rollback the datamodel using the
anchor recorded in the rollbackArray . 3) Now store the new
snapshots in state . 4) Add state to the ActiveStates list. 5)
Execute state 's <onentry> handlers 6) If state is on
defaultEntryList , execute the executable content in the
transition's state 's <initial> element. 7) If state
anc is a final parallel state,
then generate a Done event for its parent
<state>. 8) Then if add the
parent's parent is a <parallel> state
and all its children are in final
states, generate the Done event for the parent's parent.
Exit. of anc that does not
have a descendant on statesToEnter to statesToEnter .
void EnterState(state, rollbackArray, defaultEntryList) {
dataValue tempArray[];
for ancElement in getElements(state, 'anchor') {
tempArray[getAttribute(ancElement), 'anchortype'] = getDMValue(DataModel, getAttribute(ancElement, 'snapshot');
}
if(rollbackArray[getID(state)] != NULL) {
anchor rollback;
// find the corresponding anchor in state
for ancElement in getElements(state, 'anchor')) {
if (getAttriubte(ancElement, 'anchortype') == rollbackArray[getID(state)]) {
rollback = ancElement; }
}//
// roll back the data model
setDMValue(DataModel, getAttribute(ancElement, 'snapshot'),
DataSnapshots[getID(state)][getAttribute(ancElement, 'anchortype')];
}//
// now update snapshot array with values from before the rollback
for key and value in tempArray {
DataSnapshots[getID(state)][key] = value;
}
// now make state active
push(state, ActiveStates);
if(getElement(state, 'onentry')) {
executeContent(getChildren(getElement(state, 'onentry')), currentEvent);
if(member(state, defaultEntryList)) {
transition trans = getElement(getElement(state, 'initial'), 'transition'));
executeContent(getChildren(transition), currentEvent);
}//
if(isFinal(state)) {
state parent = getParent(state);
state grandparent = getParent(parent);
event parentDoneEvent = createEvent(concat(getID(parent), ".Done"));
push(parentDoneEvent, InternalEvents);
if(isParallel(grandparent)) {
boolean allFinal = true;
for state in getChildren(grandparent) {
if (!isInFinalState(state)) {
allFinal = false;
break;
}//
}//
if (allFinal) {
event grandparentDoneEvent = createEvent(concat(getID(grandparent), ".Done"));
push grandparentDoneEvent, InternalEvents);
{//
}//
}
procedure addStatesToEnter(s,root,statesToEnter,statesForDefaultEntry):
statesToEnter.add(s)
if (isParallelState(s)): for child in getChildStates(s):
addStatesToEnter(child,s,statesToEnter,statesForDefaultEntry)
elif (isCompoundState(s)):
statesForDefaultEntry.add(s)
addStatesToEnter(getDefaultInitialState(s),s,statesToEnter,statesForDefaultEntry)
for anc in getProperAncestors(s,root):
statesToEnter.add(anc)
if (isParallelState(anc)): for pChild in getChildStates(anc): if (!statesToEnter.toList().some(lambda(s): isDescendant(s,anc))):
addStatesToEnter(pChild,anc,statesToEnter,statesForDefaultEntry)
C.6.6.1
isInFinalState( state ) procedure isInFinalState(s)
Return truea) state s is a compound <state> and one of
its children is a <final> state and is on a member of the
ActiveState list configuration, or b)
state if s is a <parallel> state and
isInFinalState is true of all its
children.
boolean isInFinalState(state) {
if(isCompound(state)) {
boolean finalChildActive = false;
for child in getChildren(state) {
if (isFinal(child) && member(child, ActiveStates)) {
finalChildActive = true;
break;}
}//
if (finalChildActive) return true;
else return false;
}//
elsif(isParallel(state)) {
boolean allFinal = true;
for child in getChildren(state) {
if(! isInFinalState(child)) {
allFinal = false;
break;
}//
}//
if (allFinal) return true;
else return false;
}//
else return false;
}
function isInFinalState(s):
if (isCompoundState(s)):
return getChildStates(s).some(lambda(s): isFinalState(s) && configuration.member(s))
elif (isParallelState(s)):
return getChildStates(s).every(isInFinalState)
else:
return false
C.6.6.2
Sorting Order Functions function findLCA(stateList)
We assume that Return the sorting order
functions take two arguments state s
such that s is a proper
ancestor of all states on stateList and return
the one no descendant of
s has this property. Note that comes first in the resulting order. We take
there is guaranteed to be such a state
since the 'documentOrder' sorting
function <scxml> element (which
we treat as given (it returns
whichever a state here) is a common
ancestor of the two states
all states. Note also that since we are
speaking of proper ancestor (parent or transitions comes first in parent of a parent, etc.) the defining document.) LCA is
never a member of stateList .
state exitOrder(state1, state2) {
if(isDescendent(state1, state2)) {
return state1; }
elsif(isDescendent(state2, state1) {
return state2;
else return first(sort(list(state1, state2), 'documentOrder'));
}
state enterOrder(state1, state2) {
if(isDescendent(state1, state2)) {
return state2; }
elsif(isDescendent(state2, state1) {
return state1;
else return first(sort(list(state1, state2), 'documentOrder'));
}
C.6.6
Miscellaneous
Functions
id executeInvoke( is the parsed representation of the <invoke> element.
// this function invokes the service specified in passing any parameters specified by <param> elements
//plus the value of 'src' or 'srcexpr'. This function must generate and return a unique id that will be used to track
//this invocation.
void cancelInvoke(. This id was returned by an earlier
//call to executeInvoke;
void processFinalize() {
// is the ID of the state that executed the <invoke>.
// This function should use to find the executable content in <finalize> element (if it is present) and update
// the data model accordingly. It is an error if the executable content tries to raise events or takes an action
//other than updating the datamodel.
//void executeContent();
//Execute the items in in document order. Each item must complete before
//the execution of the next one. The special variable '_eventData' should be bound to the data contained in
//before execution takes place. If is NULL or contains no data, '_eventData' should be set to the empty string.
//Afterwards, '_eventData' should be set back to 'undefined'. Exit when all items have completed.
//NOTE: executable content items must execute in their own 'sandbox' where they cannot modify any of the internal data
//structures defined in this algorithm, except for the data model.
boolean nameMatch();
// return true if . The wildcard '*'
//in 's "event" attribute matches any string of 0 or more characters.
boolean conditionMatch();
//return true if has an empty 'cond' attribute or if its 'cond' attribute is non-empty and evaluates to
//'true' in DataModel. The special variable '_eventData' should be bound to the data contained in before
//the evaluation takes place. If is NULL or contains no data, '_eventData' should be set to the empty string.
//Afterwards, it should be set back to 'undefined'.
dataValue getDMValue( is NULL,
//return whole to
//have value is NULL,
//replace the whole .
state list getAncestors();
// return all ancestors of is NULL
// or not an ancestor of up to but not includig the root <scxml> element.
// States on the returned list are sorted so that children preceed ancestors. Note that if equals
//, the empty list is returned.
state loadAndParseStateMachine(env); // load and parse the state machine, including any
datamodel = buildDataModel(env, state);//initialize data model
void addElement(. Called only during the intitialization phase
// to add default behaviors. Once the state machine starts running, it may not be modified.
ID getID( Id attribute.
transition list getTransitions( in document order.
boolean isAtomic( is atomic (i.e. has no child <state> or <parallel> elements.)
boolean isCompound( has <state> children
boolean isParallel( is defined by a <parallel> element.
boolean isFinal( is a <final> state.
boolean isHistoryState( is a history pseudo-state.
state getParent( if any, otherwise NULL;
boolean isDescendant(.
attribute getAttribute(.
element getElement(.
list<element> getElements( that are an immediate children
//of .
list<element> getChildren(.
list <state> getChildStates(.
list <state> getHistoryStates( should be
//'deep' or 'shallow'.
list<state> getHistoryValue(, if any, otherwise NULL;
void setHistoryValue(.
list<state> getHistoryDefault('s <transition> child.
list<anchor> getAnchors(.
state getDefaultInitialState(.
state getSourceState(.
list<state> getTargetStates(.
void exitInterpreter();// causes the interpreter to terminate.
event createEvent(.
boolean empty( is empty
item pop(.
void push(
list delete(.
//the following list functions are all non-destructive and do not modify the list that is passed to them
list add(.
sitem first(
list rest( except the first.
list tail( is not
//a member of .
list append(.
list remove(.
boolean member(.
void deleteArrayElement(.
string concat(
function findLCA(stateList):
for anc in getProperAncestors(stateList.head(),null):
if (stateList.tail().every(lambda(s): isDescendant(s,anc))):
return anc
C.7 B.1
Semantics of <anchor>
There are a number of ways of defining the semantics of
<anchor>. We choose the following because it shows that,
except for the rollback of the data model, <anchor> can be
viewed as a syntactic shortcut that does not extend the basic Harel
semantics. We emphasize that implementations are required only to
behave as if they assigned the following intepretation interpretation to <anchor> and that simpler
and more efficient implementations are possible.
First, we add a special branch 'anchors' to the data model, with
a child for each anchor type defined in the document. Thus if the
document defines anchor types "foo" and "bar", the data model will
have paths 'anchors.foo' and 'anchors.bar'. Whenever the state
machine enters a state with an <anchor> element, it sets the
value of the corresponding anchor entry in the datamodel to the ID
of that state. Thus if a <state> with ID 'state27' defines an
<anchor> with 'type' "foo", whenever the state machine visits
this state, it sets 'anchors.foo; to 'state27'. Furthermore, the
state machine automatically adds the 'anchors' branch to the
snapshot specified in the <anchor> element.
Now any <transition> which specifies an 'anchor' is
replaced with a set of <transition>s, one for each
<state> that defines that <anchor>. Each of the
<transition>s takes as its 'target' one of the <state>s
that defines the <anchor>. Furthermore, an extra clause is
added to the 'cond' of the original <transition>, specifying
that the corresponding location in the data model match the target
<state>'s ID. Finally, a default transition is added
reentering the current <state>. For example, if the anchor
type "foo" is defined in <state>s 'state27' and 'state33',
then in <state> 'thisState', a transition with "event"
"someEvent", "cond" "someCond" and "anchor" 'foo' will be replaced
by three transitions, as shown below:
<transition event="someEvent" cond="someCond" anchor="foo"/>
is equivalent to
<transition event="someEvent" cond="datamodel.anchors.foo==state27 && someCond" target="state27"/>
<transition event="someEvent" cond="datamodel.anchors.foo==state33 && someCond" target="state33"/>
<transition event="someEvent" cond="someCond" target="state33"/> target="thisState"/>
At runtime when "someEvent" is raised and "someCond" is true, if
either state27 or state33 has been visited, 'datamodel.anchors.foo'
will have the corresponding stateID as its value and the
corresponding transition will be selected. The only complication is
that the transitions must retain the original 'anchor' attribute,
so that the datamodel must be rolled back to the snapshot specified
in the corresponding <anchor> element. Note that the
'anchors' branch must be automatically added to this snapshot, so
that it will be automatically rolled back as well. (This has the
effect of erasing any intermediate anchors that have been visited
since the target state was exited.) If neither state27 nor state33
has been visited, the third transition will be taken, causing the
state machine to exit and reenter 'thisState' without any rollback
of the datamodel.
