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

15 files changed, 398 insertions, 427 deletions

diff --git a/apt-pkg/cachefile.cc b/apt-pkg/cachefile.cc
index 92a3b201b..3e3540bbd 100644
--- a/apt-pkg/cachefile.cc
+++ b/apt-pkg/cachefile.cc
@@ -26,6 +26,7 @@
 #include <apt-pkg/depcache.h>
 #include <apt-pkg/mmap.h>
 #include <apt-pkg/pkgcache.h>
+#include <apt-pkg/indexfile.h>
 
 #include <string.h>
 #include <unistd.h>
@@ -186,6 +187,60 @@ bool pkgCacheFile::Open(OpProgress *Progress, bool WithLock)
    return true;
 }
 									/*}}}*/
+bool pkgCacheFile::AddIndexFile(pkgIndexFile * const File)		/*{{{*/
+{
+   if (SrcList == NULL)
+      if (BuildSourceList() == false)
+	 return false;
+   SrcList->AddVolatileFile(File);
+
+   if (Cache == nullptr || File->HasPackages() == false || File->Exists() == false)
+      return true;
+
+   if (File->FindInCache(*Cache).end() == false)
+      return _error->Warning("Duplicate sources.list entry %s",
+	    File->Describe().c_str());
+
+   if (ExternOwner == false)
+   {
+      delete DCache;
+      delete Cache;
+   }
+   delete Policy;
+   DCache = NULL;
+   Policy = NULL;
+   Cache = NULL;
+
+   if (ExternOwner == false)
+   {
+      // a dynamic mmap means that we have build at least parts of the cache
+      // in memory – which we might or might not have written to disk.
+      // Throwing away would therefore be a very costly operation we want to avoid
+      DynamicMMap * dynmmap = dynamic_cast<DynamicMMap*>(Map);
+      if (dynmmap != nullptr)
+      {
+	 {
+	    pkgCacheGenerator Gen(dynmmap, nullptr);
+	    if (File->Merge(Gen, nullptr) == false)
+	       return false;
+	 }
+	 Cache = new pkgCache(Map);
+	 return _error->PendingError() == false;
+      }
+      else
+      {
+	 delete Map;
+	 Map = NULL;
+      }
+   }
+   else
+   {
+      ExternOwner = false;
+      Map = NULL;
+   }
+   return true;
+}
+									/*}}}*/
 // CacheFile::RemoveCaches - remove all cache files from disk		/*{{{*/
 // ---------------------------------------------------------------------
 /* */
diff --git a/apt-pkg/cachefile.h b/apt-pkg/cachefile.h
index df724ff45..e23f37675 100644
--- a/apt-pkg/cachefile.h
+++ b/apt-pkg/cachefile.h
@@ -32,6 +32,7 @@
 class MMap;
 class pkgPolicy;
 class pkgSourceList;
+class pkgIndexFile;
 class OpProgress;
 
 class pkgCacheFile
@@ -74,6 +75,8 @@ class pkgCacheFile
    static void RemoveCaches();
    void Close();
 
+   bool AddIndexFile(pkgIndexFile * const File);
+
    inline pkgCache* GetPkgCache() { BuildCaches(NULL, false); return Cache; };
    inline pkgDepCache* GetDepCache() { BuildDepCache(); return DCache; };
    inline pkgPolicy* GetPolicy() { BuildPolicy(); return Policy; };
diff --git a/apt-pkg/deb/debindexfile.cc b/apt-pkg/deb/debindexfile.cc
index c11efd0ae..84dabc06b 100644
--- a/apt-pkg/deb/debindexfile.cc
+++ b/apt-pkg/deb/debindexfile.cc
@@ -297,6 +297,39 @@ std::string debDebianSourceDirIndex::GetComponent() const
    return "local-control";
 }
 									/*}}}*/
+// String Package Index - a string of Packages file content		/*{{{*/
+std::string debStringPackageIndex::GetArchitecture() const
+{
+   return std::string();
+}
+std::string debStringPackageIndex::GetComponent() const
+{
+   return "apt-tmp-index";
+}
+uint8_t debStringPackageIndex::GetIndexFlags() const
+{
+   return pkgCache::Flag::NotSource;
+}
+const pkgIndexFile::Type *debStringPackageIndex::GetType() const
+{
+   return pkgIndexFile::Type::GetType("Debian Package Index");
+}
+debStringPackageIndex::debStringPackageIndex(std::string const &content) :
+   pkgDebianIndexRealFile("", false), d(NULL)
+{
+   char fn[1024];
+   std::string const tempdir = GetTempDir();
+   snprintf(fn, sizeof(fn), "%s/%s.XXXXXX", tempdir.c_str(), "apt-tmp-index");
+   int const fd = mkstemp(fn);
+   File = fn;
+   FileFd::Write(fd, content.data(), content.length());
+   close(fd);
+}
+debStringPackageIndex::~debStringPackageIndex()
+{
+   RemoveFile("~debStringPackageIndex", File);
+}
+									/*}}}*/
 
 // Index File types for Debian						/*{{{*/
 class APT_HIDDEN debIFTypeSrc : public pkgIndexFile::Type
diff --git a/apt-pkg/deb/debindexfile.h b/apt-pkg/deb/debindexfile.h
index 890141dff..3652f631c 100644
--- a/apt-pkg/deb/debindexfile.h
+++ b/apt-pkg/deb/debindexfile.h
@@ -176,4 +176,23 @@ public:
    virtual const Type *GetType() const APT_OVERRIDE APT_CONST;
 };
 
+class debStringPackageIndex : public pkgDebianIndexRealFile
+{
+   void * const d;
+protected:
+   virtual std::string GetArchitecture() const APT_OVERRIDE;
+   virtual std::string GetComponent() const APT_OVERRIDE;
+   virtual uint8_t GetIndexFlags() const APT_OVERRIDE;
+
+public:
+   virtual const Type *GetType() const APT_OVERRIDE APT_CONST;
+
+   // Interface for the Cache Generator
+   virtual bool HasPackages() const APT_OVERRIDE {return true;};
+   // Abort if the file does not exist.
+   virtual bool Exists() const APT_OVERRIDE {return true;};
+
+   debStringPackageIndex(std::string const &content);
+   virtual ~debStringPackageIndex();
+};
 #endif
diff --git a/apt-pkg/indexfile.cc b/apt-pkg/indexfile.cc
index dfd482c04..657cdfb36 100644
--- a/apt-pkg/indexfile.cc
+++ b/apt-pkg/indexfile.cc
@@ -267,7 +267,9 @@ std::string pkgDebianIndexTargetFile::GetProgressDescription() const
 pkgDebianIndexRealFile::pkgDebianIndexRealFile(std::string const &pFile, bool const Trusted) :/*{{{*/
    pkgDebianIndexFile(Trusted), d(NULL)
 {
-   if (pFile == "/nonexistent/stdin")
+   if (pFile.empty())
+      ;
+   else if (pFile == "/nonexistent/stdin")
       File = pFile;
    else
       File = flAbsPath(pFile);
diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc
index 0dbac3df8..120b0c414 100644
--- a/apt-pkg/pkgcachegen.cc
+++ b/apt-pkg/pkgcachegen.cc
@@ -1735,7 +1735,7 @@ bool pkgCacheGenerator::MakeStatusCache(pkgSourceList &List,OpProgress *Progress
    }
 
    if (Debug == true)
-      std::clog << "Caches done. Now bring in the volatile files (if any)" << std::endl;
+      std::clog << "Caches done. " << (volatile_fine ? "No volatile files, so we are done here." : "Now bring in the volatile files") << std::endl;
 
    if (volatile_fine == false)
    {
diff --git a/apt-private/private-install.cc b/apt-private/private-install.cc
index 73aebaf2f..3f57b55e2 100644
--- a/apt-private/private-install.cc
+++ b/apt-private/private-install.cc
@@ -41,6 +41,37 @@
 									/*}}}*/
 class pkgSourceList;
 
+bool CheckNothingBroken(CacheFile &Cache)				/*{{{*/
+{
+   // Now we check the state of the packages,
+   if (Cache->BrokenCount() == 0)
+      return true;
+
+   c1out <<
+      _("Some packages could not be installed. This may mean that you have\n"
+	    "requested an impossible situation or if you are using the unstable\n"
+	    "distribution that some required packages have not yet been created\n"
+	    "or been moved out of Incoming.") << std::endl;
+   /*
+   if (Packages == 1)
+   {
+      c1out << std::endl;
+      c1out <<
+	 _("Since you only requested a single operation it is extremely likely that\n"
+	       "the package is simply not installable and a bug report against\n"
+	       "that package should be filed.") << std::endl;
+   }
+   */
+
+   c1out << _("The following information may help to resolve the situation:") << std::endl;
+   c1out << std::endl;
+   ShowBroken(c1out,Cache,false);
+   if (_error->PendingError() == true)
+      return false;
+   else
+      return _error->Error(_("Broken packages"));
+}
+									/*}}}*/
 // InstallPackages - Actually download and install the packages		/*{{{*/
 // ---------------------------------------------------------------------
 /* This displays the informative messages describing what is going to 
@@ -364,7 +395,7 @@ bool InstallPackages(CacheFile &Cache,bool ShwKept,bool Ask, bool Safety)
 // DoAutomaticRemove - Remove all automatic unused packages		/*{{{*/
 // ---------------------------------------------------------------------
 /* Remove unused automatic packages */
-static bool DoAutomaticRemove(CacheFile &Cache)
+bool DoAutomaticRemove(CacheFile &Cache)
 {
    bool Debug = _config->FindI("Debug::pkgAutoRemove",false);
    bool doAutoRemove = _config->FindB("APT::Get::AutomaticRemove", false);
@@ -628,33 +659,8 @@ bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, std::vector<const cha
 	    return false;
       }
 
-      // Now we check the state of the packages,
-      if (Cache->BrokenCount() != 0)
-      {
-	 c1out << 
-	    _("Some packages could not be installed. This may mean that you have\n" 
-	      "requested an impossible situation or if you are using the unstable\n" 
-	      "distribution that some required packages have not yet been created\n"
-	      "or been moved out of Incoming.") << std::endl;
-	 /*
-	 if (Packages == 1)
-	 {
-	    c1out << std::endl;
-	    c1out << 
-	       _("Since you only requested a single operation it is extremely likely that\n"
-		 "the package is simply not installable and a bug report against\n" 
-		 "that package should be filed.") << std::endl;
-	 }
-	 */
-
-	 c1out << _("The following information may help to resolve the situation:") << std::endl;
-	 c1out << std::endl;
-	 ShowBroken(c1out,Cache,false);
-	 if (_error->PendingError() == true)
-	    return false;
-	 else
-	    return _error->Error(_("Broken packages"));
-      }
+      if (CheckNothingBroken(Cache) == false)
+	 return false;
    }
    if (!DoAutomaticRemove(Cache)) 
       return false;
@@ -811,7 +817,17 @@ bool DoInstall(CommandLine &CmdL)
 
 // TryToInstall - Mark a package for installation			/*{{{*/
 void TryToInstall::operator() (pkgCache::VerIterator const &Ver) {
+   if (unlikely(Ver.end()))
+   {
+      _error->Fatal("The given version to TryToInstall is invalid!");
+      return;
+   }
    pkgCache::PkgIterator Pkg = Ver.ParentPkg();
+   if (unlikely(Pkg.end()))
+   {
+      _error->Fatal("The given version to TryToInstall has an invalid parent package!");
+      return;
+   }
 
    Cache->GetDepCache()->SetCandidateVersion(Ver);
    pkgDepCache::StateCache &State = (*Cache)[Pkg];
diff --git a/apt-private/private-install.h b/apt-private/private-install.h
index 7a8cd5513..6bb863f61 100644
--- a/apt-private/private-install.h
+++ b/apt-private/private-install.h
@@ -26,6 +26,8 @@ bool DoCacheManipulationFromCommandLine(CommandLine &CmdL, CacheFile &Cache, int
 APT_PUBLIC bool InstallPackages(CacheFile &Cache,bool ShwKept,bool Ask = true,
                         bool Safety = true);
 
+bool CheckNothingBroken(CacheFile &Cache);
+bool DoAutomaticRemove(CacheFile &Cache);
 
 // TryToInstall - Mark a package for installation			/*{{{*/
 struct TryToInstall {
diff --git a/apt-private/private-source.cc b/apt-private/private-source.cc
index b2abae112..a6b446587 100644
--- a/apt-private/private-source.cc
+++ b/apt-private/private-source.cc
@@ -21,6 +21,7 @@
 #include <apt-pkg/srcrecords.h>
 #include <apt-pkg/strutl.h>
 #include <apt-pkg/version.h>
+#include <apt-pkg/policy.h>
 
 #include <apt-private/private-cachefile.h>
 #include <apt-private/private-cacheset.h>
@@ -28,6 +29,8 @@
 #include <apt-private/private-install.h>
 #include <apt-private/private-source.h>
 
+#include <apt-pkg/debindexfile.h>
+
 #include <stddef.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -36,6 +39,7 @@
 #include <unistd.h>
 
 #include <iostream>
+#include <sstream>
 #include <set>
 #include <string>
 #include <vector>
@@ -43,50 +47,9 @@
 #include <apti18n.h>
 									/*}}}*/
 
-// TryToInstallBuildDep - Try to install a single package		/*{{{*/
-// ---------------------------------------------------------------------
-/* This used to be inlined in DoInstall, but with the advent of regex package
-   name matching it was split out.. */
-static bool TryToInstallBuildDep(pkgCache::PkgIterator Pkg,pkgCacheFile &Cache,
-		  pkgProblemResolver &Fix,bool Remove,bool BrokenFix,
-		  bool AllowFail = true)
-{
-   if (Cache[Pkg].CandidateVer == 0 && Pkg->ProvidesList != 0)
-   {
-      CacheSetHelperAPTGet helper(c1out);
-      helper.showErrors(false);
-      pkgCache::VerIterator Ver = helper.canNotFindNewestVer(Cache, Pkg);
-      if (Ver.end() == false)
-	 Pkg = Ver.ParentPkg();
-      else if (helper.showVirtualPackageErrors(Cache) == false)
-	 return AllowFail;
-   }
-
-   if (_config->FindB("Debug::BuildDeps",false) == true)
-   {
-      if (Remove == true)
-	 std::cout << "  Trying to remove " << Pkg << std::endl;
-      else
-	 std::cout << "  Trying to install " << Pkg << std::endl;
-   }
-
-   if (Remove == true)
-   {
-      TryToRemove RemoveAction(Cache, &Fix);
-      RemoveAction(Pkg.VersionList());
-   } else if (Cache[Pkg].CandidateVer != 0) {
-      TryToInstall InstallAction(Cache, &Fix, BrokenFix);
-      InstallAction(Cache[Pkg].CandidateVerIter(Cache));
-      InstallAction.doAutoInstall();
-   } else
-      return AllowFail;
-
-   return true;
-}
-									/*}}}*/
 // GetReleaseFileForSourceRecord - Return Suite for the given srcrecord	/*{{{*/
 static pkgCache::RlsFileIterator GetReleaseFileForSourceRecord(CacheFile &CacheFile,
-      pkgSourceList *SrcList, pkgSrcRecords::Parser *Parse)
+      pkgSourceList const * const SrcList, pkgSrcRecords::Parser const * const Parse)
 {
    // try to find release
    const pkgIndexFile& CurrentIndexFile = Parse->Index();
@@ -108,13 +71,14 @@ static pkgCache::RlsFileIterator GetReleaseFileForSourceRecord(CacheFile &CacheF
 // FindSrc - Find a source record					/*{{{*/
 static pkgSrcRecords::Parser *FindSrc(const char *Name,
 			       pkgSrcRecords &SrcRecs,std::string &Src,
-			       CacheFile &CacheFile)
+			       CacheFile &Cache)
 {
+   if (Cache.BuildCaches(false) == false)
+      return nullptr;
    std::string VerTag, UserRequestedVerTag;
    std::string ArchTag = "";
    std::string RelTag = _config->Find("APT::Default-Release");
    std::string TmpSrc = Name;
-   pkgDepCache *Cache = CacheFile.GetDepCache();
 
    // extract release
    size_t found = TmpSrc.find_last_of("/");
@@ -144,9 +108,9 @@ static pkgSrcRecords::Parser *FindSrc(const char *Name,
    bool MatchSrcOnly = _config->FindB("APT::Get::Only-Source");
    pkgCache::PkgIterator Pkg;
    if (ArchTag != "")
-      Pkg = Cache->FindPkg(TmpSrc, ArchTag);
+      Pkg = Cache.GetPkgCache()->FindPkg(TmpSrc, ArchTag);
    else
-      Pkg = Cache->FindPkg(TmpSrc);
+      Pkg = Cache.GetPkgCache()->FindPkg(TmpSrc);
 
    // if we can't find a package but the user qualified with a arch,
    // error out here
@@ -245,7 +209,15 @@ static pkgSrcRecords::Parser *FindSrc(const char *Name,
 	 // choose a good candidate and proceed with that.
 	 // Maybe we will find a source later on with the right VerTag
 	 // or RelTag
-	 pkgCache::VerIterator const Ver = Cache->GetCandidateVersion(Pkg);
+	 if (Cache.BuildPolicy() == false)
+	    return nullptr;
+	 pkgPolicy * Policy = dynamic_cast<pkgPolicy*>(Cache.GetPolicy());
+	 if (Policy == nullptr)
+	 {
+	    _error->Fatal("Implementation error: dynamic up-casting policy engine failed in FindSrc!");
+	    return nullptr;
+	 }
+	 pkgCache::VerIterator const Ver = Policy->GetCandidateVer(Pkg);
 	 if (Ver.end() == false)
 	 {
 	    if (strcmp(Ver.SourcePkgName(),Ver.ParentPkg().Name()) != 0)
@@ -277,7 +249,7 @@ static pkgSrcRecords::Parser *FindSrc(const char *Name,
    pkgSrcRecords::Parser *Last = 0;
    unsigned long Offset = 0;
    std::string Version;
-   pkgSourceList *SrcList = CacheFile.GetSourceList();
+   pkgSourceList const * const SrcList = Cache.GetSourceList();
 
    /* Iterate over all of the hits, which includes the resulting
       binary packages in the search */
@@ -293,7 +265,7 @@ static pkgSrcRecords::Parser *FindSrc(const char *Name,
 		     // See if we need to look for a specific release tag
 		     if (RelTag != "" && UserRequestedVerTag == "")
 		     {
-			pkgCache::RlsFileIterator const Rls = GetReleaseFileForSourceRecord(CacheFile, SrcList, Parse);
+			pkgCache::RlsFileIterator const Rls = GetReleaseFileForSourceRecord(Cache, SrcList, Parse);
 			if (Rls.end() == false)
 			{
 			   if ((Rls->Archive != 0 && RelTag == Rls.Archive()) ||
@@ -611,306 +583,6 @@ bool DoSource(CommandLine &CmdL)
    return ExecWait(Process, "dpkg-source");
 }
 									/*}}}*/
-// InstallBuildDepsLoop							/*{{{*/
-static bool InstallBuildDepsLoop(CacheFile &Cache, std::string const &Src,
-      std::vector<pkgSrcRecords::Parser::BuildDepRec> const &BuildDeps,
-      bool const StripMultiArch, std::string const &hostArch)
-{
-   // Install the requested packages
-   std::vector <pkgSrcRecords::Parser::BuildDepRec>::const_iterator D;
-   pkgProblemResolver Fix(Cache);
-   bool skipAlternatives = false; // skip remaining alternatives in an or group
-   for (D = BuildDeps.begin(); D != BuildDeps.end(); ++D)
-   {
-      bool hasAlternatives = (((*D).Op & pkgCache::Dep::Or) == pkgCache::Dep::Or);
-
-      if (skipAlternatives == true)
-      {
-	 /*
-	  * if there are alternatives, we've already picked one, so skip
-	  * the rest
-	  *
-	  * TODO: this means that if there's a build-dep on A|B and B is
-	  * installed, we'll still try to install A; more importantly,
-	  * if A is currently broken, we cannot go back and try B. To fix
-	  * this would require we do a Resolve cycle for each package we
-	  * add to the install list. Ugh
-	  */
-	 if (!hasAlternatives)
-	    skipAlternatives = false; // end of or group
-	 continue;
-      }
-
-      if ((*D).Type == pkgSrcRecords::Parser::BuildConflict ||
-	    (*D).Type == pkgSrcRecords::Parser::BuildConflictIndep)
-      {
-	 pkgCache::GrpIterator Grp = Cache->FindGrp((*D).Package);
-	 // Build-conflicts on unknown packages are silently ignored
-	 if (Grp.end() == true)
-	    continue;
-
-	 for (pkgCache::PkgIterator Pkg = Grp.PackageList(); Pkg.end() == false; Pkg = Grp.NextPkg(Pkg))
-	 {
-	    pkgCache::VerIterator IV = (*Cache)[Pkg].InstVerIter(*Cache);
-	    /*
-	     * Remove if we have an installed version that satisfies the
-	     * version criteria
-	     */
-	    if (IV.end() == false &&
-		  Cache->VS().CheckDep(IV.VerStr(),(*D).Op,(*D).Version.c_str()) == true)
-	       TryToInstallBuildDep(Pkg,Cache,Fix,true,false);
-	 }
-      }
-      else // BuildDep || BuildDepIndep
-      {
-	 if (_config->FindB("Debug::BuildDeps",false) == true)
-	    std::cout << "Looking for " << (*D).Package << "...\n";
-
-	 pkgCache::PkgIterator Pkg;
-
-	 // Cross-Building?
-	 if (StripMultiArch == false && D->Type != pkgSrcRecords::Parser::BuildDependIndep)
-	 {
-	    size_t const colon = D->Package.find(":");
-	    if (colon != std::string::npos)
-	    {
-	       if (strcmp(D->Package.c_str() + colon, ":any") == 0 || strcmp(D->Package.c_str() + colon, ":native") == 0)
-		  Pkg = Cache->FindPkg(D->Package.substr(0,colon));
-	       else
-		  Pkg = Cache->FindPkg(D->Package);
-	    }
-	    else
-	       Pkg = Cache->FindPkg(D->Package, hostArch);
-
-	    // a bad version either is invalid or doesn't satify dependency
-#define BADVER(Ver) (Ver.end() == true || \
-      (D->Version.empty() == false && \
-       Cache->VS().CheckDep(Ver.VerStr(),D->Op,D->Version.c_str()) == false))
-
-	    APT::VersionList verlist;
-	    if (Pkg.end() == false)
-	    {
-	       pkgCache::VerIterator Ver = (*Cache)[Pkg].InstVerIter(*Cache);
-	       if (BADVER(Ver) == false)
-		  verlist.insert(Ver);
-	       Ver = (*Cache)[Pkg].CandidateVerIter(*Cache);
-	       if (BADVER(Ver) == false)
-		  verlist.insert(Ver);
-	    }
-	    if (verlist.empty() == true)
-	    {
-	       pkgCache::PkgIterator BuildPkg = Cache->FindPkg(D->Package, "native");
-	       if (BuildPkg.end() == false && Pkg != BuildPkg)
-	       {
-		  pkgCache::VerIterator Ver = (*Cache)[BuildPkg].InstVerIter(*Cache);
-		  if (BADVER(Ver) == false)
-		     verlist.insert(Ver);
-		  Ver = (*Cache)[BuildPkg].CandidateVerIter(*Cache);
-		  if (BADVER(Ver) == false)
-		     verlist.insert(Ver);
-	       }
-	    }
-#undef BADVER
-
-	    std::string forbidden;
-	    // We need to decide if host or build arch, so find a version we can look at
-	    APT::VersionList::const_iterator Ver = verlist.begin();
-	    for (; Ver != verlist.end(); ++Ver)
-	    {
-	       forbidden.clear();
-	       if (Ver->MultiArch == pkgCache::Version::No || Ver->MultiArch == pkgCache::Version::All)
-	       {
-		  if (colon == std::string::npos)
-		     Pkg = Ver.ParentPkg().Group().FindPkg(hostArch);
-		  else if (strcmp(D->Package.c_str() + colon, ":any") == 0)
-		     forbidden = "Multi-Arch: no";
-		  else if (strcmp(D->Package.c_str() + colon, ":native") == 0)
-		     Pkg = Ver.ParentPkg().Group().FindPkg("native");
-	       }
-	       else if (Ver->MultiArch == pkgCache::Version::Same)
-	       {
-		  if (colon == std::string::npos)
-		     Pkg = Ver.ParentPkg().Group().FindPkg(hostArch);
-		  else if (strcmp(D->Package.c_str() + colon, ":any") == 0)
-		     forbidden = "Multi-Arch: same";
-		  else if (strcmp(D->Package.c_str() + colon, ":native") == 0)
-		     Pkg = Ver.ParentPkg().Group().FindPkg("native");
-	       }
-	       else if ((Ver->MultiArch & pkgCache::Version::Foreign) == pkgCache::Version::Foreign)
-	       {
-		  if (colon == std::string::npos)
-		     Pkg = Ver.ParentPkg().Group().FindPkg("native");
-		  else if (strcmp(D->Package.c_str() + colon, ":any") == 0 ||
-			strcmp(D->Package.c_str() + colon, ":native") == 0)
-		     forbidden = "Multi-Arch: foreign";
-	       }
-	       else if ((Ver->MultiArch & pkgCache::Version::Allowed) == pkgCache::Version::Allowed)
-	       {
-		  if (colon == std::string::npos)
-		     Pkg = Ver.ParentPkg().Group().FindPkg(hostArch);
-		  else if (strcmp(D->Package.c_str() + colon, ":any") == 0)
-		  {
-		     // prefer any installed over preferred non-installed architectures
-		     pkgCache::GrpIterator Grp = Ver.ParentPkg().Group();
-		     // we don't check for version here as we are better of with upgrading than remove and install
-		     for (Pkg = Grp.PackageList(); Pkg.end() == false; Pkg = Grp.NextPkg(Pkg))
-			if (Pkg.CurrentVer().end() == false)
-			   break;
-		     if (Pkg.end() == true)
-			Pkg = Grp.FindPreferredPkg(true);
-		  }
-		  else if (strcmp(D->Package.c_str() + colon, ":native") == 0)
-		     Pkg = Ver.ParentPkg().Group().FindPkg("native");
-	       }
-
-	       if (forbidden.empty() == false)
-	       {
-		  if (_config->FindB("Debug::BuildDeps",false) == true)
-		     std::cout << D->Package.substr(colon, std::string::npos) << " is not allowed from " << forbidden << " package " << (*D).Package << " (" << Ver.VerStr() << ")" << std::endl;
-		  continue;
-	       }
-
-	       //we found a good version
-	       break;
-	    }
-	    if (Ver == verlist.end())
-	    {
-	       if (_config->FindB("Debug::BuildDeps",false) == true)
-		  std::cout << " No multiarch info as we have no satisfying installed nor candidate for " << D->Package << " on build or host arch" << std::endl;
-
-	       if (forbidden.empty() == false)
-	       {
-		  if (hasAlternatives)
-		     continue;
-		  return _error->Error(_("%s dependency for %s can't be satisfied "
-			   "because %s is not allowed on '%s' packages"),
-			pkgSrcRecords::Parser::BuildDepType(D->Type), Src.c_str(),
-			D->Package.c_str(), forbidden.c_str());
-	       }
-	    }
-	 }
-	 else
-	    Pkg = Cache->FindPkg(D->Package);
-
-	 if (Pkg.end() == true || (Pkg->VersionList == 0 && Pkg->ProvidesList == 0))
-	 {
-	    if (_config->FindB("Debug::BuildDeps",false) == true)
-	       std::cout << " (not found)" << (*D).Package << std::endl;
-
-	    if (hasAlternatives)
-	       continue;
-
-	    return _error->Error(_("%s dependency for %s cannot be satisfied "
-		     "because the package %s cannot be found"),
-		  pkgSrcRecords::Parser::BuildDepType(D->Type), Src.c_str(),
-		  (*D).Package.c_str());
-	 }
-
-	 pkgCache::VerIterator IV = (*Cache)[Pkg].InstVerIter(*Cache);
-	 if (IV.end() == false)
-	 {
-	    if (_config->FindB("Debug::BuildDeps",false) == true)
-	       std::cout << "  Is installed\n";
-
-	    if (D->Version.empty() == true ||
-		  Cache->VS().CheckDep(IV.VerStr(),(*D).Op,(*D).Version.c_str()) == true)
-	    {
-	       skipAlternatives = hasAlternatives;
-	       continue;
-	    }
-
-	    if (_config->FindB("Debug::BuildDeps",false) == true)
-	       std::cout << "    ...but the installed version doesn't meet the version requirement\n";
-
-	    if (((*D).Op & pkgCache::Dep::LessEq) == pkgCache::Dep::LessEq)
-	       return _error->Error(_("Failed to satisfy %s dependency for %s: Installed package %s is too new"),
-		     pkgSrcRecords::Parser::BuildDepType(D->Type), Src.c_str(), Pkg.FullName(true).c_str());
-	 }
-
-	 // Only consider virtual packages if there is no versioned dependency
-	 if ((*D).Version.empty() == true)
-	 {
-	    /*
-	     * If this is a virtual package, we need to check the list of
-	     * packages that provide it and see if any of those are
-	     * installed
-	     */
-	    pkgCache::PrvIterator Prv = Pkg.ProvidesList();
-	    for (; Prv.end() != true; ++Prv)
-	    {
-	       if (_config->FindB("Debug::BuildDeps",false) == true)
-		  std::cout << "  Checking provider " << Prv.OwnerPkg().FullName() << std::endl;
-
-	       if ((*Cache)[Prv.OwnerPkg()].InstVerIter(*Cache).end() == false)
-		  break;
-	    }
-
-	    if (Prv.end() == false)
-	    {
-	       if (_config->FindB("Debug::BuildDeps",false) == true)
-		  std::cout << "  Is provided by installed package " << Prv.OwnerPkg().FullName() << std::endl;
-	       skipAlternatives = hasAlternatives;
-	       continue;
-	    }
-	 }
-	 else // versioned dependency
-	 {
-	    pkgCache::VerIterator CV = (*Cache)[Pkg].CandidateVerIter(*Cache);
-	    if (CV.end() == true ||
-		  Cache->VS().CheckDep(CV.VerStr(),(*D).Op,(*D).Version.c_str()) == false)
-	    {
-	       if (hasAlternatives)
-		  continue;
-	       else if (CV.end() == false)
-		  return _error->Error(_("%s dependency for %s cannot be satisfied "
-			   "because candidate version of package %s "
-			   "can't satisfy version requirements"),
-			pkgSrcRecords::Parser::BuildDepType(D->Type), Src.c_str(),
-			D->Package.c_str());
-	       else
-		  return _error->Error(_("%s dependency for %s cannot be satisfied "
-			   "because package %s has no candidate version"),
-			pkgSrcRecords::Parser::BuildDepType(D->Type), Src.c_str(),
-			D->Package.c_str());
-	    }
-	 }
-
-	 if (TryToInstallBuildDep(Pkg,Cache,Fix,false,false,false) == true)
-	 {
-	    // We successfully installed something; skip remaining alternatives
-	    skipAlternatives = hasAlternatives;
-	    if(_config->FindB("APT::Get::Build-Dep-Automatic", false) == true)
-	       Cache->MarkAuto(Pkg, true);
-	    continue;
-	 }
-	 else if (hasAlternatives)
-	 {
-	    if (_config->FindB("Debug::BuildDeps",false) == true)
-	       std::cout << "  Unsatisfiable, trying alternatives\n";
-	    continue;
-	 }
-	 else
-	 {
-	    return _error->Error(_("Failed to satisfy %s dependency for %s: %s"),
-		  pkgSrcRecords::Parser::BuildDepType(D->Type),
-		  Src.c_str(),
-		  (*D).Package.c_str());
-	 }
-      }
-   }
-
-   if (Fix.Resolve(true) == false)
-      _error->Discard();
-
-   // Now we check the state of the packages,
-   if (Cache->BrokenCount() != 0)
-   {
-      ShowBroken(std::cout, Cache, false);
-      return _error->Error(_("Build-dependencies for %s could not be satisfied."), Src.c_str());
-   }
-   return true;
-}
-									/*}}}*/
 // DoBuildDep - Install/removes packages to satisfy build dependencies  /*{{{*/
 // ---------------------------------------------------------------------
 /* This function will look at the build depends list of the given source 
@@ -943,6 +615,39 @@ static std::vector<pkgSrcRecords::Parser::BuildDepRec> GetBuildDeps(pkgSrcRecord
 
    return BuildDeps;
 }
+static void WriteBuildDependencyPackage(std::ostringstream &buildDepsPkgFile,
+      std::string const &PkgName, std::string const &Arch,
+      std::vector<pkgSrcRecords::Parser::BuildDepRec> const &Dependencies)
+{
+   buildDepsPkgFile << "Package: " << PkgName << "\n"
+      << "Architecture: " << Arch << "\n"
+      << "Version: 1\n";
+
+   std::string depends, conflicts;
+   for (auto const &dep: Dependencies)
+   {
+      std::string * type;
+      if (dep.Type == pkgSrcRecords::Parser::BuildConflict || dep.Type == pkgSrcRecords::Parser::BuildConflictIndep)
+	 type = &conflicts;
+      else
+	 type = &depends;
+
+      type->append(" ").append(dep.Package);
+      if (dep.Version.empty() ==  false)
+	 type->append(" (").append(pkgCache::CompTypeDeb(dep.Op)).append(" ").append(dep.Version).append(")");
+      if ((dep.Op & pkgCache::Dep::Or) == pkgCache::Dep::Or)
+      {
+	 type->append("\n  |");
+      }
+      else
+	 type->append(",\n");
+   }
+   if (depends.empty() == false)
+      buildDepsPkgFile << "Depends:\n" << depends;
+   if (conflicts.empty() == false)
+      buildDepsPkgFile << "Conflicts:\n" << conflicts;
+   buildDepsPkgFile << "\n";
+}
 bool DoBuildDep(CommandLine &CmdL)
 {
    CacheFile Cache;
@@ -951,11 +656,6 @@ bool DoBuildDep(CommandLine &CmdL)
 
    _config->Set("APT::Install-Recommends", false);
 
-   bool WantLock = _config->FindB("APT::Get::Print-URIs", false) == false;
-
-   if (Cache.Open(WantLock) == false)
-      return false;
-
    if (CmdL.FileSize() <= 1 && VolatileCmdL.empty())
       return _error->Error(_("Must specify at least one package to check builddeps for"));
 
@@ -971,10 +671,11 @@ bool DoBuildDep(CommandLine &CmdL)
    else
       StripMultiArch = true;
 
+   std::ostringstream buildDepsPkgFile;
+   std::vector<std::pair<std::string,std::string>> pseudoPkgs;
    // deal with the build essentials first
    {
       std::vector<pkgSrcRecords::Parser::BuildDepRec> BuildDeps;
-
       Configuration::Item const *Opts = _config->Tree("APT::Build-Essential");
       if (Opts)
 	 Opts = Opts->Child;
@@ -989,15 +690,17 @@ bool DoBuildDep(CommandLine &CmdL)
 	 rec.Op = 0;
 	 BuildDeps.push_back(rec);
       }
-
-      if (InstallBuildDepsLoop(Cache, "APT::Build-Essential", BuildDeps, StripMultiArch, hostArch) == false)
-	 return false;
+      std::string const pseudo = "builddeps:essentials";
+      std::string const nativeArch = _config->Find("APT::Architecture");
+      WriteBuildDependencyPackage(buildDepsPkgFile, pseudo, nativeArch, BuildDeps);
+      pseudoPkgs.emplace_back(pseudo, nativeArch);
    }
 
    // Read the source list
    if (Cache.BuildSourceList() == false)
       return false;
    pkgSourceList *List = Cache.GetSourceList();
+   std::string const pseudoArch = hostArch.empty() ? _config->Find("APT::Architecture") : hostArch;
 
    // FIXME: Avoid volatile sources == cmdline assumption
    {
@@ -1015,13 +718,16 @@ bool DoBuildDep(CommandLine &CmdL)
 	    if (Last == nullptr)
 	       return _error->Error(_("Unable to find a source package for %s"), Src);
 
-	    auto const BuildDeps = GetBuildDeps(Last.get(), Src, StripMultiArch, hostArch);
-	    if (InstallBuildDepsLoop(Cache, Src, BuildDeps, StripMultiArch, hostArch) == false)
-	       return false;
+	    std::string const pseudo = std::string("builddeps:") + Src;
+	    WriteBuildDependencyPackage(buildDepsPkgFile, pseudo, pseudoArch,
+		  GetBuildDeps(Last.get(), Src, StripMultiArch, hostArch));
+	    pseudoPkgs.emplace_back(pseudo, pseudoArch);
 	 }
       }
       else
-	 _error->Error("Implementation error: Volatile sources (%lu) and commandline elements (%lu) do not match!", VolatileSources.size(), VolatileCmdL.size());
+	 return _error->Error("Implementation error: Volatile sources (%lu) and"
+	       "commandline elements (%lu) do not match!", VolatileSources.size(),
+	       VolatileCmdL.size());
    }
 
    if (CmdL.FileList[1] != 0)
@@ -1037,12 +743,51 @@ bool DoBuildDep(CommandLine &CmdL)
 	 if (Last == nullptr)
 	    return _error->Error(_("Unable to find a source package for %s"), *I);
 
-	 auto const BuildDeps = GetBuildDeps(Last, Src.c_str(), StripMultiArch, hostArch);
-	 if (InstallBuildDepsLoop(Cache, Src, BuildDeps, StripMultiArch, hostArch) == false)
-	    return false;
+	 std::string const pseudo = std::string("builddeps:") + Src;
+	 WriteBuildDependencyPackage(buildDepsPkgFile, pseudo, pseudoArch,
+	       GetBuildDeps(Last, Src.c_str(), StripMultiArch, hostArch));
+	 pseudoPkgs.emplace_back(pseudo, pseudoArch);
       }
    }
 
+   Cache.AddIndexFile(new debStringPackageIndex(buildDepsPkgFile.str()));
+
+   bool WantLock = _config->FindB("APT::Get::Print-URIs", false) == false;
+   if (Cache.Open(WantLock) == false)
+      return false;
+   pkgProblemResolver Fix(Cache.GetDepCache());
+
+   APT::PackageVector removeAgain;
+   {
+      pkgDepCache::ActionGroup group(Cache);
+      TryToInstall InstallAction(Cache, &Fix, false);
+      for (auto const &pkg: pseudoPkgs)
+      {
+	 pkgCache::PkgIterator const Pkg = Cache->FindPkg(pkg.first, pkg.second);
+	 if (Pkg.end())
+	    continue;
+	 Cache->SetCandidateVersion(Pkg.VersionList());
+	 InstallAction(Cache[Pkg].CandidateVerIter(Cache));
+	 removeAgain.push_back(Pkg);
+      }
+      InstallAction.doAutoInstall();
+
+      OpTextProgress Progress(*_config);
+      bool const resolver_fail = Fix.Resolve(true, &Progress);
+      if (resolver_fail == false && Cache->BrokenCount() == 0)
+	 return false;
+      if (CheckNothingBroken(Cache) == false)
+	 return false;
+   }
+   if (DoAutomaticRemove(Cache) == false)
+      return false;
+   {
+      pkgDepCache::ActionGroup group(Cache);
+      for (auto const &pkg: removeAgain)
+	 Cache->MarkDelete(pkg, false, 0, true);
+   }
+
+   pseudoPkgs.clear();
    if (_error->PendingError() || InstallPackages(Cache, false, true) == false)
       return _error->Error(_("Failed to process build dependencies"));
    return true;
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*