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

uv_resolver/
version_map.rs
