FA-45916 / Bounded deques / Open access
Shrink uses new capacity as the eviction count · case 01
Shrink uses new capacity as the eviction count.
ROOT CAUSE
The new bound is mistaken for the number of excess live entries.
VERIFIED REPAIR
Restore the documented drop count invariant in ring-shrink.
Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.
Case contract
Shrink an occupied logical deque to a smaller bound, retaining the newest suffix. Return retained values, evicted prefix, a linear backing allocation, and free capacity.
Why this case matters
Controlled bounded deque implementation model with explicit storage and lifecycle observations.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
items, bound = x
lost = min(bound, len(items))
evicted = items[:lost]
kept = items[lost:]
slots = kept + [None] * (bound - len(kept))
free = bound - len(kept)
return [kept, evicted, slots, free]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('drop oldest pair', solve([[N,N+1,N+2,N+3],2]), [[N+2,N+3],[N,N+1],[N+2,N+3],0])
check('zero bound', solve([[N,N+1],0]), [[],[N,N+1],[],0])
check('spare capacity', solve([[N],3]), [[N],[],[N,None,None],2])
check('same bound', solve([[N,N+1],2]), [[N,N+1],[],[N,N+1],0])
check('empty', solve([[],2]), [[],[],[None,None],2])
check('drop one of three', solve([[N,N+1,N+2],2]), [[N+1,N+2],[N],[N+1,N+2],0])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| drop oldest pair | [[3, 4], [1, 2], [3, 4], 0] | [[3, 4], [1, 2], [3, 4], 0] | Passed |
| zero bound | [[1, 2], [], [1, 2], -2] | [[], [1, 2], [], 0] | Failed |
| spare capacity | [[], [1], [None, None, None], 3] | [[1], [], [1, None, None], 2] | Failed |
| same bound | [[], [1, 2], [None, None], 2] | [[1, 2], [], [1, 2], 0] | Failed |
| empty | [[], [], [None, None], 2] | [[], [], [None, None], 2] | Passed |
| drop one of three | [[3], [1, 2], [3, None], 1] | [[2, 3], [1], [2, 3], 0] | Failed |
SHA-256 / 05759f3f038b60576f44a3d331d1b472b0c71efc9a32bd33620b989c44834a6e
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
items, bound = x
lost = 0 if len(items) <= bound else min(bound, len(items))
evicted = items[:lost]
kept = items[lost:]
slots = kept + [None] * (bound - len(kept))
free = bound - len(kept)
return [kept, evicted, slots, free]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('drop oldest pair', solve([[N,N+1,N+2,N+3],2]), [[N+2,N+3],[N,N+1],[N+2,N+3],0])
check('zero bound', solve([[N,N+1],0]), [[],[N,N+1],[],0])
check('spare capacity', solve([[N],3]), [[N],[],[N,None,None],2])
check('same bound', solve([[N,N+1],2]), [[N,N+1],[],[N,N+1],0])
check('empty', solve([[],2]), [[],[],[None,None],2])
check('drop one of three', solve([[N,N+1,N+2],2]), [[N+1,N+2],[N],[N+1,N+2],0])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| drop oldest pair | [[3, 4], [1, 2], [3, 4], 0] | [[3, 4], [1, 2], [3, 4], 0] | Passed |
| zero bound | [[1, 2], [], [1, 2], -2] | [[], [1, 2], [], 0] | Failed |
| spare capacity | [[1], [], [1, None, None], 2] | [[1], [], [1, None, None], 2] | Passed |
| same bound | [[1, 2], [], [1, 2], 0] | [[1, 2], [], [1, 2], 0] | Passed |
| empty | [[], [], [None, None], 2] | [[], [], [None, None], 2] | Passed |
| drop one of three | [[3], [1, 2], [3, None], 1] | [[2, 3], [1], [2, 3], 0] | Failed |
SHA-256 / 9b167ef7f28d991fa2052f7ddd96ec3f509fd53ea35c5f228fd8ed77c6446066
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
items, bound = x
lost = max(0, len(items) - bound)
evicted = items[:lost]
kept = items[lost:]
slots = kept + [None] * (bound - len(kept))
free = bound - len(kept)
return [kept, evicted, slots, free]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('drop oldest pair', solve([[N,N+1,N+2,N+3],2]), [[N+2,N+3],[N,N+1],[N+2,N+3],0])
check('zero bound', solve([[N,N+1],0]), [[],[N,N+1],[],0])
check('spare capacity', solve([[N],3]), [[N],[],[N,None,None],2])
check('same bound', solve([[N,N+1],2]), [[N,N+1],[],[N,N+1],0])
check('empty', solve([[],2]), [[],[],[None,None],2])
check('drop one of three', solve([[N,N+1,N+2],2]), [[N+1,N+2],[N],[N+1,N+2],0])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| drop oldest pair | [[3, 4], [1, 2], [3, 4], 0] | [[3, 4], [1, 2], [3, 4], 0] | Passed |
| zero bound | [[], [1, 2], [], 0] | [[], [1, 2], [], 0] | Passed |
| spare capacity | [[1], [], [1, None, None], 2] | [[1], [], [1, None, None], 2] | Passed |
| same bound | [[1, 2], [], [1, 2], 0] | [[1, 2], [], [1, 2], 0] | Passed |
| empty | [[], [], [None, None], 2] | [[], [], [None, None], 2] | Passed |
| drop one of three | [[2, 3], [1], [2, 3], 0] | [[2, 3], [1], [2, 3], 0] | Passed |
SHA-256 / e177ee7c52852ab57671bec37ef4707a6a3004f09b1466111f2b41edb51aff2e
Verification & scope
Offline finite deterministic model; no claim of production implementation or concurrent memory-model conformance. 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:44:27.097803+00:00.
Case digest / be16f2fcfba7d6c8468843614f3e99cb3fb402c0b780850500237acaad8ff56c