Re: [SCXML] Algorithm bug in addDescendantStatesToEnter?

On 13-10-14 16:48, Jim Barnett wrote:
> 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.)
Yes, assumed correctly :)
Note: I don't have (created) a test-case which also covers the history state 
handling scenarios, but AFAIK it really shouldn't make a difference, e.g. have 
the same issue, whether processing history based states or not.

> 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.)
I'm definitely not ready yet to run all the mandatory tests.

So I hope other implementations, like LXSC and uscxml, might want to look into 
this issue and review my proposed change, including for the history states 
handling, and report its validity to be included in the specification.

Regards,
Ate

>
> - 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 15:23:16 UTC