circular-dependency-plugin Replace cycle detection algorithm with Tarjan's strongly connected components algorithm

Replace cycle detection algorithm with Tarjan's strongly connected components algorithm

Open hedgepigdaniel opened this issue 4 years ago • 5 comments

I noticed that this plugin was taking significant time (almost a second for a 5500 module project) to check for cycles in hot rebuilds. Tarjan's strongly connected components algorithm as I understand is the fastest way to find dependency cycles. Its running time is linear in the number of vertices (modules) + edges (dependencies).

My best guess is that the existing algorithm is quadratic in the number of modules, because for each module in the compilation, all its dependencies are traversed recursively, which in the worst case also visits each module in the compilation.

I haven't done benchmarks, but in the same project after this change, this plugin is no longer perceptible in the ProgressPlugin output.

I also changed the output:

One cycle is output only once, not separately for each file it contains
For cycles when some modules in the cycle are excluded - it now outputs all modules in the cycle even if some are excluded. This makes more sense IMO, since otherwise it prints e.g. a.js -> b.js even if a.js does not directly import b.js, which is confusing. If all modules in a cycle are excluded, no warning is generated (I added a test to enforce this)

Sep 19 '19 11:09 hedgepigdaniel

Thanks for sending this, I appreciate the effort that went into this. Since this reworks a lot of the core functionality I'll have to spend some time reviewing it, and I probably won't get to it until the weekend, I'll try to do a thorough review as soon as I can.