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                package_name: package_name.clone(),
98                map,
99                stable,
100                local,
101                simple_metadata,
102                no_binary: build_options.no_binary_package(package_name),
103                no_build: build_options.no_build_package(package_name),
104                index,
105                tags,
106                allowed_yanks,
107                hasher,
108                requires_python,
109                included_version_cutoff,
110                available_version_cutoff,
111            }),
112        }
113    }
114
115    #[instrument(skip_all, fields(package_name))]
116    pub(crate) fn from_flat_metadata(
117        flat_metadata: Vec<FlatIndexEntry>,
118        tags: Option<&Tags>,
119        hasher: &HashStrategy,
120        build_options: &BuildOptions,
121    ) -> Self {
122        let mut stable = false;
123        let mut local = false;
124        let mut map = BTreeMap::new();
125
126        for (version, prioritized_dist) in
127            FlatDistributions::from_entries(flat_metadata, tags, hasher, build_options)
128        {
129            stable |= version.is_stable();
130            local |= version.is_local();
131            map.insert(version, prioritized_dist);
132        }
133
134        Self {
135            inner: VersionMapInner::Eager(VersionMapEager { map, stable, local }),
136        }
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 stable (non-pre-release) version.
291    pub(crate) fn stable(&self) -> bool {
292        match self.inner {
293            VersionMapInner::Eager(ref map) => map.stable,
294            VersionMapInner::Lazy(ref map) => map.stable,
295        }
296    }
297
298    /// Returns `true` if the map contains at least one local version (e.g., `2.6.0+cpu`).
299    pub(crate) fn local(&self) -> bool {
300        match self.inner {
301            VersionMapInner::Eager(ref map) => map.local,
302            VersionMapInner::Lazy(ref map) => map.local,
303        }
304    }
305}
306
307impl From<FlatDistributions> for VersionMap {
308    fn from(flat_index: FlatDistributions) -> Self {
309        let stable = flat_index.iter().any(|(version, _)| version.is_stable());
310        let local = flat_index.iter().any(|(version, _)| version.is_local());
311        let map = flat_index.into();
312        Self {
313            inner: VersionMapInner::Eager(VersionMapEager { map, stable, local }),
314        }
315    }
316}
317
318/// A lazily initialized distribution.
319///
320/// This permits access to a handle that can be turned into a resolvable
321/// distribution when desired. This is coupled with a `Version` in
322/// [`VersionMap::iter`] to permit iteration over all items in a map without
323/// necessarily constructing a distribution for every version if it isn't
324/// needed.
325///
326/// Note that because of laziness, not all such items can be turned into
327/// a valid distribution. For example, if in the process of building a
328/// distribution no compatible wheel or source distribution could be found,
329/// then building a `CompatibleDist` will fail.
330pub(crate) struct VersionMapDistHandle<'a> {
331    inner: VersionMapDistHandleInner<'a>,
332}
333
334enum VersionMapDistHandleInner<'a> {
335    Eager(&'a PrioritizedDist),
336    Lazy {
337        lazy: &'a VersionMapLazy,
338        dist: &'a LazyPrioritizedDist,
339    },
340}
341
342impl<'a> VersionMapDistHandle<'a> {
343    /// Returns whether this distribution can be considered for selection.
344    fn is_included(&self) -> bool {
345        match self.inner {
346            VersionMapDistHandleInner::Eager(_) => true,
347            VersionMapDistHandleInner::Lazy { lazy, dist } => match (&dist.flat, &dist.simple) {
348                (Some(_), _) => true,
349                (None, Some(simple)) => lazy.any_file_materializable(simple),
350                (None, None) => false,
351            },
352        }
353    }
354
355    /// Returns a prioritized distribution from this handle.
356    pub(crate) fn prioritized_dist(&self) -> Option<&'a PrioritizedDist> {
357        match self.inner {
358            VersionMapDistHandleInner::Eager(dist) => Some(dist),
359            VersionMapDistHandleInner::Lazy { lazy, dist } => Some(lazy.get_lazy(dist)?),
360        }
361    }
362}
363
364/// The kind of internal version map we have.
365#[derive(Debug)]
366#[expect(clippy::large_enum_variant)]
367enum VersionMapInner {
368    /// All distributions are fully materialized in memory.
369    ///
370    /// This usually happens when one needs a `VersionMap` from a
371    /// `FlatDistributions`.
372    Eager(VersionMapEager),
373    /// Some distributions might be fully materialized (i.e., by initializing
374    /// a `VersionMap` with a `FlatDistributions`), but some distributions
375    /// might still be in their "raw" `SimpleDetailMetadata` format. In this case, a
376    /// `PrioritizedDist` isn't actually created in memory until the
377    /// specific version has been requested.
378    Lazy(VersionMapLazy),
379}
380
381/// A map from versions to distributions that are fully materialized in memory.
382#[derive(Debug)]
383struct VersionMapEager {
384    /// A map from version to distribution.
385    map: BTreeMap<Version, PrioritizedDist>,
386    /// Whether the version map contains at least one stable (non-pre-release) version.
387    stable: bool,
388    /// Whether the version map contains at least one local version.
389    local: bool,
390}
391
392/// An entry in the immutable lazy version index.
393#[derive(Debug)]
394struct VersionMapLazyEntry {
395    version: Version,
396    dist: LazyPrioritizedDist,
397}
398
399/// A compact immutable version index, ordered by native PEP 440 versions.
400#[derive(Debug)]
401struct VersionMapLazyIndex {
402    entries: Vec<VersionMapLazyEntry>,
403}
404
405impl VersionMapLazyIndex {
406    /// Merge the sorted flat index into the sorted simple entries in one pass.
407    fn merge_flat(self, flat_index: FlatDistributions) -> Self {
408        let flat_count = flat_index.iter().size_hint().0;
409        let mut merged = Vec::with_capacity(self.entries.len() + flat_count);
410        let mut simple = self.entries.into_iter().peekable();
411        let mut flat = flat_index.into_iter().peekable();
412        let flat_entry = |(version, dist)| VersionMapLazyEntry {
413            version,
414            dist: LazyPrioritizedDist {
415                flat: Some(dist),
416                simple: None,
417            },
418        };
419        while let (Some(simple_entry), Some((flat_version, _))) = (simple.peek(), flat.peek()) {
420            match simple_entry.version.cmp(flat_version) {
421                std::cmp::Ordering::Less => {
422                    if let Some(entry) = simple.next() {
423                        merged.push(entry);
424                    }
425                }
426                std::cmp::Ordering::Greater => {
427                    if let Some(entry) = flat.next() {
428                        merged.push(flat_entry(entry));
429                    }
430                }
431                std::cmp::Ordering::Equal => {
432                    if let (Some(mut entry), Some((_, dist))) = (simple.next(), flat.next()) {
433                        entry.dist.flat = Some(dist);
434                        merged.push(entry);
435                    }
436                }
437            }
438        }
439        merged.extend(simple);
440        merged.extend(flat.map(flat_entry));
441
442        Self { entries: merged }
443    }
444
445    fn get(&self, version: &Version) -> Option<&VersionMapLazyEntry> {
446        let index = self
447            .entries
448            .binary_search_by(|entry| entry.version.cmp(version))
449            .ok()?;
450        self.entries.get(index)
451    }
452
453    fn keys(&self) -> impl DoubleEndedIterator<Item = &Version> {
454        self.entries.iter().map(|entry| &entry.version)
455    }
456
457    fn range(&self, range: BoundingRange<'_>) -> &[VersionMapLazyEntry] {
458        let start = match range.min {
459            Bound::Included(version) => self
460                .entries
461                .partition_point(|entry| entry.version < *version),
462            Bound::Excluded(version) => self
463                .entries
464                .partition_point(|entry| entry.version <= *version),
465            Bound::Unbounded => 0,
466        };
467        let end = match range.max {
468            Bound::Included(version) => self
469                .entries
470                .partition_point(|entry| entry.version <= *version),
471            Bound::Excluded(version) => self
472                .entries
473                .partition_point(|entry| entry.version < *version),
474            Bound::Unbounded => self.entries.len(),
475        };
476        self.entries.get(start..end).unwrap_or_default()
477    }
478
479    fn len(&self) -> usize {
480        self.entries.len()
481    }
482}
483
484/// A map that lazily materializes some prioritized distributions upon access.
485///
486/// The idea here is that some packages have a lot of versions published, and
487/// needing to materialize a full `VersionMap` with all corresponding metadata
488/// for every version in memory is expensive. Since a `SimpleDetailMetadata` can be
489/// materialized with very little cost (via `rkyv` in the warm cached case),
490/// avoiding another conversion step into a fully filled out `VersionMap` can
491/// provide substantial savings in some cases.
492#[derive(Debug)]
493struct VersionMapLazy {
494    /// The normalized package name used to reconstruct cached wheel filenames.
495    package_name: PackageName,
496    /// An immutable archive-order index from version to possibly-initialized distribution.
497    map: VersionMapLazyIndex,
498    /// Whether the version map contains at least one stable (non-pre-release) version.
499    stable: bool,
500    /// Whether the version map contains at least one local version.
501    local: bool,
502    /// The raw simple metadata from which `PrioritizedDist`s should
503    /// be constructed.
504    simple_metadata: OwnedArchive<SimpleDetailMetadata>,
505    /// When true, wheels aren't allowed.
506    no_binary: bool,
507    /// When true, source dists aren't allowed.
508    no_build: bool,
509    /// The URL of the index where this package came from.
510    index: IndexUrl,
511    /// The set of compatibility tags that determines whether a wheel is usable
512    /// in the current environment.
513    tags: Option<Tags>,
514    /// Files newer than this timestamp are considered excluded, i.e., that they cannot be selected by the
515    /// resolver.
516    included_version_cutoff: Option<Timestamp>,
517    /// Files newer than this timestamp are considered unavailable, i.e., that they do not exist.
518    available_version_cutoff: Option<Timestamp>,
519    /// Which yanked versions are allowed
520    allowed_yanks: AllowedYanks,
521    /// The hashes of allowed distributions.
522    hasher: HashStrategy,
523    /// The `requires-python` constraint for the resolution.
524    requires_python: RequiresPython,
525}
526
527impl VersionMapLazy {
528    /// Returns the registry-provided metadata for the given version, if it exists.
529    fn get_metadata(&self, version: &Version) -> Option<ResolutionMetadata> {
530        let archived = self
531            .map
532            .get(version)
533            .and_then(|entry| entry.dist.simple.as_ref())
534            .and_then(|simple| self.simple_metadata.datum(simple.datum_index))
535            .and_then(|datum| datum.metadata.as_deref())?;
536        Some(
537            rkyv::deserialize::<ResolutionMetadata, rkyv::rancor::Error>(archived)
538                .expect("archived metadata always deserializes"),
539        )
540    }
541
542    /// Returns the distribution for the given version, if it exists.
543    fn get(&self, version: &Version) -> Option<&PrioritizedDist> {
544        self.get_lazy(&self.map.get(version)?.dist)
545    }
546
547    /// Returns an iterator over the versions with at least one file within the exclude-newer
548    /// cutoffs, without materializing the distributions.
549    fn included_versions(&self) -> impl DoubleEndedIterator<Item = &Version> {
550        self.map.entries.iter().filter_map(move |entry| {
551            let included = match (&entry.dist.flat, &entry.dist.simple) {
552                // Flat index files have no upload times and bypass the cutoffs.
553                (Some(_), _) => true,
554                (None, Some(simple)) => self.any_file_included(simple),
555                (None, None) => false,
556            };
557            included.then_some(&entry.version)
558        })
559    }
560
561    /// Returns whether at least one file keeps this version inside the candidate universe.
562    ///
563    /// This mirrors the per-file cutoff handling in [`Self::get_simple`] without materializing the
564    /// distribution, including the two cutoff modes' distinct handling of missing upload times.
565    fn any_file_included(&self, simple: &SimplePrioritizedDist) -> bool {
566        if self.included_version_cutoff.is_none() && self.available_version_cutoff.is_none() {
567            return true;
568        }
569        let Some(datum) = self.simple_metadata.datum(simple.datum_index) else {
570            return false;
571        };
572        let files = &datum.files;
573        files
574            .wheels
575            .iter()
576            .chain(files.source_dists.iter())
577            .any(|file| {
578                let upload_time = file.upload_time_utc_ms();
579                let excluded = if let Some(cutoff) = &self.included_version_cutoff {
580                    upload_time.is_none_or(|t| t >= cutoff.as_millisecond())
581                } else if let Some(cutoff) = &self.available_version_cutoff {
582                    upload_time.is_some_and(|t| t >= cutoff.as_millisecond())
583                } else {
584                    false
585                };
586                !excluded
587            })
588    }
589
590    /// Returns whether a version should be materialized during candidate selection.
591    ///
592    /// Missing upload times are retained here, even for `included_version_cutoff`, since
593    /// materializing them is what emits the corresponding `exclude-newer` warning.
594    fn any_file_materializable(&self, simple: &SimplePrioritizedDist) -> bool {
595        let Some(cutoff) = self
596            .included_version_cutoff
597            .as_ref()
598            .or(self.available_version_cutoff.as_ref())
599        else {
600            return true;
601        };
602        let Some(datum) = self.simple_metadata.datum(simple.datum_index) else {
603            return false;
604        };
605        datum
606            .files
607            .wheels
608            .iter()
609            .chain(datum.files.source_dists.iter())
610            .any(|file| {
611                file.upload_time_utc_ms()
612                    .is_none_or(|upload_time| upload_time < cutoff.as_millisecond())
613            })
614    }
615
616    /// Given a reference to a possibly-initialized distribution that is in
617    /// this lazy map, return the corresponding distribution.
618    ///
619    /// When both a flat and simple distribution are present internally, they
620    /// are merged automatically.
621    fn get_lazy<'p>(&'p self, lazy_dist: &'p LazyPrioritizedDist) -> Option<&'p PrioritizedDist> {
622        match (&lazy_dist.flat, &lazy_dist.simple) {
623            (Some(flat), Some(simple)) => self.get_simple(Some(flat), simple),
624            (Some(flat), None) => Some(flat),
625            (None, Some(simple)) => self.get_simple(None, simple),
626            (None, None) => None,
627        }
628    }
629
630    /// Given an optional starting point, return the final form of the
631    /// given simple distribution. If it wasn't initialized yet, then this
632    /// initializes it. If the distribution would otherwise be empty, this
633    /// returns `None`.
634    fn get_simple<'p>(
635        &'p self,
636        init: Option<&'p PrioritizedDist>,
637        simple: &'p SimplePrioritizedDist,
638    ) -> Option<&'p PrioritizedDist> {
639        let get_or_init = || {
640            let files = rkyv::deserialize::<VersionFiles, rkyv::rancor::Error>(
641                &self
642                    .simple_metadata
643                    .datum(simple.datum_index)
644                    .expect("index to lazy dist is correct")
645                    .files,
646            )
647            .expect("archived version files always deserializes");
648            let mut priority_dist = init.cloned().unwrap_or_default();
649            for (filename, file) in files.all(&self.package_name) {
650                // Support resolving as if it were an earlier timestamp, at least as long files have
651                // upload time information.
652                let (excluded, upload_time) = if let Some(included_version_cutoff) =
653                    &self.included_version_cutoff
654                {
655                    match file.upload_time_utc_ms.as_ref() {
656                        Some(&upload_time)
657                            if upload_time >= included_version_cutoff.as_millisecond() =>
658                        {
659                            trace!(
660                                "Excluding `{}` (uploaded {upload_time}) due to exclude-newer ({included_version_cutoff})",
661                                file.filename
662                            );
663                            (true, Some(upload_time))
664                        }
665                        None => {
666                            warn_user_once!(
667                                "{} is missing an upload date, but user provided: {included_version_cutoff}",
668                                file.filename,
669                            );
670                            (true, None)
671                        }
672                        _ => (false, None),
673                    }
674                } else if let Some(available_version_cutoff) = &self.available_version_cutoff {
675                    match file.upload_time_utc_ms.as_ref() {
676                        Some(&upload_time)
677                            if upload_time >= available_version_cutoff.as_millisecond() =>
678                        {
679                            trace!(
680                                "Excluding `{}` (uploaded {upload_time}) due to available version cutoff ({available_version_cutoff})",
681                                file.filename
682                            );
683                            (true, Some(upload_time))
684                        }
685                        _ => (false, None),
686                    }
687                } else {
688                    (false, None)
689                };
690
691                // Prioritize amongst all available files.
692                let yanked = file.yanked.as_deref();
693                let hashes = file.hashes.clone();
694                match filename {
695                    DistFilename::WheelFilename(filename) => {
696                        let compatibility = self.wheel_compatibility(
697                            &filename,
698                            &filename.name,
699                            &filename.version,
700                            hashes.as_slice(),
701                            yanked,
702                            excluded,
703                            upload_time,
704                        );
705                        let dist = RegistryBuiltWheel {
706                            filename,
707                            file: Box::new(file),
708                            index: self.index.clone(),
709                        };
710                        priority_dist.insert_built(dist, hashes, compatibility);
711                    }
712                    DistFilename::SourceDistFilename(filename) => {
713                        let compatibility = self.source_dist_compatibility(
714                            &filename.name,
715                            &filename.version,
716                            hashes.as_slice(),
717                            yanked,
718                            excluded,
719                            upload_time,
720                        );
721                        let dist = RegistrySourceDist {
722                            name: filename.name.clone(),
723                            version: filename.version.clone(),
724                            ext: filename.extension,
725                            file: Box::new(file),
726                            index: self.index.clone(),
727                            wheels: vec![],
728                        };
729                        priority_dist.insert_source(dist, hashes, compatibility);
730                    }
731                }
732            }
733            if priority_dist.is_empty() {
734                None
735            } else {
736                Some(priority_dist)
737            }
738        };
739        simple.dist.get_or_init(get_or_init).as_ref()
740    }
741
742    fn source_dist_compatibility(
743        &self,
744        name: &PackageName,
745        version: &Version,
746        hashes: &[HashDigest],
747        yanked: Option<&Yanked>,
748        excluded: bool,
749        upload_time: Option<i64>,
750    ) -> SourceDistCompatibility {
751        // Check if builds are disabled
752        if self.no_build {
753            return SourceDistCompatibility::Incompatible(IncompatibleSource::NoBuild);
754        }
755
756        // Check if after upload time cutoff
757        if excluded {
758            return SourceDistCompatibility::Incompatible(IncompatibleSource::ExcludeNewer(
759                upload_time,
760            ));
761        }
762
763        // Check if yanked
764        if let Some(yanked) = yanked {
765            if yanked.is_yanked() && !self.allowed_yanks.contains(name, version) {
766                return SourceDistCompatibility::Incompatible(IncompatibleSource::Yanked(
767                    yanked.clone(),
768                ));
769            }
770        }
771
772        // Check if hashes line up. If hashes aren't required, they're considered matching.
773        let hash_policy = self.hasher.get_package(name, 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 binaries are disabled
801        if self.no_binary {
802            return WheelCompatibility::Incompatible(IncompatibleWheel::NoBinary);
803        }
804
805        // Check if after upload time cutoff
806        if excluded {
807            return WheelCompatibility::Incompatible(IncompatibleWheel::ExcludeNewer(upload_time));
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.get_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
