FA-46866 / Bounded deques / Open access

Deque rebalance gives the left block the right identity · case 01

Deque rebalance gives the left block the right identity.

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

ROOT CAUSE

Deque rebalance gives the left block the right identity.

VERIFIED REPAIR

Restore the documented left id stability invariant in block-rebalance.

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

Case contract

Redistribute two adjacent deque blocks to a requested left occupancy without changing element order or block identities. Return signed left-to-right transfer count and new directory lengths.

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,b,target,aid,bid=x
    joined=a+b
    left=joined[:target]
    right=joined[target:]
    left_id=bid
    right_id=bid
    transfer=len(a)-target
    directory=[[left_id,len(left)],[right_id,len(right)]]
    return [left,right,left_id,right_id,transfer,directory]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],[N+3],2,3,8]), {1: [[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]], 2: [[2, 3], [4, 5], 3, 8, 1, [[3, 2], [8, 2]]], 3: [[3, 4], [5, 6], 3, 8, 1, [[3, 2], [8, 2]]], 4: [[4, 5], [6, 7], 3, 8, 1, [[3, 2], [8, 2]]], 5: [[5, 6], [7, 8], 3, 8, 1, [[3, 2], [8, 2]]]}[N])
check('1', solve([[N],[N+1,N+2,N+3],3,4,9]), {1: [[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]], 2: [[2, 3, 4], [5], 4, 9, -2, [[4, 3], [9, 1]]], 3: [[3, 4, 5], [6], 4, 9, -2, [[4, 3], [9, 1]]], 4: [[4, 5, 6], [7], 4, 9, -2, [[4, 3], [9, 1]]], 5: [[5, 6, 7], [8], 4, 9, -2, [[4, 3], [9, 1]]]}[N])
check('2', solve([[N,N+1],[N+2,N+3],2,5,10]), {1: [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]], 2: [[2, 3], [4, 5], 5, 10, 0, [[5, 2], [10, 2]]], 3: [[3, 4], [5, 6], 5, 10, 0, [[5, 2], [10, 2]]], 4: [[4, 5], [6, 7], 5, 10, 0, [[5, 2], [10, 2]]], 5: [[5, 6], [7, 8], 5, 10, 0, [[5, 2], [10, 2]]]}[N])
check('3', solve([[],[N,N+1],1,2,7]), {1: [[1], [2], 2, 7, -1, [[2, 1], [7, 1]]], 2: [[2], [3], 2, 7, -1, [[2, 1], [7, 1]]], 3: [[3], [4], 2, 7, -1, [[2, 1], [7, 1]]], 4: [[4], [5], 2, 7, -1, [[2, 1], [7, 1]]], 5: [[5], [6], 2, 7, -1, [[2, 1], [7, 1]]]}[N])
check('4', solve([[N,N+1],[],0,4,6]), {1: [[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]], 2: [[], [2, 3], 4, 6, 2, [[4, 0], [6, 2]]], 3: [[], [3, 4], 4, 6, 2, [[4, 0], [6, 2]]], 4: [[], [4, 5], 4, 6, 2, [[4, 0], [6, 2]]], 5: [[], [5, 6], 4, 6, 2, [[4, 0], [6, 2]]]}[N])
check('5', solve([[N],[N+1],2,1,5]), {1: [[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]], 2: [[2, 3], [], 1, 5, -1, [[1, 2], [5, 0]]], 3: [[3, 4], [], 1, 5, -1, [[1, 2], [5, 0]]], 4: [[4, 5], [], 1, 5, -1, [[1, 2], [5, 0]]], 5: [[5, 6], [], 1, 5, -1, [[1, 2], [5, 0]]]}[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	`[[1, 2], [3, 4], 8, 8, 1, [[8, 2], [8, 2]]]`	`[[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]]`	Failed
1	`[[1, 2, 3], [4], 9, 9, -2, [[9, 3], [9, 1]]]`	`[[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]]`	Failed
2	`[[1, 2], [3, 4], 10, 10, 0, [[10, 2], [10, 2]]]`	`[[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]]`	Failed
3	`[[1], [2], 7, 7, -1, [[7, 1], [7, 1]]]`	`[[1], [2], 2, 7, -1, [[2, 1], [7, 1]]]`	Failed
4	`[[], [1, 2], 6, 6, 2, [[6, 0], [6, 2]]]`	`[[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]]`	Failed
5	`[[1, 2], [], 5, 5, -1, [[5, 2], [5, 0]]]`	`[[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]]`	Failed

SHA-256 / 2bee9dc94bee256521636b1701724c3a9cc2896940a23a0e452c1db99d0822d8

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(x):
    a,b,target,aid,bid=x
    joined=a+b
    left=joined[:target]
    right=joined[target:]
    left_id=aid if target==len(a) else bid
    right_id=bid
    transfer=len(a)-target
    directory=[[left_id,len(left)],[right_id,len(right)]]
    return [left,right,left_id,right_id,transfer,directory]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],[N+3],2,3,8]), {1: [[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]], 2: [[2, 3], [4, 5], 3, 8, 1, [[3, 2], [8, 2]]], 3: [[3, 4], [5, 6], 3, 8, 1, [[3, 2], [8, 2]]], 4: [[4, 5], [6, 7], 3, 8, 1, [[3, 2], [8, 2]]], 5: [[5, 6], [7, 8], 3, 8, 1, [[3, 2], [8, 2]]]}[N])
check('1', solve([[N],[N+1,N+2,N+3],3,4,9]), {1: [[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]], 2: [[2, 3, 4], [5], 4, 9, -2, [[4, 3], [9, 1]]], 3: [[3, 4, 5], [6], 4, 9, -2, [[4, 3], [9, 1]]], 4: [[4, 5, 6], [7], 4, 9, -2, [[4, 3], [9, 1]]], 5: [[5, 6, 7], [8], 4, 9, -2, [[4, 3], [9, 1]]]}[N])
check('2', solve([[N,N+1],[N+2,N+3],2,5,10]), {1: [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]], 2: [[2, 3], [4, 5], 5, 10, 0, [[5, 2], [10, 2]]], 3: [[3, 4], [5, 6], 5, 10, 0, [[5, 2], [10, 2]]], 4: [[4, 5], [6, 7], 5, 10, 0, [[5, 2], [10, 2]]], 5: [[5, 6], [7, 8], 5, 10, 0, [[5, 2], [10, 2]]]}[N])
check('3', solve([[],[N,N+1],1,2,7]), {1: [[1], [2], 2, 7, -1, [[2, 1], [7, 1]]], 2: [[2], [3], 2, 7, -1, [[2, 1], [7, 1]]], 3: [[3], [4], 2, 7, -1, [[2, 1], [7, 1]]], 4: [[4], [5], 2, 7, -1, [[2, 1], [7, 1]]], 5: [[5], [6], 2, 7, -1, [[2, 1], [7, 1]]]}[N])
check('4', solve([[N,N+1],[],0,4,6]), {1: [[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]], 2: [[], [2, 3], 4, 6, 2, [[4, 0], [6, 2]]], 3: [[], [3, 4], 4, 6, 2, [[4, 0], [6, 2]]], 4: [[], [4, 5], 4, 6, 2, [[4, 0], [6, 2]]], 5: [[], [5, 6], 4, 6, 2, [[4, 0], [6, 2]]]}[N])
check('5', solve([[N],[N+1],2,1,5]), {1: [[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]], 2: [[2, 3], [], 1, 5, -1, [[1, 2], [5, 0]]], 3: [[3, 4], [], 1, 5, -1, [[1, 2], [5, 0]]], 4: [[4, 5], [], 1, 5, -1, [[1, 2], [5, 0]]], 5: [[5, 6], [], 1, 5, -1, [[1, 2], [5, 0]]]}[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	`[[1, 2], [3, 4], 8, 8, 1, [[8, 2], [8, 2]]]`	`[[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]]`	Failed
1	`[[1, 2, 3], [4], 9, 9, -2, [[9, 3], [9, 1]]]`	`[[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]]`	Failed
2	`[[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]]`	`[[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]]`	Passed
3	`[[1], [2], 7, 7, -1, [[7, 1], [7, 1]]]`	`[[1], [2], 2, 7, -1, [[2, 1], [7, 1]]]`	Failed
4	`[[], [1, 2], 6, 6, 2, [[6, 0], [6, 2]]]`	`[[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]]`	Failed
5	`[[1, 2], [], 5, 5, -1, [[5, 2], [5, 0]]]`	`[[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]]`	Failed

SHA-256 / ee2c47ed4067e7c6cdd920fb2f53c54989c2c252c721d3c6b29711fcf1558d36

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(x):
    a,b,target,aid,bid=x
    joined=a+b
    left=joined[:target]
    right=joined[target:]
    left_id=aid
    right_id=bid
    transfer=len(a)-target
    directory=[[left_id,len(left)],[right_id,len(right)]]
    return [left,right,left_id,right_id,transfer,directory]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,N+2],[N+3],2,3,8]), {1: [[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]], 2: [[2, 3], [4, 5], 3, 8, 1, [[3, 2], [8, 2]]], 3: [[3, 4], [5, 6], 3, 8, 1, [[3, 2], [8, 2]]], 4: [[4, 5], [6, 7], 3, 8, 1, [[3, 2], [8, 2]]], 5: [[5, 6], [7, 8], 3, 8, 1, [[3, 2], [8, 2]]]}[N])
check('1', solve([[N],[N+1,N+2,N+3],3,4,9]), {1: [[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]], 2: [[2, 3, 4], [5], 4, 9, -2, [[4, 3], [9, 1]]], 3: [[3, 4, 5], [6], 4, 9, -2, [[4, 3], [9, 1]]], 4: [[4, 5, 6], [7], 4, 9, -2, [[4, 3], [9, 1]]], 5: [[5, 6, 7], [8], 4, 9, -2, [[4, 3], [9, 1]]]}[N])
check('2', solve([[N,N+1],[N+2,N+3],2,5,10]), {1: [[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]], 2: [[2, 3], [4, 5], 5, 10, 0, [[5, 2], [10, 2]]], 3: [[3, 4], [5, 6], 5, 10, 0, [[5, 2], [10, 2]]], 4: [[4, 5], [6, 7], 5, 10, 0, [[5, 2], [10, 2]]], 5: [[5, 6], [7, 8], 5, 10, 0, [[5, 2], [10, 2]]]}[N])
check('3', solve([[],[N,N+1],1,2,7]), {1: [[1], [2], 2, 7, -1, [[2, 1], [7, 1]]], 2: [[2], [3], 2, 7, -1, [[2, 1], [7, 1]]], 3: [[3], [4], 2, 7, -1, [[2, 1], [7, 1]]], 4: [[4], [5], 2, 7, -1, [[2, 1], [7, 1]]], 5: [[5], [6], 2, 7, -1, [[2, 1], [7, 1]]]}[N])
check('4', solve([[N,N+1],[],0,4,6]), {1: [[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]], 2: [[], [2, 3], 4, 6, 2, [[4, 0], [6, 2]]], 3: [[], [3, 4], 4, 6, 2, [[4, 0], [6, 2]]], 4: [[], [4, 5], 4, 6, 2, [[4, 0], [6, 2]]], 5: [[], [5, 6], 4, 6, 2, [[4, 0], [6, 2]]]}[N])
check('5', solve([[N],[N+1],2,1,5]), {1: [[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]], 2: [[2, 3], [], 1, 5, -1, [[1, 2], [5, 0]]], 3: [[3, 4], [], 1, 5, -1, [[1, 2], [5, 0]]], 4: [[4, 5], [], 1, 5, -1, [[1, 2], [5, 0]]], 5: [[5, 6], [], 1, 5, -1, [[1, 2], [5, 0]]]}[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	`[[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]]`	`[[1, 2], [3, 4], 3, 8, 1, [[3, 2], [8, 2]]]`	Passed
1	`[[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]]`	`[[1, 2, 3], [4], 4, 9, -2, [[4, 3], [9, 1]]]`	Passed
2	`[[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]]`	`[[1, 2], [3, 4], 5, 10, 0, [[5, 2], [10, 2]]]`	Passed
3	`[[1], [2], 2, 7, -1, [[2, 1], [7, 1]]]`	`[[1], [2], 2, 7, -1, [[2, 1], [7, 1]]]`	Passed
4	`[[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]]`	`[[], [1, 2], 4, 6, 2, [[4, 0], [6, 2]]]`	Passed
5	`[[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]]`	`[[1, 2], [], 1, 5, -1, [[1, 2], [5, 0]]]`	Passed

SHA-256 / 11d0b7614a186d9f7d2caf833d429e69c852dffcab5bdba2b6c8814051bd71fb

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

Case digest / 2eea07fe038f815c799aacd11139eeaf607dc3233b6be68f828a0078fa24fcb9