FA-46906 / Bounded deques / Open access
Deque rollback discards outer checkpoints and retains nested ones · case 01
Deque rollback discards outer checkpoints and retains nested ones.
ROOT CAUSE
Deque rollback discards outer checkpoints and retains nested ones.
VERIFIED REPAIR
Restore the documented nested discard invariant in nested-checkpoints.
Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.
Case contract
Deque savepoints capture ordered snapshots by unique tag. Rolling back restores a named snapshot and discards it plus nested checkpoints. Release discards the same checkpoint suffix without restoring data. Unknown tags preserve state.
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,stack,op,tag=x
if op=='save':return [a,stack+[[tag,a[:]]],tag,True]
where=next((i for i,z in enumerate(stack) if z[0]==tag),None)
if where is None:return [a,stack,None,False]
retained=stack[where+1:]
state=stack[where][1][:] if op=='rollback' else a[:]
return [state,retained,tag,True]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N+2],[[1,[N]],[2,[N+1]]],"rollback",1]), {1: [[1], [], 1, True], 2: [[2], [], 1, True], 3: [[3], [], 1, True], 4: [[4], [], 1, True], 5: [[5], [], 1, True]}[N])
check('1', solve([[N+2],[[1,[N]],[2,[N+1]]],"rollback",2]), {1: [[2], [[1, [1]]], 2, True], 2: [[3], [[1, [2]]], 2, True], 3: [[4], [[1, [3]]], 2, True], 4: [[5], [[1, [4]]], 2, True], 5: [[6], [[1, [5]]], 2, True]}[N])
check('2', solve([[N+2],[[1,[N]],[2,[N+1]]],"release",1]), {1: [[3], [], 1, True], 2: [[4], [], 1, True], 3: [[5], [], 1, True], 4: [[6], [], 1, True], 5: [[7], [], 1, True]}[N])
check('3', solve([[N],[],"save",3]), {1: [[1], [[3, [1]]], 3, True], 2: [[2], [[3, [2]]], 3, True], 3: [[3], [[3, [3]]], 3, True], 4: [[4], [[3, [4]]], 3, True], 5: [[5], [[3, [5]]], 3, True]}[N])
check('4', solve([[N],[[1,[N-1]]],"save",4]), {1: [[1], [[1, [0]], [4, [1]]], 4, True], 2: [[2], [[1, [1]], [4, [2]]], 4, True], 3: [[3], [[1, [2]], [4, [3]]], 4, True], 4: [[4], [[1, [3]], [4, [4]]], 4, True], 5: [[5], [[1, [4]], [4, [5]]], 4, True]}[N])
check('5', solve([[N],[[1,[N-1]]],"rollback",9]), {1: [[1], [[1, [0]]], None, False], 2: [[2], [[1, [1]]], None, False], 3: [[3], [[1, [2]]], None, False], 4: [[4], [[1, [3]]], None, False], 5: [[5], [[1, [4]]], None, 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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| 0 | [[1], [[2, [2]]], 1, True] | [[1], [], 1, True] | Failed |
| 1 | [[2], [], 2, True] | [[2], [[1, [1]]], 2, True] | Failed |
| 2 | [[3], [[2, [2]]], 1, True] | [[3], [], 1, True] | Failed |
| 3 | [[1], [[3, [1]]], 3, True] | [[1], [[3, [1]]], 3, True] | Passed |
| 4 | [[1], [[1, [0]], [4, [1]]], 4, True] | [[1], [[1, [0]], [4, [1]]], 4, True] | Passed |
| 5 | [[1], [[1, [0]]], None, False] | [[1], [[1, [0]]], None, False] | Passed |
SHA-256 / b6918e51bf2ba86ff5eb0b203217cad8c4289632060ced68df32a747564dce15
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
a,stack,op,tag=x
if op=='save':return [a,stack+[[tag,a[:]]],tag,True]
where=next((i for i,z in enumerate(stack) if z[0]==tag),None)
if where is None:return [a,stack,None,False]
retained=stack[:where] if where==len(stack)-1 else stack[where+1:]
state=stack[where][1][:] if op=='rollback' else a[:]
return [state,retained,tag,True]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N+2],[[1,[N]],[2,[N+1]]],"rollback",1]), {1: [[1], [], 1, True], 2: [[2], [], 1, True], 3: [[3], [], 1, True], 4: [[4], [], 1, True], 5: [[5], [], 1, True]}[N])
check('1', solve([[N+2],[[1,[N]],[2,[N+1]]],"rollback",2]), {1: [[2], [[1, [1]]], 2, True], 2: [[3], [[1, [2]]], 2, True], 3: [[4], [[1, [3]]], 2, True], 4: [[5], [[1, [4]]], 2, True], 5: [[6], [[1, [5]]], 2, True]}[N])
check('2', solve([[N+2],[[1,[N]],[2,[N+1]]],"release",1]), {1: [[3], [], 1, True], 2: [[4], [], 1, True], 3: [[5], [], 1, True], 4: [[6], [], 1, True], 5: [[7], [], 1, True]}[N])
check('3', solve([[N],[],"save",3]), {1: [[1], [[3, [1]]], 3, True], 2: [[2], [[3, [2]]], 3, True], 3: [[3], [[3, [3]]], 3, True], 4: [[4], [[3, [4]]], 3, True], 5: [[5], [[3, [5]]], 3, True]}[N])
check('4', solve([[N],[[1,[N-1]]],"save",4]), {1: [[1], [[1, [0]], [4, [1]]], 4, True], 2: [[2], [[1, [1]], [4, [2]]], 4, True], 3: [[3], [[1, [2]], [4, [3]]], 4, True], 4: [[4], [[1, [3]], [4, [4]]], 4, True], 5: [[5], [[1, [4]], [4, [5]]], 4, True]}[N])
check('5', solve([[N],[[1,[N-1]]],"rollback",9]), {1: [[1], [[1, [0]]], None, False], 2: [[2], [[1, [1]]], None, False], 3: [[3], [[1, [2]]], None, False], 4: [[4], [[1, [3]]], None, False], 5: [[5], [[1, [4]]], None, 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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| 0 | [[1], [[2, [2]]], 1, True] | [[1], [], 1, True] | Failed |
| 1 | [[2], [[1, [1]]], 2, True] | [[2], [[1, [1]]], 2, True] | Passed |
| 2 | [[3], [[2, [2]]], 1, True] | [[3], [], 1, True] | Failed |
| 3 | [[1], [[3, [1]]], 3, True] | [[1], [[3, [1]]], 3, True] | Passed |
| 4 | [[1], [[1, [0]], [4, [1]]], 4, True] | [[1], [[1, [0]], [4, [1]]], 4, True] | Passed |
| 5 | [[1], [[1, [0]]], None, False] | [[1], [[1, [0]]], None, False] | Passed |
SHA-256 / dcaa80d7f260bde0741ffa192c8093d8ea6c14d5d99ab79c2d692056922335b2
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
a,stack,op,tag=x
if op=='save':return [a,stack+[[tag,a[:]]],tag,True]
where=next((i for i,z in enumerate(stack) if z[0]==tag),None)
if where is None:return [a,stack,None,False]
retained=stack[:where]
state=stack[where][1][:] if op=='rollback' else a[:]
return [state,retained,tag,True]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N+2],[[1,[N]],[2,[N+1]]],"rollback",1]), {1: [[1], [], 1, True], 2: [[2], [], 1, True], 3: [[3], [], 1, True], 4: [[4], [], 1, True], 5: [[5], [], 1, True]}[N])
check('1', solve([[N+2],[[1,[N]],[2,[N+1]]],"rollback",2]), {1: [[2], [[1, [1]]], 2, True], 2: [[3], [[1, [2]]], 2, True], 3: [[4], [[1, [3]]], 2, True], 4: [[5], [[1, [4]]], 2, True], 5: [[6], [[1, [5]]], 2, True]}[N])
check('2', solve([[N+2],[[1,[N]],[2,[N+1]]],"release",1]), {1: [[3], [], 1, True], 2: [[4], [], 1, True], 3: [[5], [], 1, True], 4: [[6], [], 1, True], 5: [[7], [], 1, True]}[N])
check('3', solve([[N],[],"save",3]), {1: [[1], [[3, [1]]], 3, True], 2: [[2], [[3, [2]]], 3, True], 3: [[3], [[3, [3]]], 3, True], 4: [[4], [[3, [4]]], 3, True], 5: [[5], [[3, [5]]], 3, True]}[N])
check('4', solve([[N],[[1,[N-1]]],"save",4]), {1: [[1], [[1, [0]], [4, [1]]], 4, True], 2: [[2], [[1, [1]], [4, [2]]], 4, True], 3: [[3], [[1, [2]], [4, [3]]], 4, True], 4: [[4], [[1, [3]], [4, [4]]], 4, True], 5: [[5], [[1, [4]], [4, [5]]], 4, True]}[N])
check('5', solve([[N],[[1,[N-1]]],"rollback",9]), {1: [[1], [[1, [0]]], None, False], 2: [[2], [[1, [1]]], None, False], 3: [[3], [[1, [2]]], None, False], 4: [[4], [[1, [3]]], None, False], 5: [[5], [[1, [4]]], None, 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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| 0 | [[1], [], 1, True] | [[1], [], 1, True] | Passed |
| 1 | [[2], [[1, [1]]], 2, True] | [[2], [[1, [1]]], 2, True] | Passed |
| 2 | [[3], [], 1, True] | [[3], [], 1, True] | Passed |
| 3 | [[1], [[3, [1]]], 3, True] | [[1], [[3, [1]]], 3, True] | Passed |
| 4 | [[1], [[1, [0]], [4, [1]]], 4, True] | [[1], [[1, [0]], [4, [1]]], 4, True] | Passed |
| 5 | [[1], [[1, [0]]], None, False] | [[1], [[1, [0]]], None, False] | Passed |
SHA-256 / 7750aaa508db48ef2d6f81ac9d3a162d24ff25dadb23f315531b1ad6238c63bc
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:36.503771+00:00.
Case digest / d095dd5eb44632513cd5f7e30d9a54226b9b99798fd8635231c17ab0a6862d56