From 3c51c3be85bb0d1bdb87ea0d6632f1c256912f27 Mon Sep 17 00:00:00 2001 From: Dimitri Staessens Date: Sun, 6 Oct 2019 21:37:45 +0200 Subject: build: Add some required modules for node --- node_modules/dependency-graph/lib/dep_graph.js | 244 +++++++++++++++++++++++++ node_modules/dependency-graph/lib/index.d.ts | 89 +++++++++ 2 files changed, 333 insertions(+) create mode 100755 node_modules/dependency-graph/lib/dep_graph.js create mode 100755 node_modules/dependency-graph/lib/index.d.ts (limited to 'node_modules/dependency-graph/lib') diff --git a/node_modules/dependency-graph/lib/dep_graph.js b/node_modules/dependency-graph/lib/dep_graph.js new file mode 100755 index 0000000..fb0e5ae --- /dev/null +++ b/node_modules/dependency-graph/lib/dep_graph.js @@ -0,0 +1,244 @@ +/** + * A simple dependency graph + */ + +/** + * Helper for creating a Depth-First-Search on + * a set of edges. + * + * Detects cycles and throws an Error if one is detected. + * + * @param edges The set of edges to DFS through + * @param leavesOnly Whether to only return "leaf" nodes (ones who have no edges) + * @param result An array in which the results will be populated + * @param circular A boolean to allow circular dependencies + */ +function createDFS(edges, leavesOnly, result, circular) { + var currentPath = []; + var visited = {}; + return function DFS(currentNode) { + visited[currentNode] = true; + currentPath.push(currentNode); + edges[currentNode].forEach(function (node) { + if (!visited[node]) { + DFS(node); + } else if (currentPath.indexOf(node) >= 0) { + currentPath.push(node); + if (!circular) { + throw new Error('Dependency Cycle Found: ' + currentPath.join(' -> ')); + } + } + }); + currentPath.pop(); + if ((!leavesOnly || edges[currentNode].length === 0) && result.indexOf(currentNode) === -1) { + result.push(currentNode); + } + }; +} + +/** + * Simple Dependency Graph + */ +var DepGraph = exports.DepGraph = function DepGraph(opts) { + this.nodes = {}; // Node -> Node/Data (treated like a Set) + this.outgoingEdges = {}; // Node -> [Dependency Node] + this.incomingEdges = {}; // Node -> [Dependant Node] + this.circular = opts && !!opts.circular; // Allows circular deps +}; +DepGraph.prototype = { + /** + * The number of nodes in the graph. + */ + size:function () { + return Object.keys(this.nodes).length; + }, + /** + * Add a node to the dependency graph. If a node already exists, this method will do nothing. + */ + addNode:function (node, data) { + if (!this.hasNode(node)) { + // Checking the arguments length allows the user to add a node with undefined data + if (arguments.length === 2) { + this.nodes[node] = data; + } else { + this.nodes[node] = node; + } + this.outgoingEdges[node] = []; + this.incomingEdges[node] = []; + } + }, + /** + * Remove a node from the dependency graph. If a node does not exist, this method will do nothing. + */ + removeNode:function (node) { + if (this.hasNode(node)) { + delete this.nodes[node]; + delete this.outgoingEdges[node]; + delete this.incomingEdges[node]; + [this.incomingEdges, this.outgoingEdges].forEach(function (edgeList) { + Object.keys(edgeList).forEach(function (key) { + var idx = edgeList[key].indexOf(node); + if (idx >= 0) { + edgeList[key].splice(idx, 1); + } + }, this); + }); + } + }, + /** + * Check if a node exists in the graph + */ + hasNode:function (node) { + return this.nodes.hasOwnProperty(node); + }, + /** + * Get the data associated with a node name + */ + getNodeData:function (node) { + if (this.hasNode(node)) { + return this.nodes[node]; + } else { + throw new Error('Node does not exist: ' + node); + } + }, + /** + * Set the associated data for a given node name. If the node does not exist, this method will throw an error + */ + setNodeData:function (node, data) { + if (this.hasNode(node)) { + this.nodes[node] = data; + } else { + throw new Error('Node does not exist: ' + node); + } + }, + /** + * Add a dependency between two nodes. If either of the nodes does not exist, + * an Error will be thrown. + */ + addDependency:function (from, to) { + if (!this.hasNode(from)) { + throw new Error('Node does not exist: ' + from); + } + if (!this.hasNode(to)) { + throw new Error('Node does not exist: ' + to); + } + if (this.outgoingEdges[from].indexOf(to) === -1) { + this.outgoingEdges[from].push(to); + } + if (this.incomingEdges[to].indexOf(from) === -1) { + this.incomingEdges[to].push(from); + } + return true; + }, + /** + * Remove a dependency between two nodes. + */ + removeDependency:function (from, to) { + var idx; + if (this.hasNode(from)) { + idx = this.outgoingEdges[from].indexOf(to); + if (idx >= 0) { + this.outgoingEdges[from].splice(idx, 1); + } + } + + if (this.hasNode(to)) { + idx = this.incomingEdges[to].indexOf(from); + if (idx >= 0) { + this.incomingEdges[to].splice(idx, 1); + } + } + }, + /** + * Return a clone of the dependency graph. If any custom data is attached + * to the nodes, it will only be shallow copied. + */ + clone:function () { + var source = this; + var result = new DepGraph(); + var keys = Object.keys(source.nodes); + keys.forEach(function (n) { + result.nodes[n] = source.nodes[n]; + result.outgoingEdges[n] = source.outgoingEdges[n].slice(0); + result.incomingEdges[n] = source.incomingEdges[n].slice(0); + }); + return result; + }, + /** + * Get an array containing the nodes that the specified node depends on (transitively). + * + * Throws an Error if the graph has a cycle, or the specified node does not exist. + * + * If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned + * in the array. + */ + dependenciesOf:function (node, leavesOnly) { + if (this.hasNode(node)) { + var result = []; + var DFS = createDFS(this.outgoingEdges, leavesOnly, result, this.circular); + DFS(node); + var idx = result.indexOf(node); + if (idx >= 0) { + result.splice(idx, 1); + } + return result; + } + else { + throw new Error('Node does not exist: ' + node); + } + }, + /** + * get an array containing the nodes that depend on the specified node (transitively). + * + * Throws an Error if the graph has a cycle, or the specified node does not exist. + * + * If `leavesOnly` is true, only nodes that do not have any dependants will be returned in the array. + */ + dependantsOf:function (node, leavesOnly) { + if (this.hasNode(node)) { + var result = []; + var DFS = createDFS(this.incomingEdges, leavesOnly, result, this.circular); + DFS(node); + var idx = result.indexOf(node); + if (idx >= 0) { + result.splice(idx, 1); + } + return result; + } else { + throw new Error('Node does not exist: ' + node); + } + }, + /** + * Construct the overall processing order for the dependency graph. + * + * Throws an Error if the graph has a cycle. + * + * If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned. + */ + overallOrder:function (leavesOnly) { + var self = this; + var result = []; + var keys = Object.keys(this.nodes); + if (keys.length === 0) { + return result; // Empty graph + } else { + // Look for cycles - we run the DFS starting at all the nodes in case there + // are several disconnected subgraphs inside this dependency graph. + var CycleDFS = createDFS(this.outgoingEdges, false, [], this.circular); + keys.forEach(function(n) { + CycleDFS(n); + }); + + var DFS = createDFS(this.outgoingEdges, leavesOnly, result, this.circular); + // Find all potential starting points (nodes with nothing depending on them) an + // run a DFS starting at these points to get the order + keys.filter(function (node) { + return self.incomingEdges[node].length === 0; + }).forEach(function (n) { + DFS(n); + }); + + return result; + } + } +}; diff --git a/node_modules/dependency-graph/lib/index.d.ts b/node_modules/dependency-graph/lib/index.d.ts new file mode 100755 index 0000000..76aef0a --- /dev/null +++ b/node_modules/dependency-graph/lib/index.d.ts @@ -0,0 +1,89 @@ +declare module 'dependency-graph' { + export interface Options { + circular?: boolean; + } + + export class DepGraph { + /** + * Creates an instance of DepGraph with optional Options. + */ + constructor(opts?: Options); + + /** + * The number of nodes in the graph. + */ + size(): number; + + /** + * Add a node in the graph with optional data. If data is not given, name will be used as data. + * @param {string} name + * @param data + */ + addNode(name: string, data?: T): void; + + /** + * Remove a node from the graph. + * @param {string} name + */ + removeNode(name: string): void; + + /** + * Check if a node exists in the graph. + * @param {string} name + */ + hasNode(name: string): boolean; + + /** + * Get the data associated with a node (will throw an Error if the node does not exist). + * @param {string} name + */ + getNodeData(name: string): T; + + /** + * Set the data for an existing node (will throw an Error if the node does not exist). + * @param {string} name + * @param data + */ + setNodeData(name: string, data?: T): void; + + /** + * Add a dependency between two nodes (will throw an Error if one of the nodes does not exist). + * @param {string} from + * @param {string} to + */ + addDependency(from: string, to: string): void; + + /** + * Remove a dependency between two nodes. + * @param {string} from + * @param {string} to + */ + removeDependency(from: string, to: string): void; + + /** + * Return a clone of the dependency graph (If any custom data is attached + * to the nodes, it will only be shallow copied). + */ + clone(): DepGraph; + + /** + * Get an array containing the nodes that the specified node depends on (transitively). If leavesOnly is true, only nodes that do not depend on any other nodes will be returned in the array. + * @param {string} name + * @param {boolean} leavesOnly + */ + dependenciesOf(name: string, leavesOnly?: boolean): string[]; + + /** + * Get an array containing the nodes that depend on the specified node (transitively). If leavesOnly is true, only nodes that do not have any dependants will be returned in the array. + * @param {string} name + * @param {boolean} leavesOnly + */ + dependantsOf(name: string, leavesOnly?: boolean): string[]; + + /** + * Construct the overall processing order for the dependency graph. If leavesOnly is true, only nodes that do not depend on any other nodes will be returned. + * @param {boolean} leavesOnly + */ + overallOrder(leavesOnly?: boolean): string[]; + } +} -- cgit v1.2.3