FAILURE MAP
← Case archive

FA-76041 / Chat ordering and read receipts / Open access

Plan history backfill requests for missing sequences: range close · case 01

Backfill ranges include the first message that was already received.

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

ROOT CAUSE

The range close decision evaluates `ranges.append([start, s])` where the contract requires `ranges.append([start, s - 1])`.

VERIFIED REPAIR

Use `ranges.append([start, s - 1])` for the range close decision and keep every other rule of the model unchanged.

Unsuccessful approach: Special-casing longer gaps still overfetches single missing messages. The attempted `ranges.append([start, s - 1 if s > start + 1 else s])` still disagrees with a fixture.

Case contract

have lists received seqs (unsorted, duplicates possible); horizon is the oldest seq the server still retains; head is the newest known seq. Every seq in [horizon, head] not received is missing; missing seqs are merged into inclusive [start, end] ranges, returned newest first and limited to max_ranges. complete is true only when nothing is missing.

Why this case matters

Chat clients repair gaps after reconnecting; wrong ranges refetch too much or leave holes in the timeline.

1 / The failure

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

N = 1
observations = []
def solve(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    check(_label, solve(*_args), _expected)
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
gap before first received{'complete': False, 'fetch': [[8, 10], [3, 6]]}{'complete': False, 'fetch': [[8, 9], [3, 5]]}Failed
head not yet received{'complete': False, 'fetch': [[4, 5]]}{'complete': False, 'fetch': [[4, 5]]}Passed
single missing seqs{'complete': False, 'fetch': [[6, 7], [4, 5], [2, 3]]}{'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}Failed
several gaps limited{'complete': False, 'fetch': [[8, 11], [5, 7]]}{'complete': False, 'fetch': [[8, 10], [5, 6]]}Failed
nothing missing{'complete': True, 'fetch': []}{'complete': True, 'fetch': []}Passed
limit zero with gaps{'complete': False, 'fetch': []}{'complete': False, 'fetch': []}Passed
uneven gaps newest first{'complete': False, 'fetch': [[9, 9], [3, 8]]}{'complete': False, 'fetch': [[9, 9], [3, 7]]}Failed

SHA-256 / 9e67f72441a2b5d255f6af53030cf89dbf619608d967ac5a57f6e224094eca3a

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1 if s > start + 1 else s])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    check(_label, solve(*_args), _expected)
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
gap before first received{'complete': False, 'fetch': [[8, 9], [3, 5]]}{'complete': False, 'fetch': [[8, 9], [3, 5]]}Passed
head not yet received{'complete': False, 'fetch': [[4, 5]]}{'complete': False, 'fetch': [[4, 5]]}Passed
single missing seqs{'complete': False, 'fetch': [[6, 7], [4, 5], [2, 3]]}{'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}Failed
several gaps limited{'complete': False, 'fetch': [[8, 10], [5, 6]]}{'complete': False, 'fetch': [[8, 10], [5, 6]]}Passed
nothing missing{'complete': True, 'fetch': []}{'complete': True, 'fetch': []}Passed
limit zero with gaps{'complete': False, 'fetch': []}{'complete': False, 'fetch': []}Passed
uneven gaps newest first{'complete': False, 'fetch': [[9, 9], [3, 7]]}{'complete': False, 'fetch': [[9, 9], [3, 7]]}Passed

SHA-256 / 6eaeb75e465615799ceb7d9a71d2c765e14da04f0dbd9493f90b346b729db45b

3 / The verified repair

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

N = 1
observations = []
def solve(have, horizon, head, max_ranges):
    got = set(have)
    lo = horizon
    hi = head
    ranges = []
    start = None
    for s in range(lo, hi + 1):
        if s not in got:
            if start is None:
                start = s
        elif start is not None:
            ranges.append([start, s - 1])
            start = None
    if start is not None:
        ranges.append([start, hi])
    ranges.reverse()
    return {'fetch': ranges[:max_ranges], 'complete': not ranges}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
_CASES = {1: [('gap before first received', ([6, 7, 10], 3, 10, 5), {'complete': False, 'fetch': [[8, 9], [3, 5]]}), ('head not yet received', ([1, 2, 3], 1, 5, 3), {'complete': False, 'fetch': [[4, 5]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 11], 1, 11, 2), {'complete': False, 'fetch': [[8, 10], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 4, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 9, 5), {'complete': False, 'fetch': [[9, 9], [3, 7]]})], 2: [('gap before first received', ([7, 8, 11], 4, 11, 5), {'complete': False, 'fetch': [[9, 10], [4, 6]]}), ('head not yet received', ([1, 2, 3], 1, 6, 3), {'complete': False, 'fetch': [[4, 6]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 12], 1, 12, 2), {'complete': False, 'fetch': [[8, 11], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 5, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 10, 5), {'complete': False, 'fetch': [[9, 10], [3, 7]]})], 3: [('gap before first received', ([8, 9, 12], 5, 12, 5), {'complete': False, 'fetch': [[10, 11], [5, 7]]}), ('head not yet received', ([1, 2, 3], 1, 7, 3), {'complete': False, 'fetch': [[4, 7]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 13], 1, 13, 2), {'complete': False, 'fetch': [[8, 12], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 6, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 11, 5), {'complete': False, 'fetch': [[9, 11], [3, 7]]})], 4: [('gap before first received', ([9, 10, 13], 6, 13, 5), {'complete': False, 'fetch': [[11, 12], [6, 8]]}), ('head not yet received', ([1, 2, 3], 1, 8, 3), {'complete': False, 'fetch': [[4, 8]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 14], 1, 14, 2), {'complete': False, 'fetch': [[8, 13], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 7, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 12, 5), {'complete': False, 'fetch': [[9, 12], [3, 7]]})], 5: [('gap before first received', ([10, 11, 14], 7, 14, 5), {'complete': False, 'fetch': [[12, 13], [7, 9]]}), ('head not yet received', ([1, 2, 3], 1, 9, 3), {'complete': False, 'fetch': [[4, 9]]}), ('single missing seqs', ([1, 3, 5, 7], 1, 7, 10), {'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}), ('several gaps limited', ([1, 4, 7, 15], 1, 15, 2), {'complete': False, 'fetch': [[8, 14], [5, 6]]}), ('nothing missing', ([3, 4, 5, 5], 3, 5, 0), {'complete': True, 'fetch': []}), ('limit zero with gaps', ([1, 3], 1, 8, 0), {'complete': False, 'fetch': []}), ('uneven gaps newest first', ([1, 2, 8], 1, 13, 5), {'complete': False, 'fetch': [[9, 13], [3, 7]]})]}
for _label, _args, _expected in _CASES[N]:
    check(_label, solve(*_args), _expected)
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
gap before first received{'complete': False, 'fetch': [[8, 9], [3, 5]]}{'complete': False, 'fetch': [[8, 9], [3, 5]]}Passed
head not yet received{'complete': False, 'fetch': [[4, 5]]}{'complete': False, 'fetch': [[4, 5]]}Passed
single missing seqs{'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}{'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}Passed
several gaps limited{'complete': False, 'fetch': [[8, 10], [5, 6]]}{'complete': False, 'fetch': [[8, 10], [5, 6]]}Passed
nothing missing{'complete': True, 'fetch': []}{'complete': True, 'fetch': []}Passed
limit zero with gaps{'complete': False, 'fetch': []}{'complete': False, 'fetch': []}Passed
uneven gaps newest first{'complete': False, 'fetch': [[9, 9], [3, 7]]}{'complete': False, 'fetch': [[9, 9], [3, 7]]}Passed

SHA-256 / a624374b2c66ba3fc7efc0b86c51a62e48841f499ba502b93d7b0fd06f55a8dd

Verification & scope

Stipulated offline chat model; not a complete messaging protocol, client or server implementation. 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:49:12.643703+00:00.

Case digest / 7983e0e46cba1d5c5a6f2b98a90e85689218d0f7c29beaecbed9618b80d5ad68