Friendly Finite State Machine Syntax for Swift on macOS, iOS, tvOS and watchOS
Inspired by Uncle Bob’s SMC syntax, Swift FSM is a pure Swift DSL for declaring and operating a Finite State Machine (FSM).
This guide presumes some familiarity with FSMs and specifically the SMC syntax linked above. Swift FSM makes liberal use of @resultBuilder blocks, operator overloads, [callAsFunction()][5], and [trailing closures][6], all in combination with one another - familiarity with these concepts will also be helpful.
Contents
[Requirements][7]
[Basic Syntax][8]
[Optional Arguments][9]
[Super States][10]
[Entry and Exit Actions][11]
[Syntax Order][12]
[Syntax Variations][13]
[Syntactic Sugar][14]
[Runtime Errors][15]
[Performance][16]
[Expanded Syntax][17]
[Example][18]
[ExpandedSyntaxBuilder and Predicate][19]
[Implicit Matching Statements][20]
[Multiple Predicates][21]
[Implicit Clashes][22]
[Deduplication][23]
[Chaining Blocks][24]
[Condition Statements][25]
[Runtime Errors][26]
[Predicate Performance][27]
[Troubleshooting][28]
Requirements
Swift FSM is a Swift Package, importable through the Swift Package Manager, and requires macOS 13, iOS 16, tvOS 16 and watchOS 9, alongside Swift 5.7 or later. If you need support for older platforms, please check out the [backport][29] branch.
It has two dependencies - Apple’s [Algorithms][30], and ([in one small corner][31]) my own [Reflective Equality][32]
Basic Syntax
Borrowing from SMC, we will use the example of a subway turnstile system. This turnstile has two possible states: Locked, and Unlocked, and two possible events: Coin, and Pass.
The logic is as follows (from Uncle Bob, emphasis added):
Given we are in the Locked state, when we get a Coin event, then we transition to the Unlocked state and invoke the unlock action.
Given we are in the Locked state, when we get a Pass event, then we stay in the Locked state and invoke the alarm action.
Given we are in the Unlocked state, when we get a Coin event, then we stay in the Unlocked state and invoke the thankyou action.
GIven we are in the Unlocked state, when we get a Pass event, then we transition to the Locked state and invoke the lock action.
Following Uncle Bob’s examples, we will build up our table bit by bit to demonstrate the different syntactic possibilities of Swift FSM and how they compare to SMC:
The SyntaxBuilder protocol provides the methods define, when, and then necessary to build the transition table. It has two associated types, State and Event, which must be Hashable.
let fsm = FSM<State, Event>(initialState: .locked)
FSM is generic over State and Event. As with SyntaxBuilder, State and Event must be Hashable. Here we have used an Enum, specifying the initial state of the FSM as .locked.
try fsm.buildTable {
fsm.buildTable is a throwing function - though the type system will prevent various illogical statements, there are some issues that can only be detected at runtime.
define(.locked) {
The define statement roughly corresponds to the ‘Given’ keyword in the natural language description of the FSM. It is expected however that you will only write one define per state.
define takes two arguments - a State instance, and a Swift @resultBuilder block.
when(.coin) | then(.unlocked) | unlock
As we are inside a define block, we take the .locked state as a given. We can now list our transitions, with each line representing a single transition. In this case, when we receive a .coin event, we will then transition to the .unlocked state and call unlock.
unlock is a function, also declarable as follows:
when(.coin) | then(.unlocked) | { unlock() //; otherFunction(); etc. }
The | (pipe) operator binds transitions together. It feeds the output of the left hand side into the input of the right hand side, as you might expect in a terminal.
fsm.handleEvent(.coin)
The FSM instance will look up the appropriate transition for its current state, call the associated function, and transition to the associated next state. In this case, the FSM will call the unlock function and transition to the unlocked state. If no transition is found, it will do nothing, and if compiled for debugging, will print a warning message.
Optional Arguments
Now let’s add an Alarming state that must be reset by a repairman:
then() with no argument means ‘no change’, and the FSM will remain in the current state. The actions pipe is also optional - if a transition performs no actions, it can be omitted.
Super States
Notice the duplication of the Reset transition. In all three states the Reset event does the same thing. It transitions to the Locked state and it invokes the lock and alarmOff actions. This duplication can be eliminated by using a Super State as follows:
SMC:
Initial: Locked
FSM: Turnstile
{
// This is an abstract super state.
(Resetable) {
Reset Locked {alarmOff lock}
}
Locked : Resetable {
Coin Unlocked unlock
Pass Alarming alarmOn
}
Unlocked : Resetable {
Coin Unlocked thankyou
Pass Locked lock
}
Alarming : Resetable { // inherits all it's transitions from Resetable.
}
}
SuperState takes the same @resultBuilder as define, however it does not take a starting state. The starting state is taken from the define statement to which it is passed. Passing SuperState instances to a define call will add the transitions declared in each of the SuperState instances before the other transitions declared in the define.
If a SuperState instance is passed to define, the @resultBuilder argument is optional.
SuperState instances themselves can adopt other SuperState instances, and will combine them together in the same way as define:
let s1 = SuperState { when(.coin) | then(.unlocked) | unlock }
let s2 = SuperState { when(.pass) | then(.alarming) | alarmOn }
let s3 = SuperState(adopts: s1, s2)
// s3 is equivalent to:
let s4 = SuperState {
when(.coin) | then(.unlocked) | unlock
when(.pass) | then(.alarming) | alarmOn
}
Overriding SuperStates
By default, transitions declared in a SuperState cannot be overridden by their adopters. The following code is therefore assumed to be accidental and throws:
The override block indicates to Swift FSM that any transitions contained within it override any inherited transitions with the same initial states and events.
As multiple inheritance is allowed, overrides replace all matching transitions:
In this scope, the word override has no meaning and therefore is ignored by the error handler. What remains is therefore two duplicate transitions, resulting in an error.
Overriding Overrides
Overrides in Swift FSM follow the usual rules of inheritance. In a chain of overrides, it is the final transition in that chain that takes precedence:
In the previous example, the fact that the alarm is turned on every time the Alarming state is entered and is turned off every time the Alarming state is exited, is hidden within the logic of several different transitions. We can make it explicit by using entry actions and exit actions.
onEntry and onExit are the final arguments to define and specify an array of entry and exit actions to be performed when entering or leaving the defined state. Note that these require array syntax rather than varargs, as a work around for limitations in Swift’s matching algorithm for functions that take multiple closure arguments.
SuperState instances can also accept entry and exit actions:
SuperState instances also inherit entry and exit actions from their superstates:
let s1 = SuperState(onEntry: [unlock]) { when(.coin) | then(.unlocked) }
let s2 = SuperState(onEntry: [alarmOn]) { when(.pass) | then(.alarming) }
let s3 = SuperState(adopts: s1, s2)
// s3 is equivalent to:
let s4 = SuperState(onEntry: [unlock, alarmOn]) {
when(.coin) | then(.unlocked)
when(.pass) | then(.alarming)
}
Configuring Entry and Exit Actions Behaviour
In SMC, entry and exit actions are invoked even if the state does not change. In the example above, the unlock entry action would be called on all transitions into the Unlocked state, even if the FSM is already in the Unlocked state.
In contrast, Swift FSM’s default behaviour is to invoke entry and exit actions only if there is a state change. In the example above, this means that, in the .unlocked state, after a .coin event, unlock will not be called.
This policy is configurable, by passing .executeAlways as the second argument to FSM.init:
This setting replicates SMC entry/exit action behaviour. The default is .executeOnStateChangeOnly and is not a required argument.
Syntax Order
All statements must be made in the form define { when | then | actions }. See [Expanded Syntax][33] below for exceptions to this rule.
Syntax Variations
Though define, when, and then are functions, there are matching structs with equivalent capitalised names contained in the SwiftFSM.Syntax namespace. You can therefore leverage Swift’s typealias support to modify the syntax naming conventions to fit your use case.
The @resultBuilder blocks in SwiftFSM do not support control flow logic. Though is it possible to enable such logic, it would be misleading:
define(.locked) {
if something { // ⛔️ does not compile
when(.pass) | then(.unlocked) | unlock
} else {
when(.pass) | then(.alarming) | alarmOn
}
...
}
If the if/else block were evaluated by the FSM at transition time, this would be a useful addition. However what we are doing inside these blocks is compiling our state transition table. The use of if and else in this manner is more akin to the conditional compilation statements #if/#else - based on a value defined at compile time, only one transition or the other will be added to the table.
If you do have a use for this kind of conditional compilation, please open an issue. See [Expanded Syntax][34] for alternative ways to evaluate conditional statements at transition time rather than compile time.
Runtime Errors
Important - most Swift FSM function calls and initialisers take additional parameters file: String = #file and line: Int = #line. This is similar to XCTest assertions, and allows Swift FSM to produce errors that pinpoint the location of problematic statement/s.
As these cannot be hidden, please note that there are unlikely to be any circumstances in which it would be useful or necessary to override these default arguments with alternate values.
Empty Blocks
All blocks must contain at least one transition, otherwise an error will be thrown:
Though the two transitions are distinct from one another, logically they cannot co-exist - the .coin event must lead either to the .unlocked state or to the .locked state. It cannot lead to both.
Duplicate buildTable Calls
Additional calls to fsm.buildTable { } will throw a TableAlreadyBuiltError.
NSObject Error
Swift FSM will throw an error if your State and/or Event types (or their children) inherit from NSObject.
State and Event instances are hashed to produce keys for the transition Dictionary. These keys are then recreated and reused each time fsm.handleEvent is called. This is not an issue for most Swift types, as Hashable conformance will have to be declared explicitly. NSObject however already conforms to Hashable, and is hashed by instance identity, rather than by value. This would lead to a defunct transition table where all transition lookups fail, and therefore throws an error.
This is an edge case and it is extremely unlikely that you will ever encounter this error. Nonetheless, the check is quite exhaustive - If you would like to know more about the mechanism involved, see [Reflective Equality][35].
Performance
Each call to handleEvent() requires a single operation to find the correct transition in the table. Though O(1) is ideal, this table-based system still has 2-3x the basic overhead of a nested switch case statement.
Expanded Syntax
Whilst Swift FSM matches most of the syntax of SMC, it also introduces some new possibilities of its own. None of this additional syntax is required, and is provided purely for convenience.
Example
Let’s imagine an extension to our turnstile rules: under some circumstances, we want to enforce the ‘everyone pays’ rule by entering the alarming state if a .pass is detected when still in the .locked state, yet in others, perhaps at rush hour, we want to be more permissive in order to avoid disruption to other passengers.
We could implement a time of day check somewhere else in the system, perhaps inside the implementation of the alarmOn function to decide what the appropriate behaviour should be:
try fsm.buildTable {
...
define(.locked) {
when(.pass) | then(.alarming) | handleAlarm
}
...
}
// some other file...
enum Enforcement: Predicate { case weak, strong }
let enforcement = Enforcement.weak
func handleAlarm() {
switch enforcement {
case .weak: smile()
case .strong: defconOne()
}
}
But we now have some aspects of our state transition logic declared inside the transition table, and other aspects declared elsewhere.
Furthermore, we must transition to the .alarming state, regardless of the Enforcement policy. But what if different policies called for different transitions altogether?
An alternative might be to introduce extra events to differentiate between the new policies:
This allows us both to call different functions, and to transition to different states, depending on the enforcement policy, all whilst keeping all of our logic inside the transition table.
In order to make this change however, every transition that originally responded to the .pass event will need to be rewritten twice, once for each of the two new versions of this event, even if they are identical in both cases. In no time at all, the state transition table is going to become unmanageably long, and littered with duplication.
If Enforcement is .weak, when we get a .pass, transition to .locked and smile
If Enforcement is .strong, when we get a .pass, transition to .alarming and defconOne
Regardless of Enforcement, when we get a .coin, transition to .unlocked and unlock
In this system, only those statements that depend upon the Enforcement policy need know it has been added, and all other existing statements that do not depend upon it continue to work as they always did.
ExpandedSyntaxBuilder and Predicate
ExpandedSyntaxBuilder implements SyntaxBuilder, providing all the SMC-equivalent syntax, alongside the new matching statements for working with predicates.
For the Struct based variant syntax, the equivalent namespace is SwiftFSM.Syntax.Expanded.
Predicate requires the conformer to be Hashable and CaseIterable. It is possible to use any type you wish, as long as your conformance to Hashable and CaseIterable makes logical sense. In practice, this is likely to limit Predicates to Enums without associated types, as these can be automatically conformed to CaseIterable.
Implicit Matching Statements
when(.coin) | then(.unlocked)
In the above, no Predicate is specified, and its full meaning must therefore be inferred from context. The scope for contextual inference is the sum of the builder blocks for all SuperState and define calls inside fsm.buildTable { }.
In our example, the type Enforcement appears in a matching statement elsewhere in the table, and Swift FSM will therefore infer the absent matching statement as follows:
when(.coin) | then(.unlocked)
// is inferred to mean:
matching(Enforcement.weak) | when(.coin) | then(.unlocked)
matching(Enforcement.strong) | when(.coin) | then(.unlocked)
Transitions in Swift FSM are are therefore Predicate agnostic by default, matching any given Predicate unless otherwise specified. In this way, matching is an optional modifier that constrains the transition to one or more specific Predicate cases.
Multiple Predicates
There is no limit on the number of Predicate types that can be used in one table (see [Predicate Performance][36] for practical limitations). The following (contrived and rather silly) expansion of the original Predicate example remains valid:
when(.coin) | then(.unlocked)
// types Enforcement and Reward appear elsewhere in context
// when(.coin) | then(.unlocked) is now equivalent to:
matching(Enforcement.weak, and: Reward.positive) | when(.coin) | then(.unlocked)
matching(Enforcement.strong, and: Reward.positive) | when(.coin) | then(.unlocked)
matching(Enforcement.weak, and: Reward.negative) | when(.coin) | then(.unlocked)
matching(Enforcement.strong, and: Reward.negative) | when(.coin) | then(.unlocked)
Compound Matching Statements
As seen in the above example, multiple predicates can be combined in a single matching statement, by using the and: Predicate... and or: Predicate... varargs arguments.
enum A: Predicate { case x, y, z }
enum B: Predicate { case x, y, z }
enum C: Predicate { case x, y, z }
matching(A.x, or: A.y)... // if A.x OR A.y
matching(A.x, or: A.y, A.z)... // if A.x OR A.y OR A.z
matching(A.x, and: B.x)... // if A.x AND B.x
matching(A.x, and: B.x, C.x)... // if A.x AND B.x AND C.x
matching(A.x, or: A.y, A.z, and: B.x, C.x)... // if (A.x OR A.y OR A.z) AND B.x AND C.x
matching(A.x, or: B.x)... // ⛔️ does not compile: OR types must be the same
matching(A.x, and: A.y)... // 💥 error: cannot match A.x AND A.y simultaneously
fsm.handleEvent(.coin, predicates: A.x, B.x, C.x)
In Swift FSM, matching(and:) means that we expect both predicates to be present at the same time, whereas mathing(or:) means that we expect any and only one of them to be present.
Swift FSM expects exactly one instance of each Predicate type present in the table to be passed to each call to handleEvent, as in the example above, where fsm.handleEvent(.coin, predicates: A.x, B.x, C.x) contains a single instance of types A, B and C. Accordingly, A.x AND A.y should never occur - only one can be present. Therefore, predicates passed to matching(and:) must all be of a different type. This cannot be checked at compile time, and therefore throws at runtime if violated.
In contrast, matching(or:) specifies multiple possibilities for a single Predicate. Predicates joined by or must therefore all be of the same type, and attempting to pass different Predicate types to matching(or:) will not compile (see [Implicit Clashes][37] for more information on this limitation).
Important - nested matching statements are combined by AND-ing them together, which makes it possible inadvertently to create a conflict.
define(.locked) {
matching(A.x) {
matching(A.y) {
// 💥 error: cannot match A.x AND A.y simultaneously
}
}
}
matching(or:) statements are also combined using AND:
define(.locked) {
matching(A.x, or: A.y) {
matching(A.z) {
// 💥 error: cannot match A.x AND A.z simultaneously
// 💥 error: cannot match A.y AND A.z simultaneously
}
}
}
Valid nested matching(or:) statements are combined as follows:
Swift FSM defers to the statement that explicitly specifies the greatest number of predicates - in this case, the first statement matching(Enforcement.weak, and: Reward.positive), which specifies two predicates, versus the second statement’s single predicate matching(Enforcement.weak).
Within-Predicates Clashes
Following the inference logic, connecting different types using the word ‘or’ is not allowed:
define(.locked) {
matching(Enforcement.weak, or: Reward.negative) | when(.coin) | then(.unlocked)
}
// ⛔️ does not compile, because it implies:
define(.locked) {
matching(Enforcement.weak) | when(.coin) | then(.unlocked)
matching(Reward.negative) | when(.coin) | then(.unlocked)
}
// 💥 error: implicit clash
If we were to call handleEvent(.coin, predicates: Enforcement.weak, Reward.negative) with such a table, there would be no reasonable way to decide which transition to perform. Unlike between-predicates implicit clashes, within-predicates clashes are eliminated through the type system.
matching(predicate) {
// everything in scope matches 'predicate'
}
when(event) {
// everything in scope responds to 'event'
}
then(state) {
// everything in scope transitions to 'state'
}
actions(functionCalls) {
// everything in scope calls 'functionCalls'
}
Our context blocks divide into two groups - those that can be logically chained (or AND-ed) together, and those that cannot.
Discrete Blocks - when and then
A transition responds to a single event and transitions to a single state. Therefore multiple when { } and then { } statements cannot be AND-ed together.
define(.locked) {
when(.coin) {
when(.pass) { } // ⛔️ does not compile
when(.pass) | ... // ⛔️ does not compile
matching(.something) | when(.pass) | ... // ⛔️ does not compile
matching(.something) {
when(.pass) { } // ⛔️ does not compile
when(.pass) | ... // ⛔️ does not compile
}
}
then(.unlocked) {
then(.locked) { } // ⛔️ does not compile
then(.locked) | ... // ⛔️ does not compile
matching(.something) | then(.locked) | ... // ⛔️ does not compile
matching(.something) {
then(.locked) { } // ⛔️ does not compile
then(.locked) | ... // ⛔️ does not compile
}
}
}
Additionally, there is a specific combination of when { } and then that does not compile, as there is no situation where, in response to a single event (in this case, .coin), there could then be a transition to more than one state, unless a different Predicate is given for each.
Nested actions blocks sum the actions and perform all of them. Nested matching blocks are AND-ed together.
Mixing blocks and pipes
Pipes can and must be used inside blocks, whereas blocks cannot be opened after pipes
define(.locked) {
when(.coin) | then(.unlocked) { } // ⛔️ does not compile
when(.coin) | then(.unlocked) | actions(doSomething) { } // ⛔️ does not compile
matching(.something) | when(.coin) { } // ⛔️ does not compile
}
Condition Statements
Using Predicates with matching syntax is a versatile solution, however in some cases it may bring more complexity than is necessary to solve a given problem (see [Predicate Performance][38] for a description of matching overhead).
If you need to make a specific transition conditional at runtime, then the condition statement may suffice. Some FSM implementations call this a guard statement, however the name condition was chosen here as guard is a reserved word in Swift.
Here, complexDecisionTree() is a function that returns a Bool. If it is true, the transition is executed, and if it is not, nothing is executed.
The keyword condition is syntactically interchangeable with matching - it works with pipe and block syntax, and is chainable (conditions are AND-ed together).
matching and condition blocks can also be combined freely:
There is no way to distinguish different condition statements, as the () -> Bool blocks are inherently opaque. From a logical evaluation point of view, they are invisible. What therefore remains is two statements define(.locked) { when(.coin) | ... } that both transition to different states - the FSM has no way to understand which one to call, and must therefore throw.
Runtime Errors
In order to preserve performance, fsm.handleEvent(event:predicates:) performs no error handling. Therefore, passing in Predicate instances that do not appear anywhere in the transition table will not error. Nonetheless, the FSM will be unable to perform any transitions, as it will not contain any statements that match the given, unexpected Predicate instance. It is the caller’s responsibility to ensure that the predicates passed to handleEvent and the predicates used in the transition table are of the same type and number.
try fsm.buildTable { } does perform error handling to make sure the table is syntactically and semantically valid. In particular, it ensures that all matching statements are valid, and that there are no duplicate transitions and no logical clashes between transitions.
In addition to the runtime errors thrown by the basic syntax, the expanded syntax also throws the following errors:
Matching Error
There are two ways one might inadvertently create an invalid matching statement. The first is within a single statement:
matching(A.a, and: A.b) // 💥 error: cannot match A.a AND A.b simultaneously
matching(A.a, or: B.a, and: A.b) // 💥 error: cannot match A.a AND A.b simultaneously
matching(A.a, and: A.a) // 💥 error: duplicate predicate
matching(A.a, or: A.a) // 💥 error: duplicate predicate
matching(A.x, or: B.x)... // ⛔️ does not compile: OR types must be the same
matching(A.x, and: A.y)... // 💥 error: cannot match A.x AND A.y simultaneously
The second is when AND-ing multiple matching statements through the use of blocks:
Overview: operations per function call for a table with 100 transitions, 3 Predicate types, and 10 cases per Predicate
FSM
LazyFSM
Schedule
handleEvent
1
1-7
Every transition
buildTable
100,000
100
Once on app load
FSM
Adding predicates has no effect on the performance of handleEvent(), but does affect the performance of fsm.buildTransitions { }. By default, the FSM preserves handleEvent() runtime performance by doing significant work ahead of time when creating the transition table, filling in missing transitions for all implied Predicate combinations.
The performance of fsm.buildTransitions { } is dominated by this, assuming any predicates are used at all. Because all possible combinations of cases of all given predicates have to be calculated and filtered for each transition, performance is O(m^n*o) where m is the average number of cases per predicate, n is number ofPredicate types and o is the number of transitions.
Using threePredicate types with 10 cases each in a table with 100 transitions would therefore require 100,000 operations to compile. In most real-world use cases, this is unlikely to be a problem. If your table is particularly large (see overview above), Swift FSM provides a more performance-balanced alternative for such cases in the form of the LazyFSM class.
Note: there is no performance advantage to using the keyword matching in fewer versus more transitions in your transition tables. Once the word matching is used once, and a Predicate instance is passed to handleEvent(), the performance implications for the whole table will be as above.
Lazy FSM
LazyFSM does away with the look-ahead combinatorics algorithm described above. The result is smaller tables internally, and faster table compile time. The cost is at the call to handleEvent() where multiple lookup operations are now needed to find the correct transition.
Performance ofhandleEvent() decreases from O(1) to O(n!), where n is the number of Predicate types used regardless of the number of cases. Inversely, performance of buildTable { } increases from O(m^n*o) to O(n), where n is now the number of transitions.
Using three Predicate types with 10 cases each in a table with 100 transitions would now require 100 operations to compile (down from 100,000 by a factor of 1000). Each call to handleEvent() would need to perform between 1 and 3! + 1 or 7 operations (up from 1 by a factor of 1-7). Using more than three Predicate types in this case is therefore not advisable.
Overall LazyFSM saves a lot more operations than it costs, but that cost is paid at runtime for each transition, rather than as a one-off cost at compile time. In most cases, FSM is likely to be the preferred solution, with LazyFSM reserved for especially large numbers of transitions and/or Predicate cases. If no predicates are used, both implementations exhibit similarly fast performance.
Troubleshooting
Though Swift FSM runtime errors contain verbose descriptions of the problem, nothing can be done to help with disambiguating compile time errors.
First, familiarity with how @resultBuilder works, and the kinds of compile time errors it tends to generate will be very helpful in understanding the errors you may encounter. Almost all Swift FSM-specific compile time errors will be produced by unrecognised arguments to the aforementioned @resultBuilder, and unrecognised arguments to the | operator overloaded by Swift FSM.
To help, here is a brief list of common errors you are likely to encounter if you try to build something that Swift FSM disallows at compile time:
Builder Issues
No exact matches in call to static method ‘buildExpression’
This is a common compile time error in @resultBuilder blocks. It will occur if you feed the block an argument that it does not support. It is useful to remember that each line in such a block is actually an argument fed to a static method.
For example:
try fsm.buildTable {
actions(thankyou) { }
// ⛔️ No exact matches in call to static method 'buildExpression'
}
Here an actions block is given as an argument to the hidden static function buildExpression on the @resultBuilder supporting the buildTable function. The define statement has been skipped, and actions returns a type not supported by this outer block, and therefore cannot compile.
Pipe Issues
Cannot convert value of type <T1> to expected argument type <T2>
This is common in situations where an unsupported argument is passed to a pipe overload.
For example:
try fsm.buildTable {
define(.locked) {
then(.locked) | unlock
// ⛔️ Cannot convert value of type 'Syntax.Then<TurnstileState>' to expected argument type 'Internal.MatchingWhenThen'
// ⛔️ No exact matches in call to static method 'buildExpression'
}
}
Here no matching and/or when statement precede/s the call to then(.locked). There is no | overload that takes as its two arguments the output of then(.locked) on the left, and the block () -> () on the right, and therefore cannot compile.
The error unfortunately spits out some internal implementation details that cannot be hidden. Such unavoidable details are marked as such by their location inside the Internal namespace.
It also produces a secondary error - as it cannot work out what the output of then(.locked) | unlock is, it declares that there is no overload available for buildExpression. Fix the underlying | error and this error will also disappear.
Referencing operator function ‘|’ on ‘SIMD’ requires that ‘Syntax.When<TurnstileEvent>‘ conform to ‘SIMD’
A personal favourite, from this:
try fsm.buildTable {
define(.locked) {
when(.coin) | matching(P.a) | then(.locked) | unlock
// ⛔️ Referencing operator function '|' on 'SIMD' requires that 'Syntax.When<TurnstileEvent>' conform to 'SIMD’
}
}
The order of when and matching is inverted and not supported. This no different to the previous error, but the compiler interprets the problem differently. It selects a | overload from an unrelated module and declares that it is being misused.
The compiler cannot help identify which pipe in the chain is causing the problem. Often it’s simpler just to delete and rewrite the statement rather than trying to figure out what the complaint is.
This is the original example from [Entry and Exit Actions][40], with one small error inserted at the end. This may or may not produce an appropriate error next to the dodo:
Cannot find ‘🦤’ in scope
What it will also do is generate multiple spurious errors and fixits in the SuperState declaration similar to this one:
Call to method ‘then’ in closure requires explicit use of ‘self’ to make capture semantics explicit
Reference ‘self.’ explicitly [ Fix ]
Capture ‘self’ explicitly to enable implicit ‘self’ in this closure
Ignore these errors, and if there is no other error shown, you may have to hunt about for the unrecognised argument.
Swift FSM
Friendly Finite State Machine Syntax for Swift on macOS, iOS, tvOS and watchOS
Inspired by Uncle Bob’s SMC syntax, Swift FSM is a pure Swift DSL for declaring and operating a Finite State Machine (FSM).
This guide presumes some familiarity with FSMs and specifically the SMC syntax linked above. Swift FSM makes liberal use of
@resultBuilder
blocks, operator overloads, [callAsFunction()
][5], and [trailing closures][6], all in combination with one another - familiarity with these concepts will also be helpful.Contents
Requirements
Swift FSM is a Swift Package, importable through the Swift Package Manager, and requires macOS 13, iOS 16, tvOS 16 and watchOS 9, alongside Swift 5.7 or later. If you need support for older platforms, please check out the [backport][29] branch.
It has two dependencies - Apple’s [Algorithms][30], and ([in one small corner][31]) my own [Reflective Equality][32]
Basic Syntax
Borrowing from SMC, we will use the example of a subway turnstile system. This turnstile has two possible states:
Locked
, andUnlocked
, and two possible events:Coin
, andPass
.The logic is as follows (from Uncle Bob, emphasis added):
Following Uncle Bob’s examples, we will build up our table bit by bit to demonstrate the different syntactic possibilities of Swift FSM and how they compare to SMC:
SMC:
Swift FSM (with additional code for context):
The
SyntaxBuilder
protocol provides the methodsdefine
,when
, andthen
necessary to build the transition table. It has two associated types,State
andEvent
, which must beHashable
.FSM
is generic overState
andEvent
. As withSyntaxBuilder
,State
andEvent
must beHashable
. Here we have used anEnum
, specifying the initial state of the FSM as.locked
.fsm.buildTable
is a throwing function - though the type system will prevent various illogical statements, there are some issues that can only be detected at runtime.The
define
statement roughly corresponds to the ‘Given’ keyword in the natural language description of the FSM. It is expected however that you will only write onedefine
per state.define
takes two arguments - aState
instance, and a Swift@resultBuilder
block.As we are inside a
define
block, we take the.locked
state as a given. We can now list our transitions, with each line representing a single transition. In this case,when
we receive a.coin
event, we willthen
transition to the.unlocked
state and callunlock
.unlock
is a function, also declarable as follows:The
|
(pipe) operator binds transitions together. It feeds the output of the left hand side into the input of the right hand side, as you might expect in a terminal.The
FSM
instance will look up the appropriate transition for its current state, call the associated function, and transition to the associated next state. In this case, theFSM
will call theunlock
function and transition to theunlocked
state. If no transition is found, it will do nothing, and if compiled for debugging, will print a warning message.Optional Arguments
SMC:
Swift FSM:
then()
with no argument means ‘no change’, and the FSM will remain in the current state. The actions pipe is also optional - if a transition performs no actions, it can be omitted.Super States
SMC:
Swift FSM:
SuperState
takes the same@resultBuilder
asdefine
, however it does not take a starting state. The starting state is taken from thedefine
statement to which it is passed. PassingSuperState
instances to adefine
call will add the transitions declared in each of theSuperState
instances before the other transitions declared in thedefine
.If a
SuperState
instance is passed todefine
, the@resultBuilder
argument is optional.SuperState
instances themselves can adopt otherSuperState
instances, and will combine them together in the same way asdefine
:Overriding SuperStates
By default, transitions declared in a
SuperState
cannot be overridden by their adopters. The following code is therefore assumed to be accidental and throws:If you wish to override a
SuperState
transition, you must make this explicit using theoverride { }
block:The
override
block indicates to Swift FSM that any transitions contained within it override any inherited transitions with the same initial states and events.As multiple inheritance is allowed, overrides replace all matching transitions:
Without the
override
, this multiple inheritance would otherwise create duplicate transitions:If
override
is used where there is nothing to override, the FSM will throw:Writing
override
in the parent rather than the child will throw:Attempting to override within the same
SuperState { }
ordefine { }
will also throw:In this scope, the word override has no meaning and therefore is ignored by the error handler. What remains is therefore two duplicate transitions, resulting in an error.
Overriding Overrides
Overrides in Swift FSM follow the usual rules of inheritance. In a chain of overrides, it is the final transition in that chain that takes precedence:
Entry and Exit Actions
SMC:
Swift FSM:
onEntry
andonExit
are the final arguments todefine
and specify an array of entry and exit actions to be performed when entering or leaving the defined state. Note that these require array syntax rather than varargs, as a work around for limitations in Swift’s matching algorithm for functions that take multiple closure arguments.SuperState
instances can also accept entry and exit actions:SuperState
instances also inherit entry and exit actions from their superstates:Configuring Entry and Exit Actions Behaviour
In SMC, entry and exit actions are invoked even if the state does not change. In the example above, the unlock entry action would be called on all transitions into the
Unlocked
state, even if the FSM is already in theUnlocked
state.In contrast, Swift FSM’s default behaviour is to invoke entry and exit actions only if there is a state change. In the example above, this means that, in the
.unlocked
state, after a.coin
event,unlock
will not be called.This policy is configurable, by passing
.executeAlways
as the second argument toFSM.init
:This setting replicates SMC entry/exit action behaviour. The default is
.executeOnStateChangeOnly
and is not a required argument.Syntax Order
All statements must be made in the form
define { when | then | actions }
. See [Expanded Syntax][33] below for exceptions to this rule.Syntax Variations
Though
define
,when
, andthen
are functions, there are matching structs with equivalent capitalised names contained in theSwiftFSM.Syntax
namespace. You can therefore leverage Swift’stypealias
support to modify the syntax naming conventions to fit your use case.Here is one minimalistic example:
It you wish to use this alternative syntax, it is recommended (but not required) that you do not implement
SyntaxBuilder
.Syntactic Sugar
when
statements accept varargEvent
instances for convenience.Limitations of
@resultBuilder
ImplementationThe
@resultBuilder
blocks in SwiftFSM do not support control flow logic. Though is it possible to enable such logic, it would be misleading:If the
if/else
block were evaluated by the FSM at transition time, this would be a useful addition. However what we are doing inside these blocks is compiling our state transition table. The use ofif
andelse
in this manner is more akin to the conditional compilation statements#if/#else
- based on a value defined at compile time, only one transition or the other will be added to the table.If you do have a use for this kind of conditional compilation, please open an issue. See [Expanded Syntax][34] for alternative ways to evaluate conditional statements at transition time rather than compile time.
Runtime Errors
Important - most Swift FSM function calls and initialisers take additional parameters
file: String = #file
andline: Int = #line
. This is similar toXCTest
assertions, and allows Swift FSM to produce errors that pinpoint the location of problematic statement/s.As these cannot be hidden, please note that there are unlikely to be any circumstances in which it would be useful or necessary to override these default arguments with alternate values.
Empty Blocks
All blocks must contain at least one transition, otherwise an error will be thrown:
Duplicate Transitions
Transitions are duplicates if they share the same start state, event, and next state:
Logical Clashes
A logical clash occurs when transitions share the same start state and event, but their next states differ:
Though the two transitions are distinct from one another, logically they cannot co-exist - the
.coin
event must lead either to the.unlocked
state or to the.locked
state. It cannot lead to both.Duplicate
buildTable
CallsAdditional calls to
fsm.buildTable { }
will throw aTableAlreadyBuiltError
.NSObject Error
Swift FSM will throw an error if your
State
and/orEvent
types (or their children) inherit fromNSObject
.State
andEvent
instances are hashed to produce keys for the transitionDictionary
. These keys are then recreated and reused each timefsm.handleEvent
is called. This is not an issue for most Swift types, asHashable
conformance will have to be declared explicitly.NSObject
however already conforms toHashable
, and is hashed by instance identity, rather than by value. This would lead to a defunct transition table where all transition lookups fail, and therefore throws an error.This is an edge case and it is extremely unlikely that you will ever encounter this error. Nonetheless, the check is quite exhaustive - If you would like to know more about the mechanism involved, see [Reflective Equality][35].
Performance
Each call to
handleEvent()
requires a single operation to find the correct transition in the table. Though O(1) is ideal, this table-based system still has 2-3x the basic overhead of a nested switch case statement.Expanded Syntax
Whilst Swift FSM matches most of the syntax of SMC, it also introduces some new possibilities of its own. None of this additional syntax is required, and is provided purely for convenience.
Example
Let’s imagine an extension to our turnstile rules: under some circumstances, we want to enforce the ‘everyone pays’ rule by entering the alarming state if a
.pass
is detected when still in the.locked
state, yet in others, perhaps at rush hour, we want to be more permissive in order to avoid disruption to other passengers.We could implement a time of day check somewhere else in the system, perhaps inside the implementation of the
alarmOn
function to decide what the appropriate behaviour should be:But we now have some aspects of our state transition logic declared inside the transition table, and other aspects declared elsewhere.
Furthermore, we must transition to the
.alarming
state, regardless of theEnforcement
policy. But what if different policies called for different transitions altogether?An alternative might be to introduce extra events to differentiate between the new policies:
This allows us both to call different functions, and to transition to different states, depending on the enforcement policy, all whilst keeping all of our logic inside the transition table.
In order to make this change however, every transition that originally responded to the
.pass
event will need to be rewritten twice, once for each of the two new versions of this event, even if they are identical in both cases. In no time at all, the state transition table is going to become unmanageably long, and littered with duplication.The Swift FSM Solution
Here we have introduced a new keyword
matching
, and two new protocols,ExpandedSyntaxBuilder
andPredicate
.Given that we are in the
.locked
state:Enforcement
is.weak
, when we get a.pass
, transition to.locked
andsmile
Enforcement
is.strong
, when we get a.pass
, transition to.alarming
anddefconOne
Enforcement
, when we get a.coin
, transition to.unlocked
andunlock
In this system, only those statements that depend upon the
Enforcement
policy need know it has been added, and all other existing statements that do not depend upon it continue to work as they always did.ExpandedSyntaxBuilder and Predicate
ExpandedSyntaxBuilder
implementsSyntaxBuilder
, providing all the SMC-equivalent syntax, alongside the newmatching
statements for working with predicates.For the
Struct
based variant syntax, the equivalent namespace isSwiftFSM.Syntax.Expanded
.Predicate
requires the conformer to beHashable
andCaseIterable
. It is possible to use any type you wish, as long as your conformance toHashable
andCaseIterable
makes logical sense. In practice, this is likely to limitPredicates
toEnums
without associated types, as these can be automatically conformed toCaseIterable
.Implicit Matching Statements
In the above, no
Predicate
is specified, and its full meaning must therefore be inferred from context. The scope for contextual inference is the sum of the builder blocks for allSuperState
anddefine
calls insidefsm.buildTable { }
.In our example, the type
Enforcement
appears in amatching
statement elsewhere in the table, and Swift FSM will therefore infer the absentmatching
statement as follows:Transitions in Swift FSM are are therefore
Predicate
agnostic by default, matching any givenPredicate
unless otherwise specified. In this way,matching
is an optional modifier that constrains the transition to one or more specificPredicate
cases.Multiple Predicates
There is no limit on the number of
Predicate
types that can be used in one table (see [Predicate Performance][36] for practical limitations). The following (contrived and rather silly) expansion of the originalPredicate
example remains valid:The same inference rules also apply:
Compound Matching Statements
As seen in the above example, multiple predicates can be combined in a single
matching
statement, by using theand: Predicate...
andor: Predicate...
varargs arguments.In Swift FSM,
matching(and:)
means that we expect both predicates to be present at the same time, whereasmathing(or:)
means that we expect any and only one of them to be present.Swift FSM expects exactly one instance of each
Predicate
type present in the table to be passed to each call tohandleEvent
, as in the example above, wherefsm.handleEvent(.coin, predicates: A.x, B.x, C.x)
contains a single instance of typesA
,B
andC
. Accordingly,A.x AND A.y
should never occur - only one can be present. Therefore, predicates passed tomatching(and:)
must all be of a different type. This cannot be checked at compile time, and therefore throws at runtime if violated.In contrast,
matching(or:)
specifies multiple possibilities for a singlePredicate
. Predicates joined byor
must therefore all be of the same type, and attempting to pass differentPredicate
types tomatching(or:)
will not compile (see [Implicit Clashes][37] for more information on this limitation).Important - nested
matching
statements are combined by AND-ing them together, which makes it possible inadvertently to create a conflict.matching(or:)
statements are also combined using AND:Valid nested
matching(or:)
statements are combined as follows:Implicit Clashes
Between-Predicates Clashes
The two transitions above appear to be different from one another, until we reconsider the inference rules for multiple
Predicate
types:We can break the deadlock by disambiguating at least one of the statements:
In some cases, Swift FSM can break the deadlock without disambiguation:
Swift FSM defers to the statement that explicitly specifies the greatest number of predicates - in this case, the first statement
matching(Enforcement.weak, and: Reward.positive)
, which specifies two predicates, versus the second statement’s single predicatematching(Enforcement.weak)
.Within-Predicates Clashes
Following the inference logic, connecting different types using the word ‘or’ is not allowed:
If we were to call
handleEvent(.coin, predicates: Enforcement.weak, Reward.negative)
with such a table, there would be no reasonable way to decide which transition to perform. Unlike between-predicates implicit clashes, within-predicates clashes are eliminated through the type system.Deduplication
In this example,
when(.pass)
is duplicated. We can factor this out using a context block:The full example would now be:
then
andmatching
support context blocks in a similar way:The keyword
actions
is also available for function call context blocks:Chaining Blocks
Our context blocks divide into two groups - those that can be logically chained (or AND-ed) together, and those that cannot.
Discrete Blocks -
when
andthen
A transition responds to a single event and transitions to a single state. Therefore multiple
when { }
andthen { }
statements cannot be AND-ed together.Additionally, there is a specific combination of
when { }
andthen
that does not compile, as there is no situation where, in response to a single event (in this case,.coin
), there could then be a transition to more than one state, unless a differentPredicate
is given for each.Chainable Blocks -
matching
andactions
There is no logical restriction on the number of predicates or actions per transition, and therefore both can be built up in a chain as follows:
Nested
actions
blocks sum the actions and perform all of them. Nestedmatching
blocks are AND-ed together.Mixing blocks and pipes
Pipes can and must be used inside blocks, whereas blocks cannot be opened after pipes
Condition Statements
Using Predicates with
matching
syntax is a versatile solution, however in some cases it may bring more complexity than is necessary to solve a given problem (see [Predicate Performance][38] for a description ofmatching
overhead).If you need to make a specific transition conditional at runtime, then the
condition
statement may suffice. Some FSM implementations call this aguard
statement, however the namecondition
was chosen here asguard
is a reserved word in Swift.Here,
complexDecisionTree()
is a function that returns aBool
. If it istrue
, the transition is executed, and if it is not, nothing is executed.The keyword
condition
is syntactically interchangeable withmatching
- it works with pipe and block syntax, and is chainable (conditions are AND-ed together).matching
andcondition
blocks can also be combined freely:The disadvantage of
condition
versusmatching
is that it is more limited in the logic it can express:There is no way to distinguish different
condition
statements, as the() -> Bool
blocks are inherently opaque. From a logical evaluation point of view, they are invisible. What therefore remains is two statementsdefine(.locked) { when(.coin) | ... }
that both transition to different states - the FSM has no way to understand which one to call, and must thereforethrow
.Runtime Errors
In order to preserve performance,
fsm.handleEvent(event:predicates:)
performs no error handling. Therefore, passing inPredicate
instances that do not appear anywhere in the transition table will not error. Nonetheless, the FSM will be unable to perform any transitions, as it will not contain any statements that match the given, unexpectedPredicate
instance. It is the caller’s responsibility to ensure that the predicates passed tohandleEvent
and the predicates used in the transition table are of the same type and number.try fsm.buildTable { }
does perform error handling to make sure the table is syntactically and semantically valid. In particular, it ensures that allmatching
statements are valid, and that there are no duplicate transitions and no logical clashes between transitions.In addition to the runtime errors thrown by the basic syntax, the expanded syntax also throws the following errors:
Matching Error
There are two ways one might inadvertently create an invalid
matching
statement. The first is within a single statement:The second is when AND-ing multiple
matching
statements through the use of blocks:Implicit Clash Error
See [Implicit Clashes][39]
Predicate Performance
Overview: operations per function call for a table with 100 transitions, 3
Predicate
types, and 10 cases perPredicate
handleEvent
buildTable
FSM
Adding predicates has no effect on the performance of
handleEvent()
, but does affect the performance offsm.buildTransitions { }
. By default, the FSM preserveshandleEvent()
runtime performance by doing significant work ahead of time when creating the transition table, filling in missing transitions for all impliedPredicate
combinations.The performance of
fsm.buildTransitions { }
is dominated by this, assuming any predicates are used at all. Because all possible combinations of cases of all given predicates have to be calculated and filtered for each transition, performance is O(m^n*o) where m is the average number of cases per predicate, n is number ofPredicate
types and o is the number of transitions.Using three
Predicate
types with 10 cases each in a table with 100 transitions would therefore require 100,000 operations to compile. In most real-world use cases, this is unlikely to be a problem. If your table is particularly large (see overview above), Swift FSM provides a more performance-balanced alternative for such cases in the form of theLazyFSM
class.Note: there is no performance advantage to using the keyword
matching
in fewer versus more transitions in your transition tables. Once the wordmatching
is used once, and aPredicate
instance is passed tohandleEvent()
, the performance implications for the whole table will be as above.Lazy FSM
LazyFSM
does away with the look-ahead combinatorics algorithm described above. The result is smaller tables internally, and faster table compile time. The cost is at the call tohandleEvent()
where multiple lookup operations are now needed to find the correct transition.Performance of
handleEvent()
decreases from O(1) to O(n!), wheren
is the number ofPredicate
types used regardless of the number of cases. Inversely, performance ofbuildTable { }
increases from O(m^n*o) to O(n), where n is now the number of transitions.Using three
Predicate
types with 10 cases each in a table with 100 transitions would now require 100 operations to compile (down from 100,000 by a factor of 1000). Each call tohandleEvent()
would need to perform between 1 and3! + 1
or 7 operations (up from 1 by a factor of 1-7). Using more than threePredicate
types in this case is therefore not advisable.Overall
LazyFSM
saves a lot more operations than it costs, but that cost is paid at runtime for each transition, rather than as a one-off cost at compile time. In most cases,FSM
is likely to be the preferred solution, withLazyFSM
reserved for especially large numbers of transitions and/orPredicate
cases. If no predicates are used, both implementations exhibit similarly fast performance.Troubleshooting
Though Swift FSM runtime errors contain verbose descriptions of the problem, nothing can be done to help with disambiguating compile time errors.
First, familiarity with how
@resultBuilder
works, and the kinds of compile time errors it tends to generate will be very helpful in understanding the errors you may encounter. Almost all Swift FSM-specific compile time errors will be produced by unrecognised arguments to the aforementioned@resultBuilder
, and unrecognised arguments to the|
operator overloaded by Swift FSM.To help, here is a brief list of common errors you are likely to encounter if you try to build something that Swift FSM disallows at compile time:
Builder Issues
This is a common compile time error in
@resultBuilder
blocks. It will occur if you feed the block an argument that it does not support. It is useful to remember that each line in such a block is actually an argument fed to a static method.For example:
Here an
actions
block is given as an argument to the hidden static functionbuildExpression
on the@resultBuilder
supporting thebuildTable
function. Thedefine
statement has been skipped, andactions
returns a type not supported by this outer block, and therefore cannot compile.Pipe Issues
This is common in situations where an unsupported argument is passed to a pipe overload.
For example:
Here no
matching
and/orwhen
statement precede/s the call tothen(.locked)
. There is no|
overload that takes as its two arguments the output ofthen(.locked)
on the left, and the block() -> ()
on the right, and therefore cannot compile.The error unfortunately spits out some internal implementation details that cannot be hidden. Such unavoidable details are marked as such by their location inside the
Internal
namespace.It also produces a secondary error - as it cannot work out what the output of
then(.locked) | unlock
is, it declares that there is no overload available forbuildExpression
. Fix the underlying|
error and this error will also disappear.A personal favourite, from this:
The order of
when
andmatching
is inverted and not supported. This no different to the previous error, but the compiler interprets the problem differently. It selects a|
overload from an unrelated module and declares that it is being misused.The compiler cannot help identify which pipe in the chain is causing the problem. Often it’s simpler just to delete and rewrite the statement rather than trying to figure out what the complaint is.
Spurious Issues
This is the original example from [Entry and Exit Actions][40], with one small error inserted at the end. This may or may not produce an appropriate error next to the dodo:
What it will also do is generate multiple spurious errors and fixits in the
SuperState
declaration similar to this one:Ignore these errors, and if there is no other error shown, you may have to hunt about for the unrecognised argument.
[5]: //dnrops/swift-fsm/tree/master/ https:/github.com/apple/swift-evolution/blob/main/proposals/0253-callable.md [6]: https://docs.swift.org/swift-book/documentation/the-swift-programming-language/closures/#Trailing-Closures [7]: #requirements [8]: #basic-syntax [9]: #optional-arguments [10]: #super-states [11]: #entry-and-exit-actions [12]: #syntax-order [13]: #syntax-variations [14]: #syntactic-sugar [15]: #runtime-errors [16]: #performance [17]: #expanded-syntax [18]: #example [19]: #expandedsyntaxbuilder-and-predicate [20]: #implicit-matching-statements [21]: #multiple-predicates [22]: #implicit-clashes [23]: #deduplication [24]: #chaining-blocks [25]: #condition-statements [26]: #error-handling [27]: #predicate-performance [28]: #troubleshooting [29]: https://github.com/drseg/swift-fsm/tree/backport [30]: https://github.com/apple/swift-algorithms [31]: #nsobject-error [32]: https://github.com/drseg/reflective-equality [33]: #expanded-syntax [34]: #expanded-syntax [35]: https://github.com/drseg/reflective-equality [36]: #predicate-performance [37]: #implicit-clashes [38]: #predicate-performance [39]: #implicit-clashes [40]: #entry-and-exit-actions
[image-3]: //dnrops/swift-fsm/tree/master/ https:/img.shields.io/github/actions/workflow/status/drseg/swift-fsm/swift.yml [image-4]: https://img.shields.io/github/license/drseg/swift-fsm