show or-groups in not-installed recommends and suggests lists

Further abstracting our new ShowList allows to use it for containers of
strings as well giving us the option to implement an or-groups display
for the recommends and suggests lists which is a nice trick given that
it also helps with migrating the last remaining other cases of old
ShowList.

18 files changed, 420 insertions, 203 deletions

diff --git a/apt-pkg/cachefile.cc b/apt-pkg/cachefile.cc
index 690776266..ed3c2dd0a 100644
--- a/apt-pkg/cachefile.cc
+++ b/apt-pkg/cachefile.cc
@@ -35,10 +35,13 @@
 #include <apti18n.h>
 									/*}}}*/
 // CacheFile::CacheFile - Constructor					/*{{{*/
-// ---------------------------------------------------------------------
-/* */
-pkgCacheFile::pkgCacheFile() : d(NULL), Map(NULL), Cache(NULL), DCache(NULL),
-				SrcList(NULL), Policy(NULL)
+pkgCacheFile::pkgCacheFile() : d(NULL), ExternOwner(false), Map(NULL), Cache(NULL),
+				DCache(NULL), SrcList(NULL), Policy(NULL)
+{
+}
+pkgCacheFile::pkgCacheFile(pkgDepCache * const Owner) : d(NULL), ExternOwner(true),
+   Map(&Owner->GetCache().GetMap()), Cache(&Owner->GetCache()),
+   DCache(Owner), SrcList(NULL), Policy(NULL)
 {
 }
 									/*}}}*/
@@ -47,12 +50,16 @@ pkgCacheFile::pkgCacheFile() : d(NULL), Map(NULL), Cache(NULL), DCache(NULL),
 /* */
 pkgCacheFile::~pkgCacheFile()
 {
-   delete DCache;
+   if (ExternOwner == false)
+   {
+      delete DCache;
+      delete Cache;
+      delete Map;
+   }
    delete Policy;
    delete SrcList;
-   delete Cache;
-   delete Map;
-   _system->UnLock(true);
+   if (ExternOwner == false)
+      _system->UnLock(true);
 }
 									/*}}}*/
 // CacheFile::BuildCaches - Open and build the cache files		/*{{{*/
@@ -229,11 +236,16 @@ void pkgCacheFile::RemoveCaches()
 /* */
 void pkgCacheFile::Close()
 {
-   delete DCache;
+   if (ExternOwner == false)
+   {
+      delete DCache;
+      delete Cache;
+      delete Map;
+   }
+   else
+      ExternOwner = false;
    delete Policy;
-   delete Cache;
    delete SrcList;
-   delete Map;
    _system->UnLock(true);
 
    Map = NULL;
diff --git a/apt-pkg/cachefile.h b/apt-pkg/cachefile.h
index 83dd90d36..f4cadf5e6 100644
--- a/apt-pkg/cachefile.h
+++ b/apt-pkg/cachefile.h
@@ -38,9 +38,9 @@ class pkgCacheFile
 {
    /** \brief dpointer placeholder (for later in case we need it) */
    void * const d;
+   bool ExternOwner;
 
    protected:
-   
    MMap *Map;
    pkgCache *Cache;
    pkgDepCache *DCache;
@@ -50,18 +50,18 @@ class pkgCacheFile
    pkgPolicy *Policy;
 
    // We look pretty much exactly like a pointer to a dep cache
-   inline operator pkgCache &() {return *Cache;};
-   inline operator pkgCache *() {return Cache;};
-   inline operator pkgDepCache &() {return *DCache;};
-   inline operator pkgDepCache *() {return DCache;};
-   inline operator pkgPolicy &() {return *Policy;};
-   inline operator pkgPolicy *() {return Policy;};
-   inline operator pkgSourceList &() {return *SrcList;};
-   inline operator pkgSourceList *() {return SrcList;};
-   inline pkgDepCache *operator ->() {return DCache;};
-   inline pkgDepCache &operator *() {return *DCache;};
-   inline pkgDepCache::StateCache &operator [](pkgCache::PkgIterator const &I) {return (*DCache)[I];};
-   inline unsigned char &operator [](pkgCache::DepIterator const &I) {return (*DCache)[I];};
+   inline operator pkgCache &() const {return *Cache;};
+   inline operator pkgCache *() const {return Cache;};
+   inline operator pkgDepCache &() const {return *DCache;};
+   inline operator pkgDepCache *() const {return DCache;};
+   inline operator pkgPolicy &() const {return *Policy;};
+   inline operator pkgPolicy *() const {return Policy;};
+   inline operator pkgSourceList &() const {return *SrcList;};
+   inline operator pkgSourceList *() const {return SrcList;};
+   inline pkgDepCache *operator ->() const {return DCache;};
+   inline pkgDepCache &operator *() const {return *DCache;};
+   inline pkgDepCache::StateCache &operator [](pkgCache::PkgIterator const &I) const {return (*DCache)[I];};
+   inline unsigned char &operator [](pkgCache::DepIterator const &I) const {return (*DCache)[I];};
 
    bool BuildCaches(OpProgress *Progress = NULL,bool WithLock = true);
    APT_DEPRECATED bool BuildCaches(OpProgress &Progress,bool const &WithLock = true) { return BuildCaches(&Progress, WithLock); };
@@ -85,6 +85,7 @@ class pkgCacheFile
    inline bool IsSrcListBuilt() const { return (SrcList != NULL); };
 
    pkgCacheFile();
+   explicit pkgCacheFile(pkgDepCache * const Owner);
    virtual ~pkgCacheFile();
 };
 
diff --git a/apt-pkg/cacheset.cc b/apt-pkg/cacheset.cc
index a4e330a0a..f5cf52159 100644
--- a/apt-pkg/cacheset.cc
+++ b/apt-pkg/cacheset.cc
@@ -582,6 +582,116 @@ bool VersionContainerInterface::FromPackage(VersionContainerInterface * const vc
 	return found;
 }
 									/*}}}*/
+// FromDependency - versions satisfying a given dependency		/*{{{*/
+bool VersionContainerInterface::FromDependency(VersionContainerInterface * const vci,
+					       pkgCacheFile &Cache,
+					       pkgCache::DepIterator const &D,
+					       CacheSetHelper::VerSelector const selector,
+					       CacheSetHelper &helper)
+{
+	bool found = false;
+	switch(selector) {
+	case CacheSetHelper::ALL:
+	{
+		pkgCache::PkgIterator const T = D.TargetPkg();
+		for (pkgCache::VerIterator Ver = T.VersionList(); Ver.end() == false; ++Ver)
+		{
+		   if (D.IsSatisfied(Ver) == true)
+		   {
+		      vci->insert(Ver);
+		      found = true;
+		   }
+		   for (pkgCache::PrvIterator Prv = T.ProvidesList(); Prv.end() != true; ++Prv)
+		   {
+		      pkgCache::VerIterator const V = Prv.OwnerVer();
+		      if (unlikely(V.end() == true) || D.IsSatisfied(Prv) == false)
+			 continue;
+		      vci->insert(V);
+		      found = true;
+		   }
+		}
+		return found;
+	}
+	case CacheSetHelper::CANDANDINST:
+	{
+		found = FromDependency(vci, Cache, D, CacheSetHelper::CANDIDATE, helper);
+		found &= FromDependency(vci, Cache, D, CacheSetHelper::INSTALLED, helper);
+		return found;
+	}
+	case CacheSetHelper::CANDIDATE:
+	{
+		pkgCache::PkgIterator const T = D.TargetPkg();
+		pkgCache::VerIterator const Cand = Cache[T].CandidateVerIter(Cache);
+		if (Cand.end() == false && D.IsSatisfied(Cand) == true)
+		{
+		   vci->insert(Cand);
+		   found = true;
+		}
+		for (pkgCache::PrvIterator Prv = T.ProvidesList(); Prv.end() != true; ++Prv)
+		{
+		   pkgCache::VerIterator const V = Prv.OwnerVer();
+		   pkgCache::VerIterator const Cand = Cache[Prv.OwnerPkg()].CandidateVerIter(Cache);
+		   if (Cand.end() == true || V != Cand || D.IsSatisfied(Prv) == false)
+		      continue;
+		   vci->insert(Cand);
+		   found = true;
+		}
+		return found;
+	}
+	case CacheSetHelper::INSTALLED:
+	{
+		pkgCache::PkgIterator const T = D.TargetPkg();
+		pkgCache::VerIterator const Cand = T.CurrentVer();
+		if (Cand.end() == false && D.IsSatisfied(Cand) == true)
+		{
+		   vci->insert(Cand);
+		   found = true;
+		}
+		for (pkgCache::PrvIterator Prv = T.ProvidesList(); Prv.end() != true; ++Prv)
+		{
+		   pkgCache::VerIterator const V = Prv.OwnerVer();
+		   pkgCache::VerIterator const Cand = Prv.OwnerPkg().CurrentVer();
+		   if (Cand.end() == true || V != Cand || D.IsSatisfied(Prv) == false)
+		      continue;
+		   vci->insert(Cand);
+		   found = true;
+		}
+		return found;
+	}
+	case CacheSetHelper::CANDINST:
+		return FromDependency(vci, Cache, D, CacheSetHelper::CANDIDATE, helper) ||
+		   FromDependency(vci, Cache, D, CacheSetHelper::INSTALLED, helper);
+	case CacheSetHelper::INSTCAND:
+		return FromDependency(vci, Cache, D, CacheSetHelper::INSTALLED, helper) ||
+		   FromDependency(vci, Cache, D, CacheSetHelper::CANDIDATE, helper);
+	case CacheSetHelper::NEWEST:
+	{
+		pkgCache::PkgIterator const T = D.TargetPkg();
+		pkgCache::VerIterator const Cand = T.VersionList();
+		if (Cand.end() == false && D.IsSatisfied(Cand) == true)
+		{
+		   vci->insert(Cand);
+		   found = true;
+		}
+		for (pkgCache::PrvIterator Prv = T.ProvidesList(); Prv.end() != true; ++Prv)
+		{
+		   pkgCache::VerIterator const V = Prv.OwnerVer();
+		   pkgCache::VerIterator const Cand = Prv.OwnerPkg().VersionList();
+		   if (Cand.end() == true || V != Cand || D.IsSatisfied(Prv) == false)
+		      continue;
+		   vci->insert(Cand);
+		   found = true;
+		}
+		return found;
+	}
+	case CacheSetHelper::RELEASE:
+	case CacheSetHelper::VERSIONNUMBER:
+		// both make no sense here, so always false
+		return false;
+	}
+	return found;
+}
+									/*}}}*/
 // getCandidateVer - Returns the candidate version of the given package	/*{{{*/
 pkgCache::VerIterator VersionContainerInterface::getCandidateVer(pkgCacheFile &Cache,
 		pkgCache::PkgIterator const &Pkg, CacheSetHelper &helper) {
diff --git a/apt-pkg/cacheset.h b/apt-pkg/cacheset.h
index 0b9b9441c..5455fe74b 100644
--- a/apt-pkg/cacheset.h
+++ b/apt-pkg/cacheset.h
@@ -1068,7 +1068,7 @@ APT_IGNORE_DEPRECATED_POP
 	static VersionContainer FromDependency(pkgCacheFile &Cache, pkgCache::DepIterator const &D,
 					       CacheSetHelper::VerSelector const selector) {
 		CacheSetHelper helper;
-		return FromPackage(Cache, D, selector, helper);
+		return FromDependency(Cache, D, selector, helper);
 	}
 APT_IGNORE_DEPRECATED_PUSH
 	static VersionContainer FromDependency(pkgCacheFile &Cache, pkgCache::DepIterator const &D,
@@ -1080,11 +1080,11 @@ APT_IGNORE_DEPRECATED_PUSH
 	static VersionContainer FromDependency(pkgCacheFile &Cache, pkgCache::DepIterator const &D,
 					       Version const &selector) {
 		CacheSetHelper helper;
-		return FromPackage(Cache, D, (CacheSetHelper::VerSelector)selector, helper);
+		return FromDependency(Cache, D, (CacheSetHelper::VerSelector)selector, helper);
 	}
 APT_IGNORE_DEPRECATED_POP
 	static VersionContainer FromDependency(pkgCacheFile &Cache, pkgCache::DepIterator const &D) {
-		return FromPackage(Cache, D, CacheSetHelper::CANDIDATE);
+		return FromDependency(Cache, D, CacheSetHelper::CANDIDATE);
 	}
 									/*}}}*/
 };									/*}}}*/
diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index d01c14223..0e972dbad 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -23,6 +23,7 @@
 #include <apt-pkg/cacheset.h>
 #include <apt-pkg/pkgcache.h>
 #include <apt-pkg/cacheiterators.h>
+#include <apt-pkg/cachefile.h>
 #include <apt-pkg/macros.h>
 
 #include <stdio.h>
@@ -1189,18 +1190,8 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
          fixing the problem for "positive" dependencies */
       if (Start.IsNegative() == false && (DepState[Start->ID] & DepCVer) == DepCVer)
       {
-	 APT::VersionList verlist;
-	 pkgCache::VerIterator Cand = PkgState[Start.TargetPkg()->ID].CandidateVerIter(*this);
-	 if (Cand.end() == false && Start.IsSatisfied(Cand) == true)
-	    verlist.insert(Cand);
-	 for (PrvIterator Prv = Start.TargetPkg().ProvidesList(); Prv.end() != true; ++Prv)
-	 {
-	    pkgCache::VerIterator V = Prv.OwnerVer();
-	    pkgCache::VerIterator Cand = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
-	    if (Cand.end() == true || V != Cand || Start.IsSatisfied(Prv) == false)
-	       continue;
-	    verlist.insert(Cand);
-	 }
+	 pkgCacheFile CacheFile(this);
+	 APT::VersionList verlist = APT::VersionList::FromDependency(CacheFile, Start, APT::CacheSetHelper::CANDIDATE);
 	 CompareProviders comp(Start);
 
 	 do {
diff --git a/apt-private/private-cachefile.h b/apt-private/private-cachefile.h
index 4a68d9733..221852629 100644
--- a/apt-private/private-cachefile.h
+++ b/apt-private/private-cachefile.h
@@ -61,7 +61,7 @@ class APT_PUBLIC CacheFile : public pkgCacheFile
 };
 									/*}}}*/
 
-class APT_PUBLIC SortedPackageUniverse : public APT::PackageUniverse
+class SortedPackageUniverse : public APT::PackageUniverse
 {
    std::vector<map_pointer_t> &List;
    void LazyInit() const;
@@ -85,12 +85,12 @@ public:
    };
    typedef const_iterator iterator;
 
-   APT_PUBLIC const_iterator begin() const { LazyInit(); return const_iterator(data(), List.begin()); }
-   APT_PUBLIC const_iterator end() const { LazyInit(); return const_iterator(data(), List.end()); }
-   APT_PUBLIC const_iterator cbegin() const { LazyInit(); return const_iterator(data(), List.begin()); }
-   APT_PUBLIC const_iterator cend() const { LazyInit(); return const_iterator(data(), List.end()); }
-   APT_PUBLIC iterator begin() { LazyInit(); return iterator(data(), List.begin()); }
-   APT_PUBLIC iterator end() { LazyInit(); return iterator(data(), List.end()); }
+   const_iterator begin() const { LazyInit(); return const_iterator(data(), List.begin()); }
+   const_iterator end() const { LazyInit(); return const_iterator(data(), List.end()); }
+   const_iterator cbegin() const { LazyInit(); return const_iterator(data(), List.begin()); }
+   const_iterator cend() const { LazyInit(); return const_iterator(data(), List.end()); }
+   iterator begin() { LazyInit(); return iterator(data(), List.begin()); }
+   iterator end() { LazyInit(); return iterator(data(), List.end()); }
 };
 
 #endif
diff --git a/apt-private/private-download.cc b/apt-private/private-download.cc
index 37fae18e9..099146187 100644
--- a/apt-private/private-download.cc
+++ b/apt-private/private-download.cc
@@ -78,20 +78,23 @@ bool CheckDropPrivsMustBeDisabled(pkgAcquire &Fetcher)			/*{{{*/
 // CheckAuth - check if each download comes form a trusted source	/*{{{*/
 bool CheckAuth(pkgAcquire& Fetcher, bool const PromptUser)
 {
-   std::string UntrustedList;
+   std::vector<std::string> UntrustedList;
    for (pkgAcquire::ItemIterator I = Fetcher.ItemsBegin(); I < Fetcher.ItemsEnd(); ++I)
       if (!(*I)->IsTrusted())
-          UntrustedList += std::string((*I)->ShortDesc()) + " ";
+	 UntrustedList.push_back((*I)->ShortDesc());
 
-   if (UntrustedList == "")
+   if (UntrustedList.empty())
       return true;
 
    return AuthPrompt(UntrustedList, PromptUser);
 }
 
-bool AuthPrompt(std::string const &UntrustedList, bool const PromptUser)
+bool AuthPrompt(std::vector<std::string> const &UntrustedList, bool const PromptUser)
 {
-   ShowList(c2out,_("WARNING: The following packages cannot be authenticated!"),UntrustedList,"");
+   ShowList(c2out,_("WARNING: The following packages cannot be authenticated!"), UntrustedList,
+	 [](std::string const&) { return true; },
+	 [](std::string const&str) { return str; },
+	 [](std::string const&) { return ""; });
 
    if (_config->FindB("APT::Get::AllowUnauthenticated",false) == true)
    {
diff --git a/apt-private/private-download.h b/apt-private/private-download.h
index 0a0ac6b95..0f3db5e7a 100644
--- a/apt-private/private-download.h
+++ b/apt-private/private-download.h
@@ -4,6 +4,7 @@
 #include <apt-pkg/macros.h>
 
 #include <string>
+#include <vector>
 
 class pkgAcquire;
 
@@ -14,7 +15,7 @@ APT_PUBLIC bool CheckAuth(pkgAcquire& Fetcher, bool const PromptUser);
 
 // show a authentication warning prompt and return true if the system
 // should continue
-APT_PUBLIC bool AuthPrompt(std::string const &UntrustedList, bool const PromptUser);
+APT_PUBLIC bool AuthPrompt(std::vector<std::string> const &UntrustedList, bool const PromptUser);
 
 APT_PUBLIC bool AcquireRun(pkgAcquire &Fetcher, int const PulseInterval, bool * const Failure, bool * const TransientNetworkFailure);
 
diff --git a/apt-private/private-install.cc b/apt-private/private-install.cc
index cdca45755..0b5e33ae5 100644
--- a/apt-private/private-install.cc
+++ b/apt-private/private-install.cc
@@ -330,19 +330,17 @@ bool InstallPackages(CacheFile &Cache,bool ShwKept,bool Ask, bool Safety)
    }
 
    std::set<std::string> const disappearedPkgs = PM->GetDisappearedPackages();
-   if (disappearedPkgs.empty() == true)
-      return true;
-
-   std::string disappear;
-   for (std::set<std::string>::const_iterator d = disappearedPkgs.begin();
-	d != disappearedPkgs.end(); ++d)
-      disappear.append(*d).append(" ");
-
-   ShowList(c1out, P_("The following package disappeared from your system as\n"
-	"all files have been overwritten by other packages:",
-	"The following packages disappeared from your system as\n"
-	"all files have been overwritten by other packages:", disappearedPkgs.size()), disappear, "");
-   c0out << _("Note: This is done automatically and on purpose by dpkg.") << std::endl;
+   if (disappearedPkgs.empty() == false)
+   {
+      ShowList(c1out, P_("The following package disappeared from your system as\n"
+	       "all files have been overwritten by other packages:",
+	       "The following packages disappeared from your system as\n"
+	       "all files have been overwritten by other packages:", disappearedPkgs.size()), disappearedPkgs,
+	    [](std::string const &Pkg) { return Pkg.empty() == false; },
+	    [](std::string const &Pkg) { return Pkg; },
+	    [](std::string const &) { return std::string(); });
+      c0out << _("Note: This is done automatically and on purpose by dpkg.") << std::endl;
+   }
 
    return true;
 }
@@ -699,8 +697,7 @@ bool DoInstall(CommandLine &CmdL)
 
    /* Print out a list of suggested and recommended packages */
    {
-      std::string SuggestsList, RecommendsList;
-      std::string SuggestsVersions, RecommendsVersions;
+      std::list<std::string> Recommends, Suggests, SingleRecommends, SingleSuggests;
       for (auto const &Pkg: Universe)
       {
 	 /* Just look at the ones we want to install */
@@ -714,77 +711,79 @@ bool DoInstall(CommandLine &CmdL)
 	    pkgCache::DepIterator Start;
 	    pkgCache::DepIterator End;
 	    D.GlobOr(Start,End); // advances D
+	    if (Start->Type != pkgCache::Dep::Recommends && Start->Type != pkgCache::Dep::Suggests)
+	       continue;
 
-	    // FIXME: we really should display a or-group as a or-group to the user
-	    //        the problem is that ShowList is incapable of doing this
-            std::string RecommendsOrList,RecommendsOrVersions;
-            std::string SuggestsOrList,SuggestsOrVersions;
-	    bool foundInstalledInOrGroup = false;
-	    for(;;)
 	    {
-	       /* Skip if package is  installed already, or is about to be */
-	       pkgCache::PkgIterator const TarPkg = Start.TargetPkg();
-	       if (TarPkg->SelectedState == pkgCache::State::Install ||
-		   TarPkg->SelectedState == pkgCache::State::Hold ||
-		   Cache[Start.TargetPkg()].Install())
-	       {
-		  foundInstalledInOrGroup=true;
-		  break;
-	       }
-
-	       /* Skip if we already saw it */
-               std::string target = Start.TargetPkg().FullName(true) + " ";
-	       if (int(SuggestsList.find(target)) != -1 || int(RecommendsList.find(target)) != -1)
+	       // Skip if we already saw this
+	       std::string target;
+	       for (pkgCache::DepIterator I = Start; I != D; ++I)
 	       {
-		  foundInstalledInOrGroup=true;
-		  break; 
+		  if (target.empty() == false)
+		     target.append(" | ");
+		  target.append(I.TargetPkg().FullName(true));
 	       }
+	       std::list<std::string> &Type = Start->Type == pkgCache::Dep::Recommends ? SingleRecommends : SingleSuggests;
+	       if (std::find(Type.begin(), Type.end(), target) != Type.end())
+		  continue;
+	       Type.push_back(target);
+	    }
 
-	       // this is a dep on a virtual pkg, check if any package that provides it
-	       // should be installed
-	       if(Start.TargetPkg().ProvidesList() != 0)
+	    std::list<std::string> OrList;
+	    bool foundInstalledInOrGroup = false;
+	    for (pkgCache::DepIterator I = Start; I != D; ++I)
+	    {
 	       {
-		  pkgCache::PrvIterator I = Start.TargetPkg().ProvidesList();
-		  for (; I.end() == false; ++I)
+		  // satisfying package is installed and not marked for deletion
+		  APT::VersionList installed = APT::VersionList::FromDependency(Cache, I, APT::CacheSetHelper::INSTALLED);
+		  if (std::find_if(installed.begin(), installed.end(),
+			   [&Cache](pkgCache::VerIterator const &Ver) { return Cache[Ver.ParentPkg()].Delete() == false; }) != installed.end())
 		  {
-		     pkgCache::PkgIterator Pkg = I.OwnerPkg();
-		     if (Cache[Pkg].CandidateVerIter(Cache) == I.OwnerVer() && 
-			 Pkg.CurrentVer() != 0)
-			foundInstalledInOrGroup=true;
+		     foundInstalledInOrGroup = true;
+		     break;
 		  }
 	       }
 
-	       if (Start->Type == pkgCache::Dep::Suggests) 
-	       {
-		  SuggestsOrList += target;
-		  SuggestsOrVersions += std::string(Cache[Start.TargetPkg()].CandVersion) + "\n";
-	       }
-	       
-	       if (Start->Type == pkgCache::Dep::Recommends) 
 	       {
-		  RecommendsOrList += target;
-		  RecommendsOrVersions += std::string(Cache[Start.TargetPkg()].CandVersion) + "\n";
+		  // satisfying package is upgraded to/new install
+		  APT::VersionList upgrades = APT::VersionList::FromDependency(Cache, I, APT::CacheSetHelper::CANDIDATE);
+		  if (std::find_if(upgrades.begin(), upgrades.end(),
+			   [&Cache](pkgCache::VerIterator const &Ver) { return Cache[Ver.ParentPkg()].Upgrade(); }) != upgrades.end())
+		  {
+		     foundInstalledInOrGroup = true;
+		     break;
+		  }
 	       }
 
-	       if (Start >= End)
-		  break;
-	       ++Start;
+	       if (OrList.empty())
+		  OrList.push_back(I.TargetPkg().FullName(true));
+	       else
+		  OrList.push_back("| " + I.TargetPkg().FullName(true));
 	    }
-	    
+
 	    if(foundInstalledInOrGroup == false)
 	    {
-	       RecommendsList += RecommendsOrList;
-	       RecommendsVersions += RecommendsOrVersions;
-	       SuggestsList += SuggestsOrList;
-	       SuggestsVersions += SuggestsOrVersions;
+	       std::list<std::string> &Type = Start->Type == pkgCache::Dep::Recommends ? Recommends : Suggests;
+	       std::move(OrList.begin(), OrList.end(), std::back_inserter(Type));
 	    }
-	       
 	 }
       }
-
-      ShowList(c1out,_("Suggested packages:"),SuggestsList,SuggestsVersions);
-      ShowList(c1out,_("Recommended packages:"),RecommendsList,RecommendsVersions);
-
+      auto always_true = [](std::string const&) { return true; };
+      auto string_ident = [](std::string const&str) { return str; };
+      auto verbose_show_candidate =
+	 [&Cache](std::string str)
+	 {
+	    if (APT::String::Startswith(str, "| "))
+	       str.erase(0, 2);
+	    pkgCache::PkgIterator const Pkg = Cache->FindPkg(str);
+	    if (Pkg.end() == true)
+	       return "";
+	    return (*Cache)[Pkg].CandVersion;
+	 };
+      ShowList(c1out,_("Suggested packages:"), Suggests,
+	    always_true, string_ident, verbose_show_candidate);
+      ShowList(c1out,_("Recommended packages:"), Recommends,
+	    always_true, string_ident, verbose_show_candidate);
    }
 
    // See if we need to prompt
@@ -792,7 +791,7 @@ bool DoInstall(CommandLine &CmdL)
    if (Cache->InstCount() == verset[MOD_INSTALL].size() && Cache->DelCount() == 0)
       return InstallPackages(Cache,false,false);
 
-   return InstallPackages(Cache,false);   
+   return InstallPackages(Cache,false);
 }
 									/*}}}*/
 
diff --git a/apt-private/private-output.cc b/apt-private/private-output.cc
index b77efff86..b8e6dec02 100644
--- a/apt-private/private-output.cc
+++ b/apt-private/private-output.cc
@@ -300,66 +300,6 @@ void ListSingleVersion(pkgCacheFile &CacheFile, pkgRecords &records,	/*{{{*/
    out << output;
 }
 									/*}}}*/
-// ShowList - Show a list						/*{{{*/
-// ---------------------------------------------------------------------
-/* This prints out a string of space separated words with a title and 
-   a two space indent line wraped to the current screen width. */
-bool ShowList(ostream &out,string Title,string List,string VersionsList)
-{
-   if (List.empty() == true)
-      return true;
-   // trim trailing space
-   int NonSpace = List.find_last_not_of(' ');
-   if (NonSpace != -1)
-   {
-      List = List.erase(NonSpace + 1);
-      if (List.empty() == true)
-	 return true;
-   }
-
-   // Acount for the leading space
-   int ScreenWidth = ::ScreenWidth - 3;
-      
-   out << Title << endl;
-   string::size_type Start = 0;
-   string::size_type VersionsStart = 0;
-   while (Start < List.size())
-   {
-      if(_config->FindB("APT::Get::Show-Versions",false) == true &&
-         VersionsList.size() > 0) {
-         string::size_type End;
-         string::size_type VersionsEnd;
-         
-         End = List.find(' ',Start);
-         VersionsEnd = VersionsList.find('\n', VersionsStart);
-
-         out << "   " << string(List,Start,End - Start) << " (" << 
-            string(VersionsList,VersionsStart,VersionsEnd - VersionsStart) << 
-            ")" << endl;
-
-	 if (End == string::npos || End < Start)
-	    End = Start + ScreenWidth;
-
-         Start = End + 1;
-         VersionsStart = VersionsEnd + 1;
-      } else {
-         string::size_type End;
-
-         if (Start + ScreenWidth >= List.size())
-            End = List.size();
-         else
-            End = List.rfind(' ',Start+ScreenWidth);
-
-         if (End == string::npos || End < Start)
-            End = Start + ScreenWidth;
-         out << "  " << string(List,Start,End - Start) << endl;
-         Start = End + 1;
-      }
-   }   
-
-   return false;
-}
-									/*}}}*/
 // ShowBroken - Debugging aide						/*{{{*/
 // ---------------------------------------------------------------------
 /* This prints out the names of all the packages that are broken along
diff --git a/apt-private/private-output.h b/apt-private/private-output.h
index b9151b245..4930fd981 100644
--- a/apt-private/private-output.h
+++ b/apt-private/private-output.h
@@ -34,11 +34,11 @@ void ListSingleVersion(pkgCacheFile &CacheFile, pkgRecords &records,
 APT_PUBLIC void ShowBroken(std::ostream &out, CacheFile &Cache, bool const Now);
 APT_PUBLIC void ShowBroken(std::ostream &out, pkgCacheFile &Cache, bool const Now);
 
-template<class Container> APT_PUBLIC bool ShowList(std::ostream &out, std::string const &Title,
+template<class Container, class PredicateC, class DisplayP, class DisplayV> APT_PUBLIC bool ShowList(std::ostream &out, std::string const &Title,
       Container const &cont,
-      std::function<bool(pkgCache::PkgIterator const &)> Predicate,
-      std::function<std::string(pkgCache::PkgIterator const &)> PkgDisplay,
-      std::function<std::string(pkgCache::PkgIterator const &)> VerboseDisplay)
+      PredicateC Predicate,
+      DisplayP PkgDisplay,
+      DisplayV VerboseDisplay)
 {
    size_t const ScreenWidth = (::ScreenWidth > 3) ? ::ScreenWidth - 3 : 0;
    int ScreenUsed = 0;
@@ -88,8 +88,6 @@ template<class Container> APT_PUBLIC bool ShowList(std::ostream &out, std::strin
    }
    return true;
 }
-APT_DEPRECATED APT_PUBLIC bool ShowList(std::ostream &out, std::string Title, std::string List,
-              std::string VersionsList);
 
 void ShowNew(std::ostream &out,CacheFile &Cache);
 void ShowDel(std::ostream &out,CacheFile &Cache);
@@ -106,12 +104,12 @@ void Stats(std::ostream &out, pkgDepCache &Dep);
 bool YnPrompt(bool Default=true);
 bool AnalPrompt(const char *Text);
 
-APT_PUBLIC std::string PrettyFullName(pkgCache::PkgIterator const &Pkg);
-APT_PUBLIC std::string CandidateVersion(pkgCacheFile * const Cache, pkgCache::PkgIterator const &Pkg);
-APT_PUBLIC std::function<std::string(pkgCache::PkgIterator const &)> CandidateVersion(pkgCacheFile * const Cache);
-APT_PUBLIC std::string CurrentToCandidateVersion(pkgCacheFile * const Cache, pkgCache::PkgIterator const &Pkg);
-APT_PUBLIC std::function<std::string(pkgCache::PkgIterator const &)> CurrentToCandidateVersion(pkgCacheFile * const Cache);
-APT_PUBLIC std::string EmptyString(pkgCache::PkgIterator const &);
-APT_PUBLIC bool AlwaysTrue(pkgCache::PkgIterator const &);
+std::string PrettyFullName(pkgCache::PkgIterator const &Pkg);
+std::string CandidateVersion(pkgCacheFile * const Cache, pkgCache::PkgIterator const &Pkg);
+std::function<std::string(pkgCache::PkgIterator const &)> CandidateVersion(pkgCacheFile * const Cache);
+std::string CurrentToCandidateVersion(pkgCacheFile * const Cache, pkgCache::PkgIterator const &Pkg);
+std::function<std::string(pkgCache::PkgIterator const &)> CurrentToCandidateVersion(pkgCacheFile * const Cache);
+std::string EmptyString(pkgCache::PkgIterator const &);
+bool AlwaysTrue(pkgCache::PkgIterator const &);
 
 #endif
diff --git a/cmdline/apt-get.cc b/cmdline/apt-get.cc
index 6fefbde47..ca9650998 100644
--- a/cmdline/apt-get.cc
+++ b/cmdline/apt-get.cc
@@ -742,7 +742,7 @@ static bool DoSource(CommandLine &CmdL)
 
    // Load the requestd sources into the fetcher
    unsigned J = 0;
-   std::string UntrustedList;
+   std::vector<std::string> UntrustedList;
    for (const char **I = CmdL.FileList + 1; *I != 0; I++, J++)
    {
       string Src;
@@ -756,8 +756,8 @@ static bool DoSource(CommandLine &CmdL)
       }
 
       if (Last->Index().IsTrusted() == false)
-         UntrustedList += Src + " ";
-      
+         UntrustedList.push_back(Src);
+
       string srec = Last->AsStr();
       string::size_type pos = srec.find("\nVcs-");
       while (pos != string::npos)
@@ -884,7 +884,7 @@ static bool DoSource(CommandLine &CmdL)
    CheckDropPrivsMustBeDisabled(Fetcher);
 
    // check authentication status of the source as well
-   if (UntrustedList != "" && !AuthPrompt(UntrustedList, false))
+   if (UntrustedList.empty() == false && AuthPrompt(UntrustedList, false) == false)
       return false;
 
    // Run it
diff --git a/test/integration/test-apt-showlist-orgroup-in-recommends b/test/integration/test-apt-showlist-orgroup-in-recommends
new file mode 100755
index 000000000..bce421ac4
--- /dev/null
+++ b/test/integration/test-apt-showlist-orgroup-in-recommends
@@ -0,0 +1,158 @@
+#!/bin/sh
+set -e
+
+TESTDIR=$(readlink -f $(dirname $0))
+. $TESTDIR/framework
+
+setupenvironment
+configarchitecture 'i386'
+
+# simple case
+insertinstalledpackage 'aaa' 'all' '1'
+insertinstalledpackage 'ddd' 'all' '1'
+insertpackage 'unstable' 'aaa' 'all' '1'
+insertpackage 'unstable' 'ddd' 'all' '1'
+insertpackage 'unstable' 'yyy' 'all' '1'
+insertpackage 'unstable' 'zzz' 'all' '1'
+insertpackage 'unstable' 'simple' 'all' '1' 'Recommends: aaa, bbb
+Suggests: ccc, ddd'
+insertpackage 'unstable' 'orgroup' 'all' '1' 'Recommends: aaa | bbb
+Suggests: ccc | ddd'
+insertpackage 'unstable' 'orgroup2' 'all' '1' 'Recommends: xxx | yyy
+Suggests: yyy | zzz'
+insertpackage 'unstable' 'orgroup3' 'all' '1' 'Recommends: xxx | yyy
+Suggests: yyy | zzz'
+insertpackage 'unstable' 'orgroup4' 'all' '1' 'Recommends: xxx
+Suggests: zzz'
+insertpackage 'unstable' 'versionedor' 'all' '1' 'Recommends: aaa (>> 2) | bbb
+Suggests: ccc | ddd (>> 2)'
+
+setupaptarchive
+
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Suggested packages:
+  ccc
+Recommended packages:
+  bbb
+The following NEW packages will be installed:
+  simple
+0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
+Inst simple (1 unstable [all])
+Conf simple (1 unstable [all])' aptget install simple -s --no-install-recommends
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Suggested packages:
+  ccc
+Recommended packages:
+  aaa bbb
+The following packages will be REMOVED:
+  aaa
+The following NEW packages will be installed:
+  simple
+0 upgraded, 1 newly installed, 1 to remove and 0 not upgraded.
+Remv aaa [1]
+Inst simple (1 unstable [all])
+Conf simple (1 unstable [all])' aptget install simple aaa- -s --no-install-recommends
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+The following NEW packages will be installed:
+  orgroup
+0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
+Inst orgroup (1 unstable [all])
+Conf orgroup (1 unstable [all])' aptget install orgroup -s --no-install-recommends
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Recommended packages:
+  aaa | bbb
+The following packages will be REMOVED:
+  aaa
+The following NEW packages will be installed:
+  orgroup
+0 upgraded, 1 newly installed, 1 to remove and 0 not upgraded.
+Remv aaa [1]
+Inst orgroup (1 unstable [all])
+Conf orgroup (1 unstable [all])' aptget install orgroup aaa- -s --no-install-recommends
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Suggested packages:
+  yyy | zzz
+Recommended packages:
+  xxx | yyy
+The following NEW packages will be installed:
+  orgroup2
+0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
+Inst orgroup2 (1 unstable [all])
+Conf orgroup2 (1 unstable [all])' aptget install orgroup2 -s --no-install-recommends
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Suggested packages:
+  yyy | zzz
+Recommended packages:
+  xxx | yyy
+The following NEW packages will be installed:
+  orgroup2 orgroup3
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst orgroup2 (1 unstable [all])
+Inst orgroup3 (1 unstable [all])
+Conf orgroup2 (1 unstable [all])
+Conf orgroup3 (1 unstable [all])' aptget install orgroup2 orgroup3 -s --no-install-recommends
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Suggested packages:
+  yyy | zzz zzz
+Recommended packages:
+  xxx | yyy xxx
+The following NEW packages will be installed:
+  orgroup2 orgroup4
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst orgroup2 (1 unstable [all])
+Inst orgroup4 (1 unstable [all])
+Conf orgroup2 (1 unstable [all])
+Conf orgroup4 (1 unstable [all])' aptget install orgroup2 orgroup4 -s --no-install-recommends
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Suggested packages:
+   yyy (1)
+   | zzz (1)
+   zzz (1)
+Recommended packages:
+   xxx
+   | yyy (1)
+   xxx
+The following NEW packages will be installed:
+   orgroup2 (1)
+   orgroup4 (1)
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst orgroup2 (1 unstable [all])
+Inst orgroup4 (1 unstable [all])
+Conf orgroup2 (1 unstable [all])
+Conf orgroup4 (1 unstable [all])' aptget install orgroup2 orgroup4 -s -V --no-install-recommends
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Suggested packages:
+   zzz (1)
+Recommended packages:
+   xxx
+The following NEW packages will be installed:
+   orgroup2 (1)
+   orgroup4 (1)
+   yyy (1)
+0 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
+Inst orgroup2 (1 unstable [all])
+Inst orgroup4 (1 unstable [all])
+Inst yyy (1 unstable [all])
+Conf orgroup2 (1 unstable [all])
+Conf orgroup4 (1 unstable [all])
+Conf yyy (1 unstable [all])' aptget install orgroup2 orgroup4 yyy -s -V --no-install-recommends
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Suggested packages:
+  ccc | ddd
+Recommended packages:
+  aaa | bbb
+The following NEW packages will be installed:
+  versionedor
+0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
+Inst versionedor (1 unstable [all])
+Conf versionedor (1 unstable [all])' aptget install versionedor -s --no-install-recommends
diff --git a/test/integration/test-bug-470115-new-and-tighten-recommends b/test/integration/test-bug-470115-new-and-tighten-recommends
index 0970e2f23..80f699ef3 100755
--- a/test/integration/test-bug-470115-new-and-tighten-recommends
+++ b/test/integration/test-bug-470115-new-and-tighten-recommends
@@ -165,6 +165,8 @@ Conf upgrade-over-new (2 unstable [all])' aptget install upgrade-over-new -s
 # the user doesn't seem to need it so avoid upgrading it
 testsuccessequal 'Reading package lists...
 Building dependency tree...
+Recommended packages:
+  cool
 The following packages will be upgraded:
   now-satisfiable
 1 upgraded, 0 newly installed, 0 to remove and 12 not upgraded.
diff --git a/test/integration/test-bug-549968-install-depends-of-not-installed b/test/integration/test-bug-549968-install-depends-of-not-installed
index 3ff4807de..1d969fea2 100755
--- a/test/integration/test-bug-549968-install-depends-of-not-installed
+++ b/test/integration/test-bug-549968-install-depends-of-not-installed
@@ -19,6 +19,8 @@ Building dependency tree...
   MarkInstall coolstuff [ i386 ] < none -> 1.0 > ( other ) FU=1
     Ignore MarkInstall of extracoolstuff [ i386 ] < none -> 1.0 > ( other ) as its mode (Keep) is protected
 Package 'extracoolstuff' is not installed, so not removed
+Recommended packages:
+  extracoolstuff
 The following NEW packages will be installed:
   coolstuff
 0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
diff --git a/test/integration/test-handling-broken-orgroups b/test/integration/test-handling-broken-orgroups
index 149f05fa9..15964a270 100755
--- a/test/integration/test-handling-broken-orgroups
+++ b/test/integration/test-handling-broken-orgroups
@@ -63,7 +63,7 @@ E: Unable to correct problems, you have held broken packages.' aptget install co
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Recommended packages:
-  cool2 stuff2
+  cool2 | stuff2
 The following NEW packages will be installed:
   coolstuff-brokenrec
 0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
diff --git a/test/integration/test-release-candidate-switching b/test/integration/test-release-candidate-switching
index a1a6a6142..510a8e078 100755
--- a/test/integration/test-release-candidate-switching
+++ b/test/integration/test-release-candidate-switching
@@ -370,7 +370,7 @@ The following extra packages will be installed:
 Recommended packages:
    amarok-utils (2.3.1-1+sid)
    phonon-backend-xine (4.6.0really4.4.2-1+sid)
-   phonon-backend ()
+   | phonon-backend
    libmtp8 (0.3.1+sid)
    libc6 (2.11.2-7+sid)
 The following NEW packages will be installed:
diff --git a/test/integration/test-releasefile-verification b/test/integration/test-releasefile-verification
index 759242514..06701c623 100755
--- a/test/integration/test-releasefile-verification
+++ b/test/integration/test-releasefile-verification
@@ -36,7 +36,7 @@ installaptold() {
 	testsuccessequal 'Reading package lists...
 Building dependency tree...
 Suggested packages:
-  aptitude synaptic wajig dpkg-dev apt-doc bzip2 lzma python-apt
+  aptitude | synaptic | wajig dpkg-dev apt-doc bzip2 lzma python-apt
 The following NEW packages will be installed:
   apt
 0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
@@ -49,7 +49,7 @@ installaptnew() {
 	testsuccessequal 'Reading package lists...
 Building dependency tree...
 Suggested packages:
-  aptitude synaptic wajig dpkg-dev apt-doc bzip2 lzma python-apt
+  aptitude | synaptic | wajig dpkg-dev apt-doc bzip2 lzma python-apt
 The following NEW packages will be installed:
   apt
 0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
@@ -62,7 +62,7 @@ failaptold() {
 	testfailureequal 'Reading package lists...
 Building dependency tree...
 Suggested packages:
-  aptitude synaptic wajig dpkg-dev apt-doc bzip2 lzma python-apt
+  aptitude | synaptic | wajig dpkg-dev apt-doc bzip2 lzma python-apt
 The following NEW packages will be installed:
   apt
 0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
@@ -76,7 +76,7 @@ failaptnew() {
 	testfailureequal 'Reading package lists...
 Building dependency tree...
 Suggested packages:
-  aptitude synaptic wajig dpkg-dev apt-doc bzip2 lzma python-apt
+  aptitude | synaptic | wajig dpkg-dev apt-doc bzip2 lzma python-apt
 The following NEW packages will be installed:
   apt
 0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.