sui_adapter_v3/static_programmable_transactions/linkage/
resolution.rs

1// Copyright (c) Mysten Labs, Inc.
2// SPDX-License-Identifier: Apache-2.0
3
4use crate::data_store::PackageStore;
5use std::{
6    collections::{BTreeMap, btree_map::Entry},
7    rc::Rc,
8};
9use sui_types::{
10    base_types::{ObjectID, SequenceNumber},
11    error::ExecutionError,
12    execution_status::ExecutionErrorKind,
13    move_package::MovePackage,
14};
15
16/// Unifiers. These are used to determine how to unify two packages.
17#[derive(Debug, Clone)]
18pub enum VersionConstraint {
19    /// An exact constraint unifies as follows:
20    /// 1. Exact(a) ~ Exact(b) ==> Exact(a), iff a == b
21    /// 2. Exact(a) ~ AtLeast(b) ==> Exact(a), iff a >= b
22    Exact(SequenceNumber, ObjectID),
23    /// An at least constraint unifies as follows:
24    /// * AtLeast(a, a_version) ~ AtLeast(b, b_version) ==> AtLeast(x, max(a_version, b_version)),
25    ///   where x is the package id of either a or b (the one with the greatest version).
26    AtLeast(SequenceNumber, ObjectID),
27}
28
29#[derive(Debug, Clone)]
30pub(crate) struct ResolutionTable {
31    pub(crate) resolution_table: BTreeMap<ObjectID, VersionConstraint>,
32    /// For every version of every package that we have seen, a mapping of the ObjectID for that
33    /// package to its runtime ID.
34    pub(crate) all_versions_resolution_table: BTreeMap<ObjectID, ObjectID>,
35}
36
37impl ResolutionTable {
38    pub fn empty() -> Self {
39        Self {
40            resolution_table: BTreeMap::new(),
41            all_versions_resolution_table: BTreeMap::new(),
42        }
43    }
44}
45
46impl VersionConstraint {
47    pub fn exact(pkg: &MovePackage) -> Option<VersionConstraint> {
48        Some(VersionConstraint::Exact(pkg.version(), pkg.id()))
49    }
50
51    pub fn at_least(pkg: &MovePackage) -> Option<VersionConstraint> {
52        Some(VersionConstraint::AtLeast(pkg.version(), pkg.id()))
53    }
54
55    pub fn unify(&self, other: &VersionConstraint) -> Result<VersionConstraint, ExecutionError> {
56        match (&self, other) {
57            // If we have two exact resolutions, they must be the same.
58            (VersionConstraint::Exact(sv, self_id), VersionConstraint::Exact(ov, other_id)) => {
59                if self_id != other_id || sv != ov {
60                    Err(ExecutionError::new_with_source(
61                        ExecutionErrorKind::InvalidLinkage,
62                        format!(
63                            "exact/exact conflicting resolutions for package: linkage requires the same package \
64                                 at different versions. Linkage requires exactly {self_id} (version {sv}) and \
65                                 {other_id} (version {ov}) to be used in the same transaction"
66                        ),
67                    ))
68                } else {
69                    Ok(VersionConstraint::Exact(*sv, *self_id))
70                }
71            }
72            // Take the max if you have two at least resolutions.
73            (
74                VersionConstraint::AtLeast(self_version, sid),
75                VersionConstraint::AtLeast(other_version, oid),
76            ) => {
77                let id = if self_version > other_version {
78                    *sid
79                } else {
80                    *oid
81                };
82
83                Ok(VersionConstraint::AtLeast(
84                    *self_version.max(other_version),
85                    id,
86                ))
87            }
88            // If you unify an exact and an at least, the exact must be greater than or equal to
89            // the at least. It unifies to an exact.
90            (
91                VersionConstraint::Exact(exact_version, exact_id),
92                VersionConstraint::AtLeast(at_least_version, at_least_id),
93            )
94            | (
95                VersionConstraint::AtLeast(at_least_version, at_least_id),
96                VersionConstraint::Exact(exact_version, exact_id),
97            ) => {
98                if exact_version < at_least_version {
99                    return Err(ExecutionError::new_with_source(
100                        ExecutionErrorKind::InvalidLinkage,
101                        format!(
102                            "Exact/AtLeast conflicting resolutions for package: linkage requires exactly this \
103                                 package {exact_id} (version {exact_version}) and also at least the following \
104                                 version of the package {at_least_id} at version {at_least_version}. However \
105                                 {exact_id} is at version {exact_version} which is less than {at_least_version}."
106                        ),
107                    ));
108                }
109
110                Ok(VersionConstraint::Exact(*exact_version, *exact_id))
111            }
112        }
113    }
114}
115
116/// Load a package from the store, and update the type origin map with the types in that
117/// package.
118pub(crate) fn get_package(
119    object_id: &ObjectID,
120    store: &dyn PackageStore,
121) -> Result<Rc<MovePackage>, ExecutionError> {
122    store
123        .get_package(object_id)
124        .map_err(|e| {
125            ExecutionError::new_with_source(ExecutionErrorKind::PublishUpgradeMissingDependency, e)
126        })?
127        .ok_or_else(|| ExecutionError::from_kind(ExecutionErrorKind::InvalidLinkage))
128}
129
130// Add a package to the unification table, unifying it with any existing package in the table.
131// Errors if the packages cannot be unified (e.g., if one is exact and the other is not).
132pub(crate) fn add_and_unify(
133    object_id: &ObjectID,
134    store: &dyn PackageStore,
135    resolution_table: &mut ResolutionTable,
136    resolution_fn: fn(&MovePackage) -> Option<VersionConstraint>,
137) -> Result<(), ExecutionError> {
138    let package = get_package(object_id, store)?;
139
140    let Some(resolution) = resolution_fn(&package) else {
141        // If the resolution function returns None, we do not need to add this package to the
142        // resolution table, and this does not contribute to the linkage analysis.
143        return Ok(());
144    };
145    let original_pkg_id = package.original_package_id();
146
147    if let Entry::Vacant(e) = resolution_table.resolution_table.entry(original_pkg_id) {
148        e.insert(resolution);
149    } else {
150        let existing_unifier = resolution_table
151            .resolution_table
152            .get_mut(&original_pkg_id)
153            .expect("Guaranteed to exist");
154        *existing_unifier = existing_unifier.unify(&resolution)?;
155    }
156
157    if !resolution_table
158        .all_versions_resolution_table
159        .contains_key(object_id)
160    {
161        resolution_table
162            .all_versions_resolution_table
163            .insert(*object_id, original_pkg_id);
164    }
165
166    Ok(())
167}
sui_adapter_v3/static_programmable_transactions/linkage/resolution.rs

sui_adapter_v3/static_programmable_transactions/linkage/
resolution.rs
