solver3: Merge Depends into Recommends

Merge any hard clauses into optional clauses, such that
optional clauses don't end up with more choices.

For example if you have

    Depends: a | b
    Recommends: a | c

This becomes:

    Depends: a | b
    Recommends: a

We have simulated this with the chaos-actor in the test case
and a

    Depends: git (not satisfied by chaos provider)
    Recommends: git (satisfied by chaos provider)

and the latter constraint is limited to the former.

2 files changed, 36 insertions, 7 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index c4c28b273..95cff96f3 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -683,7 +683,7 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
       bool merged = false;
       for (auto const &earlierClause : clauses)
       {
-	 if (earlierClause->negative || earlierClause->optional != clause.optional)
+	 if (earlierClause->negative)
 	    continue;
 	 if (std::none_of(earlierClause->solutions.begin(), earlierClause->solutions.end(), [&clause](auto earlierSol)
 			  { return std::find(clause.solutions.begin(),
@@ -691,13 +691,29 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
 					     earlierSol) != clause.solutions.end(); }))
 	    continue;
 
-	 std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol)
-		       { return std::find(clause.solutions.begin(),
-					  clause.solutions.end(),
-					  earlierSol) == clause.solutions.end(); });
+	 if (earlierClause->optional == clause.optional)
+	 {
+	    std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol)
+			  { return std::find(clause.solutions.begin(),
+					     clause.solutions.end(),
+					     earlierSol) == clause.solutions.end(); });
 
-	 earlierClause->merged.push_front(clause);
-	 merged = true;
+	    earlierClause->merged.push_front(clause);
+	    merged = true;
+	 }
+	 else if (clause.optional)
+	 {
+	    // If say a Depends has fewer solution than a Recommends, remove the Recommend's extranous ones.
+	    std::erase_if(clause.solutions, [&earlierClause, this](auto sol)
+			  { return std::find(earlierClause->solutions.begin(),
+					     earlierClause->solutions.end(),
+					     sol) == earlierClause->solutions.end(); });
+
+	    // Remove recursion here, such that we display correctly (if we ever display anywhere...)
+	    auto earlierClauseCopy = *earlierClause;
+	    clause.merged = std::move(earlierClauseCopy.merged);
+	    clause.merged.push_front(earlierClauseCopy);
+	 }
       }
 
       if (merged)
diff --git a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies
index 4f58893bf..86866b233 100755
--- a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies
+++ b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies
@@ -20,6 +20,8 @@ insertinstalledpackage 'git-cvs' 'amd64' '1:2.25.1-1' 'Depends: git (>> 1:2.25.1
 insertpackage 'unstable' 'git' 'amd64,i386' '1:2.26.2-1' 'Multi-Arch: foreign'
 insertpackage 'unstable' 'git-cvs' 'amd64,i386' '1:2.26.2-1' 'Depends: git (>> 1:2.26.2), git (<< 1:2.26.2-.)'
 insertpackage 'unstable' 'git-ng' 'amd64,i386' '1:2.26.2-1' 'Depends: git (>> 1:2.26.2), git (<< 1:2.26.2-.)'
+insertpackage 'unstable' 'git-rec-ng' 'amd64,i386' '1:2.26.2-1' 'Recommends: git (>> 1:2.26.2)
+Depends: git (<< 1:2.26.2-.)'
 insertpackage 'unstable' 'chaos-actor' 'amd64,i386' '1' 'Provides: git (2:1)'
 
 setupaptarchive
@@ -165,3 +167,14 @@ E: Unable to satisfy dependencies. Reached two conflicting decisions:
         1. git:amd64=1:2.25.1-1 is selected for install as above
         2. git:amd64 Conflicts git:i386' apt install git-ng -s
 
+# The Recommends: git (>> 1:2.26.2-1) will be left unsatisfied rather than pulling in chaos-actor.
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Solving dependencies...
+Recommended packages:
+  git
+The following NEW packages will be installed:
+  git-rec-ng
+0 upgraded, 1 newly installed, 0 to remove and 2 not upgraded.
+Inst git-rec-ng (1:2.26.2-1 unstable [amd64])
+Conf git-rec-ng (1:2.26.2-1 unstable [amd64])' apt install git-rec-ng -s