cryptocode/zigfsm — Gitpedia

<img align="right" width="160" height="160" src="https://user-images.githubusercontent.com/34946442/152222895-9c8adb22-a22d-4bce-a513-3486ca28bdd5.png"> zigfsm is a finite state machine library for Zig.

This library supports Zig 0.16 all the way down to Zig 0.12.x. Use the appropriate tag for older version.

Tested on Linux, macOS, FreeBSD and Windows.

Features
Motivation
Using zigfsm

Features

Never allocates
Works at both comptime and runtime
Fast transition validation
Compact memory representation
State machines can export themselves to the Graphviz DOT format
Defined programmatically or by importing Graphviz or libfsm text (even at compile time)
Imported state machines can autogenerate state- and event enums
Optional event listeners can add functionality and cancel transitions
Push-down automaton wrappers are easy to write (see GameState example in tests.zig)
Comprehensive test coverage which also serves as examples

Motivation

Using an FSM library may have some benefits over hand-written state machines:

Many real-world processes, algorithms, and protocols have rigorously defined state machines available. These can be imported directly or programmatically into zigfsm.
Can lead to significant simplification of code, as transition rules are explicitly stated in one place. Contrast this with the brittleness of manually checking and documenting which states can follow a certain state when a certain event happens.
An invalid state transition is an immediate error with useful contextual information.
You get visualization for free, which is helpful during development, debugging and as documentation.

Using zigfsm

Before diving into code, it's worth repeating that zigfsm state machines can generate their own diagram, as well as import them. This can be immensely helpful when working on your state machines,
as you get a simple visualization of all transitions and events. Obviously, the diagrams can be used as part of your documentation as well.

Here's the diagram from the CSV parser test, as generated by the library:

csv

Diagrams can be exported to any writer using exportGraphviz(...), which accepts StateMachine.ExportOptions to change style and layout.

A png can be produced using the following command: dot -Tpng csv.gv -o csv.png

Building

To build, test and benchmark:

zig build -Doptimize=ReleaseFast
zig build test
zig build benchmark

The benchmark always runs under ReleaseFast.

Importing the library

Add zigfsm as a Zig package to your zon file, or simply import main.zig directly if vendoring.

Here's how to update your zon file using the latest commit of zigfsm:

bash
zig fetch --save git+https://github.com/cryptocode/zigfsm

Next, update your build.zig to add zigfsm as an import. For example:

zig
exe.root_module.addImport("zigfsm", b.dependency("zigfsm", .{}).module("zigfsm"));

Now you can import zigfsm from any Zig file:

zig
// This example implements a simple Moore machine: a three-level intensity lightswitch
const std = @import("std");
const zigfsm = @import("zigfsm");

pub fn main() !void {
    // A state machine type is defined using state enums and, optionally, event enums.
    // An event takes the state machine from one state to another, but you can also switch to
    // other states without using events.
    //
    // State and event enums can be explicit enum types, comptime generated enums, or
    // anonymous enums like in this example.
    //
    // If you don't want to use events, simply pass null to the second argument.
    // We also define what state is the initial one, in this case .off
    var fsm = zigfsm.StateMachine(enum { off, dim, medium, bright }, enum { click }, .off).init();

    // There are many ways to define transitions (and optionally events), including importing
    // from Graphviz. In this example we use a simple API to add events and transitions.
    try fsm.addEventAndTransition(.click, .off, .dim);
    try fsm.addEventAndTransition(.click, .dim, .medium);
    try fsm.addEventAndTransition(.click, .medium, .bright);
    try fsm.addEventAndTransition(.click, .bright, .off);

    std.debug.assert(fsm.isCurrently(.off));

    // Do a full cycle: off -> dim -> medium -> bright -> off
    _ = try fsm.do(.click);
    _ = try fsm.do(.click);
    _ = try fsm.do(.click);
    _ = try fsm.do(.click);

    // Make sure we're in the expected state
    std.debug.assert(fsm.isCurrently(.off));
    std.debug.assert(fsm.canTransitionTo(.dim));
}

Learning from the tests

A good way to learn zigfsm is to study the tests file.

This file contains a number of self-contained tests that also demonstrates various aspects of the library.

Creating a state machine type

A state machine type is defined using state enums and, optionally, event enums.

Here we create an FSM for a button that can be clicked to flip between on and off states. The initial state is .off:

zig
const State = enum { on, off };
const Event = enum { click };
const FSM = zigfsm.StateMachine(State, Event, .off);

If you don't need events, simply pass null:

zig
const FSM = zigfsm.StateMachine(State, null, .off);

Making an instance

Now that we have a state machine type, let's create an instance with an initial state :

zig
var fsm = FSM.init();

If you don't need to reference the state machine type, you can define the type and get an instance like this:

zig
var fsm = zigfsm.StateMachine(State, Event, .off).init();

You can also pass anonymous state/event enums:

zig
var fsm = zigfsm.StateMachine(enum { on, off }, enum { click }, .off).init();

Adding state transitions

zig
try fsm.addTransition(.on, .off);
try fsm.addTransition(.off, .on);

Optionally defining events

While transitionTo can now be used to change state, it's also common to invoke state transitions
using events. This can vastly simplify using and reasoning about your state machine.

The same event can cause different transitions to happen, depending on the current state.

Let's define what .click means for the on and off states:

zig
try fsm.addEvent(.click, .on, .off);
try fsm.addEvent(.click, .off, .on);

This expresses that if .click happens in the .on state, then transition to the .off state, and vice versa.

Defining transitions and events at the same time

A helper function is available to define events and state transitions at the same time:

zig
try fsm.addEventAndTransition(.click, .on, .off);
try fsm.addEventAndTransition(.click, .off, .on);

Which approach to use depends on the application.

Defining transitions and events as a table

Rather than calling addTransition and addEvent, StateMachineFromTable can be used to pass a table of event- and state transitions.

zig
const State = enum { on, off };
const Event = enum { click };
const definition = [_]Transition(State, Event){
    .{ .event = .click, .from = .on, .to = .off },
    .{ .event = .click, .from = .off, .to = .on },
};
var fsm = zigfsm.StateMachineFromTable(State, Event, &definition, .off, &.{}).init();

Note that the .event field is optional, in which case only transition validation is added.

Changing state

Let's flip the lights on by directly transitioning to the on state:

zig
try fsm.transitionTo(.on);

This will fail with StateError.Invalid if the transition is not valid.

Next, let's change state using the click event. In fact, let's do it several times, flipping the switch off and on and off again:

zig
try fsm.do(.click);
try fsm.do(.click);
try fsm.do(.click);

Again, this will fail with StateError.Invalid if a transition is not valid.

Finally, it's possible to change state through the more generic apply function, which takes either a new state or an event.

zig
try fsm.apply(.{ .state = .on });
try fsm.apply(.{ .event = .click });

Probing the current state

The current state is available through currentState(). To check if the current state is a specific state, call isCurrently(...)

If final states have been added through addFinalState(...), you can check if the current state is in a final state by calling isInFinalState()

To check if the current state is in the start state, call isInStartState()

See the API docstring for more information about these are related functions.

Inspecting what transition happened

zig
const transition = try fsm.do(.identifier);

if (transition.to == .jumping and transition.from == .running) {
    ...
}

... where transition contains the fields from, to and event.

Followed by an if/else chain that checks relevant combinations of from- and to states. This could, as an example, be used in a parser loop.

See the tests for examples.

Valid states iterator

It's occasionally useful to know which states are possible to reach from the current state. This is done using an iterator:

zig
while (fsm.validNextStatesIterator()) |valid_next_state| {
    ...
}

Importing state machines

It's possible, even at compile time, to parse a Graphviz or libfsm text file and create a state machine from this.

importText is used when you already have state- and event enums defined in Zig. importText can also be called at runtime to define state transitions.
generateStateMachineFromText is used when you want the compiler to generate these enums for you. While this saves you from writing enums manually, a downside is that editors and language servers are unlikely to support autocomplete on generated types.

The source input can be a string literal, or brought in by @embedFile.

See the test cases for examples on how to use the import features.

Transition handlers

A previous section explained how to inspect the source and target state. There's another way to do this, using callbacks.

This gets called when a transition happens. The main benefit is that it allows you to cancel a transition.

Handlers also makes it easy to keep additional state, such as source locations when writing a parser.

Let's keep track of the number of times a light switch transition happens:

zig
var countingHandler = CountingHandler.init();
try fsm.addTransitionHandler(&countingHandler.handler);

Whenever a transition happens, the handler's public onTransition function will be called. See tests for complete
examples of usage.

Canceling transitions

The transition handler can conditionally stop a transition from happening by returning HandlerResult.Cancel. The callsite of transitionTo or do will then fail with StateError.Invalid

Alternatively,HandlerResult.CancelNoError can be used to cancel without failure (in other words, the current state remains but the callsite succeeds)