Bug Description

We've been seeing chunk names occasionally being different between multiple webpack runs on the same source code, causing broken HTML->JS links if not deployed at the same time. This can happen even when using chunkIds: "deterministic".

The cause is a bug in findGraphRoots that can make it return different results for the same graph with different orderings.

Link to Minimal Reproduction and step to reproduce

Since the nondeterminism is dependent on module processing order, it can't be reproduced reliably. However, it's easy to reproduce the underlying findGraphRoots bug:

> const g1 = {"A":["C","B"], "B":["C"], "C":["A"]}
> const g2 = {"A":["B","C"], "B":["C"], "C":["A"]}
> require("webpack/lib/util/findGraphRoots")(Object.keys(g1), m => g1[m])
[ 'C' ]
> require("webpack/lib/util/findGraphRoots")(Object.keys(g2), m => g2[m])
[ 'C', 'A' ]

Expected Behavior

The set of roots should be the same regardless of ordering.

Actual Behavior

With g1, findGraphRoots's reverse-order DFS goes A->B->C->A and puts all 3 nodes in a {A,B,C} cycle. C has the most inward edges (2) and is returned.

But with g2, it goes A->C->A first, finding an {A,C} cycle. By the time it finds the A->B->C path, C is already marked "done", so B is never added to the cycle! A and C both have just one inward edge within the {A,C} subgraph, and both are returned.

Environment

N/A

Is this a regression?

None

Last Working Version

No response

Additional Context

Could be worked around with --parallelism 1.

I have a fix for findGraphRoots.js: jeffrey-easyesi/webpack@main...fix-findGraphRoots
I could make a pull request, but if a CLA is required it'll probably take a long time to get permission.