Merge pull request #2428 from tomchristie/cursor-pagination

Cursor pagination

4 files changed, 343 insertions, 20 deletions

diff --git a/rest_framework/filters.py b/rest_framework/filters.py
index d188a2d1..2bcf3699 100644
--- a/rest_framework/filters.py
+++ b/rest_framework/filters.py
@@ -114,7 +114,7 @@ class OrderingFilter(BaseFilterBackend):
     ordering_param = api_settings.ORDERING_PARAM
     ordering_fields = None
 
-    def get_ordering(self, request):
+    def get_ordering(self, request, queryset, view):
         """
         Ordering is set by a comma delimited ?ordering=... query parameter.
 
@@ -124,7 +124,13 @@ class OrderingFilter(BaseFilterBackend):
         """
         params = request.query_params.get(self.ordering_param)
         if params:
-            return [param.strip() for param in params.split(',')]
+            fields = [param.strip() for param in params.split(',')]
+            ordering = self.remove_invalid_fields(queryset, fields, view)
+            if ordering:
+                return ordering
+
+        # No ordering was included, or all the ordering fields were invalid
+        return self.get_default_ordering(view)
 
     def get_default_ordering(self, view):
         ordering = getattr(view, 'ordering', None)
@@ -132,7 +138,7 @@ class OrderingFilter(BaseFilterBackend):
             return (ordering,)
         return ordering
 
-    def remove_invalid_fields(self, queryset, ordering, view):
+    def remove_invalid_fields(self, queryset, fields, view):
         valid_fields = getattr(view, 'ordering_fields', self.ordering_fields)
 
         if valid_fields is None:
@@ -152,18 +158,10 @@ class OrderingFilter(BaseFilterBackend):
             valid_fields = [field.name for field in queryset.model._meta.fields]
             valid_fields += queryset.query.aggregates.keys()
 
-        return [term for term in ordering if term.lstrip('-') in valid_fields]
+        return [term for term in fields if term.lstrip('-') in valid_fields]
 
     def filter_queryset(self, request, queryset, view):
-        ordering = self.get_ordering(request)
-
-        if ordering:
-            # Skip any incorrect parameters
-            ordering = self.remove_invalid_fields(queryset, ordering, view)
-
-        if not ordering:
-            # Use 'ordering' attribute by default
-            ordering = self.get_default_ordering(view)
+        ordering = self.get_ordering(request, queryset, view)
 
         if ordering:
             return queryset.order_by(*ordering)
diff --git a/rest_framework/pagination.py b/rest_framework/pagination.py
index 55c173df..b3658aca 100644
--- a/rest_framework/pagination.py
+++ b/rest_framework/pagination.py
@@ -1,12 +1,15 @@
+# coding: utf-8
 """
 Pagination serializers determine the structure of the output that should
 be used for paginated responses.
 """
 from __future__ import unicode_literals
+from base64 import b64encode, b64decode
 from collections import namedtuple
 from django.core.paginator import InvalidPage, Paginator as DjangoPaginator
 from django.template import Context, loader
 from django.utils import six
+from django.utils.six.moves.urllib import parse as urlparse
 from django.utils.translation import ugettext as _
 from rest_framework.compat import OrderedDict
 from rest_framework.exceptions import NotFound
@@ -17,12 +20,12 @@ from rest_framework.utils.urls import (
 )
 
 
-def _strict_positive_int(integer_string, cutoff=None):
+def _positive_int(integer_string, strict=False, cutoff=None):
     """
     Cast a string to a strictly positive integer.
     """
     ret = int(integer_string)
-    if ret <= 0:
+    if ret < 0 or (ret == 0 and strict):
         raise ValueError()
     if cutoff:
         ret = min(ret, cutoff)
@@ -123,6 +126,53 @@ def _get_page_links(page_numbers, current, url_func):
     return page_links
 
 
+def _decode_cursor(encoded):
+    """
+    Given a string representing an encoded cursor, return a `Cursor` instance.
+    """
+    try:
+        querystring = b64decode(encoded.encode('ascii')).decode('ascii')
+        tokens = urlparse.parse_qs(querystring, keep_blank_values=True)
+
+        offset = tokens.get('o', ['0'])[0]
+        offset = _positive_int(offset)
+
+        reverse = tokens.get('r', ['0'])[0]
+        reverse = bool(int(reverse))
+
+        position = tokens.get('p', [None])[0]
+    except (TypeError, ValueError):
+        return None
+
+    return Cursor(offset=offset, reverse=reverse, position=position)
+
+
+def _encode_cursor(cursor):
+    """
+    Given a Cursor instance, return an encoded string representation.
+    """
+    tokens = {}
+    if cursor.offset != 0:
+        tokens['o'] = str(cursor.offset)
+    if cursor.reverse:
+        tokens['r'] = '1'
+    if cursor.position is not None:
+        tokens['p'] = cursor.position
+
+    querystring = urlparse.urlencode(tokens, doseq=True)
+    return b64encode(querystring.encode('ascii')).decode('ascii')
+
+
+def _reverse_ordering(ordering_tuple):
+    """
+    Given an order_by tuple such as `('-created', 'uuid')` reverse the
+    ordering and return a new tuple, eg. `('created', '-uuid')`.
+    """
+    invert = lambda x: x[1:] if (x.startswith('-')) else '-' + x
+    return tuple([invert(item) for item in ordering_tuple])
+
+
+Cursor = namedtuple('Cursor', ['offset', 'reverse', 'position'])
 PageLink = namedtuple('PageLink', ['url', 'number', 'is_active', 'is_break'])
 
 PAGE_BREAK = PageLink(url=None, number=None, is_active=False, is_break=True)
@@ -168,6 +218,8 @@ class PageNumberPagination(BasePagination):
 
     template = 'rest_framework/pagination/numbers.html'
 
+    invalid_page_message = _('Invalid page "{page_number}": {message}.')
+
     def _handle_backwards_compat(self, view):
         """
         Prior to version 3.1, pagination was handled in the view, and the
@@ -200,7 +252,7 @@ class PageNumberPagination(BasePagination):
         try:
             self.page = paginator.page(page_number)
         except InvalidPage as exc:
-            msg = _('Invalid page "{page_number}": {message}.').format(
+            msg = self.invalid_page_message.format(
                 page_number=page_number, message=six.text_type(exc)
             )
             raise NotFound(msg)
@@ -223,8 +275,9 @@ class PageNumberPagination(BasePagination):
     def get_page_size(self, request):
         if self.paginate_by_param:
             try:
-                return _strict_positive_int(
+                return _positive_int(
                     request.query_params[self.paginate_by_param],
+                    strict=True,
                     cutoff=self.max_paginate_by
                 )
             except (KeyError, ValueError):
@@ -307,7 +360,7 @@ class LimitOffsetPagination(BasePagination):
     def get_limit(self, request):
         if self.limit_query_param:
             try:
-                return _strict_positive_int(
+                return _positive_int(
                     request.query_params[self.limit_query_param],
                     cutoff=self.max_limit
                 )
@@ -318,7 +371,7 @@ class LimitOffsetPagination(BasePagination):
 
     def get_offset(self, request):
         try:
-            return _strict_positive_int(
+            return _positive_int(
                 request.query_params[self.offset_query_param],
             )
         except (KeyError, ValueError):
@@ -377,3 +430,253 @@ class LimitOffsetPagination(BasePagination):
         template = loader.get_template(self.template)
         context = Context(self.get_html_context())
         return template.render(context)
+
+
+class CursorPagination(BasePagination):
+    # Determine how/if True, False and None positions work - do the string
+    # encodings work with Django queryset filters?
+    # Consider a max offset cap.
+    # Tidy up the `get_ordering` API (eg remove queryset from it)
+    cursor_query_param = 'cursor'
+    page_size = api_settings.PAGINATE_BY
+    invalid_cursor_message = _('Invalid cursor')
+    ordering = None
+    template = 'rest_framework/pagination/previous_and_next.html'
+
+    def paginate_queryset(self, queryset, request, view=None):
+        self.base_url = request.build_absolute_uri()
+        self.ordering = self.get_ordering(request, queryset, view)
+
+        # Determine if we have a cursor, and if so then decode it.
+        encoded = request.query_params.get(self.cursor_query_param)
+        if encoded is None:
+            self.cursor = None
+            (offset, reverse, current_position) = (0, False, None)
+        else:
+            self.cursor = _decode_cursor(encoded)
+            if self.cursor is None:
+                raise NotFound(self.invalid_cursor_message)
+            (offset, reverse, current_position) = self.cursor
+
+        # Cursor pagination always enforces an ordering.
+        if reverse:
+            queryset = queryset.order_by(*_reverse_ordering(self.ordering))
+        else:
+            queryset = queryset.order_by(*self.ordering)
+
+        # If we have a cursor with a fixed position then filter by that.
+        if current_position is not None:
+            order = self.ordering[0]
+            is_reversed = order.startswith('-')
+            order_attr = order.lstrip('-')
+
+            # Test for: (cursor reversed) XOR (queryset reversed)
+            if self.cursor.reverse != is_reversed:
+                kwargs = {order_attr + '__lt': current_position}
+            else:
+                kwargs = {order_attr + '__gt': current_position}
+
+            queryset = queryset.filter(**kwargs)
+
+        # If we have an offset cursor then offset the entire page by that amount.
+        # We also always fetch an extra item in order to determine if there is a
+        # page following on from this one.
+        results = list(queryset[offset:offset + self.page_size + 1])
+        self.page = results[:self.page_size]
+
+        # Determine the position of the final item following the page.
+        if len(results) > len(self.page):
+            has_following_postion = True
+            following_position = self._get_position_from_instance(results[-1], self.ordering)
+        else:
+            has_following_postion = False
+            following_position = None
+
+        # If we have a reverse queryset, then the query ordering was in reverse
+        # so we need to reverse the items again before returning them to the user.
+        if reverse:
+            self.page = list(reversed(self.page))
+
+        if reverse:
+            # Determine next and previous positions for reverse cursors.
+            self.has_next = (current_position is not None) or (offset > 0)
+            self.has_previous = has_following_postion
+            if self.has_next:
+                self.next_position = current_position
+            if self.has_previous:
+                self.previous_position = following_position
+        else:
+            # Determine next and previous positions for forward cursors.
+            self.has_next = has_following_postion
+            self.has_previous = (current_position is not None) or (offset > 0)
+            if self.has_next:
+                self.next_position = following_position
+            if self.has_previous:
+                self.previous_position = current_position
+
+        # Display page controls in the browsable API if there is more
+        # than one page.
+        if self.has_previous or self.has_next:
+            self.display_page_controls = True
+
+        return self.page
+
+    def get_next_link(self):
+        if not self.has_next:
+            return None
+
+        if self.cursor and self.cursor.reverse and self.cursor.offset != 0:
+            # If we're reversing direction and we have an offset cursor
+            # then we cannot use the first position we find as a marker.
+            compare = self._get_position_from_instance(self.page[-1], self.ordering)
+        else:
+            compare = self.next_position
+        offset = 0
+
+        for item in reversed(self.page):
+            position = self._get_position_from_instance(item, self.ordering)
+            if position != compare:
+                # The item in this position and the item following it
+                # have different positions. We can use this position as
+                # our marker.
+                break
+
+            # The item in this postion has the same position as the item
+            # following it, we can't use it as a marker position, so increment
+            # the offset and keep seeking to the previous item.
+            compare = position
+            offset += 1
+
+        else:
+            # There were no unique positions in the page.
+            if not self.has_previous:
+                # We are on the first page.
+                # Our cursor will have an offset equal to the page size,
+                # but no position to filter against yet.
+                offset = self.page_size
+                position = None
+            elif self.cursor.reverse:
+                # The change in direction will introduce a paging artifact,
+                # where we end up skipping forward a few extra items.
+                offset = 0
+                position = self.previous_position
+            else:
+                # Use the position from the existing cursor and increment
+                # it's offset by the page size.
+                offset = self.cursor.offset + self.page_size
+                position = self.previous_position
+
+        cursor = Cursor(offset=offset, reverse=False, position=position)
+        encoded = _encode_cursor(cursor)
+        return replace_query_param(self.base_url, self.cursor_query_param, encoded)
+
+    def get_previous_link(self):
+        if not self.has_previous:
+            return None
+
+        if self.cursor and not self.cursor.reverse and self.cursor.offset != 0:
+            # If we're reversing direction and we have an offset cursor
+            # then we cannot use the first position we find as a marker.
+            compare = self._get_position_from_instance(self.page[0], self.ordering)
+        else:
+            compare = self.previous_position
+        offset = 0
+
+        for item in self.page:
+            position = self._get_position_from_instance(item, self.ordering)
+            if position != compare:
+                # The item in this position and the item following it
+                # have different positions. We can use this position as
+                # our marker.
+                break
+
+            # The item in this postion has the same position as the item
+            # following it, we can't use it as a marker position, so increment
+            # the offset and keep seeking to the previous item.
+            compare = position
+            offset += 1
+
+        else:
+            # There were no unique positions in the page.
+            if not self.has_next:
+                # We are on the final page.
+                # Our cursor will have an offset equal to the page size,
+                # but no position to filter against yet.
+                offset = self.page_size
+                position = None
+            elif self.cursor.reverse:
+                # Use the position from the existing cursor and increment
+                # it's offset by the page size.
+                offset = self.cursor.offset + self.page_size
+                position = self.next_position
+            else:
+                # The change in direction will introduce a paging artifact,
+                # where we end up skipping back a few extra items.
+                offset = 0
+                position = self.next_position
+
+        cursor = Cursor(offset=offset, reverse=True, position=position)
+        encoded = _encode_cursor(cursor)
+        return replace_query_param(self.base_url, self.cursor_query_param, encoded)
+
+    def get_ordering(self, request, queryset, view):
+        """
+        Return a tuple of strings, that may be used in an `order_by` method.
+        """
+        ordering_filters = [
+            filter_cls for filter_cls in getattr(view, 'filter_backends', [])
+            if hasattr(filter_cls, 'get_ordering')
+        ]
+
+        if ordering_filters:
+            # If a filter exists on the view that implements `get_ordering`
+            # then we defer to that filter to determine the ordering.
+            filter_cls = ordering_filters[0]
+            filter_instance = filter_cls()
+            ordering = filter_instance.get_ordering(request, queryset, view)
+            assert ordering is not None, (
+                'Using cursor pagination, but filter class {filter_cls} '
+                'returned a `None` ordering.'.format(
+                    filter_cls=filter_cls.__name__
+                )
+            )
+        else:
+            # The default case is to check for an `ordering` attribute,
+            # first on the view instance, and then on this pagination instance.
+            ordering = getattr(view, 'ordering', getattr(self, 'ordering', None))
+            assert ordering is not None, (
+                'Using cursor pagination, but no ordering attribute was declared '
+                'on the view or on the pagination class.'
+            )
+
+        assert isinstance(ordering, (six.string_types, list, tuple)), (
+            'Invalid ordering. Expected string or tuple, but got {type}'.format(
+                type=type(ordering).__name__
+            )
+        )
+
+        if isinstance(ordering, six.string_types):
+            return (ordering,)
+        return tuple(ordering)
+
+    def _get_position_from_instance(self, instance, ordering):
+        attr = getattr(instance, ordering[0].lstrip('-'))
+        return six.text_type(attr)
+
+    def get_paginated_response(self, data):
+        return Response(OrderedDict([
+            ('next', self.get_next_link()),
+            ('previous', self.get_previous_link()),
+            ('results', data)
+        ]))
+
+    def get_html_context(self):
+        return {
+            'previous_url': self.get_previous_link(),
+            'next_url': self.get_next_link()
+        }
+
+    def to_html(self):
+        template = loader.get_template(self.template)
+        context = Context(self.get_html_context())
+        return template.render(context)
diff --git a/rest_framework/static/rest_framework/css/bootstrap-tweaks.css b/rest_framework/static/rest_framework/css/bootstrap-tweaks.css
index 15b42178..04f12ed3 100644
--- a/rest_framework/static/rest_framework/css/bootstrap-tweaks.css
+++ b/rest_framework/static/rest_framework/css/bootstrap-tweaks.css
@@ -63,10 +63,20 @@ a single block in the template.
 .pagination>.disabled>a,
 .pagination>.disabled>a:hover,
 .pagination>.disabled>a:focus {
-  cursor: default;
+  cursor: not-allowed;
   pointer-events: none;
 }
 
+.pager>.disabled>a,
+.pager>.disabled>a:hover,
+.pager>.disabled>a:focus {
+  pointer-events: none;
+}
+
+.pager .next {
+  margin-left: 10px;
+}
+
 /*=== dabapps bootstrap styles ====*/
 
 html {
diff --git a/rest_framework/templates/rest_framework/pagination/previous_and_next.html b/rest_framework/templates/rest_framework/pagination/previous_and_next.html
new file mode 100644
index 00000000..eacbfff4
--- /dev/null
+++ b/rest_framework/templates/rest_framework/pagination/previous_and_next.html
@@ -0,0 +1,12 @@
+<ul class="pager">
+{% if previous_url %}
+    <li class="previous"><a href="{{ previous_url }}">&laquo; Previous</a></li>
+{% else %}
+    <li class="previous disabled"><a href="#">&laquo; Previous</a></li>
+{% endif %}
+{% if next_url %}
+    <li class="next"><a href="{{ next_url }}">Next &raquo;</a></li>
+{% else %}
+    <li class="next disabled"><a href="#">Next &raquo;</li>
+{% endif %}
+</ul>