Executing statecharts¶

Statechart semantic¶

The module simulator contains a Simulator class that interprets a statechart mainly following SCXML semantic. In particular, eventless transitions are processed before evented transitions, internal events are consumed before external events, and the simulation follows a inner-first/source-state and run-to-completion semantic.

The main difference between SCXML and our implementation comes when considering parallel states. The UML specification defines that several transitions in parallel regions can be triggered by a same event:

“Due to the presence of orthogonal Regions, it is possible that multiple Transitions (in different Regions) can be triggered by the same Event occurrence. The order in which these Transitions are executed is left undefined.” — UML 2.5 Specification

This sometimes implies a non-deterministic choice in the order in which transitions must be processed, and in the order in which states must be exited and/or entered. This problem is addressed in SCXML specification:

“enabledTransitions will contain multiple transitions only if a parallel state is active. In that case, we may have one transition selected for each of its children. [...] If multiple states are active (i.e., we are in a parallel region), then there may be multiple transitions, one per active atomic state (though some states may not select a transition.) In this case, the transitions are taken in the document order of the atomic states that selected them.” — SCXML Specification

However, from our point of view, this solution is not satisfactory. The execution should not depend on the order in which items are defined in some document. Our implementation circumvents this by raising a Warning and stopping the execution if multiple transitions can be triggered at the same time. To some extent, this is the same approach than in Rhapsody:

“Rhapsody detects such cases of nondeterminism during code generation and does not allow them. The motivation for this is that the generated code is intended to serve as a final implementation and for most embedded software systems such nondeterminism is not acceptable.” — The Rhapsody Semantics of Statecharts

However, their approach only concerns conflicting transitions that are not fired in an orthogonal state. In orthogonal states, the order in which transitions are triggered in still non-determinist:

“The order of firing transitions of orthogonal components is not defined, and depends on an arbitrary traversal in the implementation. Also, the actions on the transitions of the orthogonal components are interleaved in an arbitrary way.” — The Rhapsody Semantics of Statecharts

To avoid such situations and to avoid defining arbitrary order on the execution, we decided to allow event to trigger at most one transition at a time. As a consequence, this means that parallel states execution should be “event-independant”, ie. a same event cannot trigger two (or more) transitions in distinct parallel state’s substates.

There are several workarounds. For instance, one can define a shared object in the context of an evaluator that allows parallel states to communicate and to synchronize. Or, at a statechart level, one can define an additional parallel state that resends events for each other parallel state (ie. if the received event is e1, it raises an internal event e1_i for each other parallel region i). Finally, the restriction we implemented can also be overridden by subclassing the simulator, as our implementation already consider that multiple transitions could be fired at once (see Implementing other semantics).

While it seems radical, our approach respects the UML specification which requires that the designer does not rely on any particular order for event instances to be dispatched to the relevant orthogonal regions.

Using Simulator¶

A Simulator instance is constructed upon a StateChart instance and an optional callable that returns an Evaluator (see Code contained in statecharts). If no evaluator is specified, PythonEvaluator class will be used.

Consider the following example.

from pyss.simulator import Simulator
from pyss.model import Event

simulator = Simulator(my_statechart)
# We are now in a stable initial state
simulator.send(Event('click'))  # Send event to the simulator
simulator.execute_once()  # Will process the event if no eventless transitions are found at first

For convenience, send() returns self and thus can be chained:

simulator.send(Event('click')).send(Event('click')).execute_once()

Notice that execute_once() consumes at most one event at a time. In this example, the second click event is not processed.

To process all events at once, repeatedly call execute_once() until it returns a None value. For instance:

while simulator.execute_once():
  pass

As a shortcut, the execute() method will return a list of MacroStep instances obtained by repeatedly calling execute_once():

from pyss.simulator import MacroStep

steps = simulator.execute()
for step in steps:
  assert isinstance(step, MacroStep)

Notice that a call to execute() first computes the list and then returns it, meaning that all the steps are already processed when the call returns.

As a call to execute() could lead to an infinite execution (see for example simple/infinite.yaml), an additional parameter max_steps can be specified to limit the number of steps that are computed and executed by the method.

assert len(simulator.execute(max_steps=10)) <= 10

At any time, you can reset the simulator by calling reset().

For convenience, a StateChart has an events() method that returns the list of all possible events that can be interpreted by this statechart (other events will be consumed and ignored).

This method also accepts a state name or a list of state names to restrict the list of returned events, and is thus commonly used to get a list of the “interesting” events:

print(my_statechart.events(simulator.configuration))

The main methods and attributes of a simulator instance are:

class pyss.simulator.Simulator(statechart: pyss.model.StateChart, evaluator_klass=None)¶

A discrete simulator that interprets a statechart according to a semantic close to SCXML.

Parameters:	statechart – statechart to interpret evaluator_klass – An optional callable (eg. a class) that takes no input and return a evaluator.Evaluator instance that will be used to initialize the simulator. By default, an evaluator.PythonEvaluator will be used.

configuration¶

List of active states names, ordered by depth.

execute(max_steps: int=-1) → list¶

Repeatedly calls execute_once() and return a list containing the returned values of execute_once().

Notice that this does NOT return an iterator but computes the whole list first before returning it.

Parameters:	max_steps – An upper bound on the number steps that are computed and returned. Default is -1, no limit. Set to a positive integer to avoid infinite loops in the statechart simulation.
Returns:	A list of MacroStep instances

execute_once() → pyss.simulator.MacroStep¶

Processes a transition based on the oldest queued event (or no event if an eventless transition can be processed), and stabilizes the simulator in a stable situation (ie. processes initial states, history states, etc.).

Returns:	an instance of MacroStep or None if (1) no eventless transition can be processed, (2) there is no event in the event queue.

reset()¶

Reset current simulator to its initial state. This also resets history states memory.

running¶

Boolean indicating whether this simulator is not in a final configuration.

send(event: pyss.model.Event, internal: bool=False)¶

Send an event to the simulator, and add it into the event queue.

Parameters:	event – an Event instance internal – set to True if the provided Event should be considered as an internal event (and thus, as to be prepended to the events queue).
Returns:	self

Macro and micro steps¶

The simulator is fully observable: its execute_once() (resp. execute()) method returns an instance of (resp. a list of) MacroStep. A macro step corresponds to the process of consuming an event, regardless of the number and the type (eventless or not) of transitions triggered. A macro step also includes every consecutive stabilization step (ie. the steps that are needed to enter nested states, or to switch into the configuration of an history state).

A MacroStep exposes the consumed event (Event) if any, a (possibly empty) list of transitions (Transition and two sequences of state names: entered_states and exited_states. States order in those list indicates the order in which their on entry and on exit actions were processed.

class pyss.simulator.MacroStep(main_step: pyss.simulator.MicroStep, micro_steps: list)¶

A macro step corresponds to the process of a Transition (given an Event or in case of an eventless transition). A MacroStep contains one main step (the one who processes the transition) and a (possibly empty) list of stabilization steps.

Parameters:	main_step – Main (MicroStep instance) step. micro_steps – A possibly empty list of MicroStep instances (stabilization steps).

entered_states¶

List of the states names that were entered.

event¶

Event (or None) that were consumed.

exited_states¶

List of the states names that were exited.

transitions¶

A (possibly empty) list of transitions that were triggered.

The main step and the stabilization steps of a macro step are exposed through main_step and micro_steps. The first is a MicroStep instance, and the second is an ordered list of MicroStep instances. A micro step is the smallest, atomic step that a statechart can execute. A MacroStep instance thus can be viewed (and is!) an aggregate of MicroStep instances.

class pyss.simulator.MicroStep(event: pyss.model.Event=None, transitions: list=None, entered_states: list=None, exited_states: list=None)¶

Create a micro step. A step consider event, takes transitions and results in a list of entered_states and a list of exited_states. Order in the two lists is REALLY important!

Parameters:	event – Event or None in case of eventless transition transitions – a list of transitions or None if no processed transition entered_states – possibly empty list of entered states exited_states – possibly empty list of exited states

This way, a complete run of a state machine can be summarized as an ordered list of MacroStep instances, and details of such a run can be obtained using the MicroStep list of a MacroStep.

Advanced uses¶

A Simulator makes use of several protected methods for its initialization or to compute which transition should be processed next, which are the next steps, etc.

These methods can be easily overriden or combined to define other semantics.

class OuterFirstSimulator(Simulator):
    def __init__(self, *args, **kwargs):
        super().__init__(self, *args, **kwargs)

    def _actionable_transitions(*args, **kwargs):
        transitions = super()._actionable_transitions(*args, **kwargs)
        transitions.reverse()
        return transitions

def send(self, event:model.Event, internal=False):
   self.append(event)  # No distinction between internal and external events
   return self