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