[issue23541] Re module's match() fails to halt on a particular input

Changes by Serhiy Storchaka : -- resolution: -> wont fix stage: -> resolved status: open -> closed ___ Python tracker ___ ___ Python

[issue23541] Re module's match() fails to halt on a particular input

Matthew Barnett added the comment: The problem is with the "(\w+\s*)+". \s* can match an empty string, so when matching a word it's like "(\w+)+". If you have n letters, there are 2**n ways it could match, and if what follows never matches, it'll try all of them. It _will_ finish, eventually.

[issue23541] Re module's match() fails to halt on a particular input

Serhiy Storchaka added the comment: Minimal example for your case is re.match(r'(\w+\s*)+\s+\d+', 'Compiling Regular Patterns to Sequential Machines') It doesn't halt, it just needs too long time to finish. Your should rewrite the regular expression to avoid catastrophic backtracking (http:/

[issue23541] Re module's match() fails to halt on a particular input

New submission from Ceridwen: Attached is a three-line script whose third line, a call to match() for a compiled regex, fails to halt on Python 2.7 and on 3.4 (after changing ur in front of the regex string to r to accommodate the change in Unicode handling). I found it by stepping through th