@lerna/package-graph - npm Package Compare versions

Comparing version 3.14.0 to 3.16.0

CHANGELOG.md

@@ -6,2 +6,18 @@ # Change Log
 
+# [3.16.0](https://github.com/lerna/lerna/compare/v3.15.0...v3.16.0) (2019-07-18)
+
+
+### Bug Fixes
+
+* **package-graph:** Flatten cycles to avoid skipping packages ([#2185](https://github.com/lerna/lerna/issues/2185)) ([b335763](https://github.com/lerna/lerna/commit/b335763))
+
+
+### Features
+
+* **deps:** `semver@^6.2.0` ([d8016d9](https://github.com/lerna/lerna/commit/d8016d9))
+
+
+
+
+
 # [3.14.0](https://github.com/lerna/lerna/compare/v3.13.4...v3.14.0) (2019-05-14)
@@ -8,0 +24,0 @@

index.js

@@ -58,5 +58,128 @@ "use strict";
   }
+
+  /**
+   * Returns a string representation of this node (its name)
+   *
+   * @returns {String}
+   */
+  toString() {
+    return this.name;
+  }
 }
 
+let lastCollapsedNodeId = 0;
+
 /**
+ * Represents a cyclic collection of nodes in a PackageGraph.
+ * It is meant to be used as a black box, where the only exposed
+ * information are the connections to the other nodes of the graph.
+ * It can contains either `PackageGraphNode`s or other `CyclicPackageGraphNode`s.
+ */
+class CyclicPackageGraphNode extends Map {
+  constructor() {
+    super();
+
+    this.localDependencies = new Map();
+    this.localDependents = new Map();
+
+    Object.defineProperties(this, {
+      // immutable properties
+      name: {
+        enumerable: true,
+        value: `(cycle) ${(lastCollapsedNodeId += 1)}`,
+      },
+      isCycle: {
+        value: true,
+      },
+    });
+  }
+
+  /**
+   * @returns {String} Returns a representation of a cycle, like like `A -> B -> C -> A`.
+   */
+  toString() {
+    const parts = Array.from(this, ([key, node]) =>
+      node.isCycle ? `(nested cycle: ${node.toString()})` : key
+    );
+
+    // start from the origin
+    parts.push(parts[0]);
+
+    return parts.reverse().join(" -> ");
+  }
+
+  /**
+   * Flattens a CyclicPackageGraphNode (which can have multiple level of cycles).
+   *
+   * @returns {PackageGraphNode[]}
+   */
+  flatten() {
+    const result = [];
+
+    for (const node of this.values()) {
+      if (node.isCycle) {
+        result.push(...node.flatten());
+      } else {
+        result.push(node);
+      }
+    }
+
+    return result;
+  }
+
+  /**
+   * Checks if a given node is contained in this cycle (or in a nested one)
+   *
+   * @param {String} name The name of the package to search in this cycle
+   * @returns {Boolean}
+   */
+  contains(name) {
+    for (const [currentName, currentNode] of this) {
+      if (currentNode.isCycle) {
+        if (currentNode.contains(name)) {
+          return true;
+        }
+      } else if (currentName === name) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  /**
+   * Adds a graph node, or a nested cycle, to this group.
+   *
+   * @param {PackageGraphNode|CyclicPackageGraphNode} node
+   */
+  insert(node) {
+    this.set(node.name, node);
+    this.unlink(node);
+
+    for (const [dependencyName, dependencyNode] of node.localDependencies) {
+      if (!this.contains(dependencyName)) {
+        this.localDependencies.set(dependencyName, dependencyNode);
+      }
+    }
+
+    for (const [dependentName, dependentNode] of node.localDependents) {
+      if (!this.contains(dependentName)) {
+        this.localDependents.set(dependentName, dependentNode);
+      }
+    }
+  }
+
+  /**
+   * Remove pointers to candidate node from internal collections.
+   * @param {PackageGraphNode|CyclicPackageGraphNode} candidateNode instance to unlink
+   */
+  unlink(candidateNode) {
+    // remove incoming edges ("indegree")
+    this.localDependencies.delete(candidateNode.name);
+
+    // remove outgoing edges ("outdegree")
+    this.localDependents.delete(candidateNode.name);
+  }
+}
+
+/**
  * A PackageGraph.
@@ -194,3 +317,6 @@ * @constructor
   /**
-   * Return a tuple of cycle paths and nodes, which have been removed from the graph.
+   * Return a tuple of cycle paths and nodes.
+   *
+   * @deprecated Use collapseCycles instead.
+   *
    * @param {!boolean} rejectCycles Whether or not to reject cycles
@@ -243,15 +369,67 @@ * @returns [Set<String[]>, Set<PackageGraphNode>]
 
-    if (cyclePaths.size) {
-      const cycleMessage = ["Dependency cycles detected, you should fix these!"]
-        .concat(Array.from(cyclePaths).map(cycle => cycle.join(" -> ")))
-        .join("\n");
+    reportCycles(Array.from(cyclePaths, cycle => cycle.join(" -> ")), rejectCycles);
 
-      if (rejectCycles) {
-        throw new ValidationError("ECYCLE", cycleMessage);
+    return [cyclePaths, cycleNodes];
+  }
+
+  /**
+   * Returns the cycles of this graph. If two cycles share some elements, they will
+   * be returned as a single cycle.
+   *
+   * @param {!boolean} rejectCycles Whether or not to reject cycles
+   * @returns Set<CyclicPackageGraphNode>
+   */
+  collapseCycles(rejectCycles) {
+    const cyclePaths = [];
+    const nodeToCycle = new Map();
+    const cycles = new Set();
+
+    const walkStack = [];
+
+    function visits(baseNode, dependentNode) {
+      if (nodeToCycle.has(baseNode)) {
+        return;
       }
 
-      log.warn("ECYCLE", cycleMessage);
+      let topLevelDependent = dependentNode;
+      while (nodeToCycle.has(topLevelDependent)) {
+        topLevelDependent = nodeToCycle.get(topLevelDependent);
+      }
+
+      if (
+        topLevelDependent === baseNode ||
+        (topLevelDependent.isCycle && topLevelDependent.has(baseNode.name))
+      ) {
+        const cycle = new CyclicPackageGraphNode();
+
+        walkStack.forEach(nodeInCycle => {
+          nodeToCycle.set(nodeInCycle, cycle);
+          cycle.insert(nodeInCycle);
+          cycles.delete(nodeInCycle);
+        });
+
+        cycles.add(cycle);
+        cyclePaths.push(cycle.toString());
+
+        return;
+      }
+
+      if (walkStack.indexOf(topLevelDependent) === -1) {
+        // eslint-disable-next-line no-use-before-define
+        visitWithStack(baseNode, topLevelDependent);
+      }
     }
 
-    return [cyclePaths, cycleNodes];
+    function visitWithStack(baseNode, currentNode = baseNode) {
+      walkStack.push(currentNode);
+      currentNode.localDependents.forEach(visits.bind(null, baseNode));
+      walkStack.pop();
+    }
+
+    this.forEach(currentNode => visitWithStack(currentNode));
+    cycles.forEach(collapsedNode => visitWithStack(collapsedNode));
+
+    reportCycles(cyclePaths, rejectCycles);
+
+    return cycles;
   }
@@ -297,2 +475,16 @@
 
+function reportCycles(paths, rejectCycles) {
+  if (!paths.length) {
+    return;
+  }
+
+  const cycleMessage = ["Dependency cycles detected, you should fix these!"].concat(paths).join("\n");
+
+  if (rejectCycles) {
+    throw new ValidationError("ECYCLE", cycleMessage);
+  }
+
+  log.warn("ECYCLE", cycleMessage);
+}
+
 module.exports = PackageGraph;

package.json

 {
   "name": "@lerna/package-graph",
-  "version": "3.14.0",
+  "version": "3.16.0",
   "description": "Lerna's internal representation of a package graph",
@@ -34,9 +34,9 @@ "keywords": [
   "dependencies": {
-    "@lerna/prerelease-id-from-version": "3.14.0",
+    "@lerna/prerelease-id-from-version": "3.16.0",
     "@lerna/validation-error": "3.13.0",
     "npm-package-arg": "^6.1.0",
     "npmlog": "^4.1.2",
-    "semver": "^5.5.0"
+    "semver": "^6.2.0"
   },
-  "gitHead": "39da145c67ea587457694f318f32f967b9d66ea9"
+  "gitHead": "8ca18bedecf4f141c6242a099086e84b2ced72de"
 }

No alert changes

Improved metrics

Total package byte prevSize

22391

increased by30.21%

Lines of code

410

increased by64%

Dependency changes

• + Added@lerna/prerelease-id-from-version@3.16.0(transitive)

• + Addedsemver@6.3.1(transitive)

• - Removed@lerna/prerelease-id-from-version@3.14.0(transitive)

• Updated@lerna/prerelease-id-from-version@3.16.0

• Updatedsemver@^6.2.0