Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 1 | # |
| 2 | # Secret Labs' Regular Expression Engine |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 3 | # |
| 4 | # re-compatible interface for the sre matching engine |
| 5 | # |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 6 | # Copyright (c) 1998-2001 by Secret Labs AB. All rights reserved. |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 7 | # |
Fredrik Lundh | 29c4ba9 | 2000-08-01 18:20:07 +0000 | [diff] [blame] | 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 | # |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 12 | # Portions of this engine have been developed in cooperation with |
Fredrik Lundh | 29c4ba9 | 2000-08-01 18:20:07 +0000 | [diff] [blame] | 13 | # CNRI. Hewlett-Packard provided funding for 1.6 integration and |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 14 | # other compatibility work. |
| 15 | # |
| 16 | |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 17 | import sre_compile |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 18 | import sre_parse |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 19 | |
Skip Montanaro | 0de6580 | 2001-02-15 22:15:14 +0000 | [diff] [blame^] | 20 | __all__ = ["match","search","sub","subn","split","findall","compile", |
| 21 | "purge","template","escape","I","L","M","S","X","U","IGNORECASE", |
| 22 | "LOCALE","MULTILINE","DOTALL","VERBOSE","UNICODE","error"] |
| 23 | |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 24 | # flags |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 25 | I = IGNORECASE = sre_compile.SRE_FLAG_IGNORECASE # ignore case |
| 26 | L = LOCALE = sre_compile.SRE_FLAG_LOCALE # assume current 8-bit locale |
| 27 | U = UNICODE = sre_compile.SRE_FLAG_UNICODE # assume unicode locale |
| 28 | M = MULTILINE = sre_compile.SRE_FLAG_MULTILINE # make anchors look for newline |
| 29 | S = DOTALL = sre_compile.SRE_FLAG_DOTALL # make dot match newline |
| 30 | X = VERBOSE = sre_compile.SRE_FLAG_VERBOSE # ignore whitespace and comments |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 31 | |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 32 | # sre extensions (experimental, don't rely on these) |
| 33 | T = TEMPLATE = sre_compile.SRE_FLAG_TEMPLATE # disable backtracking |
| 34 | DEBUG = sre_compile.SRE_FLAG_DEBUG # dump pattern after compilation |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 35 | |
| 36 | # sre exception |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame] | 37 | error = sre_compile.error |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 38 | |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 39 | # -------------------------------------------------------------------- |
| 40 | # public interface |
| 41 | |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 42 | def match(pattern, string, flags=0): |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 43 | """Try to apply the pattern at the start of the string, returning |
| 44 | a match object, or None if no match was found.""" |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 45 | return _compile(pattern, flags).match(string) |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 46 | |
| 47 | def search(pattern, string, flags=0): |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 48 | """Scan through string looking for a match to the pattern, returning |
| 49 | a match object, or None if no match was found.""" |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 50 | return _compile(pattern, flags).search(string) |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 51 | |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 52 | def sub(pattern, repl, string, count=0): |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 53 | """Return the string obtained by replacing the leftmost |
| 54 | non-overlapping occurrences of the pattern in string by the |
| 55 | replacement repl""" |
Fredrik Lundh | 7898c3e | 2000-08-07 20:59:04 +0000 | [diff] [blame] | 56 | return _compile(pattern, 0).sub(repl, string, count) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 57 | |
| 58 | def subn(pattern, repl, string, count=0): |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 59 | """Return a 2-tuple containing (new_string, number). |
| 60 | new_string is the string obtained by replacing the leftmost |
| 61 | non-overlapping occurrences of the pattern in the source |
| 62 | string by the replacement repl. number is the number of |
| 63 | substitutions that were made.""" |
Fredrik Lundh | 7898c3e | 2000-08-07 20:59:04 +0000 | [diff] [blame] | 64 | return _compile(pattern, 0).subn(repl, string, count) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 65 | |
| 66 | def split(pattern, string, maxsplit=0): |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 67 | """Split the source string by the occurrences of the pattern, |
| 68 | returning a list containing the resulting substrings.""" |
Fredrik Lundh | 7898c3e | 2000-08-07 20:59:04 +0000 | [diff] [blame] | 69 | return _compile(pattern, 0).split(string, maxsplit) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 70 | |
| 71 | def findall(pattern, string, maxsplit=0): |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 72 | """Return a list of all non-overlapping matches in the string. |
| 73 | |
| 74 | If one or more groups are present in the pattern, return a |
| 75 | list of groups; this will be a list of tuples if the pattern |
| 76 | has more than one group. |
| 77 | |
| 78 | Empty matches are included in the result.""" |
Fredrik Lundh | 7898c3e | 2000-08-07 20:59:04 +0000 | [diff] [blame] | 79 | return _compile(pattern, 0).findall(string, maxsplit) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 80 | |
| 81 | def compile(pattern, flags=0): |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 82 | "Compile a regular expression pattern, returning a pattern object." |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 83 | return _compile(pattern, flags) |
| 84 | |
Fredrik Lundh | 8a3ebf8 | 2000-07-23 21:46:17 +0000 | [diff] [blame] | 85 | def purge(): |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 86 | "Clear the regular expression cache" |
Fredrik Lundh | 8a3ebf8 | 2000-07-23 21:46:17 +0000 | [diff] [blame] | 87 | _cache.clear() |
| 88 | |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 89 | def template(pattern, flags=0): |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 90 | "Compile a template pattern, returning a pattern object" |
| 91 | |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 92 | return _compile(pattern, flags|T) |
| 93 | |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 94 | def escape(pattern): |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 95 | "Escape all non-alphanumeric characters in pattern." |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 96 | s = list(pattern) |
| 97 | for i in range(len(pattern)): |
| 98 | c = pattern[i] |
| 99 | if not ("a" <= c <= "z" or "A" <= c <= "Z" or "0" <= c <= "9"): |
| 100 | if c == "\000": |
| 101 | s[i] = "\\000" |
| 102 | else: |
| 103 | s[i] = "\\" + c |
Fredrik Lundh | 8a3ebf8 | 2000-07-23 21:46:17 +0000 | [diff] [blame] | 104 | return _join(s, pattern) |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 105 | |
| 106 | # -------------------------------------------------------------------- |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 107 | # internals |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 108 | |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 109 | _cache = {} |
| 110 | _MAXCACHE = 100 |
Guido van Rossum | 7627c0d | 2000-03-31 14:58:54 +0000 | [diff] [blame] | 111 | |
Fredrik Lundh | 8a3ebf8 | 2000-07-23 21:46:17 +0000 | [diff] [blame] | 112 | def _join(seq, sep): |
| 113 | # internal: join into string having the same type as sep |
Eric S. Raymond | b08b2d3 | 2001-02-09 11:10:16 +0000 | [diff] [blame] | 114 | return sep[:0].join(seq) |
Fredrik Lundh | 8a3ebf8 | 2000-07-23 21:46:17 +0000 | [diff] [blame] | 115 | |
Fredrik Lundh | 7898c3e | 2000-08-07 20:59:04 +0000 | [diff] [blame] | 116 | def _compile(*key): |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 117 | # internal: compile pattern |
Fredrik Lundh | 7898c3e | 2000-08-07 20:59:04 +0000 | [diff] [blame] | 118 | p = _cache.get(key) |
| 119 | if p is not None: |
| 120 | return p |
| 121 | pattern, flags = key |
| 122 | if type(pattern) not in sre_compile.STRING_TYPES: |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 123 | return pattern |
Fredrik Lundh | e186983 | 2000-08-01 22:47:49 +0000 | [diff] [blame] | 124 | try: |
| 125 | p = sre_compile.compile(pattern, flags) |
| 126 | except error, v: |
| 127 | raise error, v # invalid expression |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 128 | if len(_cache) >= _MAXCACHE: |
| 129 | _cache.clear() |
| 130 | _cache[key] = p |
| 131 | return p |
| 132 | |
Fredrik Lundh | 5644b7f | 2000-09-21 17:03:25 +0000 | [diff] [blame] | 133 | def _expand(pattern, match, template): |
| 134 | # internal: match.expand implementation hook |
| 135 | template = sre_parse.parse_template(template, pattern) |
| 136 | return sre_parse.expand_template(template, match) |
| 137 | |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 138 | def _sub(pattern, template, string, count=0): |
| 139 | # internal: pattern.sub implementation hook |
| 140 | return _subn(pattern, template, string, count)[0] |
| 141 | |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 142 | def _subn(pattern, template, string, count=0): |
| 143 | # internal: pattern.subn implementation hook |
| 144 | if callable(template): |
Andrew M. Kuchling | e8d52af | 2000-06-18 20:27:10 +0000 | [diff] [blame] | 145 | filter = template |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 146 | else: |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 147 | template = sre_parse.parse_template(template, pattern) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 148 | def filter(match, template=template): |
Fredrik Lundh | 436c3d58 | 2000-06-29 08:58:44 +0000 | [diff] [blame] | 149 | return sre_parse.expand_template(template, match) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 150 | n = i = 0 |
| 151 | s = [] |
| 152 | append = s.append |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame] | 153 | c = pattern.scanner(string) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 154 | while not count or n < count: |
| 155 | m = c.search() |
| 156 | if not m: |
| 157 | break |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 158 | b, e = m.span() |
Fredrik Lundh | 01016fe | 2000-06-30 00:27:46 +0000 | [diff] [blame] | 159 | if i < b: |
| 160 | append(string[i:b]) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 161 | append(filter(m)) |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 162 | i = e |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 163 | n = n + 1 |
Fredrik Lundh | 01016fe | 2000-06-30 00:27:46 +0000 | [diff] [blame] | 164 | append(string[i:]) |
Fredrik Lundh | 8a3ebf8 | 2000-07-23 21:46:17 +0000 | [diff] [blame] | 165 | return _join(s, string[:0]), n |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 166 | |
| 167 | def _split(pattern, string, maxsplit=0): |
| 168 | # internal: pattern.split implementation hook |
| 169 | n = i = 0 |
| 170 | s = [] |
| 171 | append = s.append |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame] | 172 | extend = s.extend |
| 173 | c = pattern.scanner(string) |
Fredrik Lundh | 01016fe | 2000-06-30 00:27:46 +0000 | [diff] [blame] | 174 | g = pattern.groups |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 175 | while not maxsplit or n < maxsplit: |
| 176 | m = c.search() |
| 177 | if not m: |
| 178 | break |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 179 | b, e = m.span() |
| 180 | if b == e: |
| 181 | if i >= len(string): |
| 182 | break |
| 183 | continue |
Fredrik Lundh | be2211e | 2000-06-29 16:57:40 +0000 | [diff] [blame] | 184 | append(string[i:b]) |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 185 | if g and b != e: |
Fredrik Lundh | 1c5aa69 | 2001-01-16 07:37:30 +0000 | [diff] [blame] | 186 | extend(list(m.groups())) |
Fredrik Lundh | 90a0791 | 2000-06-30 07:50:59 +0000 | [diff] [blame] | 187 | i = e |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 188 | n = n + 1 |
Fredrik Lundh | 8094611 | 2000-06-29 18:03:25 +0000 | [diff] [blame] | 189 | append(string[i:]) |
Jeremy Hylton | b1aa195 | 2000-06-01 17:39:12 +0000 | [diff] [blame] | 190 | return s |
Fredrik Lundh | 0640e11 | 2000-06-30 13:55:15 +0000 | [diff] [blame] | 191 | |
| 192 | # register myself for pickling |
| 193 | |
| 194 | import copy_reg |
| 195 | |
| 196 | def _pickle(p): |
| 197 | return _compile, (p.pattern, p.flags) |
| 198 | |
Fredrik Lundh | 7898c3e | 2000-08-07 20:59:04 +0000 | [diff] [blame] | 199 | copy_reg.pickle(type(_compile("", 0)), _pickle, _compile) |
Fredrik Lundh | 7cafe4d | 2000-07-02 17:33:27 +0000 | [diff] [blame] | 200 | |
| 201 | # -------------------------------------------------------------------- |
| 202 | # experimental stuff (see python-dev discussions for details) |
| 203 | |
| 204 | class Scanner: |
| 205 | def __init__(self, lexicon): |
Fredrik Lundh | 29c4ba9 | 2000-08-01 18:20:07 +0000 | [diff] [blame] | 206 | from sre_constants import BRANCH, SUBPATTERN |
Fredrik Lundh | 7cafe4d | 2000-07-02 17:33:27 +0000 | [diff] [blame] | 207 | self.lexicon = lexicon |
Fredrik Lundh | 8a3ebf8 | 2000-07-23 21:46:17 +0000 | [diff] [blame] | 208 | # combine phrases into a compound pattern |
Fredrik Lundh | 7cafe4d | 2000-07-02 17:33:27 +0000 | [diff] [blame] | 209 | p = [] |
Fredrik Lundh | 8a3ebf8 | 2000-07-23 21:46:17 +0000 | [diff] [blame] | 210 | s = sre_parse.Pattern() |
Fredrik Lundh | 7cafe4d | 2000-07-02 17:33:27 +0000 | [diff] [blame] | 211 | for phrase, action in lexicon: |
Fredrik Lundh | 8a3ebf8 | 2000-07-23 21:46:17 +0000 | [diff] [blame] | 212 | p.append(sre_parse.SubPattern(s, [ |
Fredrik Lundh | 29c4ba9 | 2000-08-01 18:20:07 +0000 | [diff] [blame] | 213 | (SUBPATTERN, (len(p), sre_parse.parse(phrase))), |
Fredrik Lundh | 8a3ebf8 | 2000-07-23 21:46:17 +0000 | [diff] [blame] | 214 | ])) |
| 215 | p = sre_parse.SubPattern(s, [(BRANCH, (None, p))]) |
| 216 | s.groups = len(p) |
| 217 | self.scanner = sre_compile.compile(p) |
Fredrik Lundh | 7cafe4d | 2000-07-02 17:33:27 +0000 | [diff] [blame] | 218 | def scan(self, string): |
| 219 | result = [] |
| 220 | append = result.append |
| 221 | match = self.scanner.match |
| 222 | i = 0 |
| 223 | while 1: |
| 224 | m = match(string, i) |
| 225 | if not m: |
| 226 | break |
| 227 | j = m.end() |
| 228 | if i == j: |
| 229 | break |
Fredrik Lundh | 019bcb5 | 2000-07-02 22:59:57 +0000 | [diff] [blame] | 230 | action = self.lexicon[m.lastindex][1] |
Fredrik Lundh | 7cafe4d | 2000-07-02 17:33:27 +0000 | [diff] [blame] | 231 | if callable(action): |
Fredrik Lundh | 770617b | 2001-01-14 15:06:11 +0000 | [diff] [blame] | 232 | self.match = m |
Fredrik Lundh | 7cafe4d | 2000-07-02 17:33:27 +0000 | [diff] [blame] | 233 | action = action(self, m.group()) |
| 234 | if action is not None: |
| 235 | append(action) |
| 236 | i = j |
| 237 | return result, string[i:] |