Deal with duplicates in the solution space of a dep

While we process the possible solutions we might modify other solutions
like discarding their candidates and such, so that then we reach them
they might no longer be proper candidates. We also try to drop
duplicates early on to avoid the simple cases of these which
test-explore-or-groups-in-markinstall triggers via its explicit
duplication but could also come via multiple provides.

It only worked previously as were ignoring current versions which
usually is okay expect if they are marked for removal and we want to
reinstate them so the ProblemResolver can decide which one later on.

2 files changed, 28 insertions, 22 deletions

diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index b1447bb6c..2eac1ba41 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -1258,28 +1258,31 @@ static bool MarkInstall_CollectDependencies(pkgDepCache const &Cache, pkgCache::
 									/*}}}*/
 static APT::VersionVector getAllPossibleSolutions(pkgDepCache &Cache, pkgCache::DepIterator Start, pkgCache::DepIterator const &End, APT::CacheSetHelper::VerSelector const selector, bool const sorted) /*{{{*/
 {
-      pkgCacheFile CacheFile{&Cache};
-      APT::VersionVector toUpgrade, toNewInstall;
-      do
+   pkgCacheFile CacheFile{&Cache};
+   APT::VersionVector toUpgrade, toNewInstall;
+   do
+   {
+      APT::VersionVector verlist = APT::VersionVector::FromDependency(CacheFile, Start, selector);
+      if (not sorted)
       {
-	 APT::VersionVector verlist = APT::VersionVector::FromDependency(CacheFile, Start, selector);
-	 if (not sorted)
-	 {
-	    std::move(verlist.begin(), verlist.end(), std::back_inserter(toUpgrade));
-	    continue;
-	 }
-	 std::sort(verlist.begin(), verlist.end(), CompareProviders{Cache, Start});
-	 for (auto &&Ver : verlist)
-	 {
-	    auto P = Ver.ParentPkg();
-	    if (P->CurrentVer != 0)
-	       toUpgrade.emplace_back(std::move(Ver));
-	    else
-	       toNewInstall.emplace_back(std::move(Ver));
-	 }
-      } while (Start++ != End);
-      std::move(toNewInstall.begin(), toNewInstall.end(), std::back_inserter(toUpgrade));
-  return toUpgrade;
+	 std::move(verlist.begin(), verlist.end(), std::back_inserter(toUpgrade));
+	 continue;
+      }
+      std::sort(verlist.begin(), verlist.end(), CompareProviders{Cache, Start});
+      for (auto &&Ver : verlist)
+      {
+	 auto P = Ver.ParentPkg();
+	 if (P->CurrentVer != 0)
+	    toUpgrade.emplace_back(std::move(Ver));
+	 else
+	    toNewInstall.emplace_back(std::move(Ver));
+      }
+   } while (Start++ != End);
+   std::move(toNewInstall.begin(), toNewInstall.end(), std::back_inserter(toUpgrade));
+   if (not sorted)
+      std::sort(toUpgrade.begin(), toUpgrade.end(), [](pkgCache::VerIterator const &A, pkgCache::VerIterator const &B) { return A->ID < B->ID; });
+   toUpgrade.erase(std::unique(toUpgrade.begin(), toUpgrade.end()), toUpgrade.end());
+   return toUpgrade;
 }
 									/*}}}*/
 static bool MarkInstall_MarkDeleteForNotUpgradeable(pkgDepCache &Cache, bool const DebugAutoInstall, pkgCache::VerIterator const &PV, unsigned long const Depth, pkgCache::PkgIterator const &Pkg, bool const propagateProctected)/*{{{*/
@@ -1313,6 +1316,8 @@ static bool MarkInstall_RemoveConflictsIfNotUpgradeable(pkgDepCache &Cache, bool
       {
 	 auto const Pkg = Ver.ParentPkg();
 	 auto &State = Cache[Pkg];
+	 if (State.CandidateVer != Ver)
+	    continue;
 	 if (Pkg.CurrentVer() != Ver)
 	 {
 	    if (State.Install() && not Cache.MarkKeep(Pkg, false, false, Depth))
@@ -1466,7 +1471,7 @@ static bool MarkInstall_InstallDependencies(pkgDepCache &Cache, bool const Debug
       for (auto const &InstVer : possibleSolutions)
       {
 	 auto const InstPkg = InstVer.ParentPkg();
-	 if (Cache[InstPkg].CandidateVer == nullptr || Cache[InstPkg].CandidateVer == InstPkg.CurrentVer())
+	 if (Cache[InstPkg].CandidateVer != InstVer)
 	    continue;
 	 if (DebugAutoInstall)
 	    std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.FullName()
diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests
index 1e144f1ee..c9a7b714e 100755
--- a/test/integration/test-bug-618848-always-respect-user-requests
+++ b/test/integration/test-bug-618848-always-respect-user-requests
@@ -18,6 +18,7 @@ Building dependency tree...
   MarkDelete libdb4.8:i386 < 1.0 @ii pmK > FU=1
   MarkDelete exim4-daemon-light:i386 < 1.0 @ii mK Ib > FU=0
     MarkInstall exim4-daemon-heavy:i386 < none -> 1.0 @un uN Ib > FU=0
+      Ignore MarkInstall of libdb4.8:i386 < 1.0 @ii pmR > as its mode (Delete) is protected
       exim4-daemon-heavy:i386 Depends on libdb4.8:i386 < 1.0 @ii pmR > can't be satisfied! (dep)
   MarkDelete exim4:i386 < 1.0 @ii mK Ib > FU=0
 The following packages will be REMOVED: