FAILURE MAP
← Case archive

FA-40086 / Heap invariants / Open access

Fibonacci cut preserves existing roots and appends the cut child · case 01

The bounded fibonacci cut certificate reports an incorrect root append.

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

ROOT CAUSE

Fibonacci cut preserves existing roots and appends the cut child.

VERIFIED REPAIR

Derive root append using roots+[c] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses roots+[p] and still violates the stated relation.

Case contract

A Fibonacci cut certificate has child c, parent p, ordered parent children, root ids, parent degree, child mark, and node keys. Cut detaches c, promotes it to the end of roots, clears its mark and parent, and decrements parent degree; it does not erase descendants.

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):
    c=d['child']; p=d['parent']; children=d['children']; roots=d['roots']; degree=d['degree']
    return {'parent_children': [x for x in children if x!=c],
    'root_append': [c],
    'degree': degree-1,
    'child_parent': None,
    'mark': False,
    'descendants': d["descendants"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103, 104]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103, 104]})]][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{'child_parent': None, 'degree': 0, 'descendants': [], 'mark': False, 'parent_children': [], 'root_append': [1]}{'child_parent': None, 'degree': 0, 'descendants': [], 'mark': False, 'parent_children': [], 'root_append': [9, 1]}Failed
regression certificate 2{'child_parent': None, 'degree': 2, 'descendants': [4, 5], 'mark': False, 'parent_children': [1, 3], 'root_append': [2]}{'child_parent': None, 'degree': 2, 'descendants': [4, 5], 'mark': False, 'parent_children': [1, 3], 'root_append': [9, 8, 2]}Failed
regression certificate 3{'child_parent': None, 'degree': 1, 'descendants': [3], 'mark': False, 'parent_children': [2], 'root_append': [1]}{'child_parent': None, 'degree': 1, 'descendants': [3], 'mark': False, 'parent_children': [2], 'root_append': [9, 1]}Failed
regression certificate 4{'child_parent': None, 'degree': 2, 'descendants': [], 'mark': False, 'parent_children': [1, 2], 'root_append': [3]}{'child_parent': None, 'degree': 2, 'descendants': [], 'mark': False, 'parent_children': [1, 2], 'root_append': [9, 7, 3]}Failed
regression certificate 5{'child_parent': None, 'degree': 1, 'descendants': [1], 'mark': False, 'parent_children': [5], 'root_append': [4]}{'child_parent': None, 'degree': 1, 'descendants': [1], 'mark': False, 'parent_children': [5], 'root_append': [9, 6, 4]}Failed
regression certificate 6{'child_parent': None, 'degree': 1, 'descendants': [7, 8], 'mark': False, 'parent_children': [3], 'root_append': [2]}{'child_parent': None, 'degree': 1, 'descendants': [7, 8], 'mark': False, 'parent_children': [3], 'root_append': [9, 2]}Failed
variant-dependent certificate{'child_parent': None, 'degree': 1, 'descendants': [7, 8, 100], 'mark': False, 'parent_children': [3], 'root_append': [2]}{'child_parent': None, 'degree': 1, 'descendants': [7, 8, 100], 'mark': False, 'parent_children': [3], 'root_append': [9, 2]}Failed

SHA-256 / bfb3e86bab71c8a77f78f4d4781edc748d8e6569788dc1ddf90752c981fa9145

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    c=d['child']; p=d['parent']; children=d['children']; roots=d['roots']; degree=d['degree']
    return {'parent_children': [x for x in children if x!=c],
    'root_append': roots+[p],
    'degree': degree-1,
    'child_parent': None,
    'mark': False,
    'descendants': d["descendants"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103, 104]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103, 104]})]][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{'child_parent': None, 'degree': 0, 'descendants': [], 'mark': False, 'parent_children': [], 'root_append': [9, 9]}{'child_parent': None, 'degree': 0, 'descendants': [], 'mark': False, 'parent_children': [], 'root_append': [9, 1]}Failed
regression certificate 2{'child_parent': None, 'degree': 2, 'descendants': [4, 5], 'mark': False, 'parent_children': [1, 3], 'root_append': [9, 8, 9]}{'child_parent': None, 'degree': 2, 'descendants': [4, 5], 'mark': False, 'parent_children': [1, 3], 'root_append': [9, 8, 2]}Failed
regression certificate 3{'child_parent': None, 'degree': 1, 'descendants': [3], 'mark': False, 'parent_children': [2], 'root_append': [9, 9]}{'child_parent': None, 'degree': 1, 'descendants': [3], 'mark': False, 'parent_children': [2], 'root_append': [9, 1]}Failed
regression certificate 4{'child_parent': None, 'degree': 2, 'descendants': [], 'mark': False, 'parent_children': [1, 2], 'root_append': [9, 7, 9]}{'child_parent': None, 'degree': 2, 'descendants': [], 'mark': False, 'parent_children': [1, 2], 'root_append': [9, 7, 3]}Failed
regression certificate 5{'child_parent': None, 'degree': 1, 'descendants': [1], 'mark': False, 'parent_children': [5], 'root_append': [9, 6, 9]}{'child_parent': None, 'degree': 1, 'descendants': [1], 'mark': False, 'parent_children': [5], 'root_append': [9, 6, 4]}Failed
regression certificate 6{'child_parent': None, 'degree': 1, 'descendants': [7, 8], 'mark': False, 'parent_children': [3], 'root_append': [9, 9]}{'child_parent': None, 'degree': 1, 'descendants': [7, 8], 'mark': False, 'parent_children': [3], 'root_append': [9, 2]}Failed
variant-dependent certificate{'child_parent': None, 'degree': 1, 'descendants': [7, 8, 100], 'mark': False, 'parent_children': [3], 'root_append': [9, 9]}{'child_parent': None, 'degree': 1, 'descendants': [7, 8, 100], 'mark': False, 'parent_children': [3], 'root_append': [9, 2]}Failed

SHA-256 / 44eb99d60ed147e21cb3301ed11d44be74f716f5a4b3423884f3967840b6eefe

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    c=d['child']; p=d['parent']; children=d['children']; roots=d['roots']; degree=d['degree']
    return {'parent_children': [x for x in children if x!=c],
    'root_append': roots+[c],
    'degree': degree-1,
    'child_parent': None,
    'mark': False,
    'descendants': d["descendants"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103]})], [({'child': 1, 'parent': 9, 'children': [1], 'roots': [9], 'degree': 1, 'mark': True, 'descendants': []}, {'parent_children': [], 'root_append': [9, 1], 'degree': 0, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 2, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 8], 'degree': 3, 'mark': True, 'descendants': [4, 5]}, {'parent_children': [1, 3], 'root_append': [9, 8, 2], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': [4, 5]}), ({'child': 1, 'parent': 9, 'children': [1, 2], 'roots': [9], 'degree': 2, 'mark': False, 'descendants': [3]}, {'parent_children': [2], 'root_append': [9, 1], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [3]}), ({'child': 3, 'parent': 9, 'children': [1, 2, 3], 'roots': [9, 7], 'degree': 3, 'mark': False, 'descendants': []}, {'parent_children': [1, 2], 'root_append': [9, 7, 3], 'degree': 2, 'child_parent': None, 'mark': False, 'descendants': []}), ({'child': 4, 'parent': 9, 'children': [4, 5], 'roots': [9, 6], 'degree': 2, 'mark': True, 'descendants': [1]}, {'parent_children': [5], 'root_append': [9, 6, 4], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [1]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8]}), ({'child': 2, 'parent': 9, 'children': [3, 2], 'roots': [9], 'degree': 2, 'mark': True, 'descendants': [7, 8, 100, 101, 102, 103, 104]}, {'parent_children': [3], 'root_append': [9, 2], 'degree': 1, 'child_parent': None, 'mark': False, 'descendants': [7, 8, 100, 101, 102, 103, 104]})]][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{'child_parent': None, 'degree': 0, 'descendants': [], 'mark': False, 'parent_children': [], 'root_append': [9, 1]}{'child_parent': None, 'degree': 0, 'descendants': [], 'mark': False, 'parent_children': [], 'root_append': [9, 1]}Passed
regression certificate 2{'child_parent': None, 'degree': 2, 'descendants': [4, 5], 'mark': False, 'parent_children': [1, 3], 'root_append': [9, 8, 2]}{'child_parent': None, 'degree': 2, 'descendants': [4, 5], 'mark': False, 'parent_children': [1, 3], 'root_append': [9, 8, 2]}Passed
regression certificate 3{'child_parent': None, 'degree': 1, 'descendants': [3], 'mark': False, 'parent_children': [2], 'root_append': [9, 1]}{'child_parent': None, 'degree': 1, 'descendants': [3], 'mark': False, 'parent_children': [2], 'root_append': [9, 1]}Passed
regression certificate 4{'child_parent': None, 'degree': 2, 'descendants': [], 'mark': False, 'parent_children': [1, 2], 'root_append': [9, 7, 3]}{'child_parent': None, 'degree': 2, 'descendants': [], 'mark': False, 'parent_children': [1, 2], 'root_append': [9, 7, 3]}Passed
regression certificate 5{'child_parent': None, 'degree': 1, 'descendants': [1], 'mark': False, 'parent_children': [5], 'root_append': [9, 6, 4]}{'child_parent': None, 'degree': 1, 'descendants': [1], 'mark': False, 'parent_children': [5], 'root_append': [9, 6, 4]}Passed
regression certificate 6{'child_parent': None, 'degree': 1, 'descendants': [7, 8], 'mark': False, 'parent_children': [3], 'root_append': [9, 2]}{'child_parent': None, 'degree': 1, 'descendants': [7, 8], 'mark': False, 'parent_children': [3], 'root_append': [9, 2]}Passed
variant-dependent certificate{'child_parent': None, 'degree': 1, 'descendants': [7, 8, 100], 'mark': False, 'parent_children': [3], 'root_append': [9, 2]}{'child_parent': None, 'degree': 1, 'descendants': [7, 8, 100], 'mark': False, 'parent_children': [3], 'root_append': [9, 2]}Passed

SHA-256 / 5229669fcf5ae1f2808440851d470ca9be2c093c0c8f60e9935a8dde5167c3d7

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

Case digest / 0a37a67c1fea3e2363e90138fb17bb4056a7562973686c3b0bfde84f6ed60df3