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.store(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 items.append((param, arg.types)) 806 params = params[1:] 807 else: 808 star_args.append(arg) 809 810 # Collect the remaining defaults. 811 812 while params: 813 param, default = params[0] 814 if kw_args.has_key(param): 815 arg = kw_args[param] 816 del kw_args[param] 817 elif default is not None: 818 arg = self.dispatch(default) 819 else: 820 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) 821 items.append((param, arg.types)) 822 params = params[1:] 823 824 dstar_args = kw_args.values() 825 826 # Construct temporary objects. 827 828 if star_args: 829 star_invocation = self.make_star_args(invocation, subprogram, star_args) 830 self.dispatch(star_invocation) 831 star_types = star_invocation.types 832 else: 833 star_types = None 834 835 if dstar_args: 836 dstar_invocation = self.make_dstar_args(invocation, subprogram, dstar_args) # NOTE: To be written! 837 self.dispatch(dstar_invocation) 838 dstar_types = dstar_invocation.types 839 else: 840 dstar_types = None 841 842 # NOTE: Merge the objects properly. 843 844 star_types = star_types or invocation.star and invocation.star.types 845 dstar_types = dstar_types or invocation.dstar and invocation.dstar.types 846 847 # Add star and dstar. 848 849 if star_types is not None: 850 if subprogram.star is not None: 851 param, default = subprogram.star 852 items.append((param, star_types)) 853 else: 854 raise AnnotationMessage, "Invocation provides unwanted *args." 855 elif subprogram.star is not None: 856 param, default = subprogram.star 857 arg = self.dispatch(default) # NOTE: Review reprocessing. 858 items.append((param, arg.types)) 859 860 if dstar_types is not None: 861 if subprogram.dstar is not None: 862 param, default = subprogram.dstar 863 items.append((param, dstar_types)) 864 else: 865 raise AnnotationMessage, "Invocation provides unwanted **args." 866 elif subprogram.dstar is not None: 867 param, default = subprogram.dstar 868 arg = self.dispatch(default) # NOTE: Review reprocessing. 869 items.append((param, arg.types)) 870 871 # Record the parameter types. 872 873 if not hasattr(subprogram, "paramtypes"): 874 subprogram.paramtypes = {} 875 876 for param, types in items: 877 if not subprogram.paramtypes.has_key(param): 878 subprogram.paramtypes[param] = [] 879 combine(subprogram.paramtypes[param], types) 880 881 return items 882 883 def make_star_args(self, invocation, subprogram, star_args): 884 885 "Make a subprogram which initialises a list containing 'star_args'." 886 887 if not hasattr(invocation, "stars"): 888 invocation.stars = {} 889 890 if not invocation.stars.has_key(subprogram.full_name()): 891 code=[ 892 StoreTemp( 893 expr=InvokeFunction( 894 expr=LoadAttr( 895 expr=LoadRef( 896 ref=self.builtins 897 ), 898 name="list", 899 nstype="module", 900 ), 901 args=[], 902 star=None, 903 dstar=None 904 ) 905 ) 906 ] 907 908 for arg in star_args: 909 code.append( 910 InvokeFunction( 911 expr=LoadAttr( 912 expr=LoadTemp(), 913 name="append" 914 ), 915 args=[arg], 916 star=None, 917 dstar=None 918 ) 919 ) 920 921 code += [ 922 Return(expr=LoadTemp(release=1)) 923 ] 924 925 invocation.stars[subprogram.full_name()] = InvokeBlock( 926 produces_result=1, 927 expr=LoadRef( 928 ref=Subprogram( 929 name=None, 930 returns_value=1, 931 params=[], 932 star=None, 933 dstar=None, 934 code=code 935 ) 936 ) 937 ) 938 939 return invocation.stars[subprogram.full_name()] 940 941 def make_namespace(self, items): 942 namespace = Namespace() 943 namespace.merge_items(items) 944 return namespace 945 946 # Namespace-related abstractions. 947 948 class Namespace: 949 950 """ 951 A local namespace which may either relate to a genuine set of function 952 locals or the initialisation of a structure or module. 953 """ 954 955 def __init__(self): 956 957 """ 958 Initialise the namespace with a mapping of local names to possible 959 types, a list of return values and of possible returned local 960 namespaces. The namespace also tracks the "current" types and a mapping 961 of temporary value names to types. 962 """ 963 964 self.names = {} 965 self.returns = [] 966 self.return_locals = [] 967 self.raises = [] 968 self.temp = {} 969 self.types = [] 970 971 def set_types(self, types): 972 self.types = types 973 974 def store(self, name, types): 975 self.names[name] = types 976 977 __setitem__ = store 978 979 def load(self, name): 980 return self.names[name] 981 982 __getitem__ = load 983 984 def revoke(self, name, type): 985 self.names[name].remove(type) 986 987 def revoke_exception_type(self, type): 988 self.raises.remove(type) 989 990 def merge_namespace(self, namespace, everything=1): 991 self.merge_items(namespace.names.items()) 992 if everything: 993 combine(self.returns, namespace.returns) 994 combine(self.return_locals, namespace.return_locals) 995 combine(self.raises, namespace.raises) 996 for name, values in namespace.temp.items(): 997 if values: 998 if not self.temp.has_key(name) or not self.temp[name]: 999 self.temp[name] = [[]] 1000 combine(self.temp[name][-1], values[-1]) 1001 1002 def merge_items(self, items): 1003 for name, types in items: 1004 self.merge(name, types) 1005 1006 def merge(self, name, types): 1007 if not self.names.has_key(name): 1008 self.names[name] = types[:] 1009 else: 1010 existing = self.names[name] 1011 combine(existing, types) 1012 1013 def snapshot(self): 1014 1015 "Make a snapshot of the locals and remember them." 1016 1017 namespace = Namespace() 1018 namespace.merge_namespace(self) 1019 self.return_locals.append(namespace) 1020 1021 def reset(self): 1022 1023 "Reset a namespace in preparation for merging with returned locals." 1024 1025 self.names = {} 1026 1027 def __repr__(self): 1028 return repr(self.names) 1029 1030 class Attribute: 1031 1032 """ 1033 An attribute abstraction, indicating the type of the attribute along with 1034 its context or origin. 1035 """ 1036 1037 def __init__(self, context, type): 1038 self.context = context 1039 self.type = type 1040 1041 def __eq__(self, other): 1042 return hasattr(other, "type") and other.type == self.type or other == self.type 1043 1044 def __repr__(self): 1045 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 1046 1047 class Self: 1048 1049 """ 1050 A program node encapsulating object/context information in an argument list. 1051 This is not particularly like Attribute, Class, Instance or other such 1052 things, since it actually appears in the program representation. 1053 """ 1054 1055 def __init__(self, attribute): 1056 self.types = [attribute] 1057 1058 def combine(target, additions): 1059 1060 """ 1061 Merge into the 'target' sequence the given 'additions', preventing duplicate 1062 items. 1063 """ 1064 1065 for addition in additions: 1066 if addition not in target: 1067 target.append(addition) 1068 1069 def find_attributes(structure, name): 1070 1071 """ 1072 Find for the given 'structure' all attributes for the given 'name', visiting 1073 base classes where appropriate and returning the attributes in order of 1074 descending precedence for all possible base classes. 1075 1076 The elements in the result list are 2-tuples which contain the attribute and 1077 the structure involved in accessing the attribute. 1078 """ 1079 1080 # First attempt to search the instance/class namespace. 1081 1082 try: 1083 l = structure.namespace.load(name) 1084 attributes = [] 1085 for attribute in l: 1086 attributes.append((attribute, structure)) 1087 1088 # If that does not work, attempt to investigate any class or base classes. 1089 1090 except KeyError: 1091 attributes = [] 1092 1093 # Investigate any instance's implementing class. 1094 1095 if isinstance(structure, Instance): 1096 for attr in structure.namespace.load("__class__"): 1097 cls = attr.type 1098 l = get_attributes(cls, name) 1099 combine(attributes, l) 1100 1101 # Investigate any class's base classes. 1102 1103 elif isinstance(structure, Class): 1104 1105 # If no base classes exist, return an indicator that no attribute 1106 # exists. 1107 1108 if not structure.base_refs: 1109 return [(None, structure)] 1110 1111 # Otherwise, find all possible base classes. 1112 1113 for base_refs in structure.base_refs: 1114 base_attributes = [] 1115 1116 # For each base class, find attributes either in the base 1117 # class or its own base classes. 1118 1119 for base_ref in base_refs: 1120 l = get_attributes(base_ref, name) 1121 combine(base_attributes, l) 1122 1123 combine(attributes, base_attributes) 1124 1125 return attributes 1126 1127 def get_attributes(structure, name): 1128 1129 """ 1130 Return all possible attributes for the given 'structure' having the given 1131 'name', wrapping each attribute in an Attribute object which includes 1132 context information for the attribute access. 1133 1134 The elements in the result list are 2-tuples which contain the attribute and 1135 the structure involved in accessing the attribute. 1136 """ 1137 1138 if isinstance(structure, Attribute): 1139 structure = structure.type 1140 results = [] 1141 for attribute, accessor in find_attributes(structure, name): 1142 if attribute is not None and isinstance(structure, Structure): 1143 results.append((Attribute(structure, attribute.type), accessor)) 1144 else: 1145 results.append((attribute, accessor)) 1146 return results 1147 1148 # Convenience functions. 1149 1150 def annotate(module, builtins=None): 1151 1152 """ 1153 Annotate the given 'module', also employing the optional 'builtins' module, 1154 if specified. 1155 """ 1156 1157 annotator = Annotator() 1158 if builtins is not None: 1159 annotator.process(module, builtins) 1160 else: 1161 annotator.process(module) 1162 1163 def annotate_all(modules, builtins): 1164 annotate(builtins) 1165 for module in modules: 1166 annotate(module, builtins) 1167 1168 # vim: tabstop=4 expandtab shiftwidth=4