botch-native

The tools will be explained by going through what native.sh does, step-by-step. This way it might be possible to get a good overview of how the tools can work together in a meaningful manner.

botch-native takes three or no positional arguments. If no argument is given, then botch-download-pkgsrc is run to download a default set of Packages and Sources files from http://snapshot.debian.org.

botch-download-pkgsrc

botch-download-pkgsrc takes two or no positional arguments. If no argument is given, then a default set of Packages and Sources for amd64 is downloaded from http://snapshot.debian.org. Otherwise the two positional arguments are an architecture and a suite name which can be any of etch, lenny, squeeze, wheezy, jessie or sid. In addition the suite can be a year from 2007 to 2013 and will then download Debian sid from January 01 that year.

botch-single-version

If the --latest option is given to botch-native, then botch-single-version will be run on the input Packages file.

botch-single-version takes two positional arguments which are the input and output Packages files. If either of them is a - then data is read from standard inptut or written to standard output, respectively. It goes through all packages in the given file and keeps for each architecture, the package with the highest version.

botch-clean-repository

If the --clean options is given to botch-native, then botch-clean-repository will be run on the input Packages and Sources files.

botch-clean-repository removes all binary packages which:

  • can't be installed
  • don't have a corresponding source package (Architecture:all binary packages are excluded from this check by default. This can be changed with the --reqsrcarchall option)

botch-clean-repository also removes all source packages which:

  • can't be compiled
  • do not produce any binary packages (Source packages only producing Architecture:all binary packages are removed by default. This can be changed with the --addsrcarchall option)

botch-clean-repositoryTerminology

botch-build-closure also outputs a self-contained repository but while botch-build-closure results in roughly the smallest possible self-contained repository, botch-clean-repository will calculate the biggest possible self-contained repository.

grep-dctrl

After this initial cleanup, grep-dctrl is used to select the binary packages which have to be part of the minimal native build system. The default is:

grep-dctrl -X \( \
    -FPackage build-essential --or \
    -FPackage apt --or \
    -FPackage debhelper --or \
    -FEssential yes \
\)

These packages alone are not enough to be installed together. To find a selection of packages which make it possible to install this selection (a co-installation set), dose-deb-coinstall will be run.

dose-deb-coinstall

dose-deb-coinstall takes a set of foreground packages and a set of background packages. It outputs a set of packages which make it possible to install the foreground packages into the background packages.

botch-bin2src

Lots of operations like those carried out by botch-single-version, botch-clean-repository or dose-deb-coinstall only work on binary packages. But bootstrapping needs a list of source packages as well.

botch-bin2src takes a list of binary packages and outputs the source packages that are needed to build them.

The analogous tool to botch-bin2src is botch-src2bin.

botch-build-closure

If the --self-contained option is given to botch-native then botch-build-closure will be run on the input Packages file.

botch-build-closure is given a minimal selection of co-installable packages and then:

  • adds all source packages that build the included binary packages
  • adds all binary packages needed to compile the included source packages

botch-build-closureTerminology

botch-clean-repository also outputs a self-contained repository but while botch-clean-repository results in the biggest possible self-contained repository, botch-build-closure will calculate the roughly smallest possible self-contained repository.

dose-builddebcheck

If the --self-contained option is given to botch-native then dose-builddebcheck will be run on the output of botch-build-closure.

dose-builddebcheck takes a Packages and Sources file and checks if all source packages in Sources can be compiled with the binary packages in Packages. If not it outputs the reason by giving the arguments --explain and --failures.

botch-build-fixpoint

If the --no-fixpoint option is not given to botch-native then botch-build-fixpoint will be run the input Packages file.

Given a Packages and Sources file, as well as a set of available packages, botch-build-fixpoint finds which source packages are already compilable and adds the resulting binary packages to the set of available packages. This step is repeated until no more source packages can be built. It calcuates the build order of source packages without having to break any build dependencies. This step can help to increase the amount of initially available binary packages which in turn helps to simplify the dependency graph.

The --output-order option specifies a file into which to write the deduced build order.

botch-build-fixpoint writes the list of compilable source packages to standard output.

botch-src2bin

Since botch-build-fixpoint outputs source packages, botch-src2bin has to be used to calculate a list of corresponding binary packages. Given a list of source packages, botch-src2bin outputs the list of binary packages that these source packages build.

botch-packages-union

The list of available binary packages is extended using the tool botch-packages-union. It takes two or more positional arguments. All arguments but the last are treated as input while the last is treated as the output. If the argument is a - then it will be read from standard input or written to standard output, respectively.

botch-packages-union creates a union of all input files, writing the result to the output file. It merges multiple packages files into one, leaving no duplicates.

botch-create-graph

After all these preprocessing steps, botch-create-graph is run to calculate the dependency graph.

botch-create-graphTerminologyArchitecture:all binary packages. All binary packages which are marked as available are not connected to a source package in the dependency graph.

The output of botch-create-graph is given on standard output and redirected to ./buildgraph.xml by botch-native.

The default dependency graph is created by arbitrarily choosing installation sets for binary package installation and source package compilation. The choice of installation sets can be influenced by passing the --custom-is option with a path to a file which lists dependencies that should not part of the calculated installation set.

By default, Build-Depends-Indep dependencies are not considered. This can be changed by passing the --keep-indep option.

Instead of generating an installation set and connecting vertices accordingly with edges, the --strongtype option can be used to calculate strong dependencies while the --closuretype option can be used to calculate dependency closures instead.

botch-buildgraph2srcgraph

After buildgraph.xml has been created botch-buildgraph2srcgraph is used to create srcgraph.xmlTerminology

botch-annotate-strong

If the --strong option is given to botch-native then botch-annotate-strong will be run on the source graph to mark edges as strong or not.

botch-print-stats

After all this processing, the build graph and source graph are analyzed and heuristics for how to make them acyclic are computed by botch-print-stats. Some of these heuristics for the source graph require it to be annotated with strong dependency information first.

botch-print-stats runs all algorithms by default except for calculating strong bridges and strong articulation points which can be calculated by giving the --sapsb option.

The --max-length option indicates the maximum length for the cycles that shall be listed.

The --max-length-fas option indicates the maximum length for cycles that shall initially be used in the feedback arc set algorithm. The list of available binary packages as passed with the --available option is needed to identify self-cycles in the source graph.

Listing dependencies which could possibly be marked as droppable by using build profiles or which could be moved to Build-Depends-Indep requires to specify the list of weak dependencies with the --weak-deps option.

The output of botch-print-stats is given in json format on standard output. It is redirected to ./stats.json by botch-native.

botch-stat-html

Since the json file is not human readable it is converted into html format by botch-stat-html. The output is written to standard output and redirected to stats.html by botch-native.

botch-fasofstats

The existing droppable build dependencies might not have been enough to make the whole graph acyclic. The tool botch-fasofstats extracts a set of build dependencies which would make the graph acyclic from ./stats.json. The output is written to standard output and redirected to ./remove.list by botch-native.

botch-extract-scc

The tool botch-extract-scc extracts all strongly connected components from the build graph and saves them into separate files with a given prefix. The default prefix given by botch-native is cyclic. The output filename is structured as ${prefix}_${pkgname}_${vertnum}.xml where ${prefix} is the selected prefix, ${pkgname} is the smallest package in the strongly connected component and ${vertnum} is the number of vertices in the strongly connected component.

botch-find-fvs

Given a dependency graph and a list of known droppable build dependencies, botch-find-fvs will find a small selection of source packages (a feedback vertex set) which, if their droppable build dependencies were removed from the graph, made the whole graph acyclic.

botch-native runs botch-find-fvs on all extracted strongly connected components and concatenates the resulting selection into the file ./feedback_vertex_set.list.

botch-profile-build-fvs

After a feedback vertex set which would make the graph acyclic has been found, botch-profile-build-fvs is used to modify the build graph accordingly.

botch-profile-build-fvs writes the resulting graph to standard output which is redirected into ./buildgraph_acyclic.xml by botch-native.

botch-partial-order

Given an acyclic source graph, botch-partial-order will output a build order of source packages on standard output. The output is redirected to ./order2.lst by botch-native.

All source packages which can be built in parallel are given in the same line.

botch-graph-info

The tool botch-graph-info takes a buildgraph or source graph as an argument and outputs one line with tab delimetered values. The values are:

  • the filename
  • the graph type (build graph or source graph)
  • the number of vertices
  • the number of edges
  • the number of strongly connected components (if this number is zero, then the graph is acyclic)

Other tools

botch-collapse-srcgraph

A build order can only be deduced from an acyclic graph. Sometimes, only a small remote cycle remains in the source graph which doesnt affect the major part of the graph. In that case, botch-collapse-srcgraph allows to collapse all remaining strongly connected components of the input source graph into one single vertex, thus making the input graph acyclic.

botch-extract-neighborhood

Rendering a big graph takes time and the graph might be too big to make a rendering of it useful. For this purpose, botch-extract-neighborhood allows to extract the neighborhood of a vertex. It takes three positional arguments: the nodename, the input graph and the output graph. The --depth argument allows to specify until what depth the neighborhood shall be extracted.

botch-graph-difference

For regression testing, botch-graph-difference allows to check whether two input graphs are equal or not. It does not calculate which parts are different but just outputs the first difference in case there is one.

botch-graphml2dot

The graphviz tools contain powerful visualization and processing tools but graphs have to be in the dot format. botch-graphml2dot converts an input build graph or source graph in graphml format into dot format for consumption by graphviz tools.

botch-packages-difference

botch-packages-difference works analogous to botch-packages-union and botch-packages-intersection. Given three positional arguments it removes the packages in the second file from the first file and writes the result to the third.

botch-packages-intersection

botch-packages-intersection works analogous to botch-packages-difference and botch-packages-union. Given three positional arguments it outputs all packages to the third file which are present in both, the first and the second.