siderite_orm/queryset/cursor/
mod.rs

1//! Cursor (keyset) pagination: [`QuerySet::after`], [`QuerySet::before`]
2//! and [`QuerySet::cursor_page`].
3//!
4//! A page is one statement: the rows past the cursor in the queryset's
5//! ordering plus one extra row, which only tells whether more rows follow.
6//! The cursor holds the ordering values of a row and a fingerprint of the
7//! queryset, so a token only fits the list it came from. See
8//! `docs/plans/CURSOR_PAGINATION.md` for the semantics.
9
10mod seek;
11mod token;
12
13use super::QuerySet;
14use crate::backend::Row;
15use crate::capabilities::Feature;
16use crate::error::{OrmError, QueryError};
17use crate::model::Model;
18use crate::value::Value;
19use seek::{Seek, Term};
20use token::Slot;
21
22/// The direction a cursor leads in.
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub(super) enum Way {
25    /// Rows after the cursor (`after`).
26    After,
27    /// Rows before the cursor (`before`).
28    Before,
29}
30
31impl Way {
32    /// The byte that marks the direction inside a token.
33    fn byte(self) -> u8 {
34        match self {
35            Self::After => b'a',
36            Self::Before => b'b',
37        }
38    }
39}
40
41/// One page of a [`QuerySet::cursor_page`] result.
42///
43/// Pass [`next`](Self::next) to [`QuerySet::after`] for the following page
44/// and [`previous`](Self::previous) to [`QuerySet::before`] for the one
45/// before. There is no total: counting is a separate query.
46#[derive(Debug, Clone, PartialEq)]
47pub struct CursorPage<M> {
48    /// Rows of this page, in the queryset's ordering.
49    pub items: Vec<M>,
50    /// Cursor for the page after this one; `None` on the last page.
51    pub next: Option<String>,
52    /// Cursor for the page before this one; `None` on the first page.
53    pub previous: Option<String>,
54}
55
56impl<M> CursorPage<M> {
57    fn empty() -> Self {
58        Self {
59            items: Vec::new(),
60            next: None,
61            previous: None,
62        }
63    }
64}
65
66/// The result of [`QuerySet::cursor_page`].
67type Fetched<M> = Result<CursorPage<M>, OrmError>;
68
69/// A token, or `None` where the page has no such neighbour.
70type Token = Result<Option<String>, QueryError>;
71
72fn missing(column: &str) -> QueryError {
73    QueryError::Decode {
74        column: column.to_owned(),
75        reason: "column missing from result".into(),
76    }
77}
78
79/// Everything needed to turn row positions into tokens.
80struct Cursors<'a> {
81    terms: &'a [Term],
82    fingerprint: u64,
83}
84
85impl Cursors<'_> {
86    /// The ordering values of `row`, in canonical form.
87    fn values(&self, row: &Row) -> Result<Vec<Value>, QueryError> {
88        self.terms
89            .iter()
90            .map(|term| {
91                let column = term.field.column;
92                let raw = row.get(column).cloned();
93                let raw = raw.ok_or_else(|| missing(column))?;
94                seek::canonical(column, term.field.sql_type, raw)
95            })
96            .collect()
97    }
98
99    /// The token for a position, if there is one.
100    fn token(&self, way: Way, values: Option<&[Value]>) -> Token {
101        let encode = |v: &[Value]| token::encode(self.fingerprint, way, v);
102        values.map(encode).transpose()
103    }
104}
105
106impl<M: Model> QuerySet<M> {
107    /// Continue after the position `token` names (a [`CursorPage::next`]).
108    ///
109    /// The last of `after` and [`before`](Self::before) wins only within
110    /// the same direction; asking for both is an error. The token is
111    /// checked by [`cursor_page`](Self::cursor_page).
112    #[must_use]
113    pub fn after(self, token: &str) -> Self {
114        self.with_cursor(Way::After, token)
115    }
116
117    /// Page backwards from the position `token` names (a
118    /// [`CursorPage::previous`]). See [`after`](Self::after).
119    #[must_use]
120    pub fn before(self, token: &str) -> Self {
121        self.with_cursor(Way::Before, token)
122    }
123
124    fn with_cursor(mut self, way: Way, token: &str) -> Self {
125        if self.cursor.as_ref().is_some_and(|(set, _)| *set != way) {
126            return self.fail("`after` and `before` cannot be combined");
127        }
128        self.cursor = Some((way, token.to_owned()));
129        self
130    }
131
132    /// One page of at most `limit` rows (at least 1) in a single
133    /// statement, without a count.
134    ///
135    /// The ordering is the queryset's `order_by` (or the model's), made
136    /// total by appending the primary key. Its terms must be columns of
137    /// the model. Nulls sort last ascending and first descending on every
138    /// backend. A cursor set with [`after`](Self::after) or
139    /// [`before`](Self::before) is validated against this queryset's
140    /// fingerprint: its filters, ordering and table.
141    ///
142    /// # Errors
143    /// [`QueryError::InvalidPlan`] for `limit == 0`, a queryset with
144    /// `distinct`, grouping, set operations, `limit`/`offset` or row
145    /// locks, or an ordering term that is not a model column;
146    /// [`OrmError::Cursor`] for a rejected token; capability errors
147    /// (Redis, and MongoDB with a nullable ordering column) and backend
148    /// errors.
149    pub async fn cursor_page(self, limit: u64) -> Fetched<M> {
150        if limit == 0 {
151            let err = QueryError::InvalidPlan("limit starts at 1".into());
152            return Err(err.into());
153        }
154        self.ready()?;
155        if self.empty {
156            return Ok(CursorPage::empty());
157        }
158        let caps = self.db.capabilities();
159        caps.require(Feature::KeysetPagination)?;
160        self.plan.check(&caps)?;
161        seek::check_shape(&self.plan)?;
162        let terms = seek::terms::<M>(&self.plan)?;
163        if terms.iter().any(|t| t.field.nullable) {
164            caps.require(Feature::NullableKeyset)?;
165        }
166        let print = seek::fingerprint(&self.plan, &terms);
167        let cursors = Cursors {
168            terms: &terms,
169            fingerprint: print,
170        };
171        let slots: Vec<Slot> = terms.iter().map(Term::slot).collect();
172        let (way, at) = match &self.cursor {
173            None => (Way::After, None),
174            Some((way, raw)) => {
175                let values = token::decode(raw, print, *way, &slots)?;
176                (*way, Some(values))
177            }
178        };
179        let backward = way == Way::Before;
180        let seek = Seek::new(&self.plan, &terms).backwards(backward);
181        let order = seek.ordering();
182        let predicate = at.as_deref().map(|values| seek.predicate(values));
183        let paged = self.with_plan(|mut plan| {
184            plan.ordering = order;
185            if let Some(predicate) = predicate {
186                plan = plan.filter(predicate);
187            }
188            plan.limit(limit.saturating_add(1))
189        });
190        let mut rows = paged.db.fetch(&paged.plan).await?.rows;
191        let size = usize::try_from(limit).unwrap_or(usize::MAX);
192        let more = rows.len() > size;
193        rows.truncate(size);
194        if backward {
195            rows.reverse();
196        }
197        let first = rows.first().map(|row| cursors.values(row)).transpose()?;
198        let last = rows.last().map(|row| cursors.values(row)).transpose()?;
199        let items = paged
200            .decode_rows(rows)
201            .await?
202            .into_iter()
203            .map(|(model, _)| model)
204            .collect();
205        let (next, previous) = if backward {
206            let previous = if more { first.as_deref() } else { None };
207            let next = last.as_deref().or(at.as_deref());
208            (next, previous)
209        } else {
210            let next = if more { last.as_deref() } else { None };
211            let previous = at.as_ref().and(first.as_deref().or(at.as_deref()));
212            (next, previous)
213        };
214        let next = cursors.token(Way::After, next)?;
215        let previous = cursors.token(Way::Before, previous)?;
216        Ok(CursorPage {
217            items,
218            next,
219            previous,
220        })
221    }
222}
223
224#[cfg(test)]
225mod tests;
siderite_orm/queryset/cursor/mod.rs

siderite_orm/queryset/cursor/
mod.rs
