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

Re: [SCXML] Algorithm bug in addDescendantStatesToEnter?

From: Ate Douma <ate@douma.nu>
Date: Sat, 11 Oct 2014 13:04:45 +0200
Message-ID: <54390ECD.5090506@douma.nu>
To: www-voice@w3.org
Looks like the mailing list makes a mess of the formatting in my email making it 
more difficult to read.

FYI: a more easy to ready formatted copy (quote) of this email can be found at:

   https://issues.apache.org/jira/browse/SCXML-211

Regards,
Ate

On 11-10-14 12:38, Ate Douma wrote:
> 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 11:05:14 UTC

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