1#
2# Secret Labs' Regular Expression Engine
3#
4# re-compatible interface for the sre matching engine
5#
6# Copyright (c) 1998-2001 by Secret Labs AB.  All rights reserved.
7#
8# This version of the SRE library can be redistributed under CNRI's
9# Python 1.6 license.  For any other use, please contact Secret Labs
10# AB (info@pythonware.com).
11#
12# Portions of this engine have been developed in cooperation with
13# CNRI.  Hewlett-Packard provided funding for 1.6 integration and
14# other compatibility work.
15#
16
17r"""Support for regular expressions (RE).
18
19This module provides regular expression matching operations similar to
20those found in Perl.  It supports both 8-bit and Unicode strings; both
21the pattern and the strings being processed can contain null bytes and
22characters outside the US ASCII range.
23
24Regular expressions can contain both special and ordinary characters.
25Most ordinary characters, like "A", "a", or "0", are the simplest
26regular expressions; they simply match themselves.  You can
27concatenate ordinary characters, so last matches the string 'last'.
28
29The special characters are:
30    "."      Matches any character except a newline.
31    "^"      Matches the start of the string.
32    "$"      Matches the end of the string or just before the newline at
33             the end of the string.
34    "*"      Matches 0 or more (greedy) repetitions of the preceding RE.
35             Greedy means that it will match as many repetitions as possible.
36    "+"      Matches 1 or more (greedy) repetitions of the preceding RE.
37    "?"      Matches 0 or 1 (greedy) of the preceding RE.
38    *?,+?,?? Non-greedy versions of the previous three special characters.
39    {m,n}    Matches from m to n repetitions of the preceding RE.
40    {m,n}?   Non-greedy version of the above.
41    "\\"     Either escapes special characters or signals a special sequence.
42    []       Indicates a set of characters.
43             A "^" as the first character indicates a complementing set.
44    "|"      A|B, creates an RE that will match either A or B.
45    (...)    Matches the RE inside the parentheses.
46             The contents can be retrieved or matched later in the string.
47    (?aiLmsux) The letters set the corresponding flags defined below.
48    (?:...)  Non-grouping version of regular parentheses.
49    (?P<name>...) The substring matched by the group is accessible by name.
50    (?P=name)     Matches the text matched earlier by the group named name.
51    (?#...)  A comment; ignored.
52    (?=...)  Matches if ... matches next, but doesn't consume the string.
53    (?!...)  Matches if ... doesn't match next.
54    (?<=...) Matches if preceded by ... (must be fixed length).
55    (?<!...) Matches if not preceded by ... (must be fixed length).
56    (?(id/name)yes|no) Matches yes pattern if the group with id/name matched,
57                       the (optional) no pattern otherwise.
58
59The special sequences consist of "\\" and a character from the list
60below.  If the ordinary character is not on the list, then the
61resulting RE will match the second character.
62    \number  Matches the contents of the group of the same number.
63    \A       Matches only at the start of the string.
64    \Z       Matches only at the end of the string.
65    \b       Matches the empty string, but only at the start or end of a word.
66    \B       Matches the empty string, but not at the start or end of a word.
67    \d       Matches any decimal digit; equivalent to the set [0-9] in
68             bytes patterns or string patterns with the ASCII flag.
69             In string patterns without the ASCII flag, it will match the whole
70             range of Unicode digits.
71    \D       Matches any non-digit character; equivalent to [^\d].
72    \s       Matches any whitespace character; equivalent to [ \t\n\r\f\v] in
73             bytes patterns or string patterns with the ASCII flag.
74             In string patterns without the ASCII flag, it will match the whole
75             range of Unicode whitespace characters.
76    \S       Matches any non-whitespace character; equivalent to [^\s].
77    \w       Matches any alphanumeric character; equivalent to [a-zA-Z0-9_]
78             in bytes patterns or string patterns with the ASCII flag.
79             In string patterns without the ASCII flag, it will match the
80             range of Unicode alphanumeric characters (letters plus digits
81             plus underscore).
82             With LOCALE, it will match the set [0-9_] plus characters defined
83             as letters for the current locale.
84    \W       Matches the complement of \w.
85    \\       Matches a literal backslash.
86
87This module exports the following functions:
88    match     Match a regular expression pattern to the beginning of a string.
89    fullmatch Match a regular expression pattern to all of a string.
90    search    Search a string for the presence of a pattern.
91    sub       Substitute occurrences of a pattern found in a string.
92    subn      Same as sub, but also return the number of substitutions made.
93    split     Split a string by the occurrences of a pattern.
94    findall   Find all occurrences of a pattern in a string.
95    finditer  Return an iterator yielding a Match object for each match.
96    compile   Compile a pattern into a Pattern object.
97    purge     Clear the regular expression cache.
98    escape    Backslash all non-alphanumerics in a string.
99
100Each function other than purge and escape can take an optional 'flags' argument
101consisting of one or more of the following module constants, joined by "|".
102A, L, and U are mutually exclusive.
103    A  ASCII       For string patterns, make \w, \W, \b, \B, \d, \D
104                   match the corresponding ASCII character categories
105                   (rather than the whole Unicode categories, which is the
106                   default).
107                   For bytes patterns, this flag is the only available
108                   behaviour and needn't be specified.
109    I  IGNORECASE  Perform case-insensitive matching.
110    L  LOCALE      Make \w, \W, \b, \B, dependent on the current locale.
111    M  MULTILINE   "^" matches the beginning of lines (after a newline)
112                   as well as the string.
113                   "$" matches the end of lines (before a newline) as well
114                   as the end of the string.
115    S  DOTALL      "." matches any character at all, including the newline.
116    X  VERBOSE     Ignore whitespace and comments for nicer looking RE's.
117    U  UNICODE     For compatibility only. Ignored for string patterns (it
118                   is the default), and forbidden for bytes patterns.
119
120This module also defines an exception 'error'.
121
122"""
123
124import enum
125import sre_compile
126import sre_parse
127import functools
128try:
129    import _locale
130except ImportError:
131    _locale = None
132
133
134# public symbols
135__all__ = [
136    "match", "fullmatch", "search", "sub", "subn", "split",
137    "findall", "finditer", "compile", "purge", "template", "escape",
138    "error", "Pattern", "Match", "A", "I", "L", "M", "S", "X", "U",
139    "ASCII", "IGNORECASE", "LOCALE", "MULTILINE", "DOTALL", "VERBOSE",
140    "UNICODE",
141]
142
143__version__ = "2.2.1"
144
145class RegexFlag(enum.IntFlag):
146    ASCII = A = sre_compile.SRE_FLAG_ASCII # assume ascii "locale"
147    IGNORECASE = I = sre_compile.SRE_FLAG_IGNORECASE # ignore case
148    LOCALE = L = sre_compile.SRE_FLAG_LOCALE # assume current 8-bit locale
149    UNICODE = U = sre_compile.SRE_FLAG_UNICODE # assume unicode "locale"
150    MULTILINE = M = sre_compile.SRE_FLAG_MULTILINE # make anchors look for newline
151    DOTALL = S = sre_compile.SRE_FLAG_DOTALL # make dot match newline
152    VERBOSE = X = sre_compile.SRE_FLAG_VERBOSE # ignore whitespace and comments
153    # sre extensions (experimental, don't rely on these)
154    TEMPLATE = T = sre_compile.SRE_FLAG_TEMPLATE # disable backtracking
155    DEBUG = sre_compile.SRE_FLAG_DEBUG # dump pattern after compilation
156
157    def __repr__(self):
158        if self._name_ is not None:
159            return f're.{self._name_}'
160        value = self._value_
161        members = []
162        negative = value < 0
163        if negative:
164            value = ~value
165        for m in self.__class__:
166            if value & m._value_:
167                value &= ~m._value_
168                members.append(f're.{m._name_}')
169        if value:
170            members.append(hex(value))
171        res = '|'.join(members)
172        if negative:
173            if len(members) > 1:
174                res = f'~({res})'
175            else:
176                res = f'~{res}'
177        return res
178    __str__ = object.__str__
179
180globals().update(RegexFlag.__members__)
181
182# sre exception
183error = sre_compile.error
184
185# --------------------------------------------------------------------
186# public interface
187
188def match(pattern, string, flags=0):
189    """Try to apply the pattern at the start of the string, returning
190    a Match object, or None if no match was found."""
191    return _compile(pattern, flags).match(string)
192
193def fullmatch(pattern, string, flags=0):
194    """Try to apply the pattern to all of the string, returning
195    a Match object, or None if no match was found."""
196    return _compile(pattern, flags).fullmatch(string)
197
198def search(pattern, string, flags=0):
199    """Scan through string looking for a match to the pattern, returning
200    a Match object, or None if no match was found."""
201    return _compile(pattern, flags).search(string)
202
203def sub(pattern, repl, string, count=0, flags=0):
204    """Return the string obtained by replacing the leftmost
205    non-overlapping occurrences of the pattern in string by the
206    replacement repl.  repl can be either a string or a callable;
207    if a string, backslash escapes in it are processed.  If it is
208    a callable, it's passed the Match object and must return
209    a replacement string to be used."""
210    return _compile(pattern, flags).sub(repl, string, count)
211
212def subn(pattern, repl, string, count=0, flags=0):
213    """Return a 2-tuple containing (new_string, number).
214    new_string is the string obtained by replacing the leftmost
215    non-overlapping occurrences of the pattern in the source
216    string by the replacement repl.  number is the number of
217    substitutions that were made. repl can be either a string or a
218    callable; if a string, backslash escapes in it are processed.
219    If it is a callable, it's passed the Match object and must
220    return a replacement string to be used."""
221    return _compile(pattern, flags).subn(repl, string, count)
222
223def split(pattern, string, maxsplit=0, flags=0):
224    """Split the source string by the occurrences of the pattern,
225    returning a list containing the resulting substrings.  If
226    capturing parentheses are used in pattern, then the text of all
227    groups in the pattern are also returned as part of the resulting
228    list.  If maxsplit is nonzero, at most maxsplit splits occur,
229    and the remainder of the string is returned as the final element
230    of the list."""
231    return _compile(pattern, flags).split(string, maxsplit)
232
233def findall(pattern, string, flags=0):
234    """Return a list of all non-overlapping matches in the string.
235
236    If one or more capturing groups are present in the pattern, return
237    a list of groups; this will be a list of tuples if the pattern
238    has more than one group.
239
240    Empty matches are included in the result."""
241    return _compile(pattern, flags).findall(string)
242
243def finditer(pattern, string, flags=0):
244    """Return an iterator over all non-overlapping matches in the
245    string.  For each match, the iterator returns a Match object.
246
247    Empty matches are included in the result."""
248    return _compile(pattern, flags).finditer(string)
249
250def compile(pattern, flags=0):
251    "Compile a regular expression pattern, returning a Pattern object."
252    return _compile(pattern, flags)
253
254def purge():
255    "Clear the regular expression caches"
256    _cache.clear()
257    _compile_repl.cache_clear()
258
259def template(pattern, flags=0):
260    "Compile a template pattern, returning a Pattern object"
261    return _compile(pattern, flags|T)
262
263# SPECIAL_CHARS
264# closing ')', '}' and ']'
265# '-' (a range in character set)
266# '&', '~', (extended character set operations)
267# '#' (comment) and WHITESPACE (ignored) in verbose mode
268_special_chars_map = {i: '\\' + chr(i) for i in b'()[]{}?*+-|^$\\.&~# \t\n\r\v\f'}
269
270def escape(pattern):
271    """
272    Escape special characters in a string.
273    """
274    if isinstance(pattern, str):
275        return pattern.translate(_special_chars_map)
276    else:
277        pattern = str(pattern, 'latin1')
278        return pattern.translate(_special_chars_map).encode('latin1')
279
280Pattern = type(sre_compile.compile('', 0))
281Match = type(sre_compile.compile('', 0).match(''))
282
283# --------------------------------------------------------------------
284# internals
285
286_cache = {}  # ordered!
287
288_MAXCACHE = 512
289def _compile(pattern, flags):
290    # internal: compile pattern
291    if isinstance(flags, RegexFlag):
292        flags = flags.value
293    try:
294        return _cache[type(pattern), pattern, flags]
295    except KeyError:
296        pass
297    if isinstance(pattern, Pattern):
298        if flags:
299            raise ValueError(
300                "cannot process flags argument with a compiled pattern")
301        return pattern
302    if not sre_compile.isstring(pattern):
303        raise TypeError("first argument must be string or compiled pattern")
304    p = sre_compile.compile(pattern, flags)
305    if not (flags & DEBUG):
306        if len(_cache) >= _MAXCACHE:
307            # Drop the oldest item
308            try:
309                del _cache[next(iter(_cache))]
310            except (StopIteration, RuntimeError, KeyError):
311                pass
312        _cache[type(pattern), pattern, flags] = p
313    return p
314
315@functools.lru_cache(_MAXCACHE)
316def _compile_repl(repl, pattern):
317    # internal: compile replacement pattern
318    return sre_parse.parse_template(repl, pattern)
319
320def _expand(pattern, match, template):
321    # internal: Match.expand implementation hook
322    template = sre_parse.parse_template(template, pattern)
323    return sre_parse.expand_template(template, match)
324
325def _subx(pattern, template):
326    # internal: Pattern.sub/subn implementation helper
327    template = _compile_repl(template, pattern)
328    if not template[0] and len(template[1]) == 1:
329        # literal replacement
330        return template[1][0]
331    def filter(match, template=template):
332        return sre_parse.expand_template(template, match)
333    return filter
334
335# register myself for pickling
336
337import copyreg
338
339def _pickle(p):
340    return _compile, (p.pattern, p.flags)
341
342copyreg.pickle(Pattern, _pickle, _compile)
343
344# --------------------------------------------------------------------
345# experimental stuff (see python-dev discussions for details)
346
347class Scanner:
348    def __init__(self, lexicon, flags=0):
349        from sre_constants import BRANCH, SUBPATTERN
350        if isinstance(flags, RegexFlag):
351            flags = flags.value
352        self.lexicon = lexicon
353        # combine phrases into a compound pattern
354        p = []
355        s = sre_parse.State()
356        s.flags = flags
357        for phrase, action in lexicon:
358            gid = s.opengroup()
359            p.append(sre_parse.SubPattern(s, [
360                (SUBPATTERN, (gid, 0, 0, sre_parse.parse(phrase, flags))),
361                ]))
362            s.closegroup(gid, p[-1])
363        p = sre_parse.SubPattern(s, [(BRANCH, (None, p))])
364        self.scanner = sre_compile.compile(p)
365    def scan(self, string):
366        result = []
367        append = result.append
368        match = self.scanner.scanner(string).match
369        i = 0
370        while True:
371            m = match()
372            if not m:
373                break
374            j = m.end()
375            if i == j:
376                break
377            action = self.lexicon[m.lastindex-1][1]
378            if callable(action):
379                self.match = m
380                action = action(self, m.group())
381            if action is not None:
382                append(action)
383            i = j
384        return result, string[i:]
385