HSMs?

[tomlarkworthy]

Hierarchical state machines are a great improvement to FSMs, have you seen them before? Also known as UML statecharts.

[eonarheim]

These are very cool! I definitely think this feature should be in TypeState. Found some really good reference on wikipedia https://en.wikipedia.org/wiki/UML_state_machine

I can definitely see how these can model more complicated behavior without the combinatorial increase in state trasiitions.

I'll add the on-deck label to this issue. @tomlarkworthy Do you have any proposed api ideas?

[tomlarkworthy]

The deepest states I call terminal state, a state machine is always in a terminal state.
Non-terminal states can be transitioned to and from, but when transitioned into, the "init" for that level is applied recursively until the machine gets into a terminal state.

Already your constructor API for building an FSM you set the init function. So the hierarchy of HSM is a bit like that. I wonder if there is a neat way of just nesting your existing FSMs? Doing it in a typesafe way is tricky. You could pass in the parent type of the FSM so things can call out

FSM<States, ParentFSM extends FSM>

enum top_states {A, B}
enum inner_states_A {A1, A2}
enum inner_states_B {B1, B2}

var fsm = new FSM<top_states, ???>

var fsmA = new FSM<inner_states_A, FSM<top_states, ???>>

The problem is that the top state needs to know about all the possible states underneath. You can do some weird linked list templating but it probably becomes too confusing to be unusable. Union types? Not sure if they work with enums.

The other approach is maybe just just having all terminal and non-terminal states in an enum, and manually setting the state hierarchy after construction:

hsm.group(parent: T, initialSubState: T, elements ... T)

It's quite possible for people to make an invalid hierarchy like that though (e.g. circular, partially overlapping), and it's a bit imperative in style.

// side notes:
Both need an efficient way of finding the parent-child relations between types. If you are optimizing for speed, there is a nested set representation that might be helpful https://en.wikipedia.org/wiki/Nested_set_model.

If you use two numbers to represent a state, you can do very fast checks and walks over the state diagram. On construction, all enum values are terminal, so the Left = Right value. When you group, one state stops being a leaf state, and its interval is changed to encompass all the other states.