# Lock-free state machine

I've written a lock-free state machine in go and I would love to receive some feedback on it.

Writing this library my main concerns are keeping it lock-free and very light-weight (no bells and whistles like hooks and such).

Because this is lock-free I had to use atomic.CompareAndSwap which meant that the underlining state had to be a number, I choose unsigned because I saw no reason for a negative state, and I choose uint32 because it was the smallest CompareAndSwap operand available.

Later I added an option to label each state via an option function that can be passed to the initialization function.

The initial state defaults to 0 (zero value of uint32), but it too can be changed via an option function.

option functions are not exported because they should only be used during initialization.

There are 2 ways of changing the current state Transition(...) and TransitionFrom(...). Transition uses the current state as the source node. And with TransitionFrom(...) you provide both source and destination nodes.
Providing the source node is important if you can get to the destination node from more than one source, and you want to make sure that the source was a specific node.

package lfsm

import (
"fmt"
"strconv"
"sync/atomic"
)

type transition struct {
src, dst uint32
stateNames StateNameMap
}

type transitionMap map[uint32]map[uint32]bool

type State struct {
current     uint32
transitions transitionMap
stateNames  StateNameMap
initial     uint32
}

// Current returns the current state.
func (s *State) Current() uint32 {
}

// CurrentName returns the alias for the current state.
// If no alias is defined, the state integer will be returned in its string version.
func (s *State) CurrentName() string {
}

// TransitionFrom tries to change the state.
// Returns an error if the transition failed.
func (s *State) TransitionFrom(src, dst uint32) error {
if _, ok := s.transitions[src][dst]; !ok {
return &InvalidTransitionError{src, dst, s.stateNames}
}
if !atomic.CompareAndSwapUint32(&s.current, src, dst) {
return &TransitionError{src, dst, s.stateNames}
}
return nil
}

// Transition tries to change the state.
// It uses the current state as the source state, if you want to specify the source state use TransitionFrom instead.
// Returns an error if the transition failed.
func (s *State) Transition(dst uint32) error {
}

// NewState creates a new State Machine.
func NewState(m Constraints, opts ...option) *State {
s := State{
transitions: make(transitionMap, len(m)),
stateNames: make(StateNameMap, len(m)),
}

for src, dsts := range m {
s.transitions[src] = make(map[uint32]bool)
for _, dst := range dsts {
s.transitions[src][dst] = true
}
}

for _,o := range opts {
o.apply(&s)
}

return &s
}

// Constraints defines the possible transition for this state machine.
//
// The map keys describe the source states, and their values are the valid target destinations.
type Constraints map[uint32][]uint32

// StateNameMap holds a mapping between the state (in its integer form) to its alias.
type StateNameMap map[uint32]string
func (m StateNameMap) find(v uint32) string {
name, ok := m[v]
if !ok {
name = strconv.Itoa(int(v))
}
return name
}

// Can be used to alter the state struct during initialization.
type option func(s *State)

// InitialState sets the initial state of the state machine
func InitialState(v uint32) option {
return func(s *State) {
s.initial = v
s.current = v
}
}

// StateName sets an alias to a state integer.
func StateName(v uint32, name string) option {
return func(s *State) {
s.stateNames[v] = name
}
}

// StateNames is like StateName but sets aliases to multiple state integers.
func StateNames(m StateNameMap) option {
return func(s *State) {
for v,name := range m {
s.stateNames[v] = name
}
}
}

type TransitionError transition

func (f TransitionError) Error() string {
return fmt.Sprintf("transition failed (%s -> %s)", f.stateNames.find(f.src), f.stateNames.find(f.dst))
}

type InvalidTransitionError TransitionError

func (f InvalidTransitionError) Error() string {
return fmt.Sprintf("invalid transition (%s -> %s)", f.stateNames.find(f.src), f.stateNames.find(f.dst))
}

• What's the reason behind making transition functions, saving them in a map, and then retrieving and calling them? Is that so you're able to "decorate" them (to add functionality)? Otherwise you could just do the thing directly in TransitionFrom, and use a map of bools or something like that to know which transitions are allowed. – kyrill Dec 8 '19 at 5:50
• @kyrill the reason it's that when i started this code, I thought that calling transition will also return a map of available transitions. Later I decided to remove this functionality but kept the construction. I think I'll take your advice and switch to a map of booleans. – Eyal Dec 8 '19 at 8:51