Check that all state transitions can reach a final state.

[twoolie]

• Python State Machine version: 2.1.2
• Python version: 3.10
• Operating System: Ubuntu Linux

Description

Is it possible to expand the current checks to ensure that states not marked as final always have an outgoing transition?

What I Did

I was surprised to find that I could construct a state machine that would get "stuck" in a non-final state.

class ExampleSM(StateMachine):
    start = State(initial=True)
    stuck = State()
    stop = State(final=True)

    happy = start.to(stop)
    sad = start.to(stuck)

[fgmacedo]

Hi @twoolie, thank you for bringing this to our attention.

At the moment, this is the expected behavior. As a library, our goal is to accommodate a wide range of use cases. Some state machines, like the "semaphore" example, are designed to run cycles indefinitely and never reach an end state.

However, we are considering your suggestion to implement a check if there's a declared final state, ensuring that all states have a path leading to a final state. This could be a small patch to the library but significant change to users, and may require a major release, as it has the potential to alter the "Public behavior."

What do you think?

We appreciate your input and will give it thorough consideration.

[twoolie]

Hi @fgmacedo

There's two different checks that we could implement that give different guarantees:

A) Check that all non-final states have an outgoing transition. This guarantees that progress is always possible, but allows for infinite looping state machines. (do self-transitions count? i think they should.) B) If final states exist, check that all non-final states have a path to a final state. This guarantees that the state machine has a path to termination, and the author hasn't forgot a transition that should be there.

I can't find the semaphore example, did you mean traffic light? I don't think that either of these checks would impact that example. For the A check, the traffic light example does have all states with outgoing transitions. The traffic light example has no final states, so we can skip the B check.

As far as altering public behaviour, you could add the check as a warning in the next release, and then change the check to an error in the next (major?) release.

If you're happy with this proposal, I'd be happy to work on the implementation.

[rafaelrds]

@twoolie I'm more of a fan of approach B since that will also be useful for avoiding human error when creating large state machines. Also, I thought I had this covered on #232 but apparently, I didn't. What do you think @fgmacedo ?

[fgmacedo]

I believe that A and B are not mutually exclusive and can both be implemented.

A helps prevent definition errors of dead states, which lead to a stuck SM, by making it necessary to mark a "final" state as final=True. This change may necessitate further modifications across a broad range of library uses.

B is more likely to be mapped to an error, without necessitating a major version bump.

In my opinion, we should pursue the implementation of both:

1. A: Initially, introduce it as a warning for the 2.1.X version, and include a note in the documentation indicating that it will be converted into an exception in the next major release.
2. B: Implement as an InvalidDefinition.
3. Enhance the documentation to enumerate all SM validations performed at "import time" and at "instance creation time".

[twoolie]

A and B are different checks, but B will be valid only if A is also valid.

This change may necessitate further modifications across a broad range of library uses.

I don't think this will affect any of the examples, or many users of the library who have used the examples as models, but just in case, we can add a warning for both A and B before turning them into hard errors.

Turning either A or B into hard errors is technically a breaking change, but perhaps a minor version bump is enough, since import-time errors should be easily caught by even the simplest test suite.

[fgmacedo]

Closed by #410