FA-47106 / Bounded deques / Open access

Deque compaction leaves old IDs in its traversal chain · case 01

Deque compaction leaves old IDs in its traversal chain.

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

ROOT CAUSE

Deque compaction leaves old IDs in its traversal chain.

VERIFIED REPAIR

Restore the documented chain rebuild invariant in arena-compaction.

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

Case contract

Compact a deque node arena using its logical live-ID chain. Preserve chain order, remap nullable stable cursors, return old-to-new relocation map, advance epoch, and identify reclaimed old storage IDs.

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):
    records,order,cursors,epoch=x
    mapping={old:new for new,old in enumerate(order)}
    storage=[records[old] for old in order]
    chain=order[:]
    updated=[mapping.get(c) if c is not None else None for c in cursors]
    version=epoch+1
    freed=sorted(set(range(len(records)))-set(order))
    count=len(order)
    return [storage,chain,updated,mapping,version,freed,count]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,None,N+1,N+2],[3,0,2],[0,3,None],2]), {1: [[3, 1, 2], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 2: [[4, 2, 3], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 3: [[5, 3, 4], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 4: [[6, 4, 5], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 5: [[7, 5, 6], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3]}[N])
check('1', solve([[None,N,None],[1],[1,None],0]), {1: [[1], [0], [0, None], {1: 0}, 1, [0, 2], 1], 2: [[2], [0], [0, None], {1: 0}, 1, [0, 2], 1], 3: [[3], [0], [0, None], {1: 0}, 1, [0, 2], 1], 4: [[4], [0], [0, None], {1: 0}, 1, [0, 2], 1], 5: [[5], [0], [0, None], {1: 0}, 1, [0, 2], 1]}[N])
check('2', solve([[N,N+1,N+2],[2,1,0],[0,1,2],4]), {1: [[3, 2, 1], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 2: [[4, 3, 2], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 3: [[5, 4, 3], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 4: [[6, 5, 4], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 5: [[7, 6, 5], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3]}[N])
check('3', solve([[],[],[None],1]), {1: [[], [], [None], {}, 2, [], 0], 2: [[], [], [None], {}, 2, [], 0], 3: [[], [], [None], {}, 2, [], 0], 4: [[], [], [None], {}, 2, [], 0], 5: [[], [], [None], {}, 2, [], 0]}[N])
check('4', solve([[N,N+1],[0,1],[],3]), {1: [[1, 2], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 2: [[2, 3], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 3: [[3, 4], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 4: [[4, 5], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 5: [[5, 6], [0, 1], [], {0: 0, 1: 1}, 4, [], 2]}[N])
check('5', solve([[None,N,None,N+1,None],[3,1],[3,1,None],5]), {1: [[2, 1], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 2: [[3, 2], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 3: [[4, 3], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 4: [[5, 4], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 5: [[6, 5], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 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	`[[3, 1, 2], [3, 0, 2], [1, 0, None], {'0': 1, '2': 2, '3': 0}, 3, [1], 3]`	`[[3, 1, 2], [0, 1, 2], [1, 0, None], {'0': 1, '2': 2, '3': 0}, 3, [1], 3]`	Failed
1	`[[1], [1], [0, None], {'1': 0}, 1, [0, 2], 1]`	`[[1], [0], [0, None], {'1': 0}, 1, [0, 2], 1]`	Failed
2	`[[3, 2, 1], [2, 1, 0], [2, 1, 0], {'0': 2, '1': 1, '2': 0}, 5, [], 3]`	`[[3, 2, 1], [0, 1, 2], [2, 1, 0], {'0': 2, '1': 1, '2': 0}, 5, [], 3]`	Failed
3	`[[], [], [None], {}, 2, [], 0]`	`[[], [], [None], {}, 2, [], 0]`	Passed
4	`[[1, 2], [0, 1], [], {'0': 0, '1': 1}, 4, [], 2]`	`[[1, 2], [0, 1], [], {'0': 0, '1': 1}, 4, [], 2]`	Passed
5	`[[2, 1], [3, 1], [0, 1, None], {'1': 1, '3': 0}, 6, [0, 2, 4], 2]`	`[[2, 1], [0, 1], [0, 1, None], {'1': 1, '3': 0}, 6, [0, 2, 4], 2]`	Failed

SHA-256 / fb57e4188d23ba673bcac3a71fe96e84c109e556b2200b1156bb86c75af96a3a

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(x):
    records,order,cursors,epoch=x
    mapping={old:new for new,old in enumerate(order)}
    storage=[records[old] for old in order]
    chain=list(range(len(order))) if not order else order[:]
    updated=[mapping.get(c) if c is not None else None for c in cursors]
    version=epoch+1
    freed=sorted(set(range(len(records)))-set(order))
    count=len(order)
    return [storage,chain,updated,mapping,version,freed,count]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,None,N+1,N+2],[3,0,2],[0,3,None],2]), {1: [[3, 1, 2], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 2: [[4, 2, 3], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 3: [[5, 3, 4], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 4: [[6, 4, 5], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 5: [[7, 5, 6], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3]}[N])
check('1', solve([[None,N,None],[1],[1,None],0]), {1: [[1], [0], [0, None], {1: 0}, 1, [0, 2], 1], 2: [[2], [0], [0, None], {1: 0}, 1, [0, 2], 1], 3: [[3], [0], [0, None], {1: 0}, 1, [0, 2], 1], 4: [[4], [0], [0, None], {1: 0}, 1, [0, 2], 1], 5: [[5], [0], [0, None], {1: 0}, 1, [0, 2], 1]}[N])
check('2', solve([[N,N+1,N+2],[2,1,0],[0,1,2],4]), {1: [[3, 2, 1], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 2: [[4, 3, 2], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 3: [[5, 4, 3], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 4: [[6, 5, 4], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 5: [[7, 6, 5], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3]}[N])
check('3', solve([[],[],[None],1]), {1: [[], [], [None], {}, 2, [], 0], 2: [[], [], [None], {}, 2, [], 0], 3: [[], [], [None], {}, 2, [], 0], 4: [[], [], [None], {}, 2, [], 0], 5: [[], [], [None], {}, 2, [], 0]}[N])
check('4', solve([[N,N+1],[0,1],[],3]), {1: [[1, 2], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 2: [[2, 3], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 3: [[3, 4], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 4: [[4, 5], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 5: [[5, 6], [0, 1], [], {0: 0, 1: 1}, 4, [], 2]}[N])
check('5', solve([[None,N,None,N+1,None],[3,1],[3,1,None],5]), {1: [[2, 1], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 2: [[3, 2], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 3: [[4, 3], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 4: [[5, 4], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 5: [[6, 5], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 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	`[[3, 1, 2], [3, 0, 2], [1, 0, None], {'0': 1, '2': 2, '3': 0}, 3, [1], 3]`	`[[3, 1, 2], [0, 1, 2], [1, 0, None], {'0': 1, '2': 2, '3': 0}, 3, [1], 3]`	Failed
1	`[[1], [1], [0, None], {'1': 0}, 1, [0, 2], 1]`	`[[1], [0], [0, None], {'1': 0}, 1, [0, 2], 1]`	Failed
2	`[[3, 2, 1], [2, 1, 0], [2, 1, 0], {'0': 2, '1': 1, '2': 0}, 5, [], 3]`	`[[3, 2, 1], [0, 1, 2], [2, 1, 0], {'0': 2, '1': 1, '2': 0}, 5, [], 3]`	Failed
3	`[[], [], [None], {}, 2, [], 0]`	`[[], [], [None], {}, 2, [], 0]`	Passed
4	`[[1, 2], [0, 1], [], {'0': 0, '1': 1}, 4, [], 2]`	`[[1, 2], [0, 1], [], {'0': 0, '1': 1}, 4, [], 2]`	Passed
5	`[[2, 1], [3, 1], [0, 1, None], {'1': 1, '3': 0}, 6, [0, 2, 4], 2]`	`[[2, 1], [0, 1], [0, 1, None], {'1': 1, '3': 0}, 6, [0, 2, 4], 2]`	Failed

SHA-256 / 3cf6413d0fb52e029378121a2c85adcd982d6f274e772cf1c3092ee0d7d66e98

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(x):
    records,order,cursors,epoch=x
    mapping={old:new for new,old in enumerate(order)}
    storage=[records[old] for old in order]
    chain=list(range(len(order)))
    updated=[mapping.get(c) if c is not None else None for c in cursors]
    version=epoch+1
    freed=sorted(set(range(len(records)))-set(order))
    count=len(order)
    return [storage,chain,updated,mapping,version,freed,count]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,None,N+1,N+2],[3,0,2],[0,3,None],2]), {1: [[3, 1, 2], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 2: [[4, 2, 3], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 3: [[5, 3, 4], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 4: [[6, 4, 5], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3], 5: [[7, 5, 6], [0, 1, 2], [1, 0, None], {3: 0, 0: 1, 2: 2}, 3, [1], 3]}[N])
check('1', solve([[None,N,None],[1],[1,None],0]), {1: [[1], [0], [0, None], {1: 0}, 1, [0, 2], 1], 2: [[2], [0], [0, None], {1: 0}, 1, [0, 2], 1], 3: [[3], [0], [0, None], {1: 0}, 1, [0, 2], 1], 4: [[4], [0], [0, None], {1: 0}, 1, [0, 2], 1], 5: [[5], [0], [0, None], {1: 0}, 1, [0, 2], 1]}[N])
check('2', solve([[N,N+1,N+2],[2,1,0],[0,1,2],4]), {1: [[3, 2, 1], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 2: [[4, 3, 2], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 3: [[5, 4, 3], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 4: [[6, 5, 4], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3], 5: [[7, 6, 5], [0, 1, 2], [2, 1, 0], {2: 0, 1: 1, 0: 2}, 5, [], 3]}[N])
check('3', solve([[],[],[None],1]), {1: [[], [], [None], {}, 2, [], 0], 2: [[], [], [None], {}, 2, [], 0], 3: [[], [], [None], {}, 2, [], 0], 4: [[], [], [None], {}, 2, [], 0], 5: [[], [], [None], {}, 2, [], 0]}[N])
check('4', solve([[N,N+1],[0,1],[],3]), {1: [[1, 2], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 2: [[2, 3], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 3: [[3, 4], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 4: [[4, 5], [0, 1], [], {0: 0, 1: 1}, 4, [], 2], 5: [[5, 6], [0, 1], [], {0: 0, 1: 1}, 4, [], 2]}[N])
check('5', solve([[None,N,None,N+1,None],[3,1],[3,1,None],5]), {1: [[2, 1], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 2: [[3, 2], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 3: [[4, 3], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 4: [[5, 4], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 2], 5: [[6, 5], [0, 1], [0, 1, None], {3: 0, 1: 1}, 6, [0, 2, 4], 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	`[[3, 1, 2], [0, 1, 2], [1, 0, None], {'0': 1, '2': 2, '3': 0}, 3, [1], 3]`	`[[3, 1, 2], [0, 1, 2], [1, 0, None], {'0': 1, '2': 2, '3': 0}, 3, [1], 3]`	Passed
1	`[[1], [0], [0, None], {'1': 0}, 1, [0, 2], 1]`	`[[1], [0], [0, None], {'1': 0}, 1, [0, 2], 1]`	Passed
2	`[[3, 2, 1], [0, 1, 2], [2, 1, 0], {'0': 2, '1': 1, '2': 0}, 5, [], 3]`	`[[3, 2, 1], [0, 1, 2], [2, 1, 0], {'0': 2, '1': 1, '2': 0}, 5, [], 3]`	Passed
3	`[[], [], [None], {}, 2, [], 0]`	`[[], [], [None], {}, 2, [], 0]`	Passed
4	`[[1, 2], [0, 1], [], {'0': 0, '1': 1}, 4, [], 2]`	`[[1, 2], [0, 1], [], {'0': 0, '1': 1}, 4, [], 2]`	Passed
5	`[[2, 1], [0, 1], [0, 1, None], {'1': 1, '3': 0}, 6, [0, 2, 4], 2]`	`[[2, 1], [0, 1], [0, 1, None], {'1': 1, '3': 0}, 6, [0, 2, 4], 2]`	Passed

SHA-256 / 3b0235b84bab158185508f881ce99e84019544415c5c4666b32b21ff37583c8c

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

Case digest / 59c54f5d7ef70115b9d72d2c36c0540e0413a964ffca4e255d7751a58b3f2d7b