solver3: Verbose error messages

Introduce a new function, LongWhyStr() that returns a longer
reason for why something is being installed (or not).

This does the same path walk as the other function does, but
it renders the clauses at each level, and one per line, so
the whole output is a lot more informative.

It is a separate function to keep the existing debug messages
use the simple single line implication graph

We remove the other special case in AddWork() for empty solutions
to mke use of the general case in Solve() instead, and then adapt
the case in Solve() to the same case as in Enqueue(). This also
happens to fix the bug that when we encountered an empty clause
we just printed the clause had no solution, but not how we got
to install the package with the clause.

Adapt the test suite for the changes which is an annoying amount
of paperwork.

2 files changed, 208 insertions, 21 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index 3511132dd..9f27951e8 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -35,6 +35,7 @@
 #include <cassert>
 #include <chrono>
 #include <ctime>
+#include <iomanip>
 #include <sstream>
 
 // FIXME: Helpers stolen from DepCache, please give them back.
@@ -247,11 +248,15 @@ std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty) const
 	    break;
 	 out.append(" | ");
       }
-      return out;
    }
-   out.append(" -> ");
-   for (auto var : solutions)
-      out.append(" | ").append(var.toString(cache));
+   else if (group == Group::SelectVersion && negative)
+      out.append(" conflicts with other versions of itself");
+   else
+   {
+      out.append(" -> ");
+      for (auto var : solutions)
+	 out.append(" | ").append(var.toString(cache));
+   }
    return out;
 }
 
@@ -303,6 +308,167 @@ std::string APT::Solver::WhyStr(Var reason) const
    return outstr;
 }
 
+std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const
+{
+   std::ostringstream out;
+
+   // Helper function to nicely print more details than just "install/do not install", such as "removal", "upgrade", "downgrade", "install"
+   auto printSelection = [this](Var var, bool decision)
+   {
+      std::string s;
+      if (auto pkg = var.Pkg(cache); not decision && pkg && pkg->CurrentVer)
+	 strprintf(s, "%s is selected for removal", var.toString(cache).c_str());
+      else if (auto ver = var.Ver(cache); decision && ver && ver.ParentPkg().CurrentVer() && ver.ParentPkg().CurrentVer() != ver)
+      {
+	 if (cache.VS->CmpVersion(ver.ParentPkg().CurrentVer().VerStr(), ver.VerStr()) < 0)
+	    strprintf(s, "%s is selected as an upgrade", var.toString(cache).c_str());
+	 else
+	    strprintf(s, "%s is selected as a downgrade", var.toString(cache).c_str());
+      }
+      else if (not decision)
+	 strprintf(s, "%s is not selected for install", var.toString(cache).c_str());
+      else
+	 strprintf(s, "%s is selected for install", var.toString(cache).c_str());
+      return s;
+   };
+
+   // Helper: Recurse into all of the children of the clause and print the decision for them.
+   auto recurseChildren = [&](const Clause *clause, Var skip = Var())
+   {
+      if (clause->solutions.empty())
+	 out << prefix << "[no choices]\n";
+      for (auto choice : clause->solutions)
+      {
+	 if (choice == skip)
+	    continue;
+
+	 if ((*this)[choice].decision == Decision::NONE)
+	    out << prefix << "- " << choice.toString(cache) << " is undecided\n";
+	 else
+	    out << prefix << "- " << LongWhyStr(choice, (*this)[choice].decision == Decision::MUST, (*this)[choice].reason, prefix + "  ", seen).substr(prefix.size() + 2);
+      }
+   };
+
+   // Version selection clauses like pkg=ver -> pkg or pkg -> pkg=ver are irrelevant for the user, skip them
+   if (decision && rclause && rclause->group == Group::SelectVersion)
+   {
+      var = rclause->reason;
+      rclause = (*this)[var].reason;
+   }
+
+   // No reason given, probably a user request or manually installed or essential or whatnot.
+   if (not rclause)
+   {
+      out << prefix << printSelection(var, decision) << "\n";
+      return out.str();
+   }
+
+   // We could be called with a decision we tried to make but failed due to a conflict;
+   // this checks if it is the real decision.
+   if ((*this)[var].decision != Decision::NONE && decision == ((*this)[var].decision == Decision::MUST) && (*this)[var].reason == rclause)
+   {
+      // If we have seen the real decision before; we dont't need to print it again.
+      if (seen.find(var) != seen.end())
+      {
+	 out << prefix << printSelection(var, decision) << " as above\n";
+	 return out.str();
+      }
+      seen.insert(var);
+   }
+
+   // A package was decided "not install" due to a positive clause, so the clause is unsat.
+   if (not decision && rclause && not rclause->negative)
+   {
+      out << prefix << rclause->toString(cache, true) << "\n";
+      out << prefix << "but none of the choices are installable:\n";
+      recurseChildren(rclause);
+      return out.str();
+   }
+
+   // Build the strongest path from a root to our decision leaf
+   std::vector<Var> path;
+   for (auto reason = bestReason(rclause, var); not reason.empty(); reason = bestReason((*this)[reason].reason, reason))
+      path.push_back(reason);
+
+   // Render the strong reasoning path
+   out << prefix << printSelection(var, decision) << " because:\n";
+   auto w = std::to_string(path.size() + 1).size();
+   size_t i = 1;
+   for (auto it = path.rbegin(); it != path.rend(); ++it, ++i)
+   {
+      auto const &state = (*this)[*it];
+      // Don't print version selection clauses
+      if (state.reason && state.reason->group == Group::SelectVersion)
+      {
+	 --i;
+	 continue;
+      }
+      if (seen.find(*it) != seen.end())
+      {
+	 if ((it + 1) == path.rend() || seen.find(*(it + 1)) == seen.end())
+	 {
+	    out << prefix << (i == 1 ? "" : "1-") << i << ". " << printSelection(*it, state.decision == Decision::MUST) << " as above\n";
+	 }
+	 continue;
+      }
+      seen.insert(*it);
+      if (state.reason)
+      {
+	 out << prefix << std::setw(w) << i << ". " << state.reason->toString(cache, true) << "\n";
+	 if (state.reason->solutions.size() > 1)
+	    out << prefix << std::setw(w) << " " << "  [selected " << it->toString(cache) << " for " << (state.decision == Decision::MUST ? "install" : "remove") << "]\n";
+      }
+      else
+	 out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.decision == Decision::MUST) << "\n";
+   }
+
+   // Print the leaf. We can't have the leaf in the path because we might be called for an attempted decision
+   // that conflicts with the actual assignment (to simplify: we marked X for not install, then we process Y depends X
+   // and try to mark X and reach the conflict, we are called with "X" and the "Y depends X" clause).
+   out << prefix << std::setw(w) << i << ". " << rclause->toString(cache, true) << "\n";
+   if (rclause->solutions.size() > 1)
+      out << prefix << std::setw(w) << " " << "  " << "[selected " << bestReason(rclause, var).toString(cache) << "]\n";
+
+   bool firstContext = true;
+   // Show alternative paths not taken. Consider you have Y depends X|Z; and you mark X
+   // for it; we show above Y -> X as the path, but here we go show why Z was not considered in "Y depends X|Z".
+   for (auto it = path.rbegin(); it != path.rend(); ++it)
+   {
+      auto const &state = (*this)[*it];
+      if (not state.reason) // If we have no reason, we don't have alternatives
+	 continue;
+      if (state.reason->solutions.size() <= 1) // Nothing to print if we no alternatives
+	 continue;
+      if (state.reason->negative) // We only actually need one conflicting choice, ignore others
+	 continue;
+
+      if (firstContext)
+      {
+	 out << prefix << "For context, additional choices that could not be installed:" << "\n";
+      }
+
+      firstContext = false;
+      out << prefix << "* In " << state.reason->toString(cache, true) << ":\n";
+      prefix += "  ";
+      recurseChildren(state.reason, *it);
+      prefix.resize(prefix.size() - 2);
+   }
+   if (rclause->solutions.size() > 1 && not rclause->negative)
+   {
+      if (firstContext)
+      {
+	 out << prefix << "For context, additional choices that could not be installed:" << "\n";
+      }
+      firstContext = false;
+      out << prefix << "* In " << rclause->toString(cache, true) << ":\n";
+      prefix += "  ";
+      recurseChildren(rclause, var);
+      prefix.resize(prefix.size() - 2);
+   }
+
+   return out.str();
+}
+
 // This is essentially asking whether any other binary in the source package has a higher candidate
 // version. This pretends that each package is installed at the same source version as the package
 // under consideration.
@@ -375,7 +541,14 @@ bool APT::Solver::Enqueue(Var var, bool decision, const Clause *reason)
    if (state.decision != Decision::NONE)
    {
       if (state.decision != decisionCast)
-	 return _error->Error("Conflict: %s -> %s%s but %s", WhyStr(bestReason(reason, var)).c_str(), decision ? "" : "not ", var.toString(cache).c_str(), WhyStr(var).c_str());
+      {
+	 std::ostringstream err;
+	 err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n";
+	 std::unordered_set<Var> seen;
+	 err << "1. " << LongWhyStr(var, state.decision == Decision::MUST, state.reason, "   ", seen).substr(3) << "\n";
+	 err << "2. " << LongWhyStr(var, decision, reason, "   ", seen).substr(3);
+	 return _error->Error("%s", err.str().c_str());
+      }
       return true;
    }
 
@@ -773,7 +946,7 @@ bool APT::Solver::AddWork(Work &&w)
 	 if (not Enqueue(var, false, w.clause))
 	    return false;
    }
-   else if (not w.clause->solutions.empty())
+   else
    {
       if (unlikely(debug >= 3 && w.clause->optional))
 	 std::cerr << "Enqueuing Recommends " << w.clause->toString(cache) << std::endl;
@@ -785,10 +958,6 @@ bool APT::Solver::AddWork(Work &&w)
       work.push_back(std::move(w));
       std::push_heap(work.begin(), work.end());
    }
-   else if (not w.clause->optional && w.clause->dep)
-      return _error->Error("Unsatisfiable dependency group %s -> %s", w.clause->reason.toString(cache).c_str(), pkgCache::DepIterator(cache, w.clause->dep).TargetPkg().FullName().c_str());
-   else if (not w.clause->optional)
-      return _error->Error("Unsatisfiable dependency group %s", w.clause->reason.toString(cache).c_str());
    return true;
 }
 
@@ -832,8 +1001,6 @@ bool APT::Solver::Solve()
       if (unlikely(debug >= 1))
 	 std::cerr << item.toString(cache) << std::endl;
 
-      assert(item.clause->solutions.size() > 1 || item.clause->optional);
-
       bool foundSolution = false;
       for (auto &sol : item.clause->solutions)
       {
@@ -857,15 +1024,13 @@ bool APT::Solver::Solve()
       }
       if (not foundSolution && not item.clause->optional)
       {
-	 std::ostringstream dep;
-	 assert(item.clause->solutions.size() > 0);
-	 for (auto &sol : item.clause->solutions)
-	    dep << (dep.tellp() == 0 ? "" : " | ") << sol.toString(cache);
-	 _error->Error("Unsatisfiable dependency: %s -> %s", WhyStr(item.clause->reason).c_str(), dep.str().c_str());
-	 for (auto &sol : item.clause->solutions)
-	    if ((*this)[sol].decision == Decision::MUSTNOT)
-	       _error->Error("Not considered: %s: %s", sol.toString(cache).c_str(),
-			     WhyStr(sol).c_str());
+	 std::ostringstream err;
+
+	 err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n";
+	 std::unordered_set<Var> seen;
+	 err << "1. " << LongWhyStr(item.clause->reason, true, (*this)[item.clause->reason].reason, "   ", seen).substr(3) << "\n";
+	 err << "2. " << LongWhyStr(item.clause->reason, false, item.clause, "   ", seen).substr(3);
+	 _error->Error("%s", err.str().c_str());
 	 if (not Pop())
 	    return false;
       }
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 519f48b13..9d4a195ec 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -84,6 +84,7 @@ class Solver
    struct Clause;
    struct Work;
    struct Solved;
+   friend struct std::hash<APT::Solver::Var>;
 
    // \brief Groups of works, these are ordered.
    //
@@ -290,6 +291,19 @@ class Solver
 
    // Print dependency chain
    std::string WhyStr(Var reason) const;
+
+   /**
+    * \brief Print a long reason string
+    *
+    * Print a reason as to why `rclause` implies `decision` for the variable `var`.
+    *
+    * \param var The variable to print the reason for
+    * \param decision The assumed decision to print the reason for (may be different from actual decision if rclause is specified)
+    * \param rclause The clause that caused this variable to be marked (or would be marked)
+    * \param prefix A prefix, for indentation purposes, as this is recursive
+    * \param seen A set of seen objects such that the output does not repeat itself (not for safety, it is acyclic)
+    */
+   std::string LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const;
 };
 
 }; // namespace APT
@@ -494,3 +508,11 @@ inline const APT::Solver::State &APT::Solver::operator[](Var r) const
 {
    return const_cast<Solver &>(*this)[r];
 }
+
+// Custom specialization of std::hash can be injected in namespace std.
+template <>
+struct std::hash<APT::Solver::Var>
+{
+   std::hash<decltype(APT::Solver::Var::value)> hash_value;
+   std::size_t operator()(const APT::Solver::Var &v) const noexcept { return hash_value(v.value); }
+};