| 1 | /** |
| 2 | * A trace's spans in the order a waterfall shows them: each span under |
| 3 | * its parent, children by start time. A span whose parent never arrived |
| 4 | * (sent by software that does not report here, or lost) starts a root of |
| 5 | * its own, so nothing is hidden. |
| 6 | */ |
| 7 | import type { TelemetrySpan } from "@g1t/contracts"; |
| 8 | |
| 9 | export function spanTree(spans: TelemetrySpan[]): { span: TelemetrySpan; depth: number }[] { |
| 10 | const ids = new Set(spans.map((s) => s.span_id)); |
| 11 | const children = new Map<string | null, TelemetrySpan[]>(); |
| 12 | for (const s of spans) { |
| 13 | const parent = s.parent_span_id && ids.has(s.parent_span_id) && s.parent_span_id !== s.span_id ? s.parent_span_id : null; |
| 14 | children.set(parent, [...(children.get(parent) ?? []), s]); |
| 15 | } |
| 16 | for (const list of children.values()) list.sort((a, b) => a.start_us - b.start_us); |
| 17 | const out: { span: TelemetrySpan; depth: number }[] = []; |
| 18 | const seen = new Set<string>(); |
| 19 | const walk = (parent: string | null, depth: number) => { |
| 20 | for (const s of children.get(parent) ?? []) { |
| 21 | if (seen.has(s.span_id)) continue; |
| 22 | seen.add(s.span_id); |
| 23 | out.push({ span: s, depth }); |
| 24 | walk(s.span_id, depth + 1); |
| 25 | } |
| 26 | }; |
| 27 | walk(null, 0); |
| 28 | // Spans in a loop of parents, which no root reaches. |
| 29 | for (const s of spans) if (!seen.has(s.span_id)) out.push({ span: s, depth: 0 }); |
| 30 | return out; |
| 31 | } |