Merge branch 'solver3' into 'main'

solver3: Use classical watchers and minor refactorings

See merge request apt-team/apt!548

12 files changed, 147 insertions, 117 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index a09c27f2a..e4449339e 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -123,8 +123,6 @@ std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty, bool sho
 std::string Solver::Work::toString(pkgCache &cache) const
 {
    std::ostringstream out;
-   if (erased)
-      out << "Erased ";
    if (clause->optional)
       out << "Optional ";
    out << "Item (" << ssize_t(size <= clause->solutions.size() ? size : -1) << "@" << level << ") ";
@@ -382,65 +380,77 @@ bool Solver::Propagate()
    {
       Var var = propQ.front();
       propQ.pop();
-      if (value(var) == LiftedBool::True)
+
+      // Stale propagation. These do not happen in MiniSat, because it clears the propQ on
+      // conflict, however, we simply keep the item in here and skip it.
+      if (value(var) == LiftedBool::Undefined)
+	 continue;
+
+      Lit lit = value(var) == LiftedBool::False ? ~var : var;
+      if (not lit.sign())
+	 Discover(lit.var());
+
+      for (auto clause : watches(lit))
       {
-	 Discover(var);
-	 for (auto &clause : (*this)[var].clauses)
-	    if (not AddWork(Work{clause.get(), decisionLevel()}))
-	       return false;
-	 for (auto rclause : (*this)[var].rclauses)
-	 {
-	    if (not rclause->negative || rclause->optional || rclause->reason.empty())
-	       continue;
-	    if (unlikely(debug >= 3))
-	       std::cerr << "Propagate " << var.toString(cache) << " to NOT " << rclause->reason.toString(cache) << " for dep " << const_cast<Clause *>(rclause)->toString(cache) << std::endl;
-	    if (not Enqueue(~rclause->reason, rclause))
-	       return false;
-	 }
+	 if (Propagate(clause, lit))
+	    continue;
+	 return false;
       }
-      else if (value(var) == LiftedBool::False)
-      {
-	 for (auto rclause : (*this)[var].rclauses)
-	 {
-	    if (rclause->negative || rclause->reason.empty())
-	       continue;
-	    if (value(rclause->reason) == LiftedBool::False)
-	       continue;
+   }
+   return true;
+}
 
-	    auto count = std::count_if(rclause->solutions.begin(), rclause->solutions.end(), [this](auto var)
-				       { return value(var) != LiftedBool::False; });
+bool Solver::Propagate(const Clause *clause, Lit p)
+{
+   if (debug >= 3)
+      std::cerr << "Propagate " << p.toString(cache) << " to " << clause->toString(cache) << std::endl;
+   // Negative clauses are trivial
+   if (clause->negative)
+   {
+      // One of the solutions was set, so reject the reason
+      if (p != clause->reason)
+	 return Enqueue(~clause->reason, clause);
 
-	    if (count == 1 && value(rclause->reason) == LiftedBool::True)
-	    {
-	       if (unlikely(debug >= 3))
-		  std::cerr << "Propagate NOT " << var.toString(cache) << " to unit clause " << rclause->toString(cache);
-	       if (rclause->optional)
-	       {
-		  // Enqueue duplicated item, this will ensure we see it at the correct time
-		  if (not AddWork(Work{rclause, decisionLevel()}))
-		     return false;
-	       }
-	       else
-	       {
-		  // Find the variable that must be chosen and enqueue it as a fact
-		  for (auto sol : rclause->solutions)
-		     if (value(sol) == LiftedBool::Undefined && not Enqueue(sol, rclause))
-			return false;
-	       }
-	       continue;
-	    }
-	    if (count >= 1 || rclause->optional)
-	       continue;
+      // Here we need to reject all conflicting solutions (reason -> none of solutions)
+      for (auto sol : clause->solutions)
+	 if (not Enqueue(~sol, clause))
+	    return false;
 
-	    if (unlikely(debug >= 3))
-	       std::cerr << "Propagate NOT " << var.toString(cache) << " to " << rclause->reason.toString(cache) << " for dep " << const_cast<Clause *>(rclause)->toString(cache) << std::endl;
+      return true;
+   }
 
-	    if (not Enqueue(~rclause->reason, rclause)) // Last version invalidated
-	       return false;
-	 }
+   // Check if the clause is unit, conflict, or undecided
+   Lit unit;
+   for (auto sol : clause->solutions)
+   {
+      if (value(sol) == LiftedBool::False)
+	 continue;
+      if (not unit.empty() || clause->optional)
+      {
+	 // We found a second solution, so we are undecided
+	 if (p == clause->reason)
+	    return AddWork(Work{clause, decisionLevel()});
+	 return true;
       }
+
+      unit = sol;
+   }
+
+   // The clause is now either unit or conflict
+   if (not unit.empty())
+   {
+      // Unit clause. If it is an active clause, enqueue the unit literal.
+      if (value(clause->reason) == LiftedBool::True)
+         return Enqueue(unit, clause);
+      return true;
+   }
+   else
+   {
+      // Conflict clause. If this clause is non-optional; reject it's "reason".
+      if (not clause->optional)
+	 return Enqueue(~clause->reason, clause);
+      return true;
    }
-   return true;
 }
 
 void Solver::UndoOne()
@@ -506,11 +516,9 @@ bool Solver::Pop()
       UndoOne();
 
    // We need to remove any work that is at a higher level.
-   // FIXME: We should just mark the entries as erased and only do a compaction
-   //        of the heap once we have a lot of erased entries in it.
    trailLim.pop_back();
    work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool
-			     { return w.level > decisionLevel() || w.erased; }),
+			     { return w.level > decisionLevel(); }),
 	      work.end());
    std::make_heap(work.begin(), work.end());
 
@@ -572,9 +580,6 @@ bool Solver::Solve()
       auto item = work.front();
       std::pop_heap(work.begin(), work.end());
       work.pop_back();
-      // This item has been replaced with a new one. Remove it.
-      if (item.erased)
-	 continue;
 
       if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver)
 		      { return value(ver) == LiftedBool::True; }))
@@ -598,6 +603,7 @@ bool Solver::Solve()
       }
       else
       {
+	 abort();
 	 if (unlikely(debug >= 1))
 	    std::cerr << item.toString(cache) << "\n";
 	 // Enqueue produces the right error message for us here, given that reason has been assigned true already...
@@ -859,8 +865,11 @@ const Clause *DependencySolver::RegisterClause(Clause &&clause)
 
    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());
+   // Insert all our watches
+   if (not inserted->reason.empty())
+      watches(inserted->reason).push_back(inserted.get());
+   for (auto sol : inserted->solutions)
+      watches(inserted->negative ? sol : ~sol).push_back(inserted.get());
    return inserted.get();
 }
 
@@ -885,7 +894,7 @@ bool DependencySolver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand)
       if (priority == 0 || priority < candPriority)
 	 continue;
 
-      pkgObsolete[pkg] = 2;
+      pkgObsolete[pkg] = LiftedBool::True;
       if (debug >= 3)
 	 std::cerr << "Obsolete: " << cand.ParentPkg().FullName() << "=" << cand.VerStr() << " due to " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "\n";
       return true;
@@ -898,8 +907,8 @@ bool DependencySolver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) con
 {
    if ((*this)[pkg].flags.manual && not AllowManual)
       return false;
-   if (pkgObsolete[pkg] != 0)
-      return pkgObsolete[pkg] == 2;
+   if (pkgObsolete[pkg] != LiftedBool::Undefined)
+      return pkgObsolete[pkg] == LiftedBool::True;
 
    auto ver = GetCandidateVer(pkg);
 
@@ -909,7 +918,7 @@ bool DependencySolver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) con
    {
       if (debug >= 3)
 	 std::cerr << "Obsolete: " << pkg.FullName() << " - not installable\n";
-      pkgObsolete[pkg] = 2;
+      pkgObsolete[pkg] = LiftedBool::True;
       return true;
    }
 
@@ -921,14 +930,14 @@ bool DependencySolver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) con
    {
       if (ver.Downloadable())
       {
-	 pkgObsolete[pkg] = 1;
+	 pkgObsolete[pkg] = LiftedBool::False;
 	 return false;
       }
    }
 
    if (debug >= 3)
       std::cerr << "Obsolete: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << " - not installable\n";
-   pkgObsolete[pkg] = 2;
+   pkgObsolete[pkg] = LiftedBool::True;
    return true;
 }
 void DependencySolver::Discover(Var var)
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 4a2b4ac8d..af1d749eb 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -200,6 +200,7 @@ struct Lit
    int32_t value;
 
    public:
+   constexpr Lit() : value{0} {}
    // SAFETY: value must be 31 bit, one bit is needed for the sign.
    constexpr Lit(Var var) : value{static_cast<int32_t>(var.value)} {}
 
@@ -328,6 +329,8 @@ class Solver
    inline State &operator[](Var r);
    inline const State &operator[](Var r) const;
 
+   inline std::vector<const Clause *> &watches(Lit lit);
+
    // \brief Heap of the remaining work.
    //
    // In contrast to MiniSAT which picks undecided literals and decides them,
@@ -364,6 +367,8 @@ class Solver
    virtual void Discover(Var var) = 0;
    // \brief Propagate all pending propagations
    [[nodiscard]] bool Propagate();
+   // \brief Propagate all pending propagations
+   [[nodiscard]] bool Propagate(const Clause *clause, Lit lit);
 
    // \brief Return the current level (.size() with casting)
    level_type decisionLevel()
@@ -442,7 +447,7 @@ class DependencySolver : public Solver
    bool KeepSuggests{_config->FindB("APT::AutoRemove::SuggestsImportant", true)};
 
    // Helper functions for detecting obsolete packages
-   mutable FastContiguousCacheMap<pkgCache::Package, char> pkgObsolete;
+   mutable FastContiguousCacheMap<pkgCache::Package, LiftedBool> pkgObsolete;
    bool Obsolete(pkgCache::PkgIterator pkg, bool AllowManual = false) const;
    bool ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const;
 
@@ -509,9 +514,6 @@ struct APT::Solver::Solver::Work
    /// Number of valid choices at insertion time
    size_t size{0};
 
-   // \brief This item should be removed from the queue.
-   bool erased{false};
-
    bool operator<(APT::Solver::Solver::Work const &b) const;
    std::string toString(pkgCache &cache) const;
    inline Work(const Clause *clause, level_type level) : clause(clause), level(level) {}
@@ -556,8 +558,8 @@ struct APT::Solver::Solver::State
 
    // \brief Clauses owned by this package/version
    std::vector<std::unique_ptr<Clause>> clauses;
-   // \brief Reverse clauses, that is dependencies (or conflicts) from other packages on this one
-   std::vector<const Clause *> rclauses;
+   // \brief Watches watching a clause by sign
+   std::vector<const Clause *> watches[2];
 };
 
 /**
@@ -609,3 +611,8 @@ struct std::hash<APT::Solver::Lit>
    std::hash<decltype(APT::Solver::Lit::value)> hash_value;
    std::size_t operator()(const APT::Solver::Lit &v) const noexcept { return hash_value(v.value); }
 };
+
+inline std::vector<const APT::Solver::Clause *> &APT::Solver::Solver::watches(Lit lit)
+{
+   return (*this)[lit.var()].watches[lit.sign()];
+}
diff --git a/test/integration/test-apt-get-install-deb b/test/integration/test-apt-get-install-deb
index cb423cd59..d1b6003ea 100755
--- a/test/integration/test-apt-get-install-deb
+++ b/test/integration/test-apt-get-install-deb
@@ -33,10 +33,10 @@ done
 buildsimplenativepackage 'foo' 'i386,amd64' '1.0'
 
 testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
-   1. foo:amd64 is not selected for install because:
-      1. foo:i386=1.0 is selected for install
-      2. foo:amd64 Conflicts foo:i386
-   2. foo:amd64=1.0 is selected for install" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0
+   1. foo:i386=1.0 is selected for install
+   2. foo:i386 is not selected for install because:
+      1. foo:amd64=1.0 is selected for install
+      2. foo:i386 Conflicts foo" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0
 testfailureequal "Reading package lists...
 Building dependency tree...
 Note, selecting 'foo:i386' instead of './incoming/foo_1.0_i386.deb'
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 8abc7c854..d829dc84e 100755
--- a/test/integration/test-bug-549968-install-depends-of-not-installed
+++ b/test/integration/test-bug-549968-install-depends-of-not-installed
@@ -37,7 +37,6 @@ Solving dependencies...Install coolstuff:i386 ()
 Delete extracoolstuff:i386
 [0] Reject:extracoolstuff:i386 ()
 [0] Install:coolstuff:i386 (coolstuff:i386=1.0)
-Optional Item (0@0) coolstuff:i386 ->  | extracoolstuff:i386
 
 Recommended packages:
   extracoolstuff
diff --git a/test/integration/test-bug-601961-install-info b/test/integration/test-bug-601961-install-info
index 712a9ba14..9ea5c7386 100755
--- a/test/integration/test-bug-601961-install-info
+++ b/test/integration/test-bug-601961-install-info
@@ -61,7 +61,7 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  findutils : Depends: essentialpkg but it is not going to be installed
 E: Unable to satisfy dependencies. Reached two conflicting assignments:
-   1. essentialpkg:i386 is selected for removal
-   2. essentialpkg:i386 is selected for install because:
-      1. findutils:i386 is selected for install
-      2. findutils:i386 Depends essentialpkg' aptget remove essentialpkg --trivial-only --solver 3.0
+   1. findutils:i386 is selected for install
+   2. findutils:i386 Depends essentialpkg
+      but none of the choices are installable:
+      - essentialpkg:i386 is selected for removal' aptget remove essentialpkg --trivial-only --solver 3.0
diff --git a/test/integration/test-bug-612557-garbage-upgrade b/test/integration/test-bug-612557-garbage-upgrade
index 9bc83cce4..f504abfcc 100755
--- a/test/integration/test-bug-612557-garbage-upgrade
+++ b/test/integration/test-bug-612557-garbage-upgrade
@@ -19,14 +19,15 @@ testmarkedauto python-uno openoffice.org-common
 
 # The 3.0 solver does not remove openoffice.org-emailmerge because it is manually installed.
 testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
-   1. openoffice.org-common:i386=1:3.2.1-11+squeeze2 is not selected for install because:
-      1. python-uno:i386=1:3.3.0-2 is selected as an upgrade
-      2. python-uno:i386=1:3.3.0-2 Depends libreoffice-common
-      3. libreoffice-common:i386 Conflicts openoffice.org-common
-   2. openoffice.org-common:i386=1:3.2.1-11+squeeze2 is selected for install because:
+   1. openoffice.org-common:i386 is selected for install because:
       1. openoffice.org-emailmerge:i386 is selected for install
       2. openoffice.org-emailmerge:i386 PreDepends openoffice.org-common
-      3. openoffice.org-common:i386 is available in version 1:3.2.1-11+squeeze2" aptget --trivial-only install python-uno --solver 3.0 -o APT::Solver::RemoveManual=false
+   2. openoffice.org-common:i386 is available in version 1:3.2.1-11+squeeze2
+      but none of the choices are installable:
+      - openoffice.org-common:i386=1:3.2.1-11+squeeze2 is not selected for install because:
+        1. python-uno:i386=1:3.3.0-2 is selected as an upgrade
+        2. python-uno:i386=1:3.3.0-2 Depends libreoffice-common
+        3. libreoffice-common:i386 Conflicts openoffice.org-common" aptget --trivial-only install python-uno --solver 3.0 -o APT::Solver::RemoveManual=false
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Reading state information...
diff --git a/test/integration/test-bug-675449-essential-are-protected b/test/integration/test-bug-675449-essential-are-protected
index d7e284ece..fb67f71aa 100755
--- a/test/integration/test-bug-675449-essential-are-protected
+++ b/test/integration/test-bug-675449-essential-are-protected
@@ -126,7 +126,7 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  foo : Depends: libfoo but it is not going to be installed
 E: Unable to satisfy dependencies. Reached two conflicting assignments:
-   1. libfoo:amd64 is selected for removal
-   2. libfoo:amd64 is selected for install because:
-      1. foo:amd64 is selected for install
-      2. foo:amd64 Depends libfoo' aptget purge libfoo -s --solver 3.0
+   1. foo:amd64 is selected for install
+   2. foo:amd64 Depends libfoo
+      but none of the choices are installable:
+      - libfoo:amd64 is selected for removal' aptget purge libfoo -s --solver 3.0
diff --git a/test/integration/test-bug-961266-hold-means-hold b/test/integration/test-bug-961266-hold-means-hold
index e95bb6ed6..fe678b0c9 100755
--- a/test/integration/test-bug-961266-hold-means-hold
+++ b/test/integration/test-bug-961266-hold-means-hold
@@ -90,15 +90,21 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
 E: Unable to satisfy dependencies. Reached two conflicting assignments:
-   1. git-ng:amd64=1:2.26.2-1 is selected for install
-   2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.)
+   1. git:i386=1:2.26.2-1 is selected for install because:
+      1. git-ng:amd64=1:2.26.2-1 is selected for install
+      2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.)
+         [selected git-ng:amd64]
+      For context, additional choices that could not be installed:
+      * In git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.):
+        - git:amd64=1:2.26.2-1 is not selected for install because:
+          1. git:amd64=1:2.25.1-1 is selected for install
+          2. git:amd64=1:2.26.2-1 conflicts with other versions of itself
+   2. git:i386=1:2.26.2-1 ->  | git:i386
       but none of the choices are installable:
-      - git:amd64=1:2.26.2-1 is not selected for install because:
-        1. git:amd64=1:2.25.1-1 is selected for install
-        2. git:amd64=1:2.25.1-1 conflicts with other versions of itself
-      - git:i386=1:2.26.2-1 is not selected for install because:
+      - git:i386 is not selected for install because:
         1. git:amd64=1:2.25.1-1 is selected for install as above
-        2. git:amd64 Conflicts git:i386' apt install git-ng -s --solver 3.0
+        2. git:i386 Conflicts git
+           [selected git:amd64=1:2.25.1-1]' apt install git-ng -s --solver 3.0
 
 
 msgmsg 'Now mix it up by' 'holding git-cvs'
diff --git a/test/integration/test-handling-broken-orgroups b/test/integration/test-handling-broken-orgroups
index 184c84377..9d7f3696e 100755
--- a/test/integration/test-handling-broken-orgroups
+++ b/test/integration/test-handling-broken-orgroups
@@ -100,10 +100,10 @@ Conf extrastuff (1.0-1 unstable [all])
 Conf coolstuff-provided (1.0-1 unstable [all])' aptget install coolstuff-provided -s
 
 testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
-   1. extrastuff:i386=1.0-1 is not selected for install
-   2. extrastuff:i386=1.0-1 is selected for install because:
-      1. coolstuff-provided-broken:i386=1.0-1 is selected for install
-      2. coolstuff-provided-broken:i386 Depends cool2 | stuff-abi-2' aptget install coolstuff-provided-broken --solver 3.0 -s
+   1. coolstuff-provided-broken:i386=1.0-1 is selected for install
+   2. coolstuff-provided-broken:i386 Depends cool2 | stuff-abi-2
+      but none of the choices are installable:
+      - extrastuff:i386=1.0-1 is not selected for install' aptget install coolstuff-provided-broken --solver 3.0 -s
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-prefer-higher-priority-providers b/test/integration/test-prefer-higher-priority-providers
index 07a0033b1..ff521b026 100755
--- a/test/integration/test-prefer-higher-priority-providers
+++ b/test/integration/test-prefer-higher-priority-providers
@@ -92,15 +92,17 @@ Conf baz (1 unstable [all])
 Conf awesome (1 unstable [all])" aptget install awesome foo- bar- -s
 
 testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
-   1. baz:$native is not selected for install
-   2. baz:$native=1 is selected for install because:
+   1. baz:$native=1 is selected for install because:
       1. awesome:$native=1 is selected for install
       2. awesome:$native Depends stuff
          [selected awesome:$native]
       For context, additional choices that could not be installed:
       * In awesome:$native Depends stuff:
         - foo:$native=1 is not selected for install
-        - bar:$native=1 is not selected for install" aptget install awesome foo- bar- baz- -s --solver 3.0
+        - bar:$native=1 is not selected for install
+   2. baz:$native=1 ->  | baz:$native
+      but none of the choices are installable:
+      - baz:$native is not selected for install" aptget install awesome foo- bar- baz- -s --solver 3.0
 testfailureequal "Reading package lists...
 Building dependency tree...
 Package 'foo' is not installed, so not removed
diff --git a/test/integration/test-release-candidate-switching b/test/integration/test-release-candidate-switching
index 16eb4f1ec..f7a1abcfe 100755
--- a/test/integration/test-release-candidate-switching
+++ b/test/integration/test-release-candidate-switching
@@ -449,10 +449,10 @@ The following packages have unmet dependencies:
  uninstallablepkg : Depends: libmtp8 (>= 10:0.20.1) but it is not going to be installed
                     Depends: amarok-utils (= 2.3.2-2+exp) but it is not going to be installed
 E: Unable to satisfy dependencies. Reached two conflicting assignments:
-   1. amarok-utils:i386=2.3.2-2+exp is not selected for install
-   2. amarok-utils:i386=2.3.2-2+exp is selected for install because:
-      1. uninstallablepkg:i386=1.0 is selected for install
-      2. uninstallablepkg:i386 Depends amarok-utils (= 2.3.2-2+exp)" aptget install uninstallablepkg/experimental --trivial-only -V --solver 3.0
+   1. uninstallablepkg:i386=1.0 is selected for install
+   2. uninstallablepkg:i386 Depends libmtp8 (>= 10:0.20.1)
+      but none of the choices are installable:
+      [no choices]" aptget install uninstallablepkg/experimental --trivial-only -V --solver 3.0
 
 insertinstalledpackage 'libmtp8' 'i386'  '1'
 insertinstalledpackage 'amarok' 'i386' '3' 'Depends: amarok-common (= 3), libmtp8 (>= 1)'
diff --git a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies
index 7e770a30d..3f100cb1f 100755
--- a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies
+++ b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies
@@ -97,15 +97,21 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
 E: Unable to satisfy dependencies. Reached two conflicting assignments:
-   1. git-ng:amd64=1:2.26.2-1 is selected for install
-   2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.)
+   1. git:i386=1:2.26.2-1 is selected for install because:
+      1. git-ng:amd64=1:2.26.2-1 is selected for install
+      2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.)
+         [selected git-ng:amd64]
+      For context, additional choices that could not be installed:
+      * In git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.):
+        - git:amd64=1:2.26.2-1 is not selected for install because:
+          1. git:amd64=1:2.25.1-1 is selected for install
+          2. git:amd64=1:2.26.2-1 conflicts with other versions of itself
+   2. git:i386=1:2.26.2-1 ->  | git:i386
       but none of the choices are installable:
-      - git:amd64=1:2.26.2-1 is not selected for install because:
-        1. git:amd64=1:2.25.1-1 is selected for install
-        2. git:amd64=1:2.25.1-1 conflicts with other versions of itself
-      - git:i386=1:2.26.2-1 is not selected for install because:
+      - git:i386 is not selected for install because:
         1. git:amd64=1:2.25.1-1 is selected for install as above
-        2. git:amd64 Conflicts git:i386' apt install git-ng -s
+        2. git:i386 Conflicts git
+           [selected git:amd64=1:2.25.1-1]' apt install git-ng -s
 
 
 msgmsg 'Now mix it up by' 'holding git-cvs'