commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Ate Douma (JIRA)" <j...@apache.org>
Subject [jira] [Updated] (SCXML-211) Bug in current SCXML specification for addDescendantStatesToEnter algorithm can lead to illegal configurations
Date Sat, 11 Oct 2014 11:02:33 GMT

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

Ate Douma updated SCXML-211:
----------------------------
    Description: 
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}


  was:
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:

     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
{quote}



> 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)

Mime
View raw message