FA-41141 / Heap invariants / Open access

Heap merge frontier refreshes each head from its post-pop cursor · case 01

The bounded run frontier certificate reports an incorrect heads.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Heap merge frontier refreshes each head from its post-pop cursor.

VERIFIED REPAIR

Derive heads using heads under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses sorted([[runs[i][k],i] for i,k in enumerate(offsets) if k<len(runs[i])]) and still violates the stated relation.

Case contract

A k-way heap merge frontier stores one cursor per sorted run. A frontier item identifies run r and its current offset. Pop run r current item, advance only its offset, omit exhausted runs, and report next head candidates sorted by (value,run). Return emitted value, cursor vector, heads, exhausted runs, remaining item count, and next run.

Why this case matters

This isolates an internal heap representation or priority-structure invariant using deterministic finite records.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': out,
    'heads': sorted([[runs[i][0],i] for i,k in enumerate(out) if k<len(runs[i])]),
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression certificate 1	`{'emitted': 1, 'exhausted': [0], 'heads': [], 'next_run': None, 'offsets': [1], 'remaining': 0}`	`{'emitted': 1, 'exhausted': [0], 'heads': [], 'next_run': None, 'offsets': [1], 'remaining': 0}`	Passed
regression certificate 2	`{'emitted': 1, 'exhausted': [], 'heads': [[1, 0], [2, 1]], 'next_run': 1, 'offsets': [1, 0], 'remaining': 3}`	`{'emitted': 1, 'exhausted': [], 'heads': [[2, 1], [3, 0]], 'next_run': 1, 'offsets': [1, 0], 'remaining': 3}`	Failed
regression certificate 3	`{'emitted': 4, 'exhausted': [], 'heads': [[1, 0], [2, 1]], 'next_run': 0, 'offsets': [1, 2], 'remaining': 3}`	`{'emitted': 4, 'exhausted': [], 'heads': [[5, 0], [8, 1]], 'next_run': 0, 'offsets': [1, 2], 'remaining': 3}`	Failed
regression certificate 4	`{'emitted': 2, 'exhausted': [0, 1], 'heads': [[3, 2]], 'next_run': 2, 'offsets': [2, 0, 0], 'remaining': 1}`	`{'emitted': 2, 'exhausted': [0, 1], 'heads': [[3, 2]], 'next_run': 2, 'offsets': [2, 0, 0], 'remaining': 1}`	Passed
regression certificate 5	`{'emitted': 1, 'exhausted': [], 'heads': [[1, 0], [1, 1]], 'next_run': 0, 'offsets': [0, 1], 'remaining': 3}`	`{'emitted': 1, 'exhausted': [], 'heads': [[1, 0], [3, 1]], 'next_run': 0, 'offsets': [0, 1], 'remaining': 3}`	Failed
regression certificate 6	`{'emitted': 3, 'exhausted': [0, 1], 'heads': [], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	`{'emitted': 3, 'exhausted': [0, 1], 'heads': [], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	Passed
variant-dependent certificate	`{'emitted': 4, 'exhausted': [0, 1], 'heads': [], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	`{'emitted': 4, 'exhausted': [0, 1], 'heads': [], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	Passed

SHA-256 / 242bec65effb8b28e487440ddab1773ae1f5afb371dfa4c008289469d53d8efb

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': out,
    'heads': sorted([[runs[i][k],i] for i,k in enumerate(offsets) if k<len(runs[i])]),
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression certificate 1	`{'emitted': 1, 'exhausted': [0], 'heads': [[1, 0]], 'next_run': None, 'offsets': [1], 'remaining': 0}`	`{'emitted': 1, 'exhausted': [0], 'heads': [], 'next_run': None, 'offsets': [1], 'remaining': 0}`	Failed
regression certificate 2	`{'emitted': 1, 'exhausted': [], 'heads': [[1, 0], [2, 1]], 'next_run': 1, 'offsets': [1, 0], 'remaining': 3}`	`{'emitted': 1, 'exhausted': [], 'heads': [[2, 1], [3, 0]], 'next_run': 1, 'offsets': [1, 0], 'remaining': 3}`	Failed
regression certificate 3	`{'emitted': 4, 'exhausted': [], 'heads': [[4, 1], [5, 0]], 'next_run': 0, 'offsets': [1, 2], 'remaining': 3}`	`{'emitted': 4, 'exhausted': [], 'heads': [[5, 0], [8, 1]], 'next_run': 0, 'offsets': [1, 2], 'remaining': 3}`	Failed
regression certificate 4	`{'emitted': 2, 'exhausted': [0, 1], 'heads': [[2, 0], [3, 2]], 'next_run': 2, 'offsets': [2, 0, 0], 'remaining': 1}`	`{'emitted': 2, 'exhausted': [0, 1], 'heads': [[3, 2]], 'next_run': 2, 'offsets': [2, 0, 0], 'remaining': 1}`	Failed
regression certificate 5	`{'emitted': 1, 'exhausted': [], 'heads': [[1, 0], [1, 1]], 'next_run': 0, 'offsets': [0, 1], 'remaining': 3}`	`{'emitted': 1, 'exhausted': [], 'heads': [[1, 0], [3, 1]], 'next_run': 0, 'offsets': [0, 1], 'remaining': 3}`	Failed
regression certificate 6	`{'emitted': 3, 'exhausted': [0, 1], 'heads': [[3, 0]], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	`{'emitted': 3, 'exhausted': [0, 1], 'heads': [], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	Failed
variant-dependent certificate	`{'emitted': 4, 'exhausted': [0, 1], 'heads': [[4, 0]], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	`{'emitted': 4, 'exhausted': [0, 1], 'heads': [], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	Failed

SHA-256 / d45888cbb1e3f418b59971c3e190bee858b604164ce6b33a189dfd645d8ec5b8

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(d):
    runs=d['runs']; offsets=d['offsets']; r=d['pop_run']; out=list(offsets); value=runs[r][out[r]]; out[r]+=1; heads=sorted([[runs[i][k],i] for i,k in enumerate(out) if k<len(runs[i])])
    return {'emitted': value,
    'offsets': out,
    'heads': heads,
    'exhausted': [i for i,k in enumerate(out) if k==len(runs[i])],
    'remaining': sum(len(x)-k for x,k in zip(runs,out)),
    'next_run': heads[0][1] if heads else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 4], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 4, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 5], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 5, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 6], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 6, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 7], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 7, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})], [({'runs': [[1]], 'offsets': [0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1], 'heads': [], 'exhausted': [0], 'remaining': 0, 'next_run': None}), ({'runs': [[1, 3], [2, 4]], 'offsets': [0, 0], 'pop_run': 0}, {'emitted': 1, 'offsets': [1, 0], 'heads': [[2, 1], [3, 0]], 'exhausted': [], 'remaining': 3, 'next_run': 1}), ({'runs': [[1, 5, 9], [2, 4, 8]], 'offsets': [1, 1], 'pop_run': 1}, {'emitted': 4, 'offsets': [1, 2], 'heads': [[5, 0], [8, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[1, 2], [], [3]], 'offsets': [1, 0, 0], 'pop_run': 0}, {'emitted': 2, 'offsets': [2, 0, 0], 'heads': [[3, 2]], 'exhausted': [0, 1], 'remaining': 1, 'next_run': 2}), ({'runs': [[1, 4], [1, 3]], 'offsets': [0, 0], 'pop_run': 1}, {'emitted': 1, 'offsets': [0, 1], 'heads': [[1, 0], [3, 1]], 'exhausted': [], 'remaining': 3, 'next_run': 0}), ({'runs': [[2, 3], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 3, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None}), ({'runs': [[2, 8], [1]], 'offsets': [1, 1], 'pop_run': 0}, {'emitted': 8, 'offsets': [2, 1], 'heads': [], 'exhausted': [0, 1], 'remaining': 0, 'next_run': None})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression certificate 1	`{'emitted': 1, 'exhausted': [0], 'heads': [], 'next_run': None, 'offsets': [1], 'remaining': 0}`	`{'emitted': 1, 'exhausted': [0], 'heads': [], 'next_run': None, 'offsets': [1], 'remaining': 0}`	Passed
regression certificate 2	`{'emitted': 1, 'exhausted': [], 'heads': [[2, 1], [3, 0]], 'next_run': 1, 'offsets': [1, 0], 'remaining': 3}`	`{'emitted': 1, 'exhausted': [], 'heads': [[2, 1], [3, 0]], 'next_run': 1, 'offsets': [1, 0], 'remaining': 3}`	Passed
regression certificate 3	`{'emitted': 4, 'exhausted': [], 'heads': [[5, 0], [8, 1]], 'next_run': 0, 'offsets': [1, 2], 'remaining': 3}`	`{'emitted': 4, 'exhausted': [], 'heads': [[5, 0], [8, 1]], 'next_run': 0, 'offsets': [1, 2], 'remaining': 3}`	Passed
regression certificate 4	`{'emitted': 2, 'exhausted': [0, 1], 'heads': [[3, 2]], 'next_run': 2, 'offsets': [2, 0, 0], 'remaining': 1}`	`{'emitted': 2, 'exhausted': [0, 1], 'heads': [[3, 2]], 'next_run': 2, 'offsets': [2, 0, 0], 'remaining': 1}`	Passed
regression certificate 5	`{'emitted': 1, 'exhausted': [], 'heads': [[1, 0], [3, 1]], 'next_run': 0, 'offsets': [0, 1], 'remaining': 3}`	`{'emitted': 1, 'exhausted': [], 'heads': [[1, 0], [3, 1]], 'next_run': 0, 'offsets': [0, 1], 'remaining': 3}`	Passed
regression certificate 6	`{'emitted': 3, 'exhausted': [0, 1], 'heads': [], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	`{'emitted': 3, 'exhausted': [0, 1], 'heads': [], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	Passed
variant-dependent certificate	`{'emitted': 4, 'exhausted': [0, 1], 'heads': [], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	`{'emitted': 4, 'exhausted': [0, 1], 'heads': [], 'next_run': None, 'offsets': [2, 1], 'remaining': 0}`	Passed

SHA-256 / e1deaab08db193e80909ff4c9a269bd947bd2cac8183ccefe539abe6c3697ad4

Verification & scope

A stipulated offline diagnostic model; it does not implement a production allocator, concurrency protocol, or complete heap library. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:43:37.966943+00:00.

Case digest / b43dbf10aab40c67498dbb1fc64868d65e9e4d2456213f8a9a53707983925b55