[meta] Automatic backpagination

Niké of Samothrace

---

Hej,

Project of the day: auto-backpagination.

## What?

If Sliding Sync is used to sync, the SDK is likely to have a partial view of the rooms most of the time. It's how Sliding Sync works, it's by design. By that, I mean that there might be many gaps between message-like events (state events are **not** affected by that, except memberships that are lazily loaded). However, having a full view over the rooms would be great. Should we fallback to sync v2? No! It was too slow for us. Sliding Sync is definitely better, but we must be smart and fill the gaps in the background so that nothing is blocked.

## Why?

Filling the gaps bring the following opportunities

- **app badge counter** — by having all the events, it's easier to compute an always correct app badge counter,
- **search** — by having all the events, the user will be able to search across all the message-like events even if the event wasn't in front of his/her eyes,
- **offline** — by having all the events, the user will have a better offline experience: fewer gaps means fewer chances to be stopped reading the history,
- possibly other good reasons

## How?

> [!NOTE]
>
>
> Previous plan
>
> This is not clear yet, but here is a sketch to start discussing it.
>
> ### The rough plan
>
> The key parts of the plan are the following
>
> 1. Prepare a set of rooms
> 2. Fill the gaps in each room
> 3. When to do this?
>
> ### Step 1, Prepare a set of rooms
>
> 1. The set of rooms is
>
> 1. Collect all rooms with at least one gap
> 2. Sort rooms by relevancy
> - Defining “relevancy” isn't trivial:
> - **the most frequently opened rooms** — The SDK doesn't have this knowledge. Relying on `Client::get_room()` isn't useful because this API doesn't mean “a user has opened a room”.
> - **the rooms where the user writes the most** — We could rely on the Send Queue to get this information.
> - **the most active rooms** — We could rely on the timestamp of the last received events for each room. The most active rooms are likely to be at the top of the room list for the majority of the use cases, so it can make sense.
> 3. Update the set of rooms reactively
>
> ### Step 2, Fill the gaps in each room
>
> #### Overall strategy
>
> The overall strategy is likely to be:
>
> 1. [Iterate over the gaps backwards](https://matrix-org.github.io/matrix-rust-sdk/matrix_sdk/linked_chunk/struct.LinkedChunk.html#method.rchunks)
> 2. Take the next gap,
> 3. Resolve the gap with [`RoomPagination`](https://matrix-org.github.io/matrix-rust-sdk/matrix_sdk/event_cache/struct.RoomPagination.html), modified to resolve a particular gap instead of _the leading in-memory gap_, and save the results in the store without (optionally) not touching the in-memory data
> 4. Repeat (jump at 2) or stop.
>
> #### When to stop filling the gaps?
>
> The question is when to stop filling the gaps? Here are the possible strategies:
>
> - **Round robin like** — Resolve $N$ gaps for each room, where $N \in \texttt{usize}$. When all rooms have been visited, start again. If a room has no more gap, remove it from the set of rooms.
> - **Marker-based** — Resolve all gaps until a certain marker is met. It can be a read marker for example. What if the marker is missing? Should we fallback to another strategy?
> - Any other idea?
>
> Of course, we can select multiple rooms at a time to have parallelism, it's not a problem.
>
> #### The edge cases
>
> Of course, there are edge cases, otherwise this project would be too easy.
>
> - What if there is no read marker?
> - What if a room has an accessible history, and is super old (hello Matrix HQ), we don't want to load the entire room! We **should not** auto-backpaginate prior to point where we've joined the room (it could be a general rule).
>
> ### Step 3, When to do this?
>
> Thanks for asking. Very likely when the `all_rooms` Sliding Sync list used by the [`RoomListService`](https://matrix-org.github.io/matrix-rust-sdk/matrix_sdk_ui/room_list_service/struct.RoomListService.html) is fully loaded, i.e. when all rooms have been synced and we enter long-polling (note: we may want to add a third state to [`RoomListLoadingState`](https://matrix-org.github.io/matrix-rust-sdk/matrix_sdk_ui/room_list_service/enum.RoomListLoadingState.html) to make this obvious to know). That way, it doesn't conflict with the regular syncs in terms of bandwidth and network access in general.
>

The Event Cache is likely to own a new component: `AutomaticBackPagination`.

External components, for example `LatestEvent`, will drive it via _Strategies_. A `Strategy` defines:

- **priority** — the priority of the pagination
- not all paginations are equal, e.g. a pagination for the `Search` is less important than a pagination for the `LatestEvent`
- maybe three levels is enough:
```rust
enum Priority {
High,
Normal,
Low,
}
```
- **stop condition** — when to stop the pagination
- the `Search` needs to stop at the beginning of the room, whilst the `LatestEvent` needs to stop as soon as latest event candidate is found
- a rough idea for a flexible mechanism:
- the `Strategy` can hold a callback that is responsible to tell the `AutomaticBackPagination` to stop or not after each pagination (successful or not!):
```rust
F: AsyncFnMut(PaginationOutcome) -> ControlFlow<()>
```
- the callback might introduce lifetime or borrowing troubles, let's see in practice.
- I can foresee a problem with the latest event behaviour already: detecting when to stop is similar to computing the latest event twice (one for detecting when to stop, and then one again to compute and save it)
- maybe the ideal workflow would be:
- the `AutomaticBackPagination` _suspends_ its execution after a pagination
- the `AutomaticBackPagination` _notifies_ the caller about the pagination outcome
- the `AutomaticBackPagination` _waits_ (with a configurable timeout? what happens when it expires?)
- the caller _resumes_ or _cancels_ the `AutomaticBackPagination`
- I see a simple solution: `AutomaticBackPagination` produces a `Stream>>` (see [`futures::channel::oneshot`](https://docs.rs/futures/latest/futures/channel/oneshot/index.html))!
```rust
let ongoing_pagination = automatic_back_pagination.run(Strategy { room_id, thread_id, priority, … });
let control_flow = ongoing_pagination.next().await;
// run something and see if we should stop or not
control_flow.send(ControlFlow::Continue(()));
// wait for another pagination to be done
let control_flow = ongoing_pagination.next().await;
// run something again and see if we shoul stop or not
control_flow.send(ControlFlow::Break(()));
// done!
```
- this idea is pretty similar to coroutine

A `Strategy` is sent to the `AutomaticBackPagination` component via a channel probably. `AutomaticBackPagination` will own a task that will listen to new strategy and will schedule them. We need to be very careful about concurrent paginations (which is already handled, but it will happen more often), and the scheduling in general (do we need to cancel or to pause one pagination to give the priority to another one?).

---

- Address https://github.com/element-hq/element-x-ios/issues/3151

Start by reading the Event Cache flow around RoomPagination and LinkedChunk::rchunks, then inspect how RoomListService and RoomListLoadingState expose the fully loaded all_rooms state. The proposed component is AutomaticBackPagination, driven by prioritized Strategies; done means its scheduling, stopping, concurrency, and room-history boundaries are defined and implemented.

Written by the indexing model from the issue text.