facebook / facebook/relay

PageInfo spec has bugs that require `false` to be returned when there are previous or next pages

Open
#2,787 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
19k
Forks
1.9k
PR merge metrics
No merged PRs in 30d

Description

It appears that the formal algorithm for `hasPreviousPage` and `hasNextPage`, as defined in [the Relay Connections Cursor Spec](https://facebook.github.io/relay/graphql/connections.htm), has a couple bugs. That is, if I implement my server to follow the spec exactly as written, there are some situations where `false` will be returned for `hasPreviousPage` when there in fact is a previous page, and `false` will be returned for `hasNextPage` when there is in fact a next page.

Here is the current spec I am working off of:

```
HasPreviousPage(allEdges, before, after, first, last):
* If {last} is set:
* Let {edges} be the result of calling {ApplyCursorsToEdges(allEdges, before, after)}.
* If {edges} contains more than {last} elements return {true}, otherwise {false}.
* If {after} is set:
* If the server can efficiently determine that elements exist prior to {after}, return {true}.
* Return {false}.

HasNextPage(allEdges, before, after, first, last):
* If {first} is set:
* Let {edges} be the result of calling {ApplyCursorsToEdges(allEdges, before, after)}.
* If {edges} contains more than {first} elements return {true}, otherwise {false}.
* If {before} is set:
* If the server can efficiently determine that elements exist following {before}, return {true}.
* Return {false}.
```

For the bugs listed below, assume we're working with a list of edges like `[a, b, c, d, e]` (where the letters are the cursors for each edge).

## Bug # 1

If my server is called with just `after: a` (no `first`, `last` or `before` arguments), then `[b, c, d, e]` will be returned as the page of edges. The algorithm requires that `false` be returned for `hasPreviousPage`, even though there is the previous page of `[a]`. Specifically, `last` is _not_ set but `after` is, so this part of the algorithm applies:

```
* If {after} is set:
* If the server can efficiently determine that elements exist prior to {after}, return {true}.
* Return {false}.
```

We can efficiently determine that no elements exist prior to the `after` cursor value of `a` (it is the first edge, after all) so we fall through to the `Return {false}` bit and return `false`.

In general, it seems like there's a mismatch between the algorithm for `ApplyCursorsToEdges` removing elements _on_ or _before_ `after` while `hasPreviousPage` only considers if any elements come _before_ `after` (rather than also considering the element identified by `after` itself).

The same bug also exists for `hasNextPage`; if my server is called with just `before: e`, the spec tells me I have to return `false` for `hasNextPage` even though a next page of `[e]` does in fact exist.

## Bug # 2

If my server is called with `last: 3, after: a, before: e`, then `[b, c, d]` will be returned as the page of edges, but the algorithm requires that `false` be returned for `hasPreviousPage`, even though there is a previous page (`[a]`). Since `last` is set, this part of the algorithm applies:

```
* If {last} is set:
* Let {edges} be the result of calling {ApplyCursorsToEdges(allEdges, before, after)}.
* If {edges} contains more than {last} elements return {true}, otherwise {false}.
```

Calling `ApplyCursorsToEdges(allEdges, before, after)` when `allEdges = [a, b, c, d, e] and before = e and after = a` results in `[b, c, d]`. `edges` contains 3 elements, which is the value of `last`; therefore, according to `If {edges} contains more than {last} elements return {true}, otherwise {false}` we must return `false`.

The same bug also exists for `hasNextPage`; if my server is called with just `first: 3, after: a, before: 3`, the spec tells me I have to return `false` for `hasNextPage` even though a next page of `[e]` does in fact exist.

Contributor guide

Open the contributing guide

Research direction

Read the linked Relay Connections Cursor Spec, especially ApplyCursorsToEdges, HasPreviousPage, and HasNextPage, and reproduce the listed edge cases using [a, b, c, d, e]. Determine the corrected formal behavior for both cases and update the specification; done means it no longer mandates false when the cited adjacent page exists.

Written by the indexing model from the issue text.

Assessment

Tech stack
graphql
Domain
backend-api-design, documentation
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.