[ python-Bugs-1633583 ] Hangs with 100% CPU load for certain regexes

[SourceForge.net]

Bugs item #1633583, was opened at 2007-01-11 22:40
Message generated for change (Comment added) made by niemeyer
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1633583&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Regular Expressions
Group: Python 2.4
>Status: Closed
>Resolution: Wont Fix
Priority: 5
Private: No
Submitted By: Matthias Klose (doko)
Assigned to: Gustavo Niemeyer (niemeyer)
Summary: Hangs with 100% CPU load for certain regexes

Initial Comment:
[forwarded from http://bugs.debian.org/401676]

seen with 2.4.4 and 2.5 20061209; bug submitter writes:

Hi,

https://develop.participatoryculture.org/democracy/attachment/ticket/3947/crash.py
is a small test program which causes a complete hangup for at least
minutes (I aborted after a while) on my system, with 100% CPU load. The
regex code seems to run into some endless loop or something...


----------------------------------------------------------------------

>Comment By: Gustavo Niemeyer (niemeyer)
Date: 2007-01-12 01:42

Message:
Logged In: YES 
user_id=7887
Originator: NO

Hello Matthias,

It's well known that certain regular expressions can match in exponential
time.

Try that for instance: re.match("(((a+?)+?)+?b)", "a"*100+"c")

There are ways to optimize simple cases like this (which aren't present in
Python right now), but there isn't a way to truly "solve" the exponential
time backtracking for all cases while still offering the current feature
set.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1633583&group_id=5470