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