solver3: Fix intransitivity of version comparison on upgrade

We only compared candidate to installed version, but candidate
should dominate all versions, otherwise we end up in the fancy
problem of elpa-notmuch in
  upgrade-noble-t64-remove-desktop-2024-03-29.edsp

Where we had three versions:

    not-installable 0.38.3-1ubuntu1
    candidate 0.38.2-1.1ubuntu2
    installed 0.38.2-1ubuntu2

And received an ordering:

    installed > non-installable > candidate

despite

    candidate > installed

This is only visible with no-strict-pinning right now, as we are
otherwise filtering out invalid choices (and hence we only have
candidate and installed otherwise).

1 files changed, 17 insertions, 11 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index 4c1adef4b..453bf64b4 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -47,18 +47,24 @@ struct APT::Solver::CompareProviders3 /*{{{*/
       {
 	 if (AV == BV)
 	    return false;
-	 // The current version should win, unless we are upgrading and the other is the
-	 // candidate.
-	 // If AV is the current version, AV only wins on upgrades if BV is not the candidate.
-	 if (A.CurrentVer() == AV)
-	    return upgrade ? Policy.GetCandidateVer(A) != BV : true;
-	 // If BV is the current version, AV only wins on upgrades if it is the candidate.
-	 if (A.CurrentVer() == BV)
-	    return upgrade ? Policy.GetCandidateVer(A) == AV : false;
-	 // If neither are the current version, order them by priority.
-	 if (Policy.GetPriority(AV) < Policy.GetPriority(BV))
-	    return false;
 
+	 // Candidate wins in upgrade scenario
+	 if (upgrade)
+	 {
+	    auto Cand = Policy.GetCandidateVer(A);
+	    if (AV == Cand || BV == Cand)
+	       return (AV == Cand);
+	 }
+
+	 // Installed version wins otherwise
+	 if (A.CurrentVer() == AV || B.CurrentVer() == BV)
+	    return (A.CurrentVer() == AV);
+
+	 // Rest is ordered list, first by priority
+	 if (auto pinA = Policy.GetPriority(AV), pinB = Policy.GetPriority(BV); pinA != pinB)
+	    return pinA > pinB;
+
+	 // Then by version
 	 return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0;
       }
       // Try obsolete choices only after exhausting non-obsolete choices such that we install