README
¶
go-hsm
go-hsm is a Golang library that implements the Hierarchical State Machine(HSM).
Hierarchical State Machine(HSM) is a method to express state machine. It's introduced in the book Practical Statecharts in C/C++: Quantum Programming for Embedded System by Dr. Miro M. Samek. Comparing to the traditional methods to implement state machine(e.g. nested if-else/switch, state table, state design pattern in OOP), HSM provides some major advantage as the followings:
- It supports nested states and hehavior inheritance
- It provides entry and exit action for state
- It uses class hierarchy to express state hierarchy. Easy to write and understand.
The book mentioned above gives an elaboration on state machine and HSM. For more details, please refer to it.
Whenever there arises the requirement to write codes which have high complexity but need to be definitely correct, state machine is a promising way to get there. HSM is a great pattern to express state machine. And HSM is the most powerful pattern I know so far. At the moment I ran into some Golang project like Raft, HSM occurs to me. So I port HSM to Golang and create this project.
Port HSM to Golang
Along with the theory of HSM, there are two implementations of it in the book, one in C and the other in C++. Some language specified features are used in these implementations. However, Golang has some significant differencies in the programming language features. So porting HSM to Golang would not be doing a simple copycat of the original implementations.
In both implementations, methods(member functions of class) are used to represent states. However no member function pointer in Golang. And In the C/C++ implementation the class inheritance hierarchy are used to represent the structure of states for the whole state machine. The OOP inheritance in Golang is quite different by using interface. In Golang, there is no parent pointer for parent class object in an object's memory layout.
My first thought is to use function variable/lambda function to represent state. But it's not easy to maintain the state hierarchy between functions. After some experiments on trying to get HSM up and running in Golang, it turns out to be the way it's as now: class represents State, and state hierarchy is done munually(and verbosely) in initialization of the whole state machine.
IMO, implementing HSM in this way isn't perfect. There are some pitfalls:
- To define a new state, you always need to write super.AddChild() in the New() constructor, which I consider as a abstraction leak. Anyway it's boring.
- Defining states could be lot of chunks of codes to write. All of states have the similar Entry/Exit/Handle code structure. To provide some kinds of code template for code reusage, the lack of meta programming ability in Golang leads me to a DSL and code generator, which is too heavy and too complicated.
- The type casts when handling event. Casting is inevitable in such a generic framework. But I don't think the library user should write these codes by hand again and again. It's unwelcomed especially while assert is taken out from language libraries in Golang, although casting needs it to ensure type correctness. (IMO, assert is a dark corner in Golang. The language just takes it out. But when someone revives it as a library(see testify.assert), people find it quite useful and want it.
The Missings
This project contains only the HSM, briefly a method to construct state machine and dispatch events. It's not targeted for a full Quantum Framework. But there are still some pieces missing:
- composite states
- local and external transitions, internal transitions
- event queuing
- validation of state machine structure, with checks for:
- machine having single top state
- unreachable states
- multiple occurrences of same state object instance
- multiple states with same name
- transitions that start from or point to nonexistent states
Usage
In the directory example there are examples demonostrating how to use go-hsm to write state machine, each example has its graphical state chart.
1. C Comment Parser
In the sub-directory c_comment.
2. An Annotated State Chart
In the sub-directory annotated.
Documentation
¶
Index ¶
- Constants
- Variables
- func AssertEqual(expected, actual interface{})
- func AssertFalse(value bool)
- func AssertNil(value interface{})
- func AssertNotEqual(expected, actual interface{})
- func AssertNotNil(value interface{})
- func AssertTrue(value bool)
- func ListFind(l *list.List, value interface{}) (*list.Element, error)
- func ListFindIf(l *list.List, predicate func(value interface{}) bool) (*list.Element, error)
- func ListIn(l *list.List, value interface{}) bool
- func ListTruncate(l *list.List, e *list.Element) *list.List
- func ObjectAreEqual(expected, actual interface{}) bool
- func Record(stdEvent Event, actions *list.List, hsm HSM, state State, event Event)
- func RecordEntry(actions *list.List, hsm HSM, state State, event Event)
- func RecordExit(actions *list.List, hsm HSM, state State, event Event)
- func RecordInit(actions *list.List, hsm HSM, state State, event Event)
- type Event
- type EventType
- type HSM
- type HSMType
- type Initial
- type State
- type StateHead
- func (self *StateHead) AddChild(child State)
- func (self *StateHead) Children() []State
- func (self *StateHead) Entry(hsm HSM, event Event) (state State)
- func (self *StateHead) Exit(hsm HSM, event Event) (state State)
- func (self *StateHead) Init(hsm HSM, event Event) (state State)
- func (self *StateHead) Super() State
- type StaticTranAction
- type StaticTranChain
- type StaticTranID
- type StdEvent
- type StdHSM
- func (self *StdHSM) Dispatch(event Event)
- func (self *StdHSM) Dispatch2(hsm HSM, event Event)
- func (self *StdHSM) GetState() State
- func (self *StdHSM) Init()
- func (self *StdHSM) Init2(hsm HSM, event Event)
- func (self *StdHSM) IsIn(stateID string) bool
- func (self *StdHSM) LookupState(targetStateID string) State
- func (self *StdHSM) QInit(targetStateID string)
- func (self *StdHSM) QTran(targetStateID string)
- func (self *StdHSM) QTranDyn(targetStateID string)
- func (self *StdHSM) QTranDynHSM(hsm HSM, target State)
- func (self *StdHSM) QTranDynHSMOnEvent(hsm HSM, target State, event Event)
- func (self *StdHSM) QTranDynHSMOnEvents(hsm HSM, target State, entryEvent, initEvent, exitEvent Event)
- func (self *StdHSM) QTranDynOnEvent(targetStateID string, event Event)
- func (self *StdHSM) QTranHSM(hsm HSM, target State)
- func (self *StdHSM) QTranHSMOnEvent(hsm HSM, target State, event Event)
- func (self *StdHSM) QTranHSMOnEvents(hsm HSM, target State, entryEvent, initEvent, exitEvent Event)
- func (self *StdHSM) QTranOnEvent(targetStateID string, event Event)
- func (self *StdHSM) QTranSetup(hsm HSM, target State, entryEvent, initEvent, exitEvent Event) *StaticTranChain
- func (self *StdHSM) Type() HSMType
- type Terminal
- type Top
Constants ¶
const ( TopStateID = "TOP" InitialStateID = "Initial" TerminalStateID = "Terminal" )
state IDs for all the default states
Variables ¶
var StdEvents = map[EventType]*StdEvent{ EventEmpty: NewStdEvent(EventEmpty), EventInit: NewStdEvent(EventInit), EventEntry: NewStdEvent(EventEntry), EventExit: NewStdEvent(EventExit), }
The default events(used in state transfer procedure). They are defined as global const for optimization.
Functions ¶
func AssertEqual ¶
func AssertEqual(expected, actual interface{})
AssertEqual asserts the equality of actual and expected.
func AssertNotEqual ¶
func AssertNotEqual(expected, actual interface{})
AssertEqual asserts the inequality of actual and expected.
func ListFind ¶
ListFind() searchs the first element which has the same value of `value' in list `l'. It uses object comparation for equality check.
func ListFindIf ¶
ListFindIf() searchs for and element of the list `l' that satifies the predicate function `predicate'.
func ListTruncate ¶
ListTruncate() removes elements from `e' to the last element in list `l'. The range to be removed is [e, l.Back()]. It returns list `l'.
func ObjectAreEqual ¶
func ObjectAreEqual(expected, actual interface{}) bool
ObjectAreEqual test whether actual is equal to expected. It returns true when equal, otherwise returns false.
Types ¶
type Event ¶
type Event interface {
// Returns the type of this event
Type() EventType
}
Event represents the interface that every message which is dispatched to state machine should implements.
type HSM ¶
type HSM interface {
// Returns the type of this hsm
Type() HSMType
// Runs the initialization of this hsm
Init()
// Dispatch event to state machine
Dispatch(event Event)
// Returns current state of this hsm
GetState() State
// Tests whether this hsm is in specified state. It works no matter
// stateID is in any level as a parent state of current state.
IsIn(stateID string) bool
// Transfer to specified target state during state intialization.
QInit(targetStateID string)
// Statically transfer to specified target state as normal state transfer.
QTran(targetStateID string)
// Statically transfer to specified target state as normal state transfer,
// along with specified event dispatched during transfer procedure.
QTranOnEvent(targetStateID string, event Event)
// Dynamically transfer to specified target state as normal state transfer.
QTranDyn(targetStateID string)
// Dynamically transfer to specified target state as normal state transfer,
// along with specified event dispatched during transfer procedure.
QTranDynOnEvent(targetStateID string, event Event)
}
HSM represents the interface that every state machine class should implement.
type Initial ¶
The default initial state for state machines. It's the start point of state machine.
func NewInitial ¶
type State ¶
type State interface {
// Returns the ID of this state
ID() string
// Returns parent state of this state
Super() (super State)
// Returns all children states of this state
Children() []State
// It add state child as a child of this state.
AddChild(child State)
// Called when this state is targeted in state initialization.
Init(hsm HSM, event Event) (state State)
// Called when entering this state
Entry(hsm HSM, event Event) (state State)
// Called when exiting this state
Exit(hsm HSM, event Event) (state State)
// Called when event dispatched to this state
Handle(hsm HSM, event Event) (state State)
}
State represents the interface that every state class should implements.
type StateHead ¶
type StateHead struct {
// contains filtered or unexported fields
}
StateHead is the head of every state to maintain the parent/child relationship so that all states compose the whole state hierarchy of state machine. It provides the default implementations of Super(), Children(), AddChild() for states.
func NewStateHead ¶
NewStateHead() is the constructor for StateHead.
type StaticTranAction ¶
type StaticTranChain ¶
type StaticTranID ¶
type StdEvent ¶
type StdEvent struct {
EventType EventType
}
StdEvent is the default Event implementation.
func NewStdEvent ¶
type StdHSM ¶
type StdHSM struct {
// The type of concrete HSM
MyType HSMType
// The state that handles event(it could Super(), Super().Super(), ...)
// of current state
SourceState State
// The current state(it could be child, child's child of SourceState)
State State
// The global map for all states and their names in this state machine
StateTable map[string]State
// The transfer action chains cached for static transfers
StaticTrans map[StaticTranID]*StaticTranChain
}
StdHSM is the default HSM implementation. Any HSM derived could reuse it as anonymous field.
func (*StdHSM) Init2 ¶
Init2() is a helper function to initialize the whole state machine. All state initialization actions started from initial state would be triggered.
func (*StdHSM) LookupState ¶
LookupState() search the specified state in state/name map.
func (*StdHSM) QTranDynHSM ¶
QTranDynHSM() is a helper function for QTran(). It's separated from QTranDyn() in order to deliver the concrete HSM (which is the first arguemnt of QTranDynHSM()) rather than just the embedded StdHSM to the state transfer procedure.
func (*StdHSM) QTranDynHSMOnEvent ¶
func (*StdHSM) QTranDynHSMOnEvents ¶
func (self *StdHSM) QTranDynHSMOnEvents( hsm HSM, target State, entryEvent, initEvent, exitEvent Event)
QTranDynOnEvents() is the implementation of QTranDyn* functions.
func (*StdHSM) QTranDynOnEvent ¶
QTranDynOnEvent() is a variant function of QTranDyn(). Instead of dispatching the default events of `EventEntry'/`EventInit'/`EventExit', this function would dispatch the given event along the state transfer procedure.
func (*StdHSM) QTranHSMOnEvent ¶
func (*StdHSM) QTranHSMOnEvents ¶
func (*StdHSM) QTranOnEvent ¶
QTranOnEvent() is variant function of QTran().
func (*StdHSM) QTranSetup ¶
func (self *StdHSM) QTranSetup( hsm HSM, target State, entryEvent, initEvent, exitEvent Event) *StaticTranChain
type Terminal ¶
type Terminal struct {
*StateHead
}
the default terminal state for state machines. It's the end point of state machine.
Source Files
Directories