solver3: Replace PropagateInstall() with Discover()

Just propagate the stored clauses after we have discovered them;
this is quite straightforward. We now more reliably discover common
dependencies at the package level, adjust the test case accordingly.

The next step is to make discovery recursive, or iterative, to build
an entire recursive tree from all roots, and then we can reject reverse
dependencies based on it.

A bunch of refactorings are needed in the process. We remove the
useless Hint enumeration and insert a flags struct into the State,
such that we can record whether a package/version has been
discovered, to avoid spending double time on discovery.

3 files changed, 84 insertions, 93 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index 5909bb55e..09ba920fa 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -196,7 +196,6 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy)
       priorities(cache.Head().VersionCount),
       candidates(cache.Head().PackageCount)
 {
-   static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int));
    static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer<pkgCache::Package>));
    static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer<pkgCache::Version>));
 }
@@ -356,61 +355,59 @@ bool APT::Solver::Propagate()
    {
       Var var = propQ.front();
       propQ.pop();
-      if ((*this)[var].decision == Decision::MUST && not PropagateInstall(var))
-	 return false;
+      if ((*this)[var].decision == Decision::MUST)
+      {
+	 Discover(var);
+	 for (auto &clause : (*this)[var].clauses)
+	    if (not AddWork(Work{*clause.get(), depth()}))
+	       return false;
+      }
       else if ((*this)[var].decision == Decision::MUSTNOT && not PropagateReject(var))
 	 return false;
    }
    return true;
 }
 
-bool APT::Solver::PropagateInstall(Var var)
+void APT::Solver::RegisterClause(Clause &&clause)
 {
+   auto &clauses = (*this)[clause.reason].clauses;
+   clauses.push_back(std::make_unique<Clause>(std::move(clause)));
+}
+
+void APT::Solver::Discover(Var var)
+{
+   auto &state = (*this)[var];
+
+   if (state.flags.discovered)
+      return;
+
+   state.flags.discovered = true;
+
    if (auto Pkg = var.Pkg(cache); not Pkg.end())
    {
-      bool anyInstallable = false;
-      bool anyMust = false;
-      // Insert the work item.
       Clause clause{Var(Pkg), Group::SelectVersion};
       for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
-      {
 	 clause.solutions.push_back(Var(ver));
-	 if ((*this)[ver].decision != Decision::MUSTNOT)
-	    anyInstallable = true;
-	 if ((*this)[ver].decision == Decision::MUST)
-	    anyMust = true;
-      }
-
-      // One is already marked for install, nothing to propagate
-      if (anyMust)
-	 return 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(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, Pkg, *this});
-      assert(clause.solutions.size() > 0);
+      RegisterClause(std::move(clause));
 
-      if (not AddWork(Work{clause, depth()}))
-	 return false;
-
-      return EnqueueCommonDependencies(Pkg);
+      RegisterCommonDependencies(Pkg);
    }
    else if (auto Ver = var.Ver(cache); not Ver.end())
    {
-      if (not Enqueue(Var(Ver.ParentPkg()), true, Var(Ver)))
-	 return false;
+      Clause clause{Var(Ver), Group::SelectVersion};
+      clause.solutions = {Var(Ver.ParentPkg())};
+      RegisterClause(std::move(clause));
 
       for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV)
       {
-	 if (OV != Ver && not Enqueue(Var(OV), false, Var(Ver)))
-	    return false;
+	 if (OV == Ver)
+	    continue;
+
+	 Clause clause{Var(Ver), Group::SelectVersion, false, true /* negative */};
+	 clause.solutions = {Var(OV)};
+	 RegisterClause(std::move(clause));
       }
 
       for (auto dep = Ver.DependsList(); not dep.end();)
@@ -420,12 +417,11 @@ bool APT::Solver::PropagateInstall(Var var)
 	 pkgCache::DepIterator end;
 	 dep.GlobOr(start, end); // advances dep
 
-	 if (not EnqueueOrGroup(start, end, Var(Ver)))
-	    return false;
+	 auto clause = TranslateOrGroup(start, end, Var(Ver));
+
+	 RegisterClause(std::move(clause));
       }
    }
-
-   return true;
 }
 
 bool APT::Solver::PropagateReject(Var var)
@@ -465,7 +461,7 @@ bool APT::Solver::PropagateReject(Var var)
    return true;
 }
 
-bool APT::Solver::EnqueueCommonDependencies(pkgCache::PkgIterator Pkg)
+void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg)
 {
    for (auto dep = Pkg.VersionList().DependsList(); not dep.end();)
    {
@@ -484,36 +480,9 @@ bool APT::Solver::EnqueueCommonDependencies(pkgCache::PkgIterator Pkg)
       }
       if (not allHaveDep)
 	 continue;
-      if (not EnqueueOrGroup(start, end, Var(Pkg)))
-	 return false;
+      auto clause = TranslateOrGroup(start, end, Var(Pkg));
+      RegisterClause(std::move(clause));
    }
-
-   return true;
-}
-
-bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason)
-{
-   auto clause = TranslateOrGroup(start, end, reason);
-   if (clause.negative)
-   {
-      for (auto var : clause.solutions)
-	 if (not Enqueue(var, false, clause.reason))
-	    return false;
-   }
-   else if (not clause.solutions.empty())
-   {
-      if (unlikely(debug >= 3 && clause.optional))
-      {
-	 std::cerr << "Enqueuing Recommends ";
-	 clause.Dump(cache);
-	 std::cerr << "\n";
-      }
-      return AddWork(Work{std::move(clause), depth()});
-   }
-   else if (not clause.optional)
-      return _error->Error("Unsatisfiable dependency group %s -> %s", reason.toString(cache).c_str(), start.TargetPkg().FullName().c_str());
-
-   return true;
 }
 
 APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason)
@@ -533,6 +502,8 @@ APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, p
 
    Clause clause{reason, Group::Satisfy, not start.IsCritical() /* optional */, start.IsNegative()};
 
+   clause.dep = start;
+
    do
    {
       auto begin = clause.solutions.size();
@@ -779,13 +750,32 @@ bool APT::Solver::Pop()
 
 bool APT::Solver::AddWork(Work &&w)
 {
-   if (w.clause.solutions.size() == 1 && not w.clause.optional)
-      return Enqueue(w.clause.solutions[0], true, w.clause.reason);
+   if (w.clause.negative)
+   {
+      for (auto var : w.clause.solutions)
+	 if (not Enqueue(var, false, w.clause.reason))
+	    return false;
+   }
+   else if (not w.clause.solutions.empty())
+   {
+      if (unlikely(debug >= 3 && w.clause.optional))
+      {
+	 std::cerr << "Enqueuing Recommends ";
+	 w.clause.Dump(cache);
+	 std::cerr << "\n";
+      }
+      if (w.clause.solutions.size() == 1 && not w.clause.optional)
+	 return Enqueue(w.clause.solutions[0], true, w.clause.reason);
 
-   w.size = std::count_if(w.clause.solutions.begin(), w.clause.solutions.end(), [this](auto V)
-			  { return (*this)[V].decision != Decision::MUSTNOT; });
-   work.push_back(std::move(w));
-   std::push_heap(work.begin(), work.end());
+      w.size = std::count_if(w.clause.solutions.begin(), w.clause.solutions.end(), [this](auto V)
+			     { return (*this)[V].decision != Decision::MUSTNOT; });
+      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;
 }
 
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 42cde96f5..118ea5e28 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -174,18 +174,19 @@ class Solver
    // \brief If set, we install missing recommends and pick new best packages.
    bool FixPolicyBroken{_config->FindB("APT::Get::Fix-Policy-Broken")};
 
+   // \brief Discover a variable, translating the underlying dependencies to the SAT presentation
+   void Discover(Var var);
+   // \brief Link a clause into the watchers
+   void RegisterClause(Clause &&clause);
    // \brief Enqueue dependencies shared by all versions of the package.
-   [[nodiscard]] bool EnqueueCommonDependencies(pkgCache::PkgIterator Pkg);
+   void RegisterCommonDependencies(pkgCache::PkgIterator Pkg);
+
    // \brief Reject reverse dependencies. Must call std::make_heap() after.
    [[nodiscard]] bool RejectReverseDependencies(pkgCache::VerIterator Ver);
    // \brief Translate an or group into a clause object
    [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason);
-   // \brief Enqueue a single or group
-   [[nodiscard]] bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason);
    // \brief Propagate all pending propagations
    [[nodiscard]] bool Propagate();
-   // \brief Propagate a "true" value of a variable
-   [[nodiscard]] bool PropagateInstall(Var var);
    // \brief Propagate a rejection of a variable
    [[nodiscard]] bool PropagateReject(Var var);
 
@@ -300,6 +301,8 @@ struct APT::Solver::Var
  */
 struct APT::Solver::Clause
 {
+   // \brief Underyling dependency
+   pkgCache::Dependency *dep = nullptr;
    // \brief Var for the work
    Var reason;
    // \brief The group we are in
@@ -365,17 +368,6 @@ enum class APT::Solver::Decision : uint16_t
    MUSTNOT,
 };
 
-// \brief Hints for the solver about the item.
-enum class APT::Solver::Hint : uint16_t
-{
-   // \brief We have not made a choice about the package yet
-   NONE,
-   // \brief This package was listed as a Recommends of a must package,
-   SHOULD,
-   // \brief This package was listed as a Suggests of a must-not package
-   MAY,
-};
-
 /**
  * \brief The solver state
  *
@@ -403,8 +395,16 @@ struct APT::Solver::State
    // \brief This essentially describes the install state in RFC2119 terms.
    Decision decision{Decision::NONE};
 
-   // \brief Any hint.
-   Hint hint{Hint::NONE};
+   // \brief Flags.
+   struct
+   {
+      bool discovered{};
+   } flags;
+
+   static_assert(sizeof(flags) <= sizeof(int));
+
+   // \brief Clauses owned by this package/version
+   std::vector<std::unique_ptr<Clause>> clauses;
 };
 
 /**
diff --git a/test/integration/test-bug-549968-install-depends-of-not-installed b/test/integration/test-bug-549968-install-depends-of-not-installed
index 33cbd6ee4..ec730c7b2 100755
--- a/test/integration/test-bug-549968-install-depends-of-not-installed
+++ b/test/integration/test-bug-549968-install-depends-of-not-installed
@@ -38,6 +38,7 @@ Delete extracoolstuff:i386
 [0] Reject:extracoolstuff:i386 ()
 [0] Install:coolstuff:i386 (coolstuff:i386=1.0)
 [0] Reject:extracoolstuff:i386=1.0 (not extracoolstuff:i386)
+Optional Item (0@0) coolstuff:i386 ->  | extracoolstuff:i386=1.0
 Optional Item (0@0) coolstuff:i386=1.0 ->  | extracoolstuff:i386=1.0
 
 Recommended packages: