New Paludis Query Interface

Paludis trunk will be getting a new query interface shortly. This will replace the old interface (we’re not keeping API stability until 1.0), so you’ll need to change your code — fortunately, the compiler will tell you where.

Code that used to look like this:

    env.package_database()->query(
        query::Matches(blah) & query::SupportsAction<InstallAction>(),
        qo_order_by_version);

will now look like:

    env[selection::AllVersionsSorted(
        generator::Matches(blah) | filter::SupportsAction<InstallAction>())];

In particular:

• Querying is now done by Environment, not PackageDatabase. This makes trickery with AdaptedEnvironment easier.
• The QueryOrder enum is gone, replaced with Selection subclasses.
• The Query class is gone, replaced by Generator and Filter subclasses.

The Selection subclasses substantially reduce the amount of work done to get a result in certain circumstances. Previously, a full set of results would be generated, and then that set would be sorted and reduced as specified. But in certain fairly common situations, this is overkill. Consider this old snippet:

    if (env.package_database()->query(query::Matches(spec), qo_whatever)->empty())
        /* ... */

This will return an entire set of PackageID instances, but all we really care about is whether at least one match was found. If spec is something simple, the overhead is minimal. But if spec contains slot dependencies, it means loading or generating metadata for every single matching ID, which is either slow (a metadata load is a filesystem access) or really really slow (a metadata generation is a bash invocation).

Now we do this instead:

    if (env[selection::SomeArbitraryVersion(generator::Matches(spec))]->empty())
        /* ... */

And selection::SomeArbitraryVersion is smart enough to stop trying the match as soon as it finds at least one match. (In future, we might even let IDs state the relative cost of doing such a metadata query, so we can try matching IDs whose metadata is already loaded first.)

The Query to Generator and Filter split enables a related optimisation. Given the following (which is slightly unrealistic, because there should really be an ‘installable’ check in there too):

    env.package_database()->query(
        query::Matches(blah) & query::NotMasked(),
        qo_order_by_version);

the query::NotMasked() would get called for all IDs whose name could potentially match the query::Matches(blah) spec. So if you asked for >=app-misc/foo-3, all versions of app-misc/foo would be checked for whether they’re masked — and a mask check requires metadata.

But with the new code:

    env[selection::AllVersionsSorted(
        generator::Matches(blah) | filter::NotMasked()];

only those IDs that really do match will be queried for maskedness. And if that’s combined with a smarter selection:

    env[selection::BestVersionOnly(
        generator::Matches(blah) | filter::NotMasked()];

then Paludis is now smart enough to start with the best version matching blah and work downwards until it finds a not masked version.

In Part II, we discuss available components and how they can be combined.

Paludis 0.26.2 Released

Paludis 0.26.2 has been released:

• Bug fixes: importare now really adds packages to world by default, as promised in 0.26.0_pre3. pkg_pretend is now properly fatal (ticket:579). There are no longer bogus ‘use flags defined recursively’ messages (ticket:578). Symlink rewriting now works when builddir contains symlinks (ticket:571). The dreaded Ruby bindings segfaults are fixed (ticket:558).
• The Ruby bindings have been extended somewhat.

Installing and Configuring Exherbo

Unfortunately some people think that Exherbo’s assertion that you aren’t supposed to use it means “you’re supposed to use it”. To stop these people from asking the same annoying questions again and again, here’s how you do an install. Note that you will almost certainly find lots of weird and obvious bugs — this is of course a deliberate feature.

• Boot your system off a netboot image or livecd or whatever. Set up your disks and networking.
• Pick a stage based upon arch, datestamp and which developer you think is least likely to have screwed up / deliberately broken things to see if you’re paying attention. Extract said stage into your root.
• Tinker with the Paludis config you get from the stage until you’re happy.
• Do your bootloader and kernel thing.
• Reboot into the stage using init=/bin/bash.
• Set up mounts, device nodes and networking by hand. Hope it’s your lucky day, and try to use Paludis to install Paludis (you’ll need current SCM trunk, not a release). This probably won’t work, because we probably completely changed the exheres-0 format between when your stage was made and when we updated the tree. So install Paludis by hand, then reinstall it using itself.
• Idly consider installing a proper init system. Your choices appear to be:
  • Upstart + either my hacked scripts called ‘rightstart’ that you’ll need to edit by hand because they do fun things like hardcoding mount points that my laptop uses straight into the event scripts or Mike Kelly’s possibly less hacked scripts + Annie.
  • baselayout-1.
  • A shell script.
• Reboot.
• Belatedly realise that no-one told you to set a root password. Curse.
• Try updating things.
• Realise you just wasted the past three days.

Managing Unpackaged Packages, or “What’s this ‘importare’ thing?”

There’s a problem that most Linux distributions don’t solve well: what do you do when there’s no package available for something you want to install? For Gentoo, for example, your options are generally:

• Installing it by hand. Then, when it comes to upgrading or removing it, realising you’re stuck with either nothing at all or autotools’ broken ‘make uninstall’ support. And realise that your depclean / uninstall-unused is broken unless you add dependencies of that package to world, even if you don’t really care about the dependencies.
• Whining “how do I get an ebuild for this package that me and two other people use into the tree?” repeatedly until you give up.
• Writing a really bad (no USE flags, no reliability checking, bad deps and so on) ebuild that works for yourself, and putting it in a local overlay.
• Spend ages writing a good ebuild, and hopefully putting it into a public overlay where it can be neglected once you realise that you don’t really want the package after all, despite having spent three days installing it.

This is even more of an issue for Exherbo, where one of the stated goals is to avoid having packages for things not used by a lot of people (but this isn’t a problem, as we’ll see).

A similar problem is how to handle manual installs of, say, svn or git packages when there’s no scm ebuild available. Either you spend ages making an scm ebuild (possibly for a one-off bug fix test) or you install outside of the package manager and hope for the best (and cry when you have things depending upon that package).

Paludis provides a different solution: importare. This little toy is a tool for using the package manager to install a package where no ‘package’ (ebuild / exheres / rpm / deb / whatever) is available. Specifically, it provides for:

• Clean upgrades and uninstalls of the package.
• Dependency tracking for the package.
• Ability to use that package to satisfy dependencies of other properly-packaged packages.
• Querying packages that have been installed that way, including content queries (‘what provides /bin/foo’?)

To use importare, you need an installed-unpackaged repository. You can’t use an existing VDB or Exndbam repository for tracking installed packages because there’s considerable difference metadata-wise between Ebuild or Exheres generated installs and importare-generated installs. A Paludis repository config file would look something like:

format = installed_unpackaged
location = /var/db/paludis/repositories/installed-unpackaged

Then, make an image of what you want to install under some directory. For autotools packages, you can just do make DESTDIR=/path/to/some/tmpdir install. Other build systems provide a similar option.

Install this image using importare --location /path/to/the/tmpdir category-name/package-name version slot, where:

• category-name/package-name is what you want to call the installed package. If you’re going to use the package to satisfy dependencies, use the same name as the repository package (app-misc/whatever, for example). If not, you might want to use unpackaged/whatever.
• version is the package version. If unspecified, 0 will be used. You can use scm for scm packages.
• slot is the package slot. If unspecified, 0 will be used.

Then you can clean up your temporary directory.

One small caveat: Paludis 0.26 doesn’t realise that it should do an install-uninstall rather than just an install if you install to an installed-unpackaged repository when you have an identical package-slot in a vdb or exndbam repository. If you’re replacing something ebuild-installed or exheres-installed with something importare-installed, you’ll have to tell Paludis to uninstall the previous package afterwards.

A few more options:

• --install-under /foo will install to ROOT/foo rather than ROOT/. This is useful if you’re dealing with packages that are just ‘untar into this directory’.
• --description can be used to provide a description. This will show up in --query and the like.
• --build-dependency and --run-dependency can be used to specify dependencies (both can be provided multiple times). The parameter is a standard package dependency string.
• --preserve-metadata will copy descriptions and dependencies from a previous importare-installed package that is being replaced by this install.

“Elements of Programming” and the ↦ symbol

I’m working my way through the draft of Elements of Programming. And I have a gripe. A small gripe, admittedly, but a gripe non-the-less.

The book uses a lot of symbols. I don’t have a problem with that, and in general it’s more readable that way than spelling everything out. Most of the symbols are defined in an Appendix as well, which is also good. But there is one that is not: the ↦ symbol (or in ascii art, |-->). Here’s an example of its use, taken from page 123:

Definition
abstraction(Op : BinaryOperation)
associative : Op → bool
    op ↦ (∀a, b, c ∈ Domain(op)) op(a, op(b, c)) = op(op(a, b), c)

Whilst the meaning is obvious, I can’t work out how the symbol is supposed to be read. I can’t find that symbol used in reference literature either. The best I can come up with is “Is such that”, but that’s rather clumsy…

Update: Looks like it’s “maps to”. Essentially the associative : line defines the type signature for the associative property, and the last line defines it in terms of a lambda. Looks like mathematicians came up with yet another way of defining functions that I managed to miss. Give me back my λ!

Paludis, Gentoo and Exherbo

Bryan has announced his pet project: Exherbo, a partially-Gentoo-inspired distribution. Exherbo uses the exheres-0 package format, which is implemented by Paludis. Exherbo is currently extremely user hostile, has no installer or documentation and has a huge list of things that don’t work, but then if you care about those kinds of things you’re not a target user just now.

I’ve been running Gentoo on my desktop and Exherbo on my laptop (the first Exherbo install on real hardware) for a while now, and I don’t see that changing for a good while. So for those of you who’re wondering what the situation with Paludis is, and for anyone looking for a link to dispel any “Paludis has its own distribution now” FUD:

• Paludis is going to continue supporting Gentoo and 0/1-based EAPIs. I personally don’t think Gentoo is useless.
• Paludis is going to support Exherbo and Exheres-based EAPIs too.
• It’s likely that most of my package format proposals will be sent to Exherbo rather than Gentoo because I’d rather see things implemented in three weeks than in three years. Gentoo is of course free to carry on using any ideas it realistically thinks can be implemented.
• Exherbo isn’t a Paludis-specific distribution. If other package managers want to implement Exheres and keep up with the rapid development until exheres-1 is stabilised, they’re more than welcome to.
• Exherbo is Bryan’s baby, not mine. I just happen to think it’s a nice baby and am putting considerable effort into ensuring that it grows up to become the kind of adult I find interesting.
• Paludis is fine with supporting other distributions, if we sensibly can.

Note that Sabayon is not one we can sensibly support:

lxnay> i'm the sabayon linux chief arch
lxnay> Just wanna know the implications of integrating paludis
ciaranm> you use binaries, right?
ciaranm> paludis doesn't do binaries currently, and when it does it will use a different format
ciaranm> that's probably the big issue...
ciaranm> other than that there's nothing major. with 0.26 we'll even be able to do special
distribution-specific stuff for you... you'd just need to give us a .conf file for your
distro and compile with --with-default-distribution=sabayon
lxnay> well if you devs are interested in sabayon, just contact me
ciaranm> lxnay: we don't care about sabayon, in that none of us use it. but we have no objection
to supporting it, if there's demand from users
lxnay> bah
lxnay> die alone then
-!- lxnay has left #paludis

which is a shame…

Automake and GPL-3

It turns out that recent Automake versions, when called with automake --copy, will install a GPL-3 COPYING file rather than the GPL-2 file to which developers have become accustomed.

I’ve never been particularly happy with Automake’s nasty trickery that makes you have to go out of your way to avoid shipping the GPL-2 with your code. But sneakily upgrading people to GPL-3 is rather devious… So if you’re currently relying upon automake --copy, you may want to give serious consideration to instead just sticking the generated files in your SCM before the GNU people introduce a new clause saying “by shipping this file as part of my project, I agree to give all my worldly possessions to the Church of Richard Stallman”.

Yay for git

Linux 2.6.26-rc2 wouldn’t boot on my desktop. Linux 2.6.25 worked. In the good old days, tracking down why would be a major pain in the ass. But now, a quick git bisect and fifteen reboots later, I have the exact commit: 3def3d6ddf43dbe20c00c3cbc38dfacc8586998f, also known as:

Author: Yinghai Lu
Date:   Fri Feb 22 17:07:16 2008 -0800

    x86: clean up e820_reserve_resources on 64-bit

    e820_resource_resources could use insert_resource instead of request_resource
    also move code_resource, data_resource, bss_resource, and crashk_res
    out of e820_reserve_resources.

    Signed-off-by: Yinghai Lu
    Signed-off-by: Ingo Molnar

Verifying that this really is the offender is equally easy — a quick ‘git revert’ on head and another reboot and the kernel’s working again. Now, I know nothing about what an e820 is beyond what Google tells me, but hopefully someone else will.

As much as I hate to say it, if this were Subversion I’d still be tracking down the bug. And if it were CVS, I wouldn’t've bothered.

Solving the server / headers / libs USE flag problem

There’s been some discussion on the paludis-user mailing list about embedded package management. This got me thinking about the server / headers / libs problem, which is roughly as follows:

In some situations, we’d like to be able to split a package up into different ‘parts’. A part is something like ‘headers’, ‘libraries’, ’server’, ‘client’, ‘binaries’ and ‘docs’. Some distributions do this by having separate packages. This is nasty:

• It means either building gcc five times or introducing new hacks to make multiple packages from a single build.
• It hides information from the package manager.
• It means the user has to have lots of packages installed to represent one real ‘package’. This in turn leads to complications like “if I uninstall foo-libs, should foo-headers go automatically too?”.
• It’s a hack introduced to get around package manager limitations.

Use flags for parts, as use flags are currently, aren’t the solution either, since packages need to be able to depend upon “foo with at least libs and headers enabled”. Theoretically USE dependencies (which are in kdebuild-1 and hopefully future 0-derived EAPIs) solve this. But it’s a mess — every package DEPENDing upon foo would have to do DEPEND="blah/foo[libs][headers]" RDEPEND="blah/foo[libs]". This doesn’t scale well.

I used to think that solving this required package manager knowledge of something we could call ‘parts’, which aren’t use flags. But it occurs to me that parts really are just use flags, with a few extra requirements:

• Enabling some parts might require enabling others, and enabling no parts at all might not make sense. So we need some way of restricting valid combinations of USE flags.
• Dependencies upon packages with parts need to be simpler. Rather than saying “I need foo with this part and foo with that part at DEPEND time, and this part at RDEPEND time”, we’d like to be able to say “I need foo” and only specify parts in special cases.
• The package has to be able to do the splitting and partial builds as appropriate or possible. This one needs per-ebuild support, since packages vary wildly in how they support partial builds.

The first bullet point is something we need to solve for future EAPIs anyway. The second is more interesting, and I think there might be a fairly simple solution…

One thing we’ve been playing with for consideration for future EAPIs or exheres is tweaking IUSE (or MYOPTIONS for exheres) syntax somewhat:

IUSE="foo bar linguas: en fr userland: gnu"

instead of:

IUSE="foo bar linguas_en linguas_fr userland_gnu"

This gets especially important when one learns that there is talk of removing the “expanded values don’t need to go in IUSE” special case that current EAPIs have.

When thinking about implementing this for Paludis, I started considering whether anything else useful could go in IUSE. And it seems to me that solving the parts problem could be as simple as this:

IUSE="foo bar libs(+DEPEND,+RDEPEND) headers(+DEPEND)"

What this means is “unless explicitly stated otherwise, when I resolve a DEPEND, I need to be built with libs and headers enabled, and when I resolve a RDEPEND I need to be built with headers enabled”. Then we’d need a new kind of USE dependency meaning “I don’t care about this flag” for special cases.

This also solves another problem:

IUSE="minimal(-*)"

Which means “if I’m built with minimal enabled, I don’t satisfy any dependencies unless they explicitly say that minimal is ok”.

Syntax could change. And I might drop the entire idea if it turns out it doesn’t do its job. But it’s interesting enough to write up so that I don’t forget about it entirely, at least…

C++0x Concepts

Some interesting material on C++0x concepts:

• Concepts Extending C++ Templates For Generic Programming, Douglas Gregor. Youtube.
• A Possible Future of Software Development, Sean Parent. Youtube.
• Proposed Wording for Concepts, Douglas Gregor, Bjarne Stroustrup, Jeremy Siek, James Widman. The current C++0x standard proposal for concepts. PDF.
• Elements of Programming, Alexander Stepanov, Paul McJones. An in-progress book. PDF.