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).

2 files changed, 27 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
diff --git a/test/integration/test-solver3-dependencies b/test/integration/test-solver3-dependencies
index 330ded8f9..2aa4c4d7b 100755
--- a/test/integration/test-solver3-dependencies
+++ b/test/integration/test-solver3-dependencies
@@ -63,3 +63,13 @@ Conf enhanced (3 unstable [all])
 Conf enhances (3 unstable [all])
 Conf replaced (3 unstable [all])
 Conf replaces (3 unstable [all])" apt dist-upgrade -s
+
+insertpackage 'testing,now' 'test' 'all' '1'
+insertpackage 'unstable' 'test' 'all' '2'
+insertpackage 'experimental' 'test' 'all' '3'
+insertpackage 'unstable' 'depends-test' 'all' '2' 'Depends: test'
+setupaptarchive
+
+testsuccess apt upgrade depends-test -o Debug::APT::Solver=3 --solver 3.0 --no-strict-pinning -s
+cp rootdir/tmp/testsuccess.output solver.log
+testsuccess grep 'test:amd64=2 | test:amd64=1 | test:amd64=3' solver.log