{"version":3,"sources":["../../src/util/DepGraph.ts"],"names":[],"mappings":";AAAA;;;;GAIG;;AAEH;;GAEG;AAEH;;;;;;;;;GASG;AACH,SAAS,SAAS,CAAC,KAAU,EAAE,UAAe,EAAE,MAAW;IACvD,IAAI,WAAW,GAAU,EAAE,CAAC;IAC5B,IAAI,OAAO,GAAQ,EAAE,CAAC;IACtB,OAAO,SAAS,GAAG,CAAC,WAAgB;QAChC,OAAO,CAAC,WAAW,CAAC,GAAG,IAAI,CAAC;QAC5B,WAAW,CAAC,IAAI,CAAC,WAAW,CAAC,CAAC;QAC9B,KAAK,CAAC,WAAW,CAAC,CAAC,OAAO,CAAC,UAAU,IAAS;YAC1C,IAAI,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE;gBAChB,GAAG,CAAC,IAAI,CAAC,CAAC;aACb;iBAAM,IAAI,WAAW,CAAC,OAAO,CAAC,IAAI,CAAC,IAAI,CAAC,EAAE;gBACvC,WAAW,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC;gBACvB,MAAM,IAAI,KAAK,CAAC,6BAA2B,WAAW,CAAC,IAAI,CAAC,MAAM,CAAG,CAAC,CAAC;aAC1E;QACL,CAAC,CAAC,CAAC;QACH,WAAW,CAAC,GAAG,EAAE,CAAC;QAClB,IAAI,CAAC,CAAC,UAAU,IAAI,KAAK,CAAC,WAAW,CAAC,CAAC,MAAM,KAAK,CAAC,CAAC,IAAI,MAAM,CAAC,OAAO,CAAC,WAAW,CAAC,KAAK,CAAC,CAAC,EAAE;YACxF,MAAM,CAAC,IAAI,CAAC,WAAW,CAAC,CAAC;SAC5B;IACL,CAAC,CAAC;AACN,CAAC;AAGD;IAAA;QACI,UAAK,GAAQ,EAAE,CAAC;QAChB,kBAAa,GAAQ,EAAE,CAAC,CAAC,4BAA4B;QACrD,kBAAa,GAAQ,EAAE,CAAC,CAAC,2BAA2B;IA0LxD,CAAC;IAxLG;;OAEG;IACH,0BAAO,GAAP,UAAQ,IAAS,EAAE,IAAU;QACzB,IAAI,CAAC,IAAI,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE;YACrB,kFAAkF;YAClF,IAAI,SAAS,CAAC,MAAM,KAAK,CAAC,EAAE;gBACxB,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,GAAG,IAAI,CAAC;aAC3B;iBAAM;gBACH,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,GAAG,IAAI,CAAC;aAC3B;YACD,IAAI,CAAC,aAAa,CAAC,IAAI,CAAC,GAAG,EAAE,CAAC;YAC9B,IAAI,CAAC,aAAa,CAAC,IAAI,CAAC,GAAG,EAAE,CAAC;SACjC;IACL,CAAC;IAED;;OAEG;IACH,6BAAU,GAAV,UAAW,IAAS;QAChB,IAAI,IAAI,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE;YACpB,OAAO,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,CAAC;YACxB,OAAO,IAAI,CAAC,aAAa,CAAC,IAAI,CAAC,CAAC;YAChC,OAAO,IAAI,CAAC,aAAa,CAAC,IAAI,CAAC,CAAC;YAChC,CAAC,IAAI,CAAC,aAAa,EAAE,IAAI,CAAC,aAAa,CAAC,CAAC,OAAO,CAAC,UAAU,QAAQ;gBAC/D,MAAM,CAAC,IAAI,CAAC,QAAQ,CAAC,CAAC,OAAO,CAAC,UAAU,GAAQ;oBAC5C,IAAI,GAAG,GAAG,QAAQ,CAAC,GAAG,CAAC,CAAC,OAAO,CAAC,IAAI,CAAC,CAAC;oBACtC,IAAI,GAAG,IAAI,CAAC,EAAE;wBACV,QAAQ,CAAC,GAAG,CAAC,CAAC,MAAM,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC;qBAChC;gBACL,CAAC,EAAE,IAAI,CAAC,CAAC;YACb,CAAC,CAAC,CAAC;SACN;IACL,CAAC;IAED;;OAEG;IACH,0BAAO,GAAP,UAAQ,IAAS;QACb,OAAO,IAAI,CAAC,KAAK,CAAC,cAAc,CAAC,IAAI,CAAC,CAAC;IAC3C,CAAC;IAED;;OAEG;IACH,8BAAW,GAAX,UAAY,IAAS;QACjB,IAAI,IAAI,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE;YACpB,OAAO,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,CAAC;SAC3B;aAAM;YACH,MAAM,IAAI,KAAK,CAAC,0BAAwB,IAAM,CAAC,CAAC;SACnD;IACL,CAAC;IAED;;OAEG;IACH,8BAAW,GAAX,UAAY,IAAS,EAAE,IAAS;QAC5B,IAAI,IAAI,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE;YACpB,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,GAAG,IAAI,CAAC;SAC3B;aAAM;YACH,MAAM,IAAI,KAAK,CAAC,0BAAwB,IAAM,CAAC,CAAC;SACnD;IACL,CAAC;IAED;;;OAGG;IACH,gCAAa,GAAb,UAAc,IAAS,EAAE,EAAO;QAC5B,IAAI,CAAC,IAAI,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE;YACrB,MAAM,IAAI,KAAK,CAAC,0BAAwB,IAAM,CAAC,CAAC;SACnD;QACD,IAAI,CAAC,IAAI,CAAC,OAAO,CAAC,EAAE,CAAC,EAAE;YACnB,MAAM,IAAI,KAAK,CAAC,0BAAwB,EAAI,CAAC,CAAC;SACjD;QACD,IAAI,IAAI,CAAC,aAAa,CAAC,IAAI,CAAC,CAAC,OAAO,CAAC,EAAE,CAAC,KAAK,CAAC,CAAC,EAAE;YAC7C,IAAI,CAAC,aAAa,CAAC,IAAI,CAAC,CAAC,IAAI,CAAC,EAAE,CAAC,CAAC;SACrC;QACD,IAAI,IAAI,CAAC,aAAa,CAAC,EAAE,CAAC,CAAC,OAAO,CAAC,IAAI,CAAC,KAAK,CAAC,CAAC,EAAE;YAC7C,IAAI,CAAC,aAAa,CAAC,EAAE,CAAC,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC;SACrC;QACD,OAAO,IAAI,CAAC;IAChB,CAAC;IAED;;OAEG;IACH,mCAAgB,GAAhB,UAAiB,IAAS,EAAE,EAAO;QAC/B,IAAI,GAAQ,CAAC;QACb,IAAI,IAAI,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE;YACpB,GAAG,GAAG,IAAI,CAAC,aAAa,CAAC,IAAI,CAAC,CAAC,OAAO,CAAC,EAAE,CAAC,CAAC;YAC3C,IAAI,GAAG,IAAI,CAAC,EAAE;gBACV,IAAI,CAAC,aAAa,CAAC,IAAI,CAAC,CAAC,MAAM,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC;aAC3C;SACJ;QAED,IAAI,IAAI,CAAC,OAAO,CAAC,EAAE,CAAC,EAAE;YAClB,GAAG,GAAG,IAAI,CAAC,aAAa,CAAC,EAAE,CAAC,CAAC,OAAO,CAAC,IAAI,CAAC,CAAC;YAC3C,IAAI,GAAG,IAAI,CAAC,EAAE;gBACV,IAAI,CAAC,aAAa,CAAC,EAAE,CAAC,CAAC,MAAM,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC;aACzC;SACJ;IACL,CAAC;IAED;;;;;;;OAOG;IACH,iCAAc,GAAd,UAAe,IAAS,EAAE,UAAe;QACrC,IAAI,IAAI,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE;YACpB,IAAI,MAAM,GAAU,EAAE,CAAC;YACvB,IAAI,GAAG,GAAG,SAAS,CAAC,IAAI,CAAC,aAAa,EAAE,UAAU,EAAE,MAAM,CAAC,CAAC;YAC5D,GAAG,CAAC,IAAI,CAAC,CAAC;YACV,IAAI,GAAG,GAAG,MAAM,CAAC,OAAO,CAAC,IAAI,CAAC,CAAC;YAC/B,IAAI,GAAG,IAAI,CAAC,EAAE;gBACV,MAAM,CAAC,MAAM,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC;aACzB;YACD,OAAO,MAAM,CAAC;SACjB;aACI;YACD,MAAM,IAAI,KAAK,CAAC,0BAAwB,IAAM,CAAC,CAAC;SACnD;IACL,CAAC;IAED;;;;;;OAMG;IACH,+BAAY,GAAZ,UAAa,IAAS,EAAE,UAAe;QACnC,IAAI,IAAI,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE;YACpB,IAAI,MAAM,GAAU,EAAE,CAAC;YACvB,IAAI,GAAG,GAAG,SAAS,CAAC,IAAI,CAAC,aAAa,EAAE,UAAU,EAAE,MAAM,CAAC,CAAC;YAC5D,GAAG,CAAC,IAAI,CAAC,CAAC;YACV,IAAI,GAAG,GAAG,MAAM,CAAC,OAAO,CAAC,IAAI,CAAC,CAAC;YAC/B,IAAI,GAAG,IAAI,CAAC,EAAE;gBACV,MAAM,CAAC,MAAM,CAAC,GAAG,EAAE,CAAC,CAAC,CAAC;aACzB;YACD,OAAO,MAAM,CAAC;SACjB;aAAM;YACH,MAAM,IAAI,KAAK,CAAC,0BAAwB,IAAM,CAAC,CAAC;SACnD;IACL,CAAC;IAED;;;;;;OAMG;IACH,+BAAY,GAAZ,UAAa,UAAgB;QACzB,IAAI,IAAI,GAAG,IAAI,CAAC;QAChB,IAAI,MAAM,GAAU,EAAE,CAAC;QACvB,IAAI,IAAI,GAAG,MAAM,CAAC,IAAI,CAAC,IAAI,CAAC,KAAK,CAAC,CAAC;QACnC,IAAI,IAAI,CAAC,MAAM,KAAK,CAAC,EAAE;YACnB,OAAO,MAAM,CAAC,CAAC,cAAc;SAChC;aAAM;YACH,2EAA2E;YAC3E,mEAAmE;YACnE,IAAI,UAAQ,GAAG,SAAS,CAAC,IAAI,CAAC,aAAa,EAAE,KAAK,EAAE,EAAE,CAAC,CAAC;YACxD,IAAI,CAAC,OAAO,CAAC,UAAU,CAAM;gBACzB,UAAQ,CAAC,CAAC,CAAC,CAAC;YAChB,CAAC,CAAC,CAAC;YAEH,IAAI,KAAG,GAAG,SAAS,CAAC,IAAI,CAAC,aAAa,EAAE,UAAU,EAAE,MAAM,CAAC,CAAC;YAC5D,+EAA+E;YAC/E,sDAAsD;YACtD,IAAI,CAAC,MAAM,CAAC,UAAU,IAAI;gBACtB,OAAO,IAAI,CAAC,aAAa,CAAC,IAAI,CAAC,CAAC,MAAM,KAAK,CAAC,CAAC;YACjD,CAAC,CAAC,CAAC,OAAO,CAAC,UAAU,CAAC;gBAClB,KAAG,CAAC,CAAC,CAAC,CAAC;YACX,CAAC,CAAC,CAAC;YAEH,OAAO,MAAM,CAAC;SACjB;IACL,CAAC;IAEL,eAAC;AAAD,CA7LA,AA6LC,IAAA;AA7LY,4BAAQ","file":"DepGraph.js","sourcesContent":["/**\n * This source code is from https://github.com/jriecken/dependency-graph\n * Just added \"any\" types here, wrapper everything into exported class.\n * We cant use a package itself because we want to package \"everything-in-it\" for the frontend users of TypeORM.\n */\n\n/**\n * A simple dependency graph\n */\n\n/**\n * Helper for creating a Depth-First-Search on\n * a set of edges.\n *\n * Detects cycles and throws an Error if one is detected.\n *\n * @param edges The set of edges to DFS through\n * @param leavesOnly Whether to only return \"leaf\" nodes (ones who have no edges)\n * @param result An array in which the results will be populated\n */\nfunction createDFS(edges: any, leavesOnly: any, result: any) {\n let currentPath: any[] = [];\n let visited: any = {};\n return function DFS(currentNode: any) {\n visited[currentNode] = true;\n currentPath.push(currentNode);\n edges[currentNode].forEach(function (node: any) {\n if (!visited[node]) {\n DFS(node);\n } else if (currentPath.indexOf(node) >= 0) {\n currentPath.push(node);\n throw new Error(`Dependency Cycle Found: ${currentPath.join(\" -> \")}`);\n }\n });\n currentPath.pop();\n if ((!leavesOnly || edges[currentNode].length === 0) && result.indexOf(currentNode) === -1) {\n result.push(currentNode);\n }\n };\n}\n\n\nexport class DepGraph {\n nodes: any = {};\n outgoingEdges: any = {}; // Node -> [Dependency Node]\n incomingEdges: any = {}; // Node -> [Dependant Node]\n\n /**\n * Add a node to the dependency graph. If a node already exists, this method will do nothing.\n */\n addNode(node: any, data?: any) {\n if (!this.hasNode(node)) {\n // Checking the arguments length allows the user to add a node with undefined data\n if (arguments.length === 2) {\n this.nodes[node] = data;\n } else {\n this.nodes[node] = node;\n }\n this.outgoingEdges[node] = [];\n this.incomingEdges[node] = [];\n }\n }\n\n /**\n * Remove a node from the dependency graph. If a node does not exist, this method will do nothing.\n */\n removeNode(node: any) {\n if (this.hasNode(node)) {\n delete this.nodes[node];\n delete this.outgoingEdges[node];\n delete this.incomingEdges[node];\n [this.incomingEdges, this.outgoingEdges].forEach(function (edgeList) {\n Object.keys(edgeList).forEach(function (key: any) {\n let idx = edgeList[key].indexOf(node);\n if (idx >= 0) {\n edgeList[key].splice(idx, 1);\n }\n }, this);\n });\n }\n }\n\n /**\n * Check if a node exists in the graph\n */\n hasNode(node: any) {\n return this.nodes.hasOwnProperty(node);\n }\n\n /**\n * Get the data associated with a node name\n */\n getNodeData(node: any) {\n if (this.hasNode(node)) {\n return this.nodes[node];\n } else {\n throw new Error(`Node does not exist: ${node}`);\n }\n }\n\n /**\n * Set the associated data for a given node name. If the node does not exist, this method will throw an error\n */\n setNodeData(node: any, data: any) {\n if (this.hasNode(node)) {\n this.nodes[node] = data;\n } else {\n throw new Error(`Node does not exist: ${node}`);\n }\n }\n\n /**\n * Add a dependency between two nodes. If either of the nodes does not exist,\n * an Error will be thrown.\n */\n addDependency(from: any, to: any) {\n if (!this.hasNode(from)) {\n throw new Error(`Node does not exist: ${from}`);\n }\n if (!this.hasNode(to)) {\n throw new Error(`Node does not exist: ${to}`);\n }\n if (this.outgoingEdges[from].indexOf(to) === -1) {\n this.outgoingEdges[from].push(to);\n }\n if (this.incomingEdges[to].indexOf(from) === -1) {\n this.incomingEdges[to].push(from);\n }\n return true;\n }\n\n /**\n * Remove a dependency between two nodes.\n */\n removeDependency(from: any, to: any) {\n let idx: any;\n if (this.hasNode(from)) {\n idx = this.outgoingEdges[from].indexOf(to);\n if (idx >= 0) {\n this.outgoingEdges[from].splice(idx, 1);\n }\n }\n\n if (this.hasNode(to)) {\n idx = this.incomingEdges[to].indexOf(from);\n if (idx >= 0) {\n this.incomingEdges[to].splice(idx, 1);\n }\n }\n }\n\n /**\n * Get an array containing the nodes that the specified node depends on (transitively).\n *\n * Throws an Error if the graph has a cycle, or the specified node does not exist.\n *\n * If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned\n * in the array.\n */\n dependenciesOf(node: any, leavesOnly: any) {\n if (this.hasNode(node)) {\n let result: any[] = [];\n let DFS = createDFS(this.outgoingEdges, leavesOnly, result);\n DFS(node);\n let idx = result.indexOf(node);\n if (idx >= 0) {\n result.splice(idx, 1);\n }\n return result;\n }\n else {\n throw new Error(`Node does not exist: ${node}`);\n }\n }\n\n /**\n * get an array containing the nodes that depend on the specified node (transitively).\n *\n * Throws an Error if the graph has a cycle, or the specified node does not exist.\n *\n * If `leavesOnly` is true, only nodes that do not have any dependants will be returned in the array.\n */\n dependantsOf(node: any, leavesOnly: any) {\n if (this.hasNode(node)) {\n let result: any[] = [];\n let DFS = createDFS(this.incomingEdges, leavesOnly, result);\n DFS(node);\n let idx = result.indexOf(node);\n if (idx >= 0) {\n result.splice(idx, 1);\n }\n return result;\n } else {\n throw new Error(`Node does not exist: ${node}`);\n }\n }\n\n /**\n * Construct the overall processing order for the dependency graph.\n *\n * Throws an Error if the graph has a cycle.\n *\n * If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned.\n */\n overallOrder(leavesOnly?: any) {\n let self = this;\n let result: any[] = [];\n let keys = Object.keys(this.nodes);\n if (keys.length === 0) {\n return result; // Empty graph\n } else {\n // Look for cycles - we run the DFS starting at all the nodes in case there\n // are several disconnected subgraphs inside this dependency graph.\n let CycleDFS = createDFS(this.outgoingEdges, false, []);\n keys.forEach(function (n: any) {\n CycleDFS(n);\n });\n\n let DFS = createDFS(this.outgoingEdges, leavesOnly, result);\n // Find all potential starting points (nodes with nothing depending on them) an\n // run a DFS starting at these points to get the order\n keys.filter(function (node) {\n return self.incomingEdges[node].length === 0;\n }).forEach(function (n) {\n DFS(n);\n });\n\n return result;\n }\n }\n\n}"],"sourceRoot":".."}
|
