[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

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

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 



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

Reply to: