pagination.py 34 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965
  1. """
  2. Pagination serializers determine the structure of the output that should
  3. be used for paginated responses.
  4. """
  5. from base64 import b64decode, b64encode
  6. from collections import OrderedDict, namedtuple
  7. from urllib import parse
  8. from django.core.paginator import InvalidPage
  9. from django.core.paginator import Paginator as DjangoPaginator
  10. from django.template import loader
  11. from django.utils.encoding import force_str
  12. from django.utils.translation import gettext_lazy as _
  13. from rest_framework.compat import coreapi, coreschema
  14. from rest_framework.exceptions import NotFound
  15. from rest_framework.response import Response
  16. from rest_framework.settings import api_settings
  17. from rest_framework.utils.urls import remove_query_param, replace_query_param
  18. def _positive_int(integer_string, strict=False, cutoff=None):
  19. """
  20. Cast a string to a strictly positive integer.
  21. """
  22. ret = int(integer_string)
  23. if ret < 0 or (ret == 0 and strict):
  24. raise ValueError()
  25. if cutoff:
  26. return min(ret, cutoff)
  27. return ret
  28. def _divide_with_ceil(a, b):
  29. """
  30. Returns 'a' divided by 'b', with any remainder rounded up.
  31. """
  32. if a % b:
  33. return (a // b) + 1
  34. return a // b
  35. def _get_displayed_page_numbers(current, final):
  36. """
  37. This utility function determines a list of page numbers to display.
  38. This gives us a nice contextually relevant set of page numbers.
  39. For example:
  40. current=14, final=16 -> [1, None, 13, 14, 15, 16]
  41. This implementation gives one page to each side of the cursor,
  42. or two pages to the side when the cursor is at the edge, then
  43. ensures that any breaks between non-continuous page numbers never
  44. remove only a single page.
  45. For an alternative implementation which gives two pages to each side of
  46. the cursor, eg. as in GitHub issue list pagination, see:
  47. https://gist.github.com/tomchristie/321140cebb1c4a558b15
  48. """
  49. assert current >= 1
  50. assert final >= current
  51. if final <= 5:
  52. return list(range(1, final + 1))
  53. # We always include the first two pages, last two pages, and
  54. # two pages either side of the current page.
  55. included = {1, current - 1, current, current + 1, final}
  56. # If the break would only exclude a single page number then we
  57. # may as well include the page number instead of the break.
  58. if current <= 4:
  59. included.add(2)
  60. included.add(3)
  61. if current >= final - 3:
  62. included.add(final - 1)
  63. included.add(final - 2)
  64. # Now sort the page numbers and drop anything outside the limits.
  65. included = [
  66. idx for idx in sorted(list(included))
  67. if 0 < idx <= final
  68. ]
  69. # Finally insert any `...` breaks
  70. if current > 4:
  71. included.insert(1, None)
  72. if current < final - 3:
  73. included.insert(len(included) - 1, None)
  74. return included
  75. def _get_page_links(page_numbers, current, url_func):
  76. """
  77. Given a list of page numbers and `None` page breaks,
  78. return a list of `PageLink` objects.
  79. """
  80. page_links = []
  81. for page_number in page_numbers:
  82. if page_number is None:
  83. page_link = PAGE_BREAK
  84. else:
  85. page_link = PageLink(
  86. url=url_func(page_number),
  87. number=page_number,
  88. is_active=(page_number == current),
  89. is_break=False
  90. )
  91. page_links.append(page_link)
  92. return page_links
  93. def _reverse_ordering(ordering_tuple):
  94. """
  95. Given an order_by tuple such as `('-created', 'uuid')` reverse the
  96. ordering and return a new tuple, eg. `('created', '-uuid')`.
  97. """
  98. def invert(x):
  99. return x[1:] if x.startswith('-') else '-' + x
  100. return tuple([invert(item) for item in ordering_tuple])
  101. Cursor = namedtuple('Cursor', ['offset', 'reverse', 'position'])
  102. PageLink = namedtuple('PageLink', ['url', 'number', 'is_active', 'is_break'])
  103. PAGE_BREAK = PageLink(url=None, number=None, is_active=False, is_break=True)
  104. class BasePagination:
  105. display_page_controls = False
  106. def paginate_queryset(self, queryset, request, view=None): # pragma: no cover
  107. raise NotImplementedError('paginate_queryset() must be implemented.')
  108. def get_paginated_response(self, data): # pragma: no cover
  109. raise NotImplementedError('get_paginated_response() must be implemented.')
  110. def get_paginated_response_schema(self, schema):
  111. return schema
  112. def to_html(self): # pragma: no cover
  113. raise NotImplementedError('to_html() must be implemented to display page controls.')
  114. def get_results(self, data):
  115. return data['results']
  116. def get_schema_fields(self, view):
  117. assert coreapi is not None, 'coreapi must be installed to use `get_schema_fields()`'
  118. return []
  119. def get_schema_operation_parameters(self, view):
  120. return []
  121. class PageNumberPagination(BasePagination):
  122. """
  123. A simple page number based style that supports page numbers as
  124. query parameters. For example:
  125. http://api.example.org/accounts/?page=4
  126. http://api.example.org/accounts/?page=4&page_size=100
  127. """
  128. # The default page size.
  129. # Defaults to `None`, meaning pagination is disabled.
  130. page_size = api_settings.PAGE_SIZE
  131. django_paginator_class = DjangoPaginator
  132. # Client can control the page using this query parameter.
  133. page_query_param = 'page'
  134. page_query_description = _('A page number within the paginated result set.')
  135. # Client can control the page size using this query parameter.
  136. # Default is 'None'. Set to eg 'page_size' to enable usage.
  137. page_size_query_param = None
  138. page_size_query_description = _('Number of results to return per page.')
  139. # Set to an integer to limit the maximum page size the client may request.
  140. # Only relevant if 'page_size_query_param' has also been set.
  141. max_page_size = None
  142. last_page_strings = ('last',)
  143. template = 'rest_framework/pagination/numbers.html'
  144. invalid_page_message = _('Invalid page.')
  145. def paginate_queryset(self, queryset, request, view=None):
  146. """
  147. Paginate a queryset if required, either returning a
  148. page object, or `None` if pagination is not configured for this view.
  149. """
  150. page_size = self.get_page_size(request)
  151. if not page_size:
  152. return None
  153. paginator = self.django_paginator_class(queryset, page_size)
  154. page_number = request.query_params.get(self.page_query_param, 1)
  155. if page_number in self.last_page_strings:
  156. page_number = paginator.num_pages
  157. try:
  158. self.page = paginator.page(page_number)
  159. except InvalidPage as exc:
  160. msg = self.invalid_page_message.format(
  161. page_number=page_number, message=str(exc)
  162. )
  163. raise NotFound(msg)
  164. if paginator.num_pages > 1 and self.template is not None:
  165. # The browsable API should display pagination controls.
  166. self.display_page_controls = True
  167. self.request = request
  168. return list(self.page)
  169. def get_paginated_response(self, data):
  170. return Response(OrderedDict([
  171. ('count', self.page.paginator.count),
  172. ('next', self.get_next_link()),
  173. ('previous', self.get_previous_link()),
  174. ('results', data)
  175. ]))
  176. def get_paginated_response_schema(self, schema):
  177. return {
  178. 'type': 'object',
  179. 'properties': {
  180. 'count': {
  181. 'type': 'integer',
  182. 'example': 123,
  183. },
  184. 'next': {
  185. 'type': 'string',
  186. 'nullable': True,
  187. },
  188. 'previous': {
  189. 'type': 'string',
  190. 'nullable': True,
  191. },
  192. 'results': schema,
  193. },
  194. }
  195. def get_page_size(self, request):
  196. if self.page_size_query_param:
  197. try:
  198. return _positive_int(
  199. request.query_params[self.page_size_query_param],
  200. strict=True,
  201. cutoff=self.max_page_size
  202. )
  203. except (KeyError, ValueError):
  204. pass
  205. return self.page_size
  206. def get_next_link(self):
  207. if not self.page.has_next():
  208. return None
  209. url = self.request.build_absolute_uri()
  210. page_number = self.page.next_page_number()
  211. return replace_query_param(url, self.page_query_param, page_number)
  212. def get_previous_link(self):
  213. if not self.page.has_previous():
  214. return None
  215. url = self.request.build_absolute_uri()
  216. page_number = self.page.previous_page_number()
  217. if page_number == 1:
  218. return remove_query_param(url, self.page_query_param)
  219. return replace_query_param(url, self.page_query_param, page_number)
  220. def get_html_context(self):
  221. base_url = self.request.build_absolute_uri()
  222. def page_number_to_url(page_number):
  223. if page_number == 1:
  224. return remove_query_param(base_url, self.page_query_param)
  225. else:
  226. return replace_query_param(base_url, self.page_query_param, page_number)
  227. current = self.page.number
  228. final = self.page.paginator.num_pages
  229. page_numbers = _get_displayed_page_numbers(current, final)
  230. page_links = _get_page_links(page_numbers, current, page_number_to_url)
  231. return {
  232. 'previous_url': self.get_previous_link(),
  233. 'next_url': self.get_next_link(),
  234. 'page_links': page_links
  235. }
  236. def to_html(self):
  237. template = loader.get_template(self.template)
  238. context = self.get_html_context()
  239. return template.render(context)
  240. def get_schema_fields(self, view):
  241. assert coreapi is not None, 'coreapi must be installed to use `get_schema_fields()`'
  242. assert coreschema is not None, 'coreschema must be installed to use `get_schema_fields()`'
  243. fields = [
  244. coreapi.Field(
  245. name=self.page_query_param,
  246. required=False,
  247. location='query',
  248. schema=coreschema.Integer(
  249. title='Page',
  250. description=force_str(self.page_query_description)
  251. )
  252. )
  253. ]
  254. if self.page_size_query_param is not None:
  255. fields.append(
  256. coreapi.Field(
  257. name=self.page_size_query_param,
  258. required=False,
  259. location='query',
  260. schema=coreschema.Integer(
  261. title='Page size',
  262. description=force_str(self.page_size_query_description)
  263. )
  264. )
  265. )
  266. return fields
  267. def get_schema_operation_parameters(self, view):
  268. parameters = [
  269. {
  270. 'name': self.page_query_param,
  271. 'required': False,
  272. 'in': 'query',
  273. 'description': force_str(self.page_query_description),
  274. 'schema': {
  275. 'type': 'integer',
  276. },
  277. },
  278. ]
  279. if self.page_size_query_param is not None:
  280. parameters.append(
  281. {
  282. 'name': self.page_size_query_param,
  283. 'required': False,
  284. 'in': 'query',
  285. 'description': force_str(self.page_size_query_description),
  286. 'schema': {
  287. 'type': 'integer',
  288. },
  289. },
  290. )
  291. return parameters
  292. class LimitOffsetPagination(BasePagination):
  293. """
  294. A limit/offset based style. For example:
  295. http://api.example.org/accounts/?limit=100
  296. http://api.example.org/accounts/?offset=400&limit=100
  297. """
  298. default_limit = api_settings.PAGE_SIZE
  299. limit_query_param = 'limit'
  300. limit_query_description = _('Number of results to return per page.')
  301. offset_query_param = 'offset'
  302. offset_query_description = _('The initial index from which to return the results.')
  303. max_limit = None
  304. template = 'rest_framework/pagination/numbers.html'
  305. def paginate_queryset(self, queryset, request, view=None):
  306. self.count = self.get_count(queryset)
  307. self.limit = self.get_limit(request)
  308. if self.limit is None:
  309. return None
  310. self.offset = self.get_offset(request)
  311. self.request = request
  312. if self.count > self.limit and self.template is not None:
  313. self.display_page_controls = True
  314. if self.count == 0 or self.offset > self.count:
  315. return []
  316. return list(queryset[self.offset:self.offset + self.limit])
  317. def get_paginated_response(self, data):
  318. return Response(OrderedDict([
  319. ('count', self.count),
  320. ('next', self.get_next_link()),
  321. ('previous', self.get_previous_link()),
  322. ('results', data)
  323. ]))
  324. def get_paginated_response_schema(self, schema):
  325. return {
  326. 'type': 'object',
  327. 'properties': {
  328. 'count': {
  329. 'type': 'integer',
  330. 'example': 123,
  331. },
  332. 'next': {
  333. 'type': 'string',
  334. 'nullable': True,
  335. },
  336. 'previous': {
  337. 'type': 'string',
  338. 'nullable': True,
  339. },
  340. 'results': schema,
  341. },
  342. }
  343. def get_limit(self, request):
  344. if self.limit_query_param:
  345. try:
  346. return _positive_int(
  347. request.query_params[self.limit_query_param],
  348. strict=True,
  349. cutoff=self.max_limit
  350. )
  351. except (KeyError, ValueError):
  352. pass
  353. return self.default_limit
  354. def get_offset(self, request):
  355. try:
  356. return _positive_int(
  357. request.query_params[self.offset_query_param],
  358. )
  359. except (KeyError, ValueError):
  360. return 0
  361. def get_next_link(self):
  362. if self.offset + self.limit >= self.count:
  363. return None
  364. url = self.request.build_absolute_uri()
  365. url = replace_query_param(url, self.limit_query_param, self.limit)
  366. offset = self.offset + self.limit
  367. return replace_query_param(url, self.offset_query_param, offset)
  368. def get_previous_link(self):
  369. if self.offset <= 0:
  370. return None
  371. url = self.request.build_absolute_uri()
  372. url = replace_query_param(url, self.limit_query_param, self.limit)
  373. if self.offset - self.limit <= 0:
  374. return remove_query_param(url, self.offset_query_param)
  375. offset = self.offset - self.limit
  376. return replace_query_param(url, self.offset_query_param, offset)
  377. def get_html_context(self):
  378. base_url = self.request.build_absolute_uri()
  379. if self.limit:
  380. current = _divide_with_ceil(self.offset, self.limit) + 1
  381. # The number of pages is a little bit fiddly.
  382. # We need to sum both the number of pages from current offset to end
  383. # plus the number of pages up to the current offset.
  384. # When offset is not strictly divisible by the limit then we may
  385. # end up introducing an extra page as an artifact.
  386. final = (
  387. _divide_with_ceil(self.count - self.offset, self.limit) +
  388. _divide_with_ceil(self.offset, self.limit)
  389. )
  390. if final < 1:
  391. final = 1
  392. else:
  393. current = 1
  394. final = 1
  395. if current > final:
  396. current = final
  397. def page_number_to_url(page_number):
  398. if page_number == 1:
  399. return remove_query_param(base_url, self.offset_query_param)
  400. else:
  401. offset = self.offset + ((page_number - current) * self.limit)
  402. return replace_query_param(base_url, self.offset_query_param, offset)
  403. page_numbers = _get_displayed_page_numbers(current, final)
  404. page_links = _get_page_links(page_numbers, current, page_number_to_url)
  405. return {
  406. 'previous_url': self.get_previous_link(),
  407. 'next_url': self.get_next_link(),
  408. 'page_links': page_links
  409. }
  410. def to_html(self):
  411. template = loader.get_template(self.template)
  412. context = self.get_html_context()
  413. return template.render(context)
  414. def get_count(self, queryset):
  415. """
  416. Determine an object count, supporting either querysets or regular lists.
  417. """
  418. try:
  419. return queryset.count()
  420. except (AttributeError, TypeError):
  421. return len(queryset)
  422. def get_schema_fields(self, view):
  423. assert coreapi is not None, 'coreapi must be installed to use `get_schema_fields()`'
  424. assert coreschema is not None, 'coreschema must be installed to use `get_schema_fields()`'
  425. return [
  426. coreapi.Field(
  427. name=self.limit_query_param,
  428. required=False,
  429. location='query',
  430. schema=coreschema.Integer(
  431. title='Limit',
  432. description=force_str(self.limit_query_description)
  433. )
  434. ),
  435. coreapi.Field(
  436. name=self.offset_query_param,
  437. required=False,
  438. location='query',
  439. schema=coreschema.Integer(
  440. title='Offset',
  441. description=force_str(self.offset_query_description)
  442. )
  443. )
  444. ]
  445. def get_schema_operation_parameters(self, view):
  446. parameters = [
  447. {
  448. 'name': self.limit_query_param,
  449. 'required': False,
  450. 'in': 'query',
  451. 'description': force_str(self.limit_query_description),
  452. 'schema': {
  453. 'type': 'integer',
  454. },
  455. },
  456. {
  457. 'name': self.offset_query_param,
  458. 'required': False,
  459. 'in': 'query',
  460. 'description': force_str(self.offset_query_description),
  461. 'schema': {
  462. 'type': 'integer',
  463. },
  464. },
  465. ]
  466. return parameters
  467. class CursorPagination(BasePagination):
  468. """
  469. The cursor pagination implementation is necessarily complex.
  470. For an overview of the position/offset style we use, see this post:
  471. https://cra.mr/2011/03/08/building-cursors-for-the-disqus-api
  472. """
  473. cursor_query_param = 'cursor'
  474. cursor_query_description = _('The pagination cursor value.')
  475. page_size = api_settings.PAGE_SIZE
  476. invalid_cursor_message = _('Invalid cursor')
  477. ordering = '-created'
  478. template = 'rest_framework/pagination/previous_and_next.html'
  479. # Client can control the page size using this query parameter.
  480. # Default is 'None'. Set to eg 'page_size' to enable usage.
  481. page_size_query_param = None
  482. page_size_query_description = _('Number of results to return per page.')
  483. # Set to an integer to limit the maximum page size the client may request.
  484. # Only relevant if 'page_size_query_param' has also been set.
  485. max_page_size = None
  486. # The offset in the cursor is used in situations where we have a
  487. # nearly-unique index. (Eg millisecond precision creation timestamps)
  488. # We guard against malicious users attempting to cause expensive database
  489. # queries, by having a hard cap on the maximum possible size of the offset.
  490. offset_cutoff = 1000
  491. def paginate_queryset(self, queryset, request, view=None):
  492. self.page_size = self.get_page_size(request)
  493. if not self.page_size:
  494. return None
  495. self.base_url = request.build_absolute_uri()
  496. self.ordering = self.get_ordering(request, queryset, view)
  497. self.cursor = self.decode_cursor(request)
  498. if self.cursor is None:
  499. (offset, reverse, current_position) = (0, False, None)
  500. else:
  501. (offset, reverse, current_position) = self.cursor
  502. # Cursor pagination always enforces an ordering.
  503. if reverse:
  504. queryset = queryset.order_by(*_reverse_ordering(self.ordering))
  505. else:
  506. queryset = queryset.order_by(*self.ordering)
  507. # If we have a cursor with a fixed position then filter by that.
  508. if current_position is not None:
  509. order = self.ordering[0]
  510. is_reversed = order.startswith('-')
  511. order_attr = order.lstrip('-')
  512. # Test for: (cursor reversed) XOR (queryset reversed)
  513. if self.cursor.reverse != is_reversed:
  514. kwargs = {order_attr + '__lt': current_position}
  515. else:
  516. kwargs = {order_attr + '__gt': current_position}
  517. queryset = queryset.filter(**kwargs)
  518. # If we have an offset cursor then offset the entire page by that amount.
  519. # We also always fetch an extra item in order to determine if there is a
  520. # page following on from this one.
  521. results = list(queryset[offset:offset + self.page_size + 1])
  522. self.page = list(results[:self.page_size])
  523. # Determine the position of the final item following the page.
  524. if len(results) > len(self.page):
  525. has_following_position = True
  526. following_position = self._get_position_from_instance(results[-1], self.ordering)
  527. else:
  528. has_following_position = False
  529. following_position = None
  530. if reverse:
  531. # If we have a reverse queryset, then the query ordering was in reverse
  532. # so we need to reverse the items again before returning them to the user.
  533. self.page = list(reversed(self.page))
  534. # Determine next and previous positions for reverse cursors.
  535. self.has_next = (current_position is not None) or (offset > 0)
  536. self.has_previous = has_following_position
  537. if self.has_next:
  538. self.next_position = current_position
  539. if self.has_previous:
  540. self.previous_position = following_position
  541. else:
  542. # Determine next and previous positions for forward cursors.
  543. self.has_next = has_following_position
  544. self.has_previous = (current_position is not None) or (offset > 0)
  545. if self.has_next:
  546. self.next_position = following_position
  547. if self.has_previous:
  548. self.previous_position = current_position
  549. # Display page controls in the browsable API if there is more
  550. # than one page.
  551. if (self.has_previous or self.has_next) and self.template is not None:
  552. self.display_page_controls = True
  553. return self.page
  554. def get_page_size(self, request):
  555. if self.page_size_query_param:
  556. try:
  557. return _positive_int(
  558. request.query_params[self.page_size_query_param],
  559. strict=True,
  560. cutoff=self.max_page_size
  561. )
  562. except (KeyError, ValueError):
  563. pass
  564. return self.page_size
  565. def get_next_link(self):
  566. if not self.has_next:
  567. return None
  568. if self.page and self.cursor and self.cursor.reverse and self.cursor.offset != 0:
  569. # If we're reversing direction and we have an offset cursor
  570. # then we cannot use the first position we find as a marker.
  571. compare = self._get_position_from_instance(self.page[-1], self.ordering)
  572. else:
  573. compare = self.next_position
  574. offset = 0
  575. has_item_with_unique_position = False
  576. for item in reversed(self.page):
  577. position = self._get_position_from_instance(item, self.ordering)
  578. if position != compare:
  579. # The item in this position and the item following it
  580. # have different positions. We can use this position as
  581. # our marker.
  582. has_item_with_unique_position = True
  583. break
  584. # The item in this position has the same position as the item
  585. # following it, we can't use it as a marker position, so increment
  586. # the offset and keep seeking to the previous item.
  587. compare = position
  588. offset += 1
  589. if self.page and not has_item_with_unique_position:
  590. # There were no unique positions in the page.
  591. if not self.has_previous:
  592. # We are on the first page.
  593. # Our cursor will have an offset equal to the page size,
  594. # but no position to filter against yet.
  595. offset = self.page_size
  596. position = None
  597. elif self.cursor.reverse:
  598. # The change in direction will introduce a paging artifact,
  599. # where we end up skipping forward a few extra items.
  600. offset = 0
  601. position = self.previous_position
  602. else:
  603. # Use the position from the existing cursor and increment
  604. # it's offset by the page size.
  605. offset = self.cursor.offset + self.page_size
  606. position = self.previous_position
  607. if not self.page:
  608. position = self.next_position
  609. cursor = Cursor(offset=offset, reverse=False, position=position)
  610. return self.encode_cursor(cursor)
  611. def get_previous_link(self):
  612. if not self.has_previous:
  613. return None
  614. if self.page and self.cursor and not self.cursor.reverse and self.cursor.offset != 0:
  615. # If we're reversing direction and we have an offset cursor
  616. # then we cannot use the first position we find as a marker.
  617. compare = self._get_position_from_instance(self.page[0], self.ordering)
  618. else:
  619. compare = self.previous_position
  620. offset = 0
  621. has_item_with_unique_position = False
  622. for item in self.page:
  623. position = self._get_position_from_instance(item, self.ordering)
  624. if position != compare:
  625. # The item in this position and the item following it
  626. # have different positions. We can use this position as
  627. # our marker.
  628. has_item_with_unique_position = True
  629. break
  630. # The item in this position has the same position as the item
  631. # following it, we can't use it as a marker position, so increment
  632. # the offset and keep seeking to the previous item.
  633. compare = position
  634. offset += 1
  635. if self.page and not has_item_with_unique_position:
  636. # There were no unique positions in the page.
  637. if not self.has_next:
  638. # We are on the final page.
  639. # Our cursor will have an offset equal to the page size,
  640. # but no position to filter against yet.
  641. offset = self.page_size
  642. position = None
  643. elif self.cursor.reverse:
  644. # Use the position from the existing cursor and increment
  645. # it's offset by the page size.
  646. offset = self.cursor.offset + self.page_size
  647. position = self.next_position
  648. else:
  649. # The change in direction will introduce a paging artifact,
  650. # where we end up skipping back a few extra items.
  651. offset = 0
  652. position = self.next_position
  653. if not self.page:
  654. position = self.previous_position
  655. cursor = Cursor(offset=offset, reverse=True, position=position)
  656. return self.encode_cursor(cursor)
  657. def get_ordering(self, request, queryset, view):
  658. """
  659. Return a tuple of strings, that may be used in an `order_by` method.
  660. """
  661. ordering_filters = [
  662. filter_cls for filter_cls in getattr(view, 'filter_backends', [])
  663. if hasattr(filter_cls, 'get_ordering')
  664. ]
  665. if ordering_filters:
  666. # If a filter exists on the view that implements `get_ordering`
  667. # then we defer to that filter to determine the ordering.
  668. filter_cls = ordering_filters[0]
  669. filter_instance = filter_cls()
  670. ordering = filter_instance.get_ordering(request, queryset, view)
  671. assert ordering is not None, (
  672. 'Using cursor pagination, but filter class {filter_cls} '
  673. 'returned a `None` ordering.'.format(
  674. filter_cls=filter_cls.__name__
  675. )
  676. )
  677. else:
  678. # The default case is to check for an `ordering` attribute
  679. # on this pagination instance.
  680. ordering = self.ordering
  681. assert ordering is not None, (
  682. 'Using cursor pagination, but no ordering attribute was declared '
  683. 'on the pagination class.'
  684. )
  685. assert '__' not in ordering, (
  686. 'Cursor pagination does not support double underscore lookups '
  687. 'for orderings. Orderings should be an unchanging, unique or '
  688. 'nearly-unique field on the model, such as "-created" or "pk".'
  689. )
  690. assert isinstance(ordering, (str, list, tuple)), (
  691. 'Invalid ordering. Expected string or tuple, but got {type}'.format(
  692. type=type(ordering).__name__
  693. )
  694. )
  695. if isinstance(ordering, str):
  696. return (ordering,)
  697. return tuple(ordering)
  698. def decode_cursor(self, request):
  699. """
  700. Given a request with a cursor, return a `Cursor` instance.
  701. """
  702. # Determine if we have a cursor, and if so then decode it.
  703. encoded = request.query_params.get(self.cursor_query_param)
  704. if encoded is None:
  705. return None
  706. try:
  707. querystring = b64decode(encoded.encode('ascii')).decode('ascii')
  708. tokens = parse.parse_qs(querystring, keep_blank_values=True)
  709. offset = tokens.get('o', ['0'])[0]
  710. offset = _positive_int(offset, cutoff=self.offset_cutoff)
  711. reverse = tokens.get('r', ['0'])[0]
  712. reverse = bool(int(reverse))
  713. position = tokens.get('p', [None])[0]
  714. except (TypeError, ValueError):
  715. raise NotFound(self.invalid_cursor_message)
  716. return Cursor(offset=offset, reverse=reverse, position=position)
  717. def encode_cursor(self, cursor):
  718. """
  719. Given a Cursor instance, return an url with encoded cursor.
  720. """
  721. tokens = {}
  722. if cursor.offset != 0:
  723. tokens['o'] = str(cursor.offset)
  724. if cursor.reverse:
  725. tokens['r'] = '1'
  726. if cursor.position is not None:
  727. tokens['p'] = cursor.position
  728. querystring = parse.urlencode(tokens, doseq=True)
  729. encoded = b64encode(querystring.encode('ascii')).decode('ascii')
  730. return replace_query_param(self.base_url, self.cursor_query_param, encoded)
  731. def _get_position_from_instance(self, instance, ordering):
  732. field_name = ordering[0].lstrip('-')
  733. if isinstance(instance, dict):
  734. attr = instance[field_name]
  735. else:
  736. attr = getattr(instance, field_name)
  737. return str(attr)
  738. def get_paginated_response(self, data):
  739. return Response(OrderedDict([
  740. ('next', self.get_next_link()),
  741. ('previous', self.get_previous_link()),
  742. ('results', data)
  743. ]))
  744. def get_paginated_response_schema(self, schema):
  745. return {
  746. 'type': 'object',
  747. 'properties': {
  748. 'next': {
  749. 'type': 'string',
  750. 'nullable': True,
  751. },
  752. 'previous': {
  753. 'type': 'string',
  754. 'nullable': True,
  755. },
  756. 'results': schema,
  757. },
  758. }
  759. def get_html_context(self):
  760. return {
  761. 'previous_url': self.get_previous_link(),
  762. 'next_url': self.get_next_link()
  763. }
  764. def to_html(self):
  765. template = loader.get_template(self.template)
  766. context = self.get_html_context()
  767. return template.render(context)
  768. def get_schema_fields(self, view):
  769. assert coreapi is not None, 'coreapi must be installed to use `get_schema_fields()`'
  770. assert coreschema is not None, 'coreschema must be installed to use `get_schema_fields()`'
  771. fields = [
  772. coreapi.Field(
  773. name=self.cursor_query_param,
  774. required=False,
  775. location='query',
  776. schema=coreschema.String(
  777. title='Cursor',
  778. description=force_str(self.cursor_query_description)
  779. )
  780. )
  781. ]
  782. if self.page_size_query_param is not None:
  783. fields.append(
  784. coreapi.Field(
  785. name=self.page_size_query_param,
  786. required=False,
  787. location='query',
  788. schema=coreschema.Integer(
  789. title='Page size',
  790. description=force_str(self.page_size_query_description)
  791. )
  792. )
  793. )
  794. return fields
  795. def get_schema_operation_parameters(self, view):
  796. parameters = [
  797. {
  798. 'name': self.cursor_query_param,
  799. 'required': False,
  800. 'in': 'query',
  801. 'description': force_str(self.cursor_query_description),
  802. 'schema': {
  803. 'type': 'integer',
  804. },
  805. }
  806. ]
  807. if self.page_size_query_param is not None:
  808. parameters.append(
  809. {
  810. 'name': self.page_size_query_param,
  811. 'required': False,
  812. 'in': 'query',
  813. 'description': force_str(self.page_size_query_description),
  814. 'schema': {
  815. 'type': 'integer',
  816. },
  817. }
  818. )
  819. return parameters