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