solver3: Merge intersecting dependencies

If a package declares multiple dependencies that can be solved by
the same packages we should use the common set of packages to
solve them.

A common example is requiring the same Debian source version, or the
same upstream version as in our test case:

    git-ng Depends: git (>> 1:2.26.2), git (<< 1:2.26.2-.)

The solver expands this to the concrete objects:

    git-ng Depends: "real git" (= 1:2.26.2-1) | chaos-actor, "real git" (= 1:2.26.2-1) | "real git" (= 1:2.25.1-1)

When given an upgrade request, the solver would now choose

    chaos-actor               to satisfy git (>> 1:2.26.2)
    "real git" (= 1:2.25.1-1) to satisfy git (<< 1:2.26.2-.)

To satisfy the two constraints, which is not the intended outcome.

Address this problem by introducing a concept of merged clauses:
If two dependencies of a package have overlapping solutions, replace
the dependency by the intersection, and record the merged clause
instead, this leads to a single clause:

    Depends: git (>> 1:2.26.2) and git (<< 1:2.26.2-.)

which expands to just the real git binary.

The implementation is a bit finicky in that it removes the variables
from the original clause which may not be helpful for debugging, but
it records the clauses merged with, as seen in the test case, so the
reasoning is clear.

LP: #2111792

1 files changed, 45 insertions, 5 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index be1576e98..c4c28b273 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -232,10 +232,11 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
    return false;
 }
 
-std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty) const
+std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty, bool showMerged) const
 {
    std::string out;
-   out.append(reason.toString(cache));
+   if (showMerged)
+      out.append(reason.toString(cache));
    if (dep && pretty)
    {
       out.append(" ").append(pkgCache::DepIterator(cache, dep).DepType()).append(" ");
@@ -266,6 +267,14 @@ std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty) const
       for (auto var : solutions)
 	 out.append(" | ").append(var.toString(cache));
    }
+   if (showMerged && not merged.empty())
+   {
+      for (auto &clause : merged)
+      {
+	 out.append(" and");
+	 out.append(clause.toString(cache, pretty, false));
+      }
+   }
    return out;
 }
 
@@ -664,6 +673,37 @@ static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b)
 const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
 {
    auto &clauses = (*this)[clause.reason].clauses;
+
+   if (not clause.negative)
+   {
+      // If we get multiple dependencies of the same class on related sets of packages,
+      // intersect them. In particular this deals with dependencies of the form
+      //	Depends: pkg (>= 1-1), pkg (<= 1-1.1)
+      // which is a common pattern used to express dependencies on the same source version.
+      bool merged = false;
+      for (auto const &earlierClause : clauses)
+      {
+	 if (earlierClause->negative || earlierClause->optional != clause.optional)
+	    continue;
+	 if (std::none_of(earlierClause->solutions.begin(), earlierClause->solutions.end(), [&clause](auto earlierSol)
+			  { return std::find(clause.solutions.begin(),
+					     clause.solutions.end(),
+					     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(); });
+
+	 earlierClause->merged.push_front(clause);
+	 merged = true;
+      }
+
+      if (merged)
+	 return nullptr;
+   }
+
    clauses.push_back(std::make_unique<Clause>(std::move(clause)));
    auto const &inserted = clauses.back();
    for (auto var : inserted->solutions)
@@ -1173,7 +1213,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	    Clause w{Var(), Group, isOptional};
 	    w.solutions.push_back(Var(P));
 	    auto insertedW = RegisterClause(std::move(w));
-	    if (not AddWork(Work{insertedW, depth()}))
+	    if (insertedW && not AddWork(Work{insertedW, depth()}))
 	       return false;
 
 	    if (not isAuto)
@@ -1189,7 +1229,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	       shortcircuit.solutions.push_back(Var(V));
 	    std::stable_sort(shortcircuit.solutions.begin(), shortcircuit.solutions.end(), CompareProviders3{cache, policy, P, *this});
 	    auto insertedShort = RegisterClause(std::move(shortcircuit));
-	    if (not AddWork(Work{insertedShort, depth()}))
+	    if (insertedShort && not AddWork(Work{insertedShort, depth()}))
 	       return false;
 
 	    // Discovery here is needed so the shortcircuit clause can actually become unit.
@@ -1208,7 +1248,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 if (unlikely(debug >= 1))
 	    std::cerr << "Install essential package " << P << std::endl;
 	 auto inserted = RegisterClause(std::move(w));
-	 if (not AddWork(Work{inserted, depth()}))
+	 if (inserted && not AddWork(Work{inserted, depth()}))
 	    return false;
       }
    }