Subject: bug#9086: ls --color: 30% speed-up and case-insensitive suffixes [Re: bug#9086

From: Jim Meyering <[email-masked]>
Date: Sat, 13 Oct 2012 16:41:15 +0200

Pádraig Brady wrote:

> On 10/09/2012 02:32 PM, Jim Meyering wrote:
>> Pádraig Brady wrote:
>>> On 10/09/2012 01:32 PM, Jim Meyering wrote:
>>>> Pádraig Brady wrote:
>> ...
>>>>> So do we now only support suffixes delimited by '.' ?
>>>>> Previously the delimiter was arbitrary or optional:
>>>>>
>>>>>     touch star; LS_COLORS="*tar=01;31" /bin/ls --color *tar
>>>>
>>>> Good catch.  I realized that early on, but then forgot to mention it.
>>>> Yes, I would have to document that the "." is now required.
>>>> It seems like a reasonable restriction, but technically
>>>> it could be called a regression.
>>>>
>>>> Also, with these changes, a multiple-"." suffix will no longer work.
>>>> I.e., before, if you wanted to give *.tar.xz files a color different
>>>> from plain *.xz files, you could.
>>>>
>>>> Does anyone object to that?
>>>
>>> It's marginal, though I'd be inclined to keep the existing
>>> support for arbitrary suffixes. We could fall back to the
>>> slower linear scan iff an entension entry in LS_COLORS didn't
>>> contain a single '.'  To be more generally performant and
>>> support a longest suffix match we'd have to use something
>>> like a trie I think.
>>
>> Well, I confess that I am not inclined to spend more time on this,
>> and don't think the dot-less or longest-suffix use cases are worth the
>> added code (we were already using most of hash.c already, so my change
>> induced almost no bloat), so I'm tempted to go ahead with the patch and
>> wait for complaints before adding trie-based lookup.
>
> Sure. I wasn't really suggesting we do trie now,
> just mentioning that would be a possible route in future.
>
> As for enabling the faster and slightly more limited code for now...
> It's a hard decision. I suppose it's OK for now but it'll need a
> change in behavior note in NEWS.

Thinking more about it, there are at least a few common file name
suffixes that can be usefully colored, but that are not delimited by ".",
like ",v" and "~", so I will discard that patch, for now at least.

Can anyone point to a good trie implementation in C (preferably GPL'd)?
(other than the ones referred to in https://en.wikipedia.org/wiki/Trie)
I was surprised to see that there is none in gnulib.
If not, does anyone want to write one for gnulib?