Re: bash core dumps doing glob pattern on long string

[Phi Debian]

On Tue, Oct 11, 2022 at 9:02 AM Martin D Kealey <martin@kurahaupo.gen.nz>
wrote:

> Broadly I meant translating into a "preferably" Deterministic
> (stackless/non-backtracking) Finite State Automaton.
>
> However I note that it's not always possible to make a Deterministic FSA
> when you have repeatable groups which themselves don't have fixed lengths
> (like a+(a|abbba|aabb*aba)b); either the extglob compiler would need to
> start over and compile to a Non Deterministic (stacking) FSA, or just give
> up and go back to the recursive approach.
>
> Personally I would favour the addition of «shopt -s dfa_extglob» that
> would block the fall-back, causing extglobs that would need a stack to be
> treated as magic match-never tokens.
>
> I say "extglob", but this would also speed up silly ordinary globs like
> [a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]
>
> -Martin
>
>
Ok I see, that's true that when you see a glob pattern like +(a) one would
think an optimiser could make it backtrack less.

«shopt -s dfa_extglob» could be an option, Chet may say it is hard to
explain when to use it... but we can go this path too, that is less of a
hack regarding stack provision, but more of a hack regarding the extglob
compiler :) Any implementation will please me :)