blob: 1a7d3162532eeab93adbee1fbfc724c95d9d973d [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
Guido van Rossum7627c0d2000-03-31 14:58:54 +000015from sre_constants import *
16
17SPECIAL_CHARS = ".\\[{()*+?^$|"
Fredrik Lundh143328b2000-09-02 11:03:34 +000018REPEAT_CHARS = "*+?{"
Guido van Rossum7627c0d2000-03-31 14:58:54 +000019
Serhiy Storchakae2ccf562014-10-10 11:14:49 +030020DIGITS = frozenset("0123456789")
Guido van Rossumb81e70e2000-04-10 17:10:48 +000021
Serhiy Storchakae2ccf562014-10-10 11:14:49 +030022OCTDIGITS = frozenset("01234567")
23HEXDIGITS = frozenset("0123456789abcdefABCDEF")
Guido van Rossum7627c0d2000-03-31 14:58:54 +000024
Serhiy Storchakae2ccf562014-10-10 11:14:49 +030025WHITESPACE = frozenset(" \t\n\r\v\f")
26
Raymond Hettingerdf1b6992014-11-09 15:56:33 -080027_REPEATCODES = frozenset({MIN_REPEAT, MAX_REPEAT})
28_UNITCODES = frozenset({ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY})
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
Benjamin Peterson66323412014-11-30 11:49:00 -050071 self.open = []
72 self.groups = 1
Fredrik Lundh90a07912000-06-30 07:50:59 +000073 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
Benjamin Peterson66323412014-11-30 11:49:00 -050076 self.groups = gid + 1
Serhiy Storchaka9baa5b22014-09-29 22:49:23 +030077 if self.groups > MAXGROUPS:
78 raise error("groups number is too large")
Raymond Hettingerf13eb552002-06-02 00:40:05 +000079 if name is not None:
Tim Peters75335872001-11-03 19:35:43 +000080 ogid = self.groupdict.get(name, None)
81 if ogid is not None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +020082 raise error("redefinition of group name %r as group %d; "
83 "was group %d" % (name, gid, ogid))
Fredrik Lundh90a07912000-06-30 07:50:59 +000084 self.groupdict[name] = gid
Benjamin Peterson66323412014-11-30 11:49:00 -050085 self.open.append(gid)
Fredrik Lundh90a07912000-06-30 07:50:59 +000086 return gid
Benjamin Peterson66323412014-11-30 11:49:00 -050087 def closegroup(self, gid):
88 self.open.remove(gid)
Fredrik Lundhebc37b22000-10-28 19:30:41 +000089 def checkgroup(self, gid):
Benjamin Peterson66323412014-11-30 11:49:00 -050090 return gid < self.groups and gid not in self.open
Guido van Rossum7627c0d2000-03-31 14:58:54 +000091
92class SubPattern:
93 # a subpattern, in intermediate form
94 def __init__(self, pattern, data=None):
Fredrik Lundh90a07912000-06-30 07:50:59 +000095 self.pattern = pattern
Raymond Hettingerf13eb552002-06-02 00:40:05 +000096 if data is None:
Fredrik Lundh90a07912000-06-30 07:50:59 +000097 data = []
98 self.data = data
99 self.width = None
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000100 def dump(self, level=0):
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300101 nl = True
Guido van Rossum13257902007-06-07 23:15:56 +0000102 seqtypes = (tuple, list)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000103 for op, av in self.data:
Serhiy Storchakac7f7d382014-11-09 20:48:36 +0200104 print(level*" " + str(op), end='')
Serhiy Storchakaab140882014-11-11 21:13:28 +0200105 if op is IN:
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000106 # member sublanguage
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300107 print()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000108 for op, a in av:
Serhiy Storchakac7f7d382014-11-09 20:48:36 +0200109 print((level+1)*" " + str(op), a)
Serhiy Storchakaab140882014-11-11 21:13:28 +0200110 elif op is BRANCH:
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300111 print()
112 for i, a in enumerate(av[1]):
113 if i:
Serhiy Storchakac7f7d382014-11-09 20:48:36 +0200114 print(level*" " + "OR")
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300115 a.dump(level+1)
Serhiy Storchakaab140882014-11-11 21:13:28 +0200116 elif op is GROUPREF_EXISTS:
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300117 condgroup, item_yes, item_no = av
118 print('', condgroup)
119 item_yes.dump(level+1)
120 if item_no:
Serhiy Storchakac7f7d382014-11-09 20:48:36 +0200121 print(level*" " + "ELSE")
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300122 item_no.dump(level+1)
Guido van Rossum13257902007-06-07 23:15:56 +0000123 elif isinstance(av, seqtypes):
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300124 nl = False
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000125 for a in av:
126 if isinstance(a, SubPattern):
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300127 if not nl:
128 print()
129 a.dump(level+1)
130 nl = True
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000131 else:
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300132 if not nl:
133 print(' ', end='')
134 print(a, end='')
135 nl = False
136 if not nl:
137 print()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000138 else:
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300139 print('', av)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000140 def __repr__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000141 return repr(self.data)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000142 def __len__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000143 return len(self.data)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000144 def __delitem__(self, index):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000145 del self.data[index]
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000146 def __getitem__(self, index):
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000147 if isinstance(index, slice):
148 return SubPattern(self.pattern, self.data[index])
Fredrik Lundh90a07912000-06-30 07:50:59 +0000149 return self.data[index]
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000150 def __setitem__(self, index, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000151 self.data[index] = code
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000152 def insert(self, index, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000153 self.data.insert(index, code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000154 def append(self, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000155 self.data.append(code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000156 def getwidth(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000157 # determine the width (min, max) for this subpattern
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300158 if self.width is not None:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000159 return self.width
Guido van Rossume2a383d2007-01-15 16:59:06 +0000160 lo = hi = 0
Fredrik Lundh90a07912000-06-30 07:50:59 +0000161 for op, av in self.data:
162 if op is BRANCH:
Serhiy Storchaka9d965422013-08-19 22:50:54 +0300163 i = MAXREPEAT - 1
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000164 j = 0
Fredrik Lundh90a07912000-06-30 07:50:59 +0000165 for av in av[1]:
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000166 l, h = av.getwidth()
167 i = min(i, l)
Fredrik Lundhe1869832000-08-01 22:47:49 +0000168 j = max(j, h)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000169 lo = lo + i
170 hi = hi + j
171 elif op is CALL:
172 i, j = av.getwidth()
173 lo = lo + i
174 hi = hi + j
175 elif op is SUBPATTERN:
176 i, j = av[1].getwidth()
177 lo = lo + i
178 hi = hi + j
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300179 elif op in _REPEATCODES:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000180 i, j = av[2].getwidth()
Serhiy Storchaka9d965422013-08-19 22:50:54 +0300181 lo = lo + i * av[0]
182 hi = hi + j * av[1]
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300183 elif op in _UNITCODES:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000184 lo = lo + 1
185 hi = hi + 1
Benjamin Peterson66323412014-11-30 11:49:00 -0500186 elif op == SUCCESS:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000187 break
Serhiy Storchaka9d965422013-08-19 22:50:54 +0300188 self.width = min(lo, MAXREPEAT - 1), min(hi, MAXREPEAT)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000189 return self.width
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000190
191class Tokenizer:
192 def __init__(self, string):
Antoine Pitrou463badf2012-06-23 13:29:19 +0200193 self.istext = isinstance(string, str)
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200194 self.string = string
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300195 if not self.istext:
196 string = str(string, 'latin1')
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200197 self.decoded_string = string
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000198 self.index = 0
Serhiy Storchakab99c1322014-11-10 14:38:16 +0200199 self.next = None
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000200 self.__next()
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000201 def __next(self):
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300202 index = self.index
203 try:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200204 char = self.decoded_string[index]
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300205 except IndexError:
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000206 self.next = None
207 return
Guido van Rossum75a902d2007-10-19 22:06:24 +0000208 if char == "\\":
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300209 index += 1
Fredrik Lundh90a07912000-06-30 07:50:59 +0000210 try:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200211 char += self.decoded_string[index]
Fredrik Lundh90a07912000-06-30 07:50:59 +0000212 except IndexError:
Serhiy Storchaka1b2004f2014-11-10 18:28:53 +0200213 raise error("bogus escape (end of line)",
214 self.string, len(self.string) - 1) from None
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300215 self.index = index + 1
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000216 self.next = char
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300217 def match(self, char):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000218 if char == self.next:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300219 self.__next()
220 return True
221 return False
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000222 def get(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000223 this = self.next
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000224 self.__next()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000225 return this
Antoine Pitrou463badf2012-06-23 13:29:19 +0200226 def getwhile(self, n, charset):
227 result = ''
228 for _ in range(n):
229 c = self.next
230 if c not in charset:
231 break
232 result += c
233 self.__next()
234 return result
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300235 def getuntil(self, terminator):
236 result = ''
237 while True:
238 c = self.next
239 self.__next()
240 if c is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200241 raise self.error("unterminated name")
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300242 if c == terminator:
243 break
244 result += c
245 return result
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000246 def tell(self):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200247 return self.index - len(self.next or '')
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000248 def seek(self, index):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200249 self.index = index
250 self.__next()
251
252 def error(self, msg, offset=0):
253 return error(msg, self.string, self.tell() - offset)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000254
Georg Brandl1d472b72013-04-14 11:40:00 +0200255# The following three functions are not used in this module anymore, but we keep
256# them here (with DeprecationWarnings) for backwards compatibility.
257
Fredrik Lundh4781b072000-06-29 12:38:45 +0000258def isident(char):
Georg Brandl1d472b72013-04-14 11:40:00 +0200259 import warnings
260 warnings.warn('sre_parse.isident() will be removed in 3.5',
261 DeprecationWarning, stacklevel=2)
Fredrik Lundh4781b072000-06-29 12:38:45 +0000262 return "a" <= char <= "z" or "A" <= char <= "Z" or char == "_"
263
264def isdigit(char):
Georg Brandl1d472b72013-04-14 11:40:00 +0200265 import warnings
266 warnings.warn('sre_parse.isdigit() will be removed in 3.5',
267 DeprecationWarning, stacklevel=2)
Fredrik Lundh4781b072000-06-29 12:38:45 +0000268 return "0" <= char <= "9"
269
270def isname(name):
Georg Brandl1d472b72013-04-14 11:40:00 +0200271 import warnings
272 warnings.warn('sre_parse.isname() will be removed in 3.5',
273 DeprecationWarning, stacklevel=2)
Fredrik Lundh4781b072000-06-29 12:38:45 +0000274 # check that group name is a valid string
Fredrik Lundh4781b072000-06-29 12:38:45 +0000275 if not isident(name[0]):
Guido van Rossum8ca162f2002-04-07 06:36:23 +0000276 return False
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000277 for char in name[1:]:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000278 if not isident(char) and not isdigit(char):
Guido van Rossum8ca162f2002-04-07 06:36:23 +0000279 return False
280 return True
Fredrik Lundh4781b072000-06-29 12:38:45 +0000281
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000282def _class_escape(source, escape):
283 # handle escape code inside character class
284 code = ESCAPES.get(escape)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000285 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000286 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000287 code = CATEGORIES.get(escape)
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300288 if code and code[0] is IN:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000289 return code
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000290 try:
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000291 c = escape[1:2]
292 if c == "x":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000293 # hexadecimal escape (exactly two digits)
Antoine Pitrou463badf2012-06-23 13:29:19 +0200294 escape += source.getwhile(2, HEXDIGITS)
295 if len(escape) != 4:
296 raise ValueError
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300297 return LITERAL, int(escape[2:], 16)
Antoine Pitrou463badf2012-06-23 13:29:19 +0200298 elif c == "u" and source.istext:
299 # unicode escape (exactly four digits)
300 escape += source.getwhile(4, HEXDIGITS)
301 if len(escape) != 6:
302 raise ValueError
303 return LITERAL, int(escape[2:], 16)
304 elif c == "U" and source.istext:
305 # unicode escape (exactly eight digits)
306 escape += source.getwhile(8, HEXDIGITS)
307 if len(escape) != 10:
308 raise ValueError
309 c = int(escape[2:], 16)
310 chr(c) # raise ValueError for invalid code
311 return LITERAL, c
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000312 elif c in OCTDIGITS:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000313 # octal escape (up to three digits)
Antoine Pitrou463badf2012-06-23 13:29:19 +0200314 escape += source.getwhile(2, OCTDIGITS)
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300315 c = int(escape[1:], 8)
316 if c > 0o377:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200317 raise source.error('octal escape value %r outside of '
318 'range 0-0o377' % escape, len(escape))
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300319 return LITERAL, c
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000320 elif c in DIGITS:
Antoine Pitrou463badf2012-06-23 13:29:19 +0200321 raise ValueError
Fredrik Lundh90a07912000-06-30 07:50:59 +0000322 if len(escape) == 2:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000323 return LITERAL, ord(escape[1])
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000324 except ValueError:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000325 pass
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200326 raise source.error("bogus escape: %r" % escape, len(escape))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000327
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000328def _escape(source, escape, state):
329 # handle escape code in expression
330 code = CATEGORIES.get(escape)
331 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000332 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000333 code = ESCAPES.get(escape)
334 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000335 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000336 try:
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000337 c = escape[1:2]
338 if c == "x":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000339 # hexadecimal escape
Antoine Pitrou463badf2012-06-23 13:29:19 +0200340 escape += source.getwhile(2, HEXDIGITS)
Fredrik Lundh143328b2000-09-02 11:03:34 +0000341 if len(escape) != 4:
342 raise ValueError
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300343 return LITERAL, int(escape[2:], 16)
Antoine Pitrou463badf2012-06-23 13:29:19 +0200344 elif c == "u" and source.istext:
345 # unicode escape (exactly four digits)
346 escape += source.getwhile(4, HEXDIGITS)
347 if len(escape) != 6:
348 raise ValueError
349 return LITERAL, int(escape[2:], 16)
350 elif c == "U" and source.istext:
351 # unicode escape (exactly eight digits)
352 escape += source.getwhile(8, HEXDIGITS)
353 if len(escape) != 10:
354 raise ValueError
355 c = int(escape[2:], 16)
356 chr(c) # raise ValueError for invalid code
357 return LITERAL, c
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000358 elif c == "0":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000359 # octal escape
Antoine Pitrou463badf2012-06-23 13:29:19 +0200360 escape += source.getwhile(2, OCTDIGITS)
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300361 return LITERAL, int(escape[1:], 8)
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000362 elif c in DIGITS:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000363 # octal escape *or* decimal group reference (sigh)
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000364 if source.next in DIGITS:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300365 escape += source.get()
Fredrik Lundh143328b2000-09-02 11:03:34 +0000366 if (escape[1] in OCTDIGITS and escape[2] in OCTDIGITS and
367 source.next in OCTDIGITS):
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000368 # got three octal digits; this is an octal escape
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300369 escape += source.get()
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300370 c = int(escape[1:], 8)
371 if c > 0o377:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200372 raise source.error('octal escape value %r outside of '
373 'range 0-0o377' % escape,
374 len(escape))
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300375 return LITERAL, c
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000376 # not an octal escape, so this is a group reference
377 group = int(escape[1:])
378 if group < state.groups:
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000379 if not state.checkgroup(group):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200380 raise source.error("cannot refer to open group",
381 len(escape))
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000382 return GROUPREF, group
Fredrik Lundh143328b2000-09-02 11:03:34 +0000383 raise ValueError
Fredrik Lundh90a07912000-06-30 07:50:59 +0000384 if len(escape) == 2:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000385 return LITERAL, ord(escape[1])
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000386 except ValueError:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000387 pass
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200388 raise source.error("bogus escape: %r" % escape, len(escape))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000389
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300390def _parse_sub(source, state, nested=True):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000391 # parse an alternation: a|b|c
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000392
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000393 items = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000394 itemsappend = items.append
395 sourcematch = source.match
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300396 while True:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000397 itemsappend(_parse(source, state))
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300398 if not sourcematch("|"):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000399 break
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300400 if nested and source.next is not None and source.next != ")":
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200401 raise source.error("pattern not properly closed")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000402
403 if len(items) == 1:
404 return items[0]
405
406 subpattern = SubPattern(state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000407 subpatternappend = subpattern.append
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000408
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000409 # check if all items share a common prefix
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300410 while True:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000411 prefix = None
412 for item in items:
413 if not item:
414 break
415 if prefix is None:
416 prefix = item[0]
417 elif item[0] != prefix:
418 break
419 else:
420 # all subitems start with a common "prefix".
421 # move it out of the branch
422 for item in items:
423 del item[0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000424 subpatternappend(prefix)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000425 continue # check next one
426 break
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000427
428 # check if the branch can be replaced by a character set
429 for item in items:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300430 if len(item) != 1 or item[0][0] is not LITERAL:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000431 break
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000432 else:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000433 # we can store this as a character set instead of a
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000434 # branch (the compiler may optimize this even more)
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300435 subpatternappend((IN, [item[0] for item in items]))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000436 return subpattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000437
438 subpattern.append((BRANCH, (None, items)))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000439 return subpattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000440
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000441def _parse_sub_cond(source, state, condgroup):
Tim Peters58eb11c2004-01-18 20:29:55 +0000442 item_yes = _parse(source, state)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000443 if source.match("|"):
Tim Peters58eb11c2004-01-18 20:29:55 +0000444 item_no = _parse(source, state)
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300445 if source.next == "|":
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200446 raise source.error("conditional backref with more than two branches")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000447 else:
448 item_no = None
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300449 if source.next is not None and source.next != ")":
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200450 raise source.error("pattern not properly closed")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000451 subpattern = SubPattern(state)
452 subpattern.append((GROUPREF_EXISTS, (condgroup, item_yes, item_no)))
453 return subpattern
454
Fredrik Lundh55a4f4a2000-06-30 22:37:31 +0000455def _parse(source, state):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000456 # parse a simple pattern
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000457 subpattern = SubPattern(state)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000458
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000459 # precompute constants into local variables
460 subpatternappend = subpattern.append
461 sourceget = source.get
462 sourcematch = source.match
463 _len = len
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300464 _ord = ord
465 verbose = state.flags & SRE_FLAG_VERBOSE
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000466
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300467 while True:
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000468
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300469 this = source.next
Fredrik Lundh90a07912000-06-30 07:50:59 +0000470 if this is None:
471 break # end of pattern
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300472 if this in "|)":
473 break # end of subpattern
474 sourceget()
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000475
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300476 if verbose:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000477 # skip whitespace and comments
478 if this in WHITESPACE:
479 continue
480 if this == "#":
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300481 while True:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000482 this = sourceget()
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300483 if this is None or this == "\n":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000484 break
485 continue
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000486
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300487 if this[0] == "\\":
488 code = _escape(source, this, state)
489 subpatternappend(code)
490
491 elif this not in SPECIAL_CHARS:
492 subpatternappend((LITERAL, _ord(this)))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000493
Fredrik Lundh90a07912000-06-30 07:50:59 +0000494 elif this == "[":
495 # character set
496 set = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000497 setappend = set.append
498## if sourcematch(":"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000499## pass # handle character classes
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000500 if sourcematch("^"):
501 setappend((NEGATE, None))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000502 # check remaining characters
503 start = set[:]
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300504 while True:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000505 this = sourceget()
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300506 if this is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200507 raise source.error("unexpected end of regular expression")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000508 if this == "]" and set != start:
509 break
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300510 elif this[0] == "\\":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000511 code1 = _class_escape(source, this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000512 else:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300513 code1 = LITERAL, _ord(this)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000514 if sourcematch("-"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000515 # potential range
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000516 this = sourceget()
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300517 if this is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200518 raise source.error("unexpected end of regular expression")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000519 if this == "]":
Fredrik Lundh025468d2000-10-07 10:16:19 +0000520 if code1[0] is IN:
521 code1 = code1[1][0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000522 setappend(code1)
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300523 setappend((LITERAL, _ord("-")))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000524 break
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300525 if this[0] == "\\":
526 code2 = _class_escape(source, this)
Guido van Rossum41c99e72003-04-14 17:59:34 +0000527 else:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300528 code2 = LITERAL, _ord(this)
529 if code1[0] != LITERAL or code2[0] != LITERAL:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200530 raise source.error("bad character range", len(this))
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300531 lo = code1[1]
532 hi = code2[1]
533 if hi < lo:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200534 raise source.error("bad character range", len(this))
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300535 setappend((RANGE, (lo, hi)))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000536 else:
537 if code1[0] is IN:
538 code1 = code1[1][0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000539 setappend(code1)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000540
Fredrik Lundh770617b2001-01-14 15:06:11 +0000541 # XXX: <fl> should move set optimization to compiler!
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000542 if _len(set)==1 and set[0][0] is LITERAL:
543 subpatternappend(set[0]) # optimization
544 elif _len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL:
545 subpatternappend((NOT_LITERAL, set[1][1])) # optimization
Fredrik Lundh90a07912000-06-30 07:50:59 +0000546 else:
Fredrik Lundh770617b2001-01-14 15:06:11 +0000547 # XXX: <fl> should add charmap optimization here
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000548 subpatternappend((IN, set))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000549
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300550 elif this in REPEAT_CHARS:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000551 # repeat previous item
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200552 here = source.tell()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000553 if this == "?":
554 min, max = 0, 1
555 elif this == "*":
556 min, max = 0, MAXREPEAT
Fredrik Lundhc0c7ee32001-02-18 21:04:48 +0000557
Fredrik Lundh90a07912000-06-30 07:50:59 +0000558 elif this == "+":
559 min, max = 1, MAXREPEAT
560 elif this == "{":
Gustavo Niemeyer6fa0c5a2005-09-14 08:54:39 +0000561 if source.next == "}":
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300562 subpatternappend((LITERAL, _ord(this)))
Gustavo Niemeyer6fa0c5a2005-09-14 08:54:39 +0000563 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000564 min, max = 0, MAXREPEAT
565 lo = hi = ""
566 while source.next in DIGITS:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300567 lo += sourceget()
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000568 if sourcematch(","):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000569 while source.next in DIGITS:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300570 hi += sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000571 else:
572 hi = lo
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000573 if not sourcematch("}"):
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300574 subpatternappend((LITERAL, _ord(this)))
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000575 source.seek(here)
576 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000577 if lo:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000578 min = int(lo)
Serhiy Storchaka70ca0212013-02-16 16:47:47 +0200579 if min >= MAXREPEAT:
580 raise OverflowError("the repetition number is too large")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000581 if hi:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000582 max = int(hi)
Serhiy Storchaka70ca0212013-02-16 16:47:47 +0200583 if max >= MAXREPEAT:
584 raise OverflowError("the repetition number is too large")
585 if max < min:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200586 raise source.error("bad repeat interval",
587 source.tell() - here)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000588 else:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200589 raise source.error("not supported", len(this))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000590 # figure out which item to repeat
591 if subpattern:
592 item = subpattern[-1:]
593 else:
Fredrik Lundhc0c7ee32001-02-18 21:04:48 +0000594 item = None
Serhiy Storchakaab140882014-11-11 21:13:28 +0200595 if not item or (_len(item) == 1 and item[0][0] is AT):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200596 raise source.error("nothing to repeat",
597 source.tell() - here + len(this))
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300598 if item[0][0] in _REPEATCODES:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200599 raise source.error("multiple repeat",
600 source.tell() - here + len(this))
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000601 if sourcematch("?"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000602 subpattern[-1] = (MIN_REPEAT, (min, max, item))
603 else:
604 subpattern[-1] = (MAX_REPEAT, (min, max, item))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000605
Fredrik Lundh90a07912000-06-30 07:50:59 +0000606 elif this == ".":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000607 subpatternappend((ANY, None))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000608
Fredrik Lundh90a07912000-06-30 07:50:59 +0000609 elif this == "(":
610 group = 1
611 name = None
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000612 condgroup = None
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000613 if sourcematch("?"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000614 group = 0
615 # options
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300616 char = sourceget()
617 if char is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200618 raise self.error("unexpected end of pattern")
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300619 if char == "P":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000620 # python extensions
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000621 if sourcematch("<"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000622 # named group: skip forward to end of name
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300623 name = source.getuntil(">")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000624 group = 1
Ezio Melotti0941d9f2012-11-03 20:33:08 +0200625 if not name:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200626 raise source.error("missing group name", 1)
Georg Brandl1d472b72013-04-14 11:40:00 +0200627 if not name.isidentifier():
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200628 raise source.error("bad character in group name "
629 "%r" % name,
630 len(name) + 1)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000631 elif sourcematch("="):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000632 # named backreference
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300633 name = source.getuntil(")")
Ezio Melotti0941d9f2012-11-03 20:33:08 +0200634 if not name:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200635 raise source.error("missing group name", 1)
Georg Brandl1d472b72013-04-14 11:40:00 +0200636 if not name.isidentifier():
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200637 raise source.error("bad character in backref "
638 "group name %r" % name,
639 len(name) + 1)
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000640 gid = state.groupdict.get(name)
641 if gid is None:
Raymond Hettinger1c99bc82014-06-22 19:47:22 -0700642 msg = "unknown group name: {0!r}".format(name)
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200643 raise source.error(msg, len(name) + 1)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000644 subpatternappend((GROUPREF, gid))
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000645 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000646 else:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000647 char = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000648 if char is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200649 raise source.error("unexpected end of pattern")
650 raise source.error("unknown specifier: ?P%s" % char,
651 len(char))
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300652 elif char == ":":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000653 # non-capturing group
654 group = 2
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300655 elif char == "#":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000656 # comment
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300657 while True:
658 if source.next is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200659 raise source.error("unbalanced parenthesis")
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300660 if sourceget() == ")":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000661 break
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000662 continue
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300663 elif char in "=!<":
Fredrik Lundh43b3b492000-06-30 10:41:31 +0000664 # lookahead assertions
Fredrik Lundh6f013982000-07-03 18:44:21 +0000665 dir = 1
666 if char == "<":
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300667 char = sourceget()
668 if char is None or char not in "=!":
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200669 raise source.error("syntax error")
Fredrik Lundh6f013982000-07-03 18:44:21 +0000670 dir = -1 # lookbehind
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000671 p = _parse_sub(source, state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000672 if not sourcematch(")"):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200673 raise source.error("unbalanced parenthesis")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000674 if char == "=":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000675 subpatternappend((ASSERT, (dir, p)))
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000676 else:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000677 subpatternappend((ASSERT_NOT, (dir, p)))
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000678 continue
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300679 elif char == "(":
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000680 # conditional backreference group
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300681 condname = source.getuntil(")")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000682 group = 2
Ezio Melotti0941d9f2012-11-03 20:33:08 +0200683 if not condname:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200684 raise source.error("missing group name", 1)
Georg Brandl1d472b72013-04-14 11:40:00 +0200685 if condname.isidentifier():
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000686 condgroup = state.groupdict.get(condname)
687 if condgroup is None:
Raymond Hettinger1c99bc82014-06-22 19:47:22 -0700688 msg = "unknown group name: {0!r}".format(condname)
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200689 raise source.error(msg, len(condname) + 1)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000690 else:
691 try:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000692 condgroup = int(condname)
Serhiy Storchaka9baa5b22014-09-29 22:49:23 +0300693 if condgroup < 0:
694 raise ValueError
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000695 except ValueError:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200696 raise source.error("bad character in group name",
697 len(condname) + 1)
Serhiy Storchaka9baa5b22014-09-29 22:49:23 +0300698 if not condgroup:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200699 raise source.error("bad group number",
700 len(condname) + 1)
Serhiy Storchaka9baa5b22014-09-29 22:49:23 +0300701 if condgroup >= MAXGROUPS:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200702 raise source.error("the group number is too large",
703 len(condname) + 1)
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300704 elif char in FLAGS:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000705 # flags
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300706 state.flags |= FLAGS[char]
Raymond Hettinger54f02222002-06-01 14:18:47 +0000707 while source.next in FLAGS:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300708 state.flags |= FLAGS[sourceget()]
709 verbose = state.flags & SRE_FLAG_VERBOSE
710 else:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200711 raise source.error("unexpected end of pattern")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000712 if group:
713 # parse group contents
Fredrik Lundh90a07912000-06-30 07:50:59 +0000714 if group == 2:
715 # anonymous group
716 group = None
717 else:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200718 try:
719 group = state.opengroup(name)
720 except error as err:
721 raise source.error(err.msg, len(name) + 1)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000722 if condgroup:
723 p = _parse_sub_cond(source, state, condgroup)
724 else:
725 p = _parse_sub(source, state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000726 if not sourcematch(")"):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200727 raise source.error("unbalanced parenthesis")
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000728 if group is not None:
Benjamin Peterson66323412014-11-30 11:49:00 -0500729 state.closegroup(group)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000730 subpatternappend((SUBPATTERN, (group, p)))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000731 else:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300732 while True:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000733 char = sourceget()
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000734 if char is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200735 raise source.error("unexpected end of pattern")
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000736 if char == ")":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000737 break
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200738 raise source.error("unknown extension", len(char))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000739
Fredrik Lundh90a07912000-06-30 07:50:59 +0000740 elif this == "^":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000741 subpatternappend((AT, AT_BEGINNING))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000742
Fredrik Lundh90a07912000-06-30 07:50:59 +0000743 elif this == "$":
744 subpattern.append((AT, AT_END))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000745
Fredrik Lundh90a07912000-06-30 07:50:59 +0000746 else:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200747 raise source.error("parser error", len(this))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000748
749 return subpattern
750
Antoine Pitroufd036452008-08-19 17:56:33 +0000751def fix_flags(src, flags):
752 # Check and fix flags according to the type of pattern (str or bytes)
753 if isinstance(src, str):
Serhiy Storchaka22a309a2014-12-01 11:50:07 +0200754 if flags & SRE_FLAG_LOCALE:
755 import warnings
756 warnings.warn("LOCALE flag with a str pattern is deprecated. "
757 "Will be an error in 3.6",
758 DeprecationWarning, stacklevel=6)
Antoine Pitroufd036452008-08-19 17:56:33 +0000759 if not flags & SRE_FLAG_ASCII:
760 flags |= SRE_FLAG_UNICODE
761 elif flags & SRE_FLAG_UNICODE:
762 raise ValueError("ASCII and UNICODE flags are incompatible")
763 else:
764 if flags & SRE_FLAG_UNICODE:
765 raise ValueError("can't use UNICODE flag with a bytes pattern")
Serhiy Storchaka22a309a2014-12-01 11:50:07 +0200766 if flags & SRE_FLAG_LOCALE and flags & SRE_FLAG_ASCII:
767 import warnings
768 warnings.warn("ASCII and LOCALE flags are incompatible. "
769 "Will be an error in 3.6",
770 DeprecationWarning, stacklevel=6)
Antoine Pitroufd036452008-08-19 17:56:33 +0000771 return flags
772
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000773def parse(str, flags=0, pattern=None):
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000774 # parse 're' pattern into list of (opcode, argument) tuples
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000775
776 source = Tokenizer(str)
777
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000778 if pattern is None:
779 pattern = Pattern()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000780 pattern.flags = flags
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000781 pattern.str = str
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000782
783 p = _parse_sub(source, pattern, 0)
Antoine Pitroufd036452008-08-19 17:56:33 +0000784 p.pattern.flags = fix_flags(str, p.pattern.flags)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000785
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300786 if source.next is not None:
787 if source.next == ")":
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200788 raise source.error("unbalanced parenthesis")
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300789 else:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200790 raise source.error("bogus characters at end of regular expression",
791 len(tail))
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000792
Fredrik Lundh770617b2001-01-14 15:06:11 +0000793 if flags & SRE_FLAG_DEBUG:
794 p.dump()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000795
Fredrik Lundhd11b5e52000-10-03 19:22:26 +0000796 if not (flags & SRE_FLAG_VERBOSE) and p.pattern.flags & SRE_FLAG_VERBOSE:
797 # the VERBOSE flag was switched on inside the pattern. to be
798 # on the safe side, we'll parse the whole thing again...
799 return parse(str, p.pattern.flags)
800
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000801 return p
802
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000803def parse_template(source, pattern):
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000804 # parse 're' replacement string into list of literals and
805 # group references
806 s = Tokenizer(source)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000807 sget = s.get
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300808 groups = []
809 literals = []
810 literal = []
811 lappend = literal.append
812 def addgroup(index):
813 if literal:
814 literals.append(''.join(literal))
815 del literal[:]
816 groups.append((len(literals), index))
817 literals.append(None)
818 while True:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000819 this = sget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000820 if this is None:
821 break # end of replacement string
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300822 if this[0] == "\\":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000823 # group
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300824 c = this[1]
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000825 if c == "g":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000826 name = ""
827 if s.match("<"):
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300828 name = s.getuntil(">")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000829 if not name:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200830 raise s.error("missing group name", 1)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000831 try:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000832 index = int(name)
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000833 if index < 0:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200834 raise s.error("negative group number", len(name) + 1)
Serhiy Storchaka9baa5b22014-09-29 22:49:23 +0300835 if index >= MAXGROUPS:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200836 raise s.error("the group number is too large",
837 len(name) + 1)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000838 except ValueError:
Georg Brandl1d472b72013-04-14 11:40:00 +0200839 if not name.isidentifier():
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200840 raise s.error("bad character in group name",
841 len(name) + 1)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000842 try:
843 index = pattern.groupindex[name]
844 except KeyError:
Raymond Hettinger1c99bc82014-06-22 19:47:22 -0700845 msg = "unknown group name: {0!r}".format(name)
846 raise IndexError(msg)
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300847 addgroup(index)
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000848 elif c == "0":
849 if s.next in OCTDIGITS:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300850 this += sget()
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000851 if s.next in OCTDIGITS:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300852 this += sget()
853 lappend(chr(int(this[1:], 8) & 0xff))
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000854 elif c in DIGITS:
855 isoctal = False
856 if s.next in DIGITS:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300857 this += sget()
Gustavo Niemeyerf5a15992004-09-03 20:15:56 +0000858 if (c in OCTDIGITS and this[2] in OCTDIGITS and
859 s.next in OCTDIGITS):
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300860 this += sget()
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000861 isoctal = True
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300862 c = int(this[1:], 8)
863 if c > 0o377:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200864 raise s.error('octal escape value %r outside of '
865 'range 0-0o377' % this, len(this))
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300866 lappend(chr(c))
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000867 if not isoctal:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300868 addgroup(int(this[1:]))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000869 else:
870 try:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300871 this = chr(ESCAPES[this][1])
Fredrik Lundh90a07912000-06-30 07:50:59 +0000872 except KeyError:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000873 pass
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300874 lappend(this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000875 else:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300876 lappend(this)
877 if literal:
878 literals.append(''.join(literal))
879 if not isinstance(source, str):
Ezio Melottib92ed7c2010-03-06 15:24:08 +0000880 # The tokenizer implicitly decodes bytes objects as latin-1, we must
881 # therefore re-encode the final representation.
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300882 literals = [None if s is None else s.encode('latin-1') for s in literals]
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000883 return groups, literals
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000884
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000885def expand_template(template, match):
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000886 g = match.group
Serhiy Storchaka7438e4b2014-10-10 11:06:31 +0300887 empty = match.string[:0]
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000888 groups, literals = template
889 literals = literals[:]
890 try:
891 for index, group in groups:
Serhiy Storchaka7438e4b2014-10-10 11:06:31 +0300892 literals[index] = g(group) or empty
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000893 except IndexError:
Collin Winterce36ad82007-08-30 01:19:48 +0000894 raise error("invalid group reference")
Serhiy Storchaka7438e4b2014-10-10 11:06:31 +0300895 return empty.join(literals)