miden_project/dependencies/resolver/
version_set.rs

1use core::fmt;
2use std::collections::BTreeSet;
3
4use miden_core::{LexicographicWord, Word};
5use pubgrub::VersionSet as _;
6use smallvec::{SmallVec, smallvec};
7
8use super::pubgrub_compat::SemverPubgrub;
9use crate::{SemVer, Version, VersionReq, VersionRequirement};
10
11/// This type is an implementation detail of the dependency resolver provided by
12/// [`super::PackageIndex`].
13///
14/// A [VersionSet], as implied by the name, provides set semantics for semantic versioning ranges
15/// that may also be further constrained by specific content digests that are considered to be part
16/// of the set.
17///
18/// * The empty set is represented as a range that cannot contain any version
19/// * The complete (aka "full") set is represented as an unbounded range with an empty content
20///   digest filter, equivalent to the semantic versioning constraint `*`
21/// * Set intersection is performed by finding the overlap in the ranges of the two sets, and then
22///   if either set has a content digest filter, only permitting content digests that are present in
23///   both sets. It is not guaranteed that a given content digest is included in the semantic
24///   version intersection, rather _either_ the digest or the semantic version of the intersection
25///   is used for matching a package.
26/// * Set complement is performed by negating the range of versions included in the set. The
27///   resulting set will always have an empty content digest filter.
28/// * Set containment for a version `v` is determined as follows:
29///   * If the semantic version component of `v` is covered by any range in the set, it is
30///     provisionally considered to be contained in the set, IFF
31///   * If the set specifies a content digest filter, then `v` must have a content digest component
32///     that matches that filter.
33#[derive(Debug, Clone, PartialEq, Eq)]
34pub struct VersionSet {
35    /// The range(s) of semantic versions that are included in the set
36    range: SemverPubgrub,
37    /// The content digest filter, represented as the set of content digests that are considered
38    /// to be members of this set. When non-empty, the set _only_ includes versions that are
39    /// considered contained in `range` _and_ have a content digest in `digests`.
40    digests: SmallVec<[LexicographicWord; 1]>,
41}
42
43/// Represents an additional filter on the versions considered a member of a [VersionSet].
44pub enum VersionSetFilter<'a> {
45    /// Matches any version, regardless of content digest
46    Any,
47    /// Matches only versions which have a content digest in the given set of digests
48    Digest(&'a [LexicographicWord]),
49}
50
51impl VersionSetFilter<'_> {
52    /// Returns true if `version` passes this filter, i.e. would be included in the associated set.
53    pub fn matches(&self, version: &Version) -> bool {
54        match self {
55            Self::Any => true,
56            Self::Digest(digests) => {
57                version.digest.as_ref().is_some_and(|digest| digests.contains(digest))
58            },
59        }
60    }
61}
62
63impl VersionSet {
64    /// Get the semantic version range(s) that are members of this set
65    pub fn range(&self) -> &SemverPubgrub {
66        &self.range
67    }
68
69    /// Get the filter applied to provisional members of this set when determining containment.
70    pub fn filter(&self) -> VersionSetFilter<'_> {
71        if self.digests.is_empty() {
72            VersionSetFilter::Any
73        } else {
74            VersionSetFilter::Digest(&self.digests)
75        }
76    }
77}
78
79impl Default for VersionSet {
80    #[inline]
81    fn default() -> Self {
82        Self::empty()
83    }
84}
85
86impl From<Word> for VersionSet {
87    fn from(value: Word) -> Self {
88        Self {
89            range: SemverPubgrub::empty(),
90            digests: smallvec![LexicographicWord::new(value)],
91        }
92    }
93}
94
95impl From<SemVer> for VersionSet {
96    fn from(value: SemVer) -> Self {
97        Self {
98            range: SemverPubgrub::singleton(value),
99            digests: smallvec![],
100        }
101    }
102}
103
104impl From<Version> for VersionSet {
105    fn from(value: Version) -> Self {
106        let Version { version, digest } = value;
107        Self {
108            range: SemverPubgrub::singleton(version),
109            digests: SmallVec::from_iter(digest),
110        }
111    }
112}
113
114impl From<VersionReq> for VersionSet {
115    fn from(value: VersionReq) -> Self {
116        Self {
117            range: SemverPubgrub::from(&value),
118            digests: smallvec![],
119        }
120    }
121}
122
123impl From<&VersionReq> for VersionSet {
124    fn from(value: &VersionReq) -> Self {
125        Self {
126            range: SemverPubgrub::from(value),
127            digests: smallvec![],
128        }
129    }
130}
131
132impl From<VersionRequirement> for VersionSet {
133    fn from(value: VersionRequirement) -> Self {
134        match value {
135            VersionRequirement::Digest(digest) => Self::from(digest.into_inner()),
136            VersionRequirement::Semantic(req) => Self::from(req.inner()),
137        }
138    }
139}
140
141impl From<SemverPubgrub> for VersionSet {
142    fn from(range: SemverPubgrub) -> Self {
143        Self { range, digests: smallvec![] }
144    }
145}
146
147impl fmt::Display for VersionSet {
148    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
149        match self.digests.as_slice() {
150            [] => write!(f, "{}", &self.range),
151            [digest] => write!(f, "{} in {}", digest.inner(), &self.range),
152            digests => {
153                f.write_str("any of ")?;
154                for (i, digest) in digests.iter().enumerate() {
155                    if i > 0 {
156                        f.write_str(", ")?;
157                    }
158                    write!(f, "{}", &digest.inner())?;
159                }
160                write!(f, " in {}", &self.range)
161            },
162        }
163    }
164}
165
166impl pubgrub::VersionSet for VersionSet {
167    type V = Version;
168
169    fn empty() -> Self {
170        Self::from(SemverPubgrub::empty())
171    }
172
173    fn singleton(v: Self::V) -> Self {
174        Self::from(v)
175    }
176
177    fn full() -> Self {
178        Self::from(SemverPubgrub::full())
179    }
180
181    fn complement(&self) -> Self {
182        Self::from(self.range.complement())
183    }
184
185    fn intersection(&self, other: &Self) -> Self {
186        if self.digests.is_empty() && other.digests.is_empty() {
187            return Self::from(self.range.intersection(&other.range));
188        }
189
190        let ldigests = BTreeSet::from_iter(self.digests.iter());
191        let rdigests = BTreeSet::from_iter(other.digests.iter());
192        let digests = ldigests.intersection(&rdigests).map(|d| **d).collect::<SmallVec<[_; _]>>();
193        // If either set contained specific digests, but the intersection does not, then we must
194        // return an empty set, as the expectation would be that at least one digest remains in a
195        // non-empty intersection.
196        if digests.is_empty() && !(self.digests.is_empty() || other.digests.is_empty()) {
197            Self::empty()
198        } else {
199            let range = self.range.intersection(&other.range);
200            Self { range, digests }
201        }
202    }
203
204    fn contains(&self, v: &Self::V) -> bool {
205        if let Some(digest) = v.digest.as_ref() {
206            self.digests.contains(digest)
207        } else {
208            self.range.contains(&v.version)
209        }
210    }
211}
miden_project/dependencies/resolver/version_set.rs

miden_project/dependencies/resolver/
version_set.rs
