dropshot 0.9.0

// Copyright 2022 Oxide Computer Company

//! Detailed end-user documentation for pagination lives in the Dropshot top-
//! level block comment.  Here we discuss some of the design choices.
//!
//! ## Background: patterns for pagination
//!
//! [In their own API design guidelines, Google describes an approach similar to
//! the one we use][1].  There are many ways to implement the page token with
//! many different tradeoffs.  The one described in the Dropshot top-level block
//! comment has a lot of nice properties:
//!
//! * For APIs backed by a database of some kind, it's usually straightforward to
//!   use an existing primary key or other unique, sortable field (or combination
//!   of fields) as the token.
//!
//! * If the client scans all the way through the collection, they will see every
//!   object that existed both before the scan and after the scan and was not
//!   renamed during the scan.  (This isn't true for schemes that use a simple
//!   numeric offset as the token.)
//!
//! * There's no server-side state associated with the token, so it's no problem
//!   if the server crashes between requests or if subsequent requests are
//!   handled by a different instance.  (This isn't true for schemes that store
//!   the result set on the server.)
//!
//! * It's often straightforward to support a reversed-order scan as well -- this
//!   may just be a matter of flipping the inequality used for a database query.
//!
//! * It's easy to support sorting by a single field, and with some care it's
//!   possible to support queries on multiple different fields, even at the same
//!   time.  An API can support listing by any unique, sortable combination of
//!   fields.  For example, say our Projects have a modification time ("mtime")
//!   as well.  We could support listing projects alphabetically by name _or_ in
//!   order of most recently modified.  For the latter, since the modification
//!   time is generally not unique, and the marker must be unique, we'd really be
//!   listing by an ("mtime" descending, "name" ascending) tuple.
//!
//! The interfaces here are intended to support this sort of use case.  For APIs
//! backed by traditional RDBMS databases, see [this post for background on
//! various ways to page through a large set of data][2].  (What we're describing
//! here leverages what this post calls "keyset pagination".)
//!
//! Another consideration in designing pagination is whether the token ought to
//! be explicit and meaningful to the user or just an opaque token (likely
//! encoded in some way).  It can be convenient for developers to use APIs where
//! the token is explicitly intended to be one of the fields of the object (e.g.,
//! so that you could list animals starting in the middle by just requesting
//! `?animal_name=moose`), but this puts constraints on the server because
//! clients may come to depend on specific fields being supported and sorted in a
//! certain way.  Dropshot takes the approach of using an encoded token that
//! includes information about the whole scan (e.g., the sort order).  This makes
//! it possible to identify cases that might otherwise result in confusing
//! behavior (e.g., a client lists projects in ascending order, but then asks for
//! the next page in descending order).  The token also includes a version number
//! so that it can be evolved in the future.
//!
//!
//! ## Background: Why paginate HTTP APIs in the first place?
//!
//! Pagination helps ensure that the cost of a request in terms of resource
//! utilization remains O(1) -- that is, it can be bounded above by a constant
//! rather than scaling proportionally with any of the request parameters.  This
//! simplifies utilization monitoring, capacity planning, and scale-out
//! activities for the service, since operators can think of the service in terms
//! of one unit that needs to be scaled up.  (It's still a very complex process,
//! but it would be significantly harder if requests weren't O(1).)
//!
//! Similarly, pagination helps ensure that the time required for a request is
//! O(1) under normal conditions.  This makes it easier to define expectations
//! for service latency and to monitor that latency to determine if those
//! expectations are violated.  Generally, if latency increases, then the service
//! is unhealthy, and a crisp definition of "unhealthy" is important to operate a
//! service with high availability.  If requests weren't O(1), an increase in
//! latency might just reflect a changing workload that's still performing within
//! expectations -- e.g., clients listing larger collections than they were
//! before, but still getting results promptly.  That would make it much harder
//! to see when the service really is unhealthy.
//!
//! Finally, bounding requests to O(1) work is a critical mitigation for common
//! (if basic) denial-of-service (DoS) attacks because it requires that clients
//! consume resources commensurate with the server costs that they're imposing.
//! If a service exposes an API that does work proportional to some parameter,
//! then it's cheap to launch a DoS on the service by just invoking that API with
//! a large parameter.  By contrast, if the client has to do work that scales
//! linearly with the work the server has to do, then the client's costs go up in
//! order to scale up the attack.
//!
//! Along these lines, connections and requests consume finite server resources
//! like open file descriptors and database connections.  If a service is built
//! so that requests are all supposed to take about the same amount of time (or
//! at least that there's a constant upper bound), then it may be possible to use
//! a simple timeout scheme to cancel requests that are taking too long, as might
//! happen if a malicious client finds some way to cause requests to hang or take
//! a very long time.
//!
//! [1]: https://cloud.google.com/apis/design/design_patterns#list_pagination
//! [2]: https://www.citusdata.com/blog/2016/03/30/five-ways-to-paginate/

use crate::error::HttpError;
use crate::from_map::from_map;
use base64::engine::general_purpose::URL_SAFE;
use base64::Engine;
use schemars::JsonSchema;
use serde::de::DeserializeOwned;
use serde::Deserialize;
use serde::Deserializer;
use serde::Serialize;
use serde_json::json;
use std::collections::BTreeMap;
use std::fmt::Debug;
use std::num::NonZeroU32;

/// A page of results from a paginated API
///
/// This structure is intended for use both on the server side (to generate the
/// results page) and on the client side (to parse it).
#[derive(Debug, Deserialize, Serialize)]
pub struct ResultsPage<ItemType> {
    /// token used to fetch the next page of results (if any)
    pub next_page: Option<String>,
    /// list of items on this page of results
    pub items: Vec<ItemType>,
}

impl<ItemType> JsonSchema for ResultsPage<ItemType>
where
    ItemType: JsonSchema,
{
    fn schema_name() -> String {
        format!("{}ResultsPage", ItemType::schema_name())
    }

    fn json_schema(
        gen: &mut schemars::gen::SchemaGenerator,
    ) -> schemars::schema::Schema {
        ResultsPageSchema::<ItemType>::json_schema(gen)
    }
}

/// A single page of results
#[derive(JsonSchema)]
pub struct ResultsPageSchema<ItemType> {
    /// token used to fetch the next page of results (if any)
    pub next_page: Option<String>,
    /// list of items on this page of results
    pub items: Vec<ItemType>,
}

impl<ItemType> ResultsPage<ItemType> {
    /// Construct a new results page from the list of `items`.  `page_selector`
    /// is a function used to construct the page token that clients will provide
    /// to fetch the next page of results.  `scan_params` is provided to the
    /// `page_selector` function, since the token may depend on the type of scan.
    pub fn new<F, ScanParams, PageSelector>(
        items: Vec<ItemType>,
        scan_params: &ScanParams,
        get_page_selector: F,
    ) -> Result<ResultsPage<ItemType>, HttpError>
    where
        F: Fn(&ItemType, &ScanParams) -> PageSelector,
        PageSelector: Serialize,
    {
        let next_page = items
            .last()
            .map(|last_item| {
                let selector = get_page_selector(last_item, scan_params);
                serialize_page_token(selector)
            })
            .transpose()?;

        Ok(ResultsPage { next_page, items })
    }
}

/// Querystring parameters provided by clients when scanning a paginated
/// collection
///
/// To build an API endpoint that paginates results, you have your handler
/// function accept a `Query<PaginationParams<ScanParams, PageSelector>>` and
/// return a [`ResultsPage`].  You define your own `ScanParams` and
/// `PageSelector` types.
///
/// `ScanParams` describes the set of querystring parameters that your endpoint
/// accepts for the _first_ request of the scan (typically: filters and sort
/// options).  This must be deserializable from a querystring.
///
/// `PageSelector` describes the information your endpoint needs for requests
/// after the first one.  Typically this would include an id of some sort for the
/// last item on the previous page as well as any parameters related to filtering
/// or sorting so that your function can apply those, too.  The entire
/// `PageSelector` will be serialized to an opaque string and included in the
/// [`ResultsPage`].  The client is expected to provide this string as the
/// `"page_token"` querystring parameter in the subsequent request.
/// `PageSelector` must implement both [`Deserialize`] and [`Serialize`].
/// (Unlike `ScanParams`, `PageSelector` will not be deserialized directly from
/// the querystring.)
///
/// There are several complete, documented examples in `dropshot/examples`.
///
/// **NOTE:** Your choices of `ScanParams` and `PageSelector` determine the
/// querystring parameters accepted by your endpoint and the structure of the
/// page token, respectively.  Both of these are part of your API's public
/// interface, though the page token won't appear in the OpenAPI spec.  Be
/// careful when designing these structures to consider what you might want to
/// support in the future.
#[derive(Debug, Deserialize)]
pub struct PaginationParams<ScanParams, PageSelector>
where
    ScanParams: DeserializeOwned,
    PageSelector: DeserializeOwned + Serialize,
{
    /// Specifies whether this is the first request in a scan or a subsequent
    /// request, as well as the parameters provided
    ///
    /// See [`WhichPage`] for details.  Note that this field is flattened by
    /// serde, so you have to look at the variants of [`WhichPage`] to see what
    /// query parameters are actually processed here.
    #[serde(flatten, deserialize_with = "deserialize_whichpage")]
    pub page: WhichPage<ScanParams, PageSelector>,

    /// Client-requested limit on page size (optional)
    ///
    /// Consumers should use
    /// [`RequestContext`][crate::handler::RequestContext::page_limit()]
    /// to access this value.
    pub(crate) limit: Option<NonZeroU32>,
}

pub(crate) const PAGINATION_PARAM_SENTINEL: &str =
    "x-dropshot-pagination-param";
pub(crate) const PAGINATION_EXTENSION: &str = "x-dropshot-pagination";

impl<ScanParams, PageSelector> JsonSchema
    for PaginationParams<ScanParams, PageSelector>
where
    ScanParams: DeserializeOwned + JsonSchema,
    PageSelector: DeserializeOwned + Serialize,
{
    fn schema_name() -> String {
        "PaginationParams".to_string()
    }

    fn json_schema(
        gen: &mut schemars::gen::SchemaGenerator,
    ) -> schemars::schema::Schema {
        // We use `SchemaPaginationParams to generate an intuitive schema and
        // we use the JSON schema extensions mechanism to communicate the fact
        // that this is a pagination parameter. We'll later use this to tag
        // its associated operation as paginated.
        // TODO we would ideally like to verify that both parameters *and*
        // response structure are properly configured for pagination.
        let mut schema = SchemaPaginationParams::<ScanParams>::json_schema(gen)
            .into_object();
        schema
            .extensions
            .insert(PAGINATION_PARAM_SENTINEL.to_string(), json!(true));
        schemars::schema::Schema::Object(schema)
    }
}

// This is the API consumer-visible interface for paginated endpoints. We use
// this solely to generate the schema. User-specified parameters appear before
// pagination boilerplate.
#[derive(JsonSchema)]
#[allow(dead_code)]
struct SchemaPaginationParams<ScanParams> {
    #[schemars(flatten)]
    params: Option<ScanParams>,
    /// Maximum number of items returned by a single call
    limit: Option<NonZeroU32>,
    /// Token returned by previous call to retrieve the subsequent page
    page_token: Option<String>,
}

// Deserialize `WhichPage` for `PaginationParams`. In REST APIs, callers
// typically provide either the parameters to resume a scan (in our case, just
// "page_token") or the parameters to begin a new one (which can be
// any set of parameters that our consumer wants).  There's generally no
// separate field to indicate which case they're requesting. We deserialize into
// a generic map first and then either interpret the page token or deserialize
// the map into ScanParams.
fn deserialize_whichpage<'de, D, ScanParams, PageSelector>(
    deserializer: D,
) -> Result<WhichPage<ScanParams, PageSelector>, D::Error>
where
    D: Deserializer<'de>,
    ScanParams: DeserializeOwned,
    PageSelector: DeserializeOwned,
{
    let raw_params = BTreeMap::<String, String>::deserialize(deserializer)?;

    match raw_params.get("page_token") {
        Some(page_token) => {
            let page_start = deserialize_page_token(&page_token)
                .map_err(serde::de::Error::custom)?;
            Ok(WhichPage::Next(page_start))
        }
        None => {
            let scan_params =
                from_map(&raw_params).map_err(serde::de::Error::custom)?;
            Ok(WhichPage::First(scan_params))
        }
    }
}

/// Describes whether the client is beginning a new scan or resuming an existing
/// one
///
/// In either case, this type provides access to consumer-defined parameters for
/// the particular type of request.  See [`PaginationParams`] for more
/// information.
#[derive(Debug)]
pub enum WhichPage<ScanParams, PageSelector> {
    /// Indicates that the client is beginning a new scan
    ///
    /// `ScanParams` are the consumer-defined parameters for beginning a new scan
    /// (e.g., filters, sort options, etc.)
    First(ScanParams),

    /// Indicates that the client is resuming a previous scan
    ///
    /// `PageSelector` are the consumer-defined parameters for resuming a
    /// previous scan (e.g., any scan parameters, plus a marker to indicate the
    /// last result seen by the client).
    Next(PageSelector),
}

/// `ScanParams` for use with `PaginationParams` when the API endpoint has no
/// scan parameters (i.e., it always iterates items in the collection in the same
/// way).
#[derive(Debug, Deserialize, JsonSchema)]
pub struct EmptyScanParams {}

/// The order in which the client wants to page through the requested collection
#[derive(Copy, Clone, Debug, Deserialize, JsonSchema, PartialEq, Serialize)]
#[serde(rename_all = "lowercase")]
pub enum PaginationOrder {
    Ascending,
    Descending,
}

// Token and querystring serialization and deserialization
//
// Page tokens essentially take the consumer's PageSelector struct, add a
// version number, serialize that as JSON, and base64-encode the result.  This
// token is returned in any response from a paginated API, and the client will
// pass it back as a query parameter for subsequent pagination requests. This
// approach allows us to rev the serialized form if needed (see
// `PaginationVersion`) and add other metadata in a backwards-compatiable way.
// It also emphasizes to clients that the token should be treated as opaque,
// though it's obviously not resistant to tampering.

/// Maximum length of a page token once the consumer-provided type is serialized
/// and the result is base64-encoded
///
/// We impose a maximum length primarily to prevent a client from making us parse
/// extremely large strings.  We apply this limit when we create tokens to avoid
/// handing out a token that can't be used.
///
/// Note that these tokens are passed in the HTTP request line (before the
/// headers), and many HTTP implementations impose a limit as low as 8KiB on the
/// size of the request line and headers together, so it's a good idea to keep
/// this as small as we can.
const MAX_TOKEN_LENGTH: usize = 512;

/// Version for the pagination token serialization format
///
/// This may seem like overkill, but it allows us to rev this in a future version
/// of Dropshot without breaking any ongoing scans when the change is deployed.
/// If we rev this, we might need to provide a way for clients to request at
/// runtime which version of token to generate so that if they do a rolling
/// upgrade of multiple instances, they can configure the instances to generate
/// v1 tokens until the rollout is complete, then switch on the new token
/// version.  Obviously, it would be better to avoid revving this version if
/// possible!
///
/// Note that consumers still need to consider compatibility if they change their
/// own `ScanParams` or `PageSelector` types.
#[derive(Copy, Clone, Debug, Deserialize, JsonSchema, PartialEq, Serialize)]
#[serde(rename_all = "lowercase")]
enum PaginationVersion {
    V1,
}

/// Parts of the pagination token that actually get serialized
#[derive(Debug, Deserialize, Serialize)]
struct SerializedToken<PageSelector> {
    v: PaginationVersion,
    page_start: PageSelector,
}

/// Construct a serialized page token from a consumer's page selector
fn serialize_page_token<PageSelector: Serialize>(
    page_start: PageSelector,
) -> Result<String, HttpError> {
    let token_bytes = {
        let serialized_token =
            SerializedToken { v: PaginationVersion::V1, page_start };

        let json_bytes =
            serde_json::to_vec(&serialized_token).map_err(|e| {
                HttpError::for_internal_error(format!(
                    "failed to serialize token: {}",
                    e
                ))
            })?;

        URL_SAFE.encode(json_bytes)
    };

    // TODO-robustness is there a way for us to know at compile-time that
    // this won't be a problem?  What if we say that PageSelector has to be
    // Sized?  That won't guarantee that this will work, but wouldn't that
    // mean that if it ever works, then it will always work?  But would that
    // interface be a pain to use, given that variable-length strings are
    // very common in the token?
    if token_bytes.len() > MAX_TOKEN_LENGTH {
        return Err(HttpError::for_internal_error(format!(
            "serialized token is too large ({} bytes, max is {})",
            token_bytes.len(),
            MAX_TOKEN_LENGTH
        )));
    }

    Ok(token_bytes)
}

/// Deserialize a token from the given string into the consumer's page selector
/// type
fn deserialize_page_token<PageSelector: DeserializeOwned>(
    token_str: &str,
) -> Result<PageSelector, String> {
    if token_str.len() > MAX_TOKEN_LENGTH {
        return Err(String::from(
            "failed to parse pagination token: too large",
        ));
    }
    let json_bytes = URL_SAFE
        .decode(token_str.as_bytes())
        .map_err(|e| format!("failed to parse pagination token: {}", e))?;

    // TODO-debugging: we don't want the user to have to know about the
    // internal structure of the token, so the error message here doesn't
    // say anything about that.  However, it would be nice if we could
    // create an internal error message that included the serde_json error,
    // which would have more context for someone looking at the server logs
    // to figure out what happened with this request.  Our own `HttpError`
    // supports this, but it seems like serde only preserves the to_string()
    // output of the error anyway.  It's not clear how else we could
    // propagate this information out.
    let deserialized: SerializedToken<PageSelector> =
        serde_json::from_slice(&json_bytes).map_err(|_| {
            String::from("failed to parse pagination token: corrupted token")
        })?;

    if deserialized.v != PaginationVersion::V1 {
        return Err(format!(
            "failed to parse pagination token: unsupported version: {:?}",
            deserialized.v,
        ));
    }

    Ok(deserialized.page_start)
}

#[cfg(test)]
mod test {
    use super::deserialize_page_token;
    use super::serialize_page_token;
    use super::PaginationParams;
    use super::ResultsPage;
    use super::WhichPage;
    use super::PAGINATION_PARAM_SENTINEL;
    use base64::engine::general_purpose::URL_SAFE;
    use base64::Engine;
    use schemars::JsonSchema;
    use serde::de::DeserializeOwned;
    use serde::Deserialize;
    use serde::Serialize;
    use serde_json::json;
    use std::{fmt::Debug, num::NonZeroU32};

    #[test]
    fn test_page_token_serialization() {
        #[derive(Deserialize, Serialize)]
        struct MyToken {
            x: u16,
        }

        #[derive(Debug, Deserialize, Serialize)]
        struct MyOtherToken {
            x: u8,
        }

        // The most basic functionality is that if we serialize something and
        // then deserialize the result of that, we get back the original thing.
        let before = MyToken { x: 1025 };
        let serialized = serialize_page_token(&before).unwrap();
        let after: MyToken = deserialize_page_token(&serialized).unwrap();
        assert_eq!(after.x, 1025);

        // We should also sanity-check that if we try to deserialize it as the
        // wrong type, that will fail.
        let error =
            deserialize_page_token::<MyOtherToken>(&serialized).unwrap_err();
        assert!(error.contains("corrupted token"));

        // Try serializing the maximum possible size.  (This was empirically
        // determined at the time of this writing.)
        #[derive(Debug, Deserialize, Serialize)]
        struct TokenWithStr {
            s: String,
        }
        let input =
            TokenWithStr { s: String::from_utf8(vec![b'e'; 352]).unwrap() };
        let serialized = serialize_page_token(&input).unwrap();
        assert_eq!(serialized.len(), super::MAX_TOKEN_LENGTH);
        let output: TokenWithStr = deserialize_page_token(&serialized).unwrap();
        assert_eq!(input.s, output.s);

        // Error cases make up the rest of this test.
        //
        // Start by attempting to serialize a token larger than the maximum
        // allowed size.
        let input =
            TokenWithStr { s: String::from_utf8(vec![b'e'; 353]).unwrap() };
        let error = serialize_page_token(&input).unwrap_err();
        assert_eq!(error.status_code, http::StatusCode::INTERNAL_SERVER_ERROR);
        assert_eq!(error.external_message, "Internal Server Error");
        assert!(error
            .internal_message
            .contains("serialized token is too large"));

        // Non-base64
        let error =
            deserialize_page_token::<TokenWithStr>("not base 64").unwrap_err();
        assert!(error.contains("failed to parse"));

        // Non-JSON
        let error =
            deserialize_page_token::<TokenWithStr>(&URL_SAFE.encode("{"))
                .unwrap_err();
        assert!(error.contains("corrupted token"));

        // Wrong top-level JSON type
        let error =
            deserialize_page_token::<TokenWithStr>(&URL_SAFE.encode("[]"))
                .unwrap_err();
        assert!(error.contains("corrupted token"));

        // Structure does not match our general Dropshot schema.
        let error =
            deserialize_page_token::<TokenWithStr>(&URL_SAFE.encode("{}"))
                .unwrap_err();
        assert!(error.contains("corrupted token"));

        // Bad version
        let error = deserialize_page_token::<TokenWithStr>(
            &URL_SAFE.encode("{\"v\":11}"),
        )
        .unwrap_err();
        assert!(error.contains("corrupted token"));
    }

    // It's worth testing parsing around PaginationParams and WhichPage because
    // is a little non-trivial, owing to the use of untagged enums (which rely
    // on the ordering of fields), some optional fields, an extra layer of
    // indirection using `TryFrom`, etc.
    //
    // This is also the primary place where we test things like non-positive
    // values of "limit" being rejected, so even though the implementation in
    // our code is trivial, this functions more like an integration or system
    // test for those parameters.
    #[test]
    fn test_pagparams_parsing() {
        #[derive(Debug, Deserialize, Serialize)]
        struct MyScanParams {
            the_field: String,
            only_good: Option<String>,
            how_many: u32,
            really: bool,
        }

        #[derive(Debug, Deserialize)]
        #[allow(dead_code)]
        struct MyOptionalScanParams {
            the_field: Option<String>,
            only_good: Option<String>,
            how_many: Option<i32>,
            for_reals: Option<bool>,
        }

        #[derive(Debug, Serialize, Deserialize)]
        struct MyPageSelector {
            the_page: u8,
        }

        // "First page" cases

        fn parse_as_first_page<T: DeserializeOwned + Debug>(
            querystring: &str,
        ) -> (T, Option<NonZeroU32>) {
            let pagparams: PaginationParams<T, MyPageSelector> =
                serde_urlencoded::from_str(querystring).unwrap();
            let limit = pagparams.limit;
            let scan_params = match pagparams.page {
                WhichPage::Next(..) => panic!("expected first page"),
                WhichPage::First(x) => x,
            };
            (scan_params, limit)
        }

        // basic case: optional boolean specified, limit unspecified
        let (scan, limit) = parse_as_first_page::<MyScanParams>(
            "the_field=name&only_good=true&how_many=42&really=false",
        );
        assert_eq!(scan.the_field, "name".to_string());
        assert_eq!(scan.only_good, Some("true".to_string()));
        assert_eq!(scan.how_many, 42);
        assert_eq!(scan.really, false);
        assert_eq!(limit, None);

        // optional boolean specified but false, limit unspecified
        let (scan, limit) = parse_as_first_page::<MyScanParams>(
            "the_field=&only_good=false&how_many=42&really=false",
        );
        assert_eq!(scan.the_field, "".to_string());
        assert_eq!(scan.only_good, Some("false".to_string()));
        assert_eq!(scan.how_many, 42);
        assert_eq!(scan.really, false);
        assert_eq!(limit, None);

        // optional boolean unspecified, limit is valid
        let (scan, limit) = parse_as_first_page::<MyScanParams>(
            "the_field=name&limit=3&how_many=42&really=false",
        );
        assert_eq!(scan.the_field, "name".to_string());
        assert_eq!(scan.only_good, None);
        assert_eq!(scan.how_many, 42);
        assert_eq!(scan.really, false);
        assert_eq!(limit.unwrap().get(), 3);

        // empty query string when all parameters are optional
        let (scan, limit) = parse_as_first_page::<MyOptionalScanParams>("");
        assert_eq!(scan.the_field, None);
        assert_eq!(scan.only_good, None);
        assert_eq!(limit, None);

        // extra parameters are fine
        let (scan, limit) = parse_as_first_page::<MyOptionalScanParams>(
            "the_field=name&limit=17&boomtown=okc&how_many=42",
        );
        assert_eq!(scan.the_field, Some("name".to_string()));
        assert_eq!(scan.only_good, None);
        assert_eq!(scan.how_many, Some(42));
        assert_eq!(limit.unwrap().get(), 17);

        // Error cases, including errors parsing first page parameters.
        //
        // TODO-polish The actual error messages for the following cases are
        // pretty poor, so we don't test them here, but we should clean these
        // up.
        fn parse_as_error(querystring: &str) -> serde_urlencoded::de::Error {
            serde_urlencoded::from_str::<
                PaginationParams<MyScanParams, MyPageSelector>,
            >(querystring)
            .unwrap_err()
        }

        // missing required field ("the_field")
        parse_as_error("");
        // invalid limit (number out of range)
        parse_as_error("the_field=name&limit=0");
        parse_as_error("the_field=name&limit=-3");
        // invalid limit (not a number)
        parse_as_error("the_field=name&limit=abcd");
        // Invalid page token (bad base64 length)
        // Other test cases for deserializing tokens are tested elsewhere.
        parse_as_error("page_token=q");

        // "Next page" cases

        fn parse_as_next_page(
            querystring: &str,
        ) -> (MyPageSelector, Option<NonZeroU32>) {
            let pagparams: PaginationParams<MyScanParams, MyPageSelector> =
                serde_urlencoded::from_str(querystring).unwrap();
            let limit = pagparams.limit;
            let page_selector = match pagparams.page {
                WhichPage::Next(x) => x,
                WhichPage::First(_) => panic!("expected next page"),
            };
            (page_selector, limit)
        }

        // basic case
        let token =
            serialize_page_token(&MyPageSelector { the_page: 123 }).unwrap();
        let (page_selector, limit) =
            parse_as_next_page(&format!("page_token={}", token));
        assert_eq!(page_selector.the_page, 123);
        assert_eq!(limit, None);

        // limit is also accepted
        let (page_selector, limit) =
            parse_as_next_page(&format!("page_token={}&limit=12", token));
        assert_eq!(page_selector.the_page, 123);
        assert_eq!(limit.unwrap().get(), 12);

        // Having parameters appropriate to the scan params doesn't change the
        // way this is interpreted.
        let (page_selector, limit) = parse_as_next_page(&format!(
            "the_field=name&page_token={}&limit=3",
            token
        ));
        assert_eq!(page_selector.the_page, 123);
        assert_eq!(limit.unwrap().get(), 3);

        // invalid limits (same as above)
        parse_as_error(&format!("page_token={}&limit=0", token));
        parse_as_error(&format!("page_token={}&limit=-3", token));

        // We ought not to promise much about what happens if the user's
        // ScanParams has a "page_token" field.  In practice, ours always takes
        // precedence (and it's not clear how else this could work).
        #[derive(Debug, Deserialize)]
        #[allow(dead_code)]
        struct SketchyScanParams {
            page_token: String,
        }

        let pagparams: PaginationParams<SketchyScanParams, MyPageSelector> =
            serde_urlencoded::from_str(&format!("page_token={}", token))
                .unwrap();
        assert_eq!(pagparams.limit, None);
        match &pagparams.page {
            WhichPage::First(..) => {
                panic!("expected NextPage even with page_token in ScanParams")
            }
            WhichPage::Next(p) => {
                assert_eq!(p.the_page, 123);
            }
        }
    }

    #[test]
    fn test_results_page() {
        // It would be a neat paginated fibonacci API if the page selector was
        // just the last two numbers!  Dropshot doesn't support that and it's
        // not clear that's a practical use case anyway.
        let items = vec![1, 1, 2, 3, 5, 8, 13];
        let dummy_scan_params = 21;
        #[derive(Debug, Deserialize, Serialize)]
        struct FibPageSelector {
            prev: usize,
        }
        let get_page = |item: &usize, scan_params: &usize| FibPageSelector {
            prev: *item + *scan_params,
        };

        let results =
            ResultsPage::new(items.clone(), &dummy_scan_params, get_page)
                .unwrap();
        assert_eq!(results.items, items);
        assert!(results.next_page.is_some());
        let token = results.next_page.unwrap();
        let deserialized: FibPageSelector =
            deserialize_page_token(&token).unwrap();
        assert_eq!(deserialized.prev, 34);

        let results =
            ResultsPage::new(Vec::new(), &dummy_scan_params, get_page).unwrap();
        assert_eq!(results.items.len(), 0);
        assert!(results.next_page.is_none());
    }

    #[derive(Deserialize, Serialize, JsonSchema)]
    struct Name {
        name: String,
    }

    #[test]
    fn test_pagination_schema() {
        let settings = schemars::gen::SchemaSettings::openapi3();
        let mut generator = schemars::gen::SchemaGenerator::new(settings);
        let schema =
            PaginationParams::<Name, Name>::json_schema(&mut generator)
                .into_object();

        assert_eq!(
            *schema
                .extensions
                .get(&(PAGINATION_PARAM_SENTINEL.to_string()))
                .unwrap(),
            json!(true)
        );
    }
}