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

uv_resolver/
version_map.rs
