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 i, node in enumerate(maketuple.nodes): 755 self.dispatch(node) 756 for t in tuples: 757 t.type.namespace.add("value", self.namespace.types) 758 t.type.namespace.add("__value__%d" % i, self.namespace.types) 759 760 self.namespace.set_types(tuples) 761 self.annotate(maketuple) 762 763 def visitModule(self, module): 764 765 """ 766 Process the 'module' and its contents. 767 """ 768 769 self.dispatches(module.code) 770 771 def visitNot(self, not_): 772 773 "Process the 'not_' node and its expression." 774 775 self.dispatch(not_.expr) 776 777 def visitPass(self, pass_): 778 779 "Leave the 'pass_' node unprocessed." 780 781 pass 782 783 def visitRaise(self, raise_): 784 785 """ 786 Process the 'raise_' node, processing any traceback information along 787 with the raised exception expression, converting the node into a kind of 788 invocation where the expression is found not to be an invocation itself. 789 This node affects the namespace, adding exception types to the list of 790 those raised in the namespace. 791 """ 792 793 if getattr(raise_, "traceback", None) is not None: 794 self.dispatch(raise_.traceback) 795 self.dispatch(raise_.expr) 796 797 # Handle bare name exceptions by converting any classes to instances. 798 799 if not isinstance(raise_.expr, InvokeFunction): 800 raise_.pos_args = [] 801 raise_.kw_args = {} 802 raise_.star = None 803 raise_.dstar = None 804 types = set() 805 for attr in self.namespace.types: 806 if isinstance(attr.type, GeneralClass): 807 self._visitInvoke(raise_, [attr], have_args=0) 808 types.update(self.namespace.types) 809 else: 810 types = self.namespace.types 811 812 self.namespace.raises.update(types) 813 814 def visitReleaseTemp(self, releasetemp): 815 816 """ 817 Process the 'releasetemp' node, removing temporary variable information 818 from the current namespace. 819 """ 820 821 index = getattr(releasetemp, "index", None) 822 try: 823 self.namespace.temp[index].pop() 824 except KeyError: 825 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 826 except IndexError: 827 pass #raise AnnotationMessage, "Temporary store index '%s' is empty." % index 828 829 def visitResetExc(self, resetexc): 830 self.namespace.raises = set() 831 832 def visitReturn(self, return_): 833 834 """ 835 Process the 'return_' node, processing any expression and obtaining type 836 information to be accumulated in the current namespace's list of return 837 types. A snapshot of the namespace is taken for the purposes of 838 reconciling or merging namespaces where subprograms actually share 839 locals with their callers. 840 """ 841 842 if hasattr(return_, "expr"): 843 self.dispatch(return_.expr) 844 self.namespace.returns.update(self.namespace.types) 845 self.annotate(return_) 846 self.namespace.snapshot() 847 848 visitReturnFromBlock = visitReturn 849 visitReturnFromFunction = visitReturn 850 851 def visitStoreAttr(self, storeattr): 852 853 """ 854 Process the 'storeattr' node, processing the expression and target, and 855 using the type information obtained to build records of legitimate 856 writes to the stated attribute, along with "impossible" non-writes to 857 the attribute. 858 """ 859 860 self.dispatch(storeattr.expr) 861 expr = self.namespace.types 862 self.dispatch(storeattr.lvalue) 863 writes = {} 864 non_writes = set() 865 for attr in self.namespace.types: 866 # NOTE: Impose "atomic" constraints on certain types. 867 if attr is None: 868 if not attr in non_writes: 869 non_writes.add(attr) 870 continue 871 attr.type.namespace.add(storeattr.name, expr) 872 writes[attr.type] = attr.type.namespace.load(storeattr.name) 873 if not writes: 874 print "Unable to store attribute", storeattr.name, "given", self.namespace.types 875 storeattr.writes = writes 876 storeattr.non_writes = non_writes 877 878 def visitStoreName(self, storename): 879 880 """ 881 Process the 'storename' node, processing the expression on the node and 882 associating the type information obtained with the stated name in the 883 current namespace. 884 """ 885 886 self.dispatch(storename.expr) 887 self.namespace.store(storename.name, self.namespace.types) 888 self.annotate(storename) 889 890 def visitStoreTemp(self, storetemp): 891 892 """ 893 Process the 'storetemp' node, processing the expression on the node and 894 associating the type information obtained with a temporary variable in 895 the current namespace. 896 """ 897 898 self.dispatch(storetemp.expr) 899 index = getattr(storetemp, "index", None) 900 if not self.namespace.temp.has_key(index): 901 self.namespace.temp[index] = [] 902 self.namespace.temp[index].append(self.namespace.types) 903 904 def visitSubprogram(self, subprogram): 905 906 """ 907 Process the 'subprogram' node, processing its contents (a group of nodes 908 comprising the subprogram). 909 """ 910 911 self.dispatches(subprogram.code) 912 913 def visitTry(self, try_): 914 915 """ 916 Process the 'try_' node, processing the body clause in its own namespace 917 derived from the current namespace, processing any handler clause using 918 the namespace information accumulated in the body, and processing any 919 else and finally clauses, attempting to supply each with appropriate 920 namespace information. 921 """ 922 923 is_module = self.namespace is self.module.namespace 924 925 self.dispatches(try_.body) 926 927 # Save the namespace from the body. 928 929 body_namespace = Namespace() 930 body_namespace.merge_namespace(self.namespace) 931 932 # Process the handler. 933 934 if hasattr(try_, "handler"): 935 self.dispatches(try_.handler) 936 937 # Save the namespace from the handler. 938 939 handler_namespace = Namespace() 940 handler_namespace.merge_namespace(self.namespace) 941 942 # Remember the raised exceptions encountered so far. 943 944 raises = self.namespace.raises 945 946 # Process the else clause. 947 948 if hasattr(try_, "else_"): 949 950 # Restore the body namespace for the else clause. 951 952 self.namespace = body_namespace 953 if is_module: 954 self.module.namespace = self.namespace 955 956 # Empty the raised exceptions for the else clause. 957 958 self.namespace.raises = set() 959 self.dispatches(try_.else_) 960 self.namespace.raises = raises 961 962 # Merge the namespaces. 963 964 self.namespace = Namespace() 965 if is_module: 966 self.module.namespace = self.namespace 967 self.namespace.merge_namespace(body_namespace) 968 self.namespace.merge_namespace(handler_namespace) 969 970 # Process the finally clause, if any. 971 972 self.dispatches(try_.finally_) 973 974 def visitYield(self, yield_): 975 raise NotImplementedError, "The yield statement is not currently supported." 976 977 # Utility methods. 978 979 def get_builtin_instances(self, node, name): 980 return set([Attribute(None, self.new_instance(node, attr.type)) for attr in self.builtins_namespace[name]]) 981 982 def new_instance(self, node, type): 983 984 "For the given 'node', obtain an instance from the given 'type'." 985 986 if not type.has_instance(node): 987 instance = Instance() 988 instance.namespace = Namespace() 989 instance.namespace.store("__class__", set([Attribute(None, type)])) 990 type.add_instance(node, instance) 991 else: 992 instance = type.get_instance(node) 993 994 return instance 995 996 def invoke_subprogram(self, invoke, attribute): 997 998 """ 999 Invoke using the given 'invoke' node the subprogram represented by the 1000 given 'attribute'. 1001 """ 1002 1003 # Test for context information, making it into a real attribute. 1004 1005 if attribute.context is not None: 1006 context = Attribute(None, attribute.context) 1007 target = attribute.type 1008 else: 1009 context = None 1010 target = attribute.type 1011 1012 # Test to see if anything has changed. 1013 1014 if hasattr(invoke, "syscount") and invoke.syscount.has_key(target) and invoke.syscount[target] == self.system.count: 1015 return 1016 1017 # Remember the state of the system. 1018 1019 else: 1020 if not hasattr(invoke, "syscount"): 1021 invoke.syscount = {} 1022 invoke.syscount[target] = self.system.count 1023 1024 # Provide the correct namespace for the invocation. 1025 # This may be a "shared" namespace... 1026 1027 if getattr(invoke, "share_locals", 0): 1028 namespace = Namespace() 1029 namespace.merge_namespace(self.namespace, everything=0) 1030 using_module_namespace = self.namespace is self.module.namespace 1031 1032 # Or it may be a structure... 1033 1034 elif getattr(target, "structure", None): 1035 namespace = Namespace() 1036 using_module_namespace = 0 1037 1038 # Or it may be a new namespace populated with the supplied parameters. 1039 1040 else: 1041 items = self.make_items(invoke, target, context) 1042 namespace = Namespace() 1043 namespace.merge_items(items) 1044 using_module_namespace = 0 1045 1046 # NOTE: Avoid PEP 227 (nested scopes) whilst permitting references to a 1047 # NOTE: subprogram within itself. Do not define the name of the function 1048 # NOTE: within a method definition. 1049 1050 if getattr(target, "name", None) is not None and not getattr(target, "is_method", 0): 1051 namespace.store(target.name, set([Attribute(None, target)])) 1052 1053 # Process the subprogram. 1054 1055 self.process_node(target, namespace, using_module_namespace) 1056 1057 # NOTE: Improve and verify this. 1058 # If the invocation returns a value, acquire the return types. 1059 1060 if getattr(target, "returns_value", 0): 1061 self.namespace.set_types(target.returns) 1062 self.annotate(invoke) 1063 1064 # If it is a normal block, merge the locals. 1065 # This can happen in addition to the above because for things like 1066 # logical expressions, the namespace can be modified whilst values are 1067 # returned as results. 1068 1069 if getattr(invoke, "share_locals", 0): 1070 self.namespace.reset() 1071 1072 # Merge the locals snapshots. 1073 1074 for locals in target.return_locals: 1075 1076 # For blocks returning values (such as operations), do not merge 1077 # snapshots or results. 1078 1079 if getattr(target, "returns_value", 0): 1080 self.namespace.merge_namespace(locals, everything=0, temp=0) 1081 1082 # For blocks not returning values (such as loops), merge 1083 # snapshots and results since they contain details of genuine 1084 # returns. 1085 1086 else: 1087 self.namespace.merge_namespace(locals, temp=0) 1088 1089 # Incorporate any raised exceptions. 1090 1091 if not hasattr(invoke, "raises"): 1092 invoke.raises = set() 1093 invoke.raises.update(target.raises) 1094 self.namespace.raises.update(target.raises) 1095 1096 def process_args(self, invocation): 1097 1098 """ 1099 Process the arguments associated with an 'invocation'. Return whether 1100 any arguments were processed. 1101 """ 1102 1103 self.dispatches(invocation.pos_args) 1104 self.dispatch_dict(invocation.kw_args) 1105 1106 # Get type information for star and dstar arguments. 1107 1108 if invocation.star is not None: 1109 param, default = invocation.star 1110 self.dispatch(default) 1111 invocation.star = param, default 1112 1113 if invocation.dstar is not None: 1114 param, default = invocation.dstar 1115 self.dispatch(default) 1116 invocation.dstar = param, default 1117 1118 if invocation.pos_args or invocation.kw_args or invocation.star or invocation.dstar: 1119 return 1 1120 else: 1121 return 0 1122 1123 def make_items(self, invocation, subprogram, context): 1124 1125 """ 1126 Make an items mapping for the 'invocation' of the 'subprogram' using the 1127 given 'context' (which may be None). 1128 """ 1129 1130 # NOTE: Support class methods! 1131 1132 if context is not None and isinstance(context.type, Instance): 1133 pos_args = [Self(context)] + invocation.pos_args 1134 else: 1135 pos_args = invocation.pos_args 1136 1137 # Duplicate the keyword arguments - we remove them in processing below. 1138 1139 kw_args = {} 1140 kw_args.update(invocation.kw_args) 1141 1142 # Sort the arguments into positional and keyword arguments. 1143 1144 params = subprogram.params 1145 items = [] 1146 star_args = [] 1147 1148 # Match each positional argument, taking excess arguments as star args. 1149 1150 for arg in pos_args: 1151 if params: 1152 param, default = params[0] 1153 if arg is None: 1154 arg = default 1155 if hasattr(arg, "types"): 1156 items.append((param, arg.types)) 1157 else: 1158 items.append((param, set())) # Annotation has not succeeded. 1159 params = params[1:] 1160 else: 1161 star_args.append(arg) 1162 1163 # Collect the remaining defaults. 1164 1165 while params: 1166 param, default = params[0] 1167 if kw_args.has_key(param): 1168 arg = kw_args[param] 1169 del kw_args[param] 1170 elif default is not None: 1171 self.dispatch(default) 1172 arg = default 1173 else: 1174 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) 1175 if hasattr(arg, "types"): 1176 items.append((param, arg.types)) 1177 else: 1178 items.append((param, set())) # Annotation has not succeeded. 1179 params = params[1:] 1180 1181 dstar_args = kw_args.items() 1182 1183 # Construct temporary objects. 1184 1185 if star_args: 1186 star_invocation = self.make_star_args(invocation, subprogram, star_args) 1187 self.dispatch(star_invocation) 1188 star_types = star_invocation.types 1189 else: 1190 star_types = None 1191 1192 if dstar_args: 1193 dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args) 1194 self.dispatch(dstar_invocation) 1195 dstar_types = dstar_invocation.types 1196 else: 1197 dstar_types = None 1198 1199 # NOTE: Merge the objects properly. 1200 1201 star_types = star_types or invocation.star and invocation.star.types 1202 dstar_types = dstar_types or invocation.dstar and invocation.dstar.types 1203 1204 # Add star and dstar. 1205 1206 if star_types is not None: 1207 if subprogram.star is not None: 1208 param, default = subprogram.star 1209 items.append((param, star_types)) 1210 else: 1211 raise AnnotationMessage, "Invocation provides unwanted *args." 1212 elif subprogram.star is not None: 1213 param, default = subprogram.star 1214 if not hasattr(default, "types"): 1215 subprogram.star = param, self.dispatch(default) # NOTE: Review reprocessing. 1216 items.append((param, default.types)) 1217 1218 if dstar_types is not None: 1219 if subprogram.dstar is not None: 1220 param, default = subprogram.dstar 1221 items.append((param, dstar_types)) 1222 else: 1223 raise AnnotationMessage, "Invocation provides unwanted **args." 1224 elif subprogram.dstar is not None: 1225 param, default = subprogram.dstar 1226 if not hasattr(default, "types"): 1227 subprogram.dstar = param, self.dispatch(default) # NOTE: Review reprocessing. 1228 items.append((param, default.types)) 1229 1230 # Record the parameter types. 1231 1232 self.annotate_parameters(subprogram, items) 1233 return subprogram.paramtypes.items() 1234 1235 def make_star_args(self, invocation, subprogram, star_args): 1236 1237 "Make a subprogram which initialises a list containing 'star_args'." 1238 1239 if not hasattr(invocation, "stars"): 1240 invocation.stars = {} 1241 1242 if not invocation.stars.has_key(subprogram.full_name()): 1243 instance = getattr(invocation, "instance", None) 1244 1245 code = [ 1246 Return( 1247 instance=instance, 1248 expr=MakeTuple( 1249 instance=instance, 1250 nodes=star_args 1251 ) 1252 ) 1253 ] 1254 1255 new_subprogram = Subprogram( 1256 instance=instance, 1257 name=None, 1258 returns_value=1, 1259 params=[], 1260 star=None, 1261 dstar=None, 1262 code=code 1263 ) 1264 1265 subprogram.module.simplifier.subnames[new_subprogram.full_name()] = new_subprogram 1266 1267 invocation.stars[subprogram.full_name()] = InvokeRef( 1268 invocation.original, 1269 instance=instance, 1270 produces_result=1, 1271 ref=new_subprogram 1272 ) 1273 1274 return invocation.stars[subprogram.full_name()] 1275 1276 def make_dstar_args(self, invocation, subprogram, dstar_args): 1277 1278 """ 1279 Make a subprogram which initialises a dictionary built from the given 1280 'dstar_args'. 1281 """ 1282 1283 if not hasattr(invocation, "dstars"): 1284 invocation.dstars = {} 1285 1286 if not invocation.dstars.has_key(subprogram.full_name()): 1287 instance = getattr(invocation, "instance", None) 1288 1289 code=[ 1290 StoreTemp( 1291 instance=instance, 1292 expr=InvokeFunction( 1293 invocation.original, 1294 instance=instance, 1295 expr=LoadAttr( 1296 instance=instance, 1297 expr=LoadRef( 1298 instance=instance, 1299 ref=self.builtins 1300 ), 1301 name="dict", 1302 nstype="module", 1303 ) 1304 ) 1305 ) 1306 ] 1307 1308 for arg, value in dstar_args: 1309 1310 # NOTE: Constant not added to table. 1311 1312 constant = Constant(name=repr(arg), value=arg) 1313 code += [ 1314 StoreTemp( 1315 instance=instance, 1316 expr=InvokeFunction( 1317 instance=instance, 1318 expr=LoadName( 1319 instance=instance, 1320 name=constant.typename 1321 ) 1322 ), 1323 index="const" 1324 ), 1325 InvokeFunction( 1326 invocation.original, 1327 instance=instance, 1328 expr=LoadAttr( 1329 instance=instance, 1330 expr=LoadTemp( 1331 instance=instance 1332 ), 1333 name="__setitem__" 1334 ), 1335 args=[ 1336 LoadTemp( 1337 instance=instance, 1338 index="const", 1339 release=1 1340 ), 1341 value 1342 ] 1343 ) 1344 ] 1345 1346 code += [ 1347 Return( 1348 instance=instance, 1349 expr=LoadTemp( 1350 instance=instance, 1351 release=1 1352 ) 1353 ) 1354 ] 1355 1356 new_subprogram = Subprogram( 1357 instance=instance, 1358 name=None, 1359 returns_value=1, 1360 params=[], 1361 star=None, 1362 dstar=None, 1363 code=code 1364 ) 1365 subprogram.module.simplifier.subnames[new_subprogram.full_name()] = new_subprogram 1366 1367 invocation.dstars[subprogram.full_name()] = InvokeRef( 1368 invocation.original, 1369 instance=instance, 1370 produces_result=1, 1371 ref=new_subprogram 1372 ) 1373 1374 return invocation.dstars[subprogram.full_name()] 1375 1376 # Namespace-related abstractions. 1377 1378 def combine(target, additions): 1379 1380 """ 1381 Merge into the 'target' sequence the given 'additions', preventing duplicate 1382 items. 1383 """ 1384 1385 for addition in additions: 1386 if addition not in target: 1387 target.append(addition) 1388 1389 def find_attributes(structure, name): 1390 1391 """ 1392 Find for the given 'structure' all attributes for the given 'name', visiting 1393 base classes where appropriate and returning the attributes in order of 1394 descending precedence for all possible base classes. 1395 1396 The elements in the result list are 2-tuples which contain the attribute and 1397 the structure involved in accessing the attribute. 1398 """ 1399 1400 # First attempt to search the instance/class namespace. 1401 1402 try: 1403 l = structure.namespace.load(name) 1404 attributes = [] 1405 for attribute in l: 1406 attributes.append((attribute, structure)) 1407 1408 # If that does not work, attempt to investigate any class or base classes. 1409 1410 except KeyError: 1411 attributes = [] 1412 1413 # Investigate any instance's implementing class. 1414 1415 if isinstance(structure, Instance): 1416 for attr in structure.namespace.load("__class__"): 1417 cls = attr.type 1418 l = get_attributes(cls, name) 1419 combine(attributes, l) 1420 1421 # Investigate any class's base classes. 1422 1423 elif isinstance(structure, GeneralClass): 1424 1425 # If no base classes exist, return an indicator that no attribute 1426 # exists. 1427 1428 if not structure.base_refs: 1429 return [(None, structure)] 1430 1431 # Otherwise, find all possible base classes. 1432 1433 for base_refs in structure.base_refs: 1434 base_attributes = [] 1435 1436 # For each base class, find attributes either in the base 1437 # class or its own base classes. 1438 1439 for base_ref in base_refs: 1440 l = get_attributes(base_ref, name) 1441 combine(base_attributes, l) 1442 1443 combine(attributes, base_attributes) 1444 1445 return attributes 1446 1447 def get_attributes(structure, name): 1448 1449 """ 1450 Return all possible attributes for the given 'structure' having the given 1451 'name', wrapping each attribute in an Attribute object which includes 1452 context information for the attribute access. 1453 1454 The elements in the result list are 2-tuples which contain the attribute and 1455 the structure involved in accessing the attribute. 1456 """ 1457 1458 if isinstance(structure, Attribute): 1459 structure = structure.type 1460 1461 results = [] 1462 for attribute, accessor in find_attributes(structure, name): 1463 1464 # Detect class attribute access via instances. 1465 1466 if attribute is not None and isinstance(structure, Instance) and isinstance(accessor, GeneralClass): 1467 attribute = accessor.get_attribute_for_instance(attribute, structure) 1468 1469 # Produce an attribute with the appropriate context. 1470 # Modules should not affect the context. 1471 1472 if attribute is not None and isinstance(structure, Module): 1473 results.append((attribute, accessor)) 1474 1475 # Access via classes and instances should set those as the context. 1476 1477 elif attribute is not None and isinstance(structure, Structure): 1478 results.append((Attribute(structure, attribute.type), accessor)) 1479 1480 # Other accesses are returned unmodified. 1481 1482 else: 1483 results.append((attribute, accessor)) 1484 1485 return results 1486 1487 def prompt(vars): 1488 try: 1489 while 1: 1490 s = raw_input("> ") 1491 print eval(s, vars) 1492 except EOFError: 1493 pass 1494 1495 # Convenience functions. 1496 1497 def annotate(module, builtins, importer): 1498 1499 """ 1500 Annotate the given 'module', also employing the 'builtins' module which may 1501 be specified as None. Use the 'importer' to find and load modules. 1502 """ 1503 1504 annotator = Annotator(importer) 1505 if builtins is not None: 1506 annotator.process(module, builtins) 1507 else: 1508 annotator.process(module) 1509 1510 # vim: tabstop=4 expandtab shiftwidth=4