classification
Title: re.error: nothing to repeat
Type: behavior Stage: resolved
Components: Library (Lib), Regular Expressions Versions: Python 3.3, Python 3.4, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: serhiy.storchaka Nosy List: Arfrever, arigo, eli.bendersky, ezio.melotti, larry, mrabarnett, pitrou, python-dev, serhiy.storchaka, tim.peters
Priority: normal Keywords: patch

Created on 2013-08-03 20:42 by serhiy.storchaka, last changed 2013-08-25 15:37 by serhiy.storchaka. This issue is now closed.

Files
File name Uploaded Description Edit
issue18647.patch serhiy.storchaka, 2013-08-04 20:44 review
Messages (28)
msg194297 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-08-03 20:42
Now all doctests failed on 32-bit platforms due to the unlucky coincidence of my patch with at least two bugs which were hided before.

SubPattern.getwidth() is wrong, it truncates resulted values to sys.maxsize (should be MAXREPEAT). As side effect of my patch (on 32-bit MAXREPEAT == sys.maxsize) it now returns correct value in some cases on 32-bit platforms. On other hand, the _simple() function in sre_compile.py checks if getwidth() returns (0, MAXREPEAT) and raise an error in such case. Perhaps it should guards against such patterns as '(x*)*' (but it doesn't guards against '(x*y?)*' or '(x*y*)*' and can raise false positive). Now getwidth() returns (0, MAXREPEAT) for '(x*y?)*' on 32-bit platforms (this is a correct result) and triggers the check. The doctest module uses regular expression pattern '(?:.*$\n?)*' which now causes an error.

Definitely SubPattern.getwidth() is wrong and should be fixed. At least one of two, the _simple() function or doctest pattern should be fixed too. The simplest fix is disable the 'nothing to repeat' check.
msg194298 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2013-08-03 20:48
New changeset c243896e12be by Serhiy Storchaka in branch '3.3':
Issue #18647: Temporary disable the "nothing to repeat" check to make buildbots happy.
http://hg.python.org/cpython/rev/c243896e12be

New changeset 4faf9b73c3df by Serhiy Storchaka in branch 'default':
Issue #18647: Temporary disable the "nothing to repeat" check to make buildbots happy.
http://hg.python.org/cpython/rev/4faf9b73c3df
msg194339 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2013-08-04 10:23
New changeset e2ba4592ce3a by Serhiy Storchaka in branch '2.7':
Issue #18647: Temporary disable the "nothing to repeat" check to make buildbots happy.
http://hg.python.org/cpython/rev/e2ba4592ce3a
msg194366 - (view) Author: Eli Bendersky (eli.bendersky) * (Python committer) Date: 2013-08-04 13:13
Would it not be better to temporarily-fix the test rather than the code?
msg194370 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-08-04 13:34
All doctests affected.
msg194373 - (view) Author: Eli Bendersky (eli.bendersky) * (Python committer) Date: 2013-08-04 13:44
Wonderfully terse, as usual. Can you be so kind to elaborate just a tiny bit more? Is the amount of doctests this affects so large that it's better to change the implementation? What are the plans for this "temporary" stage - is there an intention to fix the code "soon" and revert the disabling of this error check?
msg194397 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-08-04 17:19
Serhiy, I don't see the regexp '(?:.*$\n?)*' anywhere in doctest.py.  Are you talking about the _EXAMPLE_RE regexp?  That's the closest I see.

If that's the case, the "nothing to repeat" error is incorrect:  _EXAMPLE_RE also contains a negative lookahead assertion '(?![ ]*$)' to ensure that the later '.*$\n?' part never tries to match an empty string.

That said, it takes some intelligence to realize that the negative lookahead assertion prevents repeating an empty match in this regexp, so it may not be easy to fix this false positive.

A compromise may be to replace

.*$\n?

with

.+$\n? | .*$\n

Both branches then "obviously" consume at least one character.
msg194399 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-08-04 17:35
The doctest engine uses a regexp which contains subpattern which now considered as illegal be the regexp engine (due to unlucky coincidence MAXREPEAT == sys.maxsize on 32-bit platforms). We should rewrite the _simple() function in the re module to be more smart. But if this assumption is correct and this subpattern is really dangerous we should also rewrite a regular expression in the doctest module. In any case we should fix SubPattern.getwidth() so that the behavior on 32-bit and 64-bit platforms should be the same.
msg194400 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-08-04 17:37
Serhiy, I'm asking you to be very explicit about which regexp in doctest.py you're talking about.  If you're talking about the _EXAMPLE_RE regexp, I already explained what's going on with that.  If you're talking about some other regexp, I have no idea which one you're talking about.
msg194406 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-08-04 18:31
> Serhiy, I don't see the regexp '(?:.*$\n?)*' anywhere in doctest.py.  Are you talking about the _EXAMPLE_RE regexp?  That's the closest I see.

Yes, it is. In my previous message I answered Eli.

> If that's the case, the "nothing to repeat" error is incorrect:  _EXAMPLE_RE also contains a negative lookahead assertion '(?![ ]*$)' to ensure that the later '.*$\n?' part never tries to match an empty string.

Thank you for explanation. Unlucky the getwidth() method is not smart enough to detect that minimal length of matched string is not 0. We should made either the getwidth() method or the _simple() function (or both) more smart.

> A compromise may be to replace
> .*$\n?
> with
> .+$\n? | .*$\n

I'm sure similar patterns are used in third-party code. We shouldn't break them, therefore we should fix _simple()/getwidth().
msg194412 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-08-04 19:34
I'm afraid it's just too tricky for the code to deduce that a negative lookahead assertion can imply that a later match can't be empty.  But I don't know how smart the re compilation code already is ;-)

It occurs to me now that the doctest regexp could worm around this very easily, via replacing:

.*$\n?

with:

.+$\n?

The success of the negative lookahead assertion here doesn't _just_ imply that


.*$\n?

will match a non-empty string, it also implies that

.+$

will succeed (and so also that .+$\n? will succeed).
msg194419 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-08-04 20:44
Agree. Here is a partial patch which fixes getwidth() and doctest regexp. But I don't know how to fix _simple(). Perhaps we should permanently remove the "nothing to repeat" check. It guards only against '(.*)*', but there are other methods to make regexp matching exponential (i.e. '(.?.?)*').
msg194426 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-08-04 21:09
Matching an empty string an unbounded number of times isn't a case of exponential runtime, it's a case of infinite runtime, unless the regexp internals are smart enough to cut the search off (I don't know enough about re's internals to know whether it's smart enough to do so).

So it's worth catching at compile time if it can be caught.  Alas, regexps are so complicated I doubt it's possible to do so without false positives or false negatives short of major effort.

For now, at least the doctest part of the patch should be harmless ;-)
msg194434 - (view) Author: Matthew Barnett (mrabarnett) * (Python triager) Date: 2013-08-04 22:38
Suppose you have a repeated pattern, such as "(?:...)*" or "(?:...){0,100}".

If, after matching the subpattern, the text position hasn't changed, and none of the capture groups have changed, then there has been no progress, and the subpattern will be matched again with no more progress, unless the maximum count has been reached, at which point it'll continue with the remainder of the pattern. If there's no minimum count, then the subpattern will be matched repeatedly forever.

Therefore, what a repeat should do is not to attempt any more iterations if the text position hasn't changed and none of the capture groups have changed.
msg194437 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-08-04 23:15
Matthew, yes, I agree that a regexp engine can be coded to be robust against unboundedly repeated matching of an empty string.  I don't know whether Python's current engine is so coded.  It's easy to trick the 2.7 engine into accepting regexps that do try to match an empty string endlessly, but across all I've tried none show "infinite loop" (or even slow) behavior.
msg194438 - (view) Author: Matthew Barnett (mrabarnett) * (Python triager) Date: 2013-08-04 23:40
Python's current regex engine isn't so coded. That's the reason for the up-front check.
msg194440 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-08-04 23:54
> Python's current regex engine isn't so coded. That's
> the reason for the up-front check.

It's peculiar then that nobody noticed before now that the check was so badly broken ;-)

Offhand, do you have an example that displays bad behavior in 2.7?  I'm curious because I didn't find one after half an hour of trying.
msg194553 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-08-06 14:45
Originally the catch condition was (lo == 0). It was changed in changeset 41c42b1bd582.

> Offhand, do you have an example that displays bad behavior in 2.7?  I'm curious because I didn't find one after half an hour of trying.

re.match('(?:.?.?)*y', 'x'*20)
msg194568 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-08-06 17:04
Serhiy, yup, that regexp is slow, but it does finish - so the engine is doing something to avoid _unbounded_ repetitive matching of an empty string.

Change it to

(?:.?.+)*y

and the group can no longer match an empty string, but it's still slow (although about 3x faster, it's still exponential in the length of the string it fails to match).
msg194785 - (view) Author: Armin Rigo (arigo) * (Python committer) Date: 2013-08-10 07:22
Just a side note for 2.7: could I recommend people to be really extra, extra careful when changing what kind of regexps are accepted and what kind of regexps are outright rejected?  I believe the risk of making long-existing and working 2.7 programs suddenly crash on the next 2.7 micro version should *by far* outweight the theoretical advantage of crashing early on sufficiently bogus regexps.

(Fwiw, I believe the same would apply on 3.x too, where rejecting previously-accepted regexps should only be done in a minor version upgrade.)
msg194787 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-08-10 08:26
> Serhiy, yup, that regexp is slow, but it does finish - so the engine is doing something to avoid _unbounded_ repetitive matching of an empty string.

Yes, it finish, but it has exponential computation complexity. Increase the length of the string to 21, 22, 30, 100...

There were multiple bug reports about "hanged" regexps which actually had quadratic or exponential computation complexity (see for example issue1662581, issue16430, issue15077, issue15515). In all such cases the regexp can be rewritten to have linear computation complexity. However peoples constantly do such mistakes.

Armin, I totally agree with you.

Note that before b78c321ee9a5 the regexp '(?:.{0,60000}.{0,5535})?' was forbidden while '(?:.{0,60000}.{0,5534})?' and '(?:.{0,60000}.{0,5536})?' were allowed. Existing check allowed false positives.
msg194823 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-08-10 17:51
Serhiy, yes, I know the regexp you gave takes exponential time.  But:

1. This appears to have nothing to do with repeated 0-length matches.  I gave you an example of a very similar regexp that also takes exponential time, but never makes any 0-length sub-match.

2. Matthew said that Python's engine is not robust against _unbounded_ repeated matching of an empty sub-match, and so "That's the reason for the up-front check".  I was asking for an example of _that_ behavior.  I still haven't seen one.

My goal here is to understand why we're doing this check at all.  If Python's engine cannot in fact be provoked into an infinite loop, the check has at best very little value, as there are many ways to provoke exponential-time behavior, and the possibility of a repeated 0-length sub-match doesn't appear to have much (if anything) to do with it.

(By the way, exponential-time regexps can't always be rewritten to take linear time, although it takes gimmicks like back references to create examples that are inherently expensive.)
msg194825 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-08-10 18:39
> 2. Matthew said that Python's engine is not robust against _unbounded_ repeated matching of an empty sub-match, and so "That's the reason for the up-front check".  I was asking for an example of _that_ behavior.  I still haven't seen one.

Perhaps Matthew did not understand you or you did not understand Matthew. 
For non-greedy repeats this was fixed in issue9669 (thank to Matthew). For greedy repeats this was fixed some time before.
msg194826 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2013-08-10 18:43
So does anyone believe this check serves a useful purpose _now_?  Doesn't seem so to me.
msg194871 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-08-11 07:57
And not to me. This check forbids some possible legal regexps and doesn't prevent from shooting in the leg.
msg194897 - (view) Author: Matthew Barnett (mrabarnett) * (Python triager) Date: 2013-08-11 15:59
I think you're probably right.
msg195219 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-08-14 21:29
So what now? Just remove unneeded check?

Related issues: issue1633953, issue2537.
msg195661 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2013-08-19 20:30
New changeset de049e9abdf7 by Serhiy Storchaka in branch '3.3':
Issue #18647: Correctly bound calculated min/max width of a subexpression.
http://hg.python.org/cpython/rev/de049e9abdf7

New changeset e47f2dc564bc by Serhiy Storchaka in branch 'default':
Issue #18647: Correctly bound calculated min/max width of a subexpression.
http://hg.python.org/cpython/rev/e47f2dc564bc

New changeset d10c287c200c by Serhiy Storchaka in branch '2.7':
Issue #18647: Correctly bound calculated min/max width of a subexpression.
http://hg.python.org/cpython/rev/d10c287c200c

New changeset 19ed2fbb8e6b by Serhiy Storchaka in branch '3.3':
Issue #18647: A regular expression in the doctest module rewritten so that
http://hg.python.org/cpython/rev/19ed2fbb8e6b

New changeset 8b24818c7327 by Serhiy Storchaka in branch 'default':
Issue #18647: A regular expression in the doctest module rewritten so that
http://hg.python.org/cpython/rev/8b24818c7327

New changeset c2dc99ec46bc by Serhiy Storchaka in branch '2.7':
Issue #18647: A regular expression in the doctest module rewritten so that
http://hg.python.org/cpython/rev/c2dc99ec46bc

New changeset 7ab07f15d78c by Serhiy Storchaka in branch '3.3':
Issue #2537: Remove breaked check which prevented valid regular expressions.
http://hg.python.org/cpython/rev/7ab07f15d78c

New changeset f4271cc2dfb5 by Serhiy Storchaka in branch 'default':
Issue #2537: Remove breaked check which prevented valid regular expressions.
http://hg.python.org/cpython/rev/f4271cc2dfb5

New changeset 7b867a46a8b4 by Serhiy Storchaka in branch '2.7':
Issue #2537: Remove breaked check which prevented valid regular expressions.
http://hg.python.org/cpython/rev/7b867a46a8b4
History
Date User Action Args
2013-08-25 15:37:45serhiy.storchakasetstatus: open -> closed
resolution: fixed
stage: commit review -> resolved
2013-08-19 20:44:29serhiy.storchakasetstage: commit review
2013-08-19 20:30:24python-devsetmessages: + msg195661
2013-08-14 21:29:15serhiy.storchakasetmessages: + msg195219
2013-08-11 15:59:15mrabarnettsetmessages: + msg194897
2013-08-11 07:57:19serhiy.storchakasetmessages: + msg194871
2013-08-10 18:43:47tim.peterssetmessages: + msg194826
2013-08-10 18:39:15serhiy.storchakasetmessages: + msg194825
2013-08-10 17:51:45tim.peterssetmessages: + msg194823
2013-08-10 08:26:45serhiy.storchakasetmessages: + msg194787
2013-08-10 07:22:39arigosetnosy: + arigo
messages: + msg194785
2013-08-06 17:04:52tim.peterssetmessages: + msg194568
2013-08-06 14:45:30serhiy.storchakasetmessages: + msg194553
2013-08-04 23:54:31tim.peterssetmessages: + msg194440
2013-08-04 23:40:31mrabarnettsetmessages: + msg194438
2013-08-04 23:15:01tim.peterssetmessages: + msg194437
2013-08-04 22:38:06mrabarnettsetmessages: + msg194434
2013-08-04 21:09:08tim.peterssetmessages: + msg194426
2013-08-04 20:44:48serhiy.storchakasetfiles: + issue18647.patch
keywords: + patch
messages: + msg194419
2013-08-04 19:34:49tim.peterssetmessages: + msg194412
2013-08-04 18:31:38serhiy.storchakasetmessages: + msg194406
2013-08-04 17:37:09tim.peterssetmessages: + msg194400
2013-08-04 17:35:34serhiy.storchakasetmessages: + msg194399
2013-08-04 17:19:27tim.peterssetmessages: + msg194397
2013-08-04 13:44:10eli.benderskysetmessages: + msg194373
2013-08-04 13:34:33serhiy.storchakasetmessages: + msg194370
2013-08-04 13:13:50eli.benderskysetnosy: + eli.bendersky
messages: + msg194366
2013-08-04 10:23:13python-devsetmessages: + msg194339
2013-08-03 23:07:48tim.peterssetnosy: + tim.peters
2013-08-03 22:31:14Arfreversetnosy: + Arfrever
2013-08-03 20:48:44python-devsetnosy: + python-dev
messages: + msg194298
2013-08-03 20:42:07serhiy.storchakacreate