FA-46166 / Bounded deques / Open access
Capacity permits forget resident deque occupancy · case 01
Capacity permits forget resident deque occupancy.
ROOT CAUSE
Capacity permits forget resident deque occupancy.
VERIFIED REPAIR
Restore the documented resident charge invariant in capacity-permits.
Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.
Case contract
Bounded deque capacity includes live items and outstanding insertion permits. Grant a new permit only if it fits, then cancel one named permit and report the remaining permits and 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):
cap,size,claims,want,cancel=x
reserved=sum(c[1] for c in claims)
available=cap-reserved
accepted=want<=available
active=claims+([['new',want]] if accepted else [])
active=[c for c in active if c[0]!=cancel]
free=cap-size-sum(c[1] for c in active)
return [active,accepted,free]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('reserved blocks grant', solve([8,3,[["a",3]],3,"none"]), {1: [[['a', 3]], False, 2], 2: [[['a', 3]], False, 2], 3: [[['a', 3]], False, 2], 4: [[['a', 3]], False, 2], 5: [[['a', 3]], False, 2]}[N])
check('cancel existing', solve([9,2,[["a",2],["b",1]],2,"a"]), {1: [[['b', 1], ['new', 2]], True, 4], 2: [[['b', 1], ['new', 2]], True, 4], 3: [[['b', 1], ['new', 2]], True, 4], 4: [[['b', 1], ['new', 2]], True, 4], 5: [[['b', 1], ['new', 2]], True, 4]}[N])
check('cancel new', solve([7,2,[["a",1]],3,"new"]), {1: [[['a', 1]], True, 4], 2: [[['a', 1]], True, 4], 3: [[['a', 1]], True, 4], 4: [[['a', 1]], True, 4], 5: [[['a', 1]], True, 4]}[N])
check('exact available', solve([6,2,[["a",1]],3,"none"]), {1: [[['a', 1], ['new', 3]], True, 0], 2: [[['a', 1], ['new', 3]], True, 0], 3: [[['a', 1], ['new', 3]], True, 0], 4: [[['a', 1], ['new', 3]], True, 0], 5: [[['a', 1], ['new', 3]], True, 0]}[N])
check('no claims', solve([N+4,N,[],2,"none"]), {1: [[['new', 2]], True, 2], 2: [[['new', 2]], True, 2], 3: [[['new', 2]], True, 2], 4: [[['new', 2]], True, 2], 5: [[['new', 2]], True, 2]}[N])
check('zero permit', solve([4,4,[],0,"none"]), {1: [[['new', 0]], True, 0], 2: [[['new', 0]], True, 0], 3: [[['new', 0]], True, 0], 4: [[['new', 0]], True, 0], 5: [[['new', 0]], True, 0]}[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 |
|---|---|---|---|
| reserved blocks grant | [[['a', 3], ['new', 3]], True, -1] | [[['a', 3]], False, 2] | Failed |
| cancel existing | [[['b', 1], ['new', 2]], True, 4] | [[['b', 1], ['new', 2]], True, 4] | Passed |
| cancel new | [[['a', 1]], True, 4] | [[['a', 1]], True, 4] | Passed |
| exact available | [[['a', 1], ['new', 3]], True, 0] | [[['a', 1], ['new', 3]], True, 0] | Passed |
| no claims | [[['new', 2]], True, 2] | [[['new', 2]], True, 2] | Passed |
| zero permit | [[['new', 0]], True, 0] | [[['new', 0]], True, 0] | Passed |
SHA-256 / 0cc91b8b9094f5f5af7af95265a903a8cfa1b840f2e5df9bef7a3f60b75a9462
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
cap,size,claims,want,cancel=x
reserved=sum(c[1] for c in claims)
available=cap-size-reserved if size==cap else cap-reserved
accepted=want<=available
active=claims+([['new',want]] if accepted else [])
active=[c for c in active if c[0]!=cancel]
free=cap-size-sum(c[1] for c in active)
return [active,accepted,free]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('reserved blocks grant', solve([8,3,[["a",3]],3,"none"]), {1: [[['a', 3]], False, 2], 2: [[['a', 3]], False, 2], 3: [[['a', 3]], False, 2], 4: [[['a', 3]], False, 2], 5: [[['a', 3]], False, 2]}[N])
check('cancel existing', solve([9,2,[["a",2],["b",1]],2,"a"]), {1: [[['b', 1], ['new', 2]], True, 4], 2: [[['b', 1], ['new', 2]], True, 4], 3: [[['b', 1], ['new', 2]], True, 4], 4: [[['b', 1], ['new', 2]], True, 4], 5: [[['b', 1], ['new', 2]], True, 4]}[N])
check('cancel new', solve([7,2,[["a",1]],3,"new"]), {1: [[['a', 1]], True, 4], 2: [[['a', 1]], True, 4], 3: [[['a', 1]], True, 4], 4: [[['a', 1]], True, 4], 5: [[['a', 1]], True, 4]}[N])
check('exact available', solve([6,2,[["a",1]],3,"none"]), {1: [[['a', 1], ['new', 3]], True, 0], 2: [[['a', 1], ['new', 3]], True, 0], 3: [[['a', 1], ['new', 3]], True, 0], 4: [[['a', 1], ['new', 3]], True, 0], 5: [[['a', 1], ['new', 3]], True, 0]}[N])
check('no claims', solve([N+4,N,[],2,"none"]), {1: [[['new', 2]], True, 2], 2: [[['new', 2]], True, 2], 3: [[['new', 2]], True, 2], 4: [[['new', 2]], True, 2], 5: [[['new', 2]], True, 2]}[N])
check('zero permit', solve([4,4,[],0,"none"]), {1: [[['new', 0]], True, 0], 2: [[['new', 0]], True, 0], 3: [[['new', 0]], True, 0], 4: [[['new', 0]], True, 0], 5: [[['new', 0]], True, 0]}[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 |
|---|---|---|---|
| reserved blocks grant | [[['a', 3], ['new', 3]], True, -1] | [[['a', 3]], False, 2] | Failed |
| cancel existing | [[['b', 1], ['new', 2]], True, 4] | [[['b', 1], ['new', 2]], True, 4] | Passed |
| cancel new | [[['a', 1]], True, 4] | [[['a', 1]], True, 4] | Passed |
| exact available | [[['a', 1], ['new', 3]], True, 0] | [[['a', 1], ['new', 3]], True, 0] | Passed |
| no claims | [[['new', 2]], True, 2] | [[['new', 2]], True, 2] | Passed |
| zero permit | [[['new', 0]], True, 0] | [[['new', 0]], True, 0] | Passed |
SHA-256 / cb7582f9a546086dc1349bfd1c6ab91d2d23b4d1855507d44abd041958e0db47
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
cap,size,claims,want,cancel=x
reserved=sum(c[1] for c in claims)
available=cap-size-reserved
accepted=want<=available
active=claims+([['new',want]] if accepted else [])
active=[c for c in active if c[0]!=cancel]
free=cap-size-sum(c[1] for c in active)
return [active,accepted,free]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('reserved blocks grant', solve([8,3,[["a",3]],3,"none"]), {1: [[['a', 3]], False, 2], 2: [[['a', 3]], False, 2], 3: [[['a', 3]], False, 2], 4: [[['a', 3]], False, 2], 5: [[['a', 3]], False, 2]}[N])
check('cancel existing', solve([9,2,[["a",2],["b",1]],2,"a"]), {1: [[['b', 1], ['new', 2]], True, 4], 2: [[['b', 1], ['new', 2]], True, 4], 3: [[['b', 1], ['new', 2]], True, 4], 4: [[['b', 1], ['new', 2]], True, 4], 5: [[['b', 1], ['new', 2]], True, 4]}[N])
check('cancel new', solve([7,2,[["a",1]],3,"new"]), {1: [[['a', 1]], True, 4], 2: [[['a', 1]], True, 4], 3: [[['a', 1]], True, 4], 4: [[['a', 1]], True, 4], 5: [[['a', 1]], True, 4]}[N])
check('exact available', solve([6,2,[["a",1]],3,"none"]), {1: [[['a', 1], ['new', 3]], True, 0], 2: [[['a', 1], ['new', 3]], True, 0], 3: [[['a', 1], ['new', 3]], True, 0], 4: [[['a', 1], ['new', 3]], True, 0], 5: [[['a', 1], ['new', 3]], True, 0]}[N])
check('no claims', solve([N+4,N,[],2,"none"]), {1: [[['new', 2]], True, 2], 2: [[['new', 2]], True, 2], 3: [[['new', 2]], True, 2], 4: [[['new', 2]], True, 2], 5: [[['new', 2]], True, 2]}[N])
check('zero permit', solve([4,4,[],0,"none"]), {1: [[['new', 0]], True, 0], 2: [[['new', 0]], True, 0], 3: [[['new', 0]], True, 0], 4: [[['new', 0]], True, 0], 5: [[['new', 0]], True, 0]}[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 |
|---|---|---|---|
| reserved blocks grant | [[['a', 3]], False, 2] | [[['a', 3]], False, 2] | Passed |
| cancel existing | [[['b', 1], ['new', 2]], True, 4] | [[['b', 1], ['new', 2]], True, 4] | Passed |
| cancel new | [[['a', 1]], True, 4] | [[['a', 1]], True, 4] | Passed |
| exact available | [[['a', 1], ['new', 3]], True, 0] | [[['a', 1], ['new', 3]], True, 0] | Passed |
| no claims | [[['new', 2]], True, 2] | [[['new', 2]], True, 2] | Passed |
| zero permit | [[['new', 0]], True, 0] | [[['new', 0]], True, 0] | Passed |
SHA-256 / 423b4b3e95cad39705d3868532901e2268a8591564c2b541dcda6fc3ca23216e
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:29.478701+00:00.
Case digest / 14db1ab1b65e34e9f86a6b06be29255ab7cc6b6c784978530f45df12b1c706ce