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

main
Last change on this file was 79a0317, checked in by stefan toskovski <stefantoska84@…>, 3 days ago

F4 Finalna Verzija
  • Property mode set to 100644
File size: 6.0 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 DONE_MAYBE_ROOT_CYCLE_MARKER = 3;
12const DONE_AND_ROOT_MARKER = 4;
13
14/**
15 * @template T
16 */
17class Node {
18 /**
19 * @param {T} item the value of the node
20 */
21 constructor(item) {
22 this.item = item;
23 /** @type {Set<Node<T>>} */
24 this.dependencies = new Set();
25 this.marker = NO_MARKER;
26 /** @type {Cycle<T> | undefined} */
27 this.cycle = undefined;
28 this.incoming = 0;
29 }
30}
31
32/**
33 * @template T
34 */
35class Cycle {
36 constructor() {
37 /** @type {Set<Node<T>>} */
38 this.nodes = new Set();
39 }
40}
41
42/**
43 * @template T
44 * @typedef {object} StackEntry
45 * @property {Node<T>} node
46 * @property {Node<T>[]} openEdges
47 */
48
49/**
50 * @template T
51 * @param {Iterable<T>} items list of items
52 * @param {function(T): Iterable<T>} getDependencies function to get dependencies of an item (items that are not in list are ignored)
53 * @returns {Iterable<T>} graph roots of the items
54 */
55module.exports = (items, getDependencies) => {
56 /** @type {Map<T, Node<T>>} */
57 const itemToNode = new Map();
58 for (const item of items) {
59 const node = new Node(item);
60 itemToNode.set(item, node);
61 }
62
63 // early exit when there is only a single item
64 if (itemToNode.size <= 1) return items;
65
66 // grab all the dependencies
67 for (const node of itemToNode.values()) {
68 for (const dep of getDependencies(node.item)) {
69 const depNode = itemToNode.get(dep);
70 if (depNode !== undefined) {
71 node.dependencies.add(depNode);
72 }
73 }
74 }
75
76 // Set of current root modules
77 // items will be removed if a new reference to it has been found
78 /** @type {Set<Node<T>>} */
79 const roots = new Set();
80
81 // Set of current cycles without references to it
82 // cycles will be removed if a new reference to it has been found
83 // that is not part of the cycle
84 /** @type {Set<Cycle<T>>} */
85 const rootCycles = new Set();
86
87 // For all non-marked nodes
88 for (const selectedNode of itemToNode.values()) {
89 if (selectedNode.marker === NO_MARKER) {
90 // deep-walk all referenced modules
91 // in a non-recursive way
92
93 // start by entering the selected node
94 selectedNode.marker = IN_PROGRESS_MARKER;
95
96 // keep a stack to avoid recursive walk
97 /** @type {StackEntry<T>[]} */
98 const stack = [
99 {
100 node: selectedNode,
101 openEdges: Array.from(selectedNode.dependencies)
102 }
103 ];
104
105 // process the top item until stack is empty
106 while (stack.length > 0) {
107 const topOfStack = stack[stack.length - 1];
108
109 // Are there still edges unprocessed in the current node?
110 if (topOfStack.openEdges.length > 0) {
111 // Process one dependency
112 const dependency =
113 /** @type {Node<T>} */
114 (topOfStack.openEdges.pop());
115 switch (dependency.marker) {
116 case NO_MARKER:
117 // dependency has not be visited yet
118 // mark it as in-progress and recurse
119 stack.push({
120 node: dependency,
121 openEdges: Array.from(dependency.dependencies)
122 });
123 dependency.marker = IN_PROGRESS_MARKER;
124 break;
125 case IN_PROGRESS_MARKER: {
126 // It's a in-progress cycle
127 let cycle = dependency.cycle;
128 if (!cycle) {
129 cycle = new Cycle();
130 cycle.nodes.add(dependency);
131 dependency.cycle = cycle;
132 }
133 // set cycle property for each node in the cycle
134 // if nodes are already part of a cycle
135 // we merge the cycles to a shared cycle
136 for (
137 let i = stack.length - 1;
138 stack[i].node !== dependency;
139 i--
140 ) {
141 const node = stack[i].node;
142 if (node.cycle) {
143 if (node.cycle !== cycle) {
144 // merge cycles
145 for (const cycleNode of node.cycle.nodes) {
146 cycleNode.cycle = cycle;
147 cycle.nodes.add(cycleNode);
148 }
149 }
150 } else {
151 node.cycle = cycle;
152 cycle.nodes.add(node);
153 }
154 }
155 // don't recurse into dependencies
156 // these are already on the stack
157 break;
158 }
159 case DONE_AND_ROOT_MARKER:
160 // This node has be visited yet and is currently a root node
161 // But as this is a new reference to the node
162 // it's not really a root
163 // so we have to convert it to a normal node
164 dependency.marker = DONE_MARKER;
165 roots.delete(dependency);
166 break;
167 case DONE_MAYBE_ROOT_CYCLE_MARKER:
168 // This node has be visited yet and
169 // is maybe currently part of a completed root cycle
170 // we found a new reference to the cycle
171 // so it's not really a root cycle
172 // remove the cycle from the root cycles
173 // and convert it to a normal node
174 rootCycles.delete(/** @type {Cycle<T>} */ (dependency.cycle));
175 dependency.marker = DONE_MARKER;
176 break;
177 // DONE_MARKER: nothing to do, don't recurse into dependencies
178 }
179 } else {
180 // All dependencies of the current node has been visited
181 // we leave the node
182 stack.pop();
183 topOfStack.node.marker = DONE_MARKER;
184 }
185 }
186 const cycle = selectedNode.cycle;
187 if (cycle) {
188 for (const node of cycle.nodes) {
189 node.marker = DONE_MAYBE_ROOT_CYCLE_MARKER;
190 }
191 rootCycles.add(cycle);
192 } else {
193 selectedNode.marker = DONE_AND_ROOT_MARKER;
194 roots.add(selectedNode);
195 }
196 }
197 }
198
199 // Extract roots from root cycles
200 // We take the nodes with most incoming edges
201 // inside of the cycle
202 for (const cycle of rootCycles) {
203 let max = 0;
204 /** @type {Set<Node<T>>} */
205 const cycleRoots = new Set();
206 const nodes = cycle.nodes;
207 for (const node of nodes) {
208 for (const dep of node.dependencies) {
209 if (nodes.has(dep)) {
210 dep.incoming++;
211 if (dep.incoming < max) continue;
212 if (dep.incoming > max) {
213 cycleRoots.clear();
214 max = dep.incoming;
215 }
216 cycleRoots.add(dep);
217 }
218 }
219 }
220 for (const cycleRoot of cycleRoots) {
221 roots.add(cycleRoot);
222 }
223 }
224
225 // When roots were found, return them
226 if (roots.size > 0) {
227 return Array.from(roots, r => r.item);
228 }
229
230 throw new Error("Implementation of findGraphRoots is broken");
231};
Note: See TracBrowser for help on using the repository browser.