(edges: readonly GraphEdge[], roots: ReadonlySet<number>, target: number,
direction: TraceDirection)
| 17 | * loaded scope; a root target has the empty path. Hops are counted, nothing |
| 18 | * else: there is no runtime or architectural distance in this number. */ |
| 19 | export function shortestScopePath(edges: readonly GraphEdge[], roots: ReadonlySet<number>, target: number, |
| 20 | direction: TraceDirection): ScopePathStep[] | undefined { |
| 21 | if (roots.has(target)) return []; |
| 22 | const next = new Map<number, { to: number; edge: GraphEdge; index: number }[]>(); |
| 23 | const link = (from: number, to: number, edge: GraphEdge, index: number) => { |
| 24 | const list = next.get(from) ?? []; list.push({ to, edge, index }); next.set(from, list); |
| 25 | }; |
| 26 | edges.forEach((edge, index) => { |
| 27 | if (edge.source === edge.target) return; |
| 28 | if (direction !== 'inbound') link(edge.source, edge.target, edge, index); |
| 29 | if (direction !== 'outbound') link(edge.target, edge.source, edge, index); |
| 30 | }); |
| 31 | next.forEach(list => list.sort(order)); |
| 32 | const reached = new Map<number, { from: number; edge: GraphEdge } | undefined>([...roots].sort((a, b) => a - b).map(root => [root, undefined])); |
| 33 | const queue = [...reached.keys()]; |
| 34 | for (let at = 0; at < queue.length && !reached.has(target); at++) { |
| 35 | const from = queue[at]!; |
| 36 | for (const hop of next.get(from) ?? []) { |
| 37 | if (reached.has(hop.to)) continue; |
| 38 | reached.set(hop.to, { from, edge: hop.edge }); |
| 39 | queue.push(hop.to); |
| 40 | } |
| 41 | } |
| 42 | if (!reached.has(target)) return undefined; |
| 43 | const steps: ScopePathStep[] = []; |
| 44 | let node = target, parent = reached.get(node); |
| 45 | while (parent) { |
| 46 | steps.push({ edge: parent.edge, from: parent.from, to: node }); |
| 47 | node = parent.from; parent = reached.get(node); |
| 48 | } |
| 49 | return steps.reverse(); |
| 50 | } |
| 51 | |
| 52 | /** The root's outgoing CALLS in source order: by call-site line, calls without |
| 53 | * a recorded line last, then by callee. Every call site is its own step. */ |
no test coverage detected