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