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