sui_adapter_latest/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 move_vm_runtime::validation::verification::ast::Package as VerifiedPackage;
6use std::{
7    borrow::Borrow,
8    collections::{BTreeMap, btree_map::Entry},
9    sync::Arc,
10};
11use sui_types::{
12    base_types::ObjectID, error::ExecutionError, execution_status::ExecutionErrorKind,
13};
14
15/// Unifiers. These are used to determine how to unify two packages.
16#[derive(Debug, Clone)]
17pub enum VersionConstraint {
18    /// An exact constraint unifies as follows:
19    /// 1. Exact(a) ~ Exact(b) ==> Exact(a), iff a == b
20    /// 2. Exact(a) ~ AtLeast(b) ==> Exact(a), iff a >= b
21    Exact(u64, ObjectID),
22    /// An at least constraint unifies as follows:
23    /// * AtLeast(a, a_version) ~ AtLeast(b, b_version) ==> AtLeast(x, max(a_version, b_version)),
24    ///   where x is the package id of either a or b (the one with the greatest version).
25    AtLeast(u64, ObjectID),
26}
27
28#[derive(Debug, Clone)]
29pub(crate) struct ResolutionTable {
30    pub(crate) resolution_table: BTreeMap<ObjectID, VersionConstraint>,
31    /// For every version of every package that we have seen, a mapping of the ObjectID for that
32    /// package to its runtime ID.
33    pub(crate) all_versions_resolution_table: BTreeMap<ObjectID, ObjectID>,
34}
35
36impl ResolutionTable {
37    pub fn empty() -> Self {
38        Self {
39            resolution_table: BTreeMap::new(),
40            all_versions_resolution_table: BTreeMap::new(),
41        }
42    }
43
44    /// Given a list of object IDs, generate a `ResolvedLinkage` for them.
45    /// Since this linkage analysis should only be used for types, all packages are resolved
46    /// "upwards" (i.e., later versions of the package are preferred).
47    pub fn add_type_linkages_to_table<I>(
48        &mut self,
49        ids: I,
50        store: &dyn PackageStore,
51    ) -> Result<(), ExecutionError>
52    where
53        I: IntoIterator,
54        I::Item: Borrow<ObjectID>,
55    {
56        for id in ids {
57            let pkg = get_package(id.borrow(), store)?;
58            let transitive_deps = pkg.linkage_table().values().copied().map(ObjectID::from);
59            let package_id = pkg.version_id().into();
60            add_and_unify(&package_id, store, self, VersionConstraint::at_least)?;
61            for object_id in transitive_deps {
62                add_and_unify(&object_id, store, self, VersionConstraint::at_least)?;
63            }
64        }
65        Ok(())
66    }
67}
68
69impl VersionConstraint {
70    pub fn exact(pkg: &VerifiedPackage) -> Option<VersionConstraint> {
71        Some(VersionConstraint::Exact(
72            pkg.version(),
73            pkg.version_id().into(),
74        ))
75    }
76
77    pub fn at_least(pkg: &VerifiedPackage) -> Option<VersionConstraint> {
78        Some(VersionConstraint::AtLeast(
79            pkg.version(),
80            pkg.version_id().into(),
81        ))
82    }
83
84    pub fn unify(&self, other: &VersionConstraint) -> Result<VersionConstraint, ExecutionError> {
85        match (&self, other) {
86            // If we have two exact resolutions, they must be the same.
87            (VersionConstraint::Exact(sv, self_id), VersionConstraint::Exact(ov, other_id)) => {
88                if self_id != other_id || sv != ov {
89                    Err(ExecutionError::new_with_source(
90                        ExecutionErrorKind::InvalidLinkage,
91                        format!(
92                            "exact/exact conflicting resolutions for package: linkage requires the same package \
93                                 at different versions. Linkage requires exactly {self_id} (version {sv}) and \
94                                 {other_id} (version {ov}) to be used in the same transaction"
95                        ),
96                    ))
97                } else {
98                    Ok(VersionConstraint::Exact(*sv, *self_id))
99                }
100            }
101            // Take the max if you have two at least resolutions.
102            (
103                VersionConstraint::AtLeast(self_version, sid),
104                VersionConstraint::AtLeast(other_version, oid),
105            ) => {
106                let id = if self_version > other_version {
107                    *sid
108                } else {
109                    *oid
110                };
111
112                Ok(VersionConstraint::AtLeast(
113                    *self_version.max(other_version),
114                    id,
115                ))
116            }
117            // If you unify an exact and an at least, the exact must be greater than or equal to
118            // the at least. It unifies to an exact.
119            (
120                VersionConstraint::Exact(exact_version, exact_id),
121                VersionConstraint::AtLeast(at_least_version, at_least_id),
122            )
123            | (
124                VersionConstraint::AtLeast(at_least_version, at_least_id),
125                VersionConstraint::Exact(exact_version, exact_id),
126            ) => {
127                if exact_version < at_least_version {
128                    return Err(ExecutionError::new_with_source(
129                        ExecutionErrorKind::InvalidLinkage,
130                        format!(
131                            "Exact/AtLeast conflicting resolutions for package: linkage requires exactly this \
132                                 package {exact_id} (version {exact_version}) and also at least the following \
133                                 version of the package {at_least_id} at version {at_least_version}. However \
134                                 {exact_id} is at version {exact_version} which is less than {at_least_version}."
135                        ),
136                    ));
137                }
138
139                Ok(VersionConstraint::Exact(*exact_version, *exact_id))
140            }
141        }
142    }
143}
144
145/// Load a package from the store, and update the type origin map with the types in that
146/// package.
147pub(crate) fn get_package(
148    object_id: &ObjectID,
149    store: &dyn PackageStore,
150) -> Result<Arc<VerifiedPackage>, ExecutionError> {
151    store
152        .get_package(object_id)
153        .map_err(|e| {
154            ExecutionError::new_with_source(ExecutionErrorKind::PublishUpgradeMissingDependency, e)
155        })?
156        .ok_or_else(|| ExecutionError::from_kind(ExecutionErrorKind::InvalidLinkage))
157}
158
159// Add a package to the unification table, unifying it with any existing package in the table.
160// Errors if the packages cannot be unified (e.g., if one is exact and the other is not).
161pub(crate) fn add_and_unify(
162    object_id: &ObjectID,
163    store: &dyn PackageStore,
164    resolution_table: &mut ResolutionTable,
165    resolution_fn: fn(&VerifiedPackage) -> Option<VersionConstraint>,
166) -> Result<(), ExecutionError> {
167    let package = get_package(object_id, store)?;
168
169    let Some(resolution) = resolution_fn(&package) else {
170        // If the resolution function returns None, we do not need to add this package to the
171        // resolution table, and this does not contribute to the linkage analysis.
172        return Ok(());
173    };
174    let original_pkg_id = package.original_id().into();
175
176    if let Entry::Vacant(e) = resolution_table.resolution_table.entry(original_pkg_id) {
177        e.insert(resolution);
178    } else {
179        let existing_unifier = resolution_table
180            .resolution_table
181            .get_mut(&original_pkg_id)
182            .expect("Guaranteed to exist");
183        *existing_unifier = existing_unifier.unify(&resolution)?;
184    }
185
186    if !resolution_table
187        .all_versions_resolution_table
188        .contains_key(object_id)
189    {
190        resolution_table
191            .all_versions_resolution_table
192            .insert(*object_id, original_pkg_id);
193    }
194
195    Ok(())
196}
sui_adapter_latest/static_programmable_transactions/linkage/resolution.rs

sui_adapter_latest/static_programmable_transactions/linkage/
resolution.rs
