blob: ffe2bc36e6439320c5cbc2ee691910f9e8a21750 [file] [log] [blame]
Guido van Rossum7627c0d2000-03-31 14:58:54 +00001#
2# Secret Labs' Regular Expression Engine
Guido van Rossum7627c0d2000-03-31 14:58:54 +00003#
4# re-compatible interface for the sre matching engine
5#
Fredrik Lundh770617b2001-01-14 15:06:11 +00006# Copyright (c) 1998-2001 by Secret Labs AB. All rights reserved.
Guido van Rossum7627c0d2000-03-31 14:58:54 +00007#
Fredrik Lundh29c4ba92000-08-01 18:20:07 +00008# 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#
Guido van Rossum7627c0d2000-03-31 14:58:54 +000012# Portions of this engine have been developed in cooperation with
Fredrik Lundh29c4ba92000-08-01 18:20:07 +000013# CNRI. Hewlett-Packard provided funding for 1.6 integration and
Guido van Rossum7627c0d2000-03-31 14:58:54 +000014# other compatibility work.
15#
16
Fred Drake9f5b8222001-09-04 19:20:06 +000017r"""Support for regular expressions (RE).
Fred Drakeb8f22742001-09-04 19:10:20 +000018
19This module provides regular expression matching operations similar to
Fredrik Lundhdac58492001-10-21 21:48:30 +000020those found in Perl. It supports both 8-bit and Unicode strings; both
21the pattern and the strings being processed can contain null bytes and
22characters outside the US ASCII range.
Fred Drakeb8f22742001-09-04 19:10:20 +000023
Fredrik Lundhdac58492001-10-21 21:48:30 +000024Regular expressions can contain both special and ordinary characters.
25Most ordinary characters, like "A", "a", or "0", are the simplest
26regular expressions; they simply match themselves. You can
Fred Drakeb8f22742001-09-04 19:10:20 +000027concatenate ordinary characters, so last matches the string 'last'.
28
29The 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.
Fredrik Lundhdac58492001-10-21 21:48:30 +000046 (?iLmsux) Set the I, L, M, S, U, or X flag for the RE (see below).
Fred Drakeb8f22742001-09-04 19:10:20 +000047 (?:...) 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
54The special sequences consist of "\\" and a character from the list
Fredrik Lundhdac58492001-10-21 21:48:30 +000055below. If the ordinary character is not on the list, then the
Fred Drakeb8f22742001-09-04 19:10:20 +000056resulting RE will match the second character.
Fred Drake9f5b8222001-09-04 19:20:06 +000057 \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_].
Fred Drakeb8f22742001-09-04 19:10:20 +000067 With LOCALE, it will match the set [0-9_] plus characters defined
68 as letters for the current locale.
Fred Drake9f5b8222001-09-04 19:20:06 +000069 \W Matches the complement of \w.
70 \\ Matches a literal backslash.
Fred Drakeb8f22742001-09-04 19:10:20 +000071
72This 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.
Fred Drakeb8f22742001-09-04 19:10:20 +000081 escape Backslash all non-alphanumerics in a string.
82
83Some 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.
Fredrik Lundh21009b92001-09-18 18:47:09 +000090 U UNICODE Make \w, \W, \b, \B, dependent on the Unicode locale.
Fred Drakeb8f22742001-09-04 19:10:20 +000091
92This module also defines an exception 'error'.
93
94"""
Fredrik Lundh21009b92001-09-18 18:47:09 +000095
Fredrik Lundh703ce812001-10-24 22:16:30 +000096import sys
Guido van Rossum7627c0d2000-03-31 14:58:54 +000097import sre_compile
Fredrik Lundh436c3d582000-06-29 08:58:44 +000098import sre_parse
Guido van Rossum7627c0d2000-03-31 14:58:54 +000099
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000100# 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
Fredrik Lundhbec95b92001-10-21 16:47:57 +0000106__version__ = "2.2.1"
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000107
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000108# this module works under 1.5.2 and later. don't use string methods
109import string
Skip Montanaro0de65802001-02-15 22:15:14 +0000110
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000111# flags
Fredrik Lundh770617b2001-01-14 15:06:11 +0000112I = IGNORECASE = sre_compile.SRE_FLAG_IGNORECASE # ignore case
113L = LOCALE = sre_compile.SRE_FLAG_LOCALE # assume current 8-bit locale
114U = UNICODE = sre_compile.SRE_FLAG_UNICODE # assume unicode locale
115M = MULTILINE = sre_compile.SRE_FLAG_MULTILINE # make anchors look for newline
116S = DOTALL = sre_compile.SRE_FLAG_DOTALL # make dot match newline
117X = VERBOSE = sre_compile.SRE_FLAG_VERBOSE # ignore whitespace and comments
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000118
Fredrik Lundh770617b2001-01-14 15:06:11 +0000119# sre extensions (experimental, don't rely on these)
120T = TEMPLATE = sre_compile.SRE_FLAG_TEMPLATE # disable backtracking
121DEBUG = sre_compile.SRE_FLAG_DEBUG # dump pattern after compilation
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000122
123# sre exception
Fredrik Lundhbe2211e2000-06-29 16:57:40 +0000124error = sre_compile.error
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000125
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000126# --------------------------------------------------------------------
127# public interface
128
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000129def match(pattern, string, flags=0):
Fredrik Lundh770617b2001-01-14 15:06:11 +0000130 """Try to apply the pattern at the start of the string, returning
131 a match object, or None if no match was found."""
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000132 return _compile(pattern, flags).match(string)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000133
134def search(pattern, string, flags=0):
Fredrik Lundh770617b2001-01-14 15:06:11 +0000135 """Scan through string looking for a match to the pattern, returning
136 a match object, or None if no match was found."""
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000137 return _compile(pattern, flags).search(string)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000138
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000139def sub(pattern, repl, string, count=0):
Fredrik Lundh770617b2001-01-14 15:06:11 +0000140 """Return the string obtained by replacing the leftmost
141 non-overlapping occurrences of the pattern in string by the
142 replacement repl"""
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000143 return _compile(pattern, 0).sub(repl, string, count)
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000144
145def subn(pattern, repl, string, count=0):
Fredrik Lundh770617b2001-01-14 15:06:11 +0000146 """Return a 2-tuple containing (new_string, number).
147 new_string is the string obtained by replacing the leftmost
148 non-overlapping occurrences of the pattern in the source
149 string by the replacement repl. number is the number of
150 substitutions that were made."""
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000151 return _compile(pattern, 0).subn(repl, string, count)
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000152
153def split(pattern, string, maxsplit=0):
Fredrik Lundh770617b2001-01-14 15:06:11 +0000154 """Split the source string by the occurrences of the pattern,
155 returning a list containing the resulting substrings."""
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000156 return _compile(pattern, 0).split(string, maxsplit)
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000157
Fredrik Lundhe06cbb82001-07-06 20:56:10 +0000158def findall(pattern, string):
Fredrik Lundh770617b2001-01-14 15:06:11 +0000159 """Return a list of all non-overlapping matches in the string.
160
161 If one or more groups are present in the pattern, return a
162 list of groups; this will be a list of tuples if the pattern
163 has more than one group.
164
165 Empty matches are included in the result."""
Fredrik Lundhe06cbb82001-07-06 20:56:10 +0000166 return _compile(pattern, 0).findall(string)
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000167
Fredrik Lundh703ce812001-10-24 22:16:30 +0000168if sys.hexversion >= 0x02020000:
Guido van Rossum0d976552002-10-14 12:22:17 +0000169 __all__.append("finditer")
Fredrik Lundh703ce812001-10-24 22:16:30 +0000170 def finditer(pattern, string):
Fredrik Lundhb7747e22001-10-28 20:15:40 +0000171 """Return an iterator over all non-overlapping matches in the
172 string. For each match, the iterator returns a match object.
Fredrik Lundh703ce812001-10-24 22:16:30 +0000173
174 Empty matches are included in the result."""
175 return _compile(pattern, 0).finditer(string)
176
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000177def compile(pattern, flags=0):
Fredrik Lundh770617b2001-01-14 15:06:11 +0000178 "Compile a regular expression pattern, returning a pattern object."
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000179 return _compile(pattern, flags)
180
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000181def purge():
Fredrik Lundh770617b2001-01-14 15:06:11 +0000182 "Clear the regular expression cache"
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000183 _cache.clear()
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000184 _cache_repl.clear()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000185
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000186def template(pattern, flags=0):
Fredrik Lundh770617b2001-01-14 15:06:11 +0000187 "Compile a template pattern, returning a pattern object"
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000188 return _compile(pattern, flags|T)
189
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000190def escape(pattern):
Fredrik Lundh770617b2001-01-14 15:06:11 +0000191 "Escape all non-alphanumeric characters in pattern."
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000192 s = list(pattern)
193 for i in range(len(pattern)):
194 c = pattern[i]
195 if not ("a" <= c <= "z" or "A" <= c <= "Z" or "0" <= c <= "9"):
196 if c == "\000":
197 s[i] = "\\000"
198 else:
199 s[i] = "\\" + c
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000200 return _join(s, pattern)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000201
202# --------------------------------------------------------------------
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000203# internals
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000204
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000205_cache = {}
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000206_cache_repl = {}
207
Fredrik Lundh397a6542001-10-18 19:30:16 +0000208_pattern_type = type(sre_compile.compile("", 0))
209
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000210_MAXCACHE = 100
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000211
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000212def _join(seq, sep):
213 # internal: join into string having the same type as sep
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000214 return string.join(seq, sep[:0])
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000215
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000216def _compile(*key):
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000217 # internal: compile pattern
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000218 p = _cache.get(key)
219 if p is not None:
220 return p
221 pattern, flags = key
Just van Rossum12723ba2003-07-02 20:03:04 +0000222 if isinstance(pattern, _pattern_type):
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000223 return pattern
Just van Rossum74902502003-07-02 21:37:16 +0000224 if not sre_compile.isstring(pattern):
Fredrik Lundh397a6542001-10-18 19:30:16 +0000225 raise TypeError, "first argument must be string or compiled pattern"
Fredrik Lundhe1869832000-08-01 22:47:49 +0000226 try:
227 p = sre_compile.compile(pattern, flags)
228 except error, v:
229 raise error, v # invalid expression
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000230 if len(_cache) >= _MAXCACHE:
231 _cache.clear()
232 _cache[key] = p
233 return p
234
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000235def _compile_repl(*key):
236 # internal: compile replacement pattern
237 p = _cache_repl.get(key)
238 if p is not None:
239 return p
240 repl, pattern = key
241 try:
242 p = sre_parse.parse_template(repl, pattern)
243 except error, v:
244 raise error, v # invalid expression
245 if len(_cache_repl) >= _MAXCACHE:
246 _cache_repl.clear()
247 _cache_repl[key] = p
248 return p
249
Fredrik Lundh5644b7f2000-09-21 17:03:25 +0000250def _expand(pattern, match, template):
251 # internal: match.expand implementation hook
252 template = sre_parse.parse_template(template, pattern)
253 return sre_parse.expand_template(template, match)
254
Fredrik Lundhbec95b92001-10-21 16:47:57 +0000255def _subx(pattern, template):
256 # internal: pattern.sub/subn implementation helper
Fredrik Lundhdac58492001-10-21 21:48:30 +0000257 template = _compile_repl(template, pattern)
258 if not template[0] and len(template[1]) == 1:
Fredrik Lundhbec95b92001-10-21 16:47:57 +0000259 # literal replacement
Fredrik Lundhdac58492001-10-21 21:48:30 +0000260 return template[1][0]
261 def filter(match, template=template):
262 return sre_parse.expand_template(template, match)
263 return filter
Fredrik Lundh0640e112000-06-30 13:55:15 +0000264
265# register myself for pickling
266
267import copy_reg
268
269def _pickle(p):
270 return _compile, (p.pattern, p.flags)
271
Fredrik Lundh397a6542001-10-18 19:30:16 +0000272copy_reg.pickle(_pattern_type, _pickle, _compile)
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000273
274# --------------------------------------------------------------------
275# experimental stuff (see python-dev discussions for details)
276
277class Scanner:
Fredrik Lundh1296a8d2001-10-21 18:04:11 +0000278 def __init__(self, lexicon, flags=0):
Fredrik Lundh29c4ba92000-08-01 18:20:07 +0000279 from sre_constants import BRANCH, SUBPATTERN
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000280 self.lexicon = lexicon
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000281 # combine phrases into a compound pattern
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000282 p = []
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000283 s = sre_parse.Pattern()
Fredrik Lundh1296a8d2001-10-21 18:04:11 +0000284 s.flags = flags
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000285 for phrase, action in lexicon:
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000286 p.append(sre_parse.SubPattern(s, [
Fredrik Lundh1296a8d2001-10-21 18:04:11 +0000287 (SUBPATTERN, (len(p)+1, sre_parse.parse(phrase, flags))),
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000288 ]))
289 p = sre_parse.SubPattern(s, [(BRANCH, (None, p))])
290 s.groups = len(p)
291 self.scanner = sre_compile.compile(p)
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000292 def scan(self, string):
293 result = []
294 append = result.append
Fredrik Lundh1296a8d2001-10-21 18:04:11 +0000295 match = self.scanner.scanner(string).match
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000296 i = 0
297 while 1:
Fredrik Lundh1296a8d2001-10-21 18:04:11 +0000298 m = match()
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000299 if not m:
300 break
301 j = m.end()
302 if i == j:
303 break
Fredrik Lundh1296a8d2001-10-21 18:04:11 +0000304 action = self.lexicon[m.lastindex-1][1]
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000305 if callable(action):
Fredrik Lundh770617b2001-01-14 15:06:11 +0000306 self.match = m
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000307 action = action(self, m.group())
308 if action is not None:
309 append(action)
310 i = j
311 return result, string[i:]