RE: revised enterStates

And now a correction to a correction.  The declaration/assignment 'tstates = getTargetStates(t.target)'  goes at the top of getTransitionDomain.


-          Jim


From: Jim Barnett [mailto:Jim.Barnett@genesyslab.com]
Sent: Thursday, February 14, 2013 8:52 AM
To: Stefan Radomski
Cc: VBWG Public (www-voice@w3.org)
Subject: RE: revised enterStates

Stefan,
  Your observations are mostly correct.  Comments in-line set off by '>>'

From: Stefan Radomski [mailto:radomski@tk.informatik.tu-darmstadt.de]
Sent: Wednesday, February 13, 2013 6:55 PM
To: Jim Barnett
Cc: VBWG Public (www-voice@w3.org<mailto:www-voice@w3.org>)
Subject: Re: revised enterStates

I took the liberty of implementing the new algorithms and have a few superficial remarks.

On Feb 13, 2013, at 9:37 PM, Jim Barnett <Jim.Barnett@genesyslab.com<mailto:Jim.Barnett@genesyslab.com>> wrote:

[...]

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)

I assume enabledTransitions is transitions? Also getTransitionDomain takes a transition, not a state.

>> Yes and yes.  Should be 'transitions' and  'getTransitionDomain(t)'
    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)

I do not get this part: "state.initial" is supposed to be the initial state with regards to an <initial> element or the initial attribute? But how can there be more than one with a compound state? I was already wondering with the original algorithm.
>>  It's the <initial> element.  'initial' attributes are converted to <initial> elements at the top of the 'interpret' procedure, just to simplify places like this.  A compound state can have multiple initial states if they are descendents of a <parallel> element inside the state.
            for s in getTargetStates(state.initial):
                addDescendentStatesToEnter(s,statesToEnter,statesForDefaultEntry)
                addAncestorStatesToEnter(s, state, statesToEnter, statesForDefaultEntry)

This else is indented somewhat unfortunately.
>> Yes, indentation got messed up in the original email.  It should be ok when we publish a new doc, but for the moment you'll have to be creative.
   else:
        if isParallelState(state):
            for child in getChildStates(state):
                 if not statesToEnter.some(lambda s: isDescendant(s,child)):
                     addDescendentStatesToEnter(child,statesToEnter,statesForDefaultEntry)


I assume this is what's called "addAncestorStatesToEnter" in the rest of the pseudo-code.

>> Yes, naming should be consistent with addDescendentStatesToEnter

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

This elif is placed somewhat unfortunately as well. Also tstates is not defined. I take it, this is what Chris proposed as "getTransitionSubgraph"?

>> See previous remark about indentation.    Yes, there is a missing line 'tstates = getTargetStates(t.target)' that should go right after the 'elif'.   This is common code that has been factored out of enterStates and exitStates.  I think that it's what Chris had in mind.



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


Best regards
Stefan