Aluode/PerceptionLabPortable
0
1#
2# Secret Labs' Regular Expression Engine core module
3#
4# Copyright (c) 1998-2001 by Secret Labs AB. All rights reserved.
5#
6# This version of the SRE library can be redistributed under CNRI's
7# Python 1.6 license. For any other use, please contact Secret Labs
8# AB (info@pythonware.com).
9#
10# Portions of this engine have been developed in cooperation with
11# CNRI. Hewlett-Packard provided funding for 1.6 integration and
12# other compatibility work.
13#
14# 2010-01-16 mrab Python front-end re-written and extended
15
16import enum
17import string
18import unicodedata
19from collections import defaultdict
20
21from regex import _regex
22
23__all__ = ["A", "ASCII", "B", "BESTMATCH", "D", "DEBUG", "E", "ENHANCEMATCH",
24 "F", "FULLCASE", "I", "IGNORECASE", "L", "LOCALE", "M", "MULTILINE", "P",
25 "POSIX", "R", "REVERSE", "S", "DOTALL", "T", "TEMPLATE", "U", "UNICODE",
26 "V0", "VERSION0", "V1", "VERSION1", "W", "WORD", "X", "VERBOSE", "error",
27 "Scanner", "RegexFlag"]
28
29# The regex exception.
30class error(Exception):
31 """Exception raised for invalid regular expressions.
32
33 Attributes:
34
35 msg: The unformatted error message
36 pattern: The regular expression pattern
37 pos: The position in the pattern where compilation failed, or None
38 lineno: The line number where compilation failed, unless pos is None
39 colno: The column number where compilation failed, unless pos is None
40 """
41
42 def __init__(self, message, pattern=None, pos=None):
43 newline = '\n' if isinstance(pattern, str) else b'\n'
44 self.msg = message
45 self.pattern = pattern
46 self.pos = pos
47 if pattern is not None and pos is not None:
48 self.lineno = pattern.count(newline, 0, pos) + 1
49 self.colno = pos - pattern.rfind(newline, 0, pos)
50
51 message = "{} at position {}".format(message, pos)
52
53 if newline in pattern:
54 message += " (line {}, column {})".format(self.lineno,
55 self.colno)
56
57 Exception.__init__(self, message)
58
59# The exception for when a positional flag has been turned on in the old
60# behaviour.
61class _UnscopedFlagSet(Exception):
62 pass
63
64# The exception for when parsing fails and we want to try something else.
65class ParseError(Exception):
66 pass
67
68# The exception for when there isn't a valid first set.
69class _FirstSetError(Exception):
70 pass
71
72# Flags.
73class RegexFlag(enum.IntFlag):
74 A = ASCII = 0x80 # Assume ASCII locale.
75 B = BESTMATCH = 0x1000 # Best fuzzy match.
76 D = DEBUG = 0x200 # Print parsed pattern.
77 E = ENHANCEMATCH = 0x8000 # Attempt to improve the fit after finding the first
78 # fuzzy match.
79 F = FULLCASE = 0x4000 # Unicode full case-folding.
80 I = IGNORECASE = 0x2 # Ignore case.
81 L = LOCALE = 0x4 # Assume current 8-bit locale.
82 M = MULTILINE = 0x8 # Make anchors look for newline.
83 P = POSIX = 0x10000 # POSIX-style matching (leftmost longest).
84 R = REVERSE = 0x400 # Search backwards.
85 S = DOTALL = 0x10 # Make dot match newline.
86 U = UNICODE = 0x20 # Assume Unicode locale.
87 V0 = VERSION0 = 0x2000 # Old legacy behaviour.
88 V1 = VERSION1 = 0x100 # New enhanced behaviour.
89 W = WORD = 0x800 # Default Unicode word breaks.
90 X = VERBOSE = 0x40 # Ignore whitespace and comments.
91 T = TEMPLATE = 0x1 # Template (present because re module has it).
92
93 def __repr__(self):
94 if self._name_ is not None:
95 return 'regex.%s' % self._name_
96
97 value = self._value_
98 members = []
99 negative = value < 0
100
101 if negative:
102 value = ~value
103
104 for m in self.__class__:
105 if value & m._value_:
106 value &= ~m._value_
107 members.append('regex.%s' % m._name_)
108
109 if value:
110 members.append(hex(value))
111
112 res = '|'.join(members)
113
114 if negative:
115 if len(members) > 1:
116 res = '~(%s)' % res
117 else:
118 res = '~%s' % res
119
120 return res
121
122 __str__ = object.__str__
123
124# Put the flags into the module namespace. Being explicit here helps tools like
125# linters and IDEs understand the code better.
126ASCII = RegexFlag.ASCII
127BESTMATCH = RegexFlag.BESTMATCH
128DEBUG = RegexFlag.DEBUG
129DOTALL = RegexFlag.DOTALL
130ENHANCEMATCH = RegexFlag.ENHANCEMATCH
131FULLCASE = RegexFlag.FULLCASE
132IGNORECASE = RegexFlag.IGNORECASE
133LOCALE = RegexFlag.LOCALE
134MULTILINE = RegexFlag.MULTILINE
135POSIX = RegexFlag.POSIX
136REVERSE = RegexFlag.REVERSE
137TEMPLATE = RegexFlag.TEMPLATE
138UNICODE = RegexFlag.UNICODE
139VERBOSE = RegexFlag.VERBOSE
140VERSION0 = RegexFlag.VERSION0
141VERSION1 = RegexFlag.VERSION1
142WORD = RegexFlag.WORD
143A = RegexFlag.A
144B = RegexFlag.B
145D = RegexFlag.D
146E = RegexFlag.E
147F = RegexFlag.F
148I = RegexFlag.I
149L = RegexFlag.L
150M = RegexFlag.M
151P = RegexFlag.P
152R = RegexFlag.R
153S = RegexFlag.S
154U = RegexFlag.U
155V0 = RegexFlag.V0
156V1 = RegexFlag.V1
157W = RegexFlag.W
158X = RegexFlag.X
159T = RegexFlag.T
160
161DEFAULT_VERSION = VERSION1
162
163_ALL_VERSIONS = VERSION0 | VERSION1
164_ALL_ENCODINGS = ASCII | LOCALE | UNICODE
165
166# The default flags for the various versions.
167DEFAULT_FLAGS = {VERSION0: 0, VERSION1: FULLCASE}
168
169# The mask for the flags.
170GLOBAL_FLAGS = (_ALL_VERSIONS | BESTMATCH | DEBUG | ENHANCEMATCH | POSIX |
171 REVERSE)
172SCOPED_FLAGS = (FULLCASE | IGNORECASE | MULTILINE | DOTALL | WORD | VERBOSE |
173 _ALL_ENCODINGS)
174
175ALPHA = frozenset(string.ascii_letters)
176DIGITS = frozenset(string.digits)
177ALNUM = ALPHA | DIGITS
178OCT_DIGITS = frozenset(string.octdigits)
179HEX_DIGITS = frozenset(string.hexdigits)
180SPECIAL_CHARS = frozenset("()|?*+{^$.[\\#") | frozenset([""])
181NAMED_CHAR_PART = ALNUM | frozenset(" -")
182PROPERTY_NAME_PART = ALNUM | frozenset(" &_-.")
183SET_OPS = ("||", "~~", "&&", "--")
184
185# The width of the code words inside the regex engine.
186BYTES_PER_CODE = _regex.get_code_size()
187BITS_PER_CODE = BYTES_PER_CODE * 8
188
189# The repeat count which represents infinity.
190UNLIMITED = (1 << BITS_PER_CODE) - 1
191
192# The regular expression flags.
193REGEX_FLAGS = {"a": ASCII, "b": BESTMATCH, "e": ENHANCEMATCH, "f": FULLCASE,
194 "i": IGNORECASE, "L": LOCALE, "m": MULTILINE, "p": POSIX, "r": REVERSE,
195 "s": DOTALL, "u": UNICODE, "V0": VERSION0, "V1": VERSION1, "w": WORD, "x":
196 VERBOSE}
197
198# The case flags.
199CASE_FLAGS = FULLCASE | IGNORECASE
200NOCASE = 0
201FULLIGNORECASE = FULLCASE | IGNORECASE
202
203FULL_CASE_FOLDING = UNICODE | FULLIGNORECASE
204
205CASE_FLAGS_COMBINATIONS = {0: 0, FULLCASE: 0, IGNORECASE: IGNORECASE,
206 FULLIGNORECASE: FULLIGNORECASE}
207
208# The number of digits in hexadecimal escapes.
209HEX_ESCAPES = {"x": 2, "u": 4, "U": 8}
210
211# The names of the opcodes.
212OPCODES = """
213FAILURE
214SUCCESS
215ANY
216ANY_ALL
217ANY_ALL_REV
218ANY_REV
219ANY_U
220ANY_U_REV
221ATOMIC
222BOUNDARY
223BRANCH
224CALL_REF
225CHARACTER
226CHARACTER_IGN
227CHARACTER_IGN_REV
228CHARACTER_REV
229CONDITIONAL
230DEFAULT_BOUNDARY
231DEFAULT_END_OF_WORD
232DEFAULT_START_OF_WORD
233END
234END_OF_LINE
235END_OF_LINE_U
236END_OF_STRING
237END_OF_STRING_LINE
238END_OF_STRING_LINE_U
239END_OF_WORD
240FUZZY
241GRAPHEME_BOUNDARY
242GREEDY_REPEAT
243GROUP
244GROUP_CALL
245GROUP_EXISTS
246KEEP
247LAZY_REPEAT
248LOOKAROUND
249NEXT
250PROPERTY
251PROPERTY_IGN
252PROPERTY_IGN_REV
253PROPERTY_REV
254PRUNE
255RANGE
256RANGE_IGN
257RANGE_IGN_REV
258RANGE_REV
259REF_GROUP
260REF_GROUP_FLD
261REF_GROUP_FLD_REV
262REF_GROUP_IGN
263REF_GROUP_IGN_REV
264REF_GROUP_REV
265SEARCH_ANCHOR
266SET_DIFF
267SET_DIFF_IGN
268SET_DIFF_IGN_REV
269SET_DIFF_REV
270SET_INTER
271SET_INTER_IGN
272SET_INTER_IGN_REV
273SET_INTER_REV
274SET_SYM_DIFF
275SET_SYM_DIFF_IGN
276SET_SYM_DIFF_IGN_REV
277SET_SYM_DIFF_REV
278SET_UNION
279SET_UNION_IGN
280SET_UNION_IGN_REV
281SET_UNION_REV
282SKIP
283START_OF_LINE
284START_OF_LINE_U
285START_OF_STRING
286START_OF_WORD
287STRING
288STRING_FLD
289STRING_FLD_REV
290STRING_IGN
291STRING_IGN_REV
292STRING_REV
293FUZZY_EXT
294"""
295
296# Define the opcodes in a namespace.
297class Namespace:
298 pass
299
300OP = Namespace()
301for i, op in enumerate(OPCODES.split()):
302 setattr(OP, op, i)
303
304def _shrink_cache(cache_dict, args_dict, locale_sensitive, max_length, divisor=5):
305 """Make room in the given cache.
306
307 Args:
308 cache_dict: The cache dictionary to modify.
309 args_dict: The dictionary of named list args used by patterns.
310 max_length: Maximum # of entries in cache_dict before it is shrunk.
311 divisor: Cache will shrink to max_length - 1/divisor*max_length items.
312 """
313 # Toss out a fraction of the entries at random to make room for new ones.
314 # A random algorithm was chosen as opposed to simply cache_dict.popitem()
315 # as popitem could penalize the same regular expression repeatedly based
316 # on its internal hash value. Being random should spread the cache miss
317 # love around.
318 cache_keys = tuple(cache_dict.keys())
319 overage = len(cache_keys) - max_length
320 if overage < 0:
321 # Cache is already within limits. Normally this should not happen
322 # but it could due to multithreading.
323 return
324
325 number_to_toss = max_length // divisor + overage
326
327 # The import is done here to avoid a circular dependency.
328 import random
329 if not hasattr(random, 'sample'):
330 # Do nothing while resolving the circular dependency:
331 # re->random->warnings->tokenize->string->re
332 return
333
334 for doomed_key in random.sample(cache_keys, number_to_toss):
335 try:
336 del cache_dict[doomed_key]
337 except KeyError:
338 # Ignore problems if the cache changed from another thread.
339 pass
340
341 # Rebuild the arguments and locale-sensitivity dictionaries.
342 args_dict.clear()
343 sensitivity_dict = {}
344 for pattern, pattern_type, flags, args, default_version, locale in tuple(cache_dict):
345 args_dict[pattern, pattern_type, flags, default_version, locale] = args
346 try:
347 sensitivity_dict[pattern_type, pattern] = locale_sensitive[pattern_type, pattern]
348 except KeyError:
349 pass
350
351 locale_sensitive.clear()
352 locale_sensitive.update(sensitivity_dict)
353
354def _fold_case(info, string):
355 "Folds the case of a string."
356 flags = info.flags
357 if (flags & _ALL_ENCODINGS) == 0:
358 flags |= info.guess_encoding
359
360 return _regex.fold_case(flags, string)
361
362def is_cased_i(info, char):
363 "Checks whether a character is cased."
364 return len(_regex.get_all_cases(info.flags, char)) > 1
365
366def is_cased_f(flags, char):
367 "Checks whether a character is cased."
368 return len(_regex.get_all_cases(flags, char)) > 1
369
370def _compile_firstset(info, fs):
371 "Compiles the firstset for the pattern."
372 reverse = bool(info.flags & REVERSE)
373 fs = _check_firstset(info, reverse, fs)
374 if not fs or isinstance(fs, AnyAll):
375 return []
376
377 # Compile the firstset.
378 return fs.compile(reverse)
379
380def _check_firstset(info, reverse, fs):
381 "Checks the firstset for the pattern."
382 if not fs or None in fs:
383 return None
384
385 # If we ignore the case, for simplicity we won't build a firstset.
386 members = set()
387 case_flags = NOCASE
388 for i in fs:
389 if isinstance(i, Character) and not i.positive:
390 return None
391
392# if i.case_flags:
393# if isinstance(i, Character):
394# if is_cased_i(info, i.value):
395# return []
396# elif isinstance(i, SetBase):
397# return []
398 case_flags |= i.case_flags
399 members.add(i.with_flags(case_flags=NOCASE))
400
401 if case_flags == (FULLCASE | IGNORECASE):
402 return None
403
404 # Build the firstset.
405 fs = SetUnion(info, list(members), case_flags=case_flags & ~FULLCASE,
406 zerowidth=True)
407 fs = fs.optimise(info, reverse, in_set=True)
408
409 return fs
410
411def _flatten_code(code):
412 "Flattens the code from a list of tuples."
413 flat_code = []
414 for c in code:
415 flat_code.extend(c)
416
417 return flat_code
418
419def make_case_flags(info):
420 "Makes the case flags."
421 flags = info.flags & CASE_FLAGS
422
423 # Turn off FULLCASE if ASCII is turned on.
424 if info.flags & ASCII:
425 flags &= ~FULLCASE
426
427 return flags
428
429def make_character(info, value, in_set=False):
430 "Makes a character literal."
431 if in_set:
432 # A character set is built case-sensitively.
433 return Character(value)
434
435 return Character(value, case_flags=make_case_flags(info))
436
437def make_ref_group(info, name, position):
438 "Makes a group reference."
439 return RefGroup(info, name, position, case_flags=make_case_flags(info))
440
441def make_string_set(info, name):
442 "Makes a string set."
443 return StringSet(info, name, case_flags=make_case_flags(info))
444
445def make_property(info, prop, in_set):
446 "Makes a property."
447 if in_set:
448 return prop
449
450 return prop.with_flags(case_flags=make_case_flags(info))
451
452def _parse_pattern(source, info):
453 "Parses a pattern, eg. 'a|b|c'."
454 branches = [parse_sequence(source, info)]
455 while source.match("|"):
456 branches.append(parse_sequence(source, info))
457
458 if len(branches) == 1:
459 return branches[0]
460 return Branch(branches)
461
462def parse_sequence(source, info):
463 "Parses a sequence, eg. 'abc'."
464 sequence = [None]
465 case_flags = make_case_flags(info)
466 while True:
467 saved_pos = source.pos
468 ch = source.get()
469 if ch in SPECIAL_CHARS:
470 if ch in ")|":
471 # The end of a sequence. At the end of the pattern ch is "".
472 source.pos = saved_pos
473 break
474 elif ch == "\\":
475 # An escape sequence outside a set.
476 sequence.append(parse_escape(source, info, False))
477 elif ch == "(":
478 # A parenthesised subpattern or a flag.
479 element = parse_paren(source, info)
480 if element is None:
481 case_flags = make_case_flags(info)
482 else:
483 sequence.append(element)
484 elif ch == ".":
485 # Any character.
486 if info.flags & DOTALL:
487 sequence.append(AnyAll())
488 elif info.flags & WORD:
489 sequence.append(AnyU())
490 else:
491 sequence.append(Any())
492 elif ch == "[":
493 # A character set.
494 sequence.append(parse_set(source, info))
495 elif ch == "^":
496 # The start of a line or the string.
497 if info.flags & MULTILINE:
498 if info.flags & WORD:
499 sequence.append(StartOfLineU())
500 else:
501 sequence.append(StartOfLine())
502 else:
503 sequence.append(StartOfString())
504 elif ch == "$":
505 # The end of a line or the string.
506 if info.flags & MULTILINE:
507 if info.flags & WORD:
508 sequence.append(EndOfLineU())
509 else:
510 sequence.append(EndOfLine())
511 else:
512 if info.flags & WORD:
513 sequence.append(EndOfStringLineU())
514 else:
515 sequence.append(EndOfStringLine())
516 elif ch in "?*+{":
517 # Looks like a quantifier.
518 counts = parse_quantifier(source, info, ch)
519 if counts:
520 # It _is_ a quantifier.
521 apply_quantifier(source, info, counts, case_flags, ch,
522 saved_pos, sequence)
523 sequence.append(None)
524 else:
525 # It's not a quantifier. Maybe it's a fuzzy constraint.
526 constraints = parse_fuzzy(source, info, ch, case_flags)
527 if constraints:
528 # It _is_ a fuzzy constraint.
529 apply_constraint(source, info, constraints, case_flags,
530 saved_pos, sequence)
531 sequence.append(None)
532 else:
533 # The element was just a literal.
534 sequence.append(Character(ord(ch),
535 case_flags=case_flags))
536 else:
537 # A literal.
538 sequence.append(Character(ord(ch), case_flags=case_flags))
539 else:
540 # A literal.
541 sequence.append(Character(ord(ch), case_flags=case_flags))
542
543 sequence = [item for item in sequence if item is not None]
544 return Sequence(sequence)
545
546def apply_quantifier(source, info, counts, case_flags, ch, saved_pos,
547 sequence):
548 element = sequence.pop()
549 if element is None:
550 if sequence:
551 raise error("multiple repeat", source.string, saved_pos)
552 raise error("nothing to repeat", source.string, saved_pos)
553
554 if isinstance(element, (GreedyRepeat, LazyRepeat, PossessiveRepeat)):
555 raise error("multiple repeat", source.string, saved_pos)
556
557 min_count, max_count = counts
558 saved_pos = source.pos
559 ch = source.get()
560 if ch == "?":
561 # The "?" suffix that means it's a lazy repeat.
562 repeated = LazyRepeat
563 elif ch == "+":
564 # The "+" suffix that means it's a possessive repeat.
565 repeated = PossessiveRepeat
566 else:
567 # No suffix means that it's a greedy repeat.
568 source.pos = saved_pos
569 repeated = GreedyRepeat
570
571 # Ignore the quantifier if it applies to a zero-width item or the number of
572 # repeats is fixed at 1.
573 if not element.is_empty() and (min_count != 1 or max_count != 1):
574 element = repeated(element, min_count, max_count)
575
576 sequence.append(element)
577
578def apply_constraint(source, info, constraints, case_flags, saved_pos,
579 sequence):
580 element = sequence.pop()
581 if element is None:
582 raise error("nothing for fuzzy constraint", source.string, saved_pos)
583
584 # If a group is marked as fuzzy then put all of the fuzzy part in the
585 # group.
586 if isinstance(element, Group):
587 element.subpattern = Fuzzy(element.subpattern, constraints)
588 sequence.append(element)
589 else:
590 sequence.append(Fuzzy(element, constraints))
591
592_QUANTIFIERS = {"?": (0, 1), "*": (0, None), "+": (1, None)}
593
594def parse_quantifier(source, info, ch):
595 "Parses a quantifier."
596 q = _QUANTIFIERS.get(ch)
597 if q:
598 # It's a quantifier.
599 return q
600
601 if ch == "{":
602 # Looks like a limited repeated element, eg. 'a{2,3}'.
603 counts = parse_limited_quantifier(source)
604 if counts:
605 return counts
606
607 return None
608
609def is_above_limit(count):
610 "Checks whether a count is above the maximum."
611 return count is not None and count >= UNLIMITED
612
613def parse_limited_quantifier(source):
614 "Parses a limited quantifier."
615 saved_pos = source.pos
616 min_count = parse_count(source)
617 if source.match(","):
618 max_count = parse_count(source)
619
620 # No minimum means 0 and no maximum means unlimited.
621 min_count = int(min_count or 0)
622 max_count = int(max_count) if max_count else None
623 else:
624 if not min_count:
625 source.pos = saved_pos
626 return None
627
628 min_count = max_count = int(min_count)
629
630 if not source.match ("}"):
631 source.pos = saved_pos
632 return None
633
634 if is_above_limit(min_count) or is_above_limit(max_count):
635 raise error("repeat count too big", source.string, saved_pos)
636
637 if max_count is not None and min_count > max_count:
638 raise error("min repeat greater than max repeat", source.string,
639 saved_pos)
640
641 return min_count, max_count
642
643def parse_fuzzy(source, info, ch, case_flags):
644 "Parses a fuzzy setting, if present."
645 saved_pos = source.pos
646
647 if ch != "{":
648 return None
649
650 constraints = {}
651 try:
652 parse_fuzzy_item(source, constraints)
653 while source.match(","):
654 parse_fuzzy_item(source, constraints)
655 except ParseError:
656 source.pos = saved_pos
657 return None
658
659 if source.match(":"):
660 constraints["test"] = parse_fuzzy_test(source, info, case_flags)
661
662 if not source.match("}"):
663 raise error("expected }", source.string, source.pos)
664
665 return constraints
666
667def parse_fuzzy_item(source, constraints):
668 "Parses a fuzzy setting item."
669 saved_pos = source.pos
670 try:
671 parse_cost_constraint(source, constraints)
672 except ParseError:
673 source.pos = saved_pos
674
675 parse_cost_equation(source, constraints)
676
677def parse_cost_constraint(source, constraints):
678 "Parses a cost constraint."
679 saved_pos = source.pos
680 ch = source.get()
681 if ch in ALPHA:
682 # Syntax: constraint [("<=" | "<") cost]
683 constraint = parse_constraint(source, constraints, ch)
684
685 max_inc = parse_fuzzy_compare(source)
686
687 if max_inc is None:
688 # No maximum cost.
689 constraints[constraint] = 0, None
690 else:
691 # There's a maximum cost.
692 cost_pos = source.pos
693 max_cost = parse_cost_limit(source)
694
695 # Inclusive or exclusive limit?
696 if not max_inc:
697 max_cost -= 1
698
699 if max_cost < 0:
700 raise error("bad fuzzy cost limit", source.string, cost_pos)
701
702 constraints[constraint] = 0, max_cost
703 elif ch in DIGITS:
704 # Syntax: cost ("<=" | "<") constraint ("<=" | "<") cost
705 source.pos = saved_pos
706
707 # Minimum cost.
708 cost_pos = source.pos
709 min_cost = parse_cost_limit(source)
710
711 min_inc = parse_fuzzy_compare(source)
712 if min_inc is None:
713 raise ParseError()
714
715 constraint = parse_constraint(source, constraints, source.get())
716
717 max_inc = parse_fuzzy_compare(source)
718 if max_inc is None:
719 raise ParseError()
720
721 # Maximum cost.
722 cost_pos = source.pos
723 max_cost = parse_cost_limit(source)
724
725 # Inclusive or exclusive limits?
726 if not min_inc:
727 min_cost += 1
728 if not max_inc:
729 max_cost -= 1
730
731 if not 0 <= min_cost <= max_cost:
732 raise error("bad fuzzy cost limit", source.string, cost_pos)
733
734 constraints[constraint] = min_cost, max_cost
735 else:
736 raise ParseError()
737
738def parse_cost_limit(source):
739 "Parses a cost limit."
740 cost_pos = source.pos
741 digits = parse_count(source)
742
743 try:
744 return int(digits)
745 except ValueError:
746 pass
747
748 raise error("bad fuzzy cost limit", source.string, cost_pos)
749
750def parse_constraint(source, constraints, ch):
751 "Parses a constraint."
752 if ch not in "deis":
753 raise ParseError()
754
755 if ch in constraints:
756 raise ParseError()
757
758 return ch
759
760def parse_fuzzy_compare(source):
761 "Parses a cost comparator."
762 if source.match("<="):
763 return True
764 elif source.match("<"):
765 return False
766 else:
767 return None
768
769def parse_cost_equation(source, constraints):
770 "Parses a cost equation."
771 if "cost" in constraints:
772 raise error("more than one cost equation", source.string, source.pos)
773
774 cost = {}
775
776 parse_cost_term(source, cost)
777 while source.match("+"):
778 parse_cost_term(source, cost)
779
780 max_inc = parse_fuzzy_compare(source)
781 if max_inc is None:
782 raise ParseError()
783
784 max_cost = int(parse_count(source))
785
786 if not max_inc:
787 max_cost -= 1
788
789 if max_cost < 0:
790 raise error("bad fuzzy cost limit", source.string, source.pos)
791
792 cost["max"] = max_cost
793
794 constraints["cost"] = cost
795
796def parse_cost_term(source, cost):
797 "Parses a cost equation term."
798 coeff = parse_count(source)
799 ch = source.get()
800 if ch not in "dis":
801 raise ParseError()
802
803 if ch in cost:
804 raise error("repeated fuzzy cost", source.string, source.pos)
805
806 cost[ch] = int(coeff or 1)
807
808def parse_fuzzy_test(source, info, case_flags):
809 saved_pos = source.pos
810 ch = source.get()
811 if ch in SPECIAL_CHARS:
812 if ch == "\\":
813 # An escape sequence outside a set.
814 return parse_escape(source, info, False)
815 elif ch == ".":
816 # Any character.
817 if info.flags & DOTALL:
818 return AnyAll()
819 elif info.flags & WORD:
820 return AnyU()
821 else:
822 return Any()
823 elif ch == "[":
824 # A character set.
825 return parse_set(source, info)
826 else:
827 raise error("expected character set", source.string, saved_pos)
828 elif ch:
829 # A literal.
830 return Character(ord(ch), case_flags=case_flags)
831 else:
832 raise error("expected character set", source.string, saved_pos)
833
834def parse_count(source):
835 "Parses a quantifier's count, which can be empty."
836 return source.get_while(DIGITS)
837
838def parse_paren(source, info):
839 """Parses a parenthesised subpattern or a flag. Returns FLAGS if it's an
840 inline flag.
841 """
842 saved_pos = source.pos
843 ch = source.get(True)
844 if ch == "?":
845 # (?...
846 saved_pos_2 = source.pos
847 ch = source.get(True)
848 if ch == "<":
849 # (?<...
850 saved_pos_3 = source.pos
851 ch = source.get()
852 if ch in ("=", "!"):
853 # (?<=... or (?<!...: lookbehind.
854 return parse_lookaround(source, info, True, ch == "=")
855
856 # (?<...: a named capture group.
857 source.pos = saved_pos_3
858 name = parse_name(source)
859 group = info.open_group(name)
860 source.expect(">")
861 saved_flags = info.flags
862 try:
863 subpattern = _parse_pattern(source, info)
864 source.expect(")")
865 finally:
866 info.flags = saved_flags
867 source.ignore_space = bool(info.flags & VERBOSE)
868
869 info.close_group()
870 return Group(info, group, subpattern)
871 if ch in ("=", "!"):
872 # (?=... or (?!...: lookahead.
873 return parse_lookaround(source, info, False, ch == "=")
874 if ch == "P":
875 # (?P...: a Python extension.
876 return parse_extension(source, info)
877 if ch == "#":
878 # (?#...: a comment.
879 return parse_comment(source)
880 if ch == "(":
881 # (?(...: a conditional subpattern.
882 return parse_conditional(source, info)
883 if ch == ">":
884 # (?>...: an atomic subpattern.
885 return parse_atomic(source, info)
886 if ch == "|":
887 # (?|...: a common/reset groups branch.
888 return parse_common(source, info)
889 if ch == "R" or "0" <= ch <= "9":
890 # (?R...: probably a call to a group.
891 return parse_call_group(source, info, ch, saved_pos_2)
892 if ch == "&":
893 # (?&...: a call to a named group.
894 return parse_call_named_group(source, info, saved_pos_2)
895 if (ch == "+" or ch == "-") and source.peek() in DIGITS:
896 return parse_rel_call_group(source, info, ch, saved_pos_2)
897
898 # (?...: probably a flags subpattern.
899 source.pos = saved_pos_2
900 return parse_flags_subpattern(source, info)
901
902 if ch == "*":
903 # (*...
904 saved_pos_2 = source.pos
905 word = source.get_while(set(")>"), include=False)
906 if word[ : 1].isalpha():
907 verb = VERBS.get(word)
908 if not verb:
909 raise error("unknown verb", source.string, saved_pos_2)
910
911 source.expect(")")
912
913 return verb
914
915 # (...: an unnamed capture group.
916 source.pos = saved_pos
917 group = info.open_group()
918 saved_flags = info.flags
919 try:
920 subpattern = _parse_pattern(source, info)
921 source.expect(")")
922 finally:
923 info.flags = saved_flags
924 source.ignore_space = bool(info.flags & VERBOSE)
925
926 info.close_group()
927
928 return Group(info, group, subpattern)
929
930def parse_extension(source, info):
931 "Parses a Python extension."
932 saved_pos = source.pos
933 ch = source.get()
934 if ch == "<":
935 # (?P<...: a named capture group.
936 name = parse_name(source)
937 group = info.open_group(name)
938 source.expect(">")
939 saved_flags = info.flags
940 try:
941 subpattern = _parse_pattern(source, info)
942 source.expect(")")
943 finally:
944 info.flags = saved_flags
945 source.ignore_space = bool(info.flags & VERBOSE)
946
947 info.close_group()
948
949 return Group(info, group, subpattern)
950 if ch == "=":
951 # (?P=...: a named group reference.
952 name = parse_name(source, allow_numeric=True)
953 source.expect(")")
954 if info.is_open_group(name):
955 raise error("cannot refer to an open group", source.string,
956 saved_pos)
957
958 return make_ref_group(info, name, saved_pos)
959 if ch == ">" or ch == "&":
960 # (?P>...: a call to a group.
961 return parse_call_named_group(source, info, saved_pos)
962
963 source.pos = saved_pos
964 raise error("unknown extension", source.string, saved_pos)
965
966def parse_comment(source):
967 "Parses a comment."
968 while True:
969 saved_pos = source.pos
970 c = source.get(True)
971
972 if not c or c == ")":
973 break
974
975 if c == "\\":
976 c = source.get(True)
977
978 source.pos = saved_pos
979 source.expect(")")
980
981 return None
982
983def parse_lookaround(source, info, behind, positive):
984 "Parses a lookaround."
985 saved_flags = info.flags
986 try:
987 subpattern = _parse_pattern(source, info)
988 source.expect(")")
989 finally:
990 info.flags = saved_flags
991 source.ignore_space = bool(info.flags & VERBOSE)
992
993 return LookAround(behind, positive, subpattern)
994
995def parse_conditional(source, info):
996 "Parses a conditional subpattern."
997 saved_flags = info.flags
998 saved_pos = source.pos
999 ch = source.get()
1000 if ch == "?":
1001 # (?(?...
1002 ch = source.get()
1003 if ch in ("=", "!"):
1004 # (?(?=... or (?(?!...: lookahead conditional.
1005 return parse_lookaround_conditional(source, info, False, ch == "=")
1006 if ch == "<":
1007 # (?(?<...
1008 ch = source.get()
1009 if ch in ("=", "!"):
1010 # (?(?<=... or (?(?<!...: lookbehind conditional.
1011 return parse_lookaround_conditional(source, info, True, ch ==
1012 "=")
1013
1014 source.pos = saved_pos
1015 raise error("expected lookaround conditional", source.string,
1016 source.pos)
1017
1018 source.pos = saved_pos
1019 try:
1020 group = parse_name(source, True)
1021 source.expect(")")
1022 yes_branch = parse_sequence(source, info)
1023 if source.match("|"):
1024 no_branch = parse_sequence(source, info)
1025 else:
1026 no_branch = Sequence()
1027
1028 source.expect(")")
1029 finally:
1030 info.flags = saved_flags
1031 source.ignore_space = bool(info.flags & VERBOSE)
1032
1033 if yes_branch.is_empty() and no_branch.is_empty():
1034 return Sequence()
1035
1036 return Conditional(info, group, yes_branch, no_branch, saved_pos)
1037
1038def parse_lookaround_conditional(source, info, behind, positive):
1039 saved_flags = info.flags
1040 try:
1041 subpattern = _parse_pattern(source, info)
1042 source.expect(")")
1043 finally:
1044 info.flags = saved_flags
1045 source.ignore_space = bool(info.flags & VERBOSE)
1046
1047 yes_branch = parse_sequence(source, info)
1048 if source.match("|"):
1049 no_branch = parse_sequence(source, info)
1050 else:
1051 no_branch = Sequence()
1052
1053 source.expect(")")
1054
1055 return LookAroundConditional(behind, positive, subpattern, yes_branch,
1056 no_branch)
1057
1058def parse_atomic(source, info):
1059 "Parses an atomic subpattern."
1060 saved_flags = info.flags
1061 try:
1062 subpattern = _parse_pattern(source, info)
1063 source.expect(")")
1064 finally:
1065 info.flags = saved_flags
1066 source.ignore_space = bool(info.flags & VERBOSE)
1067
1068 return Atomic(subpattern)
1069
1070def parse_common(source, info):
1071 "Parses a common groups branch."
1072 # Capture group numbers in different branches can reuse the group numbers.
1073 initial_group_count = info.group_count
1074 branches = [parse_sequence(source, info)]
1075 final_group_count = info.group_count
1076 while source.match("|"):
1077 info.group_count = initial_group_count
1078 branches.append(parse_sequence(source, info))
1079 final_group_count = max(final_group_count, info.group_count)
1080
1081 info.group_count = final_group_count
1082 source.expect(")")
1083
1084 if len(branches) == 1:
1085 return branches[0]
1086 return Branch(branches)
1087
1088def parse_call_group(source, info, ch, pos):
1089 "Parses a call to a group."
1090 if ch == "R":
1091 group = "0"
1092 else:
1093 group = ch + source.get_while(DIGITS)
1094
1095 source.expect(")")
1096
1097 return CallGroup(info, group, pos)
1098
1099def parse_rel_call_group(source, info, ch, pos):
1100 "Parses a relative call to a group."
1101 digits = source.get_while(DIGITS)
1102 if not digits:
1103 raise error("missing relative group number", source.string, source.pos)
1104
1105 offset = int(digits)
1106 group = info.group_count + offset if ch == "+" else info.group_count - offset + 1
1107 if group <= 0:
1108 raise error("invalid relative group number", source.string, source.pos)
1109
1110 source.expect(")")
1111
1112 return CallGroup(info, group, pos)
1113
1114def parse_call_named_group(source, info, pos):
1115 "Parses a call to a named group."
1116 group = parse_name(source)
1117 source.expect(")")
1118
1119 return CallGroup(info, group, pos)
1120
1121def parse_flag_set(source):
1122 "Parses a set of inline flags."
1123 flags = 0
1124
1125 try:
1126 while True:
1127 saved_pos = source.pos
1128 ch = source.get()
1129 if ch == "V":
1130 ch += source.get()
1131 flags |= REGEX_FLAGS[ch]
1132 except KeyError:
1133 source.pos = saved_pos
1134
1135 return flags
1136
1137def parse_flags(source, info):
1138 "Parses flags being turned on/off."
1139 flags_on = parse_flag_set(source)
1140 if source.match("-"):
1141 flags_off = parse_flag_set(source)
1142 if not flags_off:
1143 raise error("bad inline flags: no flags after '-'", source.string,
1144 source.pos)
1145 else:
1146 flags_off = 0
1147
1148 if flags_on & LOCALE:
1149 # Remember that this pattern as an inline locale flag.
1150 info.inline_locale = True
1151
1152 return flags_on, flags_off
1153
1154def parse_subpattern(source, info, flags_on, flags_off):
1155 "Parses a subpattern with scoped flags."
1156 saved_flags = info.flags
1157 info.flags = (info.flags | flags_on) & ~flags_off
1158
1159 # Ensure that there aren't multiple encoding flags set.
1160 if info.flags & (ASCII | LOCALE | UNICODE):
1161 info.flags = (info.flags & ~_ALL_ENCODINGS) | flags_on
1162
1163 source.ignore_space = bool(info.flags & VERBOSE)
1164 try:
1165 subpattern = _parse_pattern(source, info)
1166 source.expect(")")
1167 finally:
1168 info.flags = saved_flags
1169 source.ignore_space = bool(info.flags & VERBOSE)
1170
1171 return subpattern
1172
1173def parse_flags_subpattern(source, info):
1174 """Parses a flags subpattern. It could be inline flags or a subpattern
1175 possibly with local flags. If it's a subpattern, then that's returned;
1176 if it's a inline flags, then None is returned.
1177 """
1178 flags_on, flags_off = parse_flags(source, info)
1179
1180 if flags_off & GLOBAL_FLAGS:
1181 raise error("bad inline flags: cannot turn off global flag",
1182 source.string, source.pos)
1183
1184 if flags_on & flags_off:
1185 raise error("bad inline flags: flag turned on and off", source.string,
1186 source.pos)
1187
1188 # Handle flags which are global in all regex behaviours.
1189 new_global_flags = (flags_on & ~info.global_flags) & GLOBAL_FLAGS
1190 if new_global_flags:
1191 info.global_flags |= new_global_flags
1192
1193 # A global has been turned on, so reparse the pattern.
1194 raise _UnscopedFlagSet(info.global_flags)
1195
1196 # Ensure that from now on we have only scoped flags.
1197 flags_on &= ~GLOBAL_FLAGS
1198
1199 if source.match(":"):
1200 return parse_subpattern(source, info, flags_on, flags_off)