FAILURE MAP
← Case archive

FA-46731 / Bounded deques / Open access

Deque gap insertion shifts bookmarks by one rather than batch length · case 01

Deque gap insertion shifts bookmarks by one rather than batch length.

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

ROOT CAUSE

Deque gap insertion shifts bookmarks by one rather than batch length.

VERIFIED REPAIR

Restore the documented shift distance invariant in gap-bookmarks.

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

Case contract

Insert a batch at a deque gap atomically. Left-biased bookmarks at that gap stay before inserted values, right-biased bookmarks move after them, and later gaps shift by inserted length.

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):
    a,gap,values,cap,cursors=x
    if len(a)+len(values)>cap:return [a,cursors,False,gap]
    result=a[:gap]+values+a[gap:]
    updated=[]
    for p,bias in cursors:
        move=p>gap or (p==gap and bias=='right')
        position=p+1 if move else p
        updated.append([position,bias])
    next_gap=gap+len(values)
    return [result,updated,True,next_gap]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1],1,[N+2,N+3],5,[[0,"left"],[1,"left"],[1,"right"],[2,"left"]]]), {1: [[1, 3, 4, 2], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 2: [[2, 4, 5, 3], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 3: [[3, 5, 6, 4], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 4: [[4, 6, 7, 5], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 5: [[5, 7, 8, 6], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3]}[N])
check('1', solve([[N],0,[N+1],2,[[0,"left"],[0,"right"]]]), {1: [[2, 1], [[0, 'left'], [1, 'right']], True, 1], 2: [[3, 2], [[0, 'left'], [1, 'right']], True, 1], 3: [[4, 3], [[0, 'left'], [1, 'right']], True, 1], 4: [[5, 4], [[0, 'left'], [1, 'right']], True, 1], 5: [[6, 5], [[0, 'left'], [1, 'right']], True, 1]}[N])
check('2', solve([[N,N+1],1,[N+2,N+3],3,[[1,"left"]]]), {1: [[1, 2], [[1, 'left']], False, 1], 2: [[2, 3], [[1, 'left']], False, 1], 3: [[3, 4], [[1, 'left']], False, 1], 4: [[4, 5], [[1, 'left']], False, 1], 5: [[5, 6], [[1, 'left']], False, 1]}[N])
check('3', solve([[],0,[],1,[[0,"right"]]]), {1: [[], [[0, 'right']], True, 0], 2: [[], [[0, 'right']], True, 0], 3: [[], [[0, 'right']], True, 0], 4: [[], [[0, 'right']], True, 0], 5: [[], [[0, 'right']], True, 0]}[N])
check('4', solve([[N,N+1,N+2],2,[N+3],5,[[3,"right"]]]), {1: [[1, 2, 4, 3], [[4, 'right']], True, 3], 2: [[2, 3, 5, 4], [[4, 'right']], True, 3], 3: [[3, 4, 6, 5], [[4, 'right']], True, 3], 4: [[4, 5, 7, 6], [[4, 'right']], True, 3], 5: [[5, 6, 8, 7], [[4, 'right']], True, 3]}[N])
check('5', solve([[N],1,[],2,[[1,"left"]]]), {1: [[1], [[1, 'left']], True, 1], 2: [[2], [[1, 'left']], True, 1], 3: [[3], [[1, 'left']], True, 1], 4: [[4], [[1, 'left']], True, 1], 5: [[5], [[1, 'left']], True, 1]}[N])
check('interior later bookmark', solve([[N,N+1,N+2,N+3],1,[N+4],5,[[2,'left']]]), [[N,N+4,N+1,N+2,N+3],[[3,'left']],True,2])
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[[1, 3, 4, 2], [[0, 'left'], [1, 'left'], [2, 'right'], [3, 'left']], True, 3][[1, 3, 4, 2], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3]Failed
1[[2, 1], [[0, 'left'], [1, 'right']], True, 1][[2, 1], [[0, 'left'], [1, 'right']], True, 1]Passed
2[[1, 2], [[1, 'left']], False, 1][[1, 2], [[1, 'left']], False, 1]Passed
3[[], [[1, 'right']], True, 0][[], [[0, 'right']], True, 0]Failed
4[[1, 2, 4, 3], [[4, 'right']], True, 3][[1, 2, 4, 3], [[4, 'right']], True, 3]Passed
5[[1], [[1, 'left']], True, 1][[1], [[1, 'left']], True, 1]Passed
interior later bookmark[[1, 5, 2, 3, 4], [[3, 'left']], True, 2][[1, 5, 2, 3, 4], [[3, 'left']], True, 2]Passed

SHA-256 / 6e57130d6d75e591df49f1416249f6243dec827ad948de27955494307859f06b

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(x):
    a,gap,values,cap,cursors=x
    if len(a)+len(values)>cap:return [a,cursors,False,gap]
    result=a[:gap]+values+a[gap:]
    updated=[]
    for p,bias in cursors:
        move=p>gap or (p==gap and bias=='right')
        position=p+(1 if values else 0) if move else p
        updated.append([position,bias])
    next_gap=gap+len(values)
    return [result,updated,True,next_gap]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1],1,[N+2,N+3],5,[[0,"left"],[1,"left"],[1,"right"],[2,"left"]]]), {1: [[1, 3, 4, 2], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 2: [[2, 4, 5, 3], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 3: [[3, 5, 6, 4], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 4: [[4, 6, 7, 5], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 5: [[5, 7, 8, 6], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3]}[N])
check('1', solve([[N],0,[N+1],2,[[0,"left"],[0,"right"]]]), {1: [[2, 1], [[0, 'left'], [1, 'right']], True, 1], 2: [[3, 2], [[0, 'left'], [1, 'right']], True, 1], 3: [[4, 3], [[0, 'left'], [1, 'right']], True, 1], 4: [[5, 4], [[0, 'left'], [1, 'right']], True, 1], 5: [[6, 5], [[0, 'left'], [1, 'right']], True, 1]}[N])
check('2', solve([[N,N+1],1,[N+2,N+3],3,[[1,"left"]]]), {1: [[1, 2], [[1, 'left']], False, 1], 2: [[2, 3], [[1, 'left']], False, 1], 3: [[3, 4], [[1, 'left']], False, 1], 4: [[4, 5], [[1, 'left']], False, 1], 5: [[5, 6], [[1, 'left']], False, 1]}[N])
check('3', solve([[],0,[],1,[[0,"right"]]]), {1: [[], [[0, 'right']], True, 0], 2: [[], [[0, 'right']], True, 0], 3: [[], [[0, 'right']], True, 0], 4: [[], [[0, 'right']], True, 0], 5: [[], [[0, 'right']], True, 0]}[N])
check('4', solve([[N,N+1,N+2],2,[N+3],5,[[3,"right"]]]), {1: [[1, 2, 4, 3], [[4, 'right']], True, 3], 2: [[2, 3, 5, 4], [[4, 'right']], True, 3], 3: [[3, 4, 6, 5], [[4, 'right']], True, 3], 4: [[4, 5, 7, 6], [[4, 'right']], True, 3], 5: [[5, 6, 8, 7], [[4, 'right']], True, 3]}[N])
check('5', solve([[N],1,[],2,[[1,"left"]]]), {1: [[1], [[1, 'left']], True, 1], 2: [[2], [[1, 'left']], True, 1], 3: [[3], [[1, 'left']], True, 1], 4: [[4], [[1, 'left']], True, 1], 5: [[5], [[1, 'left']], True, 1]}[N])
check('interior later bookmark', solve([[N,N+1,N+2,N+3],1,[N+4],5,[[2,'left']]]), [[N,N+4,N+1,N+2,N+3],[[3,'left']],True,2])
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[[1, 3, 4, 2], [[0, 'left'], [1, 'left'], [2, 'right'], [3, 'left']], True, 3][[1, 3, 4, 2], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3]Failed
1[[2, 1], [[0, 'left'], [1, 'right']], True, 1][[2, 1], [[0, 'left'], [1, 'right']], True, 1]Passed
2[[1, 2], [[1, 'left']], False, 1][[1, 2], [[1, 'left']], False, 1]Passed
3[[], [[0, 'right']], True, 0][[], [[0, 'right']], True, 0]Passed
4[[1, 2, 4, 3], [[4, 'right']], True, 3][[1, 2, 4, 3], [[4, 'right']], True, 3]Passed
5[[1], [[1, 'left']], True, 1][[1], [[1, 'left']], True, 1]Passed
interior later bookmark[[1, 5, 2, 3, 4], [[3, 'left']], True, 2][[1, 5, 2, 3, 4], [[3, 'left']], True, 2]Passed

SHA-256 / 66383d8564510d1bf56655b87656827834b432d5738335ade865cd1aed7337b7

3 / The verified repair

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

N = 1
observations = []
def solve(x):
    a,gap,values,cap,cursors=x
    if len(a)+len(values)>cap:return [a,cursors,False,gap]
    result=a[:gap]+values+a[gap:]
    updated=[]
    for p,bias in cursors:
        move=p>gap or (p==gap and bias=='right')
        position=p+len(values) if move else p
        updated.append([position,bias])
    next_gap=gap+len(values)
    return [result,updated,True,next_gap]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1],1,[N+2,N+3],5,[[0,"left"],[1,"left"],[1,"right"],[2,"left"]]]), {1: [[1, 3, 4, 2], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 2: [[2, 4, 5, 3], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 3: [[3, 5, 6, 4], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 4: [[4, 6, 7, 5], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3], 5: [[5, 7, 8, 6], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3]}[N])
check('1', solve([[N],0,[N+1],2,[[0,"left"],[0,"right"]]]), {1: [[2, 1], [[0, 'left'], [1, 'right']], True, 1], 2: [[3, 2], [[0, 'left'], [1, 'right']], True, 1], 3: [[4, 3], [[0, 'left'], [1, 'right']], True, 1], 4: [[5, 4], [[0, 'left'], [1, 'right']], True, 1], 5: [[6, 5], [[0, 'left'], [1, 'right']], True, 1]}[N])
check('2', solve([[N,N+1],1,[N+2,N+3],3,[[1,"left"]]]), {1: [[1, 2], [[1, 'left']], False, 1], 2: [[2, 3], [[1, 'left']], False, 1], 3: [[3, 4], [[1, 'left']], False, 1], 4: [[4, 5], [[1, 'left']], False, 1], 5: [[5, 6], [[1, 'left']], False, 1]}[N])
check('3', solve([[],0,[],1,[[0,"right"]]]), {1: [[], [[0, 'right']], True, 0], 2: [[], [[0, 'right']], True, 0], 3: [[], [[0, 'right']], True, 0], 4: [[], [[0, 'right']], True, 0], 5: [[], [[0, 'right']], True, 0]}[N])
check('4', solve([[N,N+1,N+2],2,[N+3],5,[[3,"right"]]]), {1: [[1, 2, 4, 3], [[4, 'right']], True, 3], 2: [[2, 3, 5, 4], [[4, 'right']], True, 3], 3: [[3, 4, 6, 5], [[4, 'right']], True, 3], 4: [[4, 5, 7, 6], [[4, 'right']], True, 3], 5: [[5, 6, 8, 7], [[4, 'right']], True, 3]}[N])
check('5', solve([[N],1,[],2,[[1,"left"]]]), {1: [[1], [[1, 'left']], True, 1], 2: [[2], [[1, 'left']], True, 1], 3: [[3], [[1, 'left']], True, 1], 4: [[4], [[1, 'left']], True, 1], 5: [[5], [[1, 'left']], True, 1]}[N])
check('interior later bookmark', solve([[N,N+1,N+2,N+3],1,[N+4],5,[[2,'left']]]), [[N,N+4,N+1,N+2,N+3],[[3,'left']],True,2])
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[[1, 3, 4, 2], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3][[1, 3, 4, 2], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3]Passed
1[[2, 1], [[0, 'left'], [1, 'right']], True, 1][[2, 1], [[0, 'left'], [1, 'right']], True, 1]Passed
2[[1, 2], [[1, 'left']], False, 1][[1, 2], [[1, 'left']], False, 1]Passed
3[[], [[0, 'right']], True, 0][[], [[0, 'right']], True, 0]Passed
4[[1, 2, 4, 3], [[4, 'right']], True, 3][[1, 2, 4, 3], [[4, 'right']], True, 3]Passed
5[[1], [[1, 'left']], True, 1][[1], [[1, 'left']], True, 1]Passed
interior later bookmark[[1, 5, 2, 3, 4], [[3, 'left']], True, 2][[1, 5, 2, 3, 4], [[3, 'left']], True, 2]Passed

SHA-256 / 451df95974f3f050c859102417e1fe444214911ed8a335c93220a2d65e3ea2e6

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

Case digest / e0469986a1ceff7353591265aec86b861647e4b69721163faf08b9fa2aafa9c6