cratestack_sql/
keyset.rs

1//! Keyset (cursor) pagination primitives, dialect-agnostic so the Postgres
2//! and embedded backends share one definition
3//! (`docs/design/cursor-pagination.md`).
4//!
5//! A keyset page is "the rows strictly after the last row of the previous
6//! page, in the query's sort order". [`parse_keyset_sort`] resolves a
7//! `sort` expression into ordered [`KeysetColumn`]s with the primary key
8//! appended as a unique tiebreaker; [`keyset_after`] turns the last row's
9//! values into an ordinary [`FilterExpr`] to `AND` into the query — so the
10//! bound composes with filters and read policy rather than replacing them.
11//! All ordering uses the framework's `NULLS LAST` default
12//! ([`crate::NullOrder`]).
13
14use cratestack_core::CratestackError;
15
16use crate::FilterExpr;
17
18#[derive(Debug, Clone, PartialEq, Eq)]
19pub struct KeysetColumn {
20    pub name: String,
21    pub descending: bool,
22    pub nullable: bool,
23}
24
25/// One comparison the caller must turn into a typed filter on `column`.
26#[derive(Debug, Clone, Copy)]
27pub enum KeysetLeaf<'a, V> {
28    Eq(&'a V),
29    Gt(&'a V),
30    Lt(&'a V),
31    IsNull,
32}
33
34/// Resolve `sort` (`"-createdAt,name"`; `None` = unsorted) into keyset
35/// columns, appending `primary_key` ascending when absent so the order is
36/// total. `nullable_of` returns `Some(is_nullable)` for a sortable scalar
37/// column and `None` for anything else. Relation-path (`a.b`) terms,
38/// unknown or duplicate columns and empty terms are `BadRequest`.
39pub fn parse_keyset_sort(
40    sort: Option<&str>,
41    primary_key: &str,
42    nullable_of: impl Fn(&str) -> Option<bool>,
43) -> Result<Vec<KeysetColumn>, CratestackError> {
44    let mut columns: Vec<KeysetColumn> = Vec::new();
45    for raw in sort.into_iter().flat_map(|sort| sort.split(',')) {
46        let raw = raw.trim();
47        let (descending, name) = match raw.strip_prefix('-') {
48            Some(name) => (true, name),
49            None => (false, raw),
50        };
51        if name.is_empty() {
52            return Err(CratestackError::BadRequest(
53                "sort must not contain empty fields".to_owned(),
54            ));
55        }
56        if name.contains('.') {
57            return Err(CratestackError::BadRequest(format!(
58                "cursor pagination does not support relation-path sort '{name}'"
59            )));
60        }
61        let Some(nullable) = nullable_of(name) else {
62            return Err(CratestackError::BadRequest(format!(
63                "cursor pagination does not support sort field '{name}'"
64            )));
65        };
66        if columns.iter().any(|column| column.name == name) {
67            return Err(CratestackError::BadRequest(format!(
68                "sort field '{name}' is repeated"
69            )));
70        }
71        columns.push(KeysetColumn {
72            name: name.to_owned(),
73            descending,
74            nullable,
75        });
76    }
77    if !columns.iter().any(|column| column.name == primary_key) {
78        columns.push(KeysetColumn {
79            name: primary_key.to_owned(),
80            descending: false,
81            nullable: false,
82        });
83    }
84    Ok(columns)
85}
86
87/// Canonical effective-order string (`"-createdAt,id"`) a cursor is bound to.
88pub fn keyset_order_spec(columns: &[KeysetColumn]) -> String {
89    columns
90        .iter()
91        .map(|column| {
92            if column.descending {
93                format!("-{}", column.name)
94            } else {
95                column.name.clone()
96            }
97        })
98        .collect::<Vec<_>>()
99        .join(",")
100}
101
102/// Filter selecting the rows strictly after the row whose per-column
103/// values are `values` (`None` = `NULL`), expanded as
104/// `OR_i (c_0 = v_0 AND … AND c_{i-1} = v_{i-1} AND c_i AFTER v_i)`.
105/// With `NULLS LAST`, a non-null `v_i` on a nullable column is also
106/// followed by every `NULL`; a `NULL` `v_i` has nothing after it in that
107/// column (only ties, handled by the next term). `leaf` builds the typed
108/// comparison — the caller owns value parsing, so a bad value fails here
109/// exactly as the same value in a `?col__gt=` filter would.
110pub fn keyset_after<V, E>(
111    columns: &[KeysetColumn],
112    values: &[Option<V>],
113    mut leaf: impl FnMut(&str, KeysetLeaf<'_, V>) -> Result<FilterExpr, E>,
114) -> Result<FilterExpr, E>
115where
116    E: From<CratestackError>,
117{
118    if columns.len() != values.len() || columns.is_empty() {
119        return Err(
120            CratestackError::BadRequest("cursor does not match the sort order".to_owned()).into(),
121        );
122    }
123    let mut terms = Vec::new();
124    for (index, (column, value)) in columns.iter().zip(values).enumerate() {
125        let Some(value) = value else { continue };
126        let mut conjuncts = Vec::with_capacity(index + 1);
127        for (prior, prior_value) in columns[..index].iter().zip(values) {
128            conjuncts.push(match prior_value {
129                Some(prior_value) => leaf(&prior.name, KeysetLeaf::Eq(prior_value))?,
130                None => leaf(&prior.name, KeysetLeaf::IsNull)?,
131            });
132        }
133        let strictly_after = if column.descending {
134            leaf(&column.name, KeysetLeaf::Lt(value))?
135        } else {
136            leaf(&column.name, KeysetLeaf::Gt(value))?
137        };
138        conjuncts.push(if column.nullable {
139            FilterExpr::any([strictly_after, leaf(&column.name, KeysetLeaf::IsNull)?])
140        } else {
141            strictly_after
142        });
143        terms.push(FilterExpr::all(conjuncts));
144    }
145    Ok(FilterExpr::any(terms))
146}
147
148#[cfg(test)]
149#[path = "keyset_tests.rs"]
150mod tests;
cratestack_sql/keyset.rs

cratestack_sql/
keyset.rs
