1 #!/usr/bin/env python 2 3 """ 4 Translate the AST of a Python program into a more interpretable representation. 5 6 Copyright (C) 2007, 2008 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 16 details. 17 18 You should have received a copy of the GNU General Public License along with 19 this program. If not, see <http://www.gnu.org/licenses/>. 20 """ 21 22 import micropython.inspect 23 from micropython.rsvp import * 24 from micropython.common import * 25 import compiler.ast 26 from compiler.visitor import ASTVisitor 27 try: 28 set 29 except NameError: 30 from sets import Set as set 31 32 class TranslateError(ProcessingError): pass 33 34 class Label: 35 36 "A reference to a location." 37 38 def __init__(self, number, location=None): 39 self.number = number 40 self.location = location 41 42 def __repr__(self): 43 return "Label(%r, location=%r)" % (self.number, self.location) 44 45 # Program visitors. 46 47 class Translation(ASTVisitor): 48 49 "A translated module." 50 51 def __init__(self, module, objtable, paramtable): 52 53 """ 54 Initialise the translation with an inspected 'module' and an attribute 55 table 'objtable' and parameter table 'paramtable'. 56 """ 57 58 ASTVisitor.__init__(self) 59 self.visitor = self 60 self.module = module 61 self.objtable = objtable 62 self.paramtable = paramtable 63 self.unit = None 64 65 # Wiring within the code. 66 67 self.labels = {} 68 self.label_number = 0 69 self.loop_labels = [] 70 self.exception_labels = [] 71 72 # The code itself. 73 74 self.code = None 75 76 def get_module_code(self): 77 78 "Return the top-level module code." 79 80 self.unit = self.module 81 self.code = [] 82 if self.module.module is not None: 83 self.dispatch(self.module.module) 84 return self.code 85 86 def get_code(self, unit): 87 88 "Return the code for the given 'unit'." 89 90 self.unit = unit 91 self.code = [] 92 if unit.node is not None: 93 self.dispatch(unit.node) 94 return self.code 95 96 def __repr__(self): 97 return "Translation(%r)" % self.module 98 99 def get_scope(self, name): 100 if self.unit.has_key(name): 101 return "local" 102 elif self.module.has_key(name): 103 return "global" 104 else: 105 return "builtins" 106 107 # Code writing methods. 108 109 def new_label(self): 110 111 "Return a new label object for use with set_label." 112 113 number = self.label_number 114 label = Label(number) 115 self.labels[label] = label 116 self.label_number += 1 117 return label 118 119 def set_label(self, label): 120 121 """ 122 Set the location of 'label' to that within the entire image: the 123 location within the code combined with location of the code unit. 124 """ 125 126 label.location = len(self.code) + self.unit.code_location 127 128 def get_loop_labels(self): 129 return self.loop_labels[-1] 130 131 def add_loop_labels(self, next_label, exit_label): 132 self.loop_labels.append((next_label, exit_label)) 133 134 def drop_loop_labels(self): 135 self.loop_labels.pop() 136 137 def get_exception_labels(self): 138 return self.exception_labels[-1] 139 140 def add_exception_labels(self, handler_label, exit_label): 141 self.exception_labels.append((handler_label, exit_label)) 142 143 def drop_exception_labels(self): 144 self.exception_labels.pop() 145 146 def new_op(self, op): 147 148 "Add 'op' to the generated code." 149 150 self.code.append(op) 151 152 def replace_op(self, op): 153 154 "Replace the last added instruction with 'op'." 155 156 self.code[-1] = op 157 158 def remove_ops(self, n): 159 160 "Remove the last 'n' instructions." 161 162 del self.code[-n:] 163 164 def last_ops(self, n): 165 166 "Return the last 'n' added instructions in reverse chronological order." 167 168 ops = self.code[-n:] 169 ops.reverse() 170 return ops 171 172 def last_op(self): 173 174 "Return the last added instruction." 175 176 return self.code[-1] 177 178 # Internal helper methods. 179 180 def _visitAttr(self, node, classes): 181 182 """ 183 Visit the attribute-related 'node', generating instructions based on the 184 given 'classes'. 185 """ 186 187 self.dispatch(node.expr) 188 self._generateAttr(node.attrname, classes) 189 190 def _generateAttr(self, attrname, classes): 191 192 """ 193 Generate code for the access to 'attrname' using the given 'classes'. 194 """ 195 196 AttrInstruction, AttrIndexInstruction = classes 197 # NOTE: Only simple cases are used for optimisations. 198 199 last = self.last_op() 200 201 # Where the last operation (defining the attribute owner) yields a 202 # constant... 203 204 if isinstance(last, (LoadName, LoadAttr)) and last.attr.assignments == 1: 205 206 if self._optimise_constant_storage(AttrInstruction, 1): 207 return 208 209 # Get the details of the access. 210 211 target = last.attr.value 212 target_name = target.full_name() 213 table_entry = self.objtable.table[target_name] 214 pos = table_entry[attrname] 215 self.replace_op(AttrInstruction(pos)) 216 217 # Where the last operation involves the special 'self' name, check to 218 # see if the attribute is acceptably positioned. 219 220 elif isinstance(last, LoadName) and last.attr.name == "self" and not self.unit.is_relocated(attrname): 221 attr = self.unit.parent.all_attributes()[attrname] 222 self.new_op(AttrInstruction(attr)) 223 224 # Otherwise, perform a normal operation. 225 226 else: 227 index = self.objtable.get_index(attrname) 228 self.new_op(AttrIndexInstruction(index)) 229 230 def _startCallFunc(self): 231 232 "Record the location of the invocation." 233 234 self.new_op(MakeFrame()) # records the start of the frame 235 236 def _generateCallFunc(self, args, node): 237 238 # NOTE: Only simple cases are used for optimisations. 239 240 last = self.last_op() 241 if isinstance(last, (LoadName, LoadAttr)) and last.attr.assignments == 1: 242 target = last.attr.value 243 context = last.attr.parent 244 else: 245 target = None 246 context = None 247 248 # Where a target is known and has a known context, avoid generating any 249 # first argument. 250 251 if context is not None: 252 pass # NOTE: Class methods should be supported. 253 else: 254 continue_label = self.new_label() 255 self.new_op(LoadContext()) 256 self.new_op(CheckContext()) 257 self.new_op(JumpIfTrue(continue_label)) 258 self.dispatch(compiler.ast.Name("TypeError")) 259 self.new_op(RaiseException()) 260 self.set_label(continue_label) 261 262 # Evaluate the arguments. 263 264 positional = 1 265 266 for i, arg in enumerate(args): 267 if isinstance(arg, compiler.ast.Keyword): 268 if positional: 269 self.new_op(ReserveFrame(len(args) - i)) 270 positional = 0 271 272 self.dispatch(arg.expr) 273 274 # Optimise where the target is known now. 275 276 if target is not None: 277 278 # Find the parameter table entry for the target. 279 280 target_name = target.full_name() 281 282 # Look for a callable with the precise target name. 283 284 try: 285 table_entry = self.paramtable.table[target_name] 286 287 # Where no callable is present, check to see if it is a 288 # class name and find the initialiser instead. 289 290 except KeyError: 291 if self.objtable.table.has_key(target_name): 292 table_entry = self.paramtable.table[target_name + ".__init__"] 293 else: 294 raise 295 296 pos = table_entry[arg.name] 297 self.new_op(StoreFrame(pos)) 298 299 # Otherwise, generate the code needed to obtain the details of 300 # the parameter location. 301 302 else: 303 304 # Combine the target details with the name to get the location. 305 # See the access method on the List class. 306 307 try: 308 paramindex = self.paramtable.get_index(arg.name) 309 except ValueError: 310 raise TranslateError(self.module.full_name(), node, "No parameter definition exists for %r." % arg.name) 311 312 self.new_op(StoreFrameIndex(paramindex)) 313 314 # use (callable+0)+paramindex+table 315 # checks embedded offset against (callable+0) 316 # moves the top of stack to frame+position 317 318 else: 319 self.dispatch(arg) 320 321 def _endCallFunc(self): 322 323 "Make the invocation and tidy up afterwards." 324 325 self.new_op(LoadCallable()) # uses the start of the frame to get the callable 326 self.new_op(Jump()) 327 328 # NOTE: Exception handling required. 329 330 self.new_op(DropFrame()) 331 332 def _visitName(self, node, classes): 333 334 """ 335 Visit the name-related 'node', generating instructions based on the 336 given 'classes'. 337 """ 338 339 name = node.name 340 scope = self.get_scope(name) 341 #print self.module.name, node.lineno, name, scope 342 self._generateName(name, scope, classes, node) 343 344 def _generateName(self, name, scope, classes, node): 345 346 """ 347 Generate code for the access to 'name' in 'scope' using the given 348 'classes', and using the given 'node' as the source of the access. 349 """ 350 351 NameInstruction, AttrInstruction = classes 352 353 if self._optimise_constant_storage(NameInstruction, 0): 354 return 355 356 if scope == "local": 357 unit = self.unit 358 if isinstance(unit, micropython.inspect.Function): 359 self.new_op(NameInstruction(unit.all_locals()[name])) 360 elif isinstance(unit, micropython.inspect.Class): 361 self.new_op(AttrInstruction(unit.all_class_attributes()[name])) 362 elif isinstance(unit, micropython.inspect.Module): 363 self.new_op(AttrInstruction(unit.module_attributes()[name])) 364 else: 365 raise TranslateError(self.module.full_name(), node, "Program unit %r has no local %r" % (unit, name)) 366 367 elif scope == "global": 368 globals = self.module.module_attributes() 369 if globals.has_key(name): 370 self.new_op(AttrInstruction(globals[name])) 371 else: 372 raise TranslateError(self.module.full_name(), node, "Module %r has no attribute %r" % (self.module, name)) 373 374 else: 375 self.new_op(AttrInstruction(self._get_builtin(name))) 376 377 def _get_builtin(self, name): 378 builtins = micropython.inspect.builtins.module_attributes() 379 return builtins[name] 380 381 # Optimisation methods. 382 383 def _optimise_constant_storage(self, cls, n): 384 385 """ 386 Where this operation should store a constant into a target which is 387 also constant, optimise away both operations. 388 """ 389 390 last = self.last_ops(n+1) 391 392 if cls in (StoreAttr, StoreName) and len(last) > n and \ 393 (isinstance(last[n], LoadAttr) and last[n].attr.assignments == 1 or 394 isinstance(last[n], LoadConst)): 395 396 self.remove_ops(n+1) 397 return 1 398 else: 399 return 0 400 401 # Visitor methods. 402 403 def default(self, node, *args): 404 raise TranslateError(self.module.full_name(), node, "Node class %r is not supported." % node.__class__) 405 406 def dispatch(self, node, *args): 407 return ASTVisitor.dispatch(self, node, *args) 408 409 def _visitBinary(self, node, left_method, right_method): 410 411 """ 412 _t1 = node.left 413 _t2 = node.right 414 try: 415 _t1.__add__(_t2) 416 except AttributeError: 417 _t2.__radd__(_t1) 418 """ 419 420 right_label = self.new_label() 421 end_label = self.new_label() 422 423 # NOTE: Decide on temporary storage access. 424 425 self.dispatch(node.left) 426 self.new_op(StoreTemp(1)) 427 self.dispatch(node.right) 428 self.new_op(StoreTemp(2)) 429 430 # Left method. 431 432 self._startCallFunc() 433 self.new_op(LoadTemp(1)) 434 self._generateAttr(left_method, (LoadAttr, LoadAttrIndex)) 435 self.new_op(LoadTemp(1)) # Explicit context as first argument. 436 self.new_op(LoadTemp(2)) 437 self._endCallFunc() 438 439 self.dispatch(compiler.ast.Name("AttributeError")) 440 self.new_op(CheckException()) 441 self.new_op(JumpIfFalse(end_label)) 442 443 # Right method. 444 445 self.set_label(right_label) 446 self._startCallFunc() 447 self.new_op(LoadTemp(2)) 448 self._generateAttr(right_method, (LoadAttr, LoadAttrIndex)) 449 self.new_op(LoadTemp(2)) # Explicit context as first argument. 450 self.new_op(LoadTemp(1)) 451 self._endCallFunc() 452 453 self.set_label(end_label) 454 455 def visitAdd(self, node): 456 self._visitBinary(node, "__add__", "__radd__") 457 458 def visitAnd(self, node): pass 459 460 def visitAssert(self, node): pass 461 462 def visitAssign(self, node): 463 self.dispatch(node.expr) 464 for n in node.nodes: 465 self.dispatch(n) 466 467 def visitAssAttr(self, node): 468 self._visitAttr(node, (StoreAttr, StoreAttrIndex)) 469 470 def visitAssList(self, node): pass 471 472 def visitAssName(self, node): 473 self._visitName(node, (StoreName, StoreAttr)) 474 475 visitAssTuple = visitAssList 476 477 def visitAugAssign(self, node): pass 478 479 def visitBackquote(self, node): pass 480 481 def visitBitand(self, node): pass 482 483 def visitBitor(self, node): pass 484 485 def visitBitxor(self, node): pass 486 487 def visitBreak(self, node): 488 next_label, exit_label = self.get_loop_labels() 489 self.new_op(Jump(exit_label)) 490 491 def visitCallFunc(self, node): 492 493 """ 494 Evaluate positional arguments, evaluate and store keyword arguments in 495 the correct location, then invoke the function. 496 """ 497 498 # Mark the frame, evaluate the target, generate the call. 499 500 self._startCallFunc() 501 self.dispatch(node.node) 502 self._generateCallFunc(node.args, node) 503 self._endCallFunc() 504 505 def visitClass(self, node): 506 unit = self.unit 507 self.unit = node.unit 508 self.unit.code_location = self.module.code_location # class body code is not independently addressable 509 self.dispatch(node.code) 510 self.unit = unit 511 512 def visitCompare(self, node): 513 514 """ 515 self.dispatch(node.expr) 516 for op_name, next_node in compare.ops: 517 methods = self.comparison_methods[op_name] 518 if methods is not None: 519 # Generate method call using evaluated argument and next node. 520 else: 521 # Deal with the special operators. 522 # Provide short-circuiting. 523 """ 524 525 def visitConst(self, node): 526 const = self.module.constant_values[node.value] 527 self.new_op(LoadConst(const)) 528 529 def visitContinue(self, node): 530 next_label, exit_label = self.get_loop_labels() 531 self.new_op(Jump(next_label)) 532 533 def visitDecorators(self, node): pass 534 535 def visitDict(self, node): pass 536 537 def visitDiscard(self, node): 538 self.dispatch(node.expr) 539 540 def visitDiv(self, node): 541 self._visitBinary(node, "__div__", "__rdiv__") 542 543 def visitEllipsis(self, node): pass 544 545 def visitExec(self, node): pass 546 547 def visitExpression(self, node): pass 548 549 def visitFloorDiv(self, node): 550 self._visitBinary(node, "__floordiv__", "__rfloordiv__") 551 552 def visitFor(self, node): 553 exit_label = self.new_label() 554 next_label = self.new_label() 555 else_label = self.new_label() 556 557 # Get the "list" to be iterated over, obtain its iterator. 558 559 self._startCallFunc() 560 self.dispatch(node.list) 561 self._generateAttr("__iter__", (LoadAttr, LoadAttrIndex)) 562 self._generateCallFunc([], node) 563 self._endCallFunc() 564 565 # Iterator on stack. 566 567 # In the loop... 568 569 self.set_label(next_label) 570 571 # Use the iterator to get the next value. 572 573 self._startCallFunc() 574 self.new_op(Duplicate()) 575 self._generateAttr("next", (LoadAttr, LoadAttrIndex)) 576 self._generateCallFunc([], node) 577 self._endCallFunc() 578 579 # Test for StopIteration. 580 581 self.dispatch(compiler.ast.Name("StopIteration")) 582 self.new_op(CheckException()) 583 if node.else_ is not None: 584 self.new_op(JumpIfTrue(else_label)) 585 else: 586 self.new_op(JumpIfTrue(exit_label)) 587 588 # Assign to the target. 589 590 self.dispatch(node.assign) 591 592 # Process the body with the current next and exit points. 593 594 self.add_loop_labels(next_label, exit_label) 595 self.dispatch(node.body) 596 self.drop_loop_labels() 597 598 # Repeat the loop. 599 600 self.new_op(Jump(next_label)) 601 602 # Produce the "else" section. 603 604 if node.else_ is not None: 605 self.set_label(exit_label) 606 self.dispatch(node.else_) 607 608 # Pop the iterator. 609 610 self.set_label(exit_label) 611 self.new_op(Pop()) 612 613 def visitFrom(self, node): pass 614 615 def visitFunction(self, node): 616 617 # Only store the name when visiting this node from outside. 618 619 if self.unit is not node.unit: 620 self.new_op(LoadConst(node.unit)) 621 self._visitName(node, (StoreName, StoreAttr)) 622 623 # Visiting of the code occurs when get_code is invoked on this node. 624 625 else: 626 self.dispatch(node.code) 627 self.new_op(Return()) 628 629 def visitGenExpr(self, node): pass 630 631 def visitGenExprFor(self, node): pass 632 633 def visitGenExprIf(self, node): pass 634 635 def visitGenExprInner(self, node): pass 636 637 def visitGetattr(self, node): 638 self._visitAttr(node, (LoadAttr, LoadAttrIndex)) 639 640 def visitGlobal(self, node): pass 641 642 def visitIf(self, node): 643 first = 1 644 exit_label = self.new_label() 645 646 for test, body in node.tests + [(None, node.else_)]: 647 if body is None: 648 break 649 if not first: 650 self.set_label(next_label) 651 if test is not None: 652 self.dispatch(test) 653 next_label = self.new_label() 654 self.new_op(JumpIfFalse(next_label)) 655 self.dispatch(body) 656 self.new_op(Jump(exit_label)) 657 first = 0 658 659 self.set_label(exit_label) 660 661 def visitImport(self, node): pass 662 663 def visitInvert(self, node): pass 664 665 def visitKeyword(self, node): pass 666 667 def visitLambda(self, node): pass 668 669 def visitLeftShift(self, node): pass 670 671 def visitList(self, node): pass 672 673 def visitListComp(self, node): pass 674 675 def visitListCompFor(self, node): pass 676 677 def visitListCompIf(self, node): pass 678 679 def visitMod(self, node): 680 self._visitBinary(node, "__mod__", "__rmod__") 681 682 def visitModule(self, node): 683 self.dispatch(node.node) 684 685 def visitMul(self, node): 686 self._visitBinary(node, "__mul__", "__rmul__") 687 688 def visitName(self, node): 689 self._visitName(node, (LoadName, LoadAttr)) 690 691 def visitNot(self, node): pass 692 693 def visitOr(self, node): pass 694 695 def visitPass(self, node): pass 696 697 def visitPower(self, node): pass 698 699 def visitPrint(self, node): pass 700 701 def visitPrintnl(self, node): pass 702 703 def visitRaise(self, node): pass 704 705 def visitReturn(self, node): 706 if node.value is not None: 707 self.dispatch(node.value) 708 self.new_op(Return()) 709 710 def visitRightShift(self, node): pass 711 712 def visitSlice(self, node): pass 713 714 def visitStmt(self, node): 715 for n in node.nodes: 716 self.dispatch(n) 717 718 def visitSub(self, node): 719 self._visitBinary(node, "__sub__", "__rsub__") 720 721 def visitSubscript(self, node): pass 722 723 def visitTryExcept(self, node): 724 725 """ 726 Enter try block. 727 Dispatch to code. 728 729 """ 730 731 exit_label = self.new_label() 732 handler_label = self.new_label() 733 734 self.add_exception_labels(handler_label, exit_label) 735 736 self.dispatch(node.body) 737 self.new_op(Jump(exit_label)) 738 739 self.set_label(handler_label) 740 for name, assignment, handler in node.handlers: 741 next_label = self.new_label() 742 743 if name is not None: 744 self.dispatch(name) 745 self.new_op(CheckException()) 746 self.new_op(JumpIfFalse(next_label)) 747 748 if assignment is not None: 749 self.dispatch(assignment) 750 751 self.dispatch(handler) 752 self.new_op(Jump(exit_label)) 753 754 self.set_label(next_label) 755 756 # Unhandled exceptions. 757 758 self.new_op(RaiseException()) 759 760 # After exception 761 762 self.set_label(exit_label) 763 764 # Optional else clause. 765 766 if node.else_ is not None: 767 self.dispatch(node.else_) 768 769 self.drop_exception_labels() 770 771 def visitTryFinally(self, node): pass 772 773 def visitTuple(self, node): pass 774 775 def visitUnaryAdd(self, node): pass 776 777 def visitUnarySub(self, node): pass 778 779 def visitWhile(self, node): 780 exit_label = self.new_label() 781 next_label = self.new_label() 782 else_label = self.new_label() 783 784 self.set_label(next_label) 785 self.dispatch(node.test) 786 if node.else_ is not None: 787 self.new_op(JumpIfFalse(else_label)) 788 else: 789 self.new_op(JumpIfFalse(exit_label)) 790 791 self.add_loop_labels(next_label, exit_label) 792 793 self.dispatch(node.body) 794 self.new_op(Jump(next_label)) 795 796 if node.else_ is not None: 797 self.set_label(else_label) 798 self.dispatch(node.else_) 799 800 self.set_label(exit_label) 801 self.drop_loop_labels() 802 803 def visitWith(self, node): pass 804 805 def visitYield(self, node): pass 806 807 # Useful data. 808 809 comparison_methods = { 810 "==" : ("__eq__", "__ne__"), 811 "!=" : ("__ne__", "__eq__"), 812 "<" : ("__lt__", "__gt__"), 813 "<=" : ("__le__", "__ge__"), 814 ">=" : ("__ge__", "__le__"), 815 ">" : ("__gt__", "__lt__"), 816 "is" : None, 817 "is not" : None, 818 "in" : None, 819 "not in" : None 820 } 821 822 # vim: tabstop=4 expandtab shiftwidth=4