Конечный автомат событий на С ++ с сопрограммами

Question

Совместные подпрограммы в C++ - это действительно мощный метод для реализации конечных автоматов, однако примеры, которые я нахожу в Интернете, являются чрезмерно упрощенными, например, они обычно представляют собой некий итератор, который после вызова какой-либо подпрограммы "Next" перемещается, зависящий только от начальной аргументы сопрограммы. Однако в достаточно сложных конечных автоматах на основе событий каждый следующий шаг зависит от конкретного полученного события, которое вызвало возобновление работы, а также должны быть реализованы некоторые обработчики событий по умолчанию для событий, которые могут произойти в любое время.

Предположим, у нас есть простой телефонный автомат.

СОСТОЯНИЕ: ВЫКЛЮЧЕНИЕ ->[EVT: набор номера]-> [СОСТОЯНИЕ: НАБОР]->[EVT: НАБОР НОМЕРА]-> СОСТОЯНИЕ: РАЗГОВОР.

Теперь я хотел бы сопрограмму, которая увидит что-то вроде.

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

например, требования

1. Yield_Till будет продолжаться только тогда, когда будет получено определенное событие (как???), когда возобновится запуск программы. Если нет, то он должен вернуться снова.

2. Yield_Till должен знать, как запускать события для обработчиков по умолчанию, таких как Hangup_Event, потому что на самом деле это может произойти в любое время, и добавлять его каждый раз будет сложнее.

Будем весьма благодарны за любую помощь в реализации C++ (только!!!) или готовой инфраструктуры для удовлетворения требований.

Answer 1

Мне кажется, что вы пытаетесь закодировать конечный автомат, управляемый событиями, как последовательную блок-схему. Разница между диаграммами состояний и блок-схемами довольно фундаментальна и объясняется, например, в статье "Ускоренный курс на машинах состояний UML":

Конечный автомат должен быть закодирован как одноразовая функция, которая обрабатывает текущее событие и возвращает без уступки или блокировки. Если вы хотите использовать сопрограммы, вы можете вызвать эту функцию конечного автомата из подпрограммы, которая затем выдается после каждого события.

Answer 2

Это старый вопрос, но первый, который я нашел, когда искал, как добиться этого с помощью сопрограмм C++20. Поскольку я уже реализовал это несколько раз с разными подходами, я все же пытаюсь ответить на него для будущих читателей.

Сначала немного истории, почему это на самом деле конечный автомат. Вы можете пропустить эту часть, если вас интересует только, как это реализовать. Конечные автоматы были введены как стандартный способ выполнения кода, который время от времени вызывается с новыми событиями и изменяет некоторое внутреннее состояние. Поскольку в этом случае программный счетчик и переменные состояния, очевидно, не могут находиться в регистрах, а в стеке требуется некоторый дополнительный код для продолжения с того места, откуда вы ушли. Конечные автоматы - стандартный способ добиться этого без чрезмерных накладных расходов. Однако можно написать сопрограммы для одной и той же задачи, и каждый конечный автомат может быть перенесен в такую ​​сопрограмму, где каждое состояние является меткой, а код обработки событий заканчивается переходом к следующему состоянию, в котором он завершается.Каждый разработчик знает, что goto-code - это спагетти-код, и есть более чистый способ выразить намерение с помощью структур управления потоком. И на самом деле мне еще предстоит увидеть конечный автомат, который нельзя было бы написать более компактным и легким для понимания способом с использованием сопрограмм и управления потоком. При этом: как это можно реализовать на C/C++?

Есть несколько подходов к созданию сопрограмм: это можно сделать с помощью оператора switch внутри цикла, как в устройстве Даффа, были сопрограммы POSIX, которые теперь устарели и удалены из стандарта, а C++20 предлагает современные сопрограммы на основе C++. Чтобы иметь полный конечный автомат обработки событий, есть несколько дополнительных требований. Прежде всего, сопрограмма должна выдать набор событий, которые будут ее продолжать. Затем должен быть способ передать фактически произошедшее событие вместе с его аргументами обратно в сопрограмму. И, наконец, должен быть какой-то код драйвера, который управляет событиями и регистрирует обработчики событий, обратные вызовы или соединения сигнальных слотов для ожидаемых событий и вызывает сопрограмму после того, как такое событие произошло.

В своих последних реализациях я использовал объекты событий, которые находятся внутри сопрограммы и выдаются по ссылке / указателю. Таким образом, сопрограмма может решить, когда такое событие представляет для нее интерес, даже если оно не может быть в состоянии, в котором она может его обработать (например, ответ на ранее отправленный запрос получил ответ, но ответ не в обработке). Это также позволяет использовать разные типы событий, которым могут потребоваться разные подходы для прослушивания событий, независимо от используемого кода драйвера (что можно упростить таким образом).

Вот небольшая сопрограмма устройства Даффа для конечного автомата, о котором идет речь (с дополнительным событием занятости для демонстрационных целей):

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();

                …
            }
        }
    }
}

Конечно, реализация всей обработки сопрограмм делает это слишком сложным. Настоящая сопрограмма была бы намного проще. Следующее - псевдокод:

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

Большинство сопутствующих библиотек не поддерживают сложную функцию yield. Они просто уступают, и ваша совместная рутина получит контроль в любой произвольной точке. Следовательно, после выхода вы должны будете протестировать соответствующие условия в вашем коде и снова выполнить, если они не выполняются. В этом коде вы также поместите тесты для таких событий, как зависание, и в этом случае вы прекратите свою подпрограмму.

Существует множество реализаций в открытом доступе, и некоторые операционные системы (например, Windows) предлагают сопутствующие услуги. Просто Google для совместной рутины или волокна.