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

sui_adapter_latest/static_programmable_transactions/linkage/
resolution.rs
