blob: fb622ec2357bee028715f5c76a05d42a0ed225a9 [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
Fredrik Lundh90a07912000-06-30 07:50:59 +000071 self.groupdict = {}
Serhiy Storchaka84df7fe2014-11-07 21:43:57 +020072 self.subpatterns = [None] # group 0
73 @property
74 def groups(self):
75 return len(self.subpatterns)
Fredrik Lundhebc37b22000-10-28 19:30:41 +000076 def opengroup(self, name=None):
Fredrik Lundh90a07912000-06-30 07:50:59 +000077 gid = self.groups
Serhiy Storchaka84df7fe2014-11-07 21:43:57 +020078 self.subpatterns.append(None)
Serhiy Storchaka9baa5b22014-09-29 22:49:23 +030079 if self.groups > MAXGROUPS:
80 raise error("groups number is too large")
Raymond Hettingerf13eb552002-06-02 00:40:05 +000081 if name is not None:
Tim Peters75335872001-11-03 19:35:43 +000082 ogid = self.groupdict.get(name, None)
83 if ogid is not None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +020084 raise error("redefinition of group name %r as group %d; "
85 "was group %d" % (name, gid, ogid))
Fredrik Lundh90a07912000-06-30 07:50:59 +000086 self.groupdict[name] = gid
87 return gid
Serhiy Storchaka84df7fe2014-11-07 21:43:57 +020088 def closegroup(self, gid, p):
89 self.subpatterns[gid] = p
Fredrik Lundhebc37b22000-10-28 19:30:41 +000090 def checkgroup(self, gid):
Serhiy Storchaka84df7fe2014-11-07 21:43:57 +020091 return gid < self.groups and self.subpatterns[gid] is not None
Guido van Rossum7627c0d2000-03-31 14:58:54 +000092
93class SubPattern:
94 # a subpattern, in intermediate form
95 def __init__(self, pattern, data=None):
Fredrik Lundh90a07912000-06-30 07:50:59 +000096 self.pattern = pattern
Raymond Hettingerf13eb552002-06-02 00:40:05 +000097 if data is None:
Fredrik Lundh90a07912000-06-30 07:50:59 +000098 data = []
99 self.data = data
100 self.width = None
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000101 def dump(self, level=0):
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300102 nl = True
Guido van Rossum13257902007-06-07 23:15:56 +0000103 seqtypes = (tuple, list)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000104 for op, av in self.data:
Serhiy Storchakac7f7d382014-11-09 20:48:36 +0200105 print(level*" " + str(op), end='')
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300106 if op == IN:
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000107 # member sublanguage
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300108 print()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000109 for op, a in av:
Serhiy Storchakac7f7d382014-11-09 20:48:36 +0200110 print((level+1)*" " + str(op), a)
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300111 elif op == BRANCH:
112 print()
113 for i, a in enumerate(av[1]):
114 if i:
Serhiy Storchakac7f7d382014-11-09 20:48:36 +0200115 print(level*" " + "OR")
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300116 a.dump(level+1)
117 elif op == GROUPREF_EXISTS:
118 condgroup, item_yes, item_no = av
119 print('', condgroup)
120 item_yes.dump(level+1)
121 if item_no:
Serhiy Storchakac7f7d382014-11-09 20:48:36 +0200122 print(level*" " + "ELSE")
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300123 item_no.dump(level+1)
Guido van Rossum13257902007-06-07 23:15:56 +0000124 elif isinstance(av, seqtypes):
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300125 nl = False
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000126 for a in av:
127 if isinstance(a, SubPattern):
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300128 if not nl:
129 print()
130 a.dump(level+1)
131 nl = True
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000132 else:
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300133 if not nl:
134 print(' ', end='')
135 print(a, end='')
136 nl = False
137 if not nl:
138 print()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000139 else:
Serhiy Storchaka44dae8b2014-09-21 22:47:55 +0300140 print('', av)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000141 def __repr__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000142 return repr(self.data)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000143 def __len__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000144 return len(self.data)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000145 def __delitem__(self, index):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000146 del self.data[index]
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000147 def __getitem__(self, index):
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000148 if isinstance(index, slice):
149 return SubPattern(self.pattern, self.data[index])
Fredrik Lundh90a07912000-06-30 07:50:59 +0000150 return self.data[index]
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000151 def __setitem__(self, index, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000152 self.data[index] = code
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000153 def insert(self, index, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000154 self.data.insert(index, code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000155 def append(self, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000156 self.data.append(code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000157 def getwidth(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000158 # determine the width (min, max) for this subpattern
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300159 if self.width is not None:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000160 return self.width
Guido van Rossume2a383d2007-01-15 16:59:06 +0000161 lo = hi = 0
Fredrik Lundh90a07912000-06-30 07:50:59 +0000162 for op, av in self.data:
163 if op is BRANCH:
Serhiy Storchaka9d965422013-08-19 22:50:54 +0300164 i = MAXREPEAT - 1
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000165 j = 0
Fredrik Lundh90a07912000-06-30 07:50:59 +0000166 for av in av[1]:
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000167 l, h = av.getwidth()
168 i = min(i, l)
Fredrik Lundhe1869832000-08-01 22:47:49 +0000169 j = max(j, h)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000170 lo = lo + i
171 hi = hi + j
172 elif op is CALL:
173 i, j = av.getwidth()
174 lo = lo + i
175 hi = hi + j
176 elif op is SUBPATTERN:
177 i, j = av[1].getwidth()
178 lo = lo + i
179 hi = hi + j
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300180 elif op in _REPEATCODES:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000181 i, j = av[2].getwidth()
Serhiy Storchaka9d965422013-08-19 22:50:54 +0300182 lo = lo + i * av[0]
183 hi = hi + j * av[1]
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300184 elif op in _UNITCODES:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000185 lo = lo + 1
186 hi = hi + 1
Serhiy Storchaka84df7fe2014-11-07 21:43:57 +0200187 elif op is GROUPREF:
188 i, j = self.pattern.subpatterns[av].getwidth()
189 lo = lo + i
190 hi = hi + j
191 elif op is GROUPREF_EXISTS:
192 i, j = av[1].getwidth()
193 if av[2] is not None:
194 l, h = av[2].getwidth()
195 i = min(i, l)
196 j = max(j, h)
197 else:
198 i = 0
199 lo = lo + i
200 hi = hi + j
201 elif op is SUCCESS:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000202 break
Serhiy Storchaka9d965422013-08-19 22:50:54 +0300203 self.width = min(lo, MAXREPEAT - 1), min(hi, MAXREPEAT)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000204 return self.width
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000205
206class Tokenizer:
207 def __init__(self, string):
Antoine Pitrou463badf2012-06-23 13:29:19 +0200208 self.istext = isinstance(string, str)
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200209 self.string = string
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300210 if not self.istext:
211 string = str(string, 'latin1')
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200212 self.decoded_string = string
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000213 self.index = 0
Serhiy Storchakab99c1322014-11-10 14:38:16 +0200214 self.next = None
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000215 self.__next()
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000216 def __next(self):
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300217 index = self.index
218 try:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200219 char = self.decoded_string[index]
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300220 except IndexError:
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000221 self.next = None
222 return
Guido van Rossum75a902d2007-10-19 22:06:24 +0000223 if char == "\\":
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300224 index += 1
Fredrik Lundh90a07912000-06-30 07:50:59 +0000225 try:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200226 char += self.decoded_string[index]
Fredrik Lundh90a07912000-06-30 07:50:59 +0000227 except IndexError:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200228 raise self.error("bogus escape (end of line)") from None
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300229 self.index = index + 1
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000230 self.next = char
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300231 def match(self, char):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000232 if char == self.next:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300233 self.__next()
234 return True
235 return False
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000236 def get(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000237 this = self.next
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000238 self.__next()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000239 return this
Antoine Pitrou463badf2012-06-23 13:29:19 +0200240 def getwhile(self, n, charset):
241 result = ''
242 for _ in range(n):
243 c = self.next
244 if c not in charset:
245 break
246 result += c
247 self.__next()
248 return result
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300249 def getuntil(self, terminator):
250 result = ''
251 while True:
252 c = self.next
253 self.__next()
254 if c is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200255 raise self.error("unterminated name")
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300256 if c == terminator:
257 break
258 result += c
259 return result
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000260 def tell(self):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200261 return self.index - len(self.next or '')
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000262 def seek(self, index):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200263 self.index = index
264 self.__next()
265
266 def error(self, msg, offset=0):
267 return error(msg, self.string, self.tell() - offset)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000268
Georg Brandl1d472b72013-04-14 11:40:00 +0200269# The following three functions are not used in this module anymore, but we keep
270# them here (with DeprecationWarnings) for backwards compatibility.
271
Fredrik Lundh4781b072000-06-29 12:38:45 +0000272def isident(char):
Georg Brandl1d472b72013-04-14 11:40:00 +0200273 import warnings
274 warnings.warn('sre_parse.isident() will be removed in 3.5',
275 DeprecationWarning, stacklevel=2)
Fredrik Lundh4781b072000-06-29 12:38:45 +0000276 return "a" <= char <= "z" or "A" <= char <= "Z" or char == "_"
277
278def isdigit(char):
Georg Brandl1d472b72013-04-14 11:40:00 +0200279 import warnings
280 warnings.warn('sre_parse.isdigit() will be removed in 3.5',
281 DeprecationWarning, stacklevel=2)
Fredrik Lundh4781b072000-06-29 12:38:45 +0000282 return "0" <= char <= "9"
283
284def isname(name):
Georg Brandl1d472b72013-04-14 11:40:00 +0200285 import warnings
286 warnings.warn('sre_parse.isname() will be removed in 3.5',
287 DeprecationWarning, stacklevel=2)
Fredrik Lundh4781b072000-06-29 12:38:45 +0000288 # check that group name is a valid string
Fredrik Lundh4781b072000-06-29 12:38:45 +0000289 if not isident(name[0]):
Guido van Rossum8ca162f2002-04-07 06:36:23 +0000290 return False
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000291 for char in name[1:]:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000292 if not isident(char) and not isdigit(char):
Guido van Rossum8ca162f2002-04-07 06:36:23 +0000293 return False
294 return True
Fredrik Lundh4781b072000-06-29 12:38:45 +0000295
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000296def _class_escape(source, escape):
297 # handle escape code inside character class
298 code = ESCAPES.get(escape)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000299 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000300 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000301 code = CATEGORIES.get(escape)
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300302 if code and code[0] is IN:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000303 return code
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000304 try:
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000305 c = escape[1:2]
306 if c == "x":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000307 # hexadecimal escape (exactly two digits)
Antoine Pitrou463badf2012-06-23 13:29:19 +0200308 escape += source.getwhile(2, HEXDIGITS)
309 if len(escape) != 4:
310 raise ValueError
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300311 return LITERAL, int(escape[2:], 16)
Antoine Pitrou463badf2012-06-23 13:29:19 +0200312 elif c == "u" and source.istext:
313 # unicode escape (exactly four digits)
314 escape += source.getwhile(4, HEXDIGITS)
315 if len(escape) != 6:
316 raise ValueError
317 return LITERAL, int(escape[2:], 16)
318 elif c == "U" and source.istext:
319 # unicode escape (exactly eight digits)
320 escape += source.getwhile(8, HEXDIGITS)
321 if len(escape) != 10:
322 raise ValueError
323 c = int(escape[2:], 16)
324 chr(c) # raise ValueError for invalid code
325 return LITERAL, c
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000326 elif c in OCTDIGITS:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000327 # octal escape (up to three digits)
Antoine Pitrou463badf2012-06-23 13:29:19 +0200328 escape += source.getwhile(2, OCTDIGITS)
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300329 c = int(escape[1:], 8)
330 if c > 0o377:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200331 raise source.error('octal escape value %r outside of '
332 'range 0-0o377' % escape, len(escape))
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300333 return LITERAL, c
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000334 elif c in DIGITS:
Antoine Pitrou463badf2012-06-23 13:29:19 +0200335 raise ValueError
Fredrik Lundh90a07912000-06-30 07:50:59 +0000336 if len(escape) == 2:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000337 return LITERAL, ord(escape[1])
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000338 except ValueError:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000339 pass
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200340 raise source.error("bogus escape: %r" % escape, len(escape))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000341
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000342def _escape(source, escape, state):
343 # handle escape code in expression
344 code = CATEGORIES.get(escape)
345 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000346 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000347 code = ESCAPES.get(escape)
348 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000349 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000350 try:
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000351 c = escape[1:2]
352 if c == "x":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000353 # hexadecimal escape
Antoine Pitrou463badf2012-06-23 13:29:19 +0200354 escape += source.getwhile(2, HEXDIGITS)
Fredrik Lundh143328b2000-09-02 11:03:34 +0000355 if len(escape) != 4:
356 raise ValueError
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300357 return LITERAL, int(escape[2:], 16)
Antoine Pitrou463badf2012-06-23 13:29:19 +0200358 elif c == "u" and source.istext:
359 # unicode escape (exactly four digits)
360 escape += source.getwhile(4, HEXDIGITS)
361 if len(escape) != 6:
362 raise ValueError
363 return LITERAL, int(escape[2:], 16)
364 elif c == "U" and source.istext:
365 # unicode escape (exactly eight digits)
366 escape += source.getwhile(8, HEXDIGITS)
367 if len(escape) != 10:
368 raise ValueError
369 c = int(escape[2:], 16)
370 chr(c) # raise ValueError for invalid code
371 return LITERAL, c
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000372 elif c == "0":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000373 # octal escape
Antoine Pitrou463badf2012-06-23 13:29:19 +0200374 escape += source.getwhile(2, OCTDIGITS)
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300375 return LITERAL, int(escape[1:], 8)
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000376 elif c in DIGITS:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000377 # octal escape *or* decimal group reference (sigh)
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000378 if source.next in DIGITS:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300379 escape += source.get()
Fredrik Lundh143328b2000-09-02 11:03:34 +0000380 if (escape[1] in OCTDIGITS and escape[2] in OCTDIGITS and
381 source.next in OCTDIGITS):
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000382 # got three octal digits; this is an octal escape
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300383 escape += source.get()
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300384 c = int(escape[1:], 8)
385 if c > 0o377:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200386 raise source.error('octal escape value %r outside of '
387 'range 0-0o377' % escape,
388 len(escape))
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300389 return LITERAL, c
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000390 # not an octal escape, so this is a group reference
391 group = int(escape[1:])
392 if group < state.groups:
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000393 if not state.checkgroup(group):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200394 raise source.error("cannot refer to open group",
395 len(escape))
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000396 return GROUPREF, group
Fredrik Lundh143328b2000-09-02 11:03:34 +0000397 raise ValueError
Fredrik Lundh90a07912000-06-30 07:50:59 +0000398 if len(escape) == 2:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000399 return LITERAL, ord(escape[1])
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000400 except ValueError:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000401 pass
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200402 raise source.error("bogus escape: %r" % escape, len(escape))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000403
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300404def _parse_sub(source, state, nested=True):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000405 # parse an alternation: a|b|c
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000406
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000407 items = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000408 itemsappend = items.append
409 sourcematch = source.match
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300410 while True:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000411 itemsappend(_parse(source, state))
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300412 if not sourcematch("|"):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000413 break
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300414 if nested and source.next is not None and source.next != ")":
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200415 raise source.error("pattern not properly closed")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000416
417 if len(items) == 1:
418 return items[0]
419
420 subpattern = SubPattern(state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000421 subpatternappend = subpattern.append
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000422
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000423 # check if all items share a common prefix
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300424 while True:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000425 prefix = None
426 for item in items:
427 if not item:
428 break
429 if prefix is None:
430 prefix = item[0]
431 elif item[0] != prefix:
432 break
433 else:
434 # all subitems start with a common "prefix".
435 # move it out of the branch
436 for item in items:
437 del item[0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000438 subpatternappend(prefix)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000439 continue # check next one
440 break
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000441
442 # check if the branch can be replaced by a character set
443 for item in items:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300444 if len(item) != 1 or item[0][0] is not LITERAL:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000445 break
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000446 else:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000447 # we can store this as a character set instead of a
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000448 # branch (the compiler may optimize this even more)
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300449 subpatternappend((IN, [item[0] for item in items]))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000450 return subpattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000451
452 subpattern.append((BRANCH, (None, items)))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000453 return subpattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000454
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000455def _parse_sub_cond(source, state, condgroup):
Tim Peters58eb11c2004-01-18 20:29:55 +0000456 item_yes = _parse(source, state)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000457 if source.match("|"):
Tim Peters58eb11c2004-01-18 20:29:55 +0000458 item_no = _parse(source, state)
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300459 if source.next == "|":
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200460 raise source.error("conditional backref with more than two branches")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000461 else:
462 item_no = None
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300463 if source.next is not None and source.next != ")":
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200464 raise source.error("pattern not properly closed")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000465 subpattern = SubPattern(state)
466 subpattern.append((GROUPREF_EXISTS, (condgroup, item_yes, item_no)))
467 return subpattern
468
Fredrik Lundh55a4f4a2000-06-30 22:37:31 +0000469def _parse(source, state):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000470 # parse a simple pattern
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000471 subpattern = SubPattern(state)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000472
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000473 # precompute constants into local variables
474 subpatternappend = subpattern.append
475 sourceget = source.get
476 sourcematch = source.match
477 _len = len
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300478 _ord = ord
479 verbose = state.flags & SRE_FLAG_VERBOSE
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000480
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300481 while True:
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000482
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300483 this = source.next
Fredrik Lundh90a07912000-06-30 07:50:59 +0000484 if this is None:
485 break # end of pattern
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300486 if this in "|)":
487 break # end of subpattern
488 sourceget()
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000489
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300490 if verbose:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000491 # skip whitespace and comments
492 if this in WHITESPACE:
493 continue
494 if this == "#":
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300495 while True:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000496 this = sourceget()
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300497 if this is None or this == "\n":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000498 break
499 continue
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000500
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300501 if this[0] == "\\":
502 code = _escape(source, this, state)
503 subpatternappend(code)
504
505 elif this not in SPECIAL_CHARS:
506 subpatternappend((LITERAL, _ord(this)))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000507
Fredrik Lundh90a07912000-06-30 07:50:59 +0000508 elif this == "[":
509 # character set
510 set = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000511 setappend = set.append
512## if sourcematch(":"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000513## pass # handle character classes
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000514 if sourcematch("^"):
515 setappend((NEGATE, None))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000516 # check remaining characters
517 start = set[:]
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300518 while True:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000519 this = sourceget()
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300520 if this is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200521 raise source.error("unexpected end of regular expression")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000522 if this == "]" and set != start:
523 break
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300524 elif this[0] == "\\":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000525 code1 = _class_escape(source, this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000526 else:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300527 code1 = LITERAL, _ord(this)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000528 if sourcematch("-"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000529 # potential range
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000530 this = sourceget()
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300531 if this is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200532 raise source.error("unexpected end of regular expression")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000533 if this == "]":
Fredrik Lundh025468d2000-10-07 10:16:19 +0000534 if code1[0] is IN:
535 code1 = code1[1][0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000536 setappend(code1)
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300537 setappend((LITERAL, _ord("-")))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000538 break
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300539 if this[0] == "\\":
540 code2 = _class_escape(source, this)
Guido van Rossum41c99e72003-04-14 17:59:34 +0000541 else:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300542 code2 = LITERAL, _ord(this)
543 if code1[0] != LITERAL or code2[0] != LITERAL:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200544 raise source.error("bad character range", len(this))
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300545 lo = code1[1]
546 hi = code2[1]
547 if hi < lo:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200548 raise source.error("bad character range", len(this))
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300549 setappend((RANGE, (lo, hi)))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000550 else:
551 if code1[0] is IN:
552 code1 = code1[1][0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000553 setappend(code1)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000554
Fredrik Lundh770617b2001-01-14 15:06:11 +0000555 # XXX: <fl> should move set optimization to compiler!
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000556 if _len(set)==1 and set[0][0] is LITERAL:
557 subpatternappend(set[0]) # optimization
558 elif _len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL:
559 subpatternappend((NOT_LITERAL, set[1][1])) # optimization
Fredrik Lundh90a07912000-06-30 07:50:59 +0000560 else:
Fredrik Lundh770617b2001-01-14 15:06:11 +0000561 # XXX: <fl> should add charmap optimization here
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000562 subpatternappend((IN, set))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000563
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300564 elif this in REPEAT_CHARS:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000565 # repeat previous item
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200566 here = source.tell()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000567 if this == "?":
568 min, max = 0, 1
569 elif this == "*":
570 min, max = 0, MAXREPEAT
Fredrik Lundhc0c7ee32001-02-18 21:04:48 +0000571
Fredrik Lundh90a07912000-06-30 07:50:59 +0000572 elif this == "+":
573 min, max = 1, MAXREPEAT
574 elif this == "{":
Gustavo Niemeyer6fa0c5a2005-09-14 08:54:39 +0000575 if source.next == "}":
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300576 subpatternappend((LITERAL, _ord(this)))
Gustavo Niemeyer6fa0c5a2005-09-14 08:54:39 +0000577 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000578 min, max = 0, MAXREPEAT
579 lo = hi = ""
580 while source.next in DIGITS:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300581 lo += sourceget()
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000582 if sourcematch(","):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000583 while source.next in DIGITS:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300584 hi += sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000585 else:
586 hi = lo
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000587 if not sourcematch("}"):
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300588 subpatternappend((LITERAL, _ord(this)))
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000589 source.seek(here)
590 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000591 if lo:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000592 min = int(lo)
Serhiy Storchaka70ca0212013-02-16 16:47:47 +0200593 if min >= MAXREPEAT:
594 raise OverflowError("the repetition number is too large")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000595 if hi:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000596 max = int(hi)
Serhiy Storchaka70ca0212013-02-16 16:47:47 +0200597 if max >= MAXREPEAT:
598 raise OverflowError("the repetition number is too large")
599 if max < min:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200600 raise source.error("bad repeat interval",
601 source.tell() - here)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000602 else:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200603 raise source.error("not supported", len(this))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000604 # figure out which item to repeat
605 if subpattern:
606 item = subpattern[-1:]
607 else:
Fredrik Lundhc0c7ee32001-02-18 21:04:48 +0000608 item = None
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000609 if not item or (_len(item) == 1 and item[0][0] == AT):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200610 raise source.error("nothing to repeat",
611 source.tell() - here + len(this))
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300612 if item[0][0] in _REPEATCODES:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200613 raise source.error("multiple repeat",
614 source.tell() - here + len(this))
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000615 if sourcematch("?"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000616 subpattern[-1] = (MIN_REPEAT, (min, max, item))
617 else:
618 subpattern[-1] = (MAX_REPEAT, (min, max, item))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000619
Fredrik Lundh90a07912000-06-30 07:50:59 +0000620 elif this == ".":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000621 subpatternappend((ANY, None))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000622
Fredrik Lundh90a07912000-06-30 07:50:59 +0000623 elif this == "(":
624 group = 1
625 name = None
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000626 condgroup = None
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000627 if sourcematch("?"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000628 group = 0
629 # options
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300630 char = sourceget()
631 if char is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200632 raise self.error("unexpected end of pattern")
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300633 if char == "P":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000634 # python extensions
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000635 if sourcematch("<"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000636 # named group: skip forward to end of name
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300637 name = source.getuntil(">")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000638 group = 1
Ezio Melotti0941d9f2012-11-03 20:33:08 +0200639 if not name:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200640 raise source.error("missing group name", 1)
Georg Brandl1d472b72013-04-14 11:40:00 +0200641 if not name.isidentifier():
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200642 raise source.error("bad character in group name "
643 "%r" % name,
644 len(name) + 1)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000645 elif sourcematch("="):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000646 # named backreference
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300647 name = source.getuntil(")")
Ezio Melotti0941d9f2012-11-03 20:33:08 +0200648 if not name:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200649 raise source.error("missing group name", 1)
Georg Brandl1d472b72013-04-14 11:40:00 +0200650 if not name.isidentifier():
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200651 raise source.error("bad character in backref "
652 "group name %r" % name,
653 len(name) + 1)
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000654 gid = state.groupdict.get(name)
655 if gid is None:
Raymond Hettinger1c99bc82014-06-22 19:47:22 -0700656 msg = "unknown group name: {0!r}".format(name)
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200657 raise source.error(msg, len(name) + 1)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000658 subpatternappend((GROUPREF, gid))
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000659 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000660 else:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000661 char = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000662 if char is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200663 raise source.error("unexpected end of pattern")
664 raise source.error("unknown specifier: ?P%s" % char,
665 len(char))
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300666 elif char == ":":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000667 # non-capturing group
668 group = 2
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300669 elif char == "#":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000670 # comment
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300671 while True:
672 if source.next is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200673 raise source.error("unbalanced parenthesis")
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300674 if sourceget() == ")":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000675 break
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000676 continue
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300677 elif char in "=!<":
Fredrik Lundh43b3b492000-06-30 10:41:31 +0000678 # lookahead assertions
Fredrik Lundh6f013982000-07-03 18:44:21 +0000679 dir = 1
680 if char == "<":
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300681 char = sourceget()
682 if char is None or char not in "=!":
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200683 raise source.error("syntax error")
Fredrik Lundh6f013982000-07-03 18:44:21 +0000684 dir = -1 # lookbehind
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000685 p = _parse_sub(source, state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000686 if not sourcematch(")"):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200687 raise source.error("unbalanced parenthesis")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000688 if char == "=":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000689 subpatternappend((ASSERT, (dir, p)))
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000690 else:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000691 subpatternappend((ASSERT_NOT, (dir, p)))
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000692 continue
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300693 elif char == "(":
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000694 # conditional backreference group
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300695 condname = source.getuntil(")")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000696 group = 2
Ezio Melotti0941d9f2012-11-03 20:33:08 +0200697 if not condname:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200698 raise source.error("missing group name", 1)
Georg Brandl1d472b72013-04-14 11:40:00 +0200699 if condname.isidentifier():
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000700 condgroup = state.groupdict.get(condname)
701 if condgroup is None:
Raymond Hettinger1c99bc82014-06-22 19:47:22 -0700702 msg = "unknown group name: {0!r}".format(condname)
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200703 raise source.error(msg, len(condname) + 1)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000704 else:
705 try:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000706 condgroup = int(condname)
Serhiy Storchaka9baa5b22014-09-29 22:49:23 +0300707 if condgroup < 0:
708 raise ValueError
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000709 except ValueError:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200710 raise source.error("bad character in group name",
711 len(condname) + 1)
Serhiy Storchaka9baa5b22014-09-29 22:49:23 +0300712 if not condgroup:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200713 raise source.error("bad group number",
714 len(condname) + 1)
Serhiy Storchaka9baa5b22014-09-29 22:49:23 +0300715 if condgroup >= MAXGROUPS:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200716 raise source.error("the group number is too large",
717 len(condname) + 1)
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300718 elif char in FLAGS:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000719 # flags
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300720 state.flags |= FLAGS[char]
Raymond Hettinger54f02222002-06-01 14:18:47 +0000721 while source.next in FLAGS:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300722 state.flags |= FLAGS[sourceget()]
723 verbose = state.flags & SRE_FLAG_VERBOSE
724 else:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200725 raise source.error("unexpected end of pattern")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000726 if group:
727 # parse group contents
Fredrik Lundh90a07912000-06-30 07:50:59 +0000728 if group == 2:
729 # anonymous group
730 group = None
731 else:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200732 try:
733 group = state.opengroup(name)
734 except error as err:
735 raise source.error(err.msg, len(name) + 1)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000736 if condgroup:
737 p = _parse_sub_cond(source, state, condgroup)
738 else:
739 p = _parse_sub(source, state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000740 if not sourcematch(")"):
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200741 raise source.error("unbalanced parenthesis")
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000742 if group is not None:
Serhiy Storchaka84df7fe2014-11-07 21:43:57 +0200743 state.closegroup(group, p)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000744 subpatternappend((SUBPATTERN, (group, p)))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000745 else:
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300746 while True:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000747 char = sourceget()
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000748 if char is None:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200749 raise source.error("unexpected end of pattern")
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000750 if char == ")":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000751 break
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200752 raise source.error("unknown extension", len(char))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000753
Fredrik Lundh90a07912000-06-30 07:50:59 +0000754 elif this == "^":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000755 subpatternappend((AT, AT_BEGINNING))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000756
Fredrik Lundh90a07912000-06-30 07:50:59 +0000757 elif this == "$":
758 subpattern.append((AT, AT_END))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000759
Fredrik Lundh90a07912000-06-30 07:50:59 +0000760 else:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200761 raise source.error("parser error", len(this))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000762
763 return subpattern
764
Antoine Pitroufd036452008-08-19 17:56:33 +0000765def fix_flags(src, flags):
766 # Check and fix flags according to the type of pattern (str or bytes)
767 if isinstance(src, str):
768 if not flags & SRE_FLAG_ASCII:
769 flags |= SRE_FLAG_UNICODE
770 elif flags & SRE_FLAG_UNICODE:
771 raise ValueError("ASCII and UNICODE flags are incompatible")
772 else:
773 if flags & SRE_FLAG_UNICODE:
774 raise ValueError("can't use UNICODE flag with a bytes pattern")
775 return flags
776
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000777def parse(str, flags=0, pattern=None):
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000778 # parse 're' pattern into list of (opcode, argument) tuples
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000779
780 source = Tokenizer(str)
781
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000782 if pattern is None:
783 pattern = Pattern()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000784 pattern.flags = flags
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000785 pattern.str = str
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000786
787 p = _parse_sub(source, pattern, 0)
Antoine Pitroufd036452008-08-19 17:56:33 +0000788 p.pattern.flags = fix_flags(str, p.pattern.flags)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000789
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300790 if source.next is not None:
791 if source.next == ")":
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200792 raise source.error("unbalanced parenthesis")
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300793 else:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200794 raise source.error("bogus characters at end of regular expression",
795 len(tail))
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000796
Fredrik Lundh770617b2001-01-14 15:06:11 +0000797 if flags & SRE_FLAG_DEBUG:
798 p.dump()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000799
Fredrik Lundhd11b5e52000-10-03 19:22:26 +0000800 if not (flags & SRE_FLAG_VERBOSE) and p.pattern.flags & SRE_FLAG_VERBOSE:
801 # the VERBOSE flag was switched on inside the pattern. to be
802 # on the safe side, we'll parse the whole thing again...
803 return parse(str, p.pattern.flags)
804
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000805 return p
806
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000807def parse_template(source, pattern):
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000808 # parse 're' replacement string into list of literals and
809 # group references
810 s = Tokenizer(source)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000811 sget = s.get
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300812 groups = []
813 literals = []
814 literal = []
815 lappend = literal.append
816 def addgroup(index):
817 if literal:
818 literals.append(''.join(literal))
819 del literal[:]
820 groups.append((len(literals), index))
821 literals.append(None)
822 while True:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000823 this = sget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000824 if this is None:
825 break # end of replacement string
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300826 if this[0] == "\\":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000827 # group
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300828 c = this[1]
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000829 if c == "g":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000830 name = ""
831 if s.match("<"):
Serhiy Storchakae2ccf562014-10-10 11:14:49 +0300832 name = s.getuntil(">")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000833 if not name:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200834 raise s.error("missing group name", 1)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000835 try:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000836 index = int(name)
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000837 if index < 0:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200838 raise s.error("negative group number", len(name) + 1)
Serhiy Storchaka9baa5b22014-09-29 22:49:23 +0300839 if index >= MAXGROUPS:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200840 raise s.error("the group number is too large",
841 len(name) + 1)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000842 except ValueError:
Georg Brandl1d472b72013-04-14 11:40:00 +0200843 if not name.isidentifier():
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200844 raise s.error("bad character in group name",
845 len(name) + 1)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000846 try:
847 index = pattern.groupindex[name]
848 except KeyError:
Raymond Hettinger1c99bc82014-06-22 19:47:22 -0700849 msg = "unknown group name: {0!r}".format(name)
850 raise IndexError(msg)
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300851 addgroup(index)
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000852 elif c == "0":
853 if s.next in OCTDIGITS:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300854 this += sget()
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000855 if s.next in OCTDIGITS:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300856 this += sget()
857 lappend(chr(int(this[1:], 8) & 0xff))
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000858 elif c in DIGITS:
859 isoctal = False
860 if s.next in DIGITS:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300861 this += sget()
Gustavo Niemeyerf5a15992004-09-03 20:15:56 +0000862 if (c in OCTDIGITS and this[2] in OCTDIGITS and
863 s.next in OCTDIGITS):
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300864 this += sget()
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000865 isoctal = True
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300866 c = int(this[1:], 8)
867 if c > 0o377:
Serhiy Storchakaad446d52014-11-10 13:49:00 +0200868 raise s.error('octal escape value %r outside of '
869 'range 0-0o377' % this, len(this))
Serhiy Storchakac563caf2014-09-23 23:22:41 +0300870 lappend(chr(c))
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000871 if not isoctal:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300872 addgroup(int(this[1:]))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000873 else:
874 try:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300875 this = chr(ESCAPES[this][1])
Fredrik Lundh90a07912000-06-30 07:50:59 +0000876 except KeyError:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000877 pass
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300878 lappend(this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000879 else:
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300880 lappend(this)
881 if literal:
882 literals.append(''.join(literal))
883 if not isinstance(source, str):
Ezio Melottib92ed7c2010-03-06 15:24:08 +0000884 # The tokenizer implicitly decodes bytes objects as latin-1, we must
885 # therefore re-encode the final representation.
Serhiy Storchaka9c15ec12013-10-23 22:27:52 +0300886 literals = [None if s is None else s.encode('latin-1') for s in literals]
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000887 return groups, literals
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000888
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000889def expand_template(template, match):
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000890 g = match.group
Serhiy Storchaka7438e4b2014-10-10 11:06:31 +0300891 empty = match.string[:0]
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000892 groups, literals = template
893 literals = literals[:]
894 try:
895 for index, group in groups:
Serhiy Storchaka7438e4b2014-10-10 11:06:31 +0300896 literals[index] = g(group) or empty
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000897 except IndexError:
Collin Winterce36ad82007-08-30 01:19:48 +0000898 raise error("invalid group reference")
Serhiy Storchaka7438e4b2014-10-10 11:06:31 +0300899 return empty.join(literals)