FAILURE MAP
← Case archive

FA-41106 / Heap invariants / Open access

Buffered heap flush performs a global key-and-identity merge · case 01

The bounded buffered flush certificate reports an incorrect resident.

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

ROOT CAUSE

Buffered heap flush performs a global key-and-identity merge.

VERIFIED REPAIR

Derive resident using merged if flush else h under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses sorted(h+b,key=lambda x:x[1]) if flush else h and still violates the stated relation.

Case contract

A buffered priority heap has sorted resident entries [id,key] and unsorted insertion buffer of unique ids disjoint from residents. Flush only when buffer length reaches capacity; then merge all records ordered by key then id. Report triggering flag, resident after flush, buffer after flush, visible minimum across both tiers, logical size, and write count of promoted buffer entries.

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):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': flush,
    'resident': h+sorted(b,key=lambda x:x[1]) if flush else h,
    'buffer': [] if flush else b,
    'minimum': merged[0][1] if merged else None,
    'size': len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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{'buffer': [], 'minimum': None, 'resident': [], 'size': 0, 'trigger': False, 'writes': 0}{'buffer': [], 'minimum': None, 'resident': [], 'size': 0, 'trigger': False, 'writes': 0}Passed
regression certificate 2{'buffer': [['b', 1]], 'minimum': 1, 'resident': [['a', 5]], 'size': 2, 'trigger': False, 'writes': 0}{'buffer': [['b', 1]], 'minimum': 1, 'resident': [['a', 5]], 'size': 2, 'trigger': False, 'writes': 0}Passed
regression certificate 3{'buffer': [], 'minimum': 2, 'resident': [['a', 5], ['b', 7], ['c', 2], ['d', 6]], 'size': 4, 'trigger': True, 'writes': 2}{'buffer': [], 'minimum': 2, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'size': 4, 'trigger': True, 'writes': 2}Failed
regression certificate 4{'buffer': [], 'minimum': 3, 'resident': [['z', 3], ['y', 3], ['x', 3]], 'size': 3, 'trigger': True, 'writes': 2}{'buffer': [], 'minimum': 3, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'size': 3, 'trigger': True, 'writes': 2}Failed
regression certificate 5{'buffer': [], 'minimum': 2, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'size': 3, 'trigger': True, 'writes': 3}{'buffer': [], 'minimum': 2, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'size': 3, 'trigger': True, 'writes': 3}Passed
regression certificate 6{'buffer': [], 'minimum': 1, 'resident': [['a', 1], ['b', 3]], 'size': 2, 'trigger': True, 'writes': 1}{'buffer': [], 'minimum': 1, 'resident': [['a', 1], ['b', 3]], 'size': 2, 'trigger': True, 'writes': 1}Passed
variant-dependent certificate{'buffer': [], 'minimum': 0, 'resident': [['a', 1], ['100', 0], ['b', 3]], 'size': 3, 'trigger': True, 'writes': 2}{'buffer': [], 'minimum': 0, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'size': 3, 'trigger': True, 'writes': 2}Failed

SHA-256 / 1e8aac1eb7d9043f739223e983f0f90e9942b86685f1592a504dff53af701849

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': flush,
    'resident': sorted(h+b,key=lambda x:x[1]) if flush else h,
    'buffer': [] if flush else b,
    'minimum': merged[0][1] if merged else None,
    'size': len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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{'buffer': [], 'minimum': None, 'resident': [], 'size': 0, 'trigger': False, 'writes': 0}{'buffer': [], 'minimum': None, 'resident': [], 'size': 0, 'trigger': False, 'writes': 0}Passed
regression certificate 2{'buffer': [['b', 1]], 'minimum': 1, 'resident': [['a', 5]], 'size': 2, 'trigger': False, 'writes': 0}{'buffer': [['b', 1]], 'minimum': 1, 'resident': [['a', 5]], 'size': 2, 'trigger': False, 'writes': 0}Passed
regression certificate 3{'buffer': [], 'minimum': 2, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'size': 4, 'trigger': True, 'writes': 2}{'buffer': [], 'minimum': 2, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'size': 4, 'trigger': True, 'writes': 2}Passed
regression certificate 4{'buffer': [], 'minimum': 3, 'resident': [['z', 3], ['y', 3], ['x', 3]], 'size': 3, 'trigger': True, 'writes': 2}{'buffer': [], 'minimum': 3, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'size': 3, 'trigger': True, 'writes': 2}Failed
regression certificate 5{'buffer': [], 'minimum': 2, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'size': 3, 'trigger': True, 'writes': 3}{'buffer': [], 'minimum': 2, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'size': 3, 'trigger': True, 'writes': 3}Passed
regression certificate 6{'buffer': [], 'minimum': 1, 'resident': [['a', 1], ['b', 3]], 'size': 2, 'trigger': True, 'writes': 1}{'buffer': [], 'minimum': 1, 'resident': [['a', 1], ['b', 3]], 'size': 2, 'trigger': True, 'writes': 1}Passed
variant-dependent certificate{'buffer': [], 'minimum': 0, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'size': 3, 'trigger': True, 'writes': 2}{'buffer': [], 'minimum': 0, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'size': 3, 'trigger': True, 'writes': 2}Passed

SHA-256 / 13c7e16e414877380ff5e042ca32f7deec7ef6b3ca133287b681bceef2f6b012

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    h=d['heap']; b=d['buffer']; cap=d['capacity']; flush=len(b)>=cap; merged=sorted(h+b,key=lambda x:(x[1],x[0]))
    return {'trigger': flush,
    'resident': merged if flush else h,
    'buffer': [] if flush else b,
    'minimum': merged[0][1] if merged else None,
    'size': len(h)+len(b),
    'writes': len(b) if flush else 0}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 3, 'writes': 2})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 4, 'writes': 3})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 5, 'writes': 4})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3]], 'buffer': [], 'minimum': 0, 'size': 6, 'writes': 5})], [({'heap': [], 'buffer': [], 'capacity': 2}, {'trigger': False, 'resident': [], 'buffer': [], 'minimum': None, 'size': 0, 'writes': 0}), ({'heap': [['a', 5]], 'buffer': [['b', 1]], 'capacity': 2}, {'trigger': False, 'resident': [['a', 5]], 'buffer': [['b', 1]], 'minimum': 1, 'size': 2, 'writes': 0}), ({'heap': [['a', 5], ['b', 7]], 'buffer': [['d', 6], ['c', 2]], 'capacity': 2}, {'trigger': True, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'buffer': [], 'minimum': 2, 'size': 4, 'writes': 2}), ({'heap': [['z', 3]], 'buffer': [['y', 3], ['x', 3]], 'capacity': 2}, {'trigger': True, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'buffer': [], 'minimum': 3, 'size': 3, 'writes': 2}), ({'heap': [], 'buffer': [['a', 8], ['b', 2], ['c', 4]], 'capacity': 2}, {'trigger': True, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'buffer': [], 'minimum': 2, 'size': 3, 'writes': 3}), ({'heap': [['a', 1]], 'buffer': [['b', 3]], 'capacity': 1}, {'trigger': True, 'resident': [['a', 1], ['b', 3]], 'buffer': [], 'minimum': 1, 'size': 2, 'writes': 1}), ({'heap': [['a', 1]], 'buffer': [['b', 3], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]], 'capacity': 1}, {'trigger': True, 'resident': [['100', 0], ['101', 1], ['a', 1], ['102', 2], ['103', 3], ['b', 3], ['104', 4]], 'buffer': [], 'minimum': 0, 'size': 7, 'writes': 6})]][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{'buffer': [], 'minimum': None, 'resident': [], 'size': 0, 'trigger': False, 'writes': 0}{'buffer': [], 'minimum': None, 'resident': [], 'size': 0, 'trigger': False, 'writes': 0}Passed
regression certificate 2{'buffer': [['b', 1]], 'minimum': 1, 'resident': [['a', 5]], 'size': 2, 'trigger': False, 'writes': 0}{'buffer': [['b', 1]], 'minimum': 1, 'resident': [['a', 5]], 'size': 2, 'trigger': False, 'writes': 0}Passed
regression certificate 3{'buffer': [], 'minimum': 2, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'size': 4, 'trigger': True, 'writes': 2}{'buffer': [], 'minimum': 2, 'resident': [['c', 2], ['a', 5], ['d', 6], ['b', 7]], 'size': 4, 'trigger': True, 'writes': 2}Passed
regression certificate 4{'buffer': [], 'minimum': 3, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'size': 3, 'trigger': True, 'writes': 2}{'buffer': [], 'minimum': 3, 'resident': [['x', 3], ['y', 3], ['z', 3]], 'size': 3, 'trigger': True, 'writes': 2}Passed
regression certificate 5{'buffer': [], 'minimum': 2, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'size': 3, 'trigger': True, 'writes': 3}{'buffer': [], 'minimum': 2, 'resident': [['b', 2], ['c', 4], ['a', 8]], 'size': 3, 'trigger': True, 'writes': 3}Passed
regression certificate 6{'buffer': [], 'minimum': 1, 'resident': [['a', 1], ['b', 3]], 'size': 2, 'trigger': True, 'writes': 1}{'buffer': [], 'minimum': 1, 'resident': [['a', 1], ['b', 3]], 'size': 2, 'trigger': True, 'writes': 1}Passed
variant-dependent certificate{'buffer': [], 'minimum': 0, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'size': 3, 'trigger': True, 'writes': 2}{'buffer': [], 'minimum': 0, 'resident': [['100', 0], ['a', 1], ['b', 3]], 'size': 3, 'trigger': True, 'writes': 2}Passed

SHA-256 / 5298249a371b649e88b3d3eef6062175967e1d25d13e81a22c90e2834a7d255f

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

Case digest / 994f9cf32a38e191bc4fbff80435829a53dd9478cfae3d26c5311e9ca1f19e62