From 9bce51f651aad297ef9eb6df832bfdaf1de05d84 Mon Sep 17 00:00:00 2001
From: WXL <wl_5969728@163.com>
Date: 星期三, 22 四月 2026 14:27:54 +0800
Subject: [PATCH] 青岛推送
---
node_modules/webpack/lib/util/findGraphRoots.js | 193 +++++++++++++++++++++---------------------------
1 files changed, 84 insertions(+), 109 deletions(-)
diff --git a/node_modules/webpack/lib/util/findGraphRoots.js b/node_modules/webpack/lib/util/findGraphRoots.js
index 67cbbea..5dbb5b5 100644
--- a/node_modules/webpack/lib/util/findGraphRoots.js
+++ b/node_modules/webpack/lib/util/findGraphRoots.js
@@ -8,48 +8,50 @@
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;
+const CANDIDATE_MARKER = 3;
/**
+ * Defines the nodes type used by this module.
* @template T
* @typedef {Set<Node<T>>} Nodes
*/
/**
- * @template T
- * @typedef {Set<Cycle<T>>} Cycles
- */
-
-/**
+ * Represents the node runtime component.
* @template T
*/
class Node {
/**
+ * Creates an instance of Node.
* @param {T} item the value of the node
*/
constructor(item) {
this.item = item;
/** @type {Nodes<T>} */
this.dependencies = new Set();
- this.marker = NO_MARKER;
- /** @type {Cycle<T> | undefined} */
- this.cycle = undefined;
+ /** @type {SCC<T>} */
+ this.scc = new SCC();
+ // Each node starts as a single-node SCC
+ this.scc.nodes.add(this);
+ /** @type {number} */
this.incoming = 0;
}
}
/**
+ * SCC (strongly connected component)
* @template T
*/
-class Cycle {
+class SCC {
constructor() {
/** @type {Nodes<T>} */
this.nodes = new Set();
+ this.marker = NO_MARKER;
}
}
/**
+ * Defines the stack entry type used by this module.
* @template T
* @typedef {object} StackEntry
* @property {Node<T>} node
@@ -57,6 +59,7 @@
*/
/**
+ * Returns graph roots of the items.
* @template T
* @param {Iterable<T>} items list of items
* @param {(item: T) => Iterable<T>} getDependencies function to get dependencies of an item (items that are not in list are ignored)
@@ -70,10 +73,10 @@
itemToNode.set(item, node);
}
- // early exit when there is only a single item
+ // Early exit when there is only one node
if (itemToNode.size <= 1) return items;
- // grab all the dependencies
+ // Build graph edges
for (const node of itemToNode.values()) {
for (const dep of getDependencies(node.item)) {
const depNode = itemToNode.get(dep);
@@ -83,27 +86,16 @@
}
}
- // 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();
+ // All candidate root SCCs, they will be removed once an incoming edge is found
+ /** @type {Set<SCC<T>>} */
+ const rootSCCs = 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
- /** @type {Cycles<T>} */
- const rootCycles = new Set();
-
- // For all non-marked nodes
for (const selectedNode of itemToNode.values()) {
- if (selectedNode.marker === NO_MARKER) {
- // deep-walk all referenced modules
- // in a non-recursive way
+ // DFS walk only once per unseen SCC
+ if (selectedNode.scc.marker === NO_MARKER) {
+ selectedNode.scc.marker = IN_PROGRESS_MARKER;
- // start by entering the selected node
- selectedNode.marker = IN_PROGRESS_MARKER;
-
- // keep a stack to avoid recursive walk
+ // Keep a stack to avoid recursive walk
/** @type {StackEntry<T>[]} */
const stack = [
{
@@ -112,130 +104,113 @@
}
];
- // process the top item until stack is empty
while (stack.length > 0) {
const topOfStack = stack[stack.length - 1];
- // Are there still edges unprocessed in the current node?
+ // Process one unvisited outgoing edge if available
if (topOfStack.openEdges.length > 0) {
- // Process one dependency
const dependency =
/** @type {Node<T>} */
(topOfStack.openEdges.pop());
- switch (dependency.marker) {
+ const depSCC = dependency.scc;
+ switch (depSCC.marker) {
case NO_MARKER:
- // dependency has not be visited yet
- // mark it as in-progress and recurse
+ // First time we see this SCC: enter it
stack.push({
node: dependency,
openEdges: [...dependency.dependencies]
});
- dependency.marker = IN_PROGRESS_MARKER;
+ depSCC.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
+ // Back-edge to an SCC that is still on the stack
+ // Example:
+ // A -> B -> C -> D
+ // ^ |
+ // |_________|
+ // If we are at `D` and traverse `D` -> `B`, then `B/C/D` must be in one SCC
+ /** @type {Set<SCC<T>>} */
+ const sccsToMerge = new Set();
for (
let i = stack.length - 1;
- stack[i].node !== dependency;
+ stack[i].node.scc !== depSCC;
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);
+ sccsToMerge.add(stack[i].node.scc);
+ }
+ for (const sccToMerge of sccsToMerge) {
+ for (const nodeInMergedSCC of sccToMerge.nodes) {
+ nodeInMergedSCC.scc = depSCC;
+ depSCC.nodes.add(nodeInMergedSCC);
}
}
- // 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);
+ case CANDIDATE_MARKER:
+ // This finished SCC was previously considered as root SCC
+ // We just found a new incoming edge, so it is no longer a candidate
+ rootSCCs.delete(/** @type {SCC<T>} */ (depSCC));
+ depSCC.marker = DONE_MARKER;
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;
+ case DONE_MARKER:
+ // Already finalized and not a candidate
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
+ // All dependencies of the current node have been processed
+ // So we leave the node
stack.pop();
- topOfStack.node.marker = DONE_MARKER;
+ // Mark an SCC as DONE only when the popped node is the last
+ // node from that SCC remaining on the current stack.
+ // A -> B -> C -> D
+ // ^ |
+ // |_________|
+ // If `B` is popped and the new stack top is `A`, they are in
+ // different SCCs, so B's SCC can be finalized.
+ if (
+ stack.length &&
+ topOfStack.node.scc !== stack[stack.length - 1].node.scc
+ ) {
+ topOfStack.node.scc.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);
- }
+ const scc = selectedNode.scc;
+ // This SCC is complete and currently has no known incoming edge
+ scc.marker = CANDIDATE_MARKER;
+ rootSCCs.add(scc);
}
}
- // Extract roots from root cycles
- // We take the nodes with most incoming edges
- // inside of the cycle
- for (const cycle of rootCycles) {
+ /** @type {Set<T>} */
+ const rootNodes = new Set();
+
+ // For each root SCC, we select node with the most incoming edges
+ // from within the same SCC
+ for (const scc of rootSCCs) {
let max = 0;
/** @type {Nodes<T>} */
- const cycleRoots = new Set();
- const nodes = cycle.nodes;
- for (const node of nodes) {
+ const nodes = new Set(scc.nodes);
+ for (const node of scc.nodes) {
for (const dep of node.dependencies) {
- if (nodes.has(dep)) {
+ if (scc.nodes.has(dep)) {
dep.incoming++;
if (dep.incoming < max) continue;
if (dep.incoming > max) {
- cycleRoots.clear();
+ nodes.clear();
max = dep.incoming;
}
- cycleRoots.add(dep);
+ nodes.add(dep);
}
}
}
- for (const cycleRoot of cycleRoots) {
- roots.add(cycleRoot);
+ for (const node of nodes) {
+ rootNodes.add(node.item);
}
}
- // When roots were found, return them
- if (roots.size > 0) {
- return Array.from(roots, (r) => r.item);
- }
+ // When root nodes were found, return them
+ if (rootNodes.size > 0) return rootNodes;
throw new Error("Implementation of findGraphRoots is broken");
};
--
Gitblit v1.9.3