#
# Secret Labs' Regular Expression Engine core module
#
# Copyright (c) 1998-2001 by Secret Labs AB. All rights reserved.
#
# This version of the SRE library can be redistributed under CNRI's
# Python 1.6 license. For any other use, please contact Secret Labs
# AB (info@pythonware.com).
#
# Portions of this engine have been developed in cooperation with
# CNRI. Hewlett-Packard provided funding for 1.6 integration and
# other compatibility work.
#
# 2010-01-16 mrab Python front-end re-written and extended
import enum
import string
import unicodedata
from collections import defaultdict
import regex._regex as _regex
__all__ = ["A", "ASCII", "B", "BESTMATCH", "D", "DEBUG", "E", "ENHANCEMATCH",
"F", "FULLCASE", "I", "IGNORECASE", "L", "LOCALE", "M", "MULTILINE", "P",
"POSIX", "R", "REVERSE", "S", "DOTALL", "T", "TEMPLATE", "U", "UNICODE",
"V0", "VERSION0", "V1", "VERSION1", "W", "WORD", "X", "VERBOSE", "error",
"Scanner", "RegexFlag"]
# The regex exception.
class error(Exception):
"""Exception raised for invalid regular expressions.
Attributes:
msg: The unformatted error message
pattern: The regular expression pattern
pos: The position in the pattern where compilation failed, or None
lineno: The line number where compilation failed, unless pos is None
colno: The column number where compilation failed, unless pos is None
"""
def __init__(self, message, pattern=None, pos=None):
newline = '\n' if isinstance(pattern, str) else b'\n'
self.msg = message
self.pattern = pattern
self.pos = pos
if pattern is not None and pos is not None:
self.lineno = pattern.count(newline, 0, pos) + 1
self.colno = pos - pattern.rfind(newline, 0, pos)
message = "{} at position {}".format(message, pos)
if newline in pattern:
message += " (line {}, column {})".format(self.lineno,
self.colno)
Exception.__init__(self, message)
# The exception for when a positional flag has been turned on in the old
# behaviour.
class _UnscopedFlagSet(Exception):
pass
# The exception for when parsing fails and we want to try something else.
class ParseError(Exception):
pass
# The exception for when there isn't a valid first set.
class _FirstSetError(Exception):
pass
# Flags.
class RegexFlag(enum.IntFlag):
A = ASCII = 0x80 # Assume ASCII locale.
B = BESTMATCH = 0x1000 # Best fuzzy match.
D = DEBUG = 0x200 # Print parsed pattern.
E = ENHANCEMATCH = 0x8000 # Attempt to improve the fit after finding the first
# fuzzy match.
F = FULLCASE = 0x4000 # Unicode full case-folding.
I = IGNORECASE = 0x2 # Ignore case.
L = LOCALE = 0x4 # Assume current 8-bit locale.
M = MULTILINE = 0x8 # Make anchors look for newline.
P = POSIX = 0x10000 # POSIX-style matching (leftmost longest).
R = REVERSE = 0x400 # Search backwards.
S = DOTALL = 0x10 # Make dot match newline.
U = UNICODE = 0x20 # Assume Unicode locale.
V0 = VERSION0 = 0x2000 # Old legacy behaviour.
V1 = VERSION1 = 0x100 # New enhanced behaviour.
W = WORD = 0x800 # Default Unicode word breaks.
X = VERBOSE = 0x40 # Ignore whitespace and comments.
T = TEMPLATE = 0x1 # Template (present because re module has it).
def __repr__(self):
if self._name_ is not None:
return 'regex.%s' % self._name_
value = self._value_
members = []
negative = value < 0
if negative:
value = ~value
for m in self.__class__:
if value & m._value_:
value &= ~m._value_
members.append('regex.%s' % m._name_)
if value:
members.append(hex(value))
res = '|'.join(members)
if negative:
if len(members) > 1:
res = '~(%s)' % res
else:
res = '~%s' % res
return res
__str__ = object.__str__
globals().update(RegexFlag.__members__)
DEFAULT_VERSION = VERSION1
_ALL_VERSIONS = VERSION0 | VERSION1
_ALL_ENCODINGS = ASCII | LOCALE | UNICODE
# The default flags for the various versions.
DEFAULT_FLAGS = {VERSION0: 0, VERSION1: FULLCASE}
# The mask for the flags.
GLOBAL_FLAGS = (_ALL_VERSIONS | BESTMATCH | DEBUG | ENHANCEMATCH | POSIX |
REVERSE)
SCOPED_FLAGS = (FULLCASE | IGNORECASE | MULTILINE | DOTALL | WORD | VERBOSE |
_ALL_ENCODINGS)
ALPHA = frozenset(string.ascii_letters)
DIGITS = frozenset(string.digits)
ALNUM = ALPHA | DIGITS
OCT_DIGITS = frozenset(string.octdigits)
HEX_DIGITS = frozenset(string.hexdigits)
SPECIAL_CHARS = frozenset("()|?*+{^$.[\\#") | frozenset([""])
NAMED_CHAR_PART = ALNUM | frozenset(" -")
PROPERTY_NAME_PART = ALNUM | frozenset(" &_-.")
SET_OPS = ("||", "~~", "&&", "--")
# The width of the code words inside the regex engine.
BYTES_PER_CODE = _regex.get_code_size()
BITS_PER_CODE = BYTES_PER_CODE * 8
# The repeat count which represents infinity.
UNLIMITED = (1 << BITS_PER_CODE) - 1
# The regular expression flags.
REGEX_FLAGS = {"a": ASCII, "b": BESTMATCH, "e": ENHANCEMATCH, "f": FULLCASE,
"i": IGNORECASE, "L": LOCALE, "m": MULTILINE, "p": POSIX, "r": REVERSE,
"s": DOTALL, "u": UNICODE, "V0": VERSION0, "V1": VERSION1, "w": WORD, "x":
VERBOSE}
# The case flags.
CASE_FLAGS = FULLCASE | IGNORECASE
NOCASE = 0
FULLIGNORECASE = FULLCASE | IGNORECASE
FULL_CASE_FOLDING = UNICODE | FULLIGNORECASE
CASE_FLAGS_COMBINATIONS = {0: 0, FULLCASE: 0, IGNORECASE: IGNORECASE,
FULLIGNORECASE: FULLIGNORECASE}
# The number of digits in hexadecimal escapes.
HEX_ESCAPES = {"x": 2, "u": 4, "U": 8}
# The names of the opcodes.
OPCODES = """
FAILURE
SUCCESS
ANY
ANY_ALL
ANY_ALL_REV
ANY_REV
ANY_U
ANY_U_REV
ATOMIC
BOUNDARY
BRANCH
CALL_REF
CHARACTER
CHARACTER_IGN
CHARACTER_IGN_REV
CHARACTER_REV
CONDITIONAL
DEFAULT_BOUNDARY
DEFAULT_END_OF_WORD
DEFAULT_START_OF_WORD
END
END_OF_LINE
END_OF_LINE_U
END_OF_STRING
END_OF_STRING_LINE
END_OF_STRING_LINE_U
END_OF_WORD
FUZZY
GRAPHEME_BOUNDARY
GREEDY_REPEAT
GROUP
GROUP_CALL
GROUP_EXISTS
KEEP
LAZY_REPEAT
LOOKAROUND
NEXT
PROPERTY
PROPERTY_IGN
PROPERTY_IGN_REV
PROPERTY_REV
PRUNE
RANGE
RANGE_IGN
RANGE_IGN_REV
RANGE_REV
REF_GROUP
REF_GROUP_FLD
REF_GROUP_FLD_REV
REF_GROUP_IGN
REF_GROUP_IGN_REV
REF_GROUP_REV
SEARCH_ANCHOR
SET_DIFF
SET_DIFF_IGN
SET_DIFF_IGN_REV
SET_DIFF_REV
SET_INTER
SET_INTER_IGN
SET_INTER_IGN_REV
SET_INTER_REV
SET_SYM_DIFF
SET_SYM_DIFF_IGN
SET_SYM_DIFF_IGN_REV
SET_SYM_DIFF_REV
SET_UNION
SET_UNION_IGN
SET_UNION_IGN_REV
SET_UNION_REV
SKIP
START_OF_LINE
START_OF_LINE_U
START_OF_STRING
START_OF_WORD
STRING
STRING_FLD
STRING_FLD_REV
STRING_IGN
STRING_IGN_REV
STRING_REV
FUZZY_EXT
"""
# Define the opcodes in a namespace.
class Namespace:
pass
OP = Namespace()
for i, op in enumerate(OPCODES.split()):
setattr(OP, op, i)
def _shrink_cache(cache_dict, args_dict, locale_sensitive, max_length, divisor=5):
"""Make room in the given cache.
Args:
cache_dict: The cache dictionary to modify.
args_dict: The dictionary of named list args used by patterns.
max_length: Maximum # of entries in cache_dict before it is shrunk.
divisor: Cache will shrink to max_length - 1/divisor*max_length items.
"""
# Toss out a fraction of the entries at random to make room for new ones.
# A random algorithm was chosen as opposed to simply cache_dict.popitem()
# as popitem could penalize the same regular expression repeatedly based
# on its internal hash value. Being random should spread the cache miss
# love around.
cache_keys = tuple(cache_dict.keys())
overage = len(cache_keys) - max_length
if overage < 0:
# Cache is already within limits. Normally this should not happen
# but it could due to multithreading.
return
number_to_toss = max_length // divisor + overage
# The import is done here to avoid a circular dependency.
import random
if not hasattr(random, 'sample'):
# Do nothing while resolving the circular dependency:
# re->random->warnings->tokenize->string->re
return
for doomed_key in random.sample(cache_keys, number_to_toss):
try:
del cache_dict[doomed_key]
except KeyError:
# Ignore problems if the cache changed from another thread.
pass
# Rebuild the arguments and locale-sensitivity dictionaries.
args_dict.clear()
sensitivity_dict = {}
for pattern, pattern_type, flags, args, default_version, locale in tuple(cache_dict):
args_dict[pattern, pattern_type, flags, default_version, locale] = args
try:
sensitivity_dict[pattern_type, pattern] = locale_sensitive[pattern_type, pattern]
except KeyError:
pass
locale_sensitive.clear()
locale_sensitive.update(sensitivity_dict)
def _fold_case(info, string):
"Folds the case of a string."
flags = info.flags
if (flags & _ALL_ENCODINGS) == 0:
flags |= info.guess_encoding
return _regex.fold_case(flags, string)
def is_cased_i(info, char):
"Checks whether a character is cased."
return len(_regex.get_all_cases(info.flags, char)) > 1
def is_cased_f(flags, char):
"Checks whether a character is cased."
return len(_regex.get_all_cases(flags, char)) > 1
def _compile_firstset(info, fs):
"Compiles the firstset for the pattern."
reverse = bool(info.flags & REVERSE)
fs = _check_firstset(info, reverse, fs)
if not fs:
return []
# Compile the firstset.
return fs.compile(reverse)
def _check_firstset(info, reverse, fs):
"Checks the firstset for the pattern."
if not fs or None in fs:
return None
# If we ignore the case, for simplicity we won't build a firstset.
members = set()
case_flags = NOCASE
for i in fs:
if isinstance(i, Character) and not i.positive:
return None
# if i.case_flags:
# if isinstance(i, Character):
# if is_cased_i(info, i.value):
# return []
# elif isinstance(i, SetBase):
# return []
case_flags |= i.case_flags
members.add(i.with_flags(case_flags=NOCASE))
if case_flags == (FULLCASE | IGNORECASE):
return None
# Build the firstset.
fs = SetUnion(info, list(members), case_flags=case_flags & ~FULLCASE,
zerowidth=True)
fs = fs.optimise(info, reverse, in_set=True)
return fs
def _flatten_code(code):
"Flattens the code from a list of tuples."
flat_code = []
for c in code:
flat_code.extend(c)
return flat_code
def make_case_flags(info):
"Makes the case flags."
flags = info.flags & CASE_FLAGS
# Turn off FULLCASE if ASCII is turned on.
if info.flags & ASCII:
flags &= ~FULLCASE
return flags
def make_character(info, value, in_set=False):
"Makes a character literal."
if in_set:
# A character set is built case-sensitively.
return Character(value)
return Character(value, case_flags=make_case_flags(info))
def make_ref_group(info, name, position):
"Makes a group reference."
return RefGroup(info, name, position, case_flags=make_case_flags(info))
def make_string_set(info, name):
"Makes a string set."
return StringSet(info, name, case_flags=make_case_flags(info))
def make_property(info, prop, in_set):
"Makes a property."
if in_set:
return prop
return prop.with_flags(case_flags=make_case_flags(info))
def _parse_pattern(source, info):
"Parses a pattern, eg. 'a|b|c'."
branches = [parse_sequence(source, info)]
while source.match("|"):
branches.append(parse_sequence(source, info))
if len(branches) == 1:
return branches[0]
return Branch(branches)
def parse_sequence(source, info):
"Parses a sequence, eg. 'abc'."
sequence = [None]
case_flags = make_case_flags(info)
while True:
saved_pos = source.pos
ch = source.get()
if ch in SPECIAL_CHARS:
if ch in ")|":
# The end of a sequence. At the end of the pattern ch is "".
source.pos = saved_pos
break
elif ch == "\\":
# An escape sequence outside a set.
sequence.append(parse_escape(source, info, False))
elif ch == "(":
# A parenthesised subpattern or a flag.
element = parse_paren(source, info)
if element is None:
case_flags = make_case_flags(info)
else:
sequence.append(element)
elif ch == ".":
# Any character.
if info.flags & DOTALL:
sequence.append(AnyAll())
elif info.flags & WORD:
sequence.append(AnyU())
else:
sequence.append(Any())
elif ch == "[":
# A character set.
sequence.append(parse_set(source, info))
elif ch == "^":
# The start of a line or the string.
if info.flags & MULTILINE:
if info.flags & WORD:
sequence.append(StartOfLineU())
else:
sequence.append(StartOfLine())
else:
sequence.append(StartOfString())
elif ch == "$":
# The end of a line or the string.
if info.flags & MULTILINE:
if info.flags & WORD:
sequence.append(EndOfLineU())
else:
sequence.append(EndOfLine())
else:
if info.flags & WORD:
sequence.append(EndOfStringLineU())
else:
sequence.append(EndOfStringLine())
elif ch in "?*+{":
# Looks like a quantifier.
counts = parse_quantifier(source, info, ch)
if counts:
# It _is_ a quantifier.
apply_quantifier(source, info, counts, case_flags, ch,
saved_pos, sequence)
sequence.append(None)
else:
# It's not a quantifier. Maybe it's a fuzzy constraint.
constraints = parse_fuzzy(source, info, ch, case_flags)
if constraints:
# It _is_ a fuzzy constraint.
apply_constraint(source, info, constraints, case_flags,
saved_pos, sequence)
sequence.append(None)
else:
# The element was just a literal.
sequence.append(Character(ord(ch),
case_flags=case_flags))
else:
# A literal.
sequence.append(Character(ord(ch), case_flags=case_flags))
else:
# A literal.
sequence.append(Character(ord(ch), case_flags=case_flags))
sequence = [item for item in sequence if item is not None]
return Sequence(sequence)
def apply_quantifier(source, info, counts, case_flags, ch, saved_pos,
sequence):
element = sequence.pop()
if element is None:
if sequence:
raise error("multiple repeat", source.string, saved_pos)
raise error("nothing to repeat", source.string, saved_pos)
if isinstance(element, (GreedyRepeat, LazyRepeat, PossessiveRepeat)):
raise error("multiple repeat", source.string, saved_pos)
min_count, max_count = counts
saved_pos = source.pos
ch = source.get()
if ch == "?":
# The "?" suffix that means it's a lazy repeat.
repeated = LazyRepeat
elif ch == "+":
# The "+" suffix that means it's a possessive repeat.
repeated = PossessiveRepeat
else:
# No suffix means that it's a greedy repeat.
source.pos = saved_pos
repeated = GreedyRepeat
# Ignore the quantifier if it applies to a zero-width item or the number of
# repeats is fixed at 1.
if not element.is_empty() and (min_count != 1 or max_count != 1):
element = repeated(element, min_count, max_count)
sequence.append(element)
def apply_constraint(source, info, constraints, case_flags, saved_pos,
sequence):
element = sequence.pop()
if element is None:
raise error("nothing for fuzzy constraint", source.string, saved_pos)
# If a group is marked as fuzzy then put all of the fuzzy part in the
# group.
if isinstance(element, Group):
element.subpattern = Fuzzy(element.subpattern, constraints)
sequence.append(element)
else:
sequence.append(Fuzzy(element, constraints))
_QUANTIFIERS = {"?": (0, 1), "*": (0, None), "+": (1, None)}
def parse_quantifier(source, info, ch):
"Parses a quantifier."
q = _QUANTIFIERS.get(ch)
if q:
# It's a quantifier.
return q
if ch == "{":
# Looks like a limited repeated element, eg. 'a{2,3}'.
counts = parse_limited_quantifier(source)
if counts:
return counts
return None
def is_above_limit(count):
"Checks whether a count is above the maximum."
return count is not None and count >= UNLIMITED
def parse_limited_quantifier(source):
"Parses a limited quantifier."
saved_pos = source.pos
min_count = parse_count(source)
if source.match(","):
max_count = parse_count(source)
# No minimum means 0 and no maximum means unlimited.
min_count = int(min_count or 0)
max_count = int(max_count) if max_count else None
else:
if not min_count:
source.pos = saved_pos
return None
min_count = max_count = int(min_count)
if not source.match ("}"):
source.pos = saved_pos
return None
if is_above_limit(min_count) or is_above_limit(max_count):
raise error("repeat count too big", source.string, saved_pos)
if max_count is not None and min_count > max_count:
raise error("min repeat greater than max repeat", source.string,
saved_pos)
return min_count, max_count
def parse_fuzzy(source, info, ch, case_flags):
"Parses a fuzzy setting, if present."
saved_pos = source.pos
if ch != "{":
return None
constraints = {}
try:
parse_fuzzy_item(source, constraints)
while source.match(","):
parse_fuzzy_item(source, constraints)
except ParseError:
source.pos = saved_pos
return None
if source.match(":"):
constraints["test"] = parse_fuzzy_test(source, info, case_flags)
if not source.match("}"):
raise error("expected }", source.string, source.pos)
return constraints
def parse_fuzzy_item(source, constraints):
"Parses a fuzzy setting item."
saved_pos = source.pos
try:
parse_cost_constraint(source, constraints)
except ParseError:
source.pos = saved_pos
parse_cost_equation(source, constraints)
def parse_cost_constraint(source, constraints):
"Parses a cost constraint."
saved_pos = source.pos
ch = source.get()
if ch in ALPHA:
# Syntax: constraint [("<=" | "<") cost]
constraint = parse_constraint(source, constraints, ch)
max_inc = parse_fuzzy_compare(source)
if max_inc is None:
# No maximum cost.
constraints[constraint] = 0, None
else:
# There's a maximum cost.
cost_pos = source.pos
max_cost = parse_cost_limit(source)
# Inclusive or exclusive limit?
if not max_inc:
max_cost -= 1
if max_cost < 0:
raise error("bad fuzzy cost limit", source.string, cost_pos)
constraints[constraint] = 0, max_cost
elif ch in DIGITS:
# Syntax: cost ("<=" | "<") constraint ("<=" | "<") cost
source.pos = saved_pos
# Minimum cost.
cost_pos = source.pos
min_cost = parse_cost_limit(source)
min_inc = parse_fuzzy_compare(source)
if min_inc is None:
raise ParseError()
constraint = parse_constraint(source, constraints, source.get())
max_inc = parse_fuzzy_compare(source)
if max_inc is None:
raise ParseError()
# Maximum cost.
cost_pos = source.pos
max_cost = parse_cost_limit(source)
# Inclusive or exclusive limits?
if not min_inc:
min_cost += 1
if not max_inc:
max_cost -= 1
if not 0 <= min_cost <= max_cost:
raise error("bad fuzzy cost limit", source.string, cost_pos)
constraints[constraint] = min_cost, max_cost
else:
raise ParseError()
def parse_cost_limit(source):
"Parses a cost limit."
cost_pos = source.pos
digits = parse_count(source)
try:
return int(digits)
except ValueError:
pass
raise error("bad fuzzy cost limit", source.string, cost_pos)
def parse_constraint(source, constraints, ch):
"Parses a constraint."
if ch not in "deis":
raise ParseError()
if ch in constraints:
raise ParseError()
return ch
def parse_fuzzy_compare(source):
"Parses a cost comparator."
if source.match("<="):
return True
elif source.match("<"):
return False
else:
return None
def parse_cost_equation(source, constraints):
"Parses a cost equation."
if "cost" in constraints:
raise error("more than one cost equation", source.string, source.pos)
cost = {}
parse_cost_term(source, cost)
while source.match("+"):
parse_cost_term(source, cost)
max_inc = parse_fuzzy_compare(source)
if max_inc is None:
raise ParseError()
max_cost = int(parse_count(source))
if not max_inc:
max_cost -= 1
if max_cost < 0:
raise error("bad fuzzy cost limit", source.string, source.pos)
cost["max"] = max_cost
constraints["cost"] = cost
def parse_cost_term(source, cost):
"Parses a cost equation term."
coeff = parse_count(source)
ch = source.get()
if ch not in "dis":
raise ParseError()
if ch in cost:
raise error("repeated fuzzy cost", source.string, source.pos)
cost[ch] = int(coeff or 1)
def parse_fuzzy_test(source, info, case_flags):
saved_pos = source.pos
ch = source.get()
if ch in SPECIAL_CHARS:
if ch == "\\":
# An escape sequence outside a set.
return parse_escape(source, info, False)
elif ch == ".":
# Any character.
if info.flags & DOTALL:
return AnyAll()
elif info.flags & WORD:
return AnyU()
else:
return Any()
elif ch == "[":
# A character set.
return parse_set(source, info)
else:
raise error("expected character set", source.string, saved_pos)
elif ch:
# A literal.
return Character(ord(ch), case_flags=case_flags)
else:
raise error("expected character set", source.string, saved_pos)
def parse_count(source):
"Parses a quantifier's count, which can be empty."
return source.get_while(DIGITS)
def parse_paren(source, info):
"""Parses a parenthesised subpattern or a flag. Returns FLAGS if it's an
inline flag.
"""
saved_pos = source.pos
ch = source.get(True)
if ch == "?":
# (?...
saved_pos_2 = source.pos
ch = source.get(True)
if ch == "<":
# (?<...
saved_pos_3 = source.pos
ch = source.get()
if ch in ("=", "!"):
# (?<=... or (?<!...: lookbehind.
return parse_lookaround(source, info, True, ch == "=")
# (?<...: a named capture group.
source.pos = saved_pos_3
name = parse_name(source)
group = info.open_group(name)
source.expect(">")
saved_flags = info.flags
try:
subpattern = _parse_pattern(source, info)
source.expect(")")
finally:
info.flags = saved_flags
source.ignore_space = bool(info.flags & VERBOSE)
info.close_group()
return Group(info, group, subpattern)
if ch in ("=", "!"):
# (?=... or (?!...: lookahead.
return parse_lookaround(source, info, False, ch == "=")
if ch == "P":
# (?P...: a Python extension.
return parse_extension(source, info)
if ch == "#":
# (?#...: a comment.
return parse_comment(source)
if ch == "(":
# (?(...: a conditional subpattern.
return parse_conditional(source, info)
if ch == ">":
# (?>...: an atomic subpattern.
return parse_atomic(source, info)
if ch == "|":
# (?|...: a common/reset groups branch.
return parse_common(source, info)
if ch == "R" or "0" <= ch <= "9":
# (?R...: probably a call to a group.
return parse_call_group(source, info, ch, saved_pos_2)
if ch == "&":
# (?&...: a call to a named group.
return parse_call_named_group(source, info, saved_pos_2)
# (?...: probably a flags subpattern.
source.pos = saved_pos_2
return parse_flags_subpattern(source, info)
if ch == "*":
# (*...
saved_pos_2 = source.pos
word = source.get_while(set(")>"), include=False)
if word[ : 1].isalpha():
verb = VERBS.get(word)
if not verb:
raise error("unknown verb", source.string, saved_pos_2)
source.expect(")")
return verb
# (...: an unnamed capture group.
source.pos = saved_pos
group = info.open_group()
saved_flags = info.flags
try:
subpattern = _parse_pattern(source, info)
source.expect(")")
finally:
info.flags = saved_flags
source.ignore_space = bool(info.flags & VERBOSE)
info.close_group()
return Group(info, group, subpattern)
def parse_extension(source, info):
"Parses a Python extension."
saved_pos = source.pos
ch = source.get()
if ch == "<":
# (?P<...: a named capture group.
name = parse_name(source)
group = info.open_group(name)
source.expect(">")
saved_flags = info.flags
try:
subpattern = _parse_pattern(source, info)
source.expect(")")
finally:
info.flags = saved_flags
source.ignore_space = bool(info.flags & VERBOSE)
info.close_group()
return Group(info, group, subpattern)
if ch == "=":
# (?P=...: a named group reference.
name = parse_name(source, allow_numeric=True)
source.expect(")")
if info.is_open_group(name):
raise error("cannot refer to an open group", source.string,
saved_pos)
return make_ref_group(info, name, saved_pos)
if ch == ">" or ch == "&":
# (?P>...: a call to a group.
return parse_call_named_group(source, info, saved_pos)
source.pos = saved_pos
raise error("unknown extension", source.string, saved_pos)
def parse_comment(source):
"Parses a comment."
while True:
saved_pos = source.pos
c = source.get(True)
if not c or c == ")":
break
if c == "\\":
c = source.get(True)
source.pos = saved_pos
source.expect(")")
return None
def parse_lookaround(source, info, behind, positive):
"Parses a lookaround."
saved_flags = info.flags
try:
subpattern = _parse_pattern(source, info)
source.expect(")")
finally:
info.flags = saved_flags
source.ignore_space = bool(info.flags & VERBOSE)
return LookAround(behind, positive, subpattern)
def parse_conditional(source, info):
"Parses a conditional subpattern."
saved_flags = info.flags
saved_pos = source.pos
ch = source.get()
if ch == "?":
# (?(?...
ch = source.get()
if ch in ("=", "!"):
# (?(?=... or (?(?!...: lookahead conditional.
return parse_lookaround_conditional(source, info, False, ch == "=")
if ch == "<":
# (?(?<...
ch = source.get()
if ch in ("=", "!"):
# (?(?<=... or (?(?<!...: lookbehind conditional.
return parse_lookaround_conditional(source, info, True, ch ==
"=")
source.pos = saved_pos
raise error("expected lookaround conditional", source.string,
source.pos)
source.pos = saved_pos
try:
group = parse_name(source, True)
source.expect(")")
yes_branch = parse_sequence(source, info)
if source.match("|"):
no_branch = parse_sequence(source, info)
else:
no_branch = Sequence()
source.expect(")")
finally:
info.flags = saved_flags
source.ignore_space = bool(info.flags & VERBOSE)
if yes_branch.is_empty() and no_branch.is_empty():
return Sequence()
return Conditional(info, group, yes_branch, no_branch, saved_pos)
def parse_lookaround_conditional(source, info, behind, positive):
saved_flags = info.flags
try:
subpattern = _parse_pattern(source, info)
source.expect(")")
finally:
info.flags = saved_flags
source.ignore_space = bool(info.flags & VERBOSE)
yes_branch = parse_sequence(source, info)
if source.match("|"):
no_branch = parse_sequence(source, info)
else:
no_branch = Sequence()
source.expect(")")
return LookAroundConditional(behind, positive, subpattern, yes_branch,
no_branch)
def parse_atomic(source, info):
"Parses an atomic subpattern."
saved_flags = info.flags
try:
subpattern = _parse_pattern(source, info)
source.expect(")")
finally:
info.flags = saved_flags
source.ignore_space = bool(info.flags & VERBOSE)
return Atomic(subpattern)
def parse_common(source, info):
"Parses a common groups branch."
# Capture group numbers in different branches can reuse the group numbers.
initial_group_count = info.group_count
branches = [parse_sequence(source, info)]
final_group_count = info.group_count
while source.match("|"):
info.group_count = initial_group_count
branches.append(parse_sequence(source, info))
final_group_count = max(final_group_count, info.group_count)
info.group_count = final_group_count
source.expect(")")
if len(branches) == 1:
return branches[0]
return Branch(branches)
def parse_call_group(source, info, ch, pos):
"Parses a call to a group."
if ch == "R":
group = "0"
else:
group = ch + source.get_while(DIGITS)
source.expect(")")
return CallGroup(info, group, pos)
def parse_call_named_group(source, info, pos):
"Parses a call to a named group."
group = parse_name(source)
source.expect(")")
return CallGroup(info, group, pos)
def parse_flag_set(source):
"Parses a set of inline flags."
flags = 0
try:
while True:
saved_pos = source.pos
ch = source.get()
if ch == "V":
ch += source.get()
flags |= REGEX_FLAGS[ch]
except KeyError:
source.pos = saved_pos
return flags
def parse_flags(source, info):
"Parses flags being turned on/off."
flags_on = parse_flag_set(source)
if source.match("-"):
flags_off = parse_flag_set(source)
if not flags_off:
raise error("bad inline flags: no flags after '-'", source.string,
source.pos)
else:
flags_off = 0
if flags_on & LOCALE:
# Remember that this pattern as an inline locale flag.
info.inline_locale = True
return flags_on, flags_off
def parse_subpattern(source, info, flags_on, flags_off):
"Parses a subpattern with scoped flags."
saved_flags = info.flags
info.flags = (info.flags | flags_on) & ~flags_off
source.ignore_space = bool(info.flags & VERBOSE)
try:
subpattern = _parse_pattern(source, info)
source.expect(")")
finally:
info.flags = saved_flags
source.ignore_space = bool(info.flags & VERBOSE)
return subpattern
def parse_flags_subpattern(source, info):
"""Parses a flags subpattern. It could be inline flags or a subpattern
possibly with local flags. If it's a subpattern, then that's returned;
if it's a inline flags, then None is returned.
"""
flags_on, flags_off = parse_flags(source, info)
if flags_off & GLOBAL_FLAGS:
raise error("bad inline flags: cannot turn off global flag",
source.string, source.pos)
if flags_on & flags_off:
raise error("bad inline flags: flag turned on and off", source.string,
source.pos)
# Handle flags which are global in all regex behaviours.
new_global_flags = (flags_on & ~info.global_flags) & GLOBAL_FLAGS
if new_global_flags:
info.global_flags |= new_global_flags
# A global has been turned on, so reparse the pattern.
raise _UnscopedFlagSet(info.global_flags)
# Ensure that from now on we have only scoped flags.
flags_on &= ~GLOBAL_FLAGS
if source.match(":"):
return parse_subpattern(source, info, flags_on, flags_off)
if source.match(")"):
parse_positional_flags(source, info, flags_on, flags_off)
return None
raise error("unknown extension", source.string, source.pos)
def parse_positional_flags(source, info, flags_on, flags_off):
"Parses positional flags."
info.flags = (info.flags | flags_on) & ~flags_off
source.ignore_space = bool(info.flags & VERBOSE)
def parse_name(source, allow_numeric=False, allow_group_0=False):
"Parses a name."
name = source.get_while(set(")>"), include=False)
if not name:
raise error("missing group name", source.string, source.pos)
if name.isdigit():
min_group = 0 if allow_group_0 else 1
if not allow_numeric or int(name) < min_group:
raise error("bad character in group name", source.string,
source.pos)
else:
if not name.isidentifier():
raise error("bad character in group name", source.string,
source.pos)
return name
def is_octal(string):
"Checks whether a string is octal."
return all(ch in OCT_DIGITS for ch in string)
def is_decimal(string):
"Checks whether a string is decimal."
return all(ch in DIGITS for ch in string)
def is_hexadecimal(string):
"Checks whether a string is hexadecimal."
return all(ch in HEX_DIGITS for ch in string)
def parse_escape(source, info, in_set):
"Parses an escape sequence."
saved_ignore = source.ignore_space
source.ignore_space = False
ch = source.get()
source.ignore_space = saved_ignore
if not ch:
# A backslash at the end of the pattern.
raise error("bad escape (end of pattern)", source.string, source.pos)
if ch in HEX_ESCAPES:
# A hexadecimal escape sequence.
return parse_hex_escape(source, info, ch, HEX_ESCAPES[ch], in_set, ch)
elif ch == "g" and not in_set:
# A group reference.
saved_pos = source.pos
try:
return parse_group_ref(source, info)
except error:
# Invalid as a group reference, so assume it's a literal.
source.pos = saved_pos
return make_character(info, ord(ch), in_set)
elif ch == "G" and not in_set:
# A search anchor.
return SearchAnchor()
elif ch == "L" and not in_set:
# A string set.
return parse_string_set(source, info)
elif ch == "N":
# A named codepoint.
return parse_named_char(source, info, in_set)
elif ch in "pP":
# A Unicode property, positive or negative.
return parse_property(source, info, ch == "p", in_set)
elif ch == "R" and not in_set:
# A line ending.
charset = [0x0A, 0x0B, 0x0C, 0x0D]
if info.guess_encoding == UNICODE:
charset.extend([0x85, 0x2028, 0x2029])
return Atomic(Branch([String([0x0D, 0x0A]), SetUnion(info, [Character(c)
for c in charset])]))
elif ch == "X" and not in_set:
# A grapheme cluster.
return Grapheme()
elif ch in ALPHA:
# An alphabetic escape sequence.
# Positional escapes aren't allowed inside a character set.
if not in_set:
if info.flags & WORD:
value = WORD_POSITION_ESCAPES.get(ch)
else:
value = POSITION_ESCAPES.get(ch)
if value:
return value
value = CHARSET_ESCAPES.get(ch)
if value:
return value
value = CHARACTER_ESCAPES.get(ch)
if value:
return Character(ord(value))
raise error("bad escape \\%s" % ch, source.string, source.pos)
elif ch in DIGITS:
# A numeric escape sequence.
return parse_numeric_escape(source, info, ch, in_set)
else:
# A literal.
return make_character(info, ord(ch), in_set)
def parse_numeric_escape(source, info, ch, in_set):
"Parses a numeric escape sequence."
if in_set or ch == "0":
# Octal escape sequence, max 3 digits.
return parse_octal_escape(source, info, [ch], in_set)
# At least 1 digit, so either octal escape or group.
digits = ch
saved_pos = source.pos
ch = source.get()
if ch in DIGITS:
# At least 2 digits, so either octal escape or group.
digits += ch
saved_pos = source.pos
ch = source.get()
if is_octal(digits) and ch in OCT_DIGITS:
# 3 octal digits, so octal escape sequence.
encoding = info.flags & _ALL_ENCODINGS
if encoding == ASCII or encoding == LOCALE:
octal_mask = 0xFF
else:
octal_mask = 0x1FF
value = int(digits + ch, 8) & octal_mask
return make_character(info, value)
# Group reference.
source.pos = saved_pos
if info.is_open_group(digits):
raise error("cannot refer to an open group", source.string, source.pos)
return make_ref_group(info, digits, source.pos)
def parse_octal_escape(source, info, digits, in_set):
"Parses an octal escape sequence."
saved_pos = source.pos
ch = source.get()
while len(digits) < 3 and ch in OCT_DIGITS:
digits.append(ch)
saved_pos = source.pos
ch = source.get()
source.pos = saved_pos
try:
value = int("".join(digits), 8)
return make_character(info, value, in_set)
except ValueError:
if digits[0] in OCT_DIGITS:
raise error("incomplete escape \\%s" % ''.join(digits),
source.string, source.pos)
else:
raise error("bad escape \\%s" % digits[0], source.string,
source.pos)
def parse_hex_escape(source, info, esc, expected_len, in_set, type):
"Parses a hex escape sequence."
saved_pos = source.pos
digits = []
for i in range(expected_len):
ch = source.get()
if ch not in HEX_DIGITS:
raise error("incomplete escape \\%s%s" % (type, ''.join(digits)),
source.string, saved_pos)
digits.append(ch)
try:
value = int("".join(digits), 16)
except ValueError:
pass
else:
if value < 0x110000:
return make_character(info, value, in_set)
# Bad hex escape.
raise error("bad hex escape \\%s%s" % (esc, ''.join(digits)),
source.string, saved_pos)
def parse_group_ref(source, info):
"Parses a group reference."
source.expect("<")
saved_pos = source.pos
name = parse_name(source, True)
source.expect(">")
if info.is_open_group(name):
raise error("cannot refer to an open group", source.string, source.pos)
return make_ref_group(info, name, saved_pos)
def parse_string_set(source, info):
"Parses a string set reference."
source.expect("<")
name = parse_name(source, True)
source.expect(">")
if name is None or name not in info.kwargs:
raise error("undefined named list", source.string, source.pos)
return make_string_set(info, name)
def parse_named_char(source, info, in_set):
"Parses a named character."
saved_pos = source.pos
if source.match("{"):
name = source.get_while(NAMED_CHAR_PART, keep_spaces=True)
if source.match("}"):
try:
value = unicodedata.lookup(name)
return make_character(info, ord(value), in_set)
except KeyError:
raise error("undefined character name", source.string,
source.pos)
source.pos = saved_pos
return make_character(info, ord("N"), in_set)
def parse_property(source, info, positive, in_set):
"Parses a Unicode property."
saved_pos = source.pos
ch = source.get()
if ch == "{":
negate = source.match("^")
prop_name, name = parse_property_name(source)
if source.match("}"):
# It's correctly delimited.
prop = lookup_property(prop_name, name, positive != negate, source)
return make_property(info, prop, in_set)
elif ch and ch in "CLMNPSZ":
# An abbreviated property, eg \pL.
prop = lookup_property(None, ch, positive, source)
return make_property(info, prop, in_set)
# Not a property, so treat as a literal "p" or "P".
source.pos = saved_pos
ch = "p" if positive else "P"
return make_character(info, ord(ch), in_set)
def parse_property_name(source):
"Parses a property name, which may be qualified."
name = source.get_while(PROPERTY_NAME_PART)
saved_pos = source.pos
ch = source.get()
if ch and ch in ":=":
prop_name = name
name = source.get_while(ALNUM | set(" &_-./")).strip()
if name:
# Name after the ":" or "=", so it's a qualified name.
saved_pos = source.pos
else:
# No name after the ":" or "=", so assume it's an unqualified name.
prop_name, name = None, prop_name
else:
prop_name = None
source.pos = saved_pos
return prop_name, name
def parse_set(source, info):
"Parses a character set."
version = (info.flags & _ALL_VERSIONS) or DEFAULT_VERSION
saved_ignore = source.ignore_space
source.ignore_space = False
# Negative set?
negate = source.match("^")
try:
if version == VERSION0:
item = parse_set_imp_union(source, info)
else:
item = parse_set_union(source, info)
if not source.match("]"):
raise error("missing ]", source.string, source.pos)
finally:
source.ignore_space = saved_ignore
if negate:
item = item.with_flags(positive=not item.positive)
item = item.with_flags(case_flags=make_case_flags(info))
return item
def parse_set_union(source, info):
"Parses a set union ([x||y])."
items = [parse_set_symm_diff(source, info)]
while source.match("||"):
items.append(parse_set_symm_diff(source, info))
if len(items) == 1:
return items[0]
return SetUnion(info, items)
def parse_set_symm_diff(source, info):
"Parses a set symmetric difference ([x~~y])."
items = [parse_set_inter(source, info)]
while source.match("~~"):
items.append(parse_set_inter(source, info))
if len(items) == 1:
return items[0]
return SetSymDiff(info, items)
def parse_set_inter(source, info):
"Parses a set intersection ([x&&y])."
items = [parse_set_diff(source, info)]
while source.match("&&"):
items.append(parse_set_diff(source, info))
if len(items) == 1:
return items[0]
return SetInter(info, items)
def parse_set_diff(source, info):
"Parses a set difference ([x--y])."
items = [parse_set_imp_union(source, info)]
while source.match("--"):
items.append(parse_set_imp_union(source, info))
if len(items) == 1:
return items[0]
return SetDiff(info, items)
def parse_set_imp_union(source, info):
"Parses a set implicit union ([xy])."
version = (info.flags & _ALL_VERSIONS) or DEFAULT_VERSION
items = [parse_set_member(source, info)]
while True:
saved_pos = source.pos
if source.match("]"):
# End of the set.
source.pos = saved_pos
break
if version == VERSION1 and any(source.match(op) for op in SET_OPS):
# The new behaviour has set operators.
source.pos = saved_pos
break
items.append(parse_set_member(source, info))
if len(items) == 1:
return items[0]
return SetUnion(info, items)
def parse_set_member(source, info):
"Parses a member in a character set."
# Parse a set item.
start = parse_set_item(source, info)
saved_pos1 = source.pos
if (not isinstance(start, Character) or not start.positive or not
source.match("-")):
# It's not the start of a range.
return start
version = (info.flags & _ALL_VERSIONS) or DEFAULT_VERSION
# It looks like the start of a range of characters.
saved_pos2 = source.pos
if version == VERSION1 and source.match("-"):
# It's actually the set difference operator '--', so return the
# character.
source.pos = saved_pos1
return start
if source.match("]"):
# We've reached the end of the set, so return both the character and
# hyphen.
source.pos = saved_pos2
return SetUnion(info, [start, Character(ord("-"))])
# Parse a set item.
end = parse_set_item(source, info)
if not isinstance(end, Character) or not end.positive:
# It's not a range, so return the character, hyphen and property.
return SetUnion(info, [start, Character(ord("-")), end])
# It _is_ a range.
if start.value > end.value:
raise error("bad character range", source.string, source.pos)
if start.value == end.value:
return start
return Range(start.value, end.value)
def parse_set_item(source, info):
"Parses an item in a character set."
version = (info.flags & _ALL_VERSIONS) or DEFAULT_VERSION
if source.match("\\"):
# An escape sequence in a set.
return parse_escape(source, info, True)
saved_pos = source.pos
if source.match("[:"):
# Looks like a POSIX character class.
try:
return parse_posix_class(source, info)
except ParseError:
# Not a POSIX character class.
source.pos = saved_pos
if version == VERSION1 and source.match("["):
# It's the start of a nested set.
# Negative set?
negate = source.match("^")
item = parse_set_union(source, info)
if not source.match("]"):
raise error("missing ]", source.string, source.pos)
if negate:
item = item.with_flags(positive=not item.positive)
return item
ch = source.get()
if not ch:
raise error("unterminated character set", source.string, source.pos)
return Character(ord(ch))
def parse_posix_class(source, info):
"Parses a POSIX character class."
negate = source.match("^")
prop_name, name = parse_property_name(source)
if not source.match(":]"):
raise ParseError()
return lookup_property(prop_name, name, not negate, source, posix=True)
def float_to_rational(flt):
"Converts a float to a rational pair."
int_part = int(flt)
error = flt - int_part
if abs(error) < 0.0001:
return int_part, 1
den, num = float_to_rational(1.0 / error)
return int_part * den + num, den
def numeric_to_rational(numeric):
"Converts a numeric string to a rational string, if possible."
if numeric[ : 1] == "-":
sign, numeric = numeric[0], numeric[1 : ]
else:
sign = ""
parts = numeric.split("/")
if len(parts) == 2:
num, den = float_to_rational(float(parts[0]) / float(parts[1]))
elif len(parts) == 1:
num, den = float_to_rational(float(parts[0]))
else:
raise ValueError()
result = "{}{}/{}".format(sign, num, den)
if result.endswith("/1"):
return result[ : -2]
return result
def standardise_name(name):
"Standardises a property or value name."
try:
return numeric_to_rational("".join(name))
except (ValueError, ZeroDivisionError):
return "".join(ch for ch in name if ch not in "_- ").upper()
_POSIX_CLASSES = set('ALNUM DIGIT PUNCT XDIGIT'.split())
_BINARY_VALUES = set('YES Y NO N TRUE T FALSE F'.split())
def lookup_property(property, value, positive, source=None, posix=False):
"Looks up a property."
# Normalise the names (which may still be lists).
property = standardise_name(property) if property else None
value = standardise_name(value)
if (property, value) == ("GENERALCATEGORY", "ASSIGNED"):
property, value, positive = "GENERALCATEGORY", "UNASSIGNED", not positive
if posix and not property and value.upper() in _POSIX_CLASSES:
value = 'POSIX' + value
if property:
# Both the property and the value are provided.
prop = PROPERTIES.get(property)
if not prop:
if not source:
raise error("unknown property")
raise error("unknown property", source.string, source.pos)
prop_id, value_dict = prop
val_id = value_dict.get(value)
if val_id is None:
if not source:
raise error("unknown property value")
raise error("unknown property value", source.string, source.pos)
return Property((prop_id << 16) | val_id, positive)
# Only the value is provided.
# It might be the name of a GC, script or block value.
for property in ("GC", "SCRIPT", "BLOCK"):
prop_id, value_dict = PROPERTIES.get(property)
val_id = value_dict.get(value)
if val_id is not None:
return Property((prop_id << 16) | val_id, positive)
# It might be the name of a binary property.
prop = PROPERTIES.get(value)
if prop:
prop_id, value_dict = prop
if set(value_dict) == _BINARY_VALUES:
return Property((prop_id << 16) | 1, positive)
return Property(prop_id << 16, not positive)
# It might be the name of a binary property starting with a prefix.
if value.startswith("IS"):
prop = PROPERTIES.get(value[2 : ])
if prop:
prop_id, value_dict = prop
if "YES" in value_dict:
return Property((prop_id << 16) | 1, positive)
# It might be the name of a script or block starting with a prefix.
for prefix, property in (("IS", "SCRIPT"), ("IN", "BLOCK")):
if value.startswith(prefix):
prop_id, value_dict = PROPERTIES.get(property)
val_id = value_dict.get(value[2 : ])
if val_id is not None:
return Property((prop_id << 16) | val_id, positive)
# Unknown property.
if not source:
raise error("unknown property")
raise error("unknown property", source.string, source.pos)
def _compile_replacement(source, pattern, is_unicode):
"Compiles a replacement template escape sequence."
ch = source.get()
if ch in ALPHA:
# An alphabetic escape sequence.
value = CHARACTER_ESCAPES.get(ch)
if value:
return False, [ord(value)]
if ch in HEX_ESCAPES and (ch == "x" or is_unicode):
# A hexadecimal escape sequence.
return False, [parse_repl_hex_escape(source, HEX_ESCAPES[ch], ch)]
if ch == "g":
# A group preference.
return True, [compile_repl_group(source, pattern)]
if ch == "N" and is_unicode:
# A named character.
value = parse_repl_named_char(source)
if value is not None:
return False, [value]
raise error("bad escape \\%s" % ch, source.string, source.pos)
if isinstance(source.sep, bytes):
octal_mask = 0xFF
else:
octal_mask = 0x1FF
if ch == "0":
# An octal escape sequence.
digits = ch
while len(digits) < 3:
saved_pos = source.pos
ch = source.get()
if ch not in OCT_DIGITS:
source.pos = saved_pos
break
digits += ch
return False, [int(digits, 8) & octal_mask]
if ch in DIGITS:
# Either an octal escape sequence (3 digits) or a group reference (max
# 2 digits).
digits = ch
saved_pos = source.pos
ch = source.get()
if ch in DIGITS:
digits += ch
saved_pos = source.pos
ch = source.get()
if ch and is_octal(digits + ch):
# An octal escape sequence.
return False, [int(digits + ch, 8) & octal_mask]
# A group reference.
source.pos = saved_pos
return True, [int(digits)]
if ch == "\\":
# An escaped backslash is a backslash.
return False, [ord("\\")]
if not ch:
# A trailing backslash.
raise error("bad escape (end of pattern)", source.string, source.pos)
# An escaped non-backslash is a backslash followed by the literal.
return False, [ord("\\"), ord(ch)]
def parse_repl_hex_escape(source, expected_len, type):
"Parses a hex escape sequence in a replacement string."
digits = []
for i in range(expected_len):
ch = source.get()
if ch not in HEX_DIGITS:
raise error("incomplete escape \\%s%s" % (type, ''.join(digits)),
source.string, source.pos)
digits.append(ch)
return int("".join(digits), 16)
def parse_repl_named_char(source):
"Parses a named character in a replacement string."
saved_pos = source.pos
if source.match("{"):
name = source.get_while(ALPHA | set(" "))
if source.match("}"):
try:
value = unicodedata.lookup(name)
return ord(value)
except KeyError:
raise error("undefined character name", source.string,
source.pos)
source.pos = saved_pos
return None
def compile_repl_group(source, pattern):
"Compiles a replacement template group reference."
source.expect("<")
name = parse_name(source, True, True)
source.expect(">")
if name.isdigit():
index = int(name)
if not 0 <= index <= pattern.groups:
raise error("invalid group reference", source.string, source.pos)
return index
try:
return pattern.groupindex[name]
except KeyError:
raise IndexError("unknown group")
# The regular expression is parsed into a syntax tree. The different types of
# node are defined below.
INDENT = " "
POSITIVE_OP = 0x1
ZEROWIDTH_OP = 0x2
FUZZY_OP = 0x4
REVERSE_OP = 0x8
REQUIRED_OP = 0x10
POS_TEXT = {False: "NON-MATCH", True: "MATCH"}
CASE_TEXT = {NOCASE: "", IGNORECASE: " SIMPLE_IGNORE_CASE", FULLCASE: "",
FULLIGNORECASE: " FULL_IGNORE_CASE"}
def make_sequence(items):
if len(items) == 1:
return items[0]
return Sequence(items)
# Common base class for all nodes.
class RegexBase:
def __init__(self):
self._key = self.__class__
def with_flags(self, positive=None, case_flags=None, zerowidth=None):
if positive is None:
positive = self.positive
else:
positive = bool(positive)
if case_flags is None:
case_flags = self.case_flags
else:
case_flags = CASE_FLAGS_COMBINATIONS[case_flags & CASE_FLAGS]
if zerowidth is None:
zerowidth = self.zerowidth
else:
zerowidth = bool(zerowidth)
if (positive == self.positive and case_flags == self.case_flags and
zerowidth == self.zerowidth):
return self
return self.rebuild(positive, case_flags, zerowidth)
def fix_groups(self, pattern, reverse, fuzzy):
pass
def optimise(self, info, reverse):
return self
def pack_characters(self, info):
return self
def remove_captures(self):
return self
def is_atomic(self):
return True
def can_be_affix(self):
return True
def contains_group(self):
return False
def get_firstset(self, reverse):
raise _FirstSetError()
def has_simple_start(self):
return False
def compile(self, reverse=False, fuzzy=False):
return self._compile(reverse, fuzzy)
def is_empty(self):
return False
def __hash__(self):
return hash(self._key)
def __eq__(self, other):
return type(self) is type(other) and self._key == other._key
def __ne__(self, other):
return not self.__eq__(other)
def get_required_string(self, reverse):
return self.max_width(), None
# Base class for zero-width nodes.
class ZeroWidthBase(RegexBase):
def __init__(self, positive=True):
RegexBase.__init__(self)
self.positive = bool(positive)
self._key = self.__class__, self.positive
def get_firstset(self, reverse):
return set([None])
def _compile(self, reverse, fuzzy):
flags = 0
if self.positive:
flags |= POSITIVE_OP
if fuzzy:
flags |= FUZZY_OP
if reverse:
flags |= REVERSE_OP
return [(self._opcode, flags)]
def dump(self, indent, reverse):
print("{}{} {}".format(INDENT * indent, self._op_name,
POS_TEXT[self.positive]))
def max_width(self):
return 0
class Any(RegexBase):
_opcode = {False: OP.ANY, True: OP.ANY_REV}
_op_name = "ANY"
def has_simple_start(self):
return True
def _compile(self, reverse, fuzzy):
flags = 0
if fuzzy:
flags |= FUZZY_OP
return [(self._opcode[reverse], flags)]
def dump(self, indent, reverse):
print("{}{}".format(INDENT * indent, self._op_name))
def max_width(self):
return 1
class AnyAll(Any):
_opcode = {False: OP.ANY_ALL, True: OP.ANY_ALL_REV}
_op_name = "ANY_ALL"
class AnyU(Any):
_opcode = {False: OP.ANY_U, True: OP.ANY_U_REV}
_op_name = "ANY_U"
class Atomic(RegexBase):
def __init__(self, subpattern):
RegexBase.__init__(self)
self.subpattern = subpattern
def fix_groups(self, pattern, reverse, fuzzy):
self.subpattern.fix_groups(pattern, reverse, fuzzy)
def optimise(self, info, reverse):
self.subpattern = self.subpattern.optimise(info, reverse)
if self.subpattern.is_empty():
return self.subpattern
return self
def pack_characters(self, info):
self.subpattern = self.subpattern.pack_characters(info)
return self
def remove_captures(self):
self.subpattern = self.subpattern.remove_captures()
return self
def can_be_affix(self):
return self.subpattern.can_be_affix()
def contains_group(self):
return self.subpattern.contains_group()
def get_firstset(self, reverse):
return self.subpattern.get_firstset(reverse)
def has_simple_start(self):
return self.subpattern.has_simple_start()
def _compile(self, reverse, fuzzy):
return ([(OP.ATOMIC, )] + self.subpattern.compile(reverse, fuzzy) +
[(OP.END, )])
def dump(self, indent, reverse):
print("{}ATOMIC".format(INDENT * indent))
self.subpattern.dump(indent + 1, reverse)
def is_empty(self):
return self.subpattern.is_empty()
def __eq__(self, other):
return (type(self) is type(other) and self.subpattern ==
other.subpattern)
def max_width(self):
return self.subpattern.max_width()
def get_required_string(self, reverse):
return self.subpattern.get_required_string(reverse)
class Boundary(ZeroWidthBase):
_opcode = OP.BOUNDARY
_op_name = "BOUNDARY"
class Branch(RegexBase):
def __init__(self, branches):
RegexBase.__init__(self)
self.branches = branches
def fix_groups(self, pattern, reverse, fuzzy):
for b in self.branches:
b.fix_groups(pattern, reverse, fuzzy)
def optimise(self, info, reverse):
if not self.branches:
return Sequence([])
# Flatten branches within branches.
branches = Branch._flatten_branches(info, reverse, self.branches)
# Move any common prefix or suffix out of the branches.
if reverse:
suffix, branches = Branch._split_common_suffix(info, branches)
prefix = []
else:
prefix, branches = Branch._split_common_prefix(info, branches)
suffix = []
# Try to reduce adjacent single-character branches to sets.
branches = Branch._reduce_to_set(info, reverse, branches)
if len(branches) > 1:
sequence = [Branch(branches)]
if not prefix or not suffix:
# We might be able to add a quick precheck before the branches.
firstset = self._add_precheck(info, reverse, branches)
if firstset:
if reverse:
sequence.append(firstset)
else:
sequence.insert(0, firstset)
else:
sequence = branches
return make_sequence(prefix + sequence + suffix)
def _add_precheck(self, info, reverse, branches):
charset = set()
pos = -1 if reverse else 0
for branch in branches:
if type(branch) is Literal and branch.case_flags == NOCASE:
charset.add(branch.characters[pos])
else:
return
if not charset:
return None
return _check_firstset(info, reverse, [Character(c) for c in charset])
def pack_characters(self, info):
self.branches = [b.pack_characters(info) for b in self.branches]
return self
def remove_captures(self):
self.branches = [b.remove_captures() for b in self.branches]
return self
def is_atomic(self):
return all(b.is_atomic() for b in self.branches)
def can_be_affix(self):
return all(b.can_be_affix() for b in self.branches)
def contains_group(self):
return any(b.contains_group() for b in self.branches)
def get_firstset(self, reverse):
fs = set()
for b in self.branches:
fs |= b.get_firstset(reverse)
return fs or set([None])
def _compile(self, reverse, fuzzy):
if not self.branches:
return []
code = [(OP.BRANCH, )]
for b in self.branches:
code.extend(b.compile(reverse, fuzzy))
code.append((OP.NEXT, ))
code[-1] = (OP.END, )
return code
def dump(self, indent, reverse):
print("{}BRANCH".format(INDENT * indent))
self.branches[0].dump(indent + 1, reverse)
for b in self.branches[1 : ]:
print("{}OR".format(INDENT * indent))
b.dump(indent + 1, reverse)
@staticmethod
def _flatten_branches(info, reverse, branches):
# Flatten the branches so that there aren't branches of branches.
new_branches = []
for b in branches:
b = b.optimise(info, reverse)
if isinstance(b, Branch):
new_branches.extend(b.branches)
else:
new_branches.append(b)
return new_branches
@staticmethod
def _split_common_prefix(info, branches):
# Common leading items can be moved out of the branches.
# Get the items in the branches.
alternatives = []
for b in branches:
if isinstance(b, Sequence):
alternatives.append(b.items)
else:
alternatives.append([b])
# What is the maximum possible length of the prefix?
max_count = min(len(a) for a in alternatives)
# What is the longest common prefix?
prefix = alternatives[0]
pos = 0
end_pos = max_count
while pos < end_pos and prefix[pos].can_be_affix() and all(a[pos] ==
prefix[pos] for a in alternatives):
pos += 1
count = pos
if info.flags & UNICODE:
# We need to check that we're not splitting a sequence of
# characters which could form part of full case-folding.
count = pos
while count > 0 and not all(Branch._can_split(a, count) for a in
alternatives):
count -= 1
# No common prefix is possible.
if count == 0:
return [], branches
# Rebuild the branches.
new_branches = []
for a in alternatives:
new_branches.append(make_sequence(a[count : ]))
return prefix[ : count], new_branches
@staticmethod
def _split_common_suffix(info, branches):
# Common trailing items can be moved out of the branches.
# Get the items in the branches.
alternatives = []
for b in branches:
if isinstance(b, Sequence):
alternatives.append(b.items)
else:
alternatives.append([b])
# What is the maximum possible length of the suffix?
max_count = min(len(a) for a in alternatives)
# What is the longest common suffix?
suffix = alternatives[0]
pos = -1
end_pos = -1 - max_count
while pos > end_pos and suffix[pos].can_be_affix() and all(a[pos] ==
suffix[pos] for a in alternatives):
pos -= 1
count = -1 - pos
if info.flags & UNICODE:
# We need to check that we're not splitting a sequence of
# characters which could form part of full case-folding.
while count > 0 and not all(Branch._can_split_rev(a, count) for a
in alternatives):
count -= 1
# No common suffix is possible.
if count == 0:
return [], branches
# Rebuild the branches.
new_branches = []
for a in alternatives:
new_branches.append(make_sequence(a[ : -count]))
return suffix[-count : ], new_branches
@staticmethod
def _can_split(items, count):
# Check the characters either side of the proposed split.
if not Branch._is_full_case(items, count - 1):
return True
if not Branch._is_full_case(items, count):
return True
# Check whether a 1-1 split would be OK.
if Branch._is_folded(items[count - 1 : count + 1]):
return False
# Check whether a 1-2 split would be OK.
if (Branch._is_full_case(items, count + 2) and
Branch._is_folded(items[count - 1 : count + 2])):
return False
# Check whether a 2-1 split would be OK.
if (Branch._is_full_case(items, count - 2) and
Branch._is_folded(items[count - 2 : count + 1])):
return False
return True
@staticmethod
def _can_split_rev(items, count):
end = len(items)
# Check the characters either side of the proposed split.
if not Branch._is_full_case(items, end - count):
return True
if not Branch._is_full_case(items, end - count - 1):
return True
# Check whether a 1-1 split would be OK.
if Branch._is_folded(items[end - count - 1 : end - count + 1]):
return False
# Check whether a 1-2 split would be OK.
if (Branch._is_full_case(items, end - count + 2) and
Branch._is_folded(items[end - count - 1 : end - count + 2])):
return False
# Check whether a 2-1 split would be OK.
if (Branch._is_full_case(items, end - count - 2) and
Branch._is_folded(items[end - count - 2 : end - count + 1])):
return False
return True
@staticmethod
def _merge_common_prefixes(info, reverse, branches):
# Branches with the same case-sensitive character prefix can be grouped
# together if they are separated only by other branches with a
# character prefix.
prefixed = defaultdict(list)
order = {}
new_branches = []
for b in branches:
if Branch._is_simple_character(b):
# Branch starts with a simple character.
prefixed[b.value].append([b])
order.setdefault(b.value, len(order))
elif (isinstance(b, Sequence) and b.items and
Branch._is_simple_character(b.items[0])):
# Branch starts with a simple character.
prefixed[b.items[0].value].append(b.items)
order.setdefault(b.items[0].value, len(order))
else:
Branch._flush_char_prefix(info, reverse, prefixed, order,
new_branches)
new_branches.append(b)
Branch._flush_char_prefix(info, prefixed, order, new_branches)
return new_branches
@staticmethod
def _is_simple_character(c):
return isinstance(c, Character) and c.positive and not c.case_flags
@staticmethod
def _reduce_to_set(info, reverse, branches):
# Can the branches be reduced to a set?
new_branches = []
items = set()
case_flags = NOCASE
for b in branches:
if isinstance(b, (Character, Property, SetBase)):
# Branch starts with a single character.
if b.case_flags != case_flags:
# Different case sensitivity, so flush.
Branch._flush_set_members(info, reverse, items, case_flags,
new_branches)
case_flags = b.case_flags
items.add(b.with_flags(case_flags=NOCASE))
else:
Branch._flush_set_members(info, reverse, items, case_flags,
new_branches)
new_branches.append(b)
Branch._flush_set_members(info, reverse, items, case_flags,
new_branches)
return new_branches
@staticmethod
def _flush_char_prefix(info, reverse, prefixed, order, new_branches):
# Flush the prefixed branches.
if not prefixed:
return
for value, branches in sorted(prefixed.items(), key=lambda pair:
order[pair[0]]):
if len(branches) == 1:
new_branches.append(make_sequence(branches[0]))
else:
subbranches = []
optional = False
for b in branches:
if len(b) > 1:
subbranches.append(make_sequence(b[1 : ]))
elif not optional:
subbranches.append(Sequence())
optional = True
sequence = Sequence([Character(value), Branch(subbranches)])
new_branches.append(sequence.optimise(info, reverse))
prefixed.clear()
order.clear()
@staticmethod
def _flush_set_members(info, reverse, items, case_flags, new_branches):
# Flush the set members.
if not items:
return
if len(items) == 1:
item = list(items)[0]
else:
item = SetUnion(info, list(items)).optimise(info, reverse)
new_branches.append(item.with_flags(case_flags=case_flags))
items.clear()
@staticmethod
def _is_full_case(items, i):
if not 0 <= i < len(items):
return False
item = items[i]
return (isinstance(item, Character) and item.positive and
(item.case_flags & FULLIGNORECASE) == FULLIGNORECASE)
@staticmethod
def _is_folded(items):
if len(items) < 2:
return False
for i in items:
if (not isinstance(i, Character) or not i.positive or not
i.case_flags):
return False
folded = "".join(chr(i.value) for i in items)
folded = _regex.fold_case(FULL_CASE_FOLDING, folded)
# Get the characters which expand to multiple codepoints on folding.
expanding_chars = _regex.get_expand_on_folding()
for c in expanding_chars:
if folded == _regex.fold_case(FULL_CASE_FOLDING, c):
return True
return False
def is_empty(self):
return all(b.is_empty() for b in self.branches)
def __eq__(self, other):
return type(self) is type(other) and self.branches == other.branches
def max_width(self):
return max(b.max_width() for b in self.branches)
class CallGroup(RegexBase):
def __init__(self, info, group, position):
RegexBase.__init__(self)
self.info = info
self.group = group
self.position = position
self._key = self.__class__, self.group
def fix_groups(self, pattern, reverse, fuzzy):
try:
self.group = int(self.group)
except ValueError:
try:
self.group = self.info.group_index[self.group]
except KeyError:
raise error("invalid group reference", pattern, self.position)
if not 0 <= self.group <= self.info.group_count:
raise error("unknown group", pattern, self.position)
if self.group > 0 and self.info.open_group_count[self.group] > 1:
raise error("ambiguous group reference", pattern, self.position)
self.info.group_calls.append((self, reverse, fuzzy))
self._key = self.__class__, self.group
def remove_captures(self):
raise error("group reference not allowed", pattern, self.position)
def _compile(self, reverse, fuzzy):
return [(OP.GROUP_CALL, self.call_ref)]
def dump(self, indent, reverse):
print("{}GROUP_CALL {}".format(INDENT * indent, self.group))
def __eq__(self, other):
return type(self) is type(other) and self.group == other.group
def max_width(self):
return UNLIMITED
def __del__(self):
self.info = None
class CallRef(RegexBase):
def __init__(self, ref, parsed):
self.ref = ref
self.parsed = parsed
def _compile(self, reverse, fuzzy):
return ([(OP.CALL_REF, self.ref)] + self.parsed._compile(reverse,
fuzzy) + [(OP.END, )])
class Character(RegexBase):
_opcode = {(NOCASE, False): OP.CHARACTER, (IGNORECASE, False):
OP.CHARACTER_IGN, (FULLCASE, False): OP.CHARACTER, (FULLIGNORECASE,
False): OP.CHARACTER_IGN, (NOCASE, True): OP.CHARACTER_REV, (IGNORECASE,
True): OP.CHARACTER_IGN_REV, (FULLCASE, True): OP.CHARACTER_REV,
(FULLIGNORECASE, True): OP.CHARACTER_IGN_REV}
def __init__(self, value, positive=True, case_flags=NOCASE,
zerowidth=False):
RegexBase.__init__(self)
self.value = value
self.positive = bool(positive)
self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]
self.zerowidth = bool(zerowidth)
if (self.positive and (self.case_flags & FULLIGNORECASE) ==
FULLIGNORECASE):
self.folded = _regex.fold_case(FULL_CASE_FOLDING, chr(self.value))
else:
self.folded = chr(self.value)
self._key = (self.__class__, self.value, self.positive,
self.case_flags, self.zerowidth)
def rebuild(self, positive, case_flags, zerowidth):
return Character(self.value, positive, case_flags, zerowidth)
def optimise(self, info, reverse, in_set=False):
return self
def get_firstset(self, reverse):
return set([self])
def has_simple_start(self):
return True
def _compile(self, reverse, fuzzy):
flags = 0
if self.positive:
flags |= POSITIVE_OP
if self.zerowidth:
flags |= ZEROWIDTH_OP
if fuzzy:
flags |= FUZZY_OP
code = PrecompiledCode([self._opcode[self.case_flags, reverse], flags,
self.value])
if len(self.folded) > 1:
# The character expands on full case-folding.
code = Branch([code, String([ord(c) for c in self.folded],
case_flags=self.case_flags)])
return code.compile(reverse, fuzzy)
def dump(self, indent, reverse):
display = ascii(chr(self.value)).lstrip("bu")
print("{}CHARACTER {} {}{}".format(INDENT * indent,
POS_TEXT[self.positive], display, CASE_TEXT[self.case_flags]))
def matches(self, ch):
return (ch == self.value) == self.positive
def max_width(self):
return len(self.folded)
def get_required_string(self, reverse):
if not self.positive:
return 1, None
self.folded_characters = tuple(ord(c) for c in self.folded)
return 0, self
class Conditional(RegexBase):
def __init__(self, info, group, yes_item, no_item, position):
RegexBase.__init__(self)
self.info = info
self.group = group
self.yes_item = yes_item
self.no_item = no_item
self.position = position
def fix_groups(self, pattern, reverse, fuzzy):
try:
self.group = int(self.group)
except ValueError:
try:
self.group = self.info.group_index[self.group]
except KeyError:
if self.group == 'DEFINE':
# 'DEFINE' is a special name unless there's a group with
# that name.
self.group = 0
else:
raise error("unknown group", pattern, self.position)
if not 0 <= self.group <= self.info.group_count:
raise error("invalid group reference", pattern, self.position)
self.yes_item.fix_groups(pattern, reverse, fuzzy)
self.no_item.fix_groups(pattern, reverse, fuzzy)
def optimise(self, info, reverse):
yes_item = self.yes_item.optimise(info, reverse)
no_item = self.no_item.optimise(info, reverse)
return Conditional(info, self.group, yes_item, no_item, self.position)
def pack_characters(self, info):
self.yes_item = self.yes_item.pack_characters(info)
self.no_item = self.no_item.pack_characters(info)
return self
def remove_captures(self):
self.yes_item = self.yes_item.remove_captures()
self.no_item = self.no_item.remove_captures()
def is_atomic(self):
return self.yes_item.is_atomic() and self.no_item.is_atomic()
def can_be_affix(self):
return self.yes_item.can_be_affix() and self.no_item.can_be_affix()
def contains_group(self):
return self.yes_item.contains_group() or self.no_item.contains_group()
def get_firstset(self, reverse):
return (self.yes_item.get_firstset(reverse) |
self.no_item.get_firstset(reverse))
def _compile(self, reverse, fuzzy):
code = [(OP.GROUP_EXISTS, self.group)]
code.extend(self.yes_item.compile(reverse, fuzzy))
add_code = self.no_item.compile(reverse, fuzzy)
if add_code:
code.append((OP.NEXT, ))
code.extend(add_code)
code.append((OP.END, ))
return code
def dump(self, indent, reverse):
print("{}GROUP_EXISTS {}".format(INDENT * indent, self.group))
self.yes_item.dump(indent + 1, reverse)
if not self.no_item.is_empty():
print("{}OR".format(INDENT * indent))
self.no_item.dump(indent + 1, reverse)
def is_empty(self):
return self.yes_item.is_empty() and self.no_item.is_empty()
def __eq__(self, other):
return type(self) is type(other) and (self.group, self.yes_item,
self.no_item) == (other.group, other.yes_item, other.no_item)
def max_width(self):
return max(self.yes_item.max_width(), self.no_item.max_width())
def __del__(self):
self.info = None
class DefaultBoundary(ZeroWidthBase):
_opcode = OP.DEFAULT_BOUNDARY
_op_name = "DEFAULT_BOUNDARY"
class DefaultEndOfWord(ZeroWidthBase):
_opcode = OP.DEFAULT_END_OF_WORD
_op_name = "DEFAULT_END_OF_WORD"
class DefaultStartOfWord(ZeroWidthBase):
_opcode = OP.DEFAULT_START_OF_WORD
_op_name = "DEFAULT_START_OF_WORD"
class EndOfLine(ZeroWidthBase):
_opcode = OP.END_OF_LINE
_op_name = "END_OF_LINE"
class EndOfLineU(EndOfLine):
_opcode = OP.END_OF_LINE_U
_op_name = "END_OF_LINE_U"
class EndOfString(ZeroWidthBase):
_opcode = OP.END_OF_STRING
_op_name = "END_OF_STRING"
class EndOfStringLine(ZeroWidthBase):
_opcode = OP.END_OF_STRING_LINE
_op_name = "END_OF_STRING_LINE"
class EndOfStringLineU(EndOfStringLine):
_opcode = OP.END_OF_STRING_LINE_U
_op_name = "END_OF_STRING_LINE_U"
class EndOfWord(ZeroWidthBase):
_opcode = OP.END_OF_WORD
_op_name = "END_OF_WORD"
class Failure(ZeroWidthBase):
_op_name = "FAILURE"
def _compile(self, reverse, fuzzy):
return [(OP.FAILURE, )]
class Fuzzy(RegexBase):
def __init__(self, subpattern, constraints=None):
RegexBase.__init__(self)
if constraints is None:
constraints = {}
self.subpattern = subpattern
self.constraints = constraints
# If an error type is mentioned in the cost equation, then its maximum
# defaults to unlimited.
if "cost" in constraints:
for e in "dis":
if e in constraints["cost"]:
constraints.setdefault(e, (0, None))
# If any error type is mentioned, then all the error maxima default to
# 0, otherwise they default to unlimited.
if set(constraints) & set("dis"):
for e in "dis":
constraints.setdefault(e, (0, 0))
else:
for e in "dis":
constraints.setdefault(e, (0, None))
# The maximum of the generic error type defaults to unlimited.
constraints.setdefault("e", (0, None))
# The cost equation defaults to equal costs. Also, the cost of any
# error type not mentioned in the cost equation defaults to 0.
if "cost" in constraints:
for e in "dis":
constraints["cost"].setdefault(e, 0)
else:
constraints["cost"] = {"d": 1, "i": 1, "s": 1, "max":
constraints["e"][1]}
def fix_groups(self, pattern, reverse, fuzzy):
self.subpattern.fix_groups(pattern, reverse, True)
def pack_characters(self, info):
self.subpattern = self.subpattern.pack_characters(info)
return self
def remove_captures(self):
self.subpattern = self.subpattern.remove_captures()
return self
def is_atomic(self):
return self.subpattern.is_atomic()
def contains_group(self):
return self.subpattern.contains_group()
def _compile(self, reverse, fuzzy):
# The individual limits.
arguments = []
for e in "dise":
v = self.constraints[e]
arguments.append(v[0])
arguments.append(UNLIMITED if v[1] is None else v[1])
# The coeffs of the cost equation.
for e in "dis":
arguments.append(self.constraints["cost"][e])
# The maximum of the cost equation.
v = self.constraints["cost"]["max"]
arguments.append(UNLIMITED if v is None else v)
flags = 0
if reverse:
flags |= REVERSE_OP
test = self.constraints.get("test")
if test:
return ([(OP.FUZZY_EXT, flags) + tuple(arguments)] +
test.compile(reverse, True) + [(OP.NEXT,)] +
self.subpattern.compile(reverse, True) + [(OP.END,)])
return ([(OP.FUZZY, flags) + tuple(arguments)] +
self.subpattern.compile(reverse, True) + [(OP.END,)])
def dump(self, indent, reverse):
constraints = self._constraints_to_string()
if constraints:
constraints = " " + constraints
print("{}FUZZY{}".format(INDENT * indent, constraints))
self.subpattern.dump(indent + 1, reverse)
def is_empty(self):
return self.subpattern.is_empty()
def __eq__(self, other):
return (type(self) is type(other) and self.subpattern ==
other.subpattern and self.constraints == other.constraints)
def max_width(self):
return UNLIMITED
def _constraints_to_string(self):
constraints = []
for name in "ids":
min, max = self.constraints[name]
if max == 0:
continue
con = ""
if min > 0:
con = "{}<=".format(min)
con += name
if max is not None:
con += "<={}".format(max)
constraints.append(con)
cost = []
for name in "ids":
coeff = self.constraints["cost"][name]
if coeff > 0:
cost.append("{}{}".format(coeff, name))
limit = self.constraints["cost"]["max"]
if limit is not None and limit > 0:
cost = "{}<={}".format("+".join(cost), limit)
constraints.append(cost)
return ",".join(constraints)
class Grapheme(RegexBase):
def _compile(self, reverse, fuzzy):
# Match at least 1 character until a grapheme boundary is reached. Note
# that this is the same whether matching forwards or backwards.
grapheme_matcher = Atomic(Sequence([LazyRepeat(AnyAll(), 1, None),
GraphemeBoundary()]))
return grapheme_matcher.compile(reverse, fuzzy)
def dump(self, indent, reverse):
print("{}GRAPHEME".format(INDENT * indent))
def max_width(self):
return UNLIMITED
class GraphemeBoundary:
def compile(self, reverse, fuzzy):
return [(OP.GRAPHEME_BOUNDARY, 1)]
class GreedyRepeat(RegexBase):
_opcode = OP.GREEDY_REPEAT
_op_name = "GREEDY_REPEAT"
def __init__(self, subpattern, min_count, max_count):
RegexBase.__init__(self)
self.subpattern = subpattern
self.min_count = min_count
self.max_count = max_count
def fix_groups(self, pattern, reverse, fuzzy):
self.subpattern.fix_groups(pattern, reverse, fuzzy)
def optimise(self, info, reverse):
subpattern = self.subpattern.optimise(info, reverse)
return type(self)(subpattern, self.min_count, self.max_count)
def pack_characters(self, info):
self.subpattern = self.subpattern.pack_characters(info)
return self
def remove_captures(self):
self.subpattern = self.subpattern.remove_captures()
return self
def is_atomic(self):
return self.min_count == self.max_count and self.subpattern.is_atomic()
def can_be_affix(self):
return False
def contains_group(self):
return self.subpattern.contains_group()
def get_firstset(self, reverse):
fs = self.subpattern.get_firstset(reverse)
if self.min_count == 0:
fs.add(None)
return fs
def _compile(self, reverse, fuzzy):
repeat = [self._opcode, self.min_count]
if self.max_count is None:
repeat.append(UNLIMITED)
else:
repeat.append(self.max_count)
subpattern = self.subpattern.compile(reverse, fuzzy)
if not subpattern:
return []
return ([tuple(repeat)] + subpattern + [(OP.END, )])
def dump(self, indent, reverse):
if self.max_count is None:
limit = "INF"
else:
limit = self.max_count
print("{}{} {} {}".format(INDENT * indent, self._op_name,
self.min_count, limit))
self.subpattern.dump(indent + 1, reverse)
def is_empty(self):
return self.subpattern.is_empty()
def __eq__(self, other):
return type(self) is type(other) and (self.subpattern, self.min_count,
self.max_count) == (other.subpattern, other.min_count,
other.max_count)
def max_width(self):
if self.max_count is None:
return UNLIMITED
return self.subpattern.max_width() * self.max_count
def get_required_string(self, reverse):
max_count = UNLIMITED if self.max_count is None else self.max_count
if self.min_count == 0:
w = self.subpattern.max_width() * max_count
return min(w, UNLIMITED), None
ofs, req = self.subpattern.get_required_string(reverse)
if req:
return ofs, req
w = self.subpattern.max_width() * max_count
return min(w, UNLIMITED), None
class PossessiveRepeat(GreedyRepeat):
def is_atomic(self):
return True
def _compile(self, reverse, fuzzy):
subpattern = self.subpattern.compile(reverse, fuzzy)
if not subpattern:
return []
repeat = [self._opcode, self.min_count]
if self.max_count is None:
repeat.append(UNLIMITED)
else:
repeat.append(self.max_count)
return ([(OP.ATOMIC, ), tuple(repeat)] + subpattern + [(OP.END, ),
(OP.END, )])
def dump(self, indent, reverse):
print("{}ATOMIC".format(INDENT * indent))
if self.max_count is None:
limit = "INF"
else:
limit = self.max_count
print("{}{} {} {}".format(INDENT * (indent + 1), self._op_name,
self.min_count, limit))
self.subpattern.dump(indent + 2, reverse)
class Group(RegexBase):
def __init__(self, info, group, subpattern):
RegexBase.__init__(self)
self.info = info
self.group = group
self.subpattern = subpattern
self.call_ref = None
def fix_groups(self, pattern, reverse, fuzzy):
self.info.defined_groups[self.group] = (self, reverse, fuzzy)
self.subpattern.fix_groups(pattern, reverse, fuzzy)
def optimise(self, info, reverse):
subpattern = self.subpattern.optimise(info, reverse)
return Group(self.info, self.group, subpattern)
def pack_characters(self, info):
self.subpattern = self.subpattern.pack_characters(info)
return self
def remove_captures(self):
return self.subpattern.remove_captures()
def is_atomic(self):
return self.subpattern.is_atomic()
def can_be_affix(self):
return False
def contains_group(self):
return True
def get_firstset(self, reverse):
return self.subpattern.get_firstset(reverse)
def has_simple_start(self):
return self.subpattern.has_simple_start()
def _compile(self, reverse, fuzzy):
code = []
public_group = private_group = self.group
if private_group < 0:
public_group = self.info.private_groups[private_group]
private_group = self.info.group_count - private_group
key = self.group, reverse, fuzzy
ref = self.info.call_refs.get(key)
if ref is not None:
code += [(OP.CALL_REF, ref)]
code += [(OP.GROUP, int(not reverse), private_group, public_group)]
code += self.subpattern.compile(reverse, fuzzy)
code += [(OP.END, )]
if ref is not None:
code += [(OP.END, )]
return code
def dump(self, indent, reverse):
group = self.group
if group < 0:
group = private_groups[group]
print("{}GROUP {}".format(INDENT * indent, group))
self.subpattern.dump(indent + 1, reverse)
def __eq__(self, other):
return (type(self) is type(other) and (self.group, self.subpattern) ==
(other.group, other.subpattern))
def max_width(self):
return self.subpattern.max_width()
def get_required_string(self, reverse):
return self.subpattern.get_required_string(reverse)
def __del__(self):
self.info = None
class Keep(ZeroWidthBase):
_opcode = OP.KEEP
_op_name = "KEEP"
class LazyRepeat(GreedyRepeat):
_opcode = OP.LAZY_REPEAT
_op_name = "LAZY_REPEAT"
class LookAround(RegexBase):
_dir_text = {False: "AHEAD", True: "BEHIND"}
def __init__(self, behind, positive, subpattern):
RegexBase.__init__(self)
self.behind = bool(behind)
self.positive = bool(positive)
self.subpattern = subpattern
def fix_groups(self, pattern, reverse, fuzzy):
self.subpattern.fix_groups(pattern, self.behind, fuzzy)
def optimise(self, info, reverse):
subpattern = self.subpattern.optimise(info, self.behind)
if self.positive and subpattern.is_empty():
return subpattern
return LookAround(self.behind, self.positive, subpattern)
def pack_characters(self, info):
self.subpattern = self.subpattern.pack_characters(info)
return self
def remove_captures(self):
return self.subpattern.remove_captures()
def is_atomic(self):
return self.subpattern.is_atomic()
def can_be_affix(self):
return self.subpattern.can_be_affix()
def contains_group(self):
return self.subpattern.contains_group()
def get_firstset(self, reverse):
if self.positive and self.behind == reverse:
return self.subpattern.get_firstset(reverse)
return set([None])
def _compile(self, reverse, fuzzy):
flags = 0
if self.positive:
flags |= POSITIVE_OP
if fuzzy:
flags |= FUZZY_OP
if reverse:
flags |= REVERSE_OP
return ([(OP.LOOKAROUND, flags, int(not self.behind))] +
self.subpattern.compile(self.behind) + [(OP.END, )])
def dump(self, indent, reverse):
print("{}LOOK{} {}".format(INDENT * indent,
self._dir_text[self.behind], POS_TEXT[self.positive]))
self.subpattern.dump(indent + 1, self.behind)
def is_empty(self):
return self.positive and self.subpattern.is_empty()
def __eq__(self, other):
return type(self) is type(other) and (self.behind, self.positive,
self.subpattern) == (other.behind, other.positive, other.subpattern)
def max_width(self):
return 0
class LookAroundConditional(RegexBase):
_dir_text = {False: "AHEAD", True: "BEHIND"}
def __init__(self, behind, positive, subpattern, yes_item, no_item):
RegexBase.__init__(self)
self.behind = bool(behind)
self.positive = bool(positive)
self.subpattern = subpattern
self.yes_item = yes_item
self.no_item = no_item
def fix_groups(self, pattern, reverse, fuzzy):
self.subpattern.fix_groups(pattern, reverse, fuzzy)
self.yes_item.fix_groups(pattern, reverse, fuzzy)
self.no_item.fix_groups(pattern, reverse, fuzzy)
def optimise(self, info, reverse):
subpattern = self.subpattern.optimise(info, self.behind)
yes_item = self.yes_item.optimise(info, self.behind)
no_item = self.no_item.optimise(info, self.behind)
return LookAroundConditional(self.behind, self.positive, subpattern,
yes_item, no_item)
def pack_characters(self, info):
self.subpattern = self.subpattern.pack_characters(info)
self.yes_item = self.yes_item.pack_characters(info)
self.no_item = self.no_item.pack_characters(info)
return self
def remove_captures(self):
self.subpattern = self.subpattern.remove_captures()
self.yes_item = self.yes_item.remove_captures()
self.no_item = self.no_item.remove_captures()
def is_atomic(self):
return (self.subpattern.is_atomic() and self.yes_item.is_atomic() and
self.no_item.is_atomic())
def can_be_affix(self):
return (self.subpattern.can_be_affix() and self.yes_item.can_be_affix()
and self.no_item.can_be_affix())
def contains_group(self):
return (self.subpattern.contains_group() or
self.yes_item.contains_group() or self.no_item.contains_group())
def _compile(self, reverse, fuzzy):
code = [(OP.CONDITIONAL, int(self.positive), int(not self.behind))]
code.extend(self.subpattern.compile(self.behind, fuzzy))
code.append((OP.NEXT, ))
code.extend(self.yes_item.compile(reverse, fuzzy))
add_code = self.no_item.compile(reverse, fuzzy)
if add_code:
code.append((OP.NEXT, ))
code.extend(add_code)
code.append((OP.END, ))
return code
def dump(self, indent, reverse):
print("{}CONDITIONAL {} {}".format(INDENT * indent,
self._dir_text[self.behind], POS_TEXT[self.positive]))
self.subpattern.dump(indent + 1, self.behind)
print("{}EITHER".format(INDENT * indent))
self.yes_item.dump(indent + 1, reverse)
if not self.no_item.is_empty():
print("{}OR".format(INDENT * indent))
self.no_item.dump(indent + 1, reverse)
def is_empty(self):
return (self.subpattern.is_empty() and self.yes_item.is_empty() or
self.no_item.is_empty())
def __eq__(self, other):
return type(self) is type(other) and (self.subpattern, self.yes_item,
self.no_item) == (other.subpattern, other.yes_item, other.no_item)
def max_width(self):
return max(self.yes_item.max_width(), self.no_item.max_width())
def get_required_string(self, reverse):
return self.max_width(), None
class PrecompiledCode(RegexBase):
def __init__(self, code):
self.code = code
def _compile(self, reverse, fuzzy):
return [tuple(self.code)]
class Property(RegexBase):
_opcode = {(NOCASE, False): OP.PROPERTY, (IGNORECASE, False):
OP.PROPERTY_IGN, (FULLCASE, False): OP.PROPERTY, (FULLIGNORECASE, False):
OP.PROPERTY_IGN, (NOCASE, True): OP.PROPERTY_REV, (IGNORECASE, True):
OP.PROPERTY_IGN_REV, (FULLCASE, True): OP.PROPERTY_REV, (FULLIGNORECASE,
True): OP.PROPERTY_IGN_REV}
def __init__(self, value, positive=True, case_flags=NOCASE,
zerowidth=False):
RegexBase.__init__(self)
self.value = value
self.positive = bool(positive)
self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]
self.zerowidth = bool(zerowidth)
self._key = (self.__class__, self.value, self.positive,
self.case_flags, self.zerowidth)
def rebuild(self, positive, case_flags, zerowidth):
return Property(self.value, positive, case_flags, zerowidth)
def optimise(self, info, reverse, in_set=False):
return self
def get_firstset(self, reverse):
return set([self])
def has_simple_start(self):
return True
def _compile(self, reverse, fuzzy):
flags = 0
if self.positive:
flags |= POSITIVE_OP
if self.zerowidth:
flags |= ZEROWIDTH_OP
if fuzzy:
flags |= FUZZY_OP
return [(self._opcode[self.case_flags, reverse], flags, self.value)]
def dump(self, indent, reverse):
prop = PROPERTY_NAMES[self.value >> 16]
name, value = prop[0], prop[1][self.value & 0xFFFF]
print("{}PROPERTY {} {}:{}{}".format(INDENT * indent,
POS_TEXT[self.positive], name, value, CASE_TEXT[self.case_flags]))
def matches(self, ch):
return _regex.has_property_value(self.value, ch) == self.positive
def max_width(self):
return 1
class Prune(ZeroWidthBase):
_op_name = "PRUNE"
def _compile(self, reverse, fuzzy):
return [(OP.PRUNE, )]
class Range(RegexBase):
_opcode = {(NOCASE, False): OP.RANGE, (IGNORECASE, False): OP.RANGE_IGN,
(FULLCASE, False): OP.RANGE, (FULLIGNORECASE, False): OP.RANGE_IGN,
(NOCASE, True): OP.RANGE_REV, (IGNORECASE, True): OP.RANGE_IGN_REV,
(FULLCASE, True): OP.RANGE_REV, (FULLIGNORECASE, True): OP.RANGE_IGN_REV}
_op_name = "RANGE"
def __init__(self, lower, upper, positive=True, case_flags=NOCASE,
zerowidth=False):
RegexBase.__init__(self)
self.lower = lower
self.upper = upper
self.positive = bool(positive)
self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]
self.zerowidth = bool(zerowidth)
self._key = (self.__class__, self.lower, self.upper, self.positive,
self.case_flags, self.zerowidth)
def rebuild(self, positive, case_flags, zerowidth):
return Range(self.lower, self.upper, positive, case_flags, zerowidth)
def optimise(self, info, reverse, in_set=False):
# Is the range case-sensitive?
if not self.positive or not (self.case_flags & IGNORECASE) or in_set:
return self
# Is full case-folding possible?
if (not (info.flags & UNICODE) or (self.case_flags & FULLIGNORECASE) !=
FULLIGNORECASE):
return self
# Get the characters which expand to multiple codepoints on folding.
expanding_chars = _regex.get_expand_on_folding()
# Get the folded characters in the range.
items = []
for ch in expanding_chars:
if self.lower <= ord(ch) <= self.upper:
folded = _regex.fold_case(FULL_CASE_FOLDING, ch)
items.append(String([ord(c) for c in folded],
case_flags=self.case_flags))
if not items:
# We can fall back to simple case-folding.
return self
if len(items) < self.upper - self.lower + 1:
# Not all the characters are covered by the full case-folding.
items.insert(0, self)
return Branch(items)
def _compile(self, reverse, fuzzy):
flags = 0
if self.positive:
flags |= POSITIVE_OP
if self.zerowidth:
flags |= ZEROWIDTH_OP
if fuzzy:
flags |= FUZZY_OP
return [(self._opcode[self.case_flags, reverse], flags, self.lower,
self.upper)]
def dump(self, indent, reverse):
display_lower = ascii(chr(self.lower)).lstrip("bu")
display_upper = ascii(chr(self.upper)).lstrip("bu")
print("{}RANGE {} {} {}{}".format(INDENT * indent,
POS_TEXT[self.positive], display_lower, display_upper,
CASE_TEXT[self.case_flags]))
def matches(self, ch):
return (self.lower <= ch <= self.upper) == self.positive
def max_width(self):
return 1
class RefGroup(RegexBase):
_opcode = {(NOCASE, False): OP.REF_GROUP, (IGNORECASE, False):
OP.REF_GROUP_IGN, (FULLCASE, False): OP.REF_GROUP, (FULLIGNORECASE,
False): OP.REF_GROUP_FLD, (NOCASE, True): OP.REF_GROUP_REV, (IGNORECASE,
True): OP.REF_GROUP_IGN_REV, (FULLCASE, True): OP.REF_GROUP_REV,
(FULLIGNORECASE, True): OP.REF_GROUP_FLD_REV}
def __init__(self, info, group, position, case_flags=NOCASE):
RegexBase.__init__(self)
self.info = info
self.group = group
self.position = position
self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]
self._key = self.__class__, self.group, self.case_flags
def fix_groups(self, pattern, reverse, fuzzy):
try:
self.group = int(self.group)
except ValueError:
try:
self.group = self.info.group_index[self.group]
except KeyError:
raise error("unknown group", pattern, self.position)
if not 1 <= self.group <= self.info.group_count:
raise error("invalid group reference", pattern, self.position)
self._key = self.__class__, self.group, self.case_flags
def remove_captures(self):
raise error("group reference not allowed", pattern, self.position)
def _compile(self, reverse, fuzzy):
flags = 0
if fuzzy:
flags |= FUZZY_OP
return [(self._opcode[self.case_flags, reverse], flags, self.group)]
def dump(self, indent, reverse):
print("{}REF_GROUP {}{}".format(INDENT * indent, self.group,
CASE_TEXT[self.case_flags]))
def max_width(self):
return UNLIMITED
def __del__(self):
self.info = None
class SearchAnchor(ZeroWidthBase):
_opcode = OP.SEARCH_ANCHOR
_op_name = "SEARCH_ANCHOR"
class Sequence(RegexBase):
def __init__(self, items=None):
RegexBase.__init__(self)
if items is None:
items = []
self.items = items
def fix_groups(self, pattern, reverse, fuzzy):
for s in self.items:
s.fix_groups(pattern, reverse, fuzzy)
def optimise(self, info, reverse):
# Flatten the sequences.
items = []
for s in self.items:
s = s.optimise(info, reverse)
if isinstance(s, Sequence):
items.extend(s.items)
else:
items.append(s)
return make_sequence(items)
def pack_characters(self, info):
"Packs sequences of characters into strings."
items = []
characters = []
case_flags = NOCASE
for s in self.items:
if type(s) is Character and s.positive and not s.zerowidth:
if s.case_flags != case_flags:
# Different case sensitivity, so flush, unless neither the
# previous nor the new character are cased.
if s.case_flags or is_cased_i(info, s.value):
Sequence._flush_characters(info, characters,
case_flags, items)
case_flags = s.case_flags
characters.append(s.value)
elif type(s) is String or type(s) is Literal:
if s.case_flags != case_flags:
# Different case sensitivity, so flush, unless the neither
# the previous nor the new string are cased.
if s.case_flags or any(is_cased_i(info, c) for c in
characters):
Sequence._flush_characters(info, characters,
case_flags, items)
case_flags = s.case_flags
characters.extend(s.characters)
else:
Sequence._flush_characters(info, characters, case_flags, items)
items.append(s.pack_characters(info))
Sequence._flush_characters(info, characters, case_flags, items)
return make_sequence(items)
def remove_captures(self):
self.items = [s.remove_captures() for s in self.items]
return self
def is_atomic(self):
return all(s.is_atomic() for s in self.items)
def can_be_affix(self):
return False
def contains_group(self):
return any(s.contains_group() for s in self.items)
def get_firstset(self, reverse):
fs = set()
items = self.items
if reverse:
items.reverse()
for s in items:
fs |= s.get_firstset(reverse)
if None not in fs:
return fs
fs.discard(None)
return fs | set([None])
def has_simple_start(self):
return bool(self.items) and self.items[0].has_simple_start()
def _compile(self, reverse, fuzzy):
seq = self.items
if reverse:
seq = seq[::-1]
code = []
for s in seq:
code.extend(s.compile(reverse, fuzzy))
return code
def dump(self, indent, reverse):
for s in self.items:
s.dump(indent, reverse)
@staticmethod
def _flush_characters(info, characters, case_flags, items):
if not characters:
return
# Disregard case_flags if all of the characters are case-less.
if case_flags & IGNORECASE:
if not any(is_cased_i(info, c) for c in characters):
case_flags = NOCASE
if (case_flags & FULLIGNORECASE) == FULLIGNORECASE:
literals = Sequence._fix_full_casefold(characters)
for item in literals:
chars = item.characters
if len(chars) == 1:
items.append(Character(chars[0], case_flags=item.case_flags))
else:
items.append(String(chars, case_flags=item.case_flags))
else:
if len(characters) == 1:
items.append(Character(characters[0], case_flags=case_flags))
else:
items.append(String(characters, case_flags=case_flags))
characters[:] = []
@staticmethod
def _fix_full_casefold(characters):
# Split a literal needing full case-folding into chunks that need it
# and chunks that can use simple case-folding, which is faster.
expanded = [_regex.fold_case(FULL_CASE_FOLDING, c) for c in
_regex.get_expand_on_folding()]
string = _regex.fold_case(FULL_CASE_FOLDING, ''.join(chr(c)
for c in characters)).lower()
chunks = []
for e in expanded:
found = string.find(e)
while found >= 0:
chunks.append((found, found + len(e)))
found = string.find(e, found + 1)
pos = 0
literals = []
for start, end in Sequence._merge_chunks(chunks):
if pos < start:
literals.append(Literal(characters[pos : start],
case_flags=IGNORECASE))
literals.append(Literal(characters[start : end],
case_flags=FULLIGNORECASE))
pos = end
if pos < len(characters):
literals.append(Literal(characters[pos : ], case_flags=IGNORECASE))
return literals
@staticmethod
def _merge_chunks(chunks):
if len(chunks) < 2:
return chunks
chunks.sort()
start, end = chunks[0]
new_chunks = []
for s, e in chunks[1 : ]:
if s <= end:
end = max(end, e)
else:
new_chunks.append((start, end))
start, end = s, e
new_chunks.append((start, end))
return new_chunks
def is_empty(self):
return all(i.is_empty() for i in self.items)
def __eq__(self, other):
return type(self) is type(other) and self.items == other.items
def max_width(self):
return sum(s.max_width() for s in self.items)
def get_required_string(self, reverse):
seq = self.items
if reverse:
seq = seq[::-1]
offset = 0
for s in seq:
ofs, req = s.get_required_string(reverse)
offset += ofs
if req:
return offset, req
return offset, None
class SetBase(RegexBase):
def __init__(self, info, items, positive=True, case_flags=NOCASE,
zerowidth=False):
RegexBase.__init__(self)
self.info = info
self.items = tuple(items)
self.positive = bool(positive)
self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]
self.zerowidth = bool(zerowidth)
self.char_width = 1
self._key = (self.__class__, self.items, self.positive,
self.case_flags, self.zerowidth)
def rebuild(self, positive, case_flags, zerowidth):
return type(self)(self.info, self.items, positive, case_flags,
zerowidth).optimise(self.info, False)
def get_firstset(self, reverse):
return set([self])
def has_simple_start(self):
return True
def _compile(self, reverse, fuzzy):
flags = 0
if self.positive:
flags |= POSITIVE_OP
if self.zerowidth:
flags |= ZEROWIDTH_OP
if fuzzy:
flags |= FUZZY_OP
code = [(self._opcode[self.case_flags, reverse], flags)]
for m in self.items:
code.extend(m.compile())
code.append((OP.END, ))
return code
def dump(self, indent, reverse):
print("{}{} {}{}".format(INDENT * indent, self._op_name,
POS_TEXT[self.positive], CASE_TEXT[self.case_flags]))
for i in self.items:
i.dump(indent + 1, reverse)
def _handle_case_folding(self, info, in_set):
# Is the set case-sensitive?
if not self.positive or not (self.case_flags & IGNORECASE) or in_set:
return self
# Is full case-folding possible?
if (not (self.info.flags & UNICODE) or (self.case_flags &
FULLIGNORECASE) != FULLIGNORECASE):
return self
# Get the characters which expand to multiple codepoints on folding.
expanding_chars = _regex.get_expand_on_folding()
# Get the folded characters in the set.
items = []
seen = set()
for ch in expanding_chars:
if self.matches(ord(ch)):
folded = _regex.fold_case(FULL_CASE_FOLDING, ch)
if folded not in seen:
items.append(String([ord(c) for c in folded],
case_flags=self.case_flags))
seen.add(folded)
if not items:
# We can fall back to simple case-folding.
return self
return Branch([self] + items)
def max_width(self):
# Is the set case-sensitive?
if not self.positive or not (self.case_flags & IGNORECASE):
return 1
# Is full case-folding possible?
if (not (self.info.flags & UNICODE) or (self.case_flags &
FULLIGNORECASE) != FULLIGNORECASE):
return 1
# Get the characters which expand to multiple codepoints on folding.
expanding_chars = _regex.get_expand_on_folding()
# Get the folded characters in the set.
seen = set()
for ch in expanding_chars:
if self.matches(ord(ch)):
folded = _regex.fold_case(FULL_CASE_FOLDING, ch)
seen.add(folded)
if not seen:
return 1
return max(len(folded) for folded in seen)
def __del__(self):
self.info = None
class SetDiff(SetBase):
_opcode = {(NOCASE, False): OP.SET_DIFF, (IGNORECASE, False):
OP.SET_DIFF_IGN, (FULLCASE, False): OP.SET_DIFF, (FULLIGNORECASE, False):
OP.SET_DIFF_IGN, (NOCASE, True): OP.SET_DIFF_REV, (IGNORECASE, True):
OP.SET_DIFF_IGN_REV, (FULLCASE, True): OP.SET_DIFF_REV, (FULLIGNORECASE,
True): OP.SET_DIFF_IGN_REV}
_op_name = "SET_DIFF"
def optimise(self, info, reverse, in_set=False):
items = self.items
if len(items) > 2:
items = [items[0], SetUnion(info, items[1 : ])]
if len(items) == 1:
return items[0].with_flags(case_flags=self.case_flags,
zerowidth=self.zerowidth).optimise(info, reverse, in_set)
self.items = tuple(m.optimise(info, reverse, in_set=True) for m in
items)
return self._handle_case_folding(info, in_set)
def matches(self, ch):
m = self.items[0].matches(ch) and not self.items[1].matches(ch)
return m == self.positive
class SetInter(SetBase):
_opcode = {(NOCASE, False): OP.SET_INTER, (IGNORECASE, False):
OP.SET_INTER_IGN, (FULLCASE, False): OP.SET_INTER, (FULLIGNORECASE,
False): OP.SET_INTER_IGN, (NOCASE, True): OP.SET_INTER_REV, (IGNORECASE,
True): OP.SET_INTER_IGN_REV, (FULLCASE, True): OP.SET_INTER_REV,
(FULLIGNORECASE, True): OP.SET_INTER_IGN_REV}
_op_name = "SET_INTER"
def optimise(self, info, reverse, in_set=False):
items = []
for m in self.items:
m = m.optimise(info, reverse, in_set=True)
if isinstance(m, SetInter) and m.positive:
# Intersection in intersection.
items.extend(m.items)
else:
items.append(m)
if len(items) == 1:
return items[0].with_flags(case_flags=self.case_flags,
zerowidth=self.zerowidth).optimise(info, reverse, in_set)
self.items = tuple(items)
return self._handle_case_folding(info, in_set)
def matches(self, ch):
m = all(i.matches(ch) for i in self.items)
return m == self.positive
class SetSymDiff(SetBase):
_opcode = {(NOCASE, False): OP.SET_SYM_DIFF, (IGNORECASE, False):
OP.SET_SYM_DIFF_IGN, (FULLCASE, False): OP.SET_SYM_DIFF, (FULLIGNORECASE,
False): OP.SET_SYM_DIFF_IGN, (NOCASE, True): OP.SET_SYM_DIFF_REV,
(IGNORECASE, True): OP.SET_SYM_DIFF_IGN_REV, (FULLCASE, True):
OP.SET_SYM_DIFF_REV, (FULLIGNORECASE, True): OP.SET_SYM_DIFF_IGN_REV}
_op_name = "SET_SYM_DIFF"
def optimise(self, info, reverse, in_set=False):
items = []
for m in self.items:
m = m.optimise(info, reverse, in_set=True)
if isinstance(m, SetSymDiff) and m.positive:
# Symmetric difference in symmetric difference.
items.extend(m.items)
else:
items.append(m)
if len(items) == 1:
return items[0].with_flags(case_flags=self.case_flags,
zerowidth=self.zerowidth).optimise(info, reverse, in_set)
self.items = tuple(items)
return self._handle_case_folding(info, in_set)
def matches(self, ch):
m = False
for i in self.items:
m = m != i.matches(ch)
return m == self.positive
class SetUnion(SetBase):
_opcode = {(NOCASE, False): OP.SET_UNION, (IGNORECASE, False):
OP.SET_UNION_IGN, (FULLCASE, False): OP.SET_UNION, (FULLIGNORECASE,
False): OP.SET_UNION_IGN, (NOCASE, True): OP.SET_UNION_REV, (IGNORECASE,
True): OP.SET_UNION_IGN_REV, (FULLCASE, True): OP.SET_UNION_REV,
(FULLIGNORECASE, True): OP.SET_UNION_IGN_REV}
_op_name = "SET_UNION"
def optimise(self, info, reverse, in_set=False):
items = []
for m in self.items:
m = m.optimise(info, reverse, in_set=True)
if isinstance(m, SetUnion) and m.positive:
# Union in union.
items.extend(m.items)
else:
items.append(m)
if len(items) == 1:
i = items[0]
return i.with_flags(positive=i.positive == self.positive,
case_flags=self.case_flags,
zerowidth=self.zerowidth).optimise(info, reverse, in_set)
self.items = tuple(items)
return self._handle_case_folding(info, in_set)
def _compile(self, reverse, fuzzy):
flags = 0
if self.positive:
flags |= POSITIVE_OP
if self.zerowidth:
flags |= ZEROWIDTH_OP
if fuzzy:
flags |= FUZZY_OP
characters, others = defaultdict(list), []
for m in self.items:
if isinstance(m, Character):
characters[m.positive].append(m.value)
else:
others.append(m)
code = [(self._opcode[self.case_flags, reverse], flags)]
for positive, values in characters.items():
flags = 0
if positive:
flags |= POSITIVE_OP
if len(values) == 1:
code.append((OP.CHARACTER, flags, values[0]))
else:
code.append((OP.STRING, flags, len(values)) + tuple(values))
for m in others:
code.extend(m.compile())
code.append((OP.END, ))
return code
def matches(self, ch):
m = any(i.matches(ch) for i in self.items)
return m == self.positive
class Skip(ZeroWidthBase):
_op_name = "SKIP"
_opcode = OP.SKIP
class StartOfLine(ZeroWidthBase):
_opcode = OP.START_OF_LINE
_op_name = "START_OF_LINE"
class StartOfLineU(StartOfLine):
_opcode = OP.START_OF_LINE_U
_op_name = "START_OF_LINE_U"
class StartOfString(ZeroWidthBase):
_opcode = OP.START_OF_STRING
_op_name = "START_OF_STRING"
class StartOfWord(ZeroWidthBase):
_opcode = OP.START_OF_WORD
_op_name = "START_OF_WORD"
class String(RegexBase):
_opcode = {(NOCASE, False): OP.STRING, (IGNORECASE, False): OP.STRING_IGN,
(FULLCASE, False): OP.STRING, (FULLIGNORECASE, False): OP.STRING_FLD,
(NOCASE, True): OP.STRING_REV, (IGNORECASE, True): OP.STRING_IGN_REV,
(FULLCASE, True): OP.STRING_REV, (FULLIGNORECASE, True):
OP.STRING_FLD_REV}
def __init__(self, characters, case_flags=NOCASE):
self.characters = tuple(characters)
self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]
if (self.case_flags & FULLIGNORECASE) == FULLIGNORECASE:
folded_characters = []
for char in self.characters:
folded = _regex.fold_case(FULL_CASE_FOLDING, chr(char))
folded_characters.extend(ord(c) for c in folded)
else:
folded_characters = self.characters
self.folded_characters = tuple(folded_characters)
self.required = False
self._key = self.__class__, self.characters, self.case_flags
def get_firstset(self, reverse):
if reverse:
pos = -1
else:
pos = 0
return set([Character(self.characters[pos],
case_flags=self.case_flags)])
def has_simple_start(self):
return True
def _compile(self, reverse, fuzzy):
flags = 0
if fuzzy:
flags |= FUZZY_OP
if self.required:
flags |= REQUIRED_OP
return [(self._opcode[self.case_flags, reverse], flags,
len(self.folded_characters)) + self.folded_characters]
def dump(self, indent, reverse):
display = ascii("".join(chr(c) for c in self.characters)).lstrip("bu")
print("{}STRING {}{}".format(INDENT * indent, display,
CASE_TEXT[self.case_flags]))
def max_width(self):
return len(self.folded_characters)
def get_required_string(self, reverse):
return 0, self
class Literal(String):
def dump(self, indent, reverse):
literal = ''.join(chr(c) for c in self.characters)
display = ascii(literal).lstrip("bu")
print("{}LITERAL MATCH {}{}".format(INDENT * indent, display,
CASE_TEXT[self.case_flags]))
class StringSet(Branch):
def __init__(self, info, name, case_flags=NOCASE):
self.info = info
self.name = name
self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]
self._key = self.__class__, self.name, self.case_flags
self.set_key = (name, self.case_flags)
if self.set_key not in info.named_lists_used:
info.named_lists_used[self.set_key] = len(info.named_lists_used)
index = self.info.named_lists_used[self.set_key]
items = self.info.kwargs[self.name]
case_flags = self.case_flags
encoding = self.info.flags & _ALL_ENCODINGS
fold_flags = encoding | case_flags
choices = []
for string in items:
if isinstance(string, str):
string = [ord(c) for c in string]
choices.append([Character(c, case_flags=case_flags) for c in
string])
# Sort from longest to shortest.
choices.sort(key=len, reverse=True)
self.branches = [Sequence(choice) for choice in choices]
def dump(self, indent, reverse):
print("{}STRING_SET {}{}".format(INDENT * indent, self.name,
CASE_TEXT[self.case_flags]))
def __del__(self):
self.info = None
class Source:
"Scanner for the regular expression source string."
def __init__(self, string):
if isinstance(string, str):
self.string = string
self.char_type = chr
else:
self.string = string.decode("latin-1")
self.char_type = lambda c: bytes([c])
self.pos = 0
self.ignore_space = False
self.sep = string[ : 0]
def get(self, override_ignore=False):
string = self.string
pos = self.pos
try:
if self.ignore_space and not override_ignore:
while True:
if string[pos].isspace():
# Skip over the whitespace.
pos += 1
elif string[pos] == "#":
# Skip over the comment to the end of the line.
pos = string.index("\n", pos)
else:
break
ch = string[pos]
self.pos = pos + 1
return ch
except IndexError:
# We've reached the end of the string.
self.pos = pos
return string[ : 0]
except ValueError:
# The comment extended to the end of the string.
self.pos = len(string)
return string[ : 0]
def get_many(self, count=1):
string = self.string
pos = self.pos
try:
if self.ignore_space:
substring = []
while len(substring) < count:
while True:
if string[pos].isspace():
# Skip over the whitespace.
pos += 1
elif string[pos] == "#":
# Skip over the comment to the end of the line.
pos = string.index("\n", pos)
else:
break
substring.append(string[pos])
pos += 1
substring = "".join(substring)
else:
substring = string[pos : pos + count]
pos += len(substring)
self.pos = pos
return substring
except IndexError:
# We've reached the end of the string.
self.pos = len(string)
return "".join(substring)
except ValueError:
# The comment extended to the end of the string.
self.pos = len(string)
return "".join(substring)
def get_while(self, test_set, include=True, keep_spaces=False):
string = self.string
pos = self.pos
if self.ignore_space and not keep_spaces:
try:
substring = []
while True:
if string[pos].isspace():
# Skip over the whitespace.
pos += 1
elif string[pos] == "#":
# Skip over the comment to the end of the line.
pos = string.index("\n", pos)
elif (string[pos] in test_set) == include:
substring.append(string[pos])
pos += 1
else:
break
self.pos = pos
except IndexError:
# We've reached the end of the string.
self.pos = len(string)
except ValueError:
# The comment extended to the end of the string.
self.pos = len(string)
return "".join(substring)
else:
try:
while (string[pos] in test_set) == include:
pos += 1
substring = string[self.pos : pos]
self.pos = pos
return substring
except IndexError:
# We've reached the end of the string.
substring = string[self.pos : pos]
self.pos = pos
return substring
def skip_while(self, test_set, include=True):
string = self.string
pos = self.pos
try:
if self.ignore_space:
while True:
if string[pos].isspace():
# Skip over the whitespace.
pos += 1
elif string[pos] == "#":
# Skip over the comment to the end of the line.
pos = string.index("\n", pos)
elif (string[pos] in test_set) == include:
pos += 1
else:
break
else:
while (string[pos] in test_set) == include:
pos += 1
self.pos = pos
except IndexError:
# We've reached the end of the string.
self.pos = len(string)
except ValueError:
# The comment extended to the end of the string.
self.pos = len(string)
def match(self, substring):
string = self.string
pos = self.pos
if self.ignore_space:
try:
for c in substring:
while True:
if string[pos].isspace():
# Skip over the whitespace.
pos += 1
elif string[pos] == "#":
# Skip over the comment to the end of the line.
pos = string.index("\n", pos)
else:
break
if string[pos] != c:
return False
pos += 1
self.pos = pos
return True
except IndexError:
# We've reached the end of the string.
return False
except ValueError:
# The comment extended to the end of the string.
return False
else:
if not string.startswith(substring, pos):
return False
self.pos = pos + len(substring)
return True
def expect(self, substring):
if not self.match(substring):
raise error("missing {}".format(substring), self.string, self.pos)
def at_end(self):
string = self.string
pos = self.pos
try:
if self.ignore_space:
while True:
if string[pos].isspace():
pos += 1
elif string[pos] == "#":
pos = string.index("\n", pos)
else:
break
return pos >= len(string)
except IndexError:
# We've reached the end of the string.
return True
except ValueError:
# The comment extended to the end of the string.
return True
class Info:
"Info about the regular expression."
def __init__(self, flags=0, char_type=None, kwargs={}):
flags |= DEFAULT_FLAGS[(flags & _ALL_VERSIONS) or DEFAULT_VERSION]
self.flags = flags
self.global_flags = flags
self.inline_locale = False
self.kwargs = kwargs
self.group_count = 0
self.group_index = {}
self.group_name = {}
self.char_type = char_type
self.named_lists_used = {}
self.open_groups = []
self.open_group_count = {}
self.defined_groups = {}
self.group_calls = []
self.private_groups = {}
def open_group(self, name=None):
group = self.group_index.get(name)
if group is None:
while True:
self.group_count += 1
if name is None or self.group_count not in self.group_name:
break
group = self.group_count
if name:
self.group_index[name] = group
self.group_name[group] = name
if group in self.open_groups:
# We have a nested named group. We'll assign it a private group
# number, initially negative until we can assign a proper
# (positive) number.
group_alias = -(len(self.private_groups) + 1)
self.private_groups[group_alias] = group
group = group_alias
self.open_groups.append(group)
self.open_group_count[group] = self.open_group_count.get(group, 0) + 1
return group
def close_group(self):
self.open_groups.pop()
def is_open_group(self, name):
# In version 1, a group reference can refer to an open group. We'll
# just pretend the group isn't open.
version = (self.flags & _ALL_VERSIONS) or DEFAULT_VERSION
if version == VERSION1:
return False
if name.isdigit():
group = int(name)
else:
group = self.group_index.get(name)
return group in self.open_groups
def _check_group_features(info, parsed):
"""Checks whether the reverse and fuzzy features of the group calls match
the groups which they call.
"""
call_refs = {}
additional_groups = []
for call, reverse, fuzzy in info.group_calls:
# Look up the reference of this group call.
key = (call.group, reverse, fuzzy)
ref = call_refs.get(key)
if ref is None:
# This group doesn't have a reference yet, so look up its features.
if call.group == 0:
# Calling the pattern as a whole.
rev = bool(info.flags & REVERSE)
fuz = isinstance(parsed, Fuzzy)
if (rev, fuz) != (reverse, fuzzy):
# The pattern as a whole doesn't have the features we want,
# so we'll need to make a copy of it with the desired
# features.
additional_groups.append((CallRef(len(call_refs), parsed),
reverse, fuzzy))
else:
# Calling a capture group.
def_info = info.defined_groups[call.group]
group = def_info[0]
if def_info[1 : ] != (reverse, fuzzy):
# The group doesn't have the features we want, so we'll
# need to make a copy of it with the desired features.
additional_groups.append((group, reverse, fuzzy))
ref = len(call_refs)
call_refs[key] = ref
call.call_ref = ref
info.call_refs = call_refs
info.additional_groups = additional_groups
def _get_required_string(parsed, flags):
"Gets the required string and related info of a parsed pattern."
req_offset, required = parsed.get_required_string(bool(flags & REVERSE))
if required:
required.required = True
if req_offset >= UNLIMITED:
req_offset = -1
req_flags = required.case_flags
if not (flags & UNICODE):
req_flags &= ~UNICODE
req_chars = required.folded_characters
else:
req_offset = 0
req_chars = ()
req_flags = 0
return req_offset, req_chars, req_flags
class Scanner:
def __init__(self, lexicon, flags=0):
self.lexicon = lexicon
# Combine phrases into a compound pattern.
patterns = []
for phrase, action in lexicon:
# Parse the regular expression.
source = Source(phrase)
info = Info(flags, source.char_type)
source.ignore_space = bool(info.flags & VERBOSE)
parsed = _parse_pattern(source, info)
if not source.at_end():
raise error("unbalanced parenthesis", source.string,
source.pos)
# We want to forbid capture groups within each phrase.
patterns.append(parsed.remove_captures())
# Combine all the subpatterns into one pattern.
info = Info(flags)
patterns = [Group(info, g + 1, p) for g, p in enumerate(patterns)]
parsed = Branch(patterns)
# Optimise the compound pattern.
reverse = bool(info.flags & REVERSE)
parsed = parsed.optimise(info, reverse)
parsed = parsed.pack_characters(info)
# Get the required string.
req_offset, req_chars, req_flags = _get_required_string(parsed,
info.flags)
# Check the features of the groups.
_check_group_features(info, parsed)
# Complain if there are any group calls. They are not supported by the
# Scanner class.
if info.call_refs:
raise error("recursive regex not supported by Scanner",
source.string, source.pos)
reverse = bool(info.flags & REVERSE)
# Compile the compound pattern. The result is a list of tuples.
code = parsed.compile(reverse) + [(OP.SUCCESS, )]
# Flatten the code into a list of ints.
code = _flatten_code(code)
if not parsed.has_simple_start():
# Get the first set, if possible.
try:
fs_code = _compile_firstset(info, parsed.get_firstset(reverse))
fs_code = _flatten_code(fs_code)
code = fs_code + code
except _FirstSetError:
pass
# Check the global flags for conflicts.
version = (info.flags & _ALL_VERSIONS) or DEFAULT_VERSION
if version not in (0, VERSION0, VERSION1):
raise ValueError("VERSION0 and VERSION1 flags are mutually incompatible")
# Create the PatternObject.
#
# Local flags like IGNORECASE affect the code generation, but aren't
# needed by the PatternObject itself. Conversely, global flags like
# LOCALE _don't_ affect the code generation but _are_ needed by the
# PatternObject.
self.scanner = _regex.compile(None, (flags & GLOBAL_FLAGS) | version,
code, {}, {}, {}, [], req_offset, req_chars, req_flags,
len(patterns))
def scan(self, string):
result = []
append = result.append
match = self.scanner.scanner(string).match
i = 0
while True:
m = match()
if not m:
break
j = m.end()
if i == j:
break
action = self.lexicon[m.lastindex - 1][1]
if hasattr(action, '__call__'):
self.match = m
action = action(self, m.group())
if action is not None:
append(action)
i = j
return result, string[i : ]
# Get the known properties dict.
PROPERTIES = _regex.get_properties()
# Build the inverse of the properties dict.
PROPERTY_NAMES = {}
for prop_name, (prop_id, values) in PROPERTIES.items():
name, prop_values = PROPERTY_NAMES.get(prop_id, ("", {}))
name = max(name, prop_name, key=len)
PROPERTY_NAMES[prop_id] = name, prop_values
for val_name, val_id in values.items():
prop_values[val_id] = max(prop_values.get(val_id, ""), val_name,
key=len)
# Character escape sequences.
CHARACTER_ESCAPES = {
"a": "\a",
"b": "\b",
"f": "\f",
"n": "\n",
"r": "\r",
"t": "\t",
"v": "\v",
}
# Predefined character set escape sequences.
CHARSET_ESCAPES = {
"d": lookup_property(None, "Digit", True),
"D": lookup_property(None, "Digit", False),
"h": lookup_property(None, "Blank", True),
"s": lookup_property(None, "Space", True),
"S": lookup_property(None, "Space", False),
"w": lookup_property(None, "Word", True),
"W": lookup_property(None, "Word", False),
}
# Positional escape sequences.
POSITION_ESCAPES = {
"A": StartOfString(),
"b": Boundary(),
"B": Boundary(False),
"K": Keep(),
"m": StartOfWord(),
"M": EndOfWord(),
"Z": EndOfString(),
}
# Positional escape sequences when WORD flag set.
WORD_POSITION_ESCAPES = dict(POSITION_ESCAPES)
WORD_POSITION_ESCAPES.update({
"b": DefaultBoundary(),
"B": DefaultBoundary(False),
"m": DefaultStartOfWord(),
"M": DefaultEndOfWord(),
})
# Regex control verbs.
VERBS = {
"FAIL": Failure(),
"F": Failure(),
"PRUNE": Prune(),
"SKIP": Skip(),
}
