@parcel/graph - npm Package Compare versions

Comparing version 3.2.1-dev.3238 to 3.2.1-dev.3260

lib/AdjacencyList.js

@@ -243,3 +243,3 @@ "use strict";
    * (that only happens in `addEdge`), it _may_ preemptively resize
-   * the nodes array if it is at capacity, under the asumption that
+   * the nodes array if it is at capacity, under the assumption that
    * at least 1 edge to or from this new node will be added.
@@ -246,0 +246,0 @@ *

lib/ContentGraph.js

@@ -36,3 +36,2 @@ "use strict";
   static deserialize(opts) {
-    // $FlowFixMe
     return new ContentGraph(opts);
@@ -43,2 +42,3 @@ }
   serialize() {
+    // $FlowFixMe[prop-missing]
     return {
@@ -45,0 +45,0 @@ ...super.serialize(),

lib/Graph.js

@@ -10,2 +10,9 @@ "use strict";
 var _AdjacencyList = _interopRequireDefault(require("./AdjacencyList"));
+function _featureFlags() {
+  const data = require("@parcel/feature-flags");
+  _featureFlags = function () {
+    return data;
+  };
+  return data;
+}
 var _BitSet = require("./BitSet");
@@ -21,2 +28,11 @@ function _nullthrows() {
 const ALL_EDGE_TYPES = exports.ALL_EDGE_TYPES = -1;
+
+/**
+ * Internal type used for queue iterative DFS implementation.
+ */
+
+/**
+ * Options for DFS traversal.
+ */
+
 class Graph {
@@ -184,6 +200,10 @@ constructor(opts) {
     } else {
-      return this.dfs({
+      return (0, _featureFlags().getFeatureFlag)('dfsFasterRefactor') ? this.dfsNew({
         visit,
         startNodeId,
         getChildren: nodeId => this.getNodeIdsConnectedFrom(nodeId, type)
+      }) : this.dfs({
+        visit,
+        startNodeId,
+        getChildren: nodeId => this.getNodeIdsConnectedFrom(nodeId, type)
       });
@@ -203,3 +223,3 @@ }
   dfsFast(visit, startNodeId) {
-    let traversalStartNode = (0, _nullthrows().default)(startNodeId !== null && startNodeId !== void 0 ? startNodeId : this.rootNodeId, 'A start node is required to traverse');
+    let traversalStartNode = (0, _nullthrows().default)(startNodeId ?? this.rootNodeId, 'A start node is required to traverse');
     this._assertHasNodeId(traversalStartNode);
@@ -266,3 +286,3 @@ let visited;
   postOrderDfsFast(visit, startNodeId) {
-    let traversalStartNode = (0, _nullthrows().default)(startNodeId !== null && startNodeId !== void 0 ? startNodeId : this.rootNodeId, 'A start node is required to traverse');
+    let traversalStartNode = (0, _nullthrows().default)(startNodeId ?? this.rootNodeId, 'A start node is required to traverse');
     this._assertHasNodeId(traversalStartNode);
@@ -309,2 +329,110 @@ let visited;
   }
+
+  /**
+   * Iterative implementation of DFS that supports all use-cases.
+   *
+   * This replaces `dfs` and will replace `dfsFast`.
+   */
+  dfsNew({
+    visit,
+    startNodeId,
+    getChildren
+  }) {
+    let traversalStartNode = (0, _nullthrows().default)(startNodeId ?? this.rootNodeId, 'A start node is required to traverse');
+    this._assertHasNodeId(traversalStartNode);
+    let visited;
+    if (!this._visited || this._visited.capacity < this.nodes.length) {
+      this._visited = new _BitSet.BitSet(this.nodes.length);
+      visited = this._visited;
+    } else {
+      visited = this._visited;
+      visited.clear();
+    }
+    // Take shared instance to avoid re-entrancy issues.
+    this._visited = null;
+    let stopped = false;
+    let skipped = false;
+    let actions = {
+      skipChildren() {
+        skipped = true;
+      },
+      stop() {
+        stopped = true;
+      }
+    };
+    const queue = [{
+      nodeId: traversalStartNode,
+      context: null
+    }];
+    const enter = typeof visit === 'function' ? visit : visit.enter;
+    while (queue.length !== 0) {
+      const command = queue.pop();
+      if (command.exit != null) {
+        let {
+          nodeId,
+          context,
+          exit
+        } = command;
+        let newContext = exit(nodeId, command.context, actions);
+        if (typeof newContext !== 'undefined') {
+          // $FlowFixMe[reassign-const]
+          context = newContext;
+        }
+        if (skipped) {
+          continue;
+        }
+        if (stopped) {
+          this._visited = visited;
+          return context;
+        }
+      } else {
+        let {
+          nodeId,
+          context
+        } = command;
+        if (!this.hasNode(nodeId) || visited.has(nodeId)) continue;
+        visited.add(nodeId);
+        skipped = false;
+        if (enter) {
+          let newContext = enter(nodeId, context, actions);
+          if (typeof newContext !== 'undefined') {
+            // $FlowFixMe[reassign-const]
+            context = newContext;
+          }
+        }
+        if (skipped) {
+          continue;
+        }
+        if (stopped) {
+          this._visited = visited;
+          return context;
+        }
+        if (typeof visit !== 'function' && visit.exit) {
+          queue.push({
+            nodeId,
+            exit: visit.exit,
+            context
+          });
+        }
+
+        // TODO turn into generator function
+        const children = getChildren(nodeId);
+        for (let i = children.length - 1; i > -1; i -= 1) {
+          const child = children[i];
+          if (visited.has(child)) {
+            continue;
+          }
+          queue.push({
+            nodeId: child,
+            context
+          });
+        }
+      }
+    }
+    this._visited = visited;
+  }
+
+  /**
+   * @deprecated Will be replaced by `dfsNew`
+   */
   dfs({
@@ -315,3 +443,3 @@ visit,
   }) {
-    let traversalStartNode = (0, _nullthrows().default)(startNodeId !== null && startNodeId !== void 0 ? startNodeId : this.rootNodeId, 'A start node is required to traverse');
+    let traversalStartNode = (0, _nullthrows().default)(startNodeId ?? this.rootNodeId, 'A start node is required to traverse');
     this._assertHasNodeId(traversalStartNode);
@@ -318,0 +446,0 @@ let visited;

package.json

 {
   "name": "@parcel/graph",
-  "version": "3.2.1-dev.3238+7f6b4dbbc",
+  "version": "3.2.1-dev.3260+339350eb3",
   "description": "Blazing fast, zero configuration web application bundler",
@@ -20,8 +20,9 @@ "license": "MIT",
   "engines": {
-    "node": ">= 12.0.0"
+    "node": ">= 16.0.0"
   },
   "dependencies": {
+    "@parcel/feature-flags": "2.12.1-dev.3260+339350eb3",
     "nullthrows": "^1.1.1"
   },
-  "gitHead": "7f6b4dbbc56a203e0fce8794856c03598c4f6708"
+  "gitHead": "339350eb31fd33849cb1efe5fd7ad2cb096319f0"
 }

src/AdjacencyList.js

@@ -33,3 +33,3 @@ // @flow
   peakCapacity?: number,
-  /** The percentage of deleted edges above which the capcity should shink. */
+  /** The percentage of deleted edges above which the capacity should shrink. */
   unloadFactor?: number,
@@ -332,3 +332,3 @@ /** The amount by which to shrink the capacity. */
    * (that only happens in `addEdge`), it _may_ preemptively resize
-   * the nodes array if it is at capacity, under the asumption that
+   * the nodes array if it is at capacity, under the assumption that
    * at least 1 edge to or from this new node will be added.
@@ -335,0 +335,0 @@ *

src/ContentGraph.js

@@ -15,3 +15,2 @@ // @flow strict-local
   _contentKeyToNodeId: Map<ContentKey, NodeId>,
-  _nodeIdToContentKey: Map<NodeId, ContentKey>,
 |};
@@ -41,5 +40,4 @@
   static deserialize(
-    opts: SerializedContentGraph<TNode, TEdgeType>,
+    opts: ContentGraphOpts<TNode, TEdgeType>,
   ): ContentGraph<TNode, TEdgeType> {
-    // $FlowFixMe
     return new ContentGraph(opts);
@@ -50,2 +48,3 @@ }
   serialize(): SerializedContentGraph<TNode, TEdgeType> {
+    // $FlowFixMe[prop-missing]
     return {
@@ -52,0 +51,0 @@ ...super.serialize(),

src/Graph.js

@@ -6,2 +6,3 @@ // @flow strict-local
 import type {Edge, NodeId} from './types';
+import {getFeatureFlag} from '@parcel/feature-flags';
 import type {
@@ -32,2 +33,47 @@ TraversalActions,
 
+type DFSCommandVisit<TContext> = {|
+  nodeId: NodeId,
+  context: TContext | null,
+|};
+
+type DFSCommandExit<TContext> = {|
+  nodeId: NodeId,
+  exit: GraphTraversalCallback<NodeId, TContext>,
+  context: TContext | null,
+|};
+
+/**
+ * Internal type used for queue iterative DFS implementation.
+ */
+type DFSCommand<TContext> =
+  | DFSCommandVisit<TContext>
+  | DFSCommandExit<TContext>;
+
+/**
+ * Options for DFS traversal.
+ */
+export type DFSParams<TContext> = {|
+  visit: GraphVisitor<NodeId, TContext>,
+  /**
+   * Custom function to get next entries to visit.
+   *
+   * This can be a performance bottleneck as arrays are created on every node visit.
+   *
+   * @deprecated This will be replaced by a static `traversalType` set of orders in the future
+   *
+   * Currently, this is only used in 3 ways:
+   *
+   * - Traversing down the tree (normal DFS)
+   * - Traversing up the tree (ancestors)
+   * - Filtered version of traversal; which does not need to exist at the DFS level as the visitor
+   *   can handle filtering
+   * - Sorted traversal of BundleGraph entries, which does not have a clear use-case, but may
+   *   not be safe to remove
+   *
+   * Only due to the latter we aren't replacing this.
+   */
+  getChildren: (nodeId: NodeId) => Array<NodeId>,
+  startNodeId?: ?NodeId,
+|};
+
 export default class Graph<TNode, TEdgeType: number = 1> {
@@ -54,3 +100,3 @@ nodes: Array<TNode | null>;
   static deserialize(
-    opts: SerializedGraph<TNode, TEdgeType>,
+    opts: GraphOpts<TNode, TEdgeType>,
   ): Graph<TNode, TEdgeType> {
@@ -295,7 +341,13 @@ return new this({
     } else {
-      return this.dfs({
-        visit,
-        startNodeId,
-        getChildren: nodeId => this.getNodeIdsConnectedFrom(nodeId, type),
-      });
+      return getFeatureFlag('dfsFasterRefactor')
+        ? this.dfsNew({
+            visit,
+            startNodeId,
+            getChildren: nodeId => this.getNodeIdsConnectedFrom(nodeId, type),
+          })
+        : this.dfs({
+            visit,
+            startNodeId,
+            getChildren: nodeId => this.getNodeIdsConnectedFrom(nodeId, type),
+          });
     }
@@ -456,2 +508,113 @@ }
 
+  /**
+   * Iterative implementation of DFS that supports all use-cases.
+   *
+   * This replaces `dfs` and will replace `dfsFast`.
+   */
+  dfsNew<TContext>({
+    visit,
+    startNodeId,
+    getChildren,
+  }: DFSParams<TContext>): ?TContext {
+    let traversalStartNode = nullthrows(
+      startNodeId ?? this.rootNodeId,
+      'A start node is required to traverse',
+    );
+    this._assertHasNodeId(traversalStartNode);
+
+    let visited;
+    if (!this._visited || this._visited.capacity < this.nodes.length) {
+      this._visited = new BitSet(this.nodes.length);
+      visited = this._visited;
+    } else {
+      visited = this._visited;
+      visited.clear();
+    }
+    // Take shared instance to avoid re-entrancy issues.
+    this._visited = null;
+
+    let stopped = false;
+    let skipped = false;
+    let actions: TraversalActions = {
+      skipChildren() {
+        skipped = true;
+      },
+      stop() {
+        stopped = true;
+      },
+    };
+
+    const queue: DFSCommand<TContext>[] = [
+      {nodeId: traversalStartNode, context: null},
+    ];
+    const enter = typeof visit === 'function' ? visit : visit.enter;
+    while (queue.length !== 0) {
+      const command = queue.pop();
+
+      if (command.exit != null) {
+        let {nodeId, context, exit} = command;
+        let newContext = exit(nodeId, command.context, actions);
+        if (typeof newContext !== 'undefined') {
+          // $FlowFixMe[reassign-const]
+          context = newContext;
+        }
+
+        if (skipped) {
+          continue;
+        }
+
+        if (stopped) {
+          this._visited = visited;
+          return context;
+        }
+      } else {
+        let {nodeId, context} = command;
+        if (!this.hasNode(nodeId) || visited.has(nodeId)) continue;
+        visited.add(nodeId);
+
+        skipped = false;
+        if (enter) {
+          let newContext = enter(nodeId, context, actions);
+          if (typeof newContext !== 'undefined') {
+            // $FlowFixMe[reassign-const]
+            context = newContext;
+          }
+        }
+
+        if (skipped) {
+          continue;
+        }
+
+        if (stopped) {
+          this._visited = visited;
+          return context;
+        }
+
+        if (typeof visit !== 'function' && visit.exit) {
+          queue.push({
+            nodeId,
+            exit: visit.exit,
+            context,
+          });
+        }
+
+        // TODO turn into generator function
+        const children = getChildren(nodeId);
+        for (let i = children.length - 1; i > -1; i -= 1) {
+          const child = children[i];
+          if (visited.has(child)) {
+            continue;
+          }
+
+          queue.push({nodeId: child, context});
+        }
+      }
+    }
+
+    this._visited = visited;
+  }
+
+  /**
+   * @deprecated Will be replaced by `dfsNew`
+   */
   dfs<TContext>({
@@ -461,7 +624,3 @@ visit,
     getChildren,
-  }: {|
-    visit: GraphVisitor<NodeId, TContext>,
-    getChildren(nodeId: NodeId): Array<NodeId>,
-    startNodeId?: ?NodeId,
-  |}): ?TContext {
+  }: DFSParams<TContext>): ?TContext {
     let traversalStartNode = nullthrows(
@@ -468,0 +627,0 @@ startNodeId ?? this.rootNodeId,

src/types.js

@@ -12,3 +12,3 @@ // @flow strict-local
 
-export type ContentKey = string | number;
+export type ContentKey = string;
 
@@ -15,0 +15,0 @@ export type Edge<TEdgeType: number> = {|

test/AdjacencyList.test.js

@@ -295,3 +295,4 @@ // @flow strict-local
       let received = AdjacencyList.deserialize(await work);
-      await worker.terminate();
+      // eslint-disable-next-line no-unused-vars
+      const _terminatePromise = worker.terminate();
 
@@ -298,0 +299,0 @@ assert.deepEqual(received.serialize().nodes, graph.serialize().nodes);

test/Graph.test.js

@@ -5,5 +5,6 @@ // @flow strict-local
 import sinon from 'sinon';
+import type {TraversalActions} from '@parcel/types-internal';
 
-import Graph from '../src/Graph';
-import {toNodeId} from '../src/types';
+import Graph, {type DFSParams} from '../src/Graph';
+import {toNodeId, type NodeId} from '../src/types';
 
@@ -344,2 +345,227 @@ describe('Graph', () => {
   });
+
+  describe('dfs(...)', () => {
+    function testSuite(
+      name: string,
+      dfsImpl: (graph: Graph<string>, DFSParams<mixed>) => mixed | null | void,
+    ) {
+      it(`${name} throws if the graph is empty`, () => {
+        const graph = new Graph();
+        const visit = sinon.stub();
+        const getChildren = sinon.stub();
+        assert.throws(() => {
+          dfsImpl(graph, {
+            visit,
+            startNodeId: 0,
+            getChildren,
+          });
+        }, /Does not have node 0/);
+      });
+
+      it(`${name} visits a single node`, () => {
+        const graph = new Graph();
+        graph.addNode('root');
+        const visit = sinon.stub();
+        const getChildren = () => [];
+        dfsImpl(graph, {
+          visit,
+          startNodeId: 0,
+          getChildren,
+        });
+
+        assert(visit.calledOnce);
+      });
+
+      it(`${name} visits all connected nodes in DFS order`, () => {
+        const graph = new Graph();
+        graph.addNode('0');
+        graph.addNode('1');
+        graph.addNode('2');
+        graph.addNode('3');
+        graph.addNode('disconnected-1');
+        graph.addNode('disconnected-2');
+        graph.addEdge(0, 1);
+        graph.addEdge(0, 2);
+        graph.addEdge(1, 3);
+        graph.addEdge(2, 3);
+
+        const order = [];
+        const visit = (node: NodeId) => {
+          order.push(node);
+        };
+        const getChildren = (node: NodeId) =>
+          graph.getNodeIdsConnectedFrom(node);
+        dfsImpl(graph, {
+          visit,
+          startNodeId: 0,
+          getChildren,
+        });
+
+        assert.deepEqual(order, [0, 1, 3, 2]);
+      });
+
+      describe(`${name} actions tests`, () => {
+        it(`${name} skips children if skip is called on a node`, () => {
+          const graph = new Graph();
+          graph.addNode('0');
+          graph.addNode('1');
+          graph.addNode('2');
+          graph.addNode('3');
+          graph.addNode('disconnected-1');
+          graph.addNode('disconnected-2');
+          graph.addEdge(0, 1);
+          graph.addEdge(1, 2);
+          graph.addEdge(0, 3);
+
+          const order = [];
+          const visit = (
+            node: NodeId,
+            context: mixed | null,
+            actions: TraversalActions,
+          ) => {
+            if (node === 1) actions.skipChildren();
+            order.push(node);
+          };
+          const getChildren = (node: NodeId) =>
+            graph.getNodeIdsConnectedFrom(node);
+          dfsImpl(graph, {
+            visit,
+            startNodeId: 0,
+            getChildren,
+          });
+
+          assert.deepEqual(order, [0, 1, 3]);
+        });
+
+        it(`${name} stops the traversal if stop is called`, () => {
+          const graph = new Graph();
+          graph.addNode('0');
+          graph.addNode('1');
+          graph.addNode('2');
+          graph.addNode('3');
+          graph.addNode('disconnected-1');
+          graph.addNode('disconnected-2');
+          graph.addEdge(0, 1);
+          graph.addEdge(1, 2);
+          graph.addEdge(1, 3);
+          graph.addEdge(0, 2);
+          graph.addEdge(2, 3);
+
+          const order = [];
+          const visit = (
+            node: NodeId,
+            context: mixed | null,
+            actions: TraversalActions,
+          ) => {
+            order.push(node);
+            if (node === 1) {
+              actions.stop();
+              return 'result';
+            }
+            return 'other';
+          };
+          const getChildren = (node: NodeId) =>
+            graph.getNodeIdsConnectedFrom(node);
+          const result = dfsImpl(graph, {
+            visit,
+            startNodeId: 0,
+            getChildren,
+          });
+
+          assert.deepEqual(order, [0, 1]);
+          assert.equal(result, 'result');
+        });
+      });
+
+      describe(`${name} context tests`, () => {
+        it(`${name} passes the context between visitors`, () => {
+          const graph = new Graph();
+          graph.addNode('0');
+          graph.addNode('1');
+          graph.addNode('2');
+          graph.addNode('3');
+          graph.addNode('disconnected-1');
+          graph.addNode('disconnected-2');
+          graph.addEdge(0, 1);
+          graph.addEdge(1, 2);
+          graph.addEdge(1, 3);
+          graph.addEdge(0, 2);
+          graph.addEdge(2, 3);
+
+          const contexts = [];
+          const visit = (node: NodeId, context: mixed | null) => {
+            contexts.push([node, context]);
+            return `node-${node}-created-context`;
+          };
+          const getChildren = (node: NodeId) =>
+            graph.getNodeIdsConnectedFrom(node);
+          const result = dfsImpl(graph, {
+            visit,
+            startNodeId: 0,
+            getChildren,
+          });
+
+          assert.deepEqual(contexts, [
+            [0, undefined],
+            [1, 'node-0-created-context'],
+            [2, 'node-1-created-context'],
+            [3, 'node-2-created-context'],
+          ]);
+          assert.equal(result, undefined);
+        });
+      });
+
+      describe(`${name} exit visitor tests`, () => {
+        it(`${name} calls the exit visitor`, () => {
+          const graph = new Graph();
+          graph.addNode('0');
+          graph.addNode('1');
+          graph.addNode('2');
+          graph.addNode('3');
+          graph.addNode('disconnected-1');
+          graph.addNode('disconnected-2');
+          graph.addEdge(0, 1);
+          graph.addEdge(1, 2);
+          graph.addEdge(1, 3);
+          graph.addEdge(0, 2);
+
+          const contexts = [];
+          const visit = (node: NodeId, context: mixed | null) => {
+            contexts.push([node, context]);
+            return `node-${node}-created-context`;
+          };
+          const visitExit = (node: NodeId, context: mixed | null) => {
+            contexts.push(['exit', node, context]);
+            return `node-exit-${node}-created-context`;
+          };
+          const getChildren = (node: NodeId) =>
+            graph.getNodeIdsConnectedFrom(node);
+          const result = dfsImpl(graph, {
+            visit: {
+              enter: visit,
+              exit: visitExit,
+            },
+            startNodeId: 0,
+            getChildren,
+          });
+
+          assert.deepEqual(contexts, [
+            [0, undefined],
+            [1, 'node-0-created-context'],
+            [2, 'node-1-created-context'],
+            ['exit', 2, 'node-2-created-context'],
+            [3, 'node-1-created-context'],
+            ['exit', 3, 'node-3-created-context'],
+            ['exit', 1, 'node-1-created-context'],
+            ['exit', 0, 'node-0-created-context'],
+          ]);
+          assert.equal(result, undefined);
+        });
+      });
+    }
+
+    testSuite('dfs', (graph, params) => graph.dfs(params));
+
+    testSuite('dfsNew', (graph, params) => graph.dfsNew(params));
+  });
 });

test/integration/adjacency-list-shared-array.js

@@ -9,3 +9,3 @@ require('@parcel/babel-register');
 
-parentPort.once('message', (serialized) => {
+parentPort.once('message', serialized => {
   let graph = AdjacencyList.deserialize(serialized);
@@ -12,0 +12,0 @@ serialized.nodes.forEach((v, i) => {

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

Manifest confusion

Supply chain risk

This package has inconsistent metadata. This could be malicious or caused by an error when publishing the package.

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

Manifest confusion

Supply chain risk

This package has inconsistent metadata. This could be malicious or caused by an error when publishing the package.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

186726

increased by8.3%

Lines of code

5527

increased by9.27%

Worsened metrics

Dependency count

2

increased by100%

Dependency changes

• + Added@parcel/feature-flags@2.12.1-dev.3260+339350eb3