FAILURE MAP
← Case archive

FA-39871 / Heap invariants / Open access

Fibonacci ring traversal verifies only one reciprocal link · case 01

The bounded fibonacci rings certificate reports an incorrect reciprocity.

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

ROOT CAUSE

Both neighboring ring pointers must refer back to this node.

VERIFIED REPAIR

Derive reciprocity using [i for i,x in enumerate(a) if a[x[2]][3]!=i or a[x[3]][2]!=i] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [i for i,x in enumerate(a) if a[x[2]][3]!=i and a[x[3]][2]!=i] and still violates the stated relation.

Case contract

A finite Fibonacci-ring certificate stores nodes [key,parent,left,right,degree,mark,children]. All references are in range or parent=-1. Report broken circular-link reciprocity, parent-child backlinks, degree mismatch, marked roots, roots, and designated minimum validity.

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']; m=d['minimum']; n=len(a)
    return {'reciprocity': [i for i,x in enumerate(a) if a[x[2]][3]!=i],
    'backlinks': [[i,j] for i,x in enumerate(a) for j in x[6] if a[j][1]!=i],
    'degrees': [i for i,x in enumerate(a) if x[4]!=len(x[6])],
    'root_marks': [i for i,x in enumerate(a) if x[1]==-1 and x[5]],
    'root_ids': [i for i,x in enumerate(a) if x[1]==-1],
    'minimum_valid': m is None if not a else (m is not None and a[m][1]==-1 and all(a[m][0]<=x[0] for x in a if x[1]==-1))}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[10, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[11, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[12, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[13, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[14, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})]][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{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}Passed
regression certificate 2{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Passed
regression certificate 3{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Passed
regression certificate 4{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [0, 1], 'root_marks': [0]}{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [0, 1], 'root_marks': [0]}Passed
regression certificate 5{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [1], 'root_ids': [0, 2], 'root_marks': [0, 2]}{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [1, 2], 'root_ids': [0, 2], 'root_marks': [0, 2]}Failed
regression certificate 6{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [1, 2], 'root_ids': [0, 2], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Failed
variant-dependent certificate{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [1, 2], 'root_ids': [0, 2], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Failed

SHA-256 / 632e30a86994c652d9049c7aa9b63f7ff69df6842e940163bf2f7ae4be4f66f3

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']; m=d['minimum']; n=len(a)
    return {'reciprocity': [i for i,x in enumerate(a) if a[x[2]][3]!=i and a[x[3]][2]!=i],
    'backlinks': [[i,j] for i,x in enumerate(a) for j in x[6] if a[j][1]!=i],
    'degrees': [i for i,x in enumerate(a) if x[4]!=len(x[6])],
    'root_marks': [i for i,x in enumerate(a) if x[1]==-1 and x[5]],
    'root_ids': [i for i,x in enumerate(a) if x[1]==-1],
    'minimum_valid': m is None if not a else (m is not None and a[m][1]==-1 and all(a[m][0]<=x[0] for x in a if x[1]==-1))}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[10, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[11, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[12, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[13, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[14, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})]][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{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}Passed
regression certificate 2{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Passed
regression certificate 3{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Passed
regression certificate 4{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [0, 1], 'root_marks': [0]}{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [0, 1], 'root_marks': [0]}Passed
regression certificate 5{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [0, 2], 'root_marks': [0, 2]}{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [1, 2], 'root_ids': [0, 2], 'root_marks': [0, 2]}Failed
regression certificate 6{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [1], 'root_ids': [0, 2], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Failed
variant-dependent certificate{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [1], 'root_ids': [0, 2], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Failed

SHA-256 / a5db85d59a152527cdb3ca55cc53524a369c0d1a06d856ab2fb1b64544b5e426

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']; m=d['minimum']; n=len(a)
    return {'reciprocity': [i for i,x in enumerate(a) if a[x[2]][3]!=i or a[x[3]][2]!=i],
    'backlinks': [[i,j] for i,x in enumerate(a) for j in x[6] if a[j][1]!=i],
    'degrees': [i for i,x in enumerate(a) if x[4]!=len(x[6])],
    'root_marks': [i for i,x in enumerate(a) if x[1]==-1 and x[5]],
    'root_ids': [i for i,x in enumerate(a) if x[1]==-1],
    'minimum_valid': m is None if not a else (m is not None and a[m][1]==-1 and all(a[m][0]<=x[0] for x in a if x[1]==-1))}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[10, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[11, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[12, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[13, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})], [({'nodes': [], 'minimum': None}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [], 'minimum_valid': True}), ({'nodes': [[5, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[4, -1, 0, 0, 2, False, [1, 2]], [6, 0, 2, 2, 0, False, []], [8, 0, 1, 1, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [], 'root_ids': [0], 'minimum_valid': True}), ({'nodes': [[8, -1, 1, 1, 0, True, []], [2, -1, 0, 0, 0, False, []]], 'minimum': 0}, {'reciprocity': [], 'backlinks': [], 'degrees': [], 'root_marks': [0], 'root_ids': [0, 1], 'minimum_valid': False}), ({'nodes': [[7, -1, 0, 0, 1, True, [1, 2]], [1, 0, 1, 2, 0, False, []], [4, -1, 1, 2, 2, True, []]], 'minimum': 1}, {'reciprocity': [1, 2], 'backlinks': [[0, 2]], 'degrees': [0, 2], 'root_marks': [0, 2], 'root_ids': [0, 2], 'minimum_valid': False}), ({'nodes': [[9, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True}), ({'nodes': [[14, -1, 2, 1, 3, False, [1]], [4, 2, 1, 2, 1, True, []], [3, -1, 0, 0, 1, True, [0]]], 'minimum': 2}, {'reciprocity': [0, 1, 2], 'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'root_marks': [2], 'root_ids': [0, 2], 'minimum_valid': True})]][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{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [], 'root_marks': []}Passed
regression certificate 2{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Passed
regression certificate 3{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}{'backlinks': [], 'degrees': [], 'minimum_valid': True, 'reciprocity': [], 'root_ids': [0], 'root_marks': []}Passed
regression certificate 4{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [0, 1], 'root_marks': [0]}{'backlinks': [], 'degrees': [], 'minimum_valid': False, 'reciprocity': [], 'root_ids': [0, 1], 'root_marks': [0]}Passed
regression certificate 5{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [1, 2], 'root_ids': [0, 2], 'root_marks': [0, 2]}{'backlinks': [[0, 2]], 'degrees': [0, 2], 'minimum_valid': False, 'reciprocity': [1, 2], 'root_ids': [0, 2], 'root_marks': [0, 2]}Passed
regression certificate 6{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Passed
variant-dependent certificate{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}{'backlinks': [[0, 1], [2, 0]], 'degrees': [0, 1], 'minimum_valid': True, 'reciprocity': [0, 1, 2], 'root_ids': [0, 2], 'root_marks': [2]}Passed

SHA-256 / 98b9b085ea8e95b93b4acbd57a088b174d4d9092298dde96afeb44994d4e7b17

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

Case digest / 7285b0ec270960fcf7259034e77df9d34403e6d0543d5f9889a439b92eb44b43