`TestMessagesOverFederation` detects critical regressions, but it does NOT do so RELIABLY

[gamesguru]

Based on the AI provided problem statement summarized below, it's a timing issue.

Ideally, Complement can reliably guard against such regressions (or explicitly codify them as accepted/allowed), to either avoid lulling the homeserver developer into a false sense of security or, conversely, to avoid sounding false alarms.

The types of timeline backfill and state resolution bugs under question are among the most severe imaginable -- allowing nearly fatal regressions to survive, with a 75% chance of passing on a standard AMD Ubuntu 22/24 runner, is venturesome to say the least.

Based on my run results, seems to affect ARM runners more and there may be some influence of v11 vs. v12 rooms, but I can't say definitively. For now, I'm just concerned to address the inconsistency across runs and see if anyone else is currently working on a way to make this test case more consistent across a wider range of environments and setup conditions.

Tested from my Complement fork, with a merge-base of 0e6f8552ff0c99fddb97222399efed3e1f0cb91a and a delta of:

$ gds 0e6f855 1a710af
 README.md                                        |  5 +++--
 tests/csapi/apidoc_room_members_test.go          | 18 ++++++++++++++----
 tests/csapi/apidoc_room_receipts_test.go         | 32 +++++++++++++++++++++++++++++++-
 tests/csapi/power_levels_test.go                 | 82 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----------------
 tests/csapi/rooms_state_test.go                  | 10 ++++------
 tests/csapi/sync_archive_test.go                 |  2 +-
 tests/federation_event_auth_test.go              | 14 ++++++++++++++
 tests/federation_room_get_missing_events_test.go |  6 +-----
 8 files changed, 133 insertions(+), 36 deletions(-)

---

TestMessagesOverFederation: Definitive Root Cause Analysis

Test Behavior

TestMessagesOverFederation/Visible_shared_history_after_re-joining_room_(backfill) tests:

1. User joins room, sees messages
2. User leaves room
3. Messages are sent while user is gone
4. User re-joins room
5. User paginates backward → expects to see messages from step 3 via federation backfill

The test fails when backfill doesn't happen after re-join.

---

Three Distinct Failure Eras

Era 1: Pre-backfill-loop (before a8f08f3cc) — The joined_count Race

Commit	Date	Status	Notes
5fb9a8ffc	Jun 24	✅ 10/10 stable	626 pass consistently
b790659aa	Jun 25	✅ 10/10 stable	626 pass consistently
6736a7163	Jun 25	✅ 10/10 stable	626-627 pass
ca76b73a5	Jun 25	⚠️ 2/10 fail	v11-amd64 only, 624 pass

Root cause: The test is inherently flaky due to a timing window in the joined_count <= 1 check at backfill.rs:51-65. After re-joining via federation:

1. force_state processes the join and calls update_joined_count
2. But between the /send_join response being processed and the user's /messages pagination, room_joined_count() may return 1 (only the local user) because the remote users' membership hasn't been fully replicated yet

At ca76b73a5, commit 8c320e882 removed clean_extremities() which subtly changed join timing. The backfill code itself didn't change — but the extremity handling changes altered the race window.

Important

The joined_count <= 1 guard has been in the code the entire time — since before 5fb9a8ffc. The stable commits just happened to win the race consistently. The 2/10 failure rate at ca76b73a5 confirms this is a race.

---

Era 2: b4e689df5 → 100% Failure — Duplicated Gap Scan

Commit	Date	Status	Notes
b4e689df5	Jul 2	❌ 10/10 fail	All archs, all versions
173390abf	Jul 2	⚠️ 6/10 fail	Mixed
a2b22c7e3	Jul 3	⚠️ 2/10 fail	Mostly recovered
5ccc37cba	Jul 3	✅ 10/10 stable	627 pass consistently

Root cause: Commit a8f08f3cc ("fix: resolve state across DAG forks + iterative backfill loop") added the iterative backfill loop but left the original gap scan in place before the loop. This created a duplicated backward-gap scan:

1. First scan (lines 65-96) — finds gaps, populates backwards_extremities  ← REDUNDANT
2. Power levels / server selection logic
3. Loop starts:
   a. Second scan (inside loop) — finds gaps again
   b. Sends /backfill request
   c. Re-scans for new gaps

The problem: the first scan (pre-loop) would find gaps and proceed to the server selection. But it would send /backfill using the pre-loop extremities, while the loop's scan would find different or no extremities (because the pre-loop scan already populated backwards_extremities as a separate variable). This confused the backfill logic, especially when combined with the joined_count <= 1 race.

Commit 5ccc37cba fixed this by deleting the duplicated pre-loop scan (31 lines removed), leaving only the loop-internal scan. This immediately stabilized the test to 100% pass.

---

Era 3: 6734d868c → Rezzy find_backward_extremities + joined_count Race Returns

Commit	Date	Status	Notes
ae7aae516	Jul 3	✅ 10/10 stable	628 pass
0e1a1a6e9	Jul 3	✅ 10/10 stable	628 pass
6787ceb14	Jul 3	✅ 10/10 stable	628 pass
6734d868c	Jul 3	⚠️ 4/10 fail	v11-amd64 + some v12
e4226972d	Jul 4	⚠️ ~4/10 fail	Same pattern

Root cause: Two combined factors:

1. The joined_count <= 1 race — same as Era 1. This was masked by the 628-pass era (ae7aae516 through 6787ceb14) because the timing window was narrower.

2. The rezzy find_backward_extremities refactor (commits 42ce9673f + 060a98764) changed the gap detection from inline prev_event scanning to rezzy::find_backward_extremities(). This doesn't directly cause the failure, but it changes the timing of the backfill evaluation — building the full event_map HashMap takes longer than the streaming per-event scan, widening the window during which joined_count returns stale data.

---

The Constant: joined_count <= 1 Is Always the Gate

Every single failure across all three eras produces the same server log:

backfill: SKIPPING room !xxx -- joined_count=1 <= 1

The backfill code changes in Eras 2 and 3 don't introduce the failure — they change the timing characteristics that determine how often the race is hit.

Fix

The guard at backfill.rs:51-65 should use has_remote_servers (already computed at line 39-44) instead of joined_count:

- if self
-     .services
-     .state_cache
-     .room_joined_count(room_id)
-     .await
-     .is_ok_and(|count| count <= 1)
-     && !self
-         .services
-         .state_accessor
-         .is_world_readable(room_id)
-         .await
- {
-     info!("backfill: SKIPPING room {room_id} -- joined_count={joined_count} <= 1");
-     return Ok(());
- }
+ if !has_remote_servers
+     && !self
+         .services
+         .state_accessor
+         .is_world_readable(room_id)
+         .await
+ {
+     info!("backfill: SKIPPING room {room_id} -- no remote servers in room");
+     return Ok(());
+ }

Why has_remote_servers is correct: After a re-join via federation, the originating server is immediately visible in room_servers() (it's set during /send_join processing), even if joined_count hasn't been updated yet. This eliminates the race condition entirely.

The same fix should apply to the duplicate guard in get_remote_pdu at line 284-298.

---

Summary Table

Era	Commits	Failure Rate	Root Cause	Fix
1	ca76b73a5	20% (v11-amd64 only)	joined_count race + extremity timing change	has_remote_servers guard
2	b4e689df5	100%	Duplicated gap scan + joined_count race	✅ Fixed by 5ccc37cba
3	6734d868c+	40% (mixed)	joined_count race + rezzy HashMap timing	has_remote_servers guard

[kegsay]

This is unhelpful:

• It's a wall of text
• ..referencing rust code which isn't in this repo
• ..with superlatives which mask severity / what the actual problem is.

I can believe that the test is flakey if we don't wait for a certain events to come down over federation. I would appreciate it if you spent some time actually writing a helpful bug report.