1 | "use strict";
|
2 | Object.defineProperty(exports, "__esModule", { value: true });
|
3 | const _isEqual = require("lodash.isequal");
|
4 | const graphlib = require("../graphlib");
|
5 | const create_from_json_1 = require("./create-from-json");
|
6 | class DepGraphImpl {
|
7 | constructor(_graph, _rootNodeId, _pkgs, _pkgNodes, _pkgManager) {
|
8 | this._graph = _graph;
|
9 | this._rootNodeId = _rootNodeId;
|
10 | this._pkgs = _pkgs;
|
11 | this._pkgNodes = _pkgNodes;
|
12 | this._pkgManager = _pkgManager;
|
13 | this._countNodePathsToRootCache = new Map();
|
14 | this._rootPkgId = _graph.node(_rootNodeId).pkgId;
|
15 | this._pkgList = Object.values(_pkgs);
|
16 | this._depPkgsList = this._pkgList.filter((pkg) => pkg !== this.rootPkg);
|
17 | }
|
18 | static getPkgId(pkg) {
|
19 | return `${pkg.name}@${pkg.version || ''}`;
|
20 | }
|
21 | get pkgManager() {
|
22 | return this._pkgManager;
|
23 | }
|
24 | get rootPkg() {
|
25 | return this._pkgs[this._rootPkgId];
|
26 | }
|
27 | get rootNodeId() {
|
28 | return this._rootNodeId;
|
29 | }
|
30 | |
31 |
|
32 |
|
33 | getPkgs() {
|
34 | return this._pkgList;
|
35 | }
|
36 | |
37 |
|
38 |
|
39 | getDepPkgs() {
|
40 | return this._depPkgsList;
|
41 | }
|
42 | getPkgNodes(pkg) {
|
43 | const pkgId = DepGraphImpl.getPkgId(pkg);
|
44 | const nodes = [];
|
45 | for (const nodeId of Array.from(this._pkgNodes[pkgId])) {
|
46 | const graphNode = this.getGraphNode(nodeId);
|
47 | nodes.push({
|
48 | info: graphNode.info || {},
|
49 | });
|
50 | }
|
51 | return nodes;
|
52 | }
|
53 | getNode(nodeId) {
|
54 | return this.getGraphNode(nodeId).info || {};
|
55 | }
|
56 | getNodePkg(nodeId) {
|
57 | return this._pkgs[this.getGraphNode(nodeId).pkgId];
|
58 | }
|
59 | getPkgNodeIds(pkg) {
|
60 | const pkgId = DepGraphImpl.getPkgId(pkg);
|
61 | if (!this._pkgs[pkgId]) {
|
62 | throw new Error(`no such pkg: ${pkgId}`);
|
63 | }
|
64 | return Array.from(this._pkgNodes[pkgId]);
|
65 | }
|
66 | getNodeDepsNodeIds(nodeId) {
|
67 | const deps = this._graph.successors(nodeId);
|
68 | if (!deps) {
|
69 | throw new Error(`no such node: ${nodeId}`);
|
70 | }
|
71 | return deps;
|
72 | }
|
73 | getNodeParentsNodeIds(nodeId) {
|
74 | const parents = this._graph.predecessors(nodeId);
|
75 | if (!parents) {
|
76 | throw new Error(`no such node: ${nodeId}`);
|
77 | }
|
78 | return parents;
|
79 | }
|
80 | hasCycles() {
|
81 |
|
82 | if (this._hasCycles === undefined) {
|
83 | this._hasCycles = !graphlib.alg.isAcyclic(this._graph);
|
84 | }
|
85 | return this._hasCycles;
|
86 | }
|
87 | pkgPathsToRoot(pkg) {
|
88 | const pathsToRoot = [];
|
89 | for (const nodeId of this.getPkgNodeIds(pkg)) {
|
90 | const pathsFromNodeToRoot = this.pathsFromNodeToRoot(nodeId);
|
91 | for (const path of pathsFromNodeToRoot) {
|
92 | pathsToRoot.push(path);
|
93 | }
|
94 | }
|
95 |
|
96 |
|
97 | return pathsToRoot.sort((a, b) => a.length - b.length);
|
98 | }
|
99 | countPathsToRoot(pkg) {
|
100 | let count = 0;
|
101 | for (const nodeId of this.getPkgNodeIds(pkg)) {
|
102 | count += this.countNodePathsToRoot(nodeId);
|
103 | }
|
104 | return count;
|
105 | }
|
106 | equals(other, { compareRoot = true } = {}) {
|
107 | let otherDepGraph;
|
108 | if (other instanceof DepGraphImpl) {
|
109 | otherDepGraph = other;
|
110 | }
|
111 | else {
|
112 |
|
113 |
|
114 |
|
115 | otherDepGraph = create_from_json_1.createFromJSON(other.toJSON());
|
116 | }
|
117 |
|
118 |
|
119 |
|
120 |
|
121 | return this.nodeEquals(this, this.rootNodeId, otherDepGraph, otherDepGraph.rootNodeId, compareRoot);
|
122 | }
|
123 | directDepsLeadingTo(pkg) {
|
124 | const pkgNodes = this.getPkgNodeIds(pkg);
|
125 | const directDeps = this.getNodeDepsNodeIds(this.rootNodeId);
|
126 | const nodes = directDeps.filter((directDep) => {
|
127 | const reachableNodes = graphlib.alg.postorder(this._graph, [directDep]);
|
128 | return reachableNodes.filter((node) => pkgNodes.includes(node)).length;
|
129 | });
|
130 | return nodes.map((node) => this.getNodePkg(node));
|
131 | }
|
132 | |
133 |
|
134 |
|
135 |
|
136 | toJSON() {
|
137 | const nodeIds = this._graph.nodes();
|
138 | const nodes = nodeIds.reduce((acc, nodeId) => {
|
139 | const deps = (this._graph.successors(nodeId) || []).map((depNodeId) => ({
|
140 | nodeId: depNodeId,
|
141 | }));
|
142 | const node = this._graph.node(nodeId);
|
143 | const elem = {
|
144 | nodeId,
|
145 | pkgId: node.pkgId,
|
146 | deps,
|
147 | };
|
148 | if (node.info && Object.keys(node.info).length > 0) {
|
149 | elem.info = node.info;
|
150 | }
|
151 | acc.push(elem);
|
152 | return acc;
|
153 | }, []);
|
154 | const pkgs = Object.keys(this._pkgs).map((pkgId) => ({
|
155 | id: pkgId,
|
156 | info: this._pkgs[pkgId],
|
157 | }));
|
158 | return {
|
159 | schemaVersion: DepGraphImpl.SCHEMA_VERSION,
|
160 | pkgManager: this._pkgManager,
|
161 | pkgs,
|
162 | graph: {
|
163 | rootNodeId: this._rootNodeId,
|
164 | nodes,
|
165 | },
|
166 | };
|
167 | }
|
168 | nodeEquals(graphA, nodeIdA, graphB, nodeIdB, compareRoot, traversedPairs = new Set()) {
|
169 |
|
170 | if (compareRoot ||
|
171 | (nodeIdA !== graphA.rootNodeId && nodeIdB !== graphB.rootNodeId)) {
|
172 | const pkgA = graphA.getNodePkg(nodeIdA);
|
173 | const pkgB = graphB.getNodePkg(nodeIdB);
|
174 |
|
175 | if (!_isEqual(pkgA, pkgB)) {
|
176 | return false;
|
177 | }
|
178 | const infoA = graphA.getNode(nodeIdA);
|
179 | const infoB = graphB.getNode(nodeIdB);
|
180 |
|
181 | if (!_isEqual(infoA, infoB)) {
|
182 | return false;
|
183 | }
|
184 | }
|
185 | let depsA = graphA.getNodeDepsNodeIds(nodeIdA);
|
186 | let depsB = graphB.getNodeDepsNodeIds(nodeIdB);
|
187 |
|
188 | if (depsA.length !== depsB.length) {
|
189 | return false;
|
190 | }
|
191 |
|
192 | const sortFn = (graph) => (idA, idB) => {
|
193 | const pkgA = graph.getNodePkg(idA);
|
194 | const pkgB = graph.getNodePkg(idB);
|
195 | return DepGraphImpl.getPkgId(pkgA).localeCompare(DepGraphImpl.getPkgId(pkgB));
|
196 | };
|
197 | depsA = depsA.sort(sortFn(graphA));
|
198 | depsB = depsB.sort(sortFn(graphB));
|
199 |
|
200 | for (let i = 0; i < depsA.length; i++) {
|
201 | const pairKey = `${depsA[i]}_${depsB[i]}`;
|
202 |
|
203 | if (traversedPairs.has(pairKey)) {
|
204 | continue;
|
205 | }
|
206 | traversedPairs.add(pairKey);
|
207 | if (!this.nodeEquals(graphA, depsA[i], graphB, depsB[i], compareRoot, traversedPairs)) {
|
208 | return false;
|
209 | }
|
210 | }
|
211 | return true;
|
212 | }
|
213 | getGraphNode(nodeId) {
|
214 | const node = this._graph.node(nodeId);
|
215 | if (!node) {
|
216 | throw new Error(`no such node: ${nodeId}`);
|
217 | }
|
218 | return node;
|
219 | }
|
220 | pathsFromNodeToRoot(nodeId, ancestors = []) {
|
221 | const parentNodesIds = this.getNodeParentsNodeIds(nodeId);
|
222 | const pkgInfo = this.getNodePkg(nodeId);
|
223 | if (parentNodesIds.length === 0) {
|
224 | return [[pkgInfo]];
|
225 | }
|
226 | const allPaths = [];
|
227 | ancestors = ancestors.concat(nodeId);
|
228 | for (const id of parentNodesIds) {
|
229 | if (ancestors.includes(id))
|
230 | continue;
|
231 | const pathToRoot = this.pathsFromNodeToRoot(id, ancestors).map((path) => [pkgInfo].concat(path));
|
232 | for (const path of pathToRoot) {
|
233 | allPaths.push(path);
|
234 | }
|
235 | }
|
236 | return allPaths;
|
237 | }
|
238 | countNodePathsToRoot(nodeId, ancestors = []) {
|
239 | if (ancestors.includes(nodeId)) {
|
240 | return 0;
|
241 | }
|
242 | if (this._countNodePathsToRootCache.has(nodeId)) {
|
243 | return this._countNodePathsToRootCache.get(nodeId) || 0;
|
244 | }
|
245 | const parentNodesIds = this.getNodeParentsNodeIds(nodeId);
|
246 | if (parentNodesIds.length === 0) {
|
247 | this._countNodePathsToRootCache.set(nodeId, 1);
|
248 | return 1;
|
249 | }
|
250 | ancestors = ancestors.concat(nodeId);
|
251 | const count = parentNodesIds.reduce((acc, parentNodeId) => {
|
252 | return acc + this.countNodePathsToRoot(parentNodeId, ancestors);
|
253 | }, 0);
|
254 | this._countNodePathsToRootCache.set(nodeId, count);
|
255 | return count;
|
256 | }
|
257 | }
|
258 | exports.DepGraphImpl = DepGraphImpl;
|
259 | DepGraphImpl.SCHEMA_VERSION = '1.2.0';
|
260 |
|
\ | No newline at end of file |