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 # Utility methods. 896 897 def get_builtin_instances(self, node, name): 898 return [Attribute(None, self.new_instance(node, attr.type)) for attr in self.builtins.namespace[name]] 899 900 def new_instance(self, node, type): 901 902 "For the given 'node', obtain an instance from the given 'type'." 903 904 if not type.has_instance(node): 905 instance = Instance() 906 instance.namespace = Namespace() 907 instance.namespace.store("__class__", [Attribute(None, type)]) 908 type.add_instance(node, instance) 909 else: 910 instance = type.get_instance(node) 911 912 return instance 913 914 def invoke_subprogram(self, invoke, attribute): 915 916 """ 917 Invoke using the given 'invoke' node the subprogram represented by the 918 given 'attribute'. 919 """ 920 921 # Test for context information, making it into a real attribute. 922 923 if attribute.context is not None: 924 context = Attribute(None, attribute.context) 925 target = attribute.type 926 else: 927 context = None 928 target = attribute.type 929 930 # Test to see if anything has changed. 931 932 if hasattr(invoke, "syscount") and invoke.syscount.has_key(target) and invoke.syscount[target] == self.system.count: 933 return 934 935 # Remember the state of the system. 936 937 else: 938 if not hasattr(invoke, "syscount"): 939 invoke.syscount = {} 940 invoke.syscount[target] = self.system.count 941 942 # Provide the correct namespace for the invocation. 943 # This may be a "shared" namespace... 944 945 if getattr(invoke, "share_locals", 0): 946 namespace = Namespace() 947 namespace.merge_namespace(self.namespace, everything=0) 948 using_module_namespace = self.namespace is self.module.namespace 949 950 # Or it may be a structure... 951 952 elif getattr(target, "structure", None): 953 namespace = Namespace() 954 using_module_namespace = 0 955 956 # Or it may be a new namespace populated with the supplied parameters. 957 958 else: 959 items = self.make_items(invoke, target, context) 960 namespace = Namespace() 961 namespace.merge_items(items) 962 using_module_namespace = 0 963 964 # NOTE: Avoid PEP 227 (nested scopes) whilst permitting references to a 965 # NOTE: subprogram within itself. Do not define the name of the function 966 # NOTE: within a method definition. 967 968 if getattr(target, "name", None) is not None and not getattr(target, "is_method", 0): 969 namespace.store(target.name, [Attribute(None, target)]) 970 971 # Process the subprogram. 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 = namespace 977 978 self.process_node(target, namespace) 979 980 # NOTE: Improve and verify this. 981 # If the invocation returns a value, acquire the return types. 982 983 if getattr(target, "returns_value", 0): 984 self.namespace.set_types(self.last_returns) 985 self.annotate(invoke) 986 987 # If it is a normal block, merge the locals. 988 # This can happen in addition to the above because for things like 989 # logical expressions, the namespace can be modified whilst values are 990 # returned as results. 991 992 if getattr(invoke, "share_locals", 0): 993 self.namespace.reset() 994 995 # Merge the locals snapshots. 996 997 for locals in self.returned_locals: 998 999 # For blocks returning values (such as operations), do not merge 1000 # snapshots or results. 1001 1002 if getattr(target, "returns_value", 0): 1003 self.namespace.merge_namespace(locals, everything=0) 1004 1005 # For blocks not returning values (such as loops), merge 1006 # snapshots and results since they contain details of genuine 1007 # returns. 1008 1009 else: 1010 self.namespace.merge_namespace(locals) 1011 1012 # Incorporate any raised exceptions. 1013 1014 if not hasattr(invoke, "raises"): 1015 invoke.raises = [] 1016 combine(invoke.raises, self.last_raises) 1017 combine(self.namespace.raises, self.last_raises) 1018 1019 # In order to keep global accesses working, the module namespace must be 1020 # adjusted. 1021 1022 if using_module_namespace: 1023 self.module.namespace = self.namespace 1024 1025 def process_args(self, invocation): 1026 1027 """ 1028 Process the arguments associated with an 'invocation'. Return whether 1029 any arguments were processed. 1030 """ 1031 1032 invocation.pos_args = self.dispatches(invocation.pos_args) 1033 invocation.kw_args = self.dispatch_dict(invocation.kw_args) 1034 1035 # Get type information for star and dstar arguments. 1036 1037 if invocation.star is not None: 1038 param, default = invocation.star 1039 default = self.dispatch(default) 1040 invocation.star = param, default 1041 1042 if invocation.dstar is not None: 1043 param, default = invocation.dstar 1044 default = self.dispatch(default) 1045 invocation.dstar = param, default 1046 1047 if invocation.pos_args or invocation.kw_args or invocation.star or invocation.dstar: 1048 return 1 1049 else: 1050 return 0 1051 1052 def make_items(self, invocation, subprogram, context): 1053 1054 """ 1055 Make an items mapping for the 'invocation' of the 'subprogram' using the 1056 given 'context' (which may be None). 1057 """ 1058 1059 if context is not None: 1060 pos_args = [Self(context)] + invocation.pos_args 1061 else: 1062 pos_args = invocation.pos_args 1063 1064 # Duplicate the keyword arguments - we remove them in processing below. 1065 1066 kw_args = {} 1067 kw_args.update(invocation.kw_args) 1068 1069 # Sort the arguments into positional and keyword arguments. 1070 1071 params = subprogram.params 1072 items = [] 1073 star_args = [] 1074 1075 # Match each positional argument, taking excess arguments as star args. 1076 1077 for arg in pos_args: 1078 if params: 1079 param, default = params[0] 1080 if arg is None: 1081 arg = default 1082 if hasattr(arg, "types"): 1083 items.append((param, arg.types)) 1084 else: 1085 items.append((param, [])) # Annotation has not succeeded. 1086 params = params[1:] 1087 else: 1088 star_args.append(arg) 1089 1090 # Collect the remaining defaults. 1091 1092 while params: 1093 param, default = params[0] 1094 if kw_args.has_key(param): 1095 arg = kw_args[param] 1096 del kw_args[param] 1097 elif default is not None: 1098 arg = self.dispatch(default) 1099 else: 1100 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) 1101 if hasattr(arg, "types"): 1102 items.append((param, arg.types)) 1103 else: 1104 items.append((param, [])) # Annotation has not succeeded. 1105 params = params[1:] 1106 1107 dstar_args = kw_args.items() 1108 1109 # Construct temporary objects. 1110 1111 if star_args: 1112 star_invocation = self.make_star_args(invocation, subprogram, star_args) 1113 self.dispatch(star_invocation) 1114 star_types = star_invocation.types 1115 else: 1116 star_types = None 1117 1118 if dstar_args: 1119 dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args) 1120 self.dispatch(dstar_invocation) 1121 dstar_types = dstar_invocation.types 1122 else: 1123 dstar_types = None 1124 1125 # NOTE: Merge the objects properly. 1126 1127 star_types = star_types or invocation.star and invocation.star.types 1128 dstar_types = dstar_types or invocation.dstar and invocation.dstar.types 1129 1130 # Add star and dstar. 1131 1132 if star_types is not None: 1133 if subprogram.star is not None: 1134 param, default = subprogram.star 1135 items.append((param, star_types)) 1136 else: 1137 raise AnnotationMessage, "Invocation provides unwanted *args." 1138 elif subprogram.star is not None: 1139 param, default = subprogram.star 1140 if not hasattr(default, "types"): 1141 subprogram.star = param, self.dispatch(default) # NOTE: Review reprocessing. 1142 items.append((param, default.types)) 1143 1144 if dstar_types is not None: 1145 if subprogram.dstar is not None: 1146 param, default = subprogram.dstar 1147 items.append((param, dstar_types)) 1148 else: 1149 raise AnnotationMessage, "Invocation provides unwanted **args." 1150 elif subprogram.dstar is not None: 1151 param, default = subprogram.dstar 1152 if not hasattr(default, "types"): 1153 subprogram.dstar = param, self.dispatch(default) # NOTE: Review reprocessing. 1154 items.append((param, default.types)) 1155 1156 # Record the parameter types. 1157 1158 self.annotate_parameters(subprogram, items) 1159 return subprogram.paramtypes.items() 1160 1161 def make_star_args(self, invocation, subprogram, star_args): 1162 1163 "Make a subprogram which initialises a list containing 'star_args'." 1164 1165 if not hasattr(invocation, "stars"): 1166 invocation.stars = {} 1167 1168 if not invocation.stars.has_key(subprogram.full_name()): 1169 code=[ 1170 StoreTemp( 1171 expr=InvokeFunction( 1172 invocation.original, 1173 expr=LoadAttr( 1174 expr=LoadRef( 1175 ref=self.builtins 1176 ), 1177 name="list", 1178 nstype="module", 1179 ), 1180 args=[], 1181 star=None, 1182 dstar=None 1183 ) 1184 ) 1185 ] 1186 1187 for arg in star_args: 1188 code.append( 1189 InvokeFunction( 1190 invocation.original, 1191 expr=LoadAttr( 1192 expr=LoadTemp(), 1193 name="append" 1194 ), 1195 args=[arg], 1196 star=None, 1197 dstar=None 1198 ) 1199 ) 1200 1201 code += [ 1202 Return(expr=LoadTemp(release=1)) 1203 ] 1204 1205 invocation.stars[subprogram.full_name()] = InvokeBlock( 1206 invocation.original, 1207 produces_result=1, 1208 expr=LoadRef( 1209 ref=Subprogram( 1210 name=None, 1211 returns_value=1, 1212 params=[], 1213 star=None, 1214 dstar=None, 1215 code=code 1216 ) 1217 ) 1218 ) 1219 1220 return invocation.stars[subprogram.full_name()] 1221 1222 def make_dstar_args(self, invocation, subprogram, dstar_args): 1223 1224 """ 1225 Make a subprogram which initialises a dictionary built from the given 1226 'dstar_args'. 1227 """ 1228 1229 if not hasattr(invocation, "dstars"): 1230 invocation.dstars = {} 1231 1232 if not invocation.dstars.has_key(subprogram.full_name()): 1233 code=[ 1234 StoreTemp( 1235 expr=InvokeFunction( 1236 invocation.original, 1237 expr=LoadAttr( 1238 expr=LoadRef( 1239 ref=self.builtins 1240 ), 1241 name="dict", 1242 nstype="module", 1243 ) 1244 ) 1245 ) 1246 ] 1247 1248 for arg, value in dstar_args: 1249 1250 # NOTE: Constant not added to table. 1251 1252 constant = Constant(name=repr(arg), value=arg, namespace=Namespace()) 1253 #constant.namespace.store("__class__", self.get_builtin_instances(invocation, constant.typename)) 1254 code += [ 1255 StoreTemp( 1256 expr=LoadRef( 1257 ref=constant 1258 ), 1259 index="const" 1260 ), 1261 StoreAttr( 1262 lvalue=LoadTemp( 1263 index="const" 1264 ), 1265 name="__class__", 1266 expr=LoadAttr( 1267 expr=LoadRef( 1268 ref=self.builtins 1269 ), 1270 name=constant.typename, 1271 nstype="module", 1272 ) 1273 ), 1274 InvokeFunction( 1275 invocation.original, 1276 expr=LoadAttr( 1277 expr=LoadTemp(), 1278 name="__setitem__" 1279 ), 1280 args=[ 1281 LoadTemp( 1282 index="const", 1283 release=1 1284 ), 1285 value 1286 ] 1287 ) 1288 ] 1289 1290 code += [ 1291 Return(expr=LoadTemp(release=1)) 1292 ] 1293 1294 invocation.dstars[subprogram.full_name()] = InvokeBlock( 1295 invocation.original, 1296 produces_result=1, 1297 expr=LoadRef( 1298 ref=Subprogram( 1299 name=None, 1300 returns_value=1, 1301 params=[], 1302 star=None, 1303 dstar=None, 1304 code=code 1305 ) 1306 ) 1307 ) 1308 1309 return invocation.dstars[subprogram.full_name()] 1310 1311 # Namespace-related abstractions. 1312 1313 class Namespace: 1314 1315 """ 1316 A local namespace which may either relate to a genuine set of function 1317 locals or the initialisation of a structure or module. 1318 """ 1319 1320 def __init__(self): 1321 1322 """ 1323 Initialise the namespace with a mapping of local names to possible 1324 types, a list of return values and of possible returned local 1325 namespaces. The namespace also tracks the "current" types and a mapping 1326 of temporary value names to types. 1327 """ 1328 1329 self.names = {} 1330 self.returns = [] 1331 self.return_locals = [] 1332 self.raises = [] 1333 self.temp = {} 1334 self.types = [] 1335 1336 def set_types(self, types): 1337 1338 "Set the current collection of 'types'." 1339 1340 self.types = types 1341 1342 def add(self, name, types): 1343 1344 "Add to the entry with the given 'name' the specified 'types'." 1345 1346 if self.names.has_key(name): 1347 combine(self.names[name], types) 1348 else: 1349 self.store(name, types) 1350 1351 def store(self, name, types): 1352 1353 "Store in (or associate with) the given 'name' the specified 'types'." 1354 1355 self.names[name] = types 1356 1357 __setitem__ = store 1358 1359 def load(self, name): 1360 1361 "Load the types associated with the given 'name'." 1362 1363 return self.names[name] 1364 1365 __getitem__ = load 1366 1367 def has_key(self, name): 1368 return self.names.has_key(name) 1369 1370 def revoke(self, name, type): 1371 1372 "Revoke from the entry for the given 'name' the specified 'type'." 1373 1374 new_types = self.names[name][:] 1375 new_types.remove(type) 1376 self.names[name] = new_types 1377 1378 def revoke_exception_type(self, type): 1379 1380 "Revoke the given 'type' from the collection of exception types." 1381 1382 self.raises.remove(type) 1383 1384 def revoke_temp_type(self, index, type): 1385 1386 "Revoke from the temporary variable 'index' the given 'type'." 1387 1388 new_types = self.temp[index][-1][:] 1389 new_types.remove(type) 1390 self.temp[index][-1] = new_types 1391 1392 def merge_namespace(self, namespace, everything=1): 1393 1394 """ 1395 Merge items from the given 'namespace' with this namespace. When the 1396 optional 'everything' parameter is set to a false value (unlike the 1397 default), return values and locals snapshots will not be copied to this 1398 namespace. 1399 """ 1400 1401 self.merge_items(namespace.names.items()) 1402 if everything: 1403 combine(self.returns, namespace.returns) 1404 combine(self.return_locals, namespace.return_locals) 1405 combine(self.raises, namespace.raises) 1406 for name, values in namespace.temp.items(): 1407 if values: 1408 if not self.temp.has_key(name) or not self.temp[name]: 1409 self.temp[name] = [[]] 1410 combine(self.temp[name][-1], values[-1]) 1411 1412 def merge_items(self, items): 1413 1414 "Merge the given 'items' with this namespace." 1415 1416 for name, types in items: 1417 self.merge(name, types) 1418 1419 def merge(self, name, types): 1420 1421 "Merge the entry for the given 'name' and 'types' with this namespace." 1422 1423 if not self.names.has_key(name): 1424 self.names[name] = types[:] 1425 else: 1426 existing = self.names[name] 1427 combine(existing, types) 1428 1429 def snapshot(self): 1430 1431 "Make a snapshot of the locals and remember them." 1432 1433 namespace = Namespace() 1434 namespace.merge_namespace(self) 1435 self.return_locals.append(namespace) 1436 1437 def reset(self): 1438 1439 "Reset a namespace in preparation for merging with returned locals." 1440 1441 self.names = {} 1442 1443 def __repr__(self): 1444 return repr(self.names) 1445 1446 class Importer: 1447 1448 "An import machine, searching for and loading modules." 1449 1450 def __init__(self, path=None): 1451 1452 """ 1453 Initialise the importer with the given search 'path' - a list of 1454 directories to search for Python modules. 1455 """ 1456 1457 self.path = path or [os.getcwd()] 1458 self.modules = {} 1459 1460 def find_in_path(self, name): 1461 1462 """ 1463 Find the given module 'name' in the search path, returning None where no 1464 such module could be found, or a 2-tuple from the 'find' method 1465 otherwise. 1466 """ 1467 1468 for d in self.path: 1469 m = self.find(d, name) 1470 if m: return m 1471 return None 1472 1473 def find(self, d, name): 1474 1475 """ 1476 In the directory 'd', find the given module 'name', where 'name' can 1477 either refer to a single file module or to a package. Return None if the 1478 'name' cannot be associated with either a file or a package directory, 1479 or a 2-tuple from '_find_package' or '_find_module' otherwise. 1480 """ 1481 1482 m = self._find_package(d, name) 1483 if m: return m 1484 m = self._find_module(d, name) 1485 if m: return m 1486 return None 1487 1488 def _find_module(self, d, name): 1489 1490 """ 1491 In the directory 'd', find the given module 'name', returning None where 1492 no suitable file exists in the directory, or a 2-tuple consisting of 1493 None (indicating that no package directory is involved) and a filename 1494 indicating the location of the module. 1495 """ 1496 1497 name_py = name + os.extsep + "py" 1498 filename = self._find_file(d, name_py) 1499 if filename: 1500 return None, filename 1501 return None 1502 1503 def _find_package(self, d, name): 1504 1505 """ 1506 In the directory 'd', find the given package 'name', returning None 1507 where no suitable package directory exists, or a 2-tuple consisting of 1508 a directory (indicating the location of the package directory itself) 1509 and a filename indicating the location of the __init__.py module which 1510 declares the package's top-level contents. 1511 """ 1512 1513 filename = self._find_file(d, name) 1514 if filename: 1515 init_py = "__init__" + os.path.extsep + "py" 1516 init_py_filename = self._find_file(filename, init_py) 1517 if init_py_filename: 1518 return filename, init_py_filename 1519 return None 1520 1521 def _find_file(self, d, filename): 1522 1523 """ 1524 Return the filename obtained when searching the directory 'd' for the 1525 given 'filename', or None if no actual file exists for the filename. 1526 """ 1527 1528 filename = os.path.join(d, filename) 1529 if os.path.exists(filename): 1530 return filename 1531 else: 1532 return None 1533 1534 def load(self, name, builtins, alias=None): 1535 1536 """ 1537 Load the module or package with the given 'name' and using the specified 1538 'builtins'. Return an Attribute object referencing the loaded module or 1539 package, or None if no such module or package exists. 1540 """ 1541 1542 path = name.split(".") 1543 m = self.find_in_path(path[0]) 1544 if not m: 1545 return None # NOTE: Import error. 1546 d, filename = m 1547 top = module = self.modules.get(path[0], load(filename, builtins, path[0], self)) 1548 self.modules[path[0]] = module 1549 1550 if len(path) > 1: 1551 path_so_far = path[:1] 1552 for p in path[1:]: 1553 path_so_far.append(p) 1554 m = self.find(d, p) 1555 if not m: 1556 return None # NOTE: Import error. 1557 d, filename = m 1558 module_name = ".".join(path_so_far) 1559 submodule = self.modules.get(module_name, load(filename, builtins, module_name, self)) 1560 self.modules[module_name] = submodule 1561 1562 # Store the submodule within its parent module. 1563 1564 module.namespace[p] = [Attribute(None, submodule)] 1565 module = submodule 1566 1567 if alias: 1568 return Attribute(None, module) 1569 else: 1570 return Attribute(None, top) 1571 1572 def combine(target, additions): 1573 1574 """ 1575 Merge into the 'target' sequence the given 'additions', preventing duplicate 1576 items. 1577 """ 1578 1579 for addition in additions: 1580 if addition not in target: 1581 target.append(addition) 1582 1583 def find_attributes(structure, name): 1584 1585 """ 1586 Find for the given 'structure' all attributes for the given 'name', visiting 1587 base classes where appropriate and returning the attributes in order of 1588 descending precedence for all possible base classes. 1589 1590 The elements in the result list are 2-tuples which contain the attribute and 1591 the structure involved in accessing the attribute. 1592 """ 1593 1594 # First attempt to search the instance/class namespace. 1595 1596 try: 1597 l = structure.namespace.load(name) 1598 attributes = [] 1599 for attribute in l: 1600 attributes.append((attribute, structure)) 1601 1602 # If that does not work, attempt to investigate any class or base classes. 1603 1604 except KeyError: 1605 attributes = [] 1606 1607 # Investigate any instance's implementing class. 1608 1609 if isinstance(structure, Instance): 1610 for attr in structure.namespace.load("__class__"): 1611 cls = attr.type 1612 l = get_attributes(cls, name) 1613 combine(attributes, l) 1614 1615 # Investigate any class's base classes. 1616 1617 elif isinstance(structure, Class): 1618 1619 # If no base classes exist, return an indicator that no attribute 1620 # exists. 1621 1622 if not structure.base_refs: 1623 return [(None, structure)] 1624 1625 # Otherwise, find all possible base classes. 1626 1627 for base_refs in structure.base_refs: 1628 base_attributes = [] 1629 1630 # For each base class, find attributes either in the base 1631 # class or its own base classes. 1632 1633 for base_ref in base_refs: 1634 l = get_attributes(base_ref, name) 1635 combine(base_attributes, l) 1636 1637 combine(attributes, base_attributes) 1638 1639 return attributes 1640 1641 def get_attributes(structure, name): 1642 1643 """ 1644 Return all possible attributes for the given 'structure' having the given 1645 'name', wrapping each attribute in an Attribute object which includes 1646 context information for the attribute access. 1647 1648 The elements in the result list are 2-tuples which contain the attribute and 1649 the structure involved in accessing the attribute. 1650 """ 1651 1652 if isinstance(structure, Attribute): 1653 structure = structure.type 1654 results = [] 1655 for attribute, accessor in find_attributes(structure, name): 1656 1657 # Detect class attribute access via instances. 1658 1659 if attribute is not None and isinstance(structure, Instance) and isinstance(accessor, Class): 1660 attribute = accessor.get_attribute_for_instance(attribute, structure) 1661 1662 # Produce an attribute with the appropriate context. 1663 1664 if attribute is not None and isinstance(structure, Structure): 1665 results.append((Attribute(structure, attribute.type), accessor)) 1666 else: 1667 results.append((attribute, accessor)) 1668 1669 return results 1670 1671 # Convenience functions. 1672 1673 def load(name, builtins=None, module_name=None, importer=None): 1674 1675 """ 1676 Load the module with the given 'name' (which may be a full module path), 1677 using the optional 'builtins' to resolve built-in names, and using the 1678 optional 'importer' to provide a means of finding and loading modules. 1679 """ 1680 1681 module = simplify.simplify(name, builtins is None, module_name) 1682 fixnames.fix(module, builtins) 1683 annotate(module, builtins, importer) 1684 return module 1685 1686 def annotate(module, builtins=None, importer=None): 1687 1688 """ 1689 Annotate the given 'module', also employing the optional 'builtins' module, 1690 if specified. If the optional 'importer' is given, use that to find and load 1691 modules. 1692 """ 1693 1694 annotator = Annotator(importer) 1695 if builtins is not None: 1696 annotator.process(module, builtins) 1697 else: 1698 annotator.process(module) 1699 1700 # vim: tabstop=4 expandtab shiftwidth=4