Достучаться до небес, или FSM на шаблонах

Здравствуйте! Меня зовут Александр, я работаю инженером-программистом микроконтроллеров.

Пишу на С/С++, причем предпочитаю плюсы, ибо верую в их эволюционную неизбежность в embedded.

Мир встроенного ПО, язык С++ динамично развиваются, поэтому разработчикам важно не отставать и поддерживать свои скиллы и наработки актуальными моменту.

Я стараюсь следовать этому очевидному посылу, благо небожители ведущие С++ программисты и консультанты щедро делятся своим опытом и идеями на разных площадках (например здесь, или здесь).

Некоторое время назад я посмотрел мощный доклад Сергея Федорова про построение конечного автомата с таблицей переходов на шаблонах.

Одна из идей доклада - определить состояния, эвенты и действия через пользовательские типы, а таблицу переходов реализовать через шаблонный параметр, меня очень

// Transition table definition

using transitions =
  transition_table<
  /*  State       Event       Next       */
  tr< initial,    start,      running    >,
  tr< running,    stop,       terminated >>;
};

// State machine object
state_machine<transitions> fsm;

//...and then call
fsm.process_event(start{});
fsm.process_event(stop{});

А если добавить к этому перенос части функциональности кода в компайл тайм, заявленную автором потокобезопасность, улучшенные по сравнению с Boost::MSM выразительность, читаемость кода и скорость сборки, header only модель библиотеки, то - надо брать, решил я.

Вот только попытка собрать и запустить даже простейший пример на STM-ке закончилась матерком компилятора: "cannot use 'typeid' with "-fno-rtti" и "exception handling disabled".

Да, все так. Более того, помимо отключенной поддержки RTTI и исключений, у меня также выставлены флаги -fno-cxa-atexit, -fno-threadsafe-static. А еще в линкере применены настройки --specs=nano.specs (используем урезанную версию стандартной библиотеки с++ newlib-nano), --specs=nosys.specs (применяем легковесные заглушки для системных вызовов).

Исходники проекта докладчика, включая зависимости, - это двадцать файлов со смертоноснейшей шаблонной магией. Перекроить их так, чтобы не юзать typeid и exceptions, простому смертному в моем лице - too much.

Делать нечего, поступимся принципами, включим поддержку RTTI, а вместо throw в исходниках автора проставим заглушки.

На этот раз все собралось. Вот только при использовании тулчейна gcc-arm-none-eabi-9-2020-q2-update и уровне оптимизации -O3, размер исполняемого файла превысил 200Кб.

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

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

Итак, с наскоку взять высоту не удалось, и я на некоторое время переключился на другие задачи. Но красота идеи меня не отпускала, и на днях я все-таки решился "достучаться до небес" - написать extra light embedded версию FSM из упомянутого доклада самостоятельно.

Уточню свои хотелки:

• Оперировать состояниями, эвентами и действиями как пользовательскими типами.

• Таблицу переходов реализовать в виде шаблонного параметра

• Перетащить что возможно в компайл тайм

• Асинхронно и атомарно постить эвенты

• Переключать состояния за константное время

• Выйти в итоге на приемлемый по меркам встроенного ПО размер кода

• Повторить header only модель библиотеки

Забегая вперед, скажу, что в итоге что-то получилось и даже взлетело.

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

Первым делом опишем базовые сущности:

struct StateBase{};

template <base_t N, typename Action = void>
struct State : StateBase{
  static constexpr base_t idx = N;
  using action_t = Action;
  };

Здесь и далее base_t - платформозависимый тип, машинное слово. В моем случае это unsigned int.

Состояния пусть будут двух типов - пассивное, в котором никаких действий не происходит, и активное - при нахождении в котором будет выполнятся переданный шаблонным параметром функтор, action_t.

Цель статического члена idx уточню далее по тексту.

struct EventBase{};

template <base_t N>
struct Event : EventBase{
  static constexpr base_t idx = N;
};

Элементарная структура, все ясно.

Действие при наступлении события и смене состояний:

struct action{
  void operator()(void){
    // do something
};

Безусловно, сигнатура operator() может и должна варьироваться от задач приложения, пока же для упрощения остановимся на самом легковесном варианте.

Сторож состояния:

enum class Guard : base_t{
  OFF,
  CONDITION_1,
  CONDITION_2,
  //etc.
};

Идея сторожа - допустить переход в новое состояние, только если в данный момент выполнения программы текущее значение сторожа соответствует заданному пользователем значению в типе перехода/transition-a. Если такого соответствия нет, то переход в новое состояние не происходит. Но тут возможны варианты. Например, все же переходить, но не выполнять действие, переданное в состояние. Up to you.

Итак, пока все тривиально. Идем дальше.

Переход:

struct TrBase{};

template <typename Source,
          typename Event,
          typename Target,
          typename Action,
          Guard G,
          class =
          std::enable_if_t<std::is_base_of_v<StateBase, Source>&&
          std::is_base_of_v<EventBase, Event> &&
          std::is_base_of_v<StateBase, Target>>
          >
  
struct Tr : TrBase{
  using source_t = Source;
  using event_t  = Event;
  using target_t = Target;
  using action_t = Action;
  
  static constexpr Guard guard = G;
};

Структура Tr тоже элементарна. Она параметризуется типом исходного состояния - Source, типом события Event, по наступлению которого произойдет переход в целевое состояние Target, и типом Guard.

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

Таблица переходов:

struct TransitionTableBase{};

template<typename... T>
struct TransitionTable : TransitionTableBase{
  
  using test_t = typename NoDuplicates<Collection<T...>>::Result;
  
  static_assert(std::is_same_v<test_t, Collection<T...>>,
                "Repeated transitions");
  
  using transition_p = type_pack<T...>;
  
  using state_collection = typename NoDuplicates 
  <Collection<typename T::source_t... ,typename T::target_t...>
   >::Result;
  
  using event_collection = typename NoDuplicates
  <Collection<typename T::event_t...>
    >::Result;
  
  using state_v = decltype(get_var(state_collection{}));
  using event_v = decltype(get_var(event_collection{}));
  using transition_v = std::variant<T...>;
};

Нуу, тут я набросил на вентилятор, конечно. Хотя все не настолько пугающе, как выглядит.

Структура TransitionTable параметризуется списком переходов/transition-ов, которые собственно и описывают всю логику конечного автомата.

Первым делом нам необходимо подстраховать себя от копипаста и просигналить при компиляции, что у нас повторы в списке. Исполняем это с помощью алгоритма NoDuplicates из всем известной библиотеки Loki. Результирующий тип под псевдонимом test_t сравниваем в static_assert-e с исходным списком переходов.

Далее, допуская что static_assert пройден, параметризуем некую структуру type_pack списком переходов и выведенному типу назначаем псевдоним transition_p. Структура type_pack, а также современные алгоритмы и методы по работе со списками типов собраны в файле typelist.h. Данный хедер написан под чутким руководством этого продвинутого парня.

Тип transition_p понадобится нам далее в конструкторе класса StateMachine.

Следом проходим по списку переходов, вытаскиваем, очищаем от повторов и сохраняем в отдельные коллекции состояния и эвенты. Эти коллекции alias-им как state_collection и event_collection соответственно.

К чему эта эквилибристика?

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

Удобным вариантом для этой цели является std::variant (тавтология умышлена).

Последовательно параметризуем std::variant списком переходов (выведенному типу назначим псевдоним transition_v); списком состояний и списком эвентов и назначаем для удобства псевдонимы state_v и event_v соответственно.

Тут нюанс. Чтобы вывести transition_v нам достаточно пробросить в шаблонный параметр std::variant variadic pack (T...) из шаблонного параметра класса TransitionTable.

А вот чтобы вывести state_v и event_v мы используем

template<typename... Types>
constexpr auto get_var (Collection<Types...>){
	return std::variant<Types...>{};
}

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

Оставшихся к этому моменту читателей я не обрадую - начинается основной замес.

Целиком приводить класс StateMachine не буду, он громоздок, прокомментирую его для удобства восприятия по частям.

template<typename Table>
class StateMachine{

//other stuff

private:
using map_type =
std::unordered_map < Key, transition_v, KeyHash, KeyEqual>;

Key key;
map_type transitions;
};

Основной контейнер, в котором мы храним информацию о переходах. Unordered - потому что мы хотим константное время для переключения между событиями. Память под контейнер выделяем стандартным аллокатором из кучи, но делаем это единожды, на этапе инициализации, до входа в основной цикл.

Объект типа Key хранит у себя значения индексов состояния и эвента:

struct Key{
  base_t state_idx = 0;
  base_t event_idx = 0;
};

Теперь стало понятно назначение статических членов idx в базовых сущностях. Я просто не знаю, как писать хэшеры для пустых структур. Тащить в строку название самого типа через typeid и _cxa_demangle для нас не вариант, мы же условились, что не пользуем RTTI.

template<typename Table>
class StateMachine{

//other stuff

private:

using queue_type =
  RingBufferPO2 <EVENT_STACK_SIZE, event_v, Atomic>;
  
  queue_type events;
};

events - очередь, в которую будут прилетать эвенты. Так как это чисто рантаймовая история, необходимо избежать динамических аллокаций. Поэтому реализуем ее на базе статического кольцевого буффера RingBufferPO2, который я позаимствовал здесь (отличная для своего времени работа!).

Помимо указанных контейнеров, в объекте типа StateMachine мы будем хранить текущее состояние/state и значение сторожа/guard:

template<typename Table>
class StateMachine{

//other stuff

private:

state_v current_state;
Guard guard = Guard::OFF;
};

Саспенс уже не за горами.

template<typename Table>
class StateMachine{

public:

using transition_pack = typename Table::transition_p;

StateMachine(){
  set(transition_pack{});
} 

// other stuff
};

В конструкторе метод set принимает аргументом объект с информацией о списке переходов, пробегается по нему, достает инфо о каждом состоянии и эвенте, заполняет контейнер transitions, а также запоминает начальные состояние и значение сторожа:

template <class... Ts>
void set (type_pack<Ts...>){
	(set_impl(just_type<Ts>{}), ...);
};


template <typename T>
void set_impl (just_type<T> t){

	using transition = typename decltype(t)::type;

	using state_t = typename transition::source_t;
	using event_t = typename transition::event_t;
	Guard g = transition::guard;

	Key k;

	k.state_idx = state_t::idx;
	k.event_idx = event_t::idx;

	transitions.insert( {k, transition{}} );

	if (0 == key.state_idx) {

		key.state_idx = k.state_idx;
		guard = g;
		current_state = state_t{};
	}
}

Итак, объект StateMachine сконструирован, пора его как-то шевелить.

Но перед этим забудем как страшный сон суммируем что уже рассмотрели к этому моменту:

• Определили типы компонентов конечного автомата: состояние/state, событие/event, действие/action, сторож/guard

• Определили тип переход/transition, который должен параметризоваться типами source state, event, target state, guard.

• Определили тип таблицы переходов. В качестве шаблонных параметров ему передается список переходов/transition-ов, который и определяет алгоритмы работы автомата.

• При компиляции в классе TransitionTable, на основе std::variant выводятся типы-коллекции переходов, состояний и эвентов, которые впоследствии при конструировании объекта StateMachine инстанцируются и сохраняются в контейнеры, с которыми уже можно работать в рантайме.

Стержневая идея моей имплементации автомата такова (вдохнули): при наступлении события, мы достаем из его типа индекс (idx), объединяем его с индексом текущего состояния в объекте Key, по которому в контейнере transitions находим нужный нам переход, где получаем знания о целевом состоянии, стороже и действии, которое требуется выполнить в этом переходе, а также сверяем значения сторожа с текущим, для подтверждения или отмены перехода/действия(выдохнули).

Теперь рассмотрим методы API нашего автомата, реализующие эту логику.

Переключать состояния мы можем двумя способами: вызывать немедленный переход методом fsm.on_event(event{}) (шаблонная версиия fsm.on_event<Event>() если тип события известен на этапе проектирования), или можем складывать события в очередь методом fsm.push_event(event{}), чтобы потом, например в основном цикле, разобрать ее методом fsm.process(). Также, если в состояние передано какое-то действие, то мы можем вызывать его методом fsm.state_action().

Рассмотрим их детальнее, начиная с последнего

template <typename... Args>
void state_action (const Args&... args){

  state_v temp_v{current_state};
  
  auto l = [&](const auto& arg){
  	
    using state_t =  std::decay_t<decltype(arg)>;
    using functor_t = typename state_t::action_t;
    
    if constexpr (!std::is_same_v<functor_t, void>){
    	functor_t{}(args...);
      }
  };
  
  std::visit(l, temp_v);
}
  

В методе мы создаем локальную переменную типа std::variant<State...> temp_v и инициализируем ее текущим состоянием. Далее определяем лямбду, которая послужит аргументом в методе std::visit.

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

template <typename Event,
class = std::enable_if_t<std::is_base_of_v<EventBase, Event>>>

void on_event(const Event& e){
  Key k;
  k.event_idx = e.idx;
  k.state_idx = key.state_idx;
  on_event_impl(k);
}

void on_event_impl (Key& k){

  transition_v tr_var = transitions[k];
  
  Key &ref_k = key;
  Guard &ref_g = guard;
  state_v &ref_state = current_state;
  
  auto l = [&](const auto& arg){
  
  	using tr_t =  std::decay_t<decltype(arg)>;
    using functor_t = typename tr_t::action_t;
    
    if ( GuardEqual{}(ref_g, tr_t::guard) ){
    	
      using target_t = typename tr_t::target_t;
      
      ref_k.state_idx = target_t::idx;
      ref_state = target_t{};
      
      functor_t{}();
      }
   };
   
   std::visit(l, tr_var);
}

Здесь, как я уже описывал, мы достаем индекс из эвента, объединяем его в Key с индексом текущего состояния, и в качестве ключа передаем в приватный метод on_event_impl(Key& k).

Там мы по принятому ключу достаем из контенера transitions объект типа std::variant<Tr...> и инициализируем им локальную переменную tr_var. Ну а далее - логика, схожая с предыдущим примером. Вызываем std::visit c tr_var и лямдой l, в которой из типа Tr получаем сведения о состоянии, в которое нужно перейти (target_t), стороже (tr_t::guard)и типе действия (functor_t) к исполнению.

Сверив значение сторожа перехода с текущим сторожем, мы или оcуществляем переход, инстанцируя и вызывая functor_t, и сохраняя target_t в переменную с текущим состоянием(current_state), или возвращаемся в исходное состояние. Где ждем смены значения сторожа и нового события.

template <unsigned int N>
void push_event (const Event<N>& e){
  events.push_back(e);
}

Тут все просто.

void set_guard (const Guard& g){
  guard = g;
}

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

void process (void){
  
  state_action();
  
  auto it = transitions.begin();
  
  Key k;
  k.state_idx = key.state_idx;
  
  for (uint32_t i = 0; i != events.size(); ++i){
    
    auto v = events.front(); 
    auto l = [&](const auto& arg){
      using event_t =  std::decay_t<decltype(arg)>;
      k.event_idx = event_t::idx;
      it = transitions.find(k);
    }
    
    std::visit(l, v);
    
    if ( it != transitions.end() ){
      
      events.pop_front();
      on_event_impl(k);
      return;
    
    } else {
      events.push_back(v);
      events.pop_front();
    }
  }
}

При вызове метода мы первым делом выполняем некое полезное действие (если не void), переданное в состояние, state_action().

Ну а далее пробегаемся по очереди эвентов и просто воспроизводим логику, уже описанную для метода fsm.on_event(event{}).

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

template <base_t N, base_t Priority>
struct Event : EventBase{
  static constexpr base_t idx = N;
  static constexpr base_t pri = Priority;
};

Теперь мы можем не пушить все события в одну очередь, а завести, скажем, std::array<queue_t, PRIORITY_NUM>, где индексом ячейки будет служить приоритет события. Тогда у нас получится приняв эвент, вытащить его приоритет, по нему, как по индексу за константное время попасть в нужную очередь событий, которая будет гораздо меньше, чем общая и быстрее в обработке.

И, что не менее важно, так мы сможем прыгать между состояниями не по очередности принятых эвентов, но по их приоритету.

На самом деле в следующей версии своего FSM у меня так и реализовано, но здесь я привожу упрощенный вариант.

Хорошо, каков же будет практический результат этой разнузданной шаблонной вакханалии?

struct green_a {/*toogle green led every 50ms*/}
struct yellow_a {/*toogle yellow led every 50ms*/}
struct red_a {/*toogle red led every 50ms*/}

struct green_f {/*toogle green led every 150ms*/}
struct yellow_f {/*toogle yellow led every 150ms*/}
struct red_f {/*toogle red led every 150ms*/}

using STATE_A(green_s, green_f);
using STATE_A(yellow_s, yellow_f);
using STATE_A(red_s, red_f);

using EVENT(green_e);
using EVENT(yellow_e);
using EVENT(red_e);

using fsm_table = TransitionTable
    <
    Tr<green_s, yellow_e, yellow_s, yellow_a, Guard::NO_GUARD>,
    Tr<yellow_s, red_e, red_s, red_a, Guard::NO_GUARD>,
    Tr<red_s, green_e, green_s, green_a, Guard::NO_GUARD>
    >;

int main(void){
  //some other stuff

  StateMachine<fsm_table> fsm;

  fsm.push_event(red_e{});
  fsm.push_event(yellow_e{});
  fsm.push_event(green_e{});

  while (1){
    fsm.process();
  }
}

В этом примере структуры типа color_a(ction) - это действия при переходе; color_f(unctor) - функторы, которые будут выполняться каждый раз при заходе в стейт, ну и далее понятно.

Объявляем стейты, эвенты, переходы, таблицу переходов. Конструируем из класса StateMachine<fsm_table> наш конечный автомат fsm. Пушим события, заходим в while и наблюдаем аквасветодискотеку на нашей отладке.

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

using even_t = Event<1, 15>;

using state_t = State<1, state_functor>;

Очевидно, почему это плохо. Ручная индексация - практически неизбежные ошибки и очепятки.

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

#define STATE_A(str, act) str = State<name(#str), act>
#define EVENT(str) str = Event<name(#str)>

constexpr base_t name (const char* n){
  
  base_t  res = 0;
  
  for (base_t i = 0; n[i] != '\0'; i++){
    
    char data = n[i];
    
    for (base_t j = sizeof (char) * 8; j > 0; j--){
      
      res = ((res ^ data) & 1) ? (res >> 1) ^ 0x8C : (res >> 1);
      data >>= 1;
    }
  }
  return res;
};

После крайнего проекта на работе у меня на руках осталась отладка NUCLEO-H743ZI2, на ней я и запилил тестовый вариант (забирайте здесь).

С оптимизацией -O3 реализация приведенного примера (только сам FSM) заняла 6,8Кб, с HAL-ом и моргалками - 14,4Кб.

Конечно же, пока это не более чем эксперимент, проверка концепции. Но агрегат завелся, черт его дери.

Будет очень здорово, если сообщество ткнёт носом в неизбежные факапы и укажет путь к улучшениям. Также смею надеяться, что кто-то выделит из материала и что-то полезное для себя.

Спасибо за внимание!