What does graph package do?

[coodoo]

This might be a totally off-topic question, I found this graph package lurking around down the src folder while flipping through the source code, wondering what's it meant for?

Is this something along the line of behavior trees mentioned here?

[davidkpiano]

The @xstate/graph package is meant for exposing utilities for performing graph algorithms (such as shortest paths, simple paths, etc.) on statecharts. Documentation coming 🔜

[coodoo]

Now that sounds very intriguing, very looking forward to it :D

[davidkpiano]

See the docs here: https://xstate.js.org/docs/packages/xstate-graph/

[coodoo]

Huge props for @davidkpiano for providing getShortestPaths and getSimplePaths via the lib, is it too much to expect automated testing of statechart coming soon? 😅

[davidkpiano]

is it too much to expect automated testing of statechart coming soon?

Nope 😉 Article coming 🔜📰

[coodoo]

🙌🙌

[ZempTime]

🤗 Really excited for this!

[dsedmak]

is it too much to expect automated testing of statechart coming soon?

Nope 😉 Article coming 🔜📰

Any updates on this @davidkpiano ? I would like to pitch using xstate to drive our SPA to my team. We're planning a rewrite sometime soon and this feature would definitely help make my case.

[davidkpiano]

@dsedmak I'm working on some better tooling for automating tests with XState, but here is the initial article draft I have for the topic: https://gist.github.com/davidkpiano/cf628911427b275a9a659d510a785d15

[dsedmak]

@dsedmak I'm working on some better tooling for automating tests with XState, but here is the initial article draft I have for the topic: https://gist.github.com/davidkpiano/cf628911427b275a9a659d510a785d15

Thank you for this @davidkpiano .

I have been thinking and it seems to me that both approaches to generating (and executing) test paths have their flaws.

If we follow the paths returned by getShortestPaths we will explore all nodes in the graph (states) but not all edges (transitions/guards). Not executing certain pieces of code during testing seems like a bad idea.

If on the other hand we follow the paths returned by getSimplePaths we will explore certain edges multiple times which is unnecessary and just makes the test longer. With complex machines the effect might be substantial. Even if we follow the shortest paths it's still possible to execute certain transitions multiple times.

Actually, the examples at https://xstate.js.org/docs/packages/xstate-graph/ are also examples of both problems.

I think it would be simpler and more efficient to traverse the graph using breadth-first search and not expand visited states. Something like this perhaps (not tested, just pseudocode):

const machine = Machine(/* machine config */);
const service = interpret(machine);
const eventList = getPossibleEventsForState(service.initialState);
const queue = eventList.map(event=>[service.initialState, event]);
const visitedStates = new Set([service.initialState]);
while(queue.length){
  const [previousState, event] = queue.shift();
  service.start(previousState);
  service.send(event);
  if(!visitedStates.has(service.state)){
    queue.push(getPossibleEventsForState(service.state).map(event=>[service.state, event]));
    visitedStates.add(service.state);
  }
}

This way each transition is attempted exactly once and every state is visited at least once (if it can be reached). If you only wish to generate a list of state, event pairs than the interpreter can be avoided. What do you think?

[davidkpiano]

Actually, the examples at xstate.js.org/docs/packages/xstate-graph are also examples of both problems.

Keep in mind, the "problematic" examples are still better solutions (in terms of test coverage) than existing techniques today 😉

I think it would be simpler and more efficient to traverse the graph using breadth-first search and not expand visited states

I think that's a valid technique for many use-cases, and ideally, some sort of testing package would allow the developer to choose any traversal method (shortest path would work for most).

Additionally, it is possible to recognize when potential transitions were not taken (due to a guard preventing the transition) and warn the developer. This is simply not possible (at least not with a lot of effort) with traditional testing techniques today.

I believe that even if it seems redundant, thoroughly checking testing paths that might repeat previously-tested paths is important for determining the root cause of a test failure. For example, imagine generated tests that include the paths:

A -> B
A -> B -> C
A -> B -> D

It might seem redundant to test B if that state is already being covered in the other tests, but if the tests for C and D fail, it's useful to determine if the test for B failed as well, which would be the root cause of the other tests failing.

[dsedmak]

Actually, the examples at xstate.js.org/docs/packages/xstate-graph are also examples of both problems.

Keep in mind, the "problematic" examples are still better solutions (in terms of test coverage) than existing techniques today 😉

I completely agree. Model-based testing gives us good test coverage AND saves time writing and maintaining tests :astonished:. That's why I'm here.

Additionally, it is possible to recognize when potential transitions were not taken (due to a guard preventing the transition) and warn the developer. This is simply not possible (at least not with a lot of effort) with traditional testing techniques today.

This is true, but is not really what I was talking about. Following the shortest paths can skip certain transitions even in the absence of guards on any transition. If we used a method where that doesn't happen there would be no need to warn the developer. Also a guarded transition might be skipped many times before it's finally taken so any warnings would have to come at the end of the test.

I believe that even if it seems redundant, thoroughly checking testing paths that might repeat previously-tested paths is important for determining the root cause of a test failure. For example, imagine generated tests that include the paths:

A -> B
A -> B -> C
A -> B -> D

It might seem redundant to test B if that state is already being covered in the other tests, but if the tests for C and D fail, it's useful to determine if the test for B failed as well, which would be the root cause of the other tests failing.

As for my duplicated work argument I still believe it has merit. The way you describe it if an error happened on the first event/transition every single test would still run and then fail. If every transition was only taken once we could short-circuit the tests following the broken transition.

The tests could be generated roughly like this: https://repl.it/repls/WornSurefootedListener (here I am assuming that transitions from states 2 to 5 and 4 to 5 produce different contexts so we continue executing tests). Showing the tests as a tree might better reveal the ROOT :sweat_smile: cause of the problem.

[davidkpiano]

Following the shortest paths can skip certain transitions event in the absence of guards. If we used a method where that doesn't happen there would be no need to warn the developer.

Such a method would require that:

1. a machine can reach a state S...
2. an event E can be generated...

...such that S and E satisfy the conditional (and/or negation of the conditional) that guards any given transition.

As it turns out, this is not easily solvable, and is essentially the Boolean Satisfiability Problem (which is NP-complete).

That's why, unless we use some SAT-solver, the best thing to do is simply inform the developer (at the end of the tests) that certain transitions were not taken.

[dsedmak]

You are right of course that we cannot easily find the right S and E to satisfy the guard condition. I was talking about unguarded transitions. Example where all transitions are unguarded:

• Traversing the shortest paths to all possible states would mean transition E is never taken and some duplicated work.
• Traversing the simple paths to all possible states would mean substantial duplicated work.
• Traversing in breadth-first order while not expanding visited states would take all transitions exactly once and visit every state making for a shorter test while fully exercising the machine.

Interestingly even if there were guards on some transitions as long as the conditions only depend on context properties that were never modified based on values coming from outside the machine (event.xx) the test would eventually both pass and fail the guard. A good example of this is the fetch machine that loads by default on the visualizer. Since ctx.attempts is increased by a constant just letting the machine execute would eventually cause the machine to take the transient transition to failure.

I'll drop this for now but maybe once we actually start implementing this I can contribute back upstream.