Re: Bootstrappable Debian - proposal of needed changes
Hi,
On Fri, Jan 18, 2013 at 04:27:00PM -0800, Steve Langasek wrote:
> On Thu, Jan 17, 2013 at 08:33:57AM +0100, Wouter Verhelst wrote:
> > Now it might be that a package build-depends on our package foo
> > because it needs to translate documents in that XML format into
> > something else, With your proposal, there's no way for the
> > build-depending package to declare that it needs a version of foo
> > that was built at a richer profile than stage1.
>
> The obviously correct solution to this is to strictly order the builds, by
> considering the stageX package builds as satisfying the build dependencies
> *only* of those packages that are part of the build loop. All other revdeps
> should wait until the final version of the package is available. In that
> case, misbuilds are only possible if there's an error in the bootstrapping
> metadata itself (or in the bootstrapping code).
Unfortunately, in practice the problem is a bit bigger than individual
cycles. We still call them "cycles" all the time because that's what
people can imagine best. In reality, packages are involved in strongly
connected components.
When starting native compilation from a minimal build system
(priority:essential plus build-essential plus debhelper), then the
biggest problem is a strongly connected components with 900-1000 nodes.
This means that each of the involved nodes is part of millions/billions
of real "cycles". This is partly why breaking this dependency graph with
minimal "cuts" is an NP-complete problem and only approximate solutions
are currently known. The approximate solution I came up with allows to
break this strongly connected component into a directed acyclic graph
with just modifying 83 source packages.
The problem here is, that any of the packages in that strongly connected
component is a (direct or indirect) reverse dependency of every other
package in it. And also depending on which source packages are selected
to be profile built, different orders are produced. And these different
orders can all behave differently due to the kind of problem Wouter
pointed out: because all packages in the SCC are potential (direct or
indirect) reverse dependencies. And one can only reliably rebuilt all
source packages of an SCC once all profile built packages have been
rebuilt. But this again is only possible for all profile built source
packages after all of the SCC has been solved.
So there is no obvious solution of this problem to me because the size
of the problem is a 900-100 big graph. Unfortunately, the size of this
graph is also growing with Debian over time (as I already noted in our
inital email): http://blog.mister-muffin.de/images/dep_graph_scc.svg
cheers, josch
Reply to: