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.

[serhiy-storchaka]

If there are no objections I'm going to commit the patch soon.

[python-dev]

New changeset fac649bf2d10 by Serhiy Storchaka in branch '2.7':
Issues bpo-814253, bpo-9179: Group references and conditional group references now
https://hg.python.org/cpython/rev/fac649bf2d10

New changeset 9fcf4008b626 by Serhiy Storchaka in branch '3.4':
Issues bpo-814253, bpo-9179: Group references and conditional group references now
https://hg.python.org/cpython/rev/9fcf4008b626

New changeset 60fccf0aad83 by Serhiy Storchaka in branch 'default':
Issues bpo-814253, bpo-9179: Group references and conditional group references now
https://hg.python.org/cpython/rev/60fccf0aad83

[serhiy-storchaka]

The more I think about it, the more doubt. This patch added a behavior that is incompatible with the regex module. The regex module proceeds lookbehind assertions in the opposite direction, from right to left. This allows it to work with lookbehind assertions of non-fixed length. But the side effect is that in regex group reference in lookbehind assertion can refer only to a group defined right in the same lookbehind assertion (or defined left outside). In re now group reference in lookbehind assertion can refer only to a group defined left. This is likely to change in the future, which brings us to the problem of incompatibility.

There are several quick ways to resolve the problem:

1. Rollback the patch and return to the previous non-working behavior. Because of the obvious non-working the problem with changing the implementation of lookbehind assertion in the future will be weaker.

2. Rollback the patch and emit a warning or error when using any group references in lookbehind assertion. Something like patch proposed by Greg Chapman in bpo-814253 (but slightly more advanced).

3. Leave the patch and emit a warning or an error when using group references to the group defined in this same lookbehind assertion. Group references will work in lookbehind assertions in most cases except rare cases when current re behavior differs from regex behavior.

What is your decision Benjamin?

Here is a patch against 2.7 which implements variant 3.

[python-dev]

New changeset d1f7c3f45ffe by Benjamin Peterson in branch '3.4':
backout 9fcf4008b626 (bpo-9179) for further consideration
https://hg.python.org/cpython/rev/d1f7c3f45ffe

New changeset f385bc6e6e09 by Benjamin Peterson in branch 'default':
merge 3.4 (bpo-9179)
https://hg.python.org/cpython/rev/f385bc6e6e09

New changeset 8a3807e15a1f by Benjamin Peterson in branch '2.7':
backout fac649bf2d10 (bpo-9179) for further consideration
https://hg.python.org/cpython/rev/8a3807e15a1f

[benjaminp]

I just backed out the change. Thanks for brining up the issue.

[serhiy-storchaka]

What would be the best solution for 2.7?

Here is a patch which forbids any group references in lookbehind assertions (they are not work currently and users shouldn't use them).

[benjaminp]

On Sun, Nov 30, 2014, at 12:55, Serhiy Storchaka wrote:

Serhiy Storchaka added the comment:

What would be the best solution for 2.7?

You can pick. I just always favor not changing things for release
candidates.

Here is a patch which forbids any group references in lookbehind
assertions (they are not work currently and users shouldn't use them).

[serhiy-storchaka]

Updated documentation. If there are no objections I'll commit re_forbid_groupref_in_lookbehind-2.7_2.patch to 2.7 and 3.4. For 3.5 I prefer to add support of group references.

[python-dev]

New changeset b78195af96f5 by Serhiy Storchaka in branch 'default':
Issues bpo-814253, bpo-9179: Group references and conditional group references now
https://hg.python.org/cpython/rev/b78195af96f5

New changeset 5387095b8675 by Serhiy Storchaka in branch '2.7':
Issues bpo-814253, bpo-9179: Warnings now are raised when group references and
https://hg.python.org/cpython/rev/5387095b8675

New changeset e295ad9be16d by Serhiy Storchaka in branch '3.4':
Issues bpo-814253, bpo-9179: Warnings now are raised when group references and
https://hg.python.org/cpython/rev/e295ad9be16d

[serhiy-storchaka]

Only warnings are raised in 2.7 and 3.4, so it will not break third party code that "works" by accident. In 3.5 only references to groups defined outside of lookbehind assertion work, so the behavior is compatible with regex.