- From: Ate Douma <ate@douma.nu>
- Date: Tue, 08 Apr 2014 14:24:19 -0600
- To: www-voice@w3.org
On 08-04-14 13:36, Jim Barnett wrote:
> Ate,
> Here's an example that shows why we have to dereference history states when
> computing the transition domain. Consider a state S with a deep history state
> H1, plus two child states S1 and S2, which are both deeply nested (have a
> number of descendent states.) Now add a transition to S1 with target H1 and type
> 'internal'. What is the domain of this transition? I think that it depends on
> whether the deep history value contains a descendent of S1 or of S2. If the
> deep history value is a descendent of S1, then the target of the transition is a
> descendent of S1, so the transition is internal and the domain is S1. However
> if the deep history value is a descendent of S2, the transition is not internal
> and the domain is S. So I think that we do need to dereference the actual
> history value to compute the domain.
Right, I agree, and that is a use-case I overlooked.
So dereferencing of history indeed is needed in getTransitionDomain.
Looks like I need to adjust my implementation then.
While thinking this through, could a history default transition itself target
yet another history of one of the descendant states?
What if in your example above, S1 has a history H2 of its own, can the H1
default transition target H2? This of course already assumes H1 is of type
'deep' like in your example. It might be an extreme edge-case for which I cannot
imagine practical usage, but I also don't think the specification disallows this.
Ate
>
> - Jim
> On 4/8/2014 12:26 PM, Ate Douma wrote:
>> On 08-04-14 08:19, Jim Barnett wrote:
>>> Ate,
>>> I'm getting ready to update the spec, and I think that your solution for
>>> computeEntrySet works well. However, I don't understand how
>>> getTransitionDomain is supposed to work. You test whether the source of the
>>> transition is a history state. However that can occur only for the default
>>> entry transition, and I don't think that getTransitionDomain is ever called
>>> on it (the transition is deferenced in computeEntrySet of
>>> addDescendentStatesToEnter.) Futhermore, your version of getTransitionDomain
>>> never dereferences the _target_ of the transition. This may work out fine,
>>> because the real (= dereferenced) target of a transition with a history state
>>> as its target is always a set of substates of the history state's parent
>>> state, so the calculation of the domain may work out correctly if we use the
>>> history state as the target, but I think it would be clearer to explicitly
>>> deference it.
>>>
>> Hi Jim,
>>
>> Thanks for looking into my proposal.
>>
>> I agree that getTransitionDomain won't be called for a transition with a
>> history source. That is: not through the current algorithm.
>> So you may ignore the check for it like I proposed.
>>
>> It is however still useful to keep if you consider the getTransitionDomain as
>> a general purpose function, which for instance can be used 'upfront' like I
>> do, to compile the transition domain already at parse time. I think it makes
>> sense and more clear to keep such check in place.
>>
>> The dereferencing of possible history targets of a transition in
>> getTransitionDomain I would definitely not do.
>> Formally it might be more clearer, but it will have NO benefit, as like you
>> indicated: these can only be targeting substates of the history itself, so for
>> the transition domain calculation have no consequence at all.
>> But more critically, adding history dereferencing would force the
>> getTransitionDomain function to become 'stateful' and thus no longer usable to
>> compile the transition domain upfront.
>>
>> My suggestion would be to just add some comments clarifying such history
>> targets are explicitly and safely ignored in the function description instead.
>>
>> Ate
>>
>>> - Jim
>>>
>>> -----Original Message-----
>>> From: Ate Douma [mailto:ate@douma.nu]
>>> Sent: Wednesday, April 02, 2014 5:27 AM
>>> To: www-voice@w3.org
>>> Subject: Re: test for default history content
>>>
>>> On 02-04-14 00:10, Jim Barnett wrote:
>>>> Ate,
>>>> There is a problem if getTargetStates does not dereference history states.
>>>> computeEntrySet calls it to produce the initial list of states for
>>>> addDescendentStatesToEnter to expand. If getTargetStates doesn't
>>>> dereference history states, they will get added to the statesToEnter
>>>> list before addDescendentStatesToEnter gets called - and history
>>>> states should not be on statesToEnter. Furthermore, computeExitSet
>>>> calls getTargetStates, and it will also need to know what the actual
>>>> dereferenced target state set is.
>>>
>>> Right. And I realize I already solved this differently, and IMO elegantly, in
>>> my implementation :)
>>>
>>> The 'hint' leading to my implementation was the fact that
>>> addDescendantStatesToEnter (also) stores the state parameter in statesToEnter.
>>> And is expected to do so as it recursively is invoked for derived states
>>> which were not yet initially added to the statesToEnter.
>>>
>>> What I thus did instead is the following (in pseudo language):
>>>
>>> procedure computeEntrySet(transitions, statesToEnter, statesForDefaultEntry)
>>> enterableTargets = new OrderedSet()
>>> historyTargets = new OrderedSet()
>>> for t in transitions:
>>> for s in getTargetState(t.target)):
>>> if isHistoryState(s):
>>> historyTargets.add(s)
>>> else
>>> enterableTargets.add(s)
>>> for s in enterableTargets:
>>> addDescendantStatesToEnter(s,statesToEnter,statesForDefaultEntry)
>>> for h in historyTargets:
>>> addDescendantStatesToEnter(h,statesToEnter,statesForDefaultEntry)
>>> // unmodified below
>>> for t in transitions:
>>> ancestor = getTransitionDomain(t)
>>> for s in getTargetStates(t.target)):
>>> addAncestorStatesToEnter(s, ancestor, statesToEnter,
>>> statesForDefaultEntry)
>>>
>>> This way, no history state is added to enterableStates because
>>> addDescendantStatesToEnter only does this for non-history states.
>>>
>>> Note that addAncestorStatesToEnter will work just fine with a history state
>>> as parameter.
>>>
>>> Finally, concerning computeExitSet: this also isn't a problem in my
>>> implementation because I already 'compile' the source of a history transition
>>> to that of its parent state, and actually (thus) can 'compile' the
>>> transitionDomain and the targets of a transition at document load time.
>>>
>>> In pseudo-language in the algorithm, this also can easily be catered for if
>>> you update getTransitionDomain as follows:
>>>
>>> function getTransitionDomain(t)
>>> tstates = getTargetStates(t.target)
>>> if not tstates
>>> return t.source
>>> state = t.source
>>> if isHistoryState(t.source):
>>> state = t.source.parent
>>> if t.type == "internal" and isCompoundState(state) and
>>> tstates.every(lambda
>>> s: isDescendant(s,state)):
>>> return state
>>> else:
>>> return findLCCA([state].append(tstates))
>>>
>>> The above can further be optimized by filtering out the history targets from
>>> being passed to the lambda expression or from the findLCCA(stateList), but it
>>> isn't necessary either.
>>>
>>> With the above minor improvements, the getTargets(transition) as well as the
>>> getTransitionDomain(transition) procedures can remain 'stateless' (not
>>> history state aware) and can be compiled at load time.
>>> If you add history dereferencing to getTargets(transition) this no longer
>>> will be possible, so IMO is something we should try not to do.
>>>
>>>>
>>>> It's a big gap in the algorithm that getTargetStates isn't defined -
>>>> I'm assuming that it was in an earlier version, and got lost somewhere.
>>>>
>>>> In any case we need multiple fixes so that: 1) history states don't
>>>> end up on the statesToEnter list and 2) default history executable content
>>>> gets recorded.
>>>
>>> See my above proposed changes, AFAICT it solves 1) elegantly and then 2) no
>>> longer is an issue (already solved by the earlier update to the algorithm).
>>>
>>> Regards,
>>> Ate
>>>
>>>>
>>>> - Jim
>>>> On 4/1/2014 2:45 PM, Ate Douma wrote:
>>>>> On 29-03-14 20:26, Zjnue Brzavi wrote:
>>>>>> On Sat, Mar 29, 2014 at 1:24 PM, Jim Barnett <1jhbarnett@gmail.com
>>>>>> <mailto:1jhbarnett@gmail.com>> wrote:
>>>>>>
>>>>>> Zjnue,
>>>>>> I agree that we need more tests, but why would
>>>>>> defaultHistoryContent need
>>>>>> to get passed to getTargetStates? It's just an accessor function.
>>>>>> Though I
>>>>>> do think we have to consider how getTransitionDomain and findLCCA should
>>>>>> handle history states. They ignore them at the moment, and
>>>>>> _maybe_ that's ok...
>>>>>>
>>>>>> - Jim
>>>>>>
>>>>>>
>>>>>> Hi Jim,
>>>>>>
>>>>>> Perhaps as quick background, my implementation follows (atm) the
>>>>>> proposed algorithm pretty much verbatim, in order to aid debugging
>>>>>> for cases like this and to make getting started with SCXML a little easier
>>>>>> for myself and others.
>>>>>>
>>>>>> Simply put, the recently published changes to the algorithm for
>>>>>> defaultHistoryContent support are not satisfying test579.
>>>>>>
>>>>>> While the getTargetStates function seems pretty harmless, it is also
>>>>>> hisory-aware and can redirect a transition target.
>>>>>
>>>>> Hi Zjnue,
>>>>>
>>>>> Sorry for chiming in this late, and going back to this earlier
>>>>> message, but I'm puzzled by the above statement.
>>>>>
>>>>> I can find no indication in the algorithm nor in the specification
>>>>> text that the getTargetStates function is supposed to do anything
>>>>> more than just returning the direct target(s) of a transition.
>>>>>
>>>>> It seems to me that the problems you encountered are actually
>>>>> *caused* by the the history-awareness and dereferencing in your
>>>>> getTargetStates implementation.
>>>>>
>>>>> AFAICT the pseudo algorithm expects it will take care of the history
>>>>> dereferencing itself in the addDescendantStatesToEnter procedure.
>>>>> If you do this upfront in you getTargetStates implementation, the
>>>>> addDescendantStatesToEnter never will get to 'see' a history state as
>>>>> it is supposed to, and neither can it then handle the default history
>>>>> content as just was added.
>>>>>
>>>>> I just completed the implementation of the current algorithm for
>>>>> Apache Commons SCXML (although not yet committed), and I now can
>>>>> successfully run test579, so it seems to me the proposed change simply
>>>>> works as expected.
>>>>>
>>>>> But maybe I'm overlooking some other specification requirements for
>>>>> getTargetStates?
>>>>> I'd appreciate some pointers in that case :)
>>>>>
>>>>> Regards, Ate
>>>>>
>>>>>
>>>>>> In the case of test579, the <initial> transition, targets <history
>>>>>> id="sh1">, but is effectively redirected to <state id="s01" >,
>>>>>> skipping any executable content of <history> along the way.
>>>>>>
>>>>>> Please take a look at my code for getTargetStates and getTargetState below
>>>>>> [1].
>>>>>>
>>>>>> It is only with the following two lines present in getTargetState:
>>>>>> if( defaultHistoryContent != null &&
>>>>>> h.parent.exists("id") )
>>>>>> defaultHistoryContent.set(h.parent.get("id"),
>>>>>> h.transition().next());
>>>>>> ..that 579 passes.
>>>>>>
>>>>>> As mentioned, I did not look at it in depth and will not be able to
>>>>>> spend more time on it over the next few days unfortunately.
>>>>>>
>>>>>> So in summary, after adding the published additions to the
>>>>>> algorithm, test579 did not pass.
>>>>>> It was only after the changes to getTargetStates that it did.
>>>>>> Hope this helps for now.
>>>>>>
>>>>>> Thanks,
>>>>>> Zjnue
>>>>>>
>>>>>> [1]
>>>>>>
>>>>>> function getTargetStates( node : Node, ?defaultHistoryContent :
>>>>>> Hash<Iterable<Node>> ) : List<Node> {
>>>>>> var l = new List<Node>();
>>>>>> if( !node.exists("target") )
>>>>>> return l;
>>>>>> var ids = node.get("target").split(" ");
>>>>>> var top = node;
>>>>>> while( top.parent != null && !top.isTScxml() )
>>>>>> top = top.parent;
>>>>>> for( id in ids ) {
>>>>>> var ts = getTargetState(top, id, defaultHistoryContent);
>>>>>> for( tss in ts )
>>>>>> l.add( tss );
>>>>>> }
>>>>>> return l;
>>>>>> }
>>>>>>
>>>>>> function getTargetState( s : Node, id : String,
>>>>>> ?defaultHistoryContent :
>>>>>> Hash<Iterable<Node>> ) : List<Node> {
>>>>>> if( s.get("id") == id )
>>>>>> return [s].toList();
>>>>>> else {
>>>>>> for( child in s.getChildStates() ) {
>>>>>> var ss = getTargetState(child, id, defaultHistoryContent);
>>>>>> if( ss != null )
>>>>>> return ss;
>>>>>> }
>>>>>> for( h in s.history() ) {
>>>>>> var hh = getTargetState(h, id);
>>>>>> if( hh != null ) {
>>>>>> if( defaultHistoryContent != null &&
>>>>>> h.parent.exists("id") )
>>>>>> defaultHistoryContent.set(h.parent.get("id"),
>>>>>> h.transition().next());
>>>>>> return historyValue.exists( h.get("id") ) ?
>>>>>> historyValue.get( h.get("id") ) :
>>>>>> getTargetStates( h.transition().next(),
>>>>>> defaultHistoryContent );
>>>>>> }
>>>>>> }
>>>>>> }
>>>>>> return null;
>>>>>> }
>>>>>>
>>>>>>
>>>>>>
>>>>>> On 3/28/2014 8:51 PM, Zjnue Brzavi wrote:
>>>>>>>
>>>>>>> I've added test579 to the suite. Let me know if there are problems
>>>>>>> with it or if you think there need to be more/different
>>>>>>> tests.--
>>>>>>>
>>>>>>>
>>>>>>> Hi,
>>>>>>>
>>>>>>> Not had a very good look yet, but it appears we'll need to pass
>>>>>>> defaultHistoryContent to getTargetStates as well, as it is another area
>>>>>>> where the algorithm is skipping past some history elements without
>>>>>>> considering their executable content. This diff passes test579 :
>>>>>>> https://github.com/zjnue/hscxml/commit/4b9091470d3c7c1995e6b41900535e0437ec3eb4
>>>>>>>
>>>>>>> Another test or 2 on the subject is probably a good idea.
>>>>>>>
>>>>>>> Best regards,
>>>>>>> Zjnue
>>>>>>
>>>>>> --
>>>>>> Jim Barnett
>>>>>> Genesys
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>
>>>
>>>
>>>
>>
>>
>
Received on Tuesday, 8 April 2014 20:24:49 UTC