Skip to main content

sui_rpc_api/grpc/v2/ledger_service/
get_object.rs

1// Copyright (c) Mysten Labs, Inc.
2// SPDX-License-Identifier: Apache-2.0
3
4use super::list_object_versions::removal_kind;
5use super::list_object_versions::stored_version;
6use super::list_object_versions::stored_version_of_indexed;
7use crate::ErrorReason;
8use crate::ObjectRemoval;
9use crate::RpcError;
10use crate::RpcService;
11use crate::error::ObjectNotFoundError;
12use crate::grpc::v2::render::RenderContext;
13use crate::ledger_history::query_options::below_serving_floor;
14use crate::reader::AtCheckpointUpperBound;
15use crate::reader::StateReader;
16use mysten_common::ZipDebugEqIteratorExt;
17use prost_types::FieldMask;
18use sui_rpc::field::FieldMaskTree;
19use sui_rpc::field::FieldMaskUtil;
20use sui_rpc::proto::google::rpc::bad_request::FieldViolation;
21use sui_rpc::proto::sui::rpc::v2::BatchGetObjectsRequest;
22use sui_rpc::proto::sui::rpc::v2::BatchGetObjectsResponse;
23use sui_rpc::proto::sui::rpc::v2::GetObjectRequest;
24use sui_rpc::proto::sui::rpc::v2::GetObjectResponse;
25use sui_rpc::proto::sui::rpc::v2::GetObjectResult;
26use sui_rpc::proto::sui::rpc::v2::Object;
27use sui_sdk_types::Address;
28use sui_types::base_types::ObjectID;
29use sui_types::base_types::ObjectRef;
30use sui_types::base_types::SequenceNumber;
31use sui_types::object::Object as StoredObject;
32use sui_types::storage::ObjectOrTombstone;
33use sui_types::storage::RpcStateReader;
34
35pub const MAX_BATCH_REQUESTS: usize = 1000;
36pub const READ_MASK_DEFAULT: &str = crate::read_mask_defaults::OBJECT;
37
38/// Which state of an object a `GetObjectRequest` reads.
39#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
40pub enum ObjectSelector {
41    /// The latest live version (none of `version`, `max_version` and `at_checkpoint` set).
42    Latest,
43    /// Exactly `version`. With `at_checkpoint`, only if that version was written at or before
44    /// the checkpoint. A fullnode whose object lower bound is above 0 (it pruned object versions
45    /// or was restored from a snapshot) answers a version it does not hold with `OUT_OF_RANGE` /
46    /// `BELOW_EARLIEST_AVAILABLE` rather than `NOT_FOUND`, unless it holds the tombstone of a
47    /// deletion or wrap at that version, the version is above the object's latest version, or
48    /// `at_checkpoint` decides the answer without it (see `resolve_missing_versions` in this
49    /// module). With `at_checkpoint`, it answers the same way when the version index records no
50    /// version of the object as of the checkpoint, since pruning removes the index history of an
51    /// object deleted or wrapped in a pruned checkpoint.
52    Version {
53        version: u64,
54        at_checkpoint: Option<u64>,
55    },
56    /// The newest version at or below `max_version`, unless the object was deleted or wrapped at
57    /// that version. With `at_checkpoint`, versions count up to the height the server answers
58    /// `at_checkpoint` reads at, and the read fails if the selected version was written after the
59    /// checkpoint, so it agrees with a `version` read of the selected version at that checkpoint.
60    /// Without it, a fullnode reads its live state, counting every version it holds, including
61    /// those not yet committed from its execution cache to its store, and kv-rpc reads at its
62    /// served height, answering as if `at_checkpoint` were set to it, since versions above it may
63    /// be in its tables before their deletions and wraps are. A fullnode whose object lower bound
64    /// is above 0 answers a read that finds no live version to select with `OUT_OF_RANGE` /
65    /// `BELOW_EARLIEST_AVAILABLE` rather than `NOT_FOUND`, since the versions it would select
66    /// from may have been pruned, unless the read resolves to a deletion or wrap that is the
67    /// object's latest version, its version at the end of `at_checkpoint`, or one whose
68    /// transaction's checkpoint is at or above that bound. A read with `at_checkpoint` is refused
69    /// the same way when the version index records no version of the object as of the
70    /// checkpoint. A fullnode serves it only with rpc indexes whose history is not still
71    /// backfilling after a restore.
72    MaxVersion {
73        max_version: u64,
74        at_checkpoint: Option<u64>,
75    },
76    /// The object's state at the end of this checkpoint (`at_checkpoint` alone).
77    AtCheckpoint(u64),
78}
79
80impl ObjectSelector {
81    /// The request's `at_checkpoint`: the checkpoint an [`Self::AtCheckpoint`] read is pinned
82    /// to, or the checkpoint that bounds a [`Self::Version`] or [`Self::MaxVersion`] read to
83    /// versions written at or before it. Either way, the read fails if the checkpoint is outside
84    /// the range the server can answer for.
85    pub fn at_checkpoint(&self) -> Option<u64> {
86        match *self {
87            Self::Latest => None,
88            Self::Version { at_checkpoint, .. } | Self::MaxVersion { at_checkpoint, .. } => {
89                at_checkpoint
90            }
91            Self::AtCheckpoint(checkpoint) => Some(checkpoint),
92        }
93    }
94
95    /// Whether the read picks its version by a bound rather than by name: every read with
96    /// `at_checkpoint`, and every `max_version` read. These reads need the rpc indexes' history on
97    /// a fullnode, and kv-rpc's object-at-checkpoint reads.
98    pub fn selects_version_by_bound(&self) -> bool {
99        matches!(self, Self::MaxVersion { .. }) || self.at_checkpoint().is_some()
100    }
101
102    /// The `NotFound` error for `object_id` when this selector finds no object.
103    pub fn not_found(&self, object_id: Address) -> ObjectNotFoundError {
104        let error = match *self {
105            Self::Latest | Self::AtCheckpoint(_) => ObjectNotFoundError::new(object_id),
106            Self::Version { version, .. } => {
107                ObjectNotFoundError::new_with_version(object_id, version)
108            }
109            Self::MaxVersion { max_version, .. } => {
110                ObjectNotFoundError::new_with_max_version(object_id, max_version)
111            }
112        };
113        match self.at_checkpoint() {
114            Some(checkpoint) => error.at_checkpoint(checkpoint),
115            None => error,
116        }
117    }
118}
119
120type ValidationResult = Result<(Vec<(Address, ObjectSelector)>, FieldMaskTree), RpcError>;
121
122/// Validate each request's `object_id` and selector fields, and the read mask shared by all of
123/// them; each request's own `read_mask` is ignored. A request that sets both `version` and
124/// `max_version` is rejected. `at_checkpoint` combines with either. `batch` says whether
125/// `requests` are the items of a `BatchGetObjects` request: the `max_version` violation then
126/// names the item (`requests[i].max_version`), and for a `GetObject` request the field alone.
127pub fn validate_get_object_requests(
128    requests: &[GetObjectRequest],
129    read_mask: Option<FieldMask>,
130    batch: bool,
131) -> ValidationResult {
132    let read_mask = {
133        let read_mask = read_mask.unwrap_or_else(|| FieldMask::from_str(READ_MASK_DEFAULT));
134        read_mask.validate::<Object>().map_err(|path| {
135            FieldViolation::new("read_mask")
136                .with_description(format!("invalid read_mask path: {path}"))
137                .with_reason(ErrorReason::FieldInvalid)
138        })?;
139        FieldMaskTree::from(read_mask)
140    };
141    let requests = requests
142        .iter()
143        .enumerate()
144        .map(|(idx, request)| {
145            let object_id = request
146                .object_id
147                .as_ref()
148                .ok_or_else(|| {
149                    FieldViolation::new("object_id")
150                        .with_reason(ErrorReason::FieldMissing)
151                        .nested_at("requests", idx)
152                })?
153                .parse()
154                .map_err(|e| {
155                    FieldViolation::new("object_id")
156                        .with_description(format!("invalid object_id: {e}"))
157                        .with_reason(ErrorReason::FieldInvalid)
158                        .nested_at("requests", idx)
159                })?;
160            let selector = match (request.version, request.max_version, request.at_checkpoint) {
161                (Some(_), Some(_), _) => {
162                    let violation = FieldViolation::new("max_version")
163                        .with_description("version and max_version are mutually exclusive")
164                        .with_reason(ErrorReason::FieldInvalid);
165                    return Err(if batch {
166                        violation.nested_at("requests", idx)
167                    } else {
168                        violation
169                    }
170                    .into());
171                }
172                (None, None, None) => ObjectSelector::Latest,
173                (None, None, Some(checkpoint)) => ObjectSelector::AtCheckpoint(checkpoint),
174                (Some(version), None, at_checkpoint) => ObjectSelector::Version {
175                    version,
176                    at_checkpoint,
177                },
178                (None, Some(max_version), at_checkpoint) => ObjectSelector::MaxVersion {
179                    max_version,
180                    at_checkpoint,
181                },
182            };
183            Ok((object_id, selector))
184        })
185        .collect::<Result<_, RpcError>>()?;
186    Ok((requests, read_mask))
187}
188
189#[tracing::instrument(skip(service))]
190pub fn get_object(
191    service: &RpcService,
192    mut request: GetObjectRequest,
193) -> Result<GetObjectResponse, RpcError> {
194    let read_mask = request.read_mask.take();
195    let (requests, read_mask) =
196        validate_get_object_requests(std::slice::from_ref(&request), read_mask, false)?;
197    let upper_bound = load_at_checkpoint_upper_bound(service, &requests)?;
198    let (object_id, selector) = requests[0];
199    let render_context = RenderContext::empty(service.reader.inner());
200    let read = get_object_impl(
201        service,
202        object_id,
203        selector,
204        upper_bound.as_ref(),
205        &read_mask,
206        &render_context,
207    );
208    let mut results = resolve_missing_versions(service, &requests, vec![read])?;
209    apply_at_checkpoint_lower_bound(service, &requests, upper_bound.as_ref(), &mut results)?;
210    // One request, so one result.
211    results.swap_remove(0).map(GetObjectResponse::new)
212}
213
214#[tracing::instrument(skip(service))]
215pub fn batch_get_objects(
216    service: &RpcService,
217    BatchGetObjectsRequest {
218        requests,
219        read_mask,
220        ..
221    }: BatchGetObjectsRequest,
222) -> Result<BatchGetObjectsResponse, RpcError> {
223    if requests.len() > MAX_BATCH_REQUESTS {
224        return Err(RpcError::new(
225            tonic::Code::InvalidArgument,
226            format!("number of batch requests exceed limit of {MAX_BATCH_REQUESTS}"),
227        ));
228    }
229
230    let (requests, read_mask) = validate_get_object_requests(&requests, read_mask, true)?;
231
232    let upper_bound = load_at_checkpoint_upper_bound(service, &requests)?;
233    let render_context = RenderContext::empty(service.reader.inner());
234    let reads: Vec<_> = requests
235        .iter()
236        .map(|&(object_id, selector)| {
237            get_object_impl(
238                service,
239                object_id,
240                selector,
241                upper_bound.as_ref(),
242                &read_mask,
243                &render_context,
244            )
245        })
246        .collect();
247    let mut results = resolve_missing_versions(service, &requests, reads)?;
248    apply_at_checkpoint_lower_bound(service, &requests, upper_bound.as_ref(), &mut results)?;
249    let objects = results
250        .into_iter()
251        .map(|result| match result {
252            Ok(object) => GetObjectResult::new_object(object),
253            Err(error) => GetObjectResult::new_error(error.into_status_proto()),
254        })
255        .collect();
256    Ok(BatchGetObjectsResponse::new(objects))
257}
258
259/// Before the reads, once per request, refuse the whole request if this node cannot serve one
260/// of its items, and load what the reads check:
261///
262/// - If some item sets `at_checkpoint`, the upper bound the reads at a checkpoint check
263///   (`StateReader::at_checkpoint_upper_bound`), which needs the rpc indexes' history.
264/// - Otherwise, a `max_version` item needs the rpc indexes' history
265///   (`StateReader::require_rpc_index_history`): on a pruned node its read checks the version
266///   it finds against them.
267///
268/// Other reads still work on nodes without rpc indexes.
269fn load_at_checkpoint_upper_bound(
270    service: &RpcService,
271    requests: &[(Address, ObjectSelector)],
272) -> Result<Option<AtCheckpointUpperBound>, RpcError> {
273    let any = |predicate: fn(&ObjectSelector) -> bool| {
274        requests.iter().any(|(_, selector)| predicate(selector))
275    };
276    if any(|selector| selector.at_checkpoint().is_some()) {
277        return service.reader.at_checkpoint_upper_bound().map(Some);
278    }
279    if any(|selector| matches!(selector, ObjectSelector::MaxVersion { .. })) {
280        service.reader.require_rpc_index_history()?;
281    }
282    Ok(None)
283}
284
285/// After the reads: answer every item whose read found a version missing (`Ok(None)` from
286/// [`get_object_impl`]), with this node's object lower bound
287/// ([`sui_types::storage::RpcStateReader::get_lowest_available_checkpoint_objects`]) and its
288/// objects' latest versions. See [`missing_version_error`].
289///
290/// The lower bound is read at most once per request, after the reads: pruning can raise it while
291/// the reads run, and a version pruned meanwhile then fails as pruned rather than as one that
292/// never existed.
293fn resolve_missing_versions(
294    service: &RpcService,
295    requests: &[(Address, ObjectSelector)],
296    reads: Vec<Result<Option<Object>, RpcError>>,
297) -> Result<Vec<Result<Object, RpcError>>, RpcError> {
298    let reader = service.reader.inner();
299    answer_missing_versions(
300        requests,
301        reads,
302        || Ok(reader.get_lowest_available_checkpoint_objects()?),
303        |object_id| latest_version(reader.as_ref(), ObjectID::from(object_id)),
304    )
305}
306
307/// The object's latest version, live or a deletion or wrap, read through the execution cache, so
308/// it sees changes not committed to the store yet. The live object is read first: that read
309/// caches the absence of an object with no version, so the newest-entry read after it, and both
310/// reads of a later request for the same object, find it in the cache. A store that keeps no
311/// tombstones reads none, and gives the latest live version.
312fn latest_version(reader: &dyn RpcStateReader, id: ObjectID) -> Option<LatestVersion> {
313    if let Some(object) = reader.get_object(&id) {
314        return Some(LatestVersion {
315            version: object.version(),
316            removed: false,
317        });
318    }
319    let item = reader.get_latest_object_or_tombstone(&id).ok()??;
320    Some(LatestVersion {
321        version: stored_version(&item),
322        removed: matches!(item, ObjectOrTombstone::Tombstone(_)),
323    })
324}
325
326/// An object's newest version in the object store, live or a deletion or wrap.
327#[derive(Clone, Copy, Debug)]
328struct LatestVersion {
329    version: SequenceNumber,
330    /// Whether the object was deleted or wrapped at `version`.
331    removed: bool,
332}
333
334/// [`resolve_missing_versions`] with the object lower bound and the objects' latest versions read
335/// through `objects_lower_bound` and `latest_version`. `objects_lower_bound` is called only if
336/// some read found a version missing.
337fn answer_missing_versions(
338    requests: &[(Address, ObjectSelector)],
339    reads: Vec<Result<Option<Object>, RpcError>>,
340    objects_lower_bound: impl FnOnce() -> Result<u64, RpcError>,
341    latest_version: impl Fn(Address) -> Option<LatestVersion>,
342) -> Result<Vec<Result<Object, RpcError>>, RpcError> {
343    let objects_lower_bound = if reads.iter().any(|read| matches!(read, Ok(None))) {
344        objects_lower_bound()?
345    } else {
346        0
347    };
348    Ok(requests
349        .iter()
350        .zip_debug_eq(reads)
351        .map(|(&(object_id, selector), read)| match read? {
352            Some(object) => Ok(object),
353            None => Err(missing_version_error(
354                object_id,
355                selector,
356                objects_lower_bound,
357                || latest_version(object_id),
358            )),
359        })
360        .collect())
361}
362
363/// The answer to a read that found the version it needs missing from the object store, and no
364/// deletion or wrap there that it could describe (see [`get_object_impl`]).
365///
366/// - `NOT_FOUND` if `objects_lower_bound` is 0: the node was neither pruned nor restored from a
367///   snapshot, so it holds every version ever written, and the missing one never existed.
368/// - `NOT_FOUND` for a `max_version` read without `at_checkpoint`, if the object's latest version
369///   (`latest_version`) is a deletion or wrap at or below `max_version`: that removal is the
370///   newest version at or below `max_version`. The read gets here, without the removal described,
371///   only when the store's tombstone lookup refused that tombstone as possibly below the object
372///   lower bound; a failed lookup fails the read instead (see [`read_object`]). The latest version
373///   is read through the execution cache, so it includes versions not committed to the store yet.
374/// - Otherwise `OUT_OF_RANGE` / `BELOW_EARLIEST_AVAILABLE` with `objects_lower_bound` as the
375///   lowest available checkpoint, since the version may have been pruned. That includes a
376///   `max_version` read that finds no live version at or below `max_version`, an object with no
377///   version left, and a `version` or `max_version` read with `at_checkpoint` of an object the
378///   version index records no version of as of the checkpoint (see [`VersionRead::NoVersionYet`]).
379///   The object store's live reads do not tell a deletion or wrap from a pruned version, so a
380///   read that resolves to a removal this node keeps no tombstone of, or one the store's
381///   tombstone lookup refuses as possibly below the object lower bound, fails the same way. (An
382///   exact `version` above the object's latest version is `NOT_FOUND` before it gets here; see
383///   [`exact_version_after_miss`].)
384fn missing_version_error(
385    object_id: Address,
386    selector: ObjectSelector,
387    objects_lower_bound: u64,
388    latest_version: impl FnOnce() -> Option<LatestVersion>,
389) -> RpcError {
390    let answered_by_latest_version = || match selector {
391        ObjectSelector::MaxVersion {
392            max_version,
393            at_checkpoint: None,
394        } => latest_version().is_some_and(|latest| {
395            latest.removed && latest.version <= SequenceNumber::from_u64(max_version)
396        }),
397        _ => false,
398    };
399    if objects_lower_bound == 0 || answered_by_latest_version() {
400        selector.not_found(object_id).into()
401    } else {
402        below_serving_floor(objects_lower_bound)
403    }
404}
405
406/// After the reads: answer as pruned every item whose `at_checkpoint` is below the lower bound
407/// (see `StateReader::at_checkpoint_lower_bound`), replacing whatever its read returned, since
408/// that read may have seen pruned data.
409fn apply_at_checkpoint_lower_bound(
410    service: &RpcService,
411    requests: &[(Address, ObjectSelector)],
412    upper_bound: Option<&AtCheckpointUpperBound>,
413    results: &mut [Result<Object, RpcError>],
414) -> Result<(), RpcError> {
415    // The request loads an upper bound exactly when some item sets `at_checkpoint`.
416    if upper_bound.is_none() {
417        return Ok(());
418    }
419    let lower_bound = service.reader.at_checkpoint_lower_bound()?;
420    for (&(_, selector), result) in requests.iter().zip_debug_eq(results.iter_mut()) {
421        if let Some(checkpoint) = selector.at_checkpoint()
422            && let Err(error) = lower_bound.check(checkpoint)
423        {
424            *result = Err(error);
425        }
426    }
427    Ok(())
428}
429
430/// What a read found for the version its selector picks.
431#[derive(Debug)]
432enum VersionRead<T> {
433    /// The selected version: the object, live, or read with tombstones (see [`select`]), the
434    /// tombstone of the deletion or wrap at that version.
435    Selected(T),
436    /// The answer is that the object does not exist (`NOT_FOUND`): the selected version was
437    /// written after the request's `at_checkpoint`, or deleted or wrapped the object.
438    NotFound,
439    /// The version index records no version of the object as of the request's `at_checkpoint`:
440    /// the object did not exist yet, or it was deleted or wrapped in a checkpoint this node
441    /// pruned, along with the object's index history. Either way the object does not exist at
442    /// the checkpoint, so `at_checkpoint` alone is `NOT_FOUND`, but a `version` or `max_version`
443    /// read may select a version that existed and was pruned, so it is missing data (see
444    /// [`read_object`]). There is no deletion or wrap to describe from the index.
445    NoVersionYet,
446    /// The object store has no live version where the read needs one. The version may never
447    /// have existed, may be a deletion or wrap, or may have been pruned; see
448    /// [`missing_version_error`].
449    Missing,
450}
451
452impl<T> VersionRead<T> {
453    /// The item, or [`Self::NotFound`] if there is none.
454    fn or_not_found(item: Option<T>) -> Self {
455        item.map_or(Self::NotFound, Self::Selected)
456    }
457
458    /// The item, or [`Self::Missing`] if there is none.
459    fn or_missing(item: Option<T>) -> Self {
460        item.map_or(Self::Missing, Self::Selected)
461    }
462}
463
464/// What a read of one object answers.
465#[derive(Debug)]
466enum ObjectRead {
467    /// The live object the selector picks.
468    Live(StoredObject),
469    /// `NOT_FOUND`, describing the deletion or wrap the read resolved to when it found it. A read
470    /// that found no live version answers with the removal its selection over tombstones picked;
471    /// on a pruned node, the store's tombstone lookup returns no tombstone that may have a pruned
472    /// version after it (see
473    /// [`sui_types::storage::RpcStateReader::get_object_or_tombstone_lt_or_eq_version`]).
474    NotFound(Option<ObjectRemoval>),
475    /// The object store has no live version where the read needs one, and the read found no
476    /// deletion or wrap there to answer with, or a `version` or `max_version` read with
477    /// `at_checkpoint` found no version index record ([`VersionRead::NoVersionYet`]); see
478    /// [`missing_version_error`].
479    Missing,
480}
481
482/// Read one object. `upper_bound` is set whenever some item of the request sets `at_checkpoint`;
483/// the reader checks it before any read at the checkpoint, so a
484/// checkpoint above it fails the read whatever the object's state. A read that resolves to a
485/// deletion or wrap answers `NotFound`, describing the removal if [`read_object`] finds it.
486/// `Ok(None)` if a `version` or `max_version` read found the version it needs missing, and no
487/// removal there that it can answer with (see [`ObjectRead::Missing`]);
488/// [`resolve_missing_versions`] answers it after the reads.
489#[tracing::instrument(skip(service, render_context))]
490fn get_object_impl(
491    service: &RpcService,
492    object_id: Address,
493    selector: ObjectSelector,
494    upper_bound: Option<&AtCheckpointUpperBound>,
495    read_mask: &FieldMaskTree,
496    render_context: &RenderContext,
497) -> Result<Option<Object>, RpcError> {
498    let reader = &service.reader;
499    let id = ObjectID::from(object_id);
500    // A node without object version history serves only each object's latest version, and
501    // decides from its newest entry, live or a tombstone: the compactor keeps that entry, so the
502    // answer does not change as compaction proceeds. A version above that entry has not been
503    // written yet and is `NotFound`, as on any node; an object with no entry at all is `NotFound`
504    // too. A deletion or wrap at exactly that version is `NotFound` with the removal described.
505    // Any older version is refused (`OutOfRange`, `VERSION_NOT_RETAINED`) even while it is still
506    // stored.
507    if let ObjectSelector::Version {
508        version,
509        at_checkpoint: None,
510    } = selector
511        && let Err(refusal) = reader.require_object_version_history()
512    {
513        // The live object first: a store that keeps no tombstones reads no newest entry.
514        let newest = match reader.inner().get_object(&id) {
515            Some(object) => Some(ObjectOrTombstone::Object(object)),
516            None => ObjectsOrTombstones(reader).latest(id)?,
517        };
518        return match newest {
519            Some(ObjectOrTombstone::Object(object)) if object.version().value() == version => Ok(
520                Some(service.render_object_to_proto(&object, read_mask, render_context)),
521            ),
522            Some(item) if item.stored_version().value() < version => {
523                Err(selector.not_found(object_id).into())
524            }
525            Some(ObjectOrTombstone::Tombstone(tombstone @ (_, removed_at, _)))
526                if removed_at.value() == version =>
527            {
528                let removal = tombstone_removal(tombstone);
529                Err(not_found_describing(selector.not_found(object_id), removal).into())
530            }
531            Some(_) => Err(refusal),
532            None => Err(selector.not_found(object_id).into()),
533        };
534    }
535    let read = || {
536        read_object(
537            &LiveObjects(reader),
538            &ObjectsOrTombstones(reader),
539            id,
540            selector,
541            upper_bound,
542        )
543    };
544    let read = match selector {
545        ObjectSelector::Version {
546            version,
547            at_checkpoint: None,
548        } => match LiveObjects(reader).by_key(id, version.into())? {
549            Some(object) => ObjectRead::Live(object),
550            None => exact_version_after_miss(
551                version.into(),
552                || latest_version(reader.inner().as_ref(), id),
553                read,
554            )?,
555        },
556        _ => read()?,
557    };
558    match read {
559        ObjectRead::Live(object) => Ok(Some(service.render_object_to_proto(
560            &object,
561            read_mask,
562            render_context,
563        ))),
564        ObjectRead::NotFound(removal) => {
565            Err(not_found_describing(selector.not_found(object_id), removal).into())
566        }
567        ObjectRead::Missing => Ok(None),
568    }
569}
570
571/// An exact `version` read without `at_checkpoint` whose read of the live object found the
572/// version missing. A version above the object's latest version (`latest_version`, live or a
573/// deletion or wrap) has not been written yet, and is `NOT_FOUND` on any node. The latest version
574/// is read only after the miss, so a version at or below it may have been written between the
575/// two reads: `read_again` reads it again, live and then with tombstones to describe a deletion
576/// or wrap at it, and it is [`ObjectRead::Missing`] only if that read finds neither. A version
577/// that misses is looked for with tombstones once, after the latest version.
578fn exact_version_after_miss(
579    version: SequenceNumber,
580    latest_version: impl FnOnce() -> Option<LatestVersion>,
581    read_again: impl FnOnce() -> Result<ObjectRead, RpcError>,
582) -> Result<ObjectRead, RpcError> {
583    match latest_version() {
584        Some(latest) if version > latest.version => Ok(ObjectRead::NotFound(None)),
585        Some(_) => read_again(),
586        None => Ok(ObjectRead::Missing),
587    }
588}
589
590/// `not_found`, describing `removal` if there is one.
591fn not_found_describing(
592    not_found: ObjectNotFoundError,
593    removal: Option<ObjectRemoval>,
594) -> ObjectNotFoundError {
595    match removal {
596        Some(removal) => not_found.removed(removal),
597        None => not_found,
598    }
599}
600
601/// Read object `id` by `selector`: select through `live`, and if that finds no live object,
602/// look for the deletion or wrap the read resolved to with [`find_removal`] over
603/// `with_tombstones`, or, where it found the version it needs missing, answer with
604/// [`resolve_missing`].
605///
606/// The selection over live objects answers the read unless it finds the version missing;
607/// otherwise the one with tombstones only describes a removal. It is skipped where the version
608/// index records no version of the object as of the read's `at_checkpoint`
609/// ([`VersionRead::NoVersionYet`]), so an object that never existed costs that one index read:
610/// `NOT_FOUND` for `at_checkpoint` alone, and missing data ([`ObjectRead::Missing`]) for a
611/// `version` or `max_version` read. A `max_version` read without `at_checkpoint` selects once,
612/// with tombstones: the store's live and tombstone lookups at or below a version select the same
613/// entry, so the one with tombstones answers the read whether that entry is live or a removal.
614fn read_object(
615    live: &impl ObjectReads<Item = StoredObject>,
616    with_tombstones: &impl ObjectReads<Item = ObjectOrTombstone>,
617    id: ObjectID,
618    selector: ObjectSelector,
619    upper_bound: Option<&AtCheckpointUpperBound>,
620) -> Result<ObjectRead, RpcError> {
621    if let ObjectSelector::MaxVersion {
622        at_checkpoint: None,
623        ..
624    } = selector
625    {
626        return Ok(match select(with_tombstones, id, selector, upper_bound)? {
627            VersionRead::Selected(ObjectOrTombstone::Object(object)) => ObjectRead::Live(object),
628            VersionRead::Selected(ObjectOrTombstone::Tombstone(tombstone)) => {
629                match tombstone_removal(tombstone) {
630                    Some(removal) => ObjectRead::NotFound(Some(removal)),
631                    None => ObjectRead::Missing,
632                }
633            }
634            // This selector reads `Selected` or `Missing`.
635            _ => ObjectRead::Missing,
636        });
637    }
638    let read = select(live, id, selector, upper_bound)?;
639    let removal = || find_removal(with_tombstones, id, selector, upper_bound);
640    Ok(match read {
641        VersionRead::Selected(object) => ObjectRead::Live(object),
642        VersionRead::NoVersionYet => match selector {
643            ObjectSelector::AtCheckpoint(_) => ObjectRead::NotFound(None),
644            _ => ObjectRead::Missing,
645        },
646        VersionRead::NotFound => ObjectRead::NotFound(removal()),
647        VersionRead::Missing => resolve_missing(with_tombstones, id, selector, upper_bound),
648    })
649}
650
651/// The answer to a read whose selection over live objects found the version it needs missing
652/// ([`VersionRead::Missing`]), from the same selection over the object store's tombstones as well
653/// as its live objects (`reads`). The live selection cannot tell a deletion or wrap from a pruned
654/// version; this one can. A removal it selects answers `NOT_FOUND`, described. So does its
655/// [`VersionRead::NotFound`], as for a `max_version` read with `at_checkpoint` K whose newest
656/// version at or below `max_version` is a removal written after K. The store's tombstone lookup
657/// refuses an entry that may have a pruned version after it. [`ObjectRead::Missing`] if the
658/// selection resolves to nothing, to a live object (written after the live read), or a read
659/// fails.
660fn resolve_missing(
661    reads: &impl ObjectReads<Item = ObjectOrTombstone>,
662    id: ObjectID,
663    selector: ObjectSelector,
664    upper_bound: Option<&AtCheckpointUpperBound>,
665) -> ObjectRead {
666    match select(reads, id, selector, upper_bound) {
667        Ok(VersionRead::Selected(ObjectOrTombstone::Tombstone(tombstone))) => {
668            match tombstone_removal(tombstone) {
669                Some(removal) => ObjectRead::NotFound(Some(removal)),
670                None => ObjectRead::Missing,
671            }
672        }
673        Ok(VersionRead::NotFound) => ObjectRead::NotFound(None),
674        _ => ObjectRead::Missing,
675    }
676}
677
678/// The deletion or wrap `selector` resolved to, for a read that found no live object: the same
679/// selection over the object store's tombstones as well as its live objects (`reads`). Best
680/// effort: `None` if the store keeps no tombstones, the selection finds none, or a read fails,
681/// which leaves the `NotFound` answer without detail.
682fn find_removal(
683    reads: &impl ObjectReads<Item = ObjectOrTombstone>,
684    id: ObjectID,
685    selector: ObjectSelector,
686    upper_bound: Option<&AtCheckpointUpperBound>,
687) -> Option<ObjectRemoval> {
688    let Ok(VersionRead::Selected(ObjectOrTombstone::Tombstone(tombstone))) =
689        select(reads, id, selector, upper_bound)
690    else {
691        return None;
692    };
693    tombstone_removal(tombstone)
694}
695
696/// The deletion or wrap the tombstone `(_, version, digest)` records. `None` if the digest marks
697/// no deletion or wrap. The removing transaction is not looked up: `ListObjectVersions` finds it
698/// when the request's `removal_read_mask` names `transaction`.
699fn tombstone_removal((_, version, digest): ObjectRef) -> Option<ObjectRemoval> {
700    Some(ObjectRemoval {
701        version: version.value(),
702        kind: removal_kind(&digest).ok()?,
703    })
704}
705
706/// The version `selector` reads of object `id`, through `reads`: what [`get_object_impl`] renders
707/// when `reads` reads live objects, or with [`ObjectsOrTombstones`], the tombstone in its place
708/// when that version deleted or wrapped the object. The versions the version index records come
709/// through [`ObjectReads::version_at_checkpoint`]. A read with `at_checkpoint` checks
710/// `upper_bound` before any read at the checkpoint.
711fn select<R: ObjectReads>(
712    reads: &R,
713    id: ObjectID,
714    selector: ObjectSelector,
715    upper_bound: Option<&AtCheckpointUpperBound>,
716) -> Result<VersionRead<R::Item>, RpcError> {
717    let upper_bound = || {
718        upper_bound.ok_or_else(|| {
719            RpcError::new(
720                tonic::Code::Internal,
721                "at_checkpoint upper bound was not loaded",
722            )
723        })
724    };
725    let version_at = |checkpoint, upper_bound: &AtCheckpointUpperBound| {
726        reads.version_at_checkpoint(id, checkpoint, upper_bound)
727    };
728    match selector {
729        ObjectSelector::Latest => Ok(VersionRead::or_not_found(reads.latest(id)?)),
730        ObjectSelector::Version {
731            version,
732            at_checkpoint: None,
733        } => Ok(VersionRead::or_missing(reads.by_key(id, version.into())?)),
734        ObjectSelector::Version {
735            version,
736            at_checkpoint: Some(checkpoint),
737        } => version_at_checkpoint(
738            version.into(),
739            version_at(checkpoint, upper_bound()?)?,
740            |version| reads.by_key(id, version),
741        ),
742        ObjectSelector::MaxVersion {
743            max_version,
744            at_checkpoint: None,
745        } => Ok(VersionRead::or_missing(
746            reads.lt_or_eq(id, max_version.into())?,
747        )),
748        ObjectSelector::MaxVersion {
749            max_version,
750            at_checkpoint: Some(checkpoint),
751        } => {
752            let upper_bound = upper_bound()?;
753            max_version_at_checkpoint(
754                max_version.into(),
755                version_at(checkpoint, upper_bound)?,
756                || version_at(upper_bound.highest_indexed(), upper_bound),
757                |version| reads.by_key(id, version),
758                |version| reads.lt_or_eq(id, version),
759            )
760        }
761        ObjectSelector::AtCheckpoint(checkpoint) => {
762            // A deletion or wrapping tombstone has no live object at its version.
763            match version_at(checkpoint, upper_bound()?)? {
764                Some(version) => Ok(VersionRead::or_not_found(reads.by_key(id, version)?)),
765                None => Ok(VersionRead::NoVersionYet),
766            }
767        }
768    }
769}
770
771/// The object store reads [`select`] makes.
772trait ObjectReads {
773    type Item: StoredVersion;
774
775    /// The object's latest version.
776    fn latest(&self, id: ObjectID) -> Result<Option<Self::Item>, RpcError>;
777
778    /// Exactly `version` of the object.
779    fn by_key(&self, id: ObjectID, version: SequenceNumber)
780    -> Result<Option<Self::Item>, RpcError>;
781
782    /// The object's newest version at or below `version`.
783    fn lt_or_eq(
784        &self,
785        id: ObjectID,
786        version: SequenceNumber,
787    ) -> Result<Option<Self::Item>, RpcError>;
788
789    /// The object's version at the end of `checkpoint`, as the version index records it (see
790    /// [`crate::reader::StateReader::get_object_version_at_checkpoint`]), mapped to the version in
791    /// the object store of the item it records, as far as these reads tell the two apart.
792    fn version_at_checkpoint(
793        &self,
794        id: ObjectID,
795        checkpoint: u64,
796        upper_bound: &AtCheckpointUpperBound,
797    ) -> Result<Option<SequenceNumber>, RpcError>;
798}
799
800/// Reads of live objects: a version at which the object was deleted or wrapped reads as `None`.
801struct LiveObjects<'a>(&'a StateReader);
802
803impl ObjectReads for LiveObjects<'_> {
804    type Item = StoredObject;
805
806    fn latest(&self, id: ObjectID) -> Result<Option<StoredObject>, RpcError> {
807        Ok(self.0.inner().get_object(&id))
808    }
809
810    fn by_key(
811        &self,
812        id: ObjectID,
813        version: SequenceNumber,
814    ) -> Result<Option<StoredObject>, RpcError> {
815        Ok(self.0.inner().get_object_by_key(&id, version))
816    }
817
818    fn lt_or_eq(
819        &self,
820        id: ObjectID,
821        version: SequenceNumber,
822    ) -> Result<Option<StoredObject>, RpcError> {
823        Ok(self.0.inner().get_object_lt_or_eq_version(&id, version)?)
824    }
825
826    /// The index records every live version at that version. A removal it records below its
827    /// tombstone (see [`newest_version_written_by`]) reads as no live object at either version.
828    fn version_at_checkpoint(
829        &self,
830        id: ObjectID,
831        checkpoint: u64,
832        upper_bound: &AtCheckpointUpperBound,
833    ) -> Result<Option<SequenceNumber>, RpcError> {
834        self.0
835            .get_object_version_at_checkpoint(id, checkpoint, upper_bound)
836    }
837}
838
839/// Reads of live objects and tombstones: a version at which the object was deleted or wrapped
840/// reads as its tombstone. Only as complete as the store's
841/// [`sui_types::storage::RpcStateReader::get_object_or_tombstone_lt_or_eq_version`] and
842/// [`sui_types::storage::RpcStateReader::get_object_or_tombstone_by_key`].
843struct ObjectsOrTombstones<'a>(&'a StateReader);
844
845impl ObjectReads for ObjectsOrTombstones<'_> {
846    type Item = ObjectOrTombstone;
847
848    fn latest(&self, id: ObjectID) -> Result<Option<ObjectOrTombstone>, RpcError> {
849        Ok(self.0.inner().get_latest_object_or_tombstone(&id)?)
850    }
851
852    fn by_key(
853        &self,
854        id: ObjectID,
855        version: SequenceNumber,
856    ) -> Result<Option<ObjectOrTombstone>, RpcError> {
857        Ok(self
858            .0
859            .inner()
860            .get_object_or_tombstone_by_key(&id, version)?)
861    }
862
863    fn lt_or_eq(
864        &self,
865        id: ObjectID,
866        version: SequenceNumber,
867    ) -> Result<Option<ObjectOrTombstone>, RpcError> {
868        Ok(self
869            .0
870            .inner()
871            .get_object_or_tombstone_lt_or_eq_version(&id, version)?)
872    }
873
874    fn version_at_checkpoint(
875        &self,
876        id: ObjectID,
877        checkpoint: u64,
878        upper_bound: &AtCheckpointUpperBound,
879    ) -> Result<Option<SequenceNumber>, RpcError> {
880        let indexed = self
881            .0
882            .get_object_version_at_checkpoint(id, checkpoint, upper_bound)?;
883        stored_version_of_indexed(self.0, id, indexed)
884    }
885}
886
887/// A version read from the object store, live or a tombstone.
888trait StoredVersion {
889    fn stored_version(&self) -> SequenceNumber;
890}
891
892impl StoredVersion for StoredObject {
893    fn stored_version(&self) -> SequenceNumber {
894        self.version()
895    }
896}
897
898impl StoredVersion for ObjectOrTombstone {
899    fn stored_version(&self) -> SequenceNumber {
900        stored_version(self)
901    }
902}
903
904/// Serve exactly `version` with `at_checkpoint`. `version_at_checkpoint` is the object's version
905/// at the end of the checkpoint (see
906/// [`crate::reader::StateReader::get_object_version_at_checkpoint`]); a version above it was
907/// written after the checkpoint. If there is none, [`VersionRead::NoVersionYet`]: the object
908/// did not exist yet, or this node pruned its index history.
909///
910/// The read is refused unless the `at_checkpoint` lower bound accepts the checkpoint, and then
911/// the checkpoint's end state is intact. So if `version_at_checkpoint` has no live object, it is
912/// a deletion or wrap, or the version the rpc index records for one (see
913/// [`newest_version_written_by`]), and the answer is `NOT_FOUND`. A version below it that has no
914/// live object may have been pruned.
915fn version_at_checkpoint<T>(
916    version: SequenceNumber,
917    version_at_checkpoint: Option<SequenceNumber>,
918    get_object_by_key: impl FnOnce(SequenceNumber) -> Result<Option<T>, RpcError>,
919) -> Result<VersionRead<T>, RpcError> {
920    Ok(match version_at_checkpoint {
921        Some(version_at_checkpoint) if version < version_at_checkpoint => {
922            VersionRead::or_missing(get_object_by_key(version)?)
923        }
924        Some(version_at_checkpoint) if version == version_at_checkpoint => {
925            VersionRead::or_not_found(get_object_by_key(version)?)
926        }
927        Some(_) => VersionRead::NotFound,
928        None => VersionRead::NoVersionYet,
929    })
930}
931
932/// Serve `max_version` with `at_checkpoint`: select the object's newest version at or below
933/// `max_version` written up to the highest indexed checkpoint H, and answer
934/// [`VersionRead::NotFound`] if it was written after the checkpoint, or if it deleted or wrapped
935/// the object, and [`VersionRead::NoVersionYet`] if the version index records no version of the
936/// object as of the checkpoint. `version_at_checkpoint` is the object's version at the end of the
937/// checkpoint (see
938/// [`crate::reader::StateReader::get_object_version_at_checkpoint`]), and `version_at_height`
939/// reads its version at the end of H, needed only when `max_version` is at or above
940/// `version_at_checkpoint`. A version above the object's version at the end of a checkpoint was
941/// written after it. [`VersionRead::Missing`] if the object store has no live version at or below
942/// `max_version` where the selection needs one, unless the object is live at
943/// `version_at_checkpoint`: the read is refused unless the `at_checkpoint` lower bound accepts the
944/// checkpoint, and then this node holds that version, so a scan from `max_version` at or above it
945/// that finds no live version stopped at a deletion or wrap above it, written after the
946/// checkpoint. Read with tombstones (see [`select`]), a removal written by the checkpoint selects
947/// its tombstone.
948fn max_version_at_checkpoint<T: StoredVersion>(
949    max_version: SequenceNumber,
950    version_at_checkpoint: Option<SequenceNumber>,
951    version_at_height: impl FnOnce() -> Result<Option<SequenceNumber>, RpcError>,
952    get_object_by_key: impl Fn(SequenceNumber) -> Result<Option<T>, RpcError>,
953    get_object_lt_or_eq_version: impl FnOnce(SequenceNumber) -> Result<Option<T>, RpcError>,
954) -> Result<VersionRead<T>, RpcError> {
955    let Some(version_at_checkpoint) = version_at_checkpoint else {
956        // The object did not exist yet, or this node pruned its index history.
957        return Ok(VersionRead::NoVersionYet);
958    };
959    if max_version < version_at_checkpoint {
960        // Every version at or below `max_version` was written by the checkpoint.
961        return Ok(VersionRead::or_missing(get_object_lt_or_eq_version(
962            max_version,
963        )?));
964    }
965    let selected = newest_version_written_by(
966        max_version,
967        version_at_height()?,
968        &get_object_by_key,
969        get_object_lt_or_eq_version,
970    )?;
971    // A live version is never between the version index's record of a removal and the removal's
972    // tombstone (see `newest_version_written_by`), so comparing it with `version_at_checkpoint`
973    // tells whether it was written after the checkpoint even when that is such a record.
974    Ok(match selected {
975        VersionRead::Selected(item) if item.stored_version() > version_at_checkpoint => {
976            VersionRead::NotFound
977        }
978        VersionRead::Missing if get_object_by_key(version_at_checkpoint)?.is_some() => {
979            VersionRead::NotFound
980        }
981        selected => selected,
982    })
983}
984
985/// The newest version of an object at or below `max_version` among those written at or before a
986/// checkpoint, [`VersionRead::NoVersionYet`] if the version index records no version of it, or
987/// [`VersionRead::NotFound`] if that version deleted or wrapped it. `version_at_checkpoint` is
988/// the object's version at the end of the checkpoint; every version above it was written after
989/// the checkpoint.
990///
991/// Below `version_at_checkpoint`, `max_version` selects the newest version at or below it, and
992/// the read is [`VersionRead::Missing`] if the object store has no live one. At or above it, the
993/// object's state at `version_at_checkpoint` answers: the object if it is live there. If it is
994/// not, the object was deleted or wrapped by the checkpoint, but the version index can record
995/// that removal below the version of its tombstone in the object store: for a transaction with V1
996/// effects, the index records `TransactionEffectsAPI::lamport_version`, which V1 effects recompute
997/// from the modified objects alone, while the tombstone sits at the version the transaction
998/// executed at, which also counts its read-only inputs. No version lies between the two, so the
999/// newest version at or below `max_version` answers if it is below `version_at_checkpoint` (the
1000/// removal came after `max_version`), and nothing does if the scan finds a version above it,
1001/// which was written after the checkpoint. A scan of live objects that finds no live version
1002/// either stopped at the tombstone or found the version before the removal pruned, so the read is
1003/// [`VersionRead::Missing`].
1004fn newest_version_written_by<T: StoredVersion>(
1005    max_version: SequenceNumber,
1006    version_at_checkpoint: Option<SequenceNumber>,
1007    get_object_by_key: impl FnOnce(SequenceNumber) -> Result<Option<T>, RpcError>,
1008    get_object_lt_or_eq_version: impl FnOnce(SequenceNumber) -> Result<Option<T>, RpcError>,
1009) -> Result<VersionRead<T>, RpcError> {
1010    let Some(version_at_checkpoint) = version_at_checkpoint else {
1011        return Ok(VersionRead::NoVersionYet);
1012    };
1013    if max_version < version_at_checkpoint {
1014        return Ok(VersionRead::or_missing(get_object_lt_or_eq_version(
1015            max_version,
1016        )?));
1017    }
1018    if let Some(item) = get_object_by_key(version_at_checkpoint)? {
1019        return Ok(VersionRead::Selected(item));
1020    }
1021    Ok(match get_object_lt_or_eq_version(max_version)? {
1022        Some(item) if item.stored_version() < version_at_checkpoint => VersionRead::Selected(item),
1023        Some(_) => VersionRead::NotFound,
1024        None => VersionRead::Missing,
1025    })
1026}
1027
1028#[cfg(test)]
1029mod tests {
1030    use std::cell::Cell;
1031    use std::collections::BTreeMap;
1032
1033    use sui_types::base_types::ObjectDigest;
1034    use sui_types::base_types::ObjectID;
1035    use sui_types::base_types::SequenceNumber;
1036    use sui_types::base_types::SuiAddress;
1037    use sui_types::digests::TransactionDigest;
1038    use sui_types::effects::TransactionEffects;
1039    use sui_types::effects::TransactionEffectsAPI;
1040    use sui_types::execution_status::ExecutionStatus;
1041    use sui_types::gas::GasCostSummary;
1042    use sui_types::object::Object as StoredObject;
1043    use sui_types::object::Owner;
1044    use sui_types::storage::ObjectOrTombstone;
1045
1046    use sui_rpc::proto::sui::rpc::v2::Object;
1047    use sui_sdk_types::Address;
1048
1049    use super::LatestVersion;
1050    use super::ObjectRead;
1051    use super::ObjectReads;
1052    use super::ObjectSelector;
1053    use super::VersionRead;
1054    use super::answer_missing_versions;
1055    use super::max_version_at_checkpoint;
1056    use super::read_object;
1057    use super::version_at_checkpoint;
1058    use crate::RpcError;
1059    use crate::ledger_history::object_versions::ObjectRemovalKind;
1060    use crate::ledger_history::query_options::assert_below_serving_floor_error;
1061    use crate::reader::AtCheckpointUpperBound;
1062
1063    /// V1 effects of a transaction that deletes or wraps `object`, modified at
1064    /// `object_modified_at`, paying with `gas` modified at `gas_modified_at`, and executed at
1065    /// `executed_at`, which also counts read-only inputs the effects do not list.
1066    fn v1_removal(
1067        object: ObjectID,
1068        object_modified_at: u64,
1069        gas: ObjectID,
1070        gas_modified_at: u64,
1071        executed_at: u64,
1072        wrap: bool,
1073    ) -> TransactionEffects {
1074        let executed_at = SequenceNumber::from_u64(executed_at);
1075        let removed = if wrap {
1076            (object, executed_at, ObjectDigest::OBJECT_DIGEST_WRAPPED)
1077        } else {
1078            (object, executed_at, ObjectDigest::OBJECT_DIGEST_DELETED)
1079        };
1080        let (deleted, wrapped) = if wrap {
1081            (vec![], vec![removed])
1082        } else {
1083            (vec![removed], vec![])
1084        };
1085        TransactionEffects::new_from_execution_v1(
1086            ExecutionStatus::Success,
1087            0,
1088            GasCostSummary::default(),
1089            vec![
1090                (object, SequenceNumber::from_u64(object_modified_at)),
1091                (gas, SequenceNumber::from_u64(gas_modified_at)),
1092            ],
1093            vec![],
1094            TransactionDigest::random(),
1095            vec![],
1096            vec![],
1097            vec![],
1098            deleted,
1099            vec![],
1100            wrapped,
1101            (
1102                (gas, executed_at, ObjectDigest::random()),
1103                Owner::AddressOwner(SuiAddress::ZERO),
1104            ),
1105            None,
1106            vec![],
1107        )
1108    }
1109
1110    /// One of the object's versions: the checkpoint that wrote it, whether the object is live at
1111    /// it, and the version the fullnode's rpc-store index records for it.
1112    struct Row {
1113        version: u64,
1114        checkpoint: u64,
1115        live: bool,
1116        indexed_as: u64,
1117    }
1118
1119    /// `max_version` with `at_checkpoint` against a model of the chain rule
1120    /// (`find_object_lt_or_eq_version` bounded by the checkpoints), with each removal at its
1121    /// tombstone version, over a lifecycle whose wrap and deletion have V1 effects. The
1122    /// fullnode's rpc-store index records a removal at `TransactionEffects::lamport_version`,
1123    /// while the object store holds its tombstone at the removed object's ref version; for V1
1124    /// effects the first is recomputed from the modified objects alone, so it is lower. The
1125    /// object store also holds versions written above the highest indexed checkpoint, which
1126    /// must not count.
1127    ///
1128    /// For V1 removals this differs from Postgres `obj_versions`, which records the
1129    /// removal at the recomputed lamport version: for a `max_version` at or above that version
1130    /// and below the tombstone, Postgres answers that the object does not exist, while this read
1131    /// returns the version before the removal if that version was written by `at_checkpoint`
1132    /// (and nothing otherwise), as the chain does.
1133    #[test]
1134    fn max_version_at_checkpoint_follows_chain_rule() {
1135        let id = ObjectID::random();
1136        let gas = ObjectID::random();
1137        let wrap = v1_removal(id, 5, gas, 7, 1001, true);
1138        let delete = v1_removal(id, 2500, gas, 2400, 3001, false);
1139        let removal = |effects: &TransactionEffects| {
1140            let [(_, tombstone)] = effects.all_tombstones()[..] else {
1141                panic!("expected one tombstone");
1142            };
1143            let indexed_as = effects.lamport_version();
1144            assert!(indexed_as < tombstone, "{indexed_as} < {tombstone}");
1145            (tombstone.value(), indexed_as.value())
1146        };
1147        let (wrapped_at, wrap_indexed_as) = removal(&wrap);
1148        let (deleted_at, delete_indexed_as) = removal(&delete);
1149        assert_eq!((wrapped_at, wrap_indexed_as), (1001, 8));
1150        assert_eq!((deleted_at, delete_indexed_as), (3001, 2501));
1151
1152        let live = |version, checkpoint| Row {
1153            version,
1154            checkpoint,
1155            live: true,
1156            indexed_as: version,
1157        };
1158        let removed = |(version, indexed_as), checkpoint| Row {
1159            version,
1160            checkpoint,
1161            live: false,
1162            indexed_as,
1163        };
1164        let lifecycle = [
1165            live(3, 1),
1166            live(5, 2),
1167            removed((wrapped_at, wrap_indexed_as), 3),
1168            live(2000, 4),
1169            live(2500, 6),
1170            removed((deleted_at, delete_indexed_as), 7),
1171        ];
1172        let objects: BTreeMap<SequenceNumber, Option<StoredObject>> = lifecycle
1173            .iter()
1174            .map(|row| {
1175                let version = SequenceNumber::from_u64(row.version);
1176                let object = row.live.then(|| {
1177                    StoredObject::with_id_owner_version_for_testing(
1178                        id,
1179                        version,
1180                        Owner::AddressOwner(SuiAddress::ZERO),
1181                    )
1182                });
1183                (version, object)
1184            })
1185            .collect();
1186        let indexed_version_at = |checkpoint: u64| {
1187            lifecycle
1188                .iter()
1189                .rfind(|row| row.checkpoint <= checkpoint)
1190                .map(|row| SequenceNumber::from_u64(row.indexed_as))
1191        };
1192        let read = |max_version: u64, checkpoint: u64, highest_indexed: u64| {
1193            let read = max_version_at_checkpoint(
1194                SequenceNumber::from_u64(max_version),
1195                indexed_version_at(checkpoint),
1196                || Ok(indexed_version_at(highest_indexed)),
1197                |version| Ok(objects.get(&version).cloned().flatten()),
1198                |version| {
1199                    Ok(objects
1200                        .range(..=version)
1201                        .next_back()
1202                        .and_then(|(_, object)| object.clone()))
1203                },
1204            )
1205            .unwrap();
1206            match read {
1207                VersionRead::Selected(object) => Ok(object.version().value()),
1208                VersionRead::NotFound => Err("not found"),
1209                VersionRead::NoVersionYet | VersionRead::Missing => Err("missing"),
1210            }
1211        };
1212        // The newest version at or below `max_version` written up to `highest_indexed`, or "not
1213        // found" if it was written after `checkpoint`, or "missing" if there is no such version
1214        // or the object had no version as of `checkpoint`, which the read cannot tell from index
1215        // history this node pruned. Removals sit at their tombstone versions, not at
1216        // `indexed_as`. A selected removal is "not found" by the chain rule, but the object
1217        // store's reads hide tombstones, so the read can only tell it apart from a pruned version
1218        // when it was written after `checkpoint` and the object is live at the end of
1219        // `checkpoint`; otherwise either answer (`None`) is accepted, never an object.
1220        let expected = |max_version: u64, checkpoint: u64, highest_indexed: u64| {
1221            let Some(at_checkpoint) = lifecycle.iter().rfind(|row| row.checkpoint <= checkpoint)
1222            else {
1223                return Some(Err("missing"));
1224            };
1225            let Some(selected) = lifecycle
1226                .iter()
1227                .rfind(|row| row.version <= max_version && row.checkpoint <= highest_indexed)
1228            else {
1229                return Some(Err("missing"));
1230            };
1231            if selected.live && selected.checkpoint <= checkpoint {
1232                Some(Ok(selected.version))
1233            } else if selected.live || (selected.checkpoint > checkpoint && at_checkpoint.live) {
1234                Some(Err("not found"))
1235            } else {
1236                None
1237            }
1238        };
1239
1240        let mut max_versions: Vec<u64> = (0..=12).collect();
1241        for row in &lifecycle {
1242            max_versions.extend([
1243                row.version - 1,
1244                row.version,
1245                row.version + 1,
1246                row.indexed_as,
1247            ]);
1248        }
1249        max_versions.extend([1500, u64::MAX]);
1250        for highest_indexed in 0..=8 {
1251            for checkpoint in 0..=highest_indexed {
1252                for &max_version in &max_versions {
1253                    let actual = read(max_version, checkpoint, highest_indexed);
1254                    let context = format!(
1255                        "max_version {max_version} at_checkpoint {checkpoint} \
1256                         highest indexed {highest_indexed}"
1257                    );
1258                    match expected(max_version, checkpoint, highest_indexed) {
1259                        Some(expected) => assert_eq!(actual, expected, "{context}"),
1260                        None => assert!(
1261                            matches!(actual, Err("not found" | "missing")),
1262                            "{context}: {actual:?}"
1263                        ),
1264                    }
1265                }
1266            }
1267        }
1268
1269        // A newer version at or below `max_version` written after the checkpoint is selected,
1270        // so the read finds nothing rather than an older version.
1271        assert_eq!(read(5, 1, 8), Err("not found"));
1272        assert_eq!(read(5, 2, 8), Ok(5));
1273        // A version above the highest indexed checkpoint does not count.
1274        assert_eq!(read(2500, 4, 5), Ok(2000));
1275        assert_eq!(read(2500, 4, 6), Err("not found"));
1276        // Between a V1 removal's indexed version and its tombstone, the version before it is
1277        // the newest (Postgres answers that the object does not exist), and at or above the
1278        // tombstone nothing is, which the read reports as missing: it cannot tell the wrap's
1279        // tombstone from a pruned version.
1280        assert_eq!(read(1000, 3, 8), Ok(5));
1281        assert_eq!(read(1001, 3, 8), Err("missing"));
1282        // A deletion written after the checkpoint, of the version live at its end, is not found
1283        // even though the read sees no live version at or below `max_version`.
1284        assert_eq!(read(deleted_at, 6, 8), Err("not found"));
1285        assert_eq!(read(u64::MAX, 6, 8), Err("not found"));
1286    }
1287
1288    fn assert_not_found(result: Result<Object, RpcError>) {
1289        let status = result.unwrap_err().into_status_proto();
1290        assert_eq!(status.code, tonic::Code::NotFound as i32, "{status:?}");
1291    }
1292
1293    fn version(version: u64) -> ObjectSelector {
1294        ObjectSelector::Version {
1295            version,
1296            at_checkpoint: None,
1297        }
1298    }
1299
1300    fn max_version(max_version: u64) -> ObjectSelector {
1301        ObjectSelector::MaxVersion {
1302            max_version,
1303            at_checkpoint: None,
1304        }
1305    }
1306
1307    /// Answer one read that found its version missing, on a node with `objects_lower_bound`
1308    /// whose object's latest version is `latest`, live.
1309    fn answer_missing(
1310        selector: ObjectSelector,
1311        objects_lower_bound: u64,
1312        latest: Option<u64>,
1313    ) -> Result<Object, RpcError> {
1314        answer_missing_with_removal(selector, objects_lower_bound, latest, false)
1315    }
1316
1317    /// [`answer_missing`] when the object's latest version is a deletion or wrap if `removed`.
1318    fn answer_missing_with_removal(
1319        selector: ObjectSelector,
1320        objects_lower_bound: u64,
1321        latest: Option<u64>,
1322        removed: bool,
1323    ) -> Result<Object, RpcError> {
1324        let id = Address::ZERO;
1325        let [result] = answer_missing_versions(
1326            &[(id, selector)],
1327            vec![Ok(None)],
1328            || Ok(objects_lower_bound),
1329            |_| {
1330                latest.map(|version| LatestVersion {
1331                    version: SequenceNumber::from_u64(version),
1332                    removed,
1333                })
1334            },
1335        )
1336        .unwrap()
1337        .try_into()
1338        .unwrap();
1339        result
1340    }
1341
1342    /// A missing version is `NOT_FOUND` on a node that holds every version. Otherwise a node whose
1343    /// object lower bound is above 0 may have pruned it, and refuses the read with that lower
1344    /// bound.
1345    #[test]
1346    fn missing_versions_are_refused_on_pruned_nodes() {
1347        const FLOOR: u64 = 42;
1348        // A version below the latest live one, read exactly or as a `max_version`.
1349        assert_below_serving_floor_error(
1350            answer_missing(version(5), FLOOR, Some(10)).unwrap_err(),
1351            FLOOR,
1352        );
1353        assert_below_serving_floor_error(
1354            answer_missing(max_version(5), FLOOR, Some(10)).unwrap_err(),
1355            FLOOR,
1356        );
1357        // An object with no live version left, or none ever.
1358        assert_below_serving_floor_error(
1359            answer_missing(version(5), FLOOR, None).unwrap_err(),
1360            FLOOR,
1361        );
1362        assert_below_serving_floor_error(
1363            answer_missing(max_version(u64::MAX), FLOOR, None).unwrap_err(),
1364            FLOOR,
1365        );
1366        // With `at_checkpoint`, by the same rule.
1367        let at_checkpoint = ObjectSelector::Version {
1368            version: 5,
1369            at_checkpoint: Some(100),
1370        };
1371        assert_below_serving_floor_error(
1372            answer_missing(at_checkpoint, FLOOR, Some(10)).unwrap_err(),
1373            FLOOR,
1374        );
1375
1376        // An exact version is refused whatever the latest version: one above it is `NOT_FOUND`
1377        // before the read is left to `missing_version_error` (see `exact_version_after_miss`).
1378        assert_below_serving_floor_error(
1379            answer_missing(version(10), FLOOR, Some(10)).unwrap_err(),
1380            FLOOR,
1381        );
1382
1383        // A node that was neither pruned nor restored holds every version.
1384        for selector in [version(5), version(11), max_version(5), at_checkpoint] {
1385            for latest in [None, Some(10)] {
1386                assert_not_found(answer_missing(selector, 0, latest));
1387            }
1388        }
1389    }
1390
1391    /// An exact version above the object's latest version, live or a removal, is `NOT_FOUND`.
1392    /// The latest version is read after the miss, so a version written between the two reads is
1393    /// read again and served, rather than left missing (and refused as pruned).
1394    #[test]
1395    fn exact_version_misses_check_the_latest_version_after_the_miss() {
1396        let id = ObjectID::random();
1397        let latest = |version: u64, removed: bool| LatestVersion {
1398            version: SequenceNumber::from_u64(version),
1399            removed,
1400        };
1401        let answer = |version: u64, latest: Option<LatestVersion>, found_again: bool| {
1402            let read_again = std::cell::Cell::new(false);
1403            let read = super::exact_version_after_miss(
1404                SequenceNumber::from_u64(version),
1405                || latest,
1406                || {
1407                    read_again.set(true);
1408                    Ok(if found_again {
1409                        ObjectRead::Live(StoredObject::with_id_owner_version_for_testing(
1410                            id,
1411                            SequenceNumber::from_u64(version),
1412                            Owner::AddressOwner(SuiAddress::ZERO),
1413                        ))
1414                    } else {
1415                        ObjectRead::Missing
1416                    })
1417                },
1418            )
1419            .unwrap();
1420            let answer = match read {
1421                ObjectRead::Live(object) => Ok(object.version().value()),
1422                ObjectRead::NotFound(None) => Err("not found"),
1423                ObjectRead::Missing => Err("missing"),
1424                other => panic!("unexpected {other:?}"),
1425            };
1426            (answer, read_again.get())
1427        };
1428        // Not written yet, above a live version or a removal: no second read.
1429        assert_eq!(
1430            answer(11, Some(latest(10, false)), true),
1431            (Err("not found"), false)
1432        );
1433        assert_eq!(
1434            answer(11, Some(latest(10, true)), true),
1435            (Err("not found"), false)
1436        );
1437        // At or below the latest version and still absent: possibly pruned.
1438        assert_eq!(
1439            answer(5, Some(latest(10, false)), false),
1440            (Err("missing"), true)
1441        );
1442        // No version at all.
1443        assert_eq!(answer(5, None, true), (Err("missing"), false));
1444        // Version 11 is written between the miss and the read of the latest version.
1445        assert_eq!(answer(11, Some(latest(11, false)), true), (Ok(11), true));
1446    }
1447
1448    /// On a pruned node, a `max_version` read without `at_checkpoint` that finds no live version
1449    /// and resolves to the object's latest version, a deletion or wrap at or below it, is
1450    /// `NOT_FOUND` (the latest version includes changes not committed yet). A `max_version` read
1451    /// with `at_checkpoint`, or one below the removal, is still refused: the version it selects
1452    /// may be an older one, pruned.
1453    #[test]
1454    fn missing_versions_resolving_to_the_latest_removal_are_not_found() {
1455        const FLOOR: u64 = 42;
1456        let removed_at_10 =
1457            |selector: ObjectSelector| answer_missing_with_removal(selector, FLOOR, Some(10), true);
1458        assert_not_found(removed_at_10(max_version(10)));
1459        assert_not_found(removed_at_10(max_version(u64::MAX)));
1460        assert_below_serving_floor_error(removed_at_10(max_version(9)).unwrap_err(), FLOOR);
1461        // A live latest version at or below `max_version` decides nothing.
1462        assert_below_serving_floor_error(
1463            answer_missing_with_removal(max_version(12), FLOOR, Some(10), false).unwrap_err(),
1464            FLOOR,
1465        );
1466        // With `at_checkpoint`, the read counts only versions written by the checkpoint, and the
1467        // removal may have been written after it.
1468        let at_checkpoint = ObjectSelector::MaxVersion {
1469            max_version: 12,
1470            at_checkpoint: Some(5),
1471        };
1472        assert_below_serving_floor_error(removed_at_10(at_checkpoint).unwrap_err(), FLOOR);
1473    }
1474
1475    /// In a batch, a missing version fails only its own item, the lower bound is read once, and
1476    /// only if some read found a version missing.
1477    #[test]
1478    fn missing_versions_fail_only_their_own_batch_items() {
1479        let missing = Address::new([1; 32]);
1480        let found = Address::new([2; 32]);
1481        let requests = [
1482            (missing, version(5)),
1483            (found, version(3)),
1484            (found, max_version(9)),
1485        ];
1486        let mut lower_bound_reads = 0;
1487        let results = answer_missing_versions(
1488            &requests,
1489            vec![
1490                Ok(None),
1491                Ok(Some(Object::default())),
1492                Ok(Some(Object::default())),
1493            ],
1494            || {
1495                lower_bound_reads += 1;
1496                Ok(7)
1497            },
1498            |object_id| {
1499                assert_eq!(object_id, missing);
1500                Some(LatestVersion {
1501                    version: SequenceNumber::from_u64(10),
1502                    removed: false,
1503                })
1504            },
1505        )
1506        .unwrap();
1507        assert_eq!(lower_bound_reads, 1);
1508        let [refused, served, served_max] = results.try_into().unwrap();
1509        assert_below_serving_floor_error(refused.unwrap_err(), 7);
1510        assert_eq!(served.unwrap(), Object::default());
1511        assert_eq!(served_max.unwrap(), Object::default());
1512
1513        let results = answer_missing_versions(
1514            &requests[1..],
1515            vec![
1516                Ok(Some(Object::default())),
1517                Err(requests[2].1.not_found(found).into()),
1518            ],
1519            || panic!("no read found a version missing"),
1520            |_| panic!("no read found a version missing"),
1521        )
1522        .unwrap();
1523        let [served, not_found] = results.try_into().unwrap();
1524        assert_eq!(served.unwrap(), Object::default());
1525        assert_not_found(not_found);
1526    }
1527
1528    /// With `at_checkpoint`, a version written after the checkpoint and a deletion or wrap at the
1529    /// version the checkpoint ends with are `NOT_FOUND` whatever the node pruned. A version below
1530    /// that one with no live object may have been pruned, and so may the index history of an
1531    /// object the version index records no version of as of the checkpoint: the fullnode pruner
1532    /// retracts every index row of an object deleted or wrapped in a pruned checkpoint.
1533    #[test]
1534    fn at_checkpoint_visibility_misses_stay_not_found() {
1535        let id = ObjectID::random();
1536        let object = |version: u64| {
1537            StoredObject::with_id_owner_version_for_testing(
1538                id,
1539                SequenceNumber::from_u64(version),
1540                Owner::AddressOwner(SuiAddress::ZERO),
1541            )
1542        };
1543        let v = SequenceNumber::from_u64;
1544        let exact =
1545            |version: u64, version_at: Option<u64>, held: &[u64]| match version_at_checkpoint(
1546                v(version),
1547                version_at.map(v),
1548                |version| {
1549                    Ok(held
1550                        .contains(&version.value())
1551                        .then(|| object(version.value())))
1552                },
1553            )
1554            .unwrap()
1555            {
1556                VersionRead::Selected(object) => Ok(object.version().value()),
1557                VersionRead::NotFound => Err("not found"),
1558                VersionRead::NoVersionYet | VersionRead::Missing => Err("missing"),
1559            };
1560        // The object is live at 5 at the end of the checkpoint; this node pruned 3.
1561        assert_eq!(exact(5, Some(5), &[5, 7]), Ok(5));
1562        assert_eq!(exact(7, Some(5), &[5, 7]), Err("not found"));
1563        assert_eq!(exact(3, Some(5), &[5, 7]), Err("missing"));
1564        // The checkpoint ends with a deletion at 6.
1565        assert_eq!(exact(6, Some(6), &[5]), Err("not found"));
1566        // No index row as of the checkpoint: the object may not exist yet, or it was created at 2
1567        // and deleted at 3 in checkpoints this node pruned, index rows included.
1568        assert_eq!(exact(9, None, &[5, 7]), Err("missing"));
1569        assert_eq!(exact(2, None, &[]), Err("missing"));
1570
1571        // Versions 3, 5 and 7 written at checkpoints 1, 2 and 3, and a deletion at 9 written at
1572        // checkpoint 4; this node pruned 3 and 5 and holds the deletion's tombstone.
1573        let version_at = |checkpoint: u64| match checkpoint {
1574            0 => None,
1575            1 => Some(v(3)),
1576            2 => Some(v(5)),
1577            3 => Some(v(7)),
1578            _ => Some(v(9)),
1579        };
1580        let max = |max_version: u64, checkpoint: u64| match max_version_at_checkpoint(
1581            v(max_version),
1582            version_at(checkpoint),
1583            || Ok(version_at(4)),
1584            |version| Ok((version == v(7)).then(|| object(7))),
1585            |version| Ok((v(7)..v(9)).contains(&version).then(|| object(7))),
1586        )
1587        .unwrap()
1588        {
1589            VersionRead::Selected(object) => Ok(object.version().value()),
1590            VersionRead::NotFound => Err("not found"),
1591            VersionRead::NoVersionYet | VersionRead::Missing => Err("missing"),
1592        };
1593        // 7 is selected but was written after checkpoint 2.
1594        assert_eq!(max(8, 2), Err("not found"));
1595        // No index row as of checkpoint 0, which the read cannot tell from pruned index history.
1596        assert_eq!(max(8, 0), Err("missing"));
1597        assert_eq!(max(8, 3), Ok(7));
1598        // The deletion is selected but was written after checkpoint 3, where 7 is live.
1599        assert_eq!(max(9, 3), Err("not found"));
1600        assert_eq!(max(u64::MAX, 3), Err("not found"));
1601        // Selecting 5 needs a version this node pruned.
1602        assert_eq!(max(5, 3), Err("missing"));
1603        assert_eq!(max(5, 2), Err("missing"));
1604        // At checkpoint 4 the deletion is selected, which the object store's reads do not tell
1605        // apart from a pruned version.
1606        assert_eq!(max(9, 4), Err("missing"));
1607    }
1608
1609    /// `max_version` with `at_checkpoint`, read with tombstones over `lifecycle` as `select`
1610    /// reads it, with the index recording each version where the object store holds it. The
1611    /// selected item's version, and whether it is live.
1612    fn read_with_tombstones(
1613        lifecycle: &[Row],
1614        max_version: u64,
1615        checkpoint: u64,
1616        highest_indexed: u64,
1617    ) -> Option<(u64, bool)> {
1618        let id = ObjectID::random();
1619        let items: BTreeMap<SequenceNumber, ObjectOrTombstone> = lifecycle
1620            .iter()
1621            .map(|row| {
1622                let version = SequenceNumber::from_u64(row.version);
1623                let item = if row.live {
1624                    ObjectOrTombstone::Object(StoredObject::with_id_owner_version_for_testing(
1625                        id,
1626                        version,
1627                        Owner::AddressOwner(SuiAddress::ZERO),
1628                    ))
1629                } else {
1630                    ObjectOrTombstone::Tombstone((id, version, ObjectDigest::OBJECT_DIGEST_DELETED))
1631                };
1632                (version, item)
1633            })
1634            .collect();
1635        let version_at = |checkpoint: u64| {
1636            let row = lifecycle.iter().rfind(|row| row.checkpoint <= checkpoint)?;
1637            Some(SequenceNumber::from_u64(row.version))
1638        };
1639        let read = max_version_at_checkpoint(
1640            SequenceNumber::from_u64(max_version),
1641            version_at(checkpoint),
1642            || Ok(version_at(highest_indexed)),
1643            |version| Ok(items.get(&version).cloned()),
1644            |version| {
1645                Ok(items
1646                    .range(..=version)
1647                    .next_back()
1648                    .map(|(_, item)| item.clone()))
1649            },
1650        )
1651        .unwrap();
1652        match read {
1653            VersionRead::Selected(ObjectOrTombstone::Object(object)) => {
1654                Some((object.version().value(), true))
1655            }
1656            VersionRead::Selected(ObjectOrTombstone::Tombstone((_, version, _))) => {
1657                Some((version.value(), false))
1658            }
1659            VersionRead::NotFound | VersionRead::NoVersionYet | VersionRead::Missing => None,
1660        }
1661    }
1662
1663    /// Read with tombstones, `max_version` with `at_checkpoint` selects the removal the read
1664    /// resolves to, only when that removal was written by the checkpoint, and otherwise the same
1665    /// live version or nothing as the read of live objects.
1666    #[test]
1667    fn max_version_at_checkpoint_selects_removals_written_by_the_checkpoint() {
1668        let row = |version, checkpoint, live| Row {
1669            version,
1670            checkpoint,
1671            live,
1672            indexed_as: version,
1673        };
1674        // Created, mutated, wrapped, unwrapped, mutated, deleted.
1675        let lifecycle = [
1676            row(3, 1, true),
1677            row(5, 2, true),
1678            row(6, 3, false),
1679            row(8, 4, true),
1680            row(9, 6, true),
1681            row(10, 7, false),
1682        ];
1683        // The newest version at or below `max_version` written up to `highest_indexed`, live or
1684        // removed, unless it was written after `checkpoint`.
1685        let expected = |max_version: u64, checkpoint: u64, highest_indexed: u64| {
1686            lifecycle
1687                .iter()
1688                .rfind(|row| row.version <= max_version && row.checkpoint <= highest_indexed)
1689                .filter(|row| row.checkpoint <= checkpoint)
1690                .map(|row| (row.version, row.live))
1691        };
1692        for highest_indexed in 0..=8 {
1693            for checkpoint in 0..=highest_indexed {
1694                for max_version in (0..=12).chain([u64::MAX]) {
1695                    assert_eq!(
1696                        read_with_tombstones(&lifecycle, max_version, checkpoint, highest_indexed),
1697                        expected(max_version, checkpoint, highest_indexed),
1698                        "max_version {max_version} at_checkpoint {checkpoint} \
1699                         highest indexed {highest_indexed}",
1700                    );
1701                }
1702            }
1703        }
1704        // The wrap at version 6 answers at checkpoint 3, but not at checkpoint 2, before it.
1705        assert_eq!(read_with_tombstones(&lifecycle, 7, 3, 8), Some((6, false)));
1706        assert_eq!(read_with_tombstones(&lifecycle, 7, 2, 8), None);
1707    }
1708
1709    /// How an object changed at one of its versions.
1710    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
1711    enum Change {
1712        Live,
1713        Wrapped,
1714        Deleted,
1715    }
1716
1717    /// An object's history as `(version, checkpoint that wrote it, change)`, with the version
1718    /// index recording each removal at its tombstone's version, and the reads made of it counted.
1719    struct HistoryReads<'a> {
1720        id: ObjectID,
1721        history: &'a [(u64, u64, Change)],
1722        reads: Cell<usize>,
1723    }
1724
1725    impl HistoryReads<'_> {
1726        fn item(&self, &(version, _, change): &(u64, u64, Change)) -> ObjectOrTombstone {
1727            let version = SequenceNumber::from_u64(version);
1728            match change {
1729                Change::Live => {
1730                    ObjectOrTombstone::Object(StoredObject::with_id_owner_version_for_testing(
1731                        self.id,
1732                        version,
1733                        Owner::AddressOwner(SuiAddress::ZERO),
1734                    ))
1735                }
1736                Change::Wrapped => ObjectOrTombstone::Tombstone((
1737                    self.id,
1738                    version,
1739                    ObjectDigest::OBJECT_DIGEST_WRAPPED,
1740                )),
1741                Change::Deleted => ObjectOrTombstone::Tombstone((
1742                    self.id,
1743                    version,
1744                    ObjectDigest::OBJECT_DIGEST_DELETED,
1745                )),
1746            }
1747        }
1748
1749        /// The change `pick` finds, counted as one read.
1750        fn read(
1751            &self,
1752            pick: impl Fn(&(u64, u64, Change)) -> bool,
1753            newest: bool,
1754        ) -> Option<ObjectOrTombstone> {
1755            self.reads.set(self.reads.get() + 1);
1756            let found = if newest {
1757                self.history.iter().rfind(|change| pick(change))
1758            } else {
1759                self.history.iter().find(|change| pick(change))
1760            };
1761            found.map(|change| self.item(change))
1762        }
1763    }
1764
1765    /// What a read of a [`HistoryReads`] item returns: the item itself with tombstones, or the live
1766    /// object, where a removal reads as `None`.
1767    trait FromItem: Sized {
1768        fn from_item(item: ObjectOrTombstone) -> Option<Self>;
1769    }
1770
1771    impl FromItem for ObjectOrTombstone {
1772        fn from_item(item: ObjectOrTombstone) -> Option<Self> {
1773            Some(item)
1774        }
1775    }
1776
1777    impl FromItem for StoredObject {
1778        fn from_item(item: ObjectOrTombstone) -> Option<Self> {
1779            match item {
1780                ObjectOrTombstone::Object(object) => Some(object),
1781                ObjectOrTombstone::Tombstone(_) => None,
1782            }
1783        }
1784    }
1785
1786    /// [`ObjectReads`] over a [`HistoryReads`], of live objects (`T` = `StoredObject`) or with
1787    /// tombstones (`T` = `ObjectOrTombstone`).
1788    struct Reads<'a, T> {
1789        history: HistoryReads<'a>,
1790        item: std::marker::PhantomData<T>,
1791    }
1792
1793    impl<'a, T> Reads<'a, T> {
1794        fn new(id: ObjectID, history: &'a [(u64, u64, Change)]) -> Self {
1795            Self {
1796                history: HistoryReads {
1797                    id,
1798                    history,
1799                    reads: Cell::new(0),
1800                },
1801                item: std::marker::PhantomData,
1802            }
1803        }
1804
1805        fn count(&self) -> usize {
1806            self.history.reads.get()
1807        }
1808    }
1809
1810    impl<T: FromItem + super::StoredVersion> ObjectReads for Reads<'_, T> {
1811        type Item = T;
1812
1813        fn latest(&self, _id: ObjectID) -> Result<Option<T>, RpcError> {
1814            Ok(self.history.read(|_| true, true).and_then(T::from_item))
1815        }
1816
1817        fn by_key(&self, _id: ObjectID, version: SequenceNumber) -> Result<Option<T>, RpcError> {
1818            Ok(self
1819                .history
1820                .read(|&(v, _, _)| v == version.value(), false)
1821                .and_then(T::from_item))
1822        }
1823
1824        fn lt_or_eq(&self, _id: ObjectID, version: SequenceNumber) -> Result<Option<T>, RpcError> {
1825            Ok(self
1826                .history
1827                .read(|&(v, _, _)| v <= version.value(), true)
1828                .and_then(T::from_item))
1829        }
1830
1831        fn version_at_checkpoint(
1832            &self,
1833            _id: ObjectID,
1834            checkpoint: u64,
1835            upper_bound: &AtCheckpointUpperBound,
1836        ) -> Result<Option<SequenceNumber>, RpcError> {
1837            upper_bound.check(checkpoint)?;
1838            Ok(self
1839                .history
1840                .read(|&(_, written_at, _)| written_at <= checkpoint, true)
1841                .map(|item| super::stored_version(&item)))
1842        }
1843    }
1844
1845    /// What [`read_object`] answered, with the reads it made: through live objects and with
1846    /// tombstones.
1847    #[derive(Debug, PartialEq, Eq)]
1848    enum Answer {
1849        Live(u64),
1850        NotFound,
1851        Removed(u64, ObjectRemovalKind),
1852        Missing,
1853    }
1854
1855    fn read_history(
1856        history: &[(u64, u64, Change)],
1857        selector: ObjectSelector,
1858        upper_bound: Option<&AtCheckpointUpperBound>,
1859    ) -> (Answer, [usize; 2]) {
1860        let id = ObjectID::random();
1861        let live = Reads::<StoredObject>::new(id, history);
1862        let with_tombstones = Reads::<ObjectOrTombstone>::new(id, history);
1863        let read = read_object(&live, &with_tombstones, id, selector, upper_bound).unwrap();
1864        let answer = match read {
1865            ObjectRead::Live(object) => Answer::Live(object.version().value()),
1866            ObjectRead::NotFound(None) => Answer::NotFound,
1867            ObjectRead::NotFound(Some(removal)) => Answer::Removed(removal.version, removal.kind),
1868            ObjectRead::Missing => Answer::Missing,
1869        };
1870        (answer, [live.count(), with_tombstones.count()])
1871    }
1872
1873    /// An `at_checkpoint` or exact-version read of an object that never existed costs one read;
1874    /// an `at_checkpoint` read learns it from the version index and never looks for a removal.
1875    /// The index cannot tell such an object from one whose index history this node pruned, so
1876    /// only `at_checkpoint` alone answers `NOT_FOUND`, and a `version` or `max_version` read with
1877    /// it is missing data. Without `at_checkpoint` there is no index to ask, so an exact version
1878    /// looks for a tombstone at that version, and a `max_version` makes its one read with
1879    /// tombstones.
1880    #[test]
1881    fn reads_of_objects_that_never_existed_look_for_no_removal() {
1882        let indexed = AtCheckpointUpperBound::new(5);
1883        assert_eq!(
1884            read_history(&[], ObjectSelector::AtCheckpoint(3), Some(&indexed)),
1885            (Answer::NotFound, [1, 0])
1886        );
1887        for selector in [
1888            ObjectSelector::Version {
1889                version: 3,
1890                at_checkpoint: Some(3),
1891            },
1892            ObjectSelector::MaxVersion {
1893                max_version: 3,
1894                at_checkpoint: Some(3),
1895            },
1896        ] {
1897            assert_eq!(
1898                read_history(&[], selector, Some(&indexed)),
1899                (Answer::Missing, [1, 0]),
1900                "{selector:?}"
1901            );
1902        }
1903        assert_eq!(
1904            read_history(&[], version(3), None),
1905            (Answer::Missing, [1, 1])
1906        );
1907        assert_eq!(
1908            read_history(&[], max_version(3), None),
1909            (Answer::Missing, [0, 1])
1910        );
1911    }
1912
1913    /// A read that resolves to a deletion or wrap answers `NOT_FOUND` describing it, including
1914    /// the reads whose live selection finds the version missing: an exact version, a version below
1915    /// the checkpoint's with `at_checkpoint`, and a `max_version` with or without
1916    /// `at_checkpoint`. A read that resolves to a version written after its checkpoint describes
1917    /// no removal.
1918    #[test]
1919    fn reads_resolving_to_removals_describe_them() {
1920        use Change::*;
1921        // Created at 3, wrapped at 4, unwrapped at 5 and deleted at 6, at checkpoints 1 to 4.
1922        let history = [(3, 1, Live), (4, 2, Wrapped), (5, 3, Live), (6, 4, Deleted)];
1923        let indexed = AtCheckpointUpperBound::new(4);
1924        let wrapped = Answer::Removed(4, ObjectRemovalKind::Wrapped);
1925        let deleted = Answer::Removed(6, ObjectRemovalKind::Deleted);
1926        let read = |selector, upper_bound| read_history(&history, selector, upper_bound).0;
1927        let with_at_checkpoint = |version, at_checkpoint| ObjectSelector::Version {
1928            version,
1929            at_checkpoint: Some(at_checkpoint),
1930        };
1931        let max_at_checkpoint = |max_version, at_checkpoint| ObjectSelector::MaxVersion {
1932            max_version,
1933            at_checkpoint: Some(at_checkpoint),
1934        };
1935
1936        assert_eq!(read(ObjectSelector::Latest, None), deleted);
1937        assert_eq!(read(version(4), None), wrapped);
1938        assert_eq!(read(version(6), None), deleted);
1939        assert_eq!(read(version(5), None), Answer::Live(5));
1940        assert_eq!(read(with_at_checkpoint(4, 3), Some(&indexed)), wrapped);
1941        assert_eq!(read(with_at_checkpoint(6, 4), Some(&indexed)), deleted);
1942        assert_eq!(
1943            read(ObjectSelector::AtCheckpoint(2), Some(&indexed)),
1944            wrapped
1945        );
1946        assert_eq!(
1947            read(ObjectSelector::AtCheckpoint(0), Some(&indexed)),
1948            Answer::NotFound
1949        );
1950        // `max_version` with `at_checkpoint`.
1951        assert_eq!(read(max_at_checkpoint(4, 2), Some(&indexed)), wrapped);
1952        assert_eq!(read(max_at_checkpoint(9, 4), Some(&indexed)), deleted);
1953        // Version 5 is selected but was written after checkpoint 2.
1954        assert_eq!(
1955            read(max_at_checkpoint(5, 2), Some(&indexed)),
1956            Answer::NotFound
1957        );
1958        assert_eq!(
1959            read(max_at_checkpoint(3, 2), Some(&indexed)),
1960            Answer::Live(3)
1961        );
1962
1963        // Without `at_checkpoint`, the newest entry at or below `max_version`, live or a tombstone,
1964        // decides, in one read with tombstones.
1965        assert_eq!(
1966            read_history(&history, max_version(4), None),
1967            (wrapped, [0, 1])
1968        );
1969        assert_eq!(
1970            read_history(&history, max_version(9), None),
1971            (deleted, [0, 1])
1972        );
1973        assert_eq!(
1974            read_history(&history, max_version(5), None),
1975            (Answer::Live(5), [0, 1])
1976        );
1977    }
1978
1979    /// With the versions before them pruned, `read_object` still resolves `max_version` reads
1980    /// with `at_checkpoint` K to a removal that is the object's version at the end of K: one
1981    /// wrapped by K and unwrapped after it, read between the wrap and the unwrap, and one deleted
1982    /// at K, read at or above the deletion.
1983    #[test]
1984    fn removals_ending_the_checkpoint_resolve_with_earlier_versions_pruned() {
1985        use Change::*;
1986        // Created at 3 (checkpoint 1, pruned), wrapped at 4, unwrapped at 5 and deleted at 6, at
1987        // checkpoints 2 to 4.
1988        let history = [(4, 2, Wrapped), (5, 3, Live), (6, 4, Deleted)];
1989        let indexed = AtCheckpointUpperBound::new(4);
1990        let read = |max_version, at_checkpoint| {
1991            read_history(
1992                &history,
1993                ObjectSelector::MaxVersion {
1994                    max_version,
1995                    at_checkpoint: Some(at_checkpoint),
1996                },
1997                Some(&indexed),
1998            )
1999            .0
2000        };
2001        let wrapped = Answer::Removed(4, ObjectRemovalKind::Wrapped);
2002        let deleted = Answer::Removed(6, ObjectRemovalKind::Deleted);
2003        assert_eq!(read(4, 2), wrapped);
2004        assert_eq!(read(6, 4), deleted);
2005        assert_eq!(read(u64::MAX, 4), deleted);
2006        // The unwrap is selected but was written after checkpoint 2.
2007        assert_eq!(read(5, 2), Answer::NotFound);
2008    }
2009
2010    /// A `max_version` read with `at_checkpoint` K of an object removed at K answers `NOT_FOUND`,
2011    /// with no removal described, when the newest version at or below `max_version` is a later
2012    /// removal: that removal was written after K. The live selection finds no live version there,
2013    /// and the selection with tombstones decides the answer.
2014    #[test]
2015    fn removed_at_the_checkpoint_and_removed_again_after_it_is_not_found() {
2016        use Change::*;
2017        // Created at 3, deleted at 4 (checkpoint 2), re-created at 5, deleted at 6 and re-created
2018        // at 7, at checkpoints 1 to 5.
2019        let history = [
2020            (3, 1, Live),
2021            (4, 2, Deleted),
2022            (5, 3, Live),
2023            (6, 4, Deleted),
2024            (7, 5, Live),
2025        ];
2026        let read = |history: &[(u64, u64, Change)], max_version, highest_indexed| {
2027            read_history(
2028                history,
2029                ObjectSelector::MaxVersion {
2030                    max_version,
2031                    at_checkpoint: Some(2),
2032                },
2033                Some(&AtCheckpointUpperBound::new(highest_indexed)),
2034            )
2035            .0
2036        };
2037        // The deletion at 6 is the newest version at or below 6, below the version at the height.
2038        assert_eq!(read(&history, 6, 5), Answer::NotFound);
2039        // The deletion at 6 is the object's version at the height.
2040        assert_eq!(read(&history[..4], 6, 4), Answer::NotFound);
2041        assert_eq!(read(&history[..4], u64::MAX, 4), Answer::NotFound);
2042        // The deletion at K itself still answers, described.
2043        assert_eq!(
2044            read(&history, 4, 5),
2045            Answer::Removed(4, ObjectRemovalKind::Deleted)
2046        );
2047    }
2048}
2049
2050#[cfg(test)]
2051mod version_without_history_tests {
2052    use sui_rpc::proto::sui::rpc::v2::get_object_result;
2053    use sui_types::base_types::{ObjectDigest, ObjectID, SequenceNumber, SuiAddress};
2054    use sui_types::object::Owner;
2055
2056    use super::*;
2057    use crate::reader::{NotServedHereCause, assert_not_served_here, assert_version_not_retained};
2058    use crate::stub_store::StubStore;
2059
2060    /// A store holding versions 1 and 2 of one object, and that object's id.
2061    fn store_with_two_versions(retains_object_version_history: bool) -> (RpcService, Address) {
2062        let id = ObjectID::new([1; ObjectID::LENGTH]);
2063        let owner = Owner::AddressOwner(SuiAddress::ZERO);
2064        let objects = [1, 2]
2065            .map(|version| {
2066                sui_types::object::Object::with_id_owner_version_for_testing(
2067                    id,
2068                    SequenceNumber::from_u64(version),
2069                    owner.clone(),
2070                )
2071            })
2072            .to_vec();
2073        let service = StubStore {
2074            objects,
2075            retains_object_version_history,
2076            ..StubStore::new()
2077        }
2078        .into_service();
2079        (service, id.into())
2080    }
2081
2082    /// A store without object version history holding `live` versions of one object and its
2083    /// tombstone at `removed_at`, and that object's id.
2084    fn store_with_removal(live: &[u64], removed_at: u64) -> (RpcService, Address) {
2085        let id = ObjectID::new([1; ObjectID::LENGTH]);
2086        let owner = Owner::AddressOwner(SuiAddress::ZERO);
2087        let objects = live
2088            .iter()
2089            .map(|&version| {
2090                sui_types::object::Object::with_id_owner_version_for_testing(
2091                    id,
2092                    SequenceNumber::from_u64(version),
2093                    owner.clone(),
2094                )
2095            })
2096            .collect();
2097        let service = StubStore {
2098            objects,
2099            tombstones: vec![(
2100                id,
2101                SequenceNumber::from_u64(removed_at),
2102                ObjectDigest::OBJECT_DIGEST_WRAPPED,
2103            )],
2104            retains_object_version_history: false,
2105            ..StubStore::new()
2106        }
2107        .into_service();
2108        (service, id.into())
2109    }
2110
2111    /// The `removedVersion` of `status`'s `OBJECT_REMOVED` detail, which must be `NOT_FOUND`.
2112    fn removed_version(status: &crate::proto::google::rpc::Status) -> Option<String> {
2113        assert_eq!(status.code, tonic::Code::NotFound as i32, "{status:?}");
2114        status
2115            .details
2116            .iter()
2117            .filter_map(|detail| detail.to_msg::<crate::proto::google::rpc::ErrorInfo>().ok())
2118            .find(|info| info.reason == ErrorReason::ObjectRemoved.as_str_name())
2119            .and_then(|info| info.metadata.get("removedVersion").cloned())
2120    }
2121
2122    fn request(object_id: Address, version: Option<u64>) -> GetObjectRequest {
2123        let mut request = GetObjectRequest::default();
2124        request.object_id = Some(object_id.to_string());
2125        request.version = version;
2126        request.read_mask = Some(FieldMask::from_str("object_id,version"));
2127        request
2128    }
2129
2130    fn version_of(response: Result<GetObjectResponse, RpcError>) -> u64 {
2131        response.unwrap().object.unwrap().version.unwrap()
2132    }
2133
2134    /// A node without object version history serves an object's latest version, by `version` or
2135    /// without one, answers `NotFound` for a version not written yet and for an object it holds
2136    /// no version of, and refuses every older version, including one it still stores.
2137    #[test]
2138    fn without_history_only_the_latest_version_is_served() {
2139        let (service, id) = store_with_two_versions(false);
2140
2141        assert_eq!(version_of(get_object(&service, request(id, None))), 2);
2142        assert_eq!(version_of(get_object(&service, request(id, Some(2)))), 2);
2143        assert_version_not_retained(get_object(&service, request(id, Some(1))).unwrap_err());
2144        let error = get_object(&service, request(id, Some(3))).unwrap_err();
2145        assert_eq!(error.into_status_proto().code, tonic::Code::NotFound as i32);
2146        let missing = Address::new([2; 32]);
2147        let error = get_object(&service, request(missing, Some(1))).unwrap_err();
2148        assert_eq!(error.into_status_proto().code, tonic::Code::NotFound as i32);
2149
2150        let mut batch = BatchGetObjectsRequest::default();
2151        batch.requests = vec![
2152            request(id, Some(1)),
2153            request(id, Some(2)),
2154            request(id, Some(3)),
2155            request(missing, Some(1)),
2156        ];
2157        batch.read_mask = Some(FieldMask::from_str("object_id,version"));
2158        let response = batch_get_objects(&service, batch).unwrap();
2159        let [older, latest, above_latest, never_existed] = response.objects.as_slice() else {
2160            panic!("expected four results in {response:?}");
2161        };
2162        let status_of = |result: &GetObjectResult| match &result.result {
2163            Some(get_object_result::Result::Error(status)) => status.clone(),
2164            _ => panic!("expected an error in {response:?}"),
2165        };
2166        assert_eq!(
2167            status_of(older).code,
2168            tonic::Code::OutOfRange as i32,
2169            "{response:?}"
2170        );
2171        assert!(
2172            matches!(
2173                &latest.result,
2174                Some(get_object_result::Result::Object(object)) if object.version == Some(2)
2175            ),
2176            "{response:?}"
2177        );
2178        assert_eq!(
2179            status_of(above_latest).code,
2180            tonic::Code::NotFound as i32,
2181            "{response:?}"
2182        );
2183        assert_eq!(
2184            status_of(never_existed).code,
2185            tonic::Code::NotFound as i32,
2186            "{response:?}"
2187        );
2188    }
2189
2190    /// A node with object version history serves any stored version and answers `NotFound` for
2191    /// one it does not store.
2192    #[test]
2193    fn with_history_any_stored_version_is_served() {
2194        let (service, id) = store_with_two_versions(true);
2195
2196        assert_eq!(version_of(get_object(&service, request(id, Some(1)))), 1);
2197        let error = get_object(&service, request(id, Some(3))).unwrap_err();
2198        assert_eq!(error.into_status_proto().code, tonic::Code::NotFound as i32);
2199    }
2200
2201    /// A node with object version history but without rpc indexes refuses every `max_version`
2202    /// read, with or without `at_checkpoint`, alone or with other reads in a batch, which it
2203    /// refuses whole, and still serves `version` reads.
2204    #[test]
2205    fn without_rpc_indexes_max_version_reads_are_refused() {
2206        let (service, id) = store_with_two_versions(true);
2207        let max_version = |max_version, at_checkpoint| {
2208            let mut request = request(id, None);
2209            request.max_version = Some(max_version);
2210            request.at_checkpoint = at_checkpoint;
2211            request
2212        };
2213        for request in [
2214            max_version(1, None),
2215            max_version(2, None),
2216            max_version(u64::MAX, None),
2217            max_version(2, Some(0)),
2218        ] {
2219            assert_not_served_here(
2220                get_object(&service, request.clone()).unwrap_err(),
2221                NotServedHereCause::NoRpcIndexes,
2222            );
2223            let mut batch = BatchGetObjectsRequest::default();
2224            batch.requests = vec![self::request(id, Some(1)), request];
2225            batch.read_mask = Some(FieldMask::from_str("object_id,version"));
2226            assert_not_served_here(
2227                batch_get_objects(&service, batch).unwrap_err(),
2228                NotServedHereCause::NoRpcIndexes,
2229            );
2230        }
2231        assert_eq!(version_of(get_object(&service, request(id, Some(1)))), 1);
2232    }
2233
2234    /// A node without object version history decides an exact `version` from the object's
2235    /// newest entry even when that entry is a tombstone: the removal version answers `NotFound`
2236    /// with the removal described, a version above it `NotFound`, and every older version is
2237    /// refused, through GetObject and BatchGetObjects alike.
2238    #[test]
2239    fn without_history_a_removed_object_is_answered_from_its_tombstone() {
2240        let (service, id) = store_with_removal(&[1, 2], 3);
2241
2242        let status = get_object(&service, request(id, Some(3)))
2243            .unwrap_err()
2244            .into_status_proto();
2245        assert_eq!(removed_version(&status).as_deref(), Some("3"), "{status:?}");
2246        let status = get_object(&service, request(id, Some(4)))
2247            .unwrap_err()
2248            .into_status_proto();
2249        assert_eq!(status.code, tonic::Code::NotFound as i32, "{status:?}");
2250        assert_version_not_retained(get_object(&service, request(id, Some(2))).unwrap_err());
2251
2252        let mut batch = BatchGetObjectsRequest::default();
2253        batch.requests = vec![
2254            request(id, Some(3)),
2255            request(id, Some(4)),
2256            request(id, Some(2)),
2257        ];
2258        batch.read_mask = Some(FieldMask::from_str("object_id,version"));
2259        let response = batch_get_objects(&service, batch).unwrap();
2260        let statuses: Vec<_> = response
2261            .objects
2262            .iter()
2263            .map(|result| match &result.result {
2264                Some(get_object_result::Result::Error(status)) => status,
2265                _ => panic!("expected only errors in {response:?}"),
2266            })
2267            .collect();
2268        let [at_removal, above_removal, below_removal] = statuses.as_slice() else {
2269            panic!("expected three results in {response:?}");
2270        };
2271        assert_eq!(
2272            removed_version(at_removal).as_deref(),
2273            Some("3"),
2274            "{response:?}"
2275        );
2276        assert_eq!(
2277            above_removal.code,
2278            tonic::Code::NotFound as i32,
2279            "{response:?}"
2280        );
2281        assert_eq!(
2282            below_removal.code,
2283            tonic::Code::OutOfRange as i32,
2284            "{response:?}"
2285        );
2286    }
2287}