Regex causes python to hang up? / loop infinite?

[computercrustie]

BPO	3128
Nosy	@amauryfa
Files	re_problem.py: Example regex

^{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 2008-06-17.11:45:20.088>
created_at = <Date 2008-06-17.07:16:18.751>
labels = ['expert-regex', 'type-bug', 'invalid']
title = 'Regex causes python to hang up? / loop infinite?'
updated_at = <Date 2008-06-17.12:11:09.431>
user = 'https://bugs.python.org/computercrustie'

bugs.python.org fields:

activity = <Date 2008-06-17.12:11:09.431>
actor = 'computercrustie'
assignee = 'none'
closed = True
closed_date = <Date 2008-06-17.11:45:20.088>
closer = 'amaury.forgeotdarc'
components = ['Regular Expressions']
creation = <Date 2008-06-17.07:16:18.751>
creator = 'computercrustie'
dependencies = []
files = ['10642']
hgrepos = []
issue_num = 3128
keywords = []
message_count = 7.0
messages = ['68304', '68306', '68308', '68311', '68314', '68315', '68316']
nosy_count = 2.0
nosy_names = ['amaury.forgeotdarc', 'computercrustie']
pr_nums = []
priority = 'normal'
resolution = 'not a bug'
stage = None
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue3128'
versions = ['Python 2.5']

[computercrustie]

After struggling around with my code for nearly 1 hour now, I found out
that one of my regular expressions with a special string causes python
to hang up - not really hang up, because the processor usage is at
nearly 100%, so I think the regex machine is looping infinite.

Here is the regex-string:

re_exc_line = re.compile (
        # ignore everything before the first match
        r'^.*' +
        # first group (includes second | third)
        r'(?:' +
         # second group "(line) (file)"
         r'(?:' +
          # (text to ignore, line [number])
          r'\([^,]+\s*,\s*line\s+(?P<line1>\d+)\)' +
          # any text ([filename]) any text
          r'.*\((?:(?P<file1>[^)]+))*\).*' +
         # end of second group
         r')' +
        # or
        r'|' +
         # third group "(file) (line)"
         r'(?:' +
          # ([filename])
          r'\((?:(?P<file2>[^)]+))*\)' +
          # any text (text to ignore, line [number]) any text
          r'.*\([^,]+\s*,\s*line\s+(?P<line2>\d+)\).*' +
          # end of third group
         r')' +
        # end of first group
        r')' +
        # any text after it
        r'.*$'
        , re.I
    )

It should match either the construct:

1. """some optional text (text to ignore, line [12]) ([any_filename])
   followed by optional text"""

or:

2. """some optional text ([any_filename]) (text to ignore, line [12])
   followed by optional text"""

If first text matches, it is put into 'line1' and 'file1' and if the
second one matches into 'line2' and 'file2' of the groupdict.

For the upper both examples everything is ok, but having the following
string (I had to change some pathnames, because they contained customer
names):
msg = (
r"Error: Error during parsing: invalid syntax " +
r"(D:\Projects\retest\ver_700\lib\_test\test_sapekl.py, line 14) " +
r"-- Error during parsing: invalid syntax " +
r"(D:\projects\retest\ver_700\modules\sapekl\init.py, line 21) " +
r"-- Attempted relative import in non-package, or beyond toplevel " +
r"package")

used with the upper regex:

re_exc_line.match(msg)

is running for two hours now (on a 3Ghz Machine)!

I've attached everything as an example file and hope, I could help you.

[amauryfa]

To optimize your query, you could remove '^.*' and '.*$', and replace
match() with search().
Now it returns instantly...

[computercrustie]

Thank you for this answer.
It solves my problem, but I think that the issues ist still existing -
or not? (The regex is running on - 3 hours now)

[amauryfa]

Are you sure your regexp will return what you want?

The best match for the first part of the alternative is
("14",
"D:\projects\retest\ver_700\modules\sapekl\init.py, line 21"
)
The best match for the second part is
("D:\Projects\retest\ver_700\lib\_test\test_sapekl.py, line 14",
"21"
)

IOW, don't forget that the * operator will first try the longest
possible match.

Also, there seem to be an extra * here:
# any text ([filename]) any text
r'.*\((?:(?P<file1>[^)]+))*\).*' +
^
This alone can make the number of combinations explodes.

[computercrustie]

Further I was, because the upper listed string wasn't expected for this
code (until it occured the first time ;-) )

Normally there has been only one occurence of "(file) (.., line)" or
"(.., line) (file)" per string, so the regex did quite do what I
expected - never the less you are right - instead of the '*' operator I
should have used a '?' operator for the repetition.

So far many thanks for your recommendations - but the question is if it
is ok that a regex may block a process such a long time?

[amauryfa]

Yes, this can happen.

See http://www.regular-expressions.info/catastrophic.html

I am sure your regexp belongs to the same category.

[computercrustie]

Thanks for the link, it was very interesting to read what can happen in
some circumstances.

I think, the first two chapters can match to the problem.

So the type of this issue should be feature request ;-)

Never the less I learned something new, so the invested time wasn't wasted.

Greez