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