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.

2 files changed, 82 insertions, 1 deletions

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