FAILURE MAP
← Case archive

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

Plan history backfill requests for missing sequences: newest first · case 01

Old gaps are backfilled before the recent history the user is looking at.

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

ROOT CAUSE

The newest first decision evaluates `ranges.sort()` where the contract requires `ranges.reverse()`.

THE FAILURE

The newest first decision evaluates `ranges.sort()` where the contract requires `ranges.reverse()`.

Unsuccessful approach: Ordering by gap size still fetches an older large gap before a recent one. The attempted `ranges.sort(key=lambda r: r[1] - r[0], reverse=True)` 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])
    ranges.sort()
    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': [[3, 5], [8, 9]]}{'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': [[2, 2], [4, 4], [6, 6]]}{'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}Failed
several gaps limited{'complete': False, 'fetch': [[2, 3], [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], [9, 9]]}{'complete': False, 'fetch': [[9, 9], [3, 7]]}Failed

SHA-256 / 55a909fec247a040dd336994a03a8856500b8c53866a53cf73a406cb36c281eb

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, hi])
    ranges.sort(key=lambda r: r[1] - r[0], reverse=True)
    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': [[3, 5], [8, 9]]}{'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': [[2, 2], [4, 4], [6, 6]]}{'complete': False, 'fetch': [[6, 6], [4, 4], [2, 2]]}Failed
several gaps limited{'complete': False, 'fetch': [[8, 10], [2, 3]]}{'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], [9, 9]]}{'complete': False, 'fetch': [[9, 9], [3, 7]]}Failed

SHA-256 / 5a3cffc013448ae19cf837e188b8ba8bdccd6f0de06c69d2be0c5379cfe3105f

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 7 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

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

Case digest / 3af4a11fafc1dfcf19c9e268c335d0a1eab5674716781259a3d2bdae76040183