Existe um padrão típico de implementação de máquina de estado?

Precisamos implementar uma máquina de estado simples em C .
Uma declaração de switch padrão é a melhor maneira de fazer isso?
Temos um estado atual (estado) e um gatilho para a transição.

switch(state)
{
  case STATE_1:
     state = DoState1(transition);
     break;
  case STATE_2:
     state = DoState2(transition);
     break;
}
...
DoState2(int transition)
{
   // Do State Work
   ...
   if(transition == FROM_STATE_2) {
     // New state when doing STATE 2 -> STATE 2
   }
   if(transition == FROM_STATE_1) {
    // New State when moving STATE 1 -> STATE 2
   }
   return new_state;
}

Existe uma maneira melhor para máquinas de estado simples

EDIT: Para C ++, acho que a biblioteca Boost Statechart pode ser o caminho a percorrer. No entanto, isso não ajuda com C. Vamos nos concentrar no caso de uso de C.

Eu prefiro usar uma abordagem baseada em tabela para a maioria das máquinas de estado:

typedef enum { STATE_INITIAL, STATE_FOO, STATE_BAR, NUM_STATES } state_t;
typedef struct instance_data instance_data_t;
typedef state_t state_func_t( instance_data_t *data );

state_t do_state_initial( instance_data_t *data );
state_t do_state_foo( instance_data_t *data );
state_t do_state_bar( instance_data_t *data );

state_func_t* const state_table[ NUM_STATES ] = {
    do_state_initial, do_state_foo, do_state_bar
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    return state_table[ cur_state ]( data );
};

int main( void ) {
    state_t cur_state = STATE_INITIAL;
    instance_data_t data;

    while ( 1 ) {
        cur_state = run_state( cur_state, &data );

        // do other program logic, run other state machines, etc
    }
}

Isso pode, é claro, ser estendido para suportar várias máquinas de estado, etc. As ações de transição também podem ser acomodadas:

typedef void transition_func_t( instance_data_t *data );

void do_initial_to_foo( instance_data_t *data );
void do_foo_to_bar( instance_data_t *data );
void do_bar_to_initial( instance_data_t *data );
void do_bar_to_foo( instance_data_t *data );
void do_bar_to_bar( instance_data_t *data );

transition_func_t * const transition_table[ NUM_STATES ][ NUM_STATES ] = {
    { NULL,              do_initial_to_foo, NULL },
    { NULL,              NULL,              do_foo_to_bar },
    { do_bar_to_initial, do_bar_to_foo,     do_bar_to_bar }
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    state_t new_state = state_table[ cur_state ]( data );
    transition_func_t *transition =
               transition_table[ cur_state ][ new_state ];

    if ( transition ) {
        transition( data );
    }

    return new_state;
};

A abordagem baseada em tabela é mais fácil de manter e estender e mais simples de mapear para diagramas de estado.

Você deve ter visto minha resposta a outra pergunta C, onde mencionei FSM! É assim que eu faço:

FSM {
  STATE(x) {
    ...
    NEXTSTATE(y);
  }

  STATE(y) {
    ...
    if (x == 0) 
      NEXTSTATE(y);
    else 
      NEXTSTATE(x);
  }
}

Com as seguintes macros definidas

#define FSM
#define STATE(x)      s_##x :
#define NEXTSTATE(x)  goto s_##x

Isso pode ser modificado para se adequar ao caso específico. Por exemplo, você pode ter um arquivo FSMFILEque deseja direcionar ao seu FSM, então você pode incorporar a ação de ler o próximo caractere na própria macro:

#define FSM
#define STATE(x)         s_##x : FSMCHR = fgetc(FSMFILE); sn_##x :
#define NEXTSTATE(x)     goto s_##x
#define NEXTSTATE_NR(x)  goto sn_##x

agora você tem dois tipos de transições: uma vai para um estado e lê um novo caractere, a outra vai para um estado sem consumir nenhuma entrada.

Você também pode automatizar o manuseio de EOF com algo como:

#define STATE(x)  s_##x  : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
                             goto sx_endfsm;\
                  sn_##x :

#define ENDFSM    sx_endfsm:

A vantagem dessa abordagem é que você pode traduzir diretamente um diagrama de estado desenhado em código funcional e, inversamente, pode facilmente desenhar um diagrama de estado a partir do código.

Em outras técnicas de implementação de FSM, a estrutura das transições está enterrada em estruturas de controle (while, if, switch ...) e controlada por valor de variáveis ​​(tipicamente um state variável) e pode ser uma tarefa complexa relacionar o belo diagrama a um código complicado.

Aprendi essa técnica com um artigo publicado na grande revista "Computer Language" que, infelizmente, não é mais publicado.

Eu também usei a abordagem da mesa. No entanto, existe uma sobrecarga. Por que armazenar uma segunda lista de ponteiros? Uma função em C sem o () é um ponteiro const. Então você pode fazer:

struct state;
typedef void (*state_func_t)( struct state* );

typedef struct state
{
  state_func_t function;

  // other stateful data

} state_t;

void do_state_initial( state_t* );
void do_state_foo( state_t* );
void do_state_bar( state_t* );

void run_state( state_t* i ) {
    i->function(i);
};

int main( void ) {
    state_t state = { do_state_initial };

    while ( 1 ) {
        run_state( state );

        // do other program logic, run other state machines, etc
    }
}

Claro, dependendo do seu fator de medo (ou seja, segurança versus velocidade), você pode querer verificar se há dicas válidas. Para máquinas de estado maiores do que três ou mais estados, a abordagem acima deve ser menos instruções do que uma chave equivalente ou abordagem de tabela. Você pode até macro-izar como:

#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))

Além disso, sinto, a partir do exemplo do OP, que há uma simplificação que deve ser feita ao pensar sobre / projetar uma máquina de estado. Não creio que o estado de transição deva ser usado para lógica. Cada função de estado deve ser capaz de desempenhar sua função dada sem conhecimento explícito do (s) estado (s) passado (s). Basicamente, você projeta como fazer a transição do estado em que se encontra para outro estado.

Finalmente, não comece o projeto de uma máquina de estado com base em limites "funcionais", use subfunções para isso. Em vez disso, divida os estados com base em quando você terá que esperar algo acontecer antes de continuar. Isso ajudará a minimizar o número de vezes que você precisa executar a máquina de estado antes de obter um resultado. Isso pode ser importante ao escrever funções de E / S ou manipuladores de interrupção.

Além disso, alguns prós e contras da declaração switch clássica:

Prós:

• está no idioma, por isso é documentado e claro
• estados são definidos onde são chamados
• pode executar vários estados em uma chamada de função
• código comum a todos os estados pode ser executado antes e depois da instrução switch

Contras:

• pode executar vários estados em uma chamada de função
• código comum a todos os estados pode ser executado antes e depois da instrução switch
• a implementação do switch pode ser lenta

Observe os dois atributos que são prós e contras. Acho que a mudança permite a oportunidade de muito compartilhamento entre os estados, e a interdependência entre os estados pode se tornar incontrolável. No entanto, para um pequeno número de estados, pode ser o mais legível e sustentável.

Para uma máquina de estado simples, basta usar uma instrução switch e um tipo de enum para seu estado. Faça suas transições dentro da instrução switch com base em sua entrada. Em um programa real, você obviamente mudaria o "if (input)" para verificar seus pontos de transição. Espero que isto ajude.

typedef enum
{
    STATE_1 = 0,
    STATE_2,
    STATE_3
} my_state_t;

my_state_t state = STATE_1;

void foo(char input)
{
    ...
    switch(state)
    {
        case STATE_1:
            if(input)
                state = STATE_2;
            break;
        case STATE_2:
            if(input)
                state = STATE_3;
            else
                state = STATE_1;
            break;
        case STATE_3:
            ...
            break;
    }
    ...
}

No UML Distilled de Martin Fowler , ele afirma (sem trocadilhos) no Capítulo 10 Diagramas de Máquina de Estado (grifo meu):

Um diagrama de estado pode ser implementado de três maneiras principais: switch aninhado , o padrão de estado e tabelas de estado .

Vamos usar um exemplo simplificado dos estados da tela de um telefone celular:

Switch aninhado

Fowler deu um exemplo de código C #, mas eu o adaptei ao meu exemplo.

public void HandleEvent(PhoneEvent anEvent) {
    switch (CurrentState) {
    case PhoneState.ScreenOff:
        switch (anEvent) {
        case PhoneEvent.PressButton:
            if (powerLow) { // guard condition
                DisplayLowPowerMessage(); // action
                // CurrentState = PhoneState.ScreenOff;
            } else {
                CurrentState = PhoneState.ScreenOn;
            }
            break;
        case PhoneEvent.PlugPower:
            CurrentState = PhoneState.ScreenCharging;
            break;
        }
        break;
    case PhoneState.ScreenOn:
        switch (anEvent) {
        case PhoneEvent.PressButton:
            CurrentState = PhoneState.ScreenOff;
            break;
        case PhoneEvent.PlugPower:
            CurrentState = PhoneState.ScreenCharging;
            break;
        }
        break;
    case PhoneState.ScreenCharging:
        switch (anEvent) {
        case PhoneEvent.UnplugPower:
            CurrentState = PhoneState.ScreenOff;
            break;
        }
        break;
    }
}

Padrão de estado

Aqui está uma implementação do meu exemplo com o padrão GoF State:

Tabelas de estado

Inspirando-se em Fowler, aqui está uma tabela para meu exemplo:

Ação de proteção de evento de estado de destino de estado de origem
-------------------------------------------------- ------------------------------------
Tela Desligar TelaDesligar pressioneBotton powerLow displayLowPowerMessage  
ScreenOff ScreenOn pressButton! PowerLow
ScreenOn ScreenOff pressButton
ScreenOff ScreenCharging plugPower
ScreenOn ScreenCharging plugPower
ScreenCharging ScreenOff unplugPower

Comparação

O switch aninhado mantém toda a lógica em um local, mas o código pode ser difícil de ler quando há muitos estados e transições. É possivelmente mais seguro e fácil de validar do que as outras abordagens (sem polimorfismo ou interpretação).

A implementação do padrão State potencialmente espalha a lógica por várias classes separadas, o que pode dificultar sua compreensão como um todo. Por outro lado, as turmas pequenas são fáceis de entender separadamente. O design é particularmente frágil se você alterar o comportamento adicionando ou removendo transições, pois são métodos na hierarquia e pode haver muitas alterações no código. Se você seguir o princípio de design de interfaces pequenas, verá que esse padrão realmente não funciona tão bem. No entanto, se a máquina de estado for estável, essas mudanças não serão necessárias.

A abordagem das tabelas de estado requer a escrita de algum tipo de interpretador para o conteúdo (isso pode ser mais fácil se você tiver reflexos na linguagem que está usando), o que pode ser muito trabalhoso desde o início. Como Fowler aponta, se sua tabela for separada de seu código, você pode modificar o comportamento de seu software sem recompilar. Isso tem algumas implicações de segurança, no entanto; o software está se comportando com base no conteúdo de um arquivo externo.

Editar (não realmente para a linguagem C)

Também existe uma abordagem de interface fluente (também conhecida como Linguagem Específica de Domínio Interna), que provavelmente é facilitada por linguagens que possuem funções de primeira classe . A biblioteca Stateless existe e esse blog mostra um exemplo simples com código. Uma implementação Java (pré Java8) é discutida. Também vi um exemplo de Python no GitHub .

há também a grade lógica que é mais sustentável conforme a máquina de estado fica maior

Para casos simples, você pode mudar o método de estilo. O que descobri que funciona bem no passado também é lidar com as transições:

static int current_state;    // should always hold current state -- and probably be an enum or something

void state_leave(int new_state) {
    // do processing on what it means to enter the new state
    // which might be dependent on the current state
}

void state_enter(int new_state) {
    // do processing on what is means to leave the current atate
    // might be dependent on the new state

    current_state = new_state;
}

void state_process() {
    // switch statement to handle current state
}

Não sei nada sobre a biblioteca boost, mas esse tipo de abordagem é muito simples, não requer nenhuma dependência externa e é fácil de implementar.

switch () é uma maneira poderosa e padrão de implementar máquinas de estado em C, mas pode diminuir a capacidade de manutenção se você tiver um grande número de estados. Outro método comum é usar ponteiros de função para armazenar o próximo estado. Este exemplo simples implementa um flip-flop set / reset:

/* Implement each state as a function with the same prototype */
void state_one(int set, int reset);
void state_two(int set, int reset);

/* Store a pointer to the next state */
void (*next_state)(int set, int reset) = state_one;

/* Users should call next_state(set, reset). This could
   also be wrapped by a real function that validated input
   and dealt with output rather than calling the function
   pointer directly. */

/* State one transitions to state one if set is true */
void state_one(int set, int reset) {
    if(set)
        next_state = state_two;
}

/* State two transitions to state one if reset is true */
void state_two(int set, int reset) {
    if(reset)
        next_state = state_one;
}

Eu encontrei uma implementação em C realmente inteligente de Moore FSM no curso edx.org Embedded Systems - Shape the World UTAustinX - UT.6.02x, capítulo 10, de Jonathan Valvano e Ramesh Yerraballi ....

struct State {
  unsigned long Out;  // 6-bit pattern to output
  unsigned long Time; // delay in 10ms units 
  unsigned long Next[4]; // next state for inputs 0,1,2,3
}; 

typedef const struct State STyp;

//this example has 4 states, defining constants/symbols using #define
#define goN   0
#define waitN 1
#define goE   2
#define waitE 3


//this is the full FSM logic coded into one large array of output values, delays, 
//and next states (indexed by values of the inputs)
STyp FSM[4]={
 {0x21,3000,{goN,waitN,goN,waitN}}, 
 {0x22, 500,{goE,goE,goE,goE}},
 {0x0C,3000,{goE,goE,waitE,waitE}},
 {0x14, 500,{goN,goN,goN,goN}}};
unsigned long currentState;  // index to the current state 

//super simple controller follows
int main(void){ volatile unsigned long delay;
//embedded micro-controller configuration omitteed [...]
  currentState = goN;  
  while(1){
    LIGHTS = FSM[currentState].Out;  // set outputs lines (from FSM table)
    SysTick_Wait10ms(FSM[currentState].Time);
    currentState = FSM[currentState].Next[INPUT_SENSORS];  
  }
}

Você pode querer dar uma olhada no software gerador do libero FSM. A partir de uma linguagem de descrição de estado e / ou um editor de diagrama de estado (Windows), você pode gerar código para C, C ++, java e muitos outros ... além de documentação e diagramas legais. Fonte e binários do iMatix

Este artigo é bom para o padrão de estado (embora seja C ++, não especificamente C).

Se você puder colocar as mãos no livro " Head First Design Patterns ", a explicação e o exemplo são muito claros.

Um dos meus padrões favoritos é o padrão de design de estado. Responda ou se comporte de maneira diferente para o mesmo conjunto de entradas fornecido.
Um dos problemas com o uso de instruções switch / case para máquinas de estado é que à medida que você cria mais estados, o switch / cases torna-se mais difícil / difícil de ler / manter, promove código espaguete desorganizado e cada vez mais difícil de alterar sem quebrar algo. Acho que usar padrões de projeto me ajuda a organizar melhor meus dados, o que é todo o ponto de abstração. Em vez de projetar seu código de estado em torno de qual estado você veio, em vez disso, estruture seu código para que ele registre o estado quando você entrar em um novo estado. Dessa forma, você obtém efetivamente um registro de seu estado anterior. Gosto da resposta de @JoshPetit e levei sua solução um passo adiante, tirada diretamente do livro GoF:

stateCtxt.h:

#define STATE (void *)
typedef enum fsmSignal
{
   eEnter =0,
   eNormal,
   eExit
}FsmSignalT;

typedef struct fsm 
{
   FsmSignalT signal;
   // StateT is an enum that you can define any which way you want
   StateT currentState;
}FsmT;
extern int STATECTXT_Init(void);
/* optionally allow client context to set the target state */
extern STATECTXT_Set(StateT  stateID);
extern void STATECTXT_Handle(void *pvEvent);

stateCtxt.c:

#include "stateCtxt.h"
#include "statehandlers.h"

typedef STATE (*pfnStateT)(FsmSignalT signal, void *pvEvent);

static FsmT      fsm;
static pfnStateT UsbState ;

int STATECTXT_Init(void)
{    
    UsbState = State1;
    fsm.signal = eEnter;
    // use an enum for better maintainability
    fsm.currentState = '1';
    (*UsbState)( &fsm, pvEvent);
    return 0;
}

static void ChangeState( FsmT *pFsm, pfnStateT targetState )
{
    // Check to see if the state has changed
    if (targetState  != NULL)
    {
        // Call current state's exit event
        pFsm->signal = eExit;
        STATE dummyState = (*UsbState)( pFsm, pvEvent);

        // Update the State Machine structure
        UsbState = targetState ;

        // Call the new state's enter event
        pFsm->signal = eEnter;            
        dummyState = (*UsbState)( pFsm, pvEvent);
    }
}

void STATECTXT_Handle(void *pvEvent)
{
    pfnStateT newState;

    if (UsbState != NULL)
    {
         fsm.signal = eNormal;
         newState = (*UsbState)( &fsm, pvEvent );
         ChangeState( &fsm, newState );
    }        
}


void STATECTXT_Set(StateT  stateID)
{
     prevState = UsbState;
     switch (stateID) 
     {
         case '1':               
            ChangeState( State1 );
            break;
          case '2':
            ChangeState( State2);
            break;
          case '3':
            ChangeState( State3);
            break;
     }
}

statehandlers.h:

/* define state handlers */
extern STATE State1(void);
extern STATE State2(void);
extern STATE State3(void);

statehandlers.c:

#include "stateCtxt.h:"

/* Define behaviour to given set of inputs */
STATE State1(FsmT *fsm, void *pvEvent)
{   
    STATE nextState;
    /* do some state specific behaviours 
     * here
     */
    /* fsm->currentState currently contains the previous state
     * just before it gets updated, so you can implement behaviours 
     * which depend on previous state here
     */
    fsm->currentState = '1';
    /* Now, specify the next state
     * to transition to, or return null if you're still waiting for 
     * more stuff to process.  
     */
    switch (fsm->signal)
    {
        case eEnter:
            nextState = State2;
            break;
        case eNormal:
            nextState = null;
            break;
        case eExit:
            nextState = State2;
            break;
    }

    return nextState;
}

STATE  State3(FsmT *fsm, void *pvEvent)
{
    /* do some state specific behaviours 
     * here
     */
    fsm->currentState = '2';
    /* Now, specify the next state
     * to transition to
     */
     return State1;
}

STATE   State2(FsmT *fsm, void *pvEvent)
{   
    /* do some state specific behaviours 
     * here
     */
    fsm->currentState = '3';
    /* Now, specify the next state
     * to transition to
     */
     return State3;
}

Para a maioria das máquinas de estado, esp. Máquinas de estados finitos, cada estado saberá qual deve ser seu próximo estado e os critérios para fazer a transição para seu próximo estado. Para designs de estado flexível, esse pode não ser o caso, daí a opção de expor a API para estados de transição. Se você deseja mais abstração, cada manipulador de estado pode ser separado em seu próprio arquivo, que são equivalentes aos manipuladores de estado concreto no livro GoF. Se o seu design for simples com apenas alguns estados, stateCtxt.c e statehandlers.c podem ser combinados em um único arquivo para simplificar.

Na minha experiência, o uso da instrução 'switch' é a maneira padrão de lidar com vários estados possíveis. Embora eu esteja surpreso que você esteja passando um valor de transição para o processamento por estado. Achei que o objetivo principal de uma máquina de estado era que cada estado executava uma única ação. Então, a próxima ação / entrada determina para qual novo estado fazer a transição. Portanto, eu esperava que cada função de processamento de estado executasse imediatamente tudo o que for corrigido para entrar no estado e, depois, decidisse se a transição para outro estado é necessária.

Existe um livro intitulado Practical Statecharts in C / C ++ . No entanto, é maneira demasiado pesado para o que precisamos.

Para compiladores que suportam __COUNTER__, você pode usá-los para mashines de estado simples (mas grandes).

  #define START 0      
  #define END 1000

  int run = 1;
  state = START;    
  while(run)
  {
    switch (state)
    {
        case __COUNTER__:
            //do something
            state++;
            break;
        case __COUNTER__:
            //do something
            if (input)
               state = END;
            else
               state++;
            break;
            .
            .
            .
        case __COUNTER__:
            //do something
            if (input)
               state = START;
            else
               state++;
            break;
        case __COUNTER__:
            //do something
            state++;
            break;
        case END:
            //do something
            run = 0;
            state = START;
            break;
        default:
            state++;
            break;
     } 
  } 

A vantagem de usar em __COUNTER__vez de números codificados é que você pode adicionar estados no meio de outros estados, sem renumerar tudo sempre. Se o compilador não suporta __COUNTER__, de forma limitada é possível usar com precaução__LINE__

Você pode usar a estrutura de máquina de estado UML minimalista em c. https://github.com/kiishor/UML-State-Machine-in-C

Ele suporta máquinas de estado finitas e hierárquicas. Possui apenas 3 APIs, 2 estruturas e 1 enumeração.

A máquina de estado é representada por state_machine_testrutura. É uma estrutura abstrata que pode ser herdada para criar uma máquina de estado.

//! Abstract state machine structure
struct state_machine_t
{
   uint32_t Event;          //!< Pending Event for state machine
   const state_t* State;    //!< State of state machine.
};

O estado é representado por um ponteiro para a state_testrutura no framework.

Se a estrutura estiver configurada para máquina de estado finito, então state_tcontém,

typedef struct finite_state_t state_t;

// finite state structure
typedef struct finite_state_t{
  state_handler Handler;        //!< State handler function (function pointer)
  state_handler Entry;          //!< Entry action for state (function pointer)
  state_handler Exit;           //!< Exit action for state (function pointer)
}finite_state_t;

A estrutura fornece uma API dispatch_eventpara despachar o evento para a máquina de estado e duas APIs para a passagem de estado.

state_machine_result_t dispatch_event(state_machine_t* const pState_Machine[], uint32_t quantity);

state_machine_result_t switch_state(state_machine_t* const, const state_t*);

state_machine_result_t traverse_state(state_machine_t* const, const state_t*);

Para obter mais detalhes sobre como implementar a máquina de estado hierárquico, consulte o repositório GitHub.

exemplos de código
https://github.com/kiishor/UML-State-Machine-in-C/blob/master/demo/simple_state_machine/readme.md
https://github.com/kiishor/UML-State-Machine-in -C / blob / master / demo / simple_state_machine_enhanced / readme.md

Em C ++, considere o padrão State .

Sua pergunta é semelhante a "existe um padrão típico de implementação de banco de dados"? A resposta depende do que você deseja alcançar? Se você deseja implementar uma máquina de estado determinística maior, você pode usar um modelo e um gerador de máquina de estado. Os exemplos podem ser vistos em www.StateSoft.org - SM Gallery. Janusz Dobrowolski

Boost tem a biblioteca de gráficos de estados. http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html

Eu não posso falar sobre como usá-lo, no entanto. Não usei sozinho (ainda)