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

Re: [SCXML] Algorithm bug in addDescendantStatesToEnter?

From: Jim Barnett <1jhbarnett@gmail.com>
Date: Mon, 13 Oct 2014 10:48:09 -0400
Message-ID: <543BE629.1050704@gmail.com>
To: www-voice@w3.org
Ate,
   Thanks for tracking this down.   It is clearly a bug.  The issue now is:

1)  do we want to make this change only for the 'isCompoundState' clause 
(as Stefan does), or do we want to include the history state clauses as 
well?  (I assume that you think that history states need to be included 
as well.)
2)  How can we make sure that doing this won't break anything else? How 
close are you to being able to run all the mandatory tests?  (If this 
change doesn't break any mandatory tests, I doubt if it would affect the 
optional ones.)

- Jim
On 10/13/2014 10:37 AM, Ate Douma wrote:
> 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:48:35 UTC

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