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