- From: Jacob Beard <jbeard4@cs.mcgill.ca>
- Date: Thu, 3 Mar 2011 17:44:24 -0500
- To: Jim Barnett <Jim.Barnett@alcatel-lucent.com>
- Cc: www-voice <www-voice@w3.org>
I've created a patch which seems to solve the test cases I presented, as well as some more complex ones. Relevant procedures from the original step algorithm: https://gist.github.com/853745/ce46fa7a697f1c69340b93863fda373a6a482fdd Proposed change to the step algorithm: https://gist.github.com/853745/5aaf3c0a528f9863b19c7a1d99ae8a48fbc8ce64 Note that I actually found it easier to express this in a pseudo-JavaScript syntax (rather than the pseudo-python syntax which is currently used). Diff: https://gist.github.com/853759/9d13f6741d1fd254a82a2bb2d7a5602278410472 If there's a more appropriate way to pass around long code snippets on this list (I'm not sure about the W3C's policy on archiving), please let me know. The idea is that calling addStatesToEnter recursively in order to add children of parallel state ancestors of the current state being processed leads to the unusual behaviour I mentioned in my previous email. So, the solution is to break this logic out so that it is performed as a second pass, after the recursive traversal. This is performed in a loop, because each time the recursive traversal is performed, more states (specifically, children of parallel states without descendants in statesToEnter) may need to be recursively added to statesToEnter. In case anyone is interested in seeing my implementation in JavaScript, I've posted a tarball here: http://stuff.echo-flow.com/interpreter.tar.gz Let me know what you think. Thanks, Jake On Thu, Mar 3, 2011 at 3:13 PM, Jacob Beard <jbeard4@cs.mcgill.ca> wrote: > Hi, > > I just realized that the first test case I gave in the previous email, > while correct, included some unnecessary states and transitions, which > may have been confusing. This is the correct version: > > <scxml xmlns="http://www.w3.org/2005/07/scxml" profile="ecmascript" > version="1.0" name="scxmlRoot"> > <initial> > <transition target="A2 B2"/> > </initial> > > <parallel id="P"> > > <state id="A" initial="A1"> > <state id="A1"/> > > <state id="A2"/> > </state> > > <state id="B" initial="B1"> > <state id="B1"/> > > <state id="B2"/> > </state> > > </parallel> > > </scxml> > > (gist: https://gist.github.com/850186 ) > > The trace is the same as I described in the previous email. > > Sorry for the confusion. Thanks, > > Jake > > On Tue, Mar 1, 2011 at 7:16 PM, Jacob Beard <jbeard4@cs.mcgill.ca> wrote: >> Hi Jim, >> >> Unfortunately, it seems I was mistaken, the change does not fix the >> test case I presented. >> >> In fact, I realized that, given the current step algorithm, the test >> case I presented fails during initialization, which does not have >> anything to do with history. >> >> Please consider the following new test case: >> >> <scxml xmlns="http://www.w3.org/2005/07/scxml" profile="ecmascript" >> version="1.0" name="scxmlRoot"> >> <initial> >> <transition target="A2 B2"/> >> </initial> >> >> <parallel id="P"> >> >> <state id="A" initial="A1"> >> <state id="A1"/> >> >> <state id="A2"/> >> </state> >> >> <state id="B" initial="B1"> >> <state id="B1"/> >> >> <state id="B2"/> >> </state> >> >> <transition event="e1" target="C"/> >> </parallel> >> >> <state id="C"> >> <transition event="e2" target="H"/> >> </state> >> </scxml> >> >> >> (gist: https://gist.github.com/850186 ) >> >> Here's a trace of the calls to addStatesToEnter, along with their parameters: >> >> addStatesToEnter: s : A2, root : scxmlRoot >> addStatesToEnter: s : B, root : P >> addStatesToEnter: s : B1, root : B >> addStatesToEnter: s : B2, root : scxmlRoot >> >> I think the problem here is similar to what I noticed involving >> history and nested parallel states: >> >> On the initial default transition, the step algorithm calls >> addStatesToEnter with A2 bound to parameter s, and H bound to >> parameter root. A2 is a basic state, so it gets added to >> statesToEnter. Then, for each ancestor anc of A2, anc is added to >> statesToEnter and if anc is a parallel state, any child of anc that >> does not have a descendant on statesToEnter is added to statesToEnter. >> In this case, P is an ancestor of A2, and its child compound state B >> does not yet have a descendant on statesToEnter (B2 has not yet been >> added to statesToEnter, as we have not yet returned from this >> recursive call). So, addStatesToEnter is called with B bound to s, and >> P bound to root. B is a compound state, so B's initial state, B1, will >> be added to statesToEnter. Later on, we will return from the >> recursive call, and addStatesToEnter will be called for B2. B2 will be >> added to statesToEnter, and so both B1 and B2 will have been added to >> statesToEnter, which will later on cause the statechart to enter the >> illegal basic configuration [A2, B1, B2]. >> >> >> >> I think the problem also persists in cases involving history inside of >> parallel. Please consider the following case: >> >> >> <scxml xmlns="http://www.w3.org/2005/07/scxml" profile="ecmascript" >> version="1.0" name="scxmlRoot"> >> <initial> >> <transition target="P"/> >> </initial> >> >> <parallel id="P"> >> <history id="H" type="deep"/> >> >> <state id="A" initial="A1"> >> <state id="A1"> >> <transition target="A2" event="e1" /> >> </state> >> >> >> <state id="A2"/> >> </state> >> >> <state id="B" initial="B1"> >> <state id="B1"> >> <transition target="B2" event="e1" /> >> </state> >> >> <state id="B2"/> >> </state> >> >> <transition event="e2" target="C"/> >> </parallel> >> >> <state id="C"> >> <transition event="e3" target="H"/> >> </state> >> </scxml> >> >> (gist: https://gist.github.com/850188 ) >> >> >> Given that e1 has been called, bringing the state machine into >> configuration [A2,B2], and e2 has been called, bringing the state >> machine into configuration [C] and capturing [A2,B2] as history of H, >> here's the trace of calls to addStatesToEnter on event e3: >> >> addStatesToEnter: s : H, root : scxmlRoot >> addStatesToEnter: s : A2, root : scxmlRoot >> addStatesToEnter: s : B, root : P >> addStatesToEnter: s : B1, root : B >> addStatesToEnter: s : B2, root : scxmlRoot >> >> Because the LCA for the transition from C to H is scxmlRoot, this >> means that the call to getProperAncestors(A2,scxmlRoot) will still >> include P in the returned ancestor set, and the trace will be the same >> as the one I outlined in the previous test case. >> >> >> I'd appreciate any guidance you can offer into this. Thanks, >> >> Jake >> >> On Tue, Mar 1, 2011 at 5:24 PM, Jacob Beard <jbeard4@cs.mcgill.ca> wrote: >>> Hi Jim, >>> >>> Thanks for the quick reply. The modified algorithm works as expected. >>> >>> Best, >>> >>> Jake >>> >>> On Tue, Mar 1, 2011 at 5:08 PM, Jim Barnett >>> <Jim.Barnett@alcatel-lucent.com> wrote: >>>> Jacob, >>>> We have discovered a bug in the algorithm that is probably involved in >>>> this case. The history state should not be passed as 'root' on the >>>> recursive call to addStatesToEnter. The new version of the procedure >>>> keeps the same value of 'root' on the recursive call: >>>> >>>> procedure addStatesToEnter(s,root,statesToEnter,statesForDefaultEntry): >>>> if isHistoryState(s): >>>> if historyValue[s.id]: >>>> for s0 in historyValue[s.id]: >>>> >>>> addStatesToEnter(s0,root,statesToEnter,statesForDefaultEntry) >>>> >>>> This revision will be in the next published version of the spec. Try it >>>> out and see if it helps. If not, please report back to us, and we will >>>> investigate further. >>>> >>>> - Jim >>>> >>>> -----Original Message----- >>>> From: www-voice-request@w3.org [mailto:www-voice-request@w3.org] On >>>> Behalf Of Jacob Beard >>>> Sent: Sunday, February 27, 2011 8:11 PM >>>> To: www-voice >>>> Subject: [scxml] semantics of nested history in parallel state >>>> >>>> Hi, >>>> >>>> I'm currently working on an implementation of the SCXML step >>>> algorithm, and I've run into a situation which is somewhat unclear. >>>> Please consider the following scenario: >>>> >>>> <scxml> >>>> <initial> >>>> <transition target="A2 B2"/> >>>> </initial> >>>> >>>> <parallel id="P"> >>>> <history id="H" type="deep"/> >>>> >>>> <state id="A" initial="A1"> >>>> <state id="A1"/> >>>> >>>> <state id="A2"/> >>>> </state> >>>> >>>> <state id="B" initial="B1"> >>>> <state id="B1"/> >>>> >>>> <state id="B2"/> >>>> </state> >>>> >>>> <transition event="e1" target="C"/> >>>> </parallel> >>>> >>>> <state id="C"> >>>> <transition event="e2" target="H"/> >>>> </state> >>>> </scxml> >>>> >>>> The state machine starts in basic configuration [A2,B2]. >>>> >>>> Given event e1, the state machine transitions to C, so the basic >>>> configuration is [C]. >>>> >>>> Given event e2, the state machine transitions to H. It has already >>>> captured the previous configuration [A2,B2]. The step algorithm then >>>> calls addStatesToEnter with A2 bound to parameter s, and H bound to >>>> parameter root. A2 is a basic state, so it gets added to current >>>> statesToEnter. Then, for each ancestor anc of A2, add anc to >>>> statesToEnter and if anc is a parallel state, any child of anc that >>>> does not have a descendant on statesToEnter is added to statesToEnter. >>>> In this case, P is an ancestor of A2, and its child compound state B >>>> does not yet have a descendant on statesToEnter (B2 has not yet been >>>> added to statesToEnter, as we have not yet returned from this >>>> recursive call). So, addStatesToEnter is called with B bound to s, and >>>> P bound to root. B is a compound state, so B's initial state, B1, will >>>> be added to statesToEnter. >>>> >>>> Later on, we will return from the recursive call, and addStatesToEnter >>>> will be called for B2. B2 will be added to statesToEnter, and so both >>>> B1 and B2 will have been added to statesToEnter, which will later on >>>> cause the statechart to enter an illegal configuration. >>>> >>>> It seems I have probably misunderstood the specification, but it's not >>>> clear how. I would appreciate any advice as to what I might be >>>> missing. >>>> >>>> Thanks, >>>> >>>> Jake >>>> >>>> >>>> >>>> ------------------------------------------------------------------------------------------------------------------- >>>> CONFIDENTIALITY NOTICE: This e-mail and any files attached may contain confidential and proprietary information of Alcatel-Lucent and/or its affiliated entities. Access by the intended recipient only is authorized. Any liability arising from any party acting, or refraining from acting, on any information contained in this e-mail is hereby excluded. If you are not the intended recipient, please notify the sender immediately, destroy the original transmission and its attachments and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Copyright in this e-mail and any attachments belongs to Alcatel-Lucent and/or its affiliated entities. >>>> >>>> >>> >> >
Received on Thursday, 3 March 2011 22:45:20 UTC