Re: More Problems with Preemption

I agree that that solution would fix this precise problem but that solution
would essentially be too restrictive in general.

The goal is to avoid transitions that could interact with each other while
allowing transitions that happen in logically distinct sections of the
state graph to continue.

I think a far better specification, and one that fits with existing
understanding of state machines and transitions would be to check if two
transitions affect the same state subgraph and if they do then take the
first in document order.  Note that this drops the arbitrary and unclear
type distinctions for the most part.


Going further with this definition, the full and I believe correct solution
would look like:


procedure getTransitionSubgraph( transition ):
    targets = getTargetStates(transition.targets);
    if targets.empty():
        return transition.source;
    if transition.type == "internal" and isCompoundState(transition.source)
and targets.every(lambda s: isDescendant(s,transition.source)):
        return transition.source
    else:
        return findLCCA([transition.source].append(targets)
 procedure isPreempted( existing, next ):
    if !existing.target:
        return false;

  existingRoot = getTransitionSubgraph( existing )
    nextRoot = getTransitionSubgraph( existing )
  if  existingRoot == nextRoot
         or isDescendant(existingRoot,nextRoot)
         or isDescendant(nextRoot,existingRoot):
  return true;
  return false;


Note that the getTransitionSubgraph procedure can be used to replace
similar code in EnterStates as well as in ExitStates.

I have this exact solution running and working in an SCXML implementation
right now, so I know it work for some large subset of cases and correctly
runs the test case that Gavin first posted

Chris Nuernberger


On Thu, Feb 7, 2013 at 12:17 AM, David Junger <tffy@free.fr> wrote:

> Le 6 feb 2013 à 23:26, Gavin Kistner a écrit :
>
> > A colleague of mine created a pathological preemption case to show
> problems with the current system. Consider:
> >
> > <scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0">
> >   <parallel id="p0">
> >     <onentry><raise event="e"/></onentry>
> >     <state id="s0">
> >       <parallel id="p1">
> >         <state id='p1s0'><transition event='e' target='s0a'/></state>
> >         <state id='p1s1'><transition event='e' target='s0b'/></state>
> >       </parallel>
> >       <state id="s0a"/>
> >       <state id="s0b"/>
> >     </state>
> >   </parallel>
> > </scxml>
> >
> > The event 'e' causes both transitions to be chosen by
> selectTransitions(). Both are 'type 2' transitions, and so the logic in
> preemptsTransition() causes neither to preempt the another. Both transition
> targets are entered, and now the state machine is in an invalid
> configuration where both s0a and s0b are active.
> >
> > Is there a simple fix to the preemption logic for this? Or do we need to
> consider to simpler, more robust solution for determining whether the
> subgraphs affected by transitions overlap?
>
> This may happen because the definition is not precise enough. Both
> transitions in state p1 are indeed "within a single child of <parallel>"
> state p0. But they are not Type 2 relative to their closest <parallel>
> ancestor (p1), which is what should matter.
>
>                         David
>



-- 
A foolish consistency is the hobgoblin of little minds - Emerson