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 -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20130119104118.GA4367@hoothoot