Fix backfilled events being rejected for no `state_groups` (#10439)

Reproducible on a federated homeserver when there is a membership auth event as a floating outlier. Then when we try to backfill one of that persons messages, it has missing membership auth to fetch which caused us to mistakenly replace the `context` for the message with that of the floating membership `outlier` event. Since `outliers` have no `state` or `state_group`, the error bubbles up when we continue down the persisting route: `sqlite3.IntegrityError: NOT NULL constraint failed: event_to_state_groups.state_group`

Call stack:

```
backfill
_auth_and_persist_event
_check_event_auth
_update_auth_events_and_context_for_auth
```

2 files changed, 132 insertions, 0 deletions

diff --git a/changelog.d/10439.bugfix b/changelog.d/10439.bugfix
new file mode 100644
index 0000000000..74e5a25126
--- /dev/null
+++ b/changelog.d/10439.bugfix
@@ -0,0 +1 @@
+Fix events with floating outlier state being rejected over federation.
diff --git a/tests/handlers/test_federation.py b/tests/handlers/test_federation.py
index ba8cf44f46..4140fcefc2 100644
--- a/tests/handlers/test_federation.py
+++ b/tests/handlers/test_federation.py
@@ -12,6 +12,7 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 import logging
+from typing import List
 from unittest import TestCase
 
 from synapse.api.constants import EventTypes
@@ -22,6 +23,7 @@ from synapse.federation.federation_base import event_from_pdu_json
 from synapse.logging.context import LoggingContext, run_in_background
 from synapse.rest import admin
 from synapse.rest.client.v1 import login, room
+from synapse.util.stringutils import random_string
 
 from tests import unittest
 
@@ -39,6 +41,8 @@ class FederationTestCase(unittest.HomeserverTestCase):
         hs = self.setup_test_homeserver(federation_http_client=None)
         self.handler = hs.get_federation_handler()
         self.store = hs.get_datastore()
+        self.state_store = hs.get_storage().state
+        self._event_auth_handler = hs.get_event_auth_handler()
         return hs
 
     def test_exchange_revoked_invite(self):
@@ -190,6 +194,133 @@ class FederationTestCase(unittest.HomeserverTestCase):
 
         self.assertEqual(sg, sg2)
 
+    def test_backfill_floating_outlier_membership_auth(self):
+        """
+        As the local homeserver, check that we can properly process a federated
+        event from the OTHER_SERVER with auth_events that include a floating
+        membership event from the OTHER_SERVER.
+
+        Regression test, see #10439.
+        """
+        OTHER_SERVER = "otherserver"
+        OTHER_USER = "@otheruser:" + OTHER_SERVER
+
+        # create the room
+        user_id = self.register_user("kermit", "test")
+        tok = self.login("kermit", "test")
+        room_id = self.helper.create_room_as(
+            room_creator=user_id,
+            is_public=True,
+            tok=tok,
+            extra_content={
+                "preset": "public_chat",
+            },
+        )
+        room_version = self.get_success(self.store.get_room_version(room_id))
+
+        prev_event_ids = self.get_success(self.store.get_prev_events_for_room(room_id))
+        (
+            most_recent_prev_event_id,
+            most_recent_prev_event_depth,
+        ) = self.get_success(self.store.get_max_depth_of(prev_event_ids))
+        # mapping from (type, state_key) -> state_event_id
+        prev_state_map = self.get_success(
+            self.state_store.get_state_ids_for_event(most_recent_prev_event_id)
+        )
+        # List of state event ID's
+        prev_state_ids = list(prev_state_map.values())
+        auth_event_ids = prev_state_ids
+        auth_events = list(
+            self.get_success(self.store.get_events(auth_event_ids)).values()
+        )
+
+        # build a floating outlier member state event
+        fake_prev_event_id = "$" + random_string(43)
+        member_event_dict = {
+            "type": EventTypes.Member,
+            "content": {
+                "membership": "join",
+            },
+            "state_key": OTHER_USER,
+            "room_id": room_id,
+            "sender": OTHER_USER,
+            "depth": most_recent_prev_event_depth,
+            "prev_events": [fake_prev_event_id],
+            "origin_server_ts": self.clock.time_msec(),
+            "signatures": {OTHER_SERVER: {"ed25519:key_version": "SomeSignatureHere"}},
+        }
+        builder = self.hs.get_event_builder_factory().for_room_version(
+            room_version, member_event_dict
+        )
+        member_event = self.get_success(
+            builder.build(
+                prev_event_ids=member_event_dict["prev_events"],
+                auth_event_ids=self._event_auth_handler.compute_auth_events(
+                    builder,
+                    prev_state_map,
+                    for_verification=False,
+                ),
+                depth=member_event_dict["depth"],
+            )
+        )
+        # Override the signature added from "test" homeserver that we created the event with
+        member_event.signatures = member_event_dict["signatures"]
+
+        # Add the new member_event to the StateMap
+        prev_state_map[
+            (member_event.type, member_event.state_key)
+        ] = member_event.event_id
+        auth_events.append(member_event)
+
+        # build and send an event authed based on the member event
+        message_event_dict = {
+            "type": EventTypes.Message,
+            "content": {},
+            "room_id": room_id,
+            "sender": OTHER_USER,
+            "depth": most_recent_prev_event_depth,
+            "prev_events": prev_event_ids.copy(),
+            "origin_server_ts": self.clock.time_msec(),
+            "signatures": {OTHER_SERVER: {"ed25519:key_version": "SomeSignatureHere"}},
+        }
+        builder = self.hs.get_event_builder_factory().for_room_version(
+            room_version, message_event_dict
+        )
+        message_event = self.get_success(
+            builder.build(
+                prev_event_ids=message_event_dict["prev_events"],
+                auth_event_ids=self._event_auth_handler.compute_auth_events(
+                    builder,
+                    prev_state_map,
+                    for_verification=False,
+                ),
+                depth=message_event_dict["depth"],
+            )
+        )
+        # Override the signature added from "test" homeserver that we created the event with
+        message_event.signatures = message_event_dict["signatures"]
+
+        # Stub the /event_auth response from the OTHER_SERVER
+        async def get_event_auth(
+            destination: str, room_id: str, event_id: str
+        ) -> List[EventBase]:
+            return auth_events
+
+        self.handler.federation_client.get_event_auth = get_event_auth
+
+        with LoggingContext("receive_pdu"):
+            # Fake the OTHER_SERVER federating the message event over to our local homeserver
+            d = run_in_background(
+                self.handler.on_receive_pdu, OTHER_SERVER, message_event
+            )
+        self.get_success(d)
+
+        # Now try and get the events on our local homeserver
+        stored_event = self.get_success(
+            self.store.get_event(message_event.event_id, allow_none=True)
+        )
+        self.assertTrue(stored_event is not None)
+
     @unittest.override_config(
         {"rc_invites": {"per_user": {"per_second": 0.5, "burst_count": 3}}}
     )