RE: [SCXML] Algorithm bug in addDescendantStatesToEnter?

Ate,
  There is a bug in the latest published version of addDescendentStatesToEnter and we have made changes to it in the (not yet officially published) Editor's draft, which is available here:  http://www.w3.org/Voice/2013/scxml-irp/SCXML.htm  (Among other things, the call to getEffectiveTargetStates was causing problems.) Would you look at the new version and tell us if it still has the problem?

Thanks,
Jim

-----Original Message-----
From: Ate Douma [mailto:ate@douma.nu] 
Sent: Saturday, October 11, 2014 6:39 AM
To: www-voice@w3.org
Subject: [SCXML] Algorithm bug in addDescendantStatesToEnter?

Hi there,

I think I detected a bug in the addDescendantStatesToEnter algorithm in the specification concerning *when* to invoke the addAncestorsStatesToEnter.

Currently the algorithm defines the following logic for a compound state, after having added it to the statesForDefaultEntry:

     for s in getEffectiveTargetStates(state.initial.transition):
         addDescendantStatesToEnter(s,statesToEnter,statesForDefaultEntry,
defaultHistoryContent)
         addAncestorStatesToEnter(s, state, statesToEnter, statesForDefaultEntry, defaultHistoryContent)

If not first for all effective target states addDescendantStatesToEnter is executed, the addAncestorStatesToEnter might, when in involves an ancestor parallel with nested compound states of which one also happens to be one of the effective desendant target *but not yet resolved*, end up initializing a different
(default) sibling child of such a compound state.
End result: an invalid configuration with a compound state having multiple active child states.

I detected this issue when testing irp test364, which indeed defines such a SCXML document.
If the algorithm is implemented as currently defined in the specification, you'll end up with both s11p121 and s11p122 being on the statesToEnter set (or s11p111 and s11p112, depending on the processing order of the s1 initial targets).

In Apache Commons SCXML I've implemented a legal configuration check before executing enterStates, and that fails on this point for irp test364.

Maybe important to note is that if I disable the check, the test actually passes, so maybe others might have this same bug but going unnoticed?

Solving this bug however should be pretty trivial.
To ensure explicit descendant target states are recorded first, I just changed the above logic to:

     for s in getEffectiveTargetStates(state.initial.transition):
         addDescendantStatesToEnter(s,statesToEnter,statesForDefaultEntry,
defaultHistoryContent)
     for s in getEffectiveTargetStates(state.initial.transition):
         addAncestorStatesToEnter(s, state, statesToEnter, statesForDefaultEntry, defaultHistoryContent)

And I did the same for the two similar/same for loops in the handling for history states in addDescendantStatesToEnter where likewise both descendant and ancestors states to enter are resolved within a single loop.

Note: the description of addDescendantStatesToEnter actually does seem to say it more correctly where it breaks these two separate 'steps' down in two separate sentences:

     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'.

The above description at least gives the right direction how this should be implemented, namely as separate consecutive steps, but not 'optimized' into a single loop as currently done.
Confusingly and incorrectly though this description names the "addDescendantStatesToEnter" routine "addStatesToEnter".
It probably would be good to correct that as well.

Kind regards,

Ate Douma

Received on Saturday, 11 October 2014 13:12:15 UTC