Interpreter gets stuck while applying a regex pattern

[SateeshKumar]

BPO	35932
Nosy	@tim-one, @ezio-melotti, @remilapeyre
Files	gdb_trace

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2019-02-08.02:17:30.513>
created_at = <Date 2019-02-07.17:33:27.359>
labels = ['expert-regex', 'type-bug', 'invalid']
title = 'Interpreter gets stuck while applying a regex pattern'
updated_at = <Date 2019-02-08.02:17:30.509>
user = 'https://bugs.python.org/SateeshKumar'

bugs.python.org fields:

activity = <Date 2019-02-08.02:17:30.509>
actor = 'tim.peters'
assignee = 'none'
closed = True
closed_date = <Date 2019-02-08.02:17:30.513>
closer = 'tim.peters'
components = ['Regular Expressions']
creation = <Date 2019-02-07.17:33:27.359>
creator = 'Sateesh Kumar'
dependencies = []
files = ['48110']
hgrepos = []
issue_num = 35932
keywords = []
message_count = 4.0
messages = ['335029', '335035', '335046', '335053']
nosy_count = 6.0
nosy_names = ['tim.peters', 'ezio.melotti', 'mrabarnett', 'SilentGhost', 'remi.lapeyre', 'Sateesh Kumar']
pr_nums = []
priority = 'normal'
resolution = 'not a bug'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue35932'
versions = ['Python 2.7']

[SateeshKumar]

The python interpreter gets stuck while applying a compiled regex pattern against a given string.

The regex matching doesn't get stuck if uncompiled regex pattern is used, or if the flag "re.IGNORECASE" is not used for regex match.

Below code snippets gives more details.

• Variant-1
  # Python process gets stuck

~/workbench$ cat match.py
import re
pattern = "^[_a-z0-9-]+([\.'_a-z0-9-]+)@[a-z0-9]+([\.a-z0-9-]+)(\.[a-z]{2,4})$"
compiled_pattern = re.compile(pattern, re.IGNORECASE)
val = "Z230-B900_X-Suite_Migration_Shared_Volume"
re.match(compiled_pattern, val)

~/workbench$ python match.py
^^^ The interpreter gets stuck.

• Variant-2 (Using uncompiled pattern)
  # python interpreter doesn't get stuck

~/workbench$ cat match.py
import re
pattern = "^[_a-z0-9-]+([\.'_a-z0-9-]+)@[a-z0-9]+([\.a-z0-9-]+)(\.[a-z]{2,4})$"
compiled_pattern = re.compile(pattern, re.IGNORECASE)
val = "Z230-B900_X-Suite_Migration_Shared_Volume"
re.match(pattern, val)

• Variant-3 (Using compiled pattern, but without flag re.IGNORECASE)
  # Python interpreter doesn't get stuck

~/workbench$ cat match.py
import re
pattern = "^[_a-z0-9-]+([\.'_a-z0-9-]+)@[a-z0-9]+([\.a-z0-9-]+)(\.[a-z]{2,4})$"
compiled_pattern = re.compile(pattern)
val = "Z230-B900_X-Suite_Migration_Shared_Volume"
re.match(compiled_pattern, val)

# Platform details
~/workbench$ python -V
Python 2.7.12

~/workbench$ uname -a
Linux ubuntu16-template 4.4.0-59-generic #80-Ubuntu SMP Fri Jan 6 17:47:47 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux

Though above details are from Python/2.7 I see similar beahviour with Python/3.5.2 too.

[SilentGhost]

In your variant 2 you're not using re.IGNORECASE flag, if you do you're likely to encounter the same behaviour as for the compiled pattern. At least I do on python3.6

[SateeshKumar]

@SilentGhost, You are right, when I pass the flag "re.IGNORECASE" for example in Variant-2 the python process do gets stuck.

Here is the revised code for Variant-2:

• Variant-2
  %cat match.py
  import re
  pattern = "^[_a-z0-9-]+([\.'_a-z0-9-]+)@[a-z0-9]+([\.a-z0-9-]+)(\.[a-z]{2,4})$"
  val = "Z230-B900_X-Suite_Migration_Shared_Volume"
  re.match(pattern, val, re.IGNORECASE)

~/workbench$ python match.py
^^^ The interpreter gets stuck.

Thanks for the correction. I have also modified the title of this issue accordingly.

[tim-one]

Without re.IGNORECASE, the leading

^[_a-z0-9-]+

can't even match the first character (val starts with uppercase Z), so it fails instantly.

With re.IGNORECASE, it's not "stuck", but is taking a verrrrrry long time to try an enormous number of (ultimately doomed) possibilities due to the way the regexp is written.

This is due to using nested quantifiers for no apparent reason. For any character class C,

(C+)*

matches the same set of strings as

C*

but the former way can _try_ to match in an exponential (in the length of the string) number of ways. So replace

([\\.'\_a-z0-9-]+)*

and
([\.a-z0-9-]+)*

with

[\\.'\_a-z0-9-]*

and
[\.a-z0-9-]*

and it fails to match val quickly (even with re.IGNORECASE).

For more on this (which applies to many regexp implementations, not just Python's), here's a start:

https://www.mathworks.com/matlabcentral/answers/95953-why-can-nested-quantifiers-in-regexp-can-cause-inefficient-failures-in-matlab-6-5-r13

The "Mastering Regular Expressions" book referenced in that answer is an excellent book-length treatment of this (and related) topic(s).