¿Existe un patrón de implementación de máquina de estado típico?

Necesitamos implementar una máquina de estados simple en C .
¿Es una declaración de cambio estándar la mejor manera de hacerlo?
Tenemos un estado actual (estado) y un disparador para la transición.

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 una forma mejor para las máquinas de estado simples?

EDITAR: Para C ++, creo que la biblioteca Boost Statechart podría ser el camino a seguir. Sin embargo, no ayuda con C. Concentrémonos en el caso de uso de C.

Prefiero usar un enfoque basado en tablas para la mayoría de las 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
    }
}

Por supuesto, esto se puede ampliar para admitir múltiples máquinas de estado, etc. Las acciones de transición también pueden adaptarse:

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;
};

El enfoque basado en tablas es más fácil de mantener y ampliar y más sencillo de asignar a los diagramas de estado.

¡Es posible que haya visto mi respuesta a otra pregunta C en la que mencioné FSM! Así es como lo hago:

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

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

Con las siguientes macros definidas

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

Esto se puede modificar para adaptarse al caso específico. Por ejemplo, es posible que tenga un archivo FSMFILEque desee que controle su FSM, por lo que podría incorporar la acción de leer el siguiente carácter en la macro misma:

#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

ahora tiene dos tipos de transiciones: una va a un estado y lee un nuevo carácter, la otra va a un estado sin consumir ninguna entrada.

También puede automatizar el manejo de EOF con algo como:

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

#define ENDFSM    sx_endfsm:

Lo bueno de este enfoque es que puede traducir directamente un diagrama de estado que dibuja en código de trabajo y, a la inversa, puede dibujar fácilmente un diagrama de estado a partir del código.

En otras técnicas para implementar FSM, la estructura de las transiciones está enterrada en estructuras de control (mientras, si, cambiar ...) y controlada por variables de valor (típicamente un state variable) y puede ser una tarea compleja relacionar el bonito diagrama con un código complicado.

Aprendí esta técnica de un artículo aparecido en la gran revista "Computer Language" que, lamentablemente, ya no se publica.

También he utilizado el enfoque de tabla. Sin embargo, hay gastos generales. ¿Por qué almacenar una segunda lista de punteros? Una función en C sin el () es un puntero constante. Entonces puedes hacer:

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
    }
}

Por supuesto, dependiendo de su factor de miedo (es decir, seguridad frente a velocidad), es posible que desee verificar los indicadores válidos. Para máquinas de estados mayores de tres o más estados, el enfoque anterior debería ser menos instrucciones que un enfoque equivalente de conmutador o tabla. Incluso podría macro-izar como:

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

Además, creo que por el ejemplo del OP, hay una simplificación que se debe hacer al pensar / diseñar una máquina de estado. No creo que el estado de transición deba usarse para la lógica. Cada función de estado debería poder realizar su función dada sin un conocimiento explícito de los estados pasados. Básicamente, usted diseña cómo pasar del estado en el que se encuentra a otro estado.

Finalmente, no inicie el diseño de una máquina de estados basada en límites "funcionales", use subfunciones para eso. En su lugar, divida los estados en función de cuándo tendrá que esperar a que suceda algo antes de poder continuar. Esto ayudará a minimizar la cantidad de veces que tiene que ejecutar la máquina de estado antes de obtener un resultado. Esto puede ser importante al escribir funciones de E / S o manipuladores de interrupciones.

Además, algunos pros y contras de la clásica declaración de cambio:

Pros:

• está en el idioma, por lo que está documentado y es claro
• los estados se definen donde se llaman
• puede ejecutar varios estados en una llamada de función
• el código común a todos los estados se puede ejecutar antes y después de la instrucción de cambio

Contras:

• puede ejecutar varios estados en una llamada de función
• el código común a todos los estados se puede ejecutar antes y después de la instrucción de cambio
• la implementación del cambio puede ser lenta

Tenga en cuenta los dos atributos que son pro y contra. Creo que el cambio brinda la oportunidad de compartir demasiado entre estados, y la interdependencia entre estados puede volverse inmanejable. Sin embargo, para un pequeño número de estados, puede ser el más legible y fácil de mantener.

Para una máquina de estado simple, simplemente use una declaración de cambio y un tipo de enumeración para su estado. Haga sus transiciones dentro de la declaración de cambio según su entrada. En un programa real, obviamente cambiaría el "si (entrada)" para verificar sus puntos de transición. Espero que esto ayude.

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;
    }
    ...
}

En UML Distilled de Martin Fowler , afirma (sin juego de palabras) en el Capítulo 10 Diagramas de máquinas de estado (el énfasis es mío):

Un diagrama de estado se puede implementar de tres formas principales: conmutador anidado , patrón de estado y tablas de estado .

Usemos un ejemplo simplificado de los estados de la pantalla de un teléfono móvil:

Interruptor anidado

Fowler dio un ejemplo de código C #, pero lo adapté a mi ejemplo.

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;
    }
}

Patrón de estado

Aquí hay una implementación de mi ejemplo con el patrón GoF State:

Tablas de estado

Inspirándome en Fowler, aquí hay una tabla para mi ejemplo:

Estado de origen Estado de destino Acción de protección de eventos
-------------------------------------------------- ------------------------------------
Pantalla Apagado de la pantalla Apagado del botón Encendido del botón Pantalla baja Encendido bajo Mensaje  
ScreenOff ScreenOn pressButton! PowerLow
ScreenOn ScreenOff presione el botón
Pantalla apagada Enchufe de carga
Pantalla en pantalla Enchufe de carga Alimentación
Pantalla de carga Pantalla apagada desenchufar

Comparación

El interruptor anidado mantiene toda la lógica en un solo lugar, pero el código puede ser difícil de leer cuando hay muchos estados y transiciones. Posiblemente sea más seguro y más fácil de validar que los otros enfoques (sin polimorfismo ni interpretación).

La implementación del patrón de estado potencialmente distribuye la lógica en varias clases separadas, lo que puede hacer que entenderlo como un todo sea un problema. Por otro lado, las clases pequeñas son fáciles de entender por separado. El diseño es particularmente frágil si cambia el comportamiento agregando o quitando transiciones, ya que son métodos en la jerarquía y podría haber muchos cambios en el código. Si vive según el principio de diseño de las interfaces pequeñas, verá que este patrón no funciona tan bien. Sin embargo, si la máquina de estado es estable, estos cambios no serán necesarios.

El enfoque de tablas de estado requiere escribir algún tipo de intérprete para el contenido (esto podría ser más fácil si tiene una reflexión en el idioma que está utilizando), lo que podría ser mucho trabajo por adelantado. Como señala Fowler, si su tabla está separada de su código, podría modificar el comportamiento de su software sin volver a compilarlo. Sin embargo, esto tiene algunas implicaciones de seguridad; el software se está comportando según el contenido de un archivo externo.

Editar (no realmente para lenguaje C)

También hay un enfoque de interfaz fluida (también conocido como Lenguaje específico de dominio interno), que probablemente sea facilitado por lenguajes que tienen funciones de primera clase . La biblioteca Stateless existe y ese blog muestra un ejemplo simple con código. Se discute una implementación de Java (anterior a Java8) . También me mostraron un ejemplo de Python en GitHub .

También existe la cuadrícula lógica que se puede mantener más a medida que la máquina de estado se hace más grande

Para casos simples, puede cambiar su método de estilo. Lo que encontré que funciona bien en el pasado es lidiar con las transiciones también:

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
}

No sé nada sobre la biblioteca boost, pero este tipo de enfoque es muy simple, no requiere dependencias externas y es fácil de implementar.

switch () es una forma potente y estándar de implementar máquinas de estado en C, pero puede disminuir la capacidad de mantenimiento si tiene una gran cantidad de estados. Otro método común es utilizar punteros de función para almacenar el siguiente estado. Este simple ejemplo implementa un 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;
}

Encontré una implementación C realmente hábil de Moore FSM en el curso de edx.org Embedded Systems - Shape the World UTAustinX - UT.6.02x, capítulo 10, por Jonathan Valvano y 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];  
  }
}

Es posible que desee examinar el software generador de FSM libero . Desde un lenguaje de descripción de estado y / o un editor de diagramas de estado (Windows), puede generar código para C, C ++, Java y muchos otros ... además de buena documentación y diagramas. Fuente y binarios de iMatix

Este artículo es bueno para el patrón de estado (aunque es C ++, no específicamente C).

Si puede poner sus manos en el libro " Head First Design Patterns ", la explicación y el ejemplo son muy claros.

Uno de mis patrones favoritos es el patrón de diseño estatal. Responder o comportarse de manera diferente al mismo conjunto de entradas.
Uno de los problemas con el uso de declaraciones switch / case para máquinas de estado es que a medida que crea más estados, el switch / case se vuelve más difícil / difícil de leer / mantener, promueve el código espagueti desorganizado y cada vez es más difícil de cambiar sin romper algo. Encuentro que el uso de patrones de diseño me ayuda a organizar mejor mis datos, que es el objetivo de la abstracción. En lugar de diseñar su código de estado en torno al estado de donde proviene, en su lugar, estructure su código para que registre el estado cuando ingrese a un nuevo estado. De esa manera, efectivamente obtiene un registro de su estado anterior. Me gusta la respuesta de @ JoshPetit y he llevado su solución un paso más allá, tomada directamente del libro de 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 la mayoría de las máquinas estatales, esp. Máquinas de estados finitos, cada estado sabrá cuál debería ser su próximo estado y los criterios para la transición al siguiente estado. Para diseños de estado sueltos, este puede no ser el caso, de ahí la opción de exponer la API para estados de transición. Si desea más abstracción, cada controlador de estado puede separarse en su propio archivo, que son equivalentes a los controladores de estado concretos del libro GoF. Si su diseño es simple con solo unos pocos estados, entonces tanto stateCtxt.cy statehandlers.c pueden combinarse en un solo archivo para simplificar.

En mi experiencia, el uso de la declaración 'cambiar' es la forma estándar de manejar múltiples estados posibles. Aunque me sorprende que esté pasando un valor de transición al procesamiento por estado. Pensé que el objetivo de una máquina de estados era que cada estado realizaba una sola acción. Luego, la siguiente acción / entrada determina a qué nuevo estado hacer la transición. Por lo tanto, habría esperado que cada función de procesamiento de estado realizara inmediatamente lo que sea fijo para ingresar al estado y luego decidir si es necesaria la transición a otro estado.

Hay un libro titulado Practical Statecharts en C / C ++ . Sin embargo, es manera demasiado pesado para lo que necesitamos.

Para el compilador que lo admita __COUNTER__, puede usarlos para mashines de estado simples (pero 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;
     } 
  } 

La ventaja de usar en __COUNTER__lugar de números codificados de forma rígida es que puede agregar estados en medio de otros estados, sin tener que volver a numerarlo todo cada vez. Si el compilador no lo soporta __COUNTER__, de forma limitada se puede usar con precaución__LINE__

Puede usar un marco de máquina de estado UML minimalista en c. https://github.com/kiishor/UML-State-Machine-in-C

Es compatible con máquinas de estados finitos y jerárquicos. Tiene solo 3 API, 2 estructuras y 1 enumeración.

La máquina de estado está representada por state_machine_testructura. Es una estructura abstracta que se puede heredar para crear una máquina de estados.

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

El estado está representado por un puntero a state_t estructura en el marco.

Si el marco está configurado para una máquina de estados finitos, entonces state_tcontiene,

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;

El marco proporciona una API dispatch_eventpara enviar el evento a la máquina de estado y dos API para el cruce 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 obtener más detalles sobre cómo implementar una máquina de estado jerárquica, consulte el repositorio de GitHub.

ejemplos 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

En C ++, considere el patrón de estado .

Su pregunta es similar a "¿Existe un patrón típico de implementación de la base de datos"? La respuesta depende de lo que quiera lograr. Si desea implementar una máquina de estado determinista más grande, puede usar un modelo y un generador de máquina de estado. Se pueden ver ejemplos en www.StateSoft.org - SM Gallery. Janusz Dobrowolski

Boost tiene la biblioteca statechart. http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html

Sin embargo, no puedo hablar sobre su uso. No lo usé yo mismo (todavía)