FAILURE MAP
← Case archive

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

Plan history backfill requests for missing sequences: head inclusive · case 01

The newest message is never requested when it is the one that is missing.

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

ROOT CAUSE

The head inclusive decision evaluates `range(lo, hi)` where the contract requires `range(lo, hi + 1)`.

VERIFIED REPAIR

Use `range(lo, hi + 1)` for the head inclusive decision and keep every other rule of the model unchanged.

Unsuccessful approach: Shifting the scan window down still stops before the head sequence and starts before the horizon. The attempted `range(lo - 1, hi)` 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):
        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, 10], [3, 5]]}{'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, 4], [2, 2]]}{'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}Failed
several gaps limited{'complete': False, 'fetch': [[8, 11], [5, 6]]}{'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': [[3, 7]]}{'complete': False, 'fetch': [[9, 9], [3, 7]]}Failed

SHA-256 / 8823eeda350bdac011b23b50f847503033d6048ea66f7883e68c5cd785c07604

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 - 1, hi):
        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, 10], [2, 5]]}{'complete': False, 'fetch': [[8, 9], [3, 5]]}Failed
head not yet received{'complete': False, 'fetch': [[4, 5], [0, 0]]}{'complete': False, 'fetch': [[4, 5]]}Failed
single missing seqs{'complete': False, 'fetch': [[6, 7], [4, 4], [2, 2], [0, 0]]}{'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}Failed
several gaps limited{'complete': False, 'fetch': [[8, 11], [5, 6]]}{'complete': False, 'fetch': [[8, 10], [5, 6]]}Failed
nothing missing{'complete': False, 'fetch': []}{'complete': True, 'fetch': []}Failed
limit zero with gaps{'complete': False, 'fetch': []}{'complete': False, 'fetch': []}Passed
uneven gaps newest first{'complete': False, 'fetch': [[3, 7], [0, 0]]}{'complete': False, 'fetch': [[9, 9], [3, 7]]}Failed

SHA-256 / fd6c1b758482e8cebe049969a252b462f2058267c80523e6541166abb190204b

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

Case digest / 1ad1bc716553875791efd10ad251922464639904981b9095ffc0c769de588e27