FAILURE MAP
← Case archive

FA-46886 / Bounded deques / Open access

Deque savepoint insertion overwrites outer checkpoints · case 01

Deque savepoint insertion overwrites outer checkpoints.

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

ROOT CAUSE

Deque savepoint insertion overwrites outer checkpoints.

VERIFIED REPAIR

Restore the documented snapshot stack 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,[[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 fixtureActualExpectedOutcome
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], [[4, [1]]], 4, True][[1], [[1, [0]], [4, [1]]], 4, True]Failed
5[[1], [[1, [0]]], None, False][[1], [[1, [0]]], None, False]Passed

SHA-256 / a10387972f3ad8aa7a9171343b87d72ffc92f263c88ae058967b971af65f1fab

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[:]]] if not stack else [[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 fixtureActualExpectedOutcome
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], [[4, [1]]], 4, True][[1], [[1, [0]], [4, [1]]], 4, True]Failed
5[[1], [[1, [0]]], None, False][[1], [[1, [0]]], None, False]Passed

SHA-256 / ef6e0a9a2e7b48a3778529b676a5a6336b6e35f5a0f2575255c83f846c855844

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

Case digest / 28394e8978c28aa61b572fe1377bcf460ac588c33b8751a5858a8ab0966233d6