Re: RFC: The Future of Solving Dependency Problems in APT (SAT, CUDF)
On Do, 2010-12-23 at 10:09 +0100, Stefano Zacchiroli wrote:
> On Wed, Dec 22, 2010 at 06:32:20PM +0100, Julian Andres Klode wrote:
> > as discussed on IRC; the time is ready for APT to gain some more
> > advanced facilities in the area of solving dependency problems.
>
> I surely concur :)
>
> > The first file that I attach is solver.h. This outlines my proposal for
> > a new solver API. It contains the interface of an abstract base class
> > APT::Solver that provides an interface for solving changes, inspired by
> > discussions with some members of the community.
>
> I leave the comments on this API to the tech APT people.
>
> However, to my recalling, there was an unsolved problem in dealing with
> an external solver, namely how to discriminate between packages coming
> from APT repositories and identically-looking packages which have been
> possibly locally rebuilt by the user. Does your API rely on hashing of
> some set of package field to generate package identifiers as the current
> APT?
The script I wrote drops duplicates currently. The right solution is to
add the version ID to the package: field and to add a provides package:
package: apt%1
provides: apt
I'm also using this trick for splitting virtual packages from real ones
like this:
package: apt
provides: virtual%packagename, virtual%apt
(each virtual package gets virtual% prepended, and also provides itself
with virtual%)- then I change all unversioned dependencies such as
"depends: apt" to "depends: virtual%apt".
In this case, I used the '%' character as that's not allowed in package
names and does not seem to be reserved in CUDF either.
>
> I believe this problem deserves a cleaner solution, but the only
> solutions I can imagine require support at the dpkg level as well.
>
> > It shall be the base for two new classes: SatSolver and CudfSolver. The
> > first class implements a solver based on the boolean satisfiability
> > problem, the second one an interface to an external solver with data
> > exchange happening via the CUDF format[1]. We'd also be willing to merge
> > aptitude's solver into this new infrastructure if useful.
> <snip>
> > I also have a proof of concept CUDF writer written in Python, but
> > decided that we do not really need it now (it only writes the universe
> > to stdout, no request). And yes, pure CUDF, no Debian-specific version
> > thereof.
>
> I'm glad to hear this. Is the code in APT2? I'd appreciate pointers to
> it to have a look. Also, I've noticed a backlog on IRC (sorry, too late
> to reply to it) about some very interesting performances of your writer;
> care to report them here?
It's just a simple prototype to test how I can create CUDF. I attached
the script. It defines some extra unused properties for now, but
converts predepends to depends and breaks to conflicts; so the solver
can handle them. The output is valid according to cudf-check -univ.
(I'm using a minus-dash as a seperator instead of '%' in this script,
but the '%' is clearly superior).
>
> > If there are no objections, I will create a new branch, and implement
> > a SatSolver using picosat therein (as that's fairly easy and produces
> > good results).
>
> Here, are you referring to an APT branch or ...?
Yes.
>
> > I would also like to create the CudfSolver, but I'd need a solver to
> > test with. If anyone knows such solvers, please write.
>
> In the Mancoosi project we do have quite some of them, coming from the
> MISC 2010 competition http://www.mancoosi.org/misc-2010/ . In general,
> we have two variants of each participant solver, one implementing a
> "trendy" optimization strategy (try to upgrade as much packages as
> possible), and another one implementing a "paranoid" strategy (try to
> satisfy user request, but by changing as little packages as
> possible). Mind you though, as the participants were free to use the
> language they want, there's quite some Java around which is not exactly
> "fast" in CUDF parsing.
>
> I'm adding to Cc: Pietro Abate, a co-worker of mine in the Mancoosi
> project. He has been one of the main organizers of the MISC competition
> and he has collected the code of all participant solvers. Unfortunately
> there is at least one case in which we cannot re-distribute the code of
> a participating solver (it was licensed to us only for the purposes of
> the competition), but all other solvers are free software. Pietro can
> give you the actual code and/or point you to where the solvers are
> available for download.
>
> ( Pietro: for reference the initial mail of this thread is at
> http://lists.debian.org/deity/2010/12/msg00053.html )
>
> Cheers.
>
--
Julian Andres Klode - Debian Developer, Ubuntu Member
See http://wiki.debian.org/JulianAndresKlode and http://jak-linux.org/.
import apt_pkg, apt, sys
apt_pkg.init()
class CudfWriter(object):
def __init__(self):
self.cache = apt_pkg.Cache(apt.progress.base.OpProgress())
self.versions = {}
self.extra_provides = {}
for package in self.cache.packages:
versions = set()
for version in package.version_list:
versions.add(version.ver_str)
for dep in package.rev_depends_list:
if dep.target_ver:
versions.add(dep.target_ver)
self.versions[package.name] = sorted(versions,
cmp=apt_pkg.version_compare)
def repr_dep(self, dep):
if dep.comp_type:
try:
ver = self.versions[dep.target_pkg.name].index(dep.target_ver) + 1
except:
ver = 999
return "%s %s %s" % (dep.target_pkg.name, dep.comp_type, ver)
else:
return "virtual-" + dep.target_pkg.name
def repr_or(self, or_group):
if len(or_group) == 1:
return self.repr_dep(or_group[0])
else:
group = ' | '.join(self.repr_dep(d) for d in or_group)
return group #apt_pkg.quote_string(group, "|<>=!")
def __call__(self):
print "preamble: "
print "property: "
print " debvers: string ,"
print " recommends: vpkgformula = [true!] ,"
print " suggests: vpkgformula = [true!] ,"
print " enhances: vpkgformula = [true!] ,"
print " replaces: vpkgformula = [true!] "
print
for package in sorted(self.cache.packages, key=lambda p: p.name):
done = set()
for version in sorted(package.version_list):
verid = self.versions[package.name].index(version.ver_str) + 1
if verid in done:
continue
done.add(verid)
print "package:", package.name
print "version:", verid
print "debvers:", version.ver_str
depends = {}
for k, v in version.depends_list.iteritems():
k = k.lower()
if k == "predepends":
k = "depends"
elif k == "breaks":
k = "conflicts"
if not k in depends:
depends[k] = []
depends[k] += v
have_conflicts = False
for typ, deplist in depends.iteritems():
print typ.lower()+ ":",
if typ == "conflicts":
have_conflicts=True
print "%s != %d," % (package.name, verid),
to_print = []
for or_group in deplist:
to_print.append(self.repr_or(or_group))
print ', '.join(to_print)
if not have_conflicts:
print "conflicts: %s != %d" % (package.name, verid)
provides = ["virtual-" + name for (name, ver, pver) in version.provides_list]
provides.append("virtual-%s" % package.name)
if provides:
print "provides:", ', '.join(provides)
if package.current_ver == version:
print "installed: true"
print
write = CudfWriter()
write()
Reply to: