diff options
Diffstat (limited to 'Lib/sre_compile.py')
| -rw-r--r-- | Lib/sre_compile.py | 407 |
1 files changed, 242 insertions, 165 deletions
diff --git a/Lib/sre_compile.py b/Lib/sre_compile.py index b984a54..550ea15 100644 --- a/Lib/sre_compile.py +++ b/Lib/sre_compile.py @@ -10,9 +10,10 @@ """Internal support module for sre""" -import _sre, sys +import _sre import sre_parse from sre_constants import * +from _sre import MAXREPEAT assert _sre.MAGIC == MAGIC, "SRE module mismatch" @@ -21,14 +22,51 @@ if _sre.CODESIZE == 2: else: MAXCODE = 0xFFFFFFFF -def _identityfunction(x): - return x - _LITERAL_CODES = set([LITERAL, NOT_LITERAL]) _REPEATING_CODES = set([REPEAT, MIN_REPEAT, MAX_REPEAT]) _SUCCESS_CODES = set([SUCCESS, FAILURE]) _ASSERT_CODES = set([ASSERT, ASSERT_NOT]) +# Sets of lowercase characters which have the same uppercase. +_equivalences = ( + # LATIN SMALL LETTER I, LATIN SMALL LETTER DOTLESS I + (0x69, 0x131), # iı + # LATIN SMALL LETTER S, LATIN SMALL LETTER LONG S + (0x73, 0x17f), # sſ + # MICRO SIGN, GREEK SMALL LETTER MU + (0xb5, 0x3bc), # µμ + # COMBINING GREEK YPOGEGRAMMENI, GREEK SMALL LETTER IOTA, GREEK PROSGEGRAMMENI + (0x345, 0x3b9, 0x1fbe), # \u0345ιι + # GREEK SMALL LETTER IOTA WITH DIALYTIKA AND TONOS, GREEK SMALL LETTER IOTA WITH DIALYTIKA AND OXIA + (0x390, 0x1fd3), # ΐΐ + # GREEK SMALL LETTER UPSILON WITH DIALYTIKA AND TONOS, GREEK SMALL LETTER UPSILON WITH DIALYTIKA AND OXIA + (0x3b0, 0x1fe3), # ΰΰ + # GREEK SMALL LETTER BETA, GREEK BETA SYMBOL + (0x3b2, 0x3d0), # βϐ + # GREEK SMALL LETTER EPSILON, GREEK LUNATE EPSILON SYMBOL + (0x3b5, 0x3f5), # εϵ + # GREEK SMALL LETTER THETA, GREEK THETA SYMBOL + (0x3b8, 0x3d1), # θϑ + # GREEK SMALL LETTER KAPPA, GREEK KAPPA SYMBOL + (0x3ba, 0x3f0), # κϰ + # GREEK SMALL LETTER PI, GREEK PI SYMBOL + (0x3c0, 0x3d6), # πϖ + # GREEK SMALL LETTER RHO, GREEK RHO SYMBOL + (0x3c1, 0x3f1), # ρϱ + # GREEK SMALL LETTER FINAL SIGMA, GREEK SMALL LETTER SIGMA + (0x3c2, 0x3c3), # ςσ + # GREEK SMALL LETTER PHI, GREEK PHI SYMBOL + (0x3c6, 0x3d5), # φϕ + # LATIN SMALL LETTER S WITH DOT ABOVE, LATIN SMALL LETTER LONG S WITH DOT ABOVE + (0x1e61, 0x1e9b), # ṡẛ + # LATIN SMALL LIGATURE LONG S T, LATIN SMALL LIGATURE ST + (0xfb05, 0xfb06), # ſtst +) + +# Maps the lowercase code to lowercase codes which have the same uppercase. +_ignorecase_fixes = {i: tuple(j for j in t if i != j) + for t in _equivalences for i in t} + def _compile(code, pattern, flags): # internal: compile a (sub)pattern emit = code.append @@ -37,11 +75,29 @@ def _compile(code, pattern, flags): REPEATING_CODES = _REPEATING_CODES SUCCESS_CODES = _SUCCESS_CODES ASSERT_CODES = _ASSERT_CODES + if (flags & SRE_FLAG_IGNORECASE and + not (flags & SRE_FLAG_LOCALE) and + flags & SRE_FLAG_UNICODE): + fixes = _ignorecase_fixes + else: + fixes = None for op, av in pattern: if op in LITERAL_CODES: if flags & SRE_FLAG_IGNORECASE: - emit(OPCODES[OP_IGNORE[op]]) - emit(_sre.getlower(av, flags)) + lo = _sre.getlower(av, flags) + if fixes and lo in fixes: + emit(OPCODES[IN_IGNORE]) + skip = _len(code); emit(0) + if op is NOT_LITERAL: + emit(OPCODES[NEGATE]) + for k in (lo,) + fixes[lo]: + emit(OPCODES[LITERAL]) + emit(k) + emit(OPCODES[FAILURE]) + code[skip] = _len(code) - skip + else: + emit(OPCODES[OP_IGNORE[op]]) + emit(lo) else: emit(OPCODES[op]) emit(av) @@ -52,9 +108,9 @@ def _compile(code, pattern, flags): return _sre.getlower(literal, flags) else: emit(OPCODES[op]) - fixup = _identityfunction + fixup = None skip = _len(code); emit(0) - _compile_charset(av, flags, code, fixup) + _compile_charset(av, flags, code, fixup, fixes) code[skip] = _len(code) - skip elif op is ANY: if flags & SRE_FLAG_DOTALL: @@ -64,13 +120,6 @@ def _compile(code, pattern, flags): elif op in REPEATING_CODES: if flags & SRE_FLAG_TEMPLATE: raise error("internal: unsupported template operator") - emit(OPCODES[REPEAT]) - skip = _len(code); emit(0) - emit(av[0]) - emit(av[1]) - _compile(code, av[2], flags) - emit(OPCODES[SUCCESS]) - code[skip] = _len(code) - skip elif _simple(av) and op is not REPEAT: if op is MAX_REPEAT: emit(OPCODES[REPEAT_ONE]) @@ -175,20 +224,19 @@ def _compile(code, pattern, flags): else: raise ValueError("unsupported operand type", op) -def _compile_charset(charset, flags, code, fixup=None): +def _compile_charset(charset, flags, code, fixup=None, fixes=None): # compile charset subprogram emit = code.append - if fixup is None: - fixup = _identityfunction - for op, av in _optimize_charset(charset, fixup): + for op, av in _optimize_charset(charset, fixup, fixes, + flags & SRE_FLAG_UNICODE): emit(OPCODES[op]) if op is NEGATE: pass elif op is LITERAL: - emit(fixup(av)) + emit(av) elif op is RANGE: - emit(fixup(av[0])) - emit(fixup(av[1])) + emit(av[0]) + emit(av[1]) elif op is CHARSET: code.extend(av) elif op is BIGCHARSET: @@ -204,161 +252,195 @@ def _compile_charset(charset, flags, code, fixup=None): raise error("internal: unsupported set operator") emit(OPCODES[FAILURE]) -def _optimize_charset(charset, fixup): +def _optimize_charset(charset, fixup, fixes, isunicode): # internal: optimize character set out = [] - outappend = out.append - charmap = [0]*256 - try: - for op, av in charset: - if op is NEGATE: - outappend((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: - # XXX: could append to charmap tail - return charset # cannot compress - except IndexError: - # character set contains unicode characters - return _optimize_unicode(charset, fixup) + tail = [] + charmap = bytearray(256) + for op, av in charset: + while True: + try: + if op is LITERAL: + if fixup: + i = fixup(av) + charmap[i] = 1 + if fixes and i in fixes: + for k in fixes[i]: + charmap[k] = 1 + else: + charmap[av] = 1 + elif op is RANGE: + r = range(av[0], av[1]+1) + if fixup: + r = map(fixup, r) + if fixup and fixes: + for i in r: + charmap[i] = 1 + if i in fixes: + for k in fixes[i]: + charmap[k] = 1 + else: + for i in r: + charmap[i] = 1 + elif op is NEGATE: + out.append((op, av)) + else: + tail.append((op, av)) + except IndexError: + if len(charmap) == 256: + # character set contains non-UCS1 character codes + charmap += b'\0' * 0xff00 + continue + # character set contains non-BMP character codes + if fixup and isunicode and op is RANGE: + lo, hi = av + ranges = [av] + # There are only two ranges of cased astral characters: + # 10400-1044F (Deseret) and 118A0-118DF (Warang Citi). + _fixup_range(max(0x10000, lo), min(0x11fff, hi), + ranges, fixup) + for lo, hi in ranges: + if lo == hi: + tail.append((LITERAL, hi)) + else: + tail.append((RANGE, (lo, hi))) + else: + tail.append((op, av)) + break + # compress character map - i = p = n = 0 runs = [] - runsappend = runs.append - for c in charmap: - if c: - if n == 0: - p = i - n = n + 1 - elif n: - runsappend((p, n)) - n = 0 - i = i + 1 - if n: - runsappend((p, n)) - if len(runs) <= 2: + q = 0 + while True: + p = charmap.find(1, q) + if p < 0: + break + if len(runs) >= 2: + runs = None + break + q = charmap.find(0, p) + if q < 0: + runs.append((p, len(charmap))) + break + runs.append((p, q)) + if runs is not None: # use literal/range - for p, n in runs: - if n == 1: - outappend((LITERAL, p)) + for p, q in runs: + if q - p == 1: + out.append((LITERAL, p)) else: - outappend((RANGE, (p, p+n-1))) - if len(out) < len(charset): + out.append((RANGE, (p, q - 1))) + out += tail + # if the case was changed or new representation is more compact + if fixup or len(out) < len(charset): return out - else: - # use bitmap + # else original character set is good enough + return charset + + # use bitmap + if len(charmap) == 256: data = _mk_bitmap(charmap) - outappend((CHARSET, data)) + out.append((CHARSET, data)) + out += tail return out - return charset -def _mk_bitmap(bits): - data = [] - dataappend = data.append - if _sre.CODESIZE == 2: - start = (1, 0) - else: - start = (1, 0) - m, v = start - for c in bits: - if c: - v = v + m - m = m + m - if m > MAXCODE: - dataappend(v) - m, v = start - return data - -# To represent a big charset, first a bitmap of all characters in the -# set is constructed. Then, this bitmap is sliced into chunks of 256 -# characters, duplicate chunks are eliminated, and each chunk is -# given a number. In the compiled expression, the charset is -# represented by a 32-bit word sequence, consisting of one word for -# the number of different chunks, a sequence of 256 bytes (64 words) -# of chunk numbers indexed by their original chunk position, and a -# sequence of 256-bit chunks (8 words each). - -# Compression is normally good: in a typical charset, large ranges of -# Unicode will be either completely excluded (e.g. if only cyrillic -# letters are to be matched), or completely included (e.g. if large -# subranges of Kanji match). These ranges will be represented by -# chunks of all one-bits or all zero-bits. - -# Matching can be also done efficiently: the more significant byte of -# the Unicode character is an index into the chunk number, and the -# less significant byte is a bit index in the chunk (just like the -# CHARSET matching). - -# The BIGCHARSET opcode still supports only subsets -# of the basic multilingual plane; an efficient representation -# for all of Unicode has not yet been developed. This means, -# in particular, that negated charsets cannot be represented as -# bigcharsets. - -def _optimize_unicode(charset, fixup): - try: - import array - except ImportError: - return charset - charmap = [0]*65536 - negate = 0 - try: - for op, av in charset: - if op is NEGATE: - negate = 1 - 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: - # XXX: could expand category - return charset # cannot compress - except IndexError: - # non-BMP characters; XXX now they should work - return charset - if negate: - if sys.maxunicode != 65535: - # XXX: negation does not work with big charsets - # XXX2: now they should work, but removing this will make the - # charmap 17 times bigger - return charset - for i in range(65536): - charmap[i] = not charmap[i] + # To represent a big charset, first a bitmap of all characters in the + # set is constructed. Then, this bitmap is sliced into chunks of 256 + # characters, duplicate chunks are eliminated, and each chunk is + # given a number. In the compiled expression, the charset is + # represented by a 32-bit word sequence, consisting of one word for + # the number of different chunks, a sequence of 256 bytes (64 words) + # of chunk numbers indexed by their original chunk position, and a + # sequence of 256-bit chunks (8 words each). + + # Compression is normally good: in a typical charset, large ranges of + # Unicode will be either completely excluded (e.g. if only cyrillic + # letters are to be matched), or completely included (e.g. if large + # subranges of Kanji match). These ranges will be represented by + # chunks of all one-bits or all zero-bits. + + # Matching can be also done efficiently: the more significant byte of + # the Unicode character is an index into the chunk number, and the + # less significant byte is a bit index in the chunk (just like the + # CHARSET matching). + + charmap = bytes(charmap) # should be hashable comps = {} - mapping = [0]*256 + mapping = bytearray(256) block = 0 - data = [] - for i in range(256): - chunk = tuple(charmap[i*256:(i+1)*256]) - new = comps.setdefault(chunk, block) - mapping[i] = new - if new == block: - block = block + 1 - data = data + _mk_bitmap(chunk) - header = [block] - if _sre.CODESIZE == 2: - code = 'H' - else: - code = 'I' - # Convert block indices to byte array of 256 bytes - mapping = array.array('B', mapping).tobytes() - # Convert byte array to word array - mapping = array.array(code, mapping) - assert mapping.itemsize == _sre.CODESIZE - assert len(mapping) * mapping.itemsize == 256 - header = header + mapping.tolist() - data[0:0] = header - return [(BIGCHARSET, data)] + data = bytearray() + for i in range(0, 65536, 256): + chunk = charmap[i: i + 256] + if chunk in comps: + mapping[i // 256] = comps[chunk] + else: + mapping[i // 256] = comps[chunk] = block + block += 1 + data += chunk + data = _mk_bitmap(data) + data[0:0] = [block] + _bytes_to_codes(mapping) + out.append((BIGCHARSET, data)) + out += tail + return out + +def _fixup_range(lo, hi, ranges, fixup): + for i in map(fixup, range(lo, hi+1)): + for k, (lo, hi) in enumerate(ranges): + if i < lo: + if l == lo - 1: + ranges[k] = (i, hi) + else: + ranges.insert(k, (i, i)) + break + elif i > hi: + if i == hi + 1: + ranges[k] = (lo, i) + break + else: + break + else: + ranges.append((i, i)) + +_CODEBITS = _sre.CODESIZE * 8 +_BITS_TRANS = b'0' + b'1' * 255 +def _mk_bitmap(bits, _CODEBITS=_CODEBITS, _int=int): + s = bits.translate(_BITS_TRANS)[::-1] + return [_int(s[i - _CODEBITS: i], 2) + for i in range(len(s), 0, -_CODEBITS)] + +def _bytes_to_codes(b): + # Convert block indices to word array + a = memoryview(b).cast('I') + assert a.itemsize == _sre.CODESIZE + assert len(a) * a.itemsize == len(b) + return a.tolist() def _simple(av): # check if av is a "simple" operator lo, hi = av[2].getwidth() return lo == hi == 1 and av[2][0][0] != SUBPATTERN +def _generate_overlap_table(prefix): + """ + Generate an overlap table for the following prefix. + An overlap table is a table of the same size as the prefix which + informs about the potential self-overlap for each index in the prefix: + - if overlap[i] == 0, prefix[i:] can't overlap prefix[0:...] + - if overlap[i] == k with 0 < k <= i, prefix[i-k+1:i+1] overlaps with + prefix[0:k] + """ + table = [0] * len(prefix) + for i in range(1, len(prefix)): + idx = table[i - 1] + while prefix[i] != prefix[idx]: + if idx == 0: + table[i] = 0 + break + idx = table[idx - 1] + else: + 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 @@ -455,12 +537,7 @@ def _compile_info(code, pattern, flags): 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 + code.extend(_generate_overlap_table(prefix)) elif charset: _compile_charset(charset, flags, code) code[skip] = len(code) - skip |