LCOV - code coverage report
Current view: top level - src/utils - graphTraversalUtil.ts Coverage Total Hit
Test: ComfyUI E2E Coverage Lines: 75.6 % 275 208
Test Date: 2026-11-17 04:17:53

            Line data    Source code
       1              : import type {
       2              :   LGraph,
       3              :   LGraphNode,
       4              :   Subgraph,
       5              :   SubgraphNode
       6              : } from '@comfyorg/graph-model/entityRegistry'
       7              : 
       8              : import { SUBGRAPH_INPUT_ID } from '@/lib/litegraph/src/constants'
       9              : import { inputLink } from '@/lib/litegraph/src/node/slotLinks'
      10              : import { LGraphEventMode } from '@comfyorg/graph-model/globalEnums'
      11              : import type {
      12              :   NodeExecutionId,
      13              :   NodeLocatorId
      14              : } from '@comfyorg/graph-model/nodeIdentification'
      15              : import {
      16              :   createLeafNodeExecutionId,
      17              :   createNodeExecutionId,
      18              :   createNodeLocatorId,
      19              :   getParentExecutionIds,
      20              :   parseNodeLocatorId
      21              : } from '@comfyorg/graph-model/nodeIdentification'
      22              : import { parseNodeId, toNodeId } from '@comfyorg/graph-model/nodeId'
      23              : import type { NodeId } from '@comfyorg/graph-model/nodeId'
      24              : import type { NodeState } from '@comfyorg/graph-model/nodeState'
      25              : import type { UUID } from '@/utils/uuid'
      26              : import type { PromotedWidgetExecutionSource } from '@/core/graph/subgraph/promotedWidgetTypes'
      27              : 
      28              : import { isSubgraphIoNode } from './typeGuardUtil'
      29              : 
      30              : type RuntimeGraphNode = Omit<LGraphNode, 'isSubgraphNode'> &
      31              :   Partial<Pick<LGraphNode, 'isSubgraphNode'>>
      32              : 
      33       240944 : function isSubgraphNode(node: RuntimeGraphNode): node is SubgraphNode {
      34       240944 :   return node.isSubgraphNode?.call(node) ?? false
      35              : }
      36              : 
      37              : /**
      38              :  * The containing subgraph's id, or `null` when the node belongs to the root
      39              :  * graph. Locator/execution ids key root nodes by bare id, so a root-owned node —
      40              :  * or one whose root graph is not yet known — must map to `null`.
      41              :  */
      42       140685 : export function subgraphIdFromState(
      43              :   state: Pick<NodeState, 'graphId'>,
      44              :   rootGraphId: UUID | undefined
      45              : ): UUID | null {
      46       140685 :   return rootGraphId && state.graphId !== rootGraphId ? state.graphId : null
      47              : }
      48              : 
      49              : /**
      50              :  * The locator id for a node described by its shell state.
      51              :  */
      52        75721 : export function locatorIdFromState(
      53              :   state: Pick<NodeState, 'id' | 'graphId'>,
      54              :   rootGraphId: UUID | undefined
      55              : ): NodeLocatorId | null {
      56        75721 :   return createNodeLocatorId(subgraphIdFromState(state, rootGraphId), state.id)
      57              : }
      58              : 
      59         7130 : function parseNodeIdPath(path: string[]): NodeId[] | null {
      60         7130 :   const nodeIds = path.map(parseNodeId)
      61         7130 :   return nodeIds.every((nodeId): nodeId is NodeId => nodeId !== null)
      62              :     ? nodeIds
      63              :     : null
      64              : }
      65              : 
      66         7130 : function createExecutionIdFromPath(
      67              :   parentPath: string,
      68              :   nodeId: NodeId
      69              : ): NodeExecutionId | null {
      70         7130 :   const parentNodeIds = parseNodeIdPath(parentPath.split(':'))
      71         7130 :   if (!parentNodeIds) return null
      72              : 
      73         7130 :   return createNodeExecutionId([...parentNodeIds, nodeId])
      74              : }
      75              : 
      76              : /**
      77              :  * Parses an execution ID into its component parts.
      78              :  *
      79              :  * @param executionId - The execution ID (e.g., "123:456:789" or "789")
      80              :  * @returns Array of node IDs in the path, or null if invalid
      81              :  */
      82            0 : export function parseExecutionId(executionId: string): string[] | null {
      83            0 :   if (!executionId || typeof executionId !== 'string') return null
      84            0 :   return executionId.split(':').filter((part) => part.length > 0)
      85              : }
      86              : 
      87              : /**
      88              :  * Extracts the local node ID from an execution ID.
      89              :  *
      90              :  * @param executionId - The execution ID (e.g., "123:456:789" or "789")
      91              :  * @returns The local node ID or null if invalid
      92              :  */
      93              : export function getLocalNodeIdFromExecutionId(
      94              :   executionId: string
      95              : ): string | null {
      96              :   const parts = parseExecutionId(executionId)
      97              :   return parts ? parts[parts.length - 1] : null
      98              : }
      99              : 
     100              : /**
     101              :  * Extracts the subgraph path from an execution ID.
     102              :  *
     103              :  * @param executionId - The execution ID (e.g., "123:456:789" or "789")
     104              :  * @returns Array of subgraph node IDs (excluding the final node ID), or empty array
     105              :  */
     106              : export function getSubgraphPathFromExecutionId(executionId: string): string[] {
     107              :   const parts = parseExecutionId(executionId)
     108              :   return parts ? parts.slice(0, -1) : []
     109              : }
     110              : 
     111              : /**
     112              :  * Visits each node in a graph (non-recursive, single level).
     113              :  *
     114              :  * @param graph - The graph to visit nodes from
     115              :  * @param visitor - Function called for each node
     116              :  */
     117        54409 : export function visitGraphNodes(
     118              :   graph: LGraph | Subgraph,
     119              :   visitor: (node: LGraphNode) => void
     120              : ): void {
     121        54409 :   for (const node of graph.nodes) {
     122       234276 :     visitor(node)
     123              :   }
     124              : }
     125              : 
     126              : /**
     127              :  * Traverses a path of subgraphs to reach a target graph.
     128              :  *
     129              :  * @param startGraph - The graph to start from
     130              :  * @param path - Array of subgraph node IDs to traverse
     131              :  * @returns The target graph or null if path is invalid
     132              :  */
     133            0 : export function traverseSubgraphPath(
     134              :   startGraph: LGraph | Subgraph,
     135              :   path: string[]
     136              : ): LGraph | Subgraph | null {
     137            0 :   let currentGraph: LGraph | Subgraph = startGraph
     138              : 
     139            0 :   for (const nodeId of path) {
     140            0 :     const localNodeId = parseNodeId(nodeId)
     141            0 :     if (!localNodeId) return null
     142              : 
     143            0 :     const node = currentGraph.getNodeById(localNodeId)
     144            0 :     if (!node || !isSubgraphNode(node)) return null
     145            0 :     currentGraph = node.subgraph
     146              :   }
     147              : 
     148            0 :   return currentGraph
     149              : }
     150              : 
     151              : /**
     152              :  * Traverses all nodes in a graph hierarchy (including subgraphs) and invokes
     153              :  * a callback on each node that has the specified property.
     154              :  *
     155              :  * @param graph - The root graph to start traversal from
     156              :  * @param callbackProperty - The name of the callback property to invoke on each node
     157              :  */
     158         7887 : export function triggerCallbackOnAllNodes(
     159              :   graph: LGraph | Subgraph,
     160              :   callbackProperty: keyof LGraphNode
     161              : ): void {
     162         7887 :   forEachNode(graph, (node) => {
     163        44414 :     const callback = node[callbackProperty]
     164        44414 :     if (typeof callback === 'function') {
     165        21489 :       callback.call(node)
     166              :     }
     167              :   })
     168              : }
     169              : 
     170              : /**
     171              :  * Maps a function over all nodes in a graph hierarchy (including subgraphs).
     172              :  * This is a pure functional traversal that doesn't mutate the graph.
     173              :  *
     174              :  * @param graph - The root graph to traverse
     175              :  * @param mapFn - Function to apply to each node
     176              :  * @returns Array of mapped results (excluding undefined values)
     177              :  */
     178        17675 : export function mapAllNodes<T>(
     179              :   graph: LGraph | Subgraph,
     180              :   mapFn: (node: LGraphNode) => T | undefined
     181              : ): T[] {
     182        17675 :   const results: T[] = []
     183              : 
     184        17675 :   visitGraphNodes(graph, (node) => {
     185              :     // Recursively map over subgraphs first
     186        69774 :     if (isSubgraphNode(node)) {
     187         1662 :       results.push(...mapAllNodes(node.subgraph, mapFn))
     188              :     }
     189              : 
     190              :     // Apply map function to current node
     191        69774 :     const result = mapFn(node)
     192        69774 :     if (result !== undefined) {
     193        47871 :       results.push(result)
     194              :     }
     195              :   })
     196              : 
     197        17675 :   return results
     198              : }
     199              : 
     200              : /**
     201              :  * Maps a function over each unique node in a graph hierarchy. Subgraph
     202              :  * instances share their definition's nodes, so unlike {@link mapAllNodes}
     203              :  * each subgraph definition is visited once and cyclic subgraphs terminate.
     204              :  *
     205              :  * @param graph - The root graph to traverse
     206              :  * @param mapFn - Function to apply to each node
     207              :  * @returns Array of mapped results (excluding undefined values)
     208              :  */
     209          524 : export function mapUniqueNodes<T>(
     210              :   graph: LGraph | Subgraph,
     211              :   mapFn: (node: LGraphNode) => T | undefined
     212              : ): T[] {
     213          524 :   return mapUnvisitedNodes(graph, mapFn, new Set([graph.id]))
     214              : }
     215              : 
     216          627 : function mapUnvisitedNodes<T>(
     217              :   graph: LGraph | Subgraph,
     218              :   mapFn: (node: LGraphNode) => T | undefined,
     219              :   visited: Set<string>
     220              : ): T[] {
     221          627 :   const results: T[] = []
     222              : 
     223          627 :   visitGraphNodes(graph, (node) => {
     224         1558 :     if (isSubgraphNode(node)) {
     225          103 :       const subgraphId = node.subgraph.id
     226          103 :       if (!visited.has(subgraphId)) {
     227          103 :         visited.add(subgraphId)
     228          103 :         results.push(...mapUnvisitedNodes(node.subgraph, mapFn, visited))
     229              :       }
     230              :     }
     231              : 
     232         1558 :     const result = mapFn(node)
     233         1558 :     if (result !== undefined) {
     234            7 :       results.push(result)
     235              :     }
     236              :   })
     237              : 
     238          627 :   return results
     239              : }
     240              : 
     241              : /**
     242              :  * Executes a side-effect function on all nodes in a graph hierarchy.
     243              :  * This is for operations that modify nodes or perform side effects.
     244              :  *
     245              :  * @param graph - The root graph to traverse
     246              :  * @param fn - Function to execute on each node
     247              :  */
     248        36087 : export function forEachNode(
     249              :   graph: LGraph | Subgraph,
     250              :   fn: (node: LGraphNode) => void
     251              : ): void {
     252        36087 :   visitGraphNodes(graph, (node) => {
     253              :     // Recursively process subgraphs first
     254       162908 :     if (isSubgraphNode(node)) {
     255         2827 :       forEachNode(node.subgraph, fn)
     256              :     }
     257              : 
     258              :     // Execute function on current node
     259       162908 :     fn(node)
     260              :   })
     261              : }
     262              : 
     263              : /**
     264              :  * Collects all nodes in a graph hierarchy (including subgraphs) into a flat array.
     265              :  *
     266              :  * @param graph - The root graph to collect nodes from
     267              :  * @param filter - Optional filter function to include only specific nodes
     268              :  * @returns Array of all nodes in the graph hierarchy
     269              :  */
     270        15909 : export function collectAllNodes(
     271              :   graph: LGraph | Subgraph,
     272              :   filter?: (node: LGraphNode) => boolean
     273              : ): LGraphNode[] {
     274        15909 :   return mapAllNodes(graph, (node) => {
     275        69481 :     if (!filter || filter(node)) {
     276        47578 :       return node
     277              :     }
     278              :     return undefined
     279              :   })
     280              : }
     281              : 
     282              : /**
     283              :  * Finds a node by ID anywhere in the graph hierarchy.
     284              :  *
     285              :  * @param graph - The root graph to search
     286              :  * @param nodeId - The ID of the node to find
     287              :  * @returns The node if found, null otherwise
     288              :  */
     289            0 : export function findNodeInHierarchy(
     290              :   graph: LGraph | Subgraph,
     291              :   nodeId: string | number
     292              : ): LGraphNode | null {
     293            0 :   const localNodeId = parseNodeId(nodeId)
     294            0 :   if (!localNodeId) return null
     295              : 
     296              :   // Check current graph
     297            0 :   const node = graph.getNodeById(localNodeId)
     298            0 :   if (node) return node
     299              : 
     300              :   // Search in subgraphs
     301            0 :   for (const node of graph.nodes) {
     302            0 :     if (isSubgraphNode(node)) {
     303            0 :       const found = findNodeInHierarchy(node.subgraph, nodeId)
     304            0 :       if (found) return found
     305              :     }
     306              :   }
     307              : 
     308            0 :   return null
     309              : }
     310              : 
     311              : /**
     312              :  * Find a subgraph by its UUID anywhere in the graph hierarchy.
     313              :  *
     314              :  * @param graph - The root graph to search
     315              :  * @param targetUuid - The UUID of the subgraph to find
     316              :  * @returns The subgraph if found, null otherwise
     317              :  */
     318          533 : export function findSubgraphByUuid(
     319              :   graph: LGraph | Subgraph,
     320              :   targetUuid: string
     321              : ): Subgraph | null {
     322              :   // Fast O(1) lookup via the root graph's centralized subgraph registry.
     323          533 :   if ('subgraphs' in graph && graph.subgraphs instanceof Map) {
     324          533 :     return graph.subgraphs.get(targetUuid) ?? null
     325              :   }
     326              : 
     327              :   // Fallback: recursive traversal for non-root graphs without the registry.
     328            0 :   for (const node of graph.nodes) {
     329            0 :     if (isSubgraphNode(node)) {
     330            0 :       if (node.subgraph.id === targetUuid) {
     331            0 :         return node.subgraph
     332              :       }
     333            0 :       const found = findSubgraphByUuid(node.subgraph, targetUuid)
     334            0 :       if (found) return found
     335              :     }
     336              :   }
     337            0 :   return null
     338              : }
     339              : 
     340              : /**
     341              :  * Iteratively finds the path of subgraph IDs to a target subgraph.
     342              :  * @param rootGraph The graph to start searching from.
     343              :  * @param targetId The ID of the subgraph to find.
     344              :  * @returns An array of subgraph IDs representing the path, or `null` if not found.
     345              :  */
     346          142 : export function findSubgraphPathById(
     347              :   rootGraph: LGraph,
     348              :   targetId: string
     349              : ): string[] | null {
     350          142 :   const stack: { graph: LGraph | Subgraph; path: string[] }[] = [
     351              :     { graph: rootGraph, path: [] }
     352              :   ]
     353              : 
     354          142 :   while (stack.length > 0) {
     355          151 :     const { graph, path } = stack.pop()!
     356              : 
     357              :     // Check if graph exists and has _nodes property
     358          151 :     for (const node of graph._nodes) {
     359          272 :       if (isSubgraphNode(node)) {
     360          146 :         const newPath = [...path, node.subgraph.id]
     361          146 :         if (node.subgraph.id === targetId) {
     362          136 :           return newPath
     363              :         }
     364           10 :         stack.push({ graph: node.subgraph, path: newPath })
     365              :       }
     366              :     }
     367              :   }
     368              : 
     369            6 :   return null
     370              : }
     371              : 
     372              : /**
     373              :  * Iteratively finds the path of subgraph NODE ids (not subgraph UUIDs) to a
     374              :  * target subgraph - the address form node-scoped consumers need (e.g. the
     375              :  * agent write leg's interior `set_widget`, whose wire `path` is a resolved
     376              :  * node-id chain).
     377              :  * @param rootGraph The graph to start searching from.
     378              :  * @param targetUuid The UUID of the subgraph to find.
     379              :  * @returns Subgraph-node ids from the root down to the node whose definition
     380              :  * is the target, or `null` if not found.
     381              :  */
     382            0 : export function findSubgraphNodePathById(
     383              :   rootGraph: LGraph,
     384              :   targetUuid: string
     385              : ): string[] | null {
     386            0 :   const stack: { graph: LGraph | Subgraph; path: string[] }[] = [
     387              :     { graph: rootGraph, path: [] }
     388              :   ]
     389              : 
     390            0 :   while (stack.length > 0) {
     391            0 :     const { graph, path } = stack.pop()!
     392            0 :     for (const node of graph._nodes) {
     393            0 :       if (isSubgraphNode(node)) {
     394            0 :         const newPath = [...path, String(node.id)]
     395            0 :         if (node.subgraph.id === targetUuid) {
     396            0 :           return newPath
     397              :         }
     398            0 :         stack.push({ graph: node.subgraph, path: newPath })
     399              :       }
     400              :     }
     401              :   }
     402              : 
     403            0 :   return null
     404              : }
     405              : 
     406              : /**
     407              :  * Gets the root parent node associated with a hierarchical execution ID.
     408              :  * Both Group Nodes and Subgraph Nodes use hierarchical IDs (e.g. "rootId:childId:...").
     409              :  * The root parent is always located in the rootGraph.
     410              :  *
     411              :  * @param rootGraph - The root graph to search from
     412              :  * @param executionId - The execution ID (e.g., "123:456")
     413              :  * @returns The root parent node if found, null otherwise
     414              :  */
     415            0 : export function getRootParentNode(
     416              :   rootGraph: LGraph,
     417              :   executionId: string
     418              : ): LGraphNode | null {
     419            0 :   const parts = parseExecutionId(executionId)
     420            0 :   if (!parts || parts.length < 2) return null
     421              : 
     422            0 :   const parentId = parts[0]
     423            0 :   const localParentId = parseNodeId(parentId)
     424            0 :   if (!localParentId) return null
     425              : 
     426            0 :   return rootGraph.getNodeById(localParentId) || null
     427              : }
     428              : 
     429              : /**
     430              :  * Get a node by its execution ID from anywhere in the graph hierarchy.
     431              :  * Execution IDs use hierarchical format like "123:456:789" for nested nodes.
     432              :  *
     433              :  * @param rootGraph - The root graph to search from
     434              :  * @param executionId - The execution ID (e.g., "123:456:789" or "789")
     435              :  * @returns The node if found, null otherwise
     436              :  */
     437        28898 : export function getNodeByExecutionId(
     438              :   rootGraph: LGraph,
     439              :   executionId: string
     440              : ): LGraphNode | null {
     441        28898 :   return resolveExecutionNode(rootGraph, executionId)?.node ?? null
     442              : }
     443              : 
     444              : interface ResolvedExecutionNode {
     445              :   graph: LGraph | Subgraph
     446              :   node: LGraphNode
     447              : }
     448              : 
     449        36293 : function resolveExecutionNode(
     450              :   graph: LGraph | Subgraph,
     451              :   executionId: string
     452              : ): ResolvedExecutionNode | null {
     453        36293 :   for (
     454              :     let end = executionId.indexOf(':');
     455              :     end !== -1;
     456              :     end = executionId.indexOf(':', end + 1)
     457              :   ) {
     458         6499 :     const host = graph.getNodeById(toNodeId(executionId.slice(0, end)))
     459         6499 :     if (!host || !isSubgraphNode(host)) continue
     460              : 
     461         6430 :     const nested = resolveExecutionNode(
     462              :       host.subgraph,
     463              :       executionId.slice(end + 1)
     464              :     )
     465         6430 :     if (nested) return nested
     466              :   }
     467              : 
     468        36293 :   const node = executionId ? graph.getNodeById(toNodeId(executionId)) : null
     469        36293 :   return node ? { graph, node } : null
     470              : }
     471              : 
     472              : /**
     473              :  * Returns the execution ID for a node relative to the root graph.
     474              :  *
     475              :  * Root-level nodes return their ID directly (e.g. "42").
     476              :  * Nodes inside subgraphs return a colon-separated chain (e.g. "65:70:63").
     477              :  *
     478              :  * @param rootGraph - The root graph to resolve from
     479              :  * @param node - The node whose execution ID to compute
     480              :  * @returns The execution ID string, or null if the node has no graph
     481              :  */
     482       185730 : export function getExecutionIdByNode(
     483              :   rootGraph: LGraph,
     484              :   node: LGraphNode
     485              : ): NodeExecutionId | null {
     486       185730 :   if (!node.graph) return null
     487              : 
     488       185730 :   if (node.graph === rootGraph || node.graph.isRootGraph) {
     489       177863 :     return createNodeExecutionId([node.id])
     490              :   }
     491              : 
     492         7098 :   const parentPath = findPartialExecutionPathToGraph(node.graph, rootGraph)
     493        43001 :   if (parentPath === undefined) return null
     494              : 
     495         7098 :   return createExecutionIdFromPath(parentPath, node.id)
     496              : }
     497              : 
     498              : /**
     499              :  * True when every ancestor container in the execution path is active
     500              :  * (not muted, not bypassed). Self is not checked — caller is expected to
     501              :  * have already verified the target node's own mode.
     502              :  *
     503              :  * For root-level nodes (single-segment execution ID) there are no
     504              :  * ancestors and the result is always true.
     505              :  *
     506              :  * Use after an initial full-graph scan to suppress missing-asset entries
     507              :  * whose enclosing subgraph is muted/bypassed. At scan time only each
     508              :  * node's own mode is checked; ancestor context is applied here so the
     509              :  * effect cascades to interior nodes without requiring every scanner to
     510              :  * carry the ancestor flag.
     511              :  */
     512        16103 : export function isAncestorPathActive(
     513              :   rootGraph: LGraph | null | undefined,
     514              :   executionId: string
     515              : ): boolean {
     516        16103 :   if (!rootGraph) return true
     517        16103 :   for (const ancestorId of getParentExecutionIds(executionId)) {
     518         4090 :     const ancestor = getNodeByExecutionId(rootGraph, ancestorId)
     519         4090 :     if (!ancestor) continue
     520         4090 :     if (
     521              :       ancestor.mode === LGraphEventMode.NEVER ||
     522              :       ancestor.mode === LGraphEventMode.BYPASS
     523              :     ) {
     524            2 :       return false
     525              :     }
     526              :   }
     527        16101 :   return true
     528              : }
     529              : 
     530        16012 : export function isExecutionPathActive(
     531              :   rootGraph: LGraph | null | undefined,
     532              :   executionId: string
     533              : ): boolean {
     534        16012 :   if (!rootGraph) return true
     535        16012 :   const node = getNodeByExecutionId(rootGraph, executionId)
     536        16012 :   if (!node) return false
     537        16012 :   if (
     538              :     node.mode === LGraphEventMode.NEVER ||
     539              :     node.mode === LGraphEventMode.BYPASS
     540              :   ) {
     541            4 :     return false
     542              :   }
     543        16008 :   return isAncestorPathActive(rootGraph, executionId)
     544              : }
     545              : 
     546        11151 : function getCandidateActivityExecutionId(candidate: {
     547              :   nodeId?: string | number | null | undefined
     548              :   sourceExecutionId?: string | number | null | undefined
     549              : }): string | null {
     550        11151 :   const executionId = candidate.sourceExecutionId ?? candidate.nodeId
     551        11151 :   return executionId == null ? null : String(executionId)
     552              : }
     553              : 
     554        11280 : export function isCandidateScopeActive(
     555              :   rootGraph: LGraph | null | undefined,
     556              :   candidate: {
     557              :     nodeId?: string | number | null | undefined
     558              :     sourceExecutionId?: string | number | null | undefined
     559              :     promotedSources?: readonly PromotedWidgetExecutionSource[]
     560              :   }
     561              : ): boolean {
     562        11280 :   if (candidate.promotedSources) {
     563          129 :     return candidate.promotedSources.some((source) =>
     564              :       isExecutionPathActive(rootGraph, source.executionId)
     565              :     )
     566              :   }
     567        11151 :   const executionId = getCandidateActivityExecutionId(candidate)
     568        11280 :   return executionId == null || isExecutionPathActive(rootGraph, executionId)
     569              : }
     570              : 
     571              : /**
     572              :  * Predicate used after async verification resolves: a missing-asset
     573              :  * candidate is surfaceable when it is confirmed missing and its
     574              :  * enclosing subgraph is still active. Null `nodeId` (workflow-level
     575              :  * models) bypasses the ancestor check since it has no scope to
     576              :  * validate. Shared by the missing-model pipeline post-filter and its
     577              :  * async-resolution call site; missing media resolves scope through the
     578              :  * promoted-widget-aware `isMissingMediaCandidateActive` instead.
     579              :  */
     580         5599 : export function isMissingCandidateActive(
     581              :   rootGraph: LGraph | null | undefined,
     582              :   candidate: {
     583              :     nodeId?: string | number | null | undefined
     584              :     sourceExecutionId?: string | number | null | undefined
     585              :     isMissing?: boolean | undefined
     586              :     promotedSources?: readonly PromotedWidgetExecutionSource[]
     587              :   }
     588              : ): boolean {
     589         5599 :   if (candidate.isMissing !== true) return false
     590         5524 :   return isCandidateScopeActive(rootGraph, candidate)
     591              : }
     592              : 
     593              : /**
     594              :  * Returns the execution ID for a node identified by its (graph, nodeId) pair.
     595              :  *
     596              :  * Unlike {@link getExecutionIdByNode}, this does not rely on `node.graph`.
     597              :  * Use this when the node reference may be detached (e.g. inside
     598              :  * `onNodeRemoved`, which LiteGraph fires after clearing `node.graph`).
     599              :  *
     600              :  * @param rootGraph - The root graph to resolve from
     601              :  * @param graph     - The graph the node currently lives in (or lived in)
     602              :  * @param nodeId    - The local node ID within `graph`
     603              :  */
     604        10088 : export function getExecutionIdForNodeInGraph(
     605              :   rootGraph: LGraph,
     606              :   graph: LGraph | Subgraph,
     607              :   nodeId: string | number
     608              : ): NodeExecutionId | null {
     609        10088 :   const localNodeId = parseNodeId(nodeId)
     610        10088 :   if (!localNodeId) return null
     611              : 
     612        10088 :   const localExecutionId = createNodeExecutionId([localNodeId])
     613        10088 :   if (graph === rootGraph || graph.isRootGraph) return localExecutionId
     614              : 
     615           32 :   const parentPath = findPartialExecutionPathToGraph(graph, rootGraph)
     616         1443 :   if (parentPath === undefined) return localExecutionId
     617              : 
     618        10088 :   return createExecutionIdFromPath(parentPath, localNodeId) ?? localExecutionId
     619              : }
     620              : 
     621              : /**
     622              :  * Returns the execution ID for a node described by its shell state, without
     623              :  * requiring a pre-existing {@link LGraphNode} reference. Subgraph nodes return
     624              :  * the full colon-separated path (e.g. `"65:70:63"`). Falls back to the local id
     625              :  * if the node cannot be resolved.
     626              :  */
     627        18963 : export function executionIdFromState(
     628              :   rootGraph: LGraph,
     629              :   state: Pick<NodeState, 'id' | 'graphId'>
     630              : ): NodeExecutionId | null {
     631        18963 :   const localNodeId = parseNodeId(state.id)
     632        18963 :   if (!localNodeId) return null
     633              : 
     634              :   // A root-owned node has no ancestor path to encode, so its raw id can be
     635              :   // kept whole even when it contains a colon that isn't a subgraph-scope
     636              :   // prefix (comfy-multi-player's insert_workflow remapped ids, PM-1580) —
     637              :   // see `createLeafNodeExecutionId`. A node that IS meant to live inside a
     638              :   // subgraph still goes through the strict, segment-splitting path.
     639        18963 :   const fallback = subgraphIdFromState(state, rootGraph.id)
     640              :     ? createNodeExecutionId([localNodeId])
     641              :     : createLeafNodeExecutionId(localNodeId)
     642              : 
     643        18963 :   const locatorId = locatorIdFromState(state, rootGraph.id)
     644        18963 :   const node = locatorId && getNodeByLocatorId(rootGraph, locatorId)
     645        18963 :   if (!node) return fallback
     646              : 
     647        18963 :   return getExecutionIdByNode(rootGraph, node) ?? fallback
     648              : }
     649              : 
     650        19334 : export function getNodeByState(
     651              :   rootGraph: LGraph,
     652              :   state: Pick<NodeState, 'id' | 'graphId'>
     653              : ): LGraphNode | null {
     654              :   const graph =
     655              :     state.graphId === rootGraph.id
     656              :       ? rootGraph
     657              :       : findSubgraphByUuid(rootGraph, state.graphId)
     658        19334 :   return graph?.getNodeById(state.id) ?? null
     659              : }
     660              : 
     661              : /**
     662              :  * Get a node by its locator ID from anywhere in the graph hierarchy.
     663              :  * For subgraph nodes, the format is `<subgraph-definition-uuid>:<node-id>` where
     664              :  * the node ID is a sequential integer, not a UUID.
     665              :  *
     666              :  * @param rootGraph - The root graph to search from
     667              :  * @param locatorId - The locator ID (e.g., "a1b2c3d4-e5f6-7890-abcd-ef1234567890:123" or "123")
     668              :  * @returns The node if found, null otherwise
     669              :  */
     670        27401 : export function getNodeByLocatorId(
     671              :   rootGraph: LGraph,
     672              :   locatorId: string
     673              : ): LGraphNode | null {
     674        27401 :   const parsedIds = parseNodeLocatorId(locatorId)
     675        27401 :   if (!parsedIds) {
     676            0 :     const leafNodeId = parseNodeId(locatorId)
     677            0 :     return leafNodeId ? rootGraph.getNodeById(leafNodeId) || null : null
     678              :   }
     679              : 
     680        27401 :   const { subgraphUuid, localNodeId } = parsedIds
     681              : 
     682              :   // If no subgraph UUID, it's in the root graph
     683        27401 :   if (!subgraphUuid) {
     684        27051 :     return rootGraph.getNodeById(localNodeId) || null
     685              :   }
     686              : 
     687              :   // Find the subgraph with the matching UUID
     688          350 :   const targetSubgraph = findSubgraphByUuid(rootGraph, subgraphUuid)
     689         2765 :   if (!targetSubgraph) return null
     690              : 
     691        27401 :   return targetSubgraph.getNodeById(localNodeId) || null
     692              : }
     693              : 
     694              : /**
     695              :  * Convert execution context node IDs to NodeLocatorIds.
     696              :  * Uses traverseSubgraphPath to resolve the subgraph chain.
     697              :  *
     698              :  * @param rootGraph - The root graph to resolve against
     699              :  * @param nodeId - The node ID from execution context (could be execution ID like "123:456:789")
     700              :  * @returns The NodeLocatorId, or undefined if resolution fails
     701              :  */
     702         1777 : export function executionIdToNodeLocatorId(
     703              :   rootGraph: LGraph | undefined,
     704              :   nodeId: string | number
     705              : ): NodeLocatorId | undefined {
     706         1777 :   const nodeIdStr = String(nodeId)
     707              : 
     708         1777 :   if (!nodeIdStr.includes(':')) {
     709              :     // It's a top-level node ID
     710          812 :     const localNodeId = parseNodeId(nodeIdStr)
     711          812 :     if (!localNodeId) return undefined
     712              : 
     713          812 :     return createNodeLocatorId(null, localNodeId)
     714              :   }
     715              : 
     716         1031 :   if (!rootGraph) return undefined
     717          965 :   const resolved = resolveExecutionNode(rootGraph, nodeIdStr)
     718         1026 :   if (!resolved) return undefined
     719              : 
     720              :   const subgraphUuid = resolved.graph === rootGraph ? null : resolved.graph.id
     721         1777 :   return createNodeLocatorId(subgraphUuid, resolved.node.id)
     722              : }
     723              : 
     724              : /**
     725              :  * Finds the root graph from any graph in the hierarchy.
     726              :  *
     727              :  * @param graph - Any graph or subgraph in the hierarchy
     728              :  * @returns The root graph
     729              :  */
     730              : export function getRootGraph(graph: LGraph | Subgraph): LGraph | Subgraph {
     731              :   let current: LGraph | Subgraph = graph
     732              :   while ('rootGraph' in current) {
     733              :     current = current.rootGraph
     734              :   }
     735              :   return current
     736              : }
     737              : 
     738              : /**
     739              :  * Applies a function to all nodes whose type matches a subgraph ID.
     740              :  * Operates on the entire graph hierarchy starting from the root.
     741              :  *
     742              :  * @param rootGraph - The root graph to search in
     743              :  * @param subgraphId - The ID/type of the subgraph to match nodes against
     744              :  * @param fn - Function to apply to each matching node
     745              :  */
     746            1 : export function forEachSubgraphNode(
     747              :   rootGraph: LGraph | Subgraph | null | undefined,
     748              :   subgraphId: string | null | undefined,
     749              :   fn: (node: LGraphNode) => void
     750              : ): void {
     751            1 :   if (!rootGraph || !subgraphId) return
     752              : 
     753            1 :   forEachNode(rootGraph, (node) => {
     754            9 :     if (node.type === subgraphId) {
     755            1 :       fn(node)
     756              :     }
     757              :   })
     758              : }
     759              : 
     760              : /**
     761              :  * Maps a function over all nodes whose type matches a subgraph ID.
     762              :  * Operates on the entire graph hierarchy starting from the root.
     763              :  *
     764              :  * @param rootGraph - The root graph to search in
     765              :  * @param subgraphId - The ID/type of the subgraph to match nodes against
     766              :  * @param mapFn - Function to apply to each matching node
     767              :  * @returns Array of mapped results
     768              :  */
     769              : export function mapSubgraphNodes<T>(
     770              :   rootGraph: LGraph | Subgraph | null | undefined,
     771              :   subgraphId: string | null | undefined,
     772              :   mapFn: (node: LGraphNode) => T
     773              : ): T[] {
     774              :   if (!rootGraph || !subgraphId) return []
     775              : 
     776              :   return mapAllNodes(rootGraph, (node) => {
     777              :     if (node.type === subgraphId) {
     778              :       return mapFn(node)
     779              :     }
     780              :     return undefined
     781              :   })
     782              : }
     783              : 
     784              : /**
     785              :  * Gets all non-IO nodes from a subgraph (excludes SubgraphInputNode and SubgraphOutputNode).
     786              :  * These are the user-created nodes that can be safely removed when clearing a subgraph.
     787              :  *
     788              :  * @param subgraph - The subgraph to get non-IO nodes from
     789              :  * @returns Array of non-IO nodes (user-created nodes)
     790              :  */
     791            0 : export function getAllNonIoNodesInSubgraph(subgraph: Subgraph): LGraphNode[] {
     792            0 :   return subgraph.nodes.filter((node) => !isSubgraphIoNode(node))
     793              : }
     794              : 
     795              : /**
     796              :  * Options for traverseNodesDepthFirst function
     797              :  */
     798              : interface TraverseNodesOptions<T> {
     799              :   /** Function called for each node during traversal */
     800              :   visitor?: (node: LGraphNode, context: T) => T
     801              :   /** Initial context value */
     802              :   initialContext?: T
     803              :   /** Whether to traverse into subgraph nodes (default: true) */
     804              :   expandSubgraphs?: boolean
     805              : }
     806              : 
     807              : /**
     808              :  * Performs depth-first traversal of nodes and their subgraphs.
     809              :  * Generic visitor pattern that can be used for various node processing tasks.
     810              :  *
     811              :  * @param nodes - Starting nodes for traversal
     812              :  * @param options - Optional traversal configuration
     813              :  */
     814            2 : export function traverseNodesDepthFirst<T = void>(
     815              :   nodes: LGraphNode[],
     816              :   options?: TraverseNodesOptions<T>
     817              : ): void {
     818            2 :   const visitor = options?.visitor ?? (() => undefined as T)
     819            2 :   const initialContext =
     820              :     options?.initialContext === undefined
     821              :       ? (undefined as T)
     822              :       : options.initialContext
     823            2 :   const expandSubgraphs = options?.expandSubgraphs ?? true
     824              :   type StackItem = { node: LGraphNode; context: T }
     825            2 :   const stack: StackItem[] = []
     826              : 
     827              :   // Initialize stack with starting nodes
     828            2 :   for (const node of nodes) {
     829            2 :     stack.push({ node, context: initialContext })
     830              :   }
     831              : 
     832              :   // Process stack iteratively (DFS)
     833            2 :   while (stack.length > 0) {
     834            2 :     const { node, context } = stack.pop()!
     835              : 
     836              :     // Visit node and get updated context for children
     837            2 :     const childContext = visitor(node, context)
     838              : 
     839              :     // If it's a subgraph and we should expand, add children to stack
     840            2 :     if (expandSubgraphs && isSubgraphNode(node)) {
     841              :       // Process children in reverse order to maintain left-to-right DFS processing
     842              :       // when popping from stack (LIFO). Iterate backwards to avoid array reversal.
     843            0 :       const children = node.subgraph.nodes
     844            0 :       for (let i = children.length - 1; i >= 0; i--) {
     845            0 :         stack.push({ node: children[i], context: childContext })
     846              :       }
     847              :     }
     848              :   }
     849              : }
     850              : 
     851              : /**
     852              :  * Reduces all nodes in a graph hierarchy to a single value using a reducer function.
     853              :  * Single-pass traversal for efficient aggregation.
     854              :  *
     855              :  * @param graph - The root graph to traverse
     856              :  * @param reducer - Function that reduces each node into the accumulator
     857              :  * @param initialValue - The initial accumulator value
     858              :  * @returns The final reduced value
     859              :  */
     860        13312 : export function reduceAllNodes<T>(
     861              :   graph: LGraph | Subgraph,
     862              :   reducer: (accumulator: T, node: LGraphNode) => T,
     863              :   initialValue: T
     864              : ): T {
     865        13312 :   let result = initialValue
     866        13312 :   forEachNode(graph, (node) => {
     867        51496 :     result = reducer(result, node)
     868              :   })
     869        13312 :   return result
     870              : }
     871              : 
     872              : /**
     873              :  * Options for collectFromNodes function
     874              :  */
     875              : interface CollectFromNodesOptions<T, C> {
     876              :   /** Function that returns data to collect for each node */
     877              :   collector?: (node: LGraphNode, context: C) => T | null
     878              :   /** Function that builds context for child nodes */
     879              :   contextBuilder?: (node: LGraphNode, parentContext: C) => C
     880              :   /** Initial context value */
     881              :   initialContext?: C
     882              :   /** Whether to traverse into subgraph nodes (default: true) */
     883              :   expandSubgraphs?: boolean
     884              : }
     885              : 
     886              : /**
     887              :  * Collects nodes with custom data during depth-first traversal.
     888              :  * Generic collector that can gather any type of data per node.
     889              :  *
     890              :  * @param nodes - Starting nodes for traversal
     891              :  * @param options - Optional collection configuration
     892              :  * @returns Array of collected data
     893              :  */
     894            2 : export function collectFromNodes<T = LGraphNode, C = void>(
     895              :   nodes: LGraphNode[],
     896              :   options?: CollectFromNodesOptions<T, C>
     897              : ): T[] {
     898            2 :   const {
     899              :     collector = (node: LGraphNode) => node as T,
     900              :     contextBuilder = () => undefined as C,
     901              :     initialContext,
     902              :     expandSubgraphs = true
     903              :   } = options || {}
     904            2 :   const results: T[] = []
     905              : 
     906            2 :   traverseNodesDepthFirst(nodes, {
     907              :     visitor: (node, context) => {
     908            2 :       const data = collector(node, context)
     909            2 :       if (data !== null) {
     910            2 :         results.push(data)
     911              :       }
     912            2 :       return contextBuilder(node, context)
     913              :     },
     914              :     initialContext,
     915              :     expandSubgraphs
     916              :   })
     917              : 
     918            2 :   return results
     919              : }
     920              : 
     921              : /**
     922              :  * Collects execution IDs for selected nodes and all their descendants.
     923              :  * Uses the generic DFS traversal with optimized string building.
     924              :  *
     925              :  * @param selectedNodes - The selected nodes to process
     926              :  * @returns Array of execution IDs for selected nodes and all nodes within selected subgraphs
     927              :  */
     928            2 : export function getExecutionIdsForSelectedNodes(
     929              :   selectedNodes: LGraphNode[],
     930              :   startGraph = selectedNodes[0]?.graph
     931              : ): NodeExecutionId[] {
     932            2 :   if (!startGraph) return []
     933            2 :   const rootGraph = startGraph.rootGraph
     934            2 :   const parentPath = startGraph.isRootGraph
     935              :     ? ''
     936              :     : findPartialExecutionPathToGraph(startGraph, rootGraph)
     937            2 :   if (parentPath === undefined) return []
     938              : 
     939            4 :   function buildExecId(
     940              :     node: LGraphNode,
     941              :     parentExecutionId: string | null
     942              :   ): NodeExecutionId | null {
     943            4 :     if (!parentExecutionId) return createLeafNodeExecutionId(node.id)
     944              : 
     945            0 :     return createExecutionIdFromPath(parentExecutionId, node.id)
     946              :   }
     947            2 :   return collectFromNodes<NodeExecutionId, string | null>(selectedNodes, {
     948              :     collector: buildExecId,
     949              :     contextBuilder: buildExecId,
     950              :     initialContext: parentPath,
     951              :     expandSubgraphs: true
     952              :   })
     953              : }
     954              : 
     955              : /**
     956              :  * Returns the set of local graph node IDs (as strings) for nodes that live in
     957              :  * `activeGraph` and whose execution ID appears in `executionIds`.
     958              :  *
     959              :  * @param rootGraph - The root graph used to resolve execution IDs
     960              :  * @param activeGraph - The currently-visible graph scope
     961              :  * @param executionIds - Set of execution IDs to look up
     962              :  * @returns Set of stringified local node IDs belonging to activeGraph
     963              :  */
     964         4490 : export function getActiveGraphNodeIds(
     965              :   rootGraph: LGraph,
     966              :   activeGraph: LGraph | Subgraph,
     967              :   executionIds: Set<NodeExecutionId>
     968              : ): Set<string> {
     969         4490 :   const ids = new Set<string>()
     970         4490 :   for (const executionId of executionIds) {
     971         2060 :     const graphNode = getNodeByExecutionId(rootGraph, executionId)
     972         2060 :     if (graphNode?.graph === activeGraph) {
     973         1963 :       ids.add(String(graphNode.id))
     974              :     }
     975              :   }
     976         4490 :   return ids
     977              : }
     978              : 
     979         8986 : function findPartialExecutionPathToGraph(
     980              :   target: LGraph,
     981              :   root: LGraph
     982              : ): string | undefined {
     983         8986 :   for (const node of root.nodes) {
     984        22610 :     if (!node.isSubgraphNode()) continue
     985              : 
     986        14074 :     if (node.subgraph === target) return node.id
     987              : 
     988         1856 :     const subpath = findPartialExecutionPathToGraph(target, node.subgraph)
     989         2418 :     if (subpath !== undefined) return node.id + ':' + subpath
     990              :   }
     991              :   return undefined
     992              : }
     993              : 
     994              : type InputLink = ReturnType<LGraphNode['getInputLink']>
     995              : 
     996          158 : export function resolveInputSourceNode(
     997              :   node: LGraphNode,
     998              :   slot: number,
     999              :   host?: SubgraphNode
    1000              : ): LGraphNode | undefined {
    1001          158 :   const link = node.getInputLink(slot)
    1002          158 :   if (link?.origin_id === SUBGRAPH_INPUT_ID) {
    1003            0 :     return host?.subgraph === node.graph
    1004              :       ? resolveHostInputSourceNode(host, link.origin_slot)
    1005              :       : undefined
    1006              :   }
    1007          158 :   return followSubgraphOutputs(node.getInputNode(slot), link)
    1008              : }
    1009              : 
    1010            0 : function resolveHostInputSourceNode(
    1011              :   host: SubgraphNode,
    1012              :   slot: number
    1013              : ): LGraphNode | undefined {
    1014            0 :   const graph = host.graph
    1015            0 :   const link = graph ? inputLink(graph, host.id, slot) : undefined
    1016            0 :   if (!graph || !link) return undefined
    1017            0 :   return followSubgraphOutputs(graph.getNodeById(link.origin_id), link)
    1018              : }
    1019              : 
    1020          158 : function followSubgraphOutputs(
    1021              :   source: LGraphNode | null,
    1022              :   sourceLink: InputLink | undefined
    1023              : ): LGraphNode | undefined {
    1024          158 :   let upstream = source
    1025          158 :   let link = sourceLink
    1026          158 :   const visited = new Set<LGraphNode>()
    1027              : 
    1028          158 :   while (upstream?.isSubgraphNode()) {
    1029            0 :     if (!link || visited.has(upstream)) return undefined
    1030            0 :     visited.add(upstream)
    1031              : 
    1032            0 :     const resolved = upstream.resolveSubgraphOutputLink(link.origin_slot)
    1033            0 :     if (!resolved) return undefined
    1034              : 
    1035            0 :     upstream = resolved.outputNode ?? null
    1036            0 :     link = resolved.link
    1037              :   }
    1038              : 
    1039          158 :   return upstream ?? undefined
    1040              : }
        

Generated by: LCOV version 2.0-1