commit 875bc6f6bde32d5c8d042cb3ca493bf037b8fc11
author Youssef Elghareeb <ghareeb@google.com> Thu Sep 07 14:37:34 2023 +0200
committer Youssef Elghareeb <ghareeb@google.com> Mon Sep 11 12:24:20 2023 +0200
tree 9bace295ff1905eeb879e3c0e9b0611c140d8c35
parent 9503f40ce72dd08a79ae87435a4d76b36bf659a5

List Branches - add a next-page-token request parameter

We add a next-page-token parameter to the request and response of 'List
Branches' endpoint. This would optimize the performance for pagination
across this API in contrast with the start & limit parameters.

Background
----------
The reason is that the current start/skip parameters process the request
as follows:
1) Load all the branches from the repo and get the set S
2) Filter S against caller visibility to get S'. If start and limit
   parameters are supplied, we filter branches until we get as many as
   'limit' entries starting from 'start'. Visibility checks on the
   remaining branches is not necessary.

Because of the visibility checks in (2), it needs to be executed for all
skipped branches + the branches that are returned, so a client migrating
from a one call to 'n' paginated calls will perform a quadratic
computations of visibility. This is bad since the majority of the
request time is spent on visibility checks.

With continuation tokens, the request can be executed as follows:
1) Load all the branches from the repo and get the set S
2) Drop all refs before (and including) the continuation token, get S'
3) Filter S' against caller visibility to get S''. If start and limit
   parameters are supplied, we filter branches until we get as many as
   'limit' entries starting from 'start'. Visibility checks on the
   remaining branches is not necessary.
4) Return the refs to the user and continuation_token = last item

Implementation
--------------
We accept a new 'next-page-token' request parameter which is mutually
exclusive with 'start' (or otherwise the request would fail). If the
limit parameter is set, and the number of branches is larger than the
limit, we set a new response header 'X-GERRIT-NEXT-PAGE-TOKEN' to the
string representation of the branch name that's last in the return list.
Otherwise, this header will not be set. The response header is made
opaque by proto-serializing it then encoding it with base64.

If the token corresponded to a non-existent branch, the server will skip
over to the next greater branch. We also prepend an encoded string to
the token value as a lightweight way to indicate it was generated by the
server, otherwise the request would also fail if an invalid token (not
generated by Gerrit) was supplied in the request parameters.

Change-Id: Ib3942a4024e4975f04eced3873ebb004cfe609ba
Google-Bug-Id: b/288895555
Release-Notes: Allow pagination using continuation token for 'list branches'