Author serhiy.storchaka
Recipients Arfrever, arigo, eli.bendersky, ezio.melotti, larry, mrabarnett, pitrou, python-dev, serhiy.storchaka, tim.peters
Date 2013-08-10.08:26:44
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1376123205.2.0.699065843018.issue18647@psf.upfronthosting.co.za>
In-reply-to
Content
> Serhiy, yup, that regexp is slow, but it does finish - so the engine is doing something to avoid _unbounded_ repetitive matching of an empty string.

Yes, it finish, but it has exponential computation complexity. Increase the length of the string to 21, 22, 30, 100...

There were multiple bug reports about "hanged" regexps which actually had quadratic or exponential computation complexity (see for example issue1662581, issue16430, issue15077, issue15515). In all such cases the regexp can be rewritten to have linear computation complexity. However peoples constantly do such mistakes.

Armin, I totally agree with you.

Note that before b78c321ee9a5 the regexp '(?:.{0,60000}.{0,5535})?' was forbidden while '(?:.{0,60000}.{0,5534})?' and '(?:.{0,60000}.{0,5536})?' were allowed. Existing check allowed false positives.
History
Date User Action Args
2013-08-10 08:26:45serhiy.storchakasetrecipients: + serhiy.storchaka, tim.peters, arigo, pitrou, larry, ezio.melotti, mrabarnett, Arfrever, eli.bendersky, python-dev
2013-08-10 08:26:45serhiy.storchakasetmessageid: <1376123205.2.0.699065843018.issue18647@psf.upfronthosting.co.za>
2013-08-10 08:26:45serhiy.storchakalinkissue18647 messages
2013-08-10 08:26:44serhiy.storchakacreate