summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--apt-pkg/solver3.cc122
-rw-r--r--apt-pkg/solver3.h14
-rwxr-xr-xtest/integration/test-apt-get-install-deb8
-rwxr-xr-xtest/integration/test-bug-549968-install-depends-of-not-installed1
-rwxr-xr-xtest/integration/test-bug-601961-install-info8
-rwxr-xr-xtest/integration/test-bug-612557-garbage-upgrade13
-rwxr-xr-xtest/integration/test-bug-675449-essential-are-protected8
-rwxr-xr-xtest/integration/test-bug-961266-hold-means-hold20
-rwxr-xr-xtest/integration/test-handling-broken-orgroups8
-rwxr-xr-xtest/integration/test-prefer-higher-priority-providers8
-rwxr-xr-xtest/integration/test-release-candidate-switching8
-rwxr-xr-xtest/integration/test-ubuntu-bug-2111792-intersecting-dependencies20
12 files changed, 139 insertions, 99 deletions
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index cbe318ac7..e4449339e 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -380,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()
@@ -591,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...
@@ -852,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();
}
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index a3ec859bb..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()
@@ -553,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];
};
/**
@@ -606,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'
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-07-18 01:42:04 +0000