hsm

README

hsm - Hierarchical State Machines in Go

Hsm is a Go language library for implementing hierarchical state machines.

The library implements a subset of UML state charts, with the following main features:

• Hierarchical states - child states can be nested inside parent states, inheriting their behaviors (transitions), while allowing for specialization. This is also known as "behavioral inheritance".
• State entry and exit actions.
• External, local, and internal transitions.
• Transition actions.
• Shallow and deep history transitions.
• Transition guard conditions.
• Type-safe extended state.
• PlantUML diagram generation.
• High-performance.

Quick Start

The following example illustrates most of the library features:

• Heater is turned on/off on entry to / exit from the Baking state.
• Light is turned on every time the oven is opened, and turned off when it's closed.
• Closing the door triggers transition to history state, which means we return to whichever state (Baking or Off) the oven was previously in. (Note that this is an over-simplification. Real world ovens can also be switched on/off while the door is open.)
• When the door is opened for 101st time, the oven breaks!

package hsm_test

import (
	"fmt"
	"github.com/dragomit/hsm"
	"github.com/stretchr/testify/assert"
	"testing"
)

func TestOven(t *testing.T) {

	// event types, enumerated as integers
	const (
		evOpen = iota
		evClose
		evBake
		evOff
	)

	// extended state will keep track of how many times the oven door was opened
	type eState struct {
		opened int
	}

	// Define state machine object which holds the state hierarchy.
	// State machine is parameterized by the extended state. In this case that's *eState.
	sm := hsm.StateMachine[*eState]{}

	// Actions are functions taking hsm.Event and extended state, and returning nothing.
	heatingOn := func(e hsm.Event, s *eState) { fmt.Println("Heating On") }
	heatingOff := func(e hsm.Event, s *eState) { fmt.Println("Heating Off") }
	lightOn := func(e hsm.Event, s *eState) { s.opened++; fmt.Println("Light On") }
	lightOff := func(e hsm.Event, s *eState) { fmt.Println("Light Off") }
	dying := func(e hsm.Event, s *eState) { fmt.Println("Giving up a ghost") }

	// Transition guards are functions taking hsm.Event and extended state, and returning bool.
	// Transition takes place if guard returns true.
	isBroken := func(e hsm.Event, s *eState) bool { return s.opened == 100 }
	isNotBroken := func(e hsm.Event, s *eState) bool { return !isBroken(e, s) }

	// Define the states, and assign them entry and exit actions as necessary
	// Also mark any states that are targets of automatic initial transitions.
	doorOpen := sm.State("Door Open").Entry("light_on", lightOn).Exit("light_off", lightOff).Build()
	doorClosed := sm.State("Door Closed").Initial().Build()
	baking := doorClosed.State("Baking").Entry("heating_on", heatingOn).Exit("heating_off", heatingOff).Build()
	off := doorClosed.State("Off").Initial().Build()

	// Define the transitions.
	doorClosed.Transition(evOpen, doorOpen).Guard("not broken", isNotBroken).Build()
	// Transition to nil state terminates the state machine.
	doorClosed.Transition(evOpen, nil).Guard("broken", isBroken).Action("dying", dying).Build()

	// When door is closed, we return to whichever state we were previously in.
	// We accomplish that using history transition (either deep or shallow history would work here).
	doorOpen.Transition(evClose, doorClosed).History(hsm.HistoryShallow).Build()
	baking.AddTransition(evOff, off)
	off.AddTransition(evBake, baking)

	// State machine must be finalized before it can be used.
	sm.Finalize()

	// Print PlantUML diagram for this state machine.
	evMapper := func(ev int) string {
		return []string{"open", "close", "bake", "off"}[ev]
	}
	fmt.Println(sm.DiagramPUML(evMapper))

	// Create an instance of this state machine.
	smi := hsm.StateMachineInstance[*eState]{SM: &sm, Ext: &eState{}}

	// Initialize the instance. The initial event is merely what's passed to the entry functions,
	// but is otherwise not delivered to the state machine. To drive this point home, we'll use
	// an invalid event id, and nil event data.
	smi.Initialize(hsm.Event{Id: -1, Data: nil})

	// confirm we transitioned to "off" state
	assert.Equal(t, off, smi.Current())

	smi.Deliver(hsm.Event{Id: evBake}) // prints "Heating On"
	assert.Equal(t, baking, smi.Current())

	smi.Deliver(hsm.Event{Id: evOpen}) // prints "Heating Off", "Light On"
	assert.Equal(t, doorOpen, smi.Current())

	smi.Deliver(hsm.Event{Id: evClose}) // prints "Light Off", "Heating On"
	assert.Equal(t, baking, smi.Current())

	// open and close 99 more times
	for i := 0; i < 99; i++ {
		smi.Deliver(hsm.Event{Id: evOpen})
		smi.Deliver(hsm.Event{Id: evClose})
	}
	assert.Equal(t, 100, smi.Ext.opened)
	assert.Equal(t, baking, smi.Current())

	// next time we open the door it should break, and state machine should terminate
	smi.Deliver(hsm.Event{Id: evOpen}) // prints "Giving up a ghost"
	// note: smi.Current() == nil
	// note: if any further events are delivered to the state machine, they will be ignored
}

Extended state

Extended state deals with any quantitative aspects of the object's state (as opposed to enumerable states). The state machine is parametrized by this type. Typically, extended state will be a pointer to a struct, although you are free to use other types.

sm := hsm.StateMachine[*eState]{}

If you don't need any extended state, use struct{}:

sm := hsm.StateMachine[struct{}]{}

Events

Events are represented by a struct containing event id and arbitrary event data:

type Event struct {
	Id int
	Data    any
}

The Id represents event type. For an event to be handled in a given state, you must specify a transition rule for that state and Id combination.

States

State machine must have at least one top-level state, and exactly one top-level state must be marked as the initial state. When initialized, state machine will automatically transition to this state.

States may form an arbitrarily deep hierarchy, with children states nested within the parent states. If state machine's initial state is a composite state, then exactly one of its substates must be marked as initial. This rule continues recursively, ensuring that once fully initialized, state machine will land in a leaf state.

Similarly, any composite state that's the target of a state transition must have exactly one of its substates marked as initial.

Once initialized, and after any event is delivered to the state machine and processed to completion, the state machine will be in a leaf state.

Event Delivery and State Transitions

When an event is delivered to the state machine, the configured transitions are searched for a matching transition - one satisfying these conditions:

• transition eventId matches the Id of the delivered event, and
• transition source state matches the current state or any of its ancestors, and
• transition has no guard condition, or guard condition is defined and evaluates to true

The search for a matching transition terminates on the first successful match, using the following search order:

• each substate is searched before its parent state, with the search starting at the current leaf state
• within a given state, transitions are searched in the order in which they were defined in the code

In this way we ensure that behavior defined in a super-state will apply to all its substates, but also that any substate can override the super-state's behavior.

If no matching transition is found, the event is silently ignored.

Run to Completion and the Order of Actions

Events are delivered to the state machine by invoking the StateMachineInstance.Deliver() method. Hsm follows the run-to-completion paradigm - by the time the Deliver() method returns, all state entry/exit and transition actions have been executed, and state machine is in its new leaf state.

External transitions

Each transition has:

• source state - state in which the transition is defined. If source state is a composite state, the transition will also apply to all its substates.
• target state - this is the target of the state transition.

source.Transition(evId, target).Action(...).Build()

The order of actions follows the UML specification:

• First the states are exited, starting with the current state, and going up to (but excluding) the lowest common ancestor (LCA) of the source and target states. State exit actions (if defined) are executed in the order in which the states are exited.
• Next, transition action (if defined) is executed.
• Next, states are entered, executing any defined entry actions, and landing in the transition target state.
• Finally, if the transition target is a composite state, the initial transitions are followed, eventually landing in a leaf state.

For example, in the state machine shown in the Quick Start section, delivering the "open" event while the state machine is in the "Baking" state will cause exiting "Baking" and "Door Closed" states and entering "Door Open" state. (In this case LCA is the implicit top-level state that contains the entire state machine.)

On the other hand, delivering the "off" event to the "Baking" state will exit "Baking" and enter "Off" state. (In this case, LCA is the "Door Closed" state.)

This transition semantics is known as external transitions. Hsm also supports internal and local transitions, which are described next.

Internal Transitions

Internal transitions don't involve any state changes or state entry/exit actions. To define an internal transition, set transition target to be the same as source, and mark the transition as internal:

baking.Transition(evChangeTemp, baking).Internal().Action(...).Build()

Without specifying internal transition semantics, the transition would be external. An external self-transition would result in leaving and re-entering the state.

An internal transition defined for a composite state will also apply to any of its (direct or transitive) substates, unless a substate overrides the behavior by specifying its own transition rule for the same event.

Local transitions

When source and target states stand in parent-child (or child-parent) relationship, the external transition semantics would involve leaving and re-entering the composite state. The alternative local transition semantics avoids this leaving/re-entering. For more details, see this Wikipedia entry.

parentState.Transition(evId, childState).Local(true).Action(...).Build()

To change the default behavior for the entire state machine to use local rather than external transitions (where applicable), set LocalDefault attribute of StateMachine to true:

sm := StateMachine[*eState]{LocalDefault: true}

State Machine Structure vs. Instances

StateMachine object captures the state chart structure: states, transitions, actions, and guards. Application should create a single StateMachine object (per each structurally different state chart), but it can create an arbitrary number of independent StateMachineInstance objects, all tied to the same StateMachine object.

sm := hsm.StateMachine[*eState]{}
state1 := hsm.State(...).Build()
...
sm.Finalize()

smi1 := hsm.StateMachineInstance[*eState]{SM: &sm, Ext: &eState{}}
smi2 := hsm.StateMachineInstance[*eState]{SM: &sm, Ext: &eState{}}
...

Typically, StateMachine object would be created and finalized during the program initialization, while the StateMachineInstance objects can be created as needed.

This separation between the state machine structure and instances minimizes the overhead of creating new instances.

Panic Early, not Often

State machine construction will panic when a structural error is detected:

• unspecified or over-specified initial state of the state machine
• composite state targeted by a transition with an unspecified or over-specified initial substate
• invalid internal or local transition specification

Furthermore, state machine will panic if an unfinished state or transition builder is detected. For example, consider the following code:

srcState.Transition(evId, targetState).Action(someAction) // forgotten .Build() call
sm.Finalize() // <-- panics at this point

Without invoking the final .Build() method, the transition is not installed. This could lead to a hard to find bug, which is why Finalize() will panic with an appropriate error message.

The rationale behind these design choices is that it is best to find bugs and raise errors as early as possible. Fixing structural errors requires changing code and re-compiling. Panicking early, during state machine construction helps smoke out the bugs and avoids unexpected errors much later, when state machine instances are used.

Concurrency and Re-entrancy

Methods involved in building the state machine structure are not safe for concurrent use by multiple goroutines.

Once StateMachine is finalized, it is effectively immutable and safe for concurrent use by multiple StateMachineInstances.

While different StateMachineInstances are independent of each other and can be used concurrently with each other, StateMachineInstance methods of any single instance are not safe for concurrent use.

Furthermore, StateMachineInstance.Deliver() is not re-entrant: it must not be called from within a transition action, state entry or exit function, or a transition guard function. If transition action needs to generate an event to be delivered to the state machine, this should be done by writing the event somewhere (channel, list, queue, etc) from where it can be picked up and delivered to the state machine after the currently executing StateMachineInstance.Deliver() method returns.

Finally, transition actions, state entry/exit functions and transition guards should not invoke StateMachineInstance.Current() method. If they do, the result will be undefined, and it may change in the future. The Current() method is only safe for use after the Deliver() method returns, and before the next Deliver() method is called.

PlantUML Diagram Generation

Once state machine is finalized, hsm can generate the corresponding PlantUML state diagram.

See Quick Start section for an example of a generated diagram.

PlantUML does pretty well with simple/shallow state machines, but struggles with graphs with deeply-nested states. Note also that PlantUML supports limited layout customization.

Documentation

Index

• type DiagramBuilder
  • func (db *DiagramBuilder[E]) Arrow(src, dst *State[E], arrow string) *DiagramBuilder[E]
  • func (db *DiagramBuilder[E]) Build() string
  • func (db *DiagramBuilder[E]) DefaultArrow(arrow string) *DiagramBuilder[E]
• type Event
• type History
• type State
  • func (s *State[E]) AddTransition(eventId int, target *State[E])
  • func (s *State[E]) IsLeaf() bool
  • func (s *State[E]) Name() string
  • func (s *State[E]) State(name string) *StateBuilder[E]
  • func (s *State[E]) String() string
  • func (s *State[E]) Transition(eventId int, target *State[E]) *TransitionBuilder[E]
• type StateBuilder
  • func (sb *StateBuilder[E]) Build() *State[E]
  • func (sb *StateBuilder[E]) Entry(name string, f func(Event, E)) *StateBuilder[E]
  • func (sb *StateBuilder[E]) Exit(name string, f func(Event, E)) *StateBuilder[E]
  • func (sb *StateBuilder[E]) Initial() *StateBuilder[E]
• type StateMachine
  • func (sm *StateMachine[E]) DiagramBuilder(evNameMapper func(int) string) *DiagramBuilder[E]
  • func (sm *StateMachine[E]) DiagramPUML(evNameMapper func(int) string) string
  • func (sm *StateMachine[E]) Finalize()
  • func (sm *StateMachine[E]) State(name string) *StateBuilder[E]
• type StateMachineInstance
  • func (smi *StateMachineInstance[E]) Current() *State[E]
  • func (smi *StateMachineInstance[E]) Deliver(e Event) (handled bool, src *State[E])
  • func (smi *StateMachineInstance[E]) Initialize(e Event)
• type TransitionBuilder
  • func (tb *TransitionBuilder[E]) Action(name string, f func(Event, E)) *TransitionBuilder[E]
  • func (tb *TransitionBuilder[E]) Build()
  • func (tb *TransitionBuilder[E]) Guard(name string, f func(Event, E) bool) *TransitionBuilder[E]
  • func (tb *TransitionBuilder[E]) History(h History) *TransitionBuilder[E]
  • func (tb *TransitionBuilder[E]) Internal() *TransitionBuilder[E]
  • func (tb *TransitionBuilder[E]) Local(b bool) *TransitionBuilder[E]

Types

type DiagramBuilder

type DiagramBuilder[E any] struct {
	// contains filtered or unexported fields
}

DiagramBuilder allows minor customizations of PlantUML diagram layout before building the diagram. To create a builder, use StateMachine.DiagramBuilder().

func (*DiagramBuilder[E]) Arrow

func (db *DiagramBuilder[E]) Arrow(src, dst *State[E], arrow string) *DiagramBuilder[E]

Arrow specifies the arrow style used for all transitions from src to dst state. See here for available arrow styles: https://crashedmind.github.io/PlantUMLHitchhikersGuide/layout/layout.html

func (*DiagramBuilder[E]) Build

func (db *DiagramBuilder[E]) Build() string

Build creates and returns PlantUML diagram as a string.

func (*DiagramBuilder[E]) DefaultArrow

func (db *DiagramBuilder[E]) DefaultArrow(arrow string) *DiagramBuilder[E]

DefaultArrow changes the arrow style used for transitions. The default is "-->".

type Event

type Event struct {
	Id   int
	Data any
}

Event instance are delivered to state machine, causing it to run actions and change states. Id identifies type of the event, while Data is an optional arbitrary type containing auxiliary event data.

type History

type History int

const (
	HistoryNone    History = 0
	HistoryShallow History = 1
	HistoryDeep    History = 2
)

type State

type State[E any] struct {
	// contains filtered or unexported fields
}

State is a leaf or composite state in a state machine. To create a top-level state in a state machine, use hsm.StateMachine.State method. To create a sub-state of a composite state, use hsm.State.State method. State (and its containing StateMachine) are parameterized by E - the extended state type. E is usually a pointer to a struct containing various quantitative aspects of the object's state, as opposed to the qualitative aspects captured through the state machine's discrete states. If you don't need an extended state, use struct{} for E.

func (*State[E]) AddTransition

func (s *State[E]) AddTransition(eventId int, target *State[E])

AddTransition is a convenience method, equivalent to calling s.Transition(eventId, target).Build().

func (*State[E]) IsLeaf

func (s *State[E]) IsLeaf() bool

func (*State[E]) Name

func (s *State[E]) Name() string

Name returns state's name

func (*State[E]) State

func (s *State[E]) State(name string) *StateBuilder[E]

State creates and returns a builder for building a nested sub-state.

func (*State[E]) String

func (s *State[E]) String() string

String returns state's name. It is a synonym for Name().

func (*State[E]) Transition

func (s *State[E]) Transition(eventId int, target *State[E]) *TransitionBuilder[E]

Transition creates and returns a builder for the transition from the current state into a target state. The transition is triggered by event with the given id. The returned builder can be used to further customize the transition, such as providing action, guard condition, and transition type. To indicate state machine termination, provide nil for target state.

type StateBuilder

type StateBuilder[E any] struct {
	// contains filtered or unexported fields
}

StateBuilder provides Fluent API for building new State.

func (*StateBuilder[E]) Build

func (sb *StateBuilder[E]) Build() *State[E]

Build builds and returns the new state.

func (*StateBuilder[E]) Entry

func (sb *StateBuilder[E]) Entry(name string, f func(Event, E)) *StateBuilder[E]

Entry sets func f as the entry action for the state being built. May be called multiple times to assign multiple entry actions, to be executed in the order of assignment.

func (*StateBuilder[E]) Exit

func (sb *StateBuilder[E]) Exit(name string, f func(Event, E)) *StateBuilder[E]

Exit sets func f as the exit action for the state being built. May be called multiple times to assign multiple exit actions, to be executed in the order of assignment.

func (*StateBuilder[E]) Initial

func (sb *StateBuilder[E]) Initial() *StateBuilder[E]

Initial marks the state being built as initial sub-state of the parent state. In other words, Initial creates an automatic initial transition from the parent state into the new state being built.

type StateMachine

type StateMachine[E any] struct {
	LocalDefault bool // default for whether transitions should be local
	// contains filtered or unexported fields
}

StateMachine encapsulates the structure of the entire state machine, along with all its contained states, transitions, actions, guards, etc. StateMachine is only about the structure - to create an instance, deliver events to it and drive it through transitions, create StateMachineInstance tied to this StateMachine. Zero value of StateMachine is ready for use. Do not copy a non-zero StateMachine.

func (*StateMachine[E]) DiagramBuilder

func (sm *StateMachine[E]) DiagramBuilder(evNameMapper func(int) string) *DiagramBuilder[E]

DiagramBuilder creates builder for customizing PlantUML diagram before building it. evNameMapper provides mapping of event ids to event names.

func (*StateMachine[E]) DiagramPUML

func (sm *StateMachine[E]) DiagramPUML(evNameMapper func(int) string) string

DiagramPUML builds a PlantUML diagram of a finalized state machine. This method is a shorthand for sm.DiagramBuilder(evNameMapper).Build().

func (*StateMachine[E]) Finalize

func (sm *StateMachine[E]) Finalize()

Finalize validates and finalizes the state machine structure. Finalize must be called before any state machine instances are initialized, and state machine structure must not be modified after this method is called.

func (*StateMachine[E]) State

func (sm *StateMachine[E]) State(name string) *StateBuilder[E]

State starts a builder for a top-level state in a state machine. There must be at least one top-level state in a state machine, and exactly one of those must be marked as initial state.

type StateMachineInstance

type StateMachineInstance[E any] struct {
	SM  *StateMachine[E]
	Ext E
	// contains filtered or unexported fields
}

StateMachineInstance is an instance of a particular StateMachine. StateMachineInstance receives events and goes through state transitions, executing actions along the way. Each StateMachineInstance should have its own, independent extended state, whose type is parameterized by E. Before using an instance, you must set the SM field to assign the instance to a finalized StateMachine. Prior to delivering any events to the instance, you must Initialize() it.

func (*StateMachineInstance[E]) Current

func (smi *StateMachineInstance[E]) Current() *State[E]

Current returns current (leaf) state, or nil if state machine has terminated. This method should not be invoked while state machine is processing an event. In other words, the result is not well-defined if invoked from within state entry/exit actions, transition actions, or transition guards.

func (*StateMachineInstance[E]) Deliver

func (smi *StateMachineInstance[E]) Deliver(e Event) (handled bool, src *State[E])

Deliver an event to the state machine, returning whether the event was handled, and in which state. Any applicable transitions and actions will be completed before the method returns. This method is not reentrant - do not invoke it from within transition actions, state entry/exit functions, or transition guard functions. If transition action needs to generate a new event, arrange for that event to be delivered to the instance only _after_ the current Deliver() method returns.

func (*StateMachineInstance[E]) Initialize

func (smi *StateMachineInstance[E]) Initialize(e Event)

Initialize initializes this instance. Before this method returns, state machine will enter its initial leaf state, invoking any relevant entry actions. The event e is passed into the entry actions as the initial event, but is otherwise not delivered to state machine.

type TransitionBuilder

type TransitionBuilder[E any] struct {
	// contains filtered or unexported fields
}

TransitionBuilder provides Fluent API for building transition from one state to another. TransitionBuilder allows specifying a guard condition that must be true for the transition to take place, an action to take when making the transition, and a type of transition (external, internal, local).

func (*TransitionBuilder[E]) Action

func (tb *TransitionBuilder[E]) Action(name string, f func(Event, E)) *TransitionBuilder[E]

Action specifies the transition action name and function. The transition action is invoked after any applicable state exit functions, and before any applicable state entry functions. Action name need not be unique, and is only used for state machine diagram generation. This method may be called multiple times to assign multiple actions to the same transition, to be executed in the order in which they were defined.

func (*TransitionBuilder[E]) Build

func (tb *TransitionBuilder[E]) Build()

Build completes building the transition

func (*TransitionBuilder[E]) Guard

func (tb *TransitionBuilder[E]) Guard(name string, f func(Event, E) bool) *TransitionBuilder[E]

Guard specifies the guard condition - a function that must return true for the transition to take place. Guard name need not be unique, and is only used for state machine diagram generation.

func (*TransitionBuilder[E]) History

func (tb *TransitionBuilder[E]) History(h History) *TransitionBuilder[E]

History specifies that transition shall occur into the (shallow or deep) history of the target composite state. In case the system has not yet visited the composite state, the transition will proceed into the composite state's initial sub-state.

func (*TransitionBuilder[E]) Internal

func (tb *TransitionBuilder[E]) Internal() *TransitionBuilder[E]

Internal specifies that transition should be treated as an internal transition, as opposed to the default external transition. This can only be specified for self-transitions - i.e. target state must be the same as the source state, or other the method will panic. Internal transitions differ from external transitions in that no entry or exit functions are invoked. Internal transitions specified in composite-states will be inherited by all the sub-states, unless explicitly overriden.

func (*TransitionBuilder[E]) Local

func (tb *TransitionBuilder[E]) Local(b bool) *TransitionBuilder[E]

Local specifies whether the transition should be treated as local or external, overriding the default for the state machine. This can only be specified for transitions between composite state and one of its (direct or transitive) sub-states, because the concept of local transitions does not make sense otherwise. Local transitions differ from the external ones in that they do not feature exit and re-entry from the parent (composite) state.