FAILURE MAP
← Case archive

FA-46221 / Bounded deques / Open access

Undo restores the oldest retained snapshot · case 01

Undo restores the oldest retained snapshot.

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

ROOT CAUSE

Undo restores the oldest retained snapshot.

VERIFIED REPAIR

Restore the documented undo top invariant in undo-snapshots.

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

Case contract

Bounded deque edits store the complete prior logical snapshot. Undo and redo transfer current snapshots between independent history stacks. A new edit invalidates redo history.

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,past,future,command,value,cap=x
    if command=='edit':
        new=(a+[value])[-cap:] if cap else []
        return [new,past+[a],[]]
    if command=='undo' and past:
        return [past[0],past[:-1],future+[a]]
    if command=='redo' and future:
        return [future[-1],past+[a],future[:-1]]
    return [a,past,future]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('edit invalidates redo', solve([[N],[[N-1]],[[N+1]],"edit",N+2,3]), {1: [[1, 3], [[0], [1]], []], 2: [[2, 4], [[1], [2]], []], 3: [[3, 5], [[2], [3]], []], 4: [[4, 6], [[3], [4]], []], 5: [[5, 7], [[4], [5]], []]}[N])
check('undo latest', solve([[N+2],[[N],[N+1]],[],"undo",0,3]), {1: [[2], [[1]], [[3]]], 2: [[3], [[2]], [[4]]], 3: [[4], [[3]], [[5]]], 4: [[5], [[4]], [[6]]], 5: [[6], [[5]], [[7]]]}[N])
check('redo latest', solve([[N],[],[[N+2],[N+1]],"redo",0,3]), {1: [[2], [[1]], [[3]]], 2: [[3], [[2]], [[4]]], 3: [[4], [[3]], [[5]]], 4: [[5], [[4]], [[6]]], 5: [[6], [[5]], [[7]]]}[N])
check('empty undo', solve([[N],[],[],"undo",0,3]), {1: [[1], [], []], 2: [[2], [], []], 3: [[3], [], []], 4: [[4], [], []], 5: [[5], [], []]}[N])
check('overflow snapshot', solve([[N,N+1],[],[],"edit",N+2,2]), {1: [[2, 3], [[1, 2]], []], 2: [[3, 4], [[2, 3]], []], 3: [[4, 5], [[3, 4]], []], 4: [[5, 6], [[4, 5]], []], 5: [[6, 7], [[5, 6]], []]}[N])
check('zero bound edit', solve([[],[[N]],[],"edit",N+1,0]), {1: [[], [[1], []], []], 2: [[], [[2], []], []], 3: [[], [[3], []], []], 4: [[], [[4], []], []], 5: [[], [[5], []], []]}[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
edit invalidates redo[[1, 3], [[0], [1]], []][[1, 3], [[0], [1]], []]Passed
undo latest[[1], [[1]], [[3]]][[2], [[1]], [[3]]]Failed
redo latest[[2], [[1]], [[3]]][[2], [[1]], [[3]]]Passed
empty undo[[1], [], []][[1], [], []]Passed
overflow snapshot[[2, 3], [[1, 2]], []][[2, 3], [[1, 2]], []]Passed
zero bound edit[[], [[1], []], []][[], [[1], []], []]Passed

SHA-256 / 02a304211cefee5f8c45e21583c541106771b8acf0ed35b273020760d3b4a0bb

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(x):
    a,past,future,command,value,cap=x
    if command=='edit':
        new=(a+[value])[-cap:] if cap else []
        return [new,past+[a],[]]
    if command=='undo' and past:
        return [past[-1] if len(past)==1 else past[0],past[:-1],future+[a]]
    if command=='redo' and future:
        return [future[-1],past+[a],future[:-1]]
    return [a,past,future]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('edit invalidates redo', solve([[N],[[N-1]],[[N+1]],"edit",N+2,3]), {1: [[1, 3], [[0], [1]], []], 2: [[2, 4], [[1], [2]], []], 3: [[3, 5], [[2], [3]], []], 4: [[4, 6], [[3], [4]], []], 5: [[5, 7], [[4], [5]], []]}[N])
check('undo latest', solve([[N+2],[[N],[N+1]],[],"undo",0,3]), {1: [[2], [[1]], [[3]]], 2: [[3], [[2]], [[4]]], 3: [[4], [[3]], [[5]]], 4: [[5], [[4]], [[6]]], 5: [[6], [[5]], [[7]]]}[N])
check('redo latest', solve([[N],[],[[N+2],[N+1]],"redo",0,3]), {1: [[2], [[1]], [[3]]], 2: [[3], [[2]], [[4]]], 3: [[4], [[3]], [[5]]], 4: [[5], [[4]], [[6]]], 5: [[6], [[5]], [[7]]]}[N])
check('empty undo', solve([[N],[],[],"undo",0,3]), {1: [[1], [], []], 2: [[2], [], []], 3: [[3], [], []], 4: [[4], [], []], 5: [[5], [], []]}[N])
check('overflow snapshot', solve([[N,N+1],[],[],"edit",N+2,2]), {1: [[2, 3], [[1, 2]], []], 2: [[3, 4], [[2, 3]], []], 3: [[4, 5], [[3, 4]], []], 4: [[5, 6], [[4, 5]], []], 5: [[6, 7], [[5, 6]], []]}[N])
check('zero bound edit', solve([[],[[N]],[],"edit",N+1,0]), {1: [[], [[1], []], []], 2: [[], [[2], []], []], 3: [[], [[3], []], []], 4: [[], [[4], []], []], 5: [[], [[5], []], []]}[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
edit invalidates redo[[1, 3], [[0], [1]], []][[1, 3], [[0], [1]], []]Passed
undo latest[[1], [[1]], [[3]]][[2], [[1]], [[3]]]Failed
redo latest[[2], [[1]], [[3]]][[2], [[1]], [[3]]]Passed
empty undo[[1], [], []][[1], [], []]Passed
overflow snapshot[[2, 3], [[1, 2]], []][[2, 3], [[1, 2]], []]Passed
zero bound edit[[], [[1], []], []][[], [[1], []], []]Passed

SHA-256 / b16e14dbe7e0ff2fb735119c21c2e9982cabc419b1157ecee7ef0a881ff04c1b

3 / The verified repair

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

N = 1
observations = []
def solve(x):
    a,past,future,command,value,cap=x
    if command=='edit':
        new=(a+[value])[-cap:] if cap else []
        return [new,past+[a],[]]
    if command=='undo' and past:
        return [past[-1],past[:-1],future+[a]]
    if command=='redo' and future:
        return [future[-1],past+[a],future[:-1]]
    return [a,past,future]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('edit invalidates redo', solve([[N],[[N-1]],[[N+1]],"edit",N+2,3]), {1: [[1, 3], [[0], [1]], []], 2: [[2, 4], [[1], [2]], []], 3: [[3, 5], [[2], [3]], []], 4: [[4, 6], [[3], [4]], []], 5: [[5, 7], [[4], [5]], []]}[N])
check('undo latest', solve([[N+2],[[N],[N+1]],[],"undo",0,3]), {1: [[2], [[1]], [[3]]], 2: [[3], [[2]], [[4]]], 3: [[4], [[3]], [[5]]], 4: [[5], [[4]], [[6]]], 5: [[6], [[5]], [[7]]]}[N])
check('redo latest', solve([[N],[],[[N+2],[N+1]],"redo",0,3]), {1: [[2], [[1]], [[3]]], 2: [[3], [[2]], [[4]]], 3: [[4], [[3]], [[5]]], 4: [[5], [[4]], [[6]]], 5: [[6], [[5]], [[7]]]}[N])
check('empty undo', solve([[N],[],[],"undo",0,3]), {1: [[1], [], []], 2: [[2], [], []], 3: [[3], [], []], 4: [[4], [], []], 5: [[5], [], []]}[N])
check('overflow snapshot', solve([[N,N+1],[],[],"edit",N+2,2]), {1: [[2, 3], [[1, 2]], []], 2: [[3, 4], [[2, 3]], []], 3: [[4, 5], [[3, 4]], []], 4: [[5, 6], [[4, 5]], []], 5: [[6, 7], [[5, 6]], []]}[N])
check('zero bound edit', solve([[],[[N]],[],"edit",N+1,0]), {1: [[], [[1], []], []], 2: [[], [[2], []], []], 3: [[], [[3], []], []], 4: [[], [[4], []], []], 5: [[], [[5], []], []]}[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
edit invalidates redo[[1, 3], [[0], [1]], []][[1, 3], [[0], [1]], []]Passed
undo latest[[2], [[1]], [[3]]][[2], [[1]], [[3]]]Passed
redo latest[[2], [[1]], [[3]]][[2], [[1]], [[3]]]Passed
empty undo[[1], [], []][[1], [], []]Passed
overflow snapshot[[2, 3], [[1, 2]], []][[2, 3], [[1, 2]], []]Passed
zero bound edit[[], [[1], []], []][[], [[1], []], []]Passed

SHA-256 / da55aae5a8afface8a7c50ef27009098fbb82025e99083b705a070db635cce46

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

Case digest / 6f8713b907d3f8d60f9dc09f195a5d58ee278203557acda548179177a4d5cab3