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