FAILURE MAP
← Case archive

FA-46646 / Bounded deques / Open access

Stale deque iterator advances before reporting invalidation · case 01

Stale deque iterator advances before reporting invalidation.

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

ROOT CAUSE

Stale deque iterator advances before reporting invalidation.

VERIFIED REPAIR

Restore the documented stale position invariant in iterator-batch.

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

Case contract

A fail-fast deque iterator tracks consumed logical count, captured structural epoch and traversal direction. Read at most limit elements; stale iterators emit no items and preserve position.

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,pos,limit,saved,current,reverse=x
    if saved!=current:return ['stale',pos+1,[],saved]
    remaining=max(0,len(a)-pos)
    count=min(limit,remaining)
    sequence=a[::-1] if reverse else a
    values=sequence[pos:pos+count]
    next_pos=pos+count
    return ['ok',next_pos,values,saved]
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],1,2,3,3,False]), {1: ['ok', 3, [2, 3], 3], 2: ['ok', 3, [3, 4], 3], 3: ['ok', 3, [4, 5], 3], 4: ['ok', 3, [5, 6], 3], 5: ['ok', 3, [6, 7], 3]}[N])
check('1', solve([[N,N+1,N+2],0,2,2,2,True]), {1: ['ok', 2, [3, 2], 2], 2: ['ok', 2, [4, 3], 2], 3: ['ok', 2, [5, 4], 2], 4: ['ok', 2, [6, 5], 2], 5: ['ok', 2, [7, 6], 2]}[N])
check('2', solve([[N,N+1],1,5,4,4,False]), {1: ['ok', 2, [2], 4], 2: ['ok', 2, [3], 4], 3: ['ok', 2, [4], 4], 4: ['ok', 2, [5], 4], 5: ['ok', 2, [6], 4]}[N])
check('3', solve([[N],0,3,1,2,False]), {1: ['stale', 0, [], 1], 2: ['stale', 0, [], 1], 3: ['stale', 0, [], 1], 4: ['stale', 0, [], 1], 5: ['stale', 0, [], 1]}[N])
check('4', solve([[],0,2,0,0,True]), {1: ['ok', 0, [], 0], 2: ['ok', 0, [], 0], 3: ['ok', 0, [], 0], 4: ['ok', 0, [], 0], 5: ['ok', 0, [], 0]}[N])
check('5', solve([[N,N+1],1,0,5,5,True]), {1: ['ok', 1, [], 5], 2: ['ok', 1, [], 5], 3: ['ok', 1, [], 5], 4: ['ok', 1, [], 5], 5: ['ok', 1, [], 5]}[N])
check('6', solve([[N,N+1],0,1,3,2,False]), {1: ['stale', 0, [], 3], 2: ['stale', 0, [], 3], 3: ['stale', 0, [], 3], 4: ['stale', 0, [], 3], 5: ['stale', 0, [], 3]}[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
0['ok', 3, [2, 3], 3]['ok', 3, [2, 3], 3]Passed
1['ok', 2, [3, 2], 2]['ok', 2, [3, 2], 2]Passed
2['ok', 2, [2], 4]['ok', 2, [2], 4]Passed
3['stale', 1, [], 1]['stale', 0, [], 1]Failed
4['ok', 0, [], 0]['ok', 0, [], 0]Passed
5['ok', 1, [], 5]['ok', 1, [], 5]Passed
6['stale', 1, [], 3]['stale', 0, [], 3]Failed

SHA-256 / 2e9f765dc21e83a4cf99a639b67afc8a18ebf7b1a9a957af3cb551bb1935515d

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(x):
    a,pos,limit,saved,current,reverse=x
    if saved!=current:return ['stale',pos+(1 if a else 0),[],saved]
    remaining=max(0,len(a)-pos)
    count=min(limit,remaining)
    sequence=a[::-1] if reverse else a
    values=sequence[pos:pos+count]
    next_pos=pos+count
    return ['ok',next_pos,values,saved]
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],1,2,3,3,False]), {1: ['ok', 3, [2, 3], 3], 2: ['ok', 3, [3, 4], 3], 3: ['ok', 3, [4, 5], 3], 4: ['ok', 3, [5, 6], 3], 5: ['ok', 3, [6, 7], 3]}[N])
check('1', solve([[N,N+1,N+2],0,2,2,2,True]), {1: ['ok', 2, [3, 2], 2], 2: ['ok', 2, [4, 3], 2], 3: ['ok', 2, [5, 4], 2], 4: ['ok', 2, [6, 5], 2], 5: ['ok', 2, [7, 6], 2]}[N])
check('2', solve([[N,N+1],1,5,4,4,False]), {1: ['ok', 2, [2], 4], 2: ['ok', 2, [3], 4], 3: ['ok', 2, [4], 4], 4: ['ok', 2, [5], 4], 5: ['ok', 2, [6], 4]}[N])
check('3', solve([[N],0,3,1,2,False]), {1: ['stale', 0, [], 1], 2: ['stale', 0, [], 1], 3: ['stale', 0, [], 1], 4: ['stale', 0, [], 1], 5: ['stale', 0, [], 1]}[N])
check('4', solve([[],0,2,0,0,True]), {1: ['ok', 0, [], 0], 2: ['ok', 0, [], 0], 3: ['ok', 0, [], 0], 4: ['ok', 0, [], 0], 5: ['ok', 0, [], 0]}[N])
check('5', solve([[N,N+1],1,0,5,5,True]), {1: ['ok', 1, [], 5], 2: ['ok', 1, [], 5], 3: ['ok', 1, [], 5], 4: ['ok', 1, [], 5], 5: ['ok', 1, [], 5]}[N])
check('6', solve([[N,N+1],0,1,3,2,False]), {1: ['stale', 0, [], 3], 2: ['stale', 0, [], 3], 3: ['stale', 0, [], 3], 4: ['stale', 0, [], 3], 5: ['stale', 0, [], 3]}[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
0['ok', 3, [2, 3], 3]['ok', 3, [2, 3], 3]Passed
1['ok', 2, [3, 2], 2]['ok', 2, [3, 2], 2]Passed
2['ok', 2, [2], 4]['ok', 2, [2], 4]Passed
3['stale', 1, [], 1]['stale', 0, [], 1]Failed
4['ok', 0, [], 0]['ok', 0, [], 0]Passed
5['ok', 1, [], 5]['ok', 1, [], 5]Passed
6['stale', 1, [], 3]['stale', 0, [], 3]Failed

SHA-256 / 2edff933ffd95cba17cc349f96694ba77f2f7c7d6bdeced76cd64b48b4ed088a

3 / The verified repair

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

N = 1
observations = []
def solve(x):
    a,pos,limit,saved,current,reverse=x
    if saved!=current:return ['stale',pos,[],saved]
    remaining=max(0,len(a)-pos)
    count=min(limit,remaining)
    sequence=a[::-1] if reverse else a
    values=sequence[pos:pos+count]
    next_pos=pos+count
    return ['ok',next_pos,values,saved]
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],1,2,3,3,False]), {1: ['ok', 3, [2, 3], 3], 2: ['ok', 3, [3, 4], 3], 3: ['ok', 3, [4, 5], 3], 4: ['ok', 3, [5, 6], 3], 5: ['ok', 3, [6, 7], 3]}[N])
check('1', solve([[N,N+1,N+2],0,2,2,2,True]), {1: ['ok', 2, [3, 2], 2], 2: ['ok', 2, [4, 3], 2], 3: ['ok', 2, [5, 4], 2], 4: ['ok', 2, [6, 5], 2], 5: ['ok', 2, [7, 6], 2]}[N])
check('2', solve([[N,N+1],1,5,4,4,False]), {1: ['ok', 2, [2], 4], 2: ['ok', 2, [3], 4], 3: ['ok', 2, [4], 4], 4: ['ok', 2, [5], 4], 5: ['ok', 2, [6], 4]}[N])
check('3', solve([[N],0,3,1,2,False]), {1: ['stale', 0, [], 1], 2: ['stale', 0, [], 1], 3: ['stale', 0, [], 1], 4: ['stale', 0, [], 1], 5: ['stale', 0, [], 1]}[N])
check('4', solve([[],0,2,0,0,True]), {1: ['ok', 0, [], 0], 2: ['ok', 0, [], 0], 3: ['ok', 0, [], 0], 4: ['ok', 0, [], 0], 5: ['ok', 0, [], 0]}[N])
check('5', solve([[N,N+1],1,0,5,5,True]), {1: ['ok', 1, [], 5], 2: ['ok', 1, [], 5], 3: ['ok', 1, [], 5], 4: ['ok', 1, [], 5], 5: ['ok', 1, [], 5]}[N])
check('6', solve([[N,N+1],0,1,3,2,False]), {1: ['stale', 0, [], 3], 2: ['stale', 0, [], 3], 3: ['stale', 0, [], 3], 4: ['stale', 0, [], 3], 5: ['stale', 0, [], 3]}[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
0['ok', 3, [2, 3], 3]['ok', 3, [2, 3], 3]Passed
1['ok', 2, [3, 2], 2]['ok', 2, [3, 2], 2]Passed
2['ok', 2, [2], 4]['ok', 2, [2], 4]Passed
3['stale', 0, [], 1]['stale', 0, [], 1]Passed
4['ok', 0, [], 0]['ok', 0, [], 0]Passed
5['ok', 1, [], 5]['ok', 1, [], 5]Passed
6['stale', 0, [], 3]['stale', 0, [], 3]Passed

SHA-256 / 8df25ac41577cafa3cbc155288b37068a18d0629d53c7c9caf1961c097a09b0c

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

Case digest / 3ad3b9e5eec400e45e4da7d8191e66df9bd957a17b592731210f19689f52cbb3