summaryrefslogtreecommitdiff
path: root/node_modules/webpack/lib/util/findGraphRoots.js
diff options
context:
space:
mode:
authorlittleblack111 <littleblack11111@gmail.com>2023-11-05 17:23:37 +0800
committerlittleblack111 <littleblack11111@gmail.com>2023-11-05 17:23:37 +0800
commit2cdf0cb352ab6a2d0f8cb25120e4ebc92c5316e3 (patch)
tree6b088c99810bd013f17b80522c936ca6dfc09858 /node_modules/webpack/lib/util/findGraphRoots.js
parentf8ee6ef722e6c560c4a1c879e04dbdf0b01f0316 (diff)
removed autoprefix hover as it will have a high chance of making hover stopped working
Diffstat (limited to 'node_modules/webpack/lib/util/findGraphRoots.js')
-rw-r--r--node_modules/webpack/lib/util/findGraphRoots.js231
1 files changed, 0 insertions, 231 deletions
diff --git a/node_modules/webpack/lib/util/findGraphRoots.js b/node_modules/webpack/lib/util/findGraphRoots.js
deleted file mode 100644
index 4e3c1cb2..00000000
--- a/node_modules/webpack/lib/util/findGraphRoots.js
+++ /dev/null
@@ -1,231 +0,0 @@
-/*
- MIT License http://www.opensource.org/licenses/mit-license.php
- Author Tobias Koppers @sokra
-*/
-
-"use strict";
-
-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
- */
-class Node {
- /**
- * @param {T} item the value of the node
- */
- constructor(item) {
- this.item = item;
- /** @type {Set<Node<T>>} */
- this.dependencies = new Set();
- this.marker = NO_MARKER;
- /** @type {Cycle<T> | undefined} */
- this.cycle = undefined;
- this.incoming = 0;
- }
-}
-
-/**
- * @template T
- */
-class Cycle {
- constructor() {
- /** @type {Set<Node<T>>} */
- this.nodes = new Set();
- }
-}
-
-/**
- * @template T
- * @typedef {Object} StackEntry
- * @property {Node<T>} node
- * @property {Node<T>[]} openEdges
- */
-
-/**
- * @template T
- * @param {Iterable<T>} items list of items
- * @param {function(T): Iterable<T>} getDependencies function to get dependencies of an item (items that are not in list are ignored)
- * @returns {Iterable<T>} graph roots of the items
- */
-module.exports = (items, getDependencies) => {
- /** @type {Map<T, Node<T>>} */
- const itemToNode = new Map();
- for (const item of items) {
- const node = new Node(item);
- itemToNode.set(item, node);
- }
-
- // early exit when there is only a single item
- if (itemToNode.size <= 1) return items;
-
- // grab all the dependencies
- for (const node of itemToNode.values()) {
- for (const dep of getDependencies(node.item)) {
- const depNode = itemToNode.get(dep);
- if (depNode !== undefined) {
- node.dependencies.add(depNode);
- }
- }
- }
-
- // Set of current root modules
- // items will be removed if a new reference to it has been found
- /** @type {Set<Node<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
- /** @type {Set<Cycle<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
-
- // start by entering the selected node
- selectedNode.marker = IN_PROGRESS_MARKER;
-
- // keep a stack to avoid recursive walk
- /** @type {StackEntry<T>[]} */
- const stack = [
- {
- node: selectedNode,
- openEdges: Array.from(selectedNode.dependencies)
- }
- ];
-
- // 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?
- if (topOfStack.openEdges.length > 0) {
- // Process one dependency
- const dependency =
- /** @type {Node<T>} */
- (topOfStack.openEdges.pop());
- switch (dependency.marker) {
- case NO_MARKER:
- // dependency has not be visited yet
- // mark it as in-progress and recurse
- stack.push({
- node: dependency,
- openEdges: Array.from(dependency.dependencies)
- });
- dependency.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
- for (
- let i = stack.length - 1;
- stack[i].node !== dependency;
- 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);
- }
- }
- // 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;
- 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;
- }
- }
- 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);
- }
- }
- }
-
- // 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 {Set<Node<T>>} */
- const cycleRoots = new Set();
- const nodes = cycle.nodes;
- for (const node of nodes) {
- for (const dep of node.dependencies) {
- if (nodes.has(dep)) {
- dep.incoming++;
- if (dep.incoming < max) continue;
- if (dep.incoming > max) {
- cycleRoots.clear();
- max = dep.incoming;
- }
- cycleRoots.add(dep);
- }
- }
- }
- for (const cycleRoot of cycleRoots) {
- roots.add(cycleRoot);
- }
- }
-
- // When roots were found, return them
- if (roots.size > 0) {
- return Array.from(roots, r => r.item);
- } else {
- throw new Error("Implementation of findGraphRoots is broken");
- }
-};