1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 | "use strict";
|
7 |
|
8 | const NO_MARKER = 0;
|
9 | const IN_PROGRESS_MARKER = 1;
|
10 | const DONE_MARKER = 2;
|
11 | const DONE_MAYBE_ROOT_CYCLE_MARKER = 3;
|
12 | const DONE_AND_ROOT_MARKER = 4;
|
13 |
|
14 |
|
15 |
|
16 |
|
17 | class Node {
|
18 | |
19 |
|
20 |
|
21 | constructor(item) {
|
22 | this.item = item;
|
23 |
|
24 | this.dependencies = new Set();
|
25 | this.marker = NO_MARKER;
|
26 |
|
27 | this.cycle = undefined;
|
28 | this.incoming = 0;
|
29 | }
|
30 | }
|
31 |
|
32 |
|
33 |
|
34 |
|
35 | class Cycle {
|
36 | constructor() {
|
37 |
|
38 | this.nodes = new Set();
|
39 | }
|
40 | }
|
41 |
|
42 |
|
43 |
|
44 |
|
45 |
|
46 |
|
47 |
|
48 |
|
49 |
|
50 |
|
51 |
|
52 |
|
53 |
|
54 |
|
55 | module.exports = (items, getDependencies) => {
|
56 |
|
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 |
|
64 | if (itemToNode.size <= 1) return items;
|
65 |
|
66 |
|
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 |
|
77 |
|
78 |
|
79 | const roots = new Set();
|
80 |
|
81 |
|
82 |
|
83 |
|
84 |
|
85 | const rootCycles = new Set();
|
86 |
|
87 |
|
88 | for (const selectedNode of itemToNode.values()) {
|
89 | if (selectedNode.marker === NO_MARKER) {
|
90 |
|
91 |
|
92 |
|
93 |
|
94 | selectedNode.marker = IN_PROGRESS_MARKER;
|
95 |
|
96 |
|
97 |
|
98 | const stack = [
|
99 | {
|
100 | node: selectedNode,
|
101 | openEdges: Array.from(selectedNode.dependencies)
|
102 | }
|
103 | ];
|
104 |
|
105 |
|
106 | while (stack.length > 0) {
|
107 | const topOfStack = stack[stack.length - 1];
|
108 |
|
109 |
|
110 | if (topOfStack.openEdges.length > 0) {
|
111 |
|
112 | const dependency = topOfStack.openEdges.pop();
|
113 | switch (dependency.marker) {
|
114 | case NO_MARKER:
|
115 |
|
116 |
|
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 |
|
125 | let cycle = dependency.cycle;
|
126 | if (!cycle) {
|
127 | cycle = new Cycle();
|
128 | cycle.nodes.add(dependency);
|
129 | dependency.cycle = cycle;
|
130 | }
|
131 |
|
132 |
|
133 |
|
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 |
|
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 |
|
154 |
|
155 | break;
|
156 | }
|
157 | case DONE_AND_ROOT_MARKER:
|
158 |
|
159 |
|
160 |
|
161 |
|
162 | dependency.marker = DONE_MARKER;
|
163 | roots.delete(dependency);
|
164 | break;
|
165 | case DONE_MAYBE_ROOT_CYCLE_MARKER:
|
166 |
|
167 |
|
168 |
|
169 |
|
170 |
|
171 |
|
172 | rootCycles.delete(dependency.cycle);
|
173 | dependency.marker = DONE_MARKER;
|
174 | break;
|
175 |
|
176 | }
|
177 | } else {
|
178 |
|
179 |
|
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 |
|
198 |
|
199 |
|
200 | for (const cycle of rootCycles) {
|
201 | let max = 0;
|
202 |
|
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 |
|
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 | };
|