Resolve merge conflictmodel-serializer-caching

1 files changed, 648 insertions, 49 deletions

diff --git a/rest_framework/pagination.py b/rest_framework/pagination.py
index fb451285..b3658aca 100644
--- a/rest_framework/pagination.py
+++ b/rest_framework/pagination.py
@@ -1,83 +1,682 @@
+# coding: utf-8
 """
 Pagination serializers determine the structure of the output that should
 be used for paginated responses.
 """
 from __future__ import unicode_literals
-from rest_framework import serializers
-from rest_framework.templatetags.rest_framework import replace_query_param
+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
+from rest_framework.response import Response
+from rest_framework.settings import api_settings
+from rest_framework.utils.urls import (
+    replace_query_param, remove_query_param
+)
 
 
-class NextPageField(serializers.Field):
+def _positive_int(integer_string, strict=False, cutoff=None):
     """
-    Field that returns a link to the next page in paginated results.
+    Cast a string to a strictly positive integer.
     """
-    page_field = 'page'
+    ret = int(integer_string)
+    if ret < 0 or (ret == 0 and strict):
+        raise ValueError()
+    if cutoff:
+        ret = min(ret, cutoff)
+    return ret
 
-    def to_representation(self, value):
-        if not value.has_next():
-            return None
-        page = value.next_page_number()
-        request = self.context.get('request')
-        url = request and request.build_absolute_uri() or ''
-        return replace_query_param(url, self.page_field, page)
+
+def _divide_with_ceil(a, b):
+    """
+    Returns 'a' divded by 'b', with any remainder rounded up.
+    """
+    if a % b:
+        return (a // b) + 1
+    return a // b
 
 
-class PreviousPageField(serializers.Field):
+def _get_count(queryset):
     """
-    Field that returns a link to the previous page in paginated results.
+    Determine an object count, supporting either querysets or regular lists.
     """
-    page_field = 'page'
+    try:
+        return queryset.count()
+    except (AttributeError, TypeError):
+        return len(queryset)
 
-    def to_representation(self, value):
-        if not value.has_previous():
-            return None
-        page = value.previous_page_number()
-        request = self.context.get('request')
-        url = request and request.build_absolute_uri() or ''
-        return replace_query_param(url, self.page_field, page)
+
+def _get_displayed_page_numbers(current, final):
+    """
+    This utility function determines a list of page numbers to display.
+    This gives us a nice contextually relevant set of page numbers.
+
+    For example:
+    current=14, final=16 -> [1, None, 13, 14, 15, 16]
+
+    This implementation gives one page to each side of the cursor,
+    or two pages to the side when the cursor is at the edge, then
+    ensures that any breaks between non-continous page numbers never
+    remove only a single page.
+
+    For an alernativative implementation which gives two pages to each side of
+    the cursor, eg. as in GitHub issue list pagination, see:
+
+    https://gist.github.com/tomchristie/321140cebb1c4a558b15
+    """
+    assert current >= 1
+    assert final >= current
+
+    if final <= 5:
+        return list(range(1, final + 1))
+
+    # We always include the first two pages, last two pages, and
+    # two pages either side of the current page.
+    included = set((
+        1,
+        current - 1, current, current + 1,
+        final
+    ))
+
+    # If the break would only exclude a single page number then we
+    # may as well include the page number instead of the break.
+    if current <= 4:
+        included.add(2)
+        included.add(3)
+    if current >= final - 3:
+        included.add(final - 1)
+        included.add(final - 2)
+
+    # Now sort the page numbers and drop anything outside the limits.
+    included = [
+        idx for idx in sorted(list(included))
+        if idx > 0 and idx <= final
+    ]
+
+    # Finally insert any `...` breaks
+    if current > 4:
+        included.insert(1, None)
+    if current < final - 3:
+        included.insert(len(included) - 1, None)
+    return included
+
+
+def _get_page_links(page_numbers, current, url_func):
+    """
+    Given a list of page numbers and `None` page breaks,
+    return a list of `PageLink` objects.
+    """
+    page_links = []
+    for page_number in page_numbers:
+        if page_number is None:
+            page_link = PAGE_BREAK
+        else:
+            page_link = PageLink(
+                url=url_func(page_number),
+                number=page_number,
+                is_active=(page_number == current),
+                is_break=False
+            )
+        page_links.append(page_link)
+    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')
 
 
-class DefaultObjectSerializer(serializers.ReadOnlyField):
+def _reverse_ordering(ordering_tuple):
     """
-    If no object serializer is specified, then this serializer will be applied
-    as the default.
+    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)
+
+
+class BasePagination(object):
+    display_page_controls = False
+
+    def paginate_queryset(self, queryset, request, view=None):  # pragma: no cover
+        raise NotImplementedError('paginate_queryset() must be implemented.')
 
-    def __init__(self, source=None, many=None, context=None):
-        # Note: Swallow context and many kwargs - only required for
-        # eg. ModelSerializer.
-        super(DefaultObjectSerializer, self).__init__(source=source)
+    def get_paginated_response(self, data):  # pragma: no cover
+        raise NotImplementedError('get_paginated_response() must be implemented.')
 
+    def to_html(self):  # pragma: no cover
+        raise NotImplementedError('to_html() must be implemented to display page controls.')
 
-class BasePaginationSerializer(serializers.Serializer):
+
+class PageNumberPagination(BasePagination):
     """
-    A base class for pagination serializers to inherit from,
-    to make implementing custom serializers more easy.
+    A simple page number based style that supports page numbers as
+    query parameters. For example:
+
+    http://api.example.org/accounts/?page=4
+    http://api.example.org/accounts/?page=4&page_size=100
     """
-    results_field = 'results'
+    # The default page size.
+    # Defaults to `None`, meaning pagination is disabled.
+    paginate_by = api_settings.PAGINATE_BY
+
+    # Client can control the page using this query parameter.
+    page_query_param = 'page'
+
+    # Client can control the page size using this query parameter.
+    # Default is 'None'. Set to eg 'page_size' to enable usage.
+    paginate_by_param = api_settings.PAGINATE_BY_PARAM
+
+    # Set to an integer to limit the maximum page size the client may request.
+    # Only relevant if 'paginate_by_param' has also been set.
+    max_paginate_by = api_settings.MAX_PAGINATE_BY
+
+    last_page_strings = ('last',)
+
+    template = 'rest_framework/pagination/numbers.html'
+
+    invalid_page_message = _('Invalid page "{page_number}": {message}.')
 
-    def __init__(self, *args, **kwargs):
+    def _handle_backwards_compat(self, view):
         """
-        Override init to add in the object serializer field on-the-fly.
+        Prior to version 3.1, pagination was handled in the view, and the
+        attributes were set there. The attributes should now be set on
+        the pagination class, but the old style is still pending deprecation.
         """
-        super(BasePaginationSerializer, self).__init__(*args, **kwargs)
-        results_field = self.results_field
+        for attr in (
+            'paginate_by', 'page_query_param',
+            'paginate_by_param', 'max_paginate_by'
+        ):
+            if hasattr(view, attr):
+                setattr(self, attr, getattr(view, attr))
+
+    def paginate_queryset(self, queryset, request, view=None):
+        """
+        Paginate a queryset if required, either returning a
+        page object, or `None` if pagination is not configured for this view.
+        """
+        self._handle_backwards_compat(view)
+
+        page_size = self.get_page_size(request)
+        if not page_size:
+            return None
+
+        paginator = DjangoPaginator(queryset, page_size)
+        page_number = request.query_params.get(self.page_query_param, 1)
+        if page_number in self.last_page_strings:
+            page_number = paginator.num_pages
 
         try:
-            object_serializer = self.Meta.object_serializer_class
-        except AttributeError:
-            object_serializer = DefaultObjectSerializer
+            self.page = paginator.page(page_number)
+        except InvalidPage as exc:
+            msg = self.invalid_page_message.format(
+                page_number=page_number, message=six.text_type(exc)
+            )
+            raise NotFound(msg)
 
-        self.fields[results_field] = serializers.ListSerializer(
-            child=object_serializer(),
-            source='object_list'
-        )
+        if paginator.count > 1:
+            # The browsable API should display pagination controls.
+            self.display_page_controls = True
+
+        self.request = request
+        return self.page
+
+    def get_paginated_response(self, data):
+        return Response(OrderedDict([
+            ('count', self.page.paginator.count),
+            ('next', self.get_next_link()),
+            ('previous', self.get_previous_link()),
+            ('results', data)
+        ]))
+
+    def get_page_size(self, request):
+        if self.paginate_by_param:
+            try:
+                return _positive_int(
+                    request.query_params[self.paginate_by_param],
+                    strict=True,
+                    cutoff=self.max_paginate_by
+                )
+            except (KeyError, ValueError):
+                pass
+
+        return self.paginate_by
+
+    def get_next_link(self):
+        if not self.page.has_next():
+            return None
+        url = self.request.build_absolute_uri()
+        page_number = self.page.next_page_number()
+        return replace_query_param(url, self.page_query_param, page_number)
+
+    def get_previous_link(self):
+        if not self.page.has_previous():
+            return None
+        url = self.request.build_absolute_uri()
+        page_number = self.page.previous_page_number()
+        if page_number == 1:
+            return remove_query_param(url, self.page_query_param)
+        return replace_query_param(url, self.page_query_param, page_number)
+
+    def get_html_context(self):
+        base_url = self.request.build_absolute_uri()
 
+        def page_number_to_url(page_number):
+            if page_number == 1:
+                return remove_query_param(base_url, self.page_query_param)
+            else:
+                return replace_query_param(base_url, self.page_query_param, page_number)
 
-class PaginationSerializer(BasePaginationSerializer):
+        current = self.page.number
+        final = self.page.paginator.num_pages
+        page_numbers = _get_displayed_page_numbers(current, final)
+        page_links = _get_page_links(page_numbers, current, page_number_to_url)
+
+        return {
+            'previous_url': self.get_previous_link(),
+            'next_url': self.get_next_link(),
+            'page_links': page_links
+        }
+
+    def to_html(self):
+        template = loader.get_template(self.template)
+        context = Context(self.get_html_context())
+        return template.render(context)
+
+
+class LimitOffsetPagination(BasePagination):
     """
-    A default implementation of a pagination serializer.
+    A limit/offset based style. For example:
+
+    http://api.example.org/accounts/?limit=100
+    http://api.example.org/accounts/?offset=400&limit=100
     """
-    count = serializers.ReadOnlyField(source='paginator.count')
-    next = NextPageField(source='*')
-    previous = PreviousPageField(source='*')
+    default_limit = api_settings.PAGINATE_BY
+    limit_query_param = 'limit'
+    offset_query_param = 'offset'
+    max_limit = None
+    template = 'rest_framework/pagination/numbers.html'
+
+    def paginate_queryset(self, queryset, request, view=None):
+        self.limit = self.get_limit(request)
+        self.offset = self.get_offset(request)
+        self.count = _get_count(queryset)
+        self.request = request
+        if self.count > self.limit:
+            self.display_page_controls = True
+        return queryset[self.offset:self.offset + self.limit]
+
+    def get_paginated_response(self, data):
+        return Response(OrderedDict([
+            ('count', self.count),
+            ('next', self.get_next_link()),
+            ('previous', self.get_previous_link()),
+            ('results', data)
+        ]))
+
+    def get_limit(self, request):
+        if self.limit_query_param:
+            try:
+                return _positive_int(
+                    request.query_params[self.limit_query_param],
+                    cutoff=self.max_limit
+                )
+            except (KeyError, ValueError):
+                pass
+
+        return self.default_limit
+
+    def get_offset(self, request):
+        try:
+            return _positive_int(
+                request.query_params[self.offset_query_param],
+            )
+        except (KeyError, ValueError):
+            return 0
+
+    def get_next_link(self):
+        if self.offset + self.limit >= self.count:
+            return None
+
+        url = self.request.build_absolute_uri()
+        offset = self.offset + self.limit
+        return replace_query_param(url, self.offset_query_param, offset)
+
+    def get_previous_link(self):
+        if self.offset <= 0:
+            return None
+
+        url = self.request.build_absolute_uri()
+
+        if self.offset - self.limit <= 0:
+            return remove_query_param(url, self.offset_query_param)
+
+        offset = self.offset - self.limit
+        return replace_query_param(url, self.offset_query_param, offset)
+
+    def get_html_context(self):
+        base_url = self.request.build_absolute_uri()
+        current = _divide_with_ceil(self.offset, self.limit) + 1
+        # The number of pages is a little bit fiddly.
+        # We need to sum both the number of pages from current offset to end
+        # plus the number of pages up to the current offset.
+        # When offset is not strictly divisible by the limit then we may
+        # end up introducing an extra page as an artifact.
+        final = (
+            _divide_with_ceil(self.count - self.offset, self.limit) +
+            _divide_with_ceil(self.offset, self.limit)
+        )
+
+        def page_number_to_url(page_number):
+            if page_number == 1:
+                return remove_query_param(base_url, self.offset_query_param)
+            else:
+                offset = self.offset + ((page_number - current) * self.limit)
+                return replace_query_param(base_url, self.offset_query_param, offset)
+
+        page_numbers = _get_displayed_page_numbers(current, final)
+        page_links = _get_page_links(page_numbers, current, page_number_to_url)
+
+        return {
+            'previous_url': self.get_previous_link(),
+            'next_url': self.get_next_link(),
+            'page_links': page_links
+        }
+
+    def to_html(self):
+        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)