FAILURE MAP
← Case archive

FA-41316 / Heap invariants / Open access

Skew heap light-right edges exclude missing right children · case 01

The bounded skew heavy certificate certificate reports an incorrect light right.

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

ROOT CAUSE

Skew heap light-right edges exclude missing right children.

VERIFIED REPAIR

Derive light right using [x[0] for x in a if x[2]>0 and x[0] not in heavy] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [x[0] for x in a if x[1]>0 and x[0] not in heavy] and still violates the stated relation.

Case contract

A skew-heap amortized certificate supplies nodes [id,left_size,right_size] with nonnegative subtree sizes. A right edge is heavy when right_size exceeds half the complete subtree size (1+left+right). Report heavy ids, light right ids, complete sizes, heavy potential, right-path charged light visits, and potential change between before and after certificates. Path ids refer to before nodes; this is a stipulated accounting 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):
    a=d['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[0] not in heavy],
    'subtree_sizes': [1+x[1]+x[2] for x in a],
    'potential': len(heavy),
    'light_visits': sum(i not in heavy for i in path),
    'potential_delta': len(newheavy)-len(heavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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{'heavy': [], 'light_right': [], 'light_visits': 0, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': []}{'heavy': [], 'light_right': [], 'light_visits': 0, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': []}Passed
regression certificate 2{'heavy': [], 'light_right': ['a'], 'light_visits': 1, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': [1]}{'heavy': [], 'light_right': [], 'light_visits': 1, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': [1]}Failed
regression certificate 3{'heavy': ['b'], 'light_right': ['a'], 'light_visits': 1, 'potential': 1, 'potential_delta': -1, 'subtree_sizes': [2, 3]}{'heavy': ['b'], 'light_right': ['a'], 'light_visits': 1, 'potential': 1, 'potential_delta': -1, 'subtree_sizes': [2, 3]}Passed
regression certificate 4{'heavy': ['a', 'b'], 'light_right': [], 'light_visits': 0, 'potential': 2, 'potential_delta': 0, 'subtree_sizes': [7, 5]}{'heavy': ['a', 'b'], 'light_right': [], 'light_visits': 0, 'potential': 2, 'potential_delta': 0, 'subtree_sizes': [7, 5]}Passed
regression certificate 5{'heavy': [], 'light_right': ['a', 'b'], 'light_visits': 1, 'potential': 0, 'potential_delta': 1, 'subtree_sizes': [6, 6]}{'heavy': [], 'light_right': ['a', 'b'], 'light_visits': 1, 'potential': 0, 'potential_delta': 1, 'subtree_sizes': [6, 6]}Passed
regression certificate 6{'heavy': ['a'], 'light_right': ['b', 'c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [6, 1, 5]}{'heavy': ['a'], 'light_right': ['c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [6, 1, 5]}Failed
variant-dependent certificate{'heavy': ['a'], 'light_right': ['b', 'c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [7, 1, 5]}{'heavy': ['a'], 'light_right': ['c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [7, 1, 5]}Failed

SHA-256 / e86770d73788c81c9326144de482ce55e3e0736cb6ee24c320d708a8879aaa87

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    a=d['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[1]>0 and x[0] not in heavy],
    'subtree_sizes': [1+x[1]+x[2] for x in a],
    'potential': len(heavy),
    'light_visits': sum(i not in heavy for i in path),
    'potential_delta': len(newheavy)-len(heavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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{'heavy': [], 'light_right': [], 'light_visits': 0, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': []}{'heavy': [], 'light_right': [], 'light_visits': 0, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': []}Passed
regression certificate 2{'heavy': [], 'light_right': [], 'light_visits': 1, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': [1]}{'heavy': [], 'light_right': [], 'light_visits': 1, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': [1]}Passed
regression certificate 3{'heavy': ['b'], 'light_right': [], 'light_visits': 1, 'potential': 1, 'potential_delta': -1, 'subtree_sizes': [2, 3]}{'heavy': ['b'], 'light_right': ['a'], 'light_visits': 1, 'potential': 1, 'potential_delta': -1, 'subtree_sizes': [2, 3]}Failed
regression certificate 4{'heavy': ['a', 'b'], 'light_right': [], 'light_visits': 0, 'potential': 2, 'potential_delta': 0, 'subtree_sizes': [7, 5]}{'heavy': ['a', 'b'], 'light_right': [], 'light_visits': 0, 'potential': 2, 'potential_delta': 0, 'subtree_sizes': [7, 5]}Passed
regression certificate 5{'heavy': [], 'light_right': ['a', 'b'], 'light_visits': 1, 'potential': 0, 'potential_delta': 1, 'subtree_sizes': [6, 6]}{'heavy': [], 'light_right': ['a', 'b'], 'light_visits': 1, 'potential': 0, 'potential_delta': 1, 'subtree_sizes': [6, 6]}Passed
regression certificate 6{'heavy': ['a'], 'light_right': ['c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [6, 1, 5]}{'heavy': ['a'], 'light_right': ['c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [6, 1, 5]}Passed
variant-dependent certificate{'heavy': ['a'], 'light_right': ['c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [7, 1, 5]}{'heavy': ['a'], 'light_right': ['c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [7, 1, 5]}Passed

SHA-256 / 457b1d3437fa61c2971dc8eaedc5e4eae8e13b3d9028e79d89c65ce8cc1c2f1c

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    a=d['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[2]>0 and x[0] not in heavy],
    'subtree_sizes': [1+x[1]+x[2] for x in a],
    'potential': len(heavy),
    'light_visits': sum(i not in heavy for i in path),
    'potential_delta': len(newheavy)-len(heavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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{'heavy': [], 'light_right': [], 'light_visits': 0, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': []}{'heavy': [], 'light_right': [], 'light_visits': 0, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': []}Passed
regression certificate 2{'heavy': [], 'light_right': [], 'light_visits': 1, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': [1]}{'heavy': [], 'light_right': [], 'light_visits': 1, 'potential': 0, 'potential_delta': 0, 'subtree_sizes': [1]}Passed
regression certificate 3{'heavy': ['b'], 'light_right': ['a'], 'light_visits': 1, 'potential': 1, 'potential_delta': -1, 'subtree_sizes': [2, 3]}{'heavy': ['b'], 'light_right': ['a'], 'light_visits': 1, 'potential': 1, 'potential_delta': -1, 'subtree_sizes': [2, 3]}Passed
regression certificate 4{'heavy': ['a', 'b'], 'light_right': [], 'light_visits': 0, 'potential': 2, 'potential_delta': 0, 'subtree_sizes': [7, 5]}{'heavy': ['a', 'b'], 'light_right': [], 'light_visits': 0, 'potential': 2, 'potential_delta': 0, 'subtree_sizes': [7, 5]}Passed
regression certificate 5{'heavy': [], 'light_right': ['a', 'b'], 'light_visits': 1, 'potential': 0, 'potential_delta': 1, 'subtree_sizes': [6, 6]}{'heavy': [], 'light_right': ['a', 'b'], 'light_visits': 1, 'potential': 0, 'potential_delta': 1, 'subtree_sizes': [6, 6]}Passed
regression certificate 6{'heavy': ['a'], 'light_right': ['c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [6, 1, 5]}{'heavy': ['a'], 'light_right': ['c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [6, 1, 5]}Passed
variant-dependent certificate{'heavy': ['a'], 'light_right': ['c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [7, 1, 5]}{'heavy': ['a'], 'light_right': ['c'], 'light_visits': 1, 'potential': 1, 'potential_delta': 0, 'subtree_sizes': [7, 1, 5]}Passed

SHA-256 / 2cf71ed212839800043b621eac4cfbcffbf294217be2df0cc9129b257067f111

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

Case digest / e197cd11db1e5182a8685ff83ce6b827c0aa8d73d371ea3ba85f6b2164b17a3f