fix: deterministic findGraphRoots regardless of edge ordering (#20452)

veeceey · web-flow · commit 1313375f935c · 2026-02-17T01:06:07.000+03:00
diff --git a/.changeset/giant-turkeys-hide.md b/.changeset/giant-turkeys-hide.md
@@ -0,0 +1,5 @@
+---
+"webpack": patch
+---
+
+fix: deterministic findGraphRoots regardless of edge ordering
diff --git a/.changeset/small-dingos-add.md b/.changeset/small-dingos-add.md
@@ -0,0 +1,5 @@
+---
+"webpack": patch
+---
+
+Fixed deterministic search for graph roots regardless of edge order.
diff --git a/lib/util/findGraphRoots.js b/lib/util/findGraphRoots.js
@@ -9,7 +9,6 @@ const NO_MARKER = 0;
 const IN_PROGRESS_MARKER = 1;
 const DONE_MARKER = 2;
 const DONE_MAYBE_ROOT_CYCLE_MARKER = 3;
-const DONE_AND_ROOT_MARKER = 4;
 
 /**
  * @template T
@@ -32,9 +31,9 @@ class Node {
 		this.item = item;
 		/** @type {Nodes<T>} */
 		this.dependencies = new Set();
-		this.marker = NO_MARKER;
-		/** @type {Cycle<T> | undefined} */
-		this.cycle = undefined;
+		/** @type {Cycle<T>} */
+		this.cycle = new Cycle();
+		this.cycle.nodes.add(this);
 		this.incoming = 0;
 	}
 }
@@ -46,6 +45,7 @@ class Cycle {
 	constructor() {
 		/** @type {Nodes<T>} */
 		this.nodes = new Set();
+		this.marker = NO_MARKER;
 	}
 }
 
@@ -83,11 +83,6 @@ module.exports = (items, getDependencies) => {
 		}
 	}
 
-	// Set of current root modules
-	// items will be removed if a new reference to it has been found
-	/** @type {Nodes<T>} */
-	const roots = new Set();
-
 	// Set of current cycles without references to it
 	// cycles will be removed if a new reference to it has been found
 	// that is not part of the cycle
@@ -96,12 +91,12 @@ module.exports = (items, getDependencies) => {
 
 	// For all non-marked nodes
 	for (const selectedNode of itemToNode.values()) {
-		if (selectedNode.marker === NO_MARKER) {
+		if (selectedNode.cycle.marker === NO_MARKER) {
 			// deep-walk all referenced modules
 			// in a non-recursive way
 
 			// start by entering the selected node
-			selectedNode.marker = IN_PROGRESS_MARKER;
+			selectedNode.cycle.marker = IN_PROGRESS_MARKER;
 
 			// keep a stack to avoid recursive walk
 			/** @type {StackEntry<T>[]} */
@@ -122,97 +117,85 @@ module.exports = (items, getDependencies) => {
 					const dependency =
 						/** @type {Node<T>} */
 						(topOfStack.openEdges.pop());
-					switch (dependency.marker) {
+					const cycle = dependency.cycle;
+					switch (cycle.marker) {
 						case NO_MARKER:
 							// dependency has not be visited yet
 							// mark it as in-progress and recurse
 							stack.push({
 								node: dependency,
 								openEdges: [...dependency.dependencies]
 							});
-							dependency.marker = IN_PROGRESS_MARKER;
+							cycle.marker = IN_PROGRESS_MARKER;
 							break;
 						case IN_PROGRESS_MARKER: {
 							// It's a in-progress cycle
-							let cycle = dependency.cycle;
-							if (!cycle) {
-								cycle = new Cycle();
-								cycle.nodes.add(dependency);
-								dependency.cycle = cycle;
-							}
 							// set cycle property for each node in the cycle
 							// if nodes are already part of a cycle
 							// we merge the cycles to a shared cycle
+							/** @type {Set<Cycle<T>>} */
+							const toMerge = new Set();
 							for (
 								let i = stack.length - 1;
-								stack[i].node !== dependency;
+								stack[i].node.cycle !== cycle;
 								i--
 							) {
-								const node = stack[i].node;
-								if (node.cycle) {
-									if (node.cycle !== cycle) {
-										// merge cycles
-										for (const cycleNode of node.cycle.nodes) {
-											cycleNode.cycle = cycle;
-											cycle.nodes.add(cycleNode);
-										}
-									}
-								} else {
-									node.cycle = cycle;
-									cycle.nodes.add(node);
+								toMerge.add(stack[i].node.cycle);
+							}
+							for (const cycleToMerge of toMerge) {
+								// merge cycles
+								for (const cycleNode of cycleToMerge.nodes) {
+									cycleNode.cycle = cycle;
+									cycle.nodes.add(cycleNode);
 								}
 							}
 							// don't recurse into dependencies
 							// these are already on the stack
 							break;
 						}
-						case DONE_AND_ROOT_MARKER:
-							// This node has be visited yet and is currently a root node
-							// But as this is a new reference to the node
-							// it's not really a root
-							// so we have to convert it to a normal node
-							dependency.marker = DONE_MARKER;
-							roots.delete(dependency);
-							break;
 						case DONE_MAYBE_ROOT_CYCLE_MARKER:
 							// This node has be visited yet and
 							// is maybe currently part of a completed root cycle
 							// we found a new reference to the cycle
 							// so it's not really a root cycle
 							// remove the cycle from the root cycles
 							// and convert it to a normal node
-							rootCycles.delete(/** @type {Cycle<T>} */ (dependency.cycle));
-							dependency.marker = DONE_MARKER;
+							rootCycles.delete(/** @type {Cycle<T>} */ (cycle));
+							cycle.marker = DONE_MARKER;
 							break;
 						// DONE_MARKER: nothing to do, don't recurse into dependencies
 					}
 				} else {
 					// All dependencies of the current node has been visited
 					// we leave the node
 					stack.pop();
-					topOfStack.node.marker = DONE_MARKER;
+					// Only mark the cycle as done when we leave the outermost
+					// node of the cycle on the stack
+					if (
+						stack.length === 0 ||
+						topOfStack.node.cycle !== stack[stack.length - 1].node.cycle
+					) {
+						topOfStack.node.cycle.marker = DONE_MARKER;
+					}
 				}
 			}
 			const cycle = selectedNode.cycle;
-			if (cycle) {
-				for (const node of cycle.nodes) {
-					node.marker = DONE_MAYBE_ROOT_CYCLE_MARKER;
-				}
-				rootCycles.add(cycle);
-			} else {
-				selectedNode.marker = DONE_AND_ROOT_MARKER;
-				roots.add(selectedNode);
-			}
+			cycle.marker = DONE_MAYBE_ROOT_CYCLE_MARKER;
+			rootCycles.add(cycle);
 		}
 	}
 
+	// Set of root modules
+	/** @type {T[]} */
+	const roots = [];
+
 	// Extract roots from root cycles
 	// We take the nodes with most incoming edges
 	// inside of the cycle
 	for (const cycle of rootCycles) {
 		let max = 0;
 		/** @type {Nodes<T>} */
-		const cycleRoots = new Set();
+		const cycleRoots = new Set(cycle.nodes);
 		const nodes = cycle.nodes;
 		for (const node of nodes) {
 			for (const dep of node.dependencies) {
@@ -228,14 +211,12 @@ module.exports = (items, getDependencies) => {
 			}
 		}
 		for (const cycleRoot of cycleRoots) {
-			roots.add(cycleRoot);
+			roots.push(cycleRoot.item);
 		}
 	}
 
 	// When roots were found, return them
-	if (roots.size > 0) {
-		return Array.from(roots, (r) => r.item);
-	}
+	if (roots.length > 0) return roots;
 
 	throw new Error("Implementation of findGraphRoots is broken");
 };
diff --git a/test/configCases/chunk-graph/deterministic-roots/a.js b/test/configCases/chunk-graph/deterministic-roots/a.js
@@ -0,0 +1,10 @@
+import { getC } from "./c";
+import { getB } from "./b";
+
+export function getA() {
+	return "a";
+}
+
+export function getCombined() {
+	return getA() + getB() + getC();
+}
diff --git a/test/configCases/chunk-graph/deterministic-roots/b.js b/test/configCases/chunk-graph/deterministic-roots/b.js
@@ -0,0 +1,5 @@
+import { getC } from "./c";
+
+export function getB() {
+	return "b" + getC();
+}
diff --git a/test/configCases/chunk-graph/deterministic-roots/c.js b/test/configCases/chunk-graph/deterministic-roots/c.js
@@ -0,0 +1,5 @@
+import { getA } from "./a";
+
+export function getC() {
+	return "c" + getA();
+}
diff --git a/test/configCases/chunk-graph/deterministic-roots/index.js b/test/configCases/chunk-graph/deterministic-roots/index.js
@@ -0,0 +1,8 @@
+import { getCombined } from "./a";
+
+it("should produce deterministic output with cyclic dependencies", () => {
+	const result = getCombined();
+	expect(result).toContain("a");
+	expect(result).toContain("b");
+	expect(result).toContain("c");
+});
diff --git a/test/configCases/chunk-graph/deterministic-roots/webpack.config.js b/test/configCases/chunk-graph/deterministic-roots/webpack.config.js
@@ -0,0 +1,8 @@
+"use strict";
+
+/** @type {import("../../../../").Configuration} */
+module.exports = {
+	optimization: {
+		concatenateModules: true
+	}
+};

-Original file line number
+Diff line change
@@ @@ -0,0 +1,5 @@ @@
 +---
 +"webpack": patch
 +---
++
 +fix: deterministic findGraphRoots regardless of edge ordering