Debian Codegraph @

Lib/re/_parser.py

raw
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 __init__.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 from ._constants import *
16
17 SPECIAL_CHARS = ".\\[{()*+?^$|"
18 REPEAT_CHARS = "*+?{"
19
20 DIGITS = frozenset("0123456789")
21
22 OCTDIGITS = frozenset("01234567")
23 HEXDIGITS = frozenset("0123456789abcdefABCDEF")
24 ASCIILETTERS = frozenset("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
25
26 WHITESPACE = frozenset(" \t\n\r\v\f")
27
28 _REPEATCODES = frozenset({MIN_REPEAT, MAX_REPEAT, POSSESSIVE_REPEAT})
29 _UNITCODES = frozenset({ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY})
30
31 ESCAPES = {
32 r"\a": (LITERAL, ord("\a")),
33 r"\b": (LITERAL, ord("\b")),
34 r"\f": (LITERAL, ord("\f")),
35 r"\n": (LITERAL, ord("\n")),
36 r"\r": (LITERAL, ord("\r")),
37 r"\t": (LITERAL, ord("\t")),
38 r"\v": (LITERAL, ord("\v")),
39 r"\\": (LITERAL, ord("\\"))
40 }
41
42 CATEGORIES = {
43 r"\A": (AT, AT_BEGINNING_STRING), # start of string
44 r"\b": (AT, AT_BOUNDARY),
45 r"\B": (AT, AT_NON_BOUNDARY),
46 r"\d": (IN, [(CATEGORY, CATEGORY_DIGIT)]),
47 r"\D": (IN, [(CATEGORY, CATEGORY_NOT_DIGIT)]),
48 r"\s": (IN, [(CATEGORY, CATEGORY_SPACE)]),
49 r"\S": (IN, [(CATEGORY, CATEGORY_NOT_SPACE)]),
50 r"\w": (IN, [(CATEGORY, CATEGORY_WORD)]),
51 r"\W": (IN, [(CATEGORY, CATEGORY_NOT_WORD)]),
52 r"\z": (AT, AT_END_STRING), # end of string
53 r"\Z": (AT, AT_END_STRING), # end of string (obsolete)
54 }
55
56 FLAGS = {
57 # standard flags
58 "i": SRE_FLAG_IGNORECASE,
59 "L": SRE_FLAG_LOCALE,
60 "m": SRE_FLAG_MULTILINE,
61 "s": SRE_FLAG_DOTALL,
62 "x": SRE_FLAG_VERBOSE,
63 # extensions
64 "a": SRE_FLAG_ASCII,
65 "u": SRE_FLAG_UNICODE,
66 }
67
68 TYPE_FLAGS = SRE_FLAG_ASCII | SRE_FLAG_LOCALE | SRE_FLAG_UNICODE
69 GLOBAL_FLAGS = SRE_FLAG_DEBUG
70
71 # Maximal value returned by SubPattern.getwidth().
72 # Must be larger than MAXREPEAT, MAXCODE and sys.maxsize.
73 MAXWIDTH = 1 << 64
74
75 class State:
76 # keeps track of state for parsing
77 def __init__(self):
78 self.flags = 0
79 self.groupdict = {}
80 self.groupwidths = [None] # group 0
81 self.lookbehindgroups = None
82 self.grouprefpos = {}
83 @property
84 def groups(self):
85 return len(self.groupwidths)
86 def opengroup(self, name=None):
87 gid = self.groups
88 self.groupwidths.append(None)
89 if self.groups > MAXGROUPS:
90 raise error("too many groups")
91 if name is not None:
92 ogid = self.groupdict.get(name, None)
93 if ogid is not None:
94 raise error("redefinition of group name %r as group %d; "
95 "was group %d" % (name, gid, ogid))
96 self.groupdict[name] = gid
97 return gid
98 def closegroup(self, gid, p):
99 self.groupwidths[gid] = p.getwidth()
100 def checkgroup(self, gid):
101 return gid < self.groups and self.groupwidths[gid] is not None
102
103 def checklookbehindgroup(self, gid, source):
104 if self.lookbehindgroups is not None:
105 if not self.checkgroup(gid):
106 raise source.error('cannot refer to an open group')
107 if gid >= self.lookbehindgroups:
108 raise source.error('cannot refer to group defined in the same '
109 'lookbehind subpattern')
110
111 class SubPattern:
112 # a subpattern, in intermediate form
113 def __init__(self, state, data=None):
114 self.state = state
115 if data is None:
116 data = []
117 self.data = data
118 self.width = None
119
120 def dump(self, level=0):
121 seqtypes = (tuple, list)
122 for op, av in self.data:
123 print(level*" " + str(op), end='')
124 if op is IN:
125 # member sublanguage
126 print()
127 for op, a in av:
128 print((level+1)*" " + str(op), a)
129 elif op is BRANCH:
130 print()
131 for i, a in enumerate(av[1]):
132 if i:
133 print(level*" " + "OR")
134 a.dump(level+1)
135 elif op is GROUPREF_EXISTS:
136 condgroup, item_yes, item_no = av
137 print('', condgroup)
138 item_yes.dump(level+1)
139 if item_no:
140 print(level*" " + "ELSE")
141 item_no.dump(level+1)
142 elif isinstance(av, SubPattern):
143 print()
144 av.dump(level+1)
145 elif isinstance(av, seqtypes):
146 nl = False
147 for a in av:
148 if isinstance(a, SubPattern):
149 if not nl:
150 print()
151 a.dump(level+1)
152 nl = True
153 else:
154 if not nl:
155 print(' ', end='')
156 print(a, end='')
157 nl = False
158 if not nl:
159 print()
160 else:
161 print('', av)
162 def __repr__(self):
163 return repr(self.data)
164 def __len__(self):
165 return len(self.data)
166 def __delitem__(self, index):
167 del self.data[index]
168 def __getitem__(self, index):
169 if isinstance(index, slice):
170 return SubPattern(self.state, self.data[index])
171 return self.data[index]
172 def __setitem__(self, index, code):
173 self.data[index] = code
174 def insert(self, index, code):
175 self.data.insert(index, code)
176 def append(self, code):
177 self.data.append(code)
178 def getwidth(self):
179 # determine the width (min, max) for this subpattern
180 if self.width is not None:
181 return self.width
182 lo = hi = 0
183 for op, av in self.data:
184 if op is BRANCH:
185 i = MAXWIDTH
186 j = 0
187 for av in av[1]:
188 l, h = av.getwidth()
189 i = min(i, l)
190 j = max(j, h)
191 lo = lo + i
192 hi = hi + j
193 elif op is ATOMIC_GROUP:
194 i, j = av.getwidth()
195 lo = lo + i
196 hi = hi + j
197 elif op is SUBPATTERN:
198 i, j = av[-1].getwidth()
199 lo = lo + i
200 hi = hi + j
201 elif op in _REPEATCODES:
202 i, j = av[2].getwidth()
203 lo = lo + i * av[0]
204 if av[1] == MAXREPEAT and j:
205 hi = MAXWIDTH
206 else:
207 hi = hi + j * av[1]
208 elif op in _UNITCODES:
209 lo = lo + 1
210 hi = hi + 1
211 elif op is GROUPREF:
212 i, j = self.state.groupwidths[av]
213 lo = lo + i
214 hi = hi + j
215 elif op is GROUPREF_EXISTS:
216 i, j = av[1].getwidth()
217 if av[2] is not None:
218 l, h = av[2].getwidth()
219 i = min(i, l)
220 j = max(j, h)
221 else:
222 i = 0
223 lo = lo + i
224 hi = hi + j
225 elif op is SUCCESS:
226 break
227 self.width = min(lo, MAXWIDTH), min(hi, MAXWIDTH)
228 return self.width
229
230 class Tokenizer:
231 def __init__(self, string):
232 self.istext = isinstance(string, str)
233 self.string = string
234 if not self.istext:
235 string = str(string, 'latin1')
236 self.decoded_string = string
237 self.index = 0
238 self.next = None
239 self.__next()
240 def __next(self):
241 index = self.index
242 try:
243 char = self.decoded_string[index]
244 except IndexError:
245 self.next = None
246 return
247 if char == "\\":
248 index += 1
249 try:
250 char += self.decoded_string[index]
251 except IndexError:
252 raise error("bad escape (end of pattern)",
253 self.string, len(self.string) - 1) from None
254 self.index = index + 1
255 self.next = char
256 def match(self, char):
257 if char == self.next:
258 self.__next()
259 return True
260 return False
261 def get(self):
262 this = self.next
263 self.__next()
264 return this
265 def getwhile(self, n, charset):
266 result = ''
267 for _ in range(n):
268 c = self.next
269 if c not in charset:
270 break
271 result += c
272 self.__next()
273 return result
274 def getuntil(self, terminator, name):
275 result = ''
276 while True:
277 c = self.next
278 self.__next()
279 if c is None:
280 if not result:
281 raise self.error("missing " + name)
282 raise self.error("missing %s, unterminated name" % terminator,
283 len(result))
284 if c == terminator:
285 if not result:
286 raise self.error("missing " + name, 1)
287 break
288 result += c
289 return result
290 @property
291 def pos(self):
292 return self.index - len(self.next or '')
293 def tell(self):
294 return self.index - len(self.next or '')
295 def seek(self, index):
296 self.index = index
297 self.__next()
298
299 def error(self, msg, offset=0):
300 if not self.istext:
301 msg = msg.encode('ascii', 'backslashreplace').decode('ascii')
302 return error(msg, self.string, self.tell() - offset)
303
304 def checkgroupname(self, name, offset):
305 if not (self.istext or name.isascii()):
306 msg = "bad character in group name %a" % name
307 raise self.error(msg, len(name) + offset)
308 if not name.isidentifier():
309 msg = "bad character in group name %r" % name
310 raise self.error(msg, len(name) + offset)
311
312 def _class_escape(source, escape):
313 # handle escape code inside character class
314 code = ESCAPES.get(escape)
315 if code:
316 return code
317 code = CATEGORIES.get(escape)
318 if code and code[0] is IN:
319 return code
320 try:
321 c = escape[1:2]
322 if c == "x":
323 # hexadecimal escape (exactly two digits)
324 escape += source.getwhile(2, HEXDIGITS)
325 if len(escape) != 4:
326 raise source.error("incomplete escape %s" % escape, len(escape))
327 return LITERAL, int(escape[2:], 16)
328 elif c == "u" and source.istext:
329 # unicode escape (exactly four digits)
330 escape += source.getwhile(4, HEXDIGITS)
331 if len(escape) != 6:
332 raise source.error("incomplete escape %s" % escape, len(escape))
333 return LITERAL, int(escape[2:], 16)
334 elif c == "U" and source.istext:
335 # unicode escape (exactly eight digits)
336 escape += source.getwhile(8, HEXDIGITS)
337 if len(escape) != 10:
338 raise source.error("incomplete escape %s" % escape, len(escape))
339 c = int(escape[2:], 16)
340 chr(c) # raise ValueError for invalid code
341 return LITERAL, c
342 elif c == "N" and source.istext:
343 import unicodedata
344 # named unicode escape e.g. \N{EM DASH}
345 if not source.match('{'):
346 raise source.error("missing {")
347 charname = source.getuntil('}', 'character name')
348 try:
349 c = ord(unicodedata.lookup(charname))
350 except (KeyError, TypeError):
351 raise source.error("undefined character name %r" % charname,
352 len(charname) + len(r'\N{}')) from None
353 return LITERAL, c
354 elif c in OCTDIGITS:
355 # octal escape (up to three digits)
356 escape += source.getwhile(2, OCTDIGITS)
357 c = int(escape[1:], 8)
358 if c > 0o377:
359 raise source.error('octal escape value %s outside of '
360 'range 0-0o377' % escape, len(escape))
361 return LITERAL, c
362 elif c in DIGITS:
363 raise ValueError
364 if len(escape) == 2:
365 if c in ASCIILETTERS:
366 raise source.error('bad escape %s' % escape, len(escape))
367 return LITERAL, ord(escape[1])
368 except ValueError:
369 pass
370 raise source.error("bad escape %s" % escape, len(escape))
371
372 def _escape(source, escape, state):
373 # handle escape code in expression
374 code = CATEGORIES.get(escape)
375 if code:
376 return code
377 code = ESCAPES.get(escape)
378 if code:
379 return code
380 try:
381 c = escape[1:2]
382 if c == "x":
383 # hexadecimal escape
384 escape += source.getwhile(2, HEXDIGITS)
385 if len(escape) != 4:
386 raise source.error("incomplete escape %s" % escape, len(escape))
387 return LITERAL, int(escape[2:], 16)
388 elif c == "u" and source.istext:
389 # unicode escape (exactly four digits)
390 escape += source.getwhile(4, HEXDIGITS)
391 if len(escape) != 6:
392 raise source.error("incomplete escape %s" % escape, len(escape))
393 return LITERAL, int(escape[2:], 16)
394 elif c == "U" and source.istext:
395 # unicode escape (exactly eight digits)
396 escape += source.getwhile(8, HEXDIGITS)
397 if len(escape) != 10:
398 raise source.error("incomplete escape %s" % escape, len(escape))
399 c = int(escape[2:], 16)
400 chr(c) # raise ValueError for invalid code
401 return LITERAL, c
402 elif c == "N" and source.istext:
403 import unicodedata
404 # named unicode escape e.g. \N{EM DASH}
405 if not source.match('{'):
406 raise source.error("missing {")
407 charname = source.getuntil('}', 'character name')
408 try:
409 c = ord(unicodedata.lookup(charname))
410 except (KeyError, TypeError):
411 raise source.error("undefined character name %r" % charname,
412 len(charname) + len(r'\N{}')) from None
413 return LITERAL, c
414 elif c == "0":
415 # octal escape
416 escape += source.getwhile(2, OCTDIGITS)
417 return LITERAL, int(escape[1:], 8)
418 elif c in DIGITS:
419 # octal escape *or* decimal group reference (sigh)
420 if source.next in DIGITS:
421 escape += source.get()
422 if (escape[1] in OCTDIGITS and escape[2] in OCTDIGITS and
423 source.next in OCTDIGITS):
424 # got three octal digits; this is an octal escape
425 escape += source.get()
426 c = int(escape[1:], 8)
427 if c > 0o377:
428 raise source.error('octal escape value %s outside of '
429 'range 0-0o377' % escape,
430 len(escape))
431 return LITERAL, c
432 # not an octal escape, so this is a group reference
433 group = int(escape[1:])
434 if group < state.groups:
435 if not state.checkgroup(group):
436 raise source.error("cannot refer to an open group",
437 len(escape))
438 state.checklookbehindgroup(group, source)
439 return GROUPREF, group
440 raise source.error("invalid group reference %d" % group, len(escape) - 1)
441 if len(escape) == 2:
442 if c in ASCIILETTERS:
443 raise source.error("bad escape %s" % escape, len(escape))
444 return LITERAL, ord(escape[1])
445 except ValueError:
446 pass
447 raise source.error("bad escape %s" % escape, len(escape))
448
449 def _uniq(items):
450 return list(dict.fromkeys(items))
451
452 def _parse_sub(source, state, verbose, nested):
453 # parse an alternation: a|b|c
454
455 items = []
456 itemsappend = items.append
457 sourcematch = source.match
458 start = source.tell()
459 while True:
460 itemsappend(_parse(source, state, verbose, nested + 1,
461 not nested and not items))
462 if not sourcematch("|"):
463 break
464 if not nested:
465 verbose = state.flags & SRE_FLAG_VERBOSE
466
467 if len(items) == 1:
468 return items[0]
469
470 subpattern = SubPattern(state)
471
472 # check if all items share a common prefix
473 while True:
474 prefix = None
475 for item in items:
476 if not item:
477 break
478 if prefix is None:
479 prefix = item[0]
480 elif item[0] != prefix:
481 break
482 else:
483 # all subitems start with a common "prefix".
484 # move it out of the branch
485 for item in items:
486 del item[0]
487 subpattern.append(prefix)
488 continue # check next one
489 break
490
491 # check if the branch can be replaced by a character set
492 set = []
493 for item in items:
494 if len(item) != 1:
495 break
496 op, av = item[0]
497 if op is LITERAL:
498 set.append((op, av))
499 elif op is IN and av[0][0] is not NEGATE:
500 set.extend(av)
501 else:
502 break
503 else:
504 # we can store this as a character set instead of a
505 # branch (the compiler may optimize this even more)
506 subpattern.append((IN, _uniq(set)))
507 return subpattern
508
509 subpattern.append((BRANCH, (None, items)))
510 return subpattern
511
512 def _parse(source, state, verbose, nested, first=False):
513 # parse a simple pattern
514 subpattern = SubPattern(state)
515
516 # precompute constants into local variables
517 subpatternappend = subpattern.append
518 sourceget = source.get
519 sourcematch = source.match
520 _len = len
521 _ord = ord
522
523 while True:
524
525 this = source.next
526 if this is None:
527 break # end of pattern
528 if this in "|)":
529 break # end of subpattern
530 sourceget()
531
532 if verbose:
533 # skip whitespace and comments
534 if this in WHITESPACE:
535 continue
536 if this == "#":
537 while True:
538 this = sourceget()
539 if this is None or this == "\n":
540 break
541 continue
542
543 if this[0] == "\\":
544 code = _escape(source, this, state)
545 subpatternappend(code)
546
547 elif this not in SPECIAL_CHARS:
548 subpatternappend((LITERAL, _ord(this)))
549
550 elif this == "[":
551 here = source.tell() - 1
552 # character set
553 set = []
554 setappend = set.append
555 ## if sourcematch(":"):
556 ## pass # handle character classes
557 if source.next == '[':
558 import warnings
559 warnings.warn(
560 'Possible nested set at position %d' % source.tell(),
561 FutureWarning, stacklevel=nested + 6
562 )
563 negate = sourcematch("^")
564 # check remaining characters
565 while True:
566 this = sourceget()
567 if this is None:
568 raise source.error("unterminated character set",
569 source.tell() - here)
570 if this == "]" and set:
571 break
572 elif this[0] == "\\":
573 code1 = _class_escape(source, this)
574 else:
575 if set and this in '-&~|' and source.next == this:
576 import warnings
577 warnings.warn(
578 'Possible set %s at position %d' % (
579 'difference' if this == '-' else
580 'intersection' if this == '&' else
581 'symmetric difference' if this == '~' else
582 'union',
583 source.tell() - 1),
584 FutureWarning, stacklevel=nested + 6
585 )
586 code1 = LITERAL, _ord(this)
587 if sourcematch("-"):
588 # potential range
589 that = sourceget()
590 if that is None:
591 raise source.error("unterminated character set",
592 source.tell() - here)
593 if that == "]":
594 if code1[0] is IN:
595 code1 = code1[1][0]
596 setappend(code1)
597 setappend((LITERAL, _ord("-")))
598 break
599 if that[0] == "\\":
600 code2 = _class_escape(source, that)
601 else:
602 if that == '-':
603 import warnings
604 warnings.warn(
605 'Possible set difference at position %d' % (
606 source.tell() - 2),
607 FutureWarning, stacklevel=nested + 6
608 )
609 code2 = LITERAL, _ord(that)
610 if code1[0] != LITERAL or code2[0] != LITERAL:
611 msg = "bad character range %s-%s" % (this, that)
612 raise source.error(msg, len(this) + 1 + len(that))
613 lo = code1[1]
614 hi = code2[1]
615 if hi < lo:
616 msg = "bad character range %s-%s" % (this, that)
617 raise source.error(msg, len(this) + 1 + len(that))
618 setappend((RANGE, (lo, hi)))
619 else:
620 if code1[0] is IN:
621 code1 = code1[1][0]
622 setappend(code1)
623
624 set = _uniq(set)
625 # XXX: <fl> should move set optimization to compiler!
626 if _len(set) == 1 and set[0][0] is LITERAL:
627 # optimization
628 if negate:
629 subpatternappend((NOT_LITERAL, set[0][1]))
630 else:
631 subpatternappend(set[0])
632 else:
633 if negate:
634 set.insert(0, (NEGATE, None))
635 # charmap optimization can't be added here because
636 # global flags still are not known
637 subpatternappend((IN, set))
638
639 elif this in REPEAT_CHARS:
640 # repeat previous item
641 here = source.tell()
642 if this == "?":
643 min, max = 0, 1
644 elif this == "*":
645 min, max = 0, MAXREPEAT
646
647 elif this == "+":
648 min, max = 1, MAXREPEAT
649 elif this == "{":
650 if source.next == "}":
651 subpatternappend((LITERAL, _ord(this)))
652 continue
653
654 min, max = 0, MAXREPEAT
655 lo = hi = ""
656 while source.next in DIGITS:
657 lo += sourceget()
658 if sourcematch(","):
659 while source.next in DIGITS:
660 hi += sourceget()
661 else:
662 hi = lo
663 if not sourcematch("}"):
664 subpatternappend((LITERAL, _ord(this)))
665 source.seek(here)
666 continue
667
668 if lo:
669 min = int(lo)
670 if min >= MAXREPEAT:
671 raise OverflowError("the repetition number is too large")
672 if hi:
673 max = int(hi)
674 if max >= MAXREPEAT:
675 raise OverflowError("the repetition number is too large")
676 if max < min:
677 raise source.error("min repeat greater than max repeat",
678 source.tell() - here)
679 else:
680 raise AssertionError("unsupported quantifier %r" % (char,))
681 # figure out which item to repeat
682 if subpattern:
683 item = subpattern[-1:]
684 else:
685 item = None
686 if not item or item[0][0] is AT:
687 raise source.error("nothing to repeat",
688 source.tell() - here + len(this))
689 if item[0][0] in _REPEATCODES:
690 raise source.error("multiple repeat",
691 source.tell() - here + len(this))
692 if item[0][0] is SUBPATTERN:
693 group, add_flags, del_flags, p = item[0][1]
694 if group is None and not add_flags and not del_flags:
695 item = p
696 if sourcematch("?"):
697 # Non-Greedy Match
698 subpattern[-1] = (MIN_REPEAT, (min, max, item))
699 elif sourcematch("+"):
700 # Possessive Match (Always Greedy)
701 subpattern[-1] = (POSSESSIVE_REPEAT, (min, max, item))
702 else:
703 # Greedy Match
704 subpattern[-1] = (MAX_REPEAT, (min, max, item))
705
706 elif this == ".":
707 subpatternappend((ANY, None))
708
709 elif this == "(":
710 start = source.tell() - 1
711 capture = True
712 atomic = False
713 name = None
714 add_flags = 0
715 del_flags = 0
716 if sourcematch("?"):
717 # options
718 char = sourceget()
719 if char is None:
720 raise source.error("unexpected end of pattern")
721 if char == "P":
722 # python extensions
723 if sourcematch("<"):
724 # named group: skip forward to end of name
725 name = source.getuntil(">", "group name")
726 source.checkgroupname(name, 1)
727 elif sourcematch("="):
728 # named backreference
729 name = source.getuntil(")", "group name")
730 source.checkgroupname(name, 1)
731 gid = state.groupdict.get(name)
732 if gid is None:
733 msg = "unknown group name %r" % name
734 raise source.error(msg, len(name) + 1)
735 if not state.checkgroup(gid):
736 raise source.error("cannot refer to an open group",
737 len(name) + 1)
738 state.checklookbehindgroup(gid, source)
739 subpatternappend((GROUPREF, gid))
740 continue
741
742 else:
743 char = sourceget()
744 if char is None:
745 raise source.error("unexpected end of pattern")
746 raise source.error("unknown extension ?P" + char,
747 len(char) + 2)
748 elif char == ":":
749 # non-capturing group
750 capture = False
751 elif char == "#":
752 # comment
753 while True:
754 if source.next is None:
755 raise source.error("missing ), unterminated comment",
756 source.tell() - start)
757 if sourceget() == ")":
758 break
759 continue
760
761 elif char in "=!<":
762 # lookahead assertions
763 dir = 1
764 if char == "<":
765 char = sourceget()
766 if char is None:
767 raise source.error("unexpected end of pattern")
768 if char not in "=!":
769 raise source.error("unknown extension ?<" + char,
770 len(char) + 2)
771 dir = -1 # lookbehind
772 lookbehindgroups = state.lookbehindgroups
773 if lookbehindgroups is None:
774 state.lookbehindgroups = state.groups
775 p = _parse_sub(source, state, verbose, nested + 1)
776 if dir < 0:
777 if lookbehindgroups is None:
778 state.lookbehindgroups = None
779 if not sourcematch(")"):
780 raise source.error("missing ), unterminated subpattern",
781 source.tell() - start)
782 if char == "=":
783 subpatternappend((ASSERT, (dir, p)))
784 elif p:
785 subpatternappend((ASSERT_NOT, (dir, p)))
786 else:
787 subpatternappend((FAILURE, ()))
788 continue
789
790 elif char == "(":
791 # conditional backreference group
792 condname = source.getuntil(")", "group name")
793 if not (condname.isdecimal() and condname.isascii()):
794 source.checkgroupname(condname, 1)
795 condgroup = state.groupdict.get(condname)
796 if condgroup is None:
797 msg = "unknown group name %r" % condname
798 raise source.error(msg, len(condname) + 1)
799 else:
800 condgroup = int(condname)
801 if not condgroup:
802 raise source.error("bad group number",
803 len(condname) + 1)
804 if condgroup >= MAXGROUPS:
805 msg = "invalid group reference %d" % condgroup
806 raise source.error(msg, len(condname) + 1)
807 if condgroup not in state.grouprefpos:
808 state.grouprefpos[condgroup] = (
809 source.tell() - len(condname) - 1
810 )
811 state.checklookbehindgroup(condgroup, source)
812 item_yes = _parse(source, state, verbose, nested + 1)
813 if source.match("|"):
814 item_no = _parse(source, state, verbose, nested + 1)
815 if source.next == "|":
816 raise source.error("conditional backref with more than two branches")
817 else:
818 item_no = None
819 if not source.match(")"):
820 raise source.error("missing ), unterminated subpattern",
821 source.tell() - start)
822 subpatternappend((GROUPREF_EXISTS, (condgroup, item_yes, item_no)))
823 continue
824
825 elif char == ">":
826 # non-capturing, atomic group
827 capture = False
828 atomic = True
829 elif char in FLAGS or char == "-":
830 # flags
831 flags = _parse_flags(source, state, char)
832 if flags is None: # global flags
833 if not first or subpattern:
834 raise source.error('global flags not at the start '
835 'of the expression',
836 source.tell() - start)
837 verbose = state.flags & SRE_FLAG_VERBOSE
838 continue
839
840 add_flags, del_flags = flags
841 capture = False
842 else:
843 raise source.error("unknown extension ?" + char,
844 len(char) + 1)
845
846 # parse group contents
847 if capture:
848 try:
849 group = state.opengroup(name)
850 except error as err:
851 raise source.error(err.msg, len(name) + 1) from None
852 else:
853 group = None
854 sub_verbose = ((verbose or (add_flags & SRE_FLAG_VERBOSE)) and
855 not (del_flags & SRE_FLAG_VERBOSE))
856 p = _parse_sub(source, state, sub_verbose, nested + 1)
857 if not source.match(")"):
858 raise source.error("missing ), unterminated subpattern",
859 source.tell() - start)
860 if group is not None:
861 state.closegroup(group, p)
862 if atomic:
863 assert group is None
864 subpatternappend((ATOMIC_GROUP, p))
865 else:
866 subpatternappend((SUBPATTERN, (group, add_flags, del_flags, p)))
867
868 elif this == "^":
869 subpatternappend((AT, AT_BEGINNING))
870
871 elif this == "$":
872 subpatternappend((AT, AT_END))
873
874 else:
875 raise AssertionError("unsupported special character %r" % (char,))
876
877 # unpack non-capturing groups
878 for i in range(len(subpattern))[::-1]:
879 op, av = subpattern[i]
880 if op is SUBPATTERN:
881 group, add_flags, del_flags, p = av
882 if group is None and not add_flags and not del_flags:
883 subpattern[i: i+1] = p
884
885 return subpattern
886
887 def _parse_flags(source, state, char):
888 sourceget = source.get
889 add_flags = 0
890 del_flags = 0
891 if char != "-":
892 while True:
893 flag = FLAGS[char]
894 if source.istext:
895 if char == 'L':
896 msg = "bad inline flags: cannot use 'L' flag with a str pattern"
897 raise source.error(msg)
898 else:
899 if char == 'u':
900 msg = "bad inline flags: cannot use 'u' flag with a bytes pattern"
901 raise source.error(msg)
902 add_flags |= flag
903 if (flag & TYPE_FLAGS) and (add_flags & TYPE_FLAGS) != flag:
904 msg = "bad inline flags: flags 'a', 'u' and 'L' are incompatible"
905 raise source.error(msg)
906 char = sourceget()
907 if char is None:
908 raise source.error("missing -, : or )")
909 if char in ")-:":
910 break
911 if char not in FLAGS:
912 msg = "unknown flag" if char.isalpha() else "missing -, : or )"
913 raise source.error(msg, len(char))
914 if char == ")":
915 state.flags |= add_flags
916 return None
917 if add_flags & GLOBAL_FLAGS:
918 raise source.error("bad inline flags: cannot turn on global flag", 1)
919 if char == "-":
920 char = sourceget()
921 if char is None:
922 raise source.error("missing flag")
923 if char not in FLAGS:
924 msg = "unknown flag" if char.isalpha() else "missing flag"
925 raise source.error(msg, len(char))
926 while True:
927 flag = FLAGS[char]
928 if flag & TYPE_FLAGS:
929 msg = "bad inline flags: cannot turn off flags 'a', 'u' and 'L'"
930 raise source.error(msg)
931 del_flags |= flag
932 char = sourceget()
933 if char is None:
934 raise source.error("missing :")
935 if char == ":":
936 break
937 if char not in FLAGS:
938 msg = "unknown flag" if char.isalpha() else "missing :"
939 raise source.error(msg, len(char))
940 assert char == ":"
941 if del_flags & GLOBAL_FLAGS:
942 raise source.error("bad inline flags: cannot turn off global flag", 1)
943 if add_flags & del_flags:
944 raise source.error("bad inline flags: flag turned on and off", 1)
945 return add_flags, del_flags
946
947 def fix_flags(src, flags):
948 # Check and fix flags according to the type of pattern (str or bytes)
949 if isinstance(src, str):
950 if flags & SRE_FLAG_LOCALE:
951 raise ValueError("cannot use LOCALE flag with a str pattern")
952 if not flags & SRE_FLAG_ASCII:
953 flags |= SRE_FLAG_UNICODE
954 elif flags & SRE_FLAG_UNICODE:
955 raise ValueError("ASCII and UNICODE flags are incompatible")
956 else:
957 if flags & SRE_FLAG_UNICODE:
958 raise ValueError("cannot use UNICODE flag with a bytes pattern")
959 if flags & SRE_FLAG_LOCALE and flags & SRE_FLAG_ASCII:
960 raise ValueError("ASCII and LOCALE flags are incompatible")
961 return flags
962
963 def parse(str, flags=0, state=None):
964 # parse 're' pattern into list of (opcode, argument) tuples
965
966 source = Tokenizer(str)
967
968 if state is None:
969 state = State()
970 state.flags = flags
971 state.str = str
972
973 p = _parse_sub(source, state, flags & SRE_FLAG_VERBOSE, 0)
974 p.state.flags = fix_flags(str, p.state.flags)
975
976 if source.next is not None:
977 assert source.next == ")"
978 raise source.error("unbalanced parenthesis")
979
980 for g in p.state.grouprefpos:
981 if g >= p.state.groups:
982 msg = "invalid group reference %d" % g
983 raise error(msg, str, p.state.grouprefpos[g])
984
985 if flags & SRE_FLAG_DEBUG:
986 p.dump()
987
988 return p
989
990 def parse_template(source, pattern):
991 # parse 're' replacement string into list of literals and
992 # group references
993 s = Tokenizer(source)
994 sget = s.get
995 result = []
996 literal = []
997 lappend = literal.append
998 def addliteral():
999 if s.istext:
1000 result.append(''.join(literal))
1001 else:
1002 # The tokenizer implicitly decodes bytes objects as latin-1, we must
1003 # therefore re-encode the final representation.
1004 result.append(''.join(literal).encode('latin-1'))
1005 del literal[:]
1006 def addgroup(index, pos):
1007 if index > pattern.groups:
1008 raise s.error("invalid group reference %d" % index, pos)
1009 addliteral()
1010 result.append(index)
1011 groupindex = pattern.groupindex
1012 while True:
1013 this = sget()
1014 if this is None:
1015 break # end of replacement string
1016 if this[0] == "\\":
1017 # group
1018 c = this[1]
1019 if c == "g":
1020 if not s.match("<"):
1021 raise s.error("missing <")
1022 name = s.getuntil(">", "group name")
1023 if not (name.isdecimal() and name.isascii()):
1024 s.checkgroupname(name, 1)
1025 try:
1026 index = groupindex[name]
1027 except KeyError:
1028 raise IndexError("unknown group name %r" % name) from None
1029 else:
1030 index = int(name)
1031 if index >= MAXGROUPS:
1032 raise s.error("invalid group reference %d" % index,
1033 len(name) + 1)
1034 addgroup(index, len(name) + 1)
1035 elif c == "0":
1036 if s.next in OCTDIGITS:
1037 this += sget()
1038 if s.next in OCTDIGITS:
1039 this += sget()
1040 lappend(chr(int(this[1:], 8) & 0xff))
1041 elif c in DIGITS:
1042 isoctal = False
1043 if s.next in DIGITS:
1044 this += sget()
1045 if (c in OCTDIGITS and this[2] in OCTDIGITS and
1046 s.next in OCTDIGITS):
1047 this += sget()
1048 isoctal = True
1049 c = int(this[1:], 8)
1050 if c > 0o377:
1051 raise s.error('octal escape value %s outside of '
1052 'range 0-0o377' % this, len(this))
1053 lappend(chr(c))
1054 if not isoctal:
1055 addgroup(int(this[1:]), len(this) - 1)
1056 else:
1057 try:
1058 this = chr(ESCAPES[this][1])
1059 except KeyError:
1060 if c in ASCIILETTERS:
1061 raise s.error('bad escape %s' % this, len(this)) from None
1062 lappend(this)
1063 else:
1064 lappend(this)
1065 addliteral()
1066 return result