RE: Event handling problem

Stefan,

 SCXML will go into infinite loops in both your examples.  The possibility of such loops is part of the nature of state machines and is also part of Harel State Charts, upon which SCXML is based.  Furthermore, the infinite loops would have occurred in the earlier draft's semantics as well.  That draft was specified in terms of 'phases', but that was intended only as a notational convenience.  (The concept of 'phases' was borrowed from the VXML form interpretation algorithm, and some people found it easier to understand the algorithm that way.)   In the previous draft, the algorithm effectively looped in the 'immediately enabled transitions' phase until no new eventless transitions or internal events or external events were found (note that at the end of the 'enter states phase' there was a goto back to the 'immediately enabled transitions phase', and the 'immediately enabled transitions phase' first checks for eventless transitions).  So the behaviour would be the same: if state1 has a conditionless transition going to state2 and state2 had a transition going back to state1, the algorithm would loop on those transitions forever, without ever checking the internal or external event queues.  

 

In general, the only solution for infinite loops is for the script author to avoid them.    However, if you want, your implementation can implement and extension to test for them and halt the machine after some number iterations.  

 

- Jim

 

________________________________

From: www-voice-request@w3.org [mailto:www-voice-request@w3.org] On Behalf Of Stefan Maton
Sent: Thursday, June 12, 2008 3:39 AM
To: www-voice@w3.org
Subject: Event handling problem

 

Hi everyone,

 

My SCXML C++ implementation has gone public and I already have a problem which is not easy to solve. In fact it's a little bit more tricky to explain because it's related to the way the events are handled within the state machine.

 

Let's lay out what one would like to do:

 

a) A user presses a button.

b) The button generates an event, which is injected into the state machine.

c) You call startEventLoop in the state machine.

d) The state machine handles the event, triggering the a <send>-tag one has put into his scxml.

e) The <send>-tag injects the event into the state machine.

f) The state machine should handle the newly injected event.

 

Let's lay out how my SSCXML works:

 

I) a) and b) occur. c) is called.

II) The state machine first checks all transitions that don't need any event.

III) d) is done -> any event is handled. This is done by first handling all events in the internal event queue and then handling all events in the external event queue.

IV) During III) your <send>-tag injects the event. This event is put into a list representing the "new" part of the external event queue (note that if you specify "scxml" as targettype, the event is put into a list representing the "new" part of the internal event queue).

V) Once all events have been handled, the "new" part queues are merged with their "current" queue counterpart.

VI) The update finishes.

 

What is the result of this way of handling the event queue? Well... if you inject a new event during the current frame, the event is put into a "new events" list. Once all current frame events are handled, the "new events" list is merged with the "current frame" list. The new events are *not* handled in the current frame. They will be handled ONE frame later (next update call).

 

In fact, this is the way the previous SCXML draft stated the handling. One had to merge the new events with the old ones at the end of the update. At least that's how I understood it.

 

Since I implemented the event handling before the new draft was put online, SSCXML has the old handling.

 

Now the current draft states this: The update function has to loop internally, until no internal and external events are left (unless they're timed events in which case the state machine may ignore them to determine whether to continue the loop or not) and until no more transitions can be taken.

 

Now, what does that mean? This means 2 things:

 

1. If you have states that have transitions which are i.e. condition less, they are always triggered, keeping the state machine busy forever.

 

Example (shortened for more clarity):

<state id="root">

  <state id="1">

    <transition target="2" />

  </state>

  <state id="2">

    <transition target="1" />

  </state>

</state>

The above example would create an infinite loop in the state machine, resulting in never coming back, freezing your application within the update of the state machine.

 

2. Imagine your state machine is set up in a way that you send an event. And that event would be put directly into the event queue resulting into the event being handled within the same frame. Now, due to this event a transition is triggered which contains a <send> itself, resulting in putting it into the event queue. That <send> in fact is re-triggering the first <transition> containing the first <send>... it's basically the same example as the first example but only with <send> tags. Your state machine would freeze within the update function.

 

I must admit that I came across this problem only today because I didn't re-read the drafts new event handling algorithm. But as you can see, the new way raises some problems.

 

In my current implementation the new event is handled 1 frame later (which might and will create some delay in reaction to those events). This will not freeze the entire application within an update of the state machine but will let run the rest of the application as expected. The "only drawback" is the delay.

 

Perhaps I have misunderstood your algorithm, but I don't think so. How would the current algorithm handle those infinite loop situations?

 

Thanks,

Stefan

 

---------------------------------------------------

Sidéma

Rue Lefin 4, 4860 Pepinster, Belgique

Web: http://www.sidema.be

Email: maton@sidema.be

GSM: ++32 (0)494 / 11.53.65

TVA BE 0713.367.395