fsm

README

go-fsm

A scriptable FSM library for Go

• Tengo language: fast and secure
• Scriptable functions: transition conditions, transition actions, state entry and exit actions
• Immutable values

Concepts

State Machines

A state machine is defined by

• A set of named states, and,
• An ordered list of transitions between states

States

A state is defined by:

• Name: a unique string identifier in the state machine
• Entry Action: a function that's executed when entering the state
• Exit Action: a function that's executed when exiting the state

Transitions

A transition is defined by:

• Src: the current state
• Dst: the next state
• Condition: a function that evaluates the condition
• Action: a function that's executed when the condition is fulfilled

Condition Functions

If condition function name is not specified (an empty space), the transition is considered as unconditional (always evalutes to true).

Condition functions in the script should take 3 arguments:

func(src, dst, v) {
    /* some logic */
    return some_value 
}

• src: the current state
• dst: the next state
• v: the data value (immutable)

The state machine use the returned value to determine the condition of the transition. E.g. condition is fulfilled if the value is truthy. In Tengo, the function that does not return anything is treated as if it returns undefined which is falsy.

Action Functions

Action functions in the script should take 3 arguments:

func(src, dst, v) {
    /* some logic */
    return some_value 
}

• src: the current state
• dst: the next state
• v: the data value (immutable)

The data value passed to action functions is immutable, but, the function may return a new value to change the data value for the future condition/action functions.

• If the function returns undefined (or does not return anything), the data value remains unmodified.
• If the function returns error objects (e.g. return error("some error")), the state machine stops and returns an error from StateMachine.Run function call.
• If the function returns a value of any other type, the data value of the state machine is changed to the returned value.

Input and Output

When running the state machine, user can pass an input data value that will be used by condition and action functions. The state machine will return the final output data value when there are no more transitions available.

Execution Flow

1. When the state machine starts, it's given an initial state and the input data.
2. The state machine evaluates a list of transitions that are defined with the current state as its src state. The state machine evaluates the transitions in the same order they were added (defined).
   1. If condition script is specified, the state machine runs the script to determines whether the condition is fulfilled or not.
   2. If condition script is not specified,
3. If one of the transition's condition is fulfilled, the state machine runs the action scripts:
   1. It runs exit action of the current state if it's defined.
   2. It runs action of the transition if it's defined.
   3. It runs entry action of the next state if it's defined.
4. If no transitions were fulfilled, the state machine stops and returns the final value.
5. Repeat from the step 2.

Example

Here's an example code for an FSM that tests if the input string is valid decimal numbers (e.g. 123.456) or not:

package main

import (
    "fmt"

    "github.com/d5/go-fsm"
)

var decimalsScript = []byte(`
fmt := import("fmt")

export {
	// test if the first character is a digit
	is_digit: func(src, dst, v) {
		return v[0] >= '0' && v[0] <= '9'
	},
	// test if the first character is a period
	is_dot: func(src, dst, v) {
		return v[0] == '.'  
	},
	// test if there are no more characters left
	is_eol: func(src, dst, v) {
		return len(v) == 0  
	},
	// prints out transition info
	print_tx: func(src, dst, v) {
		fmt.printf("%s -> %s: %q\n", src, dst, v)
	},
	// cut the first character
	enter: func(src, dst, v) {
		return v[1:]
	},
	enter_end: func(src, dst, v) {
		return "valid number"
	}, 
	enter_error: func(src, dst, v) {
		return "invalid number: " + v
	}
}`)

func main() {
    // build and compile state machine
    machine, err := fsm.New(decimalsScript).
        State("S", "enter", "").       // start
        State("N", "enter", "").       // whole numbers
        State("P", "enter", "").       // decimal point
        State("F", "enter", "").       // fractional part
        State("E", "enter_end", "").   // end
        State("X", "enter_error", ""). // error
        Transition("S", "E", "is_eol", "print_tx").
        Transition("S", "N", "is_digit", "print_tx").
        Transition("S", "X", "", "print_tx").
        Transition("N", "E", "is_eol", "print_tx").
        Transition("N", "N", "is_digit", "print_tx").
        Transition("N", "P", "is_dot", "print_tx").
        Transition("N", "X", "", "print_tx").
        Transition("P", "F", "is_digit", "print_tx").
        Transition("P", "X", "", "print_tx").
        Transition("F", "E", "is_eol", "print_tx").
        Transition("F", "F", "is_digit", "print_tx").
        Transition("F", "X", "", "print_tx").
        Compile()
    if err != nil {
        panic(err)
    }

    // test case 1: "123.456"
    res, err := machine.Run("S", "123.456")
    if err != nil {
        panic(err)
    }
    fmt.Println(res)

    // test case 2: "12.34.65"
    res, err = machine.Run("S", "12.34.56")
    if err != nil {
        panic(err)
    }
    fmt.Println(res)
}

Documentation

Overview

Package fsm provides a scriptable FSM library.

Example

package main

import (
	"math"

	"github.com/d5/go-fsm"
)

var script = []byte(`
fmt := import("fmt")

export {
	truthy: func(src, dst, v) { return !!v },
	falsy: func(src, dst, v) { return !v },
	action: func(src, dst, v) { fmt.printf("%s -> %s: %v\n", src, dst, v) },
	enter: func(src, dst, v) { fmt.printf("%s ->: %v\n", dst, v) },
	leave: func(src, dst, v) { fmt.printf("-> %s: %v\n", src, v) }
}
`)

func main() {
	machine, err := fsm.New(script).
		State("S", "enter", "leave").
		State("T", "enter", "leave").
		State("F", "enter", "leave").
		Transition("S", "T", "truthy", "action").
		Transition("S", "F", "falsy", "action").
		Compile()
	if err != nil {
		panic(err)
	}

	if _, err := machine.Run("S", 1); err != nil {
		panic(err)
	}
	if _, err := machine.Run("S", math.NaN()); err != nil {
		panic(err)
	}
	if _, err := machine.Run("S", "foobar"); err != nil {
		panic(err)
	}
	if _, err := machine.Run("S", []interface{}{}); err != nil {
		panic(err)
	}

}

Output:

-> S: 1
S -> T: 1
T ->: 1
-> S: NaN
S -> F: NaN
F ->: NaN
-> S: "foobar"
S -> T: "foobar"
T ->: "foobar"
-> S: []
S -> F: []
F ->: []

Example (Decimals)

package main

import (
	"fmt"

	"github.com/d5/go-fsm"
)

var decimalsScript = []byte(`
fmt := import("fmt")

export {
	// test if the first character is a digit
	is_digit: func(src, dst, v) {
		return v[0] >= '0' && v[0] <= '9'
	},
	// test if the first character is a period
	is_dot: func(src, dst, v) {
		return v[0] == '.'  
	},
	// test if there are no more characters left
	is_eol: func(src, dst, v) {
		return len(v) == 0  
	},
	// prints out transition info
	print_tx: func(src, dst, v) {
		fmt.printf("%s -> %s: %q\n", src, dst, v)
	},
	// cut the first character
	enter: func(src, dst, v) {
		return v[1:]
	},
	enter_end: func(src, dst, v) {
		return "valid number"
	}, 
	enter_error: func(src, dst, v) {
		return "invalid number: " + v
	}
}`)

func main() {
	// build and compile state machine
	machine, err := fsm.New(decimalsScript).
		State("S", "enter", "").       // start
		State("N", "enter", "").       // whole numbers
		State("P", "enter", "").       // decimal point
		State("F", "enter", "").       // fractional part
		State("E", "enter_end", "").   // end
		State("X", "enter_error", ""). // error
		Transition("S", "E", "is_eol", "print_tx").
		Transition("S", "N", "is_digit", "print_tx").
		Transition("S", "X", "", "print_tx").
		Transition("N", "E", "is_eol", "print_tx").
		Transition("N", "N", "is_digit", "print_tx").
		Transition("N", "P", "is_dot", "print_tx").
		Transition("N", "X", "", "print_tx").
		Transition("P", "F", "is_digit", "print_tx").
		Transition("P", "X", "", "print_tx").
		Transition("F", "E", "is_eol", "print_tx").
		Transition("F", "F", "is_digit", "print_tx").
		Transition("F", "X", "", "print_tx").
		Compile()
	if err != nil {
		panic(err)
	}

	// test case 1: "123.456"
	res, err := machine.Run("S", "123.456")
	if err != nil {
		panic(err)
	}
	fmt.Println(res)

	// test case 2: "12.34.65"
	res, err = machine.Run("S", "12.34.56")
	if err != nil {
		panic(err)
	}
	fmt.Println(res)

}

Output:

S -> N: "123.456"
N -> N: "23.456"
N -> N: "3.456"
N -> P: ".456"
P -> F: "456"
F -> F: "56"
F -> F: "6"
F -> E: ""
valid number
S -> N: "12.34.56"
N -> N: "2.34.56"
N -> P: ".34.56"
P -> F: "34.56"
F -> F: "4.56"
F -> X: ".56"
invalid number: .56

Index

• type Builder
  • func New(userScript []byte) *Builder
  • func (b *Builder) Compile() (*StateMachine, error)
  • func (b *Builder) State(name, entryFunc, exitFunc string) *Builder
  • func (b *Builder) Transition(src, dst, condition, action string) *Builder
  • func (b *Builder) Validate() error
  • func (b *Builder) ValidateCompile() (*StateMachine, error)
• type StateMachine
  • func (m *StateMachine) Run(src string, in interface{}) (out *tengo.Variable, err error)

Examples

• Package
• Package (Decimals)
• New

Types

type Builder

type Builder struct {
	// contains filtered or unexported fields
}

Builder represents a state machine builder that constructs and compiles the state machine. Call New to create a new Builder.

func New

func New(userScript []byte) *Builder

New creates a new Builder with a user script.

User script must export functions for all condition and actions of the state machine.

Example

var script = []byte(`
		fmt := import("fmt")

		export {
			truthy: func(src, dst, v) { return !!v },
			falsy: func(src, dst, v) { return !v },
			enter: func(src, dst, v) { fmt.printf("ENTER %v: %v\n", dst, v) },
			leave: func(src, dst, v) { fmt.printf("LEAVE %v: %v\n", src, v) }
		}`)

_ = fsm.New(script).
	State("S", "enter", "leave").
	State("T", "enter", "leave").
	State("F", "enter", "leave").
	Transition("S", "T", "truthy", "").
	Transition("S", "F", "falsy", "")

func (*Builder) Compile

func (b *Builder) Compile() (*StateMachine, error)

Compile compiles the script and builds the state machine. This function does not validate the states and transitions. Call Validate or ValidateCompile if you want to validate them.

func (*Builder) State

func (b *Builder) State(name, entryFunc, exitFunc string) *Builder

State defines a state with its entry/exit action function names.

Entry and exit action functions are optional, but, if specified, the function in the user script must take 3 arguments:

export {
  action_name: func(src, dst, v) {
    return some_value // optional
  }
}

For entry functions, 'src' is the previous state, and, 'dst' is entering state. For exit functions, 'src' is the leaving state, and, 'dst' is the next state. 'v' is the current data value of the state machine. 'v' itself is immutable, but, entry and exit action functions may return a new value to change it. If they don't return anything (or return 'undefined'), the value will not be changed. If it returns a Tengo error object, the state machine will stop and returns the error.

export {
  action_name: func(src, dst, v) {
    return error("an error occurred")
  }
}

func (*Builder) Transition

func (b *Builder) Transition(src, dst, condition, action string) *Builder

Transition defines (adds) a transition from 'src' to 'dst' states. It also takes the condition and action function names, which are optional. An empty condition function name makes the transition unconditional (which means the transition always evaluates to true). Condition function and action function must take 3 arguments:

export {
  action_name: func(src, dst, v) {
    return some_value // truthy or falsy
  }
}

'src' is the current state, and, 'dst' is next state of the transition. 'v' is the current data value of the state machine, and, 'v' is immutable. For condition functions, the truthiness (https://github.com/d5/tengo/blob/master/docs/runtime-types.md#objectisfalsy) of the returned value determines whether the condition is fulfilled or not. For action functions, they may return a new value to change it. If they don't return anything (or return 'undefined'), the value will not be changed. If it returns a Tengo error object, the state machine will stop and returns the error.

export {
  action_name: func(src, dst, v) {
    return error("an error occurred")
  }
}

func (*Builder) Validate

func (b *Builder) Validate() error

Validate validates all states and transitions. It ensures that all states are properly defined and all condition and action functions are exported from the user script.

func (*Builder) ValidateCompile

func (b *Builder) ValidateCompile() (*StateMachine, error)

ValidateCompile is combination of Validate and Compile functions. Call Compile if you don't need to validate the states and transitions.

type StateMachine

type StateMachine struct {
	// contains filtered or unexported fields
}

StateMachine represents a compiled state machine. Use Builder to construct and compile StateMachine.

func (*StateMachine) Run

func (m *StateMachine) Run(
	src string,
	in interface{},
) (out *tengo.Variable, err error)

Run executes the state machine from an initial state 'src' and an input data value 'in'. See https://github.com/d5/tengo/blob/master/docs/interoperability.md#type-conversion-table for data value conversions. Run continues to evaluate and move between states, until there are no more transitions available. When it stops, Run returns the final output value 'out' or an error 'err' if a script returned an error while executing.