FAILURE MAP
← Case archive

FA-40996 / Heap invariants / Open access

Persistent heap prior snapshot retains every original path node including the target · case 01

The bounded persistent path copy certificate reports an incorrect old refs.

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

ROOT CAUSE

Persistent heap prior snapshot retains every original path node including the target.

VERIFIED REPAIR

Derive old refs using [[x,old] for x in path] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [[x,old] for x in path[:-1]] and still violates the stated relation.

Case contract

A persistent array-backed heap update supplies a root-to-target node-id path, off-path sibling ids, old node generations, and a new generation. Allocate one copy per path node, reconnect copied edges, share every sibling, and preserve old node references. Report allocated pairs, copied edges, shared ids, old generation list, new root reference, and target reference.

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):
    path=d['path']; siblings=d['siblings']; old=d['old_generation']; new=d['new_generation']; copies=[[x,new] for x in path]
    return {'allocations': copies,
    'edges': [[[path[i],new],[path[i+1],new]] for i in range(len(path)-1)],
    'shared': [[x,old] for x in siblings],
    'old_refs': [[x,new] for x in path],
    'root': [path[0],new] if path else None,
    'target': [path[-1],new] if path else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 10}, {'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'target': [100, 10]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 11}, {'allocations': [[5, 11], [3, 11], [100, 11], [101, 11]], 'edges': [[[5, 11], [3, 11]], [[3, 11], [100, 11]], [[100, 11], [101, 11]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2]], 'root': [5, 11], 'target': [101, 11]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 12}, {'allocations': [[5, 12], [3, 12], [100, 12], [101, 12], [102, 12]], 'edges': [[[5, 12], [3, 12]], [[3, 12], [100, 12]], [[100, 12], [101, 12]], [[101, 12], [102, 12]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2]], 'root': [5, 12], 'target': [102, 12]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 13}, {'allocations': [[5, 13], [3, 13], [100, 13], [101, 13], [102, 13], [103, 13]], 'edges': [[[5, 13], [3, 13]], [[3, 13], [100, 13]], [[100, 13], [101, 13]], [[101, 13], [102, 13]], [[102, 13], [103, 13]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2]], 'root': [5, 13], 'target': [103, 13]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103, 104], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 14}, {'allocations': [[5, 14], [3, 14], [100, 14], [101, 14], [102, 14], [103, 14], [104, 14]], 'edges': [[[5, 14], [3, 14]], [[3, 14], [100, 14]], [[100, 14], [101, 14]], [[101, 14], [102, 14]], [[102, 14], [103, 14]], [[103, 14], [104, 14]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2]], 'root': [5, 14], 'target': [104, 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 fixtureActualExpectedOutcome
regression certificate 1{'allocations': [], 'edges': [], 'old_refs': [], 'root': None, 'shared': [], 'target': None}{'allocations': [], 'edges': [], 'old_refs': [], 'root': None, 'shared': [], 'target': None}Passed
regression certificate 2{'allocations': [[1, 9]], 'edges': [], 'old_refs': [[1, 9]], 'root': [1, 9], 'shared': [], 'target': [1, 9]}{'allocations': [[1, 9]], 'edges': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'shared': [], 'target': [1, 9]}Failed
regression certificate 3{'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'old_refs': [[1, 9], [3, 9]], 'root': [1, 9], 'shared': [[2, 2]], 'target': [3, 9]}{'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'shared': [[2, 2]], 'target': [3, 9]}Failed
regression certificate 4{'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'old_refs': [[1, 9], [2, 9], [5, 9]], 'root': [1, 9], 'shared': [[3, 2], [4, 2]], 'target': [5, 9]}{'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'shared': [[3, 2], [4, 2]], 'target': [5, 9]}Failed
regression certificate 5{'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'old_refs': [[7, 9], [4, 9], [9, 9], [2, 9]], 'root': [7, 9], 'shared': [[8, 2], [5, 2], [1, 2]], 'target': [2, 9]}{'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'shared': [[8, 2], [5, 2], [1, 2]], 'target': [2, 9]}Failed
regression certificate 6{'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'old_refs': [[5, 9], [3, 9]], 'root': [5, 9], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [3, 9]}{'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [3, 9]}Failed
variant-dependent certificate{'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'old_refs': [[5, 10], [3, 10], [100, 10]], 'root': [5, 10], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [100, 10]}{'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [100, 10]}Failed

SHA-256 / 1b8973d2d51464186626bdef30f24f47a8c4cb07494ad400173248b873c2b109

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    path=d['path']; siblings=d['siblings']; old=d['old_generation']; new=d['new_generation']; copies=[[x,new] for x in path]
    return {'allocations': copies,
    'edges': [[[path[i],new],[path[i+1],new]] for i in range(len(path)-1)],
    'shared': [[x,old] for x in siblings],
    'old_refs': [[x,old] for x in path[:-1]],
    'root': [path[0],new] if path else None,
    'target': [path[-1],new] if path else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 10}, {'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'target': [100, 10]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 11}, {'allocations': [[5, 11], [3, 11], [100, 11], [101, 11]], 'edges': [[[5, 11], [3, 11]], [[3, 11], [100, 11]], [[100, 11], [101, 11]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2]], 'root': [5, 11], 'target': [101, 11]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 12}, {'allocations': [[5, 12], [3, 12], [100, 12], [101, 12], [102, 12]], 'edges': [[[5, 12], [3, 12]], [[3, 12], [100, 12]], [[100, 12], [101, 12]], [[101, 12], [102, 12]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2]], 'root': [5, 12], 'target': [102, 12]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 13}, {'allocations': [[5, 13], [3, 13], [100, 13], [101, 13], [102, 13], [103, 13]], 'edges': [[[5, 13], [3, 13]], [[3, 13], [100, 13]], [[100, 13], [101, 13]], [[101, 13], [102, 13]], [[102, 13], [103, 13]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2]], 'root': [5, 13], 'target': [103, 13]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103, 104], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 14}, {'allocations': [[5, 14], [3, 14], [100, 14], [101, 14], [102, 14], [103, 14], [104, 14]], 'edges': [[[5, 14], [3, 14]], [[3, 14], [100, 14]], [[100, 14], [101, 14]], [[101, 14], [102, 14]], [[102, 14], [103, 14]], [[103, 14], [104, 14]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2]], 'root': [5, 14], 'target': [104, 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 fixtureActualExpectedOutcome
regression certificate 1{'allocations': [], 'edges': [], 'old_refs': [], 'root': None, 'shared': [], 'target': None}{'allocations': [], 'edges': [], 'old_refs': [], 'root': None, 'shared': [], 'target': None}Passed
regression certificate 2{'allocations': [[1, 9]], 'edges': [], 'old_refs': [], 'root': [1, 9], 'shared': [], 'target': [1, 9]}{'allocations': [[1, 9]], 'edges': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'shared': [], 'target': [1, 9]}Failed
regression certificate 3{'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'old_refs': [[1, 2]], 'root': [1, 9], 'shared': [[2, 2]], 'target': [3, 9]}{'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'shared': [[2, 2]], 'target': [3, 9]}Failed
regression certificate 4{'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'old_refs': [[1, 2], [2, 2]], 'root': [1, 9], 'shared': [[3, 2], [4, 2]], 'target': [5, 9]}{'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'shared': [[3, 2], [4, 2]], 'target': [5, 9]}Failed
regression certificate 5{'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'old_refs': [[7, 2], [4, 2], [9, 2]], 'root': [7, 9], 'shared': [[8, 2], [5, 2], [1, 2]], 'target': [2, 9]}{'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'shared': [[8, 2], [5, 2], [1, 2]], 'target': [2, 9]}Failed
regression certificate 6{'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'old_refs': [[5, 2]], 'root': [5, 9], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [3, 9]}{'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [3, 9]}Failed
variant-dependent certificate{'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 10], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [100, 10]}{'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [100, 10]}Failed

SHA-256 / 48b01da59ded819ac00e76d767d035f9b055f7fdb31b8495c0c351d7968e5930

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    path=d['path']; siblings=d['siblings']; old=d['old_generation']; new=d['new_generation']; copies=[[x,new] for x in path]
    return {'allocations': copies,
    'edges': [[[path[i],new],[path[i+1],new]] for i in range(len(path)-1)],
    'shared': [[x,old] for x in siblings],
    'old_refs': [[x,old] for x in path],
    'root': [path[0],new] if path else None,
    'target': [path[-1],new] if path else None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 10}, {'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'target': [100, 10]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 11}, {'allocations': [[5, 11], [3, 11], [100, 11], [101, 11]], 'edges': [[[5, 11], [3, 11]], [[3, 11], [100, 11]], [[100, 11], [101, 11]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2]], 'root': [5, 11], 'target': [101, 11]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 12}, {'allocations': [[5, 12], [3, 12], [100, 12], [101, 12], [102, 12]], 'edges': [[[5, 12], [3, 12]], [[3, 12], [100, 12]], [[100, 12], [101, 12]], [[101, 12], [102, 12]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2]], 'root': [5, 12], 'target': [102, 12]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 13}, {'allocations': [[5, 13], [3, 13], [100, 13], [101, 13], [102, 13], [103, 13]], 'edges': [[[5, 13], [3, 13]], [[3, 13], [100, 13]], [[100, 13], [101, 13]], [[101, 13], [102, 13]], [[102, 13], [103, 13]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2]], 'root': [5, 13], 'target': [103, 13]})], [({'path': [], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [], 'edges': [], 'shared': [], 'old_refs': [], 'root': None, 'target': None}), ({'path': [1], 'siblings': [], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9]], 'edges': [], 'shared': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'target': [1, 9]}), ({'path': [1, 3], 'siblings': [2], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'shared': [[2, 2]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'target': [3, 9]}), ({'path': [1, 2, 5], 'siblings': [3, 4], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'shared': [[3, 2], [4, 2]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'target': [5, 9]}), ({'path': [7, 4, 9, 2], 'siblings': [8, 5, 1], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'shared': [[8, 2], [5, 2], [1, 2]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'target': [2, 9]}), ({'path': [5, 3], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 9}, {'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'target': [3, 9]}), ({'path': [5, 3, 100, 101, 102, 103, 104], 'siblings': [8, 2, 9], 'old_generation': 2, 'new_generation': 14}, {'allocations': [[5, 14], [3, 14], [100, 14], [101, 14], [102, 14], [103, 14], [104, 14]], 'edges': [[[5, 14], [3, 14]], [[3, 14], [100, 14]], [[100, 14], [101, 14]], [[101, 14], [102, 14]], [[102, 14], [103, 14]], [[103, 14], [104, 14]]], 'shared': [[8, 2], [2, 2], [9, 2]], 'old_refs': [[5, 2], [3, 2], [100, 2], [101, 2], [102, 2], [103, 2], [104, 2]], 'root': [5, 14], 'target': [104, 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 fixtureActualExpectedOutcome
regression certificate 1{'allocations': [], 'edges': [], 'old_refs': [], 'root': None, 'shared': [], 'target': None}{'allocations': [], 'edges': [], 'old_refs': [], 'root': None, 'shared': [], 'target': None}Passed
regression certificate 2{'allocations': [[1, 9]], 'edges': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'shared': [], 'target': [1, 9]}{'allocations': [[1, 9]], 'edges': [], 'old_refs': [[1, 2]], 'root': [1, 9], 'shared': [], 'target': [1, 9]}Passed
regression certificate 3{'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'shared': [[2, 2]], 'target': [3, 9]}{'allocations': [[1, 9], [3, 9]], 'edges': [[[1, 9], [3, 9]]], 'old_refs': [[1, 2], [3, 2]], 'root': [1, 9], 'shared': [[2, 2]], 'target': [3, 9]}Passed
regression certificate 4{'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'shared': [[3, 2], [4, 2]], 'target': [5, 9]}{'allocations': [[1, 9], [2, 9], [5, 9]], 'edges': [[[1, 9], [2, 9]], [[2, 9], [5, 9]]], 'old_refs': [[1, 2], [2, 2], [5, 2]], 'root': [1, 9], 'shared': [[3, 2], [4, 2]], 'target': [5, 9]}Passed
regression certificate 5{'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'shared': [[8, 2], [5, 2], [1, 2]], 'target': [2, 9]}{'allocations': [[7, 9], [4, 9], [9, 9], [2, 9]], 'edges': [[[7, 9], [4, 9]], [[4, 9], [9, 9]], [[9, 9], [2, 9]]], 'old_refs': [[7, 2], [4, 2], [9, 2], [2, 2]], 'root': [7, 9], 'shared': [[8, 2], [5, 2], [1, 2]], 'target': [2, 9]}Passed
regression certificate 6{'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [3, 9]}{'allocations': [[5, 9], [3, 9]], 'edges': [[[5, 9], [3, 9]]], 'old_refs': [[5, 2], [3, 2]], 'root': [5, 9], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [3, 9]}Passed
variant-dependent certificate{'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [100, 10]}{'allocations': [[5, 10], [3, 10], [100, 10]], 'edges': [[[5, 10], [3, 10]], [[3, 10], [100, 10]]], 'old_refs': [[5, 2], [3, 2], [100, 2]], 'root': [5, 10], 'shared': [[8, 2], [2, 2], [9, 2]], 'target': [100, 10]}Passed

SHA-256 / 0ee84f6e732d67db463e34e940ddc5d507082054d7d85e7a14a60771230da9a1

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

Case digest / 698e1d57bd1b6d8d32eada27bf682cc1973b4e3ddccf2d6363febbf7f59d6c38