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.

5 files changed, 97 insertions, 11 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))
diff --git a/test/integration/test-apt-install-order-matters-a-bit b/test/integration/test-apt-install-order-matters-a-bit
new file mode 100755
index 000000000..e41709ff3
--- /dev/null
+++ b/test/integration/test-apt-install-order-matters-a-bit
@@ -0,0 +1,75 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertpackage 'unstable' 'a' 'all' '1' 'Depends: b | d'
+insertpackage 'unstable' 'b' 'all' '1'
+insertpackage 'unstable' 'c' 'all' '1' 'Depends: d | b'
+insertpackage 'unstable' 'd' 'all' '1'
+
+setupaptarchive
+
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+The following additional packages will be installed:
+  b
+The following NEW packages will be installed:
+  a b c
+0 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
+Inst b (1 unstable [all])
+Inst a (1 unstable [all])
+Inst c (1 unstable [all])
+Conf b (1 unstable [all])
+Conf a (1 unstable [all])
+Conf c (1 unstable [all])' apt install a c -s
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+The following additional packages will be installed:
+  d
+The following NEW packages will be installed:
+  a c d
+0 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
+Inst d (1 unstable [all])
+Inst a (1 unstable [all])
+Inst c (1 unstable [all])
+Conf d (1 unstable [all])
+Conf a (1 unstable [all])
+Conf c (1 unstable [all])' apt install c a -s
+
+TOPLEVELCHOICE='Reading package lists...
+Building dependency tree...
+The following NEW packages will be installed:
+  a c d
+0 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
+Inst d (1 unstable [all])
+Inst a (1 unstable [all])
+Inst c (1 unstable [all])
+Conf d (1 unstable [all])
+Conf a (1 unstable [all])
+Conf c (1 unstable [all])'
+testsuccessequal "$TOPLEVELCHOICE" apt install d a c -s
+testsuccessequal "$TOPLEVELCHOICE" apt install a c d -s
+
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+  MarkInstall a:amd64 < none -> 1 @un puN Ib > FU=1
+    MarkInstall b:amd64 < none -> 1 @un uN > FU=0
+  MarkInstall c:amd64 < none -> 1 @un puN > FU=1
+Starting pkgProblemResolver with broken count: 0
+Starting 2 pkgProblemResolver with broken count: 0
+Done
+The following additional packages will be installed:
+  b
+The following NEW packages will be installed:
+  a b c
+0 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
+Inst b (1 unstable [all])
+Inst a (1 unstable [all])
+Inst c (1 unstable [all])
+Conf b (1 unstable [all])
+Conf a (1 unstable [all])
+Conf c (1 unstable [all])' apt install a a a c a a a -s -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
diff --git a/test/integration/test-multiarch-allowed b/test/integration/test-multiarch-allowed
index db7f37169..fc63d0e33 100755
--- a/test/integration/test-multiarch-allowed
+++ b/test/integration/test-multiarch-allowed
@@ -62,12 +62,18 @@ Inst foo:i386 (1 unstable [i386])
 Inst needsfoo:i386 (1 unstable [i386])
 Conf foo:i386 (1 unstable [i386])
 Conf needsfoo:i386 (1 unstable [i386])' aptget install needsfoo:i386 -s
+# FIXME: same problem, but two different unmet dependency messages depending on install order
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
- needsfoo:i386 : Depends: foo:i386 but it is not installable
+ foo : Conflicts: foo:i386 but 1 is to be installed
+ foo:i386 : Conflicts: foo but 1 is to be installed
 E: Unable to correct problems, you have held broken packages." aptget install needsfoo:i386 foo:amd64 -s
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
+ needsfoo:i386 : Depends: foo:i386 but it is not installable
+E: Unable to correct problems, you have held broken packages." aptget install foo:amd64 needsfoo:i386 -s
+testfailureequal "$BADPREFIX
+The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed
  foo:i386 : Conflicts: foo but 1 is to be installed
 E: Unable to correct problems, you have held broken packages." aptget install needsfoo foo:i386 -s