FAILURE MAP
← Case archive

FA-39956 / Heap invariants / Open access

Pairing degree counts only the first child pointer · case 01

The bounded pairing siblings certificate reports an incorrect degrees.

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

ROOT CAUSE

The full sibling chain contains direct children, including its first member.

VERIFIED REPAIR

Derive degrees using [len(c) for c in chains] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [max(0,len(c)-1) for c in chains] and still violates the stated relation.

Case contract

Pairing-tree certificate nodes are [key,parent,first_child,next_sibling,previous]. Missing links are -1. Previous denotes parent for first child, prior sibling otherwise. Report first-child backlinks, sibling-parent disagreements, previous-link disagreements, root sibling violations, direct heap-order violations, and child-chain degrees (stop on cycles).

Why this case matters

This isolates an internal heap representation or priority-structure invariant using deterministic finite records.

1 / The failure

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

N = 1
observations = []
def solve(d):
    a=d['nodes']; root=d['root']; chains=[]
    for i,x in enumerate(a):
        chain=[]; j=x[2]
        while j!=-1 and j not in chain:
            chain.append(j); j=a[j][3]
        chains.append(chain)
    return {'first_previous': [i for i,x in enumerate(a) if x[2]!=-1 and a[x[2]][4]!=i],
    'sibling_parent': [i for i,x in enumerate(a) if x[3]!=-1 and a[x[3]][1]!=x[1]],
    'sibling_previous': [i for i,x in enumerate(a) if x[3]!=-1 and a[x[3]][4]!=i],
    'root_links': [] if root==-1 else [k for k in (1,3,4) if a[root][k]!=-1],
    'child_order': [[i,j] for i,c in enumerate(chains) for j in c if a[j][0]<a[i][0]],
    'degrees': [int(bool(c)) for c in chains]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[9, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[10, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[11, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[12, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
regression certificate 1{'child_order': [], 'degrees': [], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}{'child_order': [], 'degrees': [], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}Passed
regression certificate 2{'child_order': [], 'degrees': [0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}{'child_order': [], 'degrees': [0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}Passed
regression certificate 3{'child_order': [], 'degrees': [1, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}{'child_order': [], 'degrees': [2, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}Failed
regression certificate 4{'child_order': [[0, 2]], 'degrees': [1, 0, 0], 'first_previous': [0], 'root_links': [], 'sibling_parent': [1], 'sibling_previous': [1]}{'child_order': [[0, 2]], 'degrees': [2, 0, 0], 'first_previous': [0], 'root_links': [], 'sibling_parent': [1], 'sibling_previous': [1]}Failed
regression certificate 5{'child_order': [], 'degrees': [0, 1, 0], 'first_previous': [1], 'root_links': [3, 4], 'sibling_parent': [], 'sibling_previous': [1]}{'child_order': [], 'degrees': [0, 1, 0], 'first_previous': [1], 'root_links': [3, 4], 'sibling_parent': [], 'sibling_previous': [1]}Passed
regression certificate 6{'child_order': [[0, 1], [0, 3]], 'degrees': [1, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}{'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}Failed
variant-dependent certificate{'child_order': [[0, 1], [0, 3]], 'degrees': [1, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}{'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}Failed

SHA-256 / c386ad2663c64d43a2897bb55906a34071c6e800e8644842d6bb744704429ed4

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    a=d['nodes']; root=d['root']; chains=[]
    for i,x in enumerate(a):
        chain=[]; j=x[2]
        while j!=-1 and j not in chain:
            chain.append(j); j=a[j][3]
        chains.append(chain)
    return {'first_previous': [i for i,x in enumerate(a) if x[2]!=-1 and a[x[2]][4]!=i],
    'sibling_parent': [i for i,x in enumerate(a) if x[3]!=-1 and a[x[3]][1]!=x[1]],
    'sibling_previous': [i for i,x in enumerate(a) if x[3]!=-1 and a[x[3]][4]!=i],
    'root_links': [] if root==-1 else [k for k in (1,3,4) if a[root][k]!=-1],
    'child_order': [[i,j] for i,c in enumerate(chains) for j in c if a[j][0]<a[i][0]],
    'degrees': [max(0,len(c)-1) for c in chains]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[9, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[10, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[11, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[12, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
regression certificate 1{'child_order': [], 'degrees': [], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}{'child_order': [], 'degrees': [], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}Passed
regression certificate 2{'child_order': [], 'degrees': [0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}{'child_order': [], 'degrees': [0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}Passed
regression certificate 3{'child_order': [], 'degrees': [1, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}{'child_order': [], 'degrees': [2, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}Failed
regression certificate 4{'child_order': [[0, 2]], 'degrees': [1, 0, 0], 'first_previous': [0], 'root_links': [], 'sibling_parent': [1], 'sibling_previous': [1]}{'child_order': [[0, 2]], 'degrees': [2, 0, 0], 'first_previous': [0], 'root_links': [], 'sibling_parent': [1], 'sibling_previous': [1]}Failed
regression certificate 5{'child_order': [], 'degrees': [0, 0, 0], 'first_previous': [1], 'root_links': [3, 4], 'sibling_parent': [], 'sibling_previous': [1]}{'child_order': [], 'degrees': [0, 1, 0], 'first_previous': [1], 'root_links': [3, 4], 'sibling_parent': [], 'sibling_previous': [1]}Failed
regression certificate 6{'child_order': [[0, 1], [0, 3]], 'degrees': [2, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}{'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}Failed
variant-dependent certificate{'child_order': [[0, 1], [0, 3]], 'degrees': [2, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}{'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}Failed

SHA-256 / 861f30ebb1cc974bc09cf2527d53d289bc508283d04523557c709281b0827359

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    a=d['nodes']; root=d['root']; chains=[]
    for i,x in enumerate(a):
        chain=[]; j=x[2]
        while j!=-1 and j not in chain:
            chain.append(j); j=a[j][3]
        chains.append(chain)
    return {'first_previous': [i for i,x in enumerate(a) if x[2]!=-1 and a[x[2]][4]!=i],
    'sibling_parent': [i for i,x in enumerate(a) if x[3]!=-1 and a[x[3]][1]!=x[1]],
    'sibling_previous': [i for i,x in enumerate(a) if x[3]!=-1 and a[x[3]][4]!=i],
    'root_links': [] if root==-1 else [k for k in (1,3,4) if a[root][k]!=-1],
    'child_order': [[i,j] for i,c in enumerate(chains) for j in c if a[j][0]<a[i][0]],
    'degrees': [len(c) for c in chains]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[9, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[10, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[11, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})], [({'nodes': [], 'root': -1}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': []}), ({'nodes': [[2, -1, -1, -1, -1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [0]}), ({'nodes': [[1, -1, 1, -1, -1], [7, 0, -1, 2, 0], [3, 0, -1, -1, 1]], 'root': 0}, {'first_previous': [], 'sibling_parent': [], 'sibling_previous': [], 'root_links': [], 'child_order': [], 'degrees': [2, 0, 0]}), ({'nodes': [[8, -1, 1, -1, -1], [9, 0, -1, 2, -1], [2, 1, -1, -1, 0]], 'root': 0}, {'first_previous': [0], 'sibling_parent': [1], 'sibling_previous': [1], 'root_links': [], 'child_order': [[0, 2]], 'degrees': [2, 0, 0]}), ({'nodes': [[1, -1, -1, -1, -1], [4, -1, 2, 0, 0], [4, 1, -1, -1, -1]], 'root': 1}, {'first_previous': [1], 'sibling_parent': [], 'sibling_previous': [1], 'root_links': [3, 4], 'child_order': [], 'degrees': [0, 1, 0]}), ({'nodes': [[7, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0]}), ({'nodes': [[12, -1, 1, -1, -1], [2, 0, -1, 2, 0], [8, -1, -1, 3, -1], [1, 0, -1, -1, 0]], 'root': 0}, {'first_previous': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2], 'root_links': [], 'child_order': [[0, 1], [0, 2], [0, 3]], 'degrees': [3, 0, 0, 0]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
regression certificate 1{'child_order': [], 'degrees': [], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}{'child_order': [], 'degrees': [], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}Passed
regression certificate 2{'child_order': [], 'degrees': [0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}{'child_order': [], 'degrees': [0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}Passed
regression certificate 3{'child_order': [], 'degrees': [2, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}{'child_order': [], 'degrees': [2, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [], 'sibling_previous': []}Passed
regression certificate 4{'child_order': [[0, 2]], 'degrees': [2, 0, 0], 'first_previous': [0], 'root_links': [], 'sibling_parent': [1], 'sibling_previous': [1]}{'child_order': [[0, 2]], 'degrees': [2, 0, 0], 'first_previous': [0], 'root_links': [], 'sibling_parent': [1], 'sibling_previous': [1]}Passed
regression certificate 5{'child_order': [], 'degrees': [0, 1, 0], 'first_previous': [1], 'root_links': [3, 4], 'sibling_parent': [], 'sibling_previous': [1]}{'child_order': [], 'degrees': [0, 1, 0], 'first_previous': [1], 'root_links': [3, 4], 'sibling_parent': [], 'sibling_previous': [1]}Passed
regression certificate 6{'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}{'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}Passed
variant-dependent certificate{'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}{'child_order': [[0, 1], [0, 3]], 'degrees': [3, 0, 0, 0], 'first_previous': [], 'root_links': [], 'sibling_parent': [1, 2], 'sibling_previous': [1, 2]}Passed

SHA-256 / c1da3dd990cdebd93e1c96c1808c57fca8226f272076f0500db19507ec380abd

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

Case digest / f2bba8967fd502e67d5abda5882ff9ee8de08e5f4359929af906735283f07ae2