.. role:: fsmlang(code)
	:language: fsmlang

=======================
The Simple Communicator
=======================

As an example, consider a simple communications protocol which specifies that an acknowledgement must be received
for each message before another may be sent. The sender of messages in such a protocol must have at least two
states: In the first state, which will be called IDLE, the sender has sent no message. In the second, which will be
called AWAITING_ACK, the sender has sent a message and is awaiting an acknowledgement. The events which this
automaton will see are SEND_MESSAGE, the request by a client entity for a message to be sent, and ACK, the receipt
of the acknowledgment from the peer automaton.

The valid actions, then, are to send a message if one is requested, and the automaton is in the IDLE state,and to
simply return to the IDLE state if an ACK is received while in the AWAITING_ACK state. Sending a message requires a
transition to the AWAITING_ACK state. The receipt of an acknowledgement while in the IDLE state represents a
protocol error which may be safely ignored. A request to send a message while in the AWAITING_ACK state, however,
must result in the message being queued for later transmission.

----------
FSM Source
----------

Using FSMLang, this machine can be described this way:

.. code-block:: fsmlang

	/**
	   This machine manages communications using a "stop and wait" protocol.
	   Only one message is allowed to be outstanding.
	*/
	machine simpleCommunicator
	{
	
	   state IDLE
	         , AWAITING_ACK
	         ;
	
	   event SEND_MESSAGE
	         , ACK
	         ;
	
	   /**
	      Since we're idle, we can simply send the message.  Transitioning
	      to the AWAITING_ACK state ensures that any other messages
	      we're asked to send will be queued.
	   */
	   action sendMessage[SEND_MESSAGE,IDLE] transition AWAITING_ACK;
	
	   /**
	     Since we're busy, we must queue the message for later
	     sending.  The queue will be checked when the ACK
	     is received.
	   */
	   action queueMessage[SEND_MESSAGE,AWAITING_ACK];
	
	   /**
	      We've received our ACK for the previous message.  It is 
	      time to check for any others.
	   */
	   action checkQueue[ACK,AWAITING_ACK] transition IDLE;
	
	   /* these lines are informational; they affect the html output,
	      but do not affect any code generated.
	   */
	
	   /** queueMessage adds a message to the queue */
	   queueMessage returns noEvent;
	
	   /** sendMessage sends a message from the queue.  The
	       message is expected to be there, since
	       checkQueue will have been previously called.
	   */
	   sendMessage  returns noEvent;
	
	   /** checkQueue only checks; it does not dequeue; that
	       is done by sendMessage.
	
	       Return SEND_MESSAGE when the queue is not empty.
	   */
	   checkQueue   returns SEND_MESSAGE, noEvent;
	
	}

The layout of the FSM source is expected to feel familar to those familiar with C.  Moreover, it is intended to mimic the textual description
of the machine.

FSMLang can create three different layouts for the event, state, action, and transition data.  The default (or ``-tc`` option) is to simply
build an action array dimensioned by event and state having member structures to indicate the action and transitions to take when that
combination of event and state are encountered.  The second approach (``-ts``) creates an array of state functions, each containing a switch
statement for the event being handled.  The third approach (``-te``) reverses the second, creating an array of event functions, each containing
a switch for the current state.  As usual, the trade-offs between these three approaches involve size and speed.

We'll look at the code generated by each of the three, starting with the parts that are common.

-------------
Common Output
-------------

All variants produce the same files, namely:

Headers:

* simpleCommunicator.h
* simpleCommunicator_events.h 
* simpleCommunicator_priv.h

Source:

* simpleCommunicator.c 

*simpleCommunicator.h* is intended to be used by client code to invoke the state machine. Thus, it contains the single point-of-entry function.

.. code-block:: c

	void run_simpleCommunicator(SIMPLE_COMMUNICATOR_EVENT);

It also supplies convenience macros by which client code
can refer to machine events by their short names:

.. code-block:: c

	#undef THIS
	#define THIS(A) simpleCommunicator_##A
	#endif

It also includes *simpleCommunicator_events.h*, which contains the event enumeration:

.. code-block:: c

	typedef enum SIMPLE_COMMUNICATOR_EVENT {
	    simpleCommunicator_SEND_MESSAGE
	   , simpleCommunicator_ACK
	   , simpleCommunicator_noEvent
	   , simpleCommunicator_numEvents
	   , simpleCommunicator_numAllEvents = simpleCommunicator_numEvents
	}  SIMPLE_COMMUNICATOR_EVENT;

Taken together, cliend code intending to have the *simpleCommunicator* send a message need only write:

.. code-block:: c

	run_simpleCommunicator(THIS(SEND_MESSAGE));

And, the code which knows how to receive the ACK from the peer, can simply write:

.. code-block:: c

	run_simpleCommunicator(THIS(ACK));

*simpleCommunicator_priv.h* is intended to be included by files implementing the machine's action and other user defined functions. It is also
included by *simpleCommunicator.c*  Here is the common material:

.. code-block:: c

	#include "simpleCommunicator.h"
	
	#ifdef SIMPLE_COMMUNICATOR_DEBUG
	#include <stdio.h>
	#include <stdlib.h>
	#endif
	
	
	#ifdef SIMPLE_COMMUNICATOR_DEBUG
	extern char *SIMPLE_COMMUNICATOR_EVENT_NAMES[];
	extern char *SIMPLE_COMMUNICATOR_STATE_NAMES[];
	#endif
	
	typedef enum {
	   simpleCommunicator_IDLE
	   , simpleCommunicator_AWAITING_ACK
	   , simpleCommunicator_numStates
	}  SIMPLE_COMMUNICATOR_STATE;
	
	typedef struct _simpleCommunicator_struct_ SIMPLE_COMMUNICATOR;
	#undef FSM_TYPE_PTR
	#define FSM_TYPE_PTR pSIMPLE_COMMUNICATOR
	extern SIMPLE_COMMUNICATOR simpleCommunicator;
	
	typedef SIMPLE_COMMUNICATOR_EVENT (*SIMPLE_COMMUNICATOR_ACTION_FN)(FSM_TYPE_PTR);

	typedef void (*SIMPLE_COMMUNICATOR_FSM)(FSM_TYPE_PTR,SIMPLE_COMMUNICATOR_EVENT);

	void simpleCommunicatorFSM(FSM_TYPE_PTR,SIMPLE_COMMUNICATOR_EVENT);

	ACTION_RETURN_TYPE simpleCommunicator_sendMessage(FSM_TYPE_PTR);
	ACTION_RETURN_TYPE simpleCommunicator_queueMessage(FSM_TYPE_PTR);
	ACTION_RETURN_TYPE simpleCommunicator_checkQueue(FSM_TYPE_PTR);
	ACTION_RETURN_TYPE simpleCommunicator_noAction(FSM_TYPE_PTR);

FSMLang provides the ability to debug the operation of the state machine through the use of several macros and name lists, made available by
defining (in this case, for example), ``SIMPLE_COMMUNICATOR_DEBUG`` during compilation.

The source file diverges quickly between the three variants.  Debugging support, including the generation of weak versions of user functions
comprise most of the common material.

.. code-block:: c

	#ifndef DBG_PRINTF
	#define DBG_PRINTF(...)
	#endif

	SIMPLE_COMMUNICATOR_EVENT __attribute__((weak)) UFMN(sendMessage)(FSM_TYPE_PTR pfsm)
	{
	   DBG_PRINTF("weak: %s", __func__);
	   (void) pfsm;
	   return THIS(noEvent);
	}
	
	SIMPLE_COMMUNICATOR_EVENT __attribute__((weak)) UFMN(queueMessage)(FSM_TYPE_PTR pfsm)
	{
	   DBG_PRINTF("weak: %s", __func__);
	   (void) pfsm;
	   return THIS(noEvent);
	}
	
	SIMPLE_COMMUNICATOR_EVENT __attribute__((weak)) UFMN(checkQueue)(FSM_TYPE_PTR pfsm)
	{
	   DBG_PRINTF("weak: %s", __func__);
	   (void) pfsm;
	   return THIS(noEvent);
	}
	
	SIMPLE_COMMUNICATOR_EVENT __attribute__((weak)) UFMN(noAction)(FSM_TYPE_PTR pfsm)
	{
	   DBG_PRINTF("weak: %s", __func__);
	   (void) pfsm;
	   return THIS(noEvent);
	}
	
	
	#ifdef SIMPLE_COMMUNICATOR_DEBUG
	char *SIMPLE_COMMUNICATOR_EVENT_NAMES[] = {
	    "simpleCommunicator_SEND_MESSAGE"
	   ,"simpleCommunicator_ACK"
	   , "simpleCommunicator_noEvent"
	   , "simpleCommunicator_numEvents"
	};
	
	char *SIMPLE_COMMUNICATOR_STATE_NAMES[] = {
	    "simpleCommunicator_IDLE"
	   ,"simpleCommunicator_AWAITING_ACK"
	};
	
	#endif

.. note::

	For action array output, it may be necessary to inhibit the generation of the weak functions (``--generate-weak-fns=false``).  Some
	linkers get confused by the presence of these weak definitions in the same file as the action array is defined.

The final bit of commonality is the looping nature of the main FSM function, seen because this machine has actions which return events:

.. code-block:: c

	void simpleCommunicatorFSM(pSIMPLE_COMMUNICATOR pfsm, SIMPLE_COMMUNICATOR_EVENT event)
	{
	   SIMPLE_COMMUNICATOR_EVENT new_e;
	   SIMPLE_COMMUNICATOR_EVENT e = event;
	
	   while (e != THIS(noEvent)) {
	
	       /* e = (somehow call an action function to get a new event) */;
	
	   }
	}

With that, let's look at how the three variants differ.

-------------------
Action Array Output
-------------------

The action array first appears in the private header as a type definition for the structure to hold the action function pointer and the
desired state transition.  This is then used in the FSM structure type definition to declare the action array, dimensioned by the number
of events and states.

.. code-block:: c

	typedef enum {
	   simpleCommunicator_IDLE
	   , simpleCommunicator_AWAITING_ACK
	   , simpleCommunicator_numStates
	}  SIMPLE_COMMUNICATOR_STATE;

	typedef void (*SIMPLE_COMMUNICATOR_FSM)(FSM_TYPE_PTR,SIMPLE_COMMUNICATOR_EVENT);
	
	typedef struct _simpleCommunicator_action_trans_struct_ {
	  SIMPLE_COMMUNICATOR_ACTION_FN      action;
	  SIMPLE_COMMUNICATOR_STATE          transition;
	} SIMPLE_COMMUNICATOR_ACTION_TRANS, *pSIMPLE_COMMUNICATOR_ACTION_TRANS;
	
	struct _simpleCommunicator_struct_ {
	   SIMPLE_COMMUNICATOR_STATE                   state;
	   SIMPLE_COMMUNICATOR_EVENT                   event;
	   SIMPLE_COMMUNICATOR_ACTION_TRANS   const   (*actionArray)[THIS(numEvents)][simpleCommunicator_numStates];
	   SIMPLE_COMMUNICATOR_FSM                     fsm;
	};

The source file, *simpleCommunicator.c*, declares the array:

.. code-block:: c

	static const SIMPLE_COMMUNICATOR_ACTION_TRANS simpleCommunicator_action_array[THIS(numEvents)][simpleCommunicator_numStates] =
	{
	   {
	      /* -- SEND_MESSAGE -- */
	
	      /* -- IDLE -- */             {UFMN(sendMessage), simpleCommunicator_AWAITING_ACK}
	      /* -- AWAITING_ACK -- */   , {UFMN(queueMessage),simpleCommunicator_AWAITING_ACK}
	   },
	   {
	      /* -- ACK -- */
	
	      /* -- IDLE -- */             {UFMN(noAction),  simpleCommunicator_IDLE}
	      /* -- AWAITING_ACK -- */   , {UFMN(checkQueue),simpleCommunicator_IDLE}
	   },
	};

In practice, this array can become quite large; the benefit, of course, being speed of action function lookup and execution, as seen in
the main FSM function:

.. code-block:: c

	void simpleCommunicatorFSM(pSIMPLE_COMMUNICATOR pfsm, SIMPLE_COMMUNICATOR_EVENT event)
	{
	   SIMPLE_COMMUNICATOR_EVENT new_e;
	   SIMPLE_COMMUNICATOR_EVENT e = event;

	   while (e != THIS(noEvent)) {
	
	#ifdef SIMPLE_COMMUNICATOR_DEBUG
	      if (EVENT_IS_NOT_EXCLUDED_FROM_LOG(e))
	      {
	         DBG_PRINTF("event: %s; state: %s"
	                    ,SIMPLE_COMMUNICATOR_EVENT_NAMES[e]
	                    ,SIMPLE_COMMUNICATOR_STATE_NAMES[pfsm->state]
	                   );
	      }
	#endif
	
	      /* This is read-only data to facilitate error reporting in action functions */
	      pfsm->event = e;
	
	      new_e = ((* (*pfsm->actionArray)[e][pfsm->state].action)(pfsm));
	
	      pfsm->state = (*pfsm->actionArray)[e][pfsm->state].transition;
	
	      e = new_e;
	
	   } 
	
	}

--------------------
State Function Array
--------------------

The state function array also first appears in the private header:

.. code-block:: c

	typedef ACTION_RETURN_TYPE (*SIMPLE_COMMUNICATOR_STATE_FN)(pSIMPLE_COMMUNICATOR,SIMPLE_COMMUNICATOR_EVENT);
	
	static const SIMPLE_COMMUNICATOR_STATE_FN simpleCommunicator_state_fn_array[simpleCommunicator_numStates];
	
	struct _simpleCommunicator_struct_ {
	   SIMPLE_COMMUNICATOR_STATE              state;
	   SIMPLE_COMMUNICATOR_EVENT              event;
	   SIMPLE_COMMUNICATOR_STATE_FN   const (*statesArray)[simpleCommunicator_numStates];
	   SIMPLE_COMMUNICATOR_FSM                fsm;
	};
	
The state functions need the event the machine is currently handling in addition to a pointer to the machine structure.

The array and main FSM function are again defined in the source file:

.. code-block:: c

	static SIMPLE_COMMUNICATOR_EVENT IDLE_stateFn(pSIMPLE_COMMUNICATOR,SIMPLE_COMMUNICATOR_EVENT);
	static SIMPLE_COMMUNICATOR_EVENT AWAITING_ACK_stateFn(pSIMPLE_COMMUNICATOR,SIMPLE_COMMUNICATOR_EVENT);
	static const SIMPLE_COMMUNICATOR_STATE_FN simpleCommunicator_state_fn_array[simpleCommunicator_numStates] = 
	{
	     IDLE_stateFn
	   , AWAITING_ACK_stateFn
	};
	
	void simpleCommunicatorFSM(pSIMPLE_COMMUNICATOR pfsm, SIMPLE_COMMUNICATOR_EVENT event)
	{
	   SIMPLE_COMMUNICATOR_EVENT e = event;
	
	   while (e != simpleCommunicator_noEvent) {
	
	#ifdef SIMPLE_COMMUNICATOR_DEBUG
	      if (EVENT_IS_NOT_EXCLUDED_FROM_LOG(e))
	      {
	         DBG_PRINTF("event: %s; state: %s"
	                    ,SIMPLE_COMMUNICATOR_EVENT_NAMES[e]
	                    ,SIMPLE_COMMUNICATOR_STATE_NAMES[pfsm->state]
	                   );
	      }
	#endif
	
	      /* This is read-only data to facilitate error reporting in action functions */
	      pfsm->event = e;
	
	      e = ((* (*pfsm->statesArray)[pfsm->state])(pfsm,e));
	   }
	
	}
	
While the lookup into the state table is quick, the state function retrieved must first be called before the action function can finally be
located and called.  Some efficiency is gained, however, in the assignment of any new state, since this can be done within the state functions.

.. code-block:: c
 
	static SIMPLE_COMMUNICATOR_EVENT IDLE_stateFn(pSIMPLE_COMMUNICATOR pfsm,SIMPLE_COMMUNICATOR_EVENT e)
	{
	   SIMPLE_COMMUNICATOR_EVENT retVal = THIS(noEvent);
	
	   switch(e)
	   {
	   case THIS(SEND_MESSAGE):
	      retVal = UFMN(sendMessage)(pfsm);
	      pfsm->state = simpleCommunicator_AWAITING_ACK;
	      break;
	   default:
	      DBG_PRINTF("simpleCommunicator_noAction");
	      break;
	   }
	
	   return retVal;
	}
	
	static SIMPLE_COMMUNICATOR_EVENT AWAITING_ACK_stateFn(pSIMPLE_COMMUNICATOR pfsm,SIMPLE_COMMUNICATOR_EVENT e)
	{
	   SIMPLE_COMMUNICATOR_EVENT retVal = THIS(noEvent);
	
	   switch(e)
	   {
	   case THIS(SEND_MESSAGE):
	      retVal = UFMN(queueMessage)(pfsm);
	      break;
	   case THIS(ACK):
	      retVal = UFMN(checkQueue)(pfsm);
	      pfsm->state = simpleCommunicator_IDLE;
	      break;
	   default:
	      DBG_PRINTF("simpleCommunicator_noAction");
	      break;
	   }
	
	   return retVal;
	}

--------------------
Event Function Array
--------------------

The final variant offers the chance of a bit of efficiency when an event is handled identically in all states, and has no associated transition.
In this case, the action function itself can be placed in the array of event handlers.  Otherwise, of course, an "event function" must be
created, which will then result in a double lookup, as is the case with the state function implementation.

To see the insertion of an action function into the event handler array, we add an additional event and specify an
action for it:

.. code-block:: fsmlang

	event NEVER_SEEN;

	action neverExecuted[NEVER_SEEN, (IDLE, AWAITING_ACK)];

Notice the use of the state vector (event vectors are also allowed) to indicate that the action should be taken when
the event occurs in any of the states in the vector.  When both event and state vectors are used, the action is
placed in the action matrix cells representing the cross-product of the two vectors.

The private header:

.. code-block:: c

	#define simpleCommunicator_numMachineEvents 2
	struct _simpleCommunicator_struct_ {
	   SIMPLE_COMMUNICATOR_STATE         state;
	   SIMPLE_COMMUNICATOR_EVENT         event;
	   SIMPLE_COMMUNICATOR_ACTION_FN const (*eventsArray)[simpleCommunicator_numMachineEvents];
	   SIMPLE_COMMUNICATOR_FSM           fsm;
	};

No new function typedef is needed for the event handlers, as the event handler must take the same input as an action function. The macro giving
the number of machine events is neccessary because the event enumeration counts the *noEvent* entry.  That "event" is never handled.

The source:

.. code-block:: c

	static ACTION_RETURN_TYPE simpleCommunicator_handle_SEND_MESSAGE(FSM_TYPE_PTR);
	static ACTION_RETURN_TYPE simpleCommunicator_handle_ACK(FSM_TYPE_PTR);
	
	static const SIMPLE_COMMUNICATOR_ACTION_FN simpleCommunicator_event_fn_array[simpleCommunicator_numMachineEvents] =
	{
	   simpleCommunicator_handle_SEND_MESSAGE
	   , UFMN(neverExecuted)
	   , simpleCommunicator_handle_ACK
	};
	
	void simpleCommunicatorFSM(pSIMPLE_COMMUNICATOR pfsm, SIMPLE_COMMUNICATOR_EVENT event)
	{
	   SIMPLE_COMMUNICATOR_EVENT e = event;
	
	   while (e != simpleCommunicator_noEvent) {
	
	#ifdef SIMPLE_COMMUNICATOR_DEBUG
	      if (EVENT_IS_NOT_EXCLUDED_FROM_LOG(e))
	      {
	         DBG_PRINTF("event: %s; state: %s"
	                    ,SIMPLE_COMMUNICATOR_EVENT_NAMES[e]
	                    ,SIMPLE_COMMUNICATOR_STATE_NAMES[pfsm->state]
	                   );
	      }
	#endif
	
	      /* This is read-only data to facilitate error reporting in action functions */
	      pfsm->event = e;
	
	      e = ((* (*pfsm->eventsArray)[e])(pfsm));
	
	   }
	
	}
	
	static ACTION_RETURN_TYPE simpleCommunicator_handle_SEND_MESSAGE(FSM_TYPE_PTR pfsm)
	{
	   ACTION_RETURN_TYPE event = THIS(noEvent);
	
	   switch (pfsm->state)
	   {
	      case STATE(IDLE):
	         event = UFMN(sendMessage)(pfsm);
	         pfsm->state = STATE(AWAITING_ACK);
	         break;
	      case STATE(AWAITING_ACK):
	         event = UFMN(queueMessage)(pfsm);
	         break;
	   }
	
	   return event;
	}
	
	static ACTION_RETURN_TYPE simpleCommunicator_handle_ACK(FSM_TYPE_PTR pfsm)
	{
	   ACTION_RETURN_TYPE event = THIS(noEvent);
	
	   switch (pfsm->state)
	   {
	      case STATE(AWAITING_ACK):
	         event = UFMN(checkQueue)(pfsm);
	         pfsm->state = STATE(IDLE);
	         break;
	      default:
	         DBG_PRINTF("simpleCommunicator_noAction");
	         break;
	   }
	
	   return event;
	}

As with the state functions, the generated event functions handle any needed transition.

-------
Summary
-------

Though implemented differently, the three variants produce code which exhibits the same behavior, given the same event input.  The variants
are made available to accomodate different requirements in the size/speed tradeoff.  As observed earlier, the Action Array is the quickest
of the three, but when the machine is "sparse," having a low percentage of the event-state cells filled, the array is mostly empty, so size
considerations would point to either a state or event based array of handlers.  On the other hand, when the machine is not sparse, the
size differences are not as great, so the speed of the array may be attractive.