FAILURE MAP
← Case archive

FA-46606 / Bounded deques / Open access

Deque borrow validates against allocation capacity instead of live extent · case 01

Deque borrow validates against allocation capacity instead of live extent.

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

ROOT CAUSE

Deque borrow validates against allocation capacity instead of live extent.

VERIFIED REPAIR

Restore the documented live bound invariant in range-borrow.

Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.

Case contract

Borrow a valid logical subrange from a bounded ring as at most two physical spans. Reject negative or out-of-live-range requests. Borrow captures the current epoch and pins storage only for nonempty ranges.

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,head,size,start,count,epoch=x
    if start<0 or count<0 or start+count>cap:return [False,[],epoch,0,False]
    origin=(head+start)%cap
    first=min(count,cap-origin)
    spans=[[origin,first]] if first else []
    if count>first:spans.append([0,count-first])
    captured=epoch
    pin=count>0
    return [True,spans,captured,count,pin]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([8,6,5,1,3,N]), {1: [True, [[7, 1], [0, 2]], 1, 3, True], 2: [True, [[7, 1], [0, 2]], 2, 3, True], 3: [True, [[7, 1], [0, 2]], 3, 3, True], 4: [True, [[7, 1], [0, 2]], 4, 3, True], 5: [True, [[7, 1], [0, 2]], 5, 3, True]}[N])
check('1', solve([8,2,4,1,2,N]), {1: [True, [[3, 2]], 1, 2, True], 2: [True, [[3, 2]], 2, 2, True], 3: [True, [[3, 2]], 3, 2, True], 4: [True, [[3, 2]], 4, 2, True], 5: [True, [[3, 2]], 5, 2, True]}[N])
check('2', solve([7,5,4,0,4,N]), {1: [True, [[5, 2], [0, 2]], 1, 4, True], 2: [True, [[5, 2], [0, 2]], 2, 4, True], 3: [True, [[5, 2], [0, 2]], 3, 4, True], 4: [True, [[5, 2], [0, 2]], 4, 4, True], 5: [True, [[5, 2], [0, 2]], 5, 4, True]}[N])
check('3', solve([8,3,2,2,0,N]), {1: [True, [], 1, 0, False], 2: [True, [], 2, 0, False], 3: [True, [], 3, 0, False], 4: [True, [], 4, 0, False], 5: [True, [], 5, 0, False]}[N])
check('4', solve([8,3,2,1,2,N]), {1: [False, [], 1, 0, False], 2: [False, [], 2, 0, False], 3: [False, [], 3, 0, False], 4: [False, [], 4, 0, False], 5: [False, [], 5, 0, False]}[N])
check('5', solve([6,2,3,-1,2,N]), {1: [False, [], 1, 0, False], 2: [False, [], 2, 0, False], 3: [False, [], 3, 0, False], 4: [False, [], 4, 0, False], 5: [False, [], 5, 0, False]}[N])
check('6', solve([7,1,5,3,-1,N]), {1: [False, [], 1, 0, False], 2: [False, [], 2, 0, False], 3: [False, [], 3, 0, False], 4: [False, [], 4, 0, False], 5: [False, [], 5, 0, False]}[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 fixtureActualExpectedOutcome
0[True, [[7, 1], [0, 2]], 1, 3, True][True, [[7, 1], [0, 2]], 1, 3, True]Passed
1[True, [[3, 2]], 1, 2, True][True, [[3, 2]], 1, 2, True]Passed
2[True, [[5, 2], [0, 2]], 1, 4, True][True, [[5, 2], [0, 2]], 1, 4, True]Passed
3[True, [], 1, 0, False][True, [], 1, 0, False]Passed
4[True, [[4, 2]], 1, 2, True][False, [], 1, 0, False]Failed
5[False, [], 1, 0, False][False, [], 1, 0, False]Passed
6[False, [], 1, 0, False][False, [], 1, 0, False]Passed

SHA-256 / 1dc693b009c649e5c210749c694109f2f7fe134ff4bea5523d5311f39f708d8f

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(x):
    cap,head,size,start,count,epoch=x
    if start<0 or count<0 or start+count>(size if start==0 else cap):return [False,[],epoch,0,False]
    origin=(head+start)%cap
    first=min(count,cap-origin)
    spans=[[origin,first]] if first else []
    if count>first:spans.append([0,count-first])
    captured=epoch
    pin=count>0
    return [True,spans,captured,count,pin]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([8,6,5,1,3,N]), {1: [True, [[7, 1], [0, 2]], 1, 3, True], 2: [True, [[7, 1], [0, 2]], 2, 3, True], 3: [True, [[7, 1], [0, 2]], 3, 3, True], 4: [True, [[7, 1], [0, 2]], 4, 3, True], 5: [True, [[7, 1], [0, 2]], 5, 3, True]}[N])
check('1', solve([8,2,4,1,2,N]), {1: [True, [[3, 2]], 1, 2, True], 2: [True, [[3, 2]], 2, 2, True], 3: [True, [[3, 2]], 3, 2, True], 4: [True, [[3, 2]], 4, 2, True], 5: [True, [[3, 2]], 5, 2, True]}[N])
check('2', solve([7,5,4,0,4,N]), {1: [True, [[5, 2], [0, 2]], 1, 4, True], 2: [True, [[5, 2], [0, 2]], 2, 4, True], 3: [True, [[5, 2], [0, 2]], 3, 4, True], 4: [True, [[5, 2], [0, 2]], 4, 4, True], 5: [True, [[5, 2], [0, 2]], 5, 4, True]}[N])
check('3', solve([8,3,2,2,0,N]), {1: [True, [], 1, 0, False], 2: [True, [], 2, 0, False], 3: [True, [], 3, 0, False], 4: [True, [], 4, 0, False], 5: [True, [], 5, 0, False]}[N])
check('4', solve([8,3,2,1,2,N]), {1: [False, [], 1, 0, False], 2: [False, [], 2, 0, False], 3: [False, [], 3, 0, False], 4: [False, [], 4, 0, False], 5: [False, [], 5, 0, False]}[N])
check('5', solve([6,2,3,-1,2,N]), {1: [False, [], 1, 0, False], 2: [False, [], 2, 0, False], 3: [False, [], 3, 0, False], 4: [False, [], 4, 0, False], 5: [False, [], 5, 0, False]}[N])
check('6', solve([7,1,5,3,-1,N]), {1: [False, [], 1, 0, False], 2: [False, [], 2, 0, False], 3: [False, [], 3, 0, False], 4: [False, [], 4, 0, False], 5: [False, [], 5, 0, False]}[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 fixtureActualExpectedOutcome
0[True, [[7, 1], [0, 2]], 1, 3, True][True, [[7, 1], [0, 2]], 1, 3, True]Passed
1[True, [[3, 2]], 1, 2, True][True, [[3, 2]], 1, 2, True]Passed
2[True, [[5, 2], [0, 2]], 1, 4, True][True, [[5, 2], [0, 2]], 1, 4, True]Passed
3[True, [], 1, 0, False][True, [], 1, 0, False]Passed
4[True, [[4, 2]], 1, 2, True][False, [], 1, 0, False]Failed
5[False, [], 1, 0, False][False, [], 1, 0, False]Passed
6[False, [], 1, 0, False][False, [], 1, 0, False]Passed

SHA-256 / d08213a4045244091536556384a45a7b3f21da59b8135164062a0464327995f0

3 / The verified repair

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

N = 1
observations = []
def solve(x):
    cap,head,size,start,count,epoch=x
    if start<0 or count<0 or start+count>size:return [False,[],epoch,0,False]
    origin=(head+start)%cap
    first=min(count,cap-origin)
    spans=[[origin,first]] if first else []
    if count>first:spans.append([0,count-first])
    captured=epoch
    pin=count>0
    return [True,spans,captured,count,pin]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([8,6,5,1,3,N]), {1: [True, [[7, 1], [0, 2]], 1, 3, True], 2: [True, [[7, 1], [0, 2]], 2, 3, True], 3: [True, [[7, 1], [0, 2]], 3, 3, True], 4: [True, [[7, 1], [0, 2]], 4, 3, True], 5: [True, [[7, 1], [0, 2]], 5, 3, True]}[N])
check('1', solve([8,2,4,1,2,N]), {1: [True, [[3, 2]], 1, 2, True], 2: [True, [[3, 2]], 2, 2, True], 3: [True, [[3, 2]], 3, 2, True], 4: [True, [[3, 2]], 4, 2, True], 5: [True, [[3, 2]], 5, 2, True]}[N])
check('2', solve([7,5,4,0,4,N]), {1: [True, [[5, 2], [0, 2]], 1, 4, True], 2: [True, [[5, 2], [0, 2]], 2, 4, True], 3: [True, [[5, 2], [0, 2]], 3, 4, True], 4: [True, [[5, 2], [0, 2]], 4, 4, True], 5: [True, [[5, 2], [0, 2]], 5, 4, True]}[N])
check('3', solve([8,3,2,2,0,N]), {1: [True, [], 1, 0, False], 2: [True, [], 2, 0, False], 3: [True, [], 3, 0, False], 4: [True, [], 4, 0, False], 5: [True, [], 5, 0, False]}[N])
check('4', solve([8,3,2,1,2,N]), {1: [False, [], 1, 0, False], 2: [False, [], 2, 0, False], 3: [False, [], 3, 0, False], 4: [False, [], 4, 0, False], 5: [False, [], 5, 0, False]}[N])
check('5', solve([6,2,3,-1,2,N]), {1: [False, [], 1, 0, False], 2: [False, [], 2, 0, False], 3: [False, [], 3, 0, False], 4: [False, [], 4, 0, False], 5: [False, [], 5, 0, False]}[N])
check('6', solve([7,1,5,3,-1,N]), {1: [False, [], 1, 0, False], 2: [False, [], 2, 0, False], 3: [False, [], 3, 0, False], 4: [False, [], 4, 0, False], 5: [False, [], 5, 0, False]}[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 fixtureActualExpectedOutcome
0[True, [[7, 1], [0, 2]], 1, 3, True][True, [[7, 1], [0, 2]], 1, 3, True]Passed
1[True, [[3, 2]], 1, 2, True][True, [[3, 2]], 1, 2, True]Passed
2[True, [[5, 2], [0, 2]], 1, 4, True][True, [[5, 2], [0, 2]], 1, 4, True]Passed
3[True, [], 1, 0, False][True, [], 1, 0, False]Passed
4[False, [], 1, 0, False][False, [], 1, 0, False]Passed
5[False, [], 1, 0, False][False, [], 1, 0, False]Passed
6[False, [], 1, 0, False][False, [], 1, 0, False]Passed

SHA-256 / 2851c069034c3cd8ddb5cb61b343f334ab5207d9976d03a0d84ae21cb23960e7

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:33.671114+00:00.

Case digest / a2668058ee99d1a064074af37232d9c046fd1f957462e908497f5696d64e444a