FA-47096 / Bounded deques / Open access

Deque compaction builds the inverse relocation table · case 01

Deque compaction builds the inverse relocation table.

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

ROOT CAUSE

Deque compaction builds the inverse relocation table.

VERIFIED REPAIR

Restore the documented relocation direction 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={new:old 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], [3, None, None], {'0': 3, '1': 0, '2': 2}, 3, [1], 3]`	`[[3, 1, 2], [0, 1, 2], [1, 0, None], {'0': 1, '2': 2, '3': 0}, 3, [1], 3]`	Failed
1	`[[1], [0], [None, None], {'0': 1}, 1, [0, 2], 1]`	`[[1], [0], [0, None], {'1': 0}, 1, [0, 2], 1]`	Failed
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], [None, 1, None], {'0': 3, '1': 1}, 6, [0, 2, 4], 2]`	`[[2, 1], [0, 1], [0, 1, None], {'1': 1, '3': 0}, 6, [0, 2, 4], 2]`	Failed

SHA-256 / a33b233163e87df7a01419b33e5868a455e4410d9fed18f5788cdb8b5c92b200

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)} if len(order)<=1 else {new:old 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], [3, None, None], {'0': 3, '1': 0, '2': 2}, 3, [1], 3]`	`[[3, 1, 2], [0, 1, 2], [1, 0, None], {'0': 1, '2': 2, '3': 0}, 3, [1], 3]`	Failed
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], [None, 1, None], {'0': 3, '1': 1}, 6, [0, 2, 4], 2]`	`[[2, 1], [0, 1], [0, 1, None], {'1': 1, '3': 0}, 6, [0, 2, 4], 2]`	Failed

SHA-256 / 4baa13abafb2d00874c64a7bdd9ff34e073962d5a9241f4b4be88d85e1ab5728

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

Case digest / 87e2f813ed90f5c4fa9f07e46fb4a8c1ad37f0c990fa6ab728685d2bb1f27ea2