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