@snyk/dep-graph - npm Package Compare versions

Comparing version 1.25.0 to 1.26.0

dist/core/dep-graph.d.ts

 import * as graphlib from '../graphlib';
 import * as types from './types';
 export { DepGraphImpl };
+declare type NodeId = string;
+declare type PkgId = string;
 declare class DepGraphImpl implements types.DepGraphInternal {
+    private _graph;
+    private _rootNodeId;
+    private _pkgs;
+    private _pkgNodes;
+    private _pkgManager;
     static SCHEMA_VERSION: string;
     static getPkgId(pkg: types.Pkg): string;
-    private _pkgs;
-    private _pkgNodes;
     private _pkgList;
     private _depPkgsList;
-    private _graph;
-    private _pkgManager;
-    private _rootNodeId;
     private _rootPkgId;
     private _countNodePathsToRootCache;
+    private _pathsToRootCache;
     private _hasCycles;
-    constructor(graph: graphlib.Graph, rootNodeId: string, pkgs: {
-        [pkgId: string]: types.PkgInfo;
-    }, pkgNodes: {
-        [pkgId: string]: Set<string>;
-    }, pkgManager: types.PkgManager);
+    constructor(_graph: graphlib.Graph, _rootNodeId: NodeId, _pkgs: Record<PkgId, types.PkgInfo>, _pkgNodes: Record<PkgId, Set<NodeId>>, _pkgManager: types.PkgManager);
     get pkgManager(): types.PkgManager;
@@ -23,0 +22,0 @@ get rootPkg(): types.PkgInfo;

dist/core/dep-graph.js

@@ -7,11 +7,12 @@ "use strict";
 class DepGraphImpl {
-    constructor(graph, rootNodeId, pkgs, pkgNodes, pkgManager) {
+    constructor(_graph, _rootNodeId, _pkgs, _pkgNodes, _pkgManager) {
+        this._graph = _graph;
+        this._rootNodeId = _rootNodeId;
+        this._pkgs = _pkgs;
+        this._pkgNodes = _pkgNodes;
+        this._pkgManager = _pkgManager;
         this._countNodePathsToRootCache = new Map();
-        this._graph = graph;
-        this._pkgs = pkgs;
-        this._pkgNodes = pkgNodes;
-        this._pkgManager = pkgManager;
-        this._rootNodeId = rootNodeId;
-        this._rootPkgId = graph.node(rootNodeId).pkgId;
-        this._pkgList = Object.values(pkgs);
+        this._pathsToRootCache = new Map();
+        this._rootPkgId = _graph.node(_rootNodeId).pkgId;
+        this._pkgList = Object.values(_pkgs);
         this._depPkgsList = this._pkgList.filter((pkg) => pkg !== this.rootPkg);
@@ -89,10 +90,6 @@ }
     pkgPathsToRoot(pkg) {
-        // TODO: implement cycles support
-        if (this.hasCycles()) {
-            throw new Error('pkgPathsToRoot does not support cyclic graphs yet');
-        }
         const pathsToRoot = [];
-        for (const id of this.getPkgNodeIds(pkg)) {
-            const paths = this.pathsFromNodeToRoot(id);
-            for (const path of paths) {
+        for (const nodeId of this.getPkgNodeIds(pkg)) {
+            const pathsFromNodeToRoot = this.pathsFromNodeToRoot(nodeId);
+            for (const path of pathsFromNodeToRoot) {
                 pathsToRoot.push(path);
@@ -106,6 +103,2 @@ }
     countPathsToRoot(pkg) {
-        // TODO: implement cycles support
-        if (this.hasCycles()) {
-            throw new Error('countPathsToRoot does not support cyclic graphs yet');
-        }
         let count = 0;
@@ -231,19 +224,35 @@ for (const nodeId of this.getPkgNodeIds(pkg)) {
     }
-    pathsFromNodeToRoot(nodeId) {
+    pathsFromNodeToRoot(nodeId, ancestors = []) {
+        if (this._pathsToRootCache.has(nodeId)) {
+            return this._pathsToRootCache.get(nodeId);
+        }
         const parentNodesIds = this.getNodeParentsNodeIds(nodeId);
+        const pkgInfo = this.getNodePkg(nodeId);
         if (parentNodesIds.length === 0) {
-            return [[this.getNodePkg(nodeId)]];
+            const result = [[pkgInfo]];
+            this._pathsToRootCache.set(nodeId, result);
+            return result;
         }
         const allPaths = [];
-        parentNodesIds.map((id) => {
-            const out = this.pathsFromNodeToRoot(id).map((path) => {
-                return [this.getNodePkg(nodeId)].concat(path);
-            });
-            for (const path of out) {
+        ancestors = ancestors.concat(nodeId);
+        let shouldMemoize = true;
+        for (const id of parentNodesIds) {
+            if (ancestors.includes(id)) {
+                shouldMemoize = false;
+                continue;
+            }
+            const pathToRoot = this.pathsFromNodeToRoot(id, ancestors).map((path) => [pkgInfo].concat(path));
+            for (const path of pathToRoot) {
                 allPaths.push(path);
             }
-        });
+        }
+        if (shouldMemoize) {
+            this._pathsToRootCache.set(nodeId, allPaths);
+        }
         return allPaths;
     }
-    countNodePathsToRoot(nodeId) {
+    countNodePathsToRoot(nodeId, ancestors = []) {
+        if (ancestors.includes(nodeId)) {
+            return 0;
+        }
         if (this._countNodePathsToRootCache.has(nodeId)) {
@@ -257,4 +266,5 @@ return this._countNodePathsToRootCache.get(nodeId) || 0;
         }
+        ancestors = ancestors.concat(nodeId);
         const count = parentNodesIds.reduce((acc, parentNodeId) => {
-            return acc + this.countNodePathsToRoot(parentNodeId);
+            return acc + this.countNodePathsToRoot(parentNodeId, ancestors);
         }, 0);
@@ -261,0 +271,0 @@ this._countNodePathsToRootCache.set(nodeId, count);

package.json

@@ -14,2 +14,3 @@ {
     "build": "tsc",
+    "build-dev": "tsc -w",
     "format": "prettier --write '{src,test,scripts}/**/*.?s'",
@@ -71,3 +72,3 @@ "lint:eslint": "eslint 'src/**/*.ts' && (cd test && eslint '**/*.ts')",
   },
-  "version": "1.25.0"
+  "version": "1.26.0"
 }

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

104763

increased by0.9%

Lines of code

1584

increased by0.57%

No dependency changes