W3C home > Mailing lists > Public > www-voice@w3.org > October to December 2014

[SCXML] Algorithm bug in addDescendantStatesToEnter?

From: Ate Douma <ate@douma.nu>
Date: Sat, 11 Oct 2014 12:38:33 +0200
Message-ID: <543908A9.7030005@douma.nu>
To: www-voice@w3.org
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 10:39:02 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:07:45 UTC