Files
OmniRoute/scripts/merge-queue/bisect.mjs
diegosouzapw 95c72638ec fix(ci): omni-queue bisects a repeated job timeout instead of pausing
A job that hits its time limit on every attempt is a hanging test, not
the machine. When the infra retries are used up and every failure is
hang-shaped (timed_out, or cancelled with the maximum-execution-time
annotation; never runner loss, startup_failure or a plain cancel), the
tick records hang-suspected and classifies the hang signatures like any
red batch: base check when the base has no verdict, base-red pause when
the bare base fails the same job, otherwise bisection with hang: true,
whose timed-out segments are not retried. The culprit comment names the
job that timed out.

A base check that never produces a verdict (no CI run, or no result
after checksTimeoutMinutes) and has no retry left no longer pauses the
queue: it is recorded as a timeout verdict and the parked batch is
settled (pr-red, the check cannot be redone for the same SHA). The
verdict lookup for a later red batch accepts timeout, so no base check
is started again for that SHA.

A job timeout on the bare base is recorded as a hang signature of the
base check even next to other failures, so a batch that hangs on the
same job is matched to the base instead of being blamed.
2026-11-15 05:21:04 -03:00

108 lines
4.1 KiB
JavaScript

// scripts/merge-queue/bisect.mjs — WP3 (pure). Plan §3.5: isolate the culprit(s) of a red batch.
//
// Model: `segments` is the ordered list of PR groups still to validate; segments[0] is under
// test. Green → land it and test the next; red with 1 PR → culprit; red with > 1 → replace it
// by its two halves (first half = ceil(n/2), order preserved). Each segment is composed on the
// base AS IT IS when tested (landed segments included). Two culprits are found naturally.
//
// After a culprit is isolated, the segments still pending are MERGED back into one segment:
// the red verdicts that split them are already explained by the culprit, so the rest gets one
// candidate run instead of one per leftover half (a second culprit turns that run red and the
// bisection simply continues). A singleton is declared culprit only after its OWN red run —
// never inferred from a sibling — so one flaky run can never dequeue an innocent PR.
//
// Cost (candidate runs, the initial red batch included) for one culprit in a batch of n is at
// most 1 + 2·ceil(log2 n): 6 PRs → 5 to 7 runs, 8 PRs → 5 to 7 runs. Pinned by
// tests/unit/merge-queue/bisect.test.mjs.
/**
* @typedef {import("./contracts.mjs").PrRef} PrRef
* @typedef {import("./contracts.mjs").BisectState} BisectState
*/
const VERDICTS = Object.freeze(["green", "red"]);
/** @param {PrRef[]} prs @returns {[PrRef[], PrRef[]]} */
export function splitHalves(prs) {
if (!Array.isArray(prs) || prs.length < 2) {
throw new Error(`splitHalves: need at least 2 PRs, got ${Array.isArray(prs) ? prs.length : 0}`);
}
const cut = Math.ceil(prs.length / 2);
return [prs.slice(0, cut), prs.slice(cut)];
}
/**
* Start bisecting a red batch of size > 1.
* `hang`: the batch went red with a job timeout on every attempt (a suspected hanging test). The
* tick then does not retry a segment whose job times out again: every retry would cost a full
* timeout for a failure that already repeated. advanceBisection keeps the flag.
* @param {PrRef[]} batch
* @param {string} rootBatchId
* @param {{hang?: boolean}} [options]
* @returns {BisectState} segments = splitHalves(batch), steps = 0
*/
export function startBisection(batch, rootBatchId, { hang = false } = {}) {
if (typeof rootBatchId !== "string" || !rootBatchId) {
throw new Error("startBisection: rootBatchId is required");
}
return {
rootBatchId,
segments: splitHalves(batch),
culprits: [],
landed: [],
steps: 0,
hang: Boolean(hang),
};
}
/**
* Advance after segments[0] got a verdict. Never mutates its input.
* @param {BisectState} bisect
* @param {"green"|"red"} result
* @returns {{bisect: BisectState|null, land: PrRef[], culprit: PrRef|null, next: PrRef[]|null}}
* land = segment to land now (green), culprit = isolated PR (red singleton),
* next = segment to compose next (null and bisect=null when finished).
*/
export function advanceBisection(bisect, result) {
if (!VERDICTS.includes(result)) throw new Error(`advanceBisection: invalid result ${result}`);
if (!bisect || !Array.isArray(bisect.segments) || bisect.segments.length === 0) {
throw new Error("advanceBisection: no segment under test");
}
const [current, ...rest] = bisect.segments;
if (!Array.isArray(current) || current.length === 0) {
throw new Error("advanceBisection: empty segment under test");
}
let segments;
let land = [];
let culprit = null;
let landed = bisect.landed;
let culprits = bisect.culprits;
if (result === "green") {
land = current;
landed = [...landed, ...current.map((pr) => pr.n)];
segments = rest;
} else if (current.length === 1) {
culprit = current[0];
culprits = [...culprits, culprit];
const leftover = rest.flat();
segments = leftover.length ? [leftover] : [];
} else {
segments = [...splitHalves(current), ...rest];
}
if (segments.length === 0) return { bisect: null, land, culprit, next: null };
return {
bisect: {
...bisect,
segments,
culprits,
landed,
steps: bisect.steps + 1,
},
land,
culprit,
next: segments[0],
};
}