Nested/hierarchical States

[cassiozen]

Nested states are beneficial for a myriad of reasons, including:

• State nesting lets you define a new state rapidly in terms of an old one by reusing the behavior from the parent state
• State nesting lets you get new behavior almost for free, reusing most of what is common from the parent states

Configuration

This is what a nested state machine configuration would look like:

// Traffic Lights
useStateMachine()({
  initial: "green",
  states: {
    green: {
      on: {
        TIMER: "yellow",
      },
    },
    yellow: {
      on: {
        TIMER: "red",
      },
    },
    red: {
      on: {
        TIMER: "green",
      },
      // Nested state: Pedestrian traffic light
      initial: "walk",
      states: {
        walk: {
          on: {
            PED_COUNTDOWN: "wait",
          },
        },
        wait: {
          on: {
            PED_COUNTDOWN: "stop",
          },
        },
        stop: {},
      },
    },
  },
});

State value representation:

The returned machine state would still have a string representation for the state value. Nested stated will be represented with dot syntax. For the above example, possible states are:

• green
• yellow
• red.walk
• red.wait
• red.stop

Transitions & Effects

For every transition, the state machine should traverse the config three (depth-first) and find the shortest path for the transition.
Effects should be invoked on parent state only once: transitioning between child states should not re-fire parent effects.

[RunDevelopment]

I have a few questions:

1. Will this also support on in the root config like in XState?
2. Will this support infinite nesting (= arbitrary nesting depths)?
   1. Related: Will this support recursive state machines?
3. Can nested states transition into parent states? E.g. can red.wait transition into green?
4. Can parent states transition into nested states? E.g. can green transition into red.wait?
5. Is the current state of the machine also going to be represented by the dot syntax?
6. Can the initial state also use dot syntax?
7. Isn't the dot syntax (e.g. red.wait) ambiguous? E.g. what would happen if I added another root state called red.wait?
   1. Why not a nested object syntax? E.g. { red: 'wait' }. This nested object syntax also has the advantage that it's easy to express in typed while the dot syntax is impossible to express in types even using TS' template literal types.

I want to clarify: these are questions, not suggestions.

[cassiozen]

XState is, of course, a huge influence on whatever we do here, but since we don't adhere to the SCXML spec, we can be more free-form in some cases.

1. Will this also support on in the root config like in XState?

No, transitions always belong to a state. If the user wants to represent global transitions, they can create one more level of nesting and add them under a new parent state.

2. Will this support infinite nesting? Related: Will this support recursive state machines?

Yes, it should support infinite nesting and it will be recursive.

3. Can nested states transition into parent states? E.g. can red.wait transition into green?

Yes. It will recursively check for guards (we might need to update the guards to give them more information about the event and transitions), but otherwise, this transition is possible.

4. Can parent states transition into nested states? E.g. can green transition into red.wait?

That's a good question. I think yes. We could require the state names to be unique, so the user could just create a transition to "wait" and it would work. As with the previous answer, we would have to fire all existing guards in the path - if any one returns false, the whole transition is denied.

5. Is the current state also going to be represented by the dot syntax?

That was my initial though - we would have a getStateNode method which would return the config node based on the string representation. But you have a good point in question 7, so this might be different.
In any case, we need to provide an API that allows the user to easily show/hide UI based on the state. A string with dot syntax would allow the user to do things like:

// All valid:
machine.value.match(/green/)
machine.value.match(/red/)
machine.value.match(/wait/)
machine.value.match(/red.wait/)

6. Can the initial state also use dot syntax?

No. But the initial state might point to the parent of a nested state with its own initial - the end result is that the state machine would start in the nested state.

7. Isn't the dot syntax (e.g. red.wait) ambiguous? E.g. what would happen if I added another root state called red.wait?

I see your point. I like the dot representation for the reasons mentioned above. We could:

• Keep the dot syntax representation and disallow names with dots. (Might be hard to enforce with TypeScript)
• Use a different representation but keep the dot syntax as a separate property (or we could implement our own match function in the machine proxy).

8. Why not a nested object syntax? E.g. { red: 'wait' }. This nested object syntax also has the advantage that it's easy to express in typed while the dot syntax is impossible to express in types even using TS' template literal types.

I'm open to that. In my previous experimentation (before your type refactor), I got template literals working with this:

type StatesKeys<T> = T extends { states: infer S }
  ? {
      [K in Extract<keyof S, string>]: K | `${K}.${StatesKeys<S[K]>}`;
    }[Extract<keyof S, string>]
  : never;

But I understand that this might not work with the current code.

[cassiozen]

For reference, I added a branch with the experimentation on nested types I was working on before the refactor: https://github.com/cassiozen/useStateMachine/blob/dead-experimentalHierarchicalSM/src/index.tsx

Some notes:

• It needs a newer Typescript version then TSDX uses, so it ditches TSDX.
• The code is on a non-working state: The main pieces are there but it just needed more hours. It's abandoned now because of the refactor.

[RunDevelopment]

Sorry for the delay.

Points 1, 2, 6

👍

3. Can nested states transition into parent states? E.g. can red.wait transition into green?

Yes. It will recursively check for guards (we might need to update the guards to give them more information about the event and transitions), but otherwise, this transition is possible.

4. Can parent states transition into nested states? E.g. can green transition into red.wait?

That's a good question. I think yes. We could require the state names to be unique, so the user could just create a transition to "wait" and it would work. As with the previous answer, we would have to fire all existing guards in the path - if any one returns false, the whole transition is denied.

This will make typing difficult but let's see.

5. Is the current state also going to be represented by the dot syntax?

That was my initial though - we would have a getStateNode method which would return the config node based on the string representation. But you have a good point in question 7, so this might be different.
In any case, we need to provide an API that allows the user to easily show/hide UI based on the state. A string with dot syntax would allow the user to do things like:

// All valid:
machine.value.match(/green/)
machine.value.match(/red/)
machine.value.match(/wait/)
machine.value.match(/red.wait/)

Please do not use match like this...

1. match returns a RegExpExecArray | null and not a boolean.
2. The regexes are missing edge assertions. Right now, /green/ will happily match the state green-tea.
3. . matches (almost) any character, so have fun escaping the dot everywhere...

Please provide a custom API to match the current state. Regexes really aren't the right tool here.

7. Isn't the dot syntax (e.g. red.wait) ambiguous? E.g. what would happen if I added another root state called red.wait?

I see your point. I like the dot representation for the reasons mentioned above. We could:

• Keep the dot syntax representation and disallow names with dots. (Might be hard to enforce with TypeScript)
• Use a different representation but keep the dot syntax as a separate property (or we could implement our own match function in the machine proxy).

It's relatively easy to decide whether a string constant contains a dot:

type HasDot<T> = T extends `${string}.${string}` ? true : false;

I don't like the dot syntax because it imposes this arbitrary limitation on the keys. Not only does this make the types more complex is also a potential room for error and frustration for the user.

Let's say we do use TS to enforce that state names can't contain dots. If we did that, then our users would also have to enforce this in their code which can be challenging. If the user wanted to programmatically create a state machine config, the code creating the config would have to enforce the no-dots rule everywhere.

However, not enforcing the no-dots rule will leave users vulnerable to preventable and potentially hard-to-catch bugs.

8. Why not a nested object syntax? E.g. { red: 'wait' }. This nested object syntax also has the advantage that it's easy to express in typed while the dot syntax is impossible to express in types even using TS' template literal types.

I'm open to that. In my previous experimentation (before your type refactor), I got template literals working with this:

type StatesKeys<T> = T extends { states: infer S }
  ? {
      [K in Extract<keyof S, string>]: K | `${K}.${StatesKeys<S[K]>}`;
    }[Extract<keyof S, string>]
  : never;

But I understand that this might not work with the current code.

Template literals can't work. The problem is recursive machines. Your StatesKeys generates one string type for each possible states but recursive machines have effectively infinitely many states. TS can't create infinitely many types.

The object syntax doesn't have this problem. However, now that I think about it, a simple array syntax (["red", "wait"]) might be even better (and easier to type). A simple array would also be a lot easier to process for users.

[cassiozen]

Sorry for the delay.

We're not being paid for this - no need to apologize 😜.

1. Can parent states transition into nested states? E.g. can green transition into red.wait?

That's a good question. I think yes. We could require the state names to be unique, so the user could just create a transition to "wait" and it would work. As with the previous answer, we would have to fire all existing guards in the path - if any one returns false, the whole transition is denied.

This will make typing difficult but let's see.

Ok, we can revisit if the typing doesn't work.

Please do not use match like this...
Please provide a custom API to match the current state. Regexes really aren't the right tool here.

I see your point, thanks. I will provide a custom syntax - Although, if we go with your array syntax suggestion (which I like a lot), and the user is targeting modern browsers, they could simply do:

machine.value.includes('green')
machine.value.includes('red')
machine.value.includes('wait')

I don't like the dot syntax because it imposes this arbitrary limitation on the keys. Not only does this make the types more complex is also a potential room for error and frustration for the user.
(...)
However, now that I think about it, a simple array syntax (["red", "wait"]) might be even better (and easier to type).

Agreed, I like the suggestion. Let's go for the Array syntax.

[threehams]

Would you take a PR for this? Over at work we've just introduced xstate, but are now looking for a smaller state machine library with better TypeScript inference. The only feature we'd need would be nested states.

[cassiozen]

I would definitely take a PR for this!

[smhmd]

@cassiozen Is there a pattern you'd suggest as a work around?

[cassiozen]

What exactly do you want to achieve? Depending on the case you could simply flatten your state hierarchy, or use XState.

[threehams]

Turns out we're not using nested states at all - we're invoking other machines and waiting on the results. I think that's already possible without any changes (thanks, React!) but maybe I'll propose something if I run into problems.

[devanshj]

Just wanted to give my two cents on types in context of #36, also I only skim read stuff so apologies if I missed something.

what would happen if I added another root state called red.wait

If we want, we can disallow having state names that contain dots, like txstate does.

The problem is recursive machines

If this is a blocker for dot syntax then it's also a blocker for array syntax :P as you can't type an infinite long array of a pattern like ["foo", "bar", "foo", "bar", "foo", "bar", ...]. (Though I don't think anyone's making recursive state machines unless I'm ignorant about it xD)

That's a good question. I think yes. We could require the state names to be unique, so the user could just create a transition to "wait" and it would work. As with the previous answer, we would have to fire all existing guards in the path - if any one returns false, the whole transition is denied.

This will make typing difficult but let's see.

Not a problem, we can enforce state names to be unique just like how txstate enforces ids to be unique

I have zero opinions on these three issues in context of semantics, so y'all don't have to change any of the decisions already made if they seem right, just wanted to make it clear that types aren't a problem xD

[cassiozen]

Again, thanks a lot for your contribuitions, @devanshj

If we want, we can disallow having state names that contain dots

That's perfect! If we disallow names containing dots AND require names to unique, we can keep the original plan of making it string-based. I have a semi-working implementation, but none of the typing. Let me know when you think you might have time for this and we can coordinate.

[devanshj]

My pleasure!

You can continue with the implementation if you want, as said the implementation types need not be fully type safe. I'll start working on the user facing types too once I'm done with types for 1.0