11use std:: fmt:: { Display , Formatter } ;
2+ use std:: ops:: Bound ;
23
34use either:: Either ;
45use 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 ) ]
631764pub ( crate ) enum CandidateDist < ' a > {
632765 Compatible ( CompatibleDist < ' a > ) ,
0 commit comments