Paul J. LucasI’m currently in the process of porting my CHSM (Concurrent Hierarchical Finite State Machine) project that has C++ and Java implementations to Go. Porting involves both rewriting the run-time library in Go as well as augmenting the CHSM compiler to emit Go code.
Briefly, a CHSM is like an ordinary finite state machine: states can be entered and exited by receipt of events that cause transitions among the states. Unlike an ordinary finite state machine, a CHSM can have some parent states that have child states nested within them: entering a parent state in turn enters one of its child states. When a state has been entered but not yet exited, it is considered to be active.
To focus on the point of this article, the implementations presented are simplified versions of the real thing. For example, let’s implement State as:
type State interface {
Enter()
Exit()
Name() string
}
type CoreState struct {
name string
parent Parent
}
func (s *CoreState) Enter() {
fmt.Printf("CoreState.Enter(%s)\n", s.Name())
if s.parent != nil {
s.parent.switchActiveChildTo(s)
}
}
func (s *CoreState) Exit() {
fmt.Printf("CoreState.Exit(%s)\n", s.Name())
}
func (s *CoreState) Name() string {
return s.name
}
That’s mostly straightforward. Next, let’s implement Parent as:
type Parent interface {
State
switchActiveChildTo(State)
}
type CoreParent struct {
CoreState
children []State // A parent has zero or more children.
activeChild State // One child is the active one.
}
func (p *CoreParent) Enter() {
fmt.Printf("CoreParent.Enter(%s)\n", p.Name())
p.CoreState.Enter() // Enter ourselves first.
if p.activeChild == nil { // Default to first child.
p.activeChild = p.children[0]
}
p.activeChild.Enter() // Enter activeChild.
}
func (p *CoreParent) Exit() {
p.activeChild.Exit() // Exit activeChild first.
p.CoreState.Exit() // Then exit ourselves.
fmt.Printf("CoreParent.Exit(%s)\n", p.Name())
}
func (p *CoreParent) switchActiveChildTo(child State) {
p.activeChild = child
}
The semantics of CHSMs include the ability to enter a child state directly, bypassing its parent. If this happens and the parent is already active, the child must request that the parent switch its active child state to itself, hence the
switchActiveChildTo()method.
The Problem
Let’s write a test program:
func main() {
outer := &CoreParent{ CoreState: CoreState{ name: "outer" } }
inner := &CoreParent{ CoreState: CoreState{ name: "inner" } }
s := &CoreState{ name: "s" }
// Normally, the CHSM compiler emits code to set the parent/child pointers.
outer.children = []State{ inner }
inner.parent = outer
inner.children = []State{ s }
s.parent = inner
outer.Enter()
fmt.Println("-------------------------")
outer.Exit()
}
When run, it prints:
CoreParent.Enter(outer)
CoreState.Enter(outer)
CoreParent.Enter(inner)
CoreState.Enter(inner)
CoreState.Enter(S)
-------------------------
CoreState.Exit(inner)
CoreState.Exit(outer)
CoreParent.Exit(outer)
That’s wrong! The calls to Exit() should pair with the calls to Enter(), but CoreState.Exit(s) and CoreParent.Exit(inner) are missing. Why? After many hours of debugging, I tracked it down to this:
func (s *CoreState) Enter() {
// ...
s.parent.switchActiveChildTo(s)
// ...
}
func (p *CoreParent) switchActiveChildTo(child State) {
p.activeChild = child
}
But what’s wrong with that? The child is telling its parent to set its active child to itself. How could that be wrong?
Background on Interfaces
In Go, the only way to get polymorphism is via interfaces. An ordinary variable in Go has two attributes: its static type and its value. The static type is the type the variable was declared as. An interface additionally has a dynamic type that is the type of the object to which the (pointer) value points:
// static type = int; value = 42
var n int = 42
// static type = State; dynamic type = CoreParent; value = &outer
var i State = &outer
When you call a method on an interface, the implementation actually calls the corresponding method on the object to which the interface’s pointer value points. The pointer value becomes the value of the method receiver; the dynamic type of the interface becomes the static type of the receiver. This means that once an interface value “decays” into a pointer, the polymorphism disappears.
The Reason for the Bug
When the test program is run, the following happens. On the left, the name, static type, and value of the receivers are shown:
1. p *CoreParent = &outer | CoreParent.Enter(outer)
2. s *CoreState = &outer.CoreState | CoreState.Enter(outer)
3. p *CoreParent = &inner | CoreParent.Enter(inner)
4. s *CoreState = &inner.CoreState | CoreState.Enter(inner)
5. p *CoreParent = &outer | switchActiveChildTo(inner.CoreState)
At this point, outer.activeChild that should be &inner of type *CoreParent actually gets set to &inner.CoreState of type *CoreState. The confusing part is that both of those objects have the same name (because Name() of the embedded type CoreState is forwarded from CoreParent).
When Exit(outer) is called, the following happens:
1. p *CoreParent = &outer | CoreParent.Exit(outer)
2. s *CoreState = &outer.CoreState | CoreState.Exit(outer)
3. s *CoreState = &inner.CoreState | CoreState.Exit(inner)
CoreState.Exit(s) is never called because CoreParent.Exit(inner) is never called — CoreState.Exit(inner) is called instead. To show this even clearer, we can augment CoreParent.Enter():
func (p *CoreParent) Enter() {
// ...
t0 := reflect.TypeOf(p.activeChild)
p.activeChild.Enter() // eventually calls switchActiveChildTo()
t1 := reflect.TypeOf(p.activeChild)
if t1 != t0 {
fmt.Printf("%s type changed: %v != %v\n", p.activeChild.Name(), t1, t0)
}
}
and it additionally prints:
inner type changed: *CoreState != *CoreParent
Strictly Speaking...
To prevent purists in the Go community from coming after me with pitchforks, I’ll point out that the type of activeChild did not actually change. What actually happened is that activeChild gets assigned the pointer to a different object: the CoreState object that’s embedded inside CoreParent — so of course the type changed.
Well, yes, but: if you extract the pointer value from the interface before and after the assignment and compare it such as:
func getPtrValue(i interface{}) uintptr {
return (*[2]uintptr)(unsafe.Pointer(&i))[1]
}
func (p *CoreParent) Enter() {
// ...
a0 := getPtrValue(p.activeChild)
p.activeChild.Enter()
a1 := getPtrValue(p.activeChild)
if a1 != a0 {
fmt.Printf("%s address changed: %v != %v\n", p.activeChild.Name(), a1, a0)
}
}
the program does not print inner address changed because it doesn’t. A CoreParent object in memory has the embedded CoreState at a zero offset. So, yes, activeChild was assigned a pointer to “different” object having a different type — but that object has the same address.
A distinction without a difference?
The Fix
Back to the Go port of CHSM: how can the run-time library be changed to do what I want? The way I fixed this was to change CoreState.Enter() so that it looked up a pointer to the original state’s object (of the original type) using a new CoreState.id field in a slice containing pointers to all states:
var allStates []State
func (s *CoreState) Enter() {
fmt.Printf("CoreState.Enter(%s)\n", s.Name())
if s.parent != nil {
child := allStates[s.id]
s.parent.switchActiveChildTo(child)
}
}
// ...
func main() {
outer := &CoreParent{ CoreState: CoreState{ name: "outer", id: 0 } }
inner := &CoreParent{ CoreState: CoreState{ name: "inner", id: 1 } }
s := &CoreState{ name: "s", id: 2 }
allStates = []State{ outer, inner, s }
// ...
}
