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

sui_adapter_latest/static_programmable_transactions/linkage/
resolution.rs
