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    IndexUrl, MinimumLibcVersion, RegistryBuiltWheel, RegistrySourceDist, RequiresPython,
15};
16use uv_normalize::PackageName;
17use uv_pep440::Version;
18use uv_platform_tags::{IncompatibleTag, TagCompatibility, Tags};
19use uv_pypi_types::{HashDigest, ResolutionMetadata, Yanked};
20use uv_types::HashStrategy;
21use uv_warnings::warn_user_once;
22
23use crate::flat_index::FlatDistributions;
24use crate::prioritized_distribution::{
25    HashComparison, IncompatibleSource, IncompatibleWheel, PrioritizedDist,
26    SourceDistCompatibility, WheelCompatibility,
27};
28use crate::yanks::AllowedYanks;
29
30/// A map from versions to distributions.
31#[derive(Debug)]
32pub struct VersionMap {
33    /// The inner representation of the version map.
34    inner: VersionMapInner,
35}
36
37impl VersionMap {
38    /// Initialize a [`VersionMap`] from the given metadata.
39    ///
40    /// Note it is possible for files to have a different yank status per PEP 592 but in the official
41    /// PyPI warehouse this cannot happen.
42    ///
43    /// Here, we track if each file is yanked separately. If a release is partially yanked, the
44    /// unyanked distributions _can_ be used.
45    ///
46    /// PEP 592: <https://peps.python.org/pep-0592/#warehouse-pypi-implementation-notes>
47    #[instrument(skip_all, fields(package_name))]
48    pub(crate) fn from_simple_metadata(
49        simple_metadata: OwnedArchive<SimpleDetailMetadata>,
50        package_name: &PackageName,
51        index: IndexUrl,
52        tags: Option<Tags>,
53        requires_python: RequiresPython,
54        allowed_yanks: AllowedYanks,
55        hasher: HashStrategy,
56        included_version_cutoff: Option<Timestamp>,
57        available_version_cutoff: Option<Timestamp>,
58        flat_index: Option<FlatDistributions>,
59        build_options: &BuildOptions,
60        minimum_libc_version: Option<MinimumLibcVersion>,
61    ) -> Self {
62        let mut local = false;
63        let mut entries = Vec::with_capacity(simple_metadata.iter().size_hint().0);
64        // Create stubs for each entry in simple metadata. The full conversion
65        // from a `VersionFiles` to a PrioritizedDist for each version
66        // isn't done until that specific version is requested.
67        for (datum_index, datum) in simple_metadata.iter().enumerate() {
68            let version = rkyv::deserialize::<Version, rkyv::rancor::Error>(&datum.version)
69                .expect("archived version always deserializes");
70
71            local |= version.is_local();
72            debug_assert!(
73                entries
74                    .last()
75                    .is_none_or(|entry: &VersionMapLazyEntry| entry.version < version),
76                "simple metadata versions must be sorted and unique"
77            );
78            entries.push(VersionMapLazyEntry {
79                version,
80                dist: LazyPrioritizedDist {
81                    flat: None,
82                    simple: Some(SimplePrioritizedDist {
83                        datum_index,
84                        dist: OnceLock::new(),
85                    }),
86                },
87            });
88        }
89        let mut map = VersionMapLazyIndex { entries };
90        // If a set of flat distributions have been given, linearly merge the
91        // already sorted flat entries with the archive-ordered simple vector.
92        if let Some(flat_index) = flat_index {
93            map = map.merge_flat(flat_index);
94        }
95        Self {
96            inner: VersionMapInner::Lazy(VersionMapLazy {
97                package_name: package_name.clone(),
98                map,
99                local,
100                simple_metadata,
101                no_binary: build_options.no_binary_package(package_name),
102                no_build: build_options.no_build_package(package_name),
103                index,
104                tags,
105                allowed_yanks,
106                hasher,
107                requires_python,
108                included_version_cutoff,
109                available_version_cutoff,
110                minimum_libc_version,
111            }),
112        }
113    }
114
115    #[instrument(skip_all, fields(package_name))]
116    pub(crate) fn from_flat_metadata(
117        flat_metadata: Vec<FlatIndexEntry>,
118        tags: Option<&Tags>,
119        hasher: &HashStrategy,
120        build_options: &BuildOptions,
121        minimum_libc_version: Option<MinimumLibcVersion>,
122    ) -> Self {
123        FlatDistributions::from_entries(
124            flat_metadata,
125            tags,
126            hasher,
127            build_options,
128            minimum_libc_version,
129        )
130        .into()
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    /// The libc baselines required during universal resolution.
507    minimum_libc_version: Option<MinimumLibcVersion>,
508}
509
510impl VersionMapLazy {
511    /// Returns the registry-provided metadata for the given version, if it exists.
512    fn get_metadata(&self, version: &Version) -> Option<ResolutionMetadata> {
513        let archived = self
514            .map
515            .get(version)
516            .and_then(|entry| entry.dist.simple.as_ref())
517            .and_then(|simple| self.simple_metadata.datum(simple.datum_index))
518            .and_then(|datum| datum.metadata.as_deref())?;
519        Some(
520            rkyv::deserialize::<ResolutionMetadata, rkyv::rancor::Error>(archived)
521                .expect("archived metadata always deserializes"),
522        )
523    }
524
525    /// Returns the distribution for the given version, if it exists.
526    fn get(&self, version: &Version) -> Option<&PrioritizedDist> {
527        self.get_lazy(&self.map.get(version)?.dist)
528    }
529
530    /// Returns an iterator over the versions with at least one file within the exclude-newer
531    /// cutoffs, without materializing the distributions.
532    fn included_versions(&self) -> impl DoubleEndedIterator<Item = &Version> {
533        self.map.entries.iter().filter_map(move |entry| {
534            let included = match (&entry.dist.flat, &entry.dist.simple) {
535                // Flat index files have no upload times and bypass the cutoffs.
536                (Some(_), _) => true,
537                (None, Some(simple)) => self.any_file_included(simple),
538                (None, None) => false,
539            };
540            included.then_some(&entry.version)
541        })
542    }
543
544    /// Returns whether at least one file keeps this version inside the candidate universe.
545    ///
546    /// This mirrors the per-file cutoff handling in [`Self::get_simple`] without materializing the
547    /// distribution, including the two cutoff modes' distinct handling of missing upload times.
548    fn any_file_included(&self, simple: &SimplePrioritizedDist) -> bool {
549        if self.included_version_cutoff.is_none() && self.available_version_cutoff.is_none() {
550            return true;
551        }
552        let Some(datum) = self.simple_metadata.datum(simple.datum_index) else {
553            return false;
554        };
555        let files = &datum.files;
556        files
557            .wheels
558            .iter()
559            .chain(files.source_dists.iter())
560            .any(|file| {
561                let upload_time = file.upload_time_utc_ms();
562                let excluded = if let Some(cutoff) = &self.included_version_cutoff {
563                    upload_time.is_none_or(|t| t >= cutoff.as_millisecond())
564                } else if let Some(cutoff) = &self.available_version_cutoff {
565                    upload_time.is_some_and(|t| t >= cutoff.as_millisecond())
566                } else {
567                    false
568                };
569                !excluded
570            })
571    }
572
573    /// Returns whether a version should be materialized during candidate selection.
574    ///
575    /// Missing upload times are retained here, even for `included_version_cutoff`, since
576    /// materializing them is what emits the corresponding `exclude-newer` warning.
577    fn any_file_materializable(&self, simple: &SimplePrioritizedDist) -> bool {
578        let Some(cutoff) = self
579            .included_version_cutoff
580            .as_ref()
581            .or(self.available_version_cutoff.as_ref())
582        else {
583            return true;
584        };
585        let Some(datum) = self.simple_metadata.datum(simple.datum_index) else {
586            return false;
587        };
588        datum
589            .files
590            .wheels
591            .iter()
592            .chain(datum.files.source_dists.iter())
593            .any(|file| {
594                file.upload_time_utc_ms()
595                    .is_none_or(|upload_time| upload_time < cutoff.as_millisecond())
596            })
597    }
598
599    /// Given a reference to a possibly-initialized distribution that is in
600    /// this lazy map, return the corresponding distribution.
601    ///
602    /// When both a flat and simple distribution are present internally, they
603    /// are merged automatically.
604    fn get_lazy<'p>(&'p self, lazy_dist: &'p LazyPrioritizedDist) -> Option<&'p PrioritizedDist> {
605        match (&lazy_dist.flat, &lazy_dist.simple) {
606            (Some(flat), Some(simple)) => self.get_simple(Some(flat), simple),
607            (Some(flat), None) => Some(flat),
608            (None, Some(simple)) => self.get_simple(None, simple),
609            (None, None) => None,
610        }
611    }
612
613    /// Given an optional starting point, return the final form of the
614    /// given simple distribution. If it wasn't initialized yet, then this
615    /// initializes it. If the distribution would otherwise be empty, this
616    /// returns `None`.
617    fn get_simple<'p>(
618        &'p self,
619        init: Option<&'p PrioritizedDist>,
620        simple: &'p SimplePrioritizedDist,
621    ) -> Option<&'p PrioritizedDist> {
622        let get_or_init = || {
623            let files = rkyv::deserialize::<VersionFiles, rkyv::rancor::Error>(
624                &self
625                    .simple_metadata
626                    .datum(simple.datum_index)
627                    .expect("index to lazy dist is correct")
628                    .files,
629            )
630            .expect("archived version files always deserializes");
631            let mut priority_dist = init.cloned().unwrap_or_default();
632            for (filename, file) in files.all(&self.package_name) {
633                // Support resolving as if it were an earlier timestamp, at least as long files have
634                // upload time information.
635                let (excluded, upload_time) = if let Some(included_version_cutoff) =
636                    &self.included_version_cutoff
637                {
638                    match file.upload_time_utc_ms.as_ref() {
639                        Some(&upload_time)
640                            if upload_time >= included_version_cutoff.as_millisecond() =>
641                        {
642                            trace!(
643                                "Excluding `{}` (uploaded {upload_time}) due to exclude-newer ({included_version_cutoff})",
644                                file.filename
645                            );
646                            (true, Some(upload_time))
647                        }
648                        None => {
649                            warn_user_once!(
650                                "`{}` is missing an upload date, but user provided: {included_version_cutoff}",
651                                file.filename,
652                            );
653                            (true, None)
654                        }
655                        _ => (false, None),
656                    }
657                } else if let Some(available_version_cutoff) = &self.available_version_cutoff {
658                    match file.upload_time_utc_ms.as_ref() {
659                        Some(&upload_time)
660                            if upload_time >= available_version_cutoff.as_millisecond() =>
661                        {
662                            trace!(
663                                "Excluding `{}` (uploaded {upload_time}) due to available version cutoff ({available_version_cutoff})",
664                                file.filename
665                            );
666                            (true, Some(upload_time))
667                        }
668                        _ => (false, None),
669                    }
670                } else {
671                    (false, None)
672                };
673
674                // Prioritize amongst all available files.
675                let yanked = file.yanked.as_deref();
676                let hashes = file.hashes.clone();
677                match filename {
678                    DistFilename::WheelFilename(filename) => {
679                        let compatibility = self.wheel_compatibility(
680                            &filename,
681                            &filename.name,
682                            &filename.version,
683                            hashes.as_slice(),
684                            yanked,
685                            excluded,
686                            upload_time,
687                        );
688                        let dist = RegistryBuiltWheel {
689                            filename,
690                            file: Box::new(file),
691                            index: self.index.clone(),
692                            size_is_authoritative: false,
693                        };
694                        priority_dist.insert_built(
695                            dist,
696                            hashes,
697                            compatibility,
698                            self.minimum_libc_version,
699                        );
700                    }
701                    DistFilename::SourceDistFilename(filename) => {
702                        let compatibility = self.source_dist_compatibility(
703                            &filename,
704                            hashes.as_slice(),
705                            yanked,
706                            excluded,
707                            upload_time,
708                        );
709                        let dist = RegistrySourceDist {
710                            name: filename.name.clone(),
711                            version: filename.version.clone(),
712                            ext: filename.extension,
713                            file: Box::new(file),
714                            index: self.index.clone(),
715                            wheels: vec![],
716                            size_is_authoritative: false,
717                        };
718                        priority_dist.insert_source(dist, hashes, compatibility);
719                    }
720                }
721            }
722            if priority_dist.is_empty() {
723                None
724            } else {
725                Some(priority_dist)
726            }
727        };
728        simple.dist.get_or_init(get_or_init).as_ref()
729    }
730
731    fn source_dist_compatibility(
732        &self,
733        filename: &SourceDistFilename,
734        hashes: &[HashDigest],
735        yanked: Option<&Yanked>,
736        excluded: bool,
737        upload_time: Option<i64>,
738    ) -> SourceDistCompatibility {
739        // Check if after upload time cutoff
740        if excluded {
741            return SourceDistCompatibility::Incompatible(IncompatibleSource::ExcludeNewer(
742                upload_time,
743            ));
744        }
745
746        // Check if builds are disabled
747        if self.no_build {
748            return SourceDistCompatibility::Incompatible(IncompatibleSource::NoBuild);
749        }
750
751        // Check if yanked
752        if let Some(yanked) = yanked {
753            if yanked.is_yanked()
754                && !self
755                    .allowed_yanks
756                    .contains(&filename.name, &filename.version)
757            {
758                return SourceDistCompatibility::Incompatible(IncompatibleSource::Yanked(
759                    yanked.clone(),
760                ));
761            }
762        }
763
764        // Check if the filename is PEP 625-compliant.
765        // TODO: Strengthen this check more; right now we allow `.zip`
766        // (which is not compliant) and we don't strictly
767        // enforce the formatting rules for the name or version.
768        if !filename.extension.is_pep625_compliant() {
769            return SourceDistCompatibility::Incompatible(IncompatibleSource::NotPep625Filename);
770        }
771
772        // Check if hashes line up. If hashes aren't required, they're considered matching.
773        let hash_policy = self
774            .hasher
775            .archive_policy_for_package(&filename.name, &filename.version);
776        let required_hashes = hash_policy.digests();
777        let hash = if required_hashes.is_empty() {
778            HashComparison::Matched
779        } else {
780            if hashes.is_empty() {
781                HashComparison::Missing
782            } else if hash_policy.matches(hashes) {
783                HashComparison::Matched
784            } else {
785                HashComparison::Mismatched
786            }
787        };
788
789        SourceDistCompatibility::Compatible(hash)
790    }
791
792    fn wheel_compatibility(
793        &self,
794        filename: &WheelFilename,
795        name: &PackageName,
796        version: &Version,
797        hashes: &[HashDigest],
798        yanked: Option<&Yanked>,
799        excluded: bool,
800        upload_time: Option<i64>,
801    ) -> WheelCompatibility {
802        // Check if after upload time cutoff
803        if excluded {
804            return WheelCompatibility::Incompatible(IncompatibleWheel::ExcludeNewer(upload_time));
805        }
806
807        // Check if binaries are disabled
808        if self.no_binary {
809            return WheelCompatibility::Incompatible(IncompatibleWheel::NoBinary);
810        }
811
812        // Check if yanked
813        if let Some(yanked) = yanked {
814            if yanked.is_yanked() && !self.allowed_yanks.contains(name, version) {
815                return WheelCompatibility::Incompatible(IncompatibleWheel::Yanked(yanked.clone()));
816            }
817        }
818
819        // Determine a compatibility for the wheel based on tags.
820        let priority = if let Some(tags) = &self.tags {
821            match filename.compatibility(tags) {
822                TagCompatibility::Incompatible(tag) => {
823                    return WheelCompatibility::Incompatible(IncompatibleWheel::Tag(tag));
824                }
825                TagCompatibility::Compatible(priority) => Some(priority),
826            }
827        } else {
828            // Check if the wheel is compatible with the `requires-python` (i.e., the Python
829            // ABI tag is not less than the `requires-python` minimum version).
830            if !self.requires_python.matches_wheel_tag(filename) {
831                return WheelCompatibility::Incompatible(IncompatibleWheel::Tag(
832                    IncompatibleTag::AbiPythonVersion,
833                ));
834            }
835            None
836        };
837
838        // Check if hashes line up. If hashes aren't required, they're considered matching.
839        let hash_policy = self.hasher.archive_policy_for_package(name, version);
840        let required_hashes = hash_policy.digests();
841        let hash = if required_hashes.is_empty() {
842            HashComparison::Matched
843        } else {
844            if hashes.is_empty() {
845                HashComparison::Missing
846            } else if hash_policy.matches(hashes) {
847                HashComparison::Matched
848            } else {
849                HashComparison::Mismatched
850            }
851        };
852
853        // Break ties with the build tag.
854        let build_tag = filename.build_tag().cloned();
855
856        WheelCompatibility::Compatible(hash, priority, build_tag)
857    }
858}
859
860/// Represents a possibly initialized [`PrioritizedDist`] for a package version.
861#[derive(Debug)]
862struct LazyPrioritizedDist {
863    /// An eagerly constructed distribution from [`FlatDistributions`], if present.
864    flat: Option<PrioritizedDist>,
865    /// A lazy index into [`SimpleDetailMetadata`], if present.
866    simple: Option<SimplePrioritizedDist>,
867}
868
869/// Represents a lazily initialized `PrioritizedDist`.
870#[derive(Debug)]
871struct SimplePrioritizedDist {
872    /// An offset into `SimpleDetailMetadata` corresponding to a `SimpleMetadatum`.
873    /// This provides access to a `VersionFiles` that is used to construct a
874    /// `PrioritizedDist`.
875    datum_index: usize,
876    /// A lazily initialized distribution.
877    ///
878    /// Note that the `Option` does not represent the initialization state.
879    /// The `Option` can be `None` even after initialization, for example,
880    /// if initialization could not find any usable files from which to
881    /// construct a distribution. (One easy way to effect this, at the time
882    /// of writing, is to use `--exclude-newer 1900-01-01`.)
883    dist: OnceLock<Option<PrioritizedDist>>,
884}
885
886/// A range that can be used to iterate over a subset of a [`BTreeMap`].
887#[derive(Debug)]
888struct BoundingRange<'a> {
889    min: Bound<&'a Version>,
890    max: Bound<&'a Version>,
891}
892
893impl<'a> From<&'a Ranges<Version>> for BoundingRange<'a> {
894    fn from(value: &'a Ranges<Version>) -> Self {
895        let (min, max) = value
896            .bounding_range()
897            .unwrap_or((Bound::Unbounded, Bound::Unbounded));
898        Self { min, max }
899    }
900}
901
902impl<'a> RangeBounds<Version> for BoundingRange<'a> {
903    fn start_bound(&self) -> Bound<&'a Version> {
904        self.min
905    }
906
907    fn end_bound(&self) -> Bound<&'a Version> {
908        self.max
909    }
910}
uv_resolver/version_map.rs

uv_resolver/
version_map.rs
