FAILURE MAP
← Case archive

FA-40226 / Heap invariants / Open access

Skew meld retains a unary subtree instead of misclassifying the winner as a leaf · case 01

The bounded skew meld step certificate reports an incorrect leaf.

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

ROOT CAUSE

Skew meld retains a unary subtree instead of misclassifying the winner as a leaf.

VERIFIED REPAIR

Derive leaf using old is None and result is None under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses result is None 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': 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}
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': True, '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}Failed
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 / f80efe93fdf845caa32c9297141adcba9711511829604ca6a0d41ee5bedd47b6

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,
    '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': 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': True, '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}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': 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 / 4dcbfaf26306f268f40570de9114ad0a483a873629098c85e86bb418959dde6b

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

Case digest / e6714e18fef30cd685d6ab1d6beeb00212b56c06d4d686ff74e118878b4006d8