1 # 2 # Secret Labs' Regular Expression Engine 3 # 4 # convert re-style regular expression to sre pattern 5 # 6 # Copyright (c) 1998-2001 by Secret Labs AB. All rights reserved. 7 # 8 # See the sre.py file for information on usage and redistribution. 9 # 10 11 """Internal support module for sre""" 12 13 # XXX: show string offset and offending character for all errors 14 15 import sys 16 17 from sre_constants import * 18 19 SPECIAL_CHARS = ".\\[{()*+?^$|" 20 REPEAT_CHARS = "*+?{" 21 22 DIGITS = set("0123456789") 23 24 OCTDIGITS = set("01234567") 25 HEXDIGITS = set("0123456789abcdefABCDEF") 26 27 WHITESPACE = set(" \t\n\r\v\f") 28 29 ESCAPES = { 30 r"\a": (LITERAL, ord("\a")), 31 r"\b": (LITERAL, ord("\b")), 32 r"\f": (LITERAL, ord("\f")), 33 r"\n": (LITERAL, ord("\n")), 34 r"\r": (LITERAL, ord("\r")), 35 r"\t": (LITERAL, ord("\t")), 36 r"\v": (LITERAL, ord("\v")), 37 r"\\": (LITERAL, ord("\\")) 38 } 39 40 CATEGORIES = { 41 r"\A": (AT, AT_BEGINNING_STRING), # start of string 42 r"\b": (AT, AT_BOUNDARY), 43 r"\B": (AT, AT_NON_BOUNDARY), 44 r"\d": (IN, [(CATEGORY, CATEGORY_DIGIT)]), 45 r"\D": (IN, [(CATEGORY, CATEGORY_NOT_DIGIT)]), 46 r"\s": (IN, [(CATEGORY, CATEGORY_SPACE)]), 47 r"\S": (IN, [(CATEGORY, CATEGORY_NOT_SPACE)]), 48 r"\w": (IN, [(CATEGORY, CATEGORY_WORD)]), 49 r"\W": (IN, [(CATEGORY, CATEGORY_NOT_WORD)]), 50 r"\Z": (AT, AT_END_STRING), # end of string 51 } 52 53 FLAGS = { 54 # standard flags 55 "i": SRE_FLAG_IGNORECASE, 56 "L": SRE_FLAG_LOCALE, 57 "m": SRE_FLAG_MULTILINE, 58 "s": SRE_FLAG_DOTALL, 59 "x": SRE_FLAG_VERBOSE, 60 # extensions 61 "t": SRE_FLAG_TEMPLATE, 62 "u": SRE_FLAG_UNICODE, 63 } 64 65 class Pattern: 66 # master pattern object. keeps track of global attributes 67 def __init__(self): 68 self.flags = 0 69 self.open = [] 70 self.groups = 1 71 self.groupdict = {} 72 def opengroup(self, name=None): 73 gid = self.groups 74 self.groups = gid + 1 75 if name is not None: 76 ogid = self.groupdict.get(name, None) 77 if ogid is not None: 78 raise error, ("redefinition of group name %s as group %d; " 79 "was group %d" % (repr(name), gid, ogid)) 80 self.groupdict[name] = gid 81 self.open.append(gid) 82 return gid 83 def closegroup(self, gid): 84 self.open.remove(gid) 85 def checkgroup(self, gid): 86 return gid < self.groups and gid not in self.open 87 88 class SubPattern: 89 # a subpattern, in intermediate form 90 def __init__(self, pattern, data=None): 91 self.pattern = pattern 92 if data is None: 93 data = [] 94 self.data = data 95 self.width = None 96 def dump(self, level=0): 97 nl = 1 98 seqtypes = type(()), type([]) 99 for op, av in self.data: 100 print level*" " + op,; nl = 0 101 if op == "in": 102 # member sublanguage 103 print; nl = 1 104 for op, a in av: 105 print (level+1)*" " + op, a 106 elif op == "branch": 107 print; nl = 1 108 i = 0 109 for a in av[1]: 110 if i > 0: 111 print level*" " + "or" 112 a.dump(level+1); nl = 1 113 i = i + 1 114 elif type(av) in seqtypes: 115 for a in av: 116 if isinstance(a, SubPattern): 117 if not nl: print 118 a.dump(level+1); nl = 1 119 else: 120 print a, ; nl = 0 121 else: 122 print av, ; nl = 0 123 if not nl: print 124 def __repr__(self): 125 return repr(self.data) 126 def __len__(self): 127 return len(self.data) 128 def __delitem__(self, index): 129 del self.data[index] 130 def __getitem__(self, index): 131 if isinstance(index, slice): 132 return SubPattern(self.pattern, self.data[index]) 133 return self.data[index] 134 def __setitem__(self, index, code): 135 self.data[index] = code 136 def insert(self, index, code): 137 self.data.insert(index, code) 138 def append(self, code): 139 self.data.append(code) 140 def getwidth(self): 141 # determine the width (min, max) for this subpattern 142 if self.width: 143 return self.width 144 lo = hi = 0L 145 UNITCODES = (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY) 146 REPEATCODES = (MIN_REPEAT, MAX_REPEAT) 147 for op, av in self.data: 148 if op is BRANCH: 149 i = sys.maxint 150 j = 0 151 for av in av[1]: 152 l, h = av.getwidth() 153 i = min(i, l) 154 j = max(j, h) 155 lo = lo + i 156 hi = hi + j 157 elif op is CALL: 158 i, j = av.getwidth() 159 lo = lo + i 160 hi = hi + j 161 elif op is SUBPATTERN: 162 i, j = av[1].getwidth() 163 lo = lo + i 164 hi = hi + j 165 elif op in REPEATCODES: 166 i, j = av[2].getwidth() 167 lo = lo + long(i) * av[0] 168 hi = hi + long(j) * av[1] 169 elif op in UNITCODES: 170 lo = lo + 1 171 hi = hi + 1 172 elif op == SUCCESS: 173 break 174 self.width = int(min(lo, sys.maxint)), int(min(hi, sys.maxint)) 175 return self.width 176 177 class Tokenizer: 178 def __init__(self, string): 179 self.string = string 180 self.index = 0 181 self.__next() 182 def __next(self): 183 if self.index >= len(self.string): 184 self.next = None 185 return 186 char = self.string[self.index] 187 if char[0] == "\\": 188 try: 189 c = self.string[self.index + 1] 190 except IndexError: 191 raise error, "bogus escape (end of line)" 192 char = char + c 193 self.index = self.index + len(char) 194 self.next = char 195 def match(self, char, skip=1): 196 if char == self.next: 197 if skip: 198 self.__next() 199 return 1 200 return 0 201 def get(self): 202 this = self.next 203 self.__next() 204 return this 205 def tell(self): 206 return self.index, self.next 207 def seek(self, index): 208 self.index, self.next = index 209 210 def isident(char): 211 return "a" <= char <= "z" or "A" <= char <= "Z" or char == "_" 212 213 def isdigit(char): 214 return "0" <= char <= "9" 215 216 def isname(name): 217 # check that group name is a valid string 218 if not isident(name[0]): 219 return False 220 for char in name[1:]: 221 if not isident(char) and not isdigit(char): 222 return False 223 return True 224 225 def _class_escape(source, escape): 226 # handle escape code inside character class 227 code = ESCAPES.get(escape) 228 if code: 229 return code 230 code = CATEGORIES.get(escape) 231 if code: 232 return code 233 try: 234 c = escape[1:2] 235 if c == "x": 236 # hexadecimal escape (exactly two digits) 237 while source.next in HEXDIGITS and len(escape) < 4: 238 escape = escape + source.get() 239 escape = escape[2:] 240 if len(escape) != 2: 241 raise error, "bogus escape: %s" % repr("\\" + escape) 242 return LITERAL, int(escape, 16) & 0xff 243 elif c in OCTDIGITS: 244 # octal escape (up to three digits) 245 while source.next in OCTDIGITS and len(escape) < 4: 246 escape = escape + source.get() 247 escape = escape[1:] 248 return LITERAL, int(escape, 8) & 0xff 249 elif c in DIGITS: 250 raise error, "bogus escape: %s" % repr(escape) 251 if len(escape) == 2: 252 return LITERAL, ord(escape[1]) 253 except ValueError: 254 pass 255 raise error, "bogus escape: %s" % repr(escape) 256 257 def _escape(source, escape, state): 258 # handle escape code in expression 259 code = CATEGORIES.get(escape) 260 if code: 261 return code 262 code = ESCAPES.get(escape) 263 if code: 264 return code 265 try: 266 c = escape[1:2] 267 if c == "x": 268 # hexadecimal escape 269 while source.next in HEXDIGITS and len(escape) < 4: 270 escape = escape + source.get() 271 if len(escape) != 4: 272 raise ValueError 273 return LITERAL, int(escape[2:], 16) & 0xff 274 elif c == "0": 275 # octal escape 276 while source.next in OCTDIGITS and len(escape) < 4: 277 escape = escape + source.get() 278 return LITERAL, int(escape[1:], 8) & 0xff 279 elif c in DIGITS: 280 # octal escape *or* decimal group reference (sigh) 281 if source.next in DIGITS: 282 escape = escape + source.get() 283 if (escape[1] in OCTDIGITS and escape[2] in OCTDIGITS and 284 source.next in OCTDIGITS): 285 # got three octal digits; this is an octal escape 286 escape = escape + source.get() 287 return LITERAL, int(escape[1:], 8) & 0xff 288 # not an octal escape, so this is a group reference 289 group = int(escape[1:]) 290 if group < state.groups: 291 if not state.checkgroup(group): 292 raise error, "cannot refer to open group" 293 return GROUPREF, group 294 raise ValueError 295 if len(escape) == 2: 296 return LITERAL, ord(escape[1]) 297 except ValueError: 298 pass 299 raise error, "bogus escape: %s" % repr(escape) 300 301 def _parse_sub(source, state, nested=1): 302 # parse an alternation: a|b|c 303 304 items = [] 305 itemsappend = items.append 306 sourcematch = source.match 307 while 1: 308 itemsappend(_parse(source, state)) 309 if sourcematch("|"): 310 continue 311 if not nested: 312 break 313 if not source.next or sourcematch(")", 0): 314 break 315 else: 316 raise error, "pattern not properly closed" 317 318 if len(items) == 1: 319 return items[0] 320 321 subpattern = SubPattern(state) 322 subpatternappend = subpattern.append 323 324 # check if all items share a common prefix 325 while 1: 326 prefix = None 327 for item in items: 328 if not item: 329 break 330 if prefix is None: 331 prefix = item[0] 332 elif item[0] != prefix: 333 break 334 else: 335 # all subitems start with a common "prefix". 336 # move it out of the branch 337 for item in items: 338 del item[0] 339 subpatternappend(prefix) 340 continue # check next one 341 break 342 343 # check if the branch can be replaced by a character set 344 for item in items: 345 if len(item) != 1 or item[0][0] != LITERAL: 346 break 347 else: 348 # we can store this as a character set instead of a 349 # branch (the compiler may optimize this even more) 350 set = [] 351 setappend = set.append 352 for item in items: 353 setappend(item[0]) 354 subpatternappend((IN, set)) 355 return subpattern 356 357 subpattern.append((BRANCH, (None, items))) 358 return subpattern 359 360 def _parse_sub_cond(source, state, condgroup): 361 item_yes = _parse(source, state) 362 if source.match("|"): 363 item_no = _parse(source, state) 364 if source.match("|"): 365 raise error, "conditional backref with more than two branches" 366 else: 367 item_no = None 368 if source.next and not source.match(")", 0): 369 raise error, "pattern not properly closed" 370 subpattern = SubPattern(state) 371 subpattern.append((GROUPREF_EXISTS, (condgroup, item_yes, item_no))) 372 return subpattern 373 374 _PATTERNENDERS = set("|)") 375 _ASSERTCHARS = set("=!<") 376 _LOOKBEHINDASSERTCHARS = set("=!") 377 _REPEATCODES = set([MIN_REPEAT, MAX_REPEAT]) 378 379 def _parse(source, state): 380 # parse a simple pattern 381 subpattern = SubPattern(state) 382 383 # precompute constants into local variables 384 subpatternappend = subpattern.append 385 sourceget = source.get 386 sourcematch = source.match 387 _len = len 388 PATTERNENDERS = _PATTERNENDERS 389 ASSERTCHARS = _ASSERTCHARS 390 LOOKBEHINDASSERTCHARS = _LOOKBEHINDASSERTCHARS 391 REPEATCODES = _REPEATCODES 392 393 while 1: 394 395 if source.next in PATTERNENDERS: 396 break # end of subpattern 397 this = sourceget() 398 if this is None: 399 break # end of pattern 400 401 if state.flags & SRE_FLAG_VERBOSE: 402 # skip whitespace and comments 403 if this in WHITESPACE: 404 continue 405 if this == "#": 406 while 1: 407 this = sourceget() 408 if this in (None, "\n"): 409 break 410 continue 411 412 if this and this[0] not in SPECIAL_CHARS: 413 subpatternappend((LITERAL, ord(this))) 414 415 elif this == "[": 416 # character set 417 set = [] 418 setappend = set.append 419 ## if sourcematch(":"): 420 ## pass # handle character classes 421 if sourcematch("^"): 422 setappend((NEGATE, None)) 423 # check remaining characters 424 start = set[:] 425 while 1: 426 this = sourceget() 427 if this == "]" and set != start: 428 break 429 elif this and this[0] == "\\": 430 code1 = _class_escape(source, this) 431 elif this: 432 code1 = LITERAL, ord(this) 433 else: 434 raise error, "unexpected end of regular expression" 435 if sourcematch("-"): 436 # potential range 437 this = sourceget() 438 if this == "]": 439 if code1[0] is IN: 440 code1 = code1[1][0] 441 setappend(code1) 442 setappend((LITERAL, ord("-"))) 443 break 444 elif this: 445 if this[0] == "\\": 446 code2 = _class_escape(source, this) 447 else: 448 code2 = LITERAL, ord(this) 449 if code1[0] != LITERAL or code2[0] != LITERAL: 450 raise error, "bad character range" 451 lo = code1[1] 452 hi = code2[1] 453 if hi < lo: 454 raise error, "bad character range" 455 setappend((RANGE, (lo, hi))) 456 else: 457 raise error, "unexpected end of regular expression" 458 else: 459 if code1[0] is IN: 460 code1 = code1[1][0] 461 setappend(code1) 462 463 # XXX: <fl> should move set optimization to compiler! 464 if _len(set)==1 and set[0][0] is LITERAL: 465 subpatternappend(set[0]) # optimization 466 elif _len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL: 467 subpatternappend((NOT_LITERAL, set[1][1])) # optimization 468 else: 469 # XXX: <fl> should add charmap optimization here 470 subpatternappend((IN, set)) 471 472 elif this and this[0] in REPEAT_CHARS: 473 # repeat previous item 474 if this == "?": 475 min, max = 0, 1 476 elif this == "*": 477 min, max = 0, MAXREPEAT 478 479 elif this == "+": 480 min, max = 1, MAXREPEAT 481 elif this == "{": 482 if source.next == "}": 483 subpatternappend((LITERAL, ord(this))) 484 continue 485 here = source.tell() 486 min, max = 0, MAXREPEAT 487 lo = hi = "" 488 while source.next in DIGITS: 489 lo = lo + source.get() 490 if sourcematch(","): 491 while source.next in DIGITS: 492 hi = hi + sourceget() 493 else: 494 hi = lo 495 if not sourcematch("}"): 496 subpatternappend((LITERAL, ord(this))) 497 source.seek(here) 498 continue 499 if lo: 500 min = int(lo) 501 if hi: 502 max = int(hi) 503 if max < min: 504 raise error, "bad repeat interval" 505 else: 506 raise error, "not supported" 507 # figure out which item to repeat 508 if subpattern: 509 item = subpattern[-1:] 510 else: 511 item = None 512 if not item or (_len(item) == 1 and item[0][0] == AT): 513 raise error, "nothing to repeat" 514 if item[0][0] in REPEATCODES: 515 raise error, "multiple repeat" 516 if sourcematch("?"): 517 subpattern[-1] = (MIN_REPEAT, (min, max, item)) 518 else: 519 subpattern[-1] = (MAX_REPEAT, (min, max, item)) 520 521 elif this == ".": 522 subpatternappend((ANY, None)) 523 524 elif this == "(": 525 group = 1 526 name = None 527 condgroup = None 528 if sourcematch("?"): 529 group = 0 530 # options 531 if sourcematch("P"): 532 # python extensions 533 if sourcematch("<"): 534 # named group: skip forward to end of name 535 name = "" 536 while 1: 537 char = sourceget() 538 if char is None: 539 raise error, "unterminated name" 540 if char == ">": 541 break 542 name = name + char 543 group = 1 544 if not isname(name): 545 raise error, "bad character in group name" 546 elif sourcematch("="): 547 # named backreference 548 name = "" 549 while 1: 550 char = sourceget() 551 if char is None: 552 raise error, "unterminated name" 553 if char == ")": 554 break 555 name = name + char 556 if not isname(name): 557 raise error, "bad character in group name" 558 gid = state.groupdict.get(name) 559 if gid is None: 560 raise error, "unknown group name" 561 subpatternappend((GROUPREF, gid)) 562 continue 563 else: 564 char = sourceget() 565 if char is None: 566 raise error, "unexpected end of pattern" 567 raise error, "unknown specifier: ?P%s" % char 568 elif sourcematch(":"): 569 # non-capturing group 570 group = 2 571 elif sourcematch("#"): 572 # comment 573 while 1: 574 if source.next is None or source.next == ")": 575 break 576 sourceget() 577 if not sourcematch(")"): 578 raise error, "unbalanced parenthesis" 579 continue 580 elif source.next in ASSERTCHARS: 581 # lookahead assertions 582 char = sourceget() 583 dir = 1 584 if char == "<": 585 if source.next not in LOOKBEHINDASSERTCHARS: 586 raise error, "syntax error" 587 dir = -1 # lookbehind 588 char = sourceget() 589 p = _parse_sub(source, state) 590 if not sourcematch(")"): 591 raise error, "unbalanced parenthesis" 592 if char == "=": 593 subpatternappend((ASSERT, (dir, p))) 594 else: 595 subpatternappend((ASSERT_NOT, (dir, p))) 596 continue 597 elif sourcematch("("): 598 # conditional backreference group 599 condname = "" 600 while 1: 601 char = sourceget() 602 if char is None: 603 raise error, "unterminated name" 604 if char == ")": 605 break 606 condname = condname + char 607 group = 2 608 if isname(condname): 609 condgroup = state.groupdict.get(condname) 610 if condgroup is None: 611 raise error, "unknown group name" 612 else: 613 try: 614 condgroup = int(condname) 615 except ValueError: 616 raise error, "bad character in group name" 617 else: 618 # flags 619 if not source.next in FLAGS: 620 raise error, "unexpected end of pattern" 621 while source.next in FLAGS: 622 state.flags = state.flags | FLAGS[sourceget()] 623 if group: 624 # parse group contents 625 if group == 2: 626 # anonymous group 627 group = None 628 else: 629 group = state.opengroup(name) 630 if condgroup: 631 p = _parse_sub_cond(source, state, condgroup) 632 else: 633 p = _parse_sub(source, state) 634 if not sourcematch(")"): 635 raise error, "unbalanced parenthesis" 636 if group is not None: 637 state.closegroup(group) 638 subpatternappend((SUBPATTERN, (group, p))) 639 else: 640 while 1: 641 char = sourceget() 642 if char is None: 643 raise error, "unexpected end of pattern" 644 if char == ")": 645 break 646 raise error, "unknown extension" 647 648 elif this == "^": 649 subpatternappend((AT, AT_BEGINNING)) 650 651 elif this == "$": 652 subpattern.append((AT, AT_END)) 653 654 elif this and this[0] == "\\": 655 code = _escape(source, this, state) 656 subpatternappend(code) 657 658 else: 659 raise error, "parser error" 660 661 return subpattern 662 663 def parse(str, flags=0, pattern=None): 664 # parse 're' pattern into list of (opcode, argument) tuples 665 666 source = Tokenizer(str) 667 668 if pattern is None: 669 pattern = Pattern() 670 pattern.flags = flags 671 pattern.str = str 672 673 p = _parse_sub(source, pattern, 0) 674 675 tail = source.get() 676 if tail == ")": 677 raise error, "unbalanced parenthesis" 678 elif tail: 679 raise error, "bogus characters at end of regular expression" 680 681 if flags & SRE_FLAG_DEBUG: 682 p.dump() 683 684 if not (flags & SRE_FLAG_VERBOSE) and p.pattern.flags & SRE_FLAG_VERBOSE: 685 # the VERBOSE flag was switched on inside the pattern. to be 686 # on the safe side, we'll parse the whole thing again... 687 return parse(str, p.pattern.flags) 688 689 return p 690 691 def parse_template(source, pattern): 692 # parse 're' replacement string into list of literals and 693 # group references 694 s = Tokenizer(source) 695 sget = s.get 696 p = [] 697 a = p.append 698 def literal(literal, p=p, pappend=a): 699 if p and p[-1][0] is LITERAL: 700 p[-1] = LITERAL, p[-1][1] + literal 701 else: 702 pappend((LITERAL, literal)) 703 sep = source[:0] 704 if type(sep) is type(""): 705 makechar = chr 706 else: 707 makechar = unichr 708 while 1: 709 this = sget() 710 if this is None: 711 break # end of replacement string 712 if this and this[0] == "\\": 713 # group 714 c = this[1:2] 715 if c == "g": 716 name = "" 717 if s.match("<"): 718 while 1: 719 char = sget() 720 if char is None: 721 raise error, "unterminated group name" 722 if char == ">": 723 break 724 name = name + char 725 if not name: 726 raise error, "bad group name" 727 try: 728 index = int(name) 729 if index < 0: 730 raise error, "negative group number" 731 except ValueError: 732 if not isname(name): 733 raise error, "bad character in group name" 734 try: 735 index = pattern.groupindex[name] 736 except KeyError: 737 raise IndexError, "unknown group name" 738 a((MARK, index)) 739 elif c == "0": 740 if s.next in OCTDIGITS: 741 this = this + sget() 742 if s.next in OCTDIGITS: 743 this = this + sget() 744 literal(makechar(int(this[1:], 8) & 0xff)) 745 elif c in DIGITS: 746 isoctal = False 747 if s.next in DIGITS: 748 this = this + sget() 749 if (c in OCTDIGITS and this[2] in OCTDIGITS and 750 s.next in OCTDIGITS): 751 this = this + sget() 752 isoctal = True 753 literal(makechar(int(this[1:], 8) & 0xff)) 754 if not isoctal: 755 a((MARK, int(this[1:]))) 756 else: 757 try: 758 this = makechar(ESCAPES[this][1]) 759 except KeyError: 760 pass 761 literal(this) 762 else: 763 literal(this) 764 # convert template to groups and literals lists 765 i = 0 766 groups = [] 767 groupsappend = groups.append 768 literals = [None] * len(p) 769 for c, s in p: 770 if c is MARK: 771 groupsappend((i, s)) 772 # literal[i] is already None 773 else: 774 literals[i] = s 775 i = i + 1 776 return groups, literals 777 778 def expand_template(template, match): 779 g = match.group 780 sep = match.string[:0] 781 groups, literals = template 782 literals = literals[:] 783 try: 784 for index, group in groups: 785 literals[index] = s = g(group) 786 if s is None: 787 raise error, "unmatched group" 788 except IndexError: 789 raise error, "invalid group reference" 790 return sep.join(literals) 791
