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

["Ate Douma (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/SCXML-211?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Ate Douma resolved SCXML-211.
-----------------------------
    Resolution: Fixed

Resolved as described above.
I will keep this issue non-closed until verification/confirmation from the SCXML specification group on my reported bug.

> Bug in current SCXML specification for addDescendantStatesToEnter algorithm can lead to illegal configurations
> --------------------------------------------------------------------------------------------------------------
>
>                 Key: SCXML-211
>                 URL: https://issues.apache.org/jira/browse/SCXML-211
>             Project: Commons SCXML
>          Issue Type: Bug
>    Affects Versions: 2.0
>            Reporter: Ate Douma
>            Assignee: Ate Douma
>             Fix For: 2.0
>
>
> While testing the SCXML specification using the [IRP Plan tests| http://www.w3.org/Voice/2013/scxml-irp/] 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:
> {quote}
> 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:
> {noformat}
>      for s in getEffectiveTargetStates(state.initial.transition):
>          addDescendantStatesToEnter(s,statesToEnter,statesForDefaultEntry, defaultHistoryContent)
>          addAncestorStatesToEnter(s, state, statesToEnter, statesForDefaultEntry, defaultHistoryContent)
> {noformat}
> 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:
> {noformat}
>      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)
> {noformat}
> 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:
> {noformat}
>      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'.
> {noformat}
> 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
> {quote}



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)