Re: [SCXML] Algorithm bug in addDescendantStatesToEnter?

On 11-10-14 15:56, Jim Barnett wrote:
> I've updated the diff file at that location.
> http://www.w3.org/Voice/2013/scxml-irp/SCXML_Diff.htm.  The change we've made
> may address the same issue.  getEffectiveTargetStates  jumps over
> intermediate states.  Removing it means that the algorithm works its way down
> one 'layer' at a time.  That fixed some problems that we were seeing.  I'll
> be interested to know if it fixes your issue as well.

The change to (not) using the getEffectiveTargetStates in 
addDescendantStateToEnter doesn't affect nor fix the issue I'm having.

So my issue is an independent one which I think also needs to be fixed.

I've tried to look into other (open) SCXML implementations to see if/how they 
handle this issue, or not.

I could reproduce (with some effort) the issue I see with test 364 in the LXSC 
implementation from Gavin Kistner [1].
With some hacking (I'm not really familiar to using Lua and initially had some 
problems getting it to work on my Linux laptop), I finally got some trace output 
from executing test 364, for which I include only the first (relevant) part below:

    ./autotest.lua test364.scxml --trace
   Failed running test364.scxml:
   ...setdata _sessionid=dd557e0d-76b2-4d95-a7ef-4a82772e3016
   ...setdata _name=(lxsc)
   ...setdata _ioprocessors=table: 0x22a59d0
   ...entered state 's1'
   ...entered state 's11'
   ...entered parallel 's11p1'
   ...entered state 's11p11'
   ...fireevt <event>{type="internal", name="In-s11p112", origintype=""}
   ...entered state 's11p112'
   ...entered state 's11p12'
   ...entered state 's11p121'
   ...entered state 's11p122'
   ...setdata _event=<event 'In-s11p112' type=internal>
   ...exiting state 's11p122'
   ...exiting state 's11p121'
   ...exiting state 's11p12'

As can be seen above, the state machine illegally enters *both* s11p121 and 
s11p122 (unnoticed), which highlights the issue I'm raising.

I also briefly looked at the uscxml implementation from Stefan Radomski [2], 
which does NOT expose this issue. After reviewing the code (and I'm NOT a C++ 
expert either), I noticed it has a similar 'fix' already in place in the 
InterpreterRC::addDescendantStatesToEnter method as I propose: first process all 
descendants before processing possible ancestors.
Note though it only does this within the "if isCompoundState(state):" block, not 
also for the (two) blocks in the history state handling.

Kind regards,
Ate

[1] https://github.com/Phrogz/LXSC
[2] https://github.com/tklab-tud/uscxml

>
> - Jim
>
> -----Original Message----- From: Ate Douma [mailto:ate@douma.nu] Sent:
> Saturday, October 11, 2014 9:20 AM To: Jim Barnett; www-voice@w3.org Subject:
> Re: [SCXML] Algorithm bug in addDescendantStatesToEnter?
>
> On 11-10-14 15:11, Jim Barnett wrote:
>> Ate, There is a bug in the latest published version of
>> addDescendentStatesToEnter and we have made changes to it in the (not yet
>> officially published) Editor's draft, which is available here:
>> http://www.w3.org/Voice/2013/scxml-irp/SCXML.htm  (Among other things, the
>> call to getEffectiveTargetStates was causing problems.) Would you look at
>> the new version and tell us if it still has the problem?
>>
> Alright, I'll check that draft version. Although at first glance it looks
> like it has the same issue still.
>
> Is there also a diff available so I can better determine what actually has
> been modified in this draft? The provided link in the document to
> http://www.w3.org/Voice/2013/scxml-irp/diff.html results in a 404
>
> Regards, Ate
>
>> Thanks, Jim
>>
>> -----Original Message----- From: Ate Douma [mailto:ate@douma.nu] Sent:
>> Saturday, October 11, 2014 6:39 AM To: www-voice@w3.org Subject: [SCXML]
>> Algorithm bug in addDescendantStatesToEnter?
>>
>> 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 Monday, 13 October 2014 14:37:42 UTC