Using GOTO for a FSM in C

2019-07-13 03:13发布

问题:

I am creating a finite state machine in C. I learned FSM from the hardware point of view (HDL language). So I'm used a switch with one case per state.

I also like to apply the Separation of Concerns concept when programing. I mean I'd like to get this flow:

  1. Calculate the next state depending on the current state and input flags
  2. Validate this next state (if the user request a transition that is not allowed)
  3. Process the next state when it is allowed

As a start I implemented 3 functions: static e_InternalFsmStates fsm_GetNextState(); static bool_t fsm_NextStateIsAllowed(e_InternalFsmStates nextState); static void fsm_ExecuteNewState(e_InternalFsmStates);

At the moment they all contain a big switch-case which is the same:

switch (FSM_currentState) {
case FSM_State1:
    [...]
    break;
case FSM_State2:
    [...]
    break;
default:
    [...]
    break;
}

Now that it works, I'd like to improve the code.

I know that in the 3 functions I'll execute the same branch of the switch. So I am thinking to use gotos in this way:

//
// Compute next state
//
switch (FSM_currentState) {
case FSM_State1:
    next_state = THE_NEXT_STATE
    goto VALIDATE_FSM_State1_NEXT_STATE;
case FSM_State2:
    next_state = THE_NEXT_STATE
    goto VALIDATE_FSM_State2_NEXT_STATE;
    [...]
default:
    [...]
    goto ERROR;
}

//
// Validate next state
//
VALIDATE_FSM_State1_NEXT_STATE:
    // Some code to Set stateIsValid to TRUE/FALSE;
    if (stateIsValid == TRUE)
        goto EXECUTE_STATE1;
    else
        goto ERROR;

VALIDATE_FSM_State2_NEXT_STATE:
    // Some code to Set stateIsValid to TRUE/FALSE;
    if (stateIsValid == TRUE)
        goto EXECUTE_STATE2;
    else
        goto ERROR;

//
// Execute next state
//
EXECUTE_STATE1:
    // Do what I need for state1
    goto END;

EXECUTE_STATE2:
    // Do what I need for state2
    goto END;

//
// Error
//
ERROR:
    // Error handling
    goto END;

END:
    return; // End of function

Of course, I could do the 3 parts (calculate, validate and process the next state) in a single switch case. But for code readability and code reviews, I feel like it will be easier to separate them.

Finally my question, is it dangerous to use GOTOs in this way? Would you have any advice when using FSM like that?

Thank you for your comments!


After reading the answers and comments below, here is what I am going to try:

e_FSM_InternalStates nextState = FSM_currentState;
bool_t isValidNextState;

//
// Compute and validate next state
//
switch (FSM_currentState) {
case FSM_State1:
    if (FSM_inputFlags.flag1 == TRUE)
    {
        nextState = FSM_State2;
    }
    [...]

    isValidNextState = fsm_validateState1Transition(nextState);

case FSM_State2:
    if (FSM_inputFlags.flag2 == TRUE)
    {
        nextState = FSM_State3;
    }
    [...]
    isValidNextState = fsm_validateState2Transition(nextState);
}


//
// If nextState is invalid go to Error
//
if (isValidNextState == FALSE) {
    nextState = FSM_StateError;
}


//
// Execute next state
//
switch (nextState) {
case FSM_State1:
    // Execute State1
    [...]

case FSM_State2:
    // Execute State1
    [...]

case FSM_StateError:
    // Execute Error
    [...]
}

FSM_currentState = nextState;

回答1:

While goto has its benefits in C, it should be used sparesly and with extreme caution. What you intend is no recommendable use-case.

Your code will be less maintainable and more confusing. switch/case is actually some kind of "calculated" goto (thats's why there are case labels).

You are basicaly thinking the wrong way. For a state-machine, you should first verify input, then calculate the next state, then the output. There are various ways to do so, but it is often a good idea to use two switches and - possibly - a single error-handling label or a error-flag:

bool error_flag = false;

while ( run_fsm ) {
    switch ( current_state ) {

        case STATE1:
             if ( input1 == 1 )
                 next_state = STATE2;
             ...
             else
                 goto error_handling;   // use goto 
                 error_flag = true;     // or the error-flag (often better)
             break;

        ...
    }

    if ( error_flag )
        break;

    switch ( next_state ) {

        case STATE1:
            output3 = 2;
            // if outputs depend on inputs, similar to the upper `switch`
            break;
        ...
    }

    current_state = next_state;
}

error_handling:
    ...

This way you are transitioning and verifying input at once. This makes senase, as you have to evaluate the inputs anyway to set the next state, so invalid input just falls of the tests naturally.

An alternative is to have an output_state and state variable instead of next_state and current_state. In the first switch you set output_state and state, the second is switch ( output_state ) ....

If the single cases become too long, you should use functions to determine the next_state and/or output_state/outputs. It depends very much on the FSM (number of inputs, outputs, states, complexity (e.g. one-hot vs. "encoded" - if you are family with HDL, you will know).

If you need more complex error-handling (e.g. recover) inside the loop, leave the loop as-is and add an outer loop, possibly change the error-flag to an error-code and add another switch for it in the outer loop. Depending on complexity, pack the inner loop into its own function, etc.

Sidenote: The compiler might very well optimize the structured approach (without goto) to the same/similar code as with the goto



回答2:

Whether it is "dangerous" is probably somewhat a matter of opinion. The usual reason people say to avoid GOTO is that it tends to lead to spaghetti code that's hard to follow. Is that an absolute rule? Probably not, but I think it's definitely fair to say that it is the trend. Secondarily, most programmers at this point are trained to believe that GOTO is bad, so, even if it's not in some case, you may run into some level of maintainability issue with other people coming into the project later.

How much risk you have in your case, probably depends on how big of a chunk of code you're going to have under those state labels and how sure you are that it won't change much. More code (or potential for large revisions), means more risk. In addition to just straight questions of readability, you'll have increased chances for assignments to variables interfering between cases or being dependent on the path you took to get to a certain state. Using functions helps with this (in many cases) by creating local scope for variables.

All in all, I would recommend avoiding the GOTO.



回答3:

My rule of thumb is to use GOTOs only to jump forward in the code, but never backwards. In the end this boils down to using GOTO only for exception handling, which otherwise doesn't exist in C.

In your particular case I would absolutely not recommend the use of GOTO.



回答4:

You don't really need to use switch-case, it will actually get optimized away by the compiler into machine code with a function pointer jump table. Switch-cases for state machines tend to be somewhat hard to read, especially the more complex ones.

The spaghetti-gotos are unacceptable and bad programming practice: there are a few valid uses of goto, this is not one of them.

Instead, consider to have a one-line state machine which looks like:

state = STATE_MACHINE[state]();

Here is an answer of mine (taken from the electrical engineering site, it pretty much applies universally) which is based on a function-pointer lookup table.

typedef enum
{
  STATE_S1,
  STATE_S2,
  ...
  STATE_N // the number of states in this state machine
} state_t;

typedef state_t (*state_func_t)(void);


state_t do_state_s1 (void);
state_t do_state_s2 (void);

static const state_func_t STATE_MACHINE [STATE_N] =
{
  &do_state_s1,
  &do_state_s2,
  ...
};


void main()
{
  state_t state = STATE_S1;

  while (1)
  {
    state = STATE_MACHINE[state]();
  }
}

state_t do_state_s1 (void)
{
  state_t result = STATE_S1;
  // stuff
  if (...) 
    result = STATE_S2;
  return result;
}

state_t do_state_s2 (void)
{
  state_t result = STATE_S2;
  // other stuff
  if (...) 
    result = STATE_S1;
  return result;
}

You can easily modify the function signatures to contain an error code as well, such as for example:

typedef err_t (*state_func_t)(state_t*); 

with functions as

err_t do_state_s1 (state_t* state); 

in which case the caller would end up as:

error = STATE_MACHINE[state](&state);

if(error != NO_ERROR)
{
  // handle errors here
}      

Leave all error handling to the caller as show in the above example.