[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: bash core dumps doing glob pattern on long string

From: Koichi Murase
Subject: Re: bash core dumps doing glob pattern on long string
Date: Sun, 9 Oct 2022 19:30:22 +0900

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 [...]..

reply via email to

[Prev in Thread] Current Thread [Next in Thread]