classification
Title: Regexp match goes into infinite loop
Type: crash Stage:
Components: Regular Expressions Versions: Python 2.7
process
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: Nosy List: ezio.melotti, moriyoshi, mrabarnett, serhiy.storchaka
Priority: normal Keywords:

Created on 2012-06-15 10:41 by moriyoshi, last changed 2012-08-05 10:31 by serhiy.storchaka. This issue is now closed.

Files
File name Uploaded Description Edit
x.py moriyoshi, 2012-06-15 10:41
Messages (5)
msg162883 - (view) Author: Moriyoshi Koizumi (moriyoshi) Date: 2012-06-15 10:41
A peculiar pair of a regexp and a target string causes the runtime into an infinite loop.  The same expression works with Perl.
msg162896 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-06-15 12:55
This is not infinite loop. This is O(2**len(prefix_before_first_quote)) computation. Measure times of matching for "INSER(`id`...", "INSERT(`id`...", "INSERT (`id`...", "INSERT I(`id`...", etc.

Better use r'''(?:[^`';]+|'(?:''|[^'])*'|`(?:``|[^`])*`)+;''' regexp.
msg164280 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-06-28 17:13
I think it's a bug. The issue can be closed.
msg164281 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-06-28 17:15
I think it's *not* a bug. The issue can be closed.
msg164283 - (view) Author: Matthew Barnett (mrabarnett) * (Python triager) Date: 2012-06-28 17:36
It's not a bug, it's a pathological regex (i.e. it causes catastrophic backtracking).

It also works correctly in the "regex" module.
History
Date User Action Args
2012-08-05 10:31:46serhiy.storchakasetstatus: open -> closed
resolution: not a bug
2012-06-28 17:36:45mrabarnettsetmessages: + msg164283
2012-06-28 17:15:10serhiy.storchakasetmessages: + msg164281
2012-06-28 17:13:51serhiy.storchakasetmessages: + msg164280
2012-06-15 12:55:05serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg162896
2012-06-15 10:41:09moriyoshicreate