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