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 start_keywords = None 266 employed_keywords = set() 267 268 for i, arg in enumerate(args): 269 if isinstance(arg, compiler.ast.Keyword): 270 if positional: 271 self.new_op(ReserveFrame(len(args) - i)) 272 start_keywords = i 273 positional = 0 274 275 self.dispatch(arg.expr) 276 277 # Optimise where the target is known now. 278 279 if target is not None: 280 281 # Find the parameter table entry for the target. 282 283 target_name = target.full_name() 284 285 # Look for a callable with the precise target name. 286 287 try: 288 table_entry = self.paramtable.table[target_name] 289 290 # Where no callable is present, check to see if it is a 291 # class name and find the initialiser instead. 292 293 except KeyError: 294 if self.objtable.table.has_key(target_name): 295 table_entry = self.paramtable.table[target_name + ".__init__"] 296 else: 297 raise 298 299 pos = table_entry[arg.name] 300 301 # Test for illegal conditions. 302 303 if pos < start_keywords: 304 raise TranslateError(self.module.full_name(), node, 305 "Keyword argument %r overwrites parameter %r." % (arg.name, pos)) 306 elif pos in employed_keywords: 307 raise TranslateError(self.module.full_name(), node, 308 "Keyword argument %r is repeated, overwriting parameter %r." % (arg.name, pos)) 309 310 employed_keywords.add(pos) 311 self.new_op(StoreFrame(pos)) 312 313 # Otherwise, generate the code needed to obtain the details of 314 # the parameter location. 315 316 else: 317 318 # Combine the target details with the name to get the location. 319 # See the access method on the List class. 320 321 try: 322 paramindex = self.paramtable.get_index(arg.name) 323 except ValueError: 324 raise TranslateError(self.module.full_name(), node, "No parameter definition exists for %r." % arg.name) 325 326 self.new_op(StoreFrameIndex(paramindex)) 327 328 # use (callable+0)+paramindex+table 329 # checks embedded offset against (callable+0) 330 # moves the top of stack to frame+position 331 332 else: 333 self.dispatch(arg) 334 335 def _endCallFunc(self): 336 337 "Make the invocation and tidy up afterwards." 338 339 self.new_op(LoadCallable()) # uses the start of the frame to get the callable 340 self.new_op(Jump()) 341 342 # NOTE: Exception handling required. 343 344 self.new_op(DropFrame()) 345 346 def _visitName(self, node, classes): 347 348 """ 349 Visit the name-related 'node', generating instructions based on the 350 given 'classes'. 351 """ 352 353 name = node.name 354 scope = self.get_scope(name) 355 #print self.module.name, node.lineno, name, scope 356 self._generateName(name, scope, classes, node) 357 358 def _generateName(self, name, scope, classes, node): 359 360 """ 361 Generate code for the access to 'name' in 'scope' using the given 362 'classes', and using the given 'node' as the source of the access. 363 """ 364 365 NameInstruction, AttrInstruction = classes 366 367 if self._optimise_constant_storage(NameInstruction, 0): 368 return 369 370 if scope == "local": 371 unit = self.unit 372 if isinstance(unit, micropython.inspect.Function): 373 self.new_op(NameInstruction(unit.all_locals()[name])) 374 elif isinstance(unit, micropython.inspect.Class): 375 self.new_op(AttrInstruction(unit.all_class_attributes()[name])) 376 elif isinstance(unit, micropython.inspect.Module): 377 self.new_op(AttrInstruction(unit.module_attributes()[name])) 378 else: 379 raise TranslateError(self.module.full_name(), node, "Program unit %r has no local %r" % (unit, name)) 380 381 elif scope == "global": 382 globals = self.module.module_attributes() 383 if globals.has_key(name): 384 self.new_op(AttrInstruction(globals[name])) 385 else: 386 raise TranslateError(self.module.full_name(), node, "Module %r has no attribute %r" % (self.module, name)) 387 388 else: 389 self.new_op(AttrInstruction(self._get_builtin(name))) 390 391 def _get_builtin(self, name): 392 builtins = micropython.inspect.builtins.module_attributes() 393 return builtins[name] 394 395 # Optimisation methods. 396 397 def _optimise_constant_storage(self, cls, n): 398 399 """ 400 Where this operation should store a constant into a target which is 401 also constant, optimise away both operations. 402 """ 403 404 last = self.last_ops(n+1) 405 406 if cls in (StoreAttr, StoreName) and len(last) > n and \ 407 (isinstance(last[n], LoadAttr) and last[n].attr.assignments == 1 or 408 isinstance(last[n], LoadConst)): 409 410 self.remove_ops(n+1) 411 return 1 412 else: 413 return 0 414 415 # Visitor methods. 416 417 def default(self, node, *args): 418 raise TranslateError(self.module.full_name(), node, "Node class %r is not supported." % node.__class__) 419 420 def dispatch(self, node, *args): 421 return ASTVisitor.dispatch(self, node, *args) 422 423 def _visitBinary(self, node, left_method, right_method): 424 425 """ 426 _t1 = node.left 427 _t2 = node.right 428 try: 429 _t1.__add__(_t2) 430 except AttributeError: 431 _t2.__radd__(_t1) 432 """ 433 434 right_label = self.new_label() 435 end_label = self.new_label() 436 437 # NOTE: Decide on temporary storage access. 438 439 self.dispatch(node.left) 440 self.new_op(StoreTemp(1)) 441 self.dispatch(node.right) 442 self.new_op(StoreTemp(2)) 443 444 # Left method. 445 446 self._startCallFunc() 447 self.new_op(LoadTemp(1)) 448 self._generateAttr(left_method, (LoadAttr, LoadAttrIndex)) 449 self.new_op(LoadTemp(1)) # Explicit context as first argument. 450 self.new_op(LoadTemp(2)) 451 self._endCallFunc() 452 453 self.dispatch(compiler.ast.Name("AttributeError")) 454 self.new_op(CheckException()) 455 self.new_op(JumpIfFalse(end_label)) 456 457 # Right method. 458 459 self.set_label(right_label) 460 self._startCallFunc() 461 self.new_op(LoadTemp(2)) 462 self._generateAttr(right_method, (LoadAttr, LoadAttrIndex)) 463 self.new_op(LoadTemp(2)) # Explicit context as first argument. 464 self.new_op(LoadTemp(1)) 465 self._endCallFunc() 466 467 self.set_label(end_label) 468 469 def visitAdd(self, node): 470 self._visitBinary(node, "__add__", "__radd__") 471 472 def visitAnd(self, node): pass 473 474 def visitAssert(self, node): pass 475 476 def visitAssign(self, node): 477 self.dispatch(node.expr) 478 for n in node.nodes: 479 self.dispatch(n) 480 481 def visitAssAttr(self, node): 482 self._visitAttr(node, (StoreAttr, StoreAttrIndex)) 483 484 def visitAssList(self, node): pass 485 486 def visitAssName(self, node): 487 self._visitName(node, (StoreName, StoreAttr)) 488 489 visitAssTuple = visitAssList 490 491 def visitAugAssign(self, node): pass 492 493 def visitBackquote(self, node): pass 494 495 def visitBitand(self, node): pass 496 497 def visitBitor(self, node): pass 498 499 def visitBitxor(self, node): pass 500 501 def visitBreak(self, node): 502 next_label, exit_label = self.get_loop_labels() 503 self.new_op(Jump(exit_label)) 504 505 def visitCallFunc(self, node): 506 507 """ 508 Evaluate positional arguments, evaluate and store keyword arguments in 509 the correct location, then invoke the function. 510 """ 511 512 # Mark the frame, evaluate the target, generate the call. 513 514 self._startCallFunc() 515 self.dispatch(node.node) 516 self._generateCallFunc(node.args, node) 517 self._endCallFunc() 518 519 def visitClass(self, node): 520 unit = self.unit 521 self.unit = node.unit 522 self.unit.code_location = self.module.code_location # class body code is not independently addressable 523 self.dispatch(node.code) 524 self.unit = unit 525 526 def visitCompare(self, node): 527 528 """ 529 self.dispatch(node.expr) 530 for op_name, next_node in compare.ops: 531 methods = self.comparison_methods[op_name] 532 if methods is not None: 533 # Generate method call using evaluated argument and next node. 534 else: 535 # Deal with the special operators. 536 # Provide short-circuiting. 537 """ 538 539 def visitConst(self, node): 540 const = self.module.constant_values[node.value] 541 self.new_op(LoadConst(const)) 542 543 def visitContinue(self, node): 544 next_label, exit_label = self.get_loop_labels() 545 self.new_op(Jump(next_label)) 546 547 def visitDecorators(self, node): pass 548 549 def visitDict(self, node): pass 550 551 def visitDiscard(self, node): 552 self.dispatch(node.expr) 553 554 def visitDiv(self, node): 555 self._visitBinary(node, "__div__", "__rdiv__") 556 557 def visitEllipsis(self, node): pass 558 559 def visitExec(self, node): pass 560 561 def visitExpression(self, node): pass 562 563 def visitFloorDiv(self, node): 564 self._visitBinary(node, "__floordiv__", "__rfloordiv__") 565 566 def visitFor(self, node): 567 exit_label = self.new_label() 568 next_label = self.new_label() 569 else_label = self.new_label() 570 571 # Get the "list" to be iterated over, obtain its iterator. 572 573 self._startCallFunc() 574 self.dispatch(node.list) 575 self._generateAttr("__iter__", (LoadAttr, LoadAttrIndex)) 576 self._generateCallFunc([], node) 577 self._endCallFunc() 578 579 # Iterator on stack. 580 581 # In the loop... 582 583 self.set_label(next_label) 584 585 # Use the iterator to get the next value. 586 587 self._startCallFunc() 588 self.new_op(Duplicate()) 589 self._generateAttr("next", (LoadAttr, LoadAttrIndex)) 590 self._generateCallFunc([], node) 591 self._endCallFunc() 592 593 # Test for StopIteration. 594 595 self.dispatch(compiler.ast.Name("StopIteration")) 596 self.new_op(CheckException()) 597 if node.else_ is not None: 598 self.new_op(JumpIfTrue(else_label)) 599 else: 600 self.new_op(JumpIfTrue(exit_label)) 601 602 # Assign to the target. 603 604 self.dispatch(node.assign) 605 606 # Process the body with the current next and exit points. 607 608 self.add_loop_labels(next_label, exit_label) 609 self.dispatch(node.body) 610 self.drop_loop_labels() 611 612 # Repeat the loop. 613 614 self.new_op(Jump(next_label)) 615 616 # Produce the "else" section. 617 618 if node.else_ is not None: 619 self.set_label(exit_label) 620 self.dispatch(node.else_) 621 622 # Pop the iterator. 623 624 self.set_label(exit_label) 625 self.new_op(Pop()) 626 627 def visitFrom(self, node): pass 628 629 def visitFunction(self, node): 630 631 # Only store the name when visiting this node from outside. 632 633 if self.unit is not node.unit: 634 self.new_op(LoadConst(node.unit)) 635 self._visitName(node, (StoreName, StoreAttr)) 636 637 # Visiting of the code occurs when get_code is invoked on this node. 638 639 else: 640 self.dispatch(node.code) 641 self.new_op(Return()) 642 643 def visitGenExpr(self, node): pass 644 645 def visitGenExprFor(self, node): pass 646 647 def visitGenExprIf(self, node): pass 648 649 def visitGenExprInner(self, node): pass 650 651 def visitGetattr(self, node): 652 self._visitAttr(node, (LoadAttr, LoadAttrIndex)) 653 654 def visitGlobal(self, node): pass 655 656 def visitIf(self, node): 657 first = 1 658 exit_label = self.new_label() 659 660 for test, body in node.tests + [(None, node.else_)]: 661 if body is None: 662 break 663 if not first: 664 self.set_label(next_label) 665 if test is not None: 666 self.dispatch(test) 667 next_label = self.new_label() 668 self.new_op(JumpIfFalse(next_label)) 669 self.dispatch(body) 670 self.new_op(Jump(exit_label)) 671 first = 0 672 673 self.set_label(exit_label) 674 675 def visitImport(self, node): pass 676 677 def visitInvert(self, node): pass 678 679 def visitKeyword(self, node): pass 680 681 def visitLambda(self, node): pass 682 683 def visitLeftShift(self, node): pass 684 685 def visitList(self, node): pass 686 687 def visitListComp(self, node): pass 688 689 def visitListCompFor(self, node): pass 690 691 def visitListCompIf(self, node): pass 692 693 def visitMod(self, node): 694 self._visitBinary(node, "__mod__", "__rmod__") 695 696 def visitModule(self, node): 697 self.dispatch(node.node) 698 699 def visitMul(self, node): 700 self._visitBinary(node, "__mul__", "__rmul__") 701 702 def visitName(self, node): 703 self._visitName(node, (LoadName, LoadAttr)) 704 705 def visitNot(self, node): pass 706 707 def visitOr(self, node): pass 708 709 def visitPass(self, node): pass 710 711 def visitPower(self, node): pass 712 713 def visitPrint(self, node): pass 714 715 def visitPrintnl(self, node): pass 716 717 def visitRaise(self, node): pass 718 719 def visitReturn(self, node): 720 if node.value is not None: 721 self.dispatch(node.value) 722 self.new_op(Return()) 723 724 def visitRightShift(self, node): pass 725 726 def visitSlice(self, node): pass 727 728 def visitStmt(self, node): 729 for n in node.nodes: 730 self.dispatch(n) 731 732 def visitSub(self, node): 733 self._visitBinary(node, "__sub__", "__rsub__") 734 735 def visitSubscript(self, node): pass 736 737 def visitTryExcept(self, node): 738 739 """ 740 Enter try block. 741 Dispatch to code. 742 743 """ 744 745 exit_label = self.new_label() 746 handler_label = self.new_label() 747 748 self.add_exception_labels(handler_label, exit_label) 749 750 self.dispatch(node.body) 751 self.new_op(Jump(exit_label)) 752 753 self.set_label(handler_label) 754 for name, assignment, handler in node.handlers: 755 next_label = self.new_label() 756 757 if name is not None: 758 self.dispatch(name) 759 self.new_op(CheckException()) 760 self.new_op(JumpIfFalse(next_label)) 761 762 if assignment is not None: 763 self.dispatch(assignment) 764 765 self.dispatch(handler) 766 self.new_op(Jump(exit_label)) 767 768 self.set_label(next_label) 769 770 # Unhandled exceptions. 771 772 self.new_op(RaiseException()) 773 774 # After exception 775 776 self.set_label(exit_label) 777 778 # Optional else clause. 779 780 if node.else_ is not None: 781 self.dispatch(node.else_) 782 783 self.drop_exception_labels() 784 785 def visitTryFinally(self, node): pass 786 787 def visitTuple(self, node): pass 788 789 def visitUnaryAdd(self, node): pass 790 791 def visitUnarySub(self, node): pass 792 793 def visitWhile(self, node): 794 exit_label = self.new_label() 795 next_label = self.new_label() 796 else_label = self.new_label() 797 798 self.set_label(next_label) 799 self.dispatch(node.test) 800 if node.else_ is not None: 801 self.new_op(JumpIfFalse(else_label)) 802 else: 803 self.new_op(JumpIfFalse(exit_label)) 804 805 self.add_loop_labels(next_label, exit_label) 806 807 self.dispatch(node.body) 808 self.new_op(Jump(next_label)) 809 810 if node.else_ is not None: 811 self.set_label(else_label) 812 self.dispatch(node.else_) 813 814 self.set_label(exit_label) 815 self.drop_loop_labels() 816 817 def visitWith(self, node): pass 818 819 def visitYield(self, node): pass 820 821 # Useful data. 822 823 comparison_methods = { 824 "==" : ("__eq__", "__ne__"), 825 "!=" : ("__ne__", "__eq__"), 826 "<" : ("__lt__", "__gt__"), 827 "<=" : ("__le__", "__ge__"), 828 ">=" : ("__ge__", "__le__"), 829 ">" : ("__gt__", "__lt__"), 830 "is" : None, 831 "is not" : None, 832 "in" : None, 833 "not in" : None 834 } 835 836 # vim: tabstop=4 expandtab shiftwidth=4