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 annotate function: 28 29 annotate(module, builtins) 30 31 The more complicated approach involves obtaining an Annotator: 32 33 annotator = Annotator() 34 35 Then, processing an existing module with it: 36 37 annotator.process(module) 38 39 If a module containing built-in classes and functions has already been 40 annotated, such a module should be passed in as an additional argument: 41 42 annotator.process(module, builtins) 43 """ 44 45 from simplified import * 46 import compiler 47 48 class System: 49 50 """ 51 A class maintaining the state of the annotation system. When the system 52 counter can no longer be incremented by any annotation operation, the 53 system may be considered stable and fully annotated. 54 """ 55 56 def __init__(self): 57 self.count = 0 58 59 def init(self, node): 60 61 "Initialise a 'node' for annotation." 62 63 if not hasattr(node, "types"): 64 node.types = [] 65 66 def annotate(self, node, types): 67 68 "Annotate the given 'node' with the given 'types'." 69 70 self.init(node) 71 self.combine(node.types, types) 72 73 def combine(self, target, types): 74 75 """ 76 Combine the 'target' list with the given 'types', counting new members. 77 """ 78 79 for type in types: 80 if type not in target: 81 target.append(type) 82 self.count += 1 83 84 system = System() 85 86 # Exceptions. 87 88 class AnnotationError(SimplifiedError): 89 90 "An error in the annotation process." 91 92 pass 93 94 class AnnotationMessage(Exception): 95 96 "A lesser annotation error." 97 98 pass 99 100 # Annotation. 101 102 class Annotator(Visitor): 103 104 """ 105 The type annotator which traverses the program nodes, typically depth-first, 106 and maintains a record of the current set of types applying to the currently 107 considered operation. Such types are also recorded on the nodes, and a 108 special "system" record is maintained to monitor the level of annotation 109 activity with a view to recognising when no more annotations are possible. 110 111 Throughout the annotation activity, type information consists of lists of 112 Attribute objects where such objects retain information about the context of 113 the type (since a value in the program may be associated with an object or 114 class) and the actual type of the value being manipulated. Upon accessing 115 attribute information on namespaces, additional accessor information is also 116 exchanged - this provides a means of distinguishing between the different 117 types possible when the means of constructing the namespace may depend on 118 run-time behaviour. 119 120 Covered: Assign, CheckExc, Conditional, InvokeBlock, InvokeFunction, 121 LoadAttr, LoadExc, LoadName, LoadRef, LoadTemp, Module, Not, Pass, 122 Raise, ReleaseTemp, ReturnFromBlock, ReturnFromFunction, StoreAttr, 123 StoreName, StoreTemp, Subprogram, Try. 124 125 Missing: Keyword, Global, Import. 126 """ 127 128 def __init__(self): 129 130 "Initialise the visitor." 131 132 Visitor.__init__(self) 133 self.system = system 134 135 # Satisfy visitor issues. 136 137 self.visitor = self 138 139 def process(self, module, builtins=None): 140 141 """ 142 Process the given 'module', using the optional 'builtins' to access 143 built-in classes and functions. 144 """ 145 146 self.subprograms = [] 147 self.current_subprograms = [] 148 self.current_namespaces = [] 149 self.namespace = None 150 self.module = module 151 152 # Give constants their own namespace. 153 154 for value, constant in module.simplifier.constants.items(): 155 constant.namespace = Namespace() 156 157 # Process the module, supplying builtins if possible. 158 159 self.builtins = builtins 160 self.global_namespace = Namespace() 161 162 if builtins is not None: 163 self.builtins_namespace = builtins.namespace 164 else: 165 self.builtins_namespace = self.global_namespace 166 167 return self.process_node(module, self.global_namespace) 168 169 def process_node(self, node, locals): 170 171 """ 172 Process a subprogram or module 'node', indicating the initial 'locals'. 173 Return an annotated subprogram or module. Note that this method may 174 mutate nodes in the original program. 175 """ 176 177 # Record the current subprogram and namespace. 178 179 self.current_subprograms.append(node) 180 181 # Determine the namespace. 182 183 self.current_namespaces.append(self.namespace) 184 self.namespace = locals 185 186 # Add namespace details to any structure involved. 187 188 if getattr(node, "structure", None) is not None: 189 node.structure.namespace = Namespace() 190 191 # Initialise bases where appropriate. 192 193 if hasattr(node.structure, "bases"): 194 base_refs = [] 195 for base in node.structure.bases: 196 self.dispatch(base) 197 base_refs.append(self.namespace.types) 198 node.structure.base_refs = base_refs 199 200 # Dispatch to the code itself. 201 202 node.namespace = self.namespace 203 result = self.dispatch(node) 204 result.namespace = self.namespace 205 206 # Obtain the return values. 207 208 self.last_returns = self.namespace.returns 209 self.last_raises = self.namespace.raises 210 self.returned_locals = self.namespace.return_locals 211 212 # Restore the previous subprogram and namespace. 213 214 self.namespace = self.current_namespaces.pop() 215 self.current_subprograms.pop() 216 217 return result 218 219 def annotate(self, node, types=None): 220 221 """ 222 Annotate the given 'node' in the system, using either the optional 223 'types' or the namespace's current type information. 224 """ 225 226 self.system.annotate(node, types or self.namespace.types) 227 228 def annotate_parameters(self, node, items): 229 230 """ 231 Annotate the given 'node' using the given 'items' and updating the 232 system's annotation counter. 233 """ 234 235 if not hasattr(node, "paramtypes"): 236 node.paramtypes = {} 237 238 for param, types in items: 239 if not node.paramtypes.has_key(param): 240 node.paramtypes[param] = [] 241 self.system.combine(node.paramtypes[param], types) 242 243 # Visitor methods. 244 245 def default(self, node): 246 247 """ 248 Process the given 'node', given that it does not have a specific 249 handler. 250 """ 251 252 raise AnnotationMessage, "Node '%s' not supported." % node 253 254 def dispatch(self, node, *args): 255 try: 256 return Visitor.dispatch(self, node, *args) 257 except AnnotationError, exc: 258 exc.add(node) 259 raise 260 except AnnotationMessage, exc: 261 raise AnnotationError(exc, node) 262 263 # Specific node methods. 264 265 def visitAssign(self, assign): 266 267 """ 268 Return the 'assign' node whose contents (merely a group of nodes) have 269 been processed. 270 """ 271 272 assign.code = self.dispatches(assign.code) 273 return assign 274 275 def visitCheckExc(self, checkexc): 276 277 """ 278 Return the 'checkexc' node, processing the expression to find the 279 possible types of the exception, and processing each choice to build a 280 list of checked types for the exception. 281 """ 282 283 checkexc.expr = self.dispatch(checkexc.expr) 284 expr_types = self.namespace.types 285 choice_types = [] 286 choices = [] 287 for choice in checkexc.choices: 288 choices.append(self.dispatch(choice)) 289 choice_types += self.namespace.types 290 for expr_type in expr_types: 291 if expr_type.type.get_class() not in choice_types: 292 self._prune_non_accesses(checkexc.expr, expr_type) 293 return checkexc 294 295 def visitConditional(self, conditional): 296 297 """ 298 Return the 'conditional' node, processing the test, body and else 299 clauses and recording their processed forms. The body and else clauses 300 are processed within their own namespaces, and the test is also 301 processed in its own namespace if 'isolate_test' is set on the 302 'conditional' node. 303 """ 304 305 # Conditionals keep local namespace changes isolated. 306 # With Return nodes inside the body/else sections, the changes are 307 # communicated to the caller. 308 309 is_module = self.namespace is self.module.namespace 310 311 # Where the test is closely associated with the body, save the namespace 312 # before entering the test. 313 314 if conditional.isolate_test: 315 saved_namespace = self.namespace 316 self.namespace = Namespace() 317 if is_module: 318 self.module.namespace = self.namespace 319 self.namespace.merge_namespace(saved_namespace) 320 321 conditional.test = self.dispatch(conditional.test) 322 323 # Where the test may affect the body and the else clause, save the 324 # namespace after processing the test. 325 326 if not conditional.isolate_test: 327 saved_namespace = self.namespace 328 self.namespace = Namespace() 329 if is_module: 330 self.module.namespace = self.namespace 331 self.namespace.merge_namespace(saved_namespace) 332 333 # Process the body clause. 334 335 conditional.body = self.dispatches(conditional.body) 336 body_namespace = self.namespace 337 338 # Use the saved namespace as a template for the else clause. 339 340 self.namespace = Namespace() 341 if is_module: 342 self.module.namespace = self.namespace 343 self.namespace.merge_namespace(saved_namespace) 344 345 # Process the else clause. 346 347 conditional.else_ = self.dispatches(conditional.else_) 348 else_namespace = self.namespace 349 350 # Merge the body and else namespaces. 351 352 self.namespace = Namespace() 353 if is_module: 354 self.module.namespace = self.namespace 355 self.namespace.merge_namespace(body_namespace) 356 self.namespace.merge_namespace(else_namespace) 357 358 return conditional 359 360 def _visitInvoke(self, invoke, invocation_types, have_args): 361 362 """ 363 Return the processed 'invoke' node, using the given 'invocation_types' 364 as the list of callables to be investigated for instantiation or for the 365 invocation of functions or blocks. If 'have_args' is a true value, any 366 invocation or instantiation will involve arguments. 367 """ 368 369 # Now locate and invoke the subprogram. This can be complicated because 370 # the target may be a class or object, and there may be many different 371 # related subprograms. 372 373 invocations = [] 374 375 # Visit each callable in turn, finding subprograms. 376 377 for attr in invocation_types: 378 379 # Deal with class invocations by providing instance objects. 380 # Here, each class is queried for the __init__ method, which may 381 # exist for some combinations of classes in a hierarchy but not for 382 # others. 383 384 if isinstance(attr.type, Class): 385 attributes = get_attributes(attr.type, "__init__") 386 387 # Deal with object invocations by using __call__ methods. 388 389 elif isinstance(attr.type, Instance): 390 attributes = get_attributes(attr.type, "__call__") 391 392 # Normal functions or methods are more straightforward. 393 # Here, we model them using an attribute with no context and with 394 # no associated accessor. 395 396 else: 397 attributes = [(attr, None)] 398 399 # Inspect each attribute and extract the subprogram. 400 401 for attribute, accessor in attributes: 402 403 # If a class is involved, presume that it must create a new 404 # object. 405 406 if isinstance(attr.type, Class): 407 408 # Instantiate the class. 409 # NOTE: Should probably only allocate a single instance. 410 411 instance = self.new_instance(invoke, "new", attr.type.full_name(), attr.type) 412 413 # For instantiations, switch the context. 414 415 if attribute is not None: 416 attribute = Attribute(instance, attribute.type) 417 418 # Skip cases where no callable is found. 419 420 if attribute is not None: 421 422 # If a subprogram is defined, invoke it. 423 424 self.invoke_subprogram(invoke, attribute) 425 if attribute.type not in invocations: 426 invocations.append(attribute.type) 427 428 elif not isinstance(attr.type, Class): 429 print "Invocation type is None for", accessor 430 431 else: 432 433 # Test to see if no arguments were supplied in cases where no 434 # initialiser was found. 435 436 if have_args: 437 raise AnnotationMessage, "No initialiser found for '%s' with arguments." % attr.type 438 439 # Special case: initialisation. 440 441 if isinstance(attr.type, Class): 442 443 # Associate the instance with the result of this invocation. 444 445 self.namespace.set_types([Attribute(None, instance)]) 446 self.annotate(invoke) 447 448 # Remember the invocations that were found, along with the return type 449 # information. 450 451 invoke.invocations = invocations 452 self.namespace.set_types(getattr(invoke, "types", [])) 453 return invoke 454 455 def visitInvokeBlock(self, invoke): 456 457 """ 458 Return the processed 'invoke' node, first finding the callables 459 indicated by the expression. 460 """ 461 462 invoke.expr = self.dispatch(invoke.expr) 463 invocation_types = self.namespace.types 464 return self._visitInvoke(invoke, invocation_types, have_args=0) 465 466 def visitInvokeFunction(self, invoke): 467 468 """ 469 Return the processed 'invoke' node, first finding the callables 470 indicated by the expression. 471 """ 472 473 invoke.expr = self.dispatch(invoke.expr) 474 invocation_types = self.namespace.types 475 476 # Invocation processing starts with making sure that the arguments have 477 # been processed. 478 479 return self._visitInvoke(invoke, invocation_types, have_args=self.process_args(invoke)) 480 481 def visitLoadAttr(self, loadattr): 482 483 """ 484 Return the 'loadattr' node, processing and storing the expression, and 485 using the expression's types to construct records of accesses and 486 non-accesses using the stated attribute name. 487 """ 488 489 loadattr.expr = self.dispatch(loadattr.expr) 490 types = [] 491 non_accesses = [] 492 accesses = {} 493 for attr in self.namespace.types: 494 attributes = get_attributes(attr.type, loadattr.name) 495 if not attributes: 496 if not attr.type in non_accesses: 497 non_accesses.append(attr) 498 499 # Revoke this type from any name involved. 500 501 self._prune_non_accesses(loadattr.expr, attr) 502 503 for attribute, accessor in attributes: 504 if attribute is not None: 505 types.append(attribute) 506 if not accesses.has_key(attr.type): 507 accesses[attr.type] = [] 508 if not (attribute, accessor) in accesses[attr.type]: 509 accesses[attr.type].append((attribute, accessor)) 510 else: 511 if not attr in non_accesses: 512 non_accesses.append(attr) 513 514 # Revoke this type from any name involved. 515 516 self._prune_non_accesses(loadattr.expr, attr) 517 518 if not types: 519 print "No attribute found for", loadattr.name, "given", self.namespace.types 520 self.namespace.set_types(types) 521 loadattr.non_accesses = non_accesses 522 loadattr.accesses = accesses 523 self.annotate(loadattr) 524 return loadattr 525 526 def _prune_non_accesses(self, expr, attr): 527 528 """ 529 Prune type information from 'expr' where the given 'attr' has been 530 shown to be a non-access. 531 """ 532 533 if isinstance(expr, LoadName): 534 self.namespace.revoke(expr.name, attr) 535 elif isinstance(expr, LoadAttr): 536 for expr_attr in expr.expr.types: 537 if hasattr(expr_attr.type, "namespace"): 538 expr_attr.type.namespace.revoke(expr.name, attr) 539 elif isinstance(expr, LoadExc): 540 self.namespace.revoke_exception_type(attr) 541 542 def visitLoadExc(self, loadexc): 543 544 """ 545 Return the 'loadexc' node, discovering the possible exception types 546 raised. 547 """ 548 549 self.namespace.types = self.namespace.raises[:] 550 self.annotate(loadexc) 551 return loadexc 552 553 def visitLoadName(self, loadname): 554 555 """ 556 Return the 'loadname' node, processing the name information on the node 557 to determine which types are involved with the name. 558 """ 559 560 self.namespace.set_types(self.namespace.load(loadname.name)) 561 result = loadname 562 self.annotate(result) 563 return result 564 565 def visitLoadRef(self, loadref): 566 567 """ 568 Return the 'loadref' node, obtaining type information about the 569 reference stated on the node. 570 """ 571 572 self.namespace.set_types([Attribute(None, loadref.ref)]) 573 self.annotate(loadref) 574 return loadref 575 576 def visitLoadTemp(self, loadtemp): 577 578 """ 579 Return the 'loadtemp' node, obtaining type information about the 580 temporary variable accessed, and removing variable information where the 581 'release' attribute has been set on the node. 582 """ 583 584 index = getattr(loadtemp, "index", None) 585 try: 586 if getattr(loadtemp, "release", 0): 587 self.namespace.set_types(self.namespace.temp[index].pop()) 588 else: 589 self.namespace.set_types(self.namespace.temp[index][-1]) 590 except KeyError: 591 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 592 self.annotate(loadtemp) 593 return loadtemp 594 595 def visitModule(self, module): 596 597 """ 598 Return the processed 'module' whose contents (merely a group of nodes) 599 are processed. 600 """ 601 602 module.code = self.dispatches(module.code) 603 return module 604 605 def visitNot(self, not_): 606 607 "Return the 'not_' node whose expression is processed." 608 609 not_.expr = self.dispatch(not_.expr) 610 return not_ 611 612 def visitPass(self, pass_): 613 614 "Return the unprocessed 'pass_' node." 615 616 return pass_ 617 618 def visitRaise(self, raise_): 619 620 """ 621 Return the 'raise_' node, processing any traceback information along 622 with the raised exception expression, converting the node into a kind of 623 invocation where the expression is found not to be an invocation itself. 624 This node affects the namespace, adding exception types to the list of 625 those raised in the namespace. 626 """ 627 628 if getattr(raise_, "traceback", None) is not None: 629 raise_.traceback = self.dispatch(raise_.traceback) 630 raise_.expr = self.dispatch(raise_.expr) 631 632 # Handle bare name exceptions by converting any classes to instances. 633 634 if not isinstance(raise_.expr, InvokeFunction): 635 raise_.pos_args = [] 636 raise_.kw_args = {} 637 raise_.star = None 638 raise_.dstar = None 639 types = [] 640 for attr in self.namespace.types: 641 if isinstance(attr.type, Class): 642 self._visitInvoke(raise_, [attr], have_args=0) 643 types += self.namespace.types 644 else: 645 types = self.namespace.types 646 647 combine(self.namespace.raises, types) 648 return raise_ 649 650 def visitReleaseTemp(self, releasetemp): 651 652 """ 653 Return the 'releasetemp' node, removing temporary variable information 654 from the current namespace. 655 """ 656 657 index = getattr(releasetemp, "index", None) 658 try: 659 self.namespace.temp[index].pop() 660 except KeyError: 661 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 662 except IndexError: 663 pass #raise AnnotationMessage, "Temporary store index '%s' is empty." % index 664 return releasetemp 665 666 def visitReturn(self, return_): 667 668 """ 669 Return the 'return_' node, processing any expression and obtaining type 670 information to be accumulated in the current namespace's list of return 671 types. A snapshot of the namespace is taken for the purposes of 672 reconciling or merging namespaces where subprograms actually share 673 locals with their callers. 674 """ 675 676 if hasattr(return_, "expr"): 677 return_.expr = self.dispatch(return_.expr) 678 combine(self.namespace.returns, self.namespace.types) 679 self.annotate(return_) 680 self.namespace.snapshot() 681 return return_ 682 683 visitReturnFromBlock = visitReturn 684 visitReturnFromFunction = visitReturn 685 686 def visitStoreAttr(self, storeattr): 687 688 """ 689 Return the 'storeattr' node, processing the expression and target, and 690 using the type information obtained to build records of legitimate 691 writes to the stated attribute, along with "impossible" non-writes to 692 the attribute. 693 """ 694 695 storeattr.expr = self.dispatch(storeattr.expr) 696 expr = self.namespace.types 697 storeattr.lvalue = self.dispatch(storeattr.lvalue) 698 writes = {} 699 non_writes = [] 700 for attr in self.namespace.types: 701 if attr is None: 702 if not attr in non_writes: 703 non_writes.append(attr) 704 continue 705 attr.type.namespace.add(storeattr.name, expr) 706 writes[attr.type] = attr.type.namespace.load(storeattr.name) 707 if not writes: 708 print "Unable to store attribute", storeattr.name, "given", self.namespace.types 709 storeattr.writes = writes 710 storeattr.non_writes = non_writes 711 return storeattr 712 713 def visitStoreName(self, storename): 714 715 """ 716 Return the 'storename' node, processing the expression on the node and 717 associating the type information obtained with the stated name in the 718 current namespace. 719 """ 720 721 storename.expr = self.dispatch(storename.expr) 722 self.namespace.store(storename.name, self.namespace.types) 723 return storename 724 725 def visitStoreTemp(self, storetemp): 726 727 """ 728 Return the 'storetemp' node, processing the expression on the node and 729 associating the type information obtained with a temporary variable in 730 the current namespace. 731 """ 732 733 storetemp.expr = self.dispatch(storetemp.expr) 734 index = getattr(storetemp, "index", None) 735 if not self.namespace.temp.has_key(index): 736 self.namespace.temp[index] = [] 737 self.namespace.temp[index].append(self.namespace.types) 738 return storetemp 739 740 def visitSubprogram(self, subprogram): 741 742 """ 743 Return the 'subprogram' node, processing its contents (a group of nodes 744 comprising the subprogram). 745 """ 746 747 subprogram.code = self.dispatches(subprogram.code) 748 return subprogram 749 750 def visitTry(self, try_): 751 752 """ 753 Return the 'try_' node, processing the body clause in its own namespace 754 derived from the current namespace, processing any handler clause using 755 the namespace information accumulated in the body, and processing any 756 else and finally clauses, attempting to supply each with appropriate 757 namespace information. 758 """ 759 760 is_module = self.namespace is self.module.namespace 761 762 try_.body = self.dispatches(try_.body) 763 764 # Save the namespace from the body. 765 766 body_namespace = Namespace() 767 body_namespace.merge_namespace(self.namespace) 768 769 # Process the handler. 770 771 if hasattr(try_, "handler"): 772 try_.handler = self.dispatches(try_.handler) 773 774 # Save the namespace from the handler. 775 776 handler_namespace = Namespace() 777 handler_namespace.merge_namespace(self.namespace) 778 779 # Remember the raised exceptions encountered so far. 780 781 raises = self.namespace.raises 782 783 # Process the else clause. 784 785 if hasattr(try_, "else_"): 786 787 # Restore the body namespace for the else clause. 788 789 self.namespace = body_namespace 790 if is_module: 791 self.module.namespace = self.namespace 792 793 # Empty the raised exceptions for the else clause. 794 795 self.namespace.raises = [] 796 try_.else_ = self.dispatches(try_.else_) 797 self.namespace.raises = raises 798 799 # Merge the namespaces. 800 801 self.namespace = Namespace() 802 if is_module: 803 self.module.namespace = self.namespace 804 self.namespace.merge_namespace(body_namespace) 805 self.namespace.merge_namespace(handler_namespace) 806 807 # Process the finally clause, if any. 808 809 try_.finally_ = self.dispatches(try_.finally_) 810 return try_ 811 812 # Utility methods. 813 814 def new_instance(self, node, reason, target, type): 815 816 "Create, on the given 'node', a new instance with the given 'type'." 817 818 if not hasattr(node, "instances"): 819 node.instances = {} 820 821 if not node.instances.has_key((reason, target, type)): 822 823 # Insist on a single instance per type. 824 # NOTE: Strategy-dependent instantiation. 825 826 if len(type.instances) == 0: 827 instance = Instance() 828 instance.namespace = Namespace() 829 instance.namespace.store("__class__", [Attribute(None, type)]) 830 type.instances.append(instance) 831 else: 832 instance = type.instances[0] 833 834 node.instances[(reason, target, type)] = instance 835 836 return node.instances[(reason, target, type)] 837 838 def invoke_subprogram(self, invoke, attribute): 839 840 """ 841 Invoke using the given 'invoke' node the subprogram represented by the 842 given 'attribute'. 843 """ 844 845 # Test for context information, making it into a real attribute. 846 847 if attribute.context is not None: 848 context = Attribute(None, attribute.context) 849 target = attribute.type 850 else: 851 context = None 852 target = attribute.type 853 854 # Provide the correct namespace for the invocation. 855 856 if getattr(invoke, "share_locals", 0): 857 namespace = Namespace() 858 namespace.merge_namespace(self.namespace, everything=0) 859 using_module_namespace = self.namespace is self.module.namespace 860 elif getattr(target, "structure", None): 861 namespace = Namespace() 862 using_module_namespace = 0 863 else: 864 items = self.make_items(invoke, target, context) 865 namespace = Namespace() 866 namespace.merge_items(items) 867 using_module_namespace = 0 868 869 # Test to see if anything has changed. 870 871 if hasattr(invoke, "syscount") and invoke.syscount == self.system.count: 872 return 873 874 # Remember the state of the system. 875 876 else: 877 invoke.syscount = self.system.count 878 879 # Process the subprogram. 880 # In order to keep global accesses working, the module namespace must be 881 # adjusted. 882 883 if using_module_namespace: 884 self.module.namespace = namespace 885 886 self.process_node(target, namespace) 887 888 # NOTE: Improve and verify this. 889 # If the invocation returns a value, acquire the return types. 890 891 if getattr(target, "returns_value", 0): 892 self.namespace.set_types(self.last_returns) 893 self.annotate(invoke) 894 895 # If it is a normal block, merge the locals. 896 # This can happen in addition to the above because for things like 897 # logical expressions, the namespace can be modified whilst values are 898 # returned as results. 899 900 if getattr(invoke, "share_locals", 0): 901 self.namespace.reset() 902 903 # Merge the locals snapshots. 904 905 for locals in self.returned_locals: 906 907 # For blocks returning values (such as operations), do not merge 908 # snapshots or results. 909 910 if getattr(target, "returns_value", 0): 911 self.namespace.merge_namespace(locals, everything=0) 912 913 # For blocks not returning values (such as loops), merge 914 # snapshots and results since they contain details of genuine 915 # returns. 916 917 else: 918 self.namespace.merge_namespace(locals) 919 920 # Incorporate any raised exceptions. 921 922 combine(self.namespace.raises, self.last_raises) 923 924 # In order to keep global accesses working, the module namespace must be 925 # adjusted. 926 927 if using_module_namespace: 928 self.module.namespace = self.namespace 929 930 def process_args(self, invocation): 931 932 """ 933 Process the arguments associated with an 'invocation'. Return whether 934 any arguments were processed. 935 """ 936 937 invocation.pos_args = self.dispatches(invocation.pos_args) 938 invocation.kw_args = self.dispatch_dict(invocation.kw_args) 939 940 # Get type information for star and dstar arguments. 941 942 if invocation.star is not None: 943 param, default = invocation.star 944 default = self.dispatch(default) 945 invocation.star = param, default 946 947 if invocation.dstar is not None: 948 param, default = invocation.dstar 949 default = self.dispatch(default) 950 invocation.dstar = param, default 951 952 if invocation.pos_args or invocation.kw_args or invocation.star or invocation.dstar: 953 return 1 954 else: 955 return 0 956 957 def make_items(self, invocation, subprogram, context): 958 959 """ 960 Make an items mapping for the 'invocation' of the 'subprogram' using the 961 given 'context' (which may be None). 962 """ 963 964 if context is not None: 965 pos_args = [Self(context)] + invocation.pos_args 966 else: 967 pos_args = invocation.pos_args 968 kw_args = invocation.kw_args 969 970 # Sort the arguments into positional and keyword arguments. 971 972 params = subprogram.params 973 items = [] 974 star_args = [] 975 976 # Match each positional argument, taking excess arguments as star args. 977 978 for arg in pos_args: 979 if params: 980 param, default = params[0] 981 if arg is None: 982 arg = default 983 if hasattr(arg, "types"): 984 items.append((param, arg.types)) 985 else: 986 items.append((param, [])) # Annotation has not succeeded. 987 params = params[1:] 988 else: 989 star_args.append(arg) 990 991 # Collect the remaining defaults. 992 993 while params: 994 param, default = params[0] 995 if kw_args.has_key(param): 996 arg = kw_args[param] 997 del kw_args[param] 998 elif default is not None: 999 arg = self.dispatch(default) 1000 else: 1001 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) 1002 if hasattr(arg, "types"): 1003 items.append((param, arg.types)) 1004 else: 1005 items.append((param, [])) # Annotation has not succeeded. 1006 params = params[1:] 1007 1008 dstar_args = kw_args.values() 1009 1010 # Construct temporary objects. 1011 1012 if star_args: 1013 star_invocation = self.make_star_args(invocation, subprogram, star_args) 1014 self.dispatch(star_invocation) 1015 star_types = star_invocation.types 1016 else: 1017 star_types = None 1018 1019 if dstar_args: 1020 dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args) # NOTE: To be written! 1021 self.dispatch(dstar_invocation) 1022 dstar_types = dstar_invocation.types 1023 else: 1024 dstar_types = None 1025 1026 # NOTE: Merge the objects properly. 1027 1028 star_types = star_types or invocation.star and invocation.star.types 1029 dstar_types = dstar_types or invocation.dstar and invocation.dstar.types 1030 1031 # Add star and dstar. 1032 1033 if star_types is not None: 1034 if subprogram.star is not None: 1035 param, default = subprogram.star 1036 items.append((param, star_types)) 1037 else: 1038 raise AnnotationMessage, "Invocation provides unwanted *args." 1039 elif subprogram.star is not None: 1040 param, default = subprogram.star 1041 if not hasattr(arg, "types"): 1042 arg = self.dispatch(default) # NOTE: Review reprocessing. 1043 items.append((param, arg.types)) 1044 1045 if dstar_types is not None: 1046 if subprogram.dstar is not None: 1047 param, default = subprogram.dstar 1048 items.append((param, dstar_types)) 1049 else: 1050 raise AnnotationMessage, "Invocation provides unwanted **args." 1051 elif subprogram.dstar is not None: 1052 param, default = subprogram.dstar 1053 if not hasattr(arg, "types"): 1054 arg = self.dispatch(default) # NOTE: Review reprocessing. 1055 items.append((param, arg.types)) 1056 1057 # Record the parameter types. 1058 1059 self.annotate_parameters(subprogram, items) 1060 return subprogram.paramtypes.items() 1061 1062 def make_star_args(self, invocation, subprogram, star_args): 1063 1064 "Make a subprogram which initialises a list containing 'star_args'." 1065 1066 if not hasattr(invocation, "stars"): 1067 invocation.stars = {} 1068 1069 if not invocation.stars.has_key(subprogram.full_name()): 1070 code=[ 1071 StoreTemp( 1072 expr=InvokeFunction( 1073 expr=LoadAttr( 1074 expr=LoadRef( 1075 ref=self.builtins 1076 ), 1077 name="list", 1078 nstype="module", 1079 ), 1080 args=[], 1081 star=None, 1082 dstar=None 1083 ) 1084 ) 1085 ] 1086 1087 for arg in star_args: 1088 code.append( 1089 InvokeFunction( 1090 expr=LoadAttr( 1091 expr=LoadTemp(), 1092 name="append" 1093 ), 1094 args=[arg], 1095 star=None, 1096 dstar=None 1097 ) 1098 ) 1099 1100 code += [ 1101 Return(expr=LoadTemp(release=1)) 1102 ] 1103 1104 invocation.stars[subprogram.full_name()] = InvokeBlock( 1105 produces_result=1, 1106 expr=LoadRef( 1107 ref=Subprogram( 1108 name=None, 1109 returns_value=1, 1110 params=[], 1111 star=None, 1112 dstar=None, 1113 code=code 1114 ) 1115 ) 1116 ) 1117 1118 return invocation.stars[subprogram.full_name()] 1119 1120 # Namespace-related abstractions. 1121 1122 class Namespace: 1123 1124 """ 1125 A local namespace which may either relate to a genuine set of function 1126 locals or the initialisation of a structure or module. 1127 """ 1128 1129 def __init__(self): 1130 1131 """ 1132 Initialise the namespace with a mapping of local names to possible 1133 types, a list of return values and of possible returned local 1134 namespaces. The namespace also tracks the "current" types and a mapping 1135 of temporary value names to types. 1136 """ 1137 1138 self.names = {} 1139 self.returns = [] 1140 self.return_locals = [] 1141 self.raises = [] 1142 self.temp = {} 1143 self.types = [] 1144 1145 def set_types(self, types): 1146 self.types = types 1147 1148 def add(self, name, types): 1149 if self.names.has_key(name): 1150 combine(self.names[name], types) 1151 else: 1152 self.store(name, types) 1153 1154 def store(self, name, types): 1155 self.names[name] = types 1156 1157 __setitem__ = store 1158 1159 def load(self, name): 1160 return self.names[name] 1161 1162 __getitem__ = load 1163 1164 def revoke(self, name, type): 1165 self.names[name].remove(type) 1166 1167 def revoke_exception_type(self, type): 1168 self.raises.remove(type) 1169 1170 def merge_namespace(self, namespace, everything=1): 1171 self.merge_items(namespace.names.items()) 1172 if everything: 1173 combine(self.returns, namespace.returns) 1174 combine(self.return_locals, namespace.return_locals) 1175 combine(self.raises, namespace.raises) 1176 for name, values in namespace.temp.items(): 1177 if values: 1178 if not self.temp.has_key(name) or not self.temp[name]: 1179 self.temp[name] = [[]] 1180 combine(self.temp[name][-1], values[-1]) 1181 1182 def merge_items(self, items): 1183 for name, types in items: 1184 self.merge(name, types) 1185 1186 def merge(self, name, types): 1187 if not self.names.has_key(name): 1188 self.names[name] = types[:] 1189 else: 1190 existing = self.names[name] 1191 combine(existing, types) 1192 1193 def snapshot(self): 1194 1195 "Make a snapshot of the locals and remember them." 1196 1197 namespace = Namespace() 1198 namespace.merge_namespace(self) 1199 self.return_locals.append(namespace) 1200 1201 def reset(self): 1202 1203 "Reset a namespace in preparation for merging with returned locals." 1204 1205 self.names = {} 1206 1207 def __repr__(self): 1208 return repr(self.names) 1209 1210 class Attribute: 1211 1212 """ 1213 An attribute abstraction, indicating the type of the attribute along with 1214 its context or origin. 1215 """ 1216 1217 def __init__(self, context, type): 1218 self.context = context 1219 self.type = type 1220 1221 def __eq__(self, other): 1222 return hasattr(other, "type") and other.type == self.type or other == self.type 1223 1224 def __repr__(self): 1225 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 1226 1227 class Self: 1228 1229 """ 1230 A program node encapsulating object/context information in an argument list. 1231 This is not particularly like Attribute, Class, Instance or other such 1232 things, since it actually appears in the program representation. 1233 """ 1234 1235 def __init__(self, attribute): 1236 self.types = [attribute] 1237 1238 def combine(target, additions): 1239 1240 """ 1241 Merge into the 'target' sequence the given 'additions', preventing duplicate 1242 items. 1243 """ 1244 1245 for addition in additions: 1246 if addition not in target: 1247 target.append(addition) 1248 1249 def find_attributes(structure, name): 1250 1251 """ 1252 Find for the given 'structure' all attributes for the given 'name', visiting 1253 base classes where appropriate and returning the attributes in order of 1254 descending precedence for all possible base classes. 1255 1256 The elements in the result list are 2-tuples which contain the attribute and 1257 the structure involved in accessing the attribute. 1258 """ 1259 1260 # First attempt to search the instance/class namespace. 1261 1262 try: 1263 l = structure.namespace.load(name) 1264 attributes = [] 1265 for attribute in l: 1266 attributes.append((attribute, structure)) 1267 1268 # If that does not work, attempt to investigate any class or base classes. 1269 1270 except KeyError: 1271 attributes = [] 1272 1273 # Investigate any instance's implementing class. 1274 1275 if isinstance(structure, Instance): 1276 for attr in structure.namespace.load("__class__"): 1277 cls = attr.type 1278 l = get_attributes(cls, name) 1279 combine(attributes, l) 1280 1281 # Investigate any class's base classes. 1282 1283 elif isinstance(structure, Class): 1284 1285 # If no base classes exist, return an indicator that no attribute 1286 # exists. 1287 1288 if not structure.base_refs: 1289 return [(None, structure)] 1290 1291 # Otherwise, find all possible base classes. 1292 1293 for base_refs in structure.base_refs: 1294 base_attributes = [] 1295 1296 # For each base class, find attributes either in the base 1297 # class or its own base classes. 1298 1299 for base_ref in base_refs: 1300 l = get_attributes(base_ref, name) 1301 combine(base_attributes, l) 1302 1303 combine(attributes, base_attributes) 1304 1305 return attributes 1306 1307 def get_attributes(structure, name): 1308 1309 """ 1310 Return all possible attributes for the given 'structure' having the given 1311 'name', wrapping each attribute in an Attribute object which includes 1312 context information for the attribute access. 1313 1314 The elements in the result list are 2-tuples which contain the attribute and 1315 the structure involved in accessing the attribute. 1316 """ 1317 1318 if isinstance(structure, Attribute): 1319 structure = structure.type 1320 results = [] 1321 for attribute, accessor in find_attributes(structure, name): 1322 if attribute is not None and isinstance(structure, Structure): 1323 results.append((Attribute(structure, attribute.type), accessor)) 1324 else: 1325 results.append((attribute, accessor)) 1326 return results 1327 1328 # Convenience functions. 1329 1330 def annotate(module, builtins=None): 1331 1332 """ 1333 Annotate the given 'module', also employing the optional 'builtins' module, 1334 if specified. 1335 """ 1336 1337 annotator = Annotator() 1338 if builtins is not None: 1339 annotator.process(module, builtins) 1340 else: 1341 annotator.process(module) 1342 1343 def annotate_all(modules, builtins): 1344 annotate(builtins) 1345 for module in modules: 1346 annotate(module, builtins) 1347 1348 # vim: tabstop=4 expandtab shiftwidth=4