Pietro Abate homepage

debtree is a fantastic tool to create colorful graphs of package dependencies. One small shortcoming is that the user cannot provide a Packages.gz file directly to be used as repository. Since debtree is based on the excellent apt_pkg library, it is actually not that difficult to convince apt to look in a different location. To change debtree (and apt-get_ default behaviour you just need to create a new apt-get repository and then set the environment variable APT_CONFIG appropriately.

So ... imagine you create a repository as :

now you need to create a new apt.conf file that looks like :

and now you're ready to play with your new repo :

done.

After few inspiring talks in the drupal room at fosdem I decided to spend few hours to figure out the module dependency system in drupal.

Drupal has a highly modular design. The core is composed by a set of required modules (dependencies) and a set of optional modules (suggests). All contrib modules declare similar dependencies between each other. All dependencies are conjunctive, that is, in order to install a component all its dependencies must be satisfied. There are no conflict between components, and this implies that a module is always installable. The only implicit conflict is that two versions of the same module cannot be installed at the same time. This makes the module installation algorithm trivial as it is equivalent to a simple visit of the dependency graph (that might have cycles).

There is a nice page on the drupal website explaining the format of the metadata for the next version of drupal .

For example :

In order to analyze all modules' dependencies I've downloaded all available modules for the release 6 of drupal (15th Feb 2010), extracted all the meta data and transform them in something that the tools in dose3 can handle. Downloading all projects archives I've also find that there a significant number of archives that cannot be downloaded (403 / 404) and few mistakes in the metadata ... I'll blog about this in the future maybe.

Numbers and intermediate aggregate modules list

From the file .info in each module archive, I extracted all the relevant data and transformed in a 822 format similar to the one used in debian. There are about 4800 modules in the drupal repository for drupal 6.x.

This is a small snippet representing few drupal core modules and a meta package (that I created from the metadata) to express the core's dependencies) :

Dependency graphs

• package:views.dot , views.svg
• number of nodes:684
• max inbound:162

• package:taxonomy.dot , taxonomy.svg
• number of nodes:232
• max inbound:134

• package:upload.dot , upload.svg, upload.pdf
• number of nodes:134
• max inbound:32

• package:token.dot , token.svg, token.pdf
• number of nodes:90
• max inbound:45

• package:search.dot , search.svg, search.pdf
• number of nodes:78
• max inbound:40

• package:menu.dot , menu.svg, menu.pdf
• number of nodes:57
• max inbound:35

• package:locale.dot , locale.svg, locale.pdf
• number of nodes:52
• max inbound:19

• package:comment.dot , comment.svg, comment.pdf
• number of nodes:48
• max inbound:43

• package:imagecache.dot , imagecache.svg, imagecache.pdf
• number of nodes:48
• max inbound:28

• package:date-api.dot , date-api.svg, date-api.pdf
• number of nodes:47
• max inbound:15

The complete list is here

From these graphs, it seems that apart from a couple of dozen of packages, the rest of the drupal components are loosely connected. I don't think this is a matter of code sharing but this is more likely because the drupal repository has a plethora of small components with a very special functionality that only depends on the drupal core.

Dist check

Conclusions

1. Periodic generation of aggregate module metadata information.
2. Dist Check the module repository to avoid releasing a module that is not installable due to a missing dependency.
3. Integrate a developer tool to display all dependency of a module (like debtree, or directly using debtree)
4. As the system grows it might be necessary to review the dependency system to include disjunctive dependencies and conflicts between modules. At present this might be not necessary, Adding more expressivity to the dependency system of course will significantly increase the complexity of the installation problem (from polynomial to NP-complete).

I think it is important to spend few words about this last point. It is clear that not all 4800 packages can be installed at the same time. Just think about the filter modules that manipulate user's submissions. At the moment the only was a site developer has to discover a conflict it to try out the module and check if it did not break anything else on the site. Given the complexity of many drupal site this can be a painful and costly task to perform.

Adding conflicts to the meta data will make modules integration much easier for site developers, and move the burden of finding potential problems to the module developers and to the module installer. As I said before if we include conflicts (that is negation, in logical terms) the problem of installing a new module suddenly become NP-complete. Running a NP complete algorithm on a webserver is of course a bad idea, but using drush offline to run complex install operations, should be completely acceptable as much as it is acceptable to wait for apt-get to install the latest program on debian.

If conflicts are indeed needed it would be fun to have a mod_php_minisat and to implement a small dependency solver in php !

Imagine you want to create hdlist/sysnthesis files from a bunch of rpms on a debian system. If you know what you need it is not actually that difficult. The mandriva svn contains the tool genhdlist2. To use it on a debian machine we need to download and install two perl modules that are contained in the same directory as above, namely, perl-URPMI and MDV-Packdrakeng. The tool we want to use is in the rpmtools directory. You can svn checkout everything from http://svn.mandriva.com/svn/soft/rpm .

Once downloaded everything you would either need to install these perl libraries system-wide (bad idea...) or locally and to fiddle a bit with the genhdlist2 script in order to specify the location of these two libraries. Personally I added these two lines at the beginning of the file :

Make also sure that you compile the URPMI.so component of the perl library and copy it to the lib directory.

Now you are ready to generate your hdlist/systhesis files just by giving a directory with all the rpms to the tool as in perl genhdlist2 rpms

et voila.

Update

You may well ask: "Why direct action? Why sit-ins, marches and so forth? Isn't negotiation a better path?" You are quite right in calling, for negotiation. Indeed, this is the very purpose of direct action. Nonviolent direct action seeks to create such a crisis and foster such a tension that a community which has constantly refused to negotiate is forced to confront the issue. It seeks so to dramatize the issue that it can no longer be ignored. My citing the creation of tension as part of the work of the nonviolent-resister may sound rather shocking. But I must confess that I am not afraid of the word "tension." I have earnestly opposed violent tension, but there is a type of constructive, nonviolent tension which is necessary for growth. Just as Socrates felt that it was necessary to create a tension in the mind so that individuals could rise from the bondage of myths and half-truths to the unfettered realm of creative analysis and objective appraisal, we must we see the need for nonviolent gadflies to create the kind of tension in society that will help men rise from the dark depths of prejudice and racism to the majestic heights of understanding and brotherhood. - Martin Luther King: "Letter from Birmingham"

to read :

• Civil Disobedience, an essay by Henry David Thoreau
• Satyagraha - the practice of non-violent resistance developed by Mohandas Gandhi
• The Letter from Birmingham Jail by Martin Luther King, Jr.