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