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 = [] 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 if attribute.type not in invocations: 520 invocations.append(attribute.type) 521 522 elif not isinstance(attr.type, GeneralClass): 523 print "Invocation type is None for", accessor 524 525 else: 526 527 # Test to see if no arguments were supplied in cases where no 528 # initialiser was found. 529 530 if have_args: 531 raise AnnotationMessage, "No initialiser found for '%s' with arguments." % attr.type 532 533 # Special case: initialisation. 534 535 if isinstance(attr.type, GeneralClass): 536 537 # Associate the instance with the result of this invocation. 538 539 self.namespace.set_types(set([Attribute(None, instance)])) 540 self.annotate(invoke) 541 542 # Remember the invocations that were found, along with the return type 543 # information. 544 545 invoke.invocations = invocations 546 self.namespace.set_types(getattr(invoke, "types", set())) 547 548 def visitInvokeRef(self, invoke): 549 550 """ 551 Process the 'invoke' node, first finding the callables indicated by the 552 reference. 553 """ 554 555 # Where the invocation belongs to an instance but the invoked subprogram 556 # does not, request a special copy. 557 558 instance = getattr(invoke, "instance", None) 559 if instance is not None and getattr(invoke.ref, "instance", None) is None: 560 if invoke.ref.copies.has_key(instance): 561 invoke.ref = invoke.ref.copies[instance] 562 else: 563 invoke.ref = invoke.ref.copy(instance) 564 #print "Created", invoke.ref, "for", getattr(invoke.ref, "instance", None) 565 invoke.ref.module.simplifier.subnames[invoke.ref.full_name()] = invoke.ref 566 invocation_types = [Attribute(None, invoke.ref)] 567 self._visitInvoke(invoke, invocation_types, have_args=0) 568 569 def visitInvokeFunction(self, invoke): 570 571 """ 572 Process the 'invoke' node, first finding the callables indicated by the 573 expression. 574 """ 575 576 self.dispatch(invoke.expr) 577 invocation_types = self.namespace.types 578 579 # Invocation processing starts with making sure that the arguments have 580 # been processed. 581 582 self._visitInvoke(invoke, invocation_types, have_args=self.process_args(invoke)) 583 584 def visitLoadAttr(self, loadattr): 585 586 """ 587 Process the 'loadattr' node, processing and storing the expression, and 588 using the expression's types to construct records of accesses and 589 non-accesses using the stated attribute name. 590 """ 591 592 self.dispatch(loadattr.expr) 593 types = set() 594 raises = set() 595 non_accesses = set() 596 accesses = {} 597 598 # For each expression type... 599 600 for attr in self.namespace.types: 601 602 # Find types for the named attribute. 603 604 attributes = get_attributes(attr.type, loadattr.name) 605 606 # Where no attributes exist... 607 608 if not attributes: 609 610 # Register new invalid accesses and mark a possible exception. 611 612 if not attr in non_accesses: 613 non_accesses.add(attr) 614 exc = self.get_builtin_instances(loadattr, "AttributeError") 615 raises.update(exc) 616 self.namespace.raises.update(exc) 617 618 # Revoke this type from any name involved. 619 620 self._prune_non_accesses(loadattr.expr, attr) 621 622 # For each type found... 623 624 for attribute, accessor in attributes: 625 626 # For actual attributes, register the type and remember the 627 # access. 628 629 if attribute is not None: 630 types.add(attribute) 631 if not accesses.has_key(attr.type): 632 accesses[attr.type] = [] 633 if not (attribute, accessor) in accesses[attr.type]: 634 accesses[attr.type].append((attribute, accessor)) 635 636 # Otherwise, register new invalid accesses and note a possible 637 # exception. 638 639 else: 640 if not attr in non_accesses: 641 non_accesses.add(attr) 642 exc = self.get_builtin_instances(loadattr, "AttributeError") 643 raises.update(exc) 644 self.namespace.raises.update(exc) 645 646 # Revoke this type from any name involved. 647 648 self._prune_non_accesses(loadattr.expr, attr) 649 650 if not types: 651 print "No attribute found for", loadattr.name, "given", self.namespace.types 652 653 # Remember the result types. 654 655 self.namespace.set_types(types) 656 loadattr.non_accesses = non_accesses 657 loadattr.accesses = accesses 658 loadattr.raises = raises 659 self.annotate(loadattr) 660 661 def _prune_non_accesses(self, expr, attr): 662 663 """ 664 Prune type information from 'expr' where the given 'attr' has been 665 shown to be a non-access. 666 """ 667 668 if isinstance(expr, LoadName): 669 self.namespace.revoke(expr.name, attr) 670 elif isinstance(expr, LoadExc): 671 self.namespace.revoke_exception_type(attr) 672 elif isinstance(expr, LoadTemp): 673 self.namespace.revoke_temp_type(getattr(expr, "index", None), attr) 674 675 # LoadAttr cannot be pruned since this might unintentionally prune 676 # legitimate types from other applications of the referenced type, it 677 # almost certainly doesn't take "concurrent" mutation into 678 # consideration (where in a running program, the pruned type is actually 679 # reintroduced, making the pruning invalid), and there is no easy way of 680 # preserving the meaning of a namespace without either creating lots of 681 # specialised instances, and even then... 682 683 #elif isinstance(expr, LoadAttr): 684 # for expr_attr in expr.expr.types: 685 # if hasattr(expr_attr.type, "namespace"): 686 # expr_attr.type.namespace.revoke(expr.name, attr) 687 688 def visitLoadExc(self, loadexc): 689 690 """ 691 Process the 'loadexc' node, discovering the possible exception types 692 raised. 693 """ 694 695 self.namespace.set_types(self.namespace.raises) 696 self.annotate(loadexc) 697 698 def visitLoadName(self, loadname): 699 700 """ 701 Process the 'loadname' node, processing the name information on the node 702 to determine which types are involved with the name. 703 """ 704 705 self.namespace.set_types(self.namespace.load(loadname.name)) 706 self.annotate(loadname) 707 708 def visitLoadRef(self, loadref): 709 710 """ 711 Process the 'loadref' node, obtaining type information about the 712 reference stated on the node. 713 """ 714 715 self.namespace.set_types(set([Attribute(None, loadref.ref)])) 716 self.annotate(loadref) 717 718 def visitLoadTemp(self, loadtemp): 719 720 """ 721 Process the 'loadtemp' node, obtaining type information about the 722 temporary variable accessed, and removing variable information where the 723 'release' attribute has been set on the node. 724 """ 725 726 index = getattr(loadtemp, "index", None) 727 try: 728 if getattr(loadtemp, "release", 0): 729 self.namespace.set_types(self.namespace.temp[index].pop()) 730 else: 731 self.namespace.set_types(self.namespace.temp[index][-1]) 732 except KeyError: 733 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 734 self.annotate(loadtemp) 735 736 def visitMakeTuple(self, maketuple): 737 738 """ 739 Process the 'maketuple' node and its contents. 740 """ 741 742 # Get a tuple and populate it with type information for the contents. 743 744 tuples = self.get_builtin_instances(maketuple, "tuple") 745 746 # NOTE: This is dependent on the tuple definition in the builtins. 747 748 for i, node in enumerate(maketuple.nodes): 749 self.dispatch(node) 750 for t in tuples: 751 t.type.namespace.add("value", self.namespace.types) 752 t.type.namespace.add("__value__%d" % i, self.namespace.types) 753 754 self.namespace.set_types(tuples) 755 self.annotate(maketuple) 756 757 def visitModule(self, module): 758 759 """ 760 Process the 'module' and its contents. 761 """ 762 763 self.dispatches(module.code) 764 765 def visitNot(self, not_): 766 767 "Process the 'not_' node and its expression." 768 769 self.dispatch(not_.expr) 770 771 def visitPass(self, pass_): 772 773 "Leave the 'pass_' node unprocessed." 774 775 pass 776 777 def visitRaise(self, raise_): 778 779 """ 780 Process the 'raise_' node, processing any traceback information along 781 with the raised exception expression, converting the node into a kind of 782 invocation where the expression is found not to be an invocation itself. 783 This node affects the namespace, adding exception types to the list of 784 those raised in the namespace. 785 """ 786 787 if raise_.traceback is not None: 788 self.dispatch(raise_.traceback) 789 self.dispatch(raise_.expr) 790 791 # Handle bare name exceptions by converting any classes to instances. 792 793 if not isinstance(raise_.expr, InvokeFunction): 794 raise_.pos_args = [] 795 raise_.kw_args = {} 796 raise_.star = None 797 raise_.dstar = None 798 types = set() 799 for attr in self.namespace.types: 800 if isinstance(attr.type, GeneralClass): 801 self._visitInvoke(raise_, [attr], have_args=0) 802 types.update(self.namespace.types) 803 else: 804 types = self.namespace.types 805 806 self.namespace.raises.update(types) 807 808 def visitReleaseTemp(self, releasetemp): 809 810 """ 811 Process the 'releasetemp' node, removing temporary variable information 812 from the current namespace. 813 """ 814 815 index = getattr(releasetemp, "index", None) 816 try: 817 self.namespace.temp[index].pop() 818 except KeyError: 819 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 820 except IndexError: 821 pass #raise AnnotationMessage, "Temporary store index '%s' is empty." % index 822 823 def visitResetExc(self, resetexc): 824 self.namespace.raises = set() 825 826 def visitReturn(self, return_): 827 828 """ 829 Process the 'return_' node, processing any expression and obtaining type 830 information to be accumulated in the current namespace's list of return 831 types. A snapshot of the namespace is taken for the purposes of 832 reconciling or merging namespaces where subprograms actually share 833 locals with their callers. 834 """ 835 836 if hasattr(return_, "expr"): 837 self.dispatch(return_.expr) 838 self.namespace.returns.update(self.namespace.types) 839 self.annotate(return_) 840 self.namespace.snapshot() 841 842 visitReturnFromBlock = visitReturn 843 visitReturnFromFunction = visitReturn 844 845 def visitStoreAttr(self, storeattr): 846 847 """ 848 Process the 'storeattr' node, processing the expression and target, and 849 using the type information obtained to build records of legitimate 850 writes to the stated attribute, along with "impossible" non-writes to 851 the attribute. 852 """ 853 854 self.dispatch(storeattr.expr) 855 expr = self.namespace.types 856 self.dispatch(storeattr.lvalue) 857 writes = {} 858 non_writes = set() 859 for attr in self.namespace.types: 860 # NOTE: Impose "atomic" constraints on certain types. 861 if attr is None: 862 if not attr in non_writes: 863 non_writes.add(attr) 864 continue 865 attr.type.namespace.add(storeattr.name, expr) 866 writes[attr.type] = attr.type.namespace.load(storeattr.name) 867 if not writes: 868 print "Unable to store attribute", storeattr.name, "given", self.namespace.types 869 storeattr.writes = writes 870 storeattr.non_writes = non_writes 871 872 def visitStoreName(self, storename): 873 874 """ 875 Process the 'storename' node, processing the expression on the node and 876 associating the type information obtained with the stated name in the 877 current namespace. 878 """ 879 880 self.dispatch(storename.expr) 881 self.namespace.store(storename.name, self.namespace.types) 882 self.annotate(storename) 883 884 def visitStoreTemp(self, storetemp): 885 886 """ 887 Process the 'storetemp' node, processing the expression on the node and 888 associating the type information obtained with a temporary variable in 889 the current namespace. 890 """ 891 892 self.dispatch(storetemp.expr) 893 index = getattr(storetemp, "index", None) 894 if not self.namespace.temp.has_key(index): 895 self.namespace.temp[index] = [] 896 self.namespace.temp[index].append(self.namespace.types) 897 898 def visitSubprogram(self, subprogram): 899 900 """ 901 Process the 'subprogram' node, processing its contents (a group of nodes 902 comprising the subprogram). 903 """ 904 905 self.dispatches(subprogram.code) 906 907 def visitTry(self, try_): 908 909 """ 910 Process the 'try_' node, processing the body clause in its own namespace 911 derived from the current namespace, processing any handler clause using 912 the namespace information accumulated in the body, and processing any 913 else and finally clauses, attempting to supply each with appropriate 914 namespace information. 915 """ 916 917 is_module = self.namespace is self.module.namespace 918 919 self.dispatches(try_.body) 920 921 # Save the namespace from the body. 922 923 body_namespace = Namespace() 924 body_namespace.merge_namespace(self.namespace) 925 926 # Process the handler. 927 928 if hasattr(try_, "handler"): 929 self.dispatches(try_.handler) 930 931 # Save the namespace from the handler. 932 933 handler_namespace = Namespace() 934 handler_namespace.merge_namespace(self.namespace) 935 936 # Remember the raised exceptions encountered so far. 937 938 raises = self.namespace.raises 939 940 # Process the else clause. 941 942 if hasattr(try_, "else_"): 943 944 # Restore the body namespace for the else clause. 945 946 self.namespace = body_namespace 947 if is_module: 948 self.module.namespace = self.namespace 949 950 # Empty the raised exceptions for the else clause. 951 952 self.namespace.raises = set() 953 self.dispatches(try_.else_) 954 self.namespace.raises = raises 955 956 # Merge the namespaces. 957 958 self.namespace = Namespace() 959 if is_module: 960 self.module.namespace = self.namespace 961 self.namespace.merge_namespace(body_namespace) 962 self.namespace.merge_namespace(handler_namespace) 963 964 # Process the finally clause, if any. 965 966 self.dispatches(try_.finally_) 967 968 def visitYield(self, yield_): 969 raise NotImplementedError, "The yield statement is not currently supported." 970 971 # Utility methods. 972 973 def get_builtin_instances(self, node, name): 974 return set([Attribute(None, self.new_instance(node, attr.type)) for attr in self.builtins_namespace[name]]) 975 976 def new_instance(self, node, type): 977 978 "For the given 'node', obtain an instance from the given 'type'." 979 980 if not type.has_instance(node): 981 instance = Instance() 982 instance.namespace = Namespace() 983 instance.namespace.store("__class__", set([Attribute(None, type)])) 984 type.add_instance(node, instance) 985 else: 986 instance = type.get_instance(node) 987 988 return instance 989 990 def invoke_subprogram(self, invoke, attribute): 991 992 """ 993 Invoke using the given 'invoke' node the subprogram represented by the 994 given 'attribute'. 995 """ 996 997 # Test for context information, making it into a real attribute. 998 999 if attribute.context is not None: 1000 context = Attribute(None, attribute.context) 1001 target = attribute.type 1002 else: 1003 context = None 1004 target = attribute.type 1005 1006 # Test to see if anything has changed. 1007 1008 if hasattr(invoke, "syscount") and invoke.syscount.has_key(target) and invoke.syscount[target] == self.system.count: 1009 return 1010 1011 # Remember the state of the system. 1012 1013 else: 1014 if not hasattr(invoke, "syscount"): 1015 invoke.syscount = {} 1016 invoke.syscount[target] = self.system.count 1017 1018 # Provide the correct namespace for the invocation. 1019 # This may be a "shared" namespace... 1020 1021 if invoke.share_locals: 1022 namespace = Namespace() 1023 namespace.merge_namespace(self.namespace, everything=0) 1024 using_module_namespace = self.namespace is self.module.namespace 1025 1026 # Or it may be a structure... 1027 1028 elif target.structure: 1029 namespace = Namespace() 1030 using_module_namespace = 0 1031 1032 # Or it may be a new namespace populated with the supplied parameters. 1033 1034 else: 1035 items = self.make_items(invoke, target, context) 1036 namespace = Namespace() 1037 namespace.merge_items(items) 1038 using_module_namespace = 0 1039 1040 # NOTE: Avoid PEP 227 (nested scopes) whilst permitting references to a 1041 # NOTE: subprogram within itself. Do not define the name of the function 1042 # NOTE: within a method definition. 1043 1044 if target.name is not None and not target.is_method: 1045 namespace.store(target.name, set([Attribute(None, target)])) 1046 1047 # Process the subprogram. 1048 1049 self.process_node(target, namespace, using_module_namespace) 1050 1051 # NOTE: Improve and verify this. 1052 # If the invocation returns a value, acquire the return types. 1053 1054 if target.returns_value: 1055 self.namespace.set_types(target.returns) 1056 self.annotate(invoke) 1057 1058 # If it is a normal block, merge the locals. 1059 # This can happen in addition to the above because for things like 1060 # logical expressions, the namespace can be modified whilst values are 1061 # returned as results. 1062 1063 if invoke.share_locals: 1064 self.namespace.reset() 1065 1066 # Merge the locals snapshots. 1067 1068 for locals in target.return_locals: 1069 1070 # For blocks returning values (such as operations), do not merge 1071 # snapshots or results. 1072 1073 if target.returns_value: 1074 self.namespace.merge_namespace(locals, everything=0, temp=0) 1075 1076 # For blocks not returning values (such as loops), merge 1077 # snapshots and results since they contain details of genuine 1078 # returns. 1079 1080 else: 1081 self.namespace.merge_namespace(locals, temp=0) 1082 1083 # Incorporate any raised exceptions. 1084 1085 invoke.raises.update(target.raises) 1086 self.namespace.raises.update(target.raises) 1087 1088 def process_args(self, invocation): 1089 1090 """ 1091 Process the arguments associated with an 'invocation'. Return whether 1092 any arguments were processed. 1093 """ 1094 1095 self.dispatches(invocation.pos_args) 1096 self.dispatch_dict(invocation.kw_args) 1097 1098 # Get type information for star and dstar arguments. 1099 1100 if invocation.star is not None: 1101 param, default = invocation.star 1102 self.dispatch(default) 1103 invocation.star = param, default 1104 1105 if invocation.dstar is not None: 1106 param, default = invocation.dstar 1107 self.dispatch(default) 1108 invocation.dstar = param, default 1109 1110 if invocation.pos_args or invocation.kw_args or invocation.star or invocation.dstar: 1111 return 1 1112 else: 1113 return 0 1114 1115 def make_items(self, invocation, subprogram, context): 1116 1117 """ 1118 Make an items mapping for the 'invocation' of the 'subprogram' using the 1119 given 'context' (which may be None). 1120 """ 1121 1122 # NOTE: Support class methods! 1123 1124 if context is not None and isinstance(context.type, Instance): 1125 pos_args = [Self(context)] + invocation.pos_args 1126 else: 1127 pos_args = invocation.pos_args 1128 1129 # Duplicate the keyword arguments - we remove them in processing below. 1130 1131 kw_args = {} 1132 kw_args.update(invocation.kw_args) 1133 1134 # Sort the arguments into positional and keyword arguments. 1135 1136 params = subprogram.params 1137 items = [] 1138 star_args = [] 1139 1140 # Match each positional argument, taking excess arguments as star args. 1141 1142 for arg in pos_args: 1143 if params: 1144 param, default = params[0] 1145 if arg is None: 1146 arg = default 1147 if hasattr(arg, "types"): 1148 items.append((param, arg.types)) 1149 else: 1150 items.append((param, set())) # Annotation has not succeeded. 1151 params = params[1:] 1152 else: 1153 star_args.append(arg) 1154 1155 # Collect the remaining defaults. 1156 1157 while params: 1158 param, default = params[0] 1159 if kw_args.has_key(param): 1160 arg = kw_args[param] 1161 del kw_args[param] 1162 elif default is not None: 1163 self.dispatch(default) 1164 arg = default 1165 else: 1166 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) 1167 if hasattr(arg, "types"): 1168 items.append((param, arg.types)) 1169 else: 1170 items.append((param, set())) # Annotation has not succeeded. 1171 params = params[1:] 1172 1173 dstar_args = kw_args.items() 1174 1175 # Construct temporary objects. 1176 1177 if star_args: 1178 star_invocation = self.make_star_args(invocation, subprogram, star_args) 1179 self.dispatch(star_invocation) 1180 star_types = star_invocation.types 1181 else: 1182 star_types = None 1183 1184 if dstar_args: 1185 dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args) 1186 self.dispatch(dstar_invocation) 1187 dstar_types = dstar_invocation.types 1188 else: 1189 dstar_types = None 1190 1191 # NOTE: Merge the objects properly. 1192 1193 star_types = star_types or invocation.star and invocation.star.types 1194 dstar_types = dstar_types or invocation.dstar and invocation.dstar.types 1195 1196 # Add star and dstar. 1197 1198 if star_types is not None: 1199 if subprogram.star is not None: 1200 param, default = subprogram.star 1201 items.append((param, star_types)) 1202 else: 1203 raise AnnotationMessage, "Invocation provides unwanted *args." 1204 elif subprogram.star is not None: 1205 param, default = subprogram.star 1206 if not hasattr(default, "types") or not default.types: 1207 self.dispatch(default) # NOTE: Review reprocessing. 1208 items.append((param, default.types)) 1209 1210 if dstar_types is not None: 1211 if subprogram.dstar is not None: 1212 param, default = subprogram.dstar 1213 items.append((param, dstar_types)) 1214 else: 1215 raise AnnotationMessage, "Invocation provides unwanted **args." 1216 elif subprogram.dstar is not None: 1217 param, default = subprogram.dstar 1218 if not hasattr(default, "types") or not default.types: 1219 self.dispatch(default) # NOTE: Review reprocessing. 1220 items.append((param, default.types)) 1221 1222 # Record the parameter types. 1223 1224 self.annotate_parameters(subprogram, items) 1225 return subprogram.paramtypes.items() 1226 1227 def make_star_args(self, invocation, subprogram, star_args): 1228 1229 "Make a subprogram which initialises a list containing 'star_args'." 1230 1231 if not hasattr(invocation, "stars"): 1232 invocation.stars = {} 1233 1234 if not invocation.stars.has_key(subprogram.full_name()): 1235 instance = getattr(invocation, "instance", None) 1236 1237 code = [ 1238 Return( 1239 instance=instance, 1240 expr=MakeTuple( 1241 instance=instance, 1242 nodes=star_args 1243 ) 1244 ) 1245 ] 1246 1247 new_subprogram = Subprogram( 1248 instance=instance, 1249 name=None, 1250 returns_value=1, 1251 params=[], 1252 star=None, 1253 dstar=None, 1254 code=code 1255 ) 1256 1257 subprogram.module.simplifier.subnames[new_subprogram.full_name()] = new_subprogram 1258 1259 invocation.stars[subprogram.full_name()] = InvokeRef( 1260 invocation.original, 1261 instance=instance, 1262 produces_result=1, 1263 ref=new_subprogram 1264 ) 1265 1266 return invocation.stars[subprogram.full_name()] 1267 1268 def make_dstar_args(self, invocation, subprogram, dstar_args): 1269 1270 """ 1271 Make a subprogram which initialises a dictionary built from the given 1272 'dstar_args'. 1273 """ 1274 1275 if not hasattr(invocation, "dstars"): 1276 invocation.dstars = {} 1277 1278 if not invocation.dstars.has_key(subprogram.full_name()): 1279 instance = getattr(invocation, "instance", None) 1280 1281 code=[ 1282 StoreTemp( 1283 instance=instance, 1284 expr=InvokeFunction( 1285 invocation.original, 1286 instance=instance, 1287 expr=LoadAttr( 1288 instance=instance, 1289 expr=LoadRef( 1290 instance=instance, 1291 ref=self.builtins 1292 ), 1293 name="dict", 1294 nstype="module", 1295 ) 1296 ) 1297 ) 1298 ] 1299 1300 for arg, value in dstar_args: 1301 1302 # NOTE: Constant not added to table. 1303 1304 constant = Constant(name=repr(arg), value=arg) 1305 code += [ 1306 StoreTemp( 1307 instance=instance, 1308 expr=InvokeFunction( 1309 instance=instance, 1310 expr=LoadName( 1311 instance=instance, 1312 name=constant.typename 1313 ) 1314 ), 1315 index="const" 1316 ), 1317 InvokeFunction( 1318 invocation.original, 1319 instance=instance, 1320 expr=LoadAttr( 1321 instance=instance, 1322 expr=LoadTemp( 1323 instance=instance 1324 ), 1325 name="__setitem__" 1326 ), 1327 args=[ 1328 LoadTemp( 1329 instance=instance, 1330 index="const", 1331 release=1 1332 ), 1333 value 1334 ] 1335 ) 1336 ] 1337 1338 code += [ 1339 Return( 1340 instance=instance, 1341 expr=LoadTemp( 1342 instance=instance, 1343 release=1 1344 ) 1345 ) 1346 ] 1347 1348 new_subprogram = Subprogram( 1349 instance=instance, 1350 name=None, 1351 returns_value=1, 1352 params=[], 1353 star=None, 1354 dstar=None, 1355 code=code 1356 ) 1357 subprogram.module.simplifier.subnames[new_subprogram.full_name()] = new_subprogram 1358 1359 invocation.dstars[subprogram.full_name()] = InvokeRef( 1360 invocation.original, 1361 instance=instance, 1362 produces_result=1, 1363 ref=new_subprogram 1364 ) 1365 1366 return invocation.dstars[subprogram.full_name()] 1367 1368 # Namespace-related abstractions. 1369 1370 def combine(target, additions): 1371 1372 """ 1373 Merge into the 'target' sequence the given 'additions', preventing duplicate 1374 items. 1375 """ 1376 1377 for addition in additions: 1378 if addition not in target: 1379 target.append(addition) 1380 1381 def find_attributes(structure, name): 1382 1383 """ 1384 Find for the given 'structure' all attributes for the given 'name', visiting 1385 base classes where appropriate and returning the attributes in order of 1386 descending precedence for all possible base classes. 1387 1388 The elements in the result list are 2-tuples which contain the attribute and 1389 the structure involved in accessing the attribute. 1390 """ 1391 1392 # First attempt to search the instance/class namespace. 1393 1394 try: 1395 l = structure.namespace.load(name) 1396 attributes = [] 1397 for attribute in l: 1398 attributes.append((attribute, structure)) 1399 1400 # If that does not work, attempt to investigate any class or base classes. 1401 1402 except KeyError: 1403 attributes = [] 1404 1405 # Investigate any instance's implementing class. 1406 1407 if isinstance(structure, Instance): 1408 for attr in structure.namespace.load("__class__"): 1409 cls = attr.type 1410 l = get_attributes(cls, name) 1411 combine(attributes, l) 1412 1413 # Investigate any class's base classes. 1414 1415 elif isinstance(structure, GeneralClass): 1416 1417 # If no base classes exist, return an indicator that no attribute 1418 # exists. 1419 1420 if not structure.base_refs: 1421 return [(None, structure)] 1422 1423 # Otherwise, find all possible base classes. 1424 1425 for base_refs in structure.base_refs: 1426 base_attributes = [] 1427 1428 # For each base class, find attributes either in the base 1429 # class or its own base classes. 1430 1431 for base_ref in base_refs: 1432 l = get_attributes(base_ref, name) 1433 combine(base_attributes, l) 1434 1435 combine(attributes, base_attributes) 1436 1437 return attributes 1438 1439 def get_attributes(structure, name): 1440 1441 """ 1442 Return all possible attributes for the given 'structure' having the given 1443 'name', wrapping each attribute in an Attribute object which includes 1444 context information for the attribute access. 1445 1446 The elements in the result list are 2-tuples which contain the attribute and 1447 the structure involved in accessing the attribute. 1448 """ 1449 1450 if isinstance(structure, Attribute): 1451 structure = structure.type 1452 1453 results = [] 1454 for attribute, accessor in find_attributes(structure, name): 1455 1456 # Detect class attribute access via instances. 1457 1458 if attribute is not None and isinstance(structure, Instance) and isinstance(accessor, GeneralClass): 1459 attribute = accessor.get_attribute_for_instance(attribute, structure) 1460 1461 # Produce an attribute with the appropriate context. 1462 # Modules should not affect the context. 1463 1464 if attribute is not None and isinstance(structure, Module): 1465 results.append((attribute, accessor)) 1466 1467 # Access via classes and instances should set those as the context. 1468 1469 elif attribute is not None and isinstance(structure, Structure): 1470 results.append((Attribute(structure, attribute.type), accessor)) 1471 1472 # Other accesses are returned unmodified. 1473 1474 else: 1475 results.append((attribute, accessor)) 1476 1477 return results 1478 1479 def prompt(vars): 1480 try: 1481 while 1: 1482 s = raw_input("> ") 1483 print eval(s, vars) 1484 except EOFError: 1485 pass 1486 1487 # Convenience functions. 1488 1489 def annotate(module, builtins, importer): 1490 1491 """ 1492 Annotate the given 'module', also employing the 'builtins' module which may 1493 be specified as None. Use the 'importer' to find and load modules. 1494 """ 1495 1496 annotator = Annotator(importer) 1497 if builtins is not None: 1498 annotator.process(module, builtins) 1499 else: 1500 annotator.process(module) 1501 1502 # vim: tabstop=4 expandtab shiftwidth=4