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, MinimumLibcVersion,
15    PrioritizedDist, RegistryBuiltWheel, RegistrySourceDist, RequiresPython,
16    SourceDistCompatibility, 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        minimum_libc_version: Option<MinimumLibcVersion>,
59    ) -> Self {
60        let mut local = false;
61        let mut entries = Vec::with_capacity(simple_metadata.iter().size_hint().0);
62        // Create stubs for each entry in simple metadata. The full conversion
63        // from a `VersionFiles` to a PrioritizedDist for each version
64        // isn't done until that specific version is requested.
65        for (datum_index, datum) in simple_metadata.iter().enumerate() {
66            let version = rkyv::deserialize::<Version, rkyv::rancor::Error>(&datum.version)
67                .expect("archived version always deserializes");
68
69            local |= version.is_local();
70            debug_assert!(
71                entries
72                    .last()
73                    .is_none_or(|entry: &VersionMapLazyEntry| entry.version < version),
74                "simple metadata versions must be sorted and unique"
75            );
76            entries.push(VersionMapLazyEntry {
77                version,
78                dist: LazyPrioritizedDist {
79                    flat: None,
80                    simple: Some(SimplePrioritizedDist {
81                        datum_index,
82                        dist: OnceLock::new(),
83                    }),
84                },
85            });
86        }
87        let mut map = VersionMapLazyIndex { entries };
88        // If a set of flat distributions have been given, linearly merge the
89        // already sorted flat entries with the archive-ordered simple vector.
90        if let Some(flat_index) = flat_index {
91            map = map.merge_flat(flat_index);
92        }
93        Self {
94            inner: VersionMapInner::Lazy(VersionMapLazy {
95                package_name: package_name.clone(),
96                map,
97                local,
98                simple_metadata,
99                no_binary: build_options.no_binary_package(package_name),
100                no_build: build_options.no_build_package(package_name),
101                index,
102                tags,
103                allowed_yanks,
104                hasher,
105                requires_python,
106                included_version_cutoff,
107                available_version_cutoff,
108                minimum_libc_version,
109            }),
110        }
111    }
112
113    #[instrument(skip_all, fields(package_name))]
114    pub(crate) fn from_flat_metadata(
115        flat_metadata: Vec<FlatIndexEntry>,
116        tags: Option<&Tags>,
117        hasher: &HashStrategy,
118        build_options: &BuildOptions,
119        minimum_libc_version: Option<MinimumLibcVersion>,
120    ) -> Self {
121        FlatDistributions::from_entries(
122            flat_metadata,
123            tags,
124            hasher,
125            build_options,
126            minimum_libc_version,
127        )
128        .into()
129    }
130
131    /// Return the [`ResolutionMetadata`] for the given version, if any.
132    pub(crate) fn get_metadata(&self, version: &Version) -> Option<ResolutionMetadata> {
133        match self.inner {
134            VersionMapInner::Eager(_) => None,
135            VersionMapInner::Lazy(ref lazy) => lazy.get_metadata(version),
136        }
137    }
138
139    /// Return the [`DistFile`] for the given version, if any.
140    pub(crate) fn get(&self, version: &Version) -> Option<&PrioritizedDist> {
141        match self.inner {
142            VersionMapInner::Eager(ref eager) => eager.map.get(version),
143            VersionMapInner::Lazy(ref lazy) => lazy.get(version),
144        }
145    }
146
147    /// Return an iterator over the versions in this map.
148    pub(crate) fn versions(&self) -> impl DoubleEndedIterator<Item = &Version> {
149        match &self.inner {
150            VersionMapInner::Eager(eager) => either::Either::Left(eager.map.keys()),
151            VersionMapInner::Lazy(lazy) => either::Either::Right(lazy.map.keys()),
152        }
153    }
154
155    /// Returns versions with at least one file not excluded by an upload-time cutoff, in ascending
156    /// order.
157    ///
158    /// Versions unavailable for other reasons remain present so callers receive a conservative
159    /// superset of selectable versions. These reasons include yanks, hashes, `requires-python`,
160    /// and `--no-binary` or `--no-build` policies. Flat-index versions bypass upload-time cutoffs
161    /// because their files do not carry upload times.
162    pub(crate) fn included_versions(&self) -> impl DoubleEndedIterator<Item = &Version> {
163        match &self.inner {
164            VersionMapInner::Eager(eager) => either::Either::Left(eager.map.keys()),
165            VersionMapInner::Lazy(lazy) => either::Either::Right(lazy.included_versions()),
166        }
167    }
168
169    /// Return the index URL where this package came from.
170    pub(crate) fn index(&self) -> Option<&IndexUrl> {
171        match &self.inner {
172            VersionMapInner::Eager(_) => None,
173            VersionMapInner::Lazy(lazy) => Some(&lazy.index),
174        }
175    }
176
177    /// Return the included-version cutoff for this version map, if any.
178    pub(crate) fn included_version_cutoff(&self) -> Option<&Timestamp> {
179        match &self.inner {
180            VersionMapInner::Eager(_) => None,
181            VersionMapInner::Lazy(lazy) => lazy.included_version_cutoff.as_ref(),
182        }
183    }
184
185    /// Return an iterator over the versions and distributions.
186    ///
187    /// Note that the value returned in this iterator is a [`VersionMapDist`],
188    /// which can be used to lazily request a [`CompatibleDist`]. This is
189    /// useful in cases where one can skip materializing a full distribution
190    /// for each version.
191    pub(crate) fn iter(
192        &self,
193        range: &Ranges<Version>,
194    ) -> impl DoubleEndedIterator<Item = (&Version, VersionMapDistHandle<'_>)> {
195        // Performance optimization: If we only have a single version, return that version directly.
196        if let Some(version) = range.as_singleton() {
197            either::Either::Left(match self.inner {
198                VersionMapInner::Eager(ref eager) => {
199                    either::Either::Left(eager.map.get_key_value(version).into_iter().map(
200                        move |(version, dist)| {
201                            let version_map_dist = VersionMapDistHandle {
202                                inner: VersionMapDistHandleInner::Eager(dist),
203                            };
204                            (version, version_map_dist)
205                        },
206                    ))
207                }
208                VersionMapInner::Lazy(ref lazy) => {
209                    either::Either::Right(lazy.map.get(version).into_iter().map(move |entry| {
210                        let version_map_dist = VersionMapDistHandle {
211                            inner: VersionMapDistHandleInner::Lazy {
212                                lazy,
213                                dist: &entry.dist,
214                            },
215                        };
216                        (&entry.version, version_map_dist)
217                    }))
218                }
219            })
220        } else {
221            either::Either::Right(match self.inner {
222                VersionMapInner::Eager(ref eager) => {
223                    either::Either::Left(eager.map.range(BoundingRange::from(range)).map(
224                        |(version, dist)| {
225                            let version_map_dist = VersionMapDistHandle {
226                                inner: VersionMapDistHandleInner::Eager(dist),
227                            };
228                            (version, version_map_dist)
229                        },
230                    ))
231                }
232                VersionMapInner::Lazy(ref lazy) => {
233                    either::Either::Right(lazy.map.range(BoundingRange::from(range)).iter().map(
234                        |entry| {
235                            let version_map_dist = VersionMapDistHandle {
236                                inner: VersionMapDistHandleInner::Lazy {
237                                    lazy,
238                                    dist: &entry.dist,
239                                },
240                            };
241                            (&entry.version, version_map_dist)
242                        },
243                    ))
244                }
245            })
246        }
247    }
248
249    /// Return an iterator over the versions that can be considered for selection.
250    ///
251    /// Unlike [`Self::iter`], this skips lazy registry versions whose files are all excluded by
252    /// an upload-time cutoff without materializing their distributions. Files without an upload
253    /// time remain included so that materialization can emit the appropriate warning.
254    pub(crate) fn iter_included(
255        &self,
256        range: &Ranges<Version>,
257    ) -> impl DoubleEndedIterator<Item = (&Version, VersionMapDistHandle<'_>)> {
258        self.iter(range).filter(|(_, dist)| dist.is_included())
259    }
260
261    /// Return the [`Hashes`] for the given version, if any.
262    pub(crate) fn hashes(&self, version: &Version) -> Option<&[HashDigest]> {
263        match self.inner {
264            VersionMapInner::Eager(ref eager) => {
265                eager.map.get(version).map(PrioritizedDist::hashes)
266            }
267            VersionMapInner::Lazy(ref lazy) => lazy.get(version).map(PrioritizedDist::hashes),
268        }
269    }
270
271    /// Returns the total number of distinct versions in this map.
272    ///
273    /// Note that this may include versions of distributions that are not
274    /// usable in the current environment.
275    pub(crate) fn len(&self) -> usize {
276        match self.inner {
277            VersionMapInner::Eager(VersionMapEager { ref map, .. }) => map.len(),
278            VersionMapInner::Lazy(VersionMapLazy { ref map, .. }) => map.len(),
279        }
280    }
281
282    /// Returns `true` if the map contains at least one local version (e.g., `2.6.0+cpu`).
283    pub(crate) fn local(&self) -> bool {
284        match self.inner {
285            VersionMapInner::Eager(ref map) => map.local,
286            VersionMapInner::Lazy(ref map) => map.local,
287        }
288    }
289}
290
291impl From<FlatDistributions> for VersionMap {
292    fn from(flat_index: FlatDistributions) -> Self {
293        let local = flat_index.iter().any(|(version, _)| version.is_local());
294        let map = flat_index.into();
295        Self {
296            inner: VersionMapInner::Eager(VersionMapEager { map, local }),
297        }
298    }
299}
300
301/// A lazily initialized distribution.
302///
303/// This permits access to a handle that can be turned into a resolvable
304/// distribution when desired. This is coupled with a `Version` in
305/// [`VersionMap::iter`] to permit iteration over all items in a map without
306/// necessarily constructing a distribution for every version if it isn't
307/// needed.
308///
309/// Note that because of laziness, not all such items can be turned into
310/// a valid distribution. For example, if in the process of building a
311/// distribution no compatible wheel or source distribution could be found,
312/// then building a `CompatibleDist` will fail.
313pub(crate) struct VersionMapDistHandle<'a> {
314    inner: VersionMapDistHandleInner<'a>,
315}
316
317enum VersionMapDistHandleInner<'a> {
318    Eager(&'a PrioritizedDist),
319    Lazy {
320        lazy: &'a VersionMapLazy,
321        dist: &'a LazyPrioritizedDist,
322    },
323}
324
325impl<'a> VersionMapDistHandle<'a> {
326    /// Returns whether this distribution can be considered for selection.
327    fn is_included(&self) -> bool {
328        match self.inner {
329            VersionMapDistHandleInner::Eager(_) => true,
330            VersionMapDistHandleInner::Lazy { lazy, dist } => match (&dist.flat, &dist.simple) {
331                (Some(_), _) => true,
332                (None, Some(simple)) => lazy.any_file_materializable(simple),
333                (None, None) => false,
334            },
335        }
336    }
337
338    /// Returns a prioritized distribution from this handle.
339    pub(crate) fn prioritized_dist(&self) -> Option<&'a PrioritizedDist> {
340        match self.inner {
341            VersionMapDistHandleInner::Eager(dist) => Some(dist),
342            VersionMapDistHandleInner::Lazy { lazy, dist } => Some(lazy.get_lazy(dist)?),
343        }
344    }
345}
346
347/// The kind of internal version map we have.
348#[derive(Debug)]
349#[expect(clippy::large_enum_variant)]
350enum VersionMapInner {
351    /// All distributions are fully materialized in memory.
352    ///
353    /// This usually happens when one needs a `VersionMap` from a
354    /// `FlatDistributions`.
355    Eager(VersionMapEager),
356    /// Some distributions might be fully materialized (i.e., by initializing
357    /// a `VersionMap` with a `FlatDistributions`), but some distributions
358    /// might still be in their "raw" `SimpleDetailMetadata` format. In this case, a
359    /// `PrioritizedDist` isn't actually created in memory until the
360    /// specific version has been requested.
361    Lazy(VersionMapLazy),
362}
363
364/// A map from versions to distributions that are fully materialized in memory.
365#[derive(Debug)]
366struct VersionMapEager {
367    /// A map from version to distribution.
368    map: BTreeMap<Version, PrioritizedDist>,
369    /// Whether the version map contains at least one local version.
370    local: bool,
371}
372
373/// An entry in the immutable lazy version index.
374#[derive(Debug)]
375struct VersionMapLazyEntry {
376    version: Version,
377    dist: LazyPrioritizedDist,
378}
379
380/// A compact immutable version index, ordered by native PEP 440 versions.
381#[derive(Debug)]
382struct VersionMapLazyIndex {
383    entries: Vec<VersionMapLazyEntry>,
384}
385
386impl VersionMapLazyIndex {
387    /// Merge the sorted flat index into the sorted simple entries in one pass.
388    fn merge_flat(self, flat_index: FlatDistributions) -> Self {
389        let flat_count = flat_index.iter().size_hint().0;
390        let mut merged = Vec::with_capacity(self.entries.len() + flat_count);
391        let mut simple = self.entries.into_iter().peekable();
392        let mut flat = flat_index.into_iter().peekable();
393        let flat_entry = |(version, dist)| VersionMapLazyEntry {
394            version,
395            dist: LazyPrioritizedDist {
396                flat: Some(dist),
397                simple: None,
398            },
399        };
400        while let (Some(simple_entry), Some((flat_version, _))) = (simple.peek(), flat.peek()) {
401            match simple_entry.version.cmp(flat_version) {
402                std::cmp::Ordering::Less => {
403                    if let Some(entry) = simple.next() {
404                        merged.push(entry);
405                    }
406                }
407                std::cmp::Ordering::Greater => {
408                    if let Some(entry) = flat.next() {
409                        merged.push(flat_entry(entry));
410                    }
411                }
412                std::cmp::Ordering::Equal => {
413                    if let (Some(mut entry), Some((_, dist))) = (simple.next(), flat.next()) {
414                        entry.dist.flat = Some(dist);
415                        merged.push(entry);
416                    }
417                }
418            }
419        }
420        merged.extend(simple);
421        merged.extend(flat.map(flat_entry));
422
423        Self { entries: merged }
424    }
425
426    fn get(&self, version: &Version) -> Option<&VersionMapLazyEntry> {
427        let index = self
428            .entries
429            .binary_search_by(|entry| entry.version.cmp(version))
430            .ok()?;
431        self.entries.get(index)
432    }
433
434    fn keys(&self) -> impl DoubleEndedIterator<Item = &Version> {
435        self.entries.iter().map(|entry| &entry.version)
436    }
437
438    fn range(&self, range: BoundingRange<'_>) -> &[VersionMapLazyEntry] {
439        let start = match range.min {
440            Bound::Included(version) => self
441                .entries
442                .partition_point(|entry| entry.version < *version),
443            Bound::Excluded(version) => self
444                .entries
445                .partition_point(|entry| entry.version <= *version),
446            Bound::Unbounded => 0,
447        };
448        let end = match range.max {
449            Bound::Included(version) => self
450                .entries
451                .partition_point(|entry| entry.version <= *version),
452            Bound::Excluded(version) => self
453                .entries
454                .partition_point(|entry| entry.version < *version),
455            Bound::Unbounded => self.entries.len(),
456        };
457        self.entries.get(start..end).unwrap_or_default()
458    }
459
460    fn len(&self) -> usize {
461        self.entries.len()
462    }
463}
464
465/// A map that lazily materializes some prioritized distributions upon access.
466///
467/// The idea here is that some packages have a lot of versions published, and
468/// needing to materialize a full `VersionMap` with all corresponding metadata
469/// for every version in memory is expensive. Since a `SimpleDetailMetadata` can be
470/// materialized with very little cost (via `rkyv` in the warm cached case),
471/// avoiding another conversion step into a fully filled out `VersionMap` can
472/// provide substantial savings in some cases.
473#[derive(Debug)]
474struct VersionMapLazy {
475    /// The normalized package name used to reconstruct cached wheel filenames.
476    package_name: PackageName,
477    /// An immutable archive-order index from version to possibly-initialized distribution.
478    map: VersionMapLazyIndex,
479    /// Whether the version map contains at least one local version.
480    local: bool,
481    /// The raw simple metadata from which `PrioritizedDist`s should
482    /// be constructed.
483    simple_metadata: OwnedArchive<SimpleDetailMetadata>,
484    /// When true, wheels aren't allowed.
485    no_binary: bool,
486    /// When true, source dists aren't allowed.
487    no_build: bool,
488    /// The URL of the index where this package came from.
489    index: IndexUrl,
490    /// The set of compatibility tags that determines whether a wheel is usable
491    /// in the current environment.
492    tags: Option<Tags>,
493    /// Files newer than this timestamp are considered excluded, i.e., that they cannot be selected by the
494    /// resolver.
495    included_version_cutoff: Option<Timestamp>,
496    /// Files newer than this timestamp are considered unavailable, i.e., that they do not exist.
497    available_version_cutoff: Option<Timestamp>,
498    /// Which yanked versions are allowed
499    allowed_yanks: AllowedYanks,
500    /// The hashes of allowed distributions.
501    hasher: HashStrategy,
502    /// The `requires-python` constraint for the resolution.
503    requires_python: RequiresPython,
504    /// The libc baselines required during universal resolution.
505    minimum_libc_version: Option<MinimumLibcVersion>,
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(
693                            dist,
694                            hashes,
695                            compatibility,
696                            self.minimum_libc_version,
697                        );
698                    }
699                    DistFilename::SourceDistFilename(filename) => {
700                        let compatibility = self.source_dist_compatibility(
701                            &filename,
702                            hashes.as_slice(),
703                            yanked,
704                            excluded,
705                            upload_time,
706                        );
707                        let dist = RegistrySourceDist {
708                            name: filename.name.clone(),
709                            version: filename.version.clone(),
710                            ext: filename.extension,
711                            file: Box::new(file),
712                            index: self.index.clone(),
713                            wheels: vec![],
714                            size_is_authoritative: false,
715                        };
716                        priority_dist.insert_source(dist, hashes, compatibility);
717                    }
718                }
719            }
720            if priority_dist.is_empty() {
721                None
722            } else {
723                Some(priority_dist)
724            }
725        };
726        simple.dist.get_or_init(get_or_init).as_ref()
727    }
728
729    fn source_dist_compatibility(
730        &self,
731        filename: &SourceDistFilename,
732        hashes: &[HashDigest],
733        yanked: Option<&Yanked>,
734        excluded: bool,
735        upload_time: Option<i64>,
736    ) -> SourceDistCompatibility {
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 builds are disabled
745        if self.no_build {
746            return SourceDistCompatibility::Incompatible(IncompatibleSource::NoBuild);
747        }
748
749        // Check if yanked
750        if let Some(yanked) = yanked {
751            if yanked.is_yanked()
752                && !self
753                    .allowed_yanks
754                    .contains(&filename.name, &filename.version)
755            {
756                return SourceDistCompatibility::Incompatible(IncompatibleSource::Yanked(
757                    yanked.clone(),
758                ));
759            }
760        }
761
762        // Check if the filename is PEP 625-compliant.
763        // TODO: Strengthen this check more; right now we allow `.zip`
764        // (which is not compliant) and we don't strictly
765        // enforce the formatting rules for the name or version.
766        if !filename.extension.is_pep625_compliant() {
767            return SourceDistCompatibility::Incompatible(IncompatibleSource::NotPep625Filename);
768        }
769
770        // Check if hashes line up. If hashes aren't required, they're considered matching.
771        let hash_policy = self
772            .hasher
773            .archive_policy_for_package(&filename.name, &filename.version);
774        let required_hashes = hash_policy.digests();
775        let hash = if required_hashes.is_empty() {
776            HashComparison::Matched
777        } else {
778            if hashes.is_empty() {
779                HashComparison::Missing
780            } else if hash_policy.matches(hashes) {
781                HashComparison::Matched
782            } else {
783                HashComparison::Mismatched
784            }
785        };
786
787        SourceDistCompatibility::Compatible(hash)
788    }
789
790    fn wheel_compatibility(
791        &self,
792        filename: &WheelFilename,
793        name: &PackageName,
794        version: &Version,
795        hashes: &[HashDigest],
796        yanked: Option<&Yanked>,
797        excluded: bool,
798        upload_time: Option<i64>,
799    ) -> WheelCompatibility {
800        // Check if after upload time cutoff
801        if excluded {
802            return WheelCompatibility::Incompatible(IncompatibleWheel::ExcludeNewer(upload_time));
803        }
804
805        // Check if binaries are disabled
806        if self.no_binary {
807            return WheelCompatibility::Incompatible(IncompatibleWheel::NoBinary);
808        }
809
810        // Check if yanked
811        if let Some(yanked) = yanked {
812            if yanked.is_yanked() && !self.allowed_yanks.contains(name, version) {
813                return WheelCompatibility::Incompatible(IncompatibleWheel::Yanked(yanked.clone()));
814            }
815        }
816
817        // Determine a compatibility for the wheel based on tags.
818        let priority = if let Some(tags) = &self.tags {
819            match filename.compatibility(tags) {
820                TagCompatibility::Incompatible(tag) => {
821                    return WheelCompatibility::Incompatible(IncompatibleWheel::Tag(tag));
822                }
823                TagCompatibility::Compatible(priority) => Some(priority),
824            }
825        } else {
826            // Check if the wheel is compatible with the `requires-python` (i.e., the Python
827            // ABI tag is not less than the `requires-python` minimum version).
828            if !self.requires_python.matches_wheel_tag(filename) {
829                return WheelCompatibility::Incompatible(IncompatibleWheel::Tag(
830                    IncompatibleTag::AbiPythonVersion,
831                ));
832            }
833            None
834        };
835
836        // Check if hashes line up. If hashes aren't required, they're considered matching.
837        let hash_policy = self.hasher.archive_policy_for_package(name, version);
838        let required_hashes = hash_policy.digests();
839        let hash = if required_hashes.is_empty() {
840            HashComparison::Matched
841        } else {
842            if hashes.is_empty() {
843                HashComparison::Missing
844            } else if hash_policy.matches(hashes) {
845                HashComparison::Matched
846            } else {
847                HashComparison::Mismatched
848            }
849        };
850
851        // Break ties with the build tag.
852        let build_tag = filename.build_tag().cloned();
853
854        WheelCompatibility::Compatible(hash, priority, build_tag)
855    }
856}
857
858/// Represents a possibly initialized [`PrioritizedDist`] for a package version.
859#[derive(Debug)]
860struct LazyPrioritizedDist {
861    /// An eagerly constructed distribution from [`FlatDistributions`], if present.
862    flat: Option<PrioritizedDist>,
863    /// A lazy index into [`SimpleDetailMetadata`], if present.
864    simple: Option<SimplePrioritizedDist>,
865}
866
867/// Represents a lazily initialized `PrioritizedDist`.
868#[derive(Debug)]
869struct SimplePrioritizedDist {
870    /// An offset into `SimpleDetailMetadata` corresponding to a `SimpleMetadatum`.
871    /// This provides access to a `VersionFiles` that is used to construct a
872    /// `PrioritizedDist`.
873    datum_index: usize,
874    /// A lazily initialized distribution.
875    ///
876    /// Note that the `Option` does not represent the initialization state.
877    /// The `Option` can be `None` even after initialization, for example,
878    /// if initialization could not find any usable files from which to
879    /// construct a distribution. (One easy way to effect this, at the time
880    /// of writing, is to use `--exclude-newer 1900-01-01`.)
881    dist: OnceLock<Option<PrioritizedDist>>,
882}
883
884/// A range that can be used to iterate over a subset of a [`BTreeMap`].
885#[derive(Debug)]
886struct BoundingRange<'a> {
887    min: Bound<&'a Version>,
888    max: Bound<&'a Version>,
889}
890
891impl<'a> From<&'a Ranges<Version>> for BoundingRange<'a> {
892    fn from(value: &'a Ranges<Version>) -> Self {
893        let (min, max) = value
894            .bounding_range()
895            .unwrap_or((Bound::Unbounded, Bound::Unbounded));
896        Self { min, max }
897    }
898}
899
900impl<'a> RangeBounds<Version> for BoundingRange<'a> {
901    fn start_bound(&self) -> Bound<&'a Version> {
902        self.min
903    }
904
905    fn end_bound(&self) -> Bound<&'a Version> {
906        self.max
907    }
908}
uv_resolver/version_map.rs

uv_resolver/
version_map.rs
