implement KeysetPageSource and MenuKeysetPages

ioistired commented 4 years ago

This PR enables paginating sources which do not support absolute page numbers. For some systems, especially database systems, absolute offset-based page numbers suffer performance and concurrency issues. The typical pagination approach for such systems is to pass the last item seen, and request one page worth of items occurring after that item (a similar approach is taken for getting the previous page). This is called keyset pagination.

The existing PageSource API cannot accommodate this without a lot of work. (I tried it, and it would probably require a custom int subclass that supports subtraction from infinity.)

To accomplish keyset pagination, two new classes, KeysetPageSource, analogous to PageSource, and MenuKeysetPages, which is analogous to MenuPages are implemented. Consumers should implement a subclass of KeysetPageSource and pass an instance of it to MenuKeysetPages.

To me, the most obvious way of specifying any arbitrary page in a keyset system is with a direction and an optional reference. Direction being before or after, and reference being the last page seen (None indicates the first or last page). A PageDirection enum and PageSpecifier class are added for this purpose. PageSpecifier composes PageDirection, and an instance of it is passed to KeysetPageSource.get_page.

ioistired commented 4 years ago

Sample consumer code:

import itertools
import string

import asyncpg
import discord
from discord.ext import menus
from discord.ext.menus import PageDirection

class FooSource(menus.KeysetPageSource):
    async def prepare(self):
        self.db = await asyncpg.connect()
        await self.db.execute("""
            CREATE TABLE IF NOT EXISTS mytab (
                id INTEGER GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
                name TEXT NOT NULL
            );
            TRUNCATE TABLE mytab
        """)
        # insert every possible 2 character ascii lowercase string
        await self.db.executemany("""
            INSERT INTO mytab (name) VALUES ($1)
        """, [(''.join(chars),) for chars in itertools.product(string.ascii_lowercase, repeat=2)])

    def is_paginating(self):
        return True

    async def get_page(self, specifier):
        query = """
            SELECT * FROM (
                SELECT * FROM mytab
                {where_clause}
                ORDER BY id {sort_order}
                LIMIT 10
            ) subq
            -- make sure that the display order is always correct
            ORDER BY id
        """

        args = []

        if specifier.reference is None:
            where_clause = ''
        elif specifier.direction is PageDirection.after:
            where_clause = 'WHERE id > $1'
            args.append(specifier.reference[-1]['id'])
        else:  # PageDirection.before
            where_clause = 'WHERE id < $1'
            args.append(specifier.reference[0]['id'])

        # if we're getting the previous page,
        # we use DESC to actually get the previous page, rather than the first 10 entries in the database
        sort_order = 'ASC' if specifier.direction is PageDirection.after else 'DESC'

        results = await self.db.fetch(query.format(where_clause=where_clause, sort_order=sort_order), *args)
        if not results:
            raise ValueError

        return results

    async def format_page(self, menu, page):
        return discord.Embed(description='\n'.join(row['name'] for row in page))

ioistired commented 4 years ago

Here's another example, which isn't very useful but demonstrates how to paginate all of the message IDs in a particular channel:

class HistorySource(menus.KeysetPageSource):
    def __init__(self, channel):
        self.channel = channel

    def is_paginating(self):
        return True

    async def get_page(self, specifier):
        kwargs = {}
        if specifier.reference is not None:
            if specifier.direction is PageDirection.after:
                kwargs['after'] = specifier.reference[-1]
            else:
                kwargs['before'] = specifier.reference[0]
        elif specifier.direction is PageDirection.after:
            kwargs['oldest_first'] = True

        messages = await self.channel.history(**kwargs, limit=10).flatten()
        if not messages:
            raise ValueError
        if specifier.direction is PageDirection.before:
            messages.reverse()

        return messages

    def format_page(self, menu, page):
        return discord.Embed(description='\n'.join(str(msg.id) for msg in page))

ioistired commented 4 years ago

Design issues discussed here:

Rapptz / discord-ext-menus

implement KeysetPageSource and MenuKeysetPages #5