FAILURE MAP
← Case archive

FA-40201 / Heap invariants / Open access

Skew meld puts the recursive merge result on the left even when an old left child exists · case 01

The bounded skew meld step certificate reports an incorrect new left.

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

ROOT CAUSE

Skew meld puts the recursive merge result on the left even when an old left child exists.

VERIFIED REPAIR

Derive new left using result under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses result if old is None else old and still violates the stated relation.

Case contract

A skew meld unwind chooses the smaller root, recursively melds its old right subtree with the other heap, and unconditionally swaps children. Record supplies winner, old_left, recursive_result and sizes. Missing subtrees are None. No rank-based swap condition is part of this model.

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):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': old,
    'new_right': old,
    'size': 1+sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][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{'leaf': True, 'new_left': None, 'new_right': None, 'preorder_children': [], 'rewrites': [], 'size': 1}{'leaf': True, 'new_left': None, 'new_right': None, 'preorder_children': [], 'rewrites': [], 'size': 1}Passed
regression certificate 2{'leaf': False, 'new_left': 1, 'new_right': 1, 'preorder_children': [1], 'rewrites': [[1, 9]], 'size': 3}{'leaf': False, 'new_left': None, 'new_right': 1, 'preorder_children': [1], 'rewrites': [[1, 9]], 'size': 3}Failed
regression certificate 3{'leaf': False, 'new_left': None, 'new_right': None, 'preorder_children': [3], 'rewrites': [[3, 9]], 'size': 5}{'leaf': False, 'new_left': 3, 'new_right': None, 'preorder_children': [3], 'rewrites': [[3, 9]], 'size': 5}Failed
regression certificate 4{'leaf': False, 'new_left': 1, 'new_right': 1, 'preorder_children': [2, 1], 'rewrites': [[2, 9], [1, 9]], 'size': 9}{'leaf': False, 'new_left': 2, 'new_right': 1, 'preorder_children': [2, 1], 'rewrites': [[2, 9], [1, 9]], 'size': 9}Failed
regression certificate 5{'leaf': False, 'new_left': 7, 'new_right': 7, 'preorder_children': [2, 7], 'rewrites': [[2, 9], [7, 9]], 'size': 4}{'leaf': False, 'new_left': 2, 'new_right': 7, 'preorder_children': [2, 7], 'rewrites': [[2, 9], [7, 9]], 'size': 4}Failed
regression certificate 6{'leaf': False, 'new_left': 4, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 17}{'leaf': False, 'new_left': 8, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 17}Failed
variant-dependent certificate{'leaf': False, 'new_left': 4, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 19}{'leaf': False, 'new_left': 8, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 19}Failed

SHA-256 / 22428926c8e28161500bb90fd0b57f55c786457db6e5a28910aea1c5d0fcc1c3

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result if old is None else old,
    'new_right': old,
    'size': 1+sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][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{'leaf': True, 'new_left': None, 'new_right': None, 'preorder_children': [], 'rewrites': [], 'size': 1}{'leaf': True, 'new_left': None, 'new_right': None, 'preorder_children': [], 'rewrites': [], 'size': 1}Passed
regression certificate 2{'leaf': False, 'new_left': 1, 'new_right': 1, 'preorder_children': [1], 'rewrites': [[1, 9]], 'size': 3}{'leaf': False, 'new_left': None, 'new_right': 1, 'preorder_children': [1], 'rewrites': [[1, 9]], 'size': 3}Failed
regression certificate 3{'leaf': False, 'new_left': 3, 'new_right': None, 'preorder_children': [3], 'rewrites': [[3, 9]], 'size': 5}{'leaf': False, 'new_left': 3, 'new_right': None, 'preorder_children': [3], 'rewrites': [[3, 9]], 'size': 5}Passed
regression certificate 4{'leaf': False, 'new_left': 1, 'new_right': 1, 'preorder_children': [2, 1], 'rewrites': [[2, 9], [1, 9]], 'size': 9}{'leaf': False, 'new_left': 2, 'new_right': 1, 'preorder_children': [2, 1], 'rewrites': [[2, 9], [1, 9]], 'size': 9}Failed
regression certificate 5{'leaf': False, 'new_left': 7, 'new_right': 7, 'preorder_children': [2, 7], 'rewrites': [[2, 9], [7, 9]], 'size': 4}{'leaf': False, 'new_left': 2, 'new_right': 7, 'preorder_children': [2, 7], 'rewrites': [[2, 9], [7, 9]], 'size': 4}Failed
regression certificate 6{'leaf': False, 'new_left': 4, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 17}{'leaf': False, 'new_left': 8, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 17}Failed
variant-dependent certificate{'leaf': False, 'new_left': 4, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 19}{'leaf': False, 'new_left': 8, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 19}Failed

SHA-256 / 6907d82ad555fbd39e03fab2ab6e3bb79d28d5a3cec434f664b54a492a515e09

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    old=d['old_left']; result=d['result']; sizes=d['sizes']
    return {'new_left': result,
    'new_right': old,
    'size': 1+sum(sizes),
    'rewrites': [[x,d["winner"]] for x in (result,old) if x is not None],
    'preorder_children': [x for x in (result,old) if x is not None],
    'leaf': old is None and result is None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [8, 10]}, {'new_left': 8, 'new_right': 4, 'size': 19, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [9, 11]}, {'new_left': 8, 'new_right': 4, 'size': 21, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [10, 12]}, {'new_left': 8, 'new_right': 4, 'size': 23, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [11, 13]}, {'new_left': 8, 'new_right': 4, 'size': 25, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})], [({'winner': 9, 'old_left': None, 'result': None, 'sizes': [0, 0]}, {'new_left': None, 'new_right': None, 'size': 1, 'rewrites': [], 'preorder_children': [], 'leaf': True}), ({'winner': 9, 'old_left': 1, 'result': None, 'sizes': [2, 0]}, {'new_left': None, 'new_right': 1, 'size': 3, 'rewrites': [[1, 9]], 'preorder_children': [1], 'leaf': False}), ({'winner': 9, 'old_left': None, 'result': 3, 'sizes': [0, 4]}, {'new_left': 3, 'new_right': None, 'size': 5, 'rewrites': [[3, 9]], 'preorder_children': [3], 'leaf': False}), ({'winner': 9, 'old_left': 1, 'result': 2, 'sizes': [5, 3]}, {'new_left': 2, 'new_right': 1, 'size': 9, 'rewrites': [[2, 9], [1, 9]], 'preorder_children': [2, 1], 'leaf': False}), ({'winner': 9, 'old_left': 7, 'result': 2, 'sizes': [1, 2]}, {'new_left': 2, 'new_right': 7, 'size': 4, 'rewrites': [[2, 9], [7, 9]], 'preorder_children': [2, 7], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [7, 9]}, {'new_left': 8, 'new_right': 4, 'size': 17, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False}), ({'winner': 9, 'old_left': 4, 'result': 8, 'sizes': [12, 14]}, {'new_left': 8, 'new_right': 4, 'size': 27, 'rewrites': [[8, 9], [4, 9]], 'preorder_children': [8, 4], 'leaf': False})]][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{'leaf': True, 'new_left': None, 'new_right': None, 'preorder_children': [], 'rewrites': [], 'size': 1}{'leaf': True, 'new_left': None, 'new_right': None, 'preorder_children': [], 'rewrites': [], 'size': 1}Passed
regression certificate 2{'leaf': False, 'new_left': None, 'new_right': 1, 'preorder_children': [1], 'rewrites': [[1, 9]], 'size': 3}{'leaf': False, 'new_left': None, 'new_right': 1, 'preorder_children': [1], 'rewrites': [[1, 9]], 'size': 3}Passed
regression certificate 3{'leaf': False, 'new_left': 3, 'new_right': None, 'preorder_children': [3], 'rewrites': [[3, 9]], 'size': 5}{'leaf': False, 'new_left': 3, 'new_right': None, 'preorder_children': [3], 'rewrites': [[3, 9]], 'size': 5}Passed
regression certificate 4{'leaf': False, 'new_left': 2, 'new_right': 1, 'preorder_children': [2, 1], 'rewrites': [[2, 9], [1, 9]], 'size': 9}{'leaf': False, 'new_left': 2, 'new_right': 1, 'preorder_children': [2, 1], 'rewrites': [[2, 9], [1, 9]], 'size': 9}Passed
regression certificate 5{'leaf': False, 'new_left': 2, 'new_right': 7, 'preorder_children': [2, 7], 'rewrites': [[2, 9], [7, 9]], 'size': 4}{'leaf': False, 'new_left': 2, 'new_right': 7, 'preorder_children': [2, 7], 'rewrites': [[2, 9], [7, 9]], 'size': 4}Passed
regression certificate 6{'leaf': False, 'new_left': 8, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 17}{'leaf': False, 'new_left': 8, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 17}Passed
variant-dependent certificate{'leaf': False, 'new_left': 8, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 19}{'leaf': False, 'new_left': 8, 'new_right': 4, 'preorder_children': [8, 4], 'rewrites': [[8, 9], [4, 9]], 'size': 19}Passed

SHA-256 / 04de77e3580155d55e2f1fad03479510df3fe6a16dd22973c1ebfcdc99eae9b6

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

Case digest / f56ac9cee0ca1210343f17615a9588189cadd2a34b23333066899efe757ffbac