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