solver3: Use a package clause for optional roots

Instead of iterating over the version here and picking it, just
enqueue the package as well, which should allow us to select the
version at a later time.

This also causes a funny inverse problem now, though, as was evidenced
in one of the test cases: To summarize, if our optional roots are all
single items, they will be considered soft-unit, causing them to be
processed in order.

However it can be that an optional root has a specific version
selected because another version was rejected. Consider

    X Conflicts A (= 1)
    A, B have 2 versions: '2' available, '1' installed
    B (= n) Depends A (= n)

Run `apt install X`. The expected result is for A and B to be
upgraded to version 2. With only a package root, if B appears
in the cache before A however, we will get:

    Install X
        Reject A (= 1)
    Install B
        Install B (= 1)     # keep it installed
            Reject A (= 2)
    => A is being removed as both versions are rejected

Hence we do also need to re-introduce the additional version
clause, now we get:

    Install X
        Reject A (= 1)
    Install A (= 2)         # it got "promoted" to a 'stronger' soft-unit
    Install B
        Fail B (= 1)        # keep it installed
        Install B (= 2)

Introduce a root state to hold all the clauses that don't have
another owner.

moo

2 files changed, 23 insertions, 6 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index 01d93a6e3..4ebc085a5 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -197,6 +197,7 @@ class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc
 APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy)
     : cache(cache),
       policy(policy),
+      rootState(new State),
       pkgStates(cache.Head().PackageCount),
       verStates(cache.Head().VersionCount),
       pkgObsolete(cache.Head().PackageCount),
@@ -205,6 +206,8 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy)
 {
    static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer<pkgCache::Package>));
    static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer<pkgCache::Version>));
+   // Root state is "true".
+   rootState->decision = Decision::MUST;
 }
 
 // This function determines if a work item is less important than another.
@@ -218,7 +221,8 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
       return clause.group > b.clause.group;
    if ((size < 2) != (b.size < 2))
       return b.size < 2;
-
+   if (size == 1 && b.size == 1) // Special case: 'shortcircuit' optional packages
+      return clause->solutions.size() < b.clause->solutions.size();
    return false;
 }
 
@@ -966,10 +970,22 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 else
 	 {
 	    Clause w{Var(), Group, isOptional};
+	    w.solutions.push_back(Var(P));
+	    RegisterClause(std::move(w));
+	    if (not AddWork(Work{*rootState->clauses.back(), depth()}))
+	       return false;
+
+	    // Given A->A2|A1, B->B1|B2; Bn->An, if we select `not A1`, we
+	    // should try to install A2 before trying B so we end up with
+	    // A2, B2, instead of removing A1 to keep B1 installed. This
+	    // requires some special casing in Work::operator< above.
+	    // Compare test-bug-712116-dpkg-pre-install-pkgs-hook-multiarch
+	    Clause shortcircuit{Var(), Group, isOptional};
 	    for (auto V = P.VersionList(); not V.end(); ++V)
-	       w.solutions.push_back(Var(V));
-	    std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this});
-	    if (not AddWork(Work{std::move(w), depth()}))
+	       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()}))
 	       return false;
 	 }
       }
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index fc68a5cef..d3e22eaba 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -93,6 +93,8 @@ class Solver
    pkgCache &cache;
    // Policy is needed for determining candidate version.
    pkgDepCache::Policy &policy;
+   // Root state
+   std::unique_ptr<State> rootState;
    // States for packages
    std::vector<State> pkgStates{};
    // States for versions
@@ -425,6 +427,5 @@ inline APT::Solver::State &APT::Solver::operator[](Var r)
       return (*this)[cache.PkgP + P];
    if (auto V = r.Ver())
       return (*this)[cache.VerP + V];
-
-   abort();
+   return *rootState.get();
 }