[Python-checkins] cpython: Issue #24426: Fast searching optimization in regular expressions now works

Sun Jun 21 13:07:18 CEST 2015

https://hg.python.org/cpython/rev/7e46a503dd16
changeset: 96622:7e46a503dd16
user: Serhiy Storchaka <storchaka at gmail.com>
date: Sun Jun 21 14:06:55 2015 +0300
summary:
 Issue #24426: Fast searching optimization in regular expressions now works
for patterns that starts with capturing groups. Fast searching optimization
now can't be disabled at compile time.
files:
 Lib/sre_compile.py | 117 +++++++++++++++++++-------------
 Misc/NEWS | 4 +
 Modules/_sre.c | 3 -
 Modules/sre_lib.h | 53 +++++++-------
 4 files changed, 99 insertions(+), 78 deletions(-)

diff --git a/Lib/sre_compile.py b/Lib/sre_compile.py
--- a/Lib/sre_compile.py
+++ b/Lib/sre_compile.py
@@ -409,57 +409,39 @@
 table[i] = idx + 1
 return table
 
-def _compile_info(code, pattern, flags):
- # internal: compile an info block. in the current version,
- # this contains min/max pattern width, and an optional literal
- # prefix or a character map
- lo, hi = pattern.getwidth()
- if hi > MAXCODE:
- hi = MAXCODE
- if lo == 0:
- code.extend([INFO, 4, 0, lo, hi])
- return
- # look for a literal prefix
+def _get_literal_prefix(pattern):
+ # look for literal prefix
 prefix = []
 prefixappend = prefix.append
- prefix_skip = 0
+ prefix_skip = None
+ got_all = True
+ for op, av in pattern.data:
+ if op is LITERAL:
+ prefixappend(av)
+ elif op is SUBPATTERN:
+ prefix1, prefix_skip1, got_all = _get_literal_prefix(av[1])
+ if prefix_skip is None:
+ if av[0] is not None:
+ prefix_skip = len(prefix)
+ elif prefix_skip1 is not None:
+ prefix_skip = len(prefix) + prefix_skip1
+ prefix.extend(prefix1)
+ if not got_all:
+ break
+ else:
+ got_all = False
+ break
+ return prefix, prefix_skip, got_all
+
+def _get_charset_prefix(pattern):
 charset = [] # not used
 charsetappend = charset.append
- if not (flags & SRE_FLAG_IGNORECASE):
- # look for literal prefix
- for op, av in pattern.data:
+ if pattern.data:
+ op, av = pattern.data[0]
+ if op is SUBPATTERN and av[1]:
+ op, av = av[1][0]
 if op is LITERAL:
- if len(prefix) == prefix_skip:
- prefix_skip = prefix_skip + 1
- prefixappend(av)
- elif op is SUBPATTERN and len(av[1]) == 1:
- op, av = av[1][0]
- if op is LITERAL:
- prefixappend(av)
- else:
- break
- else:
- break
- # if no prefix, look for charset prefix
- if not prefix and pattern.data:
- op, av = pattern.data[0]
- if op is SUBPATTERN and av[1]:
- op, av = av[1][0]
- if op is LITERAL:
- charsetappend((op, av))
- elif op is BRANCH:
- c = []
- cappend = c.append
- for p in av[1]:
- if not p:
- break
- op, av = p[0]
- if op is LITERAL:
- cappend((op, av))
- else:
- break
- else:
- charset = c
+ charsetappend((op, av))
 elif op is BRANCH:
 c = []
 cappend = c.append
@@ -473,8 +455,43 @@
 break
 else:
 charset = c
- elif op is IN:
- charset = av
+ elif op is BRANCH:
+ c = []
+ cappend = c.append
+ for p in av[1]:
+ if not p:
+ break
+ op, av = p[0]
+ if op is LITERAL:
+ cappend((op, av))
+ else:
+ break
+ else:
+ charset = c
+ elif op is IN:
+ charset = av
+ return charset
+
+def _compile_info(code, pattern, flags):
+ # internal: compile an info block. in the current version,
+ # this contains min/max pattern width, and an optional literal
+ # prefix or a character map
+ lo, hi = pattern.getwidth()
+ if hi > MAXCODE:
+ hi = MAXCODE
+ if lo == 0:
+ code.extend([INFO, 4, 0, lo, hi])
+ return
+ # look for a literal prefix
+ prefix = []
+ prefix_skip = 0
+ charset = [] # not used
+ if not (flags & SRE_FLAG_IGNORECASE):
+ # look for literal prefix
+ prefix, prefix_skip, got_all = _get_literal_prefix(pattern)
+ # if no prefix, look for charset prefix
+ if not prefix:
+ charset = _get_charset_prefix(pattern)
 ## if prefix:
 ## print("*** PREFIX", prefix, prefix_skip)
 ## if charset:
@@ -487,7 +504,7 @@
 mask = 0
 if prefix:
 mask = SRE_INFO_PREFIX
- if len(prefix) == prefix_skip == len(pattern.data):
+ if prefix_skip is None and got_all:
 mask = mask | SRE_INFO_LITERAL
 elif charset:
 mask = mask | SRE_INFO_CHARSET
@@ -502,6 +519,8 @@
 # add literal prefix
 if prefix:
 emit(len(prefix)) # length
+ if prefix_skip is None:
+ prefix_skip = len(prefix)
 emit(prefix_skip) # skip
 code.extend(prefix)
 # generate overlap table
diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -13,6 +13,10 @@
 Library
 -------
 
+- Issue #24426: Fast searching optimization in regular expressions now works
+ for patterns that starts with capturing groups. Fast searching optimization
+ now can't be disabled at compile time.
+
 Documentation
 -------------
 
diff --git a/Modules/_sre.c b/Modules/_sre.c
--- a/Modules/_sre.c
+++ b/Modules/_sre.c
@@ -62,9 +62,6 @@
 /* -------------------------------------------------------------------- */
 /* optional features */
 
-/* enables fast searching */
-#define USE_FAST_SEARCH
-
 /* enables copy/deepcopy handling (work in progress) */
 #undef USE_BUILTIN_COPY
 
diff --git a/Modules/sre_lib.h b/Modules/sre_lib.h
--- a/Modules/sre_lib.h
+++ b/Modules/sre_lib.h
@@ -1248,7 +1248,32 @@
 prefix, prefix_len, prefix_skip));
 TRACE(("charset = %p\n", charset));
 
-#if defined(USE_FAST_SEARCH)
+ if (prefix_len == 1) {
+ /* pattern starts with a literal character */
+ SRE_CHAR c = (SRE_CHAR) prefix[0];
+#if SIZEOF_SRE_CHAR < 4
+ if ((SRE_CODE) c != prefix[0])
+ return 0; /* literal can't match: doesn't fit in char width */
+#endif
+ end = (SRE_CHAR *)state->end;
+ while (ptr < end) {
+ while (*ptr != c) {
+ if (++ptr >= end)
+ return 0;
+ }
+ TRACE(("|%p|%p|SEARCH LITERAL\n", pattern, ptr));
+ state->start = ptr;
+ state->ptr = ptr + prefix_skip;
+ if (flags & SRE_INFO_LITERAL)
+ return 1; /* we got all of it */
+ status = SRE(match)(state, pattern + 2*prefix_skip, 0);
+ if (status != 0)
+ return status;
+ ++ptr;
+ }
+ return 0;
+ }
+
 if (prefix_len > 1) {
 /* pattern starts with a known prefix. use the overlap
 table to skip forward as fast as we possibly can */
@@ -1297,32 +1322,8 @@
 }
 return 0;
 }
-#endif
 
- if (pattern[0] == SRE_OP_LITERAL) {
- /* pattern starts with a literal character. this is used
- for short prefixes, and if fast search is disabled */
- SRE_CHAR c = (SRE_CHAR) pattern[1];
-#if SIZEOF_SRE_CHAR < 4
- if ((SRE_CODE) c != pattern[1])
- return 0; /* literal can't match: doesn't fit in char width */
-#endif
- end = (SRE_CHAR *)state->end;
- while (ptr < end) {
- while (*ptr != c) {
- if (++ptr >= end)
- return 0;
- }
- TRACE(("|%p|%p|SEARCH LITERAL\n", pattern, ptr));
- state->start = ptr;
- state->ptr = ++ptr;
- if (flags & SRE_INFO_LITERAL)
- return 1; /* we got all of it */
- status = SRE(match)(state, pattern + 2, 0);
- if (status != 0)
- break;
- }
- } else if (charset) {
+ if (charset) {
 /* pattern starts with a character from a known set */
 end = (SRE_CHAR *)state->end;
 for (;;) {
-- 
Repository URL: https://hg.python.org/cpython
