[Top][All Lists]

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

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

From: Paul Eggert
Subject: bug#62483: echo a | grep -E -w '((()|a)|())*' # does not terminate
Date: Mon, 3 Apr 2023 08:57:19 -0700
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.9.0

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

reply via email to

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