source: frontend/node_modules/webpack/lib/util/findGraphRoots.js

Last change on this file was 9af201e, checked in by MBK <marija.karapandzova@…>, 12 days ago

Fix frontend appearance
  • Property mode set to 100644
File size: 5.5 KB
Line 
1/*
2 MIT License http://www.opensource.org/licenses/mit-license.php
3 Author Tobias Koppers @sokra
4*/
5
6"use strict";
7
8const NO_MARKER = 0;
9const IN_PROGRESS_MARKER = 1;
10const DONE_MARKER = 2;
11const CANDIDATE_MARKER = 3;
12
13/**
14 * Defines the nodes type used by this module.
15 * @template T
16 * @typedef {Set<Node<T>>} Nodes
17 */
18
19/**
20 * Represents the node runtime component.
21 * @template T
22 */
23class Node {
24 /**
25 * Creates an instance of Node.
26 * @param {T} item the value of the node
27 */
28 constructor(item) {
29 this.item = item;
30 /** @type {Nodes<T>} */
31 this.dependencies = new Set();
32 /** @type {SCC<T>} */
33 this.scc = new SCC();
34 // Each node starts as a single-node SCC
35 this.scc.nodes.add(this);
36 /** @type {number} */
37 this.incoming = 0;
38 }
39}
40
41/**
42 * SCC (strongly connected component)
43 * @template T
44 */
45class SCC {
46 constructor() {
47 /** @type {Nodes<T>} */
48 this.nodes = new Set();
49 this.marker = NO_MARKER;
50 }
51}
52
53/**
54 * Defines the stack entry type used by this module.
55 * @template T
56 * @typedef {object} StackEntry
57 * @property {Node<T>} node
58 * @property {Node<T>[]} openEdges
59 */
60
61/**
62 * Returns graph roots of the items.
63 * @template T
64 * @param {Iterable<T>} items list of items
65 * @param {(item: T) => Iterable<T>} getDependencies function to get dependencies of an item (items that are not in list are ignored)
66 * @returns {Iterable<T>} graph roots of the items
67 */
68module.exports = (items, getDependencies) => {
69 /** @type {Map<T, Node<T>>} */
70 const itemToNode = new Map();
71 for (const item of items) {
72 const node = new Node(item);
73 itemToNode.set(item, node);
74 }
75
76 // Early exit when there is only one node
77 if (itemToNode.size <= 1) return items;
78
79 // Build graph edges
80 for (const node of itemToNode.values()) {
81 for (const dep of getDependencies(node.item)) {
82 const depNode = itemToNode.get(dep);
83 if (depNode !== undefined) {
84 node.dependencies.add(depNode);
85 }
86 }
87 }
88
89 // All candidate root SCCs, they will be removed once an incoming edge is found
90 /** @type {Set<SCC<T>>} */
91 const rootSCCs = new Set();
92
93 for (const selectedNode of itemToNode.values()) {
94 // DFS walk only once per unseen SCC
95 if (selectedNode.scc.marker === NO_MARKER) {
96 selectedNode.scc.marker = IN_PROGRESS_MARKER;
97
98 // Keep a stack to avoid recursive walk
99 /** @type {StackEntry<T>[]} */
100 const stack = [
101 {
102 node: selectedNode,
103 openEdges: [...selectedNode.dependencies]
104 }
105 ];
106
107 while (stack.length > 0) {
108 const topOfStack = stack[stack.length - 1];
109
110 // Process one unvisited outgoing edge if available
111 if (topOfStack.openEdges.length > 0) {
112 const dependency =
113 /** @type {Node<T>} */
114 (topOfStack.openEdges.pop());
115 const depSCC = dependency.scc;
116 switch (depSCC.marker) {
117 case NO_MARKER:
118 // First time we see this SCC: enter it
119 stack.push({
120 node: dependency,
121 openEdges: [...dependency.dependencies]
122 });
123 depSCC.marker = IN_PROGRESS_MARKER;
124 break;
125 case IN_PROGRESS_MARKER: {
126 // Back-edge to an SCC that is still on the stack
127 // Example:
128 // A -> B -> C -> D
129 // ^ |
130 // |_________|
131 // If we are at `D` and traverse `D` -> `B`, then `B/C/D` must be in one SCC
132 /** @type {Set<SCC<T>>} */
133 const sccsToMerge = new Set();
134 for (
135 let i = stack.length - 1;
136 stack[i].node.scc !== depSCC;
137 i--
138 ) {
139 sccsToMerge.add(stack[i].node.scc);
140 }
141 for (const sccToMerge of sccsToMerge) {
142 for (const nodeInMergedSCC of sccToMerge.nodes) {
143 nodeInMergedSCC.scc = depSCC;
144 depSCC.nodes.add(nodeInMergedSCC);
145 }
146 }
147 break;
148 }
149 case CANDIDATE_MARKER:
150 // This finished SCC was previously considered as root SCC
151 // We just found a new incoming edge, so it is no longer a candidate
152 rootSCCs.delete(/** @type {SCC<T>} */ (depSCC));
153 depSCC.marker = DONE_MARKER;
154 break;
155 case DONE_MARKER:
156 // Already finalized and not a candidate
157 break;
158 }
159 } else {
160 // All dependencies of the current node have been processed
161 // So we leave the node
162 stack.pop();
163 // Mark an SCC as DONE only when the popped node is the last
164 // node from that SCC remaining on the current stack.
165 // A -> B -> C -> D
166 // ^ |
167 // |_________|
168 // If `B` is popped and the new stack top is `A`, they are in
169 // different SCCs, so B's SCC can be finalized.
170 if (
171 stack.length &&
172 topOfStack.node.scc !== stack[stack.length - 1].node.scc
173 ) {
174 topOfStack.node.scc.marker = DONE_MARKER;
175 }
176 }
177 }
178 const scc = selectedNode.scc;
179 // This SCC is complete and currently has no known incoming edge
180 scc.marker = CANDIDATE_MARKER;
181 rootSCCs.add(scc);
182 }
183 }
184
185 /** @type {Set<T>} */
186 const rootNodes = new Set();
187
188 // For each root SCC, we select node with the most incoming edges
189 // from within the same SCC
190 for (const scc of rootSCCs) {
191 let max = 0;
192 /** @type {Nodes<T>} */
193 const nodes = new Set(scc.nodes);
194 for (const node of scc.nodes) {
195 for (const dep of node.dependencies) {
196 if (scc.nodes.has(dep)) {
197 dep.incoming++;
198 if (dep.incoming < max) continue;
199 if (dep.incoming > max) {
200 nodes.clear();
201 max = dep.incoming;
202 }
203 nodes.add(dep);
204 }
205 }
206 }
207 for (const node of nodes) {
208 rootNodes.add(node.item);
209 }
210 }
211
212 // When root nodes were found, return them
213 if (rootNodes.size > 0) return rootNodes;
214
215 throw new Error("Implementation of findGraphRoots is broken");
216};
Note: See TracBrowser for help on using the repository browser.