Commit | Line | Data |
---|---|---|
920dae64 AT |
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. | |
33 | "*" Matches 0 or more (greedy) repetitions of the preceding RE. | |
34 | Greedy means that it will match as many repetitions as possible. | |
35 | "+" Matches 1 or more (greedy) repetitions of the preceding RE. | |
36 | "?" Matches 0 or 1 (greedy) of the preceding RE. | |
37 | *?,+?,?? Non-greedy versions of the previous three special characters. | |
38 | {m,n} Matches from m to n repetitions of the preceding RE. | |
39 | {m,n}? Non-greedy version of the above. | |
40 | "\\" Either escapes special characters or signals a special sequence. | |
41 | [] Indicates a set of characters. | |
42 | A "^" as the first character indicates a complementing set. | |
43 | "|" A|B, creates an RE that will match either A or B. | |
44 | (...) Matches the RE inside the parentheses. | |
45 | The contents can be retrieved or matched later in the string. | |
46 | (?iLmsux) Set the I, L, M, S, U, or X flag for the RE (see below). | |
47 | (?:...) Non-grouping version of regular parentheses. | |
48 | (?P<name>...) The substring matched by the group is accessible by name. | |
49 | (?P=name) Matches the text matched earlier by the group named name. | |
50 | (?#...) A comment; ignored. | |
51 | (?=...) Matches if ... matches next, but doesn't consume the string. | |
52 | (?!...) Matches if ... doesn't match next. | |
53 | ||
54 | The special sequences consist of "\\" and a character from the list | |
55 | below. If the ordinary character is not on the list, then the | |
56 | resulting RE will match the second character. | |
57 | \number Matches the contents of the group of the same number. | |
58 | \A Matches only at the start of the string. | |
59 | \Z Matches only at the end of the string. | |
60 | \b Matches the empty string, but only at the start or end of a word. | |
61 | \B Matches the empty string, but not at the start or end of a word. | |
62 | \d Matches any decimal digit; equivalent to the set [0-9]. | |
63 | \D Matches any non-digit character; equivalent to the set [^0-9]. | |
64 | \s Matches any whitespace character; equivalent to [ \t\n\r\f\v]. | |
65 | \S Matches any non-whitespace character; equiv. to [^ \t\n\r\f\v]. | |
66 | \w Matches any alphanumeric character; equivalent to [a-zA-Z0-9_]. | |
67 | With LOCALE, it will match the set [0-9_] plus characters defined | |
68 | as letters for the current locale. | |
69 | \W Matches the complement of \w. | |
70 | \\ Matches a literal backslash. | |
71 | ||
72 | This module exports the following functions: | |
73 | match Match a regular expression pattern to the beginning of a string. | |
74 | search Search a string for the presence of a pattern. | |
75 | sub Substitute occurrences of a pattern found in a string. | |
76 | subn Same as sub, but also return the number of substitutions made. | |
77 | split Split a string by the occurrences of a pattern. | |
78 | findall Find all occurrences of a pattern in a string. | |
79 | compile Compile a pattern into a RegexObject. | |
80 | purge Clear the regular expression cache. | |
81 | escape Backslash all non-alphanumerics in a string. | |
82 | ||
83 | Some of the functions in this module takes flags as optional parameters: | |
84 | I IGNORECASE Perform case-insensitive matching. | |
85 | L LOCALE Make \w, \W, \b, \B, dependent on the current locale. | |
86 | M MULTILINE "^" matches the beginning of lines as well as the string. | |
87 | "$" matches the end of lines as well as the string. | |
88 | S DOTALL "." matches any character at all, including the newline. | |
89 | X VERBOSE Ignore whitespace and comments for nicer looking RE's. | |
90 | U UNICODE Make \w, \W, \b, \B, dependent on the Unicode locale. | |
91 | ||
92 | This module also defines an exception 'error'. | |
93 | ||
94 | """ | |
95 | ||
96 | import sys | |
97 | import sre_compile | |
98 | import sre_parse | |
99 | ||
100 | # public symbols | |
101 | __all__ = [ "match", "search", "sub", "subn", "split", "findall", | |
102 | "compile", "purge", "template", "escape", "I", "L", "M", "S", "X", | |
103 | "U", "IGNORECASE", "LOCALE", "MULTILINE", "DOTALL", "VERBOSE", | |
104 | "UNICODE", "error" ] | |
105 | ||
106 | __version__ = "2.2.1" | |
107 | ||
108 | # flags | |
109 | I = IGNORECASE = sre_compile.SRE_FLAG_IGNORECASE # ignore case | |
110 | L = LOCALE = sre_compile.SRE_FLAG_LOCALE # assume current 8-bit locale | |
111 | U = UNICODE = sre_compile.SRE_FLAG_UNICODE # assume unicode locale | |
112 | M = MULTILINE = sre_compile.SRE_FLAG_MULTILINE # make anchors look for newline | |
113 | S = DOTALL = sre_compile.SRE_FLAG_DOTALL # make dot match newline | |
114 | X = VERBOSE = sre_compile.SRE_FLAG_VERBOSE # ignore whitespace and comments | |
115 | ||
116 | # sre extensions (experimental, don't rely on these) | |
117 | T = TEMPLATE = sre_compile.SRE_FLAG_TEMPLATE # disable backtracking | |
118 | DEBUG = sre_compile.SRE_FLAG_DEBUG # dump pattern after compilation | |
119 | ||
120 | # sre exception | |
121 | error = sre_compile.error | |
122 | ||
123 | # -------------------------------------------------------------------- | |
124 | # public interface | |
125 | ||
126 | def match(pattern, string, flags=0): | |
127 | """Try to apply the pattern at the start of the string, returning | |
128 | a match object, or None if no match was found.""" | |
129 | return _compile(pattern, flags).match(string) | |
130 | ||
131 | def search(pattern, string, flags=0): | |
132 | """Scan through string looking for a match to the pattern, returning | |
133 | a match object, or None if no match was found.""" | |
134 | return _compile(pattern, flags).search(string) | |
135 | ||
136 | def sub(pattern, repl, string, count=0): | |
137 | """Return the string obtained by replacing the leftmost | |
138 | non-overlapping occurrences of the pattern in string by the | |
139 | replacement repl. repl can be either a string or a callable; | |
140 | if a callable, it's passed the match object and must return | |
141 | a replacement string to be used.""" | |
142 | return _compile(pattern, 0).sub(repl, string, count) | |
143 | ||
144 | def subn(pattern, repl, string, count=0): | |
145 | """Return a 2-tuple containing (new_string, number). | |
146 | new_string is the string obtained by replacing the leftmost | |
147 | non-overlapping occurrences of the pattern in the source | |
148 | string by the replacement repl. number is the number of | |
149 | substitutions that were made. repl can be either a string or a | |
150 | callable; if a callable, it's passed the match object and must | |
151 | return a replacement string to be used.""" | |
152 | return _compile(pattern, 0).subn(repl, string, count) | |
153 | ||
154 | def split(pattern, string, maxsplit=0): | |
155 | """Split the source string by the occurrences of the pattern, | |
156 | returning a list containing the resulting substrings.""" | |
157 | return _compile(pattern, 0).split(string, maxsplit) | |
158 | ||
159 | def findall(pattern, string, flags=0): | |
160 | """Return a list of all non-overlapping matches in the string. | |
161 | ||
162 | If one or more groups are present in the pattern, return a | |
163 | list of groups; this will be a list of tuples if the pattern | |
164 | has more than one group. | |
165 | ||
166 | Empty matches are included in the result.""" | |
167 | return _compile(pattern, flags).findall(string) | |
168 | ||
169 | if sys.hexversion >= 0x02020000: | |
170 | __all__.append("finditer") | |
171 | def finditer(pattern, string, flags=0): | |
172 | """Return an iterator over all non-overlapping matches in the | |
173 | string. For each match, the iterator returns a match object. | |
174 | ||
175 | Empty matches are included in the result.""" | |
176 | return _compile(pattern, flags).finditer(string) | |
177 | ||
178 | def compile(pattern, flags=0): | |
179 | "Compile a regular expression pattern, returning a pattern object." | |
180 | return _compile(pattern, flags) | |
181 | ||
182 | def purge(): | |
183 | "Clear the regular expression cache" | |
184 | _cache.clear() | |
185 | _cache_repl.clear() | |
186 | ||
187 | def template(pattern, flags=0): | |
188 | "Compile a template pattern, returning a pattern object" | |
189 | return _compile(pattern, flags|T) | |
190 | ||
191 | def escape(pattern): | |
192 | "Escape all non-alphanumeric characters in pattern." | |
193 | s = list(pattern) | |
194 | for i in range(len(pattern)): | |
195 | c = pattern[i] | |
196 | if not ("a" <= c <= "z" or "A" <= c <= "Z" or "0" <= c <= "9"): | |
197 | if c == "\000": | |
198 | s[i] = "\\000" | |
199 | else: | |
200 | s[i] = "\\" + c | |
201 | return pattern[:0].join(s) | |
202 | ||
203 | # -------------------------------------------------------------------- | |
204 | # internals | |
205 | ||
206 | _cache = {} | |
207 | _cache_repl = {} | |
208 | ||
209 | _pattern_type = type(sre_compile.compile("", 0)) | |
210 | ||
211 | _MAXCACHE = 100 | |
212 | ||
213 | def _compile(*key): | |
214 | # internal: compile pattern | |
215 | cachekey = (type(key[0]),) + key | |
216 | p = _cache.get(cachekey) | |
217 | if p is not None: | |
218 | return p | |
219 | pattern, flags = key | |
220 | if isinstance(pattern, _pattern_type): | |
221 | return pattern | |
222 | if not sre_compile.isstring(pattern): | |
223 | raise TypeError, "first argument must be string or compiled pattern" | |
224 | try: | |
225 | p = sre_compile.compile(pattern, flags) | |
226 | except error, v: | |
227 | raise error, v # invalid expression | |
228 | if len(_cache) >= _MAXCACHE: | |
229 | _cache.clear() | |
230 | _cache[cachekey] = p | |
231 | return p | |
232 | ||
233 | def _compile_repl(*key): | |
234 | # internal: compile replacement pattern | |
235 | p = _cache_repl.get(key) | |
236 | if p is not None: | |
237 | return p | |
238 | repl, pattern = key | |
239 | try: | |
240 | p = sre_parse.parse_template(repl, pattern) | |
241 | except error, v: | |
242 | raise error, v # invalid expression | |
243 | if len(_cache_repl) >= _MAXCACHE: | |
244 | _cache_repl.clear() | |
245 | _cache_repl[key] = p | |
246 | return p | |
247 | ||
248 | def _expand(pattern, match, template): | |
249 | # internal: match.expand implementation hook | |
250 | template = sre_parse.parse_template(template, pattern) | |
251 | return sre_parse.expand_template(template, match) | |
252 | ||
253 | def _subx(pattern, template): | |
254 | # internal: pattern.sub/subn implementation helper | |
255 | template = _compile_repl(template, pattern) | |
256 | if not template[0] and len(template[1]) == 1: | |
257 | # literal replacement | |
258 | return template[1][0] | |
259 | def filter(match, template=template): | |
260 | return sre_parse.expand_template(template, match) | |
261 | return filter | |
262 | ||
263 | # register myself for pickling | |
264 | ||
265 | import copy_reg | |
266 | ||
267 | def _pickle(p): | |
268 | return _compile, (p.pattern, p.flags) | |
269 | ||
270 | copy_reg.pickle(_pattern_type, _pickle, _compile) | |
271 | ||
272 | # -------------------------------------------------------------------- | |
273 | # experimental stuff (see python-dev discussions for details) | |
274 | ||
275 | class Scanner: | |
276 | def __init__(self, lexicon, flags=0): | |
277 | from sre_constants import BRANCH, SUBPATTERN | |
278 | self.lexicon = lexicon | |
279 | # combine phrases into a compound pattern | |
280 | p = [] | |
281 | s = sre_parse.Pattern() | |
282 | s.flags = flags | |
283 | for phrase, action in lexicon: | |
284 | p.append(sre_parse.SubPattern(s, [ | |
285 | (SUBPATTERN, (len(p)+1, sre_parse.parse(phrase, flags))), | |
286 | ])) | |
287 | p = sre_parse.SubPattern(s, [(BRANCH, (None, p))]) | |
288 | s.groups = len(p) | |
289 | self.scanner = sre_compile.compile(p) | |
290 | def scan(self, string): | |
291 | result = [] | |
292 | append = result.append | |
293 | match = self.scanner.scanner(string).match | |
294 | i = 0 | |
295 | while 1: | |
296 | m = match() | |
297 | if not m: | |
298 | break | |
299 | j = m.end() | |
300 | if i == j: | |
301 | break | |
302 | action = self.lexicon[m.lastindex-1][1] | |
303 | if callable(action): | |
304 | self.match = m | |
305 | action = action(self, m.group()) | |
306 | if action is not None: | |
307 | append(action) | |
308 | i = j | |
309 | return result, string[i:] |