Lab 2: FSM Implementation

Preliminaries

Set up a bare repository on stu.cs.jmu.edu based on the instructions in the CS 361 Submission Procedures, using the name lab2-cmd.git.

The FSM that you will implement is a model of states that a process goes through during its life cycle:

This FSM can be used to parse a command line, such as the following (recall that the $ is used to denote the command line and is not parsed):

$ ls -l data

From the initial state, the TOKEN event is fired when the "ls" string is encountered, moving the FSM to the Command state after executing the start_command() effect. Two more TOKEN events are fired for "-l" and "data". Both execute the append() effect and move the FSM to the Arguments state.

After processing all arguments, the command line should either encounter a NEWLINE or PIPE event. In a normal command line, the enter or return key would produce the '\n' character to cause a NEWLINE. In this lab, we will use the string "NL" to simulate the new line. The vertical bar '|' character (which is often called the "pipe" character) fires the PIPE event. Pipes are used to chain commands together, so the output of the first command becomes the input to a second.

Implementing states and transitions

Completing the following requirements will satisfy the minimum required functionality:

• Edit the _transition table defined in model.c to match the model above. Create an FSM instance in cmdline_init() and initialize its initial state and transition function pointer appropriately. For other fields, it is good practice to initialize values to 0 or NULL if you are unsure what initial value is needed. (Note that if you use calloc() to create the instance, all fields are automatically initialized to 0.)
• Create a helper function that fsm->transition will point to. This function will perform the transition lookup, returning the next state after the transition. The function parameters must match the transition declaration in model.h. Unlike the book's implementation, your version here must not return -1 on invalid transitions. Simply ignore them by returning NST. (Note that you don't even need to check for this if you just return the values in the transition table.)
• Perform robust error handling for invalid events and FSM states. Specifically, use an assert() to throw an error if the FSM is in an invalid state (anything greater than or equal to NST) or the event is invalid (greater than or equal to NIL.
• Complete the implementation of handle_event() in model.c. Again, check for errors (such as ensuring that the passed fsm parameter is never NULL). Change state only if the table indicates that the next state is valid (something other than NST).

When checking for potential errors, we can either use assert() or return early in an if statement. The former is preferred when the error should never occur and it isn't clear how to recover.

At this point, you should be passing all public unit tests (but not the private ones). If not, you should correct your implementation up to this point.

• Now move on to building the effects table, similar to the transition table. Note that the transition table is a 2-d array of state_t values, so we use NST to indicate there is no transition. The effects table is a 2-d array of action_t function pointers. If there is no valid transition, or there is a transition but it has no associated effect, the entry should be NULL. Update the transition helper function to perform the effect table lookup similar to the lookup for transitions. Note that the effect will be returned through the call-by-reference parameter.
• Update handle_event() so that it performs the effect if one was found by the transition lookup.
• At this point, you should now fail a public test case that is testing the execution of the code in effects.c (this code wasn't called before). Fix this by implementing the effects code functions:

  start_command()

  This will be called when the token (described above) is a command, such as "ls". This function will need to copy the token into the command field of the fsm_t instance and start to set up the args and nargs fields. At this point, nargs will be 1 (because we've only encountered one argument). For args, you'll need to dynamically allocate an array to hold all the argument strings and store the current token as args[0]. (Notice there is a MAX_ARGUMENTS constant you can use.)

  append()

  In the example above, this will be called when the token is an additional argument, such as "-l" or "data". Store the token and increment nargs.

  execute()

  Called on the NEWLINE event (the "NL" token). This prints out the arguments as a string. For the example above, the string would be "{ ls, -l, data, (null) }". You also need to free the args array.

Ensure that your code is passing all unit tests at this point. You'll now implement the features to finish the program, producing the correct output along the way.

• As in Lab 1, you will need to correct the expected output in some of the test cases. Make sure to do this before proceeding to the implementation.
• Update the main.c to loop through command-line arguments. Note that the program is simulating a command-line parser, so your main() function will receive the full command-line string as a single argument (argv[1]). You will tokenize this this string, splitting at the spaces, and pass these tokens to the FSM. Specifically, you will use lookup() that will give you the appropriate event, store the token in the FSM, then call handle_event().