in short, the re module can degenerate to really really horrid performance. See this for how and why:

http://swtch.com/~rsc/regexp/regexp1.html

exponential decline instead of squared.

I don't have a patch so i'm filing this bug as a starting point for future work. The Modules/_sre.c files implementation could be updated to use the parallel stepping Thompson approach instead of recursive backtracking.

filing this as a bug until me or someone else comes up with a patch.

I would file this under "feature request"; the current situation isn't so much buggy, as slow. While you can produce a segfault with the current regular expression engine (due to stack overflow), you can do the same thing with regular Python on Linux (with sys.setrecursionlimit), ctypes, etc., and none of those are considered as buggy.

My only concern with such a change is that it may or may not change the semantics of the repeat operators '*' and '+', which are currently defined as "greedy". If I skimmed the article correctly late at night, switching to a Thompson family regular expression engine may result in those operators no longer being greedy. Please correct me if I am wrong.

yeah this is better as a feature request. certianly low priority either way.

-nothing- I propose doing would change the syntax or behaviour of existing regular expressions at all. Doing so would be a disaster. thompson nfa does not imply changing the behaviour.

anyways its a lot more than a simple "patch" to change the re module to not use backtracking so i expect this to languish unless someone has a of free time and motivation all at once. :)

Just a note for those who think this is a purely theoretical issue:

We've been using the python-markdown module on our web app for a while,
only to notice the app has been repeatedly going down. After tracking
down the culprit, we found that a speech from Hamlet passed to one of
the Markdown regular expressions caused this exponential behavior,
freezing up the app.

here are two other bug reports about the same issue:

http://bugs.python.org/issue1448325

http://bugs.python.org/issue1566086

Not sure if this is a real-world case of this in particular, but possibly:
http://groups.google.com/group/web2py/browse_thread/thread/59ff2e31698bced6/9bbae2d482d11b88

This has been addressed in issue bpo-2636.

This has been addressed in issue bpo-2636.

Are you sure about this? Does the proposed new regex engine use Thompson
NFAs, or some variant thereof?

The new code includes some extra checks which, although not foolproof,
certainly reduce the amount of backtracking in a lot of cases.

Here's an easy way to trigger the poor performance. Tested with 2.5,
2.6, and 2.7:

re.compile( '(\s+.*)*x' ).search( 'a ' * 30 )

I'm still tinkering with my regex engine (issue bpo-2636).

Some timings:

re.compile(r'(\s+.*)*x').search('a ' * 25)
20.23secs

regex.compile(r'(\s+.*)*x').search('a ' * 25)
0.10secs

Another example from bpo-11307
import re
r = re.compile(r'(\w+)*=.*')
r.match("abcdefghijklmnopqrstuvwxyz")

Given the number of times this comes up, I think it's a least worth an upgrade from 'low' priority to 'normal' priority.

Note this can be used for denials of service: see http://bugs.python.org/issue17980

The recommendation for anyone using regular expressions on hostile input is to (a) don't do that. (b) use a better regexp without this possible behavior and (c) use something like re2 (there's a Python binding at https://github.com/axiak/pyre2) which is a regular expression engine that this cannot happen to.

fixing this within python requires a complete rewrite and replacement of the re module with one that uses a different approach. see the other work on the MRAB regex module and discussion surrounding that. that is a non trivial task and it is fixing other more important things (unicode correctness!) than this...

Given that, I don't actually expect this issue to ever be fixed.

IMNSHO: People shouldn't abuse regexes and get themselves into this situation in the first place. ;)

discussion should really happen on python-ideas.

Note that https://pypi.python.org/pypi/re2 exists today as well and offers a re module compatible interface. I haven't tried it.

https://pypi.org/project/pyre2/ seems to be a maintained version of that for use on modern Python interpreters.