Lib/re.py

   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
  17 r"""Support for regular expressions (RE).
  18
  19 This module provides regular expression matching operations similar to
  20 those found in Perl.  It supports both 8-bit and Unicode strings; both
  21 the pattern and the strings being processed can contain null bytes and
  22 characters outside the US ASCII range.
  23
  24 Regular expressions can contain both special and ordinary characters.
  25 Most ordinary characters, like "A", "a", or "0", are the simplest
  26 regular expressions; they simply match themselves.  You can
  27 concatenate ordinary characters, so last matches the string 'last'.
  28
  29 The 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) Set the A, I, L, M, S, U, or X flag for the RE (see 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
  59 The special sequences consist of "\\" and a character from the list
  60 below.  If the ordinary character is not on the list, then the
  61 resulting 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].
  73     \S       Matches any non-whitespace character; equiv. to [^ \t\n\r\f\v].
  74     \w       Matches any alphanumeric character; equivalent to [a-zA-Z0-9_]
  75              in bytes patterns or string patterns with the ASCII flag.
  76              In string patterns without the ASCII flag, it will match the
  77              range of Unicode alphanumeric characters (letters plus digits
  78              plus underscore).
  79              With LOCALE, it will match the set [0-9_] plus characters defined
  80              as letters for the current locale.
  81     \W       Matches the complement of \w.
  82     \\       Matches a literal backslash.
  83
  84 This module exports the following functions:
  85     match    Match a regular expression pattern to the beginning of a string.
  86     search   Search a string for the presence of a pattern.
  87     sub      Substitute occurrences of a pattern found in a string.
  88     subn     Same as sub, but also return the number of substitutions made.
  89     split    Split a string by the occurrences of a pattern.
  90     findall  Find all occurrences of a pattern in a string.
  91     finditer Return an iterator yielding a match object for each match.
  92     compile  Compile a pattern into a RegexObject.
  93     purge    Clear the regular expression cache.
  94     escape   Backslash all non-alphanumerics in a string.
  95
  96 Some of the functions in this module takes flags as optional parameters:
  97     A  ASCII       For string patterns, make \w, \W, \b, \B, \d, \D
  98                    match the corresponding ASCII character categories
  99                    (rather than the whole Unicode categories, which is the
 100                    default).
 101                    For bytes patterns, this flag is the only available
 102                    behaviour and needn't be specified.
 103     I  IGNORECASE  Perform case-insensitive matching.
 104     L  LOCALE      Make \w, \W, \b, \B, dependent on the current locale.
 105     M  MULTILINE   "^" matches the beginning of lines (after a newline)
 106                    as well as the string.
 107                    "$" matches the end of lines (before a newline) as well
 108                    as the end of the string.
 109     S  DOTALL      "." matches any character at all, including the newline.
 110     X  VERBOSE     Ignore whitespace and comments for nicer looking RE's.
 111     U  UNICODE     For compatibility only. Ignored for string patterns (it
 112                    is the default), and forbidden for bytes patterns.
 113
 114 This module also defines an exception 'error'.
 115
 116 """
 117
 118 import sys
 119 import sre_compile
 120 import sre_parse
 121
 122 # public symbols
 123 __all__ = [ "match", "search", "sub", "subn", "split", "findall",
 124     "compile", "purge", "template", "escape", "A", "I", "L", "M", "S", "X",
 125     "U", "ASCII", "IGNORECASE", "LOCALE", "MULTILINE", "DOTALL", "VERBOSE",
 126     "UNICODE", "error" ]
 127
 128 __version__ = "2.2.1"
 129
 130 # flags
 131 A = ASCII = sre_compile.SRE_FLAG_ASCII # assume ascii "locale"
 132 I = IGNORECASE = sre_compile.SRE_FLAG_IGNORECASE # ignore case
 133 L = LOCALE = sre_compile.SRE_FLAG_LOCALE # assume current 8-bit locale
 134 U = UNICODE = sre_compile.SRE_FLAG_UNICODE # assume unicode "locale"
 135 M = MULTILINE = sre_compile.SRE_FLAG_MULTILINE # make anchors look for newline
 136 S = DOTALL = sre_compile.SRE_FLAG_DOTALL # make dot match newline
 137 X = VERBOSE = sre_compile.SRE_FLAG_VERBOSE # ignore whitespace and comments
 138
 139 # sre extensions (experimental, don't rely on these)
 140 T = TEMPLATE = sre_compile.SRE_FLAG_TEMPLATE # disable backtracking
 141 DEBUG = sre_compile.SRE_FLAG_DEBUG # dump pattern after compilation
 142
 143 # sre exception
 144 error = sre_compile.error
 145
 146 # --------------------------------------------------------------------
 147 # public interface
 148
 149 def match(pattern, string, flags=0):
 150     """Try to apply the pattern at the start of the string, returning
 151     a match object, or None if no match was found."""
 152     return _compile(pattern, flags).match(string)
 153
 154 def search(pattern, string, flags=0):
 155     """Scan through string looking for a match to the pattern, returning
 156     a match object, or None if no match was found."""
 157     return _compile(pattern, flags).search(string)
 158
 159 def sub(pattern, repl, string, count=0, flags=0):
 160     """Return the string obtained by replacing the leftmost
 161     non-overlapping occurrences of the pattern in string by the
 162     replacement repl.  repl can be either a string or a callable;
 163     if a string, backslash escapes in it are processed.  If it is
 164     a callable, it's passed the match object and must return
 165     a replacement string to be used."""
 166     return _compile(pattern, flags).sub(repl, string, count)
 167
 168 def subn(pattern, repl, string, count=0, flags=0):
 169     """Return a 2-tuple containing (new_string, number).
 170     new_string is the string obtained by replacing the leftmost
 171     non-overlapping occurrences of the pattern in the source
 172     string by the replacement repl.  number is the number of
 173     substitutions that were made. repl can be either a string or a
 174     callable; if a string, backslash escapes in it are processed.
 175     If it is a callable, it's passed the match object and must
 176     return a replacement string to be used."""
 177     return _compile(pattern, flags).subn(repl, string, count)
 178
 179 def split(pattern, string, maxsplit=0, flags=0):
 180     """Split the source string by the occurrences of the pattern,
 181     returning a list containing the resulting substrings."""
 182     return _compile(pattern, flags).split(string, maxsplit)
 183
 184 def findall(pattern, string, flags=0):
 185     """Return a list of all non-overlapping matches in the string.
 186
 187     If one or more groups are present in the pattern, return a
 188     list of groups; this will be a list of tuples if the pattern
 189     has more than one group.
 190
 191     Empty matches are included in the result."""
 192     return _compile(pattern, flags).findall(string)
 193
 194 if sys.hexversion >= 0x02020000:
 195     __all__.append("finditer")
 196     def finditer(pattern, string, flags=0):
 197         """Return an iterator over all non-overlapping matches in the
 198         string.  For each match, the iterator returns a match object.
 199
 200         Empty matches are included in the result."""
 201         return _compile(pattern, flags).finditer(string)
 202
 203 def compile(pattern, flags=0):
 204     "Compile a regular expression pattern, returning a pattern object."
 205     return _compile(pattern, flags)
 206
 207 def purge():
 208     "Clear the regular expression cache"
 209     _cache.clear()
 210     _cache_repl.clear()
 211
 212 def template(pattern, flags=0):
 213     "Compile a template pattern, returning a pattern object"
 214     return _compile(pattern, flags|T)
 215
 216 _alphanum_str = frozenset(
 217     "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890")
 218 _alphanum_bytes = frozenset(
 219     b"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890")
 220
 221 def escape(pattern):
 222     "Escape all non-alphanumeric characters in pattern."
 223     if isinstance(pattern, str):
 224         alphanum = _alphanum_str
 225         s = list(pattern)
 226         for i in range(len(pattern)):
 227             c = pattern[i]
 228             if c not in alphanum:
 229                 if c == "\000":
 230                     s[i] = "\\000"
 231                 else:
 232                     s[i] = "\\" + c
 233         return "".join(s)
 234     else:
 235         alphanum = _alphanum_bytes
 236         s = []
 237         esc = ord(b"\\")
 238         for c in pattern:
 239             if c in alphanum:
 240                 s.append(c)
 241             else:
 242                 if c == 0:
 243                     s.extend(b"\\000")
 244                 else:
 245                     s.append(esc)
 246                     s.append(c)
 247         return bytes(s)
 248
 249 # --------------------------------------------------------------------
 250 # internals
 251
 252 _cache = {}
 253 _cache_repl = {}
 254
 255 _pattern_type = type(sre_compile.compile("", 0))
 256
 257 _MAXCACHE = 100
 258
 259 def _compile(*key):
 260     # internal: compile pattern
 261     cachekey = (type(key[0]),) + key
 262     p = _cache.get(cachekey)
 263     if p is not None:
 264         return p
 265     pattern, flags = key
 266     if isinstance(pattern, _pattern_type):
 267         if flags:
 268             raise ValueError(
 269                 "Cannot process flags argument with a compiled pattern")
 270         return pattern
 271     if not sre_compile.isstring(pattern):
 272         raise TypeError("first argument must be string or compiled pattern")
 273     p = sre_compile.compile(pattern, flags)
 274     if len(_cache) >= _MAXCACHE:
 275         _cache.clear()
 276     _cache[cachekey] = p
 277     return p
 278
 279 def _compile_repl(*key):
 280     # internal: compile replacement pattern
 281     p = _cache_repl.get(key)
 282     if p is not None:
 283         return p
 284     repl, pattern = key
 285     p = sre_parse.parse_template(repl, pattern)
 286     if len(_cache_repl) >= _MAXCACHE:
 287         _cache_repl.clear()
 288     _cache_repl[key] = p
 289     return p
 290
 291 def _expand(pattern, match, template):
 292     # internal: match.expand implementation hook
 293     template = sre_parse.parse_template(template, pattern)
 294     return sre_parse.expand_template(template, match)
 295
 296 def _subx(pattern, template):
 297     # internal: pattern.sub/subn implementation helper
 298     template = _compile_repl(template, pattern)
 299     if not template[0] and len(template[1]) == 1:
 300         # literal replacement
 301         return template[1][0]
 302     def filter(match, template=template):
 303         return sre_parse.expand_template(template, match)
 304     return filter
 305
 306 # register myself for pickling
 307
 308 import copyreg
 309
 310 def _pickle(p):
 311     return _compile, (p.pattern, p.flags)
 312
 313 copyreg.pickle(_pattern_type, _pickle, _compile)
 314
 315 # --------------------------------------------------------------------
 316 # experimental stuff (see python-dev discussions for details)
 317
 318 class Scanner:
 319     def __init__(self, lexicon, flags=0):
 320         from sre_constants import BRANCH, SUBPATTERN
 321         self.lexicon = lexicon
 322         # combine phrases into a compound pattern
 323         p = []
 324         s = sre_parse.Pattern()
 325         s.flags = flags
 326         for phrase, action in lexicon:
 327             p.append(sre_parse.SubPattern(s, [
 328                 (SUBPATTERN, (len(p)+1, sre_parse.parse(phrase, flags))),
 329                 ]))
 330         s.groups = len(p)+1
 331         p = sre_parse.SubPattern(s, [(BRANCH, (None, p))])
 332         self.scanner = sre_compile.compile(p)
 333     def scan(self, string):
 334         result = []
 335         append = result.append
 336         match = self.scanner.scanner(string).match
 337         i = 0
 338         while 1:
 339             m = match()
 340             if not m:
 341                 break
 342             j = m.end()
 343             if i == j:
 344                 break
 345             action = self.lexicon[m.lastindex-1][1]
 346             if hasattr(action, "__call__"):
 347                 self.match = m
 348                 action = action(self, m.group())
 349             if action is not None:
 350                 append(action)
 351             i = j
 352         return result, string[i:]