classification
Title: infinite loop with specific regexp
Type: behavior Stage:
Components: Regular Expressions Versions: Python 2.7
process
Status: closed Resolution: duplicate
Dependencies: Superseder: the re module can perform poorly: O(2**n) versus O(n**2)
View: 1662581
Assigned To: Nosy List: georg.brandl, gnuthor
Priority: normal Keywords:

Created on 2010-07-29 11:09 by gnuthor, last changed 2010-07-29 13:28 by georg.brandl. This issue is now closed.

Messages (2)
msg111909 - (view) Author: (gnuthor) Date: 2010-07-29 11:09
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.
msg111920 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2010-07-29 13:28
This is very probably a duplicate of #1662581.  When testing both your regexes with the new engine from #2636, the match is not found/found instantaneously.
History
Date User Action Args
2010-07-29 13:28:00georg.brandlsetstatus: open -> closed

nosy: + georg.brandl
messages: + msg111920

superseder: the re module can perform poorly: O(2**n) versus O(n**2)
resolution: duplicate
2010-07-29 11:09:16gnuthorcreate