Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 1 | # |
| 2 | # Secret Labs' Regular Expression Engine |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 3 | # |
| 4 | # convert template to internal format |
| 5 | # |
| 6 | # Copyright (c) 1997-2000 by Secret Labs AB. All rights reserved. |
| 7 | # |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 8 | # Portions of this engine have been developed in cooperation with |
Fredrik Lundh | 22d2546 | 2000-07-01 17:50:59 +0000 | [diff] [blame] | 9 | # CNRI. Hewlett-Packard provided funding for 2.0 integration and |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 10 | # other compatibility work. |
| 11 | # |
| 12 | |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 13 | import _sre |
| 14 | |
| 15 | from sre_constants import * |
| 16 | |
Fredrik Lundh | 3562f11 | 2000-07-02 12:00:07 +0000 | [diff] [blame] | 17 | MAXCODE = 65535 |
| 18 | |
| 19 | def _charset(charset, fixup): |
| 20 | # internal: optimize character set |
| 21 | out = [] |
| 22 | charmap = [0]*256 |
| 23 | try: |
| 24 | for op, av in charset: |
| 25 | if op is NEGATE: |
| 26 | out.append((op, av)) |
| 27 | elif op is LITERAL: |
| 28 | charmap[fixup(av)] = 1 |
| 29 | elif op is RANGE: |
| 30 | for i in range(fixup(av[0]), fixup(av[1])+1): |
| 31 | charmap[i] = 1 |
| 32 | elif op is CATEGORY: |
| 33 | # FIXME: could append to charmap tail |
| 34 | return charset # cannot compress |
| 35 | except IndexError: |
| 36 | # unicode |
| 37 | return charset |
| 38 | # compress character map |
| 39 | i = p = n = 0 |
| 40 | runs = [] |
| 41 | for c in charmap: |
| 42 | if c: |
| 43 | if n == 0: |
| 44 | p = i |
| 45 | n = n + 1 |
| 46 | elif n: |
| 47 | runs.append((p, n)) |
| 48 | n = 0 |
| 49 | i = i + 1 |
| 50 | if n: |
| 51 | runs.append((p, n)) |
| 52 | if len(runs) <= 2: |
| 53 | # use literal/range |
| 54 | for p, n in runs: |
| 55 | if n == 1: |
| 56 | out.append((LITERAL, p)) |
| 57 | else: |
| 58 | out.append((RANGE, (p, p+n-1))) |
| 59 | if len(out) < len(charset): |
| 60 | return out |
| 61 | else: |
| 62 | # use bitmap |
| 63 | data = [] |
| 64 | m = 1; v = 0 |
| 65 | for c in charmap: |
| 66 | if c: |
| 67 | v = v + m |
| 68 | m = m << 1 |
| 69 | if m > MAXCODE: |
| 70 | data.append(v) |
| 71 | m = 1; v = 0 |
| 72 | out.append((CHARSET, data)) |
| 73 | return out |
| 74 | return charset |
| 75 | |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 76 | def _compile(code, pattern, flags): |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 77 | # internal: compile a (sub)pattern |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame] | 78 | emit = code.append |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 79 | for op, av in pattern: |
Fredrik Lundh | 43b3b49 | 2000-06-30 10:41:31 +0000 | [diff] [blame] | 80 | if op in (LITERAL, NOT_LITERAL): |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 81 | if flags & SRE_FLAG_IGNORECASE: |
| 82 | emit(OPCODES[OP_IGNORE[op]]) |
| 83 | else: |
| 84 | emit(OPCODES[op]) |
Fredrik Lundh | 0640e11 | 2000-06-30 13:55:15 +0000 | [diff] [blame] | 85 | emit(av) |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 86 | elif op is IN: |
| 87 | if flags & SRE_FLAG_IGNORECASE: |
| 88 | emit(OPCODES[OP_IGNORE[op]]) |
| 89 | def fixup(literal, flags=flags): |
Fredrik Lundh | 0640e11 | 2000-06-30 13:55:15 +0000 | [diff] [blame] | 90 | return _sre.getlower(literal, flags) |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 91 | else: |
| 92 | emit(OPCODES[op]) |
Fredrik Lundh | 4ccea94 | 2000-06-30 18:39:20 +0000 | [diff] [blame] | 93 | fixup = lambda x: x |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 94 | skip = len(code); emit(0) |
Fredrik Lundh | 3562f11 | 2000-07-02 12:00:07 +0000 | [diff] [blame] | 95 | for op, av in _charset(av, fixup): |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 96 | emit(OPCODES[op]) |
| 97 | if op is NEGATE: |
| 98 | pass |
| 99 | elif op is LITERAL: |
| 100 | emit(fixup(av)) |
| 101 | elif op is RANGE: |
| 102 | emit(fixup(av[0])) |
| 103 | emit(fixup(av[1])) |
Fredrik Lundh | 3562f11 | 2000-07-02 12:00:07 +0000 | [diff] [blame] | 104 | elif op is CHARSET: |
| 105 | code.extend(av) |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 106 | elif op is CATEGORY: |
| 107 | if flags & SRE_FLAG_LOCALE: |
| 108 | emit(CHCODES[CH_LOCALE[av]]) |
| 109 | elif flags & SRE_FLAG_UNICODE: |
| 110 | emit(CHCODES[CH_UNICODE[av]]) |
| 111 | else: |
| 112 | emit(CHCODES[av]) |
| 113 | else: |
| 114 | raise error, "internal: unsupported set operator" |
| 115 | emit(OPCODES[FAILURE]) |
| 116 | code[skip] = len(code) - skip |
Fredrik Lundh | 43b3b49 | 2000-06-30 10:41:31 +0000 | [diff] [blame] | 117 | elif op is ANY: |
| 118 | if flags & SRE_FLAG_DOTALL: |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 119 | emit(OPCODES[op]) |
Fredrik Lundh | 43b3b49 | 2000-06-30 10:41:31 +0000 | [diff] [blame] | 120 | else: |
| 121 | emit(OPCODES[CATEGORY]) |
| 122 | emit(CHCODES[CATEGORY_NOT_LINEBREAK]) |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 123 | elif op in (REPEAT, MIN_REPEAT, MAX_REPEAT): |
| 124 | if flags & SRE_FLAG_TEMPLATE: |
| 125 | emit(OPCODES[REPEAT]) |
| 126 | skip = len(code); emit(0) |
| 127 | emit(av[0]) |
| 128 | emit(av[1]) |
| 129 | _compile(code, av[2], flags) |
| 130 | emit(OPCODES[SUCCESS]) |
| 131 | code[skip] = len(code) - skip |
| 132 | else: |
| 133 | lo, hi = av[2].getwidth() |
| 134 | if lo == 0: |
| 135 | raise error, "nothing to repeat" |
| 136 | if 0 and lo == hi == 1 and op is MAX_REPEAT: |
| 137 | # FIXME: <fl> need a better way to figure out when |
| 138 | # it's safe to use this one (in the parser, probably) |
| 139 | emit(OPCODES[MAX_REPEAT_ONE]) |
| 140 | skip = len(code); emit(0) |
| 141 | emit(av[0]) |
| 142 | emit(av[1]) |
| 143 | _compile(code, av[2], flags) |
| 144 | emit(OPCODES[SUCCESS]) |
| 145 | code[skip] = len(code) - skip |
| 146 | else: |
| 147 | emit(OPCODES[op]) |
| 148 | skip = len(code); emit(0) |
| 149 | emit(av[0]) |
| 150 | emit(av[1]) |
Fredrik Lundh | 72b82ba | 2000-07-03 21:31:48 +0000 | [diff] [blame] | 151 | mark = MAXCODE |
| 152 | if av[2][0][0] == SUBPATTERN: |
| 153 | # repeated subpattern |
| 154 | gid, foo = av[2][0][1] |
| 155 | if gid: |
| 156 | mark = (gid-1)*2 |
| 157 | emit(mark) |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 158 | _compile(code, av[2], flags) |
| 159 | emit(OPCODES[SUCCESS]) |
| 160 | code[skip] = len(code) - skip |
| 161 | elif op is SUBPATTERN: |
Fredrik Lundh | 72b82ba | 2000-07-03 21:31:48 +0000 | [diff] [blame] | 162 | gid = av[0] |
| 163 | if gid: |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 164 | emit(OPCODES[MARK]) |
Fredrik Lundh | 72b82ba | 2000-07-03 21:31:48 +0000 | [diff] [blame] | 165 | emit((gid-1)*2) |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 166 | _compile(code, av[1], flags) |
Fredrik Lundh | 72b82ba | 2000-07-03 21:31:48 +0000 | [diff] [blame] | 167 | if gid: |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 168 | emit(OPCODES[MARK]) |
Fredrik Lundh | 72b82ba | 2000-07-03 21:31:48 +0000 | [diff] [blame] | 169 | emit((gid-1)*2+1) |
Fredrik Lundh | 43b3b49 | 2000-06-30 10:41:31 +0000 | [diff] [blame] | 170 | elif op in (SUCCESS, FAILURE): |
| 171 | emit(OPCODES[op]) |
Fredrik Lundh | 6f01398 | 2000-07-03 18:44:21 +0000 | [diff] [blame] | 172 | elif op in (ASSERT, ASSERT_NOT): |
| 173 | emit(OPCODES[op]) |
| 174 | skip = len(code); emit(0) |
| 175 | if av[0] >= 0: |
| 176 | emit(0) # look ahead |
| 177 | else: |
| 178 | lo, hi = av[1].getwidth() |
| 179 | if lo != hi: |
| 180 | raise error, "look-behind requires fixed-width pattern" |
| 181 | emit(lo) # look behind |
| 182 | _compile(code, av[1], flags) |
| 183 | emit(OPCODES[SUCCESS]) |
| 184 | code[skip] = len(code) - skip |
| 185 | elif op is CALL: |
Fredrik Lundh | 43b3b49 | 2000-06-30 10:41:31 +0000 | [diff] [blame] | 186 | emit(OPCODES[op]) |
| 187 | skip = len(code); emit(0) |
| 188 | _compile(code, av, flags) |
| 189 | emit(OPCODES[SUCCESS]) |
| 190 | code[skip] = len(code) - skip |
| 191 | elif op is AT: |
| 192 | emit(OPCODES[op]) |
| 193 | if flags & SRE_FLAG_MULTILINE: |
Fredrik Lundh | 55a4f4a | 2000-06-30 22:37:31 +0000 | [diff] [blame] | 194 | emit(ATCODES[AT_MULTILINE.get(av, av)]) |
Fredrik Lundh | 43b3b49 | 2000-06-30 10:41:31 +0000 | [diff] [blame] | 195 | else: |
| 196 | emit(ATCODES[av]) |
| 197 | elif op is BRANCH: |
| 198 | emit(OPCODES[op]) |
| 199 | tail = [] |
| 200 | for av in av[1]: |
| 201 | skip = len(code); emit(0) |
| 202 | _compile(code, av, flags) |
| 203 | emit(OPCODES[JUMP]) |
| 204 | tail.append(len(code)); emit(0) |
| 205 | code[skip] = len(code) - skip |
| 206 | emit(0) # end of branch |
| 207 | for tail in tail: |
| 208 | code[tail] = len(code) - tail |
| 209 | elif op is CATEGORY: |
| 210 | emit(OPCODES[op]) |
| 211 | if flags & SRE_FLAG_LOCALE: |
| 212 | emit(CHCODES[CH_LOCALE[av]]) |
| 213 | elif flags & SRE_FLAG_UNICODE: |
| 214 | emit(CHCODES[CH_UNICODE[av]]) |
| 215 | else: |
| 216 | emit(CHCODES[av]) |
Fredrik Lundh | 72b82ba | 2000-07-03 21:31:48 +0000 | [diff] [blame] | 217 | elif op is GROUPREF: |
Fredrik Lundh | 43b3b49 | 2000-06-30 10:41:31 +0000 | [diff] [blame] | 218 | if flags & SRE_FLAG_IGNORECASE: |
| 219 | emit(OPCODES[OP_IGNORE[op]]) |
| 220 | else: |
| 221 | emit(OPCODES[op]) |
| 222 | emit(av-1) |
Fredrik Lundh | 7cafe4d | 2000-07-02 17:33:27 +0000 | [diff] [blame] | 223 | elif op in (MARK, INDEX): |
Fredrik Lundh | 43b3b49 | 2000-06-30 10:41:31 +0000 | [diff] [blame] | 224 | emit(OPCODES[op]) |
| 225 | emit(av) |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 226 | else: |
| 227 | raise ValueError, ("unsupported operand type", op) |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 228 | |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 229 | def _compile_info(code, pattern, flags): |
| 230 | # internal: compile an info block. in the current version, |
Fredrik Lundh | 3562f11 | 2000-07-02 12:00:07 +0000 | [diff] [blame] | 231 | # this contains min/max pattern width, and an optional literal |
| 232 | # prefix or a character map |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 233 | lo, hi = pattern.getwidth() |
| 234 | if lo == 0: |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 235 | return # not worth it |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 236 | # look for a literal prefix |
| 237 | prefix = [] |
Fredrik Lundh | 3562f11 | 2000-07-02 12:00:07 +0000 | [diff] [blame] | 238 | charset = [] # not used |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 239 | if not (flags & SRE_FLAG_IGNORECASE): |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 240 | for op, av in pattern.data: |
| 241 | if op is LITERAL: |
Fredrik Lundh | 0640e11 | 2000-06-30 13:55:15 +0000 | [diff] [blame] | 242 | prefix.append(av) |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 243 | else: |
| 244 | break |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 245 | # add an info block |
| 246 | emit = code.append |
| 247 | emit(OPCODES[INFO]) |
| 248 | skip = len(code); emit(0) |
| 249 | # literal flag |
| 250 | mask = 0 |
Fredrik Lundh | 3562f11 | 2000-07-02 12:00:07 +0000 | [diff] [blame] | 251 | if prefix: |
| 252 | mask = SRE_INFO_PREFIX |
| 253 | if len(prefix) == len(pattern.data): |
| 254 | mask = mask + SRE_INFO_LITERAL |
| 255 | elif charset: |
| 256 | mask = mask + SRE_INFO_CHARSET |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 257 | emit(mask) |
| 258 | # pattern length |
Fredrik Lundh | 3562f11 | 2000-07-02 12:00:07 +0000 | [diff] [blame] | 259 | if lo < MAXCODE: |
| 260 | emit(lo) |
| 261 | else: |
| 262 | emit(MAXCODE) |
| 263 | prefix = prefix[:MAXCODE] |
| 264 | if hi < MAXCODE: |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 265 | emit(hi) |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 266 | else: |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 267 | emit(0) |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 268 | # add literal prefix |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 269 | if prefix: |
Fredrik Lundh | 3562f11 | 2000-07-02 12:00:07 +0000 | [diff] [blame] | 270 | emit(len(prefix)) |
| 271 | if prefix: |
| 272 | code.extend(prefix) |
| 273 | # generate overlap table |
| 274 | table = [-1] + ([0]*len(prefix)) |
| 275 | for i in range(len(prefix)): |
| 276 | table[i+1] = table[i]+1 |
| 277 | while table[i+1] > 0 and prefix[i] != prefix[table[i+1]-1]: |
| 278 | table[i+1] = table[table[i+1]-1]+1 |
| 279 | code.extend(table[1:]) # don't store first entry |
| 280 | elif charset: |
| 281 | for char in charset: |
| 282 | emit(OPCODES[LITERAL]) |
| 283 | emit(char) |
| 284 | emit(OPCODES[FAILURE]) |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 285 | code[skip] = len(code) - skip |
| 286 | |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 287 | def compile(p, flags=0): |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame] | 288 | # internal: convert pattern list to internal format |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 289 | |
| 290 | # compile, as necessary |
Guido van Rossum | b81e70e | 2000-04-10 17:10:48 +0000 | [diff] [blame] | 291 | if type(p) in (type(""), type(u"")): |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 292 | import sre_parse |
| 293 | pattern = p |
Fredrik Lundh | 55a4f4a | 2000-06-30 22:37:31 +0000 | [diff] [blame] | 294 | p = sre_parse.parse(p, flags) |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 295 | else: |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 296 | pattern = None |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 297 | |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 298 | flags = p.pattern.flags | flags |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame] | 299 | code = [] |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 300 | |
| 301 | # compile info block |
| 302 | _compile_info(code, p, flags) |
| 303 | |
| 304 | # compile the pattern |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 305 | _compile(code, p.data, flags) |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 306 | |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 307 | code.append(OPCODES[SUCCESS]) |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 308 | |
| 309 | # FIXME: <fl> get rid of this limitation! |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame] | 310 | assert p.pattern.groups <= 100,\ |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 311 | "sorry, but this version only supports 100 named groups" |
Fredrik Lundh | 29c08be | 2000-06-29 23:33:12 +0000 | [diff] [blame] | 312 | |
Fredrik Lundh | c230173 | 2000-07-02 22:25:39 +0000 | [diff] [blame] | 313 | # map in either direction |
| 314 | groupindex = p.pattern.groupdict |
| 315 | indexgroup = [None] * p.pattern.groups |
| 316 | for k, i in groupindex.items(): |
| 317 | indexgroup[i] = k |
| 318 | |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 319 | return _sre.compile( |
Fredrik Lundh | 6f01398 | 2000-07-03 18:44:21 +0000 | [diff] [blame] | 320 | pattern, flags, code, |
| 321 | p.pattern.groups-1, |
| 322 | groupindex, indexgroup |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 323 | ) |