Compute Flattened State Transition Map

This algorithm computes the state transitions for the flattened state machine corresponding to a state machine definition.

Input

1. A state machine definition smd.

2. A state machine analysis data structure sma representing the results of analysis so far.

Output

1. sma with the flattened state transition map updated.

Diagrams

The following diagrams illustrate how state transitions are flattened.

State Transitions to States

Figure 1 shows how state transitions to states are flattened. S1 is a state with substates S2 and S3. S4 is a state with substate S5. It has an initial transition specifier with do actions A' and destination S5. (That is, whenever we transition to S4, we immediately do actions A' and transition to S5.)

The solid left-to-right arrow represents a transition T in the hierarchical state machine from S1 to S4 with do actions A. In the flattened state machine, T generates each of the transitions represented by the dashed arrows. For each dashed arrow, the action list is the concatenation of the action lists shown. In these lists, exit(S) represents the list of exit functions specified by S, and similarly for entry(S).

Figure 1. State transitions to states.

Note the following:

1. Each transition in the flattened state machine goes from a leaf state to a leaf state.

2. In general, T generates the transitions out of S2 and S3 as shown. However, if the hierarchical state machine specifies a transition T' out of S2, and T' is triggered by the same signal as T, then T' overrides T; and similarly for a transition T'' out of S3. This behavior is called behavioral polymorphism, and it must be respected in the algorithm that generates the flattened transitions.

State Transitions to Junctions

Figure 2 shows how state transitions to junctions are flattened. Again S1 is a state with substates S2 and S3. S4 is a state with a junction definition J. The solid left-to-right arrow represents a transition in the hierarchical state machine from S1 to J with actions A. In the flattened state machine, it generates each of the transitions represented by the dashed arrows.

Figure 2. State transitions to junctions.

Note the following:

1. Each transition in the flattened state machine goes from a leaf state to a junction, which is a leaf in the AST.

2. Junctions do not have entry actions or substates.

3. Again the transition out of S2 will be be overridden if there is a transition specified in S2 on the same signal, and similarly for S3.

Procedure

Visit each of the state definitions in smd, walking the AST in depth-first order.

Visiting State Definitions

1. Let sd be the state definition being visited.

2. Let S be the set of leaf state definitions under sd in the AST. (If sd itself is a leaf state definition, then S contains sd as its only element.)

3. For each state transition specifier sts in sd

   1. Let s be the signal of sts.

   2. Let A be the actions of sts.

   3. Let soj be the state or junction that is the destination of sts.

   4. For each state definition sd' in S

      1. Construct the transition t from sd' to soj with actions A

      2. If the flattened state transition map has no entry for sd', then map sd' to the map that takes s to t

      3. Otherwise

         1. Let M be the map corresponding to sd' in the flattened state transition map.

         2. Update M so that it maps s to t. If there is any preexisting transition mapped to s, it is overridden. Because we walk the AST in depth-first order, a transition specified lower in the tree overrides any transition on the same signal specified higher in the tree. Thus the algorithm respects behavioral polymorphism.