Skip to content

:hedgehog: PostHog is the leading platform for building self-driving products. Our developer tools – AI observability, analytics, session replay, flags, experiments, error tracking, logs, and more – capture all the context agents need to diagnose problems, uncover opportunities, and ship fixes. Steer it all from Slack, web, desktop, or the MCP.

8.4 KB
Raw Blame
import type { Span } from './types'

/**
 * Parse an ISO 8601 timestamp string to microseconds since epoch.
 * `Date.getTime()` only gives millisecond resolution, losing sub-ms
 * precision from timestamps like "2024-01-15T10:30:00.123456Z".
 */
export function parseTimestampUs(iso: string): number {
    const ms = new Date(iso).getTime()
    // Extract fractional seconds beyond milliseconds
    const dot = iso.indexOf('.')
    if (dot === -1) {
        return ms * 1_000
    }
    // Find the end of fractional digits (before 'Z')
    const fracEnd = iso.search(/[Z+-](\d\d:\d\d)?$/i)
    if (fracEnd === -1) {
        return ms * 1_000
    }
    const fracStr = iso.slice(dot + 1, fracEnd)
    // Pad or truncate to 6 digits (microseconds)
    const padded = fracStr.padEnd(6, '0').slice(0, 6)
    const totalUs = parseInt(padded, 10)
    // ms already includes the first 3 fractional digits, so add the remaining sub-ms part
    const subMsUs = totalUs % 1_000
    return ms * 1_000 + subMsUs
}

export interface SpanNode {
    span: Span
    children: SpanNode[]
    depth: number
    isLastChild: boolean
    parent: SpanNode | null
    /** A placeholder for a parent span that is not in the trace. Its children are the spans that point to it. */
    isMissingParent?: boolean
}

const MISSING_PARENT_LABEL = '<parent span missing>'

function missingParentNode(parentSpanId: string, child: Span): SpanNode {
    return {
        span: {
            uuid: `missing-parent-${parentSpanId}`,
            trace_id: child.trace_id,
            span_id: parentSpanId,
            parent_span_id: '',
            name: MISSING_PARENT_LABEL,
            kind: 0,
            service_name: '',
            status_code: 0,
            timestamp: child.timestamp,
            end_time: child.timestamp,
            duration_nano: 0,
            is_root_span: false,
            matched_filter: true,
            attributes: {},
            resource_attributes: {},
        },
        children: [],
        depth: 0,
        isLastChild: false,
        parent: null,
        isMissingParent: true,
    }
}

// A root span has the all-zero OTel parent id, which the API returns as hex ("0000000000000000"), not "".
function parentSpanIdOf(span: Span): string | null {
    if (span.is_root_span || !span.parent_span_id || /^0+$/.test(span.parent_span_id)) {
        return null
    }
    return span.parent_span_id
}

export function buildSpanTree(spans: Span[]): SpanNode[] {
    const byId = new Map<string, SpanNode>()
    const missingParents = new Map<string, SpanNode>()
    const roots: SpanNode[] = []

    for (const span of spans) {
        byId.set(span.span_id, { span, children: [], depth: 0, isLastChild: false, parent: null })
    }

    for (const node of byId.values()) {
        const parentSpanId = parentSpanIdOf(node.span)
        if (parentSpanId && byId.has(parentSpanId)) {
            const parent = byId.get(parentSpanId)!
            parent.children.push(node)
            node.parent = parent
        } else if (parentSpanId) {
            let placeholder = missingParents.get(parentSpanId)
            if (!placeholder) {
                placeholder = missingParentNode(parentSpanId, node.span)
                missingParents.set(parentSpanId, placeholder)
                roots.push(placeholder)
            }
            placeholder.children.push(node)
            node.parent = placeholder
            // The placeholder sorts with the other roots by its earliest child.
            if (parseTimestampUs(node.span.timestamp) < parseTimestampUs(placeholder.span.timestamp)) {
                placeholder.span.timestamp = node.span.timestamp
                placeholder.span.end_time = node.span.timestamp
            }
        } else {
            roots.push(node)
        }
    }

    // Iterative so a deep parent/child chain cannot overflow the call stack.
    const groups: { nodes: SpanNode[]; depth: number }[] = [{ nodes: roots, depth: 0 }]
    while (groups.length > 0) {
        const { nodes, depth } = groups.pop()!
        for (let i = 0; i < nodes.length; i++) {
            const node = nodes[i]
            node.depth = depth
            node.isLastChild = i === nodes.length - 1
            if (node.children.length > 0) {
                node.children.sort(
                    (a, b) => new Date(a.span.timestamp).getTime() - new Date(b.span.timestamp).getTime()
                )
                groups.push({ nodes: node.children, depth: depth + 1 })
            }
        }
    }

    return roots
}

/**
 * Whether each ancestor level, root first, continues below this node, so the waterfall can draw its tree
 * lines. Derived on demand for the rows on screen: storing it on every node costs memory quadratic in depth.
 */
export function connectorLinesOf(node: SpanNode): boolean[] {
    const lines: boolean[] = []
    for (let ancestor = node.parent; ancestor; ancestor = ancestor.parent) {
        lines.push(!ancestor.isLastChild)
    }
    return lines.reverse()
}

function sortChildren(nodes: SpanNode[]): SpanNode[] {
    return [...nodes].sort((a, b) => parseTimestampUs(a.span.timestamp) - parseTimestampUs(b.span.timestamp))
}

export function countDescendants(node: SpanNode): number {
    let total = 0
    const stack = [...node.children]
    while (stack.length > 0) {
        const current = stack.pop()!
        total += 1
        for (const child of current.children) {
            stack.push(child)
        }
    }
    return total
}

/** Child spans by parent span id. A root by the rule `buildSpanTree` uses gets no entry as a child. */
export function childSpansByParentId(spans: Span[]): Map<string, Span[]> {
    const children = new Map<string, Span[]>()
    for (const span of spans) {
        const parentSpanId = parentSpanIdOf(span)
        if (!parentSpanId) {
            continue
        }
        const siblings = children.get(parentSpanId)
        if (siblings) {
            siblings.push(span)
        } else {
            children.set(parentSpanId, [span])
        }
    }
    return children
}

/**
 * The span and every span under it. The visited set holds span objects, not ids, so a parent cycle in
 * malformed data cannot loop and two spans that share an id both count.
 */
export function collectSubtreeSpans(root: Span, childrenByParentId: Map<string, Span[]>): Span[] {
    const subtree: Span[] = []
    const visited = new Set<Span>()
    const stack = [root]
    while (stack.length > 0) {
        const span = stack.pop()!
        if (visited.has(span)) {
            continue
        }
        visited.add(span)
        subtree.push(span)
        for (const child of childrenByParentId.get(span.span_id) ?? []) {
            stack.push(child)
        }
    }
    return subtree
}

/** Depth-first flatten for rendering, skipping the subtree of any collapsed span. */
export function flattenTree(nodes: SpanNode[], collapsedSpanIds: Set<string>): SpanNode[] {
    const result: SpanNode[] = []
    // An explicit stack, in reverse so the earliest child pops first, keeps deep traces off the call stack.
    const stack = sortChildren(nodes).reverse()
    while (stack.length > 0) {
        const node = stack.pop()!
        result.push(node)
        if (!collapsedSpanIds.has(node.span.span_id)) {
            const children = sortChildren(node.children)
            for (let i = children.length - 1; i >= 0; i--) {
                stack.push(children[i])
            }
        }
    }
    return result
}

/** span_ids of every node that has children — the set of spans that can be collapsed. */
export function collectCollapsibleSpanIds(nodes: SpanNode[]): Set<string> {
    const ids = new Set<string>()
    const stack = [...nodes]
    while (stack.length > 0) {
        const node = stack.pop()!
        if (node.children.length > 0) {
            ids.add(node.span.span_id)
        }
        for (const child of node.children) {
            stack.push(child)
        }
    }
    return ids
}

/** Generate evenly spaced tick marks for the timeline (in microseconds) */
export function getTimelineTicks(durationUs: number): number[] {
    if (durationUs <= 0) {
        return []
    }
    const targetTickCount = 5
    const rawInterval = durationUs / targetTickCount
    const magnitude = Math.pow(10, Math.floor(Math.log10(rawInterval)))
    const niceIntervals = [1, 2, 5, 10]
    const interval = niceIntervals.find((n) => n * magnitude >= rawInterval)! * magnitude
    const ticks: number[] = []
    for (let t = interval; t < durationUs; t += interval) {
        ticks.push(t)
    }
    return ticks
}