1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 import string, sys
18
19 from msre_constants import *
20 import re
21
22 SPECIAL_CHARS = ".\\[{()*+?^$|"
23 REPEAT_CHARS = "*+?{"
24
25 DIGITS = tuple("0123456789")
26
27 OCTDIGITS = tuple("01234567")
28 HEXDIGITS = tuple("0123456789abcdefABCDEF")
29
30 WHITESPACE = tuple(" \t\n\r\v\f")
31
32 ESCAPES = {
33 r"\a": (LITERAL, ord("\a")),
34 r"\b": (LITERAL, ord("\b")),
35 r"\f": (LITERAL, ord("\f")),
36 r"\n": (LITERAL, ord("\n")),
37 r"\r": (LITERAL, ord("\r")),
38 r"\R": (IN, [(CATEGORY, CATEGORY_NEWLINE)]),
39 r"\t": (LITERAL, ord("\t")),
40 r"\v": (LITERAL, ord("\v")),
41 r"\\": (LITERAL, ord("\\"))
42 }
43
44 CATEGORIES = {
45 r"\A": (AT, AT_BEGINNING_STRING),
46 r"\b": (AT, AT_BOUNDARY),
47 r"\B": (AT, AT_NON_BOUNDARY),
48 r"\d": (IN, [(CATEGORY, CATEGORY_DIGIT)]),
49 r"\D": (IN, [(CATEGORY, CATEGORY_NOT_DIGIT)]),
50 r"\R": (NEWLINE, None),
51 r"\s": (IN, [(CATEGORY, CATEGORY_SPACE)]),
52 r"\S": (IN, [(CATEGORY, CATEGORY_NOT_SPACE)]),
53 r"\w": (IN, [(CATEGORY, CATEGORY_WORD)]),
54 r"\W": (IN, [(CATEGORY, CATEGORY_NOT_WORD)]),
55 r"\Z": (AT, AT_END_STRING),
56 }
57
58 FLAGS = {
59
60 "i": SRE_FLAG_IGNORECASE,
61 "L": SRE_FLAG_LOCALE,
62 "m": SRE_FLAG_MULTILINE,
63 "s": SRE_FLAG_DOTALL,
64 "x": SRE_FLAG_VERBOSE,
65
66 "t": SRE_FLAG_TEMPLATE,
67 "u": SRE_FLAG_UNICODE,
68 }
69
70
71 try:
72 int("10", 8)
73 atoi = int
74 except TypeError:
75 atoi = string.atoi
76
78
80 self.flags = 0
81 self.open = []
82 self.groups = 1
83 self.groupdict = {}
94 return gid < self.groups and gid not in self.open
95
97
104 - def dump(self, level=0):
105 nl = 1
106 for op, av in self.data:
107 print level*" " + op,; nl = 0
108 if op == "in":
109
110 print; nl = 1
111 for op, a in av:
112 print (level+1)*" " + op, a
113 elif op == "branch":
114 print; nl = 1
115 i = 0
116 for a in av[1]:
117 if i > 0:
118 print level*" " + "or"
119 a.dump(level+1); nl = 1
120 i = i + 1
121 elif type(av) in (type(()), type([])):
122 for a in av:
123 if isinstance(a, SubPattern):
124 if not nl: print
125 a.dump(level+1); nl = 1
126 else:
127 print a, ; nl = 0
128 else:
129 print av, ; nl = 0
130 if not nl: print
132 return repr(self.data)
134 return len(self.data)
143 - def insert(self, index, code):
148
149 if self.width:
150 return self.width
151 lo = hi = 0L
152 for op, av in self.data:
153 if op is BRANCH:
154 i = sys.maxint
155 j = 0
156 for av in av[1]:
157 l, h = av.getwidth()
158 i = min(i, l)
159 j = max(j, h)
160 lo = lo + i
161 hi = hi + j
162 elif op is CALL:
163 i, j = av.getwidth()
164 lo = lo + i
165 hi = hi + j
166 elif op is SUBPATTERN:
167 i, j = av[1].getwidth()
168 lo = lo + i
169 hi = hi + j
170 elif op in (MIN_REPEAT, MAX_REPEAT):
171 i, j = av[2].getwidth()
172 lo = lo + long(i) * av[0]
173 hi = hi + long(j) * av[1]
174 elif op in (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY):
175 lo = lo + 1
176 hi = hi + 1
177 elif op == SUCCESS:
178 break
179 self.width = int(min(lo, sys.maxint)), int(min(hi, sys.maxint))
180 return self.width
181
184 self.string = string
185 self.index = 0
186 self.__next()
188 if self.index >= len(self.string):
189 self.next = None
190 return
191 char = self.string[self.index]
192 if char[0] == "\\":
193 try:
194 c = self.string[self.index + 1]
195 except IndexError:
196 raise error, "bogus escape"
197 char = char + c
198 self.index = self.index + len(char)
199 self.next = char
200 - def match(self, char, skip=1):
201 if char == self.next:
202 if skip:
203 self.__next()
204 return 1
205 return 0
207 this = self.next
208 self.__next()
209 return this
212 - def seek(self, index):
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
231 return "a" <= char <= "z" or "A" <= char <= "Z" or char in "_:"
232
233
235 return "a" <= char <= "z" or "A" <= char <= "Z" or \
236 "0" <= char <= "9" or char in "._:-"
237
238
249
250
251
252 _name_with_attr_pattern = re.compile(r"""
253 [a-zA-Z_:] # first character of the tag
254 [-a-zA-Z0-9._:]* # rest of the tag
255 (\? # optional attrs flagged with '?'
256 (
257 ([-a-zA-Z0-9._]|(%[0-9A-Fa-f]{2}))+ # name can contain % escapes
258 = # '=' flags value
259 ([-a-zA-Z0-9._]|(%[0-9A-Fa-f]{2}))* # value can contain % escapes
260 (& # flag for additional args
261 ([-a-zA-Z0-9._]|(%[0-9A-Fa-f]{2}))+ # name
262 = # '='
263 ([-a-zA-Z0-9._]|(%[0-9A-Fa-f]{2}))* # value
264 )* # 0 or more add'l args
265 )? # can have nothing after the '?'
266 )? # attrs are optional
267 $ # must get full string
268 """, re.X)
269
276
277
278
279
281
282 try:
283 gid = atoi(escape[1:])
284 if gid and gid < groups:
285 return gid
286 except ValueError:
287 pass
288 return None
289
318
319 -def _escape(source, escape, state):
320
321 code = CATEGORIES.get(escape)
322 if code:
323 return code
324 code = ESCAPES.get(escape)
325 if code:
326 return code
327 try:
328 if escape[1:2] == "x":
329
330 while source.next in HEXDIGITS and len(escape) < 4:
331 escape = escape + source.get()
332 if len(escape) != 4:
333 raise ValueError
334 return LITERAL, atoi(escape[2:], 16) & 0xff
335 elif escape[1:2] == "0":
336
337 while source.next in OCTDIGITS and len(escape) < 4:
338 escape = escape + source.get()
339 return LITERAL, atoi(escape[1:], 8) & 0xff
340 elif escape[1:2] in DIGITS:
341
342 here = source.tell()
343 if source.next in DIGITS:
344 escape = escape + source.get()
345 if (escape[1] in OCTDIGITS and escape[2] in OCTDIGITS and
346 source.next in OCTDIGITS):
347
348 escape = escape + source.get()
349 return LITERAL, atoi(escape[1:], 8) & 0xff
350
351 group = _group(escape, state.groups)
352 if group:
353 if not state.checkgroup(group):
354 raise error, "cannot refer to open group"
355 return GROUPREF, group
356 raise ValueError
357 if len(escape) == 2:
358 return LITERAL, ord(escape[1])
359 except ValueError:
360 pass
361 raise error, "bogus escape: %s" % repr(escape)
362
417
419
420
421 subpattern = SubPattern(state)
422
423 while 1:
424
425 if source.next in ("|", ")"):
426 break
427 this = source.get()
428 if this is None:
429 break
430
431 if state.flags & SRE_FLAG_VERBOSE:
432
433 if this in WHITESPACE:
434 continue
435 if this == "#":
436 while 1:
437 this = source.get()
438 if this in (None, "\n"):
439 break
440 continue
441
442 if this and this[0] not in SPECIAL_CHARS:
443 subpattern.append((LITERAL, ord(this)))
444
445 elif this == "[":
446
447 set = []
448
449
450 if source.match("^"):
451 set.append((NEGATE, None))
452
453 start = set[:]
454 while 1:
455 this = source.get()
456 if this == "]" and set != start:
457 break
458 elif this and this[0] == "\\":
459 code1 = _class_escape(source, this)
460 elif this:
461 code1 = LITERAL, ord(this)
462 else:
463 raise error, "unexpected end of regular expression"
464 if source.match("-"):
465
466 this = source.get()
467 if this == "]":
468 if code1[0] is IN:
469 code1 = code1[1][0]
470 set.append(code1)
471 set.append((LITERAL, ord("-")))
472 break
473 else:
474 if this[0] == "\\":
475 code2 = _class_escape(source, this)
476 else:
477 code2 = LITERAL, ord(this)
478 if code1[0] != LITERAL or code2[0] != LITERAL:
479 raise error, "bad character range"
480 lo = code1[1]
481 hi = code2[1]
482 if hi < lo:
483 raise error, "bad character range"
484 set.append((RANGE, (lo, hi)))
485 else:
486 if code1[0] is IN:
487 code1 = code1[1][0]
488 set.append(code1)
489
490
491 if len(set)==1 and set[0][0] is LITERAL:
492 subpattern.append(set[0])
493 elif len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL:
494 subpattern.append((NOT_LITERAL, set[1][1]))
495 else:
496
497 subpattern.append((IN, set))
498
499 elif this and this[0] in REPEAT_CHARS:
500
501 if this == "?":
502 min, max = 0, 1
503 elif this == "*":
504 min, max = 0, MAXREPEAT
505
506 elif this == "+":
507 min, max = 1, MAXREPEAT
508 elif this == "{":
509 here = source.tell()
510 min, max = 0, MAXREPEAT
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529 lo = hi = ""
530 while source.next in DIGITS or \
531 isname(lo + source.next):
532 lo = lo + source.get()
533 if source.match(","):
534 while source.next in DIGITS or \
535 isname(hi + source.next):
536 hi = hi + source.get()
537 else:
538 hi = lo
539 if not source.match("}"):
540 subpattern.append((LITERAL, ord(this)))
541 source.seek(here)
542 continue
543 if lo:
544 if is_firstchar(lo[:1]):
545 min = lo
546 else:
547 min = atoi(lo)
548 if hi:
549 if is_firstchar(hi[:1]):
550 max = hi
551 else:
552 max = atoi(hi)
553
554 if type(lo) == type(hi) == type(0):
555 if max < min:
556 raise error, "bad repeat interval"
557
558 else:
559 raise error, "not supported"
560
561 if subpattern:
562 item = subpattern[-1:]
563 else:
564 item = None
565 if not item or (len(item) == 1 and item[0][0] == AT):
566 raise error, "nothing to repeat"
567 if item[0][0] in (MIN_REPEAT, MAX_REPEAT):
568 raise error, "multiple repeat"
569 if source.match("?"):
570 subpattern[-1] = (MIN_REPEAT, (min, max, item))
571 else:
572 subpattern[-1] = (MAX_REPEAT, (min, max, item))
573
574 elif this == ".":
575 subpattern.append((ANY, None))
576
577 elif this == "(":
578 group = 1
579 name = None
580 if source.match("?"):
581 group = 0
582
583 if source.match("P"):
584
585 if source.match("<"):
586
587 name = ""
588 while 1:
589 char = source.get()
590 if char is None:
591 raise error, "unterminated name"
592 if char == ">":
593 break
594 name = name + char
595 group = 1
596 if not isname_with_attrs(name):
597 raise error, "bad character in group name"
598 elif source.match("="):
599
600 name = ""
601 while 1:
602 char = source.get()
603 if char is None:
604 raise error, "unterminated name"
605 if char == ")":
606 break
607 name = name + char
608 if not isname(name):
609 raise error, "bad character in group name"
610 gid = state.groupdict.get(name)
611 if gid is None:
612 raise error, "unknown group name"
613 subpattern.append((GROUPREF, gid))
614 continue
615 else:
616 char = source.get()
617 if char is None:
618 raise error, "unexpected end of pattern"
619 raise error, "unknown specifier: ?P%s" % char
620 elif source.match(":"):
621
622 group = 2
623 elif source.match("#"):
624
625 while 1:
626 if source.next is None or source.next == ")":
627 break
628 source.get()
629 if not source.match(")"):
630 raise error, "unbalanced parenthesis"
631 continue
632 elif source.next in ("=", "!", "<"):
633
634 char = source.get()
635 dir = 1
636 if char == "<":
637 if source.next not in ("=", "!"):
638 raise error, "syntax error"
639 dir = -1
640 char = source.get()
641 p = _parse_sub(source, state)
642 if not source.match(")"):
643 raise error, "unbalanced parenthesis"
644 if char == "=":
645 subpattern.append((ASSERT, (dir, p)))
646 else:
647 subpattern.append((ASSERT_NOT, (dir, p)))
648 continue
649 else:
650
651 if not FLAGS.has_key(source.next):
652 raise error, "unexpected end of pattern"
653 while FLAGS.has_key(source.next):
654 state.flags = state.flags | FLAGS[source.get()]
655 if group:
656
657 if group == 2:
658
659 group = None
660 else:
661 group = state.opengroup(name)
662 p = _parse_sub(source, state)
663 if not source.match(")"):
664 raise error, "unbalanced parenthesis"
665 if group is not None:
666 state.closegroup(group)
667 subpattern.append((SUBPATTERN, (group, p)))
668 else:
669 while 1:
670 char = source.get()
671 if char is None:
672 raise error, "unexpected end of pattern"
673 if char == ")":
674 break
675 raise error, "unknown extension"
676
677 elif this == "^":
678 subpattern.append((AT, AT_BEGINNING))
679
680 elif this == "$":
681 subpattern.append((AT, AT_END))
682
683 elif this and this[0] == "\\":
684 code = _escape(source, this, state)
685 subpattern.append(code)
686
687 else:
688 raise error, "parser error"
689
690 return subpattern
691
692 -def parse(str, flags=0, pattern=None):
719
731 sep = source[:0]
732 if type(sep) is type(""):
733 char = chr
734 else:
735 char = unichr
736 while 1:
737 this = s.get()
738 if this is None:
739 break
740 if this and this[0] == "\\":
741
742 if this == "\\g":
743 name = ""
744 if s.match("<"):
745 while 1:
746 char = s.get()
747 if char is None:
748 raise error, "unterminated group name"
749 if char == ">":
750 break
751 name = name + char
752 if not name:
753 raise error, "bad group name"
754 try:
755 index = atoi(name)
756 except ValueError:
757 if not isname(name):
758 raise error, "bad character in group name"
759 try:
760 index = pattern.groupindex[name]
761 except KeyError:
762 raise IndexError, "unknown group name"
763 a((MARK, index))
764 elif len(this) > 1 and this[1] in DIGITS:
765 code = None
766 while 1:
767 group = _group(this, pattern.groups+1)
768 if group:
769 if (s.next not in DIGITS or
770 not _group(this + s.next, pattern.groups+1)):
771 code = MARK, group
772 break
773 elif s.next in OCTDIGITS:
774 this = this + s.get()
775 else:
776 break
777 if not code:
778 this = this[1:]
779 code = LITERAL, char(atoi(this[-6:], 8) & 0xff)
780 if code[0] is LITERAL:
781 literal(code[1])
782 else:
783 a(code)
784 else:
785 try:
786 this = char(ESCAPES[this][1])
787 except KeyError:
788 pass
789 literal(this)
790 else:
791 literal(this)
792
793 i = 0
794 groups = []
795 literals = []
796 for c, s in p:
797 if c is MARK:
798 groups.append((i, s))
799 literals.append(None)
800 else:
801 literals.append(s)
802 i = i + 1
803 return groups, literals
804
806 g = match.group
807 sep = match.string[:0]
808 groups, literals = template
809 literals = literals[:]
810 try:
811 for index, group in groups:
812 literals[index] = s = g(group)
813 if s is None:
814 raise IndexError
815 except IndexError:
816 raise error, "empty group"
817 return string.join(literals, sep)
818