From: Paolo Bonzini <paolo.bonzini@gmail.com>
Date: Wed, 17 Jun 2009 16:04:57 GMT
Subject: Re: [PATCH] avoid exponential regex match for java and objc function names
Message-ID: <4A391429.4010706@gmail.com>
In-Reply-To: <9b18b3110906170900g778b3c8aie627fb45a4967eb2@mail.gmail.com>


> 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