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