Re: [SCXML] Algorithm bug in addDescendantStatesToEnter?

I have updated the draft according to Ate's suggestions.  In 
AddDescendantStatesToEnter there were three places where there was a 
single loop; iterate over all history values/target states and call 
addDescendentStatesToEnter and then addAncestorStatesToEnter.  Each of 
those three loops has now been split into two:  first iterate over all 
history values/target states and call addDescendentStatesToEnter,  then
iterate over the same states again and call addAncestorStatesToEnter.  
Thus all descendents have been added before any ancestor is.

So, Ate, please take a look and see if this is correct.

If anyone gets a chance to run the mandatory tests with this new 
version, please let us know if these changes break something.

http://www.w3.org/Voice/2013/scxml-irp/SCXML.htm
http://www.w3.org/Voice/2013/scxml-irp/SCXML_Diff.htm

- Jim

On 10/13/2014 11:22 AM, Ate Douma wrote:
> 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 17:14:51 UTC