codekingpro/portable-devtools
114k
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
528 if constraints:
529 # It _is_ a fuzzy constraint.
530 if is_actually_fuzzy(constraints):
531 apply_constraint(source, info, constraints, case_flags,
532 saved_pos, sequence)
533 sequence.append(None)
534 else:
535 # The element was just a literal.
536 sequence.append(Character(ord(ch),
537 case_flags=case_flags))
538 else:
539 # A literal.
540 sequence.append(Character(ord(ch), case_flags=case_flags))
541 else:
542 # A literal.
543 sequence.append(Character(ord(ch), case_flags=case_flags))
544
545 sequence = [item for item in sequence if item is not None]
546 return Sequence(sequence)
547
548def is_actually_fuzzy(constraints):
549 "Checks whether a fuzzy constraint is actually fuzzy."
550 if constraints.get("e") == (0, 0):
551 return False
552
553 if (constraints.get("s"), constraints.get("i"), constraints.get("d")) == ((0, 0), (0, 0), (0, 0)):
554 return False
555
556 return True
557
558def apply_quantifier(source, info, counts, case_flags, ch, saved_pos,
559 sequence):
560 element = sequence.pop()
561 if element is None:
562 if sequence:
563 raise error("multiple repeat", source.string, saved_pos)
564 raise error("nothing to repeat", source.string, saved_pos)
565
566 if isinstance(element, (GreedyRepeat, LazyRepeat, PossessiveRepeat)):
567 raise error("multiple repeat", source.string, saved_pos)
568
569 min_count, max_count = counts
570 saved_pos = source.pos
571 ch = source.get()
572 if ch == "?":
573 # The "?" suffix that means it's a lazy repeat.
574 repeated = LazyRepeat
575 elif ch == "+":
576 # The "+" suffix that means it's a possessive repeat.
577 repeated = PossessiveRepeat
578 else:
579 # No suffix means that it's a greedy repeat.
580 source.pos = saved_pos
581 repeated = GreedyRepeat
582
583 # Ignore the quantifier if it applies to a zero-width item or the number of
584 # repeats is fixed at 1.
585 if not element.is_empty() and (min_count != 1 or max_count != 1):
586 element = repeated(element, min_count, max_count)
587
588 sequence.append(element)
589
590def apply_constraint(source, info, constraints, case_flags, saved_pos,
591 sequence):
592 element = sequence.pop()
593 if element is None:
594 raise error("nothing for fuzzy constraint", source.string, saved_pos)
595
596 # If a group is marked as fuzzy then put all of the fuzzy part in the
597 # group.
598 if isinstance(element, Group):
599 element.subpattern = Fuzzy(element.subpattern, constraints)
600 sequence.append(element)
601 else:
602 sequence.append(Fuzzy(element, constraints))
603
604_QUANTIFIERS = {"?": (0, 1), "*": (0, None), "+": (1, None)}
605
606def parse_quantifier(source, info, ch):
607 "Parses a quantifier."
608 q = _QUANTIFIERS.get(ch)
609 if q:
610 # It's a quantifier.
611 return q
612
613 if ch == "{":
614 # Looks like a limited repeated element, eg. 'a{2,3}'.
615 counts = parse_limited_quantifier(source)
616 if counts:
617 return counts
618
619 return None
620
621def is_above_limit(count):
622 "Checks whether a count is above the maximum."
623 return count is not None and count >= UNLIMITED
624
625def parse_limited_quantifier(source):
626 "Parses a limited quantifier."
627 saved_pos = source.pos
628 min_count = parse_count(source)
629 if source.match(","):
630 max_count = parse_count(source)
631
632 # No minimum means 0 and no maximum means unlimited.
633 min_count = int(min_count or 0)
634 max_count = int(max_count) if max_count else None
635 else:
636 if not min_count:
637 source.pos = saved_pos
638 return None
639
640 min_count = max_count = int(min_count)
641
642 if not source.match ("}"):
643 source.pos = saved_pos
644 return None
645
646 if is_above_limit(min_count) or is_above_limit(max_count):
647 raise error("repeat count too big", source.string, saved_pos)
648
649 if max_count is not None and min_count > max_count:
650 raise error("min repeat greater than max repeat", source.string,
651 saved_pos)
652
653 return min_count, max_count
654
655def parse_fuzzy(source, info, ch, case_flags):
656 "Parses a fuzzy setting, if present."
657 saved_pos = source.pos
658
659 if ch != "{":
660 return None
661
662 constraints = {}
663 try:
664 parse_fuzzy_item(source, constraints)
665 while source.match(","):
666 parse_fuzzy_item(source, constraints)
667 except ParseError:
668 source.pos = saved_pos
669 return None
670
671 if source.match(":"):
672 constraints["test"] = parse_fuzzy_test(source, info, case_flags)
673
674 if not source.match("}"):
675 raise error("expected }", source.string, source.pos)
676
677 return constraints
678
679def parse_fuzzy_item(source, constraints):
680 "Parses a fuzzy setting item."
681 saved_pos = source.pos
682 try:
683 parse_cost_constraint(source, constraints)
684 except ParseError:
685 source.pos = saved_pos
686
687 parse_cost_equation(source, constraints)
688
689def parse_cost_constraint(source, constraints):
690 "Parses a cost constraint."
691 saved_pos = source.pos
692 ch = source.get()
693 if ch in ALPHA:
694 # Syntax: constraint [("<=" | "<") cost]
695 constraint = parse_constraint(source, constraints, ch)
696
697 max_inc = parse_fuzzy_compare(source)
698
699 if max_inc is None:
700 # No maximum cost.
701 constraints[constraint] = 0, None
702 else:
703 # There's a maximum cost.
704 cost_pos = source.pos
705 max_cost = parse_cost_limit(source)
706
707 # Inclusive or exclusive limit?
708 if not max_inc:
709 max_cost -= 1
710
711 if max_cost < 0:
712 raise error("bad fuzzy cost limit", source.string, cost_pos)
713
714 constraints[constraint] = 0, max_cost
715 elif ch in DIGITS:
716 # Syntax: cost ("<=" | "<") constraint ("<=" | "<") cost
717 source.pos = saved_pos
718
719 # Minimum cost.
720 cost_pos = source.pos
721 min_cost = parse_cost_limit(source)
722
723 min_inc = parse_fuzzy_compare(source)
724 if min_inc is None:
725 raise ParseError()
726
727 constraint = parse_constraint(source, constraints, source.get())
728
729 max_inc = parse_fuzzy_compare(source)
730 if max_inc is None:
731 raise ParseError()
732
733 # Maximum cost.
734 cost_pos = source.pos
735 max_cost = parse_cost_limit(source)
736
737 # Inclusive or exclusive limits?
738 if not min_inc:
739 min_cost += 1
740 if not max_inc:
741 max_cost -= 1
742
743 if not 0 <= min_cost <= max_cost:
744 raise error("bad fuzzy cost limit", source.string, cost_pos)
745
746 constraints[constraint] = min_cost, max_cost
747 else:
748 raise ParseError()
749
750def parse_cost_limit(source):
751 "Parses a cost limit."
752 cost_pos = source.pos
753 digits = parse_count(source)
754
755 try:
756 return int(digits)
757 except ValueError:
758 pass
759
760 raise error("bad fuzzy cost limit", source.string, cost_pos)
761
762def parse_constraint(source, constraints, ch):
763 "Parses a constraint."
764 if ch not in "deis":
765 raise ParseError()
766
767 if ch in constraints:
768 raise ParseError()
769
770 return ch
771
772def parse_fuzzy_compare(source):
773 "Parses a cost comparator."
774 if source.match("<="):
775 return True
776 elif source.match("<"):
777 return False
778 else:
779 return None
780
781def parse_cost_equation(source, constraints):
782 "Parses a cost equation."
783 if "cost" in constraints:
784 raise error("more than one cost equation", source.string, source.pos)
785
786 cost = {}
787
788 parse_cost_term(source, cost)
789 while source.match("+"):
790 parse_cost_term(source, cost)
791
792 max_inc = parse_fuzzy_compare(source)
793 if max_inc is None:
794 raise ParseError()
795
796 max_cost = int(parse_count(source))
797
798 if not max_inc:
799 max_cost -= 1
800
801 if max_cost < 0:
802 raise error("bad fuzzy cost limit", source.string, source.pos)
803
804 cost["max"] = max_cost
805
806 constraints["cost"] = cost
807
808def parse_cost_term(source, cost):
809 "Parses a cost equation term."
810 coeff = parse_count(source)
811 ch = source.get()
812 if ch not in "dis":
813 raise ParseError()
814
815 if ch in cost:
816 raise error("repeated fuzzy cost", source.string, source.pos)
817
818 cost[ch] = int(coeff or 1)
819
820def parse_fuzzy_test(source, info, case_flags):
821 saved_pos = source.pos
822 ch = source.get()
823 if ch in SPECIAL_CHARS:
824 if ch == "\\":
825 # An escape sequence outside a set.
826 return parse_escape(source, info, False)
827 elif ch == ".":
828 # Any character.
829 if info.flags & DOTALL:
830 return AnyAll()
831 elif info.flags & WORD:
832 return AnyU()
833 else:
834 return Any()
835 elif ch == "[":
836 # A character set.
837 return parse_set(source, info)
838 else:
839 raise error("expected character set", source.string, saved_pos)
840 elif ch:
841 # A literal.
842 return Character(ord(ch), case_flags=case_flags)
843 else:
844 raise error("expected character set", source.string, saved_pos)
845
846def parse_count(source):
847 "Parses a quantifier's count, which can be empty."
848 return source.get_while(DIGITS)
849
850def parse_paren(source, info):
851 """Parses a parenthesised subpattern or a flag. Returns FLAGS if it's an
852 inline flag.
853 """
854 saved_pos = source.pos
855 ch = source.get(True)
856 if ch == "?":
857 # (?...
858 saved_pos_2 = source.pos
859 ch = source.get(True)
860 if ch == "<":
861 # (?<...
862 saved_pos_3 = source.pos
863 ch = source.get()
864 if ch in ("=", "!"):
865 # (?<=... or (?<!...: lookbehind.
866 return parse_lookaround(source, info, True, ch == "=")
867
868 # (?<...: a named capture group.
869 source.pos = saved_pos_3
870 name = parse_name(source)
871 group = info.open_group(name)
872 source.expect(">")
873 saved_flags = info.flags
874 try:
875 subpattern = _parse_pattern(source, info)
876 source.expect(")")
877 finally:
878 info.flags = saved_flags
879 source.ignore_space = bool(info.flags & VERBOSE)
880
881 info.close_group()
882 return Group(info, group, subpattern)
883 if ch in ("=", "!"):
884 # (?=... or (?!...: lookahead.
885 return parse_lookaround(source, info, False, ch == "=")
886 if ch == "P":
887 # (?P...: a Python extension.
888 return parse_extension(source, info)
889 if ch == "#":
890 # (?#...: a comment.
891 return parse_comment(source)
892 if ch == "(":
893 # (?(...: a conditional subpattern.
894 return parse_conditional(source, info)
895 if ch == ">":
896 # (?>...: an atomic subpattern.
897 return parse_atomic(source, info)
898 if ch == "|":
899 # (?|...: a common/reset groups branch.
900 return parse_common(source, info)
901 if ch == "R" or "0" <= ch <= "9":
902 # (?R...: probably a call to a group.
903 return parse_call_group(source, info, ch, saved_pos_2)
904 if ch == "&":
905 # (?&...: a call to a named group.
906 return parse_call_named_group(source, info, saved_pos_2)
907 if (ch == "+" or ch == "-") and source.peek() in DIGITS:
908 return parse_rel_call_group(source, info, ch, saved_pos_2)
909
910 # (?...: probably a flags subpattern.
911 source.pos = saved_pos_2
912 return parse_flags_subpattern(source, info)
913
914 if ch == "*":
915 # (*...
916 saved_pos_2 = source.pos
917 word = source.get_while(set(")>"), include=False)
918 if word[ : 1].isalpha():
919 verb = VERBS.get(word)
920 if not verb:
921 raise error("unknown verb", source.string, saved_pos_2)
922
923 source.expect(")")
924
925 return verb
926
927 # (...: an unnamed capture group.
928 source.pos = saved_pos
929 group = info.open_group()
930 saved_flags = info.flags
931 try:
932 subpattern = _parse_pattern(source, info)
933 source.expect(")")
934 finally:
935 info.flags = saved_flags
936 source.ignore_space = bool(info.flags & VERBOSE)
937
938 info.close_group()
939
940 return Group(info, group, subpattern)
941
942def parse_extension(source, info):
943 "Parses a Python extension."
944 saved_pos = source.pos
945 ch = source.get()
946 if ch == "<":
947 # (?P<...: a named capture group.
948 name = parse_name(source)
949 group = info.open_group(name)
950 source.expect(">")
951 saved_flags = info.flags
952 try:
953 subpattern = _parse_pattern(source, info)
954 source.expect(")")
955 finally:
956 info.flags = saved_flags
957 source.ignore_space = bool(info.flags & VERBOSE)
958
959 info.close_group()
960
961 return Group(info, group, subpattern)
962 if ch == "=":
963 # (?P=...: a named group reference.
964 name = parse_name(source, allow_numeric=True)
965 source.expect(")")
966 if info.is_open_group(name):
967 raise error("cannot refer to an open group", source.string,
968 saved_pos)
969
970 return make_ref_group(info, name, saved_pos)
971 if ch == ">" or ch == "&":
972 # (?P>...: a call to a group.
973 return parse_call_named_group(source, info, saved_pos)
974
975 source.pos = saved_pos
976 raise error("unknown extension", source.string, saved_pos)
977
978def parse_comment(source):
979 "Parses a comment."
980 while True:
981 saved_pos = source.pos
982 c = source.get(True)
983
984 if not c or c == ")":
985 break
986
987 if c == "\\":
988 c = source.get(True)
989
990 source.pos = saved_pos
991 source.expect(")")
992
993 return None
994
995def parse_lookaround(source, info, behind, positive):
996 "Parses a lookaround."
997 saved_flags = info.flags
998 try:
999 subpattern = _parse_pattern(source, info)
1000 source.expect(")")
1001 finally:
1002 info.flags = saved_flags
1003 source.ignore_space = bool(info.flags & VERBOSE)
1004
1005 return LookAround(behind, positive, subpattern)
1006
1007def parse_conditional(source, info):
1008 "Parses a conditional subpattern."
1009 saved_flags = info.flags
1010 saved_pos = source.pos
1011 ch = source.get()
1012 if ch == "?":
1013 # (?(?...
1014 ch = source.get()
1015 if ch in ("=", "!"):
1016 # (?(?=... or (?(?!...: lookahead conditional.
1017 return parse_lookaround_conditional(source, info, False, ch == "=")
1018 if ch == "<":
1019 # (?(?<...
1020 ch = source.get()
1021 if ch in ("=", "!"):
1022 # (?(?<=... or (?(?<!...: lookbehind conditional.
1023 return parse_lookaround_conditional(source, info, True, ch ==
1024 "=")
1025
1026 source.pos = saved_pos
1027 raise error("expected lookaround conditional", source.string,
1028 source.pos)
1029
1030 source.pos = saved_pos
1031 try:
1032 group = parse_name(source, True)
1033 source.expect(")")
1034 yes_branch = parse_sequence(source, info)
1035 if source.match("|"):
1036 no_branch = parse_sequence(source, info)
1037 else:
1038 no_branch = Sequence()
1039
1040 source.expect(")")
1041 finally:
1042 info.flags = saved_flags
1043 source.ignore_space = bool(info.flags & VERBOSE)
1044
1045 if yes_branch.is_empty() and no_branch.is_empty():
1046 return Sequence()
1047
1048 return Conditional(info, group, yes_branch, no_branch, saved_pos)
1049
1050def parse_lookaround_conditional(source, info, behind, positive):
1051 saved_flags = info.flags
1052 try:
1053 subpattern = _parse_pattern(source, info)
1054 source.expect(")")
1055 finally:
1056 info.flags = saved_flags
1057 source.ignore_space = bool(info.flags & VERBOSE)
1058
1059 yes_branch = parse_sequence(source, info)
1060 if source.match("|"):
1061 no_branch = parse_sequence(source, info)
1062 else:
1063 no_branch = Sequence()
1064
1065 source.expect(")")
1066
1067 return LookAroundConditional(behind, positive, subpattern, yes_branch,
1068 no_branch)
1069
1070def parse_atomic(source, info):
1071 "Parses an atomic subpattern."
1072 saved_flags = info.flags
1073 try:
1074 subpattern = _parse_pattern(source, info)
1075 source.expect(")")
1076 finally:
1077 info.flags = saved_flags
1078 source.ignore_space = bool(info.flags & VERBOSE)
1079
1080 return Atomic(subpattern)
1081
1082def parse_common(source, info):
1083 "Parses a common groups branch."
1084 # Capture group numbers in different branches can reuse the group numbers.
1085 initial_group_count = info.group_count
1086 branches = [parse_sequence(source, info)]
1087 final_group_count = info.group_count
1088 while source.match("|"):
1089 info.group_count = initial_group_count
1090 branches.append(parse_sequence(source, info))
1091 final_group_count = max(final_group_count, info.group_count)
1092
1093 info.group_count = final_group_count
1094 source.expect(")")
1095
1096 if len(branches) == 1:
1097 return branches[0]
1098 return Branch(branches)
1099
1100def parse_call_group(source, info, ch, pos):
1101 "Parses a call to a group."
1102 if ch == "R":
1103 group = "0"
1104 else:
1105 group = ch + source.get_while(DIGITS)
1106
1107 source.expect(")")
1108
1109 return CallGroup(info, group, pos)
1110
1111def parse_rel_call_group(source, info, ch, pos):
1112 "Parses a relative call to a group."
1113 digits = source.get_while(DIGITS)
1114 if not digits:
1115 raise error("missing relative group number", source.string, source.pos)
1116
1117 offset = int(digits)
1118 group = info.group_count + offset if ch == "+" else info.group_count - offset + 1
1119 if group <= 0:
1120 raise error("invalid relative group number", source.string, source.pos)
1121
1122 source.expect(")")
1123
1124 return CallGroup(info, group, pos)
1125
1126def parse_call_named_group(source, info, pos):
1127 "Parses a call to a named group."
1128 group = parse_name(source)
1129 source.expect(")")
1130
1131 return CallGroup(info, group, pos)
1132
1133def parse_flag_set(source):
1134 "Parses a set of inline flags."
1135 flags = 0
1136
1137 try:
1138 while True:
1139 saved_pos = source.pos
1140 ch = source.get()
1141 if ch == "V":
1142 ch += source.get()
1143 flags |= REGEX_FLAGS[ch]
1144 except KeyError:
1145 source.pos = saved_pos
1146
1147 return flags
1148
1149def parse_flags(source, info):
1150 "Parses flags being turned on/off."
1151 flags_on = parse_flag_set(source)
1152 if source.match("-"):
1153 flags_off = parse_flag_set(source)
1154 if not flags_off:
1155 raise error("bad inline flags: no flags after '-'", source.string,
1156 source.pos)
1157 else:
1158 flags_off = 0
1159
1160 if flags_on & LOCALE:
1161 # Remember that this pattern as an inline locale flag.
1162 info.inline_locale = True
1163
1164 return flags_on, flags_off
1165
1166def parse_subpattern(source, info, flags_on, flags_off):
1167 "Parses a subpattern with scoped flags."
1168 saved_flags = info.flags
1169 info.flags = (info.flags | flags_on) & ~flags_off
1170
1171 # Ensure that there aren't multiple encoding flags set.
1172 if info.flags & (ASCII | LOCALE | UNICODE):
1173 info.flags = (info.flags & ~_ALL_ENCODINGS) | flags_on
1174
1175 source.ignore_space = bool(info.flags & VERBOSE)
1176 try:
1177 subpattern = _parse_pattern(source, info)
1178 source.expect(")")
1179 finally:
1180 info.flags = saved_flags
1181 source.ignore_space = bool(info.flags & VERBOSE)
1182
1183 return subpattern
1184
1185def parse_flags_subpattern(source, info):
1186 """Parses a flags subpattern. It could be inline flags or a subpattern
1187 possibly with local flags. If it's a subpattern, then that's returned;
1188 if it's a inline flags, then None is returned.
1189 """
1190 flags_on, flags_off = parse_flags(source, info)
1191
1192 if flags_off & GLOBAL_FLAGS:
1193 raise error("bad inline flags: cannot turn off global flag",
1194 source.string, source.pos)
1195
1196 if flags_on & flags_off:
1197 raise error("bad inline flags: flag turned on and off", source.string,
1198 source.pos)
1199
1200 # Handle flags which are global in all regex behaviours.