Index: Lib/sre_compile.py =================================================================== RCS file: /cvsroot/python/python/dist/src/Lib/sre_compile.py,v retrieving revision 1.45 diff -c -r1.45 sre_compile.py *** Lib/sre_compile.py 24 Feb 2003 01:18:35 -0000 1.45 --- Lib/sre_compile.py 12 Apr 2003 08:52:45 -0000 *************** *** 55,62 **** _compile(code, av[2], flags) emit(OPCODES[SUCCESS]) code[skip] = len(code) - skip ! elif _simple(av) and op == MAX_REPEAT: ! emit(OPCODES[REPEAT_ONE]) skip = len(code); emit(0) emit(av[0]) emit(av[1]) --- 55,65 ---- _compile(code, av[2], flags) emit(OPCODES[SUCCESS]) code[skip] = len(code) - skip ! elif _simple(av) and op != REPEAT: ! if op == MAX_REPEAT: ! emit(OPCODES[REPEAT_ONE]) ! else: ! emit(OPCODES[MIN_REPEAT_ONE]) skip = len(code); emit(0) emit(av[0]) emit(av[1]) Index: Lib/sre_constants.py =================================================================== RCS file: /cvsroot/python/python/dist/src/Lib/sre_constants.py,v retrieving revision 1.30 diff -c -r1.30 sre_constants.py *** Lib/sre_constants.py 4 Sep 2001 19:10:20 -0000 1.30 --- Lib/sre_constants.py 12 Apr 2003 08:52:45 -0000 *************** *** 60,65 **** --- 60,66 ---- REPEAT = "repeat" REPEAT_ONE = "repeat_one" SUBPATTERN = "subpattern" + MIN_REPEAT_ONE = "min_repeat_one" # positions AT_BEGINNING = "at_beginning" *************** *** 120,126 **** RANGE, REPEAT, REPEAT_ONE, ! SUBPATTERN ] --- 121,128 ---- RANGE, REPEAT, REPEAT_ONE, ! SUBPATTERN, ! MIN_REPEAT_ONE ] Index: Lib/sre_parse.py =================================================================== RCS file: /cvsroot/python/python/dist/src/Lib/sre_parse.py,v retrieving revision 1.55 diff -c -r1.55 sre_parse.py *** Lib/sre_parse.py 2 Jun 2002 00:40:05 -0000 1.55 --- Lib/sre_parse.py 12 Apr 2003 08:52:45 -0000 *************** *** 419,425 **** set.append(code1) set.append((LITERAL, ord("-"))) break ! else: if this[0] == "\\": code2 = _class_escape(source, this) else: --- 419,425 ---- set.append(code1) set.append((LITERAL, ord("-"))) break ! elif this: if this[0] == "\\": code2 = _class_escape(source, this) else: *************** *** 431,436 **** --- 431,438 ---- if hi < lo: raise error, "bad character range" set.append((RANGE, (lo, hi))) + else: + raise error, "unexpected end of regular expression" else: if code1[0] is IN: code1 = code1[1][0] Index: Lib/test/test_sre.py =================================================================== RCS file: /cvsroot/python/python/dist/src/Lib/test/test_sre.py,v retrieving revision 1.38 diff -c -r1.38 test_sre.py *** Lib/test/test_sre.py 6 Nov 2002 14:06:52 -0000 1.38 --- Lib/test/test_sre.py 12 Apr 2003 08:52:47 -0000 *************** *** 83,88 **** --- 83,101 ---- test(r"""sre.match(r'(a)(b)?b','ab').lastindex""", 1) test(r"""sre.match(r'(?Pa)(?Pb)?b','ab').lastgroup""", 'a') + # bug 545855 -- This pattern failed to cause a compile error as it + # should, instead provoking an error latter during matching. + test(r"""sre.compile('foo[a-')""", None, sre.error) + + # bugs 418626 at al. -- Testing Greg Chapman's addition of op code + # SRE_OP_MIN_REPEAT_ONE for eliminating recursion on simple uses of + # pattern '*?' on a long string. + test(r"""sre.match('.*?c', 10000*'ab'+'cd').end(0)""", 20001) + test(r"""sre.match('.*?cd', 5000*'ab'+'c'+5000*'ab'+'cde').end(0)""", 20003) + test(r"""sre.match('.*?cd', 20000*'abc'+'de').end(0)""", 60001) + # non-simple '*?' still recurses and hits the recursion limit + test(r"""sre.search('(a|b)*?c', 10000*'ab'+'cd').end(0)""", None, RuntimeError) + if verbose: print 'Running tests on sre.sub' Index: Modules/_sre.c =================================================================== RCS file: /cvsroot/python/python/dist/src/Modules/_sre.c,v retrieving revision 2.87 diff -c -r2.87 _sre.c *** Modules/_sre.c 22 Nov 2002 12:46:35 -0000 2.87 --- Modules/_sre.c 12 Apr 2003 08:52:49 -0000 *************** *** 993,998 **** --- 993,1058 ---- } return 0; + case SRE_OP_MIN_REPEAT_ONE: + /* match repeated sequence (minimizing regexp) */ + + /* this operator only works if the repeated item is + exactly one character wide, and we're not already + collecting backtracking points. for other cases, + use the MIN_REPEAT operator */ + + /* <1=min> <2=max> item tail */ + + TRACE(("|%p|%p|MIN_REPEAT_ONE %d %d\n", pattern, ptr, + pattern[1], pattern[2])); + + if (ptr + pattern[1] > end) + return 0; /* cannot match */ + + state->ptr = ptr; + + if (pattern[1] == 0) + count = 0; + else { + /* count using pattern min as the maximum */ + count = SRE_COUNT(state, pattern + 3, pattern[1], level + 1); + + if (count < 0) + return count; /* exception */ + if (count < (int) pattern[1]) + return 0; /* did not match minimum number of times */ + ptr += count; /* advance past minimum matches of repeat */ + } + + if (pattern[pattern[0]] == SRE_OP_SUCCESS) { + /* tail is empty. we're finished */ + state->ptr = ptr; + return 1; + + } else { + /* general case */ + int matchmax = ((int)pattern[2] == 65535); + int c; + lastmark = state->lastmark; + while (matchmax || count <= (int) pattern[2]) { + state->ptr = ptr; + i = SRE_MATCH(state, pattern + pattern[0], level + 1); + if (i) + return i; + state->ptr = ptr; + c = SRE_COUNT(state, pattern+3, 1, level+1); + if (c < 0) + return c; + if (c == 0) + break; + assert(c == 1); + ptr++; + count++; + } + lastmark_restore(state, lastmark); + } + return 0; + case SRE_OP_REPEAT: /* create repeat context. all the hard work is done by the UNTIL operator (MAX_UNTIL, MIN_UNTIL) */ Index: Modules/sre_constants.h =================================================================== RCS file: /cvsroot/python/python/dist/src/Modules/sre_constants.h,v retrieving revision 2.13 diff -c -r2.13 sre_constants.h *** Modules/sre_constants.h 2 Jul 2001 16:58:38 -0000 2.13 --- Modules/sre_constants.h 12 Apr 2003 08:52:49 -0000 *************** *** 42,47 **** --- 42,48 ---- #define SRE_OP_REPEAT 27 #define SRE_OP_REPEAT_ONE 28 #define SRE_OP_SUBPATTERN 29 + #define SRE_OP_MIN_REPEAT_ONE 30 #define SRE_AT_BEGINNING 0 #define SRE_AT_BEGINNING_LINE 1 #define SRE_AT_BEGINNING_STRING 2