Something went wrong. Try again.
A functional toolkit for authoring resource-leveling algorithms — compose constraint and scoring blocks, enumerate feasible schedules
Something went wrong. Try again.
9.3 kB · 328 lines
TypeScript
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329import { describe, expect, test } from "bun:test";
import { GraphValidationError } from "../../src/level-blocks/compile.ts";import { fillRunConfig, runFromConfig,} from "../../src/level-blocks/runConfig.ts";import { STANDARD_CODES } from "../../src/level-blocks/standard.ts";import { expandSweep, expandSweepCells, SweepError,} from "../../src/level-blocks/sweep.ts";
import { MON_JAN_5, SAT_JAN_10, makeAssignment, makeProject, makeResource, makeTask,} from "../level-core/fixtures.ts";
function project() { return makeProject( [ makeTask({ uniqueId: 1, start: MON_JAN_5, finish: SAT_JAN_10 }), makeTask({ uniqueId: 2, start: MON_JAN_5, finish: SAT_JAN_10 }), ], { resources: [makeResource(100, "Crew"), makeResource(200, "Other")], assignments: [makeAssignment(1, 100), makeAssignment(2, 100)], }, );}
function configWithSweep() { return { formatVersion: 1 as const, objective: { lexicographic: ["makespan"] }, pipeline: { formatVersion: 1 as const, blocks: [ { instanceId: "cap-a", code: STANDARD_CODES.maxConcurrentResource, params: { resourceUniqueId: 100, max: 1 }, }, { instanceId: "cap-b", code: STANDARD_CODES.maxConcurrentResource, params: { resourceUniqueId: 200, max: 1 }, }, { instanceId: "makespan", code: STANDARD_CODES.makespan, params: {} }, { instanceId: "search", code: STANDARD_CODES.serialSGS, params: {} }, ], }, sweep: { maxCombinations: 8, axes: [ { id: "caps", targets: [ { instanceId: "cap-a", paramPath: "max", valueKey: "A" }, { instanceId: "cap-b", paramPath: "max", valueKey: "B" }, ], values: [ { A: 1, B: 2 }, { A: 2, B: 3 }, ], }, { id: "capBEnabled", targets: [{ instanceId: "cap-b", paramPath: "$enabled" }], values: [true, false], }, ], }, };}
describe("GridSweep expansion and validation", () => { test("expands zip and broadcast axes in odometer order without mutating the filled config", () => { const filled = fillRunConfig(configWithSweep()); const cells = expandSweepCells(filled); expect(cells.map((cell) => cell.point)).toEqual([ { caps: { A: 1, B: 2 }, capBEnabled: true }, { caps: { A: 1, B: 2 }, capBEnabled: false }, { caps: { A: 2, B: 3 }, capBEnabled: true }, { caps: { A: 2, B: 3 }, capBEnabled: false }, ]); expect( cells.map((cell) => cell.config.pipeline.blocks.slice(0, 2).map((block) => ({ max: block.params["max"], enabled: block.enabled, })), ), ).toEqual([ [ { max: 1, enabled: undefined }, { max: 2, enabled: true }, ], [ { max: 1, enabled: undefined }, { max: 2, enabled: false }, ], [ { max: 2, enabled: undefined }, { max: 3, enabled: true }, ], [ { max: 2, enabled: undefined }, { max: 3, enabled: false }, ], ]); expect(cells.every((cell) => cell.config.sweep === undefined)).toBe(true); expect(filled.sweep?.axes).toHaveLength(2); expect(expandSweep(filled)).toHaveLength(4); });
test("rejects incoherent zip axes, ragged records, bad paths, bad delivered values, and oversized grids", () => { const cases: [unknown, RegExp][] = [ [ { ...configWithSweep(), sweep: { axes: [ { id: "mixed", targets: [ { instanceId: "cap-a", paramPath: "max", valueKey: "A" }, { instanceId: "cap-b", paramPath: "max" }, ], values: [{ A: 1 }], }, ], }, }, /mixed.*mixes keyed and unkeyed/, ], [ { ...configWithSweep(), sweep: { axes: [ { id: "ragged", targets: [ { instanceId: "cap-a", paramPath: "max", valueKey: "A" }, ], values: [{ B: 1 }], }, ], }, }, /ragged.*missing valueKey "A"/, ], [ { ...configWithSweep(), sweep: { axes: [ { id: "badPath", targets: [{ instanceId: "cap-a", paramPath: "nope" }], values: [1], }, ], }, }, /badPath.*does not resolve/, ], [ { ...configWithSweep(), sweep: { axes: [ { id: "badValue", targets: [{ instanceId: "cap-a", paramPath: "max" }], values: [-1], }, ], }, }, /badValue.*invalid value/, ], [ { ...configWithSweep(), sweep: { maxCombinations: 2, axes: [ { id: "large", targets: [{ instanceId: "cap-a", paramPath: "max" }], values: [1, 2, 3], }, ], }, }, /3 combinations.*maxCombinations 2/, ], ];
for (const [config, message] of cases) { expect(() => fillRunConfig(config)).toThrow(message); expect(() => fillRunConfig(config)).toThrow(GraphValidationError); } });});
describe("GridSweep execution", () => { test("selects across cells and records the winning coordinate and sweep summary", async () => { const run = runFromConfig(project(), configWithSweep()); const best = (await run.best())!; expect(best.annotations.get("sweep.point")).toEqual({ caps: { A: 2, B: 3 }, capBEnabled: true, });
const provenance = run.materialize(best).levelset!; expect(provenance.sweep).toEqual({ combinations: 4, feasibleCells: 4, winner: { caps: { A: 2, B: 3 }, capBEnabled: true }, skipped: [], }); expect(provenance.runConfig).toEqual(run.config as never); });
test("uses each cell's compiled scorer parameters during cross-cell selection", async () => { const config = configWithSweep(); const blocks: { instanceId: string; code: string; params: Record<string, unknown>; }[] = config.pipeline.blocks; blocks.splice(2, 0, { instanceId: "cost", code: STANDARD_CODES.concurrentResourceCost, params: { resourceUniqueId: 100, basePrice: 10, growthBase: 2 }, }); const run = runFromConfig(project(), { ...config, objective: { lexicographic: ["cost"] }, sweep: { axes: [ { id: "price", targets: [{ instanceId: "cost", paramPath: "basePrice" }], values: [100, 1], }, ], }, }); const best = (await run.best())!; expect(best.annotations.get("sweep.point")).toEqual({ price: 1 }); expect(run.scores(best)["cost"]).toBeLessThan(100); });
test("throws SweepError after an all-infeasible grid", async () => { const base = configWithSweep(); const blocks: { instanceId: string; code: string; params: Record<string, unknown>; }[] = base.pipeline.blocks; blocks.splice(2, 0, { instanceId: "deadline", code: STANDARD_CODES.deadline, params: { taskUniqueId: 1, latestFinish: 20 }, }); const infeasible = { ...base, sweep: { axes: [ { id: "deadline", targets: [{ instanceId: "deadline", paramPath: "latestFinish" }], values: [0, 1], }, ], }, }; // bun-types declares `expect().rejects` as `Matchers<unknown>`, whose // methods return void — but they return a promise at runtime, so dropping // this await would let the test finish before the assertion resolves. // oxlint-disable-next-line typescript/await-thenable await expect( runFromConfig(project(), infeasible).best(), ).rejects.toBeInstanceOf(SweepError); });
test("skips and records an infeasible cell while retaining feasible candidates", async () => { const base = configWithSweep(); const blocks: { instanceId: string; code: string; params: Record<string, unknown>; }[] = base.pipeline.blocks; blocks.splice(2, 0, { instanceId: "deadline", code: STANDARD_CODES.deadline, params: { taskUniqueId: 1, latestFinish: 20 }, }); const run = runFromConfig(project(), { ...base, sweep: { axes: [ { id: "deadline", targets: [{ instanceId: "deadline", paramPath: "latestFinish" }], values: [1, 20], }, ], }, }); const best = (await run.best())!; expect(run.materialize(best).levelset!.sweep).toEqual({ combinations: 2, feasibleCells: 1, winner: { deadline: 20 }, skipped: [{ point: { deadline: 1 }, reason: "infeasible" }], }); });});