Debian Bug report logs - #365087
ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied

version graph

Package: wnpp; Maintainer for wnpp is wnpp@debian.org;

Reported by: Ralf Treinen <treinen@debian.org>

Date: Thu, 27 Apr 2006 20:03:17 UTC

Owned by: ralf treinen <treinen@debian.org>

Severity: wishlist

Fixed in version edos-debcheck/0.0.2006.03.19-1

Done: Ralf Treinen <treinen@debian.org>

Bug is archived. No further changes may be made.

Toggle useless messages

View this report as an mbox folder, status mbox, maintainer mbox


Report forwarded to debian-bugs-dist@lists.debian.org, debian-devel@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Ralf Treinen <treinen@debian.org>:
New Bug report received and forwarded. Copy sent to debian-devel@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #5 received at submit@bugs.debian.org (full text, mbox):

From: Ralf Treinen <treinen@debian.org>
To: Debian Bug Tracking System <submit@bugs.debian.org>
Subject: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Thu, 27 Apr 2006 21:53:20 +0200
Package: wnpp
Severity: wishlist
Owner: Ralf Treinen <treinen@debian.org>

* Package name    : debcheck
  Version         : as of 2006/3/19
  Upstream Author : Jerome Vouillon <Jerome.Vouillon@pps.jussieu.fr>
* URL             : http://www.pps.jussieu.fr/~vouillon/
* License         : GPL
  Programming Lang: Objective Caml
  Description     : Checks whether dependencies of debian packages can be satisfied

This software checks for every package of a distribution (in the
debian format .deb) whether it is possible to satisfy its dependencies
and conflicts within this distribution.

The constraint solving algorithm is complete, that is it finds a
solution whenever there exists one, even for multiple disjunctive dependencies
and deep package conflicts. This problem is computationally intractable in
theory (that is, NP-complete), but can in practice be solved very efficiently.


==========================================================================

Some comments on this: the essential point is that it is really a
*complete* constraint solver. In particular it implements properly
the logical semantics of disjunctive dependencies. 

Despite the fact that it is a complete constraint solver, and despite
the fact that the problem is NP-complete, the tool is lightning fast.
This is achieved by using a custom-built SAT solver.  For instance, a
complete check of testing/main for i386 as of today takes 12 seconds
on my PC (1GHz).

Preliminary packages are available at 

http://people.debian.org/~treinen/debcheck/

-Ralf.

-- System Information:
Debian Release: testing/unstable
  APT prefers unstable
  APT policy: (990, 'unstable'), (500, 'testing'), (1, 'experimental')
Architecture: i386 (i686)
Shell:  /bin/sh linked to /bin/bash
Kernel: Linux 2.6.16
Locale: LANG=C, LC_CTYPE=C (charmap=ISO-8859-1) (ignored: LC_ALL set to en_US)



Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Sven Mueller <sven@incase.de>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #10 received at 365087@bugs.debian.org (full text, mbox):

From: Sven Mueller <sven@incase.de>
To: Ralf Treinen <treinen@debian.org>, 365087@bugs.debian.org
Subject: Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Thu, 27 Apr 2006 23:30:38 +0200
Hi.

While trying to compile your preliminary package on AMD64, I had a FTBFS
problem. I solved it, so this is only annecdotal, but please read the
last paragraph of this mail anyway.

After some searching, I found the problem to be that my version of
findutils interpreted the regular expression differently, so that your
Makefile rule to build .depend didn't match.

I modified the find call to be 'find . -name "*.ml" -o -name "*.mli"'
and it worked that way. I see the relevant bug in findutils has been
fixed in 4.2.22-2, so this is not an issue any longer.

However, I wonder why you have a "versioned" depend on ocaml-nox-3.09.1.
debcheck seems to run quite nicely on my Sarge box (with ocaml-nox 3.08

cu,
sven



Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Sven Mueller <sven@incase.de>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #15 received at 365087@bugs.debian.org (full text, mbox):

From: Sven Mueller <sven@incase.de>
To: Ralf Treinen <treinen@debian.org>, 365087@bugs.debian.org
Subject: Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Fri, 28 Apr 2006 00:04:02 +0200
Ralf Treinen wrote on 27/04/2006 21:53:
> Package: wnpp
> Severity: wishlist
> Owner: Ralf Treinen <treinen@debian.org>
> 
> * Package name    : debcheck
>   Version         : as of 2006/3/19
>   Upstream Author : Jerome Vouillon <Jerome.Vouillon@pps.jussieu.fr>
> * URL             : http://www.pps.jussieu.fr/~vouillon/

There is one "small" wish (actually I don't know wether it is a small or
large one, considering the work already done in debcheck/rpmcheck) I
have, which you might want to implement and/or forward to $Upstream:

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).

This would be of use on many occasions, most notably when you try to
build a minimal repository which contains all needed packages for a
given set of packages you want installed. In my case, it would help to
build an automated installation CD for Debian with some customized
and/or additional packages. Currently, when I add a new application, I
have to manually check the dependencies. Would be extremely nice to find
a way to automate this.

Regards,
Sven



Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Peter Palfrader <weasel@debian.org>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #20 received at 365087@bugs.debian.org (full text, mbox):

From: Peter Palfrader <weasel@debian.org>
To: Ralf Treinen <treinen@debian.org>, 365087@bugs.debian.org
Subject: Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Fri, 28 Apr 2006 04:43:38 +0200
On Thu, 27 Apr 2006, Ralf Treinen wrote:

> Package: wnpp
> Severity: wishlist
> Owner: Ralf Treinen <treinen@debian.org>
> 
> * Package name    : debcheck
>   Upstream Author : Jerome Vouillon <Jerome.Vouillon@pps.jussieu.fr>

Actually, there already is a debcheck.  Namely the tests run on the qa
page:

http://qa.debian.org/debcheck.php

You probably should think of a slightly different name for the thing.

-- 
 PGP signed and encrypted  |  .''`.  ** Debian GNU/Linux **
    messages preferred.    | : :' :      The  universal
                           | `. `'      Operating System
 http://www.palfrader.org/ |   `-    http://www.debian.org/



Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Ralf Treinen <treinen@free.fr>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #25 received at 365087@bugs.debian.org (full text, mbox):

From: Ralf Treinen <treinen@free.fr>
To: debian-devel@lists.debian.org
Cc: edos-wp <edos-wp2@sympa.pps.jussieu.fr>, 365087@bugs.debian.org
Subject: Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Fri, 28 Apr 2006 09:30:56 +0200
On Thu, Apr 27, 2006 at 05:30:48PM -0400, Stefano Zacchiroli wrote:
> On Thu, Apr 27, 2006 at 09:53:20PM +0200, Ralf Treinen wrote:
> > Package: wnpp
> > Severity: wishlist
> > Owner: Ralf Treinen <treinen@debian.org>
> > 
> > * Package name    : debcheck
> >   Version         : as of 2006/3/19
> >   Upstream Author : Jerome Vouillon <Jerome.Vouillon@pps.jussieu.fr>
> > * URL             : http://www.pps.jussieu.fr/~vouillon/
> > * License         : GPL
> >   Programming Lang: Objective Caml
> >   Description     : Checks whether dependencies of debian packages can be satisfied
> > 
> > This software checks for every package of a distribution (in the
> > debian format .deb) whether it is possible to satisfy its dependencies
> > and conflicts within this distribution.
> 
> Looking at the docs the tool seems to be able to work on any set of
> debian packages provided as Packages entries provided on standard input.
> I would thus rephrase the above paragraph as:
> 
>   This software checks for a set of Debian packages (provided as
>   Packages entries) whether it is possible to satisfy the dependencies
>   and conflicts of all involved packages within the set.
> 
> Better to ask for an advice of a native English speaker, but my point is
> to emphasize "the set of packages" rather then "the distribution".

You are right. My usage of the word "distribution" comes from the
terminology of the edos project
http://www.edos-project.org/xwiki/bin/view/Main/WebHome
(where this tool, and many others, originated). In the context of this
project a distribution is a set of packages containing possibly
multiple versions of a package name. The debian reading of the
word "distribution" excludes this.

> > Preliminary packages are available at 
> > http://people.debian.org/~treinen/debcheck/
> 
> I suggest to add to the manpage an hint that the Packages file is a
> suitable input for the tool.

For the moment it is in the EXAMPLES section of the manpage, but I'll
make this more explicit.

> I saw that there is also an rpmcheck tool, which does the same for .rpm
> packages. Don't you plan to package this as well? What about providing
> an unique binary package (maybe called "pkgcheck") with the two
> binaries?

For the moment I create two binary packages, one with the debcheck tool
for deb packages, and another one with the rpmcheck tool which does the
analogous thing on rpm packages. I forgot to mention this in my ITP.

> If you are worried about the size: upstream links them separately and
> they are 130 Kb each, but I'm pretty confident that linking a single
> executable with two different names and the usual speculation about
> Sys.argv.(0) would dramatically cut down the total size ...

I'll have a look into this, thanks for the suggestion.

-Ralf.



Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Ralf Treinen <treinen@free.fr>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #30 received at 365087@bugs.debian.org (full text, mbox):

From: Ralf Treinen <treinen@free.fr>
To: Sven Mueller <sven@incase.de>
Cc: 365087@bugs.debian.org
Subject: Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Fri, 28 Apr 2006 09:35:47 +0200
Hi,

On Thu, Apr 27, 2006 at 11:30:38PM +0200, Sven Mueller wrote:

> However, I wonder why you have a "versioned" depend on ocaml-nox-3.09.1.
> debcheck seems to run quite nicely on my Sarge box (with ocaml-nox 3.08

You are right, this is too strict here. I'll relax the build-dependency
for he next version. When I wrote this I was thinking about compilation
to OCaml byte code.

Thanks -Ralf.



Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Ralf Treinen <treinen@free.fr>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #35 received at 365087@bugs.debian.org (full text, mbox):

From: Ralf Treinen <treinen@free.fr>
To: Sven Mueller <sven@incase.de>
Cc: 365087@bugs.debian.org, edos-wp <edos-wp2@sympa.pps.jussieu.fr>
Subject: Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Fri, 28 Apr 2006 09:48:15 +0200
Hi Sven,

On Fri, Apr 28, 2006 at 12:04:02AM +0200, Sven Mueller wrote:
> Ralf Treinen wrote on 27/04/2006 21:53:
> > Package: wnpp
> > Severity: wishlist
> > Owner: Ralf Treinen <treinen@debian.org>
> > 
> > * Package name    : debcheck
> >   Version         : as of 2006/3/19
> >   Upstream Author : Jerome Vouillon <Jerome.Vouillon@pps.jussieu.fr>
> > * URL             : http://www.pps.jussieu.fr/~vouillon/
> 
> There is one "small" wish (actually I don't know wether it is a small or
> large one, considering the work already done in debcheck/rpmcheck) I
> have, which you might want to implement and/or forward to $Upstream:
> 
> 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).
> 
> This would be of use on many occasions, most notably when you try to
> build a minimal repository which contains all needed packages for a
> given set of packages you want installed. In my case, it would help to
> build an automated installation CD for Debian with some customized
> and/or additional packages. Currently, when I add a new application, I
> have to manually check the dependencies. Would be extremely nice to find
> a way to automate this.

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?

-Ralf.



Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Ralf Treinen <treinen@debian.org>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #40 received at 365087@bugs.debian.org (full text, mbox):

From: Ralf Treinen <treinen@debian.org>
To: Peter Palfrader <weasel@debian.org>
Cc: 365087@bugs.debian.org, edos-wp <edos-wp2@sympa.pps.jussieu.fr>
Subject: Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Fri, 28 Apr 2006 09:52:12 +0200
On Fri, Apr 28, 2006 at 04:43:38AM +0200, Peter Palfrader wrote:
> On Thu, 27 Apr 2006, Ralf Treinen wrote:
> 
> > Package: wnpp
> > Severity: wishlist
> > Owner: Ralf Treinen <treinen@debian.org>
> > 
> > * Package name    : debcheck
> >   Upstream Author : Jerome Vouillon <Jerome.Vouillon@pps.jussieu.fr>
> 
> Actually, there already is a debcheck.  Namely the tests run on the qa

This is the name used by the upstream author, but I realise that it
might be too generic. I'll think about it.

> page:
> 
> http://qa.debian.org/debcheck.php

That is interesting. How exactly are these pages computed?

-Ralf.



Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Lars Wirzenius <liw@liw.iki.fi>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #45 received at 365087@bugs.debian.org (full text, mbox):

From: Lars Wirzenius <liw@liw.iki.fi>
To: Ralf Treinen <treinen@debian.org>, 365087@bugs.debian.org
Subject: Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Fri, 28 Apr 2006 14:27:55 +0300
to, 2006-04-27 kello 21:53 +0200, Ralf Treinen kirjoitti:
> * Package name    : debcheck

There is a Debian QA page of the same name:
http://qa.debian.org/debcheck.php

It might be good to avoid a name clash and the resulting confusion.

Or, perhaps, your debcheck could be used to improve the QA page? :)

-- 
The road is wide and the sky is tall, before I die I will see it
all.--H.A.




Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Roberto Di Cosmo <roberto@dicosmo.org>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #50 received at 365087@bugs.debian.org (full text, mbox):

From: roberto@dicosmo.org
To: Sven Mueller <sven@incase.de>
Cc: Ralf Treinen <treinen@free.fr>, 365087@bugs.debian.org, edos-wp <edos-wp2@sympa.pps.jussieu.fr>
Subject: Re: [edos-wp2] Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Fri, 28 Apr 2006 17:03:41 +0200
Dear Sven,
     in EDOS we have built quite a few other tools, which are not yet
finalized to the point of being widely usable outside the project (more on
this below), that provide a first solution of the problem you mention...

 - history.
   This is a tool, written by Berk Durak, that incorporates Jerome's solver
   algorithm and has a command line interface that provides an algebraic
   language to manipulate sets of packages: select packages available on day d,
   intersect, union, get latest versions, compute dependency closure,
   testing for installability, etc.

   Now, if you look at chapter 4, section 4.2 of
   http://www.edos-project.org/xwiki/bin/download/Main/Deliverables/edos-wp2d2.pdf
   you will see the description of an actual transcript of a session with the
   tool that tries to build a small self-contained distribution containing a
   given set of requested packages.

 - anla.
   This is usable, online, at http://brion.inria.fr/anla
   It is a webified, history-aware tool written by Berke and incorporating
   Jerome's solver and Jaap Boender's package readers.
   This could be, IMHO, of huge help for distribution maintainers, and is
   already usable for Debian (since the tool is following the Debian pool
   now).

What is up to now under heavy development/testing for these two tools is the
backend that builds the huge database containing the historical information for
all the packages, day by day... Berke has been testing a relational backend, but
it is too slow, so he is now moving to a more efficient, but custom-built,
solution. Until this backend is finalized, it is a bit complicated to deploy
history or anla...

We definitely will need packages for history and anla too :-)

--Roberto

>>>>> "Ralf" == Ralf Treinen <treinen@free.fr> writes:

    Ralf> Hi Sven, On Fri, Apr 28, 2006 at 12:04:02AM +0200, Sven Mueller wrote:
    >> Ralf Treinen wrote on 27/04/2006 21:53: > Package: wnpp > Severity:
    >> wishlist > Owner: Ralf Treinen <treinen@debian.org>
    >> > 
    >> > * Package name : debcheck > Version : as of 2006/3/19 > Upstream Author
    >> : Jerome Vouillon <Jerome.Vouillon@pps.jussieu.fr> > * URL :
    >> http://www.pps.jussieu.fr/~vouillon/
    >> 
    >> There is one "small" wish (actually I don't know wether it is a small or
    >> large one, considering the work already done in debcheck/rpmcheck) I
    >> have, which you might want to implement and/or forward to $Upstream:
    >> 
    >> 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).
    >> 
    >> This would be of use on many occasions, most notably when you try to
    >> build a minimal repository which contains all needed packages for a given
    >> set of packages you want installed. In my case, it would help to build an
    >> automated installation CD for Debian with some customized and/or
    >> additional packages. Currently, when I add a new application, I have to
    >> manually check the dependencies. Would be extremely nice to find a way to
    >> automate this.

    Ralf> What you describe is indeed one of the goals of the edos project
    Ralf> (http://www.edos-project.org/xwiki/bin/view/Main/WebHome) where the
    Ralf> debcheck tool (and many others) comes from. In the context of the edos
    Ralf> projec we call this problem "thinning" of a distribution.  The problem
    Ralf> seems to be beyond debcheck's realm. There is work in progress on this
    Ralf> issue but so far there is no completely satisfying solution. In
    Ralf> particular we would like to find a minimal solution with respect to
    Ralf> some reasonable metrics (number of packages, size of packages,
    Ralf> ...). How important do you think would be minimality of a solution? Or
    Ralf> what would be your criterion for an optimal solution to the problem?

    Ralf> The use case you describe suggests to me a variant of the problem
    Ralf> which might be easier: Extend a given distribution by just a small set
    Ralf> of packages and their dependency closure. In this case it would be
    Ralf> sufficient to find a solution which is only "locally" optimal (that is
    Ralf> optimal among those that preserve the previous calculated
    Ralf> distribution). Would that be sufficient for your purpose?

    Ralf> -Ralf.

-- 
--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
------------------------------------------------------------------                                                 



Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Message #53 received at 365087@bugs.debian.org (full text, mbox):

From: Christoph Berg <myon@debian.org>
To: Ralf Treinen <treinen@debian.org>, 365087@bugs.debian.org
Subject: Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Fri, 28 Apr 2006 18:09:52 +0200
[Message part 1 (text/plain, inline)]
Re: Ralf Treinen 2006-04-28 <20060428075212.GD4975@club-internet.fr>
> > http://qa.debian.org/debcheck.php
> 
> That is interesting. How exactly are these pages computed?

The source is on cvs.debian.org, module 'qa'.

Christoph
-- 
cb@df7cb.de | http://www.df7cb.de/
[signature.asc (application/pgp-signature, inline)]

Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Ralf Treinen <treinen@lsv.ens-cachan.fr>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #58 received at 365087@bugs.debian.org (full text, mbox):

From: Ralf Treinen <treinen@lsv.ens-cachan.fr>
To: Sven Mueller <sven@incase.de>
Cc: 365087@bugs.debian.org, roberto@dicosmo.org
Subject: Re: [edos-wp2] Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Fri, 28 Apr 2006 18:10:17 +0200
On Fri, Apr 28, 2006 at 05:03:41PM +0200, roberto@dicosmo.org wrote:

>  - anla.
>    This is usable, online, at http://brion.inria.fr/anla

This should be http://brion.inria.fr/anla/

-Ralf.
-- 
Ralf Treinen
Laboratoire Spécification et Vérification
CNRS, École Normale Supérieure de Cachan, INRIA Futurs
http://www.lsv.ens-cachan.fr/~treinen



Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Sven Mueller <sven@incase.de>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #63 received at 365087@bugs.debian.org (full text, mbox):

From: Sven Mueller <sven@incase.de>
To: Ralf Treinen <treinen@free.fr>
Cc: 365087@bugs.debian.org, edos-wp <edos-wp2@sympa.pps.jussieu.fr>
Subject: Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Sat, 29 Apr 2006 21:45:08 +0200
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?

I'm not certain what you describe here. What I would need as an output
is a sort of minimal set of packages. The Definition of a minimal set
could divert under certain circumstances (minimal in size or in number
of packages), but for me it would be of no importance wether I would get
the minimal number of packages or the set of minimal size. Let's assume
that apart from what Debian defines as the core set of packages, my
repository has these packages (format: "package: Dependencies (size)"):

a: b, c|d (1)
b: d|c (1)
c: e (2)
d: (4)
e: (1)

Assuming that there are no conflicts, and I specify "a" as the 'set' of
seed packages. Now there are a number of possible solutions:
a,b,c,d,e (9)
a,b,c,e (5)
a,b,d,e (7)
a,b,d (6)
The first is trivial: If I install all packages, all dependencies are
fulfilled. The second if the optiomal solution if space is the criteria,
the fourth the optimal solution if number of packages is the criteria.
The third is a non-trivial and non-optimal solution.
I personally wouldn't care wether I get the second or fourth solution,
as long as the set is minimal to either the number of packages or the
size of packages criteria. However I need to be able to specify the seed
packages and the list of available Packages at run time.
I do not care about what the history of my archive might have produced
at some other time of its existance though. And I would be actually
quite satisfied if the solution I get is nearly optimal to either
criteria, I don't care if I could have a set with 5% less packages (or
package size), as long as the set I get doesn't contain more than 10% of
unneeded packages.

Roberto: I'm not sure I understand your descriptions of "history" and
"anla" correctly. But from glancing over the PDF you referenced, I guess
what I need is actually an equivalent to something close to the thing
described in 4.4.2 (A first solution). My ideal tool would take a
packages list from STDIN (like debcheck does) plus a set of packages
from the commandline (as a list in $need). What I would then appreciate
to get is equivalent to the following expression if I understand the
syntax right:

$essential <- unit(filter(packages, $p -> is_essential($p)))
$target <- $essential | $need
$result <- install(latest($target), packages)

I'm not worried about certain (known) packages missing from that $result
set (like kernel or bootloader - which are normally not directly
depended on) unless they were specified in the list of seed packages.

Regards,
Sven



Information forwarded to debian-bugs-dist@lists.debian.org, <wnpp@debian.org>, ralf treinen <treinen@debian.org>:
Bug#365087; Package wnpp. Full text and rfc822 format available.

Acknowledgement sent to Roberto Di Cosmo <roberto@dicosmo.org>:
Extra info received and forwarded to list. Copy sent to <wnpp@debian.org>, ralf treinen <treinen@debian.org>. Full text and rfc822 format available.

Message #68 received at 365087@bugs.debian.org (full text, mbox):

From: roberto@dicosmo.org
To: Sven Mueller <sven@incase.de>
Cc: Ralf Treinen <treinen@free.fr>, Berke.Durak@inria.fr, 365087@bugs.debian.org, edos-wp <edos-wp2@sympa.pps.jussieu.fr>
Subject: Re: [edos-wp2] Re: Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Date: Tue, 2 May 2006 04:53:55 +0200
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 sent to Ralf Treinen <treinen@debian.org>:
You have taken responsibility. Full text and rfc822 format available.

Notification sent to Ralf Treinen <treinen@debian.org>:
Bug acknowledged by developer. Full text and rfc822 format available.

Message #73 received at 365087-close@bugs.debian.org (full text, mbox):

From: Ralf Treinen <treinen@debian.org>
To: 365087-close@bugs.debian.org
Subject: Bug#365087: fixed in edos-debcheck 0.0.2006.03.19-1
Date: Sat, 24 Jun 2006 05:34:37 -0700
Source: edos-debcheck
Source-Version: 0.0.2006.03.19-1

We believe that the bug you reported is fixed in the latest version of
edos-debcheck, which is due to be installed in the Debian FTP archive:

edos-debcheck_0.0.2006.03.19-1.diff.gz
  to pool/main/e/edos-debcheck/edos-debcheck_0.0.2006.03.19-1.diff.gz
edos-debcheck_0.0.2006.03.19-1.dsc
  to pool/main/e/edos-debcheck/edos-debcheck_0.0.2006.03.19-1.dsc
edos-debcheck_0.0.2006.03.19-1_i386.deb
  to pool/main/e/edos-debcheck/edos-debcheck_0.0.2006.03.19-1_i386.deb
edos-debcheck_0.0.2006.03.19.orig.tar.gz
  to pool/main/e/edos-debcheck/edos-debcheck_0.0.2006.03.19.orig.tar.gz
edos-rpmcheck_0.0.2006.03.19-1_i386.deb
  to pool/main/e/edos-debcheck/edos-rpmcheck_0.0.2006.03.19-1_i386.deb



A summary of the changes between this version and the previous one is
attached.

Thank you for reporting the bug, which will now be closed.  If you
have further comments please address them to 365087@bugs.debian.org,
and the maintainer will reopen the bug report if appropriate.

Debian distribution maintenance software
pp.
Ralf Treinen <treinen@debian.org> (supplier of updated edos-debcheck package)

(This message was generated automatically at their request; if you
believe that there is a problem with it please contact the archive
administrators by mailing ftpmaster@debian.org)


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Format: 1.7
Date: Mon, 22 May 2006 22:47:52 +0200
Source: edos-debcheck
Binary: edos-debcheck edos-rpmcheck
Architecture: source i386
Version: 0.0.2006.03.19-1
Distribution: unstable
Urgency: low
Maintainer: Ralf Treinen <treinen@debian.org>
Changed-By: Ralf Treinen <treinen@debian.org>
Description: 
 edos-debcheck - Checks whether dependencies of debian packages can be satisfied
 edos-rpmcheck - Checks whether dependencies of redhat packages can be satisfied
Closes: 365087
Changes: 
 edos-debcheck (0.0.2006.03.19-1) unstable; urgency=low
 .
   * Initial Release (closes: Bug#365087).
Files: 
 caa96a801ba4caa8c14c670370cda829 650 devel optional edos-debcheck_0.0.2006.03.19-1.dsc
 b7a8ed153fdbf74cf952bc1e159394b4 26006 devel optional edos-debcheck_0.0.2006.03.19.orig.tar.gz
 e3fe0ef9a18775771ea9e6ea4f957774 3316 devel optional edos-debcheck_0.0.2006.03.19-1.diff.gz
 f98341b1876cfd64b0eb30ba7e8e4cd9 130566 devel optional edos-debcheck_0.0.2006.03.19-1_i386.deb
 6ba1da7b20d043e724cc49354b3c2b08 133704 devel optional edos-rpmcheck_0.0.2006.03.19-1_i386.deb

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)

iD8DBQFEciP0tzWmSeC6BMERApUXAJ9zSRD9oOvZCyBmz4Aonqb9ovc2EQCeJavc
2BvonDG8vdWHmdBWCz6W+Dw=
=fP4A
-----END PGP SIGNATURE-----




Bug archived. Request was from Debbugs Internal Request <owner@bugs.debian.org> to internal_control@bugs.debian.org. (Tue, 19 Jun 2007 01:40:58 GMT) Full text and rfc822 format available.

Send a report that this bug log contains spam.


Debian bug tracking system administrator <owner@bugs.debian.org>. Last modified: Sun Apr 20 14:01:40 2014; Machine Name: buxtehude.debian.org

Debian Bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.