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