Re: [UPLOADED] RFC: The Future of Solving Dependency Problems in APT (SAT, CUDF)
On Do, 2010-12-23 at 18:50 +0100, Julian Andres Klode wrote:
> On Mi, 2010-12-22 at 18:32 +0100, Julian Andres Klode wrote:
> > If there are no objections, I will create a new branch, and implement a
> > SatSolver using picosat therein (as that's fairly easy and produces good
> > results). I would also like to create the CudfSolver, but I'd need a
> > solver to test with. If anyone knows such solvers, please write.
>
> I pushed the branch to bzr+ssh://bzr.debian.org/bzr/apt/apt/solver/, and
> uploaded 0.8.10+expnewsolvers1 to experimental. It uses the SAT solver
> for install, remove, upgrade, dist-upgrade, but it can currently not
> handle unsatisfiable upgrades correctly (that is, it currently does not
> hold an upgrade back if it is impossible) - use with caution. And it may
> destroy detection of automatically installed packages.
I am using this version on my main system, and that's helpful in
measuring the quality of standard tasks, where it performed almost as
good as aptitude and on the average, better than standard APT. On
non-standard tasks like solving sudokus[1], it performs better than
aptitude. I pushed a fix into bzr that makes partial upgrades possible,
by keeping back impossible changes. The following is a report on the bzr
version.
[1]
http://algebraicthunk.net/~dburrows/blog/entry/package-management-sudoku/
======
Report
======
Behaviour
=========
Fully Working:
* apt-get upgrade
* apt-get install -f
Partially working:
* apt-get install
* Bug: Too Conservative. Installing mysql-server with
-texperimental will choose the mysql-server-5.1 from
unstable if libmysqlclient is already installed, because
this requires no upgrade of the installed package.
* Maybe Bug: Prefers removals over upgrades. Upgrading
nautilus to experimental causes removal of nautilus-dbg,
rather than an upgrade. Can be solved by adding package
sets to 'upgrade'.
* apt-get dist-upgrade
* Might remove every package instead of ignoring an
update. At least if you do apt-get dist-upgrade -t
experimental. We might need to keep() (manually)
installed packages first, and remove the keep() if the
user asks for it, instead of allowing the solver to do
what it wants with installed packages.
Programming interface
=====================
As it turns out, the current set of actions (install, remove, automatic)
is not enough. I propose to add two new VersionSets, 'upgrade', being
identical to 'install' in terms of the end result, but better from a
semantic point of view and easier to output; and 'keep' which is a set
of changes that were not done.
Secondly, we may want to have an interactive solver like aptitude. For
this, I propose a class APT::Solver::Helper, that contains callbacks for
various events. My current local prototype looks like this:
+
+ struct Helper {
+ /**
+ * \brief Callback invoked when a solution has been found.
+ *
+ * Represents the solution to the user and asks for confirmation
+ * of the solution. If the user does not want the solution, another
+ * solution may be found or the solver may end without a solution.
+ *
+ * \param install Packages that will be installed
+ * \param remove Packages that will be removed
+ * \param keep If the complete request cannot be satisfied, a set of
+ * packages that will not be changed.
+ * \return true if the user accepts the solution, false otherwise.
+ */
+ virtual bool Accept(const VersionSet &upgrade,
+ const VersionSet &install,
+ const VersionSet &remove,
+ const VersionSet &keep) = 0;
+ };
SatSolver bugs: Keep()
======================
Rules added by Keep() are preserved between multiple Solve() calls; that
is, the following clause is added:
Keep(P) = (P_1 | P_2 | ... |P_n)
We do not want this, as we want to allow the user to choose to remove a
package later on. Thus I propose we change this to:
Keep(P) = (-P | P_1 | P_2 | ... | P_n )
Where P is the literal describing the package and P_1..P_n are the
literals describing the package versions. This allows us to assume(P)
when solving and just stop assuming it in case we want to allow its
removal later on. In pseudo(maths+C):
P = lit(package) = cache.HeaderP->VersionCount + package->ID + 1;
P_i = lit(version) = version->ID + 1;
Meaning: The IDs of versions start at 1 and end at VersionCount. The IDs
for packages start at VersionCount + 1 and end at VersionCount +
PackageCount.
External issues
===============
* picosat is built without tracing support (Bug#607943)
* picosat prefers B in A | B if B > A (higher version ID wins)
* picosat does not allow for optional clauses, Recommends are thus
treated as Depends. I should ask them if they are interested in
adding this.
The future
==========
* Trying more solvers: clasp, minisat
* Replacing and deprecating pkgProblemSolver
* Interface for dynamically loading solvers at run-time
--
Julian Andres Klode - Debian Developer, Ubuntu Member
See http://wiki.debian.org/JulianAndresKlode and http://jak-linux.org/.
Reply to: