Eventless transition inside compound state triggers infinite loop

[rlaffers]

I'd like to ask whether the following is the intended behavior, or rather a bug:

My goal: Correct sub-state of a compound state should be selected when the compound state is entered. The target sub-state should be selected by checking some context value.

xstate version: 4.13.0

Example: https://codesandbox.io/s/quirky-shamir-ghzwn

Expected behavior:

1. Click START (event)
2. Machine enters Compound.Default state (=initial state)
3. Transient transition is immediately evaluated. Since context.mode == 1 the machine should transition internally to Compound.First

Actual behavior:
The machine enters an infinite loop. The transient transition is being evaluated ad infinitum.

Reading the docs gave me an impression that the transient transition should be evaluated only once, upon entering the Compound state. Since the transient transition is internal, I wasn't expecting the Compound state to be re-entered and thus triggering the same transient transition again.
Also comments in this issue suggest that internal transitions should not trigger infinite loops.

Am I misinterpreting the docs or is this a bug?

[davidkpiano]

As long as you're still in a compound state that has an always transition, that transition will always be checked, regardless of internal or external transitions, I'm pretty sure. Will have to double-check with the SCXML spec on this, but this is the behavior that makes sense. In the SCXML algorithm:

procedure mainEventLoop():
    while running:
        enabledTransitions = null
        macrostepDone = false
        # Here we handle eventless transitions and transitions 
        # triggered by internal events until macrostep is complete
        while running and not macrostepDone:
            enabledTransitions = selectEventlessTransitions()
            if enabledTransitions.isEmpty():
                if internalQueue.isEmpty(): 
                    macrostepDone = true
                else:
                    internalEvent = internalQueue.dequeue()
                    datamodel["_event"] = internalEvent
                    enabledTransitions = selectTransitions(internalEvent)
            if not enabledTransitions.isEmpty():
                microstep(enabledTransitions.toList())

That enabledTransitions = selectEventlessTransitions() is always called, and it will look through all "active" state nodes (which includes that compound state node) and see if there are any eventless transitions to check. Since you're still in that compound node, that always transition is still fair game.

For your example, the workaround solution is to put that eventless transition in the Default state:

const machine = Machine({
  id: "root",
  initial: "Initial",
  context: {
    mode: 1
  },
  states: {
    Initial: {
      on: {
        START: "Compound"
      }
    },
    Compound: {
      initial: "Default",

      states: {
        Default: {
          always: [
            {
              cond: (ctx) => ctx.mode === 1,
              target: "Mode1"
            },
            {
              cond: (ctx) => ctx.mode === 2,
              target: "Mode2"
            }
          ]
        },
        Mode1: {},
        Mode2: {}
      }
    }
  }
});

[rlaffers]

Thanks for the answer. Now it makes sense to me. Your suggested solution does exactly what was my intention.
Should I perhaps prepare a small PR to improve the documentation about this?

[davidkpiano]

@rlaffers I'd appreciate that!

I'll also look into adding some dev-time warnings.

[rlaffers]

I did a bit of exploring and experimenting to learn how eventless transitions with actions work in detail. Here is what I found. Perhaps someone will find it useful. I will distill key takeaways / recommendations into a documentation update.

Codesandbox demonstrating my analysis is here.

Disclaimer: That code contains anti-patterns which have been added for exploration purposes (e.g. impure and mutating guard functions; manipulating a variable outside of the state machine context). Don't do this for real.

Mechanism

Phase 1: Guard evaluation loop

Eventless transitions on a state node are evaluated in a loop. When state node is entered, the algorithm iterates over its eventless transitions and executes their guards before anything else. What happens next depends on what kind of transition is (or isn't) validated:

1. If a transition with target is validated (either due to it having no guard, or its guard being satisfied) --> the evaluation loop stops immediately, and that transition will be acted upon later (When? - See Phase 2 below).
2. If a transition without target is validated (due to its guard being satisfied) --> the current iteration stops, the transition is marked to be acted upon later, and a new evaluation loop iteration starts. The loop will continue until either a transition with target has been validated, or all guards return false.
3. If no transition was ever validated, nothing happens (obviously).

Note, that in this phase only guards have been executed (some of them possibly multiple times). No actions from validated transitions have been executed yet.

Phase 2: Executing actions

1. Entry actions of the entered state node are executed.
2. Actions of validated eventless transition(s) without targets marked for execution in Phase 1 are executed. Each action will be executed as many times as its guard was satisfied. Actions will be executed in the same order as the order in which their guards were satisfied.
3. If an eventless transition with target has been validated (and the transition is not internal), exit actions are executed.
4. Actions of the validated eventless transition with target are executed.
5. Entry actions of the next state node are executed.

Phase 3: Waiting for another microtask

When the machine receives an event (both internal or external), eventless transitions of the current node will be re-evaluated again (go to Phase 1). Not just any event but only a known event for which there is a transition declared, either in the current node, or its ancestors. Forbidden transitions will trigger Phase 1 as well. Unknown or unhandled events will not.

Takeaways

1. Be careful with eventless transitions without targets! There is a potential for infinite guard evaluation loop.
2. Eventless transition without target and cond --> infinite loop (if no preceding transition was validated first).
3. Eventless transition without target and with cond always satisfied --> infinite loop.
4. If a guard depends on a context value, which is updated in the same transition's action --> infinite loop, because actions are not executed until after the evaluation loop stops.
5. Multiple transitions can possibly be executed (and some of them multiple times) if some eventless transitions do not have targets. (Max 1 transition with target will be executed + variable number of target-less transitions may be taken, i.e. their actions executed).
6. Eventless transition without target but with cond and a send action will start the evaluation loop again but only if the sent EVENT does not trigger transition into another state.
7. raise action from a validated eventless transition will be put into a fast lane and executed immediately AFTER the evaluation loop stops but BEFORE entry actions are executed.
8. Relying on the order of actions is probably a bad idea. This has been mentioned in the docs. Significantly, some eventless transitions' actions may be executed multiple times and in the order indicated by their guard satisfaction order.

[karfau]

I have a question here: If the description of Phase 2 is correct, isn't step 3 being executed after step 1 a contradiction with what is described in Action order?

[rlaffers]

I don't think there is any contradiction. Step 3 of Phase 2 is executed when the machine exits its current state node. This corresponds to step 1. on the Actions order page.
The entry actions executed in Phase2/Step1 is what happened BEFORE handling the transition.

In short, I think you're confusing the current state node with the next state node. Each of them may have entry actions. However, the Actions order page focuses on what happens when you exit the current node, so the entry actions mentioned therein (step 3) belong to the next state node, not the current one.

Phase 2:
3. corresponds to 1. on the Actions order page
4. --> 2.
5. --> 3.

[rlaffers]

PR for updating docs: #1619

This took a while, but I wanted to make sure I did not misrepresent the behavior and kept the docs reasonably concise at the same time.