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