Event based state machine in c++ with coroutines

Question

Co-routines in c++ is a really powerful technique for implementing state machines however examples that I find on the internet are overly simplistic, e.g. they usually represent some kind of iterator which after calling to some "Next" routine moves along, dependent only on initial arguments of the coroutine. However in reasonably complicated event based state machines each next step depends, on the specific event received which caused to resume the running and also some default event handlers should be implemented for events that can occur at any time.

Suppose we have a simple phone state machine.

STATE:HOOK OFF-->[EVT:DIAL TONE]--> [STATE:DIALING] --> [EVT: NUMBER DIALED] --> STATE:TALKING.

Now I would like a coroutine that would see something like.

PhoneSM()
{ 
HookOf(); 
Yield_Till(DialTone_Event); 
Dial(); 
Yield_Till(EndOfDial_Event); 
Talk(); 
...
}

e.g. requirements

1. Yield_Till would only continue when specific event was receive (how???) when the couroutine run is resumed.If not then it should yield again.

2. Yield_Till must know how to run the events to default handlers like Hangup_Event because really it can happen any time and it will be cumbersome to add it yield call each time.

Any help with c++ (only!!!) implementation or ready made infrastructures for meeting the requirements will be highly appreciated.

Answer 1

It seems to me that you are trying to code an event-driven state machine as a sequential flow-chart. The difference between state-charts and flow-charts is quite fundamental, and is explained, for example in the article "A Crash Course in UML State Machines":

A state machine should be rather coded as a one-shot function that processes the current event and returns without yielding or blocking. If you wish to use co-routines, you can call this state-machine function from a co-routine, which then yields after each event.

Answer 2

This is an old question but the first I found when searching how to achieve this with C++20 coroutines. As I already implemented it a few times with different approaches I still try to answer it for future readers.

First some background why this is actually a state machine. You might skip this part if you are only interested in how to implement it. State machines were introduced as a standard way to do code that is called once in a while with new events and progresses some internal state. As in this case program counter and state-variables obviously can't live in registers and on stack there is some additional code required to continue where you left of. State machines are a standard way to achieve this without extreme overhead. However it is possible to write coroutines for the same task and every state-machine could be transferred in such a coroutine where each state is a label and the event handling code ends with a goto to the next state at which point it yields. As every developer knows goto-code is spaghetti code and there is a cleaner way to express the intent with flow-control structures. And in fact I have yet to see a state-machine which couldn't be written in a more compact and easier to understand way using coroutines and flow-control. That being said: How can this be implemented in C/C++?

There are a few approaches to do coroutines: it could be done with a switch statement inside a loop like in Duff's device, there were POSIX coroutines which are now obsolete and removed from the standard and C++20 brings modern C++ based coroutines. In order to have a full event-handling state-machine there are a few additional requirements. First of all the coroutine has to yield a set of events that will continue it. Then there needs to be a way to pass the actually occurred event together with its arguments back into the coroutine. And finally there has to be some driver code which manages the events and registers event-handlers, callbacks or signal-slot connections on the awaited events and calls the coroutine once such an event occurred.

In my latest implementations I used event objects that reside inside the coroutine and are yielded by reference/pointer. This way the coroutine is able to decide when such an event is of interest to it even when it might not be in a state where it is able to process it (e.g. a response to a previously send request got answered but the answer isn't to be processed yet). It also allows to use different event-types that might need different approaches to listen for events independent from the used driver code (which could be simplified this way).

Here is a small Duff's device coroutine for the state-machine in the question (with an extra occupied event for demonstration purpose):

class PhoneSM
{
    enum State { Start, WaitForDialTone, WaitForEndOfDial, … };
    State state = Start;
    std::unique_ptr<DialTone_Event> dialToneEvent;
    std::unique_ptr<EndOfDial_Event> endOfDialEvent;
    std::unique_ptr<Occupied_Event> occupiedEvent;
public:
    std::vector<Event*> operator()(Event *lastEvent = nullptr)
    {
        while (1) {
            switch (state) {
            case Start:
                HookOf();

                dialToneEvent = std::make_unique<DialTone_Event>();
                state = WaitForDialTone;
                // yield ( dialToneEvent )
                return std::vector<Event*>{ dialToneEvent.get() };
            case WaitForDialTone:
                assert(lastEvent == dialToneEvent);
                dialToneEvent.reset();

                Dial();

                endOfDialEvent = std::make_unique<EndOfDial_Event>();
                occupiedEvent = std::make_unique<Occupied_Event>();
                state = WaitForEndOfDial;
                // yield ( endOfDialEvent, occupiedEvent )
                return std::vector<Event*>{ endOfDialEvent.get(), occupiedEvent.get() };
            case WaitForEndOfDial:
                
                if (lastEvent == occupiedEvent) {
                    // Just return from the coroutine
                    return std::vector<Event*>();
                }
                assert(lastEvent == endOfDialEvent);
                occupiedEvent.reset();
                endOfDialEvent.reset();

                Talk();

                …
            }
        }
    }
}

Of course implementing all the coroutine handling makes this overly complicated. A real coroutine would be much simpler. The following is pseudocode:

coroutine std::vector<Event*> PhoneSM() {
    HookUp();
    {
        DialToneEvent dialTone;
        yield { & dialTone };
    }
    Dial();
    {
        EndOfDialEvent endOfDial;
        OccupiedEvent occupied;
        Event *occurred = yield { & endOfDial, & occupied };
        if (occurred == & occupied) {
            return;
        }
    }
    Talk();
    …
}

Answer 3

Most co-routine libraries do not off sophisticated yield function. They simply yield and your co-routine will get control back at some arbitrary point. Hence, after a yield you will have to test the appropriate conditions in your code and yield again if they are not met. In this code you would also put tests for events like hangup, in which case you would terminate your co-routine.

There are a number of implementation in the public domain and some operating systems (e.g. Windows) offer co-routine services. Just google for co-routine or fiber.