{"version":3,"file":"BaseNode.js","sourceRoot":"","sources":["../../../../../../../../front_end/models/trace/lantern/graph/BaseNode.ts"],"names":[],"mappings":"AAAA,4DAA4D;AAC5D,yEAAyE;AACzE,6BAA6B;AAE7B,OAAO,KAAK,IAAI,MAAM,iBAAiB,CAAC;AAYxC;;;;;;;;;;;GAWG;AAEH,MAAM,QAAQ;IACZ,MAAM,CAAC,KAAK,GAAG;QACb,OAAO,EAAE,SAAS;QAClB,GAAG,EAAE,KAAK;KACF,CAAC;IAEX,GAAG,CAAS;IACZ,eAAe,CAAU;IACzB,UAAU,CAAS;IACnB,YAAY,CAAS;IAErB,YAAY,EAAU;QACpB,IAAI,CAAC,GAAG,GAAG,EAAE,CAAC;QACd,IAAI,CAAC,eAAe,GAAG,KAAK,CAAC;QAC7B,IAAI,CAAC,UAAU,GAAG,EAAE,CAAC;QACrB,IAAI,CAAC,YAAY,GAAG,EAAE,CAAC;IACzB,CAAC;IAED,IAAI,EAAE;QACJ,OAAO,IAAI,CAAC,GAAG,CAAC;IAClB,CAAC;IAED,IAAI,IAAI;QACN,MAAM,IAAI,IAAI,CAAC,YAAY,CAAC,eAAe,CAAC,CAAC;IAC/C,CAAC;IAED;;OAEG;IACH,IAAI,SAAS;QACX,MAAM,IAAI,IAAI,CAAC,YAAY,CAAC,eAAe,CAAC,CAAC;IAC/C,CAAC;IAED;;OAEG;IACH,IAAI,OAAO;QACT,MAAM,IAAI,IAAI,CAAC,YAAY,CAAC,eAAe,CAAC,CAAC;IAC/C,CAAC;IAED,iBAAiB,CAAC,KAAc;QAC9B,IAAI,CAAC,eAAe,GAAG,KAAK,CAAC;IAC/B,CAAC;IAED,cAAc;QACZ,OAAO,IAAI,CAAC,eAAe,CAAC;IAC9B,CAAC;IAED,aAAa;QACX,OAAO,IAAI,CAAC,UAAU,CAAC,KAAK,EAAE,CAAC;IACjC,CAAC;IAED,qBAAqB;QACnB,OAAO,IAAI,CAAC,UAAU,CAAC,MAAM,CAAC;IAChC,CAAC;IAED,eAAe;QACb,OAAO,IAAI,CAAC,YAAY,CAAC,KAAK,EAAE,CAAC;IACnC,CAAC;IAED,uBAAuB;QACrB,OAAO,IAAI,CAAC,YAAY,CAAC,MAAM,CAAC;IAClC,CAAC;IAED,WAAW;QACT,IAAI,QAAQ,GAAG,IAAwB,CAAC;QACxC,OAAO,QAAQ,CAAC,YAAY,CAAC,MAAM,EAAE,CAAC;YACpC,QAAQ,GAAG,QAAQ,CAAC,YAAY,CAAC,CAAC,CAAC,CAAC;QACtC,CAAC;QAED,OAAO,QAAQ,CAAC;IAClB,CAAC;IAED,YAAY,CAAC,IAAU;QACrB,IAAI,CAAC,aAAa,CAAC,IAAwB,CAAC,CAAC;IAC/C,CAAC;IAED,aAAa,CAAC,IAAU;QACtB,+FAA+F;QAC/F,IAAI,IAAI,KAAK,IAAI,EAAE,CAAC;YAClB,MAAM,IAAI,IAAI,CAAC,YAAY,CAAC,iCAAiC,CAAC,CAAC;QACjE,CAAC;QAED,IAAI,IAAI,CAAC,YAAY,CAAC,QAAQ,CAAC,IAAI,CAAC,EAAE,CAAC;YACrC,OAAO;QACT,CAAC;QAED,IAAI,CAAC,UAAU,CAAC,IAAI,CAAC,IAAwB,CAAC,CAAC;QAC/C,IAAI,CAAC,YAAY,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC;IAC/B,CAAC;IAED,eAAe,CAAC,IAAU;QACxB,IAAI,CAAC,gBAAgB,CAAC,IAAwB,CAAC,CAAC;IAClD,CAAC;IAED,gBAAgB,CAAC,IAAU;QACzB,IAAI,CAAC,IAAI,CAAC,YAAY,CAAC,QAAQ,CAAC,IAAI,CAAC,EAAE,CAAC;YACtC,OAAO;QACT,CAAC;QAED,MAAM,SAAS,GAAG,IAAI,CAAC,UAAU,CAAC,OAAO,CAAC,IAAwB,CAAC,CAAC;QACpE,IAAI,CAAC,UAAU,CAAC,MAAM,CAAC,SAAS,EAAE,CAAC,CAAC,CAAC;QACrC,IAAI,CAAC,YAAY,CAAC,MAAM,CAAC,IAAI,CAAC,YAAY,CAAC,OAAO,CAAC,IAAI,CAAC,EAAE,CAAC,CAAC,CAAC;IAC/D,CAAC;IAED,sCAAsC;IACtC,qBAAqB;QACnB,KAAK,MAAM,IAAI,IAAI,IAAI,CAAC,YAAY,CAAC,KAAK,EAAE,EAAE,CAAC;YAC7C,IAAI,CAAC,gBAAgB,CAAC,IAAI,CAAC,CAAC;QAC9B,CAAC;IACH,CAAC;IAED;;;;OAIG;IACH,aAAa,CAAC,IAAiB;QAC7B,IAAI,iBAAiB,GAAG,KAAK,CAAC;QAC9B,IAAI,CAAC,QAAQ,CACT,WAAW,CAAC,EAAE;YACZ,IAAI,iBAAiB,EAAE,CAAC;gBACtB,OAAO;YACT,CAAC;YACD,iBAAiB,GAAG,WAAW,KAAK,IAAI,CAAC;QAC3C,CAAC,EACD,WAAW,CAAC,EAAE;YACZ,iEAAiE;YACjE,IAAI,iBAAiB,EAAE,CAAC;gBACtB,OAAO,EAAE,CAAC;YACZ,CAAC;YACD,wCAAwC;YACxC,OAAO,WAAW,CAAC,eAAe,EAAE,CAAC;QACvC,CAAC,CAAC,CAAC;QAEP,OAAO,iBAAiB,CAAC;IAC3B,CAAC;IAED;;OAEG;IACH,yBAAyB;QACvB,MAAM,IAAI,GAAG,IAAI,QAAQ,CAAC,IAAI,CAAC,EAAE,CAAY,CAAC;QAC9C,IAAI,CAAC,iBAAiB,CAAC,IAAI,CAAC,eAAe,CAAC,CAAC;QAC7C,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;;;;;;;OAQG;IACH,sBAAsB,CAAC,SAAmC;QACxD,MAAM,QAAQ,GAAG,IAAI,CAAC,WAAW,EAAE,CAAC;QAEpC,MAAM,mBAAmB,GAAG,IAAI,GAAG,EAAgB,CAAC;QAEpD,wBAAwB;QACxB,QAAQ,CAAC,QAAQ,CAAC,IAAI,CAAC,EAAE;YACvB,IAAI,mBAAmB,CAAC,GAAG,CAAC,IAAI,CAAC,EAAE,CAAC,EAAE,CAAC;gBACrC,OAAO;YACT,CAAC;YAED,IAAI,SAAS,KAAK,SAAS,EAAE,CAAC;gBAC5B,+CAA+C;gBAC/C,mBAAmB,CAAC,GAAG,CAAC,IAAI,CAAC,EAAE,EAAE,IAAI,CAAC,yBAAyB,EAAE,CAAC,CAAC;gBACnE,OAAO;YACT,CAAC;YAED,IAAI,SAAS,CAAC,IAAI,CAAC,EAAE,CAAC;gBACpB,yFAAyF;gBACzF,IAAI,CAAC,QAAQ,CACT,IAAI,CAAC,EAAE,CAAC,mBAAmB,CAAC,GAAG,CAAC,IAAI,CAAC,EAAE,EAAE,IAAI,CAAC,yBAAyB,EAAE,CAAC;gBAC1E,wFAAwF;gBACxF,IAAI,CAAC,EAAE,CAAC,IAAI,CAAC,YAAY,CAAC,MAAM,CAAC,MAAM,CAAC,EAAE,CAAC,CAAC,mBAAmB,CAAC,GAAG,CAAC,MAAM,CAAC,EAAE,CAAC,CAAC,CAClF,CAAC;YACJ,CAAC;QACH,CAAC,CAAC,CAAC;QAEH,mCAAmC;QACnC,QAAQ,CAAC,QAAQ,CAAC,YAAY,CAAC,EAAE;YAC/B,MAAM,UAAU,GAAG,mBAAmB,CAAC,GAAG,CAAC,YAAY,CAAC,EAAE,CAAC,CAAC;YAC5D,IAAI,CAAC,UAAU,EAAE,CAAC;gBAChB,OAAO;YACT,CAAC;YAED,KAAK,MAAM,UAAU,IAAI,YAAY,CAAC,YAAY,EAAE,CAAC;gBACnD,MAAM,gBAAgB,GAAG,mBAAmB,CAAC,GAAG,CAAC,UAAU,CAAC,EAAE,CAAC,CAAC;gBAChE,IAAI,CAAC,gBAAgB,EAAE,CAAC;oBACtB,MAAM,IAAI,IAAI,CAAC,YAAY,CAAC,+BAA+B,CAAC,CAAC;gBAC/D,CAAC;gBACD,UAAU,CAAC,aAAa,CAAC,gBAAgB,CAAC,CAAC;YAC7C,CAAC;QACH,CAAC,CAAC,CAAC;QAEH,MAAM,cAAc,GAAG,mBAAmB,CAAC,GAAG,CAAC,IAAI,CAAC,EAAE,CAAC,CAAC;QACxD,IAAI,CAAC,cAAc,EAAE,CAAC;YACpB,MAAM,IAAI,IAAI,CAAC,YAAY,CAAC,2BAA2B,CAAC,CAAC;QAC3D,CAAC;QACD,OAAO,cAAc,CAAC;IACxB,CAAC;IAED;;;;;;;OAOG;IACH,QAAQ,CACJ,QAAgE,EAChE,YAAgD;QAClD,KAAK,MAAM,EAAC,IAAI,EAAE,aAAa,EAAC,IAAI,IAAI,CAAC,iBAAiB,CAAC,YAAY,CAAC,EAAE,CAAC;YACzE,QAAQ,CAAC,IAAI,EAAE,aAAa,CAAC,CAAC;QAChC,CAAC;IACH,CAAC;IAED;;OAEG;IACH,mBAAmB;IACnB,CAAC,iBAAiB,CAAC,YAAqC;QAEtD,kBAAkB;QAClB,IAAI,CAAC,YAAY,EAAE,CAAC;YAClB,YAAY,GAAG,IAAI,CAAC,EAAE,CAAC,IAAI,CAAC,aAAa,EAAE,CAAC;QAC9C,CAAC;QAED,wFAAwF;QACxF,MAAM,KAAK,GAAa,CAAC,CAAC,IAAI,CAAC,CAAC,CAAC;QACjC,MAAM,OAAO,GAAG,IAAI,GAAG,CAAC,CAAC,IAAI,CAAC,EAAE,CAAC,CAAC,CAAC;QAEnC,OAAO,KAAK,CAAC,MAAM,EAAE,CAAC;YACpB,yEAAyE;YACzE,MAAM,aAAa,GAAW,KAAK,CAAC,KAAK,EAAE,CAAC;YAC5C,MAAM,IAAI,GAAG,aAAa,CAAC,CAAC,CAAC,CAAC;YAC9B,MAAM,EAAC,IAAI,EAAE,aAAa,EAAC,CAAC;YAE5B,KAAK,MAAM,QAAQ,IAAI,YAAY,CAAC,IAAI,CAAC,EAAE,CAAC;gBAC1C,IAAI,OAAO,CAAC,GAAG,CAAC,QAAQ,CAAC,EAAE,CAAC,EAAE,CAAC;oBAC7B,SAAS;gBACX,CAAC;gBACD,OAAO,CAAC,GAAG,CAAC,QAAQ,CAAC,EAAE,CAAC,CAAC;gBAEzB,KAAK,CAAC,IAAI,CAAC,CAAC,QAAQ,EAAE,GAAG,aAAa,CAAC,CAAC,CAAC;YAC3C,CAAC;QACH,CAAC;IACH,CAAC;IAED;;OAEG;IACH,MAAM,CAAC,QAAQ,CAAC,IAAU,EAAE,YAAgD,MAAM;QAChF,iFAAiF;QACjF,IAAI,SAAS,KAAK,MAAM,EAAE,CAAC;YACzB,OAAO,QAAQ,CAAC,QAAQ,CAAC,IAAI,EAAE,YAAY,CAAC,IAAI,QAAQ,CAAC,QAAQ,CAAC,IAAI,EAAE,cAAc,CAAC,CAAC;QAC1F,CAAC;QAED,MAAM,OAAO,GAAG,IAAI,GAAG,EAAE,CAAC;QAC1B,MAAM,WAAW,GAAe,EAAE,CAAC;QACnC,MAAM,OAAO,GAAG,CAAC,IAAI,CAAC,CAAC;QACvB,MAAM,UAAU,GAAG,IAAI,GAAG,CAAC,CAAC,CAAC,IAAI,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC;QAExC,uDAAuD;QACvD,OAAO,OAAO,CAAC,MAAM,EAAE,CAAC;YACtB,6DAA6D;YAC7D,2EAA2E;YAC3E,MAAM,WAAW,GAAa,OAAO,CAAC,GAAG,EAAE,CAAC;YAE5C,iFAAiF;YACjF,IAAI,WAAW,CAAC,QAAQ,CAAC,WAAW,CAAC,EAAE,CAAC;gBACtC,OAAO,IAAI,CAAC;YACd,CAAC;YACD,2DAA2D;YAC3D,IAAI,OAAO,CAAC,GAAG,CAAC,WAAW,CAAC,EAAE,CAAC;gBAC7B,SAAS;YACX,CAAC;YAED,2FAA2F;YAC3F,mBAAmB;YACnB,OAAO,WAAW,CAAC,MAAM,GAAG,UAAU,CAAC,GAAG,CAAC,WAAW,CAAC,EAAE,CAAC;gBACxD,WAAW,CAAC,GAAG,EAAE,CAAC;YACpB,CAAC;YAED,gFAAgF;YAChF,OAAO,CAAC,GAAG,CAAC,WAAW,CAAC,CAAC;YACzB,WAAW,CAAC,IAAI,CAAC,WAAW,CAAC,CAAC;YAE9B,iDAAiD;YACjD,MAAM,cAAc,GAAG,SAAS,KAAK,YAAY,CAAC,CAAC,CAAC,WAAW,CAAC,UAAU,CAAC,CAAC,CAAC,WAAW,CAAC,YAAY,CAAC;YACtG,KAAK,MAAM,QAAQ,IAAI,cAAc,EAAE,CAAC;gBACtC,IAAI,OAAO,CAAC,QAAQ,CAAC,QAAQ,CAAC,EAAE,CAAC;oBAC/B,SAAS;gBACX,CAAC;gBACD,OAAO,CAAC,IAAI,CAAC,QAAQ,CAAC,CAAC;gBACvB,UAAU,CAAC,GAAG,CAAC,QAAQ,EAAE,WAAW,CAAC,MAAM,CAAC,CAAC;YAC/C,CAAC;QACH,CAAC;QAED,OAAO,KAAK,CAAC;IACf,CAAC;IAED,WAAW,CAAC,IAAU;QACpB,OAAO,IAAI,CAAC,SAAS,IAAI,IAAI,CAAC,SAAS,CAAC;IAC1C,CAAC;;AAGH,OAAO,EAAC,QAAQ,EAAC,CAAC","sourcesContent":["// Copyright 2024 The Chromium Authors. All rights reserved.\n// Use of this source code is governed by a BSD-style license that can be\n// found in the LICENSE file.\n\nimport * as Core from '../core/core.js';\nimport type * as Lantern from '../types/types.js';\n\nimport type {CPUNode} from './CPUNode.js';\nimport type {NetworkNode} from './NetworkNode.js';\n\n/**\n * A union of all types derived from BaseNode, allowing type check discrimination\n * based on `node.type`. If a new node type is created, it should be added here.\n */\nexport type Node = CPUNode|NetworkNode;\n\n/**\n * @fileoverview This class encapsulates logic for handling resources and tasks used to model the\n * execution dependency graph of the page. A node has a unique identifier and can depend on other\n * nodes/be depended on. The construction of the graph maintains some important invariants that are\n * inherent to the model:\n *\n * 1. The graph is a DAG, there are no cycles.\n * 2. There is always a root node upon which all other nodes eventually depend.\n *\n * This allows particular optimizations in this class so that we do no need to check for cycles as\n * these methods are called and we can always start traversal at the root node.\n */\n\nclass BaseNode {\n static types = {\n NETWORK: 'network',\n CPU: 'cpu',\n } as const;\n\n _id: string;\n _isMainDocument: boolean;\n dependents: Node[];\n dependencies: Node[];\n\n constructor(id: string) {\n this._id = id;\n this._isMainDocument = false;\n this.dependents = [];\n this.dependencies = [];\n }\n\n get id(): string {\n return this._id;\n }\n\n get type(): 'network'|'cpu' {\n throw new Core.LanternError('Unimplemented');\n }\n\n /**\n * In microseconds\n */\n get startTime(): number {\n throw new Core.LanternError('Unimplemented');\n }\n\n /**\n * In microseconds\n */\n get endTime(): number {\n throw new Core.LanternError('Unimplemented');\n }\n\n setIsMainDocument(value: boolean): void {\n this._isMainDocument = value;\n }\n\n isMainDocument(): boolean {\n return this._isMainDocument;\n }\n\n getDependents(): Node[] {\n return this.dependents.slice();\n }\n\n getNumberOfDependents(): number {\n return this.dependents.length;\n }\n\n getDependencies(): Node[] {\n return this.dependencies.slice();\n }\n\n getNumberOfDependencies(): number {\n return this.dependencies.length;\n }\n\n getRootNode(): Node {\n let rootNode = this as BaseNode as Node;\n while (rootNode.dependencies.length) {\n rootNode = rootNode.dependencies[0];\n }\n\n return rootNode;\n }\n\n addDependent(node: Node): void {\n node.addDependency(this as BaseNode as Node);\n }\n\n addDependency(node: Node): void {\n // @ts-expect-error - in checkJs, ts doesn't know that CPUNode and NetworkNode *are* BaseNodes.\n if (node === this) {\n throw new Core.LanternError('Cannot add dependency on itself');\n }\n\n if (this.dependencies.includes(node)) {\n return;\n }\n\n node.dependents.push(this as BaseNode as Node);\n this.dependencies.push(node);\n }\n\n removeDependent(node: Node): void {\n node.removeDependency(this as BaseNode as Node);\n }\n\n removeDependency(node: Node): void {\n if (!this.dependencies.includes(node)) {\n return;\n }\n\n const thisIndex = node.dependents.indexOf(this as BaseNode as Node);\n node.dependents.splice(thisIndex, 1);\n this.dependencies.splice(this.dependencies.indexOf(node), 1);\n }\n\n // Unused in devtools, but used in LH.\n removeAllDependencies(): void {\n for (const node of this.dependencies.slice()) {\n this.removeDependency(node);\n }\n }\n\n /**\n * Computes whether the given node is anywhere in the dependency graph of this node.\n * While this method can prevent cycles, it walks the graph and should be used sparingly.\n * Nodes are always considered dependent on themselves for the purposes of cycle detection.\n */\n isDependentOn(node: BaseNode): boolean {\n let isDependentOnNode = false;\n this.traverse(\n currentNode => {\n if (isDependentOnNode) {\n return;\n }\n isDependentOnNode = currentNode === node;\n },\n currentNode => {\n // If we've already found the dependency, don't traverse further.\n if (isDependentOnNode) {\n return [];\n }\n // Otherwise, traverse the dependencies.\n return currentNode.getDependencies();\n });\n\n return isDependentOnNode;\n }\n\n /**\n * Clones the node's information without adding any dependencies/dependents.\n */\n cloneWithoutRelationships(): Node {\n const node = new BaseNode(this.id) as Node;\n node.setIsMainDocument(this._isMainDocument);\n return node;\n }\n\n /**\n * Clones the entire graph connected to this node filtered by the optional predicate. If a node is\n * included by the predicate, all nodes along the paths between the node and the root will be included. If the\n * node this was called on is not included in the resulting filtered graph, the method will throw.\n *\n * This does not clone NetworkNode's `record` or `rawRecord` fields. It may be reasonable to clone the former,\n * to assist in graph construction, but the latter should never be cloned as one constraint of Lantern is that\n * the underlying data records are accessible for plain object reference equality checks.\n */\n cloneWithRelationships(predicate?: (arg0: Node) => boolean): Node {\n const rootNode = this.getRootNode();\n\n const idsToIncludedClones = new Map();\n\n // Walk down dependents.\n rootNode.traverse(node => {\n if (idsToIncludedClones.has(node.id)) {\n return;\n }\n\n if (predicate === undefined) {\n // No condition for entry, so clone every node.\n idsToIncludedClones.set(node.id, node.cloneWithoutRelationships());\n return;\n }\n\n if (predicate(node)) {\n // Node included, so walk back up dependencies, cloning nodes from here back to the root.\n node.traverse(\n node => idsToIncludedClones.set(node.id, node.cloneWithoutRelationships()),\n // Dependencies already cloned have already cloned ancestors, so no need to visit again.\n node => node.dependencies.filter(parent => !idsToIncludedClones.has(parent.id)),\n );\n }\n });\n\n // Copy dependencies between nodes.\n rootNode.traverse(originalNode => {\n const clonedNode = idsToIncludedClones.get(originalNode.id);\n if (!clonedNode) {\n return;\n }\n\n for (const dependency of originalNode.dependencies) {\n const clonedDependency = idsToIncludedClones.get(dependency.id);\n if (!clonedDependency) {\n throw new Core.LanternError('Dependency somehow not cloned');\n }\n clonedNode.addDependency(clonedDependency);\n }\n });\n\n const clonedThisNode = idsToIncludedClones.get(this.id);\n if (!clonedThisNode) {\n throw new Core.LanternError('Cloned graph missing node');\n }\n return clonedThisNode;\n }\n\n /**\n * Traverses all connected nodes in BFS order, calling `callback` exactly once\n * on each. `traversalPath` is the shortest (though not necessarily unique)\n * path from `node` to the root of the iteration.\n *\n * The `getNextNodes` function takes a visited node and returns which nodes to\n * visit next. It defaults to returning the node's dependents.\n */\n traverse(\n callback: (node: Node, traversalPath: Array>) => void,\n getNextNodes?: (arg0: Node) => Array>): void {\n for (const {node, traversalPath} of this.traverseGenerator(getNextNodes)) {\n callback(node, traversalPath);\n }\n }\n\n /**\n * @see BaseNode.traverse\n */\n // clang-format off\n *traverseGenerator(getNextNodes?: (arg0: Node) => Node[]):\n Generator<{node: Node, traversalPath: Node[]}, void, unknown> {\n // clang-format on\n if (!getNextNodes) {\n getNextNodes = node => node.getDependents();\n }\n\n // @ts-expect-error - only traverses graphs of Node, so force tsc to treat `this` as one\n const queue: Node[][] = [[this]];\n const visited = new Set([this.id]);\n\n while (queue.length) {\n // @ts-expect-error - queue has length so it's guaranteed to have an item\n const traversalPath: Node[] = queue.shift();\n const node = traversalPath[0];\n yield {node, traversalPath};\n\n for (const nextNode of getNextNodes(node)) {\n if (visited.has(nextNode.id)) {\n continue;\n }\n visited.add(nextNode.id);\n\n queue.push([nextNode, ...traversalPath]);\n }\n }\n }\n\n /**\n * Returns whether the given node has a cycle in its dependent graph by performing a DFS.\n */\n static hasCycle(node: Node, direction: 'dependents'|'dependencies'|'both' = 'both'): boolean {\n // Checking 'both' is the default entrypoint to recursively check both directions\n if (direction === 'both') {\n return BaseNode.hasCycle(node, 'dependents') || BaseNode.hasCycle(node, 'dependencies');\n }\n\n const visited = new Set();\n const currentPath: BaseNode[] = [];\n const toVisit = [node];\n const depthAdded = new Map([[node, 0]]);\n\n // Keep going while we have nodes to visit in the stack\n while (toVisit.length) {\n // Get the last node in the stack (DFS uses stack, not queue)\n // @ts-expect-error - toVisit has length so it's guaranteed to have an item\n const currentNode: BaseNode = toVisit.pop();\n\n // We've hit a cycle if the node we're visiting is in our current dependency path\n if (currentPath.includes(currentNode)) {\n return true;\n }\n // If we've already visited the node, no need to revisit it\n if (visited.has(currentNode)) {\n continue;\n }\n\n // Since we're visiting this node, clear out any nodes in our path that we had to backtrack\n // @ts-expect-error\n while (currentPath.length > depthAdded.get(currentNode)) {\n currentPath.pop();\n }\n\n // Update our data structures to reflect that we're adding this node to our path\n visited.add(currentNode);\n currentPath.push(currentNode);\n\n // Add all of its dependents to our toVisit stack\n const nodesToExplore = direction === 'dependents' ? currentNode.dependents : currentNode.dependencies;\n for (const nextNode of nodesToExplore) {\n if (toVisit.includes(nextNode)) {\n continue;\n }\n toVisit.push(nextNode);\n depthAdded.set(nextNode, currentPath.length);\n }\n }\n\n return false;\n }\n\n canDependOn(node: Node): boolean {\n return node.startTime <= this.startTime;\n }\n}\n\nexport {BaseNode};\n"]}