Python code coverage for Lib/compiler/pyassem.py

#	count	content
1	2	"""A flow graph representation for Python bytecode"""
2	n/a
3	2	import dis
4	2	import types
5	2	import sys
6	n/a
7	2	from compiler import misc
8	2	from compiler.consts \
9	n/a	import CO_OPTIMIZED, CO_NEWLOCALS, CO_VARARGS, CO_VARKEYWORDS
10	n/a
11	4	class FlowGraph:
12	2	def __init__(self):
13	1059	self.current = self.entry = Block()
14	1059	self.exit = Block("exit")
15	1059	self.blocks = misc.Set()
16	1059	self.blocks.add(self.entry)
17	1059	self.blocks.add(self.exit)
18	n/a
19	2	def startBlock(self, block):
20	2627	if self._debug:
21	0	if self.current:
22	0	print "end", repr(self.current)
23	0	print " next", self.current.next
24	0	print " prev", self.current.prev
25	0	print " ", self.current.get_children()
26	0	print repr(block)
27	2627	self.current = block
28	n/a
29	2	def nextBlock(self, block=None):
30	n/a	# XXX think we need to specify when there is implicit transfer
31	n/a	# from one block to the next. might be better to represent this
32	n/a	# with explicit JUMP_ABSOLUTE instructions that are optimized
33	n/a	# out when they are unnecessary.
34	n/a	#
35	n/a	# I think this strategy works: each block has a child
36	n/a	# designated as "next" which is returned as the last of the
37	n/a	# children. because the nodes in a graph are emitted in
38	n/a	# reverse post order, the "next" block will always be emitted
39	n/a	# immediately after its parent.
40	n/a	# Worry: maintaining this invariant could be tricky
41	1312	if block is None:
42	315	block = self.newBlock()
43	n/a
44	n/a	# Note: If the current block ends with an unconditional control
45	n/a	# transfer, then it is techically incorrect to add an implicit
46	n/a	# transfer to the block graph. Doing so results in code generation
47	n/a	# for unreachable blocks. That doesn't appear to be very common
48	n/a	# with Python code and since the built-in compiler doesn't optimize
49	n/a	# it out we don't either.
50	1312	self.current.addNext(block)
51	1312	self.startBlock(block)
52	n/a
53	2	def newBlock(self):
54	1838	b = Block()
55	1838	self.blocks.add(b)
56	1838	return b
57	n/a
58	2	def startExitBlock(self):
59	1028	self.startBlock(self.exit)
60	n/a
61	2	_debug = 0
62	n/a
63	2	def _enable_debug(self):
64	0	self._debug = 1
65	n/a
66	2	def _disable_debug(self):
67	0	self._debug = 0
68	n/a
69	2	def emit(self, *inst):
70	37535	if self._debug:
71	0	print "\t", inst
72	37535	if len(inst) == 2 and isinstance(inst[1], Block):
73	1173	self.current.addOutEdge(inst[1])
74	37535	self.current.emit(inst)
75	n/a
76	2	def getBlocksInOrder(self):
77	n/a	"""Return the blocks in reverse postorder
78	n/a
79	n/a	i.e. each node appears before all of its successors
80	n/a	"""
81	1059	order = order_blocks(self.entry, self.exit)
82	1059	return order
83	n/a
84	2	def getBlocks(self):
85	1059	return self.blocks.elements()
86	n/a
87	2	def getRoot(self):
88	n/a	"""Return nodes appropriate for use with dominator"""
89	0	return self.entry
90	n/a
91	2	def getContainedGraphs(self):
92	0	l = []
93	0	for b in self.getBlocks():
94	0	l.extend(b.getContainedGraphs())
95	0	return l
96	n/a
97	n/a
98	2	def order_blocks(start_block, exit_block):
99	n/a	"""Order blocks so that they are emitted in the right order"""
100	n/a	# Rules:
101	n/a	# - when a block has a next block, the next block must be emitted just after
102	n/a	# - when a block has followers (relative jumps), it must be emitted before
103	n/a	# them
104	n/a	# - all reachable blocks must be emitted
105	1059	order = []
106	n/a
107	n/a	# Find all the blocks to be emitted.
108	1059	remaining = set()
109	1059	todo = [start_block]
110	4089	while todo:
111	3030	b = todo.pop()
112	3030	if b in remaining:
113	372	continue
114	2658	remaining.add(b)
115	5143	for c in b.get_children():
116	2485	if c not in remaining:
117	1971	todo.append(c)
118	n/a
119	n/a	# A block is dominated by another block if that block must be emitted
120	n/a	# before it.
121	1059	dominators = {}
122	3717	for b in remaining:
123	2658	if __debug__ and b.next:
124	1312	assert b is b.next[0].prev[0], (b, b.next)
125	n/a	# Make sure every block appears in dominators, even if no
126	n/a	# other block must precede it.
127	2658	dominators.setdefault(b, set())
128	n/a	# preceeding blocks dominate following blocks
129	4677	for c in b.get_followers():
130	2019	while 1:
131	3292	dominators.setdefault(c, set()).add(b)
132	n/a	# Any block that has a next pointer leading to c is also
133	n/a	# dominated because the whole chain will be emitted at once.
134	n/a	# Walk backwards and add them all.
135	3292	if c.prev and c.prev[0] is not b:
136	1273	c = c.prev[0]
137	n/a	else:
138	2019	break
139	n/a
140	1059	def find_next():
141	n/a	# Find a block that can be emitted next.
142	1496	for b in remaining:
143	2181	for c in dominators[b]:
144	1894	if c in remaining:
145	1209	break # can't emit yet, dominated by a remaining block
146	n/a	else:
147	287	return b
148	0	assert 0, 'circular dependency, cannot find next block'
149	n/a
150	1059	b = start_block
151	1059	while 1:
152	2658	order.append(b)
153	2658	remaining.discard(b)
154	2658	if b.next:
155	1312	b = b.next[0]
156	1312	continue
157	1346	elif b is not exit_block and not b.has_unconditional_transfer():
158	1042	order.append(exit_block)
159	1346	if not remaining:
160	1059	break
161	287	b = find_next()
162	1059	return order
163	n/a
164	n/a
165	4	class Block:
166	2	_count = 0
167	n/a
168	2	def __init__(self, label=''):
169	3956	self.insts = []
170	3956	self.outEdges = set()
171	3956	self.label = label
172	3956	self.bid = Block._count
173	3956	self.next = []
174	3956	self.prev = []
175	3956	Block._count = Block._count + 1
176	n/a
177	2	def __repr__(self):
178	0	if self.label:
179	0	return "<block %s id=%d>" % (self.label, self.bid)
180	n/a	else:
181	0	return "<block id=%d>" % (self.bid)
182	n/a
183	2	def __str__(self):
184	0	insts = map(str, self.insts)
185	0	return "<block %s %d:\n%s>" % (self.label, self.bid,
186	0	'\n'.join(insts))
187	n/a
188	2	def emit(self, inst):
189	37535	op = inst[0]
190	37535	self.insts.append(inst)
191	n/a
192	2	def getInstructions(self):
193	7656	return self.insts
194	n/a
195	2	def addOutEdge(self, block):
196	1173	self.outEdges.add(block)
197	n/a
198	2	def addNext(self, block):
199	1312	self.next.append(block)
200	1312	assert len(self.next) == 1, map(str, self.next)
201	1312	block.prev.append(self)
202	1312	assert len(block.prev) == 1, map(str, block.prev)
203	n/a
204	0	_uncond_transfer = ('RETURN_VALUE', 'RAISE_VARARGS',
205	2	'JUMP_ABSOLUTE', 'JUMP_FORWARD', 'CONTINUE_LOOP',
206	n/a	)
207	n/a
208	2	def has_unconditional_transfer(self):
209	n/a	"""Returns True if there is an unconditional transfer to an other block
210	n/a	at the end of this block. This means there is no risk for the bytecode
211	n/a	executer to go past this block's bytecode."""
212	1346	try:
213	1346	op, arg = self.insts[-1]
214	535	except (IndexError, ValueError):
215	535	return
216	811	return op in self._uncond_transfer
217	n/a
218	2	def get_children(self):
219	6375	return list(self.outEdges) + self.next
220	n/a
221	2	def get_followers(self):
222	n/a	"""Get the whole list of followers, including the next block."""
223	2658	followers = set(self.next)
224	n/a	# Blocks that must be emitted after this one, because of
225	n/a	# bytecode offsets (e.g. relative jumps) pointing to them.
226	38157	for inst in self.insts:
227	35499	if inst[0] in PyFlowGraph.hasjrel:
228	756	followers.add(inst[1])
229	2658	return followers
230	n/a
231	2	def getContainedGraphs(self):
232	n/a	"""Return all graphs contained within this block.
233	n/a
234	n/a	For example, a MAKE_FUNCTION block will contain a reference to
235	n/a	the graph for the function body.
236	n/a	"""
237	0	contained = []
238	0	for inst in self.insts:
239	0	if len(inst) == 1:
240	0	continue
241	0	op = inst[1]
242	0	if hasattr(op, 'graph'):
243	0	contained.append(op.graph)
244	0	return contained
245	n/a
246	n/a	# flags for code objects
247	n/a
248	n/a	# the FlowGraph is transformed in place; it exists in one of these states
249	2	RAW = "RAW"
250	2	FLAT = "FLAT"
251	2	CONV = "CONV"
252	2	DONE = "DONE"
253	n/a
254	4	class PyFlowGraph(FlowGraph):
255	2	super_init = FlowGraph.__init__
256	n/a
257	2	def __init__(self, name, filename, args=(), optimized=0, klass=None):
258	1059	self.super_init()
259	1059	self.name = name
260	1059	self.filename = filename
261	1059	self.docstring = None
262	1059	self.args = args # XXX
263	1059	self.argcount = getArgCount(args)
264	1059	self.klass = klass
265	1059	if optimized:
266	637	self.flags = CO_OPTIMIZED \| CO_NEWLOCALS
267	n/a	else:
268	422	self.flags = 0
269	1059	self.consts = []
270	1059	self.names = []
271	n/a	# Free variables found by the symbol table scan, including
272	n/a	# variables used only in nested scopes, are included here.
273	1059	self.freevars = []
274	1059	self.cellvars = []
275	n/a	# The closure list is used to track the order of cell
276	n/a	# variables and free variables in the resulting code object.
277	n/a	# The offsets used by LOAD_CLOSURE/LOAD_DEREF refer to both
278	n/a	# kinds of variables.
279	1059	self.closure = []
280	1059	self.varnames = list(args) or []
281	2004	for i in range(len(self.varnames)):
282	945	var = self.varnames[i]
283	945	if isinstance(var, TupleArg):
284	0	self.varnames[i] = var.getName()
285	1059	self.stage = RAW
286	n/a
287	2	def setDocstring(self, doc):
288	49	self.docstring = doc
289	n/a
290	2	def setFlag(self, flag):
291	430	self.flags = self.flags \| flag
292	430	if flag == CO_VARARGS:
293	24	self.argcount = self.argcount - 1
294	n/a
295	2	def checkFlag(self, flag):
296	63	if self.flags & flag:
297	0	return 1
298	n/a
299	2	def setFreeVars(self, names):
300	1028	self.freevars = list(names)
301	n/a
302	2	def setCellVars(self, names):
303	1028	self.cellvars = names
304	n/a
305	2	def getCode(self):
306	n/a	"""Get a Python code object"""
307	1059	assert self.stage == RAW
308	1059	self.computeStackDepth()
309	1059	self.flattenGraph()
310	1059	assert self.stage == FLAT
311	1059	self.convertArgs()
312	1059	assert self.stage == CONV
313	1059	self.makeByteCode()
314	1059	assert self.stage == DONE
315	1059	return self.newCodeObject()
316	n/a
317	2	def dump(self, io=None):
318	0	if io:
319	0	save = sys.stdout
320	0	sys.stdout = io
321	0	pc = 0
322	0	for t in self.insts:
323	0	opname = t[0]
324	0	if opname == "SET_LINENO":
325	0	print
326	0	if len(t) == 1:
327	0	print "\t", "%3d" % pc, opname
328	0	pc = pc + 1
329	n/a	else:
330	0	print "\t", "%3d" % pc, opname, t[1]
331	0	pc = pc + 3
332	0	if io:
333	0	sys.stdout = save
334	n/a
335	2	def computeStackDepth(self):
336	n/a	"""Compute the max stack depth.
337	n/a
338	n/a	Approach is to compute the stack effect of each basic block.
339	n/a	Then find the path through the code with the largest total
340	n/a	effect.
341	n/a	"""
342	1059	depth = {}
343	1059	exit = None
344	5015	for b in self.getBlocks():
345	3956	depth[b] = findDepth(b.getInstructions())
346	n/a
347	1059	seen = {}
348	n/a
349	1059	def max_depth(b, d):
350	4603	if b in seen:
351	886	return d
352	3717	seen[b] = 1
353	3717	d = d + depth[b]
354	3717	children = b.get_children()
355	3717	if children:
356	4084	return max([max_depth(c, d) for c in children])
357	n/a	else:
358	2118	if not b.label == "exit":
359	1059	return max_depth(self.exit, d)
360	n/a	else:
361	1059	return d
362	n/a
363	1059	self.stacksize = max_depth(self.entry, 0)
364	n/a
365	2	def flattenGraph(self):
366	n/a	"""Arrange the blocks in order and resolve jumps"""
367	1059	assert self.stage == RAW
368	1059	self.insts = insts = []
369	1059	pc = 0
370	1059	begin = {}
371	1059	end = {}
372	4759	for b in self.getBlocksInOrder():
373	3700	begin[b] = pc
374	41201	for inst in b.getInstructions():
375	37501	insts.append(inst)
376	37501	if len(inst) == 1:
377	5726	pc = pc + 1
378	31775	elif inst[0] != "SET_LINENO":
379	n/a	# arg takes 2 bytes
380	25682	pc = pc + 3
381	3700	end[b] = pc
382	1059	pc = 0
383	38560	for i in range(len(insts)):
384	37501	inst = insts[i]
385	37501	if len(inst) == 1:
386	5726	pc = pc + 1
387	31775	elif inst[0] != "SET_LINENO":
388	25682	pc = pc + 3
389	37501	opname = inst[0]
390	37501	if opname in self.hasjrel:
391	756	oparg = inst[1]
392	756	offset = begin[oparg] - pc
393	756	insts[i] = opname, offset
394	36745	elif opname in self.hasjabs:
395	417	insts[i] = opname, begin[inst[1]]
396	1059	self.stage = FLAT
397	n/a
398	2	hasjrel = set()
399	14	for i in dis.hasjrel:
400	12	hasjrel.add(dis.opname[i])
401	2	hasjabs = set()
402	14	for i in dis.hasjabs:
403	12	hasjabs.add(dis.opname[i])
404	n/a
405	2	def convertArgs(self):
406	n/a	"""Convert arguments from symbolic to concrete form"""
407	1059	assert self.stage == FLAT
408	1059	self.consts.insert(0, self.docstring)
409	1059	self.sort_cellvars()
410	38560	for i in range(len(self.insts)):
411	37501	t = self.insts[i]
412	37501	if len(t) == 2:
413	31775	opname, oparg = t
414	31775	conv = self._converters.get(opname, None)
415	31775	if conv:
416	18551	self.insts[i] = opname, conv(self, oparg)
417	1059	self.stage = CONV
418	n/a
419	2	def sort_cellvars(self):
420	n/a	"""Sort cellvars in the order of varnames and prune from freevars.
421	n/a	"""
422	1059	cells = {}
423	1143	for name in self.cellvars:
424	84	cells[name] = 1
425	2004	self.cellvars = [name for name in self.varnames
426	945	if name in cells]
427	1072	for name in self.cellvars:
428	13	del cells[name]
429	1059	self.cellvars = self.cellvars + cells.keys()
430	1059	self.closure = self.cellvars + self.freevars
431	n/a
432	2	def _lookupName(self, name, list):
433	n/a	"""Return index of name in list, appending if necessary
434	n/a
435	n/a	This routine uses a list instead of a dictionary, because a
436	n/a	dictionary can't store two different keys if the keys have the
437	n/a	same value but different types, e.g. 2 and 2L. The compiler
438	n/a	must treat these two separately, so it does an explicit type
439	n/a	comparison before comparing the values.
440	n/a	"""
441	29773	t = type(name)
442	266651	for i in range(len(list)):
443	254911	if t == type(list[i]) and list[i] == name:
444	18033	return i
445	11740	end = len(list)
446	11740	list.append(name)
447	11740	return end
448	n/a
449	2	_converters = {}
450	2	def _convert_LOAD_CONST(self, arg):
451	5512	if hasattr(arg, 'getCode'):
452	1028	arg = arg.getCode()
453	5512	return self._lookupName(arg, self.consts)
454	n/a
455	2	def _convert_LOAD_FAST(self, arg):
456	5628	self._lookupName(arg, self.names)
457	5628	return self._lookupName(arg, self.varnames)
458	2	_convert_STORE_FAST = _convert_LOAD_FAST
459	2	_convert_DELETE_FAST = _convert_LOAD_FAST
460	n/a
461	2	def _convert_LOAD_NAME(self, arg):
462	187	if self.klass is None:
463	139	self._lookupName(arg, self.varnames)
464	187	return self._lookupName(arg, self.names)
465	n/a
466	2	def _convert_NAME(self, arg):
467	6208	if self.klass is None:
468	4666	self._lookupName(arg, self.varnames)
469	6208	return self._lookupName(arg, self.names)
470	2	_convert_STORE_NAME = _convert_NAME
471	2	_convert_DELETE_NAME = _convert_NAME
472	2	_convert_IMPORT_NAME = _convert_NAME
473	2	_convert_IMPORT_FROM = _convert_NAME
474	2	_convert_STORE_ATTR = _convert_NAME
475	2	_convert_LOAD_ATTR = _convert_NAME
476	2	_convert_DELETE_ATTR = _convert_NAME
477	2	_convert_LOAD_GLOBAL = _convert_NAME
478	2	_convert_STORE_GLOBAL = _convert_NAME
479	2	_convert_DELETE_GLOBAL = _convert_NAME
480	n/a
481	2	def _convert_DEREF(self, arg):
482	497	self._lookupName(arg, self.names)
483	497	self._lookupName(arg, self.varnames)
484	497	return self._lookupName(arg, self.closure)
485	2	_convert_LOAD_DEREF = _convert_DEREF
486	2	_convert_STORE_DEREF = _convert_DEREF
487	n/a
488	2	def _convert_LOAD_CLOSURE(self, arg):
489	157	self._lookupName(arg, self.varnames)
490	157	return self._lookupName(arg, self.closure)
491	n/a
492	2	_cmp = list(dis.cmp_op)
493	2	def _convert_COMPARE_OP(self, arg):
494	362	return self._cmp.index(arg)
495	n/a
496	n/a	# similarly for other opcodes...
497	n/a
498	84	for name, obj in locals().items():
499	82	if name[:9] == "_convert_":
500	42	opname = name[9:]
501	42	_converters[opname] = obj
502	2	del name, obj, opname
503	n/a
504	2	def makeByteCode(self):
505	1059	assert self.stage == CONV
506	1059	self.lnotab = lnotab = LineAddrTable()
507	38560	for t in self.insts:
508	37501	opname = t[0]
509	37501	if len(t) == 1:
510	5726	lnotab.addCode(self.opnum[opname])
511	n/a	else:
512	31775	oparg = t[1]
513	31775	if opname == "SET_LINENO":
514	6093	lnotab.nextLine(oparg)
515	6093	continue
516	25682	hi, lo = twobyte(oparg)
517	25682	try:
518	25682	lnotab.addCode(self.opnum[opname], lo, hi)
519	0	except ValueError:
520	0	print opname, oparg
521	0	print self.opnum[opname], lo, hi
522	0	raise
523	1059	self.stage = DONE
524	n/a
525	2	opnum = {}
526	514	for num in range(len(dis.opname)):
527	512	opnum[dis.opname[num]] = num
528	2	del num
529	n/a
530	2	def newCodeObject(self):
531	1059	assert self.stage == DONE
532	1059	if (self.flags & CO_NEWLOCALS) == 0:
533	31	nlocals = 0
534	n/a	else:
535	1028	nlocals = len(self.varnames)
536	1059	argcount = self.argcount
537	1059	if self.flags & CO_VARKEYWORDS:
538	4	argcount = argcount - 1
539	1059	return types.CodeType(argcount, nlocals, self.stacksize, self.flags,
540	1059	self.lnotab.getCode(), self.getConsts(),
541	1059	tuple(self.names), tuple(self.varnames),
542	1059	self.filename, self.name, self.lnotab.firstline,
543	1059	self.lnotab.getTable(), tuple(self.freevars),
544	1059	tuple(self.cellvars))
545	n/a
546	2	def getConsts(self):
547	n/a	"""Return a tuple for the const slot of the code object
548	n/a
549	n/a	Must convert references to code (MAKE_FUNCTION) to code
550	n/a	objects recursively.
551	n/a	"""
552	1059	l = []
553	5304	for elt in self.consts:
554	4245	if isinstance(elt, PyFlowGraph):
555	0	elt = elt.getCode()
556	4245	l.append(elt)
557	1059	return tuple(l)
558	n/a
559	2	def isJump(opname):
560	0	if opname[:4] == 'JUMP':
561	0	return 1
562	n/a
563	4	class TupleArg:
564	2	"""Helper for marking func defs with nested tuples in arglist"""
565	2	def __init__(self, count, names):
566	0	self.count = count
567	0	self.names = names
568	2	def __repr__(self):
569	0	return "TupleArg(%s, %s)" % (self.count, self.names)
570	2	def getName(self):
571	0	return ".%d" % self.count
572	n/a
573	2	def getArgCount(args):
574	1059	argcount = len(args)
575	1059	if args:
576	1548	for arg in args:
577	945	if isinstance(arg, TupleArg):
578	0	numNames = len(misc.flatten(arg.names))
579	0	argcount = argcount - numNames
580	1059	return argcount
581	n/a
582	2	def twobyte(val):
583	n/a	"""Convert an int argument into high and low bytes"""
584	25682	assert isinstance(val, int)
585	25682	return divmod(val, 256)
586	n/a
587	4	class LineAddrTable:
588	n/a	"""lnotab
589	n/a
590	n/a	This class builds the lnotab, which is documented in compile.c.
591	n/a	Here's a brief recap:
592	n/a
593	n/a	For each SET_LINENO instruction after the first one, two bytes are
594	n/a	added to lnotab. (In some cases, multiple two-byte entries are
595	n/a	added.) The first byte is the distance in bytes between the
596	n/a	instruction for the last SET_LINENO and the current SET_LINENO.
597	n/a	The second byte is offset in line numbers. If either offset is
598	n/a	greater than 255, multiple two-byte entries are added -- see
599	n/a	compile.c for the delicate details.
600	2	"""
601	n/a
602	2	def __init__(self):
603	1059	self.code = []
604	1059	self.codeOffset = 0
605	1059	self.firstline = 0
606	1059	self.lastline = 0
607	1059	self.lastoff = 0
608	1059	self.lnotab = []
609	n/a
610	2	def addCode(self, *args):
611	114180	for arg in args:
612	82772	self.code.append(chr(arg))
613	31408	self.codeOffset = self.codeOffset + len(args)
614	n/a
615	2	def nextLine(self, lineno):
616	6093	if self.firstline == 0:
617	1080	self.firstline = lineno
618	1080	self.lastline = lineno
619	n/a	else:
620	n/a	# compute deltas
621	5013	addr = self.codeOffset - self.lastoff
622	5013	line = lineno - self.lastline
623	n/a	# Python assumes that lineno always increases with
624	n/a	# increasing bytecode address (lnotab is unsigned char).
625	n/a	# Depending on when SET_LINENO instructions are emitted
626	n/a	# this is not always true. Consider the code:
627	n/a	# a = (1,
628	n/a	# b)
629	n/a	# In the bytecode stream, the assignment to "a" occurs
630	n/a	# after the loading of "b". This works with the C Python
631	n/a	# compiler because it only generates a SET_LINENO instruction
632	n/a	# for the assignment.
633	5013	if line >= 0:
634	4960	push = self.lnotab.append
635	4961	while addr > 255:
636	1	push(255); push(0)
637	1	addr -= 255
638	4979	while line > 255:
639	19	push(addr); push(255)
640	19	line -= 255
641	19	addr = 0
642	4960	if addr > 0 or line > 0:
643	4960	push(addr); push(line)
644	4960	self.lastline = lineno
645	4960	self.lastoff = self.codeOffset
646	n/a
647	2	def getCode(self):
648	1059	return ''.join(self.code)
649	n/a
650	2	def getTable(self):
651	1059	return ''.join(map(chr, self.lnotab))
652	n/a
653	4	class StackDepthTracker:
654	n/a	# XXX 1. need to keep track of stack depth on jumps
655	n/a	# XXX 2. at least partly as a result, this code is broken
656	n/a
657	2	def findDepth(self, insts, debug=0):
658	3956	depth = 0
659	3956	maxDepth = 0
660	41491	for i in insts:
661	37535	opname = i[0]
662	37535	if debug:
663	0	print i,
664	37535	delta = self.effect.get(opname, None)
665	37535	if delta is not None:
666	10130	depth = depth + delta
667	n/a	else:
668	n/a	# now check patterns
669	68191	for pat, pat_delta in self.patterns:
670	54444	if opname[:len(pat)] == pat:
671	13658	delta = pat_delta
672	13658	depth = depth + delta
673	13658	break
674	n/a	# if we still haven't found a match
675	27405	if delta is None:
676	13747	meth = getattr(self, opname, None)
677	13747	if meth is not None:
678	5807	depth = depth + meth(i[1])
679	37535	if depth > maxDepth:
680	5633	maxDepth = depth
681	37535	if debug:
682	0	print depth, maxDepth
683	3956	return maxDepth
684	n/a
685	2	effect = {
686	2	'POP_TOP': -1,
687	2	'DUP_TOP': 1,
688	2	'LIST_APPEND': -1,
689	2	'SET_ADD': -1,
690	2	'MAP_ADD': -2,
691	2	'SLICE+1': -1,
692	2	'SLICE+2': -1,
693	2	'SLICE+3': -2,
694	2	'STORE_SLICE+0': -1,
695	2	'STORE_SLICE+1': -2,
696	2	'STORE_SLICE+2': -2,
697	2	'STORE_SLICE+3': -3,
698	2	'DELETE_SLICE+0': -1,
699	2	'DELETE_SLICE+1': -2,
700	2	'DELETE_SLICE+2': -2,
701	2	'DELETE_SLICE+3': -3,
702	2	'STORE_SUBSCR': -3,
703	2	'DELETE_SUBSCR': -2,
704	n/a	# PRINT_EXPR?
705	2	'PRINT_ITEM': -1,
706	2	'RETURN_VALUE': -1,
707	2	'YIELD_VALUE': -1,
708	2	'EXEC_STMT': -3,
709	2	'BUILD_CLASS': -2,
710	2	'STORE_NAME': -1,
711	2	'STORE_ATTR': -2,
712	2	'DELETE_ATTR': -1,
713	2	'STORE_GLOBAL': -1,
714	2	'BUILD_MAP': 1,
715	2	'COMPARE_OP': -1,
716	2	'STORE_FAST': -1,
717	2	'IMPORT_STAR': -1,
718	2	'IMPORT_NAME': -1,
719	2	'IMPORT_FROM': 1,
720	2	'LOAD_ATTR': 0, # unlike other loads
721	n/a	# close enough...
722	2	'SETUP_EXCEPT': 3,
723	2	'SETUP_FINALLY': 3,
724	2	'FOR_ITER': 1,
725	2	'WITH_CLEANUP': -1,
726	n/a	}
727	n/a	# use pattern match
728	n/a	patterns = [
729	2	('BINARY_', -1),
730	2	('LOAD_', 1),
731	n/a	]
732	n/a
733	2	def UNPACK_SEQUENCE(self, count):
734	35	return count-1
735	2	def BUILD_TUPLE(self, count):
736	1039	return -count+1
737	2	def BUILD_LIST(self, count):
738	326	return -count+1
739	2	def BUILD_SET(self, count):
740	4	return -count+1
741	2	def CALL_FUNCTION(self, argc):
742	3375	hi, lo = divmod(argc, 256)
743	3375	return -(lo + hi * 2)
744	2	def CALL_FUNCTION_VAR(self, argc):
745	5	return self.CALL_FUNCTION(argc)-1
746	2	def CALL_FUNCTION_KW(self, argc):
747	3	return self.CALL_FUNCTION(argc)-1
748	2	def CALL_FUNCTION_VAR_KW(self, argc):
749	7	return self.CALL_FUNCTION(argc)-2
750	2	def MAKE_FUNCTION(self, argc):
751	888	return -argc
752	2	def MAKE_CLOSURE(self, argc):
753	n/a	# XXX need to account for free variables too!
754	140	return -argc
755	2	def BUILD_SLICE(self, argc):
756	0	if argc == 2:
757	0	return -1
758	0	elif argc == 3:
759	0	return -2
760	2	def DUP_TOPX(self, argc):
761	0	return argc
762	n/a
763	2	findDepth = StackDepthTracker().findDepth