Is my implementation of a deterministic finite state machine framework with support for: declarative definition
, nested states
, internal/external transitions
, guards
, asynchronous execution
, serialisation
, etc.
Why
Switch/Case blocks, or even worse, logic stored in multiple variables are a poor design choice and a source of uncontrolled conditions. Automata brings in logic control by managing your system’s state complexity automatically.
The idea is simple: Automata enforces code organisation by convention, and handles the logic behind state change in a simple event-based asynchronous protocol. The result is deterministically predictable execution of code for the same starting conditions. Or put it another way: reach the same bugs for the same initial conditions and sequence of events.
Github repo: https://github.com/hyperandroid/Automata
Example how-to:
// define an automata. const json: FSMCollectionJson = [ { name : “Test”, // FSM name state : [“a”,”b”,”c”], initial: “a”, transition : [ { event : “ab”, from : “a”, to : “b”, }, { event : “bc”, from : “b”, to : “c”, } ] } ]; // register automata definition for later reference. FSMRegistry.Parse(json); // get a session for a given automata. const session = FSMRegistry.SessionFor(“Test”); // let the system handle complexity. session.dispatch(“ab”); // change state A to B session.dispatch(“ef”); // discard this message. State B has no ‘ef’ transition session.dispatch(“bc”);
FSM, States and transitions
In Automata, a FSM is an immutable entity, so are the states and transitions that conform it. It is a directed graph of nodes (States
) connected by Transitions
.
These are defined in the simplest JSON format possible:
{ name : string; // automata name state : string[]; // state names initial : string; // initial state name. transition : { event : string; // event triggering state change from : string; // from state name to : string; // to state name }[] // array of transition }
State entry/exit and Transition Actions.
When entering or exiting an State, and when a Transition is triggered, Automata calls function hooks associated to these events called Actions
. For example, when a Transition from State A
to State B
by Event E
is triggered, the following sequence of functions is called:
- call
State A exit
action. - call
Transition E
action. - call
State B enter
action.
These actions are optional, and are defined in the Session client state
object.
Session
The session object has two main responsibilities:
- it keeps track of one specific internal FSM state.
- it keeps a reference to
Client State
, which linksState
with an arbitrary state object.
For example, we can define an FSM for a game like Word With Friends. A session will keep track of the internal State (e.g. changing_tiles), and the game state object, which keeps bound information for the board, player’s tiles, etc.
State enter/exit actions, will be functions of the form: <state_name>_enter
and <state_name>_exit
respectively. Transition actions will be functions of the form: <transition_name>_transition
. These function are defined in the Session Client State object.
For example, a Session object for the previous FSM definition could be:
// external FSM state. // your game state, like board, player's tiles, decks, etc. class SessionClientState { numPlayers = 0; constructor() {} b_enter( ctx: StateInvocationParams<SessionLogic> ) {} b_exit( ctx: StateInvocationParams<SessionLogic> ) { // guaranteed session.currentState.name==='b' } a_exit( ctx: StateInvocationParams<SessionLogic> ) { this.numPlayers++; } ab_transition( ctx: StateInvocationParams<SessionLogic> ) {} // not all States or Transition need their actions defined. // Automata will call only the existing ones. } // a session, binding FSM state with external state. const session = FSMRegistry.SessionFor( "Test", new SessionClientState() // attach client state // to automata state. );
How you interact with the session object is simple:
session.dispatchMessage({ event: "ab" }); // this will invoke `a_exit`, `ab_transition`, and `b_enter` // functions if any are defined in the SessionClientState object. // if the current state does not recognize this message // (defined in transitions block of the FSM), // this dispatch has no effect.
Nested states
In Automata, FSM are States by definition. Nested State
mean that a given FSM state, can refer another FSM as one of its states.
Internally, a Session
object keeps an stack of states called SessionContext
.
Even the most basic Session
object, like the example Test FSM
, will have two contexts. If at any given time a Session
is in State a
, the context stack would be like:
State a // regular State Test // FSM State
As such, entering any FSM, triggers the following sequence of actions:
execute Test initial_Transition Action execute Test_enter Action execute a_enter Action
For each entered FSM, the Session
will contain an additional SessionContext
, thus keeping track of entered substates.
You can refer to another FSM
in any FSM
definition, by naming the State
as @<state name>
. For example:
const json: FSMCollectionJson = [ { name: "SubStateTest", state: ["_1", "_2", "_3"], initial: "_1", transition: [...] }, { name : "Test", state : ["a","b","@SubStateTest","c"], initial: "a", transition : [...] } ];
Exiting Hierarchically nested states
Entering hierarchies of States is easy, but exiting nested States can be misleading.
When transitioning, Automata will always try to find a valid Transition
for the current state
. This means that the whole stack of contexts will be checked for a valid transition.
For example, taking the previous substate stacktrace as base, to find a suitable Transition
for current State _1
, Automata will also check in SubStateTest
state and Test4
for a valid Transition. In this sample FSM
definition, assuming a session for Test4
which references another FSM as @Sub
:
+- Test4 -------------------------------------------+ | | | +---+ +------+ +---+ | |--> | A | -- ab --> | @Sub | -- sb --> | B | | | +---+ +------+ +---+ | | | +---------------------------------------------------+ +- Sub ------------------------------------------+ | | | +---+ +---+ +---+ | |--> | 1 | -- 12 --> | 2 | -- 23 --> | 3 | | | +---+ +---+ +---+ | | | +------------------------------------------------+
When trying to Transition
from 2
, by a message of type {event:”sb”}
, automata will find a valid transition from @Sub — to → B
, resulting in the following action calls:
+ state 2 exit Action + state Sub exit Action + transition sb Action + state B enter Action
Guards
A Guard
is a condition associated to a Transition
which can prevent the normal flow of events triggered by the transition. They are implemented as a function in the SessionClientState
object of the form:
( ctx: StateInvocationParams<SessionLogic> ) => boolean
For example, we want to have a transition from State A
, to State B
by Transition AB
event. If the guard function returns false
, the Transition is prevented, and instead of a A -> Transition -> B
flow of actions, the execution flow would be: A -> Transition -> A
.
This important fact is indicated in the StateInvocationParams
object, by having is optional variable guarded
set to true.
Local vs External transitions
FSM interaction happen primarily by calling dispatchMessage
which dispatchs a message to a Session
object. Each dispatched message, generates an internal messages queue, where internal messages can be queued.
When a given FSM Action
needs to post a message it must use postMessage
function instead.
Posted
messages will be queued in the current execution unit, before dispatched
messages. This way, an auto-transition can happen safely.
An Action
can as well dispatchMessage
at any time, but the difference is clear: dispatched messages will be queued after all previously dispatched messages w/o any guarantee of order of execution.
It is important to note that all messages, dispatched or posted, run in the context of setImmediate
calls. This has important implications like the fact that dispatchMessage
is fully asynchronous. This function accepts a second parameter to get notifications of when the message has been fully consumed. This is specially important when a given FSM Action
, posts new
messages to be consumed in the same unit of execution.
The full dispatchMessage
signature is:
session.dispatchMessage( {"event":"ab"}, new SessionConsumeMessagePromise<SessionClientState>().then( (session: Session<SessionLogic>, message?: Message) => { // event succesfully fully consumed // (all post messages included) }, (session: Session<SessionLogic>, error?: Error) => { // event fully consumed (all post messages included). // there was an error in execution. } ) );
Also note that all events sent to Automata, execute in a try/catch
block. The catch error will be notified to the error function of the optional consumption execution promise.
Session serialisation
By default, a Session
serializes its FSM
definition, and its internal state.
There’s no way for Automata to know what parts of the ClientState
are transient or how to serialise them, so it delegates this step to the ClientState
developer.
If the ClientState
has a method serialize
, it will be invoked and its result saved next to the Session’s
serialization information.
Serialization process would then just be:
const serialized_session = session.serialize()
Analogously, deserialization of a Session object needs a ClientState builder function
. The call to have a fully fresh session built from a serialised object would be:
const session2 = Session.Deserialize( serialized_session, (data: any) : SessionLogic => { // data is the serialized client state. return new SessionClientState(data); });
The session serializes the FSM needed to build it, w/o polluting the FSM Registry. The idea is to be self contained, so a Session
knows how to restore its internal state.
Session observers
While Session objects actions are choreographed by Automata framework, it is interesting to know about certain important Session events. The full creation of a session function call is:
Registry.SessionFor( "Test4", // a registered FSM new ClientState(), // a client State object session_observer // an optional session observer. );
SessionObserver
is of the form:
export interface SessionObserver<T> { // session finished. can't accept any other messages. finished(session: Session<T>); // session has fully processed the init event. // see Local vs External transitions. ready(session: Session<T>, message: Message|Error, isError: boolean); // the session changed State. // Auto-transitions and guarded transitions // also notify this method. stateChanged(session: Session<T>, from: string, to: string, message?: Message); }
FSM Registry
The Registry
keeps FSM definitions and allows to create multiple sessions for the same FSM. Serialised sessions don’t add new FSM entries to the Registry
.
To add new FSM definitions, you just call
Registry.Parse( FSMJson[] );
FSMJson
definition is as follows:
export interface TransitionJson { from: string; to: string; event: string; } export interface FSMJson { name: string; state: string[]; initial: string; transition: TransitionJson[]; }
Once registered, obtaining a session is quite simple:
// T is any object used as SessionClientState. Registry.SessionFor<T>(s: string, state: T, observer?: SessionObserver<T>)
e.g.
const session = Registry.SessionFor( "Test4", // a registered FSM new ClientState() // a client State object ); session.dispatchMessage({ event:"an_event", payload: {} // extra payload received in the Action's // StateInvocationParams message object. });
Examples
Going directly to the complex example. I include the FSM definition of one of my multiplayer games, a full clone of Scrabble/Word with friends type of games.
