[issue30148] Pathological regex behaviour

Change by Serhiy Storchaka : -- nosy: +serhiy.storchaka resolution: -> wont fix stage: -> resolved status: open -> closed ___ Python tracker

[issue30148] Pathological regex behaviour

Tim Peters added the comment: Yes, that example takes time exponential in the number of blanks to (fail to) match - each time you add a blank to `input`, it essentially doubles the time required. It's _possible_ for an implementation to deduce that `(\s+)+` is an insanely inefficient way to

[issue30148] Pathological regex behaviour

Jussi Pakkanen added the comment: This is slow even when ignores is set to a non-empty value. It's not as slow but the real slowdown is in the whitespace regex. Here is a minimal sample: input = ' abc' re.search(r'(\s+)+d', input) --

[issue30148] Pathological regex behaviour

Matthew Barnett added the comment: If 'ignores' is '', you get this: (?:\b(?:extern|G_INLINE_FUNC|%s)\s*) which can match an empty string, and it's tried repeatedly. That's inadvisable. There's also: (?:\s+|\*)+ which can match whitespace in multiple ways. That's inadvisable too.

[issue30148] Pathological regex behaviour

New submission from Jussi Pakkanen: Attached is a script that runs a single regex against one line of text taking over 12 seconds. If you run the exact same regex in Perl it finishes immediately. The slowness has something to do with spaces. If you replace consecutive spaces in the input