(pairs: ReadonlyArray<{ source: string; target: string }>)
| 15 | * runs over one index print the same report. |
| 16 | */ |
| 17 | export function findFileCycles(pairs: ReadonlyArray<{ source: string; target: string }>): string[][] { |
| 18 | const adjacency = new Map<string, string[]>(); |
| 19 | for (const pair of pairs) { |
| 20 | let out = adjacency.get(pair.source); |
| 21 | if (!out) adjacency.set(pair.source, (out = [])); |
| 22 | out.push(pair.target); |
| 23 | } |
| 24 | // Deterministic iteration: SQLite's DISTINCT ordering is not a contract. |
| 25 | const nodes = [...new Set([...adjacency.keys(), ...[...adjacency.values()].flat()])].sort(); |
| 26 | for (const list of adjacency.values()) list.sort(); |
| 27 | |
| 28 | return tarjan(nodes, (id) => adjacency.get(id) ?? []) |
| 29 | .filter((component) => component.length > 1) |
| 30 | .map((component) => component.slice().sort()) |
| 31 | .sort((a, b) => a.length - b.length || (a[0] ?? '').localeCompare(b[0] ?? '')); |
| 32 | } |
| 33 | |
| 34 | /** Tarjan's strongly connected components, iterative so a deep graph cannot blow the stack. */ |
| 35 | function tarjan(nodes: readonly string[], edgesOf: (id: string) => readonly string[]): string[][] { |
no test coverage detected