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