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 _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
