uv_resolver/
version_map.rs

1use std::collections::BTreeMap;
2use std::collections::Bound;
3use std::ops::RangeBounds;
4use std::sync::OnceLock;
5
6use jiff::Timestamp;
7use pubgrub::Ranges;
8use tracing::{instrument, trace};
9
10use uv_client::{FlatIndexEntry, OwnedArchive, SimpleDetailMetadata, VersionFiles};
11use uv_configuration::BuildOptions;
12use uv_distribution_filename::{DistFilename, SourceDistFilename, WheelFilename};
13use uv_distribution_types::{
14    HashComparison, IncompatibleSource, IncompatibleWheel, IndexUrl, PrioritizedDist,
15    RegistryBuiltWheel, RegistrySourceDist, RequiresPython, SourceDistCompatibility,
16    WheelCompatibility,
17};
18use uv_normalize::PackageName;
19use uv_pep440::Version;
20use uv_platform_tags::{IncompatibleTag, TagCompatibility, Tags};
21use uv_pypi_types::{HashDigest, ResolutionMetadata, Yanked};
22use uv_types::HashStrategy;
23use uv_warnings::warn_user_once;
24
25use crate::flat_index::FlatDistributions;
26use crate::yanks::AllowedYanks;
27
28/// A map from versions to distributions.
29#[derive(Debug)]
30pub struct VersionMap {
31    /// The inner representation of the version map.
32    inner: VersionMapInner,
33}
34
35impl VersionMap {
36    /// Initialize a [`VersionMap`] from the given metadata.
37    ///
38    /// Note it is possible for files to have a different yank status per PEP 592 but in the official
39    /// PyPI warehouse this cannot happen.
40    ///
41    /// Here, we track if each file is yanked separately. If a release is partially yanked, the
42    /// unyanked distributions _can_ be used.
43    ///
44    /// PEP 592: <https://peps.python.org/pep-0592/#warehouse-pypi-implementation-notes>
45    #[instrument(skip_all, fields(package_name))]
46    pub(crate) fn from_simple_metadata(
47        simple_metadata: OwnedArchive<SimpleDetailMetadata>,
48        package_name: &PackageName,
49        index: IndexUrl,
50        tags: Option<Tags>,
51        requires_python: RequiresPython,
52        allowed_yanks: AllowedYanks,
53        hasher: HashStrategy,
54        included_version_cutoff: Option<Timestamp>,
55        available_version_cutoff: Option<Timestamp>,
56        flat_index: Option<FlatDistributions>,
57        build_options: &BuildOptions,
58    ) -> Self {
59        let mut local = false;
60        let mut entries = Vec::with_capacity(simple_metadata.iter().size_hint().0);
61        // Create stubs for each entry in simple metadata. The full conversion
62        // from a `VersionFiles` to a PrioritizedDist for each version
63        // isn't done until that specific version is requested.
64        for (datum_index, datum) in simple_metadata.iter().enumerate() {
65            let version = rkyv::deserialize::<Version, rkyv::rancor::Error>(&datum.version)
66                .expect("archived version always deserializes");
67
68            local |= version.is_local();
69            debug_assert!(
70                entries
71                    .last()
72                    .is_none_or(|entry: &VersionMapLazyEntry| entry.version < version),
73                "simple metadata versions must be sorted and unique"
74            );
75            entries.push(VersionMapLazyEntry {
76                version,
77                dist: LazyPrioritizedDist {
78                    flat: None,
79                    simple: Some(SimplePrioritizedDist {
80                        datum_index,
81                        dist: OnceLock::new(),
82                    }),
83                },
84            });
85        }
86        let mut map = VersionMapLazyIndex { entries };
87        // If a set of flat distributions have been given, linearly merge the
88        // already sorted flat entries with the archive-ordered simple vector.
89        if let Some(flat_index) = flat_index {
90            map = map.merge_flat(flat_index);
91        }
92        Self {
93            inner: VersionMapInner::Lazy(VersionMapLazy {
94                package_name: package_name.clone(),
95                map,
96                local,
97                simple_metadata,
98                no_binary: build_options.no_binary_package(package_name),
99                no_build: build_options.no_build_package(package_name),
100                index,
101                tags,
102                allowed_yanks,
103                hasher,
104                requires_python,
105                included_version_cutoff,
106                available_version_cutoff,
107            }),
108        }
109    }
110
111    #[instrument(skip_all, fields(package_name))]
112    pub(crate) fn from_flat_metadata(
113        flat_metadata: Vec<FlatIndexEntry>,
114        tags: Option<&Tags>,
115        hasher: &HashStrategy,
116        build_options: &BuildOptions,
117    ) -> Self {
118        let mut local = false;
119        let mut map = BTreeMap::new();
120
121        for (version, prioritized_dist) in
122            FlatDistributions::from_entries(flat_metadata, tags, hasher, build_options)
123        {
124            local |= version.is_local();
125            map.insert(version, prioritized_dist);
126        }
127
128        Self {
129            inner: VersionMapInner::Eager(VersionMapEager { map, local }),
130        }
131    }
132
133    /// Return the [`ResolutionMetadata`] for the given version, if any.
134    pub(crate) fn get_metadata(&self, version: &Version) -> Option<ResolutionMetadata> {
135        match self.inner {
136            VersionMapInner::Eager(_) => None,
137            VersionMapInner::Lazy(ref lazy) => lazy.get_metadata(version),
138        }
139    }
140
141    /// Return the [`DistFile`] for the given version, if any.
142    pub(crate) fn get(&self, version: &Version) -> Option<&PrioritizedDist> {
143        match self.inner {
144            VersionMapInner::Eager(ref eager) => eager.map.get(version),
145            VersionMapInner::Lazy(ref lazy) => lazy.get(version),
146        }
147    }
148
149    /// Return an iterator over the versions in this map.
150    pub(crate) fn versions(&self) -> impl DoubleEndedIterator<Item = &Version> {
151        match &self.inner {
152            VersionMapInner::Eager(eager) => either::Either::Left(eager.map.keys()),
153            VersionMapInner::Lazy(lazy) => either::Either::Right(lazy.map.keys()),
154        }
155    }
156
157    /// Returns versions with at least one file not excluded by an upload-time cutoff, in ascending
158    /// order.
159    ///
160    /// Versions unavailable for other reasons remain present so callers receive a conservative
161    /// superset of selectable versions. These reasons include yanks, hashes, `requires-python`,
162    /// and `--no-binary` or `--no-build` policies. Flat-index versions bypass upload-time cutoffs
163    /// because their files do not carry upload times.
164    pub(crate) fn included_versions(&self) -> impl DoubleEndedIterator<Item = &Version> {
165        match &self.inner {
166            VersionMapInner::Eager(eager) => either::Either::Left(eager.map.keys()),
167            VersionMapInner::Lazy(lazy) => either::Either::Right(lazy.included_versions()),
168        }
169    }
170
171    /// Return the index URL where this package came from.
172    pub(crate) fn index(&self) -> Option<&IndexUrl> {
173        match &self.inner {
174            VersionMapInner::Eager(_) => None,
175            VersionMapInner::Lazy(lazy) => Some(&lazy.index),
176        }
177    }
178
179    /// Return the included-version cutoff for this version map, if any.
180    pub(crate) fn included_version_cutoff(&self) -> Option<&Timestamp> {
181        match &self.inner {
182            VersionMapInner::Eager(_) => None,
183            VersionMapInner::Lazy(lazy) => lazy.included_version_cutoff.as_ref(),
184        }
185    }
186
187    /// Return an iterator over the versions and distributions.
188    ///
189    /// Note that the value returned in this iterator is a [`VersionMapDist`],
190    /// which can be used to lazily request a [`CompatibleDist`]. This is
191    /// useful in cases where one can skip materializing a full distribution
192    /// for each version.
193    pub(crate) fn iter(
194        &self,
195        range: &Ranges<Version>,
196    ) -> impl DoubleEndedIterator<Item = (&Version, VersionMapDistHandle<'_>)> {
197        // Performance optimization: If we only have a single version, return that version directly.
198        if let Some(version) = range.as_singleton() {
199            either::Either::Left(match self.inner {
200                VersionMapInner::Eager(ref eager) => {
201                    either::Either::Left(eager.map.get_key_value(version).into_iter().map(
202                        move |(version, dist)| {
203                            let version_map_dist = VersionMapDistHandle {
204                                inner: VersionMapDistHandleInner::Eager(dist),
205                            };
206                            (version, version_map_dist)
207                        },
208                    ))
209                }
210                VersionMapInner::Lazy(ref lazy) => {
211                    either::Either::Right(lazy.map.get(version).into_iter().map(move |entry| {
212                        let version_map_dist = VersionMapDistHandle {
213                            inner: VersionMapDistHandleInner::Lazy {
214                                lazy,
215                                dist: &entry.dist,
216                            },
217                        };
218                        (&entry.version, version_map_dist)
219                    }))
220                }
221            })
222        } else {
223            either::Either::Right(match self.inner {
224                VersionMapInner::Eager(ref eager) => {
225                    either::Either::Left(eager.map.range(BoundingRange::from(range)).map(
226                        |(version, dist)| {
227                            let version_map_dist = VersionMapDistHandle {
228                                inner: VersionMapDistHandleInner::Eager(dist),
229                            };
230                            (version, version_map_dist)
231                        },
232                    ))
233                }
234                VersionMapInner::Lazy(ref lazy) => {
235                    either::Either::Right(lazy.map.range(BoundingRange::from(range)).iter().map(
236                        |entry| {
237                            let version_map_dist = VersionMapDistHandle {
238                                inner: VersionMapDistHandleInner::Lazy {
239                                    lazy,
240                                    dist: &entry.dist,
241                                },
242                            };
243                            (&entry.version, version_map_dist)
244                        },
245                    ))
246                }
247            })
248        }
249    }
250
251    /// Return an iterator over the versions that can be considered for selection.
252    ///
253    /// Unlike [`Self::iter`], this skips lazy registry versions whose files are all excluded by
254    /// an upload-time cutoff without materializing their distributions. Files without an upload
255    /// time remain included so that materialization can emit the appropriate warning.
256    pub(crate) fn iter_included(
257        &self,
258        range: &Ranges<Version>,
259    ) -> impl DoubleEndedIterator<Item = (&Version, VersionMapDistHandle<'_>)> {
260        self.iter(range).filter(|(_, dist)| dist.is_included())
261    }
262
263    /// Return the [`Hashes`] for the given version, if any.
264    pub(crate) fn hashes(&self, version: &Version) -> Option<&[HashDigest]> {
265        match self.inner {
266            VersionMapInner::Eager(ref eager) => {
267                eager.map.get(version).map(PrioritizedDist::hashes)
268            }
269            VersionMapInner::Lazy(ref lazy) => lazy.get(version).map(PrioritizedDist::hashes),
270        }
271    }
272
273    /// Returns the total number of distinct versions in this map.
274    ///
275    /// Note that this may include versions of distributions that are not
276    /// usable in the current environment.
277    pub(crate) fn len(&self) -> usize {
278        match self.inner {
279            VersionMapInner::Eager(VersionMapEager { ref map, .. }) => map.len(),
280            VersionMapInner::Lazy(VersionMapLazy { ref map, .. }) => map.len(),
281        }
282    }
283
284    /// Returns `true` if the map contains at least one local version (e.g., `2.6.0+cpu`).
285    pub(crate) fn local(&self) -> bool {
286        match self.inner {
287            VersionMapInner::Eager(ref map) => map.local,
288            VersionMapInner::Lazy(ref map) => map.local,
289        }
290    }
291}
292
293impl From<FlatDistributions> for VersionMap {
294    fn from(flat_index: FlatDistributions) -> Self {
295        let local = flat_index.iter().any(|(version, _)| version.is_local());
296        let map = flat_index.into();
297        Self {
298            inner: VersionMapInner::Eager(VersionMapEager { map, local }),
299        }
300    }
301}
302
303/// A lazily initialized distribution.
304///
305/// This permits access to a handle that can be turned into a resolvable
306/// distribution when desired. This is coupled with a `Version` in
307/// [`VersionMap::iter`] to permit iteration over all items in a map without
308/// necessarily constructing a distribution for every version if it isn't
309/// needed.
310///
311/// Note that because of laziness, not all such items can be turned into
312/// a valid distribution. For example, if in the process of building a
313/// distribution no compatible wheel or source distribution could be found,
314/// then building a `CompatibleDist` will fail.
315pub(crate) struct VersionMapDistHandle<'a> {
316    inner: VersionMapDistHandleInner<'a>,
317}
318
319enum VersionMapDistHandleInner<'a> {
320    Eager(&'a PrioritizedDist),
321    Lazy {
322        lazy: &'a VersionMapLazy,
323        dist: &'a LazyPrioritizedDist,
324    },
325}
326
327impl<'a> VersionMapDistHandle<'a> {
328    /// Returns whether this distribution can be considered for selection.
329    fn is_included(&self) -> bool {
330        match self.inner {
331            VersionMapDistHandleInner::Eager(_) => true,
332            VersionMapDistHandleInner::Lazy { lazy, dist } => match (&dist.flat, &dist.simple) {
333                (Some(_), _) => true,
334                (None, Some(simple)) => lazy.any_file_materializable(simple),
335                (None, None) => false,
336            },
337        }
338    }
339
340    /// Returns a prioritized distribution from this handle.
341    pub(crate) fn prioritized_dist(&self) -> Option<&'a PrioritizedDist> {
342        match self.inner {
343            VersionMapDistHandleInner::Eager(dist) => Some(dist),
344            VersionMapDistHandleInner::Lazy { lazy, dist } => Some(lazy.get_lazy(dist)?),
345        }
346    }
347}
348
349/// The kind of internal version map we have.
350#[derive(Debug)]
351#[expect(clippy::large_enum_variant)]
352enum VersionMapInner {
353    /// All distributions are fully materialized in memory.
354    ///
355    /// This usually happens when one needs a `VersionMap` from a
356    /// `FlatDistributions`.
357    Eager(VersionMapEager),
358    /// Some distributions might be fully materialized (i.e., by initializing
359    /// a `VersionMap` with a `FlatDistributions`), but some distributions
360    /// might still be in their "raw" `SimpleDetailMetadata` format. In this case, a
361    /// `PrioritizedDist` isn't actually created in memory until the
362    /// specific version has been requested.
363    Lazy(VersionMapLazy),
364}
365
366/// A map from versions to distributions that are fully materialized in memory.
367#[derive(Debug)]
368struct VersionMapEager {
369    /// A map from version to distribution.
370    map: BTreeMap<Version, PrioritizedDist>,
371    /// Whether the version map contains at least one local version.
372    local: bool,
373}
374
375/// An entry in the immutable lazy version index.
376#[derive(Debug)]
377struct VersionMapLazyEntry {
378    version: Version,
379    dist: LazyPrioritizedDist,
380}
381
382/// A compact immutable version index, ordered by native PEP 440 versions.
383#[derive(Debug)]
384struct VersionMapLazyIndex {
385    entries: Vec<VersionMapLazyEntry>,
386}
387
388impl VersionMapLazyIndex {
389    /// Merge the sorted flat index into the sorted simple entries in one pass.
390    fn merge_flat(self, flat_index: FlatDistributions) -> Self {
391        let flat_count = flat_index.iter().size_hint().0;
392        let mut merged = Vec::with_capacity(self.entries.len() + flat_count);
393        let mut simple = self.entries.into_iter().peekable();
394        let mut flat = flat_index.into_iter().peekable();
395        let flat_entry = |(version, dist)| VersionMapLazyEntry {
396            version,
397            dist: LazyPrioritizedDist {
398                flat: Some(dist),
399                simple: None,
400            },
401        };
402        while let (Some(simple_entry), Some((flat_version, _))) = (simple.peek(), flat.peek()) {
403            match simple_entry.version.cmp(flat_version) {
404                std::cmp::Ordering::Less => {
405                    if let Some(entry) = simple.next() {
406                        merged.push(entry);
407                    }
408                }
409                std::cmp::Ordering::Greater => {
410                    if let Some(entry) = flat.next() {
411                        merged.push(flat_entry(entry));
412                    }
413                }
414                std::cmp::Ordering::Equal => {
415                    if let (Some(mut entry), Some((_, dist))) = (simple.next(), flat.next()) {
416                        entry.dist.flat = Some(dist);
417                        merged.push(entry);
418                    }
419                }
420            }
421        }
422        merged.extend(simple);
423        merged.extend(flat.map(flat_entry));
424
425        Self { entries: merged }
426    }
427
428    fn get(&self, version: &Version) -> Option<&VersionMapLazyEntry> {
429        let index = self
430            .entries
431            .binary_search_by(|entry| entry.version.cmp(version))
432            .ok()?;
433        self.entries.get(index)
434    }
435
436    fn keys(&self) -> impl DoubleEndedIterator<Item = &Version> {
437        self.entries.iter().map(|entry| &entry.version)
438    }
439
440    fn range(&self, range: BoundingRange<'_>) -> &[VersionMapLazyEntry] {
441        let start = match range.min {
442            Bound::Included(version) => self
443                .entries
444                .partition_point(|entry| entry.version < *version),
445            Bound::Excluded(version) => self
446                .entries
447                .partition_point(|entry| entry.version <= *version),
448            Bound::Unbounded => 0,
449        };
450        let end = match range.max {
451            Bound::Included(version) => self
452                .entries
453                .partition_point(|entry| entry.version <= *version),
454            Bound::Excluded(version) => self
455                .entries
456                .partition_point(|entry| entry.version < *version),
457            Bound::Unbounded => self.entries.len(),
458        };
459        self.entries.get(start..end).unwrap_or_default()
460    }
461
462    fn len(&self) -> usize {
463        self.entries.len()
464    }
465}
466
467/// A map that lazily materializes some prioritized distributions upon access.
468///
469/// The idea here is that some packages have a lot of versions published, and
470/// needing to materialize a full `VersionMap` with all corresponding metadata
471/// for every version in memory is expensive. Since a `SimpleDetailMetadata` can be
472/// materialized with very little cost (via `rkyv` in the warm cached case),
473/// avoiding another conversion step into a fully filled out `VersionMap` can
474/// provide substantial savings in some cases.
475#[derive(Debug)]
476struct VersionMapLazy {
477    /// The normalized package name used to reconstruct cached wheel filenames.
478    package_name: PackageName,
479    /// An immutable archive-order index from version to possibly-initialized distribution.
480    map: VersionMapLazyIndex,
481    /// Whether the version map contains at least one local version.
482    local: bool,
483    /// The raw simple metadata from which `PrioritizedDist`s should
484    /// be constructed.
485    simple_metadata: OwnedArchive<SimpleDetailMetadata>,
486    /// When true, wheels aren't allowed.
487    no_binary: bool,
488    /// When true, source dists aren't allowed.
489    no_build: bool,
490    /// The URL of the index where this package came from.
491    index: IndexUrl,
492    /// The set of compatibility tags that determines whether a wheel is usable
493    /// in the current environment.
494    tags: Option<Tags>,
495    /// Files newer than this timestamp are considered excluded, i.e., that they cannot be selected by the
496    /// resolver.
497    included_version_cutoff: Option<Timestamp>,
498    /// Files newer than this timestamp are considered unavailable, i.e., that they do not exist.
499    available_version_cutoff: Option<Timestamp>,
500    /// Which yanked versions are allowed
501    allowed_yanks: AllowedYanks,
502    /// The hashes of allowed distributions.
503    hasher: HashStrategy,
504    /// The `requires-python` constraint for the resolution.
505    requires_python: RequiresPython,
506}
507
508impl VersionMapLazy {
509    /// Returns the registry-provided metadata for the given version, if it exists.
510    fn get_metadata(&self, version: &Version) -> Option<ResolutionMetadata> {
511        let archived = self
512            .map
513            .get(version)
514            .and_then(|entry| entry.dist.simple.as_ref())
515            .and_then(|simple| self.simple_metadata.datum(simple.datum_index))
516            .and_then(|datum| datum.metadata.as_deref())?;
517        Some(
518            rkyv::deserialize::<ResolutionMetadata, rkyv::rancor::Error>(archived)
519                .expect("archived metadata always deserializes"),
520        )
521    }
522
523    /// Returns the distribution for the given version, if it exists.
524    fn get(&self, version: &Version) -> Option<&PrioritizedDist> {
525        self.get_lazy(&self.map.get(version)?.dist)
526    }
527
528    /// Returns an iterator over the versions with at least one file within the exclude-newer
529    /// cutoffs, without materializing the distributions.
530    fn included_versions(&self) -> impl DoubleEndedIterator<Item = &Version> {
531        self.map.entries.iter().filter_map(move |entry| {
532            let included = match (&entry.dist.flat, &entry.dist.simple) {
533                // Flat index files have no upload times and bypass the cutoffs.
534                (Some(_), _) => true,
535                (None, Some(simple)) => self.any_file_included(simple),
536                (None, None) => false,
537            };
538            included.then_some(&entry.version)
539        })
540    }
541
542    /// Returns whether at least one file keeps this version inside the candidate universe.
543    ///
544    /// This mirrors the per-file cutoff handling in [`Self::get_simple`] without materializing the
545    /// distribution, including the two cutoff modes' distinct handling of missing upload times.
546    fn any_file_included(&self, simple: &SimplePrioritizedDist) -> bool {
547        if self.included_version_cutoff.is_none() && self.available_version_cutoff.is_none() {
548            return true;
549        }
550        let Some(datum) = self.simple_metadata.datum(simple.datum_index) else {
551            return false;
552        };
553        let files = &datum.files;
554        files
555            .wheels
556            .iter()
557            .chain(files.source_dists.iter())
558            .any(|file| {
559                let upload_time = file.upload_time_utc_ms();
560                let excluded = if let Some(cutoff) = &self.included_version_cutoff {
561                    upload_time.is_none_or(|t| t >= cutoff.as_millisecond())
562                } else if let Some(cutoff) = &self.available_version_cutoff {
563                    upload_time.is_some_and(|t| t >= cutoff.as_millisecond())
564                } else {
565                    false
566                };
567                !excluded
568            })
569    }
570
571    /// Returns whether a version should be materialized during candidate selection.
572    ///
573    /// Missing upload times are retained here, even for `included_version_cutoff`, since
574    /// materializing them is what emits the corresponding `exclude-newer` warning.
575    fn any_file_materializable(&self, simple: &SimplePrioritizedDist) -> bool {
576        let Some(cutoff) = self
577            .included_version_cutoff
578            .as_ref()
579            .or(self.available_version_cutoff.as_ref())
580        else {
581            return true;
582        };
583        let Some(datum) = self.simple_metadata.datum(simple.datum_index) else {
584            return false;
585        };
586        datum
587            .files
588            .wheels
589            .iter()
590            .chain(datum.files.source_dists.iter())
591            .any(|file| {
592                file.upload_time_utc_ms()
593                    .is_none_or(|upload_time| upload_time < cutoff.as_millisecond())
594            })
595    }
596
597    /// Given a reference to a possibly-initialized distribution that is in
598    /// this lazy map, return the corresponding distribution.
599    ///
600    /// When both a flat and simple distribution are present internally, they
601    /// are merged automatically.
602    fn get_lazy<'p>(&'p self, lazy_dist: &'p LazyPrioritizedDist) -> Option<&'p PrioritizedDist> {
603        match (&lazy_dist.flat, &lazy_dist.simple) {
604            (Some(flat), Some(simple)) => self.get_simple(Some(flat), simple),
605            (Some(flat), None) => Some(flat),
606            (None, Some(simple)) => self.get_simple(None, simple),
607            (None, None) => None,
608        }
609    }
610
611    /// Given an optional starting point, return the final form of the
612    /// given simple distribution. If it wasn't initialized yet, then this
613    /// initializes it. If the distribution would otherwise be empty, this
614    /// returns `None`.
615    fn get_simple<'p>(
616        &'p self,
617        init: Option<&'p PrioritizedDist>,
618        simple: &'p SimplePrioritizedDist,
619    ) -> Option<&'p PrioritizedDist> {
620        let get_or_init = || {
621            let files = rkyv::deserialize::<VersionFiles, rkyv::rancor::Error>(
622                &self
623                    .simple_metadata
624                    .datum(simple.datum_index)
625                    .expect("index to lazy dist is correct")
626                    .files,
627            )
628            .expect("archived version files always deserializes");
629            let mut priority_dist = init.cloned().unwrap_or_default();
630            for (filename, file) in files.all(&self.package_name) {
631                // Support resolving as if it were an earlier timestamp, at least as long files have
632                // upload time information.
633                let (excluded, upload_time) = if let Some(included_version_cutoff) =
634                    &self.included_version_cutoff
635                {
636                    match file.upload_time_utc_ms.as_ref() {
637                        Some(&upload_time)
638                            if upload_time >= included_version_cutoff.as_millisecond() =>
639                        {
640                            trace!(
641                                "Excluding `{}` (uploaded {upload_time}) due to exclude-newer ({included_version_cutoff})",
642                                file.filename
643                            );
644                            (true, Some(upload_time))
645                        }
646                        None => {
647                            warn_user_once!(
648                                "{} is missing an upload date, but user provided: {included_version_cutoff}",
649                                file.filename,
650                            );
651                            (true, None)
652                        }
653                        _ => (false, None),
654                    }
655                } else if let Some(available_version_cutoff) = &self.available_version_cutoff {
656                    match file.upload_time_utc_ms.as_ref() {
657                        Some(&upload_time)
658                            if upload_time >= available_version_cutoff.as_millisecond() =>
659                        {
660                            trace!(
661                                "Excluding `{}` (uploaded {upload_time}) due to available version cutoff ({available_version_cutoff})",
662                                file.filename
663                            );
664                            (true, Some(upload_time))
665                        }
666                        _ => (false, None),
667                    }
668                } else {
669                    (false, None)
670                };
671
672                // Prioritize amongst all available files.
673                let yanked = file.yanked.as_deref();
674                let hashes = file.hashes.clone();
675                match filename {
676                    DistFilename::WheelFilename(filename) => {
677                        let compatibility = self.wheel_compatibility(
678                            &filename,
679                            &filename.name,
680                            &filename.version,
681                            hashes.as_slice(),
682                            yanked,
683                            excluded,
684                            upload_time,
685                        );
686                        let dist = RegistryBuiltWheel {
687                            filename,
688                            file: Box::new(file),
689                            index: self.index.clone(),
690                            size_is_authoritative: false,
691                        };
692                        priority_dist.insert_built(dist, hashes, compatibility);
693                    }
694                    DistFilename::SourceDistFilename(filename) => {
695                        let compatibility = self.source_dist_compatibility(
696                            &filename,
697                            hashes.as_slice(),
698                            yanked,
699                            excluded,
700                            upload_time,
701                        );
702                        let dist = RegistrySourceDist {
703                            name: filename.name.clone(),
704                            version: filename.version.clone(),
705                            ext: filename.extension,
706                            file: Box::new(file),
707                            index: self.index.clone(),
708                            wheels: vec![],
709                            size_is_authoritative: false,
710                        };
711                        priority_dist.insert_source(dist, hashes, compatibility);
712                    }
713                }
714            }
715            if priority_dist.is_empty() {
716                None
717            } else {
718                Some(priority_dist)
719            }
720        };
721        simple.dist.get_or_init(get_or_init).as_ref()
722    }
723
724    fn source_dist_compatibility(
725        &self,
726        filename: &SourceDistFilename,
727        hashes: &[HashDigest],
728        yanked: Option<&Yanked>,
729        excluded: bool,
730        upload_time: Option<i64>,
731    ) -> SourceDistCompatibility {
732        // Check if builds are disabled
733        if self.no_build {
734            return SourceDistCompatibility::Incompatible(IncompatibleSource::NoBuild);
735        }
736
737        // Check if after upload time cutoff
738        if excluded {
739            return SourceDistCompatibility::Incompatible(IncompatibleSource::ExcludeNewer(
740                upload_time,
741            ));
742        }
743
744        // Check if yanked
745        if let Some(yanked) = yanked {
746            if yanked.is_yanked()
747                && !self
748                    .allowed_yanks
749                    .contains(&filename.name, &filename.version)
750            {
751                return SourceDistCompatibility::Incompatible(IncompatibleSource::Yanked(
752                    yanked.clone(),
753                ));
754            }
755        }
756
757        // Check if the filename is PEP 625-compliant.
758        // TODO: Strengthen this check more; right now we allow `.zip`
759        // (which is not compliant) and we don't strictly
760        // enforce the formatting rules for the name or version.
761        if !filename.extension.is_pep625_compliant() {
762            return SourceDistCompatibility::Incompatible(IncompatibleSource::NotPep625Filename);
763        }
764
765        // Check if hashes line up. If hashes aren't required, they're considered matching.
766        let hash_policy = self.hasher.get_package(&filename.name, &filename.version);
767        let required_hashes = hash_policy.digests();
768        let hash = if required_hashes.is_empty() {
769            HashComparison::Matched
770        } else {
771            if hashes.is_empty() {
772                HashComparison::Missing
773            } else if hash_policy.matches(hashes) {
774                HashComparison::Matched
775            } else {
776                HashComparison::Mismatched
777            }
778        };
779
780        SourceDistCompatibility::Compatible(hash)
781    }
782
783    fn wheel_compatibility(
784        &self,
785        filename: &WheelFilename,
786        name: &PackageName,
787        version: &Version,
788        hashes: &[HashDigest],
789        yanked: Option<&Yanked>,
790        excluded: bool,
791        upload_time: Option<i64>,
792    ) -> WheelCompatibility {
793        // Check if binaries are disabled
794        if self.no_binary {
795            return WheelCompatibility::Incompatible(IncompatibleWheel::NoBinary);
796        }
797
798        // Check if after upload time cutoff
799        if excluded {
800            return WheelCompatibility::Incompatible(IncompatibleWheel::ExcludeNewer(upload_time));
801        }
802
803        // Check if yanked
804        if let Some(yanked) = yanked {
805            if yanked.is_yanked() && !self.allowed_yanks.contains(name, version) {
806                return WheelCompatibility::Incompatible(IncompatibleWheel::Yanked(yanked.clone()));
807            }
808        }
809
810        // Determine a compatibility for the wheel based on tags.
811        let priority = if let Some(tags) = &self.tags {
812            match filename.compatibility(tags) {
813                TagCompatibility::Incompatible(tag) => {
814                    return WheelCompatibility::Incompatible(IncompatibleWheel::Tag(tag));
815                }
816                TagCompatibility::Compatible(priority) => Some(priority),
817            }
818        } else {
819            // Check if the wheel is compatible with the `requires-python` (i.e., the Python
820            // ABI tag is not less than the `requires-python` minimum version).
821            if !self.requires_python.matches_wheel_tag(filename) {
822                return WheelCompatibility::Incompatible(IncompatibleWheel::Tag(
823                    IncompatibleTag::AbiPythonVersion,
824                ));
825            }
826            None
827        };
828
829        // Check if hashes line up. If hashes aren't required, they're considered matching.
830        let hash_policy = self.hasher.get_package(name, version);
831        let required_hashes = hash_policy.digests();
832        let hash = if required_hashes.is_empty() {
833            HashComparison::Matched
834        } else {
835            if hashes.is_empty() {
836                HashComparison::Missing
837            } else if hash_policy.matches(hashes) {
838                HashComparison::Matched
839            } else {
840                HashComparison::Mismatched
841            }
842        };
843
844        // Break ties with the build tag.
845        let build_tag = filename.build_tag().cloned();
846
847        WheelCompatibility::Compatible(hash, priority, build_tag)
848    }
849}
850
851/// Represents a possibly initialized [`PrioritizedDist`] for a package version.
852#[derive(Debug)]
853struct LazyPrioritizedDist {
854    /// An eagerly constructed distribution from [`FlatDistributions`], if present.
855    flat: Option<PrioritizedDist>,
856    /// A lazy index into [`SimpleDetailMetadata`], if present.
857    simple: Option<SimplePrioritizedDist>,
858}
859
860/// Represents a lazily initialized `PrioritizedDist`.
861#[derive(Debug)]
862struct SimplePrioritizedDist {
863    /// An offset into `SimpleDetailMetadata` corresponding to a `SimpleMetadatum`.
864    /// This provides access to a `VersionFiles` that is used to construct a
865    /// `PrioritizedDist`.
866    datum_index: usize,
867    /// A lazily initialized distribution.
868    ///
869    /// Note that the `Option` does not represent the initialization state.
870    /// The `Option` can be `None` even after initialization, for example,
871    /// if initialization could not find any usable files from which to
872    /// construct a distribution. (One easy way to effect this, at the time
873    /// of writing, is to use `--exclude-newer 1900-01-01`.)
874    dist: OnceLock<Option<PrioritizedDist>>,
875}
876
877/// A range that can be used to iterate over a subset of a [`BTreeMap`].
878#[derive(Debug)]
879struct BoundingRange<'a> {
880    min: Bound<&'a Version>,
881    max: Bound<&'a Version>,
882}
883
884impl<'a> From<&'a Ranges<Version>> for BoundingRange<'a> {
885    fn from(value: &'a Ranges<Version>) -> Self {
886        let (min, max) = value
887            .bounding_range()
888            .unwrap_or((Bound::Unbounded, Bound::Unbounded));
889        Self { min, max }
890    }
891}
892
893impl<'a> RangeBounds<Version> for BoundingRange<'a> {
894    fn start_bound(&self) -> Bound<&'a Version> {
895        self.min
896    }
897
898    fn end_bound(&self) -> Bound<&'a Version> {
899        self.max
900    }
901}
uv_resolver/version_map.rs

uv_resolver/
version_map.rs
