Add Sliding Sync `/sync` endpoint (initial implementation) (#17187)

Based on [MSC3575](https://github.com/matrix-org/matrix-spec-proposals/pull/3575): Sliding Sync

This iteration only focuses on returning the list of room IDs in the sliding window API (without sorting/filtering).

Rooms appear in the Sliding sync response based on:

 - `invite`, `join`, `knock`, `ban` membership events
 - Kicks (`leave` membership events where `sender` is different from the `user_id`/`state_key`)
 - `newly_left` (rooms that were left during the given token range, > `from_token` and <= `to_token`)
 - In order for bans/kicks to not show up, you need to `/forget` those rooms. This doesn't modify the event itself though and only adds the `forgotten` flag to `room_memberships` in Synapse. There isn't a way to tell when a room was forgotten at the moment so we can't factor it into the from/to range.

### Example request

`POST http://localhost:8008/_matrix/client/unstable/org.matrix.msc3575/sync`

```json
{
  "lists": {
    "foo-list": {
      "ranges": [ [0, 99] ],
      "sort": [ "by_notification_level", "by_recency", "by_name" ],
      "required_state": [
        ["m.room.join_rules", ""],
        ["m.room.history_visibility", ""],
        ["m.space.child", "*"]
      ],
      "timeline_limit": 100
    }
  }
}
```

Response:
```json
{
  "next_pos": "s58_224_0_13_10_1_1_16_0_1",
  "lists": {
    "foo-list": {
      "count": 1,
      "ops": [
        {
          "op": "SYNC",
          "range": [0, 99],
          "room_ids": [
            "!MmgikIyFzsuvtnbvVG:my.synapse.linux.server"
          ]
        }
      ]
    }
  },
  "rooms": {},
  "extensions": {}
}
```

3 files changed, 420 insertions, 4 deletions

diff --git a/synapse/rest/client/models.py b/synapse/rest/client/models.py
index fc1aed2889..5433ed91ef 100644
--- a/synapse/rest/client/models.py
+++ b/synapse/rest/client/models.py
@@ -18,14 +18,30 @@
 # [This file includes modifications made by New Vector Limited]
 #
 #
-from typing import TYPE_CHECKING, Dict, Optional
+from typing import TYPE_CHECKING, Dict, List, Optional, Tuple, Union
 
 from synapse._pydantic_compat import HAS_PYDANTIC_V2
 
 if TYPE_CHECKING or HAS_PYDANTIC_V2:
-    from pydantic.v1 import Extra, StrictInt, StrictStr, constr, validator
+    from pydantic.v1 import (
+        Extra,
+        StrictBool,
+        StrictInt,
+        StrictStr,
+        conint,
+        constr,
+        validator,
+    )
 else:
-    from pydantic import Extra, StrictInt, StrictStr, constr, validator
+    from pydantic import (
+        Extra,
+        StrictBool,
+        StrictInt,
+        StrictStr,
+        conint,
+        constr,
+        validator,
+    )
 
 from synapse.rest.models import RequestBodyModel
 from synapse.util.threepids import validate_email
@@ -97,3 +113,172 @@ else:
 class MsisdnRequestTokenBody(ThreepidRequestTokenBody):
     country: ISO3116_1_Alpha_2
     phone_number: StrictStr
+
+
+class SlidingSyncBody(RequestBodyModel):
+    """
+    Sliding Sync API request body.
+
+    Attributes:
+        lists: Sliding window API. A map of list key to list information
+            (:class:`SlidingSyncList`). Max lists: 100. The list keys should be
+            arbitrary strings which the client is using to refer to the list. Keep this
+            small as it needs to be sent a lot. Max length: 64 bytes.
+        room_subscriptions: Room subscription API. A map of room ID to room subscription
+            information. Used to subscribe to a specific room. Sometimes clients know
+            exactly which room they want to get information about e.g by following a
+            permalink or by refreshing a webapp currently viewing a specific room. The
+            sliding window API alone is insufficient for this use case because there's
+            no way to say "please track this room explicitly".
+        extensions: Extensions API. A map of extension key to extension config.
+    """
+
+    class CommonRoomParameters(RequestBodyModel):
+        """
+        Common parameters shared between the sliding window and room subscription APIs.
+
+        Attributes:
+            required_state: Required state for each room returned. An array of event
+                type and state key tuples. Elements in this array are ORd together to
+                produce the final set of state events to return. One unique exception is
+                when you request all state events via `["*", "*"]`. When used, all state
+                events are returned by default, and additional entries FILTER OUT the
+                returned set of state events. These additional entries cannot use `*`
+                themselves. For example, `["*", "*"], ["m.room.member",
+                "@alice:example.com"]` will *exclude* every `m.room.member` event
+                *except* for `@alice:example.com`, and include every other state event.
+                In addition, `["*", "*"], ["m.space.child", "*"]` is an error, the
+                `m.space.child` filter is not required as it would have been returned
+                anyway.
+            timeline_limit: The maximum number of timeline events to return per response.
+                (Max 1000 messages)
+            include_old_rooms: Determines if `predecessor` rooms are included in the
+                `rooms` response. The user MUST be joined to old rooms for them to show up
+                in the response.
+        """
+
+        class IncludeOldRooms(RequestBodyModel):
+            timeline_limit: StrictInt
+            required_state: List[Tuple[StrictStr, StrictStr]]
+
+        required_state: List[Tuple[StrictStr, StrictStr]]
+        # mypy workaround via https://github.com/pydantic/pydantic/issues/156#issuecomment-1130883884
+        if TYPE_CHECKING:
+            timeline_limit: int
+        else:
+            timeline_limit: conint(le=1000, strict=True)  # type: ignore[valid-type]
+        include_old_rooms: Optional[IncludeOldRooms] = None
+
+    class SlidingSyncList(CommonRoomParameters):
+        """
+        Attributes:
+            ranges: Sliding window ranges. If this field is missing, no sliding window
+                is used and all rooms are returned in this list. Integers are
+                *inclusive*.
+            sort: How the list should be sorted on the server. The first value is
+                applied first, then tiebreaks are performed with each subsequent sort
+                listed.
+
+                    FIXME: Furthermore, it's not currently defined how servers should behave
+                    if they encounter a filter or sort operation they do not recognise. If
+                    the server rejects the request with an HTTP 400 then that will break
+                    backwards compatibility with new clients vs old servers. However, the
+                    client would be otherwise unaware that only some of the sort/filter
+                    operations have taken effect. We may need to include a "warnings"
+                    section to indicate which sort/filter operations are unrecognised,
+                    allowing for some form of graceful degradation of service.
+                    -- https://github.com/matrix-org/matrix-spec-proposals/blob/kegan/sync-v3/proposals/3575-sync.md#filter-and-sort-extensions
+
+            slow_get_all_rooms: Just get all rooms (for clients that don't want to deal with
+                sliding windows). When true, the `ranges` and `sort` fields are ignored.
+            required_state: Required state for each room returned. An array of event
+                type and state key tuples. Elements in this array are ORd together to
+                produce the final set of state events to return.
+
+                One unique exception is when you request all state events via `["*",
+                "*"]`. When used, all state events are returned by default, and
+                additional entries FILTER OUT the returned set of state events. These
+                additional entries cannot use `*` themselves. For example, `["*", "*"],
+                ["m.room.member", "@alice:example.com"]` will *exclude* every
+                `m.room.member` event *except* for `@alice:example.com`, and include
+                every other state event. In addition, `["*", "*"], ["m.space.child",
+                "*"]` is an error, the `m.space.child` filter is not required as it
+                would have been returned anyway.
+
+                Room members can be lazily-loaded by using the special `$LAZY` state key
+                (`["m.room.member", "$LAZY"]`). Typically, when you view a room, you
+                want to retrieve all state events except for m.room.member events which
+                you want to lazily load. To get this behaviour, clients can send the
+                following::
+
+                    {
+                        "required_state": [
+                            // activate lazy loading
+                            ["m.room.member", "$LAZY"],
+                            // request all state events _except_ for m.room.member
+                            events which are lazily loaded
+                            ["*", "*"]
+                        ]
+                    }
+
+            timeline_limit: The maximum number of timeline events to return per response.
+            include_old_rooms: Determines if `predecessor` rooms are included in the
+                `rooms` response. The user MUST be joined to old rooms for them to show up
+                in the response.
+            include_heroes: Return a stripped variant of membership events (containing
+                `user_id` and optionally `avatar_url` and `displayname`) for the users used
+                to calculate the room name.
+            filters: Filters to apply to the list before sorting.
+            bump_event_types: Allowlist of event types which should be considered recent activity
+                when sorting `by_recency`. By omitting event types from this field,
+                clients can ensure that uninteresting events (e.g. a profile rename) do
+                not cause a room to jump to the top of its list(s). Empty or omitted
+                `bump_event_types` have no effect—all events in a room will be
+                considered recent activity.
+        """
+
+        class Filters(RequestBodyModel):
+            is_dm: Optional[StrictBool] = None
+            spaces: Optional[List[StrictStr]] = None
+            is_encrypted: Optional[StrictBool] = None
+            is_invite: Optional[StrictBool] = None
+            room_types: Optional[List[Union[StrictStr, None]]] = None
+            not_room_types: Optional[List[StrictStr]] = None
+            room_name_like: Optional[StrictStr] = None
+            tags: Optional[List[StrictStr]] = None
+            not_tags: Optional[List[StrictStr]] = None
+
+        # mypy workaround via https://github.com/pydantic/pydantic/issues/156#issuecomment-1130883884
+        if TYPE_CHECKING:
+            ranges: Optional[List[Tuple[int, int]]] = None
+        else:
+            ranges: Optional[List[Tuple[conint(ge=0, strict=True), conint(ge=0, strict=True)]]] = None  # type: ignore[valid-type]
+        sort: Optional[List[StrictStr]] = None
+        slow_get_all_rooms: Optional[StrictBool] = False
+        include_heroes: Optional[StrictBool] = False
+        filters: Optional[Filters] = None
+        bump_event_types: Optional[List[StrictStr]] = None
+
+    class RoomSubscription(CommonRoomParameters):
+        pass
+
+    class Extension(RequestBodyModel):
+        enabled: Optional[StrictBool] = False
+        lists: Optional[List[StrictStr]] = None
+        rooms: Optional[List[StrictStr]] = None
+
+    # mypy workaround via https://github.com/pydantic/pydantic/issues/156#issuecomment-1130883884
+    if TYPE_CHECKING:
+        lists: Optional[Dict[str, SlidingSyncList]] = None
+    else:
+        lists: Optional[Dict[constr(max_length=64, strict=True), SlidingSyncList]] = None  # type: ignore[valid-type]
+    room_subscriptions: Optional[Dict[StrictStr, RoomSubscription]] = None
+    extensions: Optional[Dict[StrictStr, Extension]] = None
+
+    @validator("lists")
+    def lists_length_check(
+        cls, value: Optional[Dict[str, SlidingSyncList]]
+    ) -> Optional[Dict[str, SlidingSyncList]]:
+        if value is not None:
+            assert len(value) <= 100, f"Max lists: 100 but saw {len(value)}"
+        return value
diff --git a/synapse/rest/client/room.py b/synapse/rest/client/room.py
index fb4d44211e..61fdf71a27 100644
--- a/synapse/rest/client/room.py
+++ b/synapse/rest/client/room.py
@@ -292,6 +292,9 @@ class RoomStateEventRestServlet(RestServlet):
         try:
             if event_type == EventTypes.Member:
                 membership = content.get("membership", None)
+                if not isinstance(membership, str):
+                    raise SynapseError(400, "Invalid membership (must be a string)")
+
                 event_id, _ = await self.room_member_handler.update_membership(
                     requester,
                     target=UserID.from_string(state_key),
diff --git a/synapse/rest/client/sync.py b/synapse/rest/client/sync.py
index 27ea943e31..385b102b3d 100644
--- a/synapse/rest/client/sync.py
+++ b/synapse/rest/client/sync.py
@@ -33,6 +33,7 @@ from synapse.events.utils import (
     format_event_raw,
 )
 from synapse.handlers.presence import format_user_presence_state
+from synapse.handlers.sliding_sync import SlidingSyncConfig, SlidingSyncResult
 from synapse.handlers.sync import (
     ArchivedSyncResult,
     InvitedSyncResult,
@@ -43,9 +44,16 @@ from synapse.handlers.sync import (
     SyncVersion,
 )
 from synapse.http.server import HttpServer
-from synapse.http.servlet import RestServlet, parse_boolean, parse_integer, parse_string
+from synapse.http.servlet import (
+    RestServlet,
+    parse_and_validate_json_object_from_request,
+    parse_boolean,
+    parse_integer,
+    parse_string,
+)
 from synapse.http.site import SynapseRequest
 from synapse.logging.opentracing import trace_with_opname
+from synapse.rest.client.models import SlidingSyncBody
 from synapse.types import JsonDict, Requester, StreamToken
 from synapse.util import json_decoder
 from synapse.util.caches.lrucache import LruCache
@@ -735,8 +743,228 @@ class SlidingSyncE2eeRestServlet(RestServlet):
         return 200, response
 
 
+class SlidingSyncRestServlet(RestServlet):
+    """
+    API endpoint for MSC3575 Sliding Sync `/sync`. Allows for clients to request a
+    subset (sliding window) of rooms, state, and timeline events (just what they need)
+    in order to bootstrap quickly and subscribe to only what the client cares about.
+    Because the client can specify what it cares about, we can respond quickly and skip
+    all of the work we would normally have to do with a sync v2 response.
+
+    Request query parameters:
+        timeout: How long to wait for new events in milliseconds.
+        pos: Stream position token when asking for incremental deltas.
+
+    Request body::
+        {
+            // Sliding Window API
+            "lists": {
+                "foo-list": {
+                    "ranges": [ [0, 99] ],
+                    "sort": [ "by_notification_level", "by_recency", "by_name" ],
+                    "required_state": [
+                        ["m.room.join_rules", ""],
+                        ["m.room.history_visibility", ""],
+                        ["m.space.child", "*"]
+                    ],
+                    "timeline_limit": 10,
+                    "filters": {
+                        "is_dm": true
+                    },
+                    "bump_event_types": [ "m.room.message", "m.room.encrypted" ],
+                }
+            },
+            // Room Subscriptions API
+            "room_subscriptions": {
+                "!sub1:bar": {
+                    "required_state": [ ["*","*"] ],
+                    "timeline_limit": 10,
+                    "include_old_rooms": {
+                        "timeline_limit": 1,
+                        "required_state": [ ["m.room.tombstone", ""], ["m.room.create", ""] ],
+                    }
+                }
+            },
+            // Extensions API
+            "extensions": {}
+        }
+
+    Response JSON::
+        {
+            "next_pos": "s58_224_0_13_10_1_1_16_0_1",
+            "lists": {
+                "foo-list": {
+                    "count": 1337,
+                    "ops": [{
+                        "op": "SYNC",
+                        "range": [0, 99],
+                        "room_ids": [
+                            "!foo:bar",
+                            // ... 99 more room IDs
+                        ]
+                    }]
+                }
+            },
+            // Aggregated rooms from lists and room subscriptions
+            "rooms": {
+                // Room from room subscription
+                "!sub1:bar": {
+                    "name": "Alice and Bob",
+                    "avatar": "mxc://...",
+                    "initial": true,
+                    "required_state": [
+                        {"sender":"@alice:example.com","type":"m.room.create", "state_key":"", "content":{"creator":"@alice:example.com"}},
+                        {"sender":"@alice:example.com","type":"m.room.join_rules", "state_key":"", "content":{"join_rule":"invite"}},
+                        {"sender":"@alice:example.com","type":"m.room.history_visibility", "state_key":"", "content":{"history_visibility":"joined"}},
+                        {"sender":"@alice:example.com","type":"m.room.member", "state_key":"@alice:example.com", "content":{"membership":"join"}}
+                    ],
+                    "timeline": [
+                        {"sender":"@alice:example.com","type":"m.room.create", "state_key":"", "content":{"creator":"@alice:example.com"}},
+                        {"sender":"@alice:example.com","type":"m.room.join_rules", "state_key":"", "content":{"join_rule":"invite"}},
+                        {"sender":"@alice:example.com","type":"m.room.history_visibility", "state_key":"", "content":{"history_visibility":"joined"}},
+                        {"sender":"@alice:example.com","type":"m.room.member", "state_key":"@alice:example.com", "content":{"membership":"join"}},
+                        {"sender":"@alice:example.com","type":"m.room.message", "content":{"body":"A"}},
+                        {"sender":"@alice:example.com","type":"m.room.message", "content":{"body":"B"}},
+                    ],
+                    "prev_batch": "t111_222_333",
+                    "joined_count": 41,
+                    "invited_count": 1,
+                    "notification_count": 1,
+                    "highlight_count": 0
+                },
+                // rooms from list
+                "!foo:bar": {
+                    "name": "The calculated room name",
+                    "avatar": "mxc://...",
+                    "initial": true,
+                    "required_state": [
+                        {"sender":"@alice:example.com","type":"m.room.join_rules", "state_key":"", "content":{"join_rule":"invite"}},
+                        {"sender":"@alice:example.com","type":"m.room.history_visibility", "state_key":"", "content":{"history_visibility":"joined"}},
+                        {"sender":"@alice:example.com","type":"m.space.child", "state_key":"!foo:example.com", "content":{"via":["example.com"]}},
+                        {"sender":"@alice:example.com","type":"m.space.child", "state_key":"!bar:example.com", "content":{"via":["example.com"]}},
+                        {"sender":"@alice:example.com","type":"m.space.child", "state_key":"!baz:example.com", "content":{"via":["example.com"]}}
+                    ],
+                    "timeline": [
+                        {"sender":"@alice:example.com","type":"m.room.join_rules", "state_key":"", "content":{"join_rule":"invite"}},
+                        {"sender":"@alice:example.com","type":"m.room.message", "content":{"body":"A"}},
+                        {"sender":"@alice:example.com","type":"m.room.message", "content":{"body":"B"}},
+                        {"sender":"@alice:example.com","type":"m.room.message", "content":{"body":"C"}},
+                        {"sender":"@alice:example.com","type":"m.room.message", "content":{"body":"D"}},
+                    ],
+                    "prev_batch": "t111_222_333",
+                    "joined_count": 4,
+                    "invited_count": 0,
+                    "notification_count": 54,
+                    "highlight_count": 3
+                },
+                 // ... 99 more items
+            },
+            "extensions": {}
+        }
+    """
+
+    PATTERNS = client_patterns(
+        "/org.matrix.msc3575/sync$", releases=[], v1=False, unstable=True
+    )
+
+    def __init__(self, hs: "HomeServer"):
+        super().__init__()
+        self.auth = hs.get_auth()
+        self.store = hs.get_datastores().main
+        self.filtering = hs.get_filtering()
+        self.sliding_sync_handler = hs.get_sliding_sync_handler()
+
+    # TODO: Update this to `on_GET` once we figure out how we want to handle params
+    async def on_POST(self, request: SynapseRequest) -> Tuple[int, JsonDict]:
+        requester = await self.auth.get_user_by_req(request, allow_guest=True)
+        user = requester.user
+        device_id = requester.device_id
+
+        timeout = parse_integer(request, "timeout", default=0)
+        # Position in the stream
+        from_token_string = parse_string(request, "pos")
+
+        from_token = None
+        if from_token_string is not None:
+            from_token = await StreamToken.from_string(self.store, from_token_string)
+
+        # TODO: We currently don't know whether we're going to use sticky params or
+        # maybe some filters like sync v2  where they are built up once and referenced
+        # by filter ID. For now, we will just prototype with always passing everything
+        # in.
+        body = parse_and_validate_json_object_from_request(request, SlidingSyncBody)
+        logger.info("Sliding sync request: %r", body)
+
+        sync_config = SlidingSyncConfig(
+            user=user,
+            device_id=device_id,
+            # FIXME: Currently, we're just manually copying the fields from the
+            # `SlidingSyncBody` into the config. How can we gurantee into the future
+            # that we don't forget any? I would like something more structured like
+            # `copy_attributes(from=body, to=config)`
+            lists=body.lists,
+            room_subscriptions=body.room_subscriptions,
+            extensions=body.extensions,
+        )
+
+        sliding_sync_results = await self.sliding_sync_handler.wait_for_sync_for_user(
+            requester,
+            sync_config,
+            from_token,
+            timeout,
+        )
+
+        # The client may have disconnected by now; don't bother to serialize the
+        # response if so.
+        if request._disconnected:
+            logger.info("Client has disconnected; not serializing response.")
+            return 200, {}
+
+        response_content = await self.encode_response(sliding_sync_results)
+
+        return 200, response_content
+
+    # TODO: Is there a better way to encode things?
+    async def encode_response(
+        self,
+        sliding_sync_result: SlidingSyncResult,
+    ) -> JsonDict:
+        response: JsonDict = defaultdict(dict)
+
+        response["next_pos"] = await sliding_sync_result.next_pos.to_string(self.store)
+        serialized_lists = self.encode_lists(sliding_sync_result.lists)
+        if serialized_lists:
+            response["lists"] = serialized_lists
+        response["rooms"] = {}  # TODO: sliding_sync_result.rooms
+        response["extensions"] = {}  # TODO: sliding_sync_result.extensions
+
+        return response
+
+    def encode_lists(
+        self, lists: Dict[str, SlidingSyncResult.SlidingWindowList]
+    ) -> JsonDict:
+        def encode_operation(
+            operation: SlidingSyncResult.SlidingWindowList.Operation,
+        ) -> JsonDict:
+            return {
+                "op": operation.op.value,
+                "range": operation.range,
+                "room_ids": operation.room_ids,
+            }
+
+        serialized_lists = {}
+        for list_key, list_result in lists.items():
+            serialized_lists[list_key] = {
+                "count": list_result.count,
+                "ops": [encode_operation(op) for op in list_result.ops],
+            }
+
+        return serialized_lists
+
+
 def register_servlets(hs: "HomeServer", http_server: HttpServer) -> None:
     SyncRestServlet(hs).register(http_server)
 
     if hs.config.experimental.msc3575_enabled:
+        SlidingSyncRestServlet(hs).register(http_server)
         SlidingSyncE2eeRestServlet(hs).register(http_server)