debtree

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 bash to 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

So bash itself isn't even horribly slower than perl, even with all the recursion and starting of subshells for calls to grep, sed, etc.

Then I replaced the call-outs to dctrl-tools one by one, adding the dependency on 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 turned out libapt-pkg-perl 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 Tags: debian debtree

debtree 0.8.0, including the new option to display reverse dependencies, is now officially (or rather: unofficially) available.

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.

P.S. 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 reverse dependencies.

Posted Sat Sep 12 14:22:48 2009 Tags: debian debtree

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 Pre-Depends, Depends and Recommends.

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 Depends 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 apt graph).

$ debtree -I -R --no-recommends --no-conflicts debconf

The most interesting thing here is how it shows the debconf-2.0 transition. Most packages depend on 'debconf|debconf2.0'; tex-common instead has 'debconf|cdebconf', while tasksel and exim4 have both combinations (probably one explicitly in debian/control and the other added by debhelper. ucf is missing the alternative; apparently does not use debhelper (no prizes for guessing who the maintainer is :-).

Notice anything about iamerican and ibritish? Yes, they really have a double dependency on 'debconf|debconf2.0'.

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 Tags: debian debtree

It's been quite some time (almost two years) since my previous "release" of debtree, but now version 0.7.3 is available. 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 konqueror and openoffice.org).

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 dbus, policykit and pm-utils have been pruned. Here's a complete graph, with only libc6 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 libavahi-client3, libavahi-common3, libavahi-common-data and 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.

Anyway, now that I have a bit more perl experience through my recent work on debmirror, maybe I should finally port debtree from shell script to perl...

See the 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.

Posted Sun Sep 6 15:57:00 2009 Tags: debian debtree

Now available from alioth: debtree 0.7.2.

The main change in this release is a much better display of virtual packages in dependency graphs.

In regular depependency graphs debtree now shows which virtual packages are provided by the requested package, as can be seen in this example for debconf which provides debconf-2.0.
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 Pre-Depends, Depends, Recommends and unversioned Conflicts, and any Provides for the requested package
can optionally display Suggests and versioned Conflicts
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 and Build-Depends-Indep for 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 fast~~ well, that is the next thing on the agenda; but it's not slow either!

Currently not supported are displaying Relaces, Obsoletes and Enhances 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 the debtree website.

What's next for `debtree`?

You may remember that I filed an ITP when 0.7.1 was released but obviously its not in the archive yet.

One reason is that debtree is completely redundant, at least if you consider the original reason I wrote it: 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 [1]! 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 debgraph or apt-graph...

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 myself using 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 apt-utils.

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.

[1] To his (and my) defence: that feature was only recently introduced in aptitude.

Posted Fri Nov 30 16:15:00 2007 Tags: debian debtree

Now available from alioth: debtree 0.7.1.

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 Tags: debian debtree

Another nice new feature with debtree 0.7.0.

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 ucf.

I've submitted a patch (several actually; the first two had a high "brown paper bag" ratio) that makes use of debconf's Choices-C 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 both debconf and cdebconf.

Posted Tue Oct 2 22:13:40 2007 Tags: debian debtree

I've just "released" debtree 0.6.0. 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 Build-Depends-Indep dependencies.

It also takes into account architecture conditionals (such as [!s390]). 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 architecture.

Here's an example for dpkg.

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 clamav.

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 debtree web page. That also has usage information and more examples.

P.S. I've found yet another example of an undesired dependency on gconf2.

Update: fixed broken link

Posted Sun Sep 30 18:07:04 2007 Tags: debian debtree

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. gconf2 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 gimp.

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 grep-available 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 apt-cache dotty...).

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 apt-cache 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 alongside apt-cache in apt...

Enjoy!

Posted Fri Sep 28 22:11:18 2007 Tags: debian debtree

What's next for debtree?

Build dependency graphs

Show installed packages

Want to give it a try?

Package dependency graphs on steroids

What's next for `debtree`?