- From: Jim Barnett <1jhbarnett@gmail.com>
- Date: Tue, 08 Apr 2014 15:36:59 -0400
- To: www-voice@w3.org
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.
- 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
>>>>>
>>>>>
>>>>
>>>>
>>>
>>
>>
>>
>
>
--
Jim Barnett
Genesys
Received on Tuesday, 8 April 2014 19:37:34 UTC