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

Reply via email to