Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
@parcel/graph
Advanced tools
@parcel/graph - npm Package Compare versions
Comparing version 3.2.1-canary.3267 to 3.2.1-canary.3269
@@ -10,9 +10,2 @@ "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"); | ||
@@ -199,10 +192,6 @@ function _nullthrows() { | ||
| } else { | ||
| return (0, _featureFlags().getFeatureFlag)('dfsFasterRefactor') ? this.dfsNew({ | ||
| return this.dfs({ | ||
| visit, | ||
| startNodeId, | ||
| getChildren: nodeId => this.getNodeIdsConnectedFrom(nodeId, type) | ||
| }) : this.dfs({ | ||
| visit, | ||
| startNodeId, | ||
| getChildren: nodeId => this.getNodeIdsConnectedFrom(nodeId, type) | ||
| }); | ||
@@ -332,3 +321,3 @@ } | ||
| */ | ||
| dfsNew({ | ||
| dfs({ | ||
| visit, | ||
@@ -431,81 +420,2 @@ startNodeId, | ||
| } | ||
| /** | ||
| * @deprecated Will be replaced by `dfsNew` | ||
| */ | ||
| dfs({ | ||
| 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; | ||
| } | ||
| }; | ||
| let walk = (nodeId, context) => { | ||
| if (!this.hasNode(nodeId)) return; | ||
| visited.add(nodeId); | ||
| skipped = false; | ||
| let enter = typeof visit === 'function' ? visit : visit.enter; | ||
| if (enter) { | ||
| let newContext = enter(nodeId, context, actions); | ||
| if (typeof newContext !== 'undefined') { | ||
| // $FlowFixMe[reassign-const] | ||
| context = newContext; | ||
| } | ||
| } | ||
| if (skipped) { | ||
| return; | ||
| } | ||
| if (stopped) { | ||
| return context; | ||
| } | ||
| for (let child of getChildren(nodeId)) { | ||
| if (visited.has(child)) { | ||
| continue; | ||
| } | ||
| visited.add(child); | ||
| let result = walk(child, context); | ||
| if (stopped) { | ||
| return result; | ||
| } | ||
| } | ||
| if (typeof visit !== 'function' && visit.exit && | ||
| // Make sure the graph still has the node: it may have been removed between enter and exit | ||
| this.hasNode(nodeId)) { | ||
| let newContext = visit.exit(nodeId, context, actions); | ||
| if (typeof newContext !== 'undefined') { | ||
| // $FlowFixMe[reassign-const] | ||
| context = newContext; | ||
| } | ||
| } | ||
| if (skipped) { | ||
| return; | ||
| } | ||
| if (stopped) { | ||
| return context; | ||
| } | ||
| }; | ||
| let result = walk(traversalStartNode); | ||
| this._visited = visited; | ||
| return result; | ||
| } | ||
| bfs(visit) { | ||
@@ -512,0 +422,0 @@ let rootNodeId = (0, _nullthrows().default)(this.rootNodeId, 'A root node is required to traverse'); |
| { | ||
| "name": "@parcel/graph", | ||
| "version": "3.2.1-canary.3267+bcc68e119", | ||
| "version": "3.2.1-canary.3269+9eff0bfeb", | ||
| "description": "Blazing fast, zero configuration web application bundler", | ||
@@ -23,6 +23,6 @@ "license": "MIT", | ||
| "dependencies": { | ||
| "@parcel/feature-flags": "2.12.1-canary.3267+bcc68e119", | ||
| "@parcel/feature-flags": "2.12.1-canary.3269+9eff0bfeb", | ||
| "nullthrows": "^1.1.1" | ||
| }, | ||
| "gitHead": "bcc68e1196ad4df0a75a2f41fd50fdacb2b7a561" | ||
| "gitHead": "9eff0bfeb655845c8ffd86d8acdba9a21bbafc82" | ||
| } |
116
src/Graph.js
@@ -6,3 +6,2 @@ // @flow strict-local | ||
| import type {Edge, NodeId} from './types'; | ||
| import {getFeatureFlag} from '@parcel/feature-flags'; | ||
| import type { | ||
@@ -339,13 +338,7 @@ TraversalActions, | ||
| } else { | ||
| return getFeatureFlag('dfsFasterRefactor') | ||
| ? this.dfsNew({ | ||
| visit, | ||
| startNodeId, | ||
| getChildren: nodeId => this.getNodeIdsConnectedFrom(nodeId, type), | ||
| }) | ||
| : this.dfs({ | ||
| visit, | ||
| startNodeId, | ||
| getChildren: nodeId => this.getNodeIdsConnectedFrom(nodeId, type), | ||
| }); | ||
| return this.dfs({ | ||
| visit, | ||
| startNodeId, | ||
| getChildren: nodeId => this.getNodeIdsConnectedFrom(nodeId, type), | ||
| }); | ||
| } | ||
@@ -511,3 +504,3 @@ } | ||
| */ | ||
| dfsNew<TContext>({ | ||
| dfs<TContext>({ | ||
| visit, | ||
@@ -615,99 +608,2 @@ startNodeId, | ||
| /** | ||
| * @deprecated Will be replaced by `dfsNew` | ||
| */ | ||
| dfs<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; | ||
| }, | ||
| }; | ||
| let walk = (nodeId, context: ?TContext) => { | ||
| if (!this.hasNode(nodeId)) return; | ||
| visited.add(nodeId); | ||
| skipped = false; | ||
| let enter = typeof visit === 'function' ? visit : visit.enter; | ||
| if (enter) { | ||
| let newContext = enter(nodeId, context, actions); | ||
| if (typeof newContext !== 'undefined') { | ||
| // $FlowFixMe[reassign-const] | ||
| context = newContext; | ||
| } | ||
| } | ||
| if (skipped) { | ||
| return; | ||
| } | ||
| if (stopped) { | ||
| return context; | ||
| } | ||
| for (let child of getChildren(nodeId)) { | ||
| if (visited.has(child)) { | ||
| continue; | ||
| } | ||
| visited.add(child); | ||
| let result = walk(child, context); | ||
| if (stopped) { | ||
| return result; | ||
| } | ||
| } | ||
| if ( | ||
| typeof visit !== 'function' && | ||
| visit.exit && | ||
| // Make sure the graph still has the node: it may have been removed between enter and exit | ||
| this.hasNode(nodeId) | ||
| ) { | ||
| let newContext = visit.exit(nodeId, context, actions); | ||
| if (typeof newContext !== 'undefined') { | ||
| // $FlowFixMe[reassign-const] | ||
| context = newContext; | ||
| } | ||
| } | ||
| if (skipped) { | ||
| return; | ||
| } | ||
| if (stopped) { | ||
| return context; | ||
| } | ||
| }; | ||
| let result = walk(traversalStartNode); | ||
| this._visited = visited; | ||
| return result; | ||
| } | ||
| bfs(visit: (nodeId: NodeId) => ?boolean): ?NodeId { | ||
@@ -714,0 +610,0 @@ let rootNodeId = nullthrows( |
@@ -7,3 +7,3 @@ // @flow strict-local | ||
| import Graph, {type DFSParams} from '../src/Graph'; | ||
| import Graph from '../src/Graph'; | ||
| import {toNodeId, type NodeId} from '../src/types'; | ||
@@ -347,25 +347,81 @@ | ||
| 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(`throws if the graph is empty`, () => { | ||
| const graph = new Graph(); | ||
| const visit = sinon.stub(); | ||
| const getChildren = sinon.stub(); | ||
| assert.throws(() => { | ||
| graph.dfs({ | ||
| visit, | ||
| startNodeId: 0, | ||
| getChildren, | ||
| }); | ||
| }, /Does not have node 0/); | ||
| }); | ||
| it(`visits a single node`, () => { | ||
| const graph = new Graph(); | ||
| graph.addNode('root'); | ||
| const visit = sinon.stub(); | ||
| const getChildren = () => []; | ||
| graph.dfs({ | ||
| visit, | ||
| startNodeId: 0, | ||
| getChildren, | ||
| }); | ||
| it(`${name} visits a single node`, () => { | ||
| assert(visit.calledOnce); | ||
| }); | ||
| it(`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); | ||
| graph.dfs({ | ||
| visit, | ||
| startNodeId: 0, | ||
| getChildren, | ||
| }); | ||
| assert.deepEqual(order, [0, 1, 3, 2]); | ||
| }); | ||
| describe(`actions tests`, () => { | ||
| it(`skips children if skip is called on a node`, () => { | ||
| const graph = new Graph(); | ||
| graph.addNode('root'); | ||
| const visit = sinon.stub(); | ||
| const getChildren = () => []; | ||
| dfsImpl(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); | ||
| graph.dfs({ | ||
| visit, | ||
@@ -376,6 +432,6 @@ startNodeId: 0, | ||
| assert(visit.calledOnce); | ||
| assert.deepEqual(order, [0, 1, 3]); | ||
| }); | ||
| it(`${name} visits all connected nodes in DFS order`, () => { | ||
| it(`stops the traversal if stop is called`, () => { | ||
| const graph = new Graph(); | ||
@@ -389,13 +445,23 @@ graph.addNode('0'); | ||
| graph.addEdge(0, 1); | ||
| graph.addEdge(1, 2); | ||
| graph.addEdge(1, 3); | ||
| graph.addEdge(0, 2); | ||
| graph.addEdge(1, 3); | ||
| graph.addEdge(2, 3); | ||
| const order = []; | ||
| const visit = (node: NodeId) => { | ||
| 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); | ||
| dfsImpl(graph, { | ||
| const result = graph.dfs({ | ||
| visit, | ||
@@ -406,169 +472,93 @@ startNodeId: 0, | ||
| assert.deepEqual(order, [0, 1, 3, 2]); | ||
| assert.deepEqual(order, [0, 1]); | ||
| assert.equal(result, 'result'); | ||
| }); | ||
| }); | ||
| 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); | ||
| describe(`context tests`, () => { | ||
| it(`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 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]); | ||
| 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 = graph.dfs({ | ||
| visit, | ||
| startNodeId: 0, | ||
| getChildren, | ||
| }); | ||
| 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'); | ||
| }); | ||
| 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} 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); | ||
| describe(`exit visitor tests`, () => { | ||
| it(`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 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); | ||
| 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 = graph.dfs({ | ||
| visit: { | ||
| enter: visit, | ||
| exit: visitExit, | ||
| }, | ||
| startNodeId: 0, | ||
| getChildren, | ||
| }); | ||
| }); | ||
| 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); | ||
| }); | ||
| 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)); | ||
| }); | ||
| }); | ||
| }); |
New alerts
License Policy Violation
LicenseThis 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 riskThis 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
LicenseThis 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 riskThis package has inconsistent metadata. This could be malicious or caused by an error when publishing the package.
Found 1 instance in 1 package
Worsened metrics
- Total package byte prevSize
- decreased by-3.13%
180892
- Lines of code
- decreased by-3.4%
5339