Skip to content

Commit 7e62e11

Browse files
Speed up candidate selection for disjoint ranges (#20026)
## Summary PubGrub can produce allowed version ranges with many disjoint segments as resolution progresses. Candidate selection previously called `Range::contains` for every candidate, repeating a binary search over those segments even though `VersionMap` visits candidates in sorted order. This adds a monotonic cursor for candidate selection. The cursor holds the current segment and streams the remaining borrowed segments in the same direction as candidate selection, visiting each segment at most once without cloning or allocating. Empty ranges return immediately, while every non-empty range follows the same cursor-backed selection path. --------- Co-authored-by: Charlie Marsh <[email protected]>
1 parent b7ab9a3 commit 7e62e11

1 file changed

Lines changed: 134 additions & 1 deletion

File tree

‎crates/uv-resolver/src/candidate_selector.rs‎

Lines changed: 134 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
use std::fmt::{Display, Formatter};
2+
use std::ops::Bound;
23

34
use either::Either;
45
use itertools::Itertools;
@@ -455,6 +456,7 @@ impl CandidateSelector {
455456
package_name,
456457
range,
457458
allow_prerelease,
459+
highest,
458460
)
459461
} else {
460462
Self::select_candidate(
@@ -477,6 +479,7 @@ impl CandidateSelector {
477479
package_name,
478480
range,
479481
allow_prerelease,
482+
highest,
480483
)
481484
}
482485
} else {
@@ -487,6 +490,7 @@ impl CandidateSelector {
487490
package_name,
488491
range,
489492
allow_prerelease,
493+
highest,
490494
)
491495
})
492496
} else {
@@ -496,6 +500,7 @@ impl CandidateSelector {
496500
package_name,
497501
range,
498502
allow_prerelease,
503+
highest,
499504
)
500505
})
501506
}
@@ -524,12 +529,26 @@ impl CandidateSelector {
524529
/// The returned [`Candidate`] _may not_ be compatible with the current platform; in such
525530
/// cases, the resolver is responsible for tracking the incompatibility and re-running the
526531
/// selection process with additional constraints.
532+
///
533+
/// `versions` must be ordered from highest to lowest when `highest` is `true`, and from lowest
534+
/// to highest otherwise.
527535
fn select_candidate<'a>(
528536
versions: impl Iterator<Item = (&'a Version, VersionMapDistHandle<'a>)>,
529537
package_name: &'a PackageName,
530538
range: &Range<Version>,
531539
allow_prerelease: bool,
540+
highest: bool,
532541
) -> Option<Candidate<'a>> {
542+
let segments = range.iter();
543+
let segments = if highest {
544+
Either::Left(segments.rev())
545+
} else {
546+
Either::Right(segments)
547+
};
548+
let Some(mut cursor) = RangeCursor::new(segments, highest) else {
549+
trace!("Exhausted all candidates for package {package_name} with empty range");
550+
return None;
551+
};
533552
let mut steps = 0usize;
534553
let mut incompatible: Option<Candidate> = None;
535554
for (version, maybe_dist) in versions {
@@ -550,7 +569,7 @@ impl CandidateSelector {
550569
if version.any_prerelease() && !allow_prerelease {
551570
continue;
552571
}
553-
if !range.contains(version) {
572+
if !cursor.contains(version) {
554573
continue;
555574
}
556575
let Some(dist) = maybe_dist.prioritized_dist() else {
@@ -627,6 +646,120 @@ impl CandidateSelector {
627646
}
628647
}
629648

649+
/// Tracks membership in a range while visiting versions monotonically.
650+
///
651+
/// Unlike [`Range::contains`], which searches the segments for every version, the cursor visits
652+
/// each segment at most once.
653+
struct RangeCursor<'a, Segments> {
654+
current: (Bound<&'a Version>, Bound<&'a Version>),
655+
segments: Segments,
656+
highest: bool,
657+
}
658+
659+
impl<'a, Segments> RangeCursor<'a, Segments>
660+
where
661+
Segments: Iterator<Item = (Bound<&'a Version>, Bound<&'a Version>)>,
662+
{
663+
/// Create a cursor over segments ordered in the same direction as the visited versions.
664+
fn new(mut segments: Segments, highest: bool) -> Option<Self> {
665+
Some(Self {
666+
current: segments.next()?,
667+
segments,
668+
highest,
669+
})
670+
}
671+
672+
/// Return whether `version` is in the range, advancing past segments that cannot contain any
673+
/// subsequently visited versions.
674+
fn contains(&mut self, version: &Version) -> bool {
675+
if self.highest {
676+
loop {
677+
let (start, end) = self.current;
678+
if is_before(version, start) {
679+
let Some(current) = self.segments.next() else {
680+
return false;
681+
};
682+
self.current = current;
683+
} else {
684+
return !is_after(version, end);
685+
}
686+
}
687+
} else {
688+
loop {
689+
let (start, end) = self.current;
690+
if is_after(version, end) {
691+
let Some(current) = self.segments.next() else {
692+
return false;
693+
};
694+
self.current = current;
695+
} else {
696+
return !is_before(version, start);
697+
}
698+
}
699+
}
700+
}
701+
}
702+
703+
fn is_before(version: &Version, bound: Bound<&Version>) -> bool {
704+
match bound {
705+
Bound::Included(start) => version < start,
706+
Bound::Excluded(start) => version <= start,
707+
Bound::Unbounded => false,
708+
}
709+
}
710+
711+
fn is_after(version: &Version, bound: Bound<&Version>) -> bool {
712+
match bound {
713+
Bound::Included(end) => version > end,
714+
Bound::Excluded(end) => version >= end,
715+
Bound::Unbounded => false,
716+
}
717+
}
718+
719+
#[cfg(test)]
720+
mod tests {
721+
use super::*;
722+
723+
fn version(value: &str) -> Version {
724+
value.parse().expect("valid test version")
725+
}
726+
727+
fn assert_range_cursor(highest: bool, values: &[&str]) {
728+
let range = [
729+
(Bound::Unbounded, Bound::Excluded(version("2"))),
730+
(Bound::Included(version("3")), Bound::Included(version("4"))),
731+
(Bound::Excluded(version("5")), Bound::Unbounded),
732+
]
733+
.into_iter()
734+
.collect::<Range<_>>();
735+
let segments = if highest {
736+
Either::Left(range.iter().rev())
737+
} else {
738+
Either::Right(range.iter())
739+
};
740+
let mut cursor = RangeCursor::new(segments, highest).expect("test range is not empty");
741+
742+
for value in values {
743+
let version = version(value);
744+
assert_eq!(
745+
cursor.contains(&version),
746+
range.contains(&version),
747+
"{value}"
748+
);
749+
}
750+
}
751+
752+
#[test]
753+
fn range_cursor_ascending() {
754+
assert_range_cursor(false, &["1", "2", "2.5", "3", "4", "5", "6"]);
755+
}
756+
757+
#[test]
758+
fn range_cursor_descending() {
759+
assert_range_cursor(true, &["6", "5", "4", "3", "2.5", "2", "1"]);
760+
}
761+
}
762+
630763
#[derive(Debug, Clone)]
631764
pub(crate) enum CandidateDist<'a> {
632765
Compatible(CompatibleDist<'a>),

0 commit comments

Comments
 (0)