blob: 1b52967a586696f8880a8a334b9334f4a57b7861 [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#
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +00004# convert re-style regular expression to sre pattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +00005#
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# See the sre.py file for information on usage and redistribution.
Guido van Rossum7627c0d2000-03-31 14:58:54 +00009#
10
Fred Drakeb8f22742001-09-04 19:10:20 +000011"""Internal support module for sre"""
12
Fredrik Lundh470ea5a2001-01-14 21:00:44 +000013# XXX: show string offset and offending character for all errors
14
Fredrik Lundhf2989b22001-02-18 12:05:16 +000015# this module works under 1.5.2 and later. don't use string methods
16import string, sys
Guido van Rossum7627c0d2000-03-31 14:58:54 +000017
18from sre_constants import *
19
20SPECIAL_CHARS = ".\\[{()*+?^$|"
Fredrik Lundh143328b2000-09-02 11:03:34 +000021REPEAT_CHARS = "*+?{"
Guido van Rossum7627c0d2000-03-31 14:58:54 +000022
Tim Peters17289422000-09-02 07:44:32 +000023DIGITS = tuple("0123456789")
Guido van Rossumb81e70e2000-04-10 17:10:48 +000024
Fredrik Lundh75f2d672000-06-29 11:34:28 +000025OCTDIGITS = tuple("01234567")
26HEXDIGITS = tuple("0123456789abcdefABCDEF")
Guido van Rossum7627c0d2000-03-31 14:58:54 +000027
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +000028WHITESPACE = tuple(" \t\n\r\v\f")
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +000029
Guido van Rossum7627c0d2000-03-31 14:58:54 +000030ESCAPES = {
Fredrik Lundhf2989b22001-02-18 12:05:16 +000031 r"\a": (LITERAL, ord("\a")),
32 r"\b": (LITERAL, ord("\b")),
33 r"\f": (LITERAL, ord("\f")),
34 r"\n": (LITERAL, ord("\n")),
35 r"\r": (LITERAL, ord("\r")),
36 r"\t": (LITERAL, ord("\t")),
37 r"\v": (LITERAL, ord("\v")),
Fredrik Lundh0640e112000-06-30 13:55:15 +000038 r"\\": (LITERAL, ord("\\"))
Guido van Rossum7627c0d2000-03-31 14:58:54 +000039}
40
41CATEGORIES = {
Fredrik Lundh770617b2001-01-14 15:06:11 +000042 r"\A": (AT, AT_BEGINNING_STRING), # start of string
Fredrik Lundh01016fe2000-06-30 00:27:46 +000043 r"\b": (AT, AT_BOUNDARY),
44 r"\B": (AT, AT_NON_BOUNDARY),
45 r"\d": (IN, [(CATEGORY, CATEGORY_DIGIT)]),
46 r"\D": (IN, [(CATEGORY, CATEGORY_NOT_DIGIT)]),
47 r"\s": (IN, [(CATEGORY, CATEGORY_SPACE)]),
48 r"\S": (IN, [(CATEGORY, CATEGORY_NOT_SPACE)]),
49 r"\w": (IN, [(CATEGORY, CATEGORY_WORD)]),
50 r"\W": (IN, [(CATEGORY, CATEGORY_NOT_WORD)]),
Fredrik Lundh770617b2001-01-14 15:06:11 +000051 r"\Z": (AT, AT_END_STRING), # end of string
Guido van Rossum7627c0d2000-03-31 14:58:54 +000052}
53
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +000054FLAGS = {
Fredrik Lundh436c3d52000-06-29 08:58:44 +000055 # standard flags
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +000056 "i": SRE_FLAG_IGNORECASE,
57 "L": SRE_FLAG_LOCALE,
58 "m": SRE_FLAG_MULTILINE,
59 "s": SRE_FLAG_DOTALL,
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +000060 "x": SRE_FLAG_VERBOSE,
Fredrik Lundh436c3d52000-06-29 08:58:44 +000061 # extensions
62 "t": SRE_FLAG_TEMPLATE,
63 "u": SRE_FLAG_UNICODE,
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +000064}
65
Fredrik Lundhf2989b22001-02-18 12:05:16 +000066# figure out best way to convert hex/octal numbers to integers
67try:
68 int("10", 8)
69 atoi = int # 2.0 and later
70except TypeError:
71 atoi = string.atoi # 1.5.2
72
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +000073class Pattern:
74 # master pattern object. keeps track of global attributes
Guido van Rossum7627c0d2000-03-31 14:58:54 +000075 def __init__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +000076 self.flags = 0
Fredrik Lundhebc37b22000-10-28 19:30:41 +000077 self.open = []
Fredrik Lundh90a07912000-06-30 07:50:59 +000078 self.groups = 1
79 self.groupdict = {}
Fredrik Lundhebc37b22000-10-28 19:30:41 +000080 def opengroup(self, name=None):
Fredrik Lundh90a07912000-06-30 07:50:59 +000081 gid = self.groups
82 self.groups = gid + 1
Raymond Hettingerf13eb552002-06-02 00:40:05 +000083 if name is not None:
Tim Peters75335872001-11-03 19:35:43 +000084 ogid = self.groupdict.get(name, None)
85 if ogid is not None:
Fredrik Lundh82b23072001-12-09 16:13:15 +000086 raise error, ("redefinition of group name %s as group %d; "
87 "was group %d" % (repr(name), gid, ogid))
Fredrik Lundh90a07912000-06-30 07:50:59 +000088 self.groupdict[name] = gid
Fredrik Lundhebc37b22000-10-28 19:30:41 +000089 self.open.append(gid)
Fredrik Lundh90a07912000-06-30 07:50:59 +000090 return gid
Fredrik Lundhebc37b22000-10-28 19:30:41 +000091 def closegroup(self, gid):
92 self.open.remove(gid)
93 def checkgroup(self, gid):
94 return gid < self.groups and gid not in self.open
Guido van Rossum7627c0d2000-03-31 14:58:54 +000095
96class SubPattern:
97 # a subpattern, in intermediate form
98 def __init__(self, pattern, data=None):
Fredrik Lundh90a07912000-06-30 07:50:59 +000099 self.pattern = pattern
Raymond Hettingerf13eb552002-06-02 00:40:05 +0000100 if data is None:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000101 data = []
102 self.data = data
103 self.width = None
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000104 def dump(self, level=0):
105 nl = 1
106 for op, av in self.data:
107 print level*" " + op,; nl = 0
108 if op == "in":
109 # member sublanguage
110 print; nl = 1
111 for op, a in av:
112 print (level+1)*" " + op, a
113 elif op == "branch":
114 print; nl = 1
115 i = 0
116 for a in av[1]:
117 if i > 0:
118 print level*" " + "or"
119 a.dump(level+1); nl = 1
120 i = i + 1
121 elif type(av) in (type(()), type([])):
122 for a in av:
123 if isinstance(a, SubPattern):
124 if not nl: print
125 a.dump(level+1); nl = 1
126 else:
127 print a, ; nl = 0
128 else:
129 print av, ; nl = 0
130 if not nl: print
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000131 def __repr__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000132 return repr(self.data)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000133 def __len__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000134 return len(self.data)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000135 def __delitem__(self, index):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000136 del self.data[index]
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000137 def __getitem__(self, index):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000138 return self.data[index]
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000139 def __setitem__(self, index, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000140 self.data[index] = code
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000141 def __getslice__(self, start, stop):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000142 return SubPattern(self.pattern, self.data[start:stop])
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000143 def insert(self, index, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000144 self.data.insert(index, code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000145 def append(self, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000146 self.data.append(code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000147 def getwidth(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000148 # determine the width (min, max) for this subpattern
149 if self.width:
150 return self.width
151 lo = hi = 0L
152 for op, av in self.data:
153 if op is BRANCH:
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000154 i = sys.maxint
155 j = 0
Fredrik Lundh90a07912000-06-30 07:50:59 +0000156 for av in av[1]:
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000157 l, h = av.getwidth()
158 i = min(i, l)
Fredrik Lundhe1869832000-08-01 22:47:49 +0000159 j = max(j, h)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000160 lo = lo + i
161 hi = hi + j
162 elif op is CALL:
163 i, j = av.getwidth()
164 lo = lo + i
165 hi = hi + j
166 elif op is SUBPATTERN:
167 i, j = av[1].getwidth()
168 lo = lo + i
169 hi = hi + j
170 elif op in (MIN_REPEAT, MAX_REPEAT):
171 i, j = av[2].getwidth()
172 lo = lo + long(i) * av[0]
173 hi = hi + long(j) * av[1]
174 elif op in (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY):
175 lo = lo + 1
176 hi = hi + 1
177 elif op == SUCCESS:
178 break
179 self.width = int(min(lo, sys.maxint)), int(min(hi, sys.maxint))
180 return self.width
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000181
182class Tokenizer:
183 def __init__(self, string):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000184 self.string = string
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000185 self.index = 0
186 self.__next()
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000187 def __next(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000188 if self.index >= len(self.string):
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000189 self.next = None
190 return
Fredrik Lundh90a07912000-06-30 07:50:59 +0000191 char = self.string[self.index]
192 if char[0] == "\\":
193 try:
194 c = self.string[self.index + 1]
195 except IndexError:
Fredrik Lundh8a0232d2001-11-02 13:59:51 +0000196 raise error, "bogus escape (end of line)"
Fredrik Lundh90a07912000-06-30 07:50:59 +0000197 char = char + c
198 self.index = self.index + len(char)
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000199 self.next = char
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000200 def match(self, char, skip=1):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000201 if char == self.next:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000202 if skip:
203 self.__next()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000204 return 1
205 return 0
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000206 def get(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000207 this = self.next
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000208 self.__next()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000209 return this
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000210 def tell(self):
211 return self.index, self.next
212 def seek(self, index):
213 self.index, self.next = index
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000214
Fredrik Lundh4781b072000-06-29 12:38:45 +0000215def isident(char):
216 return "a" <= char <= "z" or "A" <= char <= "Z" or char == "_"
217
218def isdigit(char):
219 return "0" <= char <= "9"
220
221def isname(name):
222 # check that group name is a valid string
Fredrik Lundh4781b072000-06-29 12:38:45 +0000223 if not isident(name[0]):
Guido van Rossum8ca162f2002-04-07 06:36:23 +0000224 return False
Fredrik Lundh4781b072000-06-29 12:38:45 +0000225 for char in name:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000226 if not isident(char) and not isdigit(char):
Guido van Rossum8ca162f2002-04-07 06:36:23 +0000227 return False
228 return True
Fredrik Lundh4781b072000-06-29 12:38:45 +0000229
Fredrik Lundh01016fe2000-06-30 00:27:46 +0000230def _group(escape, groups):
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000231 # check if the escape string represents a valid group
232 try:
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000233 gid = atoi(escape[1:])
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000234 if gid and gid < groups:
235 return gid
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000236 except ValueError:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000237 pass
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000238 return None # not a valid group
239
240def _class_escape(source, escape):
241 # handle escape code inside character class
242 code = ESCAPES.get(escape)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000243 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000244 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000245 code = CATEGORIES.get(escape)
246 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000247 return code
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000248 try:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000249 if escape[1:2] == "x":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000250 # hexadecimal escape (exactly two digits)
251 while source.next in HEXDIGITS and len(escape) < 4:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000252 escape = escape + source.get()
253 escape = escape[2:]
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000254 if len(escape) != 2:
255 raise error, "bogus escape: %s" % repr("\\" + escape)
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000256 return LITERAL, atoi(escape, 16) & 0xff
Fredrik Lundh90a07912000-06-30 07:50:59 +0000257 elif str(escape[1:2]) in OCTDIGITS:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000258 # octal escape (up to three digits)
259 while source.next in OCTDIGITS and len(escape) < 5:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000260 escape = escape + source.get()
261 escape = escape[1:]
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000262 return LITERAL, atoi(escape, 8) & 0xff
Fredrik Lundh90a07912000-06-30 07:50:59 +0000263 if len(escape) == 2:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000264 return LITERAL, ord(escape[1])
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000265 except ValueError:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000266 pass
Fredrik Lundh436c3d52000-06-29 08:58:44 +0000267 raise error, "bogus escape: %s" % repr(escape)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000268
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000269def _escape(source, escape, state):
270 # handle escape code in expression
271 code = CATEGORIES.get(escape)
272 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000273 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000274 code = ESCAPES.get(escape)
275 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000276 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000277 try:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000278 if escape[1:2] == "x":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000279 # hexadecimal escape
280 while source.next in HEXDIGITS and len(escape) < 4:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000281 escape = escape + source.get()
Fredrik Lundh143328b2000-09-02 11:03:34 +0000282 if len(escape) != 4:
283 raise ValueError
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000284 return LITERAL, atoi(escape[2:], 16) & 0xff
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000285 elif escape[1:2] == "0":
286 # octal escape
Fredrik Lundh143328b2000-09-02 11:03:34 +0000287 while source.next in OCTDIGITS and len(escape) < 4:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000288 escape = escape + source.get()
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000289 return LITERAL, atoi(escape[1:], 8) & 0xff
Fredrik Lundh90a07912000-06-30 07:50:59 +0000290 elif escape[1:2] in DIGITS:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000291 # octal escape *or* decimal group reference (sigh)
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000292 if source.next in DIGITS:
293 escape = escape + source.get()
Fredrik Lundh143328b2000-09-02 11:03:34 +0000294 if (escape[1] in OCTDIGITS and escape[2] in OCTDIGITS and
295 source.next in OCTDIGITS):
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000296 # got three octal digits; this is an octal escape
Fredrik Lundh90a07912000-06-30 07:50:59 +0000297 escape = escape + source.get()
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000298 return LITERAL, atoi(escape[1:], 8) & 0xff
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000299 # got at least one decimal digit; this is a group reference
300 group = _group(escape, state.groups)
301 if group:
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000302 if not state.checkgroup(group):
303 raise error, "cannot refer to open group"
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000304 return GROUPREF, group
Fredrik Lundh143328b2000-09-02 11:03:34 +0000305 raise ValueError
Fredrik Lundh90a07912000-06-30 07:50:59 +0000306 if len(escape) == 2:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000307 return LITERAL, ord(escape[1])
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000308 except ValueError:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000309 pass
Fredrik Lundh436c3d52000-06-29 08:58:44 +0000310 raise error, "bogus escape: %s" % repr(escape)
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000311
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000312def _parse_sub(source, state, nested=1):
313 # parse an alternation: a|b|c
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000314
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000315 items = []
316 while 1:
317 items.append(_parse(source, state))
318 if source.match("|"):
319 continue
320 if not nested:
321 break
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000322 if not source.next or source.match(")", 0):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000323 break
324 else:
325 raise error, "pattern not properly closed"
326
327 if len(items) == 1:
328 return items[0]
329
330 subpattern = SubPattern(state)
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000331
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000332 # check if all items share a common prefix
333 while 1:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000334 prefix = None
335 for item in items:
336 if not item:
337 break
338 if prefix is None:
339 prefix = item[0]
340 elif item[0] != prefix:
341 break
342 else:
343 # all subitems start with a common "prefix".
344 # move it out of the branch
345 for item in items:
346 del item[0]
347 subpattern.append(prefix)
348 continue # check next one
349 break
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000350
351 # check if the branch can be replaced by a character set
352 for item in items:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000353 if len(item) != 1 or item[0][0] != LITERAL:
354 break
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000355 else:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000356 # we can store this as a character set instead of a
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000357 # branch (the compiler may optimize this even more)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000358 set = []
359 for item in items:
360 set.append(item[0])
361 subpattern.append((IN, set))
362 return subpattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000363
364 subpattern.append((BRANCH, (None, items)))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000365 return subpattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000366
Fredrik Lundh55a4f4a2000-06-30 22:37:31 +0000367def _parse(source, state):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000368 # parse a simple pattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000369
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000370 subpattern = SubPattern(state)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000371
372 while 1:
373
Fredrik Lundh90a07912000-06-30 07:50:59 +0000374 if source.next in ("|", ")"):
375 break # end of subpattern
376 this = source.get()
377 if this is None:
378 break # end of pattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000379
Fredrik Lundh90a07912000-06-30 07:50:59 +0000380 if state.flags & SRE_FLAG_VERBOSE:
381 # skip whitespace and comments
382 if this in WHITESPACE:
383 continue
384 if this == "#":
385 while 1:
386 this = source.get()
387 if this in (None, "\n"):
388 break
389 continue
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000390
Fredrik Lundh90a07912000-06-30 07:50:59 +0000391 if this and this[0] not in SPECIAL_CHARS:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000392 subpattern.append((LITERAL, ord(this)))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000393
Fredrik Lundh90a07912000-06-30 07:50:59 +0000394 elif this == "[":
395 # character set
396 set = []
397## if source.match(":"):
398## pass # handle character classes
399 if source.match("^"):
400 set.append((NEGATE, None))
401 # check remaining characters
402 start = set[:]
403 while 1:
404 this = source.get()
405 if this == "]" and set != start:
406 break
407 elif this and this[0] == "\\":
408 code1 = _class_escape(source, this)
409 elif this:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000410 code1 = LITERAL, ord(this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000411 else:
412 raise error, "unexpected end of regular expression"
413 if source.match("-"):
414 # potential range
415 this = source.get()
416 if this == "]":
Fredrik Lundh025468d2000-10-07 10:16:19 +0000417 if code1[0] is IN:
418 code1 = code1[1][0]
Fredrik Lundh90a07912000-06-30 07:50:59 +0000419 set.append(code1)
Fredrik Lundh0640e112000-06-30 13:55:15 +0000420 set.append((LITERAL, ord("-")))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000421 break
422 else:
423 if this[0] == "\\":
424 code2 = _class_escape(source, this)
425 else:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000426 code2 = LITERAL, ord(this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000427 if code1[0] != LITERAL or code2[0] != LITERAL:
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000428 raise error, "bad character range"
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000429 lo = code1[1]
430 hi = code2[1]
431 if hi < lo:
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000432 raise error, "bad character range"
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000433 set.append((RANGE, (lo, hi)))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000434 else:
435 if code1[0] is IN:
436 code1 = code1[1][0]
437 set.append(code1)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000438
Fredrik Lundh770617b2001-01-14 15:06:11 +0000439 # XXX: <fl> should move set optimization to compiler!
Fredrik Lundh90a07912000-06-30 07:50:59 +0000440 if len(set)==1 and set[0][0] is LITERAL:
441 subpattern.append(set[0]) # optimization
442 elif len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL:
443 subpattern.append((NOT_LITERAL, set[1][1])) # optimization
444 else:
Fredrik Lundh770617b2001-01-14 15:06:11 +0000445 # XXX: <fl> should add charmap optimization here
Fredrik Lundh90a07912000-06-30 07:50:59 +0000446 subpattern.append((IN, set))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000447
Fredrik Lundh90a07912000-06-30 07:50:59 +0000448 elif this and this[0] in REPEAT_CHARS:
449 # repeat previous item
450 if this == "?":
451 min, max = 0, 1
452 elif this == "*":
453 min, max = 0, MAXREPEAT
Fredrik Lundhc0c7ee32001-02-18 21:04:48 +0000454
Fredrik Lundh90a07912000-06-30 07:50:59 +0000455 elif this == "+":
456 min, max = 1, MAXREPEAT
457 elif this == "{":
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000458 here = source.tell()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000459 min, max = 0, MAXREPEAT
460 lo = hi = ""
461 while source.next in DIGITS:
462 lo = lo + source.get()
463 if source.match(","):
464 while source.next in DIGITS:
465 hi = hi + source.get()
466 else:
467 hi = lo
468 if not source.match("}"):
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000469 subpattern.append((LITERAL, ord(this)))
470 source.seek(here)
471 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000472 if lo:
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000473 min = atoi(lo)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000474 if hi:
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000475 max = atoi(hi)
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000476 if max < min:
477 raise error, "bad repeat interval"
Fredrik Lundh90a07912000-06-30 07:50:59 +0000478 else:
479 raise error, "not supported"
480 # figure out which item to repeat
481 if subpattern:
482 item = subpattern[-1:]
483 else:
Fredrik Lundhc0c7ee32001-02-18 21:04:48 +0000484 item = None
485 if not item or (len(item) == 1 and item[0][0] == AT):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000486 raise error, "nothing to repeat"
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000487 if item[0][0] in (MIN_REPEAT, MAX_REPEAT):
488 raise error, "multiple repeat"
Fredrik Lundh90a07912000-06-30 07:50:59 +0000489 if source.match("?"):
490 subpattern[-1] = (MIN_REPEAT, (min, max, item))
491 else:
492 subpattern[-1] = (MAX_REPEAT, (min, max, item))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000493
Fredrik Lundh90a07912000-06-30 07:50:59 +0000494 elif this == ".":
495 subpattern.append((ANY, None))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000496
Fredrik Lundh90a07912000-06-30 07:50:59 +0000497 elif this == "(":
498 group = 1
499 name = None
500 if source.match("?"):
501 group = 0
502 # options
503 if source.match("P"):
504 # python extensions
505 if source.match("<"):
506 # named group: skip forward to end of name
507 name = ""
508 while 1:
509 char = source.get()
510 if char is None:
511 raise error, "unterminated name"
512 if char == ">":
513 break
514 name = name + char
515 group = 1
516 if not isname(name):
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000517 raise error, "bad character in group name"
Fredrik Lundh90a07912000-06-30 07:50:59 +0000518 elif source.match("="):
519 # named backreference
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000520 name = ""
521 while 1:
522 char = source.get()
523 if char is None:
524 raise error, "unterminated name"
525 if char == ")":
526 break
527 name = name + char
528 if not isname(name):
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000529 raise error, "bad character in group name"
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000530 gid = state.groupdict.get(name)
531 if gid is None:
532 raise error, "unknown group name"
Fredrik Lundh72b82ba2000-07-03 21:31:48 +0000533 subpattern.append((GROUPREF, gid))
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000534 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000535 else:
536 char = source.get()
537 if char is None:
538 raise error, "unexpected end of pattern"
539 raise error, "unknown specifier: ?P%s" % char
540 elif source.match(":"):
541 # non-capturing group
542 group = 2
543 elif source.match("#"):
544 # comment
545 while 1:
546 if source.next is None or source.next == ")":
547 break
548 source.get()
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000549 if not source.match(")"):
550 raise error, "unbalanced parenthesis"
551 continue
Fredrik Lundh6f013982000-07-03 18:44:21 +0000552 elif source.next in ("=", "!", "<"):
Fredrik Lundh43b3b492000-06-30 10:41:31 +0000553 # lookahead assertions
554 char = source.get()
Fredrik Lundh6f013982000-07-03 18:44:21 +0000555 dir = 1
556 if char == "<":
557 if source.next not in ("=", "!"):
558 raise error, "syntax error"
559 dir = -1 # lookbehind
560 char = source.get()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000561 p = _parse_sub(source, state)
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000562 if not source.match(")"):
563 raise error, "unbalanced parenthesis"
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000564 if char == "=":
565 subpattern.append((ASSERT, (dir, p)))
566 else:
567 subpattern.append((ASSERT_NOT, (dir, p)))
568 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000569 else:
570 # flags
Raymond Hettinger54f02222002-06-01 14:18:47 +0000571 if not source.next in FLAGS:
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000572 raise error, "unexpected end of pattern"
Raymond Hettinger54f02222002-06-01 14:18:47 +0000573 while source.next in FLAGS:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000574 state.flags = state.flags | FLAGS[source.get()]
575 if group:
576 # parse group contents
Fredrik Lundh90a07912000-06-30 07:50:59 +0000577 if group == 2:
578 # anonymous group
579 group = None
580 else:
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000581 group = state.opengroup(name)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000582 p = _parse_sub(source, state)
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000583 if not source.match(")"):
584 raise error, "unbalanced parenthesis"
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000585 if group is not None:
586 state.closegroup(group)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000587 subpattern.append((SUBPATTERN, (group, p)))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000588 else:
589 while 1:
590 char = source.get()
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000591 if char is None:
592 raise error, "unexpected end of pattern"
593 if char == ")":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000594 break
595 raise error, "unknown extension"
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000596
Fredrik Lundh90a07912000-06-30 07:50:59 +0000597 elif this == "^":
598 subpattern.append((AT, AT_BEGINNING))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000599
Fredrik Lundh90a07912000-06-30 07:50:59 +0000600 elif this == "$":
601 subpattern.append((AT, AT_END))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000602
Fredrik Lundh90a07912000-06-30 07:50:59 +0000603 elif this and this[0] == "\\":
604 code = _escape(source, this, state)
605 subpattern.append(code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000606
Fredrik Lundh90a07912000-06-30 07:50:59 +0000607 else:
608 raise error, "parser error"
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000609
610 return subpattern
611
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000612def parse(str, flags=0, pattern=None):
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000613 # parse 're' pattern into list of (opcode, argument) tuples
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000614
615 source = Tokenizer(str)
616
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000617 if pattern is None:
618 pattern = Pattern()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000619 pattern.flags = flags
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000620 pattern.str = str
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000621
622 p = _parse_sub(source, pattern, 0)
623
624 tail = source.get()
625 if tail == ")":
626 raise error, "unbalanced parenthesis"
627 elif tail:
628 raise error, "bogus characters at end of regular expression"
629
Fredrik Lundh770617b2001-01-14 15:06:11 +0000630 if flags & SRE_FLAG_DEBUG:
631 p.dump()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000632
Fredrik Lundhd11b5e52000-10-03 19:22:26 +0000633 if not (flags & SRE_FLAG_VERBOSE) and p.pattern.flags & SRE_FLAG_VERBOSE:
634 # the VERBOSE flag was switched on inside the pattern. to be
635 # on the safe side, we'll parse the whole thing again...
636 return parse(str, p.pattern.flags)
637
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000638 return p
639
Fredrik Lundh436c3d52000-06-29 08:58:44 +0000640def parse_template(source, pattern):
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000641 # parse 're' replacement string into list of literals and
642 # group references
643 s = Tokenizer(source)
644 p = []
645 a = p.append
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000646 def literal(literal, p=p):
647 if p and p[-1][0] is LITERAL:
648 p[-1] = LITERAL, p[-1][1] + literal
649 else:
650 p.append((LITERAL, literal))
651 sep = source[:0]
652 if type(sep) is type(""):
Fredrik Lundh59b68652001-09-18 20:55:24 +0000653 makechar = chr
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000654 else:
Fredrik Lundh59b68652001-09-18 20:55:24 +0000655 makechar = unichr
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000656 while 1:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000657 this = s.get()
658 if this is None:
659 break # end of replacement string
660 if this and this[0] == "\\":
661 # group
662 if this == "\\g":
663 name = ""
664 if s.match("<"):
665 while 1:
666 char = s.get()
667 if char is None:
668 raise error, "unterminated group name"
669 if char == ">":
670 break
671 name = name + char
672 if not name:
673 raise error, "bad group name"
674 try:
Fredrik Lundhf2989b22001-02-18 12:05:16 +0000675 index = atoi(name)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000676 except ValueError:
677 if not isname(name):
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000678 raise error, "bad character in group name"
Fredrik Lundh90a07912000-06-30 07:50:59 +0000679 try:
680 index = pattern.groupindex[name]
681 except KeyError:
682 raise IndexError, "unknown group name"
683 a((MARK, index))
684 elif len(this) > 1 and this[1] in DIGITS:
685 code = None
686 while 1:
687 group = _group(this, pattern.groups+1)
688 if group:
Fredrik Lundh19f977b2000-09-24 14:46:23 +0000689 if (s.next not in DIGITS or
Fredrik Lundh90a07912000-06-30 07:50:59 +0000690 not _group(this + s.next, pattern.groups+1)):
Fredrik Lundh1c5aa692001-01-16 07:37:30 +0000691 code = MARK, group
Fredrik Lundh90a07912000-06-30 07:50:59 +0000692 break
693 elif s.next in OCTDIGITS:
694 this = this + s.get()
695 else:
696 break
697 if not code:
698 this = this[1:]
Fredrik Lundh59b68652001-09-18 20:55:24 +0000699 code = LITERAL, makechar(atoi(this[-6:], 8) & 0xff)
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000700 if code[0] is LITERAL:
701 literal(code[1])
702 else:
703 a(code)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000704 else:
705 try:
Fredrik Lundh59b68652001-09-18 20:55:24 +0000706 this = makechar(ESCAPES[this][1])
Fredrik Lundh90a07912000-06-30 07:50:59 +0000707 except KeyError:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000708 pass
709 literal(this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000710 else:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000711 literal(this)
712 # convert template to groups and literals lists
713 i = 0
714 groups = []
715 literals = []
716 for c, s in p:
717 if c is MARK:
718 groups.append((i, s))
719 literals.append(None)
720 else:
721 literals.append(s)
722 i = i + 1
723 return groups, literals
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000724
Fredrik Lundh436c3d52000-06-29 08:58:44 +0000725def expand_template(template, match):
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000726 g = match.group
Fredrik Lundh0640e112000-06-30 13:55:15 +0000727 sep = match.string[:0]
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000728 groups, literals = template
729 literals = literals[:]
730 try:
731 for index, group in groups:
732 literals[index] = s = g(group)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000733 if s is None:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000734 raise IndexError
735 except IndexError:
736 raise error, "empty group"
737 return string.join(literals, sep)