A Magical C++ State Machine Implementation

permalink         categories: programming         originally posted: 2005-06-14 13:54:22

And by magical I mean uses heavy C++ wizardry and probably shouldn't be used. I am abandoning this approach in the interests of code maintainability; this code is clever, and these days whenever I write something clever I feel ashamed.

Here's the source code, which compiles under Windows, GCC 2 and GCC 3 under Linux, and GCC 4 on Mac OS X:

// Proof-of-concept for a magical approach to state machines in C++
// Written by Larry Hastings, larry@hastings.org, June 14th 2005
// Released into the public domain.

#include <assert.h>
#include <stdio.h>

class stateMachine
	{
	public:
	stateMachine() { integer = 0; }
	~stateMachine() { leavingState(); }
	virtual void enteringState() {};
	virtual void leavingState() {};
	virtual void foo() {};
	int integer;
	void nextState(stateMachine *sm);
	};

class stateMachineA : public stateMachine
	{
	public:
	stateMachineA()
		{
		integer = 3;
		assert(sizeof(stateMachineA) == sizeof(stateMachine);
		};
	virtual void foo() { printf("in a, integer is %d\n", integer); };
	};
static stateMachineA _smA, *smA = &_smA;

class stateMachineB : public stateMachine
	{
	public:
	stateMachineA()
		{
		integer = 3;
		assert(sizeof(stateMachineB) == sizeof(stateMachine);
		};
	virtual void foo() { printf("in b, integer is %d\n", integer); };
	};
static stateMachineB _smB, *smB = &_smB;

void stateMachine::nextState(stateMachine *next)
	{
#if defined(__GNUC__) && (__GNUC__ <= 2)
	#define smSize sizeof(stateMachine)
	#define vssSize sizeof(void **)
	// assert sizeof(stateMachine) is sizeof(void**)-aligned
        assert((smSize & (vssSize - 1)) == 0);
        #define vtableOffset (smSize - vssSize)
#else
	#define vtableOffset 0
#endif // __GNUC__

        char *tmp;

        tmp = (char *)this;
        tmp += vtableOffset;
	void **thisVtable = (void **)tmp;

        tmp = (char *)next;
        tmp += vtableOffset;
	void **nextVtable = (void **)tmp;

        leavingState();
        *thisVtable = *nextVtable;
        enteringState();
        }

int main()
	{
	stateMachine *sm = new stateMachineA;
	sm->foo(); // prints "in a, integer is 3\n"
	sm->nextState(smB);
	sm->foo(); // prints "in b, integer is 3\n"
	return 0;
	}

So how does this work? We start with have a virtual base class that defines all the incoming events you'd care to handle. We write one class that represents each state the object might be in. To switch states, we overwrite the vtable, switching to the vtable of the subclass that handles that state. (What's a vtable? It's a secret pointer in every C++ instance pointing to an array of function pointers. That's how C++ implements "virtual functions".)

Minuses:

• This uses heavy C++ backdoor wizardry voodoo, which means it'd be confusing and hard to maintain. Note the heavy wizardry for GCC 2; it actually stores the vtable entry at the end, rather than at the beginning. Weird, huh? And a little spooky in terms of cross-platform maintainability.
• You MUST NOT declare variables in the state-machine subclasses. Those classes are never actually instantiated; the main object simply pretends to switch to them. (That's the point of the asserts in the subclass constructors.)
• You better not override the destructor, neither, for much the same reason.

Plusses:

• You don't have to dereference an external pointer that handles "state", which means a lot less dereferencing for you to stare at when it comes time to maintain the code.
• It is theoretically faster this way, and will mean far fewer trips to the heap to create and destroy state-handler objects, but that is of course negligible overhead on any modern computer.

In the final balance, the weird creepy magic going on here, and the restriction on member variables in the state classes, is enough to sour me on this approach. It is a natural paradigm to represent state in individual classes, and it gives you a natural place to put "entering this state" code (in the constructor) and "leaving this state" code (in the destructor).

(Note: if using GCC, use g++, not gcc, to compile and link. There are some extra objects that g++ will link with that gcc doesn't.)