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::ExecutionErrorTrait, 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, E>(
52        &mut self,
53        ids: I,
54        store: &dyn PackageStore,
55    ) -> Result<(), E>
56    where
57        E: ExecutionErrorTrait,
58        I: IntoIterator,
59        I::Item: Borrow<ObjectID>,
60    {
61        for id in ids {
62            let pkg = get_package(id.borrow(), store)?;
63            let transitive_deps = self
64                .config
65                .linkage_table(&pkg)
66                .into_values()
67                .map(ObjectID::from);
68            let package_id = pkg.version_id().into();
69            add_and_unify(&package_id, store, self, VersionConstraint::at_least)?;
70            for object_id in transitive_deps {
71                add_and_unify(&object_id, store, self, VersionConstraint::at_least)?;
72            }
73        }
74        Ok(())
75    }
76}
77
78impl VersionConstraint {
79    pub fn exact(pkg: &VerifiedPackage) -> Option<VersionConstraint> {
80        Some(VersionConstraint::Exact(
81            pkg.version(),
82            pkg.version_id().into(),
83        ))
84    }
85
86    pub fn at_least(pkg: &VerifiedPackage) -> Option<VersionConstraint> {
87        Some(VersionConstraint::AtLeast(
88            pkg.version(),
89            pkg.version_id().into(),
90        ))
91    }
92
93    pub fn unify<E: ExecutionErrorTrait>(
94        &self,
95        other: &VersionConstraint,
96    ) -> Result<VersionConstraint, E> {
97        match (&self, other) {
98            // If we have two exact resolutions, they must be the same.
99            (VersionConstraint::Exact(sv, self_id), VersionConstraint::Exact(ov, other_id)) => {
100                if self_id != other_id || sv != ov {
101                    Err(E::new_with_source(
102                        ExecutionErrorKind::InvalidLinkage,
103                        format!(
104                            "exact/exact conflicting resolutions for package: linkage requires the same package \
105                                 at different versions. Linkage requires exactly {self_id} (version {sv}) and \
106                                 {other_id} (version {ov}) to be used in the same transaction"
107                        ),
108                    ))
109                } else {
110                    Ok(VersionConstraint::Exact(*sv, *self_id))
111                }
112            }
113            // Take the max if you have two at least resolutions.
114            (
115                VersionConstraint::AtLeast(self_version, sid),
116                VersionConstraint::AtLeast(other_version, oid),
117            ) => {
118                let id = if self_version > other_version {
119                    *sid
120                } else {
121                    *oid
122                };
123
124                Ok(VersionConstraint::AtLeast(
125                    *self_version.max(other_version),
126                    id,
127                ))
128            }
129            // If you unify an exact and an at least, the exact must be greater than or equal to
130            // the at least. It unifies to an exact.
131            (
132                VersionConstraint::Exact(exact_version, exact_id),
133                VersionConstraint::AtLeast(at_least_version, at_least_id),
134            )
135            | (
136                VersionConstraint::AtLeast(at_least_version, at_least_id),
137                VersionConstraint::Exact(exact_version, exact_id),
138            ) => {
139                if exact_version < at_least_version {
140                    return Err(E::new_with_source(
141                        ExecutionErrorKind::InvalidLinkage,
142                        format!(
143                            "Exact/AtLeast conflicting resolutions for package: linkage requires exactly this \
144                                 package {exact_id} (version {exact_version}) and also at least the following \
145                                 version of the package {at_least_id} at version {at_least_version}. However \
146                                 {exact_id} is at version {exact_version} which is less than {at_least_version}."
147                        ),
148                    ));
149                }
150
151                Ok(VersionConstraint::Exact(*exact_version, *exact_id))
152            }
153        }
154    }
155}
156
157/// Load a package from the store, and update the type origin map with the types in that
158/// package.
159pub(crate) fn get_package<E: ExecutionErrorTrait>(
160    object_id: &ObjectID,
161    store: &dyn PackageStore,
162) -> Result<Arc<VerifiedPackage>, E> {
163    store
164        .get_package(object_id)
165        .map_err(|e| E::new_with_source(ExecutionErrorKind::PublishUpgradeMissingDependency, e))?
166        .ok_or_else(|| E::from_kind(ExecutionErrorKind::InvalidLinkage))
167}
168
169// Add a package to the unification table, unifying it with any existing package in the table.
170// Errors if the packages cannot be unified (e.g., if one is exact and the other is not).
171pub(crate) fn add_and_unify<E: ExecutionErrorTrait>(
172    object_id: &ObjectID,
173    store: &dyn PackageStore,
174    resolution_table: &mut ResolutionTable,
175    resolution_fn: fn(&VerifiedPackage) -> Option<VersionConstraint>,
176) -> Result<(), E> {
177    let package = get_package(object_id, store)?;
178
179    let Some(resolution) = resolution_fn(&package) else {
180        // If the resolution function returns None, we do not need to add this package to the
181        // resolution table, and this does not contribute to the linkage analysis.
182        return Ok(());
183    };
184    let original_pkg_id = package.original_id().into();
185
186    if let Entry::Vacant(e) = resolution_table.resolution_table.entry(original_pkg_id) {
187        e.insert(resolution);
188    } else {
189        let existing_unifier = resolution_table
190            .resolution_table
191            .get_mut(&original_pkg_id)
192            .expect("Guaranteed to exist");
193        *existing_unifier = existing_unifier.unify(&resolution)?;
194    }
195
196    if !resolution_table
197        .all_versions_resolution_table
198        .contains_key(object_id)
199    {
200        resolution_table
201            .all_versions_resolution_table
202            .insert(*object_id, original_pkg_id);
203    }
204
205    Ok(())
206}
sui_adapter_latest/static_programmable_transactions/linkage/resolution.rs

sui_adapter_latest/static_programmable_transactions/linkage/
resolution.rs
