Bug#365087: ITP: debcheck -- Checks whether dependencies of debian packages can be satisfied
Owner: Ralf Treinen <firstname.lastname@example.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)