blob: f52ea014597665f3fdd5750204614c4c1b0c02f4 [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#
4# convert template to internal format
5#
Fredrik Lundh770617b2001-01-14 15:06:11 +00006# Copyright (c) 1997-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 Lundh4fb70272002-06-27 20:08:25 +000013import _sre, sys
Christian Heimes5e696852008-04-09 08:37:03 +000014import sre_parse
Guido van Rossum7627c0d2000-03-31 14:58:54 +000015from sre_constants import *
16
Fredrik Lundhb35ffc02001-01-15 12:46:09 +000017assert _sre.MAGIC == MAGIC, "SRE module mismatch"
18
Martin v. Löwis78e2f062003-04-19 12:56:08 +000019if _sre.CODESIZE == 2:
20 MAXCODE = 65535
21else:
Guido van Rossume2a383d2007-01-15 16:59:06 +000022 MAXCODE = 0xFFFFFFFF
Fredrik Lundh3562f112000-07-02 12:00:07 +000023
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000024def _identityfunction(x):
25 return x
26
Raymond Hettinger049ade22005-02-28 19:27:52 +000027_LITERAL_CODES = set([LITERAL, NOT_LITERAL])
28_REPEATING_CODES = set([REPEAT, MIN_REPEAT, MAX_REPEAT])
29_SUCCESS_CODES = set([SUCCESS, FAILURE])
30_ASSERT_CODES = set([ASSERT, ASSERT_NOT])
31
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000032def _compile(code, pattern, flags):
33 # internal: compile a (sub)pattern
34 emit = code.append
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000035 _len = len
Raymond Hettinger049ade22005-02-28 19:27:52 +000036 LITERAL_CODES = _LITERAL_CODES
37 REPEATING_CODES = _REPEATING_CODES
38 SUCCESS_CODES = _SUCCESS_CODES
39 ASSERT_CODES = _ASSERT_CODES
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000040 for op, av in pattern:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000041 if op in LITERAL_CODES:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000042 if flags & SRE_FLAG_IGNORECASE:
43 emit(OPCODES[OP_IGNORE[op]])
Fredrik Lundh2e240442001-01-15 18:28:14 +000044 emit(_sre.getlower(av, flags))
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000045 else:
46 emit(OPCODES[op])
Fredrik Lundh2e240442001-01-15 18:28:14 +000047 emit(av)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000048 elif op is IN:
49 if flags & SRE_FLAG_IGNORECASE:
50 emit(OPCODES[OP_IGNORE[op]])
51 def fixup(literal, flags=flags):
52 return _sre.getlower(literal, flags)
53 else:
54 emit(OPCODES[op])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000055 fixup = _identityfunction
56 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000057 _compile_charset(av, flags, code, fixup)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000058 code[skip] = _len(code) - skip
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000059 elif op is ANY:
60 if flags & SRE_FLAG_DOTALL:
61 emit(OPCODES[ANY_ALL])
62 else:
63 emit(OPCODES[ANY])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000064 elif op in REPEATING_CODES:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000065 if flags & SRE_FLAG_TEMPLATE:
Collin Winterce36ad82007-08-30 01:19:48 +000066 raise error("internal: unsupported template operator")
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000067 emit(OPCODES[REPEAT])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000068 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000069 emit(av[0])
70 emit(av[1])
71 _compile(code, av[2], flags)
72 emit(OPCODES[SUCCESS])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000073 code[skip] = _len(code) - skip
74 elif _simple(av) and op is not REPEAT:
75 if op is MAX_REPEAT:
Guido van Rossum41c99e72003-04-14 17:59:34 +000076 emit(OPCODES[REPEAT_ONE])
77 else:
78 emit(OPCODES[MIN_REPEAT_ONE])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000079 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000080 emit(av[0])
81 emit(av[1])
82 _compile(code, av[2], flags)
83 emit(OPCODES[SUCCESS])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000084 code[skip] = _len(code) - skip
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000085 else:
86 emit(OPCODES[REPEAT])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000087 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000088 emit(av[0])
89 emit(av[1])
90 _compile(code, av[2], flags)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000091 code[skip] = _len(code) - skip
92 if op is MAX_REPEAT:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000093 emit(OPCODES[MAX_UNTIL])
94 else:
95 emit(OPCODES[MIN_UNTIL])
96 elif op is SUBPATTERN:
97 if av[0]:
98 emit(OPCODES[MARK])
99 emit((av[0]-1)*2)
100 # _compile_info(code, av[1], flags)
101 _compile(code, av[1], flags)
102 if av[0]:
103 emit(OPCODES[MARK])
104 emit((av[0]-1)*2+1)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000105 elif op in SUCCESS_CODES:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000106 emit(OPCODES[op])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000107 elif op in ASSERT_CODES:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000108 emit(OPCODES[op])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000109 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000110 if av[0] >= 0:
111 emit(0) # look ahead
112 else:
113 lo, hi = av[1].getwidth()
114 if lo != hi:
Collin Winterce36ad82007-08-30 01:19:48 +0000115 raise error("look-behind requires fixed-width pattern")
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000116 emit(lo) # look behind
117 _compile(code, av[1], flags)
118 emit(OPCODES[SUCCESS])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000119 code[skip] = _len(code) - skip
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000120 elif op is CALL:
121 emit(OPCODES[op])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000122 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000123 _compile(code, av, flags)
124 emit(OPCODES[SUCCESS])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000125 code[skip] = _len(code) - skip
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000126 elif op is AT:
127 emit(OPCODES[op])
128 if flags & SRE_FLAG_MULTILINE:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000129 av = AT_MULTILINE.get(av, av)
130 if flags & SRE_FLAG_LOCALE:
131 av = AT_LOCALE.get(av, av)
132 elif flags & SRE_FLAG_UNICODE:
133 av = AT_UNICODE.get(av, av)
134 emit(ATCODES[av])
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000135 elif op is BRANCH:
136 emit(OPCODES[op])
137 tail = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000138 tailappend = tail.append
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000139 for av in av[1]:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000140 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000141 # _compile_info(code, av, flags)
142 _compile(code, av, flags)
143 emit(OPCODES[JUMP])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000144 tailappend(_len(code)); emit(0)
145 code[skip] = _len(code) - skip
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000146 emit(0) # end of branch
147 for tail in tail:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000148 code[tail] = _len(code) - tail
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000149 elif op is CATEGORY:
150 emit(OPCODES[op])
151 if flags & SRE_FLAG_LOCALE:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000152 av = CH_LOCALE[av]
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000153 elif flags & SRE_FLAG_UNICODE:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000154 av = CH_UNICODE[av]
155 emit(CHCODES[av])
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000156 elif op is GROUPREF:
157 if flags & SRE_FLAG_IGNORECASE:
158 emit(OPCODES[OP_IGNORE[op]])
159 else:
160 emit(OPCODES[op])
161 emit(av-1)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000162 elif op is GROUPREF_EXISTS:
163 emit(OPCODES[op])
Andrew M. Kuchlingc30faa82005-06-02 13:35:52 +0000164 emit(av[0]-1)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000165 skipyes = _len(code); emit(0)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000166 _compile(code, av[1], flags)
167 if av[2]:
168 emit(OPCODES[JUMP])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000169 skipno = _len(code); emit(0)
170 code[skipyes] = _len(code) - skipyes + 1
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000171 _compile(code, av[2], flags)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000172 code[skipno] = _len(code) - skipno
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000173 else:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000174 code[skipyes] = _len(code) - skipyes + 1
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000175 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000176 raise ValueError("unsupported operand type", op)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000177
178def _compile_charset(charset, flags, code, fixup=None):
179 # compile charset subprogram
180 emit = code.append
Raymond Hettingerf13eb552002-06-02 00:40:05 +0000181 if fixup is None:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000182 fixup = _identityfunction
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000183 for op, av in _optimize_charset(charset, fixup):
184 emit(OPCODES[op])
185 if op is NEGATE:
186 pass
187 elif op is LITERAL:
188 emit(fixup(av))
189 elif op is RANGE:
190 emit(fixup(av[0]))
191 emit(fixup(av[1]))
192 elif op is CHARSET:
193 code.extend(av)
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000194 elif op is BIGCHARSET:
195 code.extend(av)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000196 elif op is CATEGORY:
197 if flags & SRE_FLAG_LOCALE:
198 emit(CHCODES[CH_LOCALE[av]])
199 elif flags & SRE_FLAG_UNICODE:
200 emit(CHCODES[CH_UNICODE[av]])
201 else:
202 emit(CHCODES[av])
203 else:
Collin Winterce36ad82007-08-30 01:19:48 +0000204 raise error("internal: unsupported set operator")
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000205 emit(OPCODES[FAILURE])
206
207def _optimize_charset(charset, fixup):
208 # internal: optimize character set
Fredrik Lundh3562f112000-07-02 12:00:07 +0000209 out = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000210 outappend = out.append
Raymond Hettingerd732c952004-03-27 09:24:36 +0000211 charmap = [0]*256
Fredrik Lundh3562f112000-07-02 12:00:07 +0000212 try:
213 for op, av in charset:
214 if op is NEGATE:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000215 outappend((op, av))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000216 elif op is LITERAL:
Raymond Hettingerd732c952004-03-27 09:24:36 +0000217 charmap[fixup(av)] = 1
Fredrik Lundh3562f112000-07-02 12:00:07 +0000218 elif op is RANGE:
219 for i in range(fixup(av[0]), fixup(av[1])+1):
Raymond Hettingerd732c952004-03-27 09:24:36 +0000220 charmap[i] = 1
Fredrik Lundh3562f112000-07-02 12:00:07 +0000221 elif op is CATEGORY:
Fredrik Lundh770617b2001-01-14 15:06:11 +0000222 # XXX: could append to charmap tail
Fredrik Lundh3562f112000-07-02 12:00:07 +0000223 return charset # cannot compress
224 except IndexError:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000225 # character set contains unicode characters
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000226 return _optimize_unicode(charset, fixup)
Fredrik Lundh3562f112000-07-02 12:00:07 +0000227 # compress character map
228 i = p = n = 0
229 runs = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000230 runsappend = runs.append
Fredrik Lundh3562f112000-07-02 12:00:07 +0000231 for c in charmap:
232 if c:
233 if n == 0:
234 p = i
235 n = n + 1
236 elif n:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000237 runsappend((p, n))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000238 n = 0
239 i = i + 1
240 if n:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000241 runsappend((p, n))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000242 if len(runs) <= 2:
243 # use literal/range
244 for p, n in runs:
245 if n == 1:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000246 outappend((LITERAL, p))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000247 else:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000248 outappend((RANGE, (p, p+n-1)))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000249 if len(out) < len(charset):
250 return out
251 else:
252 # use bitmap
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000253 data = _mk_bitmap(charmap)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000254 outappend((CHARSET, data))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000255 return out
256 return charset
257
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000258def _mk_bitmap(bits):
259 data = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000260 dataappend = data.append
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000261 if _sre.CODESIZE == 2:
262 start = (1, 0)
263 else:
Guido van Rossume2a383d2007-01-15 16:59:06 +0000264 start = (1, 0)
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000265 m, v = start
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000266 for c in bits:
267 if c:
268 v = v + m
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000269 m = m + m
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000270 if m > MAXCODE:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000271 dataappend(v)
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000272 m, v = start
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000273 return data
274
275# To represent a big charset, first a bitmap of all characters in the
276# set is constructed. Then, this bitmap is sliced into chunks of 256
Guido van Rossum992d4a32007-07-11 13:09:30 +0000277# characters, duplicate chunks are eliminated, and each chunk is
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000278# given a number. In the compiled expression, the charset is
279# represented by a 16-bit word sequence, consisting of one word for
280# the number of different chunks, a sequence of 256 bytes (128 words)
281# of chunk numbers indexed by their original chunk position, and a
282# sequence of chunks (16 words each).
283
284# Compression is normally good: in a typical charset, large ranges of
285# Unicode will be either completely excluded (e.g. if only cyrillic
286# letters are to be matched), or completely included (e.g. if large
287# subranges of Kanji match). These ranges will be represented by
288# chunks of all one-bits or all zero-bits.
289
290# Matching can be also done efficiently: the more significant byte of
291# the Unicode character is an index into the chunk number, and the
292# less significant byte is a bit index in the chunk (just like the
293# CHARSET matching).
294
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000295# In UCS-4 mode, the BIGCHARSET opcode still supports only subsets
296# of the basic multilingual plane; an efficient representation
297# for all of UTF-16 has not yet been developed. This means,
298# in particular, that negated charsets cannot be represented as
299# bigcharsets.
300
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000301def _optimize_unicode(charset, fixup):
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000302 try:
303 import array
304 except ImportError:
305 return charset
Raymond Hettingerd732c952004-03-27 09:24:36 +0000306 charmap = [0]*65536
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000307 negate = 0
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000308 try:
309 for op, av in charset:
310 if op is NEGATE:
311 negate = 1
312 elif op is LITERAL:
Raymond Hettingerd732c952004-03-27 09:24:36 +0000313 charmap[fixup(av)] = 1
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000314 elif op is RANGE:
Guido van Rossum805365e2007-05-07 22:24:25 +0000315 for i in range(fixup(av[0]), fixup(av[1])+1):
Raymond Hettingerd732c952004-03-27 09:24:36 +0000316 charmap[i] = 1
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000317 elif op is CATEGORY:
318 # XXX: could expand category
319 return charset # cannot compress
320 except IndexError:
321 # non-BMP characters
322 return charset
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000323 if negate:
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000324 if sys.maxunicode != 65535:
325 # XXX: negation does not work with big charsets
326 return charset
Guido van Rossum805365e2007-05-07 22:24:25 +0000327 for i in range(65536):
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000328 charmap[i] = not charmap[i]
329 comps = {}
330 mapping = [0]*256
331 block = 0
332 data = []
Guido van Rossum805365e2007-05-07 22:24:25 +0000333 for i in range(256):
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000334 chunk = tuple(charmap[i*256:(i+1)*256])
335 new = comps.setdefault(chunk, block)
336 mapping[i] = new
337 if new == block:
Fredrik Lundh4fb70272002-06-27 20:08:25 +0000338 block = block + 1
339 data = data + _mk_bitmap(chunk)
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000340 header = [block]
Martin v. Löwis7d9c6c72004-05-07 07:18:13 +0000341 if _sre.CODESIZE == 2:
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000342 code = 'H'
343 else:
Martin v. Löwis7d9c6c72004-05-07 07:18:13 +0000344 code = 'I'
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000345 # Convert block indices to byte array of 256 bytes
Antoine Pitrou1ce3eb52010-09-01 20:29:34 +0000346 mapping = array.array('b', mapping).tobytes()
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000347 # Convert byte array to word array
Martin v. Löwis7d9c6c72004-05-07 07:18:13 +0000348 mapping = array.array(code, mapping)
349 assert mapping.itemsize == _sre.CODESIZE
Guido van Rossum6b826ab2007-07-03 16:22:09 +0000350 assert len(mapping) * mapping.itemsize == 256
Martin v. Löwis7d9c6c72004-05-07 07:18:13 +0000351 header = header + mapping.tolist()
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000352 data[0:0] = header
Tim Peters87cc0c32001-07-21 01:41:30 +0000353 return [(BIGCHARSET, data)]
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000354
Fredrik Lundhe1869832000-08-01 22:47:49 +0000355def _simple(av):
356 # check if av is a "simple" operator
357 lo, hi = av[2].getwidth()
Fredrik Lundh13ac9922000-10-07 17:38:23 +0000358 if lo == 0 and hi == MAXREPEAT:
Collin Winterce36ad82007-08-30 01:19:48 +0000359 raise error("nothing to repeat")
Fredrik Lundhe1869832000-08-01 22:47:49 +0000360 return lo == hi == 1 and av[2][0][0] != SUBPATTERN
361
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000362def _compile_info(code, pattern, flags):
363 # internal: compile an info block. in the current version,
Fredrik Lundh3562f112000-07-02 12:00:07 +0000364 # this contains min/max pattern width, and an optional literal
365 # prefix or a character map
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000366 lo, hi = pattern.getwidth()
367 if lo == 0:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000368 return # not worth it
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000369 # look for a literal prefix
370 prefix = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000371 prefixappend = prefix.append
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000372 prefix_skip = 0
Fredrik Lundh3562f112000-07-02 12:00:07 +0000373 charset = [] # not used
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000374 charsetappend = charset.append
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000375 if not (flags & SRE_FLAG_IGNORECASE):
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000376 # look for literal prefix
Fredrik Lundh90a07912000-06-30 07:50:59 +0000377 for op, av in pattern.data:
378 if op is LITERAL:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000379 if len(prefix) == prefix_skip:
380 prefix_skip = prefix_skip + 1
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000381 prefixappend(av)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000382 elif op is SUBPATTERN and len(av[1]) == 1:
383 op, av = av[1][0]
384 if op is LITERAL:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000385 prefixappend(av)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000386 else:
387 break
Fredrik Lundh90a07912000-06-30 07:50:59 +0000388 else:
389 break
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000390 # if no prefix, look for charset prefix
391 if not prefix and pattern.data:
392 op, av = pattern.data[0]
393 if op is SUBPATTERN and av[1]:
394 op, av = av[1][0]
395 if op is LITERAL:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000396 charsetappend((op, av))
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000397 elif op is BRANCH:
398 c = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000399 cappend = c.append
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000400 for p in av[1]:
401 if not p:
402 break
403 op, av = p[0]
404 if op is LITERAL:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000405 cappend((op, av))
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000406 else:
407 break
408 else:
409 charset = c
410 elif op is BRANCH:
411 c = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000412 cappend = c.append
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000413 for p in av[1]:
414 if not p:
415 break
416 op, av = p[0]
417 if op is LITERAL:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000418 cappend((op, av))
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000419 else:
420 break
421 else:
422 charset = c
423 elif op is IN:
424 charset = av
425## if prefix:
426## print "*** PREFIX", prefix, prefix_skip
427## if charset:
428## print "*** CHARSET", charset
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000429 # add an info block
430 emit = code.append
431 emit(OPCODES[INFO])
432 skip = len(code); emit(0)
433 # literal flag
434 mask = 0
Fredrik Lundh3562f112000-07-02 12:00:07 +0000435 if prefix:
436 mask = SRE_INFO_PREFIX
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000437 if len(prefix) == prefix_skip == len(pattern.data):
Fredrik Lundh3562f112000-07-02 12:00:07 +0000438 mask = mask + SRE_INFO_LITERAL
439 elif charset:
440 mask = mask + SRE_INFO_CHARSET
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000441 emit(mask)
442 # pattern length
Fredrik Lundh3562f112000-07-02 12:00:07 +0000443 if lo < MAXCODE:
444 emit(lo)
445 else:
446 emit(MAXCODE)
447 prefix = prefix[:MAXCODE]
448 if hi < MAXCODE:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000449 emit(hi)
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000450 else:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000451 emit(0)
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000452 # add literal prefix
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000453 if prefix:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000454 emit(len(prefix)) # length
455 emit(prefix_skip) # skip
456 code.extend(prefix)
457 # generate overlap table
458 table = [-1] + ([0]*len(prefix))
Guido van Rossum805365e2007-05-07 22:24:25 +0000459 for i in range(len(prefix)):
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000460 table[i+1] = table[i]+1
461 while table[i+1] > 0 and prefix[i] != prefix[table[i+1]-1]:
462 table[i+1] = table[table[i+1]-1]+1
463 code.extend(table[1:]) # don't store first entry
Fredrik Lundh3562f112000-07-02 12:00:07 +0000464 elif charset:
Guido van Rossum577fb5a2003-02-24 01:18:35 +0000465 _compile_charset(charset, flags, code)
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000466 code[skip] = len(code) - skip
467
Just van Rossum74902502003-07-02 21:37:16 +0000468def isstring(obj):
Thomas Wouters40a088d2008-03-18 20:19:54 +0000469 return isinstance(obj, (str, bytes))
Just van Rossum74902502003-07-02 21:37:16 +0000470
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000471def _code(p, flags):
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000472
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000473 flags = p.pattern.flags | flags
Fredrik Lundhbe2211e2000-06-29 16:57:40 +0000474 code = []
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000475
476 # compile info block
477 _compile_info(code, p, flags)
478
479 # compile the pattern
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000480 _compile(code, p.data, flags)
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000481
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000482 code.append(OPCODES[SUCCESS])
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000483
Fredrik Lundh29c4ba92000-08-01 18:20:07 +0000484 return code
485
486def compile(p, flags=0):
487 # internal: convert pattern list to internal format
488
Just van Rossum74902502003-07-02 21:37:16 +0000489 if isstring(p):
Fredrik Lundh29c4ba92000-08-01 18:20:07 +0000490 pattern = p
491 p = sre_parse.parse(p, flags)
492 else:
493 pattern = None
494
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000495 code = _code(p, flags)
Fredrik Lundh29c4ba92000-08-01 18:20:07 +0000496
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000497 # print code
498
Fredrik Lundh770617b2001-01-14 15:06:11 +0000499 # XXX: <fl> get rid of this limitation!
Fredrik Lundh5e7d51b2004-10-15 06:15:08 +0000500 if p.pattern.groups > 100:
501 raise AssertionError(
502 "sorry, but this version only supports 100 named groups"
503 )
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000504
Fredrik Lundhc2301732000-07-02 22:25:39 +0000505 # map in either direction
506 groupindex = p.pattern.groupdict
507 indexgroup = [None] * p.pattern.groups
508 for k, i in groupindex.items():
509 indexgroup[i] = k
510
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000511 return _sre.compile(
Christian Heimes072c0f12008-01-03 23:01:04 +0000512 pattern, flags | p.pattern.flags, code,
Fredrik Lundh6f013982000-07-03 18:44:21 +0000513 p.pattern.groups-1,
514 groupindex, indexgroup
Fredrik Lundh90a07912000-06-30 07:50:59 +0000515 )