Lookback with group references incorrect (two issues?)

[acooke]

BPO	9179
Nosy	@mdickinson, @larryhastings, @benjaminp, @ezio-melotti, @serhiy-storchaka
Files	re_getwidth.patch re_forbid_some_groupref_in_lookbehind-2.7.patch re_forbid_groupref_in_lookbehind-2.7.patch re_forbid_groupref_in_lookbehind-2.7_2.patch

^{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 = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2015-02-21.10:19:37.056>
created_at = <Date 2010-07-06.10:23:32.852>
labels = ['expert-regex', 'type-bug', 'library']
title = 'Lookback with group references incorrect (two issues?)'
updated_at = <Date 2015-02-21.10:19:37.036>
user = 'https://bugs.python.org/acooke'

bugs.python.org fields:

activity = <Date 2015-02-21.10:19:37.036>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2015-02-21.10:19:37.056>
closer = 'serhiy.storchaka'
components = ['Library (Lib)', 'Regular Expressions']
creation = <Date 2010-07-06.10:23:32.852>
creator = 'acooke'
dependencies = []
files = ['36882', '37324', '37326', '37327']
hgrepos = []
issue_num = 9179
keywords = ['patch']
message_count = 21.0
messages = ['109382', '109383', '109387', '109388', '109389', '109390', '109399', '109400', '227743', '229102', '229917', '230351', '230825', '231889', '231894', '231895', '231897', '231900', '231901', '236358', '236359']
nosy_count = 9.0
nosy_names = ['mark.dickinson', 'larry', 'benjamin.peterson', 'ezio.melotti', 'acooke', 'mrabarnett', 'BreamoreBoy', 'python-dev', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue9179'
versions = ['Python 2.7', 'Python 3.4', 'Python 3.5']

[acooke]

from re import compile

# these work as expected

assert compile('(a)b(?<=b)(c)').match('abc')
assert not compile('(a)b(?<=c)(c)').match('abc')
assert compile('(a)b(?=c)(c)').match('abc')
assert not compile('(a)b(?=b)(c)').match('abc')

# but when you add groups, you get bugs

assert not compile('(?:(a)|(x))b(?<=(?(2)x|c))c').match('abc') # matches!
assert not compile('(?:(a)|(x))b(?<=(?(2)b|x))c').match('abc')
assert compile('(?:(a)|(x))b(?<=(?(2)x|b))c').match('abc') # fails!
assert not compile('(?:(a)|(x))b(?<=(?(1)c|x))c').match('abc') # matches!
assert compile('(?:(a)|(x))b(?<=(?(1)b|x))c').match('abc') # fails!

# but lookahead works as expected

assert compile('(?:(a)|(x))b(?=(?(2)x|c))c').match('abc')
assert not compile('(?:(a)|(x))b(?=(?(2)c|x))c').match('abc')
assert compile('(?:(a)|(x))b(?=(?(2)x|c))c').match('abc')
assert not compile('(?:(a)|(x))b(?=(?(1)b|x))c').match('abc')
assert compile('(?:(a)|(x))b(?=(?(1)c|x))c').match('abc')

# these are similar but, in my opinion, shouldn't even compile
# (group used before defined)

assert not compile('(a)b(?<=(?(2)x|c))(c)').match('abc') # matches!
assert not compile('(a)b(?<=(?(2)b|x))(c)').match('abc')
assert not compile('(a)b(?<=(?(1)c|x))(c)').match('abc') # matches!
assert compile('(a)b(?<=(?(1)b|x))(c)').match('abc') # fails!

assert compile('(a)b(?=(?(2)x|c))(c)').match('abc')
assert not compile('(a)b(?=(?(2)b|x))(c)').match('abc')
assert compile('(a)b(?=(?(1)c|x))(c)').match('abc')

# this is the error we should see above
try:
compile('(a)\\2(b)')
assert False, 'expected error'
except:
pass

[acooke]

I hope the above is clear enough (you need to stare at the regexps for a time) - basically, lookback with a group conditional is not as expected (it appears to be evaluated as lookahead?). Also, some patterns compile that probably shouldn't.

The re package only supports (according to the docs) lookback on expressions whose length is known. So I guess it's also possible that (?(n)pat1|pat2) should always fail that, even when len(pat1) = len(pat2)?

Also, the generally excellent unit tests for the re package don't have much coverage for lookback (I am writing my own regexp lib and it passes all the re unit tests but had a similar bug - that's how I found this one...).

[acooke]

If it's any help, these are the equivalent tests as I think they should be (you'll need to translate engine(parse(... to compile(...)
http://code.google.com/p/rxpy/source/browse/rxpy/src/rxpy/engine/backtrack/_test/engine.py?r=fc52f6959a0cfabdddc6960f47d7380128bb3584#284

[mdickinson]

Thanks very much for the reports.

So I guess it's also possible that (?(n)pat1|pat2) should always fail
that, even when len(pat1) = len(pat2)?

Yes, this seems likely to me. Possibly even the compile stage should fail, though I've no idea how feasible it is to make that happen.

Unfortunately I'm not sure that any of the currently active Python developers is particularly well versed in the intricacies of the re module. The most realistic option here may be just to document the restrictions on lookbehind assertions more clearly. Unless you're able to provide a patch?

[acooke]

I thought someone was working on the re module these days? I thought there I'd seen some issues with patches etc?

Anyway, short term, sorry - no patch. Medium/long term, yes it's possible, but please don't rely on it.

The simplest way to document it is as you suggest, I think - just extend the qualifier on lookback requiring fixed length to exclude references to groups (it does seem to *bind* groups correctly on lookback, so there's no need to exclude them completely).

[mdickinson]

I thought someone was working on the re module these days?

Well, there's bpo-2636. It doesn't seem likely that that work will land in core Python any time soon, though.

[mrabarnett]

Should a regex compile if a group is referenced before it's defined?

Consider this:

(?:(?(2)(a)|(b))+

Other regex implementations permit forward references to groups.

BTW, I had a look at the re module, found it too difficult, and so started on my own implementation of the matching engine (available on PyPI).

[acooke]

Ah good point, thanks.

[BreamoreBoy]

Given the comment from Matthew Barnett in msg109399 "...I had a look at the re module, found it too difficult..." can this be closed as "won't fix"?

[serhiy-storchaka]

Here is a patch which fixes lookbacks with group references and with group conditionals. I have used Andrew's examples as the base for tests.

[serhiy-storchaka]

The patch also fixes bpo-814253.

If there are no objections I'll commit it soon.