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