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