FA-40746 / Heap invariants / Open access

Min-max trickle repairs the displaced key against the intervening max-level parent · case 01

The bounded minmax grandchild step certificate reports an incorrect grandchild key.

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

ROOT CAUSE

Min-max trickle repairs the displaced key against the intervening max-level parent.

VERIFIED REPAIR

Derive grandchild key using gc under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses g and still violates the stated relation.

Case contract

A minimum-level trickle step receives current key x, chosen grandchild key g, its parent key p, and ids. After swapping x with smaller g, x at the grandchild must also be no greater than its maximum-level parent; if x>p exchange those two. Return root key, grandchild key, parent key, cross-level correction flag, two-step trace, and preserved multiset.

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):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': x if descend else g,
    'parent_key': parent,
    'correction': correction,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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 fixture	Actual	Expected	Outcome
regression certificate 1	`{'correction': True, 'grandchild_key': 9, 'multiset': [2, 7, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	`{'correction': True, 'grandchild_key': 7, 'multiset': [2, 7, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	Failed
regression certificate 2	`{'correction': False, 'grandchild_key': 5, 'multiset': [1, 5, 8], 'parent_key': 8, 'root_key': 1, 'trace': ['grandchild']}`	`{'correction': False, 'grandchild_key': 5, 'multiset': [1, 5, 8], 'parent_key': 8, 'root_key': 1, 'trace': ['grandchild']}`	Passed
regression certificate 3	`{'correction': False, 'grandchild_key': 4, 'multiset': [3, 4, 8], 'parent_key': 8, 'root_key': 3, 'trace': []}`	`{'correction': False, 'grandchild_key': 4, 'multiset': [3, 4, 8], 'parent_key': 8, 'root_key': 3, 'trace': []}`	Passed
regression certificate 4	`{'correction': False, 'grandchild_key': 7, 'multiset': [2, 7, 7], 'parent_key': 7, 'root_key': 2, 'trace': ['grandchild']}`	`{'correction': False, 'grandchild_key': 7, 'multiset': [2, 7, 7], 'parent_key': 7, 'root_key': 2, 'trace': ['grandchild']}`	Passed
regression certificate 5	`{'correction': False, 'grandchild_key': 4, 'multiset': [4, 4, 9], 'parent_key': 9, 'root_key': 4, 'trace': []}`	`{'correction': False, 'grandchild_key': 4, 'multiset': [4, 4, 9], 'parent_key': 9, 'root_key': 4, 'trace': []}`	Passed
regression certificate 6	`{'correction': True, 'grandchild_key': 9, 'multiset': [2, 2, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	`{'correction': True, 'grandchild_key': 2, 'multiset': [2, 2, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	Failed
variant-dependent certificate	`{'correction': True, 'grandchild_key': 10, 'multiset': [2, 2, 10], 'parent_key': 10, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	`{'correction': True, 'grandchild_key': 2, 'multiset': [2, 2, 10], 'parent_key': 10, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	Failed

SHA-256 / ff256d430fb9e852ae36a28f61ac0b6a3e791b39e0e09e8b27b39e436c79c3e5

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(d):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': g,
    'parent_key': parent,
    'correction': correction,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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 fixture	Actual	Expected	Outcome
regression certificate 1	`{'correction': True, 'grandchild_key': 2, 'multiset': [2, 7, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	`{'correction': True, 'grandchild_key': 7, 'multiset': [2, 7, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	Failed
regression certificate 2	`{'correction': False, 'grandchild_key': 1, 'multiset': [1, 5, 8], 'parent_key': 8, 'root_key': 1, 'trace': ['grandchild']}`	`{'correction': False, 'grandchild_key': 5, 'multiset': [1, 5, 8], 'parent_key': 8, 'root_key': 1, 'trace': ['grandchild']}`	Failed
regression certificate 3	`{'correction': False, 'grandchild_key': 4, 'multiset': [3, 4, 8], 'parent_key': 8, 'root_key': 3, 'trace': []}`	`{'correction': False, 'grandchild_key': 4, 'multiset': [3, 4, 8], 'parent_key': 8, 'root_key': 3, 'trace': []}`	Passed
regression certificate 4	`{'correction': False, 'grandchild_key': 2, 'multiset': [2, 7, 7], 'parent_key': 7, 'root_key': 2, 'trace': ['grandchild']}`	`{'correction': False, 'grandchild_key': 7, 'multiset': [2, 7, 7], 'parent_key': 7, 'root_key': 2, 'trace': ['grandchild']}`	Failed
regression certificate 5	`{'correction': False, 'grandchild_key': 4, 'multiset': [4, 4, 9], 'parent_key': 9, 'root_key': 4, 'trace': []}`	`{'correction': False, 'grandchild_key': 4, 'multiset': [4, 4, 9], 'parent_key': 9, 'root_key': 4, 'trace': []}`	Passed
regression certificate 6	`{'correction': True, 'grandchild_key': 2, 'multiset': [2, 2, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	`{'correction': True, 'grandchild_key': 2, 'multiset': [2, 2, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	Passed
variant-dependent certificate	`{'correction': True, 'grandchild_key': 2, 'multiset': [2, 2, 10], 'parent_key': 10, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	`{'correction': True, 'grandchild_key': 2, 'multiset': [2, 2, 10], 'parent_key': 10, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	Passed

SHA-256 / 7b227fb89a43e33c6eedad1bce389d016beea65287f33eb0882513130df1e458

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(d):
    x=d['x']; g=d['g']; p=d['p']; descend=g<x; correction=descend and x>p
    root=g if descend else x; gc=(p if correction else x) if descend else g; parent=x if correction else p
    return {'root_key': root,
    'grandchild_key': gc,
    'parent_key': parent,
    'correction': correction,
    'trace': (["grandchild"]+["parent"] if correction else ["grandchild"]) if descend else [],
    'multiset': sorted([root,gc,parent])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 10, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 10, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 10]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 11, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 11, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 11]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 12, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 12, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 12]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 13, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 13, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 13]})], [({'x': 9, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 7, 9]}), ({'x': 5, 'g': 1, 'p': 8}, {'root_key': 1, 'grandchild_key': 5, 'parent_key': 8, 'correction': False, 'trace': ['grandchild'], 'multiset': [1, 5, 8]}), ({'x': 3, 'g': 4, 'p': 8}, {'root_key': 3, 'grandchild_key': 4, 'parent_key': 8, 'correction': False, 'trace': [], 'multiset': [3, 4, 8]}), ({'x': 7, 'g': 2, 'p': 7}, {'root_key': 2, 'grandchild_key': 7, 'parent_key': 7, 'correction': False, 'trace': ['grandchild'], 'multiset': [2, 7, 7]}), ({'x': 4, 'g': 4, 'p': 9}, {'root_key': 4, 'grandchild_key': 4, 'parent_key': 9, 'correction': False, 'trace': [], 'multiset': [4, 4, 9]}), ({'x': 9, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 9, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 9]}), ({'x': 14, 'g': 2, 'p': 2}, {'root_key': 2, 'grandchild_key': 2, 'parent_key': 14, 'correction': True, 'trace': ['grandchild', 'parent'], 'multiset': [2, 2, 14]})]][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 fixture	Actual	Expected	Outcome
regression certificate 1	`{'correction': True, 'grandchild_key': 7, 'multiset': [2, 7, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	`{'correction': True, 'grandchild_key': 7, 'multiset': [2, 7, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	Passed
regression certificate 2	`{'correction': False, 'grandchild_key': 5, 'multiset': [1, 5, 8], 'parent_key': 8, 'root_key': 1, 'trace': ['grandchild']}`	`{'correction': False, 'grandchild_key': 5, 'multiset': [1, 5, 8], 'parent_key': 8, 'root_key': 1, 'trace': ['grandchild']}`	Passed
regression certificate 3	`{'correction': False, 'grandchild_key': 4, 'multiset': [3, 4, 8], 'parent_key': 8, 'root_key': 3, 'trace': []}`	`{'correction': False, 'grandchild_key': 4, 'multiset': [3, 4, 8], 'parent_key': 8, 'root_key': 3, 'trace': []}`	Passed
regression certificate 4	`{'correction': False, 'grandchild_key': 7, 'multiset': [2, 7, 7], 'parent_key': 7, 'root_key': 2, 'trace': ['grandchild']}`	`{'correction': False, 'grandchild_key': 7, 'multiset': [2, 7, 7], 'parent_key': 7, 'root_key': 2, 'trace': ['grandchild']}`	Passed
regression certificate 5	`{'correction': False, 'grandchild_key': 4, 'multiset': [4, 4, 9], 'parent_key': 9, 'root_key': 4, 'trace': []}`	`{'correction': False, 'grandchild_key': 4, 'multiset': [4, 4, 9], 'parent_key': 9, 'root_key': 4, 'trace': []}`	Passed
regression certificate 6	`{'correction': True, 'grandchild_key': 2, 'multiset': [2, 2, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	`{'correction': True, 'grandchild_key': 2, 'multiset': [2, 2, 9], 'parent_key': 9, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	Passed
variant-dependent certificate	`{'correction': True, 'grandchild_key': 2, 'multiset': [2, 2, 10], 'parent_key': 10, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	`{'correction': True, 'grandchild_key': 2, 'multiset': [2, 2, 10], 'parent_key': 10, 'root_key': 2, 'trace': ['grandchild', 'parent']}`	Passed

SHA-256 / c7ef9a607a1b957a6bbfa7c13afb7b24afdfc823e4fbebb7882279aaac41e1c0

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

Case digest / 2177d1933e68bc9f000b529a4d29386d9b2870331598dead6cf9d0c32807d8ad