bug#62483: echo a | grep -E -w '((()|a)|())*' # does not terminate

[Paul Eggert]

On 2023-04-03 05:07, Koen Claessen wrote:

> BTW, if you are interested, I could do a larger more targeted effort stress
> testing grep like this and possibly find more test cases with unexpected
> behavior. I would need some guidance on where to put most effort in order
> to be as useful as this can be. I could find a MSc student to help out with
> that. Let me know if this sounds like an interesting thing to do!

Any help like this would be most welcome.

Unfortunately (or perhaps fortunately for your student, who will learn a 
lot!), none of the current maintainers of the glibc regex code really 
understand it. The code's original author is no longer available to 
answer questions, and the code is tricky as it attempts to implement 
POSIX regular expressions (which are worst-case exponential) efficiently 
in the usual cases.

The main guidance I can give you is to look at the existing bug reports 
against glibc regex[1] and against grep[2], as well as at the grep 
source code itself[3].

[1]: 
https://sourceware.org/bugzilla/buglist.cgi?component=regex&product=glibc
[2]: https://debbugs.gnu.org/cgi/pkgreport.cgi?package=grep
[3]: https://savannah.gnu.org/projects/grep