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 annotate function: 28 29 annotate(module, builtins) 30 31 The more complicated approach involves obtaining an Annotator: 32 33 annotator = Annotator() 34 35 Then, processing an existing module with it: 36 37 annotator.process(module) 38 39 If a module containing built-in classes and functions has already been 40 annotated, such a module should be passed in as an additional argument: 41 42 annotator.process(module, builtins) 43 """ 44 45 from simplified import * 46 import compiler 47 48 class System: 49 50 """ 51 A class maintaining the state of the annotation system. When the system 52 counter can no longer be incremented by any annotation operation, the 53 system may be considered stable and fully annotated. 54 """ 55 56 def __init__(self): 57 self.count = 0 58 def init(self, node): 59 if not hasattr(node, "types"): 60 node.types = [] 61 def annotate(self, node, types): 62 self.init(node) 63 for type in types: 64 if type not in node.types: 65 node.types.append(type) 66 self.count += 1 67 68 system = System() 69 70 # Exceptions. 71 72 class AnnotationError(SimplifiedError): 73 74 "An error in the annotation process." 75 76 pass 77 78 class AnnotationMessage(Exception): 79 80 "A lesser annotation error." 81 82 pass 83 84 # Annotation. 85 86 class Annotator(Visitor): 87 88 """ 89 The type annotator which traverses the program nodes, typically depth-first, 90 and maintains a record of the current set of types applying to the currently 91 considered operation. Such types are also recorded on the nodes, and a 92 special "system" record is maintained to monitor the level of annotation 93 activity with a view to recognising when no more annotations are possible. 94 95 Throughout the annotation activity, type information consists of lists of 96 Attribute objects where such objects retain information about the context of 97 the type (since a value in the program may be associated with an object or 98 class) and the actual type of the value being manipulated. Upon accessing 99 attribute information on namespaces, additional accessor information is also 100 exchanged - this provides a means of distinguishing between the different 101 types possible when the means of constructing the namespace may depend on 102 run-time behaviour. 103 """ 104 105 def __init__(self): 106 107 "Initialise the visitor." 108 109 Visitor.__init__(self) 110 self.system = system 111 112 # Satisfy visitor issues. 113 114 self.visitor = self 115 116 def process(self, module, builtins=None): 117 118 """ 119 Process the given 'module', using the optional 'builtins' to access 120 built-in classes and functions. 121 """ 122 123 self.subprograms = [] 124 self.current_subprograms = [] 125 self.current_namespaces = [] 126 self.namespace = None 127 self.module = module 128 129 # Give constants their own namespace. 130 131 for value, constant in module.simplifier.constants.items(): 132 constant.namespace = Namespace() 133 134 # Process the module, supplying builtins if possible. 135 136 self.builtins = builtins 137 self.global_namespace = Namespace() 138 139 if builtins is not None: 140 self.builtins_namespace = builtins.namespace 141 else: 142 self.builtins_namespace = self.global_namespace 143 144 return self.process_node(module, self.global_namespace) 145 146 def process_node(self, node, locals): 147 148 """ 149 Process a subprogram or module 'node', indicating the initial 'locals'. 150 Return an annotated subprogram or module. Note that this method may 151 mutate nodes in the original program. 152 """ 153 154 # Record the current subprogram and namespace. 155 156 self.current_subprograms.append(node) 157 158 # Determine the namespace. 159 160 self.current_namespaces.append(self.namespace) 161 self.namespace = locals 162 163 # Add namespace details to any structure involved. 164 165 if getattr(node, "structure", None) is not None: 166 node.structure.namespace = Namespace() 167 168 # Initialise bases where appropriate. 169 170 if hasattr(node.structure, "bases"): 171 base_refs = [] 172 for base in node.structure.bases: 173 self.dispatch(base) 174 base_refs.append(self.namespace.types) 175 node.structure.base_refs = base_refs 176 177 # Dispatch to the code itself. 178 179 node.namespace = self.namespace 180 result = self.dispatch(node) 181 result.namespace = self.namespace 182 183 # Obtain the return values. 184 185 self.last_returns = self.namespace.returns 186 self.last_raises = self.namespace.raises 187 self.returned_locals = self.namespace.return_locals 188 189 # Restore the previous subprogram and namespace. 190 191 self.namespace = self.current_namespaces.pop() 192 self.current_subprograms.pop() 193 194 return result 195 196 def annotate(self, node, types=None): 197 198 """ 199 Annotate the given 'node' in the system, using either the optional 200 'types' or the namespace's current type information. 201 """ 202 203 self.system.annotate(node, types or self.namespace.types) 204 205 # Visitor methods. 206 207 def default(self, node): 208 209 """ 210 Process the given 'node', given that it does not have a specific 211 handler. 212 """ 213 214 raise AnnotationMessage, "Node '%s' not supported." % node 215 216 def dispatch(self, node, *args): 217 try: 218 return Visitor.dispatch(self, node, *args) 219 except AnnotationError, exc: 220 exc.add(node) 221 raise 222 except AnnotationMessage, exc: 223 raise AnnotationError(exc, node) 224 225 # Program structure/control-flow. 226 227 def visitAssign(self, assign): 228 assign.code = self.dispatches(assign.code) 229 return assign 230 231 def visitConditional(self, conditional): 232 233 # Conditionals keep local namespace changes isolated. 234 # With Return nodes inside the body/else sections, the changes are 235 # communicated to the caller. 236 237 is_module = self.namespace is self.module.namespace 238 239 # Where the test is closely associated with the body, save the namespace 240 # before entering the test. 241 242 if conditional.isolate_test: 243 saved_namespace = self.namespace 244 self.namespace = Namespace() 245 if is_module: 246 self.module.namespace = self.namespace 247 self.namespace.merge_namespace(saved_namespace) 248 249 conditional.test = self.dispatch(conditional.test) 250 251 # Where the test may affect the body and the else clause, save the 252 # namespace after processing the test. 253 254 if not conditional.isolate_test: 255 saved_namespace = self.namespace 256 self.namespace = Namespace() 257 if is_module: 258 self.module.namespace = self.namespace 259 self.namespace.merge_namespace(saved_namespace) 260 261 # Process the body clause. 262 263 conditional.body = self.dispatches(conditional.body) 264 body_namespace = self.namespace 265 266 # Use the saved namespace as a template for the else clause. 267 268 self.namespace = Namespace() 269 if is_module: 270 self.module.namespace = self.namespace 271 self.namespace.merge_namespace(saved_namespace) 272 273 # Process the else clause. 274 275 conditional.else_ = self.dispatches(conditional.else_) 276 else_namespace = self.namespace 277 278 # Merge the body and else namespaces. 279 280 self.namespace = Namespace() 281 if is_module: 282 self.module.namespace = self.namespace 283 self.namespace.merge_namespace(body_namespace) 284 self.namespace.merge_namespace(else_namespace) 285 286 return conditional 287 288 def visitModule(self, module): 289 module.code = self.dispatches(module.code) 290 return module 291 292 def visitPass(self, pass_): 293 return pass_ 294 295 def visitSubprogram(self, subprogram): 296 subprogram.code = self.dispatches(subprogram.code) 297 return subprogram 298 299 def visitTry(self, try_): 300 is_module = self.namespace is self.module.namespace 301 302 try_.body = self.dispatches(try_.body) 303 304 # Save the namespace from the body. 305 306 body_namespace = Namespace() 307 body_namespace.merge_namespace(self.namespace) 308 309 # Process the handler. 310 311 if hasattr(try_, "handler"): 312 try_.handler = self.dispatches(try_.handler) 313 314 # Save the namespace from the handler. 315 316 handler_namespace = Namespace() 317 handler_namespace.merge_namespace(self.namespace) 318 319 # Remember the raised exceptions encountered so far. 320 321 raises = self.namespace.raises 322 323 # Process the else clause. 324 325 if hasattr(try_, "else_"): 326 327 # Restore the body namespace for the else clause. 328 329 self.namespace = body_namespace 330 if is_module: 331 self.module.namespace = self.namespace 332 333 # Empty the raised exceptions for the else clause. 334 335 self.namespace.raises = [] 336 try_.else_ = self.dispatches(try_.else_) 337 self.namespace.raises = raises 338 339 # Merge the namespaces. 340 341 self.namespace = Namespace() 342 if is_module: 343 self.module.namespace = self.namespace 344 self.namespace.merge_namespace(body_namespace) 345 self.namespace.merge_namespace(handler_namespace) 346 347 # Process the finally clause, if any. 348 349 try_.finally_ = self.dispatches(try_.finally_) 350 return try_ 351 352 # Namespace operations. 353 354 def visitCheckExc(self, checkexc): 355 checkexc.expr = self.dispatch(checkexc.expr) 356 expr_types = self.namespace.types 357 choice_types = [] 358 choices = [] 359 for choice in checkexc.choices: 360 choices.append(self.dispatch(choice)) 361 choice_types += self.namespace.types 362 for expr_type in expr_types: 363 if expr_type.type.get_class() not in choice_types: 364 self._prune_non_accesses(checkexc.expr, expr_type) 365 return checkexc 366 367 def visitLoadAttr(self, loadattr): 368 loadattr.expr = self.dispatch(loadattr.expr) 369 types = [] 370 non_accesses = [] 371 accesses = {} 372 for attr in self.namespace.types: 373 attributes = get_attributes(attr.type, loadattr.name) 374 if not attributes: 375 if not attr.type in non_accesses: 376 non_accesses.append(attr) 377 378 # Revoke this type from any name involved. 379 380 self._prune_non_accesses(loadattr.expr, attr) 381 382 for attribute, accessor in attributes: 383 if attribute is not None: 384 types.append(attribute) 385 if not accesses.has_key(attr.type): 386 accesses[attr.type] = [] 387 if not (attribute, accessor) in accesses[attr.type]: 388 accesses[attr.type].append((attribute, accessor)) 389 else: 390 if not attr in non_accesses: 391 non_accesses.append(attr) 392 393 # Revoke this type from any name involved. 394 395 self._prune_non_accesses(loadattr.expr, attr) 396 397 if not types: 398 print "No attribute found for", loadattr.name, "given", self.namespace.types 399 self.namespace.set_types(types) 400 loadattr.non_accesses = non_accesses 401 loadattr.accesses = accesses 402 self.annotate(loadattr) 403 return loadattr 404 405 def _prune_non_accesses(self, expr, attr): 406 if isinstance(expr, LoadName): 407 self.namespace.revoke(expr.name, attr) 408 elif isinstance(expr, LoadAttr): 409 for expr_attr in expr.expr.types: 410 if hasattr(expr_attr.type, "namespace"): 411 expr_attr.type.namespace.revoke(expr.name, attr) 412 elif isinstance(expr, LoadExc): 413 self.namespace.revoke_exception_type(attr) 414 415 def visitLoadExc(self, loadexc): 416 self.namespace.types = self.namespace.raises[:] 417 self.annotate(loadexc) 418 return loadexc 419 420 def visitLoadName(self, loadname): 421 self.namespace.set_types(self.namespace.load(loadname.name)) 422 result = loadname 423 self.annotate(result) 424 return result 425 426 def visitLoadRef(self, loadref): 427 self.namespace.set_types([Attribute(None, loadref.ref)]) 428 self.annotate(loadref) 429 return loadref 430 431 def visitLoadTemp(self, loadtemp): 432 index = getattr(loadtemp, "index", None) 433 try: 434 if getattr(loadtemp, "release", 0): 435 self.namespace.set_types(self.namespace.temp[index].pop()) 436 else: 437 self.namespace.set_types(self.namespace.temp[index][-1]) 438 except KeyError: 439 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 440 self.annotate(loadtemp) 441 return loadtemp 442 443 def visitNot(self, not_): 444 not_.expr = self.dispatch(not_.expr) 445 return not_ 446 447 def visitRaise(self, raise_): 448 if getattr(raise_, "traceback", None) is not None: 449 raise_.traceback = self.dispatch(raise_.traceback) 450 raise_.expr = self.dispatch(raise_.expr) 451 452 # Handle bare name exceptions by converting any classes to instances. 453 454 if not isinstance(raise_.expr, InvokeFunction): 455 raise_.pos_args = [] 456 raise_.kw_args = {} 457 raise_.star = None 458 raise_.dstar = None 459 types = [] 460 for attr in self.namespace.types: 461 if isinstance(attr.type, Class): 462 self._visitInvoke(raise_, [attr], have_args=0) 463 types += self.namespace.types 464 else: 465 types = self.namespace.types 466 467 combine(self.namespace.raises, types) 468 return raise_ 469 470 def visitReleaseTemp(self, releasetemp): 471 index = getattr(releasetemp, "index", None) 472 try: 473 self.namespace.temp[index].pop() 474 except KeyError: 475 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 476 except IndexError: 477 pass #raise AnnotationMessage, "Temporary store index '%s' is empty." % index 478 return releasetemp 479 480 def visitReturn(self, return_): 481 if hasattr(return_, "expr"): 482 return_.expr = self.dispatch(return_.expr) 483 combine(self.namespace.returns, self.namespace.types) 484 self.annotate(return_) 485 self.namespace.snapshot() 486 return return_ 487 488 visitReturnFromBlock = visitReturn 489 visitReturnFromFunction = visitReturn 490 491 def visitStoreAttr(self, storeattr): 492 storeattr.expr = self.dispatch(storeattr.expr) 493 expr = self.namespace.types 494 storeattr.lvalue = self.dispatch(storeattr.lvalue) 495 writes = {} 496 non_writes = [] 497 for attr in self.namespace.types: 498 if attr is None: 499 if not attr in non_writes: 500 non_writes.append(attr) 501 continue 502 attr.type.namespace.add(storeattr.name, expr) 503 writes[attr.type] = attr.type.namespace.load(storeattr.name) 504 if not writes: 505 print "Unable to store attribute", storeattr.name, "given", self.namespace.types 506 storeattr.writes = writes 507 storeattr.non_writes = non_writes 508 return storeattr 509 510 def visitStoreName(self, storename): 511 storename.expr = self.dispatch(storename.expr) 512 self.namespace.store(storename.name, self.namespace.types) 513 return storename 514 515 def visitStoreTemp(self, storetemp): 516 storetemp.expr = self.dispatch(storetemp.expr) 517 index = getattr(storetemp, "index", None) 518 if not self.namespace.temp.has_key(index): 519 self.namespace.temp[index] = [] 520 self.namespace.temp[index].append(self.namespace.types) 521 return storetemp 522 523 # Invocations are a chapter of their own. 524 525 def visitInvokeBlock(self, invoke): 526 527 # First find the callables. 528 529 invoke.expr = self.dispatch(invoke.expr) 530 invocation_types = self.namespace.types 531 return self._visitInvoke(invoke, invocation_types, have_args=0) 532 533 def visitInvokeFunction(self, invoke): 534 535 # First find the callables. 536 537 invoke.expr = self.dispatch(invoke.expr) 538 invocation_types = self.namespace.types 539 540 # Invocation processing starts with making sure that the arguments have 541 # been processed. 542 543 return self._visitInvoke(invoke, invocation_types, have_args=self.process_args(invoke)) 544 545 def _visitInvoke(self, invoke, invocation_types, have_args): 546 547 # Now locate and invoke the subprogram. This can be complicated because 548 # the target may be a class or object, and there may be many different 549 # related subprograms. 550 551 invocations = [] 552 553 # Visit each callable in turn, finding subprograms. 554 555 for attr in invocation_types: 556 557 # Deal with class invocations by providing instance objects. 558 # Here, each class is queried for the __init__ method, which may 559 # exist for some combinations of classes in a hierarchy but not for 560 # others. 561 562 if isinstance(attr.type, Class): 563 attributes = get_attributes(attr.type, "__init__") 564 565 # Deal with object invocations by using __call__ methods. 566 567 elif isinstance(attr.type, Instance): 568 attributes = get_attributes(attr.type, "__call__") 569 570 # Normal functions or methods are more straightforward. 571 # Here, we model them using an attribute with no context and with 572 # no associated accessor. 573 574 else: 575 attributes = [(attr, None)] 576 577 # Inspect each attribute and extract the subprogram. 578 579 for attribute, accessor in attributes: 580 581 # If a class is involved, presume that it must create a new 582 # object. 583 584 if isinstance(attr.type, Class): 585 586 # Instantiate the class. 587 # NOTE: Should probably only allocate a single instance. 588 589 instance = self.new_instance(invoke, "new", attr.type.full_name(), attr.type) 590 591 # For instantiations, switch the context. 592 593 if attribute is not None: 594 attribute = Attribute(instance, attribute.type) 595 596 # Skip cases where no callable is found. 597 598 if attribute is not None: 599 600 # If a subprogram is defined, invoke it. 601 602 self.invoke_subprogram(invoke, attribute) 603 if attribute.type not in invocations: 604 invocations.append(attribute.type) 605 606 elif not isinstance(attr.type, Class): 607 print "Invocation type is None for", accessor 608 609 else: 610 611 # Test to see if no arguments were supplied in cases where no 612 # initialiser was found. 613 614 if have_args: 615 raise AnnotationMessage, "No initialiser found for '%s' with arguments." % attr.type 616 617 # Special case: initialisation. 618 619 if isinstance(attr.type, Class): 620 621 # Associate the instance with the result of this invocation. 622 623 self.namespace.set_types([Attribute(None, instance)]) 624 self.annotate(invoke) 625 626 # Remember the invocations that were found, along with the return type 627 # information. 628 629 invoke.invocations = invocations 630 self.namespace.set_types(getattr(invoke, "types", [])) 631 return invoke 632 633 # Utility methods. 634 635 def new_instance(self, node, reason, target, type): 636 637 "Create, on the given 'node', a new instance with the given 'type'." 638 639 if not hasattr(node, "instances"): 640 node.instances = {} 641 642 if not node.instances.has_key((reason, target, type)): 643 644 # Insist on a single instance per type. 645 # NOTE: Strategy-dependent instantiation. 646 647 if len(type.instances) == 0: 648 instance = Instance() 649 instance.namespace = Namespace() 650 instance.namespace.store("__class__", [Attribute(None, type)]) 651 type.instances.append(instance) 652 else: 653 instance = type.instances[0] 654 655 #instance = Instance() 656 #instance.namespace = Namespace() 657 #instance.namespace.store("__class__", [Attribute(None, type)]) 658 #type.instances.append(instance) 659 660 node.instances[(reason, target, type)] = instance 661 662 return node.instances[(reason, target, type)] 663 664 def invoke_subprogram(self, invoke, subprogram): 665 666 "Invoke using the given 'invoke' node the given 'subprogram'." 667 668 # Test to see if anything has changed. 669 670 if hasattr(invoke, "syscount") and invoke.syscount == self.system.count: 671 return 672 673 # Remember the state of the system. 674 675 else: 676 invoke.syscount = self.system.count 677 678 # Test for context information, making it into a real attribute. 679 680 if subprogram.context is not None: 681 context = Attribute(None, subprogram.context) 682 target = subprogram.type 683 else: 684 context = None 685 target = subprogram.type 686 687 # Provide the correct namespace for the invocation. 688 689 if getattr(invoke, "share_locals", 0): 690 namespace = Namespace() 691 namespace.merge_namespace(self.namespace, everything=0) 692 using_module_namespace = self.namespace is self.module.namespace 693 elif getattr(target, "structure", None): 694 namespace = Namespace() 695 using_module_namespace = 0 696 else: 697 items = self.make_items(invoke, target, context) 698 namespace = self.make_namespace(items) 699 using_module_namespace = 0 700 701 # Process the subprogram. 702 # In order to keep global accesses working, the module namespace must be 703 # adjusted. 704 705 if using_module_namespace: 706 self.module.namespace = namespace 707 708 self.process_node(target, namespace) 709 710 # NOTE: Improve and verify this. 711 # If the invocation returns a value, acquire the return types. 712 713 if getattr(target, "returns_value", 0): 714 self.namespace.set_types(self.last_returns) 715 self.annotate(invoke) 716 717 # If it is a normal block, merge the locals. 718 # This can happen in addition to the above because for things like 719 # logical expressions, the namespace can be modified whilst values are 720 # returned as results. 721 722 if getattr(invoke, "share_locals", 0): 723 self.namespace.reset() 724 725 # Merge the locals snapshots. 726 727 for locals in self.returned_locals: 728 729 # For blocks returning values (such as operations), do not merge 730 # snapshots or results. 731 732 if getattr(target, "returns_value", 0): 733 self.namespace.merge_namespace(locals, everything=0) 734 735 # For blocks not returning values (such as loops), merge 736 # snapshots and results since they contain details of genuine 737 # returns. 738 739 else: 740 self.namespace.merge_namespace(locals) 741 742 # Incorporate any raised exceptions. 743 744 combine(self.namespace.raises, self.last_raises) 745 746 # In order to keep global accesses working, the module namespace must be 747 # adjusted. 748 749 if using_module_namespace: 750 self.module.namespace = self.namespace 751 752 def process_args(self, invocation): 753 754 """ 755 Process the arguments associated with an 'invocation'. Return whether 756 any arguments were processed. 757 """ 758 759 invocation.pos_args = self.dispatches(invocation.pos_args) 760 invocation.kw_args = self.dispatch_dict(invocation.kw_args) 761 762 # Get type information for star and dstar arguments. 763 764 if invocation.star is not None: 765 param, default = invocation.star 766 default = self.dispatch(default) 767 invocation.star = param, default 768 769 if invocation.dstar is not None: 770 param, default = invocation.dstar 771 default = self.dispatch(default) 772 invocation.dstar = param, default 773 774 if invocation.pos_args or invocation.kw_args or invocation.star or invocation.dstar: 775 return 1 776 else: 777 return 0 778 779 def make_items(self, invocation, subprogram, context): 780 781 """ 782 Make an items mapping for the 'invocation' of the 'subprogram' using the 783 given 'context' (which may be None). 784 """ 785 786 if context is not None: 787 pos_args = [Self(context)] + invocation.pos_args 788 else: 789 pos_args = invocation.pos_args 790 kw_args = invocation.kw_args 791 792 # Sort the arguments into positional and keyword arguments. 793 794 params = subprogram.params 795 items = [] 796 star_args = [] 797 798 # Match each positional argument, taking excess arguments as star args. 799 800 for arg in pos_args: 801 if params: 802 param, default = params[0] 803 if arg is None: 804 arg = default 805 if hasattr(arg, "types"): 806 items.append((param, arg.types)) 807 else: 808 items.append((param, [])) # Annotation has not succeeded. 809 params = params[1:] 810 else: 811 star_args.append(arg) 812 813 # Collect the remaining defaults. 814 815 while params: 816 param, default = params[0] 817 if kw_args.has_key(param): 818 arg = kw_args[param] 819 del kw_args[param] 820 elif default is not None: 821 arg = self.dispatch(default) 822 else: 823 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) 824 if hasattr(arg, "types"): 825 items.append((param, arg.types)) 826 else: 827 items.append((param, [])) # Annotation has not succeeded. 828 params = params[1:] 829 830 dstar_args = kw_args.values() 831 832 # Construct temporary objects. 833 834 if star_args: 835 star_invocation = self.make_star_args(invocation, subprogram, star_args) 836 self.dispatch(star_invocation) 837 star_types = star_invocation.types 838 else: 839 star_types = None 840 841 if dstar_args: 842 dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args) # NOTE: To be written! 843 self.dispatch(dstar_invocation) 844 dstar_types = dstar_invocation.types 845 else: 846 dstar_types = None 847 848 # NOTE: Merge the objects properly. 849 850 star_types = star_types or invocation.star and invocation.star.types 851 dstar_types = dstar_types or invocation.dstar and invocation.dstar.types 852 853 # Add star and dstar. 854 855 if star_types is not None: 856 if subprogram.star is not None: 857 param, default = subprogram.star 858 items.append((param, star_types)) 859 else: 860 raise AnnotationMessage, "Invocation provides unwanted *args." 861 elif subprogram.star is not None: 862 param, default = subprogram.star 863 arg = self.dispatch(default) # NOTE: Review reprocessing. 864 items.append((param, arg.types)) 865 866 if dstar_types is not None: 867 if subprogram.dstar is not None: 868 param, default = subprogram.dstar 869 items.append((param, dstar_types)) 870 else: 871 raise AnnotationMessage, "Invocation provides unwanted **args." 872 elif subprogram.dstar is not None: 873 param, default = subprogram.dstar 874 arg = self.dispatch(default) # NOTE: Review reprocessing. 875 items.append((param, arg.types)) 876 877 # Record the parameter types. 878 879 if not hasattr(subprogram, "paramtypes"): 880 subprogram.paramtypes = {} 881 882 for param, types in items: 883 if not subprogram.paramtypes.has_key(param): 884 subprogram.paramtypes[param] = [] 885 combine(subprogram.paramtypes[param], types) 886 887 return items 888 889 def make_star_args(self, invocation, subprogram, star_args): 890 891 "Make a subprogram which initialises a list containing 'star_args'." 892 893 if not hasattr(invocation, "stars"): 894 invocation.stars = {} 895 896 if not invocation.stars.has_key(subprogram.full_name()): 897 code=[ 898 StoreTemp( 899 expr=InvokeFunction( 900 expr=LoadAttr( 901 expr=LoadRef( 902 ref=self.builtins 903 ), 904 name="list", 905 nstype="module", 906 ), 907 args=[], 908 star=None, 909 dstar=None 910 ) 911 ) 912 ] 913 914 for arg in star_args: 915 code.append( 916 InvokeFunction( 917 expr=LoadAttr( 918 expr=LoadTemp(), 919 name="append" 920 ), 921 args=[arg], 922 star=None, 923 dstar=None 924 ) 925 ) 926 927 code += [ 928 Return(expr=LoadTemp(release=1)) 929 ] 930 931 invocation.stars[subprogram.full_name()] = InvokeBlock( 932 produces_result=1, 933 expr=LoadRef( 934 ref=Subprogram( 935 name=None, 936 returns_value=1, 937 params=[], 938 star=None, 939 dstar=None, 940 code=code 941 ) 942 ) 943 ) 944 945 return invocation.stars[subprogram.full_name()] 946 947 def make_namespace(self, items): 948 namespace = Namespace() 949 namespace.merge_items(items) 950 return namespace 951 952 # Namespace-related abstractions. 953 954 class Namespace: 955 956 """ 957 A local namespace which may either relate to a genuine set of function 958 locals or the initialisation of a structure or module. 959 """ 960 961 def __init__(self): 962 963 """ 964 Initialise the namespace with a mapping of local names to possible 965 types, a list of return values and of possible returned local 966 namespaces. The namespace also tracks the "current" types and a mapping 967 of temporary value names to types. 968 """ 969 970 self.names = {} 971 self.returns = [] 972 self.return_locals = [] 973 self.raises = [] 974 self.temp = {} 975 self.types = [] 976 977 def set_types(self, types): 978 self.types = types 979 980 def add(self, name, types): 981 if self.names.has_key(name): 982 combine(self.names[name], types) 983 else: 984 self.store(name, types) 985 986 def store(self, name, types): 987 self.names[name] = types 988 989 __setitem__ = store 990 991 def load(self, name): 992 return self.names[name] 993 994 __getitem__ = load 995 996 def revoke(self, name, type): 997 self.names[name].remove(type) 998 999 def revoke_exception_type(self, type): 1000 self.raises.remove(type) 1001 1002 def merge_namespace(self, namespace, everything=1): 1003 self.merge_items(namespace.names.items()) 1004 if everything: 1005 combine(self.returns, namespace.returns) 1006 combine(self.return_locals, namespace.return_locals) 1007 combine(self.raises, namespace.raises) 1008 for name, values in namespace.temp.items(): 1009 if values: 1010 if not self.temp.has_key(name) or not self.temp[name]: 1011 self.temp[name] = [[]] 1012 combine(self.temp[name][-1], values[-1]) 1013 1014 def merge_items(self, items): 1015 for name, types in items: 1016 self.merge(name, types) 1017 1018 def merge(self, name, types): 1019 if not self.names.has_key(name): 1020 self.names[name] = types[:] 1021 else: 1022 existing = self.names[name] 1023 combine(existing, types) 1024 1025 def snapshot(self): 1026 1027 "Make a snapshot of the locals and remember them." 1028 1029 namespace = Namespace() 1030 namespace.merge_namespace(self) 1031 self.return_locals.append(namespace) 1032 1033 def reset(self): 1034 1035 "Reset a namespace in preparation for merging with returned locals." 1036 1037 self.names = {} 1038 1039 def __repr__(self): 1040 return repr(self.names) 1041 1042 class Attribute: 1043 1044 """ 1045 An attribute abstraction, indicating the type of the attribute along with 1046 its context or origin. 1047 """ 1048 1049 def __init__(self, context, type): 1050 self.context = context 1051 self.type = type 1052 1053 def __eq__(self, other): 1054 return hasattr(other, "type") and other.type == self.type or other == self.type 1055 1056 def __repr__(self): 1057 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 1058 1059 class Self: 1060 1061 """ 1062 A program node encapsulating object/context information in an argument list. 1063 This is not particularly like Attribute, Class, Instance or other such 1064 things, since it actually appears in the program representation. 1065 """ 1066 1067 def __init__(self, attribute): 1068 self.types = [attribute] 1069 1070 def combine(target, additions): 1071 1072 """ 1073 Merge into the 'target' sequence the given 'additions', preventing duplicate 1074 items. 1075 """ 1076 1077 for addition in additions: 1078 if addition not in target: 1079 target.append(addition) 1080 1081 def find_attributes(structure, name): 1082 1083 """ 1084 Find for the given 'structure' all attributes for the given 'name', visiting 1085 base classes where appropriate and returning the attributes in order of 1086 descending precedence for all possible base classes. 1087 1088 The elements in the result list are 2-tuples which contain the attribute and 1089 the structure involved in accessing the attribute. 1090 """ 1091 1092 # First attempt to search the instance/class namespace. 1093 1094 try: 1095 l = structure.namespace.load(name) 1096 attributes = [] 1097 for attribute in l: 1098 attributes.append((attribute, structure)) 1099 1100 # If that does not work, attempt to investigate any class or base classes. 1101 1102 except KeyError: 1103 attributes = [] 1104 1105 # Investigate any instance's implementing class. 1106 1107 if isinstance(structure, Instance): 1108 for attr in structure.namespace.load("__class__"): 1109 cls = attr.type 1110 l = get_attributes(cls, name) 1111 combine(attributes, l) 1112 1113 # Investigate any class's base classes. 1114 1115 elif isinstance(structure, Class): 1116 1117 # If no base classes exist, return an indicator that no attribute 1118 # exists. 1119 1120 if not structure.base_refs: 1121 return [(None, structure)] 1122 1123 # Otherwise, find all possible base classes. 1124 1125 for base_refs in structure.base_refs: 1126 base_attributes = [] 1127 1128 # For each base class, find attributes either in the base 1129 # class or its own base classes. 1130 1131 for base_ref in base_refs: 1132 l = get_attributes(base_ref, name) 1133 combine(base_attributes, l) 1134 1135 combine(attributes, base_attributes) 1136 1137 return attributes 1138 1139 def get_attributes(structure, name): 1140 1141 """ 1142 Return all possible attributes for the given 'structure' having the given 1143 'name', wrapping each attribute in an Attribute object which includes 1144 context information for the attribute access. 1145 1146 The elements in the result list are 2-tuples which contain the attribute and 1147 the structure involved in accessing the attribute. 1148 """ 1149 1150 if isinstance(structure, Attribute): 1151 structure = structure.type 1152 results = [] 1153 for attribute, accessor in find_attributes(structure, name): 1154 if attribute is not None and isinstance(structure, Structure): 1155 results.append((Attribute(structure, attribute.type), accessor)) 1156 else: 1157 results.append((attribute, accessor)) 1158 return results 1159 1160 # Convenience functions. 1161 1162 def annotate(module, builtins=None): 1163 1164 """ 1165 Annotate the given 'module', also employing the optional 'builtins' module, 1166 if specified. 1167 """ 1168 1169 annotator = Annotator() 1170 if builtins is not None: 1171 annotator.process(module, builtins) 1172 else: 1173 annotator.process(module) 1174 1175 def annotate_all(modules, builtins): 1176 annotate(builtins) 1177 for module in modules: 1178 annotate(module, builtins) 1179 1180 # vim: tabstop=4 expandtab shiftwidth=4