camunda / dmn-scala

DMN engine written in Scala
Apache License 2.0
34 stars 15 forks source link

Fix incorrect cyclic dependency detection #214

Closed remcowesterhoud closed 1 year ago

remcowesterhoud commented 1 year ago

Description

image

In this model there is no cyclic dependency. The parser incorrectly gives a warning that there is a cyclic dependency.

The cause lays in the cyclic dependency check. This check takes a list of decisions it still needs to visit. It builds this list from the dependencies of previous decisions that have been checked. The scoping of this check is wrong. It checks the dependencies in a cyclic way for the entire DRG. With each cycle we append to the visited elements. Upon reaching an end state, we do not clear this list of visited elements.

For the example DRG this means:

  1. We check for cyclic dependencies in C
  2. We check for cyclic dependencies in A (visited C)
  3. A doesn't have any more dependencies, yet we append it to the list of visited elements and continue with the other decisions
  4. We check for cyclic dependencies in B (visited C and A)
  5. B finds a dependency on A, we've already visited A. As a result we incorrectly assume a cyclic dependency here.

This PR fixes the scoping by not passing a list of decisions to visit, but instead keeping it scoped to a single one. By checking if any dependencies exist with a cycle for this decision we don't run into the issue mentioned above.

Related issues

closes #213

saig0 commented 1 year ago

@remcowesterhoud thank you for the fast fix. :rocket: I'll have a look at it soon.