Merge branch 'solver3' into 'main'

solver3: Verbose error messages and some bugfixes

See merge request apt-team/apt!457

2 files changed, 253 insertions, 54 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index c1a1098b5..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.
@@ -231,16 +232,31 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
    return false;
 }
 
-std::string APT::Solver::Clause::toString(pkgCache &cache) const
+std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty) const
 {
    std::string out;
-   if (auto Pkg = reason.Pkg(cache); not Pkg.end())
-      out.append(Pkg.FullName());
-   if (auto Ver = reason.Ver(cache); not Ver.end())
-      out.append(Ver.ParentPkg().FullName()).append("=").append(Ver.VerStr());
-   out.append(" -> ");
-   for (auto var : solutions)
-      out.append(" | ").append(var.toString(cache));
+   out.append(reason.toString(cache));
+   if (dep && pretty)
+   {
+      out.append(" ").append(pkgCache::DepIterator(cache, dep).DepType()).append(" ");
+      for (auto dep = pkgCache::DepIterator(cache, this->dep); not dep.end(); ++dep)
+      {
+	 out.append(dep.TargetPkg().FullName(true));
+	 if (dep.TargetVer())
+	    out.append(" (").append(dep.CompType()).append(" ").append(dep.TargetVer()).append(")");
+	 if (!(dep->CompareOp & pkgCache::Dep::Or))
+	    break;
+	 out.append(" | ");
+      }
+   }
+   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;
 }
 
@@ -262,8 +278,12 @@ inline APT::Solver::Var APT::Solver::bestReason(APT::Solver::Clause const *claus
       return Var{};
    if (clause->reason == var)
       for (auto choice : clause->solutions)
-	 if ((*this)[choice].decision != Decision::NONE)
+      {
+	 if (clause->negative && (*this)[choice].decision == Decision::MUST)
+	    return choice;
+	 if (not clause->negative && (*this)[choice].decision == Decision::MUSTNOT)
 	    return choice;
+      }
    return clause->reason;
 }
 
@@ -288,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.
@@ -360,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;
    }
 
@@ -444,13 +632,14 @@ bool APT::Solver::Propagate()
    return true;
 }
 
-void APT::Solver::RegisterClause(Clause &&clause)
+const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
 {
    auto &clauses = (*this)[clause.reason].clauses;
    clauses.push_back(std::make_unique<Clause>(std::move(clause)));
    auto const &inserted = clauses.back();
    for (auto var : inserted->solutions)
       (*this)[var].rclauses.push_back(inserted.get());
+   return inserted.get();
 }
 
 void APT::Solver::Discover(Var var)
@@ -757,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;
@@ -769,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;
 }
 
@@ -816,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)
       {
@@ -841,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;
       }
@@ -931,8 +1112,8 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 {
 	    Clause w{Var(), Group, isOptional};
 	    w.solutions.push_back(Var(P));
-	    RegisterClause(std::move(w));
-	    if (not AddWork(Work{rootState->clauses.back().get(), depth()}))
+	    auto insertedW = RegisterClause(std::move(w));
+	    if (not AddWork(Work{insertedW, depth()}))
 	       return false;
 
 	    // Given A->A2|A1, B->B1|B2; Bn->An, if we select `not A1`, we
@@ -944,8 +1125,8 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	    for (auto V = P.VersionList(); not V.end(); ++V)
 	       shortcircuit.solutions.push_back(Var(V));
 	    std::stable_sort(shortcircuit.solutions.begin(), shortcircuit.solutions.end(), CompareProviders3{cache, policy, P, *this});
-	    RegisterClause(std::move(shortcircuit));
-	    if (not AddWork(Work{rootState->clauses.back().get(), depth()}))
+	    auto insertedShort = RegisterClause(std::move(shortcircuit));
+	    if (not AddWork(Work{insertedShort, depth()}))
 	       return false;
 
 	    // Discovery here is needed so the shortcircuit clause can actually become unit.
@@ -963,8 +1144,8 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this});
 	 if (unlikely(debug >= 1))
 	    std::cerr << "Install essential package " << P << std::endl;
-	 RegisterClause(std::move(w));
-	 if (not AddWork(Work{rootState->clauses.back().get(), depth()}))
+	 auto inserted = RegisterClause(std::move(w));
+	 if (not AddWork(Work{inserted, depth()}))
 	    return false;
       }
    }
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 0ad0800ba..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.
    //
@@ -246,7 +247,7 @@ class Solver
    // utilizing the discoverQ above.
    void Discover(Var var);
    // \brief Link a clause into the watchers
-   void RegisterClause(Clause &&clause);
+   const Clause *RegisterClause(Clause &&clause);
    // \brief Enqueue dependencies shared by all versions of the package.
    void RegisterCommonDependencies(pkgCache::PkgIterator Pkg);
 
@@ -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
@@ -304,48 +318,44 @@ class Solver
  */
 struct APT::Solver::Var
 {
-   uint32_t IsVersion : 1;
-   uint32_t MapPtr : 31;
+   uint32_t value;
+
+   explicit constexpr Var(uint32_t value = 0) : value{value} {}
+   explicit Var(pkgCache::PkgIterator const &Pkg) : value(uint32_t(Pkg.MapPointer()) << 1) {}
+   explicit Var(pkgCache::VerIterator const &Ver) : value(uint32_t(Ver.MapPointer()) << 1 | 1) {}
 
-   Var() : IsVersion(0), MapPtr(0) {}
-   explicit Var(pkgCache::PkgIterator const &Pkg) : IsVersion(0), MapPtr(Pkg.MapPointer()) {}
-   explicit Var(pkgCache::VerIterator const &Ver) : IsVersion(1), MapPtr(Ver.MapPointer()) {}
+   inline constexpr bool isVersion() const { return value & 1; }
+   inline constexpr uint32_t mapPtr() const { return value >> 1; }
 
    // \brief Return the package, if any, otherwise 0.
    map_pointer<pkgCache::Package> Pkg() const
    {
-      return IsVersion ? 0 : map_pointer<pkgCache::Package>{(uint32_t)MapPtr};
+      return isVersion() ? 0 : map_pointer<pkgCache::Package>{mapPtr()};
    }
    // \brief Return the version, if any, otherwise 0.
    map_pointer<pkgCache::Version> Ver() const
    {
-      return IsVersion ? map_pointer<pkgCache::Version>{(uint32_t)MapPtr} : 0;
+      return isVersion() ? map_pointer<pkgCache::Version>{mapPtr()} : 0;
    }
    // \brief Return the package iterator if storing a package, or an empty one
    pkgCache::PkgIterator Pkg(pkgCache &cache) const
    {
-      return IsVersion ? pkgCache::PkgIterator() : pkgCache::PkgIterator(cache, cache.PkgP + Pkg());
+      return isVersion() ? pkgCache::PkgIterator() : pkgCache::PkgIterator(cache, cache.PkgP + Pkg());
    }
    // \brief Return the version iterator if storing a package, or an empty end.
    pkgCache::VerIterator Ver(pkgCache &cache) const
    {
-      return IsVersion ? pkgCache::VerIterator(cache, cache.VerP + Ver()) : pkgCache::VerIterator();
+      return isVersion() ? pkgCache::VerIterator(cache, cache.VerP + Ver()) : pkgCache::VerIterator();
    }
    // \brief Return a package, cast from version if needed
    pkgCache::PkgIterator CastPkg(pkgCache &cache) const
    {
-      assert(MapPtr != 0);
-      return IsVersion ? Ver(cache).ParentPkg() : Pkg(cache);
+      return isVersion() ? Ver(cache).ParentPkg() : Pkg(cache);
    }
    // \brief Check if there is no reason.
-   bool empty() const
-   {
-      return IsVersion == 0 && MapPtr == 0;
-   }
-   bool operator==(Var const other) const
-   {
-      return IsVersion == other.IsVersion && MapPtr == other.MapPtr;
-   }
+   constexpr bool empty() const { return value == 0; }
+   constexpr bool operator!=(Var const other) const { return value != other.value; }
+   constexpr bool operator==(Var const other) const { return value == other.value; }
 
    std::string toString(pkgCache &cache) const
    {
@@ -381,7 +391,7 @@ struct APT::Solver::Clause
 
    inline Clause(Var reason, Group group, bool optional = false, bool negative = false) : reason(reason), group(group), optional(optional), negative(negative) {}
 
-   std::string toString(pkgCache &cache) const;
+   std::string toString(pkgCache &cache, bool pretty = false) const;
 };
 
 /**
@@ -498,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); }
+};