This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: Hangs with 100% CPU load for certain regexes
Type: Stage:
Components: Regular Expressions Versions: Python 2.4
process
Status: closed Resolution: wont fix
Dependencies: Superseder:
Assigned To: niemeyer Nosy List: doko, niemeyer
Priority: normal Keywords:

Created on 2007-01-11 22:40 by doko, last changed 2022-04-11 14:56 by admin. This issue is now closed.

Files
File name Uploaded Description Edit
crash.py doko, 2007-01-11 22:40 test case
Messages (2)
msg30969 - (view) Author: Matthias Klose (doko) * (Python committer) Date: 2007-01-11 22:40
[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...
msg30970 - (view) Author: Gustavo Niemeyer (niemeyer) * (Python committer) Date: 2007-01-12 01:42
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.
History
Date User Action Args
2022-04-11 14:56:22adminsetgithub: 44439
2007-01-11 22:40:24dokocreate