Coverage for /var/srv/projects/api.amasfac.comuna18.com/tmp/venv/lib/python3.9/site-packages/rest_framework/pagination.py: 22%

1""" 

2Pagination serializers determine the structure of the output that should 

3be used for paginated responses. 

4""" 

5from base64 import b64decode, b64encode 

6from collections import OrderedDict, namedtuple 

7from urllib import parse 

8 

9from django.core.paginator import InvalidPage 

10from django.core.paginator import Paginator as DjangoPaginator 

11from django.template import loader 

12from django.utils.encoding import force_str 

13from django.utils.translation import gettext_lazy as _ 

14 

15from rest_framework.compat import coreapi, coreschema 

16from rest_framework.exceptions import NotFound 

17from rest_framework.response import Response 

18from rest_framework.settings import api_settings 

19from rest_framework.utils.urls import remove_query_param, replace_query_param 

20 

21 

22def _positive_int(integer_string, strict=False, cutoff=None): 

23 """ 

24 Cast a string to a strictly positive integer. 

25 """ 

26 ret = int(integer_string) 

27 if ret < 0 or (ret == 0 and strict): 

28 raise ValueError() 

29 if cutoff: 

30 return min(ret, cutoff) 

31 return ret 

32 

33 

34def _divide_with_ceil(a, b): 

35 """ 

36 Returns 'a' divided by 'b', with any remainder rounded up. 

37 """ 

38 if a % b: 

39 return (a // b) + 1 

40 

41 return a // b 

42 

43 

44def _get_displayed_page_numbers(current, final): 

45 """ 

46 This utility function determines a list of page numbers to display. 

47 This gives us a nice contextually relevant set of page numbers. 

48 

49 For example: 

50 current=14, final=16 -> [1, None, 13, 14, 15, 16] 

51 

52 This implementation gives one page to each side of the cursor, 

53 or two pages to the side when the cursor is at the edge, then 

54 ensures that any breaks between non-continuous page numbers never 

55 remove only a single page. 

56 

57 For an alternative implementation which gives two pages to each side of 

58 the cursor, eg. as in GitHub issue list pagination, see: 

59 

60 https://gist.github.com/tomchristie/321140cebb1c4a558b15 

61 """ 

62 assert current >= 1 

63 assert final >= current 

64 

65 if final <= 5: 

66 return list(range(1, final + 1)) 

67 

68 # We always include the first two pages, last two pages, and 

69 # two pages either side of the current page. 

70 included = {1, current - 1, current, current + 1, final} 

71 

72 # If the break would only exclude a single page number then we 

73 # may as well include the page number instead of the break. 

74 if current <= 4: 

75 included.add(2) 

76 included.add(3) 

77 if current >= final - 3: 

78 included.add(final - 1) 

79 included.add(final - 2) 

80 

81 # Now sort the page numbers and drop anything outside the limits. 

82 included = [ 

83 idx for idx in sorted(included) 

84 if 0 < idx <= final 

85 ] 

86 

87 # Finally insert any `...` breaks 

88 if current > 4: 

89 included.insert(1, None) 

90 if current < final - 3: 

91 included.insert(len(included) - 1, None) 

92 return included 

93 

94 

95def _get_page_links(page_numbers, current, url_func): 

96 """ 

97 Given a list of page numbers and `None` page breaks, 

98 return a list of `PageLink` objects. 

99 """ 

100 page_links = [] 

101 for page_number in page_numbers: 

102 if page_number is None: 

103 page_link = PAGE_BREAK 

104 else: 

105 page_link = PageLink( 

106 url=url_func(page_number), 

107 number=page_number, 

108 is_active=(page_number == current), 

109 is_break=False 

110 ) 

111 page_links.append(page_link) 

112 return page_links 

113 

114 

115def _reverse_ordering(ordering_tuple): 

116 """ 

117 Given an order_by tuple such as `('-created', 'uuid')` reverse the 

118 ordering and return a new tuple, eg. `('created', '-uuid')`. 

119 """ 

120 def invert(x): 

121 return x[1:] if x.startswith('-') else '-' + x 

122 

123 return tuple([invert(item) for item in ordering_tuple]) 

124 

125 

126Cursor = namedtuple('Cursor', ['offset', 'reverse', 'position']) 

127PageLink = namedtuple('PageLink', ['url', 'number', 'is_active', 'is_break']) 

128 

129PAGE_BREAK = PageLink(url=None, number=None, is_active=False, is_break=True) 

130 

131 

132class BasePagination: 

133 display_page_controls = False 

134 

135 def paginate_queryset(self, queryset, request, view=None): # pragma: no cover 

136 raise NotImplementedError('paginate_queryset() must be implemented.') 

137 

138 def get_paginated_response(self, data): # pragma: no cover 

139 raise NotImplementedError('get_paginated_response() must be implemented.') 

140 

141 def get_paginated_response_schema(self, schema): 

142 return schema 

143 

144 def to_html(self): # pragma: no cover 

145 raise NotImplementedError('to_html() must be implemented to display page controls.') 

146 

147 def get_results(self, data): 

148 return data['results'] 

149 

150 def get_schema_fields(self, view): 

151 assert coreapi is not None, 'coreapi must be installed to use `get_schema_fields()`' 

152 return [] 

153 

154 def get_schema_operation_parameters(self, view): 

155 return [] 

156 

157 

158class PageNumberPagination(BasePagination): 

159 """ 

160 A simple page number based style that supports page numbers as 

161 query parameters. For example: 

162 

163 http://api.example.org/accounts/?page=4 

164 http://api.example.org/accounts/?page=4&page_size=100 

165 """ 

166 # The default page size. 

167 # Defaults to `None`, meaning pagination is disabled. 

168 page_size = api_settings.PAGE_SIZE 

169 

170 django_paginator_class = DjangoPaginator 

171 

172 # Client can control the page using this query parameter. 

173 page_query_param = 'page' 

174 page_query_description = _('A page number within the paginated result set.') 

175 

176 # Client can control the page size using this query parameter. 

177 # Default is 'None'. Set to eg 'page_size' to enable usage. 

178 page_size_query_param = None 

179 page_size_query_description = _('Number of results to return per page.') 

180 

181 # Set to an integer to limit the maximum page size the client may request. 

182 # Only relevant if 'page_size_query_param' has also been set. 

183 max_page_size = None 

184 

185 last_page_strings = ('last',) 

186 

187 template = 'rest_framework/pagination/numbers.html' 

188 

189 invalid_page_message = _('Invalid page.') 

190 

191 def paginate_queryset(self, queryset, request, view=None): 

192 """ 

193 Paginate a queryset if required, either returning a 

194 page object, or `None` if pagination is not configured for this view. 

195 """ 

196 page_size = self.get_page_size(request) 

197 if not page_size: 197 ↛ 198line 197 didn't jump to line 198, because the condition on line 197 was never true

198 return None 

199 

200 paginator = self.django_paginator_class(queryset, page_size) 

201 page_number = self.get_page_number(request, paginator) 

202 

203 try: 

204 self.page = paginator.page(page_number) 

205 except InvalidPage as exc: 

206 msg = self.invalid_page_message.format( 

207 page_number=page_number, message=str(exc) 

208 ) 

209 raise NotFound(msg) 

210 

211 if paginator.num_pages > 1 and self.template is not None: 211 ↛ 213line 211 didn't jump to line 213, because the condition on line 211 was never true

212 # The browsable API should display pagination controls. 

213 self.display_page_controls = True 

214 

215 self.request = request 

216 return list(self.page) 

217 

218 def get_page_number(self, request, paginator): 

219 page_number = request.query_params.get(self.page_query_param, 1) 

220 if page_number in self.last_page_strings: 220 ↛ 221line 220 didn't jump to line 221, because the condition on line 220 was never true

221 page_number = paginator.num_pages 

222 return page_number 

223 

224 def get_paginated_response(self, data): 

225 return Response(OrderedDict([ 

226 ('count', self.page.paginator.count), 

227 ('next', self.get_next_link()), 

228 ('previous', self.get_previous_link()), 

229 ('results', data) 

230 ])) 

231 

232 def get_paginated_response_schema(self, schema): 

233 return { 

234 'type': 'object', 

235 'properties': { 

236 'count': { 

237 'type': 'integer', 

238 'example': 123, 

239 }, 

240 'next': { 

241 'type': 'string', 

242 'nullable': True, 

243 'format': 'uri', 

244 'example': 'http://api.example.org/accounts/?{page_query_param}=4'.format( 

245 page_query_param=self.page_query_param) 

246 }, 

247 'previous': { 

248 'type': 'string', 

249 'nullable': True, 

250 'format': 'uri', 

251 'example': 'http://api.example.org/accounts/?{page_query_param}=2'.format( 

252 page_query_param=self.page_query_param) 

253 }, 

254 'results': schema, 

255 }, 

256 } 

257 

258 def get_page_size(self, request): 

259 if self.page_size_query_param: 259 ↛ 269line 259 didn't jump to line 269, because the condition on line 259 was never false

260 try: 

261 return _positive_int( 

262 request.query_params[self.page_size_query_param], 

263 strict=True, 

264 cutoff=self.max_page_size 

265 ) 

266 except (KeyError, ValueError): 

267 pass 

268 

269 return self.page_size 

270 

271 def get_next_link(self): 

272 if not self.page.has_next(): 

273 return None 

274 url = self.request.build_absolute_uri() 

275 page_number = self.page.next_page_number() 

276 return replace_query_param(url, self.page_query_param, page_number) 

277 

278 def get_previous_link(self): 

279 if not self.page.has_previous(): 

280 return None 

281 url = self.request.build_absolute_uri() 

282 page_number = self.page.previous_page_number() 

283 if page_number == 1: 

284 return remove_query_param(url, self.page_query_param) 

285 return replace_query_param(url, self.page_query_param, page_number) 

286 

287 def get_html_context(self): 

288 base_url = self.request.build_absolute_uri() 

289 

290 def page_number_to_url(page_number): 

291 if page_number == 1: 

292 return remove_query_param(base_url, self.page_query_param) 

293 else: 

294 return replace_query_param(base_url, self.page_query_param, page_number) 

295 

296 current = self.page.number 

297 final = self.page.paginator.num_pages 

298 page_numbers = _get_displayed_page_numbers(current, final) 

299 page_links = _get_page_links(page_numbers, current, page_number_to_url) 

300 

301 return { 

302 'previous_url': self.get_previous_link(), 

303 'next_url': self.get_next_link(), 

304 'page_links': page_links 

305 } 

306 

307 def to_html(self): 

308 template = loader.get_template(self.template) 

309 context = self.get_html_context() 

310 return template.render(context) 

311 

312 def get_schema_fields(self, view): 

313 assert coreapi is not None, 'coreapi must be installed to use `get_schema_fields()`' 

314 assert coreschema is not None, 'coreschema must be installed to use `get_schema_fields()`' 

315 fields = [ 

316 coreapi.Field( 

317 name=self.page_query_param, 

318 required=False, 

319 location='query', 

320 schema=coreschema.Integer( 

321 title='Page', 

322 description=force_str(self.page_query_description) 

323 ) 

324 ) 

325 ] 

326 if self.page_size_query_param is not None: 

327 fields.append( 

328 coreapi.Field( 

329 name=self.page_size_query_param, 

330 required=False, 

331 location='query', 

332 schema=coreschema.Integer( 

333 title='Page size', 

334 description=force_str(self.page_size_query_description) 

335 ) 

336 ) 

337 ) 

338 return fields 

339 

340 def get_schema_operation_parameters(self, view): 

341 parameters = [ 

342 { 

343 'name': self.page_query_param, 

344 'required': False, 

345 'in': 'query', 

346 'description': force_str(self.page_query_description), 

347 'schema': { 

348 'type': 'integer', 

349 }, 

350 }, 

351 ] 

352 if self.page_size_query_param is not None: 

353 parameters.append( 

354 { 

355 'name': self.page_size_query_param, 

356 'required': False, 

357 'in': 'query', 

358 'description': force_str(self.page_size_query_description), 

359 'schema': { 

360 'type': 'integer', 

361 }, 

362 }, 

363 ) 

364 return parameters 

365 

366 

367class LimitOffsetPagination(BasePagination): 

368 """ 

369 A limit/offset based style. For example: 

370 

371 http://api.example.org/accounts/?limit=100 

372 http://api.example.org/accounts/?offset=400&limit=100 

373 """ 

374 default_limit = api_settings.PAGE_SIZE 

375 limit_query_param = 'limit' 

376 limit_query_description = _('Number of results to return per page.') 

377 offset_query_param = 'offset' 

378 offset_query_description = _('The initial index from which to return the results.') 

379 max_limit = None 

380 template = 'rest_framework/pagination/numbers.html' 

381 

382 def paginate_queryset(self, queryset, request, view=None): 

383 self.limit = self.get_limit(request) 

384 if self.limit is None: 

385 return None 

386 

387 self.count = self.get_count(queryset) 

388 self.offset = self.get_offset(request) 

389 self.request = request 

390 if self.count > self.limit and self.template is not None: 

391 self.display_page_controls = True 

392 

393 if self.count == 0 or self.offset > self.count: 

394 return [] 

395 return list(queryset[self.offset:self.offset + self.limit]) 

396 

397 def get_paginated_response(self, data): 

398 return Response(OrderedDict([ 

399 ('count', self.count), 

400 ('next', self.get_next_link()), 

401 ('previous', self.get_previous_link()), 

402 ('results', data) 

403 ])) 

404 

405 def get_paginated_response_schema(self, schema): 

406 return { 

407 'type': 'object', 

408 'properties': { 

409 'count': { 

410 'type': 'integer', 

411 'example': 123, 

412 }, 

413 'next': { 

414 'type': 'string', 

415 'nullable': True, 

416 'format': 'uri', 

417 'example': 'http://api.example.org/accounts/?{offset_param}=400&{limit_param}=100'.format( 

418 offset_param=self.offset_query_param, limit_param=self.limit_query_param), 

419 }, 

420 'previous': { 

421 'type': 'string', 

422 'nullable': True, 

423 'format': 'uri', 

424 'example': 'http://api.example.org/accounts/?{offset_param}=200&{limit_param}=100'.format( 

425 offset_param=self.offset_query_param, limit_param=self.limit_query_param), 

426 }, 

427 'results': schema, 

428 }, 

429 } 

430 

431 def get_limit(self, request): 

432 if self.limit_query_param: 

433 try: 

434 return _positive_int( 

435 request.query_params[self.limit_query_param], 

436 strict=True, 

437 cutoff=self.max_limit 

438 ) 

439 except (KeyError, ValueError): 

440 pass 

441 

442 return self.default_limit 

443 

444 def get_offset(self, request): 

445 try: 

446 return _positive_int( 

447 request.query_params[self.offset_query_param], 

448 ) 

449 except (KeyError, ValueError): 

450 return 0 

451 

452 def get_next_link(self): 

453 if self.offset + self.limit >= self.count: 

454 return None 

455 

456 url = self.request.build_absolute_uri() 

457 url = replace_query_param(url, self.limit_query_param, self.limit) 

458 

459 offset = self.offset + self.limit 

460 return replace_query_param(url, self.offset_query_param, offset) 

461 

462 def get_previous_link(self): 

463 if self.offset <= 0: 

464 return None 

465 

466 url = self.request.build_absolute_uri() 

467 url = replace_query_param(url, self.limit_query_param, self.limit) 

468 

469 if self.offset - self.limit <= 0: 

470 return remove_query_param(url, self.offset_query_param) 

471 

472 offset = self.offset - self.limit 

473 return replace_query_param(url, self.offset_query_param, offset) 

474 

475 def get_html_context(self): 

476 base_url = self.request.build_absolute_uri() 

477 

478 if self.limit: 

479 current = _divide_with_ceil(self.offset, self.limit) + 1 

480 

481 # The number of pages is a little bit fiddly. 

482 # We need to sum both the number of pages from current offset to end 

483 # plus the number of pages up to the current offset. 

484 # When offset is not strictly divisible by the limit then we may 

485 # end up introducing an extra page as an artifact. 

486 final = ( 

487 _divide_with_ceil(self.count - self.offset, self.limit) + 

488 _divide_with_ceil(self.offset, self.limit) 

489 ) 

490 

491 final = max(final, 1) 

492 else: 

493 current = 1 

494 final = 1 

495 

496 if current > final: 

497 current = final 

498 

499 def page_number_to_url(page_number): 

500 if page_number == 1: 

501 return remove_query_param(base_url, self.offset_query_param) 

502 else: 

503 offset = self.offset + ((page_number - current) * self.limit) 

504 return replace_query_param(base_url, self.offset_query_param, offset) 

505 

506 page_numbers = _get_displayed_page_numbers(current, final) 

507 page_links = _get_page_links(page_numbers, current, page_number_to_url) 

508 

509 return { 

510 'previous_url': self.get_previous_link(), 

511 'next_url': self.get_next_link(), 

512 'page_links': page_links 

513 } 

514 

515 def to_html(self): 

516 template = loader.get_template(self.template) 

517 context = self.get_html_context() 

518 return template.render(context) 

519 

520 def get_count(self, queryset): 

521 """ 

522 Determine an object count, supporting either querysets or regular lists. 

523 """ 

524 try: 

525 return queryset.count() 

526 except (AttributeError, TypeError): 

527 return len(queryset) 

528 

529 def get_schema_fields(self, view): 

530 assert coreapi is not None, 'coreapi must be installed to use `get_schema_fields()`' 

531 assert coreschema is not None, 'coreschema must be installed to use `get_schema_fields()`' 

532 return [ 

533 coreapi.Field( 

534 name=self.limit_query_param, 

535 required=False, 

536 location='query', 

537 schema=coreschema.Integer( 

538 title='Limit', 

539 description=force_str(self.limit_query_description) 

540 ) 

541 ), 

542 coreapi.Field( 

543 name=self.offset_query_param, 

544 required=False, 

545 location='query', 

546 schema=coreschema.Integer( 

547 title='Offset', 

548 description=force_str(self.offset_query_description) 

549 ) 

550 ) 

551 ] 

552 

553 def get_schema_operation_parameters(self, view): 

554 parameters = [ 

555 { 

556 'name': self.limit_query_param, 

557 'required': False, 

558 'in': 'query', 

559 'description': force_str(self.limit_query_description), 

560 'schema': { 

561 'type': 'integer', 

562 }, 

563 }, 

564 { 

565 'name': self.offset_query_param, 

566 'required': False, 

567 'in': 'query', 

568 'description': force_str(self.offset_query_description), 

569 'schema': { 

570 'type': 'integer', 

571 }, 

572 }, 

573 ] 

574 return parameters 

575 

576 

577class CursorPagination(BasePagination): 

578 """ 

579 The cursor pagination implementation is necessarily complex. 

580 For an overview of the position/offset style we use, see this post: 

581 https://cra.mr/2011/03/08/building-cursors-for-the-disqus-api 

582 """ 

583 cursor_query_param = 'cursor' 

584 cursor_query_description = _('The pagination cursor value.') 

585 page_size = api_settings.PAGE_SIZE 

586 invalid_cursor_message = _('Invalid cursor') 

587 ordering = '-created' 

588 template = 'rest_framework/pagination/previous_and_next.html' 

589 

590 # Client can control the page size using this query parameter. 

591 # Default is 'None'. Set to eg 'page_size' to enable usage. 

592 page_size_query_param = None 

593 page_size_query_description = _('Number of results to return per page.') 

594 

595 # Set to an integer to limit the maximum page size the client may request. 

596 # Only relevant if 'page_size_query_param' has also been set. 

597 max_page_size = None 

598 

599 # The offset in the cursor is used in situations where we have a 

600 # nearly-unique index. (Eg millisecond precision creation timestamps) 

601 # We guard against malicious users attempting to cause expensive database 

602 # queries, by having a hard cap on the maximum possible size of the offset. 

603 offset_cutoff = 1000 

604 

605 def paginate_queryset(self, queryset, request, view=None): 

606 self.page_size = self.get_page_size(request) 

607 if not self.page_size: 

608 return None 

609 

610 self.base_url = request.build_absolute_uri() 

611 self.ordering = self.get_ordering(request, queryset, view) 

612 

613 self.cursor = self.decode_cursor(request) 

614 if self.cursor is None: 

615 (offset, reverse, current_position) = (0, False, None) 

616 else: 

617 (offset, reverse, current_position) = self.cursor 

618 

619 # Cursor pagination always enforces an ordering. 

620 if reverse: 

621 queryset = queryset.order_by(*_reverse_ordering(self.ordering)) 

622 else: 

623 queryset = queryset.order_by(*self.ordering) 

624 

625 # If we have a cursor with a fixed position then filter by that. 

626 if current_position is not None: 

627 order = self.ordering[0] 

628 is_reversed = order.startswith('-') 

629 order_attr = order.lstrip('-') 

630 

631 # Test for: (cursor reversed) XOR (queryset reversed) 

632 if self.cursor.reverse != is_reversed: 

633 kwargs = {order_attr + '__lt': current_position} 

634 else: 

635 kwargs = {order_attr + '__gt': current_position} 

636 

637 queryset = queryset.filter(**kwargs) 

638 

639 # If we have an offset cursor then offset the entire page by that amount. 

640 # We also always fetch an extra item in order to determine if there is a 

641 # page following on from this one. 

642 results = list(queryset[offset:offset + self.page_size + 1]) 

643 self.page = list(results[:self.page_size]) 

644 

645 # Determine the position of the final item following the page. 

646 if len(results) > len(self.page): 

647 has_following_position = True 

648 following_position = self._get_position_from_instance(results[-1], self.ordering) 

649 else: 

650 has_following_position = False 

651 following_position = None 

652 

653 if reverse: 

654 # If we have a reverse queryset, then the query ordering was in reverse 

655 # so we need to reverse the items again before returning them to the user. 

656 self.page = list(reversed(self.page)) 

657 

658 # Determine next and previous positions for reverse cursors. 

659 self.has_next = (current_position is not None) or (offset > 0) 

660 self.has_previous = has_following_position 

661 if self.has_next: 

662 self.next_position = current_position 

663 if self.has_previous: 

664 self.previous_position = following_position 

665 else: 

666 # Determine next and previous positions for forward cursors. 

667 self.has_next = has_following_position 

668 self.has_previous = (current_position is not None) or (offset > 0) 

669 if self.has_next: 

670 self.next_position = following_position 

671 if self.has_previous: 

672 self.previous_position = current_position 

673 

674 # Display page controls in the browsable API if there is more 

675 # than one page. 

676 if (self.has_previous or self.has_next) and self.template is not None: 

677 self.display_page_controls = True 

678 

679 return self.page 

680 

681 def get_page_size(self, request): 

682 if self.page_size_query_param: 

683 try: 

684 return _positive_int( 

685 request.query_params[self.page_size_query_param], 

686 strict=True, 

687 cutoff=self.max_page_size 

688 ) 

689 except (KeyError, ValueError): 

690 pass 

691 

692 return self.page_size 

693 

694 def get_next_link(self): 

695 if not self.has_next: 

696 return None 

697 

698 if self.page and self.cursor and self.cursor.reverse and self.cursor.offset != 0: 

699 # If we're reversing direction and we have an offset cursor 

700 # then we cannot use the first position we find as a marker. 

701 compare = self._get_position_from_instance(self.page[-1], self.ordering) 

702 else: 

703 compare = self.next_position 

704 offset = 0 

705 

706 has_item_with_unique_position = False 

707 for item in reversed(self.page): 

708 position = self._get_position_from_instance(item, self.ordering) 

709 if position != compare: 

710 # The item in this position and the item following it 

711 # have different positions. We can use this position as 

712 # our marker. 

713 has_item_with_unique_position = True 

714 break 

715 

716 # The item in this position has the same position as the item 

717 # following it, we can't use it as a marker position, so increment 

718 # the offset and keep seeking to the previous item. 

719 compare = position 

720 offset += 1 

721 

722 if self.page and not has_item_with_unique_position: 

723 # There were no unique positions in the page. 

724 if not self.has_previous: 

725 # We are on the first page. 

726 # Our cursor will have an offset equal to the page size, 

727 # but no position to filter against yet. 

728 offset = self.page_size 

729 position = None 

730 elif self.cursor.reverse: 

731 # The change in direction will introduce a paging artifact, 

732 # where we end up skipping forward a few extra items. 

733 offset = 0 

734 position = self.previous_position 

735 else: 

736 # Use the position from the existing cursor and increment 

737 # it's offset by the page size. 

738 offset = self.cursor.offset + self.page_size 

739 position = self.previous_position 

740 

741 if not self.page: 

742 position = self.next_position 

743 

744 cursor = Cursor(offset=offset, reverse=False, position=position) 

745 return self.encode_cursor(cursor) 

746 

747 def get_previous_link(self): 

748 if not self.has_previous: 

749 return None 

750 

751 if self.page and self.cursor and not self.cursor.reverse and self.cursor.offset != 0: 

752 # If we're reversing direction and we have an offset cursor 

753 # then we cannot use the first position we find as a marker. 

754 compare = self._get_position_from_instance(self.page[0], self.ordering) 

755 else: 

756 compare = self.previous_position 

757 offset = 0 

758 

759 has_item_with_unique_position = False 

760 for item in self.page: 

761 position = self._get_position_from_instance(item, self.ordering) 

762 if position != compare: 

763 # The item in this position and the item following it 

764 # have different positions. We can use this position as 

765 # our marker. 

766 has_item_with_unique_position = True 

767 break 

768 

769 # The item in this position has the same position as the item 

770 # following it, we can't use it as a marker position, so increment 

771 # the offset and keep seeking to the previous item. 

772 compare = position 

773 offset += 1 

774 

775 if self.page and not has_item_with_unique_position: 

776 # There were no unique positions in the page. 

777 if not self.has_next: 

778 # We are on the final page. 

779 # Our cursor will have an offset equal to the page size, 

780 # but no position to filter against yet. 

781 offset = self.page_size 

782 position = None 

783 elif self.cursor.reverse: 

784 # Use the position from the existing cursor and increment 

785 # it's offset by the page size. 

786 offset = self.cursor.offset + self.page_size 

787 position = self.next_position 

788 else: 

789 # The change in direction will introduce a paging artifact, 

790 # where we end up skipping back a few extra items. 

791 offset = 0 

792 position = self.next_position 

793 

794 if not self.page: 

795 position = self.previous_position 

796 

797 cursor = Cursor(offset=offset, reverse=True, position=position) 

798 return self.encode_cursor(cursor) 

799 

800 def get_ordering(self, request, queryset, view): 

801 """ 

802 Return a tuple of strings, that may be used in an `order_by` method. 

803 """ 

804 ordering_filters = [ 

805 filter_cls for filter_cls in getattr(view, 'filter_backends', []) 

806 if hasattr(filter_cls, 'get_ordering') 

807 ] 

808 

809 if ordering_filters: 

810 # If a filter exists on the view that implements `get_ordering` 

811 # then we defer to that filter to determine the ordering. 

812 filter_cls = ordering_filters[0] 

813 filter_instance = filter_cls() 

814 ordering = filter_instance.get_ordering(request, queryset, view) 

815 assert ordering is not None, ( 

816 'Using cursor pagination, but filter class {filter_cls} ' 

817 'returned a `None` ordering.'.format( 

818 filter_cls=filter_cls.__name__ 

819 ) 

820 ) 

821 else: 

822 # The default case is to check for an `ordering` attribute 

823 # on this pagination instance. 

824 ordering = self.ordering 

825 assert ordering is not None, ( 

826 'Using cursor pagination, but no ordering attribute was declared ' 

827 'on the pagination class.' 

828 ) 

829 assert '__' not in ordering, ( 

830 'Cursor pagination does not support double underscore lookups ' 

831 'for orderings. Orderings should be an unchanging, unique or ' 

832 'nearly-unique field on the model, such as "-created" or "pk".' 

833 ) 

834 

835 assert isinstance(ordering, (str, list, tuple)), ( 

836 'Invalid ordering. Expected string or tuple, but got {type}'.format( 

837 type=type(ordering).__name__ 

838 ) 

839 ) 

840 

841 if isinstance(ordering, str): 

842 return (ordering,) 

843 return tuple(ordering) 

844 

845 def decode_cursor(self, request): 

846 """ 

847 Given a request with a cursor, return a `Cursor` instance. 

848 """ 

849 # Determine if we have a cursor, and if so then decode it. 

850 encoded = request.query_params.get(self.cursor_query_param) 

851 if encoded is None: 

852 return None 

853 

854 try: 

855 querystring = b64decode(encoded.encode('ascii')).decode('ascii') 

856 tokens = parse.parse_qs(querystring, keep_blank_values=True) 

857 

858 offset = tokens.get('o', ['0'])[0] 

859 offset = _positive_int(offset, cutoff=self.offset_cutoff) 

860 

861 reverse = tokens.get('r', ['0'])[0] 

862 reverse = bool(int(reverse)) 

863 

864 position = tokens.get('p', [None])[0]