Re: bash core dumps doing glob pattern on long string

[Koichi Murase]

2022年10月9日(日) 18:37 Oğuz <oguzismailuysal@gmail.com>:
> I'm not familiar with how extended globs are implemented in either shell
> but this doesn't look like something that'd involve recursion.

For the particular pattern +(0), you might think it is possible to
implement it without recursion, but the extglob engine needs to handle
general patterns. Pattern matching that involves the `+' operator is
non-deterministic and accepted by the non-deterministic finite
automaton (NFA). An efficient implementation for the general patterns
would be to emulate the DFA converted from the NFA, which requires
some mathematical knowledge. An alternative naive implementation would
be to directly handle the NFA by backtracking, where recursion can be
used to accumulate the backtracking points. I haven't checked the
actual implementations of bash and ksh, but I guess these are
implemented in the latter approach.

So I think option 4 would be to re-implement the engine by the DFA,
though I'm not sure if it is straightforward to take account of the
collating symbols [.x.] and equivalence classes [=x=] in the POSIX
bracket expressions [...]..