Subject: Re: [PATCH] avoid exponential regex match for java and objc function names

From: Paolo Bonzini <[email-masked]>
Date: Wed, 17 Jun 2009 18:04:57 +0200

> Ah ok. Im not familiar with the finer points of the POSIX engine, but
> PCRE and Perl's engine, and most similar engines are not true regular
> expression engines and thus benefit *greatly* from atomic matching if
> it is available.
> 
> Like the difference between heat-death performance (or stack
> overflow), and running instantly.

You can almost always fix the regex to avoid this, by ensuring that 
whenever you have (...)+ (or *) a suffix of the subexpression cannot be 
a prefix of the subexpression too.  This is what my patch did -- 
changing a bad regex to a nicely behaving one.

Paolo