青岛推送

WXL

3 天以前 9bce51f651aad297ef9eb6df832bfdaf1de05d84

 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");
};