Skip to content

Garry's Opinionated OpenClaw/Hermes Agent Brain

TypeScript
15.8 KB
Raw Blame
// sharding.test.ts — pure unit tests for the LPT bin-packer.
//
// Covers: happy path, fallback semantics, full coverage, determinism,
// balance ratio, N=1 trivial, weight-equal-to-zero handling, malformed
// weights, missing weights file fail-soft.

import { describe, expect, it } from "bun:test";
import {
  computeMedian,
  computeQuantile,
  formatPredictedWeight,
  imbalanceRatio,
  loadWeights,
  partition,
  predictedWeight,
  unitShards,
  WeightsLoadError,
  type WeightMap,
} from "../../scripts/sharding.ts";
import { mkdirSync, mkdtempSync, rmSync, writeFileSync } from "node:fs";
import { tmpdir } from "node:os";
import { join } from "node:path";

function tempJson(content: string): string {
  const dir = mkdtempSync(join(tmpdir(), "weights-test-"));
  const path = join(dir, "weights.json");
  writeFileSync(path, content, "utf8");
  return path;
}

describe("computeMedian", () => {
  it("returns 0 on empty input", () => {
    expect(computeMedian([])).toBe(0);
  });
  it("single value is itself", () => {
    expect(computeMedian([42])).toBe(42);
  });
  it("odd count: middle value", () => {
    expect(computeMedian([1, 5, 3])).toBe(3);
  });
  it("even count: mean of middle two", () => {
    expect(computeMedian([1, 2, 3, 4])).toBe(2.5);
  });
});

describe("partition — happy path", () => {
  it("balances 4 known-weight files across 2 shards", () => {
    const weights: WeightMap = new Map([
      ["a.test.ts", 100],
      ["b.test.ts", 100],
      ["c.test.ts", 50],
      ["d.test.ts", 50],
    ]);
    const out = partition(
      ["a.test.ts", "b.test.ts", "c.test.ts", "d.test.ts"],
      weights,
      2,
    );
    expect(out.length).toBe(2);
    // LPT assigns 100→s0, 100→s1, 50→s0 (now 150), 50→s1 (now 150).
    // Wait: 100→s0 (s0=100), 100→s1 (s1=100), tie → s0 gets 50 (s0=150),
    // then s1 gets 50 (s1=150). Balanced.
    const totals = out.map((s) =>
      s.reduce((acc, f) => acc + (weights.get(f) ?? 0), 0),
    );
    expect(totals[0]).toBe(150);
    expect(totals[1]).toBe(150);
  });

  it("LPT prefers heavy-first assignment", () => {
    // 3 files: 100, 10, 10. 2 shards. Naive assignment (alpha) would put
    // 100 + 10 = 110 in s0 and 10 in s1 (imbalance 11x). LPT puts 100 in
    // s0, then 10 + 10 in s1 (totals 100 + 20 = imbalance 5x).
    const weights: WeightMap = new Map([
      ["big.test.ts", 100],
      ["small1.test.ts", 10],
      ["small2.test.ts", 10],
    ]);
    const out = partition(
      ["big.test.ts", "small1.test.ts", "small2.test.ts"],
      weights,
      2,
    );
    expect(out[0]).toEqual(["big.test.ts"]);
    expect(out[1]?.sort()).toEqual(["small1.test.ts", "small2.test.ts"]);
  });
});

describe("partition — fallback semantics", () => {
  it("missing weights default to corpus p75 (missing files skew heavy)", () => {
    // weights = {a:100, b:50}, p75 (nearest-rank of [50,100] at 0.75) = 100.
    // Files c + d are unknown → 100 each.
    const weights: WeightMap = new Map([
      ["a", 100],
      ["b", 50],
    ]);
    const out = partition(["a", "b", "c", "d"], weights, 2);
    // Effective weights: a=100, b=50, c=100, d=100. Exact LPT placement of
    // ties is implementation-defined — assert the invariant instead: totals
    // differ by ≤ the fallback (the LPT bound), and every file landed once.
    const totalsEffective = out.map((s) =>
      s.reduce((acc, f) => acc + (weights.get(f) ?? 100), 0),
    );
    expect(Math.abs(totalsEffective[0]! - totalsEffective[1]!)).toBeLessThanOrEqual(100);
    const flat = out.flat().sort();
    expect(flat).toEqual(["a", "b", "c", "d"]);
  });

  it("computeQuantile: nearest-rank p75 on a skewed corpus", () => {
    // Right-skewed like the real weights file: p75 lands in the tail's
    // foothills, far above the median.
    expect(computeQuantile([1, 1, 1, 1000], 0.75)).toBe(1);
    expect(computeQuantile([1, 2, 3, 4], 0.75)).toBe(3);
    expect(computeQuantile([50, 100], 0.75)).toBe(100);
    expect(computeQuantile([], 0.75)).toBe(0);
  });

  it("explicit fallback override beats median", () => {
    const weights: WeightMap = new Map([["a", 100]]);
    const out = partition(["a", "unknown"], weights, 2, { fallbackWeight: 500 });
    // a=100 to s0, unknown=500 to s1 (heavier goes first actually — sort
    // desc puts unknown=500 first). Wait, LPT sorts desc, so unknown
    // (500) goes to s0 first, then a (100) goes to s1.
    expect(out[0]).toEqual(["unknown"]);
    expect(out[1]).toEqual(["a"]);
  });

  it("zero-weight files are valid (just always go to current min shard)", () => {
    const weights: WeightMap = new Map([
      ["zero1", 0],
      ["zero2", 0],
      ["big", 100],
    ]);
    const out = partition(["zero1", "zero2", "big"], weights, 2);
    // 100→s0=100, 0→s1=0, 0→s1=0. Both zeroes go to s1.
    expect(out[0]).toEqual(["big"]);
    expect(out[1]?.sort()).toEqual(["zero1", "zero2"]);
  });
});

describe("partition — invariants", () => {
  it("every input file lands in exactly one shard (full coverage)", () => {
    const files = Array.from({ length: 25 }, (_, i) => `f${i}.test.ts`);
    const weights: WeightMap = new Map(
      files.map((f, i) => [f, (i % 5) * 10 + 5]),
    );
    const out = partition(files, weights, 4);
    const seen: string[] = [];
    for (const shard of out) seen.push(...shard);
    expect(seen.sort()).toEqual([...files].sort());
    expect(new Set(seen).size).toBe(files.length);
  });

  it("deterministic — same input always produces same output", () => {
    const files = ["d.test.ts", "a.test.ts", "c.test.ts", "b.test.ts"];
    const weights: WeightMap = new Map([
      ["a.test.ts", 30],
      ["b.test.ts", 30],
      ["c.test.ts", 30],
      ["d.test.ts", 30],
    ]);
    const r1 = partition(files, weights, 2);
    const r2 = partition([...files].reverse(), weights, 2);
    const r3 = partition(files, weights, 2);
    // Same input → identical output
    expect(r3).toEqual(r1);
    // Input order shuffled but contents identical → identical output
    // (ties broken by path asc so order is canonical regardless of input)
    expect(r2).toEqual(r1);
  });

  it("N=1 trivial: everything in one shard", () => {
    const out = partition(["x.test.ts", "y.test.ts"], new Map(), 1);
    expect(out.length).toBe(1);
    expect(out[0]?.sort()).toEqual(["x.test.ts", "y.test.ts"]);
  });

  it("empty file list returns N empty shards", () => {
    const out = partition([], new Map(), 3);
    expect(out).toEqual([[], [], []]);
  });

  it("invalid shard count throws RangeError", () => {
    expect(() => partition(["a"], new Map(), 0)).toThrow(RangeError);
    expect(() => partition(["a"], new Map(), -1)).toThrow(RangeError);
    expect(() => partition(["a"], new Map(), 1.5)).toThrow(RangeError);
  });

  it("invalid fallbackWeight throws RangeError", () => {
    expect(() =>
      partition(["a"], new Map(), 2, { fallbackWeight: -1 }),
    ).toThrow(RangeError);
    expect(() =>
      partition(["a"], new Map(), 2, { fallbackWeight: NaN }),
    ).toThrow(RangeError);
  });
});

describe("partition — balance quality", () => {
  it("synthetic skewed corpus produces imbalance ratio ≤ 1.5", () => {
    // 100 files, weights drawn from a Zipf-ish distribution (a few heavy,
    // many light). This is the shape that broke FNV-1a hash sharding.
    const files = Array.from({ length: 100 }, (_, i) => `f${i}.test.ts`);
    const weights: WeightMap = new Map();
    for (let i = 0; i < files.length; i++) {
      // Heavy tail: file 0 = 1000ms, file 1 = 500, file 2 = 333, ...
      // Average about 50ms; max about 1000ms.
      const w = Math.max(10, Math.floor(1000 / (i + 1)));
      weights.set(files[i]!, w);
    }
    const out = partition(files, weights, 6);
    const ratio = imbalanceRatio(out, weights, 0);
    expect(ratio).toBeLessThanOrEqual(1.5);
  });

  it("imbalance ratio of 1.0 when weights are perfectly divisible", () => {
    const files = ["a", "b", "c", "d"];
    const weights: WeightMap = new Map([
      ["a", 50],
      ["b", 50],
      ["c", 50],
      ["d", 50],
    ]);
    const out = partition(files, weights, 2);
    expect(imbalanceRatio(out, weights, 0)).toBe(1.0);
  });
});

describe("loadWeights", () => {
  it("missing file → empty map (fail-soft)", () => {
    const w = loadWeights("/tmp/definitely-does-not-exist-weights.json");
    expect(w.size).toBe(0);
  });

  it("malformed JSON → throws WeightsLoadError", () => {
    const p = tempJson("not json {");
    try {
      expect(() => loadWeights(p)).toThrow(WeightsLoadError);
    } finally {
      rmSync(p.replace(/\/weights\.json$/, ""), { recursive: true, force: true });
    }
  });

  it("array JSON → throws (wrong shape)", () => {
    const p = tempJson("[1,2,3]");
    try {
      expect(() => loadWeights(p)).toThrow(/expected top-level object/);
    } finally {
      rmSync(p.replace(/\/weights\.json$/, ""), { recursive: true, force: true });
    }
  });

  it("negative weight → throws (semantic invalid)", () => {
    const p = tempJson('{"foo.test.ts": -5}');
    try {
      expect(() => loadWeights(p)).toThrow(/non-negative finite/);
    } finally {
      rmSync(p.replace(/\/weights\.json$/, ""), { recursive: true, force: true });
    }
  });

  it("non-number weight → throws (semantic invalid)", () => {
    const p = tempJson('{"foo.test.ts": "100ms"}');
    try {
      expect(() => loadWeights(p)).toThrow(/non-negative finite/);
    } finally {
      rmSync(p.replace(/\/weights\.json$/, ""), { recursive: true, force: true });
    }
  });

  it("valid weights JSON round-trips", () => {
    const p = tempJson('{"a.test.ts": 100, "b.test.ts": 250}');
    try {
      const w = loadWeights(p);
      expect(w.size).toBe(2);
      expect(w.get("a.test.ts")).toBe(100);
      expect(w.get("b.test.ts")).toBe(250);
    } finally {
      rmSync(p.replace(/\/weights\.json$/, ""), { recursive: true, force: true });
    }
  });
});

it('distributes a fully zero-weight corpus instead of concentrating it in shard 1', () => {
  const files = ['a', 'b', 'c', 'd'];
  expect(partition(files, new Map(files.map(f => [f, 0])), 4)).toEqual([['a'], ['b'], ['c'], ['d']]);
});

// #5669 — the CLI must flush its ENTIRE selection before exiting. With
// stdout a pipe (every shard consumer), `process.exit(code)` could
// terminate before pending writes drained: a 10,000-file selection
// delivered 8,187 paths at exit 0, so the wrapper ran a partial shard
// without knowing. The entry point now sets process.exitCode and lets the
// runtime drain. This spawns the real CLI, delays reading stdout (the
// condition that exposed the truncation), and requires the complete
// selection back.
describe("sharding CLI stdout flush (#5669)", () => {
  it("delivers every selected path when the reader is slow", async () => {
    const dir = mkdtempSync(join(tmpdir(), "shard-flush-"));
    const weights = join(dir, "weights.json");
    writeFileSync(weights, "{}", "utf8");
    const files = Array.from(
      { length: 10000 },
      (_, i) => `test/long-path-${i.toString().padStart(5, "0")}.test.ts`,
    );
    try {
      const child = Bun.spawn(
        [process.execPath, join(import.meta.dir, "../../scripts/sharding.ts"), "1", "1", "--weights", weights],
        { stdin: new TextEncoder().encode(files.join("\n") + "\n"), stdout: "pipe", stderr: "pipe" },
      );
      await Bun.sleep(100); // delay the reader — buffering exposes the truncation
      const [output, errors, code] = await Promise.all([
        new Response(child.stdout).text(),
        new Response(child.stderr).text(),
        child.exited,
      ]);
      const received = output.trim().split("\n").filter(Boolean);
      expect({ code, stderr: errors }).toEqual({ code: 0, stderr: "" });
      expect(received.sort()).toEqual([...files].sort());
    } finally {
      rmSync(dir, { recursive: true, force: true });
    }
  }, 60_000);

  // Bun.spawn's parent-side pipe drains eagerly on some Bun versions, which
  // hides the truncation above; a kernel pipe to a reader that sleeps before
  // its first read (the shell-wrapper shape) exposes it on Bun 1.3.14.
  it("delivers every selected path through a shell pipe whose reader starts late", async () => {
    const dir = mkdtempSync(join(tmpdir(), "shard-flush-sh-"));
    const weights = join(dir, "weights.json");
    const input = join(dir, "files.txt");
    writeFileSync(weights, "{}", "utf8");
    const files = Array.from({ length: 10000 }, (_, i) => `test/long-path-${i.toString().padStart(5, "0")}.test.ts`);
    writeFileSync(input, files.join("\n") + "\n", "utf8");
    try {
      const child = Bun.spawn(
        ["sh", "-c", '"$0" "$1" 1 1 --weights "$2" < "$3" | (sleep 1; cat)',
          process.execPath, join(import.meta.dir, "../../scripts/sharding.ts"), weights, input],
        { stdout: "pipe", stderr: "pipe" },
      );
      const [output, errors, code] = await Promise.all([
        new Response(child.stdout).text(),
        new Response(child.stderr).text(),
        child.exited,
      ]);
      expect({ code, stderr: errors }).toEqual({ code: 0, stderr: "" });
      expect(output.trim().split("\n").filter(Boolean).sort()).toEqual([...files].sort());
    } finally {
      rmSync(dir, { recursive: true, force: true });
    }
  }, 60_000);
});

// GBRA-79 — test-shard.sh prints each shard's predicted weight beside its
// "(LPT-balanced)" line so a measured time far above it reads as a runner or
// process-wide slowdown. The prediction must use the partition's own
// weights and p75 fallback, and the CLI's --sum must print the same line.
describe("predictedWeight / --sum", () => {
  const weights: WeightMap = new Map([
    ["test/a.test.ts", 4000],
    ["test/b.test.ts", 1000],
    ["test/c.test.ts", 2000],
    ["test/d.test.ts", 3000],
  ]);

  it("sums mined weights and gives unknown files the p75 fallback", () => {
    const p = predictedWeight(["test/a.test.ts", "test/b.test.ts", "test/new.test.ts"], weights);
    expect(p).toEqual({ totalMs: 4000 + 1000 + 3000, files: 3, unweighted: 1, fallbackMs: 3000 });
    expect(formatPredictedWeight(p)).toBe("predicted 8.0s over 3 files (1 unweighted at p75 3.0s)");
  });

  it("empty weights predict 1ms per file, matching partition's floor", () => {
    expect(predictedWeight(["x", "y"], new Map())).toEqual({ totalMs: 2, files: 2, unweighted: 2, fallbackMs: 1 });
  });

  it("the CLI prints the line for the file list on stdin and refuses positional shard arguments", async () => {
    const dir = mkdtempSync(join(tmpdir(), "shard-sum-"));
    const weightsPath = join(dir, "weights.json");
    writeFileSync(weightsPath, JSON.stringify(Object.fromEntries(weights)), "utf8");
    const cli = join(import.meta.dir, "../../scripts/sharding.ts");
    try {
      const ok = Bun.spawn([process.execPath, cli, "--sum", "--weights", weightsPath], {
        stdin: new TextEncoder().encode("test/a.test.ts\ntest/new.test.ts\n"), stdout: "pipe", stderr: "pipe",
      });
      const [out, err, code] = await Promise.all([new Response(ok.stdout).text(), new Response(ok.stderr).text(), ok.exited]);
      expect({ code, err, out }).toEqual({ code: 0, err: "", out: "predicted 7.0s over 2 files (1 unweighted at p75 3.0s)\n" });

      const bad = Bun.spawn([process.execPath, cli, "--sum", "1", "8", "--weights", weightsPath], {
        stdin: new TextEncoder().encode("test/a.test.ts\n"), stdout: "pipe", stderr: "pipe",
      });
      expect(await bad.exited).toBe(2);
    } finally {
      rmSync(dir, { recursive: true, force: true });
    }
  });
});

describe("unitShards", () => {
  it("names the signal when scripts/test-shard.sh is killed, as a bun test timeout does", () => {
    const root = mkdtempSync(join(tmpdir(), "unit-shards-test-"));
    try {
      mkdirSync(join(root, "scripts"));
      writeFileSync(join(root, "scripts", "test-shard.sh"), "kill -TERM $$\n");
      expect(() => unitShards(root, 1)).toThrow("scripts/test-shard.sh --dry-run-list 1 1 killed by SIGTERM: ");
    } finally {
      rmSync(root, { recursive: true, force: true });
    }
  });
});