FAILURE MAP
← Case archive

FA-40051 / Heap invariants / Open access

Binomial extraction reverses child rank order rather than sorting by priority · case 01

The bounded binomial extract certificate reports an incorrect promoted.

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

ROOT CAUSE

Binomial extraction reverses child rank order rather than sorting by priority.

VERIFIED REPAIR

Derive promoted using [x[0] for x in reversed(c)] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [x[0] for x in sorted(c,key=lambda x:x[2])] 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 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': [4, 3, 2], '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': [6, 5], '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': [7, 3], '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, 0, 1], 'minimum': 6, 'parents': [[7, None], [3, None]], 'promoted': [7, 3], '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 / cd6c073a52b758dbf875c0f4aacd260360562b330c5fc7af7f9ecef988ed2edf

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 sorted(c,key=lambda x:x[2])],
    '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': [3, 4, 2], '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, 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 / c513b73ea86fdab4bcce590f3852c1d705734bf5ae8b336a25c8a2d90842b345

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

Case digest / 08c8cf04b2b8f395a7c8748a3f30ac86e5c1d60d2d31293360a979b0e3162004