Issue 15077: Regexp match goes into infinite loop (original) (raw)

Issue15077

➜

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.

This issue has been migrated to GitHub: https://github.com/python/cpython/issues/59282

classification

process

Created on 2012-06-15 10:41 by moriyoshi, last changed 2022-04-11 14:57 by admin. This issue is now closed.

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) *	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'''(?:[^`';]+|'(?:''	[^'])*'	`(?:``
msg164280 - (view)	Author: Serhiy Storchaka (serhiy.storchaka) *	Date: 2012-06-28 17:13
I think it's a bug. The issue can be closed.
msg164281 - (view)	Author: Serhiy Storchaka (serhiy.storchaka) *	Date: 2012-06-28 17:15
I think it's *not* a bug. The issue can be closed.
msg164283 - (view)	Author: Matthew Barnett (mrabarnett) *	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.