A Simple State Machine

UIs, States and State Machines

Graphic user interfaces usually have certain internal states, e.g. which widgets are active, editable, visible. This can be seen from two distinct perspectives:

  • UI state is composed of internal states of all its elements. When handling user input or other events, relevant element states are considered to control behaviour of the event handler method. This works for simple UIs but isn’t really maintainable and scalable.
  • UI state is represented explicitely. States of its elements are understood as a consequence of the overall UI state. All events coming from users or the underlying system are routed to a state machine that reacts accordingly. Thereby, depending on the actual state, methods can be executed and UI state can be changed. A change of state usually also results in internal state changes of the UI elements.

Different formalisms exist for describing state models as finite automata. Often subsets of UML State Charts are used.

The most simple realization consists of nested if or case expressions that select the executing code based on the actual state and the triggering event. This gets quite confusing for somewhat more complex state models. Therefor a few patterns for different implementation environments and functional requirements emerged. Plenty of literature can be found on the internet:

In Java from version 8 and in Groovy, lambda expressions resp. Closures are available. They support (among other things) to store functionality in data structures. This allows a compact implementation of state machines loosely following the Methods for States pattern. Core part is a map with keys that are calculated from the current state and the arriving event and closures as values. So every legal combination of current state and arriving event selects the closure that implements the required functionality.

A better characterization for the implementation described here and used in the example would be Closures for Transitions.

Basic concepts:

  • Even complex UML State Charts with hierarchically decomposed states can be expressed with „elementary transitions“ that lead from one not decomposed, „primitive“ state to another primitive state. A transition in the original model, leading to and/or from a compound state will be in most cases implemented as several elementary transitions.

    UML State Chart graphik from Wikipedia
    State Chart compound states (from Wikipedia)
  • Activities specified in the State Chart can be implemented neatly in transition closures:
    • At first all exit() activities of the left states „inside out“ – {a(), b()}.
    • Next the activity bound to the transition – {T()}.
    • Finally entry() activities and activities bound to transitions inside the compound target state – {c(), d(), e()}.
    • Internal transitions can be implemented as transitions with identical start and target state and without exit() and entry() activities.
  • Even Guards and Choices are easily implemented, if transition closures can modify the target state of the transition.
    UML State Chart Graphic from Wikipedia
    State Chart with Guards and Choice pseudo-states (from Wikipedia)
    • Guards are evaluated before executing any activity. If they evaluate to false, the current state is not modified and no activity is executed.
    • Choices are evaluated after executing exit()- and transition activities. They can change the target state and thus the executed entry() activities

Implementation in Groovy

An implementation is available on GitHub. Also see GroovyDoc.

package de.geobe.util.statemachine
/**
 * Implementation of a state machine with these features
 * 
<ul>
<li>States as enums,</li>

 * 
<li>Events as enums,</li>

 * 
<li>Transitions are triggered by a combination of current state and event,</li>

 * 
<li>they can be guarded by a Closure inhibiting their execution,</li>

 * 
<li>onExit activities executed when leaving a state,</li>

 * 
<li>internal activities triggered by an event without state change.</li>

 * 
<li>onEntry activities executed when entering a state,</li>

 * 
<li>transitions activities executing after leaving a state and before entering a following state.
 * They can return a target state changing the following state.</li>
</ul>

 * @author georg beier
 * @param S enumertion Type for States. Limited by current implementation to 4095 values.
 * @param E enumeration type for events
 */
//@Slf4j
class StateMachine<S extends Enum, E extends Enum> {
    /** map of closures as entry actions */
    private Map<S, Closure> onEntry = new HashMap<>()
    /** map of closures as exit actions */
    private Map<S, Closure> onExit = new HashMap<>()
    /** Map of all transitions with guards and actions */
    private Map<Integer, List<TxDef<S>>> transitions = new HashMap<>()
    /** store current state */
    private S currentState
    /** for logging info to identify state machine instance */
    private String smid

    def getCurrentState() { currentState }

    def setSmId(String id) { smid = id }

    /**
     * create instance with initial fromState
     * @param start initial fromState
     * @param id identifying string for logging and debug
     */
    StateMachine(S start, String id = 'default') {
        currentState = start
        smid = id
    }

    /**
     * Add a transition to the state machine linking two states. It is not guarded, i.e. its guard is always true.
     * @param from the state, from where transition starts
     * @param to the state, where transition leads to. May be same as from state.
     * @param ev the event that triggers this transition
     * @param action (optional, default is do nothing) Closure that is executed during the transition. It may return
     * a different target state that overwrites to parameter. Thus branching transitions can be easily implemented.
     * Closure may have parameters of type Object...
     */
    void addTransition(S from, S to, E ev, Closure action = {}) {
        addGuardedTransition(from, to, ev, { true }, action)
    }

    /**
     * Add an "internal" transition that does not leave its state but executes some activity.
     * @param inState State in which this transition may happen
     * @param ev the event that triggers this transition
     * @param action Closure that is executed during the transition. Closure may have parameters
     * of type Object... .
     * @param guard (optional, default true) Closure that controls execution of the activity.
     * Only when it returns (Groovy-) true, activity is executed
     */
    void addInternalActivity(S inState, E ev, Closure action, Closure guard = { true }) {
        addGuardedTransition(inState, null, ev, guard, action)
    }

    /**
     * Add a transition to the state machine linking two states
     * @param from the state, from where transition starts
     * @param to the state, where transition leads to. May be same as from state.
     * @param ev the event that triggers this transition
     * @param guard Closure that controls execution of the transition. Only when it returns (Groovy-) true,
     * transition is executed
     * @param action Closure that is executed during the transition. It may return a different target state that
     * overwrites to parameter. Thus branching transitions can be easily implemented. Closure may have parameters
     * of type Object... .
     */
    void addGuardedTransition(S from, S to, E ev, Closure guard, Closure action = {}) {
        def index = trix(from, ev)
        if (!transitions[index]) {
            transitions[index] = []
        }
        TxDef<S> tx = new TxDef<>([start: from, target: to, action: action, guard: guard])
        transitions[index].add tx
    }

    /**
     * Add an onEntry activity to the state machine that is executed each time a transition enters
     * the state, even if it comes from the same state.
     * @param state which gets the activiy. Only one entry activity per state is supported
     * @param action Closure that implements the activity. Must not have parameters.
     */
    void addEntryAction(S state, Closure action) {
        onEntry[state] = action
    }

    /**
     * Add an onExit activity to the state machine that is executed each time a transition leaves
     * the state, even if it leads back to the same state.
     * @param state which gets the activiy. Only one exit activity per state is supported
     * @param action Closure that implements the activity. Must not have parameters.
     */
    void addExitAction(S state, Closure action) {
        onExit[state] = action
    }

    /**
     * Actions are identified by currentState and incoming event.
     * Execute first matching action with a guard delivering (Groovy-) true.
     * If none is found, no action is executed and state stays unchanged.
     * After execution, statemachine will be
     * 
<ul>
<li>in the following state as defined in addTransition method,
     * if closure returns no object of type S</li>

     * 
<li>in the state returned by the closure.</li>

     * 
<li>If no following state is defined, statemachine will stay in currentState and
     * no exitAction should have been executed.</li>
</ul>

     * @param event triggering event
     * @param params optional parameter to Action.act.
     *        Caution, Action.act will receive an Object[] Array
     * @return the current state after execution
     */
    S execute(E event, Object... params) {
        def index = trix(currentState, event)
        if (transitions[index]) {
//            S fromState = currentState
            List<TxDef<S>> txlist = transitions[index]
            // find first with guard evaluating to true
            TxDef<S> tx = txlist.find {
                it?.guard() ? true : false
            }
            if (tx?.target) {
                // full transition
                onExit[tx.start]?.call()
                def result = tx.action?.call(params)
                def next
                if (result instanceof S) {
                    next = result
                } else {
                    next = tx.target
                }
                currentState = next
                onEntry[next]?.call()
                log.debug("Transition $smid: $fromState--$event->$next")
            } else {
                // inner transition
                tx?.action?.call(params)
                log.debug("Inner Transition $smid: $fromState--$event->$currentState")
            }
        } else {
            log.warn("ignored event $event in fromState $currentState")
        }
        currentState
    }

    /**
     * calculate a unique transition index from current state and triggering event
     * @param st current state
     * @param ev event triggering transition
     * @return a unique Integer computed from state and event
     */
    private static Integer trix(S st, E ev) {
        def t = st.ordinal() + (ev.ordinal() << 12)
        t
    }

    /**
     * supporting data structure to store transition information
     * @param <S> the state enumeration type
     */
    private static class TxDef<S> {
        S start
        S target
        Closure guard = {}
        Closure action = {}
    }
}

Comments on Code

Lines 20, 22, 24, 26 and 164
Core data is held in three maps: A list of transitions or internal activities that may be triggered by the arriving event, starting from currentState (26), is stored in transitions(24). The map key is calculated from currentState and event (164).
Maps onEntry(22) and onExit(24) can optionally store entry and exit activities as Closures for all states.
Lines 53, 66 and 81
State machine reactions on incoming events are configured by adding all transitions and internal activities. Transitions and internal activities can be optionally guarded by a Closure (66, 81). Therefor, more than one transition or internal activity can be added for any combination of starting state and event. They will be stored sequentially in a list inside the transition map. Because the first entry in this list with its guarding Closure returning true will be executed, the sequence of adding guarded transitions matters! Transitions added first will be considered first.
Lines 96 and 106
Activities to be performed on entering or leaving a state can be added here as Closures. They are not executed for internal activities.
Line 125
State machine is used by calling method execute(...) with the triggering event and optionally additional parameters. This method executes the addressed closure and determines the next state.
Lines 131-132
Find first transition or internal activity with guard returning true.
Lines 134-151
The next state is calculated by these rules:

  1. If the transition has no target state defined, it is considered an internal activity and the currentState will not be changed (149-150)
  2. else if the activity closure returns a legal state, it will be taken as next state (140)
  3. else the next state is taken from the transition (142).
Line 164
The transition index is calculated as sum of the ordinal value of the st State enum and the ordinal value of the ev Event enum shifted left by 12 bits. Thus 212 States are supported.
Lines 173-178
Transition information is stored in this data structure.