ryanfaerman / fsm

A simple finite state machine for Golang

FSM

FSM provides a lightweight finite state machine for Golang. It runs allows any number of transition checks you'd like the it runs them in parallel. It's tested and benchmarked too.

Install

go get github.com/ryanfaerman/fsm

Usage

package main

import (
    "log"
    "fmt"
    "github.com/ryanfaerman/fsm"
)

type Thing struct {
    State fsm.State

    // our machine cache
    machine *fsm.Machine
}

// Add methods to comply with the fsm.Stater interface
func (t *Thing) CurrentState() fsm.State { return t.State }
func (t *Thing) SetState(s fsm.State)    { t.State = s }

// A helpful function that lets us apply arbitrary rulesets to this
// instances state machine without reallocating the machine. While not
// required, it's something I like to have.
func (t *Thing) Apply(r *fsm.Ruleset) *fsm.Machine {
    if t.machine == nil {
        t.machine = &fsm.Machine{Subject: t}
    }

    t.machine.Rules = r
    return t.machine
}

func main() {
    var err error

    some_thing := Thing{State: "pending"} // Our subject
    fmt.Println(some_thing)

    // Establish some rules for our FSM
    rules := fsm.Ruleset{}
    rules.AddTransition(fsm.T{"pending", "started"})
    rules.AddTransition(fsm.T{"started", "finished"})

    err = some_thing.Apply(&rules).Transition("started")
    if err != nil {
        log.Fatal(err)
    }

    fmt.Println(some_thing)
}

Note: FSM makes no effort to determine the default state for any ruleset. That's your job.

The Apply(r *fsm.Ruleset) *fsm.Machine method is absolutely optional. I like having it though. It solves a pretty common problem I usually have when working with permissions - some users aren't allowed to transition between certain states.

Since the rules are applied to the the subject (through the machine) I can have a simple lookup to determine the ruleset that the subject has to follow for a given user. As a result, I rarely need to use any complicated guards but I can if need be. I leave the lookup and the maintaining of independent rulesets as an exercise of the user.

Benchmarks

Golang makes it easy enough to benchmark things... why not do a few general benchmarks?

$ go test -bench=.
PASS
BenchmarkRulesetParallelGuarding      100000   13163 ns/op
BenchmarkRulesetTransitionPermitted  1000000    1805 ns/op
BenchmarkRulesetTransitionDenied    10000000     284 ns/op
BenchmarkRulesetRuleForbids          1000000    1717 ns/op
ok    github.com/ryanfaerman/fsm 14.864s

I think that's pretty good. So why do I go through the trouble of running the guards in parallel? Consider the benchmarks below:

$ go test -bench=.
PASS
BenchmarkRulesetParallelGuarding    100000       13261 ns/op
ok  github.com/ryanfaerman/fsm 1.525s


$ go test -bench=.
PASS
BenchmarkRulesetSerialGuarding         1  1003140956 ns/op
ok  github.com/ryanfaerman/fsm 1.007s

For the Parallel vs Serial benchmarks I had a guard that slept for 1 second. While I don't imagine most guards will take that long, the point remains true. Some guards will be comparatively slow -- they'll be accessing the database or consulting with some other outside service -- and why not get an answer back as soon as possible?

fsm's Issues

Transition Race Condition

Hey there,

I was taking a look at how your library was written and noticed that your transitions were not serialized using a mutex. I figured this would mean that your library would fail in cases where it shouldn't.

When I managed to reproduce it in testing, the failure was a bit more explosive than I thought it would be. When I wrote the test, I expected one of the goroutines would either: A) Fail with an InvalidTransition, B) Fail with the state being unexpected. However, both goroutines reported an InvalidTransition error, while only one reported that the state was incorrect. At first-pass, I can't explain why both goroutines ended up getting an InvalidTransition error. It would seem to confirm the race condition.

Here is the diff and then the test output. The output shows two errors getting returned from Transition, when really one should do it.

diff --git a/fsm_test.go b/fsm_test.go
index 8a9fec0..f08dfb8 100644
--- a/fsm_test.go
+++ b/fsm_test.go
@@ -1,6 +1,9 @@
 package fsm_test

 import (
+   "fmt"
+   "runtime"
+   "sync"
    "testing"
    "time"

@@ -91,6 +94,59 @@ func TestMachineTransition(t *testing.T) {
    st.Expect(t, some_thing.State, fsm.State("started"))
 }

+func TestMachineTransitionConcurrent(t *testing.T) {
+   if runtime.GOMAXPROCS(0) < 2 {
+       t.Skip("unlikely that concurrency bug would manifest on system with one CPU core; skipping")
+   }
+
+   rules := fsm.Ruleset{}
+   rules.AddTransition(fsm.T{"pending", "started"})
+   rules.AddTransition(fsm.T{"pending", "aborted"})
+   rules.AddTransition(fsm.T{"started", "finished"})
+   rules.AddTransition(fsm.T{"aborted", "pending"})
+
+   thing := Thing{State: "pending"}
+   machine := fsm.New(fsm.WithRules(rules), fsm.WithSubject(&thing))
+
+   var err error
+   wg := &sync.WaitGroup{}
+
+   wg.Add(2)
+
+   go func() {
+       err = machine.Transition("started")
+       fmt.Println(thing.State)
+       st.Expect(t, err, nil)
+       st.Expect(t, thing.State, fsm.State("started"))
+       wg.Done()
+   }()
+
+   go func() {
+       time.Sleep(time.Nanosecond * 10000)
+       err = machine.Transition("aborted")
+       st.Expect(t, err, nil)
+       st.Expect(t, thing.State, fsm.State("aborted"))
+       wg.Done()
+   }()
+
+   wg.Wait()
+}
+
 func BenchmarkRulesetParallelGuarding(b *testing.B) {
    rules := fsm.Ruleset{}
    rules.AddTransition(fsm.T{"pending", "started"})

Output:

=== RUN   TestRulesetTransitions
--- PASS: TestRulesetTransitions (0.00s)
=== RUN   TestRulesetParallelGuarding
--- PASS: TestRulesetParallelGuarding (0.00s)
=== RUN   TestMachineTransition
--- PASS: TestMachineTransition (0.00s)
=== RUN   TestMachineTransitionConcurrent
started
--- FAIL: TestMachineTransitionConcurrent (0.00s)
    st.go:41:
        fsm_test.go:127: should be ==
            have: (*errors.errorString) invalid transition
            want: (<nil>) <nil>
    st.go:41:
        fsm_test.go:128: should be ==
            have: (fsm.State) started
            want: (fsm.State) aborted
    st.go:41:
        fsm_test.go:119: should be ==
            have: (*errors.errorString) invalid transition
            want: (<nil>) <nil>
FAIL
exit status 1
FAIL    github.com/ryanfaerman/fsm  0.015s

Memleak in function Permitted

Hello, Ryan!

I think I found memleak here: https://github.com/ryanfaerman/fsm/blob/v2/fsm.go#L69
After the first goroutine ends with false the function Permitted will return and other goroutines will be blocked on write to outcome channel and will never end. It seems that select/case with default here would solve the problem.

Non-working example

rules.AddTransition(fsm.Transition{"pending", "started"})
rules.AddTransition(fsm.Transition{"started", "finished"})

err = some_thing.Apply(rules).Transition("started")

needs to be replaced with

rules.AddTransition(fsm.T{"pending", "started"})
rules.AddTransition(fsm.T{"started", "finished"})

err = some_thing.Apply(&rules).Transition("started")