blob: 1d448dae2ac42fa82759503a9d083f3e8072d225 [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
Guido van Rossum7627c0d2000-03-31 14:58:54 +000014
15from 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:
22 MAXCODE = 0xFFFFFFFFL
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 +000027def set(seq):
28 s = {}
29 for elem in seq:
30 s[elem] = 1
31 return s
32
33_LITERAL_CODES = set([LITERAL, NOT_LITERAL])
34_REPEATING_CODES = set([REPEAT, MIN_REPEAT, MAX_REPEAT])
35_SUCCESS_CODES = set([SUCCESS, FAILURE])
36_ASSERT_CODES = set([ASSERT, ASSERT_NOT])
37
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000038def _compile(code, pattern, flags):
39 # internal: compile a (sub)pattern
40 emit = code.append
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000041 _len = len
Raymond Hettinger049ade22005-02-28 19:27:52 +000042 LITERAL_CODES = _LITERAL_CODES
43 REPEATING_CODES = _REPEATING_CODES
44 SUCCESS_CODES = _SUCCESS_CODES
45 ASSERT_CODES = _ASSERT_CODES
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000046 for op, av in pattern:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000047 if op in LITERAL_CODES:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000048 if flags & SRE_FLAG_IGNORECASE:
49 emit(OPCODES[OP_IGNORE[op]])
Fredrik Lundh2e240442001-01-15 18:28:14 +000050 emit(_sre.getlower(av, flags))
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000051 else:
52 emit(OPCODES[op])
Fredrik Lundh2e240442001-01-15 18:28:14 +000053 emit(av)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000054 elif op is IN:
55 if flags & SRE_FLAG_IGNORECASE:
56 emit(OPCODES[OP_IGNORE[op]])
57 def fixup(literal, flags=flags):
58 return _sre.getlower(literal, flags)
59 else:
60 emit(OPCODES[op])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000061 fixup = _identityfunction
62 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000063 _compile_charset(av, flags, code, fixup)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000064 code[skip] = _len(code) - skip
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000065 elif op is ANY:
66 if flags & SRE_FLAG_DOTALL:
67 emit(OPCODES[ANY_ALL])
68 else:
69 emit(OPCODES[ANY])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000070 elif op in REPEATING_CODES:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000071 if flags & SRE_FLAG_TEMPLATE:
72 raise error, "internal: unsupported template operator"
73 emit(OPCODES[REPEAT])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000074 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000075 emit(av[0])
76 emit(av[1])
77 _compile(code, av[2], flags)
78 emit(OPCODES[SUCCESS])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000079 code[skip] = _len(code) - skip
80 elif _simple(av) and op is not REPEAT:
81 if op is MAX_REPEAT:
Guido van Rossum41c99e72003-04-14 17:59:34 +000082 emit(OPCODES[REPEAT_ONE])
83 else:
84 emit(OPCODES[MIN_REPEAT_ONE])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000085 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000086 emit(av[0])
87 emit(av[1])
88 _compile(code, av[2], flags)
89 emit(OPCODES[SUCCESS])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000090 code[skip] = _len(code) - skip
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000091 else:
92 emit(OPCODES[REPEAT])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000093 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000094 emit(av[0])
95 emit(av[1])
96 _compile(code, av[2], flags)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +000097 code[skip] = _len(code) - skip
98 if op is MAX_REPEAT:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +000099 emit(OPCODES[MAX_UNTIL])
100 else:
101 emit(OPCODES[MIN_UNTIL])
102 elif op is SUBPATTERN:
103 if av[0]:
104 emit(OPCODES[MARK])
105 emit((av[0]-1)*2)
106 # _compile_info(code, av[1], flags)
107 _compile(code, av[1], flags)
108 if av[0]:
109 emit(OPCODES[MARK])
110 emit((av[0]-1)*2+1)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000111 elif op in SUCCESS_CODES:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000112 emit(OPCODES[op])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000113 elif op in ASSERT_CODES:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000114 emit(OPCODES[op])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000115 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000116 if av[0] >= 0:
117 emit(0) # look ahead
118 else:
119 lo, hi = av[1].getwidth()
120 if lo != hi:
121 raise error, "look-behind requires fixed-width pattern"
122 emit(lo) # look behind
123 _compile(code, av[1], 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 CALL:
127 emit(OPCODES[op])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000128 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000129 _compile(code, av, flags)
130 emit(OPCODES[SUCCESS])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000131 code[skip] = _len(code) - skip
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000132 elif op is AT:
133 emit(OPCODES[op])
134 if flags & SRE_FLAG_MULTILINE:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000135 av = AT_MULTILINE.get(av, av)
136 if flags & SRE_FLAG_LOCALE:
137 av = AT_LOCALE.get(av, av)
138 elif flags & SRE_FLAG_UNICODE:
139 av = AT_UNICODE.get(av, av)
140 emit(ATCODES[av])
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000141 elif op is BRANCH:
142 emit(OPCODES[op])
143 tail = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000144 tailappend = tail.append
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000145 for av in av[1]:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000146 skip = _len(code); emit(0)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000147 # _compile_info(code, av, flags)
148 _compile(code, av, flags)
149 emit(OPCODES[JUMP])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000150 tailappend(_len(code)); emit(0)
151 code[skip] = _len(code) - skip
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000152 emit(0) # end of branch
153 for tail in tail:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000154 code[tail] = _len(code) - tail
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000155 elif op is CATEGORY:
156 emit(OPCODES[op])
157 if flags & SRE_FLAG_LOCALE:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000158 av = CH_LOCALE[av]
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000159 elif flags & SRE_FLAG_UNICODE:
Fredrik Lundhb25e1ad2001-03-22 15:50:10 +0000160 av = CH_UNICODE[av]
161 emit(CHCODES[av])
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000162 elif op is GROUPREF:
163 if flags & SRE_FLAG_IGNORECASE:
164 emit(OPCODES[OP_IGNORE[op]])
165 else:
166 emit(OPCODES[op])
167 emit(av-1)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000168 elif op is GROUPREF_EXISTS:
169 emit(OPCODES[op])
Andrew M. Kuchlingc30faa82005-06-02 13:35:52 +0000170 emit(av[0]-1)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000171 skipyes = _len(code); emit(0)
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000172 _compile(code, av[1], flags)
173 if av[2]:
174 emit(OPCODES[JUMP])
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000175 skipno = _len(code); emit(0)
176 code[skipyes] = _len(code) - skipyes + 1
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000177 _compile(code, av[2], flags)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000178 code[skipno] = _len(code) - skipno
Gustavo Niemeyerad3fc442003-10-17 22:13:16 +0000179 else:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000180 code[skipyes] = _len(code) - skipyes + 1
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000181 else:
182 raise ValueError, ("unsupported operand type", op)
183
184def _compile_charset(charset, flags, code, fixup=None):
185 # compile charset subprogram
186 emit = code.append
Raymond Hettingerf13eb552002-06-02 00:40:05 +0000187 if fixup is None:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000188 fixup = _identityfunction
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000189 for op, av in _optimize_charset(charset, fixup):
190 emit(OPCODES[op])
191 if op is NEGATE:
192 pass
193 elif op is LITERAL:
194 emit(fixup(av))
195 elif op is RANGE:
196 emit(fixup(av[0]))
197 emit(fixup(av[1]))
198 elif op is CHARSET:
199 code.extend(av)
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000200 elif op is BIGCHARSET:
201 code.extend(av)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000202 elif op is CATEGORY:
203 if flags & SRE_FLAG_LOCALE:
204 emit(CHCODES[CH_LOCALE[av]])
205 elif flags & SRE_FLAG_UNICODE:
206 emit(CHCODES[CH_UNICODE[av]])
207 else:
208 emit(CHCODES[av])
209 else:
210 raise error, "internal: unsupported set operator"
211 emit(OPCODES[FAILURE])
212
213def _optimize_charset(charset, fixup):
214 # internal: optimize character set
Fredrik Lundh3562f112000-07-02 12:00:07 +0000215 out = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000216 outappend = out.append
Raymond Hettingerd732c952004-03-27 09:24:36 +0000217 charmap = [0]*256
Fredrik Lundh3562f112000-07-02 12:00:07 +0000218 try:
219 for op, av in charset:
220 if op is NEGATE:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000221 outappend((op, av))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000222 elif op is LITERAL:
Raymond Hettingerd732c952004-03-27 09:24:36 +0000223 charmap[fixup(av)] = 1
Fredrik Lundh3562f112000-07-02 12:00:07 +0000224 elif op is RANGE:
225 for i in range(fixup(av[0]), fixup(av[1])+1):
Raymond Hettingerd732c952004-03-27 09:24:36 +0000226 charmap[i] = 1
Fredrik Lundh3562f112000-07-02 12:00:07 +0000227 elif op is CATEGORY:
Fredrik Lundh770617b2001-01-14 15:06:11 +0000228 # XXX: could append to charmap tail
Fredrik Lundh3562f112000-07-02 12:00:07 +0000229 return charset # cannot compress
230 except IndexError:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000231 # character set contains unicode characters
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000232 return _optimize_unicode(charset, fixup)
Fredrik Lundh3562f112000-07-02 12:00:07 +0000233 # compress character map
234 i = p = n = 0
235 runs = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000236 runsappend = runs.append
Fredrik Lundh3562f112000-07-02 12:00:07 +0000237 for c in charmap:
238 if c:
239 if n == 0:
240 p = i
241 n = n + 1
242 elif n:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000243 runsappend((p, n))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000244 n = 0
245 i = i + 1
246 if n:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000247 runsappend((p, n))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000248 if len(runs) <= 2:
249 # use literal/range
250 for p, n in runs:
251 if n == 1:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000252 outappend((LITERAL, p))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000253 else:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000254 outappend((RANGE, (p, p+n-1)))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000255 if len(out) < len(charset):
256 return out
257 else:
258 # use bitmap
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000259 data = _mk_bitmap(charmap)
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000260 outappend((CHARSET, data))
Fredrik Lundh3562f112000-07-02 12:00:07 +0000261 return out
262 return charset
263
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000264def _mk_bitmap(bits):
265 data = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000266 dataappend = data.append
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000267 if _sre.CODESIZE == 2:
268 start = (1, 0)
269 else:
270 start = (1L, 0L)
271 m, v = start
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000272 for c in bits:
273 if c:
274 v = v + m
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000275 m = m + m
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000276 if m > MAXCODE:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000277 dataappend(v)
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000278 m, v = start
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000279 return data
280
281# To represent a big charset, first a bitmap of all characters in the
282# set is constructed. Then, this bitmap is sliced into chunks of 256
283# characters, duplicate chunks are eliminitated, and each chunk is
284# given a number. In the compiled expression, the charset is
285# represented by a 16-bit word sequence, consisting of one word for
286# the number of different chunks, a sequence of 256 bytes (128 words)
287# of chunk numbers indexed by their original chunk position, and a
288# sequence of chunks (16 words each).
289
290# Compression is normally good: in a typical charset, large ranges of
291# Unicode will be either completely excluded (e.g. if only cyrillic
292# letters are to be matched), or completely included (e.g. if large
293# subranges of Kanji match). These ranges will be represented by
294# chunks of all one-bits or all zero-bits.
295
296# Matching can be also done efficiently: the more significant byte of
297# the Unicode character is an index into the chunk number, and the
298# less significant byte is a bit index in the chunk (just like the
299# CHARSET matching).
300
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000301# In UCS-4 mode, the BIGCHARSET opcode still supports only subsets
302# of the basic multilingual plane; an efficient representation
303# for all of UTF-16 has not yet been developed. This means,
304# in particular, that negated charsets cannot be represented as
305# bigcharsets.
306
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000307def _optimize_unicode(charset, fixup):
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000308 try:
309 import array
310 except ImportError:
311 return charset
Raymond Hettingerd732c952004-03-27 09:24:36 +0000312 charmap = [0]*65536
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000313 negate = 0
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000314 try:
315 for op, av in charset:
316 if op is NEGATE:
317 negate = 1
318 elif op is LITERAL:
Raymond Hettingerd732c952004-03-27 09:24:36 +0000319 charmap[fixup(av)] = 1
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000320 elif op is RANGE:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000321 for i in xrange(fixup(av[0]), fixup(av[1])+1):
Raymond Hettingerd732c952004-03-27 09:24:36 +0000322 charmap[i] = 1
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000323 elif op is CATEGORY:
324 # XXX: could expand category
325 return charset # cannot compress
326 except IndexError:
327 # non-BMP characters
328 return charset
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000329 if negate:
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000330 if sys.maxunicode != 65535:
331 # XXX: negation does not work with big charsets
332 return charset
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000333 for i in xrange(65536):
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000334 charmap[i] = not charmap[i]
335 comps = {}
336 mapping = [0]*256
337 block = 0
338 data = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000339 for i in xrange(256):
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000340 chunk = tuple(charmap[i*256:(i+1)*256])
341 new = comps.setdefault(chunk, block)
342 mapping[i] = new
343 if new == block:
Fredrik Lundh4fb70272002-06-27 20:08:25 +0000344 block = block + 1
345 data = data + _mk_bitmap(chunk)
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000346 header = [block]
Martin v. Löwis7d9c6c72004-05-07 07:18:13 +0000347 if _sre.CODESIZE == 2:
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000348 code = 'H'
349 else:
Martin v. Löwis7d9c6c72004-05-07 07:18:13 +0000350 code = 'I'
Martin v. Löwis78e2f062003-04-19 12:56:08 +0000351 # Convert block indices to byte array of 256 bytes
352 mapping = array.array('b', mapping).tostring()
353 # Convert byte array to word array
Martin v. Löwis7d9c6c72004-05-07 07:18:13 +0000354 mapping = array.array(code, mapping)
355 assert mapping.itemsize == _sre.CODESIZE
356 header = header + mapping.tolist()
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000357 data[0:0] = header
Tim Peters87cc0c32001-07-21 01:41:30 +0000358 return [(BIGCHARSET, data)]
Fredrik Lundh19af43d2001-07-02 16:58:38 +0000359
Fredrik Lundhe1869832000-08-01 22:47:49 +0000360def _simple(av):
361 # check if av is a "simple" operator
362 lo, hi = av[2].getwidth()
Fredrik Lundh13ac9922000-10-07 17:38:23 +0000363 if lo == 0 and hi == MAXREPEAT:
Fredrik Lundhe1869832000-08-01 22:47:49 +0000364 raise error, "nothing to repeat"
365 return lo == hi == 1 and av[2][0][0] != SUBPATTERN
366
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000367def _compile_info(code, pattern, flags):
368 # internal: compile an info block. in the current version,
Fredrik Lundh3562f112000-07-02 12:00:07 +0000369 # this contains min/max pattern width, and an optional literal
370 # prefix or a character map
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000371 lo, hi = pattern.getwidth()
372 if lo == 0:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000373 return # not worth it
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000374 # look for a literal prefix
375 prefix = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000376 prefixappend = prefix.append
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000377 prefix_skip = 0
Fredrik Lundh3562f112000-07-02 12:00:07 +0000378 charset = [] # not used
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000379 charsetappend = charset.append
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000380 if not (flags & SRE_FLAG_IGNORECASE):
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000381 # look for literal prefix
Fredrik Lundh90a07912000-06-30 07:50:59 +0000382 for op, av in pattern.data:
383 if op is LITERAL:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000384 if len(prefix) == prefix_skip:
385 prefix_skip = prefix_skip + 1
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000386 prefixappend(av)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000387 elif op is SUBPATTERN and len(av[1]) == 1:
388 op, av = av[1][0]
389 if op is LITERAL:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000390 prefixappend(av)
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000391 else:
392 break
Fredrik Lundh90a07912000-06-30 07:50:59 +0000393 else:
394 break
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000395 # if no prefix, look for charset prefix
396 if not prefix and pattern.data:
397 op, av = pattern.data[0]
398 if op is SUBPATTERN and av[1]:
399 op, av = av[1][0]
400 if op is LITERAL:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000401 charsetappend((op, av))
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000402 elif op is BRANCH:
403 c = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000404 cappend = c.append
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000405 for p in av[1]:
406 if not p:
407 break
408 op, av = p[0]
409 if op is LITERAL:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000410 cappend((op, av))
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000411 else:
412 break
413 else:
414 charset = c
415 elif op is BRANCH:
416 c = []
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000417 cappend = c.append
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000418 for p in av[1]:
419 if not p:
420 break
421 op, av = p[0]
422 if op is LITERAL:
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000423 cappend((op, av))
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000424 else:
425 break
426 else:
427 charset = c
428 elif op is IN:
429 charset = av
430## if prefix:
431## print "*** PREFIX", prefix, prefix_skip
432## if charset:
433## print "*** CHARSET", charset
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000434 # add an info block
435 emit = code.append
436 emit(OPCODES[INFO])
437 skip = len(code); emit(0)
438 # literal flag
439 mask = 0
Fredrik Lundh3562f112000-07-02 12:00:07 +0000440 if prefix:
441 mask = SRE_INFO_PREFIX
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000442 if len(prefix) == prefix_skip == len(pattern.data):
Fredrik Lundh3562f112000-07-02 12:00:07 +0000443 mask = mask + SRE_INFO_LITERAL
444 elif charset:
445 mask = mask + SRE_INFO_CHARSET
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000446 emit(mask)
447 # pattern length
Fredrik Lundh3562f112000-07-02 12:00:07 +0000448 if lo < MAXCODE:
449 emit(lo)
450 else:
451 emit(MAXCODE)
452 prefix = prefix[:MAXCODE]
453 if hi < MAXCODE:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000454 emit(hi)
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000455 else:
Fredrik Lundh90a07912000-06-30 07:50:59 +0000456 emit(0)
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000457 # add literal prefix
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000458 if prefix:
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000459 emit(len(prefix)) # length
460 emit(prefix_skip) # skip
461 code.extend(prefix)
462 # generate overlap table
463 table = [-1] + ([0]*len(prefix))
Raymond Hettinger01c9f8c2004-03-26 11:16:55 +0000464 for i in xrange(len(prefix)):
Fredrik Lundh7898c3e2000-08-07 20:59:04 +0000465 table[i+1] = table[i]+1
466 while table[i+1] > 0 and prefix[i] != prefix[table[i+1]-1]:
467 table[i+1] = table[table[i+1]-1]+1
468 code.extend(table[1:]) # don't store first entry
Fredrik Lundh3562f112000-07-02 12:00:07 +0000469 elif charset:
Guido van Rossum577fb5a2003-02-24 01:18:35 +0000470 _compile_charset(charset, flags, code)
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000471 code[skip] = len(code) - skip
472
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000473try:
Just van Rossum12723ba2003-07-02 20:03:04 +0000474 unicode
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000475except NameError:
Just van Rossum74902502003-07-02 21:37:16 +0000476 STRING_TYPES = (type(""),)
Just van Rossum12723ba2003-07-02 20:03:04 +0000477else:
478 STRING_TYPES = (type(""), type(unicode("")))
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000479
Just van Rossum74902502003-07-02 21:37:16 +0000480def isstring(obj):
481 for tp in STRING_TYPES:
482 if isinstance(obj, tp):
483 return 1
484 return 0
485
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000486def _code(p, flags):
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000487
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000488 flags = p.pattern.flags | flags
Fredrik Lundhbe2211e2000-06-29 16:57:40 +0000489 code = []
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000490
491 # compile info block
492 _compile_info(code, p, flags)
493
494 # compile the pattern
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000495 _compile(code, p.data, flags)
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000496
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000497 code.append(OPCODES[SUCCESS])
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000498
Fredrik Lundh29c4ba92000-08-01 18:20:07 +0000499 return code
500
501def compile(p, flags=0):
502 # internal: convert pattern list to internal format
503
Just van Rossum74902502003-07-02 21:37:16 +0000504 if isstring(p):
Fredrik Lundh29c4ba92000-08-01 18:20:07 +0000505 import sre_parse
506 pattern = p
507 p = sre_parse.parse(p, flags)
508 else:
509 pattern = None
510
Fredrik Lundh2f2c67d2000-08-01 21:05:41 +0000511 code = _code(p, flags)
Fredrik Lundh29c4ba92000-08-01 18:20:07 +0000512
Fredrik Lundh8a3ebf82000-07-23 21:46:17 +0000513 # print code
514
Fredrik Lundh770617b2001-01-14 15:06:11 +0000515 # XXX: <fl> get rid of this limitation!
Fredrik Lundh5e7d51b2004-10-15 06:15:08 +0000516 if p.pattern.groups > 100:
517 raise AssertionError(
518 "sorry, but this version only supports 100 named groups"
519 )
Fredrik Lundh29c08be2000-06-29 23:33:12 +0000520
Fredrik Lundhc2301732000-07-02 22:25:39 +0000521 # map in either direction
522 groupindex = p.pattern.groupdict
523 indexgroup = [None] * p.pattern.groups
524 for k, i in groupindex.items():
525 indexgroup[i] = k
526
Jeremy Hyltonb1aa1952000-06-01 17:39:12 +0000527 return _sre.compile(
Fredrik Lundh6f013982000-07-03 18:44:21 +0000528 pattern, flags, code,
529 p.pattern.groups-1,
530 groupindex, indexgroup
Fredrik Lundh90a07912000-06-30 07:50:59 +0000531 )