FA-45921 / Bounded deques / Open access
Shrink reports evicted objects in reverse release order · case 01
Shrink reports evicted objects in reverse release order.
ROOT CAUSE
The oldest-first release contract is reversed by a stack-style cleanup loop.
VERIFIED REPAIR
Restore the documented eviction order 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 = max(0, len(items) - bound)
evicted = items[:lost][::-1]
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], [2, 1], [3, 4], 0] | [[3, 4], [1, 2], [3, 4], 0] | Failed |
| zero bound | [[], [2, 1], [], 0] | [[], [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 | [[2, 3], [1], [2, 3], 0] | [[2, 3], [1], [2, 3], 0] | Passed |
SHA-256 / 35b97f93b15e9a6fc7439eecc67e5e004d822bb2e4e0a6cf5d4a98754092db9a
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 = max(0, len(items) - bound)
evicted = items[:lost] if lost <= 1 else items[:lost][::-1]
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], [2, 1], [3, 4], 0] | [[3, 4], [1, 2], [3, 4], 0] | Failed |
| zero bound | [[], [2, 1], [], 0] | [[], [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 | [[2, 3], [1], [2, 3], 0] | [[2, 3], [1], [2, 3], 0] | Passed |
SHA-256 / d888303592d48c89f3310fb0ae0ba8ccdb825ef2bba41b2f7b20ede852e0ea29
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.106652+00:00.
Case digest / 44eed361a350b1046472640a69cdd5ec0cb8d0047315201115704037c48eb312