Re: revised enterStates

I like the direction of the refactor.  I had already done something similar
with my implementation because if a parallel is initialized while another
target points into it then it could get two different states as part of one
of its subtrees active.  Basically moving the parallel initialization
outside of the enter states loop should have fixed that type of problem.

I think we both have a bug in our implementation, however.  Basically, the
problem is that the second pass through the transitions where you are
activating parallels uses the transition targets which may not actually
point to atomic states.  Thus you could perhaps skip parallels that have
been only partially activated via an initial transition but lie below any
transition targets.

I think, in order to be safe and easy to verify correct the second pass
that activates parallels needs to go through all atoms in the statesToEnter
set and work all the way up to the root.  Then I would feel that there is
no possible way I could create a test case that would break this pass.  As
a side benefit, you could also run verification in this second step that
the state machine wasn't in an invalid configuration (ensure that no
compound state has more than one active children).

Chris


On Thu, Feb 14, 2013 at 7:08 AM, Jim Barnett <Jim.Barnett@genesyslab.com>wrote:

>  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<radomski@tk.informatik.tu-darmstadt.de>]
>
> *Sent:* Wednesday, February 13, 2013 6:55 PM
> *To:* Jim Barnett
> *Cc:* VBWG Public (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>
> 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****
>



-- 
A foolish consistency is the hobgoblin of little minds - Emerson