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