Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 1 | # |
| 2 | # Secret Labs' Regular Expression Engine |
| 3 | # $Id$ |
| 4 | # |
| 5 | # convert template to internal format |
| 6 | # |
| 7 | # Copyright (c) 1997-2000 by Secret Labs AB. All rights reserved. |
| 8 | # |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 9 | # Portions of this engine have been developed in cooperation with |
| 10 | # CNRI. Hewlett-Packard provided funding for 1.6 integration and |
| 11 | # other compatibility work. |
| 12 | # |
| 13 | |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 14 | import array |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 15 | import _sre |
| 16 | |
| 17 | from sre_constants import * |
| 18 | |
| 19 | # find an array type code that matches the engine's code size |
| 20 | for WORDSIZE in "BHil": |
| 21 | if len(array.array(WORDSIZE, [0]).tostring()) == _sre.getcodesize(): |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 22 | break |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 23 | else: |
| 24 | raise RuntimeError, "cannot find a useable array type" |
| 25 | |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 26 | def _compile(code, pattern, flags): |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 27 | emit = code.append |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 28 | for op, av in pattern: |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 29 | if op is ANY: |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 30 | if flags & SRE_FLAG_DOTALL: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 31 | emit(OPCODES[op]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 32 | else: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 33 | emit(OPCODES[CATEGORY]) |
| 34 | emit(CHCODES[CATEGORY_NOT_LINEBREAK]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 35 | elif op in (SUCCESS, FAILURE): |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 36 | emit(OPCODES[op]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 37 | elif op is AT: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 38 | emit(OPCODES[op]) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 39 | if flags & SRE_FLAG_MULTILINE: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 40 | emit(ATCODES[AT_MULTILINE[av]]) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 41 | else: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 42 | emit(ATCODES[av]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 43 | elif op is BRANCH: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 44 | emit(OPCODES[op]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 45 | tail = [] |
| 46 | for av in av[1]: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 47 | skip = len(code); emit(0) |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 48 | _compile(code, av, flags) |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 49 | emit(OPCODES[JUMP]) |
| 50 | tail.append(len(code)); emit(0) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 51 | code[skip] = len(code) - skip |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 52 | emit(0) # end of branch |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 53 | for tail in tail: |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 54 | code[tail] = len(code) - tail |
| 55 | elif op is CALL: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 56 | emit(OPCODES[op]) |
| 57 | skip = len(code); emit(0) |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 58 | _compile(code, av, flags) |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 59 | emit(OPCODES[SUCCESS]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 60 | code[skip] = len(code) - skip |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 61 | elif op is CATEGORY: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 62 | emit(OPCODES[op]) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 63 | if flags & SRE_FLAG_LOCALE: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 64 | emit(CH_LOCALE[CHCODES[av]]) |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 65 | elif flags & SRE_FLAG_UNICODE: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 66 | emit(CH_UNICODE[CHCODES[av]]) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 67 | else: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 68 | emit(CHCODES[av]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 69 | elif op is GROUP: |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 70 | if flags & SRE_FLAG_IGNORECASE: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 71 | emit(OPCODES[OP_IGNORE[op]]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 72 | else: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 73 | emit(OPCODES[op]) |
| 74 | emit(av-1) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 75 | elif op is IN: |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 76 | if flags & SRE_FLAG_IGNORECASE: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 77 | emit(OPCODES[OP_IGNORE[op]]) |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 78 | def fixup(literal, flags=flags): |
| 79 | return _sre.getlower(ord(literal), flags) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 80 | else: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 81 | emit(OPCODES[op]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 82 | fixup = ord |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 83 | skip = len(code); emit(0) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 84 | for op, av in av: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 85 | emit(OPCODES[op]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 86 | if op is NEGATE: |
| 87 | pass |
| 88 | elif op is LITERAL: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 89 | emit(fixup(av)) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 90 | elif op is RANGE: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 91 | emit(fixup(av[0])) |
| 92 | emit(fixup(av[1])) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 93 | elif op is CATEGORY: |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 94 | if flags & SRE_FLAG_LOCALE: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 95 | emit(CH_LOCALE[CHCODES[av]]) |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 96 | elif flags & SRE_FLAG_UNICODE: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 97 | emit(CH_UNICODE[CHCODES[av]]) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 98 | else: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 99 | emit(CHCODES[av]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 100 | else: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 101 | raise error, "internal: unsupported set operator" |
| 102 | emit(OPCODES[FAILURE]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 103 | code[skip] = len(code) - skip |
| 104 | elif op in (LITERAL, NOT_LITERAL): |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 105 | if flags & SRE_FLAG_IGNORECASE: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 106 | emit(OPCODES[OP_IGNORE[op]]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 107 | else: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 108 | emit(OPCODES[op]) |
| 109 | emit(ord(av)) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 110 | elif op is MARK: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 111 | emit(OPCODES[op]) |
| 112 | emit(av) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 113 | elif op in (REPEAT, MIN_REPEAT, MAX_REPEAT): |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 114 | if flags & SRE_FLAG_TEMPLATE: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 115 | emit(OPCODES[REPEAT]) |
| 116 | skip = len(code); emit(0) |
| 117 | emit(av[0]) |
| 118 | emit(av[1]) |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 119 | _compile(code, av[2], flags) |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 120 | emit(OPCODES[SUCCESS]) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 121 | code[skip] = len(code) - skip |
| 122 | else: |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 123 | lo, hi = av[2].getwidth() |
| 124 | if lo == 0: |
| 125 | raise error, "nothing to repeat" |
| 126 | if 0 and lo == hi == 1 and op is MAX_REPEAT: |
| 127 | # FIXME: <fl> need a better way to figure out when |
| 128 | # it's safe to use this one (in the parser, probably) |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 129 | emit(OPCODES[MAX_REPEAT_ONE]) |
| 130 | skip = len(code); emit(0) |
| 131 | emit(av[0]) |
| 132 | emit(av[1]) |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 133 | _compile(code, av[2], flags) |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 134 | emit(OPCODES[SUCCESS]) |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 135 | code[skip] = len(code) - skip |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 136 | else: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 137 | emit(OPCODES[op]) |
| 138 | skip = len(code); emit(0) |
| 139 | emit(av[0]) |
| 140 | emit(av[1]) |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 141 | _compile(code, av[2], flags) |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 142 | emit(OPCODES[SUCCESS]) |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 143 | code[skip] = len(code) - skip |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 144 | elif op is SUBPATTERN: |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 145 | group = av[0] |
| 146 | if group: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 147 | emit(OPCODES[MARK]) |
| 148 | emit((group-1)*2) |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 149 | _compile(code, av[1], flags) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 150 | if group: |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 151 | emit(OPCODES[MARK]) |
| 152 | emit((group-1)*2+1) |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 153 | else: |
| 154 | raise ValueError, ("unsupported operand type", op) |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 155 | |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 156 | def compile(p, flags=0): |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 157 | # internal: convert pattern list to internal format |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 158 | if type(p) in (type(""), type(u"")): |
| 159 | import sre_parse |
| 160 | pattern = p |
| 161 | p = sre_parse.parse(p) |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 162 | else: |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 163 | pattern = None |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 164 | flags = p.pattern.flags | flags |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 165 | code = [] |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 166 | _compile(code, p.data, flags) |
| 167 | code.append(OPCODES[SUCCESS]) |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 168 | # FIXME: <fl> get rid of this limitation |
| 169 | assert p.pattern.groups <= 100,\ |
| 170 | "sorry, but this version only supports 100 named groups" |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 171 | return _sre.compile( |
| 172 | pattern, flags, |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame^] | 173 | array.array(WORDSIZE, code).tostring(), |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 174 | p.pattern.groups-1, p.pattern.groupdict |
| 175 | ) |