Re: bash "extglob" needs to upgrade at least like zsh "kshglob"

[Martin D Kealey]

I'm top-quoting this because the entire response below seems to be
predicated on a misconception, or perhaps several misconceptions.

Exactly NONE of my suggestions involves expanding the Shell language.
Users would continue to write extglob exactly as they do now, and they
would remain blissfully ignorant of the regex engine underneath. The
"translation" is entirely hidden from them.

Extglob is amenable to compilation into a FSA, which leads to the
conclusion that it's functionally a form of regular expression, even if its
syntax is rather different from regexes that people are familiar with. This
is why I said that writing our own regular/linear extglob implementation
would be equivalent to writing a regex compiler and engine. It's also why I
think the shortest route to having a working implementation would be to
write a translation layer from extglob to one of the existing RE formats.

(The only option I suggested that would modify the shell language would be
the option to remove the !(LIST) negation; I include that for completeness,
I wouldn't actually recommend it.)

The idea that "these are only technical details that nobody cares about" is
just wrong.
There have been bugs filed because the performance is not just "a bit
slow", but "slow by many orders of magnitude".

If discussion of implementation details is out of scope for the bash-bug
mailing list, is there a bash-dev list, or similar, where they should be
discussed?

With the exception of the !(LIST) negation, there's a direct correspondence
between extglob and any other regex format. Translating between them is
trivial.
If we use the standard POSIX BRE or ERE, then there's no additional code to
ship; it's included as part of the OS. The hard part is what to do with
(!LIST), which was the point of my previous post.

-Martin

On Sun, 30 Oct 2022 at 23:35, Oğuz İsmail Uysal <oguzismailuysal@gmail.com>
wrote:

> On 10/30/22 3:25 PM, Martin D Kealey wrote:
> > How much faster do you think it can be made?
> I don't know, irrelevant though.
> > The problem is not that individual steps are slow, but rather [...]

These are technical details; no user cares about them.
>
> The purpose of my suggestions was to /minimize/ the complexity that
> becomes part of Bash's codebase [...]
> I meant complexity of the language, not the codebase.
>
> In my opinion "make the existing extglob code faster" is a wasted effort
> if it doesn't get us to "run in at-most quadratic time" and preferably "run
> in regular (linear) time", and so that basically amounts to "write our own
> regex state machine compiler and regex engine". This is a non-trivial task,
> and would fairly obviously add
> > *more* complex code into Bash's codebase than any of my suggested
> > alternatives.
> extglobs are already a part of the bash language. All of your suggested
> alternatives involve expanding the language in question.


No. Just No.

That's why I
> disagree with all of them.
>






> > (Even my options of "postprocess the codebase" or "modify an existing
> > regex compiler" would leave their execution components untouched; only
> > the compilation phase would be modified, and a modified regex compiler
> > would at least stand a chance of existing as a stand-alone library
> > project.)
> If you mean bash should start shipping a huge library like pcre for
> solving an edge case, I don't think that's reasonable at all; why take
> on such a burden when you already have something that works fine in
> practice?
>

Using PCRE was only one option, and not my preferred one.
POSIX RE is provided by the standard C library, we wouldn't have to ship
anything.

The problem is that it DOESN'T work fine. In practice people encounter
abysmally slow extglob matching.