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