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, BTreeSet, 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/// How a specific version of a package resolves, recorded for every package version the linkage
29/// refinement touched.
30#[derive(Debug, Clone, Copy)]
31pub struct PackageResolution {
32    /// The original id of the package.
33    pub original_id: ObjectID,
34    /// The resolved version of the package. `None` only for the late-bound self entry that
35    /// `ResolvedLinkage::update_for_publication` adds.
36    pub version: Option<u64>,
37}
38
39#[derive(Debug, Clone)]
40pub(crate) struct ResolutionTable {
41    pub(crate) config: ResolutionConfig,
42    pub(crate) resolution_table: BTreeMap<ObjectID, VersionConstraint>,
43    /// Type-defining packages whose linkage tables have already been expanded.
44    seen_type_packages: BTreeSet<ObjectID>,
45    /// For every version of every package that we have seen, a mapping of the ObjectID for that
46    /// package to its runtime ID.
47    pub(crate) all_versions_resolution_table: BTreeMap<ObjectID, PackageResolution>,
48}
49
50impl ResolutionTable {
51    pub fn empty(config: ResolutionConfig) -> Self {
52        Self {
53            config,
54            resolution_table: BTreeMap::new(),
55            seen_type_packages: BTreeSet::new(),
56            all_versions_resolution_table: BTreeMap::new(),
57        }
58    }
59
60    /// Given a list of object IDs, generate a `ResolvedLinkage` for them.
61    /// Since this linkage analysis should only be used for types, all packages are resolved
62    /// "upwards" (i.e., later versions of the package are preferred).
63    pub fn add_type_linkages_to_table<I, E, S>(&mut self, ids: I, store: &S) -> Result<(), E>
64    where
65        S: PackageStore + ?Sized,
66        E: ExecutionErrorTrait,
67        I: IntoIterator,
68        I::Item: Borrow<ObjectID>,
69    {
70        for id in ids {
71            let id = id.borrow();
72            if !self.seen_type_packages.insert(*id) {
73                continue;
74            }
75            let pkg = get_package(id, store)?;
76            let transitive_deps = self
77                .config
78                .linkage_table(&pkg)
79                .into_values()
80                .map(ObjectID::from);
81            let package_id = pkg.version_id();
82            add_and_unify(&package_id, store, self, VersionConstraint::at_least)?;
83            for object_id in transitive_deps {
84                add_and_unify(&object_id, store, self, VersionConstraint::at_least)?;
85            }
86        }
87        Ok(())
88    }
89}
90
91impl VersionConstraint {
92    pub(crate) fn object_id(&self) -> ObjectID {
93        match self {
94            VersionConstraint::Exact(_, id) | VersionConstraint::AtLeast(_, id) => *id,
95        }
96    }
97
98    pub(crate) fn exact<P: PackageMetadata>(pkg: &P) -> Option<VersionConstraint> {
99        Some(VersionConstraint::Exact(pkg.version(), pkg.version_id()))
100    }
101
102    pub(crate) fn at_least<P: PackageMetadata>(pkg: &P) -> Option<VersionConstraint> {
103        Some(VersionConstraint::AtLeast(pkg.version(), pkg.version_id()))
104    }
105
106    pub fn unify<E: ExecutionErrorTrait>(
107        &self,
108        other: &VersionConstraint,
109    ) -> Result<VersionConstraint, E> {
110        match (&self, other) {
111            // If we have two exact resolutions, they must be the same.
112            (VersionConstraint::Exact(sv, self_id), VersionConstraint::Exact(ov, other_id)) => {
113                if self_id != other_id || sv != ov {
114                    Err(E::new_with_source(
115                        ExecutionErrorKind::InvalidLinkage,
116                        format!(
117                            "exact/exact conflicting resolutions for package: linkage requires the same package \
118                                 at different versions. Linkage requires exactly {self_id} (version {sv}) and \
119                                 {other_id} (version {ov}) to be used in the same transaction"
120                        ),
121                    ))
122                } else {
123                    Ok(VersionConstraint::Exact(*sv, *self_id))
124                }
125            }
126            // Take the max if you have two at least resolutions.
127            (
128                VersionConstraint::AtLeast(self_version, sid),
129                VersionConstraint::AtLeast(other_version, oid),
130            ) => {
131                let id = if self_version > other_version {
132                    *sid
133                } else {
134                    *oid
135                };
136
137                Ok(VersionConstraint::AtLeast(
138                    *self_version.max(other_version),
139                    id,
140                ))
141            }
142            // If you unify an exact and an at least, the exact must be greater than or equal to
143            // the at least. It unifies to an exact.
144            (
145                VersionConstraint::Exact(exact_version, exact_id),
146                VersionConstraint::AtLeast(at_least_version, at_least_id),
147            )
148            | (
149                VersionConstraint::AtLeast(at_least_version, at_least_id),
150                VersionConstraint::Exact(exact_version, exact_id),
151            ) => {
152                if exact_version < at_least_version {
153                    return Err(E::new_with_source(
154                        ExecutionErrorKind::InvalidLinkage,
155                        format!(
156                            "Exact/AtLeast conflicting resolutions for package: linkage requires exactly this \
157                                 package {exact_id} (version {exact_version}) and also at least the following \
158                                 version of the package {at_least_id} at version {at_least_version}. However \
159                                 {exact_id} is at version {exact_version} which is less than {at_least_version}."
160                        ),
161                    ));
162                }
163
164                Ok(VersionConstraint::Exact(*exact_version, *exact_id))
165            }
166        }
167    }
168}
169
170/// Load a package from the store, and update the type origin map with the types in that
171/// package.
172pub(crate) fn get_package<E: ExecutionErrorTrait, S: PackageStore + ?Sized>(
173    object_id: &ObjectID,
174    store: &S,
175) -> Result<S::Package, E> {
176    store
177        .get_package(object_id)
178        .map_err(|e| E::new_with_source(ExecutionErrorKind::PublishUpgradeMissingDependency, e))?
179        .ok_or_else(|| E::from_kind(ExecutionErrorKind::InvalidLinkage))
180}
181
182// Add a package to the unification table, unifying it with any existing package in the table.
183// Errors if the packages cannot be unified (e.g., if one is exact and the other is not).
184pub(crate) fn add_and_unify<E: ExecutionErrorTrait, S: PackageStore + ?Sized>(
185    object_id: &ObjectID,
186    store: &S,
187    resolution_table: &mut ResolutionTable,
188    resolution_fn: fn(&S::Package) -> Option<VersionConstraint>,
189) -> Result<(), E> {
190    let package = get_package(object_id, store)?;
191
192    let Some(resolution) = resolution_fn(&package) else {
193        // If the resolution function returns None, we do not need to add this package to the
194        // resolution table, and this does not contribute to the linkage analysis.
195        return Ok(());
196    };
197    let original_pkg_id = package.original_id();
198
199    if let Entry::Vacant(e) = resolution_table.resolution_table.entry(original_pkg_id) {
200        e.insert(resolution);
201    } else {
202        let existing_unifier = resolution_table
203            .resolution_table
204            .get_mut(&original_pkg_id)
205            .expect("Guaranteed to exist");
206        *existing_unifier = existing_unifier.unify(&resolution)?;
207    }
208
209    if !resolution_table
210        .all_versions_resolution_table
211        .contains_key(object_id)
212    {
213        resolution_table.all_versions_resolution_table.insert(
214            *object_id,
215            PackageResolution {
216                original_id: original_pkg_id,
217                version: Some(package.version()),
218            },
219        );
220    }
221
222    Ok(())
223}
sui_adapter_latest/static_programmable_transactions/linkage/resolution.rs

sui_adapter_latest/static_programmable_transactions/linkage/
resolution.rs
