homepage

Hi!
re.finditer() seems to incorrectly increment the current position immediately after matching a zero-length substring. For example:
>>> [m.groups() for m in re.finditer(r'(^z*)|(\w+)', 'abc')]
[('', None), (None, 'bc')]
What happened to the 'a'? I expected this result:
[('', None), (None, 'abc')]
Perl agrees with me:
% perl -le 'print defined(1ドル)?"\"1ドル\"":"undef",",",defined(2ドル)?"\"2ドル\"":"undef" while "abc" =~ /(z*)|(\w+)/g' 
"",undef
undef,"abc"
"",undef
Similarly, if I remove the ^:
>>> [m.groups() for m in re.finditer(r'(z*)|(\w+)', 'abc')]
[('', None), ('', None), ('', None), ('', None)]
Now all of the letters have fallen through the cracks! I expected this result:
[('', None), (None, 'abc'), ('', None)]
Again, perl agrees:
% perl -le 'print defined(1ドル)?"\"1ドル\"":"undef",",",defined(2ドル)?"\"2ドル\"":"undef" while "abc" =~ /(z*)|(\w+)/g' 
"",undef
undef,"abc"
"",undef
If this bug has already been reported, I apologize -- I wasn't able to find it here. I haven't looked at the code for the re module, but this seems like the sort of bug that might have been accidentally introduced in order to try to prevent the same zero-length match from being returned forever.
Thanks,
Jacques

This also affects re.findall().

What should:
 [m.groups() for m in re.finditer(r'(^z*)|(^q*)|(\w+)', 'abc')]
return? Should the second group also yield a zero-width match before the
third group is tried? I think it probably should. Does Perl?

Hmmm. This strikes me as a bug, beyond the realm of Issue 3262. The
two items may be related, but the dropping of the 'a' seems like
unexpected behaviour that I doubt any current code is expecting to
occur. Clearly, what is going on is that the Engine starts scanning at
the 'a', finds the Zero-Width match and, having found a match,
increments its pointer within the input string, thus skipping the 'a'
when it matches 'bc'.
If it is indeed a bug, I think this should be considered for inclusion
in Python 2.6 rather than being part of the new Engine Design in Issue
3626. I think the solution would simply be to not increment the ptr
(which points to the input string) when findall / finditer encounters a
Zero-Width match.

Never mind inclusion in 2.6 as no-one has repeated this bug in re-world
examples yet so it's going to have to wait for the Regexp 2.7 engine in
issue 2636.

Ah, I see the problem, if ptr is not incremented, then it will keep
matching the first expression, (^z*), so it would have to both 'skip'
the 'a' and NOT skip the 'a'. Hmm. You're right, Matthew, this is
pretty complicated. Now, for your expression, Matthew,
r'(z*)|(^q*)|(\w+)', Perl gives:
"",undef,undef
undef,undef,"abc"
"",undef,undef
Meaning it doesn't even bother matching the ^q* since the ^z* matches
first. This seems the logical behaviour and fits with the idea that a
Zero-Width match would both only match once and NOT consume any
characters. An internal flag would just have to be created to tell the
2 find functions whether the current value of ptr would allow for a "No
Zero-Width Match" option on second go-around.

What about r'(^z*)|(q*)|(\w+)'? I could imagine that the first group
could match only at the start of the string, but if the second group
doesn't have that restriction then it could match the second time, and
only after that could the third match, if you see what I mean. (The
previous example had (^q*) so it couldn't match because the first group
has already matched at the start of the string and we've already
advanced beyond that, even though by no characters!)

FYI, I posted msg73737 after finding that the fix for the original case
was really very simple, but then thought about whether it would behave
as expected when there were more zero-width matches, hence the later posts.

Perl gives this result for your new expression:
"",undef,undef
undef,undef,"abc"
undef,"",undef
I think it has to do with not thinking of a string as a sequence of
characters, but as a sequence of characters separated by null-space. 
Null-space is can be captured, but ONLY if it is part of a zero-width
match, and once captured, it can no longer be captured by another
zero-width expression. This is in keeping which what I see as Perl's
behaviour, namely that the (q*) group never participates in the first
match because, initially the (^z*) captures it. OTOH, when it gets to
the null-space AFTER the 'abc' capture, the (^z*) cannot participate
because it has a "at-beginning" restriction. The evaluator then moves
on to the (q*), which has no such restriction and this time it matches,
consuming the final null-space.

I have to report that the fix appears to be successful:
>>> print [m.groups() for m in re.finditer(r'(^z*)|(\w+)', 'abc')]
[('', None), (None, 'abc')]
>>> print re.findall(r"(^z*)|(\w+)", "abc")
[('', ''), ('', 'abc')]
>>> print [m.groups() for m in re.finditer(r"(^z*)|(q*)|(\w+)", "abc")]
[('', None, None), (None, None, 'abc'), (None, '', None)]
>>> print re.findall(r"(^z*)|(q*)|(\w+)", "abc")
[('', '', ''), ('', '', 'abc'), ('', '', '')]
The patch is regex_2.6rc2+7.diff.

Matthew, I'll try to merge all your diffs with the current repository
over the weekend. Having done the first, I know where code differs
between your implementation, mine and the base, so I can apply your
patch, and then a patch that restores my changes so the rest of the
merges should be easy! :)

I just re-tested this issue in trunk at changeset 053bc5ca199b and the issue is still exactly reproducible as originally reported. That is, the match to the empty string skips a character of the match:
>>> import re
>>> [m.groups() for m in re.finditer(r'(^z*)|(\w+)', 'abc')]
[('', None), (None, 'bc')]

This is still an issue today:
>>> import re
>>> [m.groups() for m in re.finditer(r'(^z*)|(\w+)', 'abc')]
[('', None), (None, 'bc')]

How does "the Regexp 2.7 engine in issue 2636" from msg73742 deal with this situation?

New changeset 70d56fb52582d9d3f7c00860d6e90570c6259371 by Serhiy Storchaka in branch 'master':
bpo-25054, bpo-1647489: Added support of splitting on zerowidth patterns. (#4471)
https://github.com/python/cpython/commit/70d56fb52582d9d3f7c00860d6e90570c6259371