FA-46471 / Bounded deques / Open access
Freed deque blocks retain payload references · case 01
Freed deque blocks retain payload references.
ROOT CAUSE
Freed deque blocks retain payload references.
VERIFIED REPAIR
Restore the documented reference release invariant in block-release.
Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.
Case contract
A deque block with outstanding borrowers cannot be freed. Otherwise clear its live references, append to a bounded free-block cache and dispose the oldest surplus block identities.
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):
pool,identity,borrowed,limit,live=x
if borrowed:return [pool,False,live,[]]
references=live
combined=pool+[identity]
saved=combined[-limit:] if limit else []
disposed=combined[:len(combined)-len(saved)]
return [saved,True,references,disposed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[1,2],3,False,2,[N,N+1]]), {1: [[2, 3], True, [], [1]], 2: [[2, 3], True, [], [1]], 3: [[2, 3], True, [], [1]], 4: [[2, 3], True, [], [1]], 5: [[2, 3], True, [], [1]]}[N])
check('1', solve([[1],2,True,3,[N]]), {1: [[1], False, [1], []], 2: [[1], False, [2], []], 3: [[1], False, [3], []], 4: [[1], False, [4], []], 5: [[1], False, [5], []]}[N])
check('2', solve([[],4,False,0,[N,N+1]]), {1: [[], True, [], [4]], 2: [[], True, [], [4]], 3: [[], True, [], [4]], 4: [[], True, [], [4]], 5: [[], True, [], [4]]}[N])
check('3', solve([[2],5,False,3,[N]]), {1: [[2, 5], True, [], []], 2: [[2, 5], True, [], []], 3: [[2, 5], True, [], []], 4: [[2, 5], True, [], []], 5: [[2, 5], True, [], []]}[N])
check('4', solve([[1,2,3],4,False,1,[N]]), {1: [[4], True, [], [1, 2, 3]], 2: [[4], True, [], [1, 2, 3]], 3: [[4], True, [], [1, 2, 3]], 4: [[4], True, [], [1, 2, 3]], 5: [[4], True, [], [1, 2, 3]]}[N])
check('5', solve([[],7,False,2,[]]), {1: [[7], True, [], []], 2: [[7], True, [], []], 3: [[7], True, [], []], 4: [[7], True, [], []], 5: [[7], True, [], []]}[N])
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 |
|---|---|---|---|
| 0 | [[2, 3], True, [1, 2], [1]] | [[2, 3], True, [], [1]] | Failed |
| 1 | [[1], False, [1], []] | [[1], False, [1], []] | Passed |
| 2 | [[], True, [1, 2], [4]] | [[], True, [], [4]] | Failed |
| 3 | [[2, 5], True, [1], []] | [[2, 5], True, [], []] | Failed |
| 4 | [[4], True, [1], [1, 2, 3]] | [[4], True, [], [1, 2, 3]] | Failed |
| 5 | [[7], True, [], []] | [[7], True, [], []] | Passed |
SHA-256 / 3a394052f059d0bf90ceaafae4f2b2f0c4cde7f2529d95d9389957c1c74e7bbc
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
pool,identity,borrowed,limit,live=x
if borrowed:return [pool,False,live,[]]
references=[] if len(live)<=1 else live
combined=pool+[identity]
saved=combined[-limit:] if limit else []
disposed=combined[:len(combined)-len(saved)]
return [saved,True,references,disposed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[1,2],3,False,2,[N,N+1]]), {1: [[2, 3], True, [], [1]], 2: [[2, 3], True, [], [1]], 3: [[2, 3], True, [], [1]], 4: [[2, 3], True, [], [1]], 5: [[2, 3], True, [], [1]]}[N])
check('1', solve([[1],2,True,3,[N]]), {1: [[1], False, [1], []], 2: [[1], False, [2], []], 3: [[1], False, [3], []], 4: [[1], False, [4], []], 5: [[1], False, [5], []]}[N])
check('2', solve([[],4,False,0,[N,N+1]]), {1: [[], True, [], [4]], 2: [[], True, [], [4]], 3: [[], True, [], [4]], 4: [[], True, [], [4]], 5: [[], True, [], [4]]}[N])
check('3', solve([[2],5,False,3,[N]]), {1: [[2, 5], True, [], []], 2: [[2, 5], True, [], []], 3: [[2, 5], True, [], []], 4: [[2, 5], True, [], []], 5: [[2, 5], True, [], []]}[N])
check('4', solve([[1,2,3],4,False,1,[N]]), {1: [[4], True, [], [1, 2, 3]], 2: [[4], True, [], [1, 2, 3]], 3: [[4], True, [], [1, 2, 3]], 4: [[4], True, [], [1, 2, 3]], 5: [[4], True, [], [1, 2, 3]]}[N])
check('5', solve([[],7,False,2,[]]), {1: [[7], True, [], []], 2: [[7], True, [], []], 3: [[7], True, [], []], 4: [[7], True, [], []], 5: [[7], True, [], []]}[N])
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 |
|---|---|---|---|
| 0 | [[2, 3], True, [1, 2], [1]] | [[2, 3], True, [], [1]] | Failed |
| 1 | [[1], False, [1], []] | [[1], False, [1], []] | Passed |
| 2 | [[], True, [1, 2], [4]] | [[], True, [], [4]] | Failed |
| 3 | [[2, 5], True, [], []] | [[2, 5], True, [], []] | Passed |
| 4 | [[4], True, [], [1, 2, 3]] | [[4], True, [], [1, 2, 3]] | Passed |
| 5 | [[7], True, [], []] | [[7], True, [], []] | Passed |
SHA-256 / 1cc23af4bb72b8088e3af9b2275385a10115ed17c4b9f167c87b4937ebed60af
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
pool,identity,borrowed,limit,live=x
if borrowed:return [pool,False,live,[]]
references=[]
combined=pool+[identity]
saved=combined[-limit:] if limit else []
disposed=combined[:len(combined)-len(saved)]
return [saved,True,references,disposed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[1,2],3,False,2,[N,N+1]]), {1: [[2, 3], True, [], [1]], 2: [[2, 3], True, [], [1]], 3: [[2, 3], True, [], [1]], 4: [[2, 3], True, [], [1]], 5: [[2, 3], True, [], [1]]}[N])
check('1', solve([[1],2,True,3,[N]]), {1: [[1], False, [1], []], 2: [[1], False, [2], []], 3: [[1], False, [3], []], 4: [[1], False, [4], []], 5: [[1], False, [5], []]}[N])
check('2', solve([[],4,False,0,[N,N+1]]), {1: [[], True, [], [4]], 2: [[], True, [], [4]], 3: [[], True, [], [4]], 4: [[], True, [], [4]], 5: [[], True, [], [4]]}[N])
check('3', solve([[2],5,False,3,[N]]), {1: [[2, 5], True, [], []], 2: [[2, 5], True, [], []], 3: [[2, 5], True, [], []], 4: [[2, 5], True, [], []], 5: [[2, 5], True, [], []]}[N])
check('4', solve([[1,2,3],4,False,1,[N]]), {1: [[4], True, [], [1, 2, 3]], 2: [[4], True, [], [1, 2, 3]], 3: [[4], True, [], [1, 2, 3]], 4: [[4], True, [], [1, 2, 3]], 5: [[4], True, [], [1, 2, 3]]}[N])
check('5', solve([[],7,False,2,[]]), {1: [[7], True, [], []], 2: [[7], True, [], []], 3: [[7], True, [], []], 4: [[7], True, [], []], 5: [[7], True, [], []]}[N])
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 |
|---|---|---|---|
| 0 | [[2, 3], True, [], [1]] | [[2, 3], True, [], [1]] | Passed |
| 1 | [[1], False, [1], []] | [[1], False, [1], []] | Passed |
| 2 | [[], True, [], [4]] | [[], True, [], [4]] | Passed |
| 3 | [[2, 5], True, [], []] | [[2, 5], True, [], []] | Passed |
| 4 | [[4], True, [], [1, 2, 3]] | [[4], True, [], [1, 2, 3]] | Passed |
| 5 | [[7], True, [], []] | [[7], True, [], []] | Passed |
SHA-256 / e0dfa3c1510b34330ba19826d7a1d23d2fa44d854fcb297a228cd8d550ed424f
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:32.329952+00:00.
Case digest / d88ae33acf3a2f5442caf67b5ed3faad67766b3c389c8e88172a623d55cf90fe