FA-46716 / Bounded deques / Open access
Bookmark insertion appends its values at the tail · case 01
Bookmark insertion appends its values at the tail.
ROOT CAUSE
Bookmark insertion appends its values at the tail.
VERIFIED REPAIR
Restore the documented insert position 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+values
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| 0 | [[1, 2, 3, 4], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3] | [[1, 3, 4, 2], [[0, 'left'], [1, 'left'], [3, 'right'], [4, 'left']], True, 3] | Failed |
| 1 | [[1, 2], [[0, 'left'], [1, 'right']], True, 1] | [[2, 1], [[0, 'left'], [1, 'right']], True, 1] | Failed |
| 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, 3, 4], [[4, 'right']], True, 3] | [[1, 2, 4, 3], [[4, 'right']], True, 3] | Failed |
| 5 | [[1], [[1, 'left']], True, 1] | [[1], [[1, 'left']], True, 1] | Passed |
| interior later bookmark | [[1, 2, 3, 4, 5], [[3, 'left']], True, 2] | [[1, 5, 2, 3, 4], [[3, 'left']], True, 2] | Failed |
SHA-256 / 3084009b1335074435beb13ab88876b31a3c990f5d340236af870a1484aa9f70
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:] if gap==0 else a+values
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| 0 | [[1, 2, 3, 4], [[0, 'left'], [1, 'left'], [3, 'right'], [4, '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, 3, 4], [[4, 'right']], True, 3] | [[1, 2, 4, 3], [[4, 'right']], True, 3] | Failed |
| 5 | [[1], [[1, 'left']], True, 1] | [[1], [[1, 'left']], True, 1] | Passed |
| interior later bookmark | [[1, 2, 3, 4, 5], [[3, 'left']], True, 2] | [[1, 5, 2, 3, 4], [[3, 'left']], True, 2] | Failed |
SHA-256 / 2ea1a23ce59b53af189b1b35f6ba2c06e974fab476058fc415231912d0bd50a2
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| 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.695649+00:00.
Case digest / d58a0be2d58a1395ee743f49da5fedb944fb541c16a6f11c72abef2052b78b2b