FAILURE MAP
← Case archive

FA-41156 / Heap invariants / Open access

Heap merge next winner may come from another run and returns its identity · case 01

The bounded run frontier certificate reports an incorrect next run.

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

ROOT CAUSE

Heap merge next winner may come from another run and returns its identity.

VERIFIED REPAIR

Derive next run using heads[0][1] if heads else None under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses heads[0][0] if heads else None 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': 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': r if out[r]<len(runs[r]) 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 fixtureActualExpectedOutcome
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': 0, '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': [[5, 0], [8, 1]], 'next_run': 1, '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': None, '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], [3, 1]], 'next_run': 1, '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 / 4af1f94f961d3ad0769f16a0a21c40075bccd5c7d6112909ef54f490a8cff731

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': 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][0] 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 fixtureActualExpectedOutcome
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': 2, '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': [[5, 0], [8, 1]], 'next_run': 5, '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': 3, '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], [3, 1]], 'next_run': 1, '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 / 0b8606eb7b15e6143f557ff5769eeedfbf928411bcb30945087c30fce96c208f

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 fixtureActualExpectedOutcome
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:38.169412+00:00.

Case digest / a382fcf956af0dc31891b4f918b108f13e30e1eda8f694e508c10febbd0d7021