FAILURE MAP
← Case archive

FA-40191 / Heap invariants / Open access

Leftist unwind preserves equal-rank child orientation · case 01

The bounded leftist meld step certificate reports an incorrect swap.

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

ROOT CAUSE

Leftist unwind preserves equal-rank child orientation.

VERIFIED REPAIR

Derive swap using ln<rn under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses ln>rn 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,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': True}{'left_id': None, 'npl': 0, 'parent_assignments': [], 'right_id': None, 'size': 1, 'swap': False}Failed
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': True}{'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], [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 / af6817a075e0ecb1c33794c74e681774610dd6f74e27bc75f05a7b76ed630778

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': [[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': True}{'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': [[2, 9]], 'right_id': None, 'size': 4, 'swap': False}{'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': [[1, 9], [2, 9]], 'right_id': 2, 'size': 10, 'swap': True}{'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], [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': False}{'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], [1, 9]], 'right_id': 1, 'size': 13, 'swap': False}{'left_id': 2, 'npl': 1, 'parent_assignments': [[2, 9], [1, 9]], 'right_id': 1, 'size': 13, 'swap': True}Failed

SHA-256 / dd6a629190b60e7ab271ab61b0fb24863372ff69ef0c9ba9a69a41d1baa7dac5

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

Case digest / fa70c7a0089e1c4c440e7b1b9c228d020b961501f7765cabef834d3cc4b40240