1 #!/usr/bin/env python 2 3 """ 4 Annotate program node structures. The code in this module operates upon nodes 5 which are produced when simplifying AST node trees originating from the compiler 6 module. 7 8 Copyright (C) 2006, 2007 Paul Boddie <paul@boddie.org.uk> 9 10 This software is free software; you can redistribute it and/or 11 modify it under the terms of the GNU General Public License as 12 published by the Free Software Foundation; either version 2 of 13 the License, or (at your option) any later version. 14 15 This software is distributed in the hope that it will be useful, 16 but WITHOUT ANY WARRANTY; without even the implied warranty of 17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 GNU General Public License for more details. 19 20 You should have received a copy of the GNU General Public 21 License along with this library; see the file LICENCE.txt 22 If not, write to the Free Software Foundation, Inc., 23 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA 24 25 -------- 26 27 To use this module, the easiest approach is to use the load function: 28 29 load(filename, builtins) 30 31 To control module importing, an importer should be constructed and employed. 32 Here, the standard path for module searching is used: 33 34 importer = Importer(sys.path) 35 load(filename, builtins, importer) 36 37 Underneath the load function, the annotate function provides support for 38 annotating modules already processed by simplify and fixnames: 39 40 annotate(module, builtins) 41 42 And at the most basic level, the most intricate approach involves obtaining an 43 Annotator object: 44 45 annotator = Annotator() 46 47 Then, processing an existing module with it: 48 49 annotator.process(module) 50 51 If a module containing built-in classes and functions has already been 52 annotated, such a module should be passed in as an additional argument: 53 54 annotator.process(module, builtins) 55 """ 56 57 from simplified import * 58 import simplify, fixnames # for the load function 59 import compiler 60 import os 61 62 class System: 63 64 """ 65 A class maintaining the state of the annotation system. When the system 66 counter can no longer be incremented by any annotation operation, the 67 system may be considered stable and fully annotated. 68 """ 69 70 def __init__(self): 71 self.count = 0 72 73 def init(self, node): 74 75 "Initialise a 'node' for annotation." 76 77 if not hasattr(node, "types"): 78 node.types = [] 79 80 def annotate(self, node, types): 81 82 "Annotate the given 'node' with the given 'types'." 83 84 self.init(node) 85 self.combine(node.types, types) 86 87 def combine(self, target, types): 88 89 """ 90 Combine the 'target' list with the given 'types', counting new members. 91 """ 92 93 for type in types: 94 if type not in target: 95 target.append(type) 96 self.count += 1 97 98 system = System() 99 100 # Exceptions. 101 102 class AnnotationError(SimplifiedError): 103 104 "An error in the annotation process." 105 106 pass 107 108 class AnnotationMessage(Exception): 109 110 "A lesser annotation error." 111 112 pass 113 114 # Annotation. 115 116 class Annotator(Visitor): 117 118 """ 119 The type annotator which traverses the program nodes, typically depth-first, 120 and maintains a record of the current set of types applying to the currently 121 considered operation. Such types are also recorded on the nodes, and a 122 special "system" record is maintained to monitor the level of annotation 123 activity with a view to recognising when no more annotations are possible. 124 125 Throughout the annotation activity, type information consists of lists of 126 Attribute objects where such objects retain information about the context of 127 the type (since a value in the program may be associated with an object or 128 class) and the actual type of the value being manipulated. Upon accessing 129 attribute information on namespaces, additional accessor information is also 130 exchanged - this provides a means of distinguishing between the different 131 types possible when the means of constructing the namespace may depend on 132 run-time behaviour. 133 134 Covered: Assign, CheckExc, Conditional, Global, Import, InvokeBlock, 135 InvokeFunction, LoadAttr, LoadExc, LoadName, LoadRef, LoadTemp, 136 Module, Not, Pass, Raise, ReleaseTemp, ReturnFromBlock, 137 ReturnFromFunction, StoreAttr, StoreName, StoreTemp, Subprogram, 138 Try. 139 """ 140 141 def __init__(self, importer=None): 142 143 "Initialise the visitor with an optional 'importer'." 144 145 Visitor.__init__(self) 146 self.system = system 147 self.importer = importer or Importer() 148 149 # Satisfy visitor issues. 150 151 self.visitor = self 152 153 def process(self, module, builtins=None): 154 155 """ 156 Process the given 'module', using the optional 'builtins' to access 157 built-in classes and functions. 158 """ 159 160 self.subprograms = [] 161 self.current_subprograms = [] 162 self.current_namespaces = [] 163 self.namespace = None 164 self.module = module 165 166 # Give constants their own namespace. 167 168 for value, constant in module.simplifier.constants.items(): 169 constant.namespace = Namespace() 170 171 # Process the module, supplying builtins if possible. 172 173 self.builtins = builtins 174 self.global_namespace = Namespace() 175 176 if builtins is not None: 177 self.builtins_namespace = builtins.namespace 178 else: 179 self.builtins_namespace = self.global_namespace 180 181 return self.process_node(module, self.global_namespace) 182 183 def process_node(self, node, locals): 184 185 """ 186 Process a subprogram or module 'node', indicating the initial 'locals'. 187 Return an annotated subprogram or module. Note that this method may 188 mutate nodes in the original program. 189 """ 190 191 # Record the current subprogram and namespace. 192 193 self.current_subprograms.append(node) 194 195 # Determine the namespace. 196 197 self.current_namespaces.append(self.namespace) 198 self.namespace = locals 199 200 # Add namespace details to any structure involved. 201 202 if getattr(node, "structure", None) is not None: 203 node.structure.namespace = Namespace() 204 205 # Initialise bases where appropriate. 206 207 if hasattr(node.structure, "bases"): 208 base_refs = [] 209 for base in node.structure.bases: 210 self.dispatch(base) 211 base_refs.append(self.namespace.types) 212 node.structure.base_refs = base_refs 213 214 # Dispatch to the code itself. 215 216 node.namespace = self.namespace 217 result = self.dispatch(node) 218 result.namespace = self.namespace 219 220 # Obtain the return values. 221 222 self.last_returns = self.namespace.returns 223 self.last_raises = self.namespace.raises 224 self.returned_locals = self.namespace.return_locals 225 226 # Restore the previous subprogram and namespace. 227 228 self.namespace = self.current_namespaces.pop() 229 self.current_subprograms.pop() 230 231 return result 232 233 def annotate(self, node, types=None): 234 235 """ 236 Annotate the given 'node' in the system, using either the optional 237 'types' or the namespace's current type information. 238 """ 239 240 self.system.annotate(node, types or self.namespace.types) 241 242 def annotate_parameters(self, node, items): 243 244 """ 245 Annotate the given 'node' using the given 'items' and updating the 246 system's annotation counter. 247 """ 248 249 if not hasattr(node, "paramtypes"): 250 node.paramtypes = {} 251 252 for param, types in items: 253 if not node.paramtypes.has_key(param): 254 node.paramtypes[param] = [] 255 self.system.combine(node.paramtypes[param], types) 256 257 # Visitor methods. 258 259 def default(self, node): 260 261 """ 262 Process the given 'node', given that it does not have a specific 263 handler. 264 """ 265 266 raise AnnotationMessage, "Node '%s' not supported." % node 267 268 def dispatch(self, node, *args): 269 try: 270 return Visitor.dispatch(self, node, *args) 271 except AnnotationError, exc: 272 exc.add(node) 273 raise 274 except AnnotationMessage, exc: 275 raise AnnotationError(exc, node) 276 277 # Specific node methods. 278 279 def visitAssign(self, assign): 280 281 """ 282 Return the 'assign' node whose contents (merely a group of nodes) have 283 been processed. 284 """ 285 286 assign.code = self.dispatches(assign.code) 287 return assign 288 289 def visitCheckExc(self, checkexc): 290 291 """ 292 Return the 'checkexc' node, processing the expression to find the 293 possible types of the exception, and processing each choice to build a 294 list of checked types for the exception. 295 """ 296 297 checkexc.expr = self.dispatch(checkexc.expr) 298 expr_types = self.namespace.types 299 choice_types = [] 300 choices = [] 301 for choice in checkexc.choices: 302 choices.append(self.dispatch(choice)) 303 choice_types += self.namespace.types 304 for expr_type in expr_types: 305 if expr_type.type.get_class() not in choice_types: 306 self._prune_non_accesses(checkexc.expr, expr_type) 307 return checkexc 308 309 def visitConditional(self, conditional): 310 311 """ 312 Return the 'conditional' node, processing the test, body and else 313 clauses and recording their processed forms. The body and else clauses 314 are processed within their own namespaces, and the test is also 315 processed in its own namespace if 'isolate_test' is set on the 316 'conditional' node. 317 """ 318 319 # Conditionals keep local namespace changes isolated. 320 # With Return nodes inside the body/else sections, the changes are 321 # communicated to the caller. 322 323 is_module = self.namespace is self.module.namespace 324 325 # Where the test is closely associated with the body, save the namespace 326 # before entering the test. 327 328 if conditional.isolate_test: 329 saved_namespace = self.namespace 330 self.namespace = Namespace() 331 if is_module: 332 self.module.namespace = self.namespace 333 self.namespace.merge_namespace(saved_namespace) 334 335 conditional.test = self.dispatch(conditional.test) 336 337 # Where the test may affect the body and the else clause, save the 338 # namespace after processing the test. 339 340 if not conditional.isolate_test: 341 saved_namespace = self.namespace 342 self.namespace = Namespace() 343 if is_module: 344 self.module.namespace = self.namespace 345 self.namespace.merge_namespace(saved_namespace) 346 347 # NOTE: Exception recording. 348 349 else: 350 test_raises = [] 351 combine(test_raises, self.namespace.raises) 352 353 # Process the body clause. 354 355 conditional.body = self.dispatches(conditional.body) 356 body_namespace = self.namespace 357 358 # Use the saved namespace as a template for the else clause. 359 360 self.namespace = Namespace() 361 if is_module: 362 self.module.namespace = self.namespace 363 self.namespace.merge_namespace(saved_namespace) 364 365 # Process the else clause. 366 367 conditional.else_ = self.dispatches(conditional.else_) 368 else_namespace = self.namespace 369 370 # Merge the body and else namespaces. 371 372 self.namespace = Namespace() 373 if is_module: 374 self.module.namespace = self.namespace 375 self.namespace.merge_namespace(body_namespace) 376 self.namespace.merge_namespace(else_namespace) 377 378 # NOTE: Test of exception type pruning based on the test/body. 379 # Note that the checked exceptions are tested for re-raising. 380 381 if conditional.isolate_test: 382 for exc_type in test_raises: 383 if exc_type not in body_namespace.raises: 384 self.namespace.revoke_exception_type(exc_type) 385 386 return conditional 387 388 def visitGlobal(self, global_): 389 390 """ 391 Return the 'global_' node unprocessed since namespaces should have 392 already been altered to take global names into consideration. 393 """ 394 395 return global_ 396 397 def visitImport(self, import_): 398 399 """ 400 Return the 'import_' node, importing the module with the stated name 401 and storing details on the node. 402 """ 403 404 module = self.importer.load(import_.name, self.builtins, getattr(import_, "alias", None)) 405 if module is not None: 406 self.namespace.set_types([module]) 407 else: 408 self.namespace.set_types([]) 409 self.annotate(import_) # mainly for viewing purposes 410 return import_ 411 412 def _visitInvoke(self, invoke, invocation_types, have_args): 413 414 """ 415 Return the processed 'invoke' node, using the given 'invocation_types' 416 as the list of callables to be investigated for instantiation or for the 417 invocation of functions or blocks. If 'have_args' is a true value, any 418 invocation or instantiation will involve arguments. 419 """ 420 421 # Now locate and invoke the subprogram. This can be complicated because 422 # the target may be a class or object, and there may be many different 423 # related subprograms. 424 425 invocations = [] 426 427 # Visit each callable in turn, finding subprograms. 428 429 for attr in invocation_types: 430 431 # Deal with class invocations by providing instance objects. 432 # Here, each class is queried for the __init__ method, which may 433 # exist for some combinations of classes in a hierarchy but not for 434 # others. 435 436 if isinstance(attr.type, Class): 437 attributes = get_attributes(attr.type, "__init__") 438 439 # Deal with object invocations by using __call__ methods. 440 441 elif isinstance(attr.type, Instance): 442 attributes = get_attributes(attr.type, "__call__") 443 444 # Normal functions or methods are more straightforward. 445 # Here, we model them using an attribute with no context and with 446 # no associated accessor. 447 448 else: 449 attributes = [(attr, None)] 450 451 # Inspect each attribute and extract the subprogram. 452 453 for attribute, accessor in attributes: 454 455 # If a class is involved, presume that it must create a new 456 # object. 457 458 if isinstance(attr.type, Class): 459 460 # Instantiate the class. 461 462 instance = self.new_instance(invoke, attr.type) 463 464 # For instantiations, switch the context. 465 466 if attribute is not None: 467 attribute = Attribute(instance, attribute.type) 468 469 # Skip cases where no callable is found. 470 471 if attribute is not None: 472 473 # If a subprogram is defined, invoke it. 474 475 self.invoke_subprogram(invoke, attribute) 476 if attribute.type not in invocations: 477 invocations.append(attribute.type) 478 479 elif not isinstance(attr.type, Class): 480 print "Invocation type is None for", accessor 481 482 else: 483 484 # Test to see if no arguments were supplied in cases where no 485 # initialiser was found. 486 487 if have_args: 488 raise AnnotationMessage, "No initialiser found for '%s' with arguments." % attr.type 489 490 # Special case: initialisation. 491 492 if isinstance(attr.type, Class): 493 494 # Associate the instance with the result of this invocation. 495 496 self.namespace.set_types([Attribute(None, instance)]) 497 self.annotate(invoke) 498 499 # Remember the invocations that were found, along with the return type 500 # information. 501 502 invoke.invocations = invocations 503 self.namespace.set_types(getattr(invoke, "types", [])) 504 combine(self.namespace.raises, getattr(invoke, "raises", [])) 505 return invoke 506 507 def visitInvokeBlock(self, invoke): 508 509 """ 510 Return the processed 'invoke' node, first finding the callables 511 indicated by the expression. 512 """ 513 514 invoke.expr = self.dispatch(invoke.expr) 515 invocation_types = self.namespace.types 516 return self._visitInvoke(invoke, invocation_types, have_args=0) 517 518 def visitInvokeFunction(self, invoke): 519 520 """ 521 Return the processed 'invoke' node, first finding the callables 522 indicated by the expression. 523 """ 524 525 invoke.expr = self.dispatch(invoke.expr) 526 invocation_types = self.namespace.types 527 528 # Invocation processing starts with making sure that the arguments have 529 # been processed. 530 531 return self._visitInvoke(invoke, invocation_types, have_args=self.process_args(invoke)) 532 533 def visitLoadAttr(self, loadattr): 534 535 """ 536 Return the 'loadattr' node, processing and storing the expression, and 537 using the expression's types to construct records of accesses and 538 non-accesses using the stated attribute name. 539 """ 540 541 loadattr.expr = self.dispatch(loadattr.expr) 542 types = [] 543 non_accesses = [] 544 accesses = {} 545 for attr in self.namespace.types: 546 attributes = get_attributes(attr.type, loadattr.name) 547 if not attributes: 548 if not attr in non_accesses: 549 non_accesses.append(attr) 550 combine(self.namespace.raises, self.get_builtin_instances(loadattr, "AttributeError")) 551 552 # Revoke this type from any name involved. 553 554 self._prune_non_accesses(loadattr.expr, attr) 555 556 for attribute, accessor in attributes: 557 if attribute is not None: 558 types.append(attribute) 559 if not accesses.has_key(attr.type): 560 accesses[attr.type] = [] 561 if not (attribute, accessor) in accesses[attr.type]: 562 accesses[attr.type].append((attribute, accessor)) 563 else: 564 if not attr in non_accesses: 565 non_accesses.append(attr) 566 combine(self.namespace.raises, self.get_builtin_instances(loadattr, "AttributeError")) 567 568 # Revoke this type from any name involved. 569 570 self._prune_non_accesses(loadattr.expr, attr) 571 572 if not types: 573 print "No attribute found for", loadattr.name, "given", self.namespace.types 574 self.namespace.set_types(types) 575 loadattr.non_accesses = non_accesses 576 loadattr.accesses = accesses 577 self.annotate(loadattr) 578 return loadattr 579 580 def _prune_non_accesses(self, expr, attr): 581 582 """ 583 Prune type information from 'expr' where the given 'attr' has been 584 shown to be a non-access. 585 """ 586 587 if isinstance(expr, LoadName): 588 self.namespace.revoke(expr.name, attr) 589 elif isinstance(expr, LoadExc): 590 self.namespace.revoke_exception_type(attr) 591 elif isinstance(expr, LoadTemp): 592 self.namespace.revoke_temp_type(getattr(expr, "index", None), attr) 593 594 # LoadAttr cannot be pruned since this might unintentionally prune 595 # legitimate types from other applications of the referenced type, it 596 # almost certainly doesn't take "concurrent" mutation into 597 # consideration (where in a running program, the pruned type is actually 598 # reintroduced, making the pruning invalid), and there is no easy way of 599 # preserving the meaning of a namespace without either creating lots of 600 # specialised instances, and even then... 601 602 #elif isinstance(expr, LoadAttr): 603 # for expr_attr in expr.expr.types: 604 # if hasattr(expr_attr.type, "namespace"): 605 # expr_attr.type.namespace.revoke(expr.name, attr) 606 607 def visitLoadExc(self, loadexc): 608 609 """ 610 Return the 'loadexc' node, discovering the possible exception types 611 raised. 612 """ 613 614 self.namespace.set_types(self.namespace.raises[:]) 615 self.annotate(loadexc) 616 return loadexc 617 618 def visitLoadName(self, loadname): 619 620 """ 621 Return the 'loadname' node, processing the name information on the node 622 to determine which types are involved with the name. 623 """ 624 625 self.namespace.set_types(self.namespace.load(loadname.name)) 626 result = loadname 627 self.annotate(result) 628 return result 629 630 def visitLoadRef(self, loadref): 631 632 """ 633 Return the 'loadref' node, obtaining type information about the 634 reference stated on the node. 635 """ 636 637 self.namespace.set_types([Attribute(None, loadref.ref)]) 638 self.annotate(loadref) 639 return loadref 640 641 def visitLoadTemp(self, loadtemp): 642 643 """ 644 Return the 'loadtemp' node, obtaining type information about the 645 temporary variable accessed, and removing variable information where the 646 'release' attribute has been set on the node. 647 """ 648 649 index = getattr(loadtemp, "index", None) 650 try: 651 if getattr(loadtemp, "release", 0): 652 self.namespace.set_types(self.namespace.temp[index].pop()) 653 else: 654 self.namespace.set_types(self.namespace.temp[index][-1]) 655 except KeyError: 656 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 657 self.annotate(loadtemp) 658 return loadtemp 659 660 def visitModule(self, module): 661 662 """ 663 Return the processed 'module' whose contents (merely a group of nodes) 664 are processed. 665 """ 666 667 module.code = self.dispatches(module.code) 668 return module 669 670 def visitNot(self, not_): 671 672 "Return the 'not_' node whose expression is processed." 673 674 not_.expr = self.dispatch(not_.expr) 675 return not_ 676 677 def visitPass(self, pass_): 678 679 "Return the unprocessed 'pass_' node." 680 681 return pass_ 682 683 def visitRaise(self, raise_): 684 685 """ 686 Return the 'raise_' node, processing any traceback information along 687 with the raised exception expression, converting the node into a kind of 688 invocation where the expression is found not to be an invocation itself. 689 This node affects the namespace, adding exception types to the list of 690 those raised in the namespace. 691 """ 692 693 if getattr(raise_, "traceback", None) is not None: 694 raise_.traceback = self.dispatch(raise_.traceback) 695 raise_.expr = self.dispatch(raise_.expr) 696 697 # Handle bare name exceptions by converting any classes to instances. 698 699 if not isinstance(raise_.expr, InvokeFunction): 700 raise_.pos_args = [] 701 raise_.kw_args = {} 702 raise_.star = None 703 raise_.dstar = None 704 types = [] 705 for attr in self.namespace.types: 706 if isinstance(attr.type, Class): 707 self._visitInvoke(raise_, [attr], have_args=0) 708 types += self.namespace.types 709 else: 710 types = self.namespace.types 711 712 combine(self.namespace.raises, types) 713 return raise_ 714 715 def visitReleaseTemp(self, releasetemp): 716 717 """ 718 Return the 'releasetemp' node, removing temporary variable information 719 from the current namespace. 720 """ 721 722 index = getattr(releasetemp, "index", None) 723 try: 724 self.namespace.temp[index].pop() 725 except KeyError: 726 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 727 except IndexError: 728 pass #raise AnnotationMessage, "Temporary store index '%s' is empty." % index 729 return releasetemp 730 731 def visitResetExc(self, resetexc): 732 self.namespace.raises = [] 733 return resetexc 734 735 def visitReturn(self, return_): 736 737 """ 738 Return the 'return_' node, processing any expression and obtaining type 739 information to be accumulated in the current namespace's list of return 740 types. A snapshot of the namespace is taken for the purposes of 741 reconciling or merging namespaces where subprograms actually share 742 locals with their callers. 743 """ 744 745 if hasattr(return_, "expr"): 746 return_.expr = self.dispatch(return_.expr) 747 combine(self.namespace.returns, self.namespace.types) 748 self.annotate(return_) 749 self.namespace.snapshot() 750 return return_ 751 752 visitReturnFromBlock = visitReturn 753 visitReturnFromFunction = visitReturn 754 755 def visitStoreAttr(self, storeattr): 756 757 """ 758 Return the 'storeattr' node, processing the expression and target, and 759 using the type information obtained to build records of legitimate 760 writes to the stated attribute, along with "impossible" non-writes to 761 the attribute. 762 """ 763 764 storeattr.expr = self.dispatch(storeattr.expr) 765 expr = self.namespace.types 766 storeattr.lvalue = self.dispatch(storeattr.lvalue) 767 writes = {} 768 non_writes = [] 769 for attr in self.namespace.types: 770 # NOTE: Impose "atomic" constraints on certain types. 771 if attr is None: 772 if not attr in non_writes: 773 non_writes.append(attr) 774 continue 775 attr.type.namespace.add(storeattr.name, expr) 776 writes[attr.type] = attr.type.namespace.load(storeattr.name) 777 if not writes: 778 print "Unable to store attribute", storeattr.name, "given", self.namespace.types 779 storeattr.writes = writes 780 storeattr.non_writes = non_writes 781 return storeattr 782 783 def visitStoreName(self, storename): 784 785 """ 786 Return the 'storename' node, processing the expression on the node and 787 associating the type information obtained with the stated name in the 788 current namespace. 789 """ 790 791 storename.expr = self.dispatch(storename.expr) 792 self.namespace.store(storename.name, self.namespace.types) 793 self.annotate(storename) 794 return storename 795 796 def visitStoreTemp(self, storetemp): 797 798 """ 799 Return the 'storetemp' node, processing the expression on the node and 800 associating the type information obtained with a temporary variable in 801 the current namespace. 802 """ 803 804 storetemp.expr = self.dispatch(storetemp.expr) 805 index = getattr(storetemp, "index", None) 806 if not self.namespace.temp.has_key(index): 807 self.namespace.temp[index] = [] 808 self.namespace.temp[index].append(self.namespace.types) 809 return storetemp 810 811 def visitSubprogram(self, subprogram): 812 813 """ 814 Return the 'subprogram' node, processing its contents (a group of nodes 815 comprising the subprogram). 816 """ 817 818 subprogram.code = self.dispatches(subprogram.code) 819 return subprogram 820 821 def visitTry(self, try_): 822 823 """ 824 Return the 'try_' node, processing the body clause in its own namespace 825 derived from the current namespace, processing any handler clause using 826 the namespace information accumulated in the body, and processing any 827 else and finally clauses, attempting to supply each with appropriate 828 namespace information. 829 """ 830 831 is_module = self.namespace is self.module.namespace 832 833 try_.body = self.dispatches(try_.body) 834 835 # Save the namespace from the body. 836 837 body_namespace = Namespace() 838 body_namespace.merge_namespace(self.namespace) 839 840 # Process the handler. 841 842 if hasattr(try_, "handler"): 843 try_.handler = self.dispatches(try_.handler) 844 845 # Save the namespace from the handler. 846 847 handler_namespace = Namespace() 848 handler_namespace.merge_namespace(self.namespace) 849 850 # Remember the raised exceptions encountered so far. 851 852 raises = self.namespace.raises 853 854 # Process the else clause. 855 856 if hasattr(try_, "else_"): 857 858 # Restore the body namespace for the else clause. 859 860 self.namespace = body_namespace 861 if is_module: 862 self.module.namespace = self.namespace 863 864 # Empty the raised exceptions for the else clause. 865 866 self.namespace.raises = [] 867 try_.else_ = self.dispatches(try_.else_) 868 self.namespace.raises = raises 869 870 # Merge the namespaces. 871 872 self.namespace = Namespace() 873 if is_module: 874 self.module.namespace = self.namespace 875 self.namespace.merge_namespace(body_namespace) 876 self.namespace.merge_namespace(handler_namespace) 877 878 # Process the finally clause, if any. 879 880 try_.finally_ = self.dispatches(try_.finally_) 881 return try_ 882 883 # Utility methods. 884 885 def get_builtin_instances(self, node, name): 886 return [Attribute(None, self.new_instance(node, attr.type)) for attr in self.builtins.namespace[name]] 887 888 def new_instance(self, node, type): 889 890 "For the given 'node', obtain an instance from the given 'type'." 891 892 if not type.has_instance(node): 893 instance = Instance() 894 instance.namespace = Namespace() 895 instance.namespace.store("__class__", [Attribute(None, type)]) 896 type.add_instance(node, instance) 897 else: 898 instance = type.get_instance(node) 899 900 return instance 901 902 def invoke_subprogram(self, invoke, attribute): 903 904 """ 905 Invoke using the given 'invoke' node the subprogram represented by the 906 given 'attribute'. 907 """ 908 909 # Test for context information, making it into a real attribute. 910 911 if attribute.context is not None: 912 context = Attribute(None, attribute.context) 913 target = attribute.type 914 else: 915 context = None 916 target = attribute.type 917 918 # Test to see if anything has changed. 919 920 if hasattr(invoke, "syscount") and invoke.syscount.has_key(target) and invoke.syscount[target] == self.system.count: 921 return 922 923 # Remember the state of the system. 924 925 else: 926 if not hasattr(invoke, "syscount"): 927 invoke.syscount = {} 928 invoke.syscount[target] = self.system.count 929 930 # Provide the correct namespace for the invocation. 931 # This may be a "shared" namespace... 932 933 if getattr(invoke, "share_locals", 0): 934 namespace = Namespace() 935 namespace.merge_namespace(self.namespace, everything=0) 936 using_module_namespace = self.namespace is self.module.namespace 937 938 # Or it may be a structure... 939 940 elif getattr(target, "structure", None): 941 namespace = Namespace() 942 using_module_namespace = 0 943 944 # Or it may be a new namespace populated with the supplied parameters. 945 946 else: 947 items = self.make_items(invoke, target, context) 948 namespace = Namespace() 949 namespace.merge_items(items) 950 using_module_namespace = 0 951 952 # NOTE: Avoid PEP 227 (nested scopes) whilst permitting references to a 953 # NOTE: subprogram within itself. Do not define the name of the function 954 # NOTE: within a method definition. 955 956 if getattr(target, "name", None) is not None and not getattr(target, "is_method", 0): 957 namespace.store(target.name, [Attribute(None, target)]) 958 959 # Process the subprogram. 960 # In order to keep global accesses working, the module namespace must be 961 # adjusted. 962 963 if using_module_namespace: 964 self.module.namespace = namespace 965 966 self.process_node(target, namespace) 967 968 # NOTE: Improve and verify this. 969 # If the invocation returns a value, acquire the return types. 970 971 if getattr(target, "returns_value", 0): 972 self.namespace.set_types(self.last_returns) 973 self.annotate(invoke) 974 975 # If it is a normal block, merge the locals. 976 # This can happen in addition to the above because for things like 977 # logical expressions, the namespace can be modified whilst values are 978 # returned as results. 979 980 if getattr(invoke, "share_locals", 0): 981 self.namespace.reset() 982 983 # Merge the locals snapshots. 984 985 for locals in self.returned_locals: 986 987 # For blocks returning values (such as operations), do not merge 988 # snapshots or results. 989 990 if getattr(target, "returns_value", 0): 991 self.namespace.merge_namespace(locals, everything=0) 992 993 # For blocks not returning values (such as loops), merge 994 # snapshots and results since they contain details of genuine 995 # returns. 996 997 else: 998 self.namespace.merge_namespace(locals) 999 1000 # Incorporate any raised exceptions. 1001 1002 if not hasattr(invoke, "raises"): 1003 invoke.raises = [] 1004 combine(invoke.raises, self.last_raises) 1005 1006 # In order to keep global accesses working, the module namespace must be 1007 # adjusted. 1008 1009 if using_module_namespace: 1010 self.module.namespace = self.namespace 1011 1012 def process_args(self, invocation): 1013 1014 """ 1015 Process the arguments associated with an 'invocation'. Return whether 1016 any arguments were processed. 1017 """ 1018 1019 invocation.pos_args = self.dispatches(invocation.pos_args) 1020 invocation.kw_args = self.dispatch_dict(invocation.kw_args) 1021 1022 # Get type information for star and dstar arguments. 1023 1024 if invocation.star is not None: 1025 param, default = invocation.star 1026 default = self.dispatch(default) 1027 invocation.star = param, default 1028 1029 if invocation.dstar is not None: 1030 param, default = invocation.dstar 1031 default = self.dispatch(default) 1032 invocation.dstar = param, default 1033 1034 if invocation.pos_args or invocation.kw_args or invocation.star or invocation.dstar: 1035 return 1 1036 else: 1037 return 0 1038 1039 def make_items(self, invocation, subprogram, context): 1040 1041 """ 1042 Make an items mapping for the 'invocation' of the 'subprogram' using the 1043 given 'context' (which may be None). 1044 """ 1045 1046 if context is not None: 1047 pos_args = [Self(context)] + invocation.pos_args 1048 else: 1049 pos_args = invocation.pos_args 1050 1051 # Duplicate the keyword arguments - we remove them in processing below. 1052 1053 kw_args = {} 1054 kw_args.update(invocation.kw_args) 1055 1056 # Sort the arguments into positional and keyword arguments. 1057 1058 params = subprogram.params 1059 items = [] 1060 star_args = [] 1061 1062 # Match each positional argument, taking excess arguments as star args. 1063 1064 for arg in pos_args: 1065 if params: 1066 param, default = params[0] 1067 if arg is None: 1068 arg = default 1069 if hasattr(arg, "types"): 1070 items.append((param, arg.types)) 1071 else: 1072 items.append((param, [])) # Annotation has not succeeded. 1073 params = params[1:] 1074 else: 1075 star_args.append(arg) 1076 1077 # Collect the remaining defaults. 1078 1079 while params: 1080 param, default = params[0] 1081 if kw_args.has_key(param): 1082 arg = kw_args[param] 1083 del kw_args[param] 1084 elif default is not None: 1085 arg = self.dispatch(default) 1086 else: 1087 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) 1088 if hasattr(arg, "types"): 1089 items.append((param, arg.types)) 1090 else: 1091 items.append((param, [])) # Annotation has not succeeded. 1092 params = params[1:] 1093 1094 dstar_args = kw_args.items() 1095 1096 # Construct temporary objects. 1097 1098 if star_args: 1099 star_invocation = self.make_star_args(invocation, subprogram, star_args) 1100 self.dispatch(star_invocation) 1101 star_types = star_invocation.types 1102 else: 1103 star_types = None 1104 1105 if dstar_args: 1106 dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args) 1107 self.dispatch(dstar_invocation) 1108 dstar_types = dstar_invocation.types 1109 else: 1110 dstar_types = None 1111 1112 # NOTE: Merge the objects properly. 1113 1114 star_types = star_types or invocation.star and invocation.star.types 1115 dstar_types = dstar_types or invocation.dstar and invocation.dstar.types 1116 1117 # Add star and dstar. 1118 1119 if star_types is not None: 1120 if subprogram.star is not None: 1121 param, default = subprogram.star 1122 items.append((param, star_types)) 1123 else: 1124 raise AnnotationMessage, "Invocation provides unwanted *args." 1125 elif subprogram.star is not None: 1126 param, default = subprogram.star 1127 if not hasattr(default, "types"): 1128 subprogram.star = param, self.dispatch(default) # NOTE: Review reprocessing. 1129 items.append((param, default.types)) 1130 1131 if dstar_types is not None: 1132 if subprogram.dstar is not None: 1133 param, default = subprogram.dstar 1134 items.append((param, dstar_types)) 1135 else: 1136 raise AnnotationMessage, "Invocation provides unwanted **args." 1137 elif subprogram.dstar is not None: 1138 param, default = subprogram.dstar 1139 if not hasattr(default, "types"): 1140 subprogram.dstar = param, self.dispatch(default) # NOTE: Review reprocessing. 1141 items.append((param, default.types)) 1142 1143 # Record the parameter types. 1144 1145 self.annotate_parameters(subprogram, items) 1146 return subprogram.paramtypes.items() 1147 1148 def make_star_args(self, invocation, subprogram, star_args): 1149 1150 "Make a subprogram which initialises a list containing 'star_args'." 1151 1152 if not hasattr(invocation, "stars"): 1153 invocation.stars = {} 1154 1155 if not invocation.stars.has_key(subprogram.full_name()): 1156 code=[ 1157 StoreTemp( 1158 expr=InvokeFunction( 1159 invocation.original, 1160 expr=LoadAttr( 1161 expr=LoadRef( 1162 ref=self.builtins 1163 ), 1164 name="list", 1165 nstype="module", 1166 ), 1167 args=[], 1168 star=None, 1169 dstar=None 1170 ) 1171 ) 1172 ] 1173 1174 for arg in star_args: 1175 code.append( 1176 InvokeFunction( 1177 invocation.original, 1178 expr=LoadAttr( 1179 expr=LoadTemp(), 1180 name="append" 1181 ), 1182 args=[arg], 1183 star=None, 1184 dstar=None 1185 ) 1186 ) 1187 1188 code += [ 1189 Return(expr=LoadTemp(release=1)) 1190 ] 1191 1192 invocation.stars[subprogram.full_name()] = InvokeBlock( 1193 invocation.original, 1194 produces_result=1, 1195 expr=LoadRef( 1196 ref=Subprogram( 1197 name=None, 1198 returns_value=1, 1199 params=[], 1200 star=None, 1201 dstar=None, 1202 code=code 1203 ) 1204 ) 1205 ) 1206 1207 return invocation.stars[subprogram.full_name()] 1208 1209 def make_dstar_args(self, invocation, subprogram, dstar_args): 1210 1211 """ 1212 Make a subprogram which initialises a dictionary built from the given 1213 'dstar_args'. 1214 """ 1215 1216 if not hasattr(invocation, "dstars"): 1217 invocation.dstars = {} 1218 1219 if not invocation.dstars.has_key(subprogram.full_name()): 1220 code=[ 1221 StoreTemp( 1222 expr=InvokeFunction( 1223 invocation.original, 1224 expr=LoadAttr( 1225 expr=LoadRef( 1226 ref=self.builtins 1227 ), 1228 name="dict", 1229 nstype="module", 1230 ) 1231 ) 1232 ) 1233 ] 1234 1235 for arg, value in dstar_args: 1236 1237 # NOTE: Constant not added to table. 1238 1239 constant = Constant(name=repr(arg), value=arg, namespace=Namespace()) 1240 #constant.namespace.store("__class__", self.get_builtin_instances(invocation, constant.typename)) 1241 code += [ 1242 StoreTemp( 1243 expr=LoadRef( 1244 ref=constant 1245 ), 1246 index="const" 1247 ), 1248 StoreAttr( 1249 lvalue=LoadTemp( 1250 index="const" 1251 ), 1252 name="__class__", 1253 expr=LoadAttr( 1254 expr=LoadRef( 1255 ref=self.builtins 1256 ), 1257 name=constant.typename, 1258 nstype="module", 1259 ) 1260 ), 1261 InvokeFunction( 1262 invocation.original, 1263 expr=LoadAttr( 1264 expr=LoadTemp(), 1265 name="__setitem__" 1266 ), 1267 args=[ 1268 LoadTemp( 1269 index="const", 1270 release=1 1271 ), 1272 value 1273 ] 1274 ) 1275 ] 1276 1277 code += [ 1278 Return(expr=LoadTemp(release=1)) 1279 ] 1280 1281 invocation.dstars[subprogram.full_name()] = InvokeBlock( 1282 invocation.original, 1283 produces_result=1, 1284 expr=LoadRef( 1285 ref=Subprogram( 1286 name=None, 1287 returns_value=1, 1288 params=[], 1289 star=None, 1290 dstar=None, 1291 code=code 1292 ) 1293 ) 1294 ) 1295 1296 return invocation.dstars[subprogram.full_name()] 1297 1298 # Namespace-related abstractions. 1299 1300 class Namespace: 1301 1302 """ 1303 A local namespace which may either relate to a genuine set of function 1304 locals or the initialisation of a structure or module. 1305 """ 1306 1307 def __init__(self): 1308 1309 """ 1310 Initialise the namespace with a mapping of local names to possible 1311 types, a list of return values and of possible returned local 1312 namespaces. The namespace also tracks the "current" types and a mapping 1313 of temporary value names to types. 1314 """ 1315 1316 self.names = {} 1317 self.returns = [] 1318 self.return_locals = [] 1319 self.raises = [] 1320 self.temp = {} 1321 self.types = [] 1322 1323 def set_types(self, types): 1324 1325 "Set the current collection of 'types'." 1326 1327 self.types = types 1328 1329 def add(self, name, types): 1330 1331 "Add to the entry with the given 'name' the specified 'types'." 1332 1333 if self.names.has_key(name): 1334 combine(self.names[name], types) 1335 else: 1336 self.store(name, types) 1337 1338 def store(self, name, types): 1339 1340 "Store in (or associate with) the given 'name' the specified 'types'." 1341 1342 self.names[name] = types 1343 1344 __setitem__ = store 1345 1346 def load(self, name): 1347 1348 "Load the types associated with the given 'name'." 1349 1350 return self.names[name] 1351 1352 __getitem__ = load 1353 1354 def revoke(self, name, type): 1355 1356 "Revoke from the entry for the given 'name' the specified 'type'." 1357 1358 new_types = self.names[name][:] 1359 new_types.remove(type) 1360 self.names[name] = new_types 1361 1362 def revoke_exception_type(self, type): 1363 1364 "Revoke the given 'type' from the collection of exception types." 1365 1366 self.raises.remove(type) 1367 1368 def revoke_temp_type(self, index, type): 1369 1370 "Revoke from the temporary variable 'index' the given 'type'." 1371 1372 new_types = self.temp[index][-1][:] 1373 new_types.remove(type) 1374 self.temp[index][-1] = new_types 1375 1376 def merge_namespace(self, namespace, everything=1): 1377 1378 """ 1379 Merge items from the given 'namespace' with this namespace. When the 1380 optional 'everything' parameter is set to a false value (unlike the 1381 default), return values and locals snapshots will not be copied to this 1382 namespace. 1383 """ 1384 1385 self.merge_items(namespace.names.items()) 1386 if everything: 1387 combine(self.returns, namespace.returns) 1388 combine(self.return_locals, namespace.return_locals) 1389 combine(self.raises, namespace.raises) 1390 for name, values in namespace.temp.items(): 1391 if values: 1392 if not self.temp.has_key(name) or not self.temp[name]: 1393 self.temp[name] = [[]] 1394 combine(self.temp[name][-1], values[-1]) 1395 1396 def merge_items(self, items): 1397 1398 "Merge the given 'items' with this namespace." 1399 1400 for name, types in items: 1401 self.merge(name, types) 1402 1403 def merge(self, name, types): 1404 1405 "Merge the entry for the given 'name' and 'types' with this namespace." 1406 1407 if not self.names.has_key(name): 1408 self.names[name] = types[:] 1409 else: 1410 existing = self.names[name] 1411 combine(existing, types) 1412 1413 def snapshot(self): 1414 1415 "Make a snapshot of the locals and remember them." 1416 1417 namespace = Namespace() 1418 namespace.merge_namespace(self) 1419 self.return_locals.append(namespace) 1420 1421 def reset(self): 1422 1423 "Reset a namespace in preparation for merging with returned locals." 1424 1425 self.names = {} 1426 1427 def __repr__(self): 1428 return repr(self.names) 1429 1430 class Importer: 1431 1432 "An import machine, searching for and loading modules." 1433 1434 def __init__(self, path=None): 1435 1436 """ 1437 Initialise the importer with the given search 'path' - a list of 1438 directories to search for Python modules. 1439 """ 1440 1441 self.path = path or [os.getcwd()] 1442 self.modules = {} 1443 1444 def find_in_path(self, name): 1445 1446 """ 1447 Find the given module 'name' in the search path, returning None where no 1448 such module could be found, or a 2-tuple from the 'find' method 1449 otherwise. 1450 """ 1451 1452 for d in self.path: 1453 m = self.find(d, name) 1454 if m: return m 1455 return None 1456 1457 def find(self, d, name): 1458 1459 """ 1460 In the directory 'd', find the given module 'name', where 'name' can 1461 either refer to a single file module or to a package. Return None if the 1462 'name' cannot be associated with either a file or a package directory, 1463 or a 2-tuple from '_find_package' or '_find_module' otherwise. 1464 """ 1465 1466 m = self._find_package(d, name) 1467 if m: return m 1468 m = self._find_module(d, name) 1469 if m: return m 1470 return None 1471 1472 def _find_module(self, d, name): 1473 1474 """ 1475 In the directory 'd', find the given module 'name', returning None where 1476 no suitable file exists in the directory, or a 2-tuple consisting of 1477 None (indicating that no package directory is involved) and a filename 1478 indicating the location of the module. 1479 """ 1480 1481 name_py = name + os.extsep + "py" 1482 filename = self._find_file(d, name_py) 1483 if filename: 1484 return None, filename 1485 return None 1486 1487 def _find_package(self, d, name): 1488 1489 """ 1490 In the directory 'd', find the given package 'name', returning None 1491 where no suitable package directory exists, or a 2-tuple consisting of 1492 a directory (indicating the location of the package directory itself) 1493 and a filename indicating the location of the __init__.py module which 1494 declares the package's top-level contents. 1495 """ 1496 1497 filename = self._find_file(d, name) 1498 if filename: 1499 init_py = "__init__" + os.path.extsep + "py" 1500 init_py_filename = self._find_file(filename, init_py) 1501 if init_py_filename: 1502 return filename, init_py_filename 1503 return None 1504 1505 def _find_file(self, d, filename): 1506 1507 """ 1508 Return the filename obtained when searching the directory 'd' for the 1509 given 'filename', or None if no actual file exists for the filename. 1510 """ 1511 1512 filename = os.path.join(d, filename) 1513 if os.path.exists(filename): 1514 return filename 1515 else: 1516 return None 1517 1518 def load(self, name, builtins, alias=None): 1519 1520 """ 1521 Load the module or package with the given 'name' and using the specified 1522 'builtins'. Return an Attribute object referencing the loaded module or 1523 package, or None if no such module or package exists. 1524 """ 1525 1526 path = name.split(".") 1527 m = self.find_in_path(path[0]) 1528 if not m: 1529 return None # NOTE: Import error. 1530 d, filename = m 1531 top = module = self.modules.get(path[0], load(filename, builtins, path[0], self)) 1532 self.modules[path[0]] = module 1533 1534 if len(path) > 1: 1535 path_so_far = path[:1] 1536 for p in path[1:]: 1537 path_so_far.append(p) 1538 m = self.find(d, p) 1539 if not m: 1540 return None # NOTE: Import error. 1541 d, filename = m 1542 module_name = ".".join(path_so_far) 1543 submodule = self.modules.get(module_name, load(filename, builtins, module_name, self)) 1544 self.modules[module_name] = submodule 1545 1546 # Store the submodule within its parent module. 1547 1548 module.namespace[p] = [Attribute(None, submodule)] 1549 module = submodule 1550 1551 if alias: 1552 return Attribute(None, module) 1553 else: 1554 return Attribute(None, top) 1555 1556 def combine(target, additions): 1557 1558 """ 1559 Merge into the 'target' sequence the given 'additions', preventing duplicate 1560 items. 1561 """ 1562 1563 for addition in additions: 1564 if addition not in target: 1565 target.append(addition) 1566 1567 def find_attributes(structure, name): 1568 1569 """ 1570 Find for the given 'structure' all attributes for the given 'name', visiting 1571 base classes where appropriate and returning the attributes in order of 1572 descending precedence for all possible base classes. 1573 1574 The elements in the result list are 2-tuples which contain the attribute and 1575 the structure involved in accessing the attribute. 1576 """ 1577 1578 # First attempt to search the instance/class namespace. 1579 1580 try: 1581 l = structure.namespace.load(name) 1582 attributes = [] 1583 for attribute in l: 1584 attributes.append((attribute, structure)) 1585 1586 # If that does not work, attempt to investigate any class or base classes. 1587 1588 except KeyError: 1589 attributes = [] 1590 1591 # Investigate any instance's implementing class. 1592 1593 if isinstance(structure, Instance): 1594 for attr in structure.namespace.load("__class__"): 1595 cls = attr.type 1596 l = get_attributes(cls, name) 1597 combine(attributes, l) 1598 1599 # Investigate any class's base classes. 1600 1601 elif isinstance(structure, Class): 1602 1603 # If no base classes exist, return an indicator that no attribute 1604 # exists. 1605 1606 if not structure.base_refs: 1607 return [(None, structure)] 1608 1609 # Otherwise, find all possible base classes. 1610 1611 for base_refs in structure.base_refs: 1612 base_attributes = [] 1613 1614 # For each base class, find attributes either in the base 1615 # class or its own base classes. 1616 1617 for base_ref in base_refs: 1618 l = get_attributes(base_ref, name) 1619 combine(base_attributes, l) 1620 1621 combine(attributes, base_attributes) 1622 1623 return attributes 1624 1625 def get_attributes(structure, name): 1626 1627 """ 1628 Return all possible attributes for the given 'structure' having the given 1629 'name', wrapping each attribute in an Attribute object which includes 1630 context information for the attribute access. 1631 1632 The elements in the result list are 2-tuples which contain the attribute and 1633 the structure involved in accessing the attribute. 1634 """ 1635 1636 if isinstance(structure, Attribute): 1637 structure = structure.type 1638 results = [] 1639 for attribute, accessor in find_attributes(structure, name): 1640 1641 # Detect class attribute access via instances. 1642 1643 if attribute is not None and isinstance(structure, Instance) and isinstance(accessor, Class): 1644 attribute = accessor.get_attribute_for_instance(attribute, structure) 1645 1646 # Produce an attribute with the appropriate context. 1647 1648 if attribute is not None and isinstance(structure, Structure): 1649 results.append((Attribute(structure, attribute.type), accessor)) 1650 else: 1651 results.append((attribute, accessor)) 1652 1653 return results 1654 1655 # Convenience functions. 1656 1657 def load(name, builtins=None, module_name=None, importer=None): 1658 1659 """ 1660 Load the module with the given 'name' (which may be a full module path), 1661 using the optional 'builtins' to resolve built-in names, and using the 1662 optional 'importer' to provide a means of finding and loading modules. 1663 """ 1664 1665 module = simplify.simplify(name, builtins is None, module_name) 1666 fixnames.fix(module, builtins) 1667 annotate(module, builtins, importer) 1668 return module 1669 1670 def annotate(module, builtins=None, importer=None): 1671 1672 """ 1673 Annotate the given 'module', also employing the optional 'builtins' module, 1674 if specified. If the optional 'importer' is given, use that to find and load 1675 modules. 1676 """ 1677 1678 annotator = Annotator(importer) 1679 if builtins is not None: 1680 annotator.process(module, builtins) 1681 else: 1682 annotator.process(module) 1683 1684 # vim: tabstop=4 expandtab shiftwidth=4