FAILURE MAP
← Case archive

FA-40196 / Heap invariants / Open access

Leftist meld rewrites both surviving child parent links toward the chosen root · case 01

The bounded leftist meld step certificate reports an incorrect parent assignments.

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

ROOT CAUSE

Leftist meld rewrites both surviving child parent links toward the chosen root.

VERIFIED REPAIR

Derive parent assignments using [[x[0],d["root"]] for x in (l,r) if x] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [[d["root"],x[0]] for x in (l,r) if x] and still violates the stated relation.

Case contract

A leftist meld unwind record gives chosen root id, left subtree [id,npl,size] or None, returned right subtree similarly, and root key. Orient children by npl (null=-1), retain left on equal rank, set npl to right npl+1, and size to one plus both child sizes.

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):
    left=d['left']; right=d['right']; ln=-1 if left is None else left[1]; rn=-1 if right is None else right[1]
    l,r=(right,left) if ln<rn else (left,right)
    return {'left_id': l[0] if l else None,
    'right_id': r[0] if r else None,
    'npl': 1+(-1 if r is None else r[1]),
    'size': 1+sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[x[0],d["root"]] for x in (l,) if x]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 3], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 13, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 4], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 14, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 5], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 15, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 6], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 16, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 7], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 17, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})]][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{'left_id': None, 'npl': 0, 'parent_assignments': [], 'right_id': None, 'size': 1, 'swap': False}{'left_id': None, 'npl': 0, 'parent_assignments': [], 'right_id': None, 'size': 1, 'swap': False}Passed
regression certificate 2{'left_id': 1, 'npl': 0, 'parent_assignments': [[1, 9]], 'right_id': None, 'size': 2, 'swap': False}{'left_id': 1, 'npl': 0, 'parent_assignments': [[1, 9]], 'right_id': None, 'size': 2, 'swap': False}Passed
regression certificate 3{'left_id': 2, 'npl': 0, 'parent_assignments': [[2, 9]], 'right_id': None, 'size': 4, 'swap': True}{'left_id': 2, 'npl': 0, 'parent_assignments': [[2, 9]], 'right_id': None, 'size': 4, 'swap': True}Passed
regression certificate 4{'left_id': 1, 'npl': 1, 'parent_assignments': [[1, 9]], 'right_id': 2, 'size': 10, 'swap': False}{'left_id': 1, 'npl': 1, 'parent_assignments': [[1, 9], [2, 9]], 'right_id': 2, 'size': 10, 'swap': False}Failed
regression certificate 5{'left_id': 1, 'npl': 2, 'parent_assignments': [[1, 9]], 'right_id': 2, 'size': 9, 'swap': False}{'left_id': 1, 'npl': 2, 'parent_assignments': [[1, 9], [2, 9]], 'right_id': 2, 'size': 9, 'swap': False}Failed
regression certificate 6{'left_id': 2, 'npl': 1, 'parent_assignments': [[2, 9]], 'right_id': 1, 'size': 12, 'swap': True}{'left_id': 2, 'npl': 1, 'parent_assignments': [[2, 9], [1, 9]], 'right_id': 1, 'size': 12, 'swap': True}Failed
variant-dependent certificate{'left_id': 2, 'npl': 1, 'parent_assignments': [[2, 9]], 'right_id': 1, 'size': 13, 'swap': True}{'left_id': 2, 'npl': 1, 'parent_assignments': [[2, 9], [1, 9]], 'right_id': 1, 'size': 13, 'swap': True}Failed

SHA-256 / 059ced8edf55fe69c7906317f54e1f522dd19980a094acfe92c3cfa652733867

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    left=d['left']; right=d['right']; ln=-1 if left is None else left[1]; rn=-1 if right is None else right[1]
    l,r=(right,left) if ln<rn else (left,right)
    return {'left_id': l[0] if l else None,
    'right_id': r[0] if r else None,
    'npl': 1+(-1 if r is None else r[1]),
    'size': 1+sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[d["root"],x[0]] for x in (l,r) if x]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 3], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 13, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 4], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 14, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 5], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 15, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 6], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 16, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 7], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 17, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})]][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{'left_id': None, 'npl': 0, 'parent_assignments': [], 'right_id': None, 'size': 1, 'swap': False}{'left_id': None, 'npl': 0, 'parent_assignments': [], 'right_id': None, 'size': 1, 'swap': False}Passed
regression certificate 2{'left_id': 1, 'npl': 0, 'parent_assignments': [[9, 1]], 'right_id': None, 'size': 2, 'swap': False}{'left_id': 1, 'npl': 0, 'parent_assignments': [[1, 9]], 'right_id': None, 'size': 2, 'swap': False}Failed
regression certificate 3{'left_id': 2, 'npl': 0, 'parent_assignments': [[9, 2]], 'right_id': None, 'size': 4, 'swap': True}{'left_id': 2, 'npl': 0, 'parent_assignments': [[2, 9]], 'right_id': None, 'size': 4, 'swap': True}Failed
regression certificate 4{'left_id': 1, 'npl': 1, 'parent_assignments': [[9, 1], [9, 2]], 'right_id': 2, 'size': 10, 'swap': False}{'left_id': 1, 'npl': 1, 'parent_assignments': [[1, 9], [2, 9]], 'right_id': 2, 'size': 10, 'swap': False}Failed
regression certificate 5{'left_id': 1, 'npl': 2, 'parent_assignments': [[9, 1], [9, 2]], 'right_id': 2, 'size': 9, 'swap': False}{'left_id': 1, 'npl': 2, 'parent_assignments': [[1, 9], [2, 9]], 'right_id': 2, 'size': 9, 'swap': False}Failed
regression certificate 6{'left_id': 2, 'npl': 1, 'parent_assignments': [[9, 2], [9, 1]], 'right_id': 1, 'size': 12, 'swap': True}{'left_id': 2, 'npl': 1, 'parent_assignments': [[2, 9], [1, 9]], 'right_id': 1, 'size': 12, 'swap': True}Failed
variant-dependent certificate{'left_id': 2, 'npl': 1, 'parent_assignments': [[9, 2], [9, 1]], 'right_id': 1, 'size': 13, 'swap': True}{'left_id': 2, 'npl': 1, 'parent_assignments': [[2, 9], [1, 9]], 'right_id': 1, 'size': 13, 'swap': True}Failed

SHA-256 / fcdd917e5cd7767aa5a9c394229c613c6bb16c65f404e2026e4a93c90d27424d

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    left=d['left']; right=d['right']; ln=-1 if left is None else left[1]; rn=-1 if right is None else right[1]
    l,r=(right,left) if ln<rn else (left,right)
    return {'left_id': l[0] if l else None,
    'right_id': r[0] if r else None,
    'npl': 1+(-1 if r is None else r[1]),
    'size': 1+sum(x[2] for x in (l,r) if x),
    'swap': ln<rn,
    'parent_assignments': [[x[0],d["root"]] for x in (l,r) if x]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 3], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 13, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 4], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 14, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 5], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 15, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 6], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 16, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})], [({'root': 9, 'left': None, 'right': None, 'key': 0}, {'left_id': None, 'right_id': None, 'npl': 0, 'size': 1, 'swap': False, 'parent_assignments': []}), ({'root': 9, 'left': [1, 0, 1], 'right': None, 'key': 0}, {'left_id': 1, 'right_id': None, 'npl': 0, 'size': 2, 'swap': False, 'parent_assignments': [[1, 9]]}), ({'root': 9, 'left': None, 'right': [2, 1, 3], 'key': 0}, {'left_id': 2, 'right_id': None, 'npl': 0, 'size': 4, 'swap': True, 'parent_assignments': [[2, 9]]}), ({'root': 9, 'left': [1, 2, 7], 'right': [2, 0, 2], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 1, 'size': 10, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 1, 3], 'right': [2, 1, 5], 'key': 0}, {'left_id': 1, 'right_id': 2, 'npl': 2, 'size': 9, 'swap': False, 'parent_assignments': [[1, 9], [2, 9]]}), ({'root': 9, 'left': [1, 0, 2], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 12, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]}), ({'root': 9, 'left': [1, 0, 7], 'right': [2, 2, 9], 'key': 0}, {'left_id': 2, 'right_id': 1, 'npl': 1, 'size': 17, 'swap': True, 'parent_assignments': [[2, 9], [1, 9]]})]][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{'left_id': None, 'npl': 0, 'parent_assignments': [], 'right_id': None, 'size': 1, 'swap': False}{'left_id': None, 'npl': 0, 'parent_assignments': [], 'right_id': None, 'size': 1, 'swap': False}Passed
regression certificate 2{'left_id': 1, 'npl': 0, 'parent_assignments': [[1, 9]], 'right_id': None, 'size': 2, 'swap': False}{'left_id': 1, 'npl': 0, 'parent_assignments': [[1, 9]], 'right_id': None, 'size': 2, 'swap': False}Passed
regression certificate 3{'left_id': 2, 'npl': 0, 'parent_assignments': [[2, 9]], 'right_id': None, 'size': 4, 'swap': True}{'left_id': 2, 'npl': 0, 'parent_assignments': [[2, 9]], 'right_id': None, 'size': 4, 'swap': True}Passed
regression certificate 4{'left_id': 1, 'npl': 1, 'parent_assignments': [[1, 9], [2, 9]], 'right_id': 2, 'size': 10, 'swap': False}{'left_id': 1, 'npl': 1, 'parent_assignments': [[1, 9], [2, 9]], 'right_id': 2, 'size': 10, 'swap': False}Passed
regression certificate 5{'left_id': 1, 'npl': 2, 'parent_assignments': [[1, 9], [2, 9]], 'right_id': 2, 'size': 9, 'swap': False}{'left_id': 1, 'npl': 2, 'parent_assignments': [[1, 9], [2, 9]], 'right_id': 2, 'size': 9, 'swap': False}Passed
regression certificate 6{'left_id': 2, 'npl': 1, 'parent_assignments': [[2, 9], [1, 9]], 'right_id': 1, 'size': 12, 'swap': True}{'left_id': 2, 'npl': 1, 'parent_assignments': [[2, 9], [1, 9]], 'right_id': 1, 'size': 12, 'swap': True}Passed
variant-dependent certificate{'left_id': 2, 'npl': 1, 'parent_assignments': [[2, 9], [1, 9]], 'right_id': 1, 'size': 13, 'swap': True}{'left_id': 2, 'npl': 1, 'parent_assignments': [[2, 9], [1, 9]], 'right_id': 1, 'size': 13, 'swap': True}Passed

SHA-256 / 03d9877ccee17e015cdd57d4ea10a984bce5e5c60e796c986bdd8df7c78044f9

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

Case digest / bfac90bfe7fb026b9300405e7ddb446dfe656a0d47b822c1335e577f26de2531