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) 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
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] 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
87 This 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
100 Each function other than purge and escape can take an optional 'flags' argument
101 consisting of one or more of the following module constants, joined by "|".
102 A, 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
120 This module also defines an exception 'error'.
121
122 """
123
124 import enum
125 from . import _compiler, _parser
126 import functools
127 import _sre
128
129
130 # public symbols
131 __all__ = [
132 "match", "fullmatch", "search", "sub", "subn", "split",
133 "findall", "finditer", "compile", "purge", "template", "escape",
134 "error", "Pattern", "Match", "A", "I", "L", "M", "S", "X", "U",
135 "ASCII", "IGNORECASE", "LOCALE", "MULTILINE", "DOTALL", "VERBOSE",
136 "UNICODE", "NOFLAG", "RegexFlag",
137 ]
138
139 __version__ = "2.2.1"
140
141 @enum.global_enum
142 @enum._simple_enum(enum.IntFlag, boundary=enum.KEEP)
143 class ESC[4;38;5;81mRegexFlag:
144 NOFLAG = 0
145 ASCII = A = _compiler.SRE_FLAG_ASCII # assume ascii "locale"
146 IGNORECASE = I = _compiler.SRE_FLAG_IGNORECASE # ignore case
147 LOCALE = L = _compiler.SRE_FLAG_LOCALE # assume current 8-bit locale
148 UNICODE = U = _compiler.SRE_FLAG_UNICODE # assume unicode "locale"
149 MULTILINE = M = _compiler.SRE_FLAG_MULTILINE # make anchors look for newline
150 DOTALL = S = _compiler.SRE_FLAG_DOTALL # make dot match newline
151 VERBOSE = X = _compiler.SRE_FLAG_VERBOSE # ignore whitespace and comments
152 # sre extensions (experimental, don't rely on these)
153 TEMPLATE = T = _compiler.SRE_FLAG_TEMPLATE # unknown purpose, deprecated
154 DEBUG = _compiler.SRE_FLAG_DEBUG # dump pattern after compilation
155 __str__ = object.__str__
156 _numeric_repr_ = hex
157
158 # sre exception
159 error = _compiler.error
160
161 # --------------------------------------------------------------------
162 # public interface
163
164 def match(pattern, string, flags=0):
165 """Try to apply the pattern at the start of the string, returning
166 a Match object, or None if no match was found."""
167 return _compile(pattern, flags).match(string)
168
169 def fullmatch(pattern, string, flags=0):
170 """Try to apply the pattern to all of the string, returning
171 a Match object, or None if no match was found."""
172 return _compile(pattern, flags).fullmatch(string)
173
174 def search(pattern, string, flags=0):
175 """Scan through string looking for a match to the pattern, returning
176 a Match object, or None if no match was found."""
177 return _compile(pattern, flags).search(string)
178
179 def sub(pattern, repl, string, count=0, flags=0):
180 """Return the string obtained by replacing the leftmost
181 non-overlapping occurrences of the pattern in string by the
182 replacement repl. repl can be either a string or a callable;
183 if a string, backslash escapes in it are processed. If it is
184 a callable, it's passed the Match object and must return
185 a replacement string to be used."""
186 return _compile(pattern, flags).sub(repl, string, count)
187
188 def subn(pattern, repl, string, count=0, flags=0):
189 """Return a 2-tuple containing (new_string, number).
190 new_string is the string obtained by replacing the leftmost
191 non-overlapping occurrences of the pattern in the source
192 string by the replacement repl. number is the number of
193 substitutions that were made. repl can be either a string or a
194 callable; if a string, backslash escapes in it are processed.
195 If it is a callable, it's passed the Match object and must
196 return a replacement string to be used."""
197 return _compile(pattern, flags).subn(repl, string, count)
198
199 def split(pattern, string, maxsplit=0, flags=0):
200 """Split the source string by the occurrences of the pattern,
201 returning a list containing the resulting substrings. If
202 capturing parentheses are used in pattern, then the text of all
203 groups in the pattern are also returned as part of the resulting
204 list. If maxsplit is nonzero, at most maxsplit splits occur,
205 and the remainder of the string is returned as the final element
206 of the list."""
207 return _compile(pattern, flags).split(string, maxsplit)
208
209 def findall(pattern, string, flags=0):
210 """Return a list of all non-overlapping matches in the string.
211
212 If one or more capturing groups are present in the pattern, return
213 a list of groups; this will be a list of tuples if the pattern
214 has more than one group.
215
216 Empty matches are included in the result."""
217 return _compile(pattern, flags).findall(string)
218
219 def finditer(pattern, string, flags=0):
220 """Return an iterator over all non-overlapping matches in the
221 string. For each match, the iterator returns a Match object.
222
223 Empty matches are included in the result."""
224 return _compile(pattern, flags).finditer(string)
225
226 def compile(pattern, flags=0):
227 "Compile a regular expression pattern, returning a Pattern object."
228 return _compile(pattern, flags)
229
230 def purge():
231 "Clear the regular expression caches"
232 _cache.clear()
233 _cache2.clear()
234 _compile_template.cache_clear()
235
236 def template(pattern, flags=0):
237 "Compile a template pattern, returning a Pattern object, deprecated"
238 import warnings
239 warnings.warn("The re.template() function is deprecated "
240 "as it is an undocumented function "
241 "without an obvious purpose. "
242 "Use re.compile() instead.",
243 DeprecationWarning)
244 with warnings.catch_warnings():
245 warnings.simplefilter("ignore", DeprecationWarning) # warn just once
246 return _compile(pattern, flags|T)
247
248 # SPECIAL_CHARS
249 # closing ')', '}' and ']'
250 # '-' (a range in character set)
251 # '&', '~', (extended character set operations)
252 # '#' (comment) and WHITESPACE (ignored) in verbose mode
253 _special_chars_map = {i: '\\' + chr(i) for i in b'()[]{}?*+-|^$\\.&~# \t\n\r\v\f'}
254
255 def escape(pattern):
256 """
257 Escape special characters in a string.
258 """
259 if isinstance(pattern, str):
260 return pattern.translate(_special_chars_map)
261 else:
262 pattern = str(pattern, 'latin1')
263 return pattern.translate(_special_chars_map).encode('latin1')
264
265 Pattern = type(_compiler.compile('', 0))
266 Match = type(_compiler.compile('', 0).match(''))
267
268 # --------------------------------------------------------------------
269 # internals
270
271 # Use the fact that dict keeps the insertion order.
272 # _cache2 uses the simple FIFO policy which has better latency.
273 # _cache uses the LRU policy which has better hit rate.
274 _cache = {} # LRU
275 _cache2 = {} # FIFO
276 _MAXCACHE = 512
277 _MAXCACHE2 = 256
278 assert _MAXCACHE2 < _MAXCACHE
279
280 def _compile(pattern, flags):
281 # internal: compile pattern
282 if isinstance(flags, RegexFlag):
283 flags = flags.value
284 try:
285 return _cache2[type(pattern), pattern, flags]
286 except KeyError:
287 pass
288
289 key = (type(pattern), pattern, flags)
290 # Item in _cache should be moved to the end if found.
291 p = _cache.pop(key, None)
292 if p is None:
293 if isinstance(pattern, Pattern):
294 if flags:
295 raise ValueError(
296 "cannot process flags argument with a compiled pattern")
297 return pattern
298 if not _compiler.isstring(pattern):
299 raise TypeError("first argument must be string or compiled pattern")
300 if flags & T:
301 import warnings
302 warnings.warn("The re.TEMPLATE/re.T flag is deprecated "
303 "as it is an undocumented flag "
304 "without an obvious purpose. "
305 "Don't use it.",
306 DeprecationWarning)
307 p = _compiler.compile(pattern, flags)
308 if flags & DEBUG:
309 return p
310 if len(_cache) >= _MAXCACHE:
311 # Drop the least recently used item.
312 # next(iter(_cache)) is known to have linear amortized time,
313 # but it is used here to avoid a dependency from using OrderedDict.
314 # For the small _MAXCACHE value it doesn't make much of a difference.
315 try:
316 del _cache[next(iter(_cache))]
317 except (StopIteration, RuntimeError, KeyError):
318 pass
319 # Append to the end.
320 _cache[key] = p
321
322 if len(_cache2) >= _MAXCACHE2:
323 # Drop the oldest item.
324 try:
325 del _cache2[next(iter(_cache2))]
326 except (StopIteration, RuntimeError, KeyError):
327 pass
328 _cache2[key] = p
329 return p
330
331 @functools.lru_cache(_MAXCACHE)
332 def _compile_template(pattern, repl):
333 # internal: compile replacement pattern
334 return _sre.template(pattern, _parser.parse_template(repl, pattern))
335
336 # register myself for pickling
337
338 import copyreg
339
340 def _pickle(p):
341 return _compile, (p.pattern, p.flags)
342
343 copyreg.pickle(Pattern, _pickle, _compile)
344
345 # --------------------------------------------------------------------
346 # experimental stuff (see python-dev discussions for details)
347
348 class ESC[4;38;5;81mScanner:
349 def __init__(self, lexicon, flags=0):
350 from ._constants import BRANCH, SUBPATTERN
351 if isinstance(flags, RegexFlag):
352 flags = flags.value
353 self.lexicon = lexicon
354 # combine phrases into a compound pattern
355 p = []
356 s = _parser.State()
357 s.flags = flags
358 for phrase, action in lexicon:
359 gid = s.opengroup()
360 p.append(_parser.SubPattern(s, [
361 (SUBPATTERN, (gid, 0, 0, _parser.parse(phrase, flags))),
362 ]))
363 s.closegroup(gid, p[-1])
364 p = _parser.SubPattern(s, [(BRANCH, (None, p))])
365 self.scanner = _compiler.compile(p)
366 def scan(self, string):
367 result = []
368 append = result.append
369 match = self.scanner.scanner(string).match
370 i = 0
371 while True:
372 m = match()
373 if not m:
374 break
375 j = m.end()
376 if i == j:
377 break
378 action = self.lexicon[m.lastindex-1][1]
379 if callable(action):
380 self.match = m
381 action = action(self, m.group())
382 if action is not None:
383 append(action)
384 i = j
385 return result, string[i:]