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