FAILURE MAP
← Case archive

FA-41201 / Heap invariants / Open access

Paged heap children may cross page boundaries and require global indexing · case 01

The bounded paged heap layout certificate reports an incorrect children.

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

ROOT CAUSE

Paged heap children may cross page boundaries and require global indexing.

VERIFIED REPAIR

Derive children using [address(j) for j in children] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [address(2*i)] if 2*i<n else [] and still violates the stated relation.

Case contract

A binary heap is stored in fixed-size pages of B slots using zero-based global indices. For n logical members and selected live index i report its page/offset, parent address or None, child addresses, allocated page count, last-page live occupancy, and pages touched by reading i and its existing children. B>=1 and 0<=i<n.

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):
    n=d['size']; b=d['page_size']; i=d['index']; children=[j for j in (2*i+1,2*i+2) if j<n]
    def address(j): return [j//b,j%b]
    return {'address': address(i),
    'parent': None if i==0 else address((i-1)//2),
    'children': [[i//b,2*(i%b)+k] for k in (1,2) if 2*i+k<n],
    'pages': (n+b-1)//b,
    'tail_occupancy': (n-1)%b+1,
    'touched': sorted({j//b for j in [i]+children})}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 11, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 12, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 3, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 13, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 1, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 14, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 15, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 3, 'touched': [1, 3]})]][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{'address': [0, 0], 'children': [], 'pages': 1, 'parent': None, 'tail_occupancy': 1, 'touched': [0]}{'address': [0, 0], 'children': [], 'pages': 1, 'parent': None, 'tail_occupancy': 1, 'touched': [0]}Passed
regression certificate 2{'address': [0, 3], 'children': [[0, 7]], 'pages': 2, 'parent': [0, 1], 'tail_occupancy': 4, 'touched': [0, 1]}{'address': [0, 3], 'children': [[1, 3]], 'pages': 2, 'parent': [0, 1], 'tail_occupancy': 4, 'touched': [0, 1]}Failed
regression certificate 3{'address': [0, 2], 'children': [[0, 5], [0, 6]], 'pages': 3, 'parent': [0, 0], 'tail_occupancy': 1, 'touched': [0, 1]}{'address': [0, 2], 'children': [[1, 1], [1, 2]], 'pages': 3, 'parent': [0, 0], 'tail_occupancy': 1, 'touched': [0, 1]}Failed
regression certificate 4{'address': [2, 0], 'children': [[2, 1], [2, 2]], 'pages': 5, 'parent': [0, 2], 'tail_occupancy': 3, 'touched': [2, 4]}{'address': [2, 0], 'children': [[4, 1], [4, 2]], 'pages': 5, 'parent': [0, 2], 'tail_occupancy': 3, 'touched': [2, 4]}Failed
regression certificate 5{'address': [1, 3], 'children': [[1, 7]], 'pages': 4, 'parent': [0, 3], 'tail_occupancy': 4, 'touched': [1, 3]}{'address': [1, 3], 'children': [[3, 3]], 'pages': 4, 'parent': [0, 3], 'tail_occupancy': 4, 'touched': [1, 3]}Failed
regression certificate 6{'address': [1, 1], 'children': [[1, 3]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 1, 'touched': [1, 3]}{'address': [1, 1], 'children': [[3, 0]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 1, 'touched': [1, 3]}Failed
variant-dependent certificate{'address': [1, 1], 'children': [[1, 3], [1, 4]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 2, 'touched': [1, 3]}{'address': [1, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 2, 'touched': [1, 3]}Failed

SHA-256 / 2f454b4b9b2b785bd7894ccca94fc4b19aa6d8f84bae827af9d549c43b6a6e3d

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    n=d['size']; b=d['page_size']; i=d['index']; children=[j for j in (2*i+1,2*i+2) if j<n]
    def address(j): return [j//b,j%b]
    return {'address': address(i),
    'parent': None if i==0 else address((i-1)//2),
    'children': [address(2*i)] if 2*i<n else [],
    'pages': (n+b-1)//b,
    'tail_occupancy': (n-1)%b+1,
    'touched': sorted({j//b for j in [i]+children})}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 11, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 12, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 3, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 13, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 1, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 14, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 15, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 3, 'touched': [1, 3]})]][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{'address': [0, 0], 'children': [[0, 0]], 'pages': 1, 'parent': None, 'tail_occupancy': 1, 'touched': [0]}{'address': [0, 0], 'children': [], 'pages': 1, 'parent': None, 'tail_occupancy': 1, 'touched': [0]}Failed
regression certificate 2{'address': [0, 3], 'children': [[1, 2]], 'pages': 2, 'parent': [0, 1], 'tail_occupancy': 4, 'touched': [0, 1]}{'address': [0, 3], 'children': [[1, 3]], 'pages': 2, 'parent': [0, 1], 'tail_occupancy': 4, 'touched': [0, 1]}Failed
regression certificate 3{'address': [0, 2], 'children': [[1, 0]], 'pages': 3, 'parent': [0, 0], 'tail_occupancy': 1, 'touched': [0, 1]}{'address': [0, 2], 'children': [[1, 1], [1, 2]], 'pages': 3, 'parent': [0, 0], 'tail_occupancy': 1, 'touched': [0, 1]}Failed
regression certificate 4{'address': [2, 0], 'children': [[4, 0]], 'pages': 5, 'parent': [0, 2], 'tail_occupancy': 3, 'touched': [2, 4]}{'address': [2, 0], 'children': [[4, 1], [4, 2]], 'pages': 5, 'parent': [0, 2], 'tail_occupancy': 3, 'touched': [2, 4]}Failed
regression certificate 5{'address': [1, 3], 'children': [[3, 2]], 'pages': 4, 'parent': [0, 3], 'tail_occupancy': 4, 'touched': [1, 3]}{'address': [1, 3], 'children': [[3, 3]], 'pages': 4, 'parent': [0, 3], 'tail_occupancy': 4, 'touched': [1, 3]}Failed
regression certificate 6{'address': [1, 1], 'children': [[2, 2]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 1, 'touched': [1, 3]}{'address': [1, 1], 'children': [[3, 0]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 1, 'touched': [1, 3]}Failed
variant-dependent certificate{'address': [1, 1], 'children': [[2, 2]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 2, 'touched': [1, 3]}{'address': [1, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 2, 'touched': [1, 3]}Failed

SHA-256 / 1e578a25b619ec47d007460d5d98dfb56182af0d1f446190e950b5d73706ef61

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    n=d['size']; b=d['page_size']; i=d['index']; children=[j for j in (2*i+1,2*i+2) if j<n]
    def address(j): return [j//b,j%b]
    return {'address': address(i),
    'parent': None if i==0 else address((i-1)//2),
    'children': [address(j) for j in children],
    'pages': (n+b-1)//b,
    'tail_occupancy': (n-1)%b+1,
    'touched': sorted({j//b for j in [i]+children})}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 11, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 12, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'tail_occupancy': 3, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 13, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 1, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 14, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 2, 'touched': [1, 3]})], [({'size': 1, 'page_size': 4, 'index': 0}, {'address': [0, 0], 'parent': None, 'children': [], 'pages': 1, 'tail_occupancy': 1, 'touched': [0]}), ({'size': 8, 'page_size': 4, 'index': 3}, {'address': [0, 3], 'parent': [0, 1], 'children': [[1, 3]], 'pages': 2, 'tail_occupancy': 4, 'touched': [0, 1]}), ({'size': 9, 'page_size': 4, 'index': 2}, {'address': [0, 2], 'parent': [0, 0], 'children': [[1, 1], [1, 2]], 'pages': 3, 'tail_occupancy': 1, 'touched': [0, 1]}), ({'size': 15, 'page_size': 3, 'index': 6}, {'address': [2, 0], 'parent': [0, 2], 'children': [[4, 1], [4, 2]], 'pages': 5, 'tail_occupancy': 3, 'touched': [2, 4]}), ({'size': 16, 'page_size': 4, 'index': 7}, {'address': [1, 3], 'parent': [0, 3], 'children': [[3, 3]], 'pages': 4, 'tail_occupancy': 4, 'touched': [1, 3]}), ({'size': 10, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0]], 'pages': 4, 'tail_occupancy': 1, 'touched': [1, 3]}), ({'size': 15, 'page_size': 3, 'index': 4}, {'address': [1, 1], 'parent': [0, 1], 'children': [[3, 0], [3, 1]], 'pages': 5, 'tail_occupancy': 3, 'touched': [1, 3]})]][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{'address': [0, 0], 'children': [], 'pages': 1, 'parent': None, 'tail_occupancy': 1, 'touched': [0]}{'address': [0, 0], 'children': [], 'pages': 1, 'parent': None, 'tail_occupancy': 1, 'touched': [0]}Passed
regression certificate 2{'address': [0, 3], 'children': [[1, 3]], 'pages': 2, 'parent': [0, 1], 'tail_occupancy': 4, 'touched': [0, 1]}{'address': [0, 3], 'children': [[1, 3]], 'pages': 2, 'parent': [0, 1], 'tail_occupancy': 4, 'touched': [0, 1]}Passed
regression certificate 3{'address': [0, 2], 'children': [[1, 1], [1, 2]], 'pages': 3, 'parent': [0, 0], 'tail_occupancy': 1, 'touched': [0, 1]}{'address': [0, 2], 'children': [[1, 1], [1, 2]], 'pages': 3, 'parent': [0, 0], 'tail_occupancy': 1, 'touched': [0, 1]}Passed
regression certificate 4{'address': [2, 0], 'children': [[4, 1], [4, 2]], 'pages': 5, 'parent': [0, 2], 'tail_occupancy': 3, 'touched': [2, 4]}{'address': [2, 0], 'children': [[4, 1], [4, 2]], 'pages': 5, 'parent': [0, 2], 'tail_occupancy': 3, 'touched': [2, 4]}Passed
regression certificate 5{'address': [1, 3], 'children': [[3, 3]], 'pages': 4, 'parent': [0, 3], 'tail_occupancy': 4, 'touched': [1, 3]}{'address': [1, 3], 'children': [[3, 3]], 'pages': 4, 'parent': [0, 3], 'tail_occupancy': 4, 'touched': [1, 3]}Passed
regression certificate 6{'address': [1, 1], 'children': [[3, 0]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 1, 'touched': [1, 3]}{'address': [1, 1], 'children': [[3, 0]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 1, 'touched': [1, 3]}Passed
variant-dependent certificate{'address': [1, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 2, 'touched': [1, 3]}{'address': [1, 1], 'children': [[3, 0], [3, 1]], 'pages': 4, 'parent': [0, 1], 'tail_occupancy': 2, 'touched': [1, 3]}Passed

SHA-256 / 45273083a38d2e5da74c177e7ee349ed2534a86fb0bd77b862533faa3107b4f5

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

Case digest / 1fd48cc4dd6315becb8e7734687fa7ce76fa57128bfe81ea7edd1cb357ea511b