Designing a state machine in C ++

Question

I have a little problem with the simulation of a state machine.

I was able to calculate knowledge a bit and “reverse engineer” a set of primitive deterministic rules that determine a state, as well as a state transition.

I would like to know what the best practices are about:

• How to strictly check my states and states to make sure that the system cannot end in an undefined state.

• How to ensure the fulfillment of state transition requirements (for example, it is impossible to go directly from stateFoo to StateFooBar, that is, to fill each state with “knowledge” about the states to which it can go.

Ideally, I would like to use a clean, template-based design, with templates where possible.

I need to start something, although I would be grateful for any pointers (not intended for puns) that are sent to me.

Answer 1

Be sure to take a look at the Boost Statechart Library .

Answer 2

Gosh, it's not as complicated as it sounds. State machine code is very simple and short.

Store the state in a variable, say myState.

You indicate that the machine will be a switch statement, branching out with the value of the myState variable, to implement code for each state.

The code will be filled with the following lines:

myState = newState; 

To ensure that state transition requirements are met, you need to add another method instead, for example

 void DoSafeStateTransition( int newState ) { // check myState -. newState is not forbidden // lots of ways to do this // perhaps nested switch statement switch( myState ) { … case X: switch( newState ) case A: case B: case Z: HorribleError( newState ); break; ... } // check that newState is not undetermined switch( newState ) { // all the determined states case A: case B: case C … case Z: myState = newState; break; default: HorribleError( newState ); } } void HorribleError( int newState ) { printf("Attempt to go from %d to %d - disallowed\n", myState, newState ); exit(1); } 

I suggest that it is simple and short enough that validation will be better than unit testing - it will certainly be much faster!

The point, in my opinion, of unit testing is that the test code is simpler than the tested code, so it can be more easily checked for correctness and then used to test complex code. It is often easier to verify the state machine code than the test state machine code. It makes no sense to specify 100% throughput unit test if you have little idea if the unit tests are correct.

Put it another way: coding the final car is easy, developing the right one is difficult. Unit tests will only indicate whether you have encoded the design correctly, and not with the correct design.

Answer 3

Testing has little to do with templates, templates, etc. I would recommend a testing framework like CppUnit (part of the xUnit family) to capture all your test cases. Of course, the number will depend on the complexity of the state machine.

Your question about ensuring state transitions becomes the basis of the design of your class for your state machine. I would say that a state will have a set of child states to which it can go, as well as an event that each of them will trigger. If the Foo event does not have a child element of FooBar, then there is no way to transition it.

I would use Google's "object oriented end machines" to get some design ideas.

When I thought about such problems, I thought that the Composite design template could be part of it, because the state could be a more complex FSM. I would have a State interface, with SimpleState and CompositeState as implementations. I have to start again and see if everything works out.

Answer 4

Using machine states is something that comes up from time to time. I usually do as ravenspoint suggested, and just do the switch statement. But this only works if the states are not too large. This is similar to your case. With that in mind, I think it's best to start with a good architecture that will allow some of the things you want to do. I accepted duffymo's offer and tried Google. This article looked interesting - Object-oriented state machines . This may be redundant, but I think it will provide frameworks that are easy to verify with something like CppUnit.

Some other useful links from google search

The ultimate machine for cars

Object Oriented End Machines

Answer 5

Sounds like a pristine unit testing application. There are many structural testing modules. I like Boost one .

Answer 6

If you are looking for the classic GOF Design Patterns state template, check out wikipedia .

Take a look at this page (at the time of writing) using Java as an example.

It has the StateContext class, which you can see from the usage example, has clients who know about the writeName method. Implementation: this.myState.writeName(this, name); , which means that it forwards the call to the current state, passing itself as the first argument.

Now look at interface State , it has a writeName method that matches the above usage. If you look at StateA and StateB , they return to the context, setting a new state.

This is a large part of the state model right there. The only thing you need to understand is that the StateContext class can contain all the data related to its operation, including the link (it should be a pointer to C ++) in the current state. All states collectively contain all behavioral data, but no , instead they put data (plus helper methods) in context.

When I design a state machine (usually I use TDD), I don’t worry about checking state transitions, it’s just that the final behavior is what I want.

Answer 7

If you like the state template, I did an experiment and moved this template to the library: https://code.google.com/p/dpsmlib/