Friday 17 June 2011

Muddle dependency visualisation

For about as long as I've been working with muddle, I've felt that it was lacking the ability to get a big-picture view of how a build tree fits together. This led to issue 48. It's not that I have anything against build descriptions being declarative-type programming; just that I sometimes find them hard to follow from scratch and prefer to get an overview.

Over time I hatched a plan to actually do something about this. Well, muddle knows everything it is possible to know about the dependencies; couldn't I put that knowledge to use?

Betraying myself as more of a perl hacker, I initially wrote a perl script which invoked muddle depend user-short, scraped the output and output in dot format. It was grotty and inelegant in a number of ways, but it served as a valid - if slow - proof of concept. Later, I rewrote it properly in python, directly examining the build description. So I had given myself the ability to create dot graphs of a build tree, but it still wasn't all that useful: every label was a separate node, and there were far too many of them, making the output cluttered and hard to understand.

The key insight in reducing the output was that while a muddle package usually gave rise to five labels - preconfig, configured, build, installed, postinstalled - these always appear in strict order. So why not conflate the nodes on the graph? It wasn't quite as simple as unconditionally merging them, as (for example) sometimes one package's built step depends on another package's configured, so I had it search for such dependencies and only reduce the graph as far as it could without throwing away information.

The script was duly committed to the sandbox directory, and languished there for a while. Just recently, Tibs has picked it up again. The graphs output by the script now sport colour-coding to differentially highlight checkouts, packages and deployments - and all of a sudden it's much more legible!

Alongside visualise-dependencies.py there is now a visdep.py wrapper which feeds the output into José Fonseca's xdot viewer script. The wrapper adds the options to choose amongst the various alternative layout filter algorithms (we find fdp often works well), and to pass the graph through tred (transitive reduction of vertices, e.g. if A depends on B, B on C, and A directly on C, you can drop the A-C dependency as it is implicit from the other two).

For example, a build tree I've been working on recently has a beagle-boot deployment, so here is the output from ~/muddle/sandbox/visdep.py deployment:beagle-boot/deployed :

If you want to have a play, you'll find it in the sandbox directory. For the time being you will need to install xdot.py somewhere on your PATH (see the comment at the top of visdep.py). Then invoke visdep.py, telling it the label(s) you are interested in.

The script is not perfect, being a bit hamstrung by how well dot and friends cope (or fail to cope) with complex graphs: particularly in nontrivial build trees, the output is frequently too cluttered or too sparse. Nevertheless, as you can see from the example above, it's capable of doing a very smart job! We dream of creating a more interactive viewer, perhaps one which allows the user to zoom around a three-dimensional rendering of the graph, but that will have to wait for now...

Muddle logo

Muddle has a new logo!

It came about when I was scrawling notes during a discussion. I found myself instinctively writing an M in a circle as a shorthand for muddle. I showed it around and it was well received.

So a few minutes work in Inkscape cobbling things together, and hey presto! A logo is born. It's a derivative of the FreeSans font ('@' + 'm') so is covered by the FreeFont license, which is GPLv3 with an exception which does not cause documents using it to become bound by the GPL.