Ciaran McCreesh’s Blag

Now with 17% more caffeine

New Resolver Data Structure Pictures, or, Why I Need Lots of Pens

As some people may or may not have heard, one of the big Paludis projects we’ve been discussing for the past couple of years has been to come up with a super-amazing dependency resolver that can handle ABIs, binaries and chroots perfectly, provide complete customisation so people can do stupid things like “update everything except glibc”, cure cancer, be adapted to support arbitrary new features with no difficulty and explain all of its decisions in an easy to understand manner. Obviously, doing all of that at once is rather ambitious, so in the interests of it ever being finished, I’ve instead been working on a stupid but incrementally expandable resolver designed around:

  • Doing only the basics initially, but having a simple design that cleanly splits apart things like ID selection, dependency selection and ordering, even if doing so prevents certain short cuts from being taken. That way, when we add things in later, we don’t have to rely upon lots of subtle interactions between all the different components.
  • Making sure that we can explain exactly why we’ve done a particular thing, even if this means not including clever trickery.
  • Having easily accessible innards, meaning if people still insist upon having an “upgrade everything except glibc” option, we can easily move a very small amount of code out into a std::tr1::function and let clients handle it that way without having to pollute the resolver.

The basic features all now pretty much work, and cave resolve is usable on Exherbo (although not Gentoo at present, since I haven’t implemented virtuals handling), although there’s no sensible error handling, several obvious optimisations haven’t been made, the UI is highly crude and there are no bells, whistles or cookies. Still. being able to do this is rather fun:

$ cave resolve gnome --explain libbonoboui:2
[snip]

Explaining requested decisions:

For gnome-platform/libbonoboui:2:
    The following constraints were in action:
      * >=gnome-platform/libbonoboui-2.1.1, use installed if possible, installing to /
        because of dependency >=gnome-platform/libbonoboui-2.1.1 from gnome-desktop/gnome-panel-2.26.3:0::gnome
      * >=gnome-platform/libbonoboui-2.1.1, use installed if possible, installing to /
        because of dependency >=gnome-platform/libbonoboui-2.1.1 from gnome-desktop/gnome-panel-2.26.3:0::gnome
      * >=gnome-platform/libbonoboui-2.13.1:2, use installed if possible, installing to /
        because of dependency >=gnome-platform/libbonoboui-2.13.1:2 from gnome-platform/libgnomeui-2.24.0:2::gnome
      * >=gnome-platform/libbonoboui-2.13.1:2, use installed if possible, installing to /
        because of dependency >=gnome-platform/libbonoboui-2.13.1:2 from gnome-platform/libgnomeui-2.24.0:2::gnome
    The decision made was:
        Use gnome-platform/libbonoboui-2.24.0:2::gnome
        Install to / using repository installed

Now to the important part: the pretty pictures!

Regular visitors to #exherbo may have noticed me moaning that I don’t have enough pens to implement their feature of choice. Here’s why:

Resolver Design 7

Resolver Design 7

Since I can’t keep track of more than around five classes at once in my head, I have to have summaries written out on paper. Furthermore, each class summary has to be in a different colour (although my scanner’s done a fairly good job of hiding that in the picture above…), which means I need a pen (a proper fountain pen, or I can’t write with it) for each class. This in turn means that any new feature will likely require one or more additional pens, and I am more or less at my limit.

I also need a couple of colours spare to be able to scribble all over the diagrams, draw lines, change things and generally make a huge mess of things. An earlier design page now looks like this (and note that this is the most readable of the earlier design pages):

Resolver Design 5

Resolver Design 5

On top of that, any problem too complicated to be solved in my head gets its own highly weird picture drawn out. Unfortunately the only example of this that I have handy (working out a circular dependency breaking algorithm) is on A3 paper, which I can’t easily scan…

I’ve found that working on paper for this kind of thing is much faster than working on a computer (writing’s as fast as typing, but the layout’s much quicker on paper, and scribbling over computerised designs doesn’t work). I don’t use a formal design system at this stage because it’s more pain than it’s worth, especially when there’s no need for other people to be able to read the design without being able to ask questions, although in some ways what I do is close to CRC cards with all the bits I don’t need ripped out.

I do not claim that my system is sane; merely that it works.

About these ads

4 responses to “New Resolver Data Structure Pictures, or, Why I Need Lots of Pens

  1. dagger September 10, 2009 at 7:57 am

    That looks pretty nice. Now the pen talk makes some sense.

    We’ve been moaning about pens, but you still haven’t add a proper pen set to your wishlist! ;)

    Thanks for your work

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

Follow

Get every new post delivered to your Inbox.