source: trip-planner-front/node_modules/webpack/lib/util/findGraphRoots.js@ 188ee53

Last change on this file since 188ee53 was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

initial commit

  • 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 = topOfStack.openEdges.pop();
113 switch (dependency.marker) {
114 case NO_MARKER:
115 // dependency has not be visited yet
116 // mark it as in-progress and recurse
117 stack.push({
118 node: dependency,
119 openEdges: Array.from(dependency.dependencies)
120 });
121 dependency.marker = IN_PROGRESS_MARKER;
122 break;
123 case IN_PROGRESS_MARKER: {
124 // It's a in-progress cycle
125 let cycle = dependency.cycle;
126 if (!cycle) {
127 cycle = new Cycle();
128 cycle.nodes.add(dependency);
129 dependency.cycle = cycle;
130 }
131 // set cycle property for each node in the cycle
132 // if nodes are already part of a cycle
133 // we merge the cycles to a shared cycle
134 for (
135 let i = stack.length - 1;
136 stack[i].node !== dependency;
137 i--
138 ) {
139 const node = stack[i].node;
140 if (node.cycle) {
141 if (node.cycle !== cycle) {
142 // merge cycles
143 for (const cycleNode of node.cycle.nodes) {
144 cycleNode.cycle = cycle;
145 cycle.nodes.add(cycleNode);
146 }
147 }
148 } else {
149 node.cycle = cycle;
150 cycle.nodes.add(node);
151 }
152 }
153 // don't recurse into dependencies
154 // these are already on the stack
155 break;
156 }
157 case DONE_AND_ROOT_MARKER:
158 // This node has be visited yet and is currently a root node
159 // But as this is a new reference to the node
160 // it's not really a root
161 // so we have to convert it to a normal node
162 dependency.marker = DONE_MARKER;
163 roots.delete(dependency);
164 break;
165 case DONE_MAYBE_ROOT_CYCLE_MARKER:
166 // This node has be visited yet and
167 // is maybe currently part of a completed root cycle
168 // we found a new reference to the cycle
169 // so it's not really a root cycle
170 // remove the cycle from the root cycles
171 // and convert it to a normal node
172 rootCycles.delete(dependency.cycle);
173 dependency.marker = DONE_MARKER;
174 break;
175 // DONE_MARKER: nothing to do, don't recurse into dependencies
176 }
177 } else {
178 // All dependencies of the current node has been visited
179 // we leave the node
180 stack.pop();
181 topOfStack.node.marker = DONE_MARKER;
182 }
183 }
184 const cycle = selectedNode.cycle;
185 if (cycle) {
186 for (const node of cycle.nodes) {
187 node.marker = DONE_MAYBE_ROOT_CYCLE_MARKER;
188 }
189 rootCycles.add(cycle);
190 } else {
191 selectedNode.marker = DONE_AND_ROOT_MARKER;
192 roots.add(selectedNode);
193 }
194 }
195 }
196
197 // Extract roots from root cycles
198 // We take the nodes with most incoming edges
199 // inside of the cycle
200 for (const cycle of rootCycles) {
201 let max = 0;
202 /** @type {Set<Node<T>>} */
203 const cycleRoots = new Set();
204 const nodes = cycle.nodes;
205 for (const node of nodes) {
206 for (const dep of node.dependencies) {
207 if (nodes.has(dep)) {
208 dep.incoming++;
209 if (dep.incoming < max) continue;
210 if (dep.incoming > max) {
211 cycleRoots.clear();
212 max = dep.incoming;
213 }
214 cycleRoots.add(dep);
215 }
216 }
217 }
218 for (const cycleRoot of cycleRoots) {
219 roots.add(cycleRoot);
220 }
221 }
222
223 // When roots were found, return them
224 if (roots.size > 0) {
225 return Array.from(roots, r => r.item);
226 } else {
227 throw new Error("Implementation of findGraphRoots is broken");
228 }
229};
Note: See TracBrowser for help on using the repository browser.