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 #2636.

> This has been addressed in issue #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 #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 #11307
import re
r = re.compile(r'(\w+)*=.*')
r.match("abcdefghijklmnopqrstuvwxyz")