Explore or-groups for Recommends further than first

MarkInstall only looks at the first alternative in an or-group which has
a fighting chance of being satisfiable (= the package itself satisfies
the dependency, if it is installable itself is not considered).

This is "hidden" for Depends by the problem resolver who will try
another member of the or-group later, but Recommends are not a problem
for it, so for them the alternatives are never further explored.

Exploring the or-group in MarkInstall seems like the better choice for
both types as that frees the problem resolver to deal with the hard
things like package conflicts.

2 files changed, 82 insertions, 30 deletions

diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index d43c1522e..3d510b7e6 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -1246,42 +1246,47 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 
       /* This bit is for processing the possibility of an install/upgrade
          fixing the problem for "positive" dependencies */
-      if (Start.IsNegative() == false && (DepState[Start->ID] & DepCVer) == DepCVer)
+      if (not Start.IsNegative() && (DepState[Start->ID] & DepCVer) == DepCVer)
       {
-	 pkgCacheFile CacheFile(this);
-	 APT::VersionList verlist = APT::VersionList::FromDependency(CacheFile, Start, APT::CacheSetHelper::CANDIDATE);
-	 CompareProviders comp(Start);
-
-	 do {
-	    APT::VersionList::iterator InstVer = std::max_element(verlist.begin(), verlist.end(), comp);
-
-	    if (InstVer == verlist.end())
-	       break;
+	 bool foundSolution = false;
+	 for (; Start != Dep && not foundSolution; ++Start)
+	 {
+	    pkgCacheFile CacheFile(this);
+	    APT::VersionList verlist = APT::VersionList::FromDependency(CacheFile, Start, APT::CacheSetHelper::CANDIDATE);
+	    CompareProviders comp(Start);
 
-	    pkgCache::PkgIterator InstPkg = InstVer.ParentPkg();
-	    if(DebugAutoInstall == true)
-	       std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
-			 << " as " << Start.DepType() << " of " << Pkg.Name()
-			 << std::endl;
-	    if (MarkInstall(InstPkg, true, Depth + 1, false, ForceImportantDeps) == false)
+	    do
 	    {
-	       verlist.erase(InstVer);
-	       continue;
-	    }
+	       APT::VersionList::iterator InstVer = std::max_element(verlist.begin(), verlist.end(), comp);
+	       if (InstVer == verlist.end())
+		  break;
 
-	    // now check if we should consider it a automatic dependency or not
-	    if(InstPkg->CurrentVer == 0 && MoveAutoBitToDependencies)
-	    {
-	       if(DebugAutoInstall == true)
-		  std::clog << OutputInDepth(Depth) << "Setting " << InstPkg.FullName(false) << " NOT as auto-installed (direct "
-		     << Start.DepType() << " of " << Pkg.FullName(false) << " which is manual and in APT::Move-Autobit-Sections)" << std::endl;
-	       MarkAuto(InstPkg, false);
-	    }
+	       pkgCache::PkgIterator InstPkg = InstVer.ParentPkg();
+	       if (DebugAutoInstall)
+		  std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
+			    << " as " << Start.DepType() << " of " << Pkg.Name() << '\n';
+	       if (not MarkInstall(InstPkg, true, Depth + 1, false, ForceImportantDeps))
+	       {
+		  verlist.erase(InstVer);
+		  continue;
+	       }
 
+	       // now check if we should consider it a automatic dependency or not
+	       if (InstPkg->CurrentVer == 0 && MoveAutoBitToDependencies)
+	       {
+		  if (DebugAutoInstall == true)
+		     std::clog << OutputInDepth(Depth) << "Setting " << InstPkg.FullName(false) << " NOT as auto-installed (direct "
+			       << Start.DepType() << " of " << Pkg.FullName(false) << " which is manual and in APT::Move-Autobit-Sections)\n";
+		  MarkAuto(InstPkg, false);
+	       }
 
-	    break;
-	 } while(true);
-	 continue;
+	       foundSolution = true;
+	       break;
+	    } while (true);
+	 }
+	 if (foundSolution)
+	    continue;
+	 break;
       }
       /* Negative dependencies have no or-group
 	 If the dependency isn't versioned, we try if an upgrade might solve the problem.
diff --git a/test/integration/test-explore-or-groups-in-markinstall b/test/integration/test-explore-or-groups-in-markinstall
new file mode 100755
index 000000000..f5898cfca
--- /dev/null
+++ b/test/integration/test-explore-or-groups-in-markinstall
@@ -0,0 +1,47 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertpackage 'unstable' 'okay' 'all' '1'
+insertpackage 'unstable' 'unneeded' 'all' '1'
+insertpackage 'unstable' 'later' 'all' '1'
+
+insertpackage 'unstable' 'bad-level0' 'all' '1' 'Depends: unneeded, unknown'
+
+insertfoos() {
+	insertpackage 'unstable' "foo-${1}-level0" 'all' '1' "${2}: unknown | okay | later"
+	insertpackage 'unstable' "foo-${1}-level1" 'all' '1' "${2}: bad-level0 | okay | later"
+}
+insertfoos 'd' 'Depends'
+insertfoos 'r' 'Recommends'
+
+setupaptarchive
+
+testsuccessheadequal() {
+	msggroup 'testsuccessheadequal'
+	local HEADLINES="$1"
+	local CMP="$2"
+	shift 2
+	testsuccesswithglobalerror 'testsuccess' 'EW' "$@"
+	cp "${TMPWORKINGDIRECTORY}/rootdir/tmp/testsuccess.output" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testsuccessheadequal.output"
+	testsuccessequal "$CMP" head -n "$HEADLINES" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testsuccessheadequal.output"
+	msggroup
+}
+checkfoos() {
+	msgmsg 'Install checks with foos dependency type' "$2"
+	for i in 0 1; do
+		testsuccessheadequal 7 "Reading package lists...
+Building dependency tree...
+The following additional packages will be installed:
+  okay
+The following NEW packages will be installed:
+  foo-${1}-level${i} okay
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded." apt install foo-${1}-level${i} -s
+	done
+}
+checkfoos 'd' 'Depends'
+checkfoos 'r' 'Recommends'