More fun with cross package checks

About a week ago, I wrote about doing cross package checks in Lintian.  At that time I had only played with looking up manpages in direct dependencies, which I hope will greatly improve the current binary-without-manpage stats (around 677 packages and 2750ish tags incl. overrides).

Today, I decided to take on another challenge.  Detection of circular dependencies between binary packages (created from the same source).  We already have a little library for building dependency relationships; however I ended up not using it, since it has an important limitation.  It cannot tell how the circular dependencies relate to each other.

Let me demonstrate what I mean with an example.  Suppose we have a couple packages that depend on each other like this:

pkg-core => pkg-A, pkg-D
# circle 1: A, B, C
pkg-A => pkg-B
pkg-B => pkg-C
pkg-C => pkg-A

# circle 2: D, E, F
pkg-D => pkg-E
pkg-E => pkg-F
pkg-F => pkg-D

In this case, our current tool will be able to tell that all packages (possibly except root – I did not check) are in a circular relationship. However, we can find better results by pretending we are trying to find Strongly Connected Components (actually that is exactly what we are trying to do here).

So today, I implemented Tarjan’s algorithm in Perl to solve this particular issue and committed it to my Lintian branch. If this branch is merged into the Lintian master branch, we can close #316283.

This entry was posted in Debian, Lintian. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s