Dear all,
It's possible that the goal of my current work and its possible benefit for the
gentoo community are not very clear.
In my experience, emerge is a very good tool to install new packages whose use
flags have already been configured.
However, when the packages are not correctly configured, emerge can guess,
without guarantee, some use flags to select/unselect; and unmerging a package
seems to be the user's entire responsability.
My work has several goals:
- provide a correct and complete implementation of a dependency solver for
portage that can help debug emerge
- since the solver is correct and complete, it would provide a "safe"
implementation of unmerge, where missing dependencies would be satisfied by the
installation of new packages
- provide a rather small code base that is easy to debug and on which it is
easy to prototype some tools, like REQUIRED_USE checks, or interactive use flag
configuration
- be usable, both in term of memory usage and computation time.
I finished implementing the solver and did some preliminary benchs (1000 tests
where I checked if a random set of packages -- different for each test -- could
be installed), including comparison with emerge in "search" modality, i.e.,
with the options --autounmask y --autounmask-continue y --autounmask-backtrack y
Since this is preliminary, I wanted to talk to you about it but I don't have
every bugs identified yet.
In average, my solver is a bit less than 10 times slower than emerge (not very
good, but not bad as it is still far better than a brute force approach, which
is more than 100 times slower and takes 3Gb of memory).
It is important to note that my solver is not suited for end user usage yet
(the answer it gives is correct, but random -- it includes useless packages,
useless package removal and old versions), but it is the first tool that I know
of that can correctly and completely (modulo bugs ^^) check emerge's behavior.
A first result: in more than 25% of the tests that can be installed, emerge
fails.
Most of these failures come from the fact that even in "search" modality,
emerge stops when it sees a REQUIRED_USE that is not correctly configured (I'll
post a bug report about it and about the SLOT heuristics in a few days).
I still need to look at the other failures to see what caused them.
Additionally, it seems that when I do "emerge package1 package2", emerge first
solves the dependencies of package1, and then of package2.
It seems that when resolving the depenendencies of package2, emerge can end up
with a conflict between the choices it made for solving the dependencies of
package1 and the requirements of package2.
I say "seems" because my tests were automatically done with a rather long list
of packages (so other reasons for the observed failures are possible).
I'll try to pin down the actual emerge behavior and possibly file a bug report.
I am currently porting the tests on docker (to have a safe testing environment)
and once that's done, I will be able to give actual bug reports.
In the future, I have the following plan:
- cleanup the output of the solver, so it wouldn't be random and be usable
instead (this is "just" a technical and boring algorithm to implement, but time
consuming)
- install the configuration computed by my solver (I am still unsure that
emerge --nodeps would be flexible enough, and maybe I will have to implement my
own planner)
- find a correct abstraction of packages, similar to the SLOT heuristics (
https://gitweb.gentoo.org/proj/portage.git/commit/?id=a9064d08ef4c92a5d0d1bfb3dc8a01b7850812b0
), to improve efficiency
- design an interactive package configuration algorithm + UI that would happen
during the dependency solving process and really help the user configuring what
he wants and let the solver do the rest
- start reading portage's bug tracker and continue reading its code
- extend pdepa with other kind of relevant analysis
All comments/suggestions are welcomed.
Best,
Michael
