reimplement build-dep via apts normal resolver

build-dep was implemented by parsing the build-dependencies of a package
and figuring out which packages to install/remove based on this. That
means that for the first level of dependencies build-dep was
implementing its very own resolver with all the benefits (aka: bugs)
this gives us for not using the existing resolver for all levels.

Making this work involves generating a dummy binary package with fitting
Depends and Conflicts and as we can't create them out of thin air the
cache generation needs to be involved so we end up writing a Packages
file which we want to parse – after we have parsed the other Packages
files already. With .dsc/.deb files we could add them before we started
parsing anything.

With a bit of care we can avoid generating too much data we have to
throw away again (as many parts assume that e.g. the count of packages
doesn't change midair), so that on a speed front there shouldn't be
much of a difference, but output can be slightly confusing as if we have
a completely valid cache on disk the "Reading package lists... Done" is
printed two times – but apt is pretty quick about it in that case.

Closes: #137560, #444930, #489911, #583914, #728317, #812173

6 files changed, 128 insertions, 32 deletions

diff --git a/test/integration/test-apt-get-build-dep b/test/integration/test-apt-get-build-dep
index b1c36222a..2cd4f57ec 100755
--- a/test/integration/test-apt-get-build-dep
+++ b/test/integration/test-apt-get-build-dep
@@ -38,9 +38,9 @@ Files:
 EOF
 
 test2vcardbuilddep() {
-	testsuccessequal "Reading package lists...
+	testsuccessequal "Note, using file './2vcard_0.5-3.dsc' to get the build dependencies
+Reading package lists...
 Building dependency tree...
-Note, using file './2vcard_0.5-3.dsc' to get the build dependencies
 The following packages will be REMOVED:
   build-conflict
 The following NEW packages will be installed:
@@ -125,9 +125,9 @@ Description: install packages using the apt protocol - common data
 
 EOF
 
-testsuccessequal "Reading package lists...
+testsuccessequal "Note, using directory './foo-1.0' to get the build dependencies
+Reading package lists...
 Building dependency tree...
-Note, using directory './foo-1.0' to get the build dependencies
 The following NEW packages will be installed:
   build-essential debhelper
 0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
@@ -141,14 +141,9 @@ testsuccess aptget build-dep --simulate ../foo-1.0
 testsuccess aptget build-dep --simulate "$(readlink -f ../foo-1.0)"
 cd ..
 
+testfailureequal 'E: Must specify at least one package to check builddeps for' aptget build-dep
+testfailureequal 'E: No architecture information available for armel. See apt.conf(5) APT::Architectures for setup' aptget build-dep --simulate ./foo-1.0 -a armel
 testfailureequal 'Reading package lists...
-Building dependency tree...
-E: Must specify at least one package to check builddeps for' aptget build-dep
-testfailureequal 'Reading package lists...
-Building dependency tree...
-E: No architecture information available for armel. See apt.conf(5) APT::Architectures for setup' aptget build-dep --simulate ./foo-1.0 -a armel
-testfailureequal 'Reading package lists...
-Building dependency tree...
 E: Unable to find a source package for foo' aptget build-dep --simulate foo
 
 msgmsg 'Test with a dsc' 'with comments'
@@ -172,9 +167,9 @@ Standards-Version: 3.9.6
 
 # or this?
 EOF
-testsuccessequal "Reading package lists...
+testsuccessequal "Note, using file './comments.dsc' to get the build dependencies
+Reading package lists...
 Building dependency tree...
-Note, using file './comments.dsc' to get the build dependencies
 The following NEW packages will be installed:
   build-depends build-essential debhelper
 0 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
@@ -184,3 +179,16 @@ Inst debhelper (7 stable [i386])
 Conf build-depends (1 stable [i386])
 Conf build-essential (1 stable [i386])
 Conf debhelper (7 stable [i386])" aptget build-dep --simulate ./comments.dsc
+testsuccessequal "Note, using file './comments.dsc' to get the build dependencies
+Reading package lists...
+Building dependency tree...
+Execute external solver...
+The following NEW packages will be installed:
+  build-depends build-essential debhelper
+0 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
+Inst build-depends (1 stable [i386])
+Inst build-essential (1 stable [i386])
+Inst debhelper (7 stable [i386])
+Conf build-depends (1 stable [i386])
+Conf build-essential (1 stable [i386])
+Conf debhelper (7 stable [i386])" aptget build-dep --simulate ./comments.dsc --solver apt
diff --git a/test/integration/test-architecture-specification-parsing b/test/integration/test-architecture-specification-parsing
index 5db05e9a0..23199384e 100755
--- a/test/integration/test-architecture-specification-parsing
+++ b/test/integration/test-architecture-specification-parsing
@@ -71,6 +71,7 @@ Conf foo (1.0 stable [${NATIVE}])
 Conf pkg-arch-foo-unrelated-no2 (1.0 stable [${NATIVE}])" aptget install pkg-arch-foo-unrelated-no2 -s
 
 testsuccessequal "Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   foo
@@ -79,11 +80,13 @@ Inst foo (1.0 stable [${NATIVE}])
 Conf foo (1.0 stable [${NATIVE}])" aptget build-dep pkg-arch-foo -s
 
 testsuccessequal 'Reading package lists...
-Building dependency tree...
 pkg-arch-no-foo has no build depends.
+Reading package lists...
+Building dependency tree...
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.' aptget build-dep pkg-arch-no-foo -s
 
 testsuccessequal "Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   foo
@@ -92,6 +95,7 @@ Inst foo (1.0 stable [${NATIVE}])
 Conf foo (1.0 stable [${NATIVE}])" aptget build-dep pkg-arch-foo-unrelated-no -s
 
 testsuccessequal "Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   foo
@@ -100,8 +104,9 @@ Inst foo (1.0 stable [${NATIVE}])
 Conf foo (1.0 stable [${NATIVE}])" aptget build-dep pkg-arch-foo-unrelated-no2 -s
 
 testsuccessequal 'Reading package lists...
-Building dependency tree...
 no-depends has no build depends.
+Reading package lists...
+Building dependency tree...
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.' aptget build-dep no-depends -s
 
 # this is not really testing APT - more that dpkg is in line with us
diff --git a/test/integration/test-bug-632221-cross-dependency-satisfaction b/test/integration/test-bug-632221-cross-dependency-satisfaction
index dad6e47fa..066e29d99 100755
--- a/test/integration/test-bug-632221-cross-dependency-satisfaction
+++ b/test/integration/test-bug-632221-cross-dependency-satisfaction
@@ -35,17 +35,45 @@ insertsource 'unstable' 'source-specific-armel' 'armel' '1' 'Build-Depends: spec
 
 setupaptarchive
 
-testfailureequal "Reading package lists...
+testfailureequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
-E: Build-Depends dependency for forbidden-no can't be satisfied because amdboot:any is not allowed on 'Multi-Arch: no' packages" aptget build-dep forbidden-no -s -a armel
-testfailureequal "Reading package lists...
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ builddeps:forbidden-no:armel : Depends: amdboot:any but it is not installable
+E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-no -s -a armel
+testfailureequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
-E: Build-Depends dependency for forbidden-same can't be satisfied because libc6:any is not allowed on 'Multi-Arch: same' packages" aptget build-dep forbidden-same -s -a armel
-testfailureequal "Reading package lists...
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ builddeps:forbidden-same:armel : Depends: libc6:any but it is not installable
+E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-same -s -a armel
+testfailureequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
-E: Build-Depends dependency for forbidden-foreign can't be satisfied because doxygen:any is not allowed on 'Multi-Arch: foreign' packages" aptget build-dep forbidden-foreign -s -a armel
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ builddeps:forbidden-foreign:armel : Depends: doxygen:any but it is not installable
+E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-foreign -s -a armel
 
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   libc6 specific
@@ -55,6 +83,7 @@ Inst specific (1.0 unstable [amd64])
 Conf libc6 (1.0 unstable [amd64])
 Conf specific (1.0 unstable [amd64])' aptget build-dep source-specific-amd64 -s
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   libc6 specific
@@ -65,6 +94,7 @@ Conf libc6 (1.0 unstable [amd64])
 Conf specific (1.0 unstable [amd64])' aptget build-dep source-specific-amd64 -s -a armel
 
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   libc6:armel specific:armel
@@ -74,6 +104,7 @@ Inst specific:armel (1.0 unstable [armel])
 Conf libc6:armel (1.0 unstable [armel])
 Conf specific:armel (1.0 unstable [armel])' aptget build-dep source-specific-armel -s
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   libc6:armel specific:armel
@@ -84,6 +115,7 @@ Conf libc6:armel (1.0 unstable [armel])
 Conf specific:armel (1.0 unstable [armel])' aptget build-dep source-specific-armel -s -a armel
 
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   amdboot cool doxygen foreigner libc6 libc6-dev libfwibble-dev libfwibble1
@@ -109,6 +141,7 @@ Conf libfwibble-dev (1.0 unstable [amd64])
 Conf linux-stuff (1.0 unstable [amd64])' aptget build-dep apt -s
 
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   amdboot arm-stuff:armel cool doxygen foreigner libc6 libc6:armel libc6-dev
@@ -165,6 +198,7 @@ Conf libfwibble1 (1.0 unstable [armel])
 Conf libfwibble-dev (1.0 unstable [armel])' aptget build-dep apt -s
 
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   amdboot:amd64 cool doxygen foreigner libc6 libc6:amd64 libc6-dev
@@ -202,9 +236,12 @@ testsuccessequal 'Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   amdboot doxygen libc6 libc6-dev libfwibble-dev libfwibble1 linux-stuff
-0 upgraded, 7 newly installed, 0 to remove and 2 not upgraded.
+The following packages will be upgraded:
+  foreigner:armel
+1 upgraded, 7 newly installed, 0 to remove and 1 not upgraded.
 Inst amdboot (1.0 unstable [amd64])
 Inst doxygen (1.0 unstable [amd64])
+Inst foreigner:armel [0.5] (1.0 unstable [armel])
 Inst libc6 (1.0 unstable [amd64])
 Inst libc6-dev (1.0 unstable [amd64])
 Inst libfwibble1 (1.0 unstable [amd64])
@@ -212,6 +249,7 @@ Inst libfwibble-dev (1.0 unstable [amd64])
 Inst linux-stuff (1.0 unstable [amd64])
 Conf amdboot (1.0 unstable [amd64])
 Conf doxygen (1.0 unstable [amd64])
+Conf foreigner:armel (1.0 unstable [armel])
 Conf libc6 (1.0 unstable [amd64])
 Conf libc6-dev (1.0 unstable [amd64])
 Conf libfwibble1 (1.0 unstable [amd64])
@@ -219,13 +257,17 @@ Conf libfwibble-dev (1.0 unstable [amd64])
 Conf linux-stuff (1.0 unstable [amd64])' aptget build-dep apt -s
 
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   amdboot arm-stuff:armel doxygen libc6 libc6:armel libc6-dev libc6-dev:armel
   libfwibble-dev:armel libfwibble1:armel
-0 upgraded, 9 newly installed, 0 to remove and 2 not upgraded.
+The following packages will be upgraded:
+  cool
+1 upgraded, 9 newly installed, 0 to remove and 1 not upgraded.
 Inst amdboot (1.0 unstable [amd64])
 Inst arm-stuff:armel (1.0 unstable [armel])
+Inst cool [0.5] (1.0 unstable [amd64])
 Inst doxygen (1.0 unstable [amd64])
 Inst libc6 (1.0 unstable [amd64])
 Inst libc6:armel (1.0 unstable [armel])
@@ -235,6 +277,7 @@ Inst libfwibble1:armel (1.0 unstable [armel])
 Inst libfwibble-dev:armel (1.0 unstable [armel])
 Conf amdboot (1.0 unstable [amd64])
 Conf arm-stuff:armel (1.0 unstable [armel])
+Conf cool (1.0 unstable [amd64])
 Conf doxygen (1.0 unstable [amd64])
 Conf libc6 (1.0 unstable [amd64])
 Conf libc6:armel (1.0 unstable [armel])
@@ -273,13 +316,18 @@ Conf libfwibble1 (1.0 unstable [armel])
 Conf libfwibble-dev (1.0 unstable [armel])' aptget build-dep apt -s
 
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   amdboot:amd64 doxygen libc6 libc6:amd64 libc6-dev libc6-dev:amd64
   libfwibble-dev:amd64 libfwibble1:amd64 linux-stuff:amd64
-0 upgraded, 9 newly installed, 0 to remove and 2 not upgraded.
+The following packages will be upgraded:
+  cool:amd64 foreigner
+2 upgraded, 9 newly installed, 0 to remove and 0 not upgraded.
 Inst amdboot:amd64 (1.0 unstable [amd64])
+Inst cool:amd64 [0.5] (1.0 unstable [amd64])
 Inst doxygen (1.0 unstable [armel])
+Inst foreigner [0.5] (1.0 unstable [armel])
 Inst libc6 (1.0 unstable [armel])
 Inst libc6:amd64 (1.0 unstable [amd64])
 Inst libc6-dev (1.0 unstable [armel])
@@ -288,7 +336,9 @@ Inst libfwibble1:amd64 (1.0 unstable [amd64])
 Inst libfwibble-dev:amd64 (1.0 unstable [amd64])
 Inst linux-stuff:amd64 (1.0 unstable [amd64])
 Conf amdboot:amd64 (1.0 unstable [amd64])
+Conf cool:amd64 (1.0 unstable [amd64])
 Conf doxygen (1.0 unstable [armel])
+Conf foreigner (1.0 unstable [armel])
 Conf libc6 (1.0 unstable [armel])
 Conf libc6:amd64 (1.0 unstable [amd64])
 Conf libc6-dev (1.0 unstable [armel])
diff --git a/test/integration/test-bug-661537-build-profiles-support b/test/integration/test-bug-661537-build-profiles-support
index 707562df3..91115ea18 100755
--- a/test/integration/test-bug-661537-build-profiles-support
+++ b/test/integration/test-bug-661537-build-profiles-support
@@ -25,6 +25,7 @@ insertsource 'unstable' 'spec-7' 'any' '1' 'Build-Depends: foo <stage1> <!notest
 setupaptarchive
 
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   bar
@@ -59,6 +60,7 @@ Inst bar (1.0 unstable [all])
 Conf bar (1.0 unstable [all])' aptget build-dep buildprofiles -s -o APT::Architecture=i386 -P stage1
 
 KEEP='Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   foo
@@ -67,8 +69,9 @@ Inst foo (1.0 unstable [all])
 Conf foo (1.0 unstable [all])'
 setdrop() {
 	DROP="Reading package lists...
-Building dependency tree...
 $1 has no build depends.
+Reading package lists...
+Building dependency tree...
 0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded."
 }
 
@@ -114,6 +117,7 @@ testprofile() {
 	testwithdpkg "$2" "$3" "$4"
 }
 
+testsuccess aptcache gencaches
 setdrop 'spec-1'
 testprofile 'spec-1' 'foo <!stage1>' '' "$KEEP"
 testprofile 'spec-1' 'foo <!stage1>' 'stage1' "$DROP"
diff --git a/test/integration/test-bug-683786-build-dep-on-virtual-packages b/test/integration/test-bug-683786-build-dep-on-virtual-packages
index dd599a0d0..831e1f831 100755
--- a/test/integration/test-bug-683786-build-dep-on-virtual-packages
+++ b/test/integration/test-bug-683786-build-dep-on-virtual-packages
@@ -33,6 +33,7 @@ Reverse Provides: ' aptcache showpkg po-debconf:armel
 testsuccessequal 'N: Unable to locate package texi2html:armel' aptcache showpkg texi2html:armel
 
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
   po-debconf
@@ -41,16 +42,33 @@ Inst po-debconf (1 unstable [all])
 Conf po-debconf (1 unstable [all])' aptget build-dep dash -s
 
 testfailureequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
-E: Build-Depends dependency for dash cannot be satisfied because the package po-debconf cannot be found' aptget build-dep -aarmel dash -s
-
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ builddeps:dash:armel : Depends: po-debconf:armel but it is not installable
+E: Unable to correct problems, you have held broken packages.' aptget build-dep -aarmel dash -s
 testfailureequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
-E: Build-Depends dependency for diffutils cannot be satisfied because the package texi2html cannot be found' aptget build-dep -aarmel diffutils -s
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ builddeps:diffutils:armel : Depends: texi2html:armel but it is not installable
+E: Unable to correct problems, you have held broken packages.' aptget build-dep -aarmel diffutils -s
 
 testsuccessequal "Reading package lists...
+Reading package lists...
 Building dependency tree...
-Note, selecting 'libselinux1-dev' instead of 'libselinux-dev'
 The following NEW packages will be installed:
   libselinux1-dev
 0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
@@ -58,12 +76,21 @@ Inst libselinux1-dev (1 unstable [amd64])
 Conf libselinux1-dev (1 unstable [amd64])" aptget build-dep sed -s
 
 testfailureequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
-E: Build-Depends dependency for sed cannot be satisfied because the package libselinux-dev cannot be found' aptget build-dep -aarmel sed -s
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ builddeps:sed:armel : Depends: libselinux-dev:armel but it is not installable
+E: Unable to correct problems, you have held broken packages.' aptget build-dep -aarmel sed -s
 
 testsuccessequal "Reading package lists...
+Reading package lists...
 Building dependency tree...
-Note, selecting 'libsehurd1-dev' instead of 'libsehurd-dev'
 The following NEW packages will be installed:
   libsehurd1-dev
 0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
@@ -71,8 +98,8 @@ Inst libsehurd1-dev (1 unstable [amd64])
 Conf libsehurd1-dev (1 unstable [amd64])" aptget build-dep sed2 -s
 
 testsuccessequal "Reading package lists...
+Reading package lists...
 Building dependency tree...
-Note, selecting 'libsehurd1-dev:armel' instead of 'libsehurd-dev:armel'
 The following NEW packages will be installed:
   libsehurd1-dev:armel
 0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
diff --git a/test/integration/test-bug-720597-build-dep-purge b/test/integration/test-bug-720597-build-dep-purge
index 8298d0f64..5d451f969 100755
--- a/test/integration/test-bug-720597-build-dep-purge
+++ b/test/integration/test-bug-720597-build-dep-purge
@@ -14,6 +14,7 @@ buildsimplenativepackage 'pkgc' 'amd64' '1' 'stable' 'Build-Depends: pkgb'
 setupaptarchive
 
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following packages will be REMOVED:
   pkga
@@ -25,6 +26,7 @@ Inst pkgb (1 stable [amd64])
 Conf pkgb (1 stable [amd64])' aptget build-dep pkgc -s
 
 testsuccessequal 'Reading package lists...
+Reading package lists...
 Building dependency tree...
 The following packages will be REMOVED:
   pkga*