Bootstrapping: list of 81 self-cycles in Debian Sid
Hi,
Since self-cycles in Debian are often unintuitive, maintainers might be unaware
that the source packages they maintain are actually forming a self cycle. I
therefore created a wiki page with the list of the 81 self-cycles in Debian Sid
as of 2013-01-01: http://wiki.debian.org/DebianBootstrap/SelfCycles Some extra
explanations follow.
During bootstrapping we must build some source packages with reduced build
dependencies (build profiles) to work around cyclic build dependencies. At the
same time we leave runtime dependencies of binary packages untouched. While the
build dependency graph contains thousands of nodes and there exist many
possible choices of build dependencies which would make the graph acyclic if
they were removed, some build dependencies are non-optional and *must* be
dropped: those which are part of self-cycles. Build dependencies which are part
of self-cycles are not optional because self-cycles consist of only a single
build dependency and a number of runtime dependencies. Since runtime
dependencies are not to be touched, this single build dependency *must* be
broken to be able to break the cycle. Since all cycles must be broken to make
the graph acyclic, breaking self-cycles is also not optional. Therefor, if we
enumerate a list of self-cycles in the build dependency graph, we automatically
have a list of source packages and their build dependencies which must be part
of a build profile (or be cross compiled).
Self-cycles can be divided into two classes:
1. a build dependency on a binary package the source package builds (the
simple case)
2. a build dependency on a binary package which needs one of the binary
packages the source package builds to be installable
The first class is easily detectable by checking whether any binary package is
part of the build dependencies of the source package that builds it. Such
cycles often appear in compilers that need themselves to be built.
The second class is harder to find because it is not enough to simply traverse
the dependency tree of a source package until one finds a dependency on one of
the binary packages the source package builds. Instead, the "strong
dependencies" [1] of a source package have to be calculated. If any of the
strong build dependencies of a source package are built by the source package
itself, a self-cycle is created. Such cycles are created by the
interdependencies between binary packages and are often very unintuitive.
Here two examples:
src:gnutls26 build depends on libgnutls26 because src:gnutls26 build depends on
gtk-doc-tools which needs libgnutls26 to be installable.
src:libproxy build depends on libproxy0 because src:libproxy build depends on
libwebkitgtk-dev which needs libproxy0 to be installable.
My code found 81 such cases in Debian Sid as of 2013-01-01. Due to this high
amount of results I pasted them into a wiki page instead of this email.
http://wiki.debian.org/DebianBootstrap/SelfCycles
If you find any inconsistencies, please dont hesitate to contact me or write to
our mailinglist at debian-bootstrap@lists.mister-muffin.de
cheers, josch
[1] Abate P, Boender J, di Cosmo R, Zacchiroli S. "Strong Dependencies between
Software Components" ESEM 2009
Reply to: