+++ /dev/null
-# -*- coding: utf-8 -*-\r
-#\r
-# Secret Labs' Regular Expression Engine\r
-#\r
-# convert template to internal format\r
-#\r
-# Copyright (c) 1997-2001 by Secret Labs AB. All rights reserved.\r
-#\r
-# See the sre.py file for information on usage and redistribution.\r
-#\r
-\r
-"""Internal support module for sre"""\r
-\r
-import _sre, sys\r
-import sre_parse\r
-from sre_constants import *\r
-\r
-assert _sre.MAGIC == MAGIC, "SRE module mismatch"\r
-\r
-if _sre.CODESIZE == 2:\r
- MAXCODE = 65535\r
-else:\r
- MAXCODE = 0xFFFFFFFFL\r
-\r
-_LITERAL_CODES = set([LITERAL, NOT_LITERAL])\r
-_REPEATING_CODES = set([REPEAT, MIN_REPEAT, MAX_REPEAT])\r
-_SUCCESS_CODES = set([SUCCESS, FAILURE])\r
-_ASSERT_CODES = set([ASSERT, ASSERT_NOT])\r
-\r
-# Sets of lowercase characters which have the same uppercase.\r
-_equivalences = (\r
- # LATIN SMALL LETTER I, LATIN SMALL LETTER DOTLESS I\r
- (0x69, 0x131), # iı\r
- # LATIN SMALL LETTER S, LATIN SMALL LETTER LONG S\r
- (0x73, 0x17f), # sſ\r
- # MICRO SIGN, GREEK SMALL LETTER MU\r
- (0xb5, 0x3bc), # µμ\r
- # COMBINING GREEK YPOGEGRAMMENI, GREEK SMALL LETTER IOTA, GREEK PROSGEGRAMMENI\r
- (0x345, 0x3b9, 0x1fbe), # \u0345ιι\r
- # GREEK SMALL LETTER BETA, GREEK BETA SYMBOL\r
- (0x3b2, 0x3d0), # βϐ\r
- # GREEK SMALL LETTER EPSILON, GREEK LUNATE EPSILON SYMBOL\r
- (0x3b5, 0x3f5), # εϵ\r
- # GREEK SMALL LETTER THETA, GREEK THETA SYMBOL\r
- (0x3b8, 0x3d1), # θϑ\r
- # GREEK SMALL LETTER KAPPA, GREEK KAPPA SYMBOL\r
- (0x3ba, 0x3f0), # κϰ\r
- # GREEK SMALL LETTER PI, GREEK PI SYMBOL\r
- (0x3c0, 0x3d6), # πϖ\r
- # GREEK SMALL LETTER RHO, GREEK RHO SYMBOL\r
- (0x3c1, 0x3f1), # ρϱ\r
- # GREEK SMALL LETTER FINAL SIGMA, GREEK SMALL LETTER SIGMA\r
- (0x3c2, 0x3c3), # ςσ\r
- # GREEK SMALL LETTER PHI, GREEK PHI SYMBOL\r
- (0x3c6, 0x3d5), # φϕ\r
- # LATIN SMALL LETTER S WITH DOT ABOVE, LATIN SMALL LETTER LONG S WITH DOT ABOVE\r
- (0x1e61, 0x1e9b), # ṡẛ\r
-)\r
-\r
-# Maps the lowercase code to lowercase codes which have the same uppercase.\r
-_ignorecase_fixes = {i: tuple(j for j in t if i != j)\r
- for t in _equivalences for i in t}\r
-\r
-def _compile(code, pattern, flags):\r
- # internal: compile a (sub)pattern\r
- emit = code.append\r
- _len = len\r
- LITERAL_CODES = _LITERAL_CODES\r
- REPEATING_CODES = _REPEATING_CODES\r
- SUCCESS_CODES = _SUCCESS_CODES\r
- ASSERT_CODES = _ASSERT_CODES\r
- if (flags & SRE_FLAG_IGNORECASE and\r
- not (flags & SRE_FLAG_LOCALE) and\r
- flags & SRE_FLAG_UNICODE):\r
- fixes = _ignorecase_fixes\r
- else:\r
- fixes = None\r
- for op, av in pattern:\r
- if op in LITERAL_CODES:\r
- if flags & SRE_FLAG_IGNORECASE:\r
- lo = _sre.getlower(av, flags)\r
- if fixes and lo in fixes:\r
- emit(OPCODES[IN_IGNORE])\r
- skip = _len(code); emit(0)\r
- if op is NOT_LITERAL:\r
- emit(OPCODES[NEGATE])\r
- for k in (lo,) + fixes[lo]:\r
- emit(OPCODES[LITERAL])\r
- emit(k)\r
- emit(OPCODES[FAILURE])\r
- code[skip] = _len(code) - skip\r
- else:\r
- emit(OPCODES[OP_IGNORE[op]])\r
- emit(lo)\r
- else:\r
- emit(OPCODES[op])\r
- emit(av)\r
- elif op is IN:\r
- if flags & SRE_FLAG_IGNORECASE:\r
- emit(OPCODES[OP_IGNORE[op]])\r
- def fixup(literal, flags=flags):\r
- return _sre.getlower(literal, flags)\r
- else:\r
- emit(OPCODES[op])\r
- fixup = None\r
- skip = _len(code); emit(0)\r
- _compile_charset(av, flags, code, fixup, fixes)\r
- code[skip] = _len(code) - skip\r
- elif op is ANY:\r
- if flags & SRE_FLAG_DOTALL:\r
- emit(OPCODES[ANY_ALL])\r
- else:\r
- emit(OPCODES[ANY])\r
- elif op in REPEATING_CODES:\r
- if flags & SRE_FLAG_TEMPLATE:\r
- raise error, "internal: unsupported template operator"\r
- emit(OPCODES[REPEAT])\r
- skip = _len(code); emit(0)\r
- emit(av[0])\r
- emit(av[1])\r
- _compile(code, av[2], flags)\r
- emit(OPCODES[SUCCESS])\r
- code[skip] = _len(code) - skip\r
- elif _simple(av) and op is not REPEAT:\r
- if op is MAX_REPEAT:\r
- emit(OPCODES[REPEAT_ONE])\r
- else:\r
- emit(OPCODES[MIN_REPEAT_ONE])\r
- skip = _len(code); emit(0)\r
- emit(av[0])\r
- emit(av[1])\r
- _compile(code, av[2], flags)\r
- emit(OPCODES[SUCCESS])\r
- code[skip] = _len(code) - skip\r
- else:\r
- emit(OPCODES[REPEAT])\r
- skip = _len(code); emit(0)\r
- emit(av[0])\r
- emit(av[1])\r
- _compile(code, av[2], flags)\r
- code[skip] = _len(code) - skip\r
- if op is MAX_REPEAT:\r
- emit(OPCODES[MAX_UNTIL])\r
- else:\r
- emit(OPCODES[MIN_UNTIL])\r
- elif op is SUBPATTERN:\r
- if av[0]:\r
- emit(OPCODES[MARK])\r
- emit((av[0]-1)*2)\r
- # _compile_info(code, av[1], flags)\r
- _compile(code, av[1], flags)\r
- if av[0]:\r
- emit(OPCODES[MARK])\r
- emit((av[0]-1)*2+1)\r
- elif op in SUCCESS_CODES:\r
- emit(OPCODES[op])\r
- elif op in ASSERT_CODES:\r
- emit(OPCODES[op])\r
- skip = _len(code); emit(0)\r
- if av[0] >= 0:\r
- emit(0) # look ahead\r
- else:\r
- lo, hi = av[1].getwidth()\r
- if lo != hi:\r
- raise error, "look-behind requires fixed-width pattern"\r
- emit(lo) # look behind\r
- _compile(code, av[1], flags)\r
- emit(OPCODES[SUCCESS])\r
- code[skip] = _len(code) - skip\r
- elif op is CALL:\r
- emit(OPCODES[op])\r
- skip = _len(code); emit(0)\r
- _compile(code, av, flags)\r
- emit(OPCODES[SUCCESS])\r
- code[skip] = _len(code) - skip\r
- elif op is AT:\r
- emit(OPCODES[op])\r
- if flags & SRE_FLAG_MULTILINE:\r
- av = AT_MULTILINE.get(av, av)\r
- if flags & SRE_FLAG_LOCALE:\r
- av = AT_LOCALE.get(av, av)\r
- elif flags & SRE_FLAG_UNICODE:\r
- av = AT_UNICODE.get(av, av)\r
- emit(ATCODES[av])\r
- elif op is BRANCH:\r
- emit(OPCODES[op])\r
- tail = []\r
- tailappend = tail.append\r
- for av in av[1]:\r
- skip = _len(code); emit(0)\r
- # _compile_info(code, av, flags)\r
- _compile(code, av, flags)\r
- emit(OPCODES[JUMP])\r
- tailappend(_len(code)); emit(0)\r
- code[skip] = _len(code) - skip\r
- emit(0) # end of branch\r
- for tail in tail:\r
- code[tail] = _len(code) - tail\r
- elif op is CATEGORY:\r
- emit(OPCODES[op])\r
- if flags & SRE_FLAG_LOCALE:\r
- av = CH_LOCALE[av]\r
- elif flags & SRE_FLAG_UNICODE:\r
- av = CH_UNICODE[av]\r
- emit(CHCODES[av])\r
- elif op is GROUPREF:\r
- if flags & SRE_FLAG_IGNORECASE:\r
- emit(OPCODES[OP_IGNORE[op]])\r
- else:\r
- emit(OPCODES[op])\r
- emit(av-1)\r
- elif op is GROUPREF_EXISTS:\r
- emit(OPCODES[op])\r
- emit(av[0]-1)\r
- skipyes = _len(code); emit(0)\r
- _compile(code, av[1], flags)\r
- if av[2]:\r
- emit(OPCODES[JUMP])\r
- skipno = _len(code); emit(0)\r
- code[skipyes] = _len(code) - skipyes + 1\r
- _compile(code, av[2], flags)\r
- code[skipno] = _len(code) - skipno\r
- else:\r
- code[skipyes] = _len(code) - skipyes + 1\r
- else:\r
- raise ValueError, ("unsupported operand type", op)\r
-\r
-def _compile_charset(charset, flags, code, fixup=None, fixes=None):\r
- # compile charset subprogram\r
- emit = code.append\r
- for op, av in _optimize_charset(charset, fixup, fixes,\r
- flags & SRE_FLAG_UNICODE):\r
- emit(OPCODES[op])\r
- if op is NEGATE:\r
- pass\r
- elif op is LITERAL:\r
- emit(av)\r
- elif op is RANGE:\r
- emit(av[0])\r
- emit(av[1])\r
- elif op is CHARSET:\r
- code.extend(av)\r
- elif op is BIGCHARSET:\r
- code.extend(av)\r
- elif op is CATEGORY:\r
- if flags & SRE_FLAG_LOCALE:\r
- emit(CHCODES[CH_LOCALE[av]])\r
- elif flags & SRE_FLAG_UNICODE:\r
- emit(CHCODES[CH_UNICODE[av]])\r
- else:\r
- emit(CHCODES[av])\r
- else:\r
- raise error, "internal: unsupported set operator"\r
- emit(OPCODES[FAILURE])\r
-\r
-def _optimize_charset(charset, fixup, fixes, isunicode):\r
- # internal: optimize character set\r
- out = []\r
- tail = []\r
- charmap = bytearray(256)\r
- for op, av in charset:\r
- while True:\r
- try:\r
- if op is LITERAL:\r
- if fixup:\r
- i = fixup(av)\r
- charmap[i] = 1\r
- if fixes and i in fixes:\r
- for k in fixes[i]:\r
- charmap[k] = 1\r
- else:\r
- charmap[av] = 1\r
- elif op is RANGE:\r
- r = range(av[0], av[1]+1)\r
- if fixup:\r
- r = map(fixup, r)\r
- if fixup and fixes:\r
- for i in r:\r
- charmap[i] = 1\r
- if i in fixes:\r
- for k in fixes[i]:\r
- charmap[k] = 1\r
- else:\r
- for i in r:\r
- charmap[i] = 1\r
- elif op is NEGATE:\r
- out.append((op, av))\r
- else:\r
- tail.append((op, av))\r
- except IndexError:\r
- if len(charmap) == 256:\r
- # character set contains non-UCS1 character codes\r
- charmap += b'\0' * 0xff00\r
- continue\r
- # character set contains non-BMP character codes\r
- if fixup and isunicode and op is RANGE:\r
- lo, hi = av\r
- ranges = [av]\r
- # There are only two ranges of cased astral characters:\r
- # 10400-1044F (Deseret) and 118A0-118DF (Warang Citi).\r
- _fixup_range(max(0x10000, lo), min(0x11fff, hi),\r
- ranges, fixup)\r
- for lo, hi in ranges:\r
- if lo == hi:\r
- tail.append((LITERAL, hi))\r
- else:\r
- tail.append((RANGE, (lo, hi)))\r
- else:\r
- tail.append((op, av))\r
- break\r
-\r
- # compress character map\r
- runs = []\r
- q = 0\r
- while True:\r
- p = charmap.find(b'\1', q)\r
- if p < 0:\r
- break\r
- if len(runs) >= 2:\r
- runs = None\r
- break\r
- q = charmap.find(b'\0', p)\r
- if q < 0:\r
- runs.append((p, len(charmap)))\r
- break\r
- runs.append((p, q))\r
- if runs is not None:\r
- # use literal/range\r
- for p, q in runs:\r
- if q - p == 1:\r
- out.append((LITERAL, p))\r
- else:\r
- out.append((RANGE, (p, q - 1)))\r
- out += tail\r
- # if the case was changed or new representation is more compact\r
- if fixup or len(out) < len(charset):\r
- return out\r
- # else original character set is good enough\r
- return charset\r
-\r
- # use bitmap\r
- if len(charmap) == 256:\r
- data = _mk_bitmap(charmap)\r
- out.append((CHARSET, data))\r
- out += tail\r
- return out\r
-\r
- # To represent a big charset, first a bitmap of all characters in the\r
- # set is constructed. Then, this bitmap is sliced into chunks of 256\r
- # characters, duplicate chunks are eliminated, and each chunk is\r
- # given a number. In the compiled expression, the charset is\r
- # represented by a 32-bit word sequence, consisting of one word for\r
- # the number of different chunks, a sequence of 256 bytes (64 words)\r
- # of chunk numbers indexed by their original chunk position, and a\r
- # sequence of 256-bit chunks (8 words each).\r
-\r
- # Compression is normally good: in a typical charset, large ranges of\r
- # Unicode will be either completely excluded (e.g. if only cyrillic\r
- # letters are to be matched), or completely included (e.g. if large\r
- # subranges of Kanji match). These ranges will be represented by\r
- # chunks of all one-bits or all zero-bits.\r
-\r
- # Matching can be also done efficiently: the more significant byte of\r
- # the Unicode character is an index into the chunk number, and the\r
- # less significant byte is a bit index in the chunk (just like the\r
- # CHARSET matching).\r
-\r
- # In UCS-4 mode, the BIGCHARSET opcode still supports only subsets\r
- # of the basic multilingual plane; an efficient representation\r
- # for all of Unicode has not yet been developed.\r
-\r
- charmap = bytes(charmap) # should be hashable\r
- comps = {}\r
- mapping = bytearray(256)\r
- block = 0\r
- data = bytearray()\r
- for i in range(0, 65536, 256):\r
- chunk = charmap[i: i + 256]\r
- if chunk in comps:\r
- mapping[i // 256] = comps[chunk]\r
- else:\r
- mapping[i // 256] = comps[chunk] = block\r
- block += 1\r
- data += chunk\r
- data = _mk_bitmap(data)\r
- data[0:0] = [block] + _bytes_to_codes(mapping)\r
- out.append((BIGCHARSET, data))\r
- out += tail\r
- return out\r
-\r
-def _fixup_range(lo, hi, ranges, fixup):\r
- for i in map(fixup, range(lo, hi+1)):\r
- for k, (lo, hi) in enumerate(ranges):\r
- if i < lo:\r
- if l == lo - 1:\r
- ranges[k] = (i, hi)\r
- else:\r
- ranges.insert(k, (i, i))\r
- break\r
- elif i > hi:\r
- if i == hi + 1:\r
- ranges[k] = (lo, i)\r
- break\r
- else:\r
- break\r
- else:\r
- ranges.append((i, i))\r
-\r
-_CODEBITS = _sre.CODESIZE * 8\r
-_BITS_TRANS = b'0' + b'1' * 255\r
-def _mk_bitmap(bits, _CODEBITS=_CODEBITS, _int=int):\r
- s = bytes(bits).translate(_BITS_TRANS)[::-1]\r
- return [_int(s[i - _CODEBITS: i], 2)\r
- for i in range(len(s), 0, -_CODEBITS)]\r
-\r
-def _bytes_to_codes(b):\r
- # Convert block indices to word array\r
- import array\r
- if _sre.CODESIZE == 2:\r
- code = 'H'\r
- else:\r
- code = 'I'\r
- a = array.array(code, bytes(b))\r
- assert a.itemsize == _sre.CODESIZE\r
- assert len(a) * a.itemsize == len(b)\r
- return a.tolist()\r
-\r
-def _simple(av):\r
- # check if av is a "simple" operator\r
- lo, hi = av[2].getwidth()\r
- return lo == hi == 1 and av[2][0][0] != SUBPATTERN\r
-\r
-def _compile_info(code, pattern, flags):\r
- # internal: compile an info block. in the current version,\r
- # this contains min/max pattern width, and an optional literal\r
- # prefix or a character map\r
- lo, hi = pattern.getwidth()\r
- if lo == 0:\r
- return # not worth it\r
- # look for a literal prefix\r
- prefix = []\r
- prefixappend = prefix.append\r
- prefix_skip = 0\r
- charset = [] # not used\r
- charsetappend = charset.append\r
- if not (flags & SRE_FLAG_IGNORECASE):\r
- # look for literal prefix\r
- for op, av in pattern.data:\r
- if op is LITERAL:\r
- if len(prefix) == prefix_skip:\r
- prefix_skip = prefix_skip + 1\r
- prefixappend(av)\r
- elif op is SUBPATTERN and len(av[1]) == 1:\r
- op, av = av[1][0]\r
- if op is LITERAL:\r
- prefixappend(av)\r
- else:\r
- break\r
- else:\r
- break\r
- # if no prefix, look for charset prefix\r
- if not prefix and pattern.data:\r
- op, av = pattern.data[0]\r
- if op is SUBPATTERN and av[1]:\r
- op, av = av[1][0]\r
- if op is LITERAL:\r
- charsetappend((op, av))\r
- elif op is BRANCH:\r
- c = []\r
- cappend = c.append\r
- for p in av[1]:\r
- if not p:\r
- break\r
- op, av = p[0]\r
- if op is LITERAL:\r
- cappend((op, av))\r
- else:\r
- break\r
- else:\r
- charset = c\r
- elif op is BRANCH:\r
- c = []\r
- cappend = c.append\r
- for p in av[1]:\r
- if not p:\r
- break\r
- op, av = p[0]\r
- if op is LITERAL:\r
- cappend((op, av))\r
- else:\r
- break\r
- else:\r
- charset = c\r
- elif op is IN:\r
- charset = av\r
-## if prefix:\r
-## print "*** PREFIX", prefix, prefix_skip\r
-## if charset:\r
-## print "*** CHARSET", charset\r
- # add an info block\r
- emit = code.append\r
- emit(OPCODES[INFO])\r
- skip = len(code); emit(0)\r
- # literal flag\r
- mask = 0\r
- if prefix:\r
- mask = SRE_INFO_PREFIX\r
- if len(prefix) == prefix_skip == len(pattern.data):\r
- mask = mask + SRE_INFO_LITERAL\r
- elif charset:\r
- mask = mask + SRE_INFO_CHARSET\r
- emit(mask)\r
- # pattern length\r
- if lo < MAXCODE:\r
- emit(lo)\r
- else:\r
- emit(MAXCODE)\r
- prefix = prefix[:MAXCODE]\r
- if hi < MAXCODE:\r
- emit(hi)\r
- else:\r
- emit(0)\r
- # add literal prefix\r
- if prefix:\r
- emit(len(prefix)) # length\r
- emit(prefix_skip) # skip\r
- code.extend(prefix)\r
- # generate overlap table\r
- table = [-1] + ([0]*len(prefix))\r
- for i in xrange(len(prefix)):\r
- table[i+1] = table[i]+1\r
- while table[i+1] > 0 and prefix[i] != prefix[table[i+1]-1]:\r
- table[i+1] = table[table[i+1]-1]+1\r
- code.extend(table[1:]) # don't store first entry\r
- elif charset:\r
- _compile_charset(charset, flags, code)\r
- code[skip] = len(code) - skip\r
-\r
-try:\r
- unicode\r
-except NameError:\r
- STRING_TYPES = (type(""),)\r
-else:\r
- STRING_TYPES = (type(""), type(unicode("")))\r
-\r
-def isstring(obj):\r
- for tp in STRING_TYPES:\r
- if isinstance(obj, tp):\r
- return 1\r
- return 0\r
-\r
-def _code(p, flags):\r
-\r
- flags = p.pattern.flags | flags\r
- code = []\r
-\r
- # compile info block\r
- _compile_info(code, p, flags)\r
-\r
- # compile the pattern\r
- _compile(code, p.data, flags)\r
-\r
- code.append(OPCODES[SUCCESS])\r
-\r
- return code\r
-\r
-def compile(p, flags=0):\r
- # internal: convert pattern list to internal format\r
-\r
- if isstring(p):\r
- pattern = p\r
- p = sre_parse.parse(p, flags)\r
- else:\r
- pattern = None\r
-\r
- code = _code(p, flags)\r
-\r
- # print code\r
-\r
- # XXX: <fl> get rid of this limitation!\r
- if p.pattern.groups > 100:\r
- raise AssertionError(\r
- "sorry, but this version only supports 100 named groups"\r
- )\r
-\r
- # map in either direction\r
- groupindex = p.pattern.groupdict\r
- indexgroup = [None] * p.pattern.groups\r
- for k, i in groupindex.items():\r
- indexgroup[i] = k\r
-\r
- return _sre.compile(\r
- pattern, flags | p.pattern.flags, code,\r
- p.pattern.groups-1,\r
- groupindex, indexgroup\r
- )\r
projects / mirror_edk2.git / blobdiff