He's not dead, he's resting

New Paludis Query Interface (Part III)

In the first part, we looked at the new Paludis query interface. In the second part, we looked at available components and how to fit them together. Now we look at how the selection is carried out.

The selection process is split up into four stages:

  • Find candidate repositories.
  • From those candidate repositories, find candidate categories.
  • From those candidate repositories and categories, find candidate packages.
  • From those candidate repositories and packages, work out the resulting PackageIDs.

The first three steps are basically the same for all selections. The Generator is queried for candidate repositories, and from the result set, the Filter returns a subset. That subset is then passed to the Generator to find a candidate category set, which goes to the Filter to obtain a subset. That then goes back to the Generator to get the candidate package set, which is again filtered.

At every stage, empty set checks are carried out. For most selections, an empty candidate set at any stage returns an empty result set straight away; for selection::RequireExactlyOne, it instead raises an exception.

The final stage is down to the selection. The overall process resembles the “old subset to generator to filter” flow used earlier. Some selections then re-order and reduce the final result set.

But doing a full filter on a large result set for, say, selection::BestVersionOnly is lots of (potentially very slow, since filters might need metadata) unnecessary work. So instead, the filter might be called repeatedly with a selection-crafted subset of the generator’s output until a single result is found.

Even that can be too much work. If multiple candidate packages are found for selection::SomeArbitraryVersion, asking the generator to provide IDs for every candidate might be too much. So again, a subset of the input is fed into the generator until a result is obtained.

Finally, there’s the question of how multiple generators and multiple filters are handled. When combining generators using operator &, a new generator is returned. For each stage, that generator calls its two child generators and makes a set intersection for its result. For filters combined using operator|, a new filter that feeds the first filter’s output into the second filter’s input and uses the second filter’s output as the result is created.


4 responses to “New Paludis Query Interface (Part III)

  1. Steven Oliver June 3, 2008 at 6:44 pm

    Is there a reason why you chose to use the & operator for generators and the | operator for filters?

    I tend to read them as the AND and OR operators, and when read like that, the filters don’t appear to do what they’re actually doing.

  2. Steven Oliver June 3, 2008 at 6:45 pm

    Given I do know that the AND operator is && but the mental association is still there. Ditto for the OR operator.

  3. Ciaran McCreesh June 3, 2008 at 7:08 pm

    C++ doesn’t have Intersection and Reduce operators. They’re the closest match that makes sense with operator precedence.

  4. Pingback: New Paludis Query Interface (Part II) « Ciaran McCreesh’s Blag

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