From a0ba6323f10689d1f4dd4092c0463b277e03b5a7 Mon Sep 17 00:00:00 2001
From: Denis Rastyogin <gerben@altlinux.org>
Date: Thu, 5 Jun 2025 13:42:44 +0300
Subject: [PATCH] apt-pkg/algorithms.cc: fix kill-list logic to collect all
 candidate versions
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

When two candidate versions (e.g., a task version and branch version)
both appear in VList, apt would defer deleting the first version
(because “*(V+1) != nullptr”), then skip deleting the second version
(because it isn’t installed yet). As a result, no delete marker
ever reached the main KillList, and the conflict was left unresolved.

This patch introduces a temporary buffer (KillListTemp) to collect
all (Pkg,Dep) entries as we scan every version. Only after we finish
examining every version (when V+1 == nullptr) do we move everything
from KillListTemp into the real KillList. That way, even
if there are multiple candidates, the first version’s delete entry
will still be applied once we reach the end of the list.
---
 apt-pkg/algorithms.cc | 35 +++++++++++++++++++++++++++++++++--
 1 file changed, 33 insertions(+), 2 deletions(-)

diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc
index cd5b5fb4..c6d87c05 100644
--- a/apt-pkg/algorithms.cc
+++ b/apt-pkg/algorithms.cc
@@ -1498,7 +1498,9 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
 
 	 // Isolate the problem dependency
 	 PackageKill KillList[100];
+	 PackageKill KillListTemp[100];
 	 PackageKill *LEnd = KillList;
+	 PackageKill *LEndTemp = KillListTemp;
 	 bool InOr = false;
 	 pkgCache::DepIterator Start;
 	 pkgCache::DepIterator End;
@@ -1580,6 +1582,16 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
 	       break;
 	    }
 
+            auto flushTemp = [&]()
+            {
+                for (PackageKill *ptrTemp = KillListTemp; ptrTemp != LEndTemp; ++ptrTemp)
+                {
+                    *LEnd = *ptrTemp;
+                    ++LEnd;
+                }
+                LEndTemp = KillListTemp;
+            };
+
 	    bool Done = false;
 	    for (pkgCache::Version * const *V = VList.get(); *V != nullptr; V++)
 	    {
@@ -1608,6 +1620,9 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
 			break;
 		     }
 
+                     if (*(V + 1) == nullptr && LEndTemp != KillListTemp)
+                        flushTemp();
+
 		     continue;
 		  }
 
@@ -1670,11 +1685,21 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
 		  if (Cache[Pkg].InstallVer != Ver.operator const pkgCache::Version *() &&
 		      (Start->Type == pkgCache::Dep::Conflicts ||
 		       Start->Type == pkgCache::Dep::Obsoletes))
-		     continue;
+		  {
+                     if (*(V + 1) == nullptr && LEndTemp != KillListTemp)
+                        flushTemp();
+
+                     continue;
+		  }
 
 		  // Skip adding to the kill list if it is protected
 		  if ((Flags[Pkg->ID] & Protected) != 0)
-		     continue;
+                  {
+                     if (*(V + 1) == nullptr && LEndTemp != KillListTemp)
+                        flushTemp();
+
+                     continue;
+                  }
 
 		  // CNC:2003-03-22
 		  pkgDepCache::State State(&Cache);
@@ -1693,6 +1718,12 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
 
 		  DBG.traceSolver(2, std::string("Added ") + ToDbgStr(Pkg) + " to the remove list");
 
+                  // Add this (Pkg, Dep) pair to the temporary kill list;
+                  // it will be applied if no other solution is found
+                  LEndTemp->Pkg = Pkg;
+                  LEndTemp->Dep = End;
+                  LEndTemp++;
+
 		  // CNC:2002-07-09
 		  if (*(V+1) != 0) //XXX Look for other solutions?
 		      continue;
-- 
2.42.2