Changes by Serhiy Storchaka storch...@gmail.com:
--
resolution: - fixed
stage: commit review - committed/rejected
status: open - closed
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue18647
Roundup Robot added the comment:
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
Changes by Serhiy Storchaka storch...@gmail.com:
--
stage: - commit review
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue18647
___
___
Serhiy Storchaka added the comment:
So what now? Just remove unneeded check?
Related issues: issue1633953, issue2537.
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue18647
___
Serhiy Storchaka added the comment:
And not to me. This check forbids some possible legal regexps and doesn't
prevent from shooting in the leg.
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue18647
Matthew Barnett added the comment:
I think you're probably right.
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue18647
___
___
Python-bugs-list
Armin Rigo added the comment:
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
Serhiy Storchaka added the comment:
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,
Tim Peters added the comment:
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.
Serhiy Storchaka added the comment:
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
Tim Peters added the comment:
So does anyone believe this check serves a useful purpose _now_? Doesn't seem
so to me.
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue18647
___
Serhiy Storchaka added the comment:
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 Peters added the comment:
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
Roundup Robot added the comment:
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
--
___
Python tracker
Eli Bendersky added the comment:
Would it not be better to temporarily-fix the test rather than the code?
--
nosy: +eli.bendersky
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue18647
___
Serhiy Storchaka added the comment:
All doctests affected.
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue18647
___
___
Python-bugs-list mailing
Eli Bendersky added the comment:
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
Tim Peters added the comment:
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
Serhiy Storchaka added the comment:
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
Tim Peters added the comment:
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
Serhiy Storchaka added the comment:
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
Tim Peters added the comment:
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
Serhiy Storchaka added the comment:
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
Tim Peters added the comment:
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
Matthew Barnett added the comment:
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
Tim Peters added the comment:
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
Matthew Barnett added the comment:
Python's current regex engine isn't so coded. That's the reason for the
up-front check.
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue18647
___
Tim Peters added the comment:
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
New submission from Serhiy Storchaka:
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
Roundup Robot added the comment:
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
Changes by Arfrever Frehtes Taifersar Arahesis arfrever@gmail.com:
--
nosy: +Arfrever
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue18647
___
Changes by Tim Peters tim.pet...@gmail.com:
--
nosy: +tim_one
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue18647
___
___
Python-bugs-list mailing
32 matches
Mail list logo
