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