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 from micropython.common import * 23 from micropython.data import * 24 from micropython.rsvp import * 25 import compiler.ast 26 from compiler.visitor import ASTVisitor 27 28 # Program visitors. 29 30 class Translation(ASTVisitor): 31 32 "A translated module." 33 34 supported_optimisations = ["constant_storage", "known_target", "self_access", "temp_storage", "constant_test", "stack_access"] 35 36 attribute_load_instructions = (LoadAddress, LoadAddressContext, LoadAttr, LoadAttrIndex) 37 attribute_store_instructions = (StoreAddress, StoreAddressContext, StoreAttr, StoreAttrIndex) 38 39 def __init__(self, module, importer, optimisations=None): 40 41 """ 42 Initialise the translation with an inspected 'module', the 'importer' 43 and optional 'optimisations'. See the 'supported_optimisations' 44 attribute of this class for permitted values. 45 """ 46 47 ASTVisitor.__init__(self) 48 self.visitor = self 49 self.module = module 50 51 # Global program dependencies. 52 53 self.importer = importer 54 self.objtable = self.importer.get_object_table() 55 self.paramtable = self.importer.get_parameter_table() 56 self.builtins = self.importer.modules.get("__builtins__") 57 58 # Desired optimisations. 59 60 self.optimisations = set(optimisations or []) 61 62 # The current unit being translated. 63 64 self.unit = None 65 66 # Wiring within the code. 67 68 self.labels = {} 69 self.label_number = 0 70 self.loop_labels = [] 71 self.exception_labels = [] 72 73 # The code itself. This is limited to the code for a particular block 74 # being processed. Also retained is information about temporary values 75 # and the presumed state of the value stack. 76 77 self.code = None 78 self.last_invocation = None 79 self.temp_position = 0 80 self.stack = [] 81 self.suspended_frame = [] 82 self.frame_positions = [] 83 84 def __repr__(self): 85 return "Translation(%r)" % self.module 86 87 def get_module_code(self): 88 89 "Return the top-level module code." 90 91 self.unit = self.module 92 self.code = [] 93 self.last_invocation = None 94 self.temp_position = self.unit.stack_local_usage 95 self.stack = [] 96 97 if self.module.module is not None: 98 self.dispatch(self.module.module) 99 100 return self.code 101 102 def get_code(self, unit): 103 104 "Return the code for the given 'unit'." 105 106 self.unit = unit 107 self.code = [] 108 self.last_invocation = None 109 self.temp_position = self.unit.stack_local_usage 110 self.stack = [] 111 112 if unit.astnode is not None: 113 self.dispatch(unit.astnode) 114 115 return self.code 116 117 def get_scope(self, name): 118 119 "Return the scope for the given 'name'." 120 121 if self.unit.has_key(name): 122 return "local" 123 elif self.module.has_key(name): 124 return "global" 125 else: 126 return "builtins" 127 128 # Code feature methods. 129 130 def reset_stack(self): 131 132 "Reset the stack for the current unit." 133 134 self.stack = [] 135 136 def adjust_stack(self, op): 137 138 "Adjust the stack according to the effect of 'op'." 139 140 position = len(self.code) 141 stack_level = len(self.stack) 142 143 op.fix_stack(stack_level) 144 effect = op.get_effect() 145 146 if effect == 1: 147 self.stack.append((position, op)) 148 elif effect < 0: 149 while effect != 0: 150 self.stack.pop() 151 effect += 1 152 153 # Update the stack levels. 154 155 self.unit.stack_usage = max(self.unit.stack_usage, stack_level) 156 157 def revert_stack(self, op): 158 159 "Revert the stack affected by 'op'." 160 161 effect = op.get_effect() 162 163 if effect > 0: 164 while effect != 0: 165 self.stack.pop() 166 effect -= 1 167 elif effect < 0: 168 raise ProcessingError, "Cannot remove instructions which reduce the stack." 169 170 def make_frame(self): 171 self.frame_positions.append(len(self.stack)) 172 173 def suspend_frame(self): 174 self.suspended_frame = self.stack[self.frame_positions[-1]:] 175 self.stack = self.stack[:self.frame_positions[-1]] 176 177 def resume_frame(self): 178 self.stack += self.suspended_frame 179 self.suspended_frame = [] 180 181 def drop_frame(self): 182 self.stack = self.stack[:self.frame_positions.pop()] 183 184 def new_label(self): 185 186 "Return a new label object for use with set_label." 187 188 number = self.label_number 189 label = Label(number) 190 self.labels[label] = label 191 self.label_number += 1 192 return label 193 194 def set_label(self, label): 195 196 """ 197 Set the location of 'label' to that within the entire image: the 198 location within the code combined with location of the code unit. 199 """ 200 201 label.location = len(self.code) + self.unit.code_location 202 203 def get_loop_labels(self): 204 return self.loop_labels[-1] 205 206 def add_loop_labels(self, next_label, exit_label): 207 self.loop_labels.append((next_label, exit_label)) 208 209 def drop_loop_labels(self): 210 self.loop_labels.pop() 211 212 def get_exception_labels(self): 213 return self.exception_labels[-1] 214 215 def add_exception_labels(self, handler_label, exit_label): 216 self.exception_labels.append((handler_label, exit_label)) 217 218 def drop_exception_labels(self): 219 self.exception_labels.pop() 220 221 def reserve_temp(self, n): 222 temp_position = self.temp_position 223 self.temp_position += n 224 self.unit.stack_temp_usage = max(self.unit.stack_temp_usage, self.temp_position) 225 return temp_position 226 227 def discard_temp(self, instructions): 228 for temp in instructions: 229 if isinstance(temp, LoadTemp): 230 self.temp_position -= 1 231 232 # Code writing methods. 233 234 def new_op(self, op): 235 236 "Add 'op' to the generated code." 237 238 # Optimise stack access by incorporating the source data directly into 239 # instructions. 240 241 self._optimise_stack_access(op) 242 243 # Optimise away constant storage if appropriate. 244 # The target and value loading operations are also removed. 245 246 if self._optimise_constant_storage(op): 247 return 248 249 self.adjust_stack(op) 250 self.code.append(op) 251 252 def new_ops(self, ops): 253 254 """ 255 Add copies of 'ops' to the generated code. This is typically used in 256 connection with sequences of temporary storage instructions. 257 """ 258 259 for op in ops: 260 self.new_op(op.copy()) 261 262 def remove_ops(self, n): 263 264 "Remove the last 'n' instructions." 265 266 for i in range(0, n): 267 op = self.code.pop() 268 self.revert_stack(op) 269 270 def replace_op(self, op): 271 272 "Replace the last added instruction with 'op'." 273 274 self.remove_ops(1) 275 self.new_op(op) 276 277 def remove_op_using_stack(self, op): 278 279 "Remove the instruction which created the top stack position." 280 281 position, op = self.stack[-1] 282 283 # NOTE: Prevent removal of non-end instructions. 284 285 if position < len(self.code) - 1: 286 return 0 287 else: 288 self.remove_ops(1) 289 return 1 290 291 def last_ops(self, n): 292 293 "Return the last 'n' added instructions in reverse chronological order." 294 295 ops = self.code[-n:] 296 ops.reverse() 297 return ops 298 299 def last_op(self): 300 301 "Return the last added instruction." 302 303 try: 304 return self.code[-1] 305 except IndexError: 306 return None 307 308 def set_last_invocation(self): 309 310 "Set this location as the point after the last invocation." 311 312 self.last_invocation = len(self.code) 313 314 # Internal helper methods. 315 316 def _visitAttr(self, node, classes): 317 318 """ 319 Visit the attribute-related 'node', generating instructions based on the 320 given 'classes'. 321 """ 322 323 self.dispatch(node.expr) 324 self._generateAttr(node, node.attrname, classes) 325 326 def _generateAttr(self, node, attrname, classes): 327 328 """ 329 Generate code for the access to 'attrname' using the given 'classes'. 330 """ 331 332 AddressInstruction, AddressContextInstruction, AttrInstruction, AttrIndexInstruction = classes 333 334 last = self.last_op() 335 336 # Where the last operation (defining the attribute owner) yields a 337 # constant... 338 339 if self._have_constant_input(0): 340 341 # Get the details of the access. 342 343 if isinstance(last.attr, Const): 344 target_name = last.attr.value_type_name() 345 else: 346 target = last.attr.value 347 348 if isinstance(target, Const): 349 target_name = target.value_type_name() 350 elif isinstance(target, Instance): 351 target_name = None # skip production of optimised code 352 else: 353 target_name = target.full_name() 354 355 # Only try and discover the position if the target can be resolved. 356 357 if target_name is not None: 358 359 # Access the object table to get the attribute position. 360 361 try: 362 table_entry = self.objtable.table[target_name] 363 except KeyError: 364 raise TranslateError(self.module.full_name(), node, 365 "No object entry exists for target %r." % target_name) 366 367 try: 368 pos = table_entry[attrname] 369 except KeyError: 370 raise TranslateError(self.module.full_name(), node, 371 "No attribute entry exists for name %r in target %r." % (attrname, target_name)) 372 373 # Produce a suitable instruction. 374 375 self.replace_op(AddressInstruction(pos)) 376 return 377 378 # Where the last operation involves the special 'self' name, check to 379 # see if the attribute is acceptably positioned and produce a direct 380 # access to the attribute. 381 382 elif self._optimise_self_access(attrname, (AddressInstruction, AddressContextInstruction, AttrInstruction)): 383 return 384 385 # Otherwise, perform a normal operation. 386 387 try: 388 index = self.objtable.get_index(attrname) 389 except self.objtable.TableError: 390 raise TranslateError(self.module.full_name(), node, 391 "No attribute entry exists for name %r." % attrname) 392 393 self.new_op(AttrIndexInstruction(index)) 394 395 def _startCallFunc(self): 396 397 "Record the location of the invocation." 398 399 self.new_op(MakeFrame()) # records the start of the frame 400 self.make_frame() 401 402 def _generateCallFunc(self, args, node): 403 404 """ 405 Support a generic function invocation using the given 'args', occurring 406 on the given 'node', where the expression providing the invocation 407 target has just been generated. 408 409 In other situations, the invocation is much simpler and does not need to 410 handle the full flexibility of a typical Python invocation. Internal 411 invocations, such as those employed by operators and certain 412 control-flow mechanisms, use predetermined arguments and arguably do not 413 need to support the same things as the more general invocations. 414 """ 415 416 target, context, temp = self._generateCallFuncContext() 417 self._generateCallFuncArgs(target, context, args, node) 418 return temp 419 420 def _generateCallFuncContext(self): 421 422 """ 423 Produce code which loads and checks the context of the current 424 invocation, the instructions for whose target have already been 425 produced, returning a list of instructions which reference the 426 invocation target. 427 """ 428 429 t = self._optimise_known_target() 430 if t: 431 target, context = t 432 else: 433 target, context = None, None 434 435 # Store the target in temporary storage for subsequent referencing. 436 437 temp = self._optimise_temp_storage() 438 439 # Where a target or context are not known or where an instance is known 440 # to be the context, load the context. 441 442 if context is None or isinstance(context, Instance): 443 self.new_ops(temp) 444 self.new_op(LoadContext()) 445 self.new_op(StoreFrame(0)) 446 447 # Otherwise omit the context. 448 449 else: 450 pass # NOTE: Class methods should be supported. 451 452 return target, context, temp 453 454 def _generateCallFuncArgs(self, target, context, args, node): 455 456 """ 457 Given invocation 'target' and 'context' information, a list of nodes 458 representing the 'args' (arguments), generate instructions which load 459 the arguments for the invocation defined by the given 'node'. 460 """ 461 462 # Evaluate the arguments. 463 464 employed_positions = set() 465 extra_keywords = [] 466 467 # Note the presence of the context in the frame where appropriate. 468 469 if context is None or isinstance(context, Instance): 470 ncontext = 1 471 expect_context = 0 472 elif isinstance(context, Class): 473 ncontext = 0 474 expect_context = 1 475 else: 476 ncontext = 0 477 expect_context = 0 478 479 first = 1 480 frame_pos = ncontext 481 482 for arg in args: 483 484 # Handle positional and keyword arguments separately. 485 486 if isinstance(arg, compiler.ast.Keyword): 487 488 # Optimise where the target is known now. 489 490 if target is not None: 491 492 # Find the parameter table entry for the target. 493 494 target_name = target.full_name() 495 496 # Look for a callable with the precise target name. 497 498 table_entry = self.paramtable.table[target_name] 499 500 # Look the name up in the parameter table entry. 501 502 try: 503 pos = table_entry[arg.name] 504 505 # Where no position is found, this could be an extra keyword 506 # argument. 507 508 except KeyError: 509 extra_keywords.append(arg) 510 continue 511 512 # Test for illegal conditions. 513 514 if pos in employed_positions: 515 raise TranslateError(self.module.full_name(), node, 516 "Keyword argument %r overwrites parameter %r." % (arg.name, pos)) 517 518 employed_positions.add(pos) 519 520 # Generate code for the keyword and the positioning 521 # operation. 522 523 self.dispatch(arg.expr) 524 self.new_op(StoreFrame(pos)) 525 526 # Otherwise, generate the code needed to obtain the details of 527 # the parameter location. 528 529 else: 530 531 # Combine the target details with the name to get the location. 532 # See the access method on the List class. 533 534 try: 535 paramindex = self.paramtable.get_index(arg.name) 536 537 # Where no position is found, this could be an extra keyword 538 # argument. 539 540 except self.paramtable.TableError: 541 extra_keywords.append(arg) 542 continue 543 544 # Generate code for the keyword and the positioning 545 # operation. 546 547 self.dispatch(arg.expr) 548 self.new_op(StoreFrameIndex(paramindex)) 549 550 # use (callable+0)+paramindex+table 551 # checks embedded offset against (callable+0) 552 # moves the top of stack to frame+position 553 554 else: 555 self.dispatch(arg) 556 self.new_op(StoreFrame(frame_pos)) 557 employed_positions.add(frame_pos) 558 559 # Check to see if the first argument is appropriate (compatible with 560 # the target where methods are being invoked via classes). 561 562 if first and expect_context: 563 continue_label = self.new_label() 564 self.new_op(CheckSelf()) 565 self.new_op(JumpIfTrue(continue_label)) 566 567 # Where the context is inappropriate, drop the incomplete frame and 568 # raise an exception. 569 570 self.new_op(DropFrame()) 571 572 # Pretend that the frame is now gone, generating suitable stack 573 # operations. 574 575 self.suspend_frame() 576 self.new_op(LoadResult()) 577 578 self.dispatch(compiler.ast.Name("TypeError")) 579 self.new_op(RaiseException()) 580 self.set_label(continue_label) 581 582 # Obtain the suspended frame for subsequent outcomes. 583 584 self.resume_frame() 585 586 first = 0 587 frame_pos += 1 588 589 # NOTE: Extra keywords are not supported. 590 # NOTE: Somehow, the above needs to be combined with * arguments. 591 592 # Either test for a complete set of arguments. 593 594 if target is not None: 595 596 # Make sure that enough arguments have been given. 597 598 nargs_max = len(target.positional_names) 599 ndefaults = len(target.defaults) 600 nargs_min = nargs_max - ndefaults 601 602 for i in range(ncontext, nargs_min): 603 if i not in employed_positions: 604 raise TranslateError(self.module.full_name(), node, 605 "Argument %r not supplied for %r: need at least %d arguments." % (i+1, target.name, nargs_min)) 606 607 nargs = len(args) 608 609 if nargs > nargs_max and not target.has_star and not target.has_dstar: 610 raise TranslateError(self.module.full_name(), node, 611 "Too many arguments for %r: need at most %d arguments." % (target.name, nargs_max)) 612 613 # Where defaults are involved, put them into the frame. 614 # Here, we use negative index values to visit the right hand end of 615 # the defaults list. 616 617 for pos in range(nargs_min, nargs_max): 618 if pos not in employed_positions: 619 self.new_op(LoadAddress(target.default_attrs[pos - nargs_min])) 620 self.new_op(StoreFrame(pos)) 621 622 frame_pos += 1 623 624 # Or generate instructions to do this at run-time. 625 # NOTE: CheckFrame has to check the number of arguments and to fill in 626 # NOTE: defaults; it also has to shift the invocation frame according to 627 # NOTE: the context in use. 628 629 else: 630 self.new_op(CheckFrame()) 631 632 def _doCallFunc(self, instructions): 633 634 "Make the invocation." 635 636 self.new_ops(instructions) 637 self.new_op(JumpWithFrame()) 638 639 def _endCallFunc(self, instructions=None, keep_frame=0): 640 641 "Finish the invocation and tidy up afterwards." 642 643 # NOTE: Exception handling required. 644 645 # Note this as the most recent invocation. 646 647 self.set_last_invocation() 648 649 self.new_op(DropFrame()) 650 if keep_frame: 651 self.suspend_frame() 652 else: 653 self.drop_frame() 654 self.new_op(LoadResult()) 655 if keep_frame: 656 self.resume_frame() 657 658 # Discard any temporary storage instructions. 659 660 if instructions is not None: 661 self.discard_temp(instructions) 662 663 def _visitName(self, node, classes): 664 665 """ 666 Visit the name-related 'node', generating instructions based on the 667 given 'classes'. 668 """ 669 670 name = node.name 671 scope = self.get_scope(name) 672 #print self.module.name, node.lineno, name, scope 673 self._generateName(name, scope, classes, node) 674 675 def _generateName(self, name, scope, classes, node): 676 677 """ 678 Generate code for the access to 'name' in 'scope' using the given 679 'classes', and using the given 'node' as the source of the access. 680 """ 681 682 NameInstruction, AddressInstruction = classes 683 684 if scope == "local": 685 unit = self.unit 686 if isinstance(unit, Function): 687 self.new_op(NameInstruction(unit.all_locals()[name])) 688 elif isinstance(unit, Class): 689 self.new_op(AddressInstruction(unit.all_class_attributes()[name])) 690 elif isinstance(unit, Module): 691 self.new_op(AddressInstruction(unit.module_attributes()[name])) 692 else: 693 raise TranslateError(self.module.full_name(), node, "Program unit %r has no local %r." % (unit, name)) 694 695 elif scope == "global": 696 globals = self.module.module_attributes() 697 if globals.has_key(name): 698 self.new_op(AddressInstruction(globals[name])) 699 else: 700 raise TranslateError(self.module.full_name(), node, "Module %r has no attribute %r." % (self.module, name)) 701 702 else: 703 self.new_op(AddressInstruction(self._get_builtin(name, node))) 704 705 def _get_builtin(self, name, node): 706 if self.builtins is not None: 707 try: 708 return self.builtins[name] 709 except KeyError: 710 raise TranslateError(self.module.full_name(), node, "No __builtins__ definition is available for name %r." % name) 711 else: 712 raise TranslateError(self.module.full_name(), node, "No __builtins__ module is available for name %r." % name) 713 714 # Optimisation tests. 715 716 def _should_optimise_constant_storage(self): 717 return "constant_storage" in self.optimisations 718 719 def _should_optimise_constant_test(self): 720 return "constant_test" in self.optimisations 721 722 def _should_optimise_known_target(self): 723 return "known_target" in self.optimisations 724 725 def _should_optimise_self_access(self): 726 return "self_access" in self.optimisations 727 728 def _should_optimise_temp_storage(self): 729 return "temp_storage" in self.optimisations 730 731 def _should_optimise_stack_access(self): 732 return "stack_access" in self.optimisations 733 734 # Simple tests. 735 736 def _is_constant_input(self, instruction): 737 738 "Return whether 'instruction' provides a constant input." 739 740 return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 or \ 741 isinstance(instruction, LoadConst) 742 743 def _is_local_input(self, instruction): 744 745 "Return whether 'instruction' provides a local input." 746 747 return isinstance(instruction, (LoadName, LoadTemp)) 748 749 def _is_unaffected(self, instruction, position): 750 751 """ 752 Return whether 'instruction' is unaffected by side-effects since it 753 occurs at a 'position' later than the last invocation. 754 """ 755 756 return isinstance(instruction, (LoadResult, LoadAddress)) and ( 757 self.last_invocation is None or position >= self.last_invocation) 758 759 # Convenience tests. 760 761 def _have_constant_input(self, n): 762 763 "Return whether the last 'n' instructions provide constant inputs." 764 765 last = self.last_ops(n+1) 766 return len(last) > n and self._is_constant_input(last[n]) 767 768 def _have_known_target(self): 769 770 "Return whether the last instruction is a known target." 771 772 return self._have_constant_input(0) 773 774 def _have_self_input(self): 775 776 "Return whether the last instruction is a reference to self." 777 778 last = self.last_op() 779 return isinstance(self.unit, Function) and \ 780 self.unit.is_method() and isinstance(last, LoadName) and \ 781 last.attr.name == "self" 782 783 def _have_temp_compatible_access(self): 784 785 """ 786 Indicate whether the last instruction can be used in place of access to 787 a temporary variable retaining the result of the last instruction. 788 """ 789 790 last = self.last_op() 791 # NOTE: Should expand to cover LoadAttr and LoadAttrIndex, but this 792 # NOTE: would require inspection of the stack operations. 793 return isinstance(last, (LoadName, LoadTemp, LoadAddress, LoadConst)) 794 795 def _get_access_instructions(self, instruction): 796 797 """ 798 Get the stack access instructions employed by the given 'instruction'. 799 It is assumed that the source of the data communicated through the stack 800 is not modified since the storage of the data. However, since the stack 801 should only be employed within statements, there should be no risk of 802 side-effects for local storage. 803 """ 804 805 access_ops = [] 806 for stack_op in instruction.accesses: 807 if isinstance(stack_op, (StackLoad, StackPull)): 808 position, op = self.stack[stack_op.n] 809 810 # Insist on constants, locals or other things which should not 811 # have been changed. 812 813 if not self._is_constant_input(op) and not self._is_local_input(op) and \ 814 not self._is_unaffected(op, position): 815 816 return None 817 818 access_ops.append((op, stack_op)) 819 820 return access_ops 821 822 # Optimisation methods. See the supported_optimisations class attribute. 823 824 def _optimise_temp_storage(self): 825 826 """ 827 Where the next operation would involve storing a value into temporary 828 storage at 'temp_position', record and remove any simple instruction 829 which produced the value to be stored such that instead of subsequently 830 accessing the temporary storage, that instruction is substituted. 831 832 If no optimisation can be achieved, a StoreTemp instruction is produced 833 and the appropriate LoadTemp instruction is returned. 834 835 All returned instructions are provided in a list. 836 837 Restriction: for use only in situations where the source of the 838 temporary data will not be disturbed between its first access and its 839 subsequent use. 840 """ 841 842 if self._should_optimise_temp_storage() and \ 843 self._have_temp_compatible_access(): 844 845 last = self.last_op() 846 self.remove_ops(1) 847 return [last] 848 else: 849 temp_position = self.reserve_temp(1) 850 self.new_op(StoreTemp(temp_position)) 851 return [LoadTemp(temp_position)] 852 853 def _optimise_constant_storage(self, instruction): 854 855 """ 856 Where this operation should store a constant into a target which is 857 also constant, optimise away both operations. 858 """ 859 860 if self._should_optimise_constant_storage() and \ 861 isinstance(instruction, (StoreName, StoreAddress)) and \ 862 instruction.attr.assignments == 1: 863 864 return 1 865 else: 866 return 0 867 868 def _optimise_constant_test(self, instruction): 869 870 """ 871 Where this operation tests the topmost stack value which happens to be 872 a constant against another stack value, merge the last instruction which 873 loaded the constant into the current 'instruction'. 874 """ 875 876 if self._should_optimise_constant_test() and \ 877 instruction is TestIdentity and \ 878 self._have_constant_input(0): 879 880 last = self.last_op() 881 self.replace_op(TestIdentityAddress(last.attr)) 882 return 1 883 else: 884 return 0 885 886 def _optimise_known_target(self): 887 888 """ 889 Where the target of an invocation is known, provide information about it 890 and its context. If a class is being invoked and the conditions are 891 appropriate, get information about the specific initialiser. 892 """ 893 894 if self._should_optimise_known_target() and self._have_known_target(): 895 last = self.last_op() 896 target = last.attr.value 897 context = last.attr.context 898 899 # Handle calls to classes. 900 901 if isinstance(target, Class): 902 target = target.get_instantiator() 903 context = Instance() 904 905 # A special context is chosen to avoid generating unnecessary 906 # context loading and checking instructions. 907 908 return target, context 909 else: 910 return None 911 912 def _optimise_self_access(self, attrname, classes): 913 914 """ 915 Where the provided 'attrname' accesses an attribute which occupies the 916 same position in all possible objects which can be accessed, generate an 917 instruction using one of the given 'classes', accessing the attribute 918 directly. 919 """ 920 921 AddressInstruction, AddressContextInstruction, AttrInstruction = classes 922 923 if self._should_optimise_self_access() and self._have_self_input() and \ 924 not self.unit.is_relocated(attrname): 925 926 # Either generate an instruction operating on an instance attribute. 927 928 try: 929 attr = self.unit.parent.instance_attributes()[attrname] 930 self.new_op(AttrInstruction(attr)) 931 932 # Or generate an instruction operating on a class attribute. 933 934 except KeyError: 935 attr = self.unit.parent.all_attributes()[attrname] 936 new_attr = attr.via_instance() 937 self.new_op(AddressContextInstruction(new_attr)) 938 939 return 1 940 else: 941 return 0 942 943 def _optimise_stack_access(self, instruction): 944 945 """ 946 Optimise stack access for the given 'instruction', replacing stack 947 operations with instructions directly accessing the required data. 948 """ 949 950 if self._should_optimise_stack_access(): 951 ops = self._get_access_instructions(instruction) 952 if ops is not None: 953 instruction.accesses = [] 954 for op, stack_op in ops: 955 if self.remove_op_using_stack(op): 956 instruction.accesses.append(op) 957 958 # Remove the stack side-effects of these accesses. 959 960 op.remove_results() 961 else: 962 instruction.accesses.append(stack_op) 963 964 # Visitor methods. 965 966 def default(self, node, *args): 967 raise TranslateError(self.module.full_name(), node, "Node class %r is not supported." % node.__class__) 968 969 def dispatch(self, node, *args): 970 return ASTVisitor.dispatch(self, node, *args) 971 972 def _visitUnary(self, node, method): 973 974 """ 975 _t = node.expr 976 try: 977 _result = _t.__pos__() 978 except AttributeError: 979 raise TypeError 980 """ 981 982 end_call_label = self.new_label() 983 end_label = self.new_label() 984 985 # Evaluate and store the operand in temporary storage. 986 987 self.dispatch(node.expr) 988 temp = self._optimise_temp_storage() 989 990 # Produce the invocation. 991 992 self._startCallFunc() 993 self.new_ops(temp) 994 995 # Get the method on temp. 996 997 self._generateAttr(node, method, self.attr_load_instructions) 998 999 # Add exception handling to the method acquisition instructions where 1000 # the attribute access cannot be resolved at compile-time. 1001 1002 if not self._optimise_known_target(): 1003 self.dispatch(compiler.ast.Name("AttributeError")) 1004 self.new_op(CheckException()) 1005 self.new_op(JumpIfTrue(end_call_label)) 1006 1007 temp_method = self._optimise_temp_storage() 1008 1009 # Add arguments. 1010 # NOTE: No support for defaults. 1011 1012 self.new_ops(temp) # Explicit context as first argument. 1013 self._doCallFunc(temp_method) 1014 self._endCallFunc(temp_method, keep_frame=1) 1015 self.new_op(Jump(end_label)) 1016 1017 # End method attempt. 1018 1019 self.set_label(end_call_label) 1020 self._endCallFunc() # From the method call. 1021 1022 # Raise a TypeError. 1023 1024 self.dispatch(compiler.ast.Name("TypeError")) 1025 self.new_op(RaiseException()) 1026 1027 self.set_label(end_label) 1028 1029 # Compilation duties... 1030 1031 self.discard_temp(temp) 1032 1033 def _visitBinary(self, node, left_method, right_method): 1034 1035 """ 1036 _t1 = node.left 1037 _t2 = node.right 1038 try: 1039 _result = _t1.__add__(_t2) 1040 if _result is NotImplemented: 1041 raise AttributeError 1042 except AttributeError: 1043 try: 1044 _result = _t2.__radd__(_t1) 1045 if _result is NotImplemented: 1046 raise AttributeError 1047 except AttributeError: 1048 raise TypeError 1049 """ 1050 1051 end_left_label = self.new_label() 1052 right_label = self.new_label() 1053 end_right_label = self.new_label() 1054 type_error_label = self.new_label() 1055 end_label = self.new_label() 1056 1057 # Evaluate and store the left operand in temporary storage. 1058 1059 self.dispatch(node.left) 1060 temp1 = self._optimise_temp_storage() 1061 1062 # Evaluate and store the right operand in temporary storage. 1063 1064 self.dispatch(node.right) 1065 temp2 = self._optimise_temp_storage() 1066 1067 # Left method. 1068 1069 self._startCallFunc() 1070 self.new_ops(temp1) 1071 1072 # Get left method on temp1. 1073 1074 self._generateAttr(node, left_method, self.attr_load_instructions) 1075 1076 # Add exception handling to the method acquisition instructions where 1077 # the attribute access cannot be resolved at compile-time. 1078 1079 if not self._optimise_known_target(): 1080 self.dispatch(compiler.ast.Name("AttributeError")) 1081 self.new_op(CheckException()) 1082 self.new_op(JumpIfTrue(end_left_label)) 1083 1084 temp_method = self._optimise_temp_storage() 1085 1086 # Add arguments. 1087 # NOTE: No support for defaults. 1088 1089 self.new_ops(temp1) # Explicit context as first argument. 1090 self.new_ops(temp2) 1091 self._doCallFunc(temp_method) 1092 self._endCallFunc(temp_method, keep_frame=1) 1093 1094 # Test for NotImplemented. 1095 # Don't actually raise an exception. 1096 1097 self.dispatch(compiler.ast.Name("NotImplemented")) 1098 if not self._optimise_constant_test(TestIdentity): 1099 self.new_op(TestIdentity()) 1100 self.new_op(JumpIfTrue(right_label)) 1101 self.new_op(Jump(end_label)) 1102 1103 # End left method attempt. 1104 1105 self.set_label(end_left_label) 1106 self._endCallFunc() # From the left method call. 1107 1108 # Right method. 1109 1110 self.set_label(right_label) 1111 self._startCallFunc() 1112 self.new_ops(temp2) 1113 1114 # Get right method on temp2. 1115 1116 self._generateAttr(node, right_method, self.attr_load_instructions) 1117 1118 # Add exception handling to the method acquisition instructions where 1119 # the attribute access cannot be resolved at compile-time. 1120 1121 if not self._optimise_known_target(): 1122 self.dispatch(compiler.ast.Name("AttributeError")) 1123 self.new_op(CheckException()) 1124 self.new_op(JumpIfTrue(end_right_label)) 1125 1126 temp_method = self._optimise_temp_storage() 1127 1128 # Add arguments. 1129 # NOTE: No support for defaults. 1130 1131 self.new_ops(temp2) # Explicit context as first argument. 1132 self.new_ops(temp1) 1133 self._doCallFunc(temp_method) 1134 self._endCallFunc(temp_method, keep_frame=1) 1135 1136 # Test for NotImplemented. 1137 # Don't actually raise an exception. 1138 1139 self.dispatch(compiler.ast.Name("NotImplemented")) 1140 if not self._optimise_constant_test(TestIdentity): 1141 self.new_op(TestIdentity()) 1142 self.new_op(JumpIfTrue(type_error_label)) 1143 self.new_op(Jump(end_label)) 1144 1145 # End right method attempt. 1146 1147 self.set_label(end_right_label) 1148 self._endCallFunc() # From the right method call. 1149 1150 # Raise a TypeError. 1151 1152 self.set_label(type_error_label) 1153 self.dispatch(compiler.ast.Name("TypeError")) 1154 self.new_op(RaiseException()) 1155 1156 self.set_label(end_label) 1157 1158 # Compilation duties... 1159 1160 self.discard_temp(temp1) 1161 self.discard_temp(temp2) 1162 1163 def visitAdd(self, node): 1164 self._visitBinary(node, "__add__", "__radd__") 1165 1166 def visitAnd(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "And") 1167 1168 def visitAssert(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Assert") 1169 1170 def visitAssign(self, node): 1171 self.dispatch(node.expr) 1172 for n in node.nodes: 1173 self.dispatch(n) 1174 1175 def visitAssAttr(self, node): 1176 self._visitAttr(node, self.attribute_store_instructions) 1177 1178 def visitAssList(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "AssList") 1179 1180 def visitAssName(self, node): 1181 self._visitName(node, (StoreName, StoreAddress)) 1182 1183 visitAssTuple = visitAssList 1184 1185 def visitAugAssign(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "AugAssign") 1186 1187 def visitBackquote(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Backquote") 1188 1189 def visitBitand(self, node): 1190 self._visitBinary(node, "__and__", "__rand__") 1191 1192 def visitBitor(self, node): 1193 self._visitBinary(node, "__or__", "__ror__") 1194 1195 def visitBitxor(self, node): 1196 self._visitBinary(node, "__xor__", "__rxor__") 1197 1198 def visitBreak(self, node): 1199 next_label, exit_label = self.get_loop_labels() 1200 self.new_op(Jump(exit_label)) 1201 1202 def visitCallFunc(self, node): 1203 1204 """ 1205 Evaluate positional arguments, evaluate and store keyword arguments in 1206 the correct location, then invoke the function. 1207 """ 1208 1209 # Mark the frame, evaluate the target, generate the call. 1210 1211 self._startCallFunc() 1212 self.dispatch(node.node) 1213 temp = self._generateCallFunc(node.args, node) 1214 self._doCallFunc(temp) 1215 self._endCallFunc(temp) 1216 1217 def visitClass(self, node): 1218 1219 # Store the name. 1220 1221 self.new_op(LoadConst(node.unit)) 1222 self._visitName(node, (StoreName, StoreAddress)) 1223 1224 # Visit the code. 1225 1226 unit = self.unit 1227 self.unit = node.unit 1228 self.unit.code_location = self.module.code_location # class body code is not independently addressable 1229 self.dispatch(node.code) 1230 self.unit = unit 1231 1232 def visitCompare(self, node): 1233 1234 """ 1235 self.dispatch(node.expr) 1236 for op_name, next_node in compare.ops: 1237 methods = self.comparison_methods[op_name] 1238 if methods is not None: 1239 # Generate method call using evaluated argument and next node. 1240 else: 1241 # Deal with the special operators. 1242 # Provide short-circuiting. 1243 """ 1244 1245 def visitConst(self, node): 1246 const = self.module.constant_values[node.value] 1247 self.new_op(LoadConst(const)) 1248 1249 def visitContinue(self, node): 1250 next_label, exit_label = self.get_loop_labels() 1251 self.new_op(Jump(next_label)) 1252 1253 def visitDecorators(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Decorators") 1254 1255 def visitDict(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Dict") 1256 1257 def visitDiscard(self, node): 1258 self.dispatch(node.expr) 1259 1260 def visitDiv(self, node): 1261 self._visitBinary(node, "__div__", "__rdiv__") 1262 1263 def visitEllipsis(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Ellipsis") 1264 1265 def visitExec(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Exec") 1266 1267 def visitExpression(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Expression") 1268 1269 def visitFloorDiv(self, node): 1270 self._visitBinary(node, "__floordiv__", "__rfloordiv__") 1271 1272 def visitFor(self, node): 1273 exit_label = self.new_label() 1274 next_label = self.new_label() 1275 else_label = self.new_label() 1276 1277 # Get the "list" to be iterated over, obtain its iterator. 1278 1279 self._startCallFunc() 1280 self.dispatch(node.list) 1281 self._generateAttr(node, "__iter__", self.attr_load_instructions) 1282 temp = self._generateCallFunc([], node) 1283 self._doCallFunc(temp) 1284 self._endCallFunc(temp) 1285 1286 # Iterator on stack. 1287 1288 temp_iterator_position = self.reserve_temp(1) 1289 temp_iterator = [LoadTemp(temp_iterator_position)] 1290 1291 self.new_op(StoreTemp(temp_iterator_position)) 1292 1293 # In the loop... 1294 1295 self.set_label(next_label) 1296 1297 # Use the iterator to get the next value. 1298 1299 self._startCallFunc() 1300 self.new_ops(temp_iterator) 1301 self._generateAttr(node, "next", self.attr_load_instructions) 1302 temp = self._generateCallFunc([], node) 1303 self._doCallFunc(temp) 1304 self._endCallFunc(temp) 1305 1306 # Test for StopIteration. 1307 1308 self.dispatch(compiler.ast.Name("StopIteration")) 1309 self.new_op(CheckException()) 1310 if node.else_ is not None: 1311 self.new_op(JumpIfTrue(else_label)) 1312 else: 1313 self.new_op(JumpIfTrue(exit_label)) 1314 1315 # Assign to the target. 1316 1317 self.dispatch(node.assign) 1318 1319 # Process the body with the current next and exit points. 1320 1321 self.add_loop_labels(next_label, exit_label) 1322 self.dispatch(node.body) 1323 self.drop_loop_labels() 1324 1325 # Repeat the loop. 1326 1327 self.new_op(Jump(next_label)) 1328 1329 # Produce the "else" section. 1330 1331 if node.else_ is not None: 1332 self.set_label(exit_label) 1333 self.dispatch(node.else_) 1334 1335 # After the loop... 1336 1337 self.set_label(exit_label) 1338 1339 # Compilation duties... 1340 1341 self.discard_temp(temp_iterator) 1342 1343 def visitFrom(self, node): pass 1344 1345 def visitFunction(self, node): 1346 1347 # Only store the name when visiting this node from outside. 1348 1349 if self.unit is not node.unit: 1350 self.new_op(LoadConst(node.unit)) 1351 self._visitName(node, (StoreName, StoreAddress)) 1352 1353 # Generate the default initialisation code. 1354 1355 for attr, default in zip(node.unit.default_attrs, node.unit.defaults): 1356 self.dispatch(default) 1357 self.new_op(StoreAddress(attr)) 1358 1359 # Visiting of the code occurs when get_code is invoked on this node. 1360 1361 else: 1362 self.dispatch(node.code) 1363 if not isinstance(self.last_op(), Return): 1364 self.dispatch(compiler.ast.Name("None")) 1365 self.new_op(Return()) 1366 1367 def visitGenExpr(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "GenExpr") 1368 1369 def visitGenExprFor(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "GenExprFor") 1370 1371 def visitGenExprIf(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "GenExprIf") 1372 1373 def visitGenExprInner(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "GenExprInner") 1374 1375 def visitGetattr(self, node): 1376 self._visitAttr(node, self.attribute_load_instructions) 1377 1378 def visitGlobal(self, node): pass 1379 1380 def visitIf(self, node): 1381 first = 1 1382 exit_label = self.new_label() 1383 1384 for test, body in node.tests + [(None, node.else_)]: 1385 if body is None: 1386 break 1387 if not first: 1388 self.set_label(next_label) 1389 if test is not None: 1390 self.dispatch(test) 1391 next_label = self.new_label() 1392 self.new_op(JumpIfFalse(next_label)) 1393 self.dispatch(body) 1394 self.new_op(Jump(exit_label)) 1395 first = 0 1396 1397 self.set_label(exit_label) 1398 1399 def visitImport(self, node): pass 1400 1401 def visitInvert(self, node): 1402 self._visitUnary(node, "__invert__") 1403 1404 def visitKeyword(self, node): pass 1405 1406 def visitLambda(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Lambda") 1407 1408 def visitLeftShift(self, node): 1409 self._visitBinary(node, "__lshift__", "__rlshift__") 1410 1411 def visitList(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "List") 1412 1413 def visitListComp(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "ListComp") 1414 1415 def visitListCompFor(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "ListCompFor") 1416 1417 def visitListCompIf(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "ListCompIf") 1418 1419 def visitMod(self, node): 1420 self._visitBinary(node, "__mod__", "__rmod__") 1421 1422 def visitModule(self, node): 1423 self.dispatch(node.node) 1424 1425 def visitMul(self, node): 1426 self._visitBinary(node, "__mul__", "__rmul__") 1427 1428 def visitName(self, node): 1429 if node.name == "None": 1430 const = self.module.constant_values[None] 1431 self.new_op(LoadConst(const)) 1432 else: 1433 self._visitName(node, (LoadName, LoadAddress)) 1434 1435 def visitNot(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Not") 1436 1437 def visitOr(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Or") 1438 1439 def visitPass(self, node): pass 1440 1441 def visitPower(self, node): 1442 self._visitBinary(node, "__pow__", "__rpow__") 1443 1444 def visitPrint(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Print") 1445 1446 def visitPrintnl(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Printnl") 1447 1448 def visitRaise(self, node): 1449 # NOTE: expr1 only => instance provided 1450 self.dispatch(node.expr1) 1451 1452 if node.expr2 is not None: 1453 self.dispatch(node.expr2) 1454 self._doCallFunc() 1455 1456 self.new_op(RaiseException()) 1457 1458 def visitReturn(self, node): 1459 if node.value is not None: 1460 self.dispatch(node.value) 1461 else: 1462 self.dispatch(compiler.ast.Name("None")) 1463 self.new_op(Return()) 1464 1465 def visitRightShift(self, node): 1466 self._visitBinary(node, "__rshift__", "__rrshift__") 1467 1468 def visitSlice(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Slice") 1469 1470 def visitStmt(self, node): 1471 for n in node.nodes: 1472 self.dispatch(n) 1473 self.reset_stack() 1474 1475 def visitSub(self, node): 1476 self._visitBinary(node, "__sub__", "__rsub__") 1477 1478 def visitSubscript(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Subscript") 1479 1480 def visitTryExcept(self, node): 1481 exit_label = self.new_label() 1482 handler_label = self.new_label() 1483 1484 self.add_exception_labels(handler_label, exit_label) 1485 1486 # Try... 1487 # Produce the code, then jump to the exit. 1488 1489 self.dispatch(node.body) 1490 self.new_op(Jump(exit_label)) 1491 1492 # Start of handlers. 1493 1494 self.set_label(handler_label) 1495 for name, assignment, handler in node.handlers: 1496 next_label = self.new_label() 1497 1498 # Test the given exception against the current exception. 1499 1500 if name is not None: 1501 self.dispatch(name) 1502 self.new_op(CheckException()) 1503 self.new_op(JumpIfFalse(next_label)) 1504 1505 # Handle assignment to exception variable. 1506 1507 if assignment is not None: 1508 self.dispatch(assignment) 1509 1510 # Produce the handler code, then jump to the exit. 1511 1512 self.dispatch(handler) 1513 self.new_op(Jump(exit_label)) 1514 1515 self.set_label(next_label) 1516 1517 # Unhandled exceptions. 1518 1519 self.new_op(LoadException()) 1520 self.new_op(RaiseException()) 1521 1522 # After exception 1523 1524 self.set_label(exit_label) 1525 1526 # Optional else clause. 1527 1528 if node.else_ is not None: 1529 self.dispatch(node.else_) 1530 1531 self.drop_exception_labels() 1532 1533 def visitTryFinally(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "TryFinally") 1534 1535 def visitTuple(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Tuple") 1536 1537 def visitUnaryAdd(self, node): 1538 self._visitUnary(node, "__pos__") 1539 1540 def visitUnarySub(self, node): 1541 self._visitUnary(node, "__neg__") 1542 1543 def visitWhile(self, node): 1544 exit_label = self.new_label() 1545 next_label = self.new_label() 1546 else_label = self.new_label() 1547 1548 self.set_label(next_label) 1549 self.dispatch(node.test) 1550 if node.else_ is not None: 1551 self.new_op(JumpIfFalse(else_label)) 1552 else: 1553 self.new_op(JumpIfFalse(exit_label)) 1554 1555 self.add_loop_labels(next_label, exit_label) 1556 1557 self.dispatch(node.body) 1558 self.new_op(Jump(next_label)) 1559 1560 if node.else_ is not None: 1561 self.set_label(else_label) 1562 self.dispatch(node.else_) 1563 1564 self.set_label(exit_label) 1565 self.drop_loop_labels() 1566 1567 def visitWith(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "With") 1568 1569 def visitYield(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "Yield") 1570 1571 # Useful data. 1572 1573 comparison_methods = { 1574 "==" : ("__eq__", "__ne__"), 1575 "!=" : ("__ne__", "__eq__"), 1576 "<" : ("__lt__", "__gt__"), 1577 "<=" : ("__le__", "__ge__"), 1578 ">=" : ("__ge__", "__le__"), 1579 ">" : ("__gt__", "__lt__"), 1580 "is" : None, 1581 "is not" : None, 1582 "in" : None, 1583 "not in" : None 1584 } 1585 1586 # vim: tabstop=4 expandtab shiftwidth=4