From fa25a7d51fdc4c21ac569d9f62825e337a7a6b4a Mon Sep 17 00:00:00 2001 From: Fredrik Lundh Date: Sun, 14 Jan 2001 23:55:55 +0000 Subject: -- don't use recursion for unbounded non-greedy repeat (bugs #115903, #115696) This is based on a patch by Darrel Gallion. I'm not 100% sure about this fix, but I haven't managed to come up with any test case it cannot handle... --- Lib/test/test_sre.py | 2 +- Modules/_sre.c | 15 +++++++++++++-- 2 files changed, 14 insertions(+), 3 deletions(-) diff --git a/Lib/test/test_sre.py b/Lib/test/test_sre.py index 9c01c66..5d19d40 100644 --- a/Lib/test/test_sre.py +++ b/Lib/test/test_sre.py @@ -248,7 +248,7 @@ test(r"""sre.match(r'(x)*', 50000*'x').span()""", test(r"""sre.match(r'(x)*y', 50000*'x'+'y').span()""", (0, 50001), RuntimeError) test(r"""sre.match(r'(x)*?y', 50000*'x'+'y').span()""", - (0, 50001), RuntimeError) + (0, 50001)) # this works in 2.1 from re_tests import * diff --git a/Modules/_sre.c b/Modules/_sre.c index 28ec61c..b040d87 100644 --- a/Modules/_sre.c +++ b/Modules/_sre.c @@ -24,6 +24,7 @@ * 2000-10-24 fl really fixed assert_not; reset groups in findall * 2000-12-21 fl fixed memory leak in groupdict * 2001-01-02 fl properly reset pointer after failed assertion in MIN_UNTIL + * 2001-01-15 fl don't use recursion for unbounded MIN_UTIL * * Copyright (c) 1997-2001 by Secret Labs AB. All rights reserved. * @@ -38,7 +39,7 @@ #ifndef SRE_RECURSIVE -char copyright[] = " SRE 0.9.9 Copyright (c) 1997-2000 by Secret Labs AB "; +char copyright[] = " SRE 0.9.9 Copyright (c) 1997-2001 by Secret Labs AB "; #include "Python.h" @@ -1012,11 +1013,21 @@ SRE_MATCH(SRE_STATE* state, SRE_CODE* pattern, int level) /* see if the tail matches */ state->repeat = rp->prev; - i = SRE_MATCH(state, pattern, level + 1); + if (rp->pattern[2] == 65535) { + /* unbounded repeat */ + for (;;) { + i = SRE_MATCH(state, pattern, level + 1); + if (i || ptr >= end) + break; + state->ptr = ++ptr; + } + } else + i = SRE_MATCH(state, pattern, level + 1); if (i) { /* free(rp); */ return i; } + state->ptr = ptr; state->repeat = rp; -- cgit v0.12