Finite state machines/automatons (FSM) are used to control various parts of the robot. More...

Classes
struct	fsm_event
	Type for FSM events. More...
struct	robo_fsm
	Structure describing FSM. More...
Defines
#define	FSM_SIGNAL(fsm_id, event, data)
	Sends an event to another FSM, which may run in another thread.
#define	DBG_PRINT_EVENT(msg) printf("fsm %s %s %s: %s\n", fsm->debug_name, fsm->state_name, fsm_event_str(fsm->events[fsm->ev_head]), msg)
	Prints current event in a human readable form.
#define	FSM_STATE(name) error_FSM_XXX_not_defined
	Defines a state function for finite state machine.
#define	FSM_STATE_DECL(name) error_FSM_XXX_not_defined
	Declares a prototype of state function defined later.
#define	FSM_STATE_FULL_DECL(fsm_name, name) int __fsm_func_name(fsm_name, name,)(struct robo_fsm *fsm)
	Declares a prototype of state function of given FSM.
#define	FSM_TIMER(ms)
	Sets FSM's one-shot timer.
#define	FSM_TIMER_STOP() __fsm_timer_stop(fsm)
	Stops the timer.
#define	FSM_EVENT ((__FSM_EVENT_ENUM)(fsm->events[fsm->ev_head].id))
	Value of current event in state functions.
#define	FSM_EVENT_PTR (fsm->events[fsm->ev_head].data)
	Value of the pointer sent together with the event.
#define	FSM_EVENT_INT ((long int)(fsm->events[fsm->ev_head].data))
	Value of the integer data sent together with the event.
#define	FSM_TRANSITION(next) error_FSM_XXX_not_defined
	Sets current state to `next`.
#define	SUBFSM_TRANSITION(substate, data) error_FSM_XXX_not_defined
	Invoke state transition to sub-FSM.
#define	SUBFSM_RET(data)
	Return from sub-FSM.
Typedefs
typedef struct fsm_event	fsm_event
	Type for FSM events.
typedef int(*	robo_fsm_state_t )(struct robo_fsm *fsm)
	Event handler function for FSM.
Enumerations
enum	fsm_common_events { __COMMON_EV_ENTRY = 1, __COMMON_EV_EXIT, __COMMON_EV_RETURN, __COMMON_EV_TIMER }
	FSM events. More...
Functions
void	fsm_init (struct robo_fsm fsm, char debug_name, struct fsm_main_loop *loop)
	FSM initialization.
int	fsm_start (struct fsm_main_loop loop, pthread_attr_t attr)
	Starts previously initialized FSM main loop in a separate thread.
void	fsm_exit (struct robo_fsm *fsm)
	Signals FSM to exit.
void	fsm_destroy (struct robo_fsm *fsm)
	Deallocates all resources allocated by fsm_init().
const char *	fsm_event_str (fsm_event ev)
	Returns string with the name of event submitted as parameter.

Detailed Description

Finite state machines/automatons (FSM) are used to control various parts of the robot.

Content:

Introduction

FSMs are used to write applications that need to react on events. In the simples cases it is sufficient to write such applications only by combinations of switch and if statements. In other cases when the number of events is higher than a small number and the response to events differs depending on many conditions, such approach is usually error prone, since the code becomes complicated. This library provides a framework which makes programming such applications more easy.

The fundamental entity in this library is FSM. Every FSM is defined by structure robo_fsm and a set of state functions. The state functions are executed as a response to some events. The events can be generated internally (see fsm_common_events), by another FSM or by some other piece of code. There is exactly one "current" state function at a given time. The goal of the current state functions is to react to events. The reaction to an event can be represented by an arbitrary piece of code that does something useful. It is also possible to change the current state (function) of FSM (so called state transition). Having several state functions, it is possible to react differently on the same events depending on what is the current state.

Every FSM can be executed either in its dedicated threads or together with other FSMs in a single thread. Which way is better for your application depends on your needs. If the code in state functions may take long time to execute and you need to react quickly to some events, use the threaded FSMs and assign higher priority to threads with real-time requirements and low priority to non-real-time threads with long execution times.

On the other hand, having all FSMs running in a single thread may simplify your application, because you do not have to deal with concurrent execution. The price for this is, that response time to an critical event may be too high.

It is also possible to have something in between the above two approaches. You can have, for instance, real-time FSMs running in their own high-priority threads and non-real-time FSMs, sharing a single low-priority thread.

State Functions

The state function is a function taking a pointer to FSM structure as an argument and returning an integer value. To make declaration of state function easier, there is a macro FSM_STATE(). This macro declares the state functions and also adds some code to conditionally print debugging messages. Thanks to this macro, programmer can concentrate on the real programming task and the complexity of declaration is hidden.

The usual structure of a state function is one big switch statement. The switch condition is the FSM_EVENT macro, whose value is the identifier of the event (see section Events) to be handled. In the handling code you can execute whatever you want. If there is some data associated with the event, it can be retrieved by FSM_EVENT_PTR or FSM_EVENT_INT. Additionally, FSM infrastructure provides some useful functions and macros. To work with time, you can use FSM_TIMER(). To execute transition to another state, use FSM_TRANSITION() or SUBFSM_TRANSITION() (see Sub-Automatons). To send an event to another FSM, use FSM_SIGNAL().

An example state function, whose only function is to wait 1 second before entering another_state is shown here:

FSM_STATE(my_state) {
  switch (FSM_EVENT) {
    case EV_ENTRY:
      FSM_TIMER(1000);
      break;
    case EV_TIMER:
      FSM_TRANSITION(another_state);
      break;
  }
}

For the above to work, it is important to declare the macro FSM_<id> before including header with event definition and fsm.h. See the note in Events section. This means, that state functions for different FSMs have to be declared in separate files.

Events

An event is identified by an event identifier. This is a string usually starting with EV_ prefix. Some data can be associated with events. This data can be a pointer or integer typecasted to pointer.

Every FSM can handle so called common events (e.g. EV_ENTRY, see fsm_common_events) and also some additional events specific to the FSM. Those additional events are declared only for a given FSM and can be sent to that FSM from another place by the FSM_SIGNAL() macro. To avid programming errors we have three requirements for working with events:

It is not possible to send an event to FSM, which didn't declare it. This situation should produce compile-time error.
In a state function, an attempt to handle an event declared for another FSM should also produce compile-time error.
If some event, which can be handled by the FSM, is omitted in the switch command, we want to be warned.

These requirements are hard to achieve in plain C. Therefore, additional events for FSMs are declared as a data structure in Python and there is a Python script eventgen.py, which converts this definition to .h a .c files.

The event definition is a Python dictionary (associative array) called events. Keys to this dictionary are the lowercase identifiers of FSM. The value is another dictionary, which defines the events for that FSM. The key is the event identifier and value is a comment. In the example below, event for two FSMs called "tested" and "tester" are defined. The "tested" FSM can handle additional events EV_PING and EV_OTHER and "tester" FSM handles "EV_PONG".

events = {
    "tested" : {
        "EV_PING" : "Description of the PING event",
        "EV_OTHER" : "Other event"
    },
    "tester" : {
        "EV_PONG" : "Description of the PONG event"
    },
}

The script, which generates .c and .h source code is called eventgen.py. In .h, there is one enum for each FSM with all events this FSM can handle. The members of enums are not directly event identifiers, but some internal identifiers starting with double underscore (__). You should never use these identifiers directly in your application. Then, there are macros, which translates the event identifiers to internal event identifiers. Thanks to this, the above requirements 1. and 2. are fulfilled. Requirement no. 3 is also fulfilled because recent versions of GCC warns if some enum member is not handled in switch statement (unless you use default statement).

Note:

You have to always include the generated header file with events before fsm.h. If you do not do so, an error is generated.

In the source, where you define your state function, you have to define macro FSM_<id>, where <id> is uppercase identifier of FSM as defined in event definition. If you do not do so, you get a compilation error on definition of state function. GCC generates this error message:

error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘FSM_XXX_not_defined’

Usage

To use FSMs provided by this library in your application, you need to

define additional event for your automatons (see section Events),
define state functions for your automatons (see section State Functions) and
start execution of the automatons (every FSM executes in its own thread).

Definition of state functions usually starts with lines like this:

#define FSM_SOME_NAME // define which FSM state functions are to be declared here
#include "events.h"   // include definition of additional events (generated from events.py)
#include <fsm.h>

FSM_STATE(test_state1) {
        ...
}

Initialization of an automaton looks like:

struct robo_fsm fsm;
struct fsm_main_loop loop;
fsm_main_loop_init(&loop);
fsm_init(&fsm, "id_for_debug_massages", &loop);
fsm.state = &fsm_state_test_state1;       // Initial state of the automaton

To start the FSM in its own thread do:

if (fsm_start(&loop, NULL) != 0) {
        perror("fsm_start");
        exit(1);
}

To start it in the current thread do:

fsm_main_loop(&loop);

Sub-Automatons

Sometimes, it may be useful to enter a state of sub-automaton and return back to current state after this sub-automaton finishes its task. You can enter the sub-automaton state by calling SUBFSM_TRANSITION(). When the sub-automaton is done, call from some of its state functions SUBFSM_RET(). Then the original state function will be called with EV_RETURN.

Sub-automaton calling can be nested up to the level of 10.

Define Documentation

#define DBG_PRINT_EVENT ( msg ) printf("fsm %s %s %s: %s\n", fsm->debug_name, fsm->state_name, fsm_event_str(fsm->events[fsm->ev_head]), msg)

Prints current event in a human readable form.

#define FSM_EVENT ((__FSM_EVENT_ENUM)(fsm->events[fsm->ev_head].id))

Value of current event in state functions.

#define FSM_EVENT_INT ((long int)(fsm->events[fsm->ev_head].data))

Value of the integer data sent together with the event.

#define FSM_EVENT_PTR (fsm->events[fsm->ev_head].data)

Value of the pointer sent together with the event.

#define FSM_SIGNAL	(	fsm_id,
		event,
		data
	)

Value:

do {                                                              \
                fsm_event e = {__##fsm_id##_##event, data};               \
                __fsm_signal(FSM_GET_BY_ID(fsm_id), e, true);             \
        } while(0)

Sends an event to another FSM, which may run in another thread.

Event sending is asynchronous, but each FSM has a buffer for several events. If this buffer is full, event_lost flag is set and the event is forgotten. This should never happen in carefully designed application.

Note:: This macro ensures that it is not possible to send an event to other FSM than the one for which it was declared. If you get compilation error, that __<FSM_ID>_<EVENT_ID> is not declared, it means the recipient doesn't handle this event.

Parameters:

	fsm_id	Event recipient's ID.
	event	Event ID to send.
	data	Any data (pointer or typecasted int) sent together with the event.

#define FSM_STATE ( name ) error_FSM_XXX_not_defined

Defines a state function for finite state machine.

This function is called by FSM framework whenever some event occurs. The event can be read by using FSM_EVENT macro. In the function body, other FSM_xxx macros can be used to invoke state transition or set the timer. When no state transition is invoked, FSM waits for the next event, after the function returns. Then, after another event occurs, this state function is called again with that event.

Note:: The body of state function is declared as void inline function. This function is called from state function stub, which contains debugging macros.

The actual name of the function stub is fsm_state_<name> and the name of inline implementation is fsm_state_<name>_impl.

Parameters:

name

Name of the state.

#define FSM_STATE_DECL ( name ) error_FSM_XXX_not_defined

Declares a prototype of state function defined later.

Parameters:

name

Name of state function.

#define FSM_STATE_FULL_DECL	(	fsm_name,
		name
	)		int __fsm_func_name(fsm_name, name,)(struct robo_fsm *fsm)

Declares a prototype of state function of given FSM.

This can be used to declare state function in header files (of other .c files) that the one with the state functions itself

Parameters:

	fsm_name	Name of FSM
	name	Name of state function.

#define FSM_TIMER ( ms )

Value:

if (FSM_EVENT != EV_EXIT) {                                     \
                __fsm_timespec_add_ms(&fsm->timer, &fsm->loop->now, (ms)); \
                if (!fsm->loop->first ||                                \
                    __fsm_timespec_cmp(&fsm->timer,                     \
                                       &fsm->loop->first->timer) == -1) { \
                        fsm->loop->first = fsm;                         \
                }                                                       \
        }

Sets FSM's one-shot timer.

After the specified number of milliseconds elapses, EV_TIMER is generated, unless FSM_TIMER_STOP() is used. The timer is automatically stopped on every trnasition.

Parameters:

ms

Time to timer expiration in milliseconds.

#define FSM_TIMER_STOP ( ) __fsm_timer_stop(fsm)

Stops the timer.

#define FSM_TRANSITION ( next ) error_FSM_XXX_not_defined

Sets current state to next.

The state is not changed immediately. The rest of current state function finishes its execution and then, if next is not the current state, the current state function is called again with EV_EXIT event. Finally a call to the next state function (even if it is the same as current) is executed with EV_ENTRY as event.

Parameters:

next

Next state.

#define SUBFSM_RET ( data )

Value:

do {                                                            \
                if (fsm->events[fsm->ev_head].id != EV_EXIT) {          \
                        fsm_event e = {EV_RETURN, data};                \
                        fsm->last_state = fsm->state;                   \
                        fsm->last_state_name = fsm->state_name;         \
                        fsm->state = *(--fsm->fnc_sp);                  \
                        fsm->events[fsm->ev_head] = e;                  \
                        *__ret = RC_PROC;                               \
                }                                                       \
        } while(0)

Return from sub-FSM.

EV_EXIT is executed for the current state and EV_RETURN for the state where it is returning.

Parameters:

data

Data returned back to the caller

#define SUBFSM_TRANSITION	(	substate,
		data
	)		error_FSM_XXX_not_defined

Invoke state transition to sub-FSM.

The behaviour is almost the same as of FSM_TRANSITION(), but whenever the sub-FSM returns (see SUBFSM_RET), the current state function is executed with EV_RETURN as event. Moreover, the current state function is not called with EV_EXIT before the transtition.

Parameters:

	substate	Initial state of sub-FSM.
	data	Data passed to the sub-FSM.

Typedef Documentation

typedef struct fsm_event fsm_event

Type for FSM events.

typedef int(* robo_fsm_state_t)(struct robo_fsm *fsm)

Event handler function for FSM.

Enumeration Type Documentation

enum fsm_common_events

FSM events.

Enumerator:

__COMMON_EV_ENTRY	A transition to this state was just executed (no matter whether from the same state or from the another one). This event doesn't occur on return from sub sub-automaton, use EV_RETURN for handling returns from sub-atomatons.
__COMMON_EV_EXIT	A transition to ANOTHER state is happening. If a transition is to the same state or to a sub-atomaton, this event doesn't occur. This is the last event sent before the state is changed, but robo_fsm::state already points to the next state. Warning: The behavior is undefined if state is changed (e.g. by FSM_TRANSITION()) during handling of this event.
__COMMON_EV_RETURN	Previously called sub-automaton reached its final state. EV_ENTRY is not called in this case.
__COMMON_EV_TIMER	The timer previously set by FSM_TIMER() expired.

Function Documentation

void fsm_destroy ( struct robo_fsm * fsm )

Deallocates all resources allocated by fsm_init().

Parameters:

fsm

FSM to destroy.

Here is the caller graph for this function:

const char* fsm_event_str ( fsm_event ev )

Returns string with the name of event submitted as parameter.

Parameters:

ev

Indetifier of the event

Returns:: The name of event or "undefined event!!!" if the ev doesn't refer to a valid event.

Here is the caller graph for this function:

void fsm_exit ( struct robo_fsm * fsm )

Signals FSM to exit.

This function can be called from any thread and from signal handlers.

Parameters:

fsm

FSM to exit;

Here is the caller graph for this function:

void fsm_init	(	struct robo_fsm *	fsm,
		char *	debug_name,
		struct fsm_main_loop *	loop
	)

FSM initialization.

Registeres FSM with a main event loop and prepares EV_ENTRY to be sent as the first event.

Parameters:

	fsm	FSM to initialize
	debug_name	A string used to identify the FSM in debugging massages.
	loop	Mainloop which execute this fsm. Must be previously initialized by fsm_main_loop_init().

Here is the call graph for this function:

int fsm_start	(	struct fsm_main_loop *	loop,
		pthread_attr_t *	attr
	)

Starts previously initialized FSM main loop in a separate thread.

The thread is created by this function and executes fsm_thread_routine().

Parameters:

	loop	Main loop to start.
	attr	Attributes for thread creation.

Returns:: Return value of pthread_create().

Here is the caller graph for this function:

Finite State Machines

Classes

Defines

Typedefs

Enumerations

Functions

Detailed Description

Introduction

State Functions

Events

Usage

Sub-Automatons

Define Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation