Skip to main content

sui_rpc_api/ledger_history/
object_versions.rs

1// Copyright (c) Mysten Labs, Inc.
2// SPDX-License-Identifier: Apache-2.0
3
4use std::ops::RangeInclusive;
5
6use crate::AtCheckpointUpperBound;
7use crate::ErrorReason;
8use crate::Result;
9use crate::ledger_history::query_options::above_latest_available;
10use crate::ledger_history::query_options::below_serving_floor;
11use crate::ledger_history::query_options::validate_checkpoint_bounds;
12use crate::read_mask_defaults;
13use bytes::Bytes;
14use futures::StreamExt;
15use futures::stream::BoxStream;
16use sui_rpc::field::FieldMaskTree;
17use sui_rpc::proto::google::rpc::bad_request::FieldViolation;
18use sui_rpc::proto::sui::rpc::v2::ListObjectVersionsRequest;
19use sui_rpc::proto::sui::rpc::v2::ListObjectVersionsResponse;
20use sui_rpc::proto::sui::rpc::v2::Object;
21use sui_rpc::proto::sui::rpc::v2::ObjectRemoval;
22use sui_rpc::proto::sui::rpc::v2::Ordering;
23use sui_rpc::proto::sui::rpc::v2::QueryEnd;
24use sui_rpc::proto::sui::rpc::v2::QueryEndReason;
25use sui_rpc::proto::sui::rpc::v2::QueryOptions;
26use sui_rpc::proto::sui::rpc::v2::object_removal;
27use sui_sdk_types::Address;
28use sui_types::base_types::ObjectID;
29use sui_types::base_types::SequenceNumber;
30use sui_types::digests::TransactionDigest;
31use sui_types::object::OBJECT_START_VERSION;
32
33/// A stream of `ListObjectVersions` response frames.
34pub type ObjectVersionFrames = BoxStream<'static, Result<ListObjectVersionsResponse>>;
35
36/// A position in one object's version history, set as `ListObjectVersionsResponse.cursor`
37/// and accepted back as `options.after` and `options.before`. Public so other implementors of
38/// `LedgerService` mint and accept the same cursors. BCS-encoded as an enum so that a listing in
39/// another order can add a variant without changing the encoding of existing cursors.
40#[derive(Clone, Copy, Debug, Eq, PartialEq, serde::Serialize, serde::Deserialize)]
41pub enum ObjectVersionCursor {
42    /// The item at `version` of the object `object_id`, live or a removal, minted by a listing
43    /// bounded by `bounding_checkpoint` (see [`CheckpointWindow::bounding_checkpoint`]). The
44    /// client holds the item, so as `after` it lists the versions above `version`, and as
45    /// `before` those below it. A server that has indexed less than `bounding_checkpoint` can
46    /// tell from it that the cursor comes from a server further ahead, even when the object
47    /// leaves it nothing to compare `version` with.
48    Version {
49        object_id: ObjectID,
50        version: u64,
51        bounding_checkpoint: u64,
52    },
53    /// The position between `version` and the version after it, which names no item, minted at
54    /// the edge of its window by a listing bounded by `bounding_checkpoint` (see
55    /// [`ObjectVersionsQuery::end_cursor`]). As `after` it lists the versions above `version`,
56    /// and as `before` those at or below it, so its two sides hold every version, including
57    /// versions written after the listing that minted it: resuming from it in either order
58    /// neither skips nor repeats one. Object versions start at [`OBJECT_START_VERSION`], so the
59    /// boundary at version 0 lies below every version.
60    Boundary {
61        object_id: ObjectID,
62        version: u64,
63        bounding_checkpoint: u64,
64    },
65}
66
67impl ObjectVersionCursor {
68    pub fn encode(&self) -> Bytes {
69        bcs::to_bytes(self).unwrap().into()
70    }
71}
72
73/// A cursor a request carries, decoded. A listing that ends at it hands it back as it came (see
74/// [`ObjectVersionsQuery::end_cursor`]).
75#[derive(Clone, Copy, Debug)]
76struct RequestCursor {
77    /// The version it names: an item's, or the one below a boundary.
78    version: u64,
79    /// The checkpoint that bounded the listing that minted it.
80    bounding_checkpoint: u64,
81    /// Whether it is an [`ObjectVersionCursor::Boundary`] rather than an item's cursor.
82    boundary: bool,
83}
84
85impl RequestCursor {
86    /// The version above those this cursor lists as `before`: an item's own version, or the
87    /// version after a boundary. As `after`, either kind lists the versions above `version`.
88    fn end_before(&self) -> u64 {
89        if self.boundary {
90            self.version.saturating_add(1)
91        } else {
92            self.version
93        }
94    }
95}
96
97/// What a `ListObjectVersions` request lists: the object, the fields to render, the order, the
98/// limit, and the bounds the request sets. Public so other implementors of `LedgerService` parse
99/// requests, bound listings, end them, and mint cursors the same way.
100#[derive(Clone, Debug)]
101pub struct ObjectVersionsQuery {
102    pub object_id: ObjectID,
103    /// The fields of each listed live version to render.
104    pub read_mask: FieldMaskTree,
105    /// The fields of each listed removal to render.
106    pub removal_read_mask: FieldMaskTree,
107    /// `start_checkpoint`: list only the versions written in this checkpoint or later.
108    pub start_checkpoint: Option<u64>,
109    /// `end_checkpoint`: list only the versions written before this checkpoint.
110    pub end_checkpoint: Option<u64>,
111    /// Whether to list versions from highest to lowest.
112    pub descending: bool,
113    /// The most items, live versions and removals, one stream lists.
114    pub limit: usize,
115    /// `start_version`, the lowest version to list.
116    start_version: Option<u64>,
117    /// `end_version`, the version above the highest to list.
118    end_version: Option<u64>,
119    /// The `options.after` cursor.
120    after: Option<RequestCursor>,
121    /// The `options.before` cursor.
122    before: Option<RequestCursor>,
123}
124
125/// The checkpoints a listing covers, resolved against the highest checkpoint the server has
126/// indexed (see [`ObjectVersionsQuery::checkpoint_window`]).
127#[derive(Clone, Copy, Debug, Eq, PartialEq)]
128pub struct CheckpointWindow {
129    /// The checkpoint that bounds the listing, which its cursors record: `end_checkpoint - 1`
130    /// when `end_checkpoint` is set and that checkpoint is indexed, else the highest indexed
131    /// checkpoint. The listing reads the versions written by the end of it.
132    pub bounding_checkpoint: u64,
133    /// `start_checkpoint - 1`, capped at [`Self::bounding_checkpoint`]: the listing starts above
134    /// the object's version at the end of it. `None` when `start_checkpoint` is unset or 0, and
135    /// the listing starts at version 0.
136    pub below_start: Option<u64>,
137    /// Whether the listing runs to the indexed tip: `end_checkpoint` is unset, or above the
138    /// checkpoint after the highest indexed one, or, ascending, `start_checkpoint` is at or above
139    /// that checkpoint.
140    reaches_tip: bool,
141    /// Whether the checkpoint range is empty: `end_checkpoint` is at or below
142    /// `start_checkpoint`.
143    empty: bool,
144}
145
146impl CheckpointWindow {
147    /// Whether the checkpoint range is empty, so the listing lists nothing and reads no version
148    /// at its checkpoints.
149    pub fn is_empty(&self) -> bool {
150        self.empty
151    }
152}
153
154/// The versions a listing reads, and how it ends once it has listed all of them below its limit.
155#[derive(Clone, Debug, Eq, PartialEq)]
156pub struct ObjectVersionsPlan {
157    /// The versions to read, as one inclusive range. `None` if no version is left to list.
158    pub versions: Option<RangeInclusive<SequenceNumber>>,
159    /// The reason for the final frame of a listing that lists every item in [`Self::versions`]
160    /// without reaching the limit.
161    pub end: QueryEndReason,
162    /// The window's edges, after the cursors: it lists the versions at or above `low` and below
163    /// `high`.
164    low: u64,
165    high: u64,
166}
167
168/// One item of a listing, as a backend reads it, for [`ObjectVersionsQuery::frames`] to send.
169#[derive(Clone, Debug)]
170#[allow(
171    clippy::large_enum_variant,
172    reason = "most items are live versions, each moved once into its frame; boxing them would \
173              add an allocation per item to spare the rare removal"
174)]
175pub enum ObjectVersionItem {
176    /// A live version, rendered with [`ObjectVersionsQuery::read_mask`]. `version` is the version
177    /// it was rendered from, since the mask may leave `object.version` unset.
178    Live {
179        object: Object,
180        version: SequenceNumber,
181    },
182    /// A version at which the object was deleted or wrapped.
183    Removal {
184        version: SequenceNumber,
185        kind: ObjectRemovalKind,
186        /// The transaction that deleted or wrapped the object: set whenever
187        /// [`ObjectVersionsQuery::lists_removal_transactions`], `None` otherwise.
188        transaction: Option<TransactionDigest>,
189    },
190}
191
192impl ObjectVersionItem {
193    /// The version this item is at, which its cursor names.
194    pub fn version(&self) -> SequenceNumber {
195        match self {
196            Self::Live { version, .. } | Self::Removal { version, .. } => *version,
197        }
198    }
199}
200
201/// How an object was removed from the live set at a version.
202#[derive(Clone, Copy, Debug, Eq, PartialEq)]
203pub enum ObjectRemovalKind {
204    /// Deleted, including unwrapped and deleted by the same transaction. An object ID can be
205    /// used again at a higher version, as when a dynamic field is removed and re-added under the
206    /// same name, so a deletion need not be the object's last version.
207    Deleted,
208    /// Wrapped in another object; it can be unwrapped at a higher version.
209    Wrapped,
210}
211
212impl From<ObjectRemovalKind> for object_removal::Kind {
213    fn from(kind: ObjectRemovalKind) -> Self {
214        match kind {
215            ObjectRemovalKind::Deleted => Self::Deleted,
216            ObjectRemovalKind::Wrapped => Self::Wrapped,
217        }
218    }
219}
220
221impl ObjectVersionsQuery {
222    /// Parse and validate `request`, with `options.limit` defaulting to `default_limit` and
223    /// coerced into `1..=max_limit`. A malformed cursor, one for another object, an
224    /// `end_version` below `start_version`, or an `end_checkpoint` below `start_checkpoint` is
225    /// `INVALID_ARGUMENT`.
226    pub fn new(
227        request: &ListObjectVersionsRequest,
228        default_limit: u32,
229        max_limit: u32,
230    ) -> Result<Self> {
231        let object_id = request
232            .object_id
233            .as_ref()
234            .ok_or_else(|| {
235                FieldViolation::new("object_id")
236                    .with_description("missing object_id")
237                    .with_reason(ErrorReason::FieldMissing)
238            })?
239            .parse::<Address>()
240            .map_err(|e| {
241                FieldViolation::new("object_id")
242                    .with_description(format!("invalid object_id: {e}"))
243                    .with_reason(ErrorReason::FieldInvalid)
244            })?
245            .into();
246
247        let read_mask = read_mask_defaults::validate_read_mask::<Object>(
248            request.read_mask.clone(),
249            read_mask_defaults::OBJECT,
250        )?;
251        let removal_read_mask = read_mask_defaults::validate_field_mask::<ObjectRemoval>(
252            "removal_read_mask",
253            request.removal_read_mask.clone(),
254            read_mask_defaults::OBJECT_REMOVAL,
255        )?;
256
257        let options = request.options.as_ref();
258        let after = options
259            .and_then(|options| options.after.as_ref())
260            .map(|after| request_cursor("options.after", after, object_id))
261            .transpose()?;
262        let before = options
263            .and_then(|options| options.before.as_ref())
264            .map(|before| request_cursor("options.before", before, object_id))
265            .transpose()?;
266        if let (Some(start), Some(end)) = (request.start_version, request.end_version)
267            && end < start
268        {
269            return Err(FieldViolation::new("end_version")
270                .with_description("end_version must be greater than or equal to start_version")
271                .with_reason(ErrorReason::FieldInvalid)
272                .into());
273        }
274        validate_checkpoint_bounds(request.start_checkpoint, request.end_checkpoint)?;
275
276        Ok(Self {
277            object_id,
278            read_mask,
279            removal_read_mask,
280            start_checkpoint: request.start_checkpoint,
281            end_checkpoint: request.end_checkpoint,
282            descending: descending(options)?,
283            limit: options
284                .and_then(|options| options.limit)
285                .unwrap_or(default_limit)
286                .clamp(1, max_limit) as usize,
287            start_version: request.start_version,
288            end_version: request.end_version,
289            after,
290            before,
291        })
292    }
293
294    /// Whether [`Self::removal_read_mask`] selects each removal's `transaction`. A backend that
295    /// lists removals sets [`ObjectVersionItem::Removal`]'s `transaction` exactly when it does,
296    /// failing the listing when it cannot.
297    pub fn lists_removal_transactions(&self) -> bool {
298        self.removal_read_mask
299            .contains(ObjectRemoval::TRANSACTION_FIELD.name)
300    }
301
302    /// Whether the request carries an `after` cursor whose client holds history right below the
303    /// versions the listing lists that pruning through `floor_checkpoint` may have cut a gap
304    /// after: an item's cursor, whose item the client holds, or a boundary from a listing bounded
305    /// by a checkpoint K below the floor, so that the lowest `start_checkpoint` the server
306    /// accepts, the floor + 1, is above K + 1. This checkpoint rule is complete only for the
307    /// boundary at version 0, below every version: its client holds what was written by the end
308    /// of K, and pruning keeps every version written after the floor. A boundary above version 0
309    /// can sit at an `end_version` cut and vouches for nothing above it (see
310    /// [`Self::needs_history_retained_from`]); the nothing-retained path and the
311    /// low-`start_checkpoint` gate apply the checkpoint rule to it as ruled. With nothing pruned
312    /// (`floor_checkpoint` unset), no boundary is held.
313    pub fn has_held_after_cursor(&self, floor_checkpoint: Option<u64>) -> bool {
314        self.after.as_ref().is_some_and(|after| {
315            !after.boundary
316                || floor_checkpoint.is_some_and(|floor| floor > after.bounding_checkpoint)
317        })
318    }
319
320    /// Whether the listing's lowest version, `start`, is the one right after its `after` cursor,
321    /// of either kind.
322    pub fn starts_after_cursor(&self, start: SequenceNumber) -> bool {
323        self.after
324            .as_ref()
325            .is_some_and(|after| after.version.checked_add(1) == Some(start.value()))
326    }
327
328    /// Whether a server whose listing floor is `floor_checkpoint` must find the object's history
329    /// retained from `start`, the listing's lowest version, so as not to follow the history its
330    /// client holds with a gap: the listing starts right after its `after` cursor (see
331    /// [`Self::starts_after_cursor`]), which is an item's cursor, a boundary that pruning through
332    /// the floor passed (see [`Self::has_held_after_cursor`]), or a boundary above version 0.
333    /// Such a boundary can sit at an `end_version` cut, below versions written by its checkpoint,
334    /// so it vouches for nothing above it: the history from `start` is retained only when the
335    /// object's version at the floor is at most one above the boundary's version, as it is for a
336    /// boundary minted at the top of its window bounded at or above the floor. The boundary at
337    /// version 0, below every version, keeps the checkpoint rule.
338    pub fn needs_history_retained_from(
339        &self,
340        start: SequenceNumber,
341        floor_checkpoint: Option<u64>,
342    ) -> bool {
343        self.starts_after_cursor(start)
344            && (self.has_held_after_cursor(floor_checkpoint)
345                || self.after.is_some_and(|after| after.version > 0))
346    }
347
348    /// Whether the request's `after` cursor is at or above `version`, the object's version at the
349    /// end of some checkpoint, so that every version the listing lists was written after that
350    /// checkpoint. `false` without an `after` cursor or a `version`.
351    pub fn after_at_or_above(&self, version: Option<SequenceNumber>) -> bool {
352        self.after
353            .as_ref()
354            .zip(version)
355            .is_some_and(|(after, version)| after.version >= version.value())
356    }
357
358    /// Fails with `OUT_OF_RANGE` / `ABOVE_LATEST_AVAILABLE` ([`AtCheckpointUpperBound::check_cursor`],
359    /// naming the lowest of their checkpoints) when the listing runs to the tip (`end_checkpoint`
360    /// unset, or above the checkpoint after the tip) and the request has cursors, all from
361    /// listings bounded by a checkpoint above `upper_bound`'s highest indexed one: from servers
362    /// that have indexed further than this one. A cursor from a listing bounded at or below it
363    /// names a version this server has indexed.
364    pub fn check_some_cursor_indexed(
365        &self,
366        window: &CheckpointWindow,
367        upper_bound: &AtCheckpointUpperBound,
368    ) -> Result<()> {
369        let lowest = [&self.after, &self.before]
370            .into_iter()
371            .flatten()
372            .map(|cursor| cursor.bounding_checkpoint)
373            .min();
374        match lowest {
375            Some(lowest) if window.reaches_tip => upper_bound.check_cursor(lowest),
376            _ => Ok(()),
377        }
378    }
379
380    /// The error for a request a server whose listing floor is `floor_checkpoint` cannot serve
381    /// because pruning took history it would list: `OUT_OF_RANGE` / `BELOW_EARLIEST_AVAILABLE`
382    /// ([`below_serving_floor`]), reporting `floor_checkpoint + 1`, the lowest `start_checkpoint`
383    /// it accepts, as `lowestAvailableCheckpoint`. A request whose `after` cursor comes from a
384    /// listing bounded above `upper_bound`'s highest indexed checkpoint, by a server that has
385    /// indexed further, gets that cursor's `ABOVE_LATEST_AVAILABLE`
386    /// ([`AtCheckpointUpperBound::check_cursor`]) instead, which it can retry once this server
387    /// catches up: `ListTransactions`' `floor_error_or` puts the tip refusal of a request with
388    /// an `after` cursor before the floor rules.
389    pub fn floor_error(
390        &self,
391        floor_checkpoint: u64,
392        upper_bound: &AtCheckpointUpperBound,
393    ) -> crate::RpcError {
394        self.after
395            .as_ref()
396            .and_then(|after| upper_bound.check_cursor(after.bounding_checkpoint).err())
397            .unwrap_or_else(|| below_serving_floor(floor_checkpoint.saturating_add(1)))
398    }
399
400    /// Fails with [`Self::floor_error`] when a server whose listing floor is `floor_checkpoint`
401    /// cannot serve the request's checkpoint range, as `ListTransactions` refuses one below its
402    /// floor. The lowest `start_checkpoint` it accepts is the checkpoint after the floor, since a
403    /// range starts above the object's version at the end of the checkpoint before it. A lower
404    /// `start_checkpoint` is served only when an `after` cursor bounds the listing at or above
405    /// the floor, as `ListTransactions` checks the start only after the cursors narrow it: the
406    /// cursor is at or above `version_at_floor(floor_checkpoint)`, the object's version at the
407    /// end of the floor checkpoint, so every version after it was written after the floor, or
408    /// the object has no version there. A pruned server cannot tell whether an object without
409    /// one did not exist yet or was removed at or before the floor, so it must also find the
410    /// object's history retained from the listing's lowest version on. An `end_checkpoint` at or
411    /// below that lowest start is refused when the listing has no lower bound of its own
412    /// (neither `start_checkpoint` nor an `after` cursor). An empty range lists nothing,
413    /// whatever the floor. With nothing pruned (`floor_checkpoint` unset), every range is served.
414    pub fn check_checkpoint_floor(
415        &self,
416        floor_checkpoint: Option<u64>,
417        upper_bound: &AtCheckpointUpperBound,
418        version_at_floor: impl FnOnce(u64) -> Result<Option<SequenceNumber>>,
419    ) -> Result<()> {
420        let Some(floor_checkpoint) = floor_checkpoint else {
421            return Ok(());
422        };
423        let start = self.start_checkpoint.unwrap_or(0);
424        if self.end_checkpoint.is_some_and(|end| end <= start) {
425            return Ok(());
426        }
427        let lowest_start = floor_checkpoint.saturating_add(1);
428        let start_below = match self.start_checkpoint {
429            Some(start) if start < lowest_start => match &self.after {
430                Some(after) => version_at_floor(floor_checkpoint)?
431                    .is_some_and(|at_floor| after.version < at_floor.value()),
432                None => true,
433            },
434            _ => false,
435        };
436        let end_below = self.start_checkpoint.is_none()
437            && self.after.is_none()
438            && self.end_checkpoint.is_some_and(|end| end <= lowest_start);
439        if start_below || end_below {
440            return Err(self.floor_error(floor_checkpoint, upper_bound));
441        }
442        Ok(())
443    }
444
445    /// The plan of a listing for an object of which a pruning server retains nothing up to the
446    /// bounding checkpoint: it lists nothing and ends as at the object's first version, with
447    /// `CHECKPOINT_BOUND`.
448    pub fn nothing_retained(&self) -> ObjectVersionsPlan {
449        ObjectVersionsPlan {
450            versions: None,
451            end: QueryEndReason::CheckpointBound,
452            low: 0,
453            high: 0,
454        }
455    }
456
457    /// The checkpoints the listing covers, against `upper_bound`'s highest indexed checkpoint,
458    /// the tip, as `ListTransactions` bounds them. A descending listing whose `end_checkpoint` is
459    /// above the checkpoint after the tip, or whose `start_checkpoint` is above the tip with
460    /// `end_checkpoint` unset, is `OUT_OF_RANGE` / `ABOVE_LATEST_AVAILABLE` (bound
461    /// `end_checkpoint` or `start_checkpoint`): it would start above versions this server has
462    /// not indexed. An ascending listing is never refused for its range: it runs through the tip
463    /// and ends with `LEDGER_TIP`.
464    pub fn checkpoint_window(
465        &self,
466        upper_bound: &AtCheckpointUpperBound,
467    ) -> Result<CheckpointWindow> {
468        let first_unavailable = upper_bound.highest_indexed().saturating_add(1);
469        if self.descending {
470            let past_tip = match self.end_checkpoint {
471                Some(end) if end > first_unavailable => Some(("end_checkpoint", end)),
472                Some(_) => None,
473                None => self
474                    .start_checkpoint
475                    .filter(|start| *start >= first_unavailable)
476                    .map(|start| ("start_checkpoint", start)),
477            };
478            if let Some((field, requested)) = past_tip {
479                return Err(above_latest_available(field, requested, first_unavailable));
480            }
481        }
482        let indexed_end = self.end_checkpoint.filter(|end| *end <= first_unavailable);
483        let bounding_checkpoint =
484            indexed_end.map_or(upper_bound.highest_indexed(), |end| end.saturating_sub(1));
485        Ok(CheckpointWindow {
486            bounding_checkpoint,
487            below_start: self
488                .start_checkpoint
489                .and_then(|start| start.checked_sub(1))
490                .map(|below| below.min(bounding_checkpoint)),
491            // An ascending range that starts above the tip ends there, even an empty one, as
492            // `ListTransactions` ends it.
493            reaches_tip: indexed_end.is_none()
494                || (!self.descending
495                    && self
496                        .start_checkpoint
497                        .is_some_and(|start| start >= first_unavailable)),
498            empty: self
499                .end_checkpoint
500                .is_some_and(|end| end <= self.start_checkpoint.unwrap_or(0)),
501        })
502    }
503
504    /// What the listing reads and how it ends, given `newest_visible`, the object's version at
505    /// the end of [`CheckpointWindow::bounding_checkpoint`], live or not (the newest version
506    /// written by then), or `None` if the object did not exist yet, and `newest_before_start`,
507    /// its version at the end of [`CheckpointWindow::below_start`] (`None` when that is unset).
508    /// The checkpoint range lists the versions above `newest_before_start` up to
509    /// `newest_visible`: an object's versions only increase from checkpoint to checkpoint, so
510    /// the versions written in a checkpoint range are one version range. The cursors narrow it
511    /// to the versions between their positions (see [`ObjectVersionCursor`]).
512    ///
513    /// A cursor comes from a listing on any server, such as another replica that has indexed
514    /// further, so it can name a version past this server's tip: above `newest_visible`, or at or
515    /// above [`OBJECT_START_VERSION`] if it is `None`. When the window runs to the tip
516    /// (`end_checkpoint` unset, or above the checkpoint after the tip), the ledger List APIs'
517    /// rules apply to such a cursor:
518    /// - Descending, it is [`AtCheckpointUpperBound::unindexed_cursor_error`], whatever the
519    ///   version range: listing from this server's view would start below versions it lacks. A
520    ///   `before` at the version right after `newest_visible` leaves none between them, so it is
521    ///   served. With `newest_visible` `None`, that version is [`OBJECT_START_VERSION`], the
522    ///   first an object can have, so the boundary at version 0, which a listing of the object
523    ///   that lists nothing mints, is served back as either cursor, unless every cursor of the
524    ///   request comes from a listing bounded above the tip (see
525    ///   [`Self::check_some_cursor_indexed`]).
526    /// - Ascending, the listing is served from this server's view, which holds nothing above
527    ///   the tip. If its window reaches past the tip (see `LEDGER_TIP` below), an `after` past
528    ///   the tip lists nothing and ends with `LEDGER_TIP`, where the client resumes from the
529    ///   cursor it holds, with `CURSOR_BOUND` if `before` is at or below the version after
530    ///   `after`, leaving nothing between them, or with `CHECKPOINT_BOUND` if `end_version` is.
531    ///   A window that ends at or below the tip ends by the rules below. A `before` past the tip
532    ///   leaves the tip as the listing's end.
533    ///
534    /// A listing with an indexed `end_checkpoint` stops at it, so every cursor is safe to page
535    /// from. An empty checkpoint range lists nothing. It ends with `CHECKPOINT_BOUND` when
536    /// `end_checkpoint - 1` is indexed; ascending above the tip, it ends with `LEDGER_TIP`, as
537    /// `ListTransactions` does.
538    ///
539    /// The listing ends where its range does, at the bound the ledger List APIs would name:
540    /// - The far cursor in listing order ends it with `CURSOR_BOUND` when the version it names
541    ///   is inside the request's window (`start_version`, `end_version` and the versions written
542    ///   in the checkpoint range) or at its edge: `before` at or below the window's end
543    ///   ascending, `after` at or above its start descending.
544    /// - Otherwise an ascending listing whose window runs to the tip and reaches past the
545    ///   object's newest version (`end_version` unset, or above both the version after it and
546    ///   `start_version`) ends with `LEDGER_TIP`, since versions written later extend it, even
547    ///   when its `after` cursor leaves nothing to list: a client following an object's new
548    ///   versions resumes from its newest version's cursor.
549    /// - Every other listing ends at the edge of the window the request set, with
550    ///   `CHECKPOINT_BOUND`, including one whose starting cursor (`after` ascending, `before`
551    ///   descending) sits at or past that edge.
552    pub fn plan(
553        &self,
554        window: &CheckpointWindow,
555        upper_bound: &AtCheckpointUpperBound,
556        newest_visible: Option<SequenceNumber>,
557        newest_before_start: Option<SequenceNumber>,
558    ) -> Result<ObjectVersionsPlan> {
559        // Exclusive ends throughout: the version after the newest visible one bounds the window.
560        // An empty checkpoint range reads neither version, so its window is empty too.
561        let visible_end = newest_visible.map_or(0, |newest| newest.value().saturating_add(1));
562        let checkpoints_start =
563            newest_before_start.map_or(0, |newest| newest.value().saturating_add(1));
564        let after = self.after.as_ref().map(|after| after.version);
565        let before = self.before.as_ref().map(RequestCursor::end_before);
566        // `lowest_missing` is the lowest version a server further ahead may hold that this one
567        // lacks: the one after the newest visible version, or, without one, the first version an
568        // object can have. A `before` at it leaves no such version between it and the listing.
569        // Without a visible version, the boundary at version 0 lies below it, so only the
570        // cursors' checkpoints can show that they come from further ahead.
571        if window.reaches_tip && self.descending {
572            if newest_visible.is_none() {
573                self.check_some_cursor_indexed(window, upper_bound)?;
574            }
575            let lowest_missing = newest_visible.map_or(OBJECT_START_VERSION.value(), |newest| {
576                newest.value().saturating_add(1)
577            });
578            if after.is_some_and(|after| after >= lowest_missing)
579                || before.is_some_and(|before| before > lowest_missing)
580            {
581                return Err(upper_bound.unindexed_cursor_error());
582            }
583        }
584        let reaches_tip = window.reaches_tip
585            && self
586                .end_version
587                .is_none_or(|end| end > visible_end && end > self.start_version.unwrap_or(0));
588        if reaches_tip
589            && !self.descending
590            && let Some(after) = after.filter(|&after| after >= visible_end)
591        {
592            let resume = after.saturating_add(1);
593            // The far cursor ends the listing when it is at least as tight as `end_version`.
594            let end = if before.is_some_and(|before| {
595                before <= resume && self.end_version.is_none_or(|end| before <= end)
596            }) {
597                QueryEndReason::CursorBound
598            } else if self.end_version.is_some_and(|end| end <= resume) {
599                QueryEndReason::CheckpointBound
600            } else {
601                QueryEndReason::LedgerTip
602            };
603            return Ok(ObjectVersionsPlan {
604                versions: None,
605                end,
606                low: resume,
607                high: visible_end,
608            });
609        }
610        let mut end = if reaches_tip && !self.descending {
611            QueryEndReason::LedgerTip
612        } else {
613            QueryEndReason::CheckpointBound
614        };
615        let mut low = self
616            .start_version
617            .map_or(checkpoints_start, |start| start.max(checkpoints_start));
618        let mut high = self
619            .end_version
620            .map_or(visible_end, |end| end.min(visible_end));
621        if low < high {
622            if let Some(after) = after
623                && after >= low
624            {
625                low = after.saturating_add(1);
626                if self.descending {
627                    end = QueryEndReason::CursorBound;
628                }
629            }
630            if let Some(before) = before
631                && before <= high
632            {
633                high = before;
634                if !self.descending {
635                    end = QueryEndReason::CursorBound;
636                }
637            }
638        }
639
640        Ok(ObjectVersionsPlan {
641            versions: (low < high)
642                .then(|| SequenceNumber::from_u64(low)..=SequenceNumber::from_u64(high - 1)),
643            end,
644            low,
645            high,
646        })
647    }
648
649    /// The cursor the last frame of a listing that `plan` plans resumes from, when the listing
650    /// ends with its planned reason, bounded by `bounding_checkpoint`: a request in the same
651    /// order resumes from it.
652    /// - `CURSOR_BOUND`: the far cursor (`before` ascending, `after` descending), unchanged.
653    /// - The starting cursor (`after` ascending, `before` descending), unchanged, when it sits at
654    ///   or past the window's edge, so the listing reached nothing. That includes an ascending
655    ///   `after` past the tip.
656    /// - Otherwise the window's edge, which is what the listing reached, as an
657    ///   [`ObjectVersionCursor::Boundary`]: ascending, the boundary below the window's end, above
658    ///   which `after` lists what the window left; descending, the boundary below the window's
659    ///   lowest version, at or below which `before` lists, or above `newest_visible` when the
660    ///   window lies wholly above it. Versions written later land on the far side of the
661    ///   boundary from what the listing reached, whichever order resumes from it.
662    pub fn end_cursor(&self, plan: &ObjectVersionsPlan, bounding_checkpoint: u64) -> Bytes {
663        let (far, starting) = if self.descending {
664            (&self.after, &self.before)
665        } else {
666            (&self.before, &self.after)
667        };
668        if plan.end == QueryEndReason::CursorBound
669            && let Some(far) = far
670        {
671            return self.echo(far);
672        }
673        let reached_nothing = (*starting).filter(|starting| {
674            if self.descending {
675                starting.end_before() <= plan.low
676            } else {
677                starting.version.saturating_add(1) >= plan.high
678            }
679        });
680        if let Some(starting) = reached_nothing {
681            return self.echo(&starting);
682        }
683        // A descending window wholly above the newest visible version ends at the boundary above
684        // it, a cursor this server accepts back. The boundary at version 0 lies below every
685        // version.
686        let edge = if self.descending {
687            plan.low.min(plan.high)
688        } else {
689            plan.high
690        };
691        self.boundary_cursor(edge.saturating_sub(1), bounding_checkpoint)
692    }
693
694    /// The cursor of the item at `version`, minted by a listing bounded by `bounding_checkpoint`.
695    pub fn cursor(&self, version: u64, bounding_checkpoint: u64) -> Bytes {
696        ObjectVersionCursor::Version {
697            object_id: self.object_id,
698            version,
699            bounding_checkpoint,
700        }
701        .encode()
702    }
703
704    /// The cursor of the boundary between `version` and the version after it, minted by a
705    /// listing bounded by `bounding_checkpoint`.
706    pub fn boundary_cursor(&self, version: u64, bounding_checkpoint: u64) -> Bytes {
707        ObjectVersionCursor::Boundary {
708            object_id: self.object_id,
709            version,
710            bounding_checkpoint,
711        }
712        .encode()
713    }
714
715    /// `cursor`, encoded as the request carried it.
716    fn echo(&self, cursor: &RequestCursor) -> Bytes {
717        if cursor.boundary {
718            self.boundary_cursor(cursor.version, cursor.bounding_checkpoint)
719        } else {
720            self.cursor(cursor.version, cursor.bounding_checkpoint)
721        }
722    }
723
724    /// The frames of a listing bounded by `bounding_checkpoint` (see
725    /// [`CheckpointWindow::bounding_checkpoint`]) whose items `listed` yields in listing order.
726    /// Each item goes out on its own frame, whose cursor is the item's: a live version as
727    /// `object`, a removal as `removal` with the fields [`Self::removal_read_mask`] selects. The
728    /// frame with the [`Self::limit`]th item ends the stream with `ITEM_LIMIT`, whatever `end`
729    /// says, and `listed` is not polled again. A `listed` that ends first is followed by a final
730    /// frame ending with `end`, whose cursor `end_cursor` resolves to once `listed` has ended (see
731    /// [`Self::end_cursor`]), so a listing with no items still returns a resume cursor. An error
732    /// `listed` yields ends the stream with it.
733    pub fn frames(
734        &self,
735        bounding_checkpoint: u64,
736        listed: BoxStream<'static, Result<ObjectVersionItem>>,
737        end: QueryEndReason,
738        end_cursor: impl Future<Output = Bytes> + Send + 'static,
739    ) -> ObjectVersionFrames {
740        let query = self.clone();
741        async_stream::try_stream! {
742            let mut listed = listed;
743            let mut produced = 0;
744            while let Some(item) = listed.next().await {
745                let item = item?;
746                produced += 1;
747                let mut frame = ListObjectVersionsResponse::default()
748                    .with_cursor(query.cursor(item.version().value(), bounding_checkpoint));
749                match item {
750                    ObjectVersionItem::Live { object, .. } => frame.set_object(object),
751                    ObjectVersionItem::Removal {
752                        version,
753                        kind,
754                        transaction,
755                    } => {
756                        let removal_read_mask = &query.removal_read_mask;
757                        let mut removal = ObjectRemoval::default();
758                        if removal_read_mask.contains(ObjectRemoval::VERSION_FIELD.name) {
759                            removal.set_version(version.value());
760                        }
761                        if removal_read_mask.contains(ObjectRemoval::KIND_FIELD.name) {
762                            removal.set_kind(object_removal::Kind::from(kind));
763                        }
764                        if removal_read_mask.contains(ObjectRemoval::TRANSACTION_FIELD.name) {
765                            removal.transaction = transaction.map(|digest| digest.to_string());
766                        }
767                        frame.set_removal(removal);
768                    }
769                }
770                if produced == query.limit {
771                    frame.end = Some(query_end(QueryEndReason::ItemLimit));
772                    yield frame;
773                    return;
774                }
775                yield frame;
776            }
777            yield ListObjectVersionsResponse::default()
778                .with_cursor(end_cursor.await)
779                .with_end(query_end(end));
780        }
781        .boxed()
782    }
783}
784
785fn query_end(reason: QueryEndReason) -> QueryEnd {
786    let mut end = QueryEnd::default();
787    end.reason = Some(reason as i32);
788    end
789}
790
791/// The cursor in request field `field`, which must name a version of the object `object_id`.
792fn request_cursor(field: &str, cursor: &Bytes, object_id: ObjectID) -> Result<RequestCursor> {
793    let decoded: ObjectVersionCursor = bcs::from_bytes(cursor).map_err(|e| {
794        FieldViolation::new(field)
795            .with_description(format!("invalid cursor encoding: {e}"))
796            .with_reason(ErrorReason::FieldInvalid)
797    })?;
798    let (cursor_object_id, cursor) = match decoded {
799        ObjectVersionCursor::Version {
800            object_id,
801            version,
802            bounding_checkpoint,
803        } => (
804            object_id,
805            RequestCursor {
806                version,
807                bounding_checkpoint,
808                boundary: false,
809            },
810        ),
811        ObjectVersionCursor::Boundary {
812            object_id,
813            version,
814            bounding_checkpoint,
815        } => (
816            object_id,
817            RequestCursor {
818                version,
819                bounding_checkpoint,
820                boundary: true,
821            },
822        ),
823    };
824    if cursor_object_id != object_id {
825        return Err(FieldViolation::new(field)
826            .with_description("cursor object ID does not match request object ID")
827            .with_reason(ErrorReason::FieldInvalid)
828            .into());
829    }
830    Ok(cursor)
831}
832
833/// Whether `options` asks for versions from highest to lowest.
834fn descending(options: Option<&QueryOptions>) -> Result<bool> {
835    match options
836        .and_then(|options| options.ordering)
837        .map(Ordering::try_from)
838    {
839        None | Some(Ok(Ordering::Ascending)) => Ok(false),
840        Some(Ok(Ordering::Descending)) => Ok(true),
841        Some(_) => Err(FieldViolation::new("options.ordering")
842            .with_description("invalid ordering")
843            .with_reason(ErrorReason::FieldInvalid)
844            .into()),
845    }
846}