improve no-cycle rule performance by leveraging strongly connected components

[soryy708]

I see that the no-cycle uses ExportMap to get a cached dependency graph, and then run BFS to find cycles.

... Are we running BFS, on the entire dependency graph, for every file we lint?

I think we can improve performance in this way:

• When a file changes, run Tarjan's SCC algorithm to find SCCs in linear time
• To check if any two files have a cycle, check if they belong to the same SCC (can be very fast, depending on data structure)
• If the files are not in the same SCC, we don't need to search for cycles, because there can't be any
• To get the import chain to report the directed cycle, search only the SCC (as opposed to the entire dependency graph)

An SCC means that every node that belongs to it has a path to all other nodes that belong to it. Therefore if two nodes belong to the same SCC, they have a path to each other, therefore there is a directed cycle = circular dependency between them.
(The difference between an SCC and a directed cycle is that an SCC may contain at least one directed cycle)

By the way, I'm not sure that BFS is the right algorithm for cycle detection, consider DFS instead.

Stackoverflow: Why DFS and not BFS for finding cycle in graphs

[ljharb]

I have no attachment to any particular algorithm; as long as it passes tests and is robust and correct, whatever will perform best is great. I'd be happy to review a PR.

[lukaselmer]

Sounds interesting, let's try it!

[soryy708]

@benmosher I think you were the original contributor of the no-cycle rule?

[soryy708]

The SCC optimization has been released, try v >=2.30.0