-
Notifications
You must be signed in to change notification settings - Fork 2.2k
/
query-graph.js
103 lines (83 loc) · 2.91 KB
/
query-graph.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
"use strict";
const PackageGraph = require("@lerna/package-graph");
/**
* A mutable PackageGraph used to query for next available packages
* @constructor
* @param {!Array.<Package>} packages An array of Packages to build the graph out of
* @param {!boolean} rejectCycles Whether or not to reject cycles
*/
class QueryGraph {
constructor(packages, rejectCycles) {
// Create dependency graph
this.graph = new PackageGraph(packages);
// Evaluate cycles
[this.cyclePaths, this.cycleNodes] = this.graph.partitionCycles(rejectCycles);
if (this.cyclePaths.size) {
// Find the cyclical package with the most dependents. Will be evaluated before other cyclical packages
this.cyclicalPackageWithMostDependents = Array.from(this.cycleNodes)
.sort((a, b) => b.localDependents.size - a.localDependents.size)
.shift();
}
}
_getNextLeaf() {
return Array.from(this.graph.values()).filter(node => node.localDependencies.size === 0);
}
_getNextCycle() {
// If the cyclical package with the most dependents is still in the graph, we return it
if (this.graph.has(this.cyclicalPackageWithMostDependents.name)) {
return [this.graph.get(this.cyclicalPackageWithMostDependents.name)];
}
// Otherwise, return any package that does not depend on the package referenced above
return Array.from(this.graph.values()).filter(
node => !node.localDependencies.has(this.cyclicalPackageWithMostDependents)
);
}
_onlyCyclesLeft() {
// Check if every remaining package is a package from the cycleNodes graph
return Array.from(this.graph.values()).every(node =>
Array.from(this.cycleNodes).some(cycleNode => cycleNode.name === node.name)
);
}
getAvailablePackages() {
// Get the next leaf nodes
const availablePackages = this._getNextLeaf();
if (availablePackages.length > 0) {
return availablePackages;
}
// Or, get the next cyclical packages
if (this.cyclePaths.size && this._onlyCyclesLeft()) {
return this._getNextCycle();
}
return [];
}
markAsTaken(name) {
this.graph.delete(name);
}
markAsDone(candidateNode) {
this.graph.remove(candidateNode);
}
}
module.exports = QueryGraph;
module.exports.toposort = toposort;
/**
* Sort the input list topologically.
*
* @param {!Array.<Package>} packages An array of Packages to build the list out of
* @param {!boolean} rejectCycles Whether or not to reject cycles
*
* @returns {Array<Package>} a list of Package instances in topological order
*/
function toposort(packages, rejectCycles) {
const graph = new QueryGraph(packages, rejectCycles);
const result = [];
let batch = graph.getAvailablePackages();
while (batch.length) {
for (const node of batch) {
// no need to take() in synchronous loop
result.push(node.pkg);
graph.markAsDone(node);
}
batch = graph.getAvailablePackages();
}
return result;
}