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