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

sui_adapter_latest/static_programmable_transactions/linkage/
resolution.rs
