[SCXML-211] Bug in current SCXML specification for addDescendantStatesToEnter algorithm can lead to illegal configurations

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 2.0
• Fix Version/s: 2.0
• Assignee: Ate Douma
• Reporter: Ate Douma
• Created: 11/Oct/14 10:54
• Updated: 11/Oct/14 11:10
• Resolved: 11/Oct/14 11:08

Description

While testing the SCXML specification using the IRP Plan tests I discovered a bug in the current specification addDescendantStatesToEnter algorithm: http://www.w3.org/TR/2014/WD-scxml-20140529/#addDescendantStatesToEnter

I've already send a notice about this bug to the SCXML specification mailing list, see: http://lists.w3.org/Archives/Public/www-voice/2014OctDec/0000.html
which I'm copying verbatim below:

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