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