FAILURE MAP
← Case archive

FA-40861 / Heap invariants / Open access

Cyclic priority buckets use absolute-key residue independent of the current cursor · case 01

The bounded dial window certificate reports an incorrect buckets.

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

ROOT CAUSE

Cyclic priority buckets use absolute-key residue independent of the current cursor.

VERIFIED REPAIR

Derive buckets using [[x[0],x[1]%c] for x in a] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [[x[0],x[1]//c] for x in a] and still violates the stated relation.

Case contract

A cyclic integer bucket queue with ring size C stores entries [id,absolute_key]. Cursor is last extracted absolute key. Only keys in [cursor,cursor+C) are in the active window. Report physical bucket indices, expired ids, future-window ids, next active key, rotation distance, and active ids in absolute-key order. Same-slot values from later revolutions must not be delivered.

Why this case matters

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

1 / The failure

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

N = 1
observations = []
def solve(d):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],(x[1]-cursor)%c] for x in a],
    'expired': [x[0] for x in a if x[1]<cursor],
    'future': [x[0] for x in a if x[1]>=cursor+c],
    'next': nxt,
    'advance': None if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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{'active_order': [], 'advance': None, 'buckets': [], 'expired': [], 'future': [], 'next': None}{'active_order': [], 'advance': None, 'buckets': [], 'expired': [], 'future': [], 'next': None}Passed
regression certificate 2{'active_order': ['a', 'b'], 'advance': 1, 'buckets': [['a', 1], ['b', 2], ['c', 0]], 'expired': [], 'future': ['c'], 'next': 4}{'active_order': ['a', 'b'], 'advance': 1, 'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4}Failed
regression certificate 3{'active_order': ['b', 'a'], 'advance': 1, 'buckets': [['a', 4], ['b', 1], ['c', 4], ['d', 0]], 'expired': ['c'], 'future': ['d'], 'next': 9}{'active_order': ['b', 'a'], 'advance': 1, 'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9}Failed
regression certificate 4{'active_order': ['c', 'b', 'a'], 'advance': 0, 'buckets': [['a', 2], ['b', 1], ['c', 0]], 'expired': [], 'future': [], 'next': 4}{'active_order': ['c', 'b', 'a'], 'advance': 0, 'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4}Failed
regression certificate 5{'active_order': [], 'advance': None, 'buckets': [['a', 0], ['b', 0]], 'expired': ['b'], 'future': ['a'], 'next': None}{'active_order': [], 'advance': None, 'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None}Failed
regression certificate 6{'active_order': ['c', 'b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 2], ['b', 1], ['c', 0], ['d', 7]], 'expired': [], 'future': [], 'next': 7}{'active_order': ['c', 'b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7}Failed
variant-dependent certificate{'active_order': ['b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8}{'active_order': ['b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8}Passed

SHA-256 / 16aeeb00d32773c167a26723979ccb4cc634ccc2e10a2a54218d3163b32f9f5f

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]//c] for x in a],
    'expired': [x[0] for x in a if x[1]<cursor],
    'future': [x[0] for x in a if x[1]>=cursor+c],
    'next': nxt,
    'advance': None if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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{'active_order': [], 'advance': None, 'buckets': [], 'expired': [], 'future': [], 'next': None}{'active_order': [], 'advance': None, 'buckets': [], 'expired': [], 'future': [], 'next': None}Passed
regression certificate 2{'active_order': ['a', 'b'], 'advance': 1, 'buckets': [['a', 1], ['b', 1], ['c', 1]], 'expired': [], 'future': ['c'], 'next': 4}{'active_order': ['a', 'b'], 'advance': 1, 'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4}Failed
regression certificate 3{'active_order': ['b', 'a'], 'advance': 1, 'buckets': [['a', 2], ['b', 1], ['c', 1], ['d', 2]], 'expired': ['c'], 'future': ['d'], 'next': 9}{'active_order': ['b', 'a'], 'advance': 1, 'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9}Failed
regression certificate 4{'active_order': ['c', 'b', 'a'], 'advance': 0, 'buckets': [['a', 2], ['b', 1], ['c', 1]], 'expired': [], 'future': [], 'next': 4}{'active_order': ['c', 'b', 'a'], 'advance': 0, 'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4}Failed
regression certificate 5{'active_order': [], 'advance': None, 'buckets': [['a', 2], ['b', 0]], 'expired': ['b'], 'future': ['a'], 'next': None}{'active_order': [], 'advance': None, 'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None}Failed
regression certificate 6{'active_order': ['c', 'b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 1], ['b', 1], ['c', 0], ['d', 1]], 'expired': [], 'future': [], 'next': 7}{'active_order': ['c', 'b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7}Failed
variant-dependent certificate{'active_order': ['b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 1], ['b', 1], ['c', 0], ['d', 1]], 'expired': ['c'], 'future': [], 'next': 8}{'active_order': ['b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8}Failed

SHA-256 / 8b1412459cf1d944dc58cb512fcb4efd85ee136924f327e580278b69afb370d5

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    a=d['entries']; c=d['capacity']; cursor=d['cursor']; active=[x for x in a if cursor<=x[1]<cursor+c]; nxt=min((x[1] for x in active),default=None)
    return {'buckets': [[x[0],x[1]%c] for x in a],
    'expired': [x[0] for x in a if x[1]<cursor],
    'future': [x[0] for x in a if x[1]>=cursor+c],
    'next': nxt,
    'advance': None if nxt is None else nxt-cursor,
    'active_order': [x[0] for x in sorted(active,key=lambda x:x[1])]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 8, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8, 'advance': 0, 'active_order': ['b', 'a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 9, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['b', 'c'], 'future': [], 'next': 9, 'advance': 0, 'active_order': ['a', 'd']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 10, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 4, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 11, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 3, 'active_order': ['d']})], [({'capacity': 4, 'cursor': 0, 'entries': []}, {'buckets': [], 'expired': [], 'future': [], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 4, 'cursor': 3, 'entries': [['a', 4], ['b', 5], ['c', 7]]}, {'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4, 'advance': 1, 'active_order': ['a', 'b']}), ({'capacity': 5, 'cursor': 8, 'entries': [['a', 12], ['b', 9], ['c', 7], ['d', 13]]}, {'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9, 'advance': 1, 'active_order': ['b', 'a']}), ({'capacity': 3, 'cursor': 4, 'entries': [['a', 6], ['b', 5], ['c', 4]]}, {'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4, 'advance': 0, 'active_order': ['c', 'b', 'a']}), ({'capacity': 4, 'cursor': 6, 'entries': [['a', 10], ['b', 2]]}, {'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None, 'advance': None, 'active_order': []}), ({'capacity': 8, 'cursor': 7, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7, 'advance': 0, 'active_order': ['c', 'b', 'a', 'd']}), ({'capacity': 8, 'cursor': 12, 'entries': [['a', 9], ['b', 8], ['c', 7], ['d', 14]]}, {'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['a', 'b', 'c'], 'future': [], 'next': 14, 'advance': 2, 'active_order': ['d']})]][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{'active_order': [], 'advance': None, 'buckets': [], 'expired': [], 'future': [], 'next': None}{'active_order': [], 'advance': None, 'buckets': [], 'expired': [], 'future': [], 'next': None}Passed
regression certificate 2{'active_order': ['a', 'b'], 'advance': 1, 'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4}{'active_order': ['a', 'b'], 'advance': 1, 'buckets': [['a', 0], ['b', 1], ['c', 3]], 'expired': [], 'future': ['c'], 'next': 4}Passed
regression certificate 3{'active_order': ['b', 'a'], 'advance': 1, 'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9}{'active_order': ['b', 'a'], 'advance': 1, 'buckets': [['a', 2], ['b', 4], ['c', 2], ['d', 3]], 'expired': ['c'], 'future': ['d'], 'next': 9}Passed
regression certificate 4{'active_order': ['c', 'b', 'a'], 'advance': 0, 'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4}{'active_order': ['c', 'b', 'a'], 'advance': 0, 'buckets': [['a', 0], ['b', 2], ['c', 1]], 'expired': [], 'future': [], 'next': 4}Passed
regression certificate 5{'active_order': [], 'advance': None, 'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None}{'active_order': [], 'advance': None, 'buckets': [['a', 2], ['b', 2]], 'expired': ['b'], 'future': ['a'], 'next': None}Passed
regression certificate 6{'active_order': ['c', 'b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7}{'active_order': ['c', 'b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': [], 'future': [], 'next': 7}Passed
variant-dependent certificate{'active_order': ['b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8}{'active_order': ['b', 'a', 'd'], 'advance': 0, 'buckets': [['a', 1], ['b', 0], ['c', 7], ['d', 6]], 'expired': ['c'], 'future': [], 'next': 8}Passed

SHA-256 / 3acbaca2024968c4790b45889d17305c0c8ee2a4ec85d17eb6fcc74607a2521b

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

Case digest / eaf983ed605eb375eb44915812c7201366841a37d911774b67fcdca8796743cf