UML Statechart to Simple Statechart

This is another popular example for model transformations – the flattening of a UML statechart. UML statechart, in addition to simple states (those used in the mathematical concept of FSM) contains also composite states of two kinds – sequential or OR-states (containing just one region) and concurrent or AND-states (containing more than one region). A similar example was first used in [1] to demonstrate the GReAT transformation language. We use here a version where the statechart can contain only sequential composite states (OR-states in terms of [1]). Therefore the metamodel does not contain the Region concept at all. Composite states may contain any type of states – composite, simple, initial or final, with an arbitrary nesting level. Such a statechart must be transformed into an equivalent “flat” statechart (which contains only simple states). The informal flattening algorithm is well known (most probably, formulated by D. Harel [2]).

The simplified metamodel of the “full” (hierarchical) statechart is depicted in Fig. 1. There are some constraints to the metamodel specifying what is a valid statechart. There are “normal” transitions for which the event name is nonempty and “special” ones with empty event. These empty transitions have a special role for state structuring. Each composite state must contain exactly one initial state (an instance of Init) and may have several final states. There must be exactly one empty transition from the initial state of a composite state (leading to the “default” internal state). The same way, there must be exactly one empty transition from the composite state itself  - the default exit. This exit is used when a contained final state is reached. Otherwise, transitions may freely cross composite state boundaries and all other transitions must be named. Named transitions from a composite state have a special meaning (the “interrupting” events), they actually mean an equally named transition from any contained “normal” state – not initial or final. This is the most used semantics of composite states (there are also some variations).

Fig.1. Metamodel of hierarchical statechart

All states have names – but those for initial and final states actually are not used. Names are unique only within a composite state (it acts as a namespace) and at the top level.

The traditional flattening algorithm is formulated in a recursive way. Take a topmost composite state (i.e., one not contained in another composite state). There are three ways how transitions related to this state must be modified:

1.     Transitions entering the composite state itself must be redirected to the state to which the empty transition from its initial state leads.

2.     Transitions leading to a final state of this composite state must be redirected to the state to which the empty transition from the composite state leads.

3.     Named transitions from the composite state must be converted into a set of equally named transitions from all its “normal” states (with the same destination)

Then the name of the composite state must be prefixed to all its contained normal states and the composite state must be removed (together with its initial and final states and involved empty transitions). All this must be repeated until only simple states (and top level initial/final ones) remain.

A simple analysis of this algorithm shows that the redirection of transitions may be done independently of the composite state removal – you can apply the three redirection rules until all transitions start/end at simple states (or top initial/final). The set of simple states is not modified during the process – only their names are modified.

Namely this modified algorithm is implemented in the MOLA program in Fig. 2. It contains two top-level WHILE loops – the first one performs the transition redirection and the second – the removal of composite states.

Both top-level loops are WHILE-type – especially, in the first loop a transition may be processed several times until its source and destination states reach their final position. Therefore transition processing cannot be done directly by a FOREACH loop, which cannot process one instance more than once.

The program performs a model update – source and target metamodels coincide, simply, some metaclasses cannot have instances in the target model. Mapping associations are not used in this example.

The first loop contains three loop head statements – all specify the instance t:Transition as a loop variable, but with different selection conditions. According to the semantics of MOLA, any Transition instance satisfying one of the conditions (one at a time!) is taken and the corresponding rule is applied (note that the conditions are not mutually exclusive). All this is performed until none of the conditions applies – then all transitions have their final positions. The first two rules contain a dashed line – the association (link) removal symbol. The link is used in the selection condition, but then removed by the rule. The third path through the loop contains the instance removal symbol.

Namely the use of several lop heads per loop is a strength of MOLA – this way inherently recursive algorithms can be directly implemented by WHILE loops.

The second loop – the removal of composite states also has a recursive nature to a certain degree – it implements the so-called transitive closure with respect to finding the deepest constituents (simple states) and computing their names accordingly to the path of descent.

It shows that transitive closure can be implemented in MOLA in a natural way (even the FOREACH loop could be used for this). The other constructs in this loop are “traditional” – except, may be, the fact that several instances may be deleted by a rule in MOLA.

This version of transformation is part of  the paper on MOLA at MDAFA 04, Linkoping .

 

 

Fig.2. Statechart flattening

Since the WHILE loop is not yet implemented in the MOLA tool, another version of the transformation is also presented here, which can be already executed. There FOREACH loops in conjunction with recursive calls are used to implement this recursive algorithm. Actually, for implementing a transitive closure recursive subprogram calls are as natural as WHILE loops in MOLA.

In addition, in order to make the transformation testing easier, a GMF-based simple editor for statecharts has been built. To use this editor, the transformation definition had to be slightly extended too. The metamodel is extended by the Statechart class itself. The transformation program, reformatted into two recursive subprograms TransitionFlattening and StateFlattening, contains also the third subprogram TransformChart, which has mainly a "scaffolding" role for organizing the model import and export from/to the editor.

The modified metamodel:

(the Modification class is used to emulate the While loop by the ForEach one)

 

The main program:

 

The TransitionFlattening subprogram:

 

The StateFlattening subprogram:

 

The TransformChart subprogram:

 

The statechart editor (displaying an example statechart to be transformed) is the following:

 

The transformation result for this example is the following:

 

 

 

 

 

References

1. Agrawal A., Karsai G, Shi F. Graph Transformations on Domain-Specific Models. Technical report, Institute for Software Integrated Systems, Vanderbilt University, ISIS-03-403, November 2003.

2. Harel D. Statecharts: a Visual Formalism for Complex Systems. Sci. Comput. Program. Vol 8, pp. 231-274, 1987.

3.