W3C home > Mailing lists > Public > www-voice@w3.org > January to March 2013

revised enterStates

From: Jim Barnett <Jim.Barnett@genesyslab.com>
Date: Wed, 13 Feb 2013 20:37:14 +0000
To: "VBWG Public (www-voice@w3.org)" <www-voice@w3.org>
Message-ID: <57A15FAF9E58F841B2B1651FFE16D2810208A4@GENSJZMBX03.msg.int.genesyslab.com>
The existing version of enterStates is confusing and buggy.   (For example, I believe that if you take a parallel state p and a non-default descendent of it, say p and p-grandchild, and put them as targets of a transition in that order, the state machine will enter both p-grandchild and p's default descendent.)  I have tried to re-write enterStates for clarity, below.

The basic problem with this routine is that when a state s is the target of a transition, it isn't necessarily a atomic state, so you have to work down the state tree finding the descendents of s that need to be entered.  And you also need to work _up_ the state tree, finding ancestors of s that need to be entered.  Furthermore, when you work down the tree, you may enter deep history states and/or default initial states which 'jump down' the state tree.  When that happens, you have to work back _up_ the tree.   And when you're working up the tree through the ancestors, you may run into a <parallel> state, at which point you have to start working back _down_ the tree again.  So you end up yo-yoing up and down the tree enough to make yourself seasick.

I haven't been able to figure out how to write this with a single downward pass followed by an upward pass, but I have tried to separate 'work down the tree' and 'work up the tree' into separate procedures in the hopes of making things clearer.  (All the work of computing the state tree has been pushed off into the procedure computeEntrySet, so enterStates just has the logic for actually entering the states, which hasn't changed.)

So take a look at the following and tell me:

1.        Is it clearer than what's there now?

2.       If so, is it correct?

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.member(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 enabledTransitions:
        ancestor = getTransitionDomain(t.target)
        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)

procedureaddAncestorsToEnter(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)


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)

  if not t.target

     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(getTargetStates(t.target)))
Received on Wednesday, 13 February 2013 20:37:44 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Wednesday, 13 February 2013 20:37:49 GMT