Respect users pkg order on `apt install` for resolving

The command line is evaluated in two steps: First all packages given
are marked for install and as a second step the resolver is started on
all of them in turn to get their dependencies installed.

This is done so a user can provide a non-default choice on the command
line and have it respected regardless of where on the command line it
appears.

On the other hand, the order in which dependencies are resolved can
matter, so instead of using a "random" order, we now do this in the
order given on the command line, so if you e.g. have a meta package
pulling in non-default choices and mention it first the choices are
respected predictably instead of depending on first appearance of the
package name while creating the binary cache.

I might have "broken" this more than a decade ago while introducing the
reworked command line parsing for Multi-Arch, which also brought in the
split into the two steps mentioned above which was the far more
impactful 'respect user choice' change. This one should hardly matter in
practice, but as the tests show, order can have surprising side effects.

3 files changed, 15 insertions, 10 deletions

diff --git a/apt-private/private-install.cc b/apt-private/private-install.cc
index 34cc69805..08d58a53c 100644
--- a/apt-private/private-install.cc
+++ b/apt-private/private-install.cc
@@ -593,12 +593,12 @@ static const unsigned short MOD_INSTALL = 2;
 bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg> &VolatileCmdL, CacheFile &Cache, int UpgradeMode,
 					APT::PackageVector &HeldBackPackages)
 {
-   std::map<unsigned short, APT::VersionSet> verset;
+   std::map<unsigned short, APT::VersionVector> verset;
    std::set<std::string> UnknownPackages;
    return DoCacheManipulationFromCommandLine(CmdL, VolatileCmdL, Cache, verset, UpgradeMode, UnknownPackages, HeldBackPackages);
 }
 bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg> &VolatileCmdL, CacheFile &Cache,
-					std::map<unsigned short, APT::VersionSet> &verset, int UpgradeMode,
+					std::map<unsigned short, APT::VersionVector> &verset, int UpgradeMode,
 					std::set<std::string> &UnknownPackages, APT::PackageVector &HeldBackPackages)
 {
    // Enter the special broken fixing mode if the user specified arguments
@@ -639,8 +639,13 @@ bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg
    mods.push_back(APT::VersionSet::Modifier(MOD_REMOVE, "-",
 		APT::VersionSet::Modifier::POSTFIX, APT::CacheSetHelper::NEWEST));
    CacheSetHelperAPTGet helper(c0out);
-   verset = APT::VersionSet::GroupedFromCommandLine(Cache,
+   verset = APT::VersionVector::GroupedFromCommandLine(Cache,
 		CmdL.FileList + 1, mods, fallback, helper);
+   for (auto &vs : verset)
+   {
+      std::set<map_id_t> seen;
+      vs.second.erase(std::remove_if(vs.second.begin(), vs.second.end(), [&](auto const &p) { return not seen.insert(p->ID).second; }), vs.second.end());
+   }
 
    for (auto const &I: VolatileCmdL)
    {
@@ -834,14 +839,14 @@ std::vector<PseudoPkg> GetPseudoPackages(pkgSourceList *const SL, CommandLine &C
 /* Install named packages */
 struct PkgIsExtraInstalled {
    pkgCacheFile * const Cache;
-   APT::VersionSet const * const verset;
-   PkgIsExtraInstalled(pkgCacheFile * const Cache, APT::VersionSet const * const Container) : Cache(Cache), verset(Container) {}
+   APT::VersionVector const * const verset;
+   PkgIsExtraInstalled(pkgCacheFile * const Cache, APT::VersionVector const * const Container) : Cache(Cache), verset(Container) {}
    bool operator() (pkgCache::PkgIterator const &Pkg)
    {
         if ((*Cache)[Pkg].Install() == false)
            return false;
         pkgCache::VerIterator const Cand = (*Cache)[Pkg].CandidateVerIter(*Cache);
-        return verset->find(Cand) == verset->end();
+	return std::find(verset->begin(), verset->end(), Cand) == verset->end();
    }
 };
 bool DoInstall(CommandLine &CmdL)
@@ -857,7 +862,7 @@ bool DoInstall(CommandLine &CmdL)
        Cache.CheckDeps(CmdL.FileSize() != 1) == false)
       return false;
 
-   std::map<unsigned short, APT::VersionSet> verset;
+   std::map<unsigned short, APT::VersionVector> verset;
    std::set<std::string> UnknownPackages;
    APT::PackageVector HeldBackPackages;
 
diff --git a/apt-private/private-install.h b/apt-private/private-install.h
index e3df9ac89..0f6d048fc 100644
--- a/apt-private/private-install.h
+++ b/apt-private/private-install.h
@@ -33,7 +33,7 @@ bool AddVolatileBinaryFile(pkgSourceList *const SL, PseudoPkg &&pkg, std::vector
 bool AddVolatileSourceFile(pkgSourceList *const SL, PseudoPkg &&pkg, std::vector<PseudoPkg> &VolatileCmdL);
 
 bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg> &VolatileCmdL, CacheFile &Cache,
-					std::map<unsigned short, APT::VersionSet> &verset, int UpgradeMode,
+					std::map<unsigned short, APT::VersionVector> &verset, int UpgradeMode,
 					std::set<std::string> &UnknownPackages, APT::PackageVector &HeldBackPackages);
 bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<PseudoPkg> &VolatileCmdL, CacheFile &Cache, int UpgradeMode,
 					APT::PackageVector &HeldBackPackages);
@@ -54,7 +54,7 @@ struct TryToInstall {
    pkgProblemResolver* Fix;
    bool FixBroken;
    unsigned long AutoMarkChanged;
-   APT::PackageSet doAutoInstallLater;
+   APT::PackageVector doAutoInstallLater;
 
    TryToInstall(pkgCacheFile &Cache, pkgProblemResolver *PM, bool const FixBroken) : Cache(&Cache), Fix(PM),
 			FixBroken(FixBroken), AutoMarkChanged(0) {};
diff --git a/apt-private/private-upgrade.cc b/apt-private/private-upgrade.cc
index 3423db525..97603dc16 100644
--- a/apt-private/private-upgrade.cc
+++ b/apt-private/private-upgrade.cc
@@ -27,7 +27,7 @@ static bool UpgradeHelper(CommandLine &CmdL, int UpgradeFlags)
    if (Cache.OpenForInstall() == false || Cache.CheckDeps() == false)
       return false;
 
-   std::map<unsigned short, APT::VersionSet> verset;
+   std::map<unsigned short, APT::VersionVector> verset;
    std::set<std::string> UnknownPackages;
    APT::PackageVector HeldBackPackages;
    if (not DoCacheManipulationFromCommandLine(CmdL, VolatileCmdL, Cache, verset, UpgradeFlags, UnknownPackages, HeldBackPackages))