[BUG] ELSA3 Duplicate and Missing Connections in Descendants Method for Cyclic Workflows

[RuslanSay]

Description

The Descendants method in the ConnectionsExtensions class returns incorrect results for workflows with cyclic connections. Specifically, it produces duplicate entries and skips some connections due to a flawed cycle-handling mechanism.

Steps to Reproduce

1. Create a workflow with the following setup:

using System.Text.Json;
using Elsa.Workflows.Activities;
using Elsa.Workflows.Activities.Flowchart.Extensions;
using Elsa.Workflows.Activities.Flowchart.Models;

var writeHello = new WriteLine("Hello") { Id = "Hello" };
var readLine = new ReadLine { Id = "readLine" };
var writeBranch1 = new WriteLine("Branch1") { Id = "Branch1" };
var writeBranch2 = new WriteLine("Branch2") { Id = "Branch2" };

var connection = new Connection[]
{
    new(writeHello, readLine),
    new(readLine, writeBranch1),
    new(readLine, writeBranch2),
    new(writeBranch1, readLine),
    new(writeBranch2, readLine)
};

var descendants = connection.Descendants(readLine);
var simpleDescendants = descendants.Select(x => new { Source = x.Source.Activity.Id, Target = x.Target.Activity.Id });
Console.WriteLine(JsonSerializer.Serialize(simpleDescendants));

3. Run the code to evaluate the Descendants method for the readLine activity.

Attachments

• JSON is provided in the code above.

Reproduction Rate

Occurs every time for workflows with cycles.

Additional Configuration

This issue is specific to workflows containing cyclic connections.

Expected Behavior

The Descendants method should return all unique descendant connections, correctly handling cycles without duplicates or missing connections.

Actual Behavior

The method returns an incorrect list of descendant connections.

Example Output

Here is the result of the Descendants method for the writeHello activity:

[
  {
    "Source": "readLine",
    "Target": "Branch1"
  },
  {
    "Source": "Branch1",
    "Target": "readLine"
  },
  {
    "Source": "readLine",
    "Target": "Branch2"
  },
  {
    "Source": "readLine",
    "Target": "Branch2"
  }
]

The output contains a duplicate connection from readLine to Branch2 and omits the connection from Branch2 to readLine.

Troubleshooting Attempts

• Analyzed the Descendants implementation and identified the issue in how the visitedActivities set is used.
• Possible Fix: Instead of tracking visited activities (visitedActivities), it might be more appropriate to track visited connections. This approach would ensure that connections are not revisited in cyclic workflows while still allowing all unique paths to be explored.

Additional Context

The issue occurs because the algorithm does not handle cycles properly and incorrectly considers some nodes multiple times while skipping others.

Related Issues

None found.

[RuslanSay]

Due to incorrect Descendants calculations, the LeftInboundActivities method also produces incorrect results (as it excludes Descendants). For example, this workflow will not work because the Delay activity is not scheduled, as it is waiting for the first WriteLine activity, not recognizing that it is one of its descendants.

test-cycle.json

[RuslanSay]

Also, Descendants affects Join. If you traverse the workflow twice through httpEndpoint 3b77093c6dc43ee, on the second loop, the Join will not trigger.

The behavior of Join is not entirely straightforward. During execution, Join cancels activities to the left of it, excluding Descendants. With the current incorrect Descendants, such a cyclic Join does not cancel one of the branches. However, if the Descendants is fixed, it will stop canceling activities, which seems incorrect. It suggests that another calculation might be needed to track on which "loop" the left-side activities were scheduled, since technically they are descendants of the Join from the previous loop.

test-join.json

[RuslanSay]

I just saw the fix #6138. Considering this, we need to check if the Join activity works correctly and whether it cancels incoming activities.