infinite loop with specific regexp

[gnuthor]

BPO	9414
Nosy	@birkenfeld
Superseder	bpo-1662581: the re module can perform poorly: O(2n) versus O(n2)

^{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 2010-07-29.13:28:00.783>
created_at = <Date 2010-07-29.11:09:16.815>
labels = ['expert-regex', 'type-bug']
title = 'infinite loop with specific regexp'
updated_at = <Date 2010-07-29.13:28:00.781>
user = 'https://bugs.python.org/gnuthor'

bugs.python.org fields:

activity = <Date 2010-07-29.13:28:00.781>
actor = 'georg.brandl'
assignee = 'none'
closed = True
closed_date = <Date 2010-07-29.13:28:00.783>
closer = 'georg.brandl'
components = ['Regular Expressions']
creation = <Date 2010-07-29.11:09:16.815>
creator = 'gnuthor'
dependencies = []
files = []
hgrepos = []
issue_num = 9414
keywords = []
message_count = 2.0
messages = ['111909', '111920']
nosy_count = 2.0
nosy_names = ['georg.brandl', 'gnuthor']
pr_nums = []
priority = 'normal'
resolution = 'duplicate'
stage = None
status = 'closed'
superseder = '1662581'
type = 'behavior'
url = 'https://bugs.python.org/issue9414'
versions = ['Python 2.7']

[gnuthor]

The follow code hangs on vanilla compile python 2.7 on Ubuntu 10.04 x86_64 and all other versions of Python that I could find (i386/x86_64, 2.6.5/2.5.2/2.2):

>>> import re
>>> regex = re.compile(r'^((?:\.\d+)+|(?:\.?\w+(?:\-*\w+)+)+)\.(\d*?)$')
>>> match = regex.match('lldpLocChassisIdSubtype')
<infinite loop or possibly exponential time>

the regex is taken from file client.py of libsnmp-python ( version 5.4.2.1 ~dfsg0ubuntu1-0ubuntu2.1 in Ubuntu 10.04 )

libsnmp-python ( 5.4.1~dfsg-12 in Debian Lenny) contains
a previous version of this regex which does not produce an infinite loop

>>> regex = re.compile(r'^((?:\.\d+)+|(?:\.?\w+(?:\-*\w+)+)+)\.?(.*)$')
>>> match = regex.match('lldpLocChassisIdSubtype')
>>> print match
<_sre.SRE_Match object at 0x7f5d2abebc68>

Perl 5.10.1 can run both of the regular expressions without problems

$ perl -e '$x="lldpLocChassisIdSubtype"; print "$1" if $x =~ m/^((?:\.\d+)+|(?:\.?\w+(?:\-*\w+)+)+)\.(\d*?)$/;'
$ perl -e '$x="lldpLocChassisIdSubtype"; print "$1" if $x =~ m/^((?:\.\d+)+|(?:\.?\w+(?:\-*\w+)+)+)\.?(.*)$/;'
lldpLocChassisIdSubtype

I realise that these two regular expression might not particularly sensible and are certainly not equivalent semantically, but they are syntactically correct, as far as I can tell, and do not contain back references etc. and thus the matching process should be able to always
terminate.

[birkenfeld]

This is very probably a duplicate of bpo-1662581. When testing both your regexes with the new engine from bpo-2636, the match is not found/found instantaneously.