This page serves as a resource for Debian maintainers and developers to identify how they can help to improve the situation of bootstrapping Debian.

Decide on a stage build format

Bug#661538 is so far the main place for discussion. The currently prefered solution is "build profiles", proposed by Guillem Jover. Other solutions are available in a document of his.

Build-Depends: huge (>= 1.0) [i386 arm] <!embedded !bootstrap>, tiny

If a build dependency is not used by one or more profiles than the names of those profiles follow that dependency in < and > "brackets" in a similar way that architectures are specified. Same applies for dependencies that are only required in one or more profiles. As with architecture specifications, it is not permitted for some profiles to be prepended with exclamation marks while others are not.

Patrick McDermott patched dpkg with support for this syntax while Johannes Schauer patched dose3. The patches show that implementing the above proposal is trivial and mostly borrows code from the existing architecture parsing.

We need to make this proposal either more official or need critique on it.

Uses for profile builds are:

Does arch:all mean M-A: foreign as a build dependency?

Multiarch Spec says for runtime dependencies:

  • Pre-multiarch, architecture-dependent packages may depend on Architecture: all packages and assume that the transitive dependencies will be resolved using packages of the same architecture or other packages that are Architecture: all. To avoid breaking this assumption, Architecture: all packages will, at least initially, be treated as equivalent to packages of the native architecture for all dependency resolution. This means that for an Architecture: all package to satisfy the dependencies of a foreign-architecture package, it must be marked Multi-Arch: foreign or Multi-Arch: allowed.

But for cross build dependencies Ubuntu apt assumes that architecture:all packages are implicitly Multi-Arch: foreign. Debian apt doesnt do this.

There is a discussion in bug#666772 about this.

Chicken and egg problem of Packages and Sources files

The algorithms can only work correctly if the Packages and Sources input is correct. While the Sources file already exists, generating a Packages file for the new architecture requires to actually compile source packages. This is because the content of a Packages file is generated from a source package's debian/control file. Generating correct Packages files for a new architecture would require to retrieve and convert their debian/control files.

Have apt resolve cross build dependencies correctly

It seems that dependencies on packages that are architecture:all and Multi-Arch:none are currently not properly resolved. See bug#683786.

Remove blockers for :any and :native introduction

Currently, :any and :native qualifiers cannot be added to dependencies because wanna-build doesnt understand the syntax. Without the qualifiers, all packages depending on M-A: allowed packages (gettext, python) will not be able to satisfy their cross build dependencies. Fixing wanna-build could be easy as it only builds natively and therefor only needs to be able to ignore any qualifiers.

Find a solution for hard dependencies on build tools during cross compilation

Some packages explicitly depend on gcc, binutils or other build tools to (for example) express a version constraint. This is hindering during cross compilation, as the dependencies are not gcc or binutils but indeed gcc-<triplet>-cross and binutils-<triplet>-cross. Two possible solutions exist:

Introduce an extra cross compilation header for source packages

It would be helpful for a porter if source packages would contain the information whether or not they are cross compilable. An algorithm could then make statements like:

here is a native build dependency that cannot be broken with the current knowledge I have about droppable build dependencies, but I see that the source packages required to make it available are all supposedly cross compilable, so you might want to mark them to be cross compiled

Source packages of the minimal build system (priority:essential and build-essential) must have this flag set to true.

It would be considered a bug if a source package with that flag set to true does not properly cross compile. The package would have to be fixed or the flag removed (if the source package is not part of the minimal build system).

Possible ideas for names:

Cross-Builds: Yes
Does-Cross-Build: Yes
Allows-Cross-Build: Yes

Another use would be for source packages that for some reason cannot be made to cross compile within reasonable effort. Such package can then be made Cross-Builds: No to inform botch that it has to find a way to work around that package somehow.

Improve Cross-Buildability

See https://wiki.ubuntu.com/MultiarchCross.

Many packages would cross-build just fine if their cross-build-dependencies could be resolved using multiarch.

Test cross-build-dependency resolution with:

sudo apt-get --simulate --host-architecture=armel build-dep $yourpackage

You can also get the set of packages who's build-deps are available by using dose-buildcheckdeps:

dose-builddebcheck --successes  --deb-native-arch=amd64 --deb-foreign-archs=armhf,linux-any  --deb-host-arch=armhf \
 /var/lib/apt/lists/archive.ubuntu.com_ubuntu_dists_quantal_main_binary-amd64_Packages \
 /var/lib/apt/lists/archive.ubuntu.com_ubuntu_dists_quantal_main_source_Sources

You need the package dose-builddebcheck installed, and you need at least version 3.1 to analyses cross-build deps. That is initially only available from here:https://launchpad.net/~linaro-foundations/+archive/cross-build-tools/

To analyse things step-by-step for a new port you need a local repository

It is most important that the following list of packages cross compiles:

The above packages must be cross compiled to provide a base system containing essential packages, build-essential and its dependencies and debhelper.

Here is a table of the currently unsatisfied cross-build-dependencies:

unsatisfied cross-build-dependency

source packages failing because of it

tcl-dev

db

autoconf

acl, attr, binutils, gdbm, libsigsegv, make-dfsg, shadow, slang2, tar

texlive-latex-base

bash, mpfr4

python

bsdmainutils, build-essential, file, glib2.0, linux

dh-buildinfo

coreutils

po-debconf

dash, insserv, sysvinit, util-linux

texi2html

diffutils, e2fsprogs

libtimedate-perl

dpkg

perl-modules

eglibc, gettext, libtext-charwidth-perl, libtext-iconv-perl, libxml2, xz-utils

dejagnu

findutils, libffi

locales

gawk

gsfonts-x11

gcc-4.7

libgcj-common

gcc-defaults

mingw-w64

gzip

gem2deb

libselinux, libsemanage

docbook-xml

pam

netbase

perl

Many of the cases in above table could be resolved by either making the binary package in the first column Multi-Arch: foreign or by making it Multi-Arch: allowed and adding the :any modifier to the source packages in the second column.

Out of the packages of above table, the following packages are marked Multi-Arch: foreign in Ubuntu Quantal, but not in Debian Sid:

Besides making the actual build system able to cross compile the sourcecode, the following measures will make the cross-build-dependencies resolvable for more packages:

Make lib*-dev packages Multi-Arch: same

Make lib*-dev packages Multi-Arch: same if applicable.

Mark build tools as Multi-Arch: allowed

Mark build tools as Multi-Arch: allowed if applicable.

The following packages are also Multi-Arch: allowed in Ubuntu Quantal but it's never made use of it:

Mark dependencies on Multi-Arch: allowed packages as :any

Mark dependencies on Multi-Arch: allowed packages as :any if applicable.

The following source packages depend on gettext but are missing the :any modifier.

The above packages all depend on gettext:any instead of just gettext in Ubuntu Quantal, so the :any modifier should be the right choice for them. There are no other packages in Ubuntu Quantal that use the :any modifier.

The following source packages depend on gettext but are missing the :any modifier as well. Though they were not found out by comparison with Ubuntu but by dose3:

Mark dependencies as :native

Mark dependencies as :native if applicable.

More Multi-Arch

It is always useful for multiarch cross building to make more packages Multi-Arch aware. Here is a list of packages that are Multi-Arch: none in Debian Sid but not in Ubuntu Quantal:

package

multiarch status in Quantal

bash-completion

foreign

bsdmainutils

foreign

cpio

foreign

dh-buildinfo

foreign

docbook

foreign

docbook-dsssl

foreign

docbook-utils

foreign

docbook-xml

foreign

docbook-xsl

foreign

findutils

foreign

flex

foreign

gettext

allowed

gir1.2-farstream-0.1

same

gperf

foreign

help2man

foreign

hicolor-icon-theme

foreign

initscripts

foreign

libao-common

foreign

libao-dbg

same

libao-dev

same

libao4

same

libatkmm-1.6-1

same

libatkmm-1.6-dbg

same

libatkmm-1.6-dev

same

libbonobo2-0

same

libbonobo2-common

foreign

libbonobo2-dev

same

libbonoboui2-0

same

libbonoboui2-common

foreign

libbonoboui2-dev

same

libcairomm-1.0-1

same

libcairomm-1.0-dev

same

libdbusmenu-qt2

same

libgdu-dev

same

libgdu0

same

libgif4

same

libglade2-0

same

libglade2-dev

same

libgnomecanvas2-common

foreign

libgnomeui-0

same

libgnomeui-common

foreign

libgnomeui-dev

same

libgtk-3-0-dbg

same

libgtkmm-2.4-1c2a

same

libgtkmm-2.4-dbg

same

libgtkmm-2.4-dev

same

libidl-dev

same

libidl0

same

libiec61883-0

same

libjpeg62-dbg

same

libmount1

same

libnih-dbus-dev

same

libnih-dbus1

same

libnih-dev

same

libnih1

same

liborbit2

same

libpango1.0-0-dbg

same

libpangomm-1.4-1

same

libpangomm-1.4-dbg

same

libpangomm-1.4-dev

same

libppl0.11-dev

same

libspeechd2

same

libstartup-notification0

same

libstartup-notification0-dev

same

libtool

foreign

libwayland0

same

lsb-core

foreign

makedev

foreign

module-init-tools

foreign

nih-dbus-tool

foreign

noweb

foreign

openjdk-6-demo

same

orbit2

foreign

pkg-config

foreign

pkg-kde-tools

foreign

po-debconf

foreign

pulseaudio-utils

foreign

qt-at-spi

same

rsync

foreign

sharutils

foreign

sysv-rc

foreign

sysvinit-utils

foreign

texi2html

foreign

transfig

foreign

upstart

foreign

wireless-regdb

foreign

xfonts-encodings

foreign

There exists the multiarch usertag in the Debian bugtracker. Find all packages tagged multiarch here: http://bugs.debian.org/cgi-bin/pkgreport.cgi?users=multiarch-devel@lists.alioth.debian.org;tag=multiarch

There is also a Multiarch/ToDo.

Cross build from nothing

When bootstrapping a new architecture, then initially no package of the new architecture exists. Out of the list of packages that are most important to be cross-compilable which was posted at the beginning of this section, the following packages do not cross compile:

unsatisfied cross-build-dependency

source packages failing because of it

pkg-config

dpkg, glib2.0, libpipeline

dejagnu

findutils, libffi

flex

libsemanage, man-db

perl

libtext-charwidth-perl, libtext-iconv-perl, libxml2, xz-utils

libncurses5-dev

bsdmainutils, texinfo, util-linux

po-debconf

dash, insserv, sysvinit

gettext

coreutils, eglibc, gawk, grep, libexpat1-dev, sed, tar

autoconf

acl, attr, bash, binutils, gzip, libsigsegv, make-dfsg, shadow, slang2

python

build-essential, file

tcl-dev

db

texi2html

diffutils, e2fsprogs

libc6-dev

gcc-4.7

gcj-4.7-base

gcc-defaults

libtool

gdbm

netpbm

groff

libxml2-dev

libcroco

gem2deb

libselinux

cpio

linux, perl

libmpfr-dev

mpclib

libgmp-dev

mpfr4, ncurses

libcrack2-dev

pam

libglib2.0-dev

pkg-config

libtinfo-dev

readline6

Use Build-Depends-Indep

The control fields Build-Depends-Indep and Build-Conflicts-Indep mark dependencies or conflicts for building architecture:all packages from a source package. Building architecture:all packages is useless when bootstrapping Debian for a new architecture. One is only interested in the architecture dependent packages. Therfore, the Build-Depends-Indep dependencies can be dropped. This greatly helps to reduce the circular dependency situation.

The following source packages build at least one architecture:all package and have no Build-Depends-Indep field and also no binary-indep or build-indep target:

The following source packages build at least one architecture:all package and have no Build-Depends-Indep field and also no build-indep target but a binary-indep target:

The following source packages build at least one architecture:all package and have no Build-Depends-Indep field and also no binary-indep target but a build-indep target:

The following source packages build at least one architecture:all package and have no Build-Depends-Indep field but do have a binary-indep an well as a build-indep target:

The following source packages possess a Build-Depends-Indep field and it could be checked if not more packages can be added to it:

Find more weak build dependencies

We call "weak" build dependencies those packages that have a high likelyhood of being droppable as dependencies from most source packages that need them. Can you extend this list?

The following source packages build-depend on one of the above and could be modified to have them moved into Build-Depends-Indep or marked as not being needed for stage1 profile builds.

Break dependency cycles using staged builds

When bootstrapping using native compilation, then the dependency graph contains one big strongly connected component of about 1000 vertices which means that each package in it is part of a multitude of dependency cycles. It also means that the dependency graph can neither easily be rendered using dot (will take hours of calculation) nor can it be visually inspected by a human.

The following 387 source packages are part of the main scc:

Find source packages (top 100) that are only missing few build dependencies. Maybe these source package can be built without that dependency?

source package

missing build dependencies

src:acpica-unix

flex

src:atkmm1.6

libatk1.0-dev

src:audiofile

libasound2-dev

src:augeas

texlive-latex-base

src:bc

flex

src:binfmt-support

python

src:blas

texlive-latex-recommended

src:boost-defaults

libboost1.49-dev

src:cairomm

libcairo2-dev

src:cloog-ppl

libppl0.11-dev

src:corosync

groff

src:dwarves-dfsg

cmake

src:fftw

mpi-default-dev

src:fftw3

mpi-default-dev

src:flac

doxygen

src:flex

autopoint

src:fontconfig

libfreetype6-dev

src:freetds

libgnutls-dev

src:freetype

libx11-dev

src:fsplib

scons

src:gavl

doxygen

src:gpm

texlive-base

src:guile-1.8

flex

src:icu

doxygen

src:iputils

libssl-dev

src:keyutils

lsb-release

src:lcms2

libtiff4-dev

src:libasyncns

doxygen

src:libatasmart

libudev-dev

src:libconfig

texlive-latex-base

src:libdbd-mysql-perl

libmysqlclient-dev

src:libdbi

jadetex

src:libedit

pmake

src:libesmtp

libssl-dev

src:libevent

libssl-dev

src:libfontenc

xfonts-utils

src:libical

cmake

src:libidl

flex

src:libidn

gcj-jdk

src:libieee1284

python-all-dev

src:libiodbc2

libgtk2.0-dev

src:liblqr

xsltproc

src:libmng

liblcms1-dev

src:liboauth

libcurl4-nss-dev

src:libpcap

flex

src:libquvi

libcurl4-nss-dev

src:libraw1394

docbook-utils

src:libssh2

libgcrypt11-dev

src:libusbx

doxygen

src:libvisual

autopoint

src:libvoikko

python

src:libxfixes

libx11-dev

src:libxkbfile

libx11-dev

src:libxml-parser-perl

libwww-perl

src:libxrender

libx11-dev

src:linux-atm

flex

src:ocaml

tk8.5-dev

src:open-iscsi

flex

src:openipmi

libsnmp-dev

src:openjade

libosp-dev

src:openjade1.3

libosp-dev

src:openjpeg

libtiff4-dev

src:openmpi

libtorque2-dev

src:openssl

bc

src:orc

gtk-doc-tools

src:parted

libdevmapper-dev

src:pkg-kde-tools

cmake

src:pmake

groff

src:ppl

swi-prolog

src:qt-assistant-compat

libqt4-dev

src:rarian

xsltproc

src:rasqal

libraptor2-dev

src:readline5

lsb-release

src:rtmpdump

libgnutls-dev

src:schroedinger

liborc-0.4-dev

src:source-highlight

libboost-regex-dev

src:tidy

xsltproc

src:usbutils

libusb-1.0-0-dev

src:v4l-utils

libqt4-dev

src:xcb-util

libxcb1-dev

src:xmlrpc-c

libcurl4-openssl-dev

src:xmlstarlet

libxslt1-dev

src:xmlto

xsltproc

src:xvidcore

yasm

src:alsa-lib

python-dev, doxygen

src:apr

python, doxygen

src:apt

xsltproc, libcurl4-gnutls-dev

src:attica

libqt4-dev, cmake

src:autogen

texlive, guile-1.8-dev

src:automoc

libqt4-dev, cmake

src:blt

tk8.5-dev, tk8.4-dev

src:clutter-gesture

libclutter-1.0-dev, gtk-doc-tools

src:clutter-imcontext

libclutter-1.0-dev, gtk-doc-tools

src:dbus-glib

libdbus-1-dev, gtk-doc-tools

src:djvulibre

libtiff4-dev, graphicsmagick-imagemagick-compat

src:dnsmasq

libidn11-dev, libdbus-1-dev

src:eet

libgnutls-dev, doxygen

src:esound

libaudiofile-dev, libasound2-dev

src:firebird2.5

libicu-dev, libedit-dev

src:gamin

python-support, python-all-dev

Find source packages (top 50) that build-depend on many others but are only needed by few binary packages which are in turn only needed buy a few source packages. Maybe the source packages that need those few binary packages can be built without them?

In other words: The source package in the first column draws in many binary packages as build dependencies (amount in the second column). But that source package must only be built because of few binary packages (third column) which in turn are only needed by few other source packages as build dependencies (fourth column). If the source packages in the fourth column could be built without the binary packages in the third column, then the source package of the first column would not be needed anymore and would therefor not draw in the amount of binary packages in the second column.

source package

missing build dependencies

source package is needed by

those packages are build dependencies of

src:evolution

43

evolution-dev

src:tracker

src:gnome-panel

28

libpanel-applet-4-dev

src:tracker

src:tracker

26

libtracker-sparql-0.14-dev

src:nautilus

src:matplotlib

25

python-matplotlib

src:python-numpy

src:iceweasel

22

libmozjs-dev

src:libproxy

src:libvirt

22

libvirt-dev

src:redhat-cluster

src:metacity

21

metacity

src:openjdk-6

src:pacemaker

18

pacemaker-dev

src:redhat-cluster

src:imagemagick

17

imagemagick

src:iceweasel

src:gpac

15

libgpac-dev

src:x264

src:subversion

15

subversion, libsvn-perl

src:git

src:kde4libs

27

kdelibs5-dev

src:subversion, src:libproxy

src:dia

12

dia

src:tracker

src:libunique3

12

libunique-3.0-dev

src:gnome-disk-utility

src:gnome-keyring

11

gnome-keyring

src:libgnome-keyring

src:heartbeat

22

pacemaker-dev, libheartbeat2-dev

src:pacemaker, src:redhat-cluster

src:rrdtool

11

librrd-dev

src:lm-sensors

src:upower

11

libupower-glib-dev

src:tracker

src:opencv

21

libopencv-dev, libhighgui-dev, libcvaux-dev, libcv-dev

src:libav, src:frei0r

src:libnl3

10

libnl-route-3-dev, libnl-genl-3-dev, libnl-3-dev

src:network-manager

src:python-qt4

20

python-qt4-dbus, python-qt4, pyqt4-dev-tools

src:libffado, src:matplotlib

src:telepathy-glib

10

libtelepathy-glib-dev

src:gnome-panel

src:libwnck3

9

libwnck-3-dev

src:gnome-panel

src:redhat-cluster

9

libdlm-dev, libcman-dev

src:lvm2

src:x11-xserver-utils

9

x11-xserver-utils

src:libbonoboui

src:elinks

8

libdbus-glib-1-doc

src:evolution-data-server

src:lirc

8

liblircclient-dev

src:pulseaudio

src:nautilus

16

libnautilus-extension-dev

src:tracker, src:gnome-disk-utility

src:php5

24

php5-dev, php5-cli, php5-cgi

src:swig2.0, src:libvpx, src:graphviz

src:swi-prolog

8

swi-prolog

src:ppl

src:totem-pl-parser

8

libtotem-plparser-dev

src:tracker

src:vala-0.14

8

valac-0.14

src:telepathy-glib

src:ecore

15

libecore-dev, libdbus-c++-dev, libdbus-c++-bin

src:libffado, src:dbus-c++

src:mx

15

libmx-dev, evolution-dev

src:tracker, src:evolution

src:evolution-data-server

21

libedataserverui-3.0-dev, libedataserver1.2-dev, libecal1.2-dev, libebook1.2-dev, libebackend1.2-dev, libcamel1.2-dev, evolution-dev, evolution-data-server-dev

src:tracker, src:gnome-panel, src:evolution

src:jack-audio-connection-kit

7

libjack-dev

src:pulseaudio

src:libffado

14

libffado-dev

src:jackd2, src:jack-audio-connection-kit

src:python-imaging

7

python-imaging

src:matplotlib

src:evas

12

libevas-dev, libecore-dev

src:dbus-c++, src:ecore

src:libchamplain

12

libchamplain-gtk-0.12-dev, evolution-dev

src:tracker, src:evolution

src:libgnomeprintui

6

libgnomeprintui2.2-dev

src:wxwidgets2.8

src:linuxdoc-tools

6

linuxdoc-tools

src:iproute

src:pygobject

18

python3-gi, python-matplotlib, python-gobject, python-gi

src:dbus-python, src:dbus, src:python-numpy

src:openjdk-6

28

openjdk-6-jdk, default-jdk

src:swig2.0, src:qdbm, src:java-atk-wrapper, src:swi-prolog, src:libbluray

src:libgnomeui

16

libgnomeui-dev

src:iceweasel, src:graphviz, src:dia

src:dbus-c++

5

libdbus-c++-dev, libdbus-c++-bin

src:libffado

src:ffms2

5

libffms2-dev

src:x264

src:gtkmm2.4

5

libgtkmm-2.4-dev

src:dbus-c++

src:llvm-2.9

5

llvm-2.9-dev

src:mesa

src:polkit-qt-1

5

libpolkit-qt-1-dev

src:kde4libs

Find binary packages (top 100) that are only needed by few source package but need many other source packages to be built to satisfy their runtime dependencies. Maybe the source package that needs this binary package can be built without it?

In other words: The binary package in the first column draws in many source packages (amount in the second column) because of its installation set. If the source package in the third column could be built without the binary package in the first column, then the binary package in the first column would not be needed anymore and would therefor not draw in the amount of source packages in the second column.

binary package

needs source packages

is build dependency of

evolution-dev

86

src:tracker

libbonoboui2-dev

76

src:libgnomeui

metacity

66

src:openjdk-6

zenity

57

src:metacity

libchamplain-gtk-0.12-dev

55

src:evolution

libmx-dev

55

src:evolution

libwebkitgtk-dev

55

src:libproxy

libcvaux-dev

52

src:frei0r

libhighgui-dev

52

src:frei0r

libopencv-dev

52

src:libav

libclutter-imcontext-0.1-dev

50

src:mx

libcluttergesture-dev

50

src:mx

libgtkhtml-4.0-dev

50

src:evolution

libgtkhtml-editor-4.0-dev

50

src:evolution

libpanel-applet-4-dev

47

src:tracker

libwnck-3-dev

47

src:gnome-panel

libcanberra-gtk3-dev

46

src:evolution

libunique-3.0-dev

45

src:gnome-disk-utility

python-matplotlib

45

src:python-numpy

gnome-keyring

44

src:libgnome-keyring

libgcr-3-dev

44

src:gnome-keyring

python-gtk2-dev

44

src:matplotlib

dia

43

src:tracker

libavahi-ui-gtk3-dev

43

src:gnome-disk-utility

libgnomeprintui2.2-dev

42

src:wxwidgets2.8

mauve

42

src:openjdk-6

libecore-dev

41

src:dbus-c++

libgtkmm-2.4-dev

41

src:dbus-c++

libcanberra-gtk-dev

40

src:metacity

python-wxgtk2.8

40

src:matplotlib

libwxgtk2.8-dev

38

src:gpac

kdelibs5-dev

73

src:subversion, src:libproxy

dvipng

36

src:matplotlib

libiodbc2-dev

35

src:soprano

libgoa-1.0-dev

60

src:evolution-data-server, src:evolution

libebook1.2-dev

29

src:evolution

pacemaker-dev

29

src:redhat-cluster

libwebkitgtk-3.0-dev

57

src:zenity, src:gnome-online-accounts

pyqt4-dev-tools

28

src:libffado

x11-utils

27

src:java-atk-wrapper

libcogl-pango-dev

26

src:clutter-1.0

libcv-dev

52

src:libav, src:frei0r

libedataserverui-3.0-dev

52

src:gnome-panel, src:evolution

libphononexperimental-dev

26

src:phonon-backend-gstreamer

libgnomeui-dev

77

src:iceweasel, src:graphviz, src:dia

libclutter-gtk-1.0-dev

50

src:libchamplain, src:evolution

libgnomeprint2.2-dev

25

src:libgnomeprintui

gir1.2-clutter-1.0

47

src:mx, src:libchamplain

libtotem-plparser-dev

23

src:tracker

openjdk-6-jdk

46

src:swi-prolog, src:libbluray

libcogl-dev

22

src:clutter-1.0

libnautilus-extension-dev

44

src:tracker, src:gnome-disk-utility

gcj-4.7-jdk

42

src:openjdk-6, src:ecj

latex-beamer

21

src:transfig

libevas-dev

21

src:ecore

libpolkit-qt-1-dev

21

src:kde4libs

texlive-font-utils

21

src:transfig

texlive-generic-recommended

21

src:libgcrypt11

texlive-lang-cyrillic

21

src:dia

texlive-lang-german

21

src:transfig

librsvg2-bin

41

src:imagemagick, src:iceweasel

python-gtk2

41

src:dia, src:avahi

libdbusmenu-qt-dev

20

src:kde4libs

libqca2-dev

20

src:kde4libs

libsoprano-dev

20

src:kde4libs

texlive-binaries

20

src:linuxdoc-tools

librdf0-dev

19

src:soprano

libgail-dev

37

src:webkit, src:libgnomecanvas

libnm-glib-dev

18

src:geoclue

texlive-fonts-extra

18

src:opencv

gir1.2-gtk-2.0

35

src:webkit, src:mx

imagemagick

17

src:iceweasel

libgweather-3-dev

51

src:gnome-panel, src:evolution-data-server, src:evolution

libpangomm-1.4-dev

17

src:gtkmm2.4

libpoppler-glib-dev

17

src:tracker

librrd-dev

17

src:lm-sensors

libvirt-dev

17

src:redhat-cluster

python-tk

17

src:matplotlib

python-tk-dbg

17

src:python-imaging

swi-prolog

17

src:ppl

x11-xserver-utils

17

src:libbonoboui

libgdata-dev

31

src:evolution-data-server, src:evolution

default-jdk

46

src:swig2.0, src:qdbm, src:java-atk-wrapper

gnome-common

15

src:gnome-online-accounts

libgnome-desktop-3-dev

45

src:nautilus, src:gnome-panel, src:evolution

libgnome2-dev

60

src:libgnomeui, src:libbonoboui, src:iceweasel, src:dia

librasqal3-dev

15

src:redland

libstreamanalyzer-dev

15

src:kde4libs

libcamel1.2-dev

29

src:tracker, src:evolution

apache2-prefork-dev

14

src:php5

apache2-threaded-dev

14

src:subversion

libecal1.2-dev

28

src:gnome-panel, src:evolution

libffms2-dev

14

src:x264

librest-dev

14

src:gnome-online-accounts

ocaml

14

src:findlib

python-qt4

28

src:matplotlib, src:libffado

gnome-icon-theme

41

src:pygtk, src:gtkhtml4.0, src:evolution

libedataserver1.2-dev

27

src:gnome-panel, src:evolution

gir1.2-soup-2.4

13

src:webkit

libgnomecanvas2-dev

39

src:libgnomeui, src:libgnomeprintui, src:libbonoboui

Note: src:php5 can probably be built using a profile with almost none of its B-D, since they’re for extensions, which aren’t normally needed when a package build-depends on something PHP-ish. Also, I’ve posted to the bootstrap list a few packages that can easily be reduced in GNOME land already. --mirabilos

Break small dependency cycles

Big dependency situations cannot be resolved without the smaller cycles being resolved. Dependency cycles are always of even length as source vertices depend only on binary vertices and binary vertices depend only on source vertices.

Here a more recent and more accurate list of self-cycles: DebianBootstrap/SelfCycles

Cycles with length 2:

src:atlas -> libblas-test
src:atlas -> liblapack-pic
src:avahi -> libgtk2.0-dev
src:avahi -> libgtk-3-dev
src:avahi -> python-gtk2
src:colord -> libgtk-3-dev
src:cups -> ghostscript
src:cyrus-sasl2 -> heimdal-multidev
src:cyrus-sasl2 -> libldap2-dev
src:cyrus-sasl2 -> libpq-dev
src:dbus -> libdbus-glib-1-dev
src:dbus -> python-dbus
src:ecj -> gcj-4.7-jdk
src:ecj -> gcj-jdk
src:gconf -> libgtk-3-dev
src:gnutls26 -> gtk-doc-tools
src:ijs -> ghostscript
src:java-atk-wrapper -> default-jdk
src:libav -> libcv-dev
src:libav -> libopencv-dev
src:libfontenc -> xfonts-utils
src:libproxy -> libwebkitgtk-dev
src:libtasn1-3 -> gtk-doc-tools
src:openldap -> heimdal-dev
src:opensp -> openjade1.3
src:phonon-backend-gstreamer -> libphonon-dev
src:python2.7 -> gdb
src:python2.7 -> lsb-release
src:python2.7 -> python
src:python-numpy -> python-matplotlib
src:vala-0.16 -> valac
src:x264 -> libavformat-dev
src:x264 -> libffms2-dev

Cycles with length 4:

src:atlas -> ghostscript -> src:avahi -> python-gtk2
src:avahi -> libgtk2.0-dev -> src:cups -> ghostscript
src:avahi -> libgtk2.0-dev -> src:cups -> libavahi-client-dev
src:avahi -> libgtk2.0-dev -> src:cups -> libavahi-common-dev
src:avahi -> libgtk2.0-dev -> src:cups -> libavahi-compat-libdnssd-dev
src:avahi -> libgtk2.0-dev -> src:gtk+2.0 -> libcups2-dev
src:avahi -> libgtk-3-dev -> src:colord -> libsane-dev
src:avahi -> libgtk-3-dev -> src:cups -> ghostscript
src:avahi -> libgtk-3-dev -> src:cups -> libavahi-client-dev
src:avahi -> libgtk-3-dev -> src:cups -> libavahi-common-dev
src:avahi -> libgtk-3-dev -> src:cups -> libavahi-compat-libdnssd-dev
src:avahi -> libgtk-3-dev -> src:gtk+3.0 -> libcups2-dev
src:avahi -> libqt4-dev -> src:qt4-x11 -> libcups2-dev
src:avahi -> libqt4-dev -> src:qt4-x11 -> libgtk2.0-dev
src:avahi -> python-gtk2 -> src:cups -> ghostscript
src:avahi -> python-gtk2 -> src:cups -> libavahi-client-dev
src:avahi -> python-gtk2 -> src:cups -> libavahi-common-dev
src:avahi -> python-gtk2 -> src:cups -> libavahi-compat-libdnssd-dev
src:avahi -> python-gtk2 -> src:gtk+2.0 -> libcups2-dev
src:avahi -> python-gtk2 -> src:pygtk -> gnome-icon-theme
src:avahi -> python-gtk2 -> src:pygtk -> libglade2-dev
src:avahi -> python-gtk2 -> src:pygtk -> libgtk2.0-dev
src:avahi -> python-gtk2 -> src:python-numpy -> python-matplotlib
src:colord -> libgtk-3-dev -> src:gtk+3.0 -> libcolord-dev
src:cups -> ghostscript -> src:ghostscript -> libcups2-dev
src:cups -> ghostscript -> src:ghostscript -> libcupsimage2-dev
src:cups -> ghostscript -> src:libidn -> gcj-jdk
src:cups -> libijs-dev -> src:ijs -> ghostscript
src:cups -> poppler-utils -> src:poppler -> libgtk2.0-dev
src:curl -> libgnutls-dev -> src:gnutls26 -> gtk-doc-tools
src:curl -> libgnutls-dev -> src:libtasn1-3 -> gtk-doc-tools
src:curl -> librtmp-dev -> src:gnutls26 -> gtk-doc-tools
src:curl -> librtmp-dev -> src:libtasn1-3 -> gtk-doc-tools
src:cyrus-sasl2 -> heimdal-multidev -> src:gnutls26 -> gtk-doc-tools
src:cyrus-sasl2 -> heimdal-multidev -> src:heimdal -> libldap2-dev
src:cyrus-sasl2 -> heimdal-multidev -> src:libtasn1-3 -> gtk-doc-tools
src:cyrus-sasl2 -> heimdal-multidev -> src:openldap -> heimdal-dev
src:cyrus-sasl2 -> heimdal-multidev -> src:openldap -> libsasl2-dev
src:cyrus-sasl2 -> krb5-multidev -> src:krb5 -> libldap2-dev
src:cyrus-sasl2 -> libldap2-dev -> src:gnutls26 -> gtk-doc-tools
src:cyrus-sasl2 -> libldap2-dev -> src:libtasn1-3 -> gtk-doc-tools
src:cyrus-sasl2 -> libldap2-dev -> src:openldap -> heimdal-dev
src:cyrus-sasl2 -> libldap2-dev -> src:openldap -> libsasl2-dev
src:cyrus-sasl2 -> libmysqlclient-dev -> src:mysql-5.5 -> cmake
src:cyrus-sasl2 -> libpq-dev -> src:gnutls26 -> gtk-doc-tools
src:cyrus-sasl2 -> libpq-dev -> src:krb5 -> libldap2-dev
src:cyrus-sasl2 -> libpq-dev -> src:libtasn1-3 -> gtk-doc-tools
src:cyrus-sasl2 -> libpq-dev -> src:openldap -> heimdal-dev
src:cyrus-sasl2 -> libpq-dev -> src:openldap -> libsasl2-dev
src:cyrus-sasl2 -> libpq-dev -> src:postgresql-9.1 -> libldap2-dev
src:dbus -> doxygen -> src:doxygen -> libqt4-dev
src:dbus -> libdbus-glib-1-dev -> src:dbus-glib -> libdbus-1-dev
src:dbus -> libsystemd-daemon-dev -> src:systemd -> libdbus-1-dev
src:dbus -> libsystemd-daemon-dev -> src:systemd -> libdbus-glib-1-dev
src:dbus -> libsystemd-daemon-dev -> src:systemd -> libgtk2.0-dev
src:dbus -> libsystemd-login-dev -> src:systemd -> libdbus-1-dev
src:dbus -> libsystemd-login-dev -> src:systemd -> libdbus-glib-1-dev
src:dbus -> libsystemd-login-dev -> src:systemd -> libgtk2.0-dev
src:dbus -> python-dbus -> src:dbus-glib -> libdbus-1-dev
src:dbus -> python-dbus -> src:dbus-python -> libdbus-1-dev
src:dbus -> python-dbus -> src:dbus-python -> libdbus-glib-1-dev
src:dbus -> python-gobject -> src:pygobject-2 -> dbus-x11
src:dbus -> python-gobject -> src:pygobject -> dbus-x11
src:dbus -> python-gobject -> src:pygobject -> gir1.2-gtk-3.0
src:ffms2 -> libavcodec-dev -> src:x264 -> libffms2-dev
src:ffms2 -> libavformat-dev -> src:x264 -> libffms2-dev
src:frei0r -> libcvaux-dev -> src:libav -> frei0r-plugins-dev
src:frei0r -> libcv-dev -> src:libav -> frei0r-plugins-dev
src:frei0r -> libhighgui-dev -> src:libav -> frei0r-plugins-dev
src:gdb -> gcj-jdk -> src:python2.7 -> gdb
src:gdb -> lsb-release -> src:python2.7 -> gdb
src:gdb -> python-dev -> src:python2.7 -> gdb
src:geoclue -> libsoup-gnome2.4-dev -> src:libproxy -> libwebkitgtk-dev
src:ghostscript -> libijs-dev -> src:ijs -> ghostscript
src:git -> libcurl4-gnutls-dev -> src:gnutls26 -> gtk-doc-tools
src:git -> libcurl4-gnutls-dev -> src:libtasn1-3 -> gtk-doc-tools
src:git -> libsvn-perl -> src:gnutls26 -> gtk-doc-tools
src:git -> libsvn-perl -> src:libtasn1-3 -> gtk-doc-tools
src:git -> subversion -> src:gnutls26 -> gtk-doc-tools
src:git -> subversion -> src:libtasn1-3 -> gtk-doc-tools
src:glib-networking -> libproxy-dev -> src:libproxy -> libwebkitgtk-dev
src:gnutls26 -> gtk-doc-tools -> src:krb5 -> libldap2-dev
src:gnutls26 -> gtk-doc-tools -> src:libidn -> gcj-jdk
src:gnutls26 -> gtk-doc-tools -> src:openldap -> heimdal-dev
src:gnutls26 -> gtk-doc-tools -> src:openldap -> libgnutls-dev
src:gnutls26 -> gtk-doc-tools -> src:rtmpdump -> libgnutls-dev
src:gnutls26 -> libtasn1-3-dev -> src:libtasn1-3 -> gtk-doc-tools
src:gpac -> libavcodec-dev -> src:x264 -> libgpac-dev
src:gpac -> libavformat-dev -> src:x264 -> libgpac-dev
src:gpm -> texlive-base -> src:libice -> w3m
src:gpm -> texlive-base -> src:libsm -> w3m
src:gpm -> texlive-base -> src:libx11 -> w3m
src:gpm -> texlive-base -> src:libxaw -> w3m
src:gpm -> texlive-base -> src:libxdmcp -> w3m
src:gpm -> texlive-base -> src:libxext -> w3m
src:gpm -> texlive-base -> src:libxfont -> w3m
src:gpm -> texlive-base -> src:libxmu -> w3m
src:heimdal -> libldap2-dev -> src:openldap -> heimdal-dev
src:krb5 -> libldap2-dev -> src:libtasn1-3 -> gtk-doc-tools
src:libav -> libcv-dev -> src:opencv -> libavcodec-dev
src:libav -> libcv-dev -> src:opencv -> libavformat-dev
src:libav -> libcv-dev -> src:opencv -> libswscale-dev
src:libav -> libcv-dev -> src:x264 -> libavformat-dev
src:libav -> libcv-dev -> src:x264 -> libffms2-dev
src:libav -> libopencv-dev -> src:opencv -> libavcodec-dev
src:libav -> libopencv-dev -> src:opencv -> libavformat-dev
src:libav -> libopencv-dev -> src:opencv -> libswscale-dev
src:libav -> libopencv-dev -> src:x264 -> libavformat-dev
src:libav -> libopencv-dev -> src:x264 -> libffms2-dev
src:libav -> libx264-dev -> src:x264 -> libavformat-dev
src:libav -> libx264-dev -> src:x264 -> libffms2-dev
src:libfontenc -> xfonts-utils -> src:libxfont -> libfontenc-dev
src:libfontenc -> xfonts-utils -> src:xfonts-utils -> libfontenc-dev
src:libfontenc -> xfonts-utils -> src:xfonts-utils -> libxfont-dev
src:libgcrypt11 -> texlive-generic-recommended -> src:libice -> xmlto
src:libgcrypt11 -> texlive-generic-recommended -> src:libsm -> xmlto
src:libgcrypt11 -> texlive-generic-recommended -> src:libx11 -> xmlto
src:libgcrypt11 -> texlive-generic-recommended -> src:libxaw -> xmlto
src:libgcrypt11 -> texlive-generic-recommended -> src:libxcb -> xsltproc
src:libgcrypt11 -> texlive-generic-recommended -> src:libxdmcp -> xmlto
src:libgcrypt11 -> texlive-generic-recommended -> src:libxext -> xmlto
src:libgcrypt11 -> texlive-generic-recommended -> src:libxext -> xsltproc
src:libgcrypt11 -> texlive-generic-recommended -> src:libxfont -> xmlto
src:libgcrypt11 -> texlive-generic-recommended -> src:libxmu -> xmlto
src:libgcrypt11 -> texlive-generic-recommended -> src:libxt -> xmlto
src:libgcrypt11 -> texlive-generic-recommended -> src:poppler -> gtk-doc-tools
src:libgcrypt11 -> texlive-generic-recommended -> src:poppler -> libgtk2.0-dev
src:libgcrypt11 -> texlive-latex-base -> src:libice -> xmlto
src:libgcrypt11 -> texlive-latex-base -> src:libsm -> xmlto
src:libgcrypt11 -> texlive-latex-base -> src:libx11 -> xmlto
src:libgcrypt11 -> texlive-latex-base -> src:libxaw -> xmlto
src:libgcrypt11 -> texlive-latex-base -> src:libxcb -> xsltproc
src:libgcrypt11 -> texlive-latex-base -> src:libxdmcp -> xmlto
src:libgcrypt11 -> texlive-latex-base -> src:libxext -> xmlto
src:libgcrypt11 -> texlive-latex-base -> src:libxext -> xsltproc
src:libgcrypt11 -> texlive-latex-base -> src:libxfont -> xmlto
src:libgcrypt11 -> texlive-latex-base -> src:libxmu -> xmlto
src:libgcrypt11 -> texlive-latex-base -> src:libxt -> xmlto
src:libgcrypt11 -> texlive-latex-base -> src:poppler -> gtk-doc-tools
src:libgcrypt11 -> texlive-latex-base -> src:poppler -> libgtk2.0-dev
src:libidn -> gcj-jdk -> src:libtasn1-3 -> gtk-doc-tools
src:libidn -> gcj-jdk -> src:pango1.0 -> gtk-doc-tools
src:libproxy -> libwebkitgtk-dev -> src:libsoup2.4 -> glib-networking
src:libproxy -> libwebkitgtk-dev -> src:webkit -> gir1.2-soup-2.4
src:libproxy -> libwebkitgtk-dev -> src:webkit -> libsoup2.4-dev
src:libtasn1-3 -> gtk-doc-tools -> src:openldap -> heimdal-dev
src:libtasn1-3 -> gtk-doc-tools -> src:openldap -> libgnutls-dev
src:libtasn1-3 -> gtk-doc-tools -> src:rtmpdump -> libgnutls-dev
src:libtasn1-3 -> texlive-latex-base -> src:poppler -> gtk-doc-tools
src:libtasn1-3 -> texlive-latex-base -> src:poppler -> libgtk2.0-dev
src:libxcb -> python -> src:python2.7 -> blt-dev
src:libxcb -> python -> src:python2.7 -> tk8.5-dev
src:libxcb -> python -> src:python2.7 -> xauth
src:libxcb -> python -> src:python2.7 -> xvfb
src:libxcb -> python-xcbgen -> src:python2.7 -> blt-dev
src:libxcb -> python-xcbgen -> src:python2.7 -> tk8.5-dev
src:libxcb -> python-xcbgen -> src:python2.7 -> xauth
src:libxcb -> python-xcbgen -> src:python2.7 -> xvfb
src:libxdmcp -> w3m -> src:w3m -> libimlib2-dev
src:libxext -> w3m -> src:w3m -> libimlib2-dev
src:lvm2 -> libcman-dev -> src:redhat-cluster -> libvirt-dev
src:lvm2 -> libdlm-dev -> src:redhat-cluster -> libvirt-dev
src:matplotlib -> python-gtk2-dev -> src:python-numpy -> python-matplotlib
src:matplotlib -> python-numpy-dbg -> src:python-numpy -> python-matplotlib
src:matplotlib -> python-numpy -> src:python-numpy -> python-matplotlib
src:nautilus -> libtracker-sparql-0.14-dev -> src:tracker -> libnautilus-extension-dev
src:openjade1.3 -> libosp-dev -> src:opensp -> openjade1.3
src:opensp -> jadetex -> src:poppler -> gtk-doc-tools
src:opensp -> poppler-utils -> src:poppler -> gtk-doc-tools
src:poppler -> libgtk2.0-dev -> src:shared-mime-info -> docbook-utils
src:python2.7 -> xvfb -> src:xorg-server -> lsb-release
src:systemd -> valac -> src:vala-0.16 -> dbus-x11

There would be 958 cycles of length 6, 5566 cycles of length 8 and 37839 cycles of length 10. Therfore they are all not listed here.

Find better heuristics

Except for the "weak" build dependencies enumerated above there is no other way for the algorithm to know which build dependencies can easily be dropped. It is up to a human to find source packages that have build dependencies that can be dropped.

Dont hesitate to suggest more methods to solve a build dependency situation. What is your strategy to solve dependency cycles? What are you looking for?