Дизайн шаблона конечного автомата на C++. Часть вторая.

Author / Автор: Сергей Сацкий
Publication date / Опубликовано: 06.08.2004
Version / Версия текста: 1.0

Год спустя

Прошел почти год с момента публикации первой части статьи, за это время шаблон претерпел некоторые изменения, появились новые возможности. Во второй части будут описаны новые идеи и показаны наиболее нетривиальные фрагменты кода.

Усовершенствования

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

    ...
    #define FSMStateType   string
    #define FSMEventType   Events

    SStateMachine< StateType,
                   EventType,
                   SEmptyFunctor<StateType,EventType>,
                   SThrowStrategy<EventType>
                 >
    MyMachine(

        FSM_BEGIN( "empty" )

        FSM_STATES           "empty"      << "number"  << "identifier" << "unknown"

        FSM_EVENT(letter)    "identifier" << "unknown" << "identifier" << "unknown"
        FSM_EVENT(digit)     "number"     << "number"  << "identifier" << "unknown"

        FSM_END
             );

    #undef FSMStateType
    #undef FSMEventType
    ...

В приведенном фрагменте кода можно заметить, что, попав в состояние "unknown", любое событие игнорируется. Здесь для всех событий просто-напросто указано то же самое состояние "unknown". С применением манипулятора описание конечного автомата в коде можно переписать таким образом.

    MyMachine(

        FSM_BEGIN( "empty" )

        FSM_STATES           "empty"      << "number"  << "identifier" << "unknown"

        FSM_EVENT(letter)    "identifier" << "unknown" << "identifier" << NONE
        FSM_EVENT(digit)     "number"     << "number"  << "identifier" << NONE

        FSM_END
             );

Манипулятор NONE указывает, что ничего делать не надо.

Стоит заметить, что разница между указанием того же самого состояния в таблице переходов и использования манипулятора NONE имеется. В случае манипулятора никаких действий выполнено не будет - событие игнорируется. В случае указания того же самого состояния в таблице переходов, будут вызваны функции OnEnter(. . .) и OnExit(. . .), привязанные к состоянию, если таковые определены. Использование манипулятора, на мой взгляд, предпочтительнее. Оно позволяет нагляднее представить картину происходящего.

Кроме манипулятора NONE шаблон поддерживает еще один: EXCEPTION. Манипулятор EXCEPTION приведет к генерации исключения вместо перехода, а автомат будет сброшен в начальное состояние.

Немного теоретических размышлений и второй вариант шаблона

Вернемся к вызовам функций в шаблоне конечного автомата, предложенном выше. Функции привязывались к состояниям и требовалось, чтобы тип состояния определял функции-члены OnEnter(. . .) и OnExit(. . .) с соответствующими прототипами. На рисунке это можно изобразить следующим образом:


Рисунок 1. Модель конечного автомата с функциями, привязанными к состояниям

Однако иногда может оказаться удобным привязывать вызовы функций не к состояниям, а к переходам. На рисунке это можно показать так:


Рисунок 2. Модель конечного автомата с функциями, привязанными к переходам

С учетом того, что проблема формирования списков переменной длины при описании конечного автомата уже решена, остается только вопрос об удачном синтаксисе привязки вызовов функций к переходам. В C++ можно использовать оператор [ ]. В этом случае описание конечного автомата, показанного на рисунке 2, будет выглядеть так:

    ...
    MyMachine(
        FUNCFSM_BEGIN( Start )

        FUNCFSM_STATES           Start  <<  S1      <<  S2      <<  S3

        FUNCFSM_EVENT(E1)        S1[f1] <<  NONE    <<  S2[f3]  <<  NONE
        FUNCFSM_EVENT(E2)        S2[f2] <<  NONE    <<  NONE    <<  NONE
        FUNCFSM_EVENT(E3)        NONE   <<  S3[f4]  <<  S3[f4]  <<  NONE

        FUNCFSM_END
             );
    ...

Здесь для переходов, где необходимо выполнить вызов функции, в квадратных скобках с новым состоянием указана и функция для вызова. Разумеется, возникает вопрос о том, какая именно это будет функция. Вариантов много - свободная функция, функция-член класса, виртуальная функция и т.п. Удачное решение хранения объекта-функции предлагает библиотека function из свободно распространяемого комплекта библиотек boost (http://www.boost.org). Объект boost::function представляет собой шаблон, позволяющий сохранить, а потом и вызвать все, что угодно, у чего синтаксис допускает вызов с помощью круглых скобок. Для нашего случая подойдет такое определение:

typedef boost::function< void ( StateType &  From, 
                                EventType &, 
                                StateType &  To ) >   CallbackType;

Теперь в связи с переходом потребуется хранить новое состояние, функцию обратного вызова и манипулятор. Два последних элемента не являются обязательными. Хранить несколько связанных по смыслу элементов удобно в структуре:

        // A bundle of the state related information
    template < typename SState, typename SEvent >
    struct SFuncBundle
    {
        SState                                  NewState;
        int                                     Manipulator;
        boost::function< void ( SState &,
                                SEvent &,
                                SState & ) >    Callback;

        SFuncBundle() {}
    };

Реализация оператора [ ] не представляет особого труда. Надо лишь помнить, что при указании переходов возможны два варианта: просто новое состояние и новое состояние с указанной функцией. В обоих случаях опрератор <<, перегруженный для описания переходов, ожидает ссылку на состояние. Для упрощения жизни разрабочикам можно написать шаблон:

template < typename  Child,
           typename  Event >
    class StateBase
    {
            // Should all of them be const? - No. It is easy to imagine that
            // some fields in the states and events should be changed
        typedef boost::function< void ( Child &,
                                        Event &,
                                        Child & ) >   CallbackType;

        private:
            CallbackType    Callback;

        protected:
            StateBase() : Callback( 0 ) {}

        public:
            inline Child & operator [] ( const CallbackType &  NewCallback )
            {
                Callback = NewCallback;
                return static_cast< Child & >( *this );
            }
            
            inline CallbackType  GetCallback( void )
            {
                CallbackType        Temporary( Callback );

                Callback = 0;
                return Temporary;
            }
    };

Здесь есть несколько интересных моментов. Функцию GetCallback(. . .) нельзя сделать константной. При описании переходов Proxy. . . класс, собирающий информацию о переходах, может иметь несколько переходов в одно и то же состояние, но с вызовами разных функций. Значит, как только информация о нужном вызове получена, объект-функция должен быть очищен. Кроме того, оператор [ ] не может быть константным, так как он запоминает требуемый вызов, а значит не может быть применен к константной ссылке на состояние. Из этого следует, что прежде, чем описывать конечный автомат, придется создать объекты состояний и использовать именно их в конструкторе шаблона. То есть реальный код будет выглядеть примерно так:

. . .
class MyEvent { . . . };

class MyState : public StateBase< MyState, MyEvent >
{
. . .
};

MyEvent    E1(. . .), E2(. . .);    // Could be also instaniated 
                                    // in the MyMachine constructor
MyState    Start(. . .), S1(. . .), S2(. . .), S3(. . .);

    MyMachine(
        FUNCFSM_BEGIN( Start )

        FUNCFSM_STATES           Start  <<  S1      <<  S2      <<  S3

        FUNCFSM_EVENT(E1)        S1[f1] <<  NONE    <<  S2[f3]  <<  NONE
        FUNCFSM_EVENT(E2)        S2[f2] <<  NONE    <<  NONE    <<  NONE
        FUNCFSM_EVENT(E3)        NONE   <<  S3[f4]  <<  S3[f4]  <<  NONE

        FUNCFSM_END
             );
    . . .

Итог

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

    template < typename SState, 
               typename SEvent, 
               typename SUnknownEventStrategy = SThrowStrategy<SEvent> > 

По сравнению с первым вариантом шаблона нет одной из стратегий - вызовов функций, привязанных к состояниям.

Введены новые макросы для упрощения описания конечного автомата в конструкторе. Их назначение и имена совпадают с таковыми для первого варианта за исключением добавленного префикса FUNC.

Получение текущего состояния конечного автомата и подача события на вход автомату производится точно так же, как и для первого варианта шаблона.

Преимущества и недостатки

К недостаткам, присущим первому варианту шаблона, можно добавить следующие:

  • Необходимо сначала иметь созданные экземпляры состояний, а только затем использовать их для описания переходов.
  • Классы состояний обязаны реализовывать operator [ ]. Это означает невозможность использовать стандартные типы напрямую. Придется сначала написать несколько строк, описывающий желаемый тип состояния. При реализации operator [ ] нужно помнить, как это правильно сделать или помнить о наследовании от готового шаблонного класса.
  • В коде шаблона базового класса для состояний употребляется оператор преобразования. К сожалению, без этого не обойтись.

Преимущества остались теми же самыми, что и для первого варианта.

Приведенный список недостатков не приводит к большим накладным расходам на "оформительскую" часть кода, однако, для некоторых задач, модель привязки функциональных вызовов к переходам выглядит предпочтительнее.

Можно было бы написать шаблон, который допускает совместное использование и модели с привязкой функциональных вызовов к состояниям и к переходам. Возможно, такой шаблон и будет когда-нибудь разработан.

Пример

Исходные коды примеров можно найти на интернет сайте автора: (http://satsky.spb.ru).

Литература

  1. Дэвид Вандервурд, Николаи М. Джосаттис. Шаблоны С++. Справочник разработчика. Издательский дом "Вильямс", Москва, Санкт - Петербург, Киев, 2003.
  2. Документация по библиотеке boost (http://www.boost.org).


Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.

Разрешается копирование и распространение этой статьи любым способом без внесения изменений, при условии, что это разрешение сохраняется.
Last Updated: September 27, 2005