Skip to main content

sui_rpc_api/ledger_history/
query_options.rs

1// Copyright (c) Mysten Labs, Inc.
2// SPDX-License-Identifier: Apache-2.0
3
4use std::ops::{Bound, Range};
5
6use bytes::Bytes;
7use sui_inverted_index::ScanDirection;
8use sui_rpc::proto::sui::rpc::v2::Ordering as ProtoOrdering;
9use sui_rpc::proto::sui::rpc::v2::QueryOptions as ProtoQueryOptions;
10
11use crate::ErrorDetails;
12use crate::ErrorReason;
13use crate::RpcError;
14use crate::ledger_history::cursor::CursorKind;
15use crate::ledger_history::cursor::CursorToken;
16use crate::ledger_history::cursor::LedgerPoint;
17use crate::ledger_history::cursor::Position;
18use crate::ledger_history::watermark::RangeEnd;
19use crate::proto::google::rpc::ErrorInfo;
20use crate::proto::google::rpc::bad_request::FieldViolation;
21
22const ORDERING_ASCENDING: i32 = ProtoOrdering::Ascending as i32;
23const ORDERING_DESCENDING: i32 = ProtoOrdering::Descending as i32;
24
25#[derive(Clone, Copy, Debug, Eq, PartialEq, serde::Serialize, serde::Deserialize)]
26pub enum Ordering {
27    Ascending,
28    Descending,
29}
30
31/// Intra-transaction coordinate: a transaction and an index within it
32/// (events today; any per-transaction-indexed lane). Boundary cursors may
33/// point at slots with no item.
34#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
35pub struct IntraTxCoordinate {
36    pub tx_seq: u64,
37    pub index: u32,
38}
39
40/// Why a resolved scan interval is exhausted. Fixed at range-resolution time,
41/// carried through scan state, and rendered by [`ScanTerminal`].
42///
43/// [`ScanTerminal`]: crate::ledger_history::watermark::ScanTerminal
44#[derive(Clone, Copy, Debug, Eq, PartialEq)]
45pub enum RangeExhaustion {
46    /// Reached the currently indexed ledger tip.
47    LedgerTip,
48    /// Reached the requested (or implicit-genesis) checkpoint range bound.
49    CheckpointBound,
50    /// Truncated by a client `after`/`before` cursor. `kind` is the cursor kind the terminal
51    /// cursor must carry so resume neither repeats nor skips an item: Item only for an `after`
52    /// Item cursor at the last position, which has no next position to name as a boundary;
53    /// Boundary everywhere else.
54    CursorBound { kind: CursorKind },
55    /// A descending scan with no lower bound of its own reached this server's serving floor, the
56    /// lowest checkpoint it still serves; everything below is pruned. The stream sends a watermark
57    /// at the floor claiming `floor_checkpoint`, then fails with `OutOfRange` (see
58    /// [`below_serving_floor`]) instead of ending with a `QueryEnd`.
59    ServingFloor { floor_checkpoint: u64 },
60}
61
62/// Validated, normalized form of `QueryOptions` (the proto wire type).
63#[derive(Clone, Debug, Eq, PartialEq)]
64pub struct QueryOptions {
65    pub limit_items: usize,
66    pub ordering: Ordering,
67    after: Option<CursorToken>,
68    before: Option<CursorToken>,
69}
70
71/// A request's checkpoint window resolved into the checkpoint-sequence interval to scan. Cursors
72/// do not narrow it: [`ResolvedScan::resolve`] applies them by scan position. Unlike
73/// [`ResolvedScan<u64>`]/[`ResolvedScan<IntraTxCoordinate>`], the scan domain here *is*
74/// checkpoint space, so the entry and terminal checkpoints derive from `range` directly and need
75/// no extra fields.
76#[derive(Clone, Debug, Eq, PartialEq)]
77pub struct ResolvedCheckpointRange {
78    /// Half-open checkpoint-sequence interval to scan (numeric order; a
79    /// descending scan walks it from `end - 1` down to `start`).
80    pub range: Range<u64>,
81    /// Why the interval is exhausted once the scan drains it.
82    pub exhaustion: RangeExhaustion,
83    /// Whether `range.end` is this server's indexed tip rather than a bound the request set, so
84    /// that a position at or past it is one this server has not indexed.
85    pub reaches_ledger_tip: bool,
86}
87
88/// Semantic scan bounds over explicit scan positions (cursor trims need
89/// exclusive bounds on either side).
90#[derive(Clone, Copy, Debug, Eq, PartialEq)]
91pub struct ScanBounds<P> {
92    pub lo: Bound<P>,
93    pub hi: Bound<P>,
94}
95
96pub type IntraTxScanBounds = ScanBounds<IntraTxCoordinate>;
97
98/// A request's checkpoint window in a lane's scan-position space, narrowed to the request's start
99/// and end positions inside the window's edge checkpoints (see
100/// [`CheckpointPositions`](crate::ledger_history::checkpoint_positions::CheckpointPositions)).
101#[derive(Clone, Debug, Eq, PartialEq)]
102pub struct ScanWindow<P> {
103    /// Half-open scan-position interval. A start position past the end position leaves it
104    /// inverted.
105    pub range: Range<P>,
106    /// Whether `range.start` is not the first position of the window's first checkpoint, so the
107    /// window may leave part of that checkpoint out. An event index past its transaction's events
108    /// sets it even where it leaves nothing out, which only makes coverage claims conservative.
109    pub start_cuts_checkpoint: bool,
110    /// Whether `range.end` is not the end of the window's last checkpoint, so the window may leave
111    /// part of that checkpoint out. As for `start_cuts_checkpoint`, an event index past its
112    /// transaction's events sets it even where it leaves nothing out.
113    pub end_cuts_checkpoint: bool,
114    /// The same window in ledger coordinates.
115    pub ledger: LedgerWindow,
116}
117
118/// A request's window in ledger coordinates, for placing the resume point of a scan's terminal
119/// frame, and the public position of its cursor, where the window names it (see
120/// [`ResolvedScan::end_resume_position`] and [`ResolvedScan::end_cursor_public_position`]).
121#[derive(Clone, Copy, Debug, Eq, PartialEq)]
122pub struct LedgerWindow {
123    /// The point of [`ScanWindow::range`]'s start.
124    pub start: LedgerPoint,
125    /// The point of [`ScanWindow::range`]'s end.
126    pub end: LedgerPoint,
127    /// For a window that holds no checkpoint (the request's checkpoint window, clamped to this
128    /// server's tip, holds none), the points the request's own start and end fields name, where
129    /// its terminal frame resumes ascending and descending: the start not clamped to this
130    /// server's tip (an unset field counting as 0), and the end when the request set
131    /// `end_checkpoint`, else `end`. `None` for a window that holds a checkpoint.
132    pub requested: Option<(LedgerPoint, LedgerPoint)>,
133}
134
135/// A request's checkpoint bounds resolved into the scan-position interval to scan, along with the
136/// checkpoint-space facts for watermark rendering.
137#[derive(Clone, Debug, Eq, PartialEq)]
138pub struct ResolvedScan<P> {
139    /// Scan-position interval to scan, expressed as explicit lo/hi
140    /// [`Bound`]s.
141    pub bounds: ScanBounds<P>,
142    /// The window's first checkpoint in scan direction, raised to the serving floor for an
143    /// ascending scan. No coverage claim passes it. Cursors do not move it: a cursor vouches for
144    /// every position before it in scan order, so a scan claims each checkpoint whose end it
145    /// reaches, wherever its cursor started.
146    pub entry_checkpoint: u64,
147    /// The public position of `end_scan_position`, unless a request cursor names that position
148    /// (see [`ResolvedScan::end_cursor_public_position`]): the window's edge, the serving floor,
149    /// or where the request cursor that ends the scan resumes.
150    pub end_public_position: LedgerPoint,
151    /// Scan-direction terminal edge of the interval, in the lane's private scan order: a
152    /// `tx_seq`, a `(tx_seq, event_index)`, or a checkpoint.
153    pub end_scan_position: P,
154    /// Why the interval is exhausted once the scan drains it.
155    pub exhaustion: RangeExhaustion,
156    /// The checkpoint a scan that drains the window reports as fully covered: the window's last
157    /// checkpoint in scan direction, or the one before it in scan direction where a request
158    /// position cuts it, which lies outside a one-checkpoint window
159    /// ([`ResolvedScan::natural_end_claim`] drops such a claim). `None` when the window holds no
160    /// checkpoint, when the checkpoint before it would precede genesis, or when an ascending
161    /// scan's `after` cursor resumes past the ledger tip (see [`ResolvedScan::resolve`]).
162    /// Cursors do not move it: a non-empty window's natural end claims its edge even when the
163    /// scan reads nothing, because the request's starting cursor vouches for every position
164    /// before it.
165    pub window_claim: Option<u64>,
166}
167
168/// How a lane reads wire cursors: the token's coordinate in the lane's
169/// position space.
170pub trait ScanCursor<P> {
171    fn coordinate(&self) -> P;
172}
173
174/// A scan position with a successor, so scan bounds can tell exactly whether they admit any
175/// position.
176pub trait ScanPosition: Copy + Ord {
177    /// The next position in scan order, if there is one.
178    fn successor(self) -> Option<Self>;
179}
180
181impl ScanPosition for u64 {
182    fn successor(self) -> Option<Self> {
183        self.checked_add(1)
184    }
185}
186
187impl ScanPosition for IntraTxCoordinate {
188    fn successor(self) -> Option<Self> {
189        match self.index.checked_add(1) {
190            Some(index) => Some(Self {
191                tx_seq: self.tx_seq,
192                index,
193            }),
194            None => self.tx_seq.checked_add(1).map(Self::start_of_tx),
195        }
196    }
197}
198
199impl IntraTxCoordinate {
200    /// Fencepost at the first event slot of `tx_seq`; valid as a boundary even
201    /// if the transaction has no events.
202    pub fn start_of_tx(tx_seq: u64) -> Self {
203        Self { tx_seq, index: 0 }
204    }
205}
206
207/// The error for a request that needs data below this server's serving floor, whose lowest
208/// available checkpoint is `floor_checkpoint`: that data is pruned and permanently gone.
209/// It is `OutOfRange` with a `BELOW_EARLIEST_AVAILABLE` [`ErrorInfo`] whose
210/// `lowestAvailableCheckpoint` is `floor_checkpoint`; retrying it on this server fails the same
211/// way.
212pub fn below_serving_floor(floor_checkpoint: u64) -> RpcError {
213    let error_info = ledger_error_info(
214        ErrorReason::BelowEarliestAvailable,
215        [("lowestAvailableCheckpoint", floor_checkpoint.to_string())],
216    );
217    RpcError::new(
218        tonic::Code::OutOfRange,
219        format!(
220            "requested data below earliest available; lowest available checkpoint is {floor_checkpoint}"
221        ),
222    )
223    .with_details(ErrorDetails::new().with_error_info(error_info))
224}
225
226/// The error for a request that needs versions of an object (a package, for one) below
227/// `oldest_retained_version`, the oldest one this server keeps: the object's version at the end of
228/// `floor_checkpoint`, the lowest checkpoint whose object state it keeps. Older versions are
229/// pruned and permanently gone. It is [`below_serving_floor`] for `floor_checkpoint`, with the
230/// version as `lowestAvailableVersion` too, so a client can list from it instead.
231pub fn below_oldest_retained_version(
232    floor_checkpoint: u64,
233    oldest_retained_version: u64,
234) -> RpcError {
235    let error_info = ledger_error_info(
236        ErrorReason::BelowEarliestAvailable,
237        [
238            ("lowestAvailableCheckpoint", floor_checkpoint.to_string()),
239            (
240                "lowestAvailableVersion",
241                oldest_retained_version.to_string(),
242            ),
243        ],
244    );
245    RpcError::new(
246        tonic::Code::OutOfRange,
247        format!(
248            "requested object versions below earliest available; lowest available checkpoint is \
249             {floor_checkpoint}, and lowest available version is {oldest_retained_version}"
250        ),
251    )
252    .with_details(ErrorDetails::new().with_error_info(error_info))
253}
254
255/// The error for a request that reads above the data this server has indexed, all of which lies
256/// below `checkpoint_hi_exclusive`. `bound` names what reads past it: "cursor" for an `after` or
257/// `before` cursor, or the request field, such as "start_checkpoint", "end_checkpoint" or
258/// "at_checkpoint"; `requested_checkpoint` is the checkpoint of the cursor's public position or
259/// the field's value. It is `OutOfRange` with an `ABOVE_LATEST_AVAILABLE` [`ErrorInfo`] carrying
260/// all three, by which clients recognize a request that becomes servable once this server
261/// catches up.
262pub(crate) fn above_latest_available(
263    bound: &str,
264    requested_checkpoint: u64,
265    checkpoint_hi_exclusive: u64,
266) -> RpcError {
267    let message = if bound == "cursor" {
268        format!(
269            "requested data above latest available; cursor is at checkpoint \
270             {requested_checkpoint}, and only checkpoints below {checkpoint_hi_exclusive} are \
271             available"
272        )
273    } else {
274        format!(
275            "requested data above latest available; {bound} is {requested_checkpoint}, and only \
276             checkpoints below {checkpoint_hi_exclusive} are available"
277        )
278    };
279    let error_info = ledger_error_info(
280        ErrorReason::AboveLatestAvailable,
281        [
282            ("bound", bound.to_owned()),
283            ("requestedCheckpoint", requested_checkpoint.to_string()),
284            (
285                "firstUnavailableCheckpoint",
286                checkpoint_hi_exclusive.to_string(),
287            ),
288        ],
289    );
290    RpcError::new(tonic::Code::OutOfRange, message)
291        .with_details(ErrorDetails::new().with_error_info(error_info))
292}
293
294/// An [`ErrorInfo`] in the [`ErrorReason::DOMAIN`] domain with `reason` and `metadata`.
295pub(crate) fn ledger_error_info<const N: usize>(
296    reason: ErrorReason,
297    metadata: [(&str, String); N],
298) -> ErrorInfo {
299    let metadata = metadata
300        .into_iter()
301        .map(|(key, value)| (key.to_owned(), value))
302        .collect();
303    ErrorInfo::default()
304        .with_reason(reason.as_str_name())
305        .with_domain(ErrorReason::DOMAIN)
306        .with_metadata(metadata)
307}
308
309impl QueryOptions {
310    pub fn checkpoints_from_proto(
311        request: Option<&ProtoQueryOptions>,
312        default_limit_items: u32,
313        max_limit_items: u32,
314    ) -> Result<Self, RpcError> {
315        Self::from_proto_with_position(request, default_limit_items, max_limit_items, |position| {
316            matches!(position, Position::Checkpoints { .. })
317        })
318    }
319
320    pub fn transactions_from_proto(
321        request: Option<&ProtoQueryOptions>,
322        default_limit_items: u32,
323        max_limit_items: u32,
324    ) -> Result<Self, RpcError> {
325        Self::from_proto_with_position(request, default_limit_items, max_limit_items, |position| {
326            matches!(position, Position::Transactions { .. })
327        })
328    }
329
330    pub fn events_from_proto(
331        request: Option<&ProtoQueryOptions>,
332        default_limit_items: u32,
333        max_limit_items: u32,
334    ) -> Result<Self, RpcError> {
335        Self::from_proto_with_position(request, default_limit_items, max_limit_items, |position| {
336            matches!(position, Position::Events { .. })
337        })
338    }
339
340    fn from_proto_with_position(
341        request: Option<&ProtoQueryOptions>,
342        default_limit_items: u32,
343        max_limit_items: u32,
344        position_matches: fn(&Position) -> bool,
345    ) -> Result<Self, RpcError> {
346        let limit_items = request
347            .and_then(|options| options.limit)
348            .unwrap_or(default_limit_items)
349            .clamp(1, max_limit_items) as usize;
350
351        let ordering = match request.and_then(|options| options.ordering) {
352            None | Some(ORDERING_ASCENDING) => Ordering::Ascending,
353            Some(ORDERING_DESCENDING) => Ordering::Descending,
354            Some(_) => {
355                return Err(FieldViolation::new("options.ordering")
356                    .with_description("invalid ordering")
357                    .with_reason(ErrorReason::FieldInvalid)
358                    .into());
359            }
360        };
361
362        let after = parse_cursor(
363            "options.after",
364            request.and_then(|options| options.after.as_ref()),
365            position_matches,
366        )?;
367        let before = parse_cursor(
368            "options.before",
369            request.and_then(|options| options.before.as_ref()),
370            position_matches,
371        )?;
372
373        Ok(Self {
374            limit_items,
375            ordering,
376            after,
377            before,
378        })
379    }
380
381    /// Options for a subscription stream: an unbounded ascending scan with no
382    /// cursor bounds. The ascending direction is consulted by the watermark
383    /// builders; `limit_items` is irrelevant.
384    pub fn subscription() -> Self {
385        Self {
386            limit_items: usize::MAX,
387            ordering: Ordering::Ascending,
388            after: None,
389            before: None,
390        }
391    }
392
393    pub fn scan_direction(&self) -> ScanDirection {
394        match self.ordering {
395            Ordering::Ascending => ScanDirection::Ascending,
396            Ordering::Descending => ScanDirection::Descending,
397        }
398    }
399
400    pub fn is_ascending(&self) -> bool {
401        matches!(self.ordering, Ordering::Ascending)
402    }
403
404    /// Whether the request explicitly positioned the low end of the scan via an
405    /// `after` cursor. `apply_cursor_bounds` only ever raises `range.start` from
406    /// `after` (in both orderings); `before` bounds the high end. Together with an
407    /// explicit `start_checkpoint`, this lets the pruning-floor check distinguish
408    /// "resume/start from here" (error if below the floor — the data is gone) from
409    /// an open-ended low end (clamp up to the floor).
410    pub fn has_after_cursor(&self) -> bool {
411        self.after.is_some()
412    }
413}
414
415impl ResolvedCheckpointRange {
416    pub fn empty_at(
417        checkpoint: u64,
418        exhaustion: RangeExhaustion,
419        reaches_ledger_tip: bool,
420    ) -> Self {
421        Self {
422            range: checkpoint..checkpoint,
423            exhaustion,
424            reaches_ledger_tip,
425        }
426    }
427
428    pub fn is_empty(&self) -> bool {
429        self.range.is_empty()
430    }
431}
432
433impl<P> ScanWindow<P> {
434    /// A window whose edges are checkpoint boundaries, `ledger` in ledger coordinates.
435    pub fn whole_checkpoints(range: Range<P>, ledger: LedgerWindow) -> Self {
436        Self {
437            range,
438            start_cuts_checkpoint: false,
439            end_cuts_checkpoint: false,
440            ledger,
441        }
442    }
443}
444
445impl LedgerWindow {
446    /// The window of a checkpoint scan over `range`, the request's checkpoint window
447    /// `start_checkpoint..end_checkpoint` clamped to this server's tip.
448    pub fn checkpoints(
449        range: &Range<u64>,
450        start_checkpoint: Option<u64>,
451        end_checkpoint: Option<u64>,
452    ) -> Self {
453        let start = LedgerPoint::checkpoint_start(range.start);
454        let end = LedgerPoint::checkpoint_start(range.end);
455        let requested = range.is_empty().then(|| {
456            (
457                LedgerPoint::checkpoint_start(start_checkpoint.unwrap_or(0)),
458                LedgerPoint::checkpoint_start(end_checkpoint.unwrap_or(range.end)),
459            )
460        });
461        Self {
462            start,
463            end,
464            requested,
465        }
466    }
467}
468
469impl ResolvedScan<u64> {
470    /// Collapse the symbolic bounds to the half-open store range.
471    pub fn range(&self) -> Range<u64> {
472        self.bounds.to_range()
473    }
474}
475
476impl<P: Copy + Ord> ScanBounds<P> {
477    pub fn from_range(range: Range<P>) -> Self {
478        Self {
479            lo: Bound::Included(range.start),
480            hi: Bound::Excluded(range.end),
481        }
482    }
483
484    pub fn empty_at(position: P) -> Self {
485        Self {
486            lo: Bound::Included(position),
487            hi: Bound::Excluded(position),
488        }
489    }
490
491    pub fn is_empty(&self) -> bool {
492        match (self.lo, self.hi) {
493            (Bound::Included(a), Bound::Excluded(b))
494            | (Bound::Excluded(a), Bound::Excluded(b))
495            | (Bound::Excluded(a), Bound::Included(b)) => a >= b,
496            (Bound::Included(a), Bound::Included(b)) => a > b,
497            (Bound::Unbounded, _) | (_, Bound::Unbounded) => false,
498        }
499    }
500
501    pub fn contains(&self, position: P) -> bool {
502        let above_lo = match self.lo {
503            Bound::Included(lo) => position >= lo,
504            Bound::Excluded(lo) => position > lo,
505            Bound::Unbounded => true,
506        };
507        let below_hi = match self.hi {
508            Bound::Included(hi) => position <= hi,
509            Bound::Excluded(hi) => position < hi,
510            Bound::Unbounded => true,
511        };
512        above_lo && below_hi
513    }
514}
515
516impl<P: ScanPosition> ScanBounds<P> {
517    /// Whether no position lies within the bounds. [`Self::is_empty`] compares the bounds
518    /// symbolically, so it keeps an exclusive low bound right below an exclusive high bound;
519    /// this resolves the low bound to its successor first.
520    pub fn admits_no_position(&self) -> bool {
521        let lo = match self.lo {
522            Bound::Excluded(position) => match position.successor() {
523                Some(successor) => Bound::Included(successor),
524                None => return true,
525            },
526            lo => lo,
527        };
528        ScanBounds { lo, hi: self.hi }.is_empty()
529    }
530}
531
532impl ScanBounds<u64> {
533    pub fn to_range(&self) -> Range<u64> {
534        let start = match self.lo {
535            Bound::Included(position) => position,
536            Bound::Excluded(position) => position.saturating_add(1),
537            Bound::Unbounded => 0,
538        };
539        let end = match self.hi {
540            Bound::Included(position) => position.saturating_add(1),
541            Bound::Excluded(position) => position,
542            Bound::Unbounded => u64::MAX,
543        };
544        start..end
545    }
546}
547
548impl ScanBounds<IntraTxCoordinate> {
549    /// Smallest half-open tx range covering every position these bounds could
550    /// admit. An exclusive `hi` at the start of tx N excludes tx N entirely;
551    /// any other bounded endpoint keeps its transaction, since earlier events
552    /// of that tx may still be in bounds. `None` when no tx can qualify.
553    pub fn tx_range(&self) -> Option<Range<u64>> {
554        let start_tx = match self.lo {
555            Bound::Included(position) | Bound::Excluded(position) => position.tx_seq,
556            Bound::Unbounded => 0,
557        };
558        let end_tx = match self.hi {
559            Bound::Excluded(position) if position.index == 0 => position.tx_seq,
560            Bound::Included(position) | Bound::Excluded(position) => {
561                position.tx_seq.saturating_add(1)
562            }
563            Bound::Unbounded => u64::MAX,
564        };
565        (start_tx < end_tx).then_some(start_tx..end_tx)
566    }
567}
568
569impl<P: ScanPosition> ResolvedScan<P>
570where
571    CursorToken: ScanCursor<P>,
572{
573    /// Record the request's checkpoint bounds, then apply cursor bounds to tighten the `window`
574    /// scanning interval. Cursors bound the scan by position alone; their public positions only
575    /// label the cursors this scan hands back. If the backend data source has a serving floor,
576    /// `apply_serving_floor` must be called to reconcile the scanning interval.
577    ///
578    /// The window's request positions and its cursors bound the scan by intersection. A position
579    /// that cuts the window's first checkpoint in scan direction acts as a starting cursor does:
580    /// it vouches for every position before it, so the scan still claims that checkpoint once it
581    /// reaches its end. A position that cuts the window's last checkpoint in scan direction acts as
582    /// a far cursor does: the scan never reaches that checkpoint's end, so its natural end does not
583    /// claim it.
584    ///
585    /// In a window that reaches the ledger tip, empty or not, an ascending scan whose `after`
586    /// cursor resumes past the tip ends empty where that cursor resumes, or at a `before` cursor
587    /// at or below that position, and claims no checkpoint.
588    pub fn resolve(
589        cp_range: ResolvedCheckpointRange,
590        window: ScanWindow<P>,
591        options: &QueryOptions,
592    ) -> Result<Self, RpcError> {
593        let ScanWindow {
594            range,
595            start_cuts_checkpoint,
596            end_cuts_checkpoint,
597            ledger,
598        } = window;
599        if cp_range.reaches_ledger_tip {
600            reject_descending_cursors_past_tip(options, range.end, cp_range.range.end)?;
601        }
602
603        // Positions that cross leave nothing between them: collapse the window onto its terminal
604        // edge in scan direction.
605        let range = match options.ordering {
606            _ if range.start <= range.end => range,
607            Ordering::Ascending => range.end..range.end,
608            Ordering::Descending => range.start..range.start,
609        };
610
611        let entry_checkpoint = if cp_range.is_empty() {
612            // No checkpoint entered, pin entry to terminal boundary
613            cp_range.range.end
614        } else if options.is_ascending() {
615            cp_range.range.start
616        } else {
617            cp_range.range.end - 1
618        };
619
620        let window_claim = if cp_range.is_empty() {
621            None
622        } else {
623            match options.ordering {
624                Ordering::Ascending => cp_range
625                    .range
626                    .end
627                    .checked_sub(1 + u64::from(end_cuts_checkpoint)),
628                Ordering::Descending => {
629                    Some(cp_range.range.start + u64::from(start_cuts_checkpoint))
630                }
631            }
632        };
633
634        let (end_scan_position, end_public_position) = match options.ordering {
635            Ordering::Ascending => (range.end, ledger.end),
636            Ordering::Descending => (range.start, ledger.start),
637        };
638        let resolved = Self {
639            bounds: ScanBounds::from_range(range.start..range.end),
640            entry_checkpoint,
641            end_public_position,
642            end_scan_position,
643            exhaustion: cp_range.exhaustion,
644            window_claim,
645        }
646        .apply_cursor_bounds(options);
647
648        if cp_range.reaches_ledger_tip
649            && let Some((point, position, exhaustion)) =
650                ascending_after_past_tip_end(options, range.end)
651        {
652            // The client's coverage already reaches past this server's tip, so a claim from this
653            // view could only lower it.
654            return Ok(Self {
655                bounds: ScanBounds::empty_at(position),
656                end_public_position: point,
657                end_scan_position: position,
658                exhaustion,
659                window_claim: None,
660                ..resolved
661            });
662        }
663
664        if !cp_range.is_empty()
665            && resolved.bounds.admits_no_position()
666            && let Some((point, position)) = starting_cursor_end(options, &range)
667        {
668            // The starting cursor leaves the window nothing to scan, and no far cursor stops the
669            // scan first: the page ends with the window's reason, where `starting_cursor_end`
670            // places it. A far cursor at or before the window's edge ends the page instead.
671            return Ok(Self {
672                bounds: ScanBounds::empty_at(position),
673                end_public_position: point,
674                end_scan_position: position,
675                exhaustion: cp_range.exhaustion,
676                ..resolved
677            });
678        }
679        Ok(resolved)
680    }
681
682    pub fn is_empty(&self) -> bool {
683        self.bounds.is_empty()
684    }
685
686    /// The checkpoint this scan's natural end reports as fully covered in `Watermark.checkpoint`:
687    /// the window's last checkpoint in scan direction, just below its exclusive upper edge
688    /// ascending, or its inclusive lower edge descending. A scan that drains its window has
689    /// covered every checkpoint up to that edge, and so has a scan its starting cursor leaves
690    /// empty, because the cursor vouches for every position before it. A request position that
691    /// cuts that last checkpoint moves the claim to the checkpoint before it in scan direction.
692    /// `None` when the window has no checkpoint, when an ascending scan's `after` cursor resumes
693    /// past the ledger tip, or when the claim would precede `entry_checkpoint`.
694    pub fn natural_end_claim(&self, options: &QueryOptions) -> Option<u64> {
695        let claim = self.window_claim?;
696        match options.ordering {
697            Ordering::Ascending => Some(claim).filter(|claim| *claim >= self.entry_checkpoint),
698            Ordering::Descending => Some(claim).filter(|claim| *claim <= self.entry_checkpoint),
699        }
700    }
701
702    /// Where this scan ends once it drains its range, as its terminal frame renders it: its
703    /// reason, the terminal cursor `position_at` builds from the end's scan position and public
704    /// position (see [`Self::end_cursor_public_position`]), where the frame resumes in ledger
705    /// coordinates (see [`Self::end_resume_position`]), and the natural end's claim (see
706    /// [`Self::natural_end_claim`]). `window` is the window this scan was resolved from.
707    pub fn range_end(
708        &self,
709        window: &ScanWindow<P>,
710        options: &QueryOptions,
711        position_at: impl FnOnce(P, LedgerPoint) -> Position,
712    ) -> RangeEnd {
713        RangeEnd {
714            exhaustion: self.exhaustion,
715            position: position_at(
716                self.end_scan_position,
717                self.end_cursor_public_position(options),
718            ),
719            cursor_position: self.end_resume_position(window, options),
720            natural_end_claim: self.natural_end_claim(options),
721        }
722    }
723
724    /// The public position of this scan's terminal cursor, at its end scan position: that of a
725    /// request cursor that names that position (see `request_cursor_point`), else
726    /// [`Self::end_public_position`].
727    pub fn end_cursor_public_position(&self, options: &QueryOptions) -> LedgerPoint {
728        request_cursor_point(options, self.end_scan_position).unwrap_or(self.end_public_position)
729    }
730
731    /// Where this scan's terminal frame resumes in ledger coordinates, known without a read.
732    /// `window` is the window this scan was resolved from.
733    ///
734    /// The frame resumes at its end scan position, clamped so it never lies before the request's
735    /// effective start ascending (the window's start, the position its `after` cursor resumes at)
736    /// or past its effective end descending (the window's end, its `before` cursor). A window
737    /// that holds no checkpoint names the request's own start (ascending) or end (descending):
738    /// past this server's tip, an ascending terminal echoes where the request starts.
739    ///
740    /// A position is placed by the serving floor, by a window edge (the request's own fields), by
741    /// the public position of a request cursor that names it (see `request_cursor_point`): where
742    /// an `after` cursor resumes, including past this server's tip, or a `before` cursor's
743    /// position; or, for the end scan position itself, by its cursor's public position.
744    pub fn end_resume_position(
745        &self,
746        window: &ScanWindow<P>,
747        options: &QueryOptions,
748    ) -> LedgerPoint {
749        if let RangeExhaustion::ServingFloor { floor_checkpoint } = self.exhaustion {
750            // The floor is the first position of its checkpoint.
751            return LedgerPoint::checkpoint_start(floor_checkpoint);
752        }
753        if let Some((requested_start, requested_end)) = window.ledger.requested {
754            return match options.ordering {
755                Ordering::Ascending => requested_start,
756                Ordering::Descending => requested_end,
757            };
758        }
759        let position = match options.ordering {
760            Ordering::Ascending => {
761                let after_resumes_at = options
762                    .after
763                    .as_ref()
764                    // An Item at the last position keeps naming itself, a saturated resume point.
765                    .map(|after| after_resume::<P>(after).0);
766                let entry = after_resumes_at
767                    .map_or(window.range.start, |resume| resume.max(window.range.start));
768                self.end_scan_position.max(entry)
769            }
770            Ordering::Descending => {
771                let entry = options.before.as_ref().map_or(window.range.end, |before| {
772                    ScanCursor::<P>::coordinate(before).min(window.range.end)
773                });
774                self.end_scan_position.min(entry)
775            }
776        };
777        // The clamp's entry is a window edge or a position a request cursor names, so a position
778        // neither places is the end scan position.
779        window_edge_point(window, options.ordering, position)
780            .or_else(|| request_cursor_point(options, position))
781            .unwrap_or_else(|| self.end_cursor_public_position(options))
782    }
783
784    fn apply_cursor_bounds(mut self, options: &QueryOptions) -> Self {
785        if self.is_empty() {
786            return self;
787        }
788
789        let mut cursor_terminal = self.apply_after_cursor(options);
790
791        // Either zero, one, or two cursors emptied the bounds. If the bound is empty, before's
792        // position is provably the lower coordinate. Report this minimum of the crossed positions,
793        // otherwise we will skip an interval in the ascending case, or rollback scan progress in
794        // the descending case.
795        if let Some(recording) = self.apply_before_cursor(options) {
796            cursor_terminal = Some(recording);
797        }
798
799        if let Some((point, position, kind)) = cursor_terminal {
800            self.set_terminal_record(point, position, RangeExhaustion::CursorBound { kind });
801
802            self.bounds = ScanBounds::empty_at(self.end_scan_position);
803        }
804
805        self
806    }
807
808    fn set_terminal_record(
809        &mut self,
810        point: LedgerPoint,
811        position: P,
812        exhaustion: RangeExhaustion,
813    ) {
814        self.end_public_position = point;
815        self.end_scan_position = position;
816        self.exhaustion = exhaustion;
817    }
818
819    /// Tightens the low bound, and returns the terminal record if the cursor empties the interval.
820    fn apply_after_cursor(
821        &mut self,
822        options: &QueryOptions,
823    ) -> Option<(LedgerPoint, P, CursorKind)> {
824        let cursor = options.after.as_ref()?;
825        let position: P = cursor.coordinate();
826
827        // Symbolic resume in every lane: an Item admits strictly-after, a
828        // Boundary admits from itself.
829        let candidate = match cursor.kind {
830            CursorKind::Item => Bound::Excluded(position),
831            CursorKind::Boundary => Bound::Included(position),
832        };
833
834        if !lower_bound_gte(candidate, self.bounds.lo) {
835            return None;
836        }
837
838        // The after cursor is the terminal bound for a descending scan. Its closing cursor names
839        // the boundary just below the lowest position the scan admits, where `after` resumes, so
840        // that sent back as `before` it resumes with the next position down.
841        let (descending_terminal, descending_terminal_kind, descending_terminal_point) =
842            after_resume::<P>(cursor);
843        if !options.is_ascending() {
844            self.set_terminal_record(
845                descending_terminal_point,
846                descending_terminal,
847                RangeExhaustion::CursorBound {
848                    kind: descending_terminal_kind,
849                },
850            );
851        }
852
853        self.bounds.lo = candidate;
854
855        if !self.bounds.is_empty() {
856            return None;
857        }
858
859        // Report the cursor that emptied the bound. An ascending `after` cursor reports its own
860        // position and kind; `ResolvedScan::resolve` restates it as the boundary at the first
861        // position it admits. An Item at the last position admits none, so it keeps Item kind.
862        if options.is_ascending() {
863            Some((cursor.position.public_position(), position, cursor.kind))
864        } else {
865            Some((
866                descending_terminal_point,
867                descending_terminal,
868                descending_terminal_kind,
869            ))
870        }
871    }
872
873    /// Tightens the high bound, and returns the terminal record if the cursor empties the interval.
874    fn apply_before_cursor(
875        &mut self,
876        options: &QueryOptions,
877    ) -> Option<(LedgerPoint, P, CursorKind)> {
878        let cursor = options.before.as_ref()?;
879        let point = cursor.position.public_position();
880        let position: P = cursor.coordinate();
881
882        if !hi_admits_upper_bound(self.bounds.hi, position) {
883            return None;
884        }
885
886        if options.is_ascending() {
887            self.set_terminal_record(
888                point,
889                position,
890                RangeExhaustion::CursorBound {
891                    kind: CursorKind::Boundary,
892                },
893            );
894        }
895
896        self.bounds.hi = Bound::Excluded(position);
897
898        if !self.bounds.is_empty() {
899            return None;
900        }
901
902        Some((point, position, CursorKind::Boundary))
903    }
904
905    /// Raises the scan's low end to the serving floor, for a scan with no lower bound of its own
906    /// whose low end lies below the floor. An ascending scan starts at the floor and claims
907    /// coverage from `floor_checkpoint` on. A descending scan ends at the floor with
908    /// [`RangeExhaustion::ServingFloor`]: everything below it is pruned.
909    ///
910    /// A floor that leaves the scan nothing to cover (its `before` cursor sits at or below the
911    /// floor) is `OutOfRange`.
912    pub fn apply_serving_floor(
913        &mut self,
914        floor: P,
915        floor_checkpoint: u64,
916        options: &QueryOptions,
917    ) -> Result<(), RpcError> {
918        let floored_lo = Bound::Included(floor);
919        let floored = ScanBounds {
920            lo: floored_lo,
921            hi: self.bounds.hi,
922        };
923        if floored.is_empty() {
924            return Err(below_serving_floor(floor_checkpoint));
925        }
926        self.bounds.lo = floored_lo;
927        if options.is_ascending() {
928            self.entry_checkpoint = self.entry_checkpoint.max(floor_checkpoint);
929        } else {
930            self.set_terminal_record(
931                LedgerPoint::checkpoint_start(floor_checkpoint),
932                floor,
933                RangeExhaustion::ServingFloor { floor_checkpoint },
934            );
935        }
936        Ok(())
937    }
938}
939
940/// The requested checkpoint window's validity check, standalone so backends
941/// can sequence it independently of options parsing (kv validates bounds
942/// before the read mask and options; the fused resolution re-runs it
943/// harmlessly).
944pub fn validate_checkpoint_bounds(
945    start_checkpoint: Option<u64>,
946    end_checkpoint: Option<u64>,
947) -> Result<(), RpcError> {
948    let start = start_checkpoint.unwrap_or(0);
949    if let Some(end) = end_checkpoint
950        && end < start
951    {
952        return Err(FieldViolation::new("end_checkpoint")
953            .with_description("end_checkpoint must be greater than or equal to start_checkpoint")
954            .with_reason(ErrorReason::FieldInvalid)
955            .into());
956    }
957    Ok(())
958}
959
960impl ResolvedCheckpointRange {
961    /// Validate the requested checkpoint window, clamp it to the indexed tip, and attribute the
962    /// exhaustion reason the scan will report once it drains it.
963    ///
964    /// A descending window that reaches past the tip returns `OutOfRange` with the
965    /// `ABOVE_LATEST_AVAILABLE` reason: an `end_checkpoint` above the tip, or, with
966    /// `end_checkpoint` unset, a `start_checkpoint` at or above it. A descending scan starts at
967    /// its window's high end, so answering from this view would skip the checkpoints between the
968    /// tip and that end; like a descending scan's cursor past the tip, the request becomes
969    /// servable once this server catches up. An ascending window past the tip ends at the tip,
970    /// where the client resumes once this server has caught up, so only an ascending scan ends
971    /// with `LedgerTip`.
972    ///
973    /// The request's cursors do not narrow the window here: [`ResolvedScan::resolve`] bounds the
974    /// scan by the cursors' positions.
975    pub fn from_request(
976        start_checkpoint: Option<u64>,
977        end_checkpoint: Option<u64>,
978        checkpoint_hi_exclusive: u64,
979        options: &QueryOptions,
980    ) -> Result<Self, RpcError> {
981        validate_checkpoint_bounds(start_checkpoint, end_checkpoint)?;
982        let start = start_checkpoint.unwrap_or(0);
983        let descending_past_tip = match end_checkpoint {
984            _ if options.is_ascending() => None,
985            Some(end) if end > checkpoint_hi_exclusive => Some(("end_checkpoint", end)),
986            None if start >= checkpoint_hi_exclusive => Some(("start_checkpoint", start)),
987            Some(_) | None => None,
988        };
989        if let Some((field, requested)) = descending_past_tip {
990            return Err(above_latest_available(
991                field,
992                requested,
993                checkpoint_hi_exclusive,
994            ));
995        }
996        let requested_end = end_checkpoint.unwrap_or(checkpoint_hi_exclusive);
997        // Whether the request leaves its window's high end to this server's tip.
998        let window_reaches_tip =
999            end_checkpoint.is_none() || requested_end > checkpoint_hi_exclusive;
1000        let end = requested_end.min(checkpoint_hi_exclusive);
1001        let exhaustion = match options.ordering {
1002            Ordering::Ascending if window_reaches_tip => RangeExhaustion::LedgerTip,
1003            Ordering::Ascending | Ordering::Descending => RangeExhaustion::CheckpointBound,
1004        };
1005
1006        if options.is_ascending() && start >= checkpoint_hi_exclusive {
1007            return Ok(Self::empty_at(
1008                checkpoint_hi_exclusive,
1009                RangeExhaustion::LedgerTip,
1010                window_reaches_tip,
1011            ));
1012        }
1013        if start >= end {
1014            let checkpoint = match options.ordering {
1015                Ordering::Ascending => end,
1016                Ordering::Descending => start,
1017            };
1018            return Ok(Self::empty_at(
1019                checkpoint,
1020                exhaustion,
1021                window_reaches_tip && checkpoint == checkpoint_hi_exclusive,
1022            ));
1023        }
1024        Ok(Self {
1025            range: start..end,
1026            exhaustion,
1027            reaches_ledger_tip: window_reaches_tip && end == checkpoint_hi_exclusive,
1028        })
1029    }
1030}
1031
1032/// Where a page ends when its starting cursor sits at or past the window's edge in scan
1033/// direction, `window.end` ascending or `window.start` descending, and no far cursor stops the
1034/// scan at or before that edge, as `(public position, boundary position)`. An `after` cursor
1035/// starts an ascending scan at the first position it admits; a `before` cursor starts a
1036/// descending scan below its position. A far cursor stops the scan as `apply_cursor_bounds`
1037/// applies it: a `before` at or below the window's end, an `after` at or above the window's
1038/// start.
1039///
1040/// - At the edge, the page ends at the window's edge, as the page that handed the cursor back
1041///   did.
1042/// - Past the edge, the page ends at the boundary where the starting cursor resumes: the boundary
1043///   after an `after` Item cursor's item, or a `before` cursor's position. Ending at the window's
1044///   edge instead would hand back a cursor behind the client's, which replays the positions in
1045///   between when resumed without the window.
1046///
1047/// Either way the starting cursor names where the page ends, so the end carries the public
1048/// position where it resumes. `None` otherwise, including for an `after` Item cursor at the last
1049/// position, which names no boundary after it.
1050fn starting_cursor_end<P: ScanPosition>(
1051    options: &QueryOptions,
1052    window: &Range<P>,
1053) -> Option<(LedgerPoint, P)>
1054where
1055    CursorToken: ScanCursor<P>,
1056{
1057    let position = |cursor: &CursorToken| -> P { cursor.coordinate() };
1058    match options.ordering {
1059        Ordering::Ascending => {
1060            if options
1061                .before
1062                .as_ref()
1063                .is_some_and(|before| position(before) <= window.end)
1064            {
1065                return None;
1066            }
1067            let after = options.after.as_ref()?;
1068            let (first_admitted, kind, point) = after_resume::<P>(after);
1069            // An Item at the last position admits nothing, so it ends no scan here.
1070            (kind == CursorKind::Boundary && first_admitted >= window.end)
1071                .then_some((point, first_admitted))
1072        }
1073        Ordering::Descending => {
1074            if options
1075                .after
1076                .as_ref()
1077                .is_some_and(|after| position(after) >= window.start)
1078            {
1079                return None;
1080            }
1081            let before = options.before.as_ref()?;
1082            let upper = position(before);
1083            (upper <= window.start).then(|| (before.position.public_position(), upper))
1084        }
1085    }
1086}
1087
1088/// Rejects a descending scan whose cursor names a position at or past `tip`, the first position
1089/// this server has not indexed. Such a cursor comes from a newer view of the ledger than this
1090/// server's, from another replica or derived from a newer tip. Answering from this view would
1091/// start the scan below its `before` cursor, skipping items the client has not seen, or end a
1092/// scan bounded by its `after` cursor empty, though items lie above that cursor. `OutOfRange` with
1093/// the `ABOVE_LATEST_AVAILABLE` reason (see [`above_latest_available`]) marks the request as
1094/// reading past the data this server has, the mirror of a cursor below the pruned floor; unlike
1095/// that one, it becomes servable once this server catches up, so clients that recognize the
1096/// reason may retry it. An ascending scan's cursors may lie past the tip: its `before` cursor
1097/// leaves the tip as the scan's high end, and [`ascending_after_past_tip_end`] places the end of a
1098/// page whose `after` cursor resumes past it.
1099fn reject_descending_cursors_past_tip<P: Ord>(
1100    options: &QueryOptions,
1101    tip: P,
1102    checkpoint_hi_exclusive: u64,
1103) -> Result<(), RpcError>
1104where
1105    CursorToken: ScanCursor<P>,
1106{
1107    if options.is_ascending() {
1108        return Ok(());
1109    }
1110    for cursor in [options.before.as_ref(), options.after.as_ref()]
1111        .into_iter()
1112        .flatten()
1113    {
1114        let position = cursor.coordinate();
1115        // A boundary exactly at the tip is where a caught-up scan resumes; an item there, or any
1116        // position beyond it, has not been indexed here.
1117        let past_tip = match cursor.kind {
1118            CursorKind::Item => position >= tip,
1119            CursorKind::Boundary => position > tip,
1120        };
1121        if past_tip {
1122            let requested_checkpoint = cursor.position.public_position().checkpoint;
1123            return Err(above_latest_available(
1124                "cursor",
1125                requested_checkpoint,
1126                checkpoint_hi_exclusive,
1127            ));
1128        }
1129    }
1130    Ok(())
1131}
1132
1133/// Where an ascending page ends when its `after` cursor resumes past `tip`, the first position
1134/// this server has not indexed, as `(public position, position, reason)`. Such a cursor comes
1135/// from a newer view of the ledger than this server's, from another replica or derived from a
1136/// newer tip. This server holds nothing past its tip, so the page is empty and ends with
1137/// `LedgerTip` where the cursor resumes: at the boundary after an Item cursor's item, or at a
1138/// Boundary cursor's position. The client resumes from there once this server has caught up;
1139/// ending at this server's tip instead would hand back a cursor behind the client's, which
1140/// replays the positions in between.
1141///
1142/// A `before` cursor at or below that position leaves nothing between the cursors, so the page
1143/// ends at `before` with `CursorBound`, as it does on a server that has caught up. An Item cursor
1144/// at the last position admits nothing, so its page ends at `before` too, or with no `before`, at
1145/// the Item with `CursorBound`.
1146///
1147/// `None` for a descending scan, or for an `after` cursor that resumes at or below `tip`.
1148fn ascending_after_past_tip_end<P: ScanPosition>(
1149    options: &QueryOptions,
1150    tip: P,
1151) -> Option<(LedgerPoint, P, RangeExhaustion)>
1152where
1153    CursorToken: ScanCursor<P>,
1154{
1155    let after = options.after.as_ref().filter(|_| options.is_ascending())?;
1156    let (end, kind, point) = after_resume::<P>(after);
1157    if end <= tip {
1158        return None;
1159    }
1160    if let Some(before) = options.before.as_ref()
1161        && before.coordinate() <= end
1162    {
1163        return Some((
1164            before.position.public_position(),
1165            before.coordinate(),
1166            RangeExhaustion::CursorBound {
1167                kind: CursorKind::Boundary,
1168            },
1169        ));
1170    }
1171    let exhaustion = match kind {
1172        CursorKind::Boundary => RangeExhaustion::LedgerTip,
1173        CursorKind::Item => RangeExhaustion::CursorBound { kind },
1174    };
1175    Some((point, end, exhaustion))
1176}
1177
1178/// Where an `after` cursor resumes a scan, as `(position, kind)` of the cursor that names that
1179/// place, and that place's public position: a Boundary cursor's own position, or the boundary
1180/// after an Item cursor's item (its key with the finest index incremented). An Item at the last
1181/// position names no boundary after it, so it names itself, still an Item.
1182fn after_resume<P: ScanPosition>(after: &CursorToken) -> (P, CursorKind, LedgerPoint)
1183where
1184    CursorToken: ScanCursor<P>,
1185{
1186    let position: P = after.coordinate();
1187    match (after.kind, position.successor()) {
1188        (CursorKind::Item, Some(next)) => (
1189            next,
1190            CursorKind::Boundary,
1191            after.position.item_resume(ScanDirection::Ascending),
1192        ),
1193        _ => (position, after.kind, after.position.public_position()),
1194    }
1195}
1196
1197/// The public position of scan position `position` when a request cursor names it, the point a
1198/// terminal there resumes at: where the `after` cursor resumes (see [`after_resume`]), or the
1199/// `before` cursor's own position, `after` first where both name it. `None` when no request
1200/// cursor names it.
1201fn request_cursor_point<P: ScanPosition>(options: &QueryOptions, position: P) -> Option<LedgerPoint>
1202where
1203    CursorToken: ScanCursor<P>,
1204{
1205    let after = options.after.as_ref().and_then(|after| {
1206        let (resume, _, point) = after_resume::<P>(after);
1207        (resume == position).then_some(point)
1208    });
1209    after.or_else(|| {
1210        options
1211            .before
1212            .as_ref()
1213            .filter(|before| ScanCursor::<P>::coordinate(*before) == position)
1214            .map(|before| before.position.public_position())
1215    })
1216}
1217
1218/// The point of `position` when it is one of `window`'s edges. Where the edges are one scan
1219/// position (the window spans only empty checkpoints, or a start index past its checkpoint's
1220/// end), it names the edge in scan direction, the one its checkpoint claim reaches.
1221fn window_edge_point<P: Eq + Copy>(
1222    window: &ScanWindow<P>,
1223    ordering: Ordering,
1224    position: P,
1225) -> Option<LedgerPoint> {
1226    let ledger = &window.ledger;
1227    let (terminal_edge, entry_edge) = match ordering {
1228        Ordering::Ascending => (
1229            (window.range.end, ledger.end),
1230            (window.range.start, ledger.start),
1231        ),
1232        Ordering::Descending => (
1233            (window.range.start, ledger.start),
1234            (window.range.end, ledger.end),
1235        ),
1236    };
1237    if position == terminal_edge.0 {
1238        Some(terminal_edge.1)
1239    } else if position == entry_edge.0 {
1240        Some(entry_edge.1)
1241    } else {
1242        None
1243    }
1244}
1245
1246impl ScanCursor<u64> for CursorToken {
1247    fn coordinate(&self) -> u64 {
1248        match self.position {
1249            Position::Checkpoints { checkpoint } => checkpoint,
1250            Position::Transactions { tx_seq, .. } => tx_seq,
1251            Position::Events { .. } => unreachable!("validated at decode"),
1252        }
1253    }
1254}
1255
1256impl ScanCursor<IntraTxCoordinate> for CursorToken {
1257    fn coordinate(&self) -> IntraTxCoordinate {
1258        match self.position {
1259            Position::Events {
1260                tx_seq,
1261                event_index,
1262                ..
1263            } => IntraTxCoordinate {
1264                tx_seq,
1265                index: event_index,
1266            },
1267            _ => unreachable!("validated at decode"),
1268        }
1269    }
1270}
1271
1272impl From<IntraTxCoordinate> for (u64, u32) {
1273    fn from(position: IntraTxCoordinate) -> Self {
1274        (position.tx_seq, position.index)
1275    }
1276}
1277
1278impl From<(u64, u32)> for IntraTxCoordinate {
1279    fn from((tx_seq, index): (u64, u32)) -> Self {
1280        Self { tx_seq, index }
1281    }
1282}
1283
1284fn lower_bound_gte<P: Ord + Copy>(candidate: Bound<P>, current: Bound<P>) -> bool {
1285    let Some(candidate) = lower_bound_key(candidate) else {
1286        return false;
1287    };
1288    match lower_bound_key(current) {
1289        Some(current) => candidate >= current,
1290        None => true,
1291    }
1292}
1293
1294fn lower_bound_key<P: Ord + Copy>(bound: Bound<P>) -> Option<(P, u8)> {
1295    match bound {
1296        Bound::Included(position) => Some((position, 0)),
1297        Bound::Excluded(position) => Some((position, 1)),
1298        Bound::Unbounded => None,
1299    }
1300}
1301
1302fn hi_admits_upper_bound<P: Ord + Copy>(current: Bound<P>, candidate: P) -> bool {
1303    match current {
1304        Bound::Included(position) | Bound::Excluded(position) => candidate <= position,
1305        Bound::Unbounded => true,
1306    }
1307}
1308
1309fn parse_cursor(
1310    field: &'static str,
1311    cursor: Option<&Bytes>,
1312    position_matches: fn(&Position) -> bool,
1313) -> Result<Option<CursorToken>, RpcError> {
1314    cursor
1315        .map(|cursor| {
1316            CursorToken::decode(cursor).map_err(|_| invalid_cursor(field, "invalid cursor"))
1317        })
1318        .transpose()?
1319        .map(|token| {
1320            if position_matches(&token.position) {
1321                Ok(token)
1322            } else {
1323                Err(invalid_cursor(field, "invalid cursor"))
1324            }
1325        })
1326        .transpose()
1327}
1328
1329fn invalid_cursor(field: &'static str, description: impl Into<String>) -> RpcError {
1330    FieldViolation::new(field)
1331        .with_description(description)
1332        .with_reason(ErrorReason::FieldInvalid)
1333        .into()
1334}
1335
1336/// Asserts `error` is `OutOfRange` with `message` and an [`ErrorInfo`] in the
1337/// [`ErrorReason::DOMAIN`] domain whose reason is `reason` and whose metadata is exactly
1338/// `metadata`.
1339#[cfg(test)]
1340fn assert_out_of_range_error_info(
1341    error: RpcError,
1342    message: &str,
1343    reason: ErrorReason,
1344    metadata: &[(&str, &str)],
1345) {
1346    let status = error.into_status_proto();
1347    assert_eq!(status.code, tonic::Code::OutOfRange as i32, "{status:?}");
1348    assert_eq!(status.message, message);
1349    let error_infos: Vec<ErrorInfo> = status
1350        .details
1351        .iter()
1352        .filter_map(|detail| detail.to_msg::<ErrorInfo>().ok())
1353        .collect();
1354    let [error_info] = error_infos.as_slice() else {
1355        panic!("expected exactly one ErrorInfo in {status:?}");
1356    };
1357    assert_eq!(error_info.reason, reason.as_str_name(), "{status:?}");
1358    assert_eq!(error_info.domain, ErrorReason::DOMAIN, "{status:?}");
1359    let expected_metadata: std::collections::BTreeMap<String, String> = metadata
1360        .iter()
1361        .map(|(key, value)| ((*key).to_owned(), (*value).to_owned()))
1362        .collect();
1363    assert_eq!(error_info.metadata, expected_metadata, "{status:?}");
1364}
1365
1366/// Asserts `error` is [`below_serving_floor`] for `floor_checkpoint`: its message and its
1367/// `BELOW_EARLIEST_AVAILABLE` [`ErrorInfo`].
1368#[cfg(test)]
1369pub(crate) fn assert_below_serving_floor_error(error: RpcError, floor_checkpoint: u64) {
1370    assert_out_of_range_error_info(
1371        error,
1372        &format!(
1373            "requested data below earliest available; lowest available checkpoint is \
1374             {floor_checkpoint}"
1375        ),
1376        ErrorReason::BelowEarliestAvailable,
1377        &[("lowestAvailableCheckpoint", &floor_checkpoint.to_string())],
1378    );
1379}
1380
1381/// Asserts `error` is [`below_oldest_retained_version`] for `floor_checkpoint` and
1382/// `oldest_retained_version`.
1383#[cfg(test)]
1384pub(crate) fn assert_below_oldest_retained_version_error(
1385    error: RpcError,
1386    floor_checkpoint: u64,
1387    oldest_retained_version: u64,
1388) {
1389    assert_out_of_range_error_info(
1390        error,
1391        &format!(
1392            "requested object versions below earliest available; lowest available checkpoint is \
1393             {floor_checkpoint}, and lowest available version is {oldest_retained_version}"
1394        ),
1395        ErrorReason::BelowEarliestAvailable,
1396        &[
1397            ("lowestAvailableCheckpoint", &floor_checkpoint.to_string()),
1398            (
1399                "lowestAvailableVersion",
1400                &oldest_retained_version.to_string(),
1401            ),
1402        ],
1403    );
1404}
1405
1406/// Asserts `error` is [`above_latest_available`] for `bound` at `requested_checkpoint` on a
1407/// server that has indexed the checkpoints below `checkpoint_hi_exclusive`: its message and its
1408/// `ABOVE_LATEST_AVAILABLE` [`ErrorInfo`].
1409#[cfg(test)]
1410pub(crate) fn assert_above_latest_available_error(
1411    error: RpcError,
1412    bound: &str,
1413    requested_checkpoint: u64,
1414    checkpoint_hi_exclusive: u64,
1415) {
1416    let requested = match bound {
1417        "cursor" => format!("cursor is at checkpoint {requested_checkpoint}"),
1418        field => format!("{field} is {requested_checkpoint}"),
1419    };
1420    assert_out_of_range_error_info(
1421        error,
1422        &format!(
1423            "requested data above latest available; {requested}, and only checkpoints below \
1424             {checkpoint_hi_exclusive} are available"
1425        ),
1426        ErrorReason::AboveLatestAvailable,
1427        &[
1428            ("bound", bound),
1429            ("requestedCheckpoint", &requested_checkpoint.to_string()),
1430            (
1431                "firstUnavailableCheckpoint",
1432                &checkpoint_hi_exclusive.to_string(),
1433            ),
1434        ],
1435    );
1436}
1437
1438#[cfg(test)]
1439mod tests {
1440    use super::*;
1441
1442    /// The version floor names the checkpoint floor and the oldest retained version, each in its
1443    /// own metadata entry and in the message, without swapping them.
1444    #[test]
1445    fn below_oldest_retained_version_names_checkpoint_and_version() {
1446        assert_below_oldest_retained_version_error(below_oldest_retained_version(9, 3), 9, 3);
1447    }
1448
1449    /// The event-coordinate window spanning whole transactions `[start, end)`.
1450    fn tx_window(range: Range<u64>) -> Range<IntraTxCoordinate> {
1451        IntraTxCoordinate::start_of_tx(range.start)..IntraTxCoordinate::start_of_tx(range.end)
1452    }
1453
1454    fn query_options_from_proto(
1455        request: Option<&ProtoQueryOptions>,
1456    ) -> Result<QueryOptions, RpcError> {
1457        QueryOptions::transactions_from_proto(request, 100, 1_000)
1458    }
1459
1460    fn resolved_range(range: Range<u64>) -> ResolvedScan<u64> {
1461        ResolvedScan {
1462            bounds: ScanBounds::from_range(range),
1463            end_public_position: model_point(20, 0),
1464            end_scan_position: 20,
1465            exhaustion: RangeExhaustion::CheckpointBound,
1466            entry_checkpoint: 0,
1467            window_claim: Some(19),
1468        }
1469    }
1470
1471    /// The empty resolution `resolved_range` reaches when a cursor empties it.
1472    fn empty_resolved_range(
1473        end_public_position: LedgerPoint,
1474        end_scan_position: u64,
1475        exhaustion: RangeExhaustion,
1476    ) -> ResolvedScan<u64> {
1477        ResolvedScan {
1478            bounds: ScanBounds::empty_at(end_scan_position),
1479            end_public_position,
1480            end_scan_position,
1481            exhaustion,
1482            entry_checkpoint: 0,
1483            window_claim: Some(19),
1484        }
1485    }
1486
1487    fn tx_position(tx_seq: u64, point: LedgerPoint) -> Position {
1488        Position::Transactions {
1489            tx_seq,
1490            public_position: point,
1491        }
1492    }
1493
1494    fn ev_position(tx_seq: u64, event_index: u32, point: LedgerPoint) -> Position {
1495        Position::Events {
1496            tx_seq,
1497            event_index,
1498            public_position: point,
1499        }
1500    }
1501
1502    fn tx_item(tx_seq: u64) -> CursorToken {
1503        CursorToken::item(tx_position(tx_seq, model_point(tx_seq, 0)))
1504    }
1505
1506    fn tx_boundary(tx_seq: u64) -> CursorToken {
1507        CursorToken::boundary(tx_position(tx_seq, model_point(tx_seq, 0)))
1508    }
1509
1510    /// The boundary an ascending scan frontier at the start of `tx_seq` mints, placed after the
1511    /// transaction before it (see [`after_transaction_point`]).
1512    fn tx_frontier(tx_seq: u64) -> CursorToken {
1513        CursorToken::boundary(tx_position(tx_seq, after_transaction_point(tx_seq)))
1514    }
1515
1516    fn cp_item(checkpoint: u64) -> CursorToken {
1517        CursorToken::item(Position::Checkpoints { checkpoint })
1518    }
1519
1520    fn ev_item(tx_seq: u64, index: u32) -> CursorToken {
1521        CursorToken::item(ev_position(tx_seq, index, model_point(tx_seq, index)))
1522    }
1523
1524    fn ev_boundary(tx_seq: u64, index: u32) -> CursorToken {
1525        CursorToken::boundary(ev_position(tx_seq, index, model_point(tx_seq, index)))
1526    }
1527
1528    fn resolved_intra_tx() -> ResolvedScan<IntraTxCoordinate> {
1529        ResolvedScan {
1530            bounds: IntraTxScanBounds::from_range(
1531                IntraTxCoordinate::start_of_tx(0)..IntraTxCoordinate::start_of_tx(10),
1532            ),
1533            entry_checkpoint: 2,
1534            end_public_position: model_point(10, 0),
1535            end_scan_position: IntraTxCoordinate::start_of_tx(10),
1536            exhaustion: RangeExhaustion::CheckpointBound,
1537            window_claim: Some(8),
1538        }
1539    }
1540
1541    fn after_options(ordering: Ordering, cursor: CursorToken) -> QueryOptions {
1542        QueryOptions {
1543            limit_items: 100,
1544            ordering,
1545            after: Some(cursor),
1546            before: None,
1547        }
1548    }
1549
1550    fn before_options(ordering: Ordering, cursor: CursorToken) -> QueryOptions {
1551        QueryOptions {
1552            limit_items: 100,
1553            ordering,
1554            after: None,
1555            before: Some(cursor),
1556        }
1557    }
1558
1559    fn directional_options(ascending: bool) -> QueryOptions {
1560        let mut request = ProtoQueryOptions::default();
1561        if !ascending {
1562            request.ordering = Some(ProtoOrdering::Descending as i32);
1563        }
1564        query_options_from_proto(Some(&request)).unwrap()
1565    }
1566
1567    /// Asserts `result` is the `OutOfRange` error for data below a serving floor at
1568    /// `floor_checkpoint`.
1569    fn assert_below_serving_floor(result: Result<(), RpcError>, floor_checkpoint: u64) {
1570        let error = result.expect_err("expected OutOfRange below the serving floor");
1571        assert_below_serving_floor_error(error, floor_checkpoint);
1572    }
1573
1574    /// Serving-floor reconciliation for tx intervals: a floor inside the interval starts an
1575    /// ascending scan there and raises its entry claim, and ends a descending scan there with
1576    /// [`RangeExhaustion::ServingFloor`]. A floor at/past the high end leaves nothing to cover and
1577    /// is `OutOfRange` in both directions.
1578    #[test]
1579    fn tx_serving_floor_reconciles_or_rejects_consumed_scan() {
1580        let asc = directional_options(true);
1581        let desc = directional_options(false);
1582
1583        // Ascending, floor inside 0..100: scan starts at the floor; the
1584        // entry claim rises to the floor checkpoint; terminal untouched.
1585        let mut resolved = ResolvedScan {
1586            bounds: ScanBounds::from_range(0..100),
1587            end_public_position: model_point(100, 0),
1588            end_scan_position: 100,
1589            exhaustion: RangeExhaustion::CheckpointBound,
1590            entry_checkpoint: 0,
1591            window_claim: Some(19),
1592        };
1593        resolved.apply_serving_floor(50, 10, &asc).unwrap();
1594        assert_eq!(resolved.natural_end_claim(&asc), Some(19));
1595        assert_eq!(resolved.range(), 50..100);
1596        assert_eq!(resolved.entry_checkpoint, 10);
1597        assert_eq!(resolved.end_public_position, model_point(100, 0));
1598        assert_eq!(resolved.end_scan_position, 100);
1599        assert_eq!(resolved.exhaustion, RangeExhaustion::CheckpointBound);
1600
1601        // Descending, floor inside: entry (the high edge) untouched; the
1602        // scan ends at the floor, which it reaches as its serving floor.
1603        let mut resolved = ResolvedScan {
1604            bounds: ScanBounds::from_range(0..100),
1605            end_public_position: LedgerPoint::GENESIS,
1606            end_scan_position: 0,
1607            exhaustion: RangeExhaustion::CheckpointBound,
1608            entry_checkpoint: 20,
1609            window_claim: Some(0),
1610        };
1611        resolved.apply_serving_floor(50, 10, &desc).unwrap();
1612        assert_eq!(resolved.range(), 50..100);
1613        assert_eq!(resolved.entry_checkpoint, 20);
1614        assert_eq!(
1615            resolved.end_public_position,
1616            LedgerPoint::checkpoint_start(10)
1617        );
1618        assert_eq!(resolved.end_scan_position, 50);
1619        assert_eq!(
1620            resolved.exhaustion,
1621            RangeExhaustion::ServingFloor {
1622                floor_checkpoint: 10
1623            }
1624        );
1625
1626        // Floor at/past the high end (covers the == boundary), both
1627        // directions: nothing left to cover is `OutOfRange`.
1628        for floor_tx in [40, 50] {
1629            let mut resolved = ResolvedScan {
1630                bounds: ScanBounds::from_range(0..40),
1631                end_public_position: model_point(40, 0),
1632                end_scan_position: 40,
1633                exhaustion: RangeExhaustion::CheckpointBound,
1634                entry_checkpoint: 0,
1635                window_claim: Some(7),
1636            };
1637            assert_below_serving_floor(resolved.apply_serving_floor(floor_tx, 10, &asc), 10);
1638
1639            let mut resolved = ResolvedScan {
1640                bounds: ScanBounds::from_range(0..40),
1641                end_public_position: LedgerPoint::GENESIS,
1642                end_scan_position: 0,
1643                exhaustion: RangeExhaustion::CheckpointBound,
1644                entry_checkpoint: 8,
1645                window_claim: Some(0),
1646            };
1647            assert_below_serving_floor(resolved.apply_serving_floor(floor_tx, 10, &desc), 10);
1648        }
1649    }
1650
1651    /// [`ResolvedScan::<IntraTxCoordinate>::apply_serving_floor`] mirrors the tx behavior in
1652    /// event coordinates.
1653    #[test]
1654    fn event_serving_floor_reconciles_or_rejects_consumed_scan() {
1655        let asc = directional_options(true);
1656        let desc = directional_options(false);
1657
1658        // Ascending, floor inside: low bound moves, entry rises, terminal
1659        // untouched.
1660        let mut resolved = ResolvedScan {
1661            bounds: IntraTxScanBounds::from_range(
1662                IntraTxCoordinate::start_of_tx(0)..IntraTxCoordinate::start_of_tx(100),
1663            ),
1664            end_public_position: model_point(100, 0),
1665            end_scan_position: IntraTxCoordinate::start_of_tx(100),
1666            exhaustion: RangeExhaustion::CheckpointBound,
1667            entry_checkpoint: 0,
1668            window_claim: Some(19),
1669        };
1670        resolved
1671            .apply_serving_floor(IntraTxCoordinate::start_of_tx(50), 10, &asc)
1672            .unwrap();
1673        assert_eq!(resolved.natural_end_claim(&asc), Some(19));
1674        assert_eq!(
1675            resolved.bounds.lo,
1676            Bound::Included(IntraTxCoordinate::start_of_tx(50))
1677        );
1678        assert_eq!(resolved.entry_checkpoint, 10);
1679        assert_eq!(resolved.end_public_position, model_point(100, 0));
1680        assert_eq!(
1681            resolved.end_scan_position,
1682            IntraTxCoordinate::start_of_tx(100)
1683        );
1684
1685        // Descending, floor inside: the scan ends at the floor, which it reaches as its serving
1686        // floor.
1687        let mut resolved = ResolvedScan {
1688            bounds: IntraTxScanBounds::from_range(
1689                IntraTxCoordinate::start_of_tx(0)..IntraTxCoordinate::start_of_tx(100),
1690            ),
1691            end_public_position: LedgerPoint::GENESIS,
1692            end_scan_position: IntraTxCoordinate::start_of_tx(0),
1693            exhaustion: RangeExhaustion::CheckpointBound,
1694            entry_checkpoint: 20,
1695            window_claim: Some(0),
1696        };
1697        resolved
1698            .apply_serving_floor(IntraTxCoordinate::start_of_tx(50), 10, &desc)
1699            .unwrap();
1700        assert_eq!(
1701            resolved.bounds.lo,
1702            Bound::Included(IntraTxCoordinate::start_of_tx(50))
1703        );
1704        assert_eq!(resolved.entry_checkpoint, 20);
1705        assert_eq!(
1706            resolved.end_public_position,
1707            LedgerPoint::checkpoint_start(10)
1708        );
1709        assert_eq!(
1710            resolved.end_scan_position,
1711            IntraTxCoordinate::start_of_tx(50)
1712        );
1713        assert_eq!(
1714            resolved.exhaustion,
1715            RangeExhaustion::ServingFloor {
1716                floor_checkpoint: 10
1717            }
1718        );
1719
1720        // Floor that empties the bounds (covers the == boundary), both
1721        // directions: nothing left to cover is `OutOfRange`.
1722        for floor_tx in [40, 50] {
1723            let mut resolved = ResolvedScan {
1724                bounds: IntraTxScanBounds::from_range(
1725                    IntraTxCoordinate::start_of_tx(0)..IntraTxCoordinate::start_of_tx(40),
1726                ),
1727                end_public_position: model_point(40, 0),
1728                end_scan_position: IntraTxCoordinate::start_of_tx(40),
1729                exhaustion: RangeExhaustion::CheckpointBound,
1730                entry_checkpoint: 0,
1731                window_claim: Some(7),
1732            };
1733            assert_below_serving_floor(
1734                resolved.apply_serving_floor(IntraTxCoordinate::start_of_tx(floor_tx), 10, &asc),
1735                10,
1736            );
1737
1738            let mut resolved = ResolvedScan {
1739                bounds: IntraTxScanBounds::from_range(
1740                    IntraTxCoordinate::start_of_tx(0)..IntraTxCoordinate::start_of_tx(40),
1741                ),
1742                end_public_position: LedgerPoint::GENESIS,
1743                end_scan_position: IntraTxCoordinate::start_of_tx(0),
1744                exhaustion: RangeExhaustion::CheckpointBound,
1745                entry_checkpoint: 8,
1746                window_claim: Some(0),
1747            };
1748            assert_below_serving_floor(
1749                resolved.apply_serving_floor(IntraTxCoordinate::start_of_tx(floor_tx), 10, &desc),
1750                10,
1751            );
1752        }
1753    }
1754
1755    /// A descending walk with no lower bound of its own ends at the serving floor with
1756    /// [`RangeExhaustion::ServingFloor`], claiming the floor checkpoint. Resuming it with a
1757    /// `before` cursor at the floor or below it, in either ordering, leaves nothing above the
1758    /// floor to cover and is `OutOfRange`.
1759    #[test]
1760    fn descending_walk_ends_at_serving_floor_and_resuming_below_it_is_out_of_range() {
1761        let floor_checkpoint = 10;
1762        let floor = first_tx(floor_checkpoint);
1763
1764        let walk = directional_options(false);
1765        let mut reached_floor = resolve_tx_request((None, None), &walk).unwrap();
1766        reached_floor
1767            .apply_serving_floor(floor, floor_checkpoint, &walk)
1768            .unwrap();
1769        assert_eq!(reached_floor.range(), floor..first_tx(TIP));
1770        assert_eq!(
1771            (
1772                reached_floor.exhaustion,
1773                reached_floor.end_public_position,
1774                reached_floor.end_scan_position,
1775            ),
1776            (
1777                RangeExhaustion::ServingFloor { floor_checkpoint },
1778                LedgerPoint::checkpoint_start(floor_checkpoint),
1779                floor,
1780            )
1781        );
1782
1783        let at_floor = CursorToken::boundary(tx_position(
1784            reached_floor.end_scan_position,
1785            reached_floor.end_cursor_public_position(&walk),
1786        ));
1787        let below_floor = tx_boundary(33);
1788        for ordering in [Ordering::Descending, Ordering::Ascending] {
1789            for before in [at_floor.clone(), below_floor.clone()] {
1790                let resume = before_options(ordering, before);
1791                let mut resumed = resolve_tx_request((None, None), &resume).unwrap();
1792                assert_below_serving_floor(
1793                    resumed.apply_serving_floor(floor, floor_checkpoint, &resume),
1794                    floor_checkpoint,
1795                );
1796            }
1797        }
1798    }
1799
1800    #[test]
1801    fn tx_range_covers_partial_endpoint_transactions() {
1802        let bounds = IntraTxScanBounds {
1803            lo: Bound::Included(IntraTxCoordinate {
1804                tx_seq: 10,
1805                index: 2,
1806            }),
1807            hi: Bound::Excluded(IntraTxCoordinate::start_of_tx(13)),
1808        };
1809
1810        assert_eq!(bounds.tx_range(), Some(10..13));
1811    }
1812
1813    #[test]
1814    fn tx_range_keeps_tx_of_nonzero_exclusive_hi() {
1815        let bounds = IntraTxScanBounds {
1816            lo: Bound::Unbounded,
1817            hi: Bound::Excluded(IntraTxCoordinate {
1818                tx_seq: 13,
1819                index: 1,
1820            }),
1821        };
1822
1823        assert_eq!(bounds.tx_range(), Some(0..14));
1824    }
1825
1826    #[test]
1827    fn tx_range_empty_bounds_yield_none() {
1828        let bounds = IntraTxScanBounds::from_range(
1829            IntraTxCoordinate::start_of_tx(10)..IntraTxCoordinate::start_of_tx(10),
1830        );
1831        assert_eq!(bounds.tx_range(), None);
1832    }
1833
1834    /// Every after-Item cursor now resumes as an Excluded lo; the successor
1835    /// arithmetic and its `u64::MAX` saturation live here at the store edge.
1836    #[test]
1837    fn to_range_collapses_excluded_lo_at_successor() {
1838        let bounds = ScanBounds {
1839            lo: Bound::Excluded(14u64),
1840            hi: Bound::Excluded(20u64),
1841        };
1842        assert_eq!(bounds.to_range(), 15..20);
1843
1844        // The saturated successor at the unoccupiable sentinel admits
1845        // nothing, through the ordinary emptiness of MAX..MAX.
1846        let bounds = ScanBounds {
1847            lo: Bound::Excluded(u64::MAX),
1848            hi: Bound::Unbounded,
1849        };
1850        assert!(bounds.to_range().is_empty());
1851    }
1852
1853    #[test]
1854    fn parses_cursors_and_ordering() {
1855        let after = tx_item(20).encode();
1856        let before = tx_item(30).encode();
1857        let mut request = ProtoQueryOptions::default();
1858        request.limit = Some(500);
1859        request.after = Some(after);
1860        request.before = Some(before);
1861        request.ordering = Some(ProtoOrdering::Descending as i32);
1862
1863        let options = query_options_from_proto(Some(&request)).unwrap();
1864
1865        assert_eq!(options.limit_items, 500);
1866        assert_eq!(options.ordering, Ordering::Descending);
1867        assert_eq!(options.scan_direction(), ScanDirection::Descending);
1868        assert_eq!(
1869            resolved_range(0..100).apply_cursor_bounds(&options).range(),
1870            21..30
1871        );
1872    }
1873
1874    #[test]
1875    fn has_after_cursor_reflects_only_the_after_field() {
1876        // No cursors → open-ended low end.
1877        let options = query_options_from_proto(Some(&ProtoQueryOptions::default())).unwrap();
1878        assert!(!options.has_after_cursor());
1879
1880        // `before` bounds the high end, so it must not count as an explicit low end.
1881        let mut request = ProtoQueryOptions::default();
1882        request.before = Some(tx_item(30).encode());
1883        let options = query_options_from_proto(Some(&request)).unwrap();
1884        assert!(!options.has_after_cursor());
1885
1886        // `after` raises the low end → explicit.
1887        let mut request = ProtoQueryOptions::default();
1888        request.after = Some(tx_item(20).encode());
1889        let options = query_options_from_proto(Some(&request)).unwrap();
1890        assert!(options.has_after_cursor());
1891    }
1892
1893    #[test]
1894    fn clamps_limit_items_and_defaults_to_ascending() {
1895        let mut request = ProtoQueryOptions::default();
1896        request.limit = Some(5_000);
1897
1898        let options = query_options_from_proto(Some(&request)).unwrap();
1899
1900        assert_eq!(options.limit_items, 1_000);
1901        assert_eq!(options.ordering, Ordering::Ascending);
1902        assert_eq!(options.scan_direction(), ScanDirection::Ascending);
1903    }
1904
1905    #[test]
1906    fn rejects_malformed_cursors_and_unknown_ordering() {
1907        let mut request = ProtoQueryOptions::default();
1908        request.after = Some(Bytes::from_static(b"short"));
1909        assert!(query_options_from_proto(Some(&request)).is_err());
1910
1911        let mut request = ProtoQueryOptions::default();
1912        request.before = Some(Bytes::from_static(b"short"));
1913        assert!(query_options_from_proto(Some(&request)).is_err());
1914
1915        let mut request = ProtoQueryOptions::default();
1916        request.ordering = Some(99);
1917        assert!(query_options_from_proto(Some(&request)).is_err());
1918    }
1919
1920    #[test]
1921    fn rejects_cursor_for_different_position_variant() {
1922        let token = cp_item(9).encode();
1923        let mut request = ProtoQueryOptions::default();
1924        request.after = Some(token);
1925        assert!(query_options_from_proto(Some(&request)).is_err());
1926    }
1927
1928    #[test]
1929    fn accepts_cursor_regardless_of_filter_scope() {
1930        // Cursors are portable across filters: a Transactions cursor must be
1931        // accepted by a Transactions query even though `query_options_from_proto`
1932        // applies no filter. Position is an absolute, filter-independent
1933        // coordinate, so resuming under a different filter is correct.
1934        let after = tx_item(9).encode();
1935        let before = tx_item(30).encode();
1936        let mut request = ProtoQueryOptions::default();
1937        request.after = Some(after);
1938        request.before = Some(before);
1939        assert!(query_options_from_proto(Some(&request)).is_ok());
1940    }
1941
1942    #[test]
1943    fn accepts_cursors_for_different_checkpoint_range_and_ordering() {
1944        let token = tx_item(9).encode();
1945        let mut request = ProtoQueryOptions::default();
1946        request.after = Some(token);
1947        request.ordering = Some(ProtoOrdering::Descending as i32);
1948
1949        let options = query_options_from_proto(Some(&request)).unwrap();
1950        let range =
1951            ResolvedCheckpointRange::from_request(Some(1_000), Some(1_100), 2_000, &options)
1952                .unwrap();
1953
1954        assert_eq!(range.range, 1_000..1_100);
1955    }
1956
1957    #[test]
1958    fn applies_canonical_cursor_bounds() {
1959        let options = QueryOptions {
1960            limit_items: 2,
1961            ordering: Ordering::Ascending,
1962            after: Some(tx_item(11)),
1963            before: None,
1964        };
1965        assert_eq!(
1966            resolved_range(10..20).apply_cursor_bounds(&options).range(),
1967            12..20
1968        );
1969
1970        let options = QueryOptions {
1971            after: Some(tx_item(u64::MAX)),
1972            ..options
1973        };
1974        assert_eq!(
1975            resolved_range(10..20).apply_cursor_bounds(&options),
1976            empty_resolved_range(
1977                model_point(u64::MAX, 0),
1978                u64::MAX,
1979                RangeExhaustion::CursorBound {
1980                    kind: CursorKind::Item,
1981                },
1982            )
1983        );
1984
1985        let options = QueryOptions {
1986            ordering: Ordering::Descending,
1987            after: Some(tx_item(11)),
1988            before: Some(tx_item(19)),
1989            ..options
1990        };
1991        let bounded = resolved_range(10..20).apply_cursor_bounds(&options);
1992        assert_eq!(bounded.range(), 12..19);
1993        assert_eq!(
1994            bounded.exhaustion,
1995            RangeExhaustion::CursorBound {
1996                kind: CursorKind::Boundary,
1997            }
1998        );
1999        // The terminal is the boundary just above the `after` item, which the scan excluded.
2000        assert_eq!(bounded.end_scan_position, 12);
2001    }
2002
2003    // (descending, after = Item 11, before = Item 12): the cursors leave the
2004    // empty gap (11, 12), so the fetch serves nothing and the CursorBound
2005    // frame comes from the descending stop side: the boundary just above the
2006    // after item, at 12.
2007    #[test]
2008    fn descending_before_adjacent_to_after_empties_above_the_after_item() {
2009        let options = QueryOptions {
2010            limit_items: 2,
2011            ordering: Ordering::Descending,
2012            after: Some(tx_item(11)),
2013            before: Some(tx_item(12)),
2014        };
2015        let crossed = resolved_range(10..20).apply_cursor_bounds(&options);
2016        assert_eq!(
2017            crossed,
2018            ResolvedScan {
2019                bounds: ScanBounds {
2020                    lo: Bound::Excluded(11),
2021                    hi: Bound::Excluded(12),
2022                },
2023                entry_checkpoint: 0,
2024                end_public_position: after_transaction_point(12),
2025                end_scan_position: 12,
2026                exhaustion: RangeExhaustion::CursorBound {
2027                    kind: CursorKind::Boundary,
2028                },
2029                window_claim: Some(19),
2030            }
2031        );
2032        assert!(crossed.range().is_empty());
2033    }
2034
2035    #[test]
2036    fn applies_boundary_cursor_bounds_without_item_offset() {
2037        let options = QueryOptions {
2038            limit_items: 2,
2039            ordering: Ordering::Ascending,
2040            after: Some(tx_boundary(20)),
2041            before: None,
2042        };
2043        assert_eq!(
2044            resolved_range(10..30).apply_cursor_bounds(&options).range(),
2045            20..30
2046        );
2047
2048        let options = QueryOptions {
2049            ordering: Ordering::Descending,
2050            after: None,
2051            before: Some(tx_boundary(20)),
2052            ..options
2053        };
2054        assert_eq!(
2055            resolved_range(10..30).apply_cursor_bounds(&options).range(),
2056            10..20
2057        );
2058    }
2059
2060    #[test]
2061    fn resolves_checkpoint_range_with_terminal_reason() {
2062        let options = query_options_from_proto(None).unwrap();
2063        assert_eq!(
2064            ResolvedCheckpointRange::from_request(None, None, 20, &options)
2065                .unwrap()
2066                .exhaustion,
2067            RangeExhaustion::LedgerTip
2068        );
2069        assert!(ResolvedCheckpointRange::from_request(Some(10), Some(9), 20, &options).is_err());
2070
2071        let resolved = ResolvedCheckpointRange::from_request(Some(10), None, 20, &options).unwrap();
2072        assert_eq!(resolved.range, 10..20);
2073        assert_eq!(resolved.exhaustion, RangeExhaustion::LedgerTip);
2074
2075        assert_eq!(
2076            ResolvedCheckpointRange::from_request(Some(30), None, 20, &options).unwrap(),
2077            ResolvedCheckpointRange::empty_at(20, RangeExhaustion::LedgerTip, true)
2078        );
2079    }
2080
2081    /// The cp-width clamp was removed when scan limiting moved to the runtime
2082    /// bucket-budget path. Whatever range the request asks for is honored at
2083    /// resolve time; the bitmap layer terminates scans on budget exhaustion.
2084    #[test]
2085    fn resolves_checkpoint_range_no_longer_clamped_by_width() {
2086        let options = query_options_from_proto(None).unwrap();
2087        let resolved =
2088            ResolvedCheckpointRange::from_request(Some(10), Some(10_000_000), 10_000_000, &options)
2089                .unwrap();
2090        assert_eq!(resolved.range, 10..10_000_000);
2091        assert_eq!(resolved.exhaustion, RangeExhaustion::CheckpointBound);
2092    }
2093
2094    /// (start_checkpoint = 30, tip = 20, ascending): resolves empty at the tip — entry checkpoint
2095    /// 20, terminal at the start of checkpoint 20, LedgerTip.
2096    #[test]
2097    fn ascending_window_past_tip_empties_with_ledger_tip() {
2098        let options = QueryOptions::events_from_proto(None, 100, 100).unwrap();
2099        let cp_range = ResolvedCheckpointRange::from_request(Some(30), None, 20, &options).unwrap();
2100        assert!(cp_range.is_empty());
2101        let ledger = LedgerWindow::checkpoints(&cp_range.range, Some(30), None);
2102        assert_eq!(
2103            ResolvedScan::<IntraTxCoordinate>::resolve(
2104                cp_range,
2105                ScanWindow::whole_checkpoints(tx_window(100..100), ledger),
2106                &options
2107            )
2108            .unwrap(),
2109            ResolvedScan {
2110                bounds: IntraTxScanBounds::empty_at(IntraTxCoordinate::start_of_tx(100)),
2111                entry_checkpoint: 20,
2112                end_public_position: LedgerPoint::checkpoint_start(20),
2113                end_scan_position: IntraTxCoordinate::start_of_tx(100),
2114                exhaustion: RangeExhaustion::LedgerTip,
2115                window_claim: None,
2116            }
2117        );
2118    }
2119
2120    /// A descending window that reaches past the tip (20) is out of range: an `end_checkpoint`
2121    /// above the tip, or a `start_checkpoint` at or above it with `end_checkpoint` unset. A
2122    /// window that ends at the tip resolves, and a zero-width window there is empty with
2123    /// CheckpointBound.
2124    #[test]
2125    fn descending_window_past_tip_is_out_of_range() {
2126        let mut request = ProtoQueryOptions::default();
2127        request.ordering = Some(ProtoOrdering::Descending as i32);
2128        let options = QueryOptions::events_from_proto(Some(&request), 100, 100).unwrap();
2129        for (start, end, bound, requested) in [
2130            (Some(30), None, "start_checkpoint", 30),
2131            (Some(20), None, "start_checkpoint", 20),
2132            (Some(10), Some(21), "end_checkpoint", 21),
2133            (None, Some(u64::MAX), "end_checkpoint", u64::MAX),
2134            (Some(25), Some(30), "end_checkpoint", 30),
2135        ] {
2136            let error = ResolvedCheckpointRange::from_request(start, end, 20, &options)
2137                .expect_err("descending window past the tip");
2138            assert_above_latest_available_error(error, bound, requested, 20);
2139        }
2140
2141        let resolved = ResolvedCheckpointRange::from_request(Some(10), Some(20), 20, &options);
2142        assert_eq!(resolved.unwrap().range, 10..20);
2143        assert_eq!(
2144            ResolvedCheckpointRange::from_request(Some(20), Some(20), 20, &options).unwrap(),
2145            ResolvedCheckpointRange::empty_at(20, RangeExhaustion::CheckpointBound, false)
2146        );
2147    }
2148
2149    /// A descending cursor past the tip reports the checkpoint of its public position as
2150    /// `requestedCheckpoint`; a checkpoint cursor reports its checkpoint.
2151    #[test]
2152    fn descending_cursor_past_tip_reports_its_public_checkpoint() {
2153        let descending = |before| options_with(Ordering::Descending, None, Some(before));
2154        // Position `(TIP + 1, 1)`.
2155        let error = resolve_tx_request(
2156            (None, None),
2157            &descending(tx_boundary(first_tx(TIP + 1) + 1)),
2158        )
2159        .expect_err("descending transaction cursor past the tip");
2160        assert_above_latest_available_error(error, "cursor", TIP + 1, TIP);
2161
2162        let error = resolve_checkpoint_request((None, None), &descending(cp_item(TIP)))
2163            .expect_err("descending checkpoint cursor past the tip");
2164        assert_above_latest_available_error(error, "cursor", TIP, TIP);
2165    }
2166
2167    /// When the resolved checkpoint range is below checkpoint_hi_exclusive and empties, the
2168    /// exhaustion reason is CheckpointBound, not LedgerTip.
2169    #[test]
2170    fn resolve_zero_width_window_empties_with_checkpoint_bound() {
2171        for ascending in [true, false] {
2172            let mut request = ProtoQueryOptions::default();
2173            if !ascending {
2174                request.ordering = Some(ProtoOrdering::Descending as i32);
2175            }
2176            let options = QueryOptions::events_from_proto(Some(&request), 100, 100).unwrap();
2177            let cp_range =
2178                ResolvedCheckpointRange::from_request(Some(10), Some(10), 20, &options).unwrap();
2179            assert!(cp_range.is_empty());
2180            let ledger = LedgerWindow::checkpoints(&cp_range.range, Some(10), Some(10));
2181            assert_eq!(
2182                ResolvedScan::<IntraTxCoordinate>::resolve(
2183                    cp_range,
2184                    ScanWindow::whole_checkpoints(tx_window(100..100), ledger),
2185                    &options
2186                )
2187                .unwrap(),
2188                ResolvedScan {
2189                    bounds: IntraTxScanBounds::empty_at(IntraTxCoordinate::start_of_tx(100)),
2190                    entry_checkpoint: 10,
2191                    end_public_position: LedgerPoint::checkpoint_start(10),
2192                    end_scan_position: IntraTxCoordinate::start_of_tx(100),
2193                    exhaustion: RangeExhaustion::CheckpointBound,
2194                    window_claim: None,
2195                }
2196            );
2197        }
2198    }
2199
2200    /// If the bounds are already empty, cursors do not apply.
2201    #[test]
2202    fn cursor_bounds_pass_empty_resolution_through_unchanged() {
2203        let cursor = ev_item(50, 2);
2204        for ascending in [true, false] {
2205            let mut request = ProtoQueryOptions::default();
2206            if !ascending {
2207                request.ordering = Some(ProtoOrdering::Descending as i32);
2208            }
2209            request.after = Some(cursor.encode());
2210            let options = QueryOptions::events_from_proto(Some(&request), 100, 100).unwrap();
2211            let cp_range =
2212                ResolvedCheckpointRange::from_request(Some(10), Some(10), 20, &options).unwrap();
2213            let resolved = ResolvedScan::<IntraTxCoordinate>::resolve(
2214                cp_range,
2215                ScanWindow::whole_checkpoints(
2216                    tx_window(100..100),
2217                    LedgerWindow::checkpoints(&(0..0), None, None),
2218                ),
2219                &options,
2220            )
2221            .unwrap();
2222            assert_eq!(resolved.clone().apply_cursor_bounds(&options), resolved);
2223        }
2224    }
2225
2226    /// resolve sets entry_checkpoint to the scan's first checkpoint and the terminal
2227    /// (end_public_position, end_scan_position) to its last, per ordering.
2228    #[test]
2229    fn resolve_orients_entry_and_terminal_by_ordering() {
2230        let options = directional_options(true);
2231        let cp_range =
2232            ResolvedCheckpointRange::from_request(Some(3), Some(10), 20, &options).unwrap();
2233        assert_eq!(cp_range.range, 3..10);
2234        let window = ScanWindow::whole_checkpoints(
2235            tx_window(100..200),
2236            LedgerWindow::checkpoints(&cp_range.range, Some(3), Some(10)),
2237        );
2238        let resolved =
2239            ResolvedScan::<IntraTxCoordinate>::resolve(cp_range.clone(), window.clone(), &options)
2240                .unwrap();
2241        assert_eq!(
2242            resolved.bounds,
2243            IntraTxScanBounds::from_range(
2244                IntraTxCoordinate::start_of_tx(100)..IntraTxCoordinate::start_of_tx(200)
2245            )
2246        );
2247        assert_eq!(resolved.entry_checkpoint, 3);
2248        assert_eq!(
2249            resolved.end_public_position,
2250            LedgerPoint::checkpoint_start(10)
2251        );
2252        assert_eq!(
2253            resolved.end_scan_position,
2254            IntraTxCoordinate::start_of_tx(200)
2255        );
2256
2257        let options = directional_options(false);
2258        let resolved =
2259            ResolvedScan::<IntraTxCoordinate>::resolve(cp_range, window, &options).unwrap();
2260        assert_eq!(resolved.entry_checkpoint, 9);
2261        assert_eq!(
2262            resolved.end_public_position,
2263            LedgerPoint::checkpoint_start(3)
2264        );
2265        assert_eq!(
2266            resolved.end_scan_position,
2267            IntraTxCoordinate::start_of_tx(100)
2268        );
2269    }
2270
2271    /// (ascending, `after` past the window's end): the page ends with the window's reason at the
2272    /// boundary where the cursor resumes, at the public position there, and claims the window's
2273    /// last checkpoint. An Item cursor's boundary sits after its event, so resuming from it does
2274    /// not re-serve the event.
2275    #[test]
2276    fn event_after_cursor_past_window_ends_where_it_resumes() {
2277        // Checkpoints 1..4, transactions 5..20.
2278        let window = (Some(1), Some(4));
2279        for (cursor, end_scan_position) in [
2280            (
2281                ev_item(25, 0),
2282                IntraTxCoordinate {
2283                    tx_seq: 25,
2284                    index: 1,
2285                },
2286            ),
2287            (ev_boundary(25, 0), IntraTxCoordinate::start_of_tx(25)),
2288        ] {
2289            let options = after_options(Ordering::Ascending, cursor.clone());
2290            let resolved = resolve_event_request(window, &options).unwrap();
2291            assert!(resolved.is_empty(), "{cursor:?}");
2292            assert_eq!(
2293                resolved.exhaustion,
2294                RangeExhaustion::CheckpointBound,
2295                "{cursor:?}"
2296            );
2297            assert_eq!(
2298                (resolved.end_public_position, resolved.end_scan_position),
2299                (
2300                    model_point(end_scan_position.tx_seq, end_scan_position.index),
2301                    end_scan_position
2302                ),
2303                "{cursor:?}"
2304            );
2305            assert_eq!(resolved.natural_end_claim(&options), Some(3), "{cursor:?}");
2306        }
2307    }
2308
2309    /// `before` cursor that empties the interval sets end_scan_position, and exhaustion to
2310    /// CursorBound.
2311    #[test]
2312    fn event_before_cursor_empties_descending_interval() {
2313        // Start descending over tx range [100, 200) with entry at checkpoint 9 terminating at checkpoint 3
2314        let resolved = ResolvedScan {
2315            // always in ascending order
2316            bounds: IntraTxScanBounds::from_range(
2317                IntraTxCoordinate::start_of_tx(100)..IntraTxCoordinate::start_of_tx(200),
2318            ),
2319            // checkpoints reflect ordering
2320            entry_checkpoint: 9,
2321            end_public_position: model_point(100, 0),
2322            end_scan_position: IntraTxCoordinate::start_of_tx(100),
2323            exhaustion: RangeExhaustion::CheckpointBound,
2324            window_claim: Some(3),
2325        };
2326
2327        // This cursor empties the interval; the entry checkpoint stays at the window's.
2328        for token in [ev_item(90, 0), ev_boundary(90, 0)] {
2329            let mut request = ProtoQueryOptions::default();
2330            request.ordering = Some(ProtoOrdering::Descending as i32);
2331            request.before = Some(token.encode());
2332            let options = QueryOptions::events_from_proto(Some(&request), 100, 100).unwrap();
2333
2334            let new_coordinate = IntraTxCoordinate::start_of_tx(90);
2335            assert_eq!(
2336                resolved.clone().apply_cursor_bounds(&options),
2337                ResolvedScan {
2338                    bounds: IntraTxScanBounds::empty_at(new_coordinate),
2339                    entry_checkpoint: 9,
2340                    end_public_position: model_point(90, 0),
2341                    // takes on the cursor position that emptied the range
2342                    end_scan_position: new_coordinate,
2343                    exhaustion: RangeExhaustion::CursorBound {
2344                        kind: CursorKind::Boundary,
2345                    },
2346                    window_claim: Some(3),
2347                }
2348            );
2349        }
2350    }
2351
2352    /// (ascending, after inside the window): Item admits strictly after its
2353    /// coordinate, Boundary from it; entry checkpoint and terminal untouched.
2354    #[test]
2355    fn after_cursor_tightens_ascending_lower_bound() {
2356        let options = after_options(Ordering::Ascending, ev_item(5, 1));
2357        assert_eq!(
2358            resolved_intra_tx().apply_cursor_bounds(&options),
2359            ResolvedScan {
2360                bounds: IntraTxScanBounds {
2361                    lo: Bound::Excluded(IntraTxCoordinate {
2362                        tx_seq: 5,
2363                        index: 1,
2364                    }),
2365                    hi: Bound::Excluded(IntraTxCoordinate::start_of_tx(10)),
2366                },
2367                ..resolved_intra_tx()
2368            }
2369        );
2370
2371        let options = after_options(Ordering::Ascending, ev_boundary(5, 1));
2372        assert_eq!(
2373            resolved_intra_tx().apply_cursor_bounds(&options),
2374            ResolvedScan {
2375                bounds: IntraTxScanBounds {
2376                    lo: Bound::Included(IntraTxCoordinate {
2377                        tx_seq: 5,
2378                        index: 1,
2379                    }),
2380                    hi: Bound::Excluded(IntraTxCoordinate::start_of_tx(10)),
2381                },
2382                ..resolved_intra_tx()
2383            }
2384        );
2385    }
2386
2387    #[test]
2388    fn after_cursor_below_lower_bound_changes_nothing() {
2389        let seed = ResolvedScan {
2390            bounds: IntraTxScanBounds {
2391                lo: Bound::Included(IntraTxCoordinate::start_of_tx(5)),
2392                hi: Bound::Excluded(IntraTxCoordinate::start_of_tx(10)),
2393            },
2394            ..resolved_intra_tx()
2395        };
2396        let options = after_options(Ordering::Ascending, ev_boundary(2, 0));
2397        assert_eq!(seed.clone().apply_cursor_bounds(&options), seed);
2398        let options = after_options(Ordering::Ascending, ev_item(2, 0));
2399        assert_eq!(seed.clone().apply_cursor_bounds(&options), seed);
2400    }
2401
2402    /// Tightens the lower bound, and the terminal becomes the boundary just below the lowest
2403    /// admitted position, because the after cursor is where a descending scan stops: the slot
2404    /// after an Item cursor, which the scan excluded, and a Boundary cursor itself.
2405    #[test]
2406    fn descending_after_cursor_sets_terminal_and_tightens() {
2407        let options = after_options(Ordering::Descending, ev_item(5, 1));
2408        assert_eq!(
2409            resolved_intra_tx().apply_cursor_bounds(&options),
2410            ResolvedScan {
2411                bounds: IntraTxScanBounds {
2412                    lo: Bound::Excluded(IntraTxCoordinate {
2413                        tx_seq: 5,
2414                        index: 1,
2415                    }),
2416                    hi: Bound::Excluded(IntraTxCoordinate::start_of_tx(10)),
2417                },
2418                end_public_position: model_point(5, 2),
2419                end_scan_position: IntraTxCoordinate {
2420                    tx_seq: 5,
2421                    index: 2,
2422                },
2423                exhaustion: RangeExhaustion::CursorBound {
2424                    kind: CursorKind::Boundary,
2425                },
2426                ..resolved_intra_tx()
2427            }
2428        );
2429
2430        let options = after_options(Ordering::Descending, ev_boundary(5, 1));
2431        assert_eq!(
2432            resolved_intra_tx().apply_cursor_bounds(&options),
2433            ResolvedScan {
2434                bounds: IntraTxScanBounds {
2435                    lo: Bound::Included(IntraTxCoordinate {
2436                        tx_seq: 5,
2437                        index: 1,
2438                    }),
2439                    hi: Bound::Excluded(IntraTxCoordinate::start_of_tx(10)),
2440                },
2441                end_public_position: model_point(5, 1),
2442                end_scan_position: IntraTxCoordinate {
2443                    tx_seq: 5,
2444                    index: 1,
2445                },
2446                exhaustion: RangeExhaustion::CursorBound {
2447                    kind: CursorKind::Boundary,
2448                },
2449                ..resolved_intra_tx()
2450            }
2451        );
2452    }
2453
2454    /// When the after cursor empties the window, the record empties at the boundary just below
2455    /// what the cursor admits, at the public position there: the slot after an Item cursor, a
2456    /// Boundary cursor itself, both as Boundary.
2457    #[test]
2458    fn after_cursor_empties_descending_interval() {
2459        let seed = ResolvedScan {
2460            bounds: IntraTxScanBounds::from_range(
2461                IntraTxCoordinate::start_of_tx(3)..IntraTxCoordinate::start_of_tx(9),
2462            ),
2463            entry_checkpoint: 9,
2464            end_public_position: model_point(3, 0),
2465            end_scan_position: IntraTxCoordinate::start_of_tx(3),
2466            exhaustion: RangeExhaustion::CheckpointBound,
2467            window_claim: Some(3),
2468        };
2469
2470        let emptied_at = |coordinate: IntraTxCoordinate| ResolvedScan {
2471            bounds: IntraTxScanBounds::empty_at(coordinate),
2472            entry_checkpoint: 9,
2473            end_public_position: model_point(coordinate.tx_seq, coordinate.index),
2474            end_scan_position: coordinate,
2475            exhaustion: RangeExhaustion::CursorBound {
2476                kind: CursorKind::Boundary,
2477            },
2478            window_claim: Some(3),
2479        };
2480
2481        let options = after_options(Ordering::Descending, ev_item(100, 10));
2482        assert_eq!(
2483            seed.clone().apply_cursor_bounds(&options),
2484            emptied_at(IntraTxCoordinate {
2485                tx_seq: 100,
2486                index: 11,
2487            })
2488        );
2489        let options = after_options(Ordering::Descending, ev_boundary(100, 10));
2490        assert_eq!(
2491            seed.apply_cursor_bounds(&options),
2492            emptied_at(IntraTxCoordinate {
2493                tx_seq: 100,
2494                index: 10,
2495            })
2496        );
2497    }
2498
2499    /// (descending, before inside the window, either cursor kind (Item or
2500    /// Boundary)): hi becomes exclusive at the cursor; entry checkpoint and
2501    /// terminal untouched.
2502    #[test]
2503    fn before_cursor_tightens_descending_upper_bound() {
2504        let seed = ResolvedScan {
2505            entry_checkpoint: 8,
2506            ..resolved_intra_tx()
2507        };
2508        let expected = ResolvedScan {
2509            bounds: IntraTxScanBounds {
2510                lo: Bound::Included(IntraTxCoordinate::start_of_tx(0)),
2511                hi: Bound::Excluded(IntraTxCoordinate {
2512                    tx_seq: 5,
2513                    index: 1,
2514                }),
2515            },
2516            ..seed.clone()
2517        };
2518        let options = before_options(Ordering::Descending, ev_item(5, 1));
2519        assert_eq!(seed.clone().apply_cursor_bounds(&options), expected);
2520        let options = before_options(Ordering::Descending, ev_boundary(5, 1));
2521        assert_eq!(seed.apply_cursor_bounds(&options), expected);
2522    }
2523
2524    #[test]
2525    fn before_cursor_above_window_never_tightens() {
2526        for cursor in [ev_boundary(12, 0), ev_item(12, 0)] {
2527            let options = before_options(Ordering::Descending, cursor.clone());
2528            assert_eq!(
2529                resolved_intra_tx().apply_cursor_bounds(&options),
2530                resolved_intra_tx()
2531            );
2532
2533            let options = before_options(Ordering::Ascending, cursor);
2534            assert_eq!(
2535                resolved_intra_tx().apply_cursor_bounds(&options),
2536                resolved_intra_tx()
2537            );
2538        }
2539    }
2540
2541    #[test]
2542    fn ascending_before_cursor_sets_terminal_and_tightens() {
2543        let expected = ResolvedScan {
2544            bounds: IntraTxScanBounds {
2545                lo: Bound::Included(IntraTxCoordinate::start_of_tx(0)),
2546                hi: Bound::Excluded(IntraTxCoordinate {
2547                    tx_seq: 5,
2548                    index: 1,
2549                }),
2550            },
2551            entry_checkpoint: 2,
2552            end_public_position: model_point(5, 1),
2553            end_scan_position: IntraTxCoordinate {
2554                tx_seq: 5,
2555                index: 1,
2556            },
2557            exhaustion: RangeExhaustion::CursorBound {
2558                kind: CursorKind::Boundary,
2559            },
2560            window_claim: Some(8),
2561        };
2562        let options = before_options(Ordering::Ascending, ev_boundary(5, 1));
2563        assert_eq!(resolved_intra_tx().apply_cursor_bounds(&options), expected);
2564        let options = before_options(Ordering::Ascending, ev_item(5, 1));
2565        assert_eq!(resolved_intra_tx().apply_cursor_bounds(&options), expected);
2566    }
2567
2568    /// When a before cursor empties an ascending interval, the bounds are emptied at the cursor,
2569    /// and end_scan_position and end_public_position are set to the cursor's.
2570    #[test]
2571    fn before_cursor_empties_ascending_interval() {
2572        let seed = ResolvedScan {
2573            bounds: IntraTxScanBounds::from_range(
2574                IntraTxCoordinate::start_of_tx(3)..IntraTxCoordinate::start_of_tx(10),
2575            ),
2576            entry_checkpoint: 2,
2577            ..resolved_intra_tx()
2578        };
2579        let expected = ResolvedScan {
2580            bounds: IntraTxScanBounds::empty_at(IntraTxCoordinate::start_of_tx(3)),
2581            end_public_position: model_point(3, 0),
2582            end_scan_position: IntraTxCoordinate::start_of_tx(3),
2583            exhaustion: RangeExhaustion::CursorBound {
2584                kind: CursorKind::Boundary,
2585            },
2586            ..seed.clone()
2587        };
2588        let options = before_options(Ordering::Ascending, ev_boundary(3, 0));
2589        assert_eq!(seed.clone().apply_cursor_bounds(&options), expected);
2590        let options = before_options(Ordering::Ascending, ev_item(3, 0));
2591        assert_eq!(seed.apply_cursor_bounds(&options), expected);
2592    }
2593
2594    /// (ascending, after and before both present): a `before` past the window's end does not stop
2595    /// the scan, so an `after` past the window ends the page with the window's reason where it
2596    /// resumes; if both empty the interval, the before wins at the min position.
2597    #[test]
2598    fn ascending_with_both_cursors_picks_the_terminal_owner() {
2599        // Checkpoints 1..4, transactions 5..20. The before cursor lies past the window's end, and
2600        // the after cursor past it empties the window.
2601        let options = QueryOptions {
2602            limit_items: 100,
2603            ordering: Ordering::Ascending,
2604            after: Some(ev_item(25, 0)),
2605            before: Some(ev_boundary(30, 0)),
2606        };
2607        let resolved = resolve_event_request((Some(1), Some(4)), &options).unwrap();
2608        assert!(resolved.is_empty());
2609        assert_eq!(resolved.exhaustion, RangeExhaustion::CheckpointBound);
2610        assert_eq!(
2611            (resolved.end_public_position, resolved.end_scan_position),
2612            (
2613                model_point(25, 1),
2614                IntraTxCoordinate {
2615                    tx_seq: 25,
2616                    index: 1
2617                }
2618            )
2619        );
2620
2621        // When both cursors would empty, `before` cursor attribution remains.
2622        let options = QueryOptions {
2623            limit_items: 100,
2624            ordering: Ordering::Ascending,
2625            after: Some(ev_boundary(12, 0)),
2626            before: Some(ev_boundary(3, 0)),
2627        };
2628        assert_eq!(
2629            resolved_intra_tx().apply_cursor_bounds(&options),
2630            ResolvedScan {
2631                bounds: IntraTxScanBounds::empty_at(IntraTxCoordinate::start_of_tx(3)),
2632                entry_checkpoint: 2,
2633                end_public_position: model_point(3, 0),
2634                end_scan_position: IntraTxCoordinate::start_of_tx(3),
2635                exhaustion: RangeExhaustion::CursorBound {
2636                    kind: CursorKind::Boundary,
2637                },
2638                window_claim: Some(8),
2639            }
2640        );
2641    }
2642
2643    /// (descending, after and before both present): the after's frame stands when
2644    /// only it files; when both file, the min position wins; a before that empties
2645    /// overrides the after's earlier terminal.
2646    #[test]
2647    fn descending_with_both_cursors_picks_the_terminal_owner() {
2648        // After empties, before rejected: the after-claim survives.
2649        let options = QueryOptions {
2650            limit_items: 100,
2651            ordering: Ordering::Descending,
2652            after: Some(ev_boundary(12, 0)),
2653            before: Some(ev_boundary(15, 0)),
2654        };
2655        assert_eq!(
2656            resolved_intra_tx().apply_cursor_bounds(&options),
2657            ResolvedScan {
2658                bounds: IntraTxScanBounds::empty_at(IntraTxCoordinate::start_of_tx(12)),
2659                entry_checkpoint: 2,
2660                end_public_position: model_point(12, 0),
2661                end_scan_position: IntraTxCoordinate::start_of_tx(12),
2662                exhaustion: RangeExhaustion::CursorBound {
2663                    kind: CursorKind::Boundary,
2664                },
2665                window_claim: Some(8),
2666            }
2667        );
2668
2669        // After empties, before also files: before wins at the min position.
2670        let options = QueryOptions {
2671            limit_items: 100,
2672            ordering: Ordering::Descending,
2673            after: Some(ev_boundary(12, 0)),
2674            before: Some(ev_item(5, 2)),
2675        };
2676        assert_eq!(
2677            resolved_intra_tx().apply_cursor_bounds(&options),
2678            ResolvedScan {
2679                bounds: IntraTxScanBounds::empty_at(IntraTxCoordinate {
2680                    tx_seq: 5,
2681                    index: 2,
2682                }),
2683                entry_checkpoint: 2,
2684                end_public_position: model_point(5, 2),
2685                end_scan_position: IntraTxCoordinate {
2686                    tx_seq: 5,
2687                    index: 2,
2688                },
2689                exhaustion: RangeExhaustion::CursorBound {
2690                    kind: CursorKind::Boundary,
2691                },
2692                window_claim: Some(8),
2693            }
2694        );
2695
2696        // After tightens without emptying, before empties: the before-claim
2697        // overrides the after-cursor's eagerly written terminal.
2698        let options = QueryOptions {
2699            limit_items: 100,
2700            ordering: Ordering::Descending,
2701            after: Some(ev_item(5, 0)),
2702            before: Some(ev_item(5, 0)),
2703        };
2704        assert_eq!(
2705            resolved_intra_tx().apply_cursor_bounds(&options),
2706            ResolvedScan {
2707                bounds: IntraTxScanBounds::empty_at(IntraTxCoordinate::start_of_tx(5)),
2708                entry_checkpoint: 2,
2709                end_public_position: model_point(5, 0),
2710                end_scan_position: IntraTxCoordinate::start_of_tx(5),
2711                exhaustion: RangeExhaustion::CursorBound {
2712                    kind: CursorKind::Boundary,
2713                },
2714                window_claim: Some(8),
2715            }
2716        );
2717    }
2718
2719    /// (descending, after below the window): complete noop.
2720    #[test]
2721    fn after_cursor_rejected_descending_is_noop() {
2722        let seed = ResolvedScan {
2723            bounds: IntraTxScanBounds {
2724                lo: Bound::Included(IntraTxCoordinate::start_of_tx(5)),
2725                hi: Bound::Excluded(IntraTxCoordinate::start_of_tx(10)),
2726            },
2727            ..resolved_intra_tx()
2728        };
2729        let options = after_options(Ordering::Descending, ev_boundary(2, 0));
2730        assert_eq!(seed.clone().apply_cursor_bounds(&options), seed);
2731    }
2732
2733    /// A cursor whose bound coincides with the window's own is a no-op tighten, but
2734    /// the terminal still becomes the cursor's — CursorBound on an unchanged,
2735    /// non-empty record.
2736    #[test]
2737    fn cursor_at_the_window_bound_still_takes_the_terminal() {
2738        // Admission at the exact bound is a no-op tighten, but the stop-side
2739        // cursor still takes over the terminal: exhaustion flips to
2740        // CursorBound on a non-empty result whose bounds did not change.
2741        let options = before_options(Ordering::Ascending, ev_boundary(10, 0));
2742        assert_eq!(
2743            resolved_intra_tx().apply_cursor_bounds(&options),
2744            ResolvedScan {
2745                bounds: IntraTxScanBounds::from_range(
2746                    IntraTxCoordinate::start_of_tx(0)..IntraTxCoordinate::start_of_tx(10)
2747                ),
2748                entry_checkpoint: 2,
2749                end_public_position: model_point(10, 0),
2750                end_scan_position: IntraTxCoordinate::start_of_tx(10),
2751                exhaustion: RangeExhaustion::CursorBound {
2752                    kind: CursorKind::Boundary,
2753                },
2754                window_claim: Some(8),
2755            }
2756        );
2757
2758        let options = after_options(Ordering::Descending, ev_boundary(0, 0));
2759        assert_eq!(
2760            resolved_intra_tx().apply_cursor_bounds(&options),
2761            ResolvedScan {
2762                bounds: IntraTxScanBounds::from_range(
2763                    IntraTxCoordinate::start_of_tx(0)..IntraTxCoordinate::start_of_tx(10)
2764                ),
2765                entry_checkpoint: 2,
2766                end_public_position: LedgerPoint::GENESIS,
2767                end_scan_position: IntraTxCoordinate::start_of_tx(0),
2768                exhaustion: RangeExhaustion::CursorBound {
2769                    kind: CursorKind::Boundary,
2770                },
2771                window_claim: Some(8),
2772            }
2773        );
2774    }
2775
2776    // An after-Item cursor makes the exclusive lower bound one past the cursor, while an
2777    // after-Boundary cursor makes the lower bound equal to the cursor.
2778    #[test]
2779    fn tx_after_cursor_tightens_ascending_lower_bound() {
2780        // Item at n admits strictly-after symbolically; the successor lives
2781        // at the store edge, so both forms fetch from n + 1.
2782        let options = after_options(Ordering::Ascending, tx_item(12));
2783        // Resolves to `(12, 20)`
2784        let tightened = resolved_range(10..20).apply_cursor_bounds(&options);
2785        assert_eq!(
2786            tightened,
2787            ResolvedScan {
2788                bounds: ScanBounds {
2789                    lo: Bound::Excluded(12),
2790                    hi: Bound::Excluded(20),
2791                },
2792                ..resolved_range(10..20)
2793            }
2794        );
2795        // Projection into Range<u64> sets the lower bound as n + 1
2796        assert_eq!(tightened.range(), 13..20);
2797
2798        let options = after_options(Ordering::Ascending, tx_boundary(12));
2799        assert_eq!(
2800            resolved_range(10..20).apply_cursor_bounds(&options),
2801            ResolvedScan {
2802                bounds: ScanBounds {
2803                    lo: Bound::Included(12),
2804                    hi: Bound::Excluded(20),
2805                },
2806                ..resolved_range(10..20)
2807            }
2808        );
2809    }
2810
2811    /// Tightens the lower bound, and the terminal becomes the boundary just below the lowest
2812    /// admitted position, because the after cursor is where a descending scan stops: the position
2813    /// after an Item cursor, which the scan excluded, and a Boundary cursor itself.
2814    #[test]
2815    fn tx_descending_after_cursor_sets_terminal_and_tightens() {
2816        // Item at 12 and Boundary at 13 scan the same exclusive edge (13..20),
2817        // and end on the same terminal: the boundary at 13.
2818        let options = after_options(Ordering::Descending, tx_item(12));
2819        assert_eq!(
2820            resolved_range(10..20).apply_cursor_bounds(&options),
2821            ResolvedScan {
2822                bounds: ScanBounds {
2823                    lo: Bound::Excluded(12),
2824                    hi: Bound::Excluded(20),
2825                },
2826                entry_checkpoint: 0,
2827                end_public_position: after_transaction_point(13),
2828                end_scan_position: 13,
2829                exhaustion: RangeExhaustion::CursorBound {
2830                    kind: CursorKind::Boundary,
2831                },
2832                window_claim: Some(19),
2833            }
2834        );
2835        let options = after_options(Ordering::Descending, tx_boundary(13));
2836        assert_eq!(
2837            resolved_range(10..20).apply_cursor_bounds(&options),
2838            ResolvedScan {
2839                bounds: ScanBounds::from_range(13..20),
2840                entry_checkpoint: 0,
2841                end_public_position: after_transaction_point(13),
2842                end_scan_position: 13,
2843                exhaustion: RangeExhaustion::CursorBound {
2844                    kind: CursorKind::Boundary,
2845                },
2846                window_claim: Some(19),
2847            }
2848        );
2849    }
2850
2851    /// When the after cursor empties the window, the record empties at the boundary just below
2852    /// what the cursor admits, at the public position there, as Boundary for either cursor kind.
2853    #[test]
2854    fn tx_after_cursor_empties_descending_interval() {
2855        // Item at 24 and Boundary at 25 scan the same exclusive edge, and both empty the window
2856        // at the boundary at 25, after transaction 24.
2857        let options = after_options(Ordering::Descending, tx_frontier(25));
2858        assert_eq!(
2859            resolved_range(10..20).apply_cursor_bounds(&options),
2860            ResolvedScan {
2861                bounds: ScanBounds::from_range(25..25),
2862                entry_checkpoint: 0,
2863                end_public_position: after_transaction_point(25),
2864                end_scan_position: 25,
2865                exhaustion: RangeExhaustion::CursorBound {
2866                    kind: CursorKind::Boundary,
2867                },
2868                window_claim: Some(19),
2869            }
2870        );
2871        let options = after_options(Ordering::Descending, tx_item(24));
2872        assert_eq!(
2873            resolved_range(10..20).apply_cursor_bounds(&options),
2874            ResolvedScan {
2875                bounds: ScanBounds::from_range(25..25),
2876                entry_checkpoint: 0,
2877                end_public_position: after_transaction_point(25),
2878                end_scan_position: 25,
2879                exhaustion: RangeExhaustion::CursorBound {
2880                    kind: CursorKind::Boundary,
2881                },
2882                window_claim: Some(19),
2883            }
2884        );
2885    }
2886
2887    /// after-Item at n and after-Boundary at n + 1 admit the same interval, and a page they leave
2888    /// empty past the window ends on the same terminal: the boundary at n + 1, after item n.
2889    #[test]
2890    fn tx_after_item_and_successor_boundary_admit_the_same_interval() {
2891        let item = after_options(Ordering::Ascending, tx_item(24));
2892        let successor = after_options(Ordering::Ascending, tx_frontier(25));
2893
2894        // Checkpoints 1..6, transactions 5..30: both admit 25..30.
2895        let wide = (Some(1), Some(6));
2896        assert_eq!(resolve_tx_request(wide, &item).unwrap().range(), 25..30);
2897        assert_eq!(
2898            resolve_tx_request(wide, &successor).unwrap().range(),
2899            25..30
2900        );
2901
2902        // Checkpoints 1..4, transactions 5..20: both leave the window empty and end at the
2903        // boundary at 25 with the window's reason.
2904        let narrow = (Some(1), Some(4));
2905        let resolved = resolve_tx_request(narrow, &item).unwrap();
2906        assert_eq!(resolved, resolve_tx_request(narrow, &successor).unwrap());
2907        assert!(resolved.is_empty());
2908        assert_eq!(
2909            (
2910                resolved.exhaustion,
2911                resolved.end_public_position,
2912                resolved.end_scan_position
2913            ),
2914            (
2915                RangeExhaustion::CheckpointBound,
2916                after_transaction_point(25),
2917                25
2918            )
2919        );
2920    }
2921
2922    /// (ascending, after-Boundary at u64::MAX): nothing can lie at MAX; empties at
2923    /// (cursor's public position, MAX), Boundary.
2924    #[test]
2925    fn tx_after_boundary_at_max_empties_interval() {
2926        let options = after_options(Ordering::Ascending, tx_boundary(u64::MAX));
2927        assert_eq!(
2928            resolved_range(10..20).apply_cursor_bounds(&options),
2929            empty_resolved_range(
2930                model_point(u64::MAX, 0),
2931                u64::MAX,
2932                RangeExhaustion::CursorBound {
2933                    kind: CursorKind::Boundary,
2934                },
2935            )
2936        );
2937    }
2938
2939    /// If the bounds are already empty, cursors do not apply.
2940    #[test]
2941    fn tx_after_item_at_max_lets_before_cursor_win() {
2942        // An after-Item at u64::MAX is an ordinary emptying admission (the
2943        // saturated successor), not a short-circuit: a crossed before-cursor
2944        // still participates and wins the attribution at the min position.
2945        let options = QueryOptions {
2946            limit_items: 100,
2947            ordering: Ordering::Ascending,
2948            after: Some(tx_item(u64::MAX)),
2949            before: Some(tx_boundary(15)),
2950        };
2951        assert_eq!(
2952            resolved_range(10..20).apply_cursor_bounds(&options),
2953            ResolvedScan {
2954                bounds: ScanBounds::from_range(15..15),
2955                entry_checkpoint: 0,
2956                end_public_position: model_point(15, 0),
2957                end_scan_position: 15,
2958                exhaustion: RangeExhaustion::CursorBound {
2959                    kind: CursorKind::Boundary,
2960                },
2961                window_claim: Some(19),
2962            }
2963        );
2964
2965        // Descending: the seed's entry checkpoint stands.
2966        let seed = ResolvedScan {
2967            entry_checkpoint: 7,
2968            ..resolved_range(10..20)
2969        };
2970        let options = QueryOptions {
2971            limit_items: 100,
2972            ordering: Ordering::Descending,
2973            after: Some(tx_item(u64::MAX)),
2974            before: Some(tx_boundary(15)),
2975        };
2976        assert_eq!(
2977            seed.apply_cursor_bounds(&options),
2978            ResolvedScan {
2979                bounds: ScanBounds::from_range(15..15),
2980                entry_checkpoint: 7,
2981                end_public_position: model_point(15, 0),
2982                end_scan_position: 15,
2983                exhaustion: RangeExhaustion::CursorBound {
2984                    kind: CursorKind::Boundary,
2985                },
2986                window_claim: Some(19),
2987            }
2988        );
2989    }
2990
2991    /// For some ResolvedScan<u64>, if its bounds are Excluded(A) and Excluded(A + 1), its bounds
2992    /// report non-empty, but its range is empty.
2993    /// `test_list_transactions_after_last_item_ends_at_window_bound` checks that the result set is
2994    /// empty.
2995    #[test]
2996    fn tx_after_item_at_window_edge_defers_to_drain() {
2997        let options = after_options(Ordering::Ascending, tx_item(19));
2998        let initial_range = resolved_range(10..20);
2999        let resolved = initial_range.clone().apply_cursor_bounds(&options);
3000        assert_eq!(
3001            resolved,
3002            ResolvedScan {
3003                bounds: ScanBounds {
3004                    lo: Bound::Excluded(19),
3005                    hi: Bound::Excluded(20),
3006                },
3007                ..initial_range
3008            }
3009        );
3010        assert!(!resolved.is_empty());
3011        assert!(resolved.range().is_empty());
3012    }
3013
3014    /// Exclusive after on descending bumps the bounds, and sets the end_public_position,
3015    /// end_scan_position (the boundary just above the item), and exhaustion from the after
3016    /// cursor.
3017    #[test]
3018    fn tx_after_item_at_window_edge_descending_keeps_stamped_terminal() {
3019        let options = after_options(Ordering::Descending, tx_item(19));
3020        let initial_range = resolved_range(10..20);
3021        let resolved = initial_range.clone().apply_cursor_bounds(&options);
3022        assert_eq!(
3023            resolved,
3024            ResolvedScan {
3025                bounds: ScanBounds {
3026                    lo: Bound::Excluded(19),
3027                    hi: Bound::Excluded(20),
3028                },
3029                end_public_position: after_transaction_point(20),
3030                end_scan_position: 20,
3031                exhaustion: RangeExhaustion::CursorBound {
3032                    kind: CursorKind::Boundary,
3033                },
3034                ..initial_range
3035            }
3036        );
3037        assert!(resolved.range().is_empty());
3038    }
3039
3040    /// On a descending scan, when the after-Item cursor is exactly on the terminating window, the
3041    /// terminal values remain unchanged; the cursor does not overwrite the original bounds as it is
3042    /// not additionally restrictive.
3043    #[test]
3044    fn tx_after_item_below_window_start_descending_is_noop() {
3045        let options = after_options(Ordering::Descending, tx_item(9));
3046        assert_eq!(
3047            resolved_range(10..20).apply_cursor_bounds(&options),
3048            resolved_range(10..20)
3049        );
3050    }
3051
3052    #[test]
3053    fn item_cursor_can_be_used_as_after_or_before() {
3054        let token = tx_item(11).encode();
3055
3056        let mut request = ProtoQueryOptions::default();
3057        request.after = Some(token.clone());
3058        let options = query_options_from_proto(Some(&request)).unwrap();
3059        assert_eq!(
3060            resolved_range(10..20).apply_cursor_bounds(&options).range(),
3061            12..20
3062        );
3063
3064        request.after = None;
3065        request.before = Some(token);
3066        let options = query_options_from_proto(Some(&request)).unwrap();
3067        assert_eq!(
3068            resolved_range(10..20).apply_cursor_bounds(&options).range(),
3069            10..11
3070        );
3071    }
3072
3073    /// Tip for the cursor-past-tip tests: checkpoints below 20 are indexed, and checkpoint `c`
3074    /// starts at transaction `5 * c`, so the first unindexed transaction is 100.
3075    const TIP: u64 = 20;
3076
3077    fn first_tx(checkpoint: u64) -> u64 {
3078        5 * checkpoint
3079    }
3080
3081    fn resolve_checkpoints(
3082        end_checkpoint: Option<u64>,
3083        options: &QueryOptions,
3084    ) -> Result<ResolvedScan<u64>, RpcError> {
3085        resolve_checkpoint_request((None, end_checkpoint), options)
3086    }
3087
3088    fn resolve_transactions(options: &QueryOptions) -> Result<ResolvedScan<u64>, RpcError> {
3089        resolve_tx_request((None, None), options)
3090    }
3091
3092    fn resolve_events(options: &QueryOptions) -> Result<ResolvedScan<IntraTxCoordinate>, RpcError> {
3093        resolve_event_request((None, None), options)
3094    }
3095
3096    fn is_out_of_range<P>(resolved: Result<ResolvedScan<P>, RpcError>) -> bool {
3097        resolved.is_err_and(|e| e.into_status_proto().code == tonic::Code::OutOfRange as i32)
3098    }
3099
3100    /// Where a resolved scan's page ends: `(the end's public position, terminal position, end
3101    /// reason, natural end claim)`.
3102    fn page_end<P: ScanPosition>(
3103        resolved: &ResolvedScan<P>,
3104        options: &QueryOptions,
3105    ) -> (LedgerPoint, P, RangeExhaustion, Option<u64>)
3106    where
3107        CursorToken: ScanCursor<P>,
3108    {
3109        (
3110            resolved.end_public_position,
3111            resolved.end_scan_position,
3112            resolved.exhaustion,
3113            resolved.natural_end_claim(options),
3114        )
3115    }
3116
3117    /// An ascending `after` cursor at the tip is caught up: its page ends at the tip and claims
3118    /// the checkpoint below it. A window the request ends at the tip does not reach it, so a cursor
3119    /// past the tip ends that window's page where it resumes, with `CheckpointBound` and the
3120    /// window's claim.
3121    #[test]
3122    fn ascending_after_cursor_at_the_tip_edge() {
3123        let ascending = |cursor| after_options(Ordering::Ascending, cursor);
3124
3125        let tip_boundary = CursorToken::boundary(Position::Checkpoints { checkpoint: TIP });
3126        for cursor in [cp_item(TIP - 1), tip_boundary] {
3127            let options = ascending(cursor);
3128            let resolved = resolve_checkpoints(None, &options).unwrap();
3129            assert!(resolved.is_empty());
3130            assert_eq!(
3131                page_end(&resolved, &options),
3132                (
3133                    LedgerPoint::checkpoint_start(TIP),
3134                    TIP,
3135                    RangeExhaustion::LedgerTip,
3136                    Some(TIP - 1)
3137                )
3138            );
3139        }
3140
3141        let options = ascending(cp_item(TIP + 5));
3142        let resolved = resolve_checkpoints(Some(TIP), &options).unwrap();
3143        assert_eq!(
3144            page_end(&resolved, &options),
3145            (
3146                LedgerPoint::checkpoint_start(TIP + 6),
3147                TIP + 6,
3148                RangeExhaustion::CheckpointBound,
3149                Some(TIP - 1)
3150            )
3151        );
3152    }
3153
3154    #[test]
3155    fn descending_cursors_past_the_tip_are_out_of_range() {
3156        let before = |cursor| before_options(Ordering::Descending, cursor);
3157        let after = |cursor| after_options(Ordering::Descending, cursor);
3158        let tip_boundary = || CursorToken::boundary(Position::Checkpoints { checkpoint: TIP });
3159
3160        assert!(resolve_checkpoints(None, &before(cp_item(TIP - 1))).is_ok());
3161        assert!(resolve_checkpoints(None, &before(tip_boundary())).is_ok());
3162        assert!(is_out_of_range(resolve_checkpoints(
3163            None,
3164            &before(cp_item(TIP))
3165        )));
3166
3167        // `after` bounds the far end of a descending scan. At the tip it leaves an empty page that
3168        // ends at that cursor; past it, it admits only positions this server has not indexed.
3169        let at_tip = resolve_checkpoints(None, &after(tip_boundary())).unwrap();
3170        assert!(at_tip.is_empty());
3171        assert_eq!(
3172            at_tip.exhaustion,
3173            RangeExhaustion::CursorBound {
3174                kind: CursorKind::Boundary
3175            }
3176        );
3177        assert!(is_out_of_range(resolve_checkpoints(
3178            None,
3179            &after(cp_item(TIP))
3180        )));
3181        assert!(is_out_of_range(resolve_checkpoints(
3182            None,
3183            &after(cp_item(TIP + 5))
3184        )));
3185
3186        // A window the request ends at or below the tip is exhausted, not rejected.
3187        let past_window = resolve_checkpoints(Some(TIP), &after(cp_item(TIP + 5))).unwrap();
3188        assert!(past_window.is_empty());
3189    }
3190
3191    // Cursors read in either direction, on the ledger of the cursor-past-tip tests (checkpoint
3192    // `c` holds transactions `5c..5c + 5`, tip at checkpoint 20), where every transaction emits
3193    // events 0 and 1.
3194
3195    /// What issued a cursor, which decides the public position it carries.
3196    #[derive(Clone, Copy, Debug)]
3197    enum Issuer {
3198        /// An item: the model point of the position.
3199        Item,
3200        /// A range end, a subscription boundary, a restated cursor bound or a descending scan
3201        /// frontier: the model point of the position.
3202        ExactBoundary,
3203        /// An ascending scan frontier: after the position before it (see
3204        /// [`after_transaction_point`]).
3205        AscendingFrontier,
3206    }
3207
3208    const ISSUERS: [Issuer; 3] = [
3209        Issuer::Item,
3210        Issuer::ExactBoundary,
3211        Issuer::AscendingFrontier,
3212    ];
3213
3214    /// A request's `start_checkpoint` and `end_checkpoint`.
3215    type Window = (Option<u64>, Option<u64>);
3216
3217    /// Checkpoint windows: open, inside the ledger, open at one end, and one checkpoint wide.
3218    const WINDOWS: [Window; 5] = [
3219        (None, None),
3220        (Some(4), Some(13)),
3221        (Some(7), None),
3222        (None, Some(7)),
3223        (Some(5), Some(6)),
3224    ];
3225
3226    /// Checkpoint windows reaching past the tip: an `end_checkpoint` above it, and a
3227    /// `start_checkpoint` at it with `end_checkpoint` unset. A descending request over either is
3228    /// out of range.
3229    const PAST_TIP_WINDOWS: [Window; 2] = [(Some(15), Some(TIP + 1)), (Some(TIP), None)];
3230
3231    const ORDERINGS: [Ordering; 2] = [Ordering::Ascending, Ordering::Descending];
3232
3233    fn containing_checkpoint(tx: u64) -> u64 {
3234        tx / 5
3235    }
3236
3237    /// The model point just before the event slot `(tx, index)`, or before transaction `tx` at
3238    /// index 0.
3239    fn model_point(tx: u64, index: u32) -> LedgerPoint {
3240        LedgerPoint::event(containing_checkpoint(tx), tx % 5, index)
3241    }
3242
3243    /// The point an ascending frontier at the start of `tx` carries: placed after the transaction
3244    /// before it (see [`RowPlacement`]), so at a checkpoint's start it names the end of the
3245    /// checkpoint before.
3246    ///
3247    /// [`RowPlacement`]: crate::ledger_history::row_placement::RowPlacement
3248    fn after_transaction_point(tx: u64) -> LedgerPoint {
3249        tx.checked_sub(1).map_or(LedgerPoint::GENESIS, |previous| {
3250            LedgerPoint::transaction(containing_checkpoint(previous), previous % 5 + 1)
3251        })
3252    }
3253
3254    /// The transaction cursor `issuer` mints at `tx`, where it can mint one, carrying the public
3255    /// position that issuer places it at.
3256    fn issued_tx_cursor(issuer: Issuer, tx: u64) -> Option<CursorToken> {
3257        let indexed = tx < first_tx(TIP);
3258        match issuer {
3259            Issuer::Item => indexed.then(|| tx_item(tx)),
3260            Issuer::ExactBoundary => Some(tx_boundary(tx)),
3261            Issuer::AscendingFrontier => Some(tx_frontier(tx)),
3262        }
3263    }
3264
3265    /// The event cursor `issuer` mints at `(tx, index)`, where it can mint one, carrying the
3266    /// public position that issuer places it at.
3267    fn issued_event_cursor(issuer: Issuer, tx: u64, index: u32) -> Option<CursorToken> {
3268        let indexed = tx < first_tx(TIP);
3269        match issuer {
3270            Issuer::Item => (indexed && index < 2).then(|| ev_item(tx, index)),
3271            Issuer::ExactBoundary => (indexed || index == 0).then(|| ev_boundary(tx, index)),
3272            Issuer::AscendingFrontier => (indexed || index == 0).then(|| {
3273                let point = if index == 0 {
3274                    after_transaction_point(tx)
3275                } else {
3276                    model_point(tx, index)
3277                };
3278                CursorToken::boundary(ev_position(tx, index, point))
3279            }),
3280        }
3281    }
3282
3283    fn every_tx_cursor(txs: impl Iterator<Item = u64> + Clone) -> Vec<CursorToken> {
3284        ISSUERS
3285            .iter()
3286            .flat_map(|&issuer| {
3287                txs.clone()
3288                    .filter_map(move |tx| issued_tx_cursor(issuer, tx))
3289            })
3290            .collect()
3291    }
3292
3293    fn every_event_cursor(txs: impl Iterator<Item = u64> + Clone) -> Vec<CursorToken> {
3294        ISSUERS
3295            .iter()
3296            .flat_map(|&issuer| {
3297                txs.clone().flat_map(move |tx| {
3298                    (0..3).filter_map(move |index| issued_event_cursor(issuer, tx, index))
3299                })
3300            })
3301            .collect()
3302    }
3303
3304    /// Transactions on both sides of checkpoint edges, the window edges, genesis and the tip.
3305    fn edge_txs() -> impl Iterator<Item = u64> + Clone {
3306        [
3307            0, 1, 4, 5, 6, 19, 20, 21, 24, 25, 26, 29, 30, 34, 35, 36, 64, 65, 66, 94, 95, 96, 99,
3308            100,
3309        ]
3310        .into_iter()
3311    }
3312
3313    /// A smaller set of edge transactions for event cursor pairs, which carry three slots each.
3314    fn event_edge_txs() -> impl Iterator<Item = u64> + Clone {
3315        [0, 4, 5, 20, 24, 25, 29, 30, 34, 35, 64, 65, 95, 99, 100].into_iter()
3316    }
3317
3318    /// Transaction cursors a server further along than the model mints past its tip: in the first
3319    /// unindexed checkpoint and the one after it.
3320    fn past_tip_tx_cursors() -> Vec<CursorToken> {
3321        let tip_tx = first_tx(TIP);
3322        [
3323            tx_item(tip_tx),
3324            tx_boundary(tip_tx + 1),
3325            tx_item(tip_tx + 4),
3326            tx_boundary(tip_tx + 5),
3327            tx_item(tip_tx + 7),
3328        ]
3329        .to_vec()
3330    }
3331
3332    /// Event cursors a server further along than the model mints past its tip.
3333    fn past_tip_event_cursors() -> Vec<CursorToken> {
3334        let tip_tx = first_tx(TIP);
3335        [
3336            ev_item(tip_tx, 0),
3337            ev_boundary(tip_tx, 1),
3338            ev_item(tip_tx, 1),
3339            ev_boundary(tip_tx + 1, 0),
3340            ev_item(tip_tx + 5, 2),
3341        ]
3342        .to_vec()
3343    }
3344
3345    fn options_with(
3346        ordering: Ordering,
3347        after: Option<CursorToken>,
3348        before: Option<CursorToken>,
3349    ) -> QueryOptions {
3350        QueryOptions {
3351            limit_items: 100,
3352            ordering,
3353            after,
3354            before,
3355        }
3356    }
3357
3358    /// Every single-cursor request and, over `pair_cursors`, every two-cursor request, in each
3359    /// window, including those reaching past the tip, and each ordering.
3360    fn requests(
3361        cursors: &[CursorToken],
3362        pair_cursors: &[CursorToken],
3363    ) -> Vec<(Window, QueryOptions)> {
3364        requests_in(
3365            WINDOWS.into_iter().chain(PAST_TIP_WINDOWS),
3366            cursors,
3367            pair_cursors,
3368        )
3369    }
3370
3371    /// [`requests`] in `windows`.
3372    fn requests_in(
3373        windows: impl IntoIterator<Item = Window>,
3374        cursors: &[CursorToken],
3375        pair_cursors: &[CursorToken],
3376    ) -> Vec<(Window, QueryOptions)> {
3377        let mut requests = Vec::new();
3378        for window in windows {
3379            for ordering in ORDERINGS {
3380                for cursor in cursors {
3381                    requests.push((window, options_with(ordering, Some(cursor.clone()), None)));
3382                    requests.push((window, options_with(ordering, None, Some(cursor.clone()))));
3383                }
3384                for after in pair_cursors {
3385                    for before in pair_cursors {
3386                        requests.push((
3387                            window,
3388                            options_with(ordering, Some(after.clone()), Some(before.clone())),
3389                        ));
3390                    }
3391                }
3392            }
3393        }
3394        requests
3395    }
3396
3397    /// A request's scan and the window it was resolved from, which places its terminal in
3398    /// ledger coordinates. The model's checkpoint windows have checkpoint edges, so their ledger
3399    /// coordinates are a checkpoint scan's whatever the lane.
3400    fn resolve_in_window<P: ScanPosition>(
3401        window: Window,
3402        options: &QueryOptions,
3403        lane_range: impl FnOnce(Range<u64>) -> Range<P>,
3404    ) -> Result<(ResolvedScan<P>, ScanWindow<P>), RpcError>
3405    where
3406        CursorToken: ScanCursor<P>,
3407    {
3408        let cp_range = ResolvedCheckpointRange::from_request(window.0, window.1, TIP, options)?;
3409        let ledger = LedgerWindow::checkpoints(&cp_range.range, window.0, window.1);
3410        let scan_window = ScanWindow::whole_checkpoints(lane_range(cp_range.range.clone()), ledger);
3411        let resolved = ResolvedScan::resolve(cp_range, scan_window.clone(), options)?;
3412        Ok((resolved, scan_window))
3413    }
3414
3415    fn resolve_tx_in_window(
3416        window: Window,
3417        options: &QueryOptions,
3418    ) -> Result<(ResolvedScan<u64>, ScanWindow<u64>), RpcError> {
3419        resolve_in_window(window, options, |range| {
3420            first_tx(range.start)..first_tx(range.end)
3421        })
3422    }
3423
3424    fn resolve_event_in_window(
3425        window: Window,
3426        options: &QueryOptions,
3427    ) -> Result<
3428        (
3429            ResolvedScan<IntraTxCoordinate>,
3430            ScanWindow<IntraTxCoordinate>,
3431        ),
3432        RpcError,
3433    > {
3434        resolve_in_window(window, options, |range| {
3435            tx_window(first_tx(range.start)..first_tx(range.end))
3436        })
3437    }
3438
3439    fn resolve_checkpoint_in_window(
3440        window: Window,
3441        options: &QueryOptions,
3442    ) -> Result<(ResolvedScan<u64>, ScanWindow<u64>), RpcError> {
3443        resolve_in_window(window, options, std::convert::identity)
3444    }
3445
3446    fn resolve_tx_request(
3447        window: Window,
3448        options: &QueryOptions,
3449    ) -> Result<ResolvedScan<u64>, RpcError> {
3450        resolve_tx_in_window(window, options).map(|(resolved, _)| resolved)
3451    }
3452
3453    fn resolve_event_request(
3454        window: Window,
3455        options: &QueryOptions,
3456    ) -> Result<ResolvedScan<IntraTxCoordinate>, RpcError> {
3457        resolve_event_in_window(window, options).map(|(resolved, _)| resolved)
3458    }
3459
3460    fn resolve_checkpoint_request(
3461        window: Window,
3462        options: &QueryOptions,
3463    ) -> Result<ResolvedScan<u64>, RpcError> {
3464        resolve_checkpoint_in_window(window, options).map(|(resolved, _)| resolved)
3465    }
3466
3467    fn ledger_txs() -> Vec<u64> {
3468        (0..first_tx(TIP)).collect()
3469    }
3470
3471    /// Every event slot a cursor can name: events 0 and 1 of each transaction, and the empty
3472    /// slot after them.
3473    fn ledger_event_slots() -> Vec<IntraTxCoordinate> {
3474        (0..first_tx(TIP))
3475            .flat_map(|tx_seq| (0..3).map(move |index| IntraTxCoordinate { tx_seq, index }))
3476            .collect()
3477    }
3478
3479    /// Whether the window and cursors of a request admit the position at `key` (scan order).
3480    fn admits(window: Window, options: &QueryOptions, key: (u64, u32)) -> bool {
3481        let start = first_tx(window.0.unwrap_or(0));
3482        let end = first_tx(window.1.unwrap_or(TIP).min(TIP));
3483        let in_window = start <= key.0 && key.0 < end;
3484        let after = options.after.as_ref().is_none_or(|cursor| {
3485            let cursor_key = scan_order(&cursor.position);
3486            match cursor.kind {
3487                CursorKind::Item => key > cursor_key,
3488                CursorKind::Boundary => key >= cursor_key,
3489            }
3490        });
3491        let before = options
3492            .before
3493            .as_ref()
3494            .is_none_or(|cursor| key < scan_order(&cursor.position));
3495        in_window && after && before
3496    }
3497
3498    /// A position's place in ascending scan order on the model ledger, in transaction space:
3499    /// checkpoint `c` sits at its first transaction.
3500    fn scan_order(position: &Position) -> (u64, u32) {
3501        match *position {
3502            Position::Checkpoints { checkpoint } => (first_tx(checkpoint), 0),
3503            Position::Transactions { tx_seq, .. } => (tx_seq, 0),
3504            Position::Events {
3505                tx_seq,
3506                event_index,
3507                ..
3508            } => (tx_seq, event_index),
3509        }
3510    }
3511
3512    fn status(error: RpcError) -> (i32, String) {
3513        let status = error.into_status_proto();
3514        (status.code, status.message)
3515    }
3516
3517    /// One request on the model ledger, over `positions`, every scan position its cursors can
3518    /// name:
3519    /// - it admits exactly the positions its window and cursors admit;
3520    /// - it errs exactly when it is descending and either its window reaches past the tip, or its
3521    ///   window reaches the tip and a cursor names a position past the tip, and then with
3522    ///   `OutOfRange`;
3523    /// - in a window that reaches the tip, empty or not, an ascending request whose `after` cursor
3524    ///   resumes past the tip ends an empty page where that cursor resumes, at the public position
3525    ///   there, with `LedgerTip` and no checkpoint claim, or at a `before` cursor below that
3526    ///   position, at `before`'s public position, with `CursorBound` (at `after`'s, where `before`
3527    ///   is at that position);
3528    /// - otherwise, in a non-empty window, its entry checkpoint is the window's first checkpoint
3529    ///   in scan direction, whatever its cursors' public positions;
3530    /// - otherwise, in a non-empty window, it ends with the window's reason and claims the
3531    ///   window's last checkpoint in scan direction exactly when no far cursor stops the scan at
3532    ///   or before the window's edge (ascending, a `before` at or below the window's end;
3533    ///   descending, an `after` at or above the window's start), and otherwise with
3534    ///   `CursorBound`. It ends at the window's edge, or past it, where a starting cursor beyond
3535    ///   the edge resumes: the first position an `after` cursor admits, or a `before` cursor's
3536    ///   position.
3537    fn check_request<P: ScanPosition + std::fmt::Debug>(
3538        window: Window,
3539        options: &QueryOptions,
3540        resolve: impl Fn(Window, &QueryOptions) -> Result<ResolvedScan<P>, RpcError>,
3541        positions: &[P],
3542        key: impl Fn(P) -> (u64, u32),
3543    ) where
3544        CursorToken: ScanCursor<P>,
3545    {
3546        let context = format!("window {window:?}, {options:?}");
3547        let tip_key = (first_tx(TIP), 0);
3548        // A boundary exactly at the tip is where a caught-up scan resumes; an item there, or any
3549        // position beyond it, has not been indexed.
3550        let past_tip = |cursor: &CursorToken| {
3551            let cursor_key = scan_order(&cursor.position);
3552            match cursor.kind {
3553                CursorKind::Item => cursor_key >= tip_key,
3554                CursorKind::Boundary => cursor_key > tip_key,
3555            }
3556        };
3557        let window_reaches_tip = window.1.is_none_or(|end| end > TIP);
3558        let descending_window_past_tip = options.ordering == Ordering::Descending
3559            && match window.1 {
3560                Some(end) => end > TIP,
3561                None => window.0.unwrap_or(0) >= TIP,
3562            };
3563        let descending_cursor_past_tip = options.ordering == Ordering::Descending
3564            && window_reaches_tip
3565            && [options.before.as_ref(), options.after.as_ref()]
3566                .into_iter()
3567                .flatten()
3568                .any(past_tip);
3569        let out_of_range = descending_window_past_tip || descending_cursor_past_tip;
3570        let resolved = match resolve(window, options) {
3571            Ok(resolved) => resolved,
3572            Err(error) => {
3573                let (code, message) = status(error);
3574                assert!(out_of_range, "{code}: {message}: {context}");
3575                assert_eq!(code, tonic::Code::OutOfRange as i32, "{message}: {context}");
3576                return;
3577            }
3578        };
3579        assert!(!out_of_range, "a request past the tip resolves: {context}");
3580        let admitted: Vec<P> = positions
3581            .iter()
3582            .copied()
3583            .filter(|position| resolved.bounds.contains(*position))
3584            .collect();
3585        let expected: Vec<P> = positions
3586            .iter()
3587            .copied()
3588            .filter(|position| admits(window, options, key(*position)))
3589            .collect();
3590        assert_eq!(admitted, expected, "admitted positions: {context}");
3591
3592        let cursor_key = |cursor: &CursorToken| key(cursor.coordinate());
3593        let first_admitted_key = |cursor: &CursorToken| {
3594            let position: P = cursor.coordinate();
3595            match cursor.kind {
3596                CursorKind::Item => position.successor().map(&key),
3597                CursorKind::Boundary => Some(key(position)),
3598            }
3599        };
3600
3601        if options.is_ascending()
3602            && window_reaches_tip
3603            && let Some(after) = options.after.as_ref().filter(|after| past_tip(after))
3604        {
3605            let resume = first_admitted_key(after).expect("model cursors have a successor");
3606            let resume_point = match after.kind {
3607                CursorKind::Item => after.position.item_resume(ScanDirection::Ascending),
3608                CursorKind::Boundary => after.position.public_position(),
3609            };
3610            // The terminal cursor carries `after`'s point where both cursors name its position.
3611            let (reason, end, end_cursor_public_position) = match options.before.as_ref() {
3612                Some(before) if cursor_key(before) <= resume => (
3613                    RangeExhaustion::CursorBound {
3614                        kind: CursorKind::Boundary,
3615                    },
3616                    cursor_key(before),
3617                    if cursor_key(before) == resume {
3618                        resume_point
3619                    } else {
3620                        before.position.public_position()
3621                    },
3622                ),
3623                _ => (RangeExhaustion::LedgerTip, resume, resume_point),
3624            };
3625            assert!(resolved.is_empty(), "empty page: {context}");
3626            assert_eq!(resolved.exhaustion, reason, "end reason: {context}");
3627            assert_eq!(
3628                key(resolved.end_scan_position),
3629                end,
3630                "end scan position: {context}"
3631            );
3632            assert_eq!(
3633                resolved.end_cursor_public_position(options),
3634                end_cursor_public_position,
3635                "end cursor public position: {context}"
3636            );
3637            assert_eq!(
3638                resolved.natural_end_claim(options),
3639                None,
3640                "checkpoint claim: {context}"
3641            );
3642            return;
3643        }
3644
3645        let window_start = window.0.unwrap_or(0);
3646        let window_end = window.1.unwrap_or(TIP).min(TIP);
3647        if window_start >= window_end {
3648            return;
3649        }
3650        let window_lo = (first_tx(window_start), 0);
3651        let window_hi = (first_tx(window_end), 0);
3652        // Where the page ends with the window's reason, or `None` when a far cursor stops the
3653        // scan at or before the window's edge.
3654        let (entry, claim, reason, window_reason_end) = match options.ordering {
3655            Ordering::Ascending => (
3656                window_start,
3657                window_end - 1,
3658                if window_reaches_tip {
3659                    RangeExhaustion::LedgerTip
3660                } else {
3661                    RangeExhaustion::CheckpointBound
3662                },
3663                if options
3664                    .before
3665                    .as_ref()
3666                    .is_some_and(|before| cursor_key(before) <= window_hi)
3667                {
3668                    None
3669                } else {
3670                    match options.after.as_ref() {
3671                        None => Some(window_hi),
3672                        Some(after) => first_admitted_key(after).map(|first| first.max(window_hi)),
3673                    }
3674                },
3675            ),
3676            Ordering::Descending => (
3677                window_end - 1,
3678                window_start,
3679                RangeExhaustion::CheckpointBound,
3680                if options
3681                    .after
3682                    .as_ref()
3683                    .is_some_and(|after| cursor_key(after) >= window_lo)
3684                {
3685                    None
3686                } else {
3687                    Some(
3688                        options
3689                            .before
3690                            .as_ref()
3691                            .map_or(window_lo, |before| cursor_key(before).min(window_lo)),
3692                    )
3693                },
3694            ),
3695        };
3696        assert_eq!(
3697            resolved.entry_checkpoint, entry,
3698            "entry checkpoint: {context}"
3699        );
3700        match window_reason_end {
3701            Some(end) => {
3702                assert_eq!(resolved.exhaustion, reason, "end reason: {context}");
3703                assert_eq!(
3704                    key(resolved.end_scan_position),
3705                    end,
3706                    "end scan position: {context}"
3707                );
3708                assert_eq!(
3709                    resolved.natural_end_claim(options),
3710                    Some(claim),
3711                    "checkpoint claim: {context}"
3712                );
3713            }
3714            None => assert!(
3715                matches!(resolved.exhaustion, RangeExhaustion::CursorBound { .. }),
3716                "end reason: {context}: {:?}",
3717                resolved.exhaustion
3718            ),
3719        }
3720    }
3721
3722    #[test]
3723    fn transaction_cursors_admit_their_positions_in_either_direction() {
3724        let cursors = [every_tx_cursor(0..=first_tx(TIP)), past_tip_tx_cursors()].concat();
3725        let pair_cursors = [every_tx_cursor(edge_txs()), past_tip_tx_cursors()].concat();
3726        let positions = ledger_txs();
3727        for (window, options) in requests(&cursors, &pair_cursors) {
3728            check_request(window, &options, resolve_tx_request, &positions, |tx| {
3729                (tx, 0)
3730            });
3731        }
3732    }
3733
3734    #[test]
3735    fn event_cursors_admit_their_positions_in_either_direction() {
3736        let cursors = [
3737            every_event_cursor(0..=first_tx(TIP)),
3738            past_tip_event_cursors(),
3739        ]
3740        .concat();
3741        let pair_cursors = [
3742            every_event_cursor(event_edge_txs()),
3743            past_tip_event_cursors(),
3744        ]
3745        .concat();
3746        let positions = ledger_event_slots();
3747        for (window, options) in requests(&cursors, &pair_cursors) {
3748            check_request(
3749                window,
3750                &options,
3751                resolve_event_request,
3752                &positions,
3753                |position| (position.tx_seq, position.index),
3754            );
3755        }
3756    }
3757
3758    /// The cursor a resolved request's terminal frame carries.
3759    fn terminal_cursor<P: ScanPosition>(
3760        resolved: &ResolvedScan<P>,
3761        options: &QueryOptions,
3762        position_at: impl Fn(P, LedgerPoint) -> Position,
3763    ) -> CursorToken
3764    where
3765        CursorToken: ScanCursor<P>,
3766    {
3767        let kind = match resolved.exhaustion {
3768            RangeExhaustion::CursorBound { kind } => kind,
3769            RangeExhaustion::LedgerTip
3770            | RangeExhaustion::CheckpointBound
3771            | RangeExhaustion::ServingFloor { .. } => CursorKind::Boundary,
3772        };
3773        CursorToken {
3774            kind,
3775            position: position_at(
3776                resolved.end_scan_position,
3777                resolved.end_cursor_public_position(options),
3778            ),
3779        }
3780    }
3781
3782    /// A request bounded only on its far side (`after` descending, `before` ascending) ends on a
3783    /// closing cursor. Sent back in the same ordering without the far bound, it resumes with
3784    /// exactly the window's positions the far bound excluded.
3785    fn check_closing_cursor<P: ScanPosition + std::fmt::Debug>(
3786        window: Window,
3787        options: &QueryOptions,
3788        resolve: impl Fn(Window, &QueryOptions) -> Result<ResolvedScan<P>, RpcError>,
3789        positions: &[P],
3790        key: impl Fn(P) -> (u64, u32),
3791        position_at: impl Fn(P, LedgerPoint) -> Position,
3792    ) where
3793        CursorToken: ScanCursor<P>,
3794    {
3795        let context = format!("window {window:?}, {options:?}");
3796        let resolved = resolve(window, options).unwrap();
3797        let closing = terminal_cursor(&resolved, options, position_at);
3798        let resume = if options.is_ascending() {
3799            options_with(options.ordering, Some(closing.clone()), None)
3800        } else {
3801            options_with(options.ordering, None, Some(closing.clone()))
3802        };
3803        let resumed = resolve(window, &resume)
3804            .unwrap_or_else(|e| panic!("{closing:?} resumes: {:?}: {context}", status(e)));
3805        let unbounded = options_with(options.ordering, None, None);
3806        let excluded: Vec<P> = positions
3807            .iter()
3808            .copied()
3809            .filter(|position| {
3810                admits(window, &unbounded, key(*position))
3811                    && !admits(window, options, key(*position))
3812            })
3813            .collect();
3814        let admitted: Vec<P> = positions
3815            .iter()
3816            .copied()
3817            .filter(|position| resumed.bounds.contains(*position))
3818            .collect();
3819        assert_eq!(admitted, excluded, "{closing:?} resumes: {context}");
3820    }
3821
3822    /// Requests bounded only on their far side by each of `cursors`.
3823    fn far_bounded_requests(cursors: &[CursorToken]) -> Vec<(Window, QueryOptions)> {
3824        let mut requests = Vec::new();
3825        for window in WINDOWS {
3826            for cursor in cursors {
3827                requests.push((
3828                    window,
3829                    options_with(Ordering::Descending, Some(cursor.clone()), None),
3830                ));
3831                requests.push((
3832                    window,
3833                    options_with(Ordering::Ascending, None, Some(cursor.clone())),
3834                ));
3835            }
3836        }
3837        requests
3838    }
3839
3840    #[test]
3841    fn transaction_closing_cursors_resume_without_their_far_bound() {
3842        let positions = ledger_txs();
3843        for (window, options) in far_bounded_requests(&every_tx_cursor(0..=first_tx(TIP))) {
3844            check_closing_cursor(
3845                window,
3846                &options,
3847                resolve_tx_request,
3848                &positions,
3849                |tx| (tx, 0),
3850                tx_position,
3851            );
3852        }
3853    }
3854
3855    #[test]
3856    fn event_closing_cursors_resume_without_their_far_bound() {
3857        let positions = ledger_event_slots();
3858        for (window, options) in far_bounded_requests(&every_event_cursor(0..=first_tx(TIP))) {
3859            check_closing_cursor(
3860                window,
3861                &options,
3862                resolve_event_request,
3863                &positions,
3864                |position| (position.tx_seq, position.index),
3865                |position, point| ev_position(position.tx_seq, position.index, point),
3866            );
3867        }
3868    }
3869
3870    /// A page its starting cursor leaves empty in a non-empty window, and that ends with the
3871    /// window's reason, closes on a cursor that resumes without the window exactly where the
3872    /// starting cursor does: it neither re-serves an `after` Item cursor's item nor falls back to
3873    /// the window's edge. (In a zero-width window the page closes at the window's edge.)
3874    fn check_empty_page_closing_cursor<P: ScanPosition + std::fmt::Debug>(
3875        window: Window,
3876        options: &QueryOptions,
3877        resolve: impl Fn(Window, &QueryOptions) -> Result<ResolvedScan<P>, RpcError>,
3878        positions: &[P],
3879        position_at: impl Fn(P, LedgerPoint) -> Position,
3880    ) where
3881        CursorToken: ScanCursor<P>,
3882    {
3883        let Ok(resolved) = resolve(window, options) else {
3884            return;
3885        };
3886        if !resolved.is_empty()
3887            || matches!(resolved.exhaustion, RangeExhaustion::CursorBound { .. })
3888        {
3889            return;
3890        }
3891        let context = format!("window {window:?}, {options:?}");
3892        let closing = terminal_cursor(&resolved, options, position_at);
3893        let resume = if options.is_ascending() {
3894            options_with(options.ordering, Some(closing.clone()), None)
3895        } else {
3896            options_with(options.ordering, None, Some(closing.clone()))
3897        };
3898        let admitted = |options: &QueryOptions| {
3899            resolve((None, None), options).map(|resolved| {
3900                positions
3901                    .iter()
3902                    .copied()
3903                    .filter(|position| resolved.bounds.contains(*position))
3904                    .collect::<Vec<P>>()
3905            })
3906        };
3907        match (admitted(options), admitted(&resume)) {
3908            (Ok(starting), Ok(resumed)) => {
3909                assert_eq!(resumed, starting, "{closing:?} resumes: {context}")
3910            }
3911            (Err(_), Err(_)) => {}
3912            (starting, resumed) => panic!(
3913                "{closing:?} resumes as {:?}, the starting cursor as {:?}: {context}",
3914                resumed.map_err(status),
3915                starting.map_err(status),
3916            ),
3917        }
3918    }
3919
3920    /// Requests that start from each of `cursors`: `after` ascending, `before` descending.
3921    fn starting_cursor_requests(cursors: &[CursorToken]) -> Vec<(Window, QueryOptions)> {
3922        let mut requests = Vec::new();
3923        for window in WINDOWS {
3924            for cursor in cursors {
3925                requests.push((
3926                    window,
3927                    options_with(Ordering::Ascending, Some(cursor.clone()), None),
3928                ));
3929                requests.push((
3930                    window,
3931                    options_with(Ordering::Descending, None, Some(cursor.clone())),
3932                ));
3933            }
3934        }
3935        requests
3936    }
3937
3938    #[test]
3939    fn transaction_empty_pages_close_where_their_starting_cursor_resumes() {
3940        let positions = ledger_txs();
3941        for (window, options) in starting_cursor_requests(&every_tx_cursor(0..=first_tx(TIP))) {
3942            check_empty_page_closing_cursor(
3943                window,
3944                &options,
3945                resolve_tx_request,
3946                &positions,
3947                tx_position,
3948            );
3949        }
3950    }
3951
3952    #[test]
3953    fn event_empty_pages_close_where_their_starting_cursor_resumes() {
3954        let positions = ledger_event_slots();
3955        for (window, options) in starting_cursor_requests(&every_event_cursor(0..=first_tx(TIP))) {
3956            check_empty_page_closing_cursor(
3957                window,
3958                &options,
3959                resolve_event_request,
3960                &positions,
3961                |position, point| ev_position(position.tx_seq, position.index, point),
3962            );
3963        }
3964    }
3965
3966    #[test]
3967    fn checkpoint_empty_pages_close_where_their_starting_cursor_resumes() {
3968        let positions: Vec<u64> = (0..TIP).collect();
3969        for (window, options) in starting_cursor_requests(&every_checkpoint_cursor()) {
3970            check_empty_page_closing_cursor(
3971                window,
3972                &options,
3973                resolve_checkpoint_request,
3974                &positions,
3975                |checkpoint, _| Position::Checkpoints { checkpoint },
3976            );
3977        }
3978    }
3979
3980    /// Regression: a descending scan bounded by `after: Item(X)` excludes X, so its closing
3981    /// cursor is the boundary at the position after X, at the public position after the item.
3982    /// Sent back as `before`, it resumes with X.
3983    #[test]
3984    fn descending_after_item_closes_at_the_next_position() {
3985        // Inside a checkpoint: transaction 12 of checkpoint 2 closes at the boundary at 13.
3986        let resolved =
3987            resolve_transactions(&after_options(Ordering::Descending, tx_item(12))).unwrap();
3988        assert_eq!(resolved.range(), 13..100);
3989        assert_eq!(
3990            (resolved.end_public_position, resolved.end_scan_position),
3991            (after_transaction_point(13), 13)
3992        );
3993        let resumed =
3994            resolve_transactions(&before_options(Ordering::Descending, tx_frontier(13))).unwrap();
3995        assert_eq!(resumed.range(), 0..13);
3996
3997        // Transaction 14 is the last of checkpoint 2: the next position starts checkpoint 3,
3998        // and the closing cursor's public position is the end of checkpoint 2. The boundary's
3999        // position bounds the resumed scan, so it still admits transaction 14.
4000        let resolved =
4001            resolve_transactions(&after_options(Ordering::Descending, tx_item(14))).unwrap();
4002        assert_eq!(resolved.range(), 15..100);
4003        assert_eq!(
4004            (resolved.end_public_position, resolved.end_scan_position),
4005            (after_transaction_point(15), 15)
4006        );
4007        let resumed =
4008            resolve_transactions(&before_options(Ordering::Descending, tx_frontier(15))).unwrap();
4009        assert_eq!(resumed.range(), 0..15);
4010        assert!(resumed.bounds.contains(14));
4011
4012        let resolved =
4013            resolve_events(&after_options(Ordering::Descending, ev_item(14, 1))).unwrap();
4014        assert_eq!(
4015            resolved.end_scan_position,
4016            IntraTxCoordinate {
4017                tx_seq: 14,
4018                index: 2
4019            }
4020        );
4021        let resolved =
4022            resolve_events(&after_options(Ordering::Descending, ev_item(14, u32::MAX))).unwrap();
4023        assert_eq!(
4024            resolved.end_scan_position,
4025            IntraTxCoordinate::start_of_tx(15)
4026        );
4027
4028        // No position follows the last one, so the closing cursor restates the item.
4029        let resolved = resolved_range(10..20)
4030            .apply_cursor_bounds(&after_options(Ordering::Descending, tx_item(u64::MAX)));
4031        assert_eq!(resolved.end_scan_position, u64::MAX);
4032        assert_eq!(
4033            resolved.exhaustion,
4034            RangeExhaustion::CursorBound {
4035                kind: CursorKind::Item
4036            }
4037        );
4038    }
4039
4040    /// An Item and a Boundary cursor at every checkpoint up to two past the tip.
4041    fn every_checkpoint_cursor() -> Vec<CursorToken> {
4042        (0..=TIP + 2)
4043            .flat_map(|checkpoint| {
4044                [
4045                    cp_item(checkpoint),
4046                    CursorToken::boundary(Position::Checkpoints { checkpoint }),
4047                ]
4048            })
4049            .collect()
4050    }
4051
4052    #[test]
4053    fn checkpoint_cursors_admit_their_positions_in_either_direction() {
4054        let cursors = every_checkpoint_cursor();
4055        let positions: Vec<u64> = (0..TIP).collect();
4056        for (window, options) in requests(&cursors, &cursors) {
4057            check_request(
4058                window,
4059                &options,
4060                resolve_checkpoint_request,
4061                &positions,
4062                |checkpoint| (first_tx(checkpoint), 0),
4063            );
4064        }
4065    }
4066
4067    /// Every request the model checks, plus each ordering with no cursor, in the model's windows
4068    /// and in a window that holds no checkpoint.
4069    fn terminal_requests(
4070        cursors: &[CursorToken],
4071        pair_cursors: &[CursorToken],
4072    ) -> Vec<(Window, QueryOptions)> {
4073        let windows = WINDOWS
4074            .into_iter()
4075            .chain(PAST_TIP_WINDOWS)
4076            .chain([(Some(6), Some(6))]);
4077        let mut requests = requests_in(windows.clone(), cursors, pair_cursors);
4078        for window in windows {
4079            for ordering in ORDERINGS {
4080                requests.push((window, options_with(ordering, None, None)));
4081            }
4082        }
4083        requests
4084    }
4085
4086    /// One request on the model ledger: its terminal frame's `cursor_position` splits the model's
4087    /// positions exactly where the page leaves them. Ascending, a position lies before it exactly
4088    /// when the request admits it (every admitted position was delivered by the time the page
4089    /// ends) or the request's start excludes it (the point never lies before the start: the
4090    /// window's start, or where its `after` cursor resumes). Descending, a position lies at or
4091    /// after it exactly when the request admits it or its end excludes it (the window's end, or
4092    /// its `before` cursor). A window that holds no checkpoint ignores the cursors, and is
4093    /// bounded by its fields alone.
4094    ///
4095    /// Every terminal is placed without a read, by a window edge or the public position of a
4096    /// request cursor, and its cursor carries the public position of its own scan position.
4097    fn check_terminal_ledger_position<P: ScanPosition + std::fmt::Debug>(
4098        window: Window,
4099        options: &QueryOptions,
4100        resolve: impl Fn(Window, &QueryOptions) -> Result<(ResolvedScan<P>, ScanWindow<P>), RpcError>,
4101        positions: &[P],
4102        key: impl Fn(P) -> (u64, u32),
4103        point: impl Fn(P) -> LedgerPoint,
4104    ) where
4105        CursorToken: ScanCursor<P>,
4106    {
4107        let context = format!("window {window:?}, {options:?}");
4108        // `check_request` covers the requests that fail.
4109        let Ok((resolved, scan_window)) = resolve(window, options) else {
4110            return;
4111        };
4112        let cursor_position = resolved.end_resume_position(&scan_window, options);
4113        let cursor_point = resolved.end_cursor_public_position(options);
4114
4115        // The terminal cursor's public position names its own scan position.
4116        let end_key = key(resolved.end_scan_position);
4117        for &position in positions {
4118            assert_eq!(
4119                point(position) < cursor_point,
4120                key(position) < end_key,
4121                "{position:?} against the cursor's {cursor_point:?}: {context}"
4122            );
4123        }
4124        let cursor_key = |cursor: &CursorToken| key(cursor.coordinate());
4125        let window_start = window.0.unwrap_or(0);
4126        let window_end = window.1.unwrap_or(TIP).min(TIP);
4127        let holds_no_checkpoint = window_start >= window_end;
4128        let start_excludes = |position: P| {
4129            key(position) < (first_tx(window_start), 0)
4130                || (!holds_no_checkpoint
4131                    && options
4132                        .after
4133                        .as_ref()
4134                        .is_some_and(|after| match after.kind {
4135                            CursorKind::Item => key(position) <= cursor_key(after),
4136                            CursorKind::Boundary => key(position) < cursor_key(after),
4137                        }))
4138        };
4139        let end_excludes = |position: P| {
4140            key(position) >= (first_tx(window_end), 0)
4141                || (!holds_no_checkpoint
4142                    && options
4143                        .before
4144                        .as_ref()
4145                        .is_some_and(|before| key(position) >= cursor_key(before)))
4146        };
4147        for &position in positions {
4148            let admitted = admits(window, options, key(position));
4149            let before_point = point(position) < cursor_position;
4150            if options.is_ascending() {
4151                assert_eq!(
4152                    before_point,
4153                    admitted || start_excludes(position),
4154                    "{position:?} against {cursor_position:?}: {context}"
4155                );
4156            } else {
4157                assert_eq!(
4158                    !before_point,
4159                    admitted || end_excludes(position),
4160                    "{position:?} against {cursor_position:?}: {context}"
4161                );
4162            }
4163        }
4164    }
4165
4166    #[test]
4167    fn transaction_terminal_ledger_position_splits_the_ledger_where_the_page_ends() {
4168        let cursors = [every_tx_cursor(0..=first_tx(TIP)), past_tip_tx_cursors()].concat();
4169        let pair_cursors = [every_tx_cursor(edge_txs()), past_tip_tx_cursors()].concat();
4170        let positions = ledger_txs();
4171        for (window, options) in terminal_requests(&cursors, &pair_cursors) {
4172            check_terminal_ledger_position(
4173                window,
4174                &options,
4175                resolve_tx_in_window,
4176                &positions,
4177                |tx| (tx, 0),
4178                |tx| model_point(tx, 0),
4179            );
4180        }
4181    }
4182
4183    #[test]
4184    fn event_terminal_ledger_position_splits_the_ledger_where_the_page_ends() {
4185        let cursors = [
4186            every_event_cursor(0..=first_tx(TIP)),
4187            past_tip_event_cursors(),
4188        ]
4189        .concat();
4190        let pair_cursors = [
4191            every_event_cursor(event_edge_txs()),
4192            past_tip_event_cursors(),
4193        ]
4194        .concat();
4195        let positions = ledger_event_slots();
4196        for (window, options) in terminal_requests(&cursors, &pair_cursors) {
4197            check_terminal_ledger_position(
4198                window,
4199                &options,
4200                resolve_event_in_window,
4201                &positions,
4202                |position| (position.tx_seq, position.index),
4203                |position| model_point(position.tx_seq, position.index),
4204            );
4205        }
4206    }
4207
4208    /// A checkpoint scan's terminal is its own point, including where an `after` cursor past the
4209    /// tip places it: a checkpoint cursor's checkpoint is exact.
4210    #[test]
4211    fn checkpoint_terminal_ledger_position_splits_the_ledger_where_the_page_ends() {
4212        let cursors = every_checkpoint_cursor();
4213        let positions: Vec<u64> = (0..TIP).collect();
4214        for (window, options) in terminal_requests(&cursors, &cursors) {
4215            check_terminal_ledger_position(
4216                window,
4217                &options,
4218                resolve_checkpoint_in_window,
4219                &positions,
4220                |checkpoint| (first_tx(checkpoint), 0),
4221                LedgerPoint::checkpoint_start,
4222            );
4223        }
4224    }
4225
4226    /// Past the tip, an ascending terminal echoes the request's start fields, whatever its
4227    /// cursors. With start fields inside the tip, an `after` cursor past it places the terminal
4228    /// where it resumes by the public position it carries, and its echo keeps the cursor's bytes.
4229    #[test]
4230    fn ascending_terminal_past_the_tip_echoes_the_requested_start() {
4231        let past_tip_point = LedgerPoint::checkpoint_start(TIP + 1);
4232        let past_tip_after = tx_boundary(first_tx(TIP + 1));
4233        for (after, cursor_point) in [
4234            (None, LedgerPoint::checkpoint_start(TIP)),
4235            (Some(past_tip_after.clone()), past_tip_point),
4236        ] {
4237            let options = options_with(Ordering::Ascending, after, None);
4238            let (resolved, window) = resolve_tx_in_window((Some(TIP + 3), None), &options).unwrap();
4239            assert_eq!(
4240                resolved.end_resume_position(&window, &options),
4241                LedgerPoint::checkpoint_start(TIP + 3)
4242            );
4243            assert_eq!(resolved.end_cursor_public_position(&options), cursor_point);
4244        }
4245
4246        let options = options_with(Ordering::Ascending, Some(past_tip_after.clone()), None);
4247        let (resolved, window) = resolve_tx_in_window((Some(3), None), &options).unwrap();
4248        assert_eq!(
4249            resolved.end_resume_position(&window, &options),
4250            past_tip_point
4251        );
4252        assert_eq!(
4253            resolved.end_cursor_public_position(&options),
4254            past_tip_point
4255        );
4256        let watermark = resolved
4257            .range_end(&window, &options, tx_position)
4258            .terminal()
4259            .into_watermark(None);
4260        assert_eq!(watermark.cursor, Some(past_tip_after.encode()));
4261        assert_eq!(
4262            watermark.cursor_position,
4263            Some(past_tip_point.to_ledger_position(&past_tip_after.position))
4264        );
4265
4266        // An Item cursor resumes right after its item.
4267        let past_tip_item = tx_item(first_tx(TIP));
4268        let options = options_with(Ordering::Ascending, Some(past_tip_item), None);
4269        let (resolved, window) = resolve_tx_in_window((Some(3), None), &options).unwrap();
4270        assert_eq!(
4271            resolved.end_resume_position(&window, &options),
4272            LedgerPoint::transaction(TIP, 1)
4273        );
4274        assert_eq!(
4275            resolved.end_cursor_public_position(&options),
4276            LedgerPoint::transaction(TIP, 1)
4277        );
4278    }
4279
4280    /// A descending scan that reaches the serving floor resumes at the floor checkpoint's start.
4281    #[test]
4282    fn serving_floor_terminal_is_the_floor_checkpoint_start() {
4283        let options = options_with(Ordering::Descending, None, None);
4284        let (mut resolved, window) = resolve_tx_in_window((None, None), &options).unwrap();
4285        resolved
4286            .apply_serving_floor(first_tx(4), 4, &options)
4287            .unwrap();
4288        assert_eq!(
4289            resolved.end_resume_position(&window, &options),
4290            LedgerPoint::checkpoint_start(4)
4291        );
4292    }
4293
4294    /// An ascending scan whose high end is the tip, with nothing left to scan, ends at the tip
4295    /// with `LedgerTip`, however its `after` cursor names the tip. A `before` cursor at the tip
4296    /// bounds the scan instead, and a descending scan ends at its `after` cursor.
4297    #[test]
4298    fn caught_up_ascending_scan_ends_with_ledger_tip() {
4299        let tip_tx = first_tx(TIP);
4300        let cursor_bound = RangeExhaustion::CursorBound {
4301            kind: CursorKind::Boundary,
4302        };
4303        // The `LedgerTip` terminal, an ascending frontier at the tip, and the last item, each
4304        // with the public position where it resumes.
4305        for (cursor, end_public_position) in [
4306            (tx_boundary(tip_tx), LedgerPoint::checkpoint_start(TIP)),
4307            (tx_frontier(tip_tx), after_transaction_point(tip_tx)),
4308            (tx_item(tip_tx - 1), after_transaction_point(tip_tx)),
4309        ] {
4310            for window in [(None, None), (Some(3), None), (Some(3), Some(TIP + 5))] {
4311                let options = after_options(Ordering::Ascending, cursor.clone());
4312                let resolved = resolve_tx_request(window, &options).unwrap();
4313                let context = format!("{cursor:?} {window:?}");
4314                assert!(resolved.is_empty(), "{context}");
4315                assert_eq!(resolved.exhaustion, RangeExhaustion::LedgerTip, "{context}");
4316                assert_eq!(
4317                    (resolved.end_public_position, resolved.end_scan_position),
4318                    (end_public_position, tip_tx),
4319                    "{context}"
4320                );
4321                assert_eq!(
4322                    resolved.entry_checkpoint,
4323                    window.0.unwrap_or(0),
4324                    "{context}"
4325                );
4326            }
4327
4328            let before = |position| {
4329                options_with(
4330                    Ordering::Ascending,
4331                    Some(cursor.clone()),
4332                    Some(tx_boundary(position)),
4333                )
4334            };
4335            assert_eq!(
4336                resolve_transactions(&before(tip_tx + 1))
4337                    .unwrap()
4338                    .exhaustion,
4339                RangeExhaustion::LedgerTip,
4340                "a `before` past the tip leaves the tip as the high end: {cursor:?}"
4341            );
4342            assert_eq!(
4343                resolve_transactions(&before(tip_tx)).unwrap().exhaustion,
4344                cursor_bound,
4345                "a `before` at the tip bounds the scan: {cursor:?}"
4346            );
4347        }
4348
4349        let events =
4350            resolve_events(&after_options(Ordering::Ascending, ev_boundary(tip_tx, 0))).unwrap();
4351        assert!(events.is_empty());
4352        assert_eq!(events.exhaustion, RangeExhaustion::LedgerTip);
4353        assert_eq!(
4354            events.end_scan_position,
4355            IntraTxCoordinate::start_of_tx(tip_tx)
4356        );
4357
4358        let descending =
4359            resolve_transactions(&after_options(Ordering::Descending, tx_boundary(tip_tx)))
4360                .unwrap();
4361        assert!(descending.is_empty());
4362        assert_eq!(descending.exhaustion, cursor_bound);
4363        assert_eq!(
4364            (descending.end_public_position, descending.end_scan_position),
4365            (LedgerPoint::checkpoint_start(TIP), tip_tx)
4366        );
4367    }
4368
4369    /// A descending frontier resumed descending claims coverage from the window's end: the
4370    /// cursor vouches for every position above it, so the scan's first item claims the
4371    /// checkpoint above the item's, though the scan never read that checkpoint.
4372    #[test]
4373    fn descending_resume_claims_what_its_cursor_vouches_for() {
4374        // Descending frontier at transaction 92, in checkpoint 18.
4375        let options = before_options(Ordering::Descending, tx_boundary(92));
4376        let resolved = resolve_transactions(&options).unwrap();
4377        assert_eq!(resolved.range(), 0..92);
4378        assert_eq!(resolved.entry_checkpoint, TIP - 1);
4379        assert_eq!(
4380            crate::ledger_history::watermark::advance_covered_bound_before_checkpoint(
4381                None,
4382                18,
4383                resolved.entry_checkpoint,
4384                &options
4385            ),
4386            Some(19),
4387            "the first item, in checkpoint 18, claims checkpoint 19"
4388        );
4389    }
4390
4391    /// Cursor positions, and the public positions cursors carry, at the numeric edges resolve
4392    /// without overflow.
4393    #[test]
4394    fn cursors_at_numeric_edges_resolve_without_overflow() {
4395        // A boundary at genesis admits every position.
4396        let resolved =
4397            resolve_transactions(&after_options(Ordering::Ascending, tx_boundary(0))).unwrap();
4398        assert_eq!(resolved.range(), 0..100);
4399        // A `before` at `u64::MAX` is past every window, so it narrows nothing.
4400        let resolved =
4401            resolve_transactions(&before_options(Ordering::Ascending, tx_boundary(u64::MAX)))
4402                .unwrap();
4403        assert_eq!(resolved.range(), 0..100);
4404        // An `after` at `u64::MAX` is past the tip, and past a window that ends below the tip.
4405        let options = after_options(Ordering::Descending, tx_boundary(u64::MAX));
4406        assert!(is_out_of_range(resolve_transactions(&options)));
4407        let resolved = resolve_tx_request((None, Some(10)), &options).unwrap();
4408        assert!(resolved.is_empty());
4409        // An ascending `after` Item at the last position admits nothing, so its page ends at it,
4410        // in a window with checkpoints or without.
4411        let options = after_options(Ordering::Ascending, tx_item(u64::MAX));
4412        for window in [(None, None), (Some(TIP + 1), None)] {
4413            let resolved = resolve_tx_request(window, &options).unwrap();
4414            assert!(resolved.is_empty(), "{window:?}");
4415            assert_eq!(
4416                (resolved.end_scan_position, resolved.exhaustion),
4417                (
4418                    u64::MAX,
4419                    RangeExhaustion::CursorBound {
4420                        kind: CursorKind::Item
4421                    }
4422                ),
4423                "{window:?}"
4424            );
4425        }
4426
4427        // An Item whose public position sits at every numeric edge resumes right after it, where
4428        // the point saturates rather than overflowing.
4429        let edge_point = LedgerPoint::transaction(u64::MAX, u64::MAX);
4430        let options = after_options(
4431            Ordering::Ascending,
4432            CursorToken::item(tx_position(u64::MAX - 1, edge_point)),
4433        );
4434        let (resolved, window) = resolve_tx_in_window((None, None), &options).unwrap();
4435        assert_eq!(resolved.end_cursor_public_position(&options), edge_point);
4436        assert_eq!(resolved.end_resume_position(&window, &options), edge_point);
4437
4438        let edge_point = LedgerPoint::event(u64::MAX, u64::MAX, u32::MAX);
4439        let options = after_options(
4440            Ordering::Ascending,
4441            CursorToken::item(ev_position(u64::MAX - 1, 0, edge_point)),
4442        );
4443        let (resolved, window) = resolve_event_in_window((None, None), &options).unwrap();
4444        assert_eq!(resolved.end_cursor_public_position(&options), edge_point);
4445        assert_eq!(resolved.end_resume_position(&window, &options), edge_point);
4446    }
4447}