Bug#365087: [edos-wp2] Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Dear Sven,
as you say, what is described in 4.4.2 is close to what you want,
but I really do not know if it is possible to get what you want (i.e.
an optimal, if not optimum, result)... Indeed, installability is NP-complete,
even if we are lucky and the instances found in the Debian repos are not
hard, and for some packages (like php5), the solution set is
_huge_, so getting even a nearly optimal solution w.r.t. some criteria is really
not evident... this is one of the problems we are looking at right now.
Nevertheless, I do suggest that you try by yourself to see in practice what the
current tool ends up with... we might be lucky, and you could get a decent result.
For this, you need the latest ocaml, libmysql-ocaml-dev and libpcre-ocaml-dev,
then do
svn checkout https://protactinium.pps.jussieu.fr:12345/svn/edos/software/dependencies/history/trunk
and
make
then, you need to get the latest cache file for Debian, from Berke, at
http://gallium.inria.fr/~durak/history-cache.gz (20 Mb!), uncompress it,
rename it as .history-cache and run history in the same directory where
the cache file is...
If you need further help, please contact history's author, Berke Durak, in cc:
here...
All the best
--Roberto
>>>>> "Sven" == Sven Mueller <sven@incase.de> writes:
Sven> Ralf Treinen wrote on 28/04/2006 09:48:
>> Hi Sven,
>>> It would be quite nice if the tool had an option to do the following:
>>> Given the Packages file (or other compatible list of packages) on STDIN
>>> and a set of "seed" packages on the commandline, print out all the
>>> packages needed to fulfill the dependencies (if all dependencies can be
>>> fulfilled - error out if not).
>> What you describe is indeed one of the goals of the edos project
>> (http://www.edos-project.org/xwiki/bin/view/Main/WebHome) where the
>> debcheck tool (and many others) comes from. In the context of the edos
>> projec we call this problem "thinning" of a distribution. The problem
>> seems to be beyond debcheck's realm. There is work in progress on this
>> issue but so far there is no completely satisfying solution. In
>> particular we would like to find a minimal solution with respect to some
>> reasonable metrics (number of packages, size of packages, ...). How
>> important do you think would be minimality of a solution? Or what would
>> be your criterion for an optimal solution to the problem?
>>
>> The use case you describe suggests to me a variant of the problem which
>> might be easier: Extend a given distribution by just a small set of
>> packages and their dependency closure. In this case it would be
>> sufficient to find a solution which is only "locally" optimal (that is
>> optimal among those that preserve the previous calculated
>> distribution). Would that be sufficient for your purpose?
Sven> I'm not certain what you describe here. What I would need as an output
Sven> is a sort of minimal set of packages. The Definition of a minimal set
Sven> could divert under certain circumstances (minimal in size or in number
Sven> of packages), but for me it would be of no importance wether I would
Sven> get the minimal number of packages or the set of minimal size. Let's
Sven> assume that apart from what Debian defines as the core set of
Sven> packages, my repository has these packages (format: "package:
Sven> Dependencies (size)"):
Sven> a: b, c|d (1) b: d|c (1) c: e (2) d: (4) e: (1)
Sven> Assuming that there are no conflicts, and I specify "a" as the 'set'
Sven> of seed packages. Now there are a number of possible solutions:
Sven> a,b,c,d,e (9) a,b,c,e (5) a,b,d,e (7) a,b,d (6) The first is trivial:
Sven> If I install all packages, all dependencies are fulfilled. The second
Sven> if the optiomal solution if space is the criteria, the fourth the
Sven> optimal solution if number of packages is the criteria. The third is
Sven> a non-trivial and non-optimal solution. I personally wouldn't care
Sven> wether I get the second or fourth solution, as long as the set is
Sven> minimal to either the number of packages or the size of packages
Sven> criteria. However I need to be able to specify the seed packages and
Sven> the list of available Packages at run time. I do not care about what
Sven> the history of my archive might have produced at some other time of
Sven> its existance though. And I would be actually quite satisfied if the
Sven> solution I get is nearly optimal to either criteria, I don't care if I
Sven> could have a set with 5% less packages (or package size), as long as
Sven> the set I get doesn't contain more than 10% of unneeded packages.
Sven> Roberto: I'm not sure I understand your descriptions of "history" and
Sven> "anla" correctly. But from glancing over the PDF you referenced, I
Sven> guess what I need is actually an equivalent to something close to the
Sven> thing described in 4.4.2 (A first solution). My ideal tool would take
Sven> a packages list from STDIN (like debcheck does) plus a set of packages
Sven> from the commandline (as a list in $need). What I would then
Sven> appreciate to get is equivalent to the following expression if I
Sven> understand the syntax right:
Sven> $essential <- unit(filter(packages, $p -> is_essential($p))) $target
Sven> <- $essential | $need $result <- install(latest($target), packages)
Sven> I'm not worried about certain (known) packages missing from that
Sven> $result set (like kernel or bootloader - which are normally not
Sven> directly depended on) unless they were specified in the list of seed
Sven> packages.
Sven> Regards, Sven
--
--Roberto Di Cosmo
------------------------------------------------------------------
Professeur
PPS E-mail: roberto@dicosmo.org
Universite Paris VII WWW : http://www.dicosmo.org
Case 7014 Tel : ++33-(0)1-44 27 86 55
2, place Jussieu Fax : ++33-(0)1-44 27 68 49
F-75251 Paris Cedex 05
FRANCE.
------------------------------------------------------------------
Attachments:
MIME accepted
Word deprecated, http://www.rfc1149.net/documents/whynotword
------------------------------------------------------------------
Office location:
Bureau 6C15 (6th floor)
175, rue du Chevaleret, XIII
Metro Chevaleret, ligne 6
------------------------------------------------------------------
Reply to: