Debian Codegraph @

Lib/re/__init__.py

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