[Python-Dev] Re: sre vs gcc (was: New re failures on Windows)

Gary Herron gherron@islandtraining.com
Tue, 22 Apr 2003 08:49:42 -0700

On Tuesday 22 April 2003 01:27 am, Andrew MacIntyre wrote:
> [redirected to people apparently working on SRE]
> On Mon, 21 Apr 2003, Tim Peters wrote:
> > Narrowing it down to the specific C code that's at fault is still the
> > best hope.  There are two reasons for that:
> >
> > 1. It's very easy to write ill-defined code in C, and for all we know
> >    now some part of _sre is depending on undefined, or implementation
> >    defined (but apparently likely), behavior.
> >
> > 2. If that's not the problem, optimization bugs are usually easy to
> >    sidestep via minor code changes.  You have to know which code is
> >    getting screwed first, though.
> Seeing that Gustavo had checked in some changes to _sre.c on Sunday, I CVS
> up'ed and now find that a gcc 2.95.4 build survives test_sre with -O3.
> A gcc 3.2.2 build still gets a bus error with either -O3 or -O2.
> The actual test case from test_sre that fails is:
> ---8<---8<---
> # non-simple '*?' still recurses and hits the recursion limit
> test(r"""sre.search('(a|b)*?c', 10000*'ab'+'cd').end(0)""", None,
> RuntimeError) ---8<---8<---
> For the moment, the FreeBSD 5.x (ie gcc 3.2.x) element of my configure.in
> patch (SF #725024) is still valid.

Ah.  Good clue!  Here's a very likely fix to that problem.  Around
line 3102 of _sre.c find the line that sets USE_RECURSION_LIMIT.
Depending on you platform it will be set to either 10000 or 7500.  As
a test, lower that value to 1000 or even 100.  If all the tests pass,
then we know the culprit.

The sre code uses that value to prevent run-away recursion from
overflowing the stack.  It's value must be large enough to allow for
*reasonable* levels of recursion, but small enough to catch a run-away
recursion before it actually overflows the stack.  On at least one
class of machines, a value of 10000 was determined to be too high
(i.e., the stack overflowed before that many levels of recursion were
hit), and so the limit for them was lowered to 7500.  Perhaps such is
needed for your platform.

You have a lot of leeway here in your tests.  None of the tests in
test_sre recurse more than 100 levels except for that one test which
is expressly designed to blow past any limit, thereby testing that
excessive recursion caught correctly.  (And on your system, it is not
being caught correctly, perhaps because the stack is overflowing
before the USE_RECURSION_LIMIT is hit.)

Let me know the results of the test please.

Thank you,
Gary Herron