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 else: 1199 star_types = None 1200 1201 if dstar_args: 1202 dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args) 1203 self.dispatch(dstar_invocation) 1204 dstar_types = dstar_invocation.types 1205 else: 1206 dstar_types = None 1207 1208 # NOTE: Merge the objects properly. 1209 1210 star_types = star_types or invocation.star and invocation.star.types 1211 dstar_types = dstar_types or invocation.dstar and invocation.dstar.types 1212 1213 # Add star and dstar. 1214 1215 if star_types is not None: 1216 if subprogram.star is not None: 1217 param, default = subprogram.star 1218 items.append((param, star_types)) 1219 else: 1220 raise AnnotationMessage, "Invocation provides unwanted *args." 1221 elif subprogram.star is not None: 1222 param, default = subprogram.star 1223 if not hasattr(default, "types") or not default.types: 1224 self.dispatch(default) # NOTE: Review reprocessing. 1225 items.append((param, default.types)) 1226 1227 if dstar_types is not None: 1228 if subprogram.dstar is not None: 1229 param, default = subprogram.dstar 1230 items.append((param, dstar_types)) 1231 else: 1232 raise AnnotationMessage, "Invocation provides unwanted **args." 1233 elif subprogram.dstar is not None: 1234 param, default = subprogram.dstar 1235 if not hasattr(default, "types") or not default.types: 1236 self.dispatch(default) # NOTE: Review reprocessing. 1237 items.append((param, default.types)) 1238 1239 # Record the parameter types. 1240 1241 self.annotate_parameters(subprogram, items) 1242 invocation.consumed_args[subprogram] = consumed_args 1243 return subprogram.paramtypes.items() 1244 1245 def make_star_args(self, invocation, subprogram, star_args): 1246 1247 "Make a subprogram which initialises a list containing 'star_args'." 1248 1249 if not hasattr(invocation, "stars"): 1250 invocation.stars = {} 1251 1252 if not invocation.stars.has_key(subprogram.full_name()): 1253 instance = getattr(invocation, "instance", None) 1254 1255 code = [ 1256 Return( 1257 instance=instance, 1258 expr=MakeTuple( 1259 instance=instance, 1260 nodes=star_args 1261 ) 1262 ) 1263 ] 1264 1265 new_subprogram = Subprogram( 1266 instance=instance, 1267 name=None, 1268 returns_value=1, 1269 params=[], 1270 star=None, 1271 dstar=None, 1272 code=code 1273 ) 1274 1275 subprogram.module.simplifier.subnames[new_subprogram.full_name()] = new_subprogram 1276 1277 invocation.stars[subprogram.full_name()] = InvokeRef( 1278 invocation.original, 1279 instance=instance, 1280 produces_result=1, 1281 ref=new_subprogram 1282 ) 1283 1284 return invocation.stars[subprogram.full_name()] 1285 1286 def make_dstar_args(self, invocation, subprogram, dstar_args): 1287 1288 """ 1289 Make a subprogram which initialises a dictionary built from the given 1290 'dstar_args'. 1291 """ 1292 1293 if not hasattr(invocation, "dstars"): 1294 invocation.dstars = {} 1295 1296 if not invocation.dstars.has_key(subprogram.full_name()): 1297 instance = getattr(invocation, "instance", None) 1298 1299 code=[ 1300 StoreTemp( 1301 instance=instance, 1302 expr=InvokeFunction( 1303 invocation.original, 1304 instance=instance, 1305 expr=LoadAttr( 1306 instance=instance, 1307 expr=LoadRef( 1308 instance=instance, 1309 ref=self.builtins 1310 ), 1311 name="dict", 1312 nstype="module", 1313 ) 1314 ) 1315 ) 1316 ] 1317 1318 for arg, value in dstar_args: 1319 1320 # NOTE: Constant not added to table. 1321 1322 code += [ 1323 StoreTemp( 1324 instance=instance, 1325 expr=Constant( 1326 instance=instance, 1327 name=repr(arg), 1328 value=arg 1329 ), 1330 index="const" 1331 ), 1332 InvokeFunction( 1333 invocation.original, 1334 instance=instance, 1335 expr=LoadAttr( 1336 instance=instance, 1337 expr=LoadTemp( 1338 instance=instance 1339 ), 1340 name="__setitem__" 1341 ), 1342 args=[ 1343 LoadTemp( 1344 instance=instance, 1345 index="const", 1346 release=1 1347 ), 1348 value 1349 ] 1350 ) 1351 ] 1352 1353 code += [ 1354 Return( 1355 instance=instance, 1356 expr=LoadTemp( 1357 instance=instance, 1358 release=1 1359 ) 1360 ) 1361 ] 1362 1363 new_subprogram = Subprogram( 1364 instance=instance, 1365 name=None, 1366 returns_value=1, 1367 params=[], 1368 star=None, 1369 dstar=None, 1370 code=code 1371 ) 1372 subprogram.module.simplifier.subnames[new_subprogram.full_name()] = new_subprogram 1373 1374 invocation.dstars[subprogram.full_name()] = InvokeRef( 1375 invocation.original, 1376 instance=instance, 1377 produces_result=1, 1378 ref=new_subprogram 1379 ) 1380 1381 return invocation.dstars[subprogram.full_name()] 1382 1383 # Namespace-related abstractions. 1384 1385 def combine(target, additions): 1386 1387 """ 1388 Merge into the 'target' sequence the given 'additions', preventing duplicate 1389 items. 1390 """ 1391 1392 for addition in additions: 1393 if addition not in target: 1394 target.append(addition) 1395 1396 def find_attributes(structure, name): 1397 1398 """ 1399 Find for the given 'structure' all attributes for the given 'name', visiting 1400 base classes where appropriate and returning the attributes in order of 1401 descending precedence for all possible base classes. 1402 1403 The elements in the result list are 2-tuples which contain the attribute and 1404 the structure involved in accessing the attribute. 1405 """ 1406 1407 # First attempt to search the instance/class namespace. 1408 1409 try: 1410 l = structure.namespace.load(name) 1411 attributes = [] 1412 for attribute in l: 1413 attributes.append((attribute, structure)) 1414 1415 # If that does not work, attempt to investigate any class or base classes. 1416 1417 except KeyError: 1418 attributes = [] 1419 1420 # Investigate any instance's implementing class. 1421 1422 if isinstance(structure, Instance): 1423 for attr in structure.namespace.load("__class__"): 1424 cls = attr.type 1425 l = get_attributes(cls, name) 1426 combine(attributes, l) 1427 1428 # Investigate any class's base classes. 1429 1430 elif isinstance(structure, GeneralClass): 1431 1432 # If no base classes exist, return an indicator that no attribute 1433 # exists. 1434 1435 if not structure.base_refs: 1436 return [(None, structure)] 1437 1438 # Otherwise, find all possible base classes. 1439 1440 for base_refs in structure.base_refs: 1441 base_attributes = [] 1442 1443 # For each base class, find attributes either in the base 1444 # class or its own base classes. 1445 1446 for base_ref in base_refs: 1447 l = get_attributes(base_ref, name) 1448 combine(base_attributes, l) 1449 1450 combine(attributes, base_attributes) 1451 1452 return attributes 1453 1454 def get_attributes(structure, name): 1455 1456 """ 1457 Return all possible attributes for the given 'structure' having the given 1458 'name', wrapping each attribute in an Attribute object which includes 1459 context information for the attribute access. 1460 1461 The elements in the result list are 2-tuples which contain the attribute and 1462 the structure involved in accessing the attribute. 1463 """ 1464 1465 if isinstance(structure, Attribute): 1466 structure = structure.type 1467 1468 results = [] 1469 for attribute, accessor in find_attributes(structure, name): 1470 1471 # Detect class attribute access via instances. 1472 1473 if attribute is not None and isinstance(structure, Instance) and isinstance(accessor, GeneralClass): 1474 attribute = accessor.get_attribute_for_instance(attribute, structure) 1475 1476 # Produce an attribute with the appropriate context. 1477 # Modules should not affect the context. 1478 1479 if attribute is not None and isinstance(structure, Module): 1480 results.append((attribute, accessor)) 1481 1482 # Access via classes and instances should set those as the context. 1483 1484 elif attribute is not None and isinstance(structure, Structure): 1485 results.append((Attribute(structure, attribute.type), accessor)) 1486 1487 # Other accesses are returned unmodified. 1488 1489 else: 1490 results.append((attribute, accessor)) 1491 1492 return results 1493 1494 def prompt(vars): 1495 try: 1496 while 1: 1497 s = raw_input("> ") 1498 print eval(s, vars) 1499 except EOFError: 1500 pass 1501 1502 # Convenience functions. 1503 1504 def annotate(module, builtins, importer): 1505 1506 """ 1507 Annotate the given 'module', also employing the 'builtins' module which may 1508 be specified as None. Use the 'importer' to find and load modules. 1509 """ 1510 1511 annotator = Annotator(importer) 1512 if builtins is not None: 1513 annotator.process(module, builtins) 1514 else: 1515 annotator.process(module) 1516 1517 # vim: tabstop=4 expandtab shiftwidth=4