FAILURE MAP
← Case archive

FA-40071 / Heap invariants / Open access

Binomial extraction preserves rank collisions for later consolidation · case 01

The bounded binomial extract certificate reports an incorrect merge ranks.

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

ROOT CAUSE

Binomial extraction preserves rank collisions for later consolidation.

VERIFIED REPAIR

Derive merge ranks using sorted(x[1] for x in merged) under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [x[1] for x in merged] and still violates the stated relation.

Case contract

Extracted binomial root children are [id,rank,key] in descending rank. Remaining roots are [id,rank,key]. Return promoted root order, parent resets, cardinality delta, remaining minimum, merge rank sequence, and removed handle. Reversal restores ascending rank order before union.

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):
    c=d['children']; r=d['remaining']; removed=d['removed']; merged=r+list(reversed(c))
    return {'promoted': [x[0] for x in reversed(c)],
    'parents': [[x[0],None] for x in c],
    'size_delta': -1,
    'minimum': min(merged,key=lambda x:x[2])[0] if merged else None,
    'merge_ranks': sorted(set(x[1] for x in merged)),
    'live_handles': sorted(x[0] for x in merged)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 5], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 6], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 7], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 8], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 9], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})]][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{'live_handles': [], 'merge_ranks': [], 'minimum': None, 'parents': [], 'promoted': [], 'size_delta': -1}{'live_handles': [], 'merge_ranks': [], 'minimum': None, 'parents': [], 'promoted': [], 'size_delta': -1}Passed
regression certificate 2{'live_handles': [3], 'merge_ranks': [0], 'minimum': 3, 'parents': [[3, None]], 'promoted': [3], 'size_delta': -1}{'live_handles': [3], 'merge_ranks': [0], 'minimum': 3, 'parents': [[3, None]], 'promoted': [3], 'size_delta': -1}Passed
regression certificate 3{'live_handles': [2, 3, 4, 7, 8], 'merge_ranks': [0, 1, 2, 3], 'minimum': 7, 'parents': [[4, None], [3, None], [2, None]], 'promoted': [2, 3, 4], 'size_delta': -1}{'live_handles': [2, 3, 4, 7, 8], 'merge_ranks': [0, 0, 1, 2, 3], 'minimum': 7, 'parents': [[4, None], [3, None], [2, None]], 'promoted': [2, 3, 4], 'size_delta': -1}Failed
regression certificate 4{'live_handles': [5, 6, 8], 'merge_ranks': [0, 1, 2], 'minimum': 5, 'parents': [[6, None], [5, None]], 'promoted': [5, 6], 'size_delta': -1}{'live_handles': [5, 6, 8], 'merge_ranks': [0, 1, 2], 'minimum': 5, 'parents': [[6, None], [5, None]], 'promoted': [5, 6], 'size_delta': -1}Passed
regression certificate 5{'live_handles': [2, 5], 'merge_ranks': [0, 1], 'minimum': 2, 'parents': [], 'promoted': [], 'size_delta': -1}{'live_handles': [2, 5], 'merge_ranks': [0, 1], 'minimum': 2, 'parents': [], 'promoted': [], 'size_delta': -1}Passed
regression certificate 6{'live_handles': [3, 6, 7], 'merge_ranks': [0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}{'live_handles': [3, 6, 7], 'merge_ranks': [0, 0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}Failed
variant-dependent certificate{'live_handles': [3, 6, 7], 'merge_ranks': [0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}{'live_handles': [3, 6, 7], 'merge_ranks': [0, 0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}Failed

SHA-256 / ea440e2f08e2058f4889afb820851e413d6b5b45b7bd6d175f169f00dae43f53

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    c=d['children']; r=d['remaining']; removed=d['removed']; merged=r+list(reversed(c))
    return {'promoted': [x[0] for x in reversed(c)],
    'parents': [[x[0],None] for x in c],
    'size_delta': -1,
    'minimum': min(merged,key=lambda x:x[2])[0] if merged else None,
    'merge_ranks': [x[1] for x in merged],
    'live_handles': sorted(x[0] for x in merged)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 5], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 6], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 7], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 8], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 9], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})]][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{'live_handles': [], 'merge_ranks': [], 'minimum': None, 'parents': [], 'promoted': [], 'size_delta': -1}{'live_handles': [], 'merge_ranks': [], 'minimum': None, 'parents': [], 'promoted': [], 'size_delta': -1}Passed
regression certificate 2{'live_handles': [3], 'merge_ranks': [0], 'minimum': 3, 'parents': [[3, None]], 'promoted': [3], 'size_delta': -1}{'live_handles': [3], 'merge_ranks': [0], 'minimum': 3, 'parents': [[3, None]], 'promoted': [3], 'size_delta': -1}Passed
regression certificate 3{'live_handles': [2, 3, 4, 7, 8], 'merge_ranks': [0, 3, 0, 1, 2], 'minimum': 7, 'parents': [[4, None], [3, None], [2, None]], 'promoted': [2, 3, 4], 'size_delta': -1}{'live_handles': [2, 3, 4, 7, 8], 'merge_ranks': [0, 0, 1, 2, 3], 'minimum': 7, 'parents': [[4, None], [3, None], [2, None]], 'promoted': [2, 3, 4], 'size_delta': -1}Failed
regression certificate 4{'live_handles': [5, 6, 8], 'merge_ranks': [2, 0, 1], 'minimum': 5, 'parents': [[6, None], [5, None]], 'promoted': [5, 6], 'size_delta': -1}{'live_handles': [5, 6, 8], 'merge_ranks': [0, 1, 2], 'minimum': 5, 'parents': [[6, None], [5, None]], 'promoted': [5, 6], 'size_delta': -1}Failed
regression certificate 5{'live_handles': [2, 5], 'merge_ranks': [0, 1], 'minimum': 2, 'parents': [], 'promoted': [], 'size_delta': -1}{'live_handles': [2, 5], 'merge_ranks': [0, 1], 'minimum': 2, 'parents': [], 'promoted': [], 'size_delta': -1}Passed
regression certificate 6{'live_handles': [3, 6, 7], 'merge_ranks': [0, 0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}{'live_handles': [3, 6, 7], 'merge_ranks': [0, 0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}Passed
variant-dependent certificate{'live_handles': [3, 6, 7], 'merge_ranks': [0, 0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}{'live_handles': [3, 6, 7], 'merge_ranks': [0, 0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}Passed

SHA-256 / e8a12b640a0d021a52c70c758f0b1932cee94a17cbd4ec03c460caacda9777cc

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    c=d['children']; r=d['remaining']; removed=d['removed']; merged=r+list(reversed(c))
    return {'promoted': [x[0] for x in reversed(c)],
    'parents': [[x[0],None] for x in c],
    'size_delta': -1,
    'minimum': min(merged,key=lambda x:x[2])[0] if merged else None,
    'merge_ranks': sorted(x[1] for x in merged),
    'live_handles': sorted(x[0] for x in merged)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 5], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 6], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 7], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 8], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})], [({'children': [], 'remaining': [], 'removed': 9}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': None, 'merge_ranks': [], 'live_handles': []}), ({'children': [[3, 0, 7]], 'remaining': [], 'removed': 1}, {'promoted': [3], 'parents': [[3, None]], 'size_delta': -1, 'minimum': 3, 'merge_ranks': [0], 'live_handles': [3]}), ({'children': [[4, 2, 6], [3, 1, 5], [2, 0, 8]], 'remaining': [[7, 0, 4], [8, 3, 9]], 'removed': 1}, {'promoted': [2, 3, 4], 'parents': [[4, None], [3, None], [2, None]], 'size_delta': -1, 'minimum': 7, 'merge_ranks': [0, 0, 1, 2, 3], 'live_handles': [2, 3, 4, 7, 8]}), ({'children': [[6, 1, 3], [5, 0, 2]], 'remaining': [[8, 2, 7]], 'removed': 4}, {'promoted': [5, 6], 'parents': [[6, None], [5, None]], 'size_delta': -1, 'minimum': 5, 'merge_ranks': [0, 1, 2], 'live_handles': [5, 6, 8]}), ({'children': [], 'remaining': [[5, 0, 8], [2, 1, 1]], 'removed': 7}, {'promoted': [], 'parents': [], 'size_delta': -1, 'minimum': 2, 'merge_ranks': [0, 1], 'live_handles': [2, 5]}), ({'children': [[7, 1, 4], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]}), ({'children': [[7, 1, 9], [3, 0, 3]], 'remaining': [[6, 0, 3]], 'removed': 9}, {'promoted': [3, 7], 'parents': [[7, None], [3, None]], 'size_delta': -1, 'minimum': 6, 'merge_ranks': [0, 0, 1], 'live_handles': [3, 6, 7]})]][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{'live_handles': [], 'merge_ranks': [], 'minimum': None, 'parents': [], 'promoted': [], 'size_delta': -1}{'live_handles': [], 'merge_ranks': [], 'minimum': None, 'parents': [], 'promoted': [], 'size_delta': -1}Passed
regression certificate 2{'live_handles': [3], 'merge_ranks': [0], 'minimum': 3, 'parents': [[3, None]], 'promoted': [3], 'size_delta': -1}{'live_handles': [3], 'merge_ranks': [0], 'minimum': 3, 'parents': [[3, None]], 'promoted': [3], 'size_delta': -1}Passed
regression certificate 3{'live_handles': [2, 3, 4, 7, 8], 'merge_ranks': [0, 0, 1, 2, 3], 'minimum': 7, 'parents': [[4, None], [3, None], [2, None]], 'promoted': [2, 3, 4], 'size_delta': -1}{'live_handles': [2, 3, 4, 7, 8], 'merge_ranks': [0, 0, 1, 2, 3], 'minimum': 7, 'parents': [[4, None], [3, None], [2, None]], 'promoted': [2, 3, 4], 'size_delta': -1}Passed
regression certificate 4{'live_handles': [5, 6, 8], 'merge_ranks': [0, 1, 2], 'minimum': 5, 'parents': [[6, None], [5, None]], 'promoted': [5, 6], 'size_delta': -1}{'live_handles': [5, 6, 8], 'merge_ranks': [0, 1, 2], 'minimum': 5, 'parents': [[6, None], [5, None]], 'promoted': [5, 6], 'size_delta': -1}Passed
regression certificate 5{'live_handles': [2, 5], 'merge_ranks': [0, 1], 'minimum': 2, 'parents': [], 'promoted': [], 'size_delta': -1}{'live_handles': [2, 5], 'merge_ranks': [0, 1], 'minimum': 2, 'parents': [], 'promoted': [], 'size_delta': -1}Passed
regression certificate 6{'live_handles': [3, 6, 7], 'merge_ranks': [0, 0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}{'live_handles': [3, 6, 7], 'merge_ranks': [0, 0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}Passed
variant-dependent certificate{'live_handles': [3, 6, 7], 'merge_ranks': [0, 0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}{'live_handles': [3, 6, 7], 'merge_ranks': [0, 0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [3, 7], 'size_delta': -1}Passed

SHA-256 / b9ae4173995e980a74ed977a46666c63eadc7ef2f3faa230eaadad82fdf2346d

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

Case digest / 5fc724daf0ef12f798fbf0d101c919176db888e3efd881e1bfe2401c27516e61