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

Plan history backfill requests for missing sequences: trailing gap · case 01

A gap that runs up to the head is requested short, so the newest missing messages stay missing.

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

ROOT CAUSE

The trailing gap decision evaluates `ranges.append([start, hi - 1])` where the contract requires `ranges.append([start, hi])`.

VERIFIED REPAIR

Use `ranges.append([start, hi])` for the trailing gap decision and keep every other rule of the model unchanged.

Unsuccessful approach: Closing a trailing gap at its first sequence only fetches one message of the gap. The attempted `ranges.append([start, start])` 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 - 1])
            start = None
    if start is not None:
        ranges.append([start, hi - 1])
    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 fixture	Actual	Expected	Outcome
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, 4]]}`	`{'complete': False, 'fetch': [[4, 5]]}`	Failed
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, 8], [3, 7]]}`	`{'complete': False, 'fetch': [[9, 9], [3, 7]]}`	Failed

SHA-256 / 3e79f46d125d27c94f686a0e5c96bd79172c55999a1e2821af4cceee9f342f6c

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])
            start = None
    if start is not None:
        ranges.append([start, start])
    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 fixture	Actual	Expected	Outcome
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, 4]]}`	`{'complete': False, 'fetch': [[4, 5]]}`	Failed
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 / cce7f4933d0c3371f0b1edb33f907e7cd0227632dd2858741956b465a8c7d4e4

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 fixture	Actual	Expected	Outcome
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.688999+00:00.

Case digest / 9cc2afe6f504b44624bcc4806841446514eb3095227186f8ab5afed514d8f42d