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}