Merge branch 'solver3' into 'main'

solver3: Unit propagation queues

See merge request apt-team/apt!440

2 files changed, 72 insertions, 57 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index da80222e8..6f445328c 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -187,8 +187,13 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
       return not b.optional && b.size < 2;
    if (group != b.group)
       return group > b.group;
-   if (optional && b.optional && reason.empty() != b.reason.empty())
-      return reason.empty();
+   if (optional && b.optional)
+   {
+      if ((size < 2) != (b.size < 2))
+	 return b.size < 2;
+      if (reason.empty() != b.reason.empty())
+	 return reason.empty();
+   }
    // An optional item is less important than a required one.
    if (optional != b.optional)
       return optional;
@@ -337,60 +342,25 @@ bool APT::Solver::Enqueue(Var var, bool decision, Var reason)
       std::cerr << "[" << depth() << "] " << (decision ? "Install" : "Reject") << ":" << var.toString(cache) << " (" << WhyStr(state.reason) << ")\n";
 
    solved.push_back(Solved{var, std::nullopt});
+   propQ.push(var);
 
    if (not decision)
-   {
-      if (not PropagateReject(var))
-	 return false;
       needsRescore = true;
-   }
-   else
-   {
-      if (not PropagateInstall(var))
-	 return false;
-   }
+
    return true;
 }
 
-bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Var reason, Group group)
+bool APT::Solver::Propagate()
 {
-   if ((*this)[Pkg].decision == Decision::MUST)
-      return true;
-
-   // Note decision
-   if (not Enqueue(Var(Pkg), true, reason))
-      return false;
-
-   bool anyInstallable = false;
-   // Insert the work item.
-   Work workItem{Var(Pkg), depth(), group};
-   for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
-   {
-      workItem.solutions.push_back(ver);
-      if ((*this)[ver].decision != Decision::MUSTNOT)
-	 anyInstallable = true;
-   }
-
-   if (not anyInstallable)
+   while (!propQ.empty())
    {
-      _error->Error("Conflict: %s -> %s but no versions are installable",
-		    WhyStr(reason).c_str(), Pkg.FullName().c_str());
-      for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
-	 _error->Error("Uninstallable version: %s", WhyStr(Var(ver)).c_str());
-      return false;
+      Var var = propQ.front();
+      propQ.pop();
+      if ((*this)[var].decision == Decision::MUST && not PropagateInstall(var))
+	 return false;
+      else if ((*this)[var].decision == Decision::MUSTNOT && not PropagateReject(var))
+	 return false;
    }
-
-   std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg, *this});
-   assert(workItem.solutions.size() > 0);
-
-   if (workItem.solutions.size() > 1 || workItem.optional)
-      AddWork(std::move(workItem));
-   else if (not Enqueue(Var(pkgCache::VerIterator(cache, workItem.solutions[0])), true, workItem.reason))
-      return false;
-
-   if (not EnqueueCommonDependencies(Pkg))
-      return false;
-
    return true;
 }
 
@@ -398,6 +368,40 @@ bool APT::Solver::PropagateInstall(Var var)
 {
    if (auto Pkg = var.Pkg(cache); not Pkg.end())
    {
+      bool anyInstallable = false;
+      bool anyMust = false;
+      // Insert the work item.
+      Work workItem{Var(Pkg), depth(), Group::SelectVersion};
+      for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+      {
+	 workItem.solutions.push_back(ver);
+	 if ((*this)[ver].decision != Decision::MUSTNOT)
+	    anyInstallable = true;
+	 if ((*this)[ver].decision == Decision::MUST)
+	    anyMust = true;
+      }
+
+      if (not anyInstallable)
+      {
+	 _error->Error("Conflict: %s -> %s but no versions are installable",
+		       WhyStr((*this)[Pkg].reason).c_str(), Pkg.FullName().c_str());
+	 for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+	    _error->Error("Uninstallable version: %s", WhyStr(Var(ver)).c_str());
+	 return false;
+      }
+
+      std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg, *this});
+      assert(workItem.solutions.size() > 0);
+
+      if (workItem.solutions.size() > 1 || workItem.optional)
+	 AddWork(std::move(workItem));
+      else if (not Enqueue(Var(pkgCache::VerIterator(cache, workItem.solutions[0])), true, workItem.reason))
+	 return false;
+
+      // FIXME: We skip enqueuing duplicate common dependencies if we already selected a version, but
+      // we should not have common dependencies duplicated in the version objects anyway.
+      if (not anyMust && not EnqueueCommonDependencies(Pkg))
+	 return false;
    }
    else if (auto Ver = var.Ver(cache); not Ver.end())
    {
@@ -598,8 +602,6 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera
 	 return true;
       }
    }
-   else if (workItem.optional && start.ParentPkg()->CurrentVer == 0)
-      workItem.group = Group::NewUnsatRecommends;
 
    if (not workItem.solutions.empty())
    {
@@ -827,8 +829,17 @@ void APT::Solver::RescoreWorkIfNeeded()
 
 bool APT::Solver::Solve()
 {
-   while (not work.empty())
+   while (true)
    {
+      while (not Propagate())
+      {
+	 if (not Pop())
+	    return false;
+      }
+
+      if (work.empty())
+	 break;
+
       // Rescore the work if we need to
       RescoreWorkIfNeeded();
       // *NOW* we can pop the item.
@@ -894,7 +905,7 @@ bool APT::Solver::Solve()
 	 }
 	 if (unlikely(debug >= 3))
 	    std::cerr << "(try it: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n";
-	 if (not Enqueue(Var(pkgCache::VerIterator(cache, ver)), true, item.reason) && not Pop())
+	 if (not Enqueue(Var(ver), true, item.reason) && not Pop())
 	    return false;
 	 foundSolution = true;
 	 break;
@@ -984,7 +995,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 if (not isOptional)
 	 {
 	    // Pre-empt the non-optional requests, as we don't want to queue them, we can just "unit propagate" here.
-	    if (depcache[P].Keep() ? not Install(P, {}, Group) : not Enqueue(Var(depcache.GetCandidateVersion(P)), true, {}))
+	    if (depcache[P].Keep() ? not Enqueue(Var(P), true, {}) : not Enqueue(Var(depcache.GetCandidateVersion(P)), true, {}))
 	       return false;
 	 }
 	 else
@@ -998,7 +1009,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
       }
    }
 
-   return true;
+   return Propagate();
 }
 
 bool APT::Solver::ToDepCache(pkgDepCache &depcache)
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index a643d5d07..4f6f83d15 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -46,7 +46,6 @@ class Solver
    enum class Group : uint8_t
    {
       HoldOrDelete,
-      NewUnsatRecommends,
 
       // Satisfying dependencies on entirely new packages first is a good idea because
       // it may contain replacement packages like libfoo1t64 whereas we later will see
@@ -57,6 +56,9 @@ class Solver
       // try it last.
       SatisfyObsolete,
 
+      // Select a version of a package chosen for install.
+      SelectVersion,
+
       // My intuition tells me that we should try to schedule upgrades first, then
       // any non-obsolete installed packages, and only finally obsolete ones, such
       // that newer packages guide resolution of dependencies for older ones, they
@@ -130,6 +132,9 @@ class Solver
    // queue to be concerned about
    std::vector<Solved> solved{};
 
+   // \brief Propagation queue
+   std::queue<Var> propQ;
+
    // \brief Current decision level.
    //
    // This is an index into the solved vector.
@@ -153,6 +158,8 @@ class Solver
    bool RejectReverseDependencies(pkgCache::VerIterator Ver);
    // \brief Enqueue a single or group
    bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason);
+   // \brief Propagate all pending propagations
+   bool Propagate();
    // \brief Propagate a "true" value of a variable
    bool PropagateInstall(Var var);
    // \brief Propagate a rejection of a variable
@@ -184,9 +191,6 @@ class Solver
    // Enqueue a decision fact
    bool Enqueue(Var var, bool decision, Var reason);
 
-   // \brief Mark the package for install. This is annoying as it incurs a decision
-   bool Install(pkgCache::PkgIterator Pkg, Var reason, Group group);
-
    // \brief Apply the selections from the dep cache to the solver
    bool FromDepCache(pkgDepCache &depcache);
    // \brief Apply the solver result to the depCache