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

Re: [SCXML] Algorithm bug in addDescendantStatesToEnter?

From: Ate Douma <ate@douma.nu>
Date: Mon, 13 Oct 2014 20:30:47 +0200
Message-ID: <543C1A57.1000100@douma.nu>
To: www-voice@w3.org
On 13-10-14 19:14, Jim Barnett wrote:
> 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.

This looks good to me, thanks!

Ate

>
> 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 18:31:18 UTC

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