FAILURE MAP
← Case archive

FA-40106 / Heap invariants / Open access

Fibonacci cut preserves the promoted subtree without absorbing its former parent · case 01

The bounded fibonacci cut certificate reports an incorrect descendants.

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

ROOT CAUSE

Fibonacci cut preserves the promoted subtree without absorbing its former parent.

VERIFIED REPAIR

Derive descendants using d["descendants"] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses d["descendants"]+[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': roots+[c],
    'degree': degree-1,
    'child_parent': None,
    'mark': False,
    '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': [], '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]}Failed
regression certificate 3{'child_parent': None, 'degree': 1, 'descendants': [], '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]}Failed
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': [], '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]}Failed
regression certificate 6{'child_parent': None, 'degree': 1, 'descendants': [], '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]}Failed
variant-dependent certificate{'child_parent': None, 'degree': 1, 'descendants': [], '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]}Failed

SHA-256 / faa903d10781f3141559bc93cc0b0dc37651d28c0f2debd73081498b8c4bfecf

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+[c],
    'degree': degree-1,
    'child_parent': None,
    'mark': False,
    'descendants': d["descendants"]+[p]}
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': [9], 'mark': False, 'parent_children': [], 'root_append': [9, 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, 9], '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]}Failed
regression certificate 3{'child_parent': None, 'degree': 1, 'descendants': [3, 9], '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]}Failed
regression certificate 4{'child_parent': None, 'degree': 2, 'descendants': [9], '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]}Failed
regression certificate 5{'child_parent': None, 'degree': 1, 'descendants': [1, 9], '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]}Failed
regression certificate 6{'child_parent': None, 'degree': 1, 'descendants': [7, 8, 9], '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]}Failed
variant-dependent certificate{'child_parent': None, 'degree': 1, 'descendants': [7, 8, 100, 9], '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]}Failed

SHA-256 / 01e952e2baba1b3a8178503e7f292fbb30fef37b402656e53ac793ba3f6c3f86

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

Case digest / 3e8d4947d66c273bd26eeb616446caaa0fd7ab9d99dd619f520f1aae3dbe14e4