This feed contains pages in the "debtree" category.
Yay! I've done it: 1160 lines of bash script are now 1215 lines of perl, and:
'debtree aptitude': 1m2.832s -> 0m0.596s
The new release is available as version 0.9.9 from the
debtree web site and has been
uploaded for the archive as version 1.0.
This was the starting position, the run time for my complete test set:
real 22m33.583s user 18m29.709s sys 4m21.320s
I began with a pure language conversion from
perl, i.e. I kept
the call-outs to
dctrl-tools. This allowed me to easily identify problems
in the language conversion by running my test suite, without having to worry
that a change might have been caused by getting different data.
The language conversion itself was fairly straightforward; most time was
spent on finding all the little errors made during the conversion.
This resulted in "only" a 10% speedup:
real 20m56.368s user 18m3.996s sys 2m46.986s
bash itself isn't even horribly slower than
perl, even with all the
recursion and starting of subshells for calls to
Then I replaced the call-outs to
dctrl-tools one by one, adding the
libapt-pkg-perl. And that resulted in the amazing:
real 0m21.350s user 0m19.797s sys 0m1.372s
So, from 22 minutes to 21 seconds for 22 graphs, including some pretty complex ones. Not bad.
I had to keep a call-out to
dctrl-tools for build dependencies as it
does not expose architecture conditions.
The full conversion process can be seen in the source repository, which was recently moved from my $HOME on alioth to collab-maint.Posted Wed Sep 16 12:21:02 2009
The new feature is of course documented in the man page, but also on the website.
And now I think the time has come to port the script to
perl. If I manage
that I plan to upload the package into the archive as version 1.0.
debtree now also supports generating trivial graphs:
$ debtree --max-depth=0 dpkg
Funnily enough that same graph is less trivial for
apt. Support for
--max-depth=0 was added to allow to generate graphs showing only
Funny how working on a program immediately inspires to do more.
Remember that the initial motivation for debtree was to find out why a package was installed? It can now show that in the dependency graphs!
I'm not quite ready to do a new release, but the new version is available from the git repository.
Let's start with a simple example (all graphs are based on Lenny).
$ debtree -I --rdeps-depth=3 apt
Only installed packages are displayed here; if the
-I option is omitted,
debmirror will display all, but that does tend to explode the graphs,
especially for common libraries. As for forward dependencies, the color of
the arrows indicates
The reverse dependencies are shown three levels deep (one is default).
The graph will always include all direct reverse dependencies (both on the
package itself and all virtual packages provided by it). For indirect reverse
dependencies there's a cut off that is set at five by default. Example is
debconf, that apparently has 9 reverse
Pre-Depends and 58 reverse
installed on my system.
The next one is simply beautiful.
$ debtree -I --rdeps-depth=20 --no-conflicts libcairo2
Because of the
--rdeps-depth=20 this shows the full recursion! I was
surprised that this graph remained a reasonable size. Apparently no packages
depend on the virtual package
libcairo, at least none that I have installed.
The final one is extreme, and I must confess that I have cheated a bit by
suppressing the least interesting reverse depends (which explains why it does not
match the numbers from the
$ debtree -I -R --no-recommends --no-conflicts debconf
The most interesting thing here is how it shows the
Most packages depend on '
tex-common instead has
exim4 have both combinations
(probably one explicitly in
debian/control and the other added by
ucf is missing the alternative; apparently does not use
prizes for guessing who the maintainer is :-).
Notice anything about
ibritish? Yes, they really have a
double dependency on '
The one thing missing is the version info for versioned dependecies. Not sure yet if I want to add that for reverse dependencies.
P.S. SVG versions of the images are available in the same directory as the JPGs.Posted Tue Sep 8 14:38:19 2009
It's been quite some time (almost two years) since my previous "release"
debtree, but now version 0.7.3 is
And it still generates very nice graphs
The changes are relatively minor: a few nice fixes for corner cases that
were not handled correctly, and an update of the default lists of "skip"
and "end" packages which help to limit the size of graphs for a fair number
of packages I tried (including
Reason to revisit debtree was a recent nice mail from a debtree user, but
also the current discussions about udev and the
FHS. I'm on
the side of "let's please keep
/usr mountable separately". Mostly because
I like a (small) encrypted root with a separate (large) unencrypted `/usr'.
I'm also increasingly unhappy with the default size of Debian's desktop
installs, especially now that it looks as if Squeeze will see installation
of Recommends by default by
tasksel (and thus Debian Installer).
For comparison, the size of a default Gnome desktop install for Etch was 1360MB; for Lenny it is 1830MB; for Squeeze it looks like it will be well over 3000MB! Remember that for Sarge we installed both Gnome and KDE from CD1 with both together taking 1390MB?
Sure, some of that is real functionality, but a lot is also (IMO) redundant
visual effects that only serve to slow the desktop down and junk needed to
do stuff automagically. And a heck of a lot is duplicated functionality.
One of the main reasons I switched to Linux was because it gave me back control
over my systems, but with KDE4 and pervasive stuff like
hal and all the
various "kits" Linux is on a fast track that's giving priority to flashiness
over real functionality and eroding that control.
Here's a fairly default dependency graph for
hal (click for full image).
Looks reasonable, right?
But that's only because most major dependencies, such as
pm-utils have been pruned. Here's a complete graph, with only
omitted (full image is 1.5MB). Truly a tangled web. Scary.
One can also look at it from the other side. Today I upgraded my sid chroot
and found I suddenly needed to install
libdbus-1-3. Why? Reason turned out to be
libcups2, so I checked if I really needed that. And here's why I do.
Most of these dependencies of
libgtk2.0-0 I can understand, but isn't gtk
supposed to be a graphical toolkit library? Couldn't printing support be
implemented in some more specialized Gnome printing toolkit library?
But I'm probably missing something.
debtree home page for a
full overview of how to read the graphs, but here's a quick intro.
Purple arrows are Pre-Depends, blue are Depends and black are Recommends;
green connections show Provides. The green packages are currently installed
in my sid chroot, while the white ones are not. The diamonds show where the
graph has been pruned: dependencies for these packages are not shown.
Now available from alioth:
The main change in this release is a much better display of virtual packages in dependency graphs.
- In regular depependency graphs
debtreenow shows which virtual packages are provided by the requested package, as can be seen in this example for
- If a virtual package is provided by multiple packages, these are now also displayed. To avoid clutter, by default the providing packages are only listed when there are three or less, but that number can be increased.
With this release I consider
debtree "feature complete" when it comes
to the information that is displayed in the graphs. A quick summary:
- can display both regular dependency graphs and build dependency graphs
- by default displays
Conflicts, and any
Providesfor the requested package
- can optionally display
- clearly displays the packages from alternative dependencies
- can show what packages are already installed
- by default displays versions for versioned dependencies
- displays both
Build-Depends-Indepfor build dependency graphs, and takes into account (or displays) architecture conditions in build dependencies
- has various options that can be used to limit the size/complexity of dependency graphs
is lightning fastwell, that is the next thing on the agenda; but it's not slow either!
Currently not supported are displaying
relationships. If there's demand for it, adding them should be trivial.
If you haven't yet, take a few minutes to look at the example graphs on
What's next for
One reason is that
debtree is completely redundant, at least if you
consider the original reason I wrote
to list how a package depends on another package. Just after the release
of 0.7.1 I found out that
aptitude why <package> <package> already
provides that functionality!
I'm tempted to blame Enrico because I asked him if that was possible before starting on
debtree, and Enrico
really is supposed to know such things ! Luckily
debtree now produces
such nice dependency graphs to justify its existence
Anyway, I think that option should probably just be stripped out of
debtree now. And if that is done, maybe it should be renamed to
I also discovered that beside
apt-cache there was already another utility
that produces dependency graphs:
apt-rdepends. While, just like
apt-cache, it lacks most of the features of
debtree, it is quite fast
and, because it is written in Perl, I could possibly port
debtree to Perl
apt-rdepends as an example.
Another reason is that a few people commented that maybe it should not be
a separate package. I somewhat agree with that, but also would not like it
to disappear in something non-descriptive like
debian-goodies. I'd very
much prefer it to eventually see it included in
apt itself, or maybe in
So basically I've been holding back a bit on uploading
debtree to allow
me to consider all this. The next task definitely is a rewrite in a
better language and thereby give
debtree a performance boost.
 To his (and my) defence: that feature was only recently introduced in aptitude.Posted Fri Nov 30 16:15:00 2007
Now available from alioth:
The main change is the addition of a fairly comprehensive man page. Reviews of the man page would be most welcome.
Having the man page also finally allowed me to file an ITP.
Funny that this will be my first actual package in the archive. All my uploads so far have been team maintained D-I components and some NMUs.Posted Thu Oct 18 14:33:44 2007
Another nice new feature with
The new version supports an option
max-depth that can be used to limit the
depth of a graph. I think
debtree now supports all the ways to reduce the
complexity of dependency graphs that can realistically be implemented in shell.
A nice side-effect of this change is that it made it possible to also render other nodes in the graphs more consistently. Suggested packages now also have the diamond shape. And in sets of alternative dependencies "end" packages and unknown packages are now always marked as such.
I also moved the previously hardcoded lists of "end" and "skip" packages to
configuration files. These are managed using
ucf which means that merging local changes with "upstream" updates in new releases
will hopefully be relatively painless.
If you have suggestions of packages to add to these lists, feel free to submit them. Please mail me both the command for the graph you'd like to reduce and the packages you're proposing to add to the lists.
I have one issue left I'd like to implement: displaying alternative "Provides".
And then I think its time to try to get
debtree ported to C++.
P.S. You may encounter #443179 when using
I've submitted a patch (several actually; the first two had a high "brown paper
bag" ratio) that makes use of debconf's
feature, which should
avoid this particular issue for future releases.
Besides the mentioned advantage for substitution in templates of variables that
need to be translated,
Choices-C also allows developers to define a set of
short aliases for choices that make the values used in a configuration script
independent of the actual strings that are displayed to users.
I doubt this feature is well known outside the D-I team. It was implemented in
I've just "released"
The number of options has almost doubled!
It's now possible to suppress Conflicts and to generate full dependency graphs (including packages that are excluded by default). Unknown packages are now marked with a light reddish shading; this could possibly help finding obsolete Conflicts.
I've also added verbosity options and fixed a few minor issues.
But I'm most exited by two completely new features.
Build dependency graphs
Besides dependency graphs for binary packages,
debtree now also generates
build dependency graphs for source packages. It shows both Build-Depends and
It also takes into account architecture conditionals (such as
It is possible to show such conditionals in the graph, but by default it
will just omit any build dependencies not relevant for the selected
Here's an example for
I expected this to be a lot harder to implement, but it proved relatively straightforward. I've been quite pleased with how extensible this script has proven.
Show installed packages
With this feature
debtree gets back to
its original purpose:
providing information about what packages will get installed and why.
When this option is activated,
debtree will shade packages that are already
installed light green. So if a graph is generated for a package that is not
yet installed, it is easy to see what dependencies are already satisfied and
what new packages will be installed.
More importantly, you can also see which dependencies could be avoided because they are only recommended or which extra suggested goodies could be installed.
Here's an example for
This feature can of course also be used for build dependency graphs.
Want to give it a try?
The script or the Debian package can be downloaded from the
page. That also has usage information and more examples.
P.S. I've found yet another example of an
undesired dependency on
Update: fixed broken linkPosted Sun Sep 30 18:07:04 2007
Package dependency graphs on steroids
How an innocent and simple question can lead to strange development.
I was looking for a simple command that would tell me what the dependency path is from one package to some other package. That is, without having to go by trial-and-error using e.g. aptitude.
Actually, I am getting quite annoyed by the fact that I regularly see e.g.
being pulled in when I install something on my (KDE-based) systems and I
wanted to see how exactly they got pulled in. It should be possible to install
e.g. xchat without
being forced to install
gconf2 too, right?
For Sarge I had a similar issue with the
Anyway, possibly there already is something to print dependency paths, but I did not find it. As I had some time free after dropping out of the Installer team, I decided to scratch my own itch.
To get the paths I decided to recurse through dependencies using
and friends, basically building a tree. An old wish was to play with
dot, so I thought it would be nice to visualize
the tree and so verify my code (conveniently forgetting about
I soon had something basic working and after that it turned out to be irresistible (and surprisingly easy) to keep adding functionality.
The result is that I can now produce graphs like:
This is a fairly simple example. A lot of graphs are much more interesting.
Oh, yes, it also answers my original question:
$ debtree xchat gconf2 xchat -> xchat-common (D) -> gconf2 (D)
The script is quite flexible and now looks solid enough for a first (Beta) release. After a few optimizations the shell script is even acceptably fast (or at least not slow) on my box.
Euhh, what? Shell script?
Yes. As I don't really know any of the popular languages used in Open Source,
writing this in e.g.
perl would just have taken too much time.
OTOH, after some three years of working on
D-I, I have become quite
fluent in shell script. After all, about 80% of the installer (almost all
functionality that does the actual installations — including the
partitioner) is written in shell, so complex systems in shell are
perfectly possible; thanks to Joey we even have a
web server in shell!
And it keeps surprising me how structured you can work in shell if you try a
little. So there.
Of course I'd like to see
debtree re-implemented in another language,
mainly to improve performance. Probably in C++ as that is what
is written in and its 'dotty' function could be a nice starting point.
You'll understand from the above that I'm not going to do this myself, so
if anybody is interested in working with me to do this, please contact me.
debtree seems like it would be a nice addition to Debian, maybe even
apt-cache in apt...
Enjoy!Posted Fri Sep 28 22:11:18 2007