implement dpkgs vision of interpreting pkg:<arch> dependencies

How the Multi-Arch field and pkg:<arch> dependencies interact was
discussed at DebConf15 in the "MultiArch BoF". dpkg and apt (among other
tools like dose) had a different interpretation in certain scenarios
which we resolved by agreeing on dpkg view – and this commit realizes
this agreement in code.

As was the case so far libapt sticks to the idea of trying to hide
MultiArch as much as possible from individual frontends and instead
translates it to good old SingleArch. There are certainly situations
which can be improved in frontends if they know that MultiArch is upon
them, but these are improvements – not necessary changes needed
to unbreak a frontend.

The implementation idea is simple: If we parse a dependency on foo:amd64
the dependency is formed on a package 'foo:amd64' of arch 'any'. This
package is provided by package 'foo' of arch 'amd64', but not by 'foo'
of arch 'i386'. Both of those foo packages provide each other through
(assuming foo is M-A:foreign) to allow a dependency on 'foo' to be
satisfied by either foo of amd64 or i386. Packages can also declare to
provide 'foo:amd64' which is translated to providing 'foo:amd64:any' as
well.

This indirection over provides was chosen as the alternative would be to
teach dependency resolvers how to deal with architecture specific
dependencies – which violates the design idea of avoiding resolver
changes, especially as architecture-specific dependencies are a
cornercase with quite a few subtil rules. Handling it all over versioned
provides as we already did for M-A in general seems much simpler as it
just works for them.

This switch to :any has actually a "surprising" benefit as well: Even
frontends showing a package name via .Name() [which doesn't show the
architecture] will display the "architecture" for dependencies in which
it was explicitely requested, while we will not show the 'strange' :any
arch in FullName(true) [= pretty-print] either. Before you had to
specialcase these and by default you wouldn't get these details shown.

The only identifiable disadvantage is that this complicates error
reporting and handling. apt-get's ShowBroken has existing problems with
virtual packages [it just shows the name without any reason], so that
has to be worked on eventually. The other case is that detecting if a
package is completely unknown or if it was at least referenced somewhere
needs to acount for this "split" – not that it makes a practical
difference which error is shown… but its one of the improvements
possible.

17 files changed, 295 insertions, 78 deletions

diff --git a/apt-pkg/cacheset.cc b/apt-pkg/cacheset.cc
index 6b31a4fff..5e60ef54a 100644
--- a/apt-pkg/cacheset.cc
+++ b/apt-pkg/cacheset.cc
@@ -265,6 +265,7 @@ bool CacheSetHelper::PackageFromPackageName(PackageContainerInterface * const pc
 	if (unlikely(Cache.GetPkgCache() == 0))
 		return false;
 
+	std::string const pkgstring = pkg;
 	size_t const archfound = pkg.find_last_of(':');
 	std::string arch;
 	if (archfound != std::string::npos) {
@@ -301,7 +302,7 @@ bool CacheSetHelper::PackageFromPackageName(PackageContainerInterface * const pc
 		}
 	}
 
-	pkgCache::PkgIterator Pkg = canNotFindPkgName(Cache, pkg);
+	pkgCache::PkgIterator Pkg = canNotFindPkgName(Cache, pkgstring);
 	if (Pkg.end() == true)
 	   return false;
 
diff --git a/apt-pkg/deb/deblistparser.cc b/apt-pkg/deb/deblistparser.cc
index 602e96e26..b51ee815e 100644
--- a/apt-pkg/deb/deblistparser.cc
+++ b/apt-pkg/deb/deblistparser.cc
@@ -803,13 +803,12 @@ bool debListParser::ParseDepends(pkgCache::VerIterator &Ver,
       }
       else
       {
-	 string Arch = Package.substr(found+1, string::npos);
-	 Package = Package.substr(0, found);
 	 // Such dependencies are not supposed to be accepted …
 	 // … but this is probably the best thing to do anyway
-	 if (Arch == "native")
-	    Arch = _config->Find("APT::Architecture");
-	 if (NewDepends(Ver,Package,Arch,Version,Op | pkgCache::Dep::ArchSpecific,Type) == false)
+	 if (Package.substr(found + 1) == "native")
+	    Package = Package.substr(0, found) + ':' + Ver.Cache()->NativeArch();
+
+	 if (NewDepends(Ver, Package, "any", Version, Op | pkgCache::Dep::ArchSpecific, Type) == false)
 	    return false;
       }
 
@@ -824,6 +823,22 @@ bool debListParser::ParseDepends(pkgCache::VerIterator &Ver,
 /* */
 bool debListParser::ParseProvides(pkgCache::VerIterator &Ver)
 {
+   /* it is unlikely, but while parsing dependencies, we might have already
+      picked up multi-arch implicit provides which we do not want to duplicate here */
+   bool hasProvidesAlready = false;
+   std::string const spzName = Ver.ParentPkg().FullName(false);
+   {
+      for (pkgCache::PrvIterator Prv = Ver.ProvidesList(); Prv.end() == false; ++Prv)
+      {
+	 if (Prv.IsMultiArchImplicit() == false || (Prv->Flags & pkgCache::Flag::ArchSpecific) == 0)
+	    continue;
+	 if (spzName != Prv.OwnerPkg().FullName(false))
+	    continue;
+	 hasProvidesAlready = true;
+	 break;
+      }
+   }
+
    string const Arch = Ver.Arch();
    const char *Start;
    const char *Stop;
@@ -833,31 +848,47 @@ bool debListParser::ParseProvides(pkgCache::VerIterator &Ver)
       string Version;
       unsigned int Op;
 
-      while (1)
+      do
       {
-	 Start = ParseDepends(Start,Stop,Package,Version,Op);
+	 Start = ParseDepends(Start,Stop,Package,Version,Op, false, false, false);
 	 const size_t archfound = Package.rfind(':');
 	 if (Start == 0)
 	    return _error->Error("Problem parsing Provides line");
 	 if (Op != pkgCache::Dep::NoOp && Op != pkgCache::Dep::Equals) {
 	    _error->Warning("Ignoring Provides line with non-equal DepCompareOp for package %s", Package.c_str());
 	 } else if (archfound != string::npos) {
-	    string OtherArch = Package.substr(archfound+1, string::npos);
-	    Package = Package.substr(0, archfound);
-	    if (NewProvides(Ver, Package, OtherArch, Version, pkgCache::Flag::ArchSpecific) == false)
+	    std::string spzArch = Package.substr(archfound + 1);
+	    if (spzArch != "any")
+	    {
+	       if (NewProvides(Ver, Package.substr(0, archfound), spzArch, Version, pkgCache::Flag::MultiArchImplicit | pkgCache::Flag::ArchSpecific) == false)
+		  return false;
+	    }
+	    if (NewProvides(Ver, Package, "any", Version, pkgCache::Flag::ArchSpecific) == false)
 	       return false;
 	 } else if ((Ver->MultiArch & pkgCache::Version::Foreign) == pkgCache::Version::Foreign) {
 	    if (APT::Configuration::checkArchitecture(Arch))
 	       if (NewProvidesAllArch(Ver, Package, Version, 0) == false)
 		  return false;
 	 } else {
+	    if ((Ver->MultiArch & pkgCache::Version::Allowed) == pkgCache::Version::Allowed)
+	    {
+	       if (NewProvides(Ver, Package + ":any", "any", Version, pkgCache::Flag::MultiArchImplicit) == false)
+		  return false;
+	    }
 	    if (NewProvides(Ver, Package, Arch, Version, 0) == false)
 	       return false;
 	 }
-
-	 if (Start == Stop)
-	    break;
-      }
+	 if (archfound == std::string::npos)
+	 {
+	    std::string const spzName = Package + ':' + Ver.ParentPkg().Arch();
+	    pkgCache::PkgIterator const spzPkg = Ver.Cache()->FindPkg(spzName, "any");
+	    if (spzPkg.end() == false)
+	    {
+	       if (NewProvides(Ver, spzName, "any", Version, pkgCache::Flag::MultiArchImplicit | pkgCache::Flag::ArchSpecific) == false)
+		  return false;
+	    }
+	 }
+      } while (Start != Stop);
    }
 
    if (APT::Configuration::checkArchitecture(Arch))
@@ -865,12 +896,25 @@ bool debListParser::ParseProvides(pkgCache::VerIterator &Ver)
       if ((Ver->MultiArch & pkgCache::Version::Allowed) == pkgCache::Version::Allowed)
       {
 	 string const Package = string(Ver.ParentPkg().Name()).append(":").append("any");
-	 return NewProvides(Ver, Package, "any", Ver.VerStr(), pkgCache::Flag::MultiArchImplicit);
+	 if (NewProvides(Ver, Package, "any", Ver.VerStr(), pkgCache::Flag::MultiArchImplicit) == false)
+	    return false;
       }
       else if ((Ver->MultiArch & pkgCache::Version::Foreign) == pkgCache::Version::Foreign)
-	 return NewProvidesAllArch(Ver, Ver.ParentPkg().Name(), Ver.VerStr(), pkgCache::Flag::MultiArchImplicit);
+      {
+	 if (NewProvidesAllArch(Ver, Ver.ParentPkg().Name(), Ver.VerStr(), pkgCache::Flag::MultiArchImplicit) == false)
+	    return false;
+      }
    }
 
+   if (hasProvidesAlready == false)
+   {
+      pkgCache::PkgIterator const spzPkg = Ver.Cache()->FindPkg(spzName, "any");
+      if (spzPkg.end() == false)
+      {
+	 if (NewProvides(Ver, spzName, "any", Ver.VerStr(), pkgCache::Flag::MultiArchImplicit | pkgCache::Flag::ArchSpecific) == false)
+	    return false;
+      }
+   }
    return true;
 }
 									/*}}}*/
diff --git a/apt-pkg/edsp.cc b/apt-pkg/edsp.cc
index aea6f3a5d..db38f588f 100644
--- a/apt-pkg/edsp.cc
+++ b/apt-pkg/edsp.cc
@@ -100,7 +100,7 @@ static void WriteScenarioDependency( FILE* output, pkgCache::VerIterator const &
 	 continue;
       if (orGroup == false)
 	 dependencies[Dep->Type].append(", ");
-      dependencies[Dep->Type].append(Dep.TargetPkg().FullName((Dep->CompareOp & pkgCache::Dep::ArchSpecific) != pkgCache::Dep::ArchSpecific));
+      dependencies[Dep->Type].append(Dep.TargetPkg().Name());
       if (Dep->Version != 0)
 	 dependencies[Dep->Type].append(" (").append(pkgCache::CompTypeDeb(Dep->CompareOp)).append(" ").append(Dep.TargetVer()).append(")");
       if ((Dep->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or)
@@ -150,7 +150,7 @@ static void WriteScenarioLimitedDependency(FILE* output,
 	 orGroup = false;
 	 continue;
       }
-      dependencies[Dep->Type].append(Dep.TargetPkg().FullName((Dep->CompareOp & pkgCache::Dep::ArchSpecific) != pkgCache::Dep::ArchSpecific));
+      dependencies[Dep->Type].append(Dep.TargetPkg().Name());
       if (Dep->Version != 0)
 	 dependencies[Dep->Type].append(" (").append(pkgCache::CompTypeDeb(Dep->CompareOp)).append(" ").append(Dep.TargetVer()).append(")");
       if ((Dep->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or)
diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc
index 739074910..11b9b1377 100644
--- a/apt-pkg/pkgcache.cc
+++ b/apt-pkg/pkgcache.cc
@@ -57,7 +57,7 @@ pkgCache::Header::Header()
    /* Whenever the structures change the major version should be bumped,
       whenever the generator changes the minor version should be bumped. */
    APT_HEADER_SET(MajorVersion, 10);
-   APT_HEADER_SET(MinorVersion, 0);
+   APT_HEADER_SET(MinorVersion, 1);
    APT_HEADER_SET(Dirty, false);
 
    APT_HEADER_SET(HeaderSz, sizeof(pkgCache::Header));
diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc
index 802af172c..10d3fcf21 100644
--- a/apt-pkg/pkgcachegen.cc
+++ b/apt-pkg/pkgcachegen.cc
@@ -629,6 +629,37 @@ bool pkgCacheGenerator::NewPackage(pkgCache::PkgIterator &Pkg,const string &Name
       LastPkg->NextPackage = Package;
    }
    Grp->LastPackage = Package;
+
+   // lazy-create foo (of amd64) provides foo:amd64 at the time we first need it
+   if (Arch == "any")
+   {
+      size_t const found = Name.find(':');
+      std::string const NameA = Name.substr(0, found);
+      std::string const ArchA = Name.substr(found + 1);
+      pkgCache::PkgIterator PkgA = Cache.FindPkg(NameA, ArchA);
+      if (PkgA.end() == false)
+      {
+	 Dynamic<pkgCache::PkgIterator> DynPkgA(PkgA);
+	 pkgCache::PrvIterator Prv = PkgA.ProvidesList();
+	 for (; Prv.end() == false; ++Prv)
+	 {
+	    if (Prv.IsMultiArchImplicit())
+	       continue;
+	    pkgCache::VerIterator V = Prv.OwnerVer();
+	    if (ArchA != V.ParentPkg().Arch())
+	       continue;
+	    if (NewProvides(V, Pkg, V->VerStr, pkgCache::Flag::MultiArchImplicit | pkgCache::Flag::ArchSpecific) == false)
+	       return false;
+	 }
+	 pkgCache::VerIterator V = PkgA.VersionList();
+	 Dynamic<pkgCache::VerIterator> DynV(V);
+	 for (; V.end() == false; ++V)
+	 {
+	    if (NewProvides(V, Pkg, V->VerStr, pkgCache::Flag::MultiArchImplicit | pkgCache::Flag::ArchSpecific) == false)
+	       return false;
+	 }
+      }
+   }
    return true;
 }
 									/*}}}*/
diff --git a/apt-private/private-cacheset.cc b/apt-private/private-cacheset.cc
index 8db736507..439b844d5 100644
--- a/apt-private/private-cacheset.cc
+++ b/apt-private/private-cacheset.cc
@@ -4,6 +4,7 @@
 #include <apt-pkg/pkgcache.h>
 #include <apt-pkg/depcache.h>
 #include <apt-pkg/cacheiterators.h>
+#include <apt-pkg/cachefilter.h>
 #include <apt-pkg/aptconfiguration.h>
 #include <apt-pkg/configuration.h>
 #include <apt-pkg/progress.h>
@@ -111,6 +112,67 @@ void CacheSetHelperVirtuals::canNotFindVersion(
       virtualPkgs.insert(Pkg);
    return CacheSetHelper::canNotFindVersion(select, vci, Cache, Pkg);
 }
+static pkgCache::PkgIterator canNotFindPkgName_impl(pkgCacheFile &Cache, std::string const &str)
+{
+   std::string pkg = str;
+   size_t const archfound = pkg.find_last_of(':');
+   std::string arch;
+   if (archfound != std::string::npos) {
+      arch = pkg.substr(archfound+1);
+      pkg.erase(archfound);
+      if (arch == "all" || arch == "native")
+	 arch = _config->Find("APT::Architecture");
+   }
+
+   // If we don't find 'foo:amd64' look for 'foo:amd64:any'.
+   // Note: we prepare for an error here as if foo:amd64 does not exist,
+   // but foo:amd64:any it means that this package is only referenced in a
+   // (architecture specific) dependency. We do not add to virtualPkgs directly
+   // as we can't decide from here which error message has to be printed.
+   // FIXME: This doesn't match 'barbarian' architectures
+   pkgCache::PkgIterator Pkg(Cache, 0);
+   std::vector<std::string> const archs = APT::Configuration::getArchitectures();
+   if (archfound == std::string::npos)
+   {
+      for (auto const &a : archs)
+      {
+	 Pkg = Cache.GetPkgCache()->FindPkg(pkg + ':' + a, "any");
+	 if (Pkg.end() == false && Pkg->ProvidesList != 0)
+	    break;
+      }
+      if (Pkg.end() == true)
+	 for (auto const &a : archs)
+	 {
+	    Pkg = Cache.GetPkgCache()->FindPkg(pkg + ':' + a, "any");
+	    if (Pkg.end() == false)
+	       break;
+	 }
+   }
+   else
+   {
+      Pkg = Cache.GetPkgCache()->FindPkg(pkg + ':' + arch, "any");
+      if (Pkg.end() == true)
+      {
+	 APT::CacheFilter::PackageArchitectureMatchesSpecification pams(arch);
+	 for (auto const &a : archs)
+	 {
+	    if (pams(a.c_str()) == false)
+	       continue;
+	    Pkg = Cache.GetPkgCache()->FindPkg(pkg + ':' + a, "any");
+	    if (Pkg.end() == false)
+	       break;
+	 }
+      }
+   }
+   return Pkg;
+}
+pkgCache::PkgIterator CacheSetHelperVirtuals::canNotFindPkgName(pkgCacheFile &Cache, std::string const &str)
+{
+   pkgCache::PkgIterator const Pkg = canNotFindPkgName_impl(Cache, str);
+   if (Pkg.end())
+      return APT::CacheSetHelper::canNotFindPkgName(Cache, str);
+   return Pkg;
+}
 CacheSetHelperVirtuals::CacheSetHelperVirtuals(bool const ShowErrors, GlobalError::MsgType const &ErrorType) :
    CacheSetHelper{ShowErrors, ErrorType}
 {}
@@ -292,4 +354,11 @@ APT::VersionSet CacheSetHelperAPTGet::tryVirtualPackage(pkgCacheFile &Cache, pkg
    }
    return APT::VersionSet();
 }
+pkgCache::PkgIterator CacheSetHelperAPTGet::canNotFindPkgName(pkgCacheFile &Cache, std::string const &str)
+{
+   pkgCache::PkgIterator const Pkg = canNotFindPkgName_impl(Cache, str);
+   if (Pkg.end())
+      return APT::CacheSetHelper::canNotFindPkgName(Cache, str);
+   return Pkg;
+}
 									/*}}}*/
diff --git a/apt-private/private-cacheset.h b/apt-private/private-cacheset.h
index 892993e58..2b452ab7d 100644
--- a/apt-private/private-cacheset.h
+++ b/apt-private/private-cacheset.h
@@ -71,6 +71,7 @@ public:
 
    virtual pkgCache::VerIterator canNotGetVersion(enum CacheSetHelper::VerSelector const select, pkgCacheFile &Cache, pkgCache::PkgIterator const &Pkg) APT_OVERRIDE;
    virtual void canNotFindVersion(enum CacheSetHelper::VerSelector const select, APT::VersionContainerInterface * vci, pkgCacheFile &Cache, pkgCache::PkgIterator const &Pkg) APT_OVERRIDE;
+   virtual pkgCache::PkgIterator canNotFindPkgName(pkgCacheFile &Cache, std::string const &str) APT_OVERRIDE;
 
    CacheSetHelperVirtuals(bool const ShowErrors = true, GlobalError::MsgType const &ErrorType = GlobalError::NOTICE);
 };
@@ -99,6 +100,7 @@ public:
 
 	virtual pkgCache::VerIterator canNotFindCandidateVer(pkgCacheFile &Cache, pkgCache::PkgIterator const &Pkg) APT_OVERRIDE;
 	virtual pkgCache::VerIterator canNotFindNewestVer(pkgCacheFile &Cache, pkgCache::PkgIterator const &Pkg) APT_OVERRIDE;
+	virtual pkgCache::PkgIterator canNotFindPkgName(pkgCacheFile &Cache, std::string const &str) APT_OVERRIDE;
 
 	APT::VersionSet tryVirtualPackage(pkgCacheFile &Cache, pkgCache::PkgIterator const &Pkg,
 						CacheSetHelper::VerSelector const select);
diff --git a/cmdline/apt-cache.cc b/cmdline/apt-cache.cc
index 050508663..1493b63dc 100644
--- a/cmdline/apt-cache.cc
+++ b/cmdline/apt-cache.cc
@@ -724,7 +724,6 @@ static bool ShowDepends(CommandLine &CmdL, bool const RevDepends)
 	       continue;
 
 	    pkgCache::PkgIterator Trg = RevDepends ? D.ParentPkg() : D.TargetPkg();
-	    bool const showNoArch = RevDepends || (D->CompareOp & pkgCache::Dep::ArchSpecific) != pkgCache::Dep::ArchSpecific;
 
 	    if((Installed && Trg->CurrentVer != 0) || !Installed)
 	      {
@@ -738,9 +737,9 @@ static bool ShowDepends(CommandLine &CmdL, bool const RevDepends)
 		if (ShowDepType == true)
 		  cout << D.DepType() << ": ";
 		if (Trg->VersionList == 0)
-		  cout << "<" << Trg.FullName(showNoArch) << ">";
+		  cout << "<" << Trg.FullName(true) << ">";
 		else
-		  cout << Trg.FullName(showNoArch);
+		  cout << Trg.FullName(true);
 		if (ShowVersion == true && D->Version != 0)
 		   cout << " (" << pkgCache::CompTypeDeb(D->CompareOp) << ' ' << D.TargetVer() << ')';
 		cout << std::endl;
diff --git a/test/integration/test-apt-cache b/test/integration/test-apt-cache
index 97d180a74..7927686fc 100755
--- a/test/integration/test-apt-cache
+++ b/test/integration/test-apt-cache
@@ -120,12 +120,9 @@ bar
   Depends: bar
   Breaks: foo
   Replaces: foo
-  Breaks: <foo:i386>
-  Replaces: <foo:i386>
 <foobar>
 <cool>
-<cooler>
-<foo:i386>' aptcache depends foo --recurse --implicit
+<cooler>' aptcache depends foo --recurse --implicit
 testsuccessequal 'foo
   Depends: bar
 bar
@@ -135,9 +132,7 @@ testsuccessequal 'foo
   Depends: bar
 bar
   Depends: bar
-  Replaces: foo
-  Replaces: <foo:i386>
-<foo:i386>' aptcache depends foo --recurse --important --replaces --implicit
+  Replaces: foo' aptcache depends foo --recurse --important --replaces --implicit
 testsuccessequal 'bar
   Depends: bar
   Breaks: foo
@@ -145,38 +140,37 @@ testsuccessequal 'bar
 testsuccessequal 'bar
   Depends: bar
   Breaks: foo
-  Replaces: foo
-  Breaks: <foo:i386>
-  Replaces: <foo:i386>' aptcache depends bar --implicit
+  Replaces: foo' aptcache depends bar --implicit
+
 testsuccessequal 'specific
   Depends: <bar:i386>
-  Depends: specific:amd64
-  Breaks: foo:amd64
+  Depends: <specific:amd64>
+    specific
+  Breaks: <foo:amd64>
   Replaces: <foo:i386>' aptcache depends specific
 testsuccessequal 'specific
   Depends: <bar:i386>
-  Depends: specific:amd64
-  Breaks: foo:amd64
+  Depends: <specific:amd64>
+    specific
+  Breaks: <foo:amd64>
   Replaces: <foo:i386>' aptcache depends specific --implicit
 
-## rdpends
+## rdepends
 
+# Note that specific does not appear in this list as it doesn't depend on foo,
+# but on an arch-specific foo!
 testsuccessequal 'foo
 Reverse Depends:
   bar
-  specific
   bar' aptcache rdepends foo
 testsuccessequal 'foo
 Reverse Depends:
   Breaks: bar
-  Breaks: specific
   Replaces: bar' aptcache rdepends foo -o APT::Cache::ShowDependencyType=1
 testsuccessequal 'foo
 Reverse Depends:
   Breaks: bar (<< 1)
-  Breaks: specific (<< 1)
   Replaces: bar (<< 1)' aptcache rdepends foo -o APT::Cache::ShowDependencyType=1 -o APT::Cache::ShowVersion=1
 testsuccessequal 'foo
 Reverse Depends:
-  Breaks: bar (<< 1)
-  Breaks: specific (<< 1)' aptcache rdepends foo -o APT::Cache::ShowDependencyType=1 -o APT::Cache::ShowVersion=1 --important --breaks
+  Breaks: bar (<< 1)' aptcache rdepends foo -o APT::Cache::ShowDependencyType=1 -o APT::Cache::ShowVersion=1 --important --breaks
diff --git a/test/integration/test-apt-get-install-virtual-pkgs b/test/integration/test-apt-get-install-virtual-pkgs
new file mode 100755
index 000000000..ca3790f46
--- /dev/null
+++ b/test/integration/test-apt-get-install-virtual-pkgs
@@ -0,0 +1,64 @@
+#!/bin/sh
+set -e
+
+TESTDIR=$(readlink -f $(dirname $0))
+. $TESTDIR/framework
+setupenvironment
+configarchitecture 'amd64' 'i386'
+
+insertpackage 'unstable' 'foo' 'amd64' '1' 'Provides: foo-prv'
+
+insertpackage 'unstable' 'baz1' 'amd64' '1' 'Provides: foo-prv1'
+insertpackage 'unstable' 'foo1' 'amd64' '1' 'Provides: foo-prv1'
+
+insertpackage 'unstable' 'baz2' 'amd64' '1' 'Provides: foo-prv2'
+insertpackage 'unstable' 'foo2' 'amd64' '2' 'Provides: foo-prv2:amd64'
+
+insertpackage 'unstable' 'baz3' 'amd64' '1' 'Provides: foo-prv3'
+insertpackage 'unstable' 'foo3' 'i386' '2' 'Provides: foo-prv3:amd64'
+
+insertpackage 'unstable' 'baz4' 'amd64' '1' 'Provides: foo-prv4:amd64'
+insertpackage 'unstable' 'foo4' 'i386' '2' 'Provides: foo-prv4:amd64'
+
+insertpackage 'experimental' 'baz5' 'amd64' '1' 'Provides: foo-prv5:amd64'
+insertpackage 'experimental' 'foo5' 'i386' '2' 'Provides: foo-prv5:amd64'
+
+setupaptarchive
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+Note, selecting 'foo' instead of 'foo-prv'
+The following NEW packages will be installed:
+  foo
+0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
+Inst foo (1 unstable [amd64])
+Conf foo (1 unstable [amd64])" aptget install foo-prv -s -q=0
+
+testvirtuals() {
+	testfailureequal "Reading package lists...
+Building dependency tree...
+Package $1 is a virtual package provided by:
+  $3
+  $2
+You should explicitly select one to install.
+
+E: Package '$1' has no installation candidate" aptget install $1 -s -q=0
+}
+
+testvirtuals 'foo-prv1' 'baz1 1' 'foo1 1'
+testvirtuals 'foo-prv2' 'baz2 1' 'foo2 2'
+testvirtuals 'foo-prv3' 'baz3 1' 'foo3:i386 2'
+testvirtuals 'foo-prv4' 'baz4 1' 'foo4:i386 2'
+testvirtuals 'foo-prv5' 'baz5 1' 'foo5:i386 2'
+
+echo 'Package: *
+Pin: release a=experimental
+Pin-Priority: -1' > rootdir/etc/apt/preferences.d/experimental.pref
+
+testfailureequal "Reading package lists...
+Building dependency tree...
+Package foo-prv5 is a virtual package provided by:
+  foo5:i386 2 [Not candidate version]
+  baz5 1 [Not candidate version]
+
+E: Package 'foo-prv5' has no installation candidate" aptget install foo-prv5 -s -q=0
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 13a0ef0c8..4a7c516d4 100755
--- a/test/integration/test-bug-683786-build-dep-on-virtual-packages
+++ b/test/integration/test-bug-683786-build-dep-on-virtual-packages
@@ -31,7 +31,7 @@ Reverse Depends:
 Dependencies: 
 Provides: 
 Reverse Provides: ' aptcache showpkg po-debconf:armel
-testsuccessequal 'N: Unable to locate package texi2html' aptcache showpkg texi2html:armel -q=0
+testsuccessequal 'N: Unable to locate package texi2html:armel' aptcache showpkg texi2html:armel -q=0
 
 testsuccessequal 'Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-758153-versioned-provides-support b/test/integration/test-bug-758153-versioned-provides-support
index 6d43d9943..0be7ced8c 100755
--- a/test/integration/test-bug-758153-versioned-provides-support
+++ b/test/integration/test-bug-758153-versioned-provides-support
@@ -214,7 +214,7 @@ or been moved out of Incoming.
 The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
- baz-broken:i386 : Depends: bar but it is not installable
+ baz-broken:i386 : Depends: bar:amd64 but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget install baz-broken -s
 
 testsuccessequal 'Reading package lists...
diff --git a/test/integration/test-cachecontainer-architecture-specification b/test/integration/test-cachecontainer-architecture-specification
index e5625e811..617379a79 100755
--- a/test/integration/test-cachecontainer-architecture-specification
+++ b/test/integration/test-cachecontainer-architecture-specification
@@ -28,7 +28,7 @@ Inst libsame:armel (1 unstable [armel])
 Conf libsame:armel (1 unstable [armel])' aptget -s install libsame:armel
 testfailureequal 'Reading package lists...
 Building dependency tree...
-E: Unable to locate package libsame' aptget -s install libsame:armhf
+E: Unable to locate package libsame:armhf' aptget -s install libsame:armhf
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
@@ -88,11 +88,11 @@ Conf libsame (1 unstable [amd64])
 Conf libsame:armel (1 unstable [armel])' aptget -s install libsame:linux-*
 testfailureequal 'Reading package lists...
 Building dependency tree...
-E: Unable to locate package libsame' aptget -s install libsame:windows-any
+E: Unable to locate package libsame:windows-any' aptget -s install libsame:windows-any
 
 testfailureequal 'Reading package lists...
 Building dependency tree...
-E: Unable to locate package foo' aptget -s install foo:armel
+E: Unable to locate package foo:armel' aptget -s install foo:armel
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 The following NEW packages will be installed:
diff --git a/test/integration/test-external-dependency-solver-protocol b/test/integration/test-external-dependency-solver-protocol
index 3b9b38c39..15944da9d 100755
--- a/test/integration/test-external-dependency-solver-protocol
+++ b/test/integration/test-external-dependency-solver-protocol
@@ -61,6 +61,8 @@ testsuccess aptget install --solver apt awesomecoolstuff:i386 -s
 rm -f /tmp/dump.edsp
 testfailure aptget install --solver dump awesomecoolstuff:i386 -s
 testsuccess test -s /tmp/dump.edsp
+testequal 'Install: awesomecoolstuff:i386' grep :i386 /tmp/dump.edsp
+testempty grep :amd64 /tmp/dump.edsp
 
 testsuccess aptget dist-upgrade -s
 testsuccess aptget dist-upgrade -s --solver apt
diff --git a/test/integration/test-multiarch-allowed b/test/integration/test-multiarch-allowed
index 5a8b5eb7d..ecdf39a86 100755
--- a/test/integration/test-multiarch-allowed
+++ b/test/integration/test-multiarch-allowed
@@ -12,7 +12,7 @@ insertpackage 'unstable' 'needsfooany' 'amd64,i386' '1' 'Depends: foo:any'
 insertpackage 'unstable' 'needsfoover1' 'amd64,i386' '1' 'Depends: foo:any (>= 1)'
 insertpackage 'unstable' 'needsfoover2' 'amd64,i386' '1' 'Depends: foo:any (>= 2)'
 insertpackage 'unstable' 'hatesfoo' 'amd64' '1' 'Conflicts: foo'
-insertpackage 'unstable' 'hatesfooany' 'amd64' '1' 'Conflicts: foo:any' # this makes no sense…
+insertpackage 'unstable' 'hatesfooany' 'amd64' '1' 'Conflicts: foo:any' # this makes no sense…?
 insertpackage 'unstable' 'hatesfoonative' 'amd64' '1' 'Conflicts: foo:amd64'
 
 insertpackage 'unstable' 'coolfoo' 'amd64' '1' 'Multi-Arch:allowed
@@ -21,10 +21,10 @@ insertpackage 'unstable' 'coolfoover' 'amd64' '1' 'Multi-Arch:allowed
 Provides: coolbar (= 2)'
 insertpackage 'unstable' 'needscoolfoo' 'amd64' '1' 'Depends: coolfoo, coolbar'
 insertpackage 'unstable' 'needscoolfooany' 'amd64' '1' 'Depends: coolfoo:any, coolbar:any'
-insertpackage 'unstable' 'needscoolfoover0' 'amd64' '1' 'Depends: coolfoo:any (>= 1), coolbar'
-insertpackage 'unstable' 'needscoolfoover1' 'amd64' '1' 'Depends: coolfoo:any (>= 1), coolbar (>= 1)'
-insertpackage 'unstable' 'needscoolfoover2' 'amd64' '1' 'Depends: coolfoo:any (>= 2), coolbar (>= 1)'
-insertpackage 'unstable' 'needscoolfoover3' 'amd64' '1' 'Depends: coolfoo:any (>= 2), coolbar (>= 3)'
+insertpackage 'unstable' 'needscoolfoover0' 'amd64' '1' 'Depends: coolfoo:any (>= 1), coolbar:any'
+insertpackage 'unstable' 'needscoolfoover1' 'amd64' '1' 'Depends: coolfoo:any (>= 1), coolbar:any (>= 1)'
+insertpackage 'unstable' 'needscoolfoover2' 'amd64' '1' 'Depends: coolfoo:any (>= 2), coolbar:any (>= 1)'
+insertpackage 'unstable' 'needscoolfoover3' 'amd64' '1' 'Depends: coolfoo:any (>= 2), coolbar:any (>= 3)'
 
 setupaptarchive
 
@@ -142,7 +142,7 @@ E: Unable to correct problems, you have held broken packages." aptget install fo
 	testfailuremsg 'E: Unable to correct problems, you have held broken packages.' aptget install foo hatesfooany -s
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
- hatesfoonative : Conflicts: foo but 1 is to be installed
+ hatesfoonative : Conflicts: foo:amd64
 E: Unable to correct problems, you have held broken packages." aptget install foo hatesfoonative -s
 }
 solveableinsinglearch2
@@ -189,10 +189,17 @@ Inst needscoolfoo (1 unstable [amd64])
 Conf coolfoo (1 unstable [amd64])
 Conf coolfoover (1 unstable [amd64])
 Conf needscoolfoo (1 unstable [amd64])" aptget install needscoolfoo coolfoover -s
-	testfailureequal "$BADPREFIX
-The following packages have unmet dependencies:
- needscoolfooany : Depends: coolbar:any but it is not installable
-E: Unable to correct problems, you have held broken packages." aptget install needscoolfooany -s
+	testsuccessequal "Reading package lists...
+Building dependency tree...
+The following additional packages will be installed:
+  coolfoo
+The following NEW packages will be installed:
+  coolfoo needscoolfooany
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst coolfoo (1 unstable [amd64])
+Inst needscoolfooany (1 unstable [amd64])
+Conf coolfoo (1 unstable [amd64])
+Conf needscoolfooany (1 unstable [amd64])" aptget install needscoolfooany -s
 	testsuccessequal 'Reading package lists...
 Building dependency tree...
 The following additional packages will be installed:
@@ -224,7 +231,7 @@ E: Unable to correct problems, you have held broken packages." aptget install ne
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoover3 : Depends: coolfoo:any (>= 2)
-                    Depends: coolbar (>= 3)
+                    Depends: coolbar:any (>= 3)
 E: Unable to correct problems, you have held broken packages." aptget install needscoolfoover3 -s
 }
 solveableinsinglearch3
@@ -235,7 +242,7 @@ configarchitecture 'amd64'
 solveableinsinglearch0
 testfailureequal 'Reading package lists...
 Building dependency tree...
-E: Unable to locate package needsfoo' aptget install needsfoo:i386 -s
+E: Unable to locate package needsfoo:i386' aptget install needsfoo:i386 -s
 
 solveableinsinglearch1 'needsfooany'
 solveableinsinglearch1 'needsfoover1'
diff --git a/test/integration/test-multiarch-foreign b/test/integration/test-multiarch-foreign
index 854f441fb..8c09a7fde 100755
--- a/test/integration/test-multiarch-foreign
+++ b/test/integration/test-multiarch-foreign
@@ -186,39 +186,43 @@ The following packages have unmet dependencies:
 E: Unable to correct problems, you have held broken packages." aptget install $1 hates-foo -s
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
- hates-foo-x64 : Conflicts: foo
-E: Unable to correct problems, you have held broken packages." aptget install $1 hates-foo-x64 -s
-	testfailureequal "$BADPREFIX
-The following packages have unmet dependencies:
- hates-foo-x32 : Conflicts: foo:i386
-E: Unable to correct problems, you have held broken packages." aptget install $1 hates-foo-x32 -s
+ $2 : Conflicts: foo:$4
+E: Unable to correct problems, you have held broken packages." aptget install $1 $2 -s
+	testsuccessequal "Reading package lists...
+Building dependency tree...
+The following NEW packages will be installed:
+  $1 $3
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst $1 (1.0 unstable [$4])
+Inst $3 (1.0 unstable [amd64])
+Conf $1 (1.0 unstable [$4])
+Conf $3 (1.0 unstable [amd64])" aptget install $1 $3 -s
 }
-hatersgonnahate 'foo'
-hatersgonnahate 'foo:i386'
+hatersgonnahate 'foo' 'hates-foo-x64' 'hates-foo-x32' 'amd64'
+hatersgonnahate 'foo:i386' 'hates-foo-x32' 'hates-foo-x64' 'i386'
 
-#FIXME: do not work in single-arch as i386 isn't known at cache generation time
 	testsuccessequal 'Reading package lists...
 Building dependency tree...
 The following additional packages will be installed:
-  foo
+  foo:i386
 The following NEW packages will be installed:
-  cool-foo-x32 foo
+  cool-foo-x32 foo:i386
 0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
-Inst foo (1.0 unstable [amd64])
+Inst foo:i386 (1.0 unstable [i386])
 Inst cool-foo-x32 (1.0 unstable [amd64])
-Conf foo (1.0 unstable [amd64])
+Conf foo:i386 (1.0 unstable [i386])
 Conf cool-foo-x32 (1.0 unstable [amd64])' aptget install cool-foo-x32 -s
 
 	testsuccessequal 'Reading package lists...
 Building dependency tree...
 The following additional packages will be installed:
-  bar
+  bar:i386
 The following NEW packages will be installed:
-  bar cool-bar-x32
+  bar:i386 cool-bar-x32
 0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
-Inst bar (1.0 unstable [amd64])
+Inst bar:i386 (1.0 unstable [i386])
 Inst cool-bar-x32 (1.0 unstable [amd64])
-Conf bar (1.0 unstable [amd64])
+Conf bar:i386 (1.0 unstable [i386])
 Conf cool-bar-x32 (1.0 unstable [amd64])' aptget install cool-bar-x32 -s -q=0
 
 	testsuccessequal 'Reading package lists...
diff --git a/test/integration/test-specific-architecture-dependencies b/test/integration/test-specific-architecture-dependencies
index f6635a4d6..b5fcdd6ac 100755
--- a/test/integration/test-specific-architecture-dependencies
+++ b/test/integration/test-specific-architecture-dependencies
@@ -279,7 +279,7 @@ Conf depender-x64 (1 unstable [amd64])' aptget install depender-x64 -s
 
 testequal 'Reading package lists...
 Building dependency tree...
-E: Unable to locate package depender-x64' aptget install depender-x64:i386 -s
+E: Unable to locate package depender-x64:i386' aptget install depender-x64:i386 -s
 
 testequal 'Reading package lists...
 Building dependency tree...