A Lightweight Implementation of UML Statecharts in C++

• Download demo project - 19.3 KB
• Download source - 7.5 KB

Introduction

This statechart "engine" (implemented as a C++ template class) implements the most commonly used aspects of UML statecharts. All you need to do is define an array of states and implement event checking and handling methods. Then call the engine when an event occurs. The engine calls your event checking and handling methods in the correct order to figure out what event happened, and tracks the current state.

This is a lightweight implementation that compiles under Visual Studio 2005 and, with some slight modifications, under VC++ 6.0. This implementation requires less statechart-related housekeeping code than other C++ implementations. (See Miro Samek's, for example.)

Background

Statecharts were developed by David Harel to add nesting and other features to flat state machines. (See David Harel, "On Visual Formalisms", Communications of the ACM, Vol. 31, No. 5, pp 514-530, 1988.) Statecharts were later added to the Unified Modeling Language (UML) and standardized. They are an excellent tool for modeling classes, sub-systems and interfaces that have many distinct states and complex transitions among them.

My personal need for them arose while implementing a software interface between two real-time, embedded systems that controlled separate machines requiring physical synchronization. I have also used them for modeling and implementing user interfaces that featured many modes.

The following is a brief summary of the notation and behavior of statecharts. For a full presentation of the UML statechart notation, see the UML 2.0 specification available here.

Graphically, UML shows states as boxes with rounded corners, and transitions as arrows between boxes. (See Figure 1.) The transitions are labeled with the event that causes the transition, optionally followed by a forward slash, and the action(s) that will be taken upon transition. A condition, called a "guard," can be indicated in square brackets. If the event happens, the guard condition is evaluated and the transition is taken only if the condition is true.

States can be nested (See Figure 2.), which allows high-level events to invoke transitions that leave any of several states with just one arrow. The use of so-called "composite" states keeps statechart diagrams much simpler than what flat state machines would require. Even though states can be nested, the system must always transition to some simple (i.e. non-composite) state.

A solid circle at the beginning of an arrow indicates a default start state. A statechart must have at least one default start state designated, indicating the initial state of the system. If any transition -- including a default one -- ends on a compound state, then there must be a default state designation inside that compound state, and so on, eventually leading to a simple state. One exception to this is described below.

States can have internal transitions that do not take the system to another state, yet do have associated actions. These are shown inside the state where they are handled. Compound states may also have internal transitions. Two special internal transitions are "entry" and "exit." These are executed upon entry to, and exit from, the corresponding state. This allows common actions such as initialization and destruction to be expressed one time, rather than as actions on every event leading to/from a state. Custom internal events can also be specified.

If a transition takes the system across several state boundaries, the various actions are executed in the following order:

1. The exit action(s) of all states that must be exited
2. The action specified on the transition arrow
3. The entry action(s) for all states that are entered

Statecharts allow a transition to return to a previous state within a composite state, without requiring that you specify what state you were in previously. This is represented by a transition arrow that ends in an encircled "H" for "history." (See Figure 3.) For example, say an event can be handled from any of two simple states within a compound state. If you show a transition from the compound state, back inside it to the encircled "H," this means "handle the event and return to the state you most recently left." That is much simpler than showing two (or more) transitions with identical event/action labels.

There are two kinds of history returns in UML statecharts: shallow and deep. Shallow transitions (indicated by an "H") return to the most recently exited state at the level where the "H" is shown. If that does not lead to a simple state, then it is an error. Deep history (indicated by an "H*") means that the system will return to the most recent simple state within the compound state that it most recently exited. So, if the system in Figure 3 was in state A when event x happened, the system would return to state A.

Using the Code

This implementation supports state nesting, entry, exit and custom internal events, default states and deep history transitions. If a history return cannot find a recently exited state at a given level, it will try to use default state designations to get the system to a simple state. Only failing that will it be considered an error.

This implementation does not currently support orthogonal states, factored transition paths, forks, joins, synch states or message broadcasting. Many of those unsupported features depend heavily on the system you are integrating this code into and can be simulated in your event handlers.

Once you have designed your statechart, do the following. First, define an enumeration of states. The following comes from the included sample application, which illustrates all of the above features. This application performs a path-cover test of the statechart engine.

enum eStates
{
    eStateA,
    eStartState = eStateA,
    eStateB,
    eStateC,
    eStateD,
    eStateE,
    eNumberOfStates
};

Here I name the start state and I also designate the number of states by the last enum value, so it will always be correct. Your specific state names will likely be more meaningful than these. Next, I allocate an array of the following:

typedef struct
{
    int32         m_i32StateName;
    std::string      m_sStateName;
    int32         m_i32ParentStateName;
    int32         m_i32DefaultChildToEnter;
    int32         (T::*m_pfi32EventChecker)(void);
    void          (T::*m_pfDefaultStateEntry)(void);
    void          (T::*m_pfEnteringState)(void);
    void          (T::*m_pfLeavingState)(void);
} xStateType;

For example,

TStatechart<CStateClass>::xStateType xaStates[eNumberOfStates] = {
/* name                      */    {eStateA,
/* string name               */    "A",
/* parent                    */    -1,
/* default_substate          */    eStateB,
/* event-checking func       */    &CStateClass::evStateA,
/* default state entry func  */    &CStateClass::defEntryStateA,
/* entering state func       */    &CStateClass::entryStateA,
/* exiting state func        */    &CStateClass::exitStateA},

/* name                      */    {eStateB,
/* string name               */    "B",
/* parent                    */    eStateA,
/* default_substate          */    eStateC,
/* event-checking func       */    &CStateClass::evStateB,
/* default state entry func  */    &CStateClass::defEntryStateB,
/* entering state func       */    &CStateClass::entryStateB,
/* exiting state func        */    &CStateClass::exitStateB},

/* name                      */    {eStateC,
/* string name               */    "C",
/* parent                    */    eStateB,
/* default_substate          */    -1,
/* event-checking func       */    &CStateClass::evStateC,
/* default state entry func  */    &CStateClass::defEntryStateC,
/* entering state func       */    &CStateClass::entryStateC,
/* exiting state func        */    &CStateClass::exitStateC},

/* name                      */    {eStateD,
/* string name               */    "D",
/* parent                    */    eStateA,
/* default_substate          */    -1,
/* event-checking func       */    &CStateClass::evStateD,
/* default state entry func  */    &CStateClass::defEntryStateD,
/* entering state func       */    &CStateClass::entryStateD,
/* exiting state func        */    &CStateClass::exitStateD},

/* name                      */    {eStateE,
/* string name               */    "E",
/* parent                    */    eStateB,
/* default_substate          */    -1,
/* event-checking func       */    &CStateClass::evStateE,
/* default state entry func  */    &CStateClass::defEntryStateE,
/* entering state func       */    &CStateClass::entryStateE,
/* exiting state func        */    &CStateClass::exitStateE}
};

The structs must be initialized in the same order as the states in the enumeration above. Only the top-most state, here eStateA, will have -1 for its parent designation. States without a default sub-state (which will include all simple states) must specify -1 for the default sub-state. Every state must have an event checking/handling method, but need not have the last three fields filled in. Specify 0 for those if they are not defined.

The string name field is used in printing out trace information. In the file TStatechart.hpp, set TRACING_STATUS to 1 to activate this. If compiled with MFC, the information will be written via the TRACE() macro. Otherwise, the text is sent to cout. The engine is referenced internally via a void pointer, so the class using the statechart must have a void pointer for its use:

class CStateClass
{
    .
    .
    .
    void    *engine;
};

The engine must be created and destroyed in your class. These macros and the ones below hide some of the necessary details. The engine name appears in all of them so that you may have more than one declared in the same client class.

CStateClass::CStateClass(void)
{
    CREATE_ENGINE(CStateClass, engine, 
        xaStates, eNumberOfStates, eStartState);
}

CStateClass::~CStateClass(void)
{
    DESTROY_ENGINE(CStateClass, engine);
}

At the point where events happen, place the following call:

PROCESS_EVENT(CStateClass, engine)

Since an event may be far more complex than examining a mere scalar value, the engine does not pass the event around to your event checking/handling methods. Rather, you must store the event in member variable(s) in your class before calling PROCESS_EVENT so that the event checking/handling methods can test for it. Thus, it does not appear in the above call.

For each state in your statechart diagram, an event checking/handling method must be defined that checks for all events that can be handled by that state. Simply test for each event that can happen while you are in the given state, as in the following:

uint32 CStateClass::evStateA(void)
{
    // Checking for event in state A.
    if ('g' == m_cCharRead)        // include any guard conditions here
    {
        BEGIN_EVENT_HANDLER(CStateClass, engine, eStateA);
        // Put the transition action code here.
        END_EVENT_HANDLER(CStateClass, engine);
        return (iHandlingDone);
    }
    return (iNoMatch);
}

This arrangement allows any guard conditions to be tested at the same point in the code as the event itself, simplifying the code. Return iNoMatch from a handler that does not find an event it is supposed to handle.

The BEGIN_EVENT_HANDLER macro lets the engine know that you have found a match for an event. It records this fact and executes the exit handlers for every state that must be exited to get to the destination state. It also records the fact that eStateA will be the state the system goes to after executing the handler code. If the given state is a composite state, then of course you will end up in some simple state inside that composite state.

Control then returns to this method, where any transition actions are carried out. The END_EVENT_HANDLER macro executes any state entry handlers for states that you must enter to end up in the correct simple state. If you wish to transition to a composite state with history, "OR" the history flag onto the state name in the BEGIN_EVENT_HANDLER macro:

BEGIN_EVENT_HANDLER(CStateClass, engine, eStateA | iWithHistory);

For an internal transition, use the "no state change" flag:

BEGIN_EVENT_HANDLER(CStateClass, engine, iNoStateChange);

That's it!

Internals

Internally, the state definition array is parsed upon initialization and more sophisticated data structures are created from it. Those data structures, plus the state definition array, are referenced when an event is being processed. Don't even think about changing the state definition array at run-time!

Because your code must call the statechart engine, it calls your event handlers back in order to find out who will be handling the event and where to go next. Hence, when executing an event handler, you are on the same thread that initially called the engine.

The code contains numerous assert() statements, which check for a variety of simple mistakes that can be made when defining the array of states. Examples are failure to have an initial default state, and a state not having a valid parent state. Such errors are caught during initialization, rather than at run-time.

History

• 23 August, 2007 -- Article and downloads updated
  • The code has been updated to compile/run with Visual Studio 2005.
  • A tracing feature has been added to assist in debugging.
  • The article was updated to match.
• 23 August, 2005 -- Original version posted