chore(no-loop): use BFS to find loops

[marstamm]

This uses breadth-first search, cf. detailed rationale. As a result it reduces the time needed for traversing the diagram from SUPPORT-22488 from ~1 minute to 6ms.

Related to https://github.com/camunda/camunda-modeler/issues/4401

Try it out with

npx @bpmn-io/sr camunda/linting -l camunda/bpmnlint-plugin-camunda-compat#make-loop-detection-more-perfomant

[marstamm]

I only reworked the traversal code of the rule. We are treating the diagram as a directed graph. Starting with the complete diagram, we follow these steps:

1. Create a subgraph that only contains elements that can be part of an infinite loop (eg. filter out ServiceTasks, ...)
2. On this subgraph, perform a breadth-first search. Should we find an element that we already visited, we found a loop
3. As we already filtered for elements that do no computing, we report the error

Steps 1 and 2 are new/reworked by me, rest is taken from the original lint rule.

[nikku]

What yields the massive performance improvement that we're seeing? This is the relevant learning that I'd like to spread.

[marstamm]

We assume the worst case of a fully connected diagram with V=n elements and E=n^2 edges. The previous Algorithm was:

• For every element that could be part of a loop (n)
  • Traverse all possible paths starting from this element. In the worst case, this could be (n!)

We did not do any caching, so the same paths would be calculated multiple times for each new starting element.

In the worst case, this yields O(n!), which is quite horrible. BFS is O(V+E), so O(n^2), with much lower complexity in real-world cases.

[marstamm]

Loop detection doesn't work for cases where a gateway has already been marked as visited but is in fact part of a loop that hasn't been detected yet. For example:

[philippfromme]

Remembering visited nodes and returning early when visiting them again breaks in a case where

1. The first branch marked a gateway as visited

2. The second branch returns early when visiting that gateway

[marstamm]

The Issue we have is that the loop detection works, but we ignore certain loops because it requires a Task in it to be "valid". Therefore, I think we should do more pre-processing so our graph can be traversed and any loop found is actually a loop.

This would look like this

Step 0: Initial Diagram

Step 1: Remove Blocking elements (filter, O(n))

Step 2: Treat allowed but non-required elements as annotated edges. (BFS, O(n^2))

In the resulting graph, any Loop will be a valid loop.

This increases the complexity as we need to iterate over the complete graph twice, but will not change the O-complexity O(2*n^2) = O(n^2)

[nikku]

@marstamm In your algorithm proposal (https://github.com/camunda/bpmnlint-plugin-camunda-compat/pull/165#issuecomment-2197131973), how would you handle gateway-only situations that can be loops, too:

[marstamm]

Those will be ignored. The resulting "reduced" graph will be empty, because no required Element exists.

I synced with Philipp on Friday, we want to align with the Zeebe implementation. For the Zeebe implementation, it is required for the loop to include a Blank-, Manual- or CallActivity

[marstamm]

I added the 2-step process described in https://github.com/camunda/bpmnlint-plugin-camunda-compat/pull/165#issuecomment-2197131973 and added additional test-cases that cover the previously broken scenarios.

We now use a custom Graph Structure to make traversal and annotation of paths easier: https://github.com/camunda/bpmnlint-plugin-camunda-compat/blob/85bd00872d5b6bc128276f7d197443bacabe2a41/rules/camunda-cloud/no-loop.js#L69-L74

All reported Loops now start at a Task or CallActivity. I could not detect any noticeable decreased performance to the previous implementation:

[nikku]

@marstamm Let's get this released and integrated.

[marstamm]

Already on it 🏃