First steps

Because there was no dose3 upstream release since January 2013, botch needs some features of dose3 which are only available via git. Dose3 itself can only release a new version once a new upstream version of libcudf is released. So dose3 depends on the git version of libcudf as well.

To check out the dose submodule you need git. To check out the libcudf submodule you need ca-certificates.

$ apt-get install git ca-certificates
$ git clone https://gitlab.mister-muffin.de/debian-bootstrap/botch.git
$ cd botch
$ git submodule update --init
$ (cd dose; git submodule update --init;)

You now can install all dependencies to build libcudf, dose3 and botch:

$ apt-get install build-essential ocaml-nox camlp4 libzip-ocaml-dev libbz2-ocaml-dev ocaml-findlib libextlib-ocaml-dev libre-ocaml-dev libocamlgraph-ocaml-dev
$ make doselib
$ apt-get install libatdgen-ocaml-dev libxmlm-ocaml-dev
$ make
$ apt-get install zutils dctrl-tools wget python python-apt python-networkx
$ ./native.sh

Botch is a set of tools which are concatenated in a meaningful manner by ./native.sh. The result of above invocation will be:

  • the files buildgraph.xml and srcgraph.xml which are the buildgraph and sourcegraph in graphml format for the current dependency situation
  • several graphs in graphml format cyclic_src*_*.xml representing the strongly connected components before any dependencies were dropped
  • a file stats.json containing the results of running several heuristics on the cyclic graph that help to make the graph acyclic
  • a file stats.html which contains the information of stats.json in human readable format
  • a file remove.list which contains a close to minimal selection (a feedback arc set) of build dependencies which have to be dropped in addition to the known droppable ones (given by files in the ./droppable directory) to make the graph acyclic
  • a file feedback_vertex_set.list which contains a close to minimal selection (a feedback vertex set) of source packages which were selected to be profile built according to the information in ./droppable and remove.list to make the graph acyclic
  • the files order1.lst and order2.lst which contain the resulting build order to bootstrap the whole distribution

The ./native.sh script makes the assumption that a minimal build system including Essential:yes packages, build-essential and debhelper exists. Look at the --help output for more options. Investigate the script to see how it combines the multiple tools together.

You can also use graphviz to look at the graphs:

$ apt-get install graphviz python-pygraphviz
$ ./tools/graphml2dot < cyclic_src:foo_0.xml > cyclic_src:foo_0.dot
$ dot -Tpng cyclic_src:foo_0.dot > cyclic_src:foo_0.png

The number in the graph filename indicates the amount of vertices. Do not use dot to look at large graphs as computation can take hours. Furthermore, even after computation finished, the result will not be very useful due to the sheer amount of vertices and edges. If you nevertheless want to look at it, use sfdp instead.

Instead of looking at a huge graph you might want to look at the neighborhood of a specific node in the graph:

$ ./tools/extract_neighborhood.py --depth=2 src:foo < cyclic_src:foo_0.xml > foo.xml
$ ./tools/graphml2dot < foo.xml > foo.dot

If that is still too much, try a transitive reduction of the graph (not unique if the graph has cycles):

$ tred < foo.dot > foo_tred.dot

But instead of investigating the graph manually you should really look at and follow the calculated heuristics:

$ iceweasel stats.html