blob: ae63c31ebc04e0b7779e8bb061aaa81ca70161da [file] [log] [blame]
Guido van Rossum7627c0d2000-03-31 14:58:54 +00001#
2# Secret Labs' Regular Expression Engine
Guido van Rossum7627c0d2000-03-31 14:58:54 +00003#
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +00004# convert re-style regular expression to sre pattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +00005#
Fredrik Lundh770617b2001-01-14 15:06:11 +00006# Copyright (c) 1998-2001 by Secret Labs AB. All rights reserved.
Guido van Rossum7627c0d2000-03-31 14:58:54 +00007#
Fredrik Lundh29c4ba92000-08-01 18:20:07 +00008# See the sre.py file for information on usage and redistribution.
Guido van Rossum7627c0d2000-03-31 14:58:54 +00009#
10
Fred Drakeb8f22742001-09-04 19:10:20 +000011"""Internal support module for sre"""
12
Fredrik Lundh470ea5a2001-01-14 21:00:44 +000013# XXX: show string offset and offending character for all errors
14
Barry Warsaw8bee7612004-08-25 02:22:30 +000015import sys
Guido van Rossum7627c0d2000-03-31 14:58:54 +000016
17from sre_constants import *
18
19SPECIAL_CHARS = ".\\[{()*+?^$|"
Fredrik Lundh143328b2000-09-02 11:03:34 +000020REPEAT_CHARS = "*+?{"
Guido van Rossum7627c0d2000-03-31 14:58:54 +000021
Raymond Hettinger049ade22005-02-28 19:27:52 +000022DIGITS = set("0123456789")
Guido van Rossumb81e70e2000-04-10 17:10:48 +000023
Raymond Hettinger049ade22005-02-28 19:27:52 +000024OCTDIGITS = set("01234567")
25HEXDIGITS = set("0123456789abcdefABCDEF")
Guido van Rossum7627c0d2000-03-31 14:58:54 +000026
Raymond Hettinger049ade22005-02-28 19:27:52 +000027WHITESPACE = set(" \t\n\r\v\f")
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +000028
Guido van Rossum7627c0d2000-03-31 14:58:54 +000029ESCAPES = {
Fredrik Lundhf2989b22001-02-18 12:05:16 +000030 r"\a": (LITERAL, ord("\a")),
31 r"\b": (LITERAL, ord("\b")),
32 r"\f": (LITERAL, ord("\f")),
33 r"\n": (LITERAL, ord("\n")),
34 r"\r": (LITERAL, ord("\r")),
35 r"\t": (LITERAL, ord("\t")),
36 r"\v": (LITERAL, ord("\v")),
Fredrik Lundh0640e112000-06-30 13:55:15 +000037 r"\\": (LITERAL, ord("\\"))
Guido van Rossum7627c0d2000-03-31 14:58:54 +000038}
39
40CATEGORIES = {
Fredrik Lundh770617b2001-01-14 15:06:11 +000041 r"\A": (AT, AT_BEGINNING_STRING), # start of string
Fredrik Lundh01016fe2000-06-30 00:27:46 +000042 r"\b": (AT, AT_BOUNDARY),
43 r"\B": (AT, AT_NON_BOUNDARY),
44 r"\d": (IN, [(CATEGORY, CATEGORY_DIGIT)]),
45 r"\D": (IN, [(CATEGORY, CATEGORY_NOT_DIGIT)]),
46 r"\s": (IN, [(CATEGORY, CATEGORY_SPACE)]),
47 r"\S": (IN, [(CATEGORY, CATEGORY_NOT_SPACE)]),
48 r"\w": (IN, [(CATEGORY, CATEGORY_WORD)]),
49 r"\W": (IN, [(CATEGORY, CATEGORY_NOT_WORD)]),
Fredrik Lundh770617b2001-01-14 15:06:11 +000050 r"\Z": (AT, AT_END_STRING), # end of string
Guido van Rossum7627c0d2000-03-31 14:58:54 +000051}
52
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +000053FLAGS = {
Fredrik Lundh436c3d582000-06-29 08:58:44 +000054 # standard flags
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +000055 "i": SRE_FLAG_IGNORECASE,
56 "L": SRE_FLAG_LOCALE,
57 "m": SRE_FLAG_MULTILINE,
58 "s": SRE_FLAG_DOTALL,
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +000059 "x": SRE_FLAG_VERBOSE,
Fredrik Lundh436c3d582000-06-29 08:58:44 +000060 # extensions
Antoine Pitroufd036452008-08-19 17:56:33 +000061 "a": SRE_FLAG_ASCII,
Fredrik Lundh436c3d582000-06-29 08:58:44 +000062 "t": SRE_FLAG_TEMPLATE,
63 "u": SRE_FLAG_UNICODE,
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +000064}
65
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +000066class Pattern:
67 # master pattern object. keeps track of global attributes
Guido van Rossum7627c0d2000-03-31 14:58:54 +000068 def __init__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +000069 self.flags = 0
Fredrik Lundhebc37b22000-10-28 19:30:41 +000070 self.open = []
Fredrik Lundh90a07912000-06-30 07:50:59 +000071 self.groups = 1
72 self.groupdict = {}
Fredrik Lundhebc37b22000-10-28 19:30:41 +000073 def opengroup(self, name=None):
Fredrik Lundh90a07912000-06-30 07:50:59 +000074 gid = self.groups
75 self.groups = gid + 1
Raymond Hettingerf13eb552002-06-02 00:40:05 +000076 if name is not None:
Tim Peters75335872001-11-03 19:35:43 +000077 ogid = self.groupdict.get(name, None)
78 if ogid is not None:
Collin Winterce36ad82007-08-30 01:19:48 +000079 raise error("redefinition of group name %s as group %d; "
80 "was group %d" % (repr(name), gid, ogid))
Fredrik Lundh90a07912000-06-30 07:50:59 +000081 self.groupdict[name] = gid
Fredrik Lundhebc37b22000-10-28 19:30:41 +000082 self.open.append(gid)
Fredrik Lundh90a07912000-06-30 07:50:59 +000083 return gid
Fredrik Lundhebc37b22000-10-28 19:30:41 +000084 def closegroup(self, gid):
85 self.open.remove(gid)
86 def checkgroup(self, gid):
87 return gid < self.groups and gid not in self.open
Guido van Rossum7627c0d2000-03-31 14:58:54 +000088
89class SubPattern:
90 # a subpattern, in intermediate form
91 def __init__(self, pattern, data=None):
Fredrik Lundh90a07912000-06-30 07:50:59 +000092 self.pattern = pattern
Raymond Hettingerf13eb552002-06-02 00:40:05 +000093 if data is None:
Fredrik Lundh90a07912000-06-30 07:50:59 +000094 data = []
95 self.data = data
96 self.width = None
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +000097 def dump(self, level=0):
98 nl = 1
Guido van Rossum13257902007-06-07 23:15:56 +000099 seqtypes = (tuple, list)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000100 for op, av in self.data:
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000101 print(level*" " + op, end=' '); nl = 0
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000102 if op == "in":
103 # member sublanguage
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000104 print(); nl = 1
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000105 for op, a in av:
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000106 print((level+1)*" " + op, a)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000107 elif op == "branch":
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000108 print(); nl = 1
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000109 i = 0
110 for a in av[1]:
111 if i > 0:
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000112 print(level*" " + "or")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000113 a.dump(level+1); nl = 1
114 i = i + 1
Guido van Rossum13257902007-06-07 23:15:56 +0000115 elif isinstance(av, seqtypes):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000116 for a in av:
117 if isinstance(a, SubPattern):
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000118 if not nl: print()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000119 a.dump(level+1); nl = 1
120 else:
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000121 print(a, end=' ') ; nl = 0
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000122 else:
Guido van Rossumbe19ed72007-02-09 05:37:30 +0000123 print(av, end=' ') ; nl = 0
124 if not nl: print()
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000125 def __repr__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000126 return repr(self.data)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000127 def __len__(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000128 return len(self.data)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000129 def __delitem__(self, index):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000130 del self.data[index]
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000131 def __getitem__(self, index):
Thomas Wouters902d6eb2007-01-09 23:18:33 +0000132 if isinstance(index, slice):
133 return SubPattern(self.pattern, self.data[index])
Fredrik Lundh90a07912000-06-30 07:50:59 +0000134 return self.data[index]
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000135 def __setitem__(self, index, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000136 self.data[index] = code
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000137 def insert(self, index, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000138 self.data.insert(index, code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000139 def append(self, code):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000140 self.data.append(code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000141 def getwidth(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000142 # determine the width (min, max) for this subpattern
143 if self.width:
144 return self.width
Guido van Rossume2a383d2007-01-15 16:59:06 +0000145 lo = hi = 0
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000146 UNITCODES = (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY)
147 REPEATCODES = (MIN_REPEAT, MAX_REPEAT)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000148 for op, av in self.data:
149 if op is BRANCH:
Christian Heimesa37d4c62007-12-04 23:02:19 +0000150 i = sys.maxsize
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000151 j = 0
Fredrik Lundh90a07912000-06-30 07:50:59 +0000152 for av in av[1]:
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000153 l, h = av.getwidth()
154 i = min(i, l)
Fredrik Lundhe1869832000-08-01 22:47:49 +0000155 j = max(j, h)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000156 lo = lo + i
157 hi = hi + j
158 elif op is CALL:
159 i, j = av.getwidth()
160 lo = lo + i
161 hi = hi + j
162 elif op is SUBPATTERN:
163 i, j = av[1].getwidth()
164 lo = lo + i
165 hi = hi + j
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000166 elif op in REPEATCODES:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000167 i, j = av[2].getwidth()
Guido van Rossume2a383d2007-01-15 16:59:06 +0000168 lo = lo + int(i) * av[0]
169 hi = hi + int(j) * av[1]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000170 elif op in UNITCODES:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000171 lo = lo + 1
172 hi = hi + 1
173 elif op == SUCCESS:
174 break
Christian Heimesa37d4c62007-12-04 23:02:19 +0000175 self.width = int(min(lo, sys.maxsize)), int(min(hi, sys.maxsize))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000176 return self.width
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000177
178class Tokenizer:
179 def __init__(self, string):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000180 self.string = string
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000181 self.index = 0
182 self.__next()
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000183 def __next(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000184 if self.index >= len(self.string):
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000185 self.next = None
186 return
Guido van Rossum75a902d2007-10-19 22:06:24 +0000187 char = self.string[self.index:self.index+1]
188 # Special case for the str8, since indexing returns a integer
189 # XXX This is only needed for test_bug_926075 in test_re.py
Thomas Wouters40a088d2008-03-18 20:19:54 +0000190 if char and isinstance(char, bytes):
191 char = chr(char[0])
Guido van Rossum75a902d2007-10-19 22:06:24 +0000192 if char == "\\":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000193 try:
194 c = self.string[self.index + 1]
195 except IndexError:
Collin Winterce36ad82007-08-30 01:19:48 +0000196 raise error("bogus escape (end of line)")
Guido van Rossum98297ee2007-11-06 21:34:58 +0000197 if isinstance(self.string, bytes):
Antoine Pitrou22628c42008-07-22 17:53:22 +0000198 c = chr(c)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000199 char = char + c
200 self.index = self.index + len(char)
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000201 self.next = char
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000202 def match(self, char, skip=1):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000203 if char == self.next:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000204 if skip:
205 self.__next()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000206 return 1
207 return 0
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000208 def get(self):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000209 this = self.next
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000210 self.__next()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000211 return this
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000212 def tell(self):
213 return self.index, self.next
214 def seek(self, index):
215 self.index, self.next = index
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000216
Fredrik Lundh4781b072000-06-29 12:38:45 +0000217def isident(char):
218 return "a" <= char <= "z" or "A" <= char <= "Z" or char == "_"
219
220def isdigit(char):
221 return "0" <= char <= "9"
222
223def isname(name):
224 # check that group name is a valid string
Fredrik Lundh4781b072000-06-29 12:38:45 +0000225 if not isident(name[0]):
Guido van Rossum8ca162f2002-04-07 06:36:23 +0000226 return False
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000227 for char in name[1:]:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000228 if not isident(char) and not isdigit(char):
Guido van Rossum8ca162f2002-04-07 06:36:23 +0000229 return False
230 return True
Fredrik Lundh4781b072000-06-29 12:38:45 +0000231
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000232def _class_escape(source, escape):
233 # handle escape code inside character class
234 code = ESCAPES.get(escape)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000235 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000236 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000237 code = CATEGORIES.get(escape)
238 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000239 return code
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000240 try:
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000241 c = escape[1:2]
242 if c == "x":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000243 # hexadecimal escape (exactly two digits)
244 while source.next in HEXDIGITS and len(escape) < 4:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000245 escape = escape + source.get()
246 escape = escape[2:]
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000247 if len(escape) != 2:
Collin Winterce36ad82007-08-30 01:19:48 +0000248 raise error("bogus escape: %s" % repr("\\" + escape))
Barry Warsaw8bee7612004-08-25 02:22:30 +0000249 return LITERAL, int(escape, 16) & 0xff
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000250 elif c in OCTDIGITS:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000251 # octal escape (up to three digits)
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000252 while source.next in OCTDIGITS and len(escape) < 4:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000253 escape = escape + source.get()
254 escape = escape[1:]
Barry Warsaw8bee7612004-08-25 02:22:30 +0000255 return LITERAL, int(escape, 8) & 0xff
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000256 elif c in DIGITS:
Collin Winterce36ad82007-08-30 01:19:48 +0000257 raise error("bogus escape: %s" % repr(escape))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000258 if len(escape) == 2:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000259 return LITERAL, ord(escape[1])
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000260 except ValueError:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000261 pass
Collin Winterce36ad82007-08-30 01:19:48 +0000262 raise error("bogus escape: %s" % repr(escape))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000263
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000264def _escape(source, escape, state):
265 # handle escape code in expression
266 code = CATEGORIES.get(escape)
267 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000268 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000269 code = ESCAPES.get(escape)
270 if code:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000271 return code
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000272 try:
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000273 c = escape[1:2]
274 if c == "x":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000275 # hexadecimal escape
276 while source.next in HEXDIGITS and len(escape) < 4:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000277 escape = escape + source.get()
Fredrik Lundh143328b2000-09-02 11:03:34 +0000278 if len(escape) != 4:
279 raise ValueError
Barry Warsaw8bee7612004-08-25 02:22:30 +0000280 return LITERAL, int(escape[2:], 16) & 0xff
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000281 elif c == "0":
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000282 # octal escape
Fredrik Lundh143328b2000-09-02 11:03:34 +0000283 while source.next in OCTDIGITS and len(escape) < 4:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000284 escape = escape + source.get()
Barry Warsaw8bee7612004-08-25 02:22:30 +0000285 return LITERAL, int(escape[1:], 8) & 0xff
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000286 elif c in DIGITS:
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000287 # octal escape *or* decimal group reference (sigh)
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000288 if source.next in DIGITS:
289 escape = escape + source.get()
Fredrik Lundh143328b2000-09-02 11:03:34 +0000290 if (escape[1] in OCTDIGITS and escape[2] in OCTDIGITS and
291 source.next in OCTDIGITS):
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000292 # got three octal digits; this is an octal escape
Fredrik Lundh90a07912000-06-30 07:50:59 +0000293 escape = escape + source.get()
Barry Warsaw8bee7612004-08-25 02:22:30 +0000294 return LITERAL, int(escape[1:], 8) & 0xff
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000295 # not an octal escape, so this is a group reference
296 group = int(escape[1:])
297 if group < state.groups:
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000298 if not state.checkgroup(group):
Collin Winterce36ad82007-08-30 01:19:48 +0000299 raise error("cannot refer to open group")
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000300 return GROUPREF, group
Fredrik Lundh143328b2000-09-02 11:03:34 +0000301 raise ValueError
Fredrik Lundh90a07912000-06-30 07:50:59 +0000302 if len(escape) == 2:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000303 return LITERAL, ord(escape[1])
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000304 except ValueError:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000305 pass
Collin Winterce36ad82007-08-30 01:19:48 +0000306 raise error("bogus escape: %s" % repr(escape))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000307
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000308def _parse_sub(source, state, nested=1):
309 # parse an alternation: a|b|c
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000310
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000311 items = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000312 itemsappend = items.append
313 sourcematch = source.match
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000314 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000315 itemsappend(_parse(source, state))
316 if sourcematch("|"):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000317 continue
318 if not nested:
319 break
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000320 if not source.next or sourcematch(")", 0):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000321 break
322 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000323 raise error("pattern not properly closed")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000324
325 if len(items) == 1:
326 return items[0]
327
328 subpattern = SubPattern(state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000329 subpatternappend = subpattern.append
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000330
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000331 # check if all items share a common prefix
332 while 1:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000333 prefix = None
334 for item in items:
335 if not item:
336 break
337 if prefix is None:
338 prefix = item[0]
339 elif item[0] != prefix:
340 break
341 else:
342 # all subitems start with a common "prefix".
343 # move it out of the branch
344 for item in items:
345 del item[0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000346 subpatternappend(prefix)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000347 continue # check next one
348 break
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000349
350 # check if the branch can be replaced by a character set
351 for item in items:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000352 if len(item) != 1 or item[0][0] != LITERAL:
353 break
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000354 else:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000355 # we can store this as a character set instead of a
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000356 # branch (the compiler may optimize this even more)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000357 set = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000358 setappend = set.append
Fredrik Lundh90a07912000-06-30 07:50:59 +0000359 for item in items:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000360 setappend(item[0])
361 subpatternappend((IN, set))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000362 return subpattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000363
364 subpattern.append((BRANCH, (None, items)))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000365 return subpattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000366
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000367def _parse_sub_cond(source, state, condgroup):
Tim Peters58eb11c2004-01-18 20:29:55 +0000368 item_yes = _parse(source, state)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000369 if source.match("|"):
Tim Peters58eb11c2004-01-18 20:29:55 +0000370 item_no = _parse(source, state)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000371 if source.match("|"):
Collin Winterce36ad82007-08-30 01:19:48 +0000372 raise error("conditional backref with more than two branches")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000373 else:
374 item_no = None
375 if source.next and not source.match(")", 0):
Collin Winterce36ad82007-08-30 01:19:48 +0000376 raise error("pattern not properly closed")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000377 subpattern = SubPattern(state)
378 subpattern.append((GROUPREF_EXISTS, (condgroup, item_yes, item_no)))
379 return subpattern
380
Raymond Hettinger049ade22005-02-28 19:27:52 +0000381_PATTERNENDERS = set("|)")
382_ASSERTCHARS = set("=!<")
383_LOOKBEHINDASSERTCHARS = set("=!")
384_REPEATCODES = set([MIN_REPEAT, MAX_REPEAT])
385
Fredrik Lundh55a4f4a2000-06-30 22:37:31 +0000386def _parse(source, state):
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000387 # parse a simple pattern
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000388 subpattern = SubPattern(state)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000389
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000390 # precompute constants into local variables
391 subpatternappend = subpattern.append
392 sourceget = source.get
393 sourcematch = source.match
394 _len = len
Raymond Hettinger049ade22005-02-28 19:27:52 +0000395 PATTERNENDERS = _PATTERNENDERS
396 ASSERTCHARS = _ASSERTCHARS
397 LOOKBEHINDASSERTCHARS = _LOOKBEHINDASSERTCHARS
398 REPEATCODES = _REPEATCODES
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000399
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000400 while 1:
401
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000402 if source.next in PATTERNENDERS:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000403 break # end of subpattern
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000404 this = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000405 if this is None:
406 break # end of pattern
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000407
Fredrik Lundh90a07912000-06-30 07:50:59 +0000408 if state.flags & SRE_FLAG_VERBOSE:
409 # skip whitespace and comments
410 if this in WHITESPACE:
411 continue
412 if this == "#":
413 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000414 this = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000415 if this in (None, "\n"):
416 break
417 continue
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000418
Fredrik Lundh90a07912000-06-30 07:50:59 +0000419 if this and this[0] not in SPECIAL_CHARS:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000420 subpatternappend((LITERAL, ord(this)))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000421
Fredrik Lundh90a07912000-06-30 07:50:59 +0000422 elif this == "[":
423 # character set
424 set = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000425 setappend = set.append
426## if sourcematch(":"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000427## pass # handle character classes
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000428 if sourcematch("^"):
429 setappend((NEGATE, None))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000430 # check remaining characters
431 start = set[:]
432 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000433 this = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000434 if this == "]" and set != start:
435 break
436 elif this and this[0] == "\\":
437 code1 = _class_escape(source, this)
438 elif this:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000439 code1 = LITERAL, ord(this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000440 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000441 raise error("unexpected end of regular expression")
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000442 if sourcematch("-"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000443 # potential range
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000444 this = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000445 if this == "]":
Fredrik Lundh025468d2000-10-07 10:16:19 +0000446 if code1[0] is IN:
447 code1 = code1[1][0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000448 setappend(code1)
449 setappend((LITERAL, ord("-")))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000450 break
Guido van Rossum41c99e72003-04-14 17:59:34 +0000451 elif this:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000452 if this[0] == "\\":
453 code2 = _class_escape(source, this)
454 else:
Fredrik Lundh0640e112000-06-30 13:55:15 +0000455 code2 = LITERAL, ord(this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000456 if code1[0] != LITERAL or code2[0] != LITERAL:
Collin Winterce36ad82007-08-30 01:19:48 +0000457 raise error("bad character range")
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000458 lo = code1[1]
459 hi = code2[1]
460 if hi < lo:
Collin Winterce36ad82007-08-30 01:19:48 +0000461 raise error("bad character range")
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000462 setappend((RANGE, (lo, hi)))
Guido van Rossum41c99e72003-04-14 17:59:34 +0000463 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000464 raise error("unexpected end of regular expression")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000465 else:
466 if code1[0] is IN:
467 code1 = code1[1][0]
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000468 setappend(code1)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000469
Fredrik Lundh770617b2001-01-14 15:06:11 +0000470 # XXX: <fl> should move set optimization to compiler!
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000471 if _len(set)==1 and set[0][0] is LITERAL:
472 subpatternappend(set[0]) # optimization
473 elif _len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL:
474 subpatternappend((NOT_LITERAL, set[1][1])) # optimization
Fredrik Lundh90a07912000-06-30 07:50:59 +0000475 else:
Fredrik Lundh770617b2001-01-14 15:06:11 +0000476 # XXX: <fl> should add charmap optimization here
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000477 subpatternappend((IN, set))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000478
Fredrik Lundh90a07912000-06-30 07:50:59 +0000479 elif this and this[0] in REPEAT_CHARS:
480 # repeat previous item
481 if this == "?":
482 min, max = 0, 1
483 elif this == "*":
484 min, max = 0, MAXREPEAT
Fredrik Lundhc0c7ee32001-02-18 21:04:48 +0000485
Fredrik Lundh90a07912000-06-30 07:50:59 +0000486 elif this == "+":
487 min, max = 1, MAXREPEAT
488 elif this == "{":
Gustavo Niemeyer6fa0c5a2005-09-14 08:54:39 +0000489 if source.next == "}":
490 subpatternappend((LITERAL, ord(this)))
491 continue
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000492 here = source.tell()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000493 min, max = 0, MAXREPEAT
494 lo = hi = ""
495 while source.next in DIGITS:
496 lo = lo + source.get()
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000497 if sourcematch(","):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000498 while source.next in DIGITS:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000499 hi = hi + sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000500 else:
501 hi = lo
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000502 if not sourcematch("}"):
503 subpatternappend((LITERAL, ord(this)))
Fredrik Lundhc13222c2000-07-01 23:49:14 +0000504 source.seek(here)
505 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000506 if lo:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000507 min = int(lo)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000508 if hi:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000509 max = int(hi)
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000510 if max < min:
Collin Winterce36ad82007-08-30 01:19:48 +0000511 raise error("bad repeat interval")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000512 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000513 raise error("not supported")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000514 # figure out which item to repeat
515 if subpattern:
516 item = subpattern[-1:]
517 else:
Fredrik Lundhc0c7ee32001-02-18 21:04:48 +0000518 item = None
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000519 if not item or (_len(item) == 1 and item[0][0] == AT):
Collin Winterce36ad82007-08-30 01:19:48 +0000520 raise error("nothing to repeat")
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000521 if item[0][0] in REPEATCODES:
Collin Winterce36ad82007-08-30 01:19:48 +0000522 raise error("multiple repeat")
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000523 if sourcematch("?"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000524 subpattern[-1] = (MIN_REPEAT, (min, max, item))
525 else:
526 subpattern[-1] = (MAX_REPEAT, (min, max, item))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000527
Fredrik Lundh90a07912000-06-30 07:50:59 +0000528 elif this == ".":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000529 subpatternappend((ANY, None))
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000530
Fredrik Lundh90a07912000-06-30 07:50:59 +0000531 elif this == "(":
532 group = 1
533 name = None
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000534 condgroup = None
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000535 if sourcematch("?"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000536 group = 0
537 # options
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000538 if sourcematch("P"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000539 # python extensions
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000540 if sourcematch("<"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000541 # named group: skip forward to end of name
542 name = ""
543 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000544 char = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000545 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000546 raise error("unterminated name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000547 if char == ">":
548 break
549 name = name + char
550 group = 1
551 if not isname(name):
Collin Winterce36ad82007-08-30 01:19:48 +0000552 raise error("bad character in group name")
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000553 elif sourcematch("="):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000554 # named backreference
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000555 name = ""
556 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000557 char = sourceget()
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000558 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000559 raise error("unterminated name")
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000560 if char == ")":
561 break
562 name = name + char
563 if not isname(name):
Collin Winterce36ad82007-08-30 01:19:48 +0000564 raise error("bad character in group name")
Fredrik Lundhb71624e2000-06-30 09:13:06 +0000565 gid = state.groupdict.get(name)
566 if gid is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000567 raise error("unknown group name")
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000568 subpatternappend((GROUPREF, gid))
Fredrik Lundh7cafe4d2000-07-02 17:33:27 +0000569 continue
Fredrik Lundh90a07912000-06-30 07:50:59 +0000570 else:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000571 char = sourceget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000572 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000573 raise error("unexpected end of pattern")
574 raise error("unknown specifier: ?P%s" % char)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000575 elif sourcematch(":"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000576 # non-capturing group
577 group = 2
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000578 elif sourcematch("#"):
Fredrik Lundh90a07912000-06-30 07:50:59 +0000579 # comment
580 while 1:
581 if source.next is None or source.next == ")":
582 break
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000583 sourceget()
584 if not sourcematch(")"):
Collin Winterce36ad82007-08-30 01:19:48 +0000585 raise error("unbalanced parenthesis")
Fredrik Lundh0c4fdba2000-08-31 22:57:55 +0000586 continue
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000587 elif source.next in ASSERTCHARS:
Fredrik Lundh43b3b492000-06-30 10:41:31 +0000588 # lookahead assertions
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000589 char = sourceget()
Fredrik Lundh6f013982000-07-03 18:44:21 +0000590 dir = 1
591 if char == "<":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000592 if source.next not in LOOKBEHINDASSERTCHARS:
Collin Winterce36ad82007-08-30 01:19:48 +0000593 raise error("syntax error")
Fredrik Lundh6f013982000-07-03 18:44:21 +0000594 dir = -1 # lookbehind
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000595 char = sourceget()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000596 p = _parse_sub(source, state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000597 if not sourcematch(")"):
Collin Winterce36ad82007-08-30 01:19:48 +0000598 raise error("unbalanced parenthesis")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000599 if char == "=":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000600 subpatternappend((ASSERT, (dir, p)))
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000601 else:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000602 subpatternappend((ASSERT_NOT, (dir, p)))
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000603 continue
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000604 elif sourcematch("("):
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000605 # conditional backreference group
606 condname = ""
607 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000608 char = sourceget()
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000609 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000610 raise error("unterminated name")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000611 if char == ")":
612 break
613 condname = condname + char
614 group = 2
615 if isname(condname):
616 condgroup = state.groupdict.get(condname)
617 if condgroup is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000618 raise error("unknown group name")
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000619 else:
620 try:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000621 condgroup = int(condname)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000622 except ValueError:
Collin Winterce36ad82007-08-30 01:19:48 +0000623 raise error("bad character in group name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000624 else:
625 # flags
Raymond Hettinger54f02222002-06-01 14:18:47 +0000626 if not source.next in FLAGS:
Collin Winterce36ad82007-08-30 01:19:48 +0000627 raise error("unexpected end of pattern")
Raymond Hettinger54f02222002-06-01 14:18:47 +0000628 while source.next in FLAGS:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000629 state.flags = state.flags | FLAGS[sourceget()]
Fredrik Lundh90a07912000-06-30 07:50:59 +0000630 if group:
631 # parse group contents
Fredrik Lundh90a07912000-06-30 07:50:59 +0000632 if group == 2:
633 # anonymous group
634 group = None
635 else:
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000636 group = state.opengroup(name)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000637 if condgroup:
638 p = _parse_sub_cond(source, state, condgroup)
639 else:
640 p = _parse_sub(source, state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000641 if not sourcematch(")"):
Collin Winterce36ad82007-08-30 01:19:48 +0000642 raise error("unbalanced parenthesis")
Fredrik Lundhebc37b22000-10-28 19:30:41 +0000643 if group is not None:
644 state.closegroup(group)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000645 subpatternappend((SUBPATTERN, (group, p)))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000646 else:
647 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000648 char = sourceget()
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000649 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000650 raise error("unexpected end of pattern")
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000651 if char == ")":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000652 break
Collin Winterce36ad82007-08-30 01:19:48 +0000653 raise error("unknown extension")
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000654
Fredrik Lundh90a07912000-06-30 07:50:59 +0000655 elif this == "^":
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000656 subpatternappend((AT, AT_BEGINNING))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000657
Fredrik Lundh90a07912000-06-30 07:50:59 +0000658 elif this == "$":
659 subpattern.append((AT, AT_END))
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000660
Fredrik Lundh90a07912000-06-30 07:50:59 +0000661 elif this and this[0] == "\\":
662 code = _escape(source, this, state)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000663 subpatternappend(code)
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000664
Fredrik Lundh90a07912000-06-30 07:50:59 +0000665 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000666 raise error("parser error")
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000667
668 return subpattern
669
Antoine Pitroufd036452008-08-19 17:56:33 +0000670def fix_flags(src, flags):
671 # Check and fix flags according to the type of pattern (str or bytes)
672 if isinstance(src, str):
673 if not flags & SRE_FLAG_ASCII:
674 flags |= SRE_FLAG_UNICODE
675 elif flags & SRE_FLAG_UNICODE:
676 raise ValueError("ASCII and UNICODE flags are incompatible")
677 else:
678 if flags & SRE_FLAG_UNICODE:
679 raise ValueError("can't use UNICODE flag with a bytes pattern")
680 return flags
681
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000682def parse(str, flags=0, pattern=None):
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000683 # parse 're' pattern into list of (opcode, argument) tuples
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000684
685 source = Tokenizer(str)
686
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000687 if pattern is None:
688 pattern = Pattern()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000689 pattern.flags = flags
Fredrik Lundh470ea5a2001-01-14 21:00:44 +0000690 pattern.str = str
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000691
692 p = _parse_sub(source, pattern, 0)
Antoine Pitroufd036452008-08-19 17:56:33 +0000693 p.pattern.flags = fix_flags(str, p.pattern.flags)
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000694
695 tail = source.get()
696 if tail == ")":
Collin Winterce36ad82007-08-30 01:19:48 +0000697 raise error("unbalanced parenthesis")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000698 elif tail:
Collin Winterce36ad82007-08-30 01:19:48 +0000699 raise error("bogus characters at end of regular expression")
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000700
Fredrik Lundh770617b2001-01-14 15:06:11 +0000701 if flags & SRE_FLAG_DEBUG:
702 p.dump()
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000703
Fredrik Lundhd11b5e52000-10-03 19:22:26 +0000704 if not (flags & SRE_FLAG_VERBOSE) and p.pattern.flags & SRE_FLAG_VERBOSE:
705 # the VERBOSE flag was switched on inside the pattern. to be
706 # on the safe side, we'll parse the whole thing again...
707 return parse(str, p.pattern.flags)
708
Guido van Rossum7627c0d2000-03-31 14:58:54 +0000709 return p
710
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000711def parse_template(source, pattern):
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000712 # parse 're' replacement string into list of literals and
713 # group references
714 s = Tokenizer(source)
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000715 sget = s.get
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000716 p = []
717 a = p.append
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000718 def literal(literal, p=p, pappend=a):
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000719 if p and p[-1][0] is LITERAL:
720 p[-1] = LITERAL, p[-1][1] + literal
721 else:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000722 pappend((LITERAL, literal))
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000723 sep = source[:0]
Guido van Rossum13257902007-06-07 23:15:56 +0000724 if isinstance(sep, str):
Fredrik Lundh59b68652001-09-18 20:55:24 +0000725 makechar = chr
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000726 else:
Guido van Rossum84fc66d2007-05-03 17:18:26 +0000727 makechar = chr
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000728 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000729 this = sget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000730 if this is None:
731 break # end of replacement string
732 if this and this[0] == "\\":
733 # group
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000734 c = this[1:2]
735 if c == "g":
Fredrik Lundh90a07912000-06-30 07:50:59 +0000736 name = ""
737 if s.match("<"):
738 while 1:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000739 char = sget()
Fredrik Lundh90a07912000-06-30 07:50:59 +0000740 if char is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000741 raise error("unterminated group name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000742 if char == ">":
743 break
744 name = name + char
745 if not name:
Collin Winterce36ad82007-08-30 01:19:48 +0000746 raise error("bad group name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000747 try:
Barry Warsaw8bee7612004-08-25 02:22:30 +0000748 index = int(name)
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000749 if index < 0:
Collin Winterce36ad82007-08-30 01:19:48 +0000750 raise error("negative group number")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000751 except ValueError:
752 if not isname(name):
Collin Winterce36ad82007-08-30 01:19:48 +0000753 raise error("bad character in group name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000754 try:
755 index = pattern.groupindex[name]
756 except KeyError:
Collin Winterce36ad82007-08-30 01:19:48 +0000757 raise IndexError("unknown group name")
Fredrik Lundh90a07912000-06-30 07:50:59 +0000758 a((MARK, index))
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000759 elif c == "0":
760 if s.next in OCTDIGITS:
761 this = this + sget()
762 if s.next in OCTDIGITS:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000763 this = this + sget()
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000764 literal(makechar(int(this[1:], 8) & 0xff))
765 elif c in DIGITS:
766 isoctal = False
767 if s.next in DIGITS:
768 this = this + sget()
Gustavo Niemeyerf5a15992004-09-03 20:15:56 +0000769 if (c in OCTDIGITS and this[2] in OCTDIGITS and
770 s.next in OCTDIGITS):
Gustavo Niemeyera01a2ee2004-09-03 17:06:10 +0000771 this = this + sget()
772 isoctal = True
773 literal(makechar(int(this[1:], 8) & 0xff))
774 if not isoctal:
775 a((MARK, int(this[1:])))
Fredrik Lundh90a07912000-06-30 07:50:59 +0000776 else:
777 try:
Fredrik Lundh59b68652001-09-18 20:55:24 +0000778 this = makechar(ESCAPES[this][1])
Fredrik Lundh90a07912000-06-30 07:50:59 +0000779 except KeyError:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000780 pass
781 literal(this)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000782 else:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000783 literal(this)
784 # convert template to groups and literals lists
785 i = 0
786 groups = []
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000787 groupsappend = groups.append
788 literals = [None] * len(p)
Ezio Melottib92ed7c2010-03-06 15:24:08 +0000789 if isinstance(source, str):
790 encode = lambda x: x
791 else:
792 # The tokenizer implicitly decodes bytes objects as latin-1, we must
793 # therefore re-encode the final representation.
Marc-André Lemburg8f36af72011-02-25 15:42:01 +0000794 encode = lambda x: x.encode('latin-1')
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000795 for c, s in p:
796 if c is MARK:
Raymond Hettinger968c56a2004-03-26 23:24:00 +0000797 groupsappend((i, s))
798 # literal[i] is already None
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000799 else:
Ezio Melottib92ed7c2010-03-06 15:24:08 +0000800 literals[i] = encode(s)
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000801 i = i + 1
802 return groups, literals
Andrew M. Kuchling815d5b92000-06-09 14:08:07 +0000803
Fredrik Lundh436c3d582000-06-29 08:58:44 +0000804def expand_template(template, match):
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000805 g = match.group
Fredrik Lundh0640e112000-06-30 13:55:15 +0000806 sep = match.string[:0]
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000807 groups, literals = template
808 literals = literals[:]
809 try:
810 for index, group in groups:
811 literals[index] = s = g(group)
Fredrik Lundh90a07912000-06-30 07:50:59 +0000812 if s is None:
Collin Winterce36ad82007-08-30 01:19:48 +0000813 raise error("unmatched group")
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000814 except IndexError:
Collin Winterce36ad82007-08-30 01:19:48 +0000815 raise error("invalid group reference")
Barry Warsaw8bee7612004-08-25 02:22:30 +0000816 return sep.join(literals)