Knockin 'on Heaven, o FSM en plantillas

¡Hola! Mi nombre es Alexander, trabajo como ingeniero de software de microcontroladores.





Escribo en C / C ++, y prefiero las ventajas, porque creo en su inevitabilidad evolutiva en embedded.





El mundo del software integrado, el lenguaje C ++, se está desarrollando dinámicamente, por lo que es importante que los desarrolladores se mantengan al día y actualicen sus habilidades y desarrollos.





Intento seguir este mensaje obvio, ya que los celestiales, los principales programadores y consultores de C ++ comparten generosamente su experiencia e ideas en diferentes plataformas (por ejemplo, aquí o aquí ).





Hace algún tiempo, vi una poderosa charla de Sergei Fedorov sobre la construcción de una máquina de estados finitos con una tabla de transición en plantillas.





Si de repente: "¿qué es una máquina de estado?"

Una máquina de estados finitos, o FSM (máquina de estados finitos), es una de las técnicas más demandadas y populares en la programación de MC. A la hora de la breve y práctica guía para cocinar FSM me dirigí a lo abandonado , la tierra .





Una de las ideas del informe es definir estados, eventos y acciones mediante tipos personalizados, e implementar la tabla de transición a través de un parámetro de plantilla, estoy muy





impresionado
// Transition table definition

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

// State machine object
using minimal = state_machine<transitions>;
minimal fsm;

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







Y si a esto le sumamos la transferencia de una parte de la funcionalidad del código al tiempo de compilación, la seguridad del hilo declarada por el autor, la expresividad, la legibilidad del código y la velocidad de construcción mejoraron en comparación con Boost :: MSM, el modelo de encabezado único de la biblioteca, luego decidí tomarla .





Aquí hay solo un intento de construir y ejecutar incluso el ejemplo más simple en STM-ke que terminó con el lenguaje obsceno del compilador: "no se puede usar 'typeid' con" -fno-rtti "y" manejo de excepciones deshabilitado ".





, . , RTTI , -fno-cxa-atexit, -fno-threadsafe-static. --specs=nano.specs ( ++ newlib-nano), --specs=nosys.specs ( ).





?

Embedded , :





  • ;





  • ;





  • main





++ , .





++ bare metal . .





, , - . , typeid exceptions, - too much.





, , RTTI, throw .





. gcc-arm-none-eabi-9-2020-q2-update -O3, 200.





, - " ".





, STM, 1, , , , , .





, , . , - " " - extra light embedded FSM .





:





  • , .

























  • header only





, , - .





- , . , .





:





/State
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 .





/Event
struct EventBase{};

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







, .





:





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







, operator() , .





:





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







- , /transition-a. , . . , , , . Up to you.





, . .





:





Transition
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.





. .





:





Transition table
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





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







StateMachine , .





- .





StateMachine , , .





transitions
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 :





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







idx . , . typeid _cxa_demangle , , RTTI.





events
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:





state and 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, :





set
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().





,





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) , , .





, , , . , , . callable object.





on_event
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), . .





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







.





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







, .





process
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, PRIRITY_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.





, , . , .





Será genial si la comunidad señala fakups inminentes y señala el camino para mejoras. También me atrevo a esperar que alguien separe algo útil del material.





¡Gracias por su atención!








All Articles