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 # Prevent infinite recursion. 153 154 if node in self.current_subprograms: 155 return node 156 157 # Determine the namespace. 158 159 if locals: 160 self.namespace = locals 161 else: 162 self.namespace = self.global_namespace 163 164 # Record the current subprogram and namespace. 165 166 self.current_subprograms.append(node) 167 self.current_namespaces.append(self.namespace) 168 169 # Add namespace details to any structure involved. 170 171 if getattr(node, "structure", None) is not None: 172 node.structure.namespace = Namespace() 173 174 # Initialise bases where appropriate. 175 176 if hasattr(node.structure, "bases"): 177 base_refs = [] 178 for base in node.structure.bases: 179 self.dispatch(base) 180 base_refs.append(self.namespace.types) 181 node.structure.base_refs = base_refs 182 183 # Dispatch to the code itself. 184 185 node.namespace = self.namespace 186 result = self.dispatch(node) 187 result.namespace = self.namespace 188 189 # Obtain the return values. 190 191 self.last_returns = self.namespace.returns 192 self.returned_locals = self.namespace.return_locals 193 194 # Restore the previous subprogram and namespace. 195 196 self.current_namespaces.pop() 197 if self.current_namespaces: 198 self.namespace = self.current_namespaces[-1] 199 200 self.current_subprograms.pop() 201 202 return result 203 204 def annotate(self, node): 205 206 "Annotate the given 'node' in the system." 207 208 self.system.annotate(node, self.namespace.types) 209 210 # Visitor methods. 211 212 def default(self, node): 213 214 """ 215 Process the given 'node', given that it does not have a specific 216 handler. 217 """ 218 219 for attr in ("expr", "lvalue", "test", "handler"): 220 value = getattr(node, attr, None) 221 if value is not None: 222 setattr(node, attr, self.dispatch(value)) 223 for attr in ("body", "else_", "finally_", "code"): 224 value = getattr(node, attr, None) 225 if value is not None: 226 setattr(node, attr, self.dispatches(value)) 227 return node 228 229 def dispatch(self, node, *args): 230 try: 231 return Visitor.dispatch(self, node, *args) 232 except AnnotationError, exc: 233 exc.add(node) 234 raise 235 except AnnotationMessage, exc: 236 raise AnnotationError(exc, node) 237 238 def visitLoadRef(self, loadref): 239 self.namespace.set_types([Attribute(None, loadref.ref)]) 240 self.annotate(loadref) 241 return loadref 242 243 def visitLoadName(self, loadname): 244 self.namespace.set_types(self.namespace.load(loadname.name)) 245 result = loadname 246 self.annotate(result) 247 return result 248 249 def visitStoreName(self, storename): 250 storename.expr = self.dispatch(storename.expr) 251 self.namespace.store(storename.name, self.namespace.types) 252 return storename 253 254 def visitLoadTemp(self, loadtemp): 255 index = getattr(loadtemp, "index", None) 256 try: 257 self.namespace.set_types(self.namespace.temp[index][-1]) 258 except KeyError: 259 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 260 self.annotate(loadtemp) 261 return loadtemp 262 263 def visitStoreTemp(self, storetemp): 264 storetemp.expr = self.dispatch(storetemp.expr) 265 index = getattr(storetemp, "index", None) 266 if not self.namespace.temp.has_key(index): 267 self.namespace.temp[index] = [] 268 self.namespace.temp[index].append(self.namespace.types) 269 return storetemp 270 271 def visitReleaseTemp(self, releasetemp): 272 index = getattr(releasetemp, "index", None) 273 try: 274 self.namespace.temp[index].pop() 275 except KeyError: 276 raise AnnotationMessage, "Temporary store index '%s' not defined." % index 277 except IndexError: 278 pass #raise AnnotationMessage, "Temporary store index '%s' is empty." % index 279 return releasetemp 280 281 def visitLoadAttr(self, loadattr): 282 loadattr.expr = self.dispatch(loadattr.expr) 283 types = [] 284 accesses = {} 285 for attr in self.namespace.types: 286 if not accesses.has_key(attr.type): 287 accesses[attr.type] = [] 288 for attribute, accessor in get_attributes(attr.type, loadattr.name): 289 if attribute is not None: 290 types.append(attribute) 291 else: 292 print "Empty attribute via accessor", accessor 293 accesses[attr.type].append((attribute, accessor)) 294 self.namespace.set_types(types) 295 loadattr.accesses = 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 = Instance() 395 instance.namespace = Namespace() 396 instance.namespace.store("__class__", [Attribute(None, attr.type)]) 397 398 # For instantiations, switch the context. 399 400 if attribute is not None: 401 attribute = Attribute(instance, attribute.type) 402 403 # Skip cases where no callable is found. 404 405 if attribute is not None: 406 407 # If a subprogram is defined, invoke it. 408 409 self.invoke_subprogram(invoke, attribute) 410 if attribute.type not in invocations: 411 invocations.append(attribute.type) 412 413 else: 414 print "Invocation type is None for", accessor 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 invoke_subprogram(self, invoke, subprogram): 433 434 """ 435 Invoke using the given 'invoke' node the given 'subprogram'. 436 """ 437 438 # Test to see if anything has changed. 439 440 if hasattr(invoke, "syscount") and invoke.syscount == self.system.count: 441 return 442 443 # Test for context information, making it into a real attribute. 444 445 if subprogram.context is not None: 446 context = Attribute(None, subprogram.context) 447 target = subprogram.type 448 else: 449 context = None 450 target = subprogram.type 451 452 # Provide the correct namespace for the invocation. 453 454 if isinstance(invoke, InvokeBlock): 455 namespace = Namespace() 456 namespace.merge_namespace(self.namespace) 457 else: 458 items = self.make_items(invoke, target, context) 459 namespace = self.make_namespace(items) 460 461 # Process the subprogram. 462 463 self.process_node(target, namespace) 464 465 # NOTE: Improve and verify this. 466 467 if getattr(target, "returns_value", 0): 468 self.namespace.set_types(self.last_returns) 469 self.annotate(invoke) 470 471 if isinstance(invoke, InvokeBlock): 472 for locals in self.returned_locals: 473 self.namespace.merge_namespace(locals) 474 475 # Remember the state of the system. 476 477 invoke.syscount = self.system.count 478 479 def process_args(self, invoke): 480 481 # NOTE: Consider initialiser invocation for classes. 482 483 types = [] 484 args = [] 485 486 # Get type information for regular arguments. 487 488 for arg in invoke.args: 489 args.append(self.dispatch(arg)) 490 types.append(self.namespace.types) 491 492 # Get type information for star and dstar arguments. 493 494 if invoke.star is not None: 495 param, default = invoke.star 496 default = self.dispatch(default) 497 invoke.star = param, default 498 types.append(default.types) 499 500 if invoke.dstar is not None: 501 param, default = invoke.dstar 502 default = self.dispatch(default) 503 invoke.dstar = param, default 504 types.append(default.types) 505 506 invoke.args = args 507 508 def make_items(self, invocation, subprogram, context): 509 510 """ 511 Make an items mapping for the 'invocation' of the 'subprogram' using the 512 given 'context' (which may be None). 513 """ 514 515 if context is not None: 516 args = [Self(context)] + invocation.args 517 else: 518 args = invocation.args 519 520 # Sort the arguments into positional and keyword arguments. 521 522 pos_args = [] 523 kw_args = [] 524 add_kw = 0 525 for arg in args: 526 if not add_kw: 527 if not isinstance(arg, Keyword): 528 pos_args.append(arg) 529 else: 530 add_kw = 1 531 if add_kw: 532 if isinstance(arg, Keyword): 533 kw_args.append(arg) 534 else: 535 raise AnnotationMessage, "Positional argument appears after keyword arguments in '%s'." % callfunc 536 537 params = subprogram.params 538 items = [] 539 star_args = [] 540 541 # Match each positional argument, taking excess arguments as star args. 542 543 for arg in pos_args: 544 if params: 545 param, default = params[0] 546 if arg is None: 547 arg = default 548 items.append((param, arg.types)) 549 params = params[1:] 550 else: 551 star_args.append(arg) 552 553 # Collect the remaining defaults. 554 555 while params: 556 param, default = params[0] 557 if kw_args.has_key(param): 558 arg = kw_args[param] 559 del kw_args[param] 560 elif default is None: 561 raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) 562 items.append((param, arg.types)) 563 params = params[1:] 564 565 dstar_args = kw_args 566 567 # Construct temporary objects. 568 569 if star_args: 570 list_type = self.builtins_namespace.load("list")[0] # NOTE: Hack to get list type. 571 star = Instance() 572 star.namespace = Namespace() 573 star.namespace.store("__class__", [Attribute(None, list_type.type)]) 574 star_types = [Attribute(None, star)] 575 else: 576 star_types = None 577 578 if dstar_args: 579 dict_type = self.builtins_namespace.load("dict")[0] # NOTE: Hack to get dict type. 580 dstar = Instance() 581 dstar.namespace = Namespace() 582 dstar.namespace.store("__class__", [Attribute(None, dict_type.type)]) 583 dstar_types = [Attribute(None, dstar)] 584 else: 585 dstar_types = None 586 587 # NOTE: Merge the objects properly. 588 589 star_types = star_types or invocation.star and invocation.star.types 590 dstar_types = dstar_types or invocation.dstar and invocation.dstar.types 591 592 # Add star and dstar. 593 594 if star_types is not None: 595 if subprogram.star is not None: 596 param, default = subprogram.star 597 items.append((param, star_types)) 598 else: 599 raise AnnotationMessage, "Invocation provides unwanted *args." 600 elif subprogram.star is not None: 601 param, default = subprogram.star 602 arg = self.dispatch(default) # NOTE: Review reprocessing. 603 items.append((param, arg.types)) 604 605 if dstar_types is not None: 606 if subprogram.dstar is not None: 607 param, default = subprogram.dstar 608 items.append((param, dstar_types)) 609 else: 610 raise AnnotationMessage, "Invocation provides unwanted **args." 611 elif subprogram.dstar is not None: 612 param, default = subprogram.dstar 613 arg = self.dispatch(default) # NOTE: Review reprocessing. 614 items.append((param, arg.types)) 615 616 return items 617 618 def make_namespace(self, items): 619 namespace = Namespace() 620 namespace.merge_items(items) 621 return namespace 622 623 # Namespace-related abstractions. 624 625 class Namespace: 626 627 """ 628 A local namespace which may either relate to a genuine set of function 629 locals or the initialisation of a structure or module. 630 """ 631 632 def __init__(self): 633 634 """ 635 Initialise the namespace with a mapping of local names to possible 636 types, a list of return values and of possible returned local 637 namespaces. The namespace also tracks the "current" types and a mapping 638 of temporary value names to types. 639 """ 640 641 self.names = {} 642 self.returns = [] 643 self.return_locals = [] 644 self.temp = {} 645 self.types = [] 646 647 def set_types(self, types): 648 self.types = types 649 650 def store(self, name, types): 651 self.names[name] = types 652 653 __setattr_ = store 654 655 def load(self, name): 656 return self.names[name] 657 658 __getattr__ = load 659 660 def merge_namespace(self, namespace): 661 self.merge_items(namespace.names.items()) 662 combine(self.returns, namespace.returns) 663 self.temp = namespace.temp 664 665 def merge_items(self, items): 666 for name, types in items: 667 self.merge(name, types) 668 669 def merge(self, name, types): 670 if not self.names.has_key(name): 671 self.names[name] = types[:] 672 else: 673 existing = self.names[name] 674 combine(existing, types) 675 676 def snapshot(self): 677 678 "Make a snapshot of the locals and remember them." 679 680 namespace = Namespace() 681 namespace.merge_namespace(self) 682 self.return_locals.append(namespace) 683 684 def __repr__(self): 685 return repr(self.names) 686 687 class Attribute: 688 689 """ 690 An attribute abstraction, indicating the type of the attribute along with 691 its context or origin. 692 """ 693 694 def __init__(self, context, type): 695 self.context = context 696 self.type = type 697 698 def __eq__(self, other): 699 return hasattr(other, "type") and other.type == self.type or other == self.type 700 701 def __repr__(self): 702 return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) 703 704 class Self: 705 def __init__(self, attribute): 706 self.types = [attribute] 707 708 def combine(target, additions): 709 for addition in additions: 710 if addition not in target: 711 target.append(addition) 712 713 def find_attributes(structure, name): 714 715 """ 716 Find for the given 'structure' all attributes for the given 'name', visiting 717 base classes where appropriate and returning the attributes in order of 718 descending precedence for all possible base classes. 719 720 The elements in the result list are 2-tuples which contain the attribute and 721 the structure involved in accessing the attribute. 722 """ 723 724 # First attempt to search the instance/class namespace. 725 726 try: 727 l = structure.namespace.load(name) 728 attributes = [] 729 for attribute in l: 730 attributes.append((attribute, structure)) 731 732 # If that does not work, attempt to investigate any class or base classes. 733 734 except KeyError: 735 attributes = [] 736 737 # Investigate any instance's implementing class. 738 739 if isinstance(structure, Instance): 740 for attr in structure.namespace.load("__class__"): 741 cls = attr.type 742 l = get_attributes(cls, name) 743 combine(attributes, l) 744 745 # Investigate any class's base classes. 746 747 elif isinstance(structure, Class): 748 749 # If no base classes exist, return an indicator that no attribute 750 # exists. 751 752 if not structure.base_refs: 753 return [(None, structure)] 754 755 # Otherwise, find all possible base classes. 756 757 for base_refs in structure.base_refs: 758 base_attributes = [] 759 760 # For each base class, find attributes either in the base 761 # class or its own base classes. 762 763 for base_ref in base_refs: 764 l = get_attributes(base_ref, name) 765 combine(base_attributes, l) 766 767 combine(attributes, base_attributes) 768 769 return attributes 770 771 def get_attributes(structure, name): 772 773 """ 774 Return all possible attributes for the given 'structure' having the given 775 'name', wrapping each attribute in an Attribute object which includes 776 context information for the attribute access. 777 778 The elements in the result list are 2-tuples which contain the attribute and 779 the structure involved in accessing the attribute. 780 """ 781 782 if isinstance(structure, Attribute): 783 structure = structure.type 784 results = [] 785 for attribute, accessor in find_attributes(structure, name): 786 if attribute is not None and isinstance(structure, Structure): 787 results.append((Attribute(structure, attribute.type), accessor)) 788 else: 789 results.append((attribute, accessor)) 790 return results 791 792 # Convenience functions. 793 794 def annotate(module, builtins=None): 795 796 """ 797 Annotate the given 'module', also employing the optional 'builtins' module, 798 if specified. 799 """ 800 801 annotator = Annotator() 802 if builtins is not None: 803 annotator.process(module, builtins) 804 else: 805 annotator.process(module) 806 807 def annotate_all(modules, builtins): 808 annotate(builtins) 809 for module in modules: 810 annotate(module, builtins) 811 812 # vim: tabstop=4 expandtab shiftwidth=4