FA-47286 / Bounded deques / Open access
Deque range swap reverses the first range · case 01
Deque range swap reverses the first range.
ROOT CAUSE
Deque range swap reverses the first range.
VERIFIED REPAIR
Restore the documented first order invariant in disjoint-range-swap.
Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.
Case contract
Swap two ordered, disjoint half-open ranges within a bounded deque. Preserve each range and middle order, permit unequal lengths, and remap stable cursors through the permutation.
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,s1,e1,s2,e2,cursors=x
prefix=list(range(s1))
second=list(range(s2,e2))
middle=list(range(e1,s2))
first=list(range(s1,e1))[::-1]
suffix=list(range(e2,len(a)))
order=prefix+second+middle+first+suffix
result=[a[i] for i in order]
updated=[order.index(i) for i in cursors]
return [result,updated,order,e1-s1,e2-s2]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2,N+3,N+4,N+5],0,1,3,5,[0,1,3,4,5]]), {1: [[4, 5, 2, 3, 1, 6], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 2: [[5, 6, 3, 4, 2, 7], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 3: [[6, 7, 4, 5, 3, 8], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 4: [[7, 8, 5, 6, 4, 9], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 5: [[8, 9, 6, 7, 5, 10], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2]}[N])
check('1', solve([[N,N+1,N+2,N+3,N+4],1,3,4,5,[0,1,2,3,4]]), {1: [[1, 5, 4, 2, 3], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 2: [[2, 6, 5, 3, 4], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 3: [[3, 7, 6, 4, 5], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 4: [[4, 8, 7, 5, 6], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 5: [[5, 9, 8, 6, 7], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1]}[N])
check('2', solve([[N,N+1,N+2,N+3],0,2,2,4,[0,1,2,3]]), {1: [[3, 4, 1, 2], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 2: [[4, 5, 2, 3], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 3: [[5, 6, 3, 4], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 4: [[6, 7, 4, 5], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 5: [[7, 8, 5, 6], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2]}[N])
check('3', solve([[N,N+1,N+2],1,1,2,3,[0,1,2]]), {1: [[1, 3, 2], [0, 2, 1], [0, 2, 1], 0, 1], 2: [[2, 4, 3], [0, 2, 1], [0, 2, 1], 0, 1], 3: [[3, 5, 4], [0, 2, 1], [0, 2, 1], 0, 1], 4: [[4, 6, 5], [0, 2, 1], [0, 2, 1], 0, 1], 5: [[5, 7, 6], [0, 2, 1], [0, 2, 1], 0, 1]}[N])
check('4', solve([[],0,0,0,0,[]]), {1: [[], [], [], 0, 0], 2: [[], [], [], 0, 0], 3: [[], [], [], 0, 0], 4: [[], [], [], 0, 0], 5: [[], [], [], 0, 0]}[N])
check('5', solve([[N,N+1,N+2,N+3,N+4,N+5,N+6],1,2,4,6,[1,2,4,5,6]]), {1: [[1, 5, 6, 3, 4, 2, 7], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 2: [[2, 6, 7, 4, 5, 3, 8], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 3: [[3, 7, 8, 5, 6, 4, 9], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 4: [[4, 8, 9, 6, 7, 5, 10], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 5: [[5, 9, 10, 7, 8, 6, 11], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2]}[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 | [[4, 5, 2, 3, 1, 6], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2] | [[4, 5, 2, 3, 1, 6], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2] | Passed |
| 1 | [[1, 5, 4, 3, 2], [0, 4, 3, 2, 1], [0, 4, 3, 2, 1], 2, 1] | [[1, 5, 4, 2, 3], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1] | Failed |
| 2 | [[3, 4, 2, 1], [3, 2, 0, 1], [2, 3, 1, 0], 2, 2] | [[3, 4, 1, 2], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2] | Failed |
| 3 | [[1, 3, 2], [0, 2, 1], [0, 2, 1], 0, 1] | [[1, 3, 2], [0, 2, 1], [0, 2, 1], 0, 1] | Passed |
| 4 | [[], [], [], 0, 0] | [[], [], [], 0, 0] | Passed |
| 5 | [[1, 5, 6, 3, 4, 2, 7], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2] | [[1, 5, 6, 3, 4, 2, 7], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2] | Passed |
SHA-256 / d39770558ba50717af0f948f1861cf8f7426d4111d85dacd34203d140a651d78
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
a,s1,e1,s2,e2,cursors=x
prefix=list(range(s1))
second=list(range(s2,e2))
middle=list(range(e1,s2))
first=list(range(s1,e1)) if s1==0 else list(range(s1,e1))[::-1]
suffix=list(range(e2,len(a)))
order=prefix+second+middle+first+suffix
result=[a[i] for i in order]
updated=[order.index(i) for i in cursors]
return [result,updated,order,e1-s1,e2-s2]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2,N+3,N+4,N+5],0,1,3,5,[0,1,3,4,5]]), {1: [[4, 5, 2, 3, 1, 6], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 2: [[5, 6, 3, 4, 2, 7], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 3: [[6, 7, 4, 5, 3, 8], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 4: [[7, 8, 5, 6, 4, 9], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 5: [[8, 9, 6, 7, 5, 10], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2]}[N])
check('1', solve([[N,N+1,N+2,N+3,N+4],1,3,4,5,[0,1,2,3,4]]), {1: [[1, 5, 4, 2, 3], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 2: [[2, 6, 5, 3, 4], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 3: [[3, 7, 6, 4, 5], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 4: [[4, 8, 7, 5, 6], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 5: [[5, 9, 8, 6, 7], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1]}[N])
check('2', solve([[N,N+1,N+2,N+3],0,2,2,4,[0,1,2,3]]), {1: [[3, 4, 1, 2], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 2: [[4, 5, 2, 3], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 3: [[5, 6, 3, 4], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 4: [[6, 7, 4, 5], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 5: [[7, 8, 5, 6], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2]}[N])
check('3', solve([[N,N+1,N+2],1,1,2,3,[0,1,2]]), {1: [[1, 3, 2], [0, 2, 1], [0, 2, 1], 0, 1], 2: [[2, 4, 3], [0, 2, 1], [0, 2, 1], 0, 1], 3: [[3, 5, 4], [0, 2, 1], [0, 2, 1], 0, 1], 4: [[4, 6, 5], [0, 2, 1], [0, 2, 1], 0, 1], 5: [[5, 7, 6], [0, 2, 1], [0, 2, 1], 0, 1]}[N])
check('4', solve([[],0,0,0,0,[]]), {1: [[], [], [], 0, 0], 2: [[], [], [], 0, 0], 3: [[], [], [], 0, 0], 4: [[], [], [], 0, 0], 5: [[], [], [], 0, 0]}[N])
check('5', solve([[N,N+1,N+2,N+3,N+4,N+5,N+6],1,2,4,6,[1,2,4,5,6]]), {1: [[1, 5, 6, 3, 4, 2, 7], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 2: [[2, 6, 7, 4, 5, 3, 8], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 3: [[3, 7, 8, 5, 6, 4, 9], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 4: [[4, 8, 9, 6, 7, 5, 10], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 5: [[5, 9, 10, 7, 8, 6, 11], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2]}[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 | [[4, 5, 2, 3, 1, 6], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2] | [[4, 5, 2, 3, 1, 6], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2] | Passed |
| 1 | [[1, 5, 4, 3, 2], [0, 4, 3, 2, 1], [0, 4, 3, 2, 1], 2, 1] | [[1, 5, 4, 2, 3], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1] | Failed |
| 2 | [[3, 4, 1, 2], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2] | [[3, 4, 1, 2], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2] | Passed |
| 3 | [[1, 3, 2], [0, 2, 1], [0, 2, 1], 0, 1] | [[1, 3, 2], [0, 2, 1], [0, 2, 1], 0, 1] | Passed |
| 4 | [[], [], [], 0, 0] | [[], [], [], 0, 0] | Passed |
| 5 | [[1, 5, 6, 3, 4, 2, 7], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2] | [[1, 5, 6, 3, 4, 2, 7], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2] | Passed |
SHA-256 / d48f773b3cfdaaf5e0cc459d6969c3c662c50dce896e3a08364d609e815251d2
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
a,s1,e1,s2,e2,cursors=x
prefix=list(range(s1))
second=list(range(s2,e2))
middle=list(range(e1,s2))
first=list(range(s1,e1))
suffix=list(range(e2,len(a)))
order=prefix+second+middle+first+suffix
result=[a[i] for i in order]
updated=[order.index(i) for i in cursors]
return [result,updated,order,e1-s1,e2-s2]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2,N+3,N+4,N+5],0,1,3,5,[0,1,3,4,5]]), {1: [[4, 5, 2, 3, 1, 6], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 2: [[5, 6, 3, 4, 2, 7], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 3: [[6, 7, 4, 5, 3, 8], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 4: [[7, 8, 5, 6, 4, 9], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2], 5: [[8, 9, 6, 7, 5, 10], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2]}[N])
check('1', solve([[N,N+1,N+2,N+3,N+4],1,3,4,5,[0,1,2,3,4]]), {1: [[1, 5, 4, 2, 3], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 2: [[2, 6, 5, 3, 4], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 3: [[3, 7, 6, 4, 5], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 4: [[4, 8, 7, 5, 6], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1], 5: [[5, 9, 8, 6, 7], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1]}[N])
check('2', solve([[N,N+1,N+2,N+3],0,2,2,4,[0,1,2,3]]), {1: [[3, 4, 1, 2], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 2: [[4, 5, 2, 3], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 3: [[5, 6, 3, 4], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 4: [[6, 7, 4, 5], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2], 5: [[7, 8, 5, 6], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2]}[N])
check('3', solve([[N,N+1,N+2],1,1,2,3,[0,1,2]]), {1: [[1, 3, 2], [0, 2, 1], [0, 2, 1], 0, 1], 2: [[2, 4, 3], [0, 2, 1], [0, 2, 1], 0, 1], 3: [[3, 5, 4], [0, 2, 1], [0, 2, 1], 0, 1], 4: [[4, 6, 5], [0, 2, 1], [0, 2, 1], 0, 1], 5: [[5, 7, 6], [0, 2, 1], [0, 2, 1], 0, 1]}[N])
check('4', solve([[],0,0,0,0,[]]), {1: [[], [], [], 0, 0], 2: [[], [], [], 0, 0], 3: [[], [], [], 0, 0], 4: [[], [], [], 0, 0], 5: [[], [], [], 0, 0]}[N])
check('5', solve([[N,N+1,N+2,N+3,N+4,N+5,N+6],1,2,4,6,[1,2,4,5,6]]), {1: [[1, 5, 6, 3, 4, 2, 7], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 2: [[2, 6, 7, 4, 5, 3, 8], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 3: [[3, 7, 8, 5, 6, 4, 9], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 4: [[4, 8, 9, 6, 7, 5, 10], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2], 5: [[5, 9, 10, 7, 8, 6, 11], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2]}[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 | [[4, 5, 2, 3, 1, 6], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2] | [[4, 5, 2, 3, 1, 6], [4, 2, 0, 1, 5], [3, 4, 1, 2, 0, 5], 1, 2] | Passed |
| 1 | [[1, 5, 4, 2, 3], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1] | [[1, 5, 4, 2, 3], [0, 3, 4, 2, 1], [0, 4, 3, 1, 2], 2, 1] | Passed |
| 2 | [[3, 4, 1, 2], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2] | [[3, 4, 1, 2], [2, 3, 0, 1], [2, 3, 0, 1], 2, 2] | Passed |
| 3 | [[1, 3, 2], [0, 2, 1], [0, 2, 1], 0, 1] | [[1, 3, 2], [0, 2, 1], [0, 2, 1], 0, 1] | Passed |
| 4 | [[], [], [], 0, 0] | [[], [], [], 0, 0] | Passed |
| 5 | [[1, 5, 6, 3, 4, 2, 7], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2] | [[1, 5, 6, 3, 4, 2, 7], [5, 3, 1, 2, 6], [0, 4, 5, 2, 3, 1, 6], 1, 2] | Passed |
SHA-256 / 91feafba68e27a03c3e620e0b6dd2989b62808f02bd769e6f3cc0b50b8e07827
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:40.031217+00:00.
Case digest / 4ad03af063e3d3c8e7e2f96f6f677899b372436c302da8105767db31eb13e748