dial9-viewer 0.3.13

// trace_analysis.js - Derived analysis on parsed trace data
// Can be used in browser or Node.js

(function (exports) {
  "use strict";

  function getParser() {
    if (typeof require !== "undefined") {
      return require("./trace_parser.js");
    }
    if (typeof TraceParser !== "undefined") return TraceParser;
    throw new Error(
      "TraceParser not found. Load trace_parser.js before trace_analysis.js"
    );
  }

  const parser = getParser();
  const EVENT_TYPES = parser.EVENT_TYPES;
  const formatFrame = parser.formatFrame;

  function isCpuProfileSample(sample) {
    return sample.callchain.length > 0 && sample.source !== 1;
  }

  function hasCpuProfileSamples(cpuSamples) {
    return cpuSamples.some(isCpuProfileSample);
  }

  function getTraceTimeRange(events, cpuSamples) {
    const timestamps = events.length
      ? events.map((e) => e.timestamp)
      : cpuSamples.filter(isCpuProfileSample).map((s) => s.timestamp);
    if (!timestamps.length) return null;

    let minTs = timestamps[0];
    let maxTs = timestamps[0];
    for (const timestamp of timestamps) {
      if (timestamp < minTs) minTs = timestamp;
      if (timestamp > maxTs) maxTs = timestamp;
    }
    if (maxTs === minTs) maxTs = minTs + 1;
    return { minTs, maxTs, durationNs: maxTs - minTs };
  }

  // ── Poll color heatmap ────────────────────────────────────────────────
  // Maps a poll duration in nanoseconds to a hex color string using a
  // log-scale ramp.
  //
  // Why log scale: poll durations span many orders of magnitude (≤100ns
  // common, occasional 100ms+ stalls). A linear ramp would either compress
  // most polls into a single color, or overwhelm the visualization with the
  // hottest few. Log scale gives roughly equal visual weight to each decade.
  //
  // Anchor stops are pinned to the legend swatches in viewer.html so the
  // legend stays an honest reference. Stops between anchors are interpolated
  // linearly in RGB. Inputs below the floor (100ns) clamp to dim navy;
  // inputs above the ceiling (1s) clamp to deep red.
  //
  // The previous bucketed scheme (4 colors at fixed thresholds) is replaced
  // by this continuous version — see issue #450.
  const POLL_HEATMAP_STOPS = [
    { logNs: 2, rgb: [0x2a, 0x5a, 0x7a] }, // 100ns: dim navy (floor)
    { logNs: 4, rgb: [0x4f, 0xc3, 0xf7] }, // 10µs: cyan
    { logNs: 5, rgb: [0xff, 0x8a, 0x65] }, // 100µs: orange
    { logNs: 6, rgb: [0xff, 0x44, 0x44] }, // 1ms: bright red
    { logNs: 9, rgb: [0xff, 0x00, 0x00] }, // 1s+: pure red (ceiling)
  ];

  function _toHex2(n) {
    const h = Math.round(n).toString(16);
    return h.length === 1 ? "0" + h : h;
  }

  /**
   * Continuous, log-scale color heatmap for poll durations.
   * @param {number} durationNs poll duration in nanoseconds (≥ 0)
   * @returns {string} `#rrggbb` color
   */
  function pollHeatmapColor(durationNs) {
    const stops = POLL_HEATMAP_STOPS;
    if (!(durationNs > 0)) {
      const f = stops[0].rgb;
      return "#" + _toHex2(f[0]) + _toHex2(f[1]) + _toHex2(f[2]);
    }
    const lg = Math.log10(durationNs);
    if (lg <= stops[0].logNs) {
      const f = stops[0].rgb;
      return "#" + _toHex2(f[0]) + _toHex2(f[1]) + _toHex2(f[2]);
    }
    if (lg >= stops[stops.length - 1].logNs) {
      const f = stops[stops.length - 1].rgb;
      return "#" + _toHex2(f[0]) + _toHex2(f[1]) + _toHex2(f[2]);
    }
    // Find interpolation segment
    for (let i = 0; i < stops.length - 1; i++) {
      const a = stops[i],
        b = stops[i + 1];
      if (lg >= a.logNs && lg <= b.logNs) {
        const t = (lg - a.logNs) / (b.logNs - a.logNs);
        const r = a.rgb[0] + (b.rgb[0] - a.rgb[0]) * t;
        const g = a.rgb[1] + (b.rgb[1] - a.rgb[1]) * t;
        const bl = a.rgb[2] + (b.rgb[2] - a.rgb[2]) * t;
        return "#" + _toHex2(r) + _toHex2(g) + _toHex2(bl);
      }
    }
    // Unreachable
    const f = stops[stops.length - 1].rgb;
    return "#" + _toHex2(f[0]) + _toHex2(f[1]) + _toHex2(f[2]);
  }

  // Quantize a poll duration to a small fixed set of bucket colors. Used by
  // the LOD path in viewer.html to merge adjacent polls with identical color
  // into a single fillRect; with 16 quantization bins per decade-spanning
  // log scale, runs of "approximately equal" polls still fold into one
  // rectangle, which keeps zoomed-out rendering fast.
  function pollHeatmapColorQuantized(durationNs, bins) {
    const NBINS = bins || 24;
    const stops = POLL_HEATMAP_STOPS;
    const minLg = stops[0].logNs;
    const maxLg = stops[stops.length - 1].logNs;
    let lg;
    if (!(durationNs > 0)) lg = minLg;
    else lg = Math.log10(durationNs);
    if (lg < minLg) lg = minLg;
    if (lg > maxLg) lg = maxLg;
    const t = (lg - minLg) / (maxLg - minLg);
    const bin = Math.min(NBINS - 1, Math.floor(t * NBINS));
    const lgBin = minLg + (bin / (NBINS - 1)) * (maxLg - minLg);
    const dBin = Math.pow(10, lgBin);
    return pollHeatmapColor(dBin);
  }

  /**
   * Reconstruct poll/park/active spans from raw events using a state machine.
   * @param {import('./trace_parser.js').TraceEvent[]} events - raw trace events
   * @param {number[]} workerIds - sorted worker IDs
   * @param {number} maxTs - end-of-trace timestamp for closing open spans
   * @returns {{
   *   workerSpans: Object<number, { polls: Array<{start: number, end: number, taskId?: number, spawnLocId?: string|null, spawnLoc?: string|null}>, parks: Array<{start: number, end: number, schedWait: number}>, actives: Array<{start: number, end: number, ratio: number}>, cpuSampleTimes: number[] }>,
   *   perWorker: Object<number, import('./trace_parser.js').TraceEvent[]>,
   *   queueSamples: Array<{t: number, global: number}>,
   *   workerQueueSamples: Object<number, Array<{t: number, local: number}>>,
   *   maxLocalQueue: number,
   *   wakesByTask: Object<number, Array<{timestamp: number, wakerTaskId: number, targetWorker: number}>>,
   *   wakesByWorker: Object<number, Array<{timestamp: number, wakerTaskId: number, wokenTaskId: number}>>,
   * }}
   */
  function buildWorkerSpans(events, workerIds, maxTs, blockInPlaceGaps) {
    const workerSpans = {};
    const openPoll = {},
      openPark = {},
      openUnpark = {};

    // Build per-worker gap lookup for active-span suppression.
    // An active span that crosses any gap for its worker is discarded
    // (ADR-0002: the CPU-time delta mixes two threads and is meaningless).
    const gapsByW = {};
    if (blockInPlaceGaps && blockInPlaceGaps.length > 0) {
      for (const g of blockInPlaceGaps) {
        (gapsByW[g.workerId] ??= []).push(g);
      }
    }
    const openPollMeta = {};
    const workerQueueSamples = {};
    let maxLocalQueue = 1;
    const wakesByTask = {};
    const wakesByWorker = {};
    for (const w of workerIds) {
      workerSpans[w] = {
        polls: [],
        parks: [],
        actives: [],
        cpuSampleTimes: [],
      };
      workerQueueSamples[w] = [];
    }

    // Group events by worker and sort per-worker by timestamp
    // Also index wake events in the same pass
    const perWorker = {};
    for (const e of events) {
      if (e.eventType === EVENT_TYPES.WakeEvent) {
        (wakesByTask[e.wokenTaskId] ??= []).push({
          timestamp: e.timestamp,
          wakerTaskId: e.wakerTaskId,
          targetWorker: e.targetWorker,
        });
        (wakesByWorker[e.targetWorker] ??= []).push({
          timestamp: e.timestamp,
          wakerTaskId: e.wakerTaskId,
          wokenTaskId: e.wokenTaskId,
        });
      } else if (e.eventType !== EVENT_TYPES.QueueSample) {
        (perWorker[e.workerId] ??= []).push(e);
      }
    }
    for (const wEvents of Object.values(perWorker)) {
      wEvents.sort((a, b) => a.timestamp - b.timestamp);
    }
    for (const arr of Object.values(wakesByTask)) {
      arr.sort((a, b) => a.timestamp - b.timestamp);
    }
    for (const arr of Object.values(wakesByWorker)) {
      arr.sort((a, b) => a.timestamp - b.timestamp);
    }

    for (const [w, wEvents] of Object.entries(perWorker)) {
      for (const e of wEvents) {
        // Extract local queue samples inline
        if (
          e.eventType === EVENT_TYPES.PollStart ||
          e.eventType === EVENT_TYPES.WorkerPark ||
          e.eventType === EVENT_TYPES.WorkerUnpark
        ) {
          workerQueueSamples[w].push({ t: e.timestamp, local: e.localQueue });
          if (e.localQueue > maxLocalQueue) maxLocalQueue = e.localQueue;
        }

        if (e.eventType === EVENT_TYPES.PollStart) {
          // If there's already an open poll (no PollEnd arrived), close it
          // at this timestamp. This happens during block_in_place: the task
          // is still technically polling but the worker moved on to poll
          // another task on the replacement thread.
          if (openPoll[w] != null) {
            const meta = openPollMeta[w] || {
              taskId: 0,
              spawnLocId: 0,
              spawnLoc: null,
            };
            workerSpans[w].polls.push({
              start: openPoll[w],
              end: e.timestamp,
              taskId: meta.taskId,
              spawnLocId: meta.spawnLocId,
              spawnLoc: meta.spawnLoc,
              openEnded: true, // no matching PollEnd; actual duration unknown
            });
          }
          openPoll[w] = e.timestamp;
          openPollMeta[w] = {
            taskId: e.taskId,
            spawnLocId: e.spawnLocId,
            spawnLoc: e.spawnLoc,
          };
        } else if (e.eventType === EVENT_TYPES.PollEnd) {
          if (openPoll[w] != null) {
            const meta = openPollMeta[w] || {
              taskId: 0,
              spawnLocId: 0,
              spawnLoc: null,
            };
            workerSpans[w].polls.push({
              start: openPoll[w],
              end: e.timestamp,
              taskId: meta.taskId,
              spawnLocId: meta.spawnLocId,
              spawnLoc: meta.spawnLoc,
            });
            openPoll[w] = null;
          }
        } else if (e.eventType === EVENT_TYPES.WorkerPark) {
          // Close any open poll at park time. During block_in_place the
          // replacement thread may park while a task is mid-poll (the
          // PollEnd arrives later on a different active period).
          if (openPoll[w] != null) {
            const meta = openPollMeta[w] || {
              taskId: 0,
              spawnLocId: 0,
              spawnLoc: null,
            };
            workerSpans[w].polls.push({
              start: openPoll[w],
              end: e.timestamp,
              taskId: meta.taskId,
              spawnLocId: meta.spawnLocId,
              spawnLoc: meta.spawnLoc,
              openEnded: true,
            });
            openPoll[w] = null;
          }
          openPark[w] = e.timestamp;
          if (openUnpark[w] != null) {
            const activeStart = openUnpark[w].timestamp;
            const activeEnd = e.timestamp;
            // Suppress active spans that cross a block-in-place gap.
            // The CPU-time delta mixes two threads and is meaningless.
            const wGaps = gapsByW[w];
            let crossesGap = false;
            if (wGaps) {
              for (const g of wGaps) {
                if (g.startNs >= activeEnd) break;
                if (g.endNs > activeStart) { crossesGap = true; break; }
              }
            }
            if (!crossesGap) {
              const wallDelta = activeEnd - activeStart;
              const cpuDelta = e.cpuTime - openUnpark[w].cpuTime;
              const ratio =
                wallDelta > 0 ? Math.min(cpuDelta / wallDelta, 1.0) : 1.0;
              workerSpans[w].actives.push({
                start: activeStart,
                end: activeEnd,
                ratio,
              });
            }
            openUnpark[w] = null;
          }
        } else if (e.eventType === EVENT_TYPES.WorkerUnpark) {
          if (openPark[w] != null) {
            workerSpans[w].parks.push({
              start: openPark[w],
              end: e.timestamp,
              schedWait: e.schedWait,
            });
            openPark[w] = null;
          }
          openUnpark[w] = { timestamp: e.timestamp, cpuTime: e.cpuTime };
        }
      }
    }

    // Close any open park spans at trace end.
    // Open polls are discarded: a PollStart without a matching PollEnd
    // means the segment rotated mid-poll, not that the poll was long (#194).
    for (const w of workerIds) {
      if (openPark[w] != null)
        workerSpans[w].parks.push({ start: openPark[w], end: maxTs });
    }

    // Global queue samples
    const queueSamples = events
      .filter((e) => e.eventType === EVENT_TYPES.QueueSample)
      .map((e) => ({ t: e.timestamp, global: e.globalQueue }));

    return { workerSpans, perWorker, queueSamples, workerQueueSamples, maxLocalQueue, wakesByTask, wakesByWorker };
  }

  /**
   * Attach CPU samples to the poll spans they fall within using binary search.
   * Mutates workerSpans poll objects (adds .cpuSamples[], .schedSamples[])
   * and sample objects (sets .spawnLoc).
   * @param {import('./trace_parser.js').CpuSample[]} cpuSamples
   * @param {Object} workerSpans - as returned by buildWorkerSpans
   * @returns {{ pollsWithCpuSamples: number, pollsWithSchedSamples: number }}
   */
  function attachCpuSamples(cpuSamples, workerSpans) {
    for (const sample of cpuSamples) {
      const spans = workerSpans[sample.workerId];
      if (!spans) {
        sample.spawnLoc = null;
        continue;
      }
      if (sample.source !== 1) spans.cpuSampleTimes.push(sample.timestamp);
      const polls = spans.polls;
      const ts = sample.timestamp;
      let lo = 0,
        hi = polls.length - 1,
        found = false;
      while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (polls[mid].start <= ts) {
          lo = mid + 1;
        } else {
          hi = mid - 1;
        }
      }
      if (hi >= 0 && ts <= polls[hi].end) {
        const poll = polls[hi];
        if (sample.source === 1) {
          (poll.schedSamples ??= []).push(sample);
        } else {
          (poll.cpuSamples ??= []).push(sample);
        }
        sample.spawnLoc = poll.spawnLoc;
        found = true;
      }
      if (!found) sample.spawnLoc = null;
    }

    let pollsWithCpuSamples = 0;
    let pollsWithSchedSamples = 0;
    for (const w of Object.keys(workerSpans)) {
      for (const p of workerSpans[w].polls) {
        if (p.cpuSamples) pollsWithCpuSamples++;
        if (p.schedSamples) pollsWithSchedSamples++;
      }
    }
    return { pollsWithCpuSamples, pollsWithSchedSamples };
  }

  /**
   * Build active task count timeline from spawn/terminate timestamps.
   * @param {Map<number, number>} taskSpawnTimes
   * @param {Map<number, number>} taskTerminateTimes
   * @returns {{ activeTaskSamples: Array<{t: number, count: number}>, taskFirstPoll: Map<number, number> }}
   */
  function buildActiveTaskTimeline(taskSpawnTimes, taskTerminateTimes) {
    const activeTaskSamples = [];
    const taskFirstPoll = new Map();
    if (taskSpawnTimes && taskSpawnTimes.size > 0) {
      const taskEvents = [];
      for (const [taskId, t] of taskSpawnTimes) {
        taskFirstPoll.set(taskId, t);
        taskEvents.push({ t, delta: 1 });
      }
      for (const [, t] of taskTerminateTimes) {
        taskEvents.push({ t, delta: -1 });
      }
      taskEvents.sort((a, b) => a.t - b.t);
      let count = 0;
      for (const te of taskEvents) {
        count += te.delta;
        activeTaskSamples.push({ t: te.t, count: Math.max(0, count) });
      }
    }
    return { activeTaskSamples, taskFirstPoll };
  }

  /**
   * Compute scheduling delays: for each poll, find the most recent wake before it.
   * Adjusts for mid-poll wake arrivals.
   * @param {Object} workerSpans - as returned by buildWorkerSpans
   * @param {number[]} workerIds
   * @param {Object} wakesByTask - as returned by buildWorkerSpans
   * @returns {Array<{wakeTime: number, pollTime: number, delay: number, taskId: number, wakerTaskId: number, worker: number, poll: Object}>}
   */
  function computeSchedulingDelays(workerSpans, workerIds, wakesByTask) {
    const pollsByTask = {};
    for (const w of workerIds) {
      for (const s of workerSpans[w].polls) {
        if (s.taskId) (pollsByTask[s.taskId] ??= []).push(s);
      }
    }
    for (const arr of Object.values(pollsByTask)) {
      arr.sort((a, b) => a.start - b.start);
    }

    const schedDelays = [];
    for (const w of workerIds) {
      for (const s of workerSpans[w].polls) {
        if (!s.taskId) continue;
        const wakes = wakesByTask[s.taskId];
        if (!wakes || !wakes.length) continue;
        let lo = 0,
          hi = wakes.length - 1,
          best = -1;
        while (lo <= hi) {
          const mid = (lo + hi) >> 1;
          if (wakes[mid].timestamp <= s.start) {
            best = mid;
            lo = mid + 1;
          } else hi = mid - 1;
        }
        if (best >= 0) {
          const wake = wakes[best];
          let effectiveWake = wake.timestamp;
          const taskPolls = pollsByTask[s.taskId];
          if (taskPolls) {
            for (const p of taskPolls) {
              if (p.start >= s.start) break;
              if (wake.timestamp >= p.start && wake.timestamp <= p.end) {
                effectiveWake = p.end;
                break;
              }
            }
          }
          const delay = s.start - effectiveWake;
          if (delay > 0 && delay < 1e9) {
            schedDelays.push({
              wakeTime: effectiveWake,
              pollTime: s.start,
              delay,
              taskId: s.taskId,
              wakerTaskId: wake.wakerTaskId,
              worker: w,
              poll: s,
            });
          }
        }
      }
    }
    schedDelays.sort((a, b) => a.wakeTime - b.wakeTime);
    return schedDelays;
  }

  /**
   * Filter and sort points of interest from worker spans and scheduling delays.
   * @param {string} filterType - "sched" | "long-poll" | "cpu-sampled" | "wake-delay"
   * @param {Object} workerSpans
   * @param {number[]} workerIds
   * @param {Array} schedDelays - as returned by computeSchedulingDelays
   * @param {boolean} hasSchedWait
   * @param {{ sortByWorst?: boolean }} opts
   * @returns {Array<{time: number, worker: number, type: string, value: number, span: Object, schedDelay?: Object}>}
   */
  function filterPointsOfInterest(
    filterType,
    workerSpans,
    workerIds,
    schedDelays,
    opts
  ) {
    const hasSchedWait = opts && opts.hasSchedWait;
    const points = [];

    for (const w of workerIds) {
      const spans = workerSpans[w];

      if (filterType === "sched") {
        for (const s of spans.parks) {
          if (hasSchedWait && s.schedWait > 100) {
            const wakeupShouldBe = s.end - s.schedWait;
            points.push({
              time: wakeupShouldBe,
              worker: w,
              type: "sched",
              value: s.schedWait,
              span: s,
            });
          }
        }
      } else if (filterType === "long-poll") {
        for (const s of spans.polls) {
          const durMs = (s.end - s.start) / 1e6;
          if (durMs > 1) {
            points.push({
              time: s.start,
              worker: w,
              type: "long-poll",
              value: durMs,
              span: s,
            });
          }
        }
      } else if (filterType === "cpu-sampled") {
        for (const s of spans.polls) {
          const cpuCount = s.cpuSamples ? s.cpuSamples.length : 0;
          const schedCount = s.schedSamples ? s.schedSamples.length : 0;
          if (cpuCount + schedCount > 0) {
            const durMs = (s.end - s.start) / 1e6;
            points.push({
              time: s.start,
              worker: w,
              type: "cpu-sampled",
              value: durMs,
              span: s,
            });
          }
        }
      }
    }

    if (filterType === "wake-delay") {
      for (const sd of schedDelays) {
        const delayUs = sd.delay / 1000;
        if (delayUs > 100) {
          points.push({
            time: sd.wakeTime,
            worker: sd.worker,
            type: "wake-delay",
            value: delayUs,
            span: sd.poll,
            schedDelay: sd,
          });
        }
      }
    }

    if (filterType === "uninstrumented" && opts && opts.taskInstrumented) {
      for (const w of workerIds) {
        for (const s of workerSpans[w].polls) {
          if (s.taskId && opts.taskInstrumented.get(s.taskId) === false) {
            points.push({
              time: s.start,
              worker: w,
              type: "uninstrumented",
              value: (s.end - s.start) / 1e6,
              span: s,
            });
          }
        }
      }
    }

    if (opts && opts.sortByWorst) {
      points.sort((a, b) => b.value - a.value);
    } else {
      points.sort((a, b) => a.time - b.time);
    }
    return points;
  }

  /**
   * Build a flamegraph tree from CPU samples with reversed callchains.
   * @param {import('./trace_parser.js').CpuSample[]} samples
   * @param {Map} callframeSymbols
   * @returns {{ name: string, children: Map, count: number, self: number }}
   */
  function buildFlamegraphTree(samples, callframeSymbols) {
    const root = { name: "(all)", children: new Map(), count: 0, self: 0 };
    for (const s of samples) {
      const w = s.weight != null ? s.weight : 1;
      const aw = s.allocWeight;
      const chain = s.callchain.slice().reverse();
      let node = root;
      node.count += w;
      if (aw != null) node.allocCount = (node.allocCount || 0) + aw;
      for (const addr of chain) {
        const entry = callframeSymbols.get(addr);
        // Expand inlined frames. Per blazesym, an array entry is ordered
        // [outermost, ..., innermost]: entry[0] is the real function at this
        // address, and entry[i>0] are inlined callees (entry[0] calls entry[1]
        // calls entry[2], etc.). To walk the call graph caller→callee while
        // descending the flamegraph tree, iterate 0 → N. Skip nullish slots
        // that can appear in sparse arrays (rare, but can happen if inline
        // SymbolTableEntry events arrive before their depth=0 sibling).
        const frames = Array.isArray(entry) ? entry : [entry];
        for (let fi = 0; fi < frames.length; fi++) {
          const resolved = frames[fi];
          if (fi > 0 && !resolved) continue;
          const key = resolved ? resolved.symbol : addr || "??";
          const formatted = resolved ? formatFrame(resolved) : formatFrame(addr, callframeSymbols);
          if (!node.children.has(key)) {
            node.children.set(key, {
              name: formatted.text,
              fullName: key,
              location: resolved ? resolved.location : null,
              docsUrl: formatted.docsUrl,
              children: new Map(),
              count: 0,
              self: 0,
            });
          }
          node = node.children.get(key);
          node.count += w;
          if (aw != null) node.allocCount = (node.allocCount || 0) + aw;
        }
      }
      node.self += w;
      if (aw != null) node.selfAllocCount = (node.selfAllocCount || 0) + aw;
    }
    return root;
  }

  /**
   * Flatten a flamegraph tree into drawable nodes, filtering out nodes < 0.1%.
   * @param {{ name: string, children: Map, count: number, self: number }} root
   * @param {number} total - total sample count
   * @returns {{ nodes: Array<{name: string, depth: number, x: number, w: number, count: number, self: number}>, maxDepth: number }}
   */
  function flattenFlamegraph(root, total) {
    const nodes = [];
    let maxD = 0;
    function walk(node, depth, xStart) {
      const w = node.count / total;
      if (w < 0.001) return;
      nodes.push({
        name: node.name,
        depth,
        x: xStart,
        w,
        count: node.count,
        self: node.self,
      });
      if (depth > maxD) maxD = depth;
      const kids = [...node.children.values()].sort(
        (a, b) => b.count - a.count
      );
      let cx = xStart;
      for (const child of kids) {
        walk(child, depth + 1, cx);
        cx += child.count / total;
      }
    }
    const kids = [...root.children.values()].sort(
      (a, b) => b.count - a.count
    );
    let cx = 0;
    for (const child of kids) {
      walk(child, 0, cx);
      cx += child.count / total;
    }
    return { nodes, maxDepth: maxD };
  }

  /**
   * Build flamegraph data from samples (convenience wrapper).
   * @param {import('./trace_parser.js').CpuSample[]} samples
   * @param {Map} callframeSymbols
   * @returns {{ nodes: Array, maxDepth: number, totalSamples: number } | null}
   */
  function buildFgData(samples, callframeSymbols) {
    if (!samples.length) return null;
    const tree = buildFlamegraphTree(samples, callframeSymbols);
    const result = flattenFlamegraph(tree, samples.length);
    return {
      nodes: result.nodes,
      maxDepth: result.maxDepth,
      totalSamples: samples.length,
    };
  }

  /**
   * Build span data structures from custom events.
   * Groups SpanEnter/SpanExit pairs into spans with segments (one per poll).
   * SpanCloseEvent finalizes a span and enables span ID recycling.
   * @param {Array<{name: string, timestamp: number, fields: Object}>} customEvents
   * @returns {{
   *   allSpans: Array<{start: number, end: number, spanId: string, spanName: string, fields: Object, parentSpanId: string|null, segments: Array<{start: number, end: number, workerId: number}>, activeNs: number, depth: number}>,
   *   spanMeta: Map<string, {spanName: string, fields: Object, parentSpanId: string|null}>,
   *   maxDepth: number,
   *   unmatchedSpans: Array<{start: number, spanId: string, workerId: number, spanName: string, fields: Object, parentSpanId: string|null}>,
   *   childrenByParent: Map<string|null, string[]>,
   * }}
   */
  function buildSpanData(customEvents) {
    // Events are only ordered within a single worker's stream. Cross-worker
    // interleaving can produce globally out-of-order timestamps, so we must
    // sort before processing to ensure close events are seen after all
    // enter/exit pairs that precede them in wall-clock time.
    customEvents = [...customEvents].sort((a, b) => a.timestamp - b.timestamp);
    // Key by span_id only — a span may be polled on different workers.
    const openEnters = new Map(); // spanId → {timestamp, workerId}
    // Live span records keyed by spanId. Moved to closedSpans on SpanClose.
    const spanMap = new Map(); // spanId → {spanName, fields, parentSpanId, segments}
    const closedSpans = []; // finalized span records (after SpanClose or end-of-trace)
    const spanMeta = new Map();

    const BASE_ENTER_FIELDS = new Set(["worker_id", "span_id", "parent_span_id", "span_name"]);
    const BASE_EXIT_FIELDS = new Set(["worker_id", "span_id", "span_name"]);

    function finalizeSpan(spanId) {
      const rec = spanMap.get(spanId);
      if (rec && rec.segments.length > 0) {
        closedSpans.push({ spanId, ...rec });
      }
      spanMap.delete(spanId);
    }

    for (const ev of customEvents) {
      if (ev.name.startsWith("SpanEnter:") || ev.name === "SpanEnterEvent") {
        const v = ev.fields;
        const workerId = Number(v.worker_id);
        const spanId = String(v.span_id);
        const parentSpanId = v.parent_span_id != null ? String(v.parent_span_id) : null;
        const spanName = v.span_name || "unknown";
        const fields = {};
        for (const [k, val] of Object.entries(v)) {
          if (!BASE_ENTER_FIELDS.has(k)) fields[k] = val;
        }

        // Guard: if this span already has an open enter (e.g. entered on a
        // different worker before exiting), skip to avoid losing the first enter.
        if (openEnters.has(spanId)) continue;

        openEnters.set(spanId, { timestamp: ev.timestamp, workerId });

        if (!spanMap.has(spanId)) {
          spanMap.set(spanId, { spanName, fields, parentSpanId, segments: [] });
        }
        spanMeta.set(spanId, { spanName, fields, parentSpanId });
      } else if (ev.name.startsWith("SpanExit:") || ev.name === "SpanExitEvent") {
        const v = ev.fields;
        const workerId = Number(v.worker_id);
        const spanId = String(v.span_id);

        const enter = openEnters.get(spanId);
        if (enter) {
          openEnters.delete(spanId);
          const exitFields = {};
          for (const [k, val] of Object.entries(v)) {
            if (!BASE_EXIT_FIELDS.has(k)) exitFields[k] = val;
          }
          let rec = spanMap.get(spanId);
          if (!rec) {
            rec = { spanName: v.span_name || "unknown", fields: {}, parentSpanId: null, segments: [] };
            spanMap.set(spanId, rec);
          }
          if (Object.keys(exitFields).length > 0) rec.fields = exitFields;
          rec.segments.push({ start: enter.timestamp, end: ev.timestamp, workerId });
        }
      } else if (ev.name === "SpanCloseEvent") {
        const spanId = String(ev.fields.span_id);
        openEnters.delete(spanId);
        finalizeSpan(spanId);
      }
    }

    // Finalize any spans still open at end of trace (no SpanClose seen)
    for (const [spanId] of spanMap) {
      finalizeSpan(spanId);
    }

    // Build allSpans
    const allSpans = [];
    for (const rec of closedSpans) {
      rec.segments.sort((a, b) => a.start - b.start);
      const start = rec.segments[0].start;
      const end = rec.segments[rec.segments.length - 1].end;
      const activeNs = rec.segments.reduce((sum, seg) => sum + (seg.end - seg.start), 0);
      allSpans.push({
        start, end,
        spanId: rec.spanId,
        spanName: rec.spanName,
        fields: rec.fields,
        parentSpanId: rec.parentSpanId,
        segments: rec.segments,
        activeNs,
      });
    }
    allSpans.sort((a, b) => a.start - b.start);

    // Unmatched: open enters with no segments
    const unmatchedSpans = [];
    for (const [spanId, enter] of openEnters) {
      unmatchedSpans.push({
        start: enter.timestamp,
        spanId,
        workerId: enter.workerId,
        spanName: spanMeta.get(spanId)?.spanName || "unknown",
        fields: spanMeta.get(spanId)?.fields || {},
        parentSpanId: spanMeta.get(spanId)?.parentSpanId ?? null,
      });
    }
    unmatchedSpans.sort((a, b) => a.start - b.start);

    // Compute depth via parent chain
    const depthCache = new Map();
    function getDepth(spanId, seen) {
      if (spanId == null) return -1;
      if (depthCache.has(spanId)) return depthCache.get(spanId);
      if (seen && seen.has(spanId)) { depthCache.set(spanId, 0); return 0; }
      const meta = spanMeta.get(spanId);
      if (!meta) { depthCache.set(spanId, 0); return 0; }
      const visited = seen || new Set();
      visited.add(spanId);
      const d = getDepth(meta.parentSpanId, visited) + 1;
      depthCache.set(spanId, d);
      return d;
    }
    let maxDepth = 0;
    for (const s of allSpans) {
      s.depth = getDepth(s.spanId);
      if (s.depth > maxDepth) maxDepth = s.depth;
    }

    // Build parent → children index.  Roots (parent == null) are stored under the null key.
    // Every closed span contributes exactly one entry to its parent's bucket; childless
    // spans have no bucket at all (callers must treat a missing key as empty).
    const childrenByParent = new Map();
    const addChild = (parentKey, childId) => {
      let arr = childrenByParent.get(parentKey);
      if (!arr) { arr = []; childrenByParent.set(parentKey, arr); }
      arr.push(childId);
    };
    for (const s of allSpans) {
      addChild(s.parentSpanId ?? null, s.spanId);
    }

    return { allSpans, spanMeta, maxDepth, unmatchedSpans, childrenByParent };
  }

  /**
   * Collect a set of span IDs containing the given seeds plus all their descendants.
   * Cycle-safe.
   * @param {string[]} seedIds
   * @param {Map<string|null, string[]>} childrenByParent
   * @returns {Set<string>}
   */
  function collectDescendants(seedIds, childrenByParent) {
    const result = new Set();
    const stack = [...seedIds];
    while (stack.length > 0) {
      const id = stack.pop();
      if (result.has(id)) continue;
      result.add(id);
      const children = childrenByParent.get(id);
      if (children) {
        for (const c of children) stack.push(c);
      }
    }
    return result;
  }

  /**
   * Select which spans to render based on focus state.
   * - No focus: return only root-like spans (parentSpanId is null or parent not in allSpans).
   * - Focused: return the focused span + all its descendants.
   * @param {{ allSpans: Array, focusedSpanId: string|null, childrenByParent: Map }} opts
   * @returns {Array}
   */
  function selectSpanRenderSet({ allSpans, focusedSpanId, childrenByParent }) {
    if (focusedSpanId != null) {
      const ids = collectDescendants([focusedSpanId], childrenByParent);
      return allSpans.filter(s => ids.has(s.spanId));
    }
    // Root view: spans whose parent is null or whose parent is not in the dataset
    const allIds = new Set(allSpans.map(s => s.spanId));
    return allSpans.filter(s => s.parentSpanId == null || !allIds.has(s.parentSpanId));
  }

  /**
   * Compute span panel layout with duration-based y and pixel-grid clustering.
   * @param {{ spans: Array, viewStart: number, viewEnd: number, drawW: number, panelH: number, clusterXPx: number, barH: number }} opts
   * @returns {{ buckets: Array<{spans: Array, representative: Object, x1: number, x2: number, y: number, h: number}> }}
   */
  function computeSpanLayout({ spans, viewStart, viewEnd, drawW, panelH, clusterXPx, barH }) {
    if (spans.length === 0) return { buckets: [], minDur: 0, maxDur: 0 };
    if (viewEnd === viewStart) return { buckets: [], minDur: 0, maxDur: 0 };

    const PAD_TOP = 2;
    const PAD_BOT = 2;
    const usableH = panelH - PAD_TOP - PAD_BOT - barH;

    // Compute duration for each span and find min/max log-duration
    const durations = spans.map(s => s.end - s.start);
    let minLog = Infinity, maxLog = -Infinity;
    const logs = durations.map(d => {
      const l = Math.log(Math.max(d, 1));
      if (l < minLog) minLog = l;
      if (l > maxLog) maxLog = l;
      return l;
    });
    const logRange = maxLog - minLog || 1;

    const nsToX = (ns) => ((ns - viewStart) / (viewEnd - viewStart)) * drawW;

    // Assign each span a y based on log-duration (longer → smaller y → higher)
    // and an x midpoint, then bucket by pixel grid.
    const grid = new Map(); // "cellX,cellY" → {spans[], bestIdx}
    for (let i = 0; i < spans.length; i++) {
      const s = spans[i];
      const normDur = (logs[i] - minLog) / logRange; // 0 = shortest, 1 = longest
      const y = PAD_TOP + (1 - normDur) * usableH;
      const xMid = nsToX((s.start + s.end) / 2);

      const cellX = Math.floor(xMid / clusterXPx);
      const cellY = Math.floor(y / (barH + 1));
      const key = cellX + "," + cellY;

      let cell = grid.get(key);
      if (!cell) {
        cell = { spans: [], bestIdx: i, y, xMin: xMid, xMax: xMid };
        grid.set(key, cell);
      }
      cell.spans.push(s);
      // Track representative as the longest span
      if (durations[i] > durations[cell.bestIdx]) cell.bestIdx = i;
      // Track x extent for drawing
      const x1 = nsToX(s.start);
      const x2 = nsToX(s.end);
      if (x1 < cell.xMin) cell.xMin = x1;
      if (x2 > cell.xMax) cell.xMax = x2;
    }

    // Convert grid cells to buckets
    const buckets = [];
    for (const cell of grid.values()) {
      const rep = spans[cell.bestIdx] || cell.spans[0];
      const repX1 = Math.max(0, nsToX(rep.start));
      const repX2 = Math.min(drawW, nsToX(rep.end));
      buckets.push({
        spans: cell.spans,
        representative: rep,
        x1: repX1,
        x2: repX2,
        y: cell.y,
        h: barH,
      });
    }

    return { buckets, minDur: Math.exp(minLog), maxDur: Math.exp(maxLog) };
  }

  /**
   * Analyze memory allocation and free events, including per-task attribution.
   *
   * ## Sampling rate → actual allocation conversion
   *
   * dial9 uses Poisson (geometric) byte sampling with mean gap `R`
   * (`sampleRateBytes`). An allocation of size `s` is sampled with probability:
   *
   *   P(sampled | size=s) = 1 - exp(-s / R)
   *
   * The unbiased per-sample weight (inverse probability) is:
   *
   *   **weight(s) = s / (1 - exp(-s / R))**
   *
   * Intuition:
   * - s << R: weight ≈ R  (small allocs rarely sampled; each represents ~R bytes)
   * - s >> R: weight ≈ s  (large allocs almost always sampled; represent themselves)
   * - s = R: weight ≈ 1.58R
   *
   * The estimated total allocation volume is Σ weight(s_i) over all samples.
   *
   * Default sampleRateBytes is 524288 (512 KiB).
   *
   * @param {Array<{timestamp: number, tid: number, size: number, addr: string, callchain: string[]}>} allocEvents
   * @param {Array<{timestamp: number, tid: number, addr: string, size: number, allocTimestampNs: number}>} freeEvents
   * @param {Object} [opts] - Optional parameters for per-task attribution
   * @param {Array} [opts.events] - Parsed trace events (PollStart/PollEnd with workerId+taskId)
   * @param {Map<number,number>} [opts.tidToWorker] - tid → workerId mapping from park/unpark events
   * @param {number} [opts.sampleRateBytes] - Mean bytes between samples (default 524288)
   * @param {Array<{timestamp: number, droppedAllocs: number, droppedFrees: number}>} [opts.memoryOverflows] - Ring buffer overflow events
   * @returns {{ topSites: Array<{callchain: string[], totalBytes: number, count: number, estimatedBytes: number}>,
   *             leaks: Array<{callchain: string[], size: number, timestamp: number, addr: string}>,
   *             perTask: Map<number, {sampledBytes: number, count: number, estimatedBytes: number}>,
   *             sampleRateBytes: number,
   *             summary: {totalAllocBytes: number, totalAllocCount: number, totalFreeCount: number, leakedBytes: number, leakedCount: number, estimatedTotalBytes: number} }}
   */
  function analyzeAllocations(allocEvents, freeEvents, opts) {
    const sampleRateBytes = (opts && opts.sampleRateBytes) || 524288;
    if (!allocEvents || !freeEvents) {
      return { topSites: [], leaks: [], perTask: new Map(), sampleRateBytes, summary: { totalAllocBytes: 0, totalAllocCount: 0, totalFreeCount: 0, leakedBytes: 0, leakedCount: 0, estimatedTotalBytes: 0, totalDroppedAllocs: 0, totalDroppedFrees: 0 } };
    }

    /** Unbiased weight for a sampled allocation of size s with rate R. */
    function allocWeight(s) {
      if (s <= 0) return 0;
      const ratio = s / sampleRateBytes;
      // For very large ratios, 1-exp(-ratio) ≈ 1, so weight ≈ s
      if (ratio > 50) return s;
      return s / (1 - Math.exp(-ratio));
    }

    const freedAddrs = new Set(freeEvents.map(f => f.addr + ":" + f.allocTimestampNs));

    // Top allocation sites by callchain
    const siteMap = new Map(); // callchain key → {callchain, totalBytes, count, estimatedBytes}
    for (const a of allocEvents) {
      const key = a.callchain.join(";");
      let site = siteMap.get(key);
      if (!site) { site = { callchain: a.callchain, totalBytes: 0, count: 0, estimatedBytes: 0 }; siteMap.set(key, site); }
      site.totalBytes += a.size;
      site.count++;
      site.estimatedBytes += allocWeight(a.size);
    }
    const topSites = [...siteMap.values()].sort((a, b) => b.estimatedBytes - a.estimatedBytes).slice(0, 10);

    // Leaks: allocs with no matching free
    const leaks = [];
    let leakedBytes = 0;
    for (const a of allocEvents) {
      if (!freedAddrs.has(a.addr + ":" + a.timestamp)) {
        leaks.push({ callchain: a.callchain, size: a.size, timestamp: a.timestamp, addr: a.addr });
        leakedBytes += a.size;
      }
    }

    const totalAllocBytes = allocEvents.reduce((sum, a) => sum + a.size, 0);
    const estimatedTotalBytes = allocEvents.reduce((sum, a) => sum + allocWeight(a.size), 0);

    // Per-task attribution via tid → workerId → taskId at timestamp
    const perTask = new Map(); // taskId → {sampledBytes, count, estimatedBytes}
    const events = opts && opts.events;
    const tidToWorker = opts && opts.tidToWorker;
    if (events && tidToWorker && allocEvents.length > 0) {
      // Build per-worker poll timeline: sorted list of {start, taskId}
      const workerPolls = new Map(); // workerId → [{start, taskId}] (sorted by start)
      for (let i = 0; i < events.length; i++) {
        const e = events[i];
        if (e.eventType === 0 && e.taskId) { // PollStart
          let arr = workerPolls.get(e.workerId);
          if (!arr) { arr = []; workerPolls.set(e.workerId, arr); }
          arr.push({ start: e.timestamp, taskId: e.taskId });
        }
      }

      // For each alloc, find which task was being polled on that worker at that time
      for (const a of allocEvents) {
        const workerId = tidToWorker.get(a.tid);
        if (workerId == null) continue; // non-worker thread allocation
        const polls = workerPolls.get(workerId);
        if (!polls || polls.length === 0) continue;

        // Binary search for the last PollStart with start <= a.timestamp
        let lo = 0, hi = polls.length - 1, best = -1;
        while (lo <= hi) {
          const mid = (lo + hi) >>> 1;
          if (polls[mid].start <= a.timestamp) { best = mid; lo = mid + 1; }
          else { hi = mid - 1; }
        }
        if (best < 0) continue;
        const taskId = polls[best].taskId;

        let entry = perTask.get(taskId);
        if (!entry) { entry = { sampledBytes: 0, count: 0, estimatedBytes: 0 }; perTask.set(taskId, entry); }
        entry.sampledBytes += a.size;
        entry.count++;
        entry.estimatedBytes += allocWeight(a.size);
      }
    }

    const overflows = (opts && opts.memoryOverflows) || [];
    const totalDroppedAllocs = overflows.reduce((sum, o) => sum + o.droppedAllocs, 0);
    const totalDroppedFrees = overflows.reduce((sum, o) => sum + o.droppedFrees, 0);

    return {
      topSites,
      leaks,
      perTask,
      sampleRateBytes,
      summary: {
        totalAllocBytes,
        totalAllocCount: allocEvents.length,
        totalFreeCount: freeEvents.length,
        leakedBytes,
        leakedCount: leaks.length,
        estimatedTotalBytes: Math.round(estimatedTotalBytes),
        totalDroppedAllocs,
        totalDroppedFrees,
      },
    };
  }

  // Export for both browser and Node.js
  const analysisExports = {
    buildWorkerSpans,
    attachCpuSamples,
    buildActiveTaskTimeline,
    computeSchedulingDelays,
    filterPointsOfInterest,
    buildFlamegraphTree,
    flattenFlamegraph,
    buildFgData,
    getTraceTimeRange,
    hasCpuProfileSamples,
    buildSpanData,
    collectDescendants,
    selectSpanRenderSet,
    computeSpanLayout,
    analyzeAllocations,
    pollHeatmapColor,
    pollHeatmapColorQuantized,
  };

  if (typeof module !== "undefined" && module.exports) {
    module.exports = analysisExports;
  } else {
    exports.TraceAnalysis = analysisExports;
  }
})(typeof exports === "undefined" ? this : exports);