Skip to content

Garry's Opinionated OpenClaw/Hermes Agent Brain

TypeScript
15.8 KB
Raw Blame
#!/usr/bin/env bun
/**
 * scripts/sharding.ts — weight-aware test file partitioning.
 *
 * Replaces FNV-1a path-hash sharding in scripts/test-shard.sh. Uses
 * longest-processing-time-first (LPT) greedy bin-packing over measured
 * per-file runtimes to balance total wallclock across N shards.
 *
 * LPT is a textbook approximation algorithm: sort jobs by weight desc,
 * assign each to the bin (shard) with the current minimum total. Worst-
 * case makespan is within 4/3 of optimal. Runs in O(n log n).
 *
 * Weights live in scripts/test-weights.json — committed, mined from real
 * CI run logs via scripts/mine-shard-weights.ts. Files absent from the
 * weights map fall back to the corpus p75 (not zero — that would
 * favor unknown new files into the smallest shard, defeating balance).
 *
 * CLI:
 *   bun run scripts/sharding.ts <shard-index> <total-shards>
 *     Reads test file list from stdin (one path per line). Prints the
 *     subset assigned to <shard-index> to stdout, one per line.
 *
 *   bun run scripts/sharding.ts <shard-index> <total-shards> --weights <path>
 *     Uses lane-specific weights. --fallback-on-error warns and uses uniform
 *     weights if the advisory file is malformed (serial runner compatibility).
 *
 *   bun run scripts/sharding.ts --sum [--weights <path>]
 *     Read-only diagnostic: reads an already-partitioned file list from
 *     stdin and prints its predicted weight (the same per-file weights and
 *     p75 fallback `partition` uses) as one line, e.g.
 *     `predicted 412.3s over 401 files (37 unweighted at p75 1.2s)`.
 *     test-shard.sh prints it beside its "(LPT-balanced)" line so a shard
 *     whose measured time is far above the prediction points at the runner
 *     or a process-wide slowdown, not at the partition.
 *
 * Exit codes:
 *   0   success
 *   1   internal error (e.g., malformed weights JSON)
 *   2   usage error
 *
 * Used by: scripts/test-shard.sh (thin wrapper), test/scripts/sharding.test.ts.
 */

import { spawnSync } from "node:child_process";
import { readFileSync, existsSync } from "node:fs";
import { resolve, dirname, join } from "node:path";
import { fileURLToPath } from "node:url";

const __dirname = dirname(fileURLToPath(import.meta.url));
const REPO_ROOT = resolve(__dirname, "..");
const DEFAULT_WEIGHTS_PATH = resolve(REPO_ROOT, "scripts/test-weights.json");

/**
 * test.yml's unit matrix size, also e2e.yml's coverage-full-unit matrix;
 * test/scripts/unit-shard-budget.test.ts pins both workflows to it.
 */
export const UNIT_SHARDS = 36;
/** Unit shards each test.yml `test` job runs at once (scripts/test-shard-pack.sh); test/scripts/ci-gates.test.ts pins the matrix to it. */
export const UNIT_SHARDS_PER_JOB = 2;
/** test.yml's `test` job `timeout-minutes: 22`: the only bound on a unit shard, its setup steps included. */
export const UNIT_JOB_TIMEOUT_MS = 22 * 60 * 1000;
/** The job's steps before the shard (checkout, Bun, cache restores, install): 10-20 s measured on a warm cache. */
export const UNIT_SETUP_ALLOWANCE_MS = 60 * 1000;
/**
 * A unit shard's mined weight may be at most this: on a runner twice as slow
 * as the mined weights (master shards ran 0.8-1.4x their prediction, and one
 * cancelled at the timeout) it still ends a minute inside the job timeout
 * after setup.
 */
export const UNIT_SHARD_BUDGET_MS = (UNIT_JOB_TIMEOUT_MS - UNIT_SETUP_ALLOWANCE_MS - 60_000) / 2;

/** Each unit shard's files as test.yml runs them: scripts/test-shard.sh's own discovery and partition. */
export function unitShards(root: string, n: number = UNIT_SHARDS): string[][] {
  return Array.from({ length: n }, (_, i) => {
    const r = spawnSync("bash", [join(root, "scripts/test-shard.sh"), "--dry-run-list", String(i + 1), String(n)], { cwd: root, encoding: "utf8" });
    if (r.status !== 0) throw new Error(`scripts/test-shard.sh --dry-run-list ${i + 1} ${n} ${r.signal ? `killed by ${r.signal}` : "failed"}: ${r.stderr}`);
    return r.stdout.split("\n").filter(Boolean);
  });
}

export type WeightMap = Map<string, number>;

/**
 * test.yml's unit partition with each shard's mined weight (`root`'s scripts/test-weights.json): the plan
 * test/scripts/unit-shard-budget.test.ts and the ci:ubicloud gate both hold to UNIT_SHARD_BUDGET_MS.
 */
export function unitShardPlan(root: string): { shard: number; files: string[]; ms: number }[] {
  const weights = loadWeights(join(root, "scripts/test-weights.json"));
  return unitShards(root).map((files, i) => ({ shard: i + 1, files, ms: Math.round(predictedWeight(files, weights).totalMs) }));
}

export class WeightsLoadError extends Error {
  constructor(public readonly path: string, public readonly cause: unknown) {
    super(`failed to load weights from ${path}: ${cause}`);
    this.name = "WeightsLoadError";
  }
}

/**
 * Read a weights JSON file. Fail-soft on missing file (returns empty map).
 * Throws WeightsLoadError on malformed JSON or non-object shape — the
 * caller decides whether to fall through to defaults or surface.
 */
export function loadWeights(path: string = DEFAULT_WEIGHTS_PATH): WeightMap {
  if (!existsSync(path)) {
    console.error(`warning: weights missing at ${path}; using uniform fallback weights`);
    return new Map();
  }
  let raw: string;
  try {
    raw = readFileSync(path, "utf8");
  } catch (e) {
    throw new WeightsLoadError(path, e);
  }
  let parsed: unknown;
  try {
    parsed = JSON.parse(raw);
  } catch (e) {
    throw new WeightsLoadError(path, `JSON.parse: ${e}`);
  }
  if (typeof parsed !== "object" || parsed === null || Array.isArray(parsed)) {
    throw new WeightsLoadError(path, "expected top-level object {path: ms}");
  }
  const out: WeightMap = new Map();
  for (const [k, v] of Object.entries(parsed as Record<string, unknown>)) {
    if (typeof v !== "number" || !Number.isFinite(v) || v < 0) {
      throw new WeightsLoadError(
        path,
        `value for "${k}" must be a non-negative finite number, got ${JSON.stringify(v)}`,
      );
    }
    out.set(k, v);
  }
  return out;
}

/**
 * Median of a list of numbers. Used as the fallback weight for files
 * absent from the weights map. Empty input returns 0 (no signal).
 */
export function computeMedian(values: number[]): number {
  if (values.length === 0) return 0;
  const sorted = [...values].sort((a, b) => a - b);
  const mid = Math.floor(sorted.length / 2);
  return sorted.length % 2 === 0
    ? (sorted[mid - 1]! + sorted[mid]!) / 2
    : sorted[mid]!;
}

/**
 * Quantile (nearest-rank) of a list of numbers. Empty input returns 0.
 * q in [0, 1]; q=0.75 is the missing-file fallback weight (see partition).
 */
export function computeQuantile(values: number[], q: number): number {
  if (values.length === 0) return 0;
  const sorted = [...values].sort((a, b) => a - b);
  const idx = Math.min(sorted.length - 1, Math.max(0, Math.ceil(q * sorted.length) - 1));
  return sorted[idx]!;
}

export interface PartitionOpts {
  /**
   * Weight to assign files that are absent from the weights map. Defaults
   * to the p75 of present weights (computed inside `partition`) so
   * unknown new files cluster around the typical file's cost.
   *
   * Override mainly for tests; production callers should use the default.
   */
  fallbackWeight?: number;
}

/**
 * Partition `files` into `n` shards using LPT greedy bin-packing.
 *
 * Returns an array of length `n` where each entry is the (deterministic)
 * file list for that shard. Files in each shard are returned in
 * assignment order (heaviest first). Same input always produces same
 * output — no Math.random, stable sort key (weight desc, then path asc).
 *
 * Contracts:
 *   - Every file in `files` appears in exactly one returned shard.
 *   - If `files` is empty, returns `n` empty arrays.
 *   - If `n <= 0`, throws RangeError.
 *   - Files missing from `weights` get `opts.fallbackWeight` (or p75).
 */
export function partition(
  files: string[],
  weights: WeightMap,
  n: number,
  opts: PartitionOpts = {},
): string[][] {
  if (!Number.isInteger(n) || n <= 0) {
    throw new RangeError(`shard count must be a positive integer, got ${n}`);
  }
  const shards: string[][] = Array.from({ length: n }, () => []);
  if (files.length === 0) return shards;

  // Compute fallback weight from the p75 of present weights, unless the
  // caller supplied an explicit override. p75, not median: the weight
  // distribution is extremely right-skewed (median ~27ms, mean ~800ms —
  // most files are trivial greps, the tail boots PGLite), and files
  // MISSING from the map skew heavy (new integration tests land unweighted
  // more often than new pure-unit tests). A median fallback modeled 45% of
  // the corpus at ~30ms and let one shard silently carry the unweighted
  // heavies; p75 over-weights small new files slightly (harmless — LPT
  // self-corrects on the next mine) instead of under-weighting big ones.
  let fallback: number;
  if (opts.fallbackWeight !== undefined) {
    if (!Number.isFinite(opts.fallbackWeight) || opts.fallbackWeight < 0) {
      throw new RangeError(
        `fallbackWeight must be non-negative finite, got ${opts.fallbackWeight}`,
      );
    }
    fallback = opts.fallbackWeight;
  } else {
    fallback = computeQuantile(Array.from(weights.values()), 0.75);
  }
  // Keep a nonzero estimate for unknown files until timings are available.
  // Equal-load file-count ties also distribute explicitly zero-valued weights.
  if (fallback === 0 && opts.fallbackWeight === undefined) {
    fallback = 1;
  }

  // Build [weight, path] tuples. Sort by weight desc, then path asc for
  // determinism on ties (multiple files with the same weight).
  const tuples = files.map((f) => ({
    path: f,
    weight: weights.get(f) ?? fallback,
  }));
  tuples.sort((a, b) => {
    if (b.weight !== a.weight) return b.weight - a.weight;
    return a.path < b.path ? -1 : a.path > b.path ? 1 : 0;
  });

  // Equal loads prefer fewer files, then lowest index. In particular, measured
  // zero-duration files must not all collapse into the first shard.
  const totals = new Array<number>(n).fill(0);
  for (const t of tuples) {
    let minIdx = 0;
    for (let i = 1; i < n; i++) {
      if (totals[i]! < totals[minIdx]! ||
          (totals[i] === totals[minIdx] && shards[i]!.length < shards[minIdx]!.length)) minIdx = i;
    }
    shards[minIdx]!.push(t.path);
    totals[minIdx] = totals[minIdx]! + t.weight;
  }
  return shards;
}

/**
 * Imbalance ratio: max-total / min-total over the partition. 1.0 = perfect.
 * Returns Infinity when any shard is empty (degenerate). Use ≤1.5 as a
 * loose health gate; LPT typically hits ≤1.1 on real corpora.
 *
 * Exposed for tests + the slow-test regression that pins corpus health.
 */
export function imbalanceRatio(shards: string[][], weights: WeightMap, fallback: number): number {
  if (shards.length === 0) return 1;
  const totals = shards.map((s) =>
    s.reduce((sum, f) => sum + (weights.get(f) ?? fallback), 0),
  );
  const max = Math.max(...totals);
  const min = Math.min(...totals);
  if (min === 0) return max === 0 ? 1 : Infinity;
  return max / min;
}

/**
 * Predicted weight of an already-partitioned file list: the sum of each
 * file's mined weight, with the same p75 fallback `partition` assigns to
 * files absent from the map. Read-only over the weights.
 */
export function predictedWeight(
  files: string[],
  weights: WeightMap,
): { totalMs: number; files: number; unweighted: number; fallbackMs: number } {
  let fallbackMs = computeQuantile(Array.from(weights.values()), 0.75);
  if (fallbackMs === 0) fallbackMs = 1;
  let totalMs = 0;
  let unweighted = 0;
  for (const f of files) {
    const w = weights.get(f);
    if (w === undefined) unweighted++;
    totalMs += w ?? fallbackMs;
  }
  return { totalMs, files: files.length, unweighted, fallbackMs };
}

export function formatPredictedWeight(p: ReturnType<typeof predictedWeight>): string {
  const s = (ms: number) => `${(ms / 1000).toFixed(1)}s`;
  return `predicted ${s(p.totalMs)} over ${p.files} files (${p.unweighted} unweighted at p75 ${s(p.fallbackMs)})`;
}

// ──────────────────────────────────────────────────────────────────────────
// CLI
// ──────────────────────────────────────────────────────────────────────────

async function readStdinLines(): Promise<string[]> {
  // Bun gives us a readable stream on process.stdin. Read to end.
  if (process.stdin.isTTY) return []; // no piped input
  const chunks: Buffer[] = [];
  for await (const chunk of process.stdin) {
    chunks.push(typeof chunk === "string" ? Buffer.from(chunk) : chunk);
  }
  const text = Buffer.concat(chunks).toString("utf8");
  return text
    .split("\n")
    .map((l) => l.trim())
    .filter((l) => l.length > 0);
}

async function main(): Promise<number> {
  const argv = process.argv.slice(2);
  const positional: string[] = [];
  let weightsPath: string | undefined;
  let fallbackOnError = false;
  let sumOnly = false;
  for (let i = 0; i < argv.length; i++) {
    const arg = argv[i]!;
    if (arg === "--weights" && argv[i + 1] && !argv[i + 1]!.startsWith("--")) weightsPath = argv[++i];
    else if (arg === "--fallback-on-error") fallbackOnError = true;
    else if (arg === "--sum") sumOnly = true;
    else if (arg.startsWith("--")) {
      console.error(`error: unknown or incomplete option ${arg}`);
      return 2;
    } else positional.push(arg);
  }
  if (sumOnly) {
    if (positional.length !== 0) {
      console.error("usage: bun run scripts/sharding.ts --sum [--weights PATH]  (reads the shard's file list from stdin)");
      return 2;
    }
    let weights: WeightMap;
    try {
      weights = loadWeights(weightsPath);
    } catch (e) {
      console.error(`${fallbackOnError ? "warning" : "error"}: ${e instanceof Error ? e.message : String(e)}`);
      if (!fallbackOnError) return 1;
      weights = new Map();
    }
    process.stdout.write(`${formatPredictedWeight(predictedWeight(await readStdinLines(), weights))}\n`);
    return 0;
  }
  if (positional.length !== 2) {
    console.error("usage: bun run scripts/sharding.ts <shard-index> <total-shards> [--weights PATH] [--fallback-on-error]");
    console.error("       bun run scripts/sharding.ts --sum [--weights PATH]");
    console.error("       (reads file list from stdin, one path per line)");
    return 2;
  }
  const idx = Number(positional[0]);
  const total = Number(positional[1]);
  if (!positional.every((v) => /^[0-9]+$/.test(v)) || !Number.isSafeInteger(idx) || !Number.isSafeInteger(total) || idx < 1 || total < 1 || idx > total) {
    console.error(
      `error: shard index ${positional[0]} / total ${positional[1]} invalid (need 1 <= index <= total, both ints)`,
    );
    return 2;
  }
  const files = await readStdinLines();
  if (files.length === 0) {
    // Caller asked for a shard but piped no files. Exit clean — the wrapper
    // will warn or no-op as it sees fit.
    return 0;
  }
  let weights: WeightMap;
  try {
    weights = loadWeights(weightsPath);
  } catch (e) {
    console.error(`${fallbackOnError ? "warning" : "error"}: ${e instanceof Error ? e.message : String(e)}`);
    if (!fallbackOnError) return 1;
    weights = new Map();
  }
  const shards = partition(files, weights, total);
  for (const f of shards[idx - 1]!) {
    process.stdout.write(`${f}\n`);
  }
  return 0;
}

if (import.meta.main) {
  // #5669: set exitCode and let the runtime drain instead of process.exit().
  // With stdout a PIPE (test-shard.sh / run-unit-shard.sh / the serial pool
  // all consume this CLI), process.exit() can terminate before the pending
  // writes flush — a 10,000-file selection delivered 8,187 paths at exit 0,
  // so the wrapper ran a partial shard without knowing. Setting exitCode
  // keeps the codes identical while the event loop flushes stdout first.
  main().then((code) => { process.exitCode = code; });
}