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(Exception): 73 def __init__(self, exc, node, *args): 74 Exception.__init__(self, *args) 75 self.nodes = [node] 76 self.exc = exc 77 def add(self, node): 78 self.nodes.append(node) 79 def __str__(self): 80 return "%s, %s" % (self.exc, self.nodes) 81 82 class AnnotationMessage(Exception): 83 pass 84 85 # Annotation. 86 87 class Annotator(Visitor): 88 89 """ 90 The type annotator which traverses the program nodes, typically depth-first, 91 and maintains a record of the current set of types applying to the currently 92 considered operation. Such types are also recorded on the nodes, and a 93 special "system" record is maintained to monitor the level of annotation 94 activity with a view to recognising when no more annotations are possible. 95 96 Throughout the annotation activity, type information consists of lists of 97 Attribute objects where such objects retain information about the context of 98 the type (since a value in the program may be associated with an object or 99 class) and the actual type of the value being manipulated. Upon accessing 100 attribute information on namespaces, additional accessor information is also 101 exchanged - this provides a means of distinguishing between the different 102 types possible when the means of constructing the namespace may depend on 103 run-time behaviour. 104 """ 105 106 def __init__(self): 107 108 "Initialise the visitor." 109 110 Visitor.__init__(self) 111 self.system = system 112 113 # Satisfy visitor issues. 114 115 self.visitor = self 116 117 def process(self, module, builtins=None): 118 119 """ 120 Process the given 'module', using the optional 'builtins' to access 121 built-in classes and functions. 122 """ 123 124 self.subprograms = [] 125 self.current_subprograms = [] 126 self.current_namespaces = [] 127 128 # Give constants their own namespace. 129 130 for value, constant in module.simplifier.constants.items(): 131 constant.namespace = Namespace() 132 133 # Process the module, supplying builtins if possible. 134 135 self.global_namespace = Namespace() 136 137 if builtins is not None: 138 self.builtins_namespace = builtins.namespace 139 else: 140 self.builtins_namespace = self.global_namespace 141 142 return self.process_node(module) 143 144 def process_node(self, node, locals=None): 145 146 """ 147 Process a subprogram or module 'node', indicating any initial 'locals'. 148 Return an annotated subprogram or module. Note that this method may 149 mutate nodes in the original program. 150 """ 151 152 # Determine the namespace. 153 154 if locals is not None: 155 self.namespace = locals 156 else: 157 self.namespace = self.global_namespace 158 159 # Record the current subprogram and namespace. 160 161 self.current_subprograms.append(node) 162 self.current_namespaces.append(self.namespace) 163 164 # Add namespace details to any structure involved. 165 166 if getattr(node, "structure", None) is not None: 167 node.structure.namespace = Namespace() 168 169 # Initialise bases where appropriate. 170 171 if hasattr(node.structure, "bases"): 172 base_refs = [] 173 for base in node.structure.bases: 174 self.dispatch(base) 175 base_refs.append(self.namespace.types) 176 node.structure.base_refs = base_refs 177 178 # Dispatch to the code itself. 179 180 node.namespace = self.namespace 181 result = self.dispatch(node) 182 result.namespace = self.namespace 183 184 # Obtain the return values. 185 186 self.last_returns = self.namespace.returns 187 self.returned_locals = self.namespace.return_locals 188 189 # Restore the previous subprogram and namespace. 190 191 self.current_namespaces.pop() 192 if self.current_namespaces: 193 self.namespace = self.current_namespaces[-1] 194 195 self.current_subprograms.pop() 196 197 return result 198 199 def annotate(self, node): 200 201 "Annotate the given 'node' in the system." 202 203 self.system.annotate(node, 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 for attr in ("expr", "lvalue", "test", "handler"): 215 value = getattr(node, attr, None) 216 if value is not None: 217 setattr(node, attr, self.dispatch(value)) 218 for attr in ("body", "else_", "finally_", "code"): 219 value = getattr(node, attr, None) 220 if value is not None: 221 setattr(node, attr, self.dispatches(value)) 222 return node 223 224 def dispatch(self, node, *args): 225 try: 226 return Visitor.dispatch(self, node, *args) 227 except AnnotationError, exc: 228 exc.add(node) 229 raise 230 except AnnotationMessage, exc: 231 raise AnnotationError(exc, node) 232 233 def visitLoadRef(self, loadref): 234 self.namespace.set_types([Attribute(None, loadref.ref)]) 235 self.annotate(loadref) 236 return loadref 237 238 def visitLoadName(self, loadname): 239 self.namespace.set_types(self.namespace.load(loadname.name)) 240 result = loadname 241 self.annotate(result) 242 return result 243 244 def visitStoreName(self, storename): 245 storename.expr = self.dispatch(storename.expr) 246 self.namespace.store(storename.name, self.namespace.types) 247 return storename 248 249 def visitLoadTemp(self, loadtemp): 250 index = getattr(loadtemp, "index", None) 251 try: 252 self.namespace.set_types(self.namespace.temp[index][-1]) 253 except KeyError: 254 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 255 self.annotate(loadtemp) 256 return loadtemp 257 258 def visitStoreTemp(self, storetemp): 259 storetemp.expr = self.dispatch(storetemp.expr) 260 index = getattr(storetemp, "index", None) 261 if not self.namespace.temp.has_key(index): 262 self.namespace.temp[index] = [] 263 self.namespace.temp[index].append(self.namespace.types) 264 return storetemp 265 266 def visitReleaseTemp(self, releasetemp): 267 index = getattr(releasetemp, "index", None) 268 try: 269 self.namespace.temp[index].pop() 270 except KeyError: 271 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 272 except IndexError: 273 pass #raise AnnotationMessage, "Temporary store index '%s' is empty." % index 274 return releasetemp 275 276 def visitLoadAttr(self, loadattr): 277 loadattr.expr = self.dispatch(loadattr.expr) 278 types = [] 279 accesses = {} 280 non_accesses = {} 281 for attr in self.namespace.types: 282 for attribute, accessor in get_attributes(attr.type, loadattr.name): 283 if attribute is not None: 284 types.append(attribute) 285 if not accesses.has_key(attr.type): 286 accesses[attr.type] = [] 287 accesses[attr.type].append((attribute, accessor)) 288 else: 289 print "Empty attribute", loadattr.name, "via accessor", accessor 290 if not non_accesses.has_key(attr.type): 291 non_accesses[attr.type] = [] 292 non_accesses[attr.type].append((attribute, accessor)) 293 self.namespace.set_types(types) 294 loadattr.accesses = accesses 295 loadattr.non_accesses = non_accesses 296 self.annotate(loadattr) 297 return loadattr 298 299 def visitStoreAttr(self, storeattr): 300 storeattr.expr = self.dispatch(storeattr.expr) 301 expr = self.namespace.types 302 storeattr.lvalue = self.dispatch(storeattr.lvalue) 303 writes = {} 304 for attr in self.namespace.types: 305 if attr is None: 306 print "Empty attribute storage attempt" 307 continue 308 attr.type.namespace.store(storeattr.name, expr) 309 writes[attr.type] = attr.type.namespace.load(storeattr.name) 310 storeattr.writes = writes 311 return storeattr 312 313 def visitConditional(self, conditional): 314 315 # Conditionals keep local namespace changes isolated. 316 # With Return nodes inside the body/else sections, the changes are 317 # communicated to the caller. 318 319 conditional.test = self.dispatch(conditional.test) 320 saved_namespace = self.namespace 321 322 self.namespace = Namespace() 323 self.namespace.merge_namespace(saved_namespace) 324 conditional.body = self.dispatches(conditional.body) 325 body_namespace = self.namespace 326 327 self.namespace = Namespace() 328 self.namespace.merge_namespace(saved_namespace) 329 conditional.else_ = self.dispatches(conditional.else_) 330 else_namespace = self.namespace 331 332 self.namespace = Namespace() 333 self.namespace.merge_namespace(body_namespace) 334 self.namespace.merge_namespace(else_namespace) 335 return conditional 336 337 def visitReturn(self, return_): 338 if hasattr(return_, "expr"): 339 return_.expr = self.dispatch(return_.expr) 340 combine(self.namespace.returns, self.namespace.types) 341 self.annotate(return_) 342 self.namespace.snapshot() 343 return return_ 344 345 def visitInvoke(self, invoke): 346 invoke.expr = self.dispatch(invoke.expr) 347 invocation_types = self.namespace.types 348 349 if isinstance(invoke, InvokeFunction): 350 self.process_args(invoke) 351 352 # Now locate and invoke the subprogram. This can be complicated because 353 # the target may be a class or object, and there may be many different 354 # related subprograms. 355 356 invocations = [] 357 358 # Visit each callable in turn, finding subprograms. 359 360 for attr in invocation_types: 361 362 # Deal with class invocations by providing instance objects. 363 # Here, each class is queried for the __init__ method, which may 364 # exist for some combinations of classes in a hierarchy but not for 365 # others. 366 367 if isinstance(attr.type, Class): 368 attributes = get_attributes(attr.type, "__init__") 369 370 # Deal with object invocations by using __call__ methods. 371 372 elif isinstance(attr.type, Instance): 373 attributes = get_attributes(attr.type, "__call__") 374 375 # Normal functions or methods are more straightforward. 376 # Here, we model them using an attribute with no context and with 377 # no associated accessor. 378 379 else: 380 attributes = [(attr, None)] 381 382 # Inspect each attribute and extract the subprogram. 383 384 for attribute, accessor in attributes: 385 386 # If a class is involved, presume that it must create a new 387 # object. 388 389 if isinstance(attr.type, Class): 390 391 # Instantiate the class. 392 # NOTE: Should probably only allocate a single instance. 393 394 instance = self.new_instance(invoke, "new", attr.type.full_name(), attr.type) 395 396 # For instantiations, switch the context. 397 398 if attribute is not None: 399 attribute = Attribute(instance, attribute.type) 400 401 # Skip cases where no callable is found. 402 403 if attribute is not None: 404 405 # If a subprogram is defined, invoke it. 406 407 self.invoke_subprogram(invoke, attribute) 408 if attribute.type not in invocations: 409 invocations.append(attribute.type) 410 411 elif not isinstance(attr.type, Class): 412 print "Invocation type is None for", accessor 413 414 # Special case: initialisation. 415 416 if isinstance(attr.type, Class): 417 418 # Associate the instance with the result of this invocation. 419 420 self.namespace.set_types([Attribute(None, instance)]) 421 self.annotate(invoke) 422 423 invoke.invocations = invocations 424 425 return invoke 426 427 visitInvokeFunction = visitInvoke 428 visitInvokeBlock = visitInvoke 429 430 # Utility methods. 431 432 def new_instance(self, node, reason, target, type): 433 434 "Create, on the given 'node', a new instance with the given 'type'." 435 436 if not hasattr(node, "instances"): 437 node.instances = {} 438 439 if not node.instances.has_key((reason, target, type)): 440 instance = Instance() 441 instance.namespace = Namespace() 442 instance.namespace.store("__class__", [Attribute(None, type)]) 443 node.instances[(reason, target, type)] = instance 444 445 return node.instances[(reason, target, type)] 446 447 def invoke_subprogram(self, invoke, subprogram): 448 449 "Invoke using the given 'invoke' node the given 'subprogram'." 450 451 # Test to see if anything has changed. 452 453 if hasattr(invoke, "syscount") and invoke.syscount == self.system.count: 454 return 455 456 # Remember the state of the system. 457 458 else: 459 invoke.syscount = self.system.count 460 461 # Test for context information, making it into a real attribute. 462 463 if subprogram.context is not None: 464 context = Attribute(None, subprogram.context) 465 target = subprogram.type 466 else: 467 context = None 468 target = subprogram.type 469 470 # Provide the correct namespace for the invocation. 471 472 if isinstance(invoke, InvokeBlock): 473 namespace = Namespace() 474 namespace.merge_namespace(self.namespace) 475 else: 476 items = self.make_items(invoke, target, context) 477 namespace = self.make_namespace(items) 478 479 # Process the subprogram. 480 481 self.process_node(target, namespace) 482 483 # NOTE: Improve and verify this. 484 485 if getattr(target, "returns_value", 0): 486 self.namespace.set_types(self.last_returns) 487 self.annotate(invoke) 488 489 if isinstance(invoke, InvokeBlock): 490 for locals in self.returned_locals: 491 self.namespace.merge_namespace(locals) 492 493 def process_args(self, invoke): 494 495 # NOTE: Consider initialiser invocation for classes. 496 497 types = [] 498 args = [] 499 500 # Get type information for regular arguments. 501 502 for arg in invoke.args: 503 args.append(self.dispatch(arg)) 504 types.append(self.namespace.types) 505 506 # Get type information for star and dstar arguments. 507 508 if invoke.star is not None: 509 param, default = invoke.star 510 default = self.dispatch(default) 511 invoke.star = param, default 512 types.append(default.types) 513 514 if invoke.dstar is not None: 515 param, default = invoke.dstar 516 default = self.dispatch(default) 517 invoke.dstar = param, default 518 types.append(default.types) 519 520 invoke.args = args 521 522 def make_items(self, invocation, subprogram, context): 523 524 """ 525 Make an items mapping for the 'invocation' of the 'subprogram' using the 526 given 'context' (which may be None). 527 """ 528 529 if context is not None: 530 args = [Self(context)] + invocation.args 531 else: 532 args = invocation.args 533 534 # Sort the arguments into positional and keyword arguments. 535 536 pos_args = [] 537 kw_args = [] 538 add_kw = 0 539 for arg in args: 540 if not add_kw: 541 if not isinstance(arg, Keyword): 542 pos_args.append(arg) 543 else: 544 add_kw = 1 545 if add_kw: 546 if isinstance(arg, Keyword): 547 kw_args.append(arg) 548 else: 549 raise AnnotationMessage, "Positional argument appears after keyword arguments in '%s'." % callfunc 550 551 params = subprogram.params 552 items = [] 553 star_args = [] 554 555 # Match each positional argument, taking excess arguments as star args. 556 557 for arg in pos_args: 558 if params: 559 param, default = params[0] 560 if arg is None: 561 arg = default 562 items.append((param, arg.types)) 563 params = params[1:] 564 else: 565 star_args.append(arg) 566 567 # Collect the remaining defaults. 568 569 while params: 570 param, default = params[0] 571 if kw_args.has_key(param): 572 arg = kw_args[param] 573 del kw_args[param] 574 elif default is None: 575 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) 576 items.append((param, arg.types)) 577 params = params[1:] 578 579 dstar_args = kw_args 580 581 # Construct temporary objects. 582 583 if star_args: 584 list_type = self.builtins_namespace.load("list")[0] # NOTE: Hack to get list type. 585 star = self.new_instance(invocation, "star", subprogram.full_name(), list_type.type) 586 star_types = [Attribute(None, star)] 587 else: 588 star_types = None 589 590 if dstar_args: 591 dict_type = self.builtins_namespace.load("dict")[0] # NOTE: Hack to get dict type. 592 dstar = self.new_instance(invocation, "dstar", subprogram.full_name(), dict_type.type) 593 dstar_types = [Attribute(None, dstar)] 594 else: 595 dstar_types = None 596 597 # NOTE: Merge the objects properly. 598 599 star_types = star_types or invocation.star and invocation.star.types 600 dstar_types = dstar_types or invocation.dstar and invocation.dstar.types 601 602 # Add star and dstar. 603 604 if star_types is not None: 605 if subprogram.star is not None: 606 param, default = subprogram.star 607 items.append((param, star_types)) 608 else: 609 raise AnnotationMessage, "Invocation provides unwanted *args." 610 elif subprogram.star is not None: 611 param, default = subprogram.star 612 arg = self.dispatch(default) # NOTE: Review reprocessing. 613 items.append((param, arg.types)) 614 615 if dstar_types is not None: 616 if subprogram.dstar is not None: 617 param, default = subprogram.dstar 618 items.append((param, dstar_types)) 619 else: 620 raise AnnotationMessage, "Invocation provides unwanted **args." 621 elif subprogram.dstar is not None: 622 param, default = subprogram.dstar 623 arg = self.dispatch(default) # NOTE: Review reprocessing. 624 items.append((param, arg.types)) 625 626 return items 627 628 def make_namespace(self, items): 629 namespace = Namespace() 630 namespace.merge_items(items) 631 return namespace 632 633 # Namespace-related abstractions. 634 635 class Namespace: 636 637 """ 638 A local namespace which may either relate to a genuine set of function 639 locals or the initialisation of a structure or module. 640 """ 641 642 def __init__(self): 643 644 """ 645 Initialise the namespace with a mapping of local names to possible 646 types, a list of return values and of possible returned local 647 namespaces. The namespace also tracks the "current" types and a mapping 648 of temporary value names to types. 649 """ 650 651 self.names = {} 652 self.returns = [] 653 self.return_locals = [] 654 self.temp = {} 655 self.types = [] 656 657 def set_types(self, types): 658 self.types = types 659 660 def store(self, name, types): 661 self.names[name] = types 662 663 __setattr_ = store 664 665 def load(self, name): 666 return self.names[name] 667 668 __getattr__ = load 669 670 def merge_namespace(self, namespace): 671 self.merge_items(namespace.names.items()) 672 combine(self.returns, namespace.returns) 673 self.temp = namespace.temp 674 675 def merge_items(self, items): 676 for name, types in items: 677 self.merge(name, types) 678 679 def merge(self, name, types): 680 if not self.names.has_key(name): 681 self.names[name] = types[:] 682 else: 683 existing = self.names[name] 684 combine(existing, types) 685 686 def snapshot(self): 687 688 "Make a snapshot of the locals and remember them." 689 690 namespace = Namespace() 691 namespace.merge_namespace(self) 692 self.return_locals.append(namespace) 693 694 def __repr__(self): 695 return repr(self.names) 696 697 class Attribute: 698 699 """ 700 An attribute abstraction, indicating the type of the attribute along with 701 its context or origin. 702 """ 703 704 def __init__(self, context, type): 705 self.context = context 706 self.type = type 707 708 def __eq__(self, other): 709 return hasattr(other, "type") and other.type == self.type or other == self.type 710 711 def __repr__(self): 712 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 713 714 class Self: 715 def __init__(self, attribute): 716 self.types = [attribute] 717 718 def combine(target, additions): 719 for addition in additions: 720 if addition not in target: 721 target.append(addition) 722 723 def find_attributes(structure, name): 724 725 """ 726 Find for the given 'structure' all attributes for the given 'name', visiting 727 base classes where appropriate and returning the attributes in order of 728 descending precedence for all possible base classes. 729 730 The elements in the result list are 2-tuples which contain the attribute and 731 the structure involved in accessing the attribute. 732 """ 733 734 # First attempt to search the instance/class namespace. 735 736 try: 737 l = structure.namespace.load(name) 738 attributes = [] 739 for attribute in l: 740 attributes.append((attribute, structure)) 741 742 # If that does not work, attempt to investigate any class or base classes. 743 744 except KeyError: 745 attributes = [] 746 747 # Investigate any instance's implementing class. 748 749 if isinstance(structure, Instance): 750 for attr in structure.namespace.load("__class__"): 751 cls = attr.type 752 l = get_attributes(cls, name) 753 combine(attributes, l) 754 755 # Investigate any class's base classes. 756 757 elif isinstance(structure, Class): 758 759 # If no base classes exist, return an indicator that no attribute 760 # exists. 761 762 if not structure.base_refs: 763 return [(None, structure)] 764 765 # Otherwise, find all possible base classes. 766 767 for base_refs in structure.base_refs: 768 base_attributes = [] 769 770 # For each base class, find attributes either in the base 771 # class or its own base classes. 772 773 for base_ref in base_refs: 774 l = get_attributes(base_ref, name) 775 combine(base_attributes, l) 776 777 combine(attributes, base_attributes) 778 779 return attributes 780 781 def get_attributes(structure, name): 782 783 """ 784 Return all possible attributes for the given 'structure' having the given 785 'name', wrapping each attribute in an Attribute object which includes 786 context information for the attribute access. 787 788 The elements in the result list are 2-tuples which contain the attribute and 789 the structure involved in accessing the attribute. 790 """ 791 792 if isinstance(structure, Attribute): 793 structure = structure.type 794 results = [] 795 for attribute, accessor in find_attributes(structure, name): 796 if attribute is not None and isinstance(structure, Structure): 797 results.append((Attribute(structure, attribute.type), accessor)) 798 else: 799 results.append((attribute, accessor)) 800 return results 801 802 # Convenience functions. 803 804 def annotate(module, builtins=None): 805 806 """ 807 Annotate the given 'module', also employing the optional 'builtins' module, 808 if specified. 809 """ 810 811 annotator = Annotator() 812 if builtins is not None: 813 annotator.process(module, builtins) 814 else: 815 annotator.process(module) 816 817 def annotate_all(modules, builtins): 818 annotate(builtins) 819 for module in modules: 820 annotate(module, builtins) 821 822 # vim: tabstop=4 expandtab shiftwidth=4