FAILURE MAP
← Case archive

FA-40846 / Heap invariants / Open access

Bucket bitmap consistency identifies set bits whose buckets are empty · case 01

The bounded priority bitset certificate reports an incorrect ghosts.

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

ROOT CAUSE

Bucket bitmap consistency identifies set bits whose buckets are empty.

VERIFIED REPAIR

Derive ghosts using [i for i,x in enumerate(b) if mask&(1<<i) and not x] under the stated bounded certificate contract.

Unsuccessful approach: The local patch uses [i for i,x in enumerate(b) if not x] and still violates the stated relation.

Case contract

A bounded bucket priority queue certificate supplies occupancy mask and bucket lists for priorities 0..width-1. Report actual occupancy mask, least occupied priority, greatest occupied priority, mask-only ghost priorities, missing-mask priorities, and popped-bucket bit clearing after removing one first element from requested priority. Empty buckets are valid.

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):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length()-1 if actual else None,
    'maximum': actual.bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if mask&(1<<i)],
    'missing': [i for i,x in enumerate(b) if x and not mask&(1<<i)],
    'after_pop': mask if remaining or not b else mask & ~(1<<p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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{'actual_mask': 0, 'after_pop': 0, 'ghosts': [], 'maximum': None, 'minimum': None, 'missing': []}{'actual_mask': 0, 'after_pop': 0, 'ghosts': [], 'maximum': None, 'minimum': None, 'missing': []}Passed
regression certificate 2{'actual_mask': 1, 'after_pop': 0, 'ghosts': [0], 'maximum': 0, 'minimum': 0, 'missing': []}{'actual_mask': 1, 'after_pop': 0, 'ghosts': [], 'maximum': 0, 'minimum': 0, 'missing': []}Failed
regression certificate 3{'actual_mask': 10, 'after_pop': 10, 'ghosts': [1, 3], 'maximum': 3, 'minimum': 1, 'missing': []}{'actual_mask': 10, 'after_pop': 10, 'ghosts': [], 'maximum': 3, 'minimum': 1, 'missing': []}Failed
regression certificate 4{'actual_mask': 5, 'after_pop': 2, 'ghosts': [0, 1], 'maximum': 2, 'minimum': 0, 'missing': [2]}{'actual_mask': 5, 'after_pop': 2, 'ghosts': [1], 'maximum': 2, 'minimum': 0, 'missing': [2]}Failed
regression certificate 5{'actual_mask': 0, 'after_pop': 5, 'ghosts': [0, 1, 2], 'maximum': None, 'minimum': None, 'missing': []}{'actual_mask': 0, 'after_pop': 5, 'ghosts': [0, 1, 2], 'maximum': None, 'minimum': None, 'missing': []}Passed
regression certificate 6{'actual_mask': 26, 'after_pop': 8, 'ghosts': [3], 'maximum': 4, 'minimum': 1, 'missing': [1, 4]}{'actual_mask': 26, 'after_pop': 8, 'ghosts': [], 'maximum': 4, 'minimum': 1, 'missing': [1, 4]}Failed
variant-dependent certificate{'actual_mask': 26, 'after_pop': 1, 'ghosts': [0], 'maximum': 4, 'minimum': 1, 'missing': [1, 3, 4]}{'actual_mask': 26, 'after_pop': 1, 'ghosts': [0], 'maximum': 4, 'minimum': 1, 'missing': [1, 3, 4]}Passed

SHA-256 / cb0a043a2018abbe84ab7fa85cfbc12ae8dbbcb62175d8261977e1a827b081f3

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(d):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length()-1 if actual else None,
    'maximum': actual.bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if not x],
    'missing': [i for i,x in enumerate(b) if x and not mask&(1<<i)],
    'after_pop': mask if remaining or not b else mask & ~(1<<p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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{'actual_mask': 0, 'after_pop': 0, 'ghosts': [], 'maximum': None, 'minimum': None, 'missing': []}{'actual_mask': 0, 'after_pop': 0, 'ghosts': [], 'maximum': None, 'minimum': None, 'missing': []}Passed
regression certificate 2{'actual_mask': 1, 'after_pop': 0, 'ghosts': [], 'maximum': 0, 'minimum': 0, 'missing': []}{'actual_mask': 1, 'after_pop': 0, 'ghosts': [], 'maximum': 0, 'minimum': 0, 'missing': []}Passed
regression certificate 3{'actual_mask': 10, 'after_pop': 10, 'ghosts': [0, 2], 'maximum': 3, 'minimum': 1, 'missing': []}{'actual_mask': 10, 'after_pop': 10, 'ghosts': [], 'maximum': 3, 'minimum': 1, 'missing': []}Failed
regression certificate 4{'actual_mask': 5, 'after_pop': 2, 'ghosts': [1], 'maximum': 2, 'minimum': 0, 'missing': [2]}{'actual_mask': 5, 'after_pop': 2, 'ghosts': [1], 'maximum': 2, 'minimum': 0, 'missing': [2]}Passed
regression certificate 5{'actual_mask': 0, 'after_pop': 5, 'ghosts': [0, 1, 2], 'maximum': None, 'minimum': None, 'missing': []}{'actual_mask': 0, 'after_pop': 5, 'ghosts': [0, 1, 2], 'maximum': None, 'minimum': None, 'missing': []}Passed
regression certificate 6{'actual_mask': 26, 'after_pop': 8, 'ghosts': [0, 2], 'maximum': 4, 'minimum': 1, 'missing': [1, 4]}{'actual_mask': 26, 'after_pop': 8, 'ghosts': [], 'maximum': 4, 'minimum': 1, 'missing': [1, 4]}Failed
variant-dependent certificate{'actual_mask': 26, 'after_pop': 1, 'ghosts': [0, 2], 'maximum': 4, 'minimum': 1, 'missing': [1, 3, 4]}{'actual_mask': 26, 'after_pop': 1, 'ghosts': [0], 'maximum': 4, 'minimum': 1, 'missing': [1, 3, 4]}Failed

SHA-256 / 44c03d58a7c6e302cff3488ce8cc9282ad61ec11e347c569cd39309f428d0ac1

3 / The verified repair

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

N = 1
observations = []
def solve(d):
    b=d['buckets']; mask=d['mask']; p=d['pop']; actual=sum(1<<i for i,x in enumerate(b) if x); remaining=max(0,len(b[p])-1) if b else 0
    return {'actual_mask': actual,
    'minimum': (actual & -actual).bit_length()-1 if actual else None,
    'maximum': actual.bit_length()-1 if actual else None,
    'ghosts': [i for i,x in enumerate(b) if mask&(1<<i) and not x],
    'missing': [i for i,x in enumerate(b) if x and not mask&(1<<i)],
    'after_pop': mask if remaining or not b else mask & ~(1<<p)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 1, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [1, 3, 4], 'after_pop': 1})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 2, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [3, 4], 'after_pop': 2})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 3, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0], 'missing': [3, 4], 'after_pop': 3})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 4, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [2], 'missing': [1, 3, 4], 'after_pop': 4})], [({'buckets': [], 'mask': 0, 'pop': 0}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [['a']], 'mask': 1, 'pop': 0}, {'actual_mask': 1, 'minimum': 0, 'maximum': 0, 'ghosts': [], 'missing': [], 'after_pop': 0}), ({'buckets': [[], ['a', 'b'], [], ['c']], 'mask': 10, 'pop': 1}, {'actual_mask': 10, 'minimum': 1, 'maximum': 3, 'ghosts': [], 'missing': [], 'after_pop': 10}), ({'buckets': [['a'], [], ['c']], 'mask': 3, 'pop': 0}, {'actual_mask': 5, 'minimum': 0, 'maximum': 2, 'ghosts': [1], 'missing': [2], 'after_pop': 2}), ({'buckets': [[], [], []], 'mask': 7, 'pop': 1}, {'actual_mask': 0, 'minimum': None, 'maximum': None, 'ghosts': [0, 1, 2], 'missing': [], 'after_pop': 5}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 8, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [], 'missing': [1, 4], 'after_pop': 8}), ({'buckets': [[], ['x'], [], ['y', 'z'], ['q']], 'mask': 5, 'pop': 3}, {'actual_mask': 26, 'minimum': 1, 'maximum': 4, 'ghosts': [0, 2], 'missing': [1, 3, 4], 'after_pop': 5})]][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{'actual_mask': 0, 'after_pop': 0, 'ghosts': [], 'maximum': None, 'minimum': None, 'missing': []}{'actual_mask': 0, 'after_pop': 0, 'ghosts': [], 'maximum': None, 'minimum': None, 'missing': []}Passed
regression certificate 2{'actual_mask': 1, 'after_pop': 0, 'ghosts': [], 'maximum': 0, 'minimum': 0, 'missing': []}{'actual_mask': 1, 'after_pop': 0, 'ghosts': [], 'maximum': 0, 'minimum': 0, 'missing': []}Passed
regression certificate 3{'actual_mask': 10, 'after_pop': 10, 'ghosts': [], 'maximum': 3, 'minimum': 1, 'missing': []}{'actual_mask': 10, 'after_pop': 10, 'ghosts': [], 'maximum': 3, 'minimum': 1, 'missing': []}Passed
regression certificate 4{'actual_mask': 5, 'after_pop': 2, 'ghosts': [1], 'maximum': 2, 'minimum': 0, 'missing': [2]}{'actual_mask': 5, 'after_pop': 2, 'ghosts': [1], 'maximum': 2, 'minimum': 0, 'missing': [2]}Passed
regression certificate 5{'actual_mask': 0, 'after_pop': 5, 'ghosts': [0, 1, 2], 'maximum': None, 'minimum': None, 'missing': []}{'actual_mask': 0, 'after_pop': 5, 'ghosts': [0, 1, 2], 'maximum': None, 'minimum': None, 'missing': []}Passed
regression certificate 6{'actual_mask': 26, 'after_pop': 8, 'ghosts': [], 'maximum': 4, 'minimum': 1, 'missing': [1, 4]}{'actual_mask': 26, 'after_pop': 8, 'ghosts': [], 'maximum': 4, 'minimum': 1, 'missing': [1, 4]}Passed
variant-dependent certificate{'actual_mask': 26, 'after_pop': 1, 'ghosts': [0], 'maximum': 4, 'minimum': 1, 'missing': [1, 3, 4]}{'actual_mask': 26, 'after_pop': 1, 'ghosts': [0], 'maximum': 4, 'minimum': 1, 'missing': [1, 3, 4]}Passed

SHA-256 / c4698fce54d7c50ff274383332adcac491f7297570899580c1bbfe5145bef0d8

Verification & scope

A stipulated offline diagnostic model; it does not implement a production allocator, concurrency protocol, or complete heap library. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:43:34.961720+00:00.

Case digest / f7882f23212d8b07528c7a10d1afb9c5f28ff08ecd14700fee9af89fb2f3325e