Эффективное использование STL и шаблонов
{ return AcceptEvent( Event ); }
Перегрузка operator << даст возможность использовать автомат в таком стиле:
|
// Принять события Event1, Event2 и Event3 MyMachine << Event1 << Event2 << Event3; |
Остается вопрос: что делать, если придет событие, для которого у автомата нет описания переходов? Возможны варианты: просто проигнорировать такое событие, сгенерировать исключение или сделать что-то, определяемое пользователем. Воспользуемся идеей стратегий ([4]) и включим в число аргументов шаблона функтор, который будет определять нужную стратегию поведения. Такой подход вполне соответствует требованию 5. При этом можно задать стратегию по умолчанию – например, генерировать исключение. Теперь заголовок шаблона выглядит так:
|
template <class SState, class SEvent, class SUnknownEventStrategy = SThrowStrategy<SEvent> > class SFiniteStateMachine { . . . }; |
В числе заготовленных стратегий есть и стратегия игнорирования неизвестного события:
|
template <class SEvent> class SIgnoreStrategy { public: inline void operator() ( const SEvent & ) const { return; } }; |
Если понадобятся другие действия, всегда можно написать собственный функтор по образу и подобию SIgnoreStrategy и передать его шаблону.
Многие источники, описывающие конечные автоматы, упоминают о возможности вызова функций при входе и выходе из состояния. Такую возможность легко предоставить, используя тот же подход стратегий. Функции входа и выхода из состояний удобно определять для класса, представляющего конкретное состояние. Вспоминая о требовании 5, дадим возможность гибкого управления такой возможностью. Предполагая, что функции класса состояния будут называться OnEnter и OnExit, можно написать несколько готовых функторов: не вызывающий ни одну из функций, вызывающий только OnEnter, вызывающий только OnExit и вызывающий обе функции.
|
template <class SState, class SEvent> class SEmptyFunctor { public: inline void operator() ( SState & From, const SEvent & Event, SState & To ) { return; } }; template <class SState, class SEvent> class SOnEnterFunctor { public: inline void operator() ( SState & From, const SEvent & Event, SState & To ) { To.OnEnter( From, Event ); } }; template <class SState, class SEvent> class SOnExitFunctor { public: inline void operator() ( SState & From, const SEvent & Event, SState & To ) { From.OnExit( Event, To ); } }; template <class SState, class SEvent> class SOnMoveFunctor { public: inline void operator() ( SState & From, const SEvent & Event, SState & To ) { From.OnExit( Event, To ); To.OnEnter( From, Event ); } }; |
Стратегию по умолчанию (не вызывать никакую функцию) можно передать в качестве аргумента шаблона. Стратегия вызова функций, скорее всего, будет меняться чаще, чем стратегия действий при неизвестном событии. Поэтому ее имеет смысл поместить в списке аргументов перед стратегией реакции на неизвестное событие:
|
template <class SState, class SEvent, class SFunctor = SEmptyFunctor<SState,SEvent>, class SUnknownEventStrategy = SThrowStrategy<SEvent> > class SFiniteStateMachine { . . . }; |
Еще один вопрос, связанный с событиями, состоит в том, что событие может быть сгенерировано внутри функции, вызываемой при выходе или входе в состояние. Для обработки таких событий надо соответствующим образом спроектировать функцию, принимающую событие. С учетом таких “внутренних” событий, надо предусмотреть очередь, в которую будут помещаться события. Код, который обрабатывает переходы, должен будет делать это до тех пор, пока очередь не опустеет. В качестве контейнера, подходящего для хранения событий, воспользуемся deque из STL. Поскольку нам нужны только вставка элементов в начало и исключение из конца контейнера, без произвольного доступа, контейнер deque подойдет лучше всего.
Осталось совсем немного. Иногда нужно привести автомат в исходное состояние. Как и в случае с событиями предусмотрим два варианта: обычная функция и перегруженный operator <<. Для перегруженного operator << нужно определить специальный манипулятор:
|
enum SMachineManipulator { ResetMachine = 0 }; . . . inline SFiniteStateMachine & operator << ( SMachineManipulator Manipulator ) { if ( Manipulator == ResetMachine ) return Reset(); return *this; } |
Теперь можно будет написать так:
|
// Принять событие Event1 и сбросить автомат в начальное состояние MyMachine << Event1 << RestMachine; |
Результатом работы автомата является состояние, в которое он перешел. Для получения текущего состояния напишем функцию и перегрузим оператор вывода в поток класса автомата:
|
inline StateType GetCurrentState( void ) const { return CurrentState; } template <class SState, class SEvent, class SFunctor, class SUnknownEventStrategy > ostream & operator<< (ostream & Stream, const SFiniteStateMachine<_SState, _SEvent, _SFunctor,_SUnknownEventStrategy> & Machine ) { return Stream << Machine.GetCurrentState(); } |
Теперь, если для класса состояния определен оператор вывода в поток, можно написать такой фрагмент кода:
|
MyMachine << Event1 << RestMachine; cout << MyMachine; // Эквивалентно cout << MyMachine.GetCurrentState(); |
Как уже говорилось, для сокращения времени набора кода и удобочитаемости определены несколько макросов. Они требуют предварительного определения подстановки для типов событий и состояний. Требование связано с тем, что использование вложенных директив препроцессора невозможно. Шаблон же использует Proxy классы, которым также нужны сведения о типах. Поэтому для использования макросов придется сделать так:
|
#define FSMStateType string // Тип состояния #define FSMEventType int // Тип события . . . #undef FSMStateType #undef FSMEventType |
Альтернатива есть: полностью указывать все типы.
Осталось поместить шаблон в пространство имен. После этого им можно пользоваться.
Пример использования шаблона
Напишем код для решения поставленной в начале статьи задачи.
|
#include <iostream> #include <string> using namespace std; #include "FiniteStateMachine.h" using namespace FSM; // Определим тип для событий enum Events { letter = 0, digit = 1 }; int main( int argc, char ** argv ) { #define FSMStateType string #define FSMEventType Events SFiniteStateMachine< StateType, EventType, SEmptyFunctor<StateType,EventType>, SThrowStrategy<EventType> > MyMachine( FSMBEGIN( "empty" ) FSMSTATES "empty" << "number" << "identifier" << "unknown" FSMEVENT(letter) "identifier" << "unknown" << "identifier" << "unknown" FSMEVENT(digit) "number" << "number" << "identifier" << "unknown" FSMEND ); #undef FSMStateType #undef FSMEventType cout << "StartState is: " << MyMachine << endl; MyMachine << digit << digit << letter; cout << "The 'unknown' state is expected. Current state is: " << MyMachine << endl; // Внимание: круглые скобки в следующей строке обязательны. Они обеспечат // правильный порядок выполнения операторов cout << "Reset the machine. Current state is: " << (MyMachine << ResetMachine) << endl; MyMachine << letter << digit << letter; cout << "The 'identifier' state is expected. Current state is: " << MyMachine << endl; return 0; } |
В примере намеренно опущены такие детали, как обработка исключений и введение функций, вызываемых при входе и выходе из состояния. Чтобы продемонстрировать возможность определения стратегий пользователя, в конструкторе MyMachine указаны все параметры, включая параметры по умолчанию.
Требования к клиентским приложениям
Требования немногочисленны. Для классов событий и состояний должны быть определены operator==, operator= и конструктор копирования. operator== используется для поиска событий и состояний в списках алгоритмом STL find. operator= используется при копировании элементов списков. Конструктор копирования используется при инициализации списков и других элементов.
Если клиент пользуется предоставленным функтором для вызова функций входа и выхода, то класс состояния должен реализовывать соответствующие функции: OnExit и OnEnter.
Преимущества и недостатки предложенного решения
Преимущества:
Шаблон строго типизирован. Это означает, что неправильно написанный код не будет принят компилятором, и ошибка не дойдет до времени выполнения программы.
Расширены понятия состояния и события. Теперь это произвольные классы, написанные пользователем.
Не используется оператор reinterpret_cast<…>, способный привести к неправильным результатам.
Все описание автомата сосредоточено в одном месте. Нет привязки к последовательности описания реакций на события.
Гибкость поведения определяется пользовательскими функторами. Предоставляется набор уже готовых функторов.
Возможно динамическое создание описания конечного автомата. Например, можно создать экземпляры Proxy-классов, прочитать из файла описание автомата, а затем создать экземпляр SFiniteStateMachine.
Нет операций создания и удаления объектов с помощью операторов new и delete.
Нет никаких требований к классам состояний и событий (кроме возможности их сравнения).
Недостатки:
Много операций копирования при создании автомата. Однако этот недостаток отчасти компенсируется тем, что обычно автомат создается один раз, а используется многократно.
Надо писать две директивы препроцессора или использовать длинный префикс. Однако это лишь проблема набивки текста.
Лично я готов мириться с этим коротким списком недостатков ради полученных преимуществ.
Возможные пути усовершенствования шаблона
Внимательный читатель заметит, что можно увеличить гибкость и повысить производительность шаблона. В следующем списке перечислены улучшения, лежащие на поверхности:
Можно отказаться от промежуточного класса SFiniteStateMachineProxy. Это позволит сэкономить на копированиях, но внесет потенциальную возможность неправильного использования шаблона.
Можно ввести манипуляторы, которые позволят в явном виде при описании переходов указывать такие, которые надо игнорировать, или генерировать исключение при их появлении.
Потоковая безопасность
В шаблоне используются контейнеры STL, операции с которыми в многопоточной среде могут привести к проблемам. Поскольку при проектировании шаблона ставилась цель разработать независимое от платформы решение, то никаких средств синхронизации в шаблоне нет. Наличие средств синхронизации, как известно, в зависимости от ситуации может быть как достоинством, так и недостатком. Если они не нужны, их наличие только породит дополнительные накладные расходы. Добавить же средства синхронизации в шаблон опытному разработчику не составит труда.
Список литературы
C/C++ User’s Journal, May 2000
Booch G., Rumbaugh J., Jacobson I. The Unified Modeling Language User Guide. Addison-Wesley, 2001
Meyers S. Effective STL. Addison-Wesley, 2001
Alexandrescu A. Modern C++ Design. Addison-Wesley, 2002
Lewis P., Rosenkrantz D., Stearns R. Compiler Design Theory. Addison-Wesley, 1976
Schildt H. С/С++ Programmer’s Reference. Second Edition. Williams, 2000
Meyers S. Effective C++. Second Edition. Addison-Wesley, 1998 and More Effective C++. Addison-Wesley, 1996
Sutter G. Exceptional C++. Addison-Wesley, 2002