Possible missing cycle

[vinpogo]

I currently am running dependency cruiser in my project and wanted to adopt rev-dep. I noticed some discrepancies in numbers reported. Although this example reports the same number of circular issues, it shows the underlying issue (i hope 🤞 )

Graph

• a.ts imports b.ts and c.ts
• b.ts imports a.ts and c.ts
• c.ts imports a.ts and b.ts

Observed discrepancy

Both tools report 3 circular issues, but one cycle differs:

• dependency-cruiser reports:

  • a.ts -> b.ts -> a.ts
  • a.ts -> c.ts -> a.ts
  • b.ts -> c.ts -> b.ts

• rev-dep reports:

  • a.ts -> b.ts -> a.ts
  • a.ts -> b.ts -> c.ts -> a.ts
  • b.ts -> c.ts -> b.ts

[jayu]

This is not a bug, it's rather a result of tools using different algorithms for finding circular dependencies.

Rev-dep uses Depth-First Search (DFS) based algorithm with recursion stack which finds the possible cycles directly when traversing the graph, rather than, like other tools, first find Strongly Connected Components (SCC) and derive the representations of the cycles from SCC.

So rev-dep output is related to the order in which graph is traversed.

graph TD;
    A-->B;
    A-->C;
    B-->A;
    B-->C;
    C-->A;
    C-->B;

Loading

Comparing the path-based representation of cyclic imports can be confusing, because the paths can be constructed from different nodes and can go through different nodes.

For example

c->a->c
b->a->b
c->b->c

Is also valid path-based representation of cyclic dependencies in this graph.

You should think about path-based representation as a hint, which imports should be refactored to remove cyclic dependency.
For this purpose, both tools give useful hints

• dependency-cruiser reports:

  • a.ts -> b.ts -> a.ts - need to cut a->b or b->a
  • a.ts -> c.ts -> a.ts - need to cut a->c or c->a
  • b.ts -> c.ts -> b.ts - need to cut b->c or c->b

• rev-dep reports:

  • a.ts -> b.ts -> a.ts - need to cut a->b or b->a
  • a.ts -> b.ts -> c.ts -> a.ts - need to cut a->b or b->c or c->a
  • b.ts -> c.ts -> b.ts - need to cut b->c or c->b

There is no single correct way to remove cycles in this graph, but you will manage to remove all circular deps if you follow hints from one or the other tool.

I imagine that rev-dep could implement different circular deps identification alogs and let user choose, but the current one is the fastest I was able to implement.

[vinpogo]

thanks for the explanation!

I think the current algo is fine, you just need to be aware that if you cut one dependency in a cycle, the total number doesn't necessarily reduce as a new one can pop up. In the example above:

a.ts -> b.ts -> c.ts -> a.ts - need to cut a->b or b->c or c->a

Cutting a->b removes this long cycle, but a->c->a would now be reported, right?

So rev-dep output is related to the order in which graph is traversed.

Does this mean that if i change the entrypoint and/or re-order import statements the reported cycles can change?

In any way, i think this project is great, and will be able to replace dependency-cruiser for my needs.

[jayu]

Cutting a->b removes this long cycle, but a->c->a would now be reported, right?

Yes

Does this mean that if i change the entrypoint and/or re-order import statements the reported cycles can change?

Yes

[jayu]

I've implemented and released SCC based algorithm in release 2.13.0

rev-dep circular --algorithm SCC

Config file based checks can be also set up to use this new algo. By default the previous DFS algo will be used