C state-machine design

Question

I am crafting a small project in mixed C and C++. I am building one small-ish state-machine at the heart of one of my worker thread.

I was wondering if you gurus on SO would share your state-machine design techniques.

NOTE: I am primarily after tried & tested implementation techniques.

UPDATED: Based on all the great input gathered on SO, I've settled on this architecture:

Solution 1

State machines that I've designed before (C, not C++) have all come down to a struct array and a loop. The structure basically consists of a state and event (for look-up) and a function that returns the new state, something like:

typedef struct {
    int st;
    int ev;
    int (*fn)(void);
} tTransition;

Then you define your states and events with simple defines (the ANY ones are special markers, see below):

#define ST_ANY              -1
#define ST_INIT              0
#define ST_ERROR             1
#define ST_TERM              2
: :
#define EV_ANY              -1
#define EV_KEYPRESS       5000
#define EV_MOUSEMOVE      5001

Then you define all the functions that are called by the transitions:

static int GotKey (void) { ... };
static int FsmError (void) { ... };

All these function are written to take no variables and return the new state for the state machine. In this example global variables are used for passing any information into the state functions where necessary.

Using globals isn't as bad as it sounds since the FSM is usually locked up inside a single compilation unit and all variables are static to that unit (which is why I used quotes around "global" above - they're more shared within the FSM, than truly global). As with all globals, it requires care.

The transitions array then defines all possible transitions and the functions that get called for those transitions (including the catch-all last one):

tTransition trans[] = {
    { ST_INIT, EV_KEYPRESS, &GotKey},
    : :
    { ST_ANY, EV_ANY, &FsmError}
};
#define TRANS_COUNT (sizeof(trans)/sizeof(*trans))

What that means is: if you're in the ST_INIT state and you receive the EV_KEYPRESS event, make a call to GotKey.

The workings of the FSM then become a relatively simple loop:

state = ST_INIT;
while (state != ST_TERM) {
    event = GetNextEvent();
    for (i = 0; i < TRANS_COUNT; i++) {
        if ((state == trans[i].st) || (ST_ANY == trans[i].st)) {
            if ((event == trans[i].ev) || (EV_ANY == trans[i].ev)) {
                state = (trans[i].fn)();
                break;
            }
        }
    }
}

As alluded to above, note the use of ST_ANY as wild-cards, allowing an event to call a function no matter the current state. EV_ANY also works similarly, allowing any event at a specific state to call a function.

It can also guarantee that, if you reach the end of the transitions array, you get an error stating your FSM hasn't been built correctly (by using the ST_ANY/EV_ANY combination.

I've used code similar for this on a great many communications projects, such as an early implementation of communications stacks and protocols for embedded systems. The big advantage was its simplicity and relative ease in changing the transitions array.

I've no doubt there will be higher-level abstractions which may be more suitable nowadays but I suspect they'll all boil down to this same sort of structure.

---

And, as ldog states in a comment, you can avoid the globals altogether by passing a structure pointer to all functions (and using that in the event loop). This will allow multiple state machines to run side-by-side without interference.

Just create a structure type which holds the machine-specific data (state at a bare minimum) and use that instead of the globals.

The reason I've rarely done that is simply because most of the state machines I've written have been singleton types (one-off, at-process-start, configuration file reading for example), not needing to run more than one instance. But it has value if you need to run more than one.

Solution 2

The other answers are good, but a very "lightweight" implementation I've used when the state machine is very simple looks like:

enum state { ST_NEW, ST_OPEN, ST_SHIFT, ST_END };

enum state current_state = ST_NEW;

while (current_state != ST_END)
{
    input = get_input();

    switch (current_state)
    {
        case ST_NEW:
        /* Do something with input and set current_state */
        break;

        case ST_OPEN:
        /* Do something different and set current_state */
        break;

        /* ... etc ... */
    }
}

I would use this when the state machine is simple enough that the function pointer & state transition table approach is overkill. This is often useful for character-by-character or word-by-word parsing.

Solution 3

Pardon me for breaking every rule in computer science, but a state machine is one of the few (I can count only two off hand) places where a goto statement is not only more efficient, but also makes your code cleaner and easier to read. Because goto statements are based on labels, you can name your states instead of having to keep track of a mess of numbers or use an enum. It also makes for much cleaner code since you don't need all the extra cruft of function pointers or huge switch statements and while loops. Did I mention it's more efficient too?

Here's what a state machine might look like:

void state_machine() {
first_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }

second_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }
}

You get the general idea. The point is that you can implement the state machine in an efficient way and one that is relatively easy to read and screams at the reader that they are looking at a state machine. Note that if you are using goto statements, you must still be careful as it is very easy to shoot yourself in the foot while doing so.

Solution 4

You might consider the State Machine Compiler http://smc.sourceforge.net/

This splendid open source utility accepts a description of a state machine in a simple language and compiles it to any one of a dozen or so languages - including C and C++. The utility itself is written in Java, and can be included as part of a build.

The reason to do this, rather than hand coding using GoF State pattern or any other approach, is that once your state machine is expressed as code, the underlying structure tends to disappear under the weight of boilerplate that needs to be generated to support it. Using this approach gives you an excellent separation of concerns, and you keep the structure of your state machine 'visible'. The auto-generated code goes into modules that you don't need to touch, so that you can go back and fiddle with the state machine's structure without impacting the supporting code that you have written.

Sorry, I am being over-enthusiastic, and doubtless putting everyone off. But it is a top notch utility, and well-documented too.

Solution 5

Be sure to check the work of Miro Samek (blog State Space, website State Machines & Tools), whose articles at the C/C++ Users Journal were great.

The website contains a complete (C/C++) implementation in both open source and commercial license of a state machine framework (QP Framework), an event handler (QEP), a basic modeling tool (QM) and a tracing tool (QSpy) which allow to draw state machines, create code and debug them.

The book contains an extensive explanation on the what/why of the implementation and how to use it and is also great material to gain understanding of the fundamentals of hierachical and finite state machines.

The website also contains links to several board support packages for use of the software with embedded platforms.

View more solutions

Comments

[Michael Burr]

The answers here are very good. Also look at this duplicate question that has several good answers, too: stackoverflow.com/questions/1371460/state-machines-tutorials

[Prasanth Kumar]

This is also interesting: stackoverflow.com/questions/133214/…

[jldupont]

related: stackoverflow.com/questions/2101961/python-state-machine-des‌​ign

[Prasanth Kumar]

See also this question.

[steveha]

This looks nice, and practical. I would have expected you to use a giant switch statement instead of iterating through an array of transitions... I think I see a couple of advantages of doing it this way, but I would be grateful if you would explain why you do this instead of the giant switch. Also, a minor nit: all the compilers I use these days support enums, so I would prefer to use enums for things like states. I always define a first and last enum that are not valid states, so I can write a range check like: Assert(stateInvalid < state && state < stateMax);

[paxdiablo]

A giant switch mixes code in with the FSM. Even if there's only a function call per transition, there's still some code, and it's easy for someone to abuse that by just adding a small 4-line transition inline. hen a ten-line one. Then it gets out of hand. With the struct array, the FSM stays clean - you can see every transition and the effect (function). And I started when enums were a twinkle in ISO's eye, writing code for 6809 embedded platforms with compilers that were, shall we say, less than perfect :-)

[paxdiablo]

You're right, enums would be better, but I still prefer having the FSM as a struct array. Then it's all run by data rather than code (well, there's some code but the chance of stuffing up that FSM loop I gave is slim).

[jldupont]

I modified the question's title according following your pun.

[Metiu]

This is good, for process controle state machines I used to always add three (possibly empty) substates for every state, so that the call for a state function would become GotKey(substate), where substate would be: - SS_ENTRY - SS_RUN - SS_EXIT Basically, the state function gets called with a SS_ENTRY substate on entry, so that the state can reconstruct a status (e.g. actuators positions). While there's no transition, the SS_RUN substate value gets passed. Upon transition, the state function gets called with the SS_EXIT substate, so that it can do any cleanups (e.g. deallocate resources).

[paxdiablo]

That's probably a matter of preference, @Metiu. I'd see those as three independent states but I can see where you're coming from.

[Prasanth Kumar]

@jldupont: I just meant that it was better to clarify. I have deleted the irrelevant parts of my answer now.

[jldupont]

Feels like this solution doesn't scale nicely: too much table filling, no?

[paxdiablo]

+1. The scaling issue here is memory - my own solution has a scaling issue re time, i.e., time taken to scan the transitions table (though you can manually optimize for the most common transitions). This one sacrifices memory for speed - it's just a trade-off. You'd probably need checks for bounds but it's not a bad solution.

[Ape-inago]

It is interesting, but no upvote until you give an example or two (and perhaps de-macro'ed result) or some discussion on why this may be more practical than another. Interesting use of orphaned brackets and macros. I imagine something similar could be done on a language that does some sort of tail recursion optimization; you could use straight up function calls and not worry about overloading the stack space with function call garbage (which I think is what the macros are essentially overcoming here)

[jldupont]

Guys - My comment didn't come out as intended: I meant it is much more laborious and error prone. If you add a state/event, lots of editing needs to be done.

[paxdiablo]

I love the "extremely untested" comment. Seems to indicate that there are degrees of untestedness and that you put quite a bit of effort into not testing it :-)

[John Zwinck]

Nobody said the 2D array was initialized by hand. Maybe there's something that reads a configuration file and creates it (or at least there certainly could be).

[jldupont]

Maybe an example would be nice, no?

[Bill Forster]

A realistic example that can be presented in isolation is a challenging task that would require more time than I am prepared to give just at the moment. Is there anything in my post that is particularly hard to understand ? Maybe I can express it more clearly. The idea is very simple; Don't define a state mechanism that requires a separate function for every event/state combination, you get way too many functions that way. Instead find another way to describe the functionality you want for that event/state combination, at least in the majority of cases.

[jldupont]

Understood: a pseudo-code example would have been good but your point is clear.

[skrebbel]

This only works if the state machine is in the top-level object. The moment some other object that is occasionally polled / sent messages to, needs to have state, you're stuck with this approach (that, or you have to make it much more complicated)

[Toad]

@metiu I've done the same in the past. It does get hairy though when in the 'entry' state things go wrong, and you need to go to an other state (e.g. error state). This leads to an unclear design. However, spelling entry and exit states out (like paxdiablo suggests), can lead to an abundance of states.

[ldog]

You mentioned that you share data by using globals, but it would probably be cleaner if you define the state functions to be int (*fn)(void*); where void* is the pointer to the data that each state function takes in as a parameter. Then the state functions can either use the data or ignore them.

[paxdiablo]

That's actually a good idea, @ldog, and it lends itself to better encapsulation. I tend not to do it simply because the vast majority of the state machines I've done tend to be singleton types and isolated in a single file (so the globals aren't truly global). By using your method, you could have a single piece of code running multiple state machines quite easily by casting the void* to a per-machine structure.

[Frerich Raabe]

I use the same data/code separation for writing FSMs, except that it never occurred to me to introduce 'wildcard' states. Interesting idea! However, iterating the array of transitions might become expensive if you have a lot of states (which was the case for me since the C code was automatically generated). In such situations, it would be more efficient to have one array of transitions per state. So a state is no longer an enum value, but a transition table. That way, you don't have to iterate over all transitions in the machine but just those which are relevant to the current state.

[paxdiablo]

@Frerich, that's actually not a bad optimisation. By storing the current state as a pointer to the transition table for that state, the search space is greatly reduced. The global wildcard (any state, any event) would disappear and every transition table would have to have a (this state, any event) check but that's a small price to pay for the massive reduction in searching for your desired pair. You should put that in an answer, I'd upvote that.

[Fire Crow]

+1 that's really nice, and provides nice places to hand functionality inside the transition functions

[Adriaan]

I've added what to expect on website/book, having used the software succesfully myself; it is the best book on my book shelf.

[Prasanth Kumar]

@Adriann, great explanation! I just modified the home of the website, the previous link had stopped working.

[jldupont]

looks more like a comment: could I suggest you treat it as such? i.e. not place it in the "answer" section.

[Exectron]

This really forces you to use preemptive multitasking in all but the simplest of cases.

[Exectron]

The advantages of this method are...? I see several disadvantages, such as obfuscating macros, and the use of goto that creates a dependency on a preemtive multitasking OS.

[Exectron]

It would be good if you could provide a good URL link for the "GoF state pattern", for those not familiar with it.

[Mick]

@jldupont - fair comment. I changed the text to make it a proper answer as I feel based on personal experience that, unless there are specific performance issues, the GoF approach works fine and will have a relatively large 'user base'

[Mick]

@Craig - added some links. Both looked accurate and clear at the time I added them.

[XTL]

I would avoid 'this' as a variable name or symbol just for the association, even if it isn't actually a reserved word.

[Abtin Forouzandeh]

Those gotos could be replaced with function calls. And if a profiler tells you that your program is drowning because of function call overhead, then you could replace the calls with gotos as needed.

[JustMaximumPower]

@AbtinForouzandeh simply replacing the gotos with function calls would cause a stackoverflow since the call stack is only cleared in case of an error.

[Freddie Chopin]

Hmm... sth is missing in your code. First of all you include two headers, but provide only the first one. When I just comment the "include" statement I get this error when compiling: d:\1\hsm>g++ test.cpp test.cpp:195:1: error: specialization of 'static void CompState<H, id, B>::init( H&) [with H = TestHSM; unsigned int id = 0u; B = CompState<TestHSM, 0u, TopState <TestHSM> >]' after instantiation

[Freddie Chopin]

I had to move definitions of all HSMINIT() to be above TestHSM class and it compiles and works fine (; The only thing that is wrong is the fact that all transitions are "external", while they should be "internal" - there was some debate about it in the article and the author decided that "extrenal" was right, but the arrows used suggest "internal".

[Kuba hasn't forgotten Monica]

This is what any parser or lexer generator will gladly emit for you. Uncannily so. Whether you want to code it up by hand is questionable. It has pedagogical merit, of course.

[Tatiana Racheva]

The links are either dead or point to the homepage of the site that seems to have changed its direction to embedded software. You can still see some of the content on state-machine.com/resources/articles.php, but even there most of the state machine-related links are dead. This is one of the only good links there: state-machine.com/resources/…

[AlphaGoku]

You can further optimize it for safety by using an array of constant function pointers to functions

[Joakim]

@Christoph the link in this answer is broken. Also, have you tested this code or not? If it has been tested and works you should remove that from the answer. Also maybe show an example of what code this results in once the macros have been expanded. I like the general idea.

[Al Bundy]

@FrerichRaabe how do you know how many transitions to iterate for every state? I mean how do you get the information how many transitions the current state has?

[paxdiablo]

@Al, I'm not sure that's required. You would simply have an array of transition tables, one for each state, and these would contain only the event and the function to call (which would optionally set a new state). You only do one transition per iteration. The advantage there is that you don't have to search through as many entries for each iteration since you only care about valid events for the current state.

[Frerich Raabe]

@AlBundy You could denote the end of the transition table using e.g. a null pointer for the state transition function, i.e. you end all transition tables with { 0, 0, 0 }.

[Al Bundy]

@FrerichRaabe With a lot of states it can lead to wasting memory but it is clean solution. I think that alternative small improvement is to use one transition array and put more frequent and more probable (or more time crucial) states and events in the beginning of the table.

[eddyq]

Check this out ... it is a way to make a state machine for each function and uses a scheme that mimics structured code. codeproject.com/Articles/37037/…

[eddyq]

I agree with the goto method. Here is a set of macros that illustrate that. And the macros make your code structured as if you had coded it like you normally would. It also works at interrupt level which is usually where state machines are needed codeproject.com/Articles/37037/…

[Kristoffer]

Finding this in 2018 and that it is still applicable. I was reading @paxdiablo answer, and I have successfully used that type of implementation in embedded systems before. This solution adds the missing things from paxdiablos answer :)

[hlovdal]

One way to initialize arrays like that is to make use of the preprocessor being a late binder (as opposed to early binding). You define a list of all the states #define STATE_LIST() \STATE_LIST_ENTRY(state1)\STATE_LIST_ENTRY(state2)\... (an implied newline after each \ ) where you (re)define the entry macro when you use the STATE_LIST macro. Example - making an array of state names: #define STATE_LIST_ENTRY(s) #s , \n const char *state_names[] = { STATE_LIST() };\n #undef STATE_LIST_ENTRY. Some work to set up first, but this is extremely powerful. Add new state -> guaranteed no misses.

[Ahmed Masud]

@eddyq what kind of black magic voodoo is this :P btw ... what you did in that codeproject rocks

[mindoverflow]

You probably saw it there: stackoverflow.com/a/133363