diff options
Diffstat (limited to 'Lib')
| -rw-r--r-- | Lib/sre.py | 24 | ||||
| -rw-r--r-- | Lib/sre_compile.py | 256 | ||||
| -rw-r--r-- | Lib/sre_parse.py | 8 |
3 files changed, 168 insertions, 120 deletions
@@ -47,16 +47,16 @@ def search(pattern, string, flags=0): return _compile(pattern, flags).search(string) def sub(pattern, repl, string, count=0): - return _compile(pattern).sub(repl, string, count) + return _compile(pattern, 0).sub(repl, string, count) def subn(pattern, repl, string, count=0): - return _compile(pattern).subn(repl, string, count) + return _compile(pattern, 0).subn(repl, string, count) def split(pattern, string, maxsplit=0): - return _compile(pattern).split(string, maxsplit) + return _compile(pattern, 0).split(string, maxsplit) def findall(pattern, string, maxsplit=0): - return _compile(pattern).findall(string, maxsplit) + return _compile(pattern, 0).findall(string, maxsplit) def compile(pattern, flags=0): return _compile(pattern, flags) @@ -88,16 +88,14 @@ def _join(seq, sep): # internal: join into string having the same type as sep return string.join(seq, sep[:0]) -def _compile(pattern, flags=0): +def _compile(*key): # internal: compile pattern - tp = type(pattern) - if tp not in sre_compile.STRING_TYPES: + p = _cache.get(key) + if p is not None: + return p + pattern, flags = key + if type(pattern) not in sre_compile.STRING_TYPES: return pattern - key = (tp, pattern, flags) - try: - return _cache[key] - except KeyError: - pass try: p = sre_compile.compile(pattern, flags) except error, v: @@ -168,7 +166,7 @@ import copy_reg def _pickle(p): return _compile, (p.pattern, p.flags) -copy_reg.pickle(type(_compile("")), _pickle, _compile) +copy_reg.pickle(type(_compile("", 0)), _pickle, _compile) # -------------------------------------------------------------------- # experimental stuff (see python-dev discussions for details) diff --git a/Lib/sre_compile.py b/Lib/sre_compile.py index abd619e..97a57e2 100644 --- a/Lib/sre_compile.py +++ b/Lib/sre_compile.py @@ -14,72 +14,6 @@ from sre_constants import * MAXCODE = 65535 -def _charset(charset, fixup=None): - # internal: optimize character set - if not fixup: - fixup = lambda x: x - out = [] - charmap = [0]*256 - try: - for op, av in charset: - if op is NEGATE: - out.append((op, av)) - elif op is LITERAL: - charmap[fixup(av)] = 1 - elif op is RANGE: - for i in range(fixup(av[0]), fixup(av[1])+1): - charmap[i] = 1 - elif op is CATEGORY: - # FIXME: could append to charmap tail - return charset # cannot compress - except IndexError: - # unicode - return charset - # compress character map - i = p = n = 0 - runs = [] - for c in charmap: - if c: - if n == 0: - p = i - n = n + 1 - elif n: - runs.append((p, n)) - n = 0 - i = i + 1 - if n: - runs.append((p, n)) - if len(runs) <= 2: - # use literal/range - for p, n in runs: - if n == 1: - out.append((LITERAL, p)) - else: - out.append((RANGE, (p, p+n-1))) - if len(out) < len(charset): - return out - else: - # use bitmap - data = [] - m = 1; v = 0 - for c in charmap: - if c: - v = v + m - m = m << 1 - if m > MAXCODE: - data.append(v) - m = 1; v = 0 - out.append((CHARSET, data)) - return out - return charset - -def _simple(av): - # check if av is a "simple" operator - lo, hi = av[2].getwidth() - if lo == 0: - raise error, "nothing to repeat" - return lo == hi == 1 and av[2][0][0] != SUBPATTERN - def _compile(code, pattern, flags): # internal: compile a (sub)pattern emit = code.append @@ -99,27 +33,7 @@ def _compile(code, pattern, flags): emit(OPCODES[op]) fixup = lambda x: x skip = len(code); emit(0) - for op, av in _charset(av, fixup): - emit(OPCODES[op]) - if op is NEGATE: - pass - elif op is LITERAL: - emit(fixup(av)) - elif op is RANGE: - emit(fixup(av[0])) - emit(fixup(av[1])) - elif op is CHARSET: - code.extend(av) - elif op is CATEGORY: - if flags & SRE_FLAG_LOCALE: - emit(CHCODES[CH_LOCALE[av]]) - elif flags & SRE_FLAG_UNICODE: - emit(CHCODES[CH_UNICODE[av]]) - else: - emit(CHCODES[av]) - else: - raise error, "internal: unsupported set operator" - emit(OPCODES[FAILURE]) + _compile_charset(av, flags, code, fixup) code[skip] = len(code) - skip elif op is ANY: if flags & SRE_FLAG_DOTALL: @@ -159,6 +73,7 @@ def _compile(code, pattern, flags): if av[0]: emit(OPCODES[MARK]) emit((av[0]-1)*2) + # _compile_info(code, av[1], flags) _compile(code, av[1], flags) if av[0]: emit(OPCODES[MARK]) @@ -195,6 +110,7 @@ def _compile(code, pattern, flags): tail = [] for av in av[1]: skip = len(code); emit(0) + # _compile_info(code, av, flags) _compile(code, av, flags) emit(OPCODES[JUMP]) tail.append(len(code)); emit(0) @@ -219,6 +135,97 @@ def _compile(code, pattern, flags): else: raise ValueError, ("unsupported operand type", op) +def _compile_charset(charset, flags, code, fixup=None): + # compile charset subprogram + emit = code.append + if not fixup: + fixup = lambda x: x + for op, av in _optimize_charset(charset, fixup): + emit(OPCODES[op]) + if op is NEGATE: + pass + elif op is LITERAL: + emit(fixup(av)) + elif op is RANGE: + emit(fixup(av[0])) + emit(fixup(av[1])) + elif op is CHARSET: + code.extend(av) + elif op is CATEGORY: + if flags & SRE_FLAG_LOCALE: + emit(CHCODES[CH_LOCALE[av]]) + elif flags & SRE_FLAG_UNICODE: + emit(CHCODES[CH_UNICODE[av]]) + else: + emit(CHCODES[av]) + else: + raise error, "internal: unsupported set operator" + emit(OPCODES[FAILURE]) + +def _optimize_charset(charset, fixup): + # internal: optimize character set + out = [] + charmap = [0]*256 + try: + for op, av in charset: + if op is NEGATE: + out.append((op, av)) + elif op is LITERAL: + charmap[fixup(av)] = 1 + elif op is RANGE: + for i in range(fixup(av[0]), fixup(av[1])+1): + charmap[i] = 1 + elif op is CATEGORY: + # FIXME: could append to charmap tail + return charset # cannot compress + except IndexError: + # character set contains unicode characters + return charset + # compress character map + i = p = n = 0 + runs = [] + for c in charmap: + if c: + if n == 0: + p = i + n = n + 1 + elif n: + runs.append((p, n)) + n = 0 + i = i + 1 + if n: + runs.append((p, n)) + if len(runs) <= 2: + # use literal/range + for p, n in runs: + if n == 1: + out.append((LITERAL, p)) + else: + out.append((RANGE, (p, p+n-1))) + if len(out) < len(charset): + return out + else: + # use bitmap + data = [] + m = 1; v = 0 + for c in charmap: + if c: + v = v + m + m = m << 1 + if m > MAXCODE: + data.append(v) + m = 1; v = 0 + out.append((CHARSET, data)) + return out + return charset + +def _simple(av): + # check if av is a "simple" operator + lo, hi = av[2].getwidth() + if lo == 0: + raise error, "nothing to repeat" + return lo == hi == 1 and av[2][0][0] != SUBPATTERN + 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 @@ -228,13 +235,60 @@ def _compile_info(code, pattern, flags): return # not worth it # look for a literal prefix prefix = [] + prefix_skip = 0 charset = [] # not used if not (flags & SRE_FLAG_IGNORECASE): + # look for literal prefix for op, av in pattern.data: if op is LITERAL: + if len(prefix) == prefix_skip: + prefix_skip = prefix_skip + 1 prefix.append(av) + elif op is SUBPATTERN and len(av[1]) == 1: + op, av = av[1][0] + if op is LITERAL: + prefix.append(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: + charset.append((op, av)) + elif op is BRANCH: + c = [] + for p in av[1]: + if not p: + break + op, av = p[0] + if op is LITERAL: + c.append((op, av)) + else: + break + else: + charset = c + elif op is BRANCH: + c = [] + for p in av[1]: + if not p: + break + op, av = p[0] + if op is LITERAL: + c.append((op, av)) + else: + break + else: + charset = c + elif op is IN: + charset = av +## if prefix: +## print "*** PREFIX", prefix, prefix_skip +## if charset: +## print "*** CHARSET", charset # add an info block emit = code.append emit(OPCODES[INFO]) @@ -243,7 +297,7 @@ def _compile_info(code, pattern, flags): mask = 0 if prefix: mask = SRE_INFO_PREFIX - if len(prefix) == len(pattern.data): + if len(prefix) == prefix_skip == len(pattern.data): mask = mask + SRE_INFO_LITERAL elif charset: mask = mask + SRE_INFO_CHARSET @@ -260,22 +314,18 @@ def _compile_info(code, pattern, flags): emit(0) # add literal prefix if prefix: - emit(len(prefix)) - if prefix: - code.extend(prefix) - # generate overlap table - table = [-1] + ([0]*len(prefix)) - for i in range(len(prefix)): - table[i+1] = table[i]+1 - while table[i+1] > 0 and prefix[i] != prefix[table[i+1]-1]: - table[i+1] = table[table[i+1]-1]+1 - code.extend(table[1:]) # don't store first entry + emit(len(prefix)) # length + emit(prefix_skip) # skip + code.extend(prefix) + # generate overlap table + table = [-1] + ([0]*len(prefix)) + for i in range(len(prefix)): + table[i+1] = table[i]+1 + while table[i+1] > 0 and prefix[i] != prefix[table[i+1]-1]: + table[i+1] = table[table[i+1]-1]+1 + code.extend(table[1:]) # don't store first entry elif charset: - # FIXME: use charset optimizer! - for char in charset: - emit(OPCODES[LITERAL]) - emit(char) - emit(OPCODES[FAILURE]) + _compile_charset(charset, 0, code) code[skip] = len(code) - skip STRING_TYPES = [type("")] diff --git a/Lib/sre_parse.py b/Lib/sre_parse.py index 1c1d0d5..16e49b6 100644 --- a/Lib/sre_parse.py +++ b/Lib/sre_parse.py @@ -10,8 +10,6 @@ import string, sys -import _sre - from sre_constants import * MAXREPEAT = 65535 @@ -232,6 +230,7 @@ def _class_escape(source, escape): return code try: if escape[1:2] == "x": + # FIXME: in 2.0, \xNN must have exactly two digits while source.next in HEXDIGITS: escape = escape + source.get() escape = escape[2:] @@ -556,12 +555,13 @@ def _parse(source, state): return subpattern -def parse(str, flags=0): +def parse(str, flags=0, pattern=None): # parse 're' pattern into list of (opcode, argument) tuples source = Tokenizer(str) - pattern = Pattern() + if pattern is None: + pattern = Pattern() pattern.flags = flags p = _parse_sub(source, pattern, 0) |