cockroach: github.com/cockroachdb/cockroach/pkg/util/fsm Index | Examples | Files

package fsm

import "github.com/cockroachdb/cockroach/pkg/util/fsm"

Package fsm provides an interface for defining and working with finite-state machines.

The package is split into two main types: Transitions and Machine. Transitions is an immutable State graph with Events acting as the directed edges between different States. The graph is built by calling Compile on a Pattern, which is meant to be done at init time. This pattern is a mapping from current States to Events that may be applied on those states to resulting Transitions. The pattern supports pattern matching on States and Events using wildcards and variable bindings. To add new transitions to the graph, simply adjust the Pattern provided to Compile. Transitions are not used directly after creation, instead, they're used by Machine instances.

Machine is an instantiation of a finite-state machine. It is given a Transitions graph when it is created to specify its State graph. Since the Transition graph is itself state-less, multiple Machines can be powered by the same graph simultaneously. The Machine has an Apply(Event) method, which applies the provided event to its current state. This does two things: 1. It may move the current State to a new State, according to the Transitions

graph.

2. It may apply an Action function on the Machine's ExtendedState, which is

extra state in a Machine that does not contribute to state transition
decisions, but that can be affected by a state transition.

See example_test.go for a full working example of a state machine with an associated set of states and events.

This package encourages the Pattern to be declared as a map literal. When declaring this literal, be careful to not declare two equal keys: they'll result in the second overwriting the first with no warning because of how Go deals with map literals. Note that keys that are not technically equal, but where one is a superset of the other, will work as intended. E.g. the following is permitted:

Compile(Pattern{
  stateOpen{retryIntent: Any} {
    eventTxnFinish{}: {...}
  }
  stateOpen{retryIntent: True} {
    eventRetriableErr{}: {...}
  }

Members of this package are accessed frequently when implementing a state machine. For that reason, it is encouraged to dot-import this package in the file with the transitions Pattern. The respective file should be kept small and named <name>_fsm.go; our linter doesn't complain about dot-imports in such files.

Index

Examples

Package Files

debug.go doc.go fsm.go match.go

type Args Uses

type Args struct {
    Ctx context.Context

    Prev     State
    Extended ExtendedState

    Event   Event
    Payload EventPayload
}

Args is a structure containing the arguments passed to Transition.Action.

type Bool Uses

type Bool interface {

    // Get returns the value of a Bool.
    Get() bool
    // contains filtered or unexported methods
}

Bool represents a boolean pattern.

var (
    // True is a pattern that matches true booleans.
    True Bool = b(true)
    // False is a pattern that matches false booleans.
    False Bool = b(false)
    // Any is a pattern that matches any value.
    Any = Var("")
)

func FromBool Uses

func FromBool(val bool) Bool

FromBool creates a Bool from a Go bool.

type Event Uses

type Event interface {
    Event()
}

Event is something that happens to a Machine which may or may not trigger a state transition.

type EventPayload Uses

type EventPayload interface{}

EventPayload is extra payload on an Event that does not contribute to state transition decisions, but that can be affected by a state transition. The interface is provided as part of the Args passed to Action after being given to a Machine during a call to ApplyWithPayload.

type ExtendedState Uses

type ExtendedState interface{}

ExtendedState is extra state in a Machine that does not contribute to state transition decisions, but that can be affected by a state transition. The interface is provided as part of the Args passed to Action after being given to a Machine during construction.

type Machine Uses

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

Machine encapsulates a State with a set of State transitions. It reacts to Events, adjusting its internal State according to its Transition graph and perforing actions on its ExtendedState accordingly.

Code:

ctx := context.Background()

var e executor
e.m = MakeMachine(txnStateTransitions, stateNoTxn{}, &e)
_ = e.m.Apply(ctx, eventTxnStart{})
_ = e.m.Apply(ctx, eventNoTopLevelTransition{True})
_ = e.m.Apply(ctx, eventRetriableErr{False, False})
_ = e.m.Apply(ctx, eventTxnRestart{})
_ = e.m.Apply(ctx, eventTxnFinish{})
fmt.Print(e.log.String())

Output:

Open...
Make Open
Wait for restart
Restarting
Finish...

func MakeMachine Uses

func MakeMachine(t Transitions, start State, es ExtendedState) Machine

MakeMachine creates a new Machine.

func (*Machine) Apply Uses

func (m *Machine) Apply(ctx context.Context, e Event) error

Apply applies the Event to the state Machine.

func (*Machine) ApplyWithPayload Uses

func (m *Machine) ApplyWithPayload(ctx context.Context, e Event, b EventPayload) (err error)

ApplyWithPayload applies the Event to the state Machine, passing along the EventPayload to the state transition's Action function.

func (*Machine) CurState Uses

func (m *Machine) CurState() State

CurState returns the current state.

type Pattern Uses

type Pattern map[State]map[Event]Transition

Pattern is a mapping from (State,Event) pairs to Transitions. When unexpanded, it may contain values like wildcards and variable bindings.

type State Uses

type State interface {
    State()
}

State is a node in a Machine's transition graph.

type Transition Uses

type Transition struct {
    Next   State
    Action func(Args) error
    // Description, if set, is reflected in the DOT diagram.
    Description string
}

Transition is a Machine's response to an Event applied to a State. It may transition the machine to a new State and it may also perform an action on the Machine's ExtendedState.

type TransitionNotFoundError Uses

type TransitionNotFoundError struct {
    State State
    Event Event
}

TransitionNotFoundError is returned from Machine.Apply when the Event cannot be applied to the current State.

func (TransitionNotFoundError) Error Uses

func (e TransitionNotFoundError) Error() string

type Transitions Uses

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

Transitions is a set of expanded state transitions generated from a Pattern, forming a State graph with Events acting as the directed edges between different States.

A Transitions graph is immutable and is only useful when used to direct a Machine. Because of this, multiple Machines can be instantiated using the same Transitions graph.

func Compile Uses

func Compile(p Pattern) Transitions

Compile creates a set of state Transitions from a Pattern. This is relatively expensive so it's expected that Compile is called once for each transition graph and assigned to a static variable. This variable can then be given to MakeMachine, which is cheap.

func (Transitions) GetExpanded Uses

func (t Transitions) GetExpanded() Pattern

GetExpanded returns the expanded map of transitions.

func (Transitions) WriteDotGraph Uses

func (t Transitions) WriteDotGraph(w io.Writer, start State)

WriteDotGraph writes a representaWriteDotGraphStringtion of the Transitions graph in the graphviz dot format. It accepts a starting State that will be expressed as such in the graph, if provided.

Code:

txnStateTransitions.WriteDotGraph(os.Stdout, stateNoTxn{})

Output:

digraph finite_state_machine {
	rankdir=LR;

	node [shape = doublecircle]; "NoTxn{}";
	node [shape = point ]; qi
	qi -> "NoTxn{}";

	node [shape = circle];
	"Aborted{RetryIntent:false}" -> "Aborted{RetryIntent:false}" [label = "NoTopLevelTransition{RetryIntent:false}"]
	"Aborted{RetryIntent:false}" -> "Aborted{RetryIntent:false}" [label = "NonRetriableErr{IsCommit:false}"]
	"Aborted{RetryIntent:false}" -> "Aborted{RetryIntent:false}" [label = "NonRetriableErr{IsCommit:true}"]
	"Aborted{RetryIntent:false}" -> "NoTxn{}" [label = "TxnFinish{}"]
	"Aborted{RetryIntent:false}" -> "Open{RetryIntent:false}" [label = "TxnStart{}"]
	"Aborted{RetryIntent:true}" -> "Aborted{RetryIntent:true}" [label = "NoTopLevelTransition{RetryIntent:false}"]
	"Aborted{RetryIntent:true}" -> "Aborted{RetryIntent:true}" [label = "NonRetriableErr{IsCommit:false}"]
	"Aborted{RetryIntent:true}" -> "Aborted{RetryIntent:true}" [label = "NonRetriableErr{IsCommit:true}"]
	"Aborted{RetryIntent:true}" -> "NoTxn{}" [label = "TxnFinish{}"]
	"Aborted{RetryIntent:true}" -> "Open{RetryIntent:true}" [label = "TxnStart{}"]
	"NoTxn{}" -> "NoTxn{}" [label = <NoTopLevelTransition{RetryIntent:false}<BR/><I>my test transition</I>>]
	"NoTxn{}" -> "Open{RetryIntent:false}" [label = "TxnStart{}"]
	"Open{RetryIntent:false}" -> "Open{RetryIntent:false}" [label = "NoTopLevelTransition{RetryIntent:false}"]
	"Open{RetryIntent:false}" -> "Open{RetryIntent:true}" [label = "NoTopLevelTransition{RetryIntent:true}"]
	"Open{RetryIntent:false}" -> "Aborted{RetryIntent:false}" [label = "NonRetriableErr{IsCommit:false}"]
	"Open{RetryIntent:false}" -> "NoTxn{}" [label = "NonRetriableErr{IsCommit:true}"]
	"Open{RetryIntent:false}" -> "Aborted{RetryIntent:false}" [label = "RetriableErr{CanAutoRetry:false, IsCommit:false}"]
	"Open{RetryIntent:false}" -> "Aborted{RetryIntent:false}" [label = "RetriableErr{CanAutoRetry:false, IsCommit:true}"]
	"Open{RetryIntent:false}" -> "Open{RetryIntent:false}" [label = "RetriableErr{CanAutoRetry:true, IsCommit:false}"]
	"Open{RetryIntent:false}" -> "Open{RetryIntent:false}" [label = "RetriableErr{CanAutoRetry:true, IsCommit:true}"]
	"Open{RetryIntent:false}" -> "NoTxn{}" [label = "TxnFinish{}"]
	"Open{RetryIntent:true}" -> "Open{RetryIntent:true}" [label = "NoTopLevelTransition{RetryIntent:false}"]
	"Open{RetryIntent:true}" -> "Aborted{RetryIntent:true}" [label = "NonRetriableErr{IsCommit:false}"]
	"Open{RetryIntent:true}" -> "NoTxn{}" [label = "NonRetriableErr{IsCommit:true}"]
	"Open{RetryIntent:true}" -> "RestartWait{}" [label = "RetriableErr{CanAutoRetry:false, IsCommit:false}"]
	"Open{RetryIntent:true}" -> "NoTxn{}" [label = "RetriableErr{CanAutoRetry:false, IsCommit:true}"]
	"Open{RetryIntent:true}" -> "Open{RetryIntent:true}" [label = "RetriableErr{CanAutoRetry:true, IsCommit:false}"]
	"Open{RetryIntent:true}" -> "Open{RetryIntent:true}" [label = "RetriableErr{CanAutoRetry:true, IsCommit:true}"]
	"Open{RetryIntent:true}" -> "NoTxn{}" [label = "TxnFinish{}"]
	"RestartWait{}" -> "RestartWait{}" [label = "NoTopLevelTransition{RetryIntent:false}"]
	"RestartWait{}" -> "Aborted{RetryIntent:true}" [label = "NonRetriableErr{IsCommit:false}"]
	"RestartWait{}" -> "Aborted{RetryIntent:true}" [label = "NonRetriableErr{IsCommit:true}"]
	"RestartWait{}" -> "NoTxn{}" [label = "TxnFinish{}"]
	"RestartWait{}" -> "Open{RetryIntent:true}" [label = "TxnRestart{}"]
}

func (Transitions) WriteDotGraphString Uses

func (t Transitions) WriteDotGraphString(w io.Writer, start string)

WriteDotGraphString is like WriteDotGraph, but takes the string representation of the start State.

func (Transitions) WriteReport Uses

func (t Transitions) WriteReport(w io.Writer)

WriteReport writes a report of the Transitions graph, reporting on which Events each State handles and which Events each state does not.

Code:

txnStateTransitions.WriteReport(os.Stdout)

Output:

Aborted{RetryIntent:false}
	handled events:
		NoTopLevelTransition{RetryIntent:false}
		NonRetriableErr{IsCommit:false}
		NonRetriableErr{IsCommit:true}
		TxnFinish{}
		TxnStart{}
	missing events:
		NoTopLevelTransition{RetryIntent:true}
		RetriableErr{CanAutoRetry:false, IsCommit:false}
		RetriableErr{CanAutoRetry:false, IsCommit:true}
		RetriableErr{CanAutoRetry:true, IsCommit:false}
		RetriableErr{CanAutoRetry:true, IsCommit:true}
		TxnRestart{}
Aborted{RetryIntent:true}
	handled events:
		NoTopLevelTransition{RetryIntent:false}
		NonRetriableErr{IsCommit:false}
		NonRetriableErr{IsCommit:true}
		TxnFinish{}
		TxnStart{}
	missing events:
		NoTopLevelTransition{RetryIntent:true}
		RetriableErr{CanAutoRetry:false, IsCommit:false}
		RetriableErr{CanAutoRetry:false, IsCommit:true}
		RetriableErr{CanAutoRetry:true, IsCommit:false}
		RetriableErr{CanAutoRetry:true, IsCommit:true}
		TxnRestart{}
NoTxn{}
	handled events:
		NoTopLevelTransition{RetryIntent:false}
		TxnStart{}
	missing events:
		NoTopLevelTransition{RetryIntent:true}
		NonRetriableErr{IsCommit:false}
		NonRetriableErr{IsCommit:true}
		RetriableErr{CanAutoRetry:false, IsCommit:false}
		RetriableErr{CanAutoRetry:false, IsCommit:true}
		RetriableErr{CanAutoRetry:true, IsCommit:false}
		RetriableErr{CanAutoRetry:true, IsCommit:true}
		TxnFinish{}
		TxnRestart{}
Open{RetryIntent:false}
	handled events:
		NoTopLevelTransition{RetryIntent:false}
		NoTopLevelTransition{RetryIntent:true}
		NonRetriableErr{IsCommit:false}
		NonRetriableErr{IsCommit:true}
		RetriableErr{CanAutoRetry:false, IsCommit:false}
		RetriableErr{CanAutoRetry:false, IsCommit:true}
		RetriableErr{CanAutoRetry:true, IsCommit:false}
		RetriableErr{CanAutoRetry:true, IsCommit:true}
		TxnFinish{}
	missing events:
		TxnRestart{}
		TxnStart{}
Open{RetryIntent:true}
	handled events:
		NoTopLevelTransition{RetryIntent:false}
		NonRetriableErr{IsCommit:false}
		NonRetriableErr{IsCommit:true}
		RetriableErr{CanAutoRetry:false, IsCommit:false}
		RetriableErr{CanAutoRetry:false, IsCommit:true}
		RetriableErr{CanAutoRetry:true, IsCommit:false}
		RetriableErr{CanAutoRetry:true, IsCommit:true}
		TxnFinish{}
	missing events:
		NoTopLevelTransition{RetryIntent:true}
		TxnRestart{}
		TxnStart{}
RestartWait{}
	handled events:
		NoTopLevelTransition{RetryIntent:false}
		NonRetriableErr{IsCommit:false}
		NonRetriableErr{IsCommit:true}
		TxnFinish{}
		TxnRestart{}
	missing events:
		NoTopLevelTransition{RetryIntent:true}
		RetriableErr{CanAutoRetry:false, IsCommit:false}
		RetriableErr{CanAutoRetry:false, IsCommit:true}
		RetriableErr{CanAutoRetry:true, IsCommit:false}
		RetriableErr{CanAutoRetry:true, IsCommit:true}
		TxnStart{}

type Var Uses

type Var string

Var allows variables to be bound to names and used in the match expression. If the variable binding name is the empty string, it acts as a wildcard but does not add any variable to the expression scope.

func (Var) Get Uses

func (Var) Get() bool

Get is part of the Bool interface.

Package fsm imports 7 packages (graph) and is imported by 7 packages. Updated 2019-11-06. Refresh now. Tools for package owners.