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

Previous Next

Full log

Message #53 received at 62483 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Koen Claessen <koen <at> chalmers.se>
Cc: 62483 <at> debbugs.gnu.org, Jim Meyering <jim <at> meyering.net>
Subject: Re: bug#62483: echo a | grep -E -w '((()|a)|())*' # does not terminate
Date: Mon, 3 Apr 2023 08:57:19 -0700

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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.