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