CursorPagination previous_link points to an invalid page when a page has no unique markers

[jalaziz]

Checklist

• I have verified that that issue exists against the master branch of Django REST framework.
• I have searched for similar issues in both open and closed tickets and cannot find a duplicate.
• This is not a usage question. (Those should be directed to the discussion group instead.)
• [x ] This cannot be dealt with as a third party library. (We prefer new functionality to be in the form of third party libraries where possible.)
• I have reduced the issue to the simplest possible case.
• I have included a failing test as a pull request. (If you are unable to do so we can still accept the issue.)

Steps to reproduce

• Set the PAGE_SIZE setting to 50
• Create 100+ instances of a model with the exact same created timestamp.
• Create several instances of a model with earlier created timestamps.
• Create a view and add the CursorPagination paginator class
• Navigate to the second page
• Navigate back using the previous link

Expected behavior

The previous cursor should point back to the first page with 50 results.

Actual behavior

The previous cursor points to a page with 0 results. The next cursor on that page will then point to a page that skips over the records with the same created timestamp.

Notes

I spent some time investigating this and so far have ended up with two potential issues.

In our exact setup, we have the following distribution of position markers:

created	count
2020-08-31 00:00:00+00	948
2020-09-28 00:00:00+00	877
2020-11-02 00:00:00+00	681
2020-12-28 00:00:00+00	400
2020-11-30 00:00:00+00	279
2021-02-01 00:00:00+00	201
2020-01-13 00:00:00+00	200
2020-12-24 08:00:02+00	122
2020-12-24 08:01:00+00	116
2020-12-24 07:31:54+00	108
2020-11-26 08:01:00+00	104
2020-11-19 08:01:00+00	100
2020-12-10 08:00:02+00	98
2020-11-26 07:31:17+00	90
2021-01-07 07:31:43+00	76
2020-11-19 07:31:17+00	76
2020-12-17 08:00:03+00	74
2020-12-31 13:36:06+00	74

After a short investigate, it would appear that the logic that calculates the previous link may be at fault:

• The first page has:
  • a next cursor with value: {'o': '50'} ✅
• The second page:
  • a next cursor with value: {'o': '100'} ✅
  • a previous cursor with value {'r': '1', 'p': '2021-02-01 00:00:00+00:00'} ❌
• Using the previous cursor takes you to a page with:
  • a next cursor with value {'p': '2021-02-01 00:00:00+00:00'} ❌

The problem seems to occur around here. In our case, self.next_position is set 2021-02-01 00:00:00+00:00 from paginate_queryset.

It would seem that when using we're in offset territory, the previous cursor should effectively point to the previous offset. I do realize that the comments do indicate possible skipping, but the fact that the next cursor ends up skipping thereafter is problematic.

The problem ultimately occurs because because paginate_queryset adds a lt or gt filter from the cursor position. In the "reverse" case, this returns nothing because the cursor is asking for all records with created > '2021-02-01 00:00:00+00:00'. In the "forward" case, it skips ahead because it asks for all records with created < '2021-02-01 00:00:00+00:00'.

I'd be happy to contribute a fix, but I'd like to make sure that this is not expected and get clarity on any edge cases I should consider when fixing the issue. This comment seems to suggest that the skipping back is on purpose. Also, this comment seems to suggest that skipping forward is on purpose. However, is the interaction between the two expected?