From a6ab1504058304012791281f9eb42c262745888f Mon Sep 17 00:00:00 2001 From: jacqueline Date: Fri, 19 May 2023 21:21:27 +1000 Subject: Add tinyfsm, start converting core functions to an FSM-based event loop --- lib/tinyfsm/doc/10-Introduction.md | 28 +++++ lib/tinyfsm/doc/20-Installation.md | 68 +++++++++++ lib/tinyfsm/doc/30-Concepts.md | 38 ++++++ lib/tinyfsm/doc/40-Usage.md | 244 +++++++++++++++++++++++++++++++++++++ lib/tinyfsm/doc/50-API.md | 206 +++++++++++++++++++++++++++++++ lib/tinyfsm/doc/60-Development.md | 26 ++++ lib/tinyfsm/doc/70-License.md | 9 ++ 7 files changed, 619 insertions(+) create mode 100644 lib/tinyfsm/doc/10-Introduction.md create mode 100644 lib/tinyfsm/doc/20-Installation.md create mode 100644 lib/tinyfsm/doc/30-Concepts.md create mode 100644 lib/tinyfsm/doc/40-Usage.md create mode 100644 lib/tinyfsm/doc/50-API.md create mode 100644 lib/tinyfsm/doc/60-Development.md create mode 100644 lib/tinyfsm/doc/70-License.md (limited to 'lib/tinyfsm/doc') diff --git a/lib/tinyfsm/doc/10-Introduction.md b/lib/tinyfsm/doc/10-Introduction.md new file mode 100644 index 00000000..b9186f35 --- /dev/null +++ b/lib/tinyfsm/doc/10-Introduction.md @@ -0,0 +1,28 @@ +Introduction +============ + +TinyFSM is a simple finite state machine library for C++, designed for +optimal performance and low memory footprint. This makes it ideal for +real-time operating systems. The concept is very simple, allowing the +programmer to fully understand what is happening behind the scenes. It +provides a straightforward way of mapping your state machine charts +into source code. + +TinyFSM basically wraps event dispatching into function calls, making +event dispatching equally fast to calling (or even inlining) a +function. Even in the worst case, dispatching leads to nothing more +than a single vtable lookup and function call! + +Key Features +------------ + +- Entry/exit actions +- Event actions +- Transition functions +- Transition conditions +- Event payload (classes) +- Inheritance of states and action functions + +TinyFSM benefits from the C++11 template metaprogramming features like +variadic templates, and does not depend on RTTI, exceptions or any +external library. diff --git a/lib/tinyfsm/doc/20-Installation.md b/lib/tinyfsm/doc/20-Installation.md new file mode 100644 index 00000000..78fa3f1a --- /dev/null +++ b/lib/tinyfsm/doc/20-Installation.md @@ -0,0 +1,68 @@ +Installation +============ + +TinyFSM is an header-only library, no special installation steps are +needed. Just point your compiler to the "include" directory, and in +your source files: + + #include + + +Prerequisites +------------- + +TinyFSM requires a compiler supporting the C++11 language standard +("-std=c++11" in gcc). + +TinyFSM does not depend on RTTI, exceptions or any external library. +If you need to compile without standard libraries (e.g. in conjunction +with `-nostdlib` linker option), add `-DTINYFSM_NOSTDLIB` to the +compiler options: this removes all dependencies on the standard +library by disabling some compile-time type checks. + + +Building the Elevator Example +----------------------------- + +Change to the elevator example directory and compile the sources: + + $ cd examples/elevator + $ make + +Our elevator has call buttons on every floor, sensors reporting the +current position, and an alarm button for emergency. These actors can +be triggered via a simple command interface: + + $ ./elevator + Motor: stopped + Motor: stopped + c=Call, f=FloorSensor, a=Alarm, q=Quit ? + +Let's call the elevator to floor 2: + + c=Call, f=FloorSensor, a=Alarm, q=Quit ? c + Floor ? 2 + Motor: moving up + c=Call, f=FloorSensor, a=Alarm, q=Quit ? + +Now the elevator is moving up, and we need to trigger the floor sensor: + + c=Call, f=FloorSensor, a=Alarm, q=Quit ? f + Floor ? 1 + Reached floor 1 + c=Call, f=FloorSensor, a=Alarm, q=Quit ? f + Floor ? 2 + Reached floor 2 + Motor: stopped + c=Call, f=FloorSensor, a=Alarm, q=Quit ? + +Now we simulate a sensor defect: + + c=Call, f=FloorSensor, a=Alarm, q=Quit ? c + Floor ? 1 + Motor: moving down + c=Call, f=FloorSensor, a=Alarm, q=Quit ? f + Floor ? 2 + Floor sensor defect (expected 1, got 2) + *** calling maintenance *** + Motor: stopped diff --git a/lib/tinyfsm/doc/30-Concepts.md b/lib/tinyfsm/doc/30-Concepts.md new file mode 100644 index 00000000..b0853d6b --- /dev/null +++ b/lib/tinyfsm/doc/30-Concepts.md @@ -0,0 +1,38 @@ +Concepts +======== + +Keep it Simple +-------------- + +By design, TinyFSM implements only the very basics needed for +designing state machines. For many people, it is important to know +what a library is doing when making a decision for a specific library. + + +State Definition +---------------- + +States are derived classes from a base FSM state, providing react() +functions for every event, as well as entry() and exit() functions. + + +Event Dispatching +----------------- + +TinyFSM does not hold state/event function tables like most other +state machine processors do. Instead, it keeps a pointer to the +current state (having the type of the state machine base +class). Dispatching an event simply calls the react() function of the +current state, with the event class as argument. This results in a +single vtable lookup and a function call, which is very efficient! + +Event dispatching on an FsmList<> are simply dispatch() calls to all +state machines in the list. + + +Header-Only Library +------------------- + +The TinyFSM library consist entirely of header files containing +templates, and requires no separately-compiled library binaries or +special treatment when linking. diff --git a/lib/tinyfsm/doc/40-Usage.md b/lib/tinyfsm/doc/40-Usage.md new file mode 100644 index 00000000..457146b3 --- /dev/null +++ b/lib/tinyfsm/doc/40-Usage.md @@ -0,0 +1,244 @@ +Usage +===== + +Refer to the [API examples](/examples/api/) provided with the TinyFSM +package for a quick overview. Recommended starting points: + + - [Elevator Project]: Documented example, two state machines with + buttons, floor sensors and actors. + - [Simple Switch]: A generic switch with two states (on/off). + - [Moore Machine] and [Mealy Machine]: Basic, educational examples. + +For an example in an RTOS environment, see the [stm32f103stk-demo] of +the [OpenMPTL] project. Starting points: + + - [screen.hpp](https://github.com/digint/openmptl/tree/master/projects/stm32f103stk-demo/src/screen.hpp) + : TinyFSM declarations. + - [kernel.cpp](https://github.com/digint/openmptl/tree/master/projects/stm32f103stk-demo/src/kernel.cpp) + : Poll input and trigger events. + + [OpenMPTL]: https://digint.ch/openmptl/ + [stm32f103stk-demo]: https://github.com/digint/openmptl/tree/master/projects/stm32f103stk-demo + + +The examples in the documentation below are mainly based on the +[Elevator Project]. + + [Elevator Project]: /examples/elevator/ + [Simple Switch]: /examples/api/simple_switch.cpp + [Moore Machine]: /examples/api/moore_machine.cpp + [Mealy Machine]: /examples/api/mealy_machine.cpp + + +### 1. Declare Events + +Declare events that your state machine will listen to. Events are +classes derived from the tinyfsm::Event class. + +Example: + + struct FloorEvent : tinyfsm::Event + { + int floor; + }; + + struct Call : FloorEvent { }; + struct FloorSensor : FloorEvent { }; + struct Alarm : tinyfsm::Event { }; + +In the example above, we declare three events. Note that events are +regular classes, which are passed as arguments to the react() members +of a state class. In this example, we use a member variable "floor", +which is used to specify the floor number on "Call" and "FloorSensors" +events. + + +### 2. Declare the State Machine Class + +Declare your state machine class. State machines are classes derived +from the tinyfsm::Fsm template class, where T is the type name of the +state machine itself. + +You need to declare the following public members: + + - react() function for each event + - entry() and exit() functions + +Example: + + class Elevator + : public tinyfsm::Fsm + { + public: + /* default reaction for unhandled events */ + void react(tinyfsm::Event const &) { }; + + virtual void react(Call const &); + virtual void react(FloorSensor const &); + void react(Alarm const &); + + virtual void entry(void) { }; /* entry actions in some states */ + void exit(void) { }; /* no exit actions */ + }; + + +Note that you are free to declare the functions non-virtual if you +like. This has implications on the execution speed: In the example +above, the react(Alarm) function is declared non-virtual, as all states +share the same reaction for this event. This makes code execution +faster when dispatching the "Alarm" event, since no vtable lookup is +needed. + + +### 3. Declare the States + +Declare the states of your state machine. States are classes derived +from the state machine class. + +Note that state classes are *implicitly instantiated*. If you want to +reuse states in multiple state machines, you need to declare them as +templates (see `/examples/api/multiple_switch.cpp`). + +Example: + + class Panic + : public Elevator + { + void entry() override; + }; + + class Moving + : public Elevator + { + void react(FloorSensor const &) override; + }; + + class Idle + : public Elevator + { + void entry() override; + void react(Call const & e) override; + }; + + +In this example, we declare three states. Note that the "elevator" +example source code does not declare the states separately, but rather +defines the code directly in the declaration. + + +### 4. Implement Actions and Event Reactions + +In most cases, event reactions consist of one or more of the following +steps: + + - Change some local data + - Send events to other state machines + - Transit to different state + +**Important**: +Make sure that the `transit<>()` function call is the last command +executed within a reaction function! + +**Important**: +Don't use `transit<>()` in entry/exit actions! + +Example: + + void Idle::entry() { + send_event(MotorStop()); + } + + void Idle::react(Call const & e) { + dest_floor = e.floor; + + if(dest_floor == current_floor) + return; + + /* lambda function used for transition action */ + auto action = [] { + if(dest_floor > current_floor) + send_event(MotorUp()); + else if(dest_floor < current_floor) + send_event(MotorDown()); + }; + + transit(action); + }; + + +In this example, we use a lambda function as transition action. The +`transit<>()` function does the following: + + 1. Call the exit() function of the current state + 2. Call the the transition action if provided + 3. Change the current state to the new state + 4. Call the entry() function of the new state + +Note that you can also pass condition functions to the `transit<>()` +function. + + +### 5. Define the Initial State + +Use the macro `FSM_INITIAL_STATE(fsm, state)` for defining the initial +state (or "start state") of your state machine: + +Example: + + FSM_INITIAL_STATE(Elevator, Idle) + +This sets the current state of the "Elevator" state machine to "Idle". +More specifially, it defines a template specialization for +`Fsm::set_initial_state()`, setting the current state to +Idle. + + +### 6. Define Custom Initialization + +If you need to perform custom initialization, you can override the +reset() member function in your state machine class. If you are using +state variables, you can re-instantiate your states by calling +`tinyfsm::StateList::reset()`. + +Example: + + class Switch : public tinyfsm::Fsm + { + public: static void reset(void) { + tinyfsm::StateList::reset(); // reset all states + myvar = 0; + ... + } + ... + } + +Make sure to always set the current state, or you'll end up with a +null pointer dereference. + + +### 7. Use FsmList for Event Dispatching + +You might have noticed some calls to a send_event() function in the +example above. This is NOT a function provided with TinyFSM. Since +event dispatching can be implemented in several ways, TinyFSM leaves +this open to you. The "elevator" example implements the send_event() +function as *direct event dispatching*, without using event +queues. This has the advantage that execution is much faster, since no +RTTI is needed and the decision which function to call for an event +class is made at compile-time. On the other hand, special care has to +be taken when designing the state machines, in order to avoid loops. + +Code from "fsmlist.hpp": + + typedef tinyfsm::FsmList fsm_list; + + template + void send_event(E const & event) + { + fsm_list::template dispatch(event); + } + +Here, send_event() dispatches events to all state machines in the +list. It is important to understand that this approach comes with no +performance penalties at all, as long as the default reaction is +defined empty within the state machine declaration. diff --git a/lib/tinyfsm/doc/50-API.md b/lib/tinyfsm/doc/50-API.md new file mode 100644 index 00000000..44fcf172 --- /dev/null +++ b/lib/tinyfsm/doc/50-API.md @@ -0,0 +1,206 @@ +API Reference +============= + +`#include ` + + +Class Diagram +------------- + ....... + +--------------------------------------: T : + | tinyfsm::FsmList :.....: + +-----------------------------------------| + | [+] set_initial_state() <> | + | [+] reset() <> | + | [+] enter() <> | + | [+] start() <> | + | [+] dispatch(Event) <> | + +-----------------------------------------+ + + + ....... + +--------------------------------------: T : + | tinyfsm::Fsm :.....: + +-----------------------------------------| + | [+] state() <> | + | [+] set_initial_state() <> | + | [+] reset() <> | + | [+] enter() <> | + | [+] start() <> | + | [+] dispatch(Event) <> | + | [#] transit() | + | [#] transit(Action) | + | [#] transit(Action, Condition) | + +-----------------------------------------+ + # + | + | + +---------------------+ + | MyFSM | + +---------------------+ + | [+] entry() | + | [+] exit() | + | [+] react(EventX) | + | [+] react(EventY) | + | ... | + +---------------------+ + # + | + +-------------+-------------+ + | | | + +---------+ +---------+ +---------+ + | State_A | | State_B | | ... | + +---------+ +---------+ +---------+ + + + [#] protected + [+] public + [-] private + + +template< typename F > class Fsm +-------------------------------- + +### State Machine Functions + + * `template< typename S > static constexpr S & state(void)` + + Returns a reference to a (implicitly instantiated) state S. Allows + low-level access to all states; + + + * `static void set_initial_state(void)` + + Function prototype, must be defined (explicit template + specialization) for every state machine class (e.g. by using the + `FSM_INITIAL_STATE(fsm, state`) macro). Sets current state to + initial (start) state. + + + * `static void reset(void)` + + Empty function, can be overridden by state machine class in order to + perform custom initialization (e.g. set static state machine + variables, or reset states using `StateList::reset()`) + or directly via the `state()` instance). + + Note that this function is NOT called on start(). + + See example: `/examples/api/resetting_switch.cpp` + + * `static void enter(void)` + + Helper function, usually not needed to be used directly: + calls entry() function of current state. + + + * `static void start()` + + Sets the initial (start) state and calls its entry() function. + + + * `template< typename E > static void dispatch(E const &)` + + Dispatch an event to the current state of this state machine. + + +### State Transition Functions + + * `template< typename S > void transit(void)` + + Transit to a new state: + + 1. Call exit() function on current state + 2. Set new current state to S + 3. Call entry() function on new state + + + * `template< typename S, typename ActionFunction > void transit(ActionFunction)` + + Transit to a new state, with action function: + + 1. Call exit() function on current state + 2. Call ActionFunction + 3. Set new current state to S + 4. Call entry() function on new state + + + * `template< typename S, typename ActionFunction, typename ConditionFunction > void transit(ActionFunction, ConditionFunction)` + + Transit to a new state only if ConditionFunction returns true. + Shortcut for: `if(ConditionFunction()) transit(ActionFunction);`. + + +### Derived Classes + +#### template< typename F > class MooreMachine + +Moore state machines have entry actions, but no exit actions: + + * `virtual void entry(void) { }` + + Entry action, not enforcing. Can be enforced by declaring pure + virtual: `virtual void entry(void) = 0` + + * `void exit(void) { }` + + No exit actions. + +See example: `/examples/api/more_machine.cpp` + +#### template< typename F > class MealyMachine + +Mealy state machines do not have entry/exit actions: + + * `void entry(void) { }` + + No entry actions. + + * `void exit(void) { }` + + No exit actions. + +*Input actions* are modeled in react(), conditional dependent of event +type or payload and using `transit<>(ActionFunction)`. + +See example: `/examples/api/mealy_machine.cpp` + + +template< typename... FF > struct FsmList +----------------------------------------- + + * `static void set_initial_state(void)` + + Calls set_initial_state() on all state machines in the list. + + + * `static void reset()` + + Calls reset() on all state machines in the list. + + + * `static void enter()` + + Calls enter() on all state machines in the list. + + + * `static void start()` + + Sets the initial (start) state for all state machines in list, then + call all entry() functions. + + + * `template< typename E > static void dispatch(E const &)` + + Dispatch an event to the current state of all the state machines in + the list. + + +template< typename... SS > struct StateList +------------------------------------------- + + * `static void reset(void)` + + Re-instantiate all states in the list, using copy-constructor. + + See example: `/examples/api/resetting_switch.cpp` diff --git a/lib/tinyfsm/doc/60-Development.md b/lib/tinyfsm/doc/60-Development.md new file mode 100644 index 00000000..24ad0e14 --- /dev/null +++ b/lib/tinyfsm/doc/60-Development.md @@ -0,0 +1,26 @@ +Development +=========== + +Source Code Repository +---------------------- + +The source code for TinyFSM is managed using Git: + + git clone https://dev.tty0.ch/tinyfsm.git + +Mirror on GitHub: + + git clone https://github.com/digint/tinyfsm.git + + +How to Contribute +----------------- + +Your contributions are welcome! + +If you would like to contribute or have found bugs, visit the [TinyFSM +project page on GitHub] and use the [issues tracker] there, or contact +the author via email. + + [TinyFSM project page on GitHub]: http://github.com/digint/tinyfsm + [issues tracker]: http://github.com/digint/tinyfsm/issues diff --git a/lib/tinyfsm/doc/70-License.md b/lib/tinyfsm/doc/70-License.md new file mode 100644 index 00000000..6a4da72f --- /dev/null +++ b/lib/tinyfsm/doc/70-License.md @@ -0,0 +1,9 @@ +License +======= + +TinyFSM is [Open Source] software. It may be used for any purpose, +including commercial purposes, at absolutely no cost. It is +distributed under the terms of the [MIT license]. + + [Open Source]: http://www.opensource.org/docs/definition.html + [MIT license]: http://www.opensource.org/licenses/mit-license.html -- cgit v1.2.3