Serhiy Storchaka added the comment:
> 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.
----------
_______________________________________
Python tracker <rep...@bugs.python.org>
<http://bugs.python.org/issue18647>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
