Wip-2

src/@types/global.d.ts

@@ -47,6 +47,7 @@ import { type DeepReadonly } from "./common";
 import type MatrixChat from "../components/structures/MatrixChat";
 import { type InitialCryptoSetupStore } from "../stores/InitialCryptoSetupStore";
 import { type ModuleApiType } from "../modules/Api.ts";
+import type RoomListStoreV3 from "../stores/room-list-v3/RoomListStoreV3.ts";
 
 /* eslint-disable @typescript-eslint/naming-convention */
 
@@ -99,6 +100,7 @@ declare global {
         mxToastStore: ToastStore;
         mxDeviceListener: DeviceListener;
         mxRoomListStore: RoomListStore;
+        mxRoomListStoreV3: RoomListStoreV3;
         mxRoomListLayoutStore: RoomListLayoutStore;
         mxPlatformPeg: PlatformPeg;
         mxIntegrationManagers: typeof IntegrationManagers;

src/components/views/rooms/RoomListView.tsx

@@ -5,10 +5,27 @@ SPDX-License-Identifier: AGPL-3.0-only OR GPL-3.0-only OR LicenseRef-Element-Com
 Please see LICENSE files in the repository root for full details.
 */
 
-import React from "react";
+import React, { useEffect, useState } from "react";
+
+import type { Room } from "matrix-js-sdk/src/matrix";
+import RoomListStoreV3 from "../../../stores/room-list-v3/RoomListStoreV3";
+import { LISTS_UPDATE_EVENT } from "../../../stores/room-list/SlidingRoomListStore";
 
 type IProps = unknown;
 
 export const RoomListView: React.FC<IProps> = (props: IProps) => {
-    return <div>New Room List</div>;
+    const [rooms, setRooms] = useState<Room[]>(RoomListStoreV3.instance.getSortedRooms());
+    useEffect(() => {
+        RoomListStoreV3.instance.on(LISTS_UPDATE_EVENT, () => {
+            const newRooms = RoomListStoreV3.instance.getSortedRooms();
+            setRooms(() => newRooms);
+        });
+    }, []);
+    return (
+        <div>
+            {rooms.map((r) => (
+                <div>{r.name}</div>
+            ))}
+        </div>
+    );
 };

src/stores/room-list-v3/RoomListStoreV3.ts

@@ -0,0 +1,89 @@
+/*
+Copyright 2025 New Vector Ltd.
+
+SPDX-License-Identifier: AGPL-3.0-only OR GPL-3.0-only OR LicenseRef-Element-Commercial
+Please see LICENSE files in the repository root for full details.
+*/
+
+import type { EmptyObject, Room } from "matrix-js-sdk/src/matrix";
+import type { MatrixDispatcher } from "../../dispatcher/dispatcher";
+import type { ActionPayload } from "../../dispatcher/payloads";
+import { AsyncStoreWithClient } from "../AsyncStoreWithClient";
+import SettingsStore from "../../settings/SettingsStore";
+import { VisibilityProvider } from "../room-list/filters/VisibilityProvider";
+import defaultDispatcher from "../../dispatcher/dispatcher";
+import { LISTS_UPDATE_EVENT } from "../room-list/RoomListStore";
+import { RoomSkipList } from "./skip-list/RoomSkipList";
+import type { IRoomTimelineActionPayload } from "../../actions/MatrixActionCreators";
+import { RecencySorter } from "./skip-list/sorters/RecencySorter";
+
+export class RoomListStoreV3Class extends AsyncStoreWithClient<EmptyObject> {
+    private roomSkipList?: RoomSkipList;
+    private readonly msc3946ProcessDynamicPredecessor: boolean;
+
+    public constructor(dispatcher: MatrixDispatcher) {
+        super(dispatcher);
+        this.msc3946ProcessDynamicPredecessor = SettingsStore.getValue("feature_dynamic_room_predecessors");
+    }
+
+    public getSortedRooms(): Room[] {
+        if (this.roomSkipList?.initialized) return Array.from(this.roomSkipList);
+        else return [];
+    }
+
+    protected async onReady(): Promise<any> {
+        if (this.roomSkipList?.initialized || !this.matrixClient) return;
+        const sorter = new RecencySorter(this.matrixClient.getSafeUserId() ?? "");
+        this.roomSkipList = new RoomSkipList(sorter);
+        const rooms = this.fetchRoomsFromSdk();
+        if (!rooms) return;
+        this.roomSkipList.seed(rooms);
+        this.emit(LISTS_UPDATE_EVENT);
+    }
+
+    protected async onAction(payload: ActionPayload): Promise<void> {
+        if (!this.matrixClient || !this.roomSkipList?.initialized) return;
+        const room = this.getRoomFromPayload(payload);
+        if (room) {
+            setTimeout(() => {
+                this.roomSkipList!.addRoom(room);
+                this.emit(LISTS_UPDATE_EVENT);
+            });
+        }
+    }
+
+    private getRoomFromPayload(payload: ActionPayload): Room | undefined {
+        if (payload.room) {
+            return payload.room;
+        }
+        if (payload.action === "MatrixActions.Room.timeline") {
+            const eventPayload = <IRoomTimelineActionPayload>payload;
+            const roomId = eventPayload.event.getRoomId();
+            const room = this.matrixClient?.getRoom(roomId);
+            return room ?? undefined;
+        }
+    }
+
+    private fetchRoomsFromSdk(): Room[] | null {
+        if (!this.matrixClient) return null;
+        let rooms = this.matrixClient.getVisibleRooms(this.msc3946ProcessDynamicPredecessor);
+        rooms = rooms.filter((r) => VisibilityProvider.instance.isRoomVisible(r));
+        return rooms;
+    }
+}
+
+export default class RoomListStoreV3 {
+    private static internalInstance: RoomListStoreV3Class;
+
+    public static get instance(): RoomListStoreV3Class {
+        if (!RoomListStoreV3.internalInstance) {
+            const instance = new RoomListStoreV3Class(defaultDispatcher);
+            instance.start();
+            RoomListStoreV3.internalInstance = instance;
+        }
+
+        return this.internalInstance;
+    }
+}
+
+window.mxRoomListStoreV3 = RoomListStoreV3.instance;

src/stores/room-list-v3/skip-list/Level.ts

@@ -0,0 +1,114 @@
+/*
+Copyright 2025 New Vector Ltd.
+
+SPDX-License-Identifier: AGPL-3.0-only OR GPL-3.0-only OR LicenseRef-Element-Commercial
+Please see LICENSE files in the repository root for full details.
+*/
+
+import type { RoomNode } from "./RoomNode";
+import { shouldPromote } from "./utils";
+
+/**
+ * Represents one level of the skip list
+ */
+export class Level {
+    public head?: RoomNode;
+    private current?: RoomNode;
+    private _size: number = 0;
+
+    /**
+     * The number of elements in this level
+     */
+    public get size(): number {
+        return this._size;
+    }
+
+    public constructor(public readonly level: number) {}
+
+    /**
+     * Insert node after current
+     */
+    public setNext(node: RoomNode): void {
+        if (!this.head) this.head = node;
+        if (!this.current) {
+            this.current = node;
+        } else {
+            node.previous[this.level] = this.current;
+            this.current.next[this.level] = node;
+            this.current = node;
+        }
+        this._size++;
+    }
+
+    /**
+     * Iterate through the elements in this level and create
+     * a new level above this level by probabilistically determining
+     * whether a given element must be promoted to the new level.
+     */
+    public generateNextLevel(): Level {
+        const nextLevelSentinel = new Level(this.level + 1);
+        let current = this.head;
+        while (current) {
+            if (shouldPromote()) {
+                nextLevelSentinel.setNext(current);
+            }
+            current = current.next[this.level];
+        }
+        return nextLevelSentinel;
+    }
+
+    /**
+     * Removes a given node from this level.
+     * Does nothing if the given node is not present in this level.
+     */
+    public removeNode(node: RoomNode): void {
+        // Let's first see if this node is even in this level
+        const nodeInThisLevel = this.head === node || node.previous[this.level];
+        if (!nodeInThisLevel) {
+            // This node is not in this sentinel level, so nothing to do.
+            return;
+        }
+        const prev = node.previous[this.level];
+        if (prev) {
+            const nextNode = node.next[this.level];
+            prev.next[this.level] = nextNode;
+            if (nextNode) nextNode.previous[this.level] = prev;
+        } else {
+            // This node was the head since it has no back links!
+            // so update the head.
+            const next = node.next[this.level];
+            this.head = next;
+            if (next) next.previous[this.level] = node.previous[this.level];
+        }
+        this._size--;
+    }
+
+    /**
+     * Put newNode after node in this level. No checks are done to ensure
+     * that node is actually present in this level.
+     */
+    public insertAfter(node: RoomNode, newNode: RoomNode): void {
+        const level = this.level;
+        const nextNode = node.next[level];
+        if (nextNode) {
+            newNode.next[level] = nextNode;
+            nextNode.previous[level] = newNode;
+        }
+        node.next[level] = newNode;
+        newNode.previous[level] = node;
+        this._size++;
+    }
+
+    /**
+     *  Insert a given node at the head of this level.
+     */
+    public insertAtHead(newNode: RoomNode): void {
+        const existingNode = this.head;
+        this.head = newNode;
+        if (existingNode) {
+            newNode.next[this.level] = existingNode;
+            existingNode.previous[this.level] = newNode;
+        }
+        this._size++;
+    }
+}

src/stores/room-list-v3/skip-list/RoomNode.ts

@@ -0,0 +1,29 @@
+/*
+Copyright 2025 New Vector Ltd.
+
+SPDX-License-Identifier: AGPL-3.0-only OR GPL-3.0-only OR LicenseRef-Element-Commercial
+Please see LICENSE files in the repository root for full details.
+*/
+
+import type { Room } from "matrix-js-sdk/src/matrix";
+
+/**
+ * Room skip list stores room nodes.
+ * These hold the actual room object and provides references to other nodes
+ * in different levels.
+ */
+export class RoomNode {
+    public constructor(public readonly room: Room) {}
+
+    /**
+     * This array holds references to the next node in a given level.
+     * eg: next[i] gives the next room node from this room node in level i.
+     */
+    public next: RoomNode[] = [];
+
+    /**
+     * This array holds references to the previous node in a given level.
+     * eg: previous[i] gives the next room node from this room node in level i.
+     */
+    public previous: RoomNode[] = [];
+}

src/stores/room-list-v3/skip-list/RoomSkipList.ts

@@ -0,0 +1,166 @@
+/*
+Copyright 2025 New Vector Ltd.
+
+SPDX-License-Identifier: AGPL-3.0-only OR GPL-3.0-only OR LicenseRef-Element-Commercial
+Please see LICENSE files in the repository root for full details.
+*/
+
+import type { Room } from "matrix-js-sdk/src/matrix";
+import type { Sorter } from "./sorters";
+import { RoomNode } from "./RoomNode";
+import { shouldPromote } from "./utils";
+import { Level } from "./Level";
+
+/**
+ * Implements a skip list that stores rooms using a given sorting algorithm.
+ * See See https://en.wikipedia.org/wiki/Skip_list
+ */
+export class RoomSkipList implements Iterable<Room> {
+    private readonly levels: Level[] = [new Level(0)];
+    private readonly roomNodeMap: Map<string, RoomNode> = new Map();
+    public initialized: boolean = false;
+
+    public constructor(private readonly sorter: Sorter) {}
+
+    /**
+     * Seed the list with an initial list of rooms.
+     */
+    public seed(rooms: Room[]): void {
+        // 1. First sort the rooms and create a base sorted linked list
+        const sortedRoomNodes = this.sorter.sort(rooms).map((room) => new RoomNode(room));
+        let currentLevel = this.levels[0];
+        for (const node of sortedRoomNodes) {
+            currentLevel.setNext(node);
+            this.roomNodeMap.set(node.room.roomId, node);
+        }
+
+        // 2. Create the rest of the sub linked lists
+        do {
+            this.levels[currentLevel.level] = currentLevel;
+            currentLevel = currentLevel.generateNextLevel();
+        } while (currentLevel.size > 1);
+        this.initialized = true;
+    }
+
+    /**
+     * Removes a given room from the skip list.
+     */
+    public removeRoom(room: Room): void {
+        const existingNode = this.roomNodeMap.get(room.roomId);
+        this.roomNodeMap.delete(room.roomId);
+        if (existingNode) {
+            for (const level of this.levels) {
+                level.removeNode(existingNode);
+            }
+        }
+    }
+
+    /**
+     * Adds a given room to the correct sorted position in the list.
+     * If the room is already present in the list, it is first removed.
+     */
+    public addRoom(room: Room): void {
+        /**
+         * Remove this room from the skip list if necessary.
+         */
+        this.removeRoom(room);
+
+        const newNode = new RoomNode(room);
+        this.roomNodeMap.set(room.roomId, newNode);
+
+        /**
+         * This array tracks where the new node must be inserted in a
+         * given level.
+         * The index is the level and the value represents where the
+         * insertion must happen.
+         * If the value is null, it simply means that we need to insert
+         * at the head.
+         * If the value is a RoomNode, simply insert after this node.
+         */
+        const insertionNodes: (RoomNode | null)[] = [];
+
+        /**
+         * Now we'll do the actual work of finding where to insert this
+         * node.
+         *
+         * We start at the top most level and move downwards ...
+         */
+        for (let j = this.levels.length - 1; j >= 0; --j) {
+            const level = this.levels[j];
+
+            /**
+             * If the head is undefined, that means this level is empty.
+             * So mark it as such in insertionNodes and skip over this
+             * level.
+             */
+            if (!level.head) {
+                insertionNodes[j] = null;
+                continue;
+            }
+
+            /**
+             * So there's actually some nodes in this level ...
+             * All we need to do is find the node that is smaller or
+             * equal to the node that we wish to insert.
+             */
+            let current = level.head;
+            let previous: RoomNode | null = null;
+            while (current) {
+                if (this.sorter.comparator(current.room, room) < 0) {
+                    previous = current;
+                    current = current.next[j];
+                } else break;
+            }
+
+            /**
+             * previous will now be null if there's no node in this level
+             * smaller than the node we wish to insert or it will be a
+             * RoomNode.
+             * This is exactly what we need to track in insertionNodes!
+             */
+            insertionNodes[j] = previous;
+        }
+
+        /**
+         * We're done with difficult part, now we just need to do the
+         * actual node insertion.
+         */
+        for (const [level, node] of insertionNodes.entries()) {
+            /**
+             * Whether our new node should be present in a level
+             * is decided by coin toss.
+             */
+            if (level === 0 || shouldPromote()) {
+                const levelObj = this.levels[level];
+                if (node) levelObj.insertAfter(node, newNode);
+                else levelObj.insertAtHead(newNode);
+            } else {
+                break;
+            }
+        }
+    }
+
+    public [Symbol.iterator](): SortedRoomIterator {
+        return new SortedRoomIterator(this.levels[0].head!);
+    }
+
+    /**
+     * The number of rooms currently in the skip list.
+     */
+    public get size(): number {
+        return this.levels[0].size;
+    }
+}
+
+class SortedRoomIterator implements Iterator<Room> {
+    public constructor(private current: RoomNode) {}
+
+    public next(): IteratorResult<Room> {
+        const current = this.current;
+        if (!current) return { value: undefined, done: true };
+        this.current = current.next[0];
+        return {
+            value: current.room,
+        };
+    }
+}

src/stores/room-list-v3/skip-list/sorters/AlphabeticSorter.ts

@@ -0,0 +1,23 @@
+/*
+Copyright 2025 New Vector Ltd.
+
+SPDX-License-Identifier: AGPL-3.0-only OR GPL-3.0-only OR LicenseRef-Element-Commercial
+Please see LICENSE files in the repository root for full details.
+*/
+
+import type { Room } from "matrix-js-sdk/src/matrix";
+import type { Sorter } from ".";
+
+export class AlphabeticSorter implements Sorter {
+    private readonly collator = new Intl.Collator();
+
+    public sort(rooms: Room[]): Room[] {
+        return rooms.sort((a, b) => {
+            return this.comparator(a, b);
+        });
+    }
+
+    public comparator(roomA: Room, roomB: Room): number {
+        return this.collator.compare(roomA.name, roomB.name);
+    }
+}

src/stores/room-list-v3/skip-list/sorters/RecencySorter.ts

@@ -0,0 +1,33 @@
+/*
+Copyright 2025 New Vector Ltd.
+
+SPDX-License-Identifier: AGPL-3.0-only OR GPL-3.0-only OR LicenseRef-Element-Commercial
+Please see LICENSE files in the repository root for full details.
+*/
+
+import type { Room } from "matrix-js-sdk/src/matrix";
+import type { Sorter } from ".";
+import { getLastTs } from "../../../room-list/algorithms/tag-sorting/RecentAlgorithm";
+
+export class RecencySorter implements Sorter {
+    public constructor(private myUserId: string) {}
+
+    public sort(rooms: Room[]): Room[] {
+        const tsCache: { [roomId: string]: number } = {};
+        return [...rooms].sort((a, b) => this.comparator(a, b, tsCache));
+    }
+
+    public comparator(roomA: Room, roomB: Room, cache?: any): number {
+        const roomALastTs = this.getTs(roomA, cache);
+        const roomBLastTs = this.getTs(roomB, cache);
+        return roomBLastTs - roomALastTs;
+    }
+
+    private getTs(room: Room, cache?: { [roomId: string]: number }): number {
+        const ts = cache?.[room.roomId] ?? getLastTs(room, this.myUserId);
+        if (cache) {
+            cache[room.roomId] = ts;
+        }
+        return ts;
+    }
+}

src/stores/room-list-v3/skip-list/sorters/index.ts

@@ -0,0 +1,13 @@
+/*
+Copyright 2025 New Vector Ltd.
+
+SPDX-License-Identifier: AGPL-3.0-only OR GPL-3.0-only OR LicenseRef-Element-Commercial
+Please see LICENSE files in the repository root for full details.
+*/
+
+import type { Room } from "matrix-js-sdk/src/matrix";
+
+export interface Sorter {
+    sort(rooms: Room[]): Room[];
+    comparator(roomA: Room, roomB: Room): number;
+}

src/stores/room-list-v3/skip-list/utils.ts

@@ -0,0 +1,10 @@
+/*
+Copyright 2025 New Vector Ltd.
+
+SPDX-License-Identifier: AGPL-3.0-only OR GPL-3.0-only OR LicenseRef-Element-Commercial
+Please see LICENSE files in the repository root for full details.
+*/
+
+export function shouldPromote(): boolean {
+    return Math.random() < 0.5;
+}

src/stores/room-list/algorithms/tag-sorting/RecentAlgorithm.ts

@@ -62,7 +62,7 @@ export const sortRooms = (rooms: Room[]): Room[] => {
     });
 };
 
-const getLastTs = (r: Room, userId: string): number => {
+export const getLastTs = (r: Room, userId: string): number => {
     const mainTimelineLastTs = ((): number => {
         // Apparently we can have rooms without timelines, at least under testing
         // environments. Just return MAX_INT when this happens.

test/unit-tests/stores/room-list-v3/RoomSkipList-test.ts

@@ -0,0 +1,122 @@
+/*
+Copyright 2025 New Vector Ltd.
+
+SPDX-License-Identifier: AGPL-3.0-only OR GPL-3.0-only OR LicenseRef-Element-Commercial
+Please see LICENSE files in the repository root for full details.
+*/
+
+import { shuffle } from "lodash";
+
+import type { MatrixClient, Room } from "matrix-js-sdk/src/matrix";
+import { mkMessage, mkStubRoom, stubClient } from "../../../test-utils";
+import { RoomSkipList } from "../../../../src/stores/room-list-v3/skip-list/RoomSkipList";
+import { RecencySorter } from "../../../../src/stores/room-list-v3/skip-list/sorters/RecencySorter";
+
+describe("RoomSkipList", () => {
+    function getMockedRooms(client: MatrixClient, roomCount: number = 100): Room[] {
+        const rooms: Room[] = [];
+        for (let i = 0; i < roomCount; ++i) {
+            const roomId = `!foo${i}:matrix.org`;
+            const room = mkStubRoom(roomId, `Foo Room ${i}`, client);
+            const event = mkMessage({ room: roomId, user: `@foo${i}:matrix.org`, ts: i + 1, event: true });
+            room.timeline.push(event);
+            rooms.push(room);
+        }
+        return rooms;
+    }
+
+    function generateSkipList(roomCount?: number): { skipList: RoomSkipList; rooms: Room[]; totalRooms: number } {
+        const client = stubClient();
+        const sorter = new RecencySorter(client.getSafeUserId());
+        const skipList = new RoomSkipList(sorter);
+        const rooms = getMockedRooms(client, roomCount);
+        skipList.seed(rooms);
+        return { skipList, rooms, totalRooms: rooms.length };
+    }
+
+    it("Rooms are in sorted order after initial seed", () => {
+        const { skipList, totalRooms } = generateSkipList();
+        expect(skipList.size).toEqual(totalRooms);
+        const sortedRooms = [...skipList];
+        for (let i = 0; i < totalRooms; ++i) {
+            expect(sortedRooms[i].roomId).toEqual(`!foo${totalRooms - i - 1}:matrix.org`);
+        }
+    });
+
+    it("Tolerates multiple, repeated inserts of existing rooms", () => {
+        const { skipList, rooms, totalRooms } = generateSkipList();
+        // Let's choose 5 rooms from the list
+        const toInsert = [23, 76, 2, 90, 66].map((i) => rooms[i]);
+        for (const room of toInsert) {
+            // Insert this room 10 times
+            for (let i = 0; i < 10; ++i) {
+                skipList.addRoom(room);
+            }
+        }
+        // Sorting order should be the same as before
+        const sortedRooms = [...skipList];
+        for (let i = 0; i < totalRooms; ++i) {
+            expect(sortedRooms[i].roomId).toEqual(`!foo${totalRooms - i - 1}:matrix.org`);
+        }
+    });
+
+    it("Sorting order is maintained when rooms are inserted", () => {
+        const { skipList, rooms, totalRooms } = generateSkipList();
+        // To simulate the worst case, let's say the order gets reversed one by one
+        for (let i = 0; i < rooms.length; ++i) {
+            const room = rooms[i];
+            const event = mkMessage({
+                room: room.roomId,
+                user: `@foo${i}:matrix.org`,
+                ts: totalRooms - i,
+                event: true,
+            });
+            room.timeline.push(event);
+            skipList.addRoom(room);
+            expect(skipList.size).toEqual(rooms.length);
+        }
+        const sortedRooms = [...skipList];
+        for (let i = 0; i < totalRooms; ++i) {
+            expect(sortedRooms[i].roomId).toEqual(`!foo${i}:matrix.org`);
+        }
+    });
+
+    describe("Empty skip list functionality", () => {
+        it("Insertions into empty skip list works", () => {
+            // Create an empty skip list
+            const client = stubClient();
+            const sorter = new RecencySorter(client.getSafeUserId());
+            const roomSkipList = new RoomSkipList(sorter);
+            expect(roomSkipList.size).toEqual(0);
+            roomSkipList.seed([]);
+            expect(roomSkipList.size).toEqual(0);
+
+            // Create some rooms
+            const totalRooms = 10;
+            const rooms = getMockedRooms(client, totalRooms);
+
+            // Shuffle and insert the rooms
+            for (const room of shuffle(rooms)) {
+                roomSkipList.addRoom(room);
+            }
+
+            expect(roomSkipList.size).toEqual(totalRooms);
+            const sortedRooms = [...roomSkipList];
+            for (let i = 0; i < totalRooms; ++i) {
+                expect(sortedRooms[i].roomId).toEqual(`!foo${totalRooms - i - 1}:matrix.org`);
+            }
+        });
+
+        it("Tolerates deletions until skip list is empty", () => {
+            const { skipList, rooms } = generateSkipList(10);
+            const sorted = [...skipList];
+            for (const room of shuffle(rooms)) {
+                skipList.removeRoom(room);
+                const i = sorted.findIndex((r) => r.roomId === room.roomId);
+                sorted.splice(i, 1);
+                expect([...skipList]).toEqual(sorted);
+            }
+            expect(skipList.size).toEqual(0);
+        });
+    });
+});