blob: f26229fc2870afd7476ad912bef33f69a03675d2 [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
Barry Warsaw8bee7612004-08-25 02:22:30 +000015import sys
Guido van Rossum7627c0d2000-03-31 14:58:54 +000016
17from sre_constants import *
Serhiy Storchaka70ca0212013-02-16 16:47:47 +020018from _sre import MAXREPEAT
Guido van Rossum7627c0d2000-03-31 14:58:54 +000019
20SPECIAL_CHARS = ".\\[{()*+?^$|"
Fredrik Lundh143328b2000-09-02 11:03:34 +000021REPEAT_CHARS = "*+?{"
Guido van Rossum7627c0d2000-03-31 14:58:54 +000022
Raymond Hettinger049ade22005-02-28 19:27:52 +000023DIGITS = set("0123456789")
Guido van Rossumb81e70e2000-04-10 17:10:48 +000024
Raymond Hettinger049ade22005-02-28 19:27:52 +000025OCTDIGITS = set("01234567")
26HEXDIGITS = set("0123456789abcdefABCDEF")
Guido van Rossum7627c0d2000-03-31 14:58:54 +000027
Raymond Hettinger049ade22005-02-28 19:27:52 +000028WHITESPACE = set(" \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 Lundh436c3d582000-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 Lundh436c3d582000-06-29 08:58:44 +000061 # extensions
Antoine Pitroufd036452008-08-19 17:56:33 +000062 "a": SRE_FLAG_ASCII,
Fredrik Lundh436c3d582000-06-29 08:58:44 +000063 "t": SRE_FLAG_TEMPLATE,
64 "u": SRE_FLAG_UNICODE,
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +000065}
66
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +000067class Pattern:
68 # master pattern object. keeps track of global attributes
Guido van Rossum7627c0d2000-03-31 14:58:54 +000069 def __init__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +000070 self.flags = 0
Fredrik Lundhebc37b22000-10-28 19:30:41 +000071 self.open = []
Fredrik Lundh90a07912000-06-30 07:50:59 +000072 self.groups = 1
73 self.groupdict = {}
Fredrik Lundhebc37b22000-10-28 19:30:41 +000074 def opengroup(self, name=None):
Fredrik Lundh90a07912000-06-30 07:50:59 +000075 gid = self.groups
76 self.groups = gid + 1
Raymond Hettingerf13eb552002-06-02 00:40:05 +000077 if name is not None:
Tim Peters75335872001-11-03 19:35:43 +000078 ogid = self.groupdict.get(name, None)
79 if ogid is not None:
Collin Winterce36ad82007-08-30 01:19:48 +000080 raise error("redefinition of group name %s as group %d; "
81 "was group %d" % (repr(name), gid, ogid))
Fredrik Lundh90a07912000-06-30 07:50:59 +000082 self.groupdict[name] = gid
Fredrik Lundhebc37b22000-10-28 19:30:41 +000083 self.open.append(gid)
Fredrik Lundh90a07912000-06-30 07:50:59 +000084 return gid
Fredrik Lundhebc37b22000-10-28 19:30:41 +000085 def closegroup(self, gid):
86 self.open.remove(gid)
87 def checkgroup(self, gid):
88 return gid < self.groups and gid not in self.open
Guido van Rossum7627c0d2000-03-31 14:58:54 +000089
90class SubPattern:
91 # a subpattern, in intermediate form
92 def __init__(self, pattern, data=None):
Fredrik Lundh90a07912000-06-30 07:50:59 +000093 self.pattern = pattern
Raymond Hettingerf13eb552002-06-02 00:40:05 +000094 if data is None:
Fredrik Lundh90a07912000-06-30 07:50:59 +000095 data = []
96 self.data = data
97 self.width = None
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +000098 def dump(self, level=0):
99 nl = 1
Guido van Rossum13257902007-06-07 23:15:56 +0000100 seqtypes = (tuple, list)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000101 for op, av in self.data:
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000102 print(level*" " + op, end=' '); nl = 0
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000103 if op == "in":
104 # member sublanguage
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000105 print(); nl = 1
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000106 for op, a in av:
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000107 print((level+1)*" " + op, a)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000108 elif op == "branch":
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000109 print(); nl = 1
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000110 i = 0
111 for a in av[1]:
112 if i > 0:
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000113 print(level*" " + "or")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000114 a.dump(level+1); nl = 1
115 i = i + 1
Guido van Rossum13257902007-06-07 23:15:56 +0000116 elif isinstance(av, seqtypes):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000117 for a in av:
118 if isinstance(a, SubPattern):
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000119 if not nl: print()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000120 a.dump(level+1); nl = 1
121 else:
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000122 print(a, end=' ') ; nl = 0
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000123 else:
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000124 print(av, end=' ') ; nl = 0
125 if not nl: print()
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000126 def __repr__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000127 return repr(self.data)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000128 def __len__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000129 return len(self.data)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000130 def __delitem__(self, index):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000131 del self.data[index]
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000132 def __getitem__(self, index):
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000133 if isinstance(index, slice):
134 return SubPattern(self.pattern, self.data[index])
Fredrik Lundh90a07912000-06-30 07:50:59 +0000135 return self.data[index]
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000136 def __setitem__(self, index, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000137 self.data[index] = code
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000138 def insert(self, index, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000139 self.data.insert(index, code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000140 def append(self, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000141 self.data.append(code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000142 def getwidth(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000143 # determine the width (min, max) for this subpattern
144 if self.width:
145 return self.width
Guido van Rossume2a383d2007-01-15 16:59:06 +0000146 lo = hi = 0
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000147 UNITCODES = (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY)
148 REPEATCODES = (MIN_REPEAT, MAX_REPEAT)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000149 for op, av in self.data:
150 if op is BRANCH:
Serhiy Storchaka9d965422013-08-19 22:50:54 +0300151 i = MAXREPEAT - 1
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000152 j = 0
Fredrik Lundh90a07912000-06-30 07:50:59 +0000153 for av in av[1]:
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000154 l, h = av.getwidth()
155 i = min(i, l)
Fredrik Lundhe1869832000-08-01 22:47:49 +0000156 j = max(j, h)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000157 lo = lo + i
158 hi = hi + j
159 elif op is CALL:
160 i, j = av.getwidth()
161 lo = lo + i
162 hi = hi + j
163 elif op is SUBPATTERN:
164 i, j = av[1].getwidth()
165 lo = lo + i
166 hi = hi + j
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000167 elif op in REPEATCODES:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000168 i, j = av[2].getwidth()
Serhiy Storchaka9d965422013-08-19 22:50:54 +0300169 lo = lo + i * av[0]
170 hi = hi + j * av[1]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000171 elif op in UNITCODES:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000172 lo = lo + 1
173 hi = hi + 1
174 elif op == SUCCESS:
175 break
Serhiy Storchaka9d965422013-08-19 22:50:54 +0300176 self.width = min(lo, MAXREPEAT - 1), min(hi, MAXREPEAT)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000177 return self.width
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000178
179class Tokenizer:
180 def __init__(self, string):
Antoine Pitrou463badf2012-06-23 13:29:19 +0200181 self.istext = isinstance(string, str)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000182 self.string = string
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000183 self.index = 0
184 self.__next()
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000185 def __next(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000186 if self.index >= len(self.string):
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000187 self.next = None
188 return
Guido van Rossum75a902d2007-10-19 22:06:24 +0000189 char = self.string[self.index:self.index+1]
190 # Special case for the str8, since indexing returns a integer
191 # XXX This is only needed for test_bug_926075 in test_re.py
Antoine Pitrou463badf2012-06-23 13:29:19 +0200192 if char and not self.istext:
Thomas Wouters40a088d2008-03-18 20:19:54 +0000193 char = chr(char[0])
Guido van Rossum75a902d2007-10-19 22:06:24 +0000194 if char == "\\":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000195 try:
196 c = self.string[self.index + 1]
197 except IndexError:
Collin Winterce36ad82007-08-30 01:19:48 +0000198 raise error("bogus escape (end of line)")
Antoine Pitrou463badf2012-06-23 13:29:19 +0200199 if not self.istext:
Antoine Pitrou22628c42008-07-22 17:53:22 +0000200 c = chr(c)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000201 char = char + c
202 self.index = self.index + len(char)
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000203 self.next = char
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000204 def match(self, char, skip=1):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000205 if char == self.next:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000206 if skip:
207 self.__next()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000208 return 1
209 return 0
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000210 def get(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000211 this = self.next
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000212 self.__next()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000213 return this
Antoine Pitrou463badf2012-06-23 13:29:19 +0200214 def getwhile(self, n, charset):
215 result = ''
216 for _ in range(n):
217 c = self.next
218 if c not in charset:
219 break
220 result += c
221 self.__next()
222 return result
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000223 def tell(self):
224 return self.index, self.next
225 def seek(self, index):
226 self.index, self.next = index
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000227
Georg Brandl1d472b72013-04-14 11:40:00 +0200228# The following three functions are not used in this module anymore, but we keep
229# them here (with DeprecationWarnings) for backwards compatibility.
230
Fredrik Lundh4781b072000-06-29 12:38:45 +0000231def isident(char):
Georg Brandl1d472b72013-04-14 11:40:00 +0200232 import warnings
233 warnings.warn('sre_parse.isident() will be removed in 3.5',
234 DeprecationWarning, stacklevel=2)
Fredrik Lundh4781b072000-06-29 12:38:45 +0000235 return "a" <= char <= "z" or "A" <= char <= "Z" or char == "_"
236
237def isdigit(char):
Georg Brandl1d472b72013-04-14 11:40:00 +0200238 import warnings
239 warnings.warn('sre_parse.isdigit() will be removed in 3.5',
240 DeprecationWarning, stacklevel=2)
Fredrik Lundh4781b072000-06-29 12:38:45 +0000241 return "0" <= char <= "9"
242
243def isname(name):
Georg Brandl1d472b72013-04-14 11:40:00 +0200244 import warnings
245 warnings.warn('sre_parse.isname() will be removed in 3.5',
246 DeprecationWarning, stacklevel=2)
Fredrik Lundh4781b072000-06-29 12:38:45 +0000247 # check that group name is a valid string
Fredrik Lundh4781b072000-06-29 12:38:45 +0000248 if not isident(name[0]):
Guido van Rossum8ca162f2002-04-07 06:36:23 +0000249 return False
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000250 for char in name[1:]:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000251 if not isident(char) and not isdigit(char):
Guido van Rossum8ca162f2002-04-07 06:36:23 +0000252 return False
253 return True
Fredrik Lundh4781b072000-06-29 12:38:45 +0000254
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000255def _class_escape(source, escape):
256 # handle escape code inside character class
257 code = ESCAPES.get(escape)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000258 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000259 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000260 code = CATEGORIES.get(escape)
Ezio Melottife8e6e72013-01-11 08:32:01 +0200261 if code and code[0] == IN:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000262 return code
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000263 try:
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000264 c = escape[1:2]
265 if c == "x":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000266 # hexadecimal escape (exactly two digits)
Antoine Pitrou463badf2012-06-23 13:29:19 +0200267 escape += source.getwhile(2, HEXDIGITS)
268 if len(escape) != 4:
269 raise ValueError
270 return LITERAL, int(escape[2:], 16) & 0xff
271 elif c == "u" and source.istext:
272 # unicode escape (exactly four digits)
273 escape += source.getwhile(4, HEXDIGITS)
274 if len(escape) != 6:
275 raise ValueError
276 return LITERAL, int(escape[2:], 16)
277 elif c == "U" and source.istext:
278 # unicode escape (exactly eight digits)
279 escape += source.getwhile(8, HEXDIGITS)
280 if len(escape) != 10:
281 raise ValueError
282 c = int(escape[2:], 16)
283 chr(c) # raise ValueError for invalid code
284 return LITERAL, c
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000285 elif c in OCTDIGITS:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000286 # octal escape (up to three digits)
Antoine Pitrou463badf2012-06-23 13:29:19 +0200287 escape += source.getwhile(2, OCTDIGITS)
288 return LITERAL, int(escape[1:], 8) & 0xff
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000289 elif c in DIGITS:
Antoine Pitrou463badf2012-06-23 13:29:19 +0200290 raise ValueError
Fredrik Lundh90a07912000-06-30 07:50:59 +0000291 if len(escape) == 2:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000292 return LITERAL, ord(escape[1])
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000293 except ValueError:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000294 pass
Collin Winterce36ad82007-08-30 01:19:48 +0000295 raise error("bogus escape: %s" % repr(escape))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000296
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000297def _escape(source, escape, state):
298 # handle escape code in expression
299 code = CATEGORIES.get(escape)
300 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000301 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000302 code = ESCAPES.get(escape)
303 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000304 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000305 try:
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000306 c = escape[1:2]
307 if c == "x":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000308 # hexadecimal escape
Antoine Pitrou463badf2012-06-23 13:29:19 +0200309 escape += source.getwhile(2, HEXDIGITS)
Fredrik Lundh143328b2000-09-02 11:03:34 +0000310 if len(escape) != 4:
311 raise ValueError
Barry Warsaw8bee7612004-08-25 02:22:30 +0000312 return LITERAL, int(escape[2:], 16) & 0xff
Antoine Pitrou463badf2012-06-23 13:29:19 +0200313 elif c == "u" and source.istext:
314 # unicode escape (exactly four digits)
315 escape += source.getwhile(4, HEXDIGITS)
316 if len(escape) != 6:
317 raise ValueError
318 return LITERAL, int(escape[2:], 16)
319 elif c == "U" and source.istext:
320 # unicode escape (exactly eight digits)
321 escape += source.getwhile(8, HEXDIGITS)
322 if len(escape) != 10:
323 raise ValueError
324 c = int(escape[2:], 16)
325 chr(c) # raise ValueError for invalid code
326 return LITERAL, c
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000327 elif c == "0":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000328 # octal escape
Antoine Pitrou463badf2012-06-23 13:29:19 +0200329 escape += source.getwhile(2, OCTDIGITS)
Barry Warsaw8bee7612004-08-25 02:22:30 +0000330 return LITERAL, int(escape[1:], 8) & 0xff
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000331 elif c in DIGITS:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000332 # octal escape *or* decimal group reference (sigh)
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000333 if source.next in DIGITS:
334 escape = escape + source.get()
Fredrik Lundh143328b2000-09-02 11:03:34 +0000335 if (escape[1] in OCTDIGITS and escape[2] in OCTDIGITS and
336 source.next in OCTDIGITS):
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000337 # got three octal digits; this is an octal escape
Fredrik Lundh90a07912000-06-30 07:50:59 +0000338 escape = escape + source.get()
Barry Warsaw8bee7612004-08-25 02:22:30 +0000339 return LITERAL, int(escape[1:], 8) & 0xff
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000340 # not an octal escape, so this is a group reference
341 group = int(escape[1:])
342 if group < state.groups:
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000343 if not state.checkgroup(group):
Collin Winterce36ad82007-08-30 01:19:48 +0000344 raise error("cannot refer to open group")
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000345 return GROUPREF, group
Fredrik Lundh143328b2000-09-02 11:03:34 +0000346 raise ValueError
Fredrik Lundh90a07912000-06-30 07:50:59 +0000347 if len(escape) == 2:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000348 return LITERAL, ord(escape[1])
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000349 except ValueError:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000350 pass
Collin Winterce36ad82007-08-30 01:19:48 +0000351 raise error("bogus escape: %s" % repr(escape))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000352
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000353def _parse_sub(source, state, nested=1):
354 # parse an alternation: a|b|c
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000355
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000356 items = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000357 itemsappend = items.append
358 sourcematch = source.match
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000359 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000360 itemsappend(_parse(source, state))
361 if sourcematch("|"):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000362 continue
363 if not nested:
364 break
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000365 if not source.next or sourcematch(")", 0):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000366 break
367 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000368 raise error("pattern not properly closed")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000369
370 if len(items) == 1:
371 return items[0]
372
373 subpattern = SubPattern(state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000374 subpatternappend = subpattern.append
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000375
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000376 # check if all items share a common prefix
377 while 1:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000378 prefix = None
379 for item in items:
380 if not item:
381 break
382 if prefix is None:
383 prefix = item[0]
384 elif item[0] != prefix:
385 break
386 else:
387 # all subitems start with a common "prefix".
388 # move it out of the branch
389 for item in items:
390 del item[0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000391 subpatternappend(prefix)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000392 continue # check next one
393 break
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000394
395 # check if the branch can be replaced by a character set
396 for item in items:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000397 if len(item) != 1 or item[0][0] != LITERAL:
398 break
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000399 else:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000400 # we can store this as a character set instead of a
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000401 # branch (the compiler may optimize this even more)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000402 set = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000403 setappend = set.append
Fredrik Lundh90a07912000-06-30 07:50:59 +0000404 for item in items:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000405 setappend(item[0])
406 subpatternappend((IN, set))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000407 return subpattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000408
409 subpattern.append((BRANCH, (None, items)))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000410 return subpattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000411
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000412def _parse_sub_cond(source, state, condgroup):
Tim Peters58eb11c2004-01-18 20:29:55 +0000413 item_yes = _parse(source, state)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000414 if source.match("|"):
Tim Peters58eb11c2004-01-18 20:29:55 +0000415 item_no = _parse(source, state)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000416 if source.match("|"):
Collin Winterce36ad82007-08-30 01:19:48 +0000417 raise error("conditional backref with more than two branches")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000418 else:
419 item_no = None
420 if source.next and not source.match(")", 0):
Collin Winterce36ad82007-08-30 01:19:48 +0000421 raise error("pattern not properly closed")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000422 subpattern = SubPattern(state)
423 subpattern.append((GROUPREF_EXISTS, (condgroup, item_yes, item_no)))
424 return subpattern
425
Raymond Hettinger049ade22005-02-28 19:27:52 +0000426_PATTERNENDERS = set("|)")
427_ASSERTCHARS = set("=!<")
428_LOOKBEHINDASSERTCHARS = set("=!")
429_REPEATCODES = set([MIN_REPEAT, MAX_REPEAT])
430
Fredrik Lundh55a4f4a2000-06-30 22:37:31 +0000431def _parse(source, state):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000432 # parse a simple pattern
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000433 subpattern = SubPattern(state)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000434
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000435 # precompute constants into local variables
436 subpatternappend = subpattern.append
437 sourceget = source.get
438 sourcematch = source.match
439 _len = len
Raymond Hettinger049ade22005-02-28 19:27:52 +0000440 PATTERNENDERS = _PATTERNENDERS
441 ASSERTCHARS = _ASSERTCHARS
442 LOOKBEHINDASSERTCHARS = _LOOKBEHINDASSERTCHARS
443 REPEATCODES = _REPEATCODES
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000444
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000445 while 1:
446
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000447 if source.next in PATTERNENDERS:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000448 break # end of subpattern
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000449 this = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000450 if this is None:
451 break # end of pattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000452
Fredrik Lundh90a07912000-06-30 07:50:59 +0000453 if state.flags & SRE_FLAG_VERBOSE:
454 # skip whitespace and comments
455 if this in WHITESPACE:
456 continue
457 if this == "#":
458 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000459 this = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000460 if this in (None, "\n"):
461 break
462 continue
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000463
Fredrik Lundh90a07912000-06-30 07:50:59 +0000464 if this and this[0] not in SPECIAL_CHARS:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000465 subpatternappend((LITERAL, ord(this)))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000466
Fredrik Lundh90a07912000-06-30 07:50:59 +0000467 elif this == "[":
468 # character set
469 set = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000470 setappend = set.append
471## if sourcematch(":"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000472## pass # handle character classes
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000473 if sourcematch("^"):
474 setappend((NEGATE, None))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000475 # check remaining characters
476 start = set[:]
477 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000478 this = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000479 if this == "]" and set != start:
480 break
481 elif this and this[0] == "\\":
482 code1 = _class_escape(source, this)
483 elif this:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000484 code1 = LITERAL, ord(this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000485 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000486 raise error("unexpected end of regular expression")
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000487 if sourcematch("-"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000488 # potential range
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000489 this = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000490 if this == "]":
Fredrik Lundh025468d2000-10-07 10:16:19 +0000491 if code1[0] is IN:
492 code1 = code1[1][0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000493 setappend(code1)
494 setappend((LITERAL, ord("-")))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000495 break
Guido van Rossum41c99e72003-04-14 17:59:34 +0000496 elif this:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000497 if this[0] == "\\":
498 code2 = _class_escape(source, this)
499 else:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000500 code2 = LITERAL, ord(this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000501 if code1[0] != LITERAL or code2[0] != LITERAL:
Collin Winterce36ad82007-08-30 01:19:48 +0000502 raise error("bad character range")
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000503 lo = code1[1]
504 hi = code2[1]
505 if hi < lo:
Collin Winterce36ad82007-08-30 01:19:48 +0000506 raise error("bad character range")
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000507 setappend((RANGE, (lo, hi)))
Guido van Rossum41c99e72003-04-14 17:59:34 +0000508 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000509 raise error("unexpected end of regular expression")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000510 else:
511 if code1[0] is IN:
512 code1 = code1[1][0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000513 setappend(code1)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000514
Fredrik Lundh770617b2001-01-14 15:06:11 +0000515 # XXX: <fl> should move set optimization to compiler!
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000516 if _len(set)==1 and set[0][0] is LITERAL:
517 subpatternappend(set[0]) # optimization
518 elif _len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL:
519 subpatternappend((NOT_LITERAL, set[1][1])) # optimization
Fredrik Lundh90a07912000-06-30 07:50:59 +0000520 else:
Fredrik Lundh770617b2001-01-14 15:06:11 +0000521 # XXX: <fl> should add charmap optimization here
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000522 subpatternappend((IN, set))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000523
Fredrik Lundh90a07912000-06-30 07:50:59 +0000524 elif this and this[0] in REPEAT_CHARS:
525 # repeat previous item
526 if this == "?":
527 min, max = 0, 1
528 elif this == "*":
529 min, max = 0, MAXREPEAT
Fredrik Lundhc0c7ee32001-02-18 21:04:48 +0000530
Fredrik Lundh90a07912000-06-30 07:50:59 +0000531 elif this == "+":
532 min, max = 1, MAXREPEAT
533 elif this == "{":
Gustavo Niemeyer6fa0c5a2005-09-14 08:54:39 +0000534 if source.next == "}":
535 subpatternappend((LITERAL, ord(this)))
536 continue
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000537 here = source.tell()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000538 min, max = 0, MAXREPEAT
539 lo = hi = ""
540 while source.next in DIGITS:
541 lo = lo + source.get()
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000542 if sourcematch(","):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000543 while source.next in DIGITS:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000544 hi = hi + sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000545 else:
546 hi = lo
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000547 if not sourcematch("}"):
548 subpatternappend((LITERAL, ord(this)))
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000549 source.seek(here)
550 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000551 if lo:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000552 min = int(lo)
Serhiy Storchaka70ca0212013-02-16 16:47:47 +0200553 if min >= MAXREPEAT:
554 raise OverflowError("the repetition number is too large")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000555 if hi:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000556 max = int(hi)
Serhiy Storchaka70ca0212013-02-16 16:47:47 +0200557 if max >= MAXREPEAT:
558 raise OverflowError("the repetition number is too large")
559 if max < min:
560 raise error("bad repeat interval")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000561 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000562 raise error("not supported")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000563 # figure out which item to repeat
564 if subpattern:
565 item = subpattern[-1:]
566 else:
Fredrik Lundhc0c7ee32001-02-18 21:04:48 +0000567 item = None
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000568 if not item or (_len(item) == 1 and item[0][0] == AT):
Collin Winterce36ad82007-08-30 01:19:48 +0000569 raise error("nothing to repeat")
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000570 if item[0][0] in REPEATCODES:
Collin Winterce36ad82007-08-30 01:19:48 +0000571 raise error("multiple repeat")
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000572 if sourcematch("?"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000573 subpattern[-1] = (MIN_REPEAT, (min, max, item))
574 else:
575 subpattern[-1] = (MAX_REPEAT, (min, max, item))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000576
Fredrik Lundh90a07912000-06-30 07:50:59 +0000577 elif this == ".":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000578 subpatternappend((ANY, None))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000579
Fredrik Lundh90a07912000-06-30 07:50:59 +0000580 elif this == "(":
581 group = 1
582 name = None
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000583 condgroup = None
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000584 if sourcematch("?"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000585 group = 0
586 # options
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000587 if sourcematch("P"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000588 # python extensions
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000589 if sourcematch("<"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000590 # named group: skip forward to end of name
591 name = ""
592 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000593 char = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000594 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000595 raise error("unterminated name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000596 if char == ">":
597 break
598 name = name + char
599 group = 1
Ezio Melotti0941d9f2012-11-03 20:33:08 +0200600 if not name:
601 raise error("missing group name")
Georg Brandl1d472b72013-04-14 11:40:00 +0200602 if not name.isidentifier():
R David Murray26dfaac92013-04-14 13:00:54 -0400603 raise error("bad character in group name %r" % name)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000604 elif sourcematch("="):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000605 # named backreference
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000606 name = ""
607 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000608 char = sourceget()
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000609 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000610 raise error("unterminated name")
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000611 if char == ")":
612 break
613 name = name + char
Ezio Melotti0941d9f2012-11-03 20:33:08 +0200614 if not name:
615 raise error("missing group name")
Georg Brandl1d472b72013-04-14 11:40:00 +0200616 if not name.isidentifier():
R David Murray26dfaac92013-04-14 13:00:54 -0400617 raise error("bad character in backref group name "
618 "%r" % name)
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000619 gid = state.groupdict.get(name)
620 if gid is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000621 raise error("unknown group name")
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000622 subpatternappend((GROUPREF, gid))
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000623 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000624 else:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000625 char = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000626 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000627 raise error("unexpected end of pattern")
628 raise error("unknown specifier: ?P%s" % char)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000629 elif sourcematch(":"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000630 # non-capturing group
631 group = 2
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000632 elif sourcematch("#"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000633 # comment
634 while 1:
635 if source.next is None or source.next == ")":
636 break
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000637 sourceget()
638 if not sourcematch(")"):
Collin Winterce36ad82007-08-30 01:19:48 +0000639 raise error("unbalanced parenthesis")
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000640 continue
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000641 elif source.next in ASSERTCHARS:
Fredrik Lundh43b3b492000-06-30 10:41:31 +0000642 # lookahead assertions
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000643 char = sourceget()
Fredrik Lundh6f013982000-07-03 18:44:21 +0000644 dir = 1
645 if char == "<":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000646 if source.next not in LOOKBEHINDASSERTCHARS:
Collin Winterce36ad82007-08-30 01:19:48 +0000647 raise error("syntax error")
Fredrik Lundh6f013982000-07-03 18:44:21 +0000648 dir = -1 # lookbehind
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000649 char = sourceget()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000650 p = _parse_sub(source, state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000651 if not sourcematch(")"):
Collin Winterce36ad82007-08-30 01:19:48 +0000652 raise error("unbalanced parenthesis")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000653 if char == "=":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000654 subpatternappend((ASSERT, (dir, p)))
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000655 else:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000656 subpatternappend((ASSERT_NOT, (dir, p)))
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000657 continue
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000658 elif sourcematch("("):
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000659 # conditional backreference group
660 condname = ""
661 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000662 char = sourceget()
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000663 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000664 raise error("unterminated name")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000665 if char == ")":
666 break
667 condname = condname + char
668 group = 2
Ezio Melotti0941d9f2012-11-03 20:33:08 +0200669 if not condname:
670 raise error("missing group name")
Georg Brandl1d472b72013-04-14 11:40:00 +0200671 if condname.isidentifier():
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000672 condgroup = state.groupdict.get(condname)
673 if condgroup is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000674 raise error("unknown group name")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000675 else:
676 try:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000677 condgroup = int(condname)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000678 except ValueError:
Collin Winterce36ad82007-08-30 01:19:48 +0000679 raise error("bad character in group name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000680 else:
681 # flags
Raymond Hettinger54f02222002-06-01 14:18:47 +0000682 if not source.next in FLAGS:
Collin Winterce36ad82007-08-30 01:19:48 +0000683 raise error("unexpected end of pattern")
Raymond Hettinger54f02222002-06-01 14:18:47 +0000684 while source.next in FLAGS:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000685 state.flags = state.flags | FLAGS[sourceget()]
Fredrik Lundh90a07912000-06-30 07:50:59 +0000686 if group:
687 # parse group contents
Fredrik Lundh90a07912000-06-30 07:50:59 +0000688 if group == 2:
689 # anonymous group
690 group = None
691 else:
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000692 group = state.opengroup(name)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000693 if condgroup:
694 p = _parse_sub_cond(source, state, condgroup)
695 else:
696 p = _parse_sub(source, state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000697 if not sourcematch(")"):
Collin Winterce36ad82007-08-30 01:19:48 +0000698 raise error("unbalanced parenthesis")
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000699 if group is not None:
700 state.closegroup(group)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000701 subpatternappend((SUBPATTERN, (group, p)))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000702 else:
703 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000704 char = sourceget()
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000705 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000706 raise error("unexpected end of pattern")
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000707 if char == ")":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000708 break
Collin Winterce36ad82007-08-30 01:19:48 +0000709 raise error("unknown extension")
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000710
Fredrik Lundh90a07912000-06-30 07:50:59 +0000711 elif this == "^":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000712 subpatternappend((AT, AT_BEGINNING))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000713
Fredrik Lundh90a07912000-06-30 07:50:59 +0000714 elif this == "$":
715 subpattern.append((AT, AT_END))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000716
Fredrik Lundh90a07912000-06-30 07:50:59 +0000717 elif this and this[0] == "\\":
718 code = _escape(source, this, state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000719 subpatternappend(code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000720
Fredrik Lundh90a07912000-06-30 07:50:59 +0000721 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000722 raise error("parser error")
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000723
724 return subpattern
725
Antoine Pitroufd036452008-08-19 17:56:33 +0000726def fix_flags(src, flags):
727 # Check and fix flags according to the type of pattern (str or bytes)
728 if isinstance(src, str):
729 if not flags & SRE_FLAG_ASCII:
730 flags |= SRE_FLAG_UNICODE
731 elif flags & SRE_FLAG_UNICODE:
732 raise ValueError("ASCII and UNICODE flags are incompatible")
733 else:
734 if flags & SRE_FLAG_UNICODE:
735 raise ValueError("can't use UNICODE flag with a bytes pattern")
736 return flags
737
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000738def parse(str, flags=0, pattern=None):
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000739 # parse 're' pattern into list of (opcode, argument) tuples
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000740
741 source = Tokenizer(str)
742
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000743 if pattern is None:
744 pattern = Pattern()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000745 pattern.flags = flags
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000746 pattern.str = str
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000747
748 p = _parse_sub(source, pattern, 0)
Antoine Pitroufd036452008-08-19 17:56:33 +0000749 p.pattern.flags = fix_flags(str, p.pattern.flags)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000750
751 tail = source.get()
752 if tail == ")":
Collin Winterce36ad82007-08-30 01:19:48 +0000753 raise error("unbalanced parenthesis")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000754 elif tail:
Collin Winterce36ad82007-08-30 01:19:48 +0000755 raise error("bogus characters at end of regular expression")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000756
Fredrik Lundh770617b2001-01-14 15:06:11 +0000757 if flags & SRE_FLAG_DEBUG:
758 p.dump()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000759
Fredrik Lundhd11b5e52000-10-03 19:22:26 +0000760 if not (flags & SRE_FLAG_VERBOSE) and p.pattern.flags & SRE_FLAG_VERBOSE:
761 # the VERBOSE flag was switched on inside the pattern. to be
762 # on the safe side, we'll parse the whole thing again...
763 return parse(str, p.pattern.flags)
764
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000765 return p
766
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000767def parse_template(source, pattern):
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000768 # parse 're' replacement string into list of literals and
769 # group references
770 s = Tokenizer(source)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000771 sget = s.get
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000772 p = []
773 a = p.append
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000774 def literal(literal, p=p, pappend=a):
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000775 if p and p[-1][0] is LITERAL:
776 p[-1] = LITERAL, p[-1][1] + literal
777 else:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000778 pappend((LITERAL, literal))
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000779 sep = source[:0]
Guido van Rossum13257902007-06-07 23:15:56 +0000780 if isinstance(sep, str):
Fredrik Lundh59b68652001-09-18 20:55:24 +0000781 makechar = chr
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000782 else:
Guido van Rossum84fc66d2007-05-03 17:18:26 +0000783 makechar = chr
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000784 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000785 this = sget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000786 if this is None:
787 break # end of replacement string
788 if this and this[0] == "\\":
789 # group
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000790 c = this[1:2]
791 if c == "g":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000792 name = ""
793 if s.match("<"):
794 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000795 char = sget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000796 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000797 raise error("unterminated group name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000798 if char == ">":
799 break
800 name = name + char
801 if not name:
Ezio Melotti0941d9f2012-11-03 20:33:08 +0200802 raise error("missing group name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000803 try:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000804 index = int(name)
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000805 if index < 0:
Collin Winterce36ad82007-08-30 01:19:48 +0000806 raise error("negative group number")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000807 except ValueError:
Georg Brandl1d472b72013-04-14 11:40:00 +0200808 if not name.isidentifier():
Collin Winterce36ad82007-08-30 01:19:48 +0000809 raise error("bad character in group name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000810 try:
811 index = pattern.groupindex[name]
812 except KeyError:
Collin Winterce36ad82007-08-30 01:19:48 +0000813 raise IndexError("unknown group name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000814 a((MARK, index))
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000815 elif c == "0":
816 if s.next in OCTDIGITS:
817 this = this + sget()
818 if s.next in OCTDIGITS:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000819 this = this + sget()
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000820 literal(makechar(int(this[1:], 8) & 0xff))
821 elif c in DIGITS:
822 isoctal = False
823 if s.next in DIGITS:
824 this = this + sget()
Gustavo Niemeyerf5a15992004-09-03 20:15:56 +0000825 if (c in OCTDIGITS and this[2] in OCTDIGITS and
826 s.next in OCTDIGITS):
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000827 this = this + sget()
828 isoctal = True
829 literal(makechar(int(this[1:], 8) & 0xff))
830 if not isoctal:
831 a((MARK, int(this[1:])))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000832 else:
833 try:
Fredrik Lundh59b68652001-09-18 20:55:24 +0000834 this = makechar(ESCAPES[this][1])
Fredrik Lundh90a07912000-06-30 07:50:59 +0000835 except KeyError:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000836 pass
837 literal(this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000838 else:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000839 literal(this)
840 # convert template to groups and literals lists
841 i = 0
842 groups = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000843 groupsappend = groups.append
844 literals = [None] * len(p)
Ezio Melottib92ed7c2010-03-06 15:24:08 +0000845 if isinstance(source, str):
846 encode = lambda x: x
847 else:
848 # The tokenizer implicitly decodes bytes objects as latin-1, we must
849 # therefore re-encode the final representation.
Marc-André Lemburg8f36af72011-02-25 15:42:01 +0000850 encode = lambda x: x.encode('latin-1')
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000851 for c, s in p:
852 if c is MARK:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000853 groupsappend((i, s))
854 # literal[i] is already None
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000855 else:
Ezio Melottib92ed7c2010-03-06 15:24:08 +0000856 literals[i] = encode(s)
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000857 i = i + 1
858 return groups, literals
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000859
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000860def expand_template(template, match):
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000861 g = match.group
Fredrik Lundh0640e112000-06-30 13:55:15 +0000862 sep = match.string[:0]
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000863 groups, literals = template
864 literals = literals[:]
865 try:
866 for index, group in groups:
867 literals[index] = s = g(group)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000868 if s is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000869 raise error("unmatched group")
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000870 except IndexError:
Collin Winterce36ad82007-08-30 01:19:48 +0000871 raise error("invalid group reference")
Barry Warsaw8bee7612004-08-25 02:22:30 +0000872 return sep.join(literals)