classification
Title: Capturing start of line '^'
Type: behavior Stage: resolved
Components: Regular Expressions Versions: Python 3.7, Python 3.6, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: serhiy.storchaka Nosy List: Alcolo Alcolo, ezio.melotti, martin.panter, mrabarnett, r.david.murray, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2015-09-10 12:19 by Alcolo Alcolo, last changed 2018-03-14 17:16 by serhiy.storchaka. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 4471 merged serhiy.storchaka, 2017-11-19 23:36
PR 4678 closed serhiy.storchaka, 2017-12-02 17:32
Messages (15)
msg250364 - (view) Author: Alcolo Alcolo (Alcolo Alcolo) Date: 2015-09-10 12:19
Why
re.findall('^|a', 'a') != ['', 'a'] ?

We have:
re.findall('^|a', ' a') == ['', 'a']
and
re.findall('$|a', ' a') == ['a', '']

Capturing '^' take the 1st character. It's look like a bug ...
msg250366 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2015-09-10 12:27
^ finds an empty match at the beginning of the string, $ finds an empty match at the end.  I don't see the bug (but I'm not a regex expert).
msg250370 - (view) Author: Matthew Barnett (mrabarnett) * (Python triager) Date: 2015-09-10 13:34
After matching '^', it advances so that it won't find the same match again (and again and again...).

Unfortunately, that means that it sometimes misses some matches.

It's a known issue.
msg250377 - (view) Author: Alcolo Alcolo (Alcolo Alcolo) Date: 2015-09-10 14:02
Naively, I thinked that ^ is be considered as a 0-length token (like $, \b, \B), then after capturing it, we can read the next token : 'a' (for the input string "a").

I use a simple work around: prepending my string with ' ' (because ' ' is neutral with my regex results).
msg250392 - (view) Author: Matthew Barnett (mrabarnett) * (Python triager) Date: 2015-09-10 17:09
Just to confirm, it _is_ a bug.

It tries to avoid getting stuck, but the way it does that causes it to skip a character, sometimes missing a match it should have found.
msg257296 - (view) Author: Ezio Melotti (ezio.melotti) * (Python committer) Date: 2016-01-01 20:40
AFAIU the problem is at Modules/_sre.c:852: after matching, if the ptr is still at the start position, the start position gets incremented to avoid an endless loop.
Ideally the problem could be avoided by marking and skipping the part(s) of the pattern that have already been tested and produced a zero-length match, however I don't see any easy way to do it.
Unless someone can come up with a reasonable solution, I would suggest to close this as wontfix, and possibly add a note to the docs about this corner case.
msg306517 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-11-20 00:04
PR 4471 fixes this issue, issue1647489, and a couple of similar issues.

The most visible change is the change in re.split(). This is compatibility breaking change, and it affects third-party code. But ValueError or FutureWarning were raised for patterns that will change the behavior in this PR for two Python releases, since Python 3.5. Developers had enough time for fixing them. In most cases this is so trivial as changing `*` to `+` in `\s*`.

Changes in sub(), findall(), and finditer() are less visible. No one existing test needs modification for them. Was:

>>> re.split(r"\b|:+", "a::bc")
/usr/lib/python3.6/re.py:212: FutureWarning: split() requires a non-empty pattern match.
  return _compile(pattern, flags).split(string, maxsplit)
['a:', 'bc']
>>> re.sub(r"\b|:+", "-", "a::bc")
'-a-:-bc-'
>>> re.findall(r"\b|:+", "a::bc")
['', '', ':', '', '']
>>> list(re.finditer(r"\b|:+", "a::bc"))
[<_sre.SRE_Match object; span=(0, 0), match=''>, <_sre.SRE_Match object; span=(1, 1), match=''>, <_sre.SRE_Match object; span=(2, 3), match=':'>, <_sre.SRE_Match object; span=(3, 3), match=''>, <_sre.SRE_Match object; span=(5, 5), match=''>]

Fixed:

>>> re.split(r"\b|:+", "a::bc")
['', 'a', '', 'bc', '']
>>> re.sub(r"\b|:+", "-", "a::bc")
'-a--bc-'
>>> re.findall(r"\b|:+", "a::bc")
['', '', '::', '', '']
>>> list(re.finditer(r"\b|:+", "a::bc"))
[<re.Match object; span=(0, 0), match=''>, <re.Match object; span=(1, 1), match=''>, <re.Match object; span=(1, 3), match='::'>, <re.Match object; span=(3, 3), match=''>, <re.Match object; span=(5, 5), match=''>]

The behavior of re.split(), re.findall() and re.finditer() now is the same as in the regex module with the V1 flag. But the behavior of re.sub() left closer to the previous behavior, otherwise this would break existing tests. It is consistent with re.split() rather of re.findall() and re.finditer(). In regex with the V1 flag sub() is consistent with findall() and finditer(), but not with split().
msg307400 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-01 18:54
Could anybody please make review at least of the documentation part? I want to merge this before 3.7.0a3 be released.

Initially I was going to backport the part that relates findall(), finditer() and sub(). It changes the behavior only in corner cases and I didn't expect it can break a real code. But since it broke a pattern in the doctest module, I afraid it can break a third-party code.
msg307424 - (view) Author: Martin Panter (martin.panter) * (Python committer) Date: 2017-12-02 10:50
The new “finditer” behaviour seems to contradict the documentation about excluding empty matches if they touch the start of another match.

>>> list(re.finditer(r"\b|:+", "a::bc"))
[<re.Match object; span=(0, 0), match=''>, <re.Match object; span=(1, 1), match=''>, <re.Match object; span=(1, 3), match='::'>, <re.Match object; span=(3, 3), match=''>, <re.Match object; span=(5, 5), match=''>]

An empty match at (1, 1) is included, despite it touching the beginning of the match at (1, 3). My best guess is that when an empty match is found, searching continues at the same position for the first non-empty match.
msg307441 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-02 17:37
Good point. Neither old nor new (which matches regex) behaviors conform the documentation: "Empty matches are included in the result unless they touch the beginning of another match." It is easy to exclude empty matches that touch the *ending* of another match. This would be consistent with the new behavior of split() and sub().

But this would break a one existing test for issue817234. Though that issue shouldn't rely on this detail. The test should just test that iterating doesn't hang.

And this would break a regular expression in pprint.

PR 4678 implements this version. I don't know what version is better.

>>> list(re.finditer(r"\b|:+", "a::bc"))
[<re.Match object; span=(0, 0), match=''>, <re.Match object; span=(1, 1), match=''>, <re.Match object; span=(1, 3), match='::'>, <re.Match object; span=(5, 5), match=''>]
>>> re.sub(r"(\b|:+)", r"[\1]", "a::bc")
'[]a[][::]bc[]'

With PR 4471 the result of re.sub() is the same, but the result of re.finditer() is as in msg307424.
msg307454 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-02 20:11
The clause "Empty matches are included in the result unless they touch the beginning of another match" was added in 2f3e5483a3324b44fa5dbbb98859dc0ac42b6070 (issue732120) and I suppose it never was correct. So we can ignore it in the context of this issue.
msg307461 - (view) Author: Matthew Barnett (mrabarnett) * (Python triager) Date: 2017-12-02 21:29
The pattern:

    \b|:+

will match a word boundary (zero-width) before colons, so if there's a word followed by colons, finditer will find the boundary and then the colons. You _can_ get a zero-width match (ZWM) joined to the start of a nonzero-width match (NWM). That's not really surprising.

If you wanted to avoid a ZWM joined to either end of a NWM, you'd need to keep looking for another match at a position even after you'd already found a match if what you'd found was zero-width. That would also affect re.search and re.match.

For regex on Python 3.7, I'm going with avoiding a ZWM joined to the end of a NWM, unless re's going a different way, in which case I have more work to do to remain compatible! The change I did for Python 3.7+ was trivial.
msg307467 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-02 22:01
Avoiding ZWM after a NWM in re.sub() is explicitly documented (and the documentation is correct in this case). This follows the behavior in the ancient RE implementation. Once it was broken in sre, but then fixed (see 21009b9c6fc40b25fcb30ee60d6108f235733e40, issue462270). Changing this behavior doesn't break anything in the stdlib except the specially purposed test. I think it is better to keep this behavior, but maybe discuss its changing (for making matching the behavior of other RE engines) in the separate issue.

I don't know how the behavior of findall() and finditer() is related to this.
msg307476 - (view) Author: Matthew Barnett (mrabarnett) * (Python triager) Date: 2017-12-02 22:48
findall() and finditer() consist of multiple uses of search(), basically, as do sub() and split(), so we want the same rule to apply to them all.
msg307557 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-04 12:29
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
History
Date User Action Args
2018-03-14 17:16:23serhiy.storchakasetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2017-12-04 12:29:09serhiy.storchakasetmessages: + msg307557
2017-12-02 22:48:58mrabarnettsetmessages: + msg307476
2017-12-02 22:01:15serhiy.storchakasetmessages: + msg307467
2017-12-02 21:29:18mrabarnettsetmessages: + msg307461
2017-12-02 20:11:22serhiy.storchakasetmessages: + msg307454
2017-12-02 17:37:24serhiy.storchakasetmessages: + msg307441
2017-12-02 17:32:36serhiy.storchakasetpull_requests: + pull_request4586
2017-12-02 10:50:48martin.pantersetnosy: + martin.panter
messages: + msg307424
2017-12-01 18:54:36serhiy.storchakasetmessages: + msg307400
2017-11-20 00:04:13serhiy.storchakasetmessages: + msg306517
2017-11-19 23:36:58serhiy.storchakasetkeywords: + patch
stage: patch review
pull_requests: + pull_request4403
2017-11-16 14:01:20serhiy.storchakasetassignee: serhiy.storchaka

nosy: + serhiy.storchaka
versions: + Python 2.7, Python 3.7, - Python 3.5
2016-01-01 20:41:00ezio.melottisetmessages: + msg257296
versions: + Python 3.5, Python 3.6, - Python 3.4
2015-09-10 17:09:35mrabarnettsetmessages: + msg250392
2015-09-10 14:02:01Alcolo Alcolosetmessages: + msg250377
2015-09-10 13:34:55mrabarnettsetmessages: + msg250370
2015-09-10 12:27:44r.david.murraysetnosy: + r.david.murray
messages: + msg250366
2015-09-10 12:19:56Alcolo Alcolocreate