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 node.instances[(reason, target, type)] = instance 656 657 return node.instances[(reason, target, type)] 658 659 def invoke_subprogram(self, invoke, subprogram): 660 661 "Invoke using the given 'invoke' node the given 'subprogram'." 662 663 # Test to see if anything has changed. 664 665 if hasattr(invoke, "syscount") and invoke.syscount == self.system.count: 666 return 667 668 # Remember the state of the system. 669 670 else: 671 invoke.syscount = self.system.count 672 673 # Test for context information, making it into a real attribute. 674 675 if subprogram.context is not None: 676 context = Attribute(None, subprogram.context) 677 target = subprogram.type 678 else: 679 context = None 680 target = subprogram.type 681 682 # Provide the correct namespace for the invocation. 683 684 if getattr(invoke, "share_locals", 0): 685 namespace = Namespace() 686 namespace.merge_namespace(self.namespace, everything=0) 687 using_module_namespace = self.namespace is self.module.namespace 688 elif getattr(target, "structure", None): 689 namespace = Namespace() 690 using_module_namespace = 0 691 else: 692 items = self.make_items(invoke, target, context) 693 namespace = self.make_namespace(items) 694 using_module_namespace = 0 695 696 # Process the subprogram. 697 # In order to keep global accesses working, the module namespace must be 698 # adjusted. 699 700 if using_module_namespace: 701 self.module.namespace = namespace 702 703 self.process_node(target, namespace) 704 705 # NOTE: Improve and verify this. 706 # If the invocation returns a value, acquire the return types. 707 708 if getattr(target, "returns_value", 0): 709 self.namespace.set_types(self.last_returns) 710 self.annotate(invoke) 711 712 # If it is a normal block, merge the locals. 713 # This can happen in addition to the above because for things like 714 # logical expressions, the namespace can be modified whilst values are 715 # returned as results. 716 717 if getattr(invoke, "share_locals", 0): 718 self.namespace.reset() 719 720 # Merge the locals snapshots. 721 722 for locals in self.returned_locals: 723 724 # For blocks returning values (such as operations), do not merge 725 # snapshots or results. 726 727 if getattr(target, "returns_value", 0): 728 self.namespace.merge_namespace(locals, everything=0) 729 730 # For blocks not returning values (such as loops), merge 731 # snapshots and results since they contain details of genuine 732 # returns. 733 734 else: 735 self.namespace.merge_namespace(locals) 736 737 # Incorporate any raised exceptions. 738 739 combine(self.namespace.raises, self.last_raises) 740 741 # In order to keep global accesses working, the module namespace must be 742 # adjusted. 743 744 if using_module_namespace: 745 self.module.namespace = self.namespace 746 747 def process_args(self, invocation): 748 749 """ 750 Process the arguments associated with an 'invocation'. Return whether 751 any arguments were processed. 752 """ 753 754 invocation.pos_args = self.dispatches(invocation.pos_args) 755 invocation.kw_args = self.dispatch_dict(invocation.kw_args) 756 757 # Get type information for star and dstar arguments. 758 759 if invocation.star is not None: 760 param, default = invocation.star 761 default = self.dispatch(default) 762 invocation.star = param, default 763 764 if invocation.dstar is not None: 765 param, default = invocation.dstar 766 default = self.dispatch(default) 767 invocation.dstar = param, default 768 769 if invocation.pos_args or invocation.kw_args or invocation.star or invocation.dstar: 770 return 1 771 else: 772 return 0 773 774 def make_items(self, invocation, subprogram, context): 775 776 """ 777 Make an items mapping for the 'invocation' of the 'subprogram' using the 778 given 'context' (which may be None). 779 """ 780 781 if context is not None: 782 pos_args = [Self(context)] + invocation.pos_args 783 else: 784 pos_args = invocation.pos_args 785 kw_args = invocation.kw_args 786 787 # Sort the arguments into positional and keyword arguments. 788 789 params = subprogram.params 790 items = [] 791 star_args = [] 792 793 # Match each positional argument, taking excess arguments as star args. 794 795 for arg in pos_args: 796 if params: 797 param, default = params[0] 798 if arg is None: 799 arg = default 800 if hasattr(arg, "types"): 801 items.append((param, arg.types)) 802 else: 803 items.append((param, [])) # Annotation has not succeeded. 804 params = params[1:] 805 else: 806 star_args.append(arg) 807 808 # Collect the remaining defaults. 809 810 while params: 811 param, default = params[0] 812 if kw_args.has_key(param): 813 arg = kw_args[param] 814 del kw_args[param] 815 elif default is not None: 816 arg = self.dispatch(default) 817 else: 818 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) 819 if hasattr(arg, "types"): 820 items.append((param, arg.types)) 821 else: 822 items.append((param, [])) # Annotation has not succeeded. 823 params = params[1:] 824 825 dstar_args = kw_args.values() 826 827 # Construct temporary objects. 828 829 if star_args: 830 star_invocation = self.make_star_args(invocation, subprogram, star_args) 831 self.dispatch(star_invocation) 832 star_types = star_invocation.types 833 else: 834 star_types = None 835 836 if dstar_args: 837 dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args) # NOTE: To be written! 838 self.dispatch(dstar_invocation) 839 dstar_types = dstar_invocation.types 840 else: 841 dstar_types = None 842 843 # NOTE: Merge the objects properly. 844 845 star_types = star_types or invocation.star and invocation.star.types 846 dstar_types = dstar_types or invocation.dstar and invocation.dstar.types 847 848 # Add star and dstar. 849 850 if star_types is not None: 851 if subprogram.star is not None: 852 param, default = subprogram.star 853 items.append((param, star_types)) 854 else: 855 raise AnnotationMessage, "Invocation provides unwanted *args." 856 elif subprogram.star is not None: 857 param, default = subprogram.star 858 arg = self.dispatch(default) # NOTE: Review reprocessing. 859 items.append((param, arg.types)) 860 861 if dstar_types is not None: 862 if subprogram.dstar is not None: 863 param, default = subprogram.dstar 864 items.append((param, dstar_types)) 865 else: 866 raise AnnotationMessage, "Invocation provides unwanted **args." 867 elif subprogram.dstar is not None: 868 param, default = subprogram.dstar 869 arg = self.dispatch(default) # NOTE: Review reprocessing. 870 items.append((param, arg.types)) 871 872 # Record the parameter types. 873 874 if not hasattr(subprogram, "paramtypes"): 875 subprogram.paramtypes = {} 876 877 for param, types in items: 878 if not subprogram.paramtypes.has_key(param): 879 subprogram.paramtypes[param] = [] 880 combine(subprogram.paramtypes[param], types) 881 882 return items 883 884 def make_star_args(self, invocation, subprogram, star_args): 885 886 "Make a subprogram which initialises a list containing 'star_args'." 887 888 if not hasattr(invocation, "stars"): 889 invocation.stars = {} 890 891 if not invocation.stars.has_key(subprogram.full_name()): 892 code=[ 893 StoreTemp( 894 expr=InvokeFunction( 895 expr=LoadAttr( 896 expr=LoadRef( 897 ref=self.builtins 898 ), 899 name="list", 900 nstype="module", 901 ), 902 args=[], 903 star=None, 904 dstar=None 905 ) 906 ) 907 ] 908 909 for arg in star_args: 910 code.append( 911 InvokeFunction( 912 expr=LoadAttr( 913 expr=LoadTemp(), 914 name="append" 915 ), 916 args=[arg], 917 star=None, 918 dstar=None 919 ) 920 ) 921 922 code += [ 923 Return(expr=LoadTemp(release=1)) 924 ] 925 926 invocation.stars[subprogram.full_name()] = InvokeBlock( 927 produces_result=1, 928 expr=LoadRef( 929 ref=Subprogram( 930 name=None, 931 returns_value=1, 932 params=[], 933 star=None, 934 dstar=None, 935 code=code 936 ) 937 ) 938 ) 939 940 return invocation.stars[subprogram.full_name()] 941 942 def make_namespace(self, items): 943 namespace = Namespace() 944 namespace.merge_items(items) 945 return namespace 946 947 # Namespace-related abstractions. 948 949 class Namespace: 950 951 """ 952 A local namespace which may either relate to a genuine set of function 953 locals or the initialisation of a structure or module. 954 """ 955 956 def __init__(self): 957 958 """ 959 Initialise the namespace with a mapping of local names to possible 960 types, a list of return values and of possible returned local 961 namespaces. The namespace also tracks the "current" types and a mapping 962 of temporary value names to types. 963 """ 964 965 self.names = {} 966 self.returns = [] 967 self.return_locals = [] 968 self.raises = [] 969 self.temp = {} 970 self.types = [] 971 972 def set_types(self, types): 973 self.types = types 974 975 def add(self, name, types): 976 if self.names.has_key(name): 977 combine(self.names[name], types) 978 else: 979 self.store(name, types) 980 981 def store(self, name, types): 982 self.names[name] = types 983 984 __setitem__ = store 985 986 def load(self, name): 987 return self.names[name] 988 989 __getitem__ = load 990 991 def revoke(self, name, type): 992 self.names[name].remove(type) 993 994 def revoke_exception_type(self, type): 995 self.raises.remove(type) 996 997 def merge_namespace(self, namespace, everything=1): 998 self.merge_items(namespace.names.items()) 999 if everything: 1000 combine(self.returns, namespace.returns) 1001 combine(self.return_locals, namespace.return_locals) 1002 combine(self.raises, namespace.raises) 1003 for name, values in namespace.temp.items(): 1004 if values: 1005 if not self.temp.has_key(name) or not self.temp[name]: 1006 self.temp[name] = [[]] 1007 combine(self.temp[name][-1], values[-1]) 1008 1009 def merge_items(self, items): 1010 for name, types in items: 1011 self.merge(name, types) 1012 1013 def merge(self, name, types): 1014 if not self.names.has_key(name): 1015 self.names[name] = types[:] 1016 else: 1017 existing = self.names[name] 1018 combine(existing, types) 1019 1020 def snapshot(self): 1021 1022 "Make a snapshot of the locals and remember them." 1023 1024 namespace = Namespace() 1025 namespace.merge_namespace(self) 1026 self.return_locals.append(namespace) 1027 1028 def reset(self): 1029 1030 "Reset a namespace in preparation for merging with returned locals." 1031 1032 self.names = {} 1033 1034 def __repr__(self): 1035 return repr(self.names) 1036 1037 class Attribute: 1038 1039 """ 1040 An attribute abstraction, indicating the type of the attribute along with 1041 its context or origin. 1042 """ 1043 1044 def __init__(self, context, type): 1045 self.context = context 1046 self.type = type 1047 1048 def __eq__(self, other): 1049 return hasattr(other, "type") and other.type == self.type or other == self.type 1050 1051 def __repr__(self): 1052 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 1053 1054 class Self: 1055 1056 """ 1057 A program node encapsulating object/context information in an argument list. 1058 This is not particularly like Attribute, Class, Instance or other such 1059 things, since it actually appears in the program representation. 1060 """ 1061 1062 def __init__(self, attribute): 1063 self.types = [attribute] 1064 1065 def combine(target, additions): 1066 1067 """ 1068 Merge into the 'target' sequence the given 'additions', preventing duplicate 1069 items. 1070 """ 1071 1072 for addition in additions: 1073 if addition not in target: 1074 target.append(addition) 1075 1076 def find_attributes(structure, name): 1077 1078 """ 1079 Find for the given 'structure' all attributes for the given 'name', visiting 1080 base classes where appropriate and returning the attributes in order of 1081 descending precedence for all possible base classes. 1082 1083 The elements in the result list are 2-tuples which contain the attribute and 1084 the structure involved in accessing the attribute. 1085 """ 1086 1087 # First attempt to search the instance/class namespace. 1088 1089 try: 1090 l = structure.namespace.load(name) 1091 attributes = [] 1092 for attribute in l: 1093 attributes.append((attribute, structure)) 1094 1095 # If that does not work, attempt to investigate any class or base classes. 1096 1097 except KeyError: 1098 attributes = [] 1099 1100 # Investigate any instance's implementing class. 1101 1102 if isinstance(structure, Instance): 1103 for attr in structure.namespace.load("__class__"): 1104 cls = attr.type 1105 l = get_attributes(cls, name) 1106 combine(attributes, l) 1107 1108 # Investigate any class's base classes. 1109 1110 elif isinstance(structure, Class): 1111 1112 # If no base classes exist, return an indicator that no attribute 1113 # exists. 1114 1115 if not structure.base_refs: 1116 return [(None, structure)] 1117 1118 # Otherwise, find all possible base classes. 1119 1120 for base_refs in structure.base_refs: 1121 base_attributes = [] 1122 1123 # For each base class, find attributes either in the base 1124 # class or its own base classes. 1125 1126 for base_ref in base_refs: 1127 l = get_attributes(base_ref, name) 1128 combine(base_attributes, l) 1129 1130 combine(attributes, base_attributes) 1131 1132 return attributes 1133 1134 def get_attributes(structure, name): 1135 1136 """ 1137 Return all possible attributes for the given 'structure' having the given 1138 'name', wrapping each attribute in an Attribute object which includes 1139 context information for the attribute access. 1140 1141 The elements in the result list are 2-tuples which contain the attribute and 1142 the structure involved in accessing the attribute. 1143 """ 1144 1145 if isinstance(structure, Attribute): 1146 structure = structure.type 1147 results = [] 1148 for attribute, accessor in find_attributes(structure, name): 1149 if attribute is not None and isinstance(structure, Structure): 1150 results.append((Attribute(structure, attribute.type), accessor)) 1151 else: 1152 results.append((attribute, accessor)) 1153 return results 1154 1155 # Convenience functions. 1156 1157 def annotate(module, builtins=None): 1158 1159 """ 1160 Annotate the given 'module', also employing the optional 'builtins' module, 1161 if specified. 1162 """ 1163 1164 annotator = Annotator() 1165 if builtins is not None: 1166 annotator.process(module, builtins) 1167 else: 1168 annotator.process(module) 1169 1170 def annotate_all(modules, builtins): 1171 annotate(builtins) 1172 for module in modules: 1173 annotate(module, builtins) 1174 1175 # vim: tabstop=4 expandtab shiftwidth=4