fix: deterministic findGraphRoots regardless of edge ordering#20452
Conversation
…dge ordering The findGraphRoots algorithm could return different root sets for the same graph depending on the order edges were listed. This caused nondeterministic chunk names between webpack runs, breaking HTML->JS links in deployments. The root cause was that DFS visit markers were per-node instead of per-cycle. When nodes A,B,C form a cycle but the DFS discovers a partial cycle first (e.g. A->C->A), node C gets marked as DONE before B is processed. Later when B->C is encountered, C is already "done" so B never joins the cycle, producing an incomplete cycle and wrong root selection. The fix moves markers from nodes to cycles. Each node starts in its own singleton cycle, and cycles are merged as back-edges are found. Since all nodes in a cycle share the same marker, the algorithm correctly identifies all cycle members regardless of traversal order. Fixes webpack#20445
🦋 Changeset detectedLatest commit: aae7729 The changes in this PR will be included in the next version bump. This PR includes changesets to release 1 package
Not sure what this means? Click here to learn what changesets are. Click here if you're a maintainer who wants to add another changeset to this PR |
|
Please accept CLA and add a test case |
|
Thanks for the review! I've added a changeset now. The test case was already included in the original commit — Working on the CLA as well. |
alexander-akait
left a comment
There was a problem hiding this comment.
Please rewrite tests and accept CLA, no need to send a new PR without accepting CLA, because we can't merge your fixes
test/findGraphRoots.unittest.js
Outdated
| const g2 = { A: ["B"], B: ["C"], C: ["D"], D: ["B", "A"] }; | ||
| expect(roots(g1)).toEqual(roots(g2)); | ||
| }); | ||
| }); |
There was a problem hiding this comment.
Please create a test case in configCases, no need to create unit tests, they are useless for such cases
There was a problem hiding this comment.
Done — I've replaced the unit test with a configCase at test/configCases/chunk-graph/deterministic-roots. It sets up three modules (a, b, c) with cyclic imports (a→c→a, a→b→c) and concatenateModules enabled, which exercises the findGraphRoots path. The test passes locally.
Move the findGraphRoots test from a standalone unittest to a configCase under chunk-graph/deterministic-roots as requested by the reviewer. The test exercises cyclic module dependencies (A -> C -> A, A -> B -> C) to verify deterministic graph root selection. Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>
|
Hey @alexander-akait, thanks for the feedback. I've pushed a new commit that replaces the unit test with a configCase under |
|
@CLAassistant check |
|
Both items should be resolved now — CLA is signed and passing, and the configCase test at |
|
@veeceey I can't reproduce freeze on your example |
|
Hey @alexander-akait, thanks for taking a look! To clarify — it's not a freeze, it's nondeterministic output. The same graph can produce different root sets depending on which order the edges happen to be iterated. Here's the minimal repro: const { findGraphRoots } = require("./lib/util/findGraphRoots");
// Same graph, just different edge ordering for node A
const g1 = {"A":["C","B"], "B":["C"], "C":["A"]};
const g2 = {"A":["B","C"], "B":["C"], "C":["A"]};
console.log(findGraphRoots(Object.keys(g1), m => g1[m]));
// => ['C']
console.log(findGraphRoots(Object.keys(g2), m => g2[m]));
// => ['C', 'A'] <-- different roots for the same graphBoth calls describe the exact same cycle (A→B→C→A), but because In practice this means chunk names can differ between builds if module discovery order changes (e.g. parallel file system reads), which is the issue reported in #20445. The fix makes the algorithm track cycle membership so that once any back-edge merges nodes into a cycle, all nodes in that cycle share the same marker — making the result independent of edge ordering. Let me know if you'd like me to adjust anything! |
|
@veeceey Do you copied this answer from AI? |
|
This PR is packaged and the instant preview is available (1313375). Install it locally:
npm i -D webpack@https://pkg.pr.new/webpack@1313375
yarn add -D webpack@https://pkg.pr.new/webpack@1313375
pnpm add -D webpack@https://pkg.pr.new/webpack@1313375 |
Fixes #20445
findGraphRootscould return different root sets for the same graph depending on edge ordering. This caused nondeterministic chunk names across webpack runs, which breaks deployments when HTML and JS bundles aren't deployed atomically.Root cause
DFS visit markers were stored per-node. When the DFS discovers a partial cycle first (e.g. A->C->A in a graph where A,B,C all form a cycle), C gets marked DONE before B is processed. When B->C is later encountered, C is already "done" so B never joins the cycle. This produces an incomplete cycle and wrong root selection depending on which edges happen to be traversed first.
Repro from the issue:
Fix
Move markers from individual nodes to cycles. Each node starts in its own singleton cycle, and cycles are merged as back-edges are found during DFS. Since all nodes in a merged cycle share the same marker object, the algorithm correctly identifies all cycle members regardless of traversal order.
Also added unit tests for
findGraphRoots- it previously had no test coverage.