Small case which hangs

[goatchurch]

BPO	1721518
Nosy	@birkenfeld
Superseder	bpo-2636: Adding a new regex module (compatible with re)

^{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-08-21.23:53:41.516>
created_at = <Date 2007-05-18.20:12:09.000>
labels = ['expert-regex']
title = 'Small case which hangs'
updated_at = <Date 2010-08-21.23:53:41.514>
user = 'https://bugs.python.org/goatchurch'

bugs.python.org fields:

activity = <Date 2010-08-21.23:53:41.514>
actor = 'georg.brandl'
assignee = 'niemeyer'
closed = True
closed_date = <Date 2010-08-21.23:53:41.516>
closer = 'georg.brandl'
components = ['Regular Expressions']
creation = <Date 2007-05-18.20:12:09.000>
creator = 'goatchurch'
dependencies = []
files = []
hgrepos = []
issue_num = 1721518
keywords = []
message_count = 6.0
messages = ['32073', '32074', '32075', '73983', '81421', '114612']
nosy_count = 6.0
nosy_names = ['georg.brandl', 'niemeyer', 'goatchurch', 'rsc', 'timehorse', 'mrabarnett']
pr_nums = []
priority = 'low'
resolution = 'duplicate'
stage = None
status = 'closed'
superseder = '2636'
type = None
url = 'https://bugs.python.org/issue1721518'
versions = ['Python 2.7']

[goatchurch]

import re
s = "Add.1, 2020 and Add.1, 2021-2023, 2025, 2028 and 2029 and Add.1) R"
r = "(?:\s|,|and|Add\S*?|Parts?|\([^\)]*\)|[IV\-\d]+)*$"
print "It's going to crash"
print re.search(r, s)
print "It hasn't crashed"

[birkenfeld]

I assume this is one of the pathological cases where the RE algorithm backtracks "to death". That's not really a bug, but a limitation.

[goatchurch]

I can shorten it further to:

s = "Add.1, 2020 Add.1, 20212023, 2025, 2028 and 2029 Add.1) R"
r = "(?:\s|,|and|Add\S*?|[\d]+)*$"

Sometimes it finishes after a long time when you shorten the s-string from the front. If you take the "R" from the end it goes through straight away. It's even very slow with match.

[timehorse]

Tested on 2.6rc2 and slow but successful. bpo-1662851 may be related.

[mrabarnett]

This problem has been addressed in issue bpo-2636.

Although the extra checks certainly aren't foolproof, neither of the
examples given are slow.

[birkenfeld]

If at all, this will be fixed by applying bpo-2636.