FA-46216 / Bounded deques / Open access

New deque edit retains the abandoned redo branch · case 01

New deque edit retains the abandoned redo branch.

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

ROOT CAUSE

New deque edit retains the abandoned redo branch.

VERIFIED REPAIR

Restore the documented redo invalidation 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],future]
    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 fixture	Actual	Expected	Outcome
edit invalidates redo	`[[1, 3], [[0], [1]], [[2]]]`	`[[1, 3], [[0], [1]], []]`	Failed
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 / 162838e4a31d8ebfe6c70b110442f40de36ea7df6ac705159b71b38bb780bca1

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],future if past else []]
    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 fixture	Actual	Expected	Outcome
edit invalidates redo	`[[1, 3], [[0], [1]], [[2]]]`	`[[1, 3], [[0], [1]], []]`	Failed
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 / af6d73b47645bb147003cc4c7a96f0c0246bc41bcfe7fd8a1e459332c726e627

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 fixture	Actual	Expected	Outcome
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.911238+00:00.

Case digest / 4c2849a194c605e442855191191e617280eecabb9f6b444378d9dfcdeb3dc88b