Let’s say you’ve got a list of globs: '*', 'a*', '*a', '*a*'. Now sort them. Sort them based on how specific they are. More specific globs match fewer things. Less specific globs match more things.

If Dr. Seuss had had anything to say about globs, what would he have said?

Glob on String
Blob on Thing
Glob on String for Blog on Thing
Blog on Glob for Thing on String

When Globs on Strings match Blogs on Things
Then... Blogs on Globs match Strings on Things

And When Blogs match Globs and Strings match Things
Then... Blogs on Globs match Blogs on Things on Globs on Strings!

So how do you sort globs? And why would you want to sort them? I’m working on a project where you use globs to pick out the error conditions that you are interested in. These error conditions have names. So you can match entire classes of error by using globs. For example 'foo.*' matches the errors 'foo.bar' and 'foo.baz'.

But what if I also add '*.*' to the mix. This also matches 'foo.bar' and 'foo.baz'. But I want 'foo.*' to match first. It’s more specific. For some definition of specific.

Again, 'a*' is more specific than '*a*'. 'a*' can match fewer things. Let’s look at this more closely. Say we have the set of words: [aa,ab,ba,bb]. Then

* matches aa,ab,ba,bb
a* matches aa, ab
*a matches aa, ba
*a* matches aa, ab, ba

So we can order the globs like so: 'a*', '*a', '*a*', '*', in order of increasing matches. The ones at the front are more specific. They match fewer things.

What about 'a*' and '*a'. How do we decide which comes first. Rather arbitrarily, lets say that the more specific prefix of 'a*' makes it the winner. Prefixes are more specific than suffixes. Hmm. That’s getting way too philosophical. Take Java packages: 'com.ricebridge.csvman.*' is more specific than '*.csvman.test'. The latter can occur in any top level package, but the former in only one. Yeah it’s pretty weak, but hey!

Now here’s the thing: what is the rule for sorting globs? I want a rule which:

1. is human computable 'just by looking' — that is, the rule is obvious
2. creates a full ordering of any set of globs — no arbitrary ordering of non-identical globs
3. has reasonable efficiency

The first idea: Use the number of stars. More stars means more specific. When the number of stars is the same, sort alphabetically. Neat and easy. And wrong. Sure it puts 'a*b*c' before 'a*c', but it also puts '*a*' before 'a*', which is incorrect.

Let’s look at globs. There are stars, and then there are normal characters. They always form an alternating pattern: 'a*b*c'. Or '*a*b*'. So this looks like an essential (and not accidental) feature of globs. The number of stars and the number of 'normals'. Yes, in general, the more stars you have, the more constrained you are, but there’s more going on.

After thinking about this for a bit, I realised that the outside stars are special. Very special. A glob with a star at the start or end, or both, can match a lot of things. Way more things that a glob with stars inside other characters. What if we just define an ordering for the outside stars. And we have one already. Form the preceding discussion: 'a', 'a*', '*a', '*a*', '*'.

Now that 'a' can stand for anything inside the outside stars. Other globs in fact. But those globs can’t have outside stars! The glob '**' is the same as the glob '*'. Adjacent stars merge into one. So '*a*', with a = '*b*' becomes '**b**' becomes '*b*'. On the other hand with a = 'b*c', '*a*' becomes '*b*c*'. A different beast entirely.

Now at this point you might be saying, "hold on a sec, you’re trying to order regular expressions! That's insane! You need to evaluate them to do that!" Because globs are just regular expressions: 'a*' is really /a.*/ in regex land. True. But I think that for the special case of globs built from stars only (let’s drop the use of '?'), we can in fact define an ordering without requiring evaluation. The problem is sufficiently complex to require some thought, but it's not a 'hard' problem.

I would think that due to back-tracking, solving the sorting problem for standard regular expressions is probably going to involve solving the halting problem, since you have to evaluate each regex. But I could be wrong. I often am.

Back to the globs. We can sort based on the outside stars. Fine. We have five subsets to sort now: 'a', 'a*', '*a', '*a*', '*'. '*' is a special case — it’s always last. It's the least specific glob of all, matching anything. The glob with no stars, 'a', is also easy. Just sort alphabetically.

For the other three we note that a will always take the forms 'b', 'b*b', 'b*b*b', ..., and so on. That is, the essential thing is the number of inside stars. In this case, the more stars you have, the less you can match. For example 'a*a' will match 'azbza', 'azcza'. But 'a*b*a' will only match 'azbza'. More stars are more specific. Problem solved!

Nope. Not quite. What about globs having the same number of inside stars? What about 'a*a' versus 'a*ab'? Which is more specific? I think 'a*ab' is. It has more information, more constraints on what it can match. For any given finite set of words, there are more ways to end in 'a' alone than 'ab'. So the next criteria is: more normal characters, more specific.

You can see the next catch, can't you? What if we have the same number of normal characters? Alphabetic sort? No, doesn’t work – the characters may be spread out between in the stars in different ways: 'a*ab' versus 'ab*a'. Which is more specific? Hmm. Let’s invoke our prefix rule again. This makes 'ab*a' more specific than 'a*ab', because it has a longer prefix. The criteria is: whoever’s got the mostest on the leftest.

And finally, if the character spread is identical, then we go alphabetic. So 'aa*a' precedes 'ab*a'. Let's see what we have...

The human rules are:

1. Prefixes are more specific than suffixes
2. Outside stars first: 'a', 'a*', '*a','*a*'
3. Inside stars: more stars means more specific
4. Normal characters: more characters, more to the left, is more specific
5. Otherwise go alphabetic

Here’s a sample list of globs, starting with the most specific. See if this list matches your idea of how they should be ordered.

com.ricebridge.csvman.CsvManager
com.*.*Manager
com.ricebridge.*.CsvManager
com.ricebridge.csvman.*
*.ricebridge.csvman
*.ricebridge.*
*

This is almost right. But really I think com.ricebridge.*.CsvManager is more specific than com.*.*Manager. How can we arrange this? Do more stars really mean more specific? Or do normal characters provide far more specificity?

The more normal characters you use, the more specific you are being. Stars provide very little information. But strings of normal characters really narrow things down. But in which set of words? What is the total set of words that we are matching in the com.ricebridge scenario? Infinite? Is there some structure? If these are the names of Java classes (my target domain), then com.ricebridge.*.CsvManager is definitely more specific (matches fewer items) than com.*.*Manager. Seems like prefixes really do rule. I wonder is this somehow connected to Zipf's Law...

Anyway, let’s drop rules 3 and 4, and replace them with:

Inside characters: longest prefix wins

So even if you have loads of stars, if you have a short prefix, you lose. This gives:

com.ricebridge.csvman.CsvManager
com.ricebridge.*.CsvManager
com.*.*Manager
com.ricebridge.csvman.*
*.ricebridge.csvman
*.ricebridge.*
*

That’s a lot better. Let’s restate the human rules:

1. Outside stars first: 'a', 'a*', '*a', '*a*'
2. Inside characters: longest prefix wins
4. Prefixes same length? more stars wins
3. Otherwise go alphabetic

That new rule number 4 means that 'a*b*c' is more specific than 'a*b'. So you only compare the minimum number of prefixes. If they're are equal, take the longest glob as more specific.

A much better ruleset! And it pretty much conforms to the criteria for the sorting algorithm: human computable, full ordering, and reasonable performance.

Time to go code it up. Post a comment if you want to save me from myself!