re.error: nothing to repeat #62847

serhiy-storchaka · 2013-08-03T20:42:07Z

BPO	18647
Nosy	@tim-one, @arigo, @pitrou, @larryhastings, @ezio-melotti, @serhiy-storchaka
Files	issue18647.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 2013-08-25.15:37:45.729>
created_at = <Date 2013-08-03.20:42:07.237>
labels = ['expert-regex', 'type-bug', 'library']
title = 're.error: nothing to repeat'
updated_at = <Date 2013-08-25.15:37:45.729>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2013-08-25.15:37:45.729>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2013-08-25.15:37:45.729>
closer = 'serhiy.storchaka'
components = ['Library (Lib)', 'Regular Expressions']
creation = <Date 2013-08-03.20:42:07.237>
creator = 'serhiy.storchaka'
dependencies = []
files = ['31159']
hgrepos = []
issue_num = 18647
keywords = ['patch']
message_count = 28.0
messages = ['194297', '194298', '194339', '194366', '194370', '194373', '194397', '194399', '194400', '194406', '194412', '194419', '194426', '194434', '194437', '194438', '194440', '194553', '194568', '194785', '194787', '194823', '194825', '194826', '194871', '194897', '195219', '195661']
nosy_count = 10.0
nosy_names = ['tim.peters', 'arigo', 'pitrou', 'larry', 'ezio.melotti', 'mrabarnett', 'Arfrever', 'eli.bendersky', 'python-dev', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue18647'
versions = ['Python 2.7', 'Python 3.3', 'Python 3.4']

serhiy-storchaka · 2013-08-03T20:42:07Z

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.

python-dev · 2013-08-03T20:48:45Z

New changeset c243896e12be by Serhiy Storchaka in branch '3.3':
Issue bpo-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 bpo-18647: Temporary disable the "nothing to repeat" check to make buildbots happy.
http://hg.python.org/cpython/rev/4faf9b73c3df

python-dev · 2013-08-04T10:23:13Z

New changeset e2ba4592ce3a by Serhiy Storchaka in branch '2.7':
Issue bpo-18647: Temporary disable the "nothing to repeat" check to make buildbots happy.
http://hg.python.org/cpython/rev/e2ba4592ce3a

elibendersky · 2013-08-04T13:13:50Z

Would it not be better to temporarily-fix the test rather than the code?

serhiy-storchaka · 2013-08-04T13:34:34Z

All doctests affected.

elibendersky · 2013-08-04T13:44:10Z

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?

tim-one · 2013-08-04T17:19:27Z

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.

serhiy-storchaka · 2013-08-04T17:35:34Z

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.

tim-one · 2013-08-04T17:37:09Z

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.

serhiy-storchaka · 2013-08-04T18:31:38Z

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().

tim-one · 2013-08-04T19:34:49Z

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).

serhiy-storchaka · 2013-08-04T20:44:48Z

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. '(.?.?)').

tim-one · 2013-08-04T21:09:09Z

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 ;-)

mrabarnett · 2013-08-04T22:38:06Z

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.

tim-one · 2013-08-04T23:15:01Z

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.

mrabarnett · 2013-08-04T23:40:32Z

Python's current regex engine isn't so coded. That's the reason for the up-front check.

tim-one · 2013-08-04T23:54:31Z

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.

serhiy-storchaka · 2013-08-06T14:45:30Z

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)

tim-one · 2013-08-06T17:04:52Z

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).

arigo · 2013-08-10T07:22:39Z

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.)

serhiy-storchaka · 2013-08-10T08:26:45Z

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 bpo-1662581, bpo-16430, bpo-15077, bpo-15515). 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.

tim-one · 2013-08-10T17:51:45Z

Serhiy, yes, I know the regexp you gave takes exponential time. But:

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.
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.)

serhiy-storchaka · 2013-08-10T18:39:16Z

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 bpo-9669 (thank to Matthew). For greedy repeats this was fixed some time before.

tim-one · 2013-08-10T18:43:47Z

So does anyone believe this check serves a useful purpose _now_? Doesn't seem so to me.

serhiy-storchaka · 2013-08-11T07:57:20Z

And not to me. This check forbids some possible legal regexps and doesn't prevent from shooting in the leg.

mrabarnett · 2013-08-11T15:59:16Z

I think you're probably right.

serhiy-storchaka · 2013-08-14T21:29:15Z

So what now? Just remove unneeded check?

Related issues: bpo-1633953, bpo-2537.

python-dev · 2013-08-19T20:30:24Z

New changeset de049e9abdf7 by Serhiy Storchaka in branch '3.3':
Issue bpo-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 bpo-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 bpo-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 bpo-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 bpo-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 bpo-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 bpo-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 bpo-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 bpo-2537: Remove breaked check which prevented valid regular expressions.
http://hg.python.org/cpython/rev/7b867a46a8b4

serhiy-storchaka self-assigned this Aug 3, 2013

serhiy-storchaka added stdlib Python modules in the Lib dir topic-regex type-bug An unexpected behavior, bug, or error labels Aug 3, 2013

serhiy-storchaka closed this as completed Aug 25, 2013

ezio-melotti transferred this issue from another repository Apr 10, 2022

dirkf mentioned this issue Feb 20, 2023

{Vimeo] "sre_constants.error: nothing to repeat" when running under Python 2.7.3 ytdl-org/youtube-dl#31597

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

re.error: nothing to repeat #62847

re.error: nothing to repeat #62847

serhiy-storchaka commented Aug 3, 2013

serhiy-storchaka commented Aug 3, 2013

python-dev mannequin commented Aug 3, 2013

python-dev mannequin commented Aug 4, 2013

elibendersky mannequin commented Aug 4, 2013

serhiy-storchaka commented Aug 4, 2013

elibendersky mannequin commented Aug 4, 2013

tim-one commented Aug 4, 2013

serhiy-storchaka commented Aug 4, 2013

tim-one commented Aug 4, 2013

serhiy-storchaka commented Aug 4, 2013

tim-one commented Aug 4, 2013

serhiy-storchaka commented Aug 4, 2013

tim-one commented Aug 4, 2013

mrabarnett mannequin commented Aug 4, 2013

tim-one commented Aug 4, 2013

mrabarnett mannequin commented Aug 4, 2013

tim-one commented Aug 4, 2013

serhiy-storchaka commented Aug 6, 2013

tim-one commented Aug 6, 2013

arigo mannequin commented Aug 10, 2013

serhiy-storchaka commented Aug 10, 2013

tim-one commented Aug 10, 2013

serhiy-storchaka commented Aug 10, 2013

tim-one commented Aug 10, 2013

serhiy-storchaka commented Aug 11, 2013

mrabarnett mannequin commented Aug 11, 2013

serhiy-storchaka commented Aug 14, 2013

python-dev mannequin commented Aug 19, 2013

re.error: nothing to repeat #62847

re.error: nothing to repeat #62847

Comments

serhiy-storchaka commented Aug 3, 2013

serhiy-storchaka commented Aug 3, 2013

python-dev mannequin commented Aug 3, 2013

python-dev mannequin commented Aug 4, 2013

elibendersky mannequin commented Aug 4, 2013

serhiy-storchaka commented Aug 4, 2013

elibendersky mannequin commented Aug 4, 2013

tim-one commented Aug 4, 2013

serhiy-storchaka commented Aug 4, 2013

tim-one commented Aug 4, 2013

serhiy-storchaka commented Aug 4, 2013

tim-one commented Aug 4, 2013

serhiy-storchaka commented Aug 4, 2013

tim-one commented Aug 4, 2013

mrabarnett mannequin commented Aug 4, 2013

tim-one commented Aug 4, 2013

mrabarnett mannequin commented Aug 4, 2013

tim-one commented Aug 4, 2013

serhiy-storchaka commented Aug 6, 2013

tim-one commented Aug 6, 2013

arigo mannequin commented Aug 10, 2013

serhiy-storchaka commented Aug 10, 2013

tim-one commented Aug 10, 2013

serhiy-storchaka commented Aug 10, 2013

tim-one commented Aug 10, 2013

serhiy-storchaka commented Aug 11, 2013

mrabarnett mannequin commented Aug 11, 2013

serhiy-storchaka commented Aug 14, 2013

python-dev mannequin commented Aug 19, 2013